Fast Domain Generalization with Kernel Methods – Part 2 (SSSL)


Pada dasarnya, jika ada berbagai pilihan solusi untuk pemecahan suatu masalah, saya sangat tertarik solusi yang paling simpel (salah satu interpretasi dari Occam’s razor). Di semi-supervised learning, algoritma Simple Semi-Supervised Learning (SSSL) (Ji et al., ICML2012) saya anggap termasuk dalam kategori ini. Bahkan dalam banyak kasus SSSL mampu menghasilkan performa yang lebih baik dibandingkan dengan salah satu metode yang sebelumnya dianggap sebagai yang terbaik.

Bagi yang belum familiar dengan semi-supervised learning, masalah yang ingin dipecahkan sebenarnya mirip dengan supervised learning, yaitu mencari/mempelajari fungsi prediksi g: \mathcal{X} \rightarrow \mathcal{Y} yang mendekati fungsi yang sebenarnya f:\mathcal{X} \rightarrow \mathcal{Y} diberikan himpunan pasangan data berlabel \mathcal{D}_l = \{ x^{(i)}, y^{(i)}\}_{i=1}^{n_l}. Namun demikian, seringkali data berlabel tidak tersedia cukup banyak sehingga sulit untuk mencari fungsi prediksi g yang ‘baik’. Semi-supervised learning memungkinkan kita untuk memanfaatkan data tidak berlabel \mathcal{D}_u = \{ x^{(i)}\}_{i=1}^{n_u}, dengan asumsi bahwa \mathcal{D}_l dan \mathcal{D}_u ada semacam keterkaitan (yang tentunya tidak selalu benar).

Pada kesempatan ini saya mencoba

  • menginvestigasi kemampuan SSSL dalam konteks domain adaptation. Saya mengklaim bahwa domain adaptation merupakan kasus khusus dari semi-supervised learning, dimana data berlabel dan tidak berlabel \mathcal{D}_l, \mathcal{D}_u diambil dari ‘domain’ yang berbeda;
  • mempercepat proses eksekusi SSSL dengan menggunakan Nystrom method tanpa banyak ‘mengorbankan’ performa.

1. Simple Semi-Supervised Learning (SSSL)

SSSL merupakan metode regresi atau klasifikasi berbasis kernel yang memanfaatkan proses feature extraction secara implisit. Misalkan terdapat sebuah feature map \phi : \mathcal{X} \rightarrow \mathcal{H} dan himpunan data berlabel \mathcal{D}_l = \{ \mathbf{x}^{(i)}, y^{(i)} \}_{i=1}^{n_l}, objektif dari SSSL mirip dengan Linear Regression terlebih dahulu mentransformasi input menjadi feature, lihat tulisan saya sebelumnya tentang Linear Regression (LR), yaitu

\displaystyle \hat{\boldsymbol{\beta}} := \arg \min_{\boldsymbol{\beta} \in \mathbb{R}^d} \sum_{i=1}^{n_l} \left( \sum_{j=1}^{d} \beta_j \phi_j( \mathbf{x}^{(i)}) - y^{(i)} ) \right)^{2} \quad \quad \quad (1)

Perbedaannya adalah SSSL mampu untuk memanfaatkan data tidak berlabel \mathcal{D}_u = \{ \mathbf{x}^{(i)}\}_{i=1}^{n_u} sehingga mampu mendapatkan fungsi prediksi yang lebih optimal, dengan cara menghubungkan fungsi \phi dengan \mathcal{D}_u. Dari persamaan (1), belum terlihat jelas bagaimana menyisipkan data tidak berlabel pada proses optimisasi.

Integral Operator

Pertama-tama kita perlu mendefinisikan sebuah fungsi yang dinamakan integral operator. Misalkan \mathcal{D} =\{ \mathbf{x}^{(i)} \}_{i=1}^{n_l} \cup \{ \mathbf{x}^{(i)} \}_{i=1}^{n_u} merupakan gabungan seluruh datapoints yang diambil dari \mathcal{D}_l dan \mathcal{D}_u dengan total elemen N = n_l + n_u, integral operator \hat{L}_N : \mathcal{H} \rightarrow \mathcal{H} didefinisikan sebagai berikut:

\displaystyle \hat{L}_N [f](\cdot) = \frac{1}{N} \sum_{i=1}^{N} k(\mathbf{x}^{(i)}, \cdot) f (\mathbf{x}^{(i)}) \quad \quad \quad (2)

dimana k : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R} merupakan fungsi kernel dan f \in \mathcal{H}.

Motivasi mengapa perlu mendefinisikan integral operator ini cukup panjang. Mungkin perlu sedikit pemahaman mengenai functional analysis terlebih dahulu untuk benar-benar memahaminya. Pendek kata, integral operator menyediakan semacam framework untuk mengaproksimasi fungsi target g \in \mathcal{H} secara efisien.

Menghitung Fungsi Eigen dari Integral Operator

Lebih spesifiknya, misalkan \{ \gamma_j, \psi_j \}_{j = 1}^{s} merupakan nilai dan fungsi eigen dari ke-j dari \hat{L}_N (terurut berdasarkan dari nilai eigen terbesar hingga terkecil) yang dapat dikalkulasi dengan cara sebagai berikut:

\displaystyle \gamma_j = \frac{\sigma_j}{N}

\displaystyle \psi_j (\cdot) = \frac{1}{\sqrt{\sigma_j}} \sum_{i=1}^{N} v^{(i)}_j k(\mathbf{x}^{(i)}, \cdot) \quad \quad \quad (3),

dimana \sigma_j dan \mathbf{v}_j merupakan nilai dan vektor eigen ke-j dari matriks kernel \mathbf{K} = [ k( \mathbf{x}^{(i)}, \mathbf{x}^{(j)}) ]_{ij} \in \mathbb{R}^{N \times N}. Pengertian mengenai eigenvector, eigenvalue, dan eigenfunction serta bagaimana proses penghitungannya tidak saya jelaskan secara detil di sini (lihat, e.g., http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors).

Dalam konteks linear regression, sebuah teori mengatakan bahwa fungsi prediksi target g : \mathcal{H} \rightarrow \mathbb{R} dapat diaproksimasi dengan kombinasi linear dari s buah eigenfunction (3), dimana s << N, yang terturut berdasarkan nilai eigen \gamma_1 \geq \gamma_2 \geq ... \geq \gamma_s

\displaystyle \hat{g}(\mathbf{x}) = \sum_{j=1}^{s} \hat{\beta}_j \psi_j(\mathbf{x}) \quad \quad \quad (4)

dimana \hat{g}(\mathbf{x}) \approx g(\mathbf{x}).

Ringkasan Algoritma

Dengan demikian, diberikan himpunan semua data \mathcal{D} = \{ \mathbf{x}^{(i)} \}_{i=1}^{N} = \{ \mathbf{x}^{(i)} \}_{i=1}^{n_l} \cup \{ \mathbf{x}^{(i)} \}_{i=1}^{n_u}, tahap demi tahap algoritma dapat diringkas sebagai berikut:

  1. Hitung matriks kernel \mathbf{K} = [k( \mathbf{x}^{(i}), \mathbf{x}^{(j)}]_{ij} \in \mathbb{R}^{N \times N}.
  2. Hitung nilai dan vektor eigen dari matriks kernel \mathbf{K}, yaitu \{ \sigma_j, \mathbf{v}_j \}_{j \geq 1}.
  3. Hitung nilai dan fungsi eigen dari integral operator \hat{L}_N yaitu \{ \gamma_j, \psi_j \}_{j \geq 1} dengan mengunakan persamaan (3).
  4. Ambil s fungsi eigen \{ \psi_j \}_{j=1}^{s} yang terurut berdasarkan dari nilai eigen terbesar hingga yang terkecil, lalu selesaikan objective di bawah ini

\displaystyle \hat{\boldsymbol{\beta}} := \arg \min_{\boldsymbol{\beta} \in \mathbb{R}^s} \sum_{i=1}^{n_l} \left( \sum_{j=1}^{s} \beta_j \psi_j( \mathbf{x}^{(i)}) - y^{(i)} ) \right)^{2} \quad \quad \quad (5)

Langkah 3 – 4 dapat dipersingkat menjadi 1 buah persamaan matriks-vektor saja, yaitu

\displaystyle \hat{\boldsymbol{\beta}}= \boldsymbol{\Lambda}^{\frac{1}{2}} ( \mathbf{V}^{\top} \mathbf{K}_l \mathbf{K}^{\top}_l \mathbf{V} )^{-1} \mathbf{V}^{\top} \mathbf{K}_l \mathbf{y} \quad \quad \quad (6)

dimana \mathbf{K}_l =\mathbf{K}(:, 1:n_l) \in \mathbb{R}^{N \times n_l} merupakan sub-matriks kernel yang kolom-kolomnya hanya berisi data berlabel, \mathbf{V} \in \mathbb{R}^{N \times s} merupakan matriks yang tiap kolomnya berisi vektor-vektor eigen dari \mathbf{K}, dan \boldsymbol{\Lambda} = diag(\sigma_1, ..., \sigma_s) \in \mathbb{R}^{s \times s} merupakan matriks diagonal yang diagonalnya berisi s nilai eigen terbesar dari \mathbf{K}. Perlu diketahui bahwa matriks \mathbf{V} dan \mathbf{\Lambda} dapat dihitung dengan mendekomposisi matriks \mathbf{K} sedemikian rupa sehingga

\displaystyle \mathbf{K} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^{\top}

Dekomposisi ini biasa dikenal dengan istilah Eigendecomposition.

Perhatikan bahwa terdapat sedikit perbedaan antara ekspresi (1) dengan (5). Objektif (5) menggunakan fungsi eigen sebagai input, dimana (1) menggunakan feature map. Karena fungsi eigen ini dihitung dari matriks kernel yang berisi baik data berlabel maupun yang tidak berlabel, maka secara implisit fungsi eigen mengakomodir semua data, sedangkan feature map hanya mengakomodir data berlabel saja.

2. Metode Nystrom

Pada umumnya, metode berbasis kernel akan menghasilkan dimensi matriks kernel \mathbf{K} \in \mathbb{R}^{N \times N} yang semakin besar dengan bertambahnya jumlah data latih. Hal ini akan menyebabkan kompleksitas komputasi, baik dari segi waktu maupun memori akan semakin besar. Metode Nystrom menyediakan untuk mengurangi kompleksitas komputasi dengan cara memperkecil dimensi matriks kernel tanpa banyak kehilangan performa.

Bagaimana strategi memperkecil ukuran matriks kernel? Cukup mengagetkan karena strateginya sangat simpel, yaitu membuang baris dan kolom dari matriks kernel \mathbf{K} yang dipilih secara acak (dengan catatan, kolom dan baris yang dihilangkan memiliki indeks yang sama). Hasil akhir dari proses ini menghasilkan kernel matriks yang lebih kecil \tilde{\mathbf{K}} \in \mathbb{R}^{m \times m}, m \ll N setelah membuang N - m baris dan kolom \mathbf{K}.

Teori yang menjelaskan mengapa \tilde{\mathbf{K}} dapat mengaproksimasi \mathbf{K} ini cukup rumit. Namun demikian, dari teori tersebut dapat diverifikasi bahwa

\displaystyle \mathbf{K} \approx \mathbf{B} \tilde{\mathbf{K}} \mathbf{B}^{\top}

dimana \mathbf{B} \in \mathbb{R}^{N \times m} merupakan matriks yang didapatkan dengan hanya menghilangkan N-m kolom dari matriks \mathbf{K}.

3. SSSL + Nystrom

Sekarang kita akan coba mengaplikasikan metode Nystrom pada algoritma SSSL, yaitu dengan mengganti matriks kernel \mathbf{K} \in \mathbb{R}^{N \times N} dengan \tilde{\mathbf{K}} \in \mathbb{R}^{m \times m}. Namun di sini saya sedikit melakukan modifikasi pada persamaan (5) menjadi problem Ridge Regression sebagai berikut:

\displaystyle \hat{\boldsymbol{\beta}} := \arg \min_{\boldsymbol{\beta} \in \mathbb{R}^s} \sum_{i=1}^{n_l} \left( \sum_{j=1}^{s} \beta_j \tilde{\psi}_j( \mathbf{x}^{(i)}) - y^{(i)} ) \right)^{2} + \lambda \sqrt{ \sum_{j=1}^{s} \beta^2_j} \quad \quad \quad (7)

Pada persamaan di atas, \tilde{\psi}_j merepresentasikan fungsi eigen dari integral operator (2) dengan kernel matriks \tilde{\mathbf{K}} \in \mathbb{R}^{m \times m} hasil dari metode Nystrom.

Solusi dari objektif (7) dapat dinyatakan dengan persamaan

\displaystyle \hat{\boldsymbol{\beta}}= \tilde{\boldsymbol{\Lambda}}^{\frac{1}{2}} ( \tilde{\mathbf{V}}^{\top} \tilde{\mathbf{K}}_l \tilde{\mathbf{K}}^{\top}_l \tilde{\mathbf{V}} + \lambda \mathbf{I}_{ss})^{-1} \tilde{\mathbf{V}}^{\top} \tilde{\mathbf{K}}_l \mathbf{y} \quad \quad \quad (8)

dimana \tilde{\mathbf{K}}_l \in \mathbb{R}^{m \times n_l}, matriks \mathbf{I}_{ss} merupakan matriks identitas berdimensi s \times s, serta matriks \tilde{\mathbf{V}} \in \mathbb{R}^{m \times s} dan \tilde{\boldsymbol{\Lambda}} \in \mathbb{R}^{s \times s} masing-masing berisi nilai dan vektor eigen dari matriks kernel \tilde{\mathbf{K}} \in \mathbb{R}^{m \times m}.

Algoritma SSSL termodifikasi ini saya beri nama SSSL_m, dan yang asli saya namakan SSSL_N.

4. Eksperimen

Pada eksperimen kali ini, kita akan mengevaluasi kemampuan SSSL_N dan SSSL_m dalam melakukan prediksi label dari gambar objek berupa angka, i.e., handwritten digit classification.

Dataset: USPS vs MNIST

Untuk mensimulasikan domain adaptation, saya menggunakan 2 buah handwritten digit data sets, yaitu USPS dan MNIST, dengan konfigurasi persis seperti yang dilakukan oleh Long et al. CVPR2013. USPS digunakan sebagai source domain, yaitu data berlabel \mathcal{D}_l = \{\mathbf{x}^{(i)}, y^{(i)} \}_{i=1}^{n_l} dengan jumlah n_l = 1800, dan MNIST digunakan sebagai target domain, i.e., data tidak berlabel \mathcal{D}_u = \{ \mathbf{x}^{(i)}\}_{i=1}^{n_u}, n_u = 2000. Jadi, total data dari keseluruhan domain berjumlah N = 3800.

Sebagai ilustrasi bagaimana bentuk dan karakteristik dari digit yang kita gunakan, berikut ini beberapa sampel dari USPS dan MNIST.

Di sini jelas terlihat perbedaan style dari masing-masing datasets. Kita akan mengevaluasi seberapa jauh SSSL dapat mengenali digit pada MNIST (target domain) tanpa diberikan informasi mengenai labelnya sedikit pun. Informasi label hanya dapat diakses dari USPS (source domain).

HASIL EVALUASI

Sebagai perbandingan, kita menggunakan 3 buah baselines: 1) Linear Regression (LR), 2) Ridge Regression (RR), dan 3) Kernel Ridge Regression, yang merupakan algoritma supervised learning, dimana SSSL_N dan SSSL_m seperti yang telah kita ketahui. sebelumnya. Ini bertujuan untuk melihat apakah keterlibatan data tidak berlabel dari target domain selama proses learning benar-benar mampu meningkatkan akurasi klasifikasi.

Hyper-parameters dari semua model di-tuning dengan menggunakan grid search. Jenis kernel yang digunakan untuk KRR dan SSSL adalah Gaussian kernel. Khusus untuk SSSL_m, percobaan dilakukan 10x karena terdapat proses randomisasi ketika menghasilkan matriks kernel dengan metode Nystrom, lalu diambil rata-rata dan standar deviasi dari akurasinya. Hasil klasifikasi dalam persentasi akurasi beserta waktu eksekusinya ditampilkan pada tabel di bawah ini:

Model

Source accuracy (%) Target accuracy (%)

Elapsed time (seconds)

LR

95.17

20.00

0.02

RR (\lambda=1)

90.28

33.75  0.08
KRR (\lambda=1, \sigma=0.06)  100  34.85 3.72
SSSL_N (s=120, \sigma=0.31, \lambda=0.4)  94.61 44.30  113.5
SSSL_M (m=400, \sigma=0.31, \lambda=0.4)  94.81 \pm 0.51  42.33 \pm 2.50  3.87

Dari tabel terlihat dengan jelas bahwa SSSL memberikan dampak yang signifikan terhadap peningkatan target accuracy bila dibandingkan dengan 3 buah supervised learning baselines. Ini berarti SSSL cukup efektif untuk digunakan sebagai model domain adaptation.

Dari segi waktu eksekusi antara SSSL_N dan SSSL_m, algoritma pembelajaran SSSL_m dieksekusi jauh lebih cepat dibandingkan SSSL_N. Hal yang lebih penting lagi, kemampuan akurasi dari SSSL_m tidak menurun drastis walaupun dengan menggunakan matriks kernel \tilde{\mathbf{K}} dengan dimensi yang relatif kecil, yaitu  400 \times 400, bila dibangingkan matriks kernel pada SSSL_N yang berdimensi 3800 \times 3800. Ini sesuai yang ekspektasi yang dibahas pada teori metode Nystrom sebelumnya.

Selanjutnya, saya tertarik untuk membuat SSSL_m memiliki kemampuan akurasi yang melebihi SSSL_N. Jadi, nantinya kita akan membuat algoritma berbasis kernel yang lebih cepat dan lebih akurat. Bagaimana cara melakukan? Hingga saat ini masih on-going. 🙂

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