スパースPCA

スパース主成分分析(SPCA またはスパース PCA) は、統計分析、特に多変量データ セットの分析で使用される手法です。入力変数にスパース構造を導入することで、データの次元を削減する 主成分分析(PCA)の従来の手法を拡張します。

通常の PCA の欠点は、主成分が通常、すべての入力変数の線形結合であることです。SPCA は、少数の入力変数 (SPC) の線形結合である成分を見つけることでこの欠点を克服します。これは、SPC を定義する線形結合の係数の一部 (負荷量と呼ばれる)がゼロになることを意味します^{[注 1]} 。ゼロ以外の負荷量の数は、SPC の 基数と呼ばれます。

データ行列を考えます。ここで、各列は入力変数を表し、各行はデータ母集団からの独立したサンプルを表します。 の各列の平均は 0 であると仮定します。そうでない場合は、 の各要素から列ごとの平均を減算できます。を の次元を持つ経験的共分散行列とします。 ${\displaystyle X}$${\displaystyle p}$${\displaystyle n}$${\displaystyle X}$${\displaystyle X}$${\displaystyle \Sigma ={\frac {1}{n-1}}X^{\top }X}$${\displaystyle X}$${\displaystyle p\times p}$

の整数が与えられた場合、スパース PCA 問題は、ベクトルの基数を制約しながら、ベクトルによって表される方向に沿った分散を最大化する問題として定式化できます。 ${\displaystyle k}$${\displaystyle 1\leq k\leq p}$${\displaystyle v\in \mathbb {R} ^{p}}$

${\displaystyle {\begin{aligned}\max \quad &v^{T}\Sigma v\\{\text{subject to}}\quad &\left\Vert v\right\Vert _{2}=1\\&\left\Vert v\right\Vert _{0}\leq k.\end{aligned}}}$式1

最初の制約は、v が単位ベクトルであることを指定します。2 番目の制約では、はvの疑似ノルムを表します。これは、 v の非ゼロ成分の数として定義されます。したがって、2 番目の制約は、vの非ゼロ成分の数がk以下であることを指定します。 k は通常、次元pよりもはるかに小さい整数です。式 1の最適値は、 kスパース最大固有値として知られています。 ${\displaystyle \left\Vert v\right\Vert _{0}}$${\displaystyle \ell_{0}}$

k=pとすると、問題は通常のPCAに簡略化され、最適値は共分散行列Σの最大固有値になります。

最適解vを見つけた後、Σを縮小して新しい行列を得る。

${\displaystyle \Sigma _{1}=\Sigma -(v^{T}\Sigma v)vv^{T},}$

このプロセスを繰り返して、さらなる主成分を取得します。ただし、PCA とは異なり、スパース PCA では異なる主成分が直交していることを保証できません。直交性を実現するには、追加の制約を適用する必要があります。

次の同等の定義は行列形式である。p ×p対称行列をとすれば、スパースPCA問題は次のように書き直すことができる。 ${\displaystyle V}$

${\displaystyle {\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{subject to}}\quad &Tr(V)=1\\&\Vert V\Vert _{0}\leq k^{2}\\&Rank(V)=1,V\succeq 0.\end{aligned}}}$式2

Tr は行列トレースで、行列Vの非ゼロ要素を表します。最後の行は、Vが行列の階数が1 で、半正定値であることを示します。最後の行は、 を持つことを意味し、したがって式 2 は式 1と同等です。 ${\displaystyle \Vert V\Vert _{0}}$${\displaystyle V=vv^{T}}$

さらに、この定式化におけるランク制約は実際には冗長であり、したがってスパースPCAは次の混合整数半正定値計画として表すことができる^[1]

${\displaystyle {\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{subject to}}\quad &Tr(V)=1\\&\vert V_{i,i}\vert \leq z_{i},\forall i\in \{1,...,p\},​​\vert V_{i,j}\vert \leq {\frac {1}{2}}z_{i},\forall i,j\in \{1,...,p\}:i\neq j,\\&V\succeq 0,z\in \{0,1\}^{p},\sum _{i}z_{i}\leq k\end{aligned}}}$式3

基数制約のため、特に次元pが高い場合、最大化問題を正確に解くことは困難です。実際、式1のスパースPCA問題は強い意味でNP困難です。 ^[2]

ほとんどのスパース問題と同様に、SPCAにおける変数選択は計算上扱いにくい非凸NP困難問題であるため^[3]、解決策を見つけるために貪欲な準最適アルゴリズムがよく使用されます。

（式１の）いくつかの代替アプローチが提案されており、その中には

• 回帰フレームワーク、^[4]
• ペナルティ付き行列分解フレームワーク、^[5]
• 凸緩和/半正定値計画フレームワーク、^[6]
• 一般化されたべき乗法フレームワーク^[7]
• 交互最大化フレームワーク^[8]
• 前方後方貪欲探索と分岐限定法を用いた正確な方法、^[9]
• 証明可能な最適な分岐限定法^[10]
• ベイズ定式化フレームワーク。^[11]
• 証明可能な最適な混合整数半正定値分岐カット法^[1]

スパースPCAの方法論的・理論的発展と科学的研究への応用は、最近調査論文でレビューされています。^[12]

スパースPCAは半正定値計画法（SDP）で近似できることが提案されている。^[6]ランク制約を削除し、カーディナリティ制約を1ノルムの凸制約で緩和すると、半正定値計画法の緩和が得られ、これは多項式時間で効率的に解くことができる。

${\displaystyle {\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{subject to}}\quad &Tr(V)=1\\&\mathbf {1} ^{T}|V|\mathbf {1} \leq k\\&V\succeq 0.\end{aligned}}}$式3

2番目の制約では、はp×1のベクトルであり、|V|はVの要素の絶対値を要素とする行列です。 ${\displaystyle \mathbf {1} }$

緩和された問題式 3の最適解は、必ずしもランク 1 であるとは限りません。その場合、主要な固有ベクトルのみを保持するように切り捨てることができます。 ${\displaystyle V}$${\displaystyle V}$

半正定値計画法はn=300以上の共変量ではスケールしないが、半正定値緩和法の2次円錐緩和法はほぼ同等のタイト性があり、n=1000の共変量の問題をうまく解くことができることが示されている^[13]

通常の PCA を、各入力変数が異なる資産を表すデータセットに適用すると、すべての資産の加重組み合わせである主成分が生成される場合があります。対照的に、スパース PCA は、少数の入力資産のみの加重組み合わせである主成分を生成するため、その意味を簡単に解釈できます。さらに、これらの主成分に基づく取引戦略を使用する場合、資産が少ないほど取引コストが低くなります。

各入力変数が特定の遺伝子に対応するデータセットを考えてみましょう。スパース PCA は、少数の遺伝子のみを含む主成分を生成できるため、研究者はこれらの特定の遺伝子に焦点を当ててさらに分析することができます。

現代のデータセットでは、入力変数の数（）がサンプル数（ ）と同程度か、それよりはるかに多い場合がよくあります。がゼロに収束しない場合、古典的なPCAは一貫性がないことが示されています。言い換えると、式1を とすると、サンプルサイズが のときに最適値はデータ母集団の最大固有値に収束せず、最適解は最大分散の方向に収束しません。しかし、スパースPCAは、 の場合でも一貫性を保つことができます。${\displaystyle p}$${\displaystyle n}$${\displaystyle p/n}$${\displaystyle k=p}$${\displaystyle n\rightarrow \infty}$${\displaystyle p\gg n.}$

kスパースの最大固有値（式1の最適値）は、すべての方向が同じ分散を持つ等尺性モデルを、高次元設定でのスパイク共分散モデルと区別するために使用できます。^[14]帰無仮説では、データは平均0で共分散が単位行列に等しい多変量正規分布から生成され、対立仮説では、データは信号強度のスパイクモデルから生成されると指定する仮説検定を考えます。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle \theta}$

${\displaystyle H_{0}:X\sim N(0,I_{p}),\quad H_{1}:X\sim N(0,I_{p}+\theta vv^{T}),}$

ここで、 はk 個の非ゼロ座標のみを持ちます。最大のk疎な固有値は、 の場合にのみ 2 つの仮説を区別できます。 ${\displaystyle v\in \mathbb {R} ^{p}}$${\displaystyle \theta >\Theta ({\sqrt {k\log(p)/n}})}$

k疎な固有値を計算するのは NP 困難であるため、半正定値計画法の緩和の最適値 (式 3 ) で近似することができます。その場合、 であれば 2 つの仮説を区別することができます。植え付けられたクリーク予想が成り立つ場合、追加の項は他の多項式時間アルゴリズムでは改善できません。 ${\displaystyle \theta >\Theta ({\sqrt {k^{2}\log(p)/n}})}$${\displaystyle {\sqrt {k}}}$

• amanpg - 交代多様体近似勾配法を用いたスパースPCA用のRパッケージ^[15]
• elasticnet – エラスティックネットを用いたスパース推定とスパースPCAのためのRパッケージ^[16]
• epca – 大規模データセットの探索的主成分分析のためのRパッケージ。スパース主成分分析とスパース行列近似を含む。^[17]
• nsprcomp - 閾値付き累乗反復に基づくスパースおよび/または非負PCA用のRパッケージ^[18]
• scikit-learn – 分解モジュールにスパースPCAやその他の技術を含む機械学習用のPythonライブラリ。^[19]