Límites apropiados de dimensión de VC de aprendizaje de PAC

11

Es bien sabido que para una clase de concepto con VC dimensión , es suficiente obtener ejemplos etiquetados para PAC learn . ¿No me queda claro si el algoritmo de aprendizaje PAC (que utiliza estas muestras) es correcto o incorrecto? En los libros de texto de Kearns y Vazirani, así como de Anthony y Biggs, parece que el algoritmo de aprendizaje PAC es incorrecto (es decir, la hipótesis de salida no se encuentra en )CdO(dεlog1ε)CC

  1. ¿Podría alguien aclarar si un límite superior similar es válido también para el entorno de aprendizaje PAC adecuado? Si es así, ¿podría darme una referencia donde esto se menciona explícitamente y también contiene una prueba independiente?

  2. Recientemente, Hanneke mejoró este límite al deshacerse del factor . ¿Podría alguien aclarar si se sabe que es extraíble para la configuración de aprendizaje de PAC adecuado? ¿O es una pregunta abierta todavía?log(1/ε)log(1/ε)

Anónimo
fuente
¿A qué papel de Hanneke te refieres?
gradstudent
1
@gradstudent arxiv.org/abs/1507.00473
Clement C.

Respuestas:

9

Agradezco a Aryeh por hacerme esta pregunta.

Como otros han mencionado, la respuesta a (1) es , y el método simple de Minimización empírica de riesgos en C logra la complejidad de la muestra O((re/ /ε)Iniciar sesión(1/ /ε)) (ver Vapnik y Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler y Warmuth, 1989).

En cuanto a (2), de hecho se sabe que existen espacios C donde ningún algoritmo de aprendizaje adecuado logra una complejidad de muestra mejor que Ω((d/ε)log(1/ε)) y, por lo tanto, el aprendizaje adecuado no puede lograr el O(d/ε) óptimo ( d / ε ) complejidad de la muestra. Que yo sepa, este hecho nunca se ha publicado, pero se basa en un argumento relacionado de Daniely y Shalev-Shwartz (COLT 2014) (originalmente formulado para una pregunta diferente, pero relacionada, en el aprendizaje multiclase).

Considere el caso sencillo d=1 , y poner el espacio X como {1,2,...,1/ε} , y C es singletons fz(x):=I[x=z],zX : es decir, cada clasificador en C clasifica exactamente un punto de X como 1 y los otros como 0 0. Para el límite inferior, tome la función objetivo como un singleton aleatorio FX , donde XUnorteyoFormetro(X) , y PAG , la distribución marginal de X , es uniforme en X{X} . Ahora el alumno nunca ve ningún ejemplo etiquetado como 1 , pero debe elegir un punto z para adivinar que está etiquetado como 1 (lo más importante, la función `` todo cero '' no está en C, Por lo que cualquier aprendiz adecuada debe adivinar algunos z ), y hasta que se ha visto todos los puntos en X{X} que tiene al menos 1/ /2 probabilidad de adivinar mal (es decir, la probabilidad posterior de su Fz que tiene zX es al menos 1/ /2 ). El argumento del colector de cupones implica que requeriría Ω((1/ /ε)Iniciar sesión(1/ /ε))muestras para ver cada punto en X{X} . Esto prueba un límite inferior de Ω((1/ /ε)Iniciar sesión(1/ /ε)) para todos los alumnos adecuados.

Para General re>1 , tomamos X como {1,2,...,re/ /(4 4ε)} , tome C como clasificadores yoUNA para los conjuntos UNAX de tamaño exactamente re , elija la función objetivo al azar de C y vuelva a tomar PAG como uniforme solo en los puntos donde la función objetivo clasifica 0 0 ( para que el alumno nunca vea un punto etiquetado como 1) Entonces, una generalización del argumento del colector de cupones implica que necesitamos Ω((re/ /ε)Iniciar sesión(1/ /ε)) muestras para ver al menos El |XEl |-2re puntos distintos de X , y sin ver esta cantidad de puntos distintos de cualquier alumno adecuada tiene por lo menos 1/ /3 la posibilidad de adquirir mayor que re/ /4 4 de su conjetura UNA de re puntos equivocada en su hipótesis elegido hUNA, lo que significa que su tasa de error es mayor que ε . Entonces, en este caso, no existe un alumno adecuado con una complejidad de muestra menor que Ω((re/ /ε)Iniciar sesión(1/ /ε)) , lo que significa que ningún alumno adecuado logra la complejidad óptima de la muestra O(re/ /ε) .

Tenga en cuenta que el resultado es bastante específico para el espacio C construido. Existen espacios C donde los alumnos adecuados pueden lograr la complejidad de muestra óptima O(re/ /ε) , e incluso la expresión completa exacta O((re/ /ε)+(1/ /ε)Iniciar sesión(1/ /δ)) de ( Hanneke, 2016a). Se han desarrollado algunos límites superiores e inferiores para estudiantes de ERM generales en (Hanneke, 2016b), cuantificados en términos de propiedades del espacio C, además de analizar algunos casos más especializados en los que los alumnos adecuados específicos a veces pueden lograr la complejidad de la muestra óptima.

Referencias

Vapnik y Chervonenkis (1974). Teoría del reconocimiento de patrones. Nauka, Moscú, 1974.

Blumer, Ehrenfeucht, Haussler y Warmuth (1989). Aprendizaje y la dimensión Vapnik-Chervonenkis. Revista de la Asociación de Maquinaria Informática, 36 (4): 929–965.

Daniely y Shalev-Shwartz (2014). Estudiantes óptimos para problemas multiclase. En Actas de la 27ª Conferencia sobre Teoría del Aprendizaje.

Hanneke (2016a). La complejidad de la muestra óptima del aprendizaje PAC. Revista de investigación de aprendizaje automático, vol. 17 (38), págs. 1-15.

Hanneke (2016b). Límites de error refinados para varios algoritmos de aprendizaje. Revista de investigación de aprendizaje automático, vol. 17 (135), págs. 1-55.

S. Hanneke
fuente
Interesante ... ¿Existe una caracterización combinatoria de las clases para las cuales el aprendizaje PAC adecuado es óptimo para la muestra? O al menos condiciones suficientes (¿cierre bajo intersección, unión?)C
Clement C.
2
@ClementC. No se conoce una caracterización completa de qué clases tienen tasas óptimas alcanzables por los alumnos adecuados en general. El documento referenciado "Límites de error refinados ..." ofrece una caracterización combinatoria de qué clases admiten tasas óptimas para todos los estudiantes de ERM (Corolario 14). La cantidad relevante es el "número de estrella": el mayor número de puntos de manera que uno puede voltear la etiqueta de cualquier punto sin cambiar los otros (Definición 9). Las clases de intersección cerrada tienen un alumno adecuado óptimo: el alg "cierre" (Teorema 5 en el documento, y también demostrado por Darnstädt, 2015).
S. Hanneke
¡Gracias!
Clement C.
6

Sus preguntas (1) y (2) están relacionadas. Primero, hablemos sobre el aprendizaje adecuado de PAC. Se sabe que hay aprendices de PAC adecuados que logran un error de muestra cero y, sin embargo, requieren ejemplos. Para una prueba simple de ladependenciaϵ, considere la clase de concepto de intervalos[a,b][0,1]bajo la distribución uniforme. Si elegimos elintervalo constantemás pequeño, de hecho obtenemos una complejidad de muestra deO(1/ϵ). Supongamos, sin embargo, que elegimos elintervalo consistentemás grande, y el concepto objetivo es un intervalo de puntos como[0,0]Ω(dϵlog1ϵ)ϵ[a,b][0,1]O(1/ϵ)[0,0]. Luego, un argumento simple de colector de cupones muestra que a menos que recibamos aproximadamente ejemplos, nos dejaremos engañar por el espacio entre los ejemplos negativos (el único tipo que veremos), que tiene un comportamiento característico de1/[tamaño de muestra] bajo la distribución uniforme. Los límites inferiores más generales de este tipo se dan en1ϵlog1ϵ1/

P. Auer, R. Ortner. Un nuevo PAC destinado a clases de concepto de intersección cerrada. Machine Learning 66 (2-3): 151-163 (2007) http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf

Lo importante del PAC adecuado es que para obtener resultados positivos en el caso abstracto, no se puede especificar un algoritmo más allá de ERM, que dice "encontrar un concepto consistente con la muestra etiquetada". Cuando tiene una estructura adicional, como intervalos, puede examinar dos algoritmos ERM diferentes, como se indica arriba: un segmento consistente mínimo vs. máximo. ¡Y estos tienen diferentes complejidades de muestra!

El poder de un PAC inadecuado es que puedes diseñar varios esquemas de votación (Hanneke es el resultado), y esta estructura adicional te permite probar mejores tasas. (La historia es más simple para el PAC agnóstico, donde ERM le brinda la mejor tasa de caso más desfavorable posible, hasta constantes).

Editar. Ahora se me ocurre que la estrategia de predicción del gráfico de 1 inclusión de D. Haussler, N. Littlestone, Md K. Warmuth. Predicción de {0,1} -Funciones en puntos dibujados aleatoriamente. Inf. Comput 115 (2): 248-292 (1994) podría ser un candidato natural para el aprendiz PAC universal .O(d/ϵ)

Aria
fuente
¡Gracias! Ok, entonces, si te entiendo correctamente, la complejidad de la muestra del aprendizaje incorrecto de PAC es y para el aprendizaje adecuado de PAC es Θ ( d / ϵ log ( 1 / ϵ ) ) , siendo el límite inferior para este último logrado por el ejemplo que das. ¿Está bien? Θ(d/ϵ)Θ(d/ϵlog(1/ϵ))
Anónimo
Sí, con la ligera reserva de que para un PAC incorrecto debe usar un algoritmo específico (Hanneke's), no cualquier ERM antiguo. Siéntase libre de aceptar la respuesta :)
Aryeh
Llego tarde a la fiesta, pero ¿no es el límite inferior de Proper-PAC mencionado anteriormente un límite inferior de complejidad de muestra para un algoritmo de aprendizaje específico (o una clase restringida del mismo) solamente? Quiero decir, sin esa restricción no hay información, teóricamente no hay separación entre el PAC apropiado e incorrecto, ¿verdad? (¿Y por lo tanto no hay separación sin supuestos computacionales, como o similar)?)NPRPAG
Clemente C.
1
La definición habitual de capacidad de aprendizaje PAC requiere algoritmos de poli tiempo. Mis puntos son que (i) relajar eso, lo apropiado y lo incorrecto tienen la misma complejidad de muestra; (ii) con este requisito, no podemos probar una separación incondicional entre apropiado e impropio (ya que esencialmente probaría algo como NP no es igual a RP). (Sin embargo, podemos demostrar límites más bajos en la complejidad de la muestra de algoritmos de aprendizaje adecuados específicos , que hasta donde yo entiendo es lo que hace la referencia de Aryeh.)
Clement C.
1
@ClementC. En uno de sus comentarios anteriores, que mencionó después de ejecutar un algoritmo PAC incorrecto, un alumno obtiene una hipótesis posiblemente incorrecta y luego puede encontrar la hipótesis adecuada más cercana de la clase de concepto (sin más muestras). Pero, ¿cómo podría hacer esto el alumno sin conocer la distribución bajo la cual se le están dando muestras? ¿No se mide lo más cercano de acuerdo con una distribución desconocida?
Anónimo
5

Para agregar a la respuesta actualmente aceptada:

  1. Si. El el límite superior de la complejidad de la muestra también es válido para el aprendizaje PAC adecuado(aunque es importante tener en cuenta que puede no conducir a un algoritmo de aprendizaje computacionalmente eficiente. Lo cual es normal, ya que a menos queNP=RPse sepa que algunas clases son no se puede aprender de manera eficiente y adecuada en PAC (véase el Teorema 1.3 en el libro Kearns-Vazirani que usted menciona). Esto se muestra realmente en el libro de Kearns-Vazirani (Teorema 3.3), ya queLhay un buscador de hipótesis consistente con clase hipótesisH=C. Ver también [1].

    O(reεIniciar sesión1ε)
    nortePAG=RPAGLH=C
  2. Desconocido. El algoritmo de Hanneke [2] es un algoritmo de aprendizaje inadecuado. Si este factor de adicional ( 1 / ε ) en la complejidad de la muestra se puede eliminar para un aprendizaje PAC adecuado (información teóricamente, es decir, dejando de lado cualquier requisito de eficiencia computacional) sigue siendo una cuestión abierta. Cf. Las preguntas abiertas al final de [3]:Iniciar sesión(1/ /ε)

    Clásicamente, sigue siendo una pregunta abierta si el factor en el límite superior de [1] para el aprendizaje PAC adecuado ( ε , δ ) es necesario.Iniciar sesión(1/ /ε)(ε,δ)

    (La nota de pie de página 1 en el mismo documento también es relevante)


[1] A. Blumer, A. Ehrenfeucht, D. Haussler y MK Warmuth. Aprendizaje y la dimensión Vapnik-Chervonenkis. Journal of the ACM, 36 (4): 929–965, 1989.

[2] S. Hanneke. La complejidad óptima de la muestra del aprendizaje PAC. J. Mach. Aprender. Res. 17, 1, 1319-1333, 2016.

[3] S. Arunachalam y R. de Wolf. Óptima complejidad de la muestra cuántica de algoritmos de aprendizaje. En Actas de la 32a Conferencia de Complejidad Computacional (CCC), 2017.

Clemente C.
fuente
¿Se conjetura que el gráfico de 1 inclusión de Haussler et al. ¿Es un alumno PAC tan óptimo?
Aryeh
@Aryeh, no estoy seguro. Por lo que pude encontrar, Warmuth lo conjeturó en 2004. No sé más que eso.
Clemente C.