《藤晓程崇志宏人工智能的符号方法-东南大学》由会员分享，可在线阅读，更多相关《藤晓程崇志宏人工智能的符号方法-东南大学（80页珍藏版）》请在金锄头文库上搜索。
1、Rule-based Logical ReasoningDatabase Group, Southeast University, ChinaReported By：藤晓程，崇志宏Database Group, Southeast University, ChinaOutline1.A brief introduction on reasoning systems2.Logic programming language - Datalog3.Evaluation of Datalog with mapreduceRuled-based Reasoning SystemsDatabase Gro
2、up, Southeast University, ChinaDatabase Group, Southeast University, ChinaHistoryRule-Based Systems : Also known as expert systemsIdea: 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
3、 THEN action For example: If income 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 )Database G
4、roup, Southeast University, ChinaNaive Evaluation: Begin with EDB Use rules to infer new facts Repeat until no new facts can be inferredIn 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
5、,3)=IgreenPath(1,2), greenPath(2,3)= greenPath(1,3) = The Fixpoint ApproachThe Fixpoint Approach (Forward Chaining )Database Group, Southeast University, ChinaProof theoretic Approach (Backward Chaining )A fact is in the result if there exists a proof for it using the rules and the database facts (g
6、oal-driven)1.Each leaf is labeled by a fact from database instance I2.Parent-child relationship constructed from rule A1 A2, ., AngreenPath(1,3)greenPath(1,2)greenPath(2,3)green(1,2) green(2,3)rule 2rule 1Database Group, Southeast University, ChinaOutline1.Syntax(语法)2.Semantics(语义)3.Datalog with Neg
7、ation(带否定)4.Evaluation of Datalog(计算)Database Group, Southeast University, ChinaDatalog with negationExampleTwo Minimal ModelsDatabase Group, Southeast University, ChinaModel theoretic semantics : problems1.some programs have no model2.some programs have several minimal models (choose between them)3
8、4Database Group, Southeast University, ChinaFixpoint semantics : problems1.TP may not have any fixpoint P1 = p p2.TP may have several minimal fixpoints P2 = p q, q ptwo minimal fixpoints : p and q.3.4.Use propositional program for convenienceDatabase Group, Southeast University, ChinaSemipositive da
9、talogonly 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 domain)2.Replace R(x) by R(x)Database Group, Southeast University, ChinaStratified datalogIdea: if an IDB R has already been defined, then we k
10、now what NOT R isStratified program: each IDB relation is defined by previous rules before its negation is neededDatabase Group, Southeast University, ChinaDependency Graph1.Nodes = IDB predicates. 2.Arc p - q iff p .q. 3.Arc p - q labeled iff q is negatedDatabase Group, Southeast University, ChinaA
11、nother Example: “Win”win(X) :- move(X,Y) facts produced by top-down approaches Database Group, Southeast University, ChinaTransformationDatabase Group, Southeast University, ChinaTransformationDatabase Group, Southeast University, ChinaImprovementsRepeated Variables and Constants in Rule BodiesDatab
12、ase Group, Southeast University, ChinaImprovementsCounting:record depths at which supplementary relation atoms occurnot safe: infinite set of tuples possibleDatabase Group, Southeast University, ChinaMagic set and well-founded modelsProblem for example :the magic sets transformation of a stratified
13、program may not be stratified Extend magic sets to stratified/modular stratified programs? Well-founded models?Sips(sideways information passing strategy)Database Group, Southeast University, Chinapredict call graphArc from a to qi label 0 Arc form a to pi label 1Database Group, Southeast University
14、, Chinawell-founded sipsFor each arc in the sip1.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-valuedPreserve the well-founded modelDatabase Group, Southeast University, ChinaOutline1.A brief introduction on reasoning systems2.Logic prog
15、ramming language - Datalog3.Evaluation of Datalog with mapreduceDatabase Group, Southeast University, ChinaMapreduce FrameworkDatabase 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 union - (1)(2) 4.Test for fixpoint A simple reachability queryDatabase Group, Southeast Univer
