検索ログを用いた意味知識獲得のための ブートストラップ手法 小町守(†)・鈴木久美(‡) (†) 奈良先端科学技術大学院大学情報科学研究科 (‡) Microsoft Research 電子情報通信学会 言語理解とコミュニケーション研究会 9/18/2018

研究背景 キーワード検索は情報にアクセスする必須の手段 アプリケーションには用語の意味カテゴリが重要 ユーザの興味を直接知ることが可能 ポケモンの攻略法 が知りたい ポケモン　攻略法 検索 キーワード検索は情報にアクセスする必須の手段 ユーザの興味を直接知ることが可能 アプリケーションには用語の意味カテゴリが重要 9/18/2018

アプローチ 半教師あり学習によって検索ログから意味カテゴリを ブートストラップ 意味カテゴリ 検索ログ ブートストラップ ユーザがよく聞く対象 (cf. Pasca and Durme 2007) 検索ログ Webデータそのものよりユーザの関心を反映 短いが用語のカテゴライズには有効 ユーザが(非明示的に)単語分割を指定 ブートストラップ 2項関係抽出のさまざまなタスクで適用 (Brin 1998; Collins and Singer 1999; Etzioni et al. 2005) 少量のインスタンスから学習することができる (cf. Sekine and Suzuki 2007) 9/18/2018

本研究による貢献 意味カテゴリの学習タスクにおいて日本語の検索ログを 初めて用いた 汎用的な Espresso (Pantel and Pennacchiotti 2006) アル ゴリズムに基づいて検索ログに適した効率的な手法を提 案した 単語分割の知識が不要 9/18/2018

目次 概要 関連研究 Tchai アルゴリズム 実験 まとめ 9/18/2018

ブートストラップ手法 シードインスタンスから始めて反復的にパターン導出とイ ンスタンス抽出を繰り返す ある関係にある少量のシードを増やすことができる 用語リスト コーパス (検索ログ) 文脈パターン ポケモン ポケモン+攻略法 #+攻略法 ドラクエ ドラクエ+攻略法 #:スロット +:空白文字 ff ff+攻略法 2018/9/18

インスタンス以外の文字列を文脈パターンとして使用=単語分割が不要 インスタンスの検索と文脈パターン抽出 ana ana+予約 #+予約 インスタンス 実際の検索ログ 抽出パターン 頻度 パターン インスタンス 644 #+予約 ana 140 #格安航空券 ラスベガス 114 #ホテル … インスタンス以外の文字列を文脈パターンとして使用=単語分割が不要 文脈パターンをスコアリングして上位のものを選択 先行研究ではジェネリックパターンの扱いが異なる 高適合率・低再現率 9/18/2018

インスタンス・パターンの尺度 Sekine & Suzuki (2007) Basilisk (Thelen and Riloff, 2002) ジェネリックパターンには低いスコアを割り当て、処理をスキップ ジェネリックパターンの再現率と適合率のちょうどいいところを求めるヒューリスティクス 9/18/2018

インスタンスとパターンの信頼度は相互に再帰的に定義 Espresso アルゴリズム Espresso (Pantel and Pennacchiotti, 2006) 少量のシードインスタンスからスタート 以下のステップを反復 パターン導出 パターンのランキングと選択 インスタンス抽出 インスタンスとパターンの信頼度は相互に再帰的に定義 9/18/2018

Espresso アルゴリズムの問題点 ジェネリックパターン・インスタンスの取り扱い 計算の効率 Espresso で提案されている確信度(confidence)の尺度は検索 ログデータではうまく行かなかった ジェネリックパターンは多数のインスタンスと共起するので計 算量が大きい 計算の効率 Espresso では全てのパターンの信頼度を毎回計算する 9/18/2018

Tchai アルゴリズム ジェネリックパターンやインスタンスのフィルター 信頼度の係数を修正 性能の改善 ジェネリックパターン・インスタンスは単に用いない 反復初期の適合率の向上に貢献 信頼度の係数を修正 全てのインスタンスとパターンの間の最大 PMI を使うのでは なく、あるインスタンスに対する全てのパターン・あるパターン に対する全てのパターンの間の最大 PMI を使う この修正がもっとも性能の改善に効果があった 性能の改善 最初のステップのときだけパターン導出を行う Tchai は Espresso と比較して400倍高速に動作するように 9/18/2018

手法の比較 シード数 ターゲット 反復回数 コーパス 言語 Sekine & Suzuki ~600 カテゴリつき NE 1 検索ログ 英語 Basilisk 10 意味的語彙 ∞ MUC-4 Espresso ~10 意味的関係 TREC Tchai 5 カテゴリつき用語 日本語 9/18/2018

目次 概要 関連研究 Tchai アルゴリズム 実験 まとめ 9/18/2018

実験 日本語の検索ログ 2007/01-02 ターゲットとするカテゴリ ユニーク 1M (異なりで 166M) 検索ログで頻度トップ10,000クエリを人手で23カテゴリに分類 したリストを使用 (2006/12のログから作成) 旅行: 一番大きいカテゴリ (712 用語) 金融: 一番小さいカテゴリ (240 用語) カテゴリ シード 旅行 jal, ana, jr, じゃらん, his 金融 みずほ銀行, 三井住友銀行, jcb, 新生銀行, 野村證券 9/18/2018

実験結果 高適合率 (92.1%) 旅行 251の新しい用語を獲得 10K リスト 10K リストに存在せず 旅行 Not 旅行 280 17 251 7 125 金融 人手の分類の曖昧性 旅行に関係する一般用語も含む 10K リスト 10K リストに存在せず 金融 Not金融 41 30 Not 金融 5 99 9/18/2018

シードが与えられていないサブカテゴリも学習 抽出できたインスタンスの例 サブカテゴリ 例 場所 トルコ, ラスベガス, バリ島 旅行代理店 Jtb, トクー (www.tocoo.jp), yahoo (Yahoo ! Travel), net cruiser アトラクション ディズニーランド, usj ホテル 帝国ホテル, リッツ 交通手段 京浜急行, 奈良交通 シードが与えられていないサブカテゴリも学習 9/18/2018

フィルタリングしたものはコンスタントにフィルタリングなしを上回った 各変更の影響 フィルタリングしたものはコンスタントにフィルタリングなしを上回った 係数に対する変更がもっとも適合率に影響 9/18/2018

累積適合率: 旅行ドメイン Tchai が適合率最高 9/18/2018

Basilisk もEspresso も反復初期にジェネリックパターンの影響で低適合率 累積適合率: 金融カテゴリ Basilisk もEspresso も反復初期にジェネリックパターンの影響で低適合率 9/18/2018

抽出パターンの例 Basilisk と Espresso は両方とも地名を文脈パターンとして獲得しているが、旅行ドメインにはあまり特徴的ではない システム パターンの例 Basilisk #東日本, #西日本, p#sonic, #時刻表, #九州, #+マイレージ, #バス, google+#lytics, #+料金, #+国内, #ホテル Espresso #バス, 日本#, #ホテル, #道路, #イン, フジ#, #東京, #料金, #九州, #時刻表, #+旅行, #+名古屋 Tchai #+ホテル, #+ツアー, #+旅行, #予約, #+航空券, #+格安航空券, #マイレージ, 羽田空港+# Tchai は旅行ドメインに特徴的な文脈パターンを発見することができた 9/18/2018

まとめ 意味カテゴリの学習タスクにおいて日本語の検索ログを 初めて用いた 汎用的な Espresso (Pantel and Pennacchiotti 2006) アル ゴリズムに基づいて検索ログに適した効率的な手法を提 案した 単語分割の知識が不要 9/18/2018

クラスタリングと組み合わせる カテゴリ中のサブタイプを分類 今後の方向 自動クラスタリングの結果を用いて各クラス タに属する用語をさらに増やす カテゴリ中のサブタイプを分類 階層的にブートストラップ可能 2018/9/18

Tchai IJCNLP 2008: Hyderabad, India 本研究を可能にしてくれたマイクロソフト・リサーチのインターンシップ、NLPグループのみなさん、Dmitriy Belenko, Christian Koenig 両氏に感謝いたします。 ご静聴ありがとうございました 9/18/2018

パターン導出を省いても性能低下は見られず パターン導出を省いた影響 パターン導出を省いても性能低下は見られず 9/18/2018

強いフィルタリングのために適合率は高いが再現率は低い システムの相対再現率 旅行 金融 システム インスタンス 適合率 相対再現率 Basilisk 651 63.4% 1.26 Espresso 500 65.6% 1.00 Tchai 680 80.6% 1.67 システム インスタンス 適合率 相対再現率 Basilisk 278 27.3% 0.70 Espresso 704 15.2% 1.00 Tchai 223 35.0% 0.73 高適合率・高再現率 強いフィルタリングのために適合率は高いが再現率は低い 相対再現率 (Pantel et al., 2004) 9/18/2018