Sobreajuste y regularización en JavaScript

Problema

El modelo perfecto que promete 5 minutos

La tienda le dice al cliente cuándo llegará el pedido. El tiempo se aprende de pedidos anteriores, como en la primera lección sobre aprendizaje automático: la característica es la distancia hasta el cliente, la etiqueta son los minutos hasta la puerta.

Un compañero prueba dos modelos con 8 pedidos anteriores. La recta de la regresión lineal se equivoca por unos minutos. Su curva nunca se equivoca:

const line = fit(train, 1, 0);
const curve = fit(train, 7, 0);
console.log(`recta (grado 1): MSE del entrenamiento ${mse(line, train).toFixed(2)}`);
console.log(`curva (grado 7): MSE del entrenamiento ${mse(curve, train).toFixed(2)}`);
for (const km of [3.5, 21.5])
  console.log(`pedido ${km.toFixed(1)} km: recta ${predict(line, km).toFixed(0)} min, curva ${predict(curve, km).toFixed(0)} min`);

recta (grado 1): MSE del entrenamiento 9.35
curva (grado 7): MSE del entrenamiento 0.00
pedido 3.5 km: recta 24 min, curva 5 min
pedido 21.5 km: recta 70 min, curva 79 min

La curva tiene MSE 0,00: perfecta para el pasado. Entonces llega un pedido nuevo, a 3,5 km. La curva promete 5 minutos, la recta 24. El tiempo real resulta ser de 22 minutos. Para un pedido a 21,5 km la curva dice 79, la recta 70, y la verdad es 68.

El modelo que nunca se equivoca con el pasado es el peor para el futuro. Esto es el sobreajuste (overfitting): el modelo ha memorizado los ejemplos, ruido incluido, en lugar de aprender la relación.

Míralo

La curva de grado d

La recta es w₀ + w₁ · x. La curva añade potencias de x: w₀ + w₁ · x + w₂ · x² + … + w₇ · x⁷. Es un polinomio de grado 7, con 8 pesos. El grado 1 es la recta.

Los pedidos son un ejemplo, pero se parecen a los reales: más lejos es más tiempo, con unos minutos de ruido (tráfico, el ascensor, la espera en la puerta). Además de los 8 para el entrenamiento hay otros 8 para la validación y 8 para la prueba. Por qué tres grupos, en la próxima tarjeta.

// entrenamiento: km hasta el cliente y minutos hasta la puerta
const train = [[2, 19], [5, 23], [7, 38], [10, 42], [13, 52], [16, 54], [19, 63], [22, 69]];
// validación: otros pedidos, solo para elegir
const val = [[3, 24], [6.5, 31], [9, 36], [12, 44], [15, 52], [18, 57], [21, 70], [4, 27]];
// prueba: se ejecuta una vez, al final
const test = [[3.5, 22], [8, 34], [11, 38], [14, 51], [17, 59], [20, 63], [6, 30], [21.5, 68]];

x es la distancia, desplazada alrededor de 12 km y hecha diez veces más pequeña. Si no, 22⁷ es unos 2500 millones y las cuentas pierden precisión.

// x es la distancia alrededor de 12 km, diez veces más pequeña
function powers(km, degree) {
  const x = (km - 12) / 10;
  const p = [1];
  for (let j = 1; j <= degree; j++) p.push(p[j - 1] * x);
  return p;
}

function predict(w, km) {
  const p = powers(km, w.length - 1);
  let sum = 0;
  for (let j = 0; j < w.length; j++) sum += w[j] * p[j];
  return sum;
}

function mse(w, data) {
  let sum = 0;
  for (const [km, minutes] of data) {
    const e = predict(w, km) - minutes;
    sum += e * e;
  }
  return sum / data.length;
}

Podrías encontrar los pesos con el descenso del gradiente, pero con grado 7 necesita millones de pasos. Hay un atajo: los mejores pesos son la solución de un sistema de ecuaciones, con tantas ecuaciones como pesos. El sistema se resuelve con la eliminación de Gauss, como en la escuela, solo que con 8 incógnitas. El código está aquí para que todo se vea. No hace falta que lo sigas línea por línea:

// los mejores pesos directamente: un sistema de ecuaciones
function fit(data, degree, lambda) {
  const m = degree + 1;
  const a = Array.from({ length: m }, () => new Array(m).fill(0));
  const b = new Array(m).fill(0);
  for (const [km, minutes] of data) {
    const p = powers(km, degree);
    for (let i = 0; i < m; i++) {
      b[i] += p[i] * minutes;
      for (let j = 0; j < m; j++) a[i][j] += p[i] * p[j];
    }
  }
  // la penalización: λ en la diagonal, no en el intercepto
  for (let i = 1; i < m; i++) a[i][i] += lambda;
  return solve(a, b);
}

// eliminación de Gauss: resuelve a · w = b
function solve(a, b) {
  const n = b.length;
  for (let c = 0; c < n; c++) {
    let p = c;
    for (let r = c + 1; r < n; r++)
      if (Math.abs(a[r][c]) > Math.abs(a[p][c])) p = r;
    [a[c], a[p]] = [a[p], a[c]];
    [b[c], b[p]] = [b[p], b[c]];
    for (let r = c + 1; r < n; r++) {
      const f = a[r][c] / a[c][c];
      for (let k = c; k < n; k++) a[r][k] -= f * a[c][k];
      b[r] -= f * b[c];
    }
  }
  const x = new Array(n).fill(0);
  for (let r = n - 1; r >= 0; r--) {
    let s = b[r];
    for (let k = r + 1; k < n; k++) s -= a[r][k] * x[k];
    x[r] = s / a[r][r];
  }
  return x;
}

La línea de la penalización recibe 0 por ahora. Llegaremos a ella.

La idea

Entrenamiento, validación y prueba

En la lección de evaluación los datos tenían dos grupos: entrenamiento y prueba. Ahora hace falta un tercero. Este es el motivo: queremos elegir el grado. Si lo elegimos por el error de entrenamiento, siempre gana el 7, porque su error es 0. Si lo elegimos con la prueba, la prueba ha participado en una decisión y al final ya no es honesta.

Así que los datos están en tres grupos:

datos de entrenamiento: de ellos se aprenden los pesos;
datos de validación: en ellos se comparan los modelos y se elige el grado;
datos de prueba: se ejecutan una vez, al final, para el modelo elegido.

console.log("MSE: entrenamiento / validación");
let best = 1;
let bestVal = Infinity;
for (let degree = 1; degree <= 7; degree++) {
  const w = fit(train, degree, 0);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`grado ${degree}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    best = degree;
  }
}
const testErr = mse(fit(train, best, 0), test);
console.log(`grado elegido: ${best}, ` +
  `prueba: ${testErr.toFixed(2)}`);

MSE: entrenamiento / validación
grado 1: 9.35 / 3.64
grado 2: 6.74 / 9.35
grado 3: 6.61 / 9.09
grado 4: 5.64 / 11.95
grado 5: 3.75 / 18.81
grado 6: 3.30 / 29.06
grado 7: 0.00 / 121.20
grado elegido: 1, prueba: 5.57

El error de entrenamiento baja con cada grado: 9,35, 6,74, …, 0,00. El error de validación sube: 3,64, 9,35, …, 121,20. Cuantos más pesos tiene la curva, mejor recuerda los 8 puntos y peor adivina los nuevos. La validación elige el grado 1, la recta, y su error de prueba es 5,57 (la raíz cuadrada de 5,57 es más o menos 2,4 minutos de error medio).

Una cosa parece rara: la recta tiene un error menor en la validación (3,64) que en el entrenamiento (9,35). Con 8 pedidos el azar es grande: a la validación le tocaron pedidos más cercanos a la recta. Por eso, con pocos datos, no te fíes del segundo decimal.

Míralo

La curva se retuerce

console.log("MSE: entrenamiento / validación");
let best = 1;
let bestVal = Infinity;
for (let degree = 1; degree <= 7; degree++) {
  const w = fit(train, degree, 0);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`grado ${degree}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    best = degree;
  }
}
const testErr = mse(fit(train, best, 0), test);
console.log(`grado elegido: ${best}, ` +
  `prueba: ${testErr.toFixed(2)}`);

console.log("entrenamiento / validación, max |w|");
let bestLambda = 0;
let bestVal = Infinity;
for (const lambda of [0, 0.001, 0.01, 0.1, 1, 10]) {
  const w = fit(train, 7, lambda);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`λ ${lambda.toFixed(3)}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}, ` +
    `${biggest(w).toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    bestLambda = lambda;
  }
}
const testErr = mse(fit(train, 7, bestLambda), test);
console.log(`λ elegido: ${bestLambda.toFixed(3)}, ` +
  `prueba: ${testErr.toFixed(2)}`);

Paso a paso, en palabras

8 pedidos de entrenamiento: la distancia en km y los minutos hasta la puerta. Cuanto más lejos, más tiempo, con algo de ruido.
El grado 1 es una recta. Falla la mayoría de los puntos por unos minutos: MSE del entrenamiento 9,35.
Cada grado añade un peso. La curva se dobla más y se acerca a cada punto del entrenamiento.
El grado 7 tiene 8 pesos para 8 puntos y pasa por todos: MSE del entrenamiento 0,00. Parece perfecta.
Ahora 8 pedidos distintos, para la validación. Entre los puntos del entrenamiento la curva se dispara: MSE de la validación 121,20.
Para cada grado: el error de entrenamiento baja, el de validación sube. La validación elige el grado 1, la recta.
Otra cura: conservar el grado 7 pero penalizar los pesos grandes. Con λ = 0,1 la curva se calma: MSE de la validación 9,55.
La curva que memorizó los puntos del entrenamiento es la peor con pedidos nuevos. Error de prueba: 5,57 para la recta, 9,96 para la curva con λ = 0,1.

La curva de grado 7 acierta cada punto azul y falla los naranjas por decenas de minutos. Las barras de abajo dicen lo mismo para cada grado: el azul (entrenamiento) baja, el naranja (validación) sube.

Pruébalo

Encuentra el error

Un compañero elige el grado así. Su programa siempre elige 7. ¿En qué línea está el error?

Elige la línea con el error.

La idea

Tres curas

1. Un modelo más simple. La validación ya lo ha elegido: la recta. Cuando la relación es casi recta, la recta basta, y cada peso extra es espacio para el ruido.

2. Más datos. La curva de grado 7 tiene 8 pesos. Con 8 puntos puede pasar exactamente por cada uno. Con 16 puntos no puede, así que tiene que pasar entre ellos, y eso suaviza el ruido:

const both = [...train, ...val];
for (const data of [train, both])
  console.log(`grado 7, ${data.length} pedidos: prueba ${mse(fit(data, 7, 0), test).toFixed(2)}`);

grado 7, 8 pedidos: prueba 84.44
grado 7, 16 pedidos: prueba 9.41

[...train, ...val] es un arreglo nuevo con las filas de los dos.

El error de prueba baja de 84,44 a 9,41. Aquí la validación se usa también para entrenar, así que no queda nada con qué elegir el grado. En un proyecto real para eso se usa la validación cruzada (ver «Más»).

3. Una penalización para los pesos grandes. La curva que se retuerce tiene pesos enormes: el mayor es 571,59. La curva acierta cada punto porque pesos enormes con signos distintos casi se cancelan, y lo que queda de ellos retuerce la curva. La regularización suma al error una penalización: λ veces la suma de los pesos al cuadrado. Ahora el entrenamiento busca pesos que acierten los puntos y además sean pequeños. En el código es la única línea de penalización en fit. λ se elige con la validación, igual que el grado:

// el peso más grande, sin el intercepto
function biggest(w) {
  return Math.max(...w.slice(1).map(Math.abs));
}

console.log("entrenamiento / validación, max |w|");
let bestLambda = 0;
let bestVal = Infinity;
for (const lambda of [0, 0.001, 0.01, 0.1, 1, 10]) {
  const w = fit(train, 7, lambda);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`λ ${lambda.toFixed(3)}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}, ` +
    `${biggest(w).toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    bestLambda = lambda;
  }
}
const testErr = mse(fit(train, 7, bestLambda), test);
console.log(`λ elegido: ${bestLambda.toFixed(3)}, ` +
  `prueba: ${testErr.toFixed(2)}`);

entrenamiento / validación, max |w|
λ 0.000: 0.00 / 121.20, 571.59
λ 0.001: 2.80 / 26.49, 36.79
λ 0.010: 3.59 / 17.08, 19.16
λ 0.100: 5.72 / 9.55, 20.21
λ 1.000: 19.95 / 16.71, 13.35
λ 10.000: 100.67 / 93.35, 4.92
λ elegido: 0.100, prueba: 9.96

El último número de cada línea (max |w|) es el mayor peso en valor absoluto, sin el intercepto. Con λ = 0,1 el peso más grande baja de 571,59 a 20,21 y la validación de 121,20 a 9,55. Una penalización demasiado fuerte (λ = 10) aplasta la curva casi hasta una recta plana: el error se hace grande también en los datos de entrenamiento (100,67). Esto es lo contrario del sobreajuste, el subajuste: el modelo está demasiado limitado para captar la relación.

El error de prueba para el λ elegido es 9,96: mucho mejor que 84,44, pero la recta (5,57) sigue siendo la mejor. La regularización no convierte una curva en una recta, solo evita que se desboque.

Pruébalo

Completa el hueco

La penalización va en la diagonal del sistema, sin el intercepto (i empieza en 1). ¿Qué se suma?

// la penalización: λ en la diagonal, no en el intercepto
for (let i = 1; i < m; i++) a[i][i] += ;

Pruébalo

Predice la salida

Un error con penalización: el MSE es 2, los pesos son 3 y −4, λ es 0,1. ¿Qué imprimirá?

const mse = 2.0;
const w = [3, -4];
const lambda = 0.1;
let penalty = 0;
for (const x of w) penalty += x * x;
console.log((mse + lambda * penalty).toFixed(2));

Respuesta

2.70

4.50

2.00

La idea

El vecino más cercano memoriza

Los vecinos más cercanos de la primera lección tienen la misma enfermedad. Con k = 1 el modelo devuelve el tiempo del pedido anterior más cercano. Para un pedido del conjunto de entrenamiento el más cercano es el propio pedido, así que el error de entrenamiento es 0:

// el tiempo medio de los k pedidos más cercanos
function knn(data, km, k) {
  const used = new Array(data.length).fill(false);
  let sum = 0;
  for (let t = 0; t < k; t++) {
    let best = -1;
    for (let i = 0; i < data.length; i++) {
      if (used[i]) continue;
      if (best < 0 || Math.abs(data[i][0] - km) < Math.abs(data[best][0] - km)) best = i;
    }
    used[best] = true;
    sum += data[best][1];
  }
  return sum / k;
}

function knnMse(train, data, k) {
  let sum = 0;
  for (const [km, minutes] of data) {
    const e = knn(train, km, k) - minutes;
    sum += e * e;
  }
  return sum / data.length;
}

console.log("MSE: entrenamiento / validación");
for (let k = 1; k <= 4; k++)
  console.log(`k = ${k}: ${knnMse(train, train, k).toFixed(1)} / ${knnMse(train, val, k).toFixed(1)}`);

MSE: entrenamiento / validación
k = 1: 0.0 / 28.9
k = 2: 22.0 / 11.2
k = 3: 19.0 / 19.7
k = 4: 48.7 / 23.2

k = 1 es la memorización en su forma más pura: 0,0 en el entrenamiento, 28,9 en la validación. Con k = 2 el promedio de dos vecinos suaviza el ruido y la validación baja a 11,2. Un k mayor lo empeora otra vez: el promedio de pedidos lejanos difumina la relación. Aquí k es como el grado de la curva: se elige con la validación.

La idea

Cuándo duele

Validación con pocos datos. 8 pedidos de validación dan números ruidosos. La elección puede ser aleatoria: entre el grado 2 y el 3 la diferencia (9,35 y 9,09) es ruido. Cuantos menos datos tengas, más simple debe ser el modelo.
Validación tocada muchas veces. Pruebas 100 grados, valores de λ y características y eliges el mejor en la validación. Uno de ellos es el mejor por casualidad. Por eso la prueba se queda aparte, intacta.
Regularización sin escala. La penalización es igual para todos los pesos. Si una característica está en kilómetros y otra en metros, el peso de los metros es mil veces menor y casi no se penaliza. Las características se escalan primero, como aquí se hace más pequeña x.
Una penalización demasiado fuerte. λ = 10 da subajuste: el modelo no capta ni los datos de entrenamiento. Mira los dos errores: si los dos son altos, el modelo es demasiado simple.
Más datos no son gratis. Cada pedido del entrenamiento es un pedido real que hay que reunir y comprobar. A veces el modelo más simple es la cura más barata.

Más precisamente, para curiosos

La fórmula. El programa busca los pesos para los que la suma de los errores al cuadrado más λ · (w₁² + w₂² + … + w₇²) es la menor. El MSE es la misma suma dividida por el número de pedidos, así que frente al MSE es como si λ fuera 8 veces menor. Esta es la regularización L2 (ridge). Si la penalización es la suma de los valores absolutos, |w₁| + |w₂| + …, es L1 (lasso): vuelve algunos pesos exactamente 0, así que también elige características.

Por qué en la diagonal. Los mejores pesos están donde la pendiente del error es 0 para cada peso. Cada peso da una ecuación. La pendiente de λ · w² es 2 · λ · w, y todos los demás términos de la pendiente también llevan un 2 delante. Al dividir por 2, la penalización es λ · w en la ecuación del mismo peso, es decir, en la diagonal del sistema.

Validación cruzada. Con pocos datos: divides los datos de entrenamiento en 5 partes, aprendes con 4 y mides con la quinta, cinco veces, y tomas el promedio. Cada pedido es validación una vez, y la elección no depende de un grupo aleatorio.

Otras curas. Con el descenso del gradiente: parar cuando el error de validación empieza a subir (early stopping). Con redes neuronales: dropout, que en cada paso apaga neuronas al azar. La idea es la misma: el modelo no debe poder apoyarse en detalles memorizados.

En código real. En scikit-learn son PolynomialFeatures, Ridge (λ se llama alpha), Lasso, KNeighborsRegressor, cross_val_score y GridSearchCV, que prueba los valores y elige con validación cruzada. En ML.NET la regularización es un parámetro de los entrenadores (L2Regularization). La eliminación de Gauss allí se sustituye por métodos más estables, porque con grado alto el sistema es sensible al redondeo.

for (const [km, minutes] of data) desempaqueta cada par. [a[c], a[p]] = [a[p], a[c]] intercambia dos filas.

Ejercicio

Elige k

Resuélvelo en tu editor.

Completa el programa con k-NN: elige k con la validación (el menor error de validación) y después ejecuta la prueba solo para el k elegido.

MSE: entrenamiento / validación
k = 1: 0.0 / 28.9
k = 2: 22.0 / 11.2
k = 3: 19.0 / 19.7
k = 4: 48.7 / 23.2
k elegido: 2, prueba: 16.9

La validación elige k = 2, y el error de prueba es 16,9. Compáralo con la recta: 5,57. Para esta relación casi recta, la recta gana también a los vecinos.

Más tareas

Los grados con más datos. Aprende los grados de 1 a 7 con 16 pedidos (entrenamiento y validación) e imprime el error de entrenamiento y el de prueba. ¿Desde qué grado empieza a subir el error de prueba?
Una rejilla de λ. Prueba λ de 0,02 a 0,5 en pasos de 0,02 para el grado 7. ¿Qué λ elige la validación y cuál es su error de prueba?

Test

Ponte a prueba

1. Un modelo tiene error 0 en los datos de entrenamiento y un error grande en datos nuevos. ¿Cómo se llama?Subajuste: el modelo es demasiado simpleSobreajuste: el modelo ha memorizado los datos de entrenamientoFuga de datos

2. ¿Por qué el grado se elige con la validación y no con la prueba?La elección aprende de los datos con los que elige. La prueba tiene que quedar intacta para ser honesta al finalNo hay diferencia, las dos son lo mismoLa validación es más grande que la prueba

3. ¿Qué hace la regularización?Suma al error una penalización por los pesos grandes, para que la curva no pueda retorcerse y acertar cada puntoQuita la mitad de los puntos de entrenamientoCambia el grado de la curva a 1

4. k-NN con k = 1 tiene error 0 en los datos de entrenamiento. ¿Por qué no es una buena noticia?Porque un error de 0 es imposibleCada punto de entrenamiento es su propio vecino más cercano, así que el modelo solo devuelve el tiempo recordadoPorque k = 1 es demasiado lento

5. ¿Cuál de estas NO cura el sobreajuste?Más datosUna penalización λ más fuerteUn grado más alto de la curva

Sobreajuste: el modelo que memoriza

Cookies