\chapter{Systèmes à base de connaissances}

Les systèmes  à bases  de connaissances (dit  aussi à base  de règles)
permettent à partir  d'un ensemble de règles et de  faits de faire un
diagnostique. On trouve deux  applications majeures les Business Rules
et  les  Systèmes  experts.  Les  deux  domaines  utilisent  les  mêmes
principes. On se focalisera donc sur les Système experts.

\section{Représentation des connaissances}

L'un des problèmes majeurs de  tels systèmes est la représentation des
connaissances. Pour  cela il existe plusieurs  langages offrant chacun
leurs avantages  et inconvenients.  Le choix d'une  bonne représentation
est  fondamentale et  détermine  toute la  suite  du développement  du
système.

\begin{description}
\item [Logique  des prédicats]:  La logique des  prédicats est  un des
moyens les plus courants et les plus comodes de représenter des faits ou des
règles,  dans   la  mesure  où  le  domaine   étudié  est  suffisament
élémentaire. Il faut garder à l'esprit qu'il existe un grand nombre de
façon de représenter  une même phrase. Le programmeur  doit donc faire
le bon choix pour une  efficacité optimale du système. Un des éléments
qui  peut  expliquer  le  succès  de  la  logique  des  prédicats  est
l'existance  du principe  de résolution  ainsi que  des  techniques de
résolution automatique avec les clauses de Horn.\\ 
\textbf{Ex:}$\forall x, Avion(x) \rightarrow Vole(x)$

\item [Logique modale]: Les  logiques modales permettent d'enrichir le
langage de la  logique classique du premier ordre  en introduisant des
notions de possibilité  / nécessité ou de croyance.  La logique modale
permet   de  rafiner   considérabement  le   langage  de   la  logique
classique. Elle  peut être  utilisée dès que  le problème  inclut des
notions de croyance  de nécessité ou de possibilité.  Il est également
possible de faire de la résolution automatique en logique modale, bien
que  ce  soit  autrement  plus difficile  qu'en  logique  classique.\\
\textbf{Ex:}Tout ce que sait Paul, Eric le sait:
$$\forall x, \Box (Paul)x \rightarrow  \Box (Eric)x$$

\item  [Logique temporrelle]:  La logique  temporelle s'appuie  sur la
notion  d'intervalle.  Elle  définit  un certain  nombres  d'opérateurs
(pendant,   avant,   acheval,   joint,   égal)  et   un   système   de
quarante-quatre  axiomes. Viens s'ajouter  une notion  d'événements qui
graces  aux opérateurs  peuvent être  localisés dans  le  temps. Cette
logique semble connaitre un certain succès à l'heure actuelle. Mais le
nombre de ces axiomes rend l'interprétation sémantique difficile.

\item [Logique  multivaluée et logique floue]:  Ces logiques permettent
de formaliser des  raisonnements du type: ``il est  très vrai que...''
ou  ``il est  probablement vrai  que...''. Ces  logiques  ressensent  un
ensemble de  caractéristiques qui les rendent très  différentes de la
logique classique mais sont  d'un grand intêret comme outil opératoire:
elles semblent, en effet, rencontrer d'intéressantes applications dans
le domaine des systèmes  experts. Il existe certaines formalisations
qui permettent de réaliser des inférences de façon automatique.

\item  [Logique  des  défauts]:   La  logique  des  défauts  tente  de
modéliser  un type  de raisonnement,  que nous  pratiquons  tous, qui
consiste  à réaliser  des inférences  en fonction  de règles  que nous
supposons générales (alors qu'elles admettent parfois des exceptions).

\item [Réseaux sémantiques]:  Ils constituent, très grossièrement, une
façon  de représenter  graphiquement les  relations de  la  logique du
premier ordre. Ces  réseaux permettent de répondre à  des questions du
type  ``quel est  le  lien entre  ...  ?''. Ils  ont  été utilisé,  en
particulier, pour la compréhension des langues naturelles. Ils peuvent
également  servir de  représentation intermédiaire  entre connaissance
non formalisée et langage de programmation.

\end{description}

\section{Système experts à base de règles}

  Un système  expert sert à  garder et emmagasiner la  connaissance, le
savoir-faire  et   la  mémoire   d'entreprise.  Il   permet  d'avoir
l'expérience d'un grand nombre  d'experts (et donc différents points de
vue), même de différents domaines pour en faire une synthèse.

  L'extraction des  connaissances se fait  avec des experts  (et donc
les dirigeants)  et recquiert de la  méthodologie. Il ne  faut pas non
plus négliger la représentation choisie comme vu précédement.

  \subsection{Principe}

Prenons  l'exemple  d'un  système  expert  comme  Mycin  (domaine  des
médecines interne). Le système expert raisonne alors comme un médecin.

\begin{enumerate}
  \item on regarde les signes cliniques;
  \item  le médecin  pense à  des  hypothèses (plus  l'expert est  bon
  meilleures sont les hypothèses);
  \item  on  informe  (ou  affirme)  les hypothèses  avec  des  examens
  complémentaires;
  \item la bonne condition depend du  contexte (on ne traite pas de la
  même façon une personne dans l'urgence que dans le calme).
\end{enumerate}
    
  \subsection{Architecture}

Un système expert s'articule autour de trois éléments principaux:
\begin{description}
\item [La base de faits]:  elle contient l'ensemble des faits relatifs
au  problème  considéré.  C'est  là  que  sont  stockées  les  données
symboliques et numériques. Dans l'exemple  du médecin c'est là où l'on
stocke les symptômes.
\item [La base de règles]: elle contient l'ensemble des règles de
production et des connaissances heuristiques déterminant la résolution
du problème. Ce sont les connaissances du médecin grâce auquelles il
va pouvoir formuler des hypothèses. Elles sont de la forme si
\textit{antécédent} alors \textit{conséquent}.
    \begin{description}
      \item [Antécédent]: en général conjonction de plusieurs
      conditions élémentaires appelées PREMISSES, mais aussi avec
      négation et disjonction.
      \item [Conséquents]: actions à  envisager si la partie condition
      est satisfaite. Ces actions indiquent le ou les faits nouveaux à
      déduire - sous forme de conjonction.
    \end{description}
\item [Le moteur d'inférance]: il réalise le fonctionnement créatif du
système en sélectionnant les règles et faits pour générer de nouvelles
règles et de nouveaux faits. C'est le travail du cerveau du médecin.
\end{description}

On inclut parfois un supplémentaire dans les systèmes experts:
\begin{description}
\item [Les  méta-règles]: il s'agit  des règles destinées à  guider le
moteur  d'inférence   quant  à  la  stratégie  de   résolution  ou  la
maintenance des bases de règles  et de faits. Par exemple pour traiter
une personne dans l'urgence ou dans le calme.
\end{description}

  La première  étape pour  la réalisation d'un  système expert  est le
choix de la technique  de représentation des connaissances (aussi bien
faits  que  règles)  que   nous  allons  utiliser.  Les  techniques  de
représentation ont été décrites précédement. La seconde étape consiste
à choisir un mécanisme d'inférence adapté au problème.

  \section{Moteur d'inférence}

Le moteur d'nférence est la partie créative du système. A partir de
règles et de faits, il génère de nouveaux faits afin de réaliser la
résolution effective du problème.

  La majorité des moteurs d'inférence utilisent un cycle à trois temps
(MATCH, CONFLICT RESOLUTION, ACT):

\begin{description}
  \item  [MATCH (Selection)  :]  l'étape MATCH  consiste à  rechercher
  l'ensemble  des  règles d'inférence  qui  peuvent  s'appliquer à  un
  instant  donné  à  la  base  de   faits  et  à  noter  les  faits  à
  utiliser. Certaines fois cette  partie est décomposée en une deuxième
  étape qui  est le filtrage afin  de réduire le nombre  de règles sur
  lesquels on travaille ce qui optimise la résolution.

  \item [CONFLIT  RESOLUTION (Résolution de  conflit) :] le  moteur va
  choisir parmis  toutes les  règles qu'il peut  utiliser ,  celle (ou
  celles)  qu'il  va  exécuter.  Ce   choix  est  fait  à  l'aide  des
  méta-règles.

  \item [ACT  (Déclenchement) :] après avoir séléctionné  la règle, le
  moteur  d'inférence   l'éxecute  et  éxecute   toutes  les  actions
  associées (remise à jour de la base...).
\end{description}

Les  caractéristiques principales d'un  moteur d'inférance  sont liées
aux techniques  de résolution qu'il implémente. Par  exemple un moteur
d'inférance  peut  fonctionner   par  \textit{chaînage  avant}  ou  en
\textit{chaînage  arrière}.  Un  moteur  d'inférence  fonctionnant  en
chaînage avant tente,  à partir de la base de faits  et des règles, de
générer une  réponse: une  démonstration classique (déductive)  est un
exemple de fonctionnement en chaînage avant.

\begin{algorithm}
\caption{Chaînage avant}
\label{alg1a}
\begin{algorithmic}
  \Function{chainage-avant}{}
  \State Phase de séléction
  \State Phase de filtrage
  \While{l'ensemble des règles de filtrage n'est pas vide 
    \&\& problème non résolut}
     \State Phase de résolution de conflit
     \State Modifier enventuellement l'ensemble des règles applicables
  \EndWhile
  \EndFunction
\end{algorithmic}
\end{algorithm}

Un moteur d'inférence à chaînage arrière tente d'invalider la question
en montrant l'inconsistance de la nouvelle base de faits comprenant la
négation de la  question. Le mécanisme de résolution  avec des clauses
de Horn est un exemple typique de fonctionnement en chaînage arrière.

\begin{algorithm}
\caption{Chaînage arrière}
\label{alg1a}
\begin{algorithmic}
  \Function{chainage-arrière}{}
  \State Phase de séléction
  \State Phase de filtrage
  \If{l'ensemble des règles est vide}
    \State Questionner l'utilisateur
  \Else
  \While{but non résolut \&\& il reste des règles sélectionnées}
     \State Phase de résolution de conflit
     \State Ajouter les sous-buts correspondant à la partie gauche de la 
     règle élue
     \If{un but n'est pas résolut}
       \State résoudre
     \EndIf
  \EndWhile
  \EndIf
  \EndFunction
\end{algorithmic}
\end{algorithm}

Il est  également possible  d'utiliser le \textit{chaînage  mixte} qui
tente de concilier les  deux méthodes. L'utilisation du chaînage mixte
demande  la  mise en  place  d'heuristiques  particulières capable  de
décider face à une situation donnée quel est le type de stratégie plus
adapté pour poursuivre la résolution.
 
De telles  méthodes se modelisent grâce  à des graphes  ET-OU. Dans ce
type de  graphes, il part zéro  ou plusieurs arcs de  chaque noeud, et
certains arcs sont reliés entre eux. Ce qui signifie que pour résoudre
le noeud courant il faut résoudre tous les sous noeuds auxquels il est
racordé.

Mais ces techniques de résolution sont peu efficaces car leur
compléxité est asymptotique selon l'augmentation des règles de
productions. On utilise alors des algorithmes de filtrage et de
pattern matching qui limite le nombre de règles sur lesquels on
travaille.		   

  \section{Un Algorithme de pattern matching: RETE}
  
Cet algorithme par  du principe que les règles  distinctes ont souvent
des conditions communes. On va donc compiler l'ensemble des conditions
distinctes dans  un réseau unique.   Chaque condition est  compilée dans
une suite de noeuds simples. Chacun de ces noeuds correspond à un test
sur une caractéristique de l'élément instanciant cette condition.

On considère alors deux types d'éléments:
\begin{description}
  \item [la longueur 'l' d'une condition]: Pour calculer la longueur
au rang $n$ on va jusqu'au nième élément (une parenthèse est un
élément), puis si on est sur une parenthèse on enlève le couple de
prenthèses, et on compte les éléments séparés (un couple de
parenthèses groupe des éléments).  Par exemple considerons la
condition $( A ( B ( C ) ) )$. On a alors la longueur au rang 0 :
$L(0) = 2$ et au rang 2 : $L(4) = 1$
  \item  [constantes]:   présence  d'une  constante.   Dans  l'exemple
  précédent: $K(2.1) = B$
\end{description}

Ensuite pour  construire / compiler  les règles on  utilise l'algorithme
suivant:

\begin{algorithm}
\caption{RETE algorithme}
\label{alg1c}
\begin{algorithmic}
  \Function{build-rete-graph}{$R$}
  \State $\triangleright R$: ensemble des  règles de production.
  \State Créer un noeud initial (d'instanciation)
  \State Récuperer dans $C$ l'ensemble des conditions distinctes.
  \ForAll{$ condition \in C$}
    \ForAll{$symbole \in condition$}
    \If{$symbole = '('$}
      \State créer un noeud de longueur
    \EndIf
    \If{$symbole = constante$}
      \State créer un noeud constant
    \EndIf
    \EndFor
    \State créer un noeud signalant la satisfaction de la contrainte
  \EndFor
  \State A partir de $R$ construire tous les noeuds de jonctions entre 
  les contraintes satisfaisables en ajoutant les contraintes sur les variables.
  \State Ajouter tout les noeuds terminaux indiquant la satisfaction d'une 
  règle. 
  \EndFunction
\end{algorithmic}
\end{algorithm}

Par la suite il ne reste plus qu'à parcourir le graphe pour déterminer
les règles qui sont satifaites par les faits.

Pour mieux visualiser l'algorithme voici un exemple.\\

Considérons les règles suivantes:
\begin{equation*}\label{rules}
\begin{split}
R1: (want (&  monkey \thickspace on \thickspace !o))  
  (!o \thickspace near \thickspace !x) \\
             &  \rightarrow (want (monkey \thickspace near \thickspace !x)) \\
R2:  (want (& monkey \thickspace on \thickspace !o))
 (!o \thickspace near \thickspace !x)(monkey \thickspace near \thickspace !x)\\
             & \rightarrow (want (monkey \thickspace near \thickspace !x))
\end{split}
\end{equation*}

Ce qui nous donne comme conditions dinstinctes:
\begin{itemize}
  \item \textbf{C1:} $(want (monkey \thickspace on \thickspace !o))$
  \item \textbf{C2:} $(!o \thickspace near \thickspace !x)$
  \item \textbf{C3:} $(monkey \thickspace near \thickspace !x)$\\
\end{itemize}

\begin{figure}[h]
  \begin{center}
    %BEGIN IMAGE
    \begin{tabular}{ccccc} 
                         && \node{n}{}           &			\\[3ex]
\node{a1}{$L(0) = 2$}    &&                      &\node{b1}{$L(0) = 3$} 	\\[3ex]
\node{a2}{$K_1 = want$}  && \node{b2}{$K_2 = near$}& & \node{c1}{$K_1 = monkey$}\\[3ex]
\node{a3}{$L(2) = 3$}    && \node{b3}{$C2 : OK$} &   & \node{c2}{$K_2 = near$}\\[3ex]
\node{a4}{$K_1 = monkey$}&&                      &   & \node{c3}{$C3 : OK$}	\\[3ex]
\node{a5}{$K_2 = on$}    &&                      &   & \node{c4}{$C1C2C3 / !x$}	\\[3ex]
\node{a6}{$C1 : OK$}     &&                      &   & \node{c5}{$R2 : OK$}	\\[3ex]
                         &\node{a7}{$C1C2 / !o$}  \\[3ex]
                         &\node{a8}{$R1 : OK$}    \\[3ex]
    \end{tabular}
    \nodeconnect{n}{a1}
    \nodeconnect{n}{b1}
    \nodeconnect{b1}{c1}
    \nodeconnect{a1}{a2}
    \nodeconnect{a2}{a3}
    \nodeconnect{a3}{a4}
    \nodeconnect{a4}{a5}
    \nodeconnect{a5}{a6}
    \nodeconnect{a6}{a7}
    \nodeconnect{a7}{a8}
    \nodeconnect{b1}{b2}
    \nodeconnect{b2}{b3}
    \nodeconnect{c1}{c2}
    \nodeconnect{c2}{c3}
    \nodeconnect{c3}{c4}
    \nodeconnect{c4}{c5}
    \nodeconnect{b3}{a7}
    \nodecurve[r]{a8}[l]{c4}{}
   %END IMAGE   
  %HEVEA\imageflush
  \end{center}
  \caption{exemple de Graphe résultat de l'algorithme de RETE}
  \label{graphe}
\end{figure}

%  \section{Système de maintient de connaissances}