Algoritmo de eliminación de candidatos

El algoritmo de eliminación de candidatos es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de hipótesis o conceptos en él dado un conjunto de ejemplos de entrenamiento. Este algoritmo se puede expresar como una extensión del algoritmo find-s.

El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores, cada uno de ellos denominados atributos. Adicionalmente uno de los atributos ha de ser de tipo binario ( Si/No, Cierto/Falso, Válido/Invalido ), el cual es el atributo objetivo a clasificar que diferencia el concepto. De esta forma el algoritmo trata de obtener un intervalo de hipótesis flanqueadas por un límite más específico y un límite más general de forma que las nuevas instancias se consideran consistentes con el intervalo aprendido si están dentro de él.

Una vez obtenida el intervalo de hipótesis se puede determinar si una nueva instancia la cumple.

Eliminación de candidatos realiza esta labor tomando una tupla de valores con el mismo número de atributos, menos el del atributo objetivo, que los de entrenamiento. Pero de forma adicional define un nuevo tipo de valores que puede adoptar un atributo.

  • Ø que representa ningún valor. Este es el valor más específico posible.
  •  ? que representa cualquier valor. Este es el valor más general posible.

Espacio de versiones

El intervalo de hipótesis se denomina espacio de versiones. Para el correcto funcionamiento del algoritmo se define un orden de generalidad. de forma que dos hipótesis si es más general que .

Los límites del intervalo se denominan Cota general (G) y Cota específica (S). Estos son conjuntos de tuplas.

Other Languages