確率的学習アルゴリズムを用いた有限
状態オートマトンの抽出に関する研究
北陸先端科学技術大学院大学
知識科学研究科
知識システム構築論講座 林研究室
近藤 雅之
発表の流れ
1.
2.
3.
4.
5.
背景・目的
確率的学習アルゴリズム
単純再帰型回路網への適用
実験・結果
考察・まとめ
背景1

ニューラルネットワークの記号処理への応用

単純再帰型回路網(SRN)で単純なFSAの学習を
行った (Schreiber et al.[1989])


隠れ層の活性化パターンのクラスタが、FSAの各状態
を表わしていると主張
2次結合の再帰型神経回路網(RNN)を用いて正
規言語同定問題(Giles et al.[1992])

いくつかの場合にFSAの獲得に失敗している
背景2



SRNは正規言語を(条件付きで)学習できる
隠れ層の状態から、ネットワークがどのような
FSAを獲得したかわかる
ネットワークを構成する素子の出力関数にシ
グモイド関数を用いている

活性値が連続値 → FSAの抽出困難
背景3

そこで線形閾値素子を用いる

活性値が離散値 → FSAの抽出容易
しかし

線形閾値素子を用いた学習アルゴリズムが存
在しなかった

離散値であるために微分ができない
→ BP法が適用できない
背景4

確率的学習アルゴリズム(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
図1 SRN:本研究もこのモデルを扱った
数値実験

初期値設定




結合荷重の初期値は-2.0~2.0の整数値をランダ
ムに設定
文脈層の初期値は全て1.0と設定
正規文法の一例である富田文法を用いた
入力に対し、現在の状態が受理状態にあるか
非受理状態にあるかを教示
富田文法(1)
以下の4種類について実験を行った
1. 奇数個の1の後に奇数個の0が続かない
2. 0が3つ以上連続しない
3. 1と0の個数の差が3の倍数である
4. 0*1*0*1*
文法1の例
0000110001110001
富田文法(2)
受理状態
非受理状態
初期状態
1入力の遷移
0入力の遷移
図2 文法1の状態図
実験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
3
4
5
data ave.
7877
4892
3836
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



長さ3~5までの全ての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 文法1:隠れ素子数3、4個の時の最小状態数のFSA
結果 実験2 (4)
受理状態
非受理状態
初期状態
1入力の遷移
0入力の遷移
図4 文法1:隠れ素子数5個の時の最小状態数のFSA
考察


S-MLP(PS-MLP)を用いたSRNはFSAを学習
できる → S-MLPをSRNに適用できる
最小状態数のFSAを獲得できるときがあった


状態数が最小でも正解でない場合もあった
隠れ層の素子数が多い(自由度が高い)ほ
うが収束が速い

最小状態数のFSAを得にくいが、比較的少ない
状態数に落ち着く
今後の課題

より複雑なFSAの学習について調べる



学習後のネットワークを用いて長い文でテストを行う
言語学習の一般的な教示方法を用いてみる(文法獲
得の可能性の調査)



状態数の多いもの
文法的に正しい文の次単語を予測
各文が文か非文かを教示する
S-MLPに関する課題

どのような確率分布を与えると最適か?
SRNへの適用(アルゴリズム)



各文にラベルを持たせる(収束か未収束)
各文の1入力毎にもラベルを持たせる
アルゴリズム




ランダムに文を選び、文の最初から計算する
文の途中で教師信号と異なる信号を出力したら、荷重更新
をおこない、またその文の最初から計算をおこなう。また、
全ての文を未収束とラベル付けする。
その文に関して、最後まで教師信号と同じ出力であれば、
その文は収束したと見なし、収束のラベル付けを行う
以上を全ての文について行う。
学習アルゴリズム
ラベル
Data[1]
・
・
・
Data[x]
000000
satisfied
unsatisfied
001001
unsatisfied
unsatisfied
satisfied
unsatisfied
satisfied
unsatisfied
Data[x+1] 110010
・
・
・
Data[n]
111111
ダウンロード

確率的学習アルゴリズムのリカレントニューラル