Aprendizaje adecuado de PAC de 2-DNF bajo distribución uniforme

10

¿Cuál es el resultado del estado del arte sobre la complejidad de las consultas de las fórmulas de aprendizaje 2-DNF PAC adecuadas con consultas de muestra y bajo distribución uniforme ? ¿O alguna atadura no trivial?

Debido a que no estoy familiarizado con la teoría del aprendizaje y esta pregunta está motivada por un campo diferente, la respuesta podría ser obvia. Revisé el libro de Kearns y Vazirani, pero no parecen considerar esta configuración explícitamente.

upd Aunque el parámetro principal de interés es la complejidad de la consulta, el tiempo de ejecución también es importante. Si es posible, el tiempo de ejecución debe ser aproximadamente el mismo que la complejidad de la consulta o, como máximo, polinomio.

upd El Apéndice B (parte superior de la página 18) del documento "Aprendizaje de las funciones submodulares" de Balcan y Harvey menciona que "es bien sabido que los 2-DNF son eficientes para aprender PAC". Sin embargo, no mencionan si este resultado es para un aprendizaje adecuado o si da alguna referencia.

Grigory Yaroslavtsev
fuente
¿Qué tipo de consultas?
Timothy Sun
Solo muestras. También supongo que debería ser explícito que la pregunta es sobre la complejidad de la consulta, no el tiempo de ejecución (editado).
Grigory Yaroslavtsev
He respondido a su pregunta, suponiendo que las consultas de muestra son solo ejemplos aleatorios (y no consultas de membresía).
Lev Reyzin
1
Sí, las consultas son solo ejemplos aleatorios de distribución uniforme.
Grigory Yaroslavtsev

Respuestas:

14

No sé si considerarás lo siguiente como un límite no trivial, pero aquí voy.

ckcx1,,xni=1k(i,1i,2...i,c)1ik1jci,j{x1,,xn,x¯1,,x¯n}

ccn2c(nc)|H|=22c(nc)H

Imagine un algoritmo que toma muestras y luego prueba todos loshipótesis hasta que encuentre una que prediga perfectamente sobre las muestras. El teorema Razor de Occam dice que solo necesita tomar aproximadamente muestras para este algoritmo para encontrar un objetivo con error con probabilidad .m|H|m=O(1ϵ|(H|+1δ)ϵ1δ

En nuestro caso, para , , lo que significa que necesitará aproximadamente muestras para hacer el aprendizaje (adecuado).c=2lg|H|=O(n2)n2

Pero todo el juego en el aprendizaje no es realmente una complejidad de muestra (aunque eso es parte del juego, especialmente en el aprendizaje eficiente de atributos), sino más bien en el intento de diseñar algoritmos de tiempo polinomial. Si no le importa la eficiencia, entonces es la respuesta más simple para la complejidad de la muestra PAC.n2

ACTUALIZACIÓN (dada la pregunta modificada) :

Debido a que usted declaró explícitamente que solo le importaba la complejidad de la muestra, presenté el algoritmo de fuerza bruta de Occam, que es probablemente el argumento más simple. Sin embargo, mi respuesta fue un poco tímida. -DNF son realmente aprendibles en tiempo polinómico! Este es el resultado del artículo original de Valiant, " A Theory of the Learnable ". De hecho, -DNF se puede aprender para cualquier .2cc=O(1)

El argumento es el siguiente. Puede ver un -DNF como una disyunción de "meta-variables" e intentar aprender la disyunción eliminando las meta-variables inconsistentes con los ejemplos. Dicha solución se puede traducir fácilmente a una solución "adecuada", y lleva tiempo . Como nota al margen, todavía está abierto si existe un algoritmo de tiempo polinómico para .cncO(nc)c=ω(1)

En cuanto a si la complejidad de la muestra también es un límite inferior, la respuesta es bastante sí. Este artículo de Ehrenfeucht et al. muestra que el límite de Occam es casi apretado.n2

Lev Reyzin
fuente
1
¡Gracias! Este es un resultado no trivial: no me di cuenta de que el tiempo de ejecución exponencial será útil. Sin embargo, para la aplicación que tengo en mente, el tiempo polinómico es mucho más deseable (se actualizó la pregunta). ¿Es el enfoque que describió el más conocido para este problema? ¿Hay límites inferiores en la complejidad de la consulta (incluso para un tiempo de ejecución ilimitado)?
Grigory Yaroslavtsev
Se actualizó la pregunta con una referencia que la motivó.
Grigory Yaroslavtsev
1
actualizó la respuesta dada su pregunta actualizada
Lev Reyzin
Además, en este caso, no creo que el tiempo de ejecución exponencial sea útil. Pero en general, parece ser. El aprendizaje (con una complejidad de muestra óptima) suele ser fácil cuando tienes tiempo exponencial.
Lev Reyzin
2
¡Muchas gracias! Necesitaré algo de tiempo para verificar las referencias, pero hasta ahora parece ser una respuesta completa.
Grigory Yaroslavtsev