(四) 再生核(Reproducing Kernels) PART 1

Author: Pan

Date:????2020/7/21

"A complete pattern-classification problem cast in a hight-dimension space nonlinearly is more likely to be linearly separable than in a low-dimension space."? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????????????????????????????--Cover's Theorem

1.核的定義與性質(zhì)挟伙，從異或問題談起咳焚。

在解釋上面這段話之前入问，我們需要先討論一個(gè)二維的異或問題双仍。

Fig.1 異或問題

????在Fig.1 中，有兩類的點(diǎn)，第一類是X形點(diǎn)，還有一類是圓形的點(diǎn)。我們要做的事情是用一條直線將圖中的已知點(diǎn)分開(注意乓搬，只能用一條直線，將圖中平面切成兩半代虾，每一半的空間里只有一種類別,要么X,要么O)进肯。想象自己是象棋棋盤上的車,想要憑借一己之力將它們劃分個(gè)“楚河漢界”....這貌似是在開我玩笑，圖中這些有顏色的線沒有一條完成它們的使命棉磨，其實(shí)任何一條這個(gè)平面內(nèi)的直線都做不到江掩。

? ? 那么怎么辦呢? 炮帶著車從棋盤上飛了起來，那一刻乘瓤，車淚流滿面环形，他看見了新世界Fig.2。也就是一開始的那一段話衙傀，高維是比低維更容易線性可分的抬吟。要是所有問題都能這樣映射到高維就好了。

Fig.2 三維上看原來的異或問題

????這想法好到讓人感動(dòng)到想哭统抬，好到不真實(shí)火本，好到令我困惑第三個(gè)維度是怎么出現(xiàn)在我的生命中的。聪建。钙畔。

我們并不懂這樣一個(gè)從低維到高維的映射 $\phi$ 是如何發(fā)生的：

? ?????????????????????????? $Input:\vec{x}\in R^{p}\rightarrow \vec{\phi}(\vec{x})\in R^{r}；p<r$

當(dāng)然金麸，我們可以選擇找 $\phi$ ,像神經(jīng)網(wǎng)絡(luò)一樣去找 $\phi$ ,即便假設(shè)空間大到讓模型哭泣擎析，經(jīng)常需要解決過擬合的問題，但神經(jīng)網(wǎng)絡(luò)本身也是個(gè)神跡钱骂。令人遺憾的是,今天我是個(gè)懶人,我能否在不通過這個(gè) $\phi$ 的情況下叔锐，顯式的在低維里完成隱式的高維里的線性分類過程挪鹏？

? ? 首先见秽，我們既然不想知道這個(gè)映射到底是什么，那么我們需要知道什么讨盒，才能讓我們洞見高維分類的過程解取？

? ? 我們知道，在Fig.2中返顺，是那個(gè)(超)平面讓我們將兩類分開禀苦，那么本質(zhì)上是什么左右了我們的分類結(jié)果蔓肯？其實(shí)是超平面與點(diǎn)的內(nèi)積將其映射成一個(gè)數(shù)，那個(gè)數(shù)的符號(hào)決定了類別振乏。

? ??Oh,內(nèi)積蔗包！

? ? 好的，也許我只需要知道內(nèi)積的結(jié)果就夠了慧邮。

? ? 所以定義我們的核來作為我們內(nèi)積的結(jié)果：

? ?? $X\subset R^{p} 是非空集合调限；\\K:X\times X \rightarrow R \\=K(\vec{x_{i}},\vec{x}_{j})$

? ? 這個(gè)核可以看作高維內(nèi)積。

? ? 我們的目的是將特征空間上的點(diǎn)(原來空間中的點(diǎn))映射到再生核希爾伯特空間(reproducing kernel Hilbert space误澳；RKHS)（函數(shù)空間）

定理0： $K：X\times X \to R$ 是個(gè)對(duì)稱正定核耻矮； $F$ 是個(gè)高維空間；則存在唯一的希爾伯特空間 $H$ 忆谓；存在 $\phi \in H$ 使得 $X\to F$ ; $\forall x,y\in X,K(\vec{x},\vec{y})=<\phi(\vec{x}),\phi(\vec{y})>$

? ? 我們知道無窮維希爾伯特空間是有限維歐式空間的拓展裆装，有限維歐式空間是它的一個(gè)特例。

? ? 今天我們手上有個(gè)線性空間(向量空間)倡缠，我們知道基哨免，我們可以線性相加減，可以數(shù)乘昙沦，可以定位到空間里的每個(gè)點(diǎn)铁瞒。

? ? 我們想知道距離這樣的概念怎么辦呢，我們可以在其上定義范數(shù)桅滋，于是我們就有了賦范線性空間空間慧耍。(假如我們?cè)谶@里定義完備性,即空間里的柯西列都是收斂到該空間中的某個(gè)量，見Fig.3丐谋，我們將得到巴納赫空間芍碧。)我們想知道向量之間的角度怎么辦呢，我們可以在其上定義內(nèi)積号俐，于是我們就有了內(nèi)積空間泌豆。我們想在有限維數(shù)的空間中定義完備性，就可以得到有限維歐式空間吏饿。假如我們想在無限維空間中定義完備性踪危，我們就可以得到希爾伯特空間。

Fig.3 柯西列收斂后的量依舊在這個(gè)空間中[1]

? ? 為什么要無窮維呢猪落？那是因?yàn)橹笥锌赡苡成涞綗o窮維贞远，比如高斯核(泰勒展開后無窮維)，所以我們希望能映射到這上面來探索下內(nèi)積笨忌。

2. 核的性質(zhì)

? ? 既然我們想要探索內(nèi)積蓝仲，那么我們就需要定義什么樣的條件下，我們的操作可以叫做內(nèi)積：

? ? 1. 對(duì)稱性：

? ?????????????????????? $<\vec{\phi}(\vec{x}_{i}),\vec{\phi}(\vec{x}_{j})>=$

? ? 2. 線性：?

? ????? $<a\vec{\phi}(\vec{x}_{i})+b\vec{\phi}(\vec{x}_{j}),\vec{\phi}(\vec{x}_{k})>=a+b$

? ? 3. 正定性：

? ?????? $\forall a_{i},a_{j}\in R; \space \sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})\geq0$

直覺上，對(duì)稱性和線性再正常不過袱结，那為什么要滿足一個(gè)正定性亮隙？

那么我們想想這個(gè)東西 $\vec{x}\cdot K\cdot \vec{x}^{T}$ ，他是我們判定一個(gè)矩陣是否正定的條件;假如 $K=E(單位矩陣)$ ; 這個(gè)其實(shí)就是我們平時(shí)的向量點(diǎn)積垢夹。那么溢吻，假如K是個(gè)半正定矩陣，即 $\vec{x}\cdot K\cdot \vec{x}^{T}\geq0$ 果元，這究竟與平時(shí)我們理解的點(diǎn)積有什么淵源呢煤裙？由于K是個(gè)半正定矩陣，我們又都是在實(shí)空間內(nèi)討論的噪漾，所以K一定是個(gè)實(shí)對(duì)稱矩陣硼砰，對(duì)于任意實(shí)對(duì)稱矩陣，我們都能進(jìn)行特征分解欣硼，將矩陣分解成一個(gè)特征向量組成的正交矩陣的轉(zhuǎn)置 $U^{T}$ 题翰，一個(gè)對(duì)角線上全是特征值的對(duì)角矩陣 $\Lambda$ ，以及特征向量組成的正交矩陣 $U$ 诈胜。

即： $K=U^{T}\cdot \Lambda\cdot U$ ,我們將這個(gè)式子代入上面那個(gè)式子豹障，可以得到： $\vec{x}^{T}K\vec{x}=\vec{x}^{T}U^{T}\cdot \Lambda\cdot U\vec{x}=(U\vec{x})^{T}\cdot \Lambda\cdot (U\vec{x})$

我們知道正交變換具有保范性，經(jīng)過正交變換后的向量具有相同的距離焦匈，且兩個(gè)向量經(jīng)過同一個(gè)正交變換后具有相同的角度血公。也就是原向量經(jīng)過正交變換后其實(shí)只是將坐標(biāo)基旋轉(zhuǎn)了一下，而 $\Lambda$ 則是將向量在各個(gè)維度上進(jìn)行特征值倍數(shù)的拉伸缓熟。所以本質(zhì)上是經(jīng)過矩陣變換后的內(nèi)積形式累魔。由于平時(shí)自己和自己做點(diǎn)積都必須大于0，這也可想而知够滑，為什么我們需要正定性垦写。

????其實(shí)我們這里說的正定性并不代表矩陣是正定的，而是對(duì)應(yīng)于正定核的概念彰触，當(dāng)矩陣是半正定時(shí)梯投，對(duì)應(yīng)的K核是正定核。

? ? 由此况毅，我們的核具有了對(duì)稱性分蓖，線性，以及正定性尔许。

3. 核與距離度量

既然我們引出了核正定的概念么鹤，我們繼續(xù)定義一個(gè)條件正定性，這個(gè)條件正定性母债，是之后一些證明的基礎(chǔ)午磁。

我們定義核的條件正定性： $\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})\geq0;\vec{a}=[a_{1},a_{2},...a_{i}...a_{j},...,a_{n}],\sum_{i=1}^{n}a_{i}=0$

定義核的條件正定性是為了引出一個(gè)定理：

定理1：如果K是條件正定核，-K是負(fù)定的毡们。

為什么要關(guān)心負(fù)定這樣的性質(zhì)呢迅皇？

實(shí)際上這與我們的距離度量有關(guān)，令 $\sum_{i=1}^{n}a_{i}=0$ 衙熔； $\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}||\phi(\vec{x_{i}})-\phi(\vec{x_{j}})||^{2}_{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}(\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{i}})-2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})+\phi(\vec{x_{j}})^{T}\cdot\phi(\vec{x_{j}}))\\=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{i}})-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})+\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}\phi(\vec{x_{j}})^{T}\cdot\phi(\vec{x_{j}}))\\=\sum_{j=1}^{n}a_{j}\sum_{i=1}^{n}a_{i}\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{i}})-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})+\sum_{i=1}^{n}a_{i}\sum_{j=1}^{n}a_{j}\phi(\vec{x_{j}})^{T}\cdot\phi(\vec{x_{j}}))\\=-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})=-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\ K(\vec{x}_{i},\vec{x}_{j})=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\ [-K(\vec{x}_{i},\vec{x}_{j})]$

從結(jié)果上來說登颓，當(dāng)K條件正定時(shí)，-K是負(fù)定的红氯，那么我們的距離度量的矩陣是半負(fù)定的(2是常數(shù)不影響正負(fù)判定框咙，距離的核是負(fù)定核)。這也說明痢甘，內(nèi)積是可以誘導(dǎo)出距離度量的喇嘱。

上面的只是一個(gè)引導(dǎo)性的例子，那么我們?nèi)绾卧诙攘亢伺c再生核之間建立關(guān)系呢塞栅？

定理2：令 $X$ 是非空集合, $\vec{x_{0}}\in X$ 且令 $D :X\times X\rightarrow R$ 是個(gè)對(duì)稱核者铜。

$K(\vec{x_{i}},\vec{x_{j}})=D(\vec{x_{i}},\vec{x_{0}})+D(\vec{x_{0}},\vec{x_{j}})-D(\vec{x_{i}},\vec{x_{j}})-D(\vec{x_{0}},\vec{x_{0}})$

當(dāng)且僅當(dāng) $D$ 為負(fù)定核時(shí)， $K$ 為正定核放椰。

也許你會(huì)很困惑定理2中間那個(gè)式子作烟，但是假如我給出 $\vec{a}\cdot \vec=|\vec{a}||\vec砾医|cos(\theta)=\frac{1}{2}(|\vec{a}|^{2}+|\vec拿撩|^{2}-|\vec{c}|^{2})$

這個(gè)余弦定理的式子是不是很熟悉，而實(shí)際上余弦定理中的是向量如蚜，基于零點(diǎn)做的余弦定理压恒，沒有最后一項(xiàng)，相當(dāng)于零點(diǎn)是這個(gè)余弦定理的見證人错邦，而上面那個(gè)式子中這個(gè)見證人換成了點(diǎn) $x_{0}$ 涎显。

下面我們將對(duì)定理2進(jìn)行證明。

證明：

必要性：即K為正定核時(shí)兴猩，D為負(fù)定核期吓。

當(dāng)K為正定核時(shí)，那么K也一定條件正定倾芝。

所以設(shè) $\sum_{i=1}^{n}a_{i}=0$ 讨勤；

$\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})\\=\sum _{j=1}^{n}a_{j}\sum _{i=1}^{n}a_{i}D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}a_{i}\sum _{j=1}^{n}a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})\\=-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})$

所以 $K(\vec{x}_{i},\vec{x}_{j})=-D(\vec{x}_{i},\vec{x}_{j})$ ；由定理1可知晨另，K條件正定時(shí)潭千，-K負(fù)定。所以D為負(fù)定核

充分性：即D為負(fù)定核時(shí)借尿，K為正定核刨晴。

D為負(fù)定核屉来，則D一定條件負(fù)定。

引入 $a_{0}=-\sum_{i=1}^{n}a_{i}$ ;所以 $\sum_{i=0}^{n}a_{i}=0$ 狈癞；

$\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{j=1}^{n}a_{0}a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}a_{i}a_{0}D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})$

將a0代入： $\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{j=1}^{n}(-\sum_{i=1}^{n}a_{i})a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}a_{i}(-\sum_{i=1}^{n}a_{i})D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})$

合并同類項(xiàng)后可得：

$\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})=-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})$

因?yàn)镈負(fù)定茄靠，即 $\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})\leq0$ ?所以 $\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})\geq 0$

K為正定核。

證畢蝶桶。

這個(gè)定理使得我們能在度量與內(nèi)積之間建立關(guān)系慨绳，為什么距離這么重要呢，那是因?yàn)槿蘸笤賁VM的應(yīng)用中真竖，我們需要得到點(diǎn)到超平面的距離來作為其合頁損失函數(shù)的組成部分脐雪。本質(zhì)上來說這里解釋了用核來描述距離來作為損失函數(shù)可能性。

在PART2中恢共，我們即將開始打造自己的核战秋，包括有限維的多項(xiàng)式核，無窮維的高斯核等等讨韭。

最后編輯于：2020.07.23 17:08:58

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末获询，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子拐袜，更是在濱河造成了極大的恐慌吉嚣，老刑警劉巖，帶你破解...
沈念sama閱讀 206,839評(píng)論 6贊 482
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蹬铺，死亡現(xiàn)場離奇詭異尝哆，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)甜攀，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,543評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門秋泄，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人规阀，你說我怎么就攤上這事恒序。” “怎么了谁撼？”我有些...
開封第一講書人閱讀 153,116評(píng)論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵歧胁，是天一觀的道長。經(jīng)常有香客問我厉碟，道長喊巍，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 55,371評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任箍鼓，我火速辦了婚禮崭参，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘款咖。我一直安慰自己何暮，他們只是感情好奄喂，可當(dāng)我...
茶點(diǎn)故事閱讀 64,384評(píng)論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著海洼，像睡著了一般跨新。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上贰军，一...
開封第一講書人閱讀 49,111評(píng)論 1贊 285
城市分裂傳說
那天玻蝌，我揣著相機(jī)與錄音蟹肘，去河邊找鬼词疼。笑死，一個(gè)胖子當(dāng)著我的面吹牛帘腹，可吹牛的內(nèi)容都是我干的贰盗。我是一名探鬼主播，決...
沈念sama閱讀 38,416評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼阳欲，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼舵盈！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起球化，我...
開封第一講書人閱讀 37,053評(píng)論 0贊 259
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤秽晚，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后筒愚，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體赴蝇，經(jīng)...
沈念sama閱讀 43,558評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,007評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年巢掺，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了句伶。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,117評(píng)論 1贊 334
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡陆淀，死狀恐怖考余，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情轧苫，我是刑警寧澤楚堤，帶...
沈念sama閱讀 33,756評(píng)論 4贊 324
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站含懊，受9級(jí)特大地震影響钾军，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜绢要，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,324評(píng)論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一吏恭、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧重罪，春花似錦樱哼、人聲如沸哀九。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,315評(píng)論 0贊 19
一樁弒父案搅幅，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽阅束。三九已至，卻和暖如春茄唐，著一層夾襖步出監(jiān)牢的瞬間息裸，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,539評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工沪编，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留呼盆，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,578評(píng)論 2贊 355
代替公主和親
正文我出身青樓蚁廓，卻偏偏與公主長得像访圃，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子相嵌，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,877評(píng)論 2贊 345