Преобучение (overfitting) и регуляризация в JavaScript

Проблем

Перфектният модел, който обещава 5 минути

Магазинът обещава на клиента кога ще пристигне поръчката. Времето се учи от минали поръчки, както в първия урок за машинното учене: признакът е разстоянието до клиента, етикетът са минутите до вратата.

Колега пробва два модела върху 8 минали поръчки. Правата от линейната регресия греши с няколко минути. Неговата крива не греши нито веднъж:

const line = fit(train, 1, 0);
const curve = fit(train, 7, 0);
console.log(`права (степен 1): MSE на обучението ${mse(line, train).toFixed(2)}`);
console.log(`крива (степен 7): MSE на обучението ${mse(curve, train).toFixed(2)}`);
for (const km of [3.5, 21.5])
  console.log(`поръчка ${km.toFixed(1)} км: права ${predict(line, km).toFixed(0)} мин, крива ${predict(curve, km).toFixed(0)} мин`);

права (степен 1): MSE на обучението 9.35
крива (степен 7): MSE на обучението 0.00
поръчка 3.5 км: права 24 мин, крива 5 мин
поръчка 21.5 км: права 70 мин, крива 79 мин

Кривата е с MSE 0,00: перфектна върху миналото. После идва нова поръчка на 3,5 км. Кривата обещава 5 минути, правата 24. Истинското време се оказва 22 минути. За поръчка на 21,5 км кривата казва 79, правата 70, а истината е 68.

Моделът, който никога не греши върху миналото, е най-лош за бъдещето. Това е преобучение (overfitting): моделът е наизустил примерите, заедно с шума им, вместо да научи зависимостта.

Виж го

Кривата от степен d

Правата е w₀ + w₁ · x. Кривата добавя степени на x: w₀ + w₁ · x + w₂ · x² + … + w₇ · x⁷. Това е полином от степен 7, с 8 тегла. Степен 1 е правата.

Поръчките са примерни, но наподобяват истински: по-далеч е по-дълго, с няколко минути шум (трафик, асансьор, чакане на вратата). Освен 8-те за обучение има 8 други за валидация и 8 за теста. Защо три групи, е в следващата карта.

// обучение: км до клиента и минути до вратата
const train = [[2, 19], [5, 23], [7, 38], [10, 42], [13, 52], [16, 54], [19, 63], [22, 69]];
// валидация: други поръчки, само за избора
const val = [[3, 24], [6.5, 31], [9, 36], [12, 44], [15, 52], [18, 57], [21, 70], [4, 27]];
// тест: пуска се веднъж, накрая
const test = [[3.5, 22], [8, 34], [11, 38], [14, 51], [17, 59], [20, 63], [6, 30], [21.5, 68]];

x е разстоянието, преместено около 12 км и смалено десет пъти. Иначе 22⁷ е около 2,5 милиарда и сметките губят точност.

// x е разстоянието около 12 км, смалено десет пъти
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;
}

Теглата можеш да намериш с градиентно спускане, но при степен 7 то върви милиони стъпки. Има пряк път: най-добрите тегла са решението на система уравнения, с толкова уравнения, колкото са теглата. Системата се решава с метода на Гаус, като в училище, само че с 8 неизвестни. Кодът е тук, за да е видимо всичко. Не е нужно да го следиш ред по ред:

// най-добрите тегла направо: система уравнения
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];
    }
  }
  // наказанието: λ по диагонала, без свободния член
  for (let i = 1; i < m; i++) a[i][i] += lambda;
  return solve(a, b);
}

// методът на Гаус: решава 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;
}

Редът с наказанието засега получава 0. Ще стигнем до него.

Идеята

Обучение, валидация и тест

В урока за оценката данните бяха две групи: обучение и тест. Сега трябва и трета. Ето защо: искаме да изберем степента. Ако я избираме по грешката на обучението, винаги печели 7, защото тя е 0. Ако я избираме по теста, тестът вече участва в решение и не е честен накрая.

Затова данните са три групи:

обучение (training set): от него се учат теглата;
валидация (validation set): по нея се сравняват моделите и се избира степента;
тест (test set): пуска се веднъж, накрая, за избрания модел.

console.log("MSE: обучение / валидация");
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(`степен ${degree}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    best = degree;
  }
}
const testErr = mse(fit(train, best, 0), test);
console.log(`избрана степен: ${best}, ` +
  `тест: ${testErr.toFixed(2)}`);

MSE: обучение / валидация
степен 1: 9.35 / 3.64
степен 2: 6.74 / 9.35
степен 3: 6.61 / 9.09
степен 4: 5.64 / 11.95
степен 5: 3.75 / 18.81
степен 6: 3.30 / 29.06
степен 7: 0.00 / 121.20
избрана степен: 1, тест: 5.57

Грешката на обучението пада с всяка степен: 9,35, 6,74, …, 0,00. Грешката на валидацията расте: 3,64, 9,35, …, 121,20. Колкото повече тегла има кривата, толкова по-добре помни 8-те точки и толкова по-зле познава нови. Валидацията избира степен 1, правата, а тестът ѝ е 5,57 (корен от 5,57 е около 2,4 минути средна грешка).

Едно нещо изглежда странно: правата е с по-малка грешка на валидацията (3,64), отколкото на обучението (9,35). При 8 поръчки случайността е голяма: валидацията просто е попаднала на поръчки, по-близки до правата. Затова при малко данни не се доверявай на втория знак.

Виж го

Кривата се гърчи

console.log("MSE: обучение / валидация");
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(`степен ${degree}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    best = degree;
  }
}
const testErr = mse(fit(train, best, 0), test);
console.log(`избрана степен: ${best}, ` +
  `тест: ${testErr.toFixed(2)}`);

console.log("обучение / валидация, 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(`избрано λ: ${bestLambda.toFixed(3)}, ` +
  `тест: ${testErr.toFixed(2)}`);

Стъпка по стъпка, с думи

8 поръчки за обучение: разстоянието в км и минутите до вратата. По-далеч е по-дълго, с малко шум.
Степен 1 е права. Пропуска повечето точки с няколко минути: MSE на обучението 9,35.
Всяка степен добавя едно тегло. Кривата се огъва повече и се доближава до всяка точка от обучението.
Степен 7 има 8 тегла за 8 точки и минава през всяка: MSE на обучението 0,00. Изглежда перфектно.
Сега 8 други поръчки, за валидация. Между точките на обучението кривата отскача: MSE на валидацията 121,20.
За всяка степен: грешката на обучението пада, на валидацията расте. Валидацията избира степен 1, правата.
Друг лек: степен 7, но с наказание за големи тегла. С λ = 0,1 кривата се успокоява: MSE на валидацията 9,55.
Кривата, която наизусти обучението, е най-лоша за нови поръчки. Тестът: 5,57 за правата, 9,96 за кривата с λ = 0,1.

Кривата от степен 7 уцелва всяка синя точка и пропуска оранжевите с десетки минути. Стълбчетата отдолу казват същото за всяка степен: синьото (обучението) пада, оранжевото (валидацията) расте.

Пробвай

Намери грешката

Колега избира степента така. Програмата му винаги избира 7. На кой ред е грешката?

Избери реда с грешката.

Идеята

Три лека

1. По-прост модел. Валидацията вече го избра: правата. Когато зависимостта е почти права, правата е достатъчна, а всяко тегло отгоре е място за шум.

2. Повече данни. Кривата от степен 7 има 8 тегла. С 8 точки може да мине точно през всяка. С 16 точки не може, затова трябва да мине между тях, а това изглажда шума:

const both = [...train, ...val];
for (const data of [train, both])
  console.log(`степен 7, ${data.length} поръчки: тест ${mse(fit(data, 7, 0), test).toFixed(2)}`);

степен 7, 8 поръчки: тест 84.44
степен 7, 16 поръчки: тест 9.41

[...train, ...val] е нов масив с редовете на двата.

Тестът пада от 84,44 на 9,41. Тук за обучението ползваме и валидацията, затова изборът на степен вече няма с какво да се направи. В истински проект за това има кръстосана валидация (виж „По-точно“).

3. Наказание за големи тегла. Гърчещата се крива има огромни тегла: най-голямото е 571,59. Кривата уцелва всяка точка, защото огромни тегла с различни знаци почти се унищожават, а остатъкът от тях гърчи кривата. Регуляризацията добавя към грешката наказание: λ по сбора на квадратите на теглата. Сега обучението търси тегла, които и уцелват точките, и са малки. В кода това е единственият ред с наказанието във fit. λ се избира с валидацията, както степента:

// най-голямото тегло без свободния член
function biggest(w) {
  return Math.max(...w.slice(1).map(Math.abs));
}

console.log("обучение / валидация, 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(`избрано λ: ${bestLambda.toFixed(3)}, ` +
  `тест: ${testErr.toFixed(2)}`);

обучение / валидация, 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
избрано λ: 0.100, тест: 9.96

Последното число на всеки ред (max |w|) е най-голямото тегло по абсолютна стойност, без свободния член. С λ = 0,1 най-голямото тегло пада от 571,59 до 20,21, а валидацията от 121,20 до 9,55. Твърде силното наказание (λ = 10) смачква кривата почти до хоризонтална линия: грешката става голяма и на обучението (100,67). Това е обратното на преобучение, недообучение: моделът е твърде ограничен, за да хване зависимостта.

Тестът на избраното λ е 9,96: много по-добре от 84,44, но правата (5,57) пак е най-добра. Регуляризацията не прави от крива права, тя само не ѝ дава да полудее.

Пробвай

Попълни

Наказанието отива по диагонала на системата, без свободния член (i започва от 1). Какво се добавя?

// наказанието: λ по диагонала, без свободния член
for (let i = 1; i < m; i++) a[i][i] += ;

Пробвай

Предвиди изхода

Грешка с наказание: MSE е 2, теглата са 3 и −4, λ е 0,1. Какво ще отпечата?

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));

Отговор

2.70

4.50

2.00

Идеята

Най-близкият съсед наизустява

Най-близките съседи от първия урок имат същата болест. С k = 1 моделът връща времето на най-близката минала поръчка. За поръчка от обучението най-близката е самата тя, затова грешката на обучението е 0:

// средното време на k-те най-близки поръчки
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: обучение / валидация");
for (let k = 1; k <= 4; k++)
  console.log(`k = ${k}: ${knnMse(train, train, k).toFixed(1)} / ${knnMse(train, val, k).toFixed(1)}`);

MSE: обучение / валидация
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 е наизустяване в най-чист вид: 0,0 на обучението, 28,9 на валидацията. С k = 2 средното на двама съседи изглажда шума и валидацията пада на 11,2. По-голямо k пак влошава: средното от далечни поръчки размива зависимостта. Тук k е като степента при кривата: избира се с валидацията.

Идеята

Кога вреди

Валидация с малко данни. 8 поръчки за валидация дават шумни числа. Изборът може да е случаен: при степен 2 и 3 разликата (9,35 и 9,09) е шум. Колкото по-малко данни, толкова по-прост модел избирай.
Валидацията, пипана много пъти. Пробваш 100 степени, λ и признаци и избираш най-доброто на валидацията. Някое от тях е най-добро случайно. Затова тестът стои настрана, недокоснат.
Регуляризация без мащаб. Наказанието е еднакво за всички тегла. Ако единият признак е в километри, а другият в метри, теглото на метрите е хиляда пъти по-малко и почти не се наказва. Признаците се мащабират първо, както тук x е смалено.
Твърде силно наказание. λ = 10 дава недообучение: моделът не хваща и обучението. Гледай и двете грешки: ако и двете са високи, моделът е твърде прост.
Повече данни не са безплатни. Всяка поръчка в обучението е истинска поръчка, която трябва да се събере и провери. Понякога по-простият модел е по-евтиният лек.

По-точно, за любопитните

Формулата. Програмата търси теглата, при които сборът на квадратите на грешките плюс λ · (w₁² + w₂² + … + w₇²) е най-малък. MSE е същият сбор, делен на броя на поръчките, затова все едно λ е 8 пъти по-малко пред MSE. Това е L2 регуляризация (ridge). Ако наказанието е сборът на абсолютните стойности, |w₁| + |w₂| + …, е L1 (lasso): тя прави някои тегла точно 0, затова избира и признаци.

Защо по диагонала. Най-добрите тегла са там, където наклонът на грешката е 0 по всяко тегло. Всяко тегло дава едно уравнение. Наклонът на λ · w² е 2 · λ · w, а всички останали членове на наклона също са с двойка отпред. След деленето на 2 наказанието е λ · w в уравнението на същото тегло, тоест по диагонала на системата.

Кръстосана валидация. При малко данни: делиш обучението на 5 части, учиш се на 4 и мериш на петата, пет пъти, и вземаш средното. Всяка поръчка е веднъж валидация, а изборът не зависи от една случайна група.

Други лекове. При градиентното спускане: спиране, когато грешката на валидацията започне да расте (early stopping). При невронните мрежи: dropout, който на всяка стъпка изключва случайни неврони. Идеята е същата: моделът да не може да разчита на наизустени подробности.

В истинския код. В scikit-learn това са PolynomialFeatures, Ridge (λ се казва alpha), Lasso, KNeighborsRegressor, cross_val_score и GridSearchCV, който пробва стойностите и избира с кръстосана валидация. В ML.NET регуляризацията е параметър на треньорите (L2Regularization). Методът на Гаус там е заменен с по-стабилни методи, защото при висока степен системата е чувствителна към закръглянето.

for (const [km, minutes] of data) разглобява всяка двойка. [a[c], a[p]] = [a[p], a[c]] разменя два реда.

Упражнение

Избери k

Реши задачата в редактора си.

Довърши програмата с k-NN: избери k с валидацията (най-малката грешка на валидацията), после пусни теста само за избраното k.

MSE: обучение / валидация
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: 2, тест: 16.9

Валидацията избира k = 2, а тестът е 16,9. Сравни с правата: 5,57. За тази почти права зависимост правата печели и от съседите.

Още задачи

Степените с повече данни. Учи степените от 1 до 7 на 16 поръчки (обучение и валидация) и печатай грешката на обучението и на теста. От коя степен нататък тестът започва да расте?
Мрежа от λ. Пробвай λ от 0,02 до 0,5 през 0,02 за степен 7. Коя λ избира валидацията и какъв е тестът ѝ?

Тест

Провери се

1. Модел е с грешка 0 на обучението и голяма грешка на нови данни. Как се казва това?Преобучение (overfitting): моделът е наизустил обучениетоИзтичане на данниНедообучение: моделът е твърде прост

2. Защо степента се избира с валидацията, а не с теста?Изборът се учи от данните, по които избира. Тестът трябва да остане недокоснат, за да е честен накраяНяма разлика, двете са едно и същоВалидацията е по-голяма от теста

3. Какво прави регуляризацията?Сменя степента на кривата на 1Добавя към грешката наказание за големи тегла, затова кривата не може да се гърчи, за да уцели всяка точкаМаха половината точки от обучението

4. k-NN с k = 1 е с грешка 0 на обучението. Защо това не е добра новина?Всяка точка от обучението е най-близкият съсед на себе си, затова моделът просто връща запомненото времеЗащото грешката 0 е невъзможнаЗащото k = 1 е твърде бавно

5. Кое НЕ лекува преобучението?По-висока степен на криватаПовече данниПо-силно наказание λ

Преобучение: моделът, който наизустява

Бисквитки