Към съдържанието
wannacode

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

Накратко: Преобучението (overfitting) е, когато моделът наизустява обучаващите данни и греши на нови; валидацията го хваща, а по-прост модел и регуляризация го лекуват.

Проблем

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

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

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

double[] line = fit(train, 1, 0);
double[] curve = fit(train, 7, 0);
System.out.printf("права (степен 1): MSE на обучението %.2f%n", mse(line, train));
System.out.printf("крива (степен 7): MSE на обучението %.2f%n", mse(curve, train));
for (double km : new double[] {3.5, 21.5})
    System.out.printf("поръчка %.1f км: права %.0f мин, крива %.0f мин%n",
            km, predict(line, km), predict(curve, km));
Изход
права (степен 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 за теста. Защо три групи, е в следващата карта.

// обучение: км до клиента и минути до вратата
double[][] train = {{2, 19}, {5, 23}, {7, 38}, {10, 42}, {13, 52}, {16, 54}, {19, 63}, {22, 69}};
// валидация: други поръчки, само за избора
double[][] val = {{3, 24}, {6.5, 31}, {9, 36}, {12, 44}, {15, 52}, {18, 57}, {21, 70}, {4, 27}};
// тест: пуска се веднъж, накрая
double[][] 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 км, смалено десет пъти
static double[] powers(double km, int degree) {
    double x = (km - 12) / 10;
    double[] p = new double[degree + 1];
    p[0] = 1;
    for (int j = 1; j <= degree; j++) p[j] = p[j - 1] * x;
    return p;
}


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


static double mse(double[] w, double[][] data) {
    double sum = 0;
    for (double[] row : data) {
        double e = predict(w, row[0]) - row[1];
        sum += e * e;
    }
    return sum / data.length;
}

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

// най-добрите тегла направо: система уравнения
static double[] fit(double[][] data, int degree, double lambda) {
    int m = degree + 1;
    double[][] a = new double[m][m];
    double[] b = new double[m];
    for (double[] row : data) {
        double[] p = powers(row[0], degree);
        for (int i = 0; i < m; i++) {
            b[i] += p[i] * row[1];
            for (int j = 0; j < m; j++) a[i][j] += p[i] * p[j];
        }
    }
    // наказанието: λ по диагонала, без свободния член
    for (int i = 1; i < m; i++) a[i][i] += lambda;
    return solve(a, b);
}
// методът на Гаус: решава a · w = b
static double[] solve(double[][] a, double[] b) {
    int n = b.length;
    for (int c = 0; c < n; c++) {
        int p = c;
        for (int r = c + 1; r < n; r++)
            if (Math.abs(a[r][c]) > Math.abs(a[p][c])) p = r;
        double[] row = a[c];
        a[c] = a[p];
        a[p] = row;
        double t = b[c];
        b[c] = b[p];
        b[p] = t;
        for (int r = c + 1; r < n; r++) {
            double f = a[r][c] / a[c][c];
            for (int k = c; k < n; k++) a[r][k] -= f * a[c][k];
            b[r] -= f * b[c];
        }
    }
    double[] x = new double[n];
    for (int r = n - 1; r >= 0; r--) {
        double s = b[r];
        for (int 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): пуска се веднъж, накрая, за избрания модел.
System.out.println("MSE: обучение / валидация");
int best = 1;
double bestVal = Double.MAX_VALUE;
for (int degree = 1; degree <= 7; degree++) {
    double[] w = fit(train, degree, 0);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("степен %d: %.2f / %.2f%n",
            degree, trainErr, valErr);
    if (valErr < bestVal) {
        bestVal = valErr;
        best = degree;
    }
}
double testErr = mse(fit(train, best, 0), test);
System.out.printf("избрана степен: %d, тест: %.2f%n",
        best, testErr);
Изход
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 поръчки случайността е голяма: валидацията просто е попаднала на поръчки, по-близки до правата. Затова при малко данни не се доверявай на втория знак.

Виж го

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

System.out.println("MSE: обучение / валидация");
int best = 1;
double bestVal = Double.MAX_VALUE;
for (int degree = 1; degree <= 7; degree++) {
    double[] w = fit(train, degree, 0);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("степен %d: %.2f / %.2f%n",
            degree, trainErr, valErr);
    if (valErr < bestVal) {
        bestVal = valErr;
        best = degree;
    }
}
double testErr = mse(fit(train, best, 0), test);
System.out.printf("избрана степен: %d, тест: %.2f%n",
        best, testErr);
Стъпка по стъпка, с думи
  1. 8 поръчки за обучение: разстоянието в км и минутите до вратата. По-далеч е по-дълго, с малко шум.
  2. Степен 1 е права. Пропуска повечето точки с няколко минути: MSE на обучението 9,35.
  3. Всяка степен добавя едно тегло. Кривата се огъва повече и се доближава до всяка точка от обучението.
  4. Степен 7 има 8 тегла за 8 точки и минава през всяка: MSE на обучението 0,00. Изглежда перфектно.
  5. Сега 8 други поръчки, за валидация. Между точките на обучението кривата отскача: MSE на валидацията 121,20.
  6. За всяка степен: грешката на обучението пада, на валидацията расте. Валидацията избира степен 1, правата.
  7. Друг лек: степен 7, но с наказание за големи тегла. С λ = 0,1 кривата се успокоява: MSE на валидацията 9,55.
  8. Кривата, която наизусти обучението, е най-лоша за нови поръчки. Тестът: 5,57 за правата, 9,96 за кривата с λ = 0,1.

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

Пробвай

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

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

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

Идеята

Три лека

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

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

double[][] both = Arrays.copyOf(train, train.length + val.length);
System.arraycopy(val, 0, both, train.length, val.length);
for (double[][] data : new double[][][] {train, both})
    System.out.printf("степен 7, %d поръчки: тест %.2f%n",
            data.length, mse(fit(data, 7, 0), test));
Изход
степен 7, 8 поръчки: тест 84.44
степен 7, 16 поръчки: тест 9.41
Arrays.copyOf(train, 16) прави масив с 16 места и първите 8 реда на train, а System.arraycopy копира val в другите 8.

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

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

// най-голямото тегло без свободния член
static double biggest(double[] w) {
    double max = 0;
    for (int j = 1; j < w.length; j++) max = Math.max(max, Math.abs(w[j]));
    return max;
}
System.out.println("обучение / валидация, max |w|");
double[] lambdas = {0, 0.001, 0.01, 0.1, 1, 10};
double bestLambda = 0;
double bestVal = Double.MAX_VALUE;
for (double lambda : lambdas) {
    double[] w = fit(train, 7, lambda);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("λ %.3f: %.2f / %.2f, %.2f%n",
            lambda, trainErr, valErr, biggest(w));
    if (valErr < bestVal) {
        bestVal = valErr;
        bestLambda = lambda;
    }
}
double testErr = mse(fit(train, 7, bestLambda), test);
System.out.printf("избрано λ: %.3f, тест: %.2f%n",
        bestLambda, testErr);
Изход
обучение / валидация, 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 (int i = 1; i < m; i++) a[i][i] += ;

Пробвай

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

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

double mse = 2.0;
double[] w = {3, -4};
double lambda = 0.1;
double penalty = 0;
for (double x : w) penalty += x * x;
System.out.printf("%.2f%n", mse + lambda * penalty);
Отговор

Идеята

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

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

// средното време на k-те най-близки поръчки
static double knn(double[][] data, double km, int k) {
    boolean[] used = new boolean[data.length];
    double sum = 0;
    for (int t = 0; t < k; t++) {
        int best = -1;
        for (int 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;
}


static double knnMse(double[][] train, double[][] data, int k) {
    double sum = 0;
    for (double[] row : data) {
        double e = knn(train, row[0], k) - row[1];
        sum += e * e;
    }
    return sum / data.length;
}
System.out.println("MSE: обучение / валидация");
for (int k = 1; k <= 4; k++)
    System.out.printf("k = %d: %.1f / %.1f%n", k, knnMse(train, train, k), knnMse(train, val, 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 = 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). Методът на Гаус там е заменен с по-стабилни методи, защото при висока степен системата е чувствителна към закръглянето.

double[][] е масив от масиви: train[i][0] са километрите на поръчка i, а train[i][1] минутите.

Упражнение

Избери 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 на обучението и голяма грешка на нови данни. Как се казва това?
2. Защо степента се избира с валидацията, а не с теста?
3. Какво прави регуляризацията?
4. k-NN с k = 1 е с грешка 0 на обучението. Защо това не е добра новина?
5. Кое НЕ лекува преобучението?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·