(57)【要約】【課題】ＷＷＷなどの膨大なテキストデータから、エンティティペア間の関係を表現し、エンティティペア間の関係を用いて関係検索を実現する。【解決手段】エンティティペア(Ａ，Ｂ)とエンティティＣが入力された場合に、エンティティペア（Ｃ，Ｘ）のエンティティＣ、Ｘ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを、検索する方法であって、エンティティＡとエンティティＢとの間の関係を、エンティティＡとエンティティＢを含むテキストにおけるエンティティＡ，Ｂの周辺の文脈に依存して規定し、エンティティＡ，Ｂの周辺の文脈と同一あるいは類似の文脈を周辺に備えたエンティティＣ，Ｘを探索することで、エンティティＣとの間において、エンティティＡとエンティティＢの関係と同一または類似の関係を備えるエンティティＸを取得する。【選択図】図１
2011118689.tif 000002
【特許請求の範囲】
【請求項１】
エンティティのペア(Ａ，Ｂ)とエンティティＣが入力された場合に、エンティティのペア（Ｃ，Ｘ）のエンティティＣ、Ｘ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを、検索データベースあるいは／および既存の検索エンジンを用いて、検索する方法であって、
エンティティのペア(Ａ，Ｂ)とエンティティＣをクエリとして受け取り、
エンティティＡとエンティティＢとの間の関係を、エンティティＡとエンティティＢを含むテキストにおけるエンティティＡ，Ｂの周辺の文脈に依存して規定し、
エンティティＡ，Ｂの周辺の文脈と同一あるいは類似の文脈を周辺に備えたエンティティＣ，Ｘを探索することで、エンティティＣとの間において、エンティティＡとエンティティＢの関係と同一または類似の関係を備えるエンティティＸを取得する、検索方法。
【請求項２】
前記文脈は、語彙パターン、bag-of-words、品詞パターン、係り受けパターンの１つあるいは任意の組み合わせである、請求項１に記載の検索方法。
【請求項３】
前記文脈はクラスタリングされ、各文脈クラスタには、実質的に同一あるいは類似の文脈が含まれる、請求項１、２いずれかに記載の検索方法。
【請求項４】
エンティティのペアの２つのエンティティ間の関係は、特徴ベクトルによって表現され、前記特徴ベクトルは、前記エンティティペアの２つのエンティティの周辺の文脈あるいは文脈クラスタから取得される、請求項３に記載の検索方法。
【請求項５】
エンティティＡとエンティティＢとの間の関係は、第１の特徴ベクトルによって表現され、第１の特徴ベクトルは、エンティティＡ，Ｂの周辺の文脈あるいは文脈クラスタから取得され、
エンティティＸを取得するステップは、エンティティＣとの間において、第１の特徴ベクトルと同一あるいは類似の第２の特徴ベクトルを備えるエンティティＸを取得するものであり、第２の特徴ベクトルは、エンティティＣとエンティティＸを含むテキストにおけるエンティティＣ，Ｘの周辺の文脈あるいは文脈クラスタから取得される、請求項４に記載の検索方法。
【請求項６】
前記エンティティＸを取得するステップは、
エンティティペア(Ａ，Ｂ)と各エンティティペア(Ｃ，Ｘ)のペア間の類似度を、両者の特徴ベクトル間の距離に基づいて算出し、算出されたペア間類似度を指標として、エンティティペア間類似度が大きい順に複数のエンティティペア(Ｃ，Ｘ)をソートし、ソート順にＸの候補をランキングするステップと、
ランキングされたＸの一部あるいは全部を検索結果として出力するステップと、
を備えている、請求項５に記載の検索方法。
【請求項７】
前記文脈は語彙パターンであり、前記特徴ベクトルは語彙パターンの頻度を要素とする、請求項４乃至６いずれかに記載の検索方法。
【請求項８】
前記エンティティＸを取得するステップは、
取得したエンティティペア(Ａ，Ｂ)の第１の特徴ベクトルの語彙パターン（頻度が予め設定した閾値より大きい）を要素に含む第２の特徴ベクトルを備えた複数のエンティティペア(Ｃ，Ｘ)を取得するステップと、
エンティティペア(Ａ，Ｂ)と各エンティティペア(Ｃ，Ｘ)のペア間の類似度を両者の特徴ベクトルを用いて算出し、算出されたペア間類似度を指標として、エンティティペア間類似度が大きい順に複数のエンティティペア(Ｃ，Ｘ)をソートし、ソート順にＸの候補をランキングするステップと、
ランキングされたＸの一部あるいは全部を検索結果として出力するステップと、
を備えている、請求項７に記載の検索方法。
【請求項９】
前記検索データベースには、多数のエンティティペアと、各エンティティペアのエンティティ間の関係を表現する周辺の文脈との対応が格納されている、請求項１に記載の検索方法。
【請求項１０】
前記文脈は語彙パターンであり、前記検索データベースには、多数のエンティティペアと、各エンティティペアと、語彙パターン及び当該語彙パターンの頻度と、の対応が格納されている、請求項９に記載の検索方法。
【請求項１１】
前記検索データベースは、
エンティティペアの各エンティティのＩＤを規定する第１インデックスと、
２つのエンティティＩＤのペアに対応するエンティティペアＩＤを規定する第２インデックスと、
各語彙パターンに対応する語彙パターンＩＤを規定する第３インデックスと、
エンティティペアＩＤと、語彙パターンＩＤ・語彙パターンの頻度と、の対応関係を規定する第４インデックスと、
を備えており、
入力されたエンティティペア(Ａ，Ｂ)に対応するペアＩＤを取得し、前記取得されたエンティティペアＩＤを用いてエンティティペア(Ａ，Ｂ)に対応する語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）・語彙パターンの頻度を取得して第１特徴ベクトルを形成するステップと、
前記第１特徴ベクトルの語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）を含み、かつエンティティＣのＩＤを含む候補エンティティペアＩＤを取得するステップと、
各候補エンティティペアＩＤに対応する第２特徴ベクトルを取得し、前記第２特徴ベクトルが前記第１特徴ベクトルと類似するようなエンティティペア(Ｃ，Ｘ)を取得するステップと、
を備えている、請求項１０に記載の検索方法。
【請求項１２】
前記第４インデックスは、
エンティティペアＩＤから語彙パターンＩＤ・語彙パターンの頻度を検索するためのインデックスと、
語彙パターンＩＤからエンティティペアＩＤ・語彙パターンの頻度を検索するためのインデックスと、
を備えている、請求項１１に記載の検索方法。
【請求項１３】
前記検索データベースにおいて、語彙パターンは、語彙パターンのクラスタを形成しており、各語彙パターンクラスタには、類似あるいは実質的に同一の語彙パターンが含まれている、
請求項１０乃至１２いずれかに記載の検索方法。
【請求項１４】
ペア間の類似度を計算する時の特徴ベクトルの次元を語彙パターンクラスタとし、各次元の値を当該語彙パターンクラスタに含まれる語彙パターンの頻度の総和とする、請求項１３に記載の検索方法。
【請求項１５】
前記検索データベースにおいて、類似のエンティティからなるエンティティクラスタが形成されている、請求項９乃至１４いずれかに記載の検索方法。
【請求項１６】
前記エンティティＸの候補のランキングの指標となるスコアとして、前記エンティティＸが属するエンティティクラスタのスコアを用いる、請求項１５に記載の検索方法。
【請求項１７】
前記出力ステップにおいて、前記エンティティクラスタに含まれる複数のエンティティを出力する、請求項１５、１６いずれかに記載の検索方法。
【請求項１８】
エンティティペアのエンティティ間の関係を表現する特徴ベクトルは、
テキストコーパスから取得した文を単語に切り分け、
切り分けられた単語から候補エンティティペアを作成し、
候補エンティティペアの周辺の文脈から取得される、請求項４乃至８いずれかに記載の検索方法。
【請求項１９】
前記特徴ベクトルの要素は、語彙パターンの頻度であり、
語彙パターンの頻度の抽出は、
候補エンティティペアが含まれる元の文において、エンティティペアの第１エンティティをＸに、第２エンティティをＹに置き換えて、Ｘ，Ｙを含む部分列Ｓを生成し、部分列Ｓのn-gram(ｎは1からＫまで)を生成するステップと、
得られたn-gramを特徴ベクトルの１つの次元として、エンティティペアを含む全ての文において頻度を数えるステップと、
を備え、
n-gramの頻度を語彙パターンの頻度として、エンティティペアと関連付けて保存する、請求項１８に記載の検索方法。
ここで、部分列Ｓは、Ｘの直前のｍ１個の単語，Ｘ，ＸＹ間の単語列，Ｙ，Ｙの直後のｍ２個の単語、である。ｍ１、ｍ２、Ｋは、整数のパラメータである。
【請求項２０】
前記候補エンティティペアの２つエンティティ間の距離Ｄが、閾値Ｄｔｈ以下の場合にのみ候補エンティティペアの周辺の文脈を取得する、請求項１８、１９いずれかに記載の検索方法。
【請求項２１】
前記候補エンティティペアを作成するステップにおいて、固有名詞を含むエンティティペアを候補エンティティペアとして優先的に抽出する、請求項１８乃至２０いずれかに記載の検索方法。
【請求項２２】
前記候補エンティティペアを作るステップにおいて、頻度の高いエンティティペアを候補エンティティペアとして優先的に抽出する、請求項１８乃至２１いずれかに記載の検索方法。
【請求項２３】
類似あるいは実質的に同一の語彙パターンから語彙パターンのクラスタを形成するステップを含む、請求項１８乃至２２いずれかに記載の検索方法。
【請求項２４】
既存の検索エンジンを用いて、エンティティＡとエンティティＢを含むテキストにおけるエンティティＡ，Ｂの周辺の文脈を取得するステップと、
既存の検索エンジンを用いて、エンティティＡ，Ｂの周辺の文脈と同一あるいは類似の文脈を備えたエンティティＣ，Ｘを取得するステップと、
を備えている、請求項１に記載の検索方法。
【請求項２５】
エンティティＡ，Ｂの周辺の文脈は、エンティティＡとエンティティＢの間の距離を制限したエンティティＡ、エンティティＢをクエリとした前記検索エンジンの検索結果としてのスニッペト(snippet)から取得する、請求項２４に記載の検索方法。
【請求項２６】
前記エンティティＡ，Ｂの周辺の文脈は、語彙パターンとして取得され、
エンティティＸの候補は、取得した語彙パターンのＡの位置にＣを代入してなる“C
pattern *”をクエリとした、前記検索エンジンの検索結果としてのスニッペトから取得する、請求項２５に記載の検索方法。
【請求項２７】
エンティティのペア(Ａ，Ｂ)とエンティティＣが入力された場合に、エンティティのペア（Ｃ，Ｘ）のエンティティＣ、Ｘ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを検索データベースを用いて検索するシステムであって、
前記検索データベースには、多数のエンティティペアと、各エンティティペアのエンティティ間の関係を表現する周辺の文脈との対応が格納されており、
エンティティのペア(Ａ，Ｂ)とエンティティＣをクエリとして受け取る手段と、
エンティティＡとエンティティＢとの間の関係を表現する第１の周辺の文脈を、前記検索データベースを用いて取得する手段と、
第１の周辺の文脈と同一あるいは類似の第２の周辺の文脈を備えたエンティティＣ，Ｘを、前記検索データベースを用いて探索することで、エンティティＣを取得する手段と、
を備えている、検索システム。
【請求項２８】
前記文脈は語彙パターンであり、前記検索データベースには、多数のエンティティペアと、各エンティティペアと、語彙パターン及び当該語彙パターンの頻度と、の対応が格納されている、請求項２７に記載の検索システム。
【請求項２９】
取得したエンティティペア(Ａ，Ｂ)の第１の特徴ベクトルの語彙パターン（頻度が予め設定した閾値より大きい）を要素に含む第２の特徴ベクトルを備えた複数のエンティティペア(Ｃ，Ｘ)を取得する手段と、
エンティティペア(Ａ，Ｂ)と各エンティティペア(Ｃ，Ｘ)のペア間の類似度を両者の特徴ベクトルを用いて算出する手段と、
算出されたペア間類似度を指標として、エンティティペア間類似度が大きい順に複数のエンティティペア(Ｃ，Ｘ)をソートし、ソート順にＸの候補をランキングする手段と、
ランキングされたＸの一部あるいは全部を検索結果として出力する手段と、
を備えた請求項２８に記載の検索システム。
【請求項３０】
前記検索データベースは、
エンティティペアの各エンティティのＩＤを規定する第１インデックスと、
２つのエンティティＩＤのペアに対応するエンティティペアＩＤを規定する第２インデックスと、
各語彙パターンに対応する語彙パターンＩＤを規定する第３インデックスと、
エンティティペアＩＤと、語彙パターンＩＤ・語彙パターンの頻度と、の対応関係を規定する第４インデックスと、
を備えており、
入力されたエンティティペア(Ａ，Ｂ)に対応するペアＩＤを取得し、前記取得されたエンティティペアＩＤを用いてエンティティペア(Ａ，Ｂ)に対応する語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）・語彙パターンの頻度を取得して第１特徴ベクトルを形成し、
前記第１特徴ベクトルの語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）を含み、かつエンティティＣのＩＤを含む候補ペアＩＤを取得し、
各候補エンティティペアＩＤに対応する第２特徴ベクトルを取得し、前記第２特徴ベクトルが前記第１特徴ベクトルと類似するようなエンティティペア(Ｃ，Ｘ)を取得する、
請求項２９に記載の検索システム。
【請求項３１】
前記第４インデックスは、
エンティティペアＩＤから語彙パターンＩＤ・語彙パターンの頻度を検索するためのインデックスと、
語彙パターンＩＤからエンティティペアＩＤ・語彙パターンの頻度を検索するためのインデックスと、
を備えている、請求項３０に記載の検索システム。
【請求項３２】
前記検索データベースには、語彙パターンのクラスタが格納されており、各語彙パターンクラスタには、類似あるいは実質的に同一の語彙パターンが含まれている、
請求項２７乃至３１いずれかに記載の検索システム。
【請求項３３】
前記検索データベースには、エンティティクラスタが格納されており、各エンティティクラスタには、類似あるいは実質的に同一のエンティティが含まれている、請求項２７乃至３２いずれかに記載の検索システム。
【請求項３４】
前記エンティティペア（Ｃ，Ｘ）をエンティティペア（Ｘ，Ｄ）に、前記エンティティＣをエンティティＤに置き換えることで、エンティティペア(Ａ，Ｂ)とエンティティＤが入力された場合に、エンティティペア（Ｘ，Ｄ）のエンティティＸ，Ｄ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを検索するシステムとして機能する請求項２７乃至３３いずれかの記載の検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索方法及びシステムに係り、詳しくは、ペアを形成する２つのエンティティにおけるエンティティ間の関係を利用する検索技術に関する。本明細書において、「エンティティ」とは、１つあるいは複数の単語（すなわち語句）であり、典型的には単一名詞、または複数の単語からなる名詞句である。
【背景技術】
【０００２】
近年ＷＷＷ上のデータが膨大に増加しつつある。その膨大な情報の中に、エンティティ間の関係が多数潜在している。従来のキーワードベース検索エンジンは、キーワードを受け取り、そのキーワードを含む文章を見つけ出すことができるが、エンティティ間の関係を検索することは出来ない。従来のキーワードベース検索エンジンでは、ＷＷＷ上の膨大な情報中に潜在的に存在する多くの関係情報を積極的に利用することはできない。
【０００３】
与えられた２つのエンティティの関係を抽出するシステムとして、非特許文献1に示すTextRunnerシステムがある。TextRunnerはエンティティペア(Ａ，Ｂ)を入力として受けたときに、ＡとＢの間に成り立つ述語(predicate)を検索することができる。例えば、(Bush，United States)というエンティティペアを入力すると、is(George W. Bush，President of United States)というis述語を出力する。すなわち、BushとUnited Statesとの関係(is president of)が直接出力されるわけではなく、BushとUnited Statesを含むエンティティ(George W. Bush，President of United States)の間に成り立つ一般的な述語(is)しか出力できない。よって、TextRunnerは２つのエンティティ間の関係を見つけることは出来ず、TextRunnerを用いて関係検索を行なうことは出来ない。
【０００４】
TextRunnerシステムは、教師なし学習による抽出パターン学習手法として、特許文献１に記載されている。この手法では、まず、小さなコーパス(テキストの集合)に対して、構文解析器を走らせて、各文書中の文を構文解析する。そして、その解析結果から、名詞を取り、名詞と名詞との間の関係を構文木から得る。ヒューリスティクスを使い、その関係が抽出すべき関係かどうかを判断し、学習のためのサンプルを作る。例えば、「Oppenheimer taught at Berkeley and Caltech」という文の構文木を利用すれば、(Oppenheimer，taught at，Berkeley)と(Oppenheimer，taught at，Caltech)というパターンは正のサンプルとして、(Berkeley，and，Caltech)は負のサンプルとして判断する。これらのサンプルをtrainingデータとしてNa&iuml;ve Bayes分類器を作る。つまり、ある関係が与えられた時に、その関係が良い（正しい）関係か悪い（正しくない）関係かを判断する分類器である。分類過程で使う特徴は、関係の２つの名詞が固有名詞かどうか、文中の距離や左右にある品詞などである。分類器は小さなコーパスから学習することで、構文解析器を使ってもあまり時間がかからないという利点がある。そして、分類器を学習できた後、膨大なコーパスから抽出された関係が良い（正しい）関係かどうかを、分類器を使い判断することが出来る。この手法により、良い（正しい）関係を抽出でき、本発明には良いベースになるかもしれない。しかし、特許文献１で述べられた手法は関係抽出と検索方法しか与えない。つまり、単語間の関係の抽出方法と単語または関係が与えられたときに関係、未知の単語を検索する方法である。この手法では単語ペア間の関係の類似度などは扱われず、本発明の潜在的関係検索エンジンは実現出来ない。また、特許文献1の検索は本発明と目的が違うため、indexing手法、検索アルゴリズムも本発明とは全く異なっている。更に、学習データを作るため構文解析器を使うことで、言語依存になり、言語リソースの少ない言語(構文解析器がない言語)に対してはうまくパターンを抽出できない可能性が高い。
【０００５】
２つの単語ペアの間の類似度を測定する手法がいくつか提案されている。例えば、非特許文献２で提案されているLRA(latent relational analysis)手法では、２つのエンティティペア((Ａ，Ｂ)，(Ｃ，Ｄ))が与えられた時に、(Ａ，Ｂ)の間の関係を特徴づけるlexical patterns(語彙パターン)頻度ベクトルを、キーワードベース検索エンジンを使って自動的に生成する。また、(Ｃ，Ｄ)も同様に処理し、(Ａ，Ｂ)と(Ｃ，Ｄ)の特徴ベクトルのcosine類似度を測ることにより、(Ａ，Ｂ)と(Ｃ，Ｄ)の関係類似度を測ることが出来る。更に、非特許文献３では、単語ペアの特徴ベクトルをWWWから高速に作成する手法と、関係類似度の精度を上げるために特徴ベクトル次元の削減方法を提案している。
【０００６】
非特許文献２、非特許文献３に開示された手法は本発明の基礎となるが、関係類似度測定システムでは、２つのエンティティペアの完全な４つのエンティティが必要であり、1つのエンティティが未知の場合には測定出来ず、未知のエンティティを持つエンティティペアの特徴ベクトルも出力できない。よって、それらの文献で提案されているシステムだけでは本発明で提案する検索エンジンの機能を実現出来ない。
【０００７】
非特許文献４はWordNetを利用する単語ペア間の類似度を測る手法を提案している。WordNetは図１３で示すような概念辞書である。この辞書を使って、２つの単語間の類似度を次のように定義する。
2011118689.tif 000003
ここで、τ(wi，wj)は単語wiとwjの類似度で、δ(w)は単語wのWordNet階層における深さである。Pijは単語wi，wjの共通上位語(hypernym)である。例えば、図１３の概念“abstract  entity”の深さは1で、Indo-European，Greek，Englishの深さはそれぞれ5，6，8である。そこで、(English，Greek)の類似度は、
2011118689.tif 000004
となる。
そして単語間の類似度を用いて、単語ペア間の類似度を次のように定義する。
2011118689.tif 000005
αとβは重みで、より似ている単語ペアに優先するようにα=2，β=1とする。
この式を使うと、例えば、π((English，A)，(Greek，Zeus))＝0.52で、
π((English，A)，(Greek，Alpha))＝0.82である。つまり、(English，A)と(Greek，Alpha)との類似度は(English，A)，(Greek，Zeus)との類似度よりも大となる。
【０００８】
非特許文献４で述べた手法を使い、関係検索を実現することも考えられる。すなわち、(English，A)と(Greek，?)というクエリがあった時に、EnglishからAまでのパスを探す。そして、そのパスとの共通パスが最長になるようなパス(Greek，?)を検索する。図１３に示すように、この手法を使うと、(English，A)と(Greek，?)というクエリに対する答えは、(Greek，Zeus)ではなく、(Greek，Alpha)や(Greek，Beta)，…のような答えを出すことが出来る。しかし、それだけでは正解「Alpha」という答えを出すことは出来ない。
【０００９】
さらに、関係検索に近い提案として、非特許文献５で提案された「アナロジー・シソーラス(Analogical Thesaurus)」がある。アナロジー・シソーラスとは類似関係にある単語ペアを見つけ出すための階層型概念辞書である。WordNetでは、図1１で示すように、英語の文字とギリシャの文字は共に{LETER，ALPHABETIC_CHARACTER}概念に分類されていて、その区別が全くなく、クエリ{(English，A)，(Greek，?)}に対して答えることが出来ない。
【００１０】
それに対して、非特許文献５で提案されたシソーラスは、WordNetをより詳細に分割するような概念を導入する。図１２に示すように、元々WordNetにあった概念{LETTER，ALPHABETIC_CHARACTER}を詳細に分割するために、新しい概念{GREEK_LETTER}，{ENGLISH_LETTER}や{1st LETTER}を導入する。そこで、クエリ{(English，A)，(Greek，?)}が入力されたときに、システムはこの辞書を引き、{A}の文字の位置を見つけ出す。そして、その位置の先祖ノードには{ENGLISH_LETTER}と{1st LETTER}がある。クエリがEnglishとGreekの対応を探したいので、{ENGLISH_LETTER}の対応として{GREEK_LETTER}が候補である。なぜなら{GREEK_LETTER}と{ENGLISH_LETTER}は先祖ノード{LETTER，ALPHABETIC_CHARACTER}を共通的に持つからである。よって、答えの候補は{GREEK_LETTER}のすべての子ノードであることが分かる。最後に、候補集合から正しい答えを出すために、クエリの“A”のノード{A}とノード{GREEK_LETTER}の子ノードのうち、ノード{ALPHA}がノード{A}と直前の先祖{1st LETTER}を共有するので、答えはノード{ALPHA}を出力する。よって、クエリ{(English，A)，(Greek，?)}の出力は“ALPHA”(文字α)である。出力の導出過程を見て分かるように、その理由はAはEnglishの1番目(1st letter)の文字であり、αはGreekの1番目の文字である。従って、非特許文献５で提案されたシソーラスは関係検索を直接対応できる。
【００１１】
しかしながら、この方法を使うと、検索システムの能力が大変限られる。なぜなら、正確に検索できるためにはWordNetに新しい概念(詳細分割ための概念)を導入する必要があり、それらの概念を自動的に導出する方法があるが、精度がよくなく、これが最終結果の再現率を減らす大きな原因になってしまう。また、更に悪いのはWordNetに存在しない原始概念(つまり子ノードを持たない概念)に対しては検索できない。例えば、WWWでは頻繁に新しい概念(人名、組織名など)が出てくるが、アナロジー・シソーラスではこれに対応できない。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】M. Banko and O. Etzioni. TheTradeoffs Between Open and Traditional Relation Extraction, Proceedings of ACL,pp.28-36 (2008).
【非特許文献２】Peter D. Turney. Measuring SemanticSimilarity by Latent Relational Analysis. Proceedings of International JointConf. on Artificial Intelligence (IJCAI), pp.1136-1141 (2005).
【非特許文献３】Danushka Bollegala, Yutaka Matsuo andMitsuru Ishizuka: Measuring the Similarity between Implicit Semantic Relationsfrom the Web , Proceedings of the 18th International World Wide Web Conference(WWW 2009), pp. 651-660(2009).
【非特許文献４】Tony Veale. WordNet Sits theS.A.T. - A Knowledge-Based Approach to Lexical Analogy. Proceedings of the 16thEuropean Conf. on Artificial Intelligence (ECAI), pp.606-612 (2004).
【非特許文献５】Tony Veale. The AnalogicalThesaurus. In Proceedings of the Fifteenth Conference on InnovativeApplications of Artificial Intelligence (IAAI), pp.137-141 (2003).
【特許文献】
【００１３】
【特許文献１】US2008/0243479A1.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
上述のように、TextRunnerなどの既存システムではテキストコーパスがあっても、エンティティペア間の関係をうまく表現できない。また、アナロジー・シソーラスは限られた関係検索しか出来なく、膨大なＷＷＷのデータを利用できない。また、関係類似度を測る方法がいくつか提案されたが、そのままでは関係検索を直接実現できない。
【００１５】
本発明は、ＷＷＷなどの膨大なテキストデータから、エンティティペア間の関係を表現し、エンティティペア間の関係を用いて関係検索を実現することを目的とするものである。
【課題を解決するための手段】
【００１６】
本発明が採用した第１の技術手段は、エンティティのペア(Ａ，Ｂ)とエンティティＣが入力された場合に、エンティティのペア（Ｃ，Ｘ）のエンティティＣ、Ｘ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを、検索データベースあるいは／および既存の検索エンジンを用いて、検索する方法であって、
エンティティのペア(Ａ，Ｂ)とエンティティＣをクエリとして受け取り、
エンティティＡとエンティティＢとの間の関係を、エンティティＡとエンティティＢを含むテキストにおけるエンティティＡ，Ｂの周辺の文脈に依存して規定し、
エンティティＡ，Ｂの周辺の文脈と同一あるいは類似の文脈を周辺に備えたエンティティＣ，Ｘを探索することで、エンティティＣとの間において、エンティティＡとエンティティＢの関係と同一または類似の関係を備えるエンティティＸを取得する、関係検索方法、である。
【００１７】
「エンティティ」とは、１つあるいは複数の単語、すなわち語句である。
本発明は、 (A,B)と関係類似度（relational similarity）が大となる(C,X)を関係類似度によりランキングして求める手法である。
本発明において、エンティティＸの位置は限定されず、例えば、エンティティペア（Ｘ，Ｄ）は、エンティティペア（Ｃ，Ｘ）と同様に扱うことができる。すなわち、エンティティのペア(Ａ，Ｂ)とエンティティＤがクエリとして入力された場合に、前記エンティティペア（Ｃ，Ｘ）をエンティティペア（Ｘ，Ｄ）に、前記エンティティＣをエンティティＤに置き換えることで、エンティティペア(Ａ，Ｂ)とエンティティＤが入力された場合に、エンティティペア（Ｘ，Ｄ）のエンティティＸ，Ｄ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを検索する手法として機能する。
【００１８】
１つの態様では、前記文脈は、語彙パターン、bag-of-words、品詞パターン、係り受けパターンの１つあるいは任意の組み合わせである。
【００１９】
１つの態様では、前記文脈はクラスタリングされ、各文脈クラスタには、実質的に同一あるいは類似の文脈が含まれる。
【００２０】
１つの態様では、エンティティのペアの２つのエンティティ間の関係は、特徴ベクトルによって表現され、前記特徴ベクトルは、前記エンティティペアの２つのエンティティの周辺の文脈あるいは文脈クラスタから取得される。
【００２１】
１つの態様では、エンティティＡとエンティティＢとの間の関係は、第１の特徴ベクトルによって表現され、第１の特徴ベクトルは、エンティティＡ，Ｂの周辺の文脈あるいは文脈クラスタから取得され、
エンティティＸを取得するステップは、エンティティＣとの間において、第１の特徴ベクトルと同一あるいは類似の第２の特徴ベクトルを備えるエンティティＸを取得するものであり、第２の特徴ベクトルは、エンティティＣとエンティティＸを含むテキストにおけるエンティティＣ，Ｘの周辺の文脈あるいは文脈クラスタから取得される。
【００２２】
１つの態様では、前記エンティティＸを取得するステップは、
ペア(Ａ，Ｂ)と各ペア(Ｃ，Ｘ)のペア間の類似度を、両者の特徴ベクトル間の距離に基づいて算出し、算出されたペア間類似度（関係類似度）を指標として、ペア間類似度が大きい順に複数のペア(Ｃ，Ｘ)をソートし、ソート順にＸの候補をランキングするステップと、
ランキングされたＸの一部あるいは全部を検索結果として出力するステップと、
を備えている。
典型的には、関係類似度は特徴ベクトルの間の距離によって算出されるため、まず特徴ベクトルを作成しておく必要がある。１つの態様では、特徴ベクトルは、「パターンの頻度を基にした重み」で定義することができる。
典型的な態様では、関係類似度は、両者の特徴ベクトル間のコサイン類似度に基づいて算出されるが、他の距離尺度を用いてもよい。
【００２３】
１つの態様では、前記文脈は語彙パターンであり、前記特徴ベクトルは語彙パターンの頻度を要素とする。すなわち、「語彙パターンの頻度を基に計算する重み」を特徴量にした特徴ベクトルでエンティティペア間の関係を表現する。
より具体的には、特徴ベクトルの要素は、「特徴(次元)」とその「値(特徴量)」であり、文脈を語彙パターンとした場合には、「特徴（次元）」＝「語彙パターン」、「値（特徴量）」＝「語彙パターンの頻度」、となる。
語彙パターンをクラスタリングする場合には、特徴ベクトルの次元を「語彙パターンクラスタ」とし、各次元の値を「当該語彙パターンクラスタに含まれる語彙パターンの頻度の総和」とする
【００２４】
１つの態様では、前記エンティティＸを取得するステップは、
取得したペア(Ａ，Ｂ)の第１の特徴ベクトルの語彙パターン（頻度が予め設定した閾値より大きい）を要素に含む第２の特徴ベクトルを備えた複数のペア(Ｃ，Ｘ)を取得するステップと、
ペア(Ａ，Ｂ)と各ペア(Ｃ，Ｘ)のペア間の類似度を両者の特徴ベクトルを用いて算出し、算出されたペア間類似度を指標として、ペア間類似度が大きい順に複数のペア(Ｃ，Ｘ)をソートし、ソート順にＸの候補をランキングするステップと、
ランキングされたＸの一部あるいは全部を検索結果として出力するステップと、
を備えている。
【００２５】
１つの態様では、前記検索データベースには、多数のエンティティペアと、各エンティティペアのエンティティ間の関係を表現する周辺の文脈との対応が格納されている。
１つの態様では、前記文脈は語彙パターンであり、前記検索データベースには、多数のエンティティペアと、各エンティティペアと、語彙パターン及び当該語彙パターンの頻度と、の対応が格納されている。
【００２６】
１つの態様では、前記検索データベースは、
エンティティペアの各エンティティのＩＤを規定する第１インデックスと、
２つのエンティティＩＤのペアに対応するエンティティペアＩＤを規定する第２インデックスと、
各語彙パターンに対応する語彙パターンＩＤを規定する第３インデックスと、
エンティティペアＩＤと、語彙パターンＩＤ・語彙パターンの頻度と、の対応関係を規定する第４インデックスと、
を備えており、
入力されたエンティティペア(Ａ，Ｂ)に対応するエンティティペアＩＤを取得し、前記取得されたエンティティペアＩＤを用いてエンティティペア(Ａ，Ｂ)に対応する語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）・語彙パターンの頻度を取得して第１特徴ベクトルを形成するステップと、
前記第１特徴ベクトルの語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）を含み、かつエンティティＣのＩＤを含む候補エンティティペアＩＤを取得するステップと、
各候補エンティティペアＩＤに対応する第２特徴ベクトルを取得し、前記第２特徴ベクトルが前記第１特徴ベクトルと類似するようなエンティティペア(Ｃ，Ｘ)を取得するステップと、
を備えている。
１つの態様では、前記語彙パターンの頻度の閾値は頻度１である。実際には、低頻度のものはスペルミス等の雑音を含むことが多く、予め閾値を適切に選択して設定しておくことが望ましい。
１つの態様では、前記第４インデックスは、
エンティティペアＩＤから語彙パターンＩＤ・語彙パターンの頻度を検索するためのインデックスと、
語彙パターンＩＤからエンティティペアＩＤ・語彙パターンの頻度を検索するためのインデックスと、
を備えている。
【００２７】
１つの態様では、前記検索データベースにおいて、語彙パターンは、語彙パターンのクラスタを形成しており、各語彙パターンクラスタには、類似あるいは実質的に同一の語彙パターンが含まれている。
１つの態様では、前記エンティティペア(Ｃ，Ｘ)を取得するステップは、エンティティペア(Ａ，Ｂ)の特徴ベクトルの語彙パターンと同一の語彙パターン（頻度が予め設定した閾値より大きい）を要素とする特徴ベクトルを備えたエンティティペア(Ｃ，Ｘ)のみならず、エンティティペア(Ａ，Ｂ)の特徴ベクトルの語彙パターンが属する語彙パターンクラスタに属する語彙パターン（頻度が予め設定した閾値より大きい）を要素とする特徴ベクトルを備えたエンティティペア(Ｃ，Ｘ)を探索するステップを含む。
【００２８】
１つの態様では、前記検索データベースにおいて、類似のエンティティからなるエンティティクラスタが形成されている。
１つの態様では、前記エンティティＸの候補のランキングの指標となるスコアとして、前記エンティティＸが属するエンティティクラスタのスコアを用いる。
１つの態様では、前記出力ステップにおいて、前記エンティティクラスタに含まれる複数のエンティティを出力する。前記エンティティクラスタのスコアは、当該エンティティクラスタに含まれる各エンティティのスコアの総和をエンティティクラスタサイズで割って正規化したクラスタ平均スコアである。
【００２９】
１つの態様では、エンティティペアのエンティティ間の関係を表現する特徴ベクトルは、
テキストコーパスから取得した文を単語に切り分け、
切り分けられた単語から候補エンティティペアを作成し、
候補エンティティペアの周辺の文脈から取得される。
【００３０】
１つの態様では、前記特徴ベクトルの要素は、語彙パターンの頻度であり、
語彙パターンの頻度の抽出は、
候補エンティティペアが含まれる元の文において、エンティティペアの第１エンティティをＸに、第２エンティティをＹに置き換えて、Ｘ，Ｙを含む部分列Ｓを生成し、部分列Ｓのn-gram(nは1からＫまで)を生成するステップと、
得られたn-gramを特徴ベクトルの１つの次元として、エンティティペアを含む全ての文において頻度を数えるステップと、
を備え、
n-gramの頻度を語彙パターンの頻度として、エンティティペアと関連付けて保存する。
ここで、部分列Ｓは、Ｘの直前のｍ１個の単語，Ｘ，ＸＹ間の単語列（Ｘ，Ｙを除く），Ｙ，Ｙの直後のｍ２個の単語、からなる単語列である。ｍ１、ｍ２、Ｋは、パラメータ（整数）である。
ＸＹ間の単語列（Ｘ，Ｙを除く）の長さをＤとした時、１つの態様では、ＤがＫ−２よりも大きい場合、さらに、[Ｘ, (Ｘ, Ｙ)間の列，Ｙ]のn-gramも生成する。
１つの態様では、前記候補エンティティペアの２つエンティティ間の距離Ｄが、閾値Ｄｔｈ以下の場合にのみ候補エンティティペアの周辺の文脈を取得する。この距離Ｄは、単語数である。
１つの態様では、前記候補エンティティペアを作成するステップにおいて、固有名詞を含むエンティティペアを候補エンティティペアとして優先的に抽出する。
１つの態様では、前記候補エンティティペアを作るステップにおいて、頻度の高いエンティティペアを候補エンティティペアとして優先的に抽出する。
１つの態様では、類似あるいは実質的に同一の語彙パターンから語彙パターンのクラスタを形成するステップを含む。
【００３１】
１つの態様では、本発明の検索方法は、既存の検索エンジンを用いて、エンティティＡとエンティティＢを含むテキストにおけるエンティティＡ，Ｂの周辺の文脈を取得するステップと、
既存の検索エンジンを用いて、エンティティＡ，Ｂの周辺の文脈と同一あるいは類似の文脈を備えたエンティティＣ，Ｘを取得するステップと、
を備えている。
検索データベースにクエリとして与えたエンティティが存在する場合と存在しない場合では検索システム内部の処理が変わる。エンティティＡ，Ｂ，Ｃの１つあるいは複数が検索データベースに存在しない場合、既存のキーワードベースWeb検索エンジンを用いて、動的にエンティティＡ，Ｂの間の関係を表す語彙パターンを抽出し、エンティティＣでその語彙パターンと関連付けられるエンティティＸを抽出し、ランキングする。
【００３２】
１つの態様では、エンティティＡ，Ｂの周辺の文脈は、エンティティＡとエンティティＢの間の距離を制限したエンティティＡ、エンティティＢをクエリとした前記検索エンジンの検索結果としてのスニッペト(snippet)から取得する。
具体的には、ここでの検索は、エンティティＡとＢの間に所定数の＊（＊：０個あるいは１個の単語に対応するワイルドカード）を挿入して作成したクエリ（例“A * * * B”）を用いた検索である。通常のキーワード検索エンジンでは、エンティティＡ，Ｂをクエリとして入力した場合には、エンティティＡ，Ｂを含むスニペットが得られるようになっており、ここでのワイルドカード検索は、単なるエンティティＡ，Ｂをクエリとする入力に、エンティティＡ、Ｂ間の距離を制限するものであると言える。したがって、クエリ（例“A * * * B”）で検索すると、エンティティＡとＢの前後の文脈も含むスニペットが得られて、そのスニペットからエンティティＡとＢの前後（外側）の文脈を含む語彙パターンを生成することができる。「＊」の個数は、適宜、当業者によって予め設定される。
【００３３】
１つの態様では、前記エンティティＡ，Ｂの周辺の文脈は、上記スニペット（“A
* * * B”などをクエリとして得られたスニペット）から抽出される語彙パターンである。
エンティティＸの候補は、抽出された語彙パターンにエンティティＣを代入して得られるクエリの検索結果としてのスニッペトから取得する。
当初の検索クエリが(Ａ, Ｂ), (Ｃ, ？)である場合、ここでのクエリは、エンティティＣ、語彙パターン(pattern)、？の順序を保持したクエリ“C pattern *”となる。当初の検索クエリが(Ａ, Ｂ), (？, Ｄ)である場合、ここでのクエリは、？、エンティティＤ、語彙パターンの順序を保持したクエリ“* pattern Ｄ”となる。
クエリ“C pattern *” を入力すると、多くの既存の検索エンジンは、“C pattern W1” (W1はある１個の単語(日本語では文字))だけを返すわけではなく、そのクエリとマッチされたテキストのsnippetでは文脈も返される。したがって、実際には、”… C pattern W1 W2 W3 …” (* のところはW1に対応する) が返ってくる。そこで、Dの候補は W1 または W1 W2 または W1 W2 W3 などとすることが出来る。
【００３４】
本発明が採用した第２の技術手段は、エンティティのペア(Ａ，Ｂ)とエンティティＣが入力された場合に、エンティティのペア（Ｃ，Ｘ）のエンティティＣ、Ｘ間にエンティティＡ，Ｂ間の関係と同一または類似の関係があるようなエンティティＸを検索するシステムであって、
前記検索データベースには、多数のエンティティペアと、各エンティティペアのエンティティ間の関係を表現する周辺の文脈との対応が格納されており、
エンティティのペア(Ａ，Ｂ)とエンティティＣをクエリとして受け取る手段と、
エンティティＡとエンティティＢとの間の関係を表現する第１の周辺の文脈を、前記検索データベースを用いて取得する手段と、
第１の周辺の文脈と同一あるいは類似の第２の周辺の文脈を備えたエンティティＣ，Ｘを、前記検索データベースを用いて探索することで、エンティティＣを取得する手段と、
を備えている、検索システム、である。
【００３５】
１つの態様では、前記文脈は語彙パターンであり、前記検索データベースには、多数のエンティティペアと、各エンティティペアと、語彙パターン及び当該語彙パターンの頻度と、の対応が格納されている。
１つの態様では、前記検索システムは、
取得したエンティティペア(Ａ，Ｂ)の第１の特徴ベクトルの語彙パターン（頻度が予め設定した閾値より大きい）を要素に含む第２の特徴ベクトルを備えた複数のエンティティペア(Ｃ，Ｘ)を取得する手段と、
エンティティペア(Ａ，Ｂ)と各エンティティペア(Ｃ，Ｘ)のペア間の類似度を両者の特徴ベクトルを用いて算出する手段と、
算出されたペア間類似度を指標として、ペア間類似度が大きい順に複数のエンティティペア(Ｃ，Ｘ)をソートし、ソート順にＸの候補をランキングする手段と、
ランキングされたＸの一部あるいは全部を検索結果として出力する手段と、
を備えている。
【００３６】
１つの態様では、前記検索データベースは、
エンティティペアの各エンティティのＩＤを規定する第１インデックスと、
２つのエンティティＩＤのペアに対応するエンティティペアＩＤを規定する第２インデックスと、
各語彙パターンに対応する語彙パターンＩＤを規定する第３インデックスと、
エンティティペアＩＤと、語彙パターンＩＤ・語彙パターンの頻度と、の対応関係を規定する第４インデックスと、
を備えており、
入力されたエンティティペア(Ａ，Ｂ)に対応するエンティティペアＩＤを取得し、前記取得されたエンティティペアＩＤを用いてエンティティペア(Ａ，Ｂ)に対応する語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）・語彙パターンの頻度を取得して第１特徴ベクトルを形成し、
前記第１特徴ベクトルの語彙パターンＩＤ（語彙パターンの頻度が予め設定した閾値より大きい）を含み、かつエンティティＣのＩＤを含む候補ペアＩＤを取得し、
各候補ペアＩＤに対応する第２特徴ベクトルを取得し、前記第２特徴ベクトルが前記第１特徴ベクトルと類似するようなエンティティペア(Ｃ，Ｘ)を取得する。
１つの態様では、前記第４インデックスは、
エンティティペアＩＤから語彙パターンＩＤ・語彙パターンの頻度を検索するためのインデックスと、
語彙パターンＩＤからエンティティペアＩＤ・語彙パターンの頻度を検索するためのインデックスと、
を備えている。
【００３７】
１つの態様では、前記検索データベースには、語彙パターンのクラスタが格納されており、各語彙パターンクラスタには、類似あるいは実質的に同一の語彙パターンが含まれている。
１つの態様では、前記検索データベースには、エンティティクラスタが格納されており、各エンティティクラスタには、類似あるいは実質的に同一のエンティティが含まれている。
【発明の効果】
【００３８】
本発明は、膨大なテキストコーパスから有益なエンティティ間の関係を特徴ベクトルで表現し、それに基づいて、関係検索を実用的に実現することができる。また、本発明の手法は膨大なデータ源に対応できる。つまり、膨大なWWWなどの情報空間の中で関係検索ができ、いわゆる大規模なWeb-scaleに対応できる。
【００３９】
本発明の検索データベース作成によるindexing技術は、検索時間を削減するために重要である。indexing技術により検索データベースを作成しておくことで、本システムでは高速で待ち時間の少ない関係検索を実行することができる。
【００４０】
潜在的関係に基づく本発明の関係検索エンジンを使うと、様々な問題が解決できる。例えば、質問応答システムでは、入力質問に対して、システムが答えを教えるが、システムの知識ベースの中に存在しない知識に対しては答えを出すのが難しい。本発明の検索システムを使えば、少ない知識しか持たない場合も、幅広い質問を答えることが出来る。例えば、「東京が日本の首都」という知識が予めあるとする（例えば、首都 (日本、東京)という一階述語論理式が知識ベースにある）。そのとき、「フランスの首都は何か」という質問に対して、その答えはクエリ{(日本、東京)，(フランス，?)}の結果であり、フランスの首都という知識(論理式：首都(フランス、パリ))はシステムが予め持たなくても、WWWやテキストコーパスを利用するだけで、答えを出すことが出来る。
【００４１】
また、本検索エンジンは類似語の検索なども簡単に実現でき、シソーラスの作成を支援するシステムにもなる。例えば、クエリとして、{(Ａ，Ｂ)，(Ｃ，？)}を入れ、(Ａ，Ｂ)の関係が類似語であれば、?検索結果として求まるＤはＣの類似語であるという可能性が高い。同様に、類似語だけではなく、上位下位語(hypernyms，hyponyms)、反対語や部分一部関係にある語(meronyms)の検索もできる。
【００４２】
更に、実際にすぐ利用できる応用として、製品メーカ検索などが挙げられる。例えば、電子商取引ウェブサイトでユーザは「化粧品ならば資生堂が有名」と分かっているが、「ゲーム機ならばどのメーカが良いのか」を探したい。その時に、本システムに(化粧品, 資生堂) と (ゲーム機, ? )というクエリを入力したら、有名なゲーム機メーカのリストを得ることが出来る。
【００４３】
膨大なWWWなどの情報空間の中で関係検索を行うことで、最新のデータ(知識)についても処理でき、新しい概念や情報にも対応できる。また、クエリに対して複数の候補をユーザに提示することもできる。
従って、本発明で開発される検索エンジンの応用範囲が広い。
【図面の簡単な説明】
【００４４】
【図１】本発明の検索方法及びシステムの概念を示す図である。
【図２】本発明の検索方法及びシステムの検索画面を示す図である。
【図２Ａ】クエリ(steve jobs, apple), (?,microsoft) の簡易結果 (証拠文章を含まない結果)の表示画面である。
【図２Ｂ】図２Ａの表示画面において、証拠文の一部のみを示したものである。また、 Debug Info に語彙パターンの一部を示している。
【図２Ｃ】クエリ (steve jobs, apple), (steveballmer, ?) 簡易結果 (証拠文章を含まない結果)の表示画面である。
【図３】本発明の検索方法及びシステムの全体構成を示す図である。
【図４】エンティティペアと特徴ベクトルとの関係を示す図である。
【図５】品詞タグ付けを示す図である。
【図６】（ａ）エンティティとエンティティＩＤの対応、（ｂ）エンティティペアとエンティティペアＩＤの対応を示す図である。
【図７】語彙パターンと語彙パターンＩＤの対応のテーブルを示す。
【図８】エンティティペアから、そのエンティティペアを含むような語彙パターンとその頻度の情報を保存しているテーブルを示す。
【図９】図８をＩＤで表現したテーブルである。
【図１０】語彙パターンIDからその語彙パターンを特徴ベクトルの１つの成分として含むエンティティペアIDと頻度のリストへのマッピングのテーブルを示す。
【図１１】WordNet（概念辞書）を示す図である(非特許文献５)。
【図１２】WordNet（概念辞書）を詳細分割する概念の導入後を示す図である(非特許文献５)。
【図１３】WordNet（概念辞書）中のパスを示す図である。
【発明を実施するための形態】
【００４５】
［Ａ］検索方法及びシステムの概要
本発明に係る検索システムは、図１に示すように、２つのエンティティペア{(Ａ，Ｂ)，(Ｃ，？)}がクエリとして入力され、「?」として適切なエンティティを検索する。検索システムの出力「？」は、(Ａ，Ｂ)のエンティティＡ，Ｂ間の関係と似ている関係を持つ(Ｃ，Ｘ)となるようなエンティティＸである。典型的には、エンティティＸは、ランキングされたリストとして得られる。例えば、本検索システムは、入力として{(日本、東京)，(フランス，?)}の3つのエンティティ（単語）が与えられた時、最上位の結果として、「パリ」を「?」として出力する。つまり、「日本」と「東京」の関係は「フランス」と「パリ」の関係とよく似ていることを示している。本明細書においては、簡便のため入力形式を{(Ａ，Ｂ)，(Ｃ，？)}として説明するが、本発明において、「?」の記号は各エンティティペアのどの位置にも設定できる。本検索システムのクエリは、例えば、{(？，Ｂ)，(Ｃ，Ｄ)}のような入力形式であってもよい。
【００４６】
上記のようなクエリに答えるためには、エンティティＡとエンティティＢの間の関係を抽出し、それらの関係を持つ他のエンティティペア(Ｃ，Ｘ)をデータベースから検索する必要がある。しかし、本検索エンジンが検索対象とするＷＷＷやテキストコーパスはある大きなテキストデータでしかなく、エンティティ間の関係は全く事前に準備されていない。そのため、エンティティペア(Ａ，Ｂ)におけるエンティティＡとエンティティＢの関係は事前に明示されたものではなく、潜在的である。本発明では、そのような潜在の関係を特徴ベクトルで表現し、２つエンティティペアの間の関係類似度、いわば潜在関係類似度(latent relational similarity)、を測ることにより、関係検索を実現する。
【００４７】
本発明は、与えられたエンティティペア(Ａ，Ｂ)(これを「stem語ペア」という)のエンティティＡ、Ｂ間に潜在的な関係がある場合、与えられた3つ目のエンティティ(Ｃ)で、エンティティペア(Ｃ，Ｘ)または(Ｘ，Ｃ)のエンティティＣ，Ｘ間にも類似の潜在関係を持つようなエンティティＸをＷＷＷやテキストコーパスから検索する。(Ｘ，Ｃ)を検索する問題と(Ｃ，Ｘ)を検索する問題は本質的に違わないので以下では(Ｃ，Ｘ)の検索を想定する。
【００４８】
先ず、与えられたstem語ペア(Ａ，Ｂ)のエンティティＡ，Ｂ間に潜在的に存在する関係を表現する特徴をテキストコーパスから見つけ出す。エンティティＡ，Ｂ間の関係は、エンティティＡとエンティティＢを含むテキストにおけるエンティティＡ，Ｂの周辺の文脈に基づいて抽出することができる。周辺の文脈をどのように把握するかについては、幾つかの手法が考えられ、エンティティＡ，Ｂの周辺の語彙パターン、bag-of-words、品詞パターン、係り受けパターンの１つあるいは任意の組み合わせを例示することができる。１つの態様では、これらの周辺文脈(語彙パターン、bag-of-words、品詞パターン、係り受けパターン等)を多数のエンティティペアに対して予め取得し、エンティティペアと周辺文脈を対応させてデータベースとして保存しておく。あるいは、周辺文脈をクエリ時にon-the-flyで取得することもできる。
【００４９】
語彙パターン(lexical pattern)とは、文中における順序を保った語彙の列である。例えば、文中に現れた語彙のn-gramが語彙パターンである。bag-of-wordsとは、語順に捉われずに単語の集合として扱う手法である。
【００５０】
品詞パターンについて簡単に説明する。例えば、Obama  is  the  president  of  the  U.S.という文の中で、
Obama/PERSON
is/VBZ the/DT president/NN of/IN the/DT U.S./LOCATION
ここで、VBZ:動詞-３人称単数、DT:限定詞、NN:名詞（単数または不可算名詞）、IN:前提詞または従属接続詞）と解釈されたときに、ObamaとU.S.の関係(エンティティペア(Obama, U.S.) の特徴)を表す
1つの語彙パターンは 「is the president of the」、
１つの品詞パターンは 「VBZ DT NN IN DT」、となる。
品詞パターンが同じであればエンティティペアのエンティティ間の関係が類似する可能性がある。例えば、上記の文と下記の文の品詞パターンは同じある。
Obama  is  the  leader  of  the  U.S.
【００５１】
係り受けパターンとは、その文の中の係り受け解析した結果のパターンである。係り受け解析の結果は各エンティティ（単語）の文中の役割と関係を表すので、係り受けパターンが同じであれば、エンティティペアも関係する可能性がある。例えば、
Obama  is  the  president  of  the  U.S.、
Junichiro  Koizumi  was  the  prime  minister  of  Japan、
という文については、品詞パターンが全く同じではないが、係り受けパターン:
PERSON<--subject--VERB(be)--object-->NOUN--of-->LOCATION、
は共通するので、(Obama,  U.S),  (Junichiro  Koizumi,  Japan)の間に何らかの関係があると考えられる。上記の表現は依存関係を矢印で表したもので、矢印のラベルが関係の名前である。つまり、PERSON(Obama,  Junichiro  Koizumi)は動詞(be)に依存する関係があり、また、名詞(president,  prime  minister)も動詞に依存する。更に、LOCATION (U.S.,  Japan)は真ん中の名詞(president,  prime  minister)に依存する。
【００５２】
本発明において、典型的には、エンティティペアの周辺の文脈として、エンティティペアの周辺の語彙パターンを用いるが、品詞パターンや係り受けパターンを用いてもよい。但し、Webの膨大かつnoisyなデータを高度な言語処理（係り受け解析）するときの処理時間および精度の問題を考えると、語彙パターンのみを用いることが有利である。例えば、本発明において動的モードで検索を行う場合には、キーワードベース検索エンジン出力のスニペットは完全な文でないことも多いため、形態素や構文の解析がうまくいかないこともある。
【００５３】
一つの態様では、エンティティＡ，Ｂ間の関係を表現する特徴として、エンティティＡ，Ｂが同時に出現する文中の語彙パターン(lexical patterns)を用いる。例えば、コーパスの中で「アメリカの大統領オバマ」という句がある時、“の大統領”という語彙パターンを抽出し、このパターンをエンティティペア(アメリカ，オバマ)における「アメリカ」と「オバマ」との間の潜在的な関係を特徴づけるパターンの１つとする。エンティティペアのエンティティ間の関係を特徴付けるパターンは複数存在し得るので、その特徴的なパターンを頻度のベクトルとして表現する。本手法では、Webやテキストコーパスからエンティティペアのエンティティ間における潜在的な関係を特徴ベクトル（本実施形態では、語彙パターンの頻度ベクトル）として表現する。
【００５４】
stem語ペアが与えられた時、stem語ペアのエンティティ間の関係を表現する特徴ベクトルとよく似ている特徴ベクトルを備え、かつ、3つ目のエンティティＣを1つの要素として持つようなエンティティペアを見つけ出す。見つけ出したエンティティペアのもう1つの要素(Ｃではないエンティティ)が答えの候補である。それらの候補エンティティペアとstem語ペアとの類似度を測り、類似度でソートし、ソートされたリストから結果を出力する。
【００５５】
本発明の１つの態様では、更に、特徴ベクトルの次元（例えば、語彙パターン）をクラスタリング手法によって減らし、ノイズや出現頻度の少ないパターンの問題（data sparseness problem）を解決する。
【００５６】
検索したいエンティティが固有名詞などの場合、その表現の仕方が複数に存在する可能性がある(例えば、「United States」、「U.S.」、「U.S.A.」はすべて米国を指す固有名詞であるが、その表現形式が異なっている)。本発明の１つの態様では、それらの複数表現形式(surface form)のエンティティについてもクラスタリング手法を使い、できるだけ異なる表現形式も１つのエンティティとして扱うことにより、検索の精度と再現率を上げることを図る。
【００５７】
本発明に係る検索システム（具体的な構成例を図３に示す）は、一つあるいは複数のコンピュータから構成されており、当該コンピュータは、ハードウェアとしての処理手段（ＣＰＵ等）、記憶手段（ハードディスク、ＲＡＭ、ＲＯＭ等）、入力手段、出力手段ないし表示手段、ソフトウエアとしてのコンピュータを動作させる制御プログラム等を備えている。ユーザ端末も、一つあるいは複数のコンピュータから構成されており、当該コンピュータは、処理手段、記憶手段、入力手段、出力手段ないし表示手段、コンピュータを動作させる制御プログラム等を備えている。検索システムとユーザ端末は、インターネットに代表されるコンピュータネットワークを介して相互に情報のやり取りを可能とする送受信手段を備えており、インターネットに代表されるコンピュータネットワークを介して互いに通信可能に接続されている。検索システムは、インターネットに代表されるコンピュータネットワークを介して既存のキーワードベース検索エンジンに接続されている。ユーザ端末の画面には、例えば、図２のような検索画面が表示され、ユーザ端末の入力手段からエンティティを入力し、検索クエリとして検索システムへ送信する。検索システムでは、検索クエリに基づいて検索結果を計算し、ユーザ端末から閲覧可能とする。
【００５８】
［Ｂ］検索方法及びシステムの具体的な内容
語彙パターン（lexical pattern）生成、語彙パターンクラスタリング、エンティティペア間の類似度計算、エンティティペアのインデクシング、関係類似度による検索、リモートコーパスを用いたクエリ時の動的処理、について説明する。
【００５９】
［Ｂ−１］語彙パターン（lexical pattern）生成
テキストコーパスから、エンティティペアのエンティティ間の関係を表現するための特徴ベクトルを定義し、特徴ベクトルを具体的に作成する。特徴ベクトルの要素は、エンティティ間の関係を表現する語彙パターン(lexical patterns)の頻度である。例えば、「アメリカの大統領オバマ」を含む文が10回出現し、「アメリカの議員オバマ」を含む文が8回出現した時、エンティティペア(アメリカ，オバマ)の特徴ベクトルは図４の列ベクトルＶ１のように表現される。そのペアに含まれない語彙パターンの頻度は0とする。
【００６０】
特徴ベクトルの作成には幾つかのやり方がある。第１に、テキストコーパスが予めあって、それを解析することにより、特徴ベクトルを事前に(クエリ前に)作成しておくことができる。第２に、テキストコーパスがなくても、通常のキーワードベース検索エンジンを使い、“アメリカ***オバマ”（ここで「*」演算子は１個ないしゼロ単語とマッチングするワイルドカード）のようなクエリをキーワードベース検索エンジンに送信し、得られたスニッペト(snippet)結果から語彙パターンを抽出し、特徴ベクトルを作成することができる。すなわち、クエリが分かった時に、クエリに関連するエンティティ間の関係を、既存のキーワードベース検索エンジンを利用して、オンライン(実時間)で抽出してもよい。
【００６１】
特徴ベクトルを生成する際に、特に重要なのはエンティティ間の語彙パターンである。精度の高い関係検索を行うには、エンティティ間の関係を含む文脈において当該関係を表現する語彙パターンをより正確に抽出することが重要である。以下に、語彙パターンのクエリ前処理について説明する。
【００６２】
クエリ前処理するコーパスは、検索システムのローカルハードディスクにあるローカルコーパス(local diskにあるテキストの集合やWWWページなど)である。このようなテキストコーパスには、大量のエンティティとそれらの間の潜在的な関係が含まれている。
【００６３】
これらのテキストをまず文単位に切る。そして、それらの文を単語に分けて、品詞をつける。この処理は、品詞タグ付け（part-of-speech(POS) tagging）として知られている。例えば、図５に示すように、「東京は日本の首都である」という文があったときに、品詞タグ付け後、<東京/名詞，は/助詞，日本/名詞，の/助詞，首都/名詞，で/助動詞，ある/助動詞>の列が得られる。得られた単語と品詞列から、名詞、動詞、形容詞、形容動詞を取り、それらのエンティティをエンティティペアの要素の候補とする。前記の文では、「東京」、「日本」と「首都」が抽出の候補エンティティになる。
【００６４】
候補エンティティから、候補となるエンティティペアを作る。候補エンティティペアは文の中の順序を保った２つの候補エンティティである。例えば、前記の文であれば、(東京、日本)、(日本、首都)、(東京、首都)という３つのエンティティペアを候補エンティティペアとする。文の中で候補エンティティペアが出現したら、そのエンティティペアを記録し、頻度を増やす。また、そのペアが出現する文の位置(document IDとdocument中の文の位置)も記録する。
【００６５】
候補エンティティとして固有名詞を優先的に抽出するために、ＮＥＲ(Named
Entity Recognizer)を使って、文中の固有名詞を抽出する。エンティティペアに固有名詞があったら、それを記録する。
【００６６】
固有名詞の複数形式(United States，U.S.，USA,…)を１つのエンティティとして扱えるように、それらの表現の仕方をクラスタリングする。つまりクラスタリングした後、United States，U.S.，USAは１つのクラスタに入るようにする。そのために、ある表現形式がどのエンティティと一緒にペアを作るかを調べる。更に、その表現形式を含むエンティティペアの語彙パターンについても調べる。相手のエンティティと語彙パターンが似ている表現形式は１つのクラスタに入ると判断する。例えば、United States，U.S.，USAの表現形式はよく「Barack Obama」と一緒に(United States，Barack Obama)，(U.S.，Barack Obama)，(USA，Barack Obama)というエンティティペアを作る。更に、そのエンティティペアの語彙パターンの中では「President」、「leader」が共通に出現する。従って、「United States」、「U.S.」、「USA」は１つのエンティティである可能性が高い。検索時に、候補エンティティが「U.S.」として見つかれば、「United States」、「USA」のエンティティも候補として含めると再現率を高くすることができる。同様に、
Steve Ballmerについて、
(Steve Ballmer, Microsoft): 50 回出現
(Steve Ballmer, Bill Gates): 10
(Steve Ballmer, Microsoft Corp): 8
...
Ballmerについて、
(Ballmer, Microsoft): 20
(Ballmer, Bill Gates): 15
(Ballmer, Gates): 10
...
という検索結果があれば、Steve BallmerとBallmerは似ているとして１つのクラスタに入るようにクラスタリングする。尚、エンティティクラスタリングにおいて、エンティティの種類によっては、類義語の辞書をデータベースに格納しておき、それを用いることもできる。また、検索結果をユーザに提示する時にも、エンティティ（固有名詞）のクラスタ（クラスタに属する複数の異なる表現形式）を表示すればユーザにとっても分かりやすい。
【００６７】
上記の候補エンティティペアの頻度を全コーパスで数えるために、コーパス全体に対して、上記の処理を実行する。候補エンティティペアを抽出した後、候補エンティティペア及びコーパス中に出現するそれらのエンティティペアの頻度が分かり、更に、どのエンティティペアが固有名詞を含むかも分かる。この処理が終わった後、新しくテキストがコーパスに入るときには、逐次的にそのテキストに同じ処理を施すことにより頻度を更新できる。
【００６８】
取得した候補エンティティペアを使い、語彙パターンを抽出する。その時、固有名詞を含むエンティティペアや頻度の高いエンティティペアの語彙パターンを優先的に抽出する。候補エンティティペアの語彙パターン抽出前に様々なフィルタリング手法（例えば、エンティティペアの出現頻度やエンティティ間の距離を用いる）を使い、ノイズやあまり関係のないようなエンティティペアを発見し、それらのペアを除去する。例えば、頻度の少ないエンティティペア(例えば４回以下)に対しては、ノイズとして認識し、語彙パターン抽出を実行しない。新しいテキストがコーパスに追加されるときに、もしエンティティペアの頻度が４回以上になったら、エンティティペアはノイズではなくなり、通常通りに語彙パターンを抽出する。
【００６９】
語彙パターンを決めるために、先ず、候補エンティティペアの２つエンティティ間のテキストにおける距離Ｄを測る。距離Ｄは単に２つのエンティティ間の単語数とする。距離Ｄが、閾値Ｄthよりも大きいエンティティペアに対しては、エンティティ間の関連性が低いとして、語彙パターンを抽出しない。
【００７０】
閾値Ｄth以下のエンティティペアについて、元の文においてエンティティペアの第１エンティティをＸに、エンティティペアの第２エンティティをＹに置き換えた後、Ｘ，Ｙを含む以下の部分列（単語列）Ｓを取り出し、単語列Ｓのn-gram(nは1からＫまで)を全て生成する。得られたn-gramを特徴ベクトルの１つの次元として、エンティティペアを含む文にわたって頻度を数える。特徴ベクトルはn-gramを次元として、その値はn-gramの頻度である。
部分列Ｓ＝PreX X InXY Y PostY
ここで、PreX は Xの(文中の)直前のｍ1個の単語列で、PostYはYの直後のｍ2個の単語列である。また、InXY は (X, Y)の間の単語列である。１つの態様では、パラメータm1 とm2は５である。InXY が10以下であれば候補ペアとして抽出する(つまり、InXYの長さＤがＤthよりも大きいと抽出しない。)。N-gramの nは１からＫまでとする。１つの態様では、Ｋ＝７である。1つの態様では、ＤがＫ−２よりも大きい(Ｄ＞Ｋ−２、即ち、Ｄ＋２＞Ｋ)の時、(X, InXY, Y)というn-gramも生成する。
【００７１】
以下により具体的に説明する。
エンティティの前後のｍ個の単語、エンティティ間の全ての単語
(ただし、エンティティ間の距離ＤがＤth以内)の n-gram (ｎ＝1,2,3, …,K)を取る。
例えば、
They  discussed  with  Barack  Obama,  president  of  the  United  States  in  December  to  find  a  solution  to  the  problem.
ｍ1 ＝ m2 ＝２、Ｄth＝１０、とすると、
抽出対象となる部分列Ｓは、
Ｓ＝discussed  with  Barack  Obama,  president  of  the  United  States  in  December
となる。
抽出されるn-gramは、
［Ｋ＝７の時（Ｄ＝４,Ｄ＜Ｋ−２］
n = 4:discussed  with  X,；with  X,  president；X,  president  of； ...；the  Y  in  December
n = 6:discussed  with  X,  president  of；with  X,  president  of  the；X,  president  of  the  Y；...
n = 7:discussed  with  X,  president  of  the；with  X,  president  of  the  Y；X,  president  of  the  Y  in；,  president  of  the  Y  in  December
n = 2:discussed  with；with  X；X,；,  president；president  of；of  the；the  Y；Y  in；in  December
また、別の例として、文が:
“They  discussed  with  Barack  Obama,  the  first  African  American  president  of  the  United  States  in  December  to  find  a  solution  to  the problem”
m1＝m2＝２,Ｄth＝１０とすると、抽出対象列
Ｓ＝“discussed  with  X,  the  first  African  American  president  of  the  Y  in  December”
この場合、Ｄ＝８(つまり、”, the  first  African  American  president  of  the”の長さなので、Ｄ＝８である)。また、Ｋ＝７と仮定すると、Ｄ＝８＞Ｋ−２である。
［K = 7の時、 D = 8 > K−2］
抽出されるn-gram は、
ｎ＝1, 2, .., 7のn-gramのすべて(上記の例と同様にｎ＝1から7までのn-gramをすべて生成) と次のパターン:
X,  the  first  African  American  president  of  the  Y(n＝8)
すなわち、ＤがＫ−２よりも大きい場合は、n＝1からＫまでのn-gramの全てに加えて、部分列(X,  InXY,  Y)もn-gramとして抽出する(この部分列はn-gramであるが、nがＫよりも大きい)。
生成されたn-gram の全てを関係を表す特徴として用いる。
１つの態様では、語彙パターン抽出は文を切り出した後に行う。つまり、１つの文から部分列を抽出し、その部分列からn-gramを生成する。１つの態様では、文中にエンティティペアの一方あるいは両方が複数に表れても、置き換えられた出現（ＸないしＹ）は１つだけにするが、同時に置き換えてもよい。
【００７２】
パラメータＤth、ｍ１、ｍ２、Ｋは、閾値として当業者において適宜設定され得るものであり、上述の態様ではＤth ＝10、ｍ１＝５、ｍ２＝５、Ｋ＝７としているが、これらに限定されない。例えば、Ｄth ＝10の場合、エンティティペアが単語10個以上離れている場合には、語彙パターン・特徴ベクトルの抽出を行わない。また、特徴ベクトルを計算するときに、閾値Ｄth を動的閾値（例えば、1 〜10 まで動的に変化可能）としてもよい。また、検索データベースに、所望の語彙パターンが出現できるようにするために、最小の
Ｄthの値を記録してもよい。例えば、「Obama  is  the  president  of  the  USA」 という文について、「X  is  the  president  of  the  Y」が出現するための最小のＤthは5である。もし、Ｄth = 4 であれば、この語彙パターンは出現しないとして、検索アルゴリズムが実行される。
【００７３】
［Ｂ−２］語彙パターンクラスタリング
エンティティペアのエンティティ間の関係を表現する語彙パターンは多数あり、完全に一致する語彙パターンが少ないこともある。例えば、「の大統領」という関係は「国のリーダ」とか、「政府のリーダ」などの形式でも表現され得る。そこで、本実施形態では、パターン一致低頻度の問題を解決するために、非特許文献3で開示されている手法と同様のパターンクラスタリング手法を使う。語彙パターンをクスタリングすることにより、低頻度の問題を解決でき、更に、語彙パターンが完全に一致しなくても、検索の再現率を上げることが出来る。
【００７４】
語彙パターンクラスタリングについて説明する。先ず、語彙パターンを、その語彙パターンと一緒に出現するエンティティペアの頻度ベクトルで表現する。例えばX, the president of Yという語彙パターンが(Barack Obama, USA)で10回、(Vladmir Putin, Russia)で20回出現しているとする。この場合、[10,20]のようなベクトルを作成する。同様に全ての語彙パターンを、それと一緒に出現するエンティティペアの頻度ベクトルで表す。
【００７５】
語彙パターンpを表すベクトルpにおいて、i番目の要素は次式で与えられる。
2011118689.tif 000006
ここで、ｈはエンティティペア（S,T）と語彙パターンpの出現頻度を表す関数である。
【００７６】
次に、語彙パターン同士の類似度をその対応するベクトル間のcosine(コサイン)類似度で計算し「似た語彙パターン同士をクラスタにする」という作業を行う。クラスタリングアルゴリズムとして、非特許文献３の655ページのAlgorithm1を用いる。ここで、非特許文献３に開示のクラスタリング手法は、参照により本明細書に組み込まれる。
【００７７】
簡単に説明すると、まず語彙パターンの集合を、その総出現頻度（全エンティティペアにおける出現頻度の総和）の高い順にソートする。これにより、語彙パターンの頻度順のランキングが得られる。次いで、その先頭から１個ずつ語彙パターンを選択していき、既存の語彙パターンクラスタとの類似度を計算し、最も近い語彙パターンクラスタを探索する。最も近い語彙パターンクラスタとの類似度が予め決められた閾値より大きければ、対象となっている語彙パターンをその語彙パターンクラスタに追加する。そうでなければ対象となっている語彙パターン１個からなる新たな語彙パターンクラスタを作成する。この処理を全語彙パターンに対して行う。
【００７８】
［Ｂ−３］エンティティペア間類似度計算
特徴ベクトルが得られた時に、クエリの答えを検索するためには、２つのエンティティペア間の類似度（この類似度を「関係類似度」という）を、エンティティ間の関係を表現する特徴ベクトルにより定義する必要がある。関係類似度は、特徴ベクトル間の距離によって計算することができる。ここで、２つのエンティティペア間の関係類似度を表現する関数を、
2011118689.tif 000007
で定義する。一つの典型的な態様では、関係類似度として、２つの特徴ベクトルのcosine類似度を用いることができる。また、非特許文献3で提案されている手法を使うことも出来る。また、特徴ベクトル間の距離尺度については、ユーグリット距離、マハラノビス距離等の公知の距離尺度を用いることもできる。
【００７９】
例えば、図４に示すように、(アメリカ，オバマ)のエンティティ（単語）ペアの特徴ベクトルＶ１と(フランス，サルコジ)のエンティティ（単語）ペアの特徴ベクトルＶ２とのcosine類似度は高いので、RelSim((アメリカ，オバマ)，(フランス，サルコジ))の値も高くなる。
【００８０】
類似度計算手法を使えば、エンティティペア(Ａ，Ｂ)の語彙パターンとエンティティペア(Ｃ，Ｄ)の語彙パターンが多く正確にマッチングした時に、それらのエンティティペアの関係類似度が高くなる。しかし、エンティティ間の関係を表現する語彙パターンは多数であり、完全に一致す語彙パターンが少ないこともある。よって、上述の語彙パターンクラスタリングを考慮した類似度計算を行うことが望ましい。
【００８１】
関係類度の計算方法についてより具体的に説明する。関係類似度を計算する２つのエンティティペアをそれぞれ(Ａ,Ｂ)と(Ｃ,Ｄ)とする。まず、エンティティＡとエンティティＢを関連付ける語彙パターンを抽出する。ある語彙パターンpがエンティティペア（Ａ,Ｂ）に対して抽出された回数をh(A,B,p)で表す。
【００８２】
次に、エンティティペア（Ａ,Ｂ）の特徴ベクトルF(A,B)を以下のように構築する。F(A,B)のi番目の要素は、i番目の語彙パターンクラスタCiの中で現れる全パターンpとエンティティペア（Ａ,Ｂ）の出現頻度の総和である。F(A,B)のi番目の要素を式で書けば次のようになる、
2011118689.tif 000008
【００８３】
上記式の意味は次の通りである。まず、語彙パターンクラスタは「同一関係を表すために使われる異なる表現」をまとめることが目的であることに注意されたい。例えば、一国の大統領であるという関係は「X the president of Y」、「Y president X」、「Y’s head of state X」など様々な語彙パターンで表現することが可能である（ここではXは人名、Yは国名）。これらの「同じ意味を表す異なる表層表現」をあたかも同じものとして扱うことによって、一見異なる語彙パターンを使っていてもエンティティペア間の類似度計算に影響を与えることがない。上記式を用いることで、同じ意味を表す異なる語彙パターンが全てベクトルの一つの次元に縮退して現れる。従って、ゼロ頻度問題(sparseness problem)が回避できるという利点がある。語彙パターンのクラスタ数がｎであれば、上記の特徴ベクトルはｎ次元となる。つまり、各々の語彙パターンクラスタは一つの特徴に貢献していることになる。
【００８４】
更に上記式に対してもう一つの工夫を加える必要がある。語彙パターンクラスタの中には膨大なパターンを含むものもあれば、あまりパターンを含まないものも存在する。それは、ある関係を表現するために用いられる語彙パターンの種類は、その関係によって異なるからである。例えば、「最も大きい」という関係（例：ダチョウと鳥）を表すためには「X is a large Y」、「X the largest Y」、「X is a big Y」、「enormous Y X」など書ききれないほど沢山の表現がある。一方、「一国の大統領」というようなかなり明確な関係を表す言い方はそれほど存在しない。上記式は各語彙パターンクラスタの中にどれくらいの数の語彙パターンが存在するか、すなわち、語彙パターンクラスタの大きさを考慮していない。そこで、上記式の右辺を「クラスタ内の全パターンの総和」で割って正規化する。
2011118689.tif 000009
ここでVは全エンティティペアを含む集合である。
【００８５】
［Ｂ−４］エンティティペアのインデクシング(indexing)
検索を実行するためには、ペア同士の類似度測定だけでは不十分である。なぜなら、４番目のエンティティが分かっていないからである。２番目のペアの一方のエンティティが未知であるので、そのエンティティを検索する必要がある。そのために、本実施形態では、出来るだけ多くのエンティティペアをデータベースに保存し、かつ、その特徴ベクトルを予め計算してデータベースに保存する。このことをエンティティペアのindexingという。Indexingの結果は、「エンティティペアからそのエンティティペアのエンティティ間の関係を表現する特徴ベクトルのマッピング」と「語彙パターンからその語彙パターンを含むエンティティペアリストのマッピング」である。より具体的には、「エンティティペア−特徴ベクトルのテーブル」と「語彙パターン−語彙パターンを含むエンティティペアのテーブル」である。エンティティペアのインデクシングにより得られた検索データベースを用いた検索については図３に基づいて後述する。
【００８６】
［Ｂ−５］クエリ処理
関係検索エンジンのクエリ{(Ａ，Ｂ)，(Ｃ，？)}が入力されたときに、(Ａ，Ｂ)の特徴ベクトルを探し、その特徴ベクトルに含まれている語彙パターン(頻度1よりも大きい)を全て求める。
【００８７】
次に、それらの語彙パターンが属する語彙パターンクラスタ(上記のクラスタリング結果)を見つけ出す。そして、それらの語彙パターンクラスタに属する語彙パターンを含む他の単語ペア(Ｃ，Ｄ)を見つけ出し、RelSim((A，B)，(C，D))を指標としてＤの候補をランキングする。ランキングされたDのリストが検索結果である。
【００８８】
また、indexingにより得られた検索データベースに現れないようなエンティティペアについては、次に述べるように、キーワードベース検索エンジンを使い、Web全体のテキストを検索する。この操作は幾分余計な時間が掛かるので、実行の前にユーザの許可などを伺うようにすることが望ましい。
【００８９】
［Ｂ−６］リモートコーパスを用いたクエリ時の動的処理
ローカルコーパスが膨大であっても、全てのクエリをカーバできるとは限らない。したがって、リモートコーパスを使い、ローカルコーパスにないエンティティについても答えを出せるようにする。
【００９０】
リモートコーパスは、クエリが分かった時点で、キーワードベース検索エンジン(Google，Yahoo等)に、”Ａ*****Ｂ”というクエリを送信し、結果として受信したスニペットの集合である。ここで、「*」演算子は１個ないしゼロ単語とマッチングするワイルドカードであり、多くの既存の検索エンジン（例えば、Google，YahooBOSS API）でサポートされている。これらのスニペットのテキストは事前にローカルハードディスクにないので、リモートコーパスと呼ぶ。上記クエリではＡとＢが最大５単語以内で共起する場合のスニペットをダウンロードすることが可能である。通常の既存のキーワード検索エンジンでは、Ａ，Ｂをクエリとして入力した場合には、Ａ，Ｂを含むスニペットが得られるようになっており、ここでのワイルドカード検索は、単なるＡ，Ｂをクエリとする入力に、Ａ、Ｂ間の距離の限定を加えるものであると言える。したがって、クエリ（“Ａ*****Ｂ”）で検索すると、ＡとＢが最大５単語以内で共起すると共に、ＡとＢの前後の文脈も含むスニペットが得られて、そのスニペットからＡとＢの前後の文脈を含む語彙パターンを生成することができる。スニペットを使うことによって実際にＷｅｂから検索結果をダウンロードするためにかかる時間を削減することができる。
【００９１】
リモートコーパスを用いたクエリ時の動的処理は、１つの態様では、入力されたクエリ中の３つのエンティティの少なくとも１つがローカルコーパスにない時に実行する。クエリ中の３つのエンティティがローカルコーパスに存在する場合には、リモートコーパスを用いない。
【００９２】
次に、ダウンロードした文脈の中でＡとＢの全ての出現を変数ＸとＹでそれぞれ置き換える。文脈をlowercaseに変換し、lemmatization（基底形の抽出）を行う。次に、ＸとＹ両方を含む5-gram以下の全てのn-gramを語彙パターンとして選択する。ここで抽出された語彙パターンが既に検索データベースの中に含まれている場合には、その高頻度の語彙パターンを優先的に選択してもよい。
【００９３】
上記の語彙パターン抽出で抽出した語彙パターンで変数ＸにＣを代入し、Ｙに「＊」を代入する。このように、得られた語彙パターンで再びＷｅｂ検索を行う。スニペットの中で「＊」に当てはまる部分をＤの候補として抽出する。尚、「＊」にあてはまる部分から一単語のみではなくbi-gramやtri-gramなども候補として抽出可能である。そうすることによって一単語以上からなるエンティティＤに対しても対応可能である。既述の通り、クエリ“C pattern *”としても、“C pattern W1”だけが返されるわけではなく、文脈として、“… C pattern W1 W2 W3 …”が返されるので、W1, W2, W3 などを候補として利用できる。
【００９４】
この段階ではエンティティＤの候補として様々なエンティティが現れ得る。そこで、多数のエンティティＤの候補をランキングする必要がある。膨大な数の候補のランキング手法としては、以下の手法を例示することができる。
ａ．出現頻度の大きい順にランクづける。
ｂ．何個の異なる語彙パターンで候補として選択されているかでランクづける。
ｃ．その候補Dを使って、(Ａ,Ｂ)，(？,Ｄ)クエリで検索した場合にＣが得られるかどうかでランクづける（逆検索手法）。
ｄ．上記の手法の任意の組み合わせを機械学習を使って学習する。
【００９５】
［Ｃ］検索データベースを用いた関係検索
検索データベースを用いた検索システムの一実施形態について、図３乃至図１０を参照しながら詳細に説明する。なお、説明の簡略のため、エンティティペア及びエンティティＩＤを、単語ペア及び単語ペアＩＤとして記載している。
【００９６】
図３は検索システムの構成を示す図である。データ源はローカルコーパス（Local
corpus）１、および／あるいはリモートコーパス（Remote corpus）２である。ローカルコーパスとは検索システムの記憶部に保存されているコーパスであり、例えば、Wikipediaのデータダンプ（data dump）やクロールしたWWWページなどが含まれる。それに対して、リモートコーパスとは、本検索エンジンの記憶部に存在しないコーパスで、例えば、普通のキーワードベース検索エンジンのクエリ結果が含まれる。リモートコーパスを使うと、本システムでクローリング(crawling)しなくても膨大なWWWなどのデータ源を扱うことが出来る。なお、リモートコーパスを一時的に記憶部に保存してもよい。本明細書では、これらのローカルコーパスやリモートコーパスを一般にテキストコーパスという。
【００９７】
検索クエリを処理する前に、検索するためのデータベースを、テキストコーパスを用いて作成する。図３に示す検索システムのインデクシングエンジン(Indexing Engine)３、パターンクラスタリングエンジン（Pattern Clustering Engine）４が検索データベースを作るモジュールである。インデクシングエンジン３は、トークンナイザ（Tokenizer）３０、エンティティペアセレクタ（Word-Pair Selector）３１、語彙パターン生成器（Lexical Pattern Generator）３２を備えている。インデクシングエンジン３によって、エンティティペアインデックス（Word-Pair Index）５０、語彙パターンインデックス（Pattern Index）５１、特徴ベクトルインデックス（Feature Vector Index）５２、インバーテッドエンティティペアインデックス(Inverted Word-Pair Index)５３の４つのデータベースが作成される。
【００９８】
インデクシングエンジン３は、テキストコーパス１、２からテキストを受け取り、そのテキストをトークンナイザ３０で各単語に分ける。例えば、図５に示すように、トークンナイザ３０が、入力文(東京は日本の首都である)に対して、その文に含まれる単語の品詞付け列 (東京/名詞、は/助詞、日本/名詞、の/助詞、首都/名詞、で/助動詞、ある/助動詞)を出力する。
【００９９】
次に、エンティティペアセレクタ（Word-pair Selector）３１がトークンナイザ３０により生成された単語列を受け取り、エンティティペアを作る。エンティティペアの候補は１つの文の中のすべての名詞、動詞、形容詞、形容動詞を品詞として持つエンティティのペアであるが、最終的には頻度の高いエンティティペアだけがエンティティペアセレクタにより選択され、次のステップに進む。エンティティペアの頻度を保存するテーブルは後述する特徴ベクトルインデックス５２である。
【０１００】
各エンティティに対して唯一的にある整数を対応させる。この整数をエンティティIDという。エンティティからエンティティIDを高速に見つけ出すために、図６(a)のように、エンティティとエンティティIDのハッシュ表を作り、データベースの１つのテーブルに保存する。例えば、東京、フランス、日本、パリ、首都に対して、それぞれ、エンティティＩＤ１、２、３、４、５が割り当てられる。これ以降の処理はエンティティ自身を使わなく、エンティティIDに対する処理だけで済むので、高速で検索したり、保存すべきデータ量を圧縮できたりするという利点がある。また、検索データベースには、各エンティティの頻度と品詞の情報もエンティティＩＤに関連付けて保存される。
【０１０１】
そして、エンティティペアの各候補について、そのペアの２つのエンティティIDをキーとして、図６(b)のハッシュ表を作る。図６(b)はエンティティペアの２つのエンティティIDから、エンティティペアIDにマッピングするテーブルである。図６(b)がエンティティペアインデックス５０の内容である。具体的には、エンティティＩＤ１、エンティティＩＤ３からエンティティペアが形成され、そのエンティティペアにエンティティペアＩＤ１が割り当てられる。同様に、エンティティＩＤ２、エンティティＩＤ４からエンティティペアが形成され、そのエンティティペアにエンティティペアＩＤ２が割り当てられる。
【０１０２】
インデクシングエンジン３の最後のステップでは、語彙パターン生成器３２により、選択されたエンティティペアの語彙パターン(lexical patterns)を生成する。語彙パターンの生成アルゴリズムには、既述の方法を用いることができる。語彙パターン生成器は、図７で示すような、語彙パターンを語彙パターンＩＤ（lexical pattern ID）に対応させるテーブル（Pattern vs. Pattern ID）５１を作る。図７に示すように、語彙パターン「ＸはＹの首都である」には語彙パターンＩＤ１が割り当てられ、語彙パターン「ＸはＹの最大都市である」には語彙パターンＩＤ２が割り当てられ、語彙パターン「Ｙの首都がＸである」には語彙パターン３が割り当てられている。
【０１０３】
さらに、語彙パターンから語彙パターンＩＤの情報だけではなく、語彙パターンの頻度の総数も保存しておく（図８参照）。語彙パターン生成器３２はエンティティペアの語彙パターンの頻度（そのエンティティペアに対する語彙パターンの頻度）も数え、特徴ベクトルインデックスのデータベース５２に保存する。特徴ベクトルインデックス５２は、「エンティティペア」から「エンティティペアの特徴ベクトル」へのマッピングである。概念的には、特徴ベクトルインデックスは図８で示すテーブルである。すなわち、エンティティペアから、そのエンティティペアを含むような語彙パターン（lexical pattern）とその頻度の情報を保存しているテーブルである。図８に示すように、エンティティペア（東京、日本）は、語彙パターン「ＸはＹの首都である」・頻度「１０」、語彙パターン「ＸはＹの最大都市である」・頻度「４」、語彙パターン「Ｙの首都がＸである」・頻度「６」、頻度総数「２０」に対応付けられている。エンティティペア（パリ、フランス）は、語彙パターン「ＸはＹの首都である」・頻度「１２」、語彙パターン「Ｙの首都がＸである」・頻度「３」、頻度総数「１５」に対応付けられている。ここでは、簡単のため、図８には、語彙パターンの全てのn-gramを記載していない。
【０１０４】
語彙パターンに加えて、エンティティペアが含まれる品詞パターンを抽出し、エンティティペアと品詞パターンを対応付けてデータベースに保存してもよい。品詞パターンの抽出は当業者において既知である。１つの態様では、エンティティの品詞 (つまり、このエンティティは一般名詞か、人名か、組織名、地名か)の情報はエンティティクラスタリングに用いることができる。これは、２つのエンティティが異なる品詞(たとえば、人名と地名)であれば、同じクラスタに入る可能性が同じ品詞の場合よりも低いので、類似度を測定するときに、異なる品詞であれば、類似度を普通の類似度の半分にします(異なる品詞ペアにペナルティをつける)。例として、Barack Obama (人名), Obama (人名) の類似度が 0.9 であれば、そのまま類似度 0.9 として数えて、同じクラスタに入れる。しかし、Barack Obama (人名) と Whitehouse (地名) の類似度が 0.9 であっても、品詞が異なるので、類似度を半分にし、0.45 に減じる。そこで、Barack Obama と Whitehouse が同じクラスタに入れなくなる。
【０１０５】
特徴ベクトルインデックスを簡単に検索したり、サイズを圧縮したりするために、エンティティペアのテキストをキーとして直接保存するのではなく、エンティティペアのＩＤ、語彙パターンＩＤを使う。そこで、実際に保存するのは、図９のテーブルである。図９では、エンティティペアＩＤ、語彙パターンＩＤを用いて図８を表現したものである。図６、図７、図９のテーブルを用いることで、図８に示すテーブルを再現することができる。また、stem語ペアから候補のエンティティペアを限定するために、候補エンティティペアはstem語ペアと1つ以上の語彙パターン(あるいは語彙パターンクラスタ)を共有するエンティティペアに限定する。
【０１０６】
その候補エンティティペアの集合を高速に探すために、インバーテッドエンティティペアインデックス（Inverted Word-Pair Index）５３を用意する。インバーテッドエンティティペアインデックスとは、図１０に示すように、語彙パターンIDからその語彙パターンを特徴ベクトルの１つの成分として含むエンティティペアIDと頻度のリストへのマッピングである。図１０に示すように、語彙パターンＩＤ１は、エンティティペアＩＤ１・頻度「１０」、エンティティペアＩＤ２・頻度「１２」、頻度総数「２２」に対応している。語彙パターンＩＤ２は、エンティティペアＩＤ１・頻度「４」、頻度総数「４」に対応している。語彙パターンＩＤ３は、エンティティペアＩＤ１・頻度「６」、エンティティペアＩＤ３・頻度「３」、頻度総数「９」に対応している。このテーブルは特徴ベクトルインデックスのテーブル(図９)との反対方向のindexなので、inverted indexと呼ぶ。
【０１０７】
既述のように、低頻度や完全マッチングの問題を解決するために、語彙パターンのクラスタリングとエンティティクラスタリング(named entity disambiguationの１つの方法)手法を使う。本システムで用いる手法は非特許文献３で提案されたsequential clustering algorithmである。このアルゴリズムによりクラスタリングを実現するモジュールはパターンクラスタリングエンジン４である。パターンクラスタリングエンジン４は特徴ベクトルインデックス５２とインバーテッドエンティティペアインデックス５３を用い、似ている語彙パターンを１つの語彙パターンクラスタにまとめる。似ている語彙パターンとは、その語彙パターンが出現する単語ペアの分布が似ているものである(Distributional hypothesisに基づく)。
【０１０８】
特徴ベクトルインデックス５２とインバーテッドエンティティペアインデックス５３を使い、パターンの単語ペア頻度ベクトル（例えば、図１０において、全部で３つの単語ペア(単語ペアＩＤ1, 2, 3)しかないと仮定すると、パターンＩＤ1の単語ペア頻度ベクトルが(10, 12, 0)で、パターンＩＤ 2のベクトルが(4, 0, 0)で、パターンＩＤ 3 のベクトルが (6, 0, 3) である）のcosine類似度を計算し、非特許文献3で述べたsequential clustering アルゴリズムを施し、語彙パターンのクラスタリングを行う。検索データベースには、類似する語彙パターンがまとめられた語彙パターンのクラスタのテーブルが用意され、各語彙パターンはいずれかの語彙パターンクラスタに振り分けられている。語彙パターンクラスタには語彙パターンクラスタＩＤが割り当てられる、語彙パターンＩＤと語彙パターンクラスタＩＤが関連付けられる。
【０１０９】
固有名詞(named entityなど)については、既述のように、相手のエンティティとの共起頻度と共通パターンを使い、クラスタリングする。語彙パターンのクラスタリングと同様に、エンティティ同士の類似度をその対応するベクトル間のcosine(コサイン)類似度で計算し「似たエンティティ同士をクラスタにする」という作業を行う。
例えば、United States，U.S.，USAは１つのクラスタに入るようにする。各エンティティがどのクラスタに入るかを類似するエンティティがまとめられたエンティティクラスタのテーブルに記録しておく。エンティティクラスタにはエンティティクラスタＩＤが割り当てられ、エンティティＩＤとエンティティクラスタＩＤが関連付けられる。固有名詞以外のエンティティについても、類義語をまとめたエンティティクラスタを用意してもよい。これで、検索するための準備が完成する。
【０１１０】
最後のモジュールはクエリ処理エンジン（Query  Processing  Engine）６である。クエリ７として{(Ａ，Ｂ)，(Ｃ，？)}が入力されたときに、クエリ処理エンジン６はまず、エンティティペアインデックス５０から入力stem語ペア(Ａ，Ｂ)のＩＤを探す(stem_idとする)。
【０１１１】
そのstem_idを使い、特徴ベクトルインデックス５２(図８, 図９参照)やパターンクラスタリングエンジン４の結果によって、stem語ペア(Ａ，Ｂ)の特徴ベクトルf(a，b)を見つけ出す。そして、f(a，b)にある頻度1より大きい語彙パターンＩＤを探し、インバーテッドエンティティペアインデックス５３(図１０)を参照して、候補エンティティペアＩＤの集合を作る。候補エンティティペアとなるためには、そのペアの一方のエンティティがクエリのエンティティCである必要がある。
【０１１２】
最終に、stem語ペア(Ａ，Ｂ)の特徴ベクトルと候補エンティティペア(Ｃ，Ｄ)の特徴ベクトルの類似度を前記のRelSim((Ａ，Ｂ)，(Ｃ，Ｄ))関数を使って計算し、候補エンティティペアの集合を類似度の高い順にソートする。
【０１１３】
１つの態様では、ランキングの指標となるスコア（類似度）を計算する際に、１つのエンティティクラスタに入っている複数のエンティティ(つまり、１つのエンティティを指しているが表現形式が異なる)のスコア（類似度）の和をエンティティクラスタのサイズで割ったクラスタ平均スコアを取り、そのエンティティ（エンティティ）のスコア（類似度）として用いてランキングを行う。すなわち、個々のエンティティのスコア（類似度）で個々のエンティティをランキングするのではなく、エンティティのクラスタとしてのスコア（エンティティクラスタのメンバーのスコアの総和をクラスタのサイズで割ったクラスタ平均スコアを用いてランキングを行う。
【０１１４】
以下にクラスタのスコア（類似度）について具体的に説明する。
入力クエリ: (A, B), (C, ?)とした場合、
(A, B) を含む語彙パターンはS1＝{p1,p2,..,pn}
(C, X) を含む語彙パターンはS2＝{q1,q2,..,qm}
q1∈S1ならば、Xのスコア にh(q1,
(C, X)) * h(q1, (A, B)) を加える。    
ここで、h(p, wp)は、「語彙パターンpのword pair wp における出現頻度」、である。
q1 not∈S1 の場合であっても、q1とpiが同じパターンクラスタであれば、同じく次のようにスコアを計算する。
h(q1,(C,X))*h(pi,(A,B))
クラスタのスコアは、すべてのXのスコアの和となる。
例えば、
(Obama,  US):(is  president  of  [4],  is  leader  of  [3],  is  a  senate  of  [2],)
(Koizumi,  Japan):(is  prime  minister  of  [8],  is  leader  of  [5])
Query:(Obama,US),(Koizumi,X)
“is  president  of”と“is  prime  minister  of” が同じクラスタに入る場合、X のスコアは:(3*5+4*8)=15+32=47、となる。
次に、クラスタ平均スコアについて説明する。
クラスタの総和スコア = Σ（entity のスコア)、
クラスタ平均スコア = クラスタ総和スコア / size、となる。
エンティティクラスタ(United States, U.S., US) を形成した場合に、
例えば、United States のスコア:15、 U.Sのスコア10、USのスコア8、の場合、
クラスタ総和スコア: 15 + 10 + 8 = 33、
クラスタ平均スコア: 33 / 3 = 11、となる。
【０１１５】
エンティティのクラスタのスコアを用いることは、検索結果のランキングに重要な影響を与える。例えば、 (Apple, Steve Jobs), (Microsoft, ?)のクエリの場合、D=Steve Ballmer だけの結果のスコアがD=Windows(両方ともX  introduces  Y,  X  announces  Y,...という語彙パターンを備える場合が多い)よりも低くなり得る。D=Steve
Ballmer, D=Ballmer, D=Steve Anthony Ballmer を１つのクラスタにまとめることで、そのエンティティクラスタのスコア（各エンティティのスコアの総和結果）は、D=Windows だけのエンティティクラスタのスコアよりも高くなると考えられる。このスコア逆転によって、望ましい結果が上位にランクされるという利点がある。
【０１１６】
ソートされた候補エンティティペアの集合から検索結果Ｄ(またはＤに属するエンティティクラスタ)のランキングされたリスト８を出力する。また、エンティティペア(Ａ，Ｂ)、エンティティペア(Ｃ，Ｄ)が共通に持つ語彙パターンを含む文や文書を、結果を説明する理由として出力してもよい。更に、(Ａ，Ｂ)，(Ｃ，Ｄ)の共有の代表的な関係も出力できる。
【０１１７】
あるエンティティが検索結果として得られた時に、そのエンティティをクラスタリングすることにより、「エンティティクラスタ」を検索結果として出力することができる。すなわち、検索結果をエンティティクラスタを用いて出力することで、Xの候補をユーザに提示するときに似たようなもの（例：ObamaとBarak Obama）をまとめて表示することができる。
【０１１８】
［Ｄ］動的処理を用いた検索
以上、検索データベースを用いた検索について説明した。エンティティＡ，Ｂ，Ｃの１つ以上が検索データベースに存在しない場合には、既存の検索エンジンによりリモートコーパスを用いる動的処理モードを実行する。以下に、具体的に説明する。
【０１１９】
エンティティペア（Ａ,Ｂ）のエンティティＡ，Ｂが検索データベースにない場合には、エンティティＡ，Ｂの間の関係を表す語彙パターンを既存の検索エンジンを用いて抽出する。まず“Ａ****Ｂ”というクエリを既存検索エンジンで検索する。これはエンティティＡとエンティティＢを最大4単語以内（＊は１個ないしゼロ個の単語とマッチされるワイルドカード）で出現するsnippetを検索結果として受信する。後で語彙パターンを生成するために、単語の連続(n-gram)を抽出するが、そのためにはエンティティＡとエンティティＢが近くに現れる必要がある。いわばこのクエリはエンティティＡとエンティティＢの「文脈」を近似しようとするものである。ワイルドカード＊の数については当業者において  適宜設定し得るが、例えば、1個から最大7個まで複数のクエリを用いることができる。例えば「Ａ*Ｂ」、「Ａ**Ｂ」、「Ａ***Ｂ」、…「Ａ*******Ｂ」まで用いる。＊が多いクエリで受信する結果と＊が少ないクエリで受信する結果が似ている場合もあるので、1つの態様では、同一URLからくるsnippetを一回だけ集めるようにする。多くの既存の検索エンジン（例えば、Google，YahooBOSS API）では、“Ａ****Ｂ”というクエリにより、ＡとＢの前後の文脈も含むスニペットが得られる。
【０１２０】
ワイルドカード検索を用いて取得したスニペットから、エンティティペア（Ａ,Ｂ）の文脈となるものが得られる。次に、この文脈からエンティティＡとエンティティＢの間の関係を表現する語彙パターンを抽出する必要がある。この語彙パターンを抽出するアルゴリズムは既述の語彙パターン取得手法と同じある。つまり、エンティティＡ、エンティティＢを含むn-gramを抽出し、抽出したn-gramの中のＡをＸに、ＢをＹに置き換える。以下例を示して説明する。
【０１２１】
エンティティＡ=Barack Obama、エンティティＢ=USA、とした場合、“Ａ****Ｂ”でGoogle検索すると次の結果が得られる。
2011118689.tif 000010
【０１２２】
上記のsnippetをlowercaseにし、全ての活用形を基底形に変換する(lemmatization)。Lemmatizationによって名詞の複数形がその単数形になり、動詞の活用形（過去形や進行形）が基底形になり、活用によるばらつきが吸収される。lowercaseにすることで大文字、小文字によるばらつきが吸収される。
【０１２３】
次に、Ｘ=Barack Obama, Ｙ= USAとすると次のようになる。
2011118689.tif 000011
次のこの中でXもYも両方を含むn-gramを生成する。例えば、n=6で
2011118689.tif 000012
が生成される。
【０１２４】
上記の語彙パターンはXから始まり、Yで終わっているが、必ずしもXとYの間をつなぐ語彙パターンのみを抽出するものではない。語彙パターン抽出の条件は長さがnでXもYも含んでいることであり、その2つの条件を満たすものを全て語彙パターンとして抽出する。例えば、n=7にすると上記のsnippetから次の2のパターンが抽出される。
2011118689.tif 000013
【０１２５】
得られた語彙パターンが検索データベースの中にも存在すれば高頻度のものを優先することができるが、検索データベースに存在しない場合は、クエリ（Ａ,Ｂ）対して例えば２回以上抽出されたパターンの全てにXにCを代入し検索する。
【０１２６】
例えば、上記のX, president of the Yという語彙パターンとC=Vladimir Putinの場合には、次のクエリとなる。
Vladimir  Putin,  president  of  the *
これでGoogleを検索すると次の結果が得られる。
2011118689.tif 000014
【０１２７】
このsnippetのなかでFEDERATION OF RUSSIAの部分が正解である。正解となる部分を抽出するには、例えば、語彙パターンの後に出てくる部分から3-gramまで取り、回答候補を出現頻度でランキングする。
【０１２８】
このように、エンティティペア（Ａ,Ｂ）がデータベースにない場合には、エンティティペア（Ａ,Ｂ）の関係を表す語彙パターンはWeb検索結果 snippetから抽出する必要がある。エンティティCが検索データベースにあれば抽出した語彙パターンでデータベースを検索して候補(C,X)を選択することが可能である。もちろん、動的モードは、エンティティ（Ａ,Ｂ）及びエンティティCが検索データベースに入っている場合であっても、データベースを無視して実行することができ、この場合でもあたかもエンティティCもデータベースになかったように全て動的モードで処理することが可能である。ただし、動的モードは実際にその場で動的にWeb検索エンジンにアクセスする必要があるので、検索データベース（エンティティＡ,Ｂ,Ｃが全て検索データベースにある）を用いた検索に比べて、幾分時間を要する点に留意する。1つの態様では、検索データベースを用いた検索が１秒以内で検索結果を出力するのに対して、動的モードでは30秒以内で検索結果を出力する。
【０１２９】
図２Ａ〜２Ｃに検索結果の表示画面の例を示す。図２Ａは、クエリ(steve
jobs, apple), (?, microsoft) の簡易結果 (証拠文章を含まない結果)の表示画面（クライアント端末のディスプレイに表示される）である。図２Ａでは、検索結果のランキングが表示されており、具体的には、ballmer, steve ballmer(スコア２９５)、bill gates（スコア５２）、danny thrope(スコア２７)の順に表示されている。図２Ａに表示される検索結果から、ballmerと steve ballmerはクラスタリングされていることがわかる。図２Ａの表示画面において、クライアント端末から入力手段によってShow evidenceを選択すると、証拠文が表示画面に表示される。図２Ｂは、図２の表示画面において、証拠文の一部（bill gates）のみを示したものである。また、 Debug Info に語彙パターンの一部を表示している。図２Ｃは、クエリ (steve jobs, apple), (steve ballmer, ?) 簡易結果 (証拠文章を含まない結果)の表示画面である。
【図１】
2011118689.tif 000015
【図２】
2011118689.tif 000016
【図２Ａ】
2011118689.tif 000017
【図２Ｂ】
2011118689.tif 000018
【図２Ｃ】
2011118689.tif 000019
【図３】
2011118689.tif 000020
【図４】
2011118689.tif 000021
【図５】
2011118689.tif 000022
【図６】
2011118689.tif 000023
【図７】
2011118689.tif 000024
【図８】
2011118689.tif 000025
【図９】
2011118689.tif 000026
【図１０】
2011118689.tif 000027
【図１１】
2011118689.tif 000028
【図１２】
2011118689.tif 000029
【図１３】
2011118689.tif 000030