For many real world applications, background knowledge is intensively required. The acquisition of relational domain knowledge is still an important problem. Relation extraction systems extract structured relations from unstructured sources such as documents or web pages. These structured relations are as useful as knowledge. Acquiring relational facts like Acquirer―Acquiree relation or Person―Birthplace relation with a small number of annotated data could have an important impact on these applications such as business analysis research or automatic ontology construction.

The World Wide Web contains a significant amount of relational information expressed in natural language. Although, the Web forms a fertile source of data for relation extraction, the users of relation extraction system are typically required to provide a large amount of annotated texts to identify the interesting relation. This requirement is typically neither feasible nor inapplicable. Therefore, bootstrapping systems are proposed to address the task of Web-based relation extraction, which usually only need a small number of seed entity pairs of relations.

In this thesis, graph based semi-supervised learning methods are applied to improving the performance of bootstrapping relation extraction system. Semi-supervised learning approaches aim at obtaining good performance at a low cost by combining (potentially large) amounts of unlabeled data with labeled data. The bootstrapping relation extraction can be naturally treated as semi-supervised learning problem. The experimental work of this thesis shows that considerable improvements are achieved by using graph based semi-supervised methods.

In Chapter 2, we overview information extraction task and systematically revisit related work on semantic relation extraction problem. There are three kinds of methods to extract relations from documents: traditional relation extraction, open relation extraction and bootstrapping relation extraction. For the traditional relation extraction system, the user is usually required to provide a large amount of annotated texts to identify the interesting relation. On the other hand, the open information extraction system uses some generalized patterns or a small set of relation-independent heuristics to extract all potential of relations between name entities. The bootstrapping relation extraction is a tradeoff between traditional relation extraction and open relation extraction, which uses given seeds to bootstrap relevant instances from the Web or large corpora. The target relations are "weakly" defined by the given seeds.

In Chapter 3, we survey the semi-supervised learning methods used to the information extraction or text mining task, especially the co-training algorithm and label propagation algorithm. The co-training algorithm and label propagation algorithm are based respectively on different background assumptions. The co-training algorithm is grounded on compatibility assumption. The compatibility assumption means that for any data point x=(x1, x2), the classifier f1 trained on view1 gives x1 a label that is the same as x2's, which is given by the classifier f2 trained on view2. However, one cannot expect that all data are sufficiently compatible in practice. Label propagation is based on the consistency assumption: that nearby points are inclined to achieve the same label. In this thesis, to reduce the influences of incompatibility, the consistency assumption is regarded as a relaxation of the compatibility assumption because a node in one view is merely inclined to, but need not necessarily get, the same label with linked nodes in different views. Based on this idea, we propose a multi-view algorithm in Chapter 5.

Chapter 4 focuses on a bootstrapping relation extraction framework which is mainly composed of two aspects: expanding and ranking. Given the seeds of target relation (e.g. entity pairs or context patterns or both), the expanding component alternately extracts some entity pairs and context patents of target relation. Since some extracted entity pairs and context patterns are irrelevant or weakly relevant to the target relation, it is important for user to put the most relevant instances on the top of a returned list. We propose a ranking module to rank these instances according to their similarities to the given seeds.

In Chapter 5, we propose a graph based multi-view learning algorithm. This algorithm is based on the generalized consistency assumption. This assumption is composed of two parts: intra-view consistency and inter-view consistency. The intra-view consistency means that, in each view, nearby points or points on the same structure are likely to have the same label. The inter-view consistency presume that points from different view co-occurred frequently are inclined to belong to the same class. Different from co-training style algorithm, the proposed algorithm does not require the establishment of compatibility assumption. In most real-world applications, the compatibility assumption is quite strong, since data points from different views might belong to different classes. The co-training algorithm propagates "hard" labels from one view to the other using the compatibility assumption. Instead of propagating the "hard" label on a bipartite graph, the proposed algorithm spreads label scores among different views to avoid view incompatibility.

In Chapter 6, we evaluate the proposed multi-view learning algorithm using the bootstrapping relation extraction framework. We compare the proposed algorithm to the existing methods, relevant score based methods and frequency based methods, the results indicate that the multi-view learning algorithm can improve the performance of the relation extraction systems.

In Chapter 7, the multi-view learning algorithm is applied to semantic relation classification task. It shows that our proposed algorithm can improve label propagation algorithm with single view on the CDL corpus and SemEval-07 dataset. The experimental results also show the robustness of the proposed method to different inter-view correlation measures and different feature splitting.

本論文は「Graph Based Learning Methods For Semantic Relation Extraction (意味的関係抽出のためのグラフに基づく学習手法)」と題し,英文で記されており,8章から成る.

第1章「Introduction(序章)」では,対象とする膨大なWebテキストから意味的関係を有するエンティティ対を抽出する意義,学習法を含む関連手法,本論文の貢献についての概観を述べている.ここで対象とする意味的関係を有すエンティティ対とは,例えば買収・被買収関係にある2企業名,人間に関する事項では人物と出生地といった対である.

第2章「Semantic Relation Extraction(意味的関係抽出)」では,Webテキストからの関係情報抽出の関連手法についてまとめている.大別すると3種の枠組みが存在し,1)関係種別ラベルのアノテーションが付与された大量のコーパスデータから教師付き学習によって識別器を求める伝統的関係抽出の手法,2)一般性のあるパターン或いは関係種別に非依存なヒューリスティックスを用いて,出現する名辞エンティティ間に存在する全ての関係の抽出を図るオープン関係抽出の手法,3)与えられた少数の種(seeds)を基にして大量のWeb等のテキストコーパスから,種と近い関係を持つエンティティ対の具体例を求めるブートストラッピング型関係抽出の手法である.3)の手法は1)と2)の中間的性格を有し,本論文はこのアプローチについての研究を記している.

第3章「Semi-supervised Learning(半教師付き学習)」では,まず上記のブートストラッピング型関係抽出に関係する半教師付き学習法,特に本論文に関係する共トレーニング(co-training)法とラベル伝搬(label propagation)法について記している.この両者は,異なる仮説に基づいている.共トレーニング法は全てのデータ点x=(x1, x2)に対して,ビュー1で訓練された識別器f1がx1からラベル1を与え,ビュー2で訓練された識別器f2がx2からラベル2を与える場合,このラベル1とラベル2は等しくなるという両立性仮説(compatibility assumption)に基づく.しかし,実用的にはこの仮説が全てのデータ点で十分に成立するとは期待できない.一方でラベル伝搬法は,近隣のデータ点は同一ラベルになるという整合性仮説(consistency assumption)に基づく.本論文で考案している手法は,上記の両立性が成立しない影響を軽減するため,整合性仮説が両立性仮説を以下のように緩めるものとして見なしている.即ち,1つのビューのデータ点は他のビューで連結されたデータ点と同一のラベルを持つ傾向にあるが,必ずしもそうであるとは限らないと見なしている.このアイディアに基づき,第5章で半教師付き学習のマルチビュー学習法を提案している.

第4章は「Framework of Bootstrapping Relation Extraction(ブートストラッピング型関係抽出の枠組み)」であり,拡張とランキングから成る2ステップの考案した手法を記している.抽出対象となる関係(関係を持つエンティティ対とその周辺テキスト文脈パターンの一方又は両方)が与えられた時,拡張機能は対象となる関係を持つエンティティ対と周辺文脈パターンを,ラベルなしの大量のデータセット(Web)から交互に抽出する.ここで抽出されるエンティティ対や周辺文脈パターンの幾つかは,対象とする関係と無関係であったり関係性が弱いことがあるので,抽出されるデータを関係性により選別することが重要になる.このために,ここでは与えられた種との類似性に従って,拡張機能により抽出されたデータをランキングする機能を導入している.

第5章「Graph based Multi-View Learning(グラフに基づくマルチビュー学習)」では,エンティティ対集合と周辺文脈パターン集合をそれぞれのビューとしたとき,整合性仮説を一般化したビュー内(intra-view)整合性とビュー間(inter-view)整合性を用いる手法を提示している.ここで,ビュー内整合性とは,各ビューに於いて,近傍データ点或いは同一構造上のデータ点は同一ラベルを持つ可能性が高いことを意味する.一方,ビュー間整合性では,異なるビューからのデータ点の共起度が高ければ,これらのデータ点は同一ラベルに属する傾向にあると仮定する.共トレーニング流の手法とは異なり,ここでの提案手法は両立性仮説の成立を要しない.異なるビューから得られるデータ点は異なるクラスに属することがあるので,大部分の実問題ではこの両立性仮説は強過ぎる仮説である.共トレーニング法では両立性仮説を用いて,1つのビューから得られた"ハード"なラベルを他のビューから得られるデータへ伝搬させる.これに対しここでの提案手法では,2部グラフ(bipartite graph)上で"ハード"なラベルを伝搬させるのでなく,異なるビューの間でラベルのスコアを拡散させることにより,ビュー間の非両立性の問題を回避できるようにしている.

第6章「Experiment: Improve Bootstrapping Relation Extraction(ブートストラッピング型関係抽出の改善の実験)」では,ブートストラッピング型関係抽出の実験を行い,前章で提示したマルチビュー学習法の性能を評価している.その結果として,関係スコアに基づく半教師付き学習法や,頻度に基づく半教師付き学習法といった既存手法と比較し,提案手法は関係抽出の性能向上をもたらすことを示している.

第7章「Experiment: Semantic Relation Classification(意味的関係識別の実験)」では,提案のマルチビュー学習法をブートストラッピング型の意味的関係抽出に適用している.そして,テキスト中のエンティティ間関係を44種の関係種別によってラベル付けしてテキストが表わす意味を表現する言語であるCDL(Concept Description Language)に基づくコーパスと,評価用の共通的データセットとして作成されたSemiEval-07を対象にした実験を行い,提案手法は単一ビューによるラベル伝搬法の性能を改善することを示している.また,提案手法はビュー間の相関や特徴の各ビューへの異なる分割に対して頑健であることを示している.

第8章「Conclusions and Future Research(結言と今後の研究)」では,本論文の成果をまとめると共に,今後の研究課題について言及している.

以上を要するに,本論文は種(seeds)となるある関係を有する少数のエンティティ対を与え,Web等の大量のテキスト中からこれらと近い関係を有するエンティティ対の具体例を求めるブートストラッピング型関係抽出の問題に対し,半教師付き学習で従来用いられてきた共トレーニング(co-training)法が依拠する2つのビューでの両立性仮説は必ずしも成立しないという課題を軽減する手法として,2つのビュー領域間で拡張とランキングから成る2ステップの操作を行い,また従来のラベル伝搬法が依拠していた整合性仮説を一般化したビュー内(intra-view)整合性,ビュー間(inter-view)整合性を用い,2つのビュー領域から成る2部グラフ上でハードな関係ラベルを伝搬させるのではなく,異なるビュー間でラベルのスコアを拡散させるマルチビュー学習法を考案,開発している.そして,実験を通して考案した手法による性能改善効果を示している.この研究成果は,少数の関係種別ラベル付きデータに基づき,大量の関係種別ラベルのなしデータを活用する情報処理技術に貢献するものと認められ,情報理工学における創造的実践の観点でも価値が認められる.

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