Hipótesis y ejemplos

• Dado un predicado objetivo Q cada hipótesis propone una definición candidata Ci de ese predicado. Cada Hipótesis Hi es de la forma . Por ejemplo

  

  

  

  

• H es el espacio de estados {H1, ..., Hn}

  El algoritmo de aprendizaje supone que una de esas hipótesis es correcta, es decir, cree

• La extensión de una hipótesis es el conjunto de ejemplos que predice. Dos hipótesis son inconsistentes si sus extensiones son distintas. Un ejemplo es inconsistente con una hipótesis si no pertenece a la extensión de esa hipótesis
• Un ejemplo Xi se describe con la sentencia Di(Xi) y se clasifica con la sentencia Q(Xi) si es un ejemplo positivo, not Q(Xi) si es un ejemplo negativo. Así el ejemplo X1 se describe con

  

  y se clasifica

• Inconsistencia de hipótesis y ejemplos
  • falso negativo: la hipótesis dice que debe ser negativo pero realmente es positivo

    En el ejemplo de una espera de 0-10 minutos y el restaurante lleno, la hipótesis Hr predice y el ejemplo dice

  • falso positivo: la hipótesis dice que debe ser positivo pero realmente es negativo
• El problema del aprendizaje inductivo es por tanto el de eliminar hipótesis inconsistente con los ejemplos. Describiremos el primer algoritmo de aprendizaje de este tipo debido a Patrick Winston