\documentstyle[epsf,jnlpbbl]{jnlp_j_b5}


\setcounter{page}{79}
\setcounter{巻数}{7}
\setcounter{号数}{3}
\setcounter{年}{2000}
\setcounter{月}{7}
\受付{1999}{12}{13}
\再受付{2000}{2}{15}
\採録{2000}{3}{27}

\setcounter{secnumdepth}{2}


\newcommand{\kanren}{}
\newcommand{\ikanren}{}
\newcommand{\kd}{}
\newcommand{\ikd}{}

\title{ターム間の意味的関連性に基づくタームリストの翻訳多義解消}
\author{菊井 玄一郎\affiref{SP}}

\headauthor{菊井}
\headtitle{意味的\kanren に基づくタームリストの翻訳多義解消}


\affilabel{SP}{日本電信電話(株) サイバースペース研究所}
{NTT Cyberspace Laboratories}

\jabstract{文章に付与されたキーワード集合のような内容語（ターム）
の並びを
「タームリスト」と呼ぶ．本論文では，翻訳先言語のコーパス
のみを用いて，各タームに対する訳語候補のなかから最適なものを
選択する「翻訳多義解消」の新たな方法を提案する．
  本手法では，各タームに対する訳語候補を一つずつ集めてできる
組み合わせのうち，含まれる訳語同士の意味的関連性が最も高い組
を選択する．単語間の意味的関連性の尺度は各単語が翻訳先言語
コーパスにおいてどの程度近い文脈に出現するかを数値化したも
のである．翻訳実験の結果，翻訳多義のある
単語に対する平均正解率77.4\%を達成した．}


\jkeywords{訳語選択，多議解消，共起頻度}

\etitle{Disambiguation in Termlist Translation \\
based on Semantic Proximity}
\eauthor{Genichiro Kikui\affiref{SP}} 

\eabstract{This paper presents a method for resolving ambiguity in 
translating a list of content words (termlist), such as a 
query for information retrieval or a keyword list 
that represents a document. The entire translation begins 
with retrieving a potential translation alternatives for each 
input word from a bilingual dictionary. Our disambiguation 
method, then, chooses one translation for each input word in 
such a way that the resulting list of translations are most 
coherent or related. The {\em relatedness} of translations 
is defined as the proximity among multi-dimensional 
vectors produced from the words on the basis of co-occurrence 
statistics in the target langauge corpora.\\ 
  The method was applied to term-lists extracted from 
newspaper articles and achieved 77.4\% translation accuracy for 
ambiguous words.  
}

\ekeywords{machine translation, disambiguation, co-occurrence}


\begin{document}
\maketitle

\section{はじめに}

情報検索における検索語リストや文書に付与されたキーワード
リストなど，複数の内容語(熟語も含む)から成るリストのこと
を本論文では「タームリスト」と呼ぶ．
タームリストを別の言語に翻訳する「タームリストの自動翻訳処理」は，
単言語用の文書検索と組み合わせてクロスリンガル検索\cite{Oard96}を
実現したり，他国語文書のキーワードを利用者の望む言語で翻訳表示
する処理\cite{Suzuki97j}に応用できるなど，
様々なクロスリンガル処理において重要な要素技術である．

本論文ではタームリストの自動翻訳処理のうち，各ターム
に対して辞書等から与えられた訳語候補の中から最も妥当な
ものを選択する「翻訳多義解消」に焦点を当てる．

内容語に関する翻訳多義解消の研究は従来から文(テキスト)
翻訳の分野で行われて来た．

80年代には統語的依存構造に着目した意味多義解消規則を用いる
方式が研究され，実用システムにも組み込まれた(\cite{Nagao85}など)．
この方式は翻訳対象語に対して特定の統語関係(例えば，目的語と
動詞の関係)にある別の語を手がかりにした訳語選択規則を人手で
作成し，これを入力に適用することによって多義解消を行う方式である．
従って，この方法は複数語間に統語的関係が存在しないタームリスト
には適用できない．

一方，90年代に入って言語コーパスから統計的に学習した結果に
基づいて多義解消を行う研究が活発化している．これらのうち，
統語的解析を(明示的には)行わず，翻訳対象語と同一文内，
あるいは，近傍で共起する他の単語を手がかりに多義解消を
行う手法はタームリストの翻訳にも適用可能であり，すでに
いくつかの研究も行われている．

これらは利用するコーパスによって大きく2つに分類できる． 

  １つめはパラレルコーパスと呼ばれる対訳関係にあるコーパスを
用いるもので，T. Brownらによる文翻訳のための訳語選択手法\cite{Brown91}，
R. Brownらのタームリスト翻訳手法\cite{Brown97}がある．これらの
方法は訳語候補自体もコーパスから抽出するので対訳辞書を別に用意
する必要がないという利点があるが，対象分野に関する相当量のパラ
レルコーパスを学習データとして準備しなければならないという問題
がある．

  ２つめは目的言語の単言語コーパスのみを用いるもので，
Daganら\cite{Dagan94}\footnote{\cite{Dagan94}の基本的な手法は
構文解析された学習コーパス，入力データを前提とするものであるが，
考察の章で学習データの不足に対処するために統語的依存関係を
無視して単なる共起によって処理する方法が指摘されている．}
,田中ら\cite{Tanaka96}による文翻訳の多義解消手法, 
同様の手法をタームリスト翻訳に適用した 
Jangら\cite{Jang99} による研究がある．これらは
入力の各単語(内容語)に対する訳語候補の組み合わせのうち目的
言語のコーパス中における共起頻度あるいは相互情報量
が最大のものを選択するという方法である． 
たとえば，入力が ``suits'' と  ``wear'' を含み，前者の訳語候補が
``裁判'' と ``スーツ''，後者の候補が ``着用'' であったとき，
日本語コーパスにおいて  ``スーツ'' と  ``着用'' の 共起頻度が
``裁判'' と  ``着用''のそれよりも高い場合，``suits''の訳語を
``スーツ'' に決定するというものである．
この方法はパラレルコーパスに比べて大量に入手可能な単言語コーパスを
学習データとして用いるという，統計的処理にとって重要な利点を
持っている．

本論文で提案する手法は，目的言語の単言語コーパスのみを利用
する点では上記２つめの手法に分類されるが，訳語候補の組み合わせ
の妥当性を計算する方法が異なる． 本手法では，訳語候補同士の直接
的な共起頻度を用いるのではなく，各訳語候補に対して，まず，
目的言語コーパスにおける共起パターンをベクトル化した一種の
意味表現を求め，この意味表現同士の「近さ」によって計算する． 
この「意味表現同士の近さ」を以下では \kanren と呼ぶ． 
2単語の \kanren はこれらの単語と共起する単語の頻度分布を元に
計算されるため，2単語のみの共起頻度を用いるより精度の高い
結果を得ることが期待できる．

以下，まず２章で問題設定を行う． 次に３章で多義解消モデル
とその中心となる複数単語の意味的\kanren について定義し，
４章では枝刈りによる処理の高速化について説明する．
５章では評価実験とその結果について述べ，６章で誤りの原因と
先行研究との関連について考察する．

\section{タームリスト翻訳における多義解消タスク}
 
  $n$ 個の要素からなる翻訳元言語のタームリストを 
$ S = s_1^n = s_1, s_2, \ldots, s_n (s_i $ は一つのターム，$s_i^j$ 
は $s_i から s_j $までの並びを表す) と記す． 
ここで，タームリスト内の要素の順序には意味がない
\footnote{順序を考慮しない複数の語句の集まりは
``bag of words''とも呼ばれる．}．
なお， $n$ を{\bf タームリストの長さ}と呼ぶ． 

  各タームに対して対訳辞書（bilingual dictionary )などを参照して
文脈独立に与えられた訳語の集合を  {\bf 訳語候補集合} と呼ぶ． 
なお，訳語は一つの単語であっても複数語から成る熟語であっても良い．

  入力の各タームに対してその訳語候補を一つずつ選んで並べたものを
{\bf 翻訳タームリスト候補} と呼び，$T = t_1^n = t_1, t_2, \ldots, t_n (t_i は
s_i に対する訳語候補の一つ)$ で表す． たとえば，入力がsuit と 
prosecuteとから成っていて，これらに対する
訳語候補がそれぞれ「スーツ」と「裁判」，「遂行」と「起訴」である
場合，以下の４つの翻訳タームリスト候補が存在する．

\begin{verbatim}
（スーツ，遂行）,（スーツ，起訴）,（裁判，遂行）,（裁判，起訴）
\end{verbatim}

  本論文で対象とする翻訳多義解消とは， 翻訳タームリスト候補 の中から
(入力タームリスト全体の与える文脈に照らして)最も適切なものを選ぶこと
である． 

\section{翻訳多義解消モデル}

  本論文で提案する手法は「翻訳タームリスト候補の中でターム同士の
意味的関連性が
高い方がそうでないものより妥当である」という仮定に基づいている．
ここで，単語同士の意味的関連性の高さはこれらの単語がどの程度類似した
文脈で出現しうるかによって定義する．

たとえば，2章で挙げたsuit と prosecuteの場合，翻訳タームリスト候補
内の意味的関連性が最も高いのは(裁判，起訴)であるからこれを選択する．

形式的には，$ n$個のタームから成る入力タームリスト $ S = s_1^n $ に
対する最適な翻訳タームリスト $ B(s_1^n) = \hat{T}= \hat{t_1^n} = 
\hat{t_1}, \ldots, \hat{t_n}$ は次の式で与えられる


\vspace{5mm}

\renewcommand{\arraystretch}{}
\[
\begin{array}{cccc}
\hat{T} & = & \arg & \hspace{-3mm} \max rel(T) \nonumber \\
	&   & {\it T} & \nonumber
\end{array}
\]

\renewcommand{\arraystretch}{}

ここで，
$ rel(T) $は翻訳ームリスト候補$ T$に対する \ikanren の値で {\bf 
\ikd }あるいは単に{\bf \kd }と呼ぶ．本研究では以下で示すように 
\ikd を{\bf 単語空間(WordSpace\cite{Schuetze97})}と呼ばれる多次元
ベクトル空間を用いて定義する．

\subsection{共起頻度による \ikd の定義}

  単語空間を使った \ikd の定義を行なう準備として，
コーパス中のタームの共起頻度をそのまま使った \ikd を定義する． 

  まず，ターム間の共起頻度を行列で表現する．この行列の行と列はどちら
も異なりタームに対応し，$(i, j)$
要素は $ i $行目のターム$ w_i $と$ j $列目のターム $ w_j $ とのコーパスに
おける共起頻度である．ここで，2つのタームの共起頻度とは
これらがあらかじめ決められた $p$語以内の近さでテキスト中に表れる
頻度である\footnote{sliding windowによる共起関係の定義}．以下では
この行列のことを{\bf 共起行列}と呼ぶ．

  表 \ref{tab.cooc} に共起行列の例を示す．
この例は，たとえば「訴訟」と「法」とがコーパス中で246回共起している
ことを表している．
 

\begin{table}[htb]
\caption{共起行列の例(An example of a co-occurrence matrix).}
\label{tab.cooc}
\begin{minipage}{\columnwidth}
\vspace{3mm}
\small
\begin{center}
\begin{tabular}{l||l|l|l|l|l}
 & $\ldots$  & 法(law) & $\ldots$ &  百貨店(department store)& $\ldots$\\\hline\hline
   &  &              & &          &  \\\hline
訴訟(law:suit) & $\ldots$ & 246 & & 1  &   \\\hline
   &  &              & &            &\\\hline
スーツ(garment:  suit)  &$\ldots$   & 9 &$\ldots$ & 88     &\\ \hline
&  &              & &            &\\\hline
   &  &              & &          &  \\
\end{tabular}  
\end{center}
\end{minipage}
\end{table}

  この共起行列の$i$行目の行ベクトル(長さを1に正規化したもの)を
ターム $w_i$に対する{\bf 共起ベクトル}と呼び $\vec{w_i'}$
で表す．共起ベクトルはそのタームが他のタームと
どのような共起関係にあるかを表している．この定義から明らかな通り，
２つのタームが他のタームと
同じような比率で共起しているならば，これら2つのタームに対応するベクトル
は近い方向を向く． 

そこで，2つのターム$w_i, w_j$の意味的な近さ$prox(w_i, w_j)$をこれらの
タームに対応するベクトル$\vec{w_i'}, \vec{w_j'}$のなす角の余弦
($cos(\vec{w_i'}, \vec{w_j'})$)として以下のように定義する
\footnote{$\bullet$は二つのベクトルの内積を表す記号}．

\begin{eqnarray}
prox(w_i, w_j)  =  cos(\vec{w_i'}, \vec{w_j'}) \label{f.prox}\\
\:  where \:\: cos(\vec{a}, \vec{b}) = 
\frac{\vec{a} \bullet \vec{b}}{ \sqrt{\mid \vec{a}
 \mid ^2  \mid \vec{b} \mid ^2}}\nonumber
\end{eqnarray}

この「近さ」の概念を$ n$タームに拡張したものが$n$要素から成る
タームリストの\ikd の定義である．
具体的には，ターム列 $  w_1^n = w_1, w_2, \ldots, w_n $ に関す
る共起頻度に基づく \ikd  $rel'(w_1^n)$ を下記のように定式化する．
\begin{eqnarray}
rel'(w_1^n) & = & \frac{1}{n}\sum_{i=1}^n cos(\vec{w_i'}, \vec{c}(w_1^n))  \label{f.coh}\\
where \:\: \vec{c}(w_1^n) & = &\frac{1}{n}\sum_i^n \vec{w_i'}  
\end{eqnarray}

すなわち，n個のターム$(w_1^n)$に対応するn個のベクトルの重心$\vec{c}(w_1^n)$
をまず計算し，この重心からそれぞれのベクトルまでの
「近さ(式(\ref{f.prox}))の平均」を共起行列における 
\ikd とする\footnote{空間上の複数の点の「ちらばりの程度」 
を表す尺度として一般的に使われるのは平均からの自乗偏差であるが，
本研究では点の間の近さを余弦を使って定義したので式(\ref{f.coh})を用いた．}．
 
\subsection{単語空間における\ikd }

  上記で定義した\kd はコーパス中のターム間の共起頻度をそのまま使って
いるためデータスパースネスの問題がある．また行列の次元が大きくなりすぎ
て計算機での扱いが難しいという問題もある．

これらの問題を解決するために共起行列に固有値分解(Singular Value
Decomposition:SVD)を適用し行列（の階数）を縮退させる
(なおSVDによる行列の縮退については付録参照)．
このようにしてできた行列を{\bf 縮退共起行列}と呼ぶ．
縮退共起行列には元の共起行列では陽に現れていないターム
間の間接的な共起関係が表れることが知られている
(higher order co-occurence)\footnote{文献\cite{Schuetze97}p.91}．
すなわち，$w_i$と$w_j$がコーパス中で直接共起していなくても，
$w_i$と$w_k$，$w_j$と$w_k$が数多く共起していれば，
縮退した行列では$(i,j)$要素の値がある正の値になる．

この縮退されたベクトル空間を単語空間
(word space)と呼ぶ\footnote{「単語空間」はLSI(Latent Semantic Indexing)
\cite{Deerwester90}
と密接な関係がある．
前者はタームとタームの共起行列にSVDを適用したものであ
り，後者は文書に対する各タームの生起行列にSVDを適用したものである．
これらの情報検索における相違点に関しては\cite{Schuetze97b}を参照のこと．
}．

この縮退共起行列の $i$ 番目の行ベクトルを$w_i$に対する縮退共起
ベクトルと呼び $ \vec{w_i}$ と表す．

単語空間に基づく\ikd $rel(w_1^n)$ とは前節の\ikd ($rel'(w_1^n)$)の定義に
おいて各単語($w_i$)に対する共起ベクトル($\vec{w_i'}$)を
縮退共起ベクトル($\vec{w_i}$)に置き換えたものである．
 
\section{アルゴリズム}\label{S.Algorithm}

  ３章で述べた\kd の定義には重心（平均）を求める操作が
含まれているため，動的計画法などのような部分問題への分割を
前提とした効率的なアルゴリズムが適用できない．
従って，基本的には各翻訳タームリスト候補に対して総当たり的に
\kd を計算する方法によらざるを得ない．
この問題に対して
本研究では以下に示すような枝刈りを適用して計算量の
削減を図った．

\subsection{総当たり法（基本アルゴリズム）}


根接点を1段目として$i$段目の節点から出るリンクが
$i$番目のタームに対する訳語候補に対応するような探索木を考える
(図 \ref{FigTermList}に例を示す)． 
この木の各葉接点(図の右端の節点)が一つの翻訳タームリスト
候補に対応する． 

\begin{figure}
\begin{center}
\epsfile{file=Fig1_termlist.eps,width=5cm}
\end{center}
\caption{翻訳タームリスト候補に対する探索木(A search tree for possible translations).}
\label{FigTermList}
\end{figure}

枝刈りの前提となる{\bf 総当たり法}とはこの探索木を深さ
優先で辿り，葉節点に到達するたびに\kd を計算することによって
\ikd が最大の候補を決定する方法である．
  
\subsection{枝刈り}

\subsubsection{準備}  

  入力タームリスト $S = s_1^n $ を先頭の
 $ m \: $ 個 $(m<n)$からなる $ s_1^m$の部分と残りの$s_{m+1}^n$ の部分
に分ける． 
$ s_1^n $に対する翻訳タームリスト候補のうち， $ s_1^m $に対する訳語
を $ u_1^m $ に固定した時，\kd が最大であるものを $ C_m(S, u_1^m) $ 
で表わすと次の不等式が成立する(なお，付録にこの不等式の簡単な証明を示す)．

\begin{eqnarray}
rel(C_m(S, u_1^m))  \leq  
   \frac{m * rel(u_1^m) + (n - m) * rel(B(s_{m+1}^n))}{n} \label{bound}
\end{eqnarray}

ここで，$B(s_{m+1}^n)$ は 入力が  $s_{m+1}^n$ の場合の最適な
翻訳タームリストである．
従って，式(\ref{bound})の右辺は，$ u_1^m $に対する\kd の値と $s_{m+1}^n$
の部分のみを考えた場合の最適な翻訳タームリスト($B(s_{m+1}^n)$)の\kd の
値をそれぞれのタームの個数で重みを付けて平均したものとなる． 

  この不等式は，$ s_1^m $の部分に対する訳語を $ u_1^m $に固定し
たとき，$ m+1$ 以降の
タームに対する訳語を どのように選んでもタームリスト全体の 
\kd の値が右辺を越えないこと（上限）を表している．
なお，等号が成り立つのは $ u_1^m $の重心と$ B(s_{m+1}^n)$ の
重心（の方向）が一致する時である．

\subsubsection{枝刈り手法}  

  前記の不等式(\ref{bound})を用いて「総当たり法」に対する
次のような枝刈りを行なう．

\begin{quote}
\begin{description}
\item [前処理] まず，タームリストの末端(右端)から 
$ l (l = 1, \ldots, k)$ 個の各部分に対する最適翻訳タームリストの
\ikd の値 $rel(B(s_{n-l+1}^n))$を計算しておく．これらの値は
次に述べる「枝刈り」ステップにおいて利用する． 
ここで$k $ は $n $より小さいある値で「枝刈り判定ターム数」
と呼ぶ．
なお，この前処理自体に最適な翻訳タームリストを求める処理が入って
いるが，これは本アルゴリズム全体を再帰的に適用することによって
行なう．

\item [枝刈り] 総当たり法と同様の深さ優先の探索によって，探索木
を根（タームリストの左端）から$m + 1 (但し， n - k \leq m)$番目の
深さのある節点(X)まで進んだとする
(図\ref{FigStree}の節点X)．根節点からXまでの経路に対応
する(先頭から$m$個分の)訳語の列を$ u_1^m $とし，
既に生成された翻訳タームリスト(すでに辿った葉節点)の\ikd の値の
うち最大のものを max とする(図\ref{FigStree}のmax)．

この $ u_1^m $ に対して先の前処理で計算した  $rel(B(s_{n-l+1}^n))$
を使って式(\ref{bound})の右辺の値（\ikd の上限値）を
計算し，この値がmaxより小さいならば，節点X以降のパスの探索
(図\ref{FigStree}の斜線部分)を中止する．
\end{description}
\end{quote}

\begin{figure}
\begin{center}
\epsfile{file=Fig2_Stree.eps,height=4cm}
\end{center}
\caption{枝刈り(An example of pruning).}
\label{FigStree}
\end{figure}

この枝刈りを含んだアルゴリズム全体の計算量は最悪の場合，すなわち，
枝刈りが一回も起こらなかった場合，元の総当たり法の計算量と
前処理の計算量の和になるため，元の総当たり法より計算量が増える．
しかし，実際には後述するように50\%以上計算時間が短縮される．

\section{評価実験}

新聞記事から抽出したタームリストに対して本手法を適用し，多義
解消精度，処理効率に関する評価実験を行った． 

実験手順は次の通りである． 

\begin{enumerate}
\item 英語の新聞記事から単語を抽出して入力タームリストを作成する
\item 作成されたタームリストに対して英和辞書引きを行い訳語候補を得る
\item 提案手法，および，既存の他の手法によって多義解消を行い
これらの結果を人手で作られた正解と比較する． 
\end{enumerate}

この実験を「翻訳実験」と呼ぶ． 翻訳実験は本手法本来の用途に沿った
ものであるが，「正解」を人手で作成する必要があるため客観性を保持
して大量のデータを用意するのにはコストがかかる． 

そこで，補助的な実験として，より大量の入力に対して「再翻訳実験」
と呼ばれる実験を行った． 再翻訳実験とは，上記2で得られた(日本
語)訳語候補の各々に対して逆方向の辞書(和英辞書)を引くことによって英語の訳語候
補を作り，英語コーパスを使って多義解消を行うものである． この場合，
元のタームリストを「正解」とする． 

以下では，まず実験条件について述べ，次に結果を述べる． 

\subsection{実験条件}

\subsubsection{コーパスと前処理}

英語コーパスとして 1994 年下半期のNew York Times(420MB)
\footnote{Linguistic Data Consortium}，
日本語コーパスとして1994年の毎日新聞(140MB)を利用した． 

英語コーパスについては，まず，スペース等をデリミタとして単語単位に分割し，
次に，log-likelihood によって隣接共起性の強い2つの単語(たとえば vice 
president など)を一つにまとめる処理 \cite{Dunning93}
を行った． 
日本語コーパスに関してはJTAG\cite{Fuchi97j}を使って形態素単位に
分割し，英語と同様に隣接共起性の強い2単語をまとめたものを
タームとした． 

\subsubsection{入力タームリスト}

  入力タームリストは次の手順で作成した． 

\begin{enumerate}
\item 前述の英語コーパスから400記事をランダムに選ぶ
\item 各記事について出現するタームの重要度をtf-idf値
\footnote{あるテキストにおけるターム $w $ に対するtf-idf 値 は
 $ tf_w log(\frac{N}{N_w}) $で与えられる．
ここで  $ tf_w $は
$ w $ のテキスト中での出現頻度, $ N $ はテキストの総数
$ N_w $ は $ w $を含むテキストの数である．
}によって計算し上位から順に 20単語抽出する．
\end{enumerate}

\subsubsection{訳語候補}

  前述の方法によって作られたタームリストに対して対訳辞書を
引いて訳語候補を作成した．対訳辞書としては，
入手が容易なことと約77000語という語彙の多さから EDICT\cite{Breen95}
を和英辞書として用い，英和辞書はこのEDICTを逆変換して作成した．なお，
EDICTの単語1語あたり平均訳語数は1.72である．

\begin{itemize}

\item 翻訳実験用

  前述の英語タームリストのうちさらにランダムに70個を選び，
英和辞書を使って各タームに対する訳語候補を生成した． 次に，
これらの訳語候補の中から人手で正解(複数可)にマークした．
あるタームの訳語候補の中に正解が存在しない場合，精度の判
定ができないので，そのターム自体をリストから除いた．
そして，最後に残ったものの中から重要度(tf-idf値)の大きい
順に10個選んで実験用の入力とした．表\ref{Tab.Tdata}に各
タームリストの先頭 $n$ 単語(ターム)を取り出した場合の
総語数，平均訳語数，多義語数，平均多義数を示す．ここで
平均訳語数とは1語あたりの訳語数を全タームに対してとった平均で
あり\footnote{辞書全体の平均より若干大きいのは対象語が相対的に
多義数の多い頻出語であるためと思われる．}，
平均多義数とは翻訳多義解消という観点からみたもので，多義性の
あるタームのみを対象に訳語候補数を正解数で割ったもの(の平均)
である\footnote{なお，多義性のあるタームに対する平均訳語数は4.11．}．
表によると平均多義数はおおよそ2.3 であり．ランダムに訳語
を選んだ場合，多義性のある単語に対する平均正解率は 1/2.3 
= 0.43 となる．

\begin{table}
\caption{翻訳実験データ(Test data for translation experiment).}
\label{Tab.Tdata}
\begin{center}
\begin{tabular}{llllll}\hline
$n$         &  2  &  4  &   6 &   8 & 10  \\\hline
総語数      & 146 & 292 & 438 & 576 & 669  \\
平均訳語数  & 1.99 & 1.95  &  2.03 &  2.13 & 2.12 \\
多義語数    & 71  & 141 & 216 & 285 & 224  \\
平均多義数* & 2.32 & 2.29 & 2.32 & 2.38 & 2.38 \\\hline
\end{tabular} \\ 
$*$:各翻訳多義語に対して訳語候補数を正解訳語数で割った値の平均
\end{center} 	
\end{table}
 
なお，正解訳語が存在しないために除かれたタームは全体の
10\%あり，そのうち64\%が固有名詞，18\%が複合語，残りが
通常の単語であった．固有名詞の大部分は日本語テキストには
あまり出現しない人名や組織名などであり，基本的に訳語
が一意に決まるため多義解消の対象にはならない．また，これらの
単語は翻訳先言語に殆んど出現しない人名や組織名であるため
(提案手法および比較に用いた他の手法において)他の語の
多義解消に与える影響も少ない．
複合語については個々の単語に分割して辞書引きするという方法
もあり得るが，今回は単に辞書項目なしという扱いとした．

\item 再翻訳実験用

  再翻訳実験用の訳語候補は前述の400個のタームリスト全てを使い，
各タームに対して，まず，英和辞書を引き，次に，得られた訳語の各々に
対して和英辞書を引いて，それらの集合和を取り訳語候補とした．正解は
元のタームである．なお，英和辞書に掲載されていないタームについては
訳語候補を元の単語のみ(多義なし)とした．再翻訳実験用データの平均多
義数はタームリスト長$n$に比例して増大する傾向にあり，$n = 2$の時
4．38，$n = 10$の時5.42である．

\end{itemize}

\subsubsection{多義解消用の共起行列}

  前述の形態素解析済み日本語コーパスから名詞，動詞などの内容語で
頻度が上位から50,000までの語を選び，この中からさらに上位1,000語を
選んで，前者を行と後者を列とするような共起行列(50,000 $ \times $ 1,000)
を作成した．なお，2つの単語がコーパス内で50語以内
\footnote{10, 30, 50, 70と変えて実験を行い結果が最も良いものを選択した}
に出現している時，これらが共起しているとした．

  得られた共起行列をSVDPACKC\cite{Berry93}によって50,000 x 100 の行列
に変換した．

  再翻訳実験用の英語共起行列は英語コーパスのうち入力タームリストの
作成に使った400記事を除いたものを使い上記と
同様にして作成した(英語に関してはあらかじめ作られた
「ストップ語リスト」に含まれない単語を内容語とした)． 

\subsubsection{低頻度語の扱い}

  訳語候補のうち共起行列に存在しないもの(上位50,000語に含まれないもの)
に対しては単語ベクトルが未定義となってしまう． これらの単語については
コーパス中でその前後20語に出現する単語のベクトルを平均
した値を近似値として用いた\footnote{LSIを使った情報検索における
未知タームの扱い\cite{Dumais94}を参考にした}． 
なお，コーパス中に一度も出現しない単語については訳語候補
から削除した． 

\subsection{精度比較用アルゴリズム}

  比較のため二つの多義解消アルゴリズムを用いた． 

\subsubsection{訳語のユニグラム頻度に基づく方法(ユニグラム法)}

一つ目の手法は「あるタームが複数の訳語を持つ場合，目的言語に
おける出現確率(ユニグラム確率)が最大のものを選ぶ」という
方式である． 
これをユニグラム法と呼ぶ． 

ある単語の目的言語における生起確率の推定値は，単純に，
共起行列の作成に用いたコーパスにおけるその単語の出現数を
コーパスの総語数で割ったものを用いた．

\subsubsection{訳語間の相互情報量に基づく方法(訳語共起法)}

二つ目の手法として，目的言語コーパスのみを用いた既存の多義解消手法の
代表として訳語同士の共起頻度に基づくアルゴリズム \cite{Tanaka96}
を用いた． 

この手法では，各翻訳タームリスト候補について「共起スコア」を計算し
この値が最大のものを選ぶ． 
ある翻訳タームリスト候補に対する共起スコアはその翻訳タームリスト
内の単語を2つ取り出してできる全ての組み合わせについて，
目的言語コーパスから得られる2語共起のスコア（文献
\cite{Tanaka96}では相互情報量
\footnote{単語Aと単語Bの間の相互情報量は
$ N f_{AB} / (f_A f_B)$ で与えられる． ここで，$N$は総語数，
$f_A, f_B$はそれぞれ A,Bの出現頻度を，$f_{AB}$はAとBとが一定の近さで
出現する頻度}を利用）を計算し，その総和を取ったもの
と同等である\footnote{正確な定義は文献\cite{Tanaka96}を参照のこと． }． 
なお，共起を判定する基準は我々の手法と同じく2つの単語が50語以内に
出現することとした． 

\subsection{実験結果}

\subsubsection{日英翻訳における翻訳精度}

  翻訳実験では各タームリストの先頭から$n$個($n$は2から10)取り出し
てできるタームリストに対して，4つの手法
で多義解消を行ない精度の比較を行った． ここで，4つの手法とは，
提案手法，SVDを適用する前の生の共起行列を使うもの，
5.2で述べた2つの比較用アルゴリズムである． 

\begin{figure*}[t]
\begin{center}
\epsfile{file=Fig3_gra5e.eps,height=7cm}
\end{center}
\caption{提案手法，ベースライン，訳語候補の共起に基づく手法の翻訳精度(translation results).}
\label{Fig.Trans}
\end{figure*}

図\ref{Fig.Trans}にその結果を示す．
ここで，図の縦軸は多義語1語あたりの翻訳正解率，
横軸は入力タームリストの長さ($n$)を表す．
なお，「多義語1語あたりの正解率」とは全ての翻訳多義語（不正
解訳語を候補として持つターム）の中でシステムの出力が正解だったも
のの比率である．5.1.3で述べた通り，ランダムに訳語を選択した
場合の理論値は0.43となる．

図中のProposed, Non-SVD, Unigramはそれぞれ，提案手法，提案手法で
縮退共起行列の代わりに(SVDを適用する前の)共起行列を使うもの，
ユニグラム法，に対応する． 
また， MI, MI'
はどちらも訳語共起法の結果であるが，
前者は適用不可能なもの\footnote{共起度最大のものが一意に
定まらなかったもの}(入力の19\%)の正解率を0, 後者はこれを
ランダム選択の場合の値(0.43)とした場合の正解率である． 
なお，訳語共起法に関する実験値は論文
\cite{Tanaka96}の値(MI = 0.62, 適用率 = 76\%)とほぼ一致している

図より明らかな通り，正解率の高い順にProposed, Non-SVD, Unigramとなり，
この3つの中でのSVDを使った提案手法の有効性が検証された．訳語共起法
との比較でも提案手法の方が高くなった．提案手法の正解率の最大値は
タームリスト長8の時で77.4\%，このときの多義性のない単語を含めた
正解率(全体の正解率)は89.4\% である．

タームリスト長と正解率の関係であるが，提案手法では長さ$n$が
8，MIは5で正解率極大，non-SVDは9でわずかに極大
となった．極大点が生じる理由としては，タームリストが長くな
るにつれて文脈情報が増加するが，長くなりすぎると
(tf-idf値の低い単語[ノイズ単語]が含まれるために)タームリスト
中の単語の意味的関連性が下がるため，と考えられる．

なお，手法によって極大点が異なるのはこれらタームリスト増加に
よるメリットとデメリットの影響が手法に
よって違うためであると考えられる．特に，MIの方が提案手法
より小さい$n$で極大となるのは，
前者の方法が基本的に2単語間の共起関係を用いてスコアを計算
しているので，タームリスト全体でスコアを求める後者の方法よ
り単語増加によるメリットを受けにくいためと推測できる．また，
non-SVD においてはベクトルの信頼性が低いために少ない
個数ではノイズの方が大きいことを示していると思われる．

なお，これらの詳しい検証は今後の課題である．

\subsubsection{再翻訳実験における翻訳精度}

翻訳実験と同様にタームリスト長を変えて多義解消を行いProposed, Non-SVD, 
Unigramに対して 翻訳精度を求めた． その結果を図\ref{Fig.Retrans}に示す． 
図の見方は前節と同様である． なお， ``-normalized'' の付いているものは
多義語に関する一語あたりの平均多義数が一定になるように正規化したもの
である．図より値の傾向は翻訳実験と同じであることが分かる． 

\begin{figure*}[t]
\begin{center}
\epsfile{file=Fig4_gra3e.eps,height=7cm}
\end{center}
\caption{再翻訳精度とタームリスト長の関係(Re-translation results).}
\label{Fig.Retrans}
\end{figure*}


\subsubsection{枝刈りの効果}

枝刈りの効果を調べるために，長さ8および10のタームリストに対して
再翻訳実験を行ない，処理時間を測定した．縦軸にタームリスト一つ
あたりの処理時間(秒)，横軸に枝刈り判定ターム数(4.2章の「前処理」
における$k$の値)
を取ったグラフを図\ref{Fig.Pruning}に示す． 

\begin{figure}
\begin{center}
\epsfile{file=Fig5_graTe.eps,height=7cm}
\end{center}
\caption{枝刈りと処理時間の関係(Processing Time vs. Pruning.)}
\label{Fig.Pruning}
\end{figure}

この図から明らかな通り，枝刈りによって60\%-70\%の削減となった．

また，元のタームリストの長さの半分の長さを使って枝刈りの
可否の判定を行なうと計算量はほぼ最小となることが分かった．さらに，
ここで注目すべきなのは，判定ターム数が２でも計算時間は半分以下に
なるということである．

\section{考察}

\subsection{失敗例の分析}

  失敗例のうち我々の手法に関係するもの\footnote{その他の失敗原因
として，形態素解析誤り，複合語（特に複合固有名詞）の認定誤り
などがあげられる}は次の２種類である．

  １つ目は多義解消すべき単語の出現する文脈が極めて近いもので
ある．
たとえば``share'' に対する訳語の「シェア(市場占有率)」と「株」は
どちらも会社の業績や将来性に関する文脈で出現するため識別が
難しい．
文翻訳であれば\cite{Dagan94}のような統語的依存関係を用いてより
精密な識別が可能であるが，タームリストの場合は難しい． 
  
  ２つ目は訳語候補が多義性を持つ場合である．ある訳語候補が
多義性を持ち，その意味の一つが非常に一般的である
（様々な単語と共起する）場合，この一般的な単語が訳語として選択
されやすくなる．この理由として，この種の単語のベクトルは
各次元に対して「平均的な」値を持つため，ベクトルの方向が
他の単語の重心ベクトルの方向に近くなることが考えられる．

  後者の問題はDaganら\cite{Dagan94}によって既に指摘されて
おり，解決法として１）より大きなコーパスで共起関係を学習
する，２）パラレルコーパスを使う，
\footnote{目的言語側の共起関係を原言語側の共起関係によって
分類し，入力に応じたものを利用する．} という２点が挙げられている．
これらに加えて，共起関係を学習する前にあらかじめ単言語の
意味多義解消手法\footnote{たとえば\cite{Schuetze97}\cite{Pereira93}
など} によってコーパス中の単語の意味多義を解消しておくことが考えられる．

\subsection{関連研究}

  Daganら\cite{Dagan94}はテキスト中で統語的な依存関係(例えば，
動詞-目的語, 名詞-形容詞など)にある２つの単語を対象に，
これらの単語に対する訳語候補の最適な組み合わせを決定する方法
を提案した．訳語の組み合わせの妥当性は目的言語コーパス中での
これらの共起頻度によって評価する．また，田中
\cite{Tanaka96}らは同一文に出現する任意個の単語を対象として
やはり目的言語側での共起頻度をもとに最適な訳語の組み合わせを
求める手法を提案している．

  はじめに述べた通り，第一の相違点は彼らの方法がコーパス中の
共起情報のうち訳語候補間に関する共起頻度しか利用していない
のに対して，我々の方法はコーパス全体の共起情報から計算された
高次の情報を使っていることである．

  第二の相違点は，彼らが目的言語コーパスから得られた共起頻度を
そのまま使っているのに対して我々のはSVDによって一種のスムー
ジングを施した値を使っている点である．

  すなわち，我々の方法はコーパス中の情報をより有効に利用して
いると考えられ，このことが精度向上の一つの理由だと考えられる．

\section{おわりに}

  本論文ではタームリスト中の各単語の \ikanren に着目した
翻訳多義解消方式を提案した．
本手法は多義語に対して平均77.4\%
の正解率を持ち，デフォールトのタームリスト翻訳
結果として有用であると考えられる．
また，本手法は，単語ごとに分割された目的
言語のコーパスのみの教師なし学習に基づいており，入力や学習データ 
に対する統語的解析を要さないという利点を持っている．

  今後の課題として学習コーパスから共起情報を取り出す際の最適な
共起の範囲を自動的に決定すること，また，学習コーパス中の単語に
対してあらかじめ多義解消をした場合の効果を評価することがあげら
れる．

  クロスランゲージ検索など実際の応用システム
に適用した場合，また，通常の文翻訳に適用した場合の
性能評価（クロスランゲージ検索の場合は適合率／
再現率）も今後の課題である．

\acknowledgment

 本研究は著者がスタンフォード大学言語情報研究センター(CSLI)滞在中に
 行なったものである． 研究内容に関するアドバイスとサポートを頂いた
 同大学のStanley Peters教授，および，CSLI Infomapグループのメンバー
 に感謝する．
 また，論文全体に関するコメントを頂いたNTTサイバースペース
研究所の林 良彦氏，
 アルゴリズムに関するアドバイスを頂いた同研究所の村本 
 達也氏に感謝する．



\appendix 

\section{SVDによる共起行列の縮退}

行列 $ A $に対するSVDとは次の式を満たす 
$U_{0}, S_{0}, V_0^{-1}$を求めることである．
\begin{eqnarray*}
A & = & U_0 S_0 V_0^T
\end{eqnarray*}
ここで，$U_0U_0^T = V_0V_0^T = I (I は単位行列)$, 
$ S_0 $ は対角行列 $diag(s_0, ... ,s_n) $ で 
$ s_i > s_j > 0 if (i > j) $を満たす．

$ S_0 $の対角要素のうち $ k $より大きいものを全て 
0 と置いたものを $S$とし，$U_0, V_0$の先頭
から$ k $列目までの部分行列をそれぞれ$U, V$とすると，
\begin{eqnarray*}
 \hat{A} = USV^{T} 
\end{eqnarray*}
は$ A $の階数を$k$に落した近似になっている．

Aを共起行列と考えると $w_i,w_j$の類似性を表す
行列は $ AA^{T}$で得られる．
$A$ の代わりに $\hat{A}$を使うと， 
\begin{eqnarray*}
\hat{A}\hat{A}^{T} = LSR^{T}(LSR^{T})^{T} = LS(LS)^{T} \label{aa}
\end{eqnarray*}
となり，L, Sという次元の小さい行列によって単語間の
類似性が計算できることが分かる．なお，さらに詳しい説明は
文献\cite{Deerwester90}\cite{Schuetze97}を参照されたい．

\section{不等式(4)の証明}

$S = s_1, \ldots, s_n $に対応する任意の翻訳タームリストを 
$ T = t_1, \ldots , t_n $ その最初の$ m (m \leq n)$個からなる
タームリストを $ t_1^m $，残りを $ t_{m+1}^n$ とすると次の式が成立する． 
\begin{eqnarray}
rel(T) \leq \frac{m * rel(t_1^m) + (n-m) * rel(t_{m+1}^n)}{n} \label{f1}
\end{eqnarray}

\begin{quotation}
\noindent
[証明]\\
\noindent
$T$の各タームに対応するベクトル(長さを1に正規化したもの)
を$\vec{x_1}, \ldots, \vec{x_n}$, ターム集合 $T, t_1^m,t_{m+1}^n$ 
それぞれに対するベクトル集合の重心をそれぞれ $\vec{g}, \vec{g_1}, 
\vec{g_2}$とすると，式 (\ref{f1})の左辺は
\begin{eqnarray}
rel(T) =  \frac{1}{n}\sum_{i = 1}^n prox(\vec{x_i}, \vec{g})  
  =   \frac{1}{n}\sum_{i = 1}^n \frac{\vec{x_i} \bullet \vec{g}}
    {\mid \vec{g} \mid} 
  =  \frac{1}{n}\frac{n \vec{g} \bullet \vec{g}}{\mid \vec{g} \mid} = 
    \mid \vec{g} \mid \label{f1.l}
\end{eqnarray}
\noindent
となる($ \mid \vec{g} \mid $ は$\vec{g}$の長さを表す)． 右辺も同様に書き換
えると
\begin{eqnarray}
\frac{m * rel(t_1^m) + (n-m) * rel(t_{m+1}^n)}{n} 
  =  \frac{m * \mid \vec{g_1} \mid + (n-m) * \mid \vec{g_2} \mid}{n} \label{f1.r}
\end{eqnarray}
\noindent
のようになる． ここで 重心の定義から
\begin{eqnarray}
n\vec{g} = n * \frac{1}{n} \sum_{i = 1}^n \vec{x_i} 
         = \sum_{i = 1}^m \vec{x_i} + \sum_{i = m+1}^n \vec{x_i}
         = m\vec{g_1} + (n-m)\vec{g_2} 
\end{eqnarray}
が成立しているので，(\ref{f1.r})の値は(\ref{f1.l})と同じか大きい． 
なお，等号が成立するのはベクトル$\vec{g}, \vec{g_1}, \vec{g_2}$の向
きが同じ時である． 
\begin{flushright}
(証明終)
\end{flushright}
\end{quotation}

式(\ref{f1})の$T$の部分に $ C_m(S, u_1^m) = u_1, \ldots, u_m, z_{m+1}, 
\ldots,  z_n = u_1^m, z_{m+1}^n$ を代入すると次の式が得られる．
\begin{eqnarray}
rel(C_m(S, u_1^m)) \leq  \frac{m * rel(u_1^m) + (n-m) * rel(z_{m+1}^n)}{n} \label{cent}
\end{eqnarray}

一方， $B(S)$の定義より
\begin{eqnarray}
rel(z_{m+1}^n) \leq rel(B(s_{m+1}^n)) \label{tcbest}
\end{eqnarray}
であるから，(\ref{tcbest})と(\ref{cent})を組み合わせれば
不等式(\ref{bound})が得られる．

\begin{flushright}
(証明終)
\end{flushright}



\bibliographystyle{jnlpbbl}
\bibliography{v07n3_05}


\begin{biography}
\biotitle{略歴}
\bioauthor{菊井 玄一郎}{
1986年京都大学工学部電気工学第二専攻修士課程修了.
同年NTTに入社，現在に至る．自然言語処理，特に自動翻訳，多言語情報検索
等の研究開発に従事．
1990年から1994年までATR自動翻訳電話研究所に出向．
1997年7月より1年間Stanford大学CSLI研究員．}

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

\end{biography}
\end{document}



