1.     Représentaion basée sur les règles

 

A rule base is a representation In which

> There is a working memory.

> Lexically, there are rules.

> Structurally, the rules consist of patterns. Some of  these patterns constitute the rule's if patterns; the

others constitute the rule's then pattern.

> Semantically, rules denote constraints that enable  procedures to seek new assertions or to validate a

hypothesis.

With constructors that

> Construct a rule, given an ordered list of if patterns  and a then pattern

With readers that

> Produce a list of a given rule's if patterns

> Produce a list of a given rule's then patterns

.

2.     Les connaissances représentées par les règles

Représentent des formes de connaissances variées :

-Relation : Si batterie morte alors l’auto ne démarrera pas

 

-Recommandation : Si l’auto ne démarre pas alors prendre un taxi

 

-Directive : Si l’auto ne démarre pas & le système d’alimentation en essence est ok

alors vérifier le système électrique

 

-Stratégie : Si l’auto ne démarre pas

alors vérifier le système d’alim. en essence puis le système électrique

 

-Heuristique : Si l’auto ne démarre pas & l’auto est une Ford de 1962

alors vérifier le radiateur

 

Classification en fonction de la nature du type de résolution de problème :

-Interprétation

IF voltage of resistor R1 is greater than 2 Volts

AND the collector voltage of Q1 is <= 1 Volts

THEN the pre-amp section is in the normal section

-Diagnostic

IF the stain of the organism is grampos

AND the morphology of the organism is coccus

AND the growth of the organism is chains

THEN there is evidence that the organism is streptococcus

-Conception

IF current tsak is assigning a power supply

AND the position of the power supply in the cabinet is known

AND there is a space available in the cabinet for the power supply

THEN put the power supply in the cabinet

 

 

3.     RULE-BASED SYSTEMS

Il est construit en utilisant des règles comme la suivante :

Chaque règle contient plusieurs if patterns et un ou plusieurs then. patterns

Architecture

 

Many Rule-Based Systems Are Deduction Systems

Assertion: Une declaration que quelque chose est vraie comme  "Stretch has long legs," or  "Stretch is a giraffe,".

'Facts and assertions are subtly different: A fact is something known to be true;

an assertion is a statement that something is a fact. Thus, assertions can be

false, but facts cannot be false.

 working memory(WM): collection de toutes les assertions.

Etat de système à un instant donné

A working memory is a representation

In which

> Lexically, there are assertions and application-specific  symbols. There are also patterns that contain application- specific symbols mixed with pattern symbols.

> Structurally, the assertions are lists of application-specific  symbols.

> Semantically, the assertions denote facts in some world.  With constructors that

> Add an assertion to working memory  With readers that  Produce a list of the matching assertions in working memory, given a pattern.

 

Dans tous les SBR, chaque if pattern est un pattern qui peut matcher un ou plusieurs assertions dans la collection des assertions (working memory).

 Dans plusieurs SBR le pattern then sepcifie des nouvelles assertions à ajouter dans la mémoire de travail WM. Dans ce cas le SBR est dit système déductif.

 

Dans ce système la convention est:

Le  pattern  if est dit  antécédent et le pattern  then est la conséquence.

 

Dés fois les patterns then spécifient des  actions plutôt que des assertions.

Par  exemple, "Put the item into the bag"— dans ce cas le  SBR est dit réactif.

Exemples

Si <balle, couleur, rouge> alors j’aime la balle.

 

Si j’aime la balle alors j’achète la balle

Peut exécuter des procédures

Si <carré, surface, demandée> alors surface= LONGUEUR*LARGEUR

Si <janvier, précipitations, demandée> alors Ouvrir PRÉCIPITATIONS ;

Précp_Janvier = B7

Si situation d’urgence & <resp., nom, Smith> alors Ouvrir TÉLÉPHONE ;

Trouver NOM Champ_NOM;

TEL = Champ TÉLÉPHONE

Dans les deux   forward chaining (chainage avant) is le processus qui consiste à deplacer des patterns if aux patterns then en utilisant les aptterns if pour identifier les situations appropriées. Pour déduire de Nouvelles assertions ou pour performer une action.

Pendant le chaînage avant, chaque fois qu'un modèle if correspond à une assertion, l'antécédent est satisfait. Chaque fois que tous les modèles if d'une règle sont satisfaites, la règle est déclenchée. Chaque fois qu'une règle déclenchée établit une nouvelle assertion ou effectue une action, elle  est éxecuté(fired).

Remarque

In deduction systems, all triggered rules generally fire. In reaction  systems, however, when more than one rule is triggered at the same time,  usually only one of the possible actions is desired, thus creating a need for  some sort of conflict-resolution procedure to decide which rule should fire.

 

 

Reaction Systems Require Conflict Resolution Strategies

Forward-chaining deduction systems do not need strategies for conflict  resolution because every rule presumably produces reasonable assertions, so  there is no harm in firing all triggered rules. But in reaction systems,  when more than one rule is triggered, you generally want to perform only  one of the possible actions, thus requiring a conflict-resolution strategy

to decide which rule actually fires. So far, you have learned about rule  ordering:

■ Rule ordering. Arrange all rules in one long prioritized list. Use the

triggered rule that has the highest priority. Ignore the others.

Here are other possibilities:

■ Context limiting. Reduce the likelihood of conflict by separating the  rules into groups, only some of which are active at any time.

■ Specificity ordering. Whenever the conditions of one triggering rule are  a superset of the conditions of another triggering rule, use the superset  rule on the ground that it deals with more specific situations.

■ Data ordering. Arrange all possible assertions in one long prioritized

list. Use the triggered rule that has the condition pattern that matches  the highest priority assertion in the list.

■ Size ordering. Use the triggered rule with the toughest requirements,  where toughest means the longest list of conditions.

■ Recency ordering. Use the least recently us

 

4.     Forward reasoning (chainage avant)  et backward reasoning (chainage arrière)

 

 

Forward reasoning

•Step 1: Put the observed data into the working memory.

•Step 2: Pattern matching

–Find a set C of rules that satisfy the observed data. This set C is called the conflict set.

•Step 3: Conflict resolution

–Select a rule r from C based on some criteria, and

–Do the action specified by the selected rule r.

–If the result satisfies a given criterion, stop; otherwise, return to Step 2.

Step 2 and Step 3 together are called Rec

 

R1: IF the ignition key is on

AND the engine won’t start

THEN the starting system (including battery) is faulty

R1 A∧B E

R2: IF E AND the headlights work

THEN the starter is faulty

R2 E∧C G

R3: IF E AND ~C

THEN the battery is dead

R3 E∧~C I

 

R4: IF the voltage test on the ignition switch shows 1 to 6 volts,

THEN the wiring between the ignition and the solenoid is OK R4

D F

R5: IF F

THEN replace the ignition switch

R5 F H

FACTS in the INITIAL DATABASE:

A: The ignition key is on

B: The engine won’t start

C: The headlights work

D: The voltage test on the solenoid shows 1 to 6 volts

R1 A∧B E

R2 E∧C G

R3 E∧~C I

R4 D F

R5 F H

 

 

Stratégie de sélection : fifo

cycle	Conflit set	Selected rule	Working memory
0			A B C D
1	R1 R4	R1	A B C D E
2	R4 R2	R4	A B C D F E
3	R2 R5	R2	A B C D F E G
4	R5	R5	A B C D F E G H

 

Main problems in forward reasoning

Computational cost for pattern matching is high –All data and all conditions of all rules must be compared with each other in each cycle. •Solution –Use Rete algorithm or its improved version.   •Rule selection effects the reasoning efficiency –Random selection or simple selection (e.g. depth first) may increase the redundancy of the reasoning process. •Solution –Use heuristics(e.g. LEX) LEX (Lexicographic sort)   1.Delete the “used” rules from the conflict set; 2.Assign higher priorities to rules that matches the newer data; 3.Assign higher priorities to rules with more detailed conditions; 4.Assign equal priorities otherwise.

 

Backward reasoning

• Step 1 Find a set A of rules from the knowledge base For any rule in A, its action part derives the given hypothesis h

• Step 2 If A is empty, and return “false”

• Step 3 Take out a rule from A, check its condition part, and find a set B of conditions that do not match the observed data If B is empty, return “true”

• Step 4 For each condition in B, verify its truth recursively

• Step 5 If all returned values in Step 4 are “true  return “ true otherwise, return to Step 2

 

 

 

Initial DB

IDB= {A, B, C, D}

GOAL

Use backward chaining to infer/reject

H∧I

First: Consider H. H is not in the DB. The only rule that matches H (action) is

R5: F H

Look at F; It is not in the IDB, so it is a SUBGOAL. Applicable:

R4 D F, and D is in the IDB.

So, F is SUPPORTED and hence H is supported.

Next: Consider I. I is not in the DB, applicable rule is

R3 E∧~C I

C is in the DB, hence R3 cannot be used. R3 is the ONLY rule, hence I is not

supported and GOAL H∧I is rejected.