藤晓程崇志宏：人工智能的符号方法-东南大学.pptx

Rule-based Logical Reasoning,2019/4/25,Database Group, Southeast University, China,Reported By： 藤晓程，崇志宏,2019/4/25,Database Group, Southeast University, China,Outline 1.A brief introduction on reasoning systems 2.Logic programming language - Datalog 3.Evaluation of Datalog with mapreduce,Ruled-based Reasoning Systems,2019/4/25,Database Group, Southeast University, China,2019/4/25,Database Group, Southeast University, China,History,Rule-Based Systems : Also known as expert systems Idea: to capture the knowledge of a human expert in a specialized domain and embody it within a software system. The knowledge is stored as rules of the form IF condition THEN action For example: If income 1000 THEN deny-mortgage,2019/4/25,Database Group, Southeast University, China,History,Some modern examples of rule based systems: 1.The NHS Direct adviser 2.The Automobile Diagnosis adviser 3.Ikea online assistant an RBS with a chatbox interface 4.American Express Authorizers Assistant - developed in 1988, but still in use today processes credit requests, deciding whether to authorise or deny very large: around 35,000 rules, including 3,000 “business rules” .,2019/4/25,Database Group, Southeast University, China,Architecture,knowledge base: contains the rules embodying expert knowledge about the problem domain database: contains the set of known facts about the problem currently being solved inference engine: carries out the reasoning process by linking the rules with the known facts to find a solution explanation facilities: provides information to user about the reasoning steps that are being followed user interface: communication between the user and the system,2019/4/25,Database Group, Southeast University, China,Tools,CLIPS : a productive development and delivery expert system tool which provides a complete environment for the construction of rule and/or object based expert systems IRIS Reasoner : Integrated Rule Inference System is an extensible reasoning engine for expressive rule-based languages. Reasoning over RDFS,WSML. Demo: /demo,2019/4/25,Database Group, Southeast University, China,Outline 1.A brief introduction on reasoning systems 2.Logic programming language - Datalog 3.Evaluation of Datalog with mapreduce,Datalog,2019/4/25,Database Group, Southeast University, China,2019/4/25,Database Group, Southeast University, China,Outline 1.Syntax(语法) 2.Semantics(语义) 3.Datalog with Negation(带否定) 4.Evaluation of Datalog(计算),2019/4/25,Database Group, Southeast University, China,Datalog-Syntax,Rule: greenPath(x,y) :- green(x,y) Head :- Body :- is read if ( also ) Atom: predicate/name of a relation Head: an atom literal : green(x,y) or green(x,y) 区别nogreen(x,y) an atom or a negation of an atom Body: AND of 0 or more literals,2019/4/25,Database Group, Southeast University, China,greenPath(x,x) :- 0 literal, means true subgoal : Atoms of body Datalog program : finite set of datalog rules 两个概念：外延和内涵 内涵是指一个概念所概括的思维对象本质特有的属性的总和 外延是指一个概念所概括的思维对象的数量或范围 如：“国家”的外延指古今中外一切国家,Datalog-Syntax,2019/4/25,Database Group, Southeast University, China,In a program, predicates can be either EDB = Extensional Database = facts.（外延） only in the body IDB = Intensional Database = relation defined by rules. （内涵） Head predicate is an IDB predicate Body subgoals :IDB/EDB i.e. greenPath(x,y) :- greenPath(x,z), greenPath(z,y) sch(P) = edb(P) idb(P),Datalog-Syntax,2019/4/25,Database Group, Southeast University, China,Program P: greenPath(x,y) :- green(x,y) Input I: sch(P) = green(x,y),red(x,y),greenPath(x,y) Instances over sch(P) green(1,2),red(2,3),greenPath(1,2) green(1,2),red(2,3),greenPath(2,3),Datalog-Syntax,2019/4/25,Database Group, Southeast University, China,Safe Datalog,Every variable in the head of a rule must also appear in the body greenPath(x,y,z) :- green (x,y) not safe!,2019/4/25,Database Group, Southeast University, China,Outline 1.Syntax(语法) 2.Semantics(语义) 3.Datalog with Negation(带否定) 4.Evaluation of Datalog(计算),2019/4/25,Database Group, Southeast University, China,Datalog-Semantics (without negation),3 equivalent approaches: Model theoretic Fixpoint theoretic Proof theoretic,2019/4/25,Database Group, Southeast University, China,Model theoretic Approach,model: 1.an instance over sch(P) 2.satisfying all the rules in datalog Program P: greenPath(x,y) :- green(x,y) greenPath(x,y) :- greenPath(x,z), greenPath(z,y) Input I: green(1,2),green(2,3) 1. green: (1,2),(2,3) greenPath: (1,2),(2,3) 2. green: (1,2),(2,3) greenPath: (1,2),(2,3),(1,3) 3. green: (1,2),(2,3) greenPath: (1,2),(2,3),(1,3),(1,4),x,2019/4/25,Database Group, Southeast University, China,Choose the minimum model 最小模型是唯一的么？,P(I) : The semantics of P on input I P(I)= green(1,2),green(2,3) , greenPath(1,2), greenPath(2,3), greenPath(1,3) ,Model theoretic Approach,2019/4/25,Database Group, Southeast University, China,Why the minimum model?,Closed world assumption: 1.databases are often incomplete and We cant say anything about the data that is not explicitly recorded 2.Treat the database as if it records complete information about the world,2019/4/25,Database Group, Southeast University, China,The Fixpoint Approach (Forward Chaining ),P :a datalog program, K: an instance over sch(P) A is an immediate consequence for K and P if 1.A K(R) for some edb R, or 2. AA1, . . . , An is an instantiation of a rule in P and each Ai is in K. TP :immediate consequence operator of P For each K, TP (K) consists of all facts A,2019/4/25,Database Group, Southeast University, China,TP (K) = K - K is a fixpoint of TP,The Fixpoint Approach,Program P: greenPath(x,y) :- green(x,y) greenPath(x,y) :- greenPath(x,z), greenPath(z,y) Input I: green(1,2),green(2,3) =IgreenPath(1,2), greenPath(2,3) = greenPath(1,3) =,The Fixpoint Approach (Forward Chaining ),2019/4/25,Database Group, Southeast University, China,Naive Evaluation: Begin with EDB Use rules to infer new facts Repeat until no new facts can be inferred,In this case : minimum fixpoint which equals P(I),Program P: greenPath(x,y) :- green(x,y) greenPath(x,y) :- greenPath(x,z), greenPath(z,y) Input I: green(1,2),green(2,3) =IgreenPath(1,2), greenPath(2,3) = greenPath(1,3) =,The Fixpoint Approach,The Fixpoint Approach (Forward Chaining ),2019/4/25,Database Group, Southeast University, China,Proof theoretic Approach (Backward Chaining ),A fact is in the result if there exists a proof for it using the rules and the database facts (goal-driven),1.Each leaf is labeled by a fact from database instance I 2.Parent-child relationship constructed from rule A1 A2, ., An,greenPath(1,3),greenPath(1,2),greenPath(2,3),green(1,2),green(2,3),rule 2,rule 1,2019/4/25,Database Group, Southeast University, China,Outline 1.Syntax(语法) 2.Semantics(语义) 3.Datalog with Negation(带否定) 4.Evaluation of Datalog(计算),2019/4/25,Database Group, Southeast University, China,Datalog with negation,Example,Two Minimal Models,2019/4/25,Database Group, Southeast University, China,Model theoretic semantics : problems,1.some programs have no model 2.some programs have several minimal models (choose between them) 3 4,2019/4/25,Database Group, Southeast University, China,Fixpoint semantics : problems,1.TP may not have any fixpoint P1 = p p 2.TP may have several minimal fixpoints P2 = p q, q p two minimal fixpoints : p and q. 3. 4.,Use propositional program for convenience,2019/4/25,Database Group, Southeast University, China,Semipositive datalog,only apply negation to edb relations,T(x, y) G(x, y) T(x, y) G(x, z),T(z, y),Solution: 1.new edb relation R holding the complement of R (w.r.t. the active domain) 2.Replace R(x) by R(x),2019/4/25,Database Group, Southeast University, China,Stratified datalog,Idea: if an IDB R has already been defined, then we know what NOT R is,Stratified program: each IDB relation is defined by previous rules before its negation is needed,2019/4/25,Database Group, Southeast University, China,Dependency Graph,1.Nodes = IDB predicates. 2.Arc p - q iff p .q 3.Arc p - q labeled iff q is negated,2019/4/25,Database Group, Southeast University, China,Another Example: “Win”,win(X) :- move(X,Y) & NOT win(Y),you win by forcing your opponent to a position where they have no move,2019/4/25,Database Group, Southeast University, China,Strata,largest number of s on a path from that predicate,2019/4/25,Database Group, Southeast University, China,Stratified Programs,no recursion involving negation (Stratified Datalog) finite strata-stratified- stratified model Infinite stratum -unstratified -no stratified model,2019/4/25,Database Group, Southeast University, China,Stratified Model/Perfect fixpoint,Evaluate strata 0, 1, in order Result is the stratified model.,2019/4/25,Database Group, Southeast University, China,Technical points,stratified model is one of the minimal models for the program If no negation, the stratified model is the minimum model agreement,2019/4/25,Database Group, Southeast University, China,Unstratified Datalog,extensions of the stratified semantics,From least to most general: Locally stratified models, modularly stratified models, stable/well-founded models.,2019/4/25,Database Group, Southeast University, China,Locally stratified models,2019/4/25,Database Group, Southeast University, China,Well-founded semantics,provide a natural semantics for all datalog programs,gives up settling all IDB facts some facts remain unknown 3-Valued Models,2019/4/25,Database Group, Southeast University, China,Example,win(x) moves(x, y),win(y),True:win(d),win(f ) False:win(e),win(g) Unknown:win(a),win(b),win(c),well-founded semantics,The goal is to compute the set of winning states (i.e., the set of states such that there exists a winning strategy for a player in this state).,2019/4/25,Database Group, Southeast University, China,3-valued minimal model for (extended) datalog,denote true by 1, false by 0, and unknown by extended : datalog program with 0, 1/2 and 1 as literals in bodies,omit unknown,I(ab)=min(I(a),I(b) I(a)=1-I(a),1/2,0,0,0,0,2019/4/25,Database Group, Southeast University, China,3-valued minimal model for (extended) datalog,Start :all atoms are false, denote this instance Lemma: sequence converges (收敛) to the least fixpoint of 3-TP P has a unique minimal 3-valued model that equals the least fixpoint of 3-TP semantics:minimal 3-valued model,2019/4/25,Database Group, Southeast University, China,3-stable Models of Datalog,I : 3-valued instance over sch(P) pg(P,I) : replace each negative literal A by (i.e., 0, 1 or 1/2) an extended datalog program minimal model /least fixpoint: pg(P, I)() ( conseqP(I) ) A 3-valued instance I over sch(P) is a 3-stable model of P iff conseqP(I) = I.,2019/4/25,Database Group, Southeast University, China,Example,2019/4/25,Database Group, Southeast University, China,well-founded semantics,several 3-stable models. at least one 3-stable model. well-founded semantics :consisting of all positive and negative facts belonging to all 3-stable models Previous example: Pwf =p, q,r well-founded model is also 3-stable model,2019/4/25,Database Group, Southeast University, China,Problem,Steps: 1.Checking all possible 3-valued instances 2.determining which are 3-stable models 3.taking their intersection effective but very inefficient How to compute the well-founded semantics efficiently?,2019/4/25,Database Group, Southeast University, China,A Fixpoint Definition,Define sequence: I0 = Ii+1 = conseqP (Ii) Idea: alternate underestimates and overestimates of positive facts until convergence,2019/4/25,Database Group, Southeast University, China,Example,I0 = = p,q,r ,s,t,u I1 = p,q,r ,s,t,u I2 = p,q,r ,s,t,u I3 = p,q,r ,s,t,u I4 = p,q,r ,s,t,u,I3(p)=I4(p)=1 I3(q)=I4(q)=1 I3(r)=I4(r)=0 Others 1/2,well-founded semantics: p, q, r,Alternating fixpoint semantics,2019/4/25,Database Group, Southeast University, China,Well-Founded and Stratified Semantics Agree,Theorem P :stratified datalog program P is total under the well-founded semantics for each 2-valued instance I over edb(P ), Pwf (I) = Pstrat(I).,2019/4/25,Database Group, Southeast University, China,Outline 1.Syntax(语法) 2.Semantics(语义) 3.Datalog with Negation(带否定) 4.Evaluation of Datalog(计算),2019/4/25,Database Group, Southeast University, China,Evaluation of Datalog,Two major classes of evaluation approaches: Bottom-Up Apply the datalog rules “from body to head” (forward) Top-Down Apply the datalog rules “from head to body” (backward),2019/4/25,Database Group, Southeast University, China,Bottom-up,Example,2019/4/25,Database Group, Southeast University, China,naive algorithm,redundant computation,2019/4/25,Database Group, Southeast University, China,Seminaive Evaluation,infer new facts at stage i + 1 using facts newly derived at stage i,Facts newly inferred,2019/4/25,Database Group, Southeast University, China,Top-down,Direct the search for a proof , e.g. T(2,x),T(x,y) :- G(x,y) T(x,y) :- G(x,z) ,T(z,y),Infinite recursive loops possible:,T(2,x),G(2,3),T(3,x),G(3,1),T(1,x),G(1,2),T(2,x),2019/4/25,Database Group, Southeast University, China,query-subquery (QSQ) framework,Sideways Information Passing(SIP): How information is passed in the body,a left-to-right evaluation,adornment,2019/4/25,Database Group, Southeast University, China,Supplementary Relations and QSQ Templates,bound by some previous literal, And needed by subsequent literal or in the result,QSQ template sequence : (sup0, . . . , supn),2019/4/25,Database Group, Southeast University, China,Example,adorned rules for the RSG query,2019/4/25,Database Group, Southeast University, China,2019/4/25,Database Group, Southeast University, China,2019/4/25,Database Group, Southeast University, China,2019/4/25,Database Group, Southeast University, China,2019/4/25,Database Group, Southeast University, China,Bottom-up VS Top-down,Top-down Ad: goal-oriented Disad: one-tuple-at-a-time, infinite loops possible. Bottom-up Ad: avoid infinite loops Disad:a lot of irrelevant computation,2019/4/25,Database Group, Southeast University, China,Magic set,Transforms a program into a new query : 1.same answer as the original query. 2.bottom-up technique ; facts produced by top-down approaches,2019/4/25,Database Group, Southeast University, China,Transformation,2019/4/25,Database Group, Southeast University, China,Transformation,2019/4/25,Database Group, Southeast University, China,Improvements,Repeated Variables and Constants in Rule Bodies,2019/4/25,Database Group, Southeast University, China,Improvements,Counting:record depths at which supplementary relation atoms occur,not safe: infinite set of tuples possible,2019/4/25,Database Group, Southeast University, China,Magic set and well-founded models,Problem for example :the magic sets transformation of a stratified program may not be stratified,Extend magic sets to stratified/modular stratified programs? Well-founded models? Sips(sideways information passing strategy),2019/4/25,Database Group, Southeast University, China,predict call graph,Arc from a to qi label 0 Arc form a to pi label 1,2019/4/25,Database Group, Southeast University, China,well-founded sips,For each arc in the sip,1.Qi is either the head of R or in an SCC lower than the SCC of the head R 2.Each ground instance of Qi is two-valued,Preserve the well-founded model,2019/4/25,Database Group, Southeast University, China,Outline 1.A brief introduction on reasoning systems 2.Logic programmin