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, Valido/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 hipotesis h₁ > _gh₂ si h₁ es más general que h₂.

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

Orden de generalidad

De forma concreta una tupla es más específica que otra si contiene un mayor número de valores concretos o (Ø). O lo que es lo mismo, la que contiene el menor número interrogaciones representado cualquier valor posible.

El algoritmo

Sea G el conjunto de elementos de máxima generalidad de H.
Sea S el conjunto de elementos de máxima especificidad de H.

Para cada ejemplo d del conjunto de entrenamiento D:

   Si d es un ejemplo positivo, entonces:
      Eliminar de G cualquier hipótesis inconsistente con d.
      Para cada hipótesis s de S inconsistente con d:
         Eliminar s de S.
         Incluir en S todas las generalizaciones minimales h de s, tales que h
          es consistente con d y existe una hipótesis en G más general que h.
         Eliminar de S aquellas hipótesis tales que exista en S otra hipótesis
          más específica.

   Si d es un ejemplo negativo, entonces:
      Eliminar de S cualquier hipótesis consistente con d.
      Para cada hipótesis g de G consistente con d:
         Eliminar g de G.
         Incluir en G todas las especializaciones minimales h de g, tales que h
           es consistente con d y existe una hipótesis en S más específica que h.
         Eliminar de G aquellas hipótesis tales que exista en G otra hipótesis
            más general.

Generalizaciones y especializaciones

La hipótesis más específica es aquella conformada por toda la tupla a Ø La hipótesis más general es aquella conformada por toda la tupla a ?

Las generalizaciones minimales consisten en realizar los siguientes cambios en cada tupla de S

• Si el atributo de la hipótesis es Ø y el del ejemplo contiene un valor entonces se cambia por el del valor del ejemplo
• Si en cambio la hipótesis contiene un valor distinto a Ø y el del ejemplo otro valor distinto entonces se modifica por una ?

Las especializaciones minimales consisten en realizar los siguientes cambios en G

• Se crean nuevas tuplas por cada atributo que su valor ha permanecido constante.

Clasificación de nuevas instancias

• Si es consistente con todo S, positivo
• Si no es consistente con ninguno de G, negativo
• En otro caso, voto mayoritario

Un ejemplo

Paso 0: S0 = {< ∅, ∅, ∅, ∅, ∅, ∅ >}, G0 = {<?, ?, ?, ?, ?, ? >}

Paso 1:

• Ejemplo positivo: < Sol, Templ, Normal, Fuerte, Templ, Igual >
• Nada que eliminar de G0
• Generalización minimal de S0: < Sol, Templ, Normal, Fuerte, Templ, Igual >

Esta generalización es más específica que la hipótesis de G0

• Luego:

S1 = {< Sol, Templ, Normal, Fuerte, Templ, Igual >} G1 = {<?, ?, ?, ?, ?, ? >}

Paso 2:

• Ejemplo positivo: < Sol, Templ, Alta, Fuerte, Templ, Igual >
• Nada que eliminar de G1
• Generalización minimal de S1: < Sol, Templ, ?, Fuerte, Templ, Igual >

Esta generalización es más específica que la hipótesis de G1

• Luego:

S2 = {< Sol, Templ, ?, Fuerte, Templ, Igual >} G2 = {<?, ?, ?, ?, ?, ? >}

Paso 3:

• Ejemplo negativo: < Lluvia, Fria, Alta, Fuerte, Templada, Cambio >
• Nada que eliminar de S2.
• Especializaciones minimales de G2 que son más generales que la hip´otesis

de S2: < Sol, ?, ?, ?, ?, ? >, <?, Templ, ?, ?, ?, ? > y <?, ?, ?, ?, ?, Igual >.

• Luego:

S3 = {< Sol, Templ, ?, Fuerte, Templ, Igual >} G3 = {< Sol, ?, ?, ?, ?, ? >, <?, Templ, ?, ?, ?, ? >, <?, ?, ?, ?, ?, Igual >}

Paso 4:

• Ejemplo positivo: < Sol, Templ, Alta, Fuerte, Fria, Cambio >
• Eliminamos de G3 la hipótesis <?, ?, ?, ?, ?, Igual >
• Generalización minimal de S3: < Sol, Templ, ?, Fuerte, ?, ? >

Esta generalización es más específica que hipótesis de G3.

• Luego:

S4 = {< Sol, Templ, ?, Fuerte, ?, ? >} G4 = {< Sol, ?, ?, ?, ?, ? >, <?, Templ, ?, ?, ?, ? >}

Véase también

• Algoritmo find-s
• Algoritmo id3
• Algoritmo de cobertura
• FOIL

Bibliografía

• Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)

Enlaces externos

• Aprendizaje Conceptual