Penyematan dalam Pembelajaran Mesin: Membuat Data Kompleks Menjadi Sederhana

Bekerja dengan data non-numerik bisa jadi sulit, bahkan untuk ilmuwan data berpengalaman. Model pembelajaran mesin yang khas mengharapkan fitur-fiturnya berupa angka, bukan kata-kata, email, halaman situs web, daftar, grafik, atau distribusi probabilitas. Agar berguna, data harus ditransformasikan ke dalam ruang vektor terlebih dahulu. Tapi bagaimana caranya?

Salah satu pendekatan yang populer adalah memperlakukan fitur non-numerik sebagai categorical . Ini dapat berjalan dengan baik jika jumlah kategorinya kecil (misalnya, jika data menunjukkan suatu profesi atau negara). Namun, jika kami mencoba menerapkan metode ini ke email, kemungkinan besar kami akan mendapatkan kategori sebanyak sampel yang ada. Tidak ada dua email yang persis sama, maka pendekatan ini tidak akan berguna.

Pendekatan lain adalah dengan menentukan jarak antara sampel data , sebuah fungsi yang memberi tahu kita seberapa dekat dua sampel. Atau kita dapat mendefinisikan ukuran kesamaan , yang akan memberi kita informasi yang sama kecuali bahwa jarak antara dua sampel yang dekat adalah kecil sedangkan kemiripannya besar. Jarak komputasi (kesamaan) antara semua sampel data akan memberi kita matriks jarak (atau kesamaan). Ini adalah data numerik yang bisa kita gunakan.

Namun, data ini akan memiliki dimensi sebanyak sampel yang ada, yang biasanya tidak bagus jika kita ingin menggunakannya sebagai fitur (lihat kutukan dimensi) atau untuk memvisualisasikannya (sementara satu plot dapat menangani bahkan 6D, saya belum untuk melihat plot 100D). Bisakah kita mengurangi jumlah dimensi ke jumlah yang wajar?

Jawabannya iya! Untuk itulah kami memiliki embeddings .

Apa Itu Embedding dan Mengapa Menggunakannya?

Embedding adalah representasi dimensi rendah dari data dimensi tinggi. Biasanya, penyematan tidak akan menangkap semua informasi yang terkandung dalam data asli. Sebuah embedding yang baik, bagaimanapun, akan menangkap cukup untuk memecahkan masalah yang dihadapi.

Ada banyak embedding yang disesuaikan untuk struktur data tertentu. Misalnya, Anda mungkin pernah mendengar tentang word2vec untuk data teks, atau deskriptor Fourier untuk data gambar bentuk. Sebagai gantinya, kita akan membahas bagaimana menerapkan penyematan ke data apa pun di mana kita dapat menentukan jarak atau ukuran kesamaan. Selama kita dapat menghitung matriks jarak, sifat data sama sekali tidak relevan. Ini akan bekerja sama, baik itu email, daftar, pohon, atau halaman web.

Dalam artikel ini, kami akan memperkenalkan Anda ke berbagai jenis penyematan dan membahas cara kerja beberapa penyematan populer dan bagaimana kami dapat menggunakan penyematan untuk memecahkan masalah dunia nyata yang melibatkan data kompleks. Kami juga akan membahas pro dan kontra dari metode ini, serta beberapa alternatif. Ya, beberapa masalah dapat diselesaikan dengan lebih baik dengan cara lain, tetapi sayangnya, tidak ada peluru perak dalam pembelajaran mesin.

Mari kita mulai.

Cara Kerja Penyematan

Semua penyematan berusaha mengurangi dimensi data sambil mempertahankan informasi "penting" dalam data, tetapi setiap penyematan melakukannya dengan caranya sendiri. Di sini, kita akan membahas beberapa embeddings populer yang dapat diterapkan pada matriks jarak atau kesamaan.

Kami bahkan tidak akan mencoba untuk menutupi semua embeddings di luar sana. Setidaknya ada selusin embeddings terkenal yang bisa melakukan itu dan banyak lagi embeddings yang kurang dikenal dan variasinya. Masing-masing memiliki pendekatan, kelebihan, dan kekurangannya sendiri.

Jika Anda ingin melihat penyematan lain di luar sana, Anda bisa mulai di sini:

• Panduan Pengguna Scikit-belajar
• Elemen Pembelajaran Statistik (Edisi Kedua), Bab 14

Matriks Jarak

Mari kita secara singkat menyentuh matriks jarak. Menemukan jarak yang tepat untuk data membutuhkan pemahaman yang baik tentang masalah, beberapa pengetahuan matematika, dan terkadang keberuntungan . Dalam pendekatan yang dijelaskan dalam artikel ini, itu mungkin merupakan faktor terpenting yang berkontribusi pada keberhasilan atau kegagalan proyek Anda secara keseluruhan.

Anda juga harus mengingat beberapa detail teknis. Banyak algoritma penyisipan akan mengasumsikan bahwa matriks jarak (atau ketidaksamaan ) $\textbf{D}$ memiliki nol pada diagonalnya dan simetris. Jika tidak simetris, kita dapat menggunakan $(\textbf{D} + \textbf{D}^T) / 2$ sebagai gantinya. Algoritma yang menggunakan trik kernel juga akan mengasumsikan bahwa jarak adalah metrik, yang berarti bahwa pertidaksamaan segitiga berlaku:

\[\untuk semua a, b, c \;\; d(a,c) \leq d(a,b) + d(b,c)\]

Juga, jika suatu algoritma membutuhkan matriks kesamaan, kita dapat menerapkan fungsi pengurang monoton apa pun untuk mengubah matriks jarak menjadi matriks kesamaan: misalnya, $\exp -x$.

Analisis Komponen Utama (PCA)

Analisis Komponen Utama, atau PCA, mungkin merupakan penyematan yang paling banyak digunakan hingga saat ini. Idenya sederhana: Temukan transformasi linier fitur yang memaksimalkan varians yang ditangkap atau (setara) meminimalkan kesalahan rekonstruksi kuadrat .

Secara khusus, biarkan fitur menjadi matriks sampel $\textbf{X} \in \mathbb{R}^{n \times p}$ memiliki fitur $n$ dan dimensi $p$. Untuk mempermudah, mari kita asumsikan bahwa rata-rata sampel data adalah nol. Kita dapat mengurangi jumlah dimensi dari $p$ menjadi $q$ dengan mengalikan $\textbf{X}$ dengan matriks ortonormal $\textbf{V}_q \in \mathbb{R}^{p \times q}$ :

\[\hat{\textbf{X}} = \textbf{X} \textbf{V}_q\]

Kemudian, $\hat{\textbf{X}} \in \mathbb{R}^{n \times q}$ akan menjadi kumpulan fitur baru. Untuk memetakan fitur baru kembali ke ruang aslinya (operasi ini disebut rekonstruksi ), kita hanya perlu mengalikannya lagi dengan $\textbf{V}_q^T$.

Sekarang, kita akan menemukan matriks $\textbf{V}_q$ yang meminimalkan kesalahan rekonstruksi:

\[\min_{\textbf{V}_q} ||\textbf{X}\textbf{V}_q\textbf{V}_q^T - \textbf{X}||^2\]

Kolom-kolom matriks $\textbf{V}_q$ disebut arah komponen utama, dan kolom $\hat{\textbf{X}}$ disebut komponen utama. Secara numerik, kita dapat menemukan $\textbf{V}_q$ dengan menerapkan dekomposisi SVD ke $\textbf{X}$, meskipun ada cara lain yang sama validnya untuk melakukannya.

PCA dapat diterapkan langsung ke fitur numerik. Atau, jika fitur kami non-numerik, kami dapat menerapkannya pada matriks jarak atau kesamaan.

Jika Anda menggunakan Python, PCA diimplementasikan di scikit-learn.

Keuntungan dari metode ini adalah cepat dalam menghitung dan cukup kuat terhadap noise dalam data.

Kerugiannya adalah ia hanya dapat menangkap struktur linier, sehingga informasi non-linier yang terkandung dalam data asli kemungkinan besar akan hilang.

PCA kernel

Kernel PCA adalah versi non-linear dari PCA. Idenya adalah menggunakan trik kernel , yang mungkin pernah Anda dengar jika Anda terbiasa dengan Support Vector Machines SVM.

Secara khusus, ada beberapa cara berbeda untuk menghitung PCA. Salah satunya adalah menghitung dekomposisi eigen dari matriks gram versi dua pusat $\textbf{X} \textbf{X}^T \in \mathbb{R}^{n \times n}$. Sekarang, jika kita menghitung matriks kernel $\textbf{K} \in \mathbb{R}^{n \times n}$ untuk data kita, PCA Kernel akan memperlakukannya sebagai matriks gram untuk menemukan komponen utama.

Biarkan $x_i$, $i \in {1,..,n}$ menjadi contoh fitur. Matriks kernel didefinisikan oleh fungsi kernel $K(x_i,x_j)=\langle \phi(x_i),\phi(x_j) \rangle$.

Pilihan yang populer adalah kernel radial:

\[K(x_i,x_j)=\exp -\gamma \cdot d(x_i,x_j)\]

di mana $d$ adalah fungsi jarak.

Kernel PCA mengharuskan kita untuk menentukan jarak. Misalnya, untuk fitur numerik, kita dapat menggunakan jarak Euclidean: $d(x_i,x_j)=\vert\vert x_i-x_j \vert \vert ^2$.

Untuk fitur non-numerik, kita mungkin perlu berkreasi. Satu hal yang perlu diingat adalah bahwa algoritma ini mengasumsikan jarak kita sebagai metrik.

Jika Anda menggunakan Python, Kernel PCA diimplementasikan di scikit-learn.

Keuntungan dari metode Kernel PCA adalah dapat menangkap struktur data non-linear.

Kerugiannya adalah sensitif terhadap noise dalam data dan pilihan jarak dan fungsi kernel akan sangat mempengaruhi hasil.

Penskalaan Multidimensi (MDS)

Penskalaan multidimensi (MDS) mencoba menjaga jarak antar sampel secara global. Idenya cukup intuitif dan bekerja dengan baik dengan matriks jarak.

Secara khusus, sampel fitur yang diberikan $x_i$, $i \in {1,..,n}$ dan fungsi jarak $d$, kami menghitung sampel fitur baru $z_i \in \mathbb{R}^{q}$, $i \in {1,..,n}$ dengan meminimalkan fungsi tegangan :

\[\min_{z_1,..,z_n} \sum_{1 \leq i < j \leq n} (d(x_i, x_j) - ||z_i - z_j||)^2\]

Jika Anda menggunakan Python, MDS diimplementasikan di scikit-learn. Namun, scikit-learn tidak mendukung transformasi titik di luar sampel, yang mungkin merepotkan jika kita ingin menggunakan penyematan bersama dengan model regresi atau klasifikasi. Namun, pada prinsipnya, itu mungkin.

Keuntungan dari MDS adalah bahwa idenya sangat sesuai dengan kerangka kerja kami dan tidak terlalu terpengaruh oleh noise dalam data.

Kekurangannya adalah implementasinya di scikit-learn cukup lambat dan tidak mendukung transformasi out-of-sample.

Kasus Penggunaan: Pelacakan Pengiriman

Beberapa pemukiman di pulau tropis kecil telah mengembangkan layanan pengiriman paket untuk melayani industri pariwisata lokal. Seorang pedagang di salah satu pemukiman ini memutuskan untuk mengambil tindakan untuk mendapatkan keunggulan dalam persaingan, jadi dia membuat sistem pengawasan satelit yang melacak semua pengiriman paket di pulau itu. Setelah data dikumpulkan, pedagang memanggil ilmuwan data (itu kami!) untuk membantunya menjawab pertanyaan berikut: Bisakah kami memprediksi tujuan paket yang sedang dalam perjalanan?

Dataset berisi informasi tentang 200 pengiriman terlacak. Untuk setiap pengiriman terlacak, ada daftar (x,y)-koordinat dari semua lokasi di mana paket itu terlihat, yang biasanya antara 20 dan 50 pengamatan. Plot di bawah ini menunjukkan bagaimana data ini terlihat.

Data ini terlihat seperti masalah—dua jenis masalah yang berbeda, sebenarnya.

Masalah pertama adalah bahwa data yang kita hadapi berdimensi tinggi. Misalnya, jika setiap paket ditemukan di 50 lokasi, data kami akan memiliki 100 dimensi—kedengarannya sangat banyak, dibandingkan dengan 200 sampel yang Anda miliki.

Masalah kedua: Rute pengiriman yang berbeda sebenarnya memiliki jumlah pengamatan yang berbeda, jadi kita tidak bisa begitu saja menumpuk daftar dengan koordinat untuk mewakili data dalam bentuk tabel (dan bahkan jika ada, itu masih tidak masuk akal).

Pedagang itu dengan tidak sabar menggedor meja dengan jari-jarinya, dan ilmuwan data berusaha keras untuk tidak menunjukkan tanda-tanda kepanikan.

Di sinilah matriks jarak dan embeddings akan berguna. Kami hanya perlu menemukan cara untuk membandingkan dua rute pengiriman. Jarak Frechet tampaknya menjadi pilihan yang masuk akal. Dengan jarak, kita dapat menghitung matriks jarak.

Catatan: Langkah ini mungkin memakan waktu cukup lama. Kita perlu menghitung jarak $O(n^2)$ dengan setiap jarak memiliki $O(k^2)$ iterasi, di mana $n$ adalah jumlah sampel dan $k$ adalah jumlah pengamatan dalam satu sampel. Menulis fungsi jarak secara efisien adalah kuncinya. Misalnya, dengan Python, Anda bisa menggunakan numba untuk mempercepat perhitungan ini berkali-kali lipat.

Memvisualisasikan Penyematan

Sekarang, kita dapat menggunakan embedding untuk mengurangi jumlah dimensi dari 200 menjadi hanya beberapa. Kami dapat melihat dengan jelas bahwa hanya ada beberapa jalur perdagangan, jadi kami berharap dapat menemukan representasi data yang baik bahkan dalam dua atau tiga dimensi. Kami akan menggunakan embeddings yang telah kami bahas sebelumnya: PCA, Kernel PCA, dan MDS.

Pada plot di bawah ini, Anda dapat melihat data rute berlabel (diberikan untuk demonstrasi) dan representasinya dengan penyematan dalam 2D ​​dan 3D (dari kiri ke kanan). Data berlabel menandai empat pos perdagangan yang dihubungkan oleh enam jalur perdagangan. Dua dari enam rute perdagangan adalah dua arah, yang membuat total delapan grup pengiriman (6+2). Seperti yang Anda lihat, kami mendapatkan pemisahan yang cukup jelas dari kedelapan grup pengiriman dengan penyematan 3D.

Ini adalah awal yang baik.

Penyematan dalam Model Pipeline

Sekarang, kita siap untuk melatih sebuah embedding. Meskipun MDS menunjukkan hasil terbaik, ini agak lambat; juga, implementasi scikit-learn tidak mendukung transformasi di luar sampel. Ini tidak masalah untuk penelitian tetapi bisa untuk produksi, jadi kami akan menggunakan Kernel PCA sebagai gantinya. Untuk Kernel PCA, jangan lupa untuk menerapkan kernel radial ke matriks jarak terlebih dahulu.

Bagaimana Anda memilih jumlah dimensi keluaran? Analisis menunjukkan bahwa bahkan 3D berfungsi dengan baik. Agar aman dan tidak meninggalkan informasi penting apa pun, mari atur output embedding ke 10D. Untuk kinerja terbaik, jumlah dimensi keluaran dapat diatur sebagai parameter hiper model dan kemudian disetel dengan validasi silang.

Jadi, kita akan memiliki 10 fitur numerik yang dapat kita gunakan sebagai masukan untuk hampir semua model klasifikasi. Bagaimana dengan satu model linier dan satu non-linier: katakanlah, Regresi Logistik dan Peningkatan Gradien? Sebagai perbandingan, mari kita juga menggunakan kedua model ini dengan matriks jarak penuh sebagai input. Selain itu, mari kita uji SVM juga (SVM dirancang untuk bekerja dengan matriks jarak secara langsung, jadi tidak diperlukan penyematan).

Keakuratan model pada set uji ditunjukkan di bawah ini (10 rangkaian data kereta dan uji dihasilkan sehingga kami dapat memperkirakan varians model):

• Gradient Boosting yang dipasangkan dengan embedding (KernelPCA+GB) mendapat tempat pertama. Ini mengungguli Gradient Boosting tanpa embedding (GB). Di sini, Kernel PCA terbukti bermanfaat.
• Regresi Logistik tidak apa-apa. Yang menarik adalah bahwa Regresi Logistik tanpa penyematan (LR) lebih baik daripada dengan penyematan (KernelPCA+LR). Ini tidak sepenuhnya tidak terduga. Model linier tidak terlalu fleksibel tetapi relatif sulit untuk dikenakan overfit. Di sini, hilangnya informasi yang disebabkan oleh penyematan tampaknya lebih besar daripada manfaat dimensi input yang lebih kecil.
• Last but not least, SVM juga berkinerja baik, meskipun varians model ini cukup signifikan.

Akurasi Model

Kode Python untuk kasus penggunaan ini tersedia di GitHub.

Kesimpulan

Kami telah menjelaskan apa itu embeddings dan mendemonstrasikan bagaimana embeddings dapat digunakan bersama dengan matriks jarak untuk memecahkan masalah dunia nyata. Waktu untuk putusan:

Apakah penyematan sesuatu yang harus digunakan oleh ilmuwan data? Mari kita lihat kedua sisi cerita.

Pro & Kontra Menggunakan Embeddings

Kelebihan:

• Pendekatan ini memungkinkan kita untuk bekerja dengan struktur data yang tidak biasa atau kompleks selama Anda dapat menentukan jarak, yang—dengan tingkat pengetahuan, imajinasi, dan keberuntungan tertentu—biasanya Anda dapat melakukannya.
  
• Outputnya adalah data numerik berdimensi rendah, yang dapat dengan mudah Anda analisis, klaster, atau gunakan sebagai fitur model untuk hampir semua model pembelajaran mesin di luar sana.

Kontra:

• Dengan menggunakan pendekatan ini, kita pasti akan kehilangan beberapa informasi:

  • Selama langkah pertama, ketika kami mengganti data asli dengan matriks kesamaan
  • Selama langkah kedua, saat kita mengurangi dimensi menggunakan embedding
• Tergantung pada data dan fungsi jarak, perhitungan matriks jarak mungkin memakan waktu. Ini dapat dikurangi dengan fungsi jarak tertulis yang efisien.
• Beberapa embeddings sangat sensitif terhadap noise dalam data. Ini dapat dikurangi dengan pembersihan data tambahan.
• Beberapa embedding sensitif terhadap pilihan hyper-parameternya. Ini dapat dikurangi dengan analisis yang cermat atau penyetelan hyper-parameter.

Alternatif: Mengapa Tidak Menggunakan…?

• Mengapa tidak menggunakan embedding langsung pada data, daripada matriks jarak?
  Jika Anda mengetahui penyematan yang dapat secara efisien menyandikan data Anda secara langsung, tentu saja, gunakan itu. Masalahnya adalah bahwa itu tidak selalu ada.
  
• Mengapa tidak menggunakan klasterisasi saja pada matriks jarak?
  Jika satu-satunya tujuan Anda adalah mengelompokkan kumpulan data Anda, tidak apa-apa untuk melakukannya. Beberapa metode klasterisasi juga memanfaatkan penyematan (misalnya, Pengelompokan Spektral). Jika Anda ingin mempelajari lebih lanjut, berikut adalah tutorial tentang klasterisasi.
  
• Mengapa tidak menggunakan matriks jarak sebagai fitur saja?
  Ukuran matriks jarak adalah $(n_{sampel}, n_{sampel})$. Tidak semua model dapat menanganinya secara efisien—beberapa mungkin overfit, beberapa mungkin lambat untuk menyesuaikan, beberapa mungkin gagal untuk menyesuaikan sama sekali. Model dengan varians rendah akan menjadi pilihan yang baik di sini, seperti model linier dan/atau reguler.
  
• Mengapa tidak menggunakan SVM saja dengan matriks jarak?
  SVM adalah model hebat, yang berkinerja baik dalam kasus penggunaan kami. Namun, ada beberapa peringatan. Pertama, jika kita ingin menambahkan fitur lain (bisa berupa angka numerik sederhana), kita tidak akan bisa melakukannya secara langsung. Kami harus memasukkannya ke dalam matriks kesamaan kami dan berpotensi kehilangan beberapa informasi berharga. Kedua, sebaik SVM, model lain mungkin bekerja lebih baik untuk masalah khusus Anda.
  
• Mengapa tidak menggunakan pembelajaran yang mendalam saja?
  Memang benar, untuk masalah apa pun, Anda dapat menemukan jaringan saraf yang cocok jika Anda mencari cukup lama. Namun, perlu diingat bahwa proses menemukan, melatih, memvalidasi, dan menerapkan jaringan saraf ini tidak selalu mudah. Jadi, seperti biasa, gunakan penilaian terbaik Anda.

Dalam Satu Kalimat

Penyematan dalam hubungannya dengan matriks jarak adalah alat yang sangat berguna jika Anda kebetulan bekerja dengan data non-numerik yang kompleks, terutama ketika Anda tidak dapat mengubah data Anda menjadi ruang vektor secara langsung dan lebih memilih untuk memiliki input berdimensi rendah untuk model Anda.