DNN の基礎を学習する

 承前LLM アプリケーションの構築に何度か携わったのですが、その結果として LLM の面白味はプラットフォーム各社が提供する LLM サービスを単に利用するだけではわからないという結論に至りました。そのため、今更ながら DNN の基礎部分から勉強し直したいと思います。
この記事では以下の２冊を並行して読み進めます。
ゼロから作る Deep Learning
ニューロコンピューティングの数学的基礎
前者は割と有名で評判のよい本ですが、冒頭を軽く眺めたところ、もう少し理論面にもしっかり踏み込んでほしい感じがしたので、家に転がっていた後者を副読本として採用することにしました。初版発行が 1993 年と少々古いですが、逆に現代では省略されそうな事柄についてもよく書かれており、個人的には気に入っています。
なお、ゼロから作る Deep Learning では Python を使った実装が示されていますが、この記事では Haskell を使用します。理由は単に筆者が Haskell を書くのが好きだからであり、それ以上の意味はありません。

dmystk

 生理学的なニューロンニューラルネットワークは脳の構造をベースにしているので、生理学的なニューロンの特定について知っておくと今後の学習の参考になる。
生理学的なニューロンは細胞体・樹状突起・軸索の３つの部位で構成され、細胞体から多数の樹状突起と一本の軸索が枝のように伸びているという形状をしている。
機能的には、信号が樹状突起から入り、細胞体で処理され、軸索から出ていくという構成になっている。それぞれの樹状突起から入った信号は細胞体内部の電位を高め、これが一定値に達すると細胞体はインパルスと呼ばれる急激な成長と減衰を伴う電気波形を形成する。そしてこのインパルスが軸索を伝って外部に出ていく、というのが基本的な流れである。なお、形成されるインパルスの波形は細胞体の電位の高さに依らず一定で、樹状突起からの入力信号がいくら大きくなっても出力されるインパルスの波形には影響しない。
軸索の先端は多くの枝に分かれており、これが他のニューロンの樹状突起に接続することで巨大なネットワークを構成している。この軸索と樹状突起の接続部分はシナプスと呼ばれ、シナプスには軸索から出てきた信号の大きさを強めたり弱めたりするフィルターのような機能がある。
ニューロンには以下の特性がある：

 非線形性樹状突起からの入力信号の大きさが一定値を超えない限りインパルスは形成されず、またインパルスが形成された場合でも樹状突起からの入力信号の大きさによらず波形は一定である。従って、生理学的なニューロンは非線形な素子であると解釈できる。

 二値性非線形性の項で述べたのと同じ理由により、軸索からの出力はインパルスが形成されるかされないかの２通りしかない。従って、生理学的なニューロンは二値の信号を扱う素子であると解釈できる。

 空間的加算性ニューロンがインパルスを形成するのは、それぞれの樹状突起から入力された信号の大きさの和が一定値を超えた場合であるとされている。従って、軸索を伝って樹状突起へやってくる信号の大きさを x_i で表し、シナプスでの信号の大きさへの作用を w_i とすると、

w_1 x_1 + w_2 x_2 + ... + w_n x_n
がある閾値を超えるかどうかによってインパルスが形成されるかどうかが決定される。この性質は空間的加算性と呼ばれる。なお、インパルスの形成に関わる閾値はニューロンごとに異なる。

 時間的加算性ある時間における軸索の信号の大きさはそれより後の時間における同信号の大きさに影響を与えることが観察されている。従って、軸索の信号の大きさを時間の関数と見なして、時刻 t における信号の大きさを x_i(t) と表すことにすると、

\int_{-\infty}^{t} v_i(t-t') x_i(t') dt'
がある閾値を超えるかどうかによってインパルスが形成されるかどうかが決定される。ただし、上記の v_i(t) は入力信号が t 時間後にどの程度インパルス形成に貢献するかを表す係数である。
時間的加算性についてはゼロから作る Deep Learning では言及すらされていないが、昨今注目されているエージェントなどの概念は時間的な広がりを持つため、研究してみる価値はありそうに思える。

dmystk

 ニューロンのモデル生理学的なニューロンを参考に様々なモデルが考案されている。

 モデル以前先に紹介したニューロンの特性の中でも空間的加算性は特に重要な特性と見なされており、以下に紹介する全てのモデルにおいて採用されている。そのため、モデルの紹介に先んじて空間的加算性に関する共通部分について説明しておく。
空間的加算性によると、軸索から樹状突起へと入力される信号の大きさを x_i とし、入力に加えられるシナプスの作用を w_i とすると、

w_1 x_1 + w_2 x_2 + ... + w_n x_n
が一定の値を超えた場合にインパルスが形成されるのであった。従って、その閾値を b とすれば、

\begin{gather}
w_1 x_1 + w_2 x_2 + ... + w_n x_n \geq b
\end{gather}
によってインパルス形成の条件を表現できるが、ここで更に w_0 = -b とすれば

\begin{gather}
w_0 + w_1 x_1 + w_2 x_2 + ... + w_n x_n \geq 0
\end{gather}
として閾値 b をシナプスの作用を表す重みと一緒くたに扱うことができる。
この式変形には式の右辺からニューロンに依存する閾値 b を排除できるという利点がある。この利点がもたらす恩恵は、ニューロンの軸索への出力を y とし、ニューロンの素子としての機能を式で表現してみるとわかりやすい。
式 (1) の場合は以下のようになる。

y = S_b(w_1 x_1 + w_2 x_2 + ... + w_n x_n)
ここで S_b はニューロンの非線形性を表現する性質を持つ何らかの関数である。この関数に添字の b を与えている理由は、生理学的なニューロンは閾値 b を境界として動作を変えるため、ニューロンの動きを適切に表現するためには閾値 b に依存する必要があることによる。閾値 b はニューロンに依存して決定されるため、実質的にこの関係式はニューロンの数だけ関数 S_b を要求する。
一方で (2) の場合、

y = S(w_0 + w_1 x_1 + w_2 x_2 + ... + w_n x_n)
のように S を b に依存しない汎用関数で表現できるため、非常に経済的である。なお、ここで示した S のような入力信号と重みの線型結合（積の和）と出力を対応づける関数のことを活性化関数と呼ぶ。

 静的デジタルモデルニューロンが形成するインパルスの電気波形はニューロン内部の電圧に依らず一定であることから、ニューロンにはインパルスを形成したかしなかったかの２通りしか状態が存在しないと考えられる。この点に着想を得て、活性化関数 S を以下のように定義することで１つのモデルを構築することができる。

S(u) = \begin{cases}
1 & (u \geq 0)\\
0 & (u < 0)
\end{cases}
より具体的には、集合 B = \{0, 1\} とその直積集合 B^n について B^n から B への関数 f を考える。この時、ある実数 w_0, w_1, w_2, ..., w_n が存在して、任意の入力 x = (x_1, x_2, ..., x_n) \in B^n に対して、

f(x) = S(w_0 + w_1 x_1 + w_2 x_2 + ... + w_n x_n)
と表せる場合に f は静的デジタルモデルであると定義する。ちなみに静的デジタルモデルで活性化関数として使用されている関数 S はステップ関数と呼ばれている。
このモデルはニューロンの時間的加算性を無視しているという意味で静的であり、またニューロンの非線形性・二値性を 0 と 1 による非連続関数で表しているという意味でデジタルである。
上記では静的デジタルモデルの構築に 0 と 1 を用いたが、代わりに -1 と 1 を用いても同様のモデルを構築することができ、さらにこの２つのモデルは等価である（一方のモデルの関数が与えられれば、同じ振る舞いをする関数をもう一方のモデルで構築できる）ことが証明できる。証明の詳細については割愛するが、それほど難しい内容ではなく、基本的に [0, 1] と [-1, 1] の２つのスケールの相互変換について考えることで自然に証明できる。

 動的デジタルモデル上記の静的デジタルモデルにニューロンの時間的加算性を加味することすることで別のモデルが得られる。つまり、入力 x_i および出力 y を時間の関数であると見なし、

y(t + 1) = S(w_0 + w_1 x_1(t) + w_2 x_2(t) + ... + w_n x_n(t))
によってモデルを構築する。これを動的デジタルモデルという。
動的デジタルモデルは有限オートマトンと等価であることが Kleene による こちら の論文で証明されている。この証明が提出されたのは 1956 年とのことで、先人の先進性の凄まじさが感じられる。

 静的アナログモデル我々は普段、音や光などの物理量を連続量として感じ取ることができる。生理学的な研究によると、これは単位時間あたりにニューロンがインパルスを形成した数、即ちパルス密度に対応した感覚であると考えられている。この観察に着目し、入力 x_i および出力 y が [0, 1] の範囲の実数値を取ると仮定し、活性化関数に以下の \sigma を使用することで１つのモデルを構築できる。

\sigma(u) = \frac{1}{1 + e^{-u}}
この関数は S 字のような曲線を描くことからシグモイド関数と呼ばれる。シグモイドとはアルファベットの S に対応するギリシャ文字の Sigma と「〜のような形状の」という意味を持つ -oid を組み合わせて作った用語である。実際の曲線の形状については Wikipedia を参照するとよい。
https://en.wikipedia.org/wiki/Sigmoid_function
こちらも静的デジタルモデルと同様に、各変数の取る範囲を [-1, 1] とし、シグモイド関数を以下のように定義することでモデルの亜種を作成することができる。

\sigma(u) = \tanh(u)
こちらについても [0, 1] と [-1, 1] の範囲で作成したモデルはそれぞれ等価であることが証明できる。基本的な証明方針は静的デジタルモデルと同じで、\tanh に関する変換公式を知っていればほとんど同じ手順で証明が行える。
生理学的なニューロンに比べると二値性が排除された形になるが、ゼロから学ぶ Deep Learning で使用されているのは [0, 1] の範囲で作成された静的アナログモデルであり、おそらくこのモデルが現代で最もベーシックなモデルであると考えられる。

 動的アナログモデル静的デジタルモデルから動的デジタルモデルを導いたのと同様に、静的アナログモデルから動的アナログモデルを導くことができる。静的アナログモデルで定めた \sigma を用いれば、

y(t + 1) = \sigma(w_0 + w_1 x_1(t) + w_2 x_2(t) + ... + w_n x_n(t))
によってニューロンの時間的加算性を考慮した１つのモデルを得ることができる。
一方で、アナログモデルは連続なシグモイド関数を使用するため、上記のような離散的に変化する時間を用いずに連続的に変化する時間を用いて動的モデルを考えることもできる。このモデルと区別するために、上記の離散的な時間変化におけるモデルは離散時間型動的アナログモデルと呼ばれる。
では連続的に変化する時間を用いた場合、モデルはどのように定義されるかというと、時間あたりの変化量が以下の微分方程式に従うと仮定する。

\frac{du}{dt} = -\frac{1}{\tau} u(t) + w_0 + w_1 x_1(t) + w_2 x_2(t) + ... + w_n x_n(t)
従って、このモデルで各時間における u の値を得るには、この微分方程式を解いた上で適当な初期条件を与えるという手順を踏む形になる。このようにして得た u をもって出力 y が \sigma を介して計算される。

y(t) = \sigma(u(t)) = \tanh(u(t))
このモデルを連続時間型動的アナログモデルと呼ぶ。結果を得るのがあまりに面倒なので使いたくはない。

dmystk

 ニューロンと論理回路B = \{0, 1\} 上で定義される静的デジタルモデルについて考える。この集合 B が持つ要素の値を真理値と見なすことで論理回路を構成することができる。真理値はどちらがどちらを表しても差し支えないが、ここでは 1 が真を、0 が偽を表すことにしておく。
この章では Haskell を使ったニューロンによる論理回路の実装まで行っていくが、先んじて静的デジタルモデルの雛形を用意しておく。静的デジタルモデルの定義に従って線型結合とステップ関数を定義すればニューロンのモデルの定義は容易である。
-- Linear Combination
lc :: Num a => [a] -> [a] -> a
lc xs ys = sum . map (uncurry (*)) $ zip xs ys

step :: (Num a, Ord a) => a -> a
step u
  | u >= 0    = 1
  | otherwise = 0

neuron :: (Num a, Ord a) => [a] -> [a] -> a
neuron ws xs = step $ lc ws (1 : xs)

 ANDまずは先ほど定義したニューロンのモデルを使って AND 回路を実装してみる。
AND 回路では２つの入力 x_1, x_2 が共に 1 の場合にのみ 1 を出力し、それ以外の場合は 0 を出力するように重み w_0, w_1, w_2 を設計する必要がある。最もシンプルな方法はそれぞれの重みが満たすべき条件を代数的に整理することだが、２入力程度であれば適当に試行しても割とすぐに設計できる。
今回は (w_0, w_1, w_2) = (-2, 1, 1) を使用して実装してみる。
and :: (Num a, Ord a) => [a] -> a
and = neuron [-2, 1, 1]
GHCi でテストした結果は以下の通り。なお、型注釈は警告抑制のためのものである。
ghci> print (and [0, 0] :: Double)
0.0
ghci> print (and [0, 1] :: Double)
0.0
ghci> print (and [1, 0] :: Double)
0.0
ghci> print (and [1, 1] :: Double)
1.0

 OR同様に OR 回路も実装してみる。重みには (w_0, w_1, w_2) = (-1, 1, 1) を使用する。
or :: (Num a, Ord a) => [a] -> a
or = neuron [-1, 1, 1]
結果は以下の通り。
ghci> print (or [0, 0] :: Double)
0.0
ghci> print (or [1, 0] :: Double)
1.0
ghci> print (or [0, 1] :: Double)
1.0
ghci> print (or [1, 1] :: Double)
1.0

 NOTNOT 回路も実装しておく。
not :: (Num a, Ord a) => [a] -> a
not = neuron [0, -1]
結果は以下。
ghci> print (not [0] :: Double)
1.0
ghci> print (not [1] :: Double)
0.0

 XORここまで順調に実装してきたので XOR も同様に実装できそうに思えるが、実はそうはいかない。これは XOR の重みが満たすべき条件を代数的に整理してみるとすぐにわかる。
XOR は入力 x_1, x_2 が 0 と 1 のペアの場合にのみ 1 を出力する、つまり

w_0 + w_1 x_1 + w_2 x_2 \geq 0
を満たすので、これから条件

\begin{gather}
w_0 + w_1 \geq 0  \\
w_0 + w_2 \geq 0
\end{gather}
を得る。他方、入力 x_1, x_2 が共に 0 および共に 1 の場合は 0 を出力するので、

w_0 + w_1 x_1 + w_2 x_2 < 0
を満たす。従って、

\begin{gather}
w_0 < 0  \\
w_0 + w_1 + w_2 < 0
\end{gather}
を得る。ここで (3) と (4) および (5) と (6) の両辺をそれぞれ足し合わせると

\begin{gather*}
2 w_0 + w_1 + w_2 \geq 0  \\
2 w_0 + w_1 + w_2 < 0
\end{gather*}
が得られるが、明らかにこの２式を同時に満たす重みの組 (w_0, w_1, w_2) は存在しない。従って、静的デジタルモデルの単一のニューロンだけでは XOR 回路は実現できない。この問題は XOR Problem としてよく知られている。
より俯瞰的な視点で見ると、論理回路の構成は入力となる B^n を 0 と 1 のどちらを出力するかに分類するという作業に等しい。一方で、その分類の条件に関わる式

w_0 + w_1 x_1 + w_2 x_2 + ... + w_n x_n = 0
は n 次元ユークリッド空間の平面を記述する式であり、B^n はその空間における超立方体の頂点の集合である。つまり、単一のニューロンでできるのは平面で超立方体の頂点を分離することのみであり、平面だけでは分離しきれないような出力を持つ論理回路は表現できない。要するに出力が線形分離可能であるような論理回路しか作ることができないのである。
XOR は線形分離不可能な出力を持つ論理回路の好例で、これが単一のニューロンで実現できない様子については以下の Qiita の記事に掲載されている画像を見るとわかりやすい。
https://qiita.com/forusufia/items/53de18be0e07b258fc76#おまけ線形分離できない論理回路の例

 多層化しかしながら、AND・OR・NOT が既に実装されているので、そこから XOR を構成できるという点に気がついた人も多いだろう。実際、\lnot(x_1 \land x_2) \land (x_1 \lor x_2) とすれば XOR が実現できる。
\lnot (x_1 \land x_2) は単に NOT と AND の組み合わせでも実装できるが、NAND 回路として単一のニューロンでも実装できる。こちらの方が実装がシンプルになるので、今回はこちらを採用する。
nand :: (Num a, Ord a) => [a] -> a
nand = neuron [1, -1, -1]
ghci> print (nand [0, 0] :: Double)
1.0
ghci> print (nand [0, 1] :: Double)
1.0
ghci> print (nand [1, 0] :: Double)
1.0
ghci> print (nand [1, 1] :: Double)
0.0
あとは NAND と OR を組み合わせて XOR を実装すればよい。
xor :: (Num a, Ord a) => [a] -> a
xor xs = and [nand xs, or xs]
ghci> print (xor [0, 0] :: Double)
0.0
ghci> print (xor [0, 1] :: Double)
1.0
ghci> print (xor [1, 0] :: Double)
1.0
ghci> print (xor [1, 1] :: Double)
0.0
このように複数のニューロンを組み合わせて多層構成をとることで XOR をはじめとする線形分離不可能な出力を持つ論理回路も実現することができる。
多層構成のニューロンがどれくらいの表現能力を持つのかが気になるかもしれないが、実はこれに答えるのは簡単である。というのは、NAND 回路には完全性があり、どんな論理回路も NAND 回路を使って組み上げることができることが知られている。従って、先ほどしれっと行なった NAND 回路の実装により、静的デジタルモデルのニューロンの多層構成で任意の論理回路が得られることがわかる。

 加法標準形先ほどは２層構成のニューロンで XOR 回路を作成したが、実は２層構成のニューロンだけでどんな論理回路も作れることが証明できる。これは任意の論理式が加法標準形という形式の同等な式に書き直すことができ、かつこの加法標準形の式は２層構成のニューロンで実現可能であるという事実に由来する。
n 変数の論理式 f は

\begin{align*}
& f(x_1, x_2, ..., x_n)  \\
& \quad
\begin{alignedat}{6}
{}={} & (f(0, 0, ..., 0) & {}\land{} & (\lnot x_1) & {}\land{} & (\lnot x_2) & {}\land{} & ... & {}\land{} & (\lnot x_n))  \\
{}\lor{} & (f(1, 0, ..., 0) & {}\land{} & \quad x_1 & {}\land{} & (\lnot x_2) & {}\land{} & ... & {}\land{} & (\lnot x_n))  \\
{}\lor{} & (f(0, 1, ..., 0) & {}\land{} & (\lnot x_1) & {}\land{} & \quad x_2 & {}\land{} & ... & {}\land{} & (\lnot x_n))  \\
{}\lor{} & (f(1, 1, ..., 0) & {}\land{} & \quad x_1 & {}\land{} & \quad x_2 & {}\land{} & ... & {}\land{} & (\lnot x_n))  \\
& ...  \\
{}\lor{} & (f(1, 1, ..., 1) & {}\land{} & \quad x_1 & {}\land{} & \quad x_2 & {}\land{} & ... & {}\land{} & \quad x_n\; )
\end{alignedat}
\end{align*}
のような加法標準形に書き直すことができる。加法標準形は \land で構成された 2^n 個の論理式が \lor で接続されている構成になっており、f に入力が与えられると \land で構成された論理式のうちの１つのみが真になり、それ以外は偽になるような設計になっている。
加法標準形の \land で構成された論理式はいずれも１つのニューロンだけで実現することができる。

\begin{align*}
& f(0, 0, ..., 0) \land (\lnot x_1) \land (\lnot x_2) \land ... \land (\lnot x_n)  \\
& \quad = S(n - 1 + f(0, 0, ..., 0) + (x_1 - 1) + (x_2 - 1) + ... + (x_n - 1))  \\
& f(1, 0, ..., 0) \land x_1 \land (\lnot x_2) \land ... \land (\lnot x_n)  \\
& \quad = S(n - 1 + f(1, 0, ..., 0) + x_1 + (x_2 - 1) + ... + (x_n - 1))  \\
& ...  \\
& f(1, 1, ..., 1) \land x_1 \land x_2 \land ... \land x_n  \\
& \quad = S(n - 1 + f(1, 1, ..., 1) + x_1 + x_2 + ... + x_n)
\end{align*}
また n 個の入力 x_1, x_2, ..., x_n に対する論理和は以下のように定義できる。

S(-1 + x_1 + x_2 + ... + x_n)
従って、任意の論理式は２層構成のニューロンで作成可能であることがわかる。

dmystk

 古典パーセプトロン現代の DNN は Rosenblatt が 1958 年に発表したパーセプトロンと呼ばれるモデルをその起源とする。パーセプトロンは視覚系のパターン認識のためのモデルとして開発されたモデルで、感覚層・連合層・反応層の３つの階層からなる。Rosenblatt が書いた 論文 にはその様子を表現した図が掲載されている。
図の一番左が網膜を表しており、網膜から入ってきた信号が感覚層 (Projection Area) に渡り、そこからさらに連合層 (Association Area) を経由して反応層 (Responses) に伝わる様子が描かれている。
上の図では網膜も含めた４つの層が描かれているが、情報処理の観点では網膜は重要でないので省略されるのが一般的である。また、上の図では反応層に複数のニューロンが描かれているが、元々パーセプトロンは二値分類問題のためのモデルであり、反応層には１つのニューロンしか存在しない（即ち反応層のニューロンが 0 と 1 のいずれの値をとるかで二値分類の機能を果たせる）とする定義になっている。
感覚層・連合層・反応層の間で行われる処理は、先に述べた静的デジタルモデルに従う。つまり 0 か 1 のいずれかの値のみを取る感覚層の値 x_i に対して、連合層の値 y_j は

y_j = S(w_{0j} + w_{1j} x_1 + ... + w_{nj} x_n)
によって決定される。シナプスによる作用を表す重みはニューロンごとに異なるため、重みの添字に j が現れている点に注意が必要である。
同様に連合層の値 y_j に対して反応層の値 z は

z = S(v_0 + v_1 y_1 + ... + v_m y_m)
となる。ここで v_j は連合層の値 y_j に対するシナプスの作用を表す重みである。
なお、上で述べた y_i は感覚層の値 x = (x_1, ..., x_n) に関する関数なので、これを

\begin{gather*}
f_j(x) = S(w_{0j} + w_{1j} x_1 + ... + w_{nj} x_n)  \\
f(x) = (f_1(x), ..., f_m(x))
\end{gather*}
とし、同様に z も連合層の値 y = (y_1, ..., y_m) に関する関数なので

g(y) = S(v_0 + v_1 y_1 + ... + v_m y_m)
とすれば、パーセプトロン全体を合成関数 h = f \circ g で簡潔に表すことができる。
先述の通り、パーセプトロンは視覚系のパターン認識に関わる二値分類のために考案されたモデルではあるが、現代では DNN をはじめとするより広範な用途の基礎として用いられている。そのため、視覚系に起源を持つ感覚層・連合層・反応層という名前は廃れ、現代では入力層・隠れ層・出力層という名前で呼ばれている。この記事でも以降はこの呼称に従うことにする。
また、モデルの提案当初は静的デジタルモデルが採用されていたが、現代では静的アナログモデルの方が主流となっている。そのため、ニューロコンピューティングの数学的基礎では、静的デジタルモデルを採用したオリジナルのモデルを古典パーセプトロンと呼び、静的アナログモデルを採用したモデルを現代パーセプトロンと呼んで区別している。この記事でもこの呼称に従うことにする。

 古典パーセプトロンの実装早速実装してみる。
perceptron :: (Num a, Ord a) => [[a]] -> [a] -> [a] -> a
perceptron wss vs xs =
  let ys = map (\ws -> neuron ws xs) wss
  in  neuron vs ys
リストを使用している影響で若干型定義の内容が分かりづらいが、要素数を明示できる依存型 Vect を使った擬似コードで表すと多少マシになる。
perceptron :: (Num a, Ord a)
    => (Vect m (Vect n a))  -- w_ij
    -> (Vect m a)           -- v_j
    -> (Vect n a)           -- x_i
    -> a                    -- z
もちろんこの時点で実行可能ではあるが、結果が非常に分かりづらいので、後で学習アルゴリズムを実装した際にまとめて確認することにする。（ちなみにここからしばらくは理論面の記述が続く）

 重みの決定に対する方程式的アプローチ古典パーセプトロンは重みによって振る舞いが決定される B^n から B への関数であるが、既に述べた通り、これは二値分類のための操作と見なすことができる。従って、B^n の互いに素な部分集合 X_0, X_1 に対して

\begin{gather*}
\forall x \in X_0, h(x) = 0  \\
\forall x \in X_1, h(x) = 1
\end{gather*}
を満たすような重みを決定する方法を見出したいと考えるのは自然なことである。
すぐに思いつく方法は古典パーセプトロンの式が与える連立方程式を解くことであるが、f と g は共に非線形な関数であり、これらの合成関数を代数的あるいは解析的に解くのは限りなく難しい。そのため、f に関する重み w_i を全て固定し、問題を g に関する重み v_j のみを対象とするように簡略化してみる。
X_0, X_1 の f による B^m 上の像を Y_0, Y_1 とすると

\begin{gather*}
\forall y \in Y_0, g(y) = 0  \\
\forall y \in Y_1, g(y) = 1
\end{gather*}
が満たされれば目的の二値分類が果たされる。ただし、Y_0 と Y_1 が共通部分を持つ場合は明らかに g による分類が不可能であるため、Y_0 と Y_1 は互いに素であることにしておく。
上記の式を満たすためには

\begin{gather*}
\forall y \in Y_0, v_0 + v_1 y_1 + ... + v_m y_m < 0  \\
\forall y \in Y_1, v_0 + v_1 y_1 + ... + v_m y_m \geq 0  \\
\end{gather*}
を満たす必要があり、これが解くべき連立方程式である。これで式としてはかなり簡単になったが、実はそれでもこの連立方程式を代数的ないし解析的に解くのは困難である。[1]
古典パーセプトロンの式を直接解くのはあまりにも難しいので、ここで方針を転換して直接的な解ではなく近似解を得る方法を模索してみる。つまり、Y_0, Y_1 に対して目的関数

d(y) = \begin{cases}
0 & (y \in Y_0)  \\
1 & (y \in Y_1)  \\
\text{any} & (\text{otherwise})
\end{cases}
を定義し、これを g で近似する方法を模索する。d と g の誤差は Y = Y_0 \cup Y_1 として

E = \frac{1}{2|Y|} \sum_{y \, \in \, Y} (g(y) - d(y))^2
からなる二乗誤差としておく。右辺が 2 で割られているのは後の計算を簡単にするためで、深い意味はない。
近似解を求める最もナイーブな方法は誤差関数を微分して極点を求めることである。つまり E を微分してその値が 0 となる点を求めればよい。従って、

\frac{\partial E}{\partial v_j}
=\frac{1}{|Y|} \sum_{y \, \in \, Y} (g(y) - d(y)) \frac{\partial g}{\partial v_j}(y)
= 0
を方程式として解きたいところだが、残念ながら g は非連続なステップ関数に依存しているためそもそも微分不可能である。とはいえ、g はシグモイド関数の指数部に適切な係数を与えることで任意の精度で近似できるので、この問題には目を瞑ってもよい。しかし、残念なことに、そこまでしてもこの方程式を解くのはやはり困難である。[2]
非線形関数が強すぎる ... 。

 重みの決定に対する力学的アプローチ古典パーセプトロンに関する方程式を解いて解を得るのは絶望的なので、ここで発想の転換を行い、v_j を時間に依存する関数であると考えてみる。そして v_j に以下の微分方程式を与え、古典パーセプトロン全体が重みの時間的展開を伴うある種の力学系であると見なしてみる。[3]

\begin{gather}
\frac{dv_j}{dt} = - \frac{\partial E}{\partial v_j}
\end{gather}
右辺はいかにも恣意的である。実際、これは時間 t に対して誤差 E が非増加となるように設計された式である。つまり、

\frac{dE}{dt} \leq 0
が成り立つ。これは実際に E を t で微分することで証明できる。

\begin{gather}
\frac{dE}{dt} = \sum_{j=0}^{m} \frac{\partial E}{\partial v_j} \frac{dv_j}{dt}
\end{gather}
(7) と (8) を合わせれば

\frac{dE}{dt} = - \sum_{j=0}^{m} \left( \frac{\partial E}{\partial v_j} \right)^2 \leq 0
である。この式から等号が成り立つのは全ての j に対して以下が成り立つ時、かつこの時に限ることもわかる。

\frac{\partial E}{\partial v_j} = 0
この性質によれば、誤差 E は零点に達しない限り時間経過で単調減少し続ける。従って、この微分方程式を解き、時間 t を十分に大きくとった上で v_j の値を計算すれば、誤差 E の極小値が得られるかもしれないという希望がある。ただし、零点が必ずしも極点とは限らない点には注意が必要である。これは こちら に掲載されている画像を見れば一瞬で理解できる。
とはいえ、微分方程式を真っ当に解くのはやはり絶望的なので、ここで

\frac{dv_j}{dt} \simeq \frac{v_j(t + \Delta t) - v_j(t)}{\Delta t}
という近似を施す。微分の定義から極限を取り去り、代わりに十分小さい値 \Delta t を利用することにすれば、この近似が得られる。これを (7) と合わせると

\begin{gather}
v_j(t + \Delta t) = v_j(t) - \Delta t \frac{\partial E}{\partial v_j}
\end{gather}
という漸化式が得られる。ここで

\frac{\partial E}{\partial v_j}
=\frac{1}{|Y|} \sum_{y \, \in \, Y} (g(y) - d(y)) \frac{\partial g}{\partial v_j}(y)
であり、シグモイド関数によってステップ関数 S が十分に近似されていると仮定すると

\begin{align*}
\frac{\partial g}{\partial v_j}(y)
& = S'(v_0 + v_1 y_1 + ... + v_m y_m) \frac{\partial}{\partial v_j} (v_0 + v_1 y_1 + ... + v_m y_m)  \\
& = S'(v_0 + v_1 y_1 + ... + v_m y_m) y_j
\end{align*}
なので、これらを (9) に代入すると、

\begin{align*}
v_j(t + \Delta t)
& = v_j(t) - \Delta t \frac{\partial E}{\partial v_j}  \\
& = v_j(t) - \frac{\Delta t}{|Y|} \sum_{y \, \in \, Y} (g(y) - d(y)) \frac{\partial g}{\partial v_j}(y)  \\
& = v_j(t) - \frac{\Delta t}{|Y|} \sum_{y \, \in \, Y} (g(y) - d(y)) S'(v_0 + v_1 y_1 + ... + v_m y_m) y_j
\end{align*}
という漸化式が得られる。ただし、v_0 のために便宜上 y_0 = 1 としておく。
整理のために

\delta(y) = (g(y) - d(y)) S'(v_0 + v_1 y_1 + ... + v_m y_m)
とすれば

\begin{gather}
v_j(t + \Delta t) = v_j(t) - \frac{\Delta t}{|Y|} \sum_{y \, \in \, Y} \delta(y) y_j
\end{gather}
となる。
この漸化式は、ある時点の重みに対して Y が持つ全要素の誤差を勘案したフィードバックを施すことで次の重みが得られることを表しているが、実はもう少し細かい単位に修正することができる。Y が N 個の要素を持つと仮定し、単位時間 \Delta t を N 等分して Y の要素を１つずつ与える形に修正するのである。つまり、

Y = \{ y^{(1)}, ..., y^{(N)} \}
として

\begin{gather}
v(t + \frac{k}{N} \Delta t)
= v(t + \frac{k - 1}{N} \Delta t) - \frac{\Delta t}{N} \delta(y^{(k)}) y^{(k)}_j
\end{gather}
とする。ただし k = 1, ..., N である。全ての k について (11) の両辺を足し合わせれば (10) が得られるので、これらの漸化式は実質的に同じものである。

 \delta 学習則(11) の漸化式によれば Y の要素を無限に繰り返して得られる列

\begin{align}
y^{(1)}, ..., y^{(N)}, y^{(1)}, ..., y^{(N)}, ...
\end{align}
を古典パーセプトロンに入力することで重み v_j を近似的に求めることができるようになる。これを見て、まさに「学習」そのものであると直感した人もいるだろう。実際、式 (11) による重みの近似の過程を学習と呼び、式 (12) を学習パターンと呼ぶ。
式 (11) が現在の重みを新しい重みに修正するための規則を表しているという点を強調するために、式を以下のように書き直すとわかりやすい。

v^{\text{new}}_j = v^{\text{old}}_j - \epsilon \delta(y) y_j
この式は古典パーセプトロンがニューロンの重みを修正する規則を表していることから \delta 学習則と呼ばれる。また、この式の \delta(y) を誤差信号と呼び、\epsilon を学習率と呼ぶ。

 パーセプトロン学習則\delta 学習則の導出ではステップ関数をシグモイド関数で近似していたため、近似なしのステップ関数でも適切に機能するかどうかについては疑問の余地がある。そこで \delta 学習則を参考にしつつ \delta(y) から S' を取り去った新たな学習則を作り、その学習則の下で学習が適切に機能することを確かめたい。
S はステップ関数なので S' は原点以外では 0 となるはずである。従って、S'(u) = 0 と仮定するのが自然に思えるが、これでは誤差信号が全て 0 になってしまい、学習が全く進まなくなってしまう。そのため論理的整合性をかなぐり捨てて S'(u) = 1 とおき

\delta(y) = g(y) - d(y)
として以下の新たな学習則を得る。

\begin{gather}
\begin{align*}
v^{\text{new}}_j
& = v^{\text{old}}_j - \epsilon \delta(y) y_j  \\
& = v^{\text{old}}_j - \epsilon (g(y) - d(y)) y_j
\end{align*}
\end{gather}
この式はパーセプトロン学習則と呼ばれる。このパーセプトロン学習則がステップ関数を使用した状態でも適切に機能することを確認してみる。
古典パーセプトロンが正しい結果を出力した場合、即ち g(y) = d(y) だった場合は \delta(y) = 0 となるため、現状の重みが維持されることが直ちにわかる。一方で古典パーセプトロンが誤った結果を出力した場合、即ち g(y) \neq d(y) だった場合は話が少々複雑なので、場合分けをして考えていく。
まずは y \in Y_0 の場合について考えてみる。この場合は d(y) = 0 かつ g(y) = 1 なので、式 (13) の右辺は v^{\text{old}}_j - \epsilon y_j となる。従って、y_j が 0 の場合、第２項の値が 0 になり現状の重みが維持される。結果に寄与しなかった入力に対する重みが修正されないという意味で、これは望ましい振る舞いと言える。また y_j が 1 の場合、第２項は負の値となり重みの値が減少するが、ここで

g(y) = S(v_0 + v_1 y_1 + ... + v_m y_m)
であったことを思い出すと、重みの減少はステップ関数の出力が 0 になる方向に近づくので、これも望ましい振る舞いと言える。y \in Y_1 の場合についても同様に確認でき、学習によって重みが適切な方向に調整されることがわかる。

 学習のアルゴリズム（工事中）

脚注
実のところ、古典パーセプトロンでは f に関する重み w_i を決定するのは困難を極めるため、以降の古典パーセプトロンについての議論では専らこの簡略化したモデルを対象に v_i を決定する方法のみを扱うことになる。なお、この w_i の決定の困難さが研究対象を古典パーセプトロンから現代パーセプトロンに遷移させる直接の原因となっている。 ↩︎
ニューロコンピューティングの数学的基礎にはこのように書いてあるが、実際に解くことが不可能だと証明されたかどうかについては言及されていない。有識者がいれば教えてほしい。 ↩︎
筆者の不勉強を告白しておくと、ニューロコンピューティングの数学的基礎の該当箇所を初めて読んだ際、力学系という言葉の意味を勘違いしており内容を全く理解できなかった。力学系とは「一定の規則に従って時間の経過とともに状態が変化する系」という意味である。時間による展開が重要なのであって、力はあまり関係ない。（戒め ↩︎