Comments
Description
Transcript
修士論文 DOM構造を利用した条件付確率場による Wikipedia文書中の
NAIST-IS-MT0551137
修士論文
DOM 構造を利用した条件付確率場による
Wikipedia 文書中の固有表現の意味体系への割り当て
渡邉 陽太郎
2007 年 3 月 9 日
奈良先端科学技術大学院大学
情報科学研究科 情報処理学専攻
本論文は奈良先端科学技術大学院大学情報科学研究科に
修士 (工学) 授与の要件として提出した修士論文である。
渡邉 陽太郎
審査委員：
松本 裕治 教授
（主指導教員）
石井 信 教授
（副指導教員）
乾 健太郎 助教授
（委員）
DOM 構造を利用した条件付確率場による
Wikipedia 文書中の固有表現の意味体系への割り当て∗
渡邉 陽太郎
内容梗概
本稿では，Wikipedia 内に出現する固有表現を獲得し，精度よく分類する手法
を提案する．Wikipedia の記事に出現するアンカーテキストの単語および句は，リ
ンク先の記事に語釈が記述されている．この Wikipedia の特性を用いて，我々は，
固有表現の分類問題を固有表現を表すアンカーテキストに対するラベル付与問題
として定式化する．まず，アンカーテキストをノードとして定義されるグラフを
構成する．次に，グラフに HTML の構造を取り入れるため，HTML の DOM 構
造に基づく 3 種類のエッジを導入する．このようにして構成したグラフのノード
に対するラベル付与を教師あり学習器である Conditional Random Fields (CRFs)
を用いて行う．しかし，構成したグラフは閉路を含むため，CRFs の正確な演算を
行うことは計算量が大きく困難である．そこで，Tree-based Reparameterization
(TRP) を用いて近似的に演算をおこなう手法を導入する．実施した評価実験にお
いて，提案手法が２つ組に対する Support Vector Machines の順次適用による手
法と比較して高い精度で固有表現の分類ができたことを報告する．
キーワード
固有表現, 情報抽出，語彙獲得, 機械学習, 条件付確率場
∗
奈良先端科学技術大学院大学 情報科学研究科 情報処理学専攻 修士論文, NAIST-IS-
MT0551137, 2007 年 3 月 9 日.
i
A Graph-based Approach to Named Entity
Categorization in Wikipedia Texts
∗
– Applying Conditional Random Fields to HTML DOM Structures –
Yotaro Watanabe
Abstract
This thesis proposes a method for categorizing named entities in Wikipedia.
In Wikipedia, a word or phrase of an anchor text is glossed in the linked HTML
text. We formalize named entity categorization as a task categorizing the the
anchor text with linked HTML text which glosses a named entity. Using this representation, we introduce a graph structure in which anchor texts are regarded
as nodes. In order to introduce HTML structure on the graph, three types of
edges are spanned based on the HTML DOM structure. We propose a method
with Conditional Random Fields (CRFs) to categorize the nodes on the graph.
Since the defined graph includes cycles, the exact inference of CRFs is computationally expensive. We introduce an approximate inference method using
tree-based reparameterization framework (TRP) to reduce computational cost.
Experimental results show the proposed method outperforms a baseline method
with Support Vector Machines.
Keywords:
Named Entity, Information Extraction, Lexical Acquisition, Machine Learning,
Conditional Random Fields
∗
Master’s Thesis, Department of Information Processing, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MT0551137, March 9, 2007.
ii
目次
1. はじめに
1
2. 関連研究
3
2.1 固有表現抽出タスクにおける固有表現の分類 . . . . . . . . . . . .
3
2.1.1
IREX . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.2
関根の拡張固有表現階層 . . . . . . . . . . . . . . . . . . .
4
2.1.3
その他の固有表現分類 . . . . . . . . . . . . . . . . . . . .
5
2.2 機械学習に基づくデータの依存関係を考慮した分類手法 . . . . . .
6
2.2.1
Iterative Methods . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.2
Probabilistic Relational Models . . . . . . . . . . . . . . .
8
2.2.3
Relational Markov Networks . . . . . . . . . . . . . . . . .
8
2.2.4
Tree-structured Conditional Random Fields . . . . . . . .
9
2.3 Web 文書からの語彙獲得 . . . . . . . . . . . . . . . . . . . . . . .
10
3. Conditional Random Fields
11
3.1 モデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2 パラメータ推定 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4. Conditional Random Fields を用いた Wikipedia 文書中の固有表現
分類
17
4.1 DOM 構造からのグラフ構造の構築 . . . . . . . . . . . . . . . . .
19
4.2 model 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.3 model 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.4 周辺確率の算出によるラベルの信頼度推定 . . . . . . . . . . . . .
25
5. 実験
28
5.1 訓練・評価用データ . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.2 実験方法・評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
5.3 実験結果・考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
iii
6. おわりに
37
謝辞
38
参考文献
39
付録
43
A. 実験結果の詳細
43
B. 関根の拡張固有表現階層 クラス一覧
45
iv
図目次
1
Linear-Chain CRFs と Factorial DCRFs のグラフ構造 . . . . . . .
12
2
Wikipedia の記事 . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3
HTML 文書中のリスト要素とアンカー . . . . . . . . . . . . . . .
18
4
HTML 文書と対応する DOM 構造の例 . . . . . . . . . . . . . . .
19
5
DOM 構造と定義したクリークとの対応関係 . . . . . . . . . . . .
21
6
Sibling，Cousin，Relative を含めるか含めないかの各組合せによっ
て構成されるグラフ
7
. . . . . . . . . . . . . . . . . . . . . . . . .
30
Precision-Recall 曲線 . . . . . . . . . . . . . . . . . . . . . . . . .
36
表目次
1
IREX の固有表現の定義 . . . . . . . . . . . . . . . . . . . . . . .
3
2
ACE の固有表現の定義 . . . . . . . . . . . . . . . . . . . . . . . .
5
3
訓練・評価用データの固有表現クラスと Wikipedia の記事数一覧 .
29
4
分類に用いる素性 . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5
CRFs と SVM の分類精度比較 (全体) . . . . . . . . . . . . . . . .
33
6
Wikipedia データの SVM と CRFs の分類精度比較 (リンク先なし)
34
7
Wikipedia データの CRFs (model 1) と CRFs (model 2) の分類精
9
度比較 (全体) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
拡張固有表現階層クラス一覧
49
. . . . . . . . . . . . . . . . . . . .
v
1. はじめに
固有表現とは，人名，地名，組織名などの固有名詞や，時間表現，日付表現な
どを指す．非常に多くの数の固有表現が存在するため，形態素解析の段階で用い
る辞書に登録されていない表現が多く出現し，解析時に未知語になりやすいとい
う問題がある．そのため，解析誤りを避けるためには，多くの固有表現を辞書に
登録しておくことが有効である．
また，自然言語処理の応用分野である関係抽出や情報検索，質問応答などにお
いても固有表現は非常に重要や役割を持つ．例えば，質問応答システムは，自然
言語で質問が与えられ，質問の答えとなる範囲を文書中から探し，回答するとい
う一連の処理をおこなうシステムであるが，固有表現が回答となるような質問
(Factoid 型の質問) が与えられたとき，質問文がどのようなクラスの固有表現を
要求しているかを判別した上で，答えなければならない固有表現のクラスに該当
する表現を探す．例えば，
「富士山の高さは何メートルですか？」という質問が与
えられた時，質問文を解析することで数値表現を答える必要があると判断される．
そこで文書中から数値表現に該当する表現を探し，その中で回答となるものを返
すが，文書中のどの部分が数値表現であるかということがわからなければ，回答
を探すことはできない．
固有表現の同定は一般的に，テキスト中から自動的に固有表現を抽出する固有
表現抽出によりおこなわれる．固有表現抽出は，近年では機械学習に基づく手法
が用いられることが多いが，テキスト中の固有表現を全て網羅できるわけではな
く，限界がある．そのため，獲得できる固有表現については，既存の資源などを
利用して獲得することが必要となる．
World Wide Web (WWW) の発展により，Web 上には多くの有用な資源が存
在する．その中で，本稿では固有表現獲得のための資源として Wikipedia1 に注目
した．Wikipedia は Web 上の多言語百科事典であり，日々新たな記事が追加され
ている．記事の見出し語には，本研究で抽出対象となる固有表現が数多く含まれ，
DOM 構造やカテゴリなど，抽出の手がかりとなる情報が多く存在している．ま
た，各記事からアンカーによって別の関連する記事を参照することができる．こ
1
http://ja.wikipedia.org/
1
のような特徴を持つ Wikipedia は，固有表現の獲得に適した資源であると考えら
れる．
Wikipedia の記事は一つの文書についてある特定の事柄について記述されてい
るため，その文書がどのような事柄について記述されているかを分類する文書分
類の問題として扱うことが考えられる．一般的な分類問題に対するアプローチと
して，分類対象を個別に分類する手法が用いられることが多いが，Wikipedia は
HTML 文書，すなわち半構造データである．ある特定の文書中に存在するアン
カーの出現の仕方には規則性がある．例えば，リストにおいて列挙されているア
ンカーは，同じクラスに属するような固有表現が記述されている記事を参照して
いる傾向がある．そのようなアンカーの相互の依存関係をとらえた上で分類をお
こなうことで，より高い精度での獲得が期待できる．
依存関係を考慮した分類手法はいくつか提案されてきているが，本稿では Con-
ditional Random Fields (CRFs) を用いて分類をおこなう．CRFs を用いる場合，
どのようなグラフ構造を与えるかが問題となるが，HTML 文書は木構造上とし
て扱うことができるため，その木構造上で依存関係があるようなアンカーの組を
CRFs のクリークとすることでグラフ構造に依存関係を反映させることができる．
そこで本稿では，HTML 文書の構造によって出現する依存関係をグラフ構造に反
映させた CRFs のモデルを提案する．
2 章ではまず固有表現とその分類について述べた上で，本研究に関連する，依
存関係を持つようなデータに対する識別手法，Web 文書からの語彙獲得および
Wikipedia を資源として利用する研究について述べる．3 章では Conditional Random Fields (CRFs) について述べる．4 章では，CRFs を Wikipedia から固有表現
を獲得する問題に適用する方法について述べる．5 章では，評価実験により提案
手法を検証する．6 章でまとめと今後の課題について述べる．
2
2. 関連研究
本稿は，固有表現，文書分類，Web 文書からの語彙獲得，Wikipedia を利用す
る研究と関連がある．従って，本節では各分野と本稿で関連する研究について触
れる．
2.1 固有表現抽出タスクにおける固有表現の分類
2.1.1 IREX
Infomation Retrieval and Extraction Exercise (IREX) [19] は，情報抽出，情報
検索の評価型ワークショップである．情報抽出，情報検索の各分野で共有タスク
がおこなわれており，情報抽出の課題では，文書中から固有表現を抽出する固有
表現抽出タスクが行われている．
IREX の固有表現の分類を表 1 に示す．
固有表現名
例
固有名詞的
組織名, 政府組織名 (ORGANIZATION)
国連，日本 IBM
表現
人名 (PERSON)
木村庄之助
地名 (LOCATION)
東京都，法隆寺駅
固有物名 (ARTIFACT)
魚沼産コシヒカリ，カローラ
日付表現 (DATE)
5 月 14 日，去年，ある秋
午後 5 時 25 分，正午
時間表現
時間表現 (TIME)
数値表現
金額表現 (MONEY)
500 億円，$104,500
15%，5 分の 1，倍
割合表現 (PERCENT)
表 1 IREX の固有表現の定義
IREX の固有表現の分類は，Message Understanding Conference (MUC) [7]
で定義されていた組織名 (ORGANIZATION)，人名 (PERSON)，地名 (LOCA-
TION)，日付表現 (DATE)，時間表現 (TIME)，金額表現 (MONEY)，割合表現
(PERCENT) の計 7 種類に，固有物名 (ARTIFACT) が加わえられ計 8 類種定義
されている．
3
IREX の固有表現分類において問題となっているのは，分類がカバーしている
固有表現の範囲，および曖昧性である．
まず分類がカバーする固有表現の範囲については，例えば情報抽出分野におい
て，目的によって抽出対象となる固有表現は異なってくる．そのため、分類に含
まれない固有表現については新たに定義する必要がある．
分類の曖昧性については，例えば，地名にも組織名にもなりうる固有表現 (例：
成田空港) の存在がある．どちらであるか判断がつかない場合は，IREX では (OP-
TIONAL) というカテゴリを別個に用意し，評価対象としていなかった．
2.1.2 関根の拡張固有表現階層
関根らは，MUC で定義された固有表現および IREX の固有表現分類を基準に拡
張した，拡張固有表現階層 (Extended Named Entity Hierarchy) を提案した [20]．
この分類は，新聞記事を知識源とした時に，人が質問応答システムで知りたいよ
うな主に名詞句で表現されている実体，情報抽出システムで抽出したい実体のう
ち，高い頻度で現れるようなものを意味，用法にそってまとめたものである．
この分類は，従来の非階層的な分類とは異なり階層構造を持つ．当初，150 種
類のクラスが定義されていたが，幅広い応用で適用できるよう拡張がなされ，現
在，末端ノードのみで 171 クラス，中間ノードを含めると約 200 クラスとなって
いる．階層内のクラスはノードと呼ばれ，中間ノード (子クラスを持つノード) と
末端ノード (子クラスを持たないノード) に大別される．固有表現は中間ノードに
は属さず，末端ノードの何れかに属する．
この分類では，IREX の分類よりも幅広い固有表現を扱えるようになっており，
自然物など IREX の分類では扱われていなかったクラスについても新たに定義が
なされている．例えば，動物名，植物名，物質名などがそれに該当する．
IREX の分類では，地名にも組織名にもなりうる固有表現 (例：成田空港) の扱
いに問題があった．文脈によって判断できる場合は，その文脈に応じて地名，組
織名を区別して扱い，曖昧な場合は OPTIONAL として扱っていたが，拡張固有
表現階層では地名，組織名とは異なる，施設名 (FACILITY) という別のクラスが
設けられている．
4
固有表現名
下位分類名
Facility
Geo-Political Entity
Airport, Building-Grounds, Path, Plant, Subarea-Facility
Continent, County-or-Distinct, GPE-Cluster, Nation,
Population-Center, Special, State-or-Province
Address, Boundary, Celestial, Land-Region-Natural,
Region-General, Region-International, Water-Body
Commercial, Educational, Entertainment,
Government, Media, Medical-Science, Non-Governmental,
Religious, Sports
Group, Inderminate, Individual
Air, Land, Subarea-Vehicle, Underspecified, Water
Biological, Blunt, Chemical, Exploding, Nuclear,
Projectile, Sharp, Shooting, Underspecified
Location
Organization
Person
Vehicle
Weapon
表 2 ACE の固有表現の定義
また，IREX の分類中の ARTIFACT(固有物名) に属する固有表現は多岐にわた
るものであったが，拡張固有表現階層において固有物名に該当する固有表現につ
いては，非常に細かな分類がなされている．例えば，新たに設けられた製品名の
クラスは従来の固有物名に該当するクラスであるが，製品名の子クラスには食べ
物名，文化名，宗教名，芸術名など多くのクラスが定義されている．関根の拡張
固有表現階層クラス一覧は付録 B を参照．
2.1.3 その他の固有表現分類
The Conference on Natural Language Learning (CoNLL) の 2002 年，2003 年
の shared task において固有表現抽出タスクが行われた．2002 年の shared task で
はスペイン語，オランダ語が，2003 年の shared task では英語とドイツ語が抽出
対象となる言語として選択された．固有表現の分類は，双方において PERSON,
ORGANIZATION, LOCATION, TIMES, QUANTITIES の 5 種類となっている．
MUC の流れを引き継いだ情報抽出のプロジェクトである Automatic Content
Extraction (ACE) においては，非階層的な分類ではなく階層性を持つ固有表現
分類が採用された．ACE の固有表現分類を表 2 に示す．
5
ACE の固有表現分類では，固有表現の種類が 7 種類，下位分類は 44 種類であ
る．2.1.2 節の拡張固有表現 [20] についてもそうであるが，様々な要求に応えるた
め，固有表現の分類は階層化，細分類化の方向に向かっている．
2.2 機械学習に基づくデータの依存関係を考慮した分類手法
伝統的な文書分類のアプローチでは，分類対象となる文書集合 X = {X1 , ..., XN }
は独立で同一の分布に従うという仮定に基づいているが，分類対象となる文書間
に依存関係がある場合には，その関係を捉えた上で分類を行うことで精度向上が
期待できる．ここで，文書間の依存関係の例として Web 文書のハイパーリンクが
挙げられる．ここで Web 文書 Xi , Xj ∈ X を分類することを考えた時にもし，文
書 Xi から文書 Xj へのリンクが存在する場合，文書 Xj において言及されている
事柄について，文書 Xj においても言及されている可能性が高く，依存関係があ
ると言える．文書分類の視点で捉えた場合，このような依存関係を分類に用いる
ことで精度向上が期待できる．
そのような依存関係を捉えた識別を，Relational Classification という．本稿
で扱う対象となる Wikipedia はハイパーリンクを多く含む Web 文書であるため，
Relational Classification が有効であると考えられる．そこで本節では，Relational
Classification の手法を中心に触れる．
2.2.1 Iterative Methods
Lu ら [12][13] は，リンク関係にある文書のラベルを用いた Link-based Classification の手法を提案した．このモデルは，ロジスティック回帰に基づき，識別対
象となる文書の内容からクラスを推定する識別器，リンク関係にある文書のカテ
ゴリからクラスを推定する識別器を個々に作成し，それらを統合して最終的な出
力結果を決定する．
カテゴリの推定には以下の式を用いる．
Ĉ(X) = arg max P (c|OA(X))P (c|LD(X))
c∈C
6
ここで X は分類対象となる文書，C はカテゴリ集合，OA(X) は文書の持つ特徴
(object features)，LD(X) はリンク構造の持つ特徴 (link features) を表している．
文書の持つ特徴が与えられた時のカテゴリの事後確率 P (c|OA(X)) と，リンク構
造の持つ特徴が与えられた時のカテゴリの事後確率 P (c|LD(X)) は独立であると
仮定し，個別に定義する．
P (c|OA(X)) は以下の式を用いる．
P (c|OA(X)) =
1
exp(−woT OA(X)c)
+1
また，P (c|LD(X)) は以下の式を用いる．
P (c|LD(X)) =
1
exp(−wlT LD(X)c)
+1
wo と wl は分布を決定するパラメータであり，訓練データを用いてロジスティッ
ク回帰により決定する．
局所的な識別を繰り返して全体の識別結果を得る Iterative Classification の手
法であるため，各文書に対してクラスを割り当て，その割り当てた結果を用いて
他の文書のクラスを割り当てるという手続きを再帰的におこなう．
ラベル推定の手順は，以下のように行われる．
1. object features のみを用いて各文書に対してカテゴリを割り当てる
2. 終了基準を満たすまで各文書へのカテゴリの割り当てを再帰的におこなう
(a) リンク関係にある文書の現在のカテゴリの割り当てから，リンクに関
する統計を計算する
(b) 文書のカテゴリに関する事後確率を計算する
(c) 事後確率の最も高いカテゴリを新たなカテゴリとして選択する
7
2.2.2 Probabilistic Relational Models
Getoor らの Probabilistic Relational Models (PRMs) [6] は，Bayesian Network
を Relational Classification へ応用したモデルである．
Bayesian Network は有向グラフィカルモデルであり，変数を表すノードと変数
間の依存関係を表すエッジによって構成する．Getoor らは，推定する文書のカテ
ゴリから，その文書を構成する単語が生成される形でモデルを構成した．
問題点として，Bayesian Network は有向モデルであるため，循環するような形
でエッジを張ることができない．Web 文書の分類に用いる場合，相互にハイパー
リンクを持つような文書が存在する場合は，直接リンク構造をモデル化しようと
した場合，循環が生じてしまう．そのため，リンクの情報をノードに持たせる形
で間接的に扱っており，文書間のリンク関係を直接モデル化していない．
2.2.3 Relational Markov Networks
Taskar らの Relational Markov Networks (RMNs) [25] は，Markov Network の
条件付モデルである Conditional Markov Network を，データ間に依存関係のあ
るような問題へ適用するため拡張された無向グラフィカルモデルである．
ここではまず RMNs の出発点である Markov Network について述べ，次に Markov
Network の条件付モデル (conditional model) である Conditional Markov Network
について述べ，最後に Taskar らが提案した Conditional Markov Network の拡張
である RMNs について述べる．
Markov Network は，クリーク集合 C を持つ無向グラフ G = (V , E) において，
各クリーク c ∈ C を構成するノード集合 Vc ，クリークに対してポテンシャル関数
φc (Vc ) が与えられた時，以下のような分布を定義する．
P (V ) =
1 φc (Vc )
Z c∈C
ここで Z はパーティション関数と呼ばれる正規化項で，Z =
v
φc (v ) である．
Conditional Markov Network は，x を観測ノード集合，y を推定するラベル
ノード集合とするとき，以下のような条件付分布 (conditional distribution) を与
8
える Markov Network である．
P (y|x) =
1 φc (xc , yc )
Z(x) c∈C
ここで，xc はクリーク c を構成する観測ノード集合，yc はクリーク c を構成する
ラベルノード集合，Z(x) は正規化項で，Z(x) = y φc (xc , yc ) である．
RMNs は，Conditional Markov Network を，関係 (Relation) を持つ設定に拡張
したモデルであり，関係によって決定するグラフの構造 (relational structure) お
よび内容に関する特徴 (content attribute) が与えられた時の，各ノードに対する
全てのラベル割り当てに関する条件付分布を与える．
RMNs は以下の式で与えられる．
P (I.y|I.x, I.r) =
1
φc (I.xc , I.yc )
Z(I.x, I.r) C∈C
(1)
c∈C(I)
ここで Z(I.x, I.r) は正規化項で，Z(I.x, I.r) =
I.y
C∈C
c∈C(I)
φC (I.xc , I.yc )
である．x は観測ノード集合，y は推定するラベルノード集合である．
Taskar らは分類に用いる素性として，リンク関係にあるノードの間のラベル間
素性 (Link モデル)，またある特定の文書内に文書よりも小さい Section という単
位を考え，その Section とリンク先の間のラベル間素性 (Section モデル) を導入す
ることで文書間の依存関係をとらえた分類をおこなっている．Naı̈ve Bayes と比
較し，Link モデル，Section モデルが高い性能を示し，また，Link モデルの素性，
Section モデルの素性を単独で使用する場合と比較し，両方用いた場合に高い性
能を示したと報告している．
RMNs は，条件付マルコフネットワークであるという点では本稿で用いる Conditional Random Fields (CRFs) [10] と同一のモデルである [23]．CRFs について
は 3 節にて詳しく述べる．
2.2.4 Tree-structured Conditional Random Fields
Tang ら [8] は，Web 文書のレイアウトの階層性を考慮したモデルである Treestructured Conditional Random Fields (TCRFs) を提案した．
9
TCRFs は CRFs の特殊型で，以下の式で与えられる．
⎛
⎞
1
exp ⎝
p(y|x) =
λj tj (e, y|e , x) +
μk sk (v, y|v , x)⎠
Z(x)
pc
cp
ss
v∈V,k
e∈{E
,E
(2)
,E },j
ここで，V はノード，E pc は親から子への依存関係を持つエッジ, E cp は子から親
へ依存関係を持つエッジ, E ss は兄弟関係を持つエッジである．
Tang らは，企業の年次情報が記述された Web 文書から会社名や住所など全 14
項目を抽出する実験をおこない，SVM と比較して TCRFs が高い精度を示したこ
とを報告している．しかし，データからどのようにして E pc ，E cp ，E ss のエッジ
を構成するかは詳しく述べられていない．
2.3 Web 文書からの語彙獲得
Web 文書からの語彙獲得の研究としては，新里ら [29] が HTML のレイアウト
情報を利用して，単語クラスを自動的に抽出する手法を提案している．HTML 文
書において同一のレイアウト (リスト，テーブルなど) に現れる表現は互いに関連
しているということ、また，意味的に類似した表現同士は共起しやすいという傾
向を利用することで単語クラスの獲得をおこなう．具体的には，同一のレイアウ
トに現れる表現を関連する表現の集合として獲得し，それらの間の共起の強さを
検索エンジンにより得られるヒット件数を利用して相互情報量を求め，求めた相
互情報量を特徴量として Support Vector Machines [1] を用いて単語クラスかどう
か判別する．
本稿で獲得する固有表現のクラスは事前に定義されているが，新里らは獲得す
る語彙を固有表現に限定せず，単語クラスを獲得された単語から決定しているた
め，扱っている問題が異なる．
10
3. Conditional Random Fields
3.1 モデル
Conditional Random Fields (CRFs) [10] は，無向グラフィカルモデルであり，
観測系列 x が与えられた時のラベル系列 y の条件付確率 p(y|x) を与える確率モ
デルである．
CRFs は，観測系列 x と y の同時分布 p(x, y) をモデル化するような生成モデ
ル (generative models) とは異なり，観測系列 x が与えられた時のラベル系列 y の
条件付確率を直接モデル化する識別モデル (discriminative models) である．柔軟
な素性設計が可能である上，Hidden Markov Models (HMMs) などの生成モデル
と比較して高い性能を示すため，品詞タグ付け，テキストチャンキング [21]，テ
キストからのテーブル抽出 [18]，同一指示解決 (Coreference Resolution) [15] [28]，
関係抽出 (Relation Extraction) [5]，日本語形態素解析 [32] など様々な自然言語処
理の問題に適用され，高い精度を示している．
CRFs は以下のように定義される．G = {V, E} を確率変数 y 、x 上の無向グラ
フとする．クリーク集合 C = {{yc , xc }} が与えられたとき，CRFs は観測系列 x
が与えられた時のラベル系列 y の条件付確率 p(y|x) を定義する．
1 Φ(xc , yc )
(3)
Z(x) c∈C
ここで，Z(x) は正規化項であり，Z(x) =
y
c∈C Φ(xc , yc ) で与えられる．
P (y|x) =
これは可能なラベル割り当ての各条件付確率について足し合わせたものである．
Φ(xc , yc ) はポテンシャル関数と呼ばれ，クリークに対して定義される関数で
ある．ここで，ポテンシャル関数は事前に与えられる素性関数の集合 {fk } と，各
素性に割り当てられる重み {λk } に分解可能であると仮定すると，ポテンシャル
関数は以下の式となる．
Φ(xc , yc ) = exp
λk fk (xc , yc )
(4)
k
ここで fk (xc , yc ) は素性関数と呼ばれるもので，観測系列とラベル系列の特徴を
捉えるための関数である．クリークを構成するノード数 1(c = vi , |c| = 1) の場合
11
yt-1
xt-1
yt
xt
yt+1
xt+1
……
……
yT
xT
Linear-Chain CRFs
yt-1
yt
yt+1
yt-1
yt
yt+1
xt-1
xt
xt+1
……
……
……
yT
yT
xT
Factorial DCRFs
図 1 Linear-Chain CRFs と Factorial DCRFs のグラフ構造
の素性関数としては例えば以下のようなものが考えられる．
⎧
⎨1 if yi = ”経済” & xi = ”株”
fk (yi, xi ) =
⎩0 otherwise
(5)
また，λk (∈ Λ = {λ1 , ..., λK ∈ R}) は各素性関数に対する重みであり，モデル
を決定するパラメータである．
原論文 [10] では，系列タギング問題へ適用するためのモデル (Linear-Chain
CRFs) として提案されたが，その後，McCallum らにより，閉路を持つ CRFs(Dynamic
Conditional Random Fields, DCRFs) が提案された [14] [24]．Sutton らは Dynamic Conditional Random Fields の特殊型である，Factorial DCRFs を用いて，
品詞タグ付けおよびチャンキングを同時におこなう (Joint Inference) 手法を提案
し，品詞タグ付け，チャンキングを Linear-Chain CRFs を用いて個別におこなった
場合と比較して高い精度で推定ができたことを報告している．Linear-Chain CRFs
および Factorial DCRFs のグラフ構造を図 1 に示す．
3.2 パラメータ推定
パラメータ推定の問題は，訓練データ D = {x(i) , y (i) }N
i=1 が与えられたときに，
最適なモデルのパラメータ集合 Λ = {λ1 , λ2 , ..., λK } を推定する問題である．
12
具体的には，以下のような条件付対数尤度 LΛ を最大化するようなパラメータ
を推定する．
LΛ =
log p(y (i) |x(i) )
1
log
λk fk (yc(i) , x(i)
=
exp
c )
(i) )
Z(x
i
c∈C k
=
λk fk (yc(i) , xc(i) ) − log Z(x(i) )
i
i
c∈C
k
Λ̂ = arg max LΛ
Λ
LΛ を大きくすることは，正解のラベル割り当てと，正解以外のラベル割り当て
の選ばれやすさの差を最大化することに相当し，これによって全てのラベル割り
当てから正解のラベル割り当てを分別するような学習がおこなわれる．
目的関数は凸であり，最適点では以下の式が成り立つ．
∂L
=
fk (yc(i) , x(i) ) −
p(yc(i) |x(i) )fk (yc(i) , x(i) )
∂λk
y c∈C
i c∈C
i
(6)
パラメータの最適化には様々な方法があるが，Limited Memory BFGS (L-BFGS)[11]
がよく用いられる．
また，最尤推定を用いる場合，訓練データに対して過学習を起こしてしまう問
題が生じる．そこで，各パラメータに対して事前分布を考え，目的関数に以下の
式を用いることで過学習を防ぐことができる．
LΛ =
log p(y (i) |x(i) ) + log p(Λ)
(7)
i
ここで，log p(Λ) はパラメータの事前分布であり，これには Gaussian Prior [3]，
Laplacian Prior [9] などが用いられる．
13
平均 μ = 0 の Gaussian Prior を用いて正則化をおこなった場合，目的関数は，
λ2k
1
(i) (i)
exp − 2
LΛ =
log p(y |x ) +
log √
2σ
2πσ
i
k
λ2k
1
(i)
(i)
(i)
exp − 2
λk fk (yc , xc ) − log Z(x ) +
log √
=
2σ
2πσ
i
c∈C k
k
λ2
(i)
k
λk fk (yc(i) , x(i)
)
−
log
Z(x
)
−
+ Const
=
c
2
2σ
i
c∈C
k
k
となる．ここで，σ 2 は分散，Const は定数である．また，このとき，
∂L
λk
=
fk (yc(i) , x(i) ) −
p(yc(i) |x(i) )fk (yc(i) , x(i) ) − 2
∂λk
σ
y c∈C
i c∈C
i
(8)
となる ．
(i)
ここで，p(yc |x(i) ) は，観測系列 x(i) が与えられたときのクリーク c を構成する
ノードへのラベル割り当ての周辺確率である．周辺確率の計算は，モデルに閉路
が含まれていない場合は forward-backward アルゴリズムを用いて正確に計算する
ことが可能であるが，閉路が含まれている場合は近似手法を用いて用いて求める
必要がある．近似的に求める手法として，Loopy Belief Propagation，Tree-based
Reparameterization (TRP) [26] などがある．ここでは本稿で用いる Tree-based
Reparameterization について触れる．
Tree-based Reparameterization は，木構造のグラフにおいて周辺確率の正確
な計算ができることを利用し，閉路を含むグラフから構成できる全域木の集合
Υ = {T } を列挙し，各全域木について Belief Propagation などの手法を用いて推
論をおこない，周辺確率を更新していくという手続きを繰り返すことで近似的に
周辺確率を求めるアルゴリズムである．
まず，ノード集合 V ，エッジ集合 E ，クリーク C および各クリークに対して
定義されるポテンシャル関数 φc を持つ Markov Network(G = {V, E}) を考える．
TRP では，グラフを構成する各クリークの大きさは 1 または 2 であると仮定して
いる (Markov Network の場合は pairwise Markov Network)．クリークを構成す
るノード数が 3 以上の高次 Markov Network への適用は，超グラフ (hyper graph)
上で構成できる hyper tree 上でおこなうことが可能である [27]．
14
pairwise Markov Network では C = V ∪ E となり，ポテンシャル関数は確率変
数 x，ノードに対するポテンシャル関数を φs ，エッジのポテンシャル関数を φst
とすると，x の分布 p(x) は，以下の式で与えられる．
1 p(x) =
φs (xs )
φst (xs , xt )
Z
s∈V
(9)
(s,t)∈E
ここで，グラフ G が木である場合，式 (9) の分布は以下の式で表現することが
できる (Tree factorization)．
p(x) =
s∈V
μ( xs )
(s,t)∈E
μst (xs , xt )
μs (xs )μt (xt )
(10)
ここで，μs (xs ), μt(xt ) はノードの周辺確率，μst (xs , xt ) はエッジの結合周辺確率
である．
TRP の更新手続きについて述べる．TRP の手続きは，辺集合 E を持つグラフ
U の周辺確率 T n → T n+1 の更新手続きとして表すことができる．ここで，T は
ノードおよびエッジの周辺確率の集合であり，単一のノードの周辺確率 Tun+1 (xu )
n+1
とノード 2 つ組の周辺確率 Tuv
(xu , xv ) から構成される．n は反復 (iteration) の
回数を表している．
TRP は以下のような手続きを繰り返す．
0
1. 初期化: 各ノード，各エッジに対して，T 0 を，Tu0 = κφu , Tuv
= κφuv とし
て初期化する．ここで κ は正規化項である．
2. 更新: for i = 1, 2, ..., do:
• 辺集合 E i をもつ全域木 T i ∈ Υ を選択する．ここで，Υ = {T } はグ
ラフ U から構成できる全域木の集合である．
• Belief Propagation といったアルゴリズムを使用し，T i 上の正確な周
辺確率 μi (x) を計算する．全ての (u, v) ∈ E i に対して，以下の計算を
おこなう．
Tui+1 (xu ) = μi (xu )
i+1
Tuv
(xu , xv ) =
15
μi(xu , xv )
μi (xu )μi (xv )
• 全ての (u, v) ∈ E \ E i ，すなわち T i に含まれていない全ての辺につい
i+1
i
て，Tuv
= Tuv
とする．
選択した全域木 T ∈ Υ は，元のグラフ U の辺集合を全て含んでいなければな
らない．
16
図 2 Wikipedia の記事
4. Conditional Random Fields を用いた Wikipedia
文書中の固有表現分類
本節では，Conditional Random Fields を用いて Wikipedia から固有表現を獲
得し分類する，具体的な適用方法について述べる．
Wikipedia では，一文書につきある特定の事柄に関して記述されている．各記
事には，その事柄を表している語（見出し語），その事柄の定義文，その事柄に
関連する事柄が記述されている．また，その事柄が属する 1 つ以上の Wikipedia
のカテゴリが付与されている．例えば，図 2 の記事「東ローマ帝国」では，見出
語の定義文には「東ローマ帝国 (ひがしローマていこく、395 年-1453 年) は，東
西に分裂したローマ帝国の東方地域を継承し，オスマン帝国によって滅ぼされる
までの 1000 年以上にわたって存続した帝国．…（以下略）」と記述されている．
この定義文は，その項目が何について記述されているかを表す重要な手がかりと
「帝国」の 2 つが割
なる．また，Wikipedia のカテゴリとして「東ローマ帝国」，
り当てられている．カテゴリは，項目間で共通に持つような属性のラベルと考え
ることができる．
17
アンカー
リンク先あり
リンク先なし
×
図 3 HTML 文書中のリスト要素とアンカー
ここで，定義文やカテゴリなどの情報を手がかりに，その文書で述べられてい
る事柄がどのようなものかを分類する文書分類の問題として扱うことで固有表現
を獲得するという方法が，一つのアプローチとして考えられる．これは，その文
書に関する特徴を用いて分類対象となる文書を個別に分類するという，一般的に
用いられる文書分類の問題設定と同じである．
一方，Wikipedia は HTML 文書であり，これは半構造化された文書であるため，
構造化されていないテキストには無い特徴がある．その特徴の中で特に重要な特
徴を持っているのは，リスト (<UL><OL>など) およびテーブル (<TABLE>) であり，
これらに出現する要素には強い規則性がある．本稿ではこの中で，Wikipedia に
て頻繁に出現するリストに焦点を当てることにする．
図 3 において，リストの各要素 (<LI>タグで囲まれている要素) にはまず人名，
次に著書，出版社名，最後に出版年が規則的に並んでいる．このような規則性は
分類に寄与する重要な構造である．また，Wikipedia 内の記事にはアンカーが存
在する．アンカーとは，図 3 で示しているような，別の記事へのリンクのことを
いい，このアンカーからリンク先の記事を参照することができる．アンカーに記
述されている文字列は「アンカーテキスト」と呼ばれ，リンク先の記事が述べて
「香山リカ」，
いる事柄を表す単語または句が用いられる．ここで図 3 において，
「金子勝」などの著者名は，共著者という同じ文脈で出現しており，これは相互
「金
に依存関係を持っていると言える．すなわち「香山リカ」が” 人名” ならば，
子勝」も” 人名” であるという依存関係である．逆もまた成立する．
ここで，上記のようなリストの特徴およびアンカーテキストの存在を踏まえる
と，Wikipedia から固有表現抽出の問題を，依存関係を持つアンカーテキストに
18
<UL>
<UL>
<LI><A HREF=“…”>バート・バカラック</A> …
<A HREF=“…”>作曲家</A></LI>
<LI><A HREF=“…”>カーペンターズ</A>
<UL>
<LI><A HREF=“…”>カレン・カーペンター</A></LI>
</UL>
</LI>
</UL>
<LI>
<A>
<A>
<LI>
<A>
バートバカ
ラック 作曲家 カーペン
ターズ
<UL>
<LI>
<A>
カレン・カー
ペンター
図 4 HTML 文書と対応する DOM 構造の例
対するラベリング問題として扱うということが考えられる．リストなどの規則性
によって出現するアンカーテキストの依存関係を分類に利用することで，個別に
分類をおこなうアプローチと比較して高精度な分類が期待できる．
依存関係を考慮した分類には Conditional Random Fields を用い，ノード集合
V をアンカーテキストとし，アンカーテキスト間の依存関係を G のエッジ E と
するような無向グラフ G を構成し，各ノード vi ∈ V へのラベル割り当てが全体
で最適となるような arg maxy p(y|x) を求める問題として扱う．
次節にて具体的なグラフの構成の仕方について述べる．
4.1 DOM 構造からのグラフ構造の構築
HTML や XML といった半構造化された文書は，DOM (Document Object Model)
構造 [2] として表現される．ここで DOM とは，HTML 文書や XML 文書を扱う
ための Application Programming Interface (API) であり，DOM において HTML
および XML 文書の論理構造は木構造の形で扱われる．この構造を DOM 構造と
いう．HTML 文書と対応する DOM 構造を図 4 に示す．
DOM 構造は，唯一の親を持ち，子が順序をもつ順序木として扱うことができ
る．図 4 では，唯一の他と区別される頂点が<UL>に対応し，各タグの子に対応す
るタグには出現順序があるため，順序木の定義を満たす．(通常は，唯一の親に対
19
応するのは<HTML>タグであるが，説明の簡単化のため図 4 のような局所的な構造
を示した．) よって以後，DOM 構造を順序木として扱う．
次に，DOM 構造から Conditional Random Fields を構成するために，無向グ
ラフ G のクリーク C を定義する．ここで問題となるのは，どのようなクリークを
定義するかということである．一般的にどのようなノード集合をクリークとする
かは，クリークを構成するノード間に何らかの依存関係があるかどうかを基準と
すればよい．ここで，図 4 の例において，依存関係が考えられるアンカーの組に
ついて考えることにする．まず，
「バート・バカラック」と「作曲家」は，DOM 構
造上では兄弟関係であり，同一のリストの中で出現している．この間には，
「バー
ト・バカラック」の職業が「作曲家」であるというような関係が成り立ち，この
ような出現の仕方には，先に出現したものが持っている属性，または関連する事
柄が後ろに来るという傾向がある．
次に「バート・バカラック」と「カーペンターズ」という関係は，DOM 構造上
では従兄弟の関係になっている．これらの間には，ある特定の属性を共通に持っ
ているという関係があると言え，このような出現の仕方は，双方が同じようなク
ラスに属する傾向がある．
「カーペンターズ」と「カレン・カーペンター」の関係は，DOM 構造上では，
「カーペンターズ」から見て「カレン・カーペンター」が兄弟の孫という関係に
なっている．これらの間には「カーペンターズ」の構成員としての「カレン・カー
ペンター」という関係があり，このような出現の仕方は，先に出現したものを構
成している要素が後にくる傾向がある．
このような，相互に依存関係があるようなアンカーの集合をクリークを構成す
るノードとすることで，依存関係を捉えることができると考えられる．ここで，
上記の観察に基づき，DOM 構造上において以下で述べる 3 つのクリークの定義
に該当するものを，CRFs のクリークとする．
DOM 構造に対応する順序木を T ordered = (V T , E T ) とする．まず，先祖・子関係
にある頂点間 viT , vjT ∈ V T に対して距離 d(viT , vjT ) を定義する．頂点 viT , vjT ∈ V T
間の距離を d(viT , vjT )，順序木の頂点 viT ∈ V T から k 回辿った先祖を pa(viT , k)，
頂点 viT の k 番目の子を ch(viT , k)，頂点 viT , vjT ∈ V T の共通の先祖を cpa(viT , vjT )，
20
<UL>
<UL>
<LI><A HREF=“…”>バート・バカラック</A> …
<A HREF=“…”>作曲家</A></LI>
<LI><A HREF=“…”>カーペンターズ</A>
<UL>
<LI><A HREF=“…”>カレン・カーペンター</A></LI>
</UL>
</LI>
</UL>
<LI>
<A>
<LI>
<A>
<A>
バートバカ
ラック 作曲家 カーペン
ターズ
Sibling
Cousin
Relative
<UL>
<LI>
<A>
カレン・カー
ペンター
図 5 DOM 構造と定義したクリークとの対応関係．
と表すことにする．
以下の 3 つの関係をクリークとして定義する．
Sibling 共通の先祖までの距離が 1(すなわち親が同じ) であり，なおかつ親からの
順序が最も近い頂点の対．すなわち次のような集合を Sibling とする．ES =
{(viT , vjT )|viT , vjT ∈ V T , d(viT , cpa(viT , vjT )) = d(vjT , cpa(viT , vjT )) = 1, vjT =
ch(pa(vjT , 1), k), viT = ch(pa(viT , 1), max{l|l < k})}
Cousin viT , vjT の共通の先祖までの距離が 2 以上で等しく，なおかつ親からの
順序が等しい頂点の組の中で，共通の先祖の子の順序が最も近い頂点の
対．すなわち次のような集合を Cousin とする．EC = {(viT , vjT )|viT , vjT ∈
V T , d(viT , cpa(viT , vjT )) = d(vjT , cpa(viT , vjT )) ≥ 2, viT = ch(pa(viT ), k), vjT =
ch(pa(vjT ), k), pa(vjT , d(vjT , cpa(viT , vjT ))−1) = ch(pa(vjT , d(vjT , cpa(viT , vjT ))), k),
pa(viT , d(viT , cpa(viT , vjT )) − 1) = ch(pa(viT , cpa(viT , vjT )), max{l|l < k})}
Relative 共通の先祖までの距離が vi からは 1，vj からは 3 であり，vi と，vj の親
の親の順序が最も近い頂点の対．すなわち次のような集合を Relative とする．
ER = {(viT , vjT )|viT , vjT ∈ V T , d(viT , cpa(viT , vjT )) = 1, d(vjT , cpa(viT , vjT )) =
3, vjT = ch(pa(vjT , 1), k), pa(viT , 2) = ch(pa(viT , 3), max{l|l < k})}
ES は Sibling の関係にある頂点の組の集合，EC は Cousin の関係にある頂点の組
の集合，ER は Relative の関係にある頂点の組の集合を表している．ここで，上
21
記の関係の定義にて，関係として扱う頂点の組を，ある頂点とその頂点から最も
近い頂点に限定している．その理由は，もし「最も近い」という条件を除いた場
合，ある頂点と特定の関係にある頂点の数は複数個該当する可能性が出てくるが，
それらの組を全てクリークとした場合，計算量の問題が生じるためである．例え
ば，|A| = 8 とし，それらの間に全て Cousin の関係があるとすると，クリーク数
は 82 = 28 と，指数的に増大する．本稿では周辺確率 p(yi |x) の計算および最適
解 ŷ = arg maxy p(y|x) の導出に TRP を用いるが，TRP では前述の通り，グラ
フから構成できる全域木を列挙し，周辺確率の更新をおこなう．エッジの数が増
加するとそれに伴って構成できる全域木が増え，計算量が多くなる．
上記の定義を満たす頂点の組を，構成する Conditional Random Fields のクリー
クとする．すなわち，C = ES ∪ EC ∪ ER である．図 5 に，DOM 構造とクリーク
の対応関係を示す．
次節以降，ラベル間の依存関係を考慮した 2 つのモデルを提案する．
4.2 model 1
前節で定義したクリーク C を持つ無向グラフ G = (V, E) のクリークに対して
ポテンシャル関数を定義することで p(y|x) を与える CRFs を構成する．
model 1 の，観測系列 x が与えられたときのラベル系列 y の条件付分布を以下
の式で与える．
⎛
1 ⎝
p(y|x) =
Z(x)
⎞
ΦSCR (yi, yj )⎠
ΦV (yi , x)
(11)
vi ∈V
(vi ,vj )∈ES ,EC ,ER
Z(x) は正規化項で，
Z(x) =
y
⎛
⎝
⎞
ΦSCR (yi , yj )⎠
ΦV (yi , x)
vi ∈V
(vi ,vj )∈ES ,EC ,ER
である．ここで，ΦSCR (yi , yj ) は Sibling, Cousin, Relative {(vi , vj ) ∈ ES , EC , ER }
22
に対応するクリークのポテンシャル関数で，以下の式で与える．
ΦSCR (yi , yj ) = exp
λk fk (yi , yj )
(12)
k
ここで，k ∈ {(yi , yj )|Y × Y} であり，これはラベル集合 Y の直積集合のある要素
に対応する．素性関数は例えば以下のようなものが考えられる．
⎧
⎨1 if yi = ”人名” & yj = ”人名”
fk (yi , yj ) =
⎩0 otherwise
この素性は，クリークを構成するノード vi , vj ∈ V に対するラベル割り当てが，
双方ともに人名であるかどうかという素性である．このような素性を導入するこ
とで，どのようなラベルの組合せが起こりやすいかを学習することができる．訓
練データにおいて上記の組合せが頻繁に出現した場合，fk (yi , yj ) に対応する素性
の重み λk が大きくなり，この組合せが選択されやすくなる．
ΦV (yi, x) はノード vi ∈ V に対応するポテンシャル関数であり，以下の式で与
える．
ΦV (yi, x) = exp
λk fk (yi , x)
(13)
k
ここで，k ∈ {(yi , xj )|Y × X } であり，これは観測系列に出現する素性 xj と，ラ
ベル yi ∈ Y の共起をとらえるための素性である．素性関数は例えば以下のよう
なものが考えられる．
⎧
⎨1 if yi = ”人名” & xj = ”タレント”
fk (yi, xj ) =
⎩0 otherwise
これは，観測系列に”タレント”という形態素が出現し，なおかつそのラベルが”
人名”であるかどうかという素性である．”タレント”という単語が含まれ，なお
かつそれが人名について述べられている傾向が訓練データに強く現れていた場合，
fk に対応する重み λk が大きくなり，”タレント”という形態素が出現している場
合に”人名”のラベルが選ばれやすくなる．
model 1 は，基本的には ΦV によって各ノードに付与されるべきラベルが何で
あるかを捉え，ΦSCR によって各クリークの依存関係を捉えることにより相互に
影響を及ぼし合うことで，全体として最適となるようなラベル系列が選択される．
23
4.3 model 2
model 1 では，各クリーク (vi , vj ) ∈ ES , EC , ER のポテンシャル関数に対して定
義した素性関数は，単純に Y × Y のラベルの組み合わせについてのみ見ており，
観測系列を全く考慮していなかったが，観測系列から得られる素性を結びつける
ことで，どのような観測素性が現れたときに依存関係が強く現れるかということ
を学習できると考えられる．
ここで，3 つのクリークのうち，一番重要な依存関係があると考えられるのは
Cousin である．Cousin の関係にあるアンカーは，一般的には同じラベルになり
やすいという傾向があるが，そのような関係にあるアンカー全てが同じラベルに
なるというわけではない．そのため，観測素性を model 1 で用いた式 (12) に結び
つけたものを Cousin に対応するクリークのポテンシャル関数とすることで，ど
のような場合に同じラベルになりやすいかを学習することが可能になると考えら
れる．
model 2 の，観測系列 x が与えられたときのラベル系列 y の条件付分布を以下
の式で与える．
⎛
1 ⎝
p(y|x) =
Z(x)
⎞⎛
ΦC (yi , yj , x)⎠ ⎝
(vi ,vj )∈EC
⎞
ΦSR (yi , yj , x)⎠
ΦV (yi , x)
vi ∈V
(vi ,vj )∈ES ,ER
(14)
ここで Z(x) は正規化項で，
⎞⎛
⎛
⎝
Z(x) =
ΦC (yi, yj , x)⎠ ⎝
y
(vi ,vj )∈EC
⎞
ΦSR (yi, yj , x)⎠
ΦV (yi, x)
vi ∈V
(vi ,vj )∈ES ,ER
である．また，ΦC (yi , yj , x) は Cousin {(vi , vj ) ∈ EC } に対応するクリークのポテ
ンシャル関数, ΦSR (yi , yj , x) は Sibling，Relative {(vi , vj ) ∈ ES , ER } に対応する
クリークのポテンシャル関数，ΦV (yi , x) はノードに対応するポテンシャル関数を
表している．
ここで，model 1 で用いた Cousin に対応するクリークのポテンシャル関数 ΦC (yi , yj , x)
を以下の式で与える．
ΦC (yi , yj , x) = exp
k
24
λk fk (yi , yj , x)
(15)
ここで，k ∈ {(yi , yj , xl )|Y × Y × X } であり，ラベル yi , yj ∈ Y に対して観測系列
に出現する素性 xj を結び付けた素性である．素性関数は例えば以下のようなも
のが考えられる．
⎧
⎨1 if yi = ”人名” & yj = ”人名” & xl = ”タレント”(∈ (xi ∩ xj ))
fk (yi , yj , xl ) =
⎩0 otherwise
ここで，xi , xj ⊆ x であり，xi はノード vi に対応する観測系列，xj はノード vj に
対応する観測系列を表している．これは，クリークを構成するノード双方のラベ
ルが”人名”であり，なおかつ各ノードに対応する観測系列 xi と xj に”タレント”
という形態素が共通して出現しているかどうかという素性である．”タレント”と
いう単語が観測系列に共通に含まれ，なおかつそれが人名について述べられてい
る傾向が訓練データに強く現れていた場合，fk に対応する重み λk が大きくなり，
双方で”人名”のラベルが選ばれやすくなる．
ΦSR (yi , yj , x) は，model 1 で用いた式 (12) と同様の式を Sibling および Relative
に対応するクリークのポテンシャル関数とする．
ΦSR (yi , yj , x) = exp
λk fk (yi , yj , x)
(16)
k
ここで，k ∈ {(yi , yj )|Y × Y} である．
また，ΦV (yi , x) についても model 1 で用いた式 (13) と同様の式を用いる．
ΦV (yi , x) = exp
λk fk (yi, x)
(17)
k ここで，k ∈ {(yi , xj )|Y × X } である．
4.4 周辺確率の算出によるラベルの信頼度推定
CRFs では，グラフ G のノード vi ∈ V に対するラベル割り当ての周辺確率
p(yi|x) を求めることができる．周辺確率は，識別器がどの程度自身をもってラベ
ルを割り当てたかという確信度，どの程度信用できる結果であるかという信頼度
とみなすことができる．
25
本稿では，文書中のアンカーがどの固有表現に属するか，各アンカーに対して
ラベル割り当てをおこなうが，得られた結果から固有表現の辞書を作成し，応用
に用いるといったことが考えられる．CRFs によって得られた結果には誤りは必
ず含まれるため人手で確認するという作業を省くことは不可能であるが，確率が
高いラベル割り当てほど一般的には誤りが少ないものと考えられるため，算出し
た周辺確率を用いることで，信頼度の高い結果のみを人手で確認するということ
が可能となり，それによって人手のコストが削減され，作業を効率的におこなう
ことができるようになると考えられる．
周辺確率を積極的に利用した研究としては，Peng ら [17] が中国語のわかち書
き問題に対して Linear-Chain CRFs を適用し，わかち書き問題で生じる未知語の
同定に，Linear-Chain CRFs によって求められる周辺確率を用いている．中国語
は日本語と同様，明示的な単語境界が与えられないため，まず単語境界を同定す
る必要があるが，辞書に登録されていない文字列が出現した場合，正しく単語境
界を推定することが難しい．そこで，辞書に登録されていない文字列のある特定
の分割がどの程度信頼できるものか，周辺確率を用いて算出するということをお
こなっている．特定の分割の周辺確率の算出は制約付き forward-backward [4] を
用い，確率の高いものを辞書に追加していくことでわかち書きの精度を向上させ
ている．
工藤ら [31] は，形態素解析において，テキストの分割を一意に定めるのではな
く，可能な分割の各形態素に対する期待頻度を周辺確率から算出し，曖昧性を保っ
たまま扱う手法を提案している．一般に，複合語で構成される単語列は，どの分
割が最適か一意に決定するのは困難である．そのような問題が生じるものとして
は，例えば以下のようなものがある．
• 本部長 本部/長 or 本/部長
• 応援団員 応援団/員 or 応援/団員
このような例に対して，一意に単語分割列を与えるのではなく，可能な分割にお
ける各形態素の期待頻度からなる BOW(bag-of-words，単語の集合) のベクトル
として扱うことで，多様な分割を保持したまま扱うことが可能となる．
26
岡野原ら [30] は，Linear-chain CRFs の周辺確率を用いて文字列境界の分割確
率を算出し，確率的単語分割コーパスを構築する方法を提案している．確率的単
語分割コーパス [16] は，コーパス x1...n と連続する 2 文字 xi , xi+1 の間に単語境界
が存在する確率 Pi の組として定義される．確率変数 Xi を，
⎧
⎨1 xi , xi+1 の間に単語境界が存在する場合
Xi =
⎩0 x , x が同じ単語に属する場合
i
i+1
とすると，単語分割確率は P (Xi = 1) = Pi , P (Xi = 0) = 1 − Pi で与えられる．
ここで原論文では形態素解析の結果，単語境界であると判断された境界について
は Pi = α，そうでない場合は Pi = 1 − α としていたが，このような決め方をした
場合，もし非常に近い確率の 2 通りの分割が可能性としてあった場合でも片方の
み採用され，もう一方の情報は失われてしまう．そこで，このような問題に対処
するため，この分割確率に Linear-chain CRFs によって算出できる周辺確率を用
いることが岡野原らの提案である．Linear-chain CRFs の周辺確率を用いること
によって，全系列の情報が分割確率に反映されるため，上記の問題が解決される．
27
5. 実験
本節では，前節で述べた手法を用いて，Wikipedia の記事から固有表現を獲得
する評価実験の結果について報告する．
5.1 訓練・評価用データ
2005 年 10 月 29 日時点の Wikipedia の記事から，ランダムに選択した日本語の
記事約 2300 について，HTML のリスト (<LI>タグ) 内に含まれるアンカー (<A>タ
グ) に対して，関根の拡張固有表現階層の対応するクラスを人手で付与したデー
タを用いる．ここで，リンク先の記事が存在しない場合 (アンカーのみ存在する
場合) についても，記事が存在する場合と同様にクラス付与をおこない分類対象
とした．また，Sibling，Cousin，Relative の関係にあるアンカーによって構成さ
れる連結グラフのノード数が 2 以下となるような事例については分類対象から除
外した．その結果，全体で 16136 アンカーが分類対象となった．このうち，固有
表現は 14285 である．
関根の拡張固有表現階層のクラス数は 200 以上であるが，本稿ではラベル数を
限定し，拡張固有表現階層の深さ 2 までに限定したラベルセットを使用した．ま
た，訓練・テストデータに存在する数が極端に少ない固有表現クラスについては，
一つのクラスに統合した．名前-識別番号 (ID NUMBER)，名前-神名 (GOD)，名
前-病気名 (DISEASE)，名前-名前＿その他 (NAME OTHER) を統合して「名前その他」に，数値表現-個数 (COUNTX)，数値表現-学齢 (SCHOOL AGE)，数値
表現-寸法表現 (MEASUREMENT) は，時間表現-時間 (TIMEX) と統合して「時
間・数値表現」とした．また，固有表現クラスに該当しないアンカーは「固有表
現以外」とした．その結果，訓練・評価用データに含まれるクラス数は，全体で
13 クラスとなった．拡張固有表現階層のクラスと Wikipedia 記事数の対応を表 3
に示す．統合対象となったクラス以外で，表 3 に存在しないクラスは，訓練・テ
ストデータに存在しなかったものである．
28
固有表現クラス
名前
SIZE
イベント名 (EVENT)
人名 (PERSON)
単位名 (UNIT)
地名 (LOCATION)
施設名 (FACILITY)
称号名 (TITLE)
組織名 (ORGANIZATION)
職業名 (VOCATION)
自然物名 (NATURAL OBJECT)
製品名 (PRODUCT)
名前＿その他 (NAME OTHER)
時間・数値表現
時間・数値表現
固有表現以外
全体
121
3315
15
1480
2449
42
991
303
1132
1664
24
2749
1851
16136
表 3 訓練・評価用データの固有表現クラスと Wikipedia の記事数一覧
5.2 実験方法・評価
本稿で提案した手法の有効性を示すために，ベースラインの手法として汎化性
能に優れ，文書分類など多くの分類問題において高い精度を示している Support
Vector Machines (SVM) [1] を用い，CRFs との精度を比較する．
SVM は 2 値分類器であるのに対して，本稿で扱っている問題は多値分類問題
である．そこで，識別器を組み合わせて多値分類を行う one-vs-rest 法を用いて分
類をおこなう．one-vs-rest 法は，Z = {Z1 , Z2 , ..., Zn } の多値分類問題を，Zk に
属するか，属さないかという二値分類問題に分解して解く手法であり，SVM を
多値分類問題へ適用するためによく用いられる．CRFs，SVM で用いた素性を表
4 に示す．
CRFs のグラフを構成するために定義した 3 種類のクリークのうち，どのクリー
クが精度向上に寄与するかを調査するため，Sibling(S)，Cousin(C)，Relative(R)
の各クリークを含むか含まないかの全組合せについて実験をおこなう (SCR 全て，
29
S
S
C
C
C
R
C
S
C
R
C
S
S
S
C
C
C
S
S
C
R
S
S
S
S
R
SC model
SCR model
S
SR model
S
C
C
C
R
C
C
S
C
R
S
CR model
S model
R model
I model
C
C
C
C
C model
R
R
図 6 Sibling，Cousin，Relative を含めるか含めないかの各組合せによって構成さ
れるグラフ．モデル名の S は Sibling クリーク，C は Cousin クリーク，R は Relative
クリークが，構成されるグラフに含まれることを表している．各モデルにおいて，
連結部分グラフごとに分類がおこなわれる．I には定義したクリークは含まれず，
各アンカーは個別に分類される．
30
素性の種類
素性
unigram
features
記事の定義文 (bag-of-words)
記事の見出し
記事の見出し (形態素)
記事のカテゴリ
記事のカテゴリ (形態素)
リンク元のアンカーテキスト
リンク元のアンカーテキスト (形態素)
アンカーテキストの親タグ
アンカー直前のヘッダのテキスト
アンカー直前のヘッダのテキスト (形態素)
bigram
features
other
SVM
√
√
√
√
√
√
√
√
√
√
ラベル間素性
ラベルと特定の unigram feature
前ラベル
CRFs (model 1)
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(S, C, R)
√
CRFs (model 2)
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(V )
√
(S, R)
√
(C)
√
表 4 分類に用いる素性．” ” は該当する素性を与えたこと，CRFs の V はノー
ドに対して，S は Sibling，C は Cousin，R は Relative クリークに対して素性を
与えたことを意味している．
SC，SR，CR，S のみ，C のみ，R のみ，個別に分類 (I とした) の 8 通り)．各設
定によって構成されるグラフの例を図 6 に示す．各クリークを除いた結果，グラ
フが全体で非連結となるものについては，その構成要素となる部分連結グラフご
とに分類をおこなう．
SVM による識別では，アンカーを個別に分類する手法 (以後 I)，SCR によって
構成されるノード集合に対応するアンカー A = {a1 , a2 , ..., aN } のうち，出現順序
の早いものから順番に識別する手法 (以後 P) の 2 種類の手法を適用した．P では
アンカー aj の識別に，アンカー aj−1 の識別結果を素性として用いた．
評価は Wikipedia データを 5 分割し，訓練 4，テスト 1 の比率で交差検定によ
りおこなう．交差検定のためのデータの分割は，SCR によって構成されるグラフ
の部分連結グラフ単位でおこない，分類対象となるアンカー数が各データセット
ごとに，ある程度等しくなるよう分割をおこなった．
31
各固有表現クラスおよび全体の抽出精度の評価には以下の 3 つの尺度を用いる．
システムが正しく固有表現のクラスを同定した数
システムが固有表現であると判断した数
システムが正しく固有表現のクラスを同定した数
Recall =
固有表現の数
2 × P recision × Recall
F値=
P recision + Recall
P recision =
CRFs の学習および実行には，GRaphical Models in Mallet (GRMM) [22] を
用い，パラメータ推定および最適解の算出には Tree-based Reparameterization
(TRP) を，モデルの各素性に対する重みの事前分布には Gaussian Prior を用い，
分散は σ 2 = 10 に設定した．SVM の学習および実行には，TinySVM 2 を用い，
カーネルは線形カーネルを用いた．また，形態素の素性を得るため，形態素解析
器として MeCab 3 を用いた．
5.3 実験結果・考察
表 5 は，アンカーのリンク先に文書が存在するもの，しないものの双方を含め
た Wikipedia データに対する，SVM と CRFs (model 1) の各固有表現クラスおよ
び全体の F 値を示している．
全体の傾向として，イベント名，単位名など全体数の少ない固有表現について
は，CRFs (model 1) と比較して SVM の精度が高い傾向となっているが，人名，
地名，製品名など出現する頻度の高い固有表現については CRFs が SVM を上回
る結果となり，全体として CRFs が高い精度を示す結果となった．これは，CRFs
においてノード間の依存関係を捉えた分類をおこなったことで，全体として良い
結果が得られたものと考えられる．
CRFs の Sibling，Cousin，Relative の各クリークを含めた場合と含めなかった
場合の全ての組合せの中では，Cousin と Relative を含む場合 (CR) に最も高い F
値が得られ，以降 SC，SCR，C，SR，S，R，I の順となっている．これは，個
別に分類する場合 (I) と比較し，依存関係を考慮した分類をおこなうことで精度
2
3
http://www.chasen.org/ taku/software/TinySVM/
http://mecab.sourceforge.net/
32
CRFs (model 1)
NE CLASS
人名
時間・数値表現
施設名
製品名
地名
自然物名
組織名
職業名
イベント名
称号名
名前・その他
単位名
ALL
N
3315
2749
2449
1664
1480
1132
991
303
121
42
24
15
14285
C
.7419
.9936
.8546
.7414
.7265
.3333
.7122
.9088
.2740
.1702
.0000
.2353
.7846
CR
.7429
.9944
.8541
.7540
.7239
.3422
.7160
.9050
.2345
.0889
.0000
.1250
.7862
I
.7453
.9940
.8540
.7164
.6989
.3476
.7100
.9075
.2533
.2800
.0000
.2353
.7806
R
.7458
.9936
.8516
.7208
.7048
.3513
.7073
.9059
.2667
.2800
.0000
.2353
.7814
S
.7507
.9938
.8500
.7130
.6974
.3547
.7122
.9150
.2800
.3462
.0000
.2353
.7817
SVM
SC
.7533
.9931
.8530
.7371
.7210
.3294
.6961
.9122
.2740
.2083
.0000
.1250
.7856
SCR
.7981
.9933
.8495
.7418
.7232
.3304
.5580
.9100
.2759
.1277
.0000
.1250
.7854
SR
.7515
.9940
.8495
.7187
.7033
.3316
.7109
.9186
.2667
.3462
.0000
.2353
.7823
I
.7383
.9933
.8504
.7154
.7022
.3670
.7141
.9091
.3418
.2593
.0690
.3333
.7790
P
.7386
.9935
.8560
.7135
.7132
.3326
.7180
.9069
.3500
.2642
.0000
.3158
.7798
表 5 CRFs (model 1) と SVM の分類精度 (全体，F 値)．CRFs (model 1) の S は
Sibling クリーク，C は Cousin クリーク，R は Relative クリークが，構成される
CRFs のエッジに含まれていることを意味し，I は事例を個別に分類したことを意
味している．SVM の I は個別に，P は前ラベルを与えて分類をおこなったことを
意味している．
向上が可能であることを示している．また，定義した 3 種類のクリークのうち，
Cousin が最も精度向上に寄与している．これは，他のクリークと比較して出現頻
度が高く，またクリークを構成するアンカー間に強い依存関係があるがゆえ，精
度に影響を与えているものと考えられる．
各固有表現クラス個別の分類精度に関して，まず人名については Sibling，Cousin
を含むもの (SC，SCR) にて高い F 値が得られた．データ中の Sibling の関係にあ
るラベルの組で双方のアンカーのラベルが人名である事例は 4925 中 435，Cousin
の関係にあるラベルの組で双方のアンカーのラベルが人名である事例は 13125 中
2557 であり，それぞれ高い頻度で出現していたため，ラベル間素性が有効に働き，
高い精度で分類できたものと考えられる．製品名，地名については Cousin を含
むもの (C，CR，SC，SCR) にて高い F 値が得られた．Cousin の関係にあるラベ
ルの組で双方のアンカーのラベルが製品名である事例は 1072，地名である事例は
738 と高頻度で出現していたため，高い頻度で分類できたと考えられる．
表 6 は，表 5 の実験結果のうちリンク先が存在しないアンカーのみ，SVM と
33
CRFs (model 1)
NE CLASS
施設名
人名
自然物名
地名
製品名
組織名
イベント名
名前・その他
時間・数値表現
職業名
単位名
称号名
ALL
N
1080
1068
623
552
359
174
21
8
7
4
1
1
3898
C
.9363
.6709
.0799
.5306
.6894
.2120
.1000
.0000
.8571
.5714
.0000
.0000
.6469
CR
.9369
.6732
.0795
.5303
.6991
.2353
.0909
.0000
.8571
.5714
.0000
.0000
.6487
I
.9343
.6480
.0828
.4631
.6089
.2342
.1000
.0000
.6667
.0000
.0000
.0000
.6231
R
.9351
.6492
.0828
.4758
.6133
.2192
.1000
.0000
.6667
.0000
.0000
.0000
.6258
S
.9273
.6507
.0858
.4540
.6169
.3108
.0000
.0000
.8571
.5714
.0000
.0000
.6245
SVM
SC
.9382
.6741
.0284
.5313
.6839
.2648
.0000
.0000
.8571
.5714
.0000
.0000
.6463
SCR
.9347
.6855
.0222
.5236
.6851
.2132
.0000
.0000
.8571
.5714
.0000
.0000
.6440
SR
.9324
.6441
.0253
.4593
.6034
.2996
.0000
.0000
.8571
.5714
.0000
.0000
.6182
I
.7602
.5485
.0712
.3157
.5867
.3165
.1739
.0000
.5455
.4000
.0000
.0000
.5278
P
.7789
.5572
.0712
.3121
.6066
.2932
.1739
.0000
.6000
.4000
.0000
.0000
.5386
表 6 Wikipedia データの CRFs (model 1) と SVM の分類精度 (リンク先なしの
み，F 値)．
CRFs (model 1) の各固有表現クラスおよび全体の分類結果 (F 値) をまとめたも
のである．
リンク先が存在しない場合，見出語，定義文，Wikipedia のカテゴリの情報が
欠落するため分類が難しくなる．そのため，CRFs，SVM の双方，F 値が大幅に低
下しているが，CRFs (model 1) の精度低下の幅は SVM と比較して小さく，SVM
との差が顕著に現れる結果となった．これは，CRFs において依存関係をとらえた
分類が精度向上に寄与しているものと考えられる．各固有表現クラス個別の分類
精度に関して，出現頻度の低い固有表現クラスについては差がみられないが，施
設名，人名，地名，製品名など，出現数の多い固有表現クラスについては，SVM
と比較して高い精度を示している．特に，Cousin クリークを含むものについては，
地名，製品名において，Cousin クリークを含まないものと比較して精度向上が顕
著である．これらはリスト内で列挙された出現の仕方をしていることが多く，こ
のようなアンカーの出現に対して依存関係を考慮した分類が有効であることを示
している．
表 7 は，CRFs の (model 1) と CRFs (model 2) は，アンカーのリンク先に文書
が存在するもの，しないものの双方を含めた Wikipedia データに対する，CRFs
(model 1) と CRFs (model 2) の各固有表現クラスおよび全体の F 値を示してい
34
CRFs (model 1)
NE CLASS
人名
時間・数値表現
施設名
製品名
地名
自然物名
組織名
職業名
イベント名
称号名
名前・その他
単位名
ALL
N
3315
2749
2449
1664
1480
1132
991
303
121
42
24
15
14285
C
.7419
.9936
.8546
.7414
.7265
.3333
.7122
.9088
.2740
.1702
.0000
.2353
.7846
CR
.7429
.9944
.8541
.7540
.7239
.3422
.7160
.9050
.2345
.0889
.0000
.1250
.7862
SC
.7533
.9931
.8530
.7371
.7210
.3294
.6961
.9122
.2740
.2083
.0000
.1250
.7856
CRFs (model 2)
SCR
.7981
.9933
.8495
.7418
.7232
.3304
.5580
.9100
.2759
.1277
.0000
.1250
.7854
C
.7419
.9915
.8558
.7352
.7104
.3071
.7223
.9031
.2416
.0465
.0000
.1250
.7815
CR
.7411
.9920
.8535
.7346
.7114
.2960
.7095
.9034
.2400
.0909
.0000
.1250
.7797
SC
.7458
.9909
.8528
.7163
.7033
.3088
.7090
.8997
.2597
.0889
.0000
.1250
.7783
SCR
.7565
.9907
.8512
.7157
.6963
.3218
.6731
.8877
.2710
.0870
.0000
.1250
.7779
表 7 Wikipedia データの CRFs (model 1) と CRFs (model 2) の分類精度比較 (全
体，F 値)．
る．model 1 と model 2 では，Cousin クリークに対する素性の与え方のみ異な
り，Sibling，Relative クリークに対する素性の与え方は同じであるため，ここで
は Cousin クリークを含む model の結果のみを示している．
まず全体の傾向として，CRFs (model 1) と比較し，CRFs (model 2) の F 値は
やや低い傾向がある．CRFs (model 1) における Cousin クリークにおける素性の
数 |FCmodel1 | がラベルの組合せの数 |FCmodel1 | = |L| × |L| であるのに対し，CRFs
(model 2) における Cousin クリークの素性の数 |FCmodel2 | は，ラベルの全組合せの
数と観測素性の数の積 |FCmodel2 | = |L| × |L| × |Fo|(Fo : 観測素性) となる．ラベ
ルの組によっては，データ中の出現数が僅かであるものも存在するため，観測素
性を結びつけることで素性空間がスパースとなり，パフォーマンスの低下につな
がっていると考えられる．
次に各固有表現クラス個別の分類精度に関して，まず人名については Cousin ク
リークの関係にあるアンカーの組全体 (13125) のうち，アンカーの組の固有表現
クラスが「人名-人名」となってるものは 2557 であった．これは，Cousin クリー
35
0.95
0.90
0.85
Precision
0.80
model 1
model 2
0.4
0.5
0.6
0.7
0.8
Recall
図 7 CRFs (model 1, model 2) の分類精度の Precision-Recall 曲線
ク全体の中最も頻出する固有表現クラスの組合せである．しかし，model 2 の人
名の分類精度は model 1 と比較して大差はみられず，SCR model では逆に精度が
低下してしまうなど，期待した効果を得ることはできなかった．
図 7 は，CRFs (model 1，model 2) の CR の実験結果について，各ラベル割り当
ての周辺確率 p(yj |x) を閾値でフィルタリングした時の Precision と Recall の関係
をプロットしたものである．ここで，図 7 中の実線は model 1 の Precision-Recall
曲線，破線は model 2 の Precision-Recall 曲線である．双方ともに Recall0.6 付近
にピークがあり，その点での Precision は 0.98 近くとなっている．これは，デー
タ中に存在する固有表現全体のうち 6 割を，精度 98%，つまり 50 固有表現候補中
誤りが 1 程度と非常に高い精度で獲得できることを示している．このように，周
辺確率を用いてフィルタリングをおこなうことによって，少ないコストで固有表
現を獲得することが可能である．
36
6. おわりに
本稿では，Web 上の多言語百科事典である Wikipedia から精度よく固有表現を
獲得し分類する手法を提案した．具体的には，Wikipedia の文書の DOM 構造が
持つ依存関係を，3 種類のクリーク (Sibling，Cousin，Relative) を定義すること
によってグラフ構造に反映させ，グラフを構成するそれらのクリークに対して依
存関係を考慮したポテンシャル関数を導入することで相互の影響をとらえた上で
全体に対する最適なラベル割り当てを求める Conditional Random Fields のモデ
ルを提案した．評価実験にて，汎化性能に優れ多くの分類問題に適用されている
Support Vector Machines に対する提案手法と比較して高い精度で固有表現の分
類が可能であることを示した．
今後の課題としては，付与する固有表現クラスの粒度の細分化が挙げられる．
分類した固有表現を質問応答や関係抽出などの応用に用いることを考えた場合，
固有表現クラスの粒度の細分化は非常に重要である．例えば，質問応答システム
への応用を考えた場合，固有表現が細分化されていることで回答候補を少数に絞
ることが可能となり，回答の精度向上が期待できる．しかし，一般的に付与する
ラベル集合が大きい場合，各ラベルごとの事例数は少なくなくなるため，統計的
手法による分類は難しくなる．その問題をどう解消するかは今後の課題である．
37
謝辞
主指導教官の松本裕治教授には，終始温かい御指導，御助言をいただきました．
深く感謝いたします．お忙しい中論文審査委員をお引き受けくださった副指導教
官の石井信教授に深く感謝いたします．本研究に関して，適切な御助言をくださ
いました乾健太郎助教授に深く感謝いたします．本研究を進めるにあたり直接の
御指導をいただき，数々の的確な御助言をくださいました浅原正幸助手に深謝い
たします．本研究を進めるにあたり，適切な御助言をくださいました新保仁助手
に深く感謝いたします．Wikipedia のアノテーションデータの作成にあたり，タ
グ付け作業をしてくださった樋口章子技術補佐員，山下華代技術補佐員に深く感
謝いたします．研究活動および大学生活を暖かく支えてくださいました大川基子
秘書に感謝いたします．最後になりましたが，研究に関して貴重なアドバイスを
くださった先輩方，研究生活を暖かく支えてくださった研究室の皆様に深く感謝
いたします．
38
参考文献
[1] Statistical Learning Theory. 1998.
[2] Document Object Model (DOM) Level 3 Core Specification.
cal report, 2002.
Techni-
http://www.w3.org/TR/2002/WD-DOM-Level-3-Core-
20020409.
[3] Stanley F. Chen and Ronald Rosenfeld. A gaussian prior for smoothing
maximum entropy models. Technical report, 1999.
[4] Aron Culotta and Andrew McCallum. Confidence estimation for information extraction. In In Proceedings of Human Language Technology Conference and North American Chapter of the Association for Computational
Linguistics (HLT-NAACL), 2004.
[5] Aron Culotta, Andrew McCallum, and Jonathan Betz. Integrating probabilistic extraction models and relational data mining to discover relations
and patterns in text. In HLT-NAACL, 2006.
[6] Lise Getoor, Eran Segal, Ben Taskar, and Daphne Koller. Probabilistic
models of text and link structure for hypertext classification. 2001.
[7] Ralph Grishman and Beth Sundheim. Message understanding conference 6: A brief history. In In Proceedings of COLING-96, 1996.
[8] Juanzi Li Jie Tang, Mingcai Hong and Bangyong Liang. Tree-structured
conditional random fields for semantic annotation. In Proceedings of 5th
International Conference of Semantic Web (ISWC-06), 2006.
[9] Jun’ichi Kazama and Jun’ichi Tsujii. Evaluation and extension of maximum
entropy models with inequality constraints. In In Proceedings of Empirical
Methods of Natural Language Processing, 2003.
39
[10] John Lafferty, Andrew McCallum, and Fernando Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data.
In Proceedings of the 18th International Conference on Machine Learning,
pp. 282–289. Morgan Kaufmann, San Francisco, CA, 2001.
[11] Dong C. Liu and Jorge Nocedal. The limited memory bfgs methods for large
scale optimization. In Mathematical Programming 45, 1989.
[12] Qing Lu and Lise Getoor. Link-based classification using labeled and unlabeled data. In Proceedings of the International Conference On Machine
Learning, Washington DC, August 2003.
[13] Qing Lu and Lise Getoor. Link-based text classification. In Proceedings of
the International Joint Conference on Artificial Intelligence, 2003.
[14] Andrew McCallum, Khashayar Rohanimanesh, and Charles Sutton. Dynamic conditional random fields for jointly labeling multiple sequences. In
NIPS Workshop on Syntax, Semantics, and Statistics, December 2003.
[15] Andrew McCallum and Ben Wellner. Toward conditional models of identity
uncertainty with application to proper noun coreference. In IJCAI Workshop
on Information Integration on the Web, 2003.
[16] Shinsuke Mori, Daisuke Takuma, and Gakuto Kurata. Using encyclopedic knowledge for named entity disambiguation. In In Proceedings of the
21st International Conference on Computational Linguistics and 44th Annual Meetings of the Association for Computational Linguistics, 2006.
[17] Fuchun Peng, Fangfang Feng, and Andrew McCallum. Chinese segmentation
and new word detection using conditional random fields. In In Proceedings
of The 20th International Conference on Computational Linguistics (COLING), 2004.
40
[18] David Pinto, Andrew McCallum, Xing Wei, and W. Bruce Croft. Table
extraction using conditional random fields. In Proceedings of the IEEE, 77,
257-286, 2003.
[19] Satoshi Sekine and Hitoshi Isahara. IREX: IR and IE evaluation project in
Japanese, 2000.
[20] Satoshi Sekine, Kiyoshi Sudo, and Chikashi Nobata. Extended named entity
hierarchy. 2002.
[21] Fei Sha and Fernando Pereira. Shallow parsing with conditional random
fields. In Proceedings of Human Language Technology Conference and North
American Chapter of the Association for Computational Linguistics (HLTNAACL), 2003.
[22] Charles
Sutton.
GRMM:
A
graphical
models
toolkit.
http://mallet.cs.umass.edu, 2006.
[23] Charles Sutton and Andrew McCallum. An introduction to conditional random fields for relational learning. In Lise Getoor and Ben Taskar, editors,
Introduction to Statistical Relational Learning. MIT Press, 2006. To appear.
[24] Charles Sutton, Khashayar Rohanimanesh, and Andrew McCallum. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. In Proceedings of the 21th International
Conference on Machine Learning, 2004.
[25] Ben Taskar, Pieter Abbeel, and Daphne Koller. Discriminative probabilistic models for relational data. In Proceedings of the 18th Conference on
Uncertainty in Artificial Intelligence. Morgan Kaufmann, 2002.
[26] Martin Wainwright, Tommi Jaakkola, and Alan Willsky. Tree-based reparameterization framework for analysis of belief propagation and related algorithms, 2003.
41
[27] Martin Wainwright, Tommi Jaakkola, and Alan Willsky. Tree consistency
and bounds on the performance of the max-product algorithm and its generalizations, 2004.
[28] Ben Wellner, Andrew McCallum, Fuchun Peng, and Michael Hay. An integrated, conditional model of information extraction and coreference with
application to citation matching. In Conference on Uncertainty in Artificial
Intelligence (UAI), 2004.
[29] 新里圭司, 鳥澤健太郎. Web からの単語クラスの簡単な作り方. 言語処理学
会第 11 回年次大会, 2005.
[30] 岡野原大輔, 工藤拓, 森信介. 形態素周辺確率を用いた確率的単語分割コーパ
スの構築とその応用. Technical report, 第 1 回 NLP 若手の会, 2006.
[31] 工藤拓. 形態素周辺確率を用いた分かち書きの一般化とその応用. 言語処理
学会全国大会 NLP-2005, 2005.
[32] 工藤拓, 山本薫, 松本裕治. Conditional random fields を用いた日本語形態素
解析. 情報処理学会自然言語処理研究会 SIGNL-161, 2004.
42
付録
A. 実験結果の詳細
CRFs (model 1)
NE CLASS
イベント名
人名
単位名
地名
施設名
称号名
組織名
職業名
自然物名
製品名
名前・その他
時間・数値表現
ALL
N
121
3315
15
1480
2449
42
991
303
1132
1664
24
2749
14285
Prec.
.8000
.6081
1.0000
.8181
.9196
.8000
.7627
.9496
.9463
.7609
.0000
.9935
.7856
C
Rec.
.1653
.9514
.1333
.6534
.7983
.0952
.6680
.8713
.2023
.7230
.0000
.9938
.7835
Prec.
.6897
.6258
1.0000
.7896
.9211
.8750
.7607
.9808
.9494
.7539
.0000
.9942
.7929
R
Rec.
.1653
.9228
.1333
.6365
.7918
.1667
.6609
.8416
.2155
.6905
.0000
.9931
.7702
Prec.
.8333
.6869
1.0000
.8140
.9026
.6000
.4745
.9564
.9576
SCR
Rec.
.1653
.9523
.0667
.6507
.8024
.0714
.6771
.8680
.1996
F
.2740
.7419
.2353
.7265
.8546
.1702
.7122
.9088
.3333
.7414
.0000
.9936
.7846
Prec.
.7083
.6091
1.0000
.8179
.9179
.6667
.7649
.9493
.9368
.7761
.0000
.9945
.7876
CR
Rec.
.1405
.9520
.0667
.6493
.7987
.0476
.6731
.8647
.2094
.7332
.0000
.9942
.7849
F
.2345
.7429
.1250
.7239
.8541
.0889
.7160
.9050
.3422
.7540
.0000
.9944
.7862
Prec.
.6552
.6250
1.0000
.7689
.9269
.8750
.7589
.9846
.9639
.7513
.0000
.9942
.7912
I
Rec.
.1570
.9231
.1333
.6405
.7918
.1667
.6670
.8416
.2120
.6845
.0000
.9938
.7702
F
.2533
.7453
.2353
.6989
.8540
.2800
.7100
.9075
.3476
.7164
.0000
.9940
.7806
Prec.
.8000
.6238
1.0000
.8062
.9078
.8333
.7267
.9532
.9615
.7538
.0000
.9931
.7875
SC
Rec.
.1653
.9508
.0667
.6520
.8044
.1190
.6680
.8746
.1988
.7212
.0000
.9931
.7837
F
.2740
.7533
.1250
.7210
.8530
.2083
.6961
.9122
.3294
.7371
.0000
.9931
.7856
CRFs (model 1)
NE CLASS
イベント名
人名
単位名
地名
施設名
称号名
組織名
職業名
自然物名
製品名
名前・その他
時間・数値表現
ALL
N
121
3315
15
1480
2449
42
991
303
1132
1664
24
2749
14285
F
.2667
.7458
.2353
.7048
.8516
.2800
.7073
.9059
.3513
.7208
.0000
.9936
.7814
Prec.
.7241
.6340
1.0000
.7683
.9180
.9000
.7426
.9439
.9647
.7370
.0000
.9942
.7910
S
Rec.
.1736
.9201
.1333
.6385
.7913
.2143
.6842
.8878
.2173
.6905
.0000
.9935
.7727
F
.2800
.7507
.2353
.6974
.8500
.3462
.7122
.9150
.3547
.7130
.0000
.9938
.7817
CRFs (model 1)
NE CLASS
イベント名
人名
単位名
地名
施設名
称号名
組織名
職業名
自然物名
N
121
3315
15
1480
2449
42
991
303
1132
F
.2759
.7981
.1250
.7232
.8495
.1277
.5580
.9100
.3304
43
Prec.
.6897
.6347
1.0000
.7807
.9131
.9000
.7362
.9443
.9578
CRFs (model 2)
SR
Rec.
.1653
.9210
.1333
.6399
.7942
.2143
.6872
.8944
.2005
F
.2667
.7515
.2353
.7033
.8495
.3462
.7109
.9186
.3316
Prec.
.6429
.6070
1.0000
.7922
.9185
1.0000
.7792
.9491
.9583
C
Rec.
.1488
.9538
.0667
.6439
.8011
.0238
.6731
.8614
.1829
F
.2416
.7419
.1250
.7104
.8558
.0465
.7223
.9031
.3071
製品名
名前・その他
時間・数値表現
ALL
1664
24
2749
14285
.7650
.0000
.9938
.7871
.7200
.0000
.9927
.7838
Prec.
.6207
.6065
1.0000
.7937
.9186
1.0000
.7489
.9458
.9612
.7734
.0000
.9916
.7822
CR
Rec.
.1488
.9523
.0667
.6446
.7971
.0476
.6741
.8647
.1749
.6995
.0000
.9924
.7773
Prec.
.7241
.6315
1.0000
.7683
.9182
.9000
.7418
.9439
.9647
.7375
.0000
.9942
.7898
S
Rec.
.1736
.9198
.1333
.6385
.7840
.2143
.6842
.8878
.2173
.6905
.0000
.9935
.7714
.7418
.0000
.9933
.7854
.7444
.0000
.9949
.7919
.6947
.0000
.9931
.7729
.7187
.0000
.9940
.7823
.7732
.0000
.9906
.7842
.7007
.0000
.9924
.7789
.7352
.0000
.9915
.7815
Prec.
.6897
.6277
1.0000
.7823
.9225
.8750
.7621
.9846
.9494
.7503
.0000
.9942
.7931
R
Rec.
.1653
.9216
.1333
.6385
.7918
.1667
.6660
.8449
.2155
.6935
.0000
.9935
.7709
F
.2667
.7468
.2353
.7031
.8521
.2800
.7108
.9094
.3513
.7208
.0000
.9938
.7819
Prec.
.6176
.6312
1.0000
.7786
.9126
.5000
.6793
.9476
.9563
.7121
.0000
.9891
.7791
SCR
Rec.
.1736
.9439
.0667
.6297
.7975
.0476
.6670
.8350
.1935
.7194
.0000
.9924
.7768
F
.2710
.7565
.1250
.6963
.8512
.0870
.6731
.8877
.3218
.7157
.0000
.9907
.7779
P
Rec.
.2314
.9285
.2000
.6493
.7975
.1667
.6963
.8680
.2005
.7025
.0000
F
.3500
.7386
.3158
.7132
.8560
.2642
.7180
.9069
.3326
.7135
.0000
CRFs (model 2)
NE CLASS
イベント名
人名
単位名
地名
施設名
称号名
組織名
職業名
自然物名
製品名
名前・その他
時間・数値表現
ALL
N
121
3315
15
1480
2449
42
991
303
1132
1664
24
2749
14285
F
.2400
.7411
.1250
.7114
.8535
.0909
.7095
.9034
.2960
.7346
.0000
.9920
.7797
Prec.
.6552
.6250
1.0000
.7689
.9269
.8750
.7589
.9846
.9639
.7513
.0000
.9942
.7912
I
Rec.
.1570
.9231
.1333
.6405
.7918
.1667
.6670
.8416
.2120
.6845
.0000
.9938
.7702
F
.2533
.7453
.2353
.6989
.8540
.2800
.7100
.9075
.3476
.7164
.0000
.9940
.7806
CRFs (model 2)
NE CLASS
イベント名
人名
単位名
地名
施設名
称号名
組織名
職業名
自然物名
製品名
名前・その他
時間・数値表現
ALL
N
121
3315
15
1480
2449
42
991
303
1132
1664
24
2749
14285
F
.2800
.7489
.2353
.6974
.8458
.3462
.7118
.9150
.3547
.7132
.0000
.9938
.7805
Prec.
.6061
.6161
1.0000
.7796
.9185
.6667
.7528
.9455
.9674
.7314
.0000
.9898
.7811
SC
Rec.
.1653
.9448
.0667
.6405
.7958
.0476
.6700
.8581
.1837
.7019
.0000
.9920
.7756
Prec.
.7297
.6152
1.0000
.7625
.9218
.5833
.7241
.9464
.9734
.7415
.2000
I
Rec.
.2231
.9231
.2000
.6507
.7893
.1667
.7043
.8746
.2261
.6911
.0417
CRFs (model 2)
NE CLASS
イベント名
人名
単位名
地名
施設名
称号名
組織名
職業名
自然物名
製品名
名前・その他
N
121
3315
15
1480
2449
42
991
303
1132
1664
24
Prec.
.6667
.6344
1.0000
.7772
.9154
.9000
.7322
.9443
.9620
.7494
.0000
SR
Rec.
.1653
.9204
.1333
.6365
.7913
.2143
.6842
.8944
.2014
.6935
.0000
F
.2597
.7458
.1250
.7033
.8528
.0889
.7090
.8997
.3088
.7163
.0000
.9909
.7783
SVM
F
.2649
.7511
.2353
.6999
.8489
.3462
.7074
.9186
.3331
.7203
.0000
44
F
.3418
.7383
.3333
.7022
.8504
.2593
.7141
.9091
.3670
.7154
.0690
Prec.
.7179
.6131
.7500
.7909
.9238
.6364
.7411
.9495
.9742
.7247
.0000
時間・数値表現
ALL
2749
14285
.9949
.7921
.9931
.7716
.9940
.7817
.9920
.7812
.9945
.7768
.9933
.7790
.9924
.7817
.9945
.7779
B. 関根の拡張固有表現階層 クラス一覧
ノード名
TOP
# TOP
名前
名前＿その他
# NAME
# NAME OTHER
人名
組織名
組織名＿その他
企業名
企業グループ名
軍隊名
協会名
政府組織名
政党名
競技グループ名
国際組織名
民族名
国籍名
#
#
#
#
#
#
#
#
#
#
#
#
#
PERSON
ORGANIZATION
ORGANIZATION OTHER
COMPANY
COMPANY GROUP
MILITARY
INSTITUTE
GOVERNMENT
POLITICAL PARTY
GAME GROUP
INTERNATIONAL ORGANIZATION
ETHNIC GROUP
NATIONALITY
地名
地名＿その他
GPE
GPE ＿その他
市区町村名
郡名
都道府県名
国名
大陸地域名
国内地域名
地形名
地形名＿その他
陸上地形名
河川湖沼名
海洋名
天体名
天体名＿その他
恒星名
惑星名
アドレス
アドレス＿その他
郵便住所
電話番号
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
LOCATION
LOCATION OTHER
GPE
GPE OTHER
CITY
COUNTY
PROVINCE
COUNTRY
CONTINENTAL REGION
DOMESTIC REGION
GEOLOGICAL REGION
GEOLOGICAL REGION OTHER
LANDFORM
WATER FORM
SEA
ASTRAL BODY
ASTRAL BODY OTHER
STAR
PLANET
ADDRESS
ADDRESS OTHER
POSTAL ADDRESS
PHONE NUMBER
45
.9935
.7798
電子メイル
URL
# EMAIL
# URL
施設名
施設名＿その他
GOE
GOE ＿その他
学校名
公共機関名
取引所名
美術博物館名
遊園施設名
神社寺名
駅名
駅名＿その他
空港名
電車駅名
港名
停車場名
路線名
路線名＿その他
電車路線名
道路名
航路名
トンネル名
橋名
公園名
スポーツ施設名
記念碑名
施設部分名
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
FACILITY
FACILITY OTHER
GOE
GOE OTHER
SCHOOL
PUBLIC INSTITUTION
MARKET
MUSEUM
AMUSEMENT PARK
WORSHIP PLACE
STATION TOP
STATION TOP OTHER
AIRPORT
STATION
PORT
CAR STOP
LINE
LINE OTHER
RAILROAD
ROAD
WATERWAY
TUNNEL
BRIDGE
PARK
SPORTS FACILITY
MONUMENT
FACILITY PART
製品名
製品名＿その他
乗り物名
乗り物名＿その他
車名
列車名
飛行機名
宇宙船名
船名
食べ物名
衣服名
医薬品名
武器名
株名
賞名
理論名
規則名
便名
キャラクター名
方式制度名
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
PRODUCT
PRODUCT OTHER
VEHICLE
VEHICLE OTHER
CAR
TRAINN
AIRCRAFT
SPACESHIP
SHIP
FOOD
CLOTHES
DRUG
WEAPON
STOCK
AWARD
THEORY
RULE
SERVICE
CHARACTER
METHOD SYSTEM
46
主義思想名
文化名
宗教名
言語名
政策計画名
学問
等級
競技名
罪名
芸術
芸術名＿その他
絵画名
番組名
映画名
公演名
音楽名
文学名
出版物名
出版物名＿その他
新聞名
雑誌名
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
DOCTRINE
CULTURE
REGION
LANGUAGE
PLAN
ACADEMIC
CLASS
SPORTS
OFFENCE
ART
ART OTHER
PICTURE
BROADCAST PROGRAM
MOVIE
SHOW
MUSIC
BOOK
PRINTING
PRINTING OTHER
NEWSPAPER
MAGAZINE
イベント名
イベント名＿その他
催し物名
催し物名＿その他
大会名
会議名
自然現象名
自然災害名
戦争名
事故事件名
#
#
#
#
#
#
#
#
#
#
EVENT
EVENT OTHER
OCCASION
OCCASION OTHER
GAMES
CONFERENCE
NATURAL PHENOMENA
NATURAL DISASTER
WAR
INCIDENT
自然物名
自然物名＿その他
生物名
生物名＿その他
動物名
動物名＿その他
無脊椎動物
無脊椎動物＿その他
昆虫類
脊椎動物
脊椎動物＿その他
魚類
爬虫類
両生類
鳥類
哺乳類
植物名
動物部位名
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
NATURAL OBJECT
NATURAL OBJECT OTHER
LIVING THING
LIVING THING OTHER
ANIMAL
ANIMAL OTHER
INVERTEBRATE
INVERTEBRATE OTHER
INSECT
VERTEBRATE
PVERTEBRATE OTHER
FISH
REPTILE
AMPHIBIA
BIRD
MAMMAL
FLORA
BODY PARTS
47
植物部位名
物質名
# FLORA PARTS
# MINERAL
称号名
称号名＿その他
地位名
# TITLE
# TITLE OTHER
# POSITION TITLE
単位名
単位名＿その他
通貨名
# UNIT
# UNIT OTHER
# CURRENCY
職業名
# VOCATION
病気名
# DISEASE
神名
# GOD
識別番号名
# ID NUMBER
色名
# COLOR
時間表現
時間表現＿その他
時間
時間＿その他
時刻表現
日付表現
曜日表現
時代表現
#
#
#
#
#
#
#
#
TIME TOP
TIME TOP OTHER
TIMEX
TIMEX OTHER
TIME
DATE
DAY OF WEEK
ERA
期間
期間＿その他
時刻期間
日数期間
週期間
月期間
年期間
#
#
#
#
#
#
#
PERIODX
PERIODX OTHER
TIME PERIOD
DATE PERIOD
WEEK PERIOD
MONTH PERIOD
YEAR PERIOD
数値表現
数値表現＿その他
金額表現
株指標
ポイント
割合表現
倍数表現
頻度表現
順位表現
年齢
学齢
緯度経度
#
#
#
#
#
#
#
#
#
#
#
#
NUMEX
NUMEX OTHER
MONEY
STOCK INDEX
POINT
PERCENT
NULTIPLICATION
FREQUENCY
RANK
AGE
SCHOOL AGE
LATITUDE LONGITUDE
48
寸法表現
寸法表現＿その他
長さ
面積
体積
重量
速度
密度
温度
カロリー
震度
マグニチュード
#
#
#
#
#
#
#
#
#
#
#
#
MEASUREMENT
MEASUREMENT OTHER
PHYSICAL EXTENT
SPACE
VOLUME
WEIGHT
SPEED
INTENSITY
TEMPERATURE
CALORIE
SEISMIC INTENSITY
SEISMIC MAGNITUDE
個数
個数＿その他
人数
組織数
場所数
場所数＿その他
国数
施設数
製品数
イベント数
動物数
植物数
物質数
#
#
#
#
#
#
#
#
#
#
#
#
#
COUNTX
COUNTX OTHER
N PERSON
N ORGANIZATION
N LOCATION
N LOCATION OTHER
N COUNTRY
N FACILITY
N PRODUCT
N EVENT
N ANIMAL
N FLORA
N MINERAL
序数
# ORDINAL NUMBER
表 9: 拡張固有表現階層クラス一覧
49