関連性抽出

関連性抽出サーベイ
2009/10/22
高松慎吾
コンテンツ
関連性抽出とは
関連性抽出のアルゴリズム
関連抽出の論文紹介
その他のトピック
関連性抽出とは

「文書から知識を取り出す」タスクの中で、一番シンプルな
タスクのひとつ

関連性抽出


文書から、Entity（名詞節、固有名詞など）間の関連を抽出する。
[Entity] [Relation] [Entity]
抽出された関連を意味的に解釈する（分類 or クラスタリング）
Paul was born in Tokyo.
(Paul, Tokyo): 出生地
関連性抽出の例
[Banko 07 IJCAI]
• 2つの名詞節間の関連を抽出
http://www.cs.washington.edu/re
search/textrunner/
[Yan 09 ACL] 関連のクラスタリング
関連性抽出の利用例
 自動的にwikipediaのinfobox
のようなものを作成することに
より、コンテンツページを充実
させる
 コンテンツのメタデータの拡張
(関連コンテンツ）
 Q&A
 プロテインの関連の抽出
などなど。
Webの文書を対象とすれば、大量の新鮮な情報を取得できる
コンテンツ
関連性抽出とは
関連性抽出のアルゴリズム
関連抽出の論文紹介
その他のトピック
関連性抽出のアルゴリズム

次の２つの処理が含まれる
1. 関連が記述された部分を抽出する。
2. 抽出された関連を意味的に解釈する

関連抽出のアルゴリズム

関連にラベルが付いている場合
1. 関連候補の特定
2. 関連候補のラベル（求める関連かどうか）を判別・分類
（CRFで特定とラベリングを同時に行う場合もあり）

関連にラベルが付いていない場合
1-1. 関連候補の特定
1-2. 関連候補が関連かどうかの判定
2. 関連をクラスタリング
（これらの手順が同時に行われる場合もあり）
１．関連が記述された部分を抽出する。
・・・・・・
Paul was born in Tokyo.
・・・・・・・・・・・・・・
 Entityの特定

POSTag、固有名詞抽出、照応解析
 関連候補の特定（関連がありそうなEntityペアの特定）

同一文内に出現するEntityペア


「Entity間の単語数が閾値以下」などのルール
関連候補が関連かどうか


E0
（関連， not関連）の2値分類
構文解析を利用したルール（Entityペア間の依存パス有無）
C:i:V
sign
V:obj:N
V:subj:N

Britney
Spears
N:mod:Prep
contract
a
with
recording
Prep:pcomp-n:N
Jive
Records
関連候補をクラスタリングして、小さいクラスタは候補から除去
２．抽出された関連を意味的に解釈する
Paul was born in Tokyo.
ラベルが付いている場合
(Paul, Tokyo): 出生地
ルールベース・ブートストラップ
関連候補の分類
系列ラベリング（CRF）で抽出と同時にラベル
ラベルが付いていない場合
ルールベース
クラスタリング
要素数の少ないクラスを刈り取る
最近のトレンド
Web上の膨大な文書を対象にする
解析対象が膨大にあるのでprecision重視でよい
計算時間をできるだけ減らしたい
MLNもありました
読んでいませんが
コンテンツ
関連性抽出とは
関連性抽出のアルゴリズム
関連抽出の論文紹介
その他のトピック
関連性抽出のはしり [Hasegawa, ACL04]
＜関連性抽出＞
・関連候補：同一文
内で単語距離５以下
の固有名詞のペア
・出現頻度３０以上の
固有名詞ペアを関連
とする
＜クラスタリング＞
・文脈（固有名詞間
の単語）のcos距離を
利用した階層クラスタ
リング
性能
New York Timesの
記事1年分で200程
度の関連を抽出
F値は0.8程度
構文木を利用（[Hasegawa, ACL04]の改良）
[Zhang, IJCNLP05]
 関連性抽出
 2つの固有名詞間に構文解析木のパスがあるか
 クラスタリング
 類似度＝構文木の類似度
 性能
 高頻度（３０回以上）の関連について[Hasegawa, 2004]よりもF値が良かった
 低頻度（5回以上）の関連もF値0.6程度で抽出できた
 構文木カーネルを関連性抽出に利用する研究は多数あり
CRFの利用
[Culottaet, NAACL06]
 頻度が１回でも抽出したい
 関連性の抽出・ラベル付与：CRF
 Biographicなテキストに制限し、
target entityに関係のラベル(fatherなど）を付与
 それぞれのラベルについてCRF
 cousin = father-sibling-son などのimplicit relation DBを作成し、
implicit relationを抽出する
 自動的にimplicit relation DB作成
 pathの方の特徴量もCRFの重み付きで追加
 CRFの利用
 現在ではベースライン的な手法
 教師データ作成コストがかかる
TEXTRUNNER http://www.cs.washington.edu/research/textrunner/
[Banko, IJCAI07], [Banko, ACL08]
 Web上の大量な文書から関連性抽出
 113millionの文から27万の関連を抽出
 関連性の抽出
 Self-Supervised Learner
 構文解析木を利用し、ルールベースで関連性を抽出。
 抽出された関連性を教師データとし、Entityペアに関連があるか否かをCRF
で予測。
 Single-pass Extractor
 構文解析をせずに、名詞句抽出を行う
 特徴量はEntityペア周辺の、品詞、限定詞、前置詞、大文字単語など
分類による抽出（大量のWebリソースを利用）
[Mintz 09 ACL]
 分類 (supervised)
 関連性の抽出
 Freebaseというrelation と entityペアが記述された広大なDBを利用（同
じentityペアのrelationはすべて同じという仮定）
 DBに登録されているentityペアを膨大なコーパスから複数取得し、特徴
量を抽出。（複数なので、通常よりリッチ）
 関連性の分類
 得られた特徴量でモデルを構成しlogistic regressionでマルチクラス分類
（relationのクラスに分類）
 特徴量
 Lexical features
• entity間の単語・品詞、entityが文頭か、entityの前（後ろ）の単語・品詞
 Syntactic features
• entity間のdependency path、dependency pathから外れたノード
 性能
 Precition0.69程度
 Web上の大量なリソースを活用
分類による抽出（Transfer Learningの利用）
[Jiang 09 ACL]
 関連性の抽出・分類
 Transfer Learning
 教師データ作成コストが大きい。
⇒ 異なるラベルでも共有できる情報があるはずだ。
⇒ 別のラベルのパラメータを利用よう。
 関連の種類ごとに分類機を用意し、パラメータの一部を分類機間で共有
する。これにより、新しい関連に他の関連の情報を利用できるため、少な
いデータでも学習できる
 条件付きMax Entropyモデル
パラメータの共有
 性能
 ACE2004コーパスで実験し、F値0.41
Webリソースを活用した
クラスタリング [Yan 09 ACL]
 Webの大量なリソースを活用
 “高度な言語解析”と”大量なWeb文書の情報利用”を両立
 Wikipediaの信頼性の高い文書については高度な構文解析を利用（precisionを
稼ぐ）
 検索エンジンを利用して、Web上の大量の情報を利用（coverageを稼ぐ）
 関連性の抽出
 2つの名詞間に構文木的なパスがあるか
 関連性のクラスタリング：次の２つの距離を利用しk-means
 Dependency Pattern （Precisionを稼ぐ）
 Wikipediaのtextにおける、Entityペアが出現する文脈の最短依存木
 距離はEntityペア間に共通するpatternの数に基づいて計算
 Surface Pattern （Recallを稼ぐ）
 Entityペアをクエリとし検索エンジンから得られる文書群から得られるパターン
 距離は、類似度が高いpatternを類似度順にたしこむことで計算
 クラスタのサイズが大きい上位kクラスを関連として抽出
 性能
 precision : 75%前後, Coverage ： 20%前後
ブートストラッピング
[Pennacchiotti 06]
 特定の関連性抽出
Espresso: a kind of bootstrapping algorithm
 与えられたシード（entityペア）からパターンを抽出
⇒ パターンの信頼度を抽出
⇒ 信頼度の高いパターンからentityを抽出
⇒ 信頼度の高いentityを選択
⇒ （繰り返す）
 アイデア
信頼度計算にpointwise mutual informationを利用
コーパスが少ないときはWeb検索を利用
Relation Extractionのタグ付きコーパス
 SemEval2007
Task4
7 semantic relations
210 training sentences per relation
 ACE (Automatic Content Extraction)
RDC (Relation Detection and Characterization)
2002、2003, 2004
データを取得するには会員になる必要があるが、登
録料がかかる
 タグ付きコーパスの作成
Penn Treebankを使ってルールで関連にラベリング
コンテンツ
関連性抽出とは
関連性抽出のアルゴリズム
関連抽出の論文紹介
その他のトピック
Freebase
http://www.freebase.com/
人手でつけたRelation Database
Reference
“Discovering Relations among Named Entities
from Large Corpora”, Tkaaki Hasegawa and
Satoshi Sekine and Ralph Grishman, ACL2004
 “Discovering Relations Between Named Entities
from a Large Raw Corpus Using Tree SimilarityBased Clustering”, Min Zhang et al. IJCNLP2005
 “Open Information Extraction from the Web”,
Michele Banko and Oren Etzioni et al., IJCAI2007
 “The Tradeoffs Between Open and Traditional
Relation Extraction”, Michele Banko and Oren
Etzioni, ACL2008
 “Multi-Task Transfer Learning for WeaklySupervised Relation Extraction”, Jing Jiang,
ACL2009
 “Integrating Probabilistic Extraction Models and
Data Mining to Discover Relations and Patterns in
Text”, Aron Culottaet. al, NAACL2006
 “Distant supervision for relation extraction without
labeled data”, Mike Mintz, Dan Jurafsky, et. al,
ACL2009
 “A Bootstrapping Algorithm for Automatically
Harvesting Semantic Relations”, Marco
Pennacchiotti, Patric Pantel, 2006

Download Report