En la teoría del aprendizaje computacional, el aprendizaje Ockham (u Occam) es un modelo de aprendizaje algorítmico en el que el objetivo del alumno es obtener una representación sucinta de los datos de entrenamiento recibidos.
Está estrechamente relacionado con el aprendizaje probablemente aproximadamente correcto (PAC), en el que el alumno se evalúa en función de su poder predictivo de un conjunto de pruebas.
El aprendizaje Ockham debe su nombre a la navaja de Ockham, un principio según el cual, en igualdad de condiciones, una explicación más corta de los datos observados debería ser preferible a una explicación más larga.
La teoría del aprendizaje de Occam es una justificación formal y matemática de este principio.
s i z e ( c )
sean clases de conceptos que contienen conceptos objetivo e hipótesis, respectivamente.
es la longitud máxima de cualquier muestra
s i z e ( c ) .
( n ⋅ s i z e ( c )
Una formulación ligeramente más general es la siguiente: Tenemos
sea un algoritmo tal que, dando
muestras extraída de una distribución fija pero desconocida
≤ b ϵ m − log
Aunque los teoremas anteriores muestran que el aprendizaje Ockham es suficiente para el aprendizaje PAC, no dicen nada sobre la necesidad.
Board y Pitt demuestran que, para una amplia variedad de clases conceptuales, el aprendizaje Ockham es de hecho necesario para el aprendizaje PAC.
[3] Demostraron que para cualquier clase conceptual que sea polinomialmente cerrada bajo listas de excepciones, el aprendizaje PAC implica la existencia de un algoritmo Ockham para esa clase conceptual.
Las clases conceptuales que son polinomialmente cerradas bajo listas de excepciones incluyen fórmulas booleanas, circuitos, autómatas finitos deterministas, listas de decisión, árboles de decisión y otras clases conceptuales definidas geométricamente.
de forma tal que, cuando se le da la representación de un concepto
excepciones genera una representación de un concepto
Primero probamos la versión de la cardinalidad.
Con esto concluye la demostración del segundo teorema anterior.
Utilizando el segundo teorema, podemos demostrar el primero.
esto significa que cualquier hipótesis emitida por
( n ⋅ s i z e ( c )
≤ ( n ⋅ s i z e ( c )
{\displaystyle \log |{\mathcal {H}}_{n,m}|\leq (n\cdot size(c))^{\alpha }m^{\beta }}
( n ⋅ s i z e ( c )
Con esto concluye la demostración del primer teorema anterior.
Aunque el aprendizaje de Ockham y PAC son equivalentes, el marco de Ockham puede utilizarse para producir límites más ajustados en la complejidad muestral de problemas clásicos, incluyendo conjunciones,[2] conjunciones con pocas variables relevantes,[4] y listas de decisión.
[5] Los algoritmos de Ockham también han demostrado tener éxito para el aprendizaje PAC en presencia de errores,[6][7] conceptos probabilísticos,[8] aprendizaje de funciones[9] y ejemplos markovianos no independientes.