
\newif\ifdraft \draftfalse
\documentstyle[jnlpbbl,epsf]{jnlp_j_b5}
\setlength{\topmargin}{-15mm}
\setlength{\oddsidemargin}{-5mm}
\setlength{\evensidemargin}{-5mm}

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

\newcommand{\Hline}{}
\newcommand{\subsc}[1]{}

\setcounter{page}{63}
\setcounter{巻数}{10}
\setcounter{号数}{1}
\setcounter{年}{2003} 
\setcounter{月}{1}
\受付{2002}{5}{30}
\再受付{2002}{9}{11}
\採録{2002}{10}{4}

\setcounter{secnumdepth}{2}

\title{情報検索のための表記の揺れに寛容な類似尺度}
\author{山本 英子\affiref{CRL} \and 武田 善行\affiref{TUT} \and 梅村  恭司\affiref{TUT}}
\headauthor{山本，武田，梅村}
\headtitle{情報検索のための表記の揺れに寛容な類似尺度}
\affilabel{CRL}{
通信総合研究所}
{Communications Research Laboratory}
\affilabel{TUT}{
豊橋技術科学大学情報工学系}
{Dept. of Information and Computer Sciences, \\
Toyohashi University of Technology}

\jabstract{
本論文では，情報検索のための表記の揺れに寛容な類似尺度を提案する． 
情報検索において，検索対象となるデータがさまざまな人によって記述されたものであ
るため，同じ事柄であっても表記が異なり，入力した文字列で意図した情報を得る
ことができない場合がある．人間ならば，表記が多少異なっていて（表記の揺れ
があって）も柔軟に対応し，
一致していると判断できるが，計算機はこの柔軟性を備えていない． 
表記の揺れに対応することができる尺度として編集距離が知られているが，
実際にこの尺度を単純に類似尺度に変換したものを用いて情報検索を
行ってみたが，性能がでなかった．そこで，本論文では，この単純な類似尺度を
情報検索に適した表記の揺れに寛容な類似尺度に拡張することを試み，
その結果，この拡張によって検索性能が向上したことを示す．
さらに，提案する類似尺度を組み込んだ情報検索システムを構築し，
多くの情報検索システムに用いられている一般的な類似尺度と
同等以上の検索性能を実現できたことを示す．
}
\jkeywords{表記の揺れ，編集距離，類似尺度，文字列重み}
\etitle{
An IR Similarity Measure which is Tolerant \\
for Morphological Variation
}

\eauthor{Eiko Yamamoto\affiref{CRL} \and 
	Yoshiyuki Takeda\affiref{TUT} \and 
	Kyoji Umemura\affiref{TUT}}

\eabstract{
In this paper, we propose a measure for information retrieval (IR). 
This measure is tolerant for morphological variation. 
When various persons describe the data to retrieve, their notations may 
vary even if the data describe the same topic. 
This variation prevents system to retrieve all of relevant documents for 
 the input sentence. 
Although human can handle this variation, computers usually can not
 handle this. 
Edit distance is a well-known measure that can
cope with this variation. 
We have used this measure for information retrieval and found that 
its precision is poor. 
Therefore, we propose to modify this similarity measure to be suitable 
for information retrieval. 
We show that this extension improves the performance. 
We also compared the proposed similarity measure with the popular 
similarity measures used in many information retrieval systems.
}
\ekeywords{Morphological variation, Edit distance, Similarity measure, 
String weight}
\def\argmax{}

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

\begin{document}
\maketitle
\thispagestyle{empty}


\section{はじめに}

情報検索において，検索対象となるデータはさまざまな人に記述されたものであり，同じ事柄を表す言葉であっても人によって表記が異なるために，ユーザは検索システムから意図した情報を得られないことがある．人間ならば柔軟に表記から意図を読み取り対応できるが，機械はこの柔軟性を備えていない．ここで考える表記の異なりとは，たとえば，「ウイルス」と「ウィルス」，「コンピュータ」と「コンピューター」といった一般的な表記の揺ればかりでなく，その他「機械を使って翻訳する」という事柄を表すために，ある人は「機械翻訳」，別の人は「機械による翻訳」と多少表現が異なるといった表記の違いといったあいまいな表現のことである．本研究では，このようなあいまいな表現を合わせて「表記の揺れ」と呼ぶ．情報検索においてあいまいな表現は性能
低下を招く．日本語には表記の揺れが多く存在するために，日本語における情報検索は
難しいものである．そこで，表記の揺れに対応できる類似尺度が必要で
ある．
これまでに，表記の揺れに対応できる尺度として，編集距離
\cite{Korfhage97}が知られている．
編集距離は一方の文字列をもう一方の文字列に一致させるために必要な最小限の
編集操作の数である．編集操作には挿入，削除，置換があり，編集操作の数を距離
として考える．このため，編集距離は二つの文字列の不一致な文字を計数する相違尺
度とみることができる．
そこで，本論文ではまず，この編集距離を一致する文字を計数する類似尺度
に変換し，情報検索テストコレクションNTCIR1\cite{Kando98,Kageura97}を
用いて実験を行ったが，その結果は満足できるものではなかった．
その原因の一つは，文字をすべて同等に扱い，
文章の意味に大きく関わるような文字と
表記の揺れとなりうる文字を区別せずに計数したことにあると考えた．
たとえば，ひらがなは助詞や助動詞を表現するために用いられ
ることが多く，漢字は名詞や動詞の表記に用いられるため，ひらがなの一致と漢字
の一致では直感的にも重要さが異なるにもかかわらず，同じように一致した文字
を計数してしまうことである． 
もう一つの原因は，編集距離の定義に使われている編集操作が一文字に限られてい
たことにあると考えた．
たとえば，連続した三文字が一致した場合と
不連続な三文字が一致した場合
では直感的にも重要さが異なるにもかかわ
らず，同じように一致した文字を計数してしまうことである．

本論文では，この二つの原因を解消するために，一致した
文字に対して重み付けを行い，次に一致した文字列に対応できるように，
編集距離を変換した類似尺度の拡張を試みる．
そして，編集距離から最終的に本論文で提案する類似尺度に到達する過程で
定義する類似尺度を組み込んだシステムを構築し，
類似尺度を拡張することによって表記の揺れに寛容な性質を
損なうことなく，情報検索性能が向上するかを検証する．
さらに，一致した文字列に対する重みをその文字列が持つ$IDF$に基づくスコアと
するという条件の下で，類似尺度の違いによる情報検索性能の差を
検証する．すなわち，
本論文で提案する表記の揺れに寛容な類似尺度を組み込んだ情報検索システムと，
形態素解析によって得られた単語を一致する文字列の単位とし，その単語が持つ
$tf\cdot IDF$を重みとして累計するシステム，{\it ngram}を一致する文字列の単位と
し，その{\it ngram}が持つ$IDF$を重みとして累計するシステムと比較する．
実験結果において，本論文で提案する類似尺度を用いたシステムが，従来法である
単語に基づくシステムや{\it ngram}に基づくシステムと
同等以上の検索性能を実現できたことを示す．

この論文の構成は次のとおりである．2節では，編集距離から本論文で提案する類似
尺度に到達するまでの過程をその過程で定義される類似尺度とともに示す．
3節では，本論文で用いる重みを明示する．
4節では，本論文で行った情報検索性能を測るための実験の概要を示す．
5節では，2節で定義した類似尺度の検索性能が実際に
定義した順に向上しているかと表記の揺れに寛容な性質が損なわれていないか
を検証する．
6節では，5節の結果を踏まえ，本論文で提案する類似尺度の検索性能を測るために，
比較対象としたシステムについて説明した後，検索性能の比較を行う．
7節でこれまで示した実験結果から考察を述べ，最後にまとめる．

\section{編集距離の類似尺度への変換とその拡張}

本論文では，検索性能の低下を招く表記の揺れに寛容な類似尺度を提案する．
そのために，まず編集距離を類似尺度に変換し，次に一致した文字の重みを加算す
る類似尺度に拡張し，最後に一致した文字列の重みを加算する類似尺度に拡張する．
本節では，この三つのステップ毎に定義した類似尺度を示すことで，本論文で
提案する類似尺度が考慮する性質を明示する．

\subsection{編集距離の類似尺度への変換}

情報検索において，検索対象となるデータに存在する表記の揺れは検索性能の
低下を招くものである．
そこで，本論文では，表記の揺れに対応することができる尺度としてよく知られて
いる編集距離に基づく類似尺度を考えた．

編集距離（またはレーベンシュタイン距離）は，
二つの文字列の距離として，それらを一致させるために必要な
文字の削除，挿入，置換操作の回数を距離として考える方法である．
この距離はダイナミックプログラミングを用いて計算できる．
次に，編集距離$DST_e$の定義を示す．
\begin{df}　編集距離

$\alpha,\beta$を文字列，$x,y$を異なる文字，``"を空文字列とする．
関数$MIN$は与えられた引数のうちもっとも小さい値を返す関数とする．
\begin{itemize}
 \item 両方とも空文字のとき~~~~
	   $ DST_e(``",``")=0.0 $
 \item 長さ1文字以下の異なる文字列のとき~~~~ 
	   $ DST_e(x,y)=1.0 $
 \item 先頭の1文字が同じとき
\[ DST_e(x\alpha,x\beta)=MIN(DST_e(\alpha,x\beta)+1.0,
DST_e(x\alpha,\beta)+1.0,
DST_e(\alpha,\beta)) \]
 \item 先頭の1文字が異なるとき($x \neq y$)
\[ DST_e(x\alpha,y\beta)=MIN(DST_e(\alpha,y\beta)+1.0,
DST_e(x\alpha,\beta)+1.0,
DST_e(\alpha,\beta)+1.0) \]
\end{itemize}
\end{df}
この定義で示すように，編集距離は不一致な文字を数えることによって
二つの文字列の相違度を測っている．このため，編集距離は相違尺度とみる
ことができる．
定義から，編集距離は相違度が最小になるように，関数$MIN$を用いて不一致な文
字の位置を決定している．
この部分が編集距離に表記の揺れに対応できる性質を持たせている．二つの
文字列全体をみて，もっとも相違が小さくなるように試行錯誤することによって，
表記の揺れがあっても類似したものとみなせる定義式となっている．

本論文では，情報検索に適した編集距離に基づく類似尺度を提案するための第一ス
テップとして，この定義を変形して，相違尺度である編集距離を類似尺度に変換する．
具体的には，編集距離とは逆に類似度が最大になるように，関数$MIN$の代わりに関数$MAX$を用いて
一致する文字の位置を決定する尺度に変換する．
本論文では，この尺度を「単純編集類似度」と呼ぶことにした．
この尺度と編集距離との違いは類似度を最大にするか相違度を最小にするかの違い
だけなので，編集距離の持つ表記の揺れに寛容な性質は損なわれていない．
次に単純編集類似度$SIM_1$の定義を示す．
\begin{df} 単純編集類似度

$\alpha,\beta$を文字列，$x,y$を異なる文字，``"を空文字列とする．
関数$MAX$は与えられた引数のうちもっとも大きい値を返す関数とする．
\begin{itemize}
 \item 両方とも空文字のとき~~~~
	   $ SIM_1(``",``")=0.0 $
 \item 長さ1文字以下の異なる文字列のとき~~~~
	   $ SIM_1(x,y)=0.0 $
 \item 先頭の1文字が同じとき
\[ SIM_1(x\alpha,x\beta)=MAX(SIM_1(\alpha,x\beta),
SIM_1(x\alpha,\beta),
SIM_1(\alpha,\beta)+1.0) \]
 \item 先頭の1文字が異なるとき($x \neq y$)
\[SIM_1(x\alpha,y\beta)=MAX(SIM_1(\alpha,y\beta),
SIM_1(x\alpha,\beta),
SIM_1(\alpha,\beta)) \]
\end{itemize}
\label{sim1}
\end{df}

\subsection{文字重み編集類似度への拡張} 

単純編集類似度はすべての文字を同等に扱うため，一致する文字の重みはすべ
て1.0である．
しかし，一致した文字が内容語に含まれる文字である場合と機能語に含まれる
文字である場合とでは，情報検索
においてその文字の貢献度は異なる．
これは，意味に大きく関わる文字と表記の揺れとなりうる文字の貢献度の
違いに相当する．
一般に，情報検索の性能を向上させるために機能語を考慮せず，内容語だけを考慮
するシステムが多く存在する．
これは，機能語よりも内容語のほうが検索性能に貢献する度合いが高いためである．
日本語における機能語はたとえば，「は」，「が」，「を」，「の」，「では」や
「〜する」，「〜である」，「〜した」，「〜でない」，「〜しない」
などであり，主にひらがなで構成されている．
一方，内容語は主に漢字やカタカナで構成されている．カタカナは主に外来語を構
成している．
このような背景から，情報検索に適した編集距離に基づく類似尺度を提案するための
第二ステップとして，文字が一致した場合，常に1.0を加算するのではなく，
一致した文字が持つ重みを加算する類似尺度に単純編集類似度を拡張する．
言い換えると，この類似尺度は単純編集類似度の一般化である．
本論文では，この類似尺度を「文字重み編集類似度」と呼ぶことにした．

また，編集距離（レーベンシュタイン距離）
に関して各操作に重みを持たせた重みづきレーベンシュタイン距離がある\cite{Kohonen95}．
この距離では，操作ごとに対象となる文字に関する重みを持つ．ここで，
文字に関して操作ごとに重み付けるのではなく，その文字に対して
どの操作が行われても文字が持つ唯一の重みを付けると，
編集距離（レーベンシュタイン距離）から単純編集類似度への変形の
ように，重みづきレーベンシュタイン距離を文字重み編集類似度に変形することが
できる．
次に文字重み編集類似度$SIM_2$の定義を示す．
\begin{df} 文字重み編集類似度

$\alpha,\beta$を文字列，$x,y$を異なる文字，``"を空文字列とする．
関数$Score(z)$は文字$z$が持つ重みを返す関数，
関数$MAX$は与えられた引数のうちもっとも大きい値を返す関数とする．
\begin{itemize}
 \item 両方とも空文字のとき~~~~
		$ SIM_2(``",``")=0.0 $
 \item 長さ1文字以下の異なる文字列のとき~~~~
		$ SIM_2(x,y)=0.0 $
 \item 先頭の1文字が同じとき
\[ SIM_2(x\alpha,x\beta)=MAX(SIM_2(\alpha,x\beta),
SIM_2(x\alpha,\beta),
SIM_2(\alpha,\beta)+Score(x)) \]
 \item 先頭の1文字が異なるとき($x \neq y$)
\[ SIM_2(x\alpha,y\beta)=MAX(SIM_2(\alpha,y\beta),
SIM_2(x\alpha,\beta),
SIM_2(\alpha,\beta)) \]
\end{itemize}
\label{sim2}
\end{df}
例を用いて，単純編集類似度と文字重み編集類似度の振る舞いの違いを示す．
\begin{ex} 文字重みの効果

文$\alpha, \beta, \gamma$がそれぞれ
\begin{quote}
  \begin{tabular}{ll}
   $\alpha$： & 「機械で自動的に翻訳するシステム」 \\
   $\beta$：  & 「自動翻訳システム」 \\
   $\gamma$： & 「人手で直感的に表示するシステム」 \\
  \end{tabular}
\end{quote}
であり，Score関数が次のように与えられたとする．
\begin{itemize}
 \item 文字$x$がひらがなの場合~~~~
	   $ Score(x)=0.0 $
 \item 文字$x$がひらがな以外であった場合~~~~
	   $ Score(x)=1.0 $
\end{itemize}
このとき，$\alpha$と$\beta$の類似度，$\alpha$と$\gamma$の類似度は表
 \ref{tab:character-weight}のようになる．
\begin{table}[htbp]
\caption{文字重みの効果}
\label{tab:character-weight}
\begin{center}
  \vspace{-1em}
  \begin{tabular}{|c||c|c|}\hline
    引数 & 単純編集類似度 & 文字重み編集類似度\\\hline\hline
    $\alpha,\beta$  &  8.0   &   8.0  \\\hline
    $\alpha,\gamma$ &  9.0   &   5.0  \\\hline
  \end{tabular}
 \end{center}
\end{table}
\label{ex:weight}
\end{ex}
この例において，
$\alpha$と$\beta$は人間であれば類似していると判断される文である．
これらの文に対する類似度は一致する文字がすべてひらがな以外であるため，
単純編集類似度でも文字重み編集類似度でも同じ類似度となる．
一方，$\alpha$と$\gamma$は人間であれば類似していないと判断される
文である．
これらの文に対して，
単純編集類似度は一致する文字がひらがなであっても同じ重みを加算するため
，高い類似度を与えてしまう．しかし，文字重み編集類似度は
類似していると判断される$\alpha$と$\beta$が持つ類似度よりも低い
類似度を与えることができている．
このことより，単純な重み付けでも，二つの文が類似するかしないかの
判断に役立つことが予想できる．

\subsection{文字列重み編集類似度への拡張} \label{sim3}

例\ref{ex:weight}の$\beta$は「自動翻訳システム」であり，
この文は「自動」，「翻訳」，「システム」という三つの内容語で構成されている．
これらの単語のうち，漢字で構成されるものは文字自体が意味を表している
ために一文字だけでも検索に貢献する場合があるが，「システム」は
ほとんどの場合，一文字では意味を表すことができないカタカナで
構成されている．
「システム」は構成する文字が連続して現れることによって意味を表す単語となる．
同様に，ひらがなで構成される文字列でも連続して現れることによって貢献する
場合がある．
このような場合，情報検索において，構成する文字それぞれの貢献よりも連続して
現れることによって構成された文字列のほうが貢献度が高いことが知られ
ている．
言い換えると，一致した文字列を構成する文字毎に重みを加算するのではなく，
文字列が持つ重みを加算したほうが検索性能が向上する可能性がある
ということである．
多くの情報検索システムに用いられている単語を単位とし，一致した単語が持つ重
みを加算することによって類似度を求める尺度があるが，この尺度もこの可能性に基
づくものとみることができる．さらに，一単語より長い文字列が検索に大きく貢献
するように{\it ngram}を単位とし，一致した{\it ngram}の重みを加算することによって
類似度を求める尺度もある．この尺度は一致する文字列の長さに重きを置く尺度で
ある．人間は一致する部分が長ければ長いほど，二つの文は類似していると
判断することが多い．このため，一致する文字列の長さに重きを置くことは
人間の直感に合致している．
このような背景から，情報検索に適した編集距離に基づく類似尺度を提案するための
最終ステップとして，一致した文字ではなく，一致した文字列が持つ重みを加算す
る類似尺度に文字重み編集類似度を拡張する．
言い換えると，この類似尺度は文字重み編集類似度の一般化である．
本論文では，この類似尺度を「文字列重み編集類似度」と呼ぶことにした．
次に文字列重み編集類似度$SIM_3$の定義を示す．
\begin{df} 文字列重み編集類似度 \label{df:sim3}

$\alpha,\beta,\gamma,\delta$を文字列，$\xi$を長さ1以上の文字列，
$x,y$を文字とする．
関数$Score(\epsilon)$は文字列$\epsilon$が持つ重みを返す関数，
関数$MAX$は与えられた引数のうちもっとも大きい値を返す関数とする．
\begin{itemize}
\item 両方とも空文字のとき~~~~
$ SIM_3(``",``")=Score(``") $
\item それ以外のとき
\begin{eqnarray*}
&&\hspace*{-2mm}	SIM_3(\alpha,\beta)= 
		MAX(SIM_{3s}(\alpha,\beta),SIM_{3g}(\alpha,\beta))	
\end{eqnarray*}
\begin{itemize}
\item 一致している最大の文字列を$\xi$として
\begin{eqnarray*}
&&\hspace*{-8mm}	SIM_{3s}(\xi\alpha,\xi\beta)=
	MAX(Score(\gamma)+SIM_3(\delta\alpha,\delta\beta))\\
&&\hspace*{-6mm}	for~all~\gamma;~for~all~\delta; such~that~\xi=\gamma\delta
\end{eqnarray*}
\item そのような文字列が存在しないとき~~~~
$ SIM_{3s}(\alpha,\beta)=0.0 $
\item 任意の文字列について
\[ SIM_{3g}(x\alpha,y\beta)=
MAX(SIM_3(\alpha,y\beta),
SIM_3(x\alpha,\beta),
SIM_3(\alpha,\beta)) \]
\end{itemize}
\end{itemize}
\end{df}

\section{本論文で用いる重み}

例\ref{ex:weight}では，ひらがな以外の文字に重みを持たせたが，文字に持たせる重みを
調節することによって，検索性能を大きく向上することが容易に予測できる．
情報検索だけでなく他の分野においても，適した重みを決定することは難しく，
多くの場合，経験によって決められることが多い．
情報検索においては，検索対象となるデータによって調整することが広く行われている．
本論文では，情報検索において重みの基本とされている文字列が一致したときの情
報量に相当する$IDF$(Inverse Document Frequency)を用いることにした．
また，通常の$IDF$は単語を対象とするが，文字列を対象とする$IDF$とした．
これは，提案する類似尺度が{\it ngram}を対象とするためである．
本論文で扱う類似尺度が用いる重みはすべて$IDF$に基づくものとし，
類似尺度の定義の違いによる検索性能の比較を行った．
次に本論文で提案する類似尺度に用いた重みを返す関数$Score$を示す．
ここで，$df(\xi)$は長さ1以上の文字列$\xi$が出現する
ドキュメントの数，$N$はドキュメントの総数とする．
\begin{itemize}
\item 空文字ならば，~~~~
$ Score(``")=0.0 $
\item それ以外ならば，~~~~
$ Score(\xi)=-\log_2(df(\xi)/N) $
\end{itemize}
本論文の目的は検索性能の低下を招く表記の揺れに寛容な類似尺度を提案
することであるため，最適な重みについては今後の課題と考えている．

\section{実験の概要}

本論文では，提案する類似尺度の情報検索性能を評価するために，
実験対象となる類似尺度を組み込んだ
情報検索システムをそれぞれ作成し，検索性能を比較した．
まず，単純編集類似度，文字重み編集類似度，文字列重み編集類似度の情報
検索における性能を比較し，順に拡張したことによって表記の揺れに寛容な性質を
損なうことなく，予想通り性能の向上を計ることが
できているかを検証する．
そして，この検証においてもっとも高い性能を持つ類似尺度の検索性能を，多くの
情報検索システムに用いられる類似尺度の基となっている二つの類似尺度と比較する．

実験では，情報検索テストコレクション
NTCIR1\cite{Kando98,Kageura97}を使用した．質問はキーワードではなく文
章で表され，検索対象となる文書は技術論文の抄録である．
コレクションには，質問集合83問（訓練用30問，本番用53問）と文書集合33万件，
正解集合が含まれている．
図\ref{fig:query}と図\ref{fig:document}にNTCIR1の質問と文書の記述例を
それぞれ示す．
\begin{figure} [htbp]
\vspace*{-1em}
\begin{center}
\fbox{\epsfile{file=query-image2.eps,scale=0.6}}
\caption{質問の例}
\label{fig:query}
\vspace{0.5em}
\fbox{\epsfile{file=document-image2.eps,scale=0.6}}
\caption{文書の例}
\label{fig:document}
\end{center}
\end{figure}
質問の記述は「タイトル」，「検索要求」，「検索要求説明」，「概念」，「分野」で
構成され，検索対象となる文書の記述は「タイトル」，「著者名」，「抄録」，「分野」などで
構成されている．
本論文では，質問の「検索要求」部分の文章と，文書の「抄録」
部分を連結した文章との類似度を測ることによって，情報検索を行った．

システムから得る結果は，質問ごとに類似度を高い順に並べたランキングリストで
ある．
性能評価は，この実験結果の上位1000件に対する
11点平均精度を比較することによって行った．

\section{編集類似度の性質および検索性能の検証} \label{comp-sim}

本節では，単純編集類似度($SIM_1$)，文字重み編集類似度($SIM_2$)，文字列重
み編集類似度($SIM_3$)の情報
検索における性能を比較し，順に拡張したことによって表記の揺れに寛容な性質を
損なうことなく，予想通り性能の向上を計ることができているかを検証する．
実験結果を表\ref{sim-11pt-comp}--表\ref{sim-win-comp}に示す．
まず，情報検索性能について検証する．
表\ref{sim-11pt-comp}は，単純編集類似度，文字重み編集類似度，
文字列重み編集類似度をそれぞれ用いたシステムで訓練用30問について情報検索を
行った結果の11点平均精度(11 point average precision)に示す．
\begin{table}[bht]
\vspace{-1em}
\caption{編集類似度の11点平均精度（訓練課題30問）}
\vspace{-1em}
\label{sim-11pt-comp}
\begin{center}
  \begin{tabular}{|c||c|c|c|}\hline
    類似尺度 & $SIM_1$ & $SIM_2$ & $SIM_3$ \\\hline\hline
    11-pt & 0.135 & 0.203 & 0.281 \\\hline
  \end{tabular}
\end{center}
\caption{質問ごとの11点平均精度}
\label{sim-each-comp}
\vspace{-1em}
\begin{center}
\hspace*{-1em}
\begin{tabular}{|c||c|c|c||c||c|c|c|}\hline
{\bf 質問番号}&{\bf $SIM_1$}&{\bf $SIM_2$}&{\bf $SIM_3$}&
{\bf 質問番号}&{\bf $SIM_1$}&{\bf $SIM_2$}&{\bf $SIM_3$}\\\hline\hline
 1 & 0.2611 & 0.2675 & 0.3006 & 16 & 0.5577 & 0.6777 & 0.8263\\ \hline
 2 & 0.0159 & 0.6025 & 0.6704 & 17 & 0.0009 & 0.0283 & 0.0407\\ \hline
 3 & 0.0006 & 0.0023 & 0.0148 & 18 & 0.0380 & 0.1288 & 0.0980\\ \hline
 4 & 0.0049 & 0.2929 & 0.3136 & 19 & 0.4026 & 0.4487 & 0.6890\\ \hline
 5 & 0.0006 & 0.0009 & 0.0013 & 20 & 0.2683 & 0.6493 & 0.7775\\ \hline
 6 & 0.0212 & 0.1626 & 0.1890 & 21 & 0.0215 & 0.1339 & 0.1583\\ \hline
 7 & 0.0022 & 0.0000 & 0.0024 & 22 & 0.2068 & 0.2525 & 0.2493\\ \hline
 8 & 0.0020 & 0.0003 & 0.2119 & 23 & 0.2308 & 0.3596 & 0.3481\\ \hline
 9 & 0.1050 & 0.0398 & 0.2402 & 24 & 0.2903 & 0.3153 & 0.3234\\ \hline
10 & 0.1052 & 0.3669 & 0.3618 & 25 & 0.0248 & 0.1324 & 0.4877\\ \hline
11 & 0.3268 & 0.2194 & 0.2638 & 26 & 0.4438 & 0.1266 & 0.5136\\ \hline
12 & 0.0742 & 0.0224 & 0.1566 & 27 & 0.0259 & 0.1784 & 0.2556\\ \hline
13 & 0.0057 & 0.0330 & 0.0655 & 28 & 0.0478 & 0.0518 & 0.0589\\ \hline
14 & 0.2980 & 0.3646 & 0.4257 & 29 & 0.1753 & 0.0501 & 0.1151\\ \hline
15 & 0.1001 & 0.1528 & 0.2116 & 30 & 0.1025 & 0.0349 & 0.0527\\ \hline
\end{tabular}
\end{center}
\caption{類似尺度ごとの比較}
\label{sim-win-comp}
\begin{center}
\vspace*{-1em}
\begin{tabular}{|c||c|c|}\hline
{X vs Y}&{X win}&{Y win}\\\hline\hline
{$SIM_1$ vs $SIM_2$} & 8  & 22\\\hline
{$SIM_2$ vs $SIM_3$} & 4 & 26 \\\hline
{$SIM_1$ vs $SIM_3$} &  3 & 27 \\\hline
\end{tabular}
\end{center}
\vspace*{-1em}
\end{table}
11点平均精度は情報検索における一般的な評価基準で，再現率(recall)が
0\,\%，10\,\%，20\,\%，30\,\%，40\,\%，50\,\%，60\,\%，70\,\%，80\,\%，90\,\%，100\,\%の11点における
適合率(precision)の平均値である\cite{Manning99}．
この表はこの実験における各システムの検索性能を表し，
文字列重み編集類似度が
単純編集類似度や文字重み編集類似度より情報検索に有効であることを示している．
表\ref{sim-win-comp}は，訓練用30問において
一方の編集類似度が他方の編集類似度より検索に有効であった質問を表
\ref{sim-each-comp}を用いて数えた結果を示す．
この表は，この実験において，文字重み編集類似度が単純編集類似度よりも
多くの質問に対して有効に働き，文字列重み編集類似度が
単純編集類似度や文字重み編集類似度よりもさらに多くの質問に対して有効に働く
ことを示している．
たとえば，「各質問について$SIM_2$より$SIM_1$が高い11点平均精度を出す確率が
1/2以下のとき，$SIM_2$が$SIM_1$より30個のうち22個以上の割合で性能が高い」
という仮説を立てた場合，危険率$8.1 \times 10^{-3}$以下で仮説は棄却される
．これは，$SIM_2$が$SIM_1$より高い性能を出す確率は1/2以上であることを
示し，$SIM_2$と$SIM_1$には有意な差があることがわかる．
また同様に，$SIM_3$と$SIM_1$には危険率$3.0 \times
10^{-5}$以下のレベルで有意な差があり，
$SIM_3$と$SIM_2$には危険率$4.2 \times 10^{-6}$以下のレベルで
有意な差があることがわかる．
以上のことから，編集距離に基づく類似尺度を拡張することによって
情報検索性能を向上していることが確認できる．

次に，表記の揺れに寛容な性質が損なわれていないかを検証する．
例として，図\ref{fig:query}に示す質問20を取り上げる．
検索に使うこの質問の検索要求は「日本語文におけるカタカナ外来語の研究」である．
図\ref{fig:document}に示す文書は質問20に関連する文書である．
まず，単純編集類似度から文字重み編集類似度に拡張した場合，表記の揺れに寛容
な性質が損なわれていないかを検証する．
これらの質問と文書において単純編集類似度と文字重み編集類似度は同じ「文，る，カ，タ，カ，
ナ，外，来，語，の」の10文字が一致する．
重みが影響するのは，質問に現れる文字が文書ではそれらの文字が質問に現れる順
とは異なり，前後に交換されている場合に考えられる．
たとえば，質問に「有無」が現れ，文書に「・・は無いが，・・は有る」と，
「有」と「無」が逆順に現れるとき，もし「無」が持つ重みのほうが大きい場合，
文字重み編集類似度は前にある「有」ではなく，
後ろにある「無」の重みを加算するが，
単純編集類似度はどちらを選んでも同じである．
このため，単純編集類似度と文字重み編集類似度において，
稀に選択された文字が異なると考えられるが，
サンプルで調査したすべての質問においてはすべて同じ文字を選択していた．
これは，単純編集類似度を文字重み編集類似度に拡張しても
表記の揺れに寛容な性質を保持しているということを表している．
図\ref{fig:document}の文書を，
単純編集類似度は181位，文字重み編集類似度は10位に位置
付けている．
表\ref{sim-each-comp}に示す質問20における11点平均精度を見ると，単
純編集類似度よりも文字重み編集類似度のほうが精度が高い．これは，
表記の揺れに寛容な性質を持ち，一致した文字の重みを考慮したことによって
検索性能が向上したことを示している．

一方，文字列重み編集類似度は「文，る，カタ，カナ，外，来語，の」の7つの文
字列が一致する．これは，単純編集類似度と文字重み編集類似度で選択され
た10文字と同じである．
これは，文字重み編集類似度を文字列重み編集類似度に拡張しても表記の揺れに寛
容な性質を保持しているということを表している．
実際に，図\ref{fig:document}の文書に対して，文字重み編集類似度は
4.44，文字列重み編集類似度は12.37を得ている．また，この文書を
文字重み編集類似度は10位に位置付けているが，文字列重み編集類似度は6位に
位置付けている．
表\ref{sim-each-comp}に示す質問20における11点平均精度を見ると，
文字重み編集類似度よりも文字列重み編集類似度のほうが精度が高い．これは，
表記の揺れに寛容な性質を持ち，一致した文字列の重みを考慮したことによって
検索性能が向上したことを示している．

以上のように，類似尺度を拡張しても表記の揺れに寛容な性質を損なっていない
ことをサンプルで確認した．

\section{基本的な類似尺度との検索性能比較} 

\ref{comp-sim}節に示した実験において，本論文で提案する三つの編集類似度の
なかで，
文字列重み編集類似度がもっとも情報検索において有効であることがわかった．
本節では，提案する文字列重み編集類似度の検索性能を，多くの
情報検索システムに用いられる類似尺度の基となっている類似尺度と比較する．
まず，情報検索において基とされる類似尺度を用いたシステムの概要を示
す．本論文では，形態素解析を利用して内容語を抽出し，
質問と文書のどちらともに存在する内容語の
重みを加算する類似尺度と，質問と文書のどちらとも
に存在する文字列({\it ngram})の重みを加算する類似尺度を選び，
これらの尺度を用いた二つのシステムをベースラインシステムとした．

\subsection{ベースラインシステム：BD}

本論文では，一つ目のベースラインシステムとして，形態素解析を利用し内容語を抽出し，
質問と文書のどちらともに存在する内容語の重みを加算することによって類似度を
測るシステムを作成した．本論文では，このシステムを辞書を用いる
ことから「BD(baseline-dictinary)」と呼ぶことにした．
形態素解析には，日本語形態素解析プログラム「茶筌」
\cite{Matsumoto97}を用いた．「茶筌」は大きな日本語の単語辞書を使って文
字の列を単語に区切り，品詞を割り当てるシステムである．

BDシステムはまず，質問と文書それぞれに対して形態素解析を行い，
そして，解析結果から内容語（名詞，動詞，未定義語）の原形を抽出し，類似度を測るため
の内容語だけが並ぶ質問集合のファイルと文書集合のファイルを作成する．
BDシステムに原形を採用した理由は，文章に現れる内容語の形そのままを対象とした場合と
原形を対象とした場合の検索性能を比較した結果，原形のほうが検索性能が高かったためである．
これらの二つのファイルを用いて，Salton\cite{Salton88}が用いている多くの情
報検索手法の基となっている内積スコアリング関数を用いて類似度を求める．
内積スコアリング関数
は文字列重み編集類似度に用いられる重み関
数と同じ$IDF(=-\log(df/N))$に基づく重み関数である．
このことから，辞書を用いて形態素解析
を行うことに関して比較することにした．
次にBDシステムに用いた類似尺度$SIM_{dict}$の定義を示す．
\begin{df}
$t$は比較される各々の文字列両方に現われる単語，$tf(t)$はその
ドキュメントの単語$t$の出現頻度(term frequency)，
$df(t)$は単語$t$が出現するドキュメントの数(document frequency)，
$N$はドキュメントの総数とする．
\[ SIM_{dict} = \sum_{t} tf(t) \cdot (- log_2(df(t) / N)) \]
\end{df}

\subsection{ベースラインシステム：BN}

本論文では，二つ目のベースラインシステムとして，質問と文書のどちらとも
に存在する文字列({\it ngram})の重みを加算することによって類似度を測るシステム
を作成した．本論文では，このシステムを{\it ngram}をマッチングの対象とすることから
「BN(baseline-{\it ngram})」と呼ぶことにした．
BNシステムは，質問と文書のどちらともに現れる文字列を検出し，
文字列重み編集類似度に用いられるScore関数を用いて類似度を求める．
通常，処理効率を考え，長さ2のバイグラム(bigram)または長さ3のトライグラム(trigram)
のような短い{\it ngram}だけをマッチングの対象とするが，
本論文では，
$SIM_3$がすべての{\it ngram}を対象としているので，条件をそろえるために，
すべての{\it ngram}を対象とすることにした．
一般には，\cite{Fujii93}が示したように，
短い{\it ngram}は日本語にはかなり効果的であることが報告されている．
しかし，実際にNTCIR1において短い{\it ngram}に制限した場合と制限しない場合の検
索性能の比較を行った結果，制限しない場合のほうが高い性能を得たため，
バイグラムやトライグラムより長い{\it ngram}を考慮することにした．
また，提案する文字列重み編集類似度においても扱う文字列の長さを制限していないので，
条件は同じである．

実際に長い{\it ngram}を考慮することは，複合語のマッチングを行う
情報検索\cite{Yamada97}の報告で，共起情報を用いない
ケースに相当する．DPも長い{\it ngram}を検出するので，BNを比較対象と
した．
BNシステムはマッチングの対象が文字列重み編集類似度と同じ文章にある部分文字
列({\it ngram})である．
BNシステムと文字列重み編集類似度の唯一の違いは，類似尺度の定義が語順
を無視した重みの総和をとるか語順を保存した重みの合計の最大値を
とるかの違いである．
このことが表記の揺れに寛容な性質を持つ
か持たないかの差となっていると予想される．このため，本論文では，
この二つの類似尺度を表記の揺れに対する振る舞いについて比較することにした．
次にBNに用いた類似尺度$SIM_{ngram}$の定義を示す．
\begin{df}
$\alpha,\beta,\xi,\eta$ を文字列とする．$\alpha_{ik}$を$i$番目の文字から
$i+k-1$番目の文字までの$\alpha$の部分文字列とし，
$\beta_{jk}$を$j$番目の文字から$j+k-1$番目の文字までの$\beta$の
部分文字列とする．また，$Score$は$IDF$に基づく文字列から正の実数値を
求める関数とする．
\[SIM_{ngram} = \sum_{i,j,k} Comp(\alpha_{ik},\beta_{jk})\]
ただし，$Comp(\xi,\eta)$は次のように定義され，ここで現れる$Score(\xi)$は
\ref{sim3}節に示したものと同じである．
\begin{itemize} 
\item $\xi = \eta$ならば，~~~~ $Score(\xi) = - log_2(df(\xi)/N)$
\item $\xi \neq \eta$ならば，~~~~ $0.0$ 
\end{itemize} 
\end{df}

\subsection{検索性能の比較}

本節では，本論文で提案する文字列重み編集類似度($SIM_3$)を用いたシステムと，
$SIM_{dict}$を用いたBDシステム，$SIM_{ngram}$を用いたBNシステムの検索性能
を比較する．
本論文では，文字列重み編集類似度を用いたシステムをダイナミックプログラミン
グを用いて計算できることから，「DP」と呼ぶことにした．

\begin{table}[htb]
\caption{システムの11点平均精度（訓練課題30問）}
\vspace{-1.2em}
\label{tab:all-prec}
\begin{center}
\begin{tabular}{|c||c|c|c|} \hline
システム & {\bf BD} & {\bf BN} & {\bf DP}\\\hline\hline
11-pt & 0.154 & 0.164 & 0.281 \\\hline
\end{tabular}
\vspace{-0.3em}
\end{center}
\caption{それぞれのシステムの質問ごとの11点平均精度}
\vspace{-1.2em}
\label{tab:precision}
\begin{center}
\hspace*{-2em}
\begin{tabular}{|c||c|c|c||c||c|c|c|}\hline
{\bf 質問番号}&{\bf BD}&{\bf BN}&{\bf DP}&
{\bf 質問番号}&{\bf BD}&{\bf BN}&{\bf DP}\\\hline\hline
 1 & 0.2462 & 0.2216 & 0.3006 & 16 & 0.0180 & 0.3275 & 0.8263\\ \hline
 2 & 0.2099 & 0.5022 & 0.6704 & 17 & 0.0471 & 0.0011 & 0.0407\\ \hline
 3 & 0.0257 & 0.0028 & 0.0148 & 18 & 0.0788 & 0.0051 & 0.0980\\ \hline
 4 & 0.1048 & 0.1815 & 0.3136 & 19 & 0.2091 & 0.4901 & 0.6890\\ \hline
 5 & 0.1046 & 0.0008 & 0.0013 & 20 & 0.5660 & 0.5705 & 0.7775\\ \hline
 6 & 0.0580 & 0.0221 & 0.1890 & 21 & 0.0881 & 0.0713 & 0.1583\\ \hline
 7 & 0.0005 & 0.0010 & 0.0024 & 22 & 0.0516 & 0.0703 & 0.2493\\ \hline
 8 & 0.0836 & 0.0086 & 0.2119 & 23 & 0.2003 & 0.1475 & 0.3481\\ \hline
 9 & 0.0157 & 0.0372 & 0.2402 & 24 & 0.1915 & 0.2887 & 0.3234\\ \hline
10 & 0.3751 & 0.2991 & 0.3618 & 25 & 0.6076 & 0.2291 & 0.4877\\ \hline
11 & 0.2533 & 0.0303 & 0.2638 & 26 & 0.1087 & 0.4665 & 0.5136\\ \hline
12 & 0.1008 & 0.1687 & 0.1566 & 27 & 0.0659 & 0.0696 & 0.2556\\ \hline
13 & 0.0707 & 0.0150 & 0.0655 & 28 & 0.0072 & 0.0435 & 0.0589\\ \hline
14 & 0.4107 & 0.3051 & 0.4257 & 29 & 0.1543 & 0.0882 & 0.1151\\ \hline
15 & 0.1538 & 0.1436 & 0.2116 & 30 & 0.0094 & 0.0142 & 0.0527\\ \hline
\end{tabular}
\end{center}
\vspace{-0.3em}
\caption{システムごとの比較}
\vspace{-1.2em}
\label{tab:comparison}
\begin{center}
\begin{tabular}{|c||c|c|}\hline
{X vs Y}&{X win}&{Y win}\\\hline\hline
{DP vs BD} & 23  & 7\\\hline
{DP vs BN} & 29 & 1 \\\hline
{BD vs BN} &  15 & 15 \\\hline
\end{tabular}
\end{center}
\end{table}
表\ref{tab:all-prec}
に33万件のドキュメントに対して30個の検索質問を行った場合の11点平均精度
を示す．
この表は実験において，DPがBDやBNよりも
精度が高かったことを示している．
表\ref{tab:comparison}
はそれぞれのシステムを二つずつ各質問について，表\ref{tab:precision}
に示す11点平均精度
を使って比較し，すべての質問について数値で判定した結果から作成した．
これらの表もまた，DPがBDやBNよりも精度が高いことを示している．

質問1に対して，三つのシステムは同じような性能
を示す．質問1は，用語と用語を構成する単語の多くがそれらの$IDF$重みによっ
て示されるようなよいキーワードである用語を含む質問であり，すべてのシス
テムにとって簡単な質問である．図\ref{fig:recall1and12}の左図に上位1000件の文書
に関する再現率を示す．この図から，三つのシステムは
比較の条件が揃っていることがわかる．
実験結果において，
表\ref{tab:comparison}から\ref{comp-sim}節に示すような仮説を立て，
検索性能を検証すると，
$DP$と$BD$には危険率$2.6 \times 10^{-3}$以下のレベルで
有意な差があり，$DP$と$BN$には危険率$2.9 \times 10^{-8}$以下の
レベルで有意な差があることがわかる．
\begin{figure}[htb]
\begin{center}
\fbox{\epsfile{file=dp-01and12-2.eps,scale=0.7}}
\caption{再現率：質問1「自立移動ロボット」，質問12「データマイニング」}
\label{fig:recall1and12}
\end{center}
\vspace{-3em}
\end{figure}

\subsection{BDとの振る舞いの差}

本論文の実験において，表\ref{tab:comparison}に示すように，
DPはBDと同等以上の性能を持つことを示している．
これは，未知語に対する振る舞いの違いによるものである．
辞書を利用するシステムは解析できない未知語が重要となる
質問に対応することが難しい．
たとえば，図
\ref{fig:recall1and12}の右図はそのような質問に関する再現率のグラフである．BDは
データマイニングを「デー」「タマ」「イニング」に分割してしまうため，その結果，情報検
索の性能が低い．NTCIR1において，このように未知語が重要となる質問がこの他
にも存在する．
辞書を利用するBDの場合，新しい単語が作成されるたびに辞書に単語を登録すれば語分割の失敗を避けることができるが，新しい単語に対する辞書のメンテナンスが必要である．
一方，BNとDPは辞書を利用しないため，このコストがかからないという利点を持っている．
しかし，未知語を学習することによって検索性能が向上することは明白である
ため，システムを相補的に用いることが理想である．

\subsection{実行時間}

実験における各システムの実行時間を表\ref{tab:cost}に示す．
BDはperlで記述し，他のシステムはCで記述したため，BDシステムの
実行時間は参考値であり，前処理となる文書頻度(document frequency)
の計算を除いた類似度計算のみの実行時間である．
\begin{table}[h]
\vspace*{-0.5em}
\caption{実行時間}\label{tab:cost}
\vspace*{-1em}
\begin{center}
\hspace*{-2em}
\begin{tabular}{|c||c|c|c|c|c|} \hline
システム & {\bf BD} & {\bf BN} & {\bf $SIM_1$} & {\bf $SIM_2$} & {\bf DP($SIM_3$)}
\\\hline\hline
総実行時間[sec] & 43947 & 2099 & 3257 & 3713 & 5302\\\hline
1質問当たり[sec] & 1464.9 & 70.0 & 108.6 & 123.8 & 176.7\\\hline
1ドキュメント当たり[msec] & 4.44 & 0.21 & 0.33 & 0.38 & 0.54\\\hline
\end{tabular}
\end{center}
\vspace*{-1.5em}
\end{table}
また，すべてのシステムは文書と質問を一つずつ比較するシステムであるため，
インデックスファイルは使用していない．
実験はVine Linux 2.0，CPU800MHz，メモリ1GBの計算機を用いて行った．
この表では，``総実行時間''は33万件のドキュメントに対して30個の質問を検索する
ことにかかった時間，``1質問当たり''は総実行時間を30で割った，1質問当たりに
かかる平均実行時間，``1ドキュメント当たり''は1質問当たりの時間を
33万で割った，1ドキュメントとの類似度を計算することにかかる平均実行時間である．
$BN$と$DP(SIM_3)$を比較すると，
実際のデータでの計算時間の差は2倍程度であった．
これは，
任意の文字列の文書頻度を高速に求められる方法
\cite{Yamamoto98}を利用した効果である．
そして，文字列重みを利用しても単純な編集距離の計算よりも桁違いに
遅くないことがわかる．
しかし，提案する類似尺度を用いたシステムは情報検索システムとして
実用的とは言えない．
本論文では，情報検索に利用できる表記の揺れに寛容な類似尺度の提案を目的とし
ているので，インデックスを利用する処理速度の向上は今後の課題と考えている．

\section{考察}


\subsection{単語の順序について}
定義\ref{df:sim3}に示すように，文字列重み編集類似度は一致する
文字列の重みにその文字列以外の部分の類似度を加算する操作をしている．
この定義では，質問と文書に二つずつ同一の文字が出現した
場合に，出現の順序が一致したときには加算操作の対象になるが，
順序が異なった場合には，加算の対象とならないため，結果的に
どちらかの重みが選ばれることになる．この
「順序が一致したときに，スコアが加算される」という性質は
単純編集類似度，文字重み編集類似度，文字列重み編集類似度に共通する性質である．
順序関係を保存しながら，
重みの合計が最大になるように部分文字列の組合せを探す尺度の
なかで文字列重み編集類似度はすべての文字列の重みを
考慮するということが特徴となっている．
キーワードの検索においても順序を保存することで
検索精度が向上するという報告\cite{Tanaka97}があるが，文字列重み
編集類似度はキーワードに限定せず質問を構成する文字列の順序を保存する．

また，順序情報を利用するという意味では，形態素解析を行い，内容語の列を作り
，その列が持つ順序情報を利用して検索性能を向上させてい
る研究\cite{Otake99}があるが，本論文で提案する手法では
形態素解析を行わない．さらに，修飾語の欠損と付加がある場合にも提案する手法
は対応できる．

\subsection{句の検出}

文字列重み編集類似度は，重みの合算の過程において類似判定に効果のある部
分文字列を選び出す処理を行っている．つまり，定義\ref{df:sim3}に示さ
れる定義式で関数$MAX$によって選び出された文字列は類似判定に効果がある文
字列として選び出されている．この一連の文字列は，検索に効果があるひとか
たまりと解釈できる．言い替えれば，文字列重み編集類似度によって，検索に
利用可能な「分離している複合語」を抽出していると解釈できる．
これは，類似判定ごとに「語」の定義を変更することで効果を上げている情報検索シス
テム\cite{Ozawa99}と同様に，情報検索のための句分割方法の
一つと解釈することもできる．

検索に効果がある文字列の集合を選ぶためによく用いられる方法は共起関係を利用
する方法である\cite{Takagi96}．文字列重み編集類似度で選び出される
文字列の集合は共起によるものとは異なる文字列となる．端的には，文字列
重みによるものは，$IDF$が高ければ統計的に独立に出現し，
共起関係にない文字列でもキーワードとして検出される．
実際に，文字列重み編集類似度
で選択された一群の文字列の性質を分析することは行う価値のある今後の課題で
ある．

\subsection{シソーラスの利用}

文字列の一致の検出を行うときに，シソーラスを利用する拡張が考えられる．
すなわち，質問中の文字列がシソーラスの見出し語にあるときは，その対応
する単語がドキュメントにあったときに文字列が一致しているとみなす拡張
である．
この方法を実装することは簡単であるが，適切な重みを何にするか，
実際に検索に効果があるかなどの問題が存在し，今後の課題である．

\section{まとめ}

本論文では，情報検索のための表記の揺れに寛容な類似尺度を提案し，
その検索性能を評価した．表記の揺れに対応できる尺度として編集距離が
知られているが，実際にこの尺度を単純に類似尺度に変換したものでは
性能がでない．
本論文では，表記の揺れに寛容な類似尺度を，情報検索に適するように，
文字列に対する重みを計算するように拡張した．
それを用いて情報検索による評価を行い，性能が向上したことを示した．
さらに，提案する類似尺度を組み込んだ情報検索システムを構築し，
多くのシステムに用いられている一般的な類似尺度と同等以上の検索性能を
実現できたことを示した．

\acknowledgment

本研究は住友電気工業株式会社の援助による成果です．
そして，本研究を進めるにあたって有意義なコメントを戴いた
AT\&TのKenneth W. Church氏と
筑波大学の山本幹雄助教授に深く感謝いたします．


\bibliographystyle{jnlpbbl}

\newcommand{\gengoshori}{}\newcommand{\kokuken}{}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Fujii, Croft}{Fujii, Croft}{1993}]{Fujii93}
Hideo Fujii \BBA\ W. Bruce Croft \BBOP 1993\BBCP.
\newblock \BBOQ A Comparison of Indexing Techniques for 
Japanese Text Retrieval \BBCQ\ 
\newblock In {\Bem Proceeding of SIGIR'93}, pp.~237--246, 
\newblock Pittsburgh PA, USA.

\bibitem[\protect\BCAY{Kageura, Koyama, Yoshioka, Takasu, Nozue, Tsuji}
{Kageura et al.}{1997}]{Kageura97}
Kyo Kageura, Teruo Koyama, Masaharu Yoshioka, Atsuhiro Takasu, 
Toshihiko Nozue, \BBA\ Keita Tsuji \BBOP 1997\BBCP.
\newblock \BBOQ NACSIS Corpus Project for IR and Terminological Research\BBCQ\
\newblock In {\Bem Natural Language Proceeding Pacific Rim Symposium'97},
pp.~493--496.

\bibitem[\protect\BCAY{Kando, Koyama, Oyama, Kageura, Yoshioka, Nozue, 
Matsumura, Kuriyama}{Kando et al.}{1998}]{Kando98}
Noriko Kando, Teruo Koyama, Keizo Oyama, Kyo Kageura, Masaharu Yoshioka, 
Toshihiko Nozue, Atsushi Matsumura, \BBA\ Kazuko Kuriyama \BBOP 1998\BBCP.
\newblock \BBOQ NTCIR:NACSIS Test Collection Project\BBCQ\ 
\newblock In {\Bem 20th Annual Colloquium of BCS-IRSG}.

\bibitem[\protect\BCAY{Kohonen}{Kohonen}{1995}]{Kohonen95}
Teuvo Kohonen \BBOP 1995\BBCP.
\newblock \BBOQ Self-Organizing Maps\BBCQ\
Springer-Verlag Berlin Heidelberg. 

\bibitem[\protect\BCAY{Korfhage}{Korfhage}{1997}]{Korfhage97}
Robert R. Korfhage \BBOP 1997\BBCP.
\newblock \BBOQ Information Storage and Retrieval \BBCQ\
\newblock In {\Bem WILEY COMPUTER PUBLISHING}, pp.~291--303, 
\newblock John Wiley \& Sons, Inc.,Printed in USA.

\bibitem[\protect\BCAY{Manning, Schutze}{Manning, Schutze}{1999}]{Manning99}
Christopher D. Manning and Hinrich Schutze \BBOP 1999\BBCP.
\newblock \BBOQ Foundationals of Statistical Natural Language Processing\BBOQ\
The MIT Press, Cambridge MA.

\bibitem[\protect\BCAY{Matsumoto, Kitauchi, Yamashita, Hirano}
{Matsumoto et al.}{1997}]{Matsumoto97}  
Yuji Matsumoto, Akira Kitauchi, Tatsuo Yamashita, Yoshitaka Hirano, 
Osamu Imaichi, \BBA\ Tomoaki Imamura \BBOP 1997\BBCP.
\newblock \BBOQ Japanese Morphological analysis System ChaSen Manual\BBCQ\
\newblock {\Bem NAIST Technical Report, NAIST-IS-TR97007},
http://cactus.aist-nara.ac.jp/lab/nlt/chasen.html.

\bibitem[\protect\BCAY{大竹，増山，山本}{大竹 \Jetal}{1999}]{Otake99}
大竹清敬，増山繁，山本和英 \BBOP 1999\BBCP.
\newblock \JBOQ 名詞の連接情報を用いた関連文書検索手法\BBCQ\
\newblock \Jem{情報処理学会論文誌}, {\Bbf 40(5)}, pp.~2460--2467.

\bibitem[\protect\BCAY{小澤，山本，山本，梅村}{小澤 \Jetal}{1999}]{Ozawa99}
小澤智裕，山本幹雄，山本英子，梅村恭司 \BBOP 1999\BBCP.
\newblock \JBOQ 情報検索の類似尺度を用いた検索要求文の単語分割\BBCQ\
\newblock \Jem{言語処理学会大会}, {\Bbf A5-2}.

\bibitem[\protect\BCAY{Salton, Buckley}{Salton \BBA\ Buckley}{1988}]{Salton88}
Gerard Salton \BBA\ Christopher Buckley \BBOP 1988\BBCP.
\newblock \BBOQ Term-Weighting Approaches in Automatic Text Retrieval \BBCQ\
\newblock In {\Bem Information Proceeding and Management}, {\Bbf 24}, 
pp.~513--523.

\bibitem[\protect\BCAY{高木，木谷}{高木，木谷}{1996}]{Takagi96}
高木徹，木谷強 \BBOP 1996\BBCP.
\newblock \JBOQ 単語出現共起関係を用いた文書重要度付与の検討\JBCQ\
\newblock \Jem{情報処理学会 情報学基礎研究会}, {\Bbf FI41-8}.

\bibitem[\protect\BCAY{田中}{田中}{1997}]{Tanaka97}
田中英輝 \BBOP 1997\BBCP.
\newblock \JBOQ 長い日本語表現の高速類似検索手法\JBCQ\
\newblock \Jem{情報処理学会 自然言語処理研究会}, {\Bbf NL121-10}.

\bibitem[\protect\BCAY{山田，森，中川}{山田 \Jetal}{1997}]{Yamada97}
山田剛一，森 辰則，中川 裕志 \BBOP 1997\BBCP.
\newblock \JBOQ 複合語マッチングと共起情報を併用する情報検索\JBCQ\
\newblock \Jem{情報処理学会論文誌}, {\Bbf 39(8)}, pp.~2431--2439.

\bibitem[\protect\BCAY{Yamamoto, Church}{Yamamoto \BBA\ Church}{1998}]
{Yamamoto98}
Mikio Yamamoto \BBA\ Kennth W. Church \BBOP 1998\BBCP. 
\newblock \BBOQ Using Suffix Arrays to Compute Term Frequency and 
Document Frequency for All Substrings in a Corpus\BBCQ\ 
\newblock In {\Bem Proceeding of the Sixth Workshop on Very Large Corpora}, 
\newblock Editor: Eugene Charniak, pp.~28--37.


\end{thebibliography}
\begin{biography}
\biotitle{略歴}
\bioauthor{山本 英子}{
1996年豊橋技術科学大学情報工学課程卒業．  
2002年同大学大学院工学研究科電子・情報工学専攻博士課程修了．
博士（工学）．
同年，通信総合研究所に専攻研究員として入所．
}
\bioauthor{武田 善行}{
2000年豊橋技術科学大学工学部情報工学課程卒業．
2002年同大学工学研究科情報工学専攻修士課程修了．
同年同大学大学院工学研究科電子・情報工学専攻博士課程入学．
現在に至る．
}
\bioauthor{梅村 恭司}{
1983年東京大学大学院工学系研究系情報工学専攻修士課程修了．
博士（工学）．
同年，日本電信電話公社電気通信研究所入所．
1995年豊橋技術科学大学工学部情報工学系助教授，現在に至る．
システムプログラム，記号処理の研究に従事．ACM，ソフトウェア科学会，
電子情報通信学会，計量国語学会各会員．
}  

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

\end{biography}

\end{document}









