Mengapa PCA data menggunakan SVD data?

Pertanyaan ini adalah tentang cara yang efisien untuk menghitung komponen utama.

Banyak teks tentang advokasi PCA linier menggunakan dekomposisi nilai singular dari data dengan santai . Yaitu, jika kita memiliki data dan ingin mengganti variabel ( kolomnya ) dengan komponen utama, kita lakukan SVD: , nilai singular (akar kuadrat dari nilai eigen) yang menempati diagonal utama , vektor eigen kanan adalah matriks rotasi ortogonal dari variabel-sumbu ke dalam komponen sumbu, komponen vektor eigen kiri seperti , hanya untuk kasus. Kami kemudian dapat menghitung nilai komponen sebagai . $\bf X$ $\bf X=USV'$ $\bf S$ $\bf V$ $\bf U$ $\bf V$ $\bf C=XV=US$
Cara lain untuk melakukan PCA variabel adalah melalui dekomposisi matriks kuadrat (yaitu dapat berupa korelasi atau kovarian , dll., variabel). Dekomposisi dapat berupa dekomposisi eigen atau dekomposisi nilai singular: dengan matriks semidefinit positif simetris kuadrat, mereka akan memberikan hasil yang sama dengan nilai eigen seperti diagonal , dan seperti dijelaskan sebelumnya. Nilai komponen akan menjadi . $\bf R=X'X$ $\bf R$ $\bf R=VLV'$ $\bf L$ $\bf V$ $\bf C=XV$

Sekarang, pertanyaan saya: jika data adalah matriks besar, dan jumlah kasus (yang sering merupakan kasus) jauh lebih besar daripada jumlah variabel, maka cara (1) diharapkan akan jauh lebih lambat daripada cara (2) ), karena cara (1) menerapkan algoritma yang cukup mahal (seperti SVD) ke matriks besar; itu menghitung dan menyimpan matriks besar yang kita benar-benar tidak perlu dalam kasus kami (PCA variabel). Jika demikian, lalu mengapa begitu banyak buku teks tampaknya mendukung atau hanya menyebutkan satu-satunya cara (1)? Mungkin itu adalah efisien dan aku kehilangan sesuatu? $\bf X$ $\bf U$

pca algorithms svd matrix-decomposition ttnphns
sumber

Secara umum kami hanya tertarik pada beberapa komponen utama yang menjelaskan sebagian besar varians. Dimungkinkan untuk melakukan pengurangan SVD; misalnya jika adalah dimensi mana kemudian 's fungsi akan menghitung hanya yang pertama kiri dan kanan vektor singular secara default.

X

$X$

N \times p

$N \times p$

p << N

$p << N$ Rsvd

p

$p$

M. Berk

@ M.Berk: Namun, sama dalam kedua pendekatan: mereka menghasilkan hasil yang setara (sama dengan menandatangani perubahan). Juga, misalnya R menghitung hanya jika diminta.

p

$p$

C

$\mathbf C$

cbeleites mendukung Monica

Apakah Anda memiliki referensi cara (1)? Saya hanya mengetahui PCA diimplementasikan melalui SVD pada matriks kovarians (yaitu cara 2), karena ini menghindari beberapa masalah numerik dan dengan jelas skala dengan dimensi, bukan ukuran data yang ditetapkan. Cara (1) Saya akan memanggil SVD, bukan PCA sama sekali. Saya hanya melihatnya dalam konteks SVD murni, di mana orang tidak akan melakukan dekomposisi lengkap sebenarnya.

Anony-Mousse

@ Anony-Mousse, Hanya satu untuk menyebutkan, Joliffe, Principal component analysis, 2nd ed.Sebenarnya, Joliffe menjelaskan kedua cara, tetapi dalam bab inti tentang PCA ia mengatakan tentang cara 1, sejauh yang saya ingat.

ttnphns

@ Anony-Mousse, Way 1 bagi saya penting dari titik teoretis karena jelas menunjukkan bagaimana PCA terkait langsung dengan analisis korespondensi sederhana .

ttnphns

Jawaban:

Berikut adalah 2ct saya tentang topik ini

Kuliah kimia di mana saya pertama kali belajar PCA menggunakan solusi (2), tapi itu tidak berorientasi numerik, dan kuliah numerik saya hanya pengantar dan tidak membahas SVD sejauh yang saya ingat.
Jika saya memahami Holmes: Fast SVD untuk Matriks Skala Besar dengan benar, ide Anda telah digunakan untuk mendapatkan SVD matrik matriks panjang yang cepat secara komputasi.
Itu berarti bahwa implementasi SVD yang baik dapat secara internal mengikuti (2) jika menemui matriks yang sesuai (saya tidak tahu apakah masih ada kemungkinan yang lebih baik). Ini berarti bahwa untuk implementasi tingkat tinggi lebih baik menggunakan SVD (1) dan menyerahkannya pada BLAS untuk menangani algoritma mana yang digunakan secara internal.

Pemeriksaan praktis cepat: OpenBLAS's svd tampaknya tidak membuat perbedaan ini, pada matriks 5e4 x 100, svd (X, nu = 0)menggunakan median 3,5 detik, sementara svd (crossprod (X), nu = 0)butuh 54 ms (dipanggil dari R with microbenchmark).
Kuadrat dari nilai eigen tentu saja cepat, dan hingga itu hasil dari kedua panggilan itu sama.

timing  <- microbenchmark (svd (X, nu = 0), svd (crossprod (X), nu = 0), times = 10)
timing
# Unit: milliseconds
#                      expr        min         lq    median         uq        max neval
#            svd(X, nu = 0) 3383.77710 3422.68455 3507.2597 3542.91083 3724.24130    10
# svd(crossprod(X), nu = 0)   48.49297   50.16464   53.6881   56.28776   59.21218    10

pembaruan: Lihatlah Wu, W.; Massart, D. & de Jong, S .: Algoritma PCA kernel untuk data luas. Bagian I: Teori dan algoritma, Chemometrics and Intelligent Laboratory Systems, 36, 165 - 172 (1997). DOI: http://dx.doi.org/10.1016/S0169-7439(97)00010-5

Makalah ini membahas sifat numerik dan komputasi dari 4 algoritma yang berbeda untuk PCA: SVD, eigen decomposition (EVD), NIPALS dan POWER.

Mereka terkait sebagai berikut:

computes on      extract all PCs at once       sequential extraction    
X                SVD                           NIPALS    
X'X              EVD                           POWER

Konteks makalah ini luas , dan mereka bekerja pada (kernel PCA) - ini hanya situasi yang berlawanan dengan yang Anda tanyakan. Jadi untuk menjawab pertanyaan Anda tentang perilaku matriks panjang, Anda perlu bertukar arti "kernel" dan "klasik". $\mathbf X^{(30 \times 500)}$ $\mathbf{XX'}$

perbandingan kinerja

Tidak mengherankan, EVD dan SVD mengubah tempat tergantung pada apakah algoritma klasik atau kernel digunakan. Dalam konteks pertanyaan ini, ini berarti bahwa satu atau yang lain mungkin lebih baik tergantung pada bentuk matriks.

Tetapi dari diskusi mereka tentang SVD dan EVD "klasik" jelas bahwa dekomposisi adalah cara yang sangat biasa untuk menghitung PCA. Namun, mereka tidak menentukan algoritma SVD mana yang digunakan selain itu mereka menggunakan fungsi Matlab . $\mathbf{X'X}$ svd ()

    > sessionInfo ()
    R version 3.0.2 (2013-09-25)
    Platform: x86_64-pc-linux-gnu (64-bit)

    locale:
     [1] LC_CTYPE=de_DE.UTF-8       LC_NUMERIC=C               LC_TIME=de_DE.UTF-8        LC_COLLATE=de_DE.UTF-8     LC_MONETARY=de_DE.UTF-8   
     [6] LC_MESSAGES=de_DE.UTF-8    LC_PAPER=de_DE.UTF-8       LC_NAME=C                  LC_ADDRESS=C               LC_TELEPHONE=C            
    [11] LC_MEASUREMENT=de_DE.UTF-8 LC_IDENTIFICATION=C       

    attached base packages:
    [1] stats     graphics  grDevices utils     datasets  methods   base     

    other attached packages:
    [1] microbenchmark_1.3-0

loaded via a namespace (and not attached):
[1] tools_3.0.2

$ dpkg --list libopenblas*
[...]
ii  libopenblas-base              0.1alpha2.2-3                 Optimized BLAS (linear algebra) library based on GotoBLAS2
ii  libopenblas-dev               0.1alpha2.2-3                 Optimized BLAS (linear algebra) library based on GotoBLAS2

Cbeleites mendukung Monica
sumber

Jadi, pengujian Anda (3,5 detik vs 54 msec) mendukung baris saya bahwa "cara 1" jauh lebih lambat. Kanan?

ttnphns

@ttnphns: ya. Tetapi karena svd disediakan oleh BLAS yang bisa berbeda dengan BLAS yang berbeda. Saya berharap bahwa BLAS dioptimalkan yang baik melakukan sesuatu seperti ini. Namun, tampaknya tidak demikian dengan OpenBLAS. Saya terlalu malas untuk memeriksa BLAS lain, tetapi mungkin beberapa orang dapat memeriksa BLAS lainnya sehingga kami mencari tahu mana yang dioptimalkan untuk kasus ini dan mana yang tidak. (Saya mengirim email ke pengembang OpenBLAS dan mengiriminya tautan ke pertanyaan ini, jadi mungkin dia dapat menambahkan beberapa info, misalnya alasan untuk tidak mengubah algoritme ke svd (X'X)matriks yang lama.)

cbeleites mendukung Monica

Beberapa poin perlu klarifikasi (untuk saya). Bisakah "metode kernel" diringkas sebagai "bekerja pada bukan ketika "? jika demikian, itu cukup sepele. Saya tidak tahu POWER tetapi saya tahu NIPALS, yang menghitung vektor eigen dari dengan mengulangi(konvergen ke vektor eigen pertama , maka Anda harus memperbarui untuk menghitung yang kedua, dll). Ada dua cara untuk melakukan NIPALS, (1) Anda dapat melakukan , atau (2) Anda dapat melakukan produk sebagai , cara mana yang digunakan di sini? Saya kira (1) digunakan, yang bisa tidak adil.

X^{'}

$X'$

X

$X$

n < p

$n<p$

X^{'} X

$X'X$

u_{n + 1} = X^{'} X u_{n} / | | X^{'} X u_{n} | |

$u_{n+1} = X'Xu_n / ||X'Xu_n||$

v_{1}

$v_1$

X

$X$

X^{'} X

$X'X$

X^{'} \times (X u_{n})

$X' \times (X u_n)$

@ Elvis: a) Ada lebih banyak metode kernel daripada hanya menghitung pada , lihat misalnya stats.stackexchange.com/questions/2499/… . Kesetaraan ini sepele untuk PCA (tidak masalah apakah Anda mulai dengan mendapatkan vektor tunggal kanan atau kiri) tetapi tidak untuk metode lain. b) "cara untuk melakukan NIPAL" bergantung pada prinsip keseluruhan yang sama. Algoritma mana yang digunakan untuk SVD tergantung pada BLAS Anda, dan sebenarnya tebakan saya adalah bahwa NIPALS tidak terlibat di sini. Perhatikan bahwa waktu saya termasuk perhitungan produk silang.

X X^{T}

$\mathbf X \mathbf X^T$

cbeleites mendukung Monica

Saya sedang berbicara tentang pembaruan Anda, di mana Nipals terlibat. Saya mengonfirmasi bahwa Nipals tidak terlibat dalam SVD Lapack. Tentang percobaan patokan Anda, sesuatu seperti microbenchmark(X <- matrix(rnorm(5e6), ncol=100), Y <- t(X), svd(X), svd(Y), control=list(order="inorder"), times = 5)bisa menarik juga.

Elvis

SVD lebih lambat tetapi sering dianggap sebagai metode yang disukai karena akurasi numerik yang lebih tinggi.

Seperti yang Anda sebutkan dalam pertanyaan, analisis komponen utama (PCA) dapat dilakukan baik oleh SVD dari matriks data terpusat ( lihat utas T&J ini untuk perincian lebih lanjut ) atau dengan dekomposisi eigen dari matriks kovarians (atau, sebagai alternatif, jika , lihat di sini untuk detail lebih lanjut ). $\mathbf X$ $\frac{1}{n-1}\mathbf X^\top \mathbf X$ $\mathbf{XX}^\top$ $n\ll p$

Inilah yang tertulis dalam bantuanpca() fungsi MATLAB :

Algoritma komponen utama yang pcadigunakan untuk melakukan analisis komponen utama [...]:

'svd' - Default. Dekomposisi nilai singular (SVD) X.

'eig' - dekomposisi nilai eigen (EIG) dari matriks kovarians. Algoritma EIG lebih cepat daripada SVD ketika jumlah pengamatan, , melebihi jumlah variabel, , tetapi kurang akurat karena jumlah kondisi kovarians adalah kuadrat dari jumlah kondisi X. $n$ $p$

Kalimat terakhir menyoroti pentingnya kecepatan-akurasi trade-off yang berperan di sini.

Anda benar untuk mengamati bahwa komposisi eigend dari matriks kovarians biasanya lebih cepat daripada SVD dari matriks data. Berikut ini adalah patokan pendek di Matlab dengan matriks data acak : $1000\times 100$

X = randn([1000 100]);

tic; svd(X); toc         %// Elapsed time is 0.004075 seconds.
tic; svd(X'); toc        %// Elapsed time is 0.011194 seconds.
tic; eig(X'*X); toc      %// Elapsed time is 0.001620 seconds.
tic; eig(X*X'); toc;     %// Elapsed time is 0.126723 seconds.

Cara tercepat dalam hal ini adalah melalui matriks kovarians (baris ketiga). Tentu saja jika (bukan sebaliknya) maka itu akan menjadi cara paling lambat, tetapi dalam kasus itu menggunakan matriks Gram (baris keempat) akan menjadi cara tercepat sebagai gantinya. SVD dari matriks data itu sendiri akan lebih lambat. $n \ll p$ $\mathbf{XX}^\top$

Namun, itu akan lebih akurat karena mengalikan dengan dirinya sendiri dapat menyebabkan hilangnya akurasi numerik. Berikut ini adalah contoh, diadaptasi dari jawaban @ JM untuk Mengapa SVD pada lebih disukai daripada eigendekomposisi dalam PCA pada Math.SE. $\mathbf X$ $X$ $XX^⊤$

Pertimbangkan matriks data kadang-kadang disebut matriks Läuchli (dan mari kita hilangkan centering untuk contoh ini). Nilai singular kuadratnya adalah , , dan . Mengambil , kita dapat menggunakan SVD dan EIG untuk menghitung nilai-nilai ini:

X = (\begin{matrix} 1 & 1 & 1 \\ ϵ & 0 & 0 \\ 0 & ϵ & 0 \\ 0 & 0 & ϵ \end{matrix}),

$\mathbf X = \begin{pmatrix}1&1&1\\\epsilon & 0 & 0\\ 0 & \epsilon & 0 \\ 0 & 0 & \epsilon\end{pmatrix},$

3 + ϵ^{2}

$3+\epsilon^2$

ϵ^{2}

$\epsilon^2$

ϵ^{2}

$\epsilon^2$

ϵ = 10^{- 5}

$\epsilon = 10^{-5}$

eps = 1e-5;
X = [1 1 1; eye(3)*eps];
display(['Squared sing. values of X: ' num2str(sort(svd(X),'descend').^2')])
display(['Eigenvalues of X''*X:       ' num2str(sort(eig(X'*X),'descend')')])

mendapatkan hasil yang identik:

Squared sing. values of X: 3       1e-10       1e-10
Eigenvalues of X'*X:       3       1e-10       1e-10

Tetapi dengan mengambil sekarang kita dapat mengamati bagaimana kinerja SVD masih baik tetapi EIG rusak: $\epsilon = 10^{-10}$

Squared sing. values of X: 3       1e-20       1e-20
Eigenvalues of X'*X:       3           0 -3.3307e-16

Apa yang terjadi di sini, adalah bahwa sangat perhitungan kotak kovarians matriks jumlah kondisi dari , sehingga terutama dalam kasus ketika memiliki beberapa kolom hampir collinear (yaitu beberapa nilai singular sangat kecil), pertama komputasi matriks kovariansi dan kemudian komputasi komposisi eigendnya akan menghasilkan kehilangan presisi dibandingkan dengan SVD langsung. $\mathbf X$ $\mathbf X$

Saya harus menambahkan bahwa orang sering senang mengabaikan potensi kehilangan [kecil] presisi ini dan lebih suka menggunakan metode yang lebih cepat.

amuba kata Reinstate Monica
sumber

X^{T}

$\mathbf X^T$

X

$\mathbf X$

Terima kasih atas jawaban dan untuk pertimbangan pro dan kontra.

ttnphns

amoeba, mungkinkah Anda menemukan waktu untuk menunjukkan contoh konkret di mana stabilitas numerik menderita karena eig()pendekatan? (Pembaca akan mendapat manfaat: ada titik trade-off antara kecepatan dan stabilitas. Bagaimana seseorang dapat memutuskan dalam situasi praktis yang konkret?)

ttnphns

@ttnphns Saya menulis ulang seluruh jawaban, memberikan contoh nyata. Lihatlah.

Amuba mengatakan Reinstate Monica

@amoeba, terima kasih banyak telah datang kembali dan memberikan contoh! Saya mencoba kedua contoh epsilon di SPSS dan mendapatkan hasil seperti milik Anda kecuali untuk baris terakhir: bukannya 3 0 -3.3307e-16eigen di spss mengembalikan saya 3 0 0. Sepertinya fungsi tersebut memiliki beberapa nilai toleransi built-in dan tetap di luar yang nol. Dalam contoh ini, fungsi muncul seolah-olah untuk meretas simpul ketidakstabilan numerik dengan memberi nilai nol pada kedua nilai eigen kecil, "0" dan "-16".

ttnphns