Nama saya Pavel Parkhomenko, dan saya seorang pengembang ML. Dalam artikel ini, saya ingin menjelaskan desain Yandex.Zen dan berbagi peningkatan teknis yang telah meningkatkan kualitas rekomendasi. Dalam postingan ini, Anda akan mempelajari cara menemukan dokumen yang paling relevan di antara jutaan dokumen hanya dalam beberapa milidetik; cara terus menerus memfaktorkan matriks besar (terdiri dari jutaan kolom dan puluhan juta baris) sehingga dokumen baru menerima vektornya dalam beberapa puluh menit; dan cara menggunakan kembali faktorisasi matriks pengguna-artikel untuk mendapatkan representasi vektor yang baik untuk video.
Basis data rekomendasi kami berisi jutaan dokumen dengan berbagai format: artikel teks yang dibuat di platform kami dan diambil dari situs web eksternal, video, narasi, dan postingan singkat. Mengembangkan layanan seperti ini menghadirkan banyak tantangan teknis. Berikut beberapa di antaranya:
- Pisahkan tugas komputasi: lakukan semua operasi berat secara offline, dan hanya lakukan penerapan model yang cepat secara real-time, sehingga waktu respons berada dalam kisaran 100-200 ms.
- Mengintegrasikan tindakan pengguna dengan cepat. Hal ini mengharuskan semua peristiwa segera dikirimkan ke sistem pemberi rekomendasi dan memengaruhi kinerja model.
- Rancang tampilan feed agar cepat beradaptasi dengan perilaku pengguna baru. Pengguna baru harus merasa bahwa umpan balik mereka memengaruhi rekomendasi.
- Cepat pahami kepada siapa artikel baru harus direkomendasikan.
- Tanggapilah dengan cepat kemunculan konten baru yang terus-menerus. Puluhan ribu artikel diterbitkan setiap hari, dan banyak di antaranya (seperti berita, misalnya) memiliki masa hidup terbatas. Hal ini membedakannya dari film, musik, dan konten lain yang berumur panjang dan diproduksi dengan biaya mahal.
- Mentransfer pengetahuan dari satu domain ke domain lain. Jika sistem pemberi rekomendasi telah melatih model untuk artikel teks dan kita menambahkan video, kita dapat menggunakan kembali model yang ada untuk meningkatkan peringkat jenis konten baru.
Saya akan ceritakan bagaimana kami menyelesaikan masalah-masalah ini.
Seleksi kandidat
Bagaimana kita dapat mengurangi jumlah dokumen yang dipertimbangkan hingga ribuan kali lipat dalam beberapa milidetik, tanpa berdampak signifikan pada kualitas peringkat?
Misalkan kita telah melatih beberapa model ML, menghasilkan fitur berdasarkan model-model tersebut, dan melatih model lain yang memberi peringkat dokumen untuk pengguna. Ini semua akan berjalan dengan baik, tetapi kita tidak dapat begitu saja menghitung semua fitur untuk semua dokumen secara real-time jika jumlahnya jutaan, dan rekomendasi perlu dihasilkan dalam waktu 100-200 ms. Tujuannya adalah untuk memilih subset dari jutaan dokumen yang akan diberi peringkat untuk pengguna. Tahap ini biasanya disebut pemilihan kandidat. Tahap ini memiliki beberapa persyaratan. Pertama, pemilihan harus sangat cepat, menyisakan waktu sebanyak mungkin untuk proses pemberian peringkat. Kedua, dengan mengurangi jumlah dokumen yang akan diberi peringkat secara signifikan, kita harus mempertahankan sebanyak mungkin dokumen yang relevan.
Proses seleksi kandidat kami telah berkembang seiring waktu, dan sekarang kami telah mencapai pendekatan multi-tahap:
Pertama, semua dokumen dibagi menjadi beberapa kelompok, dan dokumen yang paling populer dipilih dari setiap kelompok. Kelompok dapat berupa situs, topik, atau klaster. Untuk setiap pengguna, kelompok yang paling relevan dipilih berdasarkan riwayat mereka, dan dokumen terbaik dipilih dari kelompok-kelompok ini. Kami juga menggunakan indeks kNN untuk memilih dokumen yang paling relevan bagi pengguna secara real-time. Ada beberapa metode untuk membangun indeks kNN, tetapi metode kami bekerja paling baik. (Hierarchical Navigable Small World Graphs). Ini adalah model hierarkis yang memungkinkan kita untuk menemukan N vektor terdekat untuk seorang pengguna dari basis data jutaan data dalam beberapa milidetik. Pertama, kita mengindeks seluruh basis data dokumen kita secara offline. Karena pencarian indeks cukup cepat, jika ada beberapa embedding yang kuat, kita dapat membuat beberapa indeks (satu indeks untuk setiap embedding) dan mengakses masing-masing indeks tersebut secara real-time.
Kita masih memiliki puluhan ribu dokumen untuk setiap pengguna. Jumlah ini masih terlalu besar untuk menghitung semua fitur, jadi pada tahap ini kita menggunakan pemeringkatan ringan—model ringan dari pemeringkatan berat dengan fitur yang lebih sedikit. Tujuannya adalah untuk memprediksi dokumen mana yang akan berada di puncak model berat. Dokumen dengan nilai prediksi tertinggi akan digunakan dalam model berat, yang merupakan tahap pemeringkatan akhir. Pendekatan ini memungkinkan kita untuk mengurangi basis data dokumen yang dipertimbangkan untuk seorang pengguna dari jutaan menjadi ribuan dalam hitungan puluhan milidetik.
Langkah runtime ALS
Bagaimana cara mempertimbangkan umpan balik pengguna segera setelah diklik?
Faktor kunci dalam rekomendasi adalah waktu respons terhadap umpan balik pengguna. Hal ini sangat penting bagi pengguna baru: ketika seseorang pertama kali mulai menggunakan sistem rekomendasi, mereka akan disajikan dengan umpan dokumen yang tidak dipersonalisasi tentang berbagai topik. Begitu mereka melakukan klik pertama, perlu segera mempertimbangkan hal ini dan menyesuaikannya dengan minat mereka. Jika semua faktor dihitung secara offline, respons sistem yang cepat akan menjadi tidak mungkin karena latensi. Oleh karena itu, perlu untuk memproses tindakan pengguna secara real-time. Untuk tujuan ini, kami menggunakan langkah ALS pada saat runtime untuk membangun representasi vektor dari pengguna.
Mari kita asumsikan kita memiliki representasi vektor untuk semua dokumen. Misalnya, kita dapat membuat embedding secara offline berdasarkan teks artikel menggunakan ELMo, BERT, atau model pembelajaran mesin lainnya. Bagaimana kita dapat memperoleh representasi vektor pengguna di ruang yang sama berdasarkan interaksi mereka dalam sistem?
Prinsip umum pembentukan dan dekomposisi matriks pengguna-dokumenMisalkan kita memiliki m pengguna dan n dokumen. Untuk beberapa pengguna, sikap mereka terhadap dokumen tertentu sudah diketahui. Informasi ini kemudian dapat direpresentasikan sebagai matriks m x n: barisnya sesuai dengan pengguna dan kolomnya sesuai dengan dokumen. Karena sebagian besar dokumen belum dilihat oleh pengguna, sebagian besar sel matriks akan tetap kosong, sementara yang lain akan terisi. Untuk setiap kejadian (suka, tidak suka, klik), matriks memiliki nilai—tetapi mari kita pertimbangkan model yang disederhanakan di mana suka sesuai dengan 1 dan tidak suka sesuai dengan 1.
Mari kita uraikan matriks menjadi dua: P (m x d) dan Q (d x n), di mana d adalah dimensi representasi vektor (biasanya angka kecil). Kemudian, setiap objek akan sesuai dengan vektor berdimensi d (pengguna adalah baris dalam matriks P, dan dokumen adalah kolom dalam matriks Q). Vektor-vektor ini akan menjadi embedding dari objek yang bersangkutan. Untuk memprediksi apakah pengguna akan menyukai suatu dokumen, Anda cukup mengalikan embedding-nya.
Salah satu metode faktorisasi matriks yang mungkin adalah ALS (Alternating Least Squares). Kita akan mengoptimalkan fungsi kerugian berikut:
Di sini rui adalah interaksi pengguna u dengan dokumen i, qi adalah vektor dokumen i, pu adalah vektor pengguna u.
Kemudian, vektor pengguna optimal dalam hal kesalahan kuadrat rata-rata (dengan vektor dokumen tetap) ditemukan secara analitis dengan menyelesaikan regresi linier yang sesuai.
Ini disebut "langkah ALS." Algoritma ALS sendiri terdiri dari secara bergantian memperbaiki salah satu matriks (pengguna dan artikel) dan memperbarui matriks lainnya, untuk menemukan solusi optimal.
Untungnya, menemukan representasi vektor pengguna adalah operasi yang cukup cepat yang dapat dilakukan saat runtime menggunakan instruksi vektor. Trik ini memungkinkan umpan balik pengguna untuk segera diperhitungkan dalam pemeringkatan. Embedding yang sama dapat digunakan dalam indeks kNN untuk meningkatkan pemilihan kandidat.
Penyaringan kolaboratif terdistribusi
Bagaimana cara melakukan faktorisasi matriks terdistribusi inkremental dan dengan cepat menemukan representasi vektor dari artikel baru?
Konten bukanlah satu-satunya sumber sinyal rekomendasi. Sumber penting lainnya adalah data kolaboratif. Fitur peringkat yang baik secara tradisional dapat diperoleh dari dekomposisi matriks pengguna-dokumen. Namun, ketika mencoba menerapkan dekomposisi tersebut, kami menemukan beberapa masalah:
1. Kami memiliki jutaan dokumen dan puluhan juta pengguna. Seluruh matriks tidak muat dalam satu mesin, dan dekomposisi akan memakan waktu yang sangat lama.
2. Sebagian besar konten dalam sistem memiliki masa berlaku yang singkat: dokumen hanya relevan selama beberapa jam. Oleh karena itu, perlu untuk membangun representasi vektornya secepat mungkin.
3. Jika Anda membuat dekomposisi segera setelah dokumen dipublikasikan, dekomposisi tersebut tidak akan sempat dievaluasi oleh sejumlah pengguna yang memadai. Oleh karena itu, representasi vektornya kemungkinan besar akan buruk.
4. Jika pengguna menyukai atau tidak menyukai sebuah postingan, kami tidak dapat langsung memasukkan hal ini ke dalam rinciannya.
Untuk mengatasi masalah ini, kami menerapkan dekomposisi terdistribusi dari matriks pengguna-dokumen dengan pembaruan inkremental yang sering. Bagaimana cara kerjanya?
Misalkan kita memiliki klaster yang terdiri dari N mesin (N berjumlah ratusan) dan kita ingin melakukan dekomposisi matriks secara terdistribusi di antara mesin-mesin tersebut, karena matriks tersebut tidak muat di satu mesin saja. Pertanyaannya adalah: bagaimana kita dapat melakukan dekomposisi ini sehingga, di satu sisi, setiap mesin memiliki cukup data dan, di sisi lain, komputasinya bersifat independen?
Kita akan menggunakan algoritma dekomposisi ALS yang dijelaskan di atas. Mari kita pertimbangkan bagaimana melakukan satu langkah ALS secara terdistribusi—langkah-langkah selanjutnya akan serupa. Misalkan kita memiliki matriks dokumen tetap dan ingin membuat matriks pengguna. Untuk melakukan ini, kita akan membaginya menjadi N bagian berdasarkan baris, setiap bagian berisi jumlah baris yang kira-kira sama. Kita akan mendistribusikan sel-sel yang tidak kosong dari baris yang sesuai ke setiap mesin, serta seluruh matriks penyematan dokumen. Karena data ini tidak terlalu besar, dan matriks pengguna-dokumen biasanya sangat jarang, data ini akan muat di mesin tipikal.
Trik ini dapat diulang selama beberapa epoch hingga model konvergen, dengan mengubah matriks tetap secara bergantian. Namun, bahkan setelah itu, dekomposisi matriks dapat memakan waktu beberapa jam. Dan ini tidak menyelesaikan masalah mendapatkan embedding dengan cepat untuk dokumen baru dan memperbarui embedding dokumen yang informasinya masih minim saat membangun model.
Kami terbantu dengan menerapkan pembaruan model inkremental yang cepat. Mari kita asumsikan kita memiliki model yang telah dilatih. Sejak pelatihannya, artikel-artikel baru telah ditambahkan yang telah diinteraksi oleh pengguna kami, serta artikel-artikel yang memiliki sedikit interaksi selama pelatihan. Untuk mendapatkan embedding untuk artikel-artikel ini dengan cepat, kami menggunakan embedding pengguna yang diperoleh selama pelatihan skala besar pertama model dan melakukan satu langkah ALS untuk menghitung matriks dokumen dengan matriks pengguna tetap. Hal ini memungkinkan kami untuk mendapatkan embedding dengan cukup cepat—dalam hitungan menit setelah publikasi dokumen—dan sering memperbarui embedding dokumen baru.
Untuk memastikan bahwa rekomendasi langsung didasarkan pada tindakan manusia, kami tidak menggunakan embedding pengguna yang diperoleh secara offline saat runtime. Sebagai gantinya, kami melakukan langkah ALS dan memperoleh vektor pengguna saat ini.
Pindah ke area domain lain
Bagaimana cara menggunakan umpan balik pengguna pada artikel teks untuk membangun representasi vektor dari video?
Awalnya, kami hanya merekomendasikan artikel teks, sehingga banyak algoritma kami dirancang untuk jenis konten ini. Namun, ketika menambahkan jenis konten lain, kami menemukan kebutuhan untuk menyesuaikan model kami. Bagaimana kami memecahkan masalah ini dengan menggunakan video sebagai contoh? Salah satu opsinya adalah melatih ulang semua model dari awal. Tetapi ini memakan waktu, dan beberapa algoritma membutuhkan ukuran sampel pelatihan yang besar, yang belum tersedia dalam jumlah yang cukup untuk jenis konten baru pada tahap awal masa pakainya di layanan ini.
Kami mengambil pendekatan berbeda dan menggunakan kembali model teks untuk video. Trik ALS yang sama membantu kami membuat representasi vektor video. Kami mengambil representasi vektor pengguna berdasarkan artikel teks dan melakukan langkah ALS menggunakan data tampilan video. Dengan cara ini, kami dengan mudah memperoleh representasi vektor video. Pada saat runtime, kami cukup menghitung kesamaan antara vektor pengguna yang diperoleh dari artikel teks dan vektor video.
Kesimpulan
Mengembangkan inti dari sistem rekomendasi waktu nyata melibatkan banyak tantangan. Hal ini membutuhkan pemrosesan data yang cepat dan penerapan metode pembelajaran mesin untuk memanfaatkannya secara efektif; membangun sistem terdistribusi yang kompleks yang mampu memproses sinyal pengguna dan unit konten baru dalam waktu minimal; dan banyak tugas lainnya.
Dalam sistem saat ini, yang desainnya telah saya jelaskan, kualitas rekomendasi untuk pengguna meningkat seiring dengan aktivitas dan durasi penggunaan mereka. Namun tentu saja, di sinilah tantangan utamanya: sulit bagi sistem untuk segera memahami minat seseorang yang belum banyak berinteraksi dengan konten. Meningkatkan rekomendasi untuk pengguna baru adalah tujuan utama kami. Kami akan terus mengoptimalkan algoritma untuk memastikan bahwa konten yang relevan mencapai beranda pengguna lebih cepat dan konten yang tidak relevan tidak ditampilkan.
Sumber: www.habr.com
