Перцептрон з нуля: що обчислює нейрон

Перцептрон бере вимірювання, множить кожне на число, яким керує, додає їх, додає ще одне число й дивиться на знак.

Запишемо вимірювання однієї деталі як вектор $\mathbf{x} = (x_1, x_2)$ — ширина й вага. Перцептрон має вектор ваг $\mathbf{w} = (w_1, w_2)$ і bias $b$. Його score дорівнює

а відповідь — це знак цього score: прийняти, якщо $s(\mathbf{x}) \geq 0$, інакше відхилити.

Це вся модель. Усе, що перцептрон колись знатиме про фабрику, живе у трьох числах.

Варто зупинитися на геометрії, бо це та картинка, яка працюватиме наступні двадцять дев’ять розділів, навіть коли рівняння вже не вміщатимуться в один рядок. Множина точок, де $s(\mathbf{x}) = 0$ — де перцептрон точно не визначився, — це пряма на площині. З одного боку score додатний, і все приймається; з іншого він від’ємний, і все відхиляється. Для перцептрона навчання означає рухати цю пряму.

Два факти про цю пряму прямо випливають з алгебри, і обидва важливі далі:

• $\mathbf{w}$ перпендикулярний до неї. Вектор ваг не лежить уздовж межі — він указує поперек неї, у бік прийнятих деталей.
• $b$ зсуває її, не повертаючи. Без bias пряму довелося б провести через початок координат, а для фабрики, що вимірює міліметри й грами, це було б абсурдним обмеженням: воно означало б, що деталь нульової ширини й нульової ваги стоїть рівно на межі.

Перцептрон починає, не знаючи нічого: $\mathbf{w} = (0, 0)$ і $b = 0$. Кожен score дорівнює нулю, тож він приймає все.

Тепер показуйте йому по одному прикладу. Позначимо прийняті деталі як $y = +1$, а відхилені — як $y = -1$. Для кожного прикладу поставте одне запитання: чи правильний вийшов знак? Компактний спосіб записати це запитання — перевірити, чи $y \cdot s(\mathbf{x})$ додатне: якщо label і score мають однаковий знак, їхній добуток додатний, а якщо різні — від’ємний.

Якщо відповідь так, нічого не змінюйте. Якщо ні — підштовхніть:

Це весь алгоритм, і варто зрозуміти чому це правильний поштовх, а не просто запам’ятовувати його. Припустімо, деталь треба було прийняти ($y = +1$), а score вийшов від’ємним. Додавання $\mathbf{x}$ до $\mathbf{w}$ змінює score на цій самій деталі на

а це додатне число. Score для деталі, з якою він щойно помилився, іде вгору, саме в потрібному напрямку. Правило — не евристика, яку хтось угадав; це найменша зміна, яка доведено покращує конкретний випадок перед ним. Звісно, вона може зламати інший випадок, тому ви проходите коло знову.

Зверніть увагу на те, чого тут немає. Ніде немає похідної. Це не недогляд, і це перша справді важлива ідея курсу.

Те, що ви хотіли б диференціювати, — це помилка: кількість неправильно класифікованих деталей. Але ця кількість — сходинка: вона тримається рівно на 4, поки ви трохи рухаєте пряму, а потім миттєво падає до 3, щойно пряма перетинає точку. Її похідна дорівнює нулю майже всюди й не визначена на сходинках. Математичному аналізу нема за що вхопитися. Правило перцептрона обходить це, взагалі не питаючи про нахил: воно питає лише «правильно чи неправильно?» і рухається в напрямку, який може геометрично обґрунтувати.

Це справжнє розв’язання, і водночас глухий кут. У розділі 2 нам знадобиться loss, який звідкись походить, а не просто обраний; у розділі 4 — модель, яка повідомляє, наскільки вона впевнена; у розділі 5 — щось із більш ніж одним шаром. І жодного з цього не досягти правилом, яке знає тільки «неправильно». Повернення корисного нахилу — ось що змушує з’явитися наступні два розділи. Але перцептрон може зробити те, чого не може жоден із його наступників: навчатися взагалі без математичного аналізу.

Чистий Python, без NumPy. Списки й цикл. NumPy з’явиться в наступному розділі, коли арифметика перестане вміщатися в цикл, який вам хотілося б читати; вводити його зараз означало б сховати арифметику за бібліотекою саме в той момент, коли її треба побачити.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Чотири підсвічені рядки — це алгоритм. Усе інше — облік.

А ось конвеєр із вісьмома виміряними деталями — чотири відправили далі, чотири повернули:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Ці вісім деталей можна розділити прямою: кожна прийнята деталь має ширину менше 22 мм, а кожна відхилена — 23 мм або більше. Вертикальна огорожа на 22 міліметрах робить свою справу. Отже, перцептрон має її знайти.

Запустіть:

None [-142.1, -13.0] 54.0

Двісті епох, 454 виправлення, і він не зійшовся. Ваги великі й мають неправильний знак. Щось не так — крім того, що нічого не не так, і причина цього — найкорисніша річ у цьому розділі.

Перцептрон має гарантію, доведену Новіковим у 1962 році.¹ Якщо дані взагалі можна розділити прямою, алгоритм зробить не більше ніж

виправлень, перш ніж перестане їх робити, де $R$ — це радіус даних, довжина найдовшого вектора прикладу, а $\gamma$ — margin: відстань від розділювальної гіперплощини до найближчої точки у розширеному просторі, де bias є третьою координатою. Саме тому центрування даних змінює її, хоча відстань у міліметрах — ні.

Гарантія безумовна, і в ній немає ні слова про епохи, learning rates чи удачу. У ній також немає ні слова про час, і саме це важливо.

Підставимо наші числа. Виміряно безпосередньо з восьми деталей, із bias, згорнутим у константну ознаку:

Теорему ніколи не було порушено. Запустіть сиру версію достатньо надовго, і вона справді зійдеться — на епосі 11,976, після 29,870 виправлень — комфортно в межах своєї оцінки 2,633,550. І цей розрив сам по собі є суттю: теорема обмежує найгірший випадок, а не типовий. Їй просто знадобилося в шістдесят разів більше епох, ніж хтось витримав би спостерігати.

Другий рядок — ті самі вісім деталей, ті самі двадцять рядків коду, до яких додано три рядки для віднімання середньої ширини й середньої ваги з кожного вимірювання. Ось і все. Це вся зміна. Вона переміщує хмару точок так, що вона охоплює початок координат, а не плаває десь біля (22, 57), і вплив на межу становить коефіцієнт п’ятнадцять тисяч, бо обидва члени покращуються одночасно: $R$ падає з 74 до 13, бо точки більше не вимірюються від далекого початку координат, а $\gamma$ зростає з 0.045 до 0.989, бо margin вимірюється відносно вектора ваг, якому більше не треба нести величезний bias, щоб дотягнутися до даних.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Зійшлося за дві епохи, виправивши себе рівно один раз.

Тут є справжній урок, і це не «пам’ятайте нормалізувати inputs», хоча вам справді варто. Урок у тому, що гарантія того, чи алгоритм завершиться, нічого не каже про те, чи ви будете поруч, коли це станеться, а розрив між цими двома речами зазвичай є геометрією. Це перша поява патерну, який ви знову зустрінете в розділі 6 з ініціалізацією, у розділі 10 з розкладами learning rate і в розділі 13 з квантизацією: математика каже, що річ можлива, а інженерія вирішує, чи вона практична. Курс, який навчає вас лише теореми, дає вам модель, що тренується три дні, і звинувачує вас.

Тепер провал, який завершив першу еру нейронних мереж, — і він уміщується в чотири рядки.

Забудьте фабрику. Візьміть два inputs, кожен із яких дорівнює або 0, або 1, і вимагайте, щоб відповідь була $+1$, коли рівно один із них дорівнює 1:

Це XOR — виключне АБО. Перш ніж читати далі, намалюйте чотири точки на папері: три кути одиничного квадрата й четвертий. Позначте два діагональні кути $(0,1)$ і $(1,0)$ як прийняті, а $(0,0)$ і $(1,1)$ — як відхилені. Тепер намалюйте одну пряму, щоб дві прийняті точки були з одного боку, а дві відхилені — з іншого.

Ви не зможете. Річ не в тому, що це важко або що вам потрібен хитріший алгоритм; річ у тому, що такої прямої не існує. Три рядки алгебри показують чому. Якби перцептрон правильно класифікував усі чотири випадки, то, читаючи чотири рядки по порядку, ми отримали б

Додайте дві середні нерівності: $w_1 + w_2 + 2b \geq 0$, отже $w_1 + w_2 \geq -2b$. Остання каже $w_1 + w_2 < -b$. Разом: $-2b \leq w_1 + w_2 < -b$, що вимагає $-2b < -b$, що вимагає $b > 0$. А перша нерівність каже $b < 0$. Такого $b$ не існує, тож не існує й таких ваг. Жоден перцептрон, із будь-якими числами, не класифікує XOR.

Усе одно запустіть його, бо бачити, як алгоритм провалюється, цінніше, ніж просто почути, що він провалиться:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Він не розбігається й не метається десь біля пристойної відповіді. Він зациклюється: проходить коротку петлю в просторі ваг і повертається точно туди, звідки почав, назавжди, правильно класифікуючи два з чотирьох — те саме, що ви отримали б навмання. Сто тисяч епох і сто епох не відрізняються, бо алгоритм не робить прогресу, який довший запуск міг би завершити. Порівняйте це з конвеєром, який на 200 епохах виглядав застряглим, але насправді повільно просувався до справжньої відповіді. Ззовні перші кілька секунд обидва випадки виглядають схоже. Відрізнити їх без теореми неможливо — і це ще один аргумент за те, щоб знати теорему.

У 1969 році Марвін Мінський і Сеймур Пейперт опублікували Perceptrons — книжкове математичне дослідження того, що саме ця модель може й не може представляти.² XOR — її найчастіше цитований результат, і цю цитату зазвичай використовують як обвинувачення: мовляв, книжка вбила дослідження нейронних мереж на п’ятнадцять років через суперництво чи злість.

Математика в книжці правильна, і вона цікавіша за приклад із XOR. Мінського й Пейперта насамперед цікавило не те, чи може один перцептрон обчислити XOR; їх цікавило, що відбувається, коли перцептрони мають обмежені рецептивні поля — кожен unit бачить лише частину input, — і вони довели, що певні глобальні властивості зображення, наприклад чи фігура є зв’язною, не можуть бути обчислені таким способом незалежно від кількості units. Це справді глибокий результат про локальність, і він не має нічого спільного з популярною історією.

Популярна історія також помиляється щодо історії. Мінський і Пейперт прямо обговорюють багатошарові перцептрони й кажуть, що питання їхньої потужності відкрите: вони підозрювали, що розширення теорії буде «стерильним», але це прогноз, а не доказ, і він був неправильним. У 1969 році бракувало не ідеї складати шари; бракувало способу тренувати такий стек. Правило перцептрона не може цього зробити: йому потрібно знати, наскільки помиляється кожен unit, а для unit, захованого посередині, немає label, з яким його можна порівняти. Ця прогалина залишалася відкритою, доки backpropagation не було популяризовано в 1986 році,³ і її закриття — те, що робить розділ 5.

Отже, чесний підсумок такий. Книжка довела реальне обмеження реальної моделі. Обвал фінансування галузі в сімдесятих мав багато причин, і одна з них полягала в тому, що обіцянки щодо перцептронів на початку шістдесятих були надмірними. А технічну перешкоду можна було подолати, просто ще ні в кого не було потрібного інструмента.

Перцептрону шістдесят вісім років, і ви щойно написали один. Варто точно визначити, які його частини досі є в машині, з якою ви завершите цей курс, бо відповідь така: більше, ніж ви могли б подумати.

Перцептрон застряг на двох речах одночасно, і виявляється, що це одна й та сама річ.

Він не може представляти XOR, бо однієї прямої недостатньо. Виправити це означає складати шари: перший шар викривляє простір, другий проводить пряму у викривленому просторі. Це розділ 5.

Але ви не можете тренувати стек правилом перцептрона, бо воно знає лише «неправильно», а unit посередині мережі не має власного label, щодо якого міг би помилитися. Щоб тренувати стек, потрібно знати, наскільки неправильно і в якому напрямку для кожної ваги — потрібен нахил. А функція помилки перцептрона, ця сходинка, його не має.

Тож перед стеком має з’явитися loss function із корисною похідною. І не така, яку обрали лише тому, що її зручно диференціювати: така, що звідкись походить, каже щось правдиве про дані, і чий gradient випливає з цього значення, а не сконструйований заднім числом, щоб виглядати охайно.

Це розділ 2, і він починається із запитання, на яке перцептрону ніколи не доводилося відповідати: не «чи ця деталь добра?», а «наскільки ймовірні ці показники, якщо це правда?»

Також варто читати разом із цим розділом: оригінальну статтю Розенблата The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), яка читабельніша, ніж підказує її репутація; McCulloch and Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), статтю, що вперше змоделювала нейрон як поріг над зваженою сумою; розділ про перцептрон у A Course in Machine Learning Гела Домі III, де те саме оновлення виведено з іншим акцентом; а також розділи 2 і 3 з Mathematics for Machine Learning Deisenroth, Faisal and Ong про лінійну алгебру, якщо наведений вище блок залишив у вас бажання отримати більше, ніж він дав.