Dari heuristik hingga pembelajaran mesin: saran penelusuran di Citymobil

Halo! Nama saya Mikhail Dyachkov, dan di Citymobil saya melakukan pembelajaran mesin. Hari ini saya akan memberi tahu Anda tentang algoritme baru kami untuk menghasilkan saran penelusuran untuk tujuan akhir. Anda akan mempelajari bagaimana tugas yang tampaknya sederhana berubah menjadi skenario yang menarik, dengan bantuan yang, kami harap, kami berhasil membuat kehidupan pengguna sedikit lebih mudah. Kami terus memantau secara cermat pekerjaan algoritme baru dan selanjutnya akan menyesuaikannya untuk menjaga kualitas peringkat pada tingkat yang tinggi. Untuk semua pengguna, kami akan meluncurkan algoritme dalam beberapa minggu ke depan, tetapi kami sudah siap untuk berbicara tentang perjalanan panjang yang telah kami tempuh dari heuristik hingga algoritme pembelajaran mesin dan meluncurkannya ke dalam operasi.



Menurut saya ada baiknya memulai dengan mendeskripsikan pandangan dunia yang ideal dari skenario pesanan taksi dari perspektif antarmuka pengguna. Saya ingin aplikasi kita memahami di mana / di mana / kapan / dengan mobil apa pengguna ingin pergi. Dalam artikel ini, kita akan melihat solusi kita untuk menjawab pertanyaan "di mana".



Salah satu elemen sentral di layar pertama (yang dilihat pengguna setelah masuk) adalah saran penelusuran. Di tim geo-search, kami menyebutnya "sajest" (dari saran bahasa Inggris). Mereka menawarkan pengguna alamat rute terakhir (titik "B") dari riwayat perjalanannya berdasarkan lokasi pin saat ini (yaitu titik drop) dan waktu hari tanpa memasukkan kueri penelusuran. Kami mencoba membantu pengguna untuk membuat pesanan "dalam satu klik" dengan bantuan sagests. Dalam versi aplikasi klien iOS saat ini, perintahnya terlihat seperti ini:







Pencarian geografis karena algoritme untuk menghasilkan hasil pencarian dapat memengaruhi salah satu metrik produk terpenting untuk aplikasi klien, seperti waktu yang dihabiskan untuk memesan taksi ( Time to order , atau T2O ), serta jumlah tindakan yang dilakukan klien untuk membentuk pesanan ( Tindakan untuk memesan , atau A2O). Oleh karena itu, kami memutuskan untuk mengembangkan algoritme yang akan memprediksi titik akhir rute yang paling mungkin (titik "B") untuk lokasi dan waktu tertentu.

Heuristis

Salah satu pengembang backend dari tim geo-search (vasilesk.dll, halo!) muncul dengan heuristik yang cukup sederhana untuk menghasilkan sajests yang bekerja untuk titik awal "A" dan titik akhir "B". Perlu segera dicatat bahwa heuristik tidak berfungsi pada riwayat perjalanan pengguna, tetapi pada riwayat klik pada hasil pencarian, yang menyebabkan beberapa masalah. Objek ini kami sebut "puncak" (dari bahasa Inggris. The pick ). Heuristiknya terlihat seperti ini:

1. Untuk pengguna saat ini, kami mengambil semua puncak historisnya.
2. Kami memfilternya, meninggalkan mereka dengan target yang sama (dari / di mana).
3. , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
4. , , , , , .
5. , , 3:00 14:00, , .
6. - (), , - .
7. .

Algoritme ini berfungsi untuk sementara waktu, dan umumnya bagus untuk MVP (kita akan membicarakan metrik nanti), tetapi ada sejumlah kekurangan. Selain logika kerja yang agak primitif, ini tidak didasarkan pada perjalanan, tetapi pada pilihan pengguna. Karena itu, terkadang pengguna mendapatkan hasil pencarian yang tidak terlihat. Dan juga, karena cara "spesifik" untuk menyimpan riwayat puncak, agak sulit untuk melakukan analitik cepat. Berdasarkan ini, kami memutuskan untuk mencoba menerapkan pembelajaran mesin. Selanjutnya, kami akan mempertimbangkan rumusan masalah peringkat dan mengurangi masalah kami ke klasifikasi biner.

Pernyataan masalah peringkat

Sebelum berbicara tentang fitur, metrik, dan model, kita perlu mencari tahu jenis masalah yang ingin kita selesaikan. Mari kita lanjutkan dan pertama-tama mencoba merumuskan rumusan umum dari masalah peringkat. Ini terlihat seperti ini:



$$$X$ - banyak objek.



$$$X^l = \{x_1, \dots, x_l \}$ - sampel pelatihan. 



$$$i \prec j$ - urutan pasangan yang benar $$$(i, j)$



Tujuan: membangun fungsi peringkat $$$a: X \rightarrow ℝ$, dengan yang 

$$

$$i \prec j ⇒  a(x_i) < a(x_j)$$

Sekarang mari kita merumuskan tugas memeringkat hasil pencarian berdasarkan kueri. Ini berbeda dari masalah peringkat umum di mana alih-alih kumpulan umum objek yang perlu kita urutkan, dua set muncul$$$D$ dan $$$Q$ - banyak dokumen dan pertanyaan.



$$$D$ - kumpulan dokumen (jawaban).



$$$Q$ - banyak permintaan.



$$$D_q \subseteq D$ - kumpulan dokumen yang ditemukan oleh query q.



$$$X = Q \times D$ - objek adalah pasangan "request, document": $$$x \equiv (q, d), q \in Q, d \in D_q$



$$$Y$ - serangkaian peringkat (peringkat) yang dipesan.



$$$y(q, d): X \rightarrow Y$- skor relevansi.



Semakin tinggi nilainya$$$y(q, d)$, semakin relevan dokumennya $$$d$ permintaan $$$q$...



Urutan yang benar hanya ditentukan di antara dokumen-dokumen yang ditemukan dengan kueri yang sama$$$q$: 

$$

$$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$$

Dalam tugas kami merekomendasikan titik akhir rute, kumpulan peringkatnya adalah biner. Untuk pengguna, alamat yang disarankan mungkin relevan atau tidak relevan (tidak termasuk kasus dengan rute yang kompleks dengan beberapa titik akhir). Jika kita mempertimbangkan tugas dalam konteks pengguna, maka$$$q$- permintaan ke layanan, yang berisi id klien, posisi geografis, tanggal dan waktu;$$$D_q$- banyak titik akhir historis "B" untuk perjalanan pengguna (kami hanya membuat saran berdasarkan alamat perjalanan sebelumnya). Dan setiap jawaban yang valid$$$d \in D_q$ dalam permintaan $$$q$ dapat menjadi relevan bagi pengguna (dari titik saat ini dan saat ini, pengguna harus pergi tepat di sini) atau tidak relevan.



Demi kelengkapan, tinggal mendeskripsikan proses pembuatan sampel pasangan permintaan-respons dengan target. Pertimbangkan, untuk kesederhanaan, satu pelanggan yang telah melakukan 5 perjalanan. Mari kita beri peringkat perjalanan ini dari yang pertama hingga yang terakhir. Untuk perjalanan pertama, kami tidak tahu apa-apa tentang perjalanan pengguna, jadi kami tidak bisa menawarkan dia yang paling bijaksana menggunakan algoritma pembelajaran mesin yang dijelaskan (heuristik untuk pengguna baru berfungsi di sini). Untuk perjalanan kedua, kami mengetahui tujuan akhir dari perjalanan pertama dan kami dapat menawarkan alamat ini kepada pengguna jika ia berhasil melewati prosedur pasca-pemrosesan (terletak lebih dari 1 km dari lokasi saat ini, di wilayah yang sama, dll.). Untuk perjalanan ketiga, kita mungkin sudah memiliki satu hingga dua kemungkinan sedih,jika alamat akhir perjalanan kedua sama dengan alamat akhir perjalanan pertama dan jika alamat akhir berbeda. Jika sajest bertepatan dengan titik akhir "B" (yaitu, itu jatuh ke dalam hex yang sama dengan ukuran tetap), maka kami menetapkan 1 sebagai target, jika tidak - 0. Menurut algoritme ini, kami membentuk semua jenis pasangan formulir "permintaan - (mungkin) respons "Untuk setiap klien.



Jadi, kami telah mengurangi masalah peringkat menjadi masalah klasifikasi biner. Sekarang kita dapat berbicara tentang metrik kualitas.

Metrik

Dalam masalah peringkat, metrik yang menunjukkan proporsi jawaban yang benar dari dokumen $$$D_q$ ke atas $$$n$ daftar peringkat saat diminta $$$q$disebut Precision @ n . Kami tertarik pada Precision @ 1/2/3 , karena total Rasio Klik-Tayang untuk tiga posisi pertama adalah sekitar 95%. Pada saat yang sama, hanya ada satu alamat akhir yang benar (tentu saja, jika pengguna ingin meninggalkan alamat dari riwayatnya), oleh karena itu, metrik ini hanya akan menampilkan proporsi kasus ketika titik akhir yang benar "B" berada di 1/2/3 alamat teratas yang menyarankan algoritme kami.



Ingatlah itu dalam masalah kita$$$Y = \{0, 1\},\; y(q, d)$ - relevansi, $$$a(q, d)$Apakah fungsi peringkat yang dibutuhkan. Kemudian Presisi @ n dapat ditulis sebagai:

$$

$$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$$

Tanda dan model

Fitur untuk model dalam masalah kita dapat dibagi menjadi beberapa blok:

• Hanya untuk dokumen $$$d \in D_q$ (alamat akhir, titik "B").
• Hanya untuk permintaan $$$q$ (alamat awal, titik "A").
• Umum untuk meminta dan mendokumentasikan $$$(q, d)$ (rute dari "A" ke "B").
• Umum bagi pengguna.

Berikut beberapa contoh untuk masing-masingnya.



Contoh tanda hanya untuk dokumen (titik "B"):

1. Jumlah perjalanan ke titik "B" dalam K hari terakhir .
2. Jumlah perjalanan ke titik "B" menurut hari dan waktu.
3. Kapan perjalanan sebelumnya ke titik “B”.
4. Tandai bahwa perjalanan sebelumnya dilakukan ke titik "B".
5. Apakah titik "B" adalah alamat / rumah / kantor yang dipilih.

Contoh karakteristik untuk permintaan saja $$$q$ ( «» + /):

1. , .
2. «».
3. «» K .
4. «» .
5. «» //.
6. / $$$q$.
7. «».

, $$$(q, d)$ ( «» “”):

1. , .
2. .
3. .

:

1. K .
2. .
3. Statistik perjalanan historis (rata-rata, jumlah, jarak perjalanan median, dll.).

Hasilnya, kami mendapatkan lebih dari 100 fitur yang mendeskripsikan sepasang objek "dokumen permintaan". Karena kami ingin memaksimalkan Presisi @ 1/2/3 , adalah logis bahwa kami perlu memprediksi probabilitas perjalanan pengguna ke tujuan tertentu dan memberi peringkat kandidat yang mungkin sesuai dengan probabilitas yang diperoleh. Kami mencoba algoritma yang berbeda dan fungsi kerugian yang berbeda, dan menetapkan peningkatan gradien pada pohon dan logloss . Hasil yang diperoleh pada saat menggunakan heuristik:

Produksi

Biasanya, sebelum menghasilkan beberapa algoritme, fitur, dan model pelatihan yang rumit, Anda perlu memikirkan tentang bagaimana semua ini akan bekerja dalam pertempuran di bawah beban, sambil tidak melupakan penskalaan. Setelah berkumpul dengan tim pengembangan backend, kami membuat sketsa garis besar kasar tentang tampilan layanan kami. Kami memutuskan untuk menggabungkan model pembelajaran mesin yang terlatih dalam kerangka kerja web async-await Sanic, ke mana layanan pencarian akan mengirimkan permintaan. Selain penskalaan vertikal, kami telah menerapkan kemampuan untuk menerapkan ke banyak mesin. Permintaan ke layanan akan dikirim ke URL penyeimbang beban, dan kemudian proxy ke mesin ini atau itu menggunakan algoritma Round-robin akan terjadi. Setelah menerapkan prototipe pertama layanan, kami menyadari bahwa kami dapat mengurangi volume kueri di MySQL secara signifikan. Karena setiap pergeseran pin dengan pilihan titik umpan adalah permintaan pencarian baru, dan oleh karena itu untuk layanan kami, kami berpikir bahwa kami dapat menyimpan cache dengan riwayat perjalanan pengguna selama N menit dari saat permintaan ke Redis. Berkat ini, kami telah mengurangi beban di pangkalan sebanyak tiga kali. Hasilnya, skema layanan dapat direpresentasikan sebagai berikut:







Kami menyimpan permintaan ke layanan dan tanggapannya di ElasticSearch, dan kami mentransfer serta memantau metrik yang bertanggung jawab atas stabilitas pekerjaan di NewRelic.



Alur kerja umum layanan kami:

1. Layanan pencarian mengirimkan permintaan ke layanan petunjuk pencarian.
2. Penyeimbang memilih salah satu mesin dan mengirimkan permintaan ini padanya.
3. Di dalam mesin, permintaan dikirim ke salah satu pekerja terbuka atau memasuki antrian.
4. Di dalam pekerja:
   1. Kami memvalidasi permintaan yang masuk.
   2. Kami membuat permintaan di Redis, jika tidak ada riwayat pesanan untuk pengguna, maka kami pergi ke MySQL dan menulis data yang diterima ke Redis.
   3. Kami melakukan pemrosesan awal data dasar dan mengumpulkan fitur untuk model.
   4. Kami melakukannya predict_proba()sesuai dengan semua sadge yang dihasilkan dan mengurutkannya menurut "probabilitas".
   5. Kami melakukan pemrosesan tambahan data dan membentuk tanggapan.
   6. Kami mengembalikan jawabannya ke layanan pencarian.

Apa berikutnya?

Sekarang kami secara aktif menguji model kami menggunakan pengujian switchback untuk kemudian menarik kesimpulan dan menerapkan add-on tambahan ke algoritme untuk meningkatkan kualitas peringkat. Di masa depan, kami akan mencoba menambahkan fitur tambahan ke model, serta, bersama dengan desainer produk, menyiapkan solusi baru untuk "tampilan" sagests. Tentu saja, akan lebih bagus jika aplikasi kita sendiri memahami di mana / kapan / di mana / oleh mobil apa pengguna ingin pergi. Kami bekerja ke segala arah sehingga pesanan taksi benar-benar dibuat dalam satu klik.