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, una o más de las hipótesis 1 a n son verdaderas). 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 versiones . [1]
En entornos donde hay un orden de generalidad en 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 concordancia 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 aún 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 concepto verdadero se define solo por los datos positivos ya observados: por lo tanto, si se observa un punto de datos nuevo (nunca antes visto), se debe asumir 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 máximas constituyen esencialmente una afirmación (optimista) de que el concepto verdadero está definido solo por los datos negativos ya observados: por lo tanto, si se observa un punto de datos nuevo (nunca antes visto), se debe asumir que es positivo. (Es decir, si los datos no se han descartado previamente, entonces se incluyen).
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íficos), y las operaciones de aprendizaje pueden realizarse sólo en estos conjuntos representativos.
Después de aprender, se puede realizar una clasificación sobre ejemplos no vistos, 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]
El concepto de espacios de versiones fue introducido por Mitchell a principios de los años 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 de trabajo de espacios 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 vuelve imposible. [1] Una solución a este problema es propuesta por Dubois y Quafafou que propusieron el Espacio de Versión Aproximado, [3] donde se utilizan aproximaciones basadas en conjuntos aproximados para aprender hipótesis ciertas y posibles en presencia de datos inconsistentes.
