WEKO3
アイテム
形式文法の確率的一般性とその応用に関する研究
https://doi.org/10.15083/00002383
https://doi.org/10.15083/00002383975a3b2e-aaad-462c-a2eb-923b4bf35e41
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2012-03-01 | |||||
タイトル | ||||||
タイトル | 形式文法の確率的一般性とその応用に関する研究 | |||||
言語 | ||||||
言語 | jpn | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 計算機科学 | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 学習理論 | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_46ec | |||||
タイプ | thesis | |||||
ID登録 | ||||||
ID登録 | 10.15083/00002383 | |||||
ID登録タイプ | JaLC | |||||
著者 |
柴田, 剛志
× 柴田, 剛志 |
|||||
著者別名 | ||||||
識別子Scheme | WEKO | |||||
識別子 | 6621 | |||||
姓名 | シバタ, タケシ | |||||
著者所属 | ||||||
著者所属 | 東京大学大学院工学系研究科 電子工学専攻 | |||||
Abstract | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | 近年、正例からの学習の分野において、文脈自由文法の非正則なサブクラスで、効率的に学習可能なクラスが発見されてきた。Very Simple Grammar(VSG) のクラスや、その拡張である Right-unique Simple Grammar(RSG) のクラスがそうである。両者はともに Simple Grammar(SG) とよばれる文法のサブクラスである。これらの効率的学習アルゴリズムに対していろいろな応用を考えることができる。そのひとつとして、本論文では強化学習へ応用する方法を提案している。強化学習の理論的な基礎となっている確率モデルはマルコフ決定過程であるが、有限状態マルコフ決定過程にスタックを付与した決定過程を考えると、状態とスタックの組は、RSG とみなすことができ、観測の履歴は、RSG の正例となる。したがって、RSG の学習アルゴリズムを用いればもとの文法、即ち状態とスタックの組を推定することができる。しかし、この場合、言語が等しいだけでは正しい文法を学習したといえず、確率言語の意味で齟齬のない文法を出力しなければならない。これは次の結果を用いると解決することができる。本論文では、SG に対する確率的一般性を、その文法の生成規則に確率値を割り当てた場合に生成しうる確率言語全ての集合ととらえ、それらの間の包含関係について議論を展開している。詳しく書くと、文法クラスの統合可能性という概念を考え、RSG や SG のクラスはそれ自身の範囲内では統合不可能であることを示している。また、新たに、RSG のクラスがそのサブクラスとなる、Unifiable Simple Grammar という文法を定義し、その文法クラスがそれ自身の範囲内で統合可能なことを示すことで、RSG のクラスが SG のクラスの範囲内で統合可能なことが示される。ことことから、RSG の特性を考慮すれば、RSG のクラスが「強い意味」で SG のクラスの範囲内で統合可能であることが示せる。また、実際の統合アルゴリズムの計算量及び統合後の文法のサイズを与えている。 | |||||
書誌情報 | 発行日 2007-03-22 | |||||
日本十進分類法 | ||||||
主題Scheme | NDC | |||||
主題 | 007 | |||||
学位名 | ||||||
学位名 | 博士(工学) | |||||
学位 | ||||||
値 | doctoral | |||||
学位分野 | ||||||
Engineering (工学) | ||||||
学位授与機関 | ||||||
学位授与機関名 | University of Tokyo (東京大学) | |||||
研究科・専攻 | ||||||
Department of Electronic Engineering, Graduate School of Engineering (工学系研究科電子工学専攻) | ||||||
学位授与年月日 | ||||||
学位授与年月日 | 2007-03-22 | |||||
学位授与番号 | ||||||
学位授与番号 | 甲第22291号 | |||||
学位記番号 | ||||||
博工第6496号 |