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

Градиентно спускане

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

Проблем

Най-добрата права, без гадаене

Колегите от урока за линейната регресия избраха права на око. Сега складът иска програмата сама да намери най-добрата. Точна формула има само за правата, а следващите модели (невронните мрежи) нямат такава. Трябва начин, който работи винаги.

Задачата засега е по-малка: складът е известен (6 часа), а търсим само колко часа добавя всеки 100 km, w. Разстоянието е в стотици km, за да са числата малки:

// разстояние в стотици km (0.3 е 30 km) и часове до доставката
static final double[] DIST = {0.3, 0.5, 0.8, 1.0, 1.3, 1.6, 2.0, 2.4, 2.7, 3.0};
static final double[] HOURS = {10, 11, 17, 17, 23, 24, 31, 33, 40, 44};
static final double B = 6; // складът: 6 часа, известно е
static final double NUDGE = 0.0001;

Грешката е същата MSE като в линейната регресия, вече само функция на w:

// MSE на правата часове = w · разстояние + 6
static double loss(double w) {
    double sum = 0;
    for (int i = 0; i < DIST.length; i++) {
        double error = w * DIST[i] + B - HOURS[i];
        sum += error * error;
    }
    return sum / DIST.length;
}

Можем да пробваме w = 0, 1, 2, … до 100 и да вземем най-малката грешка. С едно w това става. С 10 тегла са 100¹⁰ проби, а една невронна мрежа има милиони тегла.

Идеята

Побутни и виж

Вместо да пробваш всичко, застани на едно w и питай: ако мръдна малко надясно, грешката пада ли или расте?

double before = loss(0);
double after = loss(0.01);
System.out.printf("w = 0: грешка %.2f%n", before);
System.out.printf("w = 0.01: грешка %.2f%n", after);
System.out.printf("наклон: %.2f%n", (after - before) / 0.01);
Изход
w = 0: грешка 485.00
w = 0.01: грешка 484.21
наклон: -78.97

Побутването с 0,01 намали грешката с 0,79. Разделено на побутването, това е наклонът: −78,97, с колко се мени грешката на единица w. Минусът значи „надясно е надолу“.

С по-малко побутване (0,0001) наклонът е по-точен. Ето го на четири места:

// наклонът: побутни w и виж с колко се мени грешката
static double slope(double w) {
    return (loss(w + NUDGE) - loss(w)) / NUDGE;
}
for (double w : new double[] {0, 6, 12, 18}) {
    System.out.printf("w = %.0f: грешка %.2f, наклон %.2f%n", w, loss(w), slope(w));
}
Изход
w = 0: грешка 485.00, наклон -79.00
w = 6: грешка 127.21, наклон -40.26
w = 12: грешка 1.83, наклон -1.53
w = 18: грешка 108.87, наклон 37.21

Наклонът казва две неща. Знакът е посоката: минус значи, че w трябва да расте, плюс, че трябва да намалее (при w = 18 вече сме подминали дъното). Големината е колко сме далеч: −79 далеч от дъното, −1,53 почти на дъното.

Идеята

Крачка срещу наклона

Правилото е един ред: w -= скорост · наклон. Срещу наклона, защото наклонът сочи нагоре. С отрицателен наклон това увеличава w, с положителен го намалява. Колкото по-стръмно, толкова по-голяма крачката.

Едно минаване (сметни наклона, направи крачка) е епоха. Повтаряме:

double w = 0;
double rate = 0.1;
for (int epoch = 1; epoch <= 10; epoch++) {
    w -= rate * slope(w);
    System.out.printf("епоха %d: w = %.2f, грешка %.2f%n", epoch, w, loss(w));
}
Изход
епоха 1: w = 7.90, грешка 62.36
епоха 2: w = 10.70, грешка 9.28
епоха 3: w = 11.69, грешка 2.61
епоха 4: w = 12.04, грешка 1.77
епоха 5: w = 12.17, грешка 1.67
епоха 6: w = 12.21, грешка 1.65
епоха 7: w = 12.23, грешка 1.65
епоха 8: w = 12.23, грешка 1.65
епоха 9: w = 12.24, грешка 1.65
епоха 10: w = 12.24, грешка 1.65

Първата крачка е голяма (от 0 до 7,90), защото кривата е стръмна. Към дъното наклонът намалява, а с него и крачките: от епоха 7 нататък w почти не мърда. Грешката 1,65 е по-малка от 1,83 на правата, която колегите избраха на око.

Това е градиентното спускане: стъпка по стъпка надолу по наклона на грешката, докато не стигнеш дъното. „Градиент“ е наклонът, когато параметрите са повече от един.

Виж го

Топката на кривата

static double slope(double w) {
    return (loss(w + NUDGE) - loss(w)) / NUDGE;
}


double w = 0;
double rate = 0.1;
for (int epoch = 1; epoch <= 10; epoch++) {
    w -= rate * slope(w);
}
Стъпка по стъпка, с думи
  1. Отдолу: грешката за всяко w; топката тръгва от w = 0. Отгоре: правата с това w.
  2. Побутни w малко: грешката пада. Наклонът е -79,00: надолу е надясно.
  3. Една стъпка: w -= 0,1 · (-79,00) и w става 7,90. Срещу наклона, тоест надолу.
  4. Всяко минаване е епоха. Към дъното наклонът намалява, а с него и стъпките. След 10: w = 12,24.
  5. Скорост 0,01: сивата топка пълзи. След 10 епохи е едва на w = 5,96.
  6. Скорост 0,35: червената топка прескача дъното, всеки път по-високо. Грешката расте: разлива се.
  7. С 0,1 топката стои на дъното: w = 12,24, грешка 1,65. Никой не е гадал w: то е намерено.

Отдолу е грешката за всяко w, а топката е текущото w. Отгоре е правата с това w върху поръчките: когато топката стигне дъното, правата минава през точките. Сивата и червената топка са същото правило с друга скорост.

Идеята

Скоростта на учене

Числото, по което се умножава наклонът, е скоростта на учене (learning rate). То решава колко дълга е крачката. Три скорости, по 20 епохи (w след първите три и след двадесетата):

for (double rate : new double[] {0.01, 0.1, 0.35}) {
    double w = 0;
    List<String> seen = new ArrayList<>();
    for (int epoch = 1; epoch <= 20; epoch++) {
        w -= rate * slope(w);
        if (epoch <= 3 || epoch == 20) seen.add(String.format("%.2f", w));
    }
    System.out.printf("скорост %.2f: w = %s, грешка %.2f%n", rate, String.join(", ", seen), loss(w));
}
Изход
скорост 0.01: w = 0.79, 1.53, 2.22, 9.02, грешка 35.14
скорост 0.10: w = 7.90, 10.70, 11.69, 12.24, грешка 1.65
скорост 0.35: w = 27.65, -7.18, 36.69, -1224.61, грешка 4938139.70
  • 0,01 е твърде малка. Посоката е правилна, но след 20 епохи w е едва 9,02. Стига дъното, но след стотици епохи.
  • 0,1 е точна. Три крачки и w е близо, после се успокоява на 12,24.
  • 0,35 е твърде голяма. Първата крачка прескача дъното до 27,65. Там наклонът е още по-голям, следващата крачка е още по-дълга и w лети до −7,18, после до 36,69. Грешката става милиони: спускането се разлива.

Добрата скорост не се смята, а се пробва. Обичайно е да започнеш с 0,1 или 0,01 и да гледаш грешката по епохи: ако расте или скача, скоростта е голяма; ако пада едва-едва, е малка.

Идеята

w и b заедно

Досега b беше известно. Сега го търсим и него: всеки параметър има свой наклон (побутваш само него), и всеки прави своя крачка в една и съща епоха.

// MSE на правата часове = w · разстояние + b
static double loss(double w, double b) {
    double sum = 0;
    for (int i = 0; i < DIST.length; i++) {
        double error = w * DIST[i] + b - HOURS[i];
        sum += error * error;
    }
    return sum / DIST.length;
}
double w = 0, b = 0, rate = 0.1;
for (int epoch = 1; epoch <= 1000; epoch++) {
    double slopeW = (loss(w + NUDGE, b) - loss(w, b)) / NUDGE;
    double slopeB = (loss(w, b + NUDGE) - loss(w, b)) / NUDGE;
    w -= rate * slopeW;
    b -= rate * slopeB;
    if (epoch == 1 || epoch == 10 || epoch == 100 || epoch == 1000)
        System.out.printf("епоха %d: w = %.2f, b = %.2f, грешка %.2f%n", epoch, w, b, loss(w, b));
}
Изход
епоха 1: w = 9.77, b = 5.00, грешка 29.77
епоха 10: w = 12.21, b = 6.03, грешка 1.66
епоха 100: w = 12.41, b = 5.65, грешка 1.62
епоха 1000: w = 12.41, b = 5.64, грешка 1.62

След 1000 епохи w = 12,41 часа на 100 km и b = 5,64 часа. Формулата за най-добрата права от линейната регресия дава 0,1241 часа на km и 5,64 часа: същата права. Спускането не знае формулата; то само върви надолу.

Идеята

Мащабът на признаците

Защо разстоянието беше в стотици km? Ето същите поръчки в km:

// същите поръчки, но разстоянието е в km
static final double[] KM = {30, 50, 80, 100, 130, 160, 200, 240, 270, 300};
static final double[] HOURS = {10, 11, 17, 17, 23, 24, 31, 33, 40, 44};
static final double NUDGE = 0.0001;

Със скорост 0,1 спускането се разлива от първата епоха:

double w = 0, b = 0, rate = 0.1;
for (int epoch = 1; epoch <= 3; epoch++) {
    double slopeW = (loss(w + NUDGE, b) - loss(w, b)) / NUDGE;
    double slopeB = (loss(w, b + NUDGE) - loss(w, b)) / NUDGE;
    w -= rate * slopeW;
    b -= rate * slopeB;
    System.out.printf("скорост 0.1, епоха %d: w = %.0f%n", epoch, w);
}
Изход
скорост 0.1, епоха 1: w = 977
скорост 0.1, епоха 2: w = -6304921
скорост 0.1, епоха 3: w = 40699231079

Наклонът по w расте с големината на признака: всяко w се умножава по 300 вместо по 3, и при w = 0 наклонът е почти −10 000. Тогава намаляваме скоростта, докато спре да се разлива:

double w = 0, b = 0, rate = 0.00002;
for (int epoch = 1; epoch <= 1000; epoch++) {
    double slopeW = (loss(w + NUDGE, b) - loss(w, b)) / NUDGE;
    double slopeB = (loss(w, b + NUDGE) - loss(w, b)) / NUDGE;
    w -= rate * slopeW;
    b -= rate * slopeB;
    if (epoch == 10 || epoch == 100 || epoch == 1000)
        System.out.printf("епоха %d: w = %.4f, b = %.4f, грешка %.2f%n", epoch, w, b, loss(w, b));
}
Изход
епоха 10: w = 0.1513, b = 0.0013, грешка 9.44
епоха 100: w = 0.1513, b = 0.0063, грешка 9.42
епоха 1000: w = 0.1510, b = 0.0563, грешка 9.28

Сега не се разлива, но b почти не мърда: след 1000 епохи е 0,06 вместо 5,64, а w стои на 0,151 вместо на 0,124. За b крачката е твърде малка. Една скорост не става и за двете. Решението е мащабът: признаците се привеждат в близък обхват преди обучението (тук делене на 100; често се вади средното и се дели на разсейването). Без това нито една скорост не върши работа.

Пробвай

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

w е 2, наклонът там е −20, а скоростта е 0,1. Какво ще отпечата една стъпка?

double w = 2;
double slope = -20;
double rate = 0.1;
w -= rate * slope;
System.out.printf("%.1f%n", w);
Отговор

Пробвай

Попълни

Кое действие прави крачката срещу наклона?

for (int epoch = 1; epoch <= 10; epoch++) {
    w  rate * slope(w);
}

Пробвай

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

Колега пише спускането, но грешката по епохи расте все по-бързо. На кой ред е грешката?

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

Идеята

Кога спускането боли

  • Грешна скорост. Твърде голяма се разлива, твърде малка пълзи. Ако грешката по епохи расте или скача, първо намали скоростта.
  • Признаци в различен мащаб. km и брой пратки в една права: наклоните се различават стотици пъти и нито една скорост не става. Мащабирай признаците преди обучението.
  • Не само една долина. Грешката на правата е една гладка купа и дъното е едно. При невронните мрежи кривата има много долини и плата: спускането стига някое дъно, не непременно най-ниското, и резултатът зависи от началното w.
  • Кога да спреш. Тук епохите са зададени. На практика се спира, когато грешката престане да пада, а дали моделът е добър за нови поръчки се мери отделно (оценката на модела).
  • Цената. Всяка епоха минава през всички данни. С милиони примери и милиони тегла обучението върви часове на специални сървъри; тази инфраструктура (машини за обучение, пускане на модела в продукция) се учи в DevOps курса ZeroToOps.
По-точно, за любопитните

Наклонът по формула. Побутването е приближение. За MSE наклонът има точна формула (производната): 2 · средното на грешка · разстояние. Ето двата начина един до друг:

// наклонът по формула: 2 · средното на грешка · разстояние
static double slopeByFormula(double w) {
    double sum = 0;
    for (int i = 0; i < DIST.length; i++) {
        double error = w * DIST[i] + B - HOURS[i];
        sum += error * DIST[i];
    }
    return 2 * sum / DIST.length;
}
for (double w : new double[] {0, 12}) {
    System.out.printf("при w = %.0f: с числа %.2f, по формула %.2f%n", w, slope(w), slopeByFormula(w));
}
Изход
при w = 0: с числа -79.00, по формула -79.00
при w = 12: с числа -1.53, по формула -1.53

Еднакви са до втория знак. Формулата е по-бърза (един проход вместо два за всеки параметър), затова библиотеките смятат производните автоматично по кода на модела. Това е обратното разпространение от урока за обучението на мрежа.

Градиентът. При много параметри наклоните им заедно са градиентът (вектор). Стъпката е същата за всеки: параметър -= скорост · неговият наклон.

Части от данните. С милиони примери една епоха е бавна. Затова наклонът се смята на малка случайна част (mini-batch) и крачките са много повече. Това е стохастичното градиентно спускане (SGD). Подобрените му версии (например Adam) пазят и „инерция“ на предишните крачки.

Упражнение

Куриерът, научен сам

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

В урока за линейната регресия колегите сравниха три прави за цената на куриера. Сега програмата да намери най-добрата сама:

// пратки: тегло в kg и цена на куриера в €
static final double[] KG = {0.5, 1.0, 1.5, 2.0, 3.0, 4.0, 5.0, 6.0};
static final double[] EUR = {4.10, 4.60, 5.00, 5.60, 6.40, 7.50, 8.30, 9.40};
static final double NUDGE = 0.0001;

Напиши функцията на грешката (MSE) за цена = w · kg + b, после 1000 епохи градиентно спускане за w и b заедно, от w = 0 и b = 0, със скорост 0,05 и побутване 0,0001. Отпечатай w, b и грешката с по 4 знака.

Изход
w = 0.9538, b = 3.6204, MSE 0.0038

Още задачи

  • Скоростта. Пусни със скорост 0,1. Какво става? Намери най-голямата скорост, при която грешката още пада.
  • Спиране. Вместо 1000 епохи спри, когато и двата наклона са по-малки от 0,001 по абсолютна стойност. След колко епохи?
  • Сравнение. Колко по-малка е грешката от най-добрата права на колегите (A, MSE 0,0144)?

Тест

Провери се

1. Наклонът на грешката при текущото w е −40. Накъде трябва да мръдне w?
2. Със скорост 0,35 w скача 27,65, −7,18, 36,69, а грешката расте. Какво да направиш?
3. Със скорост 0,01 след 10 епохи w е 5,96, а дъното е около 12. Грешна ли е скоростта?
4. Защо с разстоянието в km (30 до 300) спускането се разлива при скорост, която работи със стотици km (0,3 до 3)?
5. Спускането за правата на доставките стига w = 12,41 и b = 5,64. Формулата от линейната регресия дава 0,1241 ч/km и 5,64 ч. Защо тогава изобщо спускане?

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