Espace de versions - Définition

Introduction

Un espace de versions est un dispositif utilisé en apprentissage supervisé pour induire des concepts généraux ou des règles à partir d'un ensemble mêlant des exemples vérifiant la règle qu'on cherche à établir et des contre-exemples ne la vérifiant pas. L'espace de versions au sens restreint est l'ensemble des hypothèses cohérentes avec le jeu d'exemples. La technique des espace de versions a été proposée pour la première fois par Tom Mitchell en 1978.

Représentation des hypothèses de rectangles à partir d'exemples exemples positifs (les croix vertes, qui doivent être à l'intérieur du rectangle) et négatifs (les ronds rouges, qui doivent être à l'extérieur du rectangle). Le rectangle GB est l'hypothèses la plus générale (en généralisant plus on couvrirait des exemples négatifs), et SB est la plus spécifique (en spécialisant plus on ne couvrirait plus certains exemples positifs). Les rectangles verts représentent d'autres hypothèses de l'espace de versions.

Historique

La notion des espaces de version a été introduite par Tom Mitchell dans le contexte de son travail sur le programme Meta-Dendral, un système expert dont le but était de reconnaître des composants chimiques à partir de spectrométrie de masse. Le système devait pouvoir déduire seul des règles sur les spectromètres qui lui permettent de déterminer l'élément chimique en question. À l'époque, la méthode la plus courante était la recherche dans l'espace des hypothèses : partir d'une hypothèses collant au premier exemple, puis la modifier en ajoutant des exemples au fur et à pour tenter de la faire correspondre. Cependant il n'était pas toujours trivial de trouver des règles de modifications d'hypothèses, et il était parfois nécessaire de retourner en arrière (dans le cas où aucune modification de la règle courante ne fonctionne). Tom Mitchell a proposé une méthode systématique ne nécessitant pas de retour en arrière, même s'il faut toujours définir un espace d'hypothèses et des règles de modification (dans ce cas des règles de généralisation et de spécialisation).

Bien que le principe d'élimination de candidats ne soit pas une méthode populaire d'apprentissage, en raison notamment de sa grande sensibilité au bruit (Russell & Norvig 2002)), certaines applications pratiques ont été développées (Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).

Algorithme

L'algorithme de mise à jour de l'espace des versions est le suivant :

• Initialiser S à l'ensemble de l'hypothèse n'acceptant aucun exemple
• Initialiser G à l'ensemble des hypothèses les plus générales cohérentes avec le premier exemple connu
• Répéter pour chaque nouvel exemple
  • Mettre à jour S :
    • Si x_i est négatif
      • Éliminer les hypothèses de S couvrant x_i
    • Si x_i est positif
      • Généraliser juste assez les hypothèses de S ne couvrant pas x_i pour qu'elles couvrent x_i
      • Éliminer les hypothèses de S qui couvrent maintenant des exemples négatifs ou qui sont plus générales que d'autres hypothèses de S
  • Mettre à jour G :
    • Si x_i est négatif
      • Spécialiser juste assez les hypothèses de G couvrant x_i pour qu'elles ne couvrent couvrent plus x_i
      • Éliminer les hypothèses de G qui ne couvrent plus des exemples positifs ou qui sont plus spécifiques que d'autres hypothèses de G
    • Si x_i est positif
      • Éliminer les hypothèses de G ne couvrant pas x_i