DEIM Forum 2017 C8-5

高階ランダムプロジェクションを用いた情報検索横林 亮平†

白井匡人††

三浦 孝夫†† 法政大学 理工学部創生科学科 〒 184–8584 東京都小金井市梶野町 3-7-2†† 島根大学大学院総合理工学研究科 情報システム学領域 〒 690–8504 島根県松江市西川津町 1060
E-mail: †ryohei.yokobayashi.2j@stu.hosei.ac.jp, ††shirai@cis.shimane-u.ac.jp, †††miurat@hosei.ac.jp
あらまし

本研究では，テンソルデータモデルを確立し，データ操作として高階データ構造に対する高速な情報検索手法を提案する．情報検索では，2 階形式 (行列形式) データを仮定することが多いが，OLAP などの実務分野では高階形式 (テンソル) を仮定する．高階データは，一般に探索データ空間が膨大となり，効率よい検索が必要である．これまで、空間の削減と検索精度の維持を目的として潜在意味索引付けやランダムプロジェクション技術が提案されている．これらは行列形式データの次元数を縮小して高速検索機構を実現し，また縮小後のデータ間誤差を一定以下に保証する．本稿では，高階データ構造にランダムプロジェクションを導入し，効率よい検索機構が実現できることをいう．同時に次元縮小後のデータ距離の誤差保証が達成できることを示す．
キーワード

情報検索，ランダムプロジェクション，次元縮小，高階データ構造，誤差保証

1. 前 書 き

差分的に求めることができない．このため，HOSVD では分解時に用いたデータと異なるデータを扱うことができない．一方，近年，インターネット上のテキストを中心に様々な情報を簡HORP は高階データ構造の内容に独立に次元縮小を行うことが単かつ迅速にアクセスできる．しかしデータが膨大であるた

できる．本研究では，高階データ構造に対する高速な検索手法

め，これらを一貫して効率的に探索することは容易ではない．

を提案する．提案手法では，高階データに対して HORP を実故に，多くの有用な情報はほとんど抽出されず直ちに消えてい行することで次元縮小を行う．このとき，次元縮小に伴うデー

く．情報検索では従来ベクトル空間モデル（VSM）を想定してタ間距離の誤差保証を証明する．

きた．データ情報の多くは，単語および文書情報をベクトル形

本研究の貢献は以下の 2 点である．第 1 にテンソルデータモ式で記述したテキスト文から成る．このような枠組みでは情報デルを確立し，これに対する新たなデータ操作を提案している

検索においてカテゴリ，オントロジー，時間的な側面などさま点である．第 2 に，高階データ構造の縮小に対する誤差保証をざまな特性が反映されない．このため，単語の多義性に起因し行っている点である．本研究は，提案手法を用いて情報検索をて，ユーザの意図と異なる文書が検索される可能性がある．例

行うことで，高階データ構造に対して次元縮小後のデータ距離

えば「APPLE」という単語には，果物または会社という異なの誤差が保証され，効率的に情報検索が行えることを示す．

る解釈が存在する．高階データ (テンソル) を用いてカテゴリ情第 2 章では，テンソルデータモデルとモデル操作について述

報を付加すると (APPLE，果物) と (APPLE，会社) を区別でべ，第 3 章で行列の次元縮小について述べる．さらに第 4 章でき，情報表現の幅を広げることが可能である. しかし，テンソ

テンソル次元縮小について，第 5 章では情報検索について言及

ルはデータ量が膨大であり，検索操作の実行が高価となる．こする．第 6 章では実験により提案手法の有効性を示す．第 7 章のため，高階データに対する効率的な検索手法が必要となる．

で結論とする．

文書集合に対して効率的に検索を行う方法として次元縮小がある．一般的に文書集合の単語次元は数万から数十万といった高次元となる．このため，単語次元を縮小することで効率的に

2. データモデル
2. 1 高階データ表現

検索が行える．データ集合の次元数を縮小する手法としてラン

高階（テンソル）データとは，通常階数が 3 以上となるデー

ダムプロジェクション [5] がある．この手法は，データ間の空間

タ構造を指す．また，1 階のテンソルをベクトル，2 階のテン

距離を誤差内に止め，その空間次元を縮小する技法である [3].

ソルを行列と呼ぶ．インデックス数をテンソルの次元数と呼び，

しかし 2 階形式データを対象としているため，高階データ構造

階数 N のテンソル X は以下のようになる．

に適用することができない．高階データ構造に対する次元縮小
手法として高階特異値分解 (HOSVD) [7] と高階ランダムプロ

I1 ×I2 ×...×IN
X = {Xe1 ,..,eN |ej ∈ Ij , j = 1, .., N }⊂=R

ジェクション (HORP) [10] がある．HOSVD は，各モードに対

k 番目のインデックス Ik を k 番目の次元と呼ぶ．また，テンソ

して行列化し特異値分解を行うことで高階データの各次元を縮ルは X ∈ R[I1 × I2 × ... × IN ] とも表現でき，I1 × I2 × ... × IN

小する．HOSVD は，高階データに対して効率的に文書検索が上で一意に決まる．

行えるが，データに依存して特異値ベクトルを求める．特異値テンソルを用いることの利点は，行列データよりも詳細な情ベクトルは，特異値が少量変化するだけで大幅に変化するため，

報表現を行うことができる点とデータ操作が単純にできる点にある．例えば，ある店の商品売上情報をみる場合，行列ではひテンソルは，行列やベクトルの集合であり，ベクトル表現がと月のみのデータあるいは 1 年といったまとまったデータ情報できる．そこで，ベクトルの取り方を形式化したファイバとを表現することになる．しかし，テンソル表現をする場合，年モードについて言及する [6]．ファイバは，テンソルをベクト

間売上を月別に表示することができる．図 1 に行列とテンソルル表現したものである．3 階のテンソルを例に挙げる．このとのデータ例を示す．

き，ベクトルの取り方には 3 種類存在する．3 種の表現を図 3に示す．固定したテンソルに対して，列方向 (column)，行方

図 1 店舗 1,2 の商品売り上げ
図 3 ファイバとモード

2. 2 テンソルデータ操作
テンソルデータ操作 [6] には，テンソル射影，テンソル選

向 (row)，奥行き方向 (tube) にファイバをとり，それぞれモー

択，テンソルどうしの加算と減算，さらに乗算操作がある．

ド 1 ファイバ，モード 2 ファイバ，モード 3 ファイバと呼ぶ．

また，行列およびベクトルとの変換，およびこれらとの積テンソルを行列で表現するときは，モード n のファイバを横にを導入する．以下，個々の操作を定義する．射影とは，指定並べることで行列化を行い，これを n-モード行列化と呼ぶ．n-

した条件に従い部分的なテンソルを取り出す．例えば，図 1

モード行列化の例を図 4 に示す．モード n のファイバから構成のテンソルの月別売上データにおいて，電子レンジと洗濯された n-モード行列は，X(n) で表現する．n-モード行列を用機が 12 月以外に売れた店舗情報を取り出す．この操作は，いることで，テンソルは行列で表せる．

X ′ = π(♯1(電子レンジ, 洗濯機)♯2(∗)♯3(12 月)−1 ) (X) で表す．
選択では，更に限定的にデータの一部分を抽出する．例えば，
図 1 のテンソルデータより洗濯機が 70 台以上売れた店を抽出する．データ操作は，X ′′ = σ♯2.洗濯機>70 (X) となる．射影，選択によって得られるデータ例を図 2 に示す．

図 4 n-モード行列化

ここで，行列とテンソルの乗算 (行列テンソル積) 操作につ
図2

いて述べる．階数 N のテンソル X (X ∈ R[I1 × I2 × ... × IN ])()，行列 M M ∈ RJn ×In とし，行列テンソル積を Y とする．

射影と選択操作

次に，テンソルの演算操作について述べる．階数と次元数の等しい 2 つのテンソル X, Y ∈ R[I1 × I2 × ... × IN ] についてそれぞれの要素を xi1 ,i2 ,...,iN , yi1 ,i2 ,...,iN と表す．2 テンソルY(n) = X ×n M ∈ R[I1 × I2 × ... × In−1 × Jn × In+1 × ... × IN ]，jn = 1, .., Jn とおくと，
X ×n M = ((Yi1 ,..,in−1 ,jn ,in+1 ,..,iN ))の和と差は，X + Y ，X − Y と表し，その要素はX + Y = xi1 ,i2 ,...,iN + yi1 ,i2 ,...,iN
X − Y = xi1 ,i2 ,...,iN − yi1 ,i2 ,...,iN

(1)

=
(2)

となる．また，2 つのテンソルの積は⟨X, Y ⟩ = X · Y =

I1 I2
∑
∑
i=1 i=2...

IN∑

Yi1 ,..,in−1 ,jn ,in+1 ,..,iN
In∑

X[i1 , .., in−1 , in , in+1 , .., iN ]M [jn , in ]in =1となる．このとき，Jn <= In であれば次元数は小さくなる．

Y(n) = X ×n M は以下の特性を持つ．
xi1 ,i2 ,...,iN yi1 ,i2 ,...,iN (3)i=N√となる．X のノルム ||X|| は X · X である.

X ×m A ×n B = X ×n B ×m A,
X ×n A ×n B = X ×n (BA)m=
| n

雑さを大幅に削減する．行列データに対してデータ構造を維持したまま射影を行う方法として，潜在意味索引付 (LSI) [8] とランダムプロジェクション (RP) [5] について述べる．

3. 1 次 元 縮 小
LSI は特異値分解 (SVD) を用いて, 元のオリジナルの行列を特異値と特異ベクトルによって近似する手法である．SVD を

図 5 1,2 月店舗売り上げ

用いると，行列 X は以下のように分解される．

X ∈ R[2 × 3 × 2] のテンソル (図 5) に対して行列テンソル積を

X N × d = U ΣV t

行う場合について述べる．行列 M ∈ R
を用いると，

45 35 65 60 30 70[]  85 45 50 70 65 70 
0 1 2 3×

3 2 1 0
 50 50 70 45 40 85 

(4)

3×4

45
[
=

80

85

60

85

ここで，Σ は対角行列であり，特異値の大きな順に対角要素が並ぶ．元行列 X が単語×文書の行列のとき，Σ は記事に対する単語の重み（潜在意味）を表す．小さな特異値要素は行列の近似に対する影響が少ないため削除することで低次元に射影す

95

320

385

445

340

400

525

335

245

365

365

260

435

ることが可能になる．このため，LSI は精度を保ったまま大幅]な次元縮小できる．しかし，特異値・特異ベクトルはデータに依存して決定するため，異なるデータを扱うことができない．
一方 RP では，データ行列 X に対して射影行列 R との積をとなり，次元数が小さくなる．次に，テンソルとベクトルの取ることでデータ構造を保ったまま次元縮小を行う．射影行列

乗算 (ベクトルテンソル積) について言及する．テンソル X ∈R は，乱数を基に構築する大きさ k × N の行列である．文書行

RI1 ×I2 ×...×IN とベクトル V ∈ RIn とすると，ベクトルテンソ

列に対して RP を用いると，以下のように次元縮小が行われる．

ル積は Y(n) = X ×n V ∈ R[I1 ×I2 ×...×In−1 ×In+1 ×...×IN ]

k ×d
XRP
= Rk × N X d × N

であり，RP 行列の要素構成は以下の条件を満たす必要がある．[1] [5]

X ×n V = ((Yi1 ,..,in−1 ,in+1 ,..,iN ))Yi1 ,..,in−1 ,in+1 ,..,iN =In∑

ソル (図 5) に対してベクトルテンソル積を行う場合について述
べる．ベクトル [1 2 3] のとき，ベクトルテンソル積を以下に

45

65

60

30

45

50

70

65

50

70

45

40

80

85

60

85

各要素が平均 0，分散 1 の正規分布に従う．

•

列ベクトルの長さが 1 である．

•

R は直交行列である．

条件を近似的に満たすような RP 要素の生成方法が提案されてとなる．このとき，Y は X に対して階数が 1 つ低くなる．テン35•行列の直交化には大きな計算量を必要とする．そこで，上記のX[i1 , .., in−1 , in , in+1 , .., iN ]V [in ]

in =1

示す．

45

 85


 50

(5)

70









310

1



 
70 
 ×  2  =  325
  360
85  

3
1160
95

210



いる．RP 行列の要素 rij が +1 確率 1/6√ 
rij = 30
確率 2/3 −1 確率 1/6(6)に従うように決定される．RP 行列は，文書データに独立して
410  要素決定が行われる．そのため，文書が変更・追加されても射
380  影行列を変更する必要がない．また，LSI と比較して高速に次535
元縮小を行うことができる．

また，ファイバ長により正規化した乗算を Y = X ×◦n V で表す．

3. 2 データ間距離の誤差保証
RP では，次元縮小後に得られるデータ間の距離の誤差保証

X ×◦n V = ((Yi1 ,..,in−1 ,in+1 ,..,iN ))がなされている [3]．例として，単語 (N) と文書 (d) の行列デー

Yi1 ,..,in−1 ,in+1 ,..,iN =タを挙げる．行列データに対し，RP 行列を用いて単語の次元(縮小を行う．次元縮小前の文書ベクトル u,v のユークリッド距In∑X[i1 , .., in−1 , in , in+1 , .., iN ]V [in ])/L

in =1

v
u In
u ∑
L = t(
X[i1 , .., in−1 , in , in+1 , .., iN ])2 )||V ||in =1

離を ∥ u − v ∥2 で表す．また，次元縮小後の文書ベクトル Ruと Rv のユークリッド距離を，∥ Ru − Rv ∥2 とする．次元縮小
後に得られる単語の次元数が
( 2
3 )−1
ln N
k>
= 4 ϵ − 2/ϵ(7)

かつ N >= k を満たすとき，

3. 行列次元縮小
次元縮小とはデータを低次元に射影し，データの空間量と複2(1 − ϵ) ∥ u − v ∥2 <=∥ R 1 u − R 1 v ∥2<= (1 + ϵ) ∥ u − v ∥(8)

が成り立つ．このとき 0 < ϵ < 1 である．

となる．また，下限は,2∥ R2 u′ − R2 v ′ ∥2 >
= (1 − ϵ) ∥ R1 u − R1 v ∥4. テンソル次元縮小22>= (1 − ϵ) ∥ u − v ∥本章では，テンソルデータにおける空間量を削減する方法について述べる．ここでは行列の次元縮小技術をテンソルに拡張である．従って，RP 行列を用いて次元縮小を N 回実行した

し，次元縮小したテンソルのデータ間距離の誤差保証を行う．

とき，

4. 1 テンソル次元縮小操作
次元縮小はデータを低次元に射影する方法である．よって，テンソルデータモデルにおいて，行列とテンソルの乗算 (行列テンソル積) 操作は次元縮小の意味をもつ．テンソルに対してデータ構造を維持したまま次元縮小を行う方法としては HOSVD [7]2N2(1 − ϵ)N ∥ u − v ∥2 <=∥ RN a − RN b ∥ <= (1 + ϵ) ∥ u − v ∥と表すことができる．

5. テンソル情報検索がある．HOSVD は，LSI 同様の分解をテンソルデータに対し

ここではテンソルにおける情報検索を形式化し，次元縮小をて行う分解手法であり，n モード行列化を用いて各モードに対用いた高速な情報検索手法を提案する．また，次元縮小による

し SVD を行う．このため，LSI と同様にデータ内容に依存す

類似度の誤差保証を行う．

ることが問題となる．

5. 1 テンソル情報検索操作

4. 2 高階ランダムプロジェクション

テンソルに対する情報検索は，モード n ファイバまたは n-

データ内容に独立したテンソル次元縮小方法に高階ランダム

モード行列化を用いて，検索質問との類似度を求めることによ

プロジェクション (HORP) がある．従来のランダムプロジェク

り行う．検索質問は，索引語の集合からなり，類似度は一般的

ションは，1 つのモードに対してのみ次元縮小を行う．HORPに内積や余弦類似度を用いる．したがって，テンソルとベクト

では，n 階テンソルの各モード行列に対して RP 行列をかける

ルの乗算操作 (ベクトルテンソル積) は類似度操作の意味を持ため，全てのモードを低次元に射影できる．HORP によるモー

つ．また，ファイバ長で正規化するとベクトルテンソル積は余ドの次元縮小順序は独立である．つまり，モードとそのモード

弦類似度となる．要素が類似度となるため，要素の高い部分のにかける RP 行列が決定していれば，どのモードから次元縮小

属性データをランキングし表示することがテンソル情報検索としても最終的に得られる値は一意に定まる．また，次元縮小操なる．テンソルにおける情報検索操作の例を図 6 に示す．

作が単純で高速に処理を行うことが可能である．
単語 (N)，文書 (d)，カテゴリ (c) で構成された 3 階テンソ
ルでは，以下の式で次元縮小される．k ≪ N, l ≪ d, m ≪ c とすると，

Xklm = X ×N R1 ×d R2 ×c R3(9)
図 6 テンソル情報検索となる．このとき，R1 × R2 × R3 の表現方法により次元縮小
手法は変化する．

5. 2 HORP を用いたテンソル情報検索

次に，次元縮小されたテンソルを復元する操作について提案

HORP を用いた情報検索を提案する．行列データでは，次元する．HOSVD や HORP では，(9) の R1, R2, R3 が正規直交縮小したデータを用いて情報検索を行うことで，検索精度を保行列を仮定しているため，以下の式が成り立つ．

ちつつ高速に検索が行えることが知られている [11]. したがっ

t

R R=I

て，テンソルデータに対して HORP を用いることで次元縮小(I は単位行列)

よって，次元縮小したテンソルに対して Rt との積をとること
で次元復元が可能となる．

X

N ×d×c(10)

HORP を用いて次元縮小を行う際，RP 同様データ間の距離に誤差が生じる．HORP では，RP 行列による次元縮小を複数回実行するため誤差が大きくなる．RP により次元縮小した文書ベクトルを u′ = R1 u，v ′ = R1 v としたとき，u′ ，v ′ に対してさらに RP を実行する．よって，データ間距離の誤差の上限は′対して次元縮小を行いデータの次元数を大幅に圧縮する．検索を行う際は，検索に必要なモードのみを復元操作を行う. そう≈ R1t × X k×d×c

4. 3 HORP によるデータ間距離の誤差′を行い高速な情報検索を行う．まず，HORP で全てのモードに2∥ R2 u − R2 v ∥ <= (1 + ϵ) ∥ R1 u − R1 v ∥2<= (1 + ϵ) ∥ u − v ∥22することで，保持しておくべき記憶量を減少させると共に高速な検索が行える．例えば文書検索では，全軸次元縮小されたテンソルから文書軸のみ復元する．このとき検索質問とテンソルの次元数が異なるため乗算ができない．よって検索を行う際は，検索質問にあらかじめ RP 行列による射影を行うことで，類似度の計算を行う．

RP 行列が厳密な直交行列であれば Rt R = I となるが，近似的に RP 行列の要素決定を行うことで誤差が生じる．RP 行列の直交性に関する誤差を ϵ とすると Rt R = (1 ± ϵ) I と表せる．
次元縮小前の類似度が，⟨u, v⟩ = ut v のとき，次元縮小後の類
似度は,

( )
⟨Ru, Rv⟩ = (Ru)t Rv = ut Rt Rv = ut ((1 ± ϵ) I)v = ut v ± ϵ ut v

表1

カテゴリの記事数べつ平均索引語数
記事数

カテゴリ

平均索引語数となる．よって次元縮小後の類似度は，次元縮小前の類似度に

2-100 件

81 件

36.9

対して,

101-200 件

18 件

36.16

201-300 件

8件

35.11

301-400 件

4件

37.26

401-500 件

2件

37.58

501-600 件

1件

36.41

601-700 件

1件

37.06

701-800 件

0件

0

実験では，NTCIR-3 を用いて文書検索に関する実験を行い，801-900 件

1件

26

次元縮小を用いた情報検索手法の有効性を示す．テンソルには，

901-943 件

2件

31.22

⟨Ru, Rv⟩=1±ϵ⟨u, v⟩(11)の誤差に収まる．

6. 実

験

階数 3 のテンソル (単語，文書，カテゴリ) を用いる．それぞれの軸を HORP を用いて次元縮小した後，RP 行列の転置を用

使用頻度の高いカテゴリには 943 件の記事が含まれる．また，

いて操作に必要な軸を復元する．テンソルでは，軸 (階) 数が複同時に出現し易いカテゴリを表 2 に示す．

数あるため，どの軸に対して検索を行うのか検索の仕方が複数存在する．本実験では，簡単のため文書軸に対して検索を行う
文書検索に限定して実験を行う．

RP 行列の要素は平均 0, 分散 1 の正規分布に従い，正規直表2

重複し易いカテゴリ

同時に出現するカテゴリ

出現頻度

と

C07

85 件

A61
C08

と

C09

48 件

交行列になることが理想的である．しかし，近似的に RP 行列

B01

と

C07

32 件

を構成するため次元縮小の際に差が生じる．よって，実データ

G01

と

H01

28 件

を用いて多項分布で構成した RP 行列による次元縮小操作およ

B29

と

B32

24 件

び復元操作を行い，データ間距離誤差保証と検索精度の保証を

G02

と

G09

24 件

行う．

B60

と

B62

23 件

B21

と

B23

22 件

B01

と

C02

21 件

C21

と

C22

21 件

第 1 の実験では，次元縮小したテンソルと元のテンソルデー
タそれぞれの文書間のユークリッド距離を比較し，誤差を測定する．単語，文書，カテゴリを次元縮小した後，文書軸を復元する．3 回の次元縮小によりデータ間距離の誤差許容範囲は(1 ± ϵ)3 である．
第 2 の実験では，HORP を用いた情報検索の検索精度の実験を行う．HORP を用いて次元縮小を行っても，精度を保った
まま元のテンソル同様に情報検索が行えることを示す．

6. 1 実 験 準 備
実験に用いる NTCIR-3 は，特許検索タスクで用いた特許デー
タコレクションである．公開特許公報全文データの kkh,JAPIO
出願抄録データの jsh, 日本国英語特許出願抄録データの paj がある．kkh と jsh は日本語で構成されており，paj は英語で構成されている．
本実験では，paj の中の 1995 年に収録された 317441 文書からランダムに抜粋した 5000 記事を使用する．5000 記事の内，妙録部分を索引語として不要語の消去及び単語のステミングを行う．さらに，本実験では出現頻度 40 以上の語だけを抽出す
る．最終的に得られた索引語は 1562 語となる．提案手法は，高階データを対象とするため，索引語・文書のほかに 3 つ目の階としてカテゴリを用いる．カテゴリは，各記事に記載される国際分類カテゴリに従い各文書が属するカテゴリを決定する．各
記事には一つ以上のカテゴリが存在し，複数のカテゴリに属することを許す．実験に用いる 5000 記事中には，118 のカテゴ
リが存在する．含まれる記事数別にカテゴリを分け，平均索引
語数をとると以下のようになる．
最も使用頻度の低いカテゴリには 2 つの記事が含まれ，最も以上により得られた，索引語 (単語)，文書，カテゴリを基にテンソルデータを構築する．各文書が属するカテゴリに単語の出現頻度を挿入し，それ以外の部分の要素は全て 0 とする．本
実験におけるテンソルは，0 以外の要素が 257551 存在する．また，1 記事 1 カテゴリにおける最大索引語数は 67 語，最小索
引語数は 4 語である．

6. 2 評 価 方 法
第 1 の実験では，誤差保証した範囲内に何％の確率で収まるかで評価を行う．第 1 の実験におけるユークリッド距離の誤差
許容範囲は，(1 ± ϵ)3 である．本実験データにおいて，(7) の条件を満たす ϵ は，0.521 < ϵ < 1 である．従って ϵ を 0.6 から

0.1 ずつ増やし，各々のときの最小テンソルでデータ間距離を測定して元テンソルと比較する．
第 2 の実験では，次元縮小前のテンソルに対して検索質問を行う．その結果，類似度 0.7 以上となった文書を選びこれを適
合文書 (正解) とする．同様に，次元縮小したテンソルに対しても検索質問を行う．類似度が 0.7 以上となる文書を選び適合文書と比較することで次元縮小による検索精度の影響を測ることができる．検索質問は 5000 記事からランダムに選んだ 300 記
事を使用する．次元縮小したときのテンソルに対しては，RP
行列を用いて次元縮小した検索質問を用いる．この検索質問は，単語に関してのみ次元縮小を行う．検索精度の評価には 11 点
平均適合率を適用する．

適合率 =

検索した内の適合文書の数
検索でヒットした文書

HORP を用いた検索精度では，次元数を 65.82%圧縮しても78.5%の精度で情報検索が行える．次元数が大いほど検索精度

は，検索結果に含まれる正解の割合を示す．
再現率 =は高くなる傾向にある．次元縮小したテンソルによる検索では,
検索結果中に正解とならないものが存在する．これをノイズ検索した内の適合文書の数
適合文書(偽陽性) と呼ぶ．このノイズの内繰り返しノイズとして現れては，正解をどのくらい網羅しているかを表す．情報検索では，いる文書があり，その文書が検索精度を低下させている．例え

適合率と再現率が共に 1 となるのが理想である．しかし，現実

ば，単語とカテゴリの次元数を 100 × 60 に次元縮小したときには適合率を上げようと再現率は下がり，再現率を上げようとノイズは 113 件存在する．その中で繰り返しノイズとして出現すれば適合率が低下する．

する 8 文書あり，これを表 5 に示す．

6. 3 実 験 結 果

表 5 ノイズ文書と出現回数

第 1 の実験結果を表 3 に示す．
表3
ε

平均

標準偏差

0.6 1.353

1.038

0.7 1.355

1.042

文書番号 ノイズとしての出現回数

212

30

170

16

min max295

140.064 4.096

187,462 件 (1.50)

231

12

95,105 件 (0.76)

293

8
6
5

データ間距離の誤差
許容範囲

0.027 4.913

誤差範囲外 (%)

0.8 1.355

1.044

0.008 5.832

46,990 件 (0.38)

174

0.9 1.355

1.048

0.001 6.859

24,245 件 (0.19)

253
240

5

8 文書

96

第 1 の実験では，3 回の次元縮小と 1 回の次元復元により，次元縮小されたデータ間距離の誤差範囲は (1 ± ϵ)3 である．デー
タ間距離数は 12,497,500 件存在する．各々の ϵ における次元
縮小可能な最も小さなテンソルは ϵ = 0.6 で 137 × 158 × 89,

ϵ = 0.7 で 112 × 131 × 74，ϵ = 0.8 で 99 × 115 × 64, ϵ = 0.9
で 91 × 105 × 59 となる．データ間距離の平均誤差は，ϵ =0.6
において 1.353，ϵ =0.7 から 0.9 において 1.355 となる．
第 2 の実験における次元圧縮率と 11 点平均適合率の関係を
表 4 に示す．

この 8 文書は全ノイズ中の 85%(113 件中 96 件) に影響している．この 8 件の文書の特徴は，使われている索引語が高出現頻度語となっていることである．例として，文書 174 を図 7に示す．文書 174 では，索引語が 4 単語 (obtain, mold, base,couple) のみしか使われていない．このうち obtain，mold，baseは高出現頻度順位 30 以内の単語である．高出現頻度の単語は，その他の多くの文書で使用される単語である．文書中に高出現
頻度語以外の索引語が少ない場合，類似度を計算すると高出現
頻度部分のみ乗算が行われ類似度が高くなる傾向にある．よっ表 4 圧縮率と検索精度(単語×カテゴリ) 次元数 次元縮小率 11 点適合率
1562 × 118

100%

1100 × 110

34.35%

0.78

900 × 100

51.17%

0.787

700 × 90

65.82%

0.785

500 × 8078.30%

0.525

300 × 70

88.30%

0.44

100 × 60

96.20%

0.052て，ノイズとして繰り返し出現し，適合率の低下原因となる．

1

単語とカテゴリの次元数が 900 × 100 のとき，最大 11 点平

図7

7. 結

ノイズ文書の例

論

均適合率 78.7 となる．また，このときの縮小率は元のテンソ
ルの 48.83%(圧縮率 51.17%) のテンソルとなる．さらに，元の高階 (テンソル) データモデルを提案した．また，データ操テンソルの 34.18%(圧縮率 65.82%) のテンソルにおいても 11

作の一つとして高階ランダムプロジェクション (HORP) を用

点平均適合率は 78%を上回る．

いた情報検索手法の提案を行った．次元縮小したテンソルを用

6. 4 考察いて，次元縮小前と同様のデータ操作が可能であることを示し

第 1 の実験では，データ間距離の誤差範囲を超過するものがた．ただし，次元縮小前後のデータには誤差が存在する．よっϵ = 0.6 のとき 1.503%，ϵ = 0.7 のとき 0.761%,ϵ = 0.8 のときて，HORP による次元縮小したときの誤差保証を行った．次元

0.376%,ϵ = 0.9 のとき 0.194% 存在する．この原因は，RP 行

縮小を N 回行ったときのデータ間距離は (1 ± ϵ)N となる．実列要素を近似的に構成していることにある．本来，RP 行列はデータを用いて 3 回の次元縮小と 1 回の次元復元を行ったとき正規分布を仮定しているが，多項分布を用いているため誤差範のデータ間距離は，(1 ± ϵ)3 である．近似的に要素決定を行っ

囲を超越した．

た HORP を用いても，誤差保証範囲内におよそ 99%収まる．

テンソルの類似度操作は，次元縮小前後で誤差が 1 ± ϵ 内に収まることを保証した．HORP を用いた情報検索では，元テンソ
ルの 34.18%(圧縮率 65.82%) のテンソルで検索精度は 78.5%となる．故に，精度を維持したまま高速な情報検索を行うことが可能となった．
文

献[1] Bingham, Ella, and Heikki Mannila. ”Random projection
in dimensionality reduction: applications to image and text
data.” Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining.
ACM, 2001.
[2] Bogdanova, Iva, Francisco Rincn, and David Atienza. ”Amulti-lead ECG classification based on random projection
features.” 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2012.
[3] Dasgupta, Sanjoy, and Anupam Gupta. ”An elementary
proof of a theorem of Johnson and Lindenstrauss.” Random
Structures and Algorithms 22.1 (2003): 60-65.
[4] De Lathauwer, Lieven, Bart De Moor, and Joos Vandewalle.
”A multilinear singular value decomposition.” SIAM journal on Matrix Analysis and Applications 21.4 (2000): 12531278.
[5] Kaski, Samuel. ”Dimensionality reduction by random mapping: Fast similarity computation for clustering.” Neural Networks Proceedings, 1998. IEEE World Congress on
Computational Intelligence. The 1998 IEEE International
Joint Conference on. Vol. 1. IEEE, 1998.
[6] Kolda, Tamara G., and Brett W. Bader. ”Tensor decompositions and applications.” SIAM review 51.3 (2009): 455500.
[7] De Lathauwer, Lieven, Bart De Moor, and Joos Vandewalle.
”A multilinear singular value decomposition.” SIAM journal on Matrix Analysis and Applications 21.4 (2000): 12531278.
[8] Papadimitriou, Christos H., et al. ”Latent semantic indexing: A probabilistic analysis.” Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on
Principles of database systems. ACM, 1998.
[9] Sun, Jimeng, Dacheng Tao, and Christos Faloutsos. ”Beyond streams and graphs: dynamic tensor analysis.” Proceedings of the 12th ACM SIGKDD international conferenceon Knowledge discovery and data mining. ACM, 2006.
[10] Sanguansat, P., ”Higher-Order Random Projection for Tensor Object Recognition.”, Intn’l Symp. on Communications
and Information Technologies (ISCIT). IEEE, 2010.
[11] 大内 浩二, 三浦 孝夫, 塩谷 勇, “頻度分布に基づくプロジェ
クションを用いた文書検索,” DEWS, 1C-i8, 2005.