El algoritmo de Winston

• El algoritmo mantiene la mejor hipótesis y la ajusta según llegan nuevos ejemplos para conservar la consistencia
• Si hasta el momento se tiene la hipótesis Hr y llega un nuevo ejemplo consistente con la hipótesis no se necesita hacer nada. Sin embargo si es inconsistente tendremos dos casos:
  • El ejemplo es un falso negativo (la hipótesis dice que es negativo pero realmente es positivo). Debe incrementarse la extensión de la hipótesis para incluirlo (Generalización)
  • El ejemplo es un falso positivo (la hipótesis dice que es positivo pero realmente es negativo). Debe decrementarse la extensión de la hipótesis para excluirlo (Especialización)
• Obsérvese en el seudocódigo que el algoritmo se ha descrito de manera no determinista ya que en cualquier punto puede haber varias posibles generalizaciones o especializaciones aplicables. La elección no necesariamente llevará a la hipótesis más sencilla; incluso puede ocurrir que lleguemos a una situación en que ninguna modificación sencilla de la hipótesis la haga consistente con todos los ejemplos. En ese punto será necesario un backtracking (vuelta atrás) al punto de elección
• La generalización y la especialización son operaciones que modifican la extensión de una hipótesis. Para implementarlas nos fijamos en que también son relaciones lógicas entre hipótesis. Si H1, que tiene definición C1, es una generalización de H2, que tiene definición C2, entonces

  

• Ejemplo de funcionamiento
  • X1 es positivo, Alternate(X1) es cierto. Supongamos entonces una hipótesis inicial

    

  • X2 es un falso positivo. Necesitamos una especialización de H1 que descarte X2, por ejemplo

    

  • X3 es un falso negativo. Necesitamos una generalización que lo incluya, por ejemplo eliminando una parte de la conjunción

    

  • X4 es un falso negativo. Necesitamos una generalización que lo incluya, por ejemplo añadiendo una disyunción

    

• Dificultades del algoritmo de Winston
  • hay que comprobar que cada modificación es consistente con todos los ejemplos
  • es difícil encontrar una buena heurística para elegir la mejor modificación y el backtracking es muy costoso

    (algoritmo del espacio de versiones de Mitchell)

• Ya a finales de los 70 el algoritmo de Winston se aplicó en Meta-Dendral, un sistema para la predicción de resultados de espectometría. Generó conocimiento que fue publicado en una revista de química analítica