1.支持向量積-核函數

核(kernel)的概念由Aizenman et al.于1964年引入模式識別領域，原文介紹的是勢函數的方法。在那之后，核函數在模式識別領域沉積了很久。1992年Boser 等人的在解決支持向量機算法時，重新將核的概念引入機器學習領域；從此引發了核函數研究應用的熱潮。一個最簡單的應用就是：利用核方法擴展經典算法，將算法中的內積替換成核函數。

在支持向量機中，核函數是 將 原線性不可分的特征空間中的特征向量$x$，映射到 線性可分的高維特征空間的特征向量$?(x)$，然后,特征向量$?(x)$之間求內積的一個表達式。(核函數就是一個表達式)
$$k(x_n,x_m)=?(x_n{)}^T?(x_m)$$

核函數的巧妙之處：高維空間中特征向量的內積表達式，可以直接用低維特征向量的各個維度的坐標表示。所以，只需將低維度特征$x,x^{\prime }$帶入核函數$k(x,x^{\prime })$求函數值，就等價于$x?>?(x),x^{\prime }?>?(x^{\prime })=>求內積<?(x),?(x^{\prime })>$的過程，當高維空間維很高時，內積求解十分緩慢，所以核函數是一個十分便利的工具。

基本概念： 核函數$k(x,x^{\prime })$，樣本（特征向量）{xin}\{x_i^n\}{xin?}，gram矩陣K={Ki,j}K=\{ K_{i,j} \}K={Ki,j?},$K_{i,j}=k(x_i,x_j)$
$$?\begin{array}{ccccc}k(x_1,x_1)& k(x_1,x_2)& ...& k(x_1,x_n)& \\ k(x_2,x_1)& k(x_2,x_2)& ...& k(x_2,x_n)& \\ ...& ...& ...& ...& \\ k(x_n,x_1)& k(x_n,x_2)& ...& k(x_n,x_n)& \end{array}?$$

詳細SVM與核函數參見（對偶問題的求解巴拉巴拉）：https://cuijiahua.com/blog/2017/11/ml_9_svm_2.html

---

---

2.一個函數為核函數的條件

可以通過多種方式構造核函數，（1）原始的映射構造法、（2）核函數性質+簡單核函數構造法[RBF核函數就可以從此構造出來]、（3）概率生成式模型開始構造。

高維特征向量的內積 實際是 低維特征向量 各個分量的函數=》高維內積 是一個函數。但是，并非每一個函數都對應著一個高維內積。只有當一個函數滿足mercer定理時，它才能作為一個核函數。所以可以通過mercer定義判斷一個函數是否可以作為一個核函數。

---

Mercer定理： 對稱且半正定的函數可以作為一個核函數。

（離散化）簡單理解：“半正定”三個字常見于矩陣分析中。此處，可通過判定對稱函數Gram 矩陣的半正定性，進而判斷源函數的半正定性質。一個n × n的實對稱矩陣A是正定的當且僅當對于所有的非零實系數向量z，都有$z^{T}Az>0$。

具體做法：將樣本{xi=1i=n}\{x_{i=1}^{i=n}\}{xi=1i=n?}帶入函數$k(x,x^{\prime })$，計算gram矩陣K={Ki,j}K=\{ K_{i,j} \}K={Ki,j?},$K_{i,j}=k(x_i,x_j)$，判定gram矩陣的半正定性。

（連續化）定義：一個對稱函數$k(x,x^{\prime })$是半正定的，當且僅當對于任意的函數g下式成立：
$${\int }_{\mathcal{X}}g(x)k(x,x^{\prime })g(x^{\prime })dxd{x}^{\prime }\ge 0$$

---

通過Gram矩陣特征值分解(譜分解)，可以將$k(x_i,x_j)$表示成gram矩陣特征值與特征向量分量組合的形式：
$$Q^{T}KQ=diag({\lambda }_1,{\lambda }_2,...,{\lambda }_n)=\Lambda$$

$$K=Q\Lambda Q^T$$

$Q$為特征向量矩陣，$v_i$為n維向量，其第二個下標表示該向量分量：
$$Q=[v_1,v_2,...,v_n]$$

$$K=Q\Lambda Q^T=[{\lambda }_1{v}_1,{\lambda }_2{v}_2,...,{\lambda }_n{v}_n][v_1,v_2,...,v_n{]}^T$$
$$=?\begin{array}{ccccc}{\lambda }_1{v}_{11}& {\lambda }_2{v}_{21}& ...& {\lambda }_n{v}_{n1}& \\ {\lambda }_1{v}_{12}& {\lambda }_2{v}_{22}& ...& {\lambda }_n{v}_{n2}& \\ ...& ...& ...& ...& \\ {\lambda }_1{v}_{1n}& {\lambda }_2{v}_{2n}& ...& {\lambda }_n{v}_{nn}& \end{array}??\begin{array}{ccccc}{v}_{11}& v_{12}& ...& v_{1n}& \\ v_{21}& v_{22}& ...& v_{2n}& \\ ...& ...& ...& ...& \\ v_{n1}& v_{n2}& ...& v_{nn}& \end{array}?$$

$$k(x_i,x_j)=\sum _{k=1}^n{\lambda }_k{v}_{ki}{v}_{kj}$$

注意：$v_{ki}$第一個下標表示：這是第$k$個特征向量，第二個下標表示：這是第$k$個特征向量的第$i$個分量。
當特征$n\to \infty$時，離散-》連續。$v_{ki}$可以看做第k個特征函數的第i個函數值，即${\psi }_k(x_i)$。此時，核函數可以寫為：
$$k(x,x^{\prime })=\sum _j{\lambda }_j{\psi }_j(x){\psi }_j(x^{\prime })$$

---

用到的工具：

Mercer定理的一點證明： https://blog.csdn.net/sinat_22510827/article/details/79116612
矩陣特征值分解：https://blog.csdn.net/weixin_42018112/article/details/80250206：
矩陣A的特征向量特征值:$Ax=\lambda x$,矩陣A作用于(每一矩陣都對應一個變換)特征向量$x$，其效果等價與對向量$x$做尺度變換。（所以$x$真是一個很神奇的方向呢！！）

每一個矩陣A都相似于一個上三角矩陣：通初等變換可以將一個矩陣轉換成一個上三角陣，將這些初等變換乘在一起，就構成了一個變換矩陣。

每次的初等變換選擇 特征值變換，且，矩陣A是一個對稱矩陣，那矩陣A可以進行特征值分解:
$$Q^{T}AQ=diag({\lambda }_1,{\lambda }_2,...,{\lambda }_n)$$

$Q$的列向量組成$A$的一個完備標準正交向量系。

---

---

3.核函數與希爾伯特空間

原來線性映射$?(x)$ ，它將原始特征空間中的數據點映射到另一個高維空間中。其實這個高維空間在這里有一個華麗的名字——“再生核希爾伯特空間 (Reproducing Kernel Hilbert Space, RKHS)”[1]

所以：每一個核函數都對應著自己的一個再生核希爾伯特空間。

下面先介紹希爾波特空間，再介紹再生核希爾伯特空間。

3.1希爾伯特空間-Hilbert空間

從 泛函 說 希爾伯特空間[2]
希爾伯特空間 是 希爾伯特 在解決 無窮維線性方程組 時提出的概念，原來的線性代數理論都是基于有限維歐幾里得空間的，無法適用，這迫使希爾伯特去思考無窮維歐幾里得空間，也就是無窮序列空間的性質。

$l^2$空間：所有2范數$\sum x_n^2$（n為向量的下標）為有限的 無窮維向量$x$ 組成的空間。這是最早的Hilbert space。

$L^2$空間：單位閉區間上所有平方可積的實函數（就是說 f（x）的平方在[0，1]上的積分存在且有限）按照函數的加法和數乘成為一個線性空間。
$$\int f^2(x)dx$$

$L^2$希爾伯特空間是一個函數空間，其中定義內積如下：
$$<f，g>=\int |f?g|dx$$

范數:
$$\Vert f\Vert =\sqrt{<f，f>}=\sqrt{\int f^2(x)dx}$$

泛函：就是自變量為函數，因變量為實數的映射。一個簡單的例子，某一個泛函的定義域在$L^2$Hilbert space上。

---

從 定義 說 希爾伯特空間
向量空間：空間中的點具有加法和數乘的操作
內積空間：向量空間上定義一個內積操作
賦范空間：根據內積可以定義一個范數
度量空間：范數可以用于定義一個度量
Hilbert Space：如果一個空間在其定義的度量下是完備的，那么這個空間叫做 Hilbert Space。[1]
完備性：一個空間上的任意柯西序列必收斂于空間中的某一點——相當于閉集的定義

對于常見的${\mathbb{R}}^n$,滿足內積運算，能夠推導出$l_2$范數，且是完備的，所以是希爾伯特空間。歐幾里德空間 是 希爾伯特空間的一個重要特例，一個抽象的希爾伯特空間中的元素往往被稱為向量。在實際應用中，它可能代表了一列復數或是一個函數。

---

核函數的再生性
對于任意的$f\in \mathcal{H}$，都有：
$$f(x)=<f(.),k(.,x)>$$

k(.,.)被稱為希爾伯特空間$\mathcal{H}$的再生核。
由核的再生性還可以推到出：
$$k(x,x^{\prime })=<k(x,.),k(.,x^{\prime })>$$

---

再生核希爾伯特空間： 由具有再生性的核 張成的希爾伯特空間
定義：對于一個緊致的$\mathcal{X}\in {\mathbb{R}}^d$；和希爾伯特空間$\mathcal{H}$，其中元素為$f:\mathcal{X}\to \mathbb{R}$，如果存在$k:\mathcal{X}\to \mathbb{R}$，滿足如下條件，就叫$\mathcal{H}$為再生核希爾伯特空間。
1.$k$有再生性：$f(x)=<f(.),k(.,x)>$
2.$k$張成$\mathcal{H}$：H=span{k(.,x):x∈X}￣\mathcal{H}=\overline{span\{k(.,x):x\in \mathcal{X}\}}H=span{k(.,x):x∈X}?

所以說具有再生性的核都可以張成自己的一個再生核希爾伯特空間。

參考資料：
[1]https://blog.csdn.net/hggjgff/article/details/83828394
[2]再生核希爾伯特空間：https://wenku.baidu.com/view/09df5b7a11a6f524ccbff121dd36a32d7375c7c6.html
[3]希爾伯特空間，數學空間的神秘之地 ：http://www.sohu.com/a/315344647_348129介紹了一個大概，從定義出發去驗證希爾伯特空間

---