Mi chiamo Pavel Parkhomenko, sono uno sviluppatore ML. In questo articolo vorrei spiegare come funziona il servizio Yandex.Zen e condividere i miglioramenti tecnici che hanno aumentato la qualità delle raccomandazioni. Da questo post scoprirete come trovare, in pochi millisecondi, i documenti più rilevanti tra milioni di altri; come eseguire una fattorizzazione continua di una grande matrice (composta da milioni di colonne e decine di milioni di righe) affinché i nuovi documenti ottengano il loro vettore in pochi minuti; come riutilizzare la fattorizzazione matrice utente-articolo per ottenere una buona rappresentazione vettoriale per i video.
La nostra base di raccomandazione contiene milioni di documenti di diversi formati: articoli testuali, creati sulla nostra piattaforma e provenienti da siti esterni, video, narrazioni e brevi post. Lo sviluppo di un servizio simile comporta numerose sfide tecniche. Ecco alcune di esse:
- Dividere i compiti computazionali: eseguire tutte le operazioni pesanti offline, mentre in tempo reale eseguire solo l'applicazione rapida dei modelli, per rispondere in 100-200 ms.
- Tenere traccia rapidamente delle azioni degli utenti. È necessario che tutti gli eventi vengano inviati immediatamente al raccomandatore e influenzino i risultati dei modelli.
- Creare un feed che si adatti rapidamente al comportamento dei nuovi utenti. Le persone che accedono al sistema per la prima volta devono percepire che il loro feedback influisce sulle raccomandazioni.
- Comprendere rapidamente a chi raccomandare un nuovo articolo.
- Reagire prontamente alla continua apparizione di nuovi contenuti. Decine di migliaia di articoli vengono pubblicati ogni giorno e molti di essi hanno una durata limitata (ad esempio, le notizie). Questa è la loro differenza rispetto a film, musica e altri contenuti di lunga durata e costosi da creare.
- Trasferire conoscenze da un dominio all'altro. Se nel sistema di raccomandazione ci sono modelli addestrati per articoli testuali e aggiungiamo video, possiamo riutilizzare i modelli esistenti affinché il nuovo tipo di contenuto venga meglio classificato.
Vi racconterò come abbiamo affrontato queste sfide.
Selezione dei candidati
Come ridurre in pochi millisecondi un gran numero di documenti a migliaia, senza compromettere significativamente la qualità del ranking?
Supponiamo di aver addestrato molti modelli di machine learning, generato caratteristiche sulla base di essi e addestrato un ulteriore modello che classifica i documenti per l'utente. Tutto sarebbe perfetto, ma non possiamo semplicemente calcolare tutte le caratteristiche per tutti i documenti in tempo reale, se i documenti sono milioni e le raccomandazioni devono essere elaborate in 100-200 ms. L'obiettivo è selezionare un sottoinsieme da milioni di documenti, che sarà classificato per l'utente. Questo passaggio è solitamente chiamato selezione dei candidati. Ci sono alcuni requisiti. Innanzitutto, la selezione deve avvenire molto rapidamente, in modo che ci rimanga il maggior tempo possibile per la classificazione. In secondo luogo, riducendo notevolmente il numero di documenti da classificare, dobbiamo mantenere il massimo delle informazioni pertinenti per l'utente.
Il nostro principio di selezione dei candidati si è evoluto nel tempo, e attualmente abbiamo sviluppato uno schema multi-step:
Inizialmente, tutti i documenti vengono suddivisi in gruppi e dai quali vengono selezionati i documenti più popolari. I gruppi possono essere siti, temi o cluster. Per ogni utente, sulla base della sua storia, vengono selezionati i gruppi a lui più vicini e da questi vengono estratti i migliori documenti. Utilizziamo anche l'indice kNN per la selezione dei documenti più vicini all'utente in tempo reale. Esistono diversi metodi per costruire l'indice kNN, il nostro funziona meglio. (Hierarchical Navigable Small World graphs). Si tratta di un modello gerarchico che consente di trovare in pochi millisecondi i N vettori più vicini per l'utente da un database da milioni di elementi. Prima indicizziamo offline l'intero database dei documenti. Poiché la ricerca nell'indice è piuttosto rapida, con diversi embedding potenti, è possibile creare più indici (uno per ogni embedding) e accedere a ciascuno di essi in tempo reale.
Abbiamo decine di migliaia di documenti per ogni utente. Sono ancora troppi per contare tutte le caratteristiche, quindi a questo punto applichiamo un ranking leggero: un modello semplificato di ranking pesante con meno caratteristiche. L'obiettivo è prevedere quali documenti saranno in cima nella pesante modellazione. I documenti con il punteggio predittivo più alto verranno utilizzati nel modello pesante, cioè nell'ultima fase di ranking. Questo approccio consente di ridurre in decine di millisecondi il numero di documenti considerati per l'utente, passando da milioni a migliaia.
Passo ALS in tempo reale
Come tenere conto del feedback dell'utente subito dopo il clic?
Un fattore importante nelle raccomandazioni è il tempo di risposta al feedback dell'utente. Questo è particolarmente rilevante per i nuovi utenti: quando qualcuno inizia a utilizzare un sistema di raccomandazione, riceve un feed di documenti variabili e non personalizzati. Non appena fa il suo primo clic, è fondamentale tenerne conto e adattarsi ai suoi interessi. Se tutti i fattori vengono calcolati offline, la rapida reazione del sistema diventa impossibile a causa dei ritardi. Pertanto, è necessario elaborare le azioni dell'utente in tempo reale. A tal fine, utilizziamo il passo ALS in runtime per costruire una rappresentazione vettoriale dell'utente.
Supponiamo di avere una rappresentazione vettoriale per tutti i documenti. Ad esempio, possiamo offline costruire embedded basati sul testo di un articolo usando ELMo, BERT o altri modelli di machine learning. Come possiamo ottenere una rappresentazione vettoriale degli utenti nello stesso spazio basata sulle loro interazioni nel sistema?
Principio generale di formazione e scomposizione della matrice utente-documentoConsideriamo di avere m utenti e n documenti. Per alcuni utenti è nota la loro opinione su determinati documenti. Questa informazione può essere rappresentata in forma di matrice m x n: le righe corrispondono agli utenti, mentre le colonne ai documenti. Poiché la maggior parte dei documenti non è stata vista da una persona, gran parte delle celle della matrice rimarrà vuota, mentre altre saranno popolate. Per ogni evento (mi piace, non mi piace, clic) nella matrice è previsto un valore — ma consideriamo un modello semplificato in cui un mi piace corrisponde a 1 e un non mi piace a -1.
Scomponiamo la matrice in due: P (m x d) e Q (d x n), dove d è la dimensione della rappresentazione vettoriale (solitamente si tratta di un piccolo numero). A ciascun oggetto corrisponderà un vettore d-dimensionale (per l'utente, una riga nella matrice P, per il documento, una colonna nella matrice Q). Questi vettori saranno gli embedding degli oggetti corrispondenti. Per prevedere se un documento piacerà a un utente, possiamo semplicemente moltiplicare i loro embedding.
Uno dei possibili metodi di scomposizione della matrice è l'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.
Allora, il vettore dell'utente ottimale dal punto di vista dell'errore quadratico medio (con i vettori dei documenti fissati) si trova analiticamente risolvendo la rispettiva regressione lineare.
Questo è chiamato «passo ALS». L'algoritmo stesso di ALS consiste nel fissare alternativamente una delle matrici (utenti e articoli) e aggiornare l'altra per trovare la soluzione ottimale.
Fortunatamente, trovare la rappresentazione vettoriale dell'utente è un'operazione piuttosto veloce, che può essere eseguita in tempo reale utilizzando istruzioni vettoriali. Questo trucco consente di considerare immediatamente il feedback dell'utente nel ranking. La stessa embedding può essere utilizzata anche nell'indice kNN per migliorare la selezione dei candidati.
Filtraggio collaborativo distribuito
Come realizzare una fattorizzazione matriciale distribuita incrementale e trovare rapidamente la rappresentazione vettoriale di nuovi articoli?
Il contenuto non è l'unica fonte di segnali per le raccomandazioni. Un'altra fonte importante è l'informazione collaborativa. Buoni indicatori nel ranking possono tradizionalmente essere ottenuti attraverso la decomposizione della matrice utente-documento. Tuttavia, cercando di fare questa decomposizione, abbiamo incontrato dei problemi:
1. Abbiamo milioni di documenti e decine di milioni di utenti. La matrice non può essere completamente caricata su una singola macchina e la decomposizione sarà molto lunga.
2. La maggior parte dei contenuti nel 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 la decomposizione viene realizzata subito dopo la pubblicazione di un documento, non avrà ricevuto abbastanza valutazioni da parte degli utenti. Pertanto, la sua rappresentazione vettoriale sarà probabilmente non molto valida.
4. Se un utente ha messo un 'mi piace' o un 'non mi piace', non potremo considerarlo immediatamente nella decomposizione.
Per affrontare i problemi menzionati, abbiamo implementato una decomposizione distribuita della matrice utente-documento con aggiornamenti incrementali frequenti. Come funziona esattamente?
Supponiamo di avere un cluster di N macchine (N conta centinaia) e vogliamo eseguire una decomposizione distribuita della matrice che non può essere memorizzata su una sola macchina. La domanda è: come eseguire questa decomposizione in modo che, da un lato, ogni macchina abbia dati sufficienti e, dall'altro, i calcoli siano indipendenti?
Utilizzeremo l'algoritmo di decomposizione ALS descritto sopra. Vediamo come eseguire un passo ALS in modo distribuito: gli altri passi saranno simili. Supponiamo di avere fissata la matrice dei documenti e di voler costruire la matrice degli utenti. A tale scopo, suddivideremo la matrice in N parti per righe, ciascuna delle quali conterrà all'incirca lo stesso numero di righe. Invieremo a ciascuna macchina le celle non vuote delle righe corrispondenti, oltre alla matrice di embedding dei documenti (nella sua interezza). Poiché quest'ultima non è molto grande e la matrice utente-documento è generalmente molto sparsa, questi dati possono essere memorizzati su una macchina normale.
Questo trucco può essere ripetuto per diverse epoche fino alla convergenza del modello, alternando la matrice fissa. Anche in tal caso, la decomposizione della matrice può richiedere diverse ore. E questo non risolve il problema di dover ottenere rapidamente gli embedding di nuovi documenti e aggiornare quelli di cui ci sono poche informazioni durante la costruzione del modello.
Abbiamo beneficiato dell'implementazione di un aggiornamento incrementale veloce del modello. Supponiamo di avere un modello attualmente addestrato. Dalla sua formazione, sono emersi nuovi articoli con cui gli utenti hanno interagito, oltre a articoli che avevano avuto poche interazioni durante l'addestramento. Per ottenere rapidamente l'embedding di tali articoli, utilizziamo gli embedding degli utenti ottenuti durante il primo grande addestramento del modello e facciamo un passo di ALS per calcolare la matrice dei documenti con una matrice fissa degli utenti. Questo permette di ottenere embedding piuttosto rapidamente, in pochi minuti dopo la pubblicazione del documento, e di aggiornare frequentemente gli embedding dei documenti freschi.
Per fare in modo che le raccomandazioni tengano subito conto delle azioni degli utenti, durante il runtime non utilizziamo i feedback degli utenti raccolti offline. Invece, facciamo un passo ALS e otteniamo il vettore utente attuale.
Trasferimento a un'altra area del dominio
Come utilizzare il feedback degli utenti sugli articoli di testo per costruire una rappresentazione vettoriale dei video?
Inizialmente abbiamo raccomandato solo articoli testuali, quindi molti dei nostri algoritmi sono ottimizzati per questo tipo di contenuto. Tuttavia, con l'aggiunta di contenuti di altro tipo, abbiamo riscontrato la necessità di adattare i modelli. Come abbiamo affrontato questo problema, usando l'esempio dei video? Una delle opzioni è stata quella di riaddestrare tutti i modelli da zero. Ma questo è lungo, inoltre alcuni algoritmi sono esigenti riguardo al volume del campione di formazione, che non è ancora disponibile in quantità sufficienti per i contenuti di nuovo tipo nei primi momenti della loro vita sul servizio.
Abbiamo intrapreso un percorso diverso riutilizzando modelli di testo per i video. Nella creazione di rappresentazioni vettoriali dei video, ci ha aiutato il solito trucco con ALS. Abbiamo preso la rappresentazione vettoriale degli utenti basata su articoli di testo e abbiamo eseguito un passo ALS utilizzando le informazioni sulle visualizzazioni video. Così abbiamo ottenuto senza sforzo la rappresentazione vettoriale dei video. E a runtime, semplicemente calcoliamo la somiglianza tra il vettore utente ottenuto tramite articoli di testo e il vettore del video.
Conclusione
Lo sviluppo del nucleo di un sistema raccomandativo in tempo reale comporta molte sfide. È necessario elaborare rapidamente i dati e applicare metodi di machine learning per un uso efficace di questi dati; costruire sistemi distribuiti complessi in grado di elaborare segnali utente e nuove unità di contenuto nel minor tempo possibile; e molte altre sfide.
Nel sistema attuale, il cui dispositivo ho descritto, la qualità delle raccomandazioni per l'utente aumenta con la sua attività e la durata della sua permanenza nel servizio. Ma naturalmente, qui si cela anche la principale difficoltà: è difficile per il sistema capire subito gli interessi di una persona che ha interagito poco con i contenuti. Migliorare le raccomandazioni per i nuovi utenti è il nostro obiettivo fondamentale. Continueremo a ottimizzare gli algoritmi affinché i contenuti rilevanti per l'utente arrivino più rapidamente nel suo feed, mentre quelli non pertinenti non vengano mostrati.
Fonte: habr.com
