テキストの構造化を支える技術 -パターンマッチで始める情報抽出-
前回の記事「テキストの構造化を支える技術 -概要編-」では、OpenIEの記念碑的なシステムであるTextRunnerを紹介しました。第2回目である今回は、シンプルながら強力なReVerbと呼ばれるシステムを紹介します。
記事の構成としては、最初にTextRunnerの課題について説明し、次にReVerbではその課題をいかにして解決したのかを説明します。最後にReVerbのアルゴリズム全体を示します。
- TextRunnerの課題
- ReVerbとは？
- ReVerbのアルゴリズム
TextRunnerの課題
まずTextRunnerの入出力についておさらいしておきましょう。TextRunnerの入出力はそれぞれテキストと関係タプル (arg1, rel, arg2) なのでした。たとえば、入力として「EBay was originally founded by Pierre Omidyar.」という文を与えた場合、出力としては (Ebay, Founded by, Pierre Omidyar) という関係のタプルを抽出することを期待されます。
TextRunnerで関係タプルを抽出することはできたのですが、抽出された関係タプルについてエラー分析をしたところ、誤って抽出されたタプルに傾向があることがわかりました。それらは以下の3つに分類されます。
- Incoherent extraction
- Uninformative extraction
- Over-specific extraction
Incoherent extractionsとは、意味のある解釈をできない関係フレーズを抽出したパターンのことです。Incoherentは支離滅裂という意味を持ちます。たとえば、以下の一番上の文では、文中に出現する動詞を接続した「contains omits」を関係フレーズとして抽出していますが、その意味は解釈できません。このようなパターンはTextRunnerの出力の約13%を占めています。
Identifying Relations for Open Information Extractionより引用
Uninformative extractionとは、重要な情報が落ちた関係フレーズを抽出したパターンです。たとえば、「Faust made a deal with the devil（ファウストは悪魔と契約した）」 という文に対して (Faust, made, a deal) という抽出をした場合が該当します。なぜなら、本当に抽出して欲しいのは「契約する」という意味の「made a deal with」を関係フレーズとした (Faust, made a deal with, the devil) だからです。以下にUninformative extractionの例を挙げます。このパターンはTextRunnerの出力の約7%を占めています。
Identifying Relations for Open Information Extractionより引用
Over-specific extractionとは、抽出した関係フレーズが詳細すぎる（over-specific）パターンです。たとえば、「The Obama administration is offering only modest greenhouse gas reduction targets at the conference.」という文に対して (Obama administration, is offering only modest greenhouse gas reduction targets at, conference) という抽出をした場合が該当します。これだけ詳細だと、後続タスクで役に立てるのが難しくなります。
まとめると、TextRunnerをはじめとする既存のOpenIEシステムの抽出結果を分析したところ、「Incoherent」「Uninformative」「Over-specific」な関係フレーズが抽出されているという問題があることが判明しました。次に説明するReVerbは、これらの問題を解決することに焦点を当てています。
ReVerbとは？
ReVerbは2011年に「Identifying Relations for Open Information Extraction」という論文で発表されたシステムです。その名前の由来は「Identify Relations from Verbs.」から来ています。その名の通り、テキスト中の動詞を起点に関係フレーズを認識する手法です。
ReVerbでは前述した3つの問題点を解決することに焦点を当てています。以下では手法のキモとなる部分について説明します。
手法のキモ
前述した3つの問題となる抽出を防ぐために、ReVerbでは抽出する関係フレーズに2つの制約を課します。その一つは構文的制約です。構文的制約はIncoherentとUninformativeな関係フレーズを減らすために使われます。もう一つは字句的制約です。こちらはOver-specificな関係フレーズを減らすために使われます。
構文的制約
構文的制約は品詞のパターンに基づいて、抽出する関係フレーズに制約を課します。具体的には以下に挙げる3パターンの制約を適用します。
最初のパターンでは、単一の動詞あるいは副詞を抽出できます。2番目のパターンでは、動詞の後に前置詞が続くパターンを抽出できます。3番目のパターンでは、動詞の後に複数のW（名詞、形容詞、副詞、代名詞、限定詞）が続き、前置詞で終わるパターンを抽出できます。複数のパターンにマッチした場合は、最長マッチした系列を採用します。
実際、上記のパターンを適用することでIncoherentとUninformativeな関係フレーズを減らせます。たとえば、Incoherentの例で紹介した 「contains omits」のような動詞が2つ並ぶ場合はパターンにマッチせず、Uninformativeの例で紹介した「Faust made a deal with the devil」では2番目のパターンが最長マッチし、関係フレーズとして「made a deal with」が抽出されます。
字句的制約
構文的制約だけだと、 (Obama administration, is offering only modest greenhouse gas reduction targets at, conference) のようなover-specificなフレーズにマッチする可能性があります。そこで、ReVerbでは字句的制約を用いてover-specificなフレーズを除去します。
字句的制約では、関係タプル (arg1, rel, arg2) について「適切な関係フレーズなら多くの異なるargと共に現れるはず」という仮説を用いて関係フレーズを絞り込みます。これはどういうことかというと、「made a deal with」のような適切な関係フレーズなら (Faust, devil) 以外の様々なargとも一緒に使われるだろうということを言っています。
字句的制約は、関係フレーズが格納された巨大な辞書を使って行います。この辞書には、多くの異なるargを取る関係フレーズが格納されています。この関係フレーズが格納された巨大な辞書に抽出された関係フレーズが入っていれば字句的制約を満たすとみなします。ちなみに、辞書は以下のステップに沿って作成します。
kは検証用データセットを使って決めています。その結果、k=20がover-speficiedなフレーズを取り除くのにちょうどよいという結果になりました。結果的に170万の関係フレーズを辞書に格納しています。
全体のアルゴリズム
ここまでで、ReVerbのキモとなる処理について解説しました。ReVerb全体の処理は以下の順番で行われます。
- 関係フレーズの抽出
- argとなる名詞句の抽出
- ロジスティック回帰を使った関係タプルへの確率割り当て
最初に、関係フレーズの抽出を行います。関係フレーズの抽出は、構文的制約で示した品詞のパターンを使って行います。その後、字句的制約を用いてフィルタリングします。
次に、argとなる名詞句を抽出します。これは、抽出した関係フレーズの左右にある名詞句を抽出することで行います。なぜ、関係フレーズの左右に出現する名詞句をargとするかというと、関係フレーズは名詞句の間に現れるべきという仮定を置いているためです。この仮定は他のOpenIEのシステムでも暗黙的に置かれていることがあるため、論文を読むときは注意しましょう。
最後に、抽出された関係タプルに対してロジスティック回帰を使って確率を割り当てます。確率を割り当てることで再現率と適合率のトレードオフを調節できるようにするのが目的です。分類器の入力は関係タプルの特徴ベクトル、出力は正しいか否かを与えます。学習データについては手動で1000文にラベル付けして作成しています。
以上で、ReVerbで使われている手法の解説は終わりです。ReVerbのソースコードは以下のリポジトリで公開されているので、実装について詳しく知りたい場合は参照すると良いのではないかと思います。
おわりに
第2回目の今回は、TextRunnerの課題とReVerbについて紹介しました。ReVerbは他のOpenIEのシステムに組み込まれることもあるので、ReVerbについて理解しておくと他のシステムについての理解をするときにも役立つのではないかと思います。次回は、節ベースで関係タプルを抽出する手法について紹介する予定です。ブログを購読していただけると見逃しがないのではないかと思います。
私のTwitterアカウントでも機械学習や自然言語処理に関する情報をつぶやいています。
この分野にご興味のある方のフォローをお待ちしています。
