成果論文

複雑 さの構 造 的解析 法 の研究 とそ の応用
一
十算論 的学習 理論 に関す る研究成果
渡辺 治
東京 工 業 大学 情 報 理工 学研 究科
計算 工 学専攻 助 教 授
. は じめに
コ ンピュー タにいろ いろな処理を させ る場合、その 処理が難 しい問題 もあれば容易 な問題 もあ
る。 しか し、 この 一 見当た り前 に思え ることで も、 で は何故、あ る問題 の 計算 が難 しく、 また
一
方 で ( 似たよ うな) 別 の 問題 の計算がや さ しいのか 、 とい った疑間に正確 に答え るの は非常 に難
しい。 しか し、問題 の難 しさの本質 が 明確 にな らな い限 り、 よい解決方法 ( アル ゴ リズ ム) を 科
計算 の難 しさの構造的解析 J と 呼ばれて い る研
学的 に構成す ることは不 B I 能に近 い。 そ こで 、 「
究分野 で は、問題の難 しさの本質 を探 る方法 を開発 し、それ によ って難 しさの本質を突 き止 め る
研究を して い る。本研究で は、 構造的解析 の手法を計算論的学習理論 に応 用 し、代表的な帰納学
習 の性能 と問題点 を調 べ たc
計算論的学習 理論 は、従来、経験的あるいは実験科学的 に研究 されて きた学習 ( 主に機械学習)
に関す る研究 を、計算手法 ( アル ゴ リズ ム) と い う観点か ら、 よ り数学的 に解明 しよ うとい う研
ー
究分野で ある。 この分野 で は、いろ い ろな学習過程を コ ンピュ タの学習問題 と して モデル 化 し
「
議論 して いる。本研究 で は、代表的な モ デ ルの 1 つ であ る 質問 による学習 J ( q u e r y l e a r n i n g )
について 、その難 しさや学習 アル ゴ リズ ム について考察 した。
2 . 本 研究 で考え る 「学習」 とは
ー
一 般 には 「
学習 J と い うと、人間が行 な うよ うな万能型 の学習 が イメ ジされ る。 しか し、 こ
こで考 え る学習 は、 もっ とず っ と単純で、問題領域を非常 に限定 した中で の学習 である。 つ ま り、
ー
学習対 象が あ る特定 の型 に定 ま って いて 、その 中で ( ヨ ンピュ タな どに) 与 え られた対象 が何
であるかを同定 させ ることを考えて い る。
start
apple
図 1 : 単 純 な ジュー スの 自動販売機 の構造
注) こ こで は図を簡単 にす るために、実際 の 自動販売機 を非常 に単純化 した もの を考えて いる
-18-
‐例 と して ジュー スの 自動販売機 の学習 を考えてみ よ うc こ れ は ジュー スの 自動販売機 の 内部
ー
構造 を、図 1 の よ うな流れ図 と して表す問題であ る。 もちろん、与え られた ジュ スの 自動販売
機 の 中身を見 れば、それか ら図 1 の よ うな流れ 図を作 るのは、そ う難 しい ことで はない。 そ う し
た完全な内部情報がな い状態 で、 限 られた ( 間接的 な) 部 分情報 か ら、流れ図を構成す るのが我
々の学習問題 であ る。
た とえば、対象 とな る ジュー スの 自動販売機 の ことをよ く知 って いる人が いた と しよ う。 その
1 0 0 円を入れた らどうな りますか ? J と い った質問を繰 り
人 ( これを教師 とい う) に 対 して、 「
返 し、その 答 えを総合 して流れ図を作成す る。 これが本研究 の対象であ る質問による学習 ( 以下
で は単 に質問学習 と呼ぶ ) で あ る。 その他 に も、実際 に ジュー スの 自動販売機 に対 して、 い ろ い
ろな操 作 を ラ ンダ ム に行 な い 、 その 結 果 の 観察 か ら内部構造 を推 定 す る学 習 もあ る。 これ は
n g ) と ている。
習 ( P r o b a b l y A p p r o x i m a t e l y C o r r e c t L e a r n i 呼ばれ
一
この よ うに、 「
学習 J と はい って も、 般 にイメー ジされ る学習 とは異な り、か な り限定 され
PAC学
た形 の学習 で あ る。 しか し、 こ うした限定 された学習問題 で も、 コ ンピュー タの利用技術 の進歩
に、 い ろ い ろな形でかかわ って くる ことがで きる。
その 一 例 と して、 コン ピュー タを利用 した要求仕様書 の作成方法 を考えてみ よ う。上記 の流れ
図 は、 一般 にはオ ー トマ トン ( 有限状態機械) と 呼ばれ て い る。実際 の応用場面で は、 作成 した
い機械、 ソフ トウ ェア、 あるいは通信 システムな どが、 このオ ー トマ トンで記述で きる場合が し
ー
ば しばあ る。 しか し、 その機械 の注文者 に、 機械 の 内部状態を オ トマ トンの形 で形式的 に記述
ー
す るよ う要請 して も、難 しい場合が多 い。 そ こで 、 もしオ トマ ンを質問学習 によ り構成す るプ
ロ グラムがあれば、機械 の注文者を教師 に見立 て、注文者 にいろ い ろ と質問を繰 り返 しなが ら、
ー
所望 の機械 の使用を要領良 くオ ー トマ トンに まとめること も可能 だろ う。 つ ま り、 コ ンピュ タ
の助 けを借 りなが ら、その機械 の 要求仕様 を厳密 に作成す ることがで きるので あ る。 しか しその
ためには、 よ り少 ない質問回数 で、 しか も効率 よ く、 オ ー トマ トンを作成す る計算手法 ( アル ゴ
リズム) が 重要 にな って くる。 それが、以 下 に述 べ る質問学習 の効率 に関す る研究 の主 な動機 で
あ る。
3 . オ ー トマ トンの質問学習 の効率 について
Angiuin〔
1 , は、オ ー トマ トンを多項式時間以 内 に同定す る質問学習 のアル ゴ リズ ムを発見 し
た。 この学習 アル ゴ リズ ムで は、 所属質問 と同値質問が用 い られ る。所属質問 とは、入力例 に対
してオ ー トマ トンが どのよ うに反応 す るかを聞 く質問 である。 た とえば、先 の 自動販売機 の例 で
5 0 0 円を入れ るとどうな るか ? 」 とい うよ うな質問であ る。 一方、同値質問 とは、オ
言 えば、 「
ー トマ トンの 状態遷移図 を仮説 と して提示 して、それが所望 のオ ー トマ トンで あるかを聞 く質問
の こと。 た とえば、 自動販売機 の流れ図を示 し、 これが正 しい 内部構造 であ るかを聞 くよ な質問
で ある。 ( 先に述 べ たよ うな応用で は、同値質問をす るのが難 しい場合 が考え られ る。 そのよ う
な場合 には、 直接教師 に同値質問をす るので はな く、 い くつ かの入力例 によ り実験を行 な うこと
によ り、仮説 のオ ー トマ トンの整合性 を チ ェックす る手法が妥当だ ろ う。)
1 , の 提案 したアル ゴ リズ ムで は、状態数 n の オ ー トマ トンを同定す るのに、 0 ( n )
Angluin〔
回 の 同値質問 と、 O ( n 2 ) 回
の所属質問が必要 にな る ( なお、計算時間 は0 ( n 3 ) 程
-19-
度) 。 本研
究で は、 この 質問回数 が改善で きな いか を調 べ たG
ー
以下で は次 のよ うな記法 を用 い る : オ トマ トンの学習 アル ゴ リズ ム A に 対 し、
ー
# 砲c 砲 一q レc r υ
ム( ■) = 状 態 数 れ のオ トマ トンを学習す るた めに必 要 な所属質問 の数。
# c q ″―q t t r υム( れ) = 状 態数 れ のオ ー トマ トンを学習す るために必要 な 同値質問 の 数c
まず、同値質問が本質的 であるかについて調 べ た。 同値質問 は、 所属質問 に比 べ て はるか に実
現 に コス トがかか る。 したが つて 、同値質問が な るべ く少 ない方 が よい。 しか し比較的簡単 な議
論 で 、 同値 質 問 は必 要 で あ る こ とが 証 明 で き る。 我 々 は、学 習 ア ル ゴ リズ ム を ラ ン グ ム 化
( r a n d o m i z e d ) し、多少誤 ることを許 した と して も、同値質問 はやは り本質的 であ ることを証明
した。
定理 1 . 任 意 の オ ー トマ トンの 学 習 アル ゴ リズ ム A を 考 え る。 ただ し、 A で は、 ラ ンダム化 を
許 し、適 当 な定数 δ以 下 の誤 り率を許す ことにす る。 この とき、 もしA が 所属質問 だけ しか しな
い とす ると、 その 回数 に関 して次 の下限が成 り立 つc
-1.
存向c〃と一 q″crυ_4(れ
)≧ δ2几
このよ うに、オ ー トマ トンの学習 には、 同値質問が本質的なので あ るが、実 は、所属質問 も同
2 〕によって示 されて い る。 この ことか ら、所属質問 と同値
様 に本質的 で あることが、A n g l u i n 〔
質問 の 間 には トレー ド ・オ フの 関係があ るもの と予想 され る。本研究で は、 これを以 下 に示す 2
つの定理 によ り実証 した ( なお、最初 の定理 の証明で は構造的解析 において使われて い る、 ア ド
バ ーサ リー法を用 いた) 。
定理 2.Aを
、オ ー トマ トンの学習 アル ゴ リズ ム とす る。 また f(n)<nを
任意 の非定数関数 とす
る。 この とき、あ る定数cl,c2に対 し、次 のいずれ かが成 り立 つ :
# c 鍛―q ″ υA ω ≧
赫
Or
卿一
#確
れ―
∽グ
択づ≧
番・
定理 3 . 任 意 の f ( n ) ( n に
対 し、次 の評価式を満 たす よ うなオ
を構成で きる :
―q " c r灯
帯
cq″
)≦
υ( れ
x れ) ' a 材
)qメ
一
#向c砲 q,crソ
んKれ)≦2/1几 れ).
ただ し竹 は適 当 な多項式。
-20-
ー トマ トンの学習 アル ゴ リズ ム A
たとえば、定理 2よ り、まともな計算時間 (多項式時間)内 にオー トマ トンを同定す るために
は、 どうして もn/1og n回の同値質問 は必要であることがわかる。 一方、 n/10g n回の同値質問
で十分多項式時間以内に同定で きることが、定理 3に よ って示されて いる。
なお、 ここまでの結 果の詳細 は論文 〔4〕を参照 されたい。
さらに我 々は、並列計算でオー トマ トンを同定する手法について考察 した。実は、定理 3の 手
法は並列計算 に比較的む いてお り、それを うま く改良す ると約 0(n/1og n)時 間の並列学習アル
ゴ リズムが作れ る。一方、 どのよ うな並列アルゴリズムを考えて も、同値質問の回数 n/10g nだ
けは、 どうして も時間がかか って しまうことも証明で きた。すなわち、0(n/1og n)時 間の並列
学習 アル ゴ リズ ムは最適なアル ゴ リズムなのである。正確には、次の定理が得 られた (詳しくは
〔5〕参照)。
定理 4 . オ ー トマ トンの学習をす る0 ( n / 1 o g n ) 時間 の P R A M ア
も、 オ ー トマ トンの学習をす る P R A M ア
ル ゴ リズ ムが 構成 で きる。 しか
ル ゴ リズ ムで、計算 時間が 0 ( n / 1 o g n ) のものは存在
しな い。
4.質 問学習 の難 しさにつ いて
いままで述 べ て きたよ うに、オ ー トマ トンの質問学習 には、かな り効率 の よいアル ゴ リズ ムが
存在す る。 ところが、実際 の応用面で は、オ ー トマ トンよ りもう少 し複雑 なメカニ ズムの 同定 で
きれば都合 のよい場合 が、 しば しば生 じる。 た とえば、文脈 自由文法 などが 同定 で きるよ うにな
ると、 自然言語処理 へ の応用 の可能性 も広が る。 そ うした、 よ リー般的 な メカニ ズ ムの学習 は、
どの程度可能 なのだろ うか ?
こ う した研究 のため、渡辺 〔6、 7〕は、構造的解析 の手法 を利用 して、質問学習可能性 を調 べ
るための枠組 を提案 した。 その枠組 にそ った研究 の結果が、以下 に述 べ る 2つ の定理で あ る。 な
お、以下で は、説明を単純 にす るた めに、多少簡単化 して いる部分 もあ る。詳 しくは論文 〔8〕を
参照 された い。
定理 5.文 脈 自由文法 を質問学習 アル ゴ リズ ム は、 (教師 の助 けを借 りて も)高 々 P(NP())程
度 の計算能力 しか もた ない。 さ らに、性質 Rを 持 つ文脈 自由文法を質問学習す る場合 には、 ち ょ
うどP(NP())計
繰 り返 し文を内
算能力を持 つ ことがで きる (なお、性質 Rを 簡単 にい うと 「
包 して いるJと い う性質)。
す なわち、あ る種 の文脈 自由文法 で、その学習問題 の難 しさが P(NP(う
)を 越えた とす ると、
一
この 定理 よ り、 その種 の 文脈 自由文法を、多項式時間以内 に同定す るの は不可能 にな る。 方、
性質 Rを 持 つ文脈 自由文法 の学習不可能性 が証 明 で きた とす ると、難 しさが P(NP())を
越え
る学習問題 を示す ことがで きる。
このよ うに、 文脈 自由文法を同定す る学習問題を考え ると、その計算 の複雑 さが、多項式時間
階層 の どこに位置す るかが、文脈 自由文法 の学習可能性 に結 び付 いて くる。で は、 その 問題 が実
-21-
際 に多項式時間階層 の どこに位置す るかを考えてみ ると、次 のよ うな定理が示せ る。
定理 6 . 文 脈 自由文法を同定す る学習問題 の難 しさは、高 々 P ( N P ( N P ( ) ) ) 程
しか し、文脈 自由文法 の学習問題 が、難 しさが P ( N P ( ) ) を
度であ る。
越え るか否か は、 まだ未解決て
ある。
5 。 おわ りに
計算 の複雑 さの構造的解析 の手法を用 いて 、質問 による学習 の効率 の評価、 な らびに学習可能
一
性 の検討 を行 な った。今後 の課題 と して は、 まず第 に、文脈 自由文法 の 質問学習 の可能性 を、
さ らに深 く追求す ることが重要である。ただ し、今 まで の研究か らの経験 で は、 文脈 自由文法 が
す べ て 質問学習可能 であ るか は、かな り疑わ しい。 そ こで、 どの程度 の文脈 自由文法 が学習可能
かが重要 にな って くるだろ う。 とくに、平均的 な学習可能性 の解析 が興味深 い。 その他 の課題 と
して は、 P A C 学
習 な どの よ うな他 の学習 モ デ ル と、質問学習を融合 した形 の学習 モ デ ルの解析
もお もしろ いだ ろ う。
高
団 な らびに
最後 に、 本研究 の遂行 に多大 な ご援助 を頂 きま したl R l l柳記念電子科学技術振興財
財団 の 関係者 の皆様 に深 くお礼 申 し上げます。
参考文献
〔1〕 D. Angluin, しearning regular sets from queries and counterexamples,
Information
and Computation, Vol,75, pp.87-106 (1987).
〔2〕 D. Angluin, Negative results for equivalence queries, Machine Learning, Vol. 5, pp.
121-150(1990),
〔3〕 」. BalCazar, J. Diaz, R. Gavalda, and O, Wa↓ anabe,
of learning DFA",
A note on the query complexity
“
in Proc. Third Workshop on Algorithmic Learning Theory, Japanese
Society for Artificial intelllgence, pp.53-62 (1992).
〔4〕 」. Balcazar, J. Diaz夕 R. Gavaldあ, and O.Watanabe, The query complexity of learning
DFA, New Generation Computing, Vol. 12, pp.-337-358 (1994).
〔5〕 」.
Balcazar, J. Dlaz, R. Gavalda, and oo watanabe An optimal parallel algorithln
for learning DFA,
in Proct 7th ACM Conference on Computational Learning Theory,
ACM, New York, 208-217 (1994).
〔6〕 0, Waranabe, A formal study of learning via queries, in Proc, 17th lnternatlonal
Colloquium on Automata, Languages and Programming, し
ecture Notes in Computer
Science 443, Springer一Verlag, pp, 137-152 (1990).
〔7〕 0. Watanabe A framework for polynomial time query learnabllity, Mathematical
Systems Theory, Vol. 27, 211-229 (1994).
〔8〕 R. Gavalda and O. watanabe, Structural analysis of 9olynomial time query learn―
ability, Mathematical Systems Theory, Vol. 27, 231-256 (1994).