今期にあっている松本先生の計算言語学に出ている。今日からparsingの話で、最近parsingに興味があるわりに全然知識がないので出席*1。松本先生のparsingの授業を受けられる、というのもすごい話である。
- 資料 => http://is-education.naist.jp/Data/Syllabus/2010/TeachingMaterial/info-0022_1287486864.pdf
- 授業アーカイブ => http://library.naist.jp/mylimedio/search/av2.do?target=local&bibid=128786
来週で一通り終わったら長尾先生のテキストをの構文解析の章を見て復習するのがいいかな?
- 作者: 長尾真,佐藤理史
- 出版社/メーカー: 岩波書店
- 発売日: 1996/04/26
- メディア: 大型本
- 購入: 1人 クリック: 16回
- この商品を含むブログ (18件) を見る
- top down(CFGでいうところの左から右)、bottom up(CFGでいうところの右から左)や、並行法などがある
- top downやbottom upは普通にやるとbacktrackで時間がかかるので、並行法がよく使われる
top down
- CFGの左にマッチするやつをただひたすら展開していく
- スタックをうまく使う(右のやつを詰む)
- スタックに残っているところまでbacktrack(どこまで戻るかが分かる)
bottom up(Shift Reduce法)
- stackに積んでいく操作をshiftという
- ReduceでCFGの左に書き変えていく
- sentenceができあがるまで上がっていく(backtrackが必要な場合もある)
- Reduceを先にやるのが普通であるが、そうでないケースもある
- Shift Reduce法はルールの適用を何も考えずにやっていくとすごい時間がかかってしまうけど、どれから適用するのがいいかを機械学習のフレームワークを使って学習するというのがよくある話のようだ
- 形態素解析の論文とかでShift Reduce法を使ってやっている話を読んだことがあったけど、そういう話だったのか*2
並行法(CYK法)
- チョムスキー標準形を仮定
- backtrackで壊して、また作るのはもったいない
- 一回作ったやつは記憶しておこう
- 右上に上がっていくのをDPで効率的に管理しよう
- CYKアルゴリズム - Seeking for my unique color.
- CYKを一般的に拡張したものをChart Parsingという
- 右辺が3つ以上あるケース
- top down chart法というものもあり、アーリーparsingとも呼ばれる
