Espace de versions - Définition

Concept

La technique des espaces de versions sert à déterminer, dans un espace d'hypothèses, lesquelles peuvent correspondre à un ensemble d'exemple pris dans l'espace des données. Il faut donc commencer par définir l'espace des hypothèses. Cet espace est généralement choisi par les experts. Idéalement, il doit comporter le concept cible, mais ce n'est pas toujours le cas, et il peut être volontairement simplifié ne pas trop compliquer l'algorithme. S'il est trop simplifié, il y a le risque qu'au final aucune hypothèse ne satisfasse l'ensemble d'exemples. Par exemple, pour classer des points en 2D, on peut prendre comme hypothèses les rectangles.

L'espace des versions est l'ensemble des hypothèses qui sont cohérentes avec le jeu d'exemples. Son cardinal peut être très grand, voire infini. L'algorithme ne peut donc pas garder en mémoire l'ensemble de toutes les hypothèses valides. Toutefois, l'espace des hypothèses est partiellement ordonné : si le sous-ensemble de l'espace des données classé positivement par une hypothèse H1 est inclus dans le sous-ensemble de l'espace des données classé positivement par H2, alors H1 est plus spécifique que H2, ou encore, H2 est plus général que H1. Cet espace peut donc être représenté par ses bornes : le G-set, l'ensemble des hypothèses les plus générale qui sont cohérentes avec les exemples connus, et le S-set, l'ensemble des hypothèses les plus spécifiques qui sont cohérentes avec les exemples connus.

La méthode consiste ensuite en une élimination des candidats, par mise à jour de cet espace des versions lors d'ajouts successifs d'exemples. Il faut pour cela des règles de généralisation, lorsqu'un élément du S-set ne classe pas correctement un exemple positif, et de spécialisation lorsqu'un algorithme du G-set ne classe pas correctement un exemple négatif.

Idéalement, l'espace de versions doit converger vers une unique hypothèse. Ceci n'est bien sûr possible que si le concept cible appartient à l'espace des hypothèses.

Exemple

Dans cet exemple, on cherche à déterminer les sports qu'une personne aime regarder. Les paramètres sont le sport, le type (equipe/individuel), le lieu (intérieur/extérieur), le niveau (national/mondial) et le jour. Un exemple est donc un quintuplet, par exemple (football, equipe, extérieur, national, dimanche).

On choisit un espace des hypothèses simples : une hypothèses est une conjonction d'hypothèses sur chaque paramètre. Une hypothèse sur un paramètre impose soit une valeur précise (par exemple "national" pour la paramètre "niveau"), soit n'impose aucune valeur (toutes les valeurs sont bonnes), ce que l'ont note avec un point d'interrogation. Dans cet exemple simple on n'autorise pas les disjonction (par exemple "il fait beau ou nuageux"). Exemple d'hypothèse qui n'accepte que les sports equipe : (?, equipe, ?, ?, ?).

Étape 1 Exemple positif : (football, equipe, extérieur, national, samedi)

• S₁ = {(football,equipe,exterieur,national,samedi)}
• G₁ = {(?,?,?,?,?)}

Étape 2 Exemple positif : (hockey, equipe, extérieur, national, samedi) L'hypothèse du S-set ne couvre pas cet exemple, on doit donc la généraliser.

• S₂ = {(?,equipe,exterieur,national,samedi)}

Les hypothèses du G-set couvrent cet exemple, il n'y a donc rien à modifier.

• G₂ = {(?,?,?,?,?)}

Étape 3 Exemple négatif : (gymnastique, individuel, intérieur, mondial, samedi) Les hypothèses du S-set ne couvrent pas cet exemple, il n'y a donc rien à modifier.

• S₃ = {(?,equipe,exterieur,national,samedi)}

Il faut spécialiser l'hypothèses du G-set pour ne plus inclure cet exemple. Il y a plusieurs solutions possibles, elles sont toutes ajoutées au G-set.

• G₃ = {(?,equipe,?,?,?),(?,?,exterieur,?,?),(?,?,?,national,?)}

Étape 4 Exemple positif : (handball, equipe, intérieur, national, samedi) Les hypothèses du S-set couvrent cet exemple, il n'y a donc rien à modifier.

• S₄ = {(?,equipe,exterieur,national,samedi)}

Une hypothèse du G-set ne couvre pas cet exemple et doit être éliminée.

• G₄ = {(?,equipe,?,?,?),(?,?,?,national,?)}

Étape 5 Exemple négatif : (décathlon, individuel, extérieur, mondial, dimanche) Les hypothèses du S-set ne couvrent pas cet exemple, il n'y a donc rien à modifier.

• S₅ = {(?,equipe,exterieur,national,samedi)}

Les hypothèses du G-set ne couvrent pas cet exemple, il n'y a donc rien à modifier.

• G₅ = {(?,equipe,?,?,?),(?,?,exterieur,?,?),(?,?,?,national,?)}

Dans ce cas nous n'avons pas assez d'exemples pour arriver à une convergences.