Pac Learning vs. Learning On Uniform Distribution

Question

La clase de función $ \ mathcal {f} $ es PAP: aprende si existe un algoritmo $ A $ de tal manera que para CUALQUIER DISTRIBUCION $ D $ , cualquier función desconocida $ f $ y cualquier $ \ epsilon, \ delta $ sostiene que existe $ m $ tal que en una entrada de $ m $ iid muestras $ (x, f (x)) $ donde < span class="math-contenedor"> $ x \ sim d $ , $ a $ devueltos, con probabilidad más grande que $ 1- \ Delta $ , una función que es $ \ epsilon $ -close to $ f $ (con respecto a $ d $ ). La clase $ \ mathcal {f} $ es eficientemente PAAC aprende fácilmente si es PAP HECKABLE, y $ a $ Ejecute en el tiempo $ \ texto {poly} (1 / \ epsilon, 1 / \ delta, n) $ (donde $ | x |= n $ ) y la descripción de $ f $ .

¿Hay un caso en el que una clase $ \ mathcal {f} $ no es eficientemente PAAC apreciable, sin embargo, es eficientemente apreciable en la distribución uniforme?

Answer 1

¿Hay un caso en el que una clase $ \ mathcal {f} $ no es eficientemente PAAC apreciable, sin embargo, es eficientemente apreciable en la distribución uniforme?

Esto se ha preguntado en Tcs.se . Parece que la respuesta corta es SÍ - Aaron Roth le da el ejemplo de ancho- $ k $ conjunciones para $ k \ gg \ log n $ . Y en los comentarios, Avrim Blum se cita como la respuesta de $ 2 $ -term dnf.

No entiendo totalmente los ejemplos allí: debe tomar un poco más de trabajo para obtener realmente el resultado (actualizaré esta respuesta si encuentro una prueba autocontenida). Pero el problema general aquí con la distribución uniforme es que si la función objetivo $ f $ es "escasa", lo que significa que las etiquetas en la mayoría de un $ \ delta $ fracción de la distribución de entrada con $ 1 $ , entonces es fácil aprender simplemente adivinando $ 0 $ .

---

Más allá del aprendizaje de PAC solo eficiente (polinomial), hay otros ejemplos en los que la distribución uniforme parece ayudar. Por ejemplo, un problema difícil clásico para el aprendizaje de PAC es DNF, un problema que se conyecta a NO PAP apreciable y bastante difícil. Por otro lado, DNF sobre la distribución de uniformes es casi PAP apreciable: tenemos un algoritmo de tiempo polinomial QAUSI para ello. Consultela estas notas y estas notas .

En resumen, parece que hay mucho trabajo en el aprendizaje bajo la distribución uniforme (búsqueda "PAC Learning en Distribución uniforme" para referencias adicionales). Y parece que este problema es más fácil que estudiar el aprendizaje de PAC, donde no podemos demostrar mucho. Citando las notas de Ryan O'Donnell arriba:

El aprendizaje del PAP general insiste en que un algoritmo funciona simultáneamente para todas las distribuciones. De hecho, la comunidad de aprendizaje de la máquina interesada en las aplicaciones del mundo real encuentra que el entorno uniforme es cuestionable: "Te golpearán en la nariz si intentas contarles sobre algoritmos en este Marco. "--ryan. Pero, en un marco más general, nadie realmente puede probar nada.