2016年8月9日 河原林ERATO感謝祭III

Scalable Partial Least Squares
Regression on Grammar-Compressed
Data Matrices
田部井靖生(東京工業大学/JST-さきがけ)
西郷浩人 (九州大学)
山西芳裕 (九州大学)
Simon.J.Puglisi (ヘルシンキ大学)

KDD’16のResearch Trackに採択

概要• 解釈可能な統計モデルを大規模データ行列上で効率的に学習させるためのデータ圧縮法を提案• Partial least squares (PLS)回帰モデル学習を文法圧縮されたデータ行列上で実装• 大規模データを用いた実験で性能を検証

線形モデルの学習• データはD次元特徴ベクトルx RDとして表現されていると仮定– 文章中の単語の有る無しを表現した0/1ベクトル(フィンガープリント)– 画像における各ピクセルの値を要素とするベクトルなど• 線形モデル : 重みベクトルw RDとxの内積で応答変数yを求める y=wTx• N個の特徴ベクトルと応答変数のペアー(x1,y1),(x2,y2),…,(xN,yN)が与えられたら, 重みベクトルｗを学習する• D, N 数億からなる大規模かつ超高次元データを仮定

大規模データから解釈可能な統計モデルを学習することは知識発見ための有効な手段• 解釈可能な統計モデル– 線形モデル, 決定木, 決定集合など• 利点 : どの特徴が分類/回帰に有効かなどの解釈が可能• 学習結果を説明する必要性が機械学習の応用場面で良くある– バイオインフォマティクス, ケモインフォマティクス, 多くのビジネスシーン, etc• KDD’16の関連論文 : Lakkaju et al., Haichuan etal., Ribeiro et al.,Nakagawa etal.,

データ行列のメモリに比べて学習アルゴリ
ズムのメモリは圧倒的に小さい• 機械学習の入力 = データ行列Xとラベル列yDXyN

メモリ : O(ND)• 殆どの学習アルゴリズムのメモリ: O(D)• データ行列を圧縮した状態でモデル学習できれば巨大な行列上でも効率よく学習可能

乱択ハッシュを用いた機械学習法 [NIPS’11]• データ行列の各特徴ベクトルを低次元ベクトルにハッシュし、モデルを学習する– 入力ベクトルのサイズ >> ハッシュ後のサイズ– ２つのベクトル間の距離は近似的に保存される• 利点 : 精度を落とさずメモリ効率良く学習可(i)Input vectors(ii)BinaryHashingvectors

Learn(iii)Learn
modelweight w

b1 = (1, 0, 1)
b2 = (0, 0, 1)
b3 = (1, 1, 1)
b4 = (0, 1, 1)
b5 = (1, 0, 0)f(bi)=wbi

様々な乱択ハッシュを利用した機械学習法• 入力ベクトルの形式とシュミレートしたいカーネ
ルに応じて、様々な手法が提案されている• 欠点 : 非可逆圧縮のため学習後のモデルの解釈不可
手法

カーネル

入力形式

b-bit MinHash [Li'11]
Tensor Sketching [Pham'13]
0-bit CWS [Liʼ15]
C-Hash [Mu'12]
Random Feature [Rahimi'07]
RFM [Kar'12]
PWLSGD [Maji'09]

JaccardPolynomial
Min-Max
CosineRBF
Dot productIntersection

Fingerprint
実数ベクトル
実数ベクトル
実数ベクトル
実数ベクトル
実数ベクトル
実数ベクトル解釈可能な統計モデルを学習するためにデータ圧縮に求められる条件• スケーラブル– 巨大なデータ行列を圧縮したい• 高い圧縮率– メモリ効率よく学習するため• 可逆圧縮– 学習結果のモデル解釈するため• 学習アルゴリズムに必要な行列操作をサポート– データ圧縮した行列上で学習アルゴリズムを実装するため

発表内容• 研究の動機– 大規模データ上の機械学習• 文法圧縮– Re-Pairアルゴリズム– Re-Pairアルゴリズムの大規模データへの適応• 文法圧縮されたデータ行列上のPLS回帰モデルの学習
• 実験
• まとめ

文法圧縮 : 入力文字列だけを表現するチョムスキー標準形の文脈自由文法
⼊⼒

⽂法ルール

abcabcX3➝X2X2X2➝X1c
X1➝ab

構⽂⽊ (2分⽊)
X3

X2

X2X1c X1

a ba bc• 反復文字列に対して有効な圧縮法– 同一の部分列を多く含むほど、少ないルール数で表現可能• 文法は２分木としての良い表現を持つ– 圧縮されたデータに対する様々な操作を実装可能

Re-Pair [J.Lassarson and A.Moﬀatʼ99]• 文字列中で最頻出する隣接文字ペアーを新しい非終端記号に置き換える貪欲アルゴリズム
1. 文字列中で最頻出する隣接文字ペアーabを発見する
2. 新しい文法ルールXi➞abを生成し, 文字列中のすべてのabの出現をXiで置き換える
3. すべての文字ペアーの出現頻度が1になるまでstep1とstep2を繰り返す

Re-Pairの動作例
1. S中の最頻出はaa
S=aaaaabcaaaaa
2. 文法ルール X1→aaを生成する

頻度表
aa:8
ab:1
bc:1
ca:1

3. S中のaaのすべての出現をX1で置き換える
S’=X1X1abcX1X1a
Sʼを入力として1, 2, 3を繰り返す。

Re-Pair (続き)• 利点 : シンプルでありながら圧縮率が高い• 欠点 : 線形時間で実装するためには多くのデータ構造が必要 (メモリ大)Ex : 入力文字列の各位置に128bitのポインター,文字ペアーの頻度を管理するヒープやハッシュテーブル etc
省スペース化のための工夫 (その1)• 位置ポインターを省略• 頻出するtop-k個の文字ペアーからルールを作成– Top-kを十分大きく(k=10000)とれば高速Re-Pairの省スペース化の工夫(その2)•

Re-Pairの問題点 : すべての文字ペアーの出現頻度をハッシュテーブルに保持する必要性• Re-Pair
文字列中に頻出する文字ペアー=圧縮に貢献•• ストームマイニング
ストリームデータから頻出するアイテムを選ぶ
例 : Lossy/Frequency
Countings [VLDBʼ02,ESAʼ02]

⽂字列中に頻出するするルールのみを主記憶に残しつつ、⾼圧縮率を達成することが可能– 定数スペース化

データ行列の文法圧縮• 入力のデータ行列はフィンガープリントを仮定• 文法圧縮が有効な理由
1. 同じクラスに属するフィンガープリントは同じ要素を共有する
2. Gap-encodingにより同じ要素を共有しやすくなる(i)データ⾏列(ii)Gap-encoding(iii)⽂法圧縮X1=(1,3,4,7,9,13)
X2=(2,3,7,9,11)
X3=(1,3,4,7,9,11)

X1=(1,2,1,3,2,4)
X2=(2,1,4,2,2)
X3=(1,2,1,3,2,2)

X1=(D,2,4) D={D→C3,
X2=(A,4,B)
B→22,
X3=(D,B)
C→1A,A→21}

Partial Least Squares (PLS) 回帰モデル• データ行列の複数個の低次元空間に射影した上での線形モデル
mf (x) =X↵i wi| xi=1• wi : 低次元空間へ射影するためのベクトル• αi : 各空間ごとの重みベクトル• 利点 : 各空間ごとに予測に効く特徴を観測可PLS回帰モデルの学習アルゴリズム• データ行列 : X, レスポンス: y• 以下のステップを繰り返す- wi: Xを低次元に射影するためのベクトル
1. Xを低次元に射影しtiに保持 (ti=Xwi)
2. tiとyの共分散最大化によりwi+1を学習する• 行列の足し算と掛け算を文法圧縮したデータ行列上で実現できれば学習アルゴリズムは実装可能– データ行列の行アクセスと列アクセス

行アクセス• 復元アルゴリズムと基本的に同じ
1. アクセスしたい行の非終端記号を展開する
例 : X1=(1, 2, 1, 3, 2, 4)
2. 前から累積和を計算する
例 : X1 = (1, 3, 4, 7, 9, 13)
X1=(D,2,4)
X2=(A,4,B)
X3=(D,B)

D={D→C3,B→22,C→1A,A→21}

BDC
1 A
2 1

32 2

列アクセス• 各中間ノードより下の葉のラベルの総和を保持• 各Rowの前から累積和を計算しつつ, 候補となるカラムが有るかチェック• 非終端記号を根とする部分木を辿って, 求めたい値があるかチェックする
X1=(D,2,4)
X2=(A,4,B)
X3=(D,B)

B

DC
1 A
2 1

32

A B C D

23 4 4 7

実験• データセット
Table 2: Summary of datasets.
DatasetBook-review
CompoundWebspamCP-interaction
CP-intensity

Label typebinarybinarybinarybinaryreal

Number
12,886,488
42,682350,000
216,121,626
1,329,100

Dimension
9,253,464
52,099,292
16,609,143
3,621,623
682,475#nonzeros
698,794,696
914,667,811
1,304,697,446
32,831,736,508
28,865,055,991

Memory (mega bytes)
2,665
3,489
4,977
125,243
110,111• cPLS(提案手法),
PCA,theb-bit 300,202
MinHash,SGDを比較
first vector
w1 is obtained by maximizing
compound-protein
pairs are interact
ance between the mapped feature XG w1 andon the STITCH database [19]. We used•
評価尺度として、圧縮サイズ,学習時間, 精度を比較
able y as follows:
datasets for testing binary classification abilit
consists of 1,329,100 compound-protein pa
2(5)1 = argmax cov (XG w, y),as 682,475 dimensional fingerprints, where twabout compound-protein interaction intensit
X!G XG w = 1, where cov(XG w, y) = y ! XG w.
from several chemical databases (e.g., ChEMBan analytically be solved as w1 = X!G y.
PDSP Ki). The intensity was observed by IC
weight vector, the same optimization problem
imal (50%) inhibitory concentration) or EC
additional constraints to keep orthogonality,Compression Size (MB)
4800
5000
5200
5400

Compression Size (MB)Compression Time (sec)

●

●

●

4600

50000

●

60000
70000
80000
Compression Time (sec)

CP-interation上でのtop-kを変化させたときの実行時間と圧縮サイズ

2e+05

4e+05

6e+05

Top−k

8e+05

1e+06

Compoun
Lossy-RePair `(MB)
1
10100
1000
CP-interaction上でのヒープサイズを変化さ
compression size (MB)
1288
859
825
825
15
せたときの圧縮時間、メモリー、圧縮サイズ
compression
time (sec)
5096
7053
7787
7946
13
working space (MB)
1113
1926
5030
5030
2
• 125GBのデータを圧縮するために、約16GBのメモリー
Webspamを使用して実行時間は約12時間
Lossy-RePair `(MB)
10100
1000
• 125GBから約4GBに圧縮 1
compression size (MB)1427
948940940
23compression time (sec)6953
10585 10584 10964 21
working space (MB)
1112
1923
7075
7075
2CP-interact
CP-interaction
Lossy-RePair `(MB)
10100
1000 10000
1compression size (MB)
5199
5139
5036 20compression time (sec) 24hours 55919 44853 43756 24
working space (MB)9914 16650 16635
6CP-intensi
Lossy-RePair `(MB)
10100
1000 10000
1

Lossy-RePair `(MB)
1
10100
1000
CP-intensity上でのヒープサイズを変化させcompression size (MB)
1427
948
940
940
たときの圧縮時間、メモリー、圧縮サイズ
compressiontime (sec)6953
10585 10584 10964
working space (MB)
1112
1923
7075
7075
• 110GBのデータを圧縮するために、約4GBのメモリー
CP-interacを使用して実行時間は約2時間
Lossy-RePair `(MB)• 102GBから約500MBに圧縮
10
1001000 10000
compressionsize (MB)
5199
5139
5036 2• 各データの非ゼロ要素数>>- データのサイズ(水平ビッcompression
time (sec) 24hours 55919 44853 43756 2
グデータ)に強い圧縮法
working space (MB)9914 16650 16635
CP-inten
CP-intencity
Lossy-RePair `(MB)
10
100
1000 10000
compression size (MB)
558
543
540
535
compression time (sec)
8103
6479
6494
6657
working space (MB)
1936
3552
3722
3738

compression time (sec)working space (MB)24hours-55919
9914

44853
16650

43756 24565 39647 47230 48653
16635
616
3856 13796 13796
CP-intensity
Lossy-RePair `(MB)
Freq-RePair v(MB)10100
1000 10000
10100
1000 10000
558
543
540
535
588
535
535
535
8103
6479
6494
6657
5423
5848
5859
5923
1936
3552
3722
3738
616
2477
2477
2477

予測精度, メモリー, 学習時間

compression size (MB)compression time (sec)working space (MB)• Dspace : 圧縮データ行列のメモリ• Ospace: 最適化のメモリ
4: Resultsof cPLS, PCA-SL,
bMH-SL and SGD for various datasets. Dspace: the working spac
data matrix (MB), Ospace: the working space for optimization algorithm and Ltime: learning• CP-intencity(110GB)上でPLSを学習するのに10GB程度
Data
Book-review
CompoundWebspamCP-interaction
CP-intensity

m100
2060
4060

Dspace(MB)
1288
786
890
4367
472

Data
Book-review
CompoundWebspamCP-interaction
CP-intensity

m/C
100/1
25/0.150/1
100/0.1

Dspace(MB)
14747
12200
1521

Data
Book-review
CompoundWebspamCP-interaction
CP-intensity

b/h/C
100/16/0.01
30/16/10
30/16/10
30/16/0.1
100/16/0.1

Dspace(MB)245722012366
253

cPLS
Ospace(MB)
15082
7955
7736
53885
10683
PCA-SL
Ospace(MB)
110
12
11
bMH-SL
Ospace(MB)
110
12
1854
11Ltime(sec)
21628
1089
4171
35880
33969

AUC/PCC
0.96
0.83
0.99
0.77
0.67

Ltime(sec)
6820
6
129
>24hours
42

AUC/PCC
0.70
0.65
0.99
0.11

Ltime(sec)1033
121005445

AUC/PCC
0.95
0.62
0.99
0.77
0.54

抽出された化合物の部分構造特徴
Component1

Component2

Component3Component6  Component5



Component4

Component7                                                                                                        

Component10 Component9  Component8

  

まとめ• 圧縮されたデータ行列上での統計モデルの学習
法• 文法圧縮されたデータ行列上でPLS回帰モデルを学習• 利点– PLS回帰モデル学習のメモリ削減– 巨大データ行列からの特徴抽出