パーセプトロン

パーセプトロンはプログラムではなく機械として意図されており、最初の実装はIBM 704用のソフトウェアでしたが、その後、画像認識用に設計された「Project PARA」というプロジェクト名でMark Iパーセプトロンとしてカスタム構築されたハードウェアに実装されました^{[ 17 ]} 。この機械は現在、スミソニアン国立アメリカ歴史博物館にあります^{[ 18 ]}。

マークIパーセプトロンは3層構造であった。あるバージョンは以下のように実装された。

• 20×20のグリッド状に配置された400個の光電セルからなるアレイは、「感覚ユニット」（Sユニット）または「入力網膜」と呼ばれる。各Sユニットは最大40個のAユニットに接続できる。
• 512個のパーセプトロンからなる隠れ層があり、「連想ユニット」（Aユニット）と呼ばれている。
• 出力層は8つのパーセプトロンからなり、「応答ユニット」（Rユニット）と呼ばれる。

ローゼンブラットはこの3層パーセプトロンネットワークをアルファパーセプトロンと呼び、彼が実験した他のパーセプトロンモデルと区別した。^{[ 9 ]}

Sユニットは、プラグボードを介して（乱数表に従って）ランダムにAユニットに接続され（写真参照）、パーセプトロンにおける特定の意図的なバイアスを排除します。接続重みは固定されており、学習されません。ローゼンブラットは、網膜が視覚皮質にランダムに接続されていると信じており、彼のパーセプトロンマシンが人間の視覚知覚に似ていることを望んでいたため、ランダムな接続に固執しました。^{[ 19 ]}

AユニットはRユニットに接続されており、調整可能な重みはポテンショメータにエンコードされ、学習中の重みの更新は電気モーターによって実行されました。^{[ 2 ]： 193}ハードウェアの詳細はオペレーターズマニュアルに記載されています。^{[ 17 ]}

1958年に米国海軍が主催した記者会見で、ローゼンブラットはパーセプトロンについて発言し、黎明期のAIコミュニティの間で激しい論争を引き起こした。ローゼンブラットの発言に基づき、ニューヨーク・タイムズはパーセプトロンを「海軍が歩行、会話、視覚、筆記、自己複製、そして自己存在の認識が可能になると期待している電子コンピュータの胚芽」と報じた。^{[ 20 ]}

中央情報局の写真部門は、1960年から1964年にかけて、航空写真から軍事的に興味深いシルエット目標（飛行機や船など）を認識するために、マークIパーセプトロンマシンの使用を研究した。^{[ 21 ] [ 22 ]}

ローゼンブラットは、パーセプトロンマシンのさまざまなバリエーションを用いた実験について、著書『神経力学の原理』（1962年）で述べている。この本は、1961年の報告書を出版したものである。^{[ 23 ]}

バリエーションには以下のようなものがある。

• 「クロスカップリング」（同じ層内のユニット間の接続）と、場合によっては閉じたループ、
• 「バックカップリング」（後の層のユニットから前の層のユニットへの接続）
• 最後の 2 層に調整可能な重みを持つ 4 層パーセプトロン (したがって、適切な多層パーセプトロン)
• パーセプトロンユニットに時間遅延を組み込むことで、シーケンシャルデータの処理を可能にする。
• 画像ではなく音声を分析する。

この機械は、海軍研究局が管理する政府移管により、1967年にコーネル大学からスミソニアン博物館へ輸送された。^{[ 10 ]}

パーセプトロンは当初有望視されていたものの、多くの種類のパターンを認識するように訓練することはできないことがすぐに明らかになった。このため、ニューラルネットワークの研究分野は長年停滞したが、その後、2層以上のフィードフォワードニューラルネットワーク（多層パーセプトロンとも呼ばれる）は、1層のパーセプトロン（単層パーセプトロンとも呼ばれる）よりも処理能力が高いことが認識されるようになった。

単層パーセプトロンは、線形分離可能なパターンしか学習できません。 ^{[ 24 ]}ステップ活性化関数を持つ分類タスクでは、単一のノードは、パターンを形成するデータポイントを分割する単一の線を持ちます。ノードを増やすと分割線が増えますが、それらの線は何らかの方法で結合して、より複雑な分類を形成する必要があります。2 層目のパーセプトロン、あるいは線形ノードでも、分離不可能な多くの問題を解決するのに十分です。

1969 年、マービン・ミンスキーとシーモア・パパートによる有名な書籍『パーセプトロン』では、これらの種類のネットワークがXOR関数を学習することは不可能であることが示されました。 彼らが同様の結果が多層パーセプトロン ネットワークにも当てはまると推測したと誤って信じられることがよくあります。 しかし、これは正しくありません。ミンスキーとパパートは、多層パーセプトロンが XOR 関数を生成できることを既に知っていたからです。 (詳しくは、パーセプトロン (書籍)のページを参照してください。) それにもかかわらず、しばしば誤って引用されるミンスキーとパパートのテキストは、ニューラル ネットワーク研究への関心と資金の大幅な減少を引き起こしました。 ニューラル ネットワーク研究が 1980 年代に復活するまでには、さらに 10 年かかりました。^{[ 24 ]}このテキストは 1987 年に「パーセプトロン - 拡張版」として再版され、元のテキストのいくつかの誤りが示され、修正されています。

ローゼンブラットは資金が減ってもパーセプトロンの研究を続けた。最後の試みは、1961年から1967年にかけて構築された音声認識用のトバーモリーであった。^{[ 25 ]}それは部屋全体を占めていた。^{[ 26 ]}トロイダル磁気コアによって実装された12,000個の重みを持つ4層構造であった。完成する頃には、デジタルコンピュータによるシミュレーションは、専用のパーセプトロンマシンよりも高速になっていた。^{[ 27 ]}彼は1971年にボート事故で亡くなった。

IBM 7090/7094用にニューラルネットワークのシミュレーションプログラムが作成され、文字認識、バブルチャンバー写真の粒子軌跡、音素、単語、連続音声認識、話者照合、画像処理の注意中心メカニズムなど、さまざまなパターン認識アプリケーションを研究するために使用されました。^{[ 28 ] [ 29 ]}

カーネルパーセプトロンアルゴリズムは、1964 年に Aizerman らによって既に導入されていました。^{[ 30 ]}一般的な非分離ケースにおけるパーセプトロンアルゴリズムのマージン境界保証は、最初にFreundとSchapire (1998) によって与えられ、^{[ 1 ]}最近ではMohriと Rostamizadeh (2013) によって以前の結果を拡張し、より好ましい新しい L1 境界を与えています。^{[ 31 ] [ 32 ]}

パーセプトロンは生物学的ニューロンの単純化されたモデルです。生物学的ニューロンモデルの複雑さは神経の挙動を完全に理解するためにしばしば必要となりますが、パーセプトロンのような線形モデルが実際のニューロンに見られる挙動の一部を再現できることが研究で示唆されています。^{[ 33 ]}

すべての二値関数と学習行動の決定境界の解空間は、^{[ 34 ]で研究されています。}

情報理論の観点から、 K個の入力を持つ単一のパーセプトロンは2Kビットの情報容量を持つ。^{[ 35 ]}この結果はトーマス・カバーによるものである。^{[ 36 ]}

具体的には、${\displaystyle T(N,K)}$K次元空間でN個の点を線形分離する方法の数をとする。$${\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}}\right)&K<N\end{array}}\right.}$$Kが大きい場合、${\displaystyle T(N,K)/2^{N}}$1に非常に近い${\displaystyle N\leq 2K}$しかし、ゼロに非常に近いのは${\displaystyle N>2K}$言い換えれば、1 つのパーセプトロンユニットは、N 点に対するバイナリ ラベルのランダムな割り当てをほぼ確実に記憶することができます。${\displaystyle N\leq 2K}$しかし、ほぼ確実にそうではない${\displaystyle N>2K}$。

バイナリ入力のみで動作する場合、パーセプトロンは線形分離可能なブール関数、または閾値ブール関数と呼ばれます。n個の入力に対する閾値ブール関数の数列はOEIS A000609です。その値は正確にはまでしかわかりません。${\displaystyle n=9}$ケースではあるが、桁数は正確にわかっている。上限は${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$下限${\displaystyle 2^{n^{2}-n\log _{2}n-O(n)}}$[ ^{37 ]​}

任意のブール線形閾値関数は、整数重みのみで実装できます。さらに、単一の整数重みパラメータを表現するために必要かつ十分なビット数は、${\displaystyle \Theta (n\ln n)}$[ ^{37 ]​}

単一のパーセプトロンは、任意の半空間を分類することを学習できます。しかし、ブール論理の排他的論理和問題（有名な「XOR問題」）のような、線形分離不可能なベクトルを解くことはできません。

隠れ層が1つだけのパーセプトロンネットワークは、任意のコンパクトな部分集合を任意の精度で分類することを学習できます。同様に、任意のコンパクトな台を持つ連続関数を任意の精度で近似することもできます。これは本質的に、ジョージ・サイベンコとカート・ホーニックの定理の特殊なケースです。

パーセプトロン（ミンスキーとパパート、1969年）は、様々なブール関数を学習するために必要なパーセプトロンネットワークの種類を研究した。

パーセプトロンネットワークを考えてみましょう。${\displaystyle n}$入力ユニット、1 つの隠れ層、および 1 つの出力で構成され、Mark I パーセプトロンマシンに似ています。ブール関数を計算します。${\displaystyle f:2^{n}\to 2}$それらは、次数 の関数を結合的にローカルと呼ぶ。${\displaystyle k}$隠れ層の各ユニットが最大で${\displaystyle k}$入力単位。

定理（定理3.1.1）：パリティ関数は次数で結合的に局所的である。${\displaystyle n}$。

定理（第5.5節）：連結関数は次数で結合的に局所的である。${\displaystyle \Omega (n^{1/2})}$。

まず、いくつかの変数を定義します。

• ${\displaystyle r}$はパーセプトロンの学習率です。学習率は正の数で、通常は1未満に設定されます。値が大きいほど、重みの変化が不安定になる可能性が高くなります。
• ${\displaystyle D=\{(\mathbf {x} _{1},d_{1}),\dots ,(\mathbf {x} _{s},d_{s})\}}$トレーニングセットは${\displaystyle s}$サンプル、ここで：
  • ${\displaystyle \mathbf {x} _{j}}$は${\displaystyle j}$番目の入力ベクトルから${\displaystyle n}$次元ユークリッド空間${\displaystyle \mathbb {R} ^{n}}$。
  • ${\displaystyle d_{j}\in \{0,1\}}$これは、その入力に対するパーセプトロンの望ましい出力値です。

各特徴量の値は以下のとおりです。

• ${\displaystyle x_{j,i}}$の値は${\displaystyle i}$の th 機能${\displaystyle j}$th トレーニング入力ベクトル。
• ${\displaystyle x_{j,0}=1}$。

重みを表すには：

• ${\displaystyle w_{i}}$は${\displaystyle i}$重みベクトル内の 番目の値、 の値で乗算されます。${\displaystyle i}$入力機能。
• なぜなら${\displaystyle x_{j,0}=1}$、${\displaystyle w_{0}}$これは実質的にバイアス定数の代わりに使用するバイアスです${\displaystyle b}$。

時間依存性を示すために${\displaystyle \mathbf {w} }$私たちは以下を使用します：

• ${\displaystyle w_{i}(t)}$重さは${\displaystyle i}$その時${\displaystyle t}$。

オフライン学習の場合、反復エラーが発生するまで2番目のステップを繰り返すことができます。${\displaystyle {\frac {1}{s}}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|}$ユーザーが指定したエラーしきい値よりも小さい${\displaystyle \gamma }$または、所定の反復回数が完了した。ここで、sはサンプルセットのサイズである。

アルゴリズムはステップ2bの各トレーニングサンプル後に重みを更新しますが、重みは変更されないことに注意する必要があります。${\displaystyle d_{j}=y_{j}(t)}$。

単一のパーセプトロンは線形分類器です。すべての入力ベクトルが正しく分類された場合にのみ、安定状態に到達できます。訓練セットD が線形分離可能でない 場合、つまり、正例と負例を超平面で分離できない場合は、解が存在しないため、アルゴリズムは収束しません。したがって、訓練セットの線形分離可能性が事前にわからない場合は、以下の訓練方法のいずれかを使用する必要があります。収束定理の詳細な分析と拡張については、『パーセプトロン』（1969 年）の第 11 章を参照してください。

線形分離可能性は時間的にテスト可能である${\displaystyle \min(O(n^{d/2}),O(d^{2n}),O(n^{d-1}\ln n))}$、 どこ${\displaystyle n}$はデータポイントの数であり、${\displaystyle d}$は各点の次元です。^{[ 38 ]}

トレーニングセットが線形分離可能であれば、パーセプトロンは有限回の誤りを犯した後、収束することが保証される。^{[ 39 ]}この定理は Rosenblatt らによって証明されている。

以下の簡単な証明は、ノビコフ (1962) によるものです。証明の考え方は、重みベクトルは常に、負のドット積を持つ方向に一定の量だけ調整されるため、重みベクトルの変更回数をtとすると、O ( √ t )で上限が定められるということです。しかし、満足できる (未知の) 重みベクトルが存在する場合、すべての変更はこの (未知の) 方向に入力ベクトルのみに依存する正の量だけ進むため、O ( t )で下限も定められます。

パーセプトロンアルゴリズムは、線形分離可能な訓練セットの場合、何らかの解に収束することが保証されているが、それでも任意の解を選択する可能性があり、問題によってはさまざまな品質の多くの解が存在する可能性がある。^{[ 40 ]}最適安定性パーセプトロン（現在では線形サポートベクターマシンとしてよく知られている）は、この問題を解決するために設計された（Krauth and Mezard、1987）。^{[ 41 ]}

データセットが線形分離可能でない場合、単一のパーセプトロンが収束する方法はありません。しかし、それでも^{[ 42 ]}

これはブラッドリー・エフロンによって最初に証明された。^{[ 43 ]}

次のようなデータセットを考えてみましょう。${\displaystyle x}$から${\displaystyle \{-1,+1\}^{n}}$すなわち、原点を中心とするn次元超立方体の頂点であり、${\displaystyle y=\theta (x_{i})}$つまり、正の値を持つすべてのデータポイント${\displaystyle x_{i}}$持っている${\displaystyle y=1}$、そしてその逆も同様です。パーセプトロン収束定理によれば、パーセプトロンは最大で を した後で収束します。${\displaystyle n}$間違い。

同じタスクを実行する論理プログラムを作成する場合、各正例は座標の 1 つが正しいものであることを示し、各負例はその補数が正例であることを示します。既知のすべての正例を収集することにより、最終的に 1 つの座標を除くすべての座標が削除され、その時点でデータセットが学習されます。^{[ 44 ]}

この境界は、最悪の場合に関して漸近的にタイトである。最悪の場合、最初に提示された例は全く新しいものであり、${\displaystyle n}$情報ビットですが、後続の各例は前の例と最小限の違いしかなく、それぞれ1ビットずつ与えます。${\displaystyle n+1}$例として、${\displaystyle 2n}$情報ビットはパーセプトロンにとって十分である（${\displaystyle 2n}$情報のビット）。^{[ 35 ]}

しかし、例が均一にランダムに提示される場合、期待値の観点からはタイトではない。なぜなら、最初の例では${\displaystyle n}$ビット、2番目${\displaystyle n/2}$ビットなど、${\displaystyle O(\ln n)}$合計例数。^{[ 44 ]}

線形分類器を訓練するための他のほとんどの手法と同様に、パーセプトロンは多クラス分類に自然に一般化できます。ここで、入力は${\displaystyle x}$そして出力${\displaystyle y}$任意の集合から抽出される。特徴表現関数${\displaystyle f(x,y)}$各可能な入力/出力ペアを有限次元の実数値特徴ベクトルにマッピングします。これまでと同様に、特徴ベクトルは重みベクトルと乗算されます。${\displaystyle w}$しかし、現在では、得られたスコアを使用して、多数の可能な出力の中から選択するようになっています。

${\displaystyle {\hat {y}}=\operatorname {argmax} _{y}f(x,y)\cdot w.}$

学習は再び例を繰り返し、それぞれに対して出力を予測し、予測された出力が目標と一致する場合は重みを変更せず、一致しない場合は重みを変更します。更新は次のようになります。

${\displaystyle w_{t+1}=w_{t}+f(x,y)-f(x,{\hat {y}}).}$

このマルチクラスフィードバック定式化は、次の場合に元のパーセプトロンに帰着する。${\displaystyle x}$は実数値ベクトルであり、${\displaystyle y}$から選ばれる${\displaystyle \{0,1\}}$、 そして${\displaystyle f(x,y)=yx}$。

特定の問題では、入出力表現と特徴を次のように選択できます。${\displaystyle \mathrm {argmax} _{y}f(x,y)\cdot w}$効率的に見つけることができるが、${\displaystyle y}$非常に大きな集合、あるいは無限の集合から選ばれる。

2002年以来、パーセプトロンのトレーニングは、品詞タグ付けや構文解析などのタスクにおいて、自然言語処理の分野で人気を博している（Collins、2002）。また、分散コンピューティング環境における大規模な機械学習問題にも適用されている。^{[ 48 ]}