XTT is a knowledge representation formalism for rules.
XTT allows for structurization of the rules base, by introducing:
Rules use an expressive attribute language.
So going deeper, general issues are as follows:
Now, considering a system, containing knowledge expressed in XTT, some other issues are:
Some issues include:
We need attributes to build descriptions of state of the system. The language we use is based on attributes. So the expressiveness of the attributive language limits the expressiveness of the rule language.
The aspects of the attributive language are:
For each attribute a type has to be stated. A type is named and it specifies:
What do we need types for anyway? Not all languages use types, e.g. Lisp, Prolog after all.
We want attribute types because:
Name | Prolog | Java | C | RDB |
---|---|---|---|---|
Bool | basic use | java.lang.Boolean | int | bool |
Integer | integer | java.lang.Number.Integer | int | integer |
Numeric (fixed-point) | float | java.lang.Number.Float | float | float |
Symbol | atom | java.lang.String | char* | var char |
Symbol might also be called String.
Integer is a subset of Numeric. An integer value is a numeric value with scale set to zero.
With numeric type there exist a predefined upper and lower limit enforced by the implementation, simply referenced as MAX
, and MIN
.
Primitive types:
byte short int long, float double, char String, boolean,
integer (a special case of numeric) for (byte short int long), numeric (general) for (float double), symbolic for (char String), bool for (boolean),
Complex types:
In our attributive language we have different (narrower?) semantics:
In the XTT+ there was a proposal of grouped attributes. This is a coherent extension to attributes. While it might look similar to structures, it still does have a different semantics.
Current type specs has Prolog, SQL and Java mapping in mind (we map to Java object, not basic types, so Integer, not int).
A domain is a discrete, finite set of allowed attribute values.
So in a general case we have the following cases:
Allowed values are expressed as a sum of ranges/values:
Such a sum may be ordered or unordered.
With numbers, we do not allow real (infinite) domains. We always assume a finite domain. Floating point number are allowed but it has to be explicitly stated how many digits are allowed before and after the decimal point. Additionally a set of values, narrowing the above, can be introduced.
In the original XTT there was a feature called enum.
This was in fact an ordered symbolic domain.
In this way, one might have a named att. day-of-week
of type symbolic, and be able to:
sun
and vice versamon < tue
In this case it is still a symbolic domain, so we store “mon” not 2!!!
This corresponds to the so-called linguistic variables in other formalisms.
In the original XTT attributes could be used in four contexts: conditional, assert, retract, decision. This is a legacy concept. We assume, that assert/retract, or the KB manipulation, is an operation not a context of an attribute, see HOPs.
For the XTT^2 we should simply consider:
Attributes can have atomic or non-atomic values (multiple) – this has to be specified explicitly. Number of values, for non-atomic attributes, is not bounded.
So an attribute value, for non-atomic values, is an ordered set. This set can be treated in different ways depending on semantics as a regular set or an ordered one. There should be operators defined which treat the set accordingly: as a set, as an ordered set, or other type.
Upon setting attribute value the same notation as for the domains should be used (a sum of ranges or values), i.e. S=<5,8>u{3}
In a general sense, an attribute
(as from the progrulesext papers))
\emph{Grouped Attributes} provide means for putting together some number of attributes to express relationships among them and their values. As a result a complex data structure, called a \emph{group}, is created which is similar to constructs present in programming languages (i.e. C language structures). A group is expressed as: \[ Group(Attrinbute1,Attribute2,\ldots,AttributeN) \] Attributes within a group can be referenced by their name: \[ Group.Attribute1 \] or position within the group: \[ Group/1 \] An application of Grouped Attributes could be expressing spatial coordinates: \[ Position(X,Y) \] where $Position$ is the group name, $X$ and $Y$ are attribute names.
Now, considering the primitive types discussion, as well as type system extension possiblity I would refine the GA proposal, as it might/should? be the key to type expressiveness.
I would propose certain simplification to the above definition:
In this case to support date, we would:
integer
with domain <0,upper>integer
with domain <1-12> (see ordered symbolic domains )symbolic
with domain {mon-sun}Such a GA can is named date, and could possibly be used “like a type”.
A group can function as an attribute, or attribute type.
…or the short attribute quickstart with examples.
sensor_temperature
Another example with grouped attributes.
Let's suppose we want to represent a “date of birth” and “current date”. So, we need a “date”, then think what is a date.
<1,30>
jan-dec
and an ordered domain 1-12
1970-MAX
The CASE tools should support a concept of an attribute library, where some predefined types are available.
We should try to establish relationship/s (if any?) between:
check how current ATTML correspnds to the above
imported from xtt+ refined
It should be kept in mind, that we must not mix he issues such as:
This discussion should be about single rules.
In the HeKatE project an extended rule language is proposed. It is based on the XTT language described in the original XTT papers. The version used in the project is currently called XTT+.
The XTT+ rule language is based on the classic concepts of rule languages for rule-based systems (liebowitz), with certain important extensions and features, such as:
Here, the XTT+ language will be simply referred to as XTT.
In XTT there is a strong assumption, that the rule base is explicitly structured. The rules with same sets of attributes are grouped within decision tables. On the rule level explicit inference control is allowed. This way, a set of tables is interconnected using links, corresponding to inference control. This makes up a decision-tree like structure, with tables in the tree nodes. In the general case, the XTT is a graph, with optionally cycles allowed.
In RBS, a rule has a general format:
IF condition THEN decision
This format can be used in both forward and backward chaining systems. However, here we focus on the production rule systems, based on the forward chaining paradigm. The power of a rule language stems from the syntax and semantics of the conditional and decision expressions. Number of systems implicitly assume, that this rule format can be extended to the conjunctive normal form (CNF)}, that is:
IF cond1 AND cond2 AND ... AND condN THEN decision
which in fact corresponds to a Horn clause (ben-ari:2001,ali-book-springer), that is:
!cond1 v !cond2 v ... v !condN v decision
or transformed to:
cond1 ^ cond2 ^ ... ^ condN -> decision
The decision expression could also be a compound one in the CNF. Now the question is what are the conditional and decision expressions. In number of systems these correspond to expressions in the propositional calculus, which makes the semantics somehow limited. Some systems try to use some subsets of predicate logic, which gives much more flexibility, but may complicate a RBS design and the inference process. This is the case of the Prolog language (bratko). In XTT these expressions are in the the attributive logic (ali-book-springer) described in more detail elsewhere. This gives much more power than the propositional logic, but does not introduce problems of the predicate logic-based inference.
In XTT an extended rule semantics is used. These extensions were introduced in (gjn2007enase), and refined in (gjn2007inap). They are: Grouped Attributes, and Attribute-Attribute Comparison
Other (gjn2007enase) extensions such as Link Labeling, Not-Defined Operator, and the Scope Operator. work on the intertable inference level, so they are not included here.
In XTT it is assumed, that the whole system state is described by the means of attributes.
The XTT+ rule firing process is coherent with the regular RBS sematics. It involves:
The condition checking can be decribed as a pattern matching process, where the whole condition evaluates true or false. The condition is an expression in the CNF build of expressions in the ALSV(FD). The condition is an expression in the ALSV(FD) language. Period.
The decision execution is where actions are possible. In a general case, the XTT+ rule decision involves:
For now, it is simply assumed, that the decision is expressed in a different way, comparing with the condition.
A discussion of the current extension of the attribute logic to Attribute Logic with Set Values over Finite Domains is contained in two papers for:
in the final version some discussion from the papers could be imported.
Bottom line:
cond1 ^ cond2 ^ … ^ condN | decision
In the above condI
are {A,O,V}
, where
The valid ALSV(FD) expressions are (as of salrules-ruleapps):
While the set of operators is not really closed, the general structure of the expression holds, thus limiting other possiblities.
The structure of the ALSV(FD) expression is always:
{current attribute values set} 2arg_relational_operator {conditional values set}.
so in fact we always have:
(See AVR for some possible exception.)
Features of this approach are:
Now the full formal description of logical cond
evaulation is in the papers.
This is called ALSV(FD) inference.
It is single step, non recursive matching for every expression, that is every cond
.
So condition checking is a simple pattern matching, where the conjunction:
cond1 ^ cond2 ^ ... ^ condN
is evaluated. If it evaluates true, the rule fires.
We assume the format discussed in ALSV(FD), that is:
cond1 ^ cond2 ^ ... ^ condN
See that section for inference, satisfaction, etc.
Value representation notation. It is assumed, that SV (abbrev. single valued) (previously atomic attributes) and values are written as:
This was prposed by ALi and is a sane method to tell them apart from the very first sight. This should be supported by the design tools!
From the logical point of view:
From practical point of view:
Now, all this applies to numerics only!!! Attribute vals having symbolic domain are always explicitely enumerated!
The proposal is to have an Intensional NonAtomic Specs as follows:
NonAtomVal := NonatomVal sum NonAtomVal NonAtomVal := val | RegionSpec RegionSpec := <val, val>
Where val
is of base/primitve type.
So this shoould map to an ordered set, a list.
It is used in
MultiValue semantics:
WDL seems to be a generic data structure, a Prolog list.
Before defining operators we should check, what are builtins to process lists as sets., e.g.:
The AVR is a situation such as:
A1<A2
in conditionA1 is A2
in decisionselect({A1},lt(3),assert({A2}))
meaning select values less then 3 from A1, assert to values of A2, in decission.AVR is both powerful but evil! It is very expressfull, but makes analysis, or sometimes the design, painful, or even not possible. So we do want to have some cases where we do not use AVR. There is no calculations or operations allowed on AVR, it just represents an attribute value.
AVR is related to the so-called Attribute-Attribute Comparison of XTT+.
This is antoher aspect of the rule lang expressiveness. It is assumed, that the decision is expressed in a different way, comparing with the the condition!
Some aspects are described below.
In the original XTT the general format was the same as the condition, that is:
dec1 ^ dec2 ^ ... ^ dec2
Actually we might ask what ^
means in this case.
Since there is no logical evaluation in the decision, it is simply a conjuction.
We could/should that these are interpreted sequentially. (this would help escape oprator expressions)
The decision spec also includes the inference control spec tablenr+rulenr!
The next step is to define what dec
is.
In the original XTT there are some general actions in the so-called decision context. The vague interpretation is “in a given cell do something on/using/with att H that appears in the table scheme”.
Examples of table decisions can be shown :
|| H | -++--------------------------+--------------- 0 || vmo operation(Arguments) | 1 || = 3 | 2 || = mean(H) | 3 || + {3} | 4 || - {4,5} | 5 || = G + H * 2 | 6 || = run_robot(G) | 7 || | x run_robot(G)
In a general sense, an XTT cell in the decision context is:
H vmo operation(Arguments).
vmo
is the value modification operator, or modop
for short.
What operations are available in a XTT cell depends on the attribute primitive type! Only some of these discussed below are generic.
In the decision, references to ANY attributes present in the same table can appear. Such references are not in the column of the table scheme.
The scheme presents a single attribute which value is/or can be modified.
The following modop
s are proposed.
Denoted as =
The simplest case
is(A,V)
is({A},{V})
Assert
Denoted as +
Retract
Denoted as -
Now, depending on the multivalue semantics, we could consider
I believe this (MVS) requires some sensible restriction.
Denoted as x
Disregard the value returned by an operation,
thus not modifying the attribute value.
This VMO could/should/is? allowed only with actions –> some actions might not modify the att value, but they can be somehow related to the attribute (see tho OO-like proposal).
this is under cnsideration
modop
arguments are values.
These values are either given or evaluated during the inference process.
The evaluation regards values referenced by attributes or values calculated as results of application of Evaluaion Operators, evalop
s for short.
i.e. arithmetic expressions can be calculated this way.
evalop
s could be nested, i.e.
add(2,div(3,sin(d)))
evaluates as: 2+(3/(sin(d)))
evalop
s should be considered in SVM and MVM (abbrev. single and multi value) modes.
The following evalops
are proposed:
There could a whole range of these, including regexps for strings. Can also be considered a restriction operation. They do depend on the attribute type, since the selection criteria is type-dependent.
select({A},lt(3))
now what happens with the selection? maybe we should consider:
select({A},lt(3),{A2})
, such as A1={1,2,3,4} → select({A},lt(3),{A2}) → A2={1,2}restrict({A},lt(3))
, such as A1={1,2,3,4} → restrict({A},lt(3)) → A1={1,2}select({A},lt(3),{A1})
, such as A1={1,2,3,4} → select({A},lt(3),{A1}) → A1={1,2}, or even _
instead of self reference?Maybe the criteria in the selects, can be expressed by exactly the same relational operators as in the conditinal part?
These allow to get some information about a set of attribute values. This information could be assigned, used, etc.
All of these apply only to the MVM?
Maybe we do not this a separate class? this is just a part of calculation class?
This probably applies only to Numerics
So we support any artithemtic expression, including a set of predefined math-only functions.
(So in fact, we could use any predefined arithemtic function. This does not mean ANY “function” (as in prog lang), only math functions operating on numeric values, and returning numeric values.)
Now, we could consider implementing a sensible set of functions, based
math.h
or rather java.lang.Math
In simple words there is a need for a set of operators providing arithmetic operations:
i.e. add(X,Y) which adds X and Y and returns the result.
X and Y in this case can be evalop
s as well.
In the classic production rules and RBS there is often operational semantics, e.g. if some condition is met DO sth.
Specs and Syntax: an action can:
action(A1...An) action(A1...An)
Where action is simply a C function, Java method, Prolog pred… In the 1st case Att valus is modified, the function returns the value.
Can we restrict it any further?
In the OO-like proposal, the action has to bound with the att whose value it changes.
This is an experiemntal stuff that needs integration with the groupped attributes concept.
An idea: think of an attribute as an object (yes, really!). It is a container for data of the form of a value/list/set. It also has methods, that can be triggered from the system (only from the decision!) or from the environment, or possibly both. This is an extension of the discussion we had in the attributive_language. To define data, we also define ways to handle it (data+processing, datastructs+algorithms, kr+predicates → it might one of the essential problems of AI/CS ).
This solution would enforce binding the actions to attributes they work on.
Example:
we have a robot,
a grouped att position
, with pos.x
, pos.y
is related to the actions such as go
,
because such an action changes the position, even thought it might be executed as go(forward, 5cm)
One can imagine actions that are triggered from the env.
e.g. when the robot changes the position, it triggers a method pos.update
One should keep in mind, that in some cases we have some simplified rule schemes, or types.
We should at least consider a rule with no precondition, one that fires always.
Considering ARD restrictions, we cannot just omit the condition, but put ANY
as value.
E.g.
There is a student with several grades indicated by attribute grades. A grade could be: 2,3,4,5 I need a count how many 2 grades he has (nrfail), how many grades in total (nrgrades), and what is the mean (grmean).
{grades}||nrfail | nrgrades|grmean --------++------------------------+----------------------+--------------------- ANY ||count(nrfail,{grades},2)|count(nrfail,{grades})|mean(grmean,{grades})
A rule without decision could serve as context switching point.
(Concerning the legacy Contexts we only have general Conditional and Decision now.)
It is important to identify certain table classes. These depend on the table contents.
Not all of these should be identified before the table design.
They could/should be identified during the design, before the analysis, or in order to asses the analysis possibilities.
The classes are not related to rule types, but to rule contents.
Some possible table types:
see the XTTML