The World Wide Web contains a huge number of Web pages which refer to numerous semantic relations. When a user wants to search for an entity in a specific semantic relation using a keyword-based Web search engine, the user must formulate a query with some keywords related to the entity and the relation. The user then inputs this query into the keyword-based Web search engine to retrieve a set of text snippets which the user must read to find out the answer. Moreover, when one does not explicitly know appropriate keywords to formulate a query, one can not get answers by using keyword-based Web search engines. With the growing number of entities and semantic relations on the Web, Web search engine users frequently face with such situations. Therefore, new entity retrieval paradigm based on semantic relations between entities is required to alleviate this problem. In this thesis, we study the problem of latent relational search, a novel entity retrieval method that enables Web search engine users to directly retrieve appropriate entities in an implicitly stated semantic relation. Specifically, given a latent relational search query {(A, B), (C, ?)}, in which A, B, C are entities, a latent relational search engine is expected to retrieve a list of entities L containing candidate answers to fill in the question mark (?) in the query. In the list L, each entity D satisfies the condition that the semantic relation between A and B is highly similar to that between C and D. For example, given the query {(Japan, Tokyo), (France, ?)}, a latent relational search engine is expected to retrieve and rank the entity ``Paris'' as the first answer in the result list, because the relation between Japan and Tokyo is highly similar to that between France and Paris.

To perform latent relational search on the Web, one must overcome several challenges: discovering entity pairs to build an index for high speed retrieval, exploring and representing the semantic relations between entities, and ranking the candidate answers according to the degree of relational similarity between the candidate entity pairs and the input pair. We propose a method for extracting entity pairs from a text corpus to build an index for a high speed latent relational search engine. Following previous work on relational similarity measuring algorithms, we represent the relation between two entities in an entity pair using lexical patterns of the context surrounding the two entities. We propose a lexical pattern extraction algorithm which enables the search engine to precisely measure the relational similarity between two entity pairs and therefore to accurately rank the result list of a latent relational search query. Different from previous work on latent relational search, the proposed retrieval model allows supporting sentences to be retrieved as evidences for each result. These evidence sentences provide the users of the search engine with further knowledge concerning the common semantic relations between the input entity pair and each retrieved candidate entity pair.

Moreover, we propose cross-language latent relational search, an advanced latent relational search paradigm that allows answering the query {(A, B), (C, ?)} when the input pair (A, B) is written in another language from the language of the entity C. To capture the similarity between relations across languages, we must transfer the meaning of lexical patterns from one language to another. We propose a novel lexical pattern clustering algorithm to recognize paraphrased lexical patterns across languages, thereby effectively ranking candidates and retrieving evidence sentences for cross-lingual queries.

We evaluate the proposed search engine on both monolingual query sets and English-Japanese cross-lingual query sets. The experimental results show that, the proposed method outperforms existing latent relational search engines on monolingual query sets. The search engine also achieves a moderate Mean Reciprocal Rank (MRR) on cross-lingual latent relational search query sets. Importantly, for the majority of cross-lingual queries, the search engine retrieves supporting sentences that are semantically similar in two different languages. This implies that the results of the search engine can be used for building parallel corpora or for supporting human translators. In particular, when evaluating with an ideal corpus, the proposed search engine retrieves the correct answer in the Top 1 ranked result for 95% of monolingual queries in English and 88% in Japanese. When evaluating with Japanese - English cross-language latent relational search queries, the proposed method achieves an MRR of 0.605 while requiring an average query processing time less than 10 seconds, which is acceptable for normal search engine sessions. Finally, we show that the proposed model can be applied to build a large-scale latent relational search engine with real-world corpora. Specifically, we use seven million articles in the English and Japanese Wikipedia data dumps to build an index for the search engine and use the search engine to answer several sophisticated questions in the INEX 2008 Entity Ranking task. The results show that, the search engine was able to answer 15 (out of 35) queries in monolingual mode, where as, in cross-lingual settings, the number of successfully answered questions was 12 (out of 35). This demonstrates that the proposed system could be used for answering sophisticated questions concerning entities and relations on the Web.

From these results, this work reveals the possibility of latent relational search as a next generation information retrieval and question answering paradigm on the Web.

日本語の概要:

膨大なWWW情報空間の中には,様々なエンティティとそれらの関係が多数,潜在的に記述されている.我々は従来のキーワードベースのWeb検索エンジンを利用することでキーワードを含む文書は検索できるが,エンティティ間の関係を検索することはできない.このため,エンティティ間の関係に基づいた検索を実現するため,潜在関係検索という新しい検索パラダイムが検討されてきた.潜在関係検索とは,与えられたエンティティペア(A, B) とエンティティCに対して,(A, B) と(C, D) が類似関係を持つようなエンティティD を探す検索のことである.例えば,潜在関係検索エンジンに {(Japan, Tokyo), (France, ?)} というクエリが入力されると,``Paris''を最初にランキングした結果リストを返す.これは,Japan と Tokyo との関係が France と Paris との関係と類似するからである.WWW空間の情報爆発が顕著となった昨今においては,検索エンジンにおいて適切なキーワードと検索クエリを考え出すことが一般ユーザにとって困難となりつつあり,単純なキーワードを含むWeb ページの検索だけでは現状に対応するのには限界がある.そこで本研究では潜在関係検索に着目し,高速かつ高精度な検索を,多言語なWeb空間上で行う手法を提案する.

本研究ではまず,高速な潜在関係検索を行うために,エンティティペアをWebから発見・抽出する手法と,抽出されたエンティティペアに対するIndexの構築手法を提案する.また,高精度な潜在関係検索エンジンを実現するため,エンティティ間の関係を周辺文脈の語彙パターンで表現し,精度の高い関係類似度計算アルゴリズムを利用し,Indexを用いて検索結果のランキングを行う.提案手法は従来の潜在関係検索の手法とは異なり,検索の過程で発見された入力エンティティペアと候補ペアとの共通の語彙パターンを使用して,候補エンティティだけを結果として出力するのではなく,そのエンティティがなぜ出力されるかという根拠の文も出力する.

更に本研究では,多言語のテキストを利用する言語横断型の潜在関係検索を提案する.言語横断型の検索では,入力ペア (A, B) と入力されたエンティティ C が異なる言語で書かれている場合も検索可能である.これにより,候補エンティティDが記述された文と,入力ペア(A, B)が記述された文が異なる言語の場合も検索ができ,検索に用いられる根拠の文の数と検索可能なエンティティの範囲を広げるができる.言語横断型の潜在関係検索を実現するためには,意味関係を特徴付ける語彙パターンを,入力ペアの言語から出力ペアの言語へとマッピングする必要がある.本研究ではこの意味マッピングの問題を解決するために,類似する語彙パターンを言語横断的に認識する手法を提案する.具体的には,新しい語彙パターンクラスタリング アルゴリズムを提案し,言語横断的に語彙パターンをクラスタリングする.これにより,言語横断型のクエリを処理でき,意味の近い根拠文を異なる言語から取り出すことができる.

評価実験では,まず小規模なテキストコーパスを使い,各関係タイプにおける提案手法の性能を評価する.具体的には,8種類の関係で平均逆順位 (MRR) と,正解をTop 1の結果にランキングできるクエリの割合を調べることで評価を行う.その結果,95%の英語の単一言語検索クエリにおいて,正解をTop 1にランキングすることができた.また日本語のクエリでは,88%のクエリで正解をTop 1にランキングすることができた.これは提案手法が,従来の単一言語の潜在関係検索の手法よりも精度の高い検索ができることを示している.一方,言語横断型のクエリセットでは,平均逆順位 (MRR) で 0.605 の値を達成した.この実験では根拠文として,言語は異なるが意味は類似した文を取得できた.また,平均クエリ処理時間は10秒以内であり,実用レベルのクエリクエリ処理時間であった.これにより,提案システムにはユーザの翻訳作業を支援できる可能性があることが示された.

次に,大規模なコーパスにおいて実用レベルの潜在関係検索エンジンを実装し,INEX 2008 Entity Rakingタスクを用いてその性能を評価した.提案した潜在関係検索エンジンは,単一言語の検索において,INEXの35の質問の中で15の質問に対して正解を出力できた.また,言語横断のクエリが入力された場合では,35の質問のうち,12の質問に対して正解を出力できた.これにより,提案システムが実用レベルで質問応答システムとして使えることが示された.

上記の成果を通して本研究では,潜在関係検索が次世代の情報検索パラダイムになり得ることを明らかにする.

本論文は「Latent Relational Web Search Engine Based on the Relational Similarity between Entity Pairs (エンティティペア間の関係類似性を利用するウェブ潜在関係検索エンジン)」と題し,英文で記されており,7章から成る.

第1章「Introduction(序章)」では,まず潜在関係検索とはWeb検索において,例えば{(Japan, Mt. Fuji), (Germany, ?)} と問い合わせると,Germanyで一番高い山として " ? = Zugspitze" を答える新タイプの検索エンジンであることを説明している.一般的に記すとクエリ(問合せ){(A, B), (C, ?)} において(A, B)をソースペア,?を含む(C, ?)をターゲットペアと称し,(A, B)間に成立するのと同様,或いは類似関係を有する(C, ?) の"?" を求める検索である.(ここで,"?" は最後の位置だけでなく上記のA,B,Cの位置のどこに置いても良い.)更に,{(日本,富士山),(Germany, ?)}のように,ソースペアとターゲットペアは異なる言語であっても可能な言語横断型(cross-lingual)関係検索を実現したことを述べている.そして,このような研究を行った背景と動機を述べている.

第2章は「Relational Similarity and Latent Relational Research(関係類似性と潜在関係検索)」であり,最初に本研究で基礎としたエンティティペア間の類似性計測法について説明している.これはWebテキスト中におけるエンティティペア間の周辺語彙系列パターンの分布の類似性が高いペアは,関係類似性も高いと見なせる分布仮説(Distributional Hypothesis) に基づくものである.周辺語彙系列パターンは2つのエンティティ(単語)を含む文から,エンティティペア間だけでなく,その前後も含めて所定の閾値以上存在するパターンを選ぶ.ターゲットペア(C, ?) については,Cの近傍で共起するエンティティ(単語)とのペアについて周辺語彙系列パターンを求め,ソースペア(A, B)の周辺語彙系列パターンとの類似性からランキングする.これは既存研究を参照したものだが,実用的な時間で検索結果を出力する高速検索を実現するためには事前処理によるインデックス作成が不可欠となり,この部分が本研究のオリジナルな成果となっている.また,言語横断型潜在関係検索も実現可能にしていることも,本研究のオリジナルな成果となっている.

第3章は「Related Work(関連研究)」であり,これまでの構造写像理論(Structure Mapping Theory)などの類推,特異値分解を用いる潜在関係写像エンジン(Latent Relational Mapping Engine),高レベル認知・類推のモデルなどの関連研究について記している.また,エンティティペア間の関係類似性の,本研究で用いた計測法以外の計測法について言及している.その後に,Webコーパスからの下位語(hyponyms)や上位語(hypernym)抽出法,部分全体の関係の語(meronym)抽出法などの既存研究について紹介している.

既存の関係検索システムに関係する研究についてもまとめている.それらは,"Muslim church"に対し"mosque"を答え,"Greek A"に対して"α"を答えるシステム,スロット充填システムとして " * is the president of France." の問合せに対してフランス大統領名を答えるシステム,INDUCES(asprin, ?) の問い合わせに対してアスピリンが誘発する効果を答えるシステム等を紹介している.本研究の関係検索と同様なシステムもほぼ同時期に開発されたものが報告されているが,これはエンティティペア間の限られた語彙系列パターンを利用する方法であり,本研究の方法はより包括的であり,かつインデックス化による高精度,高速化を実現していると述べている.言語横断型検索に関して本研究は,翻訳辞書にはしばしば存在しない固有名詞エンティティを検索対象にすることから,既存の単なる語の翻訳に頼るのとは異なる方法を採るとしている.

第4章「Retrieval Model for Monolingual Latent Relational Search(単一言語の潜在関係の検索モデル)」では,上記した本研究の潜在関係検索法について詳述している.即ち,エンティティの抽出は所定以下の近さで1文中に共起する固有名詞ペアをエンティティペアとして,両エンティティ間と前後3単語を含む一定以上の出現頻度を持つ周辺語彙系列パターン(*(wild card)を含むパターンも含む)を抽出する.この際,変動を抑制するため,単語は語尾変化を除き語幹にする(stemming).このようにして得られる周辺語彙系列パターンには付随するエンティティペアが記録されるのだが,同様なエンティティペアを有する周辺語彙系列パターンは意味的に類似な関係を表していると考えることができるので,これらをクラスタ化する.例えば,買収関係を表す"X acquired Y."と"X bought Y."は多くのエンティティペアを共有するので,意味的に近いと判断でき,一つの項目にクラスタ化する.高速検索を可能とするために,各エンティティペアに対する複数クラスタ化語彙系列パターン(出現回数付き)のインデックスファイル,その転置インデックスに相当する各クラスタ化語彙系列パターンに対応する複数エンティティペア(出現回数付き)のインデックスファイルを作成し,保持する.エンティティペア間の関係類似性は,基本的にコサイン類似度により計算している.

第5章は「Retrieval Model for Cross-Lingual Latent Relational Search(言語横断型潜在関係検索のための検索モデル)」であり,英語-日本語を具体例として言語横断型関係検索の実現法を記している.両言語テキストからのエンティティペア抽出,語彙系列パターンの抽出までは第4章の場合と同様である.両言語の橋渡しは,例えば日本語テキスト中には(グーグル,ユーチューブ)ペアと(Google, YouTube)が共に使われて出現することの利用,及び周辺語彙系列パターンを機械翻訳して他方の言語の語彙パターンにして利用(この翻訳は*を含まないパターンに限っている)によって実現している.そして2段階のクラスタ化により,両言語を統合した周辺語彙系列パターンのクラスタ化を実現している.言語横断型の場合,エンティティペアもクラスタ化することにより,(グーグル,ユーチューブ)と(Google, YouTube)等を同一のクラスタ化項目にまとめることができる.このように言語横断型の場合もほぼ同様にインデックスファイル,転置インデックスファイルを作成でき,潜在関係検索が実現できることを記している.そして,本手法による言語横断型潜在関係検索は,実験によりベースラインとなる既存手法よりも優れた性能を達成することを示している.

第6章は「Milresh: A Large-Scale Latent Relational Search Engine based on the Proposed Model (Milresh:提案モデルに基づく大規模潜在関係検索エンジン)」であり,実装したMilreshシステムの構成とkey-value storeとして実装した大規模インデックス構成を記し,性能評価について述べている.このシステムはクラウドコンピュータ環境で実装しており,Hadoopなど並列分散プログラミングを活用している.検索結果はランキング付きで出力され,併せて根拠となったセンテンスも出力される.判定の基になるデータ規模は、700万Wikipediaページ(内160万が日本語ページ)から得た2憶1300万センテンスを処理し,668万エンティティ,3,077万エンティティペア,9億4585万周辺語彙系列パターンを抽出し,潜在関係検索のためのインデックスを作成している.このインデックス作成の前処理に要した時間は,各々6CPUを持つ5並列マシンを用いて7日である.固有名詞を答える質問応答用データセットを用い,等価な関係検索を行う評価実験を行い,英語単一言語クエリにおいては43%程,英語-日本語横断型クエリにおいては34%程の正解を出力できることを実証している.その他の多くのクエリに対する検索性能も示している.これらの検索時間は3秒程度であり,事前のインデックス化により実用的な時間で検索が実現できることを実証している.

第7章「Conclusion(結論)」では,本論文の成果をまとめ,残された課題に言及している.

以上を要するに,本論文は{(Tokyo, Japan), (?, France)}といった問い合わせに対し,"?=Paris"と答えるような新タイプの潜在関係検索エンジンを,テキスト中のエンティティペアに対する周辺語彙系列パターンの分布の類似性計算に基づく検索を原理とし,表記ゆらぎを吸収することによる高精度化と実用的な検索時間を達成するために,周辺語彙系列パターンのクラスタ化を含むインデックスを構成することにより実現する方法を考案している.更に,英語-日本語といったような言語横断型潜在関係検索の実現法も考案している.そして,具体的に潜在関係検索エンジンを実装し,大規模テキストコーパスからインデックスを作成し,性能を評価,実証している.このように新機能Web情報検索エンジンを実用に近い形で開発したことで情報理工学に貢献し,創造的実践の観点から価値が認められる.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.