Fungsi objektif PCA: apa hubungan antara memaksimalkan varians dan meminimalkan kesalahan?

Algoritma PCA dapat dirumuskan dalam bentuk matriks korelasi (anggap data telah dinormalisasi dan kami hanya mempertimbangkan proyeksi ke PC pertama). Fungsi objektif dapat ditulis sebagai: $X$

max_{w} (X w)^{T} (X w) s.t. w^{T} w = 1.

$\max_w (Xw)^T(Xw)\; \: \text{s.t.} \: \:w^Tw = 1.$

Ini bagus, dan kami menggunakan pengganda Lagrangian untuk menyelesaikannya, yaitu menulis ulang sebagai:

max_{w} [(X w)^{T} (X w) - λ w^{T} w],

$\max_w [(Xw)^T(Xw) - \lambda w^Tw],$

yang setara dengan

max_{w} \frac{(X w)^{T} (X w)}{w^{T} w},

$\max_w \frac{ (Xw)^T(Xw) }{w^Tw},$

dan karenanya ( lihat di sini di Mathworld ) tampaknya sama dengan

max_{w} \sum_{i = 1}^{n} {(distance from point x_{i} to line w)}^{2} .

$\max_w \sum_{i=1}^n \text{(distance from point $x_i$ to line $w$)}^2.$

Tapi ini mengatakan untuk memaksimalkan jarak antara titik dan garis, dan dari apa yang saya baca di sini , ini tidak benar - seharusnya $\min$ , bukan $\max$ . Di mana kesalahan saya?

Atau, dapatkah seseorang menunjukkan kepada saya hubungan antara memaksimalkan varians dalam ruang yang diproyeksikan dan meminimalkan jarak antara titik dan garis?

pca optimization Cam.Davidson.Pilon
sumber

Saya pikir jarak minimum digunakan untuk memenuhi kriteria orthogonality untuk komponen. Poin diproyeksikan ke PC yang ortogonal satu sama lain tetapi dalam setiap komponen berturut-turut varians yang tersisa dimaksimalkan.

Michael R. Chernick

Petunjuk: Apa yang terjadi ketika Anda mempertimbangkan nilai eigen terkecil terlebih dahulu, bukan yang terbesar?

whuber

@whuber Nilai eigen terkecil mungkin memiliki PC yang merupakan solusi untuk fungsi tujuan akhir. Namun PC ini tidak memaksimalkan fungsi tujuan semula.

Cam.Davidson.Pilon

Saya tidak yakin apa yang Anda maksud dengan fungsi tujuan "final" dan "asli", Cam. PCA bukan (secara konseptual) program optimasi. Keluarannya adalah sekumpulan arahan pokok, bukan hanya satu. Ini adalah teorema matematika (menarik) bahwa arah ini dapat ditemukan dengan memecahkan urutan program kuadratik terbatas, tetapi itu tidak mendasar untuk konsep atau praktik PCA. Saya hanya menyarankan bahwa, dengan memfokuskan pada nilai eigen terkecil daripada yang terbesar, Anda dapat merekonsiliasi dua gagasan (1) meminimalkan jarak dan (2) mengambil pandangan optimasi PCA.

whuber

Tidak apa-apa - jawaban Anda adalah versi non-kesalahan dari apa yang saya coba lakukan.

Cam.Davidson.Pilon

Jawaban:

Biarkan menjadi matriks data terpusat dengan pengamatan dalam baris. Biarkan menjadi matriks kovariansnya. Biarkan menjadi vektor satuan yang menentukan sumbu dalam ruang variabel. Kami ingin menjadi sumbu utama pertama. $\newcommand{\X}{\mathbf X}\X$ $n$ $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

Menurut pendekatan pertama, sumbu utama pertama memaksimalkan varians dari proyeksi (varians dari komponen utama pertama). Varians ini diberikan oleh $\X \w$

V a r (X w) = w^{⊤} X^{⊤} X w / (n - 1) = w^{⊤} Σ w .

$\mathrm{Var}(\X\w)=\w^\top\X^\top \X \w/(n-1)=\w^\top\S\w.$

Menurut pendekatan kedua, poros utama pertama meminimalkan kesalahan rekonstruksi antara dan rekonstruksinya , yaitu jumlah jarak kuadrat antara titik asli dan proyeksi mereka ke . Kuadrat kesalahan rekonstruksi diberikan oleh $\X$ $\X\w\w^\top$ $\w$

\begin{aligned} ‖ X - X w w^{⊤} ‖^{2} & = t r ((X - X w w^{⊤}) (X - X w w^{⊤})^{⊤}) \\ = t r ((X - X w w^{⊤}) (X^{⊤} - w w^{⊤} X^{⊤})) \\ = t r (X X^{⊤}) - 2 t r (X w w^{⊤} X^{⊤}) + t r (X w w^{⊤} w w^{⊤} X^{⊤}) \\ = c Hai n s t - t r (X w w^{⊤} X^{⊤}) \\ = c Hai n s t - t r (w^{⊤} X^{⊤} X w) \\ = c Hai n s t - c Hai n s t \cdot w^{⊤} Σ w . \end{aligned}

$\begin{align}\newcommand{\tr}{\mathrm{tr}} \|\X-\X\w\w^\top\|^2 &=\tr\left((\X-\X\w\w^\top)(\X-\X\w\w^\top)^\top\right) \\ &=\tr\left((\X-\X\w\w^\top)(\X^\top-\w\w^\top\X^\top)\right) \\ &=\tr(\X\X^\top)-2\tr(\X\w\w^\top\X^\top)+\tr(\X\w\w^\top\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\X\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\w^\top\X^\top\X\w) \\ &=\mathrm{const} - \mathrm{const} \cdot \w^\top \S \w. \end{align}$

Perhatikan tanda minus sebelum istilah utama. Karena itu, meminimalkan jumlah kesalahan rekonstruksi untuk memaksimalkan , yang merupakan varians. Jadi meminimalkan kesalahan rekonstruksi sama dengan memaksimalkan varians; kedua formulasi menghasilkan sama . $\w^\top \S \w$ $\w$

amuba kata Reinstate Monica
sumber

Sesuatu yang saya perhatikan, bukan fungsi cembung (Sehubungan dengan sebagai adalah PSD? Bagaimana kita mencoba memaksimalkannya?

w^{T} Σ w

${w}^{T} \Sigma w$

w

$w$

Σ

$\Sigma$

Royi

@amoeba dapatkah Anda menjelaskan bagaimana Anda beralih dari tr () ke const di langkah terakhir?

alberto

@alberto Apa yang ada di dalam jejak adalah angka (1x1 matriks); jejak nomor adalah nomor ini sendiri, sehingga jejak dapat dihapus. Konstanta muncul karena sama dengan , jadi ada faktor .

Σ

$\Sigma$

X^{⊤} X / n

$X^\top X/n$

1 / n

$1/n$

Amuba kata Reinstate Monica

@Leullame Perhitungan akan menampung kata demi kata untuk jika merupakan matriks dengan kolom ortonormal. Anda perlu untuk beralih dari baris # 3 ke baris # 4. Jika matriks memiliki kolom ortonormal, maka memang akan menjadi proyeksi ke subruang yang direntang oleh kolom (di sini adalah vektor baris).

W

$W$

W^{⊤} W = I

$W^\top W = I$

W

$W$

x W W^{⊤}

$xWW^\top$

x

$x$

W

$W$

x

$x$

Amuba kata Reinstate Monica

@ DanielLópez Nah, kami sedang mencari subruang 1 dimensi yang meminimalkan kesalahan rekonstruksi. Subruang 1-dimensi dapat didefinisikan oleh vektor satuan-norma yang menunjuk ke arahnya, yang menjadi . Ini memiliki norma satuan dengan konstruksi.

w

$w$

Amuba kata Reinstate Monica