1) Systèmes à Base de Connaissances

Un système à Base de Connaissances se distingue des systèmes informatiques classiques par le fait qu'il tente d'exploiter explicitement des "connaissances" sur un problème à résoudre pour en faciliter la résolution. Bien entendu, cette approche est particulièrement importante pour faire face à des problèmes "complexes". Pour illustrer ce que nous entendons par un système complexe, nous vous proposons d'explorer cette notion de complexité au travers d'exemples concrets.

1.1. Complexité des algorithmes et des problèmes

lire n
s <- 0
pour i variant de 1 à n
  s <- s + i
finpour
imprimer s

lire n
imprimer (n * (n + 1) / 2)

La complexité de cet algorithme est O(1).
On ne peut pas faire mieux. C'est donc la complexité de ce problème.
Soit maintenant à écrire un algorithme qui trie un tableau de nombres. Un débutant écrira une boucle de 1 à n-1, au sein de laquelle il comparera deux cases successives, en les permutant si elles ne sont pas dans l'ordre. Et il plongera cette boucle dans une autre de 1 à n. La complexité de son algorithme sera O(n²).
On montre qu'en fait, la complexité du problème est O(n log(n)).
Soit maintenant à écrire un programme qui joue un coup aux échecs. On développe l'arbre de tous les coups possibles (alternativement coup ami et coup ennemi), jusqu'à une profondeur n, puis on calcule une fonction d'évaluation sur chaque feuille, et on remonte alternativement le max et le min des notes obtenues.
La complexité de cet algorithme est O(pⁿ), où p est le nombre moyen de coups légaux dans un état donné.
Pour revenir un peu sur terre, comparons n2 (n au carré) et 2^{n (2 à la puissance n)}, pour n=100, en supposant une micro-seconde par opération :

C'est-à-dire à peu près un million de fois l'age de l'univers ! Inutile de chercher à acheter une machine mille fois ou un million de fois plus rapide ; il faut abandonner l'espoir de résoudre le problème.

1.2. Notion d'heuristique

Et pourtant... Je connais, et vous connaissez aussi, des gens qui résolvent un tel problème en quelques minutes, alors que leur "hardware" est environ 10⁷ fois moins rapide que celui d'un ordinateur. Donc, ils n'utilisent pas l'algorithme que nous avons évoqué au paragraphe précédent. Qu'utilisent-ils? Ce que nous appellerons des heuristiques, ou plus généralement des connaissances. Mettons les en évidence sur un petit problème. Soit à résoudre le problème de cryptarithmétique :

  S E N D
  M O R E
---------
M O N E Y

• Je commence par ré-écrire le problème :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E + O = N + 10r3
  r3 + S + M = O + 10r4
  r4 = M
  S # 0
  M # 0
  

• Je considère l'équation la plus contrainte, r4 = M. Je sais que M ne peut pas être nul, mais ça ne me suffit pas.
• Je démontre un lemme : une retenue ne peut être égale qu'à 0 ou 1.
• Donc M = 1, et r4 = 1.
• Je propage :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E + O = N + 10r3
  r3 + S + M = O + 10*1
  r4 = M
  M = 1
  r4 = 1
  S # 0
  M # 0
  

• Je nettoie :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E + O = N + 10r3
  r3 + S = O + 9
  M = 1
  S # 0
  

• Je prends l'équation la plus contrainte, r3 + S = O + 9. r3 + S vaut au maximum 10, O ne peut pas valoir 1 (valeur déjà prise par M), donc O = 0.
• Je propage et je nettoie :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E = N + 10r3
  r3 + S = 9
  O = 0
  M = 1
  

• De deux choses l'une : r3 = 0 et S = 9, ou r3 = 1 et S = 8. Mais si je commence comme ça, je vais me retrouver avec un processus combinatoire. Donc je refuse cette solution de facilité. Je regarde l'équation r2 + E = N + 10r3.
• r2 + E vaut au plus 10, et N ne peut valoir 0. Donc r3 = 0, et S = 9.
• Je propage et je nettoie :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E = N 
  S = 9
  O = 0
  M = 1
  

• Puisque je cherche une bijection, je ne peux pas avoir E = N, donc r2 =1.

  D + E = Y + 10r1
  r1 + N + R = E + 10
  1 + E = N 
  S = 9
  O = 0
  M = 1
  

• Je considère le couple d'équations 1 + E = N et r1 + N + R = E + 10. Je peux ré-écrire :

  r1 + 1 + E + R = E + 10, ou
  r1 + R = 9
  

  R ne peut pas valoir 9 (valeur de S), donc R = 8 et r1 = 1.
• Je propage et je nettoie :

  D + E = Y + 10
  1 + E = N
  R = 8 
  S = 9
  O = 0
  M = 1
  

• Arrivé là, je ne vois plus d'astuce. Je vais raisonner, non plus sur le problème, mais sur moi : si je m'obstine à ne pas vouloir faire de combinatoire, peut-être ne trouverai-je jamais la solution ; par contre, si j'accepte de faire un petit peu de combinatoire, je trouverai la solution en au plus 4⁶ essais (il me reste 4 inconnues, prenant leurs valeurs dans [2 3 4 5 6 7]).
• Allons y, mais astucieusement. Y + 10 est au moins égal à 12. N et E sont très fortement liés. De deux choses l'une : soit D < E, soit N < D.
• Premier cas : puisque je veux au moins 12, commençons par les plus grandes valeurs possibles : N = 7, E = 6, D = 5 ; cela fait D + E = 11, insuffisant ; inutile d'essayer des valeurs plus petites. La moitié de la combinatoire est déjà éliminée.
• Reste l'hypothèse D = 7, N = 6, E = 5. Ca marche. Mais c'est limite (12), donc inutile d'essayer d'autres cas.

1.3. Développement incrémental

Nous allons donc nous inspirer de ce processus pour développer notre système. Dans un premier temps, l'"ingénieur de la connaissance" (bof) discute avec l'"expert". Il construit un système initial.
L'"expert" soumet un premier problème au système, et analyse la solution.
Le "cogniticien" (beurk) modifie le système : ajout de connaissances, suppression de choses qui avaient été mal comprises.

On recommence.

Même ce qui vient d'être ajouté est remis en question.
Et on continue ainsi jusqu'à ce que, en moyenne, la solution à n'importe quel problème soit jugée acceptable.

Le processus a convergé, on a capturé la connaissance.
Sauf que ce procédé est impraticable : une étude commandée en 1972 par le DoD a montré que, s'il fallait $75 pour écrire une instruction, il en fallait 4000 pour modifier une instruction. Or ici, la quasi totalité du programme résulte de modifications.

EXPLIQUER LA DIFFERENCE DE COÜT ENTRE ECRITURE ET MODIFICATION D'UNE INSTRUCTION (EN MOYENNE); ILLUSTRER PAR UN EXEMPLE D'APPLICATION (correction avec illustration)

1.4. Représentations déclaratives