novelty日記

データサイエンスやプログラムなど

Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA

Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCAを読む

概要

通常のデータに対するバッチ処理をベースとしたPCAと違い、 ストリームデータに対するPCAは、その問題設定から制約があり、従来手法の通りではうまくいかない。

その制約として挙げられるのは主にデータが逐次的に与えられるため、モデルを更新する必要がある事と、 リソースの問題でメモリ制約が存在する事、がある。 またPCAそのものを評価する場合においても、一般的に再構成誤差のみに注目した評価が行われるが、 実際は各主成分がどのように学習されたかについても評価する必要がある。 これをスペクトル誤差と呼ぶ。

この問題に対しては2種類のアプローチが存在する。 1つ目は確率勾配法に基づいて逐次的に最適化する手法(SPCA)だが、これは主成分が1つの場合のみ収束性が保証されている。 2つ目はデータブロック毎にべき乗法に基づき共分散行列のべき乗を求め、それを用いて主成分(固有値)を求める手法である(BPCA)。 この時各ブロック毎の経験共分散行列の積により共分散行列のべき乗を近似するのが鍵である。 しかしデータブロックサイズを決定する必要があり、それは簡単ではない。

結局のところ、SGDのPCAは一般的な次元における収束の証明がなされておらず、BPCAはブロックサイズが決定できず、実際問題どちらを採用するのが良いのかもわからない。 本論では、これら問題に対する対処を提案する。

本論では、1つ目の確率勾配法に基づく手法において、主成分数が1つより多い一般的な場合においても収束性を示す。 また2つ目のデータブロックに対するべき乗法においては、ブロックサイズを自動で決定する手法を提案し、 その利用によりより良い収束性が得られる事を示す。

どちらの提案手法も基本的なアプローチとして、対象とする共分散行列の固有ベクトル固有値)をどれだけ効率よく計算できるかを考えている。 最適化時における各更新ステップでは、SPCAでは1サンプル毎にSGDの要領に沿って固有ベクトルの推測値を更新し、BPCAでは各ブロックに対して、一度に上記SGDと似た要領で固有ベクトルの推測値を更新する。