Aprendizaje agnóstico sobre distribuciones arbitrarias

$D$ $\{0,1\}^d\times \{0,1\}$ $C$ $f:\{0,1\}^d\rightarrow\{0,1\}$ $f \in C$

e r r (f, D) = \underset{(x, y) \sim D}{Pr} [f (x) \neq y]

$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$

O P T (C, D) = min_{f \in C} e r r (f, D)

$OPT(C,D) = \min_{f \in C}\ err(f,D)$ Digamos que un algoritmo

A

$A$ aprende agnósticamente

C

$C$ sobre cualquier distribución, si para cualquier

D

$D$ puede con una probabilidad

2 / 3

$2/3$ encontrar una función

f

$f$ tal que

e r r (f, D) \leq O P T (C, D) + ϵ

$err(f,D) \leq OPT(C,D) + \epsilon$ , dado el tiempo y un número de muestras de

D

$D$ que está limitado por un polinomio en

d

$d$ y

1 / ϵ

$1/\epsilon$ .

Pregunta: ¿Qué clases de funciones $C$ se sabe que se pueden aprender agnósticamente sobre distribuciones arbitrarias?

¡Ninguna clase es demasiado simple! Sé que ni siquiera se sabe que las conjunciones monótonas se pueden aprender agnósticamente sobre distribuciones arbitrarias, así que solo estoy buscando clases de funciones no triviales.

reference-request machine-learning lg.learning Aaron Roth
fuente

Vale la pena señalar para los no iniciados que el aprendizaje agnóstico se centra en el caso cuando OPT (C, D)> 0 (es decir, tiene la clase de hipótesis incorrecta

Suresh Venkat

Buen punto. En el caso especial cuando OPT (C, D) = 0, este es el aprendizaje PAC, y es mucho más fácil. Para el aprendizaje agnóstico, la garantía debe mantenerse sin importar qué OPT (C, D) sea.

Aaron Roth el

También está el caso "PAC con ruido de clasificación" donde OPT (C, D)> 0, y aunque tiene la clase de hipótesis correcta (configuración realizable) hay algún error porque las etiquetas se voltean al azar debido al ruido ... I Desearía que los nombres de las diferentes configuraciones fueran menos confusos.

Lev Reyzin

eso suena como un aprendizaje agnóstico con un límite superior en OPT (C, D)

Suresh Venkat

No del todo, porque no se permite que el ruido sea arbitrario en el modelo de clasificación de ruido. Entonces, si hubo algún patrón de ruido de confrontación que dificultó el aprendizaje (o encontrar el minimizador de riesgo empírico) en el modelo agnóstico, podría no ocurrir a menudo en el modelo de ruido de clasificación (es decir, caer en el parámetro delta PAC).

Lev Reyzin

Respuestas:

Si ninguna clase es demasiado simple, aquí hay algunas clases aprendibles de PAC agnósticamente. En respuesta a los comentarios, se tachan las clases con muchas hipótesis polinómicas:

~~árboles de decisión de profundidad constante (y otras clases que solo tienen muchas hipótesis)~~
~~hiperplanos en (solo hipótesis producen etiquetados distintos) $R^2$ $O(n^2)$~~
uniones de intervalos (programación dinámica)
paridad en algunos de los primeros de bits (vea esto y esto ) $\log(k)\log\log(k)$ $n$
~~otras clases de hipótesis en entornos de baja dimensión.~~

Prácticamente todo lo demás es NP-Difícil de aprender (al menos de manera adecuada) agnósticamente PAC.

El tutorial de Adam Kalai sobre aprendizaje agnóstico también puede interesarle.

Lev Reyzin
fuente

Gracias. Entonces, los árboles de decisión de profundidad constante, los hiperplanos bidimensionales (supongo que las otras configuraciones de baja dimensión a las que se refiere) caen en la categoría de tener solo muchas funciones polinomiales, que se pueden aprender por agotamiento. Las paridades en los bits log (k) loglog (k) y las uniones de intervalos son interesantes porque contienen muchas funciones superpolinomialmente. ¿Hay otros como estos?

Aaron Roth el

Correcto, aunque hay infinitos hiperplanos en R ^ 2, solo O (n ^ 2) wrt clasifica los puntos de datos de manera diferente. No conozco ninguna otra clase interesante fuera de mi cabeza, pero si pienso / encuentro alguna, editaré mi respuesta.

Lev Reyzin

entonces, ¿quieres clases de dimensión VC ilimitadas?

Suresh Venkat

la dimensión de VC ilimitada sin duda sería interesante, pero las clases finitas grandes (para d fija) ya son extremadamente interesantes (y parecen ser raras)

Aaron Roth

@LevReyzin El enlace de conferencias de Kalai no funciona. ¿Podrías arreglar esto amablemente? Busqué en la red pero tampoco pude encontrar esto.

Anirbit