パーセプトロンの直交射影学習とその収束性に関す る研究

パーセプトロンの直交射影学習とその収束性に関す る研究

著者 三好 誠司

発行年 1998‑03‑25

URL http://hdl.handle.net/2297/30582

パーセプトロンの直交射影学習と   その収束性に関する研究

三 好 誠 司

平成10年1月

●

博 士 論 文

パーセプトロンの直交射影学習と    その収束性に関する研究

金沢大学大学院自然科学研究科       システム科学専攻

   電子・情報システム講座

学 籍 番 号

氏     名

主任指導教官名

95−2209

三好誠司 中山謙二

目次

略字と記号

第1章 序論

第2章パーセプトロンによるパターン分類  2．1 緒言．．

 2．2 パーセプトロンの構造と動作およびパターン分類能力．．

 2．3 パーセプトロン学習

 2．4 ランダムパターンの線形分離可能性、．．．．

    2．4．1 線形分離可能性の理論．．．

    2．4．2 相互結合型ニューラルネットワークの確率的記憶容量、

 2．5 緒言．．．

第3章パーセプトロンの等比学習とその収束特性  3．1緒言．

 3．2 等比学習アルゴリズム     3．2．1 適応フィルタ

      1

5

9

17 17 19 21 22 22 25 34

35 35 37 37

3．3

3．4

 3．5  3．6  3．7

第4章

 4．1  4．2  4．3  4．4  4．5

3，2．2 LMSアノレゴリズムと正規化LMSアルゴリズム、

3．2．3 アフィン射影アルゴリズム（APA）

3．2．4 等比学習アルゴリズム（GLA）

2パターンに対する1−GLAの理論収東条件．．．．．、．

3．3．1 発振状態が存在する条件．

3．3．2 発振状態の安定性．

3．3，3 導出された条件の十分性．．．．．．．．．．．．．

3．3．4 理論収東条件．．、．

多パターンに対する1−GLAの収束特性．．．．．．．．．

3．4．1 解領域の角度．．．．．．．．．．．．．．．

3．4．2 計算機シミュレーション．．．．．．．．1．．．．

1−GLAの収束定理．．．．、．．．、、．．．．．．．、．．

1−GLAとパーセプトロン学習の収束速度．．．．．．．．

緒言．．．．．．．．．．．、．．．．．．．．．．．．．．．．

パーセプトロンの対称学習とその収束特性 緒言．．．．．．．．．．、．．．．．．．．

対称学習アルゴリズム（SLA）

ん一SLAの収東条件 トSLAの収束速度

計算機シミュレーション、．．．．．．．．．．．．．．．．

38 39 41 44 47 49 51

54 54 54 59 61

66 69

71

71

72 73 75 81

    4．5．1 SLAの次数たと学習収束性、、、．

    4．5．2 SLAの次数たと収束速度  4．6 緒言

第5章 結論

 5．1本研究のまとめ．．

 5．2 今後の課題と展望．．．

謝辞

参考文献

本研究に関連する論文一講演

付録A確率的記憶容量計算への線形計画法の適用

81

84 85

89 89 90

93

95

101

105

略字と記号

本論文で用いた主な略字と記号をまとめる．

略字 APA

BAM

FIRフィルタ

GLA

ん一APA ん一GLA ん一SLA

LMSアルゴリズム NLMSアルゴリズム

PRLAB

a冊ne projection a1gorithm：アフィン射影アルゴリズム bidirectiona1associative memory：双方向連想記憶

丘nite impu1se response丘1ter：有限長インバノレス応答フィ ルタ

geometric1earning a1gorithm：等比学習アルゴリズム ん次のAPA

ん次のGLA

ん次のSLA

1east mean square a1gorithm：最小2乗平均アルゴリズム noma1ized1east mean square a1gorithm：正規化最小2乗 平均アルゴリズム

pseudo−re1axation1eaminga1gorithmforBAM：BAMのた めの擬似緩和学習アルゴリズム

        5

SLA

XOR

記号

。

0κ（γ1）

、Cわ

ε（η）

ん（n）

パ

ん

ん0

η

N

ρ

P

Prob（P，N）

symmetric1eaming a1gorithm二対称学習アルゴリズム 排他的論理和

パーセプトロン学習の学習係数

ス：一GLA，ん一SLAの時刻ηにおける更新の対象となる（N＿ん）次元 空間

α個から6個を選ぶ組み合わせの数 時刻ηにおける適応フィルタの出力誤差 時刻ηにおける適応フィルタ係数ベクトル 適応の目標

APA，GLA，SLAの次数

GLAにおいて，パーセプトロンの出力が望みの出力と異なるパター ンの数

時刻ステップ

パターンの次元，パーセプトロンの入力数 原点

ω（乞）の への射影ベクトル パターンの数

P個のN次元パターンが線形分離可能である確率

3＊

3（η）

Sgn（・）

T

u

・ゴ（η）

u

u（n）

σ

ω

叫

ω＊

ωoc

ω（η）

ω（η）⊥

ω（n）

叫

ω美

SLAで与えられたすべてのパターンを正しく分類する結合荷重ベク トルのひとつであるω＊に垂直な超平面

結合荷重ベクトルω（η）に垂直な超平面 符号関数（sgn（α）＝α／1α1）

単位時間の遅延

パーセプトロンの積和入力

時亥I」ηにおける第ゴユニットの積加入力 適応フィルタのタップ入力ベクトル

時刻ηにおける適応フィルタタップ入力ベクトル 解領域の境界

パーセプトロンの結合荷重ベクトル＝（ωo，ω1，…，岬一1）T パーセプトロンの第乞結合荷重値

与えられたすべてのパターンを正しく分類する結合荷重ベクトルの ひとつ

ωの極限

時刻nにおける結合荷重ベクトル ω（n）の空間z方向成分

ω（η）の空間zの直交補空間方向成分

ん一SLAにおいてん個のパターンベクトルが張る空間の直交補空間へ の結合荷重ベクトル初期値ω（0）の射影

ん一SLAにおいてん個のパターンベクトルが張る空間への結合荷重ベ クトル初期値ω（0）の射影

△ω（η）

ωゴ1

㏄

lr｛

♂

li ll

X＋

μ

ガ

ひ｛（几）

6

θ

λ

μ

μ

μλPλ

ψmi。

時刻ηにおける結合荷重更新ベクトル（：ω（η十1）＿ω（η））

第乞ユニットから第ゴユニットヘの結合荷重

パーセプトロンの入力ベクトルニ（エO，エ1，＿，抑、1）T

パーセプトロンの第乞入力の値 の転置

ベクトル のノルム

XのMoorerPenrose一般逆行列

パーセプトロンの出カ

バーセプトロンが出力すべき望みの出力 時刻ηにおける第ゴユニットの出力 任意の正数

パターン数が2のパターン分類問題の解領域の角度 GLAの学習係数

LMSアルゴリズムにおけるステップサイズパラメータ NLMSアルゴリズムにおける適応係数

APAにおける適応係数

パターン分類問題の解領域の角度

第1章 序論

現代はまさにディジタルコンピュータの全盛時代である．その技術は，パーソナル コンピュータ，エンジニアリングワークステーション，スーパーコンピュータ，と いった形態で人間の種々の生産活動を支援している．あるいは，そのような形態の みにとどまらず，普段は目に見えない部分で人間の生活を支える，いわば社会基盤 となっている．このようなディジタルコンピュータの技術は，A．M．Turingによって 導入された，いわゆる チューリングマシン の理論［1］に基づいている．すなわち，

ディジタルコンピュータはあらかじめプログラムに記述された規則に従って，逐次 直列的に処理を進めることにより，与えられた仕事を行う．

 人間が行っている思考は大きく論理的思考と直感的思考に分けることができる．

論理的思考は，人間が意識して行う理路整然とした思考のことであり，記号化され た情報を対象に，命題と推論規則を用いて一ステップずつ逐次直列的に実行される．

これに対して，直感的思考とは，道筋立てて考えたわけでもないのに突然に解答が ひらめくような思考のことであり，そこでは情報は記号化される以前のものとして 表現されており，直接に意識に上ることはない．将棋というゲームを例にとると，三 手先まで読むことによって次の一手を決定する，というような場合が論理的思考で あり，突如として次の一手がひらめく，というような場合が直感的思考である．実

9

際には，三手先まで読む場合でもすべての可能な手を読んでいるわけではなく，直 感的思考で候補に残ったいくつかの手から最善手を選ぶということが多いであろう．

また，突如ひらめいた一手についても，その後で論理的思考により吟味してから実 際に指すという場合が多いであろう．このように，人間の思考においては，論理的 思考と直感的思考がうまく組み合わさり，補いあって柔軟性と厳密性が実現されて いるものと考えられる．

 大量の情報を高速に処理する能力により，いまや必要不可欠な社会基盤となった ディジタルコンピュータであるが，我々のまわりを見渡してみると，本来，もっと早 い時期に人間からコンピュータに置き換わってゆくべき，危険で，単調で，不快な 作業の多くを任せることができないでいる．これは，現代のディジタルコンピュー タの情報処理形態が，人間の論理的思考のみに対応する形態であり，人間のもうひ

とつの思考，直感的思考に相当する能力を有していないからであると言える．

 ニュ』ラルネットワークは，生物の神経細胞を模擬したユニットを多数結合した，

分散並列的な情報処理を行うネットワークに関する研究分野であり，究極には，人 間の脳のはたらきを解明し，工学的に応用することを目標としている．ニュ』ラル ネットワークはその内部にフィードバックを有するか否かによって大きく相互結合 型と階層型に分類される．これまでになされた多くの研究で，連想記憶，関数近似，

組み合わせ最適化問題，パターン分類等へのニューラルネットワークの適用に関し て多くの成果が得られている［2，3，41．

 パターン分類は，与えられたパターンをそれが属すべきクラスに分類する問題で ある［21・生物にはたいへん優れたパターン分類能力が備わっている．たとえば，生

後6ヶ月の乳児でさえも，まわりの多くの大人たちの顔の分類，違う言葉で表現する ならば認識，をたやすく行っている．この場合，認識すべき顔は，そのときによって 表情が異なるし，また角度や距離によって網膜上に結ばれる像は多様性に富むもの である．それにもかかわらず，乳児は高い確率で正しい認識を行っているのである．

現代のディジタルコンピュータの回路素子の動作は，生物の神経細胞の動作とは比 較にならないほど高速であるにもかかわらず，この作業を逐次直列処理型のディジ タルコンピュ］タで行うことはたいへん困難である．

 ニューラルネットワークによるパターン分類は，逐次直列処理型のディジタルコ ンピュータとはまったく異なる方法で実現される．すなわち，あらかじめプログラ ムとして手続きを記述するという手法によるのではなくではなく，例題から与えら れる情報を用いてネットワークの構造やパラメータをある尺度にしたがって修正し てゆき，最終的に正しいパターン分類を行うネットワークを作り上げる，という手 法，すなわち 学習 によりパターン分類を実現する．ニューラルネットワークの 学習は，大きく，教師あり学習と教師なし学習に大別される．またそれぞれの中に おいてもこれまでに多くの学習アルゴリズムが提案されている［2］．通常，ニューラ ルネットワークの学習においては，学習に用いた例題だけを正しく分類できれぱよ いというわけではなく，学習に用いていない未知のパタ』ンをも正しく分類できる 能力，すなわち 汎化能力 が要求される．ネットワークの規模を大きくすれば学 習は容易になるが，ネットワークの表現能力が豊かになりすぎて，パターンが従う 隠れた拘東条件を抽出することなく学習用のパターンを再現できてしまうことにな る．そして，学習用のパターンとほんのわずかに異なる未知パターンに対しても正

しい分類ができなくなる二とがある．この現象は， 通学習 と呼ばれ1ニューラル ネットワークの学習における大きな問題としてその対策がさかんに研究されている

［2，5，61．また，先験的な知識を持たずに例題だけで学習することの難しさもよく言 われていることである［71．

 このような未解決の問題も残されているものの，3つの層を有する階層型ニュー ラルネットワークを誤差逆伝搬アルゴリズムにより学習することにより，線形分離 可能でないものも含めてあらゆるパターン分類が可能である［8］．誤差逆伝搬アルゴ

リズムはAmariによって発見され［91，Rume1hartらによって再発見された［10］学 習アルゴリズムであり，階層型ニューラルネットワークの出力誤差を信号の流れと は逆方向に伝搬していくことにより，出力層に直接つながっていない結合荷重も学 習できるアルゴリズムである．

 神経細胞のモデル化はMcCu11ochとPittsによってなされた［11］．パーセプトロ ンはMcCu11ochとPittsのモデルを基本にRosenb1attによって提案された線形識 別回路である［12，13］．単一のパーセプトロンは3つ以上の層を有する階層型ニュー ラルネットワ』クと異なり，線形分離可能なパターン分類問題しか扱うことができ ない．しかし，パーセプトロンはニューラルネットワークの基本要素としてたいへ ん重要なモデルである．パーセプトロンの学習アルゴリズムとしては，Rosenb1att により提案された，いわゆる パーセプトロン学習 がよく知られている［12，13／。

Rosenb1attは，パーセプトロン学習では与えられたパターン分類問題が線形分離可 能であれば必ず有限回の更新で学習が終了すること，すなわち，与えられたパター

ンすべてに対して正しいクラスを出力する解が見つかることを証明した［131．この

12

ことがパーセプトロンの意義を大きなものにしている．

 一方，信号処理の分野において，自らの特性を外界の状況に合わせて変化させて ゆくフィルタを適応フィルタとよんでいる．適応フィノレタの応用としては，ノイズ キャンセラやエコーキャンセラなどがある［14］．通常，適応フィルタはタップ付き 遅延線フィルタと呼ばれるFIRフィルタで実現される．適応フィルタのインパルス 応答を変化させてゆくアノレゴリズムが適応アルゴリズムであるが，代表的な適応ア ルゴリズムに最小2乗平均（1east mean square：LMS）アルゴリズムがある．これ はB，Widrow，M−E．Ho冊ラJr．によって提案されたアルゴリズム［15］で，2乗平均誤 差を最急降下法に基づいて最小化するようにフィルタのインパルス応答を更新して ゆくアルゴリズムである．LMSアルゴリズムを改良したアノレゴリズムとして正夫見化

LMS（norma1izedLMS：NLMS）アルゴリズムがある．これはNagumo，Nodaと A1bert1Gardnerによって独立に提案されたアルゴリズム［16，171であり，LMSア ルゴリズムよりも高速であり［18］，収束速度が入力信号によらないという利点を有 する．このNLMSアルゴリズムをブロック信号処理に拡張したアルゴリズムとして アフィン射影アルゴリズム（a冊ne projection a1gorithm：APA）がある［191．

 適応フィルタとパーセプトロンを比較すると，両者ともに入力とパラメータの積 和を計算するという点，望ましい特性が得られるようにパラメータを変化させてゆ

くという点で類似している．しかし， フィルタ と パターン分類 という目的の 違いから，適応フィルタでは積和をそのまま出力とするのに対し，パーセプトロン では非線形な処理を施してから出力とする．

13

 本研究では，ニューラルネットワークの基本要素としてきわめて重要である，パー セプトロンを対象とし，その学習アルゴリズムとして，適応フイノレタのアルゴリズ ムであるAPAを適用した直交射影学習アルゴリズムを提案する．さらにこの学習ア ルゴリズムに関する種々の理論的，数値的解析により，その興味深い収束特性を解

明する［20，21，22，23，24，25，26，271．

 第2章において，パーセプトロンを中心にニューラルネットワークの歴史をふりか えるとともに，パ』セプトロンの構造と動作，およびそのパタ』ン分類能力につい て述べる．また，パーセプトロンの学習アルゴリズムとしてよく知られているパー セプトロン学習について述べ，さらに，線形分離可能なパターンの数に関する理論

と相互結合型ニュ］ラルネットワークの確率的記憶容量について述べる．

 第3章において，ハーセプトロンヘのAPAの適用として，等比学習アルゴリズム

（geometric1eaming a1gorithm：GLA）を提案する［20，21，22，24，25，26］．また，学 習中に発振状態が生じうる条件についての解析を行うことにより，2個のパタ』ン に対して五次GLAが収束するために，2パターンの角度θと学習係数λが満たす べき関係を理論的に導出する．また，パターンが3個以上の場合に・解領域の角度 ψmi。 を導入し，1次GLAが収束するためのψmi、＿λの関係が，2パターンの場合 のθ一λの関係で近似できることを計算機シミュレーションで示す．さらに，θ一λ の関係においてθによらずに収束する条件である人＝2に対して，1次GLAがパ タ』ン数に関わらずに収束することを証明する．これらにより，1次GLAの収束性 が保証され1学習アルゴリズムとしての有効性が確認される．また，1次GLAが収 束するためのψmi、と人が分布する範囲が近似的に明らかになる．

 第4章においては，GLAにおいて学習定数を2とした場合を特に区別して，対称 学習アノレゴリズム（symmetric1eaming a1gorithm：SLA）と呼ぶことにする［23，271一

次にSLAの次数ん，パターン数P，パターン次元Nと収束性の関係についての 理論検討を行い，P＞2Nの場合に結合荷重初期値によらずに学習が収束するため には，ん＜Nでなければならないことを明らかにする．さらに，ん次SLAの収束 速度とパターン次元に関する理論的な解析を行い，SLAの収束速度は，次数んがパ

ターン次元Nの1／2のときに最大になるという興味深い結論を得る．ん次SLAの 収束条件，収束速度に関するこれらの理論解析の結果は計算機シミュレ」ションに

より検証される．

 最後に第5章において本研究のまとめと今後の課題および展望について述べる．

第2章 パーセプトロンによるパターン 分類

2．1 緒言

 ニューラルネットワークは，人間の脳が行っている思考や記憶のしくみを解明し，

工学的に応用することを究極の目的とする研究分野である．人間の脳はおよそ140 億個もの神経細胞の集合体である．その神経細胞のひとつひとつは ニューロン と

も呼ばれる．ニューラルネットワークの研究においては，このニューロンの動作を 単純化したモデルとして ユニット を考え，ユニット単体，あるいは多数のユニッ

トの結合体について，その性質やふるまいを調べる．

 ニューロンのモデル化は1943年にMcCu11ochとPittsによってはじめてなされ た．ニューロンは興奮すると出力側の軸索に電気パルス列を送り出すが，興奮して いないときはほとんど出さない．McCu11ochとPittsは，この電気パルスは1と 0に量子化された信号を別のニューロンに送るものと考え，興奮状態およびそのと

き送り出される信号を1，非興奮状態およびそのとき送り出される信号を0とした．

ニューロンには樹状突起があって，多数のニューロンからの軸索が結合しており，こ こから信号を受け取る．この結合部をシナプス（synapse）結合とよぶ．数学的に表

17

現するなら，McCu11ochとPittsはニューロンを 線形しきい値関数 としてモデル 化したと言える．

 1949年にHebbは，ニューロンが興奮すると，入力部のシナプス結合のうち，刺 激を伝えたものは結合強度が増加し，さらに刺激を伝えやすくなるという説を唱え，

これが神経回路に・可塑性 をもたらし，認識や記憶のもとになっていると主張した

［281一

 パーセプトロンは，McCu11och，PittsのモデルとHebbの学習則を基本に，Rosen−

b1attによって提案された線形識別回路で，学習能力のあるユニットを構成要素とす る多層の層状回路である［12，131．パーセプトロンにおいてパターン分類の機能を担 う出力細胞に着目すると，これは線形しきい値素子として動作するので，分類しよ うとするパターン集合が線形分離可能でなければ，シナプス結合やしきい値をいか に調整しても正しい分類はできない．

 1960年代末に，MinskyやPapertは自己批判をも含めた，パーセプトロンの能力 に対する批判，すなわち，パーセプトロンのパターン分類能力は線形分離可能なパ ターン集合に限られ，たとえば，ごく簡単なXOR間題も解けないとして，ニュー ラルネットワークの研究を批判した［291．これを機に，ニューラルネットワークの 研究は下火になった．

 しかし，多層のネットワークの学習アルゴリズムとして，AmariやRume1hartら によって誤差逆伝搬学習アルゴリズムが発見され［9，101，線形分離可能でないパター ン分類問題にニューラルネットワークを適用することが可能になった．誤差逆伝搬 学習アルゴリズムは，フィードバックのない層状回路で，与えられた入出力関係を

滴たすようにニューラルネットワークを組織化させる手法であり，入力層と出力層 の間にニューロンの層はいくつあってもよい．出力ニューロンの出力と教師入力が 与える正解が食い違ったとき，いわゆる最急降下法に基づき，各層間の結合荷重を 修正する．このような更新を繰り返すことによって，最終的に与えられた入出力関 係を満たすニューラルネットワークが構成される．各更新の過程で，誤差を信号の 流れと逆方向に伝搬させることから誤差逆伝搬学習アルゴリズムとよばれている．

 パ』セプトロンは，それ自身で単体では線形分離不可能なパターン集合に対応で きないが，階層型ニューラルネットワーク，あるいは相互結合型ニューラルネット ワークの基本要素としてきわめて重要なモデノレである．本章では，まず，パーセプ トロンの構造と動作，およびパターン分類能力について述べる．また，パ』セプト ロンによるパターン分類のための学習アルゴリズムとしてよく知られている，パ』

セプトロン学習について述べる．さらに，ランダムパターンの線形分離性に関する 理論について述べる．パ』セプトロンが分類できるのは線形分離可能なパターン集 合だけてあるので，この理論はパーセプトロンの限界を規定するきわめて重要な理

論である．

2．2 パーセプトロンの構造と動作およびパターン分類能

力

本研究で対象とするパーセプトロンの構造を図2．1に，入出力関係を式（2．1），

（2．2）に示す．

Fixed

1・p・tπ・；一1

Inputs

 ■

 2

旧

●

●

●

ω

ω

 2

ω

ωル1

図2．1：パーセプトロン

Output

  v

       N−1

       ・＝Σ榊       （2・1）

      ｛＝0        ＋1，u≧0

      ツニ      （2・2）

       一1 uく0        ラ

 式（2．1）のuに0を代入すると，傾きが叫（乞＝0，1，…，N−1）で決定され原 点を通る超平面を表す式になる．よって，パーセプトロンはパターン空間において 超平面を境界とする2つのクラスを分類する能力を有すると言える．なお図2．1は，

値として常に一1をとり，対応する結合荷重がωoであるような固定入力ェ。を追加 することにより，しきい値をOとしたパーセプトロンである．このパーセプトロン

を，固定入力 oを持たずにしきい値が0に限定されない場合と比較すると，入力 の数が1だけ増えるかわりに境界超平面が常に原点を通ることになり都合がよい．

      20

よって本論文においては特にことわらない限り図2．1のパーセプトロンを扱うこと にする．また，この固定入力を含む入力の総数Nをパターンの次元とよぶことに

する．

2．3 パーセプトロン学習

 パーセプトロンによるパターン分類のための学習アルゴリズムとしては，以下に 示すパーセプトロン学習がよく知られている［12，131．

［step1］ω（0）を乱数で初期設定する．

［step2］パターンをひとつ選ぶ．このとき選ばれたパタ』ンを とする．

［step2］πに対するパーセプトロンの出カッが望みの出力ガと異なるなら結合荷 重を次式で更新する．ただし，ここでCは正の定数である．

ω（η斗1）＝ω（n）十。ガω       （2．3）

［step3］パーセプトロンの出力と望みの出力が異なるパターンが残っていないなら 終了．残っているならstep2に戻る．

 式（2．3）からわかるように，パーセプトロン学習の更新において必要な情報は，

選ばれたパターンベクトルと，それに対する望みの出力，および，実際の出力だけ である．このようにパーセプトロン学習はたいへん単純でローカルな学習アルゴリ ズムであるが，与えられた問題が線形分離可能であるならば，有限回の更新で結合       21

荷重が必ず解領域に到達することが証明されている［21・この性質はパーセプトロン の学習収束定理と呼ばれ，パーセプトロン学習の最大の長所である．

2．4 ランダムパターンの線形分離可能性

2．4．1 線形分離可能性の理論

 前節で述べたように，単一のパーセプトロンは，パターン空間において1個の超 平面を境界とする2つのクラスを分類する能力を有する．このことを逆に言うと，

パーセプトロンが正しく分類できるのは線形分離可能なパターン分類問題に限定さ

れる．

パーセプトロンの入力は実数であり，必ずしも2値に量子化されているわけではな い．すなわち，パターンは必ずしもN次元超立方体の頂点に位置するわけではな いが，理解を容易にするために図2．2〜図2．4においてはパターンが3次元立方体の 頂点に位置する場合を示している．これらの図において， O と ● を分類する ことを考える．図2．2の場合にパターンを正しく分類する平面は無数に存在し，斜 線で示す平面はその一例である．図213の場合も，例えば斜線で示す平面により分 類が可能である．ところが，図2．4の場合には， ○ と ● を分類するような平面 は存在しない．このように，必ずしも，パターンが多いから分類不可能であり，少 ないから分類可能である，というわけではない．しかし，パターン数が多くなるほ

どパターンを正しく分類できる確率が小さくなる二とは明らかである．

図2．3：パターン分類問題の例（P：6，N：3）

図2．2：パターン分類問題の例（P＝2，N＝3）

図2．2〜図2．4は，3次元のパターン分類問題の例を示している．本論文で扱う 線形分離可能なパターンの数に関する多くの研究，すなわち，2つのクラスのい

O… 一・・

図2，4：パターン分類問題の例（P＝5，N＝3）

ずれかにランダムに属する多数のランダムパターンを，1個の超平面が2つのクラス に正しく分割する場合の，パターン次元とパターン数に関する多くの研究が，1960 年代になされたエ30，31，32，33，341．

 Kofordは，線形分離可能なN次元パターンの個数期待値に関する最大値が2N であることを数値実験の結果から予想した［30］．Kofordの予想は2値パターン，す なわち，各パターンがw次元超立方体の頂点に存在する場合に関するものである．

Brownは，N次元超球面上のランダムパターンに関する数値実験からKofordと同様 の予想を行った一31］．そしてこれらの予想の理論的な解決はWinder［331とCover［341 により独立になされた．

 Wende1は，それぞれが2つのクラスのいずれかにランダムに属するような，P 個のN次元パターンが線形分離可能である確率Prob（P，N）を導出した［321．すな

24

わち，

       …岬）一（1ゾ1乞（㌃1）  （・刈

      た＝O

 WinderはNが大きい場合について非常に単純な関係を得た．すなわち，任意の  6＞0に対して，

         1im Prob（2N（1＋6），N）二 〇       （2・5）

         N→oo

       l

      Prob（2N，N） ＝  ＿      （2．6）

       2

         ！imP・・b（2N（1一・），N）一1      （2・7）

         ハ→oo

 すなわち，次元Nが大きいとき，パターン数Pが2Nより小さければ，そのパ ターン集合はほぼ確率1で線形分離可能である．この関係をCoverは， N入力の 線形しきい値素子の情報容量は2Nである と表現している．

 以上の結果は，対象とする分類問題を構成するパターンの個数が比較的少なく，か つ，それらがランダムとみなせる場合には，ほぼ確率1で線形分離可能であること

を表しており，パターン分類問題へのパーセプトロン適用の理論的な基礎を与える

ものである．

2．4．2 相互結合型ニューラルネットワークの確率的記憶容量

パーセプトロンと相互結合型ニューラルネットワーク

 序論においても述べたように，ニューラルネットワークはその内部にフィードバッ クを有するか否かによって大きく相互結合型と階層型に分類される・図2・1に示し

25

たN入力のパーセプトロンをユV個用いて構成された全結合のネットワークは典 型的な相互結合型ニューラノレネットワークである．図2．5はこのような相互結合型 ニューラルネットワークを示す．

●o

 ω  む ﾖ 加

 ●

R

図2．5：相互結合型ニューラルネットワーク

 図2・5において，ω力は乞番目のユニットからゴ番目のユニットヘの結合荷重を 示す．図2．1のパーセプトロンが単一出力であったことに対応して，図2．5におい て同一ユニットからの（N−1）本の出力はすべて同じ値である．また，本節にお いては1個々のユニットは図2．1のパーセプトロンとは異なり，固定入力 oを有し ないものとする．

相互結合型ニューラルネットワークによる連想記憶

 相互結合型ニューラノレネットワークはフィードバックを有するので，階層型ニュー ラルネットワークと異なり一般的にはダイナミクスを持つ．これを利用して，その 安定平衡点やリミットサイクルなどのアトラクタにパターンを記憶させることがで きる［351．このようにいくつかのパターンが記憶された相互結合型ニューラルネッ トワークに，たとえば記憶させたパターンの一部が欠けたパターンや，似たパター ンを入力として与えると，もとのパターンの想起が可能となる．現代のディジタル コンピュータが行っているようなアドレスによる想起とは異なり，記憶の内容から 想起を行うこのような記憶は 連想記憶 と呼ばれる．相互結合型ニューラルネット

ワークによる連想記憶の記憶容量，すなわち，Nユニットのネットワークにいくつ のパターンを記憶させることができるか，に関してはこれまでに多くの研究がなさ れてきた［36，37，38］．たとえば，代表的な相互結合型ニューラルネットワークとし て知られるホップフィールドネットワークにおいては，結合荷重は記憶したいパター

ンの相関行列として決定されるが，その記憶容量はユニット数の0．15倍程度である ことが計算機シミュレーションにより明らかになっている［371．またこの値に関す るさまざまな理論的解析もなされている［21．

 相互結合型ニューラルネットワークは，多数のパーセプトロンを組み合わせたも のであるから，その記憶容量の上限と前節で述べた線形分離可能性の理論には密接 な関係がある．ここでは，相互結合型ニューラルネットワークの記憶容量の上限に 関する数値解析について述べるとともに，その結果と前節の線形分離可能性の理論 の関係について考察する．

 まず，本節で考える相互結合型ニューラルネットワークについて述べる・ul（η）1 ひ、（η）はそれぞれ時刻ηにおける第乞ユニットの積和入力と出力を表すものとする・

また，すでに述べたように，〜は第1ユニットから第プユニットヘの結合荷重を表 す．このとき，ネットワークの動作を表す方程式は以下のようである．

      N

      ・ゴ（η）＝ΣW1（η）      （2・8）

      ｛＝1

      ＋1，・ゴ（η）≧0

       リゴ（叶1）＝       （2・9）

      一1，uゴ（η）＜O

ここで，Mはユニット数である．よって，この相互結合型ニューラルネットワーク に記憶されるパターンは，要素が十1あるいは＿1のM次元ベクトルである．記憶 パターンはすべての可能な，すなわち2N個のパターンからランダムに選ばれる．ま た，自己結合はないものとする．すなわち，次式が成立しているものとする．

       ωボ0         （2，10）

 もしこの条件が科されなければ，たとえば，すべての自己結合を正の値とし，そ れ以外の結合をゼロとすることにより，2N価すべてのパターンを記憶することが可 能になるが，これはもはや連想記憶ではない．それゆえ，本節において式（2．10）は

自然な仮定である．

確率的記憶容量の定義

 式（2．8）〜（2．10）のネットワーク方程式を満足する相互結合型ニューラノレネッ トワークの記憶容量の上限は学習アルゴリズムに依存しない普遍的な上限であるか       28

ら，この値を明らかにすることはきわめて重要である．

 ランダムに選ばれたあるパターン集合が相互結合型ニューラノレネットワークの平 衡状態に記憶され得るかどうかは相互結合型ニューラルネットワークのユニット数，

パターン数だけによって決定されるのではなく，パターン集合を構成するパターン の組み合わせに依存する．たとえば以下のパターン集合のように，1つの要素だけ が異なる2つのパターン 1，π2からなるパターン集合は，ユニット数Mに対して パターン数が2と十分小さいにも関わらず，ひとつの相互結合型ニューラノレネット

ワークで記憶することはできない．

1二（斗1，十1，十1，一・，十1，十1，±ユ）       （2，11）

        2＝（十1，十1，十1，…，十1，斗1，ゴ）    （2．12）

 いずれのパターンにおいても第Mユニットの積和入力は式（2．13）で与えられる．

1においては第Mユニットの出力が十1であるからこの値は正でなければならず，

2においては第Mユニットの出力が一1であるからこの値は負でなければならな いが，この2つの要求は矛盾する．それゆえ，このパターン集合をひとつの相互結 合型ニューラルネットワークで記憶することは不可能である．

       N         N−1

       Σωw1＝Σω舳1＋州N州

       ｛＝1        ｛＝l

      N−1       ：Σω舳       ご1

      ＝Σω州       （2・13）

      ｛＝1

 このように，たとえパターン集合を構成するパターン数が少なくてもこれらを記       29

憶する結合荷重が常に存在するわけではない．結合荷重が存在するか否かはパター ンの組み合わせによって決定される．

 そこで，ある数のユニットから構成される相互結合型ニューラルネットワークの 記憶容量を，そのユニット数の何倍というふうに表現するのではなく，逆に，ある 数のランダムパターンからなるパターン集合を言己憶できる 確率 で表現することを 考える．

 すべての可能な2wパターンからMパターンを選ぶ選び方は2．CM通り存在

する．すなわち，M個のN次元パターンからなるパターン集合は2NCM個存在 する．この2NCM個のパターン集合のうち何％のパターン集合が記憶可能であるか

は，Mを変化させることによって変わるが，M を変化させた場合の確率の集合を，

この相互結合型ニューラルネットワークの 確率的記憶容量（Probabi1istic Memory Capacity） と定義することにする［39］．確率的記憶容量は相互結合型ニューラル ネットワークのユニット数により一意に決まるもので，学習アルゴリズムやネット

ワークのダイナミクスには無関係である．確率的記憶容量はランダムパターンを記 憶する際のあらゆる学習アルゴリズムの記憶可能性，学習以東性の上限を確率で与

えるものである．

パターン集合の記憶可能性

 2N個のパターンから選ばれた記憶すべきM 個のパターンは次のように表現される．

πm：（・m1｛・ジ・・，・m・）     （2．14）

       工mゴ＝十1or一ユ       1＜m＜M

      1≦ゴ≦、V

確率的記憶容量を得るための基本作業として，〃個のw次元パターンから構成さ れるあるパターン集合が相互結合型ニューラノレネットワークの平衡状態に記憶可能 かどうかを判定する必要がある．別の表現をすれば，この判定は，〃個のM次元パ ターンに対して，式（2．15）〜（2，17）を満たすω＝｛ωゴ｛｝が存在するかどうかの 判定と言うこともできる．このようにパターン集合の記憶可能性の判定は，結合荷 重の存在可能性の判定と等価である．

       N

       Σω〆。1≧0wh…剛＝十1    （2．15）

       ゴ＝1        N

       ΣW．1・0wh・・〜二一1    （2．16）

       乞＝！

      1≦m≦M        （2．17）

計算結果と考察

 2NパターンからMパターンを選ぶ2．CM通りすべての場合について調べるこ とはMが大きくなると計算量の点で難しい．そこで，2Nパターンからランダムに M個のパターン集合を選び，そのパターン集合に関して式（2，15）〜（2．17）を満 たすω二｛ωゴ｛｝が存在するかどうかを調べ，この試行を多数回繰り返すことにより 記憶可能確率を調べた．ωが存在するかどうかの毎回の判定は，付録Aに示す方法

で線形言十画法を適用することにより行った．

 図2．6は，パターン数／ユニット数（以下，この値を 相対パターン数 と呼ぶ）

とユニット数Nに対するパターン集合の記憶可能確率を示している・また1図2・7 は図2．6の等高線表示である．図2．7においては，記憶可能確率10％，20％、30％，

 ・，90％の9本の等高線が示されている．

幸（ 耕）1OO

起50

塑  O

帽    O．5

㌦タ、 1・

     令   2

16

   12

    幸

  8 ＼

   二、

   〃

4 グ

図2．6：確率的記憶容量の計算結果

 計算時間の制限から，試行数は各ポイントにおいて100回程度と十分でない．そ のため，面図ともなめらかでない部分が見られる．また，計算したユニット数も3

〜16と少ない．しかし，これらの図から相互結合型ニューラルネットワークの確 率的記憶容量に以下の傾向があることがわかる．

・ユニット数が増大するにつれ，パターン集合の記憶可能確率が遷移する相対パ ターン数が増大する．すなわち，パターン集合の記憶可能確率が50％となる相

32

16

≧

無12

工 へ 8

い

、

  4

90％

1O％

OO．511．52

      相対パターン数

図2．7：確率的記憶容量の計算結果（等高線表示）

対パターン数は，ユニット数が3〜8の場合には約O．6であるが，ユニット数 が16の場合には約1，3と増大している．

．ユニット数が増大するにつれ，パターン集合の記憶確率の遷移幅が減少する．す なわち，ユニット数が3〜8の場合には相対パターン数O．5で記憶可能確率 70％，O．8で30％と，記憶可能確率が70％から30％に遷移する幅が約0．3で  あるが，ユニット数が16の場合には相対パターン数1．25で記憶可能確率70％

，1．45で30％と，記憶可能確率が70％から30％に遷移する幅が約0．2と減

 少している．

 この相互結合型ニューラルネットワークを構成するユニットのそれぞれは，一v入 力のパーセプトロンである．また，前節で述べたように，パーセプトロンの情報容 量は入力数の2倍である．このことから，相互結合型ニューラルネットワークにお いてユニット数Nをさらに大きくしていった場合には，記憶可能確率が遷移する相

33

対パターン数は2に，遷移幅は0に漸近すると考えられる．すなわち，図2．6，2．7 は，ユニット数が少ない場合の相互結合型ニューラルネットワークの記憶容量上限 に加えて，ユニット数を大きくする場合の漸近傾向をも示しており，これはパーセ プトロンの情報容量の理論とも合致する結果である．

2．5 緒言

 本章では，パーセプトロンを中心にニューラルネットワークの歴史をふりかえると ともに，次章以降で扱うパーセプトロンの構造と動作，およびそのパターン分類能 力について述べた．また，パーセプトロンの学習アルゴリズムとしてよく知られて いるパーセプトロン学習について述べた．さらに，線形分離可能なパターンの数に 関する理論と相互結合型ニューラルネットワ』クの確率的記憶容量について述べた．

第3章 パーセプトロンの等比学習とそ の収束特性

3．1 緒言

 パーセプトロンによるパターン分類のための学習アルゴリズムとしては，パーセ プトロン学習がよく知られている．パーセプトロン学習の最大の長所は，与えられ た問題が線形分離可能であるならば，有限回の更新で結合荷重が必ず解領域に到達 することである．この性質はパーセプトロンの学習収束定理としてよく知られてい る［21．しかしながらパーセプトロン学習にはいくつかの短所もある．すなわち，学 習速度が遅いことや，見つかった解が雑音を含むパターンの分類に対して必ずしも 良好な特性を示すとは限らないことなどである．双方向連想記憶のために提案され たPRLAB［41］は1個のユニットの一方向の学習に着目すればパーセプトロンの学習 アルゴリズムと等価であり，これはパーセプトロン学習の学習速度を改善したもの であるということができる．

 一方，適応フィルタの分野においては，正規化最小2乗平均（NLMS）アルゴリ ズムをブロック信号処理に拡張したアルゴリズムとしてアフィン射影アルゴリズム

（a冊ne projection a1gorithm：APA）［19］がよく知られている．服部らは2次のAPA

を双方向連想記憶の学習に適用し，パーセプトロン学習よりも高速であることを計 算機シミュレーションにより確認した［421一しかしながら，文献［421は双方向連想 記憶というやや特殊なモデルに限定された内容であり，また，学習収束条件につい ては詳細な検討がなされていない．

 本章では，まず，適応フイノレタ，LMSアルゴリズム，NLMSアルゴリズム，APA について述べた後，パーセプトロンにAPAを適用した直交射影学習アノレゴリズム として，等比学習アルゴリズム（geometric1eaming a1gorithm：GLA）を提案する

［20，21，24］．すなわち，GLAでは，結合荷重ベクトルの毎回の更新を，ん個のパ ターンベクトルの直交補空間に向かって垂直に行う．また，このときのんをGLA の 次数 とよぶ．次に，学習の発振状態が生じうる条件についての解析を行うこと により，1−GLAで2個のパタ』ンを分類する場合に有限回の更新で結合荷重ベクト ノレが解領域に到達するために，2パターンの角度θと学習係数λが満たすべき関係 を理論的に導出する．また，パターンが3個以上の場合に 解領域の角度ψmj刀 を 導入し，1−GLAが収束するためのψmj。＿λの関係およびθ＿λとの関係を計算機 シミュレーションで調べる．さらに，θ＿λの関係においてθによらずに収束する 条件であるλ：2に対して，1−GLAがパターン数に関わらずに常に収束すること を証明する［24，25，26］．これらをふまえてGLAの有効性と解領域の角度ψmi、の意 義について述べる．また，1＿GLAとパーセプトロン学習の収束速度比較に関する数 値解析の結果についても述べる．

 なお，本章においては，結合荷重ベクトルが解領域に到達して更新が終了するこ とを，学習が収束する，と表現するものとする．さらに，結合荷重ベクトル初期値

36

によらずに学習が有限回の更新で収束することを，学習が大域収束する，と表現す

ることにする．

3．2 等比学習アルゴリズム

3．2．1 適応フィルタ

 信号処理の分野において，自らの特性を外界の状況に合わせて変化させてゆくフィ ルタは適応フィルタとよばれ ﾄいる．図3，1はもっとも基本的な適応フィノレタの適 用例を示している．この図において，適応フィルタは加算器出力を利用するあるア ルゴリズムにより自分自身のインパルス応答を変化させてゆく．

input

adaptive i1ter

unl㎞0Wn SyStem

十

図3．1：適応フィルタ．

 適応フィルタの応用としては，ノイズキャンセラやエコーキャンセラなどがある

［141．多くの場合，適応フィルタはタップ付き遅延線フィルタと呼ばれるFIRフィル タで実現される．図3．2はタップ付き遅延線フィルタを示している．図3．2におい て，Tは単位時間の遅延を表す．このようにタップ付き遅延線フィルタにおいては，

      37

入力信号を遅延させたものと，フィルタ係数の積和が出力される．

      InPut TTTTT

       ho h】 h2 h3 h4 h5

図3．2：タップ付き遅延線フィルタ．

0uΦut

3．2．2LMSアルゴリズムと正規化LMSアルゴリズム

 Widrowによって提案された最小2乗平均（1east mean square：LMS）アルゴリ ズムは，タップ付き遅延線フィルタのもっとも単純な適応アルゴリズムとしてよく 知られている［151・LMSアルゴリズムにおいては，フィルタ係数ベクトルん（η）は 以下のように更新される．

      ん（η十1）：ん（η）十με（η）ψ）     （3．1）

ここで，ηは時刻ステップ，ε（η）は時刻ηにおける出力誤差，u（η）は時刻ηにおけ るタップ入力ベクトル，μはステップサイズパラメータである．

 タップ付き遅延線フィルタの2乗平均誤差はフィルタ係数の2次関数であるので，

その誤差特性曲面は単一の最小点をもつ［141．LMSアルゴリズムは，この誤差特性

曲面における最急降下法となっている．さらにLMSアルゴリズムは相関関数の計測 や逆行列の計算を必要としないという特徴を有している［14］．

 正規化LMS（NLMS）アルゴリズムは，Nag1mo，Noda［16］とA1bert，Gar（1ner［17］

によって独立に提案された．NLMSアノレゴリズムにおいてはフィルタ係数ベクトル は以下のように更新される．

       ρ

       ん（7z＋1）二ん（η）十    e（η）u（η）       （32）

      l1他（η川2

ここで，IIu（η）l12はタップ入力ベクトルu（η）の2乗ノルム，μは正の定数である．

NLMSアルゴリズムが収束するための必要十分条件は以下の式で与えられる［43］．

0＜μ＜2         （3，3）

 NLMSアルゴリズムはLMSアルゴリズムよりも高速であり［！8］，また収束速度が 入力信号によらないという利点を有する．

3．2．3 アフィン射影アルゴリズム（APA）

 アフィン射影アルゴリズム（a冊ne projection a1gorithm二APA）は適応フィルタ のアルゴリズムとして尾関，梅田により提案された［191．図3．3はAPAによるフィ ルタ係数更新を示している．図3．3において，パは適応の目標，すなわち未知シス テムに対する最適な同定である．また2つの超平面は，それぞれ異なる時間ステッ プでの2つのタップ入力ベクトルu1，u2を法線とし，それぞれのタップ入力ベク

トルに対して望みの値を出力するようなフィルタ係数の集合である．フィルタ係数

ベクトルは超平面の交わり，すなわち， アフィン部分空間 に向かって垂直に更新 される．ん次のARへ （ん一APA）においては，1回の更新にん個の超平面を用いる．

すなわち図3．3は，次数んが2でタップ入力ベクトルu1，仙2が3次元である場合を 表していることになる．この場合，超平面は2次元になるので，その交わりは1次元 の直線1で渉）る．APAにおいてはPQ／P0を一定として各更新を行う．1−APAは NLMSアルゴリズムと等価である1191ので，APAはNLMSアノレゴリズムをブロック 適応アノレゴリズムに一般化したアルゴリズムであると言うことができる．戸◎／戸σ をμ〃λとおくと，APAが収束するための必要十分条件は以下のようである［19］．

0＜μλ戸λ＜2       （3．4）

仙² 仙

■

ん（肌十1）        ん＊、

   R ρ

Z      P

       ん（肌）

図3．3：APAにおけるフィルタ係数更新．

3．2．4 等比学習アルゴリズム（GlLA）

 前章で述べたように，図2．1に示すパーセプトロンの分離超平面は原点を通る．

よってその交わりも原点を通る．すなわち，この交わりは入力ベクトル空間の 部 分生問 であり， アフィン部分空間 とよぶ必要はない・

 この理由により，パターン分類を行うためのパーセプトロンの学習にAPAを適用 するアルゴリズムを新たに 等比学習アルゴリズム （9eometric1eaminga1gorithm GLA） とよぶことにする．この名称は，更新ベクトルの長さ（刃）と，結合荷 重ベクトルから交わりに下ろした垂線の長さ（戸σ）の比が一定であることに由来

している．そしてこの比珂／戸σを学習係数と呼び，λで表すことにする．また，

ん一APAに対応するアルゴリズムをん次の等比学習アルゴリズム（ん一GLA）とよぶ．

すなわち，ん一GLAにおいては，各時点での結合荷重ベクトルの更新のために，その 時点でパーセプトロンの出力と望みの出力が異なるようなパターンの中のん個を用 いる．トGLAを以下に示す．

［step11ω（0）を乱数で初期設定する．

［step21パーセプトロンの出力が望みの出力と異なるパターンの個数をん。とする．

［step31ん。こ0なら収束と判定し終了する．

［・t・p41

 もしんO≧んならば

       X＝（π ，皿2，…，πた）T      （3・5）

40 41

 そうでないなら

       X＝（・ ，π2，…，πた。）T

［step51結合荷重を次式で更新する．

      ω（η十1）＝ω（η）一λX＋Xω（η）

（3．6）

（3．7）

［step6］step2に戻る．

ここでX＋はXのMoore−penrose一般逆行列である．また，Tは行列の転置を表

す．式（3．5），（3．6）において 1〜がまたは 1〜 ん・は，パーセプトロンの出力 が望みの出力と異なるパターンから選択する．この選択をどのような規則で行うか についてはここでは規定しない．

 Moore−Penrose一般逆行列の性質より，X＋XはX＋の列空間への直交射影行 列であり［44］，X＋の列生問はXの行空間である［45］から，図3．4に示すように式

（3．5）〜式（3．7）は，毎回の結合荷重更新が，選択されたん個またはん。個のパター ンベクトルの直交補空間に向かって垂直に行われることを表している．すなわち図 3．4において，選択されたパターンベクトノレ 1， 2の直交補空間02（η）に向かって 垂直に行われる．

 APAは適応フィルタのアルゴリズムであるから，フィルタ係数更新の目標は未知 システムに対する最適な同定であり，これは ある1点 である．一方，GLAはパー セプトロンでパターン分類を行う際の学習アルゴリズムであるから，結合荷重更新の

目標は与えられたすべてのパターンを正しく分類するような・ある領域・である．そ れゆえ，GLAの収束条件は式（3．4）に示されたAPAの収束条件とは異なる．GLA

ω（肌十1）

0

0。（肌）

一λX＋Xω（肌）

     ω（肌）

       1            π

rXω（肌）

図3．4：GLAにおける結合荷重更新．