確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究北陸先端科学技術大学院大学知識科学研究科知識システム構築論講座林研究室近藤雅之発表の流れ 1. 2. 3. 4. 5. 背景・目的確率的学習アルゴリズム単純再帰型回路網への適用実験・結果考察・まとめ背景１  ニューラルネットワークの記号処理への応用  単純再帰型回路網(SRN)で単純なFSAの学習を行った (Schreiber et al.[1989])   隠れ層の活性化パターンのクラスタが、FSAの各状態を表わしていると主張 2次結合の再帰型神経回路網(RNN)を用いて正規言語同定問題(Giles et al.[1992])  いくつかの場合にFSAの獲得に失敗している背景２    SRNは正規言語を(条件付きで)学習できる隠れ層の状態から、ネットワークがどのような FSAを獲得したかわかるネットワークを構成する素子の出力関数にシグモイド関数を用いている  活性値が連続値 → FSAの抽出困難背景３  そこで線形閾値素子を用いる  活性値が離散値 → FSAの抽出容易しかし  線形閾値素子を用いた学習アルゴリズムが存在しなかった  離散値であるために微分ができない → BP法が適用できない背景４  確率的学習アルゴリズム（S-MLP）が提案される［櫻井,2001］     線形閾値素子を用いている大域的な収束性かつ高速解が離散値で表現される → 解釈が容易素子の出力が離散値である回路網を学習できる特徴に着目研究の目的   S-MLPをSRNに適用し、実際にFSAを学習できるかどうかを調べるそのための実験として、正規言語の学習を行い、隠れ層の状態からFSAの抽出を行う確率的学習アルゴリズム     線形閾値素子からなる多層神経回路網(MLP) を対象とした学習アルゴリズムデータ提示のたびに素子を確率的に選択選択された素子への結合荷重をRosenblattのパーセプトロン・アルゴリズムに従い更新本研究では、S-MLPを改良したPS-MLPを用いた学習アルゴリズム I x1 H w1 O 0.5 w2 x2 x3 w3 0.1 0.2 0.2 y (yt ) 単純再帰型回路網(SRN)     Elmanによって提案される。 RNNのもっとも単純なものの一つ。一時刻前の隠れ層の出力をそのまま文脈層にコピーする。過去の情報を持つ文脈層を入力に加えることにより、時系列のパターンを学習することができる。モデル出力層隠れ層入力層フィードバック文脈層 T=t+1 T=t 図１ SRN:本研究もこのモデルを扱った数値実験  初期値設定     結合荷重の初期値は-2.0～2.0の整数値をランダムに設定文脈層の初期値は全て1.0と設定正規文法の一例である富田文法を用いた入力に対し、現在の状態が受理状態にあるか非受理状態にあるかを教示富田文法（１）以下の4種類について実験を行った 1. 奇数個の1の後に奇数個の0が続かない 2. 0が３つ以上連続しない 3. 1と0の個数の差が3の倍数である 4. 0*1*0*1* 文法1の例 0000110001110001 富田文法（２）受理状態非受理状態初期状態 1入力の遷移 0入力の遷移図2 文法１の状態図実験1     100回の試行中何回学習が収束するか長さ3～6の文を40個、ランダムに生成データ提示回数と平均収束時間を計測隠れ層の素子数を変えて実験表1 入力データの例:1 input teacher 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 結果実験1  全ての文法が、全ての試行で学習が収束した表2 1の実験結果 hidden units ３４５ data ave. ７８７７４８９２３８３６ max. 42449 30016 36645 min. 219 69 62 time ave. 1.92s 3.16s 1.01s right/wrong 30/10 30/10 30/10 実験2    長さ３～５までの全てのbitパターンを網羅したデータ隠れ層の素子数を変えて実験隠れ層の状態からFSAを抽出表3 入力データと教師信号の例：1 length 3 3 3 ・・・ 5 5 5 input 000 001 010 ・・・ 11101 11110 11111 teacher 111 111 110 ・・・ 11100 11111 11111 結果実験2 (1)  1、2、4の文法では最小状態数のFSAが得られた場合があった表4 1の実験結果 hidden units 3 4 5 state Ave. 6.3 7.6 8.0 state min. 5 5 6 right/wrong 43/13 43/13 43/13 結果実験2 (3) 受理状態非受理状態初期状態 1入力の遷移 0入力の遷移図3 文法１：隠れ素子数３、４個の時の最小状態数のFSA 結果実験2 (4) 受理状態非受理状態初期状態 1入力の遷移 0入力の遷移図4 文法１：隠れ素子数5個の時の最小状態数のFSA 考察   S-MLP（PS-MLP)を用いたSRNはFSAを学習できる → S-MLPをSRNに適用できる最小状態数のFSAを獲得できるときがあった   状態数が最小でも正解でない場合もあった隠れ層の素子数が多い（自由度が高い）ほうが収束が速い  最小状態数のFSAを得にくいが、比較的少ない状態数に落ち着く今後の課題  より複雑なFSAの学習について調べる    学習後のネットワークを用いて長い文でテストを行う言語学習の一般的な教示方法を用いてみる(文法獲得の可能性の調査）    状態数の多いもの文法的に正しい文の次単語を予測各文が文か非文かを教示する S-MLPに関する課題  どのような確率分布を与えると最適か？ SRNへの適用（アルゴリズム）    各文にラベルを持たせる（収束か未収束）各文の１入力毎にもラベルを持たせるアルゴリズム     ランダムに文を選び、文の最初から計算する文の途中で教師信号と異なる信号を出力したら、荷重更新をおこない、またその文の最初から計算をおこなう。また、全ての文を未収束とラベル付けする。その文に関して、最後まで教師信号と同じ出力であれば、その文は収束したと見なし、収束のラベル付けを行う以上を全ての文について行う。学習アルゴリズムラベル Data[1] ・・・ Data[x] 000000 satisfied unsatisfied 001001 unsatisfied unsatisfied satisfied unsatisfied satisfied unsatisfied Data[x+1] 110010 ・・・ Data[n] 111111