Apa fungsi objektif PCA?

Analisis komponen utama dapat menggunakan dekomposisi matriks, tetapi itu hanya alat untuk sampai ke sana.

Bagaimana Anda menemukan komponen utama tanpa menggunakan aljabar matriks?

Apa fungsi objektif (goal), dan apa saja kendalanya?

pca Neil McGuigan
sumber

Mungkin saya kehilangan sesuatu, jadi tolong perbaiki saya jika saya salah, tetapi harus dimungkinkan (setidaknya pada prinsipnya) untuk membangun apa yang dilakukan dalam PCA menggunakan matriks sebagai masalah pemrograman linear (rumit), tapi saya tidak tahu bagaimana Anda akan menyatakan semua kendala yang diperlukan. Juga saya tidak yakin itu akan sangat sederhana untuk dilakukan dibandingkan dengan hanya menggunakan PCA. Mengapa Anda mencoba menghindari matriks?

Chris Simokat

@ Chris Saya tidak melihat bagaimana orang bisa mendapatkan masalah pemrograman linier. Bukan pemahaman saya juga bahwa matriks harus dihindari dalam perhitungan . Pertanyaannya adalah masalah apa yang dipecahkan oleh PCA, dan bukan bagaimana hal itu dilakukan (dengan menghitung SVD misalnya). Solusi oleh kardinal mengatakan bahwa Anda menemukan arah ortogonal berurutan dari varian maksimal . Solusi yang saya sajikan mengatakan bahwa Anda menemukan hyperplanes dengan kesalahan rekonstruksi minimal.

NRH

@ Chris Saya berharap menemukan cara lain untuk melihat PCA, tanpa aljabar matriks, untuk menambah pemahaman saya tentang PCA.

Neil McGuigan

@ Chris, Anda memiliki fungsi tujuan kuadratik dan batasan kesetaraan norma . Atau, di bawah formulasi dalam jawaban @ NRH, Anda memiliki batasan peringkat matriks. Itu tidak akan mengalahkan dirinya sendiri ke masalah pemrograman linier. @NRH memberikan intuisi yang baik, dan, pada kenyataannya, ada hubungan yang sangat dekat antara kedua perspektif pada PCA yang telah diberikan. Mungkin bekerja sama dengan @NRH, kita dapat menambahkannya ke posnya untuk membuat set lengkap jawaban lebih lengkap.

ℓ_{2}

$\ell_2$

kardinal

@NRH, Sebenarnya, saya sangat suka ESL , tapi saya pikir perawatan di sana dari topik ini cukup dangkal, karena itu untuk banyak topik dalam buku ini. Secara khusus, mereka tidak membuktikan (atau bahkan menetapkan sebagai latihan) bagian penting dari solusi untuk masalah optimasi yang Anda berikan.

kardinal

Jawaban:

Tanpa mencoba memberikan primer penuh pada PCA, dari sudut pandang optimisasi, fungsi tujuan utama adalah hasil bagi Rayleigh . Matriks yang angka dalam hasil bagi adalah (beberapa kelipatan) dari sampel matriks kovarians dimana setiap adalah vektor fitur dan adalah matriks sehingga baris th adalah .

S = \frac{1}{n} \sum_{i = 1}^{n} x_{i} x_{i}^{T} = X^{T} X / n

$\newcommand{\m}[1]{\mathbf{#1}}\newcommand{\x}{\m{x}}\newcommand{\S}{\m{S}}\newcommand{\u}{\m{u}}\newcommand{\reals}{\mathbb{R}}\newcommand{\Q}{\m{Q}}\newcommand{\L}{\boldsymbol{\Lambda}} \S = \frac{1}{n} \sum_{i=1}^n \x_i \x_i^T = \m{X}^T \m{X} / n$

x_{i}

$\x_i$

p

$p$

X

$\m{X}$

i

$i$

x_{i}^{T}

$\x_i^T$

PCA berupaya memecahkan serangkaian masalah optimisasi. Yang pertama dalam urutan adalah masalah yang tidak dibatasi

\begin{array}{ll} maximize & \frac{u^{T} S u}{u^{T} u}, u \in R^{p} . \end{array}

$\begin{array}{ll} \text{maximize} & \frac{\u^T \S \u}{\u^T\u} \;, \u \in \reals^p \> . \end{array}$

Karena, masalah yang tidak dibatasi di atas setara dengan masalah yang dibatasi $\u^T \u = \|\u\|_2^2 = \|\u\| \|\u\|$

\begin{array}{ll} maximize & u^{T} S u \\ subject to & u^{T} u = 1 . \end{array}

$\begin{array}{ll} \text{maximize} & \u^T \S \u \\ \text{subject to} & \u^T \u = 1 \>. \end{array}$

Di sinilah aljabar matriks masuk. Karena adalah matriks semidefinit positif simetris (dengan konstruksi!) Ia memiliki dekomposisi nilai eigen dari bentuk mana adalah matriks ortogonal (jadi ) dan adalah matriks diagonal dengan entri tidak negatif sedemikian rupa sehingga . $\S$

S = Q Λ Q^{T},

$\S = \Q \L \Q^T \>,$

Q

$\Q$

Q Q^{T} = I

$\Q \Q^T = \m{I}$

Λ

$\L$

λ_{i}

$\lambda_i$

λ_{1} \geq λ_{2} \geq \dots \geq λ_{p} \geq 0

$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_p \geq 0$

Oleh karena itu, . Karena dibatasi dalam masalah untuk memiliki norma satu, maka begitu pula karena , berdasarkan menjadi ortogonal. $\u^T \S \u = \u^T \Q \L \Q^T \u = \m{w}^T \L \m{w} = \sum_{i=1}^p \lambda_i w_i^2$ $\u$ $\m{w}$ $\|\m{w}\|_2 = \|\Q^T \u\|_2 = \|\u\|_2 = 1$ $\Q$

Tetapi, jika kita ingin memaksimalkan kuantitas bawah batasan yang , maka yang terbaik yang bisa kita lakukan adalah dengan set , yaitu, dan untuk . $\sum_{i=1}^p \lambda_i w_i^2$ $\sum_{i=1}^p w_i^2 = 1$ $\m{w} = \m{e}_1$ $w_1 = 1$ $w_i = 0$ $i > 1$

Sekarang, dengan mencocokkan yang sesuai , yang merupakan tujuan kami, kami mendapatkan bahwa mana menunjukkan kolom pertama dari , yaitu, eigenvector sesuai dengan nilai eigen terbesar dari . Nilai fungsi objektif kemudian juga mudah dilihat sebagai . $\u$

u^{⋆} = Q e_{1} = q_{1}

$\u^\star = \Q \m{e}_1 = \m{q}_1$

q_{1}

$\m{q}_1$

Q

$\Q$

S

$\S$

λ_{1}

$\lambda_1$

Vektor komponen utama yang tersisa kemudian ditemukan dengan menyelesaikan urutan (diindeks oleh ) dari masalah optimasi Jadi, masalahnya sama, kecuali bahwa kita menambahkan batasan tambahan bahwa solusi harus ortogonal untuk semua solusi sebelumnya dalam urutan. Hal ini tidak sulit untuk memperpanjang argumen di atas induktif untuk menunjukkan bahwa solusi dari masalah th, memang, , yang th eigenvector dari . $i$

\begin{array}{ll} maximize & u_{i}^{T} S u_{i} \\ subject to & u_{i}^{T} u_{i} = 1 \\ u_{i}^{T} u_{j} = 0 \forall 1 \leq j < i . \end{array}

$\begin{array}{ll} \text{maximize} & \u_i^T \S \u_i \\ \text{subject to} & \u_i^T \u_i = 1 \\ & \u_i^T \u_j = 0 \quad \forall 1 \leq j < i\>. \end{array}$

i

$i$

q_{i}

$\m{q}_i$

i

$i$

S

$\S$

Solusi PCA juga sering dinyatakan dalam dekomposisi nilai singular dari . Untuk melihat mengapa, biarkan . Kemudian dan begitu (sebenarnya, hingga tanda membalik) dan . $\m{X}$ $\m{X} = \m{U} \m{D} \m{V}^T$ $n \S = \m{X}^T \m{X} = \m{V} \m{D}^2 \m{V}^T$ $\m{V} = \m{Q}$ $\L = \m{D}^2 / n$

Komponen utama ditemukan dengan memproyeksikan ke vektor komponen utama. Dari formulasi SVD yang baru saja diberikan, mudah untuk melihat bahwa $\m{X}$

X Q = X V = U D V^{T} V = U D .

$\m{X} \m{Q} = \m{X} \m{V} = \m{U} \m{D} \m{V}^T \m{V} = \m{U} \m{D} \> .$

Kesederhanaan representasi dari kedua vektor komponen utama dan komponen utama itu sendiri dalam hal SVD dari matriks fitur adalah salah satu alasan fitur SVD begitu menonjol dalam beberapa perawatan PCA.

kardinal
sumber

Jika hanya beberapa nilai / vektor singular pertama yang diperlukan, Nash dan Shlien memberikan algoritma yang mengingatkan pada metode daya biasa untuk menghitung nilai eigen dominan. Ini mungkin menarik bagi OP.

JM bukan ahli statistik

@NRH, Terima kasih telah menangkap (dan memperbaiki) kesalahan ketik saya sebelum saya berhasil melihatnya!

kardinal

Hai @ cardinal, terima kasih atas jawaban Anda. Tetapi tampaknya Anda tidak memberikan langkah untuk membuktikan mengapa pengoptimalan berurutan mengarah ke optimal global. Bisakah Anda menjelaskannya? Terima kasih!

Lifu Huang

Solusi yang disajikan oleh kardinal berfokus pada matriks kovarian sampel. Titik awal lainnya adalah kesalahan rekonstruksi data dengan hyperplane q- dimensional. Jika titik data p- dimensi adalah tujuannya adalah untuk menyelesaikannya $x_1, \ldots, x_n$

min_{μ, λ_{1}, \dots, λ_{n}, V_{q}} \sum_{i = 1}^{n} | | x_{i} - μ - V_{q} λ_{i} | |^{2}

$\min_{\mu, \lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n ||x_i - \mu - \mathbf{V}_q \lambda_i||^2$

untuk matriks dengan kolom ortonormal dan . Ini memberikan peringkat q- rekonstruksi terbaik yang diukur dengan norma euclidean, dan kolom dari solusi adalah vektor komponen q utama. $p \times q$ $\mathbf{V}_q$ $\lambda_i \in \mathbb{R}^q$ $\mathbf{V}_q$

Untuk fix solusi untuk dan (ini adalah regresi) adalah $\mathbf{V}_q$ $\mu$ $\lambda_i$

μ = \bar{x} = \frac{1}{n} \sum_{i = 1}^{n} x_{i} λ_{i} = V_{q}^{T} (x_{i} - \bar{x})

$\mu = \overline{x} = \frac{1}{n}\sum_{i=1}^n x_i \qquad \lambda_i = \mathbf{V}_q^T(x_i - \overline{x})$

Untuk kemudahan notasi mari kita asumsikan bahwa telah dipusatkan dalam perhitungan berikut. Kami kemudian harus meminimalkan $x_i$

\sum_{i = 1}^{n} | | x_{i} - V_{q} V_{q}^{T} x_{i} | |^{2}

$\sum_{i=1}^n ||x_i - \mathbf{V}_q\mathbf{V}_q^T x_i||^2$

lebih dengan kolom ortonormal. Perhatikan bahwa adalah proyeksi ke ruang kolom q- dimensi. Karenanya masalahnya sama dengan meminimalkan lebih rank q proyeksi . Artinya, kita perlu memaksimalkan atas peringkat q proyeksi , di mana adalah matriks kovarians sampel. Sekarang $\mathbf{V}_q$ $P = \mathbf{V}_q\mathbf{V}_q^T$

\sum_{i = 1}^{n} | | x_{i} - P x_{i} | |^{2} = \sum_{i = 1}^{n} | | x_{i} | |^{2} - \sum_{i = 1}^{n} | | P x_{i} | |^{2}

$\sum_{i=1}^n ||x_i - P x_i||^2 = \sum_{i=1}^n ||x_i||^2 - \sum_{i=1}^n||Px_i||^2$

P

$P$

\sum_{i = 1}^{n} | | P x_{i} | |^{2} = \sum_{i = 1}^{n} x_{i}^{T} P x_{i} = tr (P \sum_{i = 1}^{n} x_{i} x_{i}^{T}) = n tr (P S)

$\sum_{i=1}^n||Px_i||^2 = \sum_{i=1}^n x_i^TPx_i = \text{tr}(P \sum_{i=1}^n x_i x_i^T) = n \text{tr}(P \mathbf{S})$

P

$P$

S

$\mathbf{S}$

tr (P S) = tr (V_{q}^{T} S V_{q}) = \sum_{i = 1}^{q} u_{i}^{T} S u_{i}

$\text{tr}(P\mathbf{S}) = \text{tr}(\mathbf{V}_q^T\mathbf{S}\mathbf{V}_q) = \sum_{i=1}^q u_i^T \mathbf{S} u_i$ mana adalah kolom (ortonormal) dalam , dan argumen yang disajikan dalam jawaban @ cardinal menunjukkan bahwa maksimum diperoleh dengan mengambil ' s untuk menjadi vektor eigen untuk dengan eigen terbesar.

u_{1}, \dots, u_{q}

$u_1, \ldots, u_q$

q

$q$

V_{q}

$\mathbf{V}_q$

u_{i}

$u_i$

q

$q$

S

$\mathbf{S}$

q

$q$

Kesalahan rekonstruksi menunjukkan sejumlah generalisasi yang bermanfaat, misalnya komponen utama yang jarang atau rekonstruksi dengan manifold berdimensi rendah alih-alih hyperplanes. Untuk detailnya, lihat Bagian 14.5 di Elemen Pembelajaran Statistik .

NRH
sumber

(+1) Poin bagus. Beberapa saran: Akan bagus untuk mendefinisikan dan akan sangat menyenangkan untuk memberikan bukti singkat dari hasilnya. Atau, sebagai alternatif, dapat dihubungkan ke masalah optimisasi yang melibatkan negosiasi Rayleight. Saya pikir itu akan membuat jawaban untuk pertanyaan ini sangat lengkap!

λ_{i}

$\lambda_i$

kardinal

@ cardinal, saya yakin saya telah menyelesaikan langkah-langkah yang hilang dari perumusan rekonstruksi ke masalah yang Anda selesaikan.

NRH

Kerja bagus. Saya percaya satu-satunya celah yang tersisa adalah dalam pernyataan terakhir Anda. Tidak segera jelas bahwa mengoptimalkan jumlah sama dengan melakukan urutan optimasi dalam jawaban saya. Sebenarnya, saya tidak mengira secara langsung, secara umum. Tapi, itu juga tidak perlu dibahas di sini.

kardinal

@ kardinal, diikuti oleh induksi. Anda memberikan awal induksi, dan pada langkah induksi pilih vektor ortonormal yang memaksimalkan jumlah dan mengaturnya sehingga adalah vektor satuan ortogonal untuk . Kemudian dengan hasil Anda dan dengan asumsi induksi . Tentu saja, dasarnya bukan basis yang unik untuk ruang dimensi- . Anda juga dapat menggeneralisasi "argumen kombinasi cembung" yang Anda gunakan untuk memberikan bukti langsung.

w_{1}, \dots, w_{q}

$w_1, \ldots, w_q$

w_{q}

$w_q$

u_{1}, \dots, u_{q - 1}

$u_1, \ldots, u_{q-1}$

w_{q}^{T} S w_{q} \leq u_{q}^{T} S u_{q}

$w_q^T \mathbf{S} w_q \leq u_q^T \mathbf{S} u_q$

\sum_{i = 1}^{q - 1} w_{i}^{T} S w_{i} \leq \sum_{i = 1}^{q - 1} u_{i}^{T} S u_{i}

$\sum_{i=1}^{q-1} w_i^T \mathbf{S} w_i \leq \sum_{i=1}^{q-1}u_i^T \mathbf{S} u_i$

q

$q$

NRH

@ cardinal, saya tidak memaksa bersarang, hanya menggunakan pertimbangan dimensi. Jika kita memiliki subruang -dimensi Anda selalu dapat memilih dalam ruang itu sedemikian rupa sehingga ia ortogonal ke subruang -dimensi. Kemudian Anda mengisi -basis cara apapun yang Anda suka.

q

$q$

w_{q}

$w_q$

(q - 1)

$(q-1)$

w

$w$

NRH

Lihat NIPALS ( wiki ) untuk satu algoritma yang tidak secara eksplisit menggunakan dekomposisi matriks. Saya kira itu yang Anda maksud ketika Anda mengatakan bahwa Anda ingin menghindari aljabar matriks karena Anda benar-benar tidak dapat menghindari aljabar matriks di sini :)

JMS
sumber