Bloque A M02 1.5 h + 1 h ejercicios

¿Cuántos ejemplos necesito para confiar en mi eval de agentes?

Prerrequisitos: M01 ·

La pregunta

Corriste 50 casos y el agente pasó 45. ¿Eso es 90 por ciento, con qué margen? Si probaste diez prompts sobre esos mismos casos y te quedaste con el mejor, ¿cuánto de su ventaja es suerte? Este módulo convierte esas preguntas en un número de casos, con una demostración de una página que reaparece en cada cota del curso.

La idea en una imagen

Qué mirar: cada barra es un eval sintético de $n$ casos con tasa real $p$ ; la banda es la garantía de Hoeffding y $δ$ la fracción de evals que la cota se permite dejar fuera. Casi siempre deja fuera muchos menos: la cota es válida y conservadora. La precisión garantizada baja como $1/ n$ y sube apenas como $lo g K$ al comparar $K$ variantes.

Lo que necesitas recordar

Markov, Chebyshev y por qué no bastan

El truco de MarkovQué mirar: La curva terracota nunca supera a la azul; tomar esperanza conserva la desigualdad, t·ℙ(X ≥ t) ≤ 𝔼[X]

Markov: si $X \geq 0$ , entonces $P (X \geq t) \leq E [X] / t$ para todo $t > 0$ . Chebyshev: $P (∣ Y - E Y ∣ \geq t) \leq Var (Y) / t^{2}$ . Ambas se demuestran en la sección La matemática de este módulo.

Aplicadas a una media muestral $X ˉ_{n}$ de variables con varianza $σ^{2}$ , Chebyshev da $P (∣ X ˉ_{n} - μ ∣ \geq ε) \leq σ^{2} / (n ε^{2})$ : la ley de los grandes números con una tasa $1/ n$ . Es una tasa honesta pero floja. Para variables acotadas, Hoeffding la mejora a $2 e^{- 2 n ε^{2}}$ , exponencial en $n$ .

Ejemplo. Un eval con 100 casos y tasa de éxito real 0.8. Chebyshev: la probabilidad de desviarse 0.1 es a lo más $0.16/ (100 \cdot 0.01) = 0.16$ . Hoeffding: a lo más $2 e^{- 2} \approx 0.27$ para 0.1 pero $2 e^{- 8} \approx 0.0007$ para 0.2, mientras Chebyshev solo da 0.04.

Dónde lo vas a usar. M02 demuestra Hoeffding y lo convierte en tamaños de eval; M18 lo usa brazo por brazo en UCB.

La matemática

Todo el módulo es una idea, la cota de Chernoff: acota la cola de una suma con su función generadora de momentos, usa Markov y optimiza el parámetro libre. El lema de Hoeffding controla esa generadora para variables acotadas; la cota de la unión reparte el riesgo entre hipótesis; el diccionario finito junta las dos piezas.

Lema de Hoeffdingmedio[18.657 L02 §1.4]

Intuición

Una variable centrada en un intervalo de longitud $b - a$ tiene generadora de momentos como la de una gaussiana de varianza $(b - a)^{2} /4$ , sin importar su forma: esa es la varianza de un volado entre los extremos, la mayor posible.

Enunciado

Sea $Z$ una variable aleatoria con $E [Z] = 0$ y $Z \in [a, b]$ casi seguramente. Entonces, para todo $s \in R$ ,

E [e^{s Z}] \leq exp (\frac{s ^{2} ( b - a ) ^{2}}{8}) .

Demostración

Sea $ψ (s) = lo g E [e^{s Z}]$ ; basta probar $ψ (s) \leq s^{2} (b - a)^{2} /8$ . Como $Z$ es acotada se puede derivar bajo la esperanza:

ψ^{'} (s) = \frac{E [ Z e ^{s Z} ]}{E [ e ^{s Z} ]}, ψ^{''} (s) = \frac{E [ Z ^{2} e ^{s Z} ]}{E [ e ^{s Z} ]} - (\frac{E [ Z e ^{s Z} ]}{E [ e ^{s Z} ]})^{2} .

Define la medida de probabilidad $F$ por $d F = e^{s Z} / E [e^{s Z}] d P$ (integra 1 porque el numerador es positivo y el denominador es su esperanza). Entonces $ψ^{''} (s) = E_{F} [Z^{2}] - (E_{F} [Z])^{2} = Var_{F} (Z)$ . La varianza no cambia al restar una constante, así que $Var_{F} (Z) = Var_{F} (Z - \frac{a + b}{2}) \leq E_{F} [(Z - \frac{a + b}{2})^{2}] \leq \frac{( b - a ) ^{2}}{4}$ , porque $∣ Z - \frac{a + b}{2} ∣ \leq \frac{b - a}{2}$ casi seguramente bajo cualquier medida. Por último $ψ (0) = lo g 1 = 0$ y $ψ^{'} (0) = E [Z] = 0$ , de modo que por el teorema fundamental del cálculo aplicado dos veces,

ψ (s) = \int_{0}^{s} \int_{0}^{u} ψ^{''} (ρ) d ρ d u \leq \int_{0}^{s} \int_{0}^{u} \frac{( b - a ) ^{2}}{4} d ρ d u = \frac{s ^{2} ( b - a ) ^{2}}{8} . □

Desigualdad de Hoeffdingmedio[18.657 L02 §1.4]

Intuición

La media de $n$ variables acotadas se desvía más de $ε$ con probabilidad exponencialmente pequeña en $n ε^{2}$ . Chebyshev daba $1/ (n ε^{2})$ ; esa diferencia decide cuántos casos necesitas.

Enunciado

Sean $X_{1}, \dots, X_{n}$ independientes con $X_{i} \in [0, 1]$ casi seguramente. Para todo $ε > 0$ ,

P (\frac{1}{n} i = 1 \sum n (X_{i} - E X_{i}) > ε) \leq 2 e^{- 2 n ε^{2}} .

Si en cambio $X_{i} \in [a_{i}, b_{i}]$ , el exponente es $- 2 n^{2} ε^{2} / \sum_{i} (b_{i} - a_{i})^{2}$ . En particular, para un clasificador fijo $h$ y $δ \in (0, 1)$ , con probabilidad al menos $1 - δ$ ,

∣ R^_{n} (h) - R (h) ∣ \leq \frac{lo g ( 2/ δ )}{2 n}, y basta n \geq \frac{lo g ( 2/ δ )}{2 ε ^{2}} para garantizar precisi o ˊ n ε .

Demostración

Sea $Z_{i} = X_{i} - E X_{i}$ : variables independientes, centradas, con $Z_{i} \in [- E X_{i}, 1 - E X_{i}]$ , un intervalo de longitud 1. Para la cola superior y cualquier $s > 0$ , como $z \mapsto e^{sz}$ es creciente,

P (i \sum Z_{i} > n ε) = P (e^{s \sum_{i} Z_{i}} > e^{s n ε}) \leq e^{- s n ε} E [e^{s \sum_{i} Z_{i}}] = e^{- s n ε} i = 1 \prod n E [e^{s Z_{i}}],

donde la desigualdad es Markov (M00) y la última igualdad es la independencia. El lema de Hoeffding con $b - a = 1$ da $E [e^{s Z_{i}}] \leq e^{s^{2} /8}$ , así que la cola es a lo más $exp (n s^{2} /8 - s n ε)$ . El exponente es una parábola en $s$ que se minimiza en $s = 4 ε > 0$ , donde vale $- 2 n ε^{2}$ . La cola inferior $P (\sum_{i} Z_{i} < - n ε)$ es la cola superior de las variables $- Z_{i}$ , que cumplen las mismas hipótesis, y da la misma cota; sumar las dos colas produce el factor 2.

Para el corolario, toma $X_{i} = 1 (h (X_{i}) \neq = Y_{i})$ , que son independientes, valen 0 o 1 y tienen esperanza $R (h)$ ; iguala $2 e^{- 2 n ε^{2}} = δ$ y despeja $ε$ , o bien $n$ . Con $X_{i} \in [a_{i}, b_{i}]$ el lema da $E [e^{s Z_{i}}] \leq e^{s^{2} (b_{i} - a_{i})^{2} /8}$ y la misma optimización produce el exponente general. $□$

Cota de la unión y máximo sobre una clase finitabásico[18.657 L02 §1.4, pp. 7-8]

Intuición

Si cada una de $M$ cosas malas tiene probabilidad a lo más $δ / M$ , alguna ocurre con probabilidad a lo más $δ$ . Vigilar $M$ hipótesis a la vez cuesta solo un logaritmo.

Enunciado

Para eventos cualesquiera $A_{1}, \dots, A_{M}$ , $P (⋃_{j} A_{j}) \leq \sum_{j} P (A_{j})$ . En consecuencia, si $H = {h_{1}, \dots, h_{M}}$ es finita, con probabilidad al menos $1 - δ$ ,

1 \leq j \leq M max ∣ R^_{n} (h_{j}) - R (h_{j}) ∣ \leq \frac{lo g ( 2 M / δ )}{2 n} .

Demostración

Para dos eventos, $P (A \cup B) = P (A) + P (B) - P (A \cap B) \leq P (A) + P (B)$ ; para $M$ eventos se itera. Sea $A_{j}$ el evento $∣ R^_{n} (h_{j}) - R (h_{j}) ∣ > ε$ con $ε = lo g (2 M / δ) / (2 n)$ . Por Hoeffding, $P (A_{j}) \leq 2 e^{- 2 n ε^{2}} = δ / M$ para cada $j$ , y el evento "el máximo supera $ε$ " es exactamente $⋃_{j} A_{j}$ , cuya probabilidad es a lo más $M \cdot δ / M = δ$ . $□$

Teorema del diccionario finitomedio[18.657 L03 §1.5]

Intuición

El ERM no le gana al mejor de su clase, pero tampoco pierde por mucho: si el riesgo empírico está cerca del real para todas las hipótesis a la vez, quien gana en la muestra casi gana en la población.

Enunciado

Sea $H = {h_{1}, \dots, h_{M}}$ , $h^$ un ERM sobre $H$ y $h ˉ \in argmin_{h \in H} R (h)$ . Con probabilidad al menos $1 - δ$ ,

R (h^) \leq R (h ˉ) + \frac{2 lo g ( 2 M / δ )}{n}, es decir E (h^) \leq h \in H min E (h) + 2 \frac{lo g ( 2 M / δ )}{2 n} .

Además, en esperanza, $E [R (h^)] \leq R (h ˉ) + 2 lo g (2 M) / n$ .

Demostración

Como $R^_{n} (h^) \leq R^_{n} (h ˉ)$ por definición de ERM, sumando y restando,

R (h^) \leq R (h ˉ) + [R^_{n} (h ˉ) - R (h ˉ)] + [R (h^) - R^_{n} (h^)] \leq R (h ˉ) + 2 j max ∣ R^_{n} (h_{j}) - R (h_{j}) ∣.

El bloque anterior acota el máximo por $lo g (2 M / δ) / (2 n)$ con probabilidad $1 - δ$ , y $2 x / (2 n) = 2 x / n$ . Restar $R (h^{*})$ en ambos lados da la forma con excesos de riesgo.

Para la esperanza hay que acotar $E max_{j} ∣ Z_{j} ∣$ con $Z_{j} = R^_{n} (h_{j}) - R (h_{j})$ , sin la cota de la unión. Para cualquier $s > 0$ , como $exp$ es convexa (Jensen) y el máximo de números positivos es menor que su suma,

E j max ∣ Z_{j} ∣ = \frac{1}{s} lo g exp (s E j max ∣ Z_{j} ∣) \leq \frac{1}{s} lo g E [e^{s m a x_{j} ∣ Z_{j} ∣}] \leq \frac{1}{s} lo g j = 1 \sum M (E [e^{s Z_{j}}] + E [e^{- s Z_{j}}]) .

Cada $\pm Z_{j}$ es la media de $n$ variables independientes centradas en intervalos de longitud 1, así que por el lema de Hoeffding $E [e^{\pm s Z_{j}}] = \prod_{i} E [e^{\pm (s / n) (\cdot)}] \leq e^{n (s / n)^{2} /8} = e^{s^{2} / (8 n)}$ . Por tanto $E max_{j} ∣ Z_{j} ∣ \leq lo g (2 M) / s + s / (8 n)$ . La suma se minimiza en $s = 8 n lo g (2 M)$ , donde ambos términos valen $lo g (2 M) / (8 n)$ , y queda $E max_{j} ∣ Z_{j} ∣ \leq lo g (2 M) / (2 n)$ . Multiplicar por 2 termina. $□$

Variables sub-gaussianasmedio[18.S997 Ch1 §1.2, §1.4]

Intuición

Hoeffding solo usa que la generadora de momentos queda debajo de una gaussiana. Eso define una clase entera de variables con las colas y los máximos de la gaussiana.

Enunciado

$X$ es sub-gaussiana con proxy de varianza $σ^{2}$ , y se escribe $X \sim subG (σ^{2})$ , si $E X = 0$ y $E [e^{s X}] \leq e^{σ^{2} s^{2} /2}$ para todo $s \in R$ . Entonces: (i) $P (X > t) \leq e^{- t^{2} / (2 σ^{2})}$ y lo mismo para $P (X < - t)$ ; (ii) si $X \in [a, b]$ y $E X = 0$ , entonces $X \sim subG ((b - a)^{2} /4)$ ; (iii) una suma $\sum_{i} a_{i} X_{i}$ de independientes $subG (σ^{2})$ es $subG (σ^{2} ∥ a ∥_{2}^{2})$ ; (iv) si $X_{1}, \dots, X_{N} \sim subG (σ^{2})$ , no necesariamente independientes, $E max_{i} X_{i} \leq σ 2 lo g N$ y $E max_{i} ∣ X_{i} ∣ \leq σ 2 lo g (2 N)$ .

Solo enunciado · [18.S997 Ch1: Definición 1.2, Lema 1.3, Lema 1.8, Teorema 1.6, Teorema 1.14]

(i) es Chernoff con $s = t / σ^{2}$ ; (ii) es el lema de Hoeffding; (iii) factoriza la generadora; (iv) es el máximo suave de la demostración anterior. Se usan en M03 y M04.

Desigualdad de Bernsteinmedio[18.657 L03 §2.3]

Intuición

Hoeffding solo ve el rango. Si la varianza es pequeña, como en un agente que acierta el 95 por ciento, Bernstein lo cobra: su término dominante escala con $σ$ , no con el rango.

Enunciado

Sean $X_{1}, \dots, X_{n}$ independientes, centradas, con $∣ X_{i} ∣ \leq c$ y varianza promedio $σ^{2} = \frac{1}{n} \sum_{i} Var (X_{i})$ . Para todo $t > 0$ ,

P (\frac{1}{n} i \sum X_{i} > t) \leq exp (- \frac{n t ^{2}}{2 σ ^{2} + \frac{2}{3} t c}) .

Despejando, con probabilidad al menos $1 - δ$ , $\frac{1}{n} \sum_{i} X_{i} \leq \frac{2 σ ^{2} l o g ( 1/ δ )}{n} + \frac{2 c l o g ( 1/ δ )}{3 n}$ .

Solo enunciado · [18.657 L03 §2.3, p. 4; versión sub-exponencial en 18.S997 Ch1, Teorema 1.13]

La demostración es Chernoff con una cota más fina de la generadora, $E [e^{s X_{i}}] \leq 1 + s^{2} Var (X_{i}) g (s)$ con $g (s) = (e^{sc} - sc - 1) / (c^{2} s^{2})$ , y una optimización en $s$ que la fuente deja como ejercicio. El segundo término del despeje decae como $1/ n$ .

Más allá de Hoeffding: McDiarmid y tasas rápidasavanzado[18.657 L03 §2.1-2.2, §3.1]

Enunciado

Diferencias acotadas (McDiarmid): si $g$ cumple $sup ∣ g (x_{1}, \dots, x_{n}) - g (x_{1}, \dots, x_{i}^{'}, \dots, x_{n}) ∣ \leq c_{i}$ para cada $i$ , entonces $P (∣ g (X_{1}, \dots, X_{n}) - E g ∣ > t) \leq 2 exp (- 2 t^{2} / \sum_{i} c_{i}^{2})$ para $X_{i}$ independientes. Caso sin ruido: si $η (X) \in {0, 1}$ casi seguramente y $h^{*} \in H$ con $∣ H ∣ = M$ , entonces con probabilidad $1 - δ$ , $E (h^) \leq 2 lo g (M / δ) / n$ .

Solo enunciado · [18.657 L03 §2.1-2.2 (Azuma-Hoeffding y diferencias acotadas), §3.1 (caso sin ruido)]

McDiarmid se demuestra escribiendo $g - E g$ como suma de diferencias de martingala y aplicando Azuma, la versión de Hoeffding para martingalas; sirve para funciones de los datos que no son promedios, como el supremo de M03. La tasa $1/ n$ sale de Bernstein: la varianza de la diferencia de pérdidas está acotada por el propio exceso de riesgo.

Juega con esto

¿Y esto qué tiene que ver con mis agentes?

Un eval es una media de indicadoras, el objeto exacto de Hoeffding. Garantizar 5 puntos de precisión con 95 por ciento de confianza cuesta 738 casos por variante; con 50 casos la garantía es de 19 puntos. Una diferencia de 2 puntos entre dos modelos medida en 50 casos no distingue nada, ni con esta cota ni con el intervalo de Wilson de producción, que sigue dando unos 8 puntos.

La cota de la unión es lo que te muerde al elegir el mejor de varios prompts. Si probaste 10 prompts del agente de conciliación de pagos sobre los mismos 50 casos, $M = 10$ y la garantía pasa de 19 a 24 puntos: la ventaja de tres casos del ganador cabe entera en el ruido. La solución es declarar $K$ de antemano y calcular $n$ con él, o separar el conjunto de selección del de certificación.

Cuando la tasa real está cerca de 1, Bernstein abarata el eval porque $p (1 - p)$ es pequeña: certificar un agente que ya acierta 97 por ciento cuesta menos casos que compararlo con uno del 60. El estimador pass@k del Lab A es la misma media de indicadoras con otra combinatoria. M18 aplica Hoeffding brazo por brazo y M23 reutiliza esta librería para evals de agentes completos.

Ejercicios

Tamaños de eval (propio). (a) Calcula $n$ para $ε = 0.05$ y $δ = 0.05$ con una sola hipótesis. (b) Repite para comparar 20 prompts sobre el mismo conjunto. (c) ¿Cuánto crece $n$ si en lugar de 20 comparas 200?

Solución del ejercicio 1

(a) $n = ⌈ lo g (2/0.05) / (2 \cdot 0.0 5^{2})⌉ = ⌈ lo g 40/0.005 ⌉ = ⌈ 737.8 ⌉ = 738$ . (b) Con la unión, $δ / K$ en lugar de $δ$ : $n = ⌈ lo g (2 \cdot 20/0.05) /0.005 ⌉ = ⌈ lo g 800/0.005 ⌉ = ⌈ 1336.9 ⌉ = 1337$ . (c) $lo g 8000/0.005 \approx 1797.4$ , es decir 1798: multiplicar por diez las variantes suma unos 460 casos, porque $K$ entra dentro del logaritmo.

Acotada implica sub-gaussiana (propio). Demuestra que si $X \in [a, b]$ casi seguramente, entonces $X - E X$ es sub-gaussiana con proxy de varianza $σ^{2} = (b - a)^{2} /4$ , es decir, con parámetro $σ = (b - a) /2$ .

Solución del ejercicio 2

$Z = X - E X$ está centrada y vive en $[a - E X, b - E X]$ , un intervalo de longitud $b - a$ . El lema de Hoeffding da $E [e^{s Z}] \leq e^{s^{2} (b - a)^{2} /8} = e^{σ^{2} s^{2} /2}$ con $σ^{2} = (b - a)^{2} /4$ , que es la definición de $subG (σ^{2})$ . La constante es la mejor posible: para $X$ uniforme en ${a, b}$ la varianza real es $(b - a)^{2} /4$ .

Máximo sobre un compacto [18.S997 Assignment 1, Problem 1.3] (opcional). Sea $K$ un compacto de la esfera unitaria de $R^{p}$ con una $ε$ -red de tamaño a lo más $(C / ε)^{d}$ para todo $ε \in (0, 1)$ , y $X \sim subG_{p} (σ^{2})$ . Demuestra que con probabilidad $1 - δ$ , $max_{θ \in K} θ^{⊤} X \leq c_{1} σ d lo g (2 p / d) + c_{2} σ lo g (1/ δ)$ . Adelanta las redes de M04. Enunciado: Assignment 1 (PDF).

Autoevaluación

Fuentes

[18.657 L02 §1.4] lema y desigualdad de Hoeffding y el máximo sobre una clase finita, cotejados línea por línea: Lecture 2 notes.
[18.657 L03 §1.5, §2.1-2.3, §3.1] diccionario finito (alta probabilidad y esperanza), Azuma, diferencias acotadas, Bernstein y caso sin ruido: Lecture 3 notes.
[18.S997 Ch 1] sub-gaussianas: definición, colas, sumas y máximos: Chapter 1; ejercicio opcional en Assignment 1.
[18.650] intervalos de confianza (respaldo; Wilson en la calculadora): Statistics for Applications.
Síntesis propia: simuladores, animación, ejercicios 1 y 2 con solución.

Lo que queda fuera

Martingalas formales y la demostración de Azuma-Hoeffding: 18.657 L03 §2.1.
Clopper-Pearson y bootstrap, lo que usarías en producción sin garantía finita: Brown, Cai y DasGupta, Statistical Science 16 (2001), doi:10.1214/ss/1009213286.
Talagrand y localización, para tasas rápidas con clases infinitas: Boucheron, Lugosi y Massart, Concentration Inequalities (2013), cap. 12.
Demostración de Bernstein en versión sub-exponencial: 18.S997 Ch 1 §1.3.

Este módulo adapta material de MIT OpenCourseWare bajo licencia CC BY-NC-SA 4.0: MIT 18.650 Statistics for Applications (2016); MIT 18.657 Mathematics of Machine Learning (2015); MIT 18.S997 High-Dimensional Statistics (2015). Las adaptaciones (traducción, figuras, simuladores) son propias y heredan la misma licencia. Enlaces a cada fuente en la sección Fuentes.

Siguiente
M03 · ¿Por qué un modelo con más parámetros que datos no siempre sobreajusta?