Supponiamo di avere un insieme di $m$ vettori $X$ in $\R^N$. Non è difficile immaginare che ciò avvenga. In particolare, supponiamo che $N$ sia molto grande: allora non solo è costoso in termini di memoria tenere traccia di $X$, ma è anche in linea di massima costoso utilizzarli per varie operazioni algoritmiche. Allora se non ci interessa tenere traccia dei vettori in maniera esatta, ma ci accontentiamo di un certo livello di errore, allora magari vorremmo “comprimerli” esprimendoli in uno spazio euclideo di dimensione inferiore (diciamo $n$) in maniera da mantenere le distanze tra i vettori in maniera approssimativa. Questa compressione è una forma di riduzione dimensionale, in maniera non dissimile dall’analisi dei componenti principali che abbiamo considerato in un precedente articolo. Seguiamo queste dispense.
Questa possibilità è garantita dal lemma di Johnson-Lindenstrauss:
Teorema (Johnson-Lindenstrauss). Dato un insieme $X$ di $m$ vettori in $\R^N$, un livello di errore $0 < \epsilon < 1$, e un intero $n > \mathcal{O}( \log(m)/\epsilon^2 )$ allora esiste una funzione $f: \R^N \to \R^n$ tale che per ogni $\vec{x}, \vec{y} \in X$ abbiamo
$$(1-\epsilon)\norm{\vec{x}-\vec{y}}^2 \leq \norm{f(\vec{x})-f(\vec{y})}^2 \leq (1+\epsilon) \norm{\vec{x}-\vec{y}}^2$$
In altre parole, $\epsilon$ è l’errore relativo. È particolarmente interessante che $n$ non dipenda in nessun modo da $N$, ma solo da $m$, e in maniera solo logaritmica, il che è favorevole. Il teorema è anche particolarmente utile perché, come vedremo, un’approssimazione di $f$ è calcolabile in maniera molto semplice, e quindi la dimostrazione è costruttiva.
Questo teorema rappresenta un esempio di un fenomeno più generale noto come “concentrazione della misura”; ovvero che molto spesso la maggior parte della “misura” di uno spazio di dimensione molto elevata è concentrata in un sottospazio, e quindi non commettiamo un grande errore concentrandoci su questo sottospazio.
Dimostrazione. La dimostrazione, come abbiamo detto, è costruttiva. Iniziamo campionando una funzione di prova $f$ da una certa distribuzione di probabilità. Ovvero poniamo
$$f(\vec{x}) = \frac{1}{\sqrt{n}} A \vec{x}$$
dove $A$ è una matrice $n \times N$ i cui elementi sono indipendenti identicamente distribuiti e campionati da una distribuzione normale (gaussiana con media nulla e varianza uno), ovvero scriviamo $A_{ij} \sim N(0,1)$. Questa non è necessariamente la $f$ che cerchiamo; calcoliamo invece la probabilità che lo sia. Poiché $f$ è lineare, la disuguaglianza può essere scritta genericamente come
$$(1-\epsilon)\norm{\vec{v}}^2 \leq \norm{f(\vec{v})}^2 \leq (1+\epsilon) \norm{\vec{v}}^2$$
per un vettore generico $\vec{v}$ che poi porremo uguale alle varie coppie $\vec{v}=\vec{x}_i-\vec{x}_j$. Abbiamo detto che $A_{ij} \sim N(0,1)$. Ci interessa quindi calcolare la distribuzione di probabilità di $\norm{f(\vec{v})}^2$. Procediamo pezzo per pezzo. Esplicitando $f$ abbiamo
$$f(\vec{v})_i = \frac{1}{\sqrt{n}} \sum_{j=1}^N A_{ij} v_j$$
Ora se $X \sim N(\mu, \sigma^2)$ allora $\lambda X \sim N(\lambda \mu, \lambda^2 \sigma^2)$. Perciò abbiamo (niente somma) $A_{ij} v_j \sim N(0, v_j^2)$. Come abbiamo visto in un articolo precedente, se $X \sim N(\mu_X, \sigma_X^2)$ e $Y \sim N(\mu_Y, \sigma_Y^2)$ sono indipendenti, allora $X+Y \sim N(\mu_X+\mu_Y, \sigma_X^2+\sigma_Y^2)$. Ciò implica che
$$f(\vec{v})_i = \frac{1}{\sqrt{n}} \sum_{j=1}^N A_{ij} v_j \sim N(0, \tfrac{1}{n}\norm{\vec{v}}^2)$$
dove appunto $\norm{\vec{v}}^2 = \sum_{j=1}^N v_j^2$. Ciò implica in particolare che
$$ \frac{f(\vec{v})_i \sqrt{n}}{\norm{\vec{v}}} \sim N(0, 1)$$
Perciò
$$\frac{\norm{f(\vec{v})}^2 n}{\norm{\vec{v}}^2} = \sum_{i=1}^n \pqty{\frac{f(\vec{v})_i \sqrt{n}}{\norm{\vec{v}}}}^2$$
è la somma di $n$ variabili indipendenti normalmente distribuite, e quindi per definizione è distribuita secondo una distribuzione chi quadro $\chi_n^2$ con $n$ gradi di libertà. Perciò si tratta di calcolare la probabilità della disuguaglianza
$$(1-\epsilon)n \leq X \leq (1+\epsilon) n$$
dove $X \sim \chi_n^2$. Come abbiamo dimostrato in un precedente articolo,
$$\mathbb{P}\bqty{(1-\epsilon)n \leq X \leq (1+\epsilon) n} \geq 1-2\exp{\pqty{-n \epsilon^2 / 8 }}$$
Questa disuguaglianza fornisce una garanzia che la probabilità sia positiva se il membro destro è strettamente positivo. Più in generale, supponiamo di volere che la probabilità sia almeno $p > 0$. Allora dovremo avere
$$ 1-2\exp{\pqty{-n \epsilon^2 / 8 }} > p \qquad \leftrightarrow \qquad n > \frac{8}{\epsilon^2} \log{\pqty{\frac{2}{1-p}}} $$
Detto ciò, chiamiamo $e_{ij}$ l’evento che la disuguaglianza sia soddisfatta per $\vec{v}=\vec{x}_i-\vec{x}_j$. Allora la disuguaglianza sopra implica che abbiamo $\mathbb{P}(e_{ij}) \geq p$ e inoltre $\mathbb{P}(\overline{e_{ij}}) \leq 1-p$, dove la barra indica negazione. Ciò che vogliamo calcolare è la probabilità che la disuguaglianza sia soddisfatta per tutte le coppie, ovvero
$$\mathbb{P}\pqty{\cap_{ij} e_{ij}}$$
Come spesso accade, è più facile utilizzare la legge opposta, ovvero poiché per un evento qualsiasi $e$ abbiamo $\mathbb{P}(e) + \mathbb{P}(\overline{e})=1$, allora utilizzando le leggi di De Morgan, otteniamo
\begin{align}
\mathbb{P}\pqty{\cap_{ij} e_{ij}} &= 1-\mathbb{P}\pqty{\overline{\cap_{ij} e_{ij}}} = 1-\mathbb{P}\pqty{\cup_{ij} \overline{e_{ij}}} =\\
&\geq 1-\sum_{ij}\mathbb{P}(\overline{e_{ij}})\geq 1 -{m \choose 2} (1-p)\\
\end{align}
dove andando dalla prima alla seconda riga abbiamo utilizzato la disuguaglianza di Boole, e il fattore ${m \choose 2}$ è il numero di coppie di vettori (dato che appunto la probabilità dell’evento è la stessa per ognuna delle coppie).
Ora notiamo che abbiamo due effetti che si contrastano l’uno con l’altro: dall’ultima disuguaglianza, vogliamo $1-p$ il più piccolo possibile, così da avere la probabilità più grande. Ma se $1-p$ è troppo piccolo, allora dalla disuguaglianza sopra otteniamo che $n$ dev’essere molto grande e quindi non abbiamo compresso granché. Dobbiamo quindi bilanciare questi due effetti. Inoltre, poiché $ {m \choose 2} = \mathcal{O}(m^2)$, vogliamo $1-p = \mathcal{O}(1/m^{2})$ altrimenti la probabilità sarebbe irrilevante per un gran numero di vettori. Guardando bene anche la forma della disuguaglianza per $n$, scegliamo
$$ \frac{2}{1-p} = m^2$$
In questa maniera (sostituendo nella disuguaglianza per $n$) se la disuguaglianza $n > \frac{16 \log m}{\epsilon^2}$ è soddisfatta, allora abbiamo (sostituendo nell’altra disuguaglianza)
$$\mathbb{P}\pqty{\cap_{ij} e_{ij}} \geq 1-\frac{m (m-1)}{2} \frac{2}{m^2} = \frac{1}{m}$$
Ciò in un certo senso conclude la dimostrazione, ma va spiegato meglio. Tirando le somme, abbiamo dimostrato che una $f$ scelta a caso come sopra (ovvero come funzione lineare con una matrice $n \times n$ con componenti casuali gaussiani e $n > \frac{16 \log m}{\epsilon^2}$) ha una probabilità di almeno $1/m$ di comprimere gli $m$ vettori. Il teorema richiede di dimostrare l’esistenza di una tale $f$; poiché la probabilità è maggiore di zero, l’esistenza è dimostrata.
Tuttavia questa dimostrazione è anche costruttiva, nel senso che ci dice anche come costruire la mappa che effettivamente comprime i vettori con errore al massimo $\epsilon$. Ovvero scegliamo una $f$ a caso come sopra; questa comprimerà i vettori correttamente con probabilità $1/m$. Possiamo quindi calcolare le distanze e verificare se la compressione è accettabile (ovvero se tutte le disuguaglianze sono soddisfatte). Se lo sono, accettiamo questa $f$, mentre se non lo sono campioniamo un’altra $f$ a caso e ripetiamo il processo. Poiché la probabilità che $f$ sia corretta è $1/m$, allora ci aspettiamo di dover provare in media $\mathcal{O}(m)$ volte prima di trovare una $f$ che funzioni. Perciò il tempo richiesto per trovare $f$ è polinomiale in $m$, il che è favorevole. $\square$.
In questo articolo abbiamo dimostrato il lemma utilizzando una scelta particolare di mappa $f$, ovvero ne abbiamo campionato gli elementi da una distribuzione gaussiana. Ciò è particolarmente utile perché semplifica la dimostrazione. Chiaramente questa non è l’unica opzione possibile: cambiando la distribuzione da cui campioniamo $f$, possiamo ottenere delle proprietà migliori, come ad esempio un $n$ più piccolo o una probabilità di successo più elevata.