Bagaimana kami memprediksi masa depan dalam pencarian Yandex: dari perbaikan bug ke kueri penemuan

Orang tidak selalu secara akurat merumuskan pertanyaan mereka, jadi mesin pencari harus membantu mereka dalam hal ini. Nama saya Sergey Yudin, saya memimpin sekelompok analitik fungsi pencarian di Yandex. Setiap hari kami meningkatkan sesuatu melalui pembelajaran mesin. Tahun lalu, kami telah mengembangkan teknologi yang meramalkan kepentingan manusia.

Dengan seorang ahli dari tim saya Anastasia GaidashenkoavgaydashenkoSaya akan memberi tahu pembaca Habr bagaimana teknologi ini bekerja, saya akan menjelaskan arsitektur dan algoritma yang diterapkan. Anda juga akan belajar bagaimana prediksi permintaan berikutnya berbeda dari prediksi kepentingan manusia di masa depan.

Apa yang diinginkan pengguna?

Mari kita lihat bagaimana teknologi Yandex membantu dalam memecahkan masalah, menggunakan contoh pengguna imajiner. Misalkan dia mencetak "save ticket" di kotak pencarian. Apa yang ingin dia temukan? Untuk mengetahui tentang akumulasi tiket, atau apakah dia salah?



Ya, dia disegel. Dia ingin tidak menabung, tetapi untuk membeli tiket. Yandex mengerti dia, wali membantunya dalam hal ini - sebuah sistem yang mengoreksi permintaan yang dimasukkan secara tidak benar . Secara matematis, sistem ini memaksimalkan kemungkinan kueri yang dimasukkan dengan benar, asalkan pengguna memasukkan teks. Masalah ini telah diselesaikan di Yandex selama lebih dari sepuluh tahun. Dan tidak hanya dalam pencarian.

Jadi, pengguna imajiner kami memasukkan permintaan "beli tiket". Pada titik ini, sjest ikut bermain .(atau saran pencarian). Sajest membantu pengguna untuk merumuskan permintaan, untuk menyelesaikannya dengan benar.



Sajest kami telah datang jauh. Beberapa tahun yang lalu, kami memperumit tugas. Saya ingin menunjukkan tidak hanya penyelesaian paling logis dari permintaan, tetapi juga untuk memprediksi permintaan mana yang akan dimasukkan pengguna ini pada akhirnya dan memulai prerendernya sebelum klik. Jika Anda tertarik dengan cara kerjanya, maka Anda dapat melihat Habré .

Pengguna imajiner kami memilih akhir permintaan dari serangkaian tips: ternyata ia sedang mencari tiket ke Galeri Tretyakov. Dengan demikian, sistem rekomendasi menyelesaikan tugas pertamanya - ini membantu pengguna untuk merumuskan permintaan .

Tugas ini telah selesai, tetapi pengguna masih memiliki pertanyaan. Apa yang akan dia cari selanjutnya? Mungkin dia ingin tahu bagaimana menuju ke galeri? Ya, ia mencetak Lavrushinsky per 10 untuk memverifikasi alamat.



Bisakah kita memprediksi permintaan ini? Iya. Dan kami telah melakukan ini selama beberapa waktu. Ada blok seperti itu - "Juga bertanya" di akhir masalah. Ini menunjukkan kueri yang biasanya ditanyakan orang setelah masuk dalam bidang pencarian. Di dalamnya kita akan melihat permintaan kami dengan alamat Galeri Tretyakov.



Kami memaksimalkan probabilitas suatu permintaan tunduk pada permintaan pengguna sebelumnya. Sistem menyelesaikan tugas kedua - memperkirakan permintaan berikutnya .

Dan kemudian sesuatu yang sangat menarik terjadi. Pengguna mencetak permintaan "kapan saya bisa mengunjungi Galeri Tretyakov secara gratis." Permintaan ini berbeda dari yang lain, berlawanan dengan tugas pengguna, menyelesaikan beberapa tugas ortogonal.



Tapi mari kita pikirkan: jika kita mencari tiket ke galeri, apa yang ingin kita lihat sebagai rekomendasi? Sejumlah besar orang ingin tahu bahwa tiket mungkin tidak perlu dibeli. Ini adalah bagian ketiga, paling sulit dan menarik dari tugas - untuk merekomendasikan sesuatu yang baru dan bermanfaat bagi pengguna. Sesuatu yang dia sendiri belum pikirkan.

Kami menyebutnya penemuan permintaan tersebut. Kami belajar mengidentifikasi mereka di log pencarian kami, menyimpan dan merekomendasikan mereka di akhir masalah. Dan inilah tugas baru dan revolusioner yang sedang kami kerjakan secara aktif sekarang. Untuk orang yang membeli tongkat Skandinavia, Yandex dapat merekomendasikan permintaan tentang cara mengambilnya dengan tinggi. Jika seseorang sering bepergian, maka mungkin dia akan tertarik dengan permintaan pencarian "ke mana harus pergi tanpa visa." Dll



Formulasi matematis dari masalah dalam kasus ini akan terlihat seperti ini: kami tidak memaksimalkan probabilitas permintaan berikutnya, tetapi probabilitas klik pada permintaan, yang kami rekomendasikan kepada pengguna berdasarkan sesi sebelumnya.

Bagaimana itu bekerja?

Mari kita lihat bagaimana sistem rekomendasi kami diimplementasikan, arsitektur apa yang tersembunyi di baliknya. Tetapi untuk memulainya, kita akan menentukan apa yang umumnya ingin kita dapatkan dari sistem rekomendasi.

1. Rekomendasi yang berguna! Tentu saja, kami menginginkan permintaan yang kami rekomendasikan kepada pengguna agar sesuai dengan minatnya. Mereka harus bermanfaat dan relevan.

2. Skalabilitas. Kami berharap bahwa sistemnya akan baik: akan ada semakin banyak pengguna, dan jumlah permintaan akan meningkat. Dan kami ingin meningkatkan cakupan bagi mereka yang dapat kami jadikan rekomendasi.

3. Kemudahan implementasi.Kami berasumsi bahwa sistem kami akan tetap berfungsi, dan kami tidak ingin menulis ulang berkali-kali. Sistem ini harus mudah diimplementasikan, sehingga kita dapat memperbaikinya nanti, tidak meluncurkan versi baru, tetapi meningkatkan yang saat ini.

Setelah memutuskan keinginan kita, mari kita lihat bagaimana Anda dapat menghidupkannya.

Kami memiliki beberapa basis data penemuan - basis data kueri yang mungkin tampak menarik dan bermanfaat bagi pengguna kami. Tetapi jika kita mulai membuat peringkat seluruh pangkalan ini, kita tidak akan memiliki kekuatan komputasi yang cukup. Pengguna memiliki banyak permintaan, mereka beragam, jadi pertama-tama kita perlu memfilter basis data ini.



Penyaringan dapat dilakukan dengan metode yang berbeda. Di Yandex, kami menggunakan kNN (k-tetangga terdekat) untuk ini- Algoritma klasifikasi dasar dalam pembelajaran mesin, yang dikenal sebagai "pencarian tetangga terdekat". Dengan menggunakan algoritma ini, kami ingin memfilter basis data: pilih kueri yang paling dekat dengan yang mungkin menarik bagi pengguna. Untuk melakukan ini, kami ingin membandingkan permintaan pengguna dan permintaan yang siap kami rekomendasikan dalam ruang vektor.

Tetapi untuk membawa permintaan ini ke dalam satu ruang vektor, kita juga perlu membuat sesuatu. Misalnya, Anda dapat menggunakan DSSM (Deep Structured Semantic Model) - semacam kotak hitam yang dapat menerjemahkan entitas yang berbeda menjadi satu ruang vektor. Awalnya, pendekatan ini diusulkan dalam sebuah artikel dari Microsoft. Tapi Yandex telah mengadaptasinya dengan sangat kuat untuk tugas-tugasnya dan telah jauh dari ide aslinya. Jika Anda tertarik untuk membaca lebih lanjut tentang ini, maka informasinya dapat ditemukan, misalnya, dalam artikel tentang algoritma pencarian Palekh .



Langkah selanjutnya adalah peringkat. Ketika kami memiliki daftar permintaan yang dekat dengan apa yang mungkin diminati pengguna, kami ingin memahami apa yang akan lebih menarik baginya dan apa yang kurang.

Misalnya, kami memilih 100 kueri. Sepertinya tidak mungkin pengguna akan menggulir semua 100. Anda harus memilih 5 besar dan merekomendasikannya. Untuk melakukan ini, kami memberikan peringkat pada permintaan kami. Kami mendapatkan taksiran ini berdasarkan probabilitas klik pada permintaan yang kami rekomendasikan kepada pengguna berdasarkan sesi sebelumnya.

Bagaimana kita mendapatkan kemungkinan klik berikutnya? Sistem kami sudah berjalan dan berjalan, jadi kami hanya mengumpulkan umpan balik dari pengguna - dan dengan demikian secara bertahap meningkatkan sistem rekomendasi kami.



Sekarang kita telah meninjau semua langkah secara terpisah, mari kita kembali ke awal dan menyatukan semuanya. Total: pengguna datang kepada kami dengan beberapa permintaan, dan kami memiliki semacam basis rekomendasi. Kami mengambil basis data ini dan memfilternya, menerima permintaan yang ingin kami susun dan rekomendasikan kepada pengguna.



Sekarang ingat bahwa kita umumnya merumuskan keinginan untuk sistem rekomendasi kami. Dan mari kita lihat bagaimana kita bisa mengimplementasikannya dalam arsitektur yang dihasilkan.

Sebagai contoh, kami ingin skalabilitas dalam hal meningkatkan basis. Metode implementasi kami memiliki semua properti yang diperlukan untuk penskalaan tersebut. Kita seharusnya tidak menyimpan seluruh basis dalam memori: begitu basis melebar begitu banyak sehingga tidak muat pada satu cluster, kita dapat membaginya menjadi dua. Dan jika sebelumnya kita melewati satu cluster dengan kNN dan memilih 100 teratas, yang akan kita peringkat, sekarang kita bisa melalui dua cluster secara terpisah dan memilih, misalnya, 50 teratas di masing-masing. Atau, secara umum, memecah cluster berdasarkan topik dan berjalan dengan kNN hanya pada topik yang diinginkan.

Untuk skala jumlah pengguna, Anda dapat menambahkan daya komputasi tambahan dan memproses masing-masing secara terpisah, karena dalam arsitektur kami tidak ada tempat di mana kami harus menyimpan semua pengguna dalam memori pada saat yang sama.

Dalam beberapa pendekatan lain, ada tempat yang memfilter, misalnya, ketika mendekomposisi sebuah matriks. Dekomposisi matriks adalah pendekatan lain yang digunakan dalam rekomendasi. Bahkan, Yandex juga menggunakannya, tetapi tidak untuk menyaring, tetapi sebagai fitur tambahan untuk pelatihan, karena masih banyak informasi yang berguna untuk dianalisis.

Fitur tambahan, algoritme baru, dan metode lain dapat diterapkan ke seluruh arsitektur. Ketika sistem menyala dan berjalan, kita dapat mulai memperbaikinya.

Di mana itu bekerja?

Arsitektur seperti itu telah diterapkan di Yandex, dan dibandingkan dengan reformulasi yang biasa, ketika kami mencoba memberi saran kepada pengguna untuk mengetahui alamat Galeri Tretyakov, kami sudah dapat memberi saran bagaimana cara menuju ke Galeri Tretyakov tanpa menunggu dalam antrean atau bahkan tanpa biaya.



Ini adalah tingkat interaksi baru antara mesin pencari dan pengguna. Kami tidak hanya memperbaiki kesalahan dan melengkapi permintaan, tetapi belajar untuk memprediksi minat seseorang dan menawarkan sesuatu yang baru kepadanya. Mungkin ini akan menjadi pencarian untuk masa depan. Bagaimana menurut anda?