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

1、Rule-based Logical Reasoning2022-5-23Database Group, Southeast University, ChinaReported By： 藤晓程，崇志宏2022-5-23Database Group, Southeast University, ChinaOutlineOutline1.A brief introduction on reasoning 1.A brief introduction on reasoning systemssystems2.Logic programming language - Datalog3.Evaluati

2、on of Datalog with mapreduceRuled-based Reasoning Systems2022-5-23Database Group, Southeast University, China2022-5-23Database Group, Southeast University, ChinaHistoryRule-Based Systems : Rule-Based Systems : Also known as expert expert systemssystemsIdeaIdea: to capture the knowledge of a human ex

3、pert in a specialized domain and embody it within a software system. The knowledgeknowledge is stored as rulesrules of the form IF condition THEN action For example: If income 1000 THEN deny-If income K is a fixpointfixpoint of TP The Fixpoint ApproachProgram P:Program P:greenPath(x,y) :- green(x,y)

4、greenPath(x,y) :- greenPath(x,z), greenPath(z,y) Input I: Input I: green(1,2),green(2,3) =IgreenPath(1,2), greenPath(2,3) = greenPath(1,3) = (I) 2PT(I) 3PT(I) 2PT(I) PT(I) PTThe Fixpoint Approach (Forward Chaining )2022-5-23Database Group, Southeast University, China Naive Evaluation: Naive Evaluati

5、on: Begin with EDBUse rules to infer new factsRepeat until no new facts can be inferredIn this case : minimum minimum fixpointfixpointwhich equals P(I)P(I)Program P:Program P:greenPath(x,y) :- green(x,y)greenPath(x,y) :- greenPath(x,z), greenPath(z,y) Input I: Input I: green(1,2),green(2,3) =IgreenP

6、ath(1,2), greenPath(2,3) = greenPath(1,3) = The Fixpoint Approach(I) PT(I) 2PT(I) PT(I) 3PT(I) 2PTThe Fixpoint Approach (Forward Chaining )2022-5-23Database Group, Southeast University, ChinaProof theoretic Approach (Backward Chaining )A fact is in the result if there exists a proof for it using the

7、 rules and the database facts (goal-drivengoal-driven)1.Each leaf is labeledby a fact from database instance I I2.Parent-child relationshipconstructed fromrule A1 A2, ., AngreenPath(1,3)greenPath(1,2)greenPath(2,3) green(1,2) green(2,3)rule 2rule 12022-5-23Database Group, Southeast University, China

8、OutlineOutline1.Syntax(语法)2.Semantics(语义)3.Datalog with Negation(3.Datalog with Negation(带否定带否定) )4.Evaluation of Datalog(计算)2022-5-23Database Group, Southeast University, ChinaDatalog with negationExampleTwo Minimal ModelsTwo Minimal Models2022-5-23Database Group, Southeast University, ChinaModel t

9、heoretic semantics : problems1.some programs have no model2.some programs have several minimal models(choose between them)342022-5-23Database Group, Southeast University, ChinaFixpoint semantics : problems1.TP may not have any fixpointP1 = p p2.TP may have several minimal fixpointsP2 = p q, q p two

10、minimal fixpoints : p and q.3.4.Use propositional program for convenience2022-5-23Database Group, Southeast University, ChinaSemipositive datalogonly apply negation to edb relationsT(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 doma

11、in)2.Replace R(x) by R(x)2022-5-23Database Group, Southeast University, ChinaStratified datalogIdeaIdea: if an IDB R has already been definedIDB R has already been defined, then we know what NOT R isStratified programStratified program: each IDB relation is defined byprevious rules before its negati

12、on is needed2022-5-23Database Group, Southeast University, ChinaDependency Graph 1.Nodes = IDB predicates.2.Arc p - q iff p .q.3.Arc p - q labeled iff q is negated2022-5-23Database Group, Southeast University, ChinaAnother Example: “Win”win(X) :- move(X,Y) & NOT win(Y)you win by forcing your opp

13、onent to a position where they have no move2022-5-23Database Group, Southeast University, ChinaStrata largest number of s on a path from that predicate2022-5-23Database Group, Southeast University, ChinaStratified Programsno recursion involving negation (Stratified Datalog)finite strata-stratified-

14、stratified modelInfinite stratum -unstratified -no stratified model2022-5-23Database Group, Southeast University, ChinaStratified Model/Perfect fixpointEvaluate strata 0, 1, in orderResult is the stratified model.2022-5-23Database Group, Southeast University, ChinaTechnical pointsstratified model is

15、 one of the minimal models for the programIf no negation, the stratified model is the minimum modelagreement2022-5-23Database Group, Southeast University, ChinaUnstratified Datalogextensions of the stratified semanticsFrom least to most general:Locally stratified models,modularly stratified models,s

16、table/well-founded modelswell-founded models.2022-5-23Database Group, Southeast University, ChinaLocally stratified models 2022-5-23Database Group, Southeast University, ChinaWell-founded semanticsprovide a natural semantics for all datalog programsgives up settling all IDB facts some facts remain u

17、nknown3-Valued Models2022-5-23Database Group, Southeast University, ChinaExamplewin(x) moves(x, y),win(y)TrueTrue:win(d),win(f )FalseFalse:win(e),win(g)UnknownUnknown:win(a),win(b),win(c)well-founded semanticswell-founded semanticsThe goal is to compute the set of winning states (i.e., the set of st

18、ates such that there exists a winning strategy for a player in this state).2022-5-23Database Group, Southeast University, China3-valued minimal model for (extended) datalogdenote true by 1, false by 0, and unknown by true by 1, false by 0, and unknown by extended : datalog program with 0, 1/2 and 1

19、as literals in bodiesomit unknownomit unknownI(ab)=min(I(a),I(b)I(a)=1-I(a)1/200002022-5-23Database Group, Southeast University, China3-valued minimal model for (extended) datalogStart :all atoms are false, denote this instanceLemma: Lemma: sequence converges (收敛) to the least fixpoint of 3-TP P has

20、 a unique minimal 3-valued model that equals the least fixpoint of 3-TPsemanticssemantics:minimal 3-valued model2022-5-23Database Group, Southeast University, China3-stable Models of DatalogI :I : 3-valued instance over sch(P)pg(P,I) pg(P,I) : replace each negative literal A by (i.e., 0, 1 or 1/2)an

21、 extended datalog programminimal model /least fixpoint: minimal model /least fixpoint: pg(P, I I)() ( conseqP(I) conseqP(I) )A 3-valued instance I I over sch(P) is a 3-stable 3-stable model model of Piff conseqP(I) = Iiff conseqP(I) = I.2022-5-23Database Group, Southeast University, ChinaExample 202

22、2-5-23Database Group, Southeast University, Chinawell-founded semanticsseveral 3-stable models.at least one 3-stable model.well-founded semantics :well-founded semantics :consisting of all positive and negative facts belonging to all 3-stable modelsPrevious example: Pwf =p, q,rwell-founded model is

23、also 3-stable model2022-5-23Database Group, Southeast University, ChinaProblemSteps:1.Checking all possible 3-valued instances 2.determining which are 3-stable models3.taking their intersectioneffective but very inefficientHow to compute the well-founded semantics efficiently?2022-5-23Database Group

24、, Southeast University, ChinaA Fixpoint DefinitionDefine sequence:I I0 =I Ii+1 = conseqP (I Ii)Idea: alternate underestimates and overestimates of positive facts until convergence2022-5-23Database Group, Southeast University, ChinaExample I I0 = = p,q,r ,s,t,uI I1 1 = p,q,r ,s,t,uI I2 2 = p,q,r ,s,t

25、,uI I3 3 = p,q,r ,s,t,uI I4 4 = p,q,r ,s,t,uI I3(p)=I I4(p)=1I I3(q)=I I4(q)=1I I3(r)=I I4(r)=0Others 1/2well-founded semantics:p, q, rAlternating fixpoint semanticsAlternating fixpoint semantics2022-5-23Database Group, Southeast University, ChinaWell-Founded and Stratified Semantics Agree TheoremTh

26、eoremP :stratified datalog programP is total under the well-founded semanticsfor each 2-valued instance I over edb(P ), Pwf (I) = Pstrat(I).2022-5-23Database Group, Southeast University, ChinaOutlineOutline1.Syntax(语法)2.Semantics(语义)3.Datalog with Negation(带否定)4.Evaluation of Datalog(4.Evaluation of

27、 Datalog(计算计算) )2022-5-23Database Group, Southeast University, ChinaEvaluation of DatalogTwo major classes of evaluation approaches: Bottom-UpApply the datalog rules “from body to head” (forward) Top-DownApply the datalog rules “from head to body” (backward)2022-5-23Database Group, Southeast Univers

28、ity, ChinaBottom-upExample2022-5-23Database Group, Southeast University, Chinanaive algorithm redundant computation2022-5-23Database Group, Southeast University, ChinaSeminaive Evaluationinfer new facts at stage i + 1 using facts newly derived at stage iFacts newly inferred2022-5-23Database Group, S

29、outheast University, ChinaTop-downDirect the search for a proof , e.g. T(2,x)T(x,y) :- G(x,y)T(x,y) :- G(x,y)T(x,y) :- G(x,z) ,T(z,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).2022-5-23Database Group, Southeast University, Chinaquery-subquer

30、y (QSQ) frameworkSideways Information Passing(SIP):Sideways Information Passing(SIP):How information is passed in the bodya left-to-right evaluationadornment2022-5-23Database Group, Southeast University, ChinaSupplementary Relations and QSQ Templates bound by some previous literal, And needed by sub

31、sequent literal or in the resultQSQ template sequence : (sup0, . . . , supn)2022-5-23Database Group, Southeast University, ChinaExample adorned rules for the RSG query2022-5-23Database Group, Southeast University, China 2022-5-23Database Group, Southeast University, China 2022-5-23Database Group, So

32、utheast University, China 2022-5-23Database Group, Southeast University, China 2022-5-23Database Group, Southeast University, ChinaBottom-up VS Top-downTop-downTop-downAd: goal-oriented Disad: one-tuple-at-a-time, infinite loops possible.Bottom-upBottom-upAd: avoid infinite loopsDisad:a lot of irrel

33、evant computation 2022-5-23Database Group, Southeast University, ChinaMagic 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 2022-5-23Database Group, Southeast University, ChinaTransformation 2022-5-23Databas

34、e Group, Southeast University, ChinaTransformation 2022-5-23Database Group, Southeast University, ChinaImprovementsRepeated Variables and Constants in Rule Repeated Variables and Constants in Rule BodiesBodies2022-5-23Database Group, Southeast University, ChinaImprovementsCountingCounting:record dep

35、ths at which supplementary relation atoms occurnot safe: infinite set of tuples possible2022-5-23Database Group, Southeast University, ChinaMagic set and well-founded modelsProblem for example :the magic sets transformation of a stratified program may not be stratified Extend magic sets to stratifie

36、d/modular stratified programs?Well-founded models?SipsSips(sideways information passing strategy) 2022-5-23Database Group, Southeast University, Chinapredict call graphArc from a to qi label 0Arc form a to pi label 12022-5-23Database Group, Southeast University, Chinawell-founded sipsFor each arc in

37、 the sip1.Qi is either the head of R or or in an SCC lower than the SCC of the head R2.Each ground instance of Qi is two-valuedPreserve the well-founded modelPreserve the well-founded model2022-5-23Database Group, Southeast University, ChinaOutlineOutline1.A brief introduction on reasoning systems2.

38、Logic programming language - Datalog3.Evaluation of Datalog with 3.Evaluation of Datalog with mapreducemapreduce2022-5-23Database Group, Southeast University, ChinaMapreduce Framework2022-5-23Database Group, Southeast University, ChinaNave Evaluation1.Join:R(1,2),R(2,3),R(1,4),R(4,3) ,A(1,2),A(2,3),A(1,4),A(4,3) (1)Map-(1,R2),(2,R3),(1,R4),(4,R3) ,(2,A1),(3,A2),(4,A1),(3,A4)Reduce-A(1,3),A(1,3),A(1,2),A(2,3),A(1,4),A(4,3)2.Remove duplicate - A(1,3),A(1,2),A(2,3),A(1,4),A(4,3) (2)3.Compute