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).

The most general hypotheses (i.e., the general boundary GB) cover the observed positive training examples, but also cover as much of the remaining feature space without including any negative training examples. These, if enlarged any further, include a negative training example, and hence become inconsistent. These maximal hypotheses essentially constitute a (optimistic) claim that the true concept is defined just by the negative data already observed: Thus, if a novel (never-before-seen) data point is observed, it should be assumed to be positive. (I.e., if data has not previously been ruled out, then it's ruled in.)

Thus, during learning, the version space (which itself is a set – possibly infinite – containing all consistent hypotheses) can be represented by just its lower and upper bounds (maximally general and maximally specific hypothesis sets), and learning operations can be performed just on these representative sets.

After learning, classification can be performed on unseen examples by testing the hypothesis learned by the algorithm. If the example is consistent with multiple hypotheses, a majority vote rule can be applied.^[1]

The notion of version spaces was introduced by Mitchell in the early 1980s^[2] as a framework for understanding the basic problem of supervised learning within the context of solution search. Although the basic "candidate elimination" search method that accompanies the version space framework is not a popular learning algorithm, there are some practical implementations that have been developed (e.g., Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).

A major drawback of version space learning is its inability to deal with noise: any pair of inconsistent examples can cause the version space to collapse, i.e., become empty, so that classification becomes impossible.^[1] One solution of this problem is proposed by Dubois and Quafafou that proposed the Rough Version Space,^[3] where rough sets based approximations are used to learn certain and possible hypothesis in the presence of inconsistent data.

• Formal concept analysis
• Inductive logic programming
• 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 .