Sintesi Tecnica: Two-Sided Nearest Neighbors per la Completamento di Matrici

Definizione del Problema

Il documento affronta il problema del completamento di matrici nel contesto dei modelli a fattori latenti, concentrandosi specificamente su scenari in cui la matrice di verità fondamentale $\Theta$ è generata da una funzione latente non lineare $f$ che agisce su fattori latenti di riga e colonna sconosciuti. Il modello è definito come:
$$\theta_{i,j} = f(u_i, v_j)$$
dove $u_i \in \mathbb{R}^{d_1}$ e $v_j \in \mathbb{R}^{d_2}$ sono fattori latenti, e $f$ appartiene a una classe di funzioni Hölder con parametro di regolarità $\lambda \in (0, 1]$. Questo scenario generalizza i classici modelli bilineari (dove $f(u,v) = \langle u, v \rangle$) a funzioni non parametriche, potenzialmente non regolari (meno regolari rispetto a quelle Lipschitziane).

Una sfida critica affrontata è il regime Missing Not At Random (MNAR). A differenza del caso Missing Completely At Random (MCAR), dove la mancanza di dati è indipendente dai dati stessi, l'MNAR assume che la probabilità che un'voce sia osservata dipenda dai fattori latenti non osservati. Inoltre, gli autori considerano scenari in cui le voci possono essere deterministicamente mancanti (ovvero mancanti con probabilità 0 per specifiche configurazioni), un fenomeno comune nei sistemi reali come i motori di raccomandazione, dove le preferenze degli utenti determinano la visibilità.

L'obiettivo è stimare la verità fondamentale $\theta_{i,j}$ sia per le voci osservate che per quelle mancanti, senza conoscenza pregressa dei fattori latenti $U$ e $V$ o della funzione $f$, raggiungendo tassi minimax ottimali.

Metodologia: Two-Sided Nearest Neighbors (TS-NN)

Gli autori propongono l'algoritmo Two-Sided Nearest Neighbor (TS-NN). L'intuizione centrale è quella di approssimare le distanze latenti tra righe e colonne utilizzando i dati osservati, per poi mediare i risultati su vicinati risultanti.

1. Stima della Distanza: Poiché la funzione latente $f$ è sconosciuta, l'algoritmo costruisce proxy basati sui dati per le distanze quadrate $L_2$ tra i fattori di riga e di colonna.

   • L'algoritmo stima la distanza tra la riga $i$ e la riga $i'$ mediando le differenze al quadrato delle loro voci osservate attraverso le colonne comuni, corrette per la varianza del rumore ($2\sigma^2$).
   • Allo stesso modo, le distanze delle colonne sono stimate utilizzando le righe comuni.
   • Formalmente, la distanza di riga stimata è:
     $$\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$$
     (Una formula simmetrica si applica per le colonne).

2. Costruzione del Vicinato: Utilizzando i parametri di sintonizzazione $\eta_{row}$ e $\eta_{col}$, l'algoritmo definisce i vicinati:

   • $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
   • $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$

3. Stima: La stima $\hat{\theta}_{i,j}$ è la media di tutte le voci osservate $X_{i',j'}$ dove $i' \in N_{row}(i)$ e $j' \in N_{col}(j)$.

Contributi Chiave e Risultati Teorici

1. Adattività alla Regolarità e Ottimalità Minimax

Il principale risultato teorico è che il TS-NN si adatta alla regolarità $\lambda$ della funzione latente $f$.

• Regime MCAR: Sotto gli standard assunti per l'MCAR, gli autori dimostrano che con una corretta sintonizzazione ($\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$), l'errore quadratico medio (MSE) raggiunge il tasso minimax non parametrico ottimale:
  $$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$$
  Questo tasso coincide con quello di un algoritmo "oracle" che ha accesso ai veri fattori latenti $U$ e $V$.
• Regime MNAR: Il documento stabilisce che questa ottimalità è mantenuta anche in condizioni MNAR, a patto che sia soddisfatta una condizione di regolarità (Assunzione 6). Tale condizione richiede essenzialmente che il numero di voci osservate nell'intersezione dei vicinati di riga e colonna sia sufficientemente grande rispetto al prodotto delle dimensioni dei vicinati, anche se alcune voci sono deterministicamente mancanti.

2. Robustezza alla Mancanza Deterministica

Un contributo significativo è la dimostrazione che il TS-NN produce tassi di errore non banali anche quando una parte significativa della matrice è deterministicamente mancante (ad esempio, il 50% delle voci mancanti per specifiche coppie utente-item). I limiti teorici mostrano che finché la probabilità di mancanza "effettiva" all'interno dei vicinati rimane limitata lontano dallo zero, il tasso minimax viene preservato.

3. Garanzie Puntuali e Normalità Asintotica

• Limiti Puntuali: Il documento fornisce limiti di errore non asintotici per le singole voci $\hat{\theta}_{i,j}$. Questi limiti esibiscono una "maledizione della dimensionalità" rispetto ai parametri di sintonizzazione e alle dimensioni della matrice, che svanisce quando mediati a livello di popolazione (MSE).
• Normalità Asintotica: Sotto specifiche condizioni sulla dimensione del vicinato, gli autori dimostrano che lo stimatore puntuale è asintoticamente normale:
  $$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$$
  Questo risultato permette la costruzione di intervalli di confidenza validi per le stime controfattuali.

Risultati Empirici

Gli autori validano i loro risultati teorici attraverso:

1. Simulazioni Sintetiche:

   • Gli esperimenti confrontano TS-NN con diversi baseline, inclusi Row-NN, Column-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT) e SoftImpute.
   • Risultati: TS-NN raggiunge costantemente i migliori tassi di decadimento dell'MSE, eguagliando l'Oracle-TS-NN (che conosce i fattori latenti) nei contesti MCAR. Fondamentalmente, TS-NN mantiene prestazioni robuste nei contesti MNAR dove altri metodi (come DR-NN) degradano significativamente.
   • Adattività alla Regolarità: I tassi di decadimento empirici di TS-NN si allineano con le previsioni teoriche al variare del parametro di regolarità $\lambda$.
   • Intervalli di Confidenza: Gli intervalli di confidenza costruiti raggiungono una copertura quasi nominale (95%) per campioni di dimensioni moderate, validando il risultato della normalità asintotica.

2. Caso di Studio Reale (HeartSteps):

   • Il metodo viene applicato al dataset di salute mobile HeartSteps, un trial micro-randomizzato che coinvolge 37 utenti e punti decisionali nell'arco di 6 settimane.
   • Il dataset presenta caratteristiche MNAR (gli utenti sono indisponibili circa il 20% del tempo, e le notifiche vengono inviate solo se sono disponibili).
   • Risultati: In un setting di cross-validazione a 5 parti, TS-NN supera le varianti NN a lato singolo (Row-NN, Col-NN) e la baseline "All-Row-NN" nella stima dei passi controfattuali, dimostrando l'utilità pratica dell'approccio a due lati nel gestire la mancanza deterministica.

Significato e Rivendicazioni

Il documento rivendica di unificare due distinti domini di ricerca: il completamento di matrici non parametrico e l'analisi dei dati mancanti MNAR.

• Analisi Unica nel suo Genere: Gli autori affermano che questa è la prima analisi teorica di un metodo che gestisce contemporaneamente fattori latenti di riga e colonna sconosciuti, una funzione Hölder-continua non lineare (con $\lambda < 1$) e la mancanza di dati MNAR.
• Equivalenza Oracle: Il lavoro dimostra che la mancanza di conoscenza riguardo i fattori latenti non penalizza il tasso di convergenza; TS-NN performa allo stesso livello di un oracle con piena conoscenza di $U$ e $V$ nel regime intermedio.
• Robustezza: La metodologia si dimostra robusta ai pattern di mancanza deterministica, una caratteristica spesso ignorata nella letteratura standard sul completamento di matrici ma critica per applicazioni reali come i sistemi di raccomandazione.

Gli autori concludono che TS-NN fornisce una soluzione teoricamente fondata, adattiva e robusta per il completamento di matrici in ambienti complessi, non regolari e con mancanza di dati non casuale.