
\documentstyle[epsf,jnlpbbl]{jnlp_j}

\setcounter{page}{45}
\setcounter{巻数}{9}
\setcounter{号数}{2}
\setcounter{年}{2002}
\setcounter{月}{4}
\受付{2001}{7}{13}
\再受付{2001}{11}{6}
\採録{2002}{1}{10}

\setcounter{secnumdepth}{2}


\newtheorem{th}{}[]
\newtheorem{cor}[]{}
\newtheorem{prop}[]{}
\newtheorem{df}[]{}
\newtheorem{lemma}[]{}
\newtheorem{ex}[]{}
\newtheorem{prob}{}


\title{コーパス中の一対多関係を推定する問題における類似尺度}
\author{山本 英子\affiref{TUT} \and 梅村 恭司\affiref{TUT}}
\headauthor{山本 英子, 梅村 恭司}
\headtitle{コーパス中の一対多関係を推定する問題における類似尺度}
\affilabel{TUT}{豊橋技術科学大学 情報工学系}
{Dept. of Information and Computer Sciences, 
Toyohashi University of Technology}
\jabstract{
{
本論文では, コーパスから事象間の一対多関係を推定する問題を考える. 
これまでにコーパスから事象間の関係を推定することが
多く研究されている. 一般に, この問題に対する解決法
の多くは, コーパスを構成する文書における事象の共起に基づき, 
暗黙的に事象間の関係は一対一関係であることを想定している. 
しかし, 実際には, 事象間の関係は一対多関係である場合があり, この特徴のためにいくつか
の工夫が必要である. 
本論文では, コーパス中の一対多関係を推定するために補完類似度を利用することを提案する. 
この尺度は本来文字認識システムのために開発され, テンプレートの文字の
パターンにオーバーラップしたパターンがある条件で有効であることが知られてい
るが, これまでテキスト処理に利用されたことはなかった. 
この補完類似度の一対多関係を推定する能力を評価するために, 地名(都道府県市郡名
)を対象事象とした実験において, 
平均相互情報量, 自己相互情報量, 非対称平均相互情報量, $\phi$相関係数, 
コサイン関数, ダイス相関係数, 信頼度との性能比較を行う. 
実験では, 三種類のコーパスを用いる. 一つ目は実際に地名間にある一対多関係か
ら合成する人工的なデータ集合である. 二つ目も実際の関係から合成するが, 
誤った関係を導く少量の要素も含むデータ集合である. 
三つ目は現実の新聞記事コーパスから得られるデータ集合である. 
これらの評価実験において, 補完類似度がもっとも優れており, 
補完類似度は一対多関係の推定問題に対して有効であることを示す. 
}
}
\jkeywords{一対多関係, 補完類似度, 出現パターン, 包含関係}
\etitle{A Similarity Measure for Estimation of\\ 
One-to-Many Relationship in Corpus}
\eauthor{Eiko Yamamoto\affiref{TUT} \and Kyoji Umemura\affiref{TUT}}
\eabstract{
{
In this paper, we consider the estimation of the one-to-many relationship
between entities in corpus. 
Many works have been done to estimate the relationship between entities
from corpus. 
Generally speaking, the most common method is based on the co-ocurrence
of entities in a document of corpus, and this method implicitly assumes
that the relationship is one-to-one mapping. 
The real relationship may sometimes be one-to-many relationship, and
need some consideration for this property. 
We propose to use CSM(Complementary Similarity Measure) to
detect this relationship.
This measure is originally developed for character recognition system,
and is known to work well for overlapped patterns with template pattern, 
but is rarely used for text processing. 
We have compared CSM with other similarity measures, including three kinds
of mutual information, $\phi$ coefficient, cosine, 
dice coefficient, and confidence. 
We choose the names of prefectures and cities as the entities, which has
real one-to-many relationship. 
For the evaluation, we have used three kinds of corpora. 
The first one is a synthesized from real relations. 
The second one is also synthesized from relations but it contains
an element of false relation. 
The third one is compiled from actual newspaper corpus. 
We have found that CSM is the best similarity measure for this
experiment and works well for one-to-many relationship.
}
}
\ekeywords{one-to-many relationship, 
complementary similarity measure, 
appearance pattern, inclusion relation}
\def\argmax{}

\setcounter{topnumber}{2}
\def\topfraction{}
\setcounter{bottomnumber}{1}
\def\bottomfraction{}
\setcounter{totalnumber}{3}
\def\texfraction{}
\def\floaatpagefraction{}

\begin{document}
\thispagestyle{plain}

\maketitle


\section{はじめに}
本論文では, コーパスから事象間の関係を抽出する問題において, 事象間の一対多
関係を推定する問題を取り上げた. 
コーパスから事象間の関係を推定する場合, それらの事象は共起出現することに基
づく推定を行うことが多い. 
しかし, そこで用いられている手法は暗黙のうちに, 推定する関係が一対一関係であると想定し
ているものがほとんどである. 
しかし抽出すべき事象間の関係は一対一関係であるとは限らず, あらかじめ関係が一対多関係である
ことがわかっている場合もある. このような場合, これまでの一対一関係を前提とした手法が
有効であるかどうかは明らかではない. 
一方, データベースにおいて連想規則を抽出する問題において, その規則が表す
事象間の関係が一対多関係であることを考慮した手法が用いられている\cite{Agrawal96}. 
しかし, この手法がコーパスから事象間の関係を推定する問題に効果的であるかどうかは明らかではない. 

ここで, 事象間の関係が一対多関係である場合, それらの事象が持つ出現パターン間の関係
は一致ではなく, 包含関係であることが観測される. 
そこで, 本論文では, 出現パターンの包含関係に強いとされる類似尺度を探し, 
この条件にあてはまる類似尺度として, 文字認識の分野で提案されている補完類似度
\cite{Hagita95}に着目した. 
そして, この類似尺度をコーパスから事象間の一対多関係を抽出する問題に適用し, 
その有効性を評価する. 
さらに, 評価実験を通して, 
これまでにコーパスから事象間の関係を推定するこ
とに用いられている類似度やデータベースにおいて連想規則を発見することに用いら
れる尺度と, 補完類似度との間で性能の比較を行う. 
これまでに用いられている類似尺度として, 平均相互情報量, 自己相互情報量, 
$\phi$相関係数, コサイン関数, ダイス相関係数を選んだ. これらは関係の抽出に
用いられる代表的な類似尺度である. 
また, 一対多関係を推定する問題において, 非対称性を持つ尺度と対称性を持つ尺度との性能差を測るために, 平均相互情報量を改良し, 非対称性を持たせた非対称平均相互情報量を定義し, 比較対象とする尺度に加えた. 

実験対象となる事象としては地名(都道府県市郡名)を選んだ. 地名は実世界において
一対多関係を持つ事象である. 
実験は, 人工的に生成したデータ集合と実データに対して行った. 
人工的に生成したデータ集合は実在する地名の一対多関係か
ら擬似的に関係を取り出し, それをデータとして生成したデータ集合である. 
このデータ集合において, 現存する一対多関係を再現する能力を測定した. 
実データを用いた実験では, 実際の新聞記事における地名の出現パターンから現存する一対多関係
を推定する能力を測定した. 
これらの実験の結果において, 
補完類似度はこれまでのコーパスからの関係抽出に用いられてきた
類似尺度よりも優れ, 
連想規則の抽出に用いられる類似尺度よりもよい特性を示した. 

この論文は以下のような構成になっている. まず2節に, 一対多関係を推定
する問題を定義するために必要な要素を定義する. 次に3節では, 
評価対象とする類似尺度の概要と, 補完類似度, これと比較対象となる尺度, 
平均相互情報量, 自己相互情報量, 非対称平均相互情報量, $\phi$相関係数, コサイン関数, ダイス相関係数, 信頼度を示す. 
4節では, 実験の概要と, モデルに従って生成された人工的なデータにお
ける実験, 実データを用いた実験を示す. 
5節で考察し, 6節で関連研究を示す. 最後に7節でまとめる. 

\section{問題定義}
この節では, 本論文で扱う問題についての定義を示す. 
扱う事象は事柄を表す名前（ラベル）とする. 
ここでは, ラベル間には隠れた関係があり, ラベルの集合から
その関係を推定するという問題を定義する. 
\begin{df} ラベルの定義

ラベル$l$は関係を定める対象であり, あるラベルと他のラベルが同一であるか
ないかを判定できる事柄を表す名前である. 
本論文では, ラベルの集合を$L$と表す. 
\begin{eqnarray*}
L&=&\{l|lはラベル\}
\end{eqnarray*}
\end{df}
\begin{ex} ラベル集合$L$の例
\begin{eqnarray*}
L_{example} &=& \{ 北海道, 沖縄県, 札幌市, 那覇市, 釧路市, 東京都\} 
\end{eqnarray*}
\end{ex}
\begin{df} 一対多関係の定義

一対多関係$\langle x,y\rangle$はラベル間で定義される関係である. 
一対多関係においては, 次の二つの式が成り立つ. 
\begin{eqnarray*}
&& {}^{\forall} a \in L ; {}^{\forall} b \in L; {}^{\forall} c \in L; 
\langle a,c \rangle \wedge \langle b,c\rangle \rightarrow a=b\\
&& {}^{\exists} a \in L ; {}^{\exists} b \in L ; {}^{\exists} c \in L; 
\langle a,b\rangle \wedge \langle a,c\rangle \wedge b\neq c
\end{eqnarray*}
最初の定義は, 関係の右のラベルが等しい場合には関係の左のラベルも等し
いことを意味している. 
二番目の定義は, この関係には一対一ではないラベルが存在するということを意味している. 
これらの定義が成立する式の集合を$R$と定義し, 関係集合と呼ぶことにする. 
\begin{eqnarray*}
R&=&\{\langle l_c,l_p \rangle|l_c,l_p\in L\}\\
\end{eqnarray*}
\end{df}
\begin{ex} 関係集合$R$の例
\begin{eqnarray*}
R_{example} &=& \{ \langle 北海道, 札幌市\rangle, \langle 北海道, 釧路市\rangle, \langle 沖縄県, 那覇市\rangle \}
\end{eqnarray*}
\end{ex}
\begin{df} 雑音のないデータ集合の定義

ラベル集合$L$があり, 関係集合$R$があるとする. 
このとき, ラベル集合の部分集合$d$があり, この$d$で構成される集合が観測でき
るデータ集合$D$であると考える. ここで, $2^L$はLのべき集合を表す. 
このとき, 観測できるデータ集合$D$は次のように定義できる. 
\begin{eqnarray*}
D&=&\{d|d\in 2^L\wedge {}^{\forall} l\in d;
{}^{\exists} \langle l_c,l_p\rangle\in R;
((l=l_c\wedge l_p\in d)\vee (l=l_p\wedge l_c\in d))\}
\end{eqnarray*}
この式は, 観測できるそれぞれの$d$にあるラベルはある関係集合の要素から
対で取り出されたラベルで, 必ず関係の相手であるラベルも$d$にあるということ
を意味している. 
\label{no-noise}
\end{df}
\begin{ex} 雑音のないデータ集合の例
\begin{eqnarray*}
L_{example} &=& \{ 北海道, 沖縄県, 札幌市, 那覇市, 釧路市, 東京都\} \\
R_{example} &=& \{ \langle 北海道, 札幌市\rangle, \langle 北海道, 釧路市\rangle, \langle 沖縄県, 那覇市\rangle \} \\
&& のとき, \\
D_{example} &=& \{\{沖縄県, 那覇市\}, \{北海道, 札幌市, 釧路市\}, \\
&& ~\{北海道, 札幌市, 沖縄県, 那覇市\} \}
\end{eqnarray*}
\end{ex}
\begin{df} 出現パターンの包含関係の定義

ここで, ラベルを引数とする関数$\tilde{D}$を定義する.
この関数は与えられたラベルを含むデータ集合$D$の要素$d$を返す関数である.
\begin{eqnarray*}
 \tilde{D}(l)&=&\{d|l\in d\} 
\end{eqnarray*}
この関数を使うと, 
あるラベル$l_c$の出現パターンが他のラベル$l_p$の出現パターンを包含することを
次のように定義できる. 
\begin{eqnarray*}
\tilde{D}(l_p) \subseteq \tilde{D}(l_c)
\end{eqnarray*}
\end{df}
また, 関係集合$R$において, 左のラベル$l_c$の集合を$L_c$, 右のラベル$l_p$の集
合を$L_p$としたとき, 関係が一対多関係であるならば, 次の式が成り立つ. 
\begin{eqnarray*}
&& L_c \cap L_p = \phi ならば, 
{}^{\forall} \langle l_c,l_p\rangle\in R;\tilde{D}(l_p) \subseteq 
\tilde{D}(l_c)
\end{eqnarray*}
言い換えると, この状況において関係集合が一対多関係であることは, 
すべての関係について, 左のラベル$l_c$の出現パターンは
右のラベル$l_p$の出現パターンを包含するという関係になるということである. 
\begin{df} 雑音のないデータ集合から関係を推定する問題

雑音のない集合から関係集合を推定する問題は, 
ラベル集合$L$と観測できるデータ集合$D$から関係集合$R$を求めることで
ある. 
ここで, 求められた集合を$\hat{R}$と記述することにする. 
$\hat{R}$を得たとしても, その要素である関係が実際に成り立っているかを
簡単には決定できないため, 
この問題を厳密に解くことは難しい. 
実際には, $\hat{R}$にあるラベル間の関係
$\langle l_c, l_p \rangle$が真実の関係集合$R$に
含まれるかどうかを判定することによって推定を行う. 
そして, $\hat{R}$の要素が$R$の要素である確率が
高いほどよい推定と考える. 
\end{df}
\begin{df} 雑音のあるデータ集合の定義\label{with-noise}

実世界のデータベースの多くは「雑音のあるデータ集合」である. 
雑音$d_N$のあるデータ集合$D^*$は, 雑音のないデータ集合$D$を構成する
各集合$d$に, $d$に含まれているどのラベルとの間においても, 
関係集合$R$にある関係が成り立たない
ラベルを追加した集合$d^*$の集合と考える. 
すなわち, 雑音$d_N$は, $d$に含まれるどのラベルとの間にも正解集合$R$にある
関係が成り立たないラベル$l_N$を持つ集合である.
ここで, $2^L$は$L$のべき集合を表す. このとき, 観測できる
データ集合$D^*$は次のように定義できる. 
\begin{eqnarray*}
 D^*&=&\{d^*|{}^{\exists} d_N\in 2^L; {}^\exists d \in D;
{}^\forall l_N\in d_N; {}^\forall l\in d; \\
&& 
\,\,\,\,
\langle l_N,l\rangle\not\in R \wedge \langle l,l_N\rangle\not\in R \wedge 
d^* = d \cup d_N \wedge |d|\gg |d_N |\}
\end{eqnarray*} 
\end{df}
\begin{ex} 雑音のあるデータ集合の例
\begin{eqnarray*}
L_{example} &=& \{ 北海道, 沖縄県, 札幌市, 那覇市, 釧路市, 東京都\}, \\
R_{example} &=& \{\langle 北海道, 札幌市\rangle, \langle 北海道, 釧路市\rangle, \langle 沖縄県, 那覇市\rangle \}, \\
D_{example} &=& \{\{沖縄県, 那覇市\}, \{北海道, 札幌市, 釧路市\}, \\ 
&& ~\{北海道, 札幌市, 沖縄県, 那覇市\} \} \\
のとき, &&\\
D^*_{example} &=& \{\{沖縄県, 那覇市, 札幌市\}, \\
&& ~\{北海道, 札幌市, 釧路市, 東京都, 那覇市\}, \\
&& ~\{北海道, 札幌市, 沖縄県, 那覇市, 東京都\} \}
\end{eqnarray*}
\end{ex}
\begin{df} 雑音のあるデータ集合から関係を推定する問題

雑音のある集合から関係を推定する問題は, ラベル集合$L$と雑音のあるデータ集
合$D^*$から$R$を求めることである.
対象とするデータ集合に雑音があるため, 関係の推定は難しくなっている. 
この問題についても, 求められた関係集合の要素が関係集合$R$
の要素である確率で評価を行う. 
\end{df}
\vspace{2zw}
\begin{df} 多重度の定義 

ここで, データ集合が持つ関係の特性を表すため, 多重度を定義する. 
多重度はデータ集合から得られた正解である関係
$\langle l_c,l_p\rangle$に関して, 
一つのラベル$l_c$は平均的にいくつのラベル$l_p$
と関係を持つかを表す一対多の比率である. 

与えられたデータ集合を$D$とする. 
$D$から求められる関係集合$R^+$を以下のように定義する. 
\begin{eqnarray*}
R^+ &=& \{\langle l_c,l_p\rangle |
{}^\exists d\in D;l_c\in d \wedge l_p\in d \wedge 
\langle l_c,l_p\rangle\in R \} 
\end{eqnarray*}
同様に, $D$から求められる$L_c$を以下のように定義する. 
\begin{eqnarray*}
L_c^+ &=& \{ l_c | {}^\exists d\in D;{}^\exists l_p\in d;
\langle l_c,l_p\rangle\in R\}
\end{eqnarray*}
このとき, $D$が持つ多重度$M$は次のように定義できる. 
\begin{eqnarray*} 
M(D) &=& \frac{|R^+|}{|L_c^+|} 
\end{eqnarray*} 
\label{multi}
\end{df}
\begin{ex} 多重度の例
\begin{eqnarray*}
D^*_{example} &=& \{\{沖縄県, 那覇市, 札幌市\}, \\
&& ~\{北海道, 札幌市, 釧路市, 東京都, 那覇市\}, \\
&& ~\{北海道, 札幌市, 沖縄県, 那覇市, 東京都\} \} \\
のとき, && \\
M(D^*_{example}) &=& 
\frac{|\{\langle 沖縄県,那覇市\rangle, \langle 北海道,札幌市\rangle, \langle 北海道,釧路市\rangle\} |}{|\{北海道, 沖縄県\}|} \\
&=& 1.5
\end{eqnarray*}
\end{ex}
通常, これらの関係を推定する際には, 一対多関係にある$l_c,l_p$の間の何らか
の形をした類似尺度を用いる.
既存の多くの方法では, 
類似尺度が$l_p$と$l_c$に対して対称であることが多い. 
これは,これらの方法が$\tilde{D}(l_p) \simeq \tilde{D}(l_c)$であることを
暗黙のうちに仮定していると解釈することができる. 
これに対して, 本論文では, 実際に$\tilde{D}(l_p) \subseteq \tilde{D}(l_c)$
となる問題における一対多関係の推定に注目した. 

\section{評価対象となる類似尺度}
本論文では, さまざまな類似尺度について一対多関係を推定する問題における性能を
比較する. 
比較においては, 類似尺度が利用する情報を基本的な情報にそろえ, 
利用する情報に影響を受けないようにし, 
公正な比較となるようにしたい. 
そこで, 本論文で扱う類似尺度は下記に示すパラメー
タ$a,b,c,d$で利用できる情報をもとに計算できる類似尺度とした. 
実際に使用されている類似尺度の多くはこの$a,b,c,d$から計算される. 
次にこれらのパラメータの定義を示す. 
このパラメータによって, 本論文で扱う類似尺度は表現される. 
\newpage
\begin{df} パラメータ\label{para}

ラベル$lab_1,lab_2$に対する二値パターンをそれぞれ二値n次元のベクトル
$\vec{F}=(f_1,f_2,$ $...,f_i,...,f_n)(f_i=0または1), $
$\vec{T}=(t_1,t_2,...,t_i,...,t_n)(t_i=0または1)$とする. 
このとき, $\vec{F}$が$\vec{T}$にどれだけ類似しているかを以下のパラメー
タを用いて推定する. 
ただし, $n=a+b+c+d$である. 
\begin{eqnarray}
a &=& \sum_{i=1}^nf_i t_i\label{csm_a} \\
b &=& \sum_{i=1}^nf_i (1-t_i)\label{csm_b} \\
c &=& \sum_{i=1}^n(1-f_i) t_i\label{csm_c} \\
d &=&\sum_{i=1}^n(1-f_i) (1-t_i)\label{csm_d}
\end{eqnarray}
\end{df}
それぞれのパラメータは, 
\begin{itemize}
\item a: 二つのラベルが同時に現れるデータの数, 
\item b: $lab_1$が現れ, $lab_2$は現れないデータの数,  
\item c: $lab_2$が現れ, $lab_1$は現れないデータの数, 
\item d: 二つのラベルがどちらとも現れないデータの数
\end{itemize}
を表す. 
これらのパラメータを情報としてとらえると, $a,d$は二つの出現パターンがどれ
だけ一致しているかを見るための情報となり, $b,c$は二つの出現パターンがどれだけ一
致しないかを見るための情報となる. 実験では, これらの情報から出現パターン間
の類似度を計算し, その類似度が高ければ, 二つの出現パターンは包含関係ではな
いかと推定する. 
このとき用いる類似尺度は, $\langle lab_1,lab_2\rangle$が
関係集合$R$の要素である場合, 高いスコアを与える関数であるとする. 
また, 対称性を持つ類似尺度の場合, 包含するラベルであるかそれとも包含さ
れるラベルであるかを判断することができないため, 
本論文では, 対称性を持つ類似尺度の場合は, 
出現回数の多いラベルを包含するラベルとして出現パターンの包含関係を推定した. 

本論文では, 一対多関係を推定する問題において,
文字認識の分野で提案されている補完類似度に注目し, これと
これまでに提案されている類似尺度の性能を比較する. 
 
\subsection{補完類似度}
この節では, 補完類似度\cite{Hagita95,Sawaki95a,Sawaki95b}について
説明する. 本来, 補完類
似度は文字認識の分野のもので, 劣化印刷文字を高い精度で認識できるように考案
された類似度である. 劣化印刷文字とは, かすれていたり汚れている文字のこと
である. 補完類似度を用いた文字認識方法を補完類似度法といい, これは文字を二
値画像特徴として扱い, 補完類似度を用いて, そのパターンとテンプレートとする
文字のパターンとの類似度を計算し, 文字を認識する方法である. この手法は, 汚れ
た文字においては人間による文字認識と同等の精度を持ち, かすれた文字において
は人間による文字認識よりも高い精度を持つ\cite{Sawaki95a}. 
この結果は, 補完類似度が劣化印刷文字のパターンがテンプレート文字のパターン
に包含される形にあるのであれば, 文字であると認識できるように, 
高い類似度を保持する特徴を持つためである. 

本論文で扱う出現パターンは頻度情報を考慮しない二値パターンであるため, 仮にこれを文字
のパターンと置き換えたとすれば, 
二つのラベルの出現パターンが異なる部分はかすれや汚れと解釈することができる. 
以下に補完類似度の定義, 性質をそれぞれ示す. 

\subsubsection{補完類似度の定義}
この節では, 補完類似度(Complementary Similarity Measure)の定義を示す. 
定義\ref{para}のパラメータを用いて, $\vec{F}$の$\vec{T}$に対する
補完類似度を次のように定義する. 
この定義は文献\cite{Hagita95,Sawaki95a,Sawaki95b}に示されている定義である. 
\begin{df} 補完類似度
\begin{eqnarray}
S_c(\vec{F},\vec{T}) &=& \frac{a d-b c}{\sqrt{(a+c)(b+d)}} 
\label{csm}
\end{eqnarray}
\end{df}
この定義式から, 補完類似度はパラメータ$a,b,c,d$で表す出現情報をすべて
考慮した類似尺度である. 

\subsubsection{補完類似度の性質} 
文字認識に限らず, 二つのパターンの類似度を求める場合, 
二つのパターンの一致している部分だけに注目した類似尺度が用いられることが多
い. 
これらの類似尺度は二つのパターンをを入れ換えても同じ値を持つ. 
この性質を持つ類似尺度は対称性を持っているといわれる.
一方, 補完
類似度では分子にパラメータ$b,c$を用いて二つのパターンの相違を考慮した形の定義式
となっている. 補完類似度の定義式(\ref{csm})に含まれる項$bc$は, $\vec{F}$が
$\vec{T}$を完全に包含するなら$c=0$となるため, 0となり, また反対に, 
$\vec{T}$が$\vec{F}$を完全に包含するなら$b=0$となるため, この場合も0となる. 
このような場合, 補完類似度では定義式の分子が一致情報($ad$)と不一致情報($bc$)の差分をと
る形であるため, 包含関係を持つパターン対に対して高い類似度を保持する. 
また, 補完類似度は, 二つのパターンを入れ替えると値が変わる. このため, 補完類似
度は非対称性を持つ. 

\subsection{相互情報量}
相互情報量(Mutual Information)は二つの確率変数の依存性を表す尺度として一
般的に知られており, 多
くの処理に適用されている\cite{Nagao96,Manning99,Matsumoto00}. 
この節では, 相互情報量の一般的な定義式を示し
\cite{Honda65,Nakagawa92}, そ
の後, 定義\ref{para}のパラメータを用いて定義式を表現し直す. 

二つの確率変数$X,Y$について平均相互情報量$I(X;Y)$の定義式を示す. 
$X$は$x_1,x_2,...,x_n$をとり,$Y$は$y_1,y_2,...,y_m$をとるとしたとき, 
平均相互情報量は次式で表される. ただし, $p(x_i,y_j)$は$X$が$x_i$を, $Y$が
$y_j$を同時にとる確率である. 
\begin{eqnarray}
\mbox{\hspace*{-2em}}
I(X;Y)&=&\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j){\log}\frac{p(x_i,y_j)}{p(x_i)p(y_j)}
\label{mi-gen} \\
\mbox{\hspace*{-2em}}
&=&p(x_1,y_1){\log}\frac{p(x_1,y_1)}{p(x_1)p(y_1)} 
+p(x_1,y_2){\log}\frac{p(x_1,y_2)}{p(x_1)p(y_2)} \nonumber\\
\mbox{\hspace*{-2em}}
&+&p(x_2,y_1){\log}\frac{p(x_2,y_1)}{p(x_2)p(y_1)}
+p(x_2,y_2){\log}\frac{p(x_2,y_2)}{p(x_2)p(y_2)} 
\label{mi-parts}
\end{eqnarray}
次に, この定義式をパラメータを用いた表現に直すために, 
確率変数$X,Y$はそれぞれラベル$lab_1,lab_2$を表すとする. このとき, ラ
ベルの出現パターンは二値パターンであるため, 事象はデータにラベルが
出現するか出現しないかのどちらかとなり, データ集合に対して, 
\begin{itemize}
\item $p(x_1)$はデータにラベル$lab_1$が出現する確率, 
\item $p(x_2)$はデータにラベル$lab_1$が出現しない確率, 
\item $p(y_1)$はデータにラベル$lab_2$が出現する確率, 
\item $p(y_2)$はデータにラベル$lab_2$が出現しない確率
\end{itemize}
となる. これらの確率を言い換えると, データ集合に対する各事象を出現するデー
タの割合である. したがって, ラベル$X$に対するベクトルを$\vec{F}$, ラベル$Y$に
対するベクトルを$\vec{T}$とし, 定義\ref{para}のパラメータを用いると, 
式(\ref{mi-gen})は次のように表現できる. 
\begin{df} 平均相互情報量
\mbox{\hspace*{-2em}}
\begin{eqnarray}
I(X;Y)&=&\frac{a}{n}{\log}\frac{a n}{(a+b)(a+c)}
+\frac{b}{n}{\log}\frac{b n}{(a+b)(b+d)} \nonumber\\
&+&\frac{c}{n}{\log}\frac{c n}{(c+d)(a+c)}+
\frac{d}{n}{\log}\frac{d n}{(c+d)(b+d)}
\label{mi}
\end{eqnarray}
\end{df}
実験では, 式(\ref{mi})を用いて平均相互情報量を計算した. 
この定義式から, 平均相互情報量は出現情報をすべて考慮した類似尺度である. 
また, 平均相互情報量は対称性を持つ. 

一方, 平均相互情報量の第一項に基づく尺度が
関連性の高い単語対を発見するために多く提案されている
\cite{Church90,Rosenfeld96,Kita99}. 
この尺度は, ある単語が現れることによる情報量が他の単語と共起すること
を知ることによって増加する情報量を測る尺度である. 
これらの尺度における基本的な定義式を次に示す\cite{Church90}. 
本論文では, この尺度を自己相互情報量と呼ぶことにする. 
\begin{df} 自己相互情報量
\begin{equation}
I(x_1;y_1)=\log\frac{an}{(a+b)(a+c)}
\label{p-mi}
\end{equation}
\end{df}
この定義式から, 自己相互情報量は出現情報のうちどちらとも出現しないという情報を
考慮せず, 共起するという情報を中心とした類似尺度である. 
また, この尺度は対称性を持つ尺度である. 
本論文では, この自己相互情報量も比較対象として加えることにした. 

上記の相互情報量は対称性を持つ尺度であるが, 事象間の関係が一対多関係である場合, それらの事象が持つ出現パターン間の関係は包含関係にあるということが観察されるため, 平均相互情報量の第一項と第三項に基づく非対称な尺度も考えられる. 第一項は共起出現することによって増加する情報量を表し, 第三項はラベル$X$は出現しないとき, ラベル$Y$が出現することを知ることによって増加する情報量である. 本論文では, この尺度を非対称平均相互情報量と呼ぶことにする. 
\begin{df} 非対称平均相互情報量
\begin{equation}
I_{ac}(X;Y)=\frac{a}{n}{\log}\frac{a n}{(a+b)(a+c)}
+\frac{c}{n}{\log}\frac{c n}{(c+d)(a+c)}
\label{ac-mi}
\end{equation}
\end{df}
この定義式から, 非対称平均相互情報量はパラメータ$c$が大きいと, 類似度が低くなり, 逆に$c$が小さいと, 類似度が高くなるという性質を持つ. つまり, $c = 0$の場合, 高い類似度を保持する. 本論文では, この非対称平均相互情報量も比較対象として加え, 出現パターンの包含関係をとらえるために, 非対称性は重要な性質であるかどうかを検討する. 

\subsection{$\phi$相関係数}
統計処理に用いられる相関係数は, 二値データのときに$\phi$相関係数(Phi Coefficient)となる
\cite{TU-class94}. この関数は事象の独立性を検定するために用いられる$\chi^2$統計
量から計算される事象間の共起の強さを測る尺度である\cite{TU-class94,Manning99}. 

この節では, $\phi$相関係数の定義を示す. 二つの質量変数を$D,E$とし, データと
して$(D_1,E_1), ..., (D_n,E_n)$が与えられたとする. これらを定義\ref{para}のパラ
メータを用いて表現する. ただし, $\phi$相関係数は二値データの場合用いられる
相関係数であるので, データは$(1,1),(1,0),(0,1),(0,0)$の四つである. この
とき, $D$と$E$の$\phi$相関係数は次のように与えられる. 
\begin{df} $\phi$相関係数
\begin{equation}
\gamma_{DE} = \frac{a d-b c}{\sqrt{(a+b)(a+c)(b+d)(c+d)}} 
\label{phi}
\end{equation}
\end{df}
この定義式から, $\phi$相関係数は出現情報をすべて考慮した類似尺度である. 
この尺度は対称性を持つ尺度である. 
ここで, $D_i$の列をベクトル$\vec{F}$, $E_i$の列をベクトル$\vec{T}$と置き換
えると, この定義式の分子は補完類似度の定義式(\ref{csm})と同じである. 
また, 分母を比較すると, 補完類似度は$\phi$相関係数の分母から
$\sqrt{(a+b)(c+d)}$を取り除いたものであることがわかる. 
本論文では, この違いが
一対多関係
の推定にどのように影響するのかを観察する. 

\subsection{ベクトル空間モデルにおける類似尺度}
単語間の関係または単語と文書間の関係を推定するために, ベクトル空間モデルを利用す
る場合がある. 
これは, 単語を多次元空間にベクトルで表現し, ベクトル間の
類似度を測ることによって関係を推定する. 
ベクトル空間モデルにおける類似尺度はこれまでに多く
提案されている\cite{Manning99}. 本論文では, 
代表的なコサイン関数(Cosine), ダイス相関係数(Dice Coefficient)
を選び, 一対多関係の推定において性能を比較した. 

それぞれの尺度の定義式とその定義式をパラメータを用いて表現した式を次に示す. 
ここで, $F,T$はそれぞれ$lab_1,lab_2$に対するベクトルとする. 
\begin{df} コサイン関数
\begin{eqnarray}
cos(F,T) &=& \frac{| F \cap T|}{\sqrt{| F| \cdot | T|}} \nonumber\\
&=& \frac{a}{\sqrt{(a+b)(a+c)}}
\end{eqnarray}
\end{df}
コサイン関数はベクトル空間における類似尺度のなかでもっとも知られている類似尺度
である. しかし, この尺度は二つのベクトルの大きさが非常に異なる場合でもある
程度高い類似度を与えてしまう. 
\begin{df} ダイス相関係数
\begin{eqnarray}
S_d(F,T) &=& \frac{2| F \cap T|}{| F| +| T|} \nonumber\\
&=& \frac{2a}{(a+b)+(a+c)}
\end{eqnarray}
\end{df}
ダイス相関係数はコサイン関数が持つ問題点を軽減するために, 正規化を施した類
似尺度である. 

これらの定義式から, コサイン関数とダイス相関係数は出現情報のうちどちらとも出現しないという情報を
考慮せず, 共起するという情報を中心とした類似尺度である. 
また, これらの尺度は対称性を持つ尺度である. 

\subsection{信頼度}
これまでに, データベースの中から連想規則を抽出する問題に関する研究が多くさ
れている\cite{Adriaans96,Dzeroski96,Fayyad96a,Fayyad96b}. 
たとえば, 連想規則を高速に発見する手法として
{\it Apriori}アルゴリズムが提案されている\cite{Agrawal96}. この手法には, デー
タベースからの情報抽出において, 重要な尺度とされている支持率
(Support)と信頼度(Confidence)に基づく尺度が用いられている.
ここで, 支持率はデータ
ベースにおいて注目した事象を含むデータの割合であり, 信頼度は前提を満たす
データの集合において帰結も含むデータの割合である. 言い換えると, 信頼度は支
持率によって表現できる条件付き確率である. 
{\it Apriori}では, 支持率を用いて信頼度を計算し, ユーザが指定した信頼度の下限
値($minconf$)よりもその信頼度が高い場合, ``面白い''連想規則としている. 
次に定義式を示す. 
\begin{eqnarray*}
\frac{support(XY)}{support(X)} &\geq& minconf
\end{eqnarray*}
$support(XY)$は$X$(前提)と$Y$(帰結)のどちらと
もが現れるデータの支持率, $support(X)$は$X$(前提)が現れるデータの支持率
である. 
この式の左辺で求められる値が信頼度であり, これは
前提$X$が現われるという条件のもとで帰結$Y$が現
われるという条件付き確率である. 
本論文ではこれを単に信頼度と呼ぶこととする. 
この左辺を定義\ref{para}のパラメータを用いて表現すると, $support(XY)$は$a/n$,
$support(X)$は$(a+c)/n$と書くことができるので, 信頼度は次のように表現する
ことができる. 
\begin{df} 信頼度
\begin{equation}
conf(Y|X) = \frac{a}{a+c}
\end{equation}
\end{df}
この定義式から, 
信頼度は一方の出現情報だけを考慮するので, 非対称性を持つ尺度である. 
信頼度で使用されているパラメータは$a,c$であるが, これは出現頻度の小さいラベルを
含むデータだけから計算でき, それ以外のデータに関する情報を利用しない類似尺度である. 
本論文では, 信頼度はデータベースにおける連想規則を得るための基本的な尺度
とされているため, 比較対象に加えた. 

\section{評価実験}
\subsection{概要} 
本論文では, 注目するラベルとして日本の地名を選んで, 実験を行った.
地名を選択した一つ目の理由は, 地名間には実際に一対多関係が成り立つためである. 
たとえば, 県名と市名には地理的な包含関係があり, 
地名間の関係は一対多関係である. 
また, 二つ目の理由は, この関係は電話帳や地図, ポスタルガイドなどの既存データから
抽出できるため, 機械的に正解判定を行うことができることである. 
これらの理由から, 注目するラベルを日本の地名, その地名間において推定
する一対多関係を地理的な包含関係とし, 正解関係はポスタルガイドから抽出した
. 
正解とした地名の一対多関係は二つの地名について, 一方の地名がもう一方の地名を
地理的に包含する関係とした. たとえば, 大阪府は大阪市を地理的に包含するので, 
「大阪府, 大阪市」は一対多関係があるとする. 
このように, 一方の地名が都道府県名, もう一方の地名がそれに続く市郡名である
場合, 
それらの地名には一対多関係があるとし, この一対多関係を正解関係として一つの
関係を抽出した. 
以上のことより, 本論文では, 地名(都道府県市郡名
)をラベル集合$L$, 抽出した1239個の一対多関係を正解集合$R$とした. 

実験では, データ集合に現れる地名を組み合わせてできるすべての組について, 出現
パターンの類似度を測ることによって, その組が一対多関係であるかを推定する. 
そして, 組を類似度の降順にソートし, 実験結果とする. 
最後に, 上位$m$(任意の数)組を評価の対象となる組とし, その組について正解判定を行い, 
再現率で性能を評価する. 次に再現率の定義を示す. 
\begin{eqnarray*}
再現率 &=& \frac{評価対象とした組のうち正解した数}{全正解数}
\end{eqnarray*}

また, データ集合が持つ関係の特性を見るため, 多重度についても考察する.

\subsection{人工的に生成したデータ集合を用いた実験} \label{art-data}
この節では, モデルに従ったデータを用いて, 八つの類似尺度の
振る舞いを観察する. ここで用いたモデルは, 雑音のな
いデータモデルと, 雑音のあるデータモデルである. 

実験において, 生成するデータ集合の大きさを無限に大きくすることはできない. 
そこで, 生成するデータ集合の大きさを1000個としたが, その数が全正解数1239よ
りも小さいため, 全く使用されない正解もある. 
したがって, どんな手法を用いても欠けている情報を復元することはできないので, 
再現率は$1$にならないことになる. 

各地名の出現パターンは1000次元のベクトルで表され, 
各次元に対応するデータにある地名が出現するのであれば1, そうでなければ0が割り
当てられたその地名についての二値ベクトルである. 

この実験における評価方法は, 評価の対象となる組を500組ずつ増やしたときの再
現率をグラフにし, 性能を評価する.
また, 評価の対象となった組から, 特徴的ないくつかの組を取り出し, 
それらの組に対して各尺度が与えた順位と類似度について考察する. 

\subsubsection{雑音のないデータ集合を用いた実験} \label{sec:without}
この節では, 雑音のないデータ集合に対する類似尺度の振る舞いを
観察する. 雑音のないデータ集合$D_a$は定義\ref{no-noise}に沿って, ラベル集
合$L$と正解関係を要素とする関係集合$R$から作成した. アルゴリズムを
図\ref{algo:art_data}に示す. 
\begin{figure}[hpbt]
{\small
\begin{quote}
\hspace*{2em}
$begin$ \\
\hspace*{2em}
$D_a := \phi; ~~i := 0;$ \\
\hspace*{2em}
$while~~ i ~<~ 1000 ~~do$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}begin$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}j := 0; ~~d_i:=\phi;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}while~~ j ~<~ 2 ~~do$ \\
\hspace*{2em}
$\mbox{\hspace*{4em}}begin$ \\
\hspace*{2em}
\hspace*{4em}
$R$からランダムに$\langle l^j_c, l^j_p\rangle$を取り出す; \\
\hspace*{2em}
$\mbox{\hspace*{4em}}d_i := d_i \cup
 \{l_c^j,l_p^j\};$\\ 
\hspace*{2em}
$\mbox{\hspace*{4em}}j := j + 1$ \\
\hspace*{2em}
$\mbox{\hspace*{4em}}end;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}D_a := D_a \cup \{d_i\};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}i := i + 1$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}end$ \\
\hspace*{2em}
$end;$ 
\end{quote}
}
\caption{雑音のないデータ集合を作成するアルゴリズム} \label{algo:art_data}
\end{figure}
このアルゴリズムに沿って作成したデータ集合の要素であるデータはたとえば, 
$d_i = \{静岡県, 清水市, 神奈川県, 横浜市\}$というデータである. 
これは, 正解である関係集合$R$から$\langle 静岡県, 清水市\rangle$と
$\langle 神奈川県, 横浜市\rangle$の二つを取り出し, その四つのラベル
を要素として作成した集合である. 
要素数を4とした理由は, 4未満であると問題が簡単すぎるので, 
4が意味のある最低の数と考えたためである. 
このように作成したデータ$d_i$を1000個持
つデータ集合$D_a$を作成した. このデータ集合は雑音のないデータ集合である. 
これを用いて実験を行った. 
実験結果を図\ref{graph:art_data}に示す. 
この四つのグラフはそれぞれ同じ方法で作成した異なるデータ集合に用いて実験を行った結果である. 
\begin{figure}[bhpt]
\atari(141.8,100)
\caption{雑音のないデータ集合における実験} \label{graph:art_data}
\end{figure}

\begin{table} [thbp]
\centering
\caption{雑音のないデータ集合における順位と類似度の例}\label{without-comp}
\begin{tabular}{|c||r|r|r|r|r|r|}
\hline
組 & $\alpha$ & $\beta$ & $\gamma$ & $\delta$ & $\epsilon$ & $\zeta$\\\hline\hline
正解判定 & 不正解 & 不正解 & 不正解 & 正解 & 正解 & 正解 \\\hline
$a$ & 1 & 1 & 1 & 1 & 4 & 6 \\\hline
$b$ & 0 & 1 & 7 & 49 & 46 & 23 \\\hline
$c$ & 0 & 1 & 3 & 0 & 2 & 0 \\\hline
$d$ & 999 & 997 & 989 & 950 & 948 & 971 \\\hline
{\small 補完類似度} & 625 & 1770 & 3247 & 1362 & 269 & 3 \\
{\small } & (31.607) & (31.544) & (15.336) & (300.57) & (47.911) & (75.440) \\\hline
{\small 平均相互情報量} & 281 & 950 & 2327 & 2020 & 224 & 2 \\
{\small } & (0.0114) & (0.0074) & (0.0038) & (0.0043) & (0.0121) & (0.0316) \\\hline
{\small 自己相互情報量} & 18 & 334 & 1288 & 1779 & 2437 & 1176 \\
{\small } & (9.9658) & (7.9658) & (4.9658) & (4.3219) & (3.7370) & (5.1078) \\\hline
{\small 非対称平均相互情報量} & 349 & 965 & 2327 & 2017 & 246 & 2 \\
{\small } & (0.0100) & (0.0070) & (0.0038) & (0.0043) & (0.0119) & (0.0306) \\\hline
{\small $\phi$相関係数} & 18 & 352 & 1715 & 2038 & 1321 & 406 \\
{\small } & (1.0000) & (0.4990) & (0.1722) & (0.1379) & (0.2198) & (0.4496) \\\hline
{\small コサイン関数} & 18 & 334 & 1708 & 2040 & 1284 & 406 \\
{\small } & (1.0000) & (0.5000) & (0.1768) & (0.1414) & (0.2309) & (0.4549) \\\hline
{\small ダイス相関係数} & 18 & 271 & 1101 & 3029 & 1158 & 559 \\
{\small } & (1.0000) & (0.5000) & (0.1667) & (0.0392) & (0.1429) & (0.3429) \\\hline
{\small 信頼度} & 18 & 2314 & 3439 & 1280 & 1684 & 1009 \\
{\small } & (1.0000) & (0.5000) & (0.2500) & (1.0000) & (0.6667) & (1.0000) \\\hline
\end{tabular}
\end{table}
これらのグラフは, 上位の組の数を横軸, そのときの再現率を縦
軸とする. また, このデータ集合における再現率は約$0.8$で収束する. 
これは, $D$のなかに含まれていない正解があることを示している. 
このグラフでは, 上位に位置する組において, 補完類似
度の再現率の高さが目立ち, また補完類似度がもっとも早く収束している. 
すべてのグラフにおいて, 補完類似度に続き, 
信頼度, 非対称平均相互情報量, 平均相互情報量が高い性能を
示している. 言い換えると, これらのグラフは雑音のないデータ集合を用いた実験にお
いて, 補完類似度がもっとも一対多関係を推定する能力が高く, 次に信頼度, 非対
称平均相互情報量, 平均相互情報量の順に高いことを表している. 
この結果はすべてのグラフにおいて同じ結果を得ている. 
また, 非対称平均相互情報量は平均相互情報量と比べ, 
一対多関係を推定する能力が高いことを表しているが, 
有意な差を見ることはできなかった. 
しかし, このことから, 非対称性は一対多関係を推定するために有効な性質の一つと考え
られるが, 補完類似度と非対称平均相互情報量の性能差を見ると, 非対称性を持つだけで
は高い性能を得られないことがわかる. 

平均的な性能が高いだけでは, その性能が何によってもたらされたかがわからない
. 
そのため, 次にそれぞれの類似尺度の振る舞いに特徴的な組を選び出し, 定性的な分析を行う. 
表\ref{without-comp}は定性的な分析として, 図\ref{graph:art_data}の左上のグ
ラフにおいて
評価の対象に含まれた特徴的な6組を取り出し, それらの組に対してそれぞれの尺度で位置した
順位とそのとき与えられた類似度を, パラメータ$a,b,c,d$とともに示す. 

$\alpha$は正解ではない組「四日市市, 宇治市」である. この組は
一度だけ出現し, それが共起出現であった組($a=1,b=0,c=0$)である. 
この組は補完類似度では625位に位置し, その他の尺度ではより高い順位に位置する. 
特に, 自己相互情報量, $\phi$相関係数, コサイン関数, 
ダイス相関係数, 信頼度では上位に位置する. 
これらの尺度では各尺度における最大値がスコアとなっている. 
自己相互情報量は定義式にある分母が$1$となるため, データ総数の対数
$\log n$を与え, コサイン関数, ダイズ相関係数, 信頼度は$1.0$を類似度として与
えてしまう. これは, $d$を考慮していないことが一つの要因といえる. 
また, $\phi$相関係数は定義式の分母が平方根であり, $d$を分子に一つ分母に二つ持っている. 
このため, 分子と分母が同じになり, $1$を類似度として与えてしまう. 
つまり, $\phi$相関係数は, $d$が$a,b,c$よりも非常に大きい場合, 分子と分母が
ほぼ同じになり, 正解ではない組にも$1$に近い値を与えてしまう性質を持つ. 
このような組が500位までに多く存在する. このため, 上位500までを見たとき, 
自己相互情報量, コサイン関数, ダイス相関係数, 信頼度の再現率が, 補完類似度, 平均
相互情報量, 非対称平均相互情報量に比べ低いことの原因である. 

$\beta$は正解ではない組「川崎市, 富士市」である. この組は
補完類似度, 平均相互情報量, 非対称平均相互情報量, 信頼度では1000位近くまたはそれ以降の順位に位置するが, 
その他の尺度では300位前後に位置する. これは$d$を考慮しないことと, $d$が$a,b,c$に
比べ大きいことが原因と考えられる. 
このような組が1000位までに多く存在する. このため, 上位1000までを見たとき, 
自己相互情報量, コサイン関数, 
ダイス相関係数の再現率が, 補完類似度, 平均相互情報量, 非対称平均相互情報量, 信頼度に比べ非常に低
いことの原因である. 

$\gamma$は正解ではない組「海部郡, 静岡市」である. この組はダイス相関係数で
は1101位に位置し, その他の尺度ではより低い順位に位置する. 
これはパラメータ$b,c$によって$d$を使用しなくても下位と判定されるが, 
$d$を使用しないのは問題であり, $d$を使用する尺度はより下位と判定する. 

$\delta$は正解である組「東京都, 多摩市」である. これは
出現パターンが完全な包含関係にある組($c=0$)であり, 
一度だけ共起出現する組($a=1$)である. 
このような組が補完類似度では1000位から2000位の間に多く存在するが, 平均相互
情報量ではパラメータ$b$があるため, もっと低い順位に位置する. 
このことが図\ref{graph:art_data}において補完類似度と平均相互情報量の
上位1000から2000の間に見られる再現率の開きの原因である. 
また, 非対称平均相互情報量では, パラメータ$c$が$0$となるため, 定義式の第一
項の値が類似度となる. しかし, パラメータ$b$が第一項に含まれているため, 補
完類似度に比べ, 低い順位に位置し, 平均相互情報量より少し高い順位に位置して
いる. 
このことが平均相互情報量と同様に, 図\ref{graph:art_data}において補完
類似度と非対称平均相互情報量の上位1000から2000の間に見られる再現率の開きの
原因である. 
また, この原因は, 平均相互情報量に非対称性を持たせたことによる性能向上が
わずかであったことの要因である. 

$\epsilon$は正解である組「京都府, 中郡」である. これは
出現パターンが完全な包含関係ではない組($c>0$)である. 
この組は補完類似度, 平均相互情報量, 非対称平均相互情報量では300位以内に位置するが, その他の尺度
では1000位以降に位置する. 特に, 自己相互情報量は2437位と他のものより非常に低い
順位に位置する. 
これもパラメータ$b$が大きいことが原因である. 

$\zeta$は正解である組「石川県, 金沢市」である. これは出現パターンが完全な包含関係に
ある組($c=0$)であり, 6回共起出現する組($a=6$)である. 
この組は補完類似度, 平均相互情報量, 非対称平均相互情報量では3,2位に, $\phi$相関係数, コサ
イン関数, ダイス相関係数では500位以内に, 自己相互情報量と信頼度でも1200位以内
に位置し, どの尺度でも比較的高い順位に位置している. 
これはこのデータ集合において大きいパラメータ$a$をこの組が持つためである. 

表\ref{without-comp}における以上の考察からは, このデータ集合において, 
補完類似度, 非対称平均相互情報量, 平均相互情報量が一対多関係を推定する候補として残る
が, 図\ref{graph:art_data}のグラフに示されるように, 
1000位以降では非対称平均相互情報量と平均相互情報量の性能よりも信頼度の性能が高かった. 

また, 実験のために生成した四つの雑音のあるデータ集合には平均すると, 46の都道府県名が出現し, 
多重度は19.0であった. 
言い替えると, このデータ集合には46の都道府県名で平均すると, 
一つの都道府県名あたり19個程度の市郡名との関係が存在するということである. 
このことから, 実験結果を, 
46ラベルに対して多重度19を持つデータ集合における一対多関係を
推定する問題において, 補間類似度はもっとも高い性能を得たと見ることができる
. 

\subsubsection{雑音のあるデータ集合を用いた実験} \label{sec:with}
この節では, 雑音のあるデータ集合に対する類似尺度の振る舞いを観察する. 
雑音のあるデータ集合$D^*_a$は定義\ref{with-noise}に沿って, ラベル集合$L$と正
解関係を要素とする関係集合$R$から作成した. 具体的には, 
\ref{sec:without}節で生成した雑音のないデータ集合
$D_a$の要素$d_i$にそれぞれ雑音を追加したデータ$d^*_i$を作り, 
そのデータを要素とするデータ集合を作成した. 
アルゴリズムを図\ref{algo:noise_data}に示す. 
作成されたデータはたとえば, $d^*_i = \{静岡県, 清水市, 神奈川県, 横浜市, 京都府\}$と
いうデータである. 
これは, 雑音のないデータ$d_i = \{静岡県, 清水市, 神奈川県, 横浜市\}$に
雑音「京都府」を追加した集合である. 
「京都府」は$d_i$のどの要素とも正解集合$R$に含まれる関係を持ってい
ない. 本論文では, この性質を持つデータの要素を雑音と呼んでいる. 
このように作成したデータ$d^*_i$を1000個持
つデータ集合$D^*_a$を作成した. このデータ集合は雑音のあるデータ集合である. 
これを用いて実験を行った. 
雑音を各データに一つずつ入れた理由は, 定義\ref{with-noise}に示すように
雑音の数は4より十分小さい数であり, かつ雑音が
常にあるというデータ集合全体としてみると雑音が非常に多い状況を想定したため
である. 

\begin{figure}[th]
{\small
\begin{quote}
\hspace*{2em}
$begin$ \\
\hspace*{2em}
$D^*_a := \phi; ~~i := 0;$ \\
\hspace*{2em}
$while~~ i ~<~ 1000 ~~do$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}begin$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}D_aからd_iを取り出す;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}Lからランダムにl(l\not\in d_i)を一つ取り出す;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}d^*_i := d_i \cup \{l\};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}D^*_a := D^*_a \cup \{d^*_i\};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}i := i + 1$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}end$ \\
\hspace*{2em}
$end;$
\end{quote}
}
\caption{雑音のあるデータ集合を作成するアルゴリズム} \label{algo:noise_data}
\end{figure}

\begin{figure}[hbtp]
\atari(143,105.3)
\caption{雑音のあるデータ集合における実験} \label{graph:art_noise}
\end{figure}
\begin{table}[hbtp]
\centering
\caption{雑音のあるデータ集合における順位と類似度の例}\label{with-comp}
\begin{tabular}{|c||r|r|r|r|r|r|}
\hline
組 & $\alpha$ & $\beta$ & $\gamma$ & $\delta$ & $\epsilon$ & $\zeta$\\\hline\hline
正解判定 & 不正解 & 不正解 & 不正解 & 正解 & 正解 & 正解\\\hline
$a$ & 5 & 1 & 1 & 1 & 2 & 4\\\hline
$b$ & 83 & 5 & 0 & 61 & 122 & 53\\\hline
$c$ & 36 & 5 & 0 & 0 & 1 & 2\\\hline
$d$ & 876 & 989 & 999 & 938 & 875 & 941\\\hline
{\small 補完類似度} & 7739 & 6961 & 661 & 2531 & 2488 & 197\\
{\small } & (7.020) & (17.791) & (31.607)& (29.677) & (29.768) & (47.367)\\\hline
{\small 平均相互情報量} & 9651 & 4680 & 266 & 4461 & 4786 & 289\\
{\small } & (0.0004) & (0.0036) & (0.0114) & (0.0040) & (0.0060) & (0.0113)\\\hline
{\small 自己相互情報量} & 7849 & 3426 & 55 & 4431 & 6879 & 5093\\
{\small } & (0.4707) & (4.7959) & (9.9658) & (4.0116) & (2.4266) & (3.5479)\\\hline
{\small 非対称平均相互情報量} & 10104 & 4682 & 315 & 4429 & 4777 & 214\\
{\small } & (0.0004) & (0.0035) & (0.0100) & (0.0040) & (0.0035) & (0.0112)\\\hline
{\small $\phi$相関係数} & 7738 & 3823 & 55 & 4646 & 5578 & 3213\\
{\small } & (0.0248) & (0.1616) & (1.0000) & (0.1230) & (0.0903) & (0.2043)\\\hline
{\small コサイン関数} & 6399 & 3818 & 55 & 4660 & 5459 & 3165\\
{\small } & (0.0832) & (0.1667) & (1.0000) & (0.1270) & (0.1037) & (0.2163)\\\hline
{\small ダイス相関係数} & 3604 & 3051 & 55 & 7000 & 7099 & 3182\\
{\small } & (0.0775) & (0.1667) & (1.0000) & (0.1159) & (0.0315) & (0.1270)\\\hline
{\small 信頼度} & 7763 & 7681 & 1710 & 1628 & 2756 & 2631\\
{\small } & (0.1220) & (0.1667) & (1.0000) & (1.0000) & (0.6667) & (0.6667)\\\hline
\end{tabular}
\end{table}
実験結果を図\ref{graph:art_noise}に示す. 
この四つのグラフはそれぞれ同じ方法で作成した異なるデータ集合に用いて実験を行った結果である. 
これらのグラフは, 上位の組の数を横軸, そのときの再現率を縦
軸とする. 
この実験では, 雑音があることによって, 雑音のないデータ集合と比べ
不一致情報が多くなる. このため, すべての類似尺度の性能は雑音のないデータ集
合と比べ, 全体的に低い. 
不一致情報とは, データにラベルがどちらか一方しか現われないという情報であり
, パラメータ$b,c$で表される出現情報である. 

これらのグラフでは, 上位に位置する組において, 補完類似
度の再現率の高さが目立つ. 
すべてのグラフにおいて, 補完類似度に続き, 
信頼度, 非対称平均相互情報量, 平均相互情報量が高い性能を示している. 
言い換えると, これらのグラフは雑音のあるデータ集合を用いた実験において, 
上位の組の数が小さいとき, 補完類似度がもっとも一対多関係を推定する能力が高く, 
次に信頼度, 非対称平均相互情報量, 平均相互情報量の順に高いことを表している. 
この結果はすべてのグラフにおいて同じ結果を得ている. 
また, 非対称平均相互情報量は平均相互情報量と比べ, 
一対多関係を推定する能力が高いことを表しているが, 
有意な差を見ることはできなかった. 
雑音のないデータ集合を用いた実験と同じく, 
このことから, 非対称性は一対多関係を推定するために有効な性質の一つと考え
られるが, 補完類似度と非対称平均相互情報量の性能差を見ると, 非対称性を持つだけで
は高い性能を得られないことがわかる. 

前節と同様に, 性能差の原因を定性的に調べるため, 類似尺度の振る舞いに特徴的な組を選び出した. 
表\ref{with-comp}は定性的な分析として, 図\ref{graph:art_noise}の左上の
グラフにおいて
評価の対象に含まれた特徴的な6組を取り出し, それらの組に対してそれぞれの尺度で位置した
順位とそのとき与えられた類似度をパラメータ$a,b,c,d$とともに示す. 

$\alpha$は正解ではない組「埼玉県, 岩手県」である. 
この組は不一致情報を多く持つ組($b=83,c=36$)である. この組はどの尺
度でも3600位以降の低い順位に位置している. 

$\beta$は正解ではない組「徳島市, 浜田市」である. この組も
どの尺度でも3000位以降の低い順位に位置している. 
不一致情報が$\alpha$よりも少ないので, $\alpha$よりも高い順位に位置している. 

$\gamma$は正解ではない組「大分市, 新城市」である. この組は
一度だけ出現し, それが共起出現であった組($a=1,b=0,c=0$)である. 
この組はどの尺度でも$\beta$に比べ非常に高い順位に位置する. 
特に, 自己相互情報量, $\phi$相関係数, コサイン関数, ダイス相関係数では上位に位置する. 
これらの尺度では各尺度における最大値がスコアとなっているためである. 

$\delta$は正解である組「大阪府, 羽曳野市」である. この組は
出現パターンが完全な包含関係にある組($c=0$)である. 
この組は補完類似度と信頼度では, その他の尺度と比べ高い順位に位置している. 
信頼度がこの組をもっとも高い順位に位置付けている. これは, 信頼度は完全な包含
関係にある組に対して最大値を与えるためである. 
このデータ集合においては, 信頼度が最大値を与える組は2533組あったが, そのな
かには正解も不正解もあり, 完全な包含関係を優遇することは必ずしも有効ではな
いと観測される. 

$\epsilon$は正解である組「北海道, 登別市」である. この組は出現パターンが
完全な包含関係ではない組($c>0$)である. 
この組も補完類似度と信頼度では, その他の尺度と比べ高い順位に位置している
. 

$\zeta$は正解である組「岐阜県, 羽島市」である. 
この組は補完類似度, 平均相互情報量, 非対称平均相互情報量では, その他の尺度と比べ高い順位に位置し
ている. 
この組における補完類似度と平均相互情報量の順位の差は, 平均相互情報量がこの
組よりも$\gamma$のような組に高いスコアを与えるためである. 
平均相互情報量では$\gamma$のような組が$\zeta$よりも上位に77個も位置する. 
補完類似度と非対称平均相互情報量の順位の差も同じ原因によるものである. 
このことが図\ref{graph:art_noise}に見られる
補完類似度とそれぞれ平均相互情報量, 非対称平均相互情報量の上位500組を対象とした場合の再現率における開きの原
因である. 

表\ref{with-comp}における以上の考察からは, このデータ集合において, 
補完類似度, 非対称平均相互情報量, 平均相互情報量が一対多関係を推定する候補として残る
が, 図\ref{graph:art_noise}のグラフに示されるように, 
2000位以降では非対称平均相互情報量と平均相互情報量の性能よりも信頼度の性能が高かった. 

また, 雑音のないデータ集合と同じく,
実験のために生成した四つの雑音のあるデータ集合には平均すると, 
46の都道府県名が出現し, 多重度は19.0である. 
言い替えると, このデータ集合には46の都道府県名で平均すると, 
一つの都道府県名あたり19個程度の市郡名との関係が存在するということである. 
このことから, 実験結果を, 
46ラベルに対して多重度19を持つデータ集合における一対多関係を
推定する問題において, 補間類似度はもっとも高い性能を得たと見ることができる
. 

\subsubsection{多重度に関する実験}
この節では, 補完類似度の性能が多重度にどう依存するのかを実験す
る. 
具体的には, 人工的に一対多関係の正解集合を作成し, その一対多の程度を変
化させ, 正解集合から生成したデータに対する類似尺度の振る舞いを観察する. 
人工的なデータでは, 正解集合から公平にサンプルされるの
で, 正解集合の一対多の比率と多重度は一致する. 
\begin{figure}[hbtp]
{\small
\begin{quote}
\hspace*{2em}
$begin$ \\
\hspace*{2em}
$Sは重複のない10000個の乱数を要素とする集合;$ \\
\hspace*{2em}
$L := \phi; ~~nは定数; ~~mは定数; ~~R_m^n := \phi; ~~i := 0;$ \\
\hspace*{2em}
$D^{n*}_m := \phi; ~~j := 0;$ \\
\hspace*{2em}
$while~~ i < n ~~do$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}begin$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}Sから乱数l_cを一つ取り出す;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}Sからl_cを削除する;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}Sからm個の乱数(l_p^1,...,l_p^m)を取り出す;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}Sからl_p^1,...,l_p^mを削除する;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}} r_i:= \{\langle l_c,l_p^1\rangle ,...,
\langle l_c,l_p^m\rangle \};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}R_m^n := R_m^n \cup r_i;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}L := L \cup \{l_c, l_p^1,...,l_p^m\};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}i := i + 1$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}end;$ \\
\hspace*{2em}
$while~~ j ~<~ 1000 ~~do$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}begin$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}i := 0; ~~d^{*}_{j} := \phi;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}while~~ i ~<~ 2 ~~do$ \\
\hspace*{2em}
$\mbox{\hspace*{4em}}begin$ \\
\hspace*{2em}
$\mbox{\hspace*{4em}}R_m^n$からランダムに$\langle l_c^i,l_p^i\rangle$を取り出す; \\
\hspace*{2em}
$\mbox{\hspace*{4em}}d^{*}_{j} := d^{*}_{j} \cup \{l_c^i,l_p^i\};$ \\
\hspace*{2em}
$\mbox{\hspace*{4em}}i := i + 1$ \\
\hspace*{2em}
$\mbox{\hspace*{4em}}end;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}Lからランダムにl(l\not\in d^{*}_{j})を一つ取り出す;$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}d^{*}_{j} := d^{*}_{j} \cup \{l\};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}D^{n*}_m := D^{n*}_m \cup \{d^{*}_{j}\};$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}j := j + 1$ \\
\hspace*{2em}
$\mbox{\hspace*{2em}}end$ \\
\hspace*{2em}
$end;$
\end{quote}
}
\caption{乱数集合から関係集合とデータ集合を作成するアルゴリズム}
 \label{algo:randomnum-data}
\end{figure}
実験に用いる正解関係$\langle l_c,l_p \rangle$を要素とする関係集合$R_m^n$とデータ集合$D^{n*}_m$は図
\ref{algo:randomnum-data}に示すアルゴリズムを用いて作成した. 
アルゴリズムに現れる$n,m$はそれぞれ$R_m^n$において$l_c$であるラベルの数, 一つの$l_c$と関係を持つ$l_p$の数である. 
すなわち, $m$はデータ集合$D^{n*}_m$が持つ多重度である. 
たとえば, $n = 25$, $m = 5$とした場合, 
作成される正解とする関係集合$R_m^n$は25種類の$l_c$を持ち, それぞれの
$l_c$が5種類の関係, つまり$l_p$を5個持つような125対を要素とする集合である. 
これは, $R_m^n$に$\langle 5,10\rangle,\langle 5,32\rangle,
\langle 5,777\rangle,\langle 5,24\rangle,\langle 5,63\rangle$
といった一つの$l_c$に対して五つの関係があることを意味する. 
このような集合から作成されるデータ集合$D^{25*}_{5}$の要素であるデータはた
とえば, 
$d^{*}_{j} =\{5,10,12,321,45\}$というデータである. 
これは, $R_m^n$から$\langle 5,10\rangle$と$\langle 12,321\rangle$の二つを取り
出し, その二つの関係に含まれるラベルと関係を持たないラベル45を追加したデータである. 

\ref{sec:without}節と\ref{sec:with}節の実験で用いたデータ集合は, $n = 46$, $m = 19
(= 多重度)$であったので, その前後の値で実験を行う. 
実験結果は, $n$を25としたとき$m$を1,2,5,10,20,50,100,200と変化させた場合と, 
$n$を50としたとき$m$を1,2,5,10,20,50,100,200と変化させた場合の
推定能力である. 
推定能力はR-精度によって, 評価した. 

\begin{figure}[htbp]
\newlength{\minitwocolumn}
\setlength{\minitwocolumn}{0.5\textwidth}
\addtolength{\minitwocolumn}{-0.5\columnsep}
\begin{minipage}[h]{\minitwocolumn}
\centering
\atari(66,44.1)
\caption{25ラベルに対して多重度を変化させた \\ 場合の精度変化} \label{graph:dup25}
\end{minipage}
\begin{minipage}[h]{\minitwocolumn}
\centering
\atari(66.4,44.6)
\caption{50ラベルに対して多重度を変化させた \\ 場合の精度変化} \label{graph:dup50}
\end{minipage}
\end{figure}
実験結果を図\ref{graph:dup25}, \ref{graph:dup50}に示す. これらのグラフは
, 多重度を横軸, そのときのR-精度を縦軸とする. 図\ref{graph:dup25}は25ラベ
ルに対して多重度を変化させた場合の精度変化を示し, 図\ref{graph:dup50}は
50ラベルに対して多重度を変化させた場合の精度変化を示す. 図
\ref{graph:dup25}では, 多重度2までは実験に使用した類似尺度の精度はすべて同
じであるが, この時点で自己相互情報量は他の尺度より精度が低下し始める. 
多重度10から次第に精度の差が現れ, この時点以降の多重
度では補完類似度の精度がもっとも高い. 補完類似度に続き, 信頼度, 非対称平均
相互情報量, 平均相互情報量の順に高い精度を示している. また, 図
\ref{graph:dup50}では, 多重度5から精度の差が現れ, 
多重度100までは補完類似度の精度がもっとも高く, 多重度200では補完類似度
, 信頼度, 平均相互情報量, 非対称平均相互情報量の精度は等しい. 図
\ref{graph:dup50}においても図\ref{graph:dup25}と同様, 補完類似度に続き, 信
頼度, 非対称平均相互情報量の精度, 平均相互情報量の順に高い精度を示している
. この二つのグラフから, 多重度が1, 2程度であれば, 実験に使用したどの類似尺
度を用いても関
係を推定する能力に差はないが, 多重度が高い場合, 補完類似度は他の類似尺度よ
りも一対多関係を推定する能力が高いことがわかる. このことから, 補完類似度は
一対多関係を推定する類似尺度として有効であることが示唆される. 

\subsection{実データを用いた実験} \label{real}
\subsubsection{実験方法} 
この節の実験では, 現実の新聞記事から日本の地名を抽出し, 
データ集合を作成した. 
実験は次の流れで行う. 
まず, 新聞記事の集合からラベル集合$L$に含まれる地名
を一つでも持つ新聞記事をデータ$d^{**}$として抽出し, 
その新聞記事の集合を観察できるデータ集
合$D^{**}$とする. 次に, 地名毎に出現パターンに対応
する二値ベクトルを作成し, 
ラベル間の出現パターンの類似度を測定する. 
この測定値をもって, 地名間にある一対多関係の推定とする. 

データ集合の作成方法を説明する. 
新聞記事の集合は毎日新聞一年分とし, 七年分に対して年版毎にデータ集合を作成
した\cite{Mainichi91-97}. 
まず, 日本語形態素解析システム「茶筌」\cite{Matsumoto97}に地名辞書を追加し
た後, 新聞記事の形態素解析を行い, その結果から地名と, その地名を含む記事の識
別番号を抽出した.
次に, 記事の識別番号をデータの識別番号$i$として扱い, その記事に含まれる地名を
要素とする集合を作り, その集合をデータ$d^{**}_i$とした.
このように作成した$d^{**}_i$を要素するデータ集合を観測できる集合$D^{**}$と
した. 

本論文では, この方法で年版毎に作成した集合に対して, 一対多関係の推定を行った.
ここで, このコーパス中には単に「大阪」とだけ出現し, これが「大阪府」と「大
阪市」のどちらを表すのかわからない地名が出現する. この地名については
どちらかに解釈し正解であれば正解とした. 「大阪府, 大阪」の場合, 
「大阪」を「大阪市」と解釈し, 
また, 「大阪, 大阪市」の場合, これは「大阪」を「大阪府」と解釈し, 
正解とした. 

実験の前に, 新聞記事に一つの都道府県名に対して, 平均的にいくつの市郡名との
関係が実際に出現するかを調査した. 
極端な場合, 実質的に県庁所在地だけしか出現しないならば, コーパス上では多重
度は1となってしまうこともありうるため, 実際の地名データの多重度を調査して
おく必要がある. 

実データにおける多重度を計測した結果, 表\ref{tab:dupchk}に示されるように, す
べての年度において多重度は20前後であった. 
このことから, 本節の実験を, 
都道府県名50に対して多重度20を持つ実データからラベルの一対多関係を推定する問
題と見ることができる. 

\begin{table}[htb] 
\centering
\caption{年版ごとの多重度}\label{tab:dupchk}
\begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
年版 & 91 & 92 & 93 & 94 & 95 & 96 & 97 \\\hline \hline
多重度 & 21.7 & 20.5 & 20.6 & 22.5 & 20.6 & 19.6 & 19.3 \\\hline
\end{tabular}
\end{table}
評価においては, 正解関係1239個を用いて正解判定を行った. 
実験では, それぞれの類似尺度を用いて, 各年版に対す
るデータ集合$D^*$に含まれるすべての地名の組合せについて類似度を計算する.
その組合せは非常に多く, すべてを評価対象とすることは現実的ではない. 
そこで, 上位1239個についての適合率をとり, 性能を比較することにした. 
この比率はR-精度と呼ばれ, 情報検索などで用いられる性能尺度である. 
次に適合率の定義を示す. 
\begin{eqnarray*}
適合率 &=& \frac{評価対象とした組のうち正解した数}{評価対象とした組数}
\end{eqnarray*}

\subsubsection{評価結果}
年版毎における各類似尺度のR-精度を表\ref{r_prec2}に示す. 
表\ref{r_prec2}をグラフで表したものが
図\ref{r_prec}である. 
表\ref{r_prec2}とこのグラフは, 
すべての年版において補完類似度がもっとも高い性能を持つこと
を表している. 
{\small 
\begin{table}[thbp]
\centering
\caption{実データにおけるR-精度}\label{r_prec2}
{\small
\begin{tabular}{|c||c|c|c|c|c|c|c|}
\hline
年版 & 91 & 92 & 93 & 94 & 95 & 96 & 97 \\ \hline \hline 
補完類似度 & 0.699 & 0.559 & 0.431 & 0.362 & 0.315 & 0.485 & 0.416 \\ \hline
平均相互情報量 & 0.529 & 0.371 & 0.287 & 0.256 & 0.190 & 0.322 & 0.285
 \\ \hline
自己相互情報量 & 0.001 & 0.012 & 0.021 & 0.009 & 0.026 & 0.028 & 0.025
 \\ \hline 
非対称平均相互情報量 & 0.534 & 0.375 & 0.290 & 0.259 & 0.193 & 0.325 & 0.287
 \\ \hline 
$\phi$相関係数 & 0.001 & 0.052 & 0.086 & 0.041 & 0.142 & 0.157 & 0.148
 \\ \hline 
コサイン関数 & 0.001 & 0.054 & 0.086 & 0.043 & 0.148 & 0.161 & 0.155 \\ \hline
ダイス相関係数 & 0.001 & 0.055 & 0.103 & 0.039 & 0.113 & 0.128 & 0.146
 \\ \hline 
信頼度 & 0.024 & 0.123 & 0.158 & 0.061 & 0.239 & 0.220 & 0.232 \\ \hline
\end{tabular}
}
\end{table}
}
\begin{figure}[bhtp]
\centering
\atari(137.3,96.1)
\caption{実データにおけるR-精度のグラフ} \label{r_prec}
\end{figure}
人工的に生成したデータでは, 信頼度が非対称平均相互情報量と平均相互情報量よりも
性能が高い場合があったが, 
実データでは, 非対称平均相互情報量と平均相互情報量が信頼度よりも性能が高い. 
言い換えると, 実データを用いた実験において, 補完類似度がもっと
も一対多関係を推定する能力が高く, 次に非対称平均相互情報量, 平均相互情報量
, 信頼度の順に高いことを表している. 
この結果はすべての年版において言えることであるため. 
また, 人工的に生成したデータと同様に, 非対称平均相互情報量は平均相互情報量と比べ, 
一対多関係を推定する能力が高いことを表しているが, 
有意な差を見ることはできなかった. 
しかし, このことから, 非対称性は一対多関係を推定するために有効な性質の一つと考え
られるが, 補完類似度と非対称平均相互情報量の性能差を見ると, 非対称性を持つだけで
は高い性能を得られないことがわかる. 

\begin{table}[thbp] 
\centering
\caption{実データにおける順位と類似度の例}\label{real-comp}
\begin{tabular}{|c||r|r|r|r|r|r|}
\hline
組 & $\alpha$ & $\beta$ & $\gamma$ & $\delta$ & $\epsilon$ & $\zeta$ \\\hline\hline
正解判定 & 不正解 & 不正解 & 正解 & 正解 & 正解 & 正解 \\\hline
$a$ & 1 & 155 & 32 & 13 & 130 & 1860 \\\hline
$b$ & 0 & 381 & 249 & 202 & 697 & 4473 \\\hline
$c$ & 0 & 310 & 55 & 0 & 130 & 1124 \\\hline
$d$ & 53328 & 52483 & 52993 & 53114 & 52372 & 45872 \\\hline
{\small 補完類似度} & 12868 & 107 & 1239 & 1075 & 76 & 1 \\
{\small } & (*230.91) & (1616.94) & (781.54) & (829.37) & (1808.49) & (6550.99) \\\hline
{\small 平均相互情報量} & 15761 & 28 & 1031 & 1495 & 52 & 1 \\
{\small } & (*0.0003) & (0.0120) & (0.0031) & (*0.0020) & (0.0101) & (0.0639) \\\hline
{\small 自己相互情報量} & 21 & 73197 & 49151 & 20654 & 74144 & 153602 \\
{\small } & (15.7026) & (*5.0516) & (*6.1253) & (*7.9544) & (*5.0109) & (*2.3920) \\\hline
{\small 非対称平均相互情報量} & 18167 & 28 & 1018 &	1492 & 50 & 1 \\
{\small } & (*0.0003) & (0.0114) & (0.0030) & (*0.0019) & (0.0098) & (0.0576) \\\hline
{\small $\phi$相関係数} & 21 & 1208 & 3741 & 2263 & 1637 & 552 \\
{\small } & (1.0000) & (0.3040) & (*0.2024) & (*0.2454) & (*0.2745) & (0.3797) \\\hline
{\small コサイン関数} & 21  & 1188 & 3400 & 2272 & 1570 & 398 \\
{\small } & (1.0000) & (0.3105) & (*0.2047) & (*0.2459) & (*0.2804) & (0.4279) \\\hline
{\small ダイス相関係数} & 21 & 727 & 3267 & 8250 & 1453 & 410 \\
{\small } & (1.0000) & (0.3100) & (*0.1739) & (*0.1140) & (*0.2392) & (0.3992) \\\hline
{\small 信頼度} & 3654 & 18479 & 15039 & 70 & 10145 & 6483 \\
{\small } & (*1.0000) & (*0.3333) & (*0.3678) & (1.0000) & (*0.5000) & (*0.6233) \\\hline
\end{tabular}
\end{table}
また, 多重度に関して見ると, ラベル50に対して多重度20を持つ実データにおいて, 
前節に示した多重度に関する実験結果と同じく, 
補完類似度が有効である結果を得ている. 

表\ref{real-comp}は定性的な分析として, 93年版において評価の対象に含まれた
特徴的な6組を取り出し, それらの組に対してそれぞれの
尺度で位置した順位とそのとき与えられた類似度をパラメータ$a,b,c,d$とともに示す. 
ただし, 表に現れる`*'はその尺度においてはその組が評価の対象外であったことを表す. 

$\alpha$は正解ではない組「湯沢市, 中野市」である. この組は
一度だけ出現し, それが共起出現であった組($a=1,b=0,c=0$)である. 
この組は自己相互情報量, $\phi$相関係数, コサイン関数, ダイス相
関係数では評価対象とした組内に含まれているが, 
補完類似度, 平均相互情報量, 非対称平均相互情報量, 信頼度では含まれていない. 
これは, 自己相互情報量, $\phi$相関係数, コサイン関数, ダイス相関係数では
この組に最大値をスコアとして与えるためである. 
一方, 信頼度ではこの組にスコアとして最大値が与えるが, この組は評価対象とした上位1239組内
に含まれていない. 
これは, このデータ集合には信頼度が最大値を与えてしまう組が多く存在する
ことを表している. 

$\beta$は正解ではない組「秋田, 青森」である. この組は
自己相互情報量と信頼度では評価対象した組内に含まれてないが, その他の尺度では含まれている. 
これは, 正解である$\gamma$に比べ, パラメータ$a$が非常に大きいことが原因である. 
また, 隣接する県であることも影響し, この組が抽出された可能性もある. 
$\gamma$は正解である組「岩手県, 盛岡市」である. この組は
補完類似度, 平均相互情報量, 非対称平均相互情報量では評価対象とした組内に含まれているが, その他の尺度では含まれていない. 
また, 自己相互情報量と信頼度以外の尺度では正解ではない$\beta$よりも低い順位に位置している. 
これは, 正解ではない$\beta$に比べ, パラメータ$a$が小さいことが原因である. 

$\delta$は正解である組「愛媛県, 温泉郡」である. この組は
出現パターンが完全な包含関係にある組($a>1,c=0$)である. 
この組は補完類似度と信頼度では評価対象とした組内に含まれているが, 
その他の尺度では含まれていない. 
信頼度がこの組をもっとも高い順位に位置付けている. これは, 信頼度は完全な包含
関係にある組に対して最大値を与えるためである. 
信頼度は$\gamma,\delta$のようにパラメータ$c$が$0$の場合, 最大値を与える. 
93年版のデータ集合においては, 信頼度が最大値を与える組は$\alpha,\delta$を含め
4793組あった. このうち$\delta$のような組は788組あった. 

$\epsilon$は正解である組「静岡, 浜松」である. 
この組は補完類似度, 平均相互情報量, 非対称平均相互情報量では評価対象とした組内に含まれているが, その他の尺度では含まれていない. 
また, この組は補完類似度と信頼度以外の尺度では正解ではない$\beta$よりも
低い順位に位置している. 
これは$\beta$に比べ, パラメータ$a$が小さく, $b$が大きいことが原因である. 
このことより, 一対多関係を推定する問題における尺度は
不一致情報を緩和することが必要であると考えられる. 

$\zeta$は正解である組「大阪, 大阪市」である. 
この組は実データにおいてパラメータ$a$がもっとも大きい組である. 
この組は信頼度では評価対象とした組内に含まれていないが, 
その他の尺度では含まれている. 
これは$\alpha,\delta$のような$c$が$0$の組が多いことと, 
この組が大きい$c$を持つことが原因である. 

表\ref{real-comp}における以上の考察から, 実データにおいて, 
補完類似度が一対多関係を推定することにもっとも適していると見ること
ができる. 
また, 人工的に生成したデータ集合においては信頼度の性能が
非対称平均相互情報量と平均相互情報量より高かったが, 実データにおいては非対称平均相互情報量と平均自己相互情報量のほうが高い. 
これは, 実データが偶然共起出現し, 完全な包含関係である組($a=1,c=0$)を非常
に多く抽出することが原因である. 93年版のデータ集合においては, このような組
は4005組あった. 

以上のことから, 一対多関係を推定する問題において,
補完類似度は有効であると考える. 

\section{考察}
関係を抽出する場合, 用いる類似尺度が問題となる. 類似尺度によって推定される
関係の確かさが決まり, それらの関係を用いる処理の性能に直接影響する. 
本論文では, 一対多関係を推定する問題において, 
どのような類似尺度が有効であるかを実験によって示した. 

実験において, もっとも性能が高かった類似尺度は補完類似度であった. 
補完類似度は文字認識の分野のもので, 劣化印刷文字を高い性能で認識でき
るように考案された類似尺度である\cite{Hagita95,Sawaki95a,Sawaki95b}.
このことから, 本論文は補完類似度の応用を一つ提案していると見ることもできる. 

これまでに提案されているデータマイニング手法
\cite{Adriaans96,Fayyad96b}は, あらかじめデータから雑音を除去する処理を行っ
た雑音の少ないデータを対象としていることが多い. これらの手法の多くは, 支持
率と信頼度に基づき知識を発見する. しかし, 実験で示したように, 
信頼度は雑音に反応しやすい. 
これを避けるために雑音の除去を前処理として行なうのだが, 雑音を完全に
除去することは一般には難しい場合が多い. 
一方, 補完類似度は雑音に強い特長を持つため, 前処理となる雑音の除去を失敗した
としてもある程度の性能を保ち, 関係の抽出を行うことができる. 
出現パターンの比較による一対多関係の抽出における
補完類似度の性能の高さはこの尺度が持つ非対称性によるところもある. 
本論文の実験において, 一対多関係を推定する問題における非対称性の有効性を調
べるために, 対称性を持つ平均相互情報量の性能と, この相互情報量を改良して
, 非対称性を持たせた非対称平均相互情報量の性能を比較した結果, 非対称平均相
互情報量のほうがわずかに高かった. 
このことからも非対称性は一対多関係を推定
する問題において有効な性質の一つと考えられる. 
また, これまでに, テキストから定型表現を抽出する場合, 従来の相互情報量よりも非対
称性を持つように改良した情報量を用いた場合のほうが高い正解率を得られた
という報告がされている\cite{Sinnou95}.
この報告も, 非対称性を持つ尺度は関係抽出に有効であることを示している.
これは, 使用する類似尺度の範囲を非対称性を持つものに広げる考え方が妥当であ
ることを意味している. 
しかし, 補完類似度の性能と非対称平均相互情報量の性能との差から, 
一対多関係を推定する問題において, 非対称性だけでは有意な差は見られないことがわかった. 
また, 地名と同様に一対多関係を持つラベルは多数存在する. 
たとえば, 企業グループ名と企業名, 
総理大臣の名前と一大臣の名前などを考えた場合でも, 
知名度の高い企業グループ名や総理大臣の名前のほうが出現頻度が高いことが予想され
る.
このようなラベル間にある関係は一対多関係であり, この関係を推定するには, 
補完類似度が有効であると考えられる. 
ただし, これらのラベル間の関係に対する正解の定義が難しいので, これらのラベ
ル間の関係を推定する問題を検討することは今後の課題である. 

今後の展望としては, 補完類似度をテキストマイニングに
適用することを考えている. 
テキストから発見したい知識は, 定型表現, 
未知語や類義語に関する情報, 名詞句の修飾関係, 階層関係など
テキストを分析するために必要となる知識である. 
これらの知識を用いてテキストを分析することによって, 情報抽出が容易なデータ
ベースを構築することが可能となる
\cite{Glymour97}. 

また, 未知語は人によって表現が異なる語や述語, 新生語などであり, 
関連する既知語よりも出現頻度が低く, 
それらの出現パターンは包含関係にあると予想される. 
このとき, 補完類似度を用いて語間の一対多関係を推定することによっ
て, 未知語に関する情報を得ることができると考える. 
このように, 補完類似度は事象間の一対多関係を推定することによって, テキスト分析
に必要なこれらの知識を得ることに応用できると考えられる. 

\section{関連研究}
本論文では, 統計的手法により, コーパスから一対多関係を抽出する手法を提案した. 
これまでに, コーパスから事象間の関係を抽出する研究が多く行われている. 
この研究の代表的なものはテキスト分析に用いられる言語知識としての関係の抽出
である. 

言語知識の獲得では出現パターンの共起性だけでなく, 一般に品詞情報や構文解析結果を
用いることも多い\cite{Utsuro95}. 
本論文では, 構文解析や品詞情報を用いずに, 事象が持つ出現パターンの
共起性だけに注目して, コーパスから一対多関係を抽出することを行った. 

コーパスを用いてpart-of関係やis-a関係を抽出する研究も
行われている. part-of関係を抽出する研究において, 
コーパスから有用なpart-of関係を抽出する手法が提案されている
\cite{Berland99}. 
この手法はpart-of関係を効果的に抽出するための構文パターンを分析することに
よって, 高い性能を示している. 
part-of関係は本論文で抽出しようとした一対多関係の一種とみなすことができる. 
使用する情報が異なるが, 本論文で提案する手法と構文パターンに基づく手法は
同じ問題に対する異なるアプローチであるといえる. 
is-a(kind-of)関係を抽出する研究において, 
辞書の定義文から一般的な単語のis-a関係を抽出する手法
が提案されている\cite{Tsurumaru91}. 
この手法はパターンマッチ手法を用いて名詞や動詞のis-a関係を抽出している.
また, コーパスから下位レベルにある単語のグループを作り, そのグルー
プと一対一関係にある上位レベルの単語を求める
ボトムアップ手法が提案されている\cite{Caraballo99}. 
この手法は一般的な名詞が`and'によって連結されている部分を見つけることによって
名詞のis-a関係を抽出している. 
これらの研究では, 一般的な名詞を対象とする. 
一方, 本論文で提案する手法では, 固有表現や専門用語を事象の対象とする. 
is-a関係も本論文で抽出しようとした一対多関係の一種とみなすことができる. 
使用する情報と対象とする事象が異なるが, 同じ問題に対して相補的に用いること
ができると考えられる. 

\section{おわりに}
本論文では, コーパスから事象間の一対多関係を推定する問題を考えた. 
これまでにコーパスから事象間の関係を推定することが
多く研究されている. 一般に, この問題に対する解決法
の多くは, コーパスを構成する文書における事象の共起に基づいている. これらの
手法では暗黙的に事象間の関係は一対一関係であることを想定している. 
しかし, 実際には, 事象間の関係は一対多関係である場合があり, この特徴のためにいくつか
の工夫が可能であった. 
本論文では, コーパス中の一対多関係を推定するために補完類似度を利用することを提案した. 
この尺度は本来文字認識システムのために開発され, テンプレートとした文字が持
つパターンにオーバーラップしたパターンを認識するの
に有効であることが知られているが, これまでテキスト処理に利用されたことはなかった. 
この補完類似度の一対多関係を推定する能力を評価するために, 地名(都道府県市郡名
)を対象事象とした実験において, 
平均相互情報量, 自己相互情報量, 非対称平均相互情報量, $\phi$相関係数, 
コサイン関数, ダイス相関係数, 信頼度との性能比較を行った. 
実験では, 三種類のコーパスを用いた. 一つ目は実際に地名間にある一対多関係から合成し
た人工的なデータ集合である. 二つ目も実際の関係から合成したが, 
誤った関係を導く少量の要素も含むデータ集合である. 
三つ目は現実の新聞記事コーパスから得たデータ集合である. 
これらの評価実験において, 補完類似度がもっとも優れており, 
補完類似度は一対多関係の推定問題に対して有効であることを示した. 

\begin{acknowledgment}
本研究は文部省科学研究補助金10680379の成果です.
また,NTT光ネットワーク研究所と住友電工との共同研究の成果を利用させて
頂きました.
NTTコミュニケーション科学研究所の萩田紀博氏とNTT基礎研究所の澤木美奈子氏
に補完類似度の情報を提供して頂きました.
本学情報工学系中川聖一教授に貴重なアドバイスを頂きました.
深く感謝いたします.
\end{acknowledgment}

\bibliographystyle{jnlpbbl}


\bibliography{jnlpbib}

\begin{biography}
\biotitle{略歴}
\bioauthor{山本 英子}
{
1973年生．平成14年豊橋技術科学大学大学院工学研究科電子・情報工学専攻博士課程
修了．
同年，通信総合研究所に専攻研究員として入所．博士（工学）．
}

\bioauthor{梅村恭司}
{
1959年生．1983年東京大学大学院工学系研究科情報工学専攻修了課程修了．
同年，日本電信電話公社電気通信研究所入所．1995年豊橋技術科学大学工学部情報工
学系助教授，現在に至る．
博士（工学），システムプログラム，記号処理の研究に従事．ACM，ソフトウェア科
学会，電子情報通信学会，
計量国語学会各会員．
}

\bioreceived{受付}
\biorevised{再受付}
\bioaccepted{採録}

\end{biography}



\end{document}


