(cache)ブートストラッピング法による情報抽出の論文まとめ

はじめに

自然言語処理におけるタスクの一つとして、構造化されていないテキストから情報や知識を自動または半自動で取り出すことを情報抽出といいます。

最近では深層学習系の論文が国際学会ではメジャーですが、訓練・ベンチマークに用いているデータセットのレコード数が膨大であり、また高価なGPU環境が言語モデルの訓練のために必要など、必ずしも現実の要件で扱われる問題と合致していない部分があります。

また、抽出の際に起こる問題や、抽出の際に用いる指標を古典的な手法を通じて押さえておくことで、実際のデータに既存手法や経験的な手法をいろいろ適用してみるときの手がかりになります。

そこで本記事では情報抽出の領域で深層学習が流行る前に比較的メジャーであったブートストラッピング法にフォーカスし、抽出の概念、手法の解説、論文のタスクや手法の詳細などを追っていきます。

論文の流れを追うことで情報抽出の応用をしようとしている人にとって何らかの示唆があれば幸いです。

はじめに
情報抽出について
ブートストラッピング法について
論文
参考文献

情報抽出について

構造化されていないテキストから情報や知識を自動で取り出す。とはどういったことでしょうか。

例をいくつか上げてみます。

例えば新聞記事のテキストがあった時に、企業名と本社の場所を対で拾いたいとします。

・XXX社（本社：東京都中央区）は18日、新製品を発売すると発表した。

・東京都千代田区のYYY社の取締役、〇〇氏は…

この場合、対で拾いたい情報は以下の通りです

会社名	本社所在地
XXX社	東京都中央区
YYY社	東京都千代田区

また、Web上の膨大なドキュメントの中から本のタイトルと著者名を拾いたいとします。

・『ハリー・ポッター』（英: Harry Potter）は、イギリスの作家J・K・ローリングによる児童文学、ファンタジー小説のシリーズ。

・アイザック・ニュートンの代表作『プリンシピア自然哲学の数学的原理』は出版当時から難解と言われた。

この場合、対で拾いたい情報は以下の通りです

本のタイトル	著者名
ハリー・ポッター	J・K・ローリング
プリンシピア自然哲学の数学的原理	アイザック・ニュートン

例として上げたような、情報抽出の対象が「会社名と本社所在地」「本の著者」などといった2つの固有名間の関係を抽出するものである場合、これを関係抽出（Relation Extraction）といいます。

情報抽出の対象が一つの固有名や3つ以上の固有名であるケースもあります。抽出対象が固有名一つの、「会社名」「組織名」「人名」のようなものになる場合、これを固有表現抽出と呼んだりします。

情報抽出、固有表現抽出に関する概念の整理は以下の書籍の一章に更に詳しい解説が載っています。

情報抽出・固有表現抽出のための基礎知識 (実践・自然言語処理シリーズ)

作者:岩倉友哉,関根聡
発売日: 2020/03/31
メディア: 単行本

ブートストラッピング法について

自然言語処理の情報抽出におけるブートストラッピング法¹は、人手によるタグ付け作業を軽減するためのフレームワークです。

例えば関係抽出として<本のタイトル、本の著者>を取得するタスクを考えてみます。

ブートストラッピング法に於いてはこの<本のタイトル、本の著者>を表したペアをインスタンスとよび、インスタンス周辺にあるペアの手前、中間、後ろにある形態素を元に構成される周囲の情報をパターンとよびます。

ブートストラッピング法では以下の流れで抽出対象のテキストからインスタンスを抽出します。

シードインスタンスの用意：初めにインスタンスの集合として何種類かのパターンを用意する。
インスタンス事例探索：手元のインスタンスを元に、インスタンスが出現した部分（インスタンス事例）を洗い出す。出現した部分は、後のパターンの抽出に用いるため、文脈情報として一時的に保管しておく。
パターンの抽出：2で抽出した文脈の情報をもとに、パターンを抽出する。
インスタンスの抽出：3で抽出したパターンを用いてインスタンスを抽出する。
インスタンス数判定：抽出できたインスタンスの量が十分であれば終了。そうでなければ手元のインスタンスを更新した上で2のプロセスに戻る。

図にすると以下の通りです。

f:id:S_heiya:20200523124440p:plain

インスタンス抽出のイテレーションが進むに従って、シードインスタンスで想定した関係とは異なる関係を持つインスタンスが抽出されることがあり、これを意味ドリフトと言います。

個別の論文では、意味ドリフトを防ぐため、この図に加えてさらに判定材料が加わります。具体例については論文のセクションで見ていきます。

論文

Extracting Patterns and Relations from the World Wide Web (1999)

Sergey Brin, Extracting Patterns and Relations from the World Wide Web (1999)

書籍の著者とタイトルを抽出するタスクを取り扱っており、手法としてDual Iterative Pattern Relation Extraction（DIPRE）を提案しています。DIPREはほぼブートストラッピング法なのですが、パターンの生成方法に工夫があり、パターンの特殊性（Specificity）を用いてパターン抽出の量を減らすことで、意味ドリフトの問題を克服しようとしています。

DIPREにおけるインスタンス事例とパターンの属性

DIPREにおけるインスタンス事例(Occurrence)は、以下の7つの要素を持つタプルで構成されます。

author : 著者
title : タイトル
order : 著者→タイトルかタイトル→著者か
url : 記事のURL
prefix : 著者の手前m文字（orderがFalseならタイトル手前m文字）
middle : 著者とタイトルに挟まれた文字
suffix : タイトルの後m文字（orderがFalseなら著者の後m文字）

また、パターンは以下の5つの要素を持つタプルになっています。

order: パターンの想定するorder(インスタンス事例のorderに対応)
middle: 著者とタイトルに挟まれた文字
urlprefix: 記事のURLの探索範囲（prefixのため、初めの部分がマッチしているURLについてインスタンス抽出の対象になる）
prefix: インスタンスの手前文字マッチ対象
suffix: インスタンスの後の文字マッチ対象

パターンの生成

インスタンス事例を用いて、ブートストラッピング法における「3.パターンの生成」は以下のようにして行われます。

インスタンス事例に対して走査を実施し、orderとmiddleの一致を確認できたものでグルーピングし、パターンを作成します。作成したパターンのorder, middle属性とします。
作成したパターンに該当するインスタンス事例全体に対してurl属性を走査し、プレフィックスとして最長のものをパターンのurlprefix属性とします。
prefix, suffixも同様に最長のものをパターンのprefix, suffix属性とします。

URL, prefix, suffixを最長のものをとることによって、できるだけ次のインスタンス抽出時に取得する対象のインスタンスを限定しようとしています。

パターンの特殊性

更にDIPREではパターンの生成に際し、パターンの特殊性(Specificity)を考慮しています。パターンの特殊性にはいろいろな測定の仕方がありますが、計算効率化のため、以下のSpecificityを用いています。(ここで $| \cdot |$ は文字列の長さを表す)

\text{Specificity}(p) = |p.\text{middle}||p.\text{urlprefix}||p.\text{prefix}||p.\text{suffix}|

DIPREではこのSpecifityが低いものを一定のしきい値で省くようにし、抽出されるパターンの品質を担保するようにしています。（実際にはもう少し込み入った評価の仕方をしていますが、ここでは省きます）

除外パターンの回復

さらに、Specificityで除外されたパターンについても以下のようなプロセスでできる限りパターンを抽出するプロセスが走ります。

URLについてグループのインスタンス事例がすべて同じURLをもつ場合はパターンの候補として除外
そうでない場合はURLからurlprefixを除外した部分を用いて再度グルーピングを実施する。それらをサブグループとして扱ってパターン抽出のプロセスを再帰的に実施

このような過程を経て得られたパターンを用いて、ブートストラッピング法のプロセス「5.インスタンス数判定」に移り、インスタンス数が不十分な場合には2の段階に戻ります。

Snowball: Extracting Relations from Large Plain-Text Collections (2000)

Eugene Agichtein, Luis Gravano, Snowball: Extracting Relations from Large Plain-Text Collections (2000)

DIPREをベースに、パターン抽出、インスタンス抽出の際に固有表現タグや前後のパターンをベクトル化したものでマッチ度合い（Degree of Match）を測定することで意味ドリフトを回避しようとしています。また、パターン、インスタンスに対する確信度を計算することで、インスタンスの抽出の対象として確実なものを取得するようにしています。

マッチ度合い

パターン抽出の際に、SnowballではDIPREの方法に加えて、パターンの持つ属性として、固有表現のタグも追加するようにします。例えば、「会社名と本社所在地」の例でいうと、これまで会社名に該当するパターンにはどのような品詞もインスタンスの片方の要素として追加できたのに対して、Snowballでは会社名に該当する位置に固有表現タグで必ず＜組織名＞がつくインスタンスのみを抽出するようなパターンが生成されます。

DIPREではorderとmiddleの一致性によってインスタンス事例をグルーピングしていましたが、Snowballではマッチ度合い(Degree of match)という概念を導入し、マッチ度合いを類似度に見立てた単連結クラスタリングをすることでインスタンス事例のグルーピングを行います。この時、マッチ度合いはprefix, middle, suffixそれぞれの文脈情報をベクトル化した値を元に計算されます。

以下 $l_P, m_P, r_P$ 等はprefix, middle, suffixの文脈を表すベクトルとし、 $t_P = <l_P, m_P, r_P>, t_S = <l_S, m_S, r_S>$ をインスタンス事例の前後文脈を表す値とします。するとマッチ度合いは

\text{Match}(t_P, t_S) = \begin{cases} l_P \cdot l_S + m_P \cdot m_S + r_P \cdot r_S &\text{if the tags match} \\\\ 0 &\text{otherwise} \end{cases}

のように計算されます。

グループ内にあるインスタンス事例のprefix, middle, suffixを表すベクトルのセントロイド（平均したもの）が最終的なパターンの出力として用いられます。つまり、Snowballにおけるパターンの表現はprefix, middle, suffixを表すベクトルのセントロイドを $\bar{l} _ s, \bar{m} _ s, \bar{r} _ s$ インスタンスを構成する固有表現タグを $t_1, t_2$ として

< \bar{l}_s, t_1, \bar{m}_s, t_2, \bar{r}_s >

とできます。

マッチ度合いの概念はインスタンス抽出の際にも用いられ、コンマや限定詞（a, his, this等）のブレが文脈の中にあってもインスタンスを抽出できるようになっています。

確信度の計算

パターン抽出、インスタンス事例抽出を繰り返していく中で間違ったインスタンス事例を抽出しやすいパターンも出てきます。例えば

Intel, Santa Clara, announced...

のようなテキストから取れるパターンは middle の文脈を表すベクトルが $<",", 1>$ で構成され、このパターンを用いると <組織名>, <場所> で構成されるテキストすべてにマッチします。このようなパターンを用いて生成されたインスタンス事例は信用ができないため、それを測定するためにSnowballでは確信度(Confidence)を導入しています。

確信度はまずパターンに対して算出されます。Snowballで抽出してきた手元のインスタンスと合致する組をパターンが算出すればするほど確信度が高くなるように次の式を用います。

\text{Conf}(P) = \frac{P.\text{positive}}{(P.\text{positive} + P.\text{negative})}

ここで、 $P.\text{positive}, P.\text{negative}$ はパターン $P$ が抽出したインスタンス事例について、それぞれ手元のインスタンスに合致した数、合致しなかった数を表します。

更にパターンが抽出したインスタンスの確信度をパターンの確信度を元に算出します。インスタンス $T$ を生成したすべてのパターン $P = {P_i}$ の確信度と、パターン $P_i$ が生成したインスタンス事例の持つ実際の文脈 $C_i$ を用いて、インスタンス $T$ の確信度は以下のように表されます。

\text{Conf}(T) = 1 - \prod^{|P|}_{i=0}(1 - (\text{Conf}(P_i) \cdot \text{Match}(C_i, P_i)))

インスタンスの抽出のフェーズではこの確信度が一定のしきい値を上回っているかどうかを基準にして、新しくインスタンスが決定されます。

また、一つ前のイテレーションにおけるパターンの確信度が計算されていれば、現在のイテレーションにおけるパターンの確信度との重み付けによって、インスタンス抽出で用いるパターンの確信度の計算がなされます。この値は重みを $W_\text{updt}$ として

\text{Conf}(P) = \text{Conf}_\text{new} (P) \cdot W_\text{updt} + \text{Conf}_\text{old} (P) \cdot (1 - W_\text{updt})

で計算されます。

Semi-Supervised Bootstrapping of Relationship Extractors with Distributional Semantics (2015)

David S. Batista, et al. Semi-Supervised Bootstrapping of Relationship Extractors with Distributional Semantics 2015

Snowballの文脈ベクトルの表現をカウント中心のbow表現からword2vecベースの分散表現を足し上げたものに置き換えた論文です。

特質すべきなのは、著者がGihtubで論文の実装を公開しており。あわせてSnowballの実装も公開しています。

著者論文と合わせてSnowballの詳細な手続きを追うのに大変有用な情報源となっています。

github.com

この記事はMNTSQ勤務中に書かれた。

MNTSQは情報抽出に関心のあるエンジニアを募集しています。

www.wantedly.com

参考文献

統計学における、標本を重複を許して抽出する手法とは異なります。↩

ヤドカリラボ

ヤドカリのラボです

ブートストラッピング法による情報抽出の論文まとめ