高级算法之降维

降维Dimension Reduction

1 Metric Embedding

失真distortion: 对于$\alpha \ge 1$, 对于任意$x,y\in X$, 有

$$\frac{1}{\alpha}\cdot d(x,y)\le d(\phi(x),\phi(y))\le \alpha\cdot d(x,y)$$

2 The Johnson-Lindenstrauss Theorem

降维Dimension Reduction:

• 输入: $n$点: $x_1,x_2,\cdots,x_n\in \mathbb R^d$
• 输入: $n$点: $y_1,y_2,\cdots,y_n\in \mathbb R^k$满足$\forall i,j: (1-\epsilon)\Vert x_i-x_j \Vert\le\Vert y_i-y_j \Vert\le (1+\epsilon)\Vert x_i-x_j \Vert$

The Johnson-Lindenstrauss Theorem:

$\forall 0<\epsilon <1$, 对于任意$\mathbb R^d$中$n$点集合$S$, 存在映射$\phi :\mathbb R^d\to \mathbb R^k$, $k=O(\epsilon^{-2}\log n)$, 满足$\forall x,y\in S:$

$(1-\epsilon)\Vert x-y \Vert_2^2\le\Vert \phi(x)-\phi(y) \Vert_2^2\le (1+\epsilon)\Vert x-y \Vert_2^2$

证明: 概率法: 随机$k\times d$矩阵$A$:

$$Pr[\forall x,y\in S:(1-\epsilon)\Vert x-y\Vert_2^2\le\Vert Ax-Ay\Vert_2^2\le (1+\epsilon)\Vert x-y\Vert_2^2]\ge 1-O(\frac{1}{n})$$

具体如下:

2.1 JLT via Gaussian matrix

$A$: 所有元素服从正态分布$N(0,1/k)$.

证明如下:

$Pr[\forall x,y\in S:(1-\epsilon)\Vert x-y\Vert_2^2\le\Vert Ax-Ay\Vert_2^2\le (1+\epsilon)\Vert x-y\Vert_2^2]\ge 1-O(\frac{1}{n})$

即

$$\forall \text{ unit ventor } u\in \mathbb R^d: Pr[\vert\Vert Au\Vert_2^2-1\vert>\epsilon]<\frac{1}{n^3}$$

其中$|\Vert Au\Vert^2-1|>\epsilon$源自$1-\epsilon\le \Vert A\frac{(x-y)}{\Vert x-y\Vert}\Vert\le 1+\epsilon$

而$\frac{1}{n^3}$是因为有$O(n^2)$对$x,y\in S$, 也就是有$O(n^2 )$个独立的$u$, 需要w.h.p全部满足.

因为$A_{ij}\sim \mathcal N(0,\frac{1}{k})$, 所以

$$Y_i=(Au)_i=(\sum_{j=1}^d A_{ij}u_j)\sim \mathcal N(0,\frac{\sum_{j=1}^d u_j^2}{k})=\mathcal N(0,\frac{1}{k})$$

所以 $\Vert Au\Vert_2^2=\sum_{i=1}^k(Au)_i^2=\sum_{i=1}^k Y_i^2$满足$\chi^2$分布.

所以

$$\mathbb E[Y_i^2]=Var[Y_i]+\mathbb E[Y_i]^2=\frac{1}{k}$$

因此

$$\mathbb E[\Vert Au\Vert_2 ^2]=\sum_{i=1}^k\mathbb E[Y_i^2]=1$$

2.2 Concentration of $\chi ^{2}$-distribution

Chernoff bound for $\chi ^{2}$-distribution:

对于任意正的$\epsilon,\delta <1/2$, 存在正整数$k=O(\epsilon^{-2}\log \frac{1}{\delta})$, 满足对于独立同分布的随机变量$Y_1,\cdots,Y_k\sim \mathcal N(0,1/k)$,

$$Pr[\vert\sum_{i=1}^k Y_i^2-1\vert >\epsilon]<\delta$$

证明见slides.

根据该不等式, 就证明了The Johnson-Lindenstrauss Theorem.

3 Nearest Neighbor Search (NNS)

NNS

数据: $n$ 个点 $y_1,\cdots,y_n\in X$

询问: 点 $x\in X$

找到离$x$最近的$y_i$

ANN

数据: $n$ 个点 $y_1,\cdots,y_n\in X$

询问: 点 $x\in X$

c-ANN(近似最近邻): 找到$y_i$满足$dist(x,y_i)\le c\cdot \min_{1\le j\le n}dist(x,y_i)$

(c,r)-ANN(近似近邻):

如果存在$y_j$满足$dist(x,y_j)\le r$, 返回一个$y_i$满足$dist(x,y_i)\le c\cdot r$ ;

如果任意$y_i$都有$dist(x,y_i)>c\cdot r$, 返回’no’;

否则返回上面两种中任意一个.

c-ANN和(c,r)-ANN两者关系:

• 令$R=\frac{D_{max}}{D_{min}}$. $D_{max}=\max_{1\le i<j\le n}dist(y_i,y_j)$, $D_{min}$同理.

• 如果$\forall r, (\sqrt c,r)$-ANN可以在$s$空间$t$询问时间内解决, 则$c$-ANN可以在$O(s\log_c R)$空间$O(t\log\log_c R)$询问时间内解决

• 方法: 打表($\log_c R$项)+二分
  • 每次查询的$r$: $r_0=D_{min}$, $r_k=c^{k/2}r_0$
  • 找到$i$满足刚好$i$返回’no’, $i+1$非’no’:
    • $r_{i}$返回值’no’, 即内圈内无点, 即$dist_{min}>r_{i}$
    • $r_{i+1}$返回的点$y$一定满足$dist(x,y_i)\le \sqrt c r_{i+1}=cr_i<c \cdot dist_{min}$, 即为c-ANN答案.

(c,r)-ANN算法

对于$X=\{0,1\}^d$:

$k,p,s$为待定常数, 随机$k\times d$的布尔矩阵$A$, 每个项为独立的参数$p$伯努利随机变量;

对于$i=1,2,\cdots,n$: 令$z_i=Ay_i\in\{0,1\}^k$定义于有限域$GF(2)$;

存储所有的$s$球, $B_s(u)=\{y_i|dist(u,z_i)\le s\}$, $u\in\{0,1\}^k$.

询问过程: 找到$B_s(Ax)$; 如果$B_s(Ax)=\emptyset$, 返回’no’; 否则返回任意一个$y_i\in B_s(Ax)$

复杂度:

空间$O(n2^k)$, 询问时间$O(kd)$计算+$O(1)$内存访问

正确率

$\forall x,y\in\{0,1\}^d$, $dist(x,y)\le r$则$\Pr[dist(Ax,Ay)>s]<1/n^2$;

$dist(x,y)>c r$则$\Pr[dist(Ax,Ay)\le s]<1/n^2$. 即w.h.p解决$(c,r)$-ANN问题.

证明见ppt.

参数选取:

$k=\frac{\ln n}{(1/8-2^{-(c+2)})^2}$, $p=\frac{1}{2}-2^{-1-1/r}$, $s=(\frac{3}{8}-2^{-(c+2)})k$

空间$n^{O(1)}$, 询问时间$O(d\ln n)$.

4 Locality-Sensitive Hashing (LSH)

(r,cr,p,q)​-LSH函数

如果$\forall x,y\in X$:

$dist(x,y)\le r =>Pr[h(x)=h(y)]\ge p$

$dist(x,y)> cr =>Pr[h(x)=h(y)]\le q$

则随机函数$h:X\to U$是$(r,cr,p,q)$-LSH.

性质:

$\exist (r,cr,p,q)$-LSH $h:X\to U$ => $\exist (r,cr,p^k,q^k)$-LSH $h:X\to U^k$ :

证明:

直接根据$h$构造独立的$h_1,\cdots,h_k$, $g(x)=(h_1(x),\cdots,h_k(x))\in U^k$

解(c,r)-ANN问题

假设我们有(r,cr,$p^*$,1/n)-LSH g:$X\to U$, 我们将$y_1,\cdots,y_n$按照$g(y_i)$的顺序存储

询问$x\in X$: 二分搜索找到所有的满足$g(x)=g(y_i)$的$y_i$;

其中如果碰到$y_i$满足$dist(x,y_i)\le cr$则返回这个$y_i$; 否则返回’no’.

复杂度:

空间$O(n)$, 时间$O(\log n)+O(1)$(期望)

正确率:

(c,r)-ANN实际答案为’no’: 必定正确, 因为会检查是否真的有$dist(x,y_i)\le cr$, 所以算法一定也返回no

(c,r)-ANN实际答案不是’no’: 以概率$\ge p^*$正确, 因为有1-p的概率会$dist(x,y)\le r$但是$g(x)\ne g(y)$, 导致漏掉

改进:

取$l=1/p^*$, 找$l$个独立的$g$, 在这$l$个表中找到至多$10l$(随便定的参数)个$y_i$满足$\exists j ~g_j(x)=g_j(y_i)$, 检查有没有和$x$距离小于等于$cr$的$y_i$, 有就返回, 否则返回’no’.

分析:

$$\begin{aligned} \Pr[\text{answer 'no'}]&\le \Pr[\forall j, g_j(x)\ne g_j(y_s)]+\\ &\Pr[>10l\text{ bad }y_i\text{ that }dist(x,y_i)>cr\text{ but }\exist j~s.t. g_j(x)=g_j(y_j)]\\ &\le (1-p^*)^l+ E[\text{number of such bad }y_i]/10l\\ &\le 1/e+\frac{l\cdot n\cdot (1/n)}{10l}\\&\le 1/e+0.1<0.5 \end{aligned}$$

其中使用了马尔科夫不等式.

实际步骤

如果最初有(r,cr,p,q)-LSH $h:X\to U$, 可以构造出(r,cr,$p^k$,1/n)-LSH $g:X\to U^k$, 其中$k=\log_{1/q}n$, 所以$p^k=p^{\log_{1/q}n}=n^{-\rho}$, 其中$\rho=\frac{\log p}{\log q}$. 这样我们就可以解决(c, r)-ANN, 空间复杂度$O(n^{1+\rho})$, 询问时间$O(n^\rho \log n)$, 单边错误率<0.5.

LSH函数举例

对于$X=\{0,1\}^d$, 可以使用如下的LSH函数:

$\forall x\in\{0,1\}^d: h(x)=x_i\text{ for uniform random }i\in[d]$

则有

$dist(x,y)\le r =>Pr[h(x)=h(y)]\ge 1-r/d$

$dist(x,y)> cr =>Pr[h(x)=h(y)]\le 1-cr/d$

所以$\rho=\frac{\log(1-r/d)}{\log(1-cr/d)}\le \frac{1}{c}$, 可以解决汉明空间内的(c, r)-ANN问题, 空间复杂度$O(n^{1+1/c})$, 询问时间$O(n^{1/c}\log n)$, 单边错误率<0.5.