Web 文書と検索ログを用いた
オープンドメインのクラスとクラス
属性の弱教師あり学習
ACL 2008 読み会
2008年6月27日
奈良先端大 松本研 小町守
紹介する論文
• Marius Pasca and Benjamin Van Durme
• Weakly-Supervised Acquisition of OpenDomain Classes and Class Attributes from Web
Documents and Query Logs
• In Proc of ACL 2008
• pages 19-27
08.6.27
2
背景
• 情報抽出で非構造化データの利用が盛ん
– Web 文書(Banko et al., 2007; Snow et al. 2006)
– Web 検索クエリのログ(Pasca, 2007)
• 非構造化データからの弱教師あり学習
08.6.27
3
弱教師あり学習
• Pasca et al., 2006
– シード:対象の属性(例:人々の誕生年=(John
Lennon, 1941))
– コーパス: Web 文書
• Pasca, 2007
– シード: ターゲットクラス(例: Drug)とインスタンス
(例:Vicodin と Xanax)
– コーパス: 検索ログ
• 入力クラスは人手で指定する必要がある
08.6.27
4
目的
• オープンドメインのインスタンス集合を抽出
– 対象: Web 文書 and 検索ログ
– 入力: クラスを事前に指定する必要がない
– 出力:
• インスタンス集合(例:{whales, seals, dolphins, …})
• クラスのラベル(例:marine animals)
• クラスの属性(例: life cycle, food chain, …)
08.6.27
5
本研究の特長
1. クラスの (インスタンス集合, ラベル, 属性) を
同時に獲得できる
2. 非常に少ない4,583個のオープンドメインの
クラスを抽出し、精度は80%以上
3. 自動獲得したオープンドメインのクラス属性
抽出の初めての評価
4. Web 文書と検索ログを両方使って情報抽出
する初の試み
08.6.27
6
概要
Web 文書と検索ログから抽出した知識
Web
文書
オーブンドメインのラベル付きクラスとインスタンス集合
Marine animals = {whales, seals, dolphins, …}
Amino acids = {phenylalanine, 1-cysteine, …}
検索
ログ
オーブンドメインのクラス属性
Marine animals = [life cycle, evolution, food chain, …]
Amino acids = [molecular formula, isoelectric point, …]
08.6.27
7
クラスラベルとインスタンスの抽出
• 入力
– ISA抽出パターン(クラス {such as|including} インス
タンス {and|,|.})
– 検索クエリ
– Web文書
– Precision と recall を調節するパラメータ
• 出力
– クラスラベルとインスタンスのペア(zoonotic
diseases, west nile virus)
08.6.27
8
アルゴリズム
1. Web文書でISAパターンにマッチするペア(クラス
ラベル,インスタンス)を抽出
2. Web文書中のdistributional similarityに基づい
て検索ログをクラスタリング
3. 各クラスタごとに
1. 各検索クエリのラベルをラベル候補集合に追加
2. ラベル候補集合の各ラベルについて
1.
検索ログ中に出てくるクエリで条件に合うものをインスタ
ンスとして出力に(ラベル,インスタンス)のペアを追加
4. ペアのリストを出力
08.6.27
9
ヒューリスティック
• パターンマッチする文の条件
– クラスのラベルは “non-recursive noun phrase
whose last component is a plural-form” (e.g.,
zoonotic diseases)
– インスタンスは検索ログ中にそのままの形で現れ
ているもののみを使う(Downey et al., 2007)
08.6.27
10
クラス属性の獲得(1)
• 検索ログ中でインスタンスを含む検索クエリ
のうち、インスタンスを除いた単語列を属性候
補に追加
– インスタンス: “jay and silent bob strike back”
– 検索クエリ: “cast jay and silent bob strike back”
– →属性候補: “cast”
08.6.27
11
クラス属性の獲得(2,3)
• Internal search-signature vector を作る
–
–
–
–
検索クエリ: “cast selection for kill bill”
属性候補: “cast”
インスタンス: “kill bill”
→Search-signature vector: “selection for” から作る(具
体的には書いていない)
• “X for Y” といった一般的なパターンの特殊化に用いる
• Reference internal search signature vector 作成
– 入力:シードとなる属性
– 出力:シード属性に対応するベクトルの和(正規化)
08.6.27
12
クラス属性の獲得(4)
• 各クラスに対応する属性候補のランクづけ
– シード属性に対応する reference vector との間の
類似度スコアの計算による
– →各クラスについて属性候補のランキングが得ら
れる
• (movies に対して [opening song, cast, characters, …])
08.6.27
13
本研究のクラス属性獲得の特長
• 各クラスに対するインスタンスは自動獲得さ
れたものを用いる
– 先行研究ではシードインスタンスは人手で与える
• シード属性は一つのクラスに対する属性のみ
でよい
– (pasca, 2007) では各クラスについてシード属性
– 一つのクラスに対するシード属性の reference
vector との間の類似度のみの計算に相当
08.6.27
14
実験
• Google 検索エンジン
– 検索ログ: 英語のログのランダムサンプル、5,000
万 unique queries (頻度つき)
– Web 文書: 英語1億 Web 文書
• HTML 除去、単語分割、文分割、品詞付与(TnT tagger)
済み
08.6.27
15
クラスのラベルの評価
• パラメータの決定
– ヒューリスティックに決めた
• クラスのラベルの精度
– WordNet との比較(Table 1)
• 42.2%は WordNet にそのままある
• 57.0%は少し加工すると WordNet にある
– うちランダムサンプリングで評価してみると、77%は正しい、
13.5%は場合によって正しい、9.5%は間違いラベルだった
– WordNet に入っていないが意味のあるクラスラベルの抽出
に成功→WordNet の拡張などにも使えるかもしれない
08.6.27
16
インスタンスの精度
• 獲得された各クラスラベルのインスタンスに
ついてそれぞれ人手で評価
– 先行研究(Pasca, 2007)で人手作成した集合を正
解データとして用いる
– Precision: クラスラベル(90%)インスタンス(80%)
– Recall: インスタンス(26.89%)
• 大量に精度高くインスタンスを獲得することができた
• (recall低いのは大量にprecision低く獲得したためでは
ない)
08.6.27
17
クラス属性の評価
• ランクによるバイアスを避けるためアルファ
ベット順にソートして評価
• 結果をランク順に並べたときの精度
– Figure 3 と Table 5
• 上2つのグラフは各クラスに5個ずつシード(5x37=185)
• 下2つのグラフは1つのクラスのみに5個のシード
– シードが多い方が(当然ながら)よい結果(だが1つのクラスの
みでもそれなりの精度)
• シードを自動抽出した線と人手で与えた線をプロット
– 人手で与えた方が(当然ながら)よい結果
08.6.27
18
インスタンス獲得の関連研究
• クラスインスタンスの獲得
– 非構造化データからインスタンス集合を獲得
• Wikipedia から (Ponzetto and Strube, 2007)
• WordNet から (Snow et al., 2006)
• 両方 (Suchanek et al., 2007)
• 手法
– シードパターンから (Collins and Singer, 1999)
– 新聞記事から抽出したNE使って (Shinyama and
Sekine, 2004)
– 多言語コーパスから (Klementiev and Roth, 2006)
08.6.27
19
弱教師あり学習の関連研究
• 弱教師あり学習
– ブートストラッピング (Riloff and Jones, 1999)
– 固有表現認識(NER)を使うとブートストラップの性
能が向上 (Feldman and Rosenfeld, 2006)
• ただし評価は coarse-grained なデータのみ
• 簡単な実験設定
– Person (Feldman and Rosenfeld, 2006)
– Company and Country (Cafarella et al., 2005)
08.6.27
20
クラスラベル付与の関連研究
• 非構造化データ (Pantel and Ravichandran,
2004)
– クラスラベルの自動獲得
– 評価が甘い(n-best の結果で評価している)
• 非構造化Web文書 (Davidov et al., 2007)
– インスタンスの自動獲得
– 検索エンジンの結果上位1,000件の文書を使用
– 事前にクラスを指定する必要あり
08.6.27
21
まとめ
1. クラスの (インスタンス集合, ラベル, 属性) を
同時に獲得する手法の提案
2. 非常に少ない4,583個のオープンドメインの
クラスを抽出し、精度は80%以上
3. 自動獲得したオープンドメインのクラス属性
抽出の初めての評価
4. Web 文書と検索ログを両方使って情報抽出
する初の試み
08.6.27
22
ダウンロード

cl-20080627