Aprendizaje Inductivo

El aprendizaje inductivo puede verse como el proceso de aprender una función. Por ejemplo, en aprendizaje supervisado, al elemento de aprendizaje se le dá un valor correcto (o aproximadamente correcto) de una función a aprender para entradas particulares y cambia la representación de la función que está infiriendo, para tratar de aparear la información dada por la retroalimentación que ofrecen los ejemplos.

Un ejemplo es un par $(\mathbf{x},f(\mathbf{x}))$, donde $\mathbf{x}$ es la entrada (que generalmente es un vector) y $f(\mathbf{x})$ la salida. El proceso de inferencia inductiva pura (o inducción) es: dada una colección de ejemplos de $f$, regresar una función $h$ tal que se aproxime a $f$. A la función $h$ se le llama la hipótesis.

En principio existen muchas posibilidades para escoger $h$, cualquier preferencia se llama bias o sesgo. Todos los algoritmos de aprendizaje exhiben algún tipo de sesgo.

La selección de una representación para la función deseada es probablemente el factor más importante en el diseño de un sistema de aprendizaje.

Desde un punto de vista más tradicional (hablando de representaciones simbólicas/reglas,...), podemos decir que una buena parte de ML está dedicada a inferir reglas a partir de ejemplos. Descripciones generales de clases de objetos, obtenidas a partir de un conjunto de ejemplos, pueden ser usadas para clasificar o predecir.

En general, el interes no está en aprender conceptos de la forma en que lo hacen los humanos, sino aprender representaciones simbólicas de ellos.

Angluin y Smith listan cinco elementos que deben de especificarse para caracterizar un problema de inferencia inductiva:

  1. La clase de reglas
  2. El espacio de hipótesis
  3. El conjunto de ejemplos y su presentación
  4. La clase del método de inferencia
  5. El criterio de éxito

La clase de reglas:

La clase de reglas denota la clase de funciones o lenguaje bajo consideración. Por ejemplo, todas las expresiones regulares sobre un alfabeto específico, lenguajes libres de contexto, funciones recursivamente enumerables, programas en Prolog, etc.

El espacio de hipótesis:

El espacio de hipótesis es el conjunto de descripciones tal que cada regla en la clase tiene por lo menos una descripción en el espacio de hipótesis. Diferentes espacios de hipótesis pueden usarse para la misma clase de reglas.

El lenguaje de hipótesis debe de tener descripciones para todas las reglas en la clase, pero puede contener más.

Por conveniencia, normalmente se asume que el lenguaje descrito por el espacio de hipótesis (i.e., el lenguaje de hipótesis) es el mismo que el de la clase de reglas:

El lenguaje de hipótesis determina el espacio de hipótesis del cual el método de inferencia selecciona sus reglas. El lenguaje impone ciertas restricciones (o preferencias) en lo que puede ser aprendido y qué estrategias de razonamiento son permitidas. Al escoger un lenguaje, debemos de considerar no sólo lo que queremos que el sistema realice, sino también qué información se le debe de proporcionar al sistema de entrada para permitirle resolver el problema, y si lo va a resolver a tiempo.

Al igual que en los mecanismos de razonamiento utilizados para representar conocimiento, aquí existe un balance fundamental entre la expresividad y la eficiencia (ver figura 1.7 y 1.8).

Figura 1.7: El espacio de hipótesis depende de la expresividad del lenguaje.
\begin{figure}\centerline{\hbox{
\psfig{figure=espaciohipo2.ps,height=12cm}
}}
\end{figure}

Figura 1.8: Qué tan bien se ajusta el modelo depende de la expresividad del lenguaje.
\begin{figure}\centerline{\hbox{
\psfig{figure=espaciohipo1.ps,height=5cm}
}}
\end{figure}

El lenguaje de hipótesis depende del área de aplicación. Una vez definido, una buena parte del tiempo de desarrollo se dedica a seleccionar cuidadosamente las estructuras de conocimiento adecuadas para la tarea de aprendizaje.

Este tiempo se vuelve más crítico cuando el lenguaje de hipótesis restringe la expresividad de tal forma que el conocimiento del dominio tiene que adaptarse al formalismo adoptado.

El proceso de indución puede verse como una búsqueda de hipótesis o reglas.

El espacio puede buscarse sistemáticamente, hasta encontrar la regla adecuada. Dado un espacio de hipótesis particular, podemos tener una enumeración de descripciones, digamos $d_1, \ldots,
d_n$, tal que cada regla en el espacio de hipótesis tiene una o más descripciones en esta enumeración.

Dada una colección de ejemplos, identificación en el límite recorre esta lista encontrando la primera descripción, digamos $d_{i}$, que es compatible con los ejemplos vistos y conjetura a $d_{i}$.

Este método a pesar de ser poderoso y general es impráctico, para todos exceptuando un número limitado de casos, debido al tamaño del espacio de búsqueda.

Para que el aprendizaje puede realizarse en forma eficiente, es normalmente crucial estructurar el espacio de hipótesis. Esto se puede hacer con un modelo de generalización.

A grandes razgos una regla $R_{1}$ es más general que otra regla $R_{2}$ (o $R_{2}$ es más específica que $R_{1}$), si en cualquier mundo $R_{1}$ puede mostrar los mismos resultados que $R_{2}.$

Esta estructuración permite cortar ramas durante la búsqueda sabiendo que especializaciones o generalizaciones de reglas hereden alguna propiedad.

Las propiedades más comunes son: incapacidad de cubrir un ejemplo conocido como verdadero o probar un ejemplo conocido como falso.

Conjunto de ejemplos y su presentación:

Existen diferentes tipos de presentación de datos y sus efectos en la inferencia de lenguajes.

Los ejemplos pueden dar una retroalimentación directa o indirecta. Por ejemplo, al aprender a jugar un cierto juego, la retroalimentación se puede dar en cada jugada o al final del juego o después de un conjunto de jugadas que provocaron una pérdida de material, etc. Aquí, surge el problema de asignación de crédito (cuál jugada es responsable del éxito o fracaso).

Una presentación puede consistir en: (i) sólo ejemplos positivos y (ii) positivos y negativos.

Casi todos los algoritmos requieren presentaciones admisibles, esto es, para cada regla falsa que es consistente con los ejemplos positivos, existe un ejemplo negativo que la refuta (se relaciona con Popper: Las teorías deben de ser refutables con hechos).

Los ejemplos se usan para probar y formar hipótesis. En la práctica una selección de ejemplos se hace sobre el espacio de ejemplos.

Esta selección puede hacerla un: oráculo, el medio ambiente, seleccionada en forma aleatoria, propuesta por el sistema.

Una ``buena'' selección de ejemplos puede mejorar el desempeño de un sistema (ver por ejemplo Active Learning).

A veces esa selección puede mejorarse con conocimiento del dominio.

Es deseable que la distribución que sigan los ejemplos sea similar a la que van a tener ejemplos futuros.

Finalmente, si el sistema es quién tiene el control sobre cuándo experimentar situaciones novedosas o no, entonces se tiene el problema de formar un balance entre exploración y explotación.

Métodos de inferencia:

Intuitivamente un método de inferencia es un proceso computacional de algún tipo que lee ejemplos y produce hipótesis del espacio de hipótesis.

Existe una gran cantidad de métodos. Algunos realizan ajustes graduales en base a refuerzos sobre predicciones sucesivas (e.g., aprendizaje por refuerzo, redes neuronales, regresión, etc.). Otros construyen incrementalmente hipótesis tratando de cubrir la mayor parte de un conjunto de ejemplos (e.g., reglas de clasificación, programas lógicos) o en base a mejores particiones de ejemplos (e.g., árboles de decisión). Otros, guardan ejemplos prototípicos (e.g., aprendizaje basado en casos y aprendizaje basado en instancias). Algunos buscan relaciones entre variables (e.g., redes Bayesianas). Finalmente, algunos algoritmos combinan o modifican hipótesis promisorias (e.g., algoritmos genéticos).

Criterio de éxito:

Un componente importante dentro de la especificación de un problema de inferencia es el criterio de éxito. Identificación en el límite es uno de ellos, sin embargo, normalmente es difícil saber cuándo el método ha convergido.

Recientemente Valiant, propuso un criterio de identificación correcta de una regla a partir de ejemplos usando un criterio estocástico.

La idea es que después de un muestreo aleatorio de ejemplos positivos y negativos de una regla, un procedimiento de identificación debe de producir una regla que con ``alta probabilidad'' no sea ``muy diferente'' de la regla correcta.

Esto se basa en dos parámetros: $\epsilon$ y $\delta$. $\epsilon$ es una medida de tolerancia o un límite de la diferencia permitida entre la regla correcta y la hipótesis generada. $\delta$ es una medida de confianza.

Informalmente, un procedimiento de identificación se dice ser probablemente aproximadamente correcto o PAC si la diferencia entre la regla correcta y la hipótesis es menos que $\epsilon$ con probabilidad mayor a $1 - \delta$.

En la práctica queremos ciertas garantias de la calidad de la hipótesis.

Las más comunes son que sea completo y consistente (ver figura 1.9):

A veces el usuario determina el criterio de paro. Si el sistema genera sus propios ejemplos, éste lo determina.

Figura 1.9: Completo y Consistente (X positivos y O negativos).
\begin{figure}\centerline{\hbox{
\psfig{figure=complcorrec.ps,height=10cm}
}}
\end{figure}

emorales 2012-01-23