確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究

Presentation on theme: "確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究"— Presentation transcript:

1 確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
北陸先端科学技術大学院大学 知識科学研究科 知識システム構築論講座　林研究室 近藤　雅之

2 発表の流れ 背景・目的 確率的学習アルゴリズム 単純再帰型回路網への適用 実験・結果 考察・まとめ

3 背景１ ニューラルネットワークの記号処理への応用
単純再帰型回路網(SRN)で単純なFSAの学習を行った (Schreiber et al.[1989]) 隠れ層の活性化パターンのクラスタが、FSAの各状態を表わしていると主張 2次結合の再帰型神経回路網(RNN)を用いて正規言語同定問題(Giles et al.[1992]) いくつかの場合にFSAの獲得に失敗している

4 背景２ SRNは正規言語を(条件付きで)学習できる 隠れ層の状態から、ネットワークがどのようなFSAを獲得したかわかる
ネットワークを構成する素子の出力関数にシグモイド関数を用いている 活性値が連続値　→　FSAの抽出困難

5 背景３ そこで線形閾値素子を用いる 線形閾値素子を用いた学習アルゴリズムが存在しなかった 活性値が離散値 → FSAの抽出容易
離散値であるために微分ができない 　→　BP法が適用できない しかし

6 背景４ 確率的学習アルゴリズム（S-MLP）が提案される［櫻井,2001］ 素子の出力が離散値である回路網を学習できる特徴に着目
線形閾値素子を用いている 大域的な収束性かつ高速 解が離散値で表現される　→　解釈が容易 素子の出力が離散値である回路網を学習できる特徴に着目

7 研究の目的 S-MLPをSRNに適用し、実際にFSAを学習できるかどうかを調べる

8 確率的学習アルゴリズム 線形閾値素子からなる多層神経回路網(MLP)を対象とした学習アルゴリズム データ提示のたびに素子を確率的に選択
選択された素子への結合荷重をRosenblattのパーセプトロン・アルゴリズムに従い更新 本研究では、S-MLPを改良したPS-MLPを用いた

9 学習アルゴリズム I H O x1 x2 x3 y (yt) 0.5 w1 w2 w3 0.5 0.1 0.2

10 単純再帰型回路網(SRN) Elmanによって提案される。 RNNのもっとも単純なものの一つ。
一時刻前の隠れ層の出力をそのまま文脈層にコピーする。 過去の情報を持つ文脈層を入力に加えることにより、時系列のパターンを学習することができる。

11 モデル T=t+1 出力層 フィードバック 隠れ層 T=t 入力層 文脈層 図１　SRN:本研究もこのモデルを扱った

12 数値実験 初期値設定 正規文法の一例である富田文法を用いた 入力に対し、現在の状態が受理状態にあるか非受理状態にあるかを教示
結合荷重の初期値は-2.0～2.0の整数値をランダムに設定 文脈層の初期値は全て1.0と設定 正規文法の一例である富田文法を用いた 入力に対し、現在の状態が受理状態にあるか非受理状態にあるかを教示

13 富田文法（１） 以下の4種類について実験を行った 1. 奇数個の1の後に奇数個の0が続かない 2. 0が３つ以上連続しない
3. 1と0の個数の差が3の倍数である 4. 0*1*0*1* 文法1の例

14 富田文法（２） 初期状態 1入力の遷移 0入力の遷移 受理状態 非受理状態 図2　文法１の状態図

15 実験1 100回の試行中何回学習が収束するか 長さ3～6の文を40個、ランダムに生成 データ提示回数と平均収束時間を計測
隠れ層の素子数を変えて実験 表1　入力データの例:1 input 1 teacher

16 結果 実験1 全ての文法が、全ての試行で学習が収束した hidden units ３ ４ ５ data ave. ７８７７ ４８９２
結果　実験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

17 実験2 長さ３～５までの全てのbitパターンを網羅したデータ 隠れ層の素子数を変えて実験 隠れ層の状態からFSAを抽出 3 ・・・ 5
表3　入力データと教師信号の例：1 length 3 ・・・ 5 input 000 001 010 11101 11110 11111 teacher 111 110 11100

18 結果 実験2 (1) 1、2、4の文法では最小状態数のFSAが得られた場合があった hidden units 3 4 5
結果　実験2 (1) 1、2、4の文法では最小状態数のFSAが得られた場合があった 表4　1の実験結果 hidden units 3 4 5 state Ave. 6.3 7.6 8.0 state min. 6 right/wrong 43/13

19 結果　実験2 (3) 初期状態 1入力の遷移 0入力の遷移 受理状態 非受理状態 図3　文法１：隠れ素子数３、４個の時の最小状態数のFSA

20 結果　実験2 (4) 初期状態 1入力の遷移 0入力の遷移 受理状態 非受理状態 図4　文法１：隠れ素子数5個の時の最小状態数のFSA

21 考察 S-MLP（PS-MLP)を用いたSRNはFSAを学習できる → S-MLPをSRNに適用できる
状態数が最小でも正解でない場合もあった 隠れ層の素子数が多い（自由度が高い）ほうが収束が速い 最小状態数のFSAを得にくいが、比較的少ない状態数に落ち着く

22 今後の課題 より複雑なFSAの学習について調べる 学習後のネットワークを用いて長い文でテストを行う
状態数の多いもの 学習後のネットワークを用いて長い文でテストを行う 言語学習の一般的な教示方法を用いてみる(文法獲得の可能性の調査） 文法的に正しい文の次単語を予測 各文が文か非文かを教示する S-MLPに関する課題 どのような確率分布を与えると最適か？

23 SRNへの適用（アルゴリズム） 各文にラベルを持たせる（収束か未収束） 各文の１入力毎にもラベルを持たせる アルゴリズム
ランダムに文を選び、文の最初から計算する 文の途中で教師信号と異なる信号を出力したら、荷重更新をおこない、またその文の最初から計算をおこなう。また、全ての文を未収束とラベル付けする。 その文に関して、最後まで教師信号と同じ出力であれば、その文は収束したと見なし、収束のラベル付けを行う 以上を全ての文について行う。

24 学習アルゴリズム ラベル Data[1] 000000 satisfied unsatisfied ・・・ Data[x] 001001
110010 satisfied ・・・ Data[n] 111111 satisfied