Backward Chaining

L11. An Example of Backward
Chaining Program in Java
An Rule Base System in Java
RuleBaseSystem.java
CarShop.data
1
Reasoning with Rules
• Knowledge represented as if-then rules
• Backward chain
– To prove a conclusion  from the known facts and knowledge (rules)
2
Major Elements
• A rule base
– The set of if-then rules
• A fact base
– Known facts
• Inference engine
– Containing the reasoning logic used to process the rules and data
3
Backward Chaining
熱がある
食欲が無い
ワーキングメモリの中
（事前知識）
IF
食欲が無い
THEN
食事をしていない
IF
食事をしていない
THEN
栄養が足りない
（患者から得られた事実情報）
熱がある
IF
栄養が足りない
THEN
風邪を引く
風邪を引いている
4
A Rule-base System Architecture
class RuleBaseSystem{}
Class FileManager
Rule Base
Fact base
In a file
class RuleBase{}
class Rule{}
Interaction with
Inference Engine
class Unifier{}
Matching
Fire a Rule
Select a Rule
Acting
5
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
6
rule
if
then
"CarRule1"
"?x is inexpensive"
"?x is made in Japan"
rule
if
then
Rule
if
then
"CarRule2"
"?x is small"
"?x is made in Japan"
rule
If
then
"CarRule3"
"?x is expensive"
"?x is a foreign car"
rule
if
"CarRule4"
"?x is big"
"?x needs a lot of gas"
"?x is a foreign car"
then
Rule
"CarRule5"
If
"?x is made in Japan"
"?x has Toyota's logo"
then
"?x is a Toyota"
rule
if
Ｔhen
"CarRule6"
"?x is made in Japan"
"?x is a popular car"
"?x is a Toyota"
rule
if
then
rule
if
then
rule
if
then
rule
if
then
"CarRule7"
"?x is made in Japan"
"?x has Honda's logo"
"?x is a Honda"
"CarRule8"
"?x is made in Japan"
"?x has a VTEC engine"
"?x is a Honda"
"CarRule9"
"?x is a Toyota"
"?x has several seats"
"?x is a wagon"
"?x is a Carolla Wagon"
"CarRule10"
"?x is a Toyota"
"?x has several seats"
"?x is a hybrid car"
"?x is a Prius"
"CarRule11"
"?x is a Honda"
"?x is stylish"
"?x has several color models"
"?x has several seats"
"?x is a wagon"
"?x is an Accord Wagon"
rule
if
then
"CarRule12"
"?x is a Honda"
"?x has an aluminium body"
"?x has only 2 seats"
"?x is a NSX"
rule
if
"CarRule13"
"?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
if
"CarRule14"
"?x is a foreign car"
"?x is a sports car"
"?x is red"
"?x has a big engine"
then "?x is a Ferrari F50"
rule
if
"CarRule15"
"?x is a foreign car"
"?x is a good face"
then "?x is a Jaguar XJ8"
7
Backward Chaining
ここでは
?x is an Accord Wagon?
(アコードワゴンである?ｘは何です
か？)
という仮説を証明したいと思います。
（これを仮説というかは微妙ですが・・・）
8
Backward Chaining
9
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");
}
}
10
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{
ングを行う。
…
}
仮説の数が二つ以
}
・・・
}
上の場合の処理は
自分で見て理解し
てみて下さい。
11
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を行う。
成功すればマッチしたルールの
次の順番を表す番号を返し、不
成功の場合は変数束縛情報表を
マッチングの前の状態に戻す（バ 12
ックトラック）
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
Success RULE
Rule:CarRule7 [?x17 is made in Japan, ?x17 has Honda's logo]->?x17 is a Honda <=> ?x10 is a Honda
Success RULE
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
Success RULE
Rule:CarRule8 [?x37 is made in Japan, ?x37 has a VTEC engine]->?x37 is a Honda <=> ?x10 is a Honda
Success RULE
Rule:CarRule1 [?x38 is inexpensive]->?x38 is made in Japan <=> ?x37 is made in Japan
Success WM
his-car is inexpensive <=> ?x38 is inexpensive
Success:?x37 is made in Japan
Success WM
his-car has a VTEC engine <=> ?x37 has a VTEC engine
Success:?x10 is a Honda
Success WM
his-car is stylish <=> ?x10 is stylish
Success:?x10 is stylish
Success WM
his-car has several color models <=> ?x10 has several color models
Success:?x10 has several color models
Success WM
his-car has several seats <=> ?x10 has several seats
Success:?x10 has several seats
Success WM
his-car is a wagon <=> ?x10 is a wagon
Yes
{?x38=his-car, ?x37=his-car, ?x=his-car, ?x10=his-car}
13
Query: ?x is an Accord Wagon
Answer:his-car is an Accord Wagon
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.
14
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)
4.
{}
Creep(Steve)
5.
{}
15
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
Success RULE
Rule:f2 [?y2 is Slimy, ?z2 is Creep]->?z2 is Slug <=> ?z0 is Slug
Success WM
Steve is Slimy <=> ?y2 is Slimy
Success:?y2 is Slimy
Success WM
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
16

Download Report