Gram矩阵和核函数

水深无声 2021-11-23 03:42 362阅读 0赞

*  **Gram矩阵定义**  
    内积空间中的一组向量 v 1 , v 2 , ⋯ &ThinSpace; , v n \\bm v\_1,\\bm v\_2,\\cdots,\\bm v\_n v1,v2,⋯,vn的**Gram矩阵**是**内积**的Hermitian矩阵（复共轭对称矩阵 A H = A A^H=A AH=A），定义为： G i j = ⟨ v i , v j ⟩ \{\\rm G\}\_\{ij\}=\\langle\\bm v\_i,\\bm v\_j\\rangle Gij=⟨vi,vj⟩，即：如果是一组实向量，则产生的Gram矩阵是对称矩阵（symmetric matrix）；如果是复向量，产生的Gram矩阵是复共轭对称矩阵。
 *  给定一个实矩阵 A A A，矩阵 A T A A^TA ATA是 A A A的**列向量**的Gram 矩阵，而矩阵 A A T AA^T AAT是 A A A的**行向量**的Gram矩阵。
 *  在Euclidean空间或以二范数为基础的Hilbert空间中，Gram矩阵是**半正定矩阵**：
    
     *  证明： 设 A = ( v 1 , v 2 , ⋯ &ThinSpace; , v n ) 设A=(\\bm v\_1,\\bm v\_2,\\cdots,\\bm v\_n) 设A=(v1,v2,⋯,vn)，由格拉姆矩阵的定义有 G = A H A \{\\rm G\}=A^HA G=AHA，我们知道 A H A A^HA AHA是半正定矩阵，可由 x H A H A x = ( A x ) H ( A x ) = ∣ ∣ A x ∣ ∣ 2 2 ≥ 0 \\bm x^HA^HA\\bm x=(A\\bm x)^H(A\\bm x)=||A\\bm x||\_2^2\\geq0 xHAHAx=(Ax)H(Ax)=∣∣Ax∣∣22≥0证明。
     *  应用：**正定核函数** K ( x i , x j ) = ϕ ( x i ) ⋅ ϕ ( x j ) K(\\bm x\_i,\\bm x\_j)=\\bm \\phi(\\bm x\_i)\\bm\\cdot\\bm \\phi(\\bm x\_j) K(xi,xj)=ϕ(xi)⋅ϕ(xj)通常所说的核函数都是正定核函数，为什么呢？通常不加以**显示地**定义映射函数 ϕ ( x ) \\bm \\phi(\\bm x) ϕ(x)，而是以核函数直接产生的映射内积的结果为导向（结果导向型），直接用核函数作用输入训练样本 X \\mathcal X X，产生核函数 K ( x , z ) K(\\bm x,\\bm z) K(x,z)对应的**Gram矩阵**： K = \[ K ( x i , x j ) \] m × m K=\\left\[K(\\bm x\_i,\\bm x\_j)\\right\]\_\{m\\times m\} K=\[K(xi,xj)\]m×m此核函数对应的Gram矩阵是**半正定矩阵**。因为映射函数 ϕ ( x ) \\bm \\phi(\\bm x) ϕ(x)本身就是一个向量， m m m个样本将产生 N N N个映射向量，这些向量的内积将产生Gram矩阵，由于Gram矩阵的正定性，所以必须使我们**直接定义**的核函数所对应的矩阵也是半正定的，才可以放心的不显示表示映射函数 ϕ ( x ) \\bm \\phi(\\bm x) ϕ(x)。
     *  疑问：为什么不显示地定义映射函数，然后直接做内积得结果呢？  
        这里涉及到**计算复杂度**的事情。我们假设最初的特征是 n n n维的，如果先把它映射到 n 2 n^2 n2维后，再做内积计算结果，那么计算复杂度变成什么了？明显是计算时间从原来的 O ( n ) O(n) O(n)变成了 O ( n 2 ) O(n^2) O(n2)。所以核函数应用而生，核函数既可以使得运算结果等同于非线性映射，同时又使得运算量远远小于非线性映射。  
        举例说明：  
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70][]
 *  **高斯核函数**（Gaussian kernel function）  
     K ( x , z ) = exp ⁡ ⟮ − ∣ ∣ x − z ∣ ∣ 2 2 σ 2 ⟯ K(\\bm x,\\bm z)=\\exp\\left\\lgroup-\\frac\{||\\bm x-\\bm z||^2\}\{2\\sigma^2\}\\right\\rgroup K(x,z)=exp⎩⎪⎪⎧−2σ2∣∣x−z∣∣2⎭⎪⎪⎫高斯核函数对应的映射函数 ϕ ( x ) \\phi(\\bm x) ϕ(x)是无穷维的，这一点非常重要。下面进行说明：  
    我们的目标是倒推 K ( x , z ) = ϕ ( x ) ⋅ ϕ ( z ) K(\\bm x,\\bm z)=\\phi(\\bm x)\\bm\\cdot\\phi(\\bm z) K(x,z)=ϕ(x)⋅ϕ(z)，且 ϕ ( x ) \\phi(\\bm x) ϕ(x)是无穷维的；  
    首先有泰勒展开： e x = 1 + x + x 2 2 ! + x 3 3 ! + ⋯ + x n n ! + R n e^x=1+x+\\frac\{x^2\}\{2!\}+\\frac\{x^3\}\{3!\}+\\cdots+\\frac\{x^n\}\{n!\}+R^n ex=1\+x\+2!x2\+3!x3\+⋯\+n!xn\+Rn接着： K ( x , z ) = exp ⁡ ⟮ − ∣ ∣ x − z ∣ ∣ 2 2 σ 2 ⟯ = exp ⁡ ⟮ − ( x − z ) ⋅ ( x − z ) 2 σ 2 ⟯ = exp ⁡ ⟮ − x 2 + z 2 − 2 x z 2 σ 2 ⟯ = exp ⁡ ⟮ − x 2 + z 2 2 σ 2 ⟯ ⋅ exp ⁡ ⟮ − x z σ 2 ⟯ = exp ⁡ ⟮ − x 2 + z 2 2 σ 2 ⟯ ⋅ \[ 1 + 1 σ 2 ⋅ x z 1 ! + ( 1 σ 2 ) 2 ⋅ ( x z ) 2 2 ! + ( 1 σ 2 ) 3 ⋅ ( x z ) 3 3 ! + ⋯ + ( 1 σ 2 ) n ⋅ ( x z ) n n ! + ⋯ &ThinSpace; \] = exp ⁡ ⟮ − x 2 + z 2 2 σ 2 ⟯ ⋅ \[ 1 ⋅ 1 + 1 1 ! x σ ⋅ z σ + 1 2 ! x 2 σ 2 ⋅ z 2 σ 2 + 1 3 ! x 3 σ 3 ⋅ z 3 σ 3 + ⋯ + 1 n ! x n σ n ⋅ z n σ n + ⋯ &ThinSpace; \] = ϕ ( x ) ⋅ ϕ ( z ) \\begin\{aligned\} K(\\bm x,\\bm z)&=\\exp\\left\\lgroup-\\frac\{||\\bm x-\\bm z||^2\}\{2\\sigma^2\}\\right\\rgroup=\\exp\\left\\lgroup-\\frac\{(\\bm x-\\bm z)\\bm\\cdot(\\bm x-\\bm z)\}\{2\\sigma^2\}\\right\\rgroup=\\exp\\left\\lgroup-\\frac\{\\bm x^2+\\bm z^2-2\\bm\{xz\}\}\{2\\sigma^2\}\\right\\rgroup\\\\ &=\\exp\\left\\lgroup-\\frac\{\\bm x^2+\\bm z^2\}\{2\\sigma^2\}\\right\\rgroup\\cdot\\exp\\left\\lgroup-\\frac\{\\bm\{xz\}\}\{\\sigma^2\}\\right\\rgroup\\\\ &=\\exp\\left\\lgroup-\\frac\{\\bm x^2+\\bm z^2\}\{2\\sigma^2\}\\right\\rgroup\\cdot\\left\[1+\\frac\{1\}\{\\sigma^2\}\\cdot\\frac\{\\bm\{xz\}\}\{1!\}+\\left(\\frac\{1\}\{\\sigma^2\}\\right)^2\\cdot\\frac\{(\\bm\{xz\})^2\}\{2!\}+\\left(\\frac\{1\}\{\\sigma^2\}\\right)^3\\cdot\\frac\{(\\bm\{xz\})^3\}\{3!\}+\\cdots+\\left(\\frac\{1\}\{\\sigma^2\}\\right)^n\\cdot\\frac\{(\\bm\{xz\})^n\}\{n!\}+\\cdots\\right\]\\\\ &=\\exp\\left\\lgroup-\\frac\{\\bm x^2+\\bm z^2\}\{2\\sigma^2\}\\right\\rgroup\\cdot\\left\[1\\cdot1+\\frac\{1\}\{1!\}\\frac\{\\bm x\}\{\\sigma\}\\cdot\\frac\{\\bm z\}\{\\sigma\}+\\frac\{1\}\{2!\}\\frac\{\\bm x^2\}\{\\sigma^2\}\\cdot\\frac\{\\bm z^2\}\{\\sigma^2\}+\\frac\{1\}\{3!\}\\frac\{\\bm x^3\}\{\\sigma^3\}\\cdot\\frac\{\\bm z^3\}\{\\sigma^3\}+\\cdots+\\frac\{1\}\{n!\}\\frac\{\\bm x^n\}\{\\sigma^n\}\\cdot\\frac\{\\bm z^n\}\{\\sigma^n\}+\\cdots\\right\]\\\\ &=\\phi(\\bm x)\\bm\\cdot\\phi(\\bm z) \\end\{aligned\} K(x,z)=exp⎩⎪⎪⎧−2σ2∣∣x−z∣∣2⎭⎪⎪⎫=exp⎩⎪⎪⎧−2σ2(x−z)⋅(x−z)⎭⎪⎪⎫=exp⎩⎪⎪⎧−2σ2x2\+z2−2xz⎭⎪⎪⎫=exp⎩⎪⎪⎧−2σ2x2\+z2⎭⎪⎪⎫⋅exp⎩⎧−σ2xz⎭⎫=exp⎩⎪⎪⎧−2σ2x2\+z2⎭⎪⎪⎫⋅\[1\+σ21⋅1!xz\+(σ21)2⋅2!(xz)2\+(σ21)3⋅3!(xz)3\+⋯\+(σ21)n⋅n!(xz)n\+⋯\]=exp⎩⎪⎪⎧−2σ2x2\+z2⎭⎪⎪⎫⋅\[1⋅1\+1!1σx⋅σz\+2!1σ2x2⋅σ2z2\+3!1σ3x3⋅σ3z3\+⋯\+n!1σnxn⋅σnzn\+⋯\]=ϕ(x)⋅ϕ(z)其中 ϕ ( x ) = exp ⁡ ⟮ − x 2 2 σ 2 ⟯ ( 1 , 1 1 ! x σ , 1 2 ! x 2 σ 2 , 1 3 ! x 3 σ 3 , ⋯ &ThinSpace; , 1 n ! x n σ n , ⋯ &ThinSpace; ) \\phi(\\bm x)=\\exp\\left\\lgroup-\\frac\{\\bm x^2\}\{2\\sigma^2\}\\right\\rgroup\\left(1,\\sqrt\{\\frac\{1\}\{1!\}\}\\frac\{\\bm x\}\{\\sigma\},\\sqrt\{\\frac\{1\}\{2!\}\}\\frac\{\\bm x^2\}\{\\sigma^2\},\\sqrt\{\\frac\{1\}\{3!\}\}\\frac\{\\bm x^3\}\{\\sigma^3\},\\cdots,\\sqrt\{\\frac\{1\}\{n!\}\}\\frac\{\\bm x^n\}\{\\sigma^n\},\\cdots\\right) ϕ(x)=exp⎩⎪⎪⎧−2σ2x2⎭⎪⎪⎫(1,1!1σx,2!1σ2x2,3!1σ3x3,⋯,n!1σnxn,⋯)请注意，这里的  x \\bm x x 是向量，因此这个映射函数 ϕ ( x ) \\phi(\\bm x) ϕ(x)是对 x \\bm x x整体做映射,这点需知晓。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70]: /images/20211122/08d04034314e494b8b4e3e7481f28041.png