Персептронът от нулата: какво изчислява един неврон

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

Запишете измерванията на една част като vector $\mathbf{x} = (x_1, x_2)$ — ширина и тегло. Персептронът държи weight vector $\mathbf{w} = (w_1, w_2)$ и bias $b$. Неговият score е

а отговорът му е знакът на този score: приема, ако $s(\mathbf{x}) \geq 0$, иначе отхвърля.

Това е целият модел. Всичко, което персептронът някога ще знае за фабриката, живее в три числа.

Геометрията заслужава пауза, защото това е картината, която продължава да работи през следващите двадесет и девет глави дори когато уравненията вече не се побират на един ред. Множеството от точки, за които $s(\mathbf{x}) = 0$ — където персептронът е точно нерешителен — е права линия в равнината. От едната страна score е положителен и всичко се приема; от другата е отрицателен и всичко се отхвърля. За един персептрон ученето означава да мести тази права.

Два факта за тази права следват директно от алгебрата и и двата ще имат значение по-късно:

• $\mathbf{w}$ е перпендикулярен на нея. Weight vector не лежи по границата, а сочи през нея, към приетата страна.
• $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 на частта, която току-що е сбъркал, се качва нагоре, точно в посоката, в която трябва да тръгне. Правилото не е heuristic, който някой е налучкал; то е най-малката промяна, която доказуемо подобрява случая пред него. Разбира се, може да счупи друг случай, затова минавате отново.

Забележете какво липсва. Няма производна никъде. Това не е пропуск и е първата наистина важна идея в курса.

Нещото, което бихте искали да диференцирате, е грешката — броят на неправилно класифицираните части. Но този брой е стълбище: стои равен на 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 mm, а всяка отхвърлена е 23 mm или повече. Вертикална ограда при 22 милиметра върши работа. Значи персептронът трябва да я намери.

Пуснете го:

None [-142.1, -13.0] 54.0

Двеста epochs, 454 корекции, и не е converged. Weights са големи и с грешен знак. Нещо не е наред — освен че нищо не е сбъркано, а причината е най-полезното нещо в тази глава.

Персептронът има гаранция, доказана от Новиков през 1962 г.¹ Ако данните изобщо могат да бъдат разделени с права, алгоритъмът прави най-много

корекции, преди да спре да прави такива — където $R$ е радиусът на данните, дължината на най-дългия example vector, а $\gamma$ е margin: разстоянието от разделящия hyperplane до най-близката точка в augmented space, където bias е трета координата. Затова центрирането на данните го променя, докато разстоянието в милиметри не се променя.

Гаранцията е безусловна и не споменава epochs, learning rates или късмет. Тя също така не споменава време, и точно този пропуск е важният.

Сложете нашите числа. Измерени директно от осемте части, с bias, сгънат като постоянна feature:

Теоремата никога не е била нарушена. Пуснете суровата версия достатъчно дълго и тя наистина converges — на epoch 11,976, след 29,870 корекции — спокойно в рамките на bound от 2,633,550, а тази разлика сама по себе си е важна: теоремата ограничава най-лошия случай, не типичния. Просто са ѝ били нужни шестдесет пъти повече epochs, отколкото някой би изтърпял.

Вторият ред е същите осем части, същите двадесет реда code, с добавени три реда за изваждане на средната ширина и средното тегло от всяко измерване. Това е всичко. Това е цялата промяна. Тя премества облака от точки така, че да обхване началото на координатната система, вместо да плава около (22, 57), а ефектът върху bound е фактор петнадесет хиляди, защото и двата члена се подобряват едновременно: $R$ пада от 74 на 13, защото точките вече не се измерват от далечен origin, а $\gamma$ се покачва от 0.045 на 0.989, защото margin се измерва спрямо weight vector, който вече не трябва да носи огромен 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

Converged за два epochs, като се е коригирал точно веднъж.

Тук има истински урок и той не е „помнете да нормализирате входовете си“, макар че трябва. Урокът е, че гаранция дали един алгоритъм ще завърши не ви казва нищо за това дали ще сте там, когато го направи, а разликата между двете обикновено е геометрия. Това е първата поява на pattern, който ще срещнете отново в Глава 6 с initialization, в Глава 10 с learning-rate schedules и в Глава 13 с quantisation: математиката казва, че нещото е възможно, а engineering решава дали е практично. Курс, който ви преподава само теоремата, ви подава модел, който тренира три дни, и после обвинява вас.

Сега провалът, който сложи край на първата ера на neural networks, и той се побира в четири реда.

Забравете фабриката. Вземете два 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$, следователно няма такива weights. Никой персептрон, с каквито и да било числа, не класифицира 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

Той не diverges и не се мята около приличен отговор. Той цикли: върви по кратък loop през weight space и се връща точно там, откъдето е започнал, завинаги, като познава две от четири — колкото бихте получили с налучкване. Сто хиляди epochs и сто са неразличими, защото алгоритъмът не напредва по начин, който по-дълъг run би могъл да довърши. Сравнете това с лентата, която изглеждаше заседнала на 200 epochs, а всъщност се търкаше бавно към реален отговор. Отвън двете изглеждат сходно през първите няколко секунди. Да ги различите без теоремата е невъзможно — което е още един аргумент да знаете теоремата.

През 1969 г. Марвин Мински и Сиймур Пейпърт публикуват Perceptrons, математическо изследване с размер на книга за това какво точно този модел може и не може да представи.² XOR е най-често цитираният му резултат, а цитатът обикновено се използва като обвинение: че книгата е убила изследванията на neural networks за петнадесет години от съперничество или злонамереност.

Математиката в книгата е вярна и е по-интересна от примера с XOR. Мински и Пейпърт не са се интересували основно дали един-единствен персептрон може да направи XOR; интересували са се какво се случва, когато на персептроните се дадат ограничени receptive fields — всяка unit вижда само част от input — и са доказали, че определени глобални свойства на изображение, например дали една фигура е свързана, не могат да бъдат изчислени така, независимо колко units използвате. Това е наистина дълбок резултат за locality и няма нищо общо с популярния разказ.

Популярният разказ греши и исторически. Мински и Пейпърт изрично обсъждат multi-layer perceptrons и казват, че въпросът за тяхната мощ е отворен — подозирали са, че разширяването на теорията би било „sterile“, което е предсказание, не доказателство, и то е било погрешно. Това, което е липсвало през 1969 г., не е била идеята за stacking layers; липсвал е начин да се тренира stack. Правилото на персептрона не може да го направи: трябва да знае колко греши всяка unit, а за unit, заровена по средата, няма label, с който да се сравни. Тази празнина остава отворена, докато backpropagation не е популяризиран през 1986 г.,³ а затварянето ѝ е това, което прави Глава 5.

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

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

Персептронът заседна на две неща едновременно, а те се оказват едно и също.

Не може да представи XOR, защото една права не е достатъчна. Поправянето на това означава stacking layers — първи слой, който огъва пространството, втори, който чертае правата в огънатото пространство. Това е Глава 5.

Но не можете да тренирате stack с правилото на персептрона, защото то знае само „грешно“, а unit в средата на network няма собствен label, за който да е сгрешила. За да тренирате stack, трябва да знаете колко е грешно и в коя посока, за всяко weight — нужен ви е наклон. А error function на персептрона, стълбището, няма такъв.

Затова преди stack трябва да има loss function с използваема производна. И не такава, избрана защото е удобна за диференциране: такава, която идва отнякъде, която казва нещо вярно за данните и чийто gradient произтича от това значение, вместо да бъде reverse-engineered, за да изглежда подредено.

Това е Глава 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), статията, която първа моделира neuron като threshold върху weighted sum; секцията за персептрона в A Course in Machine Learning на Hal Daumé III, която извежда същия update с различен акцент; и глави 2 и 3 от Mathematics for Machine Learning на Deisenroth, Faisal and Ong за линейната алгебра, ако полето по-горе ви е оставило с желание за повече.