KDD'16に文法圧縮されたデータ行列上でのPLS回帰のモデル学習に関する論文が採択

データマイニング分野のトップの国際会議KDD’16に以下の論文が採択されました.

Y.Tabei, H.Saigo, Y.Yamanishi, S.J.Puglisi: Scalable partial least squares regression on grammar-compressed data matrices, accepted to KDD’16

内容は, PLS回帰モデルの入力となるデータ行列を文法圧縮してその上でスケーラブルにモデル学習するというものです.
機械学習法の殆の入力はデータ行列とそのラベル列です. 機械学習には, データ行列がメモリーの大半を占める機械学習アルゴリズムが存在して, もし, データ行列を圧縮して学習することができれば, 入力が巨大な行列でもメモリー効率良くモデル学習を行なうことができます.PLS回帰モデルにはそのような学習アルゴリズムが存在して, 圧縮されたデータ行列上でモデル学習を行なうことができます. しかし, モデル学習を行なうためにはナイーブには圧縮されたデータ行列をいったん解凍して学習を行わなければならず, そのようにするともとのデータ行列を保存するのと同じメモリーを消費してしまいます. よって, 省メモリーでモデル学習を行なうためには, 圧縮したデータ行列上で行列の要素にアクセスする手法が必要です. 本研究では, データ行列を文法圧縮して, 行列全体を復元することなく行列の要素にアクセスする手法を開発しています. これにより, PLS回帰モデルのメモリー効率の良い学習を可能にしています.

文法圧縮を用いる利点は, 多くのデータ行列に対して高い圧縮率を達成することができることに加えて, 可逆データ圧縮であることが挙げられます. データ行列を圧縮してモデル学習を行なう先行研究に, Liらが提案したb-bit minhashを用いる方法があります. しかし, b-bit minhashは不可逆データ圧縮であり, 元のデータ行列を復元することが不可能で, 学習後のモデルの解釈(どの特徴が予測に寄与しているか)ができません. 一方, 文法圧縮は可逆圧縮なので, モデルの解釈を行なうことができます.
実データを用いた実験と大規模データ向けの学習法(b-bit minhash, SGDなど)などの比較により, 圧縮率, 予測精度, モデルの解釈可能性の観点から文法圧縮の有効性を示しています.

2016/6/20更新
arXivに論文を置きました. http://arxiv.org/abs/1606.05031