Mi chiamo Pavel Parkhomenko, sono uno sviluppatore ML. In questo articolo vorrei parlare della struttura del servizio Yandex.Zen e condividere i miglioramenti tecnici, la cui implementazione ha permesso di aumentare la qualità delle raccomandazioni. Da questo post imparerai come trovare in pochi millisecondi quelli più rilevanti per l'utente tra milioni di documenti; come eseguire la scomposizione continua di una grande matrice (composta da milioni di colonne e decine di milioni di righe) in modo che i nuovi documenti ricevano il loro vettore in decine di minuti; come riutilizzare la scomposizione della matrice utente-articolo per ottenere una buona rappresentazione vettoriale per il video.
Il nostro database di raccomandazioni contiene milioni di documenti di vari formati: articoli di testo creati sulla nostra piattaforma e presi da siti esterni, video, racconti e brevi post. Lo sviluppo di un tale servizio è associato a un gran numero di sfide tecniche. Ecco qui alcuni di loro:
- Dividere i compiti di elaborazione: eseguire tutte le operazioni pesanti offline e in tempo reale eseguire solo l'applicazione rapida dei modelli per essere responsabili di 100-200 ms.
- Prendi rapidamente in considerazione le azioni dell'utente. Per fare ciò è necessario che tutti gli eventi vengano immediatamente consegnati al consigliere e influenzino i risultati dei modelli.
- Realizza il feed in modo che per i nuovi utenti si adatti rapidamente al loro comportamento. Le persone che hanno appena aderito al sistema dovrebbero sentire che il loro feedback influenza le raccomandazioni.
- Comprendi rapidamente a chi consigliare un nuovo articolo.
- Rispondi rapidamente alla costante comparsa di nuovi contenuti. Ogni giorno vengono pubblicati decine di migliaia di articoli e molti di essi hanno una durata limitata (ad esempio, le notizie). Questo è ciò che li distingue da film, musica e altri contenuti longevi e costosi da creare.
- Trasferire la conoscenza da un dominio all'altro. Se un sistema di raccomandazione ha modelli addestrati per articoli di testo e vi aggiungiamo video, possiamo riutilizzare i modelli esistenti in modo che il nuovo tipo di contenuto si classifichi meglio.
Ti dirò come abbiamo risolto questi problemi.
Selezione dei candidati
Come ridurre il numero di documenti in esame di migliaia di volte in pochi millisecondi, senza praticamente alcun deterioramento della qualità della classifica?
Supponiamo di aver addestrato molti modelli ML, generato funzionalità basate su di essi e addestrato un altro modello che classifica i documenti per l'utente. Andrebbe tutto bene, ma non puoi semplicemente prendere e calcolare tutti i segni per tutti i documenti in tempo reale, se ci sono milioni di questi documenti e le raccomandazioni devono essere costruite in 100-200 ms. Il compito è selezionare un determinato sottoinsieme tra milioni, che verrà classificato per l'utente. Questa fase è solitamente chiamata selezione dei candidati. Ci sono diversi requisiti per questo. Innanzitutto la selezione deve avvenire in tempi molto brevi, in modo da lasciare più tempo possibile alla graduatoria stessa. In secondo luogo, avendo ridotto notevolmente il numero di documenti da classificare, dobbiamo preservare il più completamente possibile i documenti rilevanti per l'utente.
Il nostro principio di selezione dei candidati si è evoluto e al momento siamo arrivati a uno schema in più fasi:
Innanzitutto, tutti i documenti vengono divisi in gruppi e da ciascun gruppo vengono presi i documenti più popolari. I gruppi possono essere siti, argomenti, cluster. Per ogni utente, in base alla sua storia, vengono selezionati i gruppi a lui più vicini e da essi vengono tratti i migliori documenti. Utilizziamo anche l'indice kNN per selezionare i documenti più vicini all'utente in tempo reale. Esistono diversi metodi per costruire un indice kNN; il nostro ha funzionato meglio (Grafici gerarchici navigabili del piccolo mondo). Si tratta di un modello gerarchico che consente di trovare gli N vettori più vicini per un utente da un database di milioni in pochi millisecondi. Per prima cosa indicizziamo offline il nostro intero database di documenti. Poiché la ricerca nell'indice funziona abbastanza rapidamente, se sono presenti diversi incorporamenti forti, è possibile creare diversi indici (un indice per ogni incorporamento) e accedere a ciascuno di essi in tempo reale.
Abbiamo ancora decine di migliaia di documenti per ciascun utente. Questo è ancora molto per contare tutte le funzionalità, quindi in questa fase utilizziamo la classificazione leggera, un modello di classificazione pesante e leggero con meno funzionalità. Il compito è prevedere quali documenti un modello pesante avrà nella parte superiore. I documenti con il predittore più alto verranno utilizzati nel modello pesante, ovvero nell'ultima fase della classifica. Questo approccio consente di ridurre il database dei documenti considerati per l'utente da milioni a migliaia in decine di millisecondi.
Passo ALS in fase di esecuzione
Come tenere conto del feedback degli utenti subito dopo un clic?
Un fattore importante nelle raccomandazioni è il tempo di risposta al feedback degli utenti. Ciò è particolarmente importante per i nuovi utenti: quando una persona inizia a utilizzare il sistema di consigli, riceve un feed non personalizzato di documenti su vari argomenti. Non appena fa il primo clic, devi tenerne immediatamente conto e adattarti ai suoi interessi. Se si calcolano tutti i fattori offline, una risposta rapida del sistema diventerà impossibile a causa del ritardo. Quindi è necessario elaborare le azioni dell'utente in tempo reale. Per questi scopi, utilizziamo la fase ALS in fase di runtime per creare una rappresentazione vettoriale dell'utente.
Supponiamo di avere una rappresentazione vettoriale per tutti i documenti. Ad esempio, possiamo creare incorporamenti offline basati sul testo di un articolo utilizzando ELMo, BERT o altri modelli di machine learning. Come possiamo ottenere una rappresentazione vettoriale degli utenti nello stesso spazio in base alle loro interazioni nel sistema?
Principio generale di formazione e scomposizione della matrice utente-documentoConsideriamo m utenti e n documenti. Per alcuni utenti è nota la loro relazione con determinati documenti. Quindi queste informazioni possono essere rappresentate come una matrice mxn: le righe corrispondono agli utenti e le colonne corrispondono ai documenti. Poiché la persona non ha visto la maggior parte dei documenti, la maggior parte delle celle della matrice rimarranno vuote, mentre altre saranno riempite. Per ogni evento (mi piace, non mi piace, clic) nella matrice viene fornito un valore, ma consideriamo un modello semplificato in cui un mi piace corrisponde a 1 e un non mi piace corrisponde a -1.
Scomponiamo la matrice in due: P (mxd) e Q (dxn), dove d è la dimensione della rappresentazione vettoriale (solitamente un numero piccolo). Quindi ogni oggetto corrisponderà a un vettore d-dimensionale (per un utente - una riga nella matrice P, per un documento - una colonna nella matrice Q). Questi vettori saranno gli incorporamenti degli oggetti corrispondenti. Per prevedere se un utente apprezzerà un documento, puoi semplicemente moltiplicare i suoi incorporamenti.
Uno dei modi possibili per decomporre una matrice è ALS (Alternating Least Squares). Ottimizzeremo la seguente funzione di perdita:
Qui rui è l'interazione dell'utente u con il documento i, qi è il vettore del documento i, pu è il vettore dell'utente u.
Quindi il vettore utente ottimale dal punto di vista dell'errore quadratico medio (per vettori di documenti fissi) viene trovato analiticamente risolvendo la corrispondente regressione lineare.
Questo è chiamato il “fase ALS”. E lo stesso algoritmo ALS prevede che alternativamente fissiamo una delle matrici (utenti e articoli) e aggiorniamo l'altra, trovando la soluzione ottimale.
Fortunatamente, trovare la rappresentazione vettoriale dell'utente è un'operazione abbastanza veloce che può essere eseguita in fase di esecuzione utilizzando le istruzioni vettoriali. Questo trucco ti consente di tenere immediatamente conto del feedback degli utenti nel ranking. Lo stesso incorporamento può essere utilizzato nell'indice kNN per migliorare la selezione dei candidati.
Filtraggio collaborativo distribuito
Come eseguire la fattorizzazione incrementale della matrice distribuita e trovare rapidamente rappresentazioni vettoriali di nuovi articoli?
Il contenuto non è l’unica fonte di segnali di raccomandazione. Un'altra fonte importante sono le informazioni collaborative. Buone caratteristiche di ranking possono tradizionalmente essere ottenute dalla scomposizione della matrice utente-documento. Ma quando abbiamo provato a fare una tale scomposizione, abbiamo riscontrato dei problemi:
1. Abbiamo milioni di documenti e decine di milioni di utenti. La matrice non si adatta interamente a una macchina e la decomposizione richiederà molto tempo.
2. La maggior parte dei contenuti del sistema ha una vita breve: i documenti rimangono rilevanti solo per poche ore. Pertanto è necessario costruire la loro rappresentazione vettoriale il più rapidamente possibile.
3. Se si costruisce una scomposizione subito dopo la pubblicazione del documento, un numero sufficiente di utenti non avrà il tempo di valutarlo. Pertanto, la sua rappresentazione vettoriale molto probabilmente non sarà molto buona.
4. Se a un utente piace o non piace, non saremo in grado di tenerne immediatamente conto nella scomposizione.
Per risolvere questi problemi, abbiamo implementato una scomposizione distribuita della matrice utente-documento con frequenti aggiornamenti incrementali. Come funziona esattamente?
Supponiamo di avere un cluster di N macchine (N è nell'ordine delle centinaia) e di voler eseguire su di esse una scomposizione distribuita di una matrice che non si adatta a una macchina. La domanda è: come eseguire questa scomposizione in modo che, da un lato, ci siano abbastanza dati su ciascuna macchina e, dall'altro, in modo che i calcoli siano indipendenti?
Utilizzeremo l'algoritmo di decomposizione ALS descritto sopra. Diamo un'occhiata a come eseguire un passaggio ALS in modo distribuito: il resto dei passaggi sarà simile. Diciamo che abbiamo una matrice fissa di documenti e vogliamo costruire una matrice di utenti. Per fare ciò lo divideremo in N parti per righe, ciascuna parte conterrà all'incirca lo stesso numero di righe. Invieremo a ciascuna macchina le celle non vuote delle righe corrispondenti, nonché la matrice degli incorporamenti del documento (interamente). Poiché le sue dimensioni non sono molto grandi e la matrice del documento utente è generalmente molto scarsa, questi dati si adatteranno a una macchina normale.
Questo trucco può essere ripetuto per più epoche finché il modello non converge, alternando una per una la matrice fissa. Ma anche in questo caso, la decomposizione della matrice può richiedere diverse ore. E questo non risolve il problema che è necessario ricevere rapidamente gli incorporamenti di nuovi documenti e aggiornare gli incorporamenti di quelli su cui c'erano poche informazioni durante la costruzione del modello.
L'introduzione di rapidi aggiornamenti incrementali del modello ci ha aiutato. Diciamo che abbiamo un modello attualmente addestrato. Dopo la sua formazione, ci sono stati nuovi articoli con cui i nostri utenti hanno interagito, nonché articoli che hanno avuto poca interazione durante la formazione. Per ottenere rapidamente gli incorporamenti di tali articoli, utilizziamo gli incorporamenti degli utenti ottenuti durante il primo grande addestramento del modello ed eseguiamo un passaggio ALS per calcolare la matrice del documento data una matrice utente fissa. Ciò consente di ricevere gli incorporamenti abbastanza rapidamente, entro pochi minuti dalla pubblicazione del documento, e di aggiornare spesso gli incorporamenti di documenti recenti.
Per fare in modo che le raccomandazioni tengano immediatamente conto delle azioni umane, in runtime non utilizziamo gli incorporamenti degli utenti ottenuti offline. Invece, eseguiamo un passaggio ALS e otteniamo il vettore utente effettivo.
Trasferimento in un'altra area del dominio
Come utilizzare il feedback degli utenti sugli articoli di testo per creare una rappresentazione vettoriale di un video?
Inizialmente consigliavamo solo articoli di testo, quindi molti dei nostri algoritmi sono adattati a questo tipo di contenuti. Ma quando abbiamo aggiunto altri tipi di contenuti, ci siamo trovati di fronte alla necessità di adattare i modelli. Come abbiamo risolto questo problema utilizzando un esempio video? Un'opzione è riqualificare tutti i modelli da zero. Ma ciò richiede molto tempo e alcuni algoritmi richiedono dimensioni del campione di formazione, che non è ancora disponibile nella quantità richiesta per un nuovo tipo di contenuto nei primi momenti della sua vita sul servizio.
Siamo andati dall'altra parte e abbiamo riutilizzato i modelli di testo per il video. Lo stesso trucco ALS ci ha aiutato a creare rappresentazioni vettoriali di video. Abbiamo preso una rappresentazione vettoriale degli utenti basata su articoli di testo e abbiamo eseguito un passaggio ALS utilizzando le informazioni sulla visualizzazione del video. Quindi abbiamo facilmente ottenuto una rappresentazione vettoriale del video. E in fase di esecuzione calcoliamo semplicemente la prossimità tra il vettore utente ottenuto dagli articoli di testo e il vettore video.
conclusione
Sviluppare il nucleo di un sistema di raccomandazioni in tempo reale comporta molte sfide. È necessario elaborare rapidamente i dati e applicare metodi ML per utilizzare questi dati in modo efficace; costruire sistemi distribuiti complessi in grado di elaborare segnali degli utenti e nuove unità di contenuto in un tempo minimo; e molti altri compiti.
Nel sistema attuale, di cui ho descritto la progettazione, la qualità delle raccomandazioni per l'utente cresce insieme alla sua attività e alla durata della permanenza nel servizio. Ma ovviamente qui sta la difficoltà principale: è difficile che il sistema comprenda immediatamente gli interessi di una persona che ha interagito poco con i contenuti. Migliorare i consigli per i nuovi utenti è il nostro obiettivo principale. Continueremo a ottimizzare gli algoritmi in modo che i contenuti rilevanti per una persona arrivino nel suo feed più velocemente e non vengano mostrati contenuti irrilevanti.
Fonte: habr.com