L11. An Example of Backward Chaining Program in Java An Rule Base System in Java RuleBaseSystem.java CarShop.data

Reasoning with Rules Knowledge represented as if-then rules Backward chain To prove a conclusion  from the known facts and knowledge (rules)

Major Elements A rule base A fact base Inference engine The set of if-then rules A fact base Known facts Inference engine Containing the reasoning logic used to process the rules and data

Backward Chaining IF 食欲が無い THEN 食事をしていない 熱がある 食欲が無い ワーキングメモリの中 （事前知識） （患者から得られた事実情報） IF 食事をしていない THEN 栄養が足りない IF 熱がある 栄養が足りない THEN 風邪を引く 風邪を引いている

A Rule-base System Architecture class RuleBaseSystem{} Rule Base Class FileManager Fact base class RuleBase{} In a file class Rule{} Interaction with Inference Engine Matching class Unifier{} Fire a Rule Select a Rule Acting

Backward Chaining 初期状態でワーキングメモリに以下の「事実」が入っているとします my-car is inexpensive my-car has a VTEC engine my-car is stylish my-car has several color models my-car has several seats my-car is a wagon

rule 　　　"CarRule1" if 　　　　　"?x is inexpensive" then 　　　"?x is made in Japan" Rule　　　"CarRule2" if 　　　　　"?x is small" rule 　　　　"CarRule3" If　　　　　　"?x is expensive" then 　　　　"?x is a foreign car" rule 　　　　"CarRule4" if 　　　　 "?x is big" 　　　　　　　"?x needs a lot of gas" then 　　　"?x is a foreign car" Rule　　　　"CarRule5" If　　　　　　"?x is made in Japan" 　　　　　　　"?x has Toyota's logo" then 　　　　"?x is a Toyota" rule 　　　　"CarRule6" if 　　　　　　"?x is made in Japan" 　　　　　　　"?x is a popular car" Ｔhen　　　　"?x is a Toyota" rule 　　　"CarRule7" if 　　　　　"?x is made in Japan" 　　　　　"?x has Honda's logo" then 　　　"?x is a Honda" rule 　　　"CarRule8" 　　　　　　"?x has a VTEC engine" rule 　　　"CarRule9" if 　　　　　"?x is a Toyota" 　　　　　　"?x has several seats" 　　　　　　"?x is a wagon" then　　　"?x is a Carolla Wagon" rule 　　　"CarRule10" 　　　　　　"?x is a hybrid car" then　　　"?x is a Prius" rule 　　　"CarRule11" if 　　　　　"?x is a Honda" 　　　　　　"?x is stylish" 　　　　　　"?x has several color models" then　　　"?x is an Accord Wagon" rule "CarRule12" if "?x is a Honda" 　　　　 "?x has an aluminium body" "?x has only 2 seats" then "?x is a NSX" rule "CarRule13" if "?x is a foreign car" "?x is a sports car" "?x is stylish" 　　　　 "?x has several color models" "?x has a big engine" then　 "?x is a Lamborghini Countach" rule "CarRule14" if "?x is a foreign car" "?x is red" then "?x is a Ferrari F50" rule "CarRule15" "?x is a good face" then "?x is a Jaguar XJ8"

Backward Chaining (アコードワゴンである?ｘは何ですか？) ここでは ?x is an Accord Wagon? という仮説を証明したいと思います。 （これを仮説というかは微妙ですが・・・）

Backward Chaining

Rule-base System Examples (2) public class RuleBaseSystem { static RuleBase rb; static File Manager fm; public static void main(String args[]){ fm = new FileManager(); Vector rules = fm.loadRules("ex11/CarShop.data"); Vector wm = fm.loadWm("ex11/CarShopWm.data"); rb = new RuleBase(rules,wm); StringTokenizer st = new StringTokenizer(args[0],","); Vector queries = new Vector(); for (int i = 0 ; i < st.countTokens();) { queries.addElement(st.nextToken()); } rb.backwardChain(queries); public void backwardChain(Vector hypothesis){ System.out.println("Hypothesis:"+hypothesis); Vector orgQueries = (Vector)hypothesis.clone(); Hashtable binding = new Hashtable(); if (matchingPatterns(hypothesis,binding)){ System.out.println("Yes"); System.out.println(binding); for (int i = 0 ; i < orgQueries.size() ; i++){ String aQuery = (String)orgQueries.elementAt(i); String anAnswer = instantiate(aQuery,binding); System.out.println("Query: "+aQuery); System.out.println("Answer:"+anAnswer); } } else { System.out.println("No");

Backward Chainingのプログラム Rule Baseクラス - matchingPatterns() public class RuleBase implements Serializable { ・・・ private boolean matchingPatterns(Vector thePatterns, Hashtable theBinding) { String firstPattern; if (thePatterns.size() == 1) { firstPattern = (String) thePatterns.elementAt(0); if (matchingPatternOne(firstPattern, theBinding, 0) != -1) { return true; } else { return false; } } else{ … 仮説の数が一つならば、その仮説とワーキングメモリ中の「事実」及びルールベース中のルールの後件部とのマッチングを行う。 仮説の数が二つ以上の場合の処理は自分で見て理解してみて下さい。

Backward Chainingのプログラム Rule Baseクラス - matchingPatternsOne() public class RuleBase implements Serializable { ・・・ private int matchingPatternOne(String thePattern, Hashtable theBinding, int cPoint) { if (cPoint < wm.size()) { // WME(Working Memory Elements) と Unify してみる． for (int i = cPoint; i < wm.size(); i++) { if ((new Unifier()).unify(thePattern, (String) wm.elementAt(i), theBinding)) { … return i + 1; } if (cPoint < wm.size() + rules.size()) { // Ruleと Unify してみる． for (int i = cPoint; i < rules.size(); i++) { Rule aRule = rename((Rule) rules.elementAt(i)); // 元のバインディングを取っておく． Hashtable orgBinding = new Hashtable(); if ((new Unifier()).unify(thePattern, (String) aRule.getConsequent(), theBinding)) { // さらにbackwardChaining Vector newPatterns = (Vector) aRule.getAntecedents(); if (matchingPatterns(newPatterns, theBinding)) { return wm.size() + i + 1; } else { // 失敗したら元に戻す． theBinding.clear(); for (Enumeration e = orgBinding.keys(); e.hasMoreElements();) { String key = (String) e.nextElement(); String value = (String) orgBinding.get(key); theBinding.put(key, value); ワーキングメモリ中の事実とマッチングする。もし成功すればマッチした事実の次の順番を表す数字を返す。 ワーキングメモリ中の事実とマッチしなければ、今度はルールベース中のルールの後件部とマッチングを行う。 もし成功すれば、マッチしたルールの前件部を新たな仮説としてbackwardChainingを行う。 成功すればマッチしたルールの次の順番を表す番号を返し、不成功の場合は変数束縛情報表をマッチングの前の状態に戻す（バックトラック）

Hypothesis:[?x is an Accord Wagon] Success RULE Rule:CarRule11 [?x10 is a Honda, ?x10 is stylish, ?x10 has several color models, ?x10 has several seats, ?x10 is a wagon]->?x10 is an Accord Wagon <=> ?x is an Accord Wagon Rule:CarRule7 [?x17 is made in Japan, ?x17 has Honda's logo]->?x17 is a Honda <=> ?x10 is a Honda Rule:CarRule1 [?x18 is inexpensive]->?x18 is made in Japan <=> ?x17 is made in Japan Success WM his-car is inexpensive <=> ?x18 is inexpensive Success:?x17 is made in Japan Rule:CarRule8 [?x37 is made in Japan, ?x37 has a VTEC engine]->?x37 is a Honda <=> ?x10 is a Honda Rule:CarRule1 [?x38 is inexpensive]->?x38 is made in Japan <=> ?x37 is made in Japan his-car is inexpensive <=> ?x38 is inexpensive Success:?x37 is made in Japan his-car has a VTEC engine <=> ?x37 has a VTEC engine Success:?x10 is a Honda his-car is stylish <=> ?x10 is stylish Success:?x10 is stylish his-car has several color models <=> ?x10 has several color models Success:?x10 has several color models his-car has several seats <=> ?x10 has several seats Success:?x10 has several seats his-car is a wagon <=> ?x10 is a wagon Yes {?x38=his-car, ?x37=his-car, ?x=his-car, ?x10=his-car} Query: ?x is an Accord Wagon Answer:his-car is an Accord Wagon

Exercises: 1. Input RuleBaseSystem Exercises: 1. Input RuleBaseSystem.java, understand it, run the program, and check the output. 2. (optional) Make some modifications to RuleBaseSystem.java ( data file names: fasterRun.data, rules fasterRunWm.data, the initial known facts) so that the program can run for the following case.

Backward chaining example 1. Pig(y) Slug(z)  Faster(y,z) 2. Slimy(ｚ)  Creep(z)  Slug(z) 3. Pig(Pat) 4. Slimy(Steve) 5. Creep(Steve) 徐行 粘液性の Goal: to prove Faster(Pat, Steve) 1. {y/Pat, z/Steve} Pig(Pat) Slug(z) 3. {} 2. {z/Steve} Slimy(Steve) Creep(Steve) 4. {} 5. {}

Output: Hypothesis:[Pat is Faster than Steve] Success RULE Rule:f1 [?y0 is Pig, ?z0 is Slug]->?y0 is Faster than ?z0 <=> Pat is Faster than Steve Success WM Pat is Pig <=> ?y0 is Pig Success:?y0 is Pig Rule:f2 [?y2 is Slimy, ?z2 is Creep]->?z2 is Slug <=> ?z0 is Slug Steve is Slimy <=> ?y2 is Slimy Success:?y2 is Slimy Steve is Creep <=> ?z2 is Creep Yes {?y2=Steve, ?z2=Steve, ?y0=Pat, ?z0=Steve} Query: Pat is Faster than Steve Answer:Pat is Faster than Steve