Saya belajar PCA dari kursus Andrew Ng's Coursera dan materi lainnya. Dalam tugas pertama Stanford NLP kursus cs224n , dan dalam video ceramah dari Andrew Ng , mereka melakukan dekomposisi nilai singular bukan dekomposisi vektor eigen dari matriks kovarians, dan Ng bahkan mengatakan bahwa SVD secara numerik lebih stabil daripada komposisi eigend.
Dari pemahaman saya, untuk PCA kita harus melakukan SVD dari matriks (m,n)
ukuran data , bukan dari matriks kovarians (n,n)
ukuran. Dan dekomposisi vektor eigen dari matriks kovarians.
Mengapa mereka melakukan SVD matriks kovarians, bukan matriks data?
pca
linear-algebra
svd
eigenvalues
numerics
DongukJu
sumber
sumber
x=randn(10000); x=x'*x; tic; eig(x); toc; tic; svd(x); toc;
pada mesin saya menghasilkan 12s untuk eig () dan 26s untuk svd (). Jika jauh lebih lambat, setidaknya harus lebih stabil! :-)eig
atausvd
pada matriks kovarians, tapi sejauh yang saya tahu tidak ada perbedaan besar antara menggunakaneig
atausvd
pada matriks kovarians --- mereka keduanya algoritma stabil mundur. Jika ada, saya akan menempatkan uang saya pada eig menjadi lebih stabil, karena melakukan lebih sedikit perhitungan (dengan asumsi keduanya diimplementasikan dengan algoritma canggih).Jawaban:
amuba sudah memberikan jawaban yang baik di komentar, tetapi jika Anda ingin argumen formal, ini dia.
Dekomposisi nilai singular dari matriks adalah , di mana kolom adalah vektor eigen dari dan entri diagonal adalah akar kuadrat dari nilai eigennya, yaitu .A = U Σ V T V A T A Σ σ i i = √SEBUAH A = UΣ VT V SEBUAHTSEBUAH Σ σi i= λsaya( ATA )-------√
Seperti yang Anda ketahui, komponen utama adalah proyeksi ortogonal variabel Anda ke ruang vektor eigen dari matriks kovarians empiris . komponen diberikan oleh nilai eigennya, .λi(11n - 1SEBUAHTSEBUAH λsaya( 1n - 1SEBUAHTA )
Pertimbangkan matriks persegi , dan vektor sedemikian rupa sehingga . Kemudianα ∈ R v B v = λ vB α ∈ R v B v = λ v
Mari kita mendefinisikan . SVD akan menghitung komposisi eigend dari untuk menghasilkanSSTS=1S= 1n - 1SEBUAHTSEBUAH S STS= 1( n - 1 )2SEBUAHTA ATSEBUAH
Voa!
Mengenai stabilitas numerik, orang perlu mencari tahu apa alogritma yang digunakan. Jika Anda mau, saya percaya ini adalah rutinitas LAPACK yang digunakan oleh numpy:
Pembaruan: Pada stabilitas, implementasi SVD tampaknya menggunakan pendekatan divide-and-conquer, sedangkan komposisi eigend menggunakan algoritma QR polos. Saya tidak dapat mengakses beberapa makalah SIAM yang relevan dari institusi saya (menyalahkan pemotongan penelitian) tetapi saya menemukan sesuatu yang dapat mendukung penilaian bahwa rutin SVD lebih stabil.
Di
mereka membandingkan stabilitas berbagai algoritma nilai eigen, dan tampaknya pendekatan divide-and-conquer (mereka menggunakan yang sama dengan numpy dalam salah satu eksperimen!) lebih stabil daripada algoritma QR. Ini, bersama dengan klaim di tempat lain bahwa metode D&C memang lebih stabil, mendukung pilihan Ng.
sumber
@amoeba memiliki jawaban yang sangat baik untuk pertanyaan PCA, termasuk yang ini tentang hubungan SVD ke PCA. Menjawab pertanyaan persis Anda, saya akan membuat tiga poin:
Ternyata SVD lebih stabil daripada prosedur dekomoposisi nilai eigen tipikal, terutama, untuk pembelajaran mesin. Dalam pembelajaran mesin, mudah untuk berakhir dengan regresi yang sangat kolinear. SVD bekerja lebih baik dalam kasus ini.
Berikut kode Python untuk menunjukkan maksudnya. Saya membuat matriks data yang sangat collinear, mendapatkan matriks kovariannya dan mencoba untuk mendapatkan nilai eigen dari yang terakhir. SVD masih berfungsi, sementara dekomposisi eigen biasa gagal dalam kasus ini.
Keluaran:
Memperbarui
Menjawab komentar Federico Poloni, inilah kode dengan pengujian stabilitas SVD vs Eig pada 1000 sampel acak dari matriks yang sama di atas. Dalam banyak kasus Eig menunjukkan 0 nilai eigen kecil, yang akan menyebabkan singularitas matriks, dan SVD tidak melakukannya di sini. SVD sekitar dua kali lebih tepat pada penentuan nilai eigen kecil, yang mungkin atau mungkin tidak penting tergantung pada masalah Anda.
Keluaran:
sumber
Untuk pengguna Python, saya ingin menunjukkan bahwa untuk matriks simetris (seperti matriks kovarians), lebih baik menggunakan
numpy.linalg.eigh
fungsi daripadanumpy.linalg.eig
fungsi umum .eigh
9-10 kali lebih cepat daripadaeig
di komputer saya (terlepas dari ukuran matriks) dan memiliki akurasi yang lebih baik (berdasarkan uji akurasi @ Aksakal).Saya tidak yakin dengan demonstrasi manfaat akurasi SVD dengan nilai eigen kecil. Tes @ Aksakal adalah 1-2 urutan besarnya lebih sensitif terhadap keadaan acak daripada algoritma (cobalah merencanakan semua kesalahan alih-alih menguranginya menjadi satu maksimum absolut). Ini berarti bahwa kesalahan kecil dalam matriks kovarians akan memiliki efek yang lebih besar pada akurasi daripada pemilihan algoritma komposisi eigendec. Juga, ini tidak terkait dengan pertanyaan utama, yaitu tentang PCA. Komponen terkecil diabaikan dalam PCA.
Argumen serupa dapat dibuat tentang stabilitas numerik. Jika saya harus menggunakan metode matriks kovarians untuk PCA, saya akan menguraikannya dengan
eigh
bukansvd
. Jika gagal (yang belum didemonstrasikan di sini), maka mungkin Anda perlu memikirkan kembali masalah yang Anda coba selesaikan sebelum mulai mencari algoritma yang lebih baik.sumber
eigh
vseig
.: mail.scipy.org/pipermail/numpy-discussion/2006-March/…Menghitung matriks kovarians dan kemudian melakukan SVD pada yang jauh lebih cepat daripada menghitung SVD pada matriks data lengkap dalam kondisi ini, untuk hasil yang sama.
Bahkan untuk nilai yang cukup kecil, peningkatan kinerja adalah faktor ribuan (milidetik vs detik). Saya menjalankan beberapa tes pada mesin saya untuk membandingkan menggunakan Matlab:
Itu hanya waktu CPU, tetapi kebutuhan penyimpanan sama pentingnya, jika tidak lebih penting. Jika Anda mencoba SVD pada sejuta demi seribu matriks di Matlab, ia akan melakukan kesalahan secara default, karena membutuhkan ukuran larik yang berfungsi yaitu 7.4TB.
sumber