



\documentstyle[epsf,jnlpbbl]{jnlp_j_b5}

\setcounter{page}{129}
\setcounter{巻数}{10}
\setcounter{号数}{2}
\setcounter{年}{2003}
\setcounter{月}{4}
\受付{2002}{8}{12}
\再受付{2002}{10}{23}
\採録{2003}{1}{10}

\setcounter{secnumdepth}{2}

\title{SVDPACKC とその語義判別問題への利用}
\author{新納 浩幸\affiref{shinnou} \and 佐々木 稔\affiref{sasaki}}
\headauthor{新納，佐々木}

\headtitle{SVDPACKC とその語義判別問題への利用}
\affilabel{shinnou}{茨城大学工学部システム工学科}
{Department of Systems Engineering, Ibaraki University}
\affilabel{sasaki}{茨城大学工学部情報工学科}
{Department of Computer and Information sciences, Ibaraki University}

\jabstract{
本論文ではフリーの特異値分解ツール SVDPACKC を紹介する．
その利用方法を解説し，利用事例として語義判別問題を扱う．
近年，情報検索では潜在的意味インデキシング（Latent Semantic Indexing，LSI）
が活発に研究されている．
LSI では高次元の索引語ベクトルを
低次元の潜在的な概念のベクトルに射影することで，
ベクトル空間モデルの問題点である同義語や多義語の問題に対処する．
そして概念のベクトルを構築するために，索引語文書行列に対して特異値分解を行う．
SVDPACKC は索引語文書行列のような高次元かつスパースな行列に対して
特異値分解を行うツールである．
また LSI は，高次元の特徴ベクトルを重要度の高い低次元のベクトルに
圧縮する技術であり，情報検索以外にも様々な応用が期待される．
ここでは SVDPACKC の利用事例として語義判別問題を取り上げる．
SENSEVAL2 の辞書タスクの動詞 50 単語を対象に実験を行った．
LSI に交差検定を合わせて用いることで，最近傍法の精度を向上させることができた．
また最近傍法をベースとした手法は，一部の単語に対して
決定リストや Naive Bayes 以上の正解率が得られることも確認できた．
}

\jkeywords{特異値分解，SVDPACKC，LSI，語義の曖昧性解消}

\etitle{Introduction of SVDPACKC and its application\\
to word sense disambiguation problems}
\eauthor{Hiroyuki Shinnou\affiref{shinnou} \and Minoru
Sasaki\affiref{sasaki}}

\eabstract{
In this paper, we introduce a free software package SVDPACKC
computing the singular value decomposition (SVD) of large sparse matrics.
First we explain how to use it, and then
solve word sense disambiguation problems by using it.
In information retrieval domain, Latent Semantic Indexing (LSI) has
actively been researched.
LSI maps a high dimensional term vector to the low dimensional concept vectors
to overcome synonymy and polysemy problems over information retrieval 
using vector space model.
To build low dimensional concept vectors
LSI computes the SVD of term-document matrics.
SVDPACKC is a software tool to computes the SVD  of large sparse matrics
like term-document matrics.
LSI compresses a high dimensional future vector
to the low dimensional concept vectors, so has many applications 
besides information retrieval.
In this paper, we attack word sense disambiguation problems of 50 verbs in Japanese dictionary 
task of SENSEVAL2.
By using cross validation and LSI, we improved simple Nearest Neighbor method (NN).
And we showed that the methods based on NN achieve better precision than 
the decision list method and Naive Bayes method for some words.
}

\ekeywords{singular value decomposition, SVDPACKC, LSI, word sense disambiguation}

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


\section{はじめに}


本論文はフリーの特異値分解ツール SVDPACKC \cite{svdpackc}を紹介する．
その利用方法を解説し，利用事例として多義語の曖昧性解消問題
（以下，語義判別問題と呼ぶ）を扱う．

情報検索ではベクトル空間モデルが主流である．そこでは文書とクエリを索引語ベクトルで表し，
それらベクトル間の距離をコサイン尺度などで測ることで，クエリと最も近い文書を検索する．
ベクトル空間モデルの問題点として，同義語（synonymy）と多義語（polysemy）の問題が
指摘されている．同義語の問題とは，例えば，``car'' というクエリから ``automobile'' を含む文書が
検索できないこと．多義語の問題とは，例えば，ネットサーフィンについてのクエリ ``surfing''に対して，
波乗りに関する文書が検索されることである．
これらの問題は文書のベクトルに索引語を当てることから生じている．
そこでこれら問題の解決のために文書のベクトルを潜在的（latent）な概念に設定することが
提案されており，そのような技術を潜在的意味インデキシング
（Latent Semantic Indexing，以下 LSI と略す）と呼んでいる．
LSI の中心課題はどのようにして潜在的な概念に対応するベクトルを抽出するかである．
その抽出手法に LSI では特異値分解を利用する．
具体的には索引語文書行列\( A \)に対して特異値分解を行い，
その左特異ベクトル（\( A A^{T} \) の固有ベクトル）を固有値の
大きい順に適当な数\( k \)だけ取りだし\footnote{ここでは索引語ベクトルを
列ベクトルとしている．また\( A^{T} \)は\( A \)の転置行列を表す．}，
それらを潜在的な概念に対応するベクトルとする\cite{kita-ir}．

LSI は魅力的な手法であるが，実際に試してみるには，特異値分解のプログラムが必要になる．
低次元の特異値分解のプログラムは比較的簡単に作成できるが，
現実の問題においては，高次元かつスパースな行列を扱わなくてはならない．
このような場合，特異値分解のプログラムを作成するのはそれほど容易ではない．
そこで本論文では，この特異値分解を行うためのツール SVDPACKC を紹介する．
このツールによって高次元かつスパースな行列に対する特異値分解が行え，
簡単に LSI を試すことができる．

また LSI の情報検索以外の応用として，語義判別問題を取り上げ SVDPACKC の
利用例として紹介する．実験では SENSEVAL2 の日本語辞書タスク\cite{sen2}で
出題された単語の中の動詞 50 単語を対象とした．
LSI に交差検定を合わせて用いることで，最近傍法\cite{ishii}の精度を向上させることができた．
また最近傍法をベースとした手法は，一部の単語に対して
決定リスト\cite{Yarowsky1}や Naive Bayes \cite{ml-text}以上の正解率が
得られることも確認できた．



\section{LSI と 特異値分解}


情報検索において，\( m \)個の索引語を予め決めておけば，
文書は\( m \)次元の索引語ベクトルとして表現できる（ここでは列ベクトルとして考える）．
検索対象の文書群が\( n \)個ある場合，各文書\( d_i \)に対する\( m \)次元の索引語ベクトルが
\( n \)個並ぶので，\( m \times n \)の索引語文書行列\( A \)ができる．

\( m \times n \)の行列\( A \)の特異値分解とは，行列\( A \)を以下のような
行列\( U \)，\( \Sigma \)，\( V \)の積に分解することである．
\begin{equation}
A = U  \Sigma  V^{T} \label{siki1}  
\end{equation}

\noindent
ここで，\( U \)は\( m \times m \)の直交行列，\( V \)は\( n \times n \)の直交行列である．
また\( \Sigma \)は\( m \times n \)の行列であり，\( rank(A) = r \) とすると，
対角線上に\( r \)個の要素\( \sigma_1, \sigma_2, \cdots, \sigma_r \)
（ただし \( \sigma_1 \ge \sigma_2 \ge \cdots, \ge \sigma_r\)）が並んだ行列である．
それ以外の\( \Sigma \)の要素は 0 である．

行列\( A \)の特異値分解を行ったとき，\( U \)は\( A \)の列ベクトルが
張る空間の正規直交基底となっている．そして\( U \)内の列ベクトルは
左側にあるものほど基底としての重要度が高い．
そこで，\( U \)の最初の\( k \)個の列ベクトルを使って，索引語ベクトルを
表すことにする．具体的には索引語ベクトルを\( U \)の最初の\( k \)個の列ベクトルに
射影させればよい．
つまり，\( U \)の最初の\( k \)個の列ベクトルで作成される\( m \times k \)の行列を
\( U_k \)とおくと，索引語ベクトル\( d \)は\( U_{k}^{T} d \)によって
\( k \)次元のベクトルで表現できることになる．
実際の検索では，\( m \)次元の索引語ベクトルで表現されていたクエリ\( q \)も
\( U_{k}^{T} q \) によって\( k \)次元のベクトルで表現し，
\( U_{k}^{T} d \)と\( U_{k}^{T} q \)の距離によって，\( d \)と\( q \)
の距離を測ればよい．例えば，\( d \)と\( q \)の距離\( dist(d,q) \)は以下のように
測ることができる\cite{kita-ir}．
\begin{equation}
dist(d,q) = \frac{(U_{k}^{T} d, U_{k}^{T} q)}{||U_{k}^{T} q|| ||U_{k}^{T} q||} \label{siki2}
\end{equation}

以上より，情報検索に LSI を利用するためには，索引語文書行列\( A \)の
特異値分解から得られる行列\( U \)が求まれば良いことがわかる．


\section{特異値分解ツール SVDPACKC}


\subsection{入手とコンパイル}

行列\( A \)の特異値分解を行うツールが SVDPACKC である．
SVDPACKC はフリーで配布されており，以下の URL から入手できる．
\begin{center}
{\tt   http://www.netlib.org/svdpack/svdpackc.tgz}
\end{center}

SVDPACKC には特異値分解を行う C 言語のプログラムが8つ入っている．
この中で最も計算速度が優れているのは{\tt las2 }と名付けられている
ランチョス法\cite{kita-ir}を使ったプログラムである．
単に特異値分解の結果だけを得たいのであれば{\tt las2 }を利用すれば良く，
他のプログラムをコンパイルする必要はない．ここでは {\tt las2 }だけをコンパイルする．

{\tt las2.c } をコンパイルする前に，{\tt las2.c }の中でコメントアウト
されているマクロ定数\verb| UNIX_CREAT |を有効にしておく．
\begin{verbatim}
         /* #define  UNIX_CREAT */   →   #define  UNIX_CREAT
\end{verbatim}
\noindent
これによって{\tt las2 }による特異値分解の結果がファイルに保存される．
次に，{\tt las2.h } のマクロ定数\verb|LMTNW|，\verb|NMAX|，\verb|NZMAX|の
値を適当に調整する．これらは取り得るメモリの最大サイズ，行列の最大サイズ，
行列中の非ゼロ要素の最大個数を定義したものであり，どの程度の大きさの行列を扱えるかを
示している．
扱う問題や利用する計算機にもよるだろうが，本論文での実験では予め与えられている値の10倍の数に変更した．
実行時に行列のサイズに関するエラーが出た場合は，これらの値を設定し直してコンパイルする．
また{\tt las2.c }の中では{\tt random }関数を自前で用意しているために，
{\tt stdlib.h }で定義されている{\tt random }関数と競合する場合がある．
ここでは{\tt las2.c }中の{\tt stdlib.h }を include しないことにした．
\begin{verbatim}
         #include <stdlib.h>   →   /* #include <stdlib.h> */
\end{verbatim}
\noindent
コンパイルは{\tt makefile} のコンパイラの指定（CC）を利用するコンパイラに合わせて，
以下を実行する．ここでは Linux の gcc で問題なくコンパイルできた
\footnote{gcc，libc 及び libm のバージョンはそれぞれ egcs-2.91.66，2.1.2，2.1.2 のものを用いた．
libm 以外のライブラリは使用されない．}．

\begin{center}
{\tt   make\ \ las2}
\end{center}

またマニュアルには，CRAY Y-MP，IBM RS/6000-550，DEC 5000-100，
HP 9000-750，SPARCstation 2 及び Machintosh II/fx で SVDPACKC が動作することが
記載されている．また Windows2000 上の Borland C++ Compiler 5.5 を利用しても
{\tt las2.c }をコンパイルできた
\footnote{ただし構造体 rusage の定義がないので，若干変更する必要があった．}．
更に Windows2000 上の cygwin + gcc 環境
\footnote{cygwin の dll のバージョンは 1.2.12-2，gcc のバージョンは
2.95.3-5 のものを用いた．}でもコンパイルできた．
特別なライブラリは使われていないので，多くの環境でコンパイル可能と思われる．

\subsection{利用方法}

{\tt las2 }は内部で２つのファイルを読む込む．１つは特異値分解を行いたい対象の行列が記述された
ファイル{\tt matrix}であり，もう１つはパラメータを記述したファイル{\tt lap2 }である．
この２つのファイルを適切に用意することで，{\tt las2}を実行することができる．

配布キットでは，サンプルの行列が{\tt belladit.Z} という名前の圧縮されたファイルとして
提供されている．このファイルから，例えば以下のコマンドにより，{\tt matrix} ファイルを作り，
{\tt las2}を試してみる．{\tt lap2 }はこのサンプル用にキット内に用意されている．
\begin{verbatim}
           zcat belladit.Z > matrix
\end{verbatim}
\noindent
実行は以下のように単にコマンド名だけを入力する．
\begin{verbatim}
           ./las2
\end{verbatim}
\noindent
結果は{\tt lav2}と{\tt lao2}というファイルに保存される．
{\tt lav2}には特異値分解したときの\mbox{式\ref{siki1}}における\( U \) や\( V \)の
配列が保存される．ただし，バイナリファイルなので直接見ることはできない．
{\tt lao2}には特異値分解したときの\mbox{式\ref{siki1}}の\( \Sigma \)，つまり特異値の
列とその他の情報（行列の大きさや実行時間等）が保存される．
これはテキストファイルなので中身を確認できる．

\subsubsection{{\tt matrix}ファイルの記述方法}

特異値分解の対象となる行列\( A \)は，ハーウェル・ボーイング形式（Harwell-Boeing format）と
呼ばれる列方向の圧縮形式を用いてファイル {\tt matrix}に記述する．
これによりスパース行列を少ない記述量で簡単に表現することができる．

最初に注意として，行列\( A \)の大きさを\( m \times n \)とした場合，
SVDPACKC では \( m \ge n \) を仮定している．
そのために，実際に特異値分解したい行列\( A \)の列数の方が行数よりも大きい場合は，
行列\( A \)の転置行列\( A^{T} \)に対して特異値分解を行う必要がある．
この場合，\mbox{式\ref{siki2}}の\( U \)は\( V \)と置き換えなければならないこともある．

ここでは，{\tt matrix}の記述形式の説明として，以下のような
行列\( A \)を考える．
\[
A = \left[
      \begin{array}{cccc}
         1.0 & 0   & 0   & 0      \\
         0   & 2.1 & 0   & 0.5    \\
         0   & 1.0 & 0   & 0      \\
         0   & 0.8 & 0   & 0      \\
         0   & 0.8 & 1.0 & 0      \\
         1.0 & 0   & 2.2 & 0    \\
         0   & 0   & 0   & 1.0     
      \end{array}
    \right]
\]

この行列に対して，１列目から順に非ゼロ要素を取り出し，以下のような表を作る．
\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline
データ番号  & 1  & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
位置       & (1,1) & (6,1) & (2,2) & (3,2) & (4,2) & (5,2) & (5,3) & (6,3) & (2,4) & (7,4) \\ \hline
値    & 1.0   & 1.0 & 2.1 & 1.0 & 0.8 & 0.8 & 1.0 & 2.2 & 0.5 & 1.0 \\ \hline
    \end{tabular}
  \end{center}
\end{table}

次にこの表から位置の行の部分だけを取り出す．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline
データ番号  & 1  & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
位置       & (1,1) & (6,1) & (2,2) & (3,2) & (4,2) & (5,2) & (5,3) & (6,3) & (2,4) & (7,4) \\ \hline
値    & 1.0   & 1.0 & 2.1 & 1.0 & 0.8 & 0.8 & 1.0 & 2.2 & 0.5 & 1.0 \\ \hline
行位置  & 1 & 6 & 2 & 3 & 4 & 5 & 5 & 6 & 2 & 7 \\ \hline
    \end{tabular}
  \end{center}
\end{table}

次に各列の最初の非ゼロ要素のデータ番号を列ポインタに記述する．
例えば，1列目であれば，最初の非ゼロ要素は\verb|(1,1)|の \verb|1.0| であり，
これに対するデータ番号は 1 である．次に
2列目であれば，最初の要素は\verb|(2,2)|の \verb|2.1| であり，
これに対するデータ番号は 3 である．
これを各列，順に記述したものが列ポインタである．つまり列ポインタの要素数は
配列\( A \)の列数となる．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline
データ番号  & 1     & 2     & 3    & 4      & 5     & 6     & 7     & 8     & 9     & 10 \\ \hline
位置       & (1,1) & (6,1) & (2,2) & (3,2) & (4,2) & (5,2) & (5,3) & (6,3) & (2,4) & (7,4) \\ \hline
値          & 1.0   & 1.0 & 2.1 & 1.0 & 0.8 & 0.8 & 1.0 & 2.2 & 0.5 & 1.0 \\ \hline
行位置  & 1 & 6 & 2 & 3 & 4 & 5 & 5 & 6 & 2 & 7 \\ \hline
列ポインタ  & 1 & 3 & 7 & 9 & - & - & - & - & - & - \\ \hline
    \end{tabular}
  \end{center}
\end{table}

ハーウェル・ボーイング形式とは，行列に対して，このような表を作り，
列ポインタ，行位置，値を記述した形式である．これはスパース行列を圧縮した表現となる．

{\tt matrix}では4行目以降に，列ポインタ，行位置，値が記述されている．
列ポインタについては最後の非ゼロ要素のデータ番号に１を足したものが付け加えられることに注意する．
先の例では以下のようになる．

\bigskip

\small
\begin{tabular}{|c|} \hline
\begin{minipage}{134mm}
\begin{verbatim}

       1       3       7       9       11
       1       6       2       3       4       5       5       6       2       7
       1.0       1.0       2.1       1.0       0.8       0.8       1.0       2.2
       0.5       1.0

\end{verbatim}
\end{minipage}
\\
\hline
\end{tabular}
\normalsize

\bigskip

{\tt matrix}の最初の4行は行列に関するその他の情報が記述されている．
3行目以外意味はない．1行目はデータの名前であり，
サンプルファイルの{\tt belladit.Z}を参考に適当につければよい．
2行目，4行目も意味はなく，{\tt belladit.Z}の通りに記述すれば良い．
3行目は以下のように 5つのデータを空白で区切って記述すればよい．

\bigskip

\small
\begin{tabular}{|c|} \hline
\begin{minipage}{134mm}
\begin{verbatim}

       rra                      7            4          10             0

\end{verbatim}
\end{minipage}
\\
\hline
\end{tabular}
\normalsize

\bigskip

この行の1列目（\verb|rra|），5列目（0）はこの通り記述すれば良い．
2列目（7）は行列\( A \)の行数，3列目（4）は列数，4列目（10）は非ゼロ要素の総数
を記述する．結果，先の例において，{\tt matrix} は以下のようになる．

\bigskip

\small
\begin{tabular}{|c|} \hline
\begin{minipage}{134mm}
\begin{verbatim}

    Jikken Data                                                             jikken
    Transposed
    rra                      7            4          10             0
              (10i8)          (10i8)            (8f10.3)            (8f10.3)
        1       3       7       9       11
        1       6       2       3       4       5       5       6       2       7
        1.0       1.0       2.1       1.0       0.8       0.8       1.0       2.2
        0.5       1.0

\end{verbatim}
\end{minipage}
\\
\hline
\end{tabular}
\normalsize

\bigskip

\subsubsection{{\tt lap2}ファイルの記述方法}

{\tt lap2}ファイルは{\tt las2}で使われるパラメータが 1行で記述されている．
例えば，配布キットに入っている{\tt lap2}ファイルの中身は以下のような
1行のファイルであり，8個のデータが空白で区切られて入っている．

\bigskip

\small
\begin{tabular}{|c|} \hline
\begin{minipage}{134mm}
\begin{verbatim}

       'belladit' 44 10 -1.0e-30 1.0e-30 TRUE 1.0e-6 0

\end{verbatim}
\end{minipage}
\\
\hline
\end{tabular}
\normalsize

\bigskip

1列目（'belladit'）は{\tt matrix}ファイルの1行目に記述したデータの名前である．{\tt matrix}と
{\tt lap2}とのデータ名の一致は検査していないので，実質意味はない．適当な名前をつければ良い．
4列目（-1.0e-30），5列目（1.0e-30），6列目（1.0e-6）の数値は，繰り返しの収束条件に
あたるものであり，特に変更する必要はない．
7列目（TRUE）は特異値分解の結果の\( U \) や\( V \)の行列をファイルに保存するかどうかの
指定であり，\verb| TRUE |にしておけば保存される．
8列目に意味はない．実際は何も書かなくてもよい．

問題は2列目（44）と3列目（10）の整数値である．
結論から述べれば，どちらも行列\( A \)の列数\( n \)を設定すればよい．
今，2列目の整数値を\verb| lanmax |，3列目の整数値を\verb| maxprs |とおく．
\verb| lanmax |は{\tt las2}のアルゴリズムであるランチョス法の最大の繰り返し回数を意味する．
一方，\verb| maxprs |の意味はやや不明確である．
マニュアルには，所望の\( U \)や\( V \)の次元数と記載されているが，例えば，
\verb| maxprs = 20 |と設定したからといって，必ずしも\( U \)や\( V \)の次元数が 20 になって
出力されるわけではなく，10 であったり，25 であったりする．
このような違いは\verb| lanmax |の数値とも関連しており，依存関係は複雑である．
しかし {\tt las2} 内部では，\( U \)や\( V \)を最大の次元数に設定して計算しており，
最後の出力の部分で指定した次元数を考慮して出力させている．
そのため\verb| maxprs |の値は実行時間等に影響はなく，
現実的には得られる最大の次元数を出力させ，その結果から所望の次元数を得た方が取り扱いが
簡単である．

\subsection{出力結果の利用}

{\tt las2}による特異値分解の結果は{\tt lav2}と{\tt lao2}というファイルに保存される．
{\tt lao2}はテキストファイルであり，内容の確認は容易である．
重要部分はファイルの下方に記載されている固有値の列である．
この部分を適当に切り取って利用すればよい．
また，{\tt lao2}では，固有値は値の小さい順に出力されていること
に注意すべきである．
固有値は大きい方が重要な意味を持つため，ファイルの下方に書かれた
特異値ほど重要である．

{\tt lav2}はバイナリファイルであり，{\tt las2} のソースをみて
出力形式を確認すれば，特異値分解結果の\( U \)や\( V \)を得ることが可能である．
結局，{\tt lav2}をテキストファイルの形式に変換する何らかのプログラムを自作する
必要がある．
ただし，そのようなプログラムを作成するのであれば，{\tt las2} のソースを
直接変更して，テキストファイルの形式で出力させた方が簡単である．

例えば，{\tt las2.c} の 334行目で\( U \)が出力されているので，
以下のように変更する．

\bigskip

\small
\begin{tabular}{|c|} \hline
\begin{minipage}[H]{134mm}
\begin{verbatim}

  変更前
           write(fp_out2, (char *)&xv1[ida], size1);

  変更後

           long kk;   /* この変数をはじめの方で作っておく */

           ...
          
           /* write(fp_out2, (char *)&xv1[ida], size1); */
           for(kk = 0;kk < nrow;kk++) fprintf(fp_out2,"
           fprintf(fp_out2,"EOV\n"); /* ベクトルの終りの記号も入れる */

\end{verbatim}
\end{minipage}
\\
\hline
\end{tabular}
\normalsize

\bigskip

これで\verb| lav2 | に\( U \)の中身がテキスト形式で出力される．
ファイル名も変更したいときは，148行目の以下の部分を書き換える．
\begin{verbatim}

           out2 = "lav2";

\end{verbatim}

また{\tt las2.c} の 756行目で\( V \)が出力されているので，以下のように変更する．

\bigskip

\small
\begin{tabular}{|c|} \hline
\begin{minipage}[H]{134mm}
\begin{verbatim}

  変更前
          for (i = 0; i < n; i++) xv1[id++] = w1[i];

  変更後
        
          FILE *fp_out3;   /* 他と合わせるために las2.h に
                              書いておく．大域変数となる． */
          ... 

          fp_out3 = fopen("V-matrix", "w");  
                           /* 行列 V のファイル名は V-matrix とする．
                              main 中で fopen で開いておく */
          ... 
          
          /* for (i = 0; i < n; i++) xv1[id++] = w1[i]; */
          for (i = 0; i < n; i++) {
             xv1[id++] = w1[i];
             fprintf(fp_out3,"
          }
          fprintf(fp_out3,"EOV\n"); /* ベクトルの終りの記号も入れる */

\end{verbatim}
\end{minipage}
\\
\hline
\end{tabular}
\normalsize

\bigskip

以上のようにして，テキストファイルの形式で\( U \) や\( V \)を得ることができる．
これらのファイルは，\( U \) や\( V \)の列ベクトルが，順に出力されている形になるが，
その順序は{\tt lao2}の固有値の順序に対応している．
つまり，固有値の大きな順に\( k \)個の列ベクトルを取り出すときには，
下方にあるベクトルから順に\( k \)個取り出さなければならないことに注意する．


\section{語義判別問題への利用}


ここでは情報検索以外への LSI の応用として語義判別問題を取り上げる．
SENSEVAL2 の日本語辞書タスクで課題として出された動詞 50単語を実験の対象とする．

\subsection{最近傍法の利用}

単語\( w \)は\( k \)個の語義を持つとし，
各語義を\( c_i \)\ \ (\(i = 1 〜 k\))で表す．
単語\( w \)の語義判別問題とは，テキストに単語\( w \)が現れたときに，
その文脈上での単語\( w \)の語義\( c_j \)を判定する問題である．
文脈を\( m \)個の素性のベクトル\( (f_1,f_2, \cdots, f_m )\)で表現した場合，
この語義判別問題は分類問題となり，帰納学習の手法により解決できる．
ここでは最近傍法（Nearest Neighbor 法，以下 NN法と略す）\cite{ishii}を用いる．NN法は与えられた
素性ベクトルと最も距離が近い訓練事例中の素性ベクトルを選び，そのクラスを
出力とする手法である\footnote{これは用例ベースの手法であり，
帰納学習手法とは位置づけない見方もできる．}．
今，単語\( w \)の訓練データの事例数を\( n \)とし，各事例を\( m \times 1 \)の
素性ベクトル\( d_i \)\ （\( i = 1 〜 n \)）で表す．
すると訓練データ全体の集合は \( m \times n \) の行列\( A \)として表せる．
実際の語義判別は，単語\( w \)の現れた文脈を素性ベクトル\( q \)で表し，
以下の式で求められる訓練事例\( \hat{d} \)のクラスを返すことで行える．
\[
\hat{d} = arg \min_{d_i} dist(q,d_i)
\]
\noindent
ここでの NN法は，\( dist(q,d_i) \)を単純なコサイン尺度で計算することにする．
また行列\( A \)を特異値分解し，\mbox{式\ref{siki2}}を利用して
\( dist(q,d_i) \)を定義したものを LSI 法と呼ぶことにする．

\subsection{素性の設定}

ここでは語義判別の手がかりとなる属性として以下のものを設定した．
\begin{verbatim}

      e1     直前の単語
      e2     直後の単語
      e3     前方の内容語２つまで
      e4     後方の内容語２つまで
      e5     e3 の分類語彙表の番号
      e6     e5 の分類語彙表の番号

\end{verbatim}

例えば，語義判別対象の単語を「出す」として，以下の文を考える（形態素解析され
各単語は原型に戻されているとする）．
\begin{verbatim}

             短い/コメント/を/出す/に/とどまる/た/。

\end{verbatim}
\noindent 
この場合，「出す」の直前，直後の単語は「を」と「に」なので，
\verb| `e1=を' |，\verb| `e2=に' |となる．
次に，「出す」の前方の内容語は「短い」と「コメント」なので，
\verb| `e3=短い' |，\verb| `e3=コメント' |の２つが作られる．
またここでは句読点も内容語に設定しているので，
「出す」の後方の内容語は「とどまる」「。」となり，
\verb| `e4=とどまる' |，\verb| `e4=。' |が作られる．
次に「短い」の分類語彙表\cite{bunrui-tab}の番号を調べると，\verb| 3.1920_1 |である．
ここでは分類語彙表の4桁目と5桁目までの数値をとることにした．
つまり\verb| `e3=短い' |に対しては，\verb| `e5=3192' | と \verb| `e5=31920' | 
が作られる．「コメント」は分類語彙表には記載されていないので，
\verb| `e3=コメント' |に対しては\verb| e5 |に関する素性は作られない．
次は「とどまる」の分類語彙表を調べるはずだが，
ここでは平仮名だけで構成される単語の場合，
分類語彙表の番号を調べないことにしている．
これは平仮名だけで構成される単語は多義性が高く，
無意味な素性が増えるので，その問題を避けたためである．
もしも分類語彙表上で多義になっていた場合には，
それぞれの番号に対して並列にすべての素性を作成する．

結果として，上記の例文に対しては以下の8つの素性が得られる．
\begin{verbatim}

             e1=を， e2=に， e3=短い， e3=コメント，
             e4=とどまる， e4=。， e5=3192， e5=31920，

\end{verbatim}

上記の例のようにして，「出す」に対するすべての訓練事例の素性を集め，
各素性に 1番から順に番号をつける．例えば，本論文の実験では「出す」に対しては
978種類の素性があり，上記例の素性には\mbox{表\ref{sosei-jigen}}のように番号が振られた．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \caption{素性と次元番号}
    \begin{tabular}{lcr}  \hline
素性          &  & 次元番号 \\  \hline
     \verb| e1=を| &  &   21 \\
     \verb| e2=に | &  &   60 \\
     \verb| e3=コメント | & &  134 \\
     \verb| e3=短い | & & 302 \\
     \verb| e4=。 |  & &   379 \\
     \verb| e4=とどまる | & &   406 \\
     \verb| e5=3192 | & &  789 \\
     \verb| e5=31920 | & &  790 \\ \hline
    \end{tabular} \label{sosei-jigen}
  \end{center}
\end{table}

以上より，上記例文に対する素性ベクトルは第21次元目，
第60次元目，第134次元目，第302次元目，第379次元目，
第406次元目，第789次元目，第790次元目の各要素が 1 であり，その他の要素がすべて 0 の
978次元のベクトルとなる．

\subsection{交差検定の利用}

LSI法を利用した場合，NN法と比較して，
必ずしも精度が向上するわけではなく，逆に精度が悪化する場合もある．
そのため単純にすべての単語に対して，LSI法を用いることはできない．
そこで交差検定を行い，次元圧縮の効果が確認できる単語のみ LSI法を用いることにする．
このように NN法と LSI法を融合した手法を LSI+NN法 と呼ぶことにする．

ここでの交差検定では訓練データを4分割し，3つを訓練データ，1つをテストデータとする．
組合わせを変えて，合計4通りの実験を行う．
各実験では，NN法と LSI法のテストデータに対する正解率を測る．
また特異値分解を使って圧縮する次元数は 75 とした．ただし
行列\( A \)のランク数が 75 以下の場合は，行列\( A \)のランク数にした．
付録の\mbox{表\ref{jigen-com1}}に{\tt las2 }の結果をまとめている．
そこではSENSEVAL2 の日本語辞書タスクの動詞 50単語の各単語に対する
行列\( A \)の大きさ，非ゼロ要素の密度，圧縮した次元数，次元圧縮に要したメモリと時間
が記されている．ただし，これらは4通りの実験での平均である．
また次元圧縮に要したメモリと時間は{\tt las2 }の出力ファイル\verb| lao2 |から得ている．

各単語に対して，4通りの実験の平均をとった結果が\mbox{表\ref{kousakekka}}である．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \caption{交差検定による比較}
    \begin{tabular}{|p{6zw}|p{4zw}|p{4zw}p{1zw}||p{6zw}|p{4zw}|p{4zw}p{1zw}|} \hline
    単語 & NN &  LSI &    & ↓ & ↓  & ↓  & \\ \hline
ataeru     &  0.621  & 0.517 &      &      tsutaeru   &  0.703  & 0.629 &       \\
iu         &  0.803  & 0.836 & 〇   &      dekiru     &  0.722  & 0.708 &       \\
ukeru      &  0.608  & 0.513 &      &      deru       &  0.432  & 0.279 &       \\
uttaeru    &  0.828  & 0.659 &      &      tou        &  0.718  & 0.703 &       \\
umareru    &  0.722  & 0.690 &      &      toru       &  0.464  & 0.232 &       \\
egaku      &  0.628  & 0.533 &      &      nerau      &  0.894  & 0.895 & 〇    \\
omou       &  0.918  & 0.845 &      &      nokosu     &  0.592  & 0.530 &       \\
kau        &  0.930  & 0.896 &      &      noru       &  0.672  & 0.641 &       \\
kakaru     &  0.644  & 0.452 &      &      hairu      &  0.443  & 0.392 &       \\
kaku\_v    &  0.741  & 0.733 &      &      hakaru     &  0.941  & 0.905 &       \\
kawaru     &  0.907  & 0.948 & 〇   &      hanasu     &  0.983  & 0.965 &       \\
kangaeru   &  0.925  & 0.949 & 〇   &      hiraku     &  0.853  & 0.813 &       \\
kiku       &  0.667  & 0.456 &      &      fukumu     &  0.946  & 0.946 & 〇     \\
kimaru     &  0.881  & 0.915 & 〇   &      matsu      &  0.589  & 0.470 &       \\
kimeru     &  0.899  & 0.886 &      &      matomeru   &  0.655  & 0.669 & 〇    \\
kuru       &  0.766  & 0.773 & 〇   &      mamoru     &  0.774  & 0.795 & 〇    \\
kuwaeru    &  0.899  & 0.899 & 〇   &      miseru     &  0.920  & 0.880 &       \\
koeru      &  0.841  & 0.716 &      &      mitomeru   &  0.934  & 0.934 & 〇    \\
shiru      &  0.866  & 0.834 &      &      miru       &  0.806  & 0.777 &       \\
susumu     &  0.339  & 0.366 & 〇   &      mukaeru    &  0.925  & 0.893 &       \\
susumeru   &  0.886  & 0.826 &      &      motsu      &  0.566  & 0.472 &       \\
dasu       &  0.476  & 0.303 &      &      motomeru   &  0.882  & 0.807 &       \\
chigau     &  0.905  & 0.971 & 〇   &      yomu       &  0.963  & 0.967 &       \\
tsukau     &  0.715  & 0.704 &      &      yoru       &  0.973  & 0.931 &       \\
tsukuru    &  0.578  & 0.569 &      &      wakaru     &  0.848  & 0.916 & 〇    \\ \hline
  ↓  &   ↓    &     ↓     &        &   平均        &  0.764  &  0.719  & \\  \hline
    \end{tabular}\label{kousakekka}
  \end{center}
\end{table}

特異値分解を利用することで正解率が向上したものは，\mbox{表\ref{kousakekka}}で
〇印のつけた以下の 14 単語である．これらに対して LSI法を用いることにする．

\begin{verbatim}

     iu, kawaru, kangaeru, kimaru, kuru, kuwaeru, susumu, 
     chigau, nerau, fukumu, matomeru, mamoru, mitomeru, wakaru

\end{verbatim}
\newpage

\subsection{特異値分解を用いた語義判別実験}

実際は選出した 14単語のみに対して LSI 法を行えば良いが，交差検定の効果も示すために，
すべての単語に対して LSI法を試みた．圧縮する次元数は 100 に設定した．
ただし行列\( A \)のランク数が 100 以下の場合は，行列\( A \)のランク数にした．
付録の\mbox{表\ref{jigen-com2}}に{\tt las2 }の結果をまとめている．
そこではSENSEVAL2 の日本語辞書タスクの動詞 50単語の各単語に対する
行列\( A \)の大きさ，非ゼロ要素の密度，圧縮した次元数，次元圧縮に要したメモリと時間
が記されている．
また次元圧縮に要したメモリと時間は{\tt las2 }の出力ファイル\verb| lao2 |から得ている．

次にSENSEVAL2 で配布されたテスト文を用いて正解率を測った結果が\mbox{表\ref{result1}}である．
スコアの算出は解答結果に部分点を与える mixed-gained scoring という方式\cite{sen2}を用いている．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \caption{実験結果}\label{result1}
    \begin{tabular}{|p{6zw}|c|c|c||p{6zw}|c|c|c|} \hline
    単語   & NN       &  LSI   & LSI+NN   & ↓ & ↓  & ↓  & ↓ \\ \hline
ataeru     & 0.680   & 0.560 & 0.680  &      tsutaeru   & 0.663   & 0.780 & 0.663    \\
iu         & 0.820   & 0.880 & 0.880  &      dekiru     & 0.760   & 0.690 & 0.760    \\
ukeru      & 0.550   & 0.410 & 0.550  &      deru       & 0.440   & 0.320 & 0.440    \\
uttaeru    & 0.810   & 0.680 & 0.810  &      tou        & 0.670   & 0.640 & 0.670    \\
umareru    & 0.720   & 0.670 & 0.720  &      toru       & 0.280   & 0.270 & 0.280    \\
egaku      & 0.560   & 0.570 & 0.560  &      nerau      & 0.980   & 0.920 & 0.920    \\
omou       & 0.930   & 0.710 & 0.930  &      nokosu     & 0.705   & 0.595 & 0.705    \\
kau        & 0.860   & 0.850 & 0.860  &      noru       & 0.680   & 0.600 & 0.680    \\
kakaru     & 0.620   & 0.540 & 0.620  &      hairu      & 0.390   & 0.250 & 0.390    \\
kaku\_v    & 0.770   & 0.560 & 0.770  &      hakaru     & 0.980   & 0.980 & 0.980    \\
kawaru     & 0.920   & 0.890 & 0.890  &      hanasu     & 1.000   & 0.990 & 1.000    \\
kangaeru   & 0.960   & 0.950 & 0.950  &      hiraku     & 0.880   & 0.790 & 0.880    \\
kiku       & 0.550   & 0.470 & 0.550  &      fukumu     & 0.960   & 0.990 & 0.990    \\
kimaru     & 0.910   & 0.900 & 0.900  &      matsu      & 0.490   & 0.540 & 0.490    \\
kimeru     & 0.920   & 0.910 & 0.920  &      matomeru   & 0.710   & 0.740 & 0.740    \\
kuru       & 0.740   & 0.830 & 0.830  &      mamoru     & 0.635   & 0.735 & 0.735    \\
kuwaeru    & 0.870   & 0.860 & 0.860  &      miseru     & 0.950   & 0.980 & 0.950    \\
koeru      & 0.770   & 0.710 & 0.770  &      mitomeru   & 0.860   & 0.880 & 0.880    \\
shiru      & 0.940   & 0.930 & 0.940  &      miru       & 0.740   & 0.730 & 0.740    \\
susumu     & 0.390   & 0.340 & 0.340  &      mukaeru    & 0.940   & 0.890 & 0.940    \\
susumeru   & 0.920   & 0.830 & 0.920  &      motsu      & 0.540   & 0.390 & 0.540    \\
dasu       & 0.340   & 0.210 & 0.340  &      motomeru   & 0.810   & 0.790 & 0.810    \\
chigau     & 0.870   & 0.970 & 0.970  &      yomu       & 0.880   & 0.830 & 0.880    \\
tsukau     & 0.715   & 0.895 & 0.715  &      yoru       & 0.960   & 0.900 & 0.960    \\
tsukuru    & 0.660   & 0.590 & 0.660  &      wakaru     & 0.820   & 0.890 & 0.890    \\ \hline
  ↓  &   ↓    &     ↓     &    ↓       &   平均       &  0.750    & 0.717 & 0.7570    \\ \hline
    \end{tabular}
  \end{center}
\end{table}




わずかではあるが，LSI+NN法の方が NN法よりも精度が高かった．

また選択した 14 単語のうち LSI法を利用することで精度が上がった
単語（選択が正しかった単語）は 8単語，下がった単語（選択が誤った単語）は 6単語である．
逆に選択しなかった 36 単語のうち NN法の方が精度が良かった
単語（選択が正しかった単語）は31単語，LSI法の方が精度が良かった
単語（選択が誤った単語）は 5単語であった．つまり，全体の50単語のうち
選択が正しかった単語は 39単語（78\,\%），選択が誤った単語は11単語（22\,\%）である．
単純にすべて NN法を選択した場合，選択が正しくなる単語は 37単語（74\,\%），選択が
誤る単語は 13単語（26\,\%）であるため，交差検定の効果が確認できる．

また同様の素性を用いて，決定リスト（DL と略す），Naive Bayes（NB と略す）を用いた判別も行った．
結果を\mbox{表\ref{result2}}に示す．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \caption{他手法との比較}\label{result2}
    \begin{tabular}{|p{6zw}|c|c|c|c||p{6zw}|c|c|c|c|} \hline
    単語   & NN       &  LSI   & DL & NB   & ↓ & ↓  & ↓  & ↓ & ↓ \\ \hline
ataeru     & 0.680   & 0.560 & 0.660   &  \underline{0.740}     & tsutaeru   & 0.663   & \underline{0.780} & 0.750  & \underline{0.780}      \\
iu         & 0.820   & 0.880 & \underline{0.940}   &  0.930     & dekiru     & 0.760   & 0.690 & 0.790  & \underline{0.800}      \\
ukeru      & 0.550   & 0.410 & 0.550   &  \underline{0.660}     & deru       & 0.440   & 0.320 & 0.560  & \underline{0.570}      \\
uttaeru    & 0.810   & 0.680 & 0.820   &  \underline{0.870}     & tou        & 0.670   & 0.640 & 0.600  & \underline{0.700}      \\
umareru    & \underline{0.720}   & 0.670 & 0.680   &  0.710     & toru       & 0.280   & 0.270 & 0.330  & \underline{0.390}      \\
egaku      & 0.560   & 0.570 & 0.560   &  \underline{0.580}     & nerau      & 0.980   & 0.920 & \underline{0.990}  & \underline{0.990}      \\
omou       & \underline{0.930}   & 0.710 & 0.890   &  0.900     & nokosu     & 0.705   & 0.595 & 0.770  & \underline{0.800}      \\
kau        & \underline{0.860}   & 0.850 & 0.850   &  0.850     & noru       & \underline{0.680}   & 0.600 & 0.590  & 0.660      \\
kakaru     & 0.620   & 0.540 & 0.630   &  \underline{0.660}     & hairu      & 0.390   & 0.250 & \underline{0.440}  & 0.380      \\
kaku\_v    & \underline{0.770}   & 0.560 & 0.740   &  0.730     & hakaru     & \underline{0.980}   & \underline{0.980} & 0.920  & 0.920      \\
kawaru     & \underline{0.920}   & 0.890 & \underline{0.920}   &  \underline{0.920}     & hanasu     & \underline{1.000}   & 0.990 & \underline{1.000}  & 0.990      \\
kangaeru   & 0.960   & 0.950 & 0.990   &  \underline{0.990}     & hiraku     & 0.880   & 0.790 & 0.830  & \underline{0.910}      \\
kiku       & 0.550   & 0.470 & 0.590   &  \underline{0.640}     & fukumu     & 0.960   & \underline{0.990} & \underline{0.990}  & \underline{0.990}      \\
kimaru     & 0.910   & 0.900 & \underline{0.960}   &  \underline{0.960}     & matsu      & 0.490   & \underline{0.540} & 0.530  & 0.490      \\
kimeru     & 0.920   & 0.910 & \underline{0.940}   &  0.920     & matomeru   & 0.710   & 0.740 & \underline{0.780}  & 0.750      \\
kuru       & 0.740   & 0.830 & \underline{0.890}   &  0.880     & mamoru     & 0.635   & 0.735 & \underline{0.800}  & 0.750      \\
kuwaeru    & 0.870   & 0.860 & \underline{0.890}   &  0.880     & miseru     & 0.950   & \underline{0.980} & \underline{0.980}  & 0.970      \\
koeru      & 0.770   & 0.710 & \underline{0.780}   &  0.760     & mitomeru   & 0.860   & 0.880 & \underline{0.890}  & \underline{0.890}      \\
shiru      & 0.940   & 0.930 & \underline{0.960}   &  \underline{0.960}     & miru       & \underline{0.740}   & 0.730 & 0.730  & \underline{0.740}      \\
susumu     & 0.390   & 0.340 & 0.430   &  \underline{0.450}     & mukaeru    & \underline{0.940}   & 0.890 & 0.920  & 0.900      \\
susumeru   & 0.920   & 0.830 & \underline{0.960}   &  0.940     & motsu      & 0.540   & 0.390 & 0.520  & \underline{0.550}      \\
dasu       & 0.340   & 0.210 & \underline{0.350}   &  0.340     & motomeru   & 0.810   & 0.790 & \underline{0.880}  & 0.870      \\
chigau     & 0.870   & 0.970 & \underline{1.000}   &  \underline{1.000}     & yomu       & \underline{0.880}   & 0.830 & \underline{0.880}  & \underline{0.880}      \\
tsukau     & 0.715   & 0.895 & 0.935   &  \underline{0.963}     & yoru       & 0.960   & 0.900 & \underline{0.970}  & \underline{0.970}      \\
tsukuru    & 0.660   & 0.590 & 0.590   &  \underline{0.710}     & wakaru     & 0.820   & 0.890 & \underline{0.900}  & \underline{0.900}      \\ \hline
  ↓  &   ↓    &     ↓     & ↓ & ↓  &   平均         & 0.750   & 0.717 & 0.777 & 0.790      \\ \hline
    \end{tabular}
  \end{center}
\end{table}

ほとんどの単語で，決定リストや Naive Bayes は NN 法や LSI法よりも良い結果を出しているが，
一部では NN 法や LSI法の方が良い値を出している．
単語によっては NN法をベースとした方が良い場合もあることを示している．


\section{考察}


SVDPACKC が扱える行列の大きさについて述べておく．
\verb| las2.c | からメモリ割り当ての関数\verb| malloc |の部分を抜き出して
みると，\verb| las2 | は\( m \times n \)の行列の特異値分解を行うのに，
大ざっぱに見積もって，\(  8mn \)バイト強の
メモリを必要としていることがわかる\footnote{{\tt sizeof(double)} の \( mn \)倍である．
{\tt sizeof(double) = 8} として\( 8mn \)を得ている．}．
この点から考えると，必要メモリが約200Mバイトとなる\( 25000 \times 1000 \) 位の
大きさが現実的な最大サイズだと思われる\footnote{これは個人的な感覚である．}．
確認のために，非ゼロ要素の密度が 1\,\% であり，平均 2 のポアソン分布に従って，
非ゼロ要素の整数値（1 〜 6）が配置されるような\( 25000 \times 1000 \)の行列\( A \)を人工的に作成し
\footnote{実際の索引語文書行列に似せるよう考慮している．}，
その行列に対して{\tt las2 }で特異値分解を行ってみた．Pentium-4 1.5GHz メモリ 512Mバイトの Linux 環境での
実行時間は 227秒，要したメモリは 228M バイトであった．
この程度の大きさの行列であれば，実行時間は大きな問題にはならないと思われる．

ただし，行列の大きさを変更して同じ条件で試してみると\mbox{表\ref{sokudo}}の結果が得られた．
メモリは行列のサイズにほぼ比例するが実行時間は指数関数的に増加しているので，
実行時間の面からも，この程度の大きさの行列が SVDPACKC で扱える限度だと思われる．
ちなみに\( 25000 \times 2000 \)の行列ではメモリ不足で実行できなかった．
ただし実験で用いたマシンにスワップは設定されていないことを注記しておく．
スワップを利用すれば，更に大きな行列も扱えるが，その場合は実行時間の方で
問題が生じるであろう．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \caption{行列の大きさと速度・メモリの関係}\label{sokudo}
    \begin{tabular}{|c|c|c|c|c|} \hline
                &   \( 25000 \times 125 \) & \( 25000 \times 250 \) & \( 25000 \times 500 \) & \( 25000 \times 1000 \) \\  \hline
使用メモリ(MB)  &    26.2      &    52.6    &    108    &   228      \\
実行時間（秒）  &     7.49     &    16.8    &   53.5    &   227      \\ \hline
    \end{tabular}
  \end{center}
\end{table}

実際に情報検索で用いられる索引語ベクトルの次元数は少なくとも数十万単位になり，
検索対象の文書も 100万文書以上となるであろう．
その場合の索引語文書行列\( A \)の大きさは巨大なスパース行列である．
このような巨大な行列になると，SVDPACKC によって一気に特異値分解を行うのは不可能である．
この問題に対しては最初に小さな行列で特異値分解を行い，その後に
文書や索引語の追加に従って特異値分解の更新を行う folding-in とよばれる手法や
大規模な文書集合から文書をランダムサンプルし，そこから特異値分解を
行う手法などが提案されている\cite{kita-ir}．あるいは概念ベクトルの選択に
特異値分解以外の手法を使うアプローチもある（\cite{sasaki}など）．
最近では言語横断検索にも LSI が利用されているが\cite{dumais}，
そこでも大規模な行列の特異値分解をどう行うかが問題点として上がっている\cite{mori}．
結局，現実の情報検索で現れるような大規模な行列に対しては，
SVDPACKC を直接利用することはできない．
しかしアイデアを試すための中規模の実験であれば，十分にその役割を果たせる．

実験では圧縮する次元の数を交差検定では 75 に，実際の評価では 100 に固定している．
この値は適当である．最適な次元数については様々な議論があるが，
ここでは SVDPACKC の利用例として紹介した実験であるため，
最適な次元数を推定する処理は行わなかった．
ちなみに実際の評価における次元数を 100 から増減させた場合の，実験結果を\mbox{表\ref{jigen}}に示す．
次元数を 100 に圧縮するといっても行列のランク数がそれ以下であれば，100よりも
小さい数になるので，100のときに圧縮された次元数を基準に $-$20, $-$10, +10, +20 と
次元数を変更させて実験を行った．また表中に MAX とあるのは，行列のランク数で圧縮した場合を示す．
これが圧縮できる次元の最大値である．
大まかな傾向としては次元数が多い方が精度は高いようである．
ただし最高精度を記録する次元数は個々の単語によって異っており，
最適な次元数は問題に依存すると言える．

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \caption{圧縮次元数と精度の関係}\label{jigen}
    \begin{tabular}{|c|c|c|c|c|c|c|} \hline
                &   $-$20  &  $-$10    & 100      & +10       & +20      & MAX   \\  \hline
判別精度        &  0.7030 &  0.7168 & 0.7202  &  0.7212   &  0.7202  & 0.7203 \\ \hline
    \end{tabular}
  \end{center}
\end{table}

LSI のアイデア自体は情報検索以外にも適用できる．
ここでは語義判別問題への利用を試みた．
他にも文書分類への応用が報告されている\cite{zelikovitz}．
このような教師付き学習のタイプでは，訓練事例数が大規模なものになることはないため，
SVDPACKC が利用できる．
また素性ベクトルの次元圧縮という手法は，統計学では主成分分析，パターン認識では
Karhunen-Lo\`{e}ve 展開や線形判別法\cite{ishii}として知られている手法である．
またデータマイニングの分野ではデータ数が非常に大きいために，
現実的には機械学習手法を直接適用できないという問題がある．
そのために類似する事例集合を抽象表現として表される事例に変換し，
変換後の事例に対して機械学習手法を適用する Data Squashing という
手法が使われる\cite{suzuki}．これは索引語ベクトルではなく
文書ベクトルに対する次元圧縮の手法に対応する．
このように次元圧縮の手法は様々な分野で重要であり，
新しい手法が次々と提案されている（例えば\cite{suenaga}など）．
次元圧縮の手法として，特異値分解は古典的と言えるが，ベースとなる手法として
容易に試すことのできる意味でも SVDPACKC は有用であろう．

最後に LSI を分類問題に利用する場合の注意を述べておく．
次元圧縮を行う手法は種々あるが，それらは2つに大別できる．
１つは「表現のための次元圧縮」であり，もう１つは「判別のための次元圧縮」である\cite{ishii}．
「表現のための次元圧縮」は素性ベクトルの分布全体のもつ情報をできるだけ
反映できるように次元を圧縮する．一方，「判別のための次元圧縮」は
クラスをできるだけ明確に分離できるように次元を圧縮する．
主成分分析やKarhunen-Lo\`{e}ve 展開は前者であり，線形判別法は後者である．
そして特異値分解も「表現のための次元圧縮」に属する手法である．
このため，特異値分解を行ったからといって必ずしも判別精度が高まることは保証されない．
「表現のための次元圧縮」が判別精度向上に寄与できる問題は，
非常に高次元のベクトルを扱う問題（例えば情報検索や音声・画像認識）だと思われる．
このような場合，「表現のための次元圧縮」は ``次元の呪い''に対抗できる可能性がある．
あるいは次元数が多くなったときに素性間に共起性（依存関係）が生じる
傾向があり，それが精度向上に悪影響を及ぼすが，そのような依存関係を解消できる可能性ももつ．

特異値分解による次元圧縮が判別精度の向上に寄与できるかどうかは未知である．
本研究では交差検定を行うことで，精度向上に寄与できそうな問題を選別しておく
というアプローチをとった．しかし，LSI法は平均的には他の学習手法よりも
精度が低かった．LSI 法を語義判別問題に利用するためには，また別の工夫が必要になるだろう．
１つの利用可能性としてはbagging 手法\cite{breiman96}の１つの学習器として使うことが
考えられる．
実際に，LSI 法は数個の単語に関しては他の学習手法よりも精度が高かった．
また NN法まで含めるとその数は更に増える．
SENSEVAL2 の辞書タスクでは様々な学習手法を融合して用いる
手法が最も良い成績を納めた\cite{murata-sen2}．
そこでは，決定リスト，Naive Bayes，SVM の学習手法を用意し，交差検定の結果から
単語毎に利用する学習手法を設定している．
ここで用いた NN法 や LSI法も１つの学習手法としてエントリーさせておけばよい．

今回の実験では，多くの単語に対して LSI法は NN法よりも正解率が低かった．
特に，語義判別の場合，素性ベクトルの次元数\( m \)に比べ，訓練事例数\( n \)が小さい．
特異値分解で圧縮する次元数の最大値は\( n \)なので，
この点でかなり制約があった．交差検定を用いることで NN 法の精度を高めることができたが，
他の学習手法と比べると精度の面ではまだ十分ではない．
今後は NN法や LSI法が他の学習手法よりも正解率が高かった単語について，その原因を調査する．
これによって LSI を語義判別問題のような分類問題に利用する方法を
探ってゆく．またLSI が利用可能な他の問題を調べゆく．





\section{おわりに}


本論文ではフリーの特異値分解ツール SVDPACKC を紹介した．
その利用方法を解説し，利用事例として語義判別問題を扱った．
SENSEVAL2 の辞書タスクの動詞 50単語を対象に実験を行ったところ，
交差検定を合わせて用いることで，NN法を改良できた．
また NN法や LSI法は，一部の単語に対して
決定リストや Naive Bayes 以上の正解率が得られることも確認できた．
特異値分解は，情報検索の LSI だけではなく，高次元の特徴ベクトルを重要な低次元の
ベクトルに射影する手法で必要とされる．
このために様々な応用が期待される．
今後はここでの実験の結果を詳しく調査し，LSI が利用可能な問題を
調べてゆきたい．




\bibliographystyle{jnlpbbl}
\bibliography{408}


\newpage
\appendix


\begin{table}[ht]
\scriptsize
  \begin{center}
    \leavevmode
    \caption{las2 による特異値分解結果(1)}
    \begin{tabular}{|p{6zw}|c|c|c|c|c|} \hline
単語  &  行列サイズ &  非ゼロ密度 &  圧縮次元数 &   メモリ(MB) & 実行時間(秒) \\ \hline
ataeru & \( 431 \times 87 \) & 0.0232    & 75.00 & 0.51   & 0.1225   \\
iu & \( 937 \times 274 \) & 0.0087       & 75.00 & 3.93   & 1.8625   \\
ukeru & \( 1138 \times 267 \) & 0.0092   & 75.00 & 4.21   & 2.0050   \\
uttaeru & \( 292 \times 52 \) & 0.0315   & 26.50 & 0.20   & 0.0225   \\
umareru & \( 309 \times 48 \) & 0.0338   & 32.75 & 0.19   & 0.0325   \\
egaku & \( 339 \times 52 \) & 0.0283     & 36.25 & 0.22   & 0.0350   \\
omou & \( 981 \times 348 \) & 0.0079     & 75.00 & 5.67   & 3.0700   \\
kau & \( 375 \times 65 \)   & 0.0241     & 65.25 & 0.32   & 0.0700   \\
kakaru & \( 482 \times 86 \) & 0.0233    & 66.75 & 0.54   & 0.1150   \\
kaku\_v & \( 498 \times 101 \) & 0.0197  & 65.00 & 0.68   & 0.1400   \\
kawaru & \( 424 \times 72 \) & 0.0224    & 72.75 & 0.40   & 0.0950    \\
kangaeru & \( 953 \times 218 \) & 0.0103 & 75.00 & 2.87   & 1.2775   \\
kiku & \( 569 \times 135 \) & 0.0154     & 75.00 & 1.09   & 0.2925   \\
kimaru & \( 407 \times 87 \) & 0.0239    & 75.00 & 0.47   & 0.1050   \\
kimeru & \( 656 \times 171 \) & 0.0137   & 75.00 & 1.52   & 0.3975   \\
kuru & \( 493 \times 96 \) & 0.0194      & 75.00 & 0.63   & 0.2925   \\
kuwaeru & \( 418 \times 81 \) & 0.0215   & 66.00 & 0.46   & 0.1000   \\
koeru & \( 460 \times 89 \) & 0.0227     & 67.00 & 0.54   & 0.1125   \\
shiru & \( 797 \times 184 \) & 0.0111    & 75.00 & 2.04   & 0.6225    \\
susumu & \( 473 \times 84 \) & 0.0215    & 75.00 & 0.51   & 0.1175    \\
susumeru & \( 529 \times 99 \) & 0.0193  & 75.00 & 0.68   & 0.1675   \\
dasu & \( 791 \times 156 \) & 0.0130     & 75.00 & 1.61   & 0.3900   \\
chigau & \( 522 \times 78 \) & 0.0190    & 55.75 & 0.50   & 0.0950   \\
tsukau & \( 1056 \times 202 \) & 0.0093  & 75.00 & 2.75   & 1.1400   \\
tsukuru & \( 648 \times 137 \) & 0.0146  & 75.00 & 1.09   & 0.3200  \\
tsutaeru & \( 377 \times 72 \) & 0.0252  & 72.25 & 0.36   & 0.0875      \\
dekiru & \( 364 \times 56 \) & 0.0266    & 56.25 & 0.26   & 0.0600        \\
deru & \( 1153 \times 309 \) & 0.0083    & 75.00 & 5.17   & 2.8725          \\
tou & \( 265 \times 53 \) & 0.0405       & 52.25 & 0.19   & 0.0475           \\
toru & \( 457 \times 84 \) & 0.0221      & 57.25 & 0.50   & 0.0925          \\
nerau & \( 318 \times 50 \) & 0.0290     & 50.25 & 0.20   & 0.0425         \\
nokosu & \( 436 \times 73 \) & 0.0216    & 73.50 & 0.41   & 0.1000        \\
noru & \( 258 \times 48 \) & 0.0386      & 33.75 & 0.17   & 0.0300          \\
hairu & \( 974 \times 208 \) & 0.0106    & 75.00 & 2.71   & 0.9075         \\
hakaru & \( 365 \times 63 \) & 0.0285    & 63.00 & 0.30   & 0.0700        \\
hanasu & \( 382 \times 131 \) & 0.0195   & 75.00 & 0.82   & 0.1575        \\
hiraku & \( 657 \times 168 \) & 0.0161   & 75.00 & 1.60   & 0.4325        \\
fukumu & \( 520 \times 69 \) & 0.0223    & 49.25 & 0.42   & 0.0725        \\
matsu & \( 380 \times 62 \) & 0.0274     & 45.00 & 0.30   & 0.0525         \\
matomeru & \( 381 \times 69 \) & 0.0293  & 69.75 & 0.35   & 0.0800      \\
mamoru & \( 392 \times 69 \) & 0.0236    & 69.75 & 0.36   & 0.0800        \\
miseru & \( 357 \times 75 \) & 0.0248    & 74.50 & 0.37   & 0.0800        \\
mitomeru & \( 729 \times 159 \) & 0.0132 & 75.00 & 1.58   & 0.4475      \\
miru & \( 1229 \times 306 \) & 0.0076    & 75.00 & 5.29   & 2.8975          \\
mukaeru & \( 348 \times 69 \) & 0.0318   & 69.00 & 0.33   & 0.0750       \\
motsu & \( 1020 \times 200 \) & 0.0101   & 75.00 & 2.64   & 0.8900         \\
motomeru & \( 975 \times 229 \) & 0.0104 & 75.00 & 3.09   & 1.1875      \\
yomu & \( 406 \times 79 \) & 0.0238      & 75.00 & 0.43   & 0.1025          \\
yoru & \( 1001 \times 355 \) & 0.0092    & 75.00 & 5.97   & 3.0350          \\
wakaru & \( 425 \times 133 \) & 0.0196   & 65.50 & 0.90   & 0.1725       \\ \hline
    \end{tabular} \label{jigen-com1}
  \end{center}
\end{table}

\begin{table}[ht]
\scriptsize
  \begin{center}
    \leavevmode
    \caption{las2 による特異値分解結果(2)}
    \begin{tabular}{|p{6zw}|c|c|c|c|c|} \hline
単語  &  行列サイズ &  非ゼロ密度 &  圧縮次元数 &   メモリ(MB) & 実行時間(秒) \\ \hline
ataeru & \( 529 \times 116 \) & 0.0189     &  100  & 0.85   & 0.22    \\
iu & \( 1158 \times 366 \) & 0.0070        &  100  & 6.68   & 4.16        \\
ukeru & \( 1382 \times 357 \) & 0.0076     &  100  & 7.05   & 3.97     \\
uttaeru & \( 365 \times 70 \) & 0.0252     &  27   & 0.34   & 0.03   \\
umareru & \( 385 \times 65 \) & 0.0272     &  64   & 0.32   & 0.07   \\
egaku & \( 429 \times 70 \) & 0.0223       &  32   & 0.38   & 0.05     \\
omou & \( 1201 \times 465 \) & 0.0064      &  100  & 9.77   & 6.47      \\
kau & \( 472 \times 87 \) & 0.0192         &  87   & 0.54   & 0.14       \\
kakaru & \( 598 \times 115 \) & 0.0187     &  100  & 0.89   & 0.23    \\
kaku\_v & \( 606 \times 135 \) & 0.0162    &  100  & 1.12   & 0.30     \\
kawaru & \( 532 \times 97 \) & 0.0179      &  97   & 0.67   & 0.16    \\
kangaeru & \( 1156 \times 291 \) & 0.0085  &  100  & 4.81   & 2.55  \\
kiku & \( 711 \times 180 \) & 0.0123       &  100  & 1.85   & 0.62      \\
kimaru & \( 498 \times 117 \) & 0.0196     &  100  & 0.77   & 0.20     \\
kimeru & \( 807 \times 228 \) & 0.0111     &  100  & 2.78   & 0.79    \\
kuru & \( 612 \times 128 \) & 0.0156       &  100  & 1.06   & 0.30       \\
kuwaeru & \( 517 \times 109 \) & 0.0174    &  53   & 0.77   & 0.11   \\
koeru & \( 580 \times 119 \) & 0.0180      &  100  & 0.92   & 0.23     \\
shiru & \( 986 \times 246 \) & 0.0090      &  100  & 3.46   & 1.09     \\
susumu & \( 581 \times 112 \) & 0.0175     &  100  & 0.86   & 0.21    \\
susumeru & \( 652 \times 132 \) & 0.0157   &  100  & 1.15   & 0.30   \\
dasu & \( 978 \times 208 \) & 0.0105       &  100  & 2.69   & 0.97      \\
chigau & \( 653 \times 105 \) & 0.0152     &  61   & 0.84   & 0.15    \\
tsukau & \( 1309 \times 270 \) & 0.0075    &  100  & 4.65   & 1.97    \\
tsukuru & \( 811 \times 183 \) & 0.0117    &  100  & 1.80   & 0.51   \\
tsutaeru & \( 464 \times 97 \) & 0.0205    &  58   & 0.61   & 0.11   \\
dekiru & \( 461 \times 75 \) & 0.0211      &  75   & 0.43   & 0.11     \\
deru & \( 1387 \times 412 \) & 0.0069      &  100  & 8.63   & 5.81       \\
tou & \( 328 \times 71 \) & 0.0326         &  69   & 0.32   & 0.07        \\
toru & \( 560 \times 112 \) & 0.0180       &  54   & 0.84   & 0.13       \\
nerau & \( 404 \times 67 \) & 0.0229       &  67   & 0.34   & 0.07      \\
nokosu & \( 544 \times 98 \) & 0.0174      &  98   & 0.69   & 0.16     \\
noru & \( 321 \times 64 \) & 0.0311        &  28   & 0.28   & 0.04       \\
hairu & \( 1199 \times 278 \) & 0.0086     &  100  & 4.52   & 2.04      \\
hakaru & \( 448 \times 84 \) & 0.0232      &  84   & 0.50   & 0.12     \\
hanasu & \( 480 \times 175 \) & 0.0155     &  100  & 1.45   & 0.28     \\
hiraku & \( 795 \times 224 \) & 0.0133     &  100  & 2.69   & 0.85     \\
fukumu & \( 649 \times 92 \) & 0.0179      &  91   & 0.70   & 0.18     \\
matsu & \( 473 \times 83 \) & 0.0220       &  42   & 0.51   & 0.07      \\
matomeru & \( 467 \times 93 \) & 0.0239    &  93   & 0.58   & 0.13   \\
mamoru & \( 492 \times 93 \) & 0.0188      &  93   & 0.60   & 0.16     \\
miseru & \( 448 \times 100 \) & 0.0198     &  99   & 0.62   & 0.16     \\
mitomeru & \( 890 \times 212 \) & 0.0108   &  100  & 2.65   & 0.75   \\
miru & \( 1502 \times 408 \) & 0.0062      &  100  & 8.90   & 5.87       \\
mukaeru & \( 423 \times 93 \) & 0.0262     &  92   & 0.55   & 0.13    \\
motsu & \( 1246 \times 267 \) & 0.0083     &  100  & 4.40   & 2.13      \\
motomeru & \( 1171 \times 306 \) & 0.0086  &  100  & 5.08   & 2.50    \\
yomu & \( 513 \times 106 \) & 0.0188       &  100  & 0.73   & 0.17       \\
yoru & \( 1218 \times 474 \) & 0.0076      &  100  & 10.10  & 5.30       \\
wakaru & \( 528 \times 178 \) & 0.0158     &  100  &  1.44  & 0.45       \\ \hline
    \end{tabular}\label{jigen-com2}
  \end{center}
\end{table}


\begin{biography}
\newpage
\biotitle{略歴}
\bioauthor{新納 浩幸}{
1985年東京工業大学理学部情報科学科卒業．
1987年同大学大学院理工学研究科情報科学専攻修士課程修了．
同年富士ゼロックス，翌年松下電器を経て，
1993年茨城大学工学部システム工学科助手．
1997年同学科講師，2001年同学科助教授．
情報処理学会，人工知能学会，言語処理学会，ACL 各会員．博士(工学)．}

\bioauthor{佐々木 稔}{
1996年徳島大学工学部知能情報工学科卒業．
2001年徳島大学大学院博士後期課程修了．博士(工学)．
現在，茨城大学工学部情報工学科助手．
機械学習や統計的手法による情報検索，自然言語処理等に関する研究に従事．
情報処理学会，言語処理学会各会員．}

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

\end{biography}
\end{document}
