Faktorisasi Matriks

Faktorisasi matriks adalah model penyematan sederhana. Dengan matriks masukan A \(\in R^{m \times n}\), dengan \(m\) adalah jumlah pengguna (atau kueri) dan \(n\) adalah jumlah item, model mempelajari:

• Matriks penyematan pengguna \(U \in \mathbb R^{m \times d}\), dengan baris i adalah penyematan untuk pengguna i.
• Matriks penyematan item \(V \in \mathbb R^{n \times d}\), dengan baris j adalah penyematan untuk item j.

Embeddings itu dipelajari sehingga produknya \(U V^T\) merupakan perkiraan yang baik dari matriks masukan A. Perhatikan bahwa \((i, j)\) entri \(U . V^T\) hanyalah produk titik \(\langle U_i, V_j\rangle\) dari penyematan pengguna \(i\) dan item \(j\), yang ingin Anda dekatkan dengan \(A_{i, j}\).

Catatan: Faktorisasi matriks biasanya memberikan representasi yang lebih ringkas daripada mempelajari matriks lengkap. Matriks penuh memiliki \(O(nm)\) entri, sedangkan matriks penyematan \(U, \ V\) memiliki \(O((n+m)d)\) entri, dengan dimensi penyematan \(d\) biasanya jauh lebih kecil dari \(m\) dan \(n\). Akibatnya, faktorisasi matriks menemukan struktur laten dalam data, dengan asumsi bahwa observasinya berada dekat dengan subruang berdimensi rendah. Pada contoh sebelumnya, nilai n, m, dan d sangat rendah sehingga manfaatnya dapat diabaikan. Namun, dalam sistem rekomendasi dunia nyata, faktorisasi matriks dapat jauh lebih ringkas daripada mempelajari matriks lengkap.

Memilih Fungsi Tujuan

Salah satu fungsi tujuan yang intuitif adalah jarak kuadrat. Untuk melakukannya, kurangi jumlah error kuadrat pada semua pasangan entri yang diamati:

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2.\]

Dalam fungsi tujuan ini, Anda hanya menjumlahkan pasangan yang diamati (i, j), yaitu, lebih dari nilai bukan nol dalam matriks masukan. Namun, menjumlahkan nilai hanya satu saja bukan ide yang bagus—matriks semuanya akan memiliki kerugian minimal dan menghasilkan model yang tidak dapat membuat rekomendasi yang efektif dan menggeneralisasi dengan buruk.

Mungkin Anda dapat memperlakukan nilai yang tidak diamati sebagai nol, dan menjumlahkan semua entri dalam matriks. Ini sama dengan meminimalkan jarak Frobenius kuadrat antara \(A\) dan perkiraannya \(U V^T\):

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \|A - U V^T\|_F^2.\]

Anda dapat mengatasi masalah kuadrat ini melalui Dekomposisi Nilai Tunggal (SVD) dari matriks. Namun, SVD juga bukan solusi yang bagus karena dalam aplikasi sungguhan, matriks \(A\) mungkin sangat jarang. Misalnya, pikirkan semua video di YouTube dibandingkan dengan semua video yang ditonton pengguna tertentu. Solusi \(UV^T\) (yang sesuai dengan perkiraan model matriks input) akan mendekati nol, sehingga menyebabkan performa umum yang buruk.

Sebaliknya, Faktorisasi Matriks Tertimbang menguraikan tujuan menjadi dua jumlah berikut:

• Jumlah entri yang diamati.
• Jumlah entri yang tidak diamati (diperlakukan sebagai nol).

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2.\]

Di sini, \(w_0\) adalah hyperparameter yang memberi bobot pada kedua istilah sehingga tujuan tidak didominasi oleh satu atau yang lainnya. Menyesuaikan hyperparameter ini sangat penting.

Catatan: Dalam aplikasi praktis, Anda juga harus mempertimbangkan pasangan yang diamati. Misalnya, item rutin (misalnya, video YouTube yang sangat populer) atau kueri yang sering (misalnya, pengguna berat) dapat mendominasi fungsi tujuan. Anda dapat mengoreksi efek ini dengan menimbang contoh pelatihan untuk memperhitungkan frekuensi item. Dengan kata lain, Anda dapat mengganti fungsi tujuan dengan:

\[\sum_{(i, j) \in \text{obs}} w_{i, j} (A_{i, j} - \langle U_i, V_j \rangle)^2 + w_0 \sum_{i, j \not \in \text{obs}} \langle U_i, V_j \rangle^2\]

dengan \(w_{i, j}\) adalah fungsi frekuensi kueri i dan item j.

Meminimalkan Fungsi Tujuan

Algoritme umum untuk meminimalkan fungsi tujuan meliputi:

• Penurunan gradien stokastik (SGD) adalah metode generik untuk meminimalkan fungsi kerugian.

• Weighted Alternating Least Squares (WALS) dikhususkan untuk tujuan khusus ini.

Tujuannya adalah kuadrat di masing-masing dua matriks U dan V. (Namun, perlu diperhatikan bahwa masalahnya tidak konveks bersama-sama.) WALS bekerja dengan menginisialisasi embedding secara acak, lalu berganti-ganti antara:

• Memperbaiki \(U\) dan memecahkan masalah \(V\).
• Memperbaiki \(V\) dan memecahkan masalah \(U\).

Setiap tahap dapat diselesaikan dengan tepat (melalui solusi sistem linear) dan dapat didistribusikan. Teknik ini dijamin akan disatukan karena setiap langkah dijamin mengurangi kerugian.

SGD vs. WALS

SGD dan WALS memiliki kelebihan dan kekurangan. Tinjau informasi di bawah untuk melihat perbandingannya:

SGD

Sangat fleksibel—dapat menggunakan fungsi kerugian lainnya.

Dapat diparalelkan.

Lebih lambat—tidak bertemu dengan cepat.

Sulit untuk menangani entri yang tidak diamati (perlu menggunakan sampling atau gravitasi negatif).

WALS

Relatif pada Kotak Kehilangan saja.

Dapat diparalelkan.

Konvergen lebih cepat dari SGD.

Lebih mudah menangani entri yang tidak diamati.