授業の概要 自然言語処理システム特論 Natural Language Processing Systems 第２回 2016/4/20 芝浦工業大学 工学部 情報工学科 杉本 徹 [email protected] • 自然言語処理システムの基礎となる概念を解説 した上で，システム作成実験や論文輪講を通じて その実現手法と応用事例について学んでいく • 授業形式： 講義 ＋ 実験課題 ＋ 輪講 • 想定する予備知識： – 「データ構造とアルゴリズム」，「自然言語処理」を履修 済み，または同等の知識を持っていることが望ましい – プログラミングの基本的なスキルが必要（C, Java等） 授業ホームページ • 杉本の研究室ホームページから辿れる 今日の内容 形態素解析 • はじめに：テキストの構造 • 講義資料（PDF） • スケジュール • 課題（今後） • 形態素解析とは？ • 形態素解析アルゴリズム • 形態素解析ツールの紹介 実験課題の参加希望アンケート テキストの構造 例（2008/4/21 産経新聞）： はじめに： テキストの構造 段落 東京ディズニーランド（ＴＤＬ）を運営するオリエンタルランド （千葉県浦安市）は２１日、賞味期限切れの商品「明治ベ ビーフード赤ちゃん村麦茶」４個をＴＤＬ内で販売したと発表 した。 従業員のチェックミスが原因。 来園者から健康被害 の訴えや苦情はないが、対象商品を回収する。 同社によると、問題の商品は３月２７日から今月１９日の 間、ベビーセンターの入り口カウンターで販売。 賞味期限 （今年３月２１日）は紙箱の底面に記されている。 同社は 「（製造者の）明治乳業に責任はなく、当社の管理ミス。 チェック頻度を高めるなど再発防止に努めたい」としている。 1 テキストの構造（続き） 文章，文の階層構造 文章（text） • 文間の構造（文章構造，修辞構造，談話構造） ～ 発表した。 ～ が原因。 ～ 回収する。 ～ 販売。 ～ ている。 段落（paragraph） ～ ている。 文章構造 文（sentence），節（clause） 文節（），句（phrase） • 文内の構造（構文構造） 単語（word），形態素（morpheme） 健康被害の訴えや苦情はないが、対象商品を回収する。 節 構文構造 文字（character），音素（phoneme） 文節 • 句（phrase） • 文（sentence） – 完結した表現内容を表す最小の単位 – 通常，「。」，「？」 などで終わる • 節（clause） – 文の一部分で，主語・述語を持つもの – １つの文の中に複数の節が含まれることがある – 例： 「雨が降ってきたので，太郎は傘をさした。」 副詞節 – 例： 「花子は，昨日借りた本を読んだ。」 – 一つの意味を表す単語のまとまり 例： 名詞句 「古い本」 “an old book” 「昨日買った本」 “the book that I bought yesterday” 例： 前置詞句 “in the morning”, “at the moment” 例： 後置詞句 「私が」 「古い本を」 • 文節 – 自立語（名詞や動詞）＋付属語（助詞や助動詞） – 日本語に特有（橋本文法，学校文法） 連体節 品詞分類表 • 品詞（part of speech） • 単語（word） • 形態素（morpheme） – 単語を文法的機能や形態によって分類したもの 動詞 活用あり 述語になる（用言） 形容詞 形容動詞 – 大体同じ（意味をもつ，最小の言語単位） – 例外： 接尾辞 “-ing” “-est” 「屋」 「さん」 形態素だが，単語ではない 自立語 単語 主語になる（体言） 名詞 連用修飾語になる 副詞 活用なし 連体修飾語になる 付属語 連体詞 接続語になる 接続詞 独立語になる 感動詞 活用あり 助動詞 活用なし 助詞 2 自然言語の解析処理の流れ 形態素解析とは？ 入力文 「太郎は本を読んだ。」 ① 形態素解析 太郎 は 本 を 読ん だ 名 助 名 助 動 助動 ② 構文解析 太郎 は 本 を 読ん だ ③ 意味解析 agent read taro ④ 文脈解析 参考： コンパイラの解析処理 object book 複数の文に またがる処理 解析の各段階における処理内容 （形態素解析 ⇒ 構文解析 ⇒ 意味解析 ⇒ 文脈解析） 原始プログラム sum := sum + 10 ① 字句解析 sum := sum + 10 id １．入力文が正しいかどうか判定する （言語知識の一種である制約を用いる．例：文法） asn id pls num ２．正しい場合，可能な解析結果を数え上げる statement ② 構文解析 expression （複数解が存在 ⇒ 曖昧性） sum := sum + 10 ③ 意味解析 ３．その中から妥当な結果を選択する id asn id pls num （言語知識の一種である選好を用いる．例：出現確率） 形態素解析 （Morphological Analysis） 注： 厳密には 「形態素」≠「単語」 だが，慣例にならい， 以後「形態素」という言葉の代わりに「単語」と言う 入力文 形態素解析 「太郎は走った。」 形態素解析アルゴリズム (1) 単語列への分割 (2) 単語への品詞付与 (3) 単語の原形復元 単語辞書 表層形 太郎 は 走っ 単語情報の列 た 品詞 名詞 助詞 動詞 助動 原形 太郎 は 走る た 参考： 英文解析の場合は，上記 (2) と (3) の処理が重要 3 問題の定式化 解析グラフ（Lattice） • まず，単語辞書を参照して，与えられた入力文を 単語の列へ分割するあらゆる可能性を示すグラフ 構造（lattice と呼ばれる）を作成する 日本 文頭 日 本 本 日本 を 名詞 名詞 接尾辞 名詞 助詞 本 を 出 発 する 文末 日 • 例： 「日本を出発する」 – 単語辞書 出発 本 出（る） 発 出発 発する する 動詞 接尾辞 名詞 動詞 動詞 形態素解析における経験則（Heuristics） 発する • 形態素解析とは，解析グラフにおいて，文頭から 文末 までたどる複数の経路の中から最適な経 路を選ぶ処理 コスト最小化法 • 各単語および単語どうしの接続にコストを課す． 合計コストが最小の単語分割を求めるのが目標 • 最長一致法 – 文の先頭から解析を始めて，もし可能な単語が 複数あるならば最長のものを選ぶ • 分割数最小法 – 文全体の単語数が最小となる分割を選ぶ • 品詞接続表 – 品詞の連鎖可能性を表形式で表しておき，単語 分割の際の制約条件として参照する 例： 「名詞＋助詞」はＯＫ．「名詞＋動詞」はＮＧ Markov モデル • 単語列の生起確率 n P(w1 w2 … wn) ＝ Π P(wi｜w1 … wi-1) i=1 を bigram で近似する n P(w1 w2 … wn) ＝ Π P(wi｜wi-1) 文 S = w1 w2 … wn （wi: 単語） cost(w1 w2 … wn) = cost(w1) + cost(w2) + … + cost(wn) + cost(w1,w2) + cost(w2,w3) + … + cost(wn-1,wn) • 単語コスト cost(w)，接続コスト cost(w, w’) の設定 – 直観に基づき手作業で設定するのは困難 ⇒ 統計的モデルを利用する 隠れ Markov モデル（HMM） • 品詞 ti を（観測不可能な）内部状態，単語 wi をそれ らの状態から生成されるシンボルと考えると， n P(w1 w2 … wn) ＝ Π P(ti｜ti-1) P(wi｜ti) i=1 i=1 • 単語 bigram 確率の最尤推定 P(wi｜wi-1) ＝ C(wi-1, wi) ／ C(wi-1) C(w) : コーパス中の出現頻度 • 接続コストの設定例 cost(w, w’) = －log P(w’｜w) • 品詞 bigram 確率の最尤推定 （→ 接続コスト） P(ti｜ti-1) ＝ C(ti-1, ti) ／ C(ti-1) • 品詞ごとの単語出現確率の最尤推定（→単語コスト） P(wi｜ti) ＝ C(wi, ti) ／ C(ti) 4 コスト最小解の探索 組合せ最適化問題と動的計画法 • 組合せ最適化問題 • 動的計画法（部分最適解の記録を伴う探索） • アルゴリズム 1. 部分最適解を記録する表を初期化（空）する 2. 文頭から始めて，注目する文字位置 i を１つずつ 右へ移動しながら以下の処理を行う • 文字位置 i で終わる単語 w を含むエントリを表から探 し，そのような単語 w ごとに以下の処理を行う 1) w で終わるエントリが表に複数登録されている場合は，その 中でコスト最小のもの以外を削除する 2) 文字位置 i の次から始まる単語 w’ ごとに w と w’ を接続した 場合のコストを計算し，結果を表に追加する 解析例 日本 文頭 単語 単語 コスト 出（る） 動詞 名詞 接尾 8 日本 名詞 7 本 を 出 発 本 8 10 本 する 文末 発 接尾 7 10 出発 名詞 12 発する 動詞 14 • 部分最適解表 単語列 日本 日 3 日＋本 9 22 左＼右 名詞 接尾 助詞 動詞 文末 1 10 10 5 － 3 5 10 名詞 3 1 3 5 10 接尾 5 1 4 日＋本 20 文頭 5 日本＋を 12 6 日＋本＋を 26 7 日＋本＋を 24 助詞 1 10 5 3 8 ・・ ・・・ 動詞 3 8 3 3 3 する 3 動詞 3 • 接続コスト 形態素解析ツールの紹介 コスト計 2 助詞 • 例： ダイクストラ法（最短経路探索） 発する 1 を 1. 問題から小さい部分問題を抽出し，それに対する最適解 を求めて記録する 2. その部分問題を少し拡張して得られる部分問題を生成し， それに対する最適解を，前段で求めた最適解を用いて求 める 3. これを繰り返し，最終的に元の問題の最適解を求める 出発 本 コスト 名詞 • 動的計画法 日 • 単語コスト 日 – 有限個の要素の組合せで定義される最適化問題 （最適レイアウト，最適スケジューリング，最適経路など） 8 MeCab の使い方 形態素解析ツールの例 • MeCab （工藤拓，2006～） – 条件付き確率場（CRF）を用いたコスト推定 – ChaSen より高速に動作 • ChaSen （奈良先端大，1997～） – HMM を用いた単語コスト・接続コストの自動推定 • JUMAN（京都大，1993～） – 単語コスト・接続コストは人手で設定 – MeCab, ChaSen と異なり，益岡・田窪文法に基づく辞書を使用 – 代表表記や意味情報など，出力される単語情報が充実 • Yahoo! 日本語形態素解析API – Web 上で形態素解析を実行できる Web サービス • MeCab を起動し，解析したい文を標準入力から入力する 入力文 品詞（4階層） ラーメンを食べた。 ラーメン 名詞,一般,*,*,*,*,ラーメン,ラーメン,ラーメン を 助詞,格助詞,一般,*,*,*,を,ヲ,ヲ 食べ 動詞,自立,*,*,一段,連用形,食べる,タベ,タベ た 助動詞,*,*,*,特殊・タ,基本形,た,タ,タ 。 記号,句点,*,*,*,*,。,。,。 EOS % mecab • または，解析したい文章を１文ずつ行に区切ってテキストファイ ルに保存し，そのファイル名を引数として MeCab を実行する • コマンドオプションなどの詳細は，MeCab ホームページまたは ヘルプを参照 5 実験課題について • 2～3人でチームを作って，自然言語データを自作プ ログラムで分析する実験に取り組む 実験課題の 参加希望アンケート – チームは各自の興味を基に杉本がランダムに決定 – 各チームはメンバー間で分担して与えられた課題の実験に 取り組む（全員がプログラミングを行う） – 課題は後述の４つの課題の中からチームごとに１つを杉本 が指定（アンケート結果を考慮） – プログラム作成だけでなく，完成したプログラムを用いて 自然言語データを分析し，その結果の評価・考察も行う 課題１．かな漢字変換 続き • 入力：ひらがな列 → 出力：かな漢字列 • 日程（予定） 「きょうはあめ」 → 「今日は雨」？「京は飴」？ • コスト最小化法を用いて，複数の変換候補の中から 最適と思われる（コスト最小の）解を選ぶ – 第2回 参加アンケート – 第3回 グループ分け発表 – 第4回 実験の構想発表（プレゼン） • 目標，アプローチ，使用予定データ，評価方法，分担 – 第8～10回 実験の結果報告（プレゼン） • 目標，アルゴリズム説明，使用したデータ，実験結果， 考察，分担 – 各コストの値は直感で決めるのではなく，コーパスから導 出するのが望ましい – 品詞接続コスト，単語コストのどちらか一方でもよい．これ に加えて読みコスト（例： P(きょう | 今日)）を考えてもよい • 単語辞書は十分な量のエントリをもつものを用意す ること（最低100語） – MeCab付属のIPADICを使ってもよい • 形態素解析ツールなど既存の言語処理ツールは利用不可 解析グラフ（lattice）の例 課題２．単語N-gramデータの作成と利用 • 入力文字列： 「だいがくにいく」 台 が 国 名詞 助詞 名詞 • 単語N-gramデータの作成 – 十分な大きさのコーパスから，単語1-gram（各単 語の出現回数）と単語2-gram（隣接して出現する 2単語の組み合わせの出現回数）を求める 胃 文頭 だ 行く 名詞 助動詞 医学 名詞 大学 名詞 に 動詞 文末 助詞 各頂点 → 単語コスト（，読みコスト） 各辺 → （品詞）接続コスト • 作成した単語N-gramデータの利用 例1： Markov連鎖による文生成 • 単語N-gram確率にしたがって次々に単語を選択して いくことにより文を自動生成する 例2： 語順の復元 • 文を構成する単語の順番をランダムに並び替えた後 N-gram確率が最大になるような語順を求める 6 課題３．単語の類似度計算 • 方法２．単語の分布類似度の計算 • 方法１．シソーラスに基づく類似度計算 – ２つの単語（名詞に限定してよい）を入力すると， Wu & Palmer の類似度 [Wu & Palmer 94] を計算 して出力する • 基本的アイデアは，シソーラス上で 具体物 近くにある単語ほど類似度が大きく なるようにする 動物 器具 – 利用するシソーラスの候補 • （日本語）WordNet – Javaのインタフェースあり 哺乳類 ワープロ 犬 猫 課題４．文章のカテゴリ分類（文書分類） • 対象とする文書の例 – ニュース記事，ブログ記事，ツイートなど • 分類先のカテゴリの例 – 政治，経済，スポーツ，科学などの分野 – 肯定的意見，否定的意見（このように２値分類も可） 今日のまとめ 形態素解析 – 単語が使用される文脈の類似度を基に，単語の 類似度を定義する方法 – 入力された２単語 A, B に対して，コーパスで A と共起する単語の集合SA ，Bと共起する単語の 集合SBをそれぞれ求め，SAとSBの重なり具合を 測ることによりA, Bの類似度とする – 入力単語を名詞に限定し，共起単語は動詞や形 容詞を考えるとよい（可能ならば格助詞も考慮）． 入力単語を形容詞，共起単語として名詞を考え ることも可能． 文書分類の手法 • 方法１．分類器の作成 – Naïve Bayes，Support Vector Machine など – 学習用の素性： 文章中の単語（名詞など） • 方法２．文書間類似度の利用 – 文書間類似度： 出現単語の重なり具合に基づく – 各カテゴリを代表する文書と分類対象文書の類 似度を求め，類似度が最大となるカテゴリへ分類 次回（4/27）の予定 • 意味解析の基礎（講義） • はじめに：テキストの構造 • 形態素解析とは？ • 形態素解析アルゴリズム • チーム分け，課題割り当ての発表 • 課題の補足 • 形態素解析ツールの紹介 実験課題の参加希望アンケート 7
© Copyright 2024 ExpyDoc
