//img.uscri.be/pth/bd4d372d8be9e152bd9b0e2618ccfdf584b284fc
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

La représentation des connaissances (coll. Informatique)

De
324 pages
Ce livre donne à toute personne intéressée par les sciences cognitives une idée des principes généraux qui régissent la représentation des connaissances. L'ouvrage contient des exercices de difficulté très variable avec tous les corrigés en fin de volume.
1. Introduction 2. Codage des informations Quelques éléments sur le codage - Recherche d'une information - Connaissance et information 3. Notion de représentation Généralités - Représentation et modèle - Langages de représentation - Représentation de procédures 4. Représentation dans un modèle La logique des propositions - La logique du premier ordre - Quelques éléments sur les logiques d'ordre supérieur - La logique modale - La logique multi-valuée 5. Les réseaux sémantiques Généralités sur les réseaux - Graphes conceptuels - Inférence par propagation - Logiques de description - Discussion 6. Connaissances menant à des conclusions révisables Motivations - Les logiques non-monotones - Non-monotonie et modèles préférés - Raffinement progressif de la conclusion - Raisonnement sur un monde évolutif - Ontologie et non-monotonie 7. Conclusion Exercices et corrections des exercices Bibliographie - Index
Voir plus Voir moins

collection informatique
La représentation
des
connaissances
Daniel Kayser
HERME S La représentation des connaissances © Editions HERMES , Paris, 1997
Edition s HERMES
14, rue Lantiez
75017 Paris
ISB N 2-86601-647-5
Catalogage Electre-Bibliographie
Kayser, Daniel
La représentation des connaissances. - Paris : Hermès, 1997.
ISBN 2-86601-647-5
RAMEAU : représentation des connaissances
intelligence artificielle
DEWEY : 006.1 : Méthodes informatique spéciales.
Intelligence artificielle
Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une
part, que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4).
Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc
une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété
intellectuelle. La représentation
des
connaissances
Daniel Kayser
HERME S EXTRAIT DU CATALOGUE GÉNÉRAL
Acquisition et application des connaissances juridiques,
Vincente FORTIER, Jean-Louis BILON, 1997 .
Connaissances et savoir-faire en entreprise, intégration et capitalisation,
coordonnateur Jean-Marc FOUET, 1997.
Eléments de logique floue, Louis GACÔGNE, 1997 .
L'apprentissage de la complexité, Gérard CLERGUE, 1997 .
Le raisonnement qualitatif, pour les sciences de l'ingénieur,
Louise TRAVÉ-MASSUYÈS, Philippe DAGUE, François GUERRIN, 1997 .
Les agents intelligents, essai sur la rationnalité des calculs,
Jean SALLANTIN, 1997 .
Les systèmes transactionnels, concepts, normes et produits,
Jérôme BESANCENOT, Michèle CART, Jean FERRIE, Rachid GUERRAOUI,
Philippe PUCHERAL, Bruno TRAVERSON, 1997 .
Sciences cognitives, diversité des approches, Mirta B.GORDON, Hélène
PAUGAM-MOISY, 1997 .
Eléments de logique formelle, Gérard CHAZAL, 1996 .
Langage et cognition, l'approche connexionniste, Bernard LAKS, 1996 .
La polysémie, construction dynamique du sens,d VICTORRI,
Catherine FUCHS, 1996 .
Les systèmes de connaissances, Jean-Louis ERMINE, 1996 .
Serveur we b : http://www.editions-hermes.fr à la mémoire de mon père,
Femand KAYSER (1905-1966)
Professeur à la Faculté de Pharmacie de Nancy,
à ma mère,
Hélène KAYSER
qui m'ont transmis le désir de connaître Table des matières
Chapitre 1. Introduction 1
1.1. Au commencement était l'inférence 2
1.2. Ceci n'est pas de l'informatique 5
1.3. Inference et raisonnement 6
1.4.e sans représentation
Chapitre 2. Codage des informations 9
2.1. Quelques éléments sur le codage
2.1.1. Codage et représentation
2.1.2.e des nombres 11
2.1.3. Codage des graphiques et des images6
2.2. Recherche d'une information 20
2.2.1. Recherche séquentielle
2.2.2.e dichotomique
2.2.3. Recherche directe3
2.2.4. Adressage dispersé4
2.2.5. Discussion6
2.3. Connaissance et information 28
2.3.1. Connaissance et action
2.3.2. Différentes natures de connaissances 31
Chapitre 3. Notion de représentation5
3.1. Généralités 3
3.2. Représentation et modèle7
3.3. Langage de représentation 40
3.4.n de procédures4
3.4.1. Le minimum
3.4.2. Les procédures comme objets9
3.4.3. Indécidabilité 51 VIII La représentation des connaissances
Chapitre 4. Représentation dans un modèle 55
4.1. La logique des propositions 56
4.1.1. Langage
4.1.2. Système de déduction7
4.1.3. Règles de valuation 60
4.1.4. Connaissances propositionnelles
4.1.5. Décidabilité9
4.1.6. L'algorithme de Davis & Putnam 7
4.1.7. Résolution sur les clauses de Horn2
4.2. La logique du premier ordre3
4.2.1. Langage 7
4.2.2. Système de déduction5
4.2.3. Règles de valuation7
4.2.4. Connaissances du premier ordre 81
4.2.5. Décidabilité 86
4.3. Quelques éléments sur les logiques d'ordre supérieur
4.3.1. Motivation
4.3.2. Langage
4.3.3. Propriétés8
4.3.4. Connaissances d'ordre > 1
4.3.5. "Faux second ordre"9
4.4. La logique modale 91
4.4.1. Motivations
4.4.2. Langage3
4.4.3. Systèmes de déduction
4.4.4. Règles de valuation5
4.4.5. Logique modale du premier ordre 10
4.4.6. Connaissances modales4
4.5. La logique multi-valuée 11
4.5.1. Modalités et valeurs de vérité
4.5.2. Logiques tri-valuées
4.5.3. Généralisation à n valeurs6
4.5.4. Logique des possibilités 120
4.5.5. Renforcement et affaiblissement2
4.5.6. Connaissances multi-valuées
Chapitre 5. Les réseaux sémantiques9
5.1. Généralités sur les réseaux
5.1.1. Motivations
5.1.2. Définition 131
5.1.3. Début d'interprétation3
5.1.4. Un exemple : les réseaux partitionnés 135
5.2. Graphes conceptuels 140
5.2.1. Brève présentation formelleTable des matières IX
5.2.2. Intreprétation logique 143
5.3. Inference par propagation4
5.3.1. Propagation de marqueurs6
5.3.2.n de signaux périodiques 150
5.3.3. Réseaux connexionnistes
5.4. Logiques de description 155
5.4.1. Présentation
5.4.2. FL
5.4.3. PLi et PL28
5.4.4. Une autre notion de modèle 160
5.5. Discussion 163
Chapitre 6. Connaissances menant à des conclusions révisables. 167
6.1. Motivations7
6.2. Les logiques non-monotones 17
6.2.1. La logique du raisonnement par défaut
6.2.2. Quelques variantes du raisonnement par défaut 184
6.2.3. Statut de la notion d'exception 188
6.2.4. THEORIST 191
6.2.5. La logique auto-épistémique5
6.3. Non-monotonie et modèles préférés
6.3.1. Modèles des systèmes déductifs non monotones 19
6.3.2. La circonscription9
6.3.3. Déductibilité non monotone 203
6.4. Raffinement progressif de la conclusion 210
6.5. Raisonnement sur un monde évolutif
6.5.1. Révision des connaissances4
6.5.2. Représentation des actions7
6.6. Ontologie et non-monotonie 22
6.6.1. Les objets
6.6.2. Qu'est-ce qu'un livre ?5
6.6.3. Raisonner à profondeur variable8
Chapitre 7. Conclusion 233
Correction des exercices9
Bibliographie 281
Index 297 Chapitre 1
Introduction
Ce livre vise deux objectifs : d'un côté, il s'efforce de donner à toute personne
intéressée par les sciences cognitives une idée des principes généraux qui régissent
un domaine d'études d'une grande importance scientifique et technique ; l'autre
objectif, plus didactique, consiste à familiariser des étudiants, des chercheurs, et des
ingénieurs avec un ensemble de théories, dont la maîtrise apparaît nécessaire à qui
veut se lancer dans un travail effectif de représentation de connaissances.
Ces deux objectifs ne sont pas disjoints. Il se pourrait qu'un lecteur,
initialement désireux de parfaire sa culture générale, se prenne au jeu et investisse
dans son parcours plus d'efforts qu'il ne l'avait envisagé ; inversement, un spécialiste
sera probablement déçu de ne pas trouver les développements qu'il escomptait sur
un sujet qui l'intéresse, mais appréciera peut-être la perspective dans lequel il est
abordé. La présence d'exercices, de difficulté très variable (tous les corrigés sont
donnés en fin de volume !), et d'encadrés donnant une formulation concise aux
thèses défendues ici, cherche à satisfaire les deux types de lecture.
Après une période de bouillonnement un peu désordonné, et par une réaction
que certains ont pu juger excessive, le champ d'études couvert par l'appellation
"représentation des connaissances" se caractérise actuellement par d'importants
travaux formels. Pour atteindre les objectifs que nous nous fixons, nous ne pouvons
donc pas faire l'économie d'une présentation rigoureuse des théories sur lesquelles
ils s'appuient.
Ces théories ont souvent été étudiées en elles-mêmes, et nous aurions pu nous
contenter de renvoyer le lecteur à des ouvrages classiques. Cependant nous
développerons à loisir l'idée que la représentation des connaissances les aborde sous
un angle rendant leur réexamen nécessaire, ce qui justifie d'en donner ici une 2 La représentation des connaissances
présentation autonome. Avantage supplémentaire : cet ouvrage se veut
"autosuffisant", au sens où les références bibliographiques mentionnées apportent
des informations complémentaires, mais ne constituent pas des prérequis.
Nous avons toujours cherché à éviter l'écueil de la théorie pour elle-même. Nous
croyons donc n'avoir infligé au lecteur que les développements techniques qu'il nous
paraissait impossible de lui épargner sans le priver du même coup d'une idée
importante. Nous espérons que, nous faisant crédit sur ce point, il consentira à les
lire, et surtout qu'il trouvera alors quelque récompense à ses efforts !
1.1. Au commencement était l'inférence
La réflexion scientifique est intéressante en ce qu'elle modifie
notre vision de notre environnement et de nous-mêmes.
L'aventure scientifique que l'on connaît aujourd'hui sous l'appellation de
"sciences cognitives" a pour intérêt essentiel de mieux nous faire comprendre ce que
nous sommes, sous le rapport de ce que nous nous plaisons à considérer comme
nos facultés de "haut niveau" : connaître, comprendre, apprendre, communiquer,
résoudre. Une de ses branches, communément dénommée intelligence artificielle
(IA) a pour objectif d'obtenir de la machine un comportement intelligent, ou, si l'on
préfère, qui serait jugé intelligent si c'était un être humain qui le produisait. Ses
succès comme ses échecs nous amènent à mieux saisir la nature de ce que nous
appelons intelligence, que nous décidions de limiter l'emploi de ce terme à
l'intelligence humaine ou que nous acceptions de l'employer au sujet d'une faculté
abstraite, dont l'intelligence humaine est à ce jour le meilleur exemple.
Le résultat peut-être le plus intéressant de l'IA est de nous montrer qu'un certain
archétype de l'intelligence : résoudre numériquement une équation mathématique
difficile ou un problème de logique particulièrement opaque, suivre une stratégie
gagnante dans certains jeux, trouver une décision qui optimise un grand nombre de
facteurs, s'avère réductible à l'application répétitive et sans erreur d'un petit nombre
d'opérations simples. Or on ne considère généralement pas comme intelligent celui
qui sait répéter un grand nombre de fois sans se tromper une opération simple ; on
aurait même plutôt tendance à dire le contraire ! En revanche, d'autres tâches que
l'on ne considère généralement pas comme requérant de l'intelligence : marcher au
milieu d'obstacles, reconnaître des objets, identifier les mots d'une phrase
prononcée, tenir une conversation banale, sont beaucoup plus difficiles à réduire à
une itération d'opérations élémentaires. Introduction 3
1D'après certains auteurs, il y aurait même là une impossibilité . Du fait que
l'espèce humaine semble dotée de moyens innés ou rapidement acquis pour effectuer
ces tâches, on ne s'est jamais vraiment soucié de les enseigner, tandis que les tâches
qui nous semblent plus difficiles, celles-là mêmes dont nous disons qu'elles
requièrent de l'intelligence, ont été disséquées pour pouvoir être résolues. C'est
pourquoi, pour effectuer les opérations que nous trouvons complexes, l'IA a pu
disposer dès le départ d'une méthode, tandis qu'elle doit découvrir par elle-même les
éléments à combiner, s'ils existent, pour accomplir ce que nous trouvons simple.
Prenons pour exemple une action aussi banale que de passer d'une pièce à une
autre dans une maison ; elle nécessite au moins :
- une faculté d'analyse et d'interprétation permanentes des données qui nous
parviennent de notre environnement,
- un jugement sur l'importance de tel ou tel événement susceptible d'interagir
avec notre déplacement,
- une aptitude à orienter nos organes de perception vers les sources d'information
qui, à chaque instant, nous paraissent les plus dignes d'attention,
- des capacités pour déterminer un plan d'action rudimentaire, et pour le modifier
dynamiquement,
- la possibilité d'enchevêtrer entre elles ces différentes activités sans les perturber,
et de les enchevêtrer avec d'autres activités au moins aussi complexes (discuter avec
quelqu'un, réfléchir à toute autre chose...).
Le point commun aux processus que nous avons énumérés : interpréter, juger,
décider, planifier, trier, évaluer, et à beaucoup d'autres que nous pratiquons à chaque
instant, c'est {'inference, prise en un sens très large.
L'inférence est l'élément de base de toute description de la
cognition.
Entendons-nous : il ne s'agit pas de prétendre qu'il existe un mécanisme unique,
l'inférence, dont l'élucidation serait l'alpha et l'oméga des sciences cognitives. Chez
les êtres vivants, il est connu que certains organes perceptifs effectuent des
traitements que l'on peut assimiler à des inferences assez frustes. Le fait d'appeler
d'un même nom une variété de processus n'implique nullement que ces processus
revêtent des formes identiques, ou même semblables, dans chacune de leurs
manifestations. Il doit toutefois exister un ensemble de propriétés caractéristiques
qui font qu'un processus peut être qualifié d'inférentiel, faute de quoi une telle
dénomination serait impropre.
'Il faut se méfier des résultats d'impossibilité en science : il y en a peu, et ils ont des
conséquences très profondes. Ce n'est pas parce que l'on n'a pas réussi à faire cette
décomposition, ou parce que l'on a l'intuition que les hommes effectuent ces opérations
sans les décomposer, que celle-ci est impossible. 4 La représentation des connaissances
Nous supposons donc qu'il est possible de rendre compte d'une large variété de
comportements "intelligents" en les analysant en termes d'inférence. Il est important
de démarquer cette thèse de celle qui assimile cognition à "computation". Rendre
compte d'un comportement au moyen d'un outil n'affirme rien sur la nature de ce
comportement, mais seulement sur les aspects que l'on cherche à modéliser.
Une autre leçon des recherches en IA est que :
Pour être efficace, l'inférence doit être guidée par la
connaissance.
En effet, l'ambition des premiers programmes d'IA était de réaliser en quelque
sorte une "machine à inférer universelle" qui pourrait aussi bien démontrer de
nouveaux théorèmes que commander un robot. Certains résultats d'indécidabilité
(nous y reviendrons au §3.4.3.) montrent qu'une telle machine ne peut être
complète : il y a des propositions vraies qu'elle ne pourra jamais démontrer, et, si
l'univers dans lequel évolue le robot est suffisamment complexe, des situations pour
lesquelles il existe un moyen de résoudre une certaine tâche, moyen que la machine
ne pourra pas découvrir. Mais il n'était pas invraisemblable de penser a priori que
dans la plupart des situations auxquelles nous avons à faire face, certaines
2heuristiques qu'il suffisait de découvrir permettaient à une machine universelle de
trouver des solutions utilisables.
Or cette ambition s'est avérée irréaliste. Il y a en général trop de choix possibles
pour qu'une recherche systématique, même guidée par de bonnes heuristiques, ait la
moindre chance d'aboutir à des solutions utilisables. Des résultats théoriques sur la
complexité intrinsèque de la recherche heuristique (voir notamment [Pearl,85]) ont
permis d'étayer cette constatation empirique.
S'il ne peut exister de machine universellement efficace pour rendre compte du
comportement intelligent, c'est ou bien qu'il ne peut pas en exister du tout, ou bien
qu'il ne peut en exister que localement. Préciser cette idée de localité amène à dire
qu'il faut des connaissances sur le domaine, autres que le simple énoncé de la tâche,
avant de pouvoir se lancer dans sa résolution avec l'espoir d'aboutir dans un délai
raisonnable. C'est pourquoi, depuis une vingtaine d'années, les chercheurs en IA ont
concentré leurs efforts sur la façon de communiquer à la machine des connaissances
sur un domaine, car il s'agit là d'un préalable à toute tentative réaliste d'obtenir des
résultats utilisables.
^On entend ici par heuristique un procédé dont la complétude n'est pas garantie, mais
dont l'expérience montre qu'il conduit souvent à de bonnes solutions. Dans les
publications d'IA. on appelle heuristique une fonction qui évalue numériquement la
"qualité" d'un état ; par exemple, dans un programme de jeu. cette fonction permet
d'ordonner les coups légaux et de choisir celui qui amène le joueur dans la "meilleure"
position. Introduction 5
Il s'est donc constitué un sujet de recherches, intitulé représentation des
connaissances (ou, en terminologie anglo-saxonne Knowledge Representation), qui
est abordé dans toutes les conférences d'IA et qui possède également ses propres
conférences. C'est ce sujet que le présent livre a l'ambition de traiter.
1.2. Ceci n'est pas de l'informatique !
Si l'informatique est considérée comme la traduction de Computer Science, il
n'y a pas a priori de relation entre la technique des ordinateurs et le problème
général de la représentation des connaissances. On a cherché à modéliser le
comportement inférentiel et on a même donné des formalisations de la notion
d'algorithme bien avant l'apparition des ordinateurs, et nous verrons au §3.4. qu'il
est possible de traiter de ces questions indépendamment de toute supposition sur
leur réalisation matérielle. Il y a également de bons arguments pour contester que
3l'intelligence artificielle soit une branche de l'informatique . La représentation des
connaissances est un domaine qui peut être considéré en soi, sans être rattaché à
l'informatique, science des ordinateurs.
Mais les promoteurs du mot "informatique" ont insisté, ajuste titre, sur le fait
que l'analyse des procédés de traitement de l'information n'est pas intrinsèquement
liée à l'étude d'un dispositif matériel particulier, l'ordinateur. En ce sens large, y a-t-
il un obstacle à rattacher la représentation des connaissances à l'informatique ? La
réponse dépend de ce que l'on entend exactement par "information". Jacques Arsac
(cf. [Arsac,87] et [Arsac,93]) distingue avec soin l'information, qui s'inscrit sur u n
support matériel et qui peut faire l'objet d'un traitement formel, de la connaissance,
qui se place au niveau du sens, et qui ne serait accessible qu'à l'esprit humain. Pour
plusieurs raisons — développées dans [Kayser,89] et [Kayser,90] —, nous
n'adoptons pas ce point de vue, mais nous serons amenés (§2.3.) à distinguer
également information et connaissance. Ces arguments justifieraient un refus
d'inclure la représentation dess dans l'informatique, science du
traitement des informations (tout en la plaçant au cœur des sciences cognitives).
Malgré tout, il est évident que c'est l'essor de l'informatique qui a stimulé ces
recherches et les a dotées d'un fort enjeu socio-économique, et c'est un fait que la
plupart des chercheurs en IA se perçoivent eux-mêmes comme informaticiens. On
serait tenté de dire que si la définition élargie de l'informatique reste insuffisante
pour couvrir la pratique, il faut la modifier.
-'Cf. "Bien que l'ordinateur soit un outil indispensable pour faire tourner nos
systèmes, l'IA n'est pas une branche de l'Informatique. Notre démarche est différente de
celle des informaticiens, en particulier par l'importance que nous attachons au
comportement des êtres humains" extrait de l'avant-propos de [Pitrat,93]. "Informatique"
est clairement pris ici au sens de Computer Science. 6 La représentation des connaissances
Il n'est donc pas interdit de penser que le titre de cette section a une certaine
parenté avec celui d'un tableau bien connu de René Magritte, à condition que l'on
accepte de donner à l'informatique un champ de compétences particulièrement
étendu.
1.3. Inference et raisonnement
On parlera ^inference pour désigner d'une façon générique l'ensemble des
mécanismes par lesquels des entrées (perceptives ou non) sont combinées à des
connaissances préalables afin d'obtenir des comportements élaborés. Le terme de
raisonnement sera réservé au cas particulier où l'inférence peut être justifiée par des
principes communément admis : en d'autres termes, l'être doué de "raison" n'obtient
pas seulement un résultat ; il peut aussi expliquer comment il arrive à ce résultat, en
explicitant les prémisses sur lesquelles il s'est fondé et les règles par lesquelles ces
prémisses y mènent.
Accepter cette terminologie conduit à constater une distinction importante entre
raisonnement naturel et artificiel : les êtres biologiques produisent beaucoup plus
facilement de l'inférence que du raisonnement ; seul l'être humain — et encore, dans
des conditions assez restrictives — peut produire des raisonnements. Au contraire,
les systèmes artificiels symboliques produisent aussi facilement l'un que l'autre
puisque, comme le fait remarquer p. ex. [Pitrat,93], on peut faire en sorte qu'ils
aient accès à tous les paramètres nécessaires à la description de ce qu'ils sont en
train de faire, donc la liste des règles utilisées est un sous-produit facile à obtenir à
partir de n'importe quelle inference. Il n'en est pas de même dans les systèmes
naturels.
1.4. Inference sans représentation
Dans un article très polémique intitulé "intelligence sans représentation",
Rodney Brooks [Brooks,91 ] soutient que les problèmes prioritaires à résoudre pour
fabriquer des systèmes intelligents concernent la perception et la motricité, et qu'il
est plus important, dans ce but, de réaliser des systèmes qui réagissent dans le
4monde que des systèmes qui se représentent le monde . L'évolution prouve, dit-il,
que le plus difficile — puisque cela a pris des milliards d'années — est d'obtenir des
4Malgré de notables différences, on retrouve ce genre de critique dans un grand nombre
d'ouvrages, qui insistent soit sur l'impossibilité d'une intelligence non incarnée
[Dreyfus,79] [Flores & Winograd,86], soit sur les limites intrinsèques d'une approche
basée sur l'inférence symbolique (cf. le courant dit «connexionniste» p. ex. [PDP,86]).
Parmi les textes français débattant de ces questions, on se référera notamment à
[Intellectica,90] et à [Andler,92]. Introduction 7
systèmes qui perçoivent leur environnement et parviennent à survivre en y
répondant d'une façon fruste. Ceci une fois obtenu, la couche "intelligence" — qui
n'a nécessité "que" quelques centaines de milliers d'années — se mettra en place
beaucoup plus facilement.
Par contraste, l'IA semble souvent faire comme si le niveau perceptif, auquel elle
s'intéresse peu, et qui permettrait de dégager les représentations, pouvait être
totalement isolé du niveau inférentiel, auquel elle consacre l'essentiel de ses efforts.
Une des justifications données, p. ex. par Brooks, pour refuser de prendre en compte
les représentations, est que cette séparation est inadéquate. Dans les "créatures" qu'il
construit, on ne peut identifier aucun produit de la perception, et d'ailleurs aucun
organe central de contrôle n'est prévu pour le prendre en charge. "Même au niveau
local, ajoute-t-il, nous n'avons pas de représentation au sens de VIA
traditionnelle". Sans vouloir faire d"'anthropomimétisme", il se dit en accord avec
la thèse selon laquelle, "même dans l'activité humaine, beaucoup de choses sont
dues à une réflexion du monde à travers des mécanismes très simples, sans
représentation détaillée" ([Brooks,91] pp. 147 et 149). Un autre argument — que
Brooks exclut explicitement, mais qui est souvent donné pour justifier l'approche
"connexionniste" — serait que le fonctionnement du seul "dispositif manifestement
doté d'intelligence, le cerveau humain, ne semble pas reposer sur des
représentations.
On peut cependant formuler de nombreuses objections à pareille thèse : de la
possibilité d'obtenir quelques bribes de comportement intelligent sans
représentation, on ne peut déduire que l'usage de représentations ne conduit pas à
réagir plus efficacement sur le monde. L'analyse de l'évolution proposée par Brooks
est d'ailleurs facile à retourner :
C'est la capacité à transmettre des représentations qui a permis
l'extraordinaire accélération des possibilités humaines.
Autrement dit, les représentations servent de "condensé d'expérience" qui
semblent jouer un rôle irremplaçable pour nous éviter, et éviter aux autres, de
reproduire des réponses inadéquates.
Et surtout, il faut se garder d'identifier l'objet et le modèle. Du fait que l'on n'a
pas pu isoler des représentations dans le cerveau, il ne faut pas conclure que la
notion de représentation est inutile pour modéliser la cognition humaine. Et
lorsque, comme Brooks, on n'a pas pour ambition l'imitation des performances
humaines, mais simplement la volonté de réaliser des machines agissant
efficacement sur l'environnement, ce n'est pas parce que de telless peuvent
(peut-être) fonctionner sans représentation qu'il faut se contraindre à parler de ce
qu'elles font (c'est-à-dire à donner un modèle de leur fonctionnement) sans utiliser
cette notion. 8 La représentation des connaissances
À titre subsidiaire, on ajoutera qu'un des principaux intérêts qu'il y a à disposer
d'un modèle, c'est de pouvoir répondre à des questions du type "que se passerait-il
si "comment se fait-il que où ce qui remplace les points de suspension
est, bien sûr, exprimé dans le langage de celui qui pose la question. Y répondre
implique notamment que la traduction entre ce langage et le modèle ne soulève pas
de grave difficulté. Or, si le modèle n'utilise pas de représentation, la traduction
risque d'être délicate. De même, on voit mal comment un modèle sans
représentation pourrait avoir la capacité d'expliquer son propre fonctionnement.
Ne serait-ce que pour ces raisons, il paraît plus prometteur de tenter de
comprendre le comportement intelligent au moyen de représentations. Chapitre 2
Codage des informations
Ce qui peut se représenter peut se coder. Il y a une science du codage. La
représentation des connaissances n'est-elle qu'un nouveau nom donné à cette
science ?
Non, pour une raison très simple : nous avons déjà insisté sur le fait que nous
attendions des connaissances qu'elles se comportent comme guides des inferences ;
leur simple stockage sous une forme condensée et fiable, ce à quoi s'intéresse le
codage, ne leur confère nullement ce rôle. Mais il est nécessaire de savoir coder, et
nous reviendrons à la fin de ce chapitre sur la distance qui sépare le codage
d'informations de la représentation de connaissances.
2.1. Quelques éléments sur le codage
2.1.1. Codage et représentation
Un symbole ou une suite de symboles ne permettent pas de savoir ce qui est
représenté (O représente une lettre ou un chiffre), four un nombre en anglais, un
ustensile de cuisine en français, 4 8 07M une altitude, un digicode, etc. Il faut
disposer de types de façon que l'ensemble <suite de symboles ; type> détermine de
façon unique ce qui est codé.
Remarquons qu'il suffit de deux signes pour coder n'importe quelle information.
En effet, avec p positions, on peut coder exactement IP symboles distincts sur un
alphabet à deux signes. 10 La représentation des connaissances
Preuve : appelons a et b les deux signes. Il est évident qu'avec p = 1, on peut
coder exactement deux symboles distincts, l'un par a et l'autre par b.
1
Supposons qu'avec p-1 positions, on puisse coder exactement 2P" symboles
1
distincts. En ajoutant une p* ™ position, on double le nombre de possibilités (en
mettant a dans la nouvelle, et en y mettant b, on obtient des codes
distincts et comme tout code possède soit un a soit un b dans cette position, on
1
épuise ainsi toutes les possibilités de codage) donc 2.2P" = 2P représente le
nombre exact de symboles distincts codables sur p positions.»
Ainsi, si on prend pour symboles les 26 lettres majuscules de notre alphabet, les
26 minuscules correspondantes, les 10 chiffres arabes, il y a au total 26 + 26 + 10 =
62 symboles distincts. 6 positions d'un alphabet à 2 signes suffiront puisque 62 <
6
2 = 64. La correspondance entre une suite de 6 signes et un symbole peut être
choisie arbitrairement. Si on prend pour signes 0 et 1, et que l'on décide de coder A
par 0 0 000 0, B par 00 0001, C par 000010, Z par 011001, a par 011010,
b par 011011 , ..., z par 110011 , 0 par 110100 , 1 par 110101 , 9 par
111101, nos exemples ci-dessus donnent respectivement :
001110 pour la lettre O,
110100 pour le chiffre 0
011111101000101110101011 pour la séquence de quatre lettres four
(qui reste ambiguë)
111000111100110100111011001100 pour la séquence 4807M
(même remarque).
Remarque : nous avons présupposé que chaque symbole occuperait le même
nombre de positions (ici, 6) ; cela n'a rien d'obligatoire. Si l'on connaît pour
chaque symbole ej sa probabilité d'apparition, pj, on peut démontrer que la
longueur minimale du code est obtenue si on peut organiser les symboles sur un
"questionnaire" binaire, où à chaque nœud, les deux réponses sont
équiprobables (codage de Huffman, cf. [Crochemore & Rytter,94]).
Sans vouloir développer la théorie des questionnaires, traitons l'exemple suivant :
les symboles sont les couleurs de l'arc-en-ciel dotées des probabilités
suivantes : le rouge a une probabilité de 1/2 ;
le bleuet le vert, une probabilité de 1/8 ;
le violet, Y indigo, le jaune, et Y orange une probabilité de 1/16 (la
somme des probabilités est bien 1/2 + 1/8+ 1/8 + 1/16 + 1/16 + 1/16 + 1/16= 1).
On peut construire un questionnaire idéal, par exemple de la façon suivante :
Première question : rouge ou non (chaque branche a une probabilité égale)
Si non rouge, deuxième question : (bleu ou vert) ou autre (même remarque)
Si (bleu ou vert), troisième question : bleu ou vert (id.)
Si autre, troisième question : (violet ou indigo) ou autre (id.)
Si (violet ou indigo), quatrième question : violet ou indigo (id.)
Si autre, quatrième question : jaune ou orange (id.)
Ce questionnaire donne naissance à un code de longueur variable ; si par exemple
le choix de la première alternative, dans chaque question, est codé par o, et
celui de la deuxième par 1, le code obtenu est : Codage des informations 11
o rouge
bleu 100
vert 101
violet 1100
indigo 1101
jaune 1110
orange m i
Même si les "tranches" sont de longueur variable, le décodage n'est pas ambigu. On
pourra s'en assurer avec la séquence prise au hasard : oiooioooimo . La
seule segmentation possible est o 100 100 o m i o, soit rouge-bleu-bleu-
rouge- orange- rouge.m
Exercice [Codage variable de l'alphabet] : imaginer, selon le même principe, un code
de taille variable pour les lettres de l'alphabet (majuscule), en supposant que la
probabilité de A et E vaut 1/8, celle de I et O, 1/16, celle de K, Q, W et X, 1/64, et
celle des 18 autres lettres, 1/32. Utiliser ce code pour coder le mot AMBIGU.
Une séquence de signes n'acquiert de signification que si l'on connaît le type de
l'information codée, et si chaque type est pourvu d'une convention non ambiguë de
codage. De plus, représenter, c'est coder en prenant en compte les utilisations.
Nous allons illustrer ce propos avec l'exemple des nombres.
2.1.2. Codage des nombres
2.1.2.1. Entiers naturels
La notation usuelle des nombres nous donne une première technique de codage.
6
Avec nos 62 symboles, nous n'avons pas épuisé les 2 = 64 possibilités données
par l'utilisation de 6 positions ; nous pouvons donc coder la virgule, par exemple
par 111110 et le signe moins par 111111. Le nombre - 3,5 formé de 4 symboles
serait ainsi codé par la suite des 4 x 6 = 24 positions :
111111110111111110111001. Nous pouvons ainsi coder tous les nombres
décimaux, et nous dirons que nous codons les nombres dans le type "caractère".
Mais un tel codage est une bien mauvaise représentation. Aucune des utilisations
normales des nombres — les opérations arithmétiques — n'est aisée avec ce
codage : quelle méthode appliquer pour trouver la somme des nombres représentés
respectivement par 110111111110111001 et 111001110111 ?
Il existe cependant une façon simple de procéder à la somme de deux nombres
représentés avec deux signes : on adapte la bonne vieille addition décimale "à
retenue". Si on prend pour signes 0 et 1 et que l'on garde l'ordre de codage
systématique présenté ci-dessus pour ne coder que les entiers naturels, 0 se
représentera par 000000, 1 par 000001, 2 par 000010, 9 par 001001, 10 1 2 La représentation des connaissances
par 0 01010, etc. Il est facile de voir que le signe le plus à droite est celui des
unités, celui immédiatement à sa gauche est celui des "deuzaines", puis des
"quatraines", des "huitaines", etc. On décode :
32 16 8 4 2 1
0 0 1 0 10
par : "une huitaine" + "une deuzaine" = 8 + 2 = 10. Dans ces conditions, l'addition
5 + 5 = 10 se pose comme :
1 1
000101
+ 000101 (lire : "u n et un = 10, j e pose 0 et je retiens un", etc.)
00101 0
Les autres opérations sont également des adaptations simples des méthodes
usuelles. Par exemple, la multiplication :
000101
x 000101
000101
000101 = =
011001. On décode:
32 16 8 4 2 1
0 1 1 0 0
par : "une seizaine" + "une huitaine" + "une unité" = 16 + 8 + 1 = 25. Nous avons
donc deux façons, l'une beaucoup plus agréable que l'autre, de coder les entiers.
Mais, au contraire de "caractère", cette nouvelle façon ne concerne que les entiers
positifs (et encore seulement certains d'entre eux, puisque nous avons limité ici le
code à 6 positions). Nous l'appellerons le type "entier-pos". Si nous voulons
représenter certains entiers négatifs, voire des nombres réels, il va falloir trouver de
nouvelles conventions de codage, c'est-à-dire de nouveaux types.
2.1.2.2. Entiers relatifs
Pour un certain nombre p de positions, nous définissons le type "entiers^", afin
1
de représenter dans un système de deux signes 0 et 1 les entiers compris entre -2P'
]
et 2P- - 1. Il y en a bien IP, donc on peut les coder sur p positions. La convention
"entiers*"' consistera à représenter un nombre positif ou nul dans le type "entier-pos"
et un nombre négatif par la somme de ce nombre et de 2P dans ce même type.
6
Exemple : prenons p = 6 ; on peut représenter dans le type "entier " des nombres
compris entre -32 et +31. Le nombre 25 sera codé par 011001 qui est également Codage des informations 13
la représentation de 25 dans le type "entier-pos" ; le nombre -25 sera codé par
6loo m qui est la représentation de -25 + 2 = -25 + 64 = 39 dans le type
"entier-pos".•
16 16Exercice [les entiers] : un type usuel en informatique est celui des "entier".
Quels sont les représentables dans ce type ?
Donnons deux propriétés du type "entier^". La position la plus à gauche du
codage donne le signe du nombre représenté.
1 1Preuve : Soit X un "entier?', donc -2? < X < 2? -1 .
si X > 0, son codage est le même que dans le type "entier-pos", donc la position la
1 1plus à gauche est le chiffre des "2P" -aines". Comme X < 2^ - 1, il ne comporte
1aucune "2P" -aine". La position la plus à gauche de son codage est donc à o.
1si X < 0, son codage est celui de (2P + X) dans le type "entier-pos" ; comme X >-2P" ,
1 1 1on a (2P + X) > (2P - 2P" ) = 2^" , il comporte une "2P" -aine". La position la plus à
gauche de son codage est donc à I . B
Si X*0, la somme du codage de X et du codage de -X vaut IP [d'où le nom de
"complément à 2" (sous-entendu "2 puissancep") de cette convention].
Preuve : si X > 0, codage(X) = X, codage(-X) = 2P • X, donc codage(X) + codage
(-X) = 2P
si X < 0, codage(X) = 7P + X, codage(-X) = -X, donc codage(X) + codage
(-X) = 2P.m
2.1.2.3. Nombres réels
Pour un certain nombre p de positions, on choisit un nombre e < p et on note
emm = p - e. On définit maintenant un nouveau type, que nous appelons "réel " par
la convention de codage suivante : soit R le nombre réel à coder ; soit M un nombre
Eréel et E un entier tels que R = M.2 . R étant fixé, il y a une infinité de couples
E 1 2 1(M,E) qui satisfont R= M.2 . (p. ex. 2 = 2.2°= 1.2 = 0,5.2 = ... = 4.2' =
28.2" = ... Mais si R*0, il existe un couple unique (M,E) qui satisfait aux
Econditions : E est un entier, R = M.2 , 0,5 < |M| < 1.
5 L L+ 1Preuve : si R est différent de 0, il existe un entier L unique tel que 2 < IRI < 2 ;
R IRI
Eon prend M = gCTT et E = L+1. On a bien E entier, R = M.2 et IMI = gU+T donc
0,5 < IMI < 1.B
Si R = 0, M est unique (M = 0) mais E est indéterminé ; par convention, on
prendra dans ce cas E = 0. Dans ces conditions, M s'appelle la mantisse et E
l'exposant de la représentation.
^C'est la partie entière du logarithme à base 2 de |R|. 14 La représentation des connaissances
Exemples : Soit R = -3,5 ; 2 < IRI < 4, donc L = 1 ; on prend M = -3,5/4 = -0,875
et E = 2.
1 2 1 3
Soit R = 4807 ; 2 = 4096 < IRI < 2 = 8192, donc L = 12 ; on prend M =
4807/8192 = 0,586792 et E = 13.B
Comme E est entier, on pourra le représenter dans le type "entier*". Mais pour
M, qui est réel, nous devons trouver une convention de représentation. Soit M' la
1 1 m ] m ]
partie entière de M.2" " . M' est compris entre -2 ~ et 2~-\.
/T> 1 m 1 m_1
Preuve : comm e 0,5 < IMI < 1, on a -1 < M < 1, d'où -2 < M.2 " < 2 . Prendre la
m 1 M 1partie entière rend la première inégalité non stricte, d'où -2 " < M' < 2 " .B
Donc M' est représentable dans le type "entier"'". Nous définissons la convention
em
"réel " de la façon suivante : si R est égal à zéro, il est codé par p fois le signe 0.
7
Sinon, il est codé par la juxtaposition du nombre E codé dans le type "entier*" et du
1
nombre M' codé dans le type "entier" ", où E et M sont l'unique couple satisfaisant
E
les trois conditions : E est un entier, R= M.2 , 0,5 < |M| < 1, et où M' est la
m l
partie entière de M.2~.
Exemples : Soit p = 12 et choisissons e = 4 ; il vient m = 12-4=8 . Le codage de
4,8
-3,5 dans le type "réel " est la juxtaposition du codage de l'exposant E = 2
comme "entier" soit ooio et, comme la mantisse M vaut -0,875, de l'entier M' =
7 8
partie entière de M.2 = -0,875.128 = -112 comme "entier ", soit encore de -112
8
+ 2 = -112 + 256 = 144 comme "entier-pos", d'où 10010000. Il vient finalement
le code 001010010000.
Le codage de 4807 dans le même type nécessite le codage de l'exposant E = 13
4
comme "entier", mais le plus grand entier représentable dans le type "entier?"
1 3
est 2P"-1 soit ici 2 -1 = 7; donc 4807 n'est pas représentable comme
4 8
"réel ' ".»
6,12
Exercice [Mont-Blanc] : Représenter 4 807 dans le type réel '.
emDonnons quelques propriétés du type "réel ". Les réels non nuls représentables
m 2e 1 1 1 26 1
dans ce type sont compris dans les intervallesf -(l-2'" )2 " " ; -2" " " ] et [
2eA]
2-1-26-1 . (\-2l-™)2-]
Preuve : considérons la valeur absolue du nombre représenté. Sa plus petite valeur
est obtenue en prenant la plus petite valeur de la mantisse, soit 0,5 et la plus
petite valeur de l'exposant, c'est-à-dire le plus petit entier que l'on puisse coder
6 e 1 2e 1
dans le type "entier " soit -2 " ; donc il s'agit de ±0,5.2" " . Sa plus grande
valeur est obtenue en prenant la plus grande valeur de M', c'est-à-dire le plus
m 1
grand entier que l'on puisse coder dans le type "entier™" soit 2 * -1 ; d'où M =
m 1 m 6M'/2 "l = 1 - 2 " ; pour avoir la plus grande valeur absolue, il faut prendre
e 1
aussi le plus grand exposant, soit 2 " -1 ; donc les réels ayant la plus grande
1 2E 1_1
valeur absolue sont +(1 - 2 "'").2 " .B
m
"En toute rigueur, M' étant la partie entière de M.2 '\ M peut prendre toute valeur réelle
strictement inférieure à 1, mais au décodage, on "relira" le nombre calculé ci-dessus. Codage des informations 15
4 8Exemple s : dans le type "réel' " considéré ci-dessus, ces intervalles
correspondent à [-127;-0,00195] et [0,00195;127]. Il n'est pas étonnant que
8 24480 7 n'ait pu être représenté dans ce type. Dans le type "réel ' " — qui est
nettement mieux adapté à des calculs usuels — les intervalles sont
38 39 39
[-1,701 411 631.10 ; -1,469 367 938. 10" ] et [1,469 367 938. 10" ;
38
1,701 411 631. 10 ]. De plus, 0 est représentable.B
"Granularité" du codage : l'écart relatif maximal entre deux réels non nuls dont le
2 1
codage est identique est voisin de 2 '" .
Preuve : Soient R-| et R2 deux réels ayant même codage, donc même exposant E ;
m 1leurs mantisses M1 et M 2 sont telles que M', la partie entière de M-|.2 " est
m i m m 1
égale à M-2 '' ; on a donc = M72 ^ et M < (M'+1)/2 - . L'écart relatif 2 2
1 7 1
(M'+l)/^™- - lvr/2" - 1
1 m1 = comme lail sera maximal pour- (M'+1)/2'' MVf valeur minimale
1 2
de M est 1/2, la valeur minimale de M' est 2" " , d'où un écart maximal de
m 2 2 m
1/(1+2 " ), très voisin de 2 " .«
8 24 2 2 7 Application : dans le type "réel ' ", deux nombres distants de 2" , soit 2,4.10"
pourront être confondus.
Cette granularité est illustrée par le diagramme ci-dessous :
7Seules les séquences de p signes dont les positions e+l et e+2 diffèrent ou bien
emdont les positions e+3 à p sont égales à zéro codent des éléments du type "réel ".
Preuve : pour un nombre positif, la mantisse M est > 1/2 ; M', la partie entière de
7 1 7 2
M.2" " , est donc > 2" ' , et la deuxième position binaire du codage de M' comme
7"entier" " est à 1 tandis que la première est à 0 (nombre positif) ; [sauf pour R -
0, et dans ce cas, toutes les positions sont à zéro] ;
7 1 m 2pour un nombre négatif, -1 < M < -1/2 ; donc -2" " < M' < -2 ~ et son codage
7 mcomme "entier"", qui est celui de 2 + M' comme "entier-pos" est compris entre
7 1 7 1 1 22" " et 2" " + 2" " ; sauf pour la borne supérieure (correspondant à M = -1/2),
cette représentation a sa première position à 1 et sa deuxième position à 0 [pour
la borne supérieure, ces deux positions sont à 1 mais toutes les autres sont à
o].a
En conclusion, un même objet mathématique, un nombre, peut avoir
d'innombrables codages différents suivant le type dans lequel on le code. Le choix
de ce type dépend des opérations qu'on envisage de lui faire subir. Si des opérations
sur les entiers suffisent, on choisira le type "entier?" avec une valeur de p fonction du
^Les positions sont numérotées de gauche à droite en partant de 1. 16 La représentation des connaissances
plus grand résultat que l'on envisage d'obtenir. Sinon, il faudra prendre un type
em"rée\ ". À nombre de positions égal, on choisira une grande valeur de e si c'est la
plage des valeurs possibles qui importe, ou une grande valeur de m si la précision
est primordiale.
2.1.3. Codage des graphiques et des images
Nous avons illustré la notion de codage en traitant assez longuement le codage
des nombres, mais nous ne voudrions pas laisser le lecteur sur l'impression que
seules des informations numériques sont faciles à coder. Nous avons déjà attiré
l'attention sur le fait que toute chaîne de caractères était facilement codable (s'il y a «
caractères distincts dans l'alphabet et que l'on dispose de deux signes, il suffit de
8coder chacun d'eux sur p positions en choisissant p tel que 2P > «) . Mais les
graphiques, les sons, les images peuvent également être codés.
Le problème posé par le codage de ces informations est celui de la réduction du
continu au discret, problème que nous avons d'ailleurs déjà rencontré lors du codage
des nombres réels. La situation est cependant plus facile ici, car le continu dont il
s'agit a un support physique, et l'on sait que les signaux physiques ont un spectre à
support borné (la vitesse à laquelle une grandeur physique change de valeur n'est pas
infinie). Un célèbre théorème "d'échantillonnage", dû à Claude Shannon, montre que
dans ces conditions, un signal continu peut être codé sans perte d'information, par la
suite des valeurs qu'il prend à des intervalles réguliers. Reste le fait que ces valeurs,
des réels, ne peuvent être codés qu'avec approximation. Mais nous avons insisté sur
le fait que représenter, c'est coder en prenant en compte les utilisations ; or pour
toute utilisation, il existe un seuil de finesse au-delà duquel un accroissement de
précision n'a plus aucune influence.
Si l'on doit coder un graphique, par exemple, on peut choisir un maillage sur
lequel on le projette ; la maille sera d'autant plus fine que l'utilisation envisagée
nécessite une grande précision. Puis, on approche cette projection par une suite de
vecteurs. L'usage est de choisir une base de 8 vecteurs possibles (codage de
3Freeman), et comme 8 = 2 , on se ramène à une suite de caractères codés sur 3
positions dans un alphabet à 2 signes.
"Des techniques que nous ne présentons pas ici permettent de "comprimer" le codage, en
prenant en compte l'existence de régularités dans les séquences de caractères à coder (cf.
p. ex. [Crochemore & Rytter,94]). Codage des informations 17
Chacune de ces huit orientations correspond à un chiffre ; ainsi, le contour ci-
dessous (codé en partant de l'extrémité nord-est) donnera :
3334644444445666442244446422356444644245445544456666600 0
200002000446600664444434464 7 0660100006464624444445707707
6666000021000106667007006660020660066660660024222 2 066006
0 .
En codant chacun de ces symboles de façon naturelle sur l'alphabet à deux signes
0 et 1, le début du codage est :
011011011100110100100100100100100100101.. .
Si on choisit un maillage moins fin (une maille = 3x3 mailles du codage
précédent), on obtient un codage grossier : 18 La représentation des connaissances
344544254445460007444600644470660100607767227 , mais qui
occupe nettement moins de place que le précédent (45 vecteurs au lieu de 169, soit
une séquence de 135 signes au lieu de 507).
Cette méthode ne permet que de coder des contours continus ; pour représenter
des discontinuités, il faudrait pouvoir "lever le crayon", et parmi plusieurs
possibilités, la plus simple — mais pas la plus économique — consiste à dédoubler
les vecteurs : 8 vecteurs "noirs" et 8 vecteurs "blancs".
Si maintenant on veut coder des images en noir et blanc, il faut non seulement
discrétiser le plan par un maillage (chaque maille s'appelle alors un pixel,
abréviation de l'anglais "picture element"), mais aussi discrétiser les "niveaux de
gris". Pour des applications rudimentaires, 8 niveaux de gris peuvent suffire, par
exemple : Codage des informations 19
Une image est alors rendue par un tableau, dont chaque case code le niveau de
gris du pixel correspondant. Ainsi, l'image :
0 1 1 0 0 3 4 1
1 2 2 1 3 4 5 2
2 6 5 2 3 5 6 3
3 7 6 4 3 6 7 4
correspond au tableau :
2 3 7 6 6 7 4 3
1 2 3 7 7 4 3 2
0 1 2 6 6 3 2 1
0 0 1 2 2 2 1 0
qui sera codé, sur un alphabet à deux signes par :
00000100100000001110000 1
00101001000101110010101 0
01011010101001110111001 1
01111111010001111011110 0
01001111111011011110001 1
00101001111111110001101 0
00000101011011001101000 1
00000000101001001000100 0
Si l'on veut coder des images en couleur, on peut juxtaposer pour chaque pixel
deux informations, l'intensité (le niveau de gris, si l'image était en noir et blanc) et
la couleur (on discrétise l'ensemble des couleurs possibles sur une "palette"
comportant l'ensemble des teintes qu'il est nécessaire de discriminer dans une
application donnée).
Nous avons montré, dans cette section, que le codage d'informations aussi
variées que des textes, des nombres, des images même en couleur, sur un alphabet
aussi pauvre que 0 et 1 ne soulève aucun problème de principe. La réalisation de ces 20 La représentation des connaissances
codages de façon optimale (en place occupée, en temps de codage et de décodage, en
adaptation à certaines opérations) est une affaire beaucoup plus délicate, mais au lieu
de chercher à l'approfondir, nous allons plutôt examiner les opérations que nous
souhaitons effectuer, ce qui nous mènera progressivement de l'idée de codage de
l'information à celle de représentation des connaissances.
2.2. Recherche d'une information
Supposons codé, suivant une convention appropriée, un ensemble
d'informations, par exemple une suite d'entiers. Cet effort n'a de sens que si certaines
opérations sont définies sur ce code, et nous allons nous intéresser ici au fait de
savoir si un élément donné du type appartient ou n'appartient pas à la suite qui a été
codée. On peut spécifier le problème de la façon suivante : le codage est une
opération qui, étant donné une suite d'éléments d'un type donné, crée une suite de
symboles ; la recherche est une autre opération qui, étant donné cette suite de s et un élément du même type, répond si cet élément est un de ceux qui ont
été codés. D'une façon un peu plus formelle, on peut écrire :
Codag e : ensemble d'éléments du type T -» code
Recherch e : code x élément du type T —» booléen
où T est un type pour lequel une convention de codage a été définie, x désigne le
produit cartésien, et booléen* est un type permettant de coder les deux valeurs vrai
et faux (généralement, la convention de codage de ce type consiste à représenter
vrai par 1 et faux par 0). La deuxième ligne se lit donc : Recherch e est une
application (au sens mathématique du terme) qui, étant donné un code c et un
élément e appartenant au type T, produit un élément b de type booléen. Ce que cette
convention d'écriture ne dit pas, et que nous devons donc exprimer séparément, c'est
que le résultat b doit être vrai si et seulement si l'élément e faisait partie de
l'ensemble qui a servi à l'application Codage pour créer le code c.
vCette appellation usuelle en Informatique est un hommage à George Boole (1815-1864)
dont le livre An Investigation into the Laws of Thought (1854) contient les bases du
calcul propositionnel (ainsi d'ailleurs que des contributions au calcul des probabilités).