PCA

中川研機械学習勉強会 2007/4/4
A Generalization of Principal
Component Analysis to the
Exponential Family
M. Collins and S. Dasgupta and R. Schapire, NIPS 13 (2001)
吉田稔
PCA(Principal Component Analysis)とは
•
•
•
•
•
次元圧縮の有名な手法
入力：n個の点
dより低い次元の部分空間を考える。
の部分空間への射影：
目的：
が最小になるような部分空間を選ぶ
PCAの確率論的解釈
•
•
•
を正規分布とする。
は、分布
からのサンプリング
のlikelihoodを最大化するパラメー
タ
を求めよ。
•
の最小化と同値（正規分布の
negative log likelihoodがこの形になるので）
本論文のねらい
• 正規分布は、（-∞, +∞）の実数値を対象とし
た分布
• その他の値（整数、正の実数、1-0、…）に対し
ては、もっと適した分布があるはず。
• PCAの仮定を、正規分布以外の分布に拡張し
たい
準備：Exponential Family
• （本論文における）Exponential Family
•
：正規化項
• この形で書ける分布の例：
– 分散１の正規分布:
– ベルヌーイ分布:
準備：Exponential Family
• 正規化項
の微分を
と書く
•
を微分することによ
り、
を得る。
• すなわち、このとき、
は、(natural)
parameterをexpectation parameterに変換す
る関数と見なすことができる。
– 注意：正規分布はパラメータとデータが同じ空間
だが、一般的には違う。
– Expectation Parameterはデータと同じ空間に載る。
参考：Generalized Linear Model
• Linear Regression:
– 入力
に対し、
を返す。
を yi の推定値とする。
• Linear Regressionを２乗誤差（⇔正規分布）以
外に拡張
参考：Generalized Linear Model
• パラメータを線形に予測
•
: 線形予測値をexpectation parameter
へ変換（すなわち、＝g(θ)と考えてよい）
– hを恒等関数とすれば、log-likelihoodは、
=
• これを最大化させればよい。
• g(θ)=θ ⇒
⇒ 最小２乗法
（再掲）
参考：Generalized Linear Model
• パラメータを線形に予測
•
: 線形予測値をexpectation parameter
へ変換（すなわち、＝g(θ)と考えてよい）
– Logistic Regression: h-1=logit(p)=log(p/(1-p))
– h=exp(θ)/{1+exp(θ)}=g(θ) ⇒
– Negative log-likelihoodは、
準備：Bregman Distance
• p,qの”距離”を、狭義凸関数Fを通して定義
• p,qが離れるほど、Fの値も離れる（：凸関数の
性質）
F(p)の実際の値
F(p)のq,F(q)からの予測値
準備：Bregman Distance
• 適当なFを定義することにより、exponential
familyのnegative log-likelihoodが、Bregman
Distanceを用いて表現できる。
（再掲）
準備：Bregman Distance
• すなわち、log-likelihoodの最大化を、「xと、g(θ)
（＝expextation parameter)のBregman Distance
を最小化する」と読み替えることができる。
• なお、本論文では、ベクトル間、行列間の
Bregman Distanceを以下のように定義している。
Exponential Family PCA
• 入力：n個の点
• dより低い次元の部分空間を考える。
•
の部分空間への射影：
• 目的：
ぶ
に最も近い
を選
Exponential Family PCA
• 定義
基底ベクトル行列（l×d）
基底ベクトル
∈
データ行列（n×d）
パラメータ予測値
係数行列
：i行k列目
パラメータ行列
Exponential Family PCA
定数（以後省略）
• Loss Function
（
– 正規分布のとき：
– ベルヌーイ分布のとき：
の最小化）
⇒普通のPCA
• Bregman Distanceによる表現
Exponential Family PCA
• Vが与えられたときの最適な
:
– 正規分布(⇒g(θ)=θ)を仮定すれば、BFはユーク
リッド距離
– ⇒aは、単純なxiのQへの射影
• 最適なV:
アルゴリズム
• 簡単のため、l=1の場合を考える。
• アイデア：VとAを交互に更新することにより、
Θを更新する。
それぞれの最適化問題は、
GLM regressionと見なせる。
– Lは、VあるいはAを固定したとき凸関数
（再掲）
アルゴリズム
• 特に正規分布のとき、各iterationは単純な射
影であり、以下の形になる。
の固有値を求める冪乗法と同じ形
アルゴリズム
• l>1のときは、例えば以下のような方法で計算
する。

Download Report