Aprenentatge de l'espai de versions

Espai de versions per a un llenguatge d'hipòtesi "rectangle" en dues dimensions. Els avantatges verds són exemples positius i els cercles vermells són exemples negatius. GB és el límit de la hipòtesi positiva màxima general, i SB és el límit de la hipòtesi positiva màxima específica. Els rectangles intermedis (prims) representen les hipòtesis a l'espai de versions.

L'aprenentatge de l'espai de versions és un enfocament lògic de l'aprenentatge automàtic, concretament la classificació binària. Els algorismes d'aprenentatge de l'espai de versions cerquen un espai predefinit d'hipòtesis, vist com un conjunt d'oracions lògiques. Formalment, l'espai d'hipòtesi és una disjunció

$H_{1}\lor H_{2}\lor ...\lor H_{n}$

(és a dir, la hipòtesi 1 és certa, o la hipòtesi 2, o qualsevol subconjunt de les hipòtesis 1 a n). Es presenta un algorisme d'aprenentatge de l'espai de versions amb exemples, que utilitzarà per restringir l'espai d'hipòtesis; per a cada exemple x, les hipòtesis que són inconsistents amb x s'eliminen de l'espai. Aquest perfeccionament iteratiu de l'espai d'hipòtesis s'anomena algorisme d'eliminació de candidats, l'espai d'hipòtesi que manté dins de l'algorisme el seu espai de versions.

L'algoritme de l'espai de versions

En entorns on hi ha un ordre de generalitat en les hipòtesis, és possible representar l'espai de versions mitjançant dos conjunts d'hipòtesis: (1) les hipòtesis consistents més específiques i (2) les hipòtesis consistents més generals, on "consistent" indica acord amb les dades observades.

Les hipòtesis més específiques (és a dir, el límit específic SB) cobreixen els exemples d'entrenament positius observats, i el mínim possible de l'espai de característiques restants. Aquestes hipòtesis, si es redueixen més, exclouen un exemple d'entrenament positiu i, per tant, es tornen inconsistents. Aquestes hipòtesis mínimes constitueixen essencialment una afirmació (pessimista) que el veritable concepte es defineix només per les dades positives ja observades: per tant, si s'observa un punt de dades nou (mai abans vist), s'ha de suposar que és negatiu. (És a dir, si les dades no s'han descartat prèviament, es descarten).

Les hipòtesis més generals (és a dir, el límit general GB) cobreixen els exemples d'entrenament positius observats, però també cobreixen la major part de l'espai de característiques restants sense incloure cap exemple d'entrenament negatiu. Aquests, si s'amplien més, inclouen un exemple d'entrenament negatiu i, per tant, es tornen inconsistents. Aquestes hipòtesis màximes constitueixen essencialment una afirmació (optimista) que el veritable concepte es defineix només per les dades negatives ja observades: per tant, si s'observa un punt de dades nou (mai abans vist), s'ha de suposar que és positiu. (És a dir, si les dades no s'han descartat anteriorment, s'han descartat).

Així, durant l'aprenentatge, l'espai de versions (que en si mateix és un conjunt, possiblement infinit, que conté totes les hipòtesis consistents) es pot representar només pels seus límits inferior i superior (conjunts d'hipòtesis màximament generals i màximament específics), i les operacions d'aprenentatge es poden realitzar només en aquests conjunts representatius.

Després de l'aprenentatge, la classificació es pot realitzar en exemples no vists provant la hipòtesi apresa per l'algorisme. Si l'exemple és coherent amb múltiples hipòtesis, es pot aplicar una regla de vot majoritari.