Just a chunk of mathematical proof about machine learning


Beberapa minggu yang lalu, saya sepertinya (masih menunggu hasil review) berhasil membuktikan sebuah teori tentang machine learning dalam konteks domain adaptation. Domain adaptation merupakan salah satu cabang yang relatif baru di machine learning yang concern dengan bagaimana caranya mengadaptasi / mentransfer pengetahuan sebuah learnt model di lingkungan/domain yang baru, lihat bagian 2 pada tulisan saya di sini.

Sebelumnya saya juga sempat menulis tentang salah satu algoritma yang saya rancang bernama Scatter Component Analysis (SCA). Salah satu teori penting dari SCA adalah hubungan antara 2 besaran jarak: domain scatter vs Maximum Mean Discrepancy (MMD), lihat Teorema 3 pada tulisan tersebut.

Kali ini saya coba menunjukkan secara matematis bahwa domain scatter dan MMD berhubungan dengan domain adaptation learning bound (yang berarti memang benar-benar mampu menghasilkan model domain adaptation yang baik), dengan meminjam sebuah framework dari Mansour et al. COLT 2009.

1. Discrepancy Distance & Domain Adaptation Bound

Alat utama yang digunakan oleh Mansour et al. 2009 adalah sebuah besaran jarak yang dinamakan dengan discrepancy distance. Sebelum menjelaskan tentang besaran ini, ada baiknya untuk mengenali notasi-notasi yang akan saya gunakan. Saya tulis

  • \mathcal{X} sebagai ruang input,
  • \mathcal{Y} sebagai ruang output (yang merupakan label dari \mathcal{X}),
  • H sebagai himpunan hypothesis,
  • h:\mathcal{X} \rightarrow \mathcal{Y} dan f:\mathcal{X} \rightarrow \mathcal{Y} sebagai hypothesis dan concept (lihat tulisan tentang PAC Learning),
  • \ell : \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}  sebagai loss function,
  • \mathcal{L}_{\mathbb{D}}(h, f) = \mathbb{E}_{x \sim \mathbb{D}}[\ell(h(x), f(x))] sebagai expected loss/risk, dimana \mathbb{D} merupakan distribusi probabilitas yang menghasilkan sampel x. Empirical loss ditulis sebagai \mathcal{L}_{\hat{\mathbb{D}}}(\cdot,\cdot)

Discrepancy distance didefinisikan sebagai berikut:

Definisi 1 (Discrepancy Distance). Misalkan H = \{h : \mathcal{X} \rightarrow \mathcal{Y}\} sebuah himpunan fungsi yang memetakan dari input \mathcal{X} ke output \mathcal{Y}, dan \mathbb{P} dan \mathbb{Q} merupakan distribusi probabilitas pada \mathcal{X}. Discrepancy distance, \mathrm{disc}, dapat dinyatakan:

\displaystyle \mathrm{disc}(\mathbb{P}, \mathbb{Q}) = \sup_{h, h' \in H} | \mathcal{L}_{\mathbb{P}}(h, h') -\mathcal{L}_{\mathbb{Q}}(h, h') |

Semakin kecil nilai dari discrepancy distance, semakin dekat pula jarak antar 2 buah probabilitas/domain. Dalam ranah praktis, kita membutuhkan algoritma learning yang dapat meminimalisir discrepancy distance agar dapat menghasilkan model domain adaptation yang efektif.

Secara matematis, kita tertarik dengan hubungan antara 2 buah loss function pada domain yang berbeda (\mathbb{P} dan \mathbb{Q}) yaitu \mathcal{L}_{\mathbb{P}}(\cdot, \cdot) dan \mathcal{L}_{\mathbb{Q}}(\cdot, \cdot)Discrepancy distance berperan sebagai jembatan antara kedua loss function tersebut. Misalkan f_{\mathbb{P}}: \mathcal{X} \rightarrow \mathcal{Y} dan f_{\mathbb{Q}}: \mathcal{X} \rightarrow \mathcal{Y} merupakan concept atau true labeling function dari masing-masing domain. h^*_{\mathbb{P}} := \arg \min \mathcal{L}_{\mathbb{P}}(h, f_{\mathbb{P}}) dan h^*_{\mathbb{Q}} := \arg \min \mathcal{L}_{\mathbb{Q}}(h, f_{\mathbb{Q}}) merupakan hipotesis-hipotesis optimal yang dihasilkan dari sebuah algoritma. Teorema di bawah ini menjelaskan hubungan antara loss function dari masing-masing domain dan discrepancy distance.

Teorema 1 (Domain Adaptation Bound). Untuk setiap hipotesis h \in H, dan fungsi loss \ell simetris serta memenuhi sifat triangle inequality, pertidaksamaan di bawah ini merupakan pertidaksamaan yang valid.

\mathcal{L}_{\mathbb{P}}(h, f_{\mathbb{P}}) \leq \mathcal{L}_{\mathbb{P}}( h^*_{\mathbb{P}} , f_{\mathbb{P}})+\mathcal{L}_{\mathbb{Q}}( h^*_{\mathbb{Q}} , f_{\mathbb{Q}})+\mathrm{disc}_{\ell}(\mathbb{P}, \mathbb{Q})+\mathcal{L}_{\mathbb{Q}}( h^*_{\mathbb{Q}} , h^*_{\mathbb{P}})

Bukti. Hasil teorema ini didapatkan dengan menggabungkan sifat triangle inequality

\mathcal{L}_{\mathbb{P}}(h, f_{\mathbb{P}}) \leq \mathcal{L}_{\mathbb{P}}(h, h^*_{\mathbb{Q}}) + \mathcal{L}_{\mathbb{P}}(h^*_{\mathbb{Q}}, h^*_{\mathbb{P}}) + \mathcal{L}_{\mathbb{P}}(h^*_{\mathbb{P}}, f_{\mathbb{P}})

dan Definisi 1.

2. Reproducing Kernel Hilbert Space (RKHS)

Teori yang akan saya buktikan memiliki asumsi utama bahwa ruang hypothesis H merupakan subset dari sebuah ruang \mathcal{H} yang dikenal sebagai reproducing kernel Hilbert space (RKHS). Secara formal, RKHS didefinisikan sebagai berikut.

Definisi 2 (Reproducing Kernel Hilbert Space, RKHS). Misalkan \mathcal{X} merupakan himpunan sebarang dan \mathcal{H} \in \{ f : \mathcal{X} \rightarrow \mathbb{R}\} merupakan ruang Hilbert pada \mathcal{X}. Definisikan sebuah evalution functional L_x : \mathcal{H} \rightarrow \mathbb{R}, yaitu L_x[h] := h(x), \forall h \in \mathcal{H}. Maka, \mathcal{H} dapat dikatakan sebagai sebuah RKHS jika fungsi L_x dibatasi oleh sebuah bilangan (bounded), yaitu untuk setiap x \in \mathcal{X}, terdapat A>0 sedemikian sehingga

\displaystyle | L_x[h] | = | h(x) | \leq A \| h\|_{\mathcal{H}}

Definisi di atas berimplikasi dengan fakta berikut: terdapat sebuah fungsi \phi: \mathcal{X} \rightarrow \mathcal{H} (yang disebut sebagai feature map) memenuhi persamaan

\displaystyle L_x[h] = \langle h, \phi(x) \rangle = h(x)\quad\quad\quad (1)

Memahami RKHS cukup sulit bagi yang belum familiar dengan ruang Hilbert dan, lebih umum lagi, functional analysis. Namun, yang hanya perlu diingat untuk kasus ini adalah bahwa RKHS merupakan sebuah himpunan berisi fungsi-fungsi, dimana fungsi-fungsi tersebut linear dan nilainya berbatas (bounded) — tidak pernah menghasilkan output tak hingga (+\infty atau -\infty).

3. Domain scatter vs discrepancy distance

Domain scatter \Psi(\mu_\mathbb{P}, \mu_\mathbb{Q}) merupakan sebuah besaran yang kami turunkan dari persamaan scatter ketika menerima 2 buah input domain \mathbb{P} dan \mathbb{Q}, lihat Definisi 2 dan Teorema 3 pada tulisan ini. Besaran ini merupakan elemen yang penting pada algoritma domain adaptation yang kami rancang, yaitu Scatter Component Analysis (SCA).

Teorema 3 pada tulisan sebelumnya menjelaskan hubungan antara domain scatter dengan maximum mean discrepancy (MMD), dimana teorema tersebut tetap valid apabila ruang fungsi \mathcal{F} diganti dengan RKHS \mathcal{H} dan \| f \|_{\mathcal{H}} \leq 1 untuk setiap f \in \mathcal{H}unit ball. Untuk lebih jelasnya, MMD pada unit ball RKHS \mathcal{H} diberikan oleh persamaan sebagai berikut:

\displaystyle \mathrm{MMD}_{\mathcal{H}}( \mathbb{P}, \mathbb{Q}) = \| \mu_\mathbb{P} - \mu_\mathbb{Q} \|_\mathcal{H} \quad\quad\quad(2),

dimana \mu_\mathbb{P}, \mu_\mathbb{Q} : \mathcal{X} \rightarrow \mathcal{H} merupakan mean map, lihat Definisi 1.

Tujuan kita sekarang adalah menemukan hubungan antara domain scatter dengan discrepancy distance (Definisi 1). Untuk merealisasikan hal ini, dibutuhkan sebuah alat tambahan yang disebut dengan multiplication operator.

Lemma 2. Misalkan L_2(\mathcal{X}) merupakan ruang Hilbert berisi fungsi-fungsi yang square integrable pada \mathcal{X}. Diberikan \varphi dan h \in L_2(\mathcal{X}), pertidaksamaan berikut ini terpenuhi:

\displaystyle \| \varphi \cdot h \|_2 \leq \| h \|_\infty \cdot \| f \|_2

Definisi 3 (Multiplication Operator). Untuk setiap \varphi \in L_2(\mathcal{X}) sedemikian sehingga \| \varphi \|_\infty \leq \infty, multiplication operator \mathbf{M}_{\varphi}: L_2(\mathcal{X}) \rightarrow L_2(\mathcal{X}) didefinisikan sebagai berikut:

\mathbf{M}_{\varphi}(h)(x) = \varphi(x) h(x)

Selanjutnya, teorema di bawah ini menjelaskan hubungan antara domain scatter dan discrepancy distance.

Teorema 3 (Domain Scatter vs Discrepancy Distance). Misalkan \ell(y, y') = (y - y')^2 merupakan fungsi loss kuadrat dan sebuah himpunan hypothesis:

\mathrm{Hyp} = \{ f \in \mathcal{H} : \| f \|_{\mathcal{H}} \leq 1\} \mbox{ dan } \| f \|_\infty \leq r \}.

Jika \mathbb{P}  dan \mathbb{Q} merupakan 2 buah domain pada \mathcal{X}, maka pertidaksamaan di bawah ini valid:

\mathrm{disc}_\ell(\mathbb{P}, \mathbb{Q}) \leq 8 r \sqrt{ \Psi_\phi( \{\mu_\mathbb{P}, \mu_\mathbb{Q} \})}

Bukti. Andaikan h, h' \in \mathrm{Hyp}. Dengan memanfaatkan Definisi 2 dan 3, perhatikan bahwa

\displaystyle | \mathcal{L}_\mathbb{P} (h, h') - \mathcal{L}_\mathbb{Q} (h, h')|

\displaystyle = \big| \mathbb{E}_{x \sim \mathbb{P}}[ ( h(x) - h'(x))^2] - \mathbb{E}_{x \sim \mathbb{Q}}[ (h(x) - h'(x))^2]\big|

\displaystyle = \big| \mathbb{E}_{x \sim \mathbb{P}}[ h(x) h(x) - 2 h(x) h'(x) + h'(x) h'(x)] - \mathbb{E}_{x \sim \mathbb{Q}}[h(x) h(x) - 2 h(x) h'(x) + h'(x) h'(x) ]\big|

\displaystyle = \big | \mathbb{E}_{x \sim \mathbb{P}}[ \langle \mathbf{M}_h h - 2 \mathbf{M}_{h'} h + \mathbf{M}_{h'} h', \phi(x) \rangle_{\mathrm{Hyp}} ] - \mathbb{E}_{x \sim \mathbb{Q}}[\langle \mathbf{M}_{h'} h - 2 \mathbf{M}_{h'} h + \mathbf{M}_{h'} h', \phi(x) \rangle_{\mathrm{Hyp}}] \big |

\displaystyle = \big | \langle \mathbf{M}_h h - 2 \mathbf{M}_{h'} h + \mathbf{M}_{h'} h', \mu_\mathbb{P} - \mu_\mathbb{Q} \rangle_{\mathrm{Hyp}} \big |.

Dengan menggunakan Cauchy-Schwartz dan definisi dari MMD pada RKHS \mathcal{H} (persamaan 2),

\displaystyle \big| \mathcal{L}_\mathbb{P}(h, h') - \mathcal{L}_\mathbb{Q}(h, h')\big|

\displaystyle \leq \| \mathbf{M}_h h - 2 \mathbf{M}_{h'} h + \mathbf{M}_{h'} h' \|_{\mathrm{Hyp}} \cdot \| \mu_\mathbb{P} - \mu_\mathbb{Q}\|_\mathrm{Hyp}

\displaystyle \leq \big( \| \mathbf{M}_h h \|_\mathrm{Hyp} + 2 \| \mathbf{M}_{h'} h \|_\mathrm{Hyp} + \| \mathbf{M}_{h'} h'\|_\mathrm{Hyp}\big) \cdot \mathrm{MMD}_{\mathrm{Hyp}}[\mathbb{P}, \mathbb{Q}]

\displaystyle \leq \big( \| h \|_\infty \| h \|_{\mathrm{Hyp}} + 2 \| h'\|_\infty \| h \|_\mathrm{Hyp} + \| h' \|_\infty \| h' \|_\mathrm{Hyp} \big) \cdot \mathrm{MMD}_\mathrm{Hyp}[\mathbb{P}, \mathbb{Q}]

\displaystyle \leq 4r \cdot \mathrm{MMD}_\mathrm{Hyp}[\mathbb{P}, \mathbb{Q}],

dimana pertidaksamaan di baris ke-2 terakhir didapatkan melalui Lemma 2. Dengan komputasi langsung menggunakan Teorema 3 di tulisan ini, maka teorema ini terbukti.

4. Domain adaptation bound dengan domain scatter

Dikarenakan sekarang kita telah mengetahui hubungan antara discrepancy distance dan domain scatter, maka kita dapat dengan mudah menurunkan adaptation bound (Teorema 1) untuk domain scatter. Ini dilakukan dengan cara mensubstitusi disc_{\ell}(\mathbb{P}, \mathbb{Q}) dengan hasil yang didapatkan pada Teorema 3, sehingga menghasilkan teorema di bawah ini.

Teorema 4 (Adaptation bound dengan domain scatter). Dengan asumsi yang sama seperti di Teorema 1 dan 3, untuk setiap h \in \mathrm{Hyp}, dengan probabilitas paling kecil sebesar 1-\delta, pertidaksamaan di bawah ini terpenuhi:

\displaystyle \mathcal{L}_\mathbb{P} (h, f_\mathbb{P}) - \mathcal{L}_\mathbb{P}(h^*_\mathbb{P}, f_\mathbb{P}) \leq \mathcal{L}_\mathbb{Q} (h^*_\mathbb{Q}, f_\mathbb{Q}) + 8r \sqrt{\Psi_\phi(\mu_\mathbb{P}, \mu_\mathbb{Q})} + \mathcal{L}_\mathbb{Q}(h^*_\mathbb{Q}, h^*_\mathbb{P})

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