Jeux de projections
Exemple de triplet de projections MojetteSoit une grille de nombres dont on connaît seulement des sommes
selon des lignes, des colonnes et des diagonales. Dans certains cas,
il est possible de trouver tous les nombres de la grille. Tel est le principe de
base de l’imagerie par scanner (tomodensimétrie). En effet, un scanner X
mesure des taux d’absorption, par le corps, de rayons X selon différentes
lignes de visée (schématiquement, ces valeurs correspondraient aux
sommes évoquées précédemment) et l’on produit avec ces données
des images de l’intérieur du corps (dont les niveaux de gris des pixels
correspondraient aux nombres de la grille).
Produire une image 2D avec les données 1D d’un scanner, comme
réaliser une image 3D à partir de vues en 2D, est cependant un problème
plus complexe. Pour le résoudre, on s’appuie sur la « transformée de
Radon » (R ) selon laquelle les données disponibles sont des éléments de
différentes projections de l’image à reconstituer. Ce procédé mathématique
élaboré dans les années 1910 par l’Autrichien Johann Radon est resté
dans l’ombre pendant plusieurs décennies avant d’être utilisé dans la
plupart des techniques d’imagerie, en astronomie, en médecine, en
sismologie, en surveillance vidéo, etc. Il consiste à trouver la transformée
inverse de R (notée R –1), or reconstituer ainsi parfaitement une image
projetée nécessiterait, en théorie, de disposer d’une infinité de projections.
Le travail des spécialistes de traitement d’images consiste donc, pour
chaque nouvelle technique, à trouver une approximation de R –1 suffisante
pour obtenir la précision requise.
Les travaux de Radon nous ont inspiré la transformée Mojette (M ), une
variante simple de R dont les projections sont des additions ou des
soustractions des nombres d’une grille selon les lignes, les colonnes ou
en biais (pas forcément en diagonale). En utilisant seulement l’addition,
on retrouve le problème évoqué au début de ce texte (et celui du jeu
Mojette^^TM^^ ). Trouver la solution, c’est trouver M –1
exactement, et il est possible d’élaborer des algorithmes qui permettent
de faire cela automatiquement, y compris pour des grilles ayant plus
de 2 dimensions. Ces algorithmes s’appuient sur des théorèmes qui permettent parfois de connaître, pour un type de grille donné, le nombre
de projections nécessaire à l’existence d’une solution, ou les conditions
auxquelles la solution sera unique.
Les applications de M ne concernent pas seulement l’imagerie. Par exemple, supposons que la grille comporte les valeurs d’un fichier numérique (telles que les codes Ascii des caractères) que vous voulez stocker en sécurité. Au lieu d’enregistrer ce fichier de façon lisible par tous sur un disque dur qui peut être détruit, on peut stocker les données de trois projections Mojette chez autant de prestataires de service différents. Aucun d’entre eux ne pourra savoir ce que vous avez mis en sûreté ; seule votre connaissance des projections utilisées permettra de reconstituer le fichier original. De plus, on peut calculer et stocker une quatrième projection de sorte que, si l’une des trois premières est perdue, vous pourrez toujours reconstituer votre fichier.
DOSSIER
L'intelligence des Maths
Maths et automates
Des machines à décider
Classement de mails en fonction du nombre Nv de mots viagra et du nombre Nd de destinataires. La ligne bleue correspond à une règle de discrimination plus complexe que celle de la ligne noire. Elle compte moins d’erreurs (aucune, en l’occurrence) relatives aux données d’apprentissage mais n’est pas pour autant meilleure pour les futurs classements. © RC2C , d’après S. LoustauUne machine peut-elle apprendre ?
Oui, et les maths y sont pour quelque
chose. La théorie de l’apprentissage aide à
doter les ordinateurs d’une « intelligence
artificielle » : une capacité de décision évoluant
avec l’acquisition de données d’observation.
Jouez à « pierre-papier-ciseaux »1 contre un
logiciel doté d’un algorithme (processus de
traitement de données) d’apprentissage bien
conçu, celui-ci va apprendre votre façon de
jouer en y repérant un déséquilibre (il est
en effet établi que personne n’est capable
de jouer à ce jeu d’une manière totalement
imprévisible). Ne vous entêtez pas : plus vous
jouerez, plus vous perdrez !
Comment un algorithme apprend-il ?
Considérons un programme voué à détecter
des spams et dont la décision de classement
d’un mail (spam ou non-spam) dépend
seulement de deux variables : le nombre Nv
de mots viagra présents dans le message et
le nombre Nd de destinataires du mail. On lui
fournit des « mails d’apprentissage » (MA)
déjà étiquetés « spam » ou « non-spam »
(il apprendra d’autant mieux qu’on lui en
donnera un plus grand nombre). Il ajuste alors
sa règle de décision en cherchant, parmi tous
les classements possibles de ces MA, celui qui
rend minimale la valeur du « risque pénalisé »,
somme d’un terme « de risque empirique » et
d’un terme « de régularisation ». Le premier
terme évalue l’ampleur des erreurs commises
sur les MA (certaines étiquettes peuvent en
effet déroger à la règle de l’algorithme) ;
le second quantifie la complexité que peut
atteindre sa règle de décision. La complexité
traduit l’importance attribuée à chaque donnée
d’apprentissage dans l’ajustement de la règle.
Dans le cas présent, une règle complexe peut
consister à décider que si un MA donné a été
exceptionnellement étiqueté « non-spam »
malgré des valeurs Nv et Nd élevées, tout futur
mail ayant des Nv et Nd très proches de celles de
ce MA sera également classé « non-spam ».
L’algorithme doit alors réaliser un compromis
entre un excès de prudence envers les données
(risque empirique trop élevé) et un excès de
confiance (règle trop complexe). Sa règle sera
raisonnable ou « consistante » si son risque
d’erreur commise sur le classement des
nouveaux mails diminue quand le nombre
de MA augmente, se rapprochant ainsi de la
meilleure règle possible (de risque minimal).
L’ampleur de cette diminution traduit l’efficacité
de l’apprentissage.
Le mathématicien cherche donc d’abord à
établir la « vitesse de convergence » maximale
du risque d’erreur vers le risque minimal2, qui
dépend du problème posé et notamment de
la régularité des données à classer. Ensuite, il
cherche à faire en sorte que l’algorithme atteigne
effectivement cette vitesse d’apprentissage
maximale. Pour cela, il faut bien choisir la
valeur du « paramètre de lissage » L qui fixe le
poids du terme de régularisation par rapport
à celui du risque empirique (plus L est grand,
moins la règle tient compte de l’irrégularité des
données d’apprentissage). Grâce à des résultats
de la théorie des probabilités et de la théorie
de l’approximation, il est possible de choisir le
paramètre L de manière optimale.
Cependant, ce choix nécessite souvent de faire
des hypothèses préalables sur la régularité du
phénomène à traiter, celle-ci étant en effet
rarement connue. Mes recherches actuelles
portent sur les moyens d’utiliser les données
d’apprentissage pour choisir L de manière
automatique et donc, finalement, de paramétrer
de la façon la plus efficace possible différents
types d’algorithmes de classification.
1. Cf.sur Wikipedia
2. Par exemple, soient d = (risque d’erreur – risque minimal), noté d1 pour un algorithme A1, d2 pour un algorithme A2 , et n le nombre de données d’apprentissage. Si d1 est proportionnel à 1/ n et d2 à 1/racine carrée de n, alors d1 tend plus vite vers 0 que d2 quand n croît. A1 peut donc apprendre plus rapidement que A2.
Robots sous contrôle
Les ordinateurs calculent-ils « sans se tromper » ? Non, car ils sont
incapables de représenter exactement un nombre quelconque dans
leur mémoire. Par exemple, le nombre pi n’est stocké qu’avec quelques
chiffres après la virgule alors qu’il en possède une infinité. Ainsi, le
plus souvent, des erreurs d’approximation s’accumulent lors d’une
suite d’opérations sur des nombres réels, pour aboutir à un résultat
plus ou moins erroné (un problème sans doute à l’origine du crash de
la première fusée Ariane V).
Pour limiter ces erreurs, des méthodes de « calcul par intervalles » ont vu
le jour dans les années 1950. Elles consistent à manipuler, plutôt que des
nombres, des intervalles dont les bornes sont parfaitement représentables
dans l’ordinateur. Par exemple, pour effectuer des opérations avec pi,
on peut représenter celui-ci par l’intervalle [ 3,1415 ;
3,1416 ], qui
contient pi. Le calcul du périmètre d’un cercle de rayon 1 donne alors
[ 6,283 ;
6,2832 ], qui contient nécessairement le résultat exact (2pi).
On parle alors de « calcul garanti ».
Nous utilisons le calcul par intervalles pour résoudre des problèmes qui
se posent notamment en robotique. À titre d’illustration, considérons un
robot ayant un bras constitué de deux segments articulés. Le premier
segment fait un angle alpha avec l’horizontale ; le second fait un angle beta
avec le premier (cf. figure 1).
Piloter ce robot consiste à déplacer l’extrémité E du bras d’une position
(x1, y1), en coordonnées cartésiennes, à une position (x2, y2). Pour ce faire,
la commande fait varier alpha et beta, nommés « degrés de liberté ». Une
question qui se pose est de savoir si la façon de modifier (alpha, beta) pour
réaliser le déplacement visé est unique ou non ; dans le cas présent,
elle ne l’est pas (cf. figures 2a et 2b).
Si l’on écrit les coordonnées (x, y ) comme une fonction f de (alpha, beta),
l’unicité d’une trajectoire dans l’ensemble des (alpha, beta), nommé « espace
des configurations », nécessite que f soit injective, c’est-à-dire qu’à
tout couple (x, y ) repérant E corresponde un unique couple (alpha, beta). Cette
question est importante parce que la non-injectivité de f est parfois source
de complications pratiques pour l’opérateur, ou au contraire d’intérêt,
comme de pouvoir satisfaire à un critère donné (choisir la commande qui
va minimiser la consommation d’énergie du robot, par exemple).
Il est rarement possible de démontrer algébriquement (« à la main ») toute propriété d’une fonction f associée à un robot donné (qui peut avoir plus de 2 degrés de liberté), telle que l’injectivité, et il ne l’est jamais par un calcul numérique classique à cause des erreurs d’approximation sur les valeurs de f et parce qu’il y aurait une infinité de points à tester un par un. Le calcul numérique par intervalles le permet davantage, en manipulant un nombre fini d’ensembles de points et en s’affranchissant de telles erreurs. En cas de succès, il devient possible de lister, avec certitude et parfois de façon exhaustive, des ensembles de commandes qui permettent de réaliser un déplacement souhaité, d’éviter un obstacle, ou qui aboutissent à une impasse.
Exemple de deux commandes distinctes qui réalisent un même déplacement de l’extrémité d’un bras articulé © RC2C, d’après S. Lagrange et N. Delanoue