
\documentstyle[epsf,jnlpbbl]{jnlp_j_b5}

\setcounter{page}{5}
\setcounter{巻数}{8}
\setcounter{号数}{1}
\setcounter{年}{2001}
\setcounter{月}{1}
\受付{2000}{4}{14}
\再受付{2000}{6}{26}
\採録{2000}{10}{10}

\setcounter{secnumdepth}{2}

\title{ランダム・プロジェクションによる\\ベクトル空間情報検索モデルの次元削減}
\author{佐々木 稔\affiref{Tdoc} \and 北 研二\affiref{Toku}}

\headauthor{佐々木 稔・北 研二}
\headtitle{ランダム・プロジェクションによるベクトル空間情報検索モデルの次元削減}

\affilabel{Tdoc}{徳島大学大学院工学研究科}
{Graduate School of Engineering, University of Tokushima}
\affilabel{Toku}{徳島大学工学部}
{Faculty of Engineering, University of Tokushima}


\jabstract{
ベクトル空間モデルは情報検索における代表的な検索モデルである．
ベクトル空間モデルでは文書を索引語の重みベクトルで表現するが，
文書ベクトルは一般に要素数が非常に多く，スパースなベクトルに
なるため，検索時間の長さや必要なメモリの量が大きな問題となる．
本論文では，この問題を解決するため，ベクトル空間モデルにおける
ベクトルの次元圧縮を行う手法としてランダム・プロジェクションを
用いた検索モデルを提案する．
その有効性を評価するために，評価用テストコレクションである 
MEDLINEを利用して，検索実験を行った．
その結果，ランダム・プロジェクションはLSI(Latent Semantic Indexing)
に比べ高速で，かつ同等な検索性能を持つ次元圧縮手法であることが確認された．
また，ランダム・プロジェクションで次元圧縮に必要な行列を得るために，
球面 $k$ 平均アルゴリズムで得られる概念ベクトルの利用を提案する．
同様に検索実験を行った結果，任意のベクトルを用いた検索性能に比べ改善され，
概念ベクトルが検索性能の向上に有効であることが確認された．
}

\jkeywords{情報検索，ベクトル空間モデル，ランダム・プロジェクション，LSI，概念ベクトル}

\etitle{Dimensionality Reduction of Vector Space \\ Information Retrieval Model
Based on \\ Random Projection}
\eauthor{Minoru Sasaki\affiref{Tdoc} \and
	Kenji Kita\affiref{Toku}}

\eabstract{
Vector space model is a conventional information retrieval model,
in which text documents are represented as high-dimensional and 
sparse vectors using words as features in a multidimensional space.
These vectors require a large number of computer resources and 
it is difficult to capture underlying concepts referred to by the terms.
In this paper, we present a technique of an information retrieval model
using a random projection to project document vectors 
to a low-dimensional space as a way of solving these problems.
To evaluate its efficiency, we show results of retrieval experiments 
on the MEDLINE test collection.
Experiments show that the proposed method is faster 
than LSI(Latent Semantic Indexing) and efficient close to the LSI.
In addition, we propose to apply a concept vector, 
which random projection needs for dimensionality reduction, 
produced by a spherical $k$-means algorithm.
A result of this evaluation shows that the concept vector captures 
the underlying concepts of the corpus effectively.
}

\ekeywords{Information retrieval, Vector space model, Random projection, 
Latent semantic indexing, Concept vector}

\begin{document}
\maketitle


\section{はじめに}
近年，インターネットの普及とともに，個人でWWW (World Wide Web)を代表とする
ネットワーク上の大量の電子データやデータベースが取り扱えるようになり，
膨大なテキストデータの中から必要な情報を取り出す機会が増加している．
しかし，このようなデータの増加は必要な情報の抽出を困難とする原因となる．
この状況を反映し，情報検索，情報フィルタリングや文書クラスタリング等の
技術に関する研究開発が盛んに進められている．

情報検索システムの中でよく使われている検索モデルに，
ベクトル空間モデル\cite{salton}がある．
ベクトル空間モデルは，文書と検索要求を多次元空間ベクトルとして
表現する方法である．
基本的には，文書集合から索引語とするタームを取り出し，タームの頻度などの
統計的な情報により，文書ベクトルを表現する．
この際，タームに重みを加えることにより，
文書全体に対するタームの特徴を目立たせることが可能である．
この重みを計算するために，IDF(Inverse Document Freqency)\cite{chisholm}
などの重みづけ方法が数多く提案されている．
また，文書と検索要求を比較する類似度の尺度として，
内積や余弦(cosine)がよく用いられている．
この類似度計算により，類似度の高いものからランクづけを行い，
ユーザに表示することができることもベクトル空間モデルの特徴のひとつである．

ベクトル空間モデルを用いた検索システムを新聞記事などの大量の
文書データに対して適用した場合，
文書データ全体に存在するタームの数が非常に多くなるため，
文書ベクトルは高い次元を持つようになる．
しかし，ひとつの文書データに存在するタームの数は文書データ全体の
ターム数に比べると非常に少なく，文書ベクトルは要素に0の多い，
スパースなベクトルになる．
このような文書ベクトルを用いて類似度を計算する際には，
検索時間の増加や文書ベクトルを保存するために必要な
メモリの量が大きな問題となる．
このため，単語の意味や共起関係などの情報を用いたり，
ベクトル空間の構造を利用してベクトルの次元を圧縮する研究が盛んに行われている．
このようなベクトルの次元圧縮技術には，統計的なパターン認識技術や
線形代数を用いた手法などが用いられている\cite{Kolda}\cite{Faloutsos}．
この中で，最も代表的な手法として，LSI (Latent Semantic Indexing)がある
\cite{Deerwester}\cite{Dumais}．
この手法は，文書・単語行列を特異値分解を用いて，低いランクの近似的な行列を
求めるものであり，これを用いた検索システムは，次元圧縮を行わない検索モデルと
比較して一般的に良い性能を示す．
しかし，特異値分解に必要な計算量が大きいために，
検索モデルを構築する時間が非常に長いことが問題となっている．

上記の問題を解決するベクトル空間モデルの次元圧縮手法に，
ランダム・プロジェクション\cite{Arriaga}が存在する．
ランダム・プロジェクションは，あらかじめ指定した数のベクトルとの内積を
計算することで次元圧縮を行う手法である．
これまでに報告されているランダム・プロジェクションを用いた研究には，
VLSI(Very Large-Scale Integrated circuit)の設計問題への利用\cite{Vempala}や
次元圧縮後の行列の特性を理論的に述べたものがある
\cite{Papadimitriou}\cite{Arriaga}．
しかし，これらの文献では，ランダム・プロジェクションの理論的な特性は
示されているものの，情報検索における具体的な実験結果は報告されていない．
そのため，情報検索に対するランダム・プロジェクションの有効性に疑問が残る．

我々は，ランダム・プロジェクションを用いた情報検索モデルを構築し，
評価用テストコレクションであるMEDLINEを利用した検索実験を行った．
この検索実験より，情報検索における次元圧縮手法として，
ランダム・プロジェクションが有効であることを示す．
また，ランダム・プロジェクションを行う際にあらかじめ指定するベクトルとして，
文書の内容を表す概念ベクトル\cite{Dhillon}の利用を提案する．
概念ベクトルは文書の内容が似ているベクトル集合の重心で，
この概念ベクトルを得る際，高次元でスパースな文書データ集合を高速に
クラスタリングすることができる球面 $k$ 平均アルゴリズム\cite{Dhillon}を用いる．
これにより，文書集合を自動的にクラスタリングできるだけでなく，
ランダム・プロジェクションに必要な概念ベクトルも同時に得ることができる．
この概念ベクトルをランダム・プロジェクションで用いることにより，
任意のベクトルを用いた検索性能と比較して，検索性能が改善されていることを示し，
概念ベクトルを利用した次元圧縮の有効性を示す．

\section{ランダム・プロジェクションによるベクトルの次元圧縮}
本節では，ランダム・プロジェクションを用いた
ベクトル空間モデル\cite{Papadimitriou}\cite{Arriaga}についての概観を述べる．
ランダム・プロジェクションは，ひとつの文書データを 
$n$ 次元空間上のベクトル ${\bf u}$ として表現するとき，
このベクトルを $k\ (k < n)$ 次元空間に射影する手法である．
その際， $k$ 個の任意の $n$ 次元ベクトル ${\bf r}_1, \cdots , {\bf r}_k$ 
を用意する．
用意したこれらのベクトルと $n$ 次元ベクトル ${\bf u}$ の内積，
\begin{equation}
{\bf u}'_1 = {\bf r}_1 \cdot {\bf u}, \cdots , {\bf u}'_k ={\bf r}_k \cdot {\bf u}
\end{equation}
をそれぞれ計算する．
その結果，$k$ 次元に圧縮した ${\bf u}'_1, \cdots , {\bf u}'_k$ を
要素とするベクトルが得られる．

次元圧縮に必要なベクトル ${\bf r}_1, \cdots , {\bf r}_k$ を
列ベクトルとする $n \times k$ の行列 ${\bf R}$ を用いると，
求める $k$ 次元ベクトルは
\begin{equation}
{\bf u}' = {\bf R}^T {\bf u}
\end{equation}
となり，
ランダム・プロジェクションは行列計算のみの簡単な形で表現することができる．
この行列 ${\bf R}$ が任意の正規直交行列のとき，すなわち，行列 ${\bf R}$ の
列ベクトルがすべて単位ベクトルで，かつ，相異なる列ベクトルが互いに
直交していれば，ランダム・プロジェクションは射影前後におけるベクトル間距離を
近似的に保存する特性を持っている．

\section{概念ベクトルを用いたランダム・プロジェクション}
ランダム・プロジェクションに必要な行列 ${\bf R}$ は，これまでの研究では
正規分布などの確率分布をなす任意の行列が
用いられている\cite{Papadimitriou}\cite{Vempala}\cite{Arriaga}
\cite{Kleinberg}\cite{Blum}\cite{Feige}．
このような行列を用いて任意の部分空間に射影する場合，
次元圧縮を行う前後の任意のベクトル間距離は近似的に保存されることが
示されている\cite{Frankl}\cite{Johnson}．
しかし，任意の正規直交行列を用いる場合，次元圧縮を行う前後のベクトル間距離を
保存する効果は得られたとしても，LSIのように，ベクトルの要素が
抽象的な意味を持つ索引語の生成や
内容的に関連のある文書をまとめる効果があるとは考えられない．
このことから，LSIのような，情報検索に有効な索引語を生成するために，
ランダム・プロジェクションの改良が課題となる．

このような課題を解決するものとして，ランダム・プロジェクションで
ベクトルを次元圧縮をした後，さらに特異値分解を行うことにより，
LSIの効果を得る手法が提案されている\cite{Papadimitriou}．
この手法は，関連文書をまとめる効果を得ると同時に，
特異値分解のみを用いた場合に比べ，モデル作成に必要な時間を
短縮したものである．
しかし，ランダム・プロジェクションと特異値分解は，
共にベクトル間距離を保存する効果を持つ手法であるため，
特異値分解が内容的に関連のある文書，あるいはタームをまとめるために
適用されているとしても，これらの手法を同時に利用することは，
検索モデルを構築する時間に関して，効率の良い手法であるとはいえない．
さらに，非常に大きい次元数をもつ行列について考えた場合，
特異値分解に多くの計算量が必要であることも問題となる．
したがって，特異値分解により誤差を最小とする近似行列を得る代わりに，
誤差は最小ではないものの，ランダム・プロジェクションのみを用いてLSIの
効果を得ることで，より高速に検索モデルが構築できるのではないかと考えられる．

これを実現するために，我々は，ランダム・プロジェクションにおける
行列 ${\bf R}$ に，文書の内容を表現した概念ベクトルを利用することを提案する．
概念ベクトルは，文書ベクトル集合をクラスタリングしてできたクラスタの，
各クラスタに属する文書ベクトルの重心を正規化したベクトルとして表される．
この概念ベクトルによる次元圧縮は，単にベクトルを近似するだけではなく，
クラスタに属するベクトル集合の重心を求めることにより，ターム間で
特徴づけられる隠れた関連性やタームの同義性と多義性を捉えることができる．
クラスタリングにより得られた各クラスタは互いに異なる概念を持ち，
これより得られる概念ベクトルが圧縮した空間の軸となるように用いられる．
これにより，次元圧縮された行列は文書と概念ベクトルの類似度を表し，
元の空間において内容の近い文書は，圧縮した空間においても
近くなる可能性がある．
また，類似しているが，異なるタームを使った文書の場合，
元の空間では近くないが，圧縮した空間では近くなる可能性があり，
検索性能が改善されると考えられる．
さらに，多義語により元の空間において近いとされる文書どうしが
圧縮した空間では遠くに離れ，誤った検索が取り除かれる可能性も期待できる．
このように，これまで単語などが要素であったベクトルが，
文書の内容を要素とするようなベクトルに変換され，
文書を低い次元で，より検索性能が向上するベクトル表現ができると考えられる．

概念ベクトルからなる行列 ${\bf R}$ を求めるために，
球面 $k$ 平均アルゴリズム\cite{Dhillon}と呼ばれるクラスタリング手法を用いる．
球面 $k$ 平均アルゴリズムは，目的関数が局所的に最大となるまで，
高い次元でスパースな文書データ集合をクラスタリングする手法である．
球面 $k$ 平均アルゴリズムでは，ユークリッド空間内でベクトル間のなす角の余弦を
類似度とし，多次元空間の単位円を分割することによりクラスタリングを行う．
これにより，文書ベクトルの集合は指定した数の部分集合に分割され，
各クラスタの中心を計算することで，容易に概念ベクトルを作ることができる．
さらに，このアルゴリズムは文書ベクトルのスパースさを逆に利用して高速に
収束する利点を持ち，得られる概念ベクトルは特異値分解を
用いたものに非常に近いことが示されている\cite{Dhillon}．

しかし，球面 $k$ 平均アルゴリズムにより得られる概念ベクトルは
一般的に直交性を満たしているとは限らないため，概念ベクトルを
ランダム・プロジェクションに適用するには疑問が生じる．
先に述べたように，距離を保存するには正規直交性を満たすベクトルを
利用する必要があるが，この概念ベクトルをランダム・プロジェクションに
適用する場合，直交性を満たしていないとしても独立であれば，
任意の行列においても十分に距離を保存する可能性のあることが示されている
\cite{Arriaga}．
球面 $k$ 平均アルゴリズムでは，内容的に似通ったベクトルをクラスタとして
まとめるため，原理的には独立した概念ベクトルを生成すると考えられる．
このため，直交性に関して，概念ベクトルをランダム・プロジェクションに
適用するのは問題ないと考えられる．

本節では，まず，球面 $k$ 平均アルゴリズムの概要を述べる前に，
クラスタリングにより得られる概念ベクトルについて述べる．

\subsection{概念ベクトル}
ベクトルの集合をベクトル空間にプロットしたとき，
同質のベクトルが多く存在する場合を除いて，いくつかのグループに分かれる．
このようなグループはクラスタと呼ばれ，類似した内容をもつ
ベクトルの集合が形成される．
概念ベクトルはクラスタに属するベクトルの重心を求めることにより得られ，
そのクラスタの内容を表す代表ベクトルである．

概念ベクトルを求める例として，正規化された $N$ 個のベクトル 
${\bf x}_1, {\bf x}_2, \cdots , {\bf x}_N$ を，
異なる $s\ (s < N)$ 個のクラスタ $\pi_1, \pi_2, \cdots , \pi_s$ 
にクラスタリングすることを考える．
このとき，ひとつのクラスタ $\pi_j$ に含まれるベクトル $x_i$ の平均である
重心 ${\bf m}_j$ は以下のように表される．
\begin{equation}
{\bf m}_j = \frac{1}{n_j} \sum_{{\bf x}_i \in \pi_j} {\bf x}_i
\end{equation}
ここで $n_j$ はクラスタ $\pi_j$ に含まれるベクトルの数を表す．
ベクトルの重心は単位長にはなっていないので，そのベクトルの長さで
割ることにより概念ベクトル ${\bf c}_j$ を得る．
\begin{equation}
{\bf c}_j = \frac{{\bf m}_j}{\| {\bf m}_j \|}
\end{equation}

\subsection{目的関数} \label{moku}
$k$ 平均アルゴリズムでは，目的関数は一般的に概念ベクトルと
クラスタに属するベクトルとの距離の和
\begin{equation}
\sum_{{\bf x}_i \in \pi_j} \| {\bf m}_j - {\bf x}_i \|
\end{equation}
を最小にするような概念ベクトルを求める，最小二乗法が用いられる．
球面 $k$ 平均アルゴリズムでは，このような最小化問題ではなく，
ミクロ経済学の分野における，生産計画の最適化問題で扱われている目的関数を
用いている\cite{Kleinberg}．
これは，各クラスタ $\pi_{j} (1 \leq j \leq s)$ の密度を
\begin{equation}
\sum_{{\bf x}_i \in \pi_j} {\bf x}_i^T {\bf c}_j
\end{equation}
とし，クラスタの結合密度の和を目的関数としている．
\begin{equation}
D = \sum_{j =1}^{s} \sum_{{\bf x}_i \in \pi_j} {\bf x}_i^T {\bf c}_j
\end{equation}

クラスタの密度は，以下のコーシー・シュワルツの不等式より，
任意の単位ベクトル ${\bf z}$ に対して，
クラスタ $\pi_j$ に含まれるベクトル $x_i$ と概念ベクトルとの内積の
総和が最大となる．
\begin{equation}
\sum_{{\bf x}_i \in \pi_j} {\bf x}_i^T {\bf z} \leq 
\sum_{{\bf x}_i \in \pi_j} {\bf x}_i^T {\bf c}_j
\end{equation}
また，クラスタの密度は，それに属するベクトル和の距離に
等しくなるという特徴を持っている．
\begin{equation}
\sum_{{\bf x}_i \in \pi_j} {\bf x}_i^T {\bf c}_j = 
\| \sum_{{\bf x}_i \in \pi_j} {\bf x}_i \|
\end{equation}

\subsection{球面 $k$ 平均アルゴリズム}
\ref{moku}節で示した目的関数 $D$ を最大にするように，
ベクトルの集合を反復法によりクラスタリングする．
文書ベクトル ${\bf x}_1, {\bf x}_2, \cdots , {\bf x}_N$ を 
$s$ 個のクラスタ $\pi_1^{\star}, \pi_2^{\star}, \cdots , \pi_s^{\star}$ に
分割するためのアルゴリズムを以下に示す．
\begin{enumerate}
\item すべての文書ベクトルを $s$ 個のクラスタに任意に分割する．
これらの部分集合を $\{ \pi_j^{(0)} \}_{j = 1}^{s}$ とし，
これより求められた概念ベクトルの初期集合を 
$\{ {\bf c}_j^{(0)} \}_{j = 1}^{s}$ とする．
また，$t$ を繰り返しの回数とし，初期値は $t = 0$ である．

\item 各文書ベクトル ${\bf x}_i (1 \leq i \leq N$) に対し，
余弦が最も大きい，最も文書ベクトルに近い概念ベクトルを見つける．
このとき，すべての概念ベクトルは正規化されているので，余弦は
文書ベクトル ${\bf x}_i$ と 概念ベクトル ${\bf c}_j^{(t)}$ の内積を
求めることと同値である．
これにより，前回の繰り返しで求めた概念ベクトル 
$\{ {\bf c}_j^{(t)} \}_{j = 1}^{s}$ から，
文書ベクトルが新たな部分集合 $\{ \pi_j^{(t+1)} \}_{j = 1}^{s}$ に分割される．
\begin{equation}
\pi_j^{(t+1)} = \{ {\bf x}_i: 
{\bf x}_i^T {\bf c}_j^{(t)} \geq {\bf x}_i^T {\bf c}_l^{(t)}\} \ 
(1 \leq l \leq N,\  1 \leq j \leq s)
\end{equation}
ここで，$\pi_j^{(t+1)}$ は概念ベクトル ${\bf c}_j^{(t)}$ に近いすべての
文書ベクトルの集合とする．

\item 新たに導かれた概念ベクトルの長さを正規化する．
\begin{equation}
{\bf c}_j^{(t+1)} = \frac{{\bf m}_j^{(t+1)}}{|| {\bf m}_j^{(t+1)} ||}, 
\ \ \ (1 \leq j \leq s)
\end{equation}
ここで，${\bf m}_j^{(t+1)}$ はクラスタ $\pi_j^{(t+1)}$ の文書ベクトルの
重心を表す．

\item 目的関数 $D^{(t+1)}$ の値を求め．前回の繰り返しにおける目的関数の
値 $D^{(t)}$ との差を計算する．
このとき，
\begin{equation}
\| D^{(t)} - D^{(t+1)} \| \leq 1
\end{equation}
を満たす場合，$\pi_j^{\star} = \pi_j^{(t+1)}$，
${\bf c}_j^{\star} = {\bf c}_j^{(t+1)}$ ($1 \leq j \leq s$) とし，
アルゴリズムを終了する．
停止基準を超えていない場合は，$t$ に1を加え，ステップ2に戻る．
ここで，停止基準における目的関数の差は，文書数が約4000で，
クラスタの数が8よりも大きい場合，収束した時の目的関数は1000を超えることが
これまでの研究で報告されている\cite{Dhillon}．
このため，繰り返しでの1以下の差は無視できるとし，便宜的に1という値を設定した．
\end{enumerate}


\section{実験}
本節では，ランダム・プロジェクションを用いた検索モデルを構築し，
その評価として，MEDLINEを用いた検索実験について述べる．

\subsection{データ}
実験で用いたデータは，情報検索システムの評価用テストコレクションである 
MEDLINEを利用した．
MEDLINEは医学・生物学分野における英文の文献情報データベースで，
検索の対象となる文書の件数は1033件で，約1Mbyteの容量を持つ
テキストデータである．
また，MEDLINEには30個の評価用検索要求文と各要求文に対する正解文書が
用意されている．

MEDLINEに含まれている1033件の文書全体から，
前処理として，``a''や``about''などの一般的な439個の英単語を
不要語リストに指定して，文書の内容と
関係のほとんどない単語は削除した．
この後，接辞処理を行い，残った英単語を語幹に変換する処理を行った．
この前処理の結果，文書全体に5526個あった単語から，
4329個の単語が索引語として抽出され，実験データとして用いた．

\subsection{検索実験方法}
実験では，MEDLINEから前処理により得られた索引語を要素とする文書ベクトルと
検索要求ベクトルを作成し，比較することで検索スコアを計算する．
文書ベクトルを作成するとき，ベクトルの要素には局所的，大域的な
索引語の分布を考慮するために，索引語の頻度に重み付けした数値が用いられる．
数多く提案されている重みづけ手法で，今回の実験では以下の式で定義された
対数エントロピー重み\cite{chisholm}を用いた．
$L_{ij}$ は $j$ 番目の文書に対する $i$ 番目の索引語への重み，
$G_i$ は文書全体に対する $i$ 番目の索引語への重みを表す．
\begin{equation}
L_{ij} = 
\left\{
\begin{array}{l}
1 + \log f_{ij} \ \ ( f_{ij} > 0 ) \\
0 \ \ \ \ \ \ \ \ \ \ \ \ \ ( f_{ij} = 0 )
\end{array}
\right.
\end{equation}
\begin{equation}
G_i = 1 + \sum_{j = 1}^{n} \frac{\frac{f_{ij}}{F_i} \log 
\frac{f_{ij}}{F_i}}{\log n}
\end{equation}
ここで，$n$ は全文書数，$f_{ij}$ は $j$ 番目の文書に出現する $i$ 番目の
索引語の頻度，$F_i$ は文書集合全体における $i$ 番目の索引語の頻度を表す．
これより，$j$ 番目の文書から得られる文書ベクトルの $i$ 番目の要素 $d_{ij}$ は，
\begin{equation}
d_{ij} = L_{ij} \times G_i
\end{equation}
となる．

得られた文書ベクトルから，球面 $k$ 平均アルゴリズムを用い，
これらの文書ベクトルより指定された数の概念ベクトルを作成する．
作成した概念ベクトルを結合した行列に対し，ランダム・プロジェクションを行い，
文書ベクトル，検索要求ベクトルの次元を削減する．
次元の削減されたベクトルを用いて，内積の計算を行い，
その値を各文書に対する検索スコアとする．
これらのスコアのうち，上位50文書を検索結果として出力する．

検索システムの評価には，一般的に用いられている正解率 (Precision) と
再現率 (Recall) を用いた\cite{lewis2}\cite{Witten}．
\begin{equation}
\mbox{Recall} = \frac{システムが出力した正解文書数}{全正解文書数}
\end{equation}
\begin{equation}
\mbox{Precision} = \frac{システムが出力した正解文書数}
{システムが出力した文書数}
\end{equation}
再現率と正解率は，それぞれ個別に用いて，システム評価を行うことができるが，
本実験では，一般にランクづけ検索システムの評価に用いられる
再現率・正解率曲線を用い，システムの評価を行った．
この曲線は，各質問に対しひとつの曲線が作成されるが，
本稿の検索システム評価には，全30個の質問に対する各再現率での平均を計算した
再現率・正解率曲線を用いた．

\vspace*{0.3cm}

\section{実験結果および考察}
\subsection{次元数による比較}
本実験では，ランダム・プロジェクションにより，
ベクトルの次元を100から900まで圧縮した検索モデルについて，
検索実験を行った．
その結果，各次元における平均正解率は表\ref{pre_sys}のようになった．
平均正解率は，ベクトルの次元が大きくなるにつれて増加し，
次元数300において，次元圧縮を行わないベクトル空間モデルよりも
良い結果となった．
また，次元数が400から500に変化させたときの平均正解率の増加が最も大きく，
それ以降は変化の割合が少なくなっている．
次元数を大きくすれば，検索に必要な計算量が増加する．
このことから，効果的な検索を行うためには，
全文書数の約半分に次元圧縮を行う必要があることが分かった．
\begin{table} \caption{各次元数における平均正解率} \ecaption{Average precision at each number of dimensions}
\label{pre_sys}
\renewcommand{\arraystretch}{}
\centering
\begin{tabular}{c|c|c} \hline \hline
次元数 & ランダム・プロジェクション & 平均正解率 \\ \hline
100 & あり & 0.3982 \\
200 & あり & 0.4711 \\
300 & あり & 0.5154 \\
400 & あり & 0.5231 \\
500 & あり & 0.5673 \\
600 & あり & 0.5748 \\
700 & あり & 0.5822 \\
800 & あり & 0.5979 \\
900 & あり & 0.6037 \\ \hline
1033 & なし & 0.4936 \\ \hline
\end{tabular}
\end{table}

\subsection{検索モデル作成時間}
検索モデルを作成する時間，および，一つの検索要求に対し，
検索を行うために必要な時間を測定した結果を述べる．
検索実験には，Ultra Sparc(330MHz) のマシンを使用し，
ベクトルの次元を500とした結果，表\ref{time}に示すように，
ランダム・プロジェクションを用いた場合，モデルを作成する時間は
約11分必要であった．
LSIの場合，SVDの計算についてはSVDPACKの中で最も高速なLanczos法を利用し，
同様にベクトルの次元を500とした結果，モデルを作成する時間は
約24分で必要であった．
この結果，ランダム・プロジェクションはLSIに比べ，
高速に検索モデルを構築することができた．

このモデル作成時間においては，メモリサイズの大きさによる，
SVDの計算時間に与える影響が考えられる．
スワップ領域を用いるほどの大規模なデータについては大きな影響を及ぼし，
モデル作成の時間を多く必要とするが，本実験において用いたマシンには
640Mバイトのメモリを搭載しているため，MEDLINEコレクションのような規模の
データに対しては，メモリサイズの影響はほとんどないと考えられる．

本実験で用いたMEDLINEには収録されているデータは1033件と比較的少ない．
このため，文書数を変化させたときの検索モデル構築時間の変化について
比較を行った．
文書数を増加させるために，MEDLINEと同様なテストコレクションである
CISIを併せた2493記事，さらにCRANFIELDを併せた3893記事について，
それぞれの検索モデル作成時間を測定した．
その結果，ランダム・プロジェクションとLSIのモデル作成時間は
表\ref{model_time}のようになった．
これより，文書数が増加に対して球面 $k$ 平均アルゴリズムの1回の反復による
計算量が大きくなるのであるが，ランダム・プロジェクションが検索時間に
関しても有効であることが分かる．
しかし，非常に大規模な文書数に対しては，より1回の反復による計算量が
増加するため，反復計算を必要とせずに，球面 $k$ 平均アルゴリズム並の
概念ベクトルを得ることが課題となった．
\begin{table} \caption{モデル作成時間とひとつの検索要求に対する検索時間} \ecaption{Processing time for making a retrieval model and retrieving one query}
\renewcommand{\arraystretch}{}
\label{time}
\centering
\begin{tabular}{c|c|c} \hline \hline
手法 & モデル作成時間 & 検索時間 \\ \hline
ランダム・プロジェクション & 約2分 & 4秒\\
LSI & 約24分 & 4秒\\ \hline
\end{tabular}
\end{table}
\begin{table} \caption{文書数の変化によるモデル作成時間} \ecaption{Processing time for making a retrieval model and retrieving one query}
\renewcommand{\arraystretch}{}
\label{model_time}
\centering
\begin{tabular}{l|c|c} \hline \hline
データ                 & ランダム・プロジェクション & LSI \\ \hline
MEDLINE                & 約2分                      & 約24分 \\
MEDLINE+CISI           & 約14分                     & 約26分 \\
MEDLINE+CISI+CRANFIELD & 約34分                     & 約43分 \\ \hline
\end{tabular}
\end{table}

\subsection{他の検索モデルとの比較}
ランダム・プロジェクションを用いた検索モデルに対して，
モデルとしての有効性について評価をする．
この評価をするために，次元圧縮をしていない元のベクトル空間モデルと
特異値分解を用いたLSIによる検索モデルについての検索実験も同時に行い，
性能を比較した．このとき，比較として用いたLSIは，
次元数100として次元圧縮した検索モデルを用いている．
これらの検索モデルについて，同様に検索実験を行い，
すべての検索質問の平均を求めた再現率・正解率曲線を図\ref{re_pre}に示す．
図\ref{re_pre}において，横軸は再現率を表し，縦軸は正解率を表す．
またグラフの`LSI100'は次元数100のLSI，`VSM'は次元圧縮なしのベクトル空間モデル，
`RP500'，`RP700'，`RP900'はランダム・プロジェクションによる
それぞれに示された次元数に圧縮したモデルの実験結果である．

その結果，ベクトル空間モデルと比較して，ランダム・プロジェクションを
用いた検索モデルは，大幅に性能が改善されていることが分かった．
また，次元数100のLSIと比較すると，ランダム・プロジェクションは
LSIに比べ少し下がってはいるものの，ほぼ同じ程度に検索精度が
改善されていることを示している．
このことから，ランダム・プロジェクションが検索モデルとして，
LSIと同等の性能を持っていることが分かる．
\begin{figure}[tb]
	\begin{center}
                 \atari(100,82)
		
	\end{center}
	\caption{モデルに対する再現率・正解率曲線}
	\ecaption{Recall-Precision curve for comparison between models}
	\label{re_pre}
\end{figure}

\subsection{概念ベクトルの有効性}
ランダム・プロジェクションで次元圧縮に用いられる
概念ベクトルが有効であるかを評価するために，
他のベクトルを用いて次元圧縮が行われた場合との検索結果の比較を行った．
ベクトルには，乱数を用いて，全要素の平均が0，分散が1の正規分布 $N(0, 1)$ 
となるベクトルと，指定された数の文書ベクトルを任意に
抽出して得られた部分集合からなるベクトルを，それぞれ次元圧縮に用いた．
この結果，再現率・正解率曲線は図\ref{concept}となった．
ここで，`Random'は正規分布となるベクトル，`Subset'は文書ベクトルの
部分集合を表し，共にベクトルの次元数は500として，次元圧縮を行ったモデルの
実験結果である．
また，サンプルに使った文書集合の偏りを考慮するため，
グラフに示した実験でのベクトルの他にいくらかのサンプルを用意し，
同様の実験を行い，平均的な検索精度を求めた．
その結果，正規分布による任意のベクトルにおける平均正解率の平均値は0.38，
文書ベクトルの部分集合における平均値は0.47となった．

このグラフと平均値から，正規分布の性質を持つ任意のベクトルや
文書ベクトルの部分集合を
用いて次元圧縮を行った結果とそれぞれ比較すると，概念ベクトルを用いて
次元圧縮を行った結果が，明らかに優れていることが分かる．
乱数により生成したベクトルを用いた場合，
これらのベクトルの各要素には，索引の重要度や索引語間の関連性は
ほとんど存在しない．
このようなベクトルにより次元圧縮を行う場合，ベクトルの要素には
文書の内容を表すような潜在的な意味がほとんど含まれていないために，
検索性能が下がってしまったと考えられる．

文書ベクトルの部分集合を用いた場合は，次元圧縮後，
ベクトル中のいくつかの要素が似通った意味を持っているために，
検索性能が下がったと考えられる．
概念ベクトルは，内容の似通った文書がクラスタリングによりひとつにまとめられ，
それらの重心を求めることで，文書の内容を端的に表すことができる．
また，クラスタリングを行うことで似通った内容を持つ概念ベクトルが
少なくなるため，内容がほとんど変わらない概念ベクトルを重複して生成する
可能性が少ない．
しかし，文書の部分集合では，内容の重複した文書が複数存在する可能性がある．
このため，次元圧縮後のベクトル空間モデルに意味の重なった要素が存在し，
検索性能が下がってしまう可能性が大きくなってしまうと考えられる．
これらのことにより，情報検索に対してランダム・プロジェクションを用いて
次元圧縮を行う場合，内容の近い文書や同義語などのような索引語の特徴を表した
概念ベクトルを用いることにより，優れた検索性能が得られることが示された．
\begin{figure}[tb]
	\begin{center}
                 \atari(90,75)
		
	\end{center}
	\caption{概念ベクトルに対する再現率・正解率曲線}
	\ecaption{Recall-Precision curve for comparison between vectors}
	\label{concept}
\end{figure}

\section{おわりに}
本論文では，ベクトル空間モデルの次元圧縮手法として，
ランダム・プロジェクションを用いた検索モデルを提案した．
このモデルの有効性を評価するために，MEDLINEを利用した検索実験を行った．
その結果，次元圧縮していない元のベクトル空間モデルと比べ検索精度が
改善されていることが分かった．
また，LSIと比較しても，検索精度の差は少なく，
ランダム・プロジェクションがLSIと同程度の次元圧縮性能を
持っていることが分かった．
LSIとランダム・プロジェクションのモデル作成，検索に必要な時間を比較すると，
LSIは特異値分解を行うこともあり，ランダム・プロジェクションはLSIに比べ
約半分の時間で検索を行うことができた．
また，MEDLINEよりも大規模な文書集合に対しても，ランダム・プロジェクションが
高速に検索モデルが構築することができる．
これらのことから，ランダム・プロジェクションはLSIに比べ，高速，かつ有効な
次元圧縮手法であることが分かった．

また，ランダム・プロジェクションで次元圧縮に必要な行列を得るために，
球面 $k$ 平均アルゴリズムで得られる概念ベクトルの利用を提案し，
その有効性を検索実験にて評価した．
その結果，乱数により生成したベクトルや文書ベクトルの部分集合を用いた場合に
比べ，検索精度が優れていた．
文書間の内容などの特徴を表した概念ベクトルを用いることで，
その概念における索引語の分布を，ベクトルのひとつの要素として
表現することができる．
これより，ランダム・プロジェクションを用いて検索モデルを構築するとき，
概念ベクトルが潜在的な意味を有効にとらえることができることが分かった．

今後の研究課題としては，まず，球面 $k$ 平均アルゴリズムは初期段階での分割に
非常に大きな影響を及ぼす可能性があるため，初期分割に依存しない有効な
概念ベクトルの生成方法を考慮し，より有効な次元圧縮を実現が可能であると
考えられる．
さらに，より有効な次元圧縮を行うために，評価用データの解答やユーザの評価を
フィードバック情報として，概念ベクトルの調節を
行った検索モデル\cite{Vogt}\cite{Tai}を
構築することが挙げられる．




\bibliographystyle{jnlpbbl}
\bibliography{sankou}

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

\biorevised{再受付}

\bioaccepted{採録}

\end{biography}
\end{document}
