このPCAが熱いトップ10

この記事は[バイオインフォマティクス Advent Calendar 2020](https://qiita.com/advent-calendar/2020/bioinfo)の22日目の記事です

今年はあまり書くことが思いつかなかったので、自分が注目しているPCA（Principal Component Analysis, 主成分分析）ベースの手法を紹介する。

# 1. Randomized PCA
[Halko, N et al., FINDING STRUCTURE WITH RANDOMNESS: PROBABILISTIC ALGORITHMS FOR CONSTRUCTING APPROXIMATE MATRIX DECOMPOSITIONS, 2010](https://arxiv.org/pdf/0909.4061.pdf)
データを一度ランダムに低次元に射影してコンパクトにしてから扱うことで、大規模データ行列も高速・低メモリで計算できるPCA。
今年出した[PCAのベンチマーク論文](https://genomebiology.biomedcentral.com/articles/10.1186/s13059-019-1900-3)で、速度、精度ともに性能が良かった。
乱数を使っているのに、驚くほど正確な値を返す。
実装も簡単で4行くらいで書ける。
そのせいかRでもPythonでも様々な実装がある。
PCAでできることは、他の固有値分解・特異値分解を使う手法でも大体できるので、例えば[Randomized CCA](https://arxiv.org/abs/1411.3409)という手法もその後開発されている。
乱数を使う線形代数は[ランダム線形代数](https://arxiv.org/abs/2002.01387)という名前で、１研究分野になってきている。

# 2. SGD-PCA
[Erkki, Oja, et al., On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix, 1985](https://www.sciencedirect.com/science/article/pii/0022247X85901313)
Deep Learningでは主流の最適化手法である、SGD（Stochastic Gradient Descent）で固有値分解を行うもの。
Ojaの手法とも呼ばれる。
今年出した[PCAのベンチマーク論文](https://genomebiology.biomedcentral.com/articles/10.1186/s13059-019-1900-3)では、精度が若干悪かったが、正則化項の追加や、学習率スケージューリング（[ADAGRAD](https://github.com/rikenbit/OnlinePCA.jl)とか）のところでカスタムできるメリットがある。

# 3. Riemannian PCA
[Silvere Bonnabel, Stochastic gradient descent on Riemannian manifolds, 2013](https://arxiv.org/abs/1111.5280)
固有値分解は制約ありの最適化として解かれるが、制約を考えずにデータが曲がった空間（多様体）上にいるという仮定で解いたもの。
SGDよりも収束が早くなるらしい。
https://www.slideshare.net/tkm2261/nips2016-riemannian-svrg-fast-stochastic-optimization-on-riemannian-manifolds

# 4. Supervised PCA
[Elnaz Barshan, et al., Supervised principal component analysis: Visualization, classification and regression on subspaces and submanifolds, Pattern Recognition, 2011](http://cslt.riit.tsinghua.edu.cn/mediawiki/images/1/11/Supervised_Principal_Component_Analysis-_Visualization%2C_Classification_and_Regression_on_Subspace_and_Submanifolds.pdf)
データ行列Xの分解に、教師データYも使う教師あり次元圧縮法。
Hilbert-Schmidt Independence Criterion（HSIC）を利用して、カーネル関数で高次元空間に射影されたXとYの独立性をもとめる問題と、PCAの固有値分解問題を混ぜている。
よく似た手法に、[Laplacian PCA](https://openaccess.thecvf.com/content_cvpr_2013/papers/Jiang_Graph-Laplacian_PCA_Closed-Form_2013_CVPR_paper.pdf)や[Hessian PCA](https://viplab.cis.um.edu.mo/publications/conference/Principal%20Component%20Analysis%20on%20Graph-Hessian.pdf)もある。
なぜか、正則化項がトレース(tr）で、PCAの目的関数もtrなので、tr同士をまとめて、簡単に最適化できるのも魅力。

# 5. Contrastive PCA
[Abid, A. et al., Exploring patterns enriched in a dataset with contrastive principal component analysis, Nature Communications, 2018](https://www.nature.com/articles/s41467-018-04608-8)
あるターゲット行列$X_{1}$と、バックグラウンド行列$X_{2}$があった時に、バックグラウンドでも分散が大きくなる固有ベクトルは取らないように補正したPCA。
データに含まれるパターンのうち、面白くない成分はバックグランドとすれば良いので、色々使えそう。

# 6. Differential PCA
[Hongkai, Ji et al., Differential principal component analysis of ChIP-seq, PNAS, 2013](https://www.pnas.org/content/110/17/6789)
Contrastive PCAと似ているが、2行列$X_{1}$、$X_{2}$の差分行列を特異値分解したもの。
ターゲット vs バックグランドという構図ではなく、単に差を調べたい感じ。
ChIP-seqデータへの適用例あり。

# 7. GO-PCA
[Wagner, F. et al., GO-PCA: An Unsupervised Method to Explore Gene Expression Data Using Prior Knowledge, PLOS ONE, 2015](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0143196)
オミックスデータ行列でまずPCAをして、取り出したPCごとにGOエンリッチメント解析をしたもの。

# 8. Tree PCA
[Burcu Aydin, A PRINCIPAL COMPONENT ANALYSIS FOR TREES, The Annals of Applied Statistics, 2009](https://projecteuclid.org/download/pdfview_1/euclid.aoas/1267453955)
木構造データにも適用できるPCA（まだ精読できていない）。

# 9. Complex PCA
[J. D. Horel, et al., Complex Principal Component Analysis: Theory and Examples, Journal of Applied Meteorology and Climatology, 1984](https://journals.ametsoc.org/view/journals/apme/23/12/1520-0450_1984_023_1660_cpcata_2_0_co_2.xml)
複素数にも適用できるPCA。
まだ精読できていないが、多分波形データに使うのだと思う。

# 10. Quantum PCA
[Seth Lloyd, Quantum principal component analysis,　Nature Physics, 2014](https://www.nature.com/articles/nphys3029)
数学が難しくてまだ解読できてないが、量子コンピューターを使うことで、通常$\mathcal{O}\left(NM \min{\left(N,M\right)}\right)$の計算オーダーである特異値分解が、$\mathcal{O}\left(\log{d}\right)$で解けるらしくて驚異的（N: 行数、M: 列数、d: 圧縮次元数）。
ハードから攻めるという点では、[FPGAでPCAをした論文](https://link.springer.com/article/10.1007/s11554-016-0650-7)もある。
量子コンピュータで固有値分解を解く部分は、Variational Quantum Eigensolver (VQE)というソルバーが既にあるらしい
（cf. [量子コンピュータによる機械学習](https://www.kyoritsu-pub.co.jp/bookdetail/9784320124622)）。