ゼロから作るパーセプトロン：ニューロンは何を計算しているのか

パーセプトロンは測定値を受け取り、それぞれに自分が制御する数を掛け、それらを足し、さらにもう1つの数を足して、その符号を見ます。

1つの部品の測定値をベクトル $\mathbf{x} = (x_1, x_2)$ と書きます。幅と重さです。パーセプトロンは重みベクトル $\mathbf{w} = (w_1, w_2)$ とバイアス $b$ を持ちます。そのスコアは

であり、答えはそのスコアの符号です。$s(\mathbf{x}) \geq 0$ なら受け入れ、それ以外なら却下します。

これがモデルのすべてです。パーセプトロンが工場について知り得ることは、すべて3つの数値の中にあります。

この幾何は少し立ち止まって見る価値があります。なぜなら、方程式が1行に収まらなくなっても、この絵はこれから29章ずっと役に立ち続けるからです。$s(\mathbf{x}) = 0$ となる点の集合、つまりパーセプトロンがちょうど決めかねている点の集合は、平面上の直線です。その片側ではスコアが正で、すべて受け入れられます。反対側では負で、すべて却下されます。パーセプトロンにとって学習とは、その直線を動かすことです。

その直線について、代数から直接分かる事実が2つあります。どちらも後で重要になります。

• $\mathbf{w}$ は直線に垂直です。重みベクトルは境界に沿って横たわるのではなく、境界をまたいで、受け入れ側へ向かって指します。
• $b$ は直線を回転させずにずらします。バイアスがなければ、直線は原点を通るよう強制されます。ミリメートルとグラムを測る工場では、それは馬鹿げた制約です。幅も重さもゼロの部品が、ちょうど境界上にあるという意味になってしまうからです。

パーセプトロンは何も知らない状態から始まります。$\mathbf{w} = (0, 0)$ かつ $b = 0$ です。すべてのスコアはゼロなので、すべてを受け入れます。

次に、例を1つずつ見せます。受け入れる部品には $y = +1$、却下する部品には $y = -1$ というラベルを付けます。各例について、問いは1つだけです。符号は正しかったか？ この問いを簡潔に書くには、$y \cdot s(\mathbf{x})$ が正かどうかを調べます。ラベルとスコアの符号が一致していれば積は正になり、一致していなければ負になります。

答えがイエスなら、何も変えません。ノーなら、少し動かします。

これがアルゴリズム全体です。そして、これを丸暗記するのではなく、なぜこれが正しいひと押しなのかを理解する価値があります。ある部品は受け入れられるべきだった（$y = +1$）のに、スコアが負になったとします。$\mathbf{w}$ に $\mathbf{x}$ を足すと、その同じ部品に対するスコアの変化は

となります。これは正の数です。つまり、たった今間違えた部品のスコアは上がる。まさに上がる必要があった方向です。このルールは、誰かが思いつきで選んだヒューリスティックではありません。目の前のケースを改善することが証明できる最小の変更です。もちろん別のケースを壊すかもしれません。だから、もう一周するのです。

ここで存在しないものに注目してください。導関数はどこにもありません。これは見落としではありません。そして、このコースで最初に本当に重要になる考え方です。

微分したくなる対象は誤り、つまり誤分類された部品の数です。しかしその数は階段です。直線を少し動かしている間は4のまま平らに続き、直線が点を横切った瞬間に3へ落ちます。導関数はほとんどどこでもゼロで、段差では未定義です。微積分にはつかむ場所がありません。パーセプトロンのルールは、傾きをまったく求めないことで、この問題を回避します。「正しいか間違いか？」だけを問い、幾何的に正当化できる方向へ動きます。

これは本物の解決策であり、同時に行き止まりでもあります。第2章では、単に選ぶのではなくどこかから導かれる損失が欲しくなります。第4章では、モデルがどれくらい確信しているかを報告してほしくなります。第5章では、1層より多いものが必要になります。そして、それらはいずれも「間違い」しか知らないルールからは届きません。使える傾きを取り戻すことが、次の2章を必要にします。しかしパーセプトロンには、後継者の誰にもできないことができます。微積分なしで学習することです。

純粋な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

ハイライトされた4行がアルゴリズムです。それ以外はすべて事務処理です。

そして、ベルトから測った8つの部品です。4つは出荷され、4つは戻ってきました。

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)

この8つの部品は、直線で分離可能です。受け入れられた部品はすべて22 mm未満で、却下された部品はすべて23 mm以上です。22ミリメートルに垂直な柵を置けば済みます。したがって、パーセプトロンはそれを見つけられるはずです。

実行します。

None [-142.1, -13.0] 54.0

200エポック、454回の修正。それでも収束していません。重みは大きく、符号も逆です。何かがおかしい。ところが、何もおかしくありません。その理由こそ、この章で最も役に立つことです。

パーセプトロンには保証があります。1962年にNovikoffが証明したものです。¹ データがそもそも直線で分離できるなら、このアルゴリズムが停止するまでに行う修正回数は高々

です。ここで $R$ はデータの半径、つまり最も長い例ベクトルの長さであり、$\gamma$ はマージンです。これは、バイアスを第3の座標として持つ拡張空間における、分離超平面から最も近い点までの距離です。だから、ミリメートル単位での距離が変わらなくても、データを中心化するとこれが変わるのです。

この保証は無条件であり、エポック、学習率、運には触れていません。同時に、時間にも触れていません。そして、その省略こそがポイントです。

私たちの数値を入れてみます。8つの部品から直接測り、バイアスを定数特徴量として畳み込むと、次のようになります。

定理は一度も破られていません。生のバージョンを十分長く走らせると、確かに収束します。エポック11,976、29,870回の修正の後です。上限である2,633,550の内側には余裕で収まっています。そして、その差自体がポイントです。定理が抑えるのは最悪の場合であって、典型的な場合ではありません。単に、誰も待っていられないほど、60倍のエポックが必要だっただけです。

2行目は同じ8つの部品、同じ20行のコードです。そこに、各測定値から平均幅と平均重さを引く3行を足しただけです。それだけです。変更は本当にそれだけです。これにより点群は、(22, 57) あたりに浮かぶのではなく、原点をまたぐ位置へ移動します。そして上限への効果は1万5千倍です。なぜなら、2つの項が同時に改善するからです。点が遠く離れた原点から測られなくなるため $R$ は74から13へ下がり、データに到達するために巨大なバイアスを重みベクトルが背負う必要がなくなるため $\gamma$ は0.045から0.989へ上がります。

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

2エポックで収束し、修正はちょうど1回でした。

ここには本当の教訓があります。それは「入力を正規化するのを忘れるな」ではありません。もちろん、それもすべきです。教訓は、アルゴリズムが終了するかどうかについての保証は、それが終了するときにあなたがそこにいられるかについては何も教えてくれないということです。そして、その2つの間の差はたいてい幾何です。これは、これから何度も出会うパターンの最初の登場です。第6章の初期化、第10章の学習率スケジュール、第13章の量子化でも同じです。数学は「それが可能だ」と言い、エンジニアリングは「それが実用的か」を決めます。定理だけを教えるコースは、3日間訓練し続けるモデルを渡して、あなたのせいにします。

次は、ニューラルネットワークの最初の時代を終わらせた失敗です。そしてそれは4行に収まります。

工場のことは忘れてください。0か1のどちらかである2つの入力を取り、そのうちちょうど1つだけが1のときに答えを $+1$ にしたいとします。

これがXOR、排他的論理和です。読み進める前に、4つの点を紙に描いてください。単位正方形の4つの角です。対角にある $(0,1)$ と $(1,0)$ を受け入れ、$(0,0)$ と $(1,1)$ を却下として印を付けます。では、受け入れの2点が片側に、却下の2点が反対側に来るように、1本の直線を引いてください。

できません。難しいのではありません。もっと賢いアルゴリズムが必要なのでもありません。その直線が存在しないのです。3行の代数で理由が分かります。もしパーセプトロンが4つすべてを正しく分類できたなら、4行を順に読むと

となります。真ん中の2つの不等式を足すと、$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

発散はしません。そこそこ良い答えの近くで暴れるわけでもありません。循環します。重み空間の短いループを歩き、永遠に出発点へ正確に戻ってきます。4つのうち2つを正しく分類します。つまり、当てずっぽうと同じです。10万エポックと100エポックは区別できません。長く走らせれば完了するような進捗を、アルゴリズムが作っていないからです。これをベルトの例と比べてください。あちらは200エポックでは詰まって見えましたが、実際には本物の答えへ向かって少しずつ進んでいました。外から見ると、最初の数秒はこの2つが似て見えます。定理なしに見分けることは不可能です。これもまた、定理を知るべき理由です。

1969年、Marvin MinskyとSeymour PapertはPerceptronsを出版しました。このモデルが何を表現でき、何を表現できないのかを数学的に1冊かけて研究した本です。² XORはその中で最もよく引用される結果であり、その引用はたいてい告発として使われます。この本が対抗心や悪意からニューラルネットワーク研究を15年間殺した、という話です。

本の中の数学は正しく、XORの例よりもずっと面白いものです。MinskyとPapertが主に関心を持っていたのは、単一のパーセプトロンがXORを扱えるかどうかではありませんでした。彼らが関心を持っていたのは、パーセプトロンに制限された受容野、つまり各ユニットが入力の一部だけを見るような条件を与えたときに何が起きるかです。そして、図形が連結しているかどうかのような画像のある種の大域的性質は、ユニットをどれだけ使ってもその方式では計算できないことを証明しました。これは局所性についての本当に深い結果であり、よく語られる物語とは関係ありません。

そのよく語られる物語は、歴史についても間違っています。MinskyとPapertは多層パーセプトロンを明示的に論じ、その能力については未解決だと言っています。彼らは理論を拡張することは「不毛」だろうと疑っていましたが、それは予測であって証明ではなく、しかも間違っていました。1969年に欠けていたのは、層を積み重ねるというアイデアではありません。積み重ねたものを訓練する方法でした。パーセプトロンのルールではそれができません。各ユニットがどれだけ間違っているかを知る必要がありますが、ネットワークの真ん中に埋もれたユニットには、比較できるラベルがないからです。この穴は、backpropagationが1986年に広く知られるようになるまで開いたままでした。³ そしてその穴を閉じるのが第5章です。

ですから、正直な要約はこうです。その本は、実在するモデルの実在する限界を証明しました。70年代にこの分野の資金が崩れた原因は多く、その1つは、60年代初頭にパーセプトロンへ寄せられた約束が過大だったことです。そして技術的な障害は解けるものでしたが、まだ誰もその道具を持っていませんでした。

パーセプトロンは68歳で、あなたはいまそれを1つ書きました。このコースを終えるときの機械に、そのどの部分がまだ残っているのかを正確にしておく価値があります。答えは、思っているより多いからです。

パーセプトロンは同時に2つのものにつまずきました。そして、その2つは同じものだと分かります。

XORを表現できません。1本の直線では足りないからです。これを直すには層を積み重ねます。第1層が空間を曲げ、第2層が曲がった空間に直線を引くのです。それが第5章です。

しかし、パーセプトロンのルールでは積み重ねた層を訓練できません。このルールは「間違い」しか知らず、ネットワークの真ん中にあるユニットには、自分自身について間違えたと言えるラベルがないからです。積み重ねた層を訓練するには、すべての重みについて、どれくらい間違っているのか、どちらの方向なのかを知る必要があります。つまり傾きが必要です。そしてパーセプトロンの誤差関数、あの階段には傾きがありません。

だから、層を積む前に、使える導関数を持つ損失関数が必要です。しかも、微分しやすいから選ばれたものではいけません。どこかから導かれ、データについて真実を語り、その意味から自然に勾配が出てくるものでなければなりません。整って見えるように逆算されたものではなく。

それが第2章です。そして第2章は、パーセプトロンが答える必要のなかった問いから始まります。「この部品は良いか？」ではなく、「これが真実だとしたら、これらの測定値はどれくらいありそうか？」です。

この章とあわせて読む価値があるものも挙げておきます。Rosenblattの元論文 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) は、ニューロンを重み付き和に対するしきい値として初めてモデル化した論文です。Hal Daumé IIIの A Course in Machine Learning のパーセプトロンの節は、同じ更新を別の重点で導出しています。上の箱だけでは線形代数が物足りなかった場合は、Deisenroth, Faisal and Ongの Mathematics for Machine Learning の第2章と第3章も参考になります。