UA MATH567 高維統計II 隨機向量10 Grothendieck不等式的證明 版本二：kernel trick

在介紹亞高斯隨機向量的更多應用之前，我們先簡單介紹一下核方法(kernel trick)。大概近十來年，張量數據(tensor data)越來越多了，比如MRI數據，基因組學的array data等等，如果按傳統多元統計的思路處理張量數據，那就是定義一些拉平算子把張量變成一個向量進行研究，這樣做的缺陷在于它完全破壞了張量數據本身的spatial correlation，所以我們需要另一種能夠不破壞張量數據的spatial structure的方法——核方法(kernel trick)。它的本質是在用低維的簡單的結構近似高維的、非線性的結構。

一個直觀例子，關于Kernel trick在做什么：函數$f(x_1,x_2)=x_1^2+x_2^2+3x_1{x}_2+x_1+x_2$是一個二次函數，我們可以用二次型分析它，但不管怎么說這都是一個需要一點工具才能分析的東西，但如果我們打破我們的刻板印象，不在$(x_1,x_2)$這個二維坐標系下討論這個函數，而是在$(x_1,x_2,x_1{x}_2,x_1^2,x_2^2)$這個五維的坐標系下討論這個函數，它就是是一個非常簡單的線性函數了。

---

Tensor and Array Data

假設我們要處理的張量數據用$A=(a_{i_1?i_k})\in {\mathbb{R}}^{n_1\times ?\times n_k}$表示，其中$i_1,?,i_k$是啞標（可以自由取遍所有可能的取值），$i_1=1,?,n_1,?,i_k=1,?,n_k$。

定義張量數據的內積為
$$?A,B?=\sum _{i_1,?,i_k}{a}_{i_1?i_k}{b}_{i_1?i_k}$$

定義rank 1 tensor（或者稱為簡單張量）為向量的張量積，比如
$$u\in {\mathbb{R}}^n,u???u=u^{?k}=(u_{i_1}?u_{i_k})\in {\mathbb{R}}^{n\times ?\times n}$$

性質
$$u,v\in {\mathbb{R}}^n,?u^{?k},v^{?k}?=?u,v{?}^k$$

證明
根據定義，
$$\begin{gathered} ?u^{?k},v^{?k}?=\sum _{i_1,?,i_k}{u}_{i_1}?u_{i_k}{v}_{i_1}?v_{i_k} \\ =\left(\sum _{i_1}{u}_{i_1}{v}_{i_1}\right)?\left(\sum _{i_1}{u}_{i_k}{v}_{i_k}\right)=?u,v{?}^k \end{gathered}$$

---

假設$K$是一個二元映射，$K:\Omega \times \Omega \to \mathbb{R}$，能用kernel trick分析這個二元映射的前提是存在一個Hilbert空間與映射$\Phi :\Omega \to H$，使得
$$K(u,v)=?\Phi (u),\Phi (v){?}_H,?u,v\in \Omega$$

比如對于任意解析函數$f$，$K=f(??,??)$，我們希望$?\Phi ,\Psi :{\mathbb{R}}^n\to {\mathbb{R}}^{n^k}$，使得
$$?u,v\in {\mathbb{R}}^n,f(?u,v?)=?\Phi (u),\Psi (v)?$$

(上面的性質就是一個例子)，這樣的kernel與Hilbert空間的存在性由下列定理保證：

Mercer定理、Moore-Aronszajn定理 $\{u_i{\}}_{i=1}^N$是$\Omega$中的任意點集，如果矩陣$[K(u_i,u_j){]}_{N\times N}$是半正定矩陣，則存在Hilbert空間與映射$\Phi :\Omega \to H$，使得
$$K(u,v)=?\Phi (u),\Phi (v){?}_H,?u,v\in \Omega$$

稱$\Phi$是特征映射(feature map)，稱$K$為kernel，$H$具有唯一性，可以根據$K$構建，稱其為reproducing kernel Hilbert space (RKHS)。

---

應用舉例

現在回到第七講討論的Grothendieck不等式，這個不等式提供了分析用半正定規劃近似整數規劃的誤差的方法。第九講中我們用半正定規劃+random rounding技巧近似了用整數規劃建模的圖的max-cut問題。對比這兩個思路我們可以獲得一個新的想法，我們能不能用random rounding技巧推Grothendieck不等式？

Grothendieck不等式
$A$是$m\times n$的實矩陣，$x_i,y_j\in \{?1,1\}$，假設$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$，則$?H$(Hilbert space)，$?u_i,v_j\in H$，$\Vert u_i\Vert =\Vert v_j\Vert =1$，
$$|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le K,K\le 1.783$$

第七講中證明這個不等式的第二步引入了隨機性，定義$g～N(0,I_N)$，定義$x_i=sgn?g,u_i?,y_j=sgn?g,v_j?$，我們沿用這個設定，但后續用random rounding的思路分析，根據Grothendieck恒等式（第九講）
$$E[x_i{y}_j]=\frac{2}{\pi }\arcsin ?u_i,v_j?$$

我們可以想象一下，如果$E[x_i{y}_j]=\frac{2}{\pi }?u_i,v_j?$，那么
$$\begin{gathered} K(A)=|\sum _{i,j}{A}_{i,j}?u_i,v_j?|=\frac{\pi }{2}|\sum _{i,j}{A}_{i,j}E[x_i{y}_j]| \\ =\frac{\pi }{2}E|\sum _{i,j}{A}_{i,j}[x_i{y}_j]|=\frac{\pi }{2}<1.783 \end{gathered}$$

也就是說我們甚至還能得到一個更小的上界，那么到底怎么才能實現$E[x_i{y}_j]=\frac{2}{\pi }?u_i,v_j?$呢？我們可以做一個變換：
$$u_i\to u_i^{\prime },v_j\to v_j^{\prime }$$

使得
$$?\beta ,\beta ?u_i,v_j?=\sin \frac{2}{\pi }?u_i^{\prime },v_j^{\prime }??\frac{\pi }{2}\arcsin \beta ?u_i,v_j?=?u_i^{\prime },v_j^{\prime }?$$

這個變換實際上就是kernel trick，$?\Phi ,\Psi :{\mathbb{R}}^n\to {\mathbb{R}}^{n^k}$，使得
$$?u,v\in {\mathbb{R}}^n,f(?u,v?)=?\Phi (u),\Psi (v)?$$

這里的$f(?u,v?)=\frac{\pi }{2}\arcsin \beta ?u,v?$，$u_i^{\prime },v_j^{\prime }$的存在性由Mercer定理、Moore-Aronszajn定理保證。

于是
$$\beta K(A)=|\sum _{i,j}{A}_{i,j}\beta ?u_i,v_j?|=|\sum _{i,j}{A}_{i,j}\frac{2}{\pi }\arcsin ?u_i^{\prime },v_j^{\prime }?|$$

根據Grothendieck恒等式，
$$\begin{gathered} |\sum _{i,j}{A}_{i,j}\frac{2}{\pi }\arcsin ?u_i^{\prime },v_j^{\prime }?|=|\sum _{i,j}{A}_{i,j}E[sgn?g,u_i?sgn?g,v_j?]| \\ =|\sum _{i,j}{A}_{i,j}E{x}_i{y}_j|\le E|\sum _{i,j}{A}_{i,j}{x}_i{y}_j|=1 \end{gathered}$$

所以$K=K(A)\le 1/\beta$，接下來的問題就是$\beta$可以是什么，這就要涉及前面的那個變換怎么構造了。

---

引理
存在一個Hilbert空間$H$，以及變換$\Phi ,\Psi :S^{n?1}\to S(H)$，使得
$$\frac{2}{\pi }\arcsin ?\Phi (u),\Psi (v)?=\beta ?u,v?,\beta =\frac{2}{\pi }\ln (1+\sqrt{2})$$

其中$S(H)$是$H$上的單位球面。

有了這個引理，我們就可以直接得到Grothendieck不等式了，下一講我們介紹這個引理的證明。

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计II 随机向量10 Grothendieck不等式的证明 版本二：kernel trick的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。