形式文法の確率的一般性とその応用に関する研究

柴田, 剛志

WEKO3

AND

lat lon distance

[[sub_check.contents]]　

[[sub_radio.contents]]

Field does not validate

[[sub_attr.contents]]　

インデックスツリー

アイテム

{"_buckets": {"deposit": "900cde6e-fa6b-46bd-8848-a61c6a233982"}, "_deposit": {"id": "2389", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "2389"}, "status": "published"}, "_oai": {"id": "oai:repository.dl.itc.u-tokyo.ac.jp:00002389"}, "item_7_biblio_info_7": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2007-03-22", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}]}]}, "item_7_date_granted_25": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u5e74\u6708\u65e5", "attribute_value_mlt": [{"subitem_dategranted": "2007-03-22"}]}, "item_7_degree_grantor_23": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u6a5f\u95a2", "attribute_value_mlt": [{"subitem_degreegrantor": [{"subitem_degreegrantor_name": "University of Tokyo (\u6771\u4eac\u5927\u5b66)"}]}]}, "item_7_degree_name_20": {"attribute_name": "\u5b66\u4f4d\u540d", "attribute_value_mlt": [{"subitem_degreename": "\u535a\u58eb(\u5de5\u5b66)"}]}, "item_7_description_5": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "\u8fd1\u5e74\u3001\u6b63\u4f8b\u304b\u3089\u306e\u5b66\u7fd2\u306e\u5206\u91ce\u306b\u304a\u3044\u3066\u3001\u6587\u8108\u81ea\u7531\u6587\u6cd5\u306e\u975e\u6b63\u5247\u306a\u30b5\u30d6\u30af\u30e9\u30b9\u3067\u3001\u52b9\u7387\u7684\u306b\u5b66\u7fd2\u53ef\u80fd\u306a\u30af\u30e9\u30b9\u304c\u767a\u898b\u3055\u308c\u3066\u304d\u305f\u3002Very Simple Grammar(VSG) \u306e\u30af\u30e9\u30b9\u3084\u3001\u305d\u306e\u62e1\u5f35\u3067\u3042\u308b Right-unique Simple Grammar(RSG) \u306e\u30af\u30e9\u30b9\u304c\u305d\u3046\u3067\u3042\u308b\u3002\u4e21\u8005\u306f\u3068\u3082\u306b Simple Grammar(SG) \u3068\u3088\u3070\u308c\u308b\u6587\u6cd5\u306e\u30b5\u30d6\u30af\u30e9\u30b9\u3067\u3042\u308b\u3002\u3053\u308c\u3089\u306e\u52b9\u7387\u7684\u5b66\u7fd2\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u5bfe\u3057\u3066\u3044\u308d\u3044\u308d\u306a\u5fdc\u7528\u3092\u8003\u3048\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u305d\u306e\u3072\u3068\u3064\u3068\u3057\u3066\u3001\u672c\u8ad6\u6587\u3067\u306f\u5f37\u5316\u5b66\u7fd2\u3078\u5fdc\u7528\u3059\u308b\u65b9\u6cd5\u3092\u63d0\u6848\u3057\u3066\u3044\u308b\u3002\u5f37\u5316\u5b66\u7fd2\u306e\u7406\u8ad6\u7684\u306a\u57fa\u790e\u3068\u306a\u3063\u3066\u3044\u308b\u78ba\u7387\u30e2\u30c7\u30eb\u306f\u30de\u30eb\u30b3\u30d5\u6c7a\u5b9a\u904e\u7a0b\u3067\u3042\u308b\u304c\u3001\u6709\u9650\u72b6\u614b\u30de\u30eb\u30b3\u30d5\u6c7a\u5b9a\u904e\u7a0b\u306b\u30b9\u30bf\u30c3\u30af\u3092\u4ed8\u4e0e\u3057\u305f\u6c7a\u5b9a\u904e\u7a0b\u3092\u8003\u3048\u308b\u3068\u3001\u72b6\u614b\u3068\u30b9\u30bf\u30c3\u30af\u306e\u7d44\u306f\u3001RSG \u3068\u307f\u306a\u3059\u3053\u3068\u304c\u3067\u304d\u3001\u89b3\u6e2c\u306e\u5c65\u6b74\u306f\u3001RSG \u306e\u6b63\u4f8b\u3068\u306a\u308b\u3002\u3057\u305f\u304c\u3063\u3066\u3001RSG \u306e\u5b66\u7fd2\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u7528\u3044\u308c\u3070\u3082\u3068\u306e\u6587\u6cd5\u3001\u5373\u3061\u72b6\u614b\u3068\u30b9\u30bf\u30c3\u30af\u306e\u7d44\u3092\u63a8\u5b9a\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u3057\u304b\u3057\u3001\u3053\u306e\u5834\u5408\u3001\u8a00\u8a9e\u304c\u7b49\u3057\u3044\u3060\u3051\u3067\u306f\u6b63\u3057\u3044\u6587\u6cd5\u3092\u5b66\u7fd2\u3057\u305f\u3068\u3044\u3048\u305a\u3001\u78ba\u7387\u8a00\u8a9e\u306e\u610f\u5473\u3067\u9f5f\u9f6c\u306e\u306a\u3044\u6587\u6cd5\u3092\u51fa\u529b\u3057\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u3002\u3053\u308c\u306f\u6b21\u306e\u7d50\u679c\u3092\u7528\u3044\u308b\u3068\u89e3\u6c7a\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u672c\u8ad6\u6587\u3067\u306f\u3001SG \u306b\u5bfe\u3059\u308b\u78ba\u7387\u7684\u4e00\u822c\u6027\u3092\u3001\u305d\u306e\u6587\u6cd5\u306e\u751f\u6210\u898f\u5247\u306b\u78ba\u7387\u5024\u3092\u5272\u308a\u5f53\u3066\u305f\u5834\u5408\u306b\u751f\u6210\u3057\u3046\u308b\u78ba\u7387\u8a00\u8a9e\u5168\u3066\u306e\u96c6\u5408\u3068\u3068\u3089\u3048\u3001\u305d\u308c\u3089\u306e\u9593\u306e\u5305\u542b\u95a2\u4fc2\u306b\u3064\u3044\u3066\u8b70\u8ad6\u3092\u5c55\u958b\u3057\u3066\u3044\u308b\u3002\u8a73\u3057\u304f\u66f8\u304f\u3068\u3001\u6587\u6cd5\u30af\u30e9\u30b9\u306e\u7d71\u5408\u53ef\u80fd\u6027\u3068\u3044\u3046\u6982\u5ff5\u3092\u8003\u3048\u3001RSG \u3084 SG \u306e\u30af\u30e9\u30b9\u306f\u305d\u308c\u81ea\u8eab\u306e\u7bc4\u56f2\u5185\u3067\u306f\u7d71\u5408\u4e0d\u53ef\u80fd\u3067\u3042\u308b\u3053\u3068\u3092\u793a\u3057\u3066\u3044\u308b\u3002\u307e\u305f\u3001\u65b0\u305f\u306b\u3001RSG \u306e\u30af\u30e9\u30b9\u304c\u305d\u306e\u30b5\u30d6\u30af\u30e9\u30b9\u3068\u306a\u308b\u3001Unifiable Simple Grammar \u3068\u3044\u3046\u6587\u6cd5\u3092\u5b9a\u7fa9\u3057\u3001\u305d\u306e\u6587\u6cd5\u30af\u30e9\u30b9\u304c\u305d\u308c\u81ea\u8eab\u306e\u7bc4\u56f2\u5185\u3067\u7d71\u5408\u53ef\u80fd\u306a\u3053\u3068\u3092\u793a\u3059\u3053\u3068\u3067\u3001RSG \u306e\u30af\u30e9\u30b9\u304c SG \u306e\u30af\u30e9\u30b9\u306e\u7bc4\u56f2\u5185\u3067\u7d71\u5408\u53ef\u80fd\u306a\u3053\u3068\u304c\u793a\u3055\u308c\u308b\u3002\u3053\u3068\u3053\u3068\u304b\u3089\u3001RSG \u306e\u7279\u6027\u3092\u8003\u616e\u3059\u308c\u3070\u3001RSG \u306e\u30af\u30e9\u30b9\u304c\u300c\u5f37\u3044\u610f\u5473\u300d\u3067 SG \u306e\u30af\u30e9\u30b9\u306e\u7bc4\u56f2\u5185\u3067\u7d71\u5408\u53ef\u80fd\u3067\u3042\u308b\u3053\u3068\u304c\u793a\u305b\u308b\u3002\u307e\u305f\u3001\u5b9f\u969b\u306e\u7d71\u5408\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8a08\u7b97\u91cf\u53ca\u3073\u7d71\u5408\u5f8c\u306e\u6587\u6cd5\u306e\u30b5\u30a4\u30ba\u3092\u4e0e\u3048\u3066\u3044\u308b\u3002", "subitem_description_type": "Abstract"}]}, "item_7_dissertation_number_26": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u756a\u53f7", "attribute_value_mlt": [{"subitem_dissertationnumber": "\u7532\u7b2c22291\u53f7"}]}, "item_7_full_name_3": {"attribute_name": "\u8457\u8005\u5225\u540d", "attribute_value_mlt": [{"nameIdentifiers": [{"nameIdentifier": "6621", "nameIdentifierScheme": "WEKO"}], "names": [{"name": "\u30b7\u30d0\u30bf, \u30bf\u30b1\u30b7"}]}]}, "item_7_identifier_registration": {"attribute_name": "ID\u767b\u9332", "attribute_value_mlt": [{"subitem_identifier_reg_text": "10.15083/00002383", "subitem_identifier_reg_type": "JaLC"}]}, "item_7_select_21": {"attribute_name": "\u5b66\u4f4d", "attribute_value_mlt": [{"subitem_select_item": "doctoral"}]}, "item_7_subject_13": {"attribute_name": "\u65e5\u672c\u5341\u9032\u5206\u985e\u6cd5", "attribute_value_mlt": [{"subitem_subject": "007", "subitem_subject_scheme": "NDC"}]}, "item_7_text_22": {"attribute_name": "\u5b66\u4f4d\u5206\u91ce", "attribute_value_mlt": [{"subitem_text_value": "Engineering (\u5de5\u5b66)"}]}, "item_7_text_24": {"attribute_name": "\u7814\u7a76\u79d1\u30fb\u5c02\u653b", "attribute_value_mlt": [{"subitem_text_value": "Department of Electronic Engineering, Graduate School of Engineering (\u5de5\u5b66\u7cfb\u7814\u7a76\u79d1\u96fb\u5b50\u5de5\u5b66\u5c02\u653b)"}]}, "item_7_text_27": {"attribute_name": "\u5b66\u4f4d\u8a18\u756a\u53f7", "attribute_value_mlt": [{"subitem_text_value": "\u535a\u5de5\u7b2c6496\u53f7"}]}, "item_7_text_36": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"subitem_text_value": "Thesis"}]}, "item_7_text_4": {"attribute_name": "\u8457\u8005\u6240\u5c5e", "attribute_value_mlt": [{"subitem_text_value": "\u6771\u4eac\u5927\u5b66\u5927\u5b66\u9662\u5de5\u5b66\u7cfb\u7814\u7a76\u79d1 \u96fb\u5b50\u5de5\u5b66\u5c02\u653b"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "\u67f4\u7530, \u525b\u5fd7"}], "nameIdentifiers": [{"nameIdentifier": "6620", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-05-31"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "shibata.pdf", "filesize": [{"value": "590.8 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 590800.0, "url": {"label": "shibata.pdf", "url": "https://repository.dl.itc.u-tokyo.ac.jp/record/2389/files/shibata.pdf"}, "version_id": "66fb2c62-4413-4bd0-9ee7-50bddd21f246"}]}, "item_keyword": {"attribute_name": "\u30ad\u30fc\u30ef\u30fc\u30c9", "attribute_value_mlt": [{"subitem_subject": "\u8a08\u7b97\u6a5f\u79d1\u5b66", "subitem_subject_scheme": "Other"}, {"subitem_subject": "\u5b66\u7fd2\u7406\u8ad6", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "jpn"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "\u5f62\u5f0f\u6587\u6cd5\u306e\u78ba\u7387\u7684\u4e00\u822c\u6027\u3068\u305d\u306e\u5fdc\u7528\u306b\u95a2\u3059\u308b\u7814\u7a76", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "\u5f62\u5f0f\u6587\u6cd5\u306e\u78ba\u7387\u7684\u4e00\u822c\u6027\u3068\u305d\u306e\u5fdc\u7528\u306b\u95a2\u3059\u308b\u7814\u7a76"}]}, "item_type_id": "7", "owner": "1", "path": ["9/233/280", "6/260/318"], "permalink_uri": "https://doi.org/10.15083/00002383", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_value": "2012-03-01"}, "publish_date": "2012-03-01", "publish_status": "0", "recid": "2389", "relation": {}, "relation_version_is_last": true, "title": ["\u5f62\u5f0f\u6587\u6cd5\u306e\u78ba\u7387\u7684\u4e00\u822c\u6027\u3068\u305d\u306e\u5fdc\u7528\u306b\u95a2\u3059\u308b\u7814\u7a76"], "weko_shared_id": null}

形式文法の確率的一般性とその応用に関する研究

https://doi.org/10.15083/00002383

	名前 / ファイル	ライセンス	アクション
	shibata.pdf (590.8 kB)

Item type

学位論文 / Thesis or Dissertation(1)

公開日

2012-03-01

タイトル

形式文法の確率的一般性とその応用に関する研究

言語

jpn

キーワード

主題

計算機科学

主題Scheme

Other

キーワード

主題

学習理論

主題Scheme

Other

資源タイプ

資源

http://purl.org/coar/resource_type/c_46ec

タイプ

thesis

ID登録

10.15083/00002383

ID登録タイプ

JaLC

著者

柴田, 剛志

著者別名

識別子

6621

識別子Scheme

WEKO

姓名

シバタ, タケシ

著者所属

東京大学大学院工学系研究科電子工学専攻

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

日本十進分類法

主題

007

主題Scheme

NDC

学位名

博士(工学)

学位

値

doctoral

学位分野

Engineering (工学)

学位授与機関

学位授与機関名

University of Tokyo (東京大学)

研究科・専攻

Department of Electronic Engineering, Graduate School of Engineering (工学系研究科電子工学専攻)

学位授与年月日

2007-03-22

学位授与番号

甲第22291号

学位記番号

博工第6496号

戻る

views

See details

	Views

Versions

Ver.1

2021-03-01 19:58:16.640313

Show All versions

Cite as

Export

OAI-PMH

JPCOAR
DublinCore
DDI

Other Formats

JSON
BIBTEX

インデックスリンク

インデックスツリー

アイテム

形式文法の確率的一般性とその応用に関する研究

× 柴田, 剛志

Versions

Share

Cite as

Export