Aprendizaje en el espacio de versiones

El aprendizaje en el espacio de versiones es un enfoque lógico para el aprendizaje automático , específicamente para la clasificación binaria . Los algoritmos de aprendizaje en el espacio de versiones buscan en 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 ].}

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

(es decir, una o más de las hipótesis 1 a n son verdaderas). Se presentan ejemplos a un algoritmo de aprendizaje del espacio de versiones, 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 , y el espacio de hipótesis que se mantiene dentro del algoritmo, su espacio de versiones . ^{[ 1 ]}

En entornos donde existe un ordenamiento 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 acuerdo con los datos observados.

Las hipótesis más específicas (es decir, el límite específico SB ) abarcan los ejemplos de entrenamiento positivos observados y la menor parte posible del espacio de características restante. Si estas hipótesis 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 únicamente por los datos positivos ya observados: por lo tanto, si se observa un dato nuevo (nunca antes visto), debe asumirse que es negativo. (Es decir, si los datos no se han incluido previamente, se descartan).

Las hipótesis más generales (es decir, el límite general GB ) abarcan 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. 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 se define únicamente por los datos negativos ya observados: por lo tanto, si se observa un dato nuevo (nunca antes visto), debe asumirse que es positivo. (Es decir, si los datos no se han descartado previamente, se consideran incluidos).

De este modo, 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 únicamente mediante 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 solo sobre estos conjuntos representativos.

Tras el aprendizaje, se puede realizar la clasificación en 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 votación por mayoría. ^{[ 1 ]}

La noción de espacios de versiones 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 dentro del 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 espacios de versiones no es un algoritmo de aprendizaje popular, existen algunas implementaciones prácticas que se han desarrollado (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, que se vuelva vacío, de modo que la clasificación se vuelve imposible. ^{[ 1 ]} Una solución a este problema es propuesta por Dubois y Quafafou, quienes propusieron el Espacio de Versiones Aproximado, ^{[ 3 ]} donde se utilizan aproximaciones basadas en conjuntos aproximados para aprender ciertas hipótesis y posibles en presencia de datos inconsistentes.

• Análisis formal de conceptos
• Programación lógica inductiva
• Conjunto aproximado . [El marco del conjunto aproximado se centra en el caso en que la ambigüedad se introduce por un conjunto de características empobrecido. Es decir, el concepto objetivo no puede describirse de manera concluyente porque el conjunto de características disponible no permite desambiguar objetos que pertenecen a diferentes categorías. El marco del espacio de versiones se centra en el caso (de inducción clásica) en que la ambigüedad se introduce por un conjunto de datos empobrecido . Es decir, el concepto objetivo no puede describirse de manera concluyente porque los datos disponibles no permiten seleccionar de forma unívoca una hipótesis. Naturalmente, ambos tipos de ambigüedad pueden ocurrir en el mismo problema de aprendizaje.]
• Razonamiento inductivo . [Sobre el problema general de la inducción.]

• Hong, Tzung-Pai; Shian-Shyong Tsang (1997). "Un algoritmo generalizado de aprendizaje de espacio de versiones para datos ruidosos e inciertos". IEEE Transactions on Knowledge and Data Engineering . 9 (2): 336– 340. doi : 10.1109/69.591457 . S2CID 29926783 . 
• Mitchell, Tom M. (1997). Aprendizaje automático . Boston: McGraw-Hill.
• Sverdlik, W.; Reynolds, RG (1992). "Espacios de versiones dinámicas en el aprendizaje automático". Actas de la Cuarta Conferencia Internacional sobre Herramientas con Inteligencia Artificial (TAI '92) . Arlington, VA. págs. 308–315 .