Perbedaan antara Primal, Dual dan Kernel Ridge Regression

Apa perbedaan antara Regresi Primal , Dual dan Kernel Ridge? Orang-orang menggunakan ketiganya, dan karena notasi yang berbeda yang digunakan setiap orang pada sumber yang berbeda sulit untuk saya ikuti.

Jadi bisakah seseorang memberi tahu saya dengan kata-kata sederhana apa perbedaan antara ketiganya? Selain itu apa yang bisa menjadi kelebihan atau kekurangan dari masing-masing, dan apa yang bisa menjadi kompleksitas mereka?

Jawaban singkat: tidak ada perbedaan antara Primal dan Dual - ini hanya tentang cara sampai pada solusi. Regresi ridge kernel pada dasarnya sama dengan regresi ridge biasa, tetapi menggunakan trik kernel untuk menjadi non-linear.

Regresi linier

Pertama-tama, Regresi Linear Least Squares biasa mencoba untuk mencocokkan garis lurus ke set titik data sedemikian rupa sehingga jumlah kesalahan kuadrat minimal.

Kami menetapkan garis yang paling cocok dengan $\mathbb w$ dan untuk setiap titik data $(\mathbf x_i, y_i)$ kami ingin $\mathbf w^T \mathbf x_i \approx y_i$ . Biarkan $e_i = y_i - \mathbf w^T \mathbf x_i$ menjadi kesalahan - jarak antara nilai yang diprediksi dan nilai sebenarnya. Jadi tujuan kami adalah untuk meminimalkan jumlah kesalahan kuadrat $\sum e_i^2 = \| \mathbf e \|^2 = \| X \mathbf w - \mathbf y \|^2$di mana - sebuah matriks data dengan masing-masing menjadi baris, dan vektor dengan semua .$X = \begin{bmatrix} — \mathbf x_1 \,— \\ — \mathbf x_2 \,— \\ \vdots \\ — \mathbf x_n \,— \end{bmatrix}$$\mathbf x_i$$\mathbf y = (y_1 , \ ... \ , y_n)$$y_i$

Dengan demikian, tujuannya adalah , dan solusinya adalah (dikenal sebagai "Persamaan Normal").$\min\limits_{\mathbf w} \| X \mathbf w - \mathbf y \|^2$$\mathbf w = (X^T X)^{-1} X^T \mathbf y$

Untuk data titik yang tak terlihat baru kami memprediksi nya nilai target sebagai .$\mathbf x$y$\hat y$y = w T x$\hat y = \mathbf w^T \mathbf x$

Regresi Punggung

Ketika ada banyak variabel yang berkorelasi dalam model regresi linier, koefisien dapat menjadi buruk ditentukan dan memiliki banyak varian. Salah satu solusi untuk masalah ini adalah untuk membatasi bobot sehingga mereka tidak melebihi beberapa anggaran . Ini setara dengan menggunakan -regularisasi, juga dikenal sebagai "pembusukan berat": itu akan mengurangi varians dengan biaya kadang-kadang kehilangan hasil yang benar (yaitu dengan memperkenalkan beberapa bias).$\mathbf w$$\mathbf w$$C$$L_2$

Tujuannya sekarang menjadi , dengan menjadi parameter regularisasi. Dengan mempelajari matematika, kita mendapatkan solusi berikut: . Ini sangat mirip dengan regresi linier biasa, tetapi di sini kami menambahkan ke setiap elemen diagonal .$\min\limits_{\mathbf w} \| X \mathbf w - y \|^2 + \lambda \, \| \mathbf w \|^2$$\lambda$$\mathbf w = (X^T X + \lambda \, I )^{-1} X^T \mathbf y$$\lambda$$X^T X$

Perhatikan bahwa kita dapat menulis kembali sebagai (lihat di sini untuk detailnya). Untuk titik data baru yang tidak terlihat kami memperkirakan nilai targetnya sebagai . Biarkan . Kemudian .$\mathbf w$$\mathbf w = X^T \, (X X^T + \lambda \, I)^{-1} \mathbf y$x y y = x T w = x T X T$\mathbf x$$\hat y$$\hat y = \mathbf x^T \mathbf w = \mathbf x^T X^T \, (X X^T + \lambda \, I)^{-1} \mathbf y$$\boldsymbol \alpha = (X X^T + \lambda \, I)^{-1} \mathbf y$y = x T X T α = n Σ i = 1$\hat y = \mathbf x^T X^T \boldsymbol \alpha = \sum\limits_{i=1}^{n} \alpha_i \cdot \mathbf x^T \mathbf x_i$

Ridge Regression Dual Form

Kita dapat memiliki pandangan yang berbeda pada tujuan kita - dan mendefinisikan masalah program kuadrat berikut:

$\min\limits_{\mathbf e, \mathbf w} \sum\limits_{i = 1}^n e_i^2$ st untuk dan .$e_i = y_i - \mathbf w^T \mathbf x_i$$i = 1 \, .. \, n$$\| \mathbf w \|^2 \leqslant C$

Ini adalah tujuan yang sama, tetapi dinyatakan agak berbeda, dan di sini batasan pada ukuran adalah eksplisit. Untuk menyelesaikannya, kita mendefinisikan Lagrangian - ini adalah bentuk primal yang berisi variabel primal dan . Kemudian kami mengoptimalkannya wrt dan . Untuk mendapatkan formulasi ganda, kami meletakkan ditemukan dan kembali ke .$\mathbf w$$\mathcal L_p(\mathbf w, \mathbf e ; C)$$\mathbf w$$\mathbf e$$\mathbf e$$\mathbf w$$\mathbf e$$\mathbf w$$\mathcal L_p(\mathbf w, \mathbf e ; C)$

Jadi, . Dengan mengambil turunan wrt dan , kita memperoleh dan . Dengan membiarkan , dan meletakkan dan kembali ke , kita dapat dual Lagrangian$\mathcal L_p(\mathbf w, \mathbf e ; C) = \| \mathbf e \|^2 + \boldsymbol \beta^T (\mathbf y - X \mathbf w - \mathbf e) - \lambda \, (\| \mathbf w \|^2 - C)$$\mathbf w$$\mathbf e$$\mathbf e = \cfrac{1}{2} \boldsymbol \beta$$\mathbf w = \cfrac{1}{2 \lambda} X^T \boldsymbol \beta$$\boldsymbol \alpha = \cfrac{1}{2 \lambda} \boldsymbol \beta$$\mathbf e$$\mathbf w$$\mathcal L_p(\mathbf w, \mathbf e ; C)$$\mathcal L_d(\boldsymbol \alpha, \lambda; C) = -\lambda^2 \| \boldsymbol \alpha \|^2 + 2 \lambda \, \boldsymbol \alpha^T y - \lambda \| X^T \boldsymbol \alpha \| - \lambda C$α α = ( X X T - λ I ) - 1 y λ C λ . Jika kita mengambil turunan wrt , kita mendapatkan - jawaban yang sama dengan regresi Kernel Ridge biasa. Tidak perlu mengambil turunan wrt - itu tergantung pada , yang merupakan parameter regularisasi - dan itu membuat parameter regularisasi juga.$\boldsymbol \alpha$$\boldsymbol \alpha = (XX^T - \lambda I)^{-1} \mathbf y$$\lambda$$C$$\lambda$

Selanjutnya, masukkan ke solusi form primal untuk , dan dapatkan . Dengan demikian, bentuk ganda memberikan solusi yang sama seperti Regresi Ridge biasa, dan itu hanya cara yang berbeda untuk sampai pada solusi yang sama.$\boldsymbol \alpha$$\mathbf w$$\mathbf w = \cfrac{1}{2 \lambda} X^T \boldsymbol \beta = X^T \boldsymbol \alpha$

Regresi Ridge Kernel

Kernel digunakan untuk menghitung produk dalam dari dua vektor di beberapa ruang fitur bahkan tanpa mengunjunginya. Kita dapat melihat kernel sebagai , walaupun kita tidak tahu apa - kita hanya tahu itu ada. Ada banyak kernel, misalnya RBF, Polynonial, dll.$k$$k(\mathbf x_1, \mathbf x_2) = \phi(\mathbf x_1)^T \phi(\mathbf x_2)$$\phi(\cdot)$

Kita dapat menggunakan kernel untuk membuat Regresi Punggung kita menjadi non-linear. Misalkan kita memiliki kernel . Biarkan menjadi matriks di mana setiap baris adalah , yaitu$k(\mathbf x_1, \mathbf x_2) = \phi(\mathbf x_1)^T \phi(\mathbf x_2)$$\Phi(X)$$\phi(\mathbf x_i)$$\Phi(X) = \begin{bmatrix} — \phi(\mathbf x_1) \,— \\ — \phi(\mathbf x_2) \,— \\ \vdots \\ — \phi(\mathbf x_n) \,— \end{bmatrix}$

Sekarang kita bisa mengambil solusi untuk Regresi Ridge dan mengganti setiap dengan : . Untuk titik data baru yang tidak terlihat kami memperkirakan nilai targetnya sebagai .$X$$\Phi(X)$$\mathbf w = \Phi(X)^T \, (\Phi(X) \Phi(X)^T + \lambda \, I)^{-1} \mathbf y$$\mathbf x$$\hat y$$\hat y= \mathbf \phi(\mathbf x)^T \Phi(X)^T \, (\Phi(X) \Phi(X)^T + \lambda \, I)^{-1} \mathbf y$

Pertama, kita dapat mengganti dengan matriks , dihitung sebagai . Kemudian, adalah . Jadi di sini kami berhasil mengekspresikan setiap titik produk dari masalah dalam hal kernel.$\Phi(X) \Phi(X)^T$$K$$(K)_{ij} = k(\mathbf x_i, \mathbf x_j)$$\phi(\mathbf x)^T \Phi(X)^T$$\sum\limits_{i = 1}^n \phi(\mathbf x)^T \phi(\mathbf x_i) = \sum\limits_{i = 1}^n k(\mathbf x, \mathbf x_j)$

Akhirnya, dengan membiarkan (seperti sebelumnya), kita memperoleh$\boldsymbol \alpha = (K + \lambda \, I)^{-1} \mathbf y$$\hat y= \sum\limits_{i = 1}^n \alpha_i k(\mathbf x, \mathbf x_j)$

Referensi

• Kelas Machine Learning I di TU Berlin
• Elemen Pembelajaran Statistik, http://statweb.stanford.edu/~tibs/ElemStatLearn/
• http://0agr.ru/wiki/index.php/Normal_Equation
• http://stat.wikia.com/wiki/Kernel_Ridge_Regression
• http://stat.rutgers.edu/home/tzhang/papers/ml02_dual.pdf
• http://www.ics.uci.edu/~welling/classnotes/papers_class/Kernel-Ridge.pdf
• http://www.cs.nyu.edu/~mohri/mls/lecture_8.pdf