Ahogrammer

Deep Dive Into NLP, ML and Cloud

テキストの構造化を支える技術 -パターンマッチで始める情報抽出-

前回の記事「テキストの構造化を支える技術 -概要編-」では、OpenIEの記念碑的なシステムであるTextRunnerを紹介しました。第2回目である今回は、シンプルながら強力な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%を占めています。

f:id:Hironsan:20181016102410p:plain
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%を占めています。

f:id:Hironsan:20181016103225p:plain
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パターンの制約を適用します。

f:id:Hironsan:20181015101518p:plain

最初のパターンでは、単一の動詞あるいは副詞を抽出できます。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を取る関係フレーズが格納されています。この関係フレーズが格納された巨大な辞書に抽出された関係フレーズが入っていれば字句的制約を満たすとみなします。ちなみに、辞書は以下のステップに沿って作成します。

  • 大規模コーパスから構文的制約を満たすフレーズを抽出
  • ヒューリスティックにargを絞り込む
  • 少なくともk以上の異なるargペアを取る関係フレーズを辞書に格納

kは検証用データセットを使って決めています。その結果、k=20がover-speficiedなフレーズを取り除くのにちょうどよいという結果になりました。結果的に170万の関係フレーズを辞書に格納しています。

全体のアルゴリズム

ここまでで、ReVerbのキモとなる処理について解説しました。ReVerb全体の処理は以下の順番で行われます。

  1. 関係フレーズの抽出
  2. argとなる名詞句の抽出
  3. ロジスティック回帰を使った関係タプルへの確率割り当て

最初に、関係フレーズの抽出を行います。関係フレーズの抽出は、構文的制約で示した品詞のパターンを使って行います。その後、字句的制約を用いてフィルタリングします。

次に、argとなる名詞句を抽出します。これは、抽出した関係フレーズの左右にある名詞句を抽出することで行います。なぜ、関係フレーズの左右に出現する名詞句をargとするかというと、関係フレーズは名詞句の間に現れるべきという仮定を置いているためです。この仮定は他のOpenIEのシステムでも暗黙的に置かれていることがあるため、論文を読むときは注意しましょう。

最後に、抽出された関係タプルに対してロジスティック回帰を使って確率を割り当てます。確率を割り当てることで再現率と適合率のトレードオフを調節できるようにするのが目的です。分類器の入力は関係タプルの特徴ベクトル、出力は正しいか否かを与えます。学習データについては手動で1000文にラベル付けして作成しています。

以上で、ReVerbで使われている手法の解説は終わりです。ReVerbのソースコードは以下のリポジトリで公開されているので、実装について詳しく知りたい場合は参照すると良いのではないかと思います。

github.com

おわりに

第2回目の今回は、TextRunnerの課題とReVerbについて紹介しました。ReVerbは他のOpenIEのシステムに組み込まれることもあるので、ReVerbについて理解しておくと他のシステムについての理解をするときにも役立つのではないかと思います。次回は、節ベースで関係タプルを抽出する手法について紹介する予定です。ブログを購読していただけると見逃しがないのではないかと思います。

私のTwitterアカウントでも機械学習自然言語処理に関する情報をつぶやいています。

この分野にご興味のある方のフォローをお待ちしています。

参考文献

テキストの構造化を支える技術 -概要編-

最近、情報抽出、特にOpen Information Extraction(OpenIE)という分野について勉強しています。せっかく勉強しているので、学んだ内容について何回かに分けて紹介していこうと思います。第一回目の今回は、OpenIEという分野の概要について紹介し、OpenIEのきっかけとなったシステムであるTextRunnerとその仕組みについて説明します。

Open Information Extractionとは?

OpenIEについて述べる前に、まずは伝統的な情報抽出について述べておきましょう。情報抽出は非構造化データであるテキストを構造化された表現に変換するタスクです*1。情報抽出で抽出される情報は関係のタプルの形(arg1, rel, arg2)で表現されます。このタプルは関係を示すフレーズ(rel)とその対象であるエンティティ(args)から成ります。一般的な処理の流れとしては固有表現認識を行った後に、抽出された固有表現間の関係を推定します。

f:id:Hironsan:20181009135000p:plain
Relation Extractionより引用

情報抽出は質問応答や知識ベースの構築といった自然言語処理の様々なタスクに使うことができます。たとえば、「When was Gandhi born?」という質問に回答することを考えます。この場合、質問文を「(Gandhi, Born-In, ??)」という形式に変換できれば、関係を満たすレコードをデータベースから探すことで質問に回答することができます。

伝統的な情報抽出の課題として、ラベル付きコーパスを作成するコストが高い点とドメインに依存した少数の関係しか扱えない点が挙げられます。ラベル付きコーパスの作成は、固有表現のラベル付をした後、固有表現間に関係のラベル付をする必要があり、非常に時間のかかる作業です。また、手動でラベル付するため、多くの関係を扱うことは困難です。以下の画像はアノテーションツールであるbratを使ってラベル付している例です。

f:id:Hironsan:20181009140041p:plain
bratより引用

OpenIEでは、伝統的な情報抽出とは異なり、抽出する関係は事前に定義されません。伝統的な情報抽出では事前に定義された関係をあるドメインコーパスから抽出することに焦点を当てていましたが、OpenIEではWebからの情報抽出に焦点を当てています。そのため、ドメインを絞ったり関係を事前に定義することは基本的にできません。本記事で紹介するTextRunnerの論文内で著者らはOpenIEに求められる以下の3つの課題を提唱しました。

  • Automation
  • Corpus Heterogeneity
  • Efficiency

Automationは、アノテーションやルールを書く労力を最小化することを示しています。Corpus Heterogeneityは、ドメイン依存を避けるために、特定のドメインで訓練された固有表現認識や構文解析のような処理を入れたくないということです。Efficiencyは、OpenIEが対象とするWeb上の大規模テキストを処理するには計算効率の良さが求められるといっています。

OpenIEの歴史をざっくりと眺めると以下のようになっています。一般的に、OpenIEの研究は2007年のTextRunnerから始まったとされています。研究を積み重ねるにつれ、適合率・再現率はどんどん向上しています。最近の事情については、COLING 2018のベストペーパーの一つである「A Survey on Open Information Extraction」が参考になるでしょう。

f:id:Hironsan:20181009143539p:plain
Open Information Extraction Systems and Downstream Applicationsより引用

以降では、OpenIEという分野が始まるきっかけとなったTextRunnerについて紹介します。

TextRunnerとは?

TextRunnerはBankoらによって2007年に発表されたOpenIEのシステムです。少々ややこしいことに、最初に発表されたのは2007年なのですが、同じ著者が2008年に発表した論文のシステムのこともTextRunnerと呼ぶこともあるようです。(むしろ、TextRunnerというと後者を指すことが多い?) 論文としては以下の2つが該当します。

TextRunnerの入出力はそれぞれテキストと関係タプル(arg1, rel, arg2)です。たとえば、"EBay was originally founded by Pierre Omidyar." という文をTextRunnerに与えたとしましょう。このとき、TextRunnerの出力として期待されるのは (Ebay, Founded by, Pierre Omidyar) という関係のタプルです。

関係タプルを抽出するための仕組みとして、TextRunnerは以下の3つのコンポーネントから構成されています。

  • Learner
  • Extractor
  • Assessor

Learnerはコーパスから自動的に学習用データを生成し、分類器に学習させます。学習用データは関係タプル(arg1, rel, arg2)がもっともらしいか否かというデータであり、分類器はタプルを2値分類するために使われます。Extractorはコーパスからタプルを抽出し、Learnerで学習した分類器で分類します。分類結果がもっともらしければそのまま残します。AssessorはExtractorで抽出したタプルに対して確率を付与します。

イメージを掴むために、各コンポーネントについてより詳しく説明します。

Learner

Learnerではまずテキストを解析して関係タプルがもっともらしいか否かというデータを生成します。たとえば、"Before the war, when Oppenheimer taught at Berkeley and CalTech"というテキストから、正例として(Oppenheimer, taught at, Berkeley), (Oppenheimer, taught at CalTech)、負例として(war, when, Oppenheimer)のようなデータを生成します。

データを生成するために、テキストを構文解析し、得られた名詞句(NP)をエンティティ、そして各名詞句のペアをつなぐ単語列を関係フレーズとします。こうして得られたタプルに対して、いくつかの構文的制約を満たす場合は正例、そうでない場合は負例とします。制約としては、各名詞句が代名詞でないとか、各名詞句をつなぐパスが文の境界を超えないといった制約を使います。

f:id:Hironsan:20181011103314p:plain
Machine Reading & Open Information Extractionより引用

最後に、生成した学習データを特徴表現に変換し、ナイーブベイズ分類器で学習させます。特徴としては関係フレーズの単語数、ストップワード数、名詞句が固有名詞か否かといった特徴を使用しています。

Extractor

Extractorでは、まずテキストから関係タプルを抽出します。そのために各単語に対して品詞タグ付けを行い、名詞句を抽出します。そして、各名詞句のペアの間にあるテキストを関係フレーズとします。

注意点は、重要ではない単語をヒューリスティックに削除する点です。たとえば、エンティティの修飾語(例: "Scientists from many universities are studying ..." → "Scientists are studying...")や副詞(例: "definitely developed" → "developed")は削除します。

こうして得られた関係タプルは、Learnerで学習した分類器に与えて正しい関係か否かを判断します。そして、正しい関係であれば得られた関係タプルをそのまま残しておきます。

Assessor

最後にAssessorを使って抽出したタプルに確率を割り当てます。確率を割り当てるために異なる文から得られた同一のタプルのカウントを求めます。抽出されたタプルに対して以下のように確率を割り当てることができます。

f:id:Hironsan:20181011125212p:plain
Machine Reading & Open Information Extractionより引用

おわりに

第一回の今回は、Open Information Extraction(OpenIE)の概要とTextRunnerについて紹介しました。TextRunnerはOpenIEの記念碑的なシステムであり、OpenIEの文脈では必ず登場するため、ここを押さえておくと次回以降の理解も深まるのではないかと思います。次回は、ReVerbと呼ばれるシンプルながら強力なOpenIEのシステムについて紹介する予定です。ブログを購読していただけると見逃しがないのではないかと思います。

私のTwitterアカウントでも機械学習自然言語処理に関する情報をつぶやいています。

この分野にご興味のある方のフォローをお待ちしています。

参考文献

固有表現認識器に言語モデルを組み込んで、性能を向上させる

最近の自然言語処理では言語モデルを使って転移学習をしたり、性能向上に役立てたりするようになってきました。言語モデルの1つであるELMoでは、言語モデルから得られる分散表現を他のタスクの入力に使うことで、質問応答や固有表現認識、評価分析といった様々なタスクの性能向上に役立つことを示しました。ELMoについては以下の記事で詳しく紹介されています。

kamujun.hatenablog.com

本記事では、以前書いた記事で構築したディープラーニングベースの固有表現認識器の性能をELMoを使って向上させる方法を紹介します。ELMoの学習から始めるのは大変なので、今回はAllenNLPで提供されている学習済みのELMoを使用します。ちなみにAllenNLPとは、自然言語処理をするのに便利な機能を提供しているライブラリです。

記事の構成は以下の3部から成っています。

  • 実装するモデルの説明
  • モデルの実装
  • モデルの学習

全体のコードは以下のGitHubリポジトリに置いてあります。スターしていただけるとうれしいです。m(_ _)m

github.com

では、実装するモデルについて説明していきます。

続きを読む