Transcript Representação do Conhecimento

Knowledge Representation and
Reasoning
José Júlio Alferes
Luís Moniz Pereira
What is it ?
• What data does an intelligent “agent” deal with?
- Not just facts or tuples.
• How does an “agent” know what surrounds it?
The rules of the game?
– One must represent that “knowledge”.
• And what to do afterwards with that knowledge?
How to draw conclusions from it? How to reason?
• Knowledge Representation and Reasoning  AI
Algorithms and Data Structures  Computation
What is it good for ?
• Basic subject matter for Artificial Intelligence
– Planning
– Legal Knowledge
– Model-Based Diagnosis
• Expert Systems
• Semantic Web (http://www.w3.org)
– Web of Knowledge (http://www.rewerse.com)
What is this course about ?
• Logic approaches to knowledge
representation
• Issues in knowledge representation
– semantics, expressivity, structure, efficiency
•
•
•
•
Representation formalisms
Forms of reasoning
Methodologies
Applications
What prior knowledge ?
• Computational Logic
• Introduction to Artificial Intelligence
• Logic Programming
Bibliography
• Will be pointed out as we go along (articles,
surveys) in the summaries at the web page
• For the first part of the syllabus:
– Reasoning with Logic Programming
J. J. Alferes and L. M. Pereira
Springer LNAI, 1996
– Nonmonotonic Reasoning
G. Antoniou
MIT Press, 1996.
Logic for KRR
• Logic is a language conceived for
representing knowledge
• It was developed for representing
mathematical knowledge
• What is appropriate for mathematical
knowledge might not be so for representing
common sense
Mathematical knowledge vs
common sense
• Complete vs incomplete knowledge
– "x:xN→xR
– go_Work → use_car
• Solid inferences vs default ones
–
–
–
–
–
In the face incomplete knowledge
In emergency situations
In taxonomies
In legal reasoning
...
Monotonicity of Logic
• Classical Logic is monotonic
T |= F → T U T’ |= F
• This is a basic property which makes sense
for mathematical knowledge
• But is not desirable for knowledge
representation in general !
Non-monotonic logics
• Do not obey that property
• Default Logic
– Introduces default rules
• Autoepistemic Logic
– Introduces (modal) operators which speak
about knowledge and beliefs
• Logic Programming
Default Logic
• Proposed by Ray Reiter (1980)
go_Work → use_car
• Does not admit exceptions !
• Default rules
go_Work : use_car
use_car
More examples
anniversary(X)  friend(X) : give_gift(X)
give_gift(X)
friend(X,Y)  friend(Y,Z) : friend (X,Z)
friend(X,Z)
accused(X) : innocent(X)
innocent(X)
Default Logic Syntaxe
• A theory is a pair (W,D), where:
– W is a set of 1st order formulas
– D is a set of default rules of the form:
j : Y1, … ,Yn
g
– j (pre-requisites), Yi (justifications) and g
(conclusion) are 1st order formulas
The issue of semantics
• If j is true (where?) and all Yi are
consistent (with what?) then g becomes true
(becomes? Wasn’t it before?)
• Conclusions must:
– be a closed set
– contain W
– apply the rules of D maximally, without
becoming unsupported
Default extensions
• G(S) is the smallest set such that:
– W  G(S)
– Th(G(S)) = G(S)
– A:Bi/C  D, A  G(S) and Bi  S → C  G(S)
• E is an extension of (W,D) iff E = G(E)
Quasi-inductive definition
• E is an extension iff E = Ui Ei for:
– E0 = W
– Ei+1 = Th(Ei) U {C: A:Bj/C  D, A  Ei, Bj  E}
Some properties
• (W,D) has an inconsistent extension iff W is
inconsistent
– If an inconsistent extension exists, it is unique
• If W  Just  Conc is inconsistent , then
there is only a single extension
• If E is an extension of (W,D), then it is also
an extension of (W  E’,D) for any E’  E
Operational semantics
• The computation of an extension can be reduced to
finding a rule application order (without repetitions).
• P = (d1,d2,...) and P[k] is the initial segment of P
with k elements
• In(P) = Th(W  {conc(d) | d  P})
– The conclusions after rules in P are applied
• Out(P) = {Y | Y  just(d) and d  P }
– The formulas which may not become true, after
application of rules in P
Operational semantics (cont’d)
• d is applicable in P iff pre(d)  In(P) and Y 
In(P)
• P is a process iff " dk  P, dk is applicable in P[k-1]
• A process P is:
– successful iff In(P) ∩ Out(P) = {}.
• Otherwise it is failed.
– closed iff " d  D applicable in P → d  P
• Theorem: E is an extension iff there exists P,
successful and closed, such that In(P) = E
Computing extensions (Antoniou page 39)
extension(W,D,E) :- process(D,[],W,[],_,E,_).
process(D,Pcur,InCur,OutCur,P,In,Out) :getNewDefault(default(A,B,C),D,Pcur),
prove(InCur,[A]),
not prove(InCur,[~B]),
process(D,[default(A,B,C)|Pcur],[C|InCur],[~B|OutCur],P,In,Out).
process(D,P,In,Out,P,In,Out) :closed(D,P,In), successful(In,Out).
closed(D,P,In) :not (getNewDefault(default(A,B,C),D,P),
prove(In,[A]), not prove(In,[~B]) ).
successful(In,Out) :- not ( member(B,Out), member(B,In) ).
getNewDefault(Def,D,P) :- member(Def,D), not member(Def,P).
Normal theories
• Every rule has its justification identical to its
conclusion
• Normal theories always have extensions
• If D grows, then the extensions grow (semimonotonicity)
• They are not good for everything:
– John is a recent graduate
– Normally recent graduates are adult
– Normally adults, not recently graduated, have a job
(this cannot be coded with a normal rule!)
Problems
• No guarantee of extension existence
• Deficiencies in reasoning by cases
– D = {italian:wine/wine
– W ={italian v french}
french:wine/wine}
• No guarantee of consistency among justifications.
– D = {:usable(X),  broken(X)/usable(X)}
– W ={broken(right) v broken(left)}
• Non cummulativity
– D = {:p/p, pvq:p/p}
– derives p v q, but after adding p v q no longer does so