読者です 読者をやめる 読者になる 読者になる

統語解析入門

自然言語処理

今期にあっている松本先生の計算言語学に出ている。今日からparsingの話で、最近parsingに興味があるわりに全然知識がないので出席*1。松本先生のparsingの授業を受けられる、というのもすごい話である。

来週で一通り終わったら長尾先生のテキストをの構文解析の章を見て復習するのがいいかな?

岩波講座 ソフトウェア科学〈〔知識〕15〉自然言語処理

岩波講座 ソフトウェア科学〈〔知識〕15〉自然言語処理

  • 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とも呼ばれる

*1:木を使って色々やりたいけど、木を作るやり方をCYKとかPCFGくらいしか知らなかった

*2:全然分かってなかった