Pemfaktoran matriks

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

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

Embeddings dipelajari sehingga produk \(U V^T\) adalah pendekatan yang baik dari matriks umpan balik A. Perhatikan bahwa \((i, j)\) entri dari \(U . V^T\) merupakan produk .titik \(\langle U_i, V_j\rangle\) penyematan pengguna \(i\) dan item \(j\), yang ingin Anda mendekati \(A_{i, j}\).

Catatan: Faktorisasi matriks biasanya memberikan representasi yang lebih ringkas daripada mempelajari matriks lengkap. Matriks lengkap memiliki \(O(nm)\) entri, sedangkan matriks embedding \(U, \ V\) memiliki \(O((n+m)d)\) entri, dengan dimensi embedding \(d\) biasanya jauh lebih kecil daripada \(m\) dan \(n\). Akibatnya, faktorisasi matriks menemukan struktur laten dalam data, dengan asumsi bahwa pengamatan terletak dekat dengan subruang dimensi rendah. Dalam contoh sebelumnya, nilai n, m, dan d sangat rendah sehingga keunggulannya dapat diabaikan. Namun, dalam sistem rekomendasi di dunia nyata, faktorisasi matriks bisa secara signifikan lebih ringkas dibandingkan pembelajaran matriks lengkap.

Memilih fungsi objektif

Salah satu fungsi objektif yang intuitif adalah jarak kuadrat. Untuk melakukannya: minimalkan jumlah kesalahan 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 {i>function<i} objektif ini, Anda hanya menjumlahkan pasangan yang diamati (i, j), yaitu, di atas nilai bukan nol dalam matriks umpan balik. Namun, hanya menjumlahkan di atas nilai satu bukanlah ide yang baik-matriks yang semuanya bernilai kerugian minimal dan menghasilkan model yang tidak dapat membuat rekomendasi yang efektif yang digeneralisasi dengan buruk.

Mungkin Anda dapat memperlakukan nilai yang tidak diamati sebagai nol, dan menjumlahkan semua entri data dalam matriks. Hal ini berkaitan dengan meminimalkan Frobenius kuadrat jarak 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 menyelesaikan soal kuadrat ini melalui Dekomposisi Nilai Singular (SVD) dari matriks. Namun, SVD juga bukan solusi yang bagus, karena dalam penerapan nyata, matriks \(A\) mungkin sangat renggang. Misalnya, pikirkan semua video di YouTube dibandingkan dengan semua video yang ditonton oleh pengguna tertentu. Solusi \(UV^T\) (yang sesuai dengan perkiraan model matriks input) akan mendekati nol, yang mengarah pada performa generalisasi.

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

• Jumlah atas entri yang diamati.
• Jumlah atas 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 kedua suku sehingga tujuannya tidak dominasi oleh satu atau yang lain. Menyesuaikan hyperparameter ini sangat penting.

Catatan: Dalam penerapan praktis, Anda juga perlu memberi bobot pada metode yang diamati berpasangan dengan hati-hati. Misalnya, item yang sering digunakan (misalnya, sangat video YouTube populer) atau kueri yang sering diajukan (misalnya, pengguna berat) mungkin mendominasi fungsi objektif. Anda dapat memperbaiki efek ini dengan contoh pelatihan pembobotan untuk memperhitungkan frekuensi item. Dengan kata lain, {i>SUMIF<i} memiliki daftar sel Anda dapat mengganti fungsi objektif 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 objektif

Algoritma umum untuk meminimalkan fungsi objektif meliputi:

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

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

Tujuannya adalah kuadrat di masing-masing dua matriks U dan V. (Catatan, namun, masalahnya bukan merupakan cembung bersama.) WALS bekerja dengan melakukan inisialisasi embedding tersebut secara acak, lalu beralih antara:

• Memperbaiki \(U\) dan menyelesaikan masalah untuk \(V\).
• Memperbaiki \(V\) dan menyelesaikan masalah untuk \(U\).

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

SGD versus WALS

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

SGD

Sangat fleksibel—dapat menggunakan kerugian fungsi-fungsi lainnya.

Dapat diparalelkan.

Lebih lambat—tidak menyatu dengan cepat.

Lebih sulit menangani entri yang tidak diamati (perlu menggunakan sampling negatif atau gravitasi).

WALS

Hanya mengandalkan Kotak Hilang.

Dapat diparalelkan.

Konvergensi lebih cepat daripada SGD.

Lebih mudah menangani entri yang tidak diamati.