Fast Domain Generalization with Kernel Methods – Part 3 (PCA, KPCA, TCA)


Walaupun teori tentang Principal Component Analysis (PCA) dari sudut pandang statistics ataupun information theory dapat ditelusuri hingga tahun 1901, penggunaannya secara praktis dimulai pada tahun 1980an seiring dengan perkembangan teknologi komputer. Saat ini PCA merupakan metode yang sangat populer di berbagai bidang seperti signal processing, neurosciencemachine learning, finance, hingga ke social science. Secara umum, PCA digunakan untuk mencari atau menganalisis pola dari data yang berdimensi banyak. Salah satu hal yang disukai dari PCA adalah proses komputasi yang relatif efisien.

Di berbagai aplikasi, seringkali kumpulan data yang berdimensi banyak dapat dijelaskan hanya dengan beberapa variabel saja (mulai saat ini kita sebut variabel tsb dengan istilah variabel latent). Ambil contoh kasus heart disease prediction untuk mendeteksi apakah seseorang mengidap penyakit jantung diberikan sejumlah variabel. Terdapat 76 variabel yang perlu dianalisis dimulai dari usia, jenis kelamin, tekanan darah, detak jantung, dsb. Pertanyaan yang sering diajukan pertama kali adalah mampukah prediksi tersebut dilakukan dengan menggunakan lebih sedikit variabel dengan hanya memilih variabel-variabel paling informatif ? Hal ini mungkin dilakukan secara manual oleh human experts. Namun demikian, akan lebih elegan apabila komputer dapat mengidentifikasi variabel latent secara otomatis. Di Machine Learning, permasalahan ini dikaji secara intensif dalam sub-bidang yang dikenal sebagai Dimensionality Reduction.

Saat ini PCA telah berkembang menjadi berbagai bentuk. Pada kesempatan kali ini saya coba bermain-main dengan PCA beserta 2 variannya: Kernel Principal Component Analysis (KPCA) dan  Transfer Component Analysis (TCA). Yang terakhir ini khusus dirancang untuk aplikasi transfer learning / domain adaptation.

1. MEAN, variance & Covariance

Mean (nilai rata-rata), variance (varians), dan covariance (kovarians) merupakan istilah yang sudah tidak asing lagi bagi yang sudah mempelajari dasar statistika. Kali ini saya fokuskan pada konteks dimana variabel random berbentuk vektor dan diskrit.

Diberikan sebuah vektor random diskrit \mathbf{X}^{(i)} = [ X^{(i)}_1, ...., X^{(i)}_d]^{\top} \in \mathbb{R}^{d}, \forall i = 1,...,N dimana masing-masing elemennya merupakan variabel random. Berikut ini definisi dari masing-masing istilah:

Mean

Mean dari sebuah vektor random berisi nilai rata-rata dari masing-masing elemennya yang didefinisikan sebagai berikut

\displaystyle \vec{\mu}_{\mathbf{X}}=[\mu_{X_1},...,\mu_{X_d}]^{\top}=\frac{1}{N}\sum_{i=1}^{N}\mathbf{X}^{(i)},

dimana \mu_{X} merupakan nilai rata-rata dari variabel random.

Variance

Variance dari sebuah variabel random X didefinisikan sebagai berikut

\displaystyle \mathrm{cov}(X) = \mu_{X^2} - (\mu_X) (\mu_X).

Besaran ini mengukur seberapa jauh posisi data tersebar terhadap nilai rata-rata.

Jika input dari variance berupa vektor random, maka bentuknya adalah berupa vektor

\displaystyle \mathrm{Var}(\mathbf{X})=[\mu_{X^2_1} - (\mu_{X_1})^2, ..., \mu_{X^2_d} - (\mu_{X_d})^2]^{\top}

\displaystyle =[\mathrm{var}(X_1),...,\mathrm{cov}(X_d)]^{\top}

dimana masing-masing elemen dari \mathrm{Var}(\mathbf{X}) \in \mathbb{R}^d merupakan varians dari variabel random.

COVARIANCE

Diberikan 2 buah variabel random, covariance mengukur bagaimana perubahan nilai dari 2 variabel tersebut. Jika variabel-variabel tersebut sama-sama naik atau turun, maka covariance bernilai positif. Bentuk dasar dari covariance adalah

\displaystyle \mathrm{cov}(X,Y) = \mu_{XY} - \mu_X \mu_Y,

dimana X, Y merupakan variabel random. Perhatikan bahwa jika X = Y, maka \mathrm{cov}(X,X) = \mathrm{var}(X).

Jika input dari covariance berupa sebuah vektor random \mathbf{X} \in \mathbb{R}^{d}, maka kita akan mendapatkan matriks covariance

\displaystyle \mathrm{Cov}(\mathbf{X}) = \begin{bmatrix} \mathrm{var}(X_1) & \mathrm{cov}(X_1, X_2) & ... & \mathrm{cov}(X_1,X_d) \\ \mathrm{cov}(X_2,X_1) & \mathrm{var}(X_2) & .... & \mathrm{cov}(X_2,X_d) \\ . & . & ... & . \\ . & . & ... & . \\ \mathrm{cov}(X_d,X_1) & \mathrm{cov}(X_d,X_2) &...&\mathrm{var}(X_d)\end{bmatrix}\quad \quad \quad (1)

dimana elemen-elemen diagonal dari \mathrm{Cov}(\mathbf{X}) \in \mathbb{R}^{d \times d} berupa variance dan elemen-elemen non-diagonal berupa covariance dari variabel random. Perhatikan bahwa matriks \mathrm{Cov}(\mathbf{X}) selalu simetris.

2. Principal Component Analysis

Ide utama dari PCA adalah menemukan komponen atau koordinat dari suatu himpunan data dengan persebaran/varians maksimum. Mengapa varians maksimum? Secara intuitif, hubungan geometris dari komponen-komponen dengan variasi maksimum merupakan aproksimasi terdekat dari hubungan geometris dari sampel sebenarnya (hubungan geometris = jarak antar sampel).

Misal terdapat n buat data vektor \{ \mathbf{x}^{(i)}\}_{i=1}^{n} dimana \mathbf{x}^{(i)} \in \mathbb{R}^{d}. Tanpa mengurangi generalitas, kita asumsikan \boldsymbol{\mu}_{\mathbf{x}} = \frac{1}{n}\sum_{i=1}^{n} \mathbf{x}^{(i)}=\mathbf{0}. Dari himpunan tersebut dapat dibentuk sebuah matriks \mathbf{X} \in \mathbb{R}^{n \times d} dimana baris ke-i dari \mathbf{X} berisi \mathbf{x}^{(i)\top}. Dari sini cukup mudah untuk melihat bahwa matriks covariance pada persamaan (1) ekuivalen dengan persamaan di bawah ini:

\displaystyle \mathbf{C}_{\mathbf{x}} = \frac{1}{n} \sum_{i=1}^{n} \mathbf{x}^{(i)} \mathbf{x}^{(i) \top} = \frac{1}{n}\mathbf{X}^{\top} \mathbf{X}\quad \quad \quad (2)

Tujuan utama dari PCA adalah mencari komponen-komponen yang berupa vektor koordinat. Misal terdapat k buah komponen \mathbf{w}_1, ..., \mathbf{w}_k dimana \mathbf{w}_l \in \mathbb{R}^{d} dan k < d. Dari komponen tersebut kita dapat menghitung k buah variabel latent dari data \mathbf{x}^{(i)} melalui kombinasi linear dengan tiap-tiap komponen sebagai berikut:

\displaystyle \mathbf{w}_1^{\top} \mathbf{x}^{(i)} = z^{(i)}_1

\displaystyle \mathbf{w}_2^{\top} \mathbf{x}^{(i)} = z^{(i)}_2

….

\displaystyle \mathbf{w}_k^{\top} \mathbf{x}^{(i)} = z^{(i)}_k

Definisikan persamaan variance dari komponen z_l

\displaystyle \mathrm{Var}(z_l)=\frac{1}{n} \sum_{i=1}^{n} z^{(i)}_l z^{(i)}_l = \frac{1}{n}\sum_{i=1}^{n} \mathbf{w}_l^{\top} \mathbf{x}^{(i)} \mathbf{x}^{(i) \top} \mathbf{w}_l

= \mathbf{w}_l^{\top} \mathbf{C}_{\mathbf{x}} \mathbf{w}_l \quad \quad \quad (3)

Objektif dari PCA adalah mencari principal component \mathbf{w}_1 yang membuat persamaan (3) bernilai maksimum:

\displaystyle \max_{\mathbf{w}_l} \mathbf{w}_l^{\top} \mathbf{C}_{\mathbf{x}} \mathbf{w}_l \quad \text{s.t.} \quad \| \mathbf{w}_l \|_2^2 = 1 \quad \quad \quad (4)

dimana constraint \| \mathbf{w}_l \|_2^2 = \mathbf{w}_l^{\top} \mathbf{w}_l digunakan untuk menjamin agar panjang komponen selalu 1 (normal vector).

Problem (4) dapat diselesaikan secara analitis dengan menggunakan turunan pertama dari fungsi objektif. Pertama-tama kita tulis fungsi objektif dalam bentuk Lagrangian sebagai berikut:

\displaystyle J(\mathbf{w}_l)=\mathbf{w}^{\top}_l \mathbf{C}_{\mathbf{x}} \mathbf{w}_l-\lambda(\mathbf{w}^{\top}_l \mathbf{w}_l - 1) \quad \quad \quad (5)

dimana \lambda \neq 0 merupakan Lagrage multiplier. Lalu hitung turunan pertama dari fungsi (5) terhadap \mathbf{w}_l yang hasilnya sama dengan 0

\displaystyle \frac{\partial J(\mathbf{w}_l)}{\partial \mathbf{w}_l} = 2 \mathbf{C}_{\mathbf{x}} \mathbf{w}_l - 2 \lambda \mathbf{w}_l = 0

\displaystyle \mathbf{C}_{\mathbf{x}} \mathbf{w}_l = \lambda_l \mathbf{w}_l \quad \quad \quad (6)

Persamaan (6) merupakan eigenvalue problem dimana \mathbf{w}_l merupakan eigenvector dan \lambda_l merupakan eigenvalue dari matriks \mathbf{C}_{\mathbf{x}}. Problem (6) dapat memiliki lebih dari 1 solusi \{\mathbf{w}_l, \lambda_l \}_{l \geq 1} (maksimum hingga d solusi). Di sini kita hanya mengambil komponen \mathbf{w}_l dengan nilai \lambda_l terbesar, sebut saja \mathbf{w}_1. Jadi, \mathbf{w}_1 merupakan principal component pertama dari himpunan data \{ \mathbf{x}^{(i)}\}_{i=1}^{n}.

Seperti yang telah diketahui sebelumnya bahwa kita dapat menghitung k buah principal components. Kita telah menghitung komponen pertama dengan persamaan (4)-(6). Bagaimana cara menghitung principal component ke-2, 3, …, k? Hampir mirip seperti menghitung komponen ke-1. Namun, kita perlu menambahkan contstraint tambahan yaitu komponen-komponen selanjutnya harus ortogonal terhadap komponen-komponen sebelumnya. Secara matematis (ambil contoh hanya dengan menghitung komponen ke-2) dapat ditulis sebagai berikut

\displaystyle \max_{\mathbf{w}_2} \mathbf{w}^{\top}_2 \mathbf{C}_{\mathbf{x}} \mathbf{w}_2 \quad \text{s.t.} \quad \| \mathbf{w}_2 \|^2 = 1, \mathbf{w}^{\top}_2 \mathbf{w}_1 = 0 \quad \quad \quad(7).

dimana \mathbf{w}^{\top}_2 \mathbf{w}_1 = 0 berarti komponen 2 ortogonal terhadap komponen 1. Dalam bentuk Lagrangian

\displaystyle J(\mathbf{w}_2) = \mathbf{w}^{\top}_2 \mathbf{C}_{\mathbf{x}} \mathbf{w}_2 - \lambda( \mathbf{w}^{\top}_1 \mathbf{w}_1 - 1) - \beta (\mathbf{w}^{\top}_2 \mathbf{w}_1 - 0)\quad \quad \quad(8)

Langkah-langkah selanjutnya sama dengan langkah-langkah menghitung komponen pertama.

Kita dapat meringkas pencarian k buah principal components dalam satu persamaan optimisasi saja. Tulis principal components dalam bentuk matriks kolom \mathbf{W} = [\mathbf{w}_1 ... \mathbf{w}_k] \in \mathbb{R}^{d \times k}. Problem optimisasi PCA dapat ditulis menjadi

\displaystyle \mathbf{W}^{*} := \arg \max_{\mathbf{W} } \mathrm{Tr}( \mathbf{W}^{\top} \mathbf{C}_{\mathbf{x}} \mathbf{W}) \quad \text{s.t.} \quad \mathbf{W}^{\top} \mathbf{W} = \mathbf{I} \quad \quad \quad (9)

dimana fungsi \mathrm{Tr}(\mathbf{A}) merupakan penjumlahan elemen-elemen diagonal dari matriks \mathbf{A} dan \| A \|_F = \sqrt( \sum_{i,j}^{} A^2_{ij}) merupakan fungsi yang kita sebut sebagai Frobenious norm (generalisasi dari vector norm). Constraint \|\mathbf{W}\|^2_F = \mathbf{I} menjamin agar setiap kolom dari matriks \mathbf{W} akan saling ortonormal.

Setelah mendapatkan principal components \mathbf{W}^*, kita dapat menghitung k buah variabel latent ke-i sekaligus, dalam bentuk vektor \mathbf{z}^{(i)} = \mathbf{W}^{*\top} \mathbf{x}^{(i)}, \forall i=1,...,n, atau dapat diringkas menjadi \mathbf{Z} = \mathbf{X} \mathbf{W}^{*}, dimana baris dari \mathbf{Z} \in \mathbb{R}^{n \times k} berisi \mathbf{z}^{(i) \top} (sebut saja \mathbf{Z} sebagai matriks latent). Vektor-vektor \{ \mathbf{z}^{(i)}\}_{i=1}^{n} inilah yang nantinya akan digunakan untuk analisis lebih lanjut sebagai ganti dari sampel asli \{ \mathbf{x}^{(i)} \}_{i=1}^{n}, e.g., sebagai input untuk algoritma supervised learning.

Seperti yang telah dibahas sebelumnya, kita dapat menghitung k buah principal components maksimum hingga d buah, i.e., sebanyak dimensi asli sampel . Jika PCA digunakan sebagai dimensionality reduction, maka k < d. Selanjutnya adalah bagaimana cara menentukan jumlah komponen k? Jawabannya adalah tergantung dari problem yang kita ingin selesaikan.

Sebagai contoh dalam konteks permasalahan supervised learning, i.e., klasifikasi atau regresi, kita menginginkan k sekecil mungkin, namun tanpa mengurangi performa klasisifikasi / regresi, atau bahkan lebih baik lagi. Ada beberapa metode heuristics yang dapat digunakan antara lain, cross-validation, pengecekan spektrum eigenvalues, dan lain-lain.

3. Kernel Principal Component Analysis

Principal Component Analysis yang telah dibahas sebelumnya bekerja pada ruang data yang asli \mathcal{X}. Dibanyak kasus, terkadang “struktur” ruang \mathcal{X} tidak cukup mudah bagi classifier untuk mengkategorisasi data. Salah satu trik yang dapat digunakan adalah dengan memetakan data ke feature map oleh sebuah fungsi \phi: \mathcal{X} \rightarrow \mathcal{H} yang nantinya dapat di-‘kernelisasi’ (lihat tulisan pertama saya mengenai metode kernel).

Pertama-tama, kita asumsikan bahwa ruang fitur \mathcal{H} memiliki dimensi terhingga p. Misalkan \mathbf{\Phi} \in \mathbb{R}^{n \times p} merupakan matriks fitur dimana baris ke-i dari matriks tersebut berisi vektor \phi(\mathbf{x}^{(i)})^{\top}. Kita definisikan ulang persamaan matriks covariance (2) dalam konteks ruang fitur, sehingga menjadi

\displaystyle \mathbf{C}_{\phi} = \frac{1}{n} \mathbf{\Phi}^{\top} \mathbf{\Phi},\quad \quad \quad(10)

dengan asumsi fitur-fitur \phi( \mathbf{x}^{(i)}) sudah distandardisasi, i.e., \frac{1}{n} \sum_{i=1}^{n} \phi( \mathbf{x}^{(i)}) = 0. Perubahan ini berimbas ke problem optimisasi PCA (9) yang menjadi

\displaystyle \mathbf{W}^* := \arg \max_{\mathbf{W} \in \mathbb{R}^{p \times k}} \frac{1}{n} \mathrm{Tr}(\mathbf{W}^{\top} \mathbf{\Phi}^{\top} \mathbf{\Phi} \mathbf{W}) \textnormal{ s.t. }\mathbf{W}^{\top} \mathbf{W}= \mathbf{I}. \quad \quad \quad (11).

Sekarang kita definisikan  matriks kernel [\mathbf{K}]_{ij} = [\kappa(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})] berdimensi n \times n, dimana \kappa: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R} merupakan fungsi kernel. Definiskan matriks proyeksi \mathbf{B} \in \mathbb{R}^{n \times k} sedemikian sehingga persamaan berikut ini terpenuhi

\displaystyle \mathbf{Z} = \mathbf{\Phi} \mathbf{W} = (\mathbf{\Phi} \mathbf{\Phi}^{\top})^{\top} \mathbf{B} = \mathbf{K}^{\top} \mathbf{B}. \quad \quad \quad(12)

Di sini \mathbf{K}^{\top} \mathbf{B} dapat dilihat sebagai alternatif untuk menghitung variabel-variabel latent.

Dengan demikian, untuk mengubah problem (11) menjadi representasi kernel, kita dapat mensubstitusi \mathbf{\Phi} \mathbf{W} = \mathbf{K}^{\top} \mathbf{B} dan \mathbf{W} = \mathbf{\Phi}^{\top} \mathbf{B} sehingga problem yang akan kita selesaikan menjadi

\displaystyle \mathbf{B}^{*} := \arg \max_{\mathbf{B}} \frac{1}{n} \mathrm{Tr} (\mathbf{B}^{\top} \mathbf{K} \mathbf{K} \mathbf{B}) \textnormal{ s.t. } \mathbf{B}^{\top} \mathbf{K} \mathbf{B} = \mathbf{I}. \quad \quad \quad(13)

Perhatikan bahwa \| \mathbf{\Phi}^{\top} \mathbf{B}\|_F^2 = \mathbf{B}^{\top} \mathbf{\Phi} \mathbf{\Phi}^{\top} \mathbf{B} = \mathbf{B}^{\top} \mathbf{K} \mathbf{B}. Sama halnya seperti PCA standar, fungsi objektif di atas dapat ditulis dalam bentuk Lagrangian

\displaystyle J(\mathbf{B}) = \frac{1}{n} \mathrm{Tr}( \mathbf{B}^{\top} \mathbf{K} \mathbf{K} \mathbf{B} ) - (\mathbf{B}^{\top} \mathbf{K} \mathbf{B} - \mathbf{I} ) \mathbf{\Lambda} \quad \quad \quad (14)

dimana \mathbf{\Lambda} = \mathrm{diag}(\lambda_1, ..., \lambda_n) merupakan Lagrange multipliers. Dengan menghitung \frac{\partial J( \mathbf{B}) }{\partial \mathbf{B}} = 0, kita mendapatkan solusi dari (14) berikut ini:

\displaystyle \frac{1}{n} \mathbf{K} \mathbf{B} = \mathbf{B} \mathbf{\Lambda} \quad \quad \quad (15)

dimana \mathbf{\Lambda} = \mathrm{Tr}(\lambda_1, ..., \lambda_n) sekarang merupakan k buah nilai eigen (\lambda_1 > \lambda_2 > ... > \lambda_n) dan kolom-kolom dari matriks \mathbf{B} merupakan vektor-vektor eigen terkait. Algoritma ini kita sebut sebagai Kernel Principal Component Analaysis (KPCA).

Dalam konteks aplikasi klasifikasi atau regresi, secara umum KPCA akan menyediakan performa klasifikasi/regresi yang lebih baik dibandingkan PCA, apabila fungsi kernel \kappa(\cdot,\cdot) dipilih dengan tepat. Perlu diketahui bahwa jika kita menggunakan linear kernel \kappa(\mathbf{a},\mathbf{b}) = \mathbf{a}^{\top} \mathbf{b} sebagai fungsi kernel, maka KPCA = PCA.

4. Transfer Component Analysis

(Pan et al. 2011) merancang sebuah metode berbasis KPCA untuk memecahkan masalah domain adaptation / transfer learning yang dinamakan sebagai Transfer Component Analysis (TCA). Dalam konteks domain adaptation dimana data latih dan data target memiliki distribusi yang berbeda (lihat tulisan saya mengenai domain adaptation & dataset bias), PCA dan KPCA mungkin belum cukup untuk mengurangi perbedaan distribusi antara data latih dan data target.

Lebih spesifiknya, misalkan terdapat himpunan data latih (source domain) \{ x_s^{(i)}, y_s^{(i)}\}_{i=1}^{n_s} \sim \mathcal{D}_s dan data target (target domain) \{ x_t^{(j)}, y_t^{(j)}\}_{j=1}^{n_t} \sim \mathcal{D}_t dimana \mathcal{D}_s \neq \mathcal{D}_t. Definsikan sebuah distance measure antara 2 buah probability distribution \mathfrak{M} (\mathcal{P}, \mathcal{Q}). Objektif dari TCA adalah menyelesaikan problem optimisasi sebagai berikut:

\displaystyle \mathbf{B}^{*} := \arg \max_{\mathbf{B}} \frac{1}{n} \mathrm{Tr} (\mathbf{B}^{\top} \mathbf{K} \mathbf{K} \mathbf{B}) \quad \quad \quad(16)

\displaystyle \textnormal{ s.t. } \mathbf{B}^{\top} \mathbf{B}=\mathbf{I}\textnormal{ dan } \mathfrak{M}(\mathcal{D}_s, \mathcal{D}_t)=0

Perhatikan bahwa jika constraint \mathfrak{M}(\cdot, \cdot) dihilangkan, maka problem (16) sama dengan problem (13), i.e., TCA = KPCA.

Karena bentuk probability distributions \mathcal{D}_s dan \mathcal{D}_t tidak diketahui, kita butuh suatu kriteria yang dapat menghitung \mathfrak{M}(\cdot, \cdot) secara empiris dari sampel \{ \mathbf{x}^{(i)}\}_{i=1}^{n_s} \cup \{ \mathbf{x}^{(j)}\}_{j=1}^{n_t}. Salah satu kriteria yang dapat digunakan adalah Maximum Mean Discrepancy (MMD).

Maximum mean discrepancy

Seperti yang telah disinggung sebelumnya, Maximum Mean Discrepancy (MMD) merupakan kriteria yang digunakan untuk mengukur perbedaan antara 2 buah probability distributions dari sampel-sampelnya. Sebenarnya ada beberapa kriteria yang lainnya yang dapat digunakan. Alasan utamanya adalah karena MMD dapat dengan mudah diubah menjadi bentuk kernel sehingga MMD merupakan pilihan natural untuk memodifikasi KPCA menjadi TCA.

Misalkan S_s = \{ \mathbf{x}^{(i)} \}_{i=1}^{n_s} dan S_t = \{ \mathbf{x}^{(j)} \}_{j=1}^{n_t}, Maximum Mean Discrepancy (dalam bentuk kuadrat) didefinisikan sebagai berikut

\displaystyle \mathfrak{MMD}^2(S_s, S_t) = \left \| \frac{1}{n_s} \sum_{i=1}^{n_s} \phi(\mathbf{x}^{(i)}) - \frac{1}{n_t} \sum_{j=1}^{n_t} \phi(\mathbf{x}^{(j)}) \right \|^2_{\mathcal{H}}\quad \quad \quad (17)

dimana fungsi \phi: \mathcal{X} \rightarrow \mathcal{H} merupakan feature map. Sedikit mengutak-atik aljabar dari persamaan (17), kita mendapatkan

\displaystyle \mathfrak{MMD}^2(S_s, S_t) = \mathrm{Tr}(\mathbf{K} \mathbf{L})\quad \quad \quad (18)

dimana [\mathbf{K}]_{ij} = [\kappa(\mathbf{x}^{(i)} ,\mathbf{x}^{(j)})], \forall \mathbf{x}^{(i)}, \mathbf{x}^{(j)} \in S_s \cup S_t merupakan matriks kernel dan

\displaystyle [\mathbf{L}]_{ij} = \frac{1}{n^2_s}, \forall \mathbf{x}^{(i)}, \mathbf{x}^{(j)} \in S_s

\displaystyle [\mathbf{L}]_{ij} = \frac{1}{n^2_t}, \forall \mathbf{x}^{(i)}, \mathbf{x}^{(j)} \in S_t

\displaystyle [\mathbf{L}]_{ij} = -\frac{1}{n_s n_t}, \forall \mathbf{x}^{(i)} \in S_s, \mathbf{x}^{(j)} \in S_t

merupakan matriks yang hanya berisikan konstanta.

problem optimisasi

Perhatikan bahwa persamaan MMD (17)-(18)  beroperasi pada ruang fitur \mathcal{H}. TCA menggunakan MMD pada ruang fitur yang setelah terproyeksi, sebut saja \tilde{\mathcal{H}} \subset \mathcal{H}. Asumsikan kedua ruang tersebut memiliki dimensi terhingga k dan d, masing-masing untuk \tilde{\mathcal{H}} dan \mathcal{H}, dimana k < d. Misal terdapat matriks kernel \tilde{\mathbf{K}} yang terdefinisi di ruang \tilde{\mathcal{H}} (dapat diverifikasi bahwa \tilde{\mathbf{K}} = \mathbf{K} \mathbf{B} \mathbf{B}^{\top} \mathbf{K}), persamaan MMD pada ruang tersebut dapat ditulis sebagai berikut:

\displaystyle \mathfrak{MMD}^2(S_s, S_t) = \mathrm{Tr}( \tilde{\mathbf{K}} \mathbf{L}) = \mathrm{Tr}( \mathbf{B}^{\top} \mathbf{K} \mathbf{L}\mathbf{K} \mathbf{B} )\quad \quad \quad (19)

Dengan mensubstitusi contraint \mathfrak{M}(\cdot, \cdot) dengan kriteria (19), kita dapat menyatakan problem (16) dalam bentuk Lagrangian

\displaystyle J(\mathbf{B}) = \frac{1}{n} \mathrm{Tr}(\mathbf{B}^{\top} \mathbf{K} \mathbf{K} \mathbf{B}) - \mathrm{Tr}( (\mathbf{B}^{\top} (\mathbf{K} \mathbf{L} \mathbf{K} + \alpha \mathbf{I}) \mathbf{B} - \mathbf{I} ) \mathbf{\Lambda}) \quad\quad\quad(20)

dimana \alpha > 0 merupakan konstanta pengontrol panjang vektor-vektor proyeksi, i.e., kolom dari matriks \mathbf{B} \in \mathbb{R}^{n \times k}. dengan solusi dalam bentuk generalized eigendecomposition sebagai berikut:

\displaystyle \frac{1}{n} \mathbf{K} \mathbf{K} \mathbf{B} = (\mathbf{K} \mathbf{L} \mathbf{K} + \alpha \mathbf{I}) \mathbf{\Lambda}\quad\quad\quad(21)

dimana \mathbf{\Lambda} = \mathrm{Tr}(\lambda_1, ..., \lambda_n) sekarang merupakan k buah nilai eigen (\lambda_1 > \lambda_2 > ... > \lambda_n) dan kolom-kolom dari matriks \mathbf{B} merupakan vektor-vektor eigen terkait.

Seperti halnya pada KPCA, pengekstraksian fitur (variabel-variabel latent) dilakukan dengan menghitung \mathbf{Z} = \mathbf{K} \mathbf{B}^{*}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s