Fast Domain Generalization with Kernel Methods – Part 4 (Scatter Component Analysis)


Ini merupakan seri terakhir dari tulisan saya mengenai metode kernel pada domain adaptation/generalization. Akhirnya summer project kali ini ditutup dengan men-submit sebuah paper ke International Conference on Machine Learning (ICML). Kami merancang sebuah algoritma transfer learing / domain adaptation yang dinamakan Scatter Component Analysis (SCA) pada aplikasi object recognition.

Ide utama dari algoritma ini adalah mengekstrak representasi (features) yang memiliki 3 buah sifat berikut ini:

  1. Persebaran data (total variance) maksimum
  2. Perbedaan antar domain (domain mismatch) minimum
  3. Persebaran representasi berdasarkan kategori / kelas maksimum

Kesemua sifat tersebut dapat dicapai dengan menggunakan sebuah tool bernama scatter.

1. Notasi

Pertama-tama, kita definisikan “domain” sebagai distribusi probabilitas \mathbb{P}_{XY} pada \mathcal{X} \times \mathcal{Y}, dimana \mathcal{X} dan \mathcal{Y} merupakan ruang input dan label. Himpunan sampel dari sebuah domain dapat ditulis sebagai S = \{ x_i, y_i\}_{i=1}^n \sim \mathbb{P}_{XY}. Kita dapat menuliskan distribusi empiris dari sampel tersebut dengan \hat{\mathbb{P}}_{XY}(x,y) = \frac{1}{n} \sum_{i=1}^{n} \delta_{(x_i, y_i)} (x,y), dimana \delta merupakan fungsi Dirac delta.

2. Scatter

Scatter tidak lain merupakan varians, sebuah ukuran yang lazim di statistik. Pada konteks kali ini kita fokuskan komputasi varians pada ruang fitur reproducing kernel Hilbert Space \mathcal{H}, yang mungkin saja berdimensi tak hingga.

Sebelum mendefinisikan scatter secara formal, akan lebih nyaman apabila merepresentasikan domain dengan menggunakan mean map (Smola et al. 2007).

Definisi 1 (Mean map). Misal \mathcal{X} dilengkapi dengan sebuah kernel \kappa : \mathcal{X} \times \mathcal{X} \rightarrow \mathcal{H} dan \mathcal{H} merupakan ruang fitur reproducing kernel Hilbert space (RKHS) dengan feature map \phi : \mathcal{X} \rightarrow \mathcal{H}. Tulis \Delta_{\mathcal{H}} sebagai sebuah himpunan distribusi probabilitas pada \mathcal{X}. Mean map dideskripsikan sebagai berikut:

\displaystyle \mu: \Delta_{\mathcal{X}} \rightarrow \mathcal{H}: \mathbb{P} \rightarrow \mathbb{E}_{x \sim \mathbb{P}}[\phi(x)] =: \mu_{\mathbb{P}}

Secara geometris, mean map merupakan centroid (titik tengah) dari himpunan representasi di ruang fitur \mathcal{H}.

Definis 2 (Scatter). Misal \mathcal{X} merupakan ruang input, dilengkapi dengan feature map \phi : \mathcal{X} \rightarrow \mathcal{H}. (Expected) Scatter dari distribusi probabilitas \mathbb{P} pada \mathcal{X} relatif terhadap \phi didefinisikan sebagai:

\displaystyle \Psi_{\phi}(\mathbb{P}) := \mathbb{E}_{x \sim \mathbb{P}} \left[ \| \mu_{\mathbb{P}} - \phi(x) \|^2 \right]

dimana \| \cdot \|_{\mathcal{H}} merupakan fungsi norm dari \mathcal{H}.

Untuk melengkapi Definisi 2, kita dapat pula menuliskan sample scatter sebagai

\displaystyle \Psi_{\phi}( \hat{ \mathbb{P} }) := \frac{1}{n} \sum_{i=1}^{n} \| \mu_{\hat{\mathbb{P}}} - \phi(x_i)\|^2, 

yaitu, scatter yang dihitung dari himpunan n sampel S = \{ x_1, ...., x_n\}, dengan \hat{\mathbb{P}} merupakan distribusi probabilitas empiris dihitung dari sampel S.

Teorema berikut ini mengindikasikan seberapa besar perbedaan antara expected scatter dengan sample scatter.

Teorema 1. Misalkan \mathbb{P} merupakan distribusi probabilitas pada ruang input \mathcal{X} dan \hat{\mathbb{P}} merupakan distribusi empiris dihitung dari n sampel. Kemudian, misalkan \| \phi(x) \|^2 \leq M untuk setiap x \in \mathcal{X}. Dengan probabilitas \geq 1 -\delta,

\displaystyle | \Psi_{\phi}(\mathbb{P}) - \Psi_{\phi} (\hat{\mathbb{P}}) | \leq M \sqrt{ \frac{2 \mathrm{log}( \frac{2}{\delta} )}{n} }.

Bukti: Tulis \Psi_{i \leftarrow \tilde{x}}:= \Psi_{\phi}(x_1....x_{i-1}, \tilde{x}, x_{i+1}....x_{n}). Ekspresi di bawah ini akan terpenuhi

\displaystyle \mathrm{sup}_{x_1, ..., .x_n, \tilde{x} \in \mathcal{X}}| \Psi_{\phi}( x_1, ..., x_n) - \Psi_{i \leftarrow \tilde{x}} (x_1, ..., x_n)|\leq \frac{2M}{n}.

Dengan pertidaksamaan McDiarmid, didapatkan

\displaystyle \mathbb{Q} \left\{ | \Psi_{\phi}(\mathbb{P}) - \Psi_{\phi} (\hat{\mathbb{P}} ) | > \epsilon \right\} \leq 2 \exp (- \frac{\epsilon^2 n}{2M^2}).

Dengan \mathbb{Q} \left \{ \cdot \right \} \geq 1 - \delta dan beberapa operasi aljabar, maka akan didapatkan Teorema 1.

Berikut ini merupakan penggunaan praktis dari scatter. Jika input berupa vektor dan \phi merupakan fungsi identitas, maka didapatkan Lemma

Lemma 2 (scatter sebagai total variance). Scatter dari himpunan sampel \mathbf{X}=\{ \mathbf{x}_1, ..., \mathbf{x}_n \} merupakan total variance:

\displaystyle \Psi(\mathbf{X}) = \mathrm{Tr} (\mathrm{Cov}(\mathbf{X}))

dimana \mathrm{Tr}(\cdot) merupakan operasi Trace.

3. Scatter Component Analysis

Scatter Component Analysis (SCA) mengekstrak representasi (features) yang meningkatkan “generalisasi” dari source domain ke target domain. Sebagai ilustrasi, representasi tersebut dibentuk dengan menyelesaikan problem optimisasi dalam ekspresi seperti di bawah ini:

\displaystyle \mathrm{sup} \frac{ \{ \textnormal{total scatter} \} + \{ \textnormal{between-class scatter} \} }{ \{ \textnormal{domain scatter} \} + \{ \textnormal{within-class scatter}\}}\quad\quad\quad(1).

SCA memaksimalkan unsur-unsur yang berada pada pembilang ekspresi (1), sekaliguskan meminimalkan unsur-unsur pada penyebut. Strategi ini bertujuan untuk mencapai sifat-sifat yang telah disebutkan di awal. Berikutnya akan dijelaskan masing-masing unsur tersebut.

Total Scatter

Diberikan source dan target domain \mathbb{P}_{X}^s dan \mathbb{P}_X^t pada \mathcal{X}, kita definisikan total scatter dari distribusi probabilitas rata-rata (mean) \mathbb{P}^{s \cup t}_{X}:= \frac{1}{2} \mathbb{P}_X^s + \frac{1}{2} \mathbb{P}_X^t sebagai berikut:

\displaystyle \textnormal{total scatter} = \Psi_{\phi}(\mathbb{P}_X^{s \cup t})

Total scatter dapat diestimasi dari n buah sampel. Misalkan \mathbf{X} = [\mathbf{x}_1, ..., \mathbf{x}_n]^{\top} \in \mathbb{R}^{n \times p} sebuah matriks data, gabungan dari source dan target domain (n = n_s + n_t). Diberikan feature map \phi : \mathbb{R}^p \rightarrow \mathcal{H} dengan kernel \kappa, kita definisikan matriks fitur \mathbf{\Phi} = [\phi(\mathbf{x}_1, ..., \phi(\mathbf{x}_n)]^{\top}. Dengan mengasumsikan rata-rata \frac{1}{n} \sum_{i=1}^{n} \phi(\mathbf{x}_i) = 0 dan Lemma 2, (sample) total scatter didefinisikan sebagai berikut:

\displaystyle \Psi_{\phi}(\hat{\mathbb{P}}_X^{s \cup t})=\mathrm{Tr}( \mathrm{Cov}(\mathbf{\Phi}) ).

Kita tertarik dengan total scatter pada representasi setelah mengaplikasi transformasi linear \mathbf{W}: \mathcal{H} \rightarrow \tilde{\mathcal{H}}, dimana dimensi dari \tilde{\mathcal{H}}, i.e., \mathrm{dim}(\tilde{\mathcal{H}}) = k cukup kecil. Mulai saat ini kita sebut \mathcal{H} sebagai ruang fitur dan \tilde{\mathcal{H}} sebagai ruang fitur tertransformasi.

Misalkan \mathbf{Z} = \mathbf{\Phi} \mathbf{W} \in \mathbb{R}^{n \times k} merupakan matriks feature yang telah tertransformasi dan [\mathbf{K}]_{ij} = [\mathbf{\Phi} \mathbf{\Phi}^{\top}]_{ij} = [\kappa(\mathbf{x}_i, \mathbf{x}_j)]. Jika \mathbf{B} \in \mathbb{R}^{n \times k} merupakan sebuah matriks sedemikian sehingga \mathbf{W} = \mathbf{\Phi}^{\top} \mathbf{B}, maka total transformed scatter dapat didefinisikan sebagai berikut:

\displaystyle \Psi_{\mathbf{B} \circ \phi}(\hat{\mathbb{P}}^{s \cup t}_X) = \mathrm{Tr}( \underbrace{\mathbf{B}^{\top} \mathbf{K} \mathbf{K} \mathbf{B}}_{\mathrm{Cov}(\mathbf{Z})} )\quad \quad \quad(2).

Jika terdapat problem optimisasi dalam bentuk

\displaystyle \max \Psi_{\mathbf{B} \circ \phi}(\hat{\mathbb{P}^{s \cup t}_X}) \textnormal{ s.t. } \mathbf{B}^{\top}\mathbf{K} \mathbf{B} = \mathbf{I},

maka problem tersebut merupakan Kernel Principal Component Analysis (KPCA) (Schölkopf et al. 1998).

domain scatter

Scatter juga dapat diaplikasikan untuk mengukur perbedaan antara source dan target domain :

\displaystyle \textnormal{domain scatter} = \Psi(\{ \mu_{\mathbb{P}_X^s }, \mu_{\mathbb{P}_X^t} \})

Kita akan menunjukkan bahwa ekspresi di atas sebanding dengan sebuah metrik yang disebut sebagai Maximum Mean Discrepancy (MMD), yang sudah cukup banyak digunakan pada aplikasi domain adaptation / transfer learning.

Definisi 3 (Maximum Mean Discrepancy). Misalkan \mathcal{F} merupakan sebuah himpunan fungsi dari f: \mathcal{X} \rightarrow \mathbb{R}. MMD dari domain \mathbb{P} and \mathbb{Q} dinyatakan sebagai berikut:

\displaystyle \mathrm{MMD}_{\mathcal{F}} [ \mathbb{P}, \mathbb{Q}] := \sup_{f \in \mathcal{F}} \left( \mathbb{E}_{\mathbb{P}}[f(x)] - \mathbb{E}_{\mathbb{Q}}[f(x)] \right)

Hubungan antara domain scatter dengan MMD dijelaskan oleh teorema di bawah ini:

Teorema 3 (scatter sebanding dengan MMD). Scatter dari 2 buah domain \mathbb{P} dan \mathbb{Q} pada ruang \mathcal{X} merupakan MMD kuadrat:

\displaystyle \Psi(\{ \mu_{\mathbb{P}}, \mu_{\mathbb{Q}} \})=\frac{1}{4} MMD_{\mathcal{F}}^2[\mathbb{P}, \mathbb{Q}]

dimana \mathcal{F} = \{ f : \mathcal{X} \rightarrow \mathbb{R}\} merupakan himpunan fungsi linear dan \| f \|_{\mathcal{F}} \leq 1\}.

Selanjutnya kita akan merancang bagaimana menghitung domain scatter pada ruang fitur tertransformasi \tilde{\mathcal{H}} diberikan sejumlah sampel. Pertama-tama, tulis \mathbf{Z} = \mathbf{\Phi} \mathbf{W} = \mathbf{K}^{\top} \mathbf{B} (lihat kembali subbab total scatter untuk mengingat kembali maksud dari notasi tsb) dan

matrixK

sebagai matriks features dan kernel dari sampel diambil dari semua (source dan target) domain. Dengan sedikit aljabar, (sampel) domain scatter dapat dinyatakan sebagai berikut:

\Psi(\{ \mu_{\hat{\mathbb{P}}_X^s}, \mu_{\hat{\mathbb{P}}_X^t}\})=\mathrm{Tr}(\mathbf{B}^{\top} \mathbf{K} \mathbf{L} \mathbf{K} \mathbf{B})\quad \quad \quad(3),

dimana

matrixL

dan \mathcal{I}_{S^s}, \mathcal{I}_{S^t} masing-masing merupakan himpunan indeks dari source dan target domain.

class scatter

Unsur terakhir yang dimiliki SCA adalah class scatter yang terdiri dari 2 besaran:

i) Within-class scatter : mengukur persebaran sampel di kelas/kategori tertentu,

ii) Between-class scatter: mengukur persebaran sampel antar kelas/kategori.

Secara formal, kedua besaran tersebut didefinisikan sebagai berikut. Untuk setiap kelas k \in \{ 1,..., C\}, tulis \mathbb{P}_{X | k}^s sebagai distribusi kondisional pada \mathcal{X} dihasilkan dari source domain \mathbb{P}_{XY}^s ketika Y=k. Within-class dan between-class scatter :

class_scatter

Seperti yang dilakukan pada unsur-unsur sebelumnya, kita tertarik menghitung class scatter pada ruang fitur tertransformasi \tilde{\mathcal{H}}.

Sebelum melakukan operasi di ruang tertransformasi \tilde{\mathcal{H}}, pertama-tama kita akan melihat bagaimana menghitung class scatter di ruang fitur \mathcal{H}. Misalkan \mathbf{S}_k^w = (\phi(\mathbf{x}_j))_{\mathbf{x}_j \in k} merupakan n_ktuple sampel dari source domain pada ruang fitur \mathcal{H}. Tulis centroid dari \mathbf{S}_k^w sebagai \boldsymbol{\mu}_k = \frac{1}{n_k} \sum_{\mathbf{x}_i \in k} \phi(\mathbf{x}_i). Lalu, misal \mathbf{S}^b=(\boldsymbol{\mu}_1, ..., \boldsymbol{\mu}_{|C|} ) merupakan tuple dari centroid masing-masing kelas. Sekarang akan mudah untuk melihat bahwa centroid dari \mathbf{S}^b merupakan centroid dari source domain: \bar{\boldsymbol{\mu}^s} = \frac{1}{n} \sum_{k=1}^{|C|} n_k \boldsymbol{\mu}_k.

Dengan demikian, (sample) within-class scatter pada ruang fitur \mathcal{H} dapat dinyatakan sebagai:

\displaystyle \Psi_{\phi} ( \hat{\mathbb{P}}^s_{X | y_k} ) = \mathrm{Tr} \left(\sum_{j=1}^{n_k} (\phi(\mathbf{x}_{jk}) - \boldsymbol{\mu}_k) (\phi(\mathbf{x}_{jk}) - \boldsymbol{\mu}_k )^{\top} \right)

\displaystyle = \mathrm{Tr}\left( \mathrm{Cov}(\mathbf{S}^w_k)\right),

serta (sample) between-class scatter

\displaystyle \Psi( \{ \mu_{\hat{\mathbb{P}}^s_{X | y_k} } \}_{k=1}^C) = \mathrm{Tr} \left(n_k (\boldsymbol{\mu}_k - \bar{\boldsymbol{\mu}} ) (\boldsymbol{\mu}_k - \bar{\boldsymbol{\mu}})^{\top} \right)

\displaystyle = \mathrm{Tr}\left( \mathrm{Cov}(\mathbf{S}^b) \right).

Sekarang kita akan merancang bagaimana kedua besaran ini dihitung pada ruang fitur tertransformasi \tilde{\mathcal{H}}. Diketahui matriks transformasi \mathbf{W} \in \mathbb{R}^{d \times k}, dengan menggunakan Lemma 2, masing-masing within-class dan between-class scatter dapat dinyatakan sebagai berikut:

\displaystyle \sum_{k=1}^{C}\Psi_{B \circ \phi}( \{ \mu_{\hat{\mathbb{P}}^s_{X | y_k} } \}_{k=1}^C )=\sum_{k=1}^{C}\mathrm{Tr}( \mathbf{W}^{\top} \mathrm{Cov}(\mathbf{S}^w_k) \mathbf{W}) = \mathrm{Tr}(\mathbf{B}^{\top} \mathbf{Q}_s \mathbf{B})\quad\quad\quad(4),

\displaystyle \Psi_{B} ( \hat{\mathbb{P}}^s_{X | y_k})=\mathrm{Tr}\left( \mathbf{W}^{\top} \mathrm{Cov}( \mathbf{S}^b) \mathbf{W}\right) = \mathrm{Tr}\left( \mathbf{B}^{\top} \mathbf{P}_s \mathbf{B}\right)\quad\quad\quad(5),

dimana

\displaystyle \mathbf{P}_s = \sum_{k=1}^{C} n_k (\mathbf{m}_k - \bar{\mathbf{m}})(\mathbf{m}_k - \bar{\mathbf{m}})^{\top},

\displaystyle \mathbf{Q}_s = \sum_{k=1}^{C} \mathbf{K}_k \mathbf{H}_k \mathbf{K}_k^{\top},

dan \mathbf{m}_k = \frac{1}{n_k} \sum_{j=1}^{n_k} \kappa(\cdot, \mathbf{x}_{jk}),

\bar{\mathbf{m}} = \frac{1}{n} \sum_{j=1}^{n} \kappa(\cdot, \mathbf{x}_j),

[\mathbf{K}_k]_{ij} = [\kappa(\mathbf{x}_{ik}, \mathbf{x}_{jk})],

serta \mathbf{H}_k = \mathbf{I}_{n_k} - \frac{1}{n_k} \mathbf{1}_{n_k} \mathbf{1}_{n_k}^{\top} merupakan centering matrix, dimana \mathbf{I}_{n_k} matriks identitas dan \mathbf{1}_{n_k} \in \mathbb{R}^{n_k} vektor yang semua elemennya 1.

 4. ALgoritma SCA

SCA menggabungkan semua unsur-unsur yang didefinisikan pada persamaan (2), (3), (4), dan (5), sehingga ekspresi (1) dapat dikuantifikasi menjadi

\displaystyle \arg \max_{\mathbf{B}} \frac{\Psi_{\mathbf{B} \circ \phi}(\hat{\mathbb{P}}^{s \cup t}_X) + \Psi_{\mathbf{B}} ( \{ \mu_{\hat{\mathbb{P}}^s_{X | y_k} } \}_{k=1}^{C})}{\Psi_{\mathbf{B}}( \{ \mu_{\hat{\mathbb{P}}^s_X}, \mu_{\hat{\mathbb{P}}^t_X} \}) + \sum_{k=1}^{C} \Psi_{\mathbf{B} \circ \phi} (\hat{\mathbb{P}}^s_{X | y_k})}\quad\quad\quad(6).

Persamaan (6) dapat lebih dipertajam lagi sehingga menjadi problem optimisasi yang dapat dikomputasikan. Secara eksplisit, SCA mencari matriks transformasi \mathbf{B} = [\mathbf{b}_1, ..., \mathbf{b}_k] yang menyelesaikan problem di bawah ini:

\displaystyle \arg \max_{\mathbf{B} \in \mathbb{R}^{n \times k}} \frac{\mathrm{Tr}(\mathbf{B}^{\top} (\mathbf{K}^2 + \beta \mathbf{P})\mathbf{B})}{\mathrm{Tr}(\mathbf{B}^{\top} (\delta \mathbf{K} \mathbf{L} \mathbf{K} + \gamma \mathbf{Q}) \mathbf{B})} \textnormal{ s.t. } \mathbf{B}^{\top} \mathbf{K} \mathbf{B} = \mathbf{I}\quad \quad \quad(7),

dimana

matrixP_Q

dan \beta, \delta, \gamma \geq 0 merupakan parameter-parameter trade-off untuk mengontrol ‘seberapa penting’ masing-masing unsur scatter.

Problem (7) dapat ditulis dalam bentuk Lagrangian

\displaystyle J(\mathbf{B}) = \mathrm{Tr}(\mathbf{B}^{\top} (\mathbf{K}^2 + \beta \mathbf{P}) \mathbf{B}) -

\displaystyle \mathrm{Tr}( (\mathbf{B}^{\top} (\delta \mathbf{K} \mathbf{L} \mathbf{K} + \mathbf{K} + \gamma \mathbf{Q}) \mathbf{B} - \mathbf{I}_k ) \boldsymbol{\Lambda} )\quad\quad\quad(8),

dimana \boldsymbol{\Lambda} \in \mathbb{R}^{k \times k} merupakan matriks simetris berisi Lagrange multipliers.

Untuk menyelesaikan persamaan (8), hitung turunan pertama \displaystyle \frac{\partial J(\mathbf{B})}{\partial \mathbf{B}} = 0 sedemikian sehingga kita mendapatkan generalized eigenproblem

(\mathbf{K}^2 + \beta \mathbf{P}) \mathbf{B}^{*} = (\delta \mathbf{K} \mathbf{L} \mathbf{K} + \mathbf{K} + \gamma \mathbf{Q}) \mathbf{B}^{*} \boldsymbol{\Lambda} \quad\quad\quad(9)

dimana \boldsymbol{\Lambda} = \mathrm{diag}(\lambda_1, ..., \lambda_k) \in \mathbb{R}^{k \times k} sekarang merupakan matriks diagonal berisi k nilai eigen terbesar dan \mathbf{B} = [\mathbf{b}_1,...,\mathbf{b}_k] berisi vektor-vektor eigen terkait.

Setelah mendapatkan matriks transformasi optimal \mathbf{B}^{*}, kita dapat mengekstrak fitur \mathbf{Z} = \mathbf{K}^{\top} \mathbf{B}^{*}.

Algoritma 1 di bawah ini merupakan langkah per langkah implementasi dari SCA.

SCA_alg

5. Eksperimen

Bab ini menjelaskan sebagian hasil evaluasi dari SCA. Di bagian pertama, kita menggunakan data sintetis untuk menjelaskan ‘tingkah laku’ dari SCA dibandingkan dengan beberapa algoritma feature learning lainnya. Di bagian kedua, SCA diaplikasikan pada object recognition dengan menggunakan data gambar real-world.

5.1. Toy dataset

toy_vis
Gambar 1 Toy dataset

Gambar 1(a) di atas mendeskripsikan data sintetis yang memiliki 2 buah domain dan 3 buah kategori / kelas. Dapat dilihat pada gambar tersebut, terdapat 6 buah cluster yang berisi sampel, yang dibuat dengan sampling dari distribusi Gaussian / normal x_i^c \sim \mathcal{N}(\mu^c, \sigma^c), \forall c=1,...,6, dimana \mu^c dan \sigma^c masing-masing merupakan rata-rata (centroid) dan standar deviasi dari cluster ke-c.

Algoritma-algoritma lainnya yang digunakan sebagai pembanding adalah Kernel PCA, (Schölkopf et al. 1998), Semi-supervised Transfer Component Analaysis (SSTCA) (Pan et al. 2011), dan Transfer Joint Matching (TJM) (Long et al. 2014). SSTCA dan TJM merupakan algoritma yang dirancang khusus untuk kebutuhan domain adaptation / transfer learning, seperti halnya SCA.

Perhatikan bahwa baris ke-1 dan 2 dari Gambar 1 menampilkan konfigurasi sampel yang sama. Baris ke-1 mengilustrasikan perbedaan domain dari sampel (biru = source domain, merah = target domain). Tujuan dari algoritma domain adaptation adalah untuk mengurangi perbedaan (mismatch) dari kedua domain tersebut. Dapat dilihat bahwa ini berhasil dilakukan oleh SSTCA, TJM, dan SCA, dimana sampel berwarna merah dan biru bercampur satu sama lain.

Baris ke-2 mengilustrasikan 3 kelas yang diindikasikan oleh 3 warna berbeda, yang menunjukkan perbedaan utama antara SCA dengan algoritma-algoritma lainnya: representasi yang dihasilkan oleh SCA lebih jelas terkelompok berdasarkan kelas, sehingga berpeluang untuk lebih mudah dikategorisasi oleh metode supervised learning / classifier yang sederhana. Hal ini dikonfirmasi dengan hasil classification accuracy menggunakan 1-Nearest Neighbor (1-NN) –lihat angka persentase yang berada di dalam kurung pada label gambar. Dalam hal ini, SCA + 1-NN menghasilkan akurasi tertinggi.

5.2. office DATASET

Selanjutnya kita akan menginvestigasi performa dari SCA dengan menggunakan Office+Caltech dataset, yang berisi gambar-gambar 10 kategori objek. e.g., monitor, laptop, projector, etc, yang dapat ditemukan di lingkungan kantor. Office dataset terdiri dari 4 buah domain yang dikumpulkan dari dataset-dataset yang berbeda: Amazon (A), Webcam ( W ), Dslr (D), dan Caltech-256 (C). Dari Gambar 2, kita dapat melihat bahwa tampilan objek dari masing-masing domain (walaupun dalam kategori yang sama) tampak berbeda satu sama lain. Sulit untuk mendapatkan performa yang baik dengan menggunakan algoritma  machine learning konvensional dalam situasi seperti ini.

office_caltech
Gambar 2 Office+Caltech dataset

Dari ke-4 domain ini, kita dapat membentuk 12 kombinasi source-target: C \rightarrow A, C \rightarrow W, C \rightarrow D, ..., D \rightarrow W. Sebagai contoh, C \rightarrow A berarti algoritma diaplikasikan untuk mengenali kategori objek di A, dengan menggunakan data latih berlabel yang berasal dari C, dan data latih tidak berlabel dari A.

Perlu diketahui bahwa input gambar yang digunakan tidak lagi dalam bentuk raw pixels, melainkan berupa representasi SURF-BoW: raw pixels diubah menjadi representasi SURF, lalu dikuantisasi menjadi 800-bin data histogram yang diekstraksi dengan menggunakan algoritma K-means. Kemudian, histogram distandardisasi sehingga memilki rata-rata 0 dan standar deviasi 1.

SCA dibandingkan dengan berbagai algoritma baseline: 1) 1-Nearest Neighbor pada raw data (1NN), 2) TCA, 3) GFK, 4) SSTCA, 5) TJM, dan 6) uSCA. Perlu diketahui bahwa uSCA merupakan versi unsupervised dari SCA —class scatter dihilangkan dari problem optimisasi (7). Classifier yang digunakan pada metode 2) – 6), termasuk SCA,  adalah 1-Nearest Neighbor. Performa dalam classification accuracy (%) ditunjukkan pada tabel di bawah ini.

SURF_BoW_Office_table

SCA memberikan performa rata-rata klasifikasi terbaik dibandingkan algoritma lainnya, dan dari 12 kasus, akurasi SCA tertinggi di 10 kasus. Yang agak mengagetkan adalah uSCA merupakan kompetitor terdekat dari SCA.

6. kesimpulan

Scatter Component Analysis (SCA) merupakan algoritma representation / feature learning yang khusus dirancang untuk aplikasi domain adaptation, yang dibangun hanya menggunakan 1 buah tool: scatter. SCA menghasilkan representasi yang tidak hanya mengurangi perbedaan (mismatch) antara 2 buah domain, tetapi juga meningkatkan level pemisahan antar kelas sehingga lebih mudah untuk dikategorisasi oleh classifier sederhana, e.g., 1NN.

Beberapa hal yang dapat dikembangkan selanjutnya: i) memodifikasi SCA untuk aplikasi domain generalization, situasi dimana terdapat lebih dari 2 source domain dan sampel dari target domain benar-benar tidak dapat diakses, ii) mempercepat algoritma dengan menggunakan, e.g., random features (Williams & Seeger, 2001; Rahimi & Recht, 2007).

One thought on “Fast Domain Generalization with Kernel Methods – Part 4 (Scatter Component Analysis)

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