DEIM Forum 2014 D9-1

MOARLE: 高速・省メモリな行列圧縮計算フレームワーク
小山田昌史†

成田

和世†

劉

健全†

荒木

拓也†

† 日本電気株式会社 グリーンプラットフォーム研究所 〒 211-8666 神奈川県川崎市中原区下沼部 1753
E-mail: †m-oyamada@cq.jp.nec.com, ††{k-narita,j-liu}@ct.jp.nec.com, †††t-araki@dc.jp.nec.com
あら ま し行列計算は，データマイニング処理，機械学習処理，情報検索処理をはじめとするさまざまなデータ処理の中心をなす．行列計算の対象となる行列のサイズは，計算資源の発展やビッグデータの普及に伴い巨大となっている．巨大な行列はコンピュータの記憶領域を逼迫し，またその計算に長大な時間を要する．そのため，巨大な行列の記憶容量と計算時間を削減することは肝要な課題である．この課題に対し，本稿は行列の記憶容量削減，計算高速化，計算省メモリ化を同時に実現する行列の圧縮計算フレームワーク MOARLE を提案する．MOARLE は，事前に行列を連長圧縮して行列の記憶容量を削減した上で，その後何度もおこなわれる計算を連長圧縮情報の利用により高速か
つ省メモリにおこなう．疎行列表現とは異なり，MOARLE は密行列に対しても効果的である．実データを用いた実験により MOARLE は内積計算やユークリッド距離計算などのコア演算処理におけるメモリ使用量を最大で 98%削減
し，また処理速度を最大で 124 倍高速化することが分かった．
キ ーワ ード

1. 背

行列計算，ベクトル計算，機械学習，情報検索，圧縮，組み合わせ最適化
は事前に計算対象となる行列を連長圧縮して行列の記憶容量を景削減したうえで，その後の計算を連長圧縮により得られた情報

行列計算は，データマイニング処理，機械学習処理，情報検の利用により高速かつ省メモリにおこなう．圧縮処理に必要な索処理をはじめとするさまざまなデータ分析処理の中心をな

初期コストは，何度も計算がおこなわれることで償却される．

す．行列計算の対象となる行列のサイズは，計算資源の発展や

MOARLE は行列の圧縮部と計算部からなる．圧縮部に対しビッグデータの普及に伴い巨大となっている．巨大な行列はコて，我々は圧縮形式として基本的な連長圧縮 (run-length encod-

ンピュータの記憶領域を逼迫し，またその計算に長大な時間をing) を用いる．そして，データ分析処理においては行ないし列要する．そのため，巨大な行列の記憶容量と計算時間を削減すの順序が多くの場合演算結果に影響をおよぼさないことに着目ることは肝要な課題である．

し，行ないし列を並び替えることで，連長圧縮の効果を向上さ

本稿はデータ分析処理の持つ二つの特徴に着目し，巨大な行せる方式を提案する．また，行列内の要素を少数の代表値で置

列の記憶容量と計算時間を削減するという課題に取り組む．一

換すことにより精度を犠牲にしつつ圧縮率をさらに向上させる

つ目の特徴は，データ分析処理においては同じ行列に対して何

代表値置換処理も提案する．圧縮情報を利用した計算部分では，度も繰り返し計算がおこなわれるというものである．例えば，

連長圧縮処理によりベクトル内で同一の値が連続するという事

機械学習処理におけるハイパーパラメータの調節処理 [4] や，前知識が得られることに着目し，その知識を利用して計算回数

パターン認識や情報検索の分野におけるクエリベクトルとデーを減らす方式を提案する．

タベース内のベクトル群とのマッチング処理がこれにあたる．

本研究の貢献は以下のとおりである:

二つ目の特徴は，データ分析処理においては多くの場合に行列（ 1 ） 行列の行ないし列方向に並ぶ要素を連長圧縮してそのの行や列の順序を入れ替えても演算結果が変化しないというも情報を計算時に活用することで行列の記憶容量の削減，計算ののである．例えば機械学習処理は行をサンプルデータ，列を特高速化，計算の省メモリ化を同時に達成する行列の圧縮計算フ

徴量次元とする計画行列を対象に目的関数の最適化をおこな

レームワーク MOARLE を提案する．

うが，この際よく用いられる確率的勾配法 [5, 8] や Coordinate（ 2 ） 行列に対する演算の種類によっては行ないし列の順序

Descent 法 [9] では，行や列の順序を入れ替えても最終的に得が演算結果に影響をおよぼさないことに着目し，行ないし列のられる結果は変化しない [8]．また，前述したクエリベクトル

並びかえをおこない連長圧縮の効果を最大化させる問題を組みとデータベース内のベクトル群とのマッチング処理ではユーク

合わせ最適化問題として定式化する．

リッド距離やコサイン類似度による近傍探索をおこなうが，こ（ 3 ） 連長圧縮の効果を最大化させる問題について，最適解の際にデータベース内のベクトル群の順序やベクトル次元の順を求めるアルゴリズムが多項式時間では動作しないことをあき

序を入れ替えても，探索結果は変化しない．

らかにしたうえで，行列の辞書ソートにもとづいて近似解を求

我々は，これら二つのデータ分析処理の特徴をうまく利用して行列の記憶容量削減，計算高速化，計算高速化を同時に実現
モ

アレ

めるアルゴリズムを提案する．
（ 4 ） 行列内の要素を少数の代表値で置き換える方式を提案

する計算処理フレームワークMOARLE (Matrix Operation Ac-

し，演算精度を犠牲にしつつ連長圧縮の効果をさらに高めるこ

celerator based on Run-Length Encoding) を提案する．MOARLEとを可能とする．

本稿の構成は以下のとおりである．はじめに，2. 節で，行列単のため，以降の例では単純な連長圧縮を用いて説明するが，に連長圧縮を適用することによる行列計算の省メモリ化・高速提案方式は PackBits を利用した場合にも適用可能である．単純化について述べる．次に，3. 節で，行列の行ないし列を並び替

な連長圧縮と PackBits を用いた場合の提案方式の性能差についえることにより連長圧縮の効果を高める方式について述べる．

ては，5. 節で議論する．

そして 4. 節で，行列内の要素を少数の代表値で置換することに

つぎに，行列に対する連長圧縮について説明する．MOARLE

より連長圧縮の効果をさらに高める方式について述べる．そのは行列の行ないし列に対して連長圧縮を適用したうえで，圧縮

後 5. 節で提案方式の有効性を実データを用いた実験により確か情報を利用して計算を高速化する．ここで，行列の行（列）にめ，6. 節で関連研究について紹介したあと，7. 節でまとめる．

対する連長圧縮とは，行列の各行（列）をそれぞれ独立の数列，

2. 行列の圧縮計算

すなわちベクトルとみなしたうえで連長圧縮を適用することを意味する．例えば

本節では，MOARLE における計算部のコア技術である，行


 1

 2


 2

 2

2

列に連長圧縮を適用することによる計算の省メモリ化と高速化について述べる．

2. 1 行列の連長圧縮
はじめに，データ圧縮の基礎的な技術である連長圧縮 (run-length encoding, RLE) について説明する．連長圧縮はデータ列
を可逆圧縮する技術である．連長圧縮は，データ列を (データ

1

2

2

2

1

2

3

3

3

3

3

2

3

1

2


2 

2 

3 

2 

2という行列に対して，行を連長圧縮するとが連続する個数, データ) というペアの列として表現する．その(2, 1) (3, 2)

ため，同一のデータが頻繁に連続して登場するようなデータ列
を，元のデータ列よりもコンパクトに表現することができる．

(2, 2) (1, 1) (2, 2)

例えば(1, 2) (4, 3)
1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1

(1, 2) (2, 3) (2, 2)という 17 個の数値からなるデータ列を連長圧縮すると，(5, 1), (9, 2), (3, 1)(1)(1, 2) (1, 3) (1, 1) (2, 2)となり，列を連長圧縮するとという 6 個の数値からなるデータ列になり（注 1），データサイズ(1, 1) (1, 1)(1, 2)(2, 2)(2, 2)が削減される．なお，連長圧縮の問題として，同一データがあ(4, 2) (1, 2)(1, 1)(1, 3)(1, 3)

まり連続しないデータ列に対して連長圧縮を適用した場合に圧(3, 3)(1, 3)(2, 2)(2, 2)

縮後のデータサイズが元のデータサイズよりも大きくなりう
るというものがある．この問題は，連長圧縮のシステム実装に

PackBits [2] と呼ばれる技術や γ 符号・δ 符号などの符号化技術 [12] をつかうことにより，緩和可能である．
簡単に PackBits について説明する．PackBits は，連長圧縮において同一の要素が連続しない場合に，同一の要素が連続しない回数を負の値で表現したうえで，連続しない要素をその後に並べる．これにより，異なる要素が並んだ場合にサイズが肥大することを防ぐ．例えば

1, 2, 3, 4, 1, 1, 1, 1

(1, 1)となる．行列に対して連長圧縮を適用することで，巨大な行列をコンパクトに表現することができる．

2. 2 連長圧縮を 利用し た計算の高速化
先に述べた行列の連長圧縮は，行列のデータサイズを削減するためだけでなく，行列に対する計算の高速化に利用することができる．連長圧縮はデータ列を (データが連続する個数, データ) というペアの列として表現するものであることを思い返す．
これはすなわち，連長圧縮されたデータには「ある値が何度連続して登場するか」という事前知識が含まれていることを意味する．以下で，この事前知識を利用して計算を高速化する方式という 8 個の数値からなるデータ列を単純に連長圧縮すると，(1, 1), (1, 2), (1, 3), (1, 4), (4, 1)という 10 個の数値列となって圧縮前と比べデータサイズが増えてしまうが，PackBits をつかうとについて例を用いて説明する．なお，本節で説明する方式は圧縮されたデータの伸張を必要としない，すなわちデータを圧縮したまま計算することが可能な方式であるため，計算の高速化と同時に計算の省メモリ化も同時に実現する．

2. 2. 1 二乗和計算の高速化
はじめに，単純な例として行列の列に関する二乗和計算の高(−4, 1, 2, 3, 4), (4, 1)

速化について説明する．行列の列に関する二乗和計算は，凸最という 7 個の数値列となり，圧縮効果が得られる．本稿では簡適化問題の解法としてよく用いられる Coordinate Descent 法 [9]などのさまざまな処理で利用されるため，その高速化は重要で（注 1）：なお，括弧は読みやすさのために付与しているものである．

ある．

v
t n
X

例として，式 1 の行列の一列目に対する二乗和計算について考える．単純な二乗和計算は12 + 22 + 22 + 22 + 22

(2)

(9)

で定義される．このとき式 9 は

v
t n
X

となり，5 回の積算と 4 回の加算処理を要する．これに対し，圧縮計算ではまず行列を列方向に圧縮し，一列目として(1, 1), (4, 2)(ai − bi )2i(ai − bi )2 =

i

(3)

v
t n
X

a2i +

i

n
X

b2i − 2

i

n
X

ai bi

(10)

i

と展開でき，展開後の各項は二乗和と内積計算となるため，前述した圧縮計算が適用できる．そのため，圧縮計算によりユーを得る．そして，1 が 1 回，2 が 4 回，連続するという知識をクリッド距離計算が高速化できる．圧縮計算が可能な演算にはつかい，この列に対する二乗和計算を

他にコサイン類似度などがあるが，本稿ではこれ以上の例示は

12 + 4 · 22

(4)としておこなう．元の二乗和計算（式 2）が 5 回の積算と 4 回しない．

3. 行列の並び替え によ る 圧縮率の向上の加算処理を要したのに対し，圧縮二乗和計算（式 4）は 3 回

前節で，MOARLE における計算部のコア技術として，行列の積算と 1 回の加算処理でおこなえ，積算と加算の回数が少な

を連長圧縮してデータサイズを減らす方式と，圧縮情報を用いくなっている．そのため，計算が高速におこなえる．

て計算を高速化する方式について説明した．本節では，行列の2. 2. 2 内積計算の高速化行ないし列を並び替えることで行列の連長圧縮率が向上するこ

つぎに，行列の行に対する内積計算の高速化について説明すとを示し，最良の並びを求める問題が多項式時間で解けないこる．内積計算はユークリッド距離やコサイン類似度の計算をはとをあきらかにしたうえで，MOARLE における圧縮部のコアじめとする機械学習・情報検索分野での計算に頻出するため，技術として，効率的に近似解を得る並び替え方式を提案する．

3. 1 行列の並び替え と 圧縮計算

その高速化は重要である．
例として，式 1 の行列の一行目と二行目の内積を計算するこ

本小節では，行列の内容と計算の種類によっては行列の行ないし列を並び替えることで行列全体の連長圧縮率を向上させたとを考える．単純な内積計算はうえで演算が可能であることを述べる．

1·2+1·2+2·1+2·2+2·2(5)となり，5 回の積算と 4 回の加算処理を要する．これに対し，行列を行方向に連長圧縮すると，一行目と二行目はそれぞれ(2, 1), (3, 2)(6)と(2, 2), (1, 1), (2, 2)(7)のようになる．ここで，二乗和計算と同様に値の連続性の知識

まず，つぎの行列 X ∈ R6×3 を考える．


 2

 1

 5
X = 
 4

 3

1

1
0
1
0
2
2

行列 X を列方向に連長圧縮すると


2 

1 

1 

2 

1 

1(11)を用いると，内積の圧縮計算は

1 × (2 × 2) + 2 × (1 × 1 + 2 × 2)

(8)となる．このとき元の内積計算（式 5）が 5 回の積算と 4 回の加算処理を要したのに対し，圧縮内積計算（式 8）は 2 回の積算と 4 回の加算処理でおこなえ，積算の回数が少なくなっている．そのため，計算が高速におこなえる．

(1, 2)(1, 1)(1, 2)(1, 1)(1, 0)(2, 1)(1, 5)(1, 1)(1, 2)(1, 4)(1, 0)(2, 1)(1, 3)(2, 2)(1, 1)

2. 3 ユーク リ ッ ド 距離計算の高速化のように計 15 個のペアによって行列全体を表現することとな

以上で説明した二乗和計算と内積計算の高速化により，多くる．このとき，行列 X に対して行列の基本変形である行の交換の計算処理が高速化できる．ここでは，その例としてユーク処理をおこない行の並びを変化させると，行列の列方向の連長

リッド距離計算の高速化について説明する．ユークリッド距離

圧縮率を高めることができる．行列 X の行を並び替えて列方向

計算は近傍探索処理やクラスタリング処理など多くのデータの圧縮率を最良とした行列を X ∗ と表記すると，行列 X ∗ は処理で支配的な計算となり，ユークリッド距離計算の高速化によって，多くのデータ処理が高速化される．
ベクトル a = (a1 , ..., an ) と b = (b1 , ..., bn ) のユークリッド距
離は


 2

 5


 3
X ∗ = 
 1

 1


4

1
1
2
2
0
0


2 

1 

1 

1 

1 

2となる．行列 X ∗ を列方向に連長圧縮すると3. 3 全 探 索 法
はじめに，問題 1 の最適解を探索する全探索法について説明する．全探索法は，行列 X の行を並び替えて得られる全ての行
列のパターンを走査し，そのなかから最適な行列を選ぶ．並び替えで得られる行列のパターンは m! 通りあり，それぞれの行列に対してペア数を確認するので，この方式の計算量は O(m! n)となる．全探索法を用いると最適な圧縮率を示す並び替えパ
ターンを必ず得ることができるが，計算量が多項式時間ではな(1, 2)(2, 1)(1, 2)

いため，巨大な行列に対しては適用ができず，実用的ではない．

(1, 5)(2, 2)(4, 1)

本節の残りでは，最適解を算出可能だが計算時間が多項式時(1, 3)(2, 0)(1, 2)

間でない全探索法に代わり，多項式時間で実行可能解を算出す(2, 1)

る方式である貪欲法とスコア付き辞書ソート法の二つを紹介(1, 4)

する．

のように計 11 個のペアによって行列全体を表現でき，行列 X

3. 4 貪 欲 法と比べ連長圧縮率が向上している．

多項式時間で実行可能解を算出する方式である貪欲法につい

ここで，行列に対する演算によっては行列の行ないし列の順て説明する．貪欲法は，貪欲的アプローチで行の並び替えをお序を入れ替えても結果に影響しない，という性質に注目する．

こない，行列の圧縮率を高める．並び替えは，ある開始行を選

本稿では，行の順序が入れ替わっても結果が変化しない演算を択して先頭に並べたうえで，選択された行とハミング距離が最行順序不問演算 (row-order insensitive operation)，同様に列に対も小さな行をつぎに並べる，という処理を繰り返すことでおこして列順序不問演算 (column-order insensitive operation)，そしなわれる．完全な処理の流れをアルゴリズム 1 に示す．なお，て行と列どちらの順序を入れ替えても結果に影響しない演算をアルゴリズム中，行列の A の i 行目を行列 B の j 行目で置き換

行列順序不問演算 (row-column-order insensitive operation) と呼えることを ai∗ ← b j∗ と，m 行 n 列の零行列を Om,n と，それぞぶ．例えば 2. 2 節で例としてあげた行ベクトルないし列ベクト

れ表記する．また，簡単のため arg min は集合でなく要素を返

ルに対する二乗和計算と内積計算は，行列順序不問演算になる．

す，すなわち対象となる関数が最小値をただ一点でとるものとこれらの処理は，パターン認識や情報検索の分野におけるクエ

する．

リベクトルとデータベース行列内ベクトルのマッチング処理な貪欲法の計算量について議論する．貪欲法では，開始行

どに頻出する．また，データベース分野におけるリレーショナの 選 び 方 は m 通 り あ り，開 始 行 そ れ ぞ れ に つ い て ハ ミ ン

ルモデルではレコードをあらわす行に順序関係はなく，リレー

グ距離が最小となる行を貪欲的に選んでいくパターンはショナルデータを対象とする関係演算は行順序不問演算となる．

(m − 1) + (m − 2) + ... + 1 = m(m − 1)/2 通りある．また，各さらに，機械学習の分野では教師データとしてサンプルを行，

ハミング距離の計算には n 回の比較が必要である．そのため，

特徴量次元を列とする計画行列 (design matrix) を用いるが，計貪欲法の計算量は O(m3 n) となる．これは多項式時間であるが，画行列を学習対象するアルゴリズムの多く [8, 9] は，サンプル

行数 m に対して m3 のオーダーとなっており，巨大な行列へのの順序や特徴量次元の順序を入れ替えても最終的に同じ結果へ適用は難しい．

収束し [8]，行列順序不問演算となる．

3. 5 ス コ ア 付き 辞書ソ ート 法
貪欲法の計算量は行数 m に対して m3 のオーダーとなり，巨3. 2 問 題 定 義
MOARLE は，行列に対しておこなわれうる演算が判明して大な行列を並び替えることが困難である．これに対し，我々はおり，その演算が行列順序不問演算であった場合，行列の行な

m log m のオーダーで行を並び替えることのできるス コ ア 付き

いし列の順序を入れ替えて連長圧縮率を高めたうえで，圧縮計

辞書ソ ート 法を提案する．はじめに，スコア付き辞書ソート法

算する．そのため，いかにして行列の行ないし列の順序を入れの基礎となる行列の行の辞書ソ ート (lexicographical sort) につ替えて連長圧縮を高めるかが，課題となる．本節の残りでは簡いて説明する．行列の行の辞書ソートとは，行列の行を文字列

単のため議論を行列の行の並び替えに限定したうえで，つぎのに見立てて行の大小関係を辞書式順序 (lexicographical order) に問題に取り組む．

より定義したうえで，汎用のソートアルゴリズムにより並び替

問題 1 (圧縮率を 高める 並び替え 探索) m 行 n 列 の 行 列 X ∈えることである．すなわち行列 X に対し，まず一列目の要素に→ N を行列を列方向に連長ついてソートし，その次に二列目についてソートし，という作

圧縮した際のペア数を算出する関数，X を行列 X に行の交換作

業を繰り返す．例えば 3. 1 節の式 11 であげた行列 X の行を辞

業を繰り返して得られる全ての行列からなる集合としたとき，

書ソートすると，

R

m×nが与えられ，Pair# : R

m×n

minimize:

Pair# (X ′ )subject to:

X ′ ∈ X, Pair# (X ′ ) <= Pair# (X)となるような行列 X ′ を得る．

Algorithm 1: 貪欲法

Algorithm 2: スコア付き辞書ソート法の行比較関数

Input: X ∈ Rm×n , 並び替え対象の行列

Input: X ∈ Rm×n , 行列; p ∈ { 1, ..., m }, 比較対象行番号 1;

Output: 並び替えられた行列
1
2q ∈ { 1, ..., m }, 比較対象行番号 2;

Data: P, 行プール; Xcand , 候補解集合; X ′ , 並び替え済行列

Output: 行列 X における p 番目の行と q 番目の行の大小関係

foreach i ∈ { 1, ..., m } do

Data: Q, 優先度付きキューX′ ← O/* 全ての列についてスコアを計算

m,n/* 行列 X 内の i 番目の行を開始行として選択し，それ以外の行をプール P に追加
3P ← { 1, ..., m } \ { i }4x′1∗ ← xi∗

5

for k ← 2 to m do

*/

2

*/

j ← arg min HammingDistance(X, k − 1, j)

4k ← Dequeue(Q)5

if x pk > xqk then7

P ← P \ { j}78x′k∗ ← x j∗

8

Xcand ← Xcand ∪ { X ′ }9*/while Q is not empty doreturn 1 /* 行列 X の p 番目の行 > q 番目の行

6

j∈P

10

Enqueue(Q, k, ComputeScore(X, k)) /* 行列 X の k 番目の列に/* スコアの高い列から順に要素を比較

3

プール P から取り出し，並び替え済行列に追加

9*/foreach k ∈ { 1, ..., n } do
対しスコアを算出し，スコアを優先度としキューに追加 *//* 開始行 i に対してハミング距離が最も小さい行 j を
6

1

*/

else if x pk < xqk thenreturn -1 /* 行列 X の p 番目の行 < q 番目の行
return 0 /* 行列 X の p 番目の行 = q 番目の行*/*/

return arg min Pair# (X ′ )X ′ ∈Xcand

表 1 圧縮率を向上させる並び替え方式の比較

となる．


 1

 1


 2
Xlex = 
 3

 4


5

0
2
1
2
0
1


1 

1 

2 

1 

2 

1(12)

並び替え方式

計算量

並び替え結果全探索法

O(m! n)最適解

貪欲法

O(m3 n)

実行可能解

スコア付き辞書ソート法（提案方式） O(n m log m) 実行可能解

スコア付き辞書ソートの計算量について議論する．汎用のソートアルゴリズムは m 個のレコードを O(m log m) でソートできることが知られている [7]．汎用のソートにおける一度の比行列の行に対する辞書ソートは列番号の若い列を優先的に較で，スコア付き辞書ソートの比較関数（アルゴリズム 2）はソートするが，これは場合によって連長圧縮率の向上に効果的n 回の比較をおこなう．また，濃度をスコアとして利用するスでない．例えば式 11 の行列 X を辞書ソートすると一列目が優コア計算には O(nm) を要する．そのため，スコア付き辞書ソー

先的にソートされて式 12 の行列 Xlex となるが，この結果の連トの計算量は O(n m log m) となる．これは行列の行数 m に対し長圧縮率は低く，三列目を優先してソートした方が連長圧縮率て m log m のオーダーであり，巨大な行列にも十分適用可能では高くなる．そこで，本稿では辞書ソートを一般化したス コ ア

ある．

付き 辞書ソ ート (scored lexicographical sort) を提案する．スコ3. 6 並び替え 方式の特性

ア付き辞書ソートは，行列の各列についてスコアを計算したう

表 3 に，本稿で議論した三つの並び替え方式の特性をまとめえで，そのスコアの高い順に行をソートする．効果的なスコア

る．提案するスコア付き辞書ソート法は，三つの並び替え方式

定義としては，列内の要素を集合としてみなしたときの濃度のなかで最も計算量が小さく，巨大な行列に対しても十分適用(cardinality) を用いたものがある．濃度は列内に登場する値のが可能である．スコア付き辞書ソート法による圧縮率の向上効

種類数をあらわすため，この値が小さな列を優先してソートす

果は，5. 節で実データを用いた実験により確認する．

ると，同じ値が列方向に連続して並ぶ確率が高くなる．その結果，全体として列方向の連長圧縮率が高くなることが期待される．以降，本稿では特に指定しない限りスコア付き辞書ソートのスコアとして濃度の逆数を用いる．

4. 代表値置換によ る 不可逆圧縮
前節で，行列の行ないし列を並び替えることで行列の連長圧縮率を向上させる方式について述べた．本節では，行列内の要

アルゴリズム 2 に，行のスコア付き辞書ソートにおける行の素を少数の代表値で置換することによりさらに連長圧縮率を向比較関数の処理を示す．アルゴリズム中 xi j は行列 X の (i, j) 成

上させ，データサイズの減少と高速化の効果を高める方式につ分をあらわす．この比較関数を汎用のソートアルゴリズム内でいて議論する．

つかうことで，行列の行をスコア付き辞書ソートすることがで

本稿でこれまでに議論してきた行列の連長圧縮方式は，行列きる．なお，アルゴリズム 2 では比較関数内でスコア計算をお内に同じ値があまり登場しない場合，圧縮率が低い．例えば実こなっているが，この処理は事前に一度おこなえばよいため，

数値を含む下記の行列 X は，同じ値を全く含まないため，連長比較関数の外に出してもよい．

圧縮による圧縮効果は得られない．


 62.5  63.0 




X =  64.5 
 72.5 


64.7

を高めるほど，代表値置換後の行列に対する演算結果と代表値
置換前の元行列に対する演算結果の間に生じる演算の誤差は大(13)きくなる．このトレードオフ関係に対しては，代表値置換方式と演算の種類によっては，パラメータの値から代表値置換により生じうる演算誤差の上限値と下限値を見積もる，ないしその逆をおこなうことが可能である．これによって，許容する誤差

この問題に対し，MOARLE は行列内の似た値をグループにまの上限値を与えたうえで行列の圧縮率を最大にし，省メモリ化・

とめ，同一グループに属す値をグループの代表値により置き換高速化の効果を最大限に高めたうえで計算をおこなうことがでえる代表値置換処理 (representative replacement) をおこなう．代きる．なお，演算誤差の見積もりの実装と評価は今後の課題と表値置換処理は一種の不可逆圧縮であり，計算の精度を下げる

する．

一方で，さらなる圧縮効果を得る．本節の残りでは MOARLEの備える具体的な代表値置換方式二つについて説明する．

4. 1 離散化によ る 代表値置換

5. 評 価 実 験
本節では提案する行列圧縮計算フレームワーク MOARLE の

ま ず，離 散 化 に よ る 代 表 値 置 換 方 式 に つ い て 説 明 す る ．
この方式は，行列の各列について，格納されている値の値

有効性を確かめるため，実データを用いた評価実験をおこなう．

5. 1 実 験 環 境

域 を あ る 基 準 点 β と あ る 幅 δ で 区 切 る ．す な わ ち 値 域 をシ ステム : 実験に用いた計算機は，プロセッサが Intel Core i5[β, β + δ), [β + δ, β + 2δ), [β + 2δ, β + 3δ), ... という区間に分割

680 (4 コア，3.60GHz)，メモリが 16GB，OS が Linux 3.8.0 でする．各区間が一つのグループとなる．そして，列内の値がそある．MOARLE の実装は C++言語でおこない，コンパイラとれぞれどの区間に属すかを算出し，同じ区間に属す値を区間のしては GNU g++ 4.7.3 を用いた．

代表値により置き換える．代表値の例としては区間内の要素にデータ セッ ト : 実験では，行列の圧縮計算対象として疎行列ついての平均値がある．例えば式 13 の行列 X の一列目に対しと密行列の両方を用いた．疎行列としては [3] で公開されていて β = 0, δ = 5 で離散化と平均値による代表値置換をおこなう

る Bag of Words 形式の文書行列を用いた．密行列としては [11]ことを考える．このとき 62.5, 63.0, 64.5, 64.7 は区間 [60, 65) に，で公開されている行列を用いた．各行列の情報を表 2 に記載

72.5 は区間 [70, 75) に入り，それぞれの区間に対する平均値はする．

(62.5 + 63.0 + 64.5 + 64.7)/4 = 63.675 と 72.5 となる．そのため，
表 2 実験に用いたデータセット

行列 X の第一列目を代表値置換した行列は

 63.675  63.675 b =  63.675 
X




 72.5 

63.675Sparse(14)となり，連長圧縮の置換前と比べ効果が高くなる．また，代表
b に行の並び替えをおこなうことでさらに連長値置換後の行列 X
圧縮率を高めることができる．

Dense

nips

kos

enron

madelonarcene

行数12,419

6,906

列数

1,500

3,430

非零要素数

746,316 353,160 3,710,420 999,999

gisette28,102500

10,0005,000

39,861

2,000

100

6,000

540,941 3,891,362

5. 2 行列データ サイ ズの圧縮率
まず，MOARLE 圧縮部の行列データサイズの削減効果を評価する．実験では，2. 1 節で述べた行列の行に関する連長圧縮

4. 2 ク ラ ス タ リ ン グ によ る 代表値置換

を各データセット行列について適用し，圧縮前と比べた圧縮後つぎに，クラスタリングによる代表値置換方式について説明の行列のデータサイズの比率（単位: %），すなわち圧縮率を比する．この方式は，行列の各列について，格納されている値を較した．連長圧縮方式には単純な連長圧縮（RLE）と改良方式

クラスタリングする．各クラスタがグループとなる．そして，である PackBits の二つを用いた．また，それぞれの方式につい各クラスタの値を，クラスタの代表値により置き換える．例えて，データセットをそのまま圧縮した場合と，3. 5 節で提案しば k-means 法 [13] をクラスタリングに用いる場合，各列の値がたスコア付き辞書ソート法でデータセット行列の列を並び替えあらかじめ設定されたパラメータ k の値に応じ，k 個の代表値

たあとに圧縮した場合との計測をおこなった．

へと置換される．クラスタリングによる代表値置換の利点には，

表 3 に，各データセットに対して連長圧縮を適用した際の値の値域を考慮する必要がないというものがある．これに対し，

データ圧縮率を示す．表中，RLE は単純な連長圧縮の利用，Sort

4. 1 節で述べた離散化による代表値置換方式では，列ごとに値は事前の行列並び替えを，それぞれあらわす．表 3 を見ると，域を考慮して適切にパラメータ β, δ の値を設定する必要がある．

以下のようなことが確認できる．

4. 3 代表値置換によ る 圧縮率の向上と 演算誤差
本稿で述べた二つの代表値置換方式では，パラメータの値を変化させることで，行列の圧縮効果を左右することができる．
このとき一般に，代表値置換のパラメータを変化させて圧縮率•

連長圧縮は疎行列に対し て 大き な効果を 発揮す る ． 疎行

列である enron に対して並び替えをおこない， PackBits により連長圧縮をした場合に，最高の圧縮率 1.21% を得ている．

•

密行列に対し て 連長圧縮を おこ なう と ， 行列のデータ サ表 3 疎行列・密行列に対するデータ圧縮率（単位: MB）

Sparse90.36

madelon4273.12

3.81

arcenegisette

71.06

RLE

3.81

114.44

10.54 (14.84%) 5.19 (5.74%) 54.95 (1.28%) 7.53 (197.42%) 5.96 (156.45%) 55.16 (48.20%)
9.96 (14.02%)

4.89 (5.41%) 53.46 (1.25%) 7.46 (195.67%) 5.12 (134.48%) 46.82 (40.91%)

PackBits

10.0 (14.07%)

5.07 (5.62%) 53.69 (1.25%) 3.86 (101.40%) 3.84 (100.90%) 49.92 (43.62%)

Sort+PackBits

9.12 (12.84%)

4.75 (5.26%) 51.71 (1.21%) 3.88 (101.79%) 3.20 (83.97%)

10

1

kos

enron madelon arcene gisette

100

RLE
Sort+RLE
Packbits
Sort+Packbits

10

1

0.1

nips

kos

enron madelon arcene gisette

Datasets(a) 二乗和計算の高速化比率

Runtime speedup (Original = 1.0)

Sort+RLE

RLE
Sort+RLE
Packbits
Sort+Packbits

nips

enron

Original

100

0.1

kos

Runtime speedup (Original = 1.0)

Runtime speedup (Original = 1.0)

nips

Dense

39.03 (34.10%)

100

RLE
Sort+RLE
Packbits
Sort+Packbits

10

1

0.1

nips

kos

enron madelon arcene gisette

Datasets(b) 内積計算の高速化比率

Datasets(c) ユークリッド距離計算の高速化比率

図 1 計算の高速化比率（速度向上比率は対数）

イ ズが増え て し ま う こ と がある ． 密行列である madelon に単純もみられる．しかし，RLE と比べ PackBits ではデータ圧縮率

な連長圧縮をした場合，圧縮率は最悪の 197.42% となり，元行

こそ上がっているものの，高速化比率が下がってしまっている．

列と比べデータサイズが倍近くに膨れ上がってしまう．この問

これは，PackBits における圧縮データ列のスキャン時に長さが題は，PackBits の適用により緩和される（圧縮率が 101.40% と正か負か確認し条件分岐をおこなう処理があり，その処理がなる）．

オーバーヘッドとなったためと推測される．密行列に対しては，

PackBits は密行列に対し て 大き な効果を 発揮する ． made-単純な RLE を用いた場合に圧縮計算をおこなわない場合より

lon，arcene，gisette の三つで，RLE における圧縮率と比較し，も速度が遅くなりうることが確認できる．この問題は PackBits

PackBits の利用によりそれぞれ 96%，55%，4.58% データサイと Sort の利用により解決され，最終的に各密行列で 1.5 倍からズが減少している．

3.7 倍の高速化を達成している．

•

並び替え は密行列に 対し て 特に 効果を 発揮す る ． gisette

図 1(b) は内積計算の高速化をあらわす．疎行列に対してはに PackBits を適用した場合，並び替えにより 9.5% データサイ

3.5 倍から 124 倍の高速化を達成しており，二乗和計算と同様

ズが減少している．

にソートによる速度の向上もみられる．また，二乗和計算とは•並び替え と PackBits の組み合わせは広範に 効果的で あ異なり PackBits を利用した場合に RLE と比べ速度向上がみらる ． madelon 以外の全てのデータセットで行列のデータサイズ

れる．これは，内積計算の圧縮計算実装が二乗和計算と比べ複を削減することができている．

雑であり，長さの正負を確認する処理が支配的ではないためと•以上の結果から，スコア付き辞書ソートによる行列の並び替推測される．密行列に対しては，圧縮をおこなわない場合より

えと PackBits の利用により多様な行列に対して行列の圧縮効果

も速度が遅くなってしまっている．これは，現在の圧縮計算実が得られるといえる．

装が複雑で最適化されておらず，実装面でのオーバーヘッドが

5. 3 行列計算の高速化大きいためと推測される．今後，実装を最適化したうえで，比まず，MOARLE による計算高速化の効果を評価する．実験

較を再びおこなうことを予定している．

では，行列内の各行ベクトルに関する二乗和計算，行ベクトル

図 1(c) はユークリッド距離計算の高速化をあらわす．ユーク同士の内積計算，行ベクトル同士のユークリッド距離計算につリッド距離の圧縮計算は二乗和計算と内積計算の組み合わせでいて，計算に要した時間を各圧縮方式について計測した．実あり，二乗和計算と内積計算の間に位置する実験結果となって験結果を図 1 に示す．図 1 は，圧縮をおこなわない通常の計いるため，考察は省略する．

算方式と比較した際の，各圧縮方式（RLE, Sort+RLE, PackBits,

5. 4 圧縮率と 高速化比率の関係

Sort+PackBits）による圧縮計算の計算時間の向上度合いをあら最後に，圧縮率と高速化比率に関する考察をおこなう．5. 2

わす．

節と 5. 3 節で，各圧縮方式のデータ圧縮効果と高速化比率につ

図 1(a) は，二乗和計算の高速化をあらす．疎行列に対してはいて述べた．図 2 は，これら効果の関係をあきらかにするため，10 倍から 120 倍の高速化を達成して，ソートによる速度の向上

各圧縮方式についてデータセットを圧縮した際の圧縮率とその1

Square sum
Dot product
Euclidean distance

0.1
0%

1%

10%

100%

Compressed size (Original = 100%)(a) RLE

100

10

1

Square sum
Dot product
Euclidean distance

0.1
0%

1%

10%

100%

Compressed size (Original = 100%)(b) Sort+RLE

Runtime speedup (Original = 1.0)

10

Runtime speedup (Original = 1.0)

Runtime speedup (Original = 1.0)

Runtime speedup (Original = 1.0)

100

100

10

1

Square sum
Dot product
Euclidean distance

0.1
0%

1%

10%

100%

100

10

1

Square sum
Dot product
Euclidean distance

0.1
0%Compressed size (Original = 100%)

1%

10%

100%

Compressed size (Original = 100%)(c) PackBits(d) Sort+PackBits

図 2 各圧縮方式における圧縮率と高速化比率の関係（両対数グラフ）

際に得られた高速化比率を散布図にしたものである．各サンプ
ル点がデータセットに対応する．図 2 は両対数グラフであり，

7. 結

論

全ての圧縮方式・全ての演算でデータセットの圧縮率と高速化

本稿で我々は，行列の圧縮計算フレームワーク MOARLE を比率の間にはベキ分布の関係が成り立つことをあらわしている．

提案した．MOARLE は事前に行列を連長圧縮したうえで，そすなわち，圧縮後のサイズを線形に減少させると，高速化比率の後何度もおこなわれる計算を連長圧縮情報の利用により高速は指数関数的に向上する．この結果を利用すると，MOARLE

かつ省メモリにおこなう． MOARLE は，行列の圧縮部と圧縮内でデータ圧縮率から高速化効果を見積もり，高速化が期待で情報を利用した計算部からなる．圧縮部に対して，我々は行列にきない場合は通常の演算処理をおこなうことが可能となる．そ対する演算の種類によっては行ないし列の順序が演算結果に影の実装と評価に関しては今後の課題とする．

響をおよぼさないことに着目し，行ないし列の入れ替えをおこ6. 関 連 研 究

なうことで連長圧縮の効果を向上させる方式を提案した．また，行列内の要素を少数の代表値で置換することによってさらに連MOARLE は，疎行列表現・疎ベクトル表現を利用した行列・

長圧縮の効果を向上させる方式も提案した．計算部に関しては，

ベクトル演算ライブラリに関連する．ベクトル演算ライブラリ

連長圧縮処理によりベクトル内で同一の値が連続するという事である Eigen [10] は，疎行列や疎ベクトルをコンパクトに表現前知識が得られることに着目し，その知識を利用して計算回数

し，省メモリかつ高速に処理できる．疎なデータを対象とするを減らす方式を提案した．そして，実験により MOARLE が疎

Eigen に対し，本稿で提案した MOARLE は密なデータに対しなデータに対して処理速度を最大で数十から数百倍高速化し，ても圧縮をおこない，圧縮計算効果を得ることができる．

密なデータに対して数倍高速化することを示した．

Rendle らは，行列内のブロック構造を利用することで機械学
習アルゴリズムを高速化する方式を提案している [14]．彼らの提案方式は関係代数におけるリレーション結合により生成される構造を利用するものであり，想定する構造がない場合には効果が得られない．これに対し MOARLE は行列の構造に対する想定が少なく，より多くの種類の行列に対して効果を得ることができる．
行列の行並び替えによる連長圧縮率の向上に関しては，オー
トマトンの状態遷移表の圧縮方式に類似した試みがある [6]．彼らは，本稿で述べた貪欲法に相当する方式で連長圧縮の向上を試みている．彼らの対象としている行列は状態遷移表であり，行列が巨大ではないため貪欲法が有効である．一方，本稿のようにデータ分析処理を対象とした場合は行列が巨大となり，計算量が O(m3 n) である貪欲法が適用できなくなることもある．MOARLE におけるスコア付き辞書ソート法の計算量はO(n m log m) であり，巨大な行列にも適用可能である．
4. 3 節で述べた代表値置換による行列演算誤差の見積もりに関する試みとしては，BlinkDB [1] がある．BlinkDB は問合せ
処理内でサンプリングをおこない近似結果を算出することで，問合せへの応答時間を短縮する．BlinkDB は問合せへの応答時間と近似による誤差のトレードオフ関係をシステマティックに扱い，ユーザの要求する応答時間から，結果に生じる最大誤差を算出することができる．

文

献[1] S. Agarwal et al. BlinkDB: Queries with Bounded Errors andBounded Response Times on Very Large Data. In EuroSys, pages
29–42, New York, NY, USA, 2013. ACM.
[2] Apple Inc. Apple Technical Note TN1023, 1996.
[3] K. Bache, M. Lichman. UCI Machine Learning Repository, 2013.
[4] J. Bergstra, Y. Bengio. Random Search for Hyper-parameter Optimization. J. Mach. Learn. Res., 13:281–305, February 2012.
[5] L. Bottou. Large-Scale Machine Learning with Stochastic Gradient Descent. In COMPSTAT, pages 177–187, Paris, France, August
2010. Springer.
[6] B. C. Brodie, D. E. Taylor, R. K. Cytron. A Scalable Architecture forHigh-Throughput Regular-Expression Pattern Matching. In ISCA,
pages 191–202. IEEE Computer Society, 2006.
[7] T. H. Cormen et al. Introduction to Algorithms. McGraw-Hill Higher
Education, 2nd edition, 2001.
[8] X. Feng et al. Towards a unified architecture for in-RDBMS analytics. In SIGMOD, pages 325–336. ACM, 2012.
[9] W. J. Fu. Penalized Regressions: The Bridge versus the Lasso. Journal of Computational and Graphical Statistics, 7(3):397–416, 1998.
[10] G. Guennebaud, B. Jacob et al. Eigen v3. http://eigen.tuxfamily.org,
2010.
[11] I. Guyon et al. Result Analysis of the NIPS 2003 Feature Selection
Challenge. In NIPS, 2004.
[12] D. J. C. MacKay. Information Theory, Inference & Learning Algorithms. Cambridge University Press, New York, NY, USA, 2002.
[13] J. Macqueen. Some Methods for Classification and Analysis of Multivariate Observations. In 5-th Berkeley Symposium on Mathematical
Statistics and Probability, pages 281–297, 1967.
[14] S. Rendle. Scaling Factorization Machines to Relational Data.
PVLDB, 6(5):337–348, 2013.