机械学习基日本语解析.ppt

機械学習に基づく日本語解析システム 奈良先端科学技術大学院大学 情報科学研究科 松本裕治 形態素解析 文を単語に区切り、品詞を同定する処理 以下の３つの処理より成る 単語への分かち書き(tokenization) 文を単語単位の文字列に分ける処理 活用語処理(stemming, lemmatization) 英語の動詞や名詞の語尾、日本語の活用語の語尾などを処理し、原型と活用形情報を得る処理 品詞同定(part-of-speech tagging) 個々の単語の品詞を推定する処理 形態素解析の問題点 それぞれの処理に曖昧性が発生する 単語への分かち書き 日本語では単語がスペースによって区切られてないため、分かち書きの曖昧性の問題が深刻 英語では、スペースによって単語がくぎられているが、例外も多い。 カンマやピリオドなどの句読点はスペースで区切られない。 ピリオドなどが常に句読点とは限らない（Mr., U.S.A., I’m など） 複数の語がひとつの語のような働きをする場合がある 　　（“New York” “with regard to”　など） 活用語処理 品詞同定 同じ形の語が複数の品詞や活用形の可能性がある場合がある 形態素解析に必要な事項 基本的な処理: 辞書から単語を引いて、与えられた文と照合し、最も自然な単語列を求める 辞書 入力文は文字列(単語毎に区切られていない) どの文字列を対象に辞書引きをするかが自明でない 解の探索 すべての可能な単語の組合せから(何らかの基準で)最適な単語列を発見する 単純に全探索を行うのは計算量が膨大 動的計画法に基づくアルゴリズムが用いられる(Viterbi algorithm) 形態素解析のための辞書の構成 文に含まれるすべての単語は、実はかなりの数 「単語毎に区切られていない」という文は正しくは、8単語からなる 　　　「単語 / 毎 / に / 区切ら / れ / て / い / ない」 現在の辞書ですべての形態素を検索すると、上の文には69語もの異なる単語が含まれる 入力文のすべての部分文字列に対して辞書引きを行うのは、あまりにも効率が悪い 辞書の構成を工夫する必要がある 部分文字列のすべてを高速に検索するためのデータ構造がいくつか提案されている TRIE構造、パトリシア木、Suffix array など 日本語処理のための辞書の要件 単語の区切りが明確でないので、先頭から何文字までが単語なのかわからない。 　　先頭から１文字、２文字と順番に辞書を引く？ 　　しかし、どこまでを辞書引きの対象にすればよいかわからない このような接頭部分が重なった文字列を効率的に検索する方法が必要　　　　　TRIE構造 辞書検索のためのデータ構造：TRIE TRIE: 文字毎にポインタを持たせた木構造 辞書検索のためのデータ構造：TRIE 日本語でも同様 TRIEの特徴 対象文字列の先頭から文字を順番にたどっていくことによって、すべての単語を検索可能 入力文字列の長さに比例した時間で探索が可能 辞書引き終了のタイミングが自動的にわかる TRIEの葉の末端に来るか、検索対象の文字に対応する枝がない場合に探索を終了すればよい TRIEの欠点 メモリ効率が悪い 各節点からアルファベットの数の枝が出るが、木の下の方では、ほとんどの節点は少数の枝しかもたない 節点のデータ構造の効率が極めて悪い 日本語の場合は、文字種（数千種類）だけの出力枝を各節点に持たせるのは現実的に不可能 TRIE構造実現のための工夫 日本語の場合： 各文字（２バイト文字）ごとに出力枝をもたせるのではなく、２バイトコードのうちの１バイトごとに節点を作る これにより、中間の節点は（１バイトコード文字であるアルファベットや数字を除いて）無駄になるが、メモリ効率は大幅によくなる（各節点からの出力枝の数は高々28 =128本） これでも、多くの節点は、それより遥かに少ない枝しかもたず、各節点が無駄なデータ領域を持つことになる 問題の解決策 ダブル配列によるデータ領域の圧縮 2分木による再構成　　　　　パトリシア木 ２分木を用いたTRIE すべての文字を2進数表示で考える 各節点は、２つの枝（０と１に対応）しか持たない 枝に関する無駄な領域は大幅に削減できるが、無駄な節点が多数できる ２分木TRIEの特徴と欠点 ２分木にすることによって節点は２出力しかもたず、コンパクトに表現できる しかし、実際の単語を登録すると、ほとんどの節点は、１本の枝しか必要としない パトリシア木 ２分木TRIEの枝分かれのないパスを縮退し、途中に節点を設けない 枝が分岐するところにだけ、節点を作る 各節点は、自分が何ビット目の節点かの情報をもつ パトリシア木の