El aprendizaje del espacio de versiones es un enfoque lógico del aprendizaje automático , específicamente de la clasificación binaria . Los algoritmos de aprendizaje del espacio de versiones buscan un espacio predefinido de hipótesis , visto como un conjunto de oraciones lógicas . Formalmente, el espacio de hipótesis es una disyunción [1]
(es decir, la hipótesis 1 es verdadera, o la hipótesis 2, o cualquier subconjunto de las hipótesis 1 a n ). Se presenta un algoritmo de aprendizaje del espacio de versiones con ejemplos, que utilizará para restringir su espacio de hipótesis; para cada ejemplo x , las hipótesis que son inconsistentes con x se eliminan del espacio. [2] Este refinamiento iterativo del espacio de hipótesis se denomina algoritmo de eliminación de candidatos , el espacio de hipótesis mantenido dentro del algoritmo, su espacio de versión . [1]
En entornos donde existe un orden general de las hipótesis, es posible representar el espacio de versiones mediante dos conjuntos de hipótesis: (1) las hipótesis consistentes más específicas y (2) las hipótesis consistentes más generales , donde "consistente" indica acuerdo con los datos observados.
Las hipótesis más específicas (es decir, el límite específico SB ) cubren los ejemplos de entrenamiento positivos observados y la menor cantidad posible del espacio de características restante. Estas hipótesis, si se reducen más, excluyen un ejemplo de entrenamiento positivo y, por lo tanto, se vuelven inconsistentes. Estas hipótesis mínimas constituyen esencialmente una afirmación (pesimista) de que el verdadero concepto se define sólo por los datos positivos ya observados: por lo tanto, si se observa un dato nuevo (nunca antes visto), se debe suponer que es negativo. (Es decir, si los datos no se han descartado previamente, entonces se descartan).
Las hipótesis más generales (es decir, el límite general GB ) cubren los ejemplos de entrenamiento positivos observados, pero también cubren la mayor parte del espacio de características restante sin incluir ningún ejemplo de entrenamiento negativo. Estos, si se amplían aún más, incluyen un ejemplo de entrenamiento negativo y, por lo tanto, se vuelven inconsistentes. Estas hipótesis maximales constituyen esencialmente una afirmación (optimista) de que el verdadero concepto se define sólo por los datos negativos ya observados: por lo tanto, si se observa un dato nuevo (nunca antes visto), se debe suponer que es positivo. (Es decir, si los datos no se han descartado previamente, entonces se descartan).
Así, durante el aprendizaje, el espacio de versiones (que en sí mismo es un conjunto – posiblemente infinito – que contiene todas las hipótesis consistentes) puede representarse sólo por sus límites inferior y superior (conjuntos de hipótesis máximamente generales y máximamente específicas), y las operaciones de aprendizaje pueden realizarse simplemente en estos conjuntos representativos.
Después del aprendizaje, la clasificación se puede realizar en ejemplos invisibles probando la hipótesis aprendida por el algoritmo. Si el ejemplo es consistente con múltiples hipótesis, se puede aplicar una regla de voto mayoritario. [1]
La noción de espacios de versión fue introducida por Mitchell a principios de la década de 1980 [2] como un marco para comprender el problema básico del aprendizaje supervisado en el contexto de la búsqueda de soluciones . Aunque el método básico de búsqueda de " eliminación de candidatos " que acompaña al marco del espacio de versiones no es un algoritmo de aprendizaje popular, se han desarrollado algunas implementaciones prácticas (por ejemplo, Sverdlik y Reynolds 1992, Hong y Tsang 1997, Dubois y Quafafou 2002).
Una desventaja importante del aprendizaje del espacio de versiones es su incapacidad para lidiar con el ruido: cualquier par de ejemplos inconsistentes puede hacer que el espacio de versiones colapse , es decir, quede vacío, de modo que la clasificación se vuelva imposible. [1] Dubois y Quafafou proponen una solución a este problema, quienes propusieron el espacio de versión aproximada, [3] donde se utilizan aproximaciones basadas en conjuntos aproximados para aprender hipótesis ciertas y posibles en presencia de datos inconsistentes.
