Contando etiquetas alcanzables: coeficientes de ruptura canónicos
Definir verbalmente los coeficientes de ruptura parece sencillo a primera vista:
Dada una clase de hipótesis h, es norteᵗʰ coeficiente de ruptura, denotado Sₙ(h), representa el mayor número de etiquetados que pueden lograr los clasificadores en h en una muestra de norte vectores de características.
Pero ¿qué es un “etiquetado”? ¿Y qué lo hace?realizable”? Responder esas preguntas nos ayudará a sentar algunas bases en la búsqueda de una definición más formal.
En el contexto de la clasificación binaria, una etiquetado de una muestra de vectores de características es simplemente cualquiera de las formas en que podemos asignar valores del conjunto {-1, 1} a esos vectores. Como ejemplo muy simple, considere dos vectores de características unidimensionales (es decir, puntos en una recta numérica), X₁ = 1 y X₂ = 2.
Los posibles etiquetados son cualquier combinación de los valores de clasificación que podemos asignar a los vectores de características individuales independientes entre sí. Podemos representar cada etiquetado como un vector, donde la primera y segunda coordenada representan los valores asignados a X₁ y X₂, respectivamente. El conjunto de posibles etiquetados es, por tanto, {(-1, -1), (-1, 1), (1, -1), (1, 1)}. Tenga en cuenta que una muestra de tamaño 2 produce 2² = 4 etiquetados posibles; pronto veremos cómo esto se generaliza a muestras de tamaño arbitrario.
Nosotros decimos eso un etiquetado es realizable por una clase de hipótesis h si existe un clasificador h ∈ h de donde puede resultar ese etiquetado. Continuando con nuestro ejemplo simple, supongamos que estamos limitados a clasificadores de la forma X ≥ kk ∈ ℝ, es decir, umbrales unidimensionales tales que cualquier cosa a la derecha del umbral se clasifica positivamente. Esta clase de hipótesis no puede lograr el etiquetado (1, -1). X₂ siendo mayor que X₁ implica que cualquier umbral que clasifique X₁ positivamente debe hacer lo mismo para X₂. Por tanto, el conjunto de etiquetados alcanzables es {(-1, -1), (-1, 1), (1, 1)}.
Habiendo entendido la terminología básica, podemos comenzar a desarrollar alguna notación para expresar formalmente elementos de la definición verbal con la que comenzamos.
Nos limitamos a representar las etiquetas como vectores como lo hicimos en nuestro ejemplo simple, donde cada coordenada representa el valor de clasificación asignado al vector de características correspondiente. Hay 2ⁿ posibles etiquetados en total: Hay dos opciones posibles para cada vector de características, y podemos pensar en un etiquetado como una colección de norte tales elecciones, cada una de ellas independientemente del resto. Si una clase de hipótesis h puede lograr todos los etiquetados posibles de una muestra 𝒞ₙ, es decir, si el número de realizable etiquetados de 𝒞ₙ es igual a 2ⁿ, Nosotros decimos eso H se hace añicos 𝒞ₙ.
Finalmente, usando la notación anterior, convergimos en una definición más rigurosa de Sₙ(h):
De acuerdo con nuestra explicación de la destrucción, Sₙ(h) igual a 2ⁿ implica que existe una muestra de tamaño norte que esta destrozado por h.
Estimación de la expresividad de la clase de hipótesis: dimensión canónica de VC
La dimensión Vapnik-Chervonenkis (VC) es una forma de medir el poder expresivo de una clase de hipótesis. Se basa en la idea de destrucción que acabamos de definir y juega un papel importante al ayudarnos a determinar qué clases de hipótesis se pueden aprender con PAC y cuáles no.
Comencemos intentando definir intuitivamente la dimensión canónica de VC:
Dada una clase de hipótesis hsu dimensión VC, denotada como VCdim(h), se define como el mayor número natural norte para el cual existe una muestra de tamaño norte eso es roto por h.
Usando Sₙ(h) nos permite expresar esto de manera mucho más limpia y sucinta:
VCdim(h) = máx{ norte ∈ ℕ : Sₙ(h) = 2ⁿ }
Sin embargo, esta definición no es precisa. Tenga en cuenta que el conjunto de números para los cuales el coeficiente de destrucción es igual a 2ⁿ puede ser infinito. (En consecuencia, es posible que VCdim(h) = ∞.) Si ese es el caso, el conjunto no tiene un máximo bien definido. Abordamos esto tomando el supremum en su lugar:
VCdim(h) = sorber{ norte ∈ ℕ : Sₙ(h) = 2ⁿ }
Esta definición rigurosa y concisa es la que usaremos en el futuro.
Agregar preferencias a la mezcla: coeficientes estratégicos devastadores
Generalizar las nociones canónicas que acabamos de repasar para que funcionen en una configuración estratégica es bastante sencillo. Redefinir los coeficientes devastadores en términos de punto de datos mejor respuesta definimos en el artículo anterior es prácticamente todo lo que tendremos que hacer.
Dada una clase de hipótesis h, un conjunto de preferencias Ry una función de costo C, el norteᵗʰ coeficiente devastador de Sᴛʀᴀᴄ⟨h, R, C⟩, denotado σₙ(H, R, c), representa el mayor número de etiquetados que pueden lograr los clasificadores en h en un conjunto de norte vectores de características potencialmente manipulados, es decir, norte Los datos señalan las mejores respuestas.
Como recordatorio, así es como definimos la mejor respuesta al punto de datos:
Podemos modificar la notación que utilizamos en nuestra discusión sobre los coeficientes de ruptura canónicos para formalizar aún más esto:
La principal diferencia es que cada X en la muestra tiene que tener un correspondiente r. Aparte de eso, poner el punto de datos con la mejor respuesta donde teníamos x en el caso canónico funciona sin problemas.
Como control rápido de cordura, consideremos qué sucede si R = {0}. El término de recompensa realizado 𝕀(h(z) = 1) ⋅ r será 0 en todos los puntos de datos. Maximizar la utilidad se convierte así en sinónimo de minimizar costes.. La mejor manera de minimizar el costo incurrido por un punto de datos es trivial: nunca manipular su vector de características.
Δ(X, r; h) termina siempre siendo solo X, colocándonos firmemente dentro del territorio de la clasificación canónica. Se deduce que σₙ(h{0}, C) = Sₙ(h) para todos h,c. Esto es consistente con nuestra observación de que la clase de preferencia imparcial representada por R = { 0 } es equivalente a la clasificación binaria canónica.
Expresividad con Preferencias: Dimensión Estratégica de VC (SVC)
Habiendo definido el norteᵗʰ coeficiente de destrucción estratégica, simplemente podemos cambiar el Sₙ(h) en la definición canónica de la dimensión VC para σₙ(h, R, C).
CVS(H, R, c) = sorber{ norte ∈ ℕ : σₙ(H, R, c) = 2ⁿ }
Según el ejemplo que consideramos anteriormente, encontramos que SVC(h{0}, C) = VCdim(h) para cualquier h, C. En efecto, SVC es a VCdim lo que el coeficiente de destrucción estratégica es a su equivalente canónico: ambas son elegantes generalizaciones de conceptos no estratégicos.
De SVC a la capacidad de aprendizaje estratégica de PAC: el teorema fundamental del aprendizaje estratégico
Ahora podemos usar SVC para enunciar el Teorema Fundamental del Aprendizaje Estratégico, que relaciona la complejidad de un problema de clasificación estratégica con su capacidad de aprendizaje (agnóstico) de PAC.
Una instancia de clasificación estratégica Sᴛʀᴀᴄ⟨h, R, C⟩ es un PAC agnóstico que se puede aprender si y solo si SVC(H, R, c) es finito. El complejidad de la muestra para el aprendizaje estratégico agnóstico de PAC es metro(δ, ε) ≤ Cε ⁻² ⋅ CVS(H, R, c) ⋅ iniciar sesión(1/δ)con C siendo una constante.
No daremos muchos detalles sobre cómo se puede probar esto. Baste decir que todo se reduce a una reducción inteligente al (bien documentado) Teorema fundamental de Estadístico Aprendiendo, que es esencialmente la versión no estratégica del teorema. Si tiene inclinaciones matemáticas y está interesado en los aspectos prácticos de la prueba, puede encontrarlos en Apéndice B del documento.
Este teorema esencialmente completa nuestra generalización del aprendizaje clásico de PAC a un entorno de clasificación estratégica. Muestra que la forma en que definimos SVC en realidad no sólo tiene sentido en nuestras cabezas; en realidad funciona como una generalización de VCDim donde más importa. Armados con el teorema fundamental, estamos bien equipados para analizar problemas de clasificación estratégica como lo haríamos con cualquier antiguo problema de clasificación binaria. En mi opinión, tener la capacidad de determinar si un problema estratégico se puede aprender teóricamente o no es bastante increíble.