\documentstyle[epsbox,jnlpbbl]{jnlp_j_b5}

\setcounter{page}{79}
\setcounter{巻数}{5}
\setcounter{号数}{1}
\setcounter{年}{1998}
\setcounter{月}{1}
\受付{1997}{6}{20}
\再受付{1997}{8}{22}
\採録{1997}{10}{24}

\setcounter{secnumdepth}{2}

\title{単語の位置情報に基づくコーパスからの\\
コロケーションの自動抽出}
\author{小田 裕樹\affiref{TU} \and 北 研二\affiref{TU}}

\headauthor{小田 裕樹・北 研二}
\headtitle{単語の位置情報に基づくコーパスからのコロケーションの自動抽出}

\affilabel{TU}{徳島大学工学部 知能情報工学科}
{Faculty of Engineering, Tokushima University}

\jabstract{
コロケーションの知識は，単語間の共起情報を与える言語学的に
重要な知識源であり，機械翻訳をはじめとする自然言語処理において，
重要な意味をもっている．
本論文では，コーパスからコロケーションを自動的に抽出する
新しい手法を提案する．提案する手法では，コーパス中の各単語の
位置情報を用いて，任意の文中のコロケーションを連続型・不連続型
の別に抽出する．
また，提案した自動抽出法を用いて，ATR対話コーパスから
コロケーションを抽出する実験を行った．
本実験で得られた結果は，連続型・不連続型コロケーションともに
重要な表現が抽出されており，提案した抽出法の有効性を示すこと
ができた．}

\jkeywords{コーパス，コロケーション，決定性有限オートマトン，位置情報}

\etitle{Automatically Extracting Collocations\\
Based on Words Position Information\\
in Corpora}
\eauthor{Hiroki Oda \affiref{TU} \and Kenji Kita\affiref{TU}} 

\eabstract{
Collocations, which are cohesive and recurrent word clusters,
play an \mbox{important} role in many natural language
application systems.
In this paper, we present a set of new techniques
for automatically identifying or extracting collocations
from corpora.
These techniques are based on words position information,
and produce a wide range of collocations,
including continuous or discontinuous collocations.
The effectiveness has been confirmed by evaluation experiments
using the ADD (ATR Dialogue Database) corpus.}

\ekeywords{corpus, collocations, deterministic finite automata,
position information}

\begin{document}
\maketitle


\section{はじめに}

コロケーション(Collocation)の知識は，単語間の共起情報を
与える言語学的に重要な知識源であり，機械翻訳をはじめとする
自然言語処理において，重要な意味をもっている．
コロケーションとは，テキスト中に頻繁に出現する単語の組み合わせで
あり，言語的あるいは慣用的な表現であることから，様々な形態が
考えられる．その例として，
``{\it Thank you very much}''や``{\it I would like to}''のような
単語が連続している表現と，``{\it not only 〜 but (also) 〜}''や
``{\it not so much 〜 as 〜}''のように単語間にギャップを持つ
不連続な表現が存在する．これらの表現はそれを一つのまとまった
単位として処理する必要があり，
その知識は機械翻訳への適用をはじめとして，音声・文字認識に
おける認識結果の誤り訂正\cite{Omoto96}や，
第二外国語を学習する際の手助けとするような言語学習や言語教育の
分野にも適用できる\cite{Kita94a,Kita97}．

以上のように，コロケーションの収集・整理は言語学的にも機械処理の
面からも有益であるため，その収集の仕方は自然言語処理における
重要な課題である．
しかし，人手による収集では膨大な時間と手間が必要となり，
かつコロケーションの定義が曖昧であるためにその網羅性・
一貫性にも問題が生じる．

これらの点から，コロケーションを自動的に抽出・収集する方法として，
相互情報量を用いた方法\cite{Church90}，仕事量基準を用いた方法
\cite{Kita93,Kita94b}，$n$-gramを用いた方法\cite{Nagao94}，
2つの単語の位置関係の分布を考慮する方法\cite{Smadja93}
をはじめとして様々な方法が提案されている
\cite{Shinnou94,Shinnou95a,Shinnou95b}．
しかし，従来の方法の多くは連続したコロケーションを抽出の対象としており，
不連続なコロケーションの抽出に関する研究はごく少数であった
\cite{Omoto96,Ikehara95}．

本論文では，単語の位置情報に基づき，連続型および不連続型の
二種類のコロケーションをコーパスから自動的に抽出する方法を
提案する．提案する手法は，コーパス全体からコロケーションを
抽出するだけではなく，指定された任意の範囲
(たとえば，何番目の文，または何番目から何番目の文の中)
にあるコロケーションを同定することができる．
また，提案する手法は，言語に依存しない(言語独立の)方法であり，
機械翻訳等への様々な活用が期待できる．

以下，本論文の
第\ref{Sec:extract_abstract}節では，提案する手法の基本的な考え方と
その特徴について述べる．本手法では，単語の位置情報をとらえるために，
コーパス・データを受理する有限オートマトンを用いるが，
第\ref{Sec:alergia_algorithm}節では，我々の用いたオートマトン学習
アルゴリズムであるALERGIAアルゴリズムについて概略を述べる．
第\ref{Sec:extract_algorithm}節では，
第\ref{Sec:extract_abstract}節で述べた考えに基づく位置情報を
用いた自動抽出アルゴリズムを提案する．第\ref{Sec:experiment}節では，
本手法をATR対話コーパスに適用した結果を示し評価を行う．

\section{コロケーションの自動抽出の考え方と特徴}
\label{Sec:extract_abstract}

従来，コロケーションは人手によって収集・整理されてきており，
自動的に抽出する方法についての研究も，その多くは
連続したコロケーションの抽出に限定されていた．そこで本論文では，
そのような限定をせずにすべてのコロケーションを自動的に抽出する
手法として，コーパス中の単語の位置情報を用いる方法を提案する．

\subsection{コロケーションとは}
\label{Subsec:def_collocation}

コロケーションは，一般には，任意の再現する単語の組み合わせ
(arbitrary and recurrent word combination)として定義される
\cite{Benson90,Benson86,Smadja93}．
しかし，この定義だけでは余りに漠然としているため，本論文では，
コロケーションを以下のようにとらえる．
\begin{itemize}
\item[1.] コロケーションは，テキスト中で頻繁に出現する(繰り返し使われる)単語の
組み合わせで，同一文中に共起し，複数文にまたがらないものである．
\item[2.] コロケーションは，単語間の結び付きが強い単語の組み合わせであり，
これらは意味的なまとまりを構成する．また，コロケーションは，形態的な
面から，次の二つのタイプに分類することができる\cite{Abe97}．
\begin{itemize}
\item[(a)] 単語が隣接して強く結合して，他語の挿入や語の交換が通常なされない
表現．
\item[(b)] 隣接の度合が弱く，表現中に他語の挿入も許される表現．
\end{itemize}
本論文では，(a)のタイプのコロケーションを連続型コロケーション，
(b)のタイプのコロケーションを不連続型コロケーションと呼ぶ．
\end{itemize}

\subsection{コロケーションの自動抽出}
\label{Subsec:auto_extract}

\ref{Subsec:def_collocation}節の条件を満たすコロケーションを
自動的に抽出するために，本論文では，まずコーパス中での
出現頻度の高い単語列に着目する．しかし，
単に出現頻度の高い単語列を抽出するだけでは，意味的にまとまりの
ない断片的な単語列が多く抽出されるので，最長一致の原則\cite{Ikehara95}
を用いて，一度，コロケーションとみなされた単語の組み合わせが，
それ以後に分割されて処理されることを避ける．

また，以下のように，
連続型コロケーションと不連続型コロケーションは，別々に抽出する．
\begin{itemize}
\item[1.] コーパス中に複数回出現する単語列(連続型コロケーション)と，
複数回出現し，かつ出現ごとに隣接する単語が異なる単語を抽出する．
\item[2.] 上記1の単語列または単語がギャップを持って(離れて)複数回共起する
組み合わせが不連続型コロケーションである．
\end{itemize}
上の集計方法は，不連続型コロケーションが
連続型コロケーションに比べて，その存在数(出現回数)が少ないため，
出現回数をスコアとしてコロケーションを抽出した場合，不連続型
コロケーションは連続型コロケーションよりも，はるかに低いスコアとなり，
スコアのみにより，不連続なコロケーションを抽出するのは困難である
\cite{Omoto96}ことから，現実的な方法であると考える．

\subsection{単語の位置情報}
\label{Subsec:based}

まず，本手法の基礎となる，単語の``位置情報''について説明する．
コーパス中のある特定の場所にある単語$w$の位置を，
2項組\hspace{-0.2mm}$(i,j)$\hspace{-0.2mm}によって表す．
ここで，$i$は文番号(コーパス中の何番目の文であるか)を，
また$j$は単語番号(文中の何番目の単語であるか)を示している．
単語$w$はコーパス中の複数箇所に出現しえるので，
このような2項組のリストを考えることにより，
単語$w$がコーパス中のどこに出現するかを把握することができる．
以下では，2項組\hspace{-0.2mm}$(i,j)$\hspace{-0.2mm}のリストのことを，
単語$w$の出現位置表と呼ぶことにする．

一つ注意すべきことは，ある単語\hspace{-0.2mm}$w$\hspace{-0.2mm}に対し，必ずしも出現位置表を
一つだけ考える必要はないという点である．
もし，単語$w$が異なったコンテキストで用いられていれば，
コンテキストごとに単語$w$の出現位置表を用意してもよい．
従って，同じ単語$w$であっても，異なった出現位置表を持つ場合がある．
本論文では，単語$w$の出現するコンテキストをとらえるために，
有限オートマトンを用いる．
まず，コーパス中のすべての文を受理するような有限オートマトンを構成する．
このような有限オートマトンにおいて，
単語$w$による状態遷移はオートマトン中の複数箇所に現れる可能性があるので，
各状態遷移ごとに単語$w$の出現位置表を作成する．
なお，本論文では，コーパスから有限オートマトンを構成するために，
ALERGIAアルゴリズム\cite{Carrasco94}を用いる
(\ref{Sec:alergia_algorithm}節参照)．

本論文における自動抽出法では，ある文中の単語の組み合わせが
他の文にも出現するものをその文に含まれるコロケーション
(の候補)とみなす．
単語の出現位置表を用いることにより，単語間の位置関係をとらえることが
できるので，ある単語がコーパス中の複数の文に出現している場合，
その各々の文の中での組み合わせを考慮するだけで，
複数の文に対して同じ組み合わせで出現しているものを知ることができる．

\section{ALERGIAアルゴリズムによる決定性確率有限オートマトンの構成}
\label{Sec:alergia_algorithm}

\ref{Subsec:based}節で述べたように，単語の出現するコンテキストを
とらえるために，本論文では有限オートマトンを用いる．我々は，
コーパス・テキストを受理するような有限オートマトンを
構成するために，ALERGIAアルゴリズム\cite{Carrasco94}を用いた．
ALERGIAアルゴリズムは，状態マージング手法を用いて，
学習データに対し最適な構造を持つオートマトンを自動的に
構成する．また，ALERGIAアルゴリズムでは，本節(3)で述べるように，
状態の等価判定を行い，等価な状態をマージすることで，オートマトンを
構成する．等価判定を変化させることで，本手法で抽出される
単語の組み合わせの結び付きの強さを考慮できるのではないかと考える．
以下で，ALERGIAアルゴリズムの概要を述べる．また，図\ref{Fig:pta2dsfa}に，
ALERGIAアルゴリズムを用いて，学習データ\(S=\{110,\lambda,\lambda,
\lambda,0,\lambda,00,00,\lambda,\lambda,\lambda,10110,\lambda,\lambda,100\}\)
($\lambda$は空列)に対する決定性確率有限オートマトンを構成する例を示す．
図\ref{Fig:pta2dsfa}(a)から(d)までの各状態の中には状態番号を記載し，
各状態の下には入力記号列がその状態をたどった回数(左)とその状態で受理
された回数(右)を付与している．また，各状態遷移には``遷移記号[状態遷移を
行った回数]''を付与した．
\begin{figure}[hbt]
\begin{center}
\epsfile{file=kita1.eps,width=0.80\textwidth}
\end{center}
\caption{ALERGIAアルゴリズムによる決定性確率有限オートマトンの構成}
\label{Fig:pta2dsfa}
\end{figure}

\subsubsection*{(1) 接頭木アクセプタの作成}

学習データから接頭木アクセプタ(Prefix Tree Acceptor; PTA)を作成する．
ここで，接頭木アクセプタとは，学習データ中の入力記号列のみを受理することが
可能な決定性有限オートマトンであり，初期状態を根とした木構造となる
(図\ref{Fig:pta2dsfa}(a)参照)．

\subsubsection*{(2) 状態遷移確率の計算}

\hspace{-0.2mm}$n_{i}$\hspace{-0.2mm}を学習データが接頭木アクセプタの状態\hspace{-0.2mm}$q_{i}$\hspace{-0.2mm}を訪れた
回数とする．もし学習データが状態\hspace{-0.2mm}$q_{i}$\hspace{-0.2mm}で受理されれば，受理された
データの個数を \hspace{-0.2mm}$f_{i}(\sharp)$\hspace{-0.2mm}とする．状態\hspace{-0.2mm}$q_{i}$\hspace{-0.2mm}で受理されなければ，
次の状態へ遷移するが，このとき状態遷移\hspace{-0.2mm}$\delta_{i}(a)$\hspace{-0.2mm}
(状態\hspace{-0.2mm}$q_{i}$\hspace{-0.2mm}で入力記号$a$がきたときの遷移)をたどった回数を
\hspace{-0.2mm}$f_{i}(a)$\hspace{-0.2mm}とする．状態遷移\hspace{-0.2mm}$\delta_{i}(a)$\hspace{-0.2mm}の遷移確率\hspace{-0.2mm}$P_{i}(a)$\hspace{-0.2mm}は，
次のようにして求められる．
\vspace{-0.5mm}\begin{equation}
P_{i}(a)=\frac{f_{i}(a)}{n_{i}}
\end{equation}
\vspace{-0.5mm}
なお，\hspace{-0.2mm}$P_{i}(\sharp)$\hspace{-0.2mm}は，入力記号列が状態\hspace{-0.2mm}$q_{i}$\hspace{-0.2mm}で受理される確率を
表している．

\subsubsection*{(3) 状態のマージ}

接頭木アクセプタの状態$q_{i}$と状態$q_{j}$が等価(\(q_{i} \equiv q_{j}\))で
あれば，これら2つの状態をマージする．ここで，状態$q_{i}$\hspace{-0.2mm}と状態$q_{j}$\hspace{-0.2mm}が
等価であるとは，すべての入力記号\(a \in \Sigma\)($\Sigma$は入力記号の集合)に
ついて，遷移確率$P_{i}(a)$と$P_{j}(a)$が等しく，遷移後の状態も等価である
ときをいう．すなわち，
\begin{equation}
q_{i} \equiv q_{j}
	\Longleftrightarrow
		\forall a \in \Sigma
			\left\{
			\begin{array}{l}
				P_{i}(a)=P_{j}(a)\\
				\delta_{i}(a) \equiv \delta_{j}(a)
			\end{array}
			\right.
\end{equation}

状態の等価性を判断する場合，学習データに対する統計的な揺れを伴うので，
二つの遷移確率の差が許容範囲にあるときに等価であるとする．
いま，
確率$p$のベルヌイ確率変数があり，$n$回の試行のうち$f$回この事象が起こった
とすると，次式が成り立つ．
\begin{equation}
P \left( \left| p - \frac{f}{n} \right| <
	\sqrt{\frac{1}{2n} \log \frac{2}{\alpha}} \right)
		\geq
			1 - \alpha
\end{equation}
ALERGIAアルゴリズムでは，学習データから推定された二つの遷移確率の差が
信頼範囲\(\sqrt{\frac{1}{2n} \log \frac{2}{\alpha}}\)の和の範囲内に
あるときに，二つの状態を確率的に等価であるとしている．すなわち，
状態$q_{i}$\hspace{-0.2mm}と状態$q_{j}$\hspace{-0.2mm}が等価であるとは，
すべての入力記号\(a \in \Sigma\)について，次式が成り立つことである．
\begin{equation}
\left| \frac{f_{i}(a)}{n_{i}} - \frac{f_{j}(a)}{n_{j}} \right|
	\leq
		\sqrt{\frac{1}{2} \log \frac{2}{\alpha}}
			\left(
				\frac{1}{\sqrt{n_{i}}} + \frac{1}{\sqrt{n_{j}}}
			\right)
\label{Eq:eq_state}
\end{equation}

図\ref{Fig:pta2dsfa}(b)は図\ref{Fig:pta2dsfa}(a)の状態$q_1$\hspace{-0.2mm}と状態$q_2$\hspace{-0.2mm}を
マージした後のオートマトンである．その後，順に状態をマージして，
最終的に図\ref{Fig:pta2dsfa}(e)の決定性確率有限オートマトンが得られる．
図\ref{Fig:pta2dsfa}(e)の状態の中にはその状態の受理確率を記載し，
各状態遷移には``遷移記号[遷移確率]''を付与している．

\section{単語位置情報に基づく自動抽出アルゴリズム}
\label{Sec:extract_algorithm}

\ref{Sec:extract_abstract}節で述べた考えに基づいた，
コロケーションの自動抽出アルゴリズムを，以下で説明する．
まず，コーパスを\(W=s_0 s_1 \ldots s_N\)と表す．
$s_n$はコーパス中の$n$番目の文であり，$N+1$がコーパス中の
文の総数である．また，コーパス中の文$s_n$は，
\(s_n = w_n^0 \ldots w_n^{T(n)}\)と表す．ここで，$w_n^t$は，
文$s_n$中の$t$番目の単語であり，\hspace{-0.2mm}$T(n)+1$\hspace{-0.2mm}が文の長さ(単語長)である．
以下では，コーパス中の単語の位置を表すのに，``文番号''および
``単語番号''という用語を用いる．文番号とはコーパス中の文に対して
先頭から順に付けた番号であり，単語番号とは各々の文の中で先頭から
順に付けた単語の出現番号である．すなわち，文\hspace{-0.2mm}$s_n$\hspace{-0.2mm}中の単語$w_n^t$に
対しては，文番号は$n$，単語番号は$t$となる．

\subsection*{手順(1) : 単語の出現位置表の作成}

\hspace{0.5mm}ALERGIA\hspace{0.5mm}アルゴリズムを用いて，コーパス\(W=\{s_n; 0\le n \le N\}\)を
受理する決定性確率有限オートマトンを構成する．
決定性確率有限オートマトンでは，各文\hspace{-0.2mm}$s_n$\hspace{-0.2mm}に対して状態遷移が
一意に定まる．各状態遷移に対して，単語の出現位置表を作成する
(図\ref{Fig:inlearn}参照)．なお，出現位置表とは，すでに
\ref{Subsec:based}節で述べたように，各単語のコーパス中の出現位置を
まとめたものであり，出現位置は文番号と単語番号の2項組で表される．
位置情報は\(n=0,1,\ldots N\)，\(t(n)=0,\ldots T(n)\)の順に
記録する．
\begin{figure}[hbt]
\begin{center}
\epsfile{file=kita2.eps,width=0.60\textwidth}
\end{center}
\caption{コーパス$W$中の各単語の出現位置の記録}
\label{Fig:inlearn}
\end{figure}
図\ref{Fig:edgeattr}は，図\ref{Fig:inlearn}の処理によって
作成された($W$中の)単語の出現位置表を示している．各表は文$s_0$の
単語``もしもし''，``通訳国際会議事務局''，``です''，``か''に
対応している．
\begin{figure}[hbt]
\begin{center}
\begin{footnotesize}
	\begin{minipage}[t]{3cm}
	\begin{tabular}[t]{|r|r|}
	\multicolumn{2}{c}{\bf もしもし}\\
	\hline
	\multicolumn{1}{|c|}{\bf 文} & \multicolumn{1}{c|}{\bf 単語}\\
	\multicolumn{1}{|c|}{\bf 番号} & \multicolumn{1}{c|}{\bf 番号}\\
	\hline
	0 & 0\\
	73 & 0\\
	116 & 0\\
	169 & 0\\
	236 & 0\\
	270 & 0\\
	353 & 0\\
	429 & 0\\
	484 & 0\\
	512 & 0\\
	\end{tabular}
	\end{minipage} \quad
	\begin{minipage}[t]{3cm}
	\begin{tabular}[t]{|r|r|}
	\multicolumn{2}{c}{\bf 通訳国際会議}\\
	\multicolumn{2}{c}{\bf 事務局}\\
	\hline
	\multicolumn{1}{|c|}{\bf 文} & \multicolumn{1}{c|}{\bf 単語}\\
	\multicolumn{1}{|c|}{\bf 番号} & \multicolumn{1}{c|}{\bf 番号}\\
	\hline
	0 & 1\\
	\hline
	\end{tabular}
	\end{minipage} \quad
	\begin{minipage}[t]{3cm}
	\begin{tabular}[t]{|r|r|}
	\multicolumn{2}{c}{\bf です}\\
	\hline
	\multicolumn{1}{|c|}{\bf 文} & \multicolumn{1}{c|}{\bf 単語}\\
	\multicolumn{1}{|c|}{\bf 番号} & \multicolumn{1}{c|}{\bf 番号}\\
	\hline
	0 & 2\\
	1 & 2\\
	2 & 5\\
	4 & 2\\
	7 & 8\\
	13 & 9\\
	14 & 8\\
	15 & 3\\
	16 & 22\\
	17 & 4\\
	18 & 9\\
	19 & 9\\
	22 & 10\\
	23 & 27\\
	31 & 6\\
	33 & 6\\
	33 & 12\\
	\multicolumn{2}{|c|}{$\vdots$}\\
	73 & 2\\
	\multicolumn{2}{|c|}{$\vdots$}\\
	\end{tabular}
	\end{minipage} \quad
	\begin{minipage}[t]{3cm}
	\begin{tabular}[t]{|r|r|}
	\multicolumn{2}{c}{\bf か}\\
	\hline
	\multicolumn{1}{|c|}{\bf 文} & \multicolumn{1}{c|}{\bf 単語}\\
	\multicolumn{1}{|c|}{\bf 番号} & \multicolumn{1}{c|}{\bf 番号}\\
	\hline
	0 & 3\\
	3 & 9\\
	6 & 19\\
	10 & 2\\
	12 & 7\\
	14 & 9\\
	15 & 4\\
	18 & 10\\
	21 & 33\\
	22 & 19\\
	27 & 15\\
	31 & 7\\
	33 & 13\\
	\multicolumn{2}{|c|}{$\vdots$}\\
	73 & 3\\
	\multicolumn{2}{|c|}{$\vdots$}\\
	\end{tabular}
	\end{minipage}
\end{footnotesize}
\end{center}
\caption{$W$中の文$s_0$の単語に関する出現位置表}
\label{Fig:edgeattr}
\end{figure}

なお，ALERGIAアルゴリズムの等価判定の信頼範囲を決定する\hspace{-0.2mm}$\alpha$\hspace{-0.2mm}の
値によって，構築されるオートマトンの規模は変化する．様々な\hspace{-0.2mm}$\alpha$\hspace{-0.2mm}の
値に対するオートマトンによって，上の手順で作成される出現位置表の
総数\((=状態遷移の総数)\)と各表の内容が異なる．各表に記録される出現位置
の2項組の数は状態遷移の回数である．

\subsection*{手順(2) : 単語共有表の作成}

手順(2)から手順(6)にかけて，コーパス中の文$s_n$中の
コロケーションを同定・抽出する処理を行う．
手順\hspace{0.6mm}(1)で\hspace{0.6mm}作成された，単語の出現位置表から，文$s_n$の
単語共有表を作成する(図4
参照)．
\begin{figure}[hbt]
\begin{center}
\begin{footnotesize}
	\begin{minipage}[t]{5cm}
	\begin{tabular}[t]{|c|c|c|}
	\multicolumn{3}{c}{\bf 文$s_0$の単語共有表}\\
	\hline
	\multicolumn{1}{|c|}{\bf 文番号} & \multicolumn{1}{c|}{\bf 単語番号} & \multicolumn{1}{c|}{\bf 位置番号}\\
	\hline
	14 & 8 & 2\\
	14 & 9 & 3\\
	15 & 3 & 2\\
	15 & 4 & 3\\
	18 & 9 & 2\\
	18 & 10 & 3\\
	31 & 6 & 2\\
	31 & 7 & 3\\
	33 & 6 & 2\\
	33 & 12 & 2\\
	33 & 13 & 3\\
	\multicolumn{3}{|c|}{$\vdots$}\\
	73 & 0 & 0\\
	73 & 2 & 2\\
	73 & 3 & 3\\
	\multicolumn{3}{|c|}{$\vdots$}\\
	\end{tabular}
	\end{minipage} \quad
	\begin{minipage}[t]{5cm}
	\begin{tabular}[t]{|c|c|c|}
	\multicolumn{3}{c}{\bf 下記のものは単語共有表には}\\
	\multicolumn{3}{c}{\bf 含めない}\\
	\hline
	\multicolumn{1}{|c|}{\bf 文番号} & \multicolumn{1}{c|}{\bf 単語番号} & \multicolumn{1}{c|}{\bf 位置番号}\\
	\hline
	0 & 0 & 0\\
	0 & 1 & 1\\
	0 & 2 & 2\\
	0 & 3 & 3\\
	1 & 2 & 2\\
	2 & 5 & 2\\
	3 & 9 & 3\\
	4 & 2 & 2\\
	6 & 19 & 3\\
	7 & 8 & 2\\
	10 & 2 & 3\\
	12 & 7 & 3\\
	13 & 9 & 2\\
	16 & 22 & 2\\
	17 & 4 & 2\\
	19 & 9 & 2\\
	21 & 33 & 3\\
	22 & 10 & 2\\
	23 & 27 & 2\\
	\end{tabular}
	\end{minipage}
\end{footnotesize}
\end{center}
\caption{コーパス$W$中の文$s_0$の単語共有表(左表)と単語共有表には含めない出現位置(右表)}
\label{Fig:wordkyofile}
\end{figure}
文$s_n$の単語共有表とは，文$s_n$中のすべての単語\hspace{-0.2mm}\(w_n^0,\ldots w_n^{T(n)}\)\hspace{-0.2mm}
(の状態遷移)の出現位置表を文番号の小さい順にマージして一つの表に
まとめた(文$s_n$に対して固有の)ものである．なお，
図\ref{Fig:wordkyofile}において\hspace{-0.2mm}``位置番号''\hspace{-0.2mm}と
あるものは，マージする前に，各単語の出現位置表に文$s_n$の
単語番号$t(n)$を付けて，文$s_n$の単語共有表の情報として付加したものである．
つまり，文$s_n$の単語共有表の中の情報は``文番号(出現する文の番号$m$)''，
``単語番号(文$s_m$中の単語位置)''，``位置番号(文$s_n$中の単語位置)''の
3項組となる．以下では，単語共有表の一行(3項組)を
出現位置レコードと呼ぶ．ただし，次のものは文$s_n$の単語共有表に含めない．
\begin{itemize}
\item[1.] 文番号が$n$である出現位置レコード．
\item[2.] マージしたときにその文番号を持つ出現位置が一つしかない
出現位置レコード．たとえば，図\ref{Fig:edgeattr}の出現位置表において，
文番号$1$や$2$を持つ出現位置レコードがこれに該当する．
\end{itemize}
上記のものを含めない理由は，手順(3)と手順(5)で，文$s_n$の単語共有表を
参照して，他の文にも出現する文$s_n$\hspace{-0.2mm}中の単語の組み合わせを探すために，
文$s_n$\hspace{-0.2mm}中の単語が複数個出現する他の文番号を持つ出現位置レコードのみを，
文$s_n$の単語共有表に残せばよいからである．

\subsection*{手順(3) : 二文中に共通して出現するパターンの抽出}

手順(3)から手順(6)では，他の文にも出現する文$s_n$\hspace{-0.2mm}中の
パターンを抽出するために，二文(文$s_n$と\hspace{-0.2mm}他の文)中
で共通して現れるパターンを抽出する処理(手順(3)，手順(5))を繰り返し，
抽出されるパターンを収集する(手順(4)，手順(6))．手順(3)と手順(4)では，
抽出・収集するパターンは単語または単語列であり，
手順(5)と手順(6)では，抽出・収集するパターンはギャップを持った
単語の組み合わせである(\ref{Subsec:auto_extract}節参照)．

手順(2)で作成した文$s_n$の単語共有表を，同一文番号を持つ
出現位置レコードごとにまとめ，分割する(図\ref{Fig:tst2sp}参照)．
\begin{figure}[hbt]
\begin{center}
\epsfile{file=kita5.eps,width=0.70\textwidth}
\end{center}
\caption{コーパス$W$中の文$s_0$から抽出された出現パターン}
\label{Fig:tst2sp}
\end{figure}
こうして得られた分割表のうち，文番号が$m$であるものをとりだし，
次の抽出規則を用いて出現パターンを抽出する．
ここで抽出される出現パターンは，文$s_n$と文$s_m$の両者に現れるパターン
となる．
\begin{itemize}
\item[{\bf 抽出規則1~:~}] 二つの出現位置レコード$r_1$と$r_2$($\neq r_1$)の
位置番号(文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の単語位置)を${\cal P}_1$，${\cal P}_2$と表し，
単語番号(文$s_m$中の単語位置)を${\cal W}_1$，${\cal W}_2$と表すと，
\begin{itemize}
\item[1.] \({\cal P}_1 + 1 = {\cal P}_2\)かつ\({\cal W}_1 + 1 = {\cal W}_2\)
のとき，``[$r_1$の単語][$r_2$の単語]''
\item[2.] \({\cal P}_2 + 1 = {\cal P}_1\)かつ\({\cal W}_2 + 1 = {\cal W}_1\)
のとき，``[$r_2$の単語][$r_1$の単語]''
\end{itemize}
のように前後に単語を結び付け，結び付いた単語列(二単語以上のパターン)を
一つの出現パターンとする．
\item[{\bf 抽出規則2~:~}] 抽出規則1を満たす$r_2$がない場合，``[$r_1$の単語]''を
一つの出現パターンとする．
\end{itemize}
上記の抽出規則により得られる出現パターンはコーパス中に最低でも
2回出現するために，文$s_n$に含まれるコロケーション(またはその要素)
となる可能性がある．
以上の処理を，
文$s_n$の単語共有表のすべての分割表に対して行い，
出現パターンをすべて抽出する．

\subsection*{手順(4) : 単語パターンの収集と連続型コロケーションの抽出}

手順(3)で抽出された出現パターン群から，
位置番号の値のみの比較処理で，文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}の単語パターンを収集する
(図\ref{Fig:subpdel}参照)．ここで，単語パターンとは，文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の単語(列)が
一つのまとまりとして他の文にも出現するものである．
\begin{figure}[hbt]
\begin{center}
\epsfile{file=kita6.eps,width=0.70\textwidth}
\end{center}
\vspace{-3mm}
\caption{コーパス$W$中の文$s_0$の部分パターンの削除}
\label{Fig:subpdel}
\vspace{-2mm}
\end{figure}

抽出された出現パターン群から，次の収集規則により，既に抽出されたパターンに
包含される断片的なパターンを削除する．
\begin{itemize}
\item[{\bf 収集規則~:~}] 文$s_n$中で，あるパターンが抽出された場所からは，
その部分パターンを抽出しないとし，部分パターンを削除する．
\end{itemize}

上の収集規則を満たすために問題となるのは，出現パターンが
複数個抽出されたときに，複数の出現パターンが同じ位置番号の値の
単語を持つ場合である．その場合，
出現パターン$a$の最小の位置番号を${\cal P}_{min}(a)$，
最大の位置番号を${\cal P}_{max}(a)$とすると，もし$a$の
位置番号(列)が最大値・最小値の比較によって出現パターン$b$(\(\neq a\))の
位置番号列に包含される(\({\cal P}_{min}(b) \leq {\cal P}_{min}(a)\)
かつ\({\cal P}_{max}(a) \leq {\cal P}_{max}(b)\))ならば$a$を削除する．
単語パターンは文$s_n$中のパターンの
位置のみで判定して収集し，以後，位置番号の情報のみを必要とする．
たとえば，複数の出現パターンの位置番号列が全く
一致する場合(\({\cal P}_{min}(a)={\cal P}_{min}(b)\)かつ
\({\cal P}_{max}(a)={\cal P}_{max}(b)\))は，同一単語パターンである
ので，どれか一つを残し，削除すればよい(図\ref{Fig:subpdel}(1)(3)(5))．

収集規則で削除されずに残された出現パターンを文$s_n$の単語パターンとし，
単語パターンの集合を$P_{s_n}$とする．
$P_{s_n}$中の単語列(二単語以上のパターン)を文$s_n$中の連続型
コロケーションとして抽出する．
たとえば，コーパス$W$の文$s_0$の\hspace{-0.1mm}$P_{s_0}$\hspace{-0.1mm}からは``です か''が抽出される．
また，$P_{s_n}$中の単語パターンは，文$s_n$中の不連続型コロケーションの
構成要素となる．

\subsection*{手順(5) : 二文中に共通して出現する不連続型コロケーションの抽出}

手順(4)で作られた集合\hspace{-0.1mm}$P_{s_n}$\hspace{-0.1mm}中の単語パターンは，
文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の単語(列)が，コーパス中の他の文にも
出現するパターンであり，文$s_n$における単語のまとまりと考える
ことができる．\ref{Subsec:auto_extract}節で述べたように，
文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}に含まれる不連続型コロケーションは，
集合$P_{s_n}$中の単語パターンが，文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}の中と同じ組み合わせ
(同順)で他の文中でもギャップを持って共起するものである．

文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中のどのような不連続な単語の組み合わせが他の文に
出現しているかを知るために，再度，文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中と同じ単語の組み合わせが
出現している他の文に対して処理を行う．
文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}の単語共有表の分割表で，文番号が\hspace{-0.1mm}$m'$\hspace{-0.1mm}であるものを
とりだす．文番号\hspace{-0.1mm}$m'$\hspace{-0.1mm}の分割表から，手順(3)と同様の処理で抽出される
二文中に共通する出現パターンが，位置番号列の比較によって，
$P_{s_n}$中の単語パターンと一致するかどうかを調べる．
もし，文$s_{m'}$との間で複数の($P_{s_n}$中の)単語パターンが
共通して出現していて，かつ両方の文で同順でギャップを持って
現れている場合，その単語パターンの組み合わせが文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}と文$s_{m'}$に
共通して現れる不連続型コロケーションである．
以下で，処理の詳細な説明を述べる．

\subsubsection*{手順(5.1) : 要素の認定}

手順(3)で作成された文$s_n$の単語共有表の分割表のうち，
文番号が$m'$であるものをとりだし，二文(文$s_n$と文$s_{m'}$)中に
共通して出現するパターンを抽出する．
ただし，この手順では，抽出された出現パターンから，次の条件を
満たさないパターンを削除する(図\ref{Fig:idenexam}参照．ただし，
$P_{s_0}$は図\ref{Fig:subpdel}のものを用いている)．
\begin{itemize}
\item[{\bf 条件1~:~}] $P_{s_n}$中にある単語パターンと
位置番号(列)が一致するパターンであること．
\item[{\bf 条件2~:~}] 条件1を満たさない出現パターンをすべて削除した後，
出現パターンが，``位置番号(文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の位置)''と``単語番号
(文$s_{m'}$中の位置)''ともに不連続な関係が
成立する他の出現パターンを持つものであること．
\end{itemize}
\begin{figure}[hbt]
\begin{center}
\epsfile{file=kita7.eps,width=0.90\textwidth}
\end{center}
\caption{コーパス$W$中の文$s_0$に含まれる不連続型コロケーションの要素の認定}
\label{Fig:idenexam}
\end{figure}

条件1は，出現パターンの最小位置番号と最大位置番号が，$P_{s_n}$中
にある単語パターンの最小位置番号と最大位置番号と完全に一致する
場合のみ成立する．たとえば，図\ref{Fig:idenexam}(a)の
出現パターン2と図\ref{Fig:idenexam}(b)の出現パターン2は，
図\ref{Fig:subpdel}の$P_{s_0}$中の単語パターン1と一致し，
図\ref{Fig:idenexam}(b)の出現パターン1は図\ref{Fig:subpdel}の
$P_{s_0}$中の単語パターン2と一致するため，条件1を満たす．
しかし，図\ref{Fig:idenexam}(a)の出現パターン1は条件1を満たさない．
次に，条件1を満たす出現パターンが一つしか存在しない場合は，
条件2で比較対象となる他の出現パターンがないため，このパターンは削除する
(図\ref{Fig:idenexam}(a)の出現パターン2)．
もし条件1を満たす出現パターンが複数ある場合，ある出現
パターンに対して，位置番号と単語番号が共に不連続な関係が成立する
他の出現パターンを探す．
なお，条件2の不連続な関係は，次の不連続条件により判定できる．ここで，
条件2の判定の対象となる出現パターンを$a$，比較対象の他の出現パターンを
$b$とする．また，${\cal W}_{min}(a)$を$a$の最小単語番号，
${\cal W}_{max}(a)$を$a$の最大単語番号とする．最小位置番号と
最大位置番号は，手順(4)と同様，${\cal P}_{min}(a)$と${\cal P}_{max}(a)$
で表す．
\begin{itemize}
\item[{\bf 不連続条件A~:~}] \({\cal P}_{min}(a)-1 > {\cal P}_{max}(b)\)
かつ\({\cal W}_{min}(a)-1 > {\cal W}_{max}(b)\)
\item[{\bf 不連続条件B~:~}] \({\cal P}_{max}(a)+1 < {\cal P}_{min}(b)\)
かつ\({\cal W}_{max}(a)+1 < {\cal W}_{min}(b)\)
\end{itemize}
不連続条件Aまたは不連続条件Bの一方を満たす場合，パターン$a$と
パターン$b$の間に
位置番号と単語番号とで共に不連続な関係が成立する．
二つの不連続条件を用いて条件2を満たさない出現パターンを削除する．
図\ref{Fig:idenexam}(b)の場合，出現パターン1と出現パターン2の間には，
位置番号(文$s_0$中の位置)と単語番号(文$s_{73}$中の位置)共に不連続な
関係が成立する(不連続条件を満たす)ため，二つのパターンはともに条件2を満たす．

条件1と条件2を共に満たす出現パターン($P_{s_n}$中の単語パターン)が，
文$s_n$に含まれる不連続型コロケーションの要素となる．つまり，
そのパターンを共有する文$s_{m'}$(図\ref{Fig:idenexam}(b)の
場合は\(m'=73\))と，文$s_n$には同じ不連続な単語の組み合わせが出現する．
条件1と条件2を共に満たす出現パターンがある場合，次の手順(5.2)の
処理を行い，二文中で共通する不連続型コロケーションを抽出する．

\subsubsection*{手順(5.2) : 多分木の構築}

手順(5.1)で抽出された文$s_n$と文$s_{m'}$で共通して出現する
出現パターンのうちの一つを$a$としたときに，不連続条件Aを
満たす$b$を持たない(両方の文で，その出現パターンより前の位置には
他の出現パターンが出現していない)出現パターンが，
文$s_n$と文$s_{m'}$との間で共通して現れる不連続型コロケーションの
先頭の要素である．先頭の要素である
出現パターンすべてに対して，先頭の要素ではない(両方の文で，ある
出現パターンの後に出現している)出現パターンを
つないで，先頭の出現パターンを根とした多分木を構成する．
以下にその多分木の構築について述べる．

最初に，先頭の要素である出現パターンを各々別の木構造の
根とする．各々の根に対してつなぐことのできる出現
パターンは，根を$a$としたときに不連続条件Bが成立する出現パターン$b$
のみである．このとき，$b$は根$a$の子孫となる．
つまり，木構造の各々の節の出現パターンを$a$としたときに，
\begin{itemize}
\item 不連続条件Bを満たす出現パターン$b$が節$a$の子孫である．
\item あるいは，不連続条件Aを満たす出現パターン$b$が節$a$の祖先である．
\end{itemize}
という条件を満たし，木構造が根のみである場合は単純に根の子として
直接つなげればよい．しかし，既に根以外の節がある場合は，
次のようにしてパターンを多分木につなげていく(図\ref{Fig:ctree}参照)．
\begin{itemize}
\item[1.] 節$X$の子孫であり，かつ節$X$が子パターンを持っていない場合，
節$X$の子としてつなげる．
\item[2.] 節$X$\hspace{-0.1mm}の子孫であり，かつ節$X$\hspace{-0.1mm}の子の祖先でもある場合，
節$X$\hspace{-0.1mm}と節$X$\hspace{-0.1mm}の子の間に挿入する．
\item[3.] 節$X$\hspace{-0.1mm}の子孫であり，かつ節$X$\hspace{-0.1mm}の子すべてに対して
子孫でも祖先でもない場合，節$X\hspace{-0.1mm}$の子としてつなげる．
\end{itemize}
上の条件を，1，2，3の順に適用して多分木を構築する．
\begin{figure}[hbt]
\begin{center}
\epsfile{file=kita8.eps,width=0.50\textwidth}
\end{center}
\caption{多分木による不連続型コロケーションの抽出}
\label{Fig:ctree}
\vspace{4mm}
\end{figure}

以上の処理に基づいて，すべての出現パターンを各々多分木につなげる．
構成されたすべての多分木を根からすべての葉までたどった
各々の出現パターン($P_{s_n}$中の単語パターン)の
組み合わせが，文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}と文$s_{m'}$の間で共通して出現する文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の
不連続型コロケーションである．
たとえば，図\ref{Fig:idenexam}(b)の場合，文$s_0$と文$s_{73}$との間では，
出現パターン1``もしもし''が根となり，残る出現パターン2
``です か''を根につなぐことになる．``です か''は葉となるので，
根からたどったパターン``もしもし 〜 です か''が文$s_0$と文$s_{73}$で
共通して出現する不連続型コロケーションとして抽出される．

\subsection*{手順(6) : 不連続型コロケーションの収集}

手順(5)を文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}の単語共有表のすべての分割表に対して行い，抽出される
二文(文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}と他の文)中で共通して出現する$P_{s_n}$中の
単語パターンの組み合わせ(不連続型コロケーション)から，文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の
不連続型コロケーションを重複しないように収集する．

まず，抽出された各々の不連続型コロケーション$\alpha$の
先頭の要素である単語パターンと，不連続型コロケーション$\beta$
\((\neq \alpha)\)の先頭の要素である単語パターンの位置番号列を比較する．
位置番号列が一致した場合は，
次の要素同士を比較するという処理を繰り返す．すべての単語
パターンが一致すれば，\hspace{-0.2mm}$\alpha$\hspace{-0.1mm}と\hspace{-0.1mm}$\beta$\hspace{-0.1mm}を文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}の同じ
不連続型コロケーションとし，一致しない要素が一つでもあれば，
$\alpha$と$\beta$は文\hspace{-0.1mm}$s_n$\hspace{-0.1mm}中の異なる不連続型コロケーションとする．

\vspace{-2mm}
\subsection*{手順(7) : コロケーションの集計}

コーパス中のすべての文に対して手順(2)から手順(6)の処理を行い，
各文に含まれる連続型および不連続型コロケーション(の候補)を
手順(4)と手順(6)で抽出する．コーパス全体でのコロケーションを
集計するために，抽出された連続型および不連続型コロケーションを，
各々単語の組み合わせそのもの(文字列)の比較により，
同じものが抽出された回数を求める．

\vspace{1zh}

以上，手順(1)から手順(7)で，コロケーションの抽出法を述べてきた．
手順(1)と手順(7)のみで若干の文字列処理を必要とするほかは，すべて
整数(位置情報)の比較演算のみで行うことができる．
また，各文$s_n$\((0\le n\le N)\)が含むコロケーションの抽出処理は，
各々独立したものであり，分割処理を行うことで，
計算機の負荷を軽くすることができる．

本手法の処理の特徴を次に示す．
\begin{itemize}
\item[1.] 各単語間の距離値そのものを扱うのではなく，各単語の関係を``連続''か
``不連続''かのみとして考える．
\item[2.] 意味的にまとまりのない断片的な単語列の抽出を防ぐために，
池原ら\cite{Ikehara95}のように最長一致の原則により単語列の長いものだけを
抽出する．
\item[3.] 多分木を構築することで一度の処理で，すべての任意の長さの不連続型
コロケーションを抽出する．
\item[4.] コーパス全体に含まれるコロケーションだけではなく，任意の文
(または任意の範囲の文)に含まれるコロケーションを知りたい場合にも適する．
\item[5.] 処理するコーパスを大きくしたい場合，位置情報を追加または新規作成する
だけでよい．
\end{itemize}

\section{コロケーションの抽出実験}
\label{Sec:experiment}

\subsection{言語データ}

前節で述べた抽出法を用いて，コロケーションの
抽出実験を行った．
実験で使用したデータは
ATR自動翻訳電話研究所で作成されたATR対話データベース
(ATR Dialogue Database; ADD)から抜き出した．ADDは主に電話または
キーボードを介した目的指向型の対話に基づいて作成された話し言葉ないしは
疑似話し言葉に関する言語データベースであり，ADD中の各単語には
形態素解析等の様々な事前分析により，表記，ひらがなによる読み，
標準表現，品詞，活用型，音便等の属性が付与されている．
本実験では，単語の表記の部分のみを用いた．

なお，ADDには会話属性として領域(国際会議，旅行等)とメディア
(電話，キーボード等)がある．本実験では，国際会議に関する
キーボード会話データを用いた．キーボード会話とは，キーボードを使って入力し，
計算機を介してコミュニケーションを行う会話で，話し言葉に近い言い回しを
含んでいる．
使用したデータの大きさを表\ref{Tab:sourcedata}に示す．
\begin{table}[hbt]
\begin{center}
\caption{抽出実験に用いたデータの大きさ}
\label{Tab:sourcedata}
\begin{tabular}{lccc}
\hline
言語 & 文の数 & 異なり単語数 & 延べ単語数\\
\hline
日本語 & 6,025 & 3,799 & 71,780\\
\hline
英語 & 5,984 & 3,158 & 64,088\\
\hline
\end{tabular}
\end{center}
\end{table}

\subsection{実験結果}

実験結果を，表\ref{Tab:jcolalphaht209}(日本語データ)および
表\ref{Tab:ecolalphaht209}(英語データ)に示す(式(\ref{Eq:eq_state})
で，$\alpha\approx 1^{-10}$程度)．
実験結果より，連続型コロケーションと不連続型コロケーション
ともに意味的にまとまりのある単語の組み合わせを抽出している．
また，名詞間の共起関係(複合名詞句等)よりも，述語型の定型表現や
慣用表現を多く抽出している．

一方，従来の手法で抽出される連続型コロケーションは，
相互情報量を用いた方法では，主に複合語やコーパスのドメインに
依存した複合名詞句であり，仕事量基準を用いた方法では，
主に述語型の定型表現や慣用句である\cite{Kita94a,Kita94b}．
本手法は，出現頻度をスコアとして抽出したために，同じく出現頻度に
着目した仕事量基準を用いた方法と同じ傾向の表現を抽出し，
従来法に相当する結果を得た．

ただし，不連続型コロケーションは，全体として出現回数が少ないために，
一部にノイズ的なものを含んでいる．この原因の一つとして，
今回の実験で使用した言語データの規模が小さかったことがあげられる．
抽出された不連続型コロケーションの出現回数は，連続型コロケーション
の出現回数に比べ圧倒的に少なく，最も多い場合でも，日本語の場合に13回，
英語の場合に5回に過ぎない．このため，偶然共起したような
単語の組み合わせが，ノイズとして混入してしまった．
より大規模の言語データを用いれば，ノイズ的な単語の組み合わせの
混入を抑えることができると考えられる．

不連続型コロケーションの出現回数が少ないという点に関しては，
今回実験に用いた言語データの性質も関係していると思われる．
抽出実験に用いた言語データは会話，すなわち話し言葉であり，
話し言葉の性質として，断片的で不完全な表現や省略が多いことを
あげることができる．その結果として，話し言葉中には不連続型
コロケーションの絶対数が少ないのではないかと考えられる．
この点に関しては，新聞記事等の言語データを対象とした抽出実験を
行い，今回の結果と比較してみる必要があるだろう．これは，
今後の課題である．

\begin{table}[hbt]
\begin{center}
\caption{実験結果(日本語)}
\label{Tab:jcolalphaht209}
\begin{footnotesize}
\begin{tabular}{|lr||lr|}
\hline
\multicolumn{2}{|c||}{連続型コロケーション} & \multicolumn{2}{c|}{不連続型コロケーション}\\
\hline
\multicolumn{2}{|c||}{種類数 10,994} & \multicolumn{2}{c|}{種類数 8,293}\\
\hline
\multicolumn{2}{|c||}{延べ出現回数 26,308} & \multicolumn{2}{c|}{延べ出現回数 9,139}\\
\hline
\multicolumn{2}{|c||}{コロケーションと出現回数} & \multicolumn{2}{c|}{コロケーションと出現回数}\\
\hline
そう です か & 111 & はい 〜 です ね & 13\\
です か & 95 & はい 〜 です & 13\\
わかり まし た & 81 & の 〜 です & 10\\
そう です ね & 81 & の 〜 が & 7\\
です ね & 73 & はい 〜 が & 7\\
に は & 46 & の 〜 の & 6\\
はい わかり まし た & 46 & を 〜 に & 6\\
あ そう です か & 43 & もしもし 〜 です か & 5\\
です から & 43 & はい 〜 で ございます & 5\\
はい かしこまり まし た & 34 & はい 〜 に & 5\\
失礼 し ます & 32 & ええ 〜 が & 5\\
はい 第 １３ 回 コンピュータ国際会議事務局 です & 32 & え 〜 です か & 4\\
でしょ う か & 32 & も 〜 に & 4\\
はい では & 30 & は 〜 を & 4\\
それ は & 29 & あと 〜 の & 4\\
です が & 29 & を 〜 の & 4\\
失礼 いたし ます & 26 & ええ 〜 で & 4\\
はい 第 １３ 回 コンピュータ国際会議事務局 で ございます & 25 & ええ 〜 に & 4\\
お 世話 に なっ て おり ます & 25 & で 〜 を & 4\\
それ と & 25 & と 〜 です ね & 4\\
な ん です が & 25 & 表 〜 で & 4\\
はい 失礼 いたし ます & 24 & 普通 ページ 〜 表 & 4\\
です ので & 24 & 表 〜 ページ & 4\\
私 は & 23 & ２ 〜 で & 4\\
どうも ありがとう ございまし た & 23 & が 〜 です & 4\\
で ございます & 23 & の 〜 を & 4\\
に も & 23 & はい 〜 に は & 4\\
はい 失礼 し ます & 22 & はい 〜 て おり まし て & 4\\
でし たら & 21 & の 〜 から & 4\\
はい では 失礼 いたし ます & 21 & の 〜 と & 4\\
で は & 21 & あ 〜 です か & 3\\
よろしく お 願い し ます & 20 & ああ 〜 です か & 3\\
ああ そう です か & 20 & の 方 も 〜 の 方 も & 3\\
と 申し ます & 20 & 現在 〜 中 です & 3\\
はい そう です & 19 & 失礼 です が 〜 です か & 3\\
\hline
\end{tabular}
\end{footnotesize}
\end{center}
\end{table}

\begin{table}[hbt]
\begin{center}
\caption{実験結果(英語)}
\label{Tab:ecolalphaht209}
\begin{footnotesize}
\begin{tabular}{|lr||lr|}
\hline
\multicolumn{2}{|c||}{連続型コロケーション} & \multicolumn{2}{c|}{不連続型コロケーション}\\
\hline
\multicolumn{2}{|c||}{種類数 10,127} & \multicolumn{2}{c|}{種類数 5,910}\\
\hline
\multicolumn{2}{|c||}{延べ出現回数 24,692} & \multicolumn{2}{c|}{延べ出現回数 6,414}\\
\hline
\multicolumn{2}{|c||}{コロケーションと出現回数} & \multicolumn{2}{c|}{コロケーションと出現回数}\\
\hline
is that so & 82 & i see 〜 right & 5\\
i see & 70 & from 〜 to & 4\\
and the & 62 & and 〜 are & 4\\
thank you very much & 58 & as far as the 〜 is concerned & 4\\
oh is that so & 53 & of 〜 and & 4\\
okay goodbye & 52 & professor 〜 professor & 4\\
for the & 46 & whether the 〜 or not & 3\\
yes goodbye & 43 & mr 〜 right & 3\\
to the & 38 & professor 〜 of tokyo university and & 3\\
of the & 36 & professor 〜 and & 3\\
from the & 31 & your application is 〜 10th & 3\\
thank you & 31 & from the 〜 of the & 3\\
will be & 31 & the 〜 are & 3\\
yes it is & 30 & the slides 〜 the ohp & 3\\
on the & 29 & directly 〜 he comes & 3\\
it 's & 29 & yes 〜 speaking & 3\\
in the & 28 & professor 〜 professor 〜 and & 3\\
with the & 28 & the 〜 one & 3\\
is the & 25 & yes the 〜 and the & 3\\
yes please & 25 & the 〜 and & 3\\
may i help you & 23 & out 〜 for & 3\\
is that & 23 & for the 〜 of & 3\\
so the & 22 & of 〜 our & 3\\
this is & 22 & of the 〜 of the & 3\\
all right & 22 & on the 〜 and & 3\\
no problem & 22 & in the 〜 no & 3\\
it is & 22 & in 〜 and & 3\\
we have & 19 & dr 〜 of & 3\\
yes the & 19 & and the 〜 are & 3\\
this time & 19 & yes 〜 are & 3\\
at the & 19 & i will show 〜 by & 2\\
is it & 19 & how many 〜 will there be & 2\\
i understand & 19 & fee of 〜 per person & 2\\
yes i will & 19 & i would like to take 〜 with me & 2\\
oh i see & 19 & from the 〜 to the & 2\\
\hline
\end{tabular}
\end{footnotesize}
\end{center}
\end{table}

\subsection{位置情報の変化によるコロケーションの違い}

\ref{Sec:extract_algorithm}節で述べた抽出方法では，
コーパス・データを受理する有限オートマトンを用いて単語の
出現位置表を作成した．しかし，単語の出現位置表を作成する方法は，
他にも色々と考えられる．本論文では有限オートマトンを用いた
理由は，\ref{Subsec:based}節で述べたように，有限オートマトンより
単語の出現するコンテキストをとらえるためである．
また，本論文では有限オートマトンの作成にALERGIAアルゴリズムを
用いたが，ALERGIAアルゴリズムの信頼範囲(式(\ref{Eq:eq_state})における
$\alpha$の値)を変化させることにより，
異なった出現位置表が作られる．追加実験として，
ALERGIAアルゴリズムの信頼範囲を変化させた場合に抽出される
コロケーションの違いを調べた．

結果として，状態の等価判定を厳しくする(式(\ref{Eq:eq_state})の\hspace{-0.2mm}$\alpha$の\hspace{-0.2mm}値が
大きい)ほど，出現回数の多い単語同士の共起関係が強調される傾向にあり，
出現回数の少ない長い表現の抽出は抑制された．これにより，単語数の
少ないコロケーションが多く抽出された．特に，上位に抽出されたものの
多くは2単語のみの表現であった．たとえば，日本語の場合には，格助詞間の
共起(``〜 の 〜 に''，``〜 を 〜 に''等)が上位に抽出され，英語の場合には，
前置詞と冠詞などの共起が上位に抽出された．上位の表現の出現回数は
等価判定を緩くした場合に比べて多くなった．
逆に，等価判定を緩くする($\alpha$の値が小さい)ほど
短い表現の抽出が抑制され，単語数の多い長い表現が優先して
抽出された．等価判定が厳しかった場合に抽出されていた短い表現は，
より単語数の多い表現に吸収され，抽出されるコロケーションの
種類が多くなった．
我々の実験より，式(\ref{Eq:eq_state})の$\alpha$の値は0から0.1の範囲が
適当であると考えられる．

以上のように抽出されるコロケーションが変化する理由として
次のことが考えられる．ALERGIAアルゴリズムでは，状態を
マージする際の等価判定は，ある状態から遷移する単語とその遷移確率の
類似判定をどれほど厳しく(または緩く)するかを意味している．
したがって，等価判定を操作することにより，疑似的に，単語の結び付きの強さを
考慮することができる．単語自身の出現回数が多い単語ほど，その
単語に比べ，前後の単語が原文中で珍しい(出現回数が少ない)単語
であることが増える．結果として，コーパス中で滅多に出現しないような
単語が前後に結び付く(出現する)ことがあっても，結び付くことが
少ない(珍しい)ために，単語間の関係が認められなくなる．
ただし，あまりに等価判定が厳しすぎる場合は，接頭木アクセプタ
(木構造)に近いものとなるために，各文での先頭からの距離値に
左右されやすく，また，出現回数の多い単語が，その前後の単語を
無視して共起することが増える．このため，
\ref{Subsec:def_collocation}節での定義に対して，コロケーションとして
不適切なものが上位に抽出される場合がある．

\section{おわりに}
\label{Sec:conclusion}

本論文では，連続型および不連続型コロケーションの自動抽出法として，
単語の出現位置表を用いて，単語の連続・不連続の関係により，
出現頻度の高い単語の組み合わせを長さ優先の条件で抽出する
方法を提案した．また，ATR対話データベースを用いた実験を行い，
提案した方法の有効性を示した．

本手法はコーパス中の各々の文に対する処理であることから，
任意の文(またはコーパスの一部分)に含まれるコロケーションを
知りたい場合にも有効である．
今後の課題として，有限オートマトン以外の方法による出現位置表の
作成や，抽出されたコロケーションの定量的な評価方法について
研究を行いたいと考えている．



\bibliographystyle{jnlpbbl}
\bibliography{paper}

\begin{biography}
\biotitle{略歴}
\bioauthor{小田 裕樹}{
1975年生．1997年徳島大学工学部知能情報工学科卒業．
同年，同大学院博士前期課程入学，現在に至る．
確率・統計的自然言語処理の研究に従事．情報処理学会学生会員．
}
\bioauthor{北 研二}{
1957年生．1981年早稲田大学理工学部数学科卒業．
1983年から 1992年まで沖電気工業(株)勤務．
この間，1987年から 1992年まで ATR 自動翻訳電話研究所に出向．
1992年 9月から徳島大学工学部勤務．現在，同助教授．工学博士．
確率・統計的自然言語処理，音声認識等の研究に従事．
情報処理学会，電子情報通信学会，日本音響学会，日本言語学会，
計量国語学会，ACL 各会員．}

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

\end{biography}

\end{document}

