Bloque A M01 1.5 h + 1 h ejercicios

¿Por qué un LLM puede predecir texto que nunca vio?

Prerrequisitos: M00 ·

La pregunta

Un modelo de lenguaje termina frases que jamás aparecieron en su corpus, y tu agente de soporte responde tickets que nadie había escrito. Eso solo es posible si "aprender" significa algo más preciso que memorizar. Este módulo fija ese significado: qué se minimiza, cuál es el mejor predictor posible, por qué incluso ese predictor se equivoca, y qué le pasa a un modelo que solo memoriza.

La idea en una imagen

Qué mirar: cada paso es una pieza de la notación del curso. El contexto es la entrada $X$ , el siguiente token es la etiqueta $Y$ , y la distribución real del lenguaje, $η (y ∣ x) = P (Y = y ∣ X = x)$ , es lo que nadie conoce y todo modelo imita. Con dos clases $η$ es un número entre 0 y 1; con $∣ V ∣$ tokens, un vector de probabilidades. El módulo trabaja con dos clases porque ahí las demostraciones caben en media página.

Lo que necesitas recordar

Esperanza, varianza y esperanza condicional

Para una variable aleatoria $Y$ , $E [Y]$ es su promedio ponderado por probabilidad y $Var (Y) = E [(Y - E Y)^{2}]$ mide su dispersión. La esperanza condicional $η (x) = E [Y ∣ X = x]$ es el promedio de $Y$ dentro de la rebanada de datos donde $X = x$ : la mejor predicción de $Y$ cuando solo conoces $X$ , en el sentido de que minimiza $E [(Y - g (X))^{2}]$ sobre todas las funciones $g$ .

Ley de la esperanza total: $E [Y] = E [E [Y ∣ X]]$ . Promediar por rebanadas y luego promediar las rebanadas da el promedio global.

Ejemplo. $Y \in {0, 1}$ (clasificación binaria): $η (x) = P (Y = 1 ∣ X = x)$ . Si $η (x) = 0.5$ , ningún clasificador puede hacerlo mejor que un volado en ese $x$ .

Dónde lo vas a usar. Es la definición de "aprender" en M01: el clasificador de Bayes es $1 (η (x) > 1/2)$ . Un LLM aprende $P (siguiente token ∣ contexto)$ , la misma $η$ con $∣ V ∣$ clases (M14). Rebana la nube en el simulador de más abajo y verás $η (x)$ aparecer.

Notación del curso

Míralo en el simulador de esperanza condicional de más abajo. La nube son pares $(X, Y)$ , la curva terracota es la estimación de $η (x)$ y la punteada azul es la $η$ verdadera: tres símbolos de esta tabla en una sola figura.

Símbolo	Significado	Se introduce en
$X, Y$	entrada (features), salida (etiqueta o token)	M01
$η (x) = E [Y ∣ X = x]$	función de regresión	M01
$h, h^{*}, h^$	clasificador, clasificador de Bayes, ERM	M01
$H$	clase de hipótesis	M01
$R (h), R^_{n} (h), E (h)$	riesgo, riesgo empírico, exceso de riesgo	M01
$ℓ, φ$	pérdida, pérdida sustituta	M05
$n, d, K$	muestras, dimensión, brazos o expertos	M02, M17
$ε, δ$	precisión, nivel de confianza	M02
$R_{n} (F)$	complejidad de Rademacher	M03
$VC (H), S_{H} (n)$	dimensión VC, coeficiente de shattering	M03
$N (ε, F, d)$	número de cobertura	M04
$\nabla f, D f, J$	gradiente, derivada, jacobiano	M06
$L, μ, κ$	suavidad, convexidad fuerte, número de condición	M07
$η_{t}$	tamaño de paso (learning rate)	M07
$Q, K, V$	consultas, claves, valores	M09
$N, D, C$	parámetros, tokens, cómputo	M13
$T$	temperatura	M14
$R_{n}$	regret acumulado	M17
$Δ_{i}$	gap del brazo $i$	M18
$π, π_{ref}, β$	política, política de referencia, coeficiente KL	M20

Convenciones: $lo g$ es el logaritmo natural; $∥ \cdot ∥$ sin subíndice es $∥ \cdot ∥_{2}$ ; $1 (\cdot)$ es la indicadora; $softmax (z)_{i} = e^{z_{i}} / \sum_{j} e^{z_{j}}$ ; log-loss es $- lo g p_{y}$ . Esta tabla es copia de la tabla de notación de docs/04 y se actualiza junto con ella.

La matemática

Rigollet abre 18.657 con dos oficios. La estadística modela: supone $y = f (x) + ε$ y estima sus parámetros. El machine learning replica la caja sin abrirla, y la teoría del aprendizaje estadístico pregunta cuántos datos hacen falta para replicarla con una precisión dada.

Caja negra vs. modeloQué mirar: A la izquierda solo importa predecir la salida; a la derecha se escribe lo que hay dentro

Riesgo, función de regresión y ruidobásico[18.657 L01 §2.1]

Intuición

Fijada la entrada, la etiqueta es un volado cargado que cae en 1 con probabilidad $η (x)$ . Cuanto más cerca de $1/2$ está $η (x)$ , menos dice $x$ sobre $y$ , con todos los datos del mundo.

Enunciado

Sea $(X, Y) \in X \times {0, 1}$ un par aleatorio con distribución conjunta $P_{X, Y}$ , y sean $(X_{1}, Y_{1}), \dots, (X_{n}, Y_{n})$ copias independientes de $(X, Y)$ . Un clasificador es una función medible $h : X \to {0, 1}$ y su riesgo (error de clasificación) es

R (h) = P (h (X) \neq = Y) .

La función de regresión es $η (x) = P (Y = 1 ∣ X = x) = E [Y ∣ X = x]$ , de modo que $Y ∣ X \sim Ber (η (X))$ y $Y = η (X) + ε$ con $E [ε ∣ X] = 0$ . El ruido $ε$ es nulo casi seguramente si y solo si $η (X) \in {0, 1}$ casi seguramente.

Riesgo empírico, ERM y el clasificador que memorizabásico[18.657 L01 §2.2; L02 §1.2]

Intuición

No conoces $η$ , pero tienes $n$ pares: sustituye la probabilidad de error por la frecuencia en la muestra y minimízala. Sin restricciones gana un clasificador que memoriza la muestra y nada más; los teoremas de no-free-lunch (ver "Lo que queda fuera") dicen que sin restringir la clase no hay arreglo.

Enunciado

El riesgo empírico de $h$ es

R^_{n} (h) = \frac{1}{n} i = 1 \sum n 1 (h (X_{i}) \neq = Y_{i}) .

Para $h$ fija, $E [R^_{n} (h)] = R (h)$ y $R^_{n} (h) \to R (h)$ casi seguramente. Dada una clase $H$ , un minimizador del riesgo empírico (ERM) es cualquier $h^\in argmin_{h \in H} R^_{n} (h)$ . Sobre la clase de todos los clasificadores, la regla $h^(X_{i}) = Y_{i}$ y $h^(x) = 0$ fuera de la muestra cumple $R^_{n} (h^) = 0$ , pero su riesgo $R (h^) = P (h^(X) \neq = Y ∣ (X_{1}, Y_{1}), \dots, (X_{n}, Y_{n}))$ es una variable aleatoria que no tiene por qué ser pequeña.

Demostración de la insesgadez

Para $h$ fija, cada $1 (h (X_{i}) \neq = Y_{i})$ es una variable de Bernoulli cuya esperanza es $P (h (X_{i}) \neq = Y_{i}) = P (h (X) \neq = Y) = R (h)$ , porque $(X_{i}, Y_{i})$ tiene la misma ley que $(X, Y)$ . Por linealidad, $E [R^_{n} (h)] = \frac{1}{n} \sum_{i} R (h) = R (h)$ . La ley fuerte de los grandes números, aplicada a esas $n$ variables independientes, da la convergencia casi segura. El argumento falla para $h^$ porque $h^$ depende de los mismos pares que se promedian: los sumandos $1 (h^(X_{i}) \neq = Y_{i})$ ya no son independientes ni tienen esperanza $R (h^)$ . $□$

El riesgo de Bayes vale 𝔼[min(η, 1 − η)] ≤ 1/2medio[18.657 L02 §1.1, ecs. (1.2)-(1.3)]

Intuición

Si conocieras $η$ , en cada $x$ apostarías por la etiqueta más probable y perderías con probabilidad $min (η (x), 1 - η (x))$ . El promedio de eso es un piso que ningún dato adicional baja.

Enunciado

El clasificador de Bayes es $h^{*} (x) = 1 (η (x) > 1/2)$ . Para todo clasificador $h$ ,

R (h) = E [1 (h (X) = 0) η (X) + 1 (h (X) = 1) (1 - η (X))], (1)

y en particular el riesgo de Bayes $R^{*} := R (h^{*})$ satisface

R^{*} = E [min (η (X), 1 - η (X))] \leq \frac{1}{2},

con $R^{*} = 1/2$ si y solo si $η (X) = 1/2$ casi seguramente.

Demostración

Los eventos ${Y = 1, h (X) = 0}$ y ${Y = 0, h (X) = 1}$ son disjuntos y su unión es ${h (X) \neq = Y}$ , así que

R (h) = P (Y = 1, h (X) = 0) + P (Y = 0, h (X) = 1) .

Escribe cada probabilidad como esperanza de una indicadora y condiciona en $X$ (ley de la esperanza total):

R (h) = E [E [1 (Y = 1) 1 (h (X) = 0) ∣ X]] + E [E [1 (Y = 0) 1 (h (X) = 1) ∣ X]] .

Como $h (X)$ es función de $X$ , sale de la esperanza condicional; y $E [1 (Y = 1) ∣ X] = η (X)$ , $E [1 (Y = 0) ∣ X] = 1 - η (X)$ . Eso es (1).

Con $h = h^{*}$ se tiene $1 (h^{*} (X) = 0) = 1 (η (X) \leq 1/2)$ y $1 (h^{*} (X) = 1) = 1 (η (X) > 1/2)$ , así que

R (h^{*}) = E [1 (η (X) \leq 1/2) η (X) + 1 (η (X) > 1/2) (1 - η (X))] .

Pero $η \leq 1/2$ equivale a $η \leq 1 - η$ : en el primer sumando $η (X) = min (η (X), 1 - η (X))$ y en el segundo $1 - η (X) = min (η (X), 1 - η (X))$ . Las dos indicadoras suman 1, luego $R (h^{*}) = E [min (η (X), 1 - η (X))]$ . Por último, $min (η, 1 - η) \leq 1/2$ punto a punto, con igualdad exactamente cuando $η = 1/2$ ; al tomar esperanza se obtiene la cota, y la igualdad $R^{*} = 1/2$ fuerza $min (η (X), 1 - η (X)) = 1/2$ casi seguramente. $□$

Identidad del exceso de riesgo y optimalidad de Bayesmedio[18.657 L02 §1.1, teorema y ec. (1.1)]

Intuición

El exceso de riesgo solo cobra donde $h$ contradice a $h^{*}$ , y cobra $∣2 η (x) - 1∣$ : casi nada donde $η \approx 1/2$ , porque ahí nadie puede hacerlo bien, y hasta 1 donde $η \in {0, 1}$ . Por eso es no negativo y $h^{*}$ es óptimo.

Enunciado

Para todo clasificador $h$ , el exceso de riesgo $E (h) := R (h) - R (h^{*})$ satisface

E (h) = E [∣2 η (X) - 1∣ 1 (h (X) \neq = h^{*} (X))] = \int_{{h \neq = h^{*}}} ∣2 η (x) - 1∣ P_{X} (d x) \geq 0.

En consecuencia $R (h^{*}) = in f_{h} R (h)$ , donde el ínfimo recorre todos los clasificadores medibles.

Demostración

Aplica (1) a $h$ y a $h^{*}$ y resta:

R (h) - R (h^{*}) = E [(1 (h (X) = 0) - 1 (h^{*} (X) = 0)) η (X) + (1 (h (X) = 1) - 1 (h^{*} (X) = 1)) (1 - η (X))] .

Como cada clasificador vale 0 o 1, $1 (h (X) = 1) = 1 - 1 (h (X) = 0)$ , y lo mismo para $h^{*}$ : el segundo paréntesis es el negativo del primero. Llamando $D (X) := 1 (h (X) = 0) - 1 (h^{*} (X) = 0)$ ,

R (h) - R (h^{*}) = E [D (X) (η (X) - (1 - η (X)))] = E [(2 η (X) - 1) D (X)] .

Ahora $D (X)$ vale 0 cuando $h$ y $h^{*}$ coinciden. Cuando difieren hay dos casos: si $h^{*} (X) = 0$ entonces $η (X) \leq 1/2$ , $h (X) = 1$ y $D (X) = 0 - 1 = - 1$ , de modo que $(2 η (X) - 1) D (X) = 1 - 2 η (X) = ∣2 η (X) - 1∣$ ; si $h^{*} (X) = 1$ entonces $η (X) > 1/2$ , $h (X) = 0$ y $D (X) = 1 - 0 = 1$ , de modo que $(2 η (X) - 1) D (X) = ∣2 η (X) - 1∣$ . En todos los casos $(2 η (X) - 1) D (X) = ∣2 η (X) - 1∣ 1 (h (X) \neq = h^{*} (X))$ , que es la identidad. La forma integral es la misma esperanza escrita contra la marginal $P_{X}$ . El integrando es no negativo, así que $R (h) \geq R (h^{*})$ para todo $h$ : $h^{*}$ minimiza el riesgo. $□$

Descomposición estimación / aproximación y desigualdades oráculomedio[18.657 L01 §2.4; L02 §1.3]

Intuición

Restringir la clase $H$ elimina al memorizador, pero quizá el mejor de $H$ ya no es $h^{*}$ . El exceso de riesgo del ERM se parte en lo que pierdes por tener datos finitos y lo que pierdes por haber elegido $H$ ; solo el primero baja con $n$ .

Enunciado

Sea $h ˉ \in argmin_{h \in H} R (h)$ (se supone que existe) y $h^_{n}$ el ERM sobre $H$ . Entonces

E (h^_{n}) = error de estimaci o ˊ n R (h^_{n}) - R (h ˉ) + error de aproximaci o ˊ n R (h ˉ) - R (h^{*}) .

El segundo término no depende de los datos; para el primero, como $R^_{n} (h^_{n}) \leq R^_{n} (h ˉ)$ por definición,

R (h^_{n}) - R (h ˉ) \leq [R (h^_{n}) - R^_{n} (h^_{n})] + [R^_{n} (h ˉ) - R (h ˉ)] \leq h \in H sup R^_{n} (h) - R (h) + [R^_{n} (h ˉ) - R (h ˉ)] .

Una desigualdad oráculo es una cota $P (R (h^_{n}) \leq R (h ˉ) + Δ_{n, δ} (H)) \geq 1 - δ$ con $Δ_{n, δ} (H)$ explícito: el ERM es casi tan bueno como el mejor de su clase sin conocer a $h ˉ$ .

Solo enunciado · [18.657 L01 §2.4, pp. 5-6; L02 §1.3, pp. 5-6]

El paso "sup out" cambia una variable que depende de los datos de forma complicada por el supremo de un proceso empírico; controlarlo es el trabajo de M02 ( $H$ finita) y M03 ( $H$ infinita).

Juega con esto

En el segundo simulador, $H_{k}$ son los clasificadores $1 (p (x) > 0)$ con $p$ de grado a lo más $k$ : en una dimensión, a lo más $k$ cambios de etiqueta, así que el ERM es exacto. La $η$ cambia de lado tres veces; ninguna clase con $k < 3$ la sigue.

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

El predictor Bayes-óptimo del siguiente token es la distribución verdadera del lenguaje, y su riesgo no es cero: "el gato se subió al" admite varias continuaciones legítimas: ruido irreducible. Con log-loss ese piso es la entropía del lenguaje, y su exponencial es el piso de la perplejidad (M14); el ejercicio 2 hace la cuenta.

Un modelo que reproduce su corpus y contesta al azar lo demás es el ERM sin restricciones: riesgo empírico cero, riesgo real pésimo. Que un LLM no sea eso depende de cuánto restringen la clase la arquitectura y el entrenamiento (M03, M13).

Un ejemplo concreto. Tu agente de soporte de pagos clasifica cada ticket como "contracargo" o "reembolso" antes de enrutarlo. Cuando el propio cliente no distingue las dos cosas, $η (x) \approx 1/2$ : ningún modelo ni ningún humano baja el error ahí, y castigar al agente por esos casos es medir mal.

"Acertó 43 de 50" es $R^_{n} (h^)$ , no $R (h^)$ ; cuánto pueden separarse es M02. Y si un modelo pequeño no mejora con más ejemplos, sospecha de la aproximación antes que de la estimación (M04).

Ejercicios

Análisis discriminante [18.657 PS1 P1, partes 1-2]. $(X, Y) \in R^{d} \times {0, 1}$ con $P (Y = k) = π_{k} > 0$ y $X ∣ Y = k \sim N (μ_{k}, Σ_{k})$ , $μ_{0} \neq = μ_{1}$ . (1) Densidad de $X$ . (2) Con $Σ_{0} = Σ_{1} = Σ$ definida positiva, calcula $h^{*}$ y describe la geometría de ${h^{*} = 0}$ y ${h^{*} = 1}$ . (3, opcional) Con $Σ_{0} \neq = Σ_{1}$ , ¿qué forma tiene la frontera? Pista: escribe $η (x)$ con la regla de Bayes (L02 §1.1) y compara $π_{1} p_{1} (x)$ con $π_{0} p_{0} (x)$ . Original: PS1 (PDF) · solución oficial.
Riesgo de Bayes para tokens con dos pérdidas (propio). Fija un contexto $x$ y sea $η (\cdot ∣ x)$ la distribución del siguiente token sobre un vocabulario $V$ . (a) Con pérdida 0-1, ¿cuál es el predictor de Bayes y cuánto vale $R^{*} (x)$ ? (b) Con log-loss $ℓ (q, y) = - lo g q (y)$ , con $q$ una distribución sobre $V$ , demuestra que el minimizador de $E [ℓ (q, Y) ∣ X = x]$ es $q = η (\cdot ∣ x)$ y que el mínimo es la entropía $H (η (\cdot ∣ x))$ . (c) Con la distribución de la animación, $(0.42, 0.21, 0.15, 0.10, 0.07, 0.05)$ , calcula ambos riesgos y di cuál importa para un LLM.

Solución del ejercicio 2

(a) $h^{*} (x) = argmax_{y} η (y ∣ x)$ y $R^{*} (x) = 1 - max_{y} η (y ∣ x)$ : es la versión con $∣ V ∣$ clases de $min (η, 1 - η)$ . En el ejemplo, $R^{*} (x) = 0.58$ .

(b) Para cualquier distribución $q$ ,

E [- lo g q (Y) ∣ X = x] = - y \sum η (y ∣ x) lo g q (y) = H (η) + KL (η ∥ q),

donde $H (η) = - \sum_{y} η (y ∣ x) lo g η (y ∣ x)$ y $KL (η ∥ q) = \sum_{y} η (y ∣ x) lo g \frac{η ( y ∣ x )}{q ( y )}$ . La divergencia es no negativa por la desigualdad de Jensen aplicada a $- lo g$ , que es convexa: $KL (η ∥ q) = E_{η} [- lo g (q / η)] \geq - lo g E_{η} [q / η] = - lo g \sum_{y} q (y) = 0$ , con igualdad si y solo si $q = η$ . Por tanto el mínimo es $H (η)$ y se alcanza en $q = η (\cdot ∣ x)$ .

(c) Con logaritmo natural, $H = - (0.42 ln 0.42 + 0.21 ln 0.21 + 0.15 ln 0.15 + 0.10 ln 0.10 + 0.07 ln 0.07 + 0.05 ln 0.05) \approx 1.54$ nats, es decir una perplejidad $e^{1.54} \approx 4.7$ : como si el modelo perfecto dudara entre unas cinco continuaciones equiprobables. El riesgo 0-1 es 0.58 y solo mira el argmax: un modelo que pone 0.99 en "tejado" y otro que pone 0.42 tienen el mismo riesgo 0-1 y log-loss muy distintas. Un LLM se entrena y se evalúa con log-loss porque lo que usa es la distribución completa (muestreo, temperatura, calibración), así que su piso es la entropía, no el 0.58. M14 retoma esto.

Autoevaluación

Fuentes

[18.657 L01 §1, §2.1-2.4] caja negra vs. modelo; $R$ , $η$ y ruido; riesgo empírico y memorizador; descomposición y "sup out": Lecture 1 notes.
[18.657 L02 §1.1-1.3] clasificador de Bayes, teorema (1.1)-(1.3) con su demostración cotejada línea por línea (notación y una errata de la prosa original, anotadas en comentarios), ERM y desigualdades oráculo: Lecture 2 notes.
[18.657 PS1 P1]: enunciado, solución oficial.
[6.7960 Lec 01] marco general: redes como clasificadores con softmax y entropía cruzada; sobreparametrización y generalización (M03): transcripción, video.
[Vision Ch 12] (opcional) redes como funciones: visionbook.mit.edu.
Síntesis propia: animación, simuladores, ejercicio 2 con su solución y la figura rediseñada.

Lo que queda fuera

Regresión con pérdida cuadrática y clasificación multiclase formal con softmax: M05.
No-free-lunch (para todo algoritmo hay una $P_{X, Y}$ con $R^{*} = 0$ y $E R (h^_{n}) \geq 1/2 - ε$ ): enunciado en 18.657 L01 §2.2; demostración en Devroye, Györfi y Lugosi (1996), cap. 7.
Estimadores plug-in y regresión logística como modelo de $η$ : 18.657 L02 §1.2; The Elements of Statistical Learning, cap. 4.
Control del supremo $sup_{H} ∣ R^_{n} - R ∣$ : M02 y M03.

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

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