データ抽出装置、データ抽出方法、及びプログラム
【課題】機械学習方式にかかわらず、特定の記号列の組み合わせと関連性がある記号列の組み合わせを精度よく収集する。
【解決手段】正例集合から選択された要素をスパイ素性列とし、機械学習によってどのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習して識別モデルを生成し、スパイ素性列を識別モデルに適用して得られた結果から閾値を決定する。そして、ラベルなし集合に属する各素性列を識別モデルに与えて得られる指標と閾値を比較し、ラベルなし集合に属する各素性列が正例集合に属するか負例集合に属するかを判定する。
【解決手段】正例集合から選択された要素をスパイ素性列とし、機械学習によってどのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習して識別モデルを生成し、スパイ素性列を識別モデルに適用して得られた結果から閾値を決定する。そして、ラベルなし集合に属する各素性列を識別モデルに与えて得られる指標と閾値を比較し、ラベルなし集合に属する各素性列が正例集合に属するか負例集合に属するかを判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、特定の記号列の組み合わせと関連性がある記号列の組み合わせをテキストから収集するためのデータ抽出技術に関する。
【背景技術】
【０００２】
現在様々な自然言語処理技術の研究開発が進み、WEBのような膨大な知識源から必要な情報を抽出する手法が多く存在している。情報を抽出する上で或る関係に基づいた語の集合をまとめることは有益である。例えば「X=NTT」と「Y=通信」といった語のペアX−Yは、「業態」に対応する集合に属すると考える。以下では、何らかの関係を持った記号列をそれぞれエンティティeX，eYと呼び、それらの組み合わせであるエンティティペアeX,Yの抽出を行う。
【０００３】
このようなエンティティペアの抽出問題を、或る文に含まれる任意のエンティティペアが、特定のエンティティペアと関係を持つか(ω=1)持たないか(ω=0)という識別問題として捉え、最大エントロピー原理(ME)に基づいて任意のエンティティペアがω=1またはω=0のどちらの集合に属するかを識別するための識別モデルを学習することにより、識別問題を解く手法が知られている（非特許文献１）。
【０００４】
具体的には、ω＝１の集合に属するエンティティペア(正例)とω＝0の集合に属するエンティティペア（負例）とを教師ありデータとし、どちらの集合に属するか分かっていないエンティティペアを教師なしデータとする。そして、(1)まず、最初に与えられた教師ありデータを用いた機械学習によって識別モデルを生成して識別器を構成する。(2)次に、上記(1)で得られた識別器を用いて教師なしデータを識別し、正例に対応する集合、負例に対応する集合、又はどちらにも判別できない集合（ラベルなし集合）に振り分ける。(3)次に、上記(2)の振り分けで得られた新たな正例集合、負例集合、及びラベルなし集合を用いた機械学習によって識別モデルを生成して、識別器を更新する。(4)そして、上記(3)で得られた識別器を用いて、上記ラベルなし集合の要素を再度識別して、正例集合、負例集合、及びラベルなし集合を更新する。そして、(3)(4)の処理を学習結果が収束するまで（正例集合と負例集合への振り分け結果が変化しなくなるまで）繰り返し、識別モデルの更新と、正例集合、負例集合、及びラベルなし集合の更新とを行う。
【０００５】
なお、複数の正例集合を考慮する場合は、ω={1，2，…，c, N}のように、c（cは2以上の整数）個の正例集合(ω＝1〜cのc個の集合)と１個の負例集合(ω＝Nの1クラス)との合計c+1個の集合への識別問題（マルチクラス識別問題）へ拡張でき、複数の正例集合についてのエンティティペアを抽出することが可能となる。
【０００６】
上述のような識別問題とみなした場合、特定のエンティティペアと関係を持たないエンティティペアが属する集合(負例集合)をも考慮することになる。この場合、特定のエンティティペアと関係を持つエンティティペアが属する集合(正例集合)のみに基づいて機械学習を行う場合のように意図しない学習方向へ偏向することを抑えることができるが、負例集合に属するエンティティペアの与え方が新たな課題となる。
【０００７】
非特許文献１では、２単語間の関係が記述された巨大な辞書を用いることで、その関係中に存在しない単語を全て負例として用いている。
【０００８】
また、非特許文献２では、スパイアルゴリズムというヒューリスティクスを用いて負例を作成する技術も提案されている。スパイアルゴリズムとは、少量の正例とラベルなし集合の要素とを識別器に与えることで負例の閾値を得る方法である。閾値を得ることができればその閾値を用いて信頼のある負例を選択でき、さらに信頼度の高い識別モデルを学習することができる。
【０００９】
一方、非特許文献３では、互いの関係の薄い集合をペアとして、それらの集合にそれぞれ属するエンティティペアのエンティティを交換することで負例を作成する方法が提案されている。例えば、「NTT-通信」という「業態クラス」と、「バラ-赤」という「花の色」クラスがあった場合、それらのエンティティペアのエンティティを交換し、「NTT-赤」と「バラ-通信」という新たな無関係のエンティティペアを作り、これを負例として用いる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Distant supervision for relation extraction without labeled data (Mintz, M., Bills, S., Snow, R. and Jurafsky, D. 2009)
【非特許文献２】Partially Supervised Classification of Text Documents (Liu, B., Lee, W., Yu, P. and Li, X. 2002)
【非特許文献３】Lightly-Supervised Attribute Extraction (Bellare, K. , Talukdar, P. , Kumaran, G. , Pereira, F. , Liberman, M. , McCallum, A. and Dredze, M. 2007)
【発明の概要】
【発明が解決しようとする課題】
【００１１】
非特許文献１はMEを用いて関係抽出を行うシステムであるが、負例の生成には巨大な辞書が必要となるため、その作成にはコストがかかってしまう。少量のシードで大量のエンティティが抽出できることを目的とする本目的にあって、この辞書作成コストは大きな課題となる。また、非特許文献１の識別モデルは、識別結果の信頼度の高い/低いに関わらず、教師なしデータを何れかの集合に振り分けてしまうため、信頼度の低い識別結果にひきずられ、間違った方向へ識別モデルの学習が進み、識別の精度が低下してしまう可能性がある。この問題を解決するためには、予め定めた信頼度の閾値を超えないエンティティペアについては正例集合（又は負例集合）に割り振らないといった対策を採ることも考えられる。しかし、上述のように、非特許文献１では、学習が収束するまで繰り返し識別モデルを更新していくので、繰り返し毎に識別モデルが変化し、識別結果の信頼度も変わってくる。そのため、閾値も識別モデルに合わせて変化させるべきであるが、各繰り返しでどのくらい識別モデルの信頼度が変化するかは予測できないため、それ考慮して予め繰り返し毎に閾値を与えておくことは難しい。そのため、非特許文献１の方式では、特定の記号列の組み合わせと関連性がある記号列の組み合わせをテキストから精度よく収集することは困難である。
【００１２】
また、非特許文献２は、学習の初期の負例生成方法としてスパイアルゴリズムを用いた先行技術である。これにより、学習の初期の負例集合を作成する際の恣意性やノイズなどの問題は解決できる。また、非特許文献２はEMアルゴリズムの枠組みを用いているため、信頼度がアルゴリズム内部で確率として反映されており、信頼度の低い識別結果にひきずられて間違った方向へ学習が進む問題を解決することができる。しかしながら、非特許文献２の方式には、学習データとして使用可能な素性が単語のみに制限されるという問題がある。例えば「eX,“の”,<PSN>(人物名),“社長”,品詞=助詞(は,が等),eY,“事業”,品詞=助詞」というやや複雑な組成列からなるパターンのように、非特許文献２の方式を、複数の素性から構成される素性列を学習データとする方式に拡張することは難しい。このような複雑な素性列を学習データとし、直接的にEMアルゴリズムの枠組みを用いて識別モデルを求めることは困難だからである。そのため、非特許文献２の方式を用い、多用なテキストから特定の記号列の組み合わせと関連性がある記号列の組み合わせを収集することは困難である。
一方、非特許文献３は、最初に明示的な負例をエンティティの交換によって与えている。このような負例の付与は少なからず恣意的であり、ノイズを含む可能性や、網羅性に欠ける可能性がある。例えば、互いの関係の薄い集合にそれぞれ属するエンティティペアであっても、それらの片方のエンティティが同一である場合がある。このような場合にエンティティペアの片方のエンティティを交換することで負例を作成する方法を採ると再び正例が生成されてしまう。具体例を挙げると、「業態」に対応する集合に属するエンティティペア「NTT-通信」と、「親子会社関係」に対応する集合に属するエンティティペア「NTT-NTT西日本」とのエンティティ「NTT」を交換しても同じものしか得られない。これは似たようなエンティティからなるエンティティペアと関係を持つエンティティペアを集める際にクリティカルな問題となる。
【００１３】
非特許文献１での初期の負例集合の生成に、非特許文献２のスパイアルゴリズムを用いれば、初期の負例集合作成時の恣意性やノイズ、網羅性などの問題は緩和できる。また、非特許文献２の使用できる素性が制限されるという課題は、EMアルゴリズムの代わりに非特許文献１のMEに基づく学習を用いることで解決できる。しかしながら、単に非特許文献１の方式と非特許文献２の方式とを組み合わせただけの方式では、MEに基づく学習結果の信頼度が負例集合の更新処理に反映されないため、学習が誤った方向へ進むという非特許文献１の方式の問題点は解決しない。
【００１４】
本発明はこのような点に鑑みてなされたものであり、機械学習方式にかかわらず、特定の記号列の組み合わせと関連性がある記号列の組み合わせを精度よく収集することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明では、シードエンティティの組み合わせを含むテキストに対応する複数の素性からなる素性列を正例集合の初期要素とし、母集合から正例集合の初期要素を除いた差集合の少なくとも一部の要素をラベルなし集合の初期要素とし、正例集合から選択された要素を初期スパイ素性列とする。また、正例集合に属する素性列と当該素性列が正例集合に属することを表すラベルとの組、及び、ラベルなし集合に属する素性列と当該素性列が負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルを生成する。また、ラベルなし集合を表すラベルと初期スパイ素性列とを初期識別モデルに与え、初期スパイ素性列がラベルなし集合に属することになり易いかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値を決定する。そして、ラベルなし集合を表すラベルとラベルなし集合に属する各素性列とを初期識別モデルに与え、当該ラベルなし集合に属する各素性列がラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該第１指標と第１閾値とを比較することで当該ラベルなし集合に属する各素性列が負例集合に属するか否かを識別し、負例集合に属すると識別された素性列を負例集合の要素とし、母集合から当該負例集合と正例集合とを除いた差集合に相当する集合をラベルなし集合の要素とする。
【００１６】
ここで、第１閾値は初期識別モデルの信頼度を表す指標となるため、第１閾値と第１指標とを比較して負例集合の要素を選択することは、初期識別モデルの信頼度を考慮して負例集合の要素を選択することになる。これにより、機械学習方式にかかわらず、初期識別モデルの信頼度を考慮した負例集合の要素の選択が可能となる。
【００１７】
また、本発明において好ましくは、正例集合から選択された要素を正例スパイ素性列とし、負例集合から選択された要素を負例スパイ素性列とする。また、正例集合に属する素性列と当該素性列が正例集合に属することを表すラベルとの組、及び、負例集合に属する素性列と当該素性列が負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルを生成する。また、正例集合を表すラベルと正例スパイ素性列とを識別モデルに与え、正例スパイ素性列が正例集合に属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値を決定し、さらに、負例集合を表すラベルと負例スパイ素性列とを識別モデルに与え、負例スパイ素性列が負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値を決定する。さらに、正例集合を表すラベルとラベルなし集合に属する各素性列とを識別モデルに与え、当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属することになり易いかということを表す指標である正例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該正例指標と正例閾値とを比較することで当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属するか否かを識別し、当該ラベルによって表される正例集合に属すると識別された素性列を当該ラベルによって表される正例集合の要素に追加し、負例集合を表すラベルとラベルなし集合に属する各素性列とを識別モデルに与え、当該ラベルなし集合に属する各素性列が負例集合に属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と負例閾値とを比較することで当該ラベルなし集合に属する各素性列が負例集合に属するか否かを識別し、負例集合に属すると識別された素性列を負例集合の要素に追加し、母集合から当該負例集合と正例集合とを除いた差集合に相当する集合を新たなラベルなし集合とする。
【００１８】
ここで、正例閾値や負例閾値は識別モデルの信頼度を表す指標となるため、正例閾値と正例指標とを比較して正例集合の要素を選択し、負例閾値と負例指標とを比較して負例集合の要素を選択することは、識別モデルの信頼度を考慮して負例集合や正例集合の要素を選択することになる。これにより、機械学習方式にかかわらず、識別モデルの信頼度を考慮した負例集合や正例集合の要素の選択が可能となる。
【発明の効果】
【００１９】
以上により、本発明では、機械学習方式にかかわらず、特定の記号列の組み合わせと関連性がある記号列の組み合わせを精度よく収集することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】図１は、第１実施形態のデータ抽出装置の構成を説明するための図である。
【図２】図２は、図１の識別学習部の詳細を説明するための図である。
【図３】図３は、図１の識別学習部の詳細を説明するための図である。
【図４】図４は、第１実施形態のデータ抽出方法を説明するための図である。
【図５】図５Ａは、テキストを例示するための図である。図５Ｂは、エンティティペアを例示するための図である。
【図６】図６は、素性列を説明するための図である。
【図７】図７は、第２実施形態のデータ抽出装置の構成を説明するための図である。
【図８】図７は、図７の識別学習部の詳細を説明するための図である。
【図９】図８は、図７の識別学習部の詳細を説明するための図である。
【図１０】図１０は、第２実施形態のデータ抽出方法を説明するための図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施形態を説明する。
【００２２】
〔定義〕
まず、本形態で使用する用語を定義する。
【００２３】
［テキスト］テキストとは２以上の記号からなる記号列を意味する。テキストの具体例は、文などの文字列、プログラムコード列、遺伝子の塩基配列を表す記号列などである。以下では、テキストとして文を取り扱う場合を例示する。
【００２４】
［エンティティ］エンティティとは記号列を意味する。エンティティの具体例は、単語や固有名詞などの文字列、プログラムコード、塩基を表す記号などである。以下では、エンティティとして固有名詞を取り扱う場合を例示する。
【００２５】
［エンティティの組み合わせ］エンティティの組み合わせとは、２以上のエンティティの組み合わせを意味する。以下では、エンティティの組み合わせとして２つのエンティティの組み合わせであるエンティティペアを取り扱う場合を例示する。
【００２６】
［シードエンティティ］シードエンティティとは、予め定められた特定のエンティティ（記号列）を意味する。
【００２７】
［シードエンティティの組み合わせ］シードエンティティの組み合わせとは、２以上のシードエンティティの組み合わせを意味する。以下では、シードエンティティの組み合わせとして２つのシードエンティティの組み合わせであるシードエンティティペアを取り扱う場合を例示する。
【００２８】
［素性］素性とは、解析に用いられる最小単位である。素性はテキストを素性変換して得られ、テキストは複数の素性に対応する。各素性はテキストを構成する各記号列に対応する。素性の具体例は、テキストが含む各単語のエンティティからの相対位置をそれぞれ表す表層素性、テキストが含む各単語の品詞情報を表す品詞素性、テキストが含む各固有名詞情報を表す固有名詞素性、テキストが含む各単語の構文情報を表す構文素性、テキストのエンティティの出現回数を表す素性、エンティティの組み合わせ（エンティティペアなど）の共起回数を表す素性などである。
【００２９】
例えば、エンティティペアを(eX, eY)=(NTT, 通信)とするテキスト「NTT／は／通信／業務／を／主体／と／する／」を素性変換した場合、以下のような素性が得られる。
【００３０】
・表層素性の場合：「eX−1=EOS」，「eX+1=“は”」，「eX+2=eY」
ここで、ex-mはエンティティexのm単語前の単語、ex+mはエンティティexのm単語後ろの単語、EOSはその部分に単語が存在しない（文の先頭を越えている）ことを表す。
【００３１】
・品詞素性：「eX+1=助詞」，「eX+3=名詞」
・固有名詞素性：「eX=組織名」
・構文素性：「eXの階層=eYの階層」(両方とも「する」に係る)
以下では、表層素性を用いる場合を例にとって説明する。
【００３２】
［素性列］：素性列とは、或るテキストに対応する複数の素性からなる情報を意味する。
【００３３】
［母集合］母集合とは、素性列を要素とする集合を意味する。以下では、コーパスが含む各テキストに対応する複数の素性からなる素性列を要素とする集合を母集合とする場合を例示する。
【００３４】
［正例集合］正例集合とは、母集合のうち、シードエンティティの組み合わせと関連性があると識別された素性列を要素とする集合を意味する。
【００３５】
［負例集合］負例集合とは、シードエンティティの組み合わせと関連性がないと識別された素性列を要素とする集合を意味する。
【００３６】
［ラベルなし集合］ラベルなし集合とは、シードエンティティの組み合わせとの関連性が識別されていない素性列を要素とする集合を意味する。
【００３７】
［クラス］クラスとは、集合に対応する分類を意味する。
【００３８】
〔第１実施形態〕
本発明の第１実施形態を説明する。
【００３９】
＜構成＞
図１に例示するように、本形態のデータ抽出装置１は、記憶部１１０，１２０，１３０と識別学習部１４０，１５０と停止条件判定部１６０と選択部１７０を有する。図２に例示するように、識別学習部１４０は、初期正例集合作成部１４１と初期ラベルなし集合作成部１４２とスパイ作成部１４３と学習部１４４と閾値決定部１４５とクラス識別部１４６とを有する。図３に例示するように、識別学習部１５０は、スパイ作成部１５１と、学習部１５２と、閾値決定部１５３と、クラス識別部１５４とを有する。
【００４０】
なお、本形態のデータ抽出装置１は、例えば、CPU(central processing unit)、RAM(random-access memory)などから構成される公知又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される特別な装置である。すなわち、記憶部１１０，１２０，１３０は、例えば、ハードディスク装置、半導体メモリなどの公知の記憶手段からなり、識別学習部１４０，１５０や停止条件判定部１６０や選択部１７０は、例えば、CPUに所定のプログラムが読み込まれて実行されることで構成される処理手段からなる。また、識別学習部１４０，１５０や停止条件判定部１６０や選択部１７０の少なくとも一部が集積回路などのハードウェアによって構成されてもよい。
【００４１】
＜処理＞
次に、本形態の処理を説明する。
【００４２】
［前提］
本形態では、１又は複数のクラスが設定され、クラスごとに正例集合が対応するものとする。クラスからなる集合をC={1,2,…,c}と表す。cはクラスの総数を表す１以上の整数であり、j=1,...,cは各クラスを表すラベル(クラスID)である。ラベルは整数値に限られるものではなく、各クラスを識別できるものであれば文字列や記号などでも良い。なお、「ラベルがjのクラス」のことを「クラスj」と表現する。また、負例集合に対応するラベルをNで表す。また、正例集合に対応するラベルと負例集合に対応するラベルとの集合をC'={1,2,…,c,N}で表す。
【００４３】
予め形態素解析、固有表現抽出、係り受け解析が行われた文区切りのテキストの集合であるコーパスが記憶部１１０（図１）に格納される。本形態のコーパスを構成する各テキストは予め素性変換されており、当該コーパスは、テキストに対応する素性列を要素とする母集合Dとされる。前述のように、本形態では素性として表層素性を用いる。本形態の素性列は、対応するエンティティペアに対応付けられているものとする。このような母集合Dは、予め記憶部１１０（図１）に格納される。
【００４４】
また、本形態では、シードエンティティの組み合わせであるシードエンティティペア(eX, eY)がクラスjごとに設定され、シードエンティティペアの集合をPS={PS1,...,PSc}と表現する。ここで、PSjは、クラスjにおけるシードエンティティペアの集合を表す。シードエンティティペアの集合PSは、予め記憶部１２０に格納される。
【００４５】
［データ抽出処理］
まず、識別学習部１４０の初期正例集合作成部１４１（図２）が、記憶部１２０から抽出したシードエンティティペアの集合PSを用い、記憶部１１０に格納された母集合Dから抽出した素性列を初期要素とする正例集合RP0j (j=1,...,c)を生成する。なお、正例集合RPijはi回更新されたクラスjに対応する正例集合を表し、正例集合RPijの集合をRPi={RPi1,...,RPij}と表す。ステップＳ１１１ではi=0であり、正例集合RP0jの集合RP0が生成される。例えば、本形態の初期正例集合作成部１４１は、各正例クラスj∈Cについて、シードエンティティペアの集合Psj中のシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RPijの初期要素とし、正例集合RP0jの集合RP0={RP01,...,RP0j}を生成する。
【００４６】
本形態では、各RP0j(j=1,2,…,c)及びRP0は以下の(A)及び(B)の条件を満たすものとする。
【００４７】
(A) 各RP0j(j=1,2,…,c)には１以上の素性列が含まれていること。
【００４８】
(B) RP0に含まれる素性列の総数はc+1以上であること。
【００４９】
条件(A)を満たしていない場合、初期正例集合作成部１４１は、以下のいずれかの方法によって、条件(A)を満たすように調整を行う。
【００５０】
(方法1)初期正例集合作成部１４１は、RP0jに１つも素性列が含まれていないクラスjについて、新しいシードエンティティペアの追加を要求し、追加されたシードエンティティペアをP0jに追加して記憶部１２０に格納する。初期正例集合作成部１４１は、追加されたシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RP0jの要素に加える。このような処理が、各クラスjにそれぞれ対応するRP0jに含まれる素性列がそれぞれ１以上になるまで繰り返される。
【００５１】
(方法2)RP0jに１つも文が含まれていないクラスjを削除し、(A)の条件を満たすクラスのみが存在するものとして、以下の処理を進める。
【００５２】
条件(B)を満たしていない場合、初期正例集合作成部１４１は、何れかのクラスj∈Cについての新しいシードエンティティペアの追加を要求し、追加されたシードエンティティペアP0jに追加して記憶部１２０に格納する。初期正例集合作成部１４１は、追加されたシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RP0jの要素に加える。このような処理が条件(B)を満たすまで繰り返される。
【００５３】
初期正例集合作成部１４１は、以上の処理によって生成した正例集合RP0jの集合RP0={RP01,...,RP0j}を記憶部１３０に格納する（ステップＳ１１１）。
【００５４】
次に、初期ラベルなし集合作成部１４２（図２）が、記憶部１１０に格納された母集合Dから記憶部１３０に格納された正例集合RP0jの集合RP0の要素を除いた差集合D-RP0の少なくとも一部の要素を、ラベルなし集合U0の初期要素とする。例えば、初期ラベルなし集合作成部１４２は、集合RP0が含む何れか素性列と素性が１個以上マッチする素性列を差集合D-RP0から抽出し、抽出した素性列をラベルなし集合U0の初期要素とする（ステップＳ１１２）。
【００５５】
次に、スパイ作成部１４３（図２）が、記憶部１３０に格納された正例集合RP0jの集合RP0から選択された要素を初期スパイ素性列とする。例えば、スパイ作成部１４３は、記憶部１３０に記憶された正例集合RP0jの集合RP0全体から、予め定めた任意の割合rに従ってランダムに選択した要素を初期スパイ素性列の集合spy0={spy01，…，spy0c}とし、記憶部１３０に格納する。ここでspy0jは、クラスjに対応する初期スパイ素性列の集合である。ただし、本形態では、正例集合RP0全体から最低でも１つの要素が初期スパイ素性列として選択されるものとする。また、本形態の場合、要素が１つしか存在しない正例集合RP0jについては初期スパイ素性列が抽出されないものとする。以下のように、本形態では正例集合RP0jから初期スパイ素性列の集合spy0jを除いたものを学習データとして用いるからである。
【００５６】
スパイ作成部１４３は、生成した初期スパイ素性列の集合spy0={spy01，…，spy0c}を記憶部１３０に格納する（ステップＳ１１３）。
【００５７】
次に、学習部１４４が、各正例集合RP0j (j=1,...,c)に属する素性列と当該素性列が正例集合RP0jに属することを表すラベルjとの組、及び、初期ラベルなし集合作成部１４２で生成されたラベルなし集合U0に属する素性列と当該素性列がラベルなし集合U0に属することを表すラベルUとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルME0を生成する。本形態では、機械学習方式として、例えば、最大エントロピー原理に基づく識別学習（ME学習）方式を用いる（参考文献１参照）。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【００５８】
［参考文献１］A maximum entropy approach to natural language processing (Berger, A. L., Pietra, V. J. D. and Pietra, S. A. D. 1996)
【００５９】
この例の場合、学習部１４４は、例えば、各クラスj(j∈C)における各正例集合RP0j (j=1,...,c)から、当該クラスjに対応する初期スパイ素性列の集合spy0jを差し引いた差集合（RP0j−spy0j）とラベルjとの組、及び、ラベルなし集合U0と初期スパイ素性列の集合spy0との和集合（U0+spy0）とラベルUとの組を学習データとして用い、最大エントロピー原理に基づく識別学習により、差集合（RP0j−spy0j）の要素をxとした場合の条件付確率p(j｜x)と和集合（U0+spy0）の要素をxとした場合の条件付確率p(U｜x)とに対応するエントロピーを最大化する初期識別モデルME0を生成する。すなわち、学習部１４４は、例えば、x∈(RP0j−spy0j)とy=j (j=1,...,c)との組、及び、x∈(U0+spy0)とy=Uとの組を学習データとして用い、条件付確率
【００６０】
【数１】
に対するエントロピー
【００６１】
【数２】
を最大化する各パラメータλqに対応するPλ(y|x)であるP(y|x)を初期識別モデルME0とする。ただし、
【００６２】
【数３】
であり、qは各学習データ(x,y)の組にそれぞれ対応するラベルであり、p'(x)は学習データ(x,y)におけるxの出現頻度であり、fq(x,y)はqに対応する素性関数(feature function)である。
【００６３】
なお、上述学習処理の変形例として、x∈(U0+spy0)とy=Uとの組の代わりにx∈U0とy=Uとの組を学習データとして用いてもよい。
【００６４】
学習部１４４は、生成した初期識別モデルME0を記憶部１３０に格納する（ステップＳ１１４）。
【００６５】
次に、閾値決定部１４５（図２）が、ラベルなし集合U0に対応するラベルUと記憶部１３０に格納された初期スパイ素性列の集合spy0に属する初期スパイ素性列とを初期識別モデルME0に与え、初期スパイ素性列がラベルなし集合U0に属することになり易いか、逆に言うと正例集合RP0に属しにくいかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値t0Nを決定する。本形態の閾値決定部１４５は、例えば、初期識別モデルME0を用い、初期スパイ素性列の集合spy0に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の最大値
【００６６】
【数４】
を第１閾値t0Nとする。
【００６７】
また、式(4)の代わりに、初期スパイ素性列の集合spy0に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の平均値
【００６８】
【数５】
を第１閾値t0Nとしてもよい。
【００６９】
さらに、第１閾値t0Nに加えて、初期スパイ素性列の集合spy0に属する初期スパイ素性列spyとラベルjとに対する条件付確率P(j|spy)の平均値
【００７０】
【数６】
を閾値t0jとして求めてもよい。
【００７１】
閾値決定部１４５は、以上のように生成した第１閾値t0N（及び閾値t0j）を記憶部１３０に格納する（ステップＳ１１５）。
【００７２】
次に、クラス識別部１４６（図２）が、ラベルなし集合U0を表すラベルUとラベルなし集合U0に属する各素性列とを初期識別モデルME0に与え、当該ラベルなし集合U0に属する各素性列がラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合U0に属する各素性列に対してそれぞれ生成し、当該第１指標と第１閾値t0Nとを比較することで当該ラベルなし集合U0に属する各素性列が負例集合RN1に属するか否かを識別し、負例集合RN1に属すると識別された素性列を負例集合RN1の要素とし、母集合Dから当該負例集合RN1と正例集合RP0j (j=1,...,c)とを除いた差集合(D-RN1-RP0j) (j=1,...,c)に相当する集合をラベルなし集合U1の要素とする。例えば、クラス識別部１４６は、閾値決定部１４５で決定された各閾値と学習部１４４で生成された初期識別モデルME0とを用い、ラベルなし文集合U0に含まれる素性列uのうち、
p(U｜u)>t0N …(7)
を満たすものを負例集合RN1に属すると識別し、負例集合RN1に属すると識別された素性列を負例集合RN1の要素とする。また、例えば、クラス識別部１４６は、正例集合RP0j (j=1,...,c)をそのまま正例集合RP1j (j=1,...,c)とし、RP1=｛RP11，…，RP1C｝とする。また、例えば、クラス識別部１４６は、ラベルなし集合U0に含まれる素性列のうち負例集合RN1の要素と識別されなかった素性列の集合U0−RN1と、ラベルなし文集合検索部１４２において、母集合Dに含まれる素性列のうちラベルなし集合U0として検索されなかった素性列の集合D−RP0−U0の和、すなわちD−RP1−RN1を新たなラベルなし文集合U1として作成する。
【００７３】
なお、閾値決定部１４５で閾値t0j (j=1,...,c)が生成される場合には、正例集合RP0j (j=1,...,c)をそのまま正例集合RP1j (j=1,...,c)とする代わりに、ラベルなし文集合U0に含まれる素性列uのうち、
p(j｜u)>t0j …(8)
を満たすものを正例集合RP1j (j=1,...,c)に属すると識別し、正例集合RP1j (j=1,...,c)に属すると識別された素性列をそれぞれ正例集合RP1j (j=1,...,c)の要素としてもよい（ステップＳ１１６）。
【００７４】
次に、停止条件判定部１６０（図１）がi=1に設定する（ステップＳ１２１）。
【００７５】
次に、識別学習部１５０のスパイ作成部１５１（図３）が、正例集合RPij(j=1,...,c)から選択された要素を正例スパイ素性列とし、負例集合RNiから選択された要素を負例スパイ素性列とする。ラベルjに対応する正例スパイ素性列の集合をspyijで表し、負例スパイ素性列の集合をspyiNで表す。例えば、スパイ作成部１５１は、正例集合RPij(j=1,...,c)及び負例集合RNi中から，予め定めた任意の割合rに従ってランダムに正例スパイ素性列及び負例スパイ素性列を選択し、スパイ素性列の集合spyi=｛spyi1,…,spyic,spyiN｝を生成する。スパイ作成部１５１は、生成したスパイ素性列の集合spyiを記憶部１３０に格納する（ステップＳ１２２）。
【００７６】
次に、学習部１５２（図３）が、正例集合RPij (j=1,...,c)に属する素性列と当該素性列が正例集合に属することを表すラベルjとの組、及び、負例集合RN1に属する素性列と当該素性列が負例集合RNiに属することを表すラベルNとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルMEiを生成する。ここでの機械学習は、前述のステップＳ１１４と同様に行う。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【００７７】
例えば、学習部１５２は、各クラスj(j∈C)における各正例集合RPij (j=1,...,c)から、当該クラスjに対応する正例スパイ素性列の集合spyijを差し引いた差集合（RPij−spyij）(j=1,...,c)とラベルj(j=1,...,c)との組、負例集合RNiから負例スパイ素性列の集合spyiNを差し引いた差集合（RNi−spyiN）とラベルNとの組、及び、ラベルなし集合Uiとスパイ素性列の集合spyiとの和集合（Ui+spyi）とラベルUとの組を学習データとして用い、前述した最大エントロピー原理に基づく識別学習により（式(1)-(3)）、前述したようなP(y|x)を求め、これを識別モデルMEiとする。なお、ラベルUはラベルなし集合Uiを表すラベルである。
【００７８】
また、上述学習処理の変形例として、和集合（Ui+spyi）とラベルUとの組との代わりにUiとラベルUとの組を学習データとして用いてもよい。また、和集合（Ui+spyi）とラベルUとの組やUiとラベルUを学習データとして用いないことにしてもよい。
【００７９】
学習部１５２は、生成した識別モデルMEiを記憶部１３０に格納する（ステップＳ１２３）。
【００８０】
次に、閾値決定部１５３（図３）が、少なくとも、正例集合RPijを表すラベルj(j=1,...,c)と記憶部１３０に格納された正例スパイ素性列（spyijの要素）とを識別モデルMEiに与え、正例スパイ素性列が正例集合RPijに属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値tij(j=1,...,c)を決定する。さらに、閾値決定部１５３は、負例集合RNiを表すラベルNと記憶部１３０に格納された負例スパイ素性列（spyijの要素）とを識別モデルMEiに与え、負例スパイ素性列が負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値tiNを決定する。本形態の閾値決定部１５３は、例えば、識別モデルMEiを用い、スパイ素性列の集合spy0に属するスパイ素性列spyとラベルj=1,2,…,cとNとUとを用い、以下のように正例閾値tij(j=1,...,c)と負例閾値tiNとラベルなし閾値tiUとを生成する。なお、minαはαの最小値を表す。
【００８１】
クラスjに対する正例閾値tij:
【００８２】
【数７】
クラスNに対する負例閾値tiN：
【００８３】
【数８】
ラベルなしクラスに対する閾値:
【００８４】
【数９】
なお、式(9)(10)の代わりに以下のように正例閾値tijと負例閾値tiNとが生成されてもよい。
【００８５】
クラスjに対する正例閾値tij:
【００８６】
【数１０】
クラスNに対する負例閾値tiN：
【００８７】
【数１１】
また、ラベルなし閾値tiUを用いないことにしてもよい（ステップＳ１２４）。
【００８８】
次に、クラス識別部１５４（図３）が、正例集合RPijを表すラベルjとラベルなし集合Uiに属する各素性列とを識別モデルMEiに与え、当該ラベルなし集合Uiに属する各素性列が当該ラベルjによって表される正例集合RPijに属することになり易いかということを表す指標である正例指標を当該ラベルなし集合Uiに属する各素性列に対してそれぞれ生成し、当該正例指標と正例閾値とを比較することで当該ラベルなし集合Uiに属する各素性列が当該ラベルjによって表される正例集合RPi+1jに属するか否かを識別し、当該ラベルjによって表される正例集合RPi+1jに属すると識別された素性列を当該ラベルjによって表される正例集合RPi+1jの要素に追加する。また、クラス識別部１５４は、負例集合RNiを表すラベルNとラベルなし集合Uiに属する各素性列とを識別モデルMEiに与え、当該ラベルなし集合Uiに属する各素性列が負例集合RNiに属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と負例閾値とを比較することで当該ラベルなし集合Uiに属する各素性列が負例集合RNi+1に属するか否かを識別し、負例集合RNi+1に属すると識別された素性列を負例集合RNi+1の要素に追加する。さらに、クラス識別部１５４は、母集合Dから当該負例集合RNiと正例集合RPij(j=1,...,c)とを除いた差集合に相当する集合を新たなラベルなし集合Ui+1とする。本形態のクラス識別部１５４は、例えば、閾値決定部１５３で決定された各閾値と学習部１５２で生成された識別モデルMEiとを用い、以下のような識別処理を行う。
【００８９】
ラベルなし集合Uiに含まれる素性列xについて、
(I) p(U|x)<tiU である。
【００９０】
(II)全てのj'∈C'(C'={1,...,c,N})のうちp(j'|x)を最大にするクラスj'についてp(j'|x)>tijである。
の両方の条件を満たす場合には当該素性列xがクラスj'に対応する正例集合RPi+1j又は負例集合RNi+1に属すると識別し、当該素性列xを正例集合RPi+1j又は負例集合RNi+1の要素とする。一方、(I)(II)の少なくとも一方を満たさない場合には、当該素性列xがラベルなし集合Ui+1に属すると識別し、当該素性列xをラベルなし集合Ui+1の要素とする。ラベルなし集合Uiに含まれる各素性列xは、新たな正例集合RPi+1j、負例集合RNi+1又はラベルなし集合Ui+1のいずれかに識別される。
【００９１】
クラス識別部１５４は、更新した正例集合RPi+1j、負例集合RNi+1及びラベルなし集合Ui+1を記憶部１３０に格納する（ステップＳ１２５）。
【００９２】
次に、停止条件判定部１６０（図１）が、予め定められた停止条件を満たすか否かを判定する。本形態の停止条件判定部１６０は、例えば、ラベルなし集合Ui中の素性列が新たに正例集合RPi+1j若しくは負例集合RNi+1に割り当てられなかった場合、又は、ラベルなし集合Uiが空集合となった場合には停止条件を満たさないと判定し、そうでない場合には停止条件を満たすと判定する（ステップＳ１２６）。ここで、停止条件を満たさないと判定された場合、停止条件判定部１６０は、i+1を新たなiとおき（ステップＳ１２７）、処理をステップＳ１２２に戻す。これにより、停止条件判定部１６０は、スパイ作成部１５１の処理と学習部１５２の処理と閾値決定部１５３の処理とクラス識別部１５４の処理とを再び実行させる。一方、停止条件を満たすと判定された場合、以下のステップＳ１２８の処理に進む。
【００９３】
ステップＳ１２８では、選択部１７０（図１）が、記憶部１３０に格納された正例集合RPi+1jと最後の識別モデルMEiとを用い、正例集合RPi+1jから素性列を選択する。本形態の選択部１７０は、正例集合RPi+1jを表すラベルjと正例集合RPi+1jに属する素性列とを識別モデルMEiに与え、正例集合RPi+1jに属する素性列がラベルjに対応する正例集合RPi+1jに属することになり易いかということを表す指標を生成し、当該指標を基準として正例集合RPi+1jから素性列を選択する。例えば、選択部１７０は、最後に得られた識別モデルMEiを各クラスjにおける正例集合RPi+1jに属する各素性列xに適用し、条件付確率p(j|x)の高い順に正例集合RPi+1jに属する各素性列xをソートし、ソートした各素性列xのうち上位K個（Kは予め定められたクラスごとに抽出すべきエンティティペアの数）の素性列を選択する。選択部１７０は、選択した素性列に対応するエンティティペアを出力する。ただし、出力しようとするエンティティペアがそれまでに出力したものと重複する場合には、そのような重複するエンティティペアを出力しないことにしてもよい。
【００９４】
また、このような処理の代わりに、選択部１７０が、正例集合RPi+1jを表すラベルjと正例集合RPi+1jに属する素性列が含む素性の組み合わせとを識別モデルMEiに与え、当該素性の組み合わせが正例集合RPi+1jに属することになり易いかということを表す指標を生成し、当該基準として、正例集合RPi+1jに属する素性列から素性の組み合わせを選択してもよい。例えば、選択部１７０が、条件付確率p(j|x)を基準として素性列単位でソートを行う代わりに、最後に得られた識別モデルMEiを各クラスjにおける正例集合RPi+1jに属する各素性列xに対応するエンティティペアeに適用し、条件付確率p(j|e)の高い順に正例集合RPi+1jに属する各素性列x対応するエンティティペアeをソートし、ソートした各エンティティペアeのうち上位K個（Kは予め定められたクラスごとに抽出すべきエンティティペアの数）のエンティティペアを選択してもよい。この場合、選択部１７０は、選択したエンティティペアを出力する（ステップＳ１２８）。
【００９５】
＜具体例＞
次に、具体例を用いて本形態の処理を説明する。
【００９６】
以下では、母集合Dに含まれる素性列を図５Ａに例示するu1,...,u11とする。なお、図５Ａでは、各u1,...,u11とそれらに対応する各テキストとが対応付けられている。また、図５Ａのテキストを構成する単語のうち下線で示した単語はエンティティである。また、業態クラス(j=1)〉及び〈社長クラス(j=2)〉の２クラスにそれぞれ対応する２つの正例集合RPi+1jが存在し、シードエンティティペアの集合PS={PS1,PS2}として図５ＢのPs1とPs2が与えられているとする。また、素性列u1,...,u11は、それぞれ、対応するテキストに対して図６のような素性変換（簡単のためexの表層素性のみに注目している）を行って得られたものであるとする。
【００９７】
この場合、ステップＳ１１１では、初期正例集合作成部１４１が、図５ＢのPs1，Ps2に対して図５Ａのu1,...,u11に対応する各テキストを検索するので、以下の正例集合RP0={RP01, RP02}が生成される。
【００９８】
RP01={u1, u3} …(14)
RP02={u5, u6, u9} …(15)
また、ステップＳ１１２では、上記RP0に含まれる素性列と、母集合Dの残りの素性列(D-RP0)について
u1と素性値が1つ以上一致する素性列：u2, u4, u7, u8, u10
u3と素性値が1つ以上一致する素性列：u2, u4, u7, u8, u10
u5と素性値が1つ以上一致する素性列：u4, u11
u6と素性値が1つ以上一致する素性列：u2, u4, u7, u8
u9と素性値が1つ以上一致する素性列：u2, u4, u7, u8, u11
であるため、初期ラベルなし集合作成部１４２が、ラベルなし集合
U0={u2, u4, u7, u8，u10，u11}
を生成する。
【００９９】
また、ステップＳ１１３では、スパイ作成部１４３が、
spy01={u1}
spy02={u6}
を初期スパイ素性列の集合として選択したと仮定する。
【０１００】
すると、ステップＳ１１４では、学習部１４４が、
RP01-spy01={u3}
RP02-spy02={u5, u9}
U0+spy0={u1, u2, u4, u6, u7, u8，u10，u11}
を用いて機械学習を行い、識別モデルME0を作成する。
【０１０１】
作成した識別モデルME0に基づいて、各初期スパイ素性列u1,u6のラベルUへの条件付確率を計算した結果が
p(U|u1)=0.15
p(U|u6)=0.3
であるとすると、ステップＳ１１５で閾値決定部１４５が決定する閾値t0Nはmax[p(U|u1),p(U|u6)]=0.3となる。
【０１０２】
次に、ステップＳ１１６において、クラス識別部１４６が、U0={u2, u4, u7, u8，u10，u11}の各素性列の識別を行う。各素性列u3, u4, u7, u11のラベルUへの条件付確率を計算した結果が
p(U|u2)=0.1
p(U|u4)=0.2
p(U|u7)=0.2
p(U|u8)=0.25
p(U|u10)=0.7
p(U|u11)=0.8
とすると、閾値t0N=0.3を超えるu10, u11が負例集合に識別されるので、
RN1={u10, u11}
となり、
U1={u2, u4, u7, u8}
RP1={u1, u3, u5, u6, u9}
となる。
【０１０３】
次に、ステップＳ１２２で、スパイ作成部１５１が、i=1に対して
spy11={u3}
spy12={u9}
spy1N={u10}
をスパイ素性列として選択したとする。
【０１０４】
続いて、ステップＳ１２３で、学習部１５２が、RP11-spy11,RP12-spy12,RN1-spy1N, U1+spy1を用いて識別モデルME1を学習する。
【０１０５】
クラスj=1, j=2及びクラスNについてはスパイ素性列が１つずつしか存在しないため、ステップＳ１２４で、閾値決定部１５３が、
t1j=1=p(j=1|u3)=0.55
t1j=2=p(j=2|u9)=0.6
t1N=p(N|u10)=0.6
を設定する。
【０１０６】
また、閾値t１Uはp(U|u3) , p(U|u9), p(U|u10)のうちの最大値を取り、t１U=0.3だったと仮定する。
【０１０７】
次のステップＳ１２５において、クラス識別部１５４が、U1={u2, u4, u7, u8}が含む各素性列の識別を行う。素性列u2について条件付確率を計算した結果が以下のようになっているとする。
【０１０８】
p(j=1|u2)=0.7
p(j=2|u2)=0.05
p(N|u2)=0.1
p(U|u2)=0.15
ここで、p(U|u2)はt１U=0.6より小さく、argmaxj∈C p(j|u2)とするクラスj=1において、p(j=1|u2)=0.7 ＞ t１1(=0.55)なので、素性列u2はクラス1の正例集合RP21に識別される。
【０１０９】
同様に素性列u4，u7, u8∈U1について条件付確率を計算した結果を
p(j=1|u4)=0.1
p(j=2|u4)=0.7
p(N|u4)=0.1
p(U|u4)=0.1
p(j=1|u7)=0.7
p(j=2|u7)=0.1
p(N|u7)=0.15
p(U|u7)=0.05
p(j=1|u8)=0.25
p(j=2|u8)=0.4
p(N|u8)=0.15
p(U|u8)=0.2
とすると、素性列u4はクラス2の正例集合RP22に、素性列u7はクラス1の正例集合RP21に識別される。一方、素性列u8はargmaxj∈C p(j|u8)となるクラスはj=2であるが、p(c2|u8)=0.4 ＞ t１2(=0.6)であるため、PR22には識別されず、ラベルなし集合U2へ識別される。このように閾値を設けることで、学習部１５２で作成した識別モデルME1に基づく識別結果を訂正することができる。よって、
RP21＝{u1, u2, u3, u7}
RP22＝{u4, u5, u6, u9}
RN2={u10, u11}
U2={u8}
となる。
【０１１０】
ここでは、新たにU1中の文u2，u4，u7がRP21, RP22又はRN2に割り当てられているため、ステップＳ１２６で停止条件判定部１６０は、i+1を新たなiとおいて（ステップＳ１２７）、ステップＳ１２２の処理に戻すように制御する。それにより、新たにRP2,RN2,U2に対してステップＳ１２２〜Ｓ１２６の処理が繰り返される。
【０１１１】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態では、各クラスに対応する各正例集合、負例集合及びラベルなし集合をそれぞれV個（Vは予め設定された2以上の整数）の部分集合に分割し、部分集合ごとに閾値を定めてラベルなし集合の要素を識別し、その識別結果を統合して各正例集合、負例集合及びラベルなし集合の更新処理を行う。以下では、第１実施形態との相違点を中心に説明、第１実施形態と共通する部分については説明を省略する。また、第１実施形態と同一の処理部やステップについては、第１実施形態と同じ参照番号を付して説明を省略する。
【０１１２】
＜構成＞
図７に例示するように、本形態のデータ抽出装置２は、記憶部１１０，１２０，１３０と識別学習部２４０，２５０と停止条件判定部１６０と選択部１７０を有する。図８に例示するように、識別学習部２４０は、初期正例集合作成部２４１と初期ラベルなし集合作成部１４２とスパイ作成・分割部２４３と学習部２４４と閾値決定部２４５とクラス識別部２４６とを有する。クラス識別部２４６は、閾値判定部２４６Ａと統合部２４６Ｂとを有する。図９に例示するように、識別学習部２５０は、スパイ作成・分割部２５１と、学習部２５２と、閾値決定部２５３と、クラス識別部２５４とを有する。また、クラス識別部２５４は、閾値判定部２５４Ａと統合部２５４Ｂとを有する。
【０１１３】
なお、本形態のデータ抽出装置２は、例えば、CPU、RAMなどから構成される公知又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される特別な装置である。また、識別学習部２４０，２５０や停止条件判定部１６０や選択部１７０の少なくとも一部が集積回路などのハードウェアによって構成されてもよい。
【０１１４】
＜処理＞
次に、本形態の処理を説明する。
【０１１５】
［前提］
第１実施形態と同じである。
【０１１６】
［データ抽出処理］
まず、識別学習部２４０の初期正例集合作成部２４１（図８）が、記憶部１２０から抽出したシードエンティティペアの集合PSを用い、記憶部１１０に格納された母集合Dから抽出した素性列を初期要素とする正例集合RPijの集合をRPi={RPi1,...,RPij}を生成する。ただし、第１実施形態と異なり、各RP0j(j=1,2,…,c)及びRP0は以下の(A)及び(B)の条件を満たすものとする。
【０１１７】
(A-2) 各RP0j(j=1,2,…,c)にはV以上の素性列が含まれていること。
【０１１８】
(B-2) RP0に含まれる素性列の総数はVc+V以上であること。
【０１１９】
条件(A-2)を満たしていない場合、初期正例集合作成部２４１は、以下のいずれかの方法によって、条件(A-2)を満たすように調整を行う。
【０１２０】
(方法1-2)初期正例集合作成部２４１は、RP0jに含まれる素性列の数がV未満のクラスjについて、新しいシードエンティティペアの追加を要求し、追加されたシードエンティティペアをP0jに追加して記憶部１２０に格納する。初期正例集合作成部２４１は、追加されたシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RP0jの要素に加える。このような処理が、各クラスjにそれぞれ対応するRP0jに含まれる素性列がそれぞれV以上になるまで繰り返される。
【０１２１】
(方法2-2)RP0jに含まれる素性列がV未満のクラスjを削除し、(A-2)の条件を満たすクラスのみが存在するものとして、以下の処理を進める。
【０１２２】
条件(B-2)を満たしていない場合の処理は第１実施形態と同様である。
【０１２３】
初期正例集合作成部２４１は、以上の処理によって生成した正例集合RP0jの集合RP0={RP01,...,RP0j}を記憶部１３０に格納する（ステップＳ２１１）。
【０１２４】
次に、第１実施形態のステップＳ１１２で説明したように、初期ラベルなし集合作成部１４２（図８）が、ラベルなし集合U0を生成する（ステップＳ１１２）。
【０１２５】
次に、スパイ作成・分割部２４３（図８）が、記憶部１３０に格納された各クラスjに対応する正例集合RP0jをそれぞれV個の部分集合に分割し、各部分集合からそれぞれ選択された要素を初期スパイ素性列とする。すなわち、本形態では、クラスjに対応する正例集合RP0jをV個の部文集合に分割したものを
RP0j={spy0j(1),…,spy0j(V)} …(16)
とし、初期スパイ素性列の集合spy0を
spy0={spy0(1),…,spy0(V)} …(17)
のようにV個の部分集合からなるものとし、これらの各部文集合を
spy0(v)={spy01(v),…,spy0c(v)} (v=1,2,3,…,V) …(18)
とする。
【０１２６】
スパイ作成・分割部２４３は、生成した初期スパイ素性列の集合spy0を記憶部１３０に格納する（ステップＳ２１３）。
【０１２７】
次に、学習部２４４が、部分集合v(v=1,2,3,…,V)ごとに独立に、各正例集合RP0j (j=1,...,c)に属する素性列と当該素性列が正例集合正例集合RP0jに属することを表すラベルjとの組、及び、初期ラベルなし集合作成部１４２で生成されたラベルなし集合U0に属する素性列と当該素性列がラベルなし集合U0に属することを表すラベルUとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルME0(v)を生成する。本形態では、第１実施形態と同様な機械学習方式を用いる。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【０１２８】
例えば、学習部２４４は、部分集合v(v=1,2,3,…,V)ごとに独立に、差集合（RP0j−spy0j(v)）とラベルjとの組、及び、ラベルなし集合U0とラベルUとの組を学習データとして用い、最大エントロピー原理に基づく識別学習により、差集合（RP0j−spy0j(v)）の要素をxとした場合の条件付確率p(j｜x)とラベルなし集合U0の要素をxとした場合の条件付確率p(U｜x)とに対応するエントロピーを最大化する初期識別モデルME0(v) (v=1,2,3,…,V)を生成する。なお、部分集合v(v=1,2,3,…,V)ごとに独立に機械学習を行うのではなく、第１実施形態と同様にV個の分割を一度無視して機械学習を行って初期識別モデルをME0を得た後に，ME0をME0 (v) (v=1,2,3,…,V)とみなして用いてもよい。
【０１２９】
学習部２４４は、生成した初期識別モデルME0(v) (v=1,2,3,…,V)を記憶部１３０に格納する（ステップＳ２１４）。
【０１３０】
次に、閾値決定部２４５（図８）が、部分集合v(v=1,2,3,…,V)ごとに独立に、ラベルなし集合U0に対応するラベルUと記憶部１３０に格納された初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列とを初期識別モデルME0(v)に与え、初期スパイ素性列がラベルなし集合U0に属することになり易いか，逆に言えば正例集合RP0に属することになりにくいか，ということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値t0N(v)を決定する。本形態の閾値決定部２４５は、例えば、初期識別モデルME0(v)を用い、初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の最大値
【０１３１】
【数１２】
を第１閾値t0N(v)とする。
【０１３２】
また、式(19)の代わりに、初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の平均値
【０１３３】
【数１３】
を第１閾値t0N(v)としてもよい。
【０１３４】
さらに、第１閾値t0N(v)に加えて、初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列spyとラベルjとに対する条件付確率P(j|spy)の平均値
【０１３５】
【数１４】
を閾値t0j(v)として求めてもよい。
【０１３６】
閾値決定部２４５は、以上のように生成した第１閾値t0N(v)（及び閾値t0j(v)）を記憶部１３０に格納する（ステップＳ２１５）。
【０１３７】
次に、クラス識別部２４６（図８）の閾値判定部２４６Ａが、各部分集合v(v=1,2,3,…,V)について、ラベルなし集合U0を表すラベルUとラベルなし集合U0に属する各素性列とを初期識別モデルME0(v)に与え、当該ラベルなし集合U0に属する各素性列がラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合U0に属する各素性列に対してそれぞれ生成し、当該第１指標と第１閾値t0N(v)とを比較する。閾値判定部２４６Ａは、当該比較結果に基づき、各部分集合v(v=1,2,3,…,V)について、当該ラベルなし集合U0に属する各素性列が負例集合RN1(v)に属するか否かを識別し、負例集合RN1(v)に属すると識別された素性列を負例集合RN1(v)の要素とする。例えば、閾値判定部２４６Ａは、閾値決定部２４５で決定された各閾値と学習部２４４で生成された初期識別モデルME0(v)とを用い、
pv(U｜u)>t0N(v) …(22)
を満たすか否かを判定し、これを満たす素性列uを負例集合RN1(v)の要素とする。なお、pv(U｜u)は、初期識別モデルME0(v)を用いて生成された条件付確率を表す。
【０１３８】
また、例えば、閾値判定部２４６Ａは、記憶部１３０から読み出した各クラスjに対応する正例集合RP0j (j=1,...,c)をそれぞれV個の部分集合に分割し、それらをRP1j(1)，…，RP1j(V)とし、RP1j(v) (v=1,...,V)を正例集合RN1(v)の要素とする。
【０１３９】
なお、閾値決定部２４５で閾値t0j(v)(j=1,...,c)が生成される場合には、正例集合RP0j(v)(j=1,...,c)を正例集合RP1j(v)とする代わりに、ラベルなし文集合U0に含まれる素性列uのうち、
pv(j｜u)>t0j(v) …(23)
を満たすものを正例集合RP1j(v)に属すると識別し、正例集合RP1j(v)に属すると識別された素性列をそれぞれ正例集合RP1j(v)の要素としてもよい（ステップＳ２１６）。
【０１４０】
次に、統合部２４６ＢがRN1(1),...,RN1(V)とRP1j(1),...,RP1j(V)(j=1,...,c)とを入力とし、統合部２４６Ｂは、第１判定閾値個以上の第１閾値t0N(v)に対して第１判定条件を満たすと判定された第１指標に対応する素性列を負例集合RN1の要素とする。すなわち、統合部２４６Ｂは、第１判定閾値個以上のRN1(1),...,RN1(V)が含む同一の素性列を負例集合RN1の要素とする。また、統合部２４６Ｂは、第１判定閾値個以上のRP1j(1),...,RP1j(V)が含む同一の素性列を正例集合RP1jの要素とする。
【０１４１】
ここで、第１判定閾値の例は、V/2, V, 1などの値から選択可能である。例えば、Vを選択した場合は、V/2を選択した場合よりも精度の高い正例及び負例を集めることができるが、正例や負例の数が少なくなってしまう危険性がある。1を選択した場合は、精度が他の第１判定閾値の場合よりも低くなる可能性があるものの、より多くの正例及び負例を集めることができると言える。これらの第１判定閾値のうちV/2は、システムが出力する正例や負例の精度（適合率）との網羅性（再現率）のバランスを取った平均的な閾値といえる。このように、本形態では、第１判定閾値の選択に応じて、抽出できる正例及び負例の精度や数を調整することができる。さらに、統合部２４６Ｂは、D−RP1−RN1（RP1=｛RP11，…，RP1C｝）を新たなラベルなし文集合U1として作成する（ステップＳ２１７）。
【０１４２】
次に、停止条件判定部１６０（図７）がi=1に設定する（ステップＳ１２１）。
【０１４３】
次に、識別学習部２５０のスパイ作成・分割部２５１（図９）が、記憶部１３０に格納された各クラスjに対応する正例集合RPijをそれぞれV個の部分集合に分割し、各部分集合からそれぞれ選択された要素を正例スパイ素性列する。また、スパイ作成・分割部２５１は、記憶部１３０に格納された負例集合RNiをそれぞれV個の部分集合に分割し、各部分集合からそれぞれ選択された要素を負例スパイ素性列とする。本形態のスパイ作成・分割部２５１は、例えば、RPij (j=1,2,…,c)およびRNiをそれぞれV個の部分集合に分割し、スパイ文集合spyi={spyi(1),…,spyi(V)}を作成する。ここで、
spyi(v)={spyi1(v),…,spyic(v),spyiN(v)} v=1,2,3,…,V
spyij={spyij(1),…,spyij(V)}, spyi={spyi(1),…,spyi(V)}
である。
【０１４４】
スパイ作成・分割部２５１は、生成したスパイ文集合spyi={spyi(1),…,spyi(V)}を記憶部１３０に格納する（ステップＳ２２２）。
【０１４５】
次に、学習部２５２（図３）が、部分集合v(v=1,2,3,…,V)ごとに独立に、正例集合RPij (j=1,...,c)に属する素性列と当該素性列が正例集合に属することを表すラベルjとの組、及び、負例集合RN1に属する素性列と当該素性列が負例集合RNiに属することを表すラベルNとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルMEi(v)を生成する。ここでの機械学習は、前述のステップＳ２１４と同様に行う。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【０１４６】
例えば、学習部２５２は、部分集合v(v=1,2,3,…,V)ごとに独立に、各クラスj(j∈C)における各正例集合RPij (j=1,...,c)から、当該クラスjに対応する正例スパイ素性列の集合spyij(v)を差し引いた差集合（RPij−spyij(v)）(j=1,...,c)とラベルj(j=1,...,c)との組、負例集合RNiから負例スパイ素性列の集合spyiN(v)を差し引いた差集合（RNi−spyiN(v)）とラベルNとの組、及び、ラベルなし集合Uiとスパイ素性列の集合spyiとの和集合（Ui+spyi(v)）とラベルUとの組を学習データとして用い、前述した最大エントロピー原理に基づく識別学習により、識別モデルMEi(v)を求める。なお、部分集合v(v=1,2,3,…,V)ごとに独立に機械学習を行うのではなく、第１実施形態と同様にV個の分割を一度無視して機械学習を行って初期識別モデルをMEiを得た後に、MEiをMEi (v) (v=1,2,3,…,V)とみなして用いてもよい。
【０１４７】
学習部２５２は、生成した識別モデルMEi(v)を記憶部１３０に格納する（ステップＳ２２３）。
【０１４８】
次に、閾値決定部２５３（図９）が、部分集合v(v=1,2,3,…,V)ごとに独立に、正例集合RPijを表すラベルj(j=1,...,c)と記憶部１３０に格納された正例スパイ素性列（spyij(v)の要素）とを識別モデルMEi(v)に与え、正例スパイ素性列が正例集合RPijに属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値tij(v) (j=1,...,c)を決定する。さらに、閾値決定部２５３は、負例集合RNiを表すラベルNと記憶部１３０に格納された負例スパイ素性列（spyij(v)の要素）とを識別モデルMEi(v)に与え、負例スパイ素性列が負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値tiNを決定する。本形態の閾値決定部２５３は、例えば、識別モデルMEi(v)を用い、スパイ素性列の集合spy0(v)に属するスパイ素性列spyとラベルj=1,2,…,cとNとを用い、以下のように正例閾値tij(v) (j=1,...,c)と負例閾値tiN(v)とを生成する。
【０１４９】
クラスjに対する正例閾値tij(v):
【０１５０】
【数１５】
クラスNに対する負例閾値tiN(v)：
【０１５１】
【数１６】
なお、式(25)(26)の代わりに以下のように正例閾値tijと負例閾値tiNとが生成されてもよい。
【０１５２】
クラスjに対する正例閾値tij(v):
【０１５３】
【数１７】
クラスNに対する負例閾値tiN(v)：
【０１５４】
【数１８】
閾値決定部２５３は、生成した正例閾値tij(v)と負例閾値tiN(v)とを出力する（ステップＳ２２４）。
【０１５５】
次に、クラス識別部２５４（図９）が、部分集合v(v=1,2,3,…,V)ごとに独立に、正例集合RPijを表すラベルjとラベルなし集合Uiに属する各素性列とを識別モデルMEi(v)に与え、当該ラベルなし集合Uiに属する各素性列が当該ラベルjによって表される正例集合RPijに属することになり易いかということを表す指標である正例指標を当該ラベルなし集合Uiに属する各素性列に対してそれぞれ生成し、当該正例指標と正例閾値tij(v)とを比較する。また、クラス識別部２５４は、部分集合v(v=1,2,3,…,V)ごとに独立に、負例集合RNiを表すラベルNとラベルなし集合Uiに属する各素性列とを識別モデルMEi(v)に与え、当該ラベルなし集合Uiに属する各素性列が負例集合RNiに属することになり易いかということを表す指標である負例指標tiN(v)を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と負例閾値とを比較する。クラス識別部２５４は、これらの比較結果に応じて、部分集合v(v=1,2,3,…,V)ごとに独立に、ラベルなし集合Uiに属する各素性列を正例集合RPi+1jと負例集合RNi+1jとに振り分ける。例えば、クラス識別部２５４は、各v=1,2,…,Vについて、RPi(v), RNi(v), Uiに含まれる素性列xのうち、argmaxj'∈C'p(j'|x)となるクラスj'∈C'がp(j'|x)>tij'(v)を満たす場合に、素性列xをクラスj'に対応する集合に識別する。つまり、j'が正例集合に対応するのであれば正例集合RPi+1j(v)、負例集合に対応するのであれば負例集合RNi(v)に識別される（ステップＳ２２５）。
【０１５６】
次に、統合部２５４ＢがRNi(1),...,RNi(V)とRPij(1),...,RPij(V)(j=1,...,c)とを入力とし、統合部２５４Ｂは、第２判定閾値個以上の正例閾値tij(v)に対して第２判定条件を満たすと判定された指標に対応する素性列を正例集合RPi+1の要素の要素とする。また、統合部２５４Ｂは、第３判定閾値個以上の負例閾値tiN(v)に対して第３判定条件を満たすと判定された指標に対応する素性列を負例集合RNi+1の要素とする。第２、３判定閾値は、例えば、第１判定閾値と同様に設定される。本形態では、判定閾値の選択に応じて、抽出できる正例及び負例の精度や数を調整することができる。また，RPi+1j (j=1,2,…,c)及びRNi+1のいずれにも識別されなかったものが、新たなラベルなし集合Ui+1の要素とされる（ステップＳ２２６）。
【０１５７】
その後、第１実施形態と同様にステップＳ１２６、Ｓ１２７、Ｓ１２８の処理が実行される。
【０１５８】
〔本形態の特徴〕
以上説明したように、第１、２実施形態では、繰り返し処理ごとに識別モデルとスパイ素性列とから閾値を決定し、決定した閾値を用いた判断基準に従って、正例集合、負例集合及びラベルなし集合を更新する。
【０１５９】
これにより、繰り返し処理ごとに変化する識別モデルに応じて適切な閾値を自動的に定めることができ、生成された閾値を用いて正例集合、負例集合及びラベルなし集合を更新することで、信頼度の低い識別結果にひきずられ、間違った方向へ学習が進む問題を解消し、高精度な関係抽出を行うことが可能となる。
【０１６０】
また、広範囲な機械学習方式を利用できるため、単語以外の一般的な識別に有用と思われる素性を利用して識別（関係抽出）を行うことができる。
【０１６１】
さらに、スパイアルゴリズムをマルチクラスへ拡張した手法を利用することにより、負例作成時の恣意性や網羅性、ノイズの問題を削減できる。
【０１６２】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の実施形態では、コーパスが予め素性変換されている例を示したが、正例集合の初期要素を生成した後など、その他のタイミングでコーパスを素性変換してもよい。
【０１６３】
また、上記の実施形態では、最大エントロピー法を用いて学習を行ったが、サポートベクトルマシンなどその他の周知の機械学習方式が用いられてもよい。なお、最大エントロピー法を用いた場合の「与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標」は条件付確率であったが、サポートベクトルマシンを用いた場合の同様の指標は距離となる。
【０１６４】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１６５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１６６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１６７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１６８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１７０】
１，２ データ抽出装置
【技術分野】
【０００１】
この発明は、特定の記号列の組み合わせと関連性がある記号列の組み合わせをテキストから収集するためのデータ抽出技術に関する。
【背景技術】
【０００２】
現在様々な自然言語処理技術の研究開発が進み、WEBのような膨大な知識源から必要な情報を抽出する手法が多く存在している。情報を抽出する上で或る関係に基づいた語の集合をまとめることは有益である。例えば「X=NTT」と「Y=通信」といった語のペアX−Yは、「業態」に対応する集合に属すると考える。以下では、何らかの関係を持った記号列をそれぞれエンティティeX，eYと呼び、それらの組み合わせであるエンティティペアeX,Yの抽出を行う。
【０００３】
このようなエンティティペアの抽出問題を、或る文に含まれる任意のエンティティペアが、特定のエンティティペアと関係を持つか(ω=1)持たないか(ω=0)という識別問題として捉え、最大エントロピー原理(ME)に基づいて任意のエンティティペアがω=1またはω=0のどちらの集合に属するかを識別するための識別モデルを学習することにより、識別問題を解く手法が知られている（非特許文献１）。
【０００４】
具体的には、ω＝１の集合に属するエンティティペア(正例)とω＝0の集合に属するエンティティペア（負例）とを教師ありデータとし、どちらの集合に属するか分かっていないエンティティペアを教師なしデータとする。そして、(1)まず、最初に与えられた教師ありデータを用いた機械学習によって識別モデルを生成して識別器を構成する。(2)次に、上記(1)で得られた識別器を用いて教師なしデータを識別し、正例に対応する集合、負例に対応する集合、又はどちらにも判別できない集合（ラベルなし集合）に振り分ける。(3)次に、上記(2)の振り分けで得られた新たな正例集合、負例集合、及びラベルなし集合を用いた機械学習によって識別モデルを生成して、識別器を更新する。(4)そして、上記(3)で得られた識別器を用いて、上記ラベルなし集合の要素を再度識別して、正例集合、負例集合、及びラベルなし集合を更新する。そして、(3)(4)の処理を学習結果が収束するまで（正例集合と負例集合への振り分け結果が変化しなくなるまで）繰り返し、識別モデルの更新と、正例集合、負例集合、及びラベルなし集合の更新とを行う。
【０００５】
なお、複数の正例集合を考慮する場合は、ω={1，2，…，c, N}のように、c（cは2以上の整数）個の正例集合(ω＝1〜cのc個の集合)と１個の負例集合(ω＝Nの1クラス)との合計c+1個の集合への識別問題（マルチクラス識別問題）へ拡張でき、複数の正例集合についてのエンティティペアを抽出することが可能となる。
【０００６】
上述のような識別問題とみなした場合、特定のエンティティペアと関係を持たないエンティティペアが属する集合(負例集合)をも考慮することになる。この場合、特定のエンティティペアと関係を持つエンティティペアが属する集合(正例集合)のみに基づいて機械学習を行う場合のように意図しない学習方向へ偏向することを抑えることができるが、負例集合に属するエンティティペアの与え方が新たな課題となる。
【０００７】
非特許文献１では、２単語間の関係が記述された巨大な辞書を用いることで、その関係中に存在しない単語を全て負例として用いている。
【０００８】
また、非特許文献２では、スパイアルゴリズムというヒューリスティクスを用いて負例を作成する技術も提案されている。スパイアルゴリズムとは、少量の正例とラベルなし集合の要素とを識別器に与えることで負例の閾値を得る方法である。閾値を得ることができればその閾値を用いて信頼のある負例を選択でき、さらに信頼度の高い識別モデルを学習することができる。
【０００９】
一方、非特許文献３では、互いの関係の薄い集合をペアとして、それらの集合にそれぞれ属するエンティティペアのエンティティを交換することで負例を作成する方法が提案されている。例えば、「NTT-通信」という「業態クラス」と、「バラ-赤」という「花の色」クラスがあった場合、それらのエンティティペアのエンティティを交換し、「NTT-赤」と「バラ-通信」という新たな無関係のエンティティペアを作り、これを負例として用いる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Distant supervision for relation extraction without labeled data (Mintz, M., Bills, S., Snow, R. and Jurafsky, D. 2009)
【非特許文献２】Partially Supervised Classification of Text Documents (Liu, B., Lee, W., Yu, P. and Li, X. 2002)
【非特許文献３】Lightly-Supervised Attribute Extraction (Bellare, K. , Talukdar, P. , Kumaran, G. , Pereira, F. , Liberman, M. , McCallum, A. and Dredze, M. 2007)
【発明の概要】
【発明が解決しようとする課題】
【００１１】
非特許文献１はMEを用いて関係抽出を行うシステムであるが、負例の生成には巨大な辞書が必要となるため、その作成にはコストがかかってしまう。少量のシードで大量のエンティティが抽出できることを目的とする本目的にあって、この辞書作成コストは大きな課題となる。また、非特許文献１の識別モデルは、識別結果の信頼度の高い/低いに関わらず、教師なしデータを何れかの集合に振り分けてしまうため、信頼度の低い識別結果にひきずられ、間違った方向へ識別モデルの学習が進み、識別の精度が低下してしまう可能性がある。この問題を解決するためには、予め定めた信頼度の閾値を超えないエンティティペアについては正例集合（又は負例集合）に割り振らないといった対策を採ることも考えられる。しかし、上述のように、非特許文献１では、学習が収束するまで繰り返し識別モデルを更新していくので、繰り返し毎に識別モデルが変化し、識別結果の信頼度も変わってくる。そのため、閾値も識別モデルに合わせて変化させるべきであるが、各繰り返しでどのくらい識別モデルの信頼度が変化するかは予測できないため、それ考慮して予め繰り返し毎に閾値を与えておくことは難しい。そのため、非特許文献１の方式では、特定の記号列の組み合わせと関連性がある記号列の組み合わせをテキストから精度よく収集することは困難である。
【００１２】
また、非特許文献２は、学習の初期の負例生成方法としてスパイアルゴリズムを用いた先行技術である。これにより、学習の初期の負例集合を作成する際の恣意性やノイズなどの問題は解決できる。また、非特許文献２はEMアルゴリズムの枠組みを用いているため、信頼度がアルゴリズム内部で確率として反映されており、信頼度の低い識別結果にひきずられて間違った方向へ学習が進む問題を解決することができる。しかしながら、非特許文献２の方式には、学習データとして使用可能な素性が単語のみに制限されるという問題がある。例えば「eX,“の”,<PSN>(人物名),“社長”,品詞=助詞(は,が等),eY,“事業”,品詞=助詞」というやや複雑な組成列からなるパターンのように、非特許文献２の方式を、複数の素性から構成される素性列を学習データとする方式に拡張することは難しい。このような複雑な素性列を学習データとし、直接的にEMアルゴリズムの枠組みを用いて識別モデルを求めることは困難だからである。そのため、非特許文献２の方式を用い、多用なテキストから特定の記号列の組み合わせと関連性がある記号列の組み合わせを収集することは困難である。
一方、非特許文献３は、最初に明示的な負例をエンティティの交換によって与えている。このような負例の付与は少なからず恣意的であり、ノイズを含む可能性や、網羅性に欠ける可能性がある。例えば、互いの関係の薄い集合にそれぞれ属するエンティティペアであっても、それらの片方のエンティティが同一である場合がある。このような場合にエンティティペアの片方のエンティティを交換することで負例を作成する方法を採ると再び正例が生成されてしまう。具体例を挙げると、「業態」に対応する集合に属するエンティティペア「NTT-通信」と、「親子会社関係」に対応する集合に属するエンティティペア「NTT-NTT西日本」とのエンティティ「NTT」を交換しても同じものしか得られない。これは似たようなエンティティからなるエンティティペアと関係を持つエンティティペアを集める際にクリティカルな問題となる。
【００１３】
非特許文献１での初期の負例集合の生成に、非特許文献２のスパイアルゴリズムを用いれば、初期の負例集合作成時の恣意性やノイズ、網羅性などの問題は緩和できる。また、非特許文献２の使用できる素性が制限されるという課題は、EMアルゴリズムの代わりに非特許文献１のMEに基づく学習を用いることで解決できる。しかしながら、単に非特許文献１の方式と非特許文献２の方式とを組み合わせただけの方式では、MEに基づく学習結果の信頼度が負例集合の更新処理に反映されないため、学習が誤った方向へ進むという非特許文献１の方式の問題点は解決しない。
【００１４】
本発明はこのような点に鑑みてなされたものであり、機械学習方式にかかわらず、特定の記号列の組み合わせと関連性がある記号列の組み合わせを精度よく収集することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明では、シードエンティティの組み合わせを含むテキストに対応する複数の素性からなる素性列を正例集合の初期要素とし、母集合から正例集合の初期要素を除いた差集合の少なくとも一部の要素をラベルなし集合の初期要素とし、正例集合から選択された要素を初期スパイ素性列とする。また、正例集合に属する素性列と当該素性列が正例集合に属することを表すラベルとの組、及び、ラベルなし集合に属する素性列と当該素性列が負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルを生成する。また、ラベルなし集合を表すラベルと初期スパイ素性列とを初期識別モデルに与え、初期スパイ素性列がラベルなし集合に属することになり易いかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値を決定する。そして、ラベルなし集合を表すラベルとラベルなし集合に属する各素性列とを初期識別モデルに与え、当該ラベルなし集合に属する各素性列がラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該第１指標と第１閾値とを比較することで当該ラベルなし集合に属する各素性列が負例集合に属するか否かを識別し、負例集合に属すると識別された素性列を負例集合の要素とし、母集合から当該負例集合と正例集合とを除いた差集合に相当する集合をラベルなし集合の要素とする。
【００１６】
ここで、第１閾値は初期識別モデルの信頼度を表す指標となるため、第１閾値と第１指標とを比較して負例集合の要素を選択することは、初期識別モデルの信頼度を考慮して負例集合の要素を選択することになる。これにより、機械学習方式にかかわらず、初期識別モデルの信頼度を考慮した負例集合の要素の選択が可能となる。
【００１７】
また、本発明において好ましくは、正例集合から選択された要素を正例スパイ素性列とし、負例集合から選択された要素を負例スパイ素性列とする。また、正例集合に属する素性列と当該素性列が正例集合に属することを表すラベルとの組、及び、負例集合に属する素性列と当該素性列が負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルを生成する。また、正例集合を表すラベルと正例スパイ素性列とを識別モデルに与え、正例スパイ素性列が正例集合に属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値を決定し、さらに、負例集合を表すラベルと負例スパイ素性列とを識別モデルに与え、負例スパイ素性列が負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値を決定する。さらに、正例集合を表すラベルとラベルなし集合に属する各素性列とを識別モデルに与え、当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属することになり易いかということを表す指標である正例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該正例指標と正例閾値とを比較することで当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属するか否かを識別し、当該ラベルによって表される正例集合に属すると識別された素性列を当該ラベルによって表される正例集合の要素に追加し、負例集合を表すラベルとラベルなし集合に属する各素性列とを識別モデルに与え、当該ラベルなし集合に属する各素性列が負例集合に属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と負例閾値とを比較することで当該ラベルなし集合に属する各素性列が負例集合に属するか否かを識別し、負例集合に属すると識別された素性列を負例集合の要素に追加し、母集合から当該負例集合と正例集合とを除いた差集合に相当する集合を新たなラベルなし集合とする。
【００１８】
ここで、正例閾値や負例閾値は識別モデルの信頼度を表す指標となるため、正例閾値と正例指標とを比較して正例集合の要素を選択し、負例閾値と負例指標とを比較して負例集合の要素を選択することは、識別モデルの信頼度を考慮して負例集合や正例集合の要素を選択することになる。これにより、機械学習方式にかかわらず、識別モデルの信頼度を考慮した負例集合や正例集合の要素の選択が可能となる。
【発明の効果】
【００１９】
以上により、本発明では、機械学習方式にかかわらず、特定の記号列の組み合わせと関連性がある記号列の組み合わせを精度よく収集することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】図１は、第１実施形態のデータ抽出装置の構成を説明するための図である。
【図２】図２は、図１の識別学習部の詳細を説明するための図である。
【図３】図３は、図１の識別学習部の詳細を説明するための図である。
【図４】図４は、第１実施形態のデータ抽出方法を説明するための図である。
【図５】図５Ａは、テキストを例示するための図である。図５Ｂは、エンティティペアを例示するための図である。
【図６】図６は、素性列を説明するための図である。
【図７】図７は、第２実施形態のデータ抽出装置の構成を説明するための図である。
【図８】図７は、図７の識別学習部の詳細を説明するための図である。
【図９】図８は、図７の識別学習部の詳細を説明するための図である。
【図１０】図１０は、第２実施形態のデータ抽出方法を説明するための図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施形態を説明する。
【００２２】
〔定義〕
まず、本形態で使用する用語を定義する。
【００２３】
［テキスト］テキストとは２以上の記号からなる記号列を意味する。テキストの具体例は、文などの文字列、プログラムコード列、遺伝子の塩基配列を表す記号列などである。以下では、テキストとして文を取り扱う場合を例示する。
【００２４】
［エンティティ］エンティティとは記号列を意味する。エンティティの具体例は、単語や固有名詞などの文字列、プログラムコード、塩基を表す記号などである。以下では、エンティティとして固有名詞を取り扱う場合を例示する。
【００２５】
［エンティティの組み合わせ］エンティティの組み合わせとは、２以上のエンティティの組み合わせを意味する。以下では、エンティティの組み合わせとして２つのエンティティの組み合わせであるエンティティペアを取り扱う場合を例示する。
【００２６】
［シードエンティティ］シードエンティティとは、予め定められた特定のエンティティ（記号列）を意味する。
【００２７】
［シードエンティティの組み合わせ］シードエンティティの組み合わせとは、２以上のシードエンティティの組み合わせを意味する。以下では、シードエンティティの組み合わせとして２つのシードエンティティの組み合わせであるシードエンティティペアを取り扱う場合を例示する。
【００２８】
［素性］素性とは、解析に用いられる最小単位である。素性はテキストを素性変換して得られ、テキストは複数の素性に対応する。各素性はテキストを構成する各記号列に対応する。素性の具体例は、テキストが含む各単語のエンティティからの相対位置をそれぞれ表す表層素性、テキストが含む各単語の品詞情報を表す品詞素性、テキストが含む各固有名詞情報を表す固有名詞素性、テキストが含む各単語の構文情報を表す構文素性、テキストのエンティティの出現回数を表す素性、エンティティの組み合わせ（エンティティペアなど）の共起回数を表す素性などである。
【００２９】
例えば、エンティティペアを(eX, eY)=(NTT, 通信)とするテキスト「NTT／は／通信／業務／を／主体／と／する／」を素性変換した場合、以下のような素性が得られる。
【００３０】
・表層素性の場合：「eX−1=EOS」，「eX+1=“は”」，「eX+2=eY」
ここで、ex-mはエンティティexのm単語前の単語、ex+mはエンティティexのm単語後ろの単語、EOSはその部分に単語が存在しない（文の先頭を越えている）ことを表す。
【００３１】
・品詞素性：「eX+1=助詞」，「eX+3=名詞」
・固有名詞素性：「eX=組織名」
・構文素性：「eXの階層=eYの階層」(両方とも「する」に係る)
以下では、表層素性を用いる場合を例にとって説明する。
【００３２】
［素性列］：素性列とは、或るテキストに対応する複数の素性からなる情報を意味する。
【００３３】
［母集合］母集合とは、素性列を要素とする集合を意味する。以下では、コーパスが含む各テキストに対応する複数の素性からなる素性列を要素とする集合を母集合とする場合を例示する。
【００３４】
［正例集合］正例集合とは、母集合のうち、シードエンティティの組み合わせと関連性があると識別された素性列を要素とする集合を意味する。
【００３５】
［負例集合］負例集合とは、シードエンティティの組み合わせと関連性がないと識別された素性列を要素とする集合を意味する。
【００３６】
［ラベルなし集合］ラベルなし集合とは、シードエンティティの組み合わせとの関連性が識別されていない素性列を要素とする集合を意味する。
【００３７】
［クラス］クラスとは、集合に対応する分類を意味する。
【００３８】
〔第１実施形態〕
本発明の第１実施形態を説明する。
【００３９】
＜構成＞
図１に例示するように、本形態のデータ抽出装置１は、記憶部１１０，１２０，１３０と識別学習部１４０，１５０と停止条件判定部１６０と選択部１７０を有する。図２に例示するように、識別学習部１４０は、初期正例集合作成部１４１と初期ラベルなし集合作成部１４２とスパイ作成部１４３と学習部１４４と閾値決定部１４５とクラス識別部１４６とを有する。図３に例示するように、識別学習部１５０は、スパイ作成部１５１と、学習部１５２と、閾値決定部１５３と、クラス識別部１５４とを有する。
【００４０】
なお、本形態のデータ抽出装置１は、例えば、CPU(central processing unit)、RAM(random-access memory)などから構成される公知又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される特別な装置である。すなわち、記憶部１１０，１２０，１３０は、例えば、ハードディスク装置、半導体メモリなどの公知の記憶手段からなり、識別学習部１４０，１５０や停止条件判定部１６０や選択部１７０は、例えば、CPUに所定のプログラムが読み込まれて実行されることで構成される処理手段からなる。また、識別学習部１４０，１５０や停止条件判定部１６０や選択部１７０の少なくとも一部が集積回路などのハードウェアによって構成されてもよい。
【００４１】
＜処理＞
次に、本形態の処理を説明する。
【００４２】
［前提］
本形態では、１又は複数のクラスが設定され、クラスごとに正例集合が対応するものとする。クラスからなる集合をC={1,2,…,c}と表す。cはクラスの総数を表す１以上の整数であり、j=1,...,cは各クラスを表すラベル(クラスID)である。ラベルは整数値に限られるものではなく、各クラスを識別できるものであれば文字列や記号などでも良い。なお、「ラベルがjのクラス」のことを「クラスj」と表現する。また、負例集合に対応するラベルをNで表す。また、正例集合に対応するラベルと負例集合に対応するラベルとの集合をC'={1,2,…,c,N}で表す。
【００４３】
予め形態素解析、固有表現抽出、係り受け解析が行われた文区切りのテキストの集合であるコーパスが記憶部１１０（図１）に格納される。本形態のコーパスを構成する各テキストは予め素性変換されており、当該コーパスは、テキストに対応する素性列を要素とする母集合Dとされる。前述のように、本形態では素性として表層素性を用いる。本形態の素性列は、対応するエンティティペアに対応付けられているものとする。このような母集合Dは、予め記憶部１１０（図１）に格納される。
【００４４】
また、本形態では、シードエンティティの組み合わせであるシードエンティティペア(eX, eY)がクラスjごとに設定され、シードエンティティペアの集合をPS={PS1,...,PSc}と表現する。ここで、PSjは、クラスjにおけるシードエンティティペアの集合を表す。シードエンティティペアの集合PSは、予め記憶部１２０に格納される。
【００４５】
［データ抽出処理］
まず、識別学習部１４０の初期正例集合作成部１４１（図２）が、記憶部１２０から抽出したシードエンティティペアの集合PSを用い、記憶部１１０に格納された母集合Dから抽出した素性列を初期要素とする正例集合RP0j (j=1,...,c)を生成する。なお、正例集合RPijはi回更新されたクラスjに対応する正例集合を表し、正例集合RPijの集合をRPi={RPi1,...,RPij}と表す。ステップＳ１１１ではi=0であり、正例集合RP0jの集合RP0が生成される。例えば、本形態の初期正例集合作成部１４１は、各正例クラスj∈Cについて、シードエンティティペアの集合Psj中のシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RPijの初期要素とし、正例集合RP0jの集合RP0={RP01,...,RP0j}を生成する。
【００４６】
本形態では、各RP0j(j=1,2,…,c)及びRP0は以下の(A)及び(B)の条件を満たすものとする。
【００４７】
(A) 各RP0j(j=1,2,…,c)には１以上の素性列が含まれていること。
【００４８】
(B) RP0に含まれる素性列の総数はc+1以上であること。
【００４９】
条件(A)を満たしていない場合、初期正例集合作成部１４１は、以下のいずれかの方法によって、条件(A)を満たすように調整を行う。
【００５０】
(方法1)初期正例集合作成部１４１は、RP0jに１つも素性列が含まれていないクラスjについて、新しいシードエンティティペアの追加を要求し、追加されたシードエンティティペアをP0jに追加して記憶部１２０に格納する。初期正例集合作成部１４１は、追加されたシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RP0jの要素に加える。このような処理が、各クラスjにそれぞれ対応するRP0jに含まれる素性列がそれぞれ１以上になるまで繰り返される。
【００５１】
(方法2)RP0jに１つも文が含まれていないクラスjを削除し、(A)の条件を満たすクラスのみが存在するものとして、以下の処理を進める。
【００５２】
条件(B)を満たしていない場合、初期正例集合作成部１４１は、何れかのクラスj∈Cについての新しいシードエンティティペアの追加を要求し、追加されたシードエンティティペアP0jに追加して記憶部１２０に格納する。初期正例集合作成部１４１は、追加されたシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RP0jの要素に加える。このような処理が条件(B)を満たすまで繰り返される。
【００５３】
初期正例集合作成部１４１は、以上の処理によって生成した正例集合RP0jの集合RP0={RP01,...,RP0j}を記憶部１３０に格納する（ステップＳ１１１）。
【００５４】
次に、初期ラベルなし集合作成部１４２（図２）が、記憶部１１０に格納された母集合Dから記憶部１３０に格納された正例集合RP0jの集合RP0の要素を除いた差集合D-RP0の少なくとも一部の要素を、ラベルなし集合U0の初期要素とする。例えば、初期ラベルなし集合作成部１４２は、集合RP0が含む何れか素性列と素性が１個以上マッチする素性列を差集合D-RP0から抽出し、抽出した素性列をラベルなし集合U0の初期要素とする（ステップＳ１１２）。
【００５５】
次に、スパイ作成部１４３（図２）が、記憶部１３０に格納された正例集合RP0jの集合RP0から選択された要素を初期スパイ素性列とする。例えば、スパイ作成部１４３は、記憶部１３０に記憶された正例集合RP0jの集合RP0全体から、予め定めた任意の割合rに従ってランダムに選択した要素を初期スパイ素性列の集合spy0={spy01，…，spy0c}とし、記憶部１３０に格納する。ここでspy0jは、クラスjに対応する初期スパイ素性列の集合である。ただし、本形態では、正例集合RP0全体から最低でも１つの要素が初期スパイ素性列として選択されるものとする。また、本形態の場合、要素が１つしか存在しない正例集合RP0jについては初期スパイ素性列が抽出されないものとする。以下のように、本形態では正例集合RP0jから初期スパイ素性列の集合spy0jを除いたものを学習データとして用いるからである。
【００５６】
スパイ作成部１４３は、生成した初期スパイ素性列の集合spy0={spy01，…，spy0c}を記憶部１３０に格納する（ステップＳ１１３）。
【００５７】
次に、学習部１４４が、各正例集合RP0j (j=1,...,c)に属する素性列と当該素性列が正例集合RP0jに属することを表すラベルjとの組、及び、初期ラベルなし集合作成部１４２で生成されたラベルなし集合U0に属する素性列と当該素性列がラベルなし集合U0に属することを表すラベルUとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルME0を生成する。本形態では、機械学習方式として、例えば、最大エントロピー原理に基づく識別学習（ME学習）方式を用いる（参考文献１参照）。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【００５８】
［参考文献１］A maximum entropy approach to natural language processing (Berger, A. L., Pietra, V. J. D. and Pietra, S. A. D. 1996)
【００５９】
この例の場合、学習部１４４は、例えば、各クラスj(j∈C)における各正例集合RP0j (j=1,...,c)から、当該クラスjに対応する初期スパイ素性列の集合spy0jを差し引いた差集合（RP0j−spy0j）とラベルjとの組、及び、ラベルなし集合U0と初期スパイ素性列の集合spy0との和集合（U0+spy0）とラベルUとの組を学習データとして用い、最大エントロピー原理に基づく識別学習により、差集合（RP0j−spy0j）の要素をxとした場合の条件付確率p(j｜x)と和集合（U0+spy0）の要素をxとした場合の条件付確率p(U｜x)とに対応するエントロピーを最大化する初期識別モデルME0を生成する。すなわち、学習部１４４は、例えば、x∈(RP0j−spy0j)とy=j (j=1,...,c)との組、及び、x∈(U0+spy0)とy=Uとの組を学習データとして用い、条件付確率
【００６０】
【数１】
に対するエントロピー
【００６１】
【数２】
を最大化する各パラメータλqに対応するPλ(y|x)であるP(y|x)を初期識別モデルME0とする。ただし、
【００６２】
【数３】
であり、qは各学習データ(x,y)の組にそれぞれ対応するラベルであり、p'(x)は学習データ(x,y)におけるxの出現頻度であり、fq(x,y)はqに対応する素性関数(feature function)である。
【００６３】
なお、上述学習処理の変形例として、x∈(U0+spy0)とy=Uとの組の代わりにx∈U0とy=Uとの組を学習データとして用いてもよい。
【００６４】
学習部１４４は、生成した初期識別モデルME0を記憶部１３０に格納する（ステップＳ１１４）。
【００６５】
次に、閾値決定部１４５（図２）が、ラベルなし集合U0に対応するラベルUと記憶部１３０に格納された初期スパイ素性列の集合spy0に属する初期スパイ素性列とを初期識別モデルME0に与え、初期スパイ素性列がラベルなし集合U0に属することになり易いか、逆に言うと正例集合RP0に属しにくいかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値t0Nを決定する。本形態の閾値決定部１４５は、例えば、初期識別モデルME0を用い、初期スパイ素性列の集合spy0に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の最大値
【００６６】
【数４】
を第１閾値t0Nとする。
【００６７】
また、式(4)の代わりに、初期スパイ素性列の集合spy0に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の平均値
【００６８】
【数５】
を第１閾値t0Nとしてもよい。
【００６９】
さらに、第１閾値t0Nに加えて、初期スパイ素性列の集合spy0に属する初期スパイ素性列spyとラベルjとに対する条件付確率P(j|spy)の平均値
【００７０】
【数６】
を閾値t0jとして求めてもよい。
【００７１】
閾値決定部１４５は、以上のように生成した第１閾値t0N（及び閾値t0j）を記憶部１３０に格納する（ステップＳ１１５）。
【００７２】
次に、クラス識別部１４６（図２）が、ラベルなし集合U0を表すラベルUとラベルなし集合U0に属する各素性列とを初期識別モデルME0に与え、当該ラベルなし集合U0に属する各素性列がラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合U0に属する各素性列に対してそれぞれ生成し、当該第１指標と第１閾値t0Nとを比較することで当該ラベルなし集合U0に属する各素性列が負例集合RN1に属するか否かを識別し、負例集合RN1に属すると識別された素性列を負例集合RN1の要素とし、母集合Dから当該負例集合RN1と正例集合RP0j (j=1,...,c)とを除いた差集合(D-RN1-RP0j) (j=1,...,c)に相当する集合をラベルなし集合U1の要素とする。例えば、クラス識別部１４６は、閾値決定部１４５で決定された各閾値と学習部１４４で生成された初期識別モデルME0とを用い、ラベルなし文集合U0に含まれる素性列uのうち、
p(U｜u)>t0N …(7)
を満たすものを負例集合RN1に属すると識別し、負例集合RN1に属すると識別された素性列を負例集合RN1の要素とする。また、例えば、クラス識別部１４６は、正例集合RP0j (j=1,...,c)をそのまま正例集合RP1j (j=1,...,c)とし、RP1=｛RP11，…，RP1C｝とする。また、例えば、クラス識別部１４６は、ラベルなし集合U0に含まれる素性列のうち負例集合RN1の要素と識別されなかった素性列の集合U0−RN1と、ラベルなし文集合検索部１４２において、母集合Dに含まれる素性列のうちラベルなし集合U0として検索されなかった素性列の集合D−RP0−U0の和、すなわちD−RP1−RN1を新たなラベルなし文集合U1として作成する。
【００７３】
なお、閾値決定部１４５で閾値t0j (j=1,...,c)が生成される場合には、正例集合RP0j (j=1,...,c)をそのまま正例集合RP1j (j=1,...,c)とする代わりに、ラベルなし文集合U0に含まれる素性列uのうち、
p(j｜u)>t0j …(8)
を満たすものを正例集合RP1j (j=1,...,c)に属すると識別し、正例集合RP1j (j=1,...,c)に属すると識別された素性列をそれぞれ正例集合RP1j (j=1,...,c)の要素としてもよい（ステップＳ１１６）。
【００７４】
次に、停止条件判定部１６０（図１）がi=1に設定する（ステップＳ１２１）。
【００７５】
次に、識別学習部１５０のスパイ作成部１５１（図３）が、正例集合RPij(j=1,...,c)から選択された要素を正例スパイ素性列とし、負例集合RNiから選択された要素を負例スパイ素性列とする。ラベルjに対応する正例スパイ素性列の集合をspyijで表し、負例スパイ素性列の集合をspyiNで表す。例えば、スパイ作成部１５１は、正例集合RPij(j=1,...,c)及び負例集合RNi中から，予め定めた任意の割合rに従ってランダムに正例スパイ素性列及び負例スパイ素性列を選択し、スパイ素性列の集合spyi=｛spyi1,…,spyic,spyiN｝を生成する。スパイ作成部１５１は、生成したスパイ素性列の集合spyiを記憶部１３０に格納する（ステップＳ１２２）。
【００７６】
次に、学習部１５２（図３）が、正例集合RPij (j=1,...,c)に属する素性列と当該素性列が正例集合に属することを表すラベルjとの組、及び、負例集合RN1に属する素性列と当該素性列が負例集合RNiに属することを表すラベルNとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルMEiを生成する。ここでの機械学習は、前述のステップＳ１１４と同様に行う。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【００７７】
例えば、学習部１５２は、各クラスj(j∈C)における各正例集合RPij (j=1,...,c)から、当該クラスjに対応する正例スパイ素性列の集合spyijを差し引いた差集合（RPij−spyij）(j=1,...,c)とラベルj(j=1,...,c)との組、負例集合RNiから負例スパイ素性列の集合spyiNを差し引いた差集合（RNi−spyiN）とラベルNとの組、及び、ラベルなし集合Uiとスパイ素性列の集合spyiとの和集合（Ui+spyi）とラベルUとの組を学習データとして用い、前述した最大エントロピー原理に基づく識別学習により（式(1)-(3)）、前述したようなP(y|x)を求め、これを識別モデルMEiとする。なお、ラベルUはラベルなし集合Uiを表すラベルである。
【００７８】
また、上述学習処理の変形例として、和集合（Ui+spyi）とラベルUとの組との代わりにUiとラベルUとの組を学習データとして用いてもよい。また、和集合（Ui+spyi）とラベルUとの組やUiとラベルUを学習データとして用いないことにしてもよい。
【００７９】
学習部１５２は、生成した識別モデルMEiを記憶部１３０に格納する（ステップＳ１２３）。
【００８０】
次に、閾値決定部１５３（図３）が、少なくとも、正例集合RPijを表すラベルj(j=1,...,c)と記憶部１３０に格納された正例スパイ素性列（spyijの要素）とを識別モデルMEiに与え、正例スパイ素性列が正例集合RPijに属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値tij(j=1,...,c)を決定する。さらに、閾値決定部１５３は、負例集合RNiを表すラベルNと記憶部１３０に格納された負例スパイ素性列（spyijの要素）とを識別モデルMEiに与え、負例スパイ素性列が負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値tiNを決定する。本形態の閾値決定部１５３は、例えば、識別モデルMEiを用い、スパイ素性列の集合spy0に属するスパイ素性列spyとラベルj=1,2,…,cとNとUとを用い、以下のように正例閾値tij(j=1,...,c)と負例閾値tiNとラベルなし閾値tiUとを生成する。なお、minαはαの最小値を表す。
【００８１】
クラスjに対する正例閾値tij:
【００８２】
【数７】
クラスNに対する負例閾値tiN：
【００８３】
【数８】
ラベルなしクラスに対する閾値:
【００８４】
【数９】
なお、式(9)(10)の代わりに以下のように正例閾値tijと負例閾値tiNとが生成されてもよい。
【００８５】
クラスjに対する正例閾値tij:
【００８６】
【数１０】
クラスNに対する負例閾値tiN：
【００８７】
【数１１】
また、ラベルなし閾値tiUを用いないことにしてもよい（ステップＳ１２４）。
【００８８】
次に、クラス識別部１５４（図３）が、正例集合RPijを表すラベルjとラベルなし集合Uiに属する各素性列とを識別モデルMEiに与え、当該ラベルなし集合Uiに属する各素性列が当該ラベルjによって表される正例集合RPijに属することになり易いかということを表す指標である正例指標を当該ラベルなし集合Uiに属する各素性列に対してそれぞれ生成し、当該正例指標と正例閾値とを比較することで当該ラベルなし集合Uiに属する各素性列が当該ラベルjによって表される正例集合RPi+1jに属するか否かを識別し、当該ラベルjによって表される正例集合RPi+1jに属すると識別された素性列を当該ラベルjによって表される正例集合RPi+1jの要素に追加する。また、クラス識別部１５４は、負例集合RNiを表すラベルNとラベルなし集合Uiに属する各素性列とを識別モデルMEiに与え、当該ラベルなし集合Uiに属する各素性列が負例集合RNiに属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と負例閾値とを比較することで当該ラベルなし集合Uiに属する各素性列が負例集合RNi+1に属するか否かを識別し、負例集合RNi+1に属すると識別された素性列を負例集合RNi+1の要素に追加する。さらに、クラス識別部１５４は、母集合Dから当該負例集合RNiと正例集合RPij(j=1,...,c)とを除いた差集合に相当する集合を新たなラベルなし集合Ui+1とする。本形態のクラス識別部１５４は、例えば、閾値決定部１５３で決定された各閾値と学習部１５２で生成された識別モデルMEiとを用い、以下のような識別処理を行う。
【００８９】
ラベルなし集合Uiに含まれる素性列xについて、
(I) p(U|x)<tiU である。
【００９０】
(II)全てのj'∈C'(C'={1,...,c,N})のうちp(j'|x)を最大にするクラスj'についてp(j'|x)>tijである。
の両方の条件を満たす場合には当該素性列xがクラスj'に対応する正例集合RPi+1j又は負例集合RNi+1に属すると識別し、当該素性列xを正例集合RPi+1j又は負例集合RNi+1の要素とする。一方、(I)(II)の少なくとも一方を満たさない場合には、当該素性列xがラベルなし集合Ui+1に属すると識別し、当該素性列xをラベルなし集合Ui+1の要素とする。ラベルなし集合Uiに含まれる各素性列xは、新たな正例集合RPi+1j、負例集合RNi+1又はラベルなし集合Ui+1のいずれかに識別される。
【００９１】
クラス識別部１５４は、更新した正例集合RPi+1j、負例集合RNi+1及びラベルなし集合Ui+1を記憶部１３０に格納する（ステップＳ１２５）。
【００９２】
次に、停止条件判定部１６０（図１）が、予め定められた停止条件を満たすか否かを判定する。本形態の停止条件判定部１６０は、例えば、ラベルなし集合Ui中の素性列が新たに正例集合RPi+1j若しくは負例集合RNi+1に割り当てられなかった場合、又は、ラベルなし集合Uiが空集合となった場合には停止条件を満たさないと判定し、そうでない場合には停止条件を満たすと判定する（ステップＳ１２６）。ここで、停止条件を満たさないと判定された場合、停止条件判定部１６０は、i+1を新たなiとおき（ステップＳ１２７）、処理をステップＳ１２２に戻す。これにより、停止条件判定部１６０は、スパイ作成部１５１の処理と学習部１５２の処理と閾値決定部１５３の処理とクラス識別部１５４の処理とを再び実行させる。一方、停止条件を満たすと判定された場合、以下のステップＳ１２８の処理に進む。
【００９３】
ステップＳ１２８では、選択部１７０（図１）が、記憶部１３０に格納された正例集合RPi+1jと最後の識別モデルMEiとを用い、正例集合RPi+1jから素性列を選択する。本形態の選択部１７０は、正例集合RPi+1jを表すラベルjと正例集合RPi+1jに属する素性列とを識別モデルMEiに与え、正例集合RPi+1jに属する素性列がラベルjに対応する正例集合RPi+1jに属することになり易いかということを表す指標を生成し、当該指標を基準として正例集合RPi+1jから素性列を選択する。例えば、選択部１７０は、最後に得られた識別モデルMEiを各クラスjにおける正例集合RPi+1jに属する各素性列xに適用し、条件付確率p(j|x)の高い順に正例集合RPi+1jに属する各素性列xをソートし、ソートした各素性列xのうち上位K個（Kは予め定められたクラスごとに抽出すべきエンティティペアの数）の素性列を選択する。選択部１７０は、選択した素性列に対応するエンティティペアを出力する。ただし、出力しようとするエンティティペアがそれまでに出力したものと重複する場合には、そのような重複するエンティティペアを出力しないことにしてもよい。
【００９４】
また、このような処理の代わりに、選択部１７０が、正例集合RPi+1jを表すラベルjと正例集合RPi+1jに属する素性列が含む素性の組み合わせとを識別モデルMEiに与え、当該素性の組み合わせが正例集合RPi+1jに属することになり易いかということを表す指標を生成し、当該基準として、正例集合RPi+1jに属する素性列から素性の組み合わせを選択してもよい。例えば、選択部１７０が、条件付確率p(j|x)を基準として素性列単位でソートを行う代わりに、最後に得られた識別モデルMEiを各クラスjにおける正例集合RPi+1jに属する各素性列xに対応するエンティティペアeに適用し、条件付確率p(j|e)の高い順に正例集合RPi+1jに属する各素性列x対応するエンティティペアeをソートし、ソートした各エンティティペアeのうち上位K個（Kは予め定められたクラスごとに抽出すべきエンティティペアの数）のエンティティペアを選択してもよい。この場合、選択部１７０は、選択したエンティティペアを出力する（ステップＳ１２８）。
【００９５】
＜具体例＞
次に、具体例を用いて本形態の処理を説明する。
【００９６】
以下では、母集合Dに含まれる素性列を図５Ａに例示するu1,...,u11とする。なお、図５Ａでは、各u1,...,u11とそれらに対応する各テキストとが対応付けられている。また、図５Ａのテキストを構成する単語のうち下線で示した単語はエンティティである。また、業態クラス(j=1)〉及び〈社長クラス(j=2)〉の２クラスにそれぞれ対応する２つの正例集合RPi+1jが存在し、シードエンティティペアの集合PS={PS1,PS2}として図５ＢのPs1とPs2が与えられているとする。また、素性列u1,...,u11は、それぞれ、対応するテキストに対して図６のような素性変換（簡単のためexの表層素性のみに注目している）を行って得られたものであるとする。
【００９７】
この場合、ステップＳ１１１では、初期正例集合作成部１４１が、図５ＢのPs1，Ps2に対して図５Ａのu1,...,u11に対応する各テキストを検索するので、以下の正例集合RP0={RP01, RP02}が生成される。
【００９８】
RP01={u1, u3} …(14)
RP02={u5, u6, u9} …(15)
また、ステップＳ１１２では、上記RP0に含まれる素性列と、母集合Dの残りの素性列(D-RP0)について
u1と素性値が1つ以上一致する素性列：u2, u4, u7, u8, u10
u3と素性値が1つ以上一致する素性列：u2, u4, u7, u8, u10
u5と素性値が1つ以上一致する素性列：u4, u11
u6と素性値が1つ以上一致する素性列：u2, u4, u7, u8
u9と素性値が1つ以上一致する素性列：u2, u4, u7, u8, u11
であるため、初期ラベルなし集合作成部１４２が、ラベルなし集合
U0={u2, u4, u7, u8，u10，u11}
を生成する。
【００９９】
また、ステップＳ１１３では、スパイ作成部１４３が、
spy01={u1}
spy02={u6}
を初期スパイ素性列の集合として選択したと仮定する。
【０１００】
すると、ステップＳ１１４では、学習部１４４が、
RP01-spy01={u3}
RP02-spy02={u5, u9}
U0+spy0={u1, u2, u4, u6, u7, u8，u10，u11}
を用いて機械学習を行い、識別モデルME0を作成する。
【０１０１】
作成した識別モデルME0に基づいて、各初期スパイ素性列u1,u6のラベルUへの条件付確率を計算した結果が
p(U|u1)=0.15
p(U|u6)=0.3
であるとすると、ステップＳ１１５で閾値決定部１４５が決定する閾値t0Nはmax[p(U|u1),p(U|u6)]=0.3となる。
【０１０２】
次に、ステップＳ１１６において、クラス識別部１４６が、U0={u2, u4, u7, u8，u10，u11}の各素性列の識別を行う。各素性列u3, u4, u7, u11のラベルUへの条件付確率を計算した結果が
p(U|u2)=0.1
p(U|u4)=0.2
p(U|u7)=0.2
p(U|u8)=0.25
p(U|u10)=0.7
p(U|u11)=0.8
とすると、閾値t0N=0.3を超えるu10, u11が負例集合に識別されるので、
RN1={u10, u11}
となり、
U1={u2, u4, u7, u8}
RP1={u1, u3, u5, u6, u9}
となる。
【０１０３】
次に、ステップＳ１２２で、スパイ作成部１５１が、i=1に対して
spy11={u3}
spy12={u9}
spy1N={u10}
をスパイ素性列として選択したとする。
【０１０４】
続いて、ステップＳ１２３で、学習部１５２が、RP11-spy11,RP12-spy12,RN1-spy1N, U1+spy1を用いて識別モデルME1を学習する。
【０１０５】
クラスj=1, j=2及びクラスNについてはスパイ素性列が１つずつしか存在しないため、ステップＳ１２４で、閾値決定部１５３が、
t1j=1=p(j=1|u3)=0.55
t1j=2=p(j=2|u9)=0.6
t1N=p(N|u10)=0.6
を設定する。
【０１０６】
また、閾値t１Uはp(U|u3) , p(U|u9), p(U|u10)のうちの最大値を取り、t１U=0.3だったと仮定する。
【０１０７】
次のステップＳ１２５において、クラス識別部１５４が、U1={u2, u4, u7, u8}が含む各素性列の識別を行う。素性列u2について条件付確率を計算した結果が以下のようになっているとする。
【０１０８】
p(j=1|u2)=0.7
p(j=2|u2)=0.05
p(N|u2)=0.1
p(U|u2)=0.15
ここで、p(U|u2)はt１U=0.6より小さく、argmaxj∈C p(j|u2)とするクラスj=1において、p(j=1|u2)=0.7 ＞ t１1(=0.55)なので、素性列u2はクラス1の正例集合RP21に識別される。
【０１０９】
同様に素性列u4，u7, u8∈U1について条件付確率を計算した結果を
p(j=1|u4)=0.1
p(j=2|u4)=0.7
p(N|u4)=0.1
p(U|u4)=0.1
p(j=1|u7)=0.7
p(j=2|u7)=0.1
p(N|u7)=0.15
p(U|u7)=0.05
p(j=1|u8)=0.25
p(j=2|u8)=0.4
p(N|u8)=0.15
p(U|u8)=0.2
とすると、素性列u4はクラス2の正例集合RP22に、素性列u7はクラス1の正例集合RP21に識別される。一方、素性列u8はargmaxj∈C p(j|u8)となるクラスはj=2であるが、p(c2|u8)=0.4 ＞ t１2(=0.6)であるため、PR22には識別されず、ラベルなし集合U2へ識別される。このように閾値を設けることで、学習部１５２で作成した識別モデルME1に基づく識別結果を訂正することができる。よって、
RP21＝{u1, u2, u3, u7}
RP22＝{u4, u5, u6, u9}
RN2={u10, u11}
U2={u8}
となる。
【０１１０】
ここでは、新たにU1中の文u2，u4，u7がRP21, RP22又はRN2に割り当てられているため、ステップＳ１２６で停止条件判定部１６０は、i+1を新たなiとおいて（ステップＳ１２７）、ステップＳ１２２の処理に戻すように制御する。それにより、新たにRP2,RN2,U2に対してステップＳ１２２〜Ｓ１２６の処理が繰り返される。
【０１１１】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態では、各クラスに対応する各正例集合、負例集合及びラベルなし集合をそれぞれV個（Vは予め設定された2以上の整数）の部分集合に分割し、部分集合ごとに閾値を定めてラベルなし集合の要素を識別し、その識別結果を統合して各正例集合、負例集合及びラベルなし集合の更新処理を行う。以下では、第１実施形態との相違点を中心に説明、第１実施形態と共通する部分については説明を省略する。また、第１実施形態と同一の処理部やステップについては、第１実施形態と同じ参照番号を付して説明を省略する。
【０１１２】
＜構成＞
図７に例示するように、本形態のデータ抽出装置２は、記憶部１１０，１２０，１３０と識別学習部２４０，２５０と停止条件判定部１６０と選択部１７０を有する。図８に例示するように、識別学習部２４０は、初期正例集合作成部２４１と初期ラベルなし集合作成部１４２とスパイ作成・分割部２４３と学習部２４４と閾値決定部２４５とクラス識別部２４６とを有する。クラス識別部２４６は、閾値判定部２４６Ａと統合部２４６Ｂとを有する。図９に例示するように、識別学習部２５０は、スパイ作成・分割部２５１と、学習部２５２と、閾値決定部２５３と、クラス識別部２５４とを有する。また、クラス識別部２５４は、閾値判定部２５４Ａと統合部２５４Ｂとを有する。
【０１１３】
なお、本形態のデータ抽出装置２は、例えば、CPU、RAMなどから構成される公知又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される特別な装置である。また、識別学習部２４０，２５０や停止条件判定部１６０や選択部１７０の少なくとも一部が集積回路などのハードウェアによって構成されてもよい。
【０１１４】
＜処理＞
次に、本形態の処理を説明する。
【０１１５】
［前提］
第１実施形態と同じである。
【０１１６】
［データ抽出処理］
まず、識別学習部２４０の初期正例集合作成部２４１（図８）が、記憶部１２０から抽出したシードエンティティペアの集合PSを用い、記憶部１１０に格納された母集合Dから抽出した素性列を初期要素とする正例集合RPijの集合をRPi={RPi1,...,RPij}を生成する。ただし、第１実施形態と異なり、各RP0j(j=1,2,…,c)及びRP0は以下の(A)及び(B)の条件を満たすものとする。
【０１１７】
(A-2) 各RP0j(j=1,2,…,c)にはV以上の素性列が含まれていること。
【０１１８】
(B-2) RP0に含まれる素性列の総数はVc+V以上であること。
【０１１９】
条件(A-2)を満たしていない場合、初期正例集合作成部２４１は、以下のいずれかの方法によって、条件(A-2)を満たすように調整を行う。
【０１２０】
(方法1-2)初期正例集合作成部２４１は、RP0jに含まれる素性列の数がV未満のクラスjについて、新しいシードエンティティペアの追加を要求し、追加されたシードエンティティペアをP0jに追加して記憶部１２０に格納する。初期正例集合作成部２４１は、追加されたシードエンティティペアに含まれる２エンティティ(eX，eY)を両方含むテキストに対応する素性列を母集合Dから抽出し、それを正例集合RP0jの要素に加える。このような処理が、各クラスjにそれぞれ対応するRP0jに含まれる素性列がそれぞれV以上になるまで繰り返される。
【０１２１】
(方法2-2)RP0jに含まれる素性列がV未満のクラスjを削除し、(A-2)の条件を満たすクラスのみが存在するものとして、以下の処理を進める。
【０１２２】
条件(B-2)を満たしていない場合の処理は第１実施形態と同様である。
【０１２３】
初期正例集合作成部２４１は、以上の処理によって生成した正例集合RP0jの集合RP0={RP01,...,RP0j}を記憶部１３０に格納する（ステップＳ２１１）。
【０１２４】
次に、第１実施形態のステップＳ１１２で説明したように、初期ラベルなし集合作成部１４２（図８）が、ラベルなし集合U0を生成する（ステップＳ１１２）。
【０１２５】
次に、スパイ作成・分割部２４３（図８）が、記憶部１３０に格納された各クラスjに対応する正例集合RP0jをそれぞれV個の部分集合に分割し、各部分集合からそれぞれ選択された要素を初期スパイ素性列とする。すなわち、本形態では、クラスjに対応する正例集合RP0jをV個の部文集合に分割したものを
RP0j={spy0j(1),…,spy0j(V)} …(16)
とし、初期スパイ素性列の集合spy0を
spy0={spy0(1),…,spy0(V)} …(17)
のようにV個の部分集合からなるものとし、これらの各部文集合を
spy0(v)={spy01(v),…,spy0c(v)} (v=1,2,3,…,V) …(18)
とする。
【０１２６】
スパイ作成・分割部２４３は、生成した初期スパイ素性列の集合spy0を記憶部１３０に格納する（ステップＳ２１３）。
【０１２７】
次に、学習部２４４が、部分集合v(v=1,2,3,…,V)ごとに独立に、各正例集合RP0j (j=1,...,c)に属する素性列と当該素性列が正例集合正例集合RP0jに属することを表すラベルjとの組、及び、初期ラベルなし集合作成部１４２で生成されたラベルなし集合U0に属する素性列と当該素性列がラベルなし集合U0に属することを表すラベルUとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルME0(v)を生成する。本形態では、第１実施形態と同様な機械学習方式を用いる。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【０１２８】
例えば、学習部２４４は、部分集合v(v=1,2,3,…,V)ごとに独立に、差集合（RP0j−spy0j(v)）とラベルjとの組、及び、ラベルなし集合U0とラベルUとの組を学習データとして用い、最大エントロピー原理に基づく識別学習により、差集合（RP0j−spy0j(v)）の要素をxとした場合の条件付確率p(j｜x)とラベルなし集合U0の要素をxとした場合の条件付確率p(U｜x)とに対応するエントロピーを最大化する初期識別モデルME0(v) (v=1,2,3,…,V)を生成する。なお、部分集合v(v=1,2,3,…,V)ごとに独立に機械学習を行うのではなく、第１実施形態と同様にV個の分割を一度無視して機械学習を行って初期識別モデルをME0を得た後に，ME0をME0 (v) (v=1,2,3,…,V)とみなして用いてもよい。
【０１２９】
学習部２４４は、生成した初期識別モデルME0(v) (v=1,2,3,…,V)を記憶部１３０に格納する（ステップＳ２１４）。
【０１３０】
次に、閾値決定部２４５（図８）が、部分集合v(v=1,2,3,…,V)ごとに独立に、ラベルなし集合U0に対応するラベルUと記憶部１３０に格納された初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列とを初期識別モデルME0(v)に与え、初期スパイ素性列がラベルなし集合U0に属することになり易いか，逆に言えば正例集合RP0に属することになりにくいか，ということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値t0N(v)を決定する。本形態の閾値決定部２４５は、例えば、初期識別モデルME0(v)を用い、初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の最大値
【０１３１】
【数１２】
を第１閾値t0N(v)とする。
【０１３２】
また、式(19)の代わりに、初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列spyとラベルUとに対する条件付確率P(U|spy)の平均値
【０１３３】
【数１３】
を第１閾値t0N(v)としてもよい。
【０１３４】
さらに、第１閾値t0N(v)に加えて、初期スパイ素性列の集合spy0(v)に属する初期スパイ素性列spyとラベルjとに対する条件付確率P(j|spy)の平均値
【０１３５】
【数１４】
を閾値t0j(v)として求めてもよい。
【０１３６】
閾値決定部２４５は、以上のように生成した第１閾値t0N(v)（及び閾値t0j(v)）を記憶部１３０に格納する（ステップＳ２１５）。
【０１３７】
次に、クラス識別部２４６（図８）の閾値判定部２４６Ａが、各部分集合v(v=1,2,3,…,V)について、ラベルなし集合U0を表すラベルUとラベルなし集合U0に属する各素性列とを初期識別モデルME0(v)に与え、当該ラベルなし集合U0に属する各素性列がラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合U0に属する各素性列に対してそれぞれ生成し、当該第１指標と第１閾値t0N(v)とを比較する。閾値判定部２４６Ａは、当該比較結果に基づき、各部分集合v(v=1,2,3,…,V)について、当該ラベルなし集合U0に属する各素性列が負例集合RN1(v)に属するか否かを識別し、負例集合RN1(v)に属すると識別された素性列を負例集合RN1(v)の要素とする。例えば、閾値判定部２４６Ａは、閾値決定部２４５で決定された各閾値と学習部２４４で生成された初期識別モデルME0(v)とを用い、
pv(U｜u)>t0N(v) …(22)
を満たすか否かを判定し、これを満たす素性列uを負例集合RN1(v)の要素とする。なお、pv(U｜u)は、初期識別モデルME0(v)を用いて生成された条件付確率を表す。
【０１３８】
また、例えば、閾値判定部２４６Ａは、記憶部１３０から読み出した各クラスjに対応する正例集合RP0j (j=1,...,c)をそれぞれV個の部分集合に分割し、それらをRP1j(1)，…，RP1j(V)とし、RP1j(v) (v=1,...,V)を正例集合RN1(v)の要素とする。
【０１３９】
なお、閾値決定部２４５で閾値t0j(v)(j=1,...,c)が生成される場合には、正例集合RP0j(v)(j=1,...,c)を正例集合RP1j(v)とする代わりに、ラベルなし文集合U0に含まれる素性列uのうち、
pv(j｜u)>t0j(v) …(23)
を満たすものを正例集合RP1j(v)に属すると識別し、正例集合RP1j(v)に属すると識別された素性列をそれぞれ正例集合RP1j(v)の要素としてもよい（ステップＳ２１６）。
【０１４０】
次に、統合部２４６ＢがRN1(1),...,RN1(V)とRP1j(1),...,RP1j(V)(j=1,...,c)とを入力とし、統合部２４６Ｂは、第１判定閾値個以上の第１閾値t0N(v)に対して第１判定条件を満たすと判定された第１指標に対応する素性列を負例集合RN1の要素とする。すなわち、統合部２４６Ｂは、第１判定閾値個以上のRN1(1),...,RN1(V)が含む同一の素性列を負例集合RN1の要素とする。また、統合部２４６Ｂは、第１判定閾値個以上のRP1j(1),...,RP1j(V)が含む同一の素性列を正例集合RP1jの要素とする。
【０１４１】
ここで、第１判定閾値の例は、V/2, V, 1などの値から選択可能である。例えば、Vを選択した場合は、V/2を選択した場合よりも精度の高い正例及び負例を集めることができるが、正例や負例の数が少なくなってしまう危険性がある。1を選択した場合は、精度が他の第１判定閾値の場合よりも低くなる可能性があるものの、より多くの正例及び負例を集めることができると言える。これらの第１判定閾値のうちV/2は、システムが出力する正例や負例の精度（適合率）との網羅性（再現率）のバランスを取った平均的な閾値といえる。このように、本形態では、第１判定閾値の選択に応じて、抽出できる正例及び負例の精度や数を調整することができる。さらに、統合部２４６Ｂは、D−RP1−RN1（RP1=｛RP11，…，RP1C｝）を新たなラベルなし文集合U1として作成する（ステップＳ２１７）。
【０１４２】
次に、停止条件判定部１６０（図７）がi=1に設定する（ステップＳ１２１）。
【０１４３】
次に、識別学習部２５０のスパイ作成・分割部２５１（図９）が、記憶部１３０に格納された各クラスjに対応する正例集合RPijをそれぞれV個の部分集合に分割し、各部分集合からそれぞれ選択された要素を正例スパイ素性列する。また、スパイ作成・分割部２５１は、記憶部１３０に格納された負例集合RNiをそれぞれV個の部分集合に分割し、各部分集合からそれぞれ選択された要素を負例スパイ素性列とする。本形態のスパイ作成・分割部２５１は、例えば、RPij (j=1,2,…,c)およびRNiをそれぞれV個の部分集合に分割し、スパイ文集合spyi={spyi(1),…,spyi(V)}を作成する。ここで、
spyi(v)={spyi1(v),…,spyic(v),spyiN(v)} v=1,2,3,…,V
spyij={spyij(1),…,spyij(V)}, spyi={spyi(1),…,spyi(V)}
である。
【０１４４】
スパイ作成・分割部２５１は、生成したスパイ文集合spyi={spyi(1),…,spyi(V)}を記憶部１３０に格納する（ステップＳ２２２）。
【０１４５】
次に、学習部２５２（図３）が、部分集合v(v=1,2,3,…,V)ごとに独立に、正例集合RPij (j=1,...,c)に属する素性列と当該素性列が正例集合に属することを表すラベルjとの組、及び、負例集合RN1に属する素性列と当該素性列が負例集合RNiに属することを表すラベルNとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルMEi(v)を生成する。ここでの機械学習は、前述のステップＳ２１４と同様に行う。この場合、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標は、条件付確率で与えられる。
【０１４６】
例えば、学習部２５２は、部分集合v(v=1,2,3,…,V)ごとに独立に、各クラスj(j∈C)における各正例集合RPij (j=1,...,c)から、当該クラスjに対応する正例スパイ素性列の集合spyij(v)を差し引いた差集合（RPij−spyij(v)）(j=1,...,c)とラベルj(j=1,...,c)との組、負例集合RNiから負例スパイ素性列の集合spyiN(v)を差し引いた差集合（RNi−spyiN(v)）とラベルNとの組、及び、ラベルなし集合Uiとスパイ素性列の集合spyiとの和集合（Ui+spyi(v)）とラベルUとの組を学習データとして用い、前述した最大エントロピー原理に基づく識別学習により、識別モデルMEi(v)を求める。なお、部分集合v(v=1,2,3,…,V)ごとに独立に機械学習を行うのではなく、第１実施形態と同様にV個の分割を一度無視して機械学習を行って初期識別モデルをMEiを得た後に、MEiをMEi (v) (v=1,2,3,…,V)とみなして用いてもよい。
【０１４７】
学習部２５２は、生成した識別モデルMEi(v)を記憶部１３０に格納する（ステップＳ２２３）。
【０１４８】
次に、閾値決定部２５３（図９）が、部分集合v(v=1,2,3,…,V)ごとに独立に、正例集合RPijを表すラベルj(j=1,...,c)と記憶部１３０に格納された正例スパイ素性列（spyij(v)の要素）とを識別モデルMEi(v)に与え、正例スパイ素性列が正例集合RPijに属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値tij(v) (j=1,...,c)を決定する。さらに、閾値決定部２５３は、負例集合RNiを表すラベルNと記憶部１３０に格納された負例スパイ素性列（spyij(v)の要素）とを識別モデルMEi(v)に与え、負例スパイ素性列が負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値tiNを決定する。本形態の閾値決定部２５３は、例えば、識別モデルMEi(v)を用い、スパイ素性列の集合spy0(v)に属するスパイ素性列spyとラベルj=1,2,…,cとNとを用い、以下のように正例閾値tij(v) (j=1,...,c)と負例閾値tiN(v)とを生成する。
【０１４９】
クラスjに対する正例閾値tij(v):
【０１５０】
【数１５】
クラスNに対する負例閾値tiN(v)：
【０１５１】
【数１６】
なお、式(25)(26)の代わりに以下のように正例閾値tijと負例閾値tiNとが生成されてもよい。
【０１５２】
クラスjに対する正例閾値tij(v):
【０１５３】
【数１７】
クラスNに対する負例閾値tiN(v)：
【０１５４】
【数１８】
閾値決定部２５３は、生成した正例閾値tij(v)と負例閾値tiN(v)とを出力する（ステップＳ２２４）。
【０１５５】
次に、クラス識別部２５４（図９）が、部分集合v(v=1,2,3,…,V)ごとに独立に、正例集合RPijを表すラベルjとラベルなし集合Uiに属する各素性列とを識別モデルMEi(v)に与え、当該ラベルなし集合Uiに属する各素性列が当該ラベルjによって表される正例集合RPijに属することになり易いかということを表す指標である正例指標を当該ラベルなし集合Uiに属する各素性列に対してそれぞれ生成し、当該正例指標と正例閾値tij(v)とを比較する。また、クラス識別部２５４は、部分集合v(v=1,2,3,…,V)ごとに独立に、負例集合RNiを表すラベルNとラベルなし集合Uiに属する各素性列とを識別モデルMEi(v)に与え、当該ラベルなし集合Uiに属する各素性列が負例集合RNiに属することになり易いかということを表す指標である負例指標tiN(v)を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と負例閾値とを比較する。クラス識別部２５４は、これらの比較結果に応じて、部分集合v(v=1,2,3,…,V)ごとに独立に、ラベルなし集合Uiに属する各素性列を正例集合RPi+1jと負例集合RNi+1jとに振り分ける。例えば、クラス識別部２５４は、各v=1,2,…,Vについて、RPi(v), RNi(v), Uiに含まれる素性列xのうち、argmaxj'∈C'p(j'|x)となるクラスj'∈C'がp(j'|x)>tij'(v)を満たす場合に、素性列xをクラスj'に対応する集合に識別する。つまり、j'が正例集合に対応するのであれば正例集合RPi+1j(v)、負例集合に対応するのであれば負例集合RNi(v)に識別される（ステップＳ２２５）。
【０１５６】
次に、統合部２５４ＢがRNi(1),...,RNi(V)とRPij(1),...,RPij(V)(j=1,...,c)とを入力とし、統合部２５４Ｂは、第２判定閾値個以上の正例閾値tij(v)に対して第２判定条件を満たすと判定された指標に対応する素性列を正例集合RPi+1の要素の要素とする。また、統合部２５４Ｂは、第３判定閾値個以上の負例閾値tiN(v)に対して第３判定条件を満たすと判定された指標に対応する素性列を負例集合RNi+1の要素とする。第２、３判定閾値は、例えば、第１判定閾値と同様に設定される。本形態では、判定閾値の選択に応じて、抽出できる正例及び負例の精度や数を調整することができる。また，RPi+1j (j=1,2,…,c)及びRNi+1のいずれにも識別されなかったものが、新たなラベルなし集合Ui+1の要素とされる（ステップＳ２２６）。
【０１５７】
その後、第１実施形態と同様にステップＳ１２６、Ｓ１２７、Ｓ１２８の処理が実行される。
【０１５８】
〔本形態の特徴〕
以上説明したように、第１、２実施形態では、繰り返し処理ごとに識別モデルとスパイ素性列とから閾値を決定し、決定した閾値を用いた判断基準に従って、正例集合、負例集合及びラベルなし集合を更新する。
【０１５９】
これにより、繰り返し処理ごとに変化する識別モデルに応じて適切な閾値を自動的に定めることができ、生成された閾値を用いて正例集合、負例集合及びラベルなし集合を更新することで、信頼度の低い識別結果にひきずられ、間違った方向へ学習が進む問題を解消し、高精度な関係抽出を行うことが可能となる。
【０１６０】
また、広範囲な機械学習方式を利用できるため、単語以外の一般的な識別に有用と思われる素性を利用して識別（関係抽出）を行うことができる。
【０１６１】
さらに、スパイアルゴリズムをマルチクラスへ拡張した手法を利用することにより、負例作成時の恣意性や網羅性、ノイズの問題を削減できる。
【０１６２】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の実施形態では、コーパスが予め素性変換されている例を示したが、正例集合の初期要素を生成した後など、その他のタイミングでコーパスを素性変換してもよい。
【０１６３】
また、上記の実施形態では、最大エントロピー法を用いて学習を行ったが、サポートベクトルマシンなどその他の周知の機械学習方式が用いられてもよい。なお、最大エントロピー法を用いた場合の「与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標」は条件付確率であったが、サポートベクトルマシンを用いた場合の同様の指標は距離となる。
【０１６４】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１６５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１６６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１６７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１６８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１７０】
１，２ データ抽出装置
【特許請求の範囲】
【請求項１】
テキストに対応する複数の素性からなる素性列を要素とする母集合のうち、特定の記号列であるシードエンティティの組み合わせと関連性があると識別された素性列を要素とする集合を正例集合とし、前記シードエンティティの組み合わせと関連性がないと識別された素性列を要素とする集合を負例集合とし、前記シードエンティティの組み合わせとの関連性が識別されていない素性列を要素とする集合をラベルなし集合とした場合における、前記シードエンティティの組み合わせを含むテキストに対応する複数の素性からなる素性列を前記正例集合の初期要素とする初期正例集合作成部と、
前記母集合から前記正例集合の初期要素を除いた差集合の少なくとも一部の要素を前記ラベルなし集合の初期要素とする初期ラベルなし集合作成部と、
前記正例集合から選択された要素を初期スパイ素性列とする第１スパイ作成部と、
前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記ラベルなし集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルを生成する第１学習部と、
前記ラベルなし集合を表すラベルと前記初期スパイ素性列とを前記初期識別モデルに与え、前記初期スパイ素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値を決定する第１閾値決定部と、
前記ラベルなし集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記初期識別モデルに与え、当該ラベルなし集合に属する各素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該第１指標と前記第１閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素とし、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を前記ラベルなし集合の要素とする第１クラス識別部と、
を有するデータ抽出装置。
【請求項２】
請求項１のデータ抽出装置であって、
前記正例集合から選択された要素を正例スパイ素性列とし、前記負例集合から選択された要素を負例スパイ素性列とする第２スパイ作成部と、
前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記負例集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルを生成する第２学習部と、
前記正例集合を表すラベルと前記正例スパイ素性列とを前記識別モデルに与え、前記正例スパイ素性列が前記正例集合に属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値を決定し、さらに、前記負例集合を表すラベルと前記負例スパイ素性列とを前記識別モデルに与え、前記負例スパイ素性列が前記負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値を決定する第２閾値決定部と、
前記正例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属することになり易いかということを表す指標である正例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該正例指標と前記正例閾値とを比較することで当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属するか否かを識別し、当該ラベルによって表される正例集合に属すると識別された素性列を当該ラベルによって表される正例集合の要素に追加し、前記負例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が前記負例集合に属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と前記負例閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素に追加し、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を新たなラベルなし集合とする第２クラス識別部と、
を有するデータ抽出装置。
【請求項３】
請求項２のデータ抽出装置であって、
１又は複数のクラスが設定され、前記シードエンティティの組み合わせは前記クラスごとに設定され、前記正例集合は前記クラスごとに対応し、素性列が前記正例集合に属することを表すラベルは、素性列が特定のクラスに対応する前記正例集合に属することを表す情報である、
ことを特徴とするデータ抽出装置。
【請求項４】
請求項３のデータ抽出装置であって、
前記初期スパイ素性列と前記正例スパイ素性列とは、それぞれ、前記クラスごとに生成される、
ことを特徴とするデータ抽出装置。
【請求項５】
請求項３のデータ抽出装置であって、
前記クラスごとに存在する前記正例集合はそれぞれ複数の部分集合に分割され、
前記初期スパイ素性列と前記正例スパイ素性列と前記負例スパイ素性列とは、それぞれ、前記部分集合ごとに生成され、
前記第１閾値決定部は、前記部分集合ごとに前記第１閾値を決定し、
前記第１クラス識別部は、前記第１指標と前記部分集合ごとに決定された複数の前記第１閾値とをそれぞれ比較して前記第１閾値ごとに前記第１指標が第１判定条件を満たすか否かを判定し、第１判定閾値個以上の前記第１閾値に対して前記第１判定条件を満たすと判定された前記第１指標に対応する素性列を前記負例集合の要素とし、
前記第２閾値決定部は、前記部分集合ごとに前記正例閾値及び前記負例閾値を決定し、
前記第２クラス識別部は、前記正例指標と前記部分集合ごとに決定された複数の前記正例閾値とをそれぞれ比較して前記正例閾値ごとに前記正例指標が正例判定条件を満たすか否かを判定し、第２判定閾値個以上の前記正例閾値に対して前記正例判定条件を満たすと判定された前記正例指標に対応する素性列を前記正例集合の要素に追加し、前記負例指標と前記部分集合ごとに決定された複数の前記負例閾値とをそれぞれ比較して前記負例閾値ごとに前記負例指標が負例判定条件を満たすか否かを判定し、第３判定閾値個以上の前記負例閾値に対して前記負例判定条件を満たすと判定された前記負例指標に対応する素性列を前記負例集合の要素に追加する、
ことを特徴とするデータ抽出装置。
【請求項６】
請求項２から５の何れかのデータ抽出装置であって、
予め定められた停止条件を満たすか否かを判定し、停止条件を満たさないと判定した場合に、前記第２スパイ作成部の処理と前記第２学習部の処理と前記第２閾値決定部の処理と前記第２クラス識別部の処理とを再び実行させる停止条件判定部と、
前記停止条件判定部が予め定められた停止条件を満たすと判定した場合、前記正例集合を表すラベルと前記正例集合に属する素性列とを前記識別モデルに与えることで得られる、前記正例集合に属する前記素性列が前記正例集合に属することになり易いかということを表す指標を基準として前記正例集合から素性列を選択する選択部と、
を有するデータ抽出装置。
【請求項７】
請求項２から５の何れかのデータ抽出装置であって、
予め定められた停止条件を満たすか否かを判定し、停止条件を満たさないと判定した場合に、前記第２スパイ作成部の処理と前記第２学習部の処理と前記第２閾値決定部の処理と前記第２クラス識別部の処理とを再び実行させる停止条件判定部と、
前記停止条件判定部が予め定められた停止条件を満たすと判定した場合、前記正例集合を表すラベルと前記正例集合に属する素性列が含む素性の組み合わせとを前記識別モデルに与えることで得られる、当該素性の組み合わせが前記正例集合に属することになり易いかということを表す指標を基準として、前記正例集合に属する素性列から素性の組み合わせを選択する選択部と、
を有するデータ抽出装置。
【請求項８】
初期正例集合作成部が、テキストに対応する複数の素性からなる素性列を要素とする母集合のうち、特定の記号列であるシードエンティティの組み合わせと関連性があると識別された素性列を要素とする集合を正例集合とし、前記シードエンティティの組み合わせと関連性がないと識別された素性列を要素とする集合を負例集合とし、前記シードエンティティの組み合わせとの関連性が識別されていない素性列を要素とする集合をラベルなし集合とした場合における、前記シードエンティティの組み合わせを含むテキストに対応する複数の素性からなる素性列を前記正例集合の初期要素とするステップと、
初期ラベルなし集合作成部が、前記母集合から前記正例集合の初期要素を除いた差集合の少なくとも一部の要素を前記ラベルなし集合の初期要素とするステップと、
第１スパイ作成部が、前記正例集合から選択された要素を初期スパイ素性列とするステップと、
第１学習部が、前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記ラベルなし集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルを生成するステップと、
第１閾値決定部が、前記ラベルなし集合を表すラベルと前記初期スパイ素性列とを前記初期識別モデルに与え、前記初期スパイ素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値を決定するステップと、
第１クラス識別部が、前記ラベルなし集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記初期識別モデルに与え、当該ラベルなし集合に属する各素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該第１指標と前記第１閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素とし、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を前記ラベルなし集合の要素とするステップと、
を有するデータ抽出方法。
【請求項９】
請求項８のデータ抽出方法であって、
第２スパイ作成部が、前記正例集合から選択された要素を正例スパイ素性列とし、前記負例集合から選択された要素を負例スパイ素性列とするステップと、
第２学習部が、前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記負例集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルを生成するステップと、
第２閾値決定部が、前記正例集合を表すラベルと前記正例スパイ素性列とを前記識別モデルに与え、前記正例スパイ素性列が前記正例集合に属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値を決定し、さらに、前記負例集合を表すラベルと前記負例スパイ素性列とを前記識別モデルに与え、前記負例スパイ素性列が前記負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値を決定するステップと、
第２クラス識別部が、前記正例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属することになり易いかということを表す指標である正例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該正例指標と前記正例閾値とを比較することで当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属するか否かを識別し、当該ラベルによって表される正例集合に属すると識別された素性列を当該ラベルによって表される正例集合の要素に追加し、前記負例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が前記負例集合に属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と前記負例閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素に追加し、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を新たなラベルなし集合とするステップと、
停止条件判定部が、予め定められた停止条件を満たすか否かを判定し、停止条件を満たさないと判定した場合に、前記第２スパイ作成部の処理と前記第２学習部の処理と前記第２閾値決定部の処理と前記第２クラス識別部の処理とを再び実行させるステップと、
を有するデータ抽出方法。
【請求項１０】
請求項１から７の何れかのデータ抽出装置としてコンピュータを機能させるためのプログラム。
【請求項１】
テキストに対応する複数の素性からなる素性列を要素とする母集合のうち、特定の記号列であるシードエンティティの組み合わせと関連性があると識別された素性列を要素とする集合を正例集合とし、前記シードエンティティの組み合わせと関連性がないと識別された素性列を要素とする集合を負例集合とし、前記シードエンティティの組み合わせとの関連性が識別されていない素性列を要素とする集合をラベルなし集合とした場合における、前記シードエンティティの組み合わせを含むテキストに対応する複数の素性からなる素性列を前記正例集合の初期要素とする初期正例集合作成部と、
前記母集合から前記正例集合の初期要素を除いた差集合の少なくとも一部の要素を前記ラベルなし集合の初期要素とする初期ラベルなし集合作成部と、
前記正例集合から選択された要素を初期スパイ素性列とする第１スパイ作成部と、
前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記ラベルなし集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルを生成する第１学習部と、
前記ラベルなし集合を表すラベルと前記初期スパイ素性列とを前記初期識別モデルに与え、前記初期スパイ素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値を決定する第１閾値決定部と、
前記ラベルなし集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記初期識別モデルに与え、当該ラベルなし集合に属する各素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該第１指標と前記第１閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素とし、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を前記ラベルなし集合の要素とする第１クラス識別部と、
を有するデータ抽出装置。
【請求項２】
請求項１のデータ抽出装置であって、
前記正例集合から選択された要素を正例スパイ素性列とし、前記負例集合から選択された要素を負例スパイ素性列とする第２スパイ作成部と、
前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記負例集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルを生成する第２学習部と、
前記正例集合を表すラベルと前記正例スパイ素性列とを前記識別モデルに与え、前記正例スパイ素性列が前記正例集合に属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値を決定し、さらに、前記負例集合を表すラベルと前記負例スパイ素性列とを前記識別モデルに与え、前記負例スパイ素性列が前記負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値を決定する第２閾値決定部と、
前記正例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属することになり易いかということを表す指標である正例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該正例指標と前記正例閾値とを比較することで当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属するか否かを識別し、当該ラベルによって表される正例集合に属すると識別された素性列を当該ラベルによって表される正例集合の要素に追加し、前記負例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が前記負例集合に属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と前記負例閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素に追加し、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を新たなラベルなし集合とする第２クラス識別部と、
を有するデータ抽出装置。
【請求項３】
請求項２のデータ抽出装置であって、
１又は複数のクラスが設定され、前記シードエンティティの組み合わせは前記クラスごとに設定され、前記正例集合は前記クラスごとに対応し、素性列が前記正例集合に属することを表すラベルは、素性列が特定のクラスに対応する前記正例集合に属することを表す情報である、
ことを特徴とするデータ抽出装置。
【請求項４】
請求項３のデータ抽出装置であって、
前記初期スパイ素性列と前記正例スパイ素性列とは、それぞれ、前記クラスごとに生成される、
ことを特徴とするデータ抽出装置。
【請求項５】
請求項３のデータ抽出装置であって、
前記クラスごとに存在する前記正例集合はそれぞれ複数の部分集合に分割され、
前記初期スパイ素性列と前記正例スパイ素性列と前記負例スパイ素性列とは、それぞれ、前記部分集合ごとに生成され、
前記第１閾値決定部は、前記部分集合ごとに前記第１閾値を決定し、
前記第１クラス識別部は、前記第１指標と前記部分集合ごとに決定された複数の前記第１閾値とをそれぞれ比較して前記第１閾値ごとに前記第１指標が第１判定条件を満たすか否かを判定し、第１判定閾値個以上の前記第１閾値に対して前記第１判定条件を満たすと判定された前記第１指標に対応する素性列を前記負例集合の要素とし、
前記第２閾値決定部は、前記部分集合ごとに前記正例閾値及び前記負例閾値を決定し、
前記第２クラス識別部は、前記正例指標と前記部分集合ごとに決定された複数の前記正例閾値とをそれぞれ比較して前記正例閾値ごとに前記正例指標が正例判定条件を満たすか否かを判定し、第２判定閾値個以上の前記正例閾値に対して前記正例判定条件を満たすと判定された前記正例指標に対応する素性列を前記正例集合の要素に追加し、前記負例指標と前記部分集合ごとに決定された複数の前記負例閾値とをそれぞれ比較して前記負例閾値ごとに前記負例指標が負例判定条件を満たすか否かを判定し、第３判定閾値個以上の前記負例閾値に対して前記負例判定条件を満たすと判定された前記負例指標に対応する素性列を前記負例集合の要素に追加する、
ことを特徴とするデータ抽出装置。
【請求項６】
請求項２から５の何れかのデータ抽出装置であって、
予め定められた停止条件を満たすか否かを判定し、停止条件を満たさないと判定した場合に、前記第２スパイ作成部の処理と前記第２学習部の処理と前記第２閾値決定部の処理と前記第２クラス識別部の処理とを再び実行させる停止条件判定部と、
前記停止条件判定部が予め定められた停止条件を満たすと判定した場合、前記正例集合を表すラベルと前記正例集合に属する素性列とを前記識別モデルに与えることで得られる、前記正例集合に属する前記素性列が前記正例集合に属することになり易いかということを表す指標を基準として前記正例集合から素性列を選択する選択部と、
を有するデータ抽出装置。
【請求項７】
請求項２から５の何れかのデータ抽出装置であって、
予め定められた停止条件を満たすか否かを判定し、停止条件を満たさないと判定した場合に、前記第２スパイ作成部の処理と前記第２学習部の処理と前記第２閾値決定部の処理と前記第２クラス識別部の処理とを再び実行させる停止条件判定部と、
前記停止条件判定部が予め定められた停止条件を満たすと判定した場合、前記正例集合を表すラベルと前記正例集合に属する素性列が含む素性の組み合わせとを前記識別モデルに与えることで得られる、当該素性の組み合わせが前記正例集合に属することになり易いかということを表す指標を基準として、前記正例集合に属する素性列から素性の組み合わせを選択する選択部と、
を有するデータ抽出装置。
【請求項８】
初期正例集合作成部が、テキストに対応する複数の素性からなる素性列を要素とする母集合のうち、特定の記号列であるシードエンティティの組み合わせと関連性があると識別された素性列を要素とする集合を正例集合とし、前記シードエンティティの組み合わせと関連性がないと識別された素性列を要素とする集合を負例集合とし、前記シードエンティティの組み合わせとの関連性が識別されていない素性列を要素とする集合をラベルなし集合とした場合における、前記シードエンティティの組み合わせを含むテキストに対応する複数の素性からなる素性列を前記正例集合の初期要素とするステップと、
初期ラベルなし集合作成部が、前記母集合から前記正例集合の初期要素を除いた差集合の少なくとも一部の要素を前記ラベルなし集合の初期要素とするステップと、
第１スパイ作成部が、前記正例集合から選択された要素を初期スパイ素性列とするステップと、
第１学習部が、前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記ラベルなし集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する初期識別モデルを生成するステップと、
第１閾値決定部が、前記ラベルなし集合を表すラベルと前記初期スパイ素性列とを前記初期識別モデルに与え、前記初期スパイ素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１基準指標を生成し、当該第１基準指標に対応する第１閾値を決定するステップと、
第１クラス識別部が、前記ラベルなし集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記初期識別モデルに与え、当該ラベルなし集合に属する各素性列が前記ラベルなし集合に属することになり易いかということを表す指標である第１指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該第１指標と前記第１閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素とし、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を前記ラベルなし集合の要素とするステップと、
を有するデータ抽出方法。
【請求項９】
請求項８のデータ抽出方法であって、
第２スパイ作成部が、前記正例集合から選択された要素を正例スパイ素性列とし、前記負例集合から選択された要素を負例スパイ素性列とするステップと、
第２学習部が、前記正例集合に属する素性列と当該素性列が前記正例集合に属することを表すラベルとの組、及び、前記負例集合に属する素性列と当該素性列が前記負例集合に属することを表すラベルとの組を学習データとして用い、どのような素性から構成される素性列の場合にどのようなラベルが表す集合に属することになり易いかということを機械学習し、与えられた素性列及びラベルに対して当該与えられた素性列が当該与えられたラベルの表す集合に属することになり易いかということを表す指標を出力する識別モデルを生成するステップと、
第２閾値決定部が、前記正例集合を表すラベルと前記正例スパイ素性列とを前記識別モデルに与え、前記正例スパイ素性列が前記正例集合に属することになり易いかということを表す指標である正例基準指標を生成し、当該正例基準指標に対応する正例閾値を決定し、さらに、前記負例集合を表すラベルと前記負例スパイ素性列とを前記識別モデルに与え、前記負例スパイ素性列が前記負例集合に属することになり易いかということを表す指標である負例基準指標を生成し、当該負例基準指標に対応する負例閾値を決定するステップと、
第２クラス識別部が、前記正例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属することになり易いかということを表す指標である正例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該正例指標と前記正例閾値とを比較することで当該ラベルなし集合に属する各素性列が当該ラベルによって表される正例集合に属するか否かを識別し、当該ラベルによって表される正例集合に属すると識別された素性列を当該ラベルによって表される正例集合の要素に追加し、前記負例集合を表すラベルと前記ラベルなし集合に属する各素性列とを前記識別モデルに与え、当該ラベルなし集合に属する各素性列が前記負例集合に属することになり易いかということを表す指標である負例指標を当該ラベルなし集合に属する各素性列に対してそれぞれ生成し、当該負例指標と前記負例閾値とを比較することで当該ラベルなし集合に属する各素性列が前記負例集合に属するか否かを識別し、前記負例集合に属すると識別された素性列を前記負例集合の要素に追加し、前記母集合から当該負例集合と前記正例集合とを除いた差集合に相当する集合を新たなラベルなし集合とするステップと、
停止条件判定部が、予め定められた停止条件を満たすか否かを判定し、停止条件を満たさないと判定した場合に、前記第２スパイ作成部の処理と前記第２学習部の処理と前記第２閾値決定部の処理と前記第２クラス識別部の処理とを再び実行させるステップと、
を有するデータ抽出方法。
【請求項１０】
請求項１から７の何れかのデータ抽出装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−１７５４９７（Ｐ２０１１−１７５４９７Ａ）
【公開日】平成２３年９月８日（２０１１．９．８）
【国際特許分類】
【出願番号】特願２０１０−３９６５１（Ｐ２０１０−３９６５１）
【出願日】平成２２年２月２５日（２０１０．２．２５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年９月８日（２０１１．９．８）
【国際特許分類】
【出願日】平成２２年２月２５日（２０１０．２．２５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]