Mi chiamo Pavel Parkhomenko, sono uno sviluppatore di ML. In questo articolo vorrei parlare del funzionamento del servizio Yandex.Zen e condividere i miglioramenti tecnici che hanno consentito di aumentare la qualità delle raccomandazioni. Dall'articolo scoprirai come trovare in pochi millisecondi i documenti più rilevanti per l'utente tra milioni di documenti; come eseguire una decomposizione 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 pochi minuti; come riutilizzare la decomposizione della matrice utente-articolo per ottenere una buona rappresentazione vettoriale per i video.
La nostra base di raccomandazioni contiene milioni di documenti di diversi formati: articoli testuali creati sulla nostra piattaforma e presi da siti esterni, video, narrazioni e brevi post. Sviluppare un servizio simile è legato a un numero elevato di sfide tecniche. Ecco alcune di esse:
- Suddividere i compiti computazionali: eseguire tutte le operazioni pesanti offline, mentre in tempo reale eseguire solo l'applicazione rapida dei modelli, per rispondere entro 100-200 ms.
- Calcolare rapidamente le azioni dell'utente. È necessario che tutti gli eventi vengano immediatamente inviati al raccomandatore e influenzino il risultato del lavoro dei modelli.
- Creare un feed in modo che per i nuovi utenti si adatti rapidamente al loro comportamento. Le persone che appena arrivano nel sistema devono sentire che il loro feedback influisce sulle raccomandazioni.
- Comprendere rapidamente a chi raccomandare un nuovo articolo.
- Reagire rapidamente alla continua apparizione di nuovi contenuti. Decine di migliaia di articoli vengono pubblicati ogni giorno, e molti di essi hanno una vita limitata (ad esempio, le notizie). Questa è la loro differenza rispetto a film, musica e altri contenuti di lungo termine e costosi da creare.
- Trasferire conoscenze da un dominio a un altro. Se nel sistema di raccomandazione ci sono modelli addestrati per articoli testuali e aggiungiamo video ad esso, possiamo riutilizzare i modelli esistenti affinché il nuovo tipo di contenuto venga classificato meglio.
Parlerò di come abbiamo affrontato queste sfide.
Selezione dei candidati
Come ridurre in millisecondi un gran numero di documenti analizzati di mille volte, senza praticamente compromettere la qualità del ranking?
Supponiamo di aver addestrato molti modelli ML, generato delle caratteristiche basate su di essi e addestrato un altro modello che classifica i documenti per l'utente. Tutto sarebbe perfetto, ma non si possono semplicemente calcolare tutte le caratteristiche per tutti i documenti in tempo reale, se questi documenti sono milioni e le raccomandazioni devono essere costruite in 100-200 ms. Il compito è selezionare un sottoinsieme da milioni di documenti, che verrà classificato per l'utente. Questa fase viene di solito chiamata selezione dei candidati. A essa sono richiesti alcuni requisiti. Innanzitutto, la selezione deve avvenire molto rapidamente, per lasciare il maggior tempo possibile per il ranking stesso. In secondo luogo, riducendo significativamente il numero di documenti per il ranking, dobbiamo preservare il più possibile i documenti pertinenti per l'utente.
Il nostro principio di selezione dei candidati si è evoluto nel tempo, e attualmente abbiamo raggiunto uno schema multilivello:
Inizialmente, tutti i documenti vengono suddivisi in gruppi e dai quali vengono presi i documenti più popolari. I gruppi possono essere siti, temi o cluster. Per ogni utente, in base alla sua storia, vengono selezionati i gruppi a lui più vicini e dai quali vengono poi estratti i migliori documenti. Utilizziamo anche un indice kNN per la selezione dei documenti più vicini all'utente in tempo reale. Ci sono diversi metodi per costruire l'indice kNN, il nostro ha funzionato meglio con (Grafi a Mondo Piccolo Navigabile Gerarchico). Questo è un modello gerarchico che consente di trovare in pochi millisecondi N vettori più vicini per l'utente da una base di milioni. In precedenza, indicizziamo offline tutto il nostro database di documenti. Poiché la ricerca nell'indice è piuttosto veloce, 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. Questo è ancora molto per conteggiare tutte le caratteristiche, quindi in questa fase applichiamo un ranking semplificato: un modello di ranking leggero con un numero ridotto di caratteristiche. L'obiettivo è prevedere quali documenti arriveranno in cima al ranking del modello pesante. I documenti con il punteggio predittivo più alto saranno utilizzati nel modello pesante, ossia nell'ultima fase del ranking. Questo approccio consente di ridurre in decine di millisecondi la base di documenti considerati per l'utente 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 importante per i nuovi utenti: quando una persona inizia a usare il sistema di raccomandazione, riceve un feed non personalizzato di documenti vari. Non appena effettua il primo clic, è necessario considerarlo immediatamente e adattarsi ai suoi interessi. Se tutti i fattori vengono calcolati offline, la reazione rapida del sistema diventa impossibile a causa dei ritardi. Quindi è necessario elaborare le azioni dell'utente in tempo reale. A questo scopo utilizziamo il passo ALS in tempo reale per costruire una rappresentazione vettoriale dell'utente.
Supponiamo di avere una rappresentazione vettoriale per tutti i documenti. Ad esempio, possiamo offline costruire embedding basati sul testo dell'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 all'interno del sistema?
Principio generale di formazione e decomposizione della matrice utente-documentoSupponiamo di avere m utenti e n documenti. Per alcuni utenti è noto il loro rapporto con alcuni documenti. Queste informazioni possono essere rappresentate sotto 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 dall'individuo, gran parte delle celle della matrice rimarrà vuota, mentre altre saranno riempite. Per ciascun evento (like, dislike, click) nella matrice è previsto un certo valore, ma consideriamo un modello semplificato in cui il like corrisponde a 1 e il dislike a -1.
Scomponiamo la matrice in due: P (m x d) e Q (d x n), dove d è la dimensione della rappresentazione vettoriale (di solito è un numero ridotto). Così, ad ogni oggetto corrisponderebbe un vettore di dimensione d (l'utente sarebbe una riga nella matrice P, il documento una colonna nella matrice Q). Questi vettori costituiranno gli embedding degli oggetti corrispondenti. Per prevedere se un documento piacerà a un utente, è sufficiente moltiplicare i loro embedding.
Uno dei modi possibili per scomporre la matrice è l'ALS (Alternating Least Squares). Andremo a ottimizzare 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 dell'utente ottimale dal punto di vista dell'errore quadratico medio (con i vettori dei documenti fissati) si trova analiticamente risolvendo la corrispondente regressione lineare.
Questo è chiamato "step ALS". E l'algoritmo ALS consiste nel fissare alternativamente una delle matrici (utenti e articoli) e aggiornare l'altra, trovando la soluzione ottimale.
Fortunatamente, trovare la rappresentazione vettoriale dell'utente è un'operazione piuttosto veloce, che può essere effettuata in tempo reale, utilizzando istruzioni vettoriali. Questo trucco consente di tener conto immediatamente del feedback dell'utente nel ranking. Lo stesso embedding può essere utilizzato anche nell'indice kNN per migliorare la selezione dei candidati.
Filtraggio collaborativo distribuito
Come eseguire la fattorizzazione della matrice 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 segnali nel ranking possono tradizionalmente derivare dalla scomposizione della matrice utente-documento. Ma tentando di fare tale scomposizione ci siamo imbattuti in problemi:
1. Abbiamo milioni di documenti e decine di milioni di utenti. La matrice non può essere ospitata su una sola macchina e la scomposizione sarà molto lunga.
2. La maggior parte dei contenuti nel sistema ha una vita breve: i documenti rimangono rilevanti solo per alcune ore. Pertanto, è necessario costruire la loro rappresentazione vettoriale il più rapidamente possibile.
3. Se si costruisce la scomposizione subito dopo la pubblicazione del documento, non avrà abbastanza valutazioni da parte degli utenti. Pertanto, la sua rappresentazione vettoriale sarà probabilmente di qualità non ottimale.
4. Se un utente mette un like o un dislike, non saremo in grado di tenerne conto immediatamente nella scomposizione.
Per risolvere i problemi elencati, abbiamo implementato una scomposizione distribuita della matrice utente-documento con aggiornamenti incrementali frequenti. Come funziona esattamente?
Supponiamo di avere un cluster di N macchine (N conta centinaia) e desideriamo effettuare una scomposizione distribuita della matrice, che non può essere ospitata su una sola macchina. La domanda è: come eseguire questa scomposizione in modo che, da un lato, ogni macchina abbia dati sufficienti e, dall'altro, che i calcoli siano indipendenti?
Utilizzeremo l'algoritmo di scomposizione ALS descritto sopra. Vediamo come eseguire un passo ALS in modo distribuito — gli altri passi saranno simili. Supponiamo di avere una matrice di documenti fissa e vogliamo costruire una matrice di utenti. A tal fine, la divideremo in N parti per righe, ciascuna contenente circa lo stesso numero di righe. Invieremo a ogni macchina le celle non vuote delle righe corrispondenti, così come la matrice degli embedding dei documenti (per intero). Poiché la sua dimensione non è molto grande, e la matrice utente-documento è generalmente molto sparsa, questi dati si adatteranno a una macchina normale.
Questo trucco può essere ripetuto per diverse epoche fino alla convergenza del modello, cambiando a turno la matrice fissa. Ma anche allora, la fattorizzazione della matrice può richiedere diverse ore. E questo non risolve il problema di dover ottenere rapidamente gli embedding di nuovi documenti e aggiornare gli embedding di quelli per cui si disponeva di poche informazioni durante la costruzione del modello.
Ci ha aiutato l'implementazione di un aggiornamento incrementale rapido del modello. Supponiamo di avere il nostro attuale modello addestrato. Dalla sua formazione, sono apparsi nuovi articoli con cui i nostri utenti hanno interagito, così come articoli che durante la formazione hanno avuto poche interazioni. 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 ALS per calcolare la matrice dei documenti con una matrice fissa degli utenti. Questo permette di ottenere embedding abbastanza rapidamente — in pochi minuti dopo la pubblicazione del documento — e di aggiornare frequentemente gli embedding dei documenti freschi.
Per garantire che le azioni dell'utente siano immediatamente considerate nelle raccomandazioni, durante il runtime non utilizziamo gli embedding degli utenti ottenuti offline. Invece, facciamo un passo ALS e otteniamo il vettore utente attuale.
Trasferimento in un'altra area tematica
Come utilizzare il feedback degli utenti sugli articoli di testo per costruire una rappresentazione vettoriale dei video?
Inizialmente, raccomandavamo solo articoli di testo, quindi molti dei nostri algoritmi sono ottimizzati per questo tipo di contenuto. Ma con l'aggiunta di contenuti di altro tipo, ci siamo imbattuti nella necessità di adattare i modelli. Come abbiamo affrontato questa sfida con i video? Una delle opzioni è riaddestrare tutti i modelli da zero. Ma questo richiede tempo, e inoltre alcuni algoritmi sono esigenti in termini di volume del campione di addestramento, che non è ancora disponibile in quantità sufficiente per il nuovo tipo di contenuto nei primi momenti della sua vita nel servizio.
Abbiamo seguito un'altra strada e riutilizzato modelli di testi per i video. Nella creazione delle rappresentazioni vettoriali dei video ci ha aiutato lo stesso trucco con ALS. Abbiamo preso la rappresentazione vettoriale degli utenti basata su articoli testuali e abbiamo effettuato un passo ALS, utilizzando le informazioni sulle visualizzazioni video. In questo modo abbiamo ottenuto senza sforzo una rappresentazione vettoriale dei video. E durante il runtime calcoliamo semplicemente la vicinanza tra il vettore dell'utente, ottenuto sulla base degli articoli testuali, e il vettore del video.
Conclusione
Lo sviluppo del nucleo di un sistema di raccomandazione in tempo reale è accompagnato da molteplici compiti. È necessario elaborare rapidamente i dati e applicare metodi di ML per un utilizzo efficace di questi dati; costruire sistemi distribuiti complessi, in grado di elaborare i segnali degli utenti e nuove unità di contenuto nel minor tempo possibile; e molte altre sfide.
Nell'attuale sistema, la cui architettura ho descritto, la qualità delle raccomandazioni per l'utente cresce insieme alla sua attività e alla durata del tempo trascorso sul servizio. Ma naturalmente, qui si cela anche la principale difficoltà: il sistema fatica a comprendere immediatamente gli interessi di una persona che ha interagito poco con il contenuto. Migliorare le raccomandazioni per i nuovi utenti è il nostro obiettivo chiave. Continueremo a ottimizzare gli algoritmi affinché i contenuti pertinenti per l'utente arrivino più velocemente nel suo feed, mentre quelli non pertinenti non vengano mostrati.
Fonte: habr.com
