Anatomi sistem rekomendasi. Bagian dua

Seminggu yang lalu, saya melakukan ikhtisar algoritma rekomendasi yang ada di sini . Pada artikel ini, saya akan melanjutkan tinjauan ini: Saya akan berbicara tentang varian berbasis item dari filter kolaboratif, tentang metode berdasarkan dekomposisi matriks, masalah pengujian, dan juga tentang lebih sedikit algoritma "tidak terpilin" (tapi tidak kalah menarik).

Pemfilteran kolaboratif (opsi berbasis item)

Pendekatan berbasis Item adalah alternatif alami untuk pendekatan berbasis Pengguna klasik yang dijelaskan pada bagian pertama, dan mengulanginya hampir sepenuhnya, kecuali untuk satu titik - itu berlaku untuk matriks preferensi yang ditransposisikan. Yaitu mencari produk terkait, bukan pengguna.

Biarkan saya mengingatkan Anda bahwa pemfilteran kolaboratif berbasis pengguna (CF berbasis pengguna) mencari setiap klien sekelompok pelanggan yang paling mirip dengan itu (dalam hal pembelian sebelumnya) dan rata-rata preferensi mereka. Preferensi rata-rata ini berfungsi sebagai rekomendasi bagi pengguna. Dalam kasus penyaringan kolaboratif komoditas (CF berbasis item), tetangga terdekat dicari pada set produk - kolom dari matriks preferensi. Dan rata-rata terjadi tepat pada mereka.

Memang, jika produk secara substansial mirip, maka kemungkinan besar mereka suka atau tidak disukai pada saat yang sama. Oleh karena itu, ketika kita melihat bahwa dua produk memiliki korelasi kuat, ini dapat menunjukkan bahwa mereka adalah produk yang serupa.

Keuntungan berbasis Barang dibandingkan berbasis Pengguna:

• Ketika ada banyak pengguna (hampir selalu), tugas untuk menemukan tetangga terdekat menjadi tidak dapat dihitung. Misalnya, untuk 1 juta pengguna Anda perlu menghitung dan menyimpan $$$\ frac {1} {2} 10 ^ 6 * 10 ^ 6$~ 500 miliar jarak. Jika jarak dikodekan dengan 8 byte, ini menghasilkan 4TB untuk matriks jarak saja. Jika kita melakukan Item-based, maka kompleksitas perhitungannya berkurang $$$O (N ^ 2n)$sebelumnya $$$O (n ^ 2N)$dan matriks jarak memiliki dimensi tidak lagi (1 juta per 1 juta), tetapi, misalnya, (100 per 100) dengan jumlah barang.
  
• Peringkat kedekatan jauh lebih akurat daripada peringkat kedekatan. Ini adalah konsekuensi langsung dari kenyataan bahwa biasanya ada lebih banyak pengguna daripada barang, dan karena itu kesalahan standar dalam menghitung korelasi barang jauh lebih sedikit. Kami hanya memiliki lebih banyak informasi untuk menarik kesimpulan.
  
• Dalam versi berbasis pengguna, deskripsi pengguna biasanya sangat jarang (ada banyak produk, beberapa peringkat). Di satu sisi, ini membantu mengoptimalkan perhitungan - kami hanya mengalikan elemen-elemen tersebut di mana ada persimpangan. Tetapi di sisi lain - berapa banyak tetangga yang tidak Anda ambil, daftar barang yang akhirnya dapat Anda rekomendasikan sangat kecil.
  
• Preferensi pengguna dapat berubah seiring waktu, tetapi deskripsi item jauh lebih stabil.
  

Algoritma lainnya hampir sepenuhnya mengulangi opsi berbasis Pengguna: jarak kosinus yang sama dengan ukuran utama kedekatan, kebutuhan yang sama untuk normalisasi data. Jumlah barang tetangga N biasanya dipilih di wilayah 20.

Karena fakta bahwa korelasi produk dipertimbangkan pada jumlah pengamatan yang lebih besar, tidak begitu penting untuk menghitung ulang setelah setiap penilaian baru, dan Anda dapat melakukan ini secara berkala dalam mode pertempuran.

Beberapa kemungkinan peningkatan algoritma:

• Modifikasi yang menarik adalah untuk mempertimbangkan "kesamaan" produk bukan sebagai jarak cosinus khas, tetapi dengan membandingkan konten mereka (kesamaan berbasis konten). Jika pada saat yang sama preferensi pengguna tidak diperhitungkan dengan cara apa pun, pemfilteran seperti itu berhenti menjadi "kolaboratif". Selain itu, bagian kedua dari algoritma - mendapatkan estimasi rata-rata - tidak berubah sama sekali.
• Modifikasi lain yang mungkin adalah untuk menimbang pengguna saat menghitung kesamaan item. Misalnya, semakin banyak pengguna membuat peringkat, semakin berat yang mereka miliki saat membandingkan dua produk.
• Alih-alih hanya rata-rata perkiraan produk tetangga, bobot dapat dipilih dengan melakukan regresi linier.

Saat menggunakan pendekatan berbasis item, rekomendasi cenderung lebih konservatif. Memang, sebaran rekomendasi kurang dan karenanya cenderung menunjukkan produk yang tidak standar.

Jika dalam matriks preferensi kami menggunakan tampilan deskripsi produk sebagai peringkat, maka produk yang direkomendasikan kemungkinan besar adalah analog - produk yang sering dilihat bersama. Jika kita menghitung peringkat dalam matriks preferensi berdasarkan pembelian, maka kemungkinan besar produk yang direkomendasikan adalah aksesori - barang yang sering dibeli bersama.

Penilaian Kualitas Sistem

Menguji sistem rekomendasi adalah proses yang sulit dan selalu menimbulkan banyak pertanyaan, terutama karena ambiguitas konsep "kualitas".

Secara umum, dalam tugas pembelajaran mesin, ada dua pendekatan utama untuk pengujian:

• pengujian offline model pada data historis menggunakan tes retro,
• menguji model yang sudah selesai menggunakan pengujian A / B (kami meluncurkan beberapa opsi, lihat mana yang memberikan hasil terbaik).

Kedua pendekatan ini secara aktif digunakan dalam pengembangan sistem rekomendasi. Mari kita mulai dengan pengujian offline.

Batasan utama yang harus Anda hadapi adalah untuk mengevaluasi keakuratan ramalan yang kami dapat hanya pada produk-produk yang telah dinilai pengguna.

Pendekatan standar adalah validasi silang dengan metode leave-one-out dan leave-p-out. Pengulangan tes berulang dengan rata-rata hasil memungkinkan untuk memperoleh penilaian kualitas yang lebih stabil.

• leave-one-out - model dilatih pada semua objek yang dievaluasi oleh pengguna, kecuali satu, dan diuji pada objek yang satu ini. Ini dilakukan untuk semua n objek, dan rata-rata dihitung di antara estimasi kualitas yang diperoleh.
• leave-p-out adalah sama, tetapi poin p dikecualikan pada setiap langkah.

Semua metrik kualitas dapat dibagi menjadi tiga kategori:

• Akurasi Prediksi - mengevaluasi keakuratan peringkat yang diprediksi,
• Dukungan keputusan - mengevaluasi relevansi rekomendasi,
• Metrik Akurasi Peringkat - mengevaluasi kualitas peringkat rekomendasi yang dikeluarkan.
  

Sayangnya, tidak ada satu pun metrik yang disarankan untuk semua kesempatan, dan semua orang yang terlibat dalam pengujian sistem merekomendasikan memilihnya untuk tujuan mereka sendiri.

Ketika peringkat dinilai pada skala berkelanjutan (0-10), metrik kelas Prediksi Akurasi biasanya cukup.
Metrik kelas Pendukung Keputusan berfungsi dengan data biner (0 dan 1, ya dan tidak). Jika dalam tugas kami peringkat pada awalnya ditunda pada skala berkelanjutan, mereka dapat dikonversi ke format biner dengan menerapkan aturan yang menentukan - katakanlah, jika peringkatnya kurang dari 3,5, kami menganggap peringkat itu "buruk", dan jika lebih tinggi, maka "bagus".
Sebagai aturan, rekomendasi ditampilkan dalam daftar beberapa posisi (pertama atas, kemudian dalam urutan prioritas menurun). Metrik kelas Akurasi Peringkat mengukur seberapa benar urutan di mana rekomendasi ditampilkan dalam daftar yang diurutkan.
Jika kami menggunakan sistem rekomendasi dalam bisnis online, maka, sebagai aturannya, mereka memiliki dua tujuan (terkadang saling bertentangan):

1. memberi tahu pengguna tentang produk yang menarik,
2. Dorong dia untuk melakukan pembelian (melalui surat, menyusun penawaran pribadi, dll.).

Seperti dalam model apa pun yang bertujuan memotivasi pengguna untuk bertindak, hanya peningkatan target tindakan yang harus dievaluasi. Misalnya, ketika menghitung pembelian berdasarkan rekomendasi, kita perlu mengecualikan pembelian yang dilakukan sendiri oleh pengguna tanpa model kita. Jika ini tidak dilakukan, efek dari memperkenalkan model akan sangat ditaksir.

Angkat adalah indikator berapa kali akurasi suatu model melebihi algoritma dasar tertentu. Dalam kasus kami, algoritme dasar mungkin hanya berupa kurangnya rekomendasi. Metrik ini menangkap pangsa pembelian inkremental dengan baik dan ini memungkinkan Anda untuk membandingkan model yang berbeda secara efektif.

Pengujian pengguna

Sumber

Perilaku pengguna adalah hal yang tidak diformalkan dengan baik dan tidak satu metrik tunggal akan sepenuhnya menggambarkan proses pemikiran di kepalanya ketika memilih suatu produk. Keputusan dipengaruhi oleh banyak faktor. Mengklik tautan dengan produk yang disarankan belum memiliki peringkat tinggi atau bahkan minat. Pengujian daring membantu sebagian memahami logika klien. Berikut ini adalah beberapa skenario untuk pengujian tersebut.

Skenario pertama dan paling jelas adalah analisis peristiwa situs. Kami melihat apa yang dilakukan pengguna di situs, apakah dia memperhatikan rekomendasi kami, apakah mengikuti mereka, fitur sistem mana yang diminati, yang tidak, produk mana yang lebih baik direkomendasikan, mana yang lebih buruk. Untuk memahami algoritma mana yang secara keseluruhan bekerja lebih baik atau hanya mencoba ide baru yang menjanjikan, kami melakukan pengujian A / B dan mengumpulkan hasilnya.

Skenario kedua adalah menerima umpan balik dari pengguna dalam bentuk jajak pendapat dan jajak pendapat. Sebagai aturan, ini adalah pertanyaan umum untuk memahami bagaimana pelanggan menggunakan layanan - yang lebih penting: relevansi atau keragaman, apakah mungkin untuk menampilkan produk duplikat, atau terlalu mengganggu. Keuntungan dari skrip ini adalah memberikan jawaban langsung untuk semua pertanyaan ini.

Pengujian semacam itu adalah hal yang rumit, tetapi untuk layanan rekomendasi besar itu hanya perlu. Pertanyaan dapat menjadi lebih rumit, misalnya, "daftar mana yang lebih relevan bagi Anda", "seberapa banyak lembar terlihat lengkap", "Anda akan menonton film ini / membaca buku".

Peringkat Tersirat dan Data Unary

Pada awal pengembangannya, sistem rekomendasi digunakan dalam layanan di mana pengguna secara jelas mengevaluasi produk dengan memberi peringkat padanya - ini adalah Amazon, Netflix, dan situs perdagangan online lainnya. Namun, dengan popularitas sistem rekomendasi, ada kebutuhan untuk menggunakannya juga di mana tidak ada peringkat - ini bisa berupa bank, bengkel mobil, kios dengan shawarma dan layanan lain di mana karena alasan tertentu tidak mungkin untuk membangun sistem evaluasi. Dalam kasus ini, minat pengguna dapat dihitung hanya dengan tanda tidak langsung - tindakan tertentu dengan produk menunjukkan preferensi pengguna, misalnya, melihat deskripsi di situs, menambahkan produk ke keranjang, dll. Ini menggunakan prinsip "dibeli - itu berarti cinta!". Sistem peringkat implisit seperti ini disebut Peringkat Implisit.

Peringkat implisit jelas bekerja lebih buruk daripada yang eksplisit, karena mereka menambahkan urutan besarnya lebih banyak noise. Lagi pula, pengguna dapat membeli produk sebagai hadiah untuk istrinya atau pergi ke halaman dengan deskripsi produk, hanya untuk meninggalkan komentar di sana dengan gaya "apa jenis nastiness itu semua sama" atau untuk memuaskan rasa ingin tahunya yang alami.

Jika dalam hal peringkat eksplisit, kami memiliki hak untuk berharap bahwa setidaknya satu peringkat negatif adalah tidak, tidak, dan ya, maka kami tidak akan mengambil peringkat negatif dari mana pun. Jika pengguna tidak membeli buku "Fifty Shades of Grey," ia bisa melakukan ini karena dua alasan:

• dia benar-benar tidak tertarik padanya (ini adalah kasus negatif),
  
• dia tertarik padanya, tapi dia tidak tahu tentang dia (ini adalah kasus positif yang terlewatkan).
  

Tetapi kami tidak memiliki data untuk membedakan kasus pertama dari yang kedua. Ini buruk, karena ketika melatih suatu model, kita harus memperkuatnya pada kasus-kasus positif dan baik pada kasus-kasus negatif, sehingga kita akan hampir selalu baik-baik saja, dan akibatnya, model tersebut akan menjadi bias.

Kasus kedua adalah kemampuan untuk meninggalkan hanya peringkat positif. Contoh yang mencolok adalah tombol Suka di jejaring sosial. Peringkat di sini sudah dicantumkan secara eksplisit, tetapi seperti pada contoh sebelumnya, kami tidak memiliki contoh negatif - kami tahu saluran mana yang disukai pengguna, tetapi kami tidak tahu yang mana yang tidak mereka sukai.

Dalam kedua contoh, tugas berubah menjadi tugas Klasifikasi Kelas Unary .

Solusi yang paling jelas adalah mengikuti jalur sederhana dan menganggap tidak adanya peringkat sebagai peringkat negatif. Dalam beberapa kasus ini lebih dibenarkan, dalam beberapa kurang. Misalnya, jika kita tahu bahwa pengguna kemungkinan besar melihat produk (misalnya, kami menunjukkan kepadanya daftar produk, dan dia beralih ke produk yang mengikutinya), maka kurangnya transisi dapat benar-benar menunjukkan kurangnya minat.

Sumber

Algoritma Faktorisasi

Akan sangat bagus untuk menggambarkan minat pengguna dalam "stroke" yang lebih besar. Bukan dalam format "dia mencintai film X, Y dan Z", tetapi dalam format "dia mencintai komedi Rusia modern". Selain fakta bahwa ini akan meningkatkan generalisasi model, itu juga akan memecahkan masalah dimensi data yang besar - karena kepentingan akan dijelaskan bukan oleh vektor barang, tetapi oleh vektor preferensi yang jauh lebih kecil.

Pendekatan semacam itu juga disebut dekomposisi spektral atau penyaringan high-pass (karena kami menghilangkan noise dan meninggalkan sinyal yang bermanfaat). Ada banyak dekomposisi matriks yang berbeda dalam aljabar, dan salah satu yang paling umum digunakan adalah dekomposisi SVD (dekomposisi nilai singular).

Metode SVD digunakan pada akhir 80-an untuk memilih halaman yang memiliki makna yang serupa, tetapi tidak dalam konten, dan kemudian mulai digunakan dalam tugas-tugas rekomendasi. Metode ini didasarkan pada dekomposisi dari matriks awal dari peringkat ® menjadi produk dari 3 matriks:

$$$R = U * D * S$di mana ukuran dari matriks $$$(k, m) = (k, r) * (r, r) * (r, m)$, dan r adalah
peringkat dekomposisi - parameter yang mencirikan tingkat detail penguraian.

Menerapkan dekomposisi ini ke matriks preferensi kami, kami memperoleh dua matriks faktor (deskripsi singkat):

U - deskripsi ringkas tentang preferensi pengguna,
S adalah deskripsi ringkas tentang fitur produk.

Penting bahwa dengan pendekatan ini kita tidak tahu karakteristik mana yang sesuai dengan faktor-faktor dalam deskripsi yang direduksi, bagi kita mereka dikodekan dengan beberapa angka. Oleh karena itu, SVD adalah model yang tidak diinterpretasikan.

Untuk mendapatkan perkiraan matriks preferensi, cukup untuk melipatgandakan matriks faktor. Setelah melakukan ini, kami mendapatkan skor penilaian untuk semua pasangan klien-produk.

Keluarga umum dari algoritma tersebut disebut NMF (faktorisasi matriks non-negatif). Sebagai aturan, perhitungan ekspansi semacam itu sangat memakan waktu, oleh karena itu, dalam praktiknya, mereka sering menggunakan varian iteratif perkiraan mereka.

ALS (alternating least square) adalah algoritma iteratif yang populer untuk mendekomposisi matriks preferensi menjadi produk 2 matriks: faktor pengguna (U) dan faktor produk (I). Ini bekerja pada prinsip meminimalkan kesalahan standar peringkat. Optimalisasi terjadi secara bergantian, pertama oleh faktor pengguna, kemudian oleh faktor produk. Juga, untuk menghindari pelatihan ulang, koefisien regularisasi ditambahkan ke kesalahan standar.


Jika kami melengkapi matriks preferensi dengan dimensi baru yang berisi informasi tentang pengguna atau produk, maka kami tidak dapat memperluas matriks preferensi, tetapi tensor. Dengan demikian, kami akan menggunakan lebih banyak informasi yang tersedia dan mungkin mendapatkan model yang lebih akurat.

Pendekatan lain

Aturan Asosiasi

Aturan asosiatif biasanya digunakan dalam analisis korelasi produk (Analisis Keranjang Pasar) dan terlihat seperti ini: "jika ada susu dalam cek pelanggan, maka dalam 80% kasus akan ada roti". Yaitu, jika kita melihat bahwa pelanggan telah memasukkan susu ke dalam keranjang, sekarang saatnya untuk mengingatkan tentang roti.

Ini tidak sama dengan analisis pembelian yang berjarak waktu, tetapi jika kita menganggap seluruh sejarah sebagai satu keranjang besar, maka kita dapat sepenuhnya menerapkan prinsip ini di sini. Ini dapat dibenarkan ketika, misalnya, kami menjual barang mahal satu kali (kredit, penerbangan).

RBM (Mesin Bolzman terbatas)

Mesin Bounded Boltzmann adalah pendekatan yang relatif lama berdasarkan jaringan saraf berulang stokastik. Ini adalah model dengan variabel laten dan dalam hal ini mirip dengan dekomposisi SVD. Itu juga mencari deskripsi yang paling ringkas dari preferensi pengguna, yang dikodekan menggunakan variabel laten. Metode ini tidak dikembangkan untuk mencari rekomendasi, tetapi berhasil digunakan dalam solusi Netflix Prize teratas dan masih digunakan dalam beberapa tugas.

Autoencoder

Ini didasarkan pada prinsip dekomposisi spektral yang sama, itulah sebabnya jaringan seperti itu juga disebut denoising auto-encoders. Jaringan pertama-tama menciutkan data pengguna yang diketahuinya menjadi representasi yang ringkas, mencoba hanya meninggalkan informasi yang bermakna, dan kemudian mengembalikan data ke dimensi aslinya. Hasilnya adalah jenis rata-rata, templat bebas bising yang digunakan untuk mengevaluasi minat pada produk apa pun.

DSSM (model similiaritas semi-dalam)

Salah satu pendekatan baru. Semua prinsip yang sama, tetapi dalam peran variabel laten, berikut adalah deskripsi tensor internal dari data input (embeddings). Awalnya, model ini dibuat untuk pencocokan permintaan dengan dokumen (serta rekomendasi berbasis konten), tetapi mudah diubah menjadi tugas mencocokkan pengguna dan produk.


Berbagai arsitektur jaringan yang dalam tidak ada habisnya, itulah sebabnya Deep Learning menyediakan bidang eksperimen yang sangat luas untuk sistem rekomendasi.

Solusi hibrida

Dalam praktiknya, hanya satu pendekatan yang jarang digunakan. Sebagai aturan, beberapa algoritma digabungkan menjadi satu untuk mencapai efek maksimum.

Dua keuntungan utama dari menggabungkan model adalah peningkatan akurasi dan kemungkinan penyetelan yang lebih fleksibel untuk berbagai kelompok pelanggan. Kerugiannya adalah interpretabilitas yang kurang dan kompleksitas implementasi dan dukungan yang lebih besar.

Beberapa strategi penggabungan:

• Bobot - baca perkiraan rata-rata tertimbang untuk beberapa perkiraan,
  
• Stacking - prediksi masing-masing model adalah input dari pengelompokan (meta) lain yang belajar untuk menimbang dengan benar estimasi menengah,
  

• Switching - menerapkan algoritma yang berbeda untuk produk / pengguna yang berbeda,
  
• Pencampuran - rekomendasi tentang algoritma yang berbeda dihitung, dan kemudian digabungkan menjadi satu daftar.
  

Misalnya, rekomendasi berbasis konten digunakan, dan sebagai salah satu fitur - hasil pemfilteran kolaboratif.

Fitur Tertimbang (Linear) Susun:

$$

$$P(u,i) = w_1 P_1(u,i) + w_2 P_2(u,i) + … + w_n P_n(u,i)$$

Bobot $$$w_1,w_2 … w_n$dilatih pada sampel. Sebagai aturan, regresi logistik digunakan untuk ini.

Susun secara umum:

$$

$$P(u,i) = f_1(u,i) P_1(u,i) + f_2(u,i) P_2(u,i) + … + f_n(u,i) P_n(u,i)$$

Penjelasan Solusi Netflix

Netflix Prize adalah kompetisi yang diadakan pada 2009 yang mengharuskan pengguna untuk memprediksi peringkat pengguna perpustakaan film Netflix. Uang hadiah $ 1 juta yang baik menyebabkan kegemparan dan menarik banyak peserta, termasuk orang-orang yang cukup terkenal di AI.

Itu adalah tugas dengan peringkat eksplisit, skor ditetapkan pada skala 1 hingga 5, dan akurasi perkiraan dinilai oleh RMSE. Sebagian besar tempat pertama diambil oleh ansambel besar pengklasifikasi.

Ensemble yang menang menggunakan model kelas berikut:

• model dasar - model regresi berdasarkan estimasi rata-rata
  
• pemfilteran kolaboratif - pemfilteran kolaboratif
  
• RBM - Mesin Boltzmann Terbatas
  
• hutan acak - model prediksi
  

Peningkatan gradien tradisional digunakan sebagai meta-algoritma yang menggabungkan estimasi algoritma lokal.

Ringkasan

Tugas menghasilkan rekomendasi sangat sederhana - kami menyusun matriks preferensi dengan perkiraan pengguna yang diketahui oleh kami, jika ternyata, kami melengkapi perkiraan ini dengan informasi tentang klien dan produk, dan mencoba mengisi nilai yang tidak diketahui.

Terlepas dari kesederhanaan pernyataan itu, ratusan artikel diterbitkan yang menggambarkan metode baru yang mendasar untuk menyelesaikannya. Pertama, ini disebabkan oleh peningkatan jumlah data yang dikumpulkan yang dapat digunakan dalam model dan peningkatan peran peringkat implisit. Kedua, dengan perkembangan pembelajaran yang mendalam dan munculnya arsitektur jaringan saraf baru. Semua ini mengalikan kompleksitas model.

Namun secara umum, semua keragaman ini bermuara pada serangkaian pendekatan yang sangat kecil, yang saya coba uraikan dalam artikel ini.