機(jī)器學(xué)習(xí)基礎(chǔ)

預(yù)備知識(shí)

令 $\mathcal{I}$ 表示輸入數(shù)據(jù) $x$ 的數(shù)據(jù)空間, 被稱為輸入空間 (input space). $\phi$ 是一個(gè)映射, 令 $\mathcal{F} = \mathcal{I}^{**}$ 表示特征空間 (feature space).

數(shù)據(jù)實(shí)例 $x$ 可以任意對(duì)象, 如文本, 序列, 圖像, 字符串等;
對(duì)于給定的數(shù)據(jù)實(shí)例 $x$ , $\phi(x)$ 是一個(gè)向量, 被稱為特征向量.

內(nèi)積運(yùn)算 $K: \mathcal{I \times I} → \mathbb{R}$ 定義為 $\mathcal{I}$ 上的核函數(shù) 為 , 即
$? x_i, x_j \in \mathcal{I}, \; K(x_i,x_j) = ?\phi(x_i),\phi(x_j)?$

令 $D= \{x_i\}_{i=1}^n \subset \mathcal{I}$ 為輸入空間中包含 $n$ 個(gè)對(duì)象的數(shù)據(jù)集, 則將 $D$ 中的點(diǎn)對(duì)間的核函數(shù) (亦稱為相似度函數(shù), 或核) 表示為一個(gè) $n \times n$ 的核矩陣, 定義為
$\mathbf{K} = \begin{pmatrix} K(x_1,x_1) & K(x_1,x_2) & \cdots & K(x_1,x_n) \\ K(x_2,x_1) & K(x_2,x_2) & \cdots & K(x_2,x_n) \\ \vdots & \vdots & \ddots & \vdots\\ K(x_n,x_1) & K(x_n,x_2) & \cdots & K(x_n,x_n) \\ \end{pmatrix}$

核方法避免了顯式地將輸入空間中的每個(gè)點(diǎn) $x$ 變換到特征空間中的映射點(diǎn) $\phi(x)$ , 而是直接通過核矩陣來獲取. 這樣，所有的相關(guān)分析均可轉(zhuǎn)移到對(duì)核矩陣的研究上來. 當(dāng)然, 核矩陣也可以看作對(duì)應(yīng) $n$ 個(gè)輸入點(diǎn)的完全圖的帶權(quán)鄰接矩陣.

對(duì)于輸入空間中的任一 $x \in \mathcal{I}$ , 都被映射到如下函數(shù) (被稱為再生核映射):
$\phi(x) = K(x,\cdot)$
其中 $\cdot$ 代表 $\mathcal{I}$ 中任一參數(shù). 這意味著輸入空間中的每一個(gè)對(duì)象 $x$ 都映射到一個(gè)特征點(diǎn) $\phi(x)$ , 該特征點(diǎn)事實(shí)上是一個(gè)函數(shù) $K(x,\cdot)$ , 代表了該點(diǎn)與輸入空間 $\mathcal{I}$ 中其他點(diǎn)的相似度.

令
$\begin{aligned} \mathcal{F} &= \operatorname{span} \{K(x,?): x \in \mathcal{I}\}\\ &= \{ \mathbf{f} = f(\cdot) = \displaystyle\sum_{i=1}^m α_iK(x_i,?):m \in \mathbb{N}, α_i \in ?, \{x_1,x_2,\cdots,x_m \} ? \mathcal{I} \} \end{aligned}$
代表能夠由特征點(diǎn)的任意子集的線性組合得到的所有函數(shù)點(diǎn)或點(diǎn)的集合.

對(duì)于 $\mathbf{f,g} \in \mathcal{F}$ 為特征空間中任意兩點(diǎn):
$\mathbf{f} = \displaystyle\sum_{i=1}^{m_a} α_iK(x_i, ?), \mathbf{g} = \displaystyle\sum_{j=1}^{m_b} β_iK(x_j, ?)$
定義這兩個(gè)點(diǎn)的內(nèi)積為
$?\mathbf{f,g}? = \displaystyle\sum_{i=1}^{m_a}\sum_{j=1}^{m_b}α_iβ_jK(x_i,x_j)$

易證 $\mathcal{F}$ 是希爾伯特空間, $\mathcal{F}$ 具有再生性質(zhì) (reproducing property), 即可以通過取 $\mathbf{f}$ 和 $\phi(x)$ 的內(nèi)積來計(jì)算一個(gè)函數(shù) $f(?)$ 在一個(gè)點(diǎn) $x\in \mathcal{I}$ 上的值:
$?f(?),\phi(x)? = \displaystyle\sum_{j=1}^{m_a} α_i K(x_i,x) = f(x)$
由此, $\mathcal{F}$ 也被稱為再生希爾伯特空間.

再生核映射 $\phi$ 將輸入空間映射到一個(gè)可能是無限維的特征空間中, 然而, 給定一個(gè)數(shù)據(jù)集 $D = \{x_i\}_{i=1}^n$ , 可以只計(jì)算 $D$ 中的點(diǎn)核, 從而得到一個(gè)有限維的映射, 即定義經(jīng)驗(yàn)核映射 $\phi$ 如下:
$\phi(x) = \mathbf{K}^{-\frac{1}{2}}[K(x_1,x); K(x_2,x); \cdots; K(x_n,x)] \in \mathbb{R}^n$

故而
$\phi(x_i)^T\phi(x_i) = \mathbf{K}_i^T\mathbf{K}^{-1}\mathbf{K}_j$
其中 $\mathbf{K}_i$ 代表核矩陣 $\mathbf{K}$ 的第 $i$ 列.

設(shè) $α = [α_1;α_2;\cdots;α_b]$ 為參數(shù)向量, 基函數(shù)向量為 $\phi(x) = [\phi_1(x);\phi_2(x);\cdots;\phi_b(x)]$

在統(tǒng)計(jì)學(xué)中, 通常把基于參數(shù)的線性模型稱為參數(shù)模型, 把核模型稱為非參數(shù)模型.
與參數(shù)相關(guān)的非線性模型, 稱為非線性模型 (如層級(jí)模型).

線性模型:

$f_{α}(x) = \displaystyle\sum_{j=1}^b α_j \,\phi_j(x) = α^T\phi(x)$

層級(jí)模型:

$f_{α}(x) = \displaystyle\sum_{j=1}^b α_j \,\phi(x;\beta_j) = α^T\phi(x;\beta)$

其中, $\phi(x;\beta_j)$ 是含有參數(shù) $\beta = [\beta_1;\beta_2; \cdots;\beta_b]$ 的基函數(shù).

若基函數(shù) $\phi_i(x) = \phi(x,x_i)$ 內(nèi)積運(yùn)算, 則可將線性模型轉(zhuǎn)換為核模型;把 $\phi(x;\beta_j)$ 替換為核函數(shù), 則是核模型; 把 $\beta$ 當(dāng)作超參數(shù), 則是線性模型.

最小二乘學(xué)習(xí)法 (Least Squares)

模型假設(shè): $D ? \mathbb{R}^d$ , 定義損失函數(shù)為
$J_{LS}(\alpha) = \frac{1}{2} \displaystyle\sum_{i=1}^n (f_{\alpha}(x_i) - y_i)^2$

學(xué)習(xí)目標(biāo):
$\hat{\alpha}_{LS} = \underset{\alpha}{\arg\min} \; J_{LS}$

如果使用線性模型的話, $J_{LS}$ 可以轉(zhuǎn)換為
$J_{LS}(\alpha) = \frac{1}{2} ||\Phi\alpha - y||^2$

這里 $y=[y_1;y_2;\cdots;y_n]$ , $\Phi$ 被稱為設(shè)計(jì)矩陣:
$\Phi = \begin{pmatrix} \phi_1(x_1) & \cdots & \phi_b(x_1)\\ \vdots & \ddots & \vdots\\ \phi_1(x_n) & \cdots & \phi_b(x_n) \end{pmatrix}$

由 $?_{\alpha} J_{LS} = \Phi^T\Phi\alpha - \Phi^T y = 0$ , 便得出最小二乘解
$\Phi^T\Phi\alpha = \Phi^T y$
亦即
$\hat{α}_{LS} = \Phi^{\dagger}y$

其中 $\Phi^{\dagger}$ 表示 $\Phi$ 的偽逆, 若 $\Phi^T\Phi$ 可逆時(shí), 有 $\Phi^{\dagger} = (\Phi^T\Phi)^{-1} \Phi^T$ .

帶有約束條件的最小二乘學(xué)習(xí)法

可微分的凸函數(shù) $f: \mathbb{R}^d → \mathbb{R}$ 和 $g: \mathbb{R}^d → \mathbb{R}^p$ 的約束條件的最小化問題

$\begin{cases} \underset{t}{\min} &f(t)\\ \operatorname{s.t.}& g(t) \preceq 0 \end{cases}$
的拉格朗日對(duì)偶問題, 可以使用拉格朗日乘子 $λ = (λ_1,\cdots,λ_p)^T$ 和拉格朗日函數(shù)
$L(t,λ) = f(t) + λ^Tg(t)$
采用以下方式進(jìn)行定義:
$\begin{cases} \displaystyle\max_{λ} \inf_{t}& L(t,λ)\\ \operatorname{s.t.}& λ \succeq 0 \end{cases}$
拉格朗日對(duì)偶問題的 $t$ 的解, 與原問題的解是一致的.

下面探討線性模型:
$f_{\theta}(x) = θ^T\phi(x)$
的帶約束的最小二乘法.

部分空間約束

約束條件
$P\theta = \theta$

這里, $P$ 滿足 $P^2=P, P^T=P\in ?^{b×b}$ , 表示 $P$ 的值域 $\mathcal{R}(P)$ 的正交投影矩陣. 約束條件 $P\theta = \theta$ 使得參數(shù) $\theta$ 不會(huì)偏移值域 $\mathcal{R}(P)$ 的范圍外.

該問題的最小二乘解為
$\hat{\theta} = (\Phi P)^{\dagger}y$

$l_2$ 約束

約束條件
$||\theta||^2 \leq R$
是以參數(shù)空間的圓點(diǎn)為圓心, 在一定半徑范圍的超球內(nèi)進(jìn)行求解的. 利用其拉格朗日對(duì)偶問題為
$\begin{cases} \displaystyle\max_{λ} \min_{t}& J_{LS}(\theta) + \frac{λ}{2}(||\theta||^2 - R) \\ \operatorname{s.t.}& λ \succeq 0 \end{cases}$
該問題的最小二乘解為
$\hat{\theta} = (\Phi^T\Phi + λ I)^{-1}\Phi^Ty$

矩陣 $\Phi^T\Phi + λ I$ 提高了其正則性, 進(jìn)而可以更穩(wěn)定地進(jìn)行逆矩陣的求解. 因此, $l_2$ 約束的最小二乘法也稱為 $l_2$ 正則化的最小二乘法或稱為嶺回歸.

將約束條件改為
$\theta^TG\theta \leq R$
稱為一般 $l_2$ 約束的最小二乘法. 當(dāng)矩陣 $G$ 為正定矩陣時(shí), $\theta^TG\theta \leq R$ 可以把數(shù)據(jù)限制在橢球內(nèi).
該問題的最小二乘解為
$\hat{\theta} = (\Phi^T\Phi + λ G)^{-1}\Phi^Ty$

稀疏學(xué)習(xí)

模型假設(shè):

模型假設(shè): $D ? \mathbb{R}^d$ , 定義損失函數(shù)為
$J_{LS}(\theta) = \frac{1}{2} ||\Phi\theta - y||^2$

學(xué)習(xí)目標(biāo):
$\hat{\theta}_{LS} = \underset{\alpha}{\arg\min} \; J_{LS}$
約束條件為
$||\theta||_1 \leq R$

對(duì)于 $l_1$ 范數(shù)的處理, $c_j > 0$
$|\theta_j| \leq \frac{\theta_j^2}{2c_j} + \frac{c_j}{2}$
即使用可微分的二次函數(shù)來控制 $l_1$ 范數(shù)
原問題可化為
$\hat{\theta} = \underset{\theta}{\arg\min} \tilde{J}(\theta)$
其中
$\tilde{J}(\theta) = J_{LS}(\theta) + \frac{λ}{2} \theta^T \circledS^{\dagger} \theta + C$

$\circledS$ 是對(duì)角元為 $\tilde{\theta_1}, \cdots, \tilde{\theta_b}$ 的對(duì)角矩陣, $C = \sum_{j=1}^b \frac{\tilde{\theta_j}}{2}$ 是不依賴于 $\theta$ 的常數(shù).

對(duì)于有參數(shù)的線性模型 $f_{\theta} = \theta^T\phi(x)$
該問題的最小二乘解為
$\hat{\theta} = (\Phi^T\Phi + λ \circledS^{-1})^{-1}\Phi^Ty$

使用隨機(jī)梯度下降法求解

對(duì)于有參數(shù)的線性模型 $f_{\theta} = \theta^T\phi(x)$ , 使用隨機(jī)選擇的樣本 $(x,y)$ 按下式對(duì)其參數(shù)進(jìn)行更新:
$\theta ← \theta - ε \phi(x)(f_{\theta}(x)-y)$
為了得到隨機(jī)梯度下降法的稀疏解, 建議在多次進(jìn)行梯度下降的過程中, 對(duì)各個(gè)參數(shù)值 $\theta_j$ 進(jìn)行如下的值域處理
$? j =1, \cdots, b,\;\;\theta ←\begin{cases} \max(0,\theta_j - λε) & (\theta_j > 0)\\ \max(0,\theta_j + λε) & (\theta_j \leq 0) \end{cases}$

$l_p$ 約束的最小二乘法

$?p \geq 0$ , 約束條件是
$||\theta||_p = (\displaystyle\sum_{j=1}^b |\theta_j|^p)^{\frac{1}{p}} \leq R$

$p=∞$ , $||\theta||_{∞} = \max_j{|\theta_j|}$
$p=0$ , 有

$||\theta||_0 = \displaystyle\sum_{j=1}^b δ(\theta_j \neq 0)$

其中
$δ(\theta_j \neq 0) = \begin{cases} 1 & (\theta_j \neq 0)\\ 0 &(\theta_j = 0) \end{cases}$
也就是說, $l_0$ 范數(shù)表示的是非零的向量的元素個(gè)數(shù).

詳細(xì)見彈性網(wǎng)回歸學(xué)習(xí)法.

魯棒學(xué)習(xí)

在統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)領(lǐng)域, 對(duì)異常值也能保持穩(wěn)定定鸟、可靠的性質(zhì), 稱為魯棒性.

當(dāng)訓(xùn)練樣本中混入了異常值時(shí)往往希望采用先除去這些異常值再進(jìn)行學(xué)習(xí)的方法 (異常檢驗(yàn)), 或者采用保留異常值, 但結(jié)果不易受異常值影響的方法 (魯棒學(xué)習(xí)方法).

$l_1$ 損失最小化學(xué)習(xí)

最小二乘學(xué)習(xí)中, 對(duì)訓(xùn)練樣本的合理性, 一般使用 $l_2$ 損失 $J_{LS}(\theta)$ 來測(cè)定.
$J_{LS}(\theta) = \frac{1}{2} \displaystyle\sum_{i=1}^n r_i^2$
這里 $r_i = f_{\theta}(x_i) - y_i$ 為殘差. 但是 $l_2$ 損失對(duì)異常值很敏感, 故而可以使用 $l_1$ 損失對(duì)殘差的增幅加以抑制
$J_{LA} = \displaystyle\sum_{j=1}^n |r_j|$
這里 $LA$ 是 Least Absolute 的縮寫.

Huber 損失最小化學(xué)習(xí)

Huber 損失
$\rho_{\operatorname{Huber}}(r) = \begin{cases} \frac{r^2}{2} & (|r| \leq \eta)\\ \eta |r| - \frac{\eta^2}{2} & (|r| > \eta) \end{cases}$

如果殘差的絕對(duì)值 |r| 小于閾值 $\eta$ 的話 (即正常值), 上式就變成了 $l_2$ 損失;
如果殘差的絕對(duì)值 |r| 大于閾值 $\eta$ 的話 (即異常值), 上式就變成了 $l_1$ 損失, 但是, 為了使與 $l_2$ 平滑地連接, 在 $l_1$ 損失中減去了常數(shù) $\frac{\eta^2}{2}$

這樣的學(xué)習(xí)方法就是 Huber 損失最小化學(xué)習(xí).

$\underset{\theta}{\min} J(\theta) = \displaystyle\sum_{i=1}^n \rho_{\operatorname{Huber}}(r_i)$

圖片發(fā)自簡書App

最后編輯于：2018.08.24 23:35:14

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

人面猴
序言：七十年代末闽巩，一起剝皮案震驚了整個(gè)濱河市俯画，隨后出現(xiàn)的幾起案子涂滴，更是在濱河造成了極大的恐慌展融，老刑警劉巖正驻，帶你破解...
沈念sama閱讀 219,039評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件咒精，死亡現(xiàn)場(chǎng)離奇詭異密末，居然都是意外死亡握爷，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,426評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門严里，熙熙樓的掌柜王于貴愁眉苦臉地迎上來新啼，“玉大人，你說我怎么就攤上這事刹碾≡镒玻” “怎么了？”我有些...
開封第一講書人閱讀 165,417評(píng)論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長物舒。經(jīng)常有香客問我色洞，道長，這世上最難降的妖魔是什么冠胯？我笑而不...
開封第一講書人閱讀 58,868評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任火诸，我火速辦了婚禮，結(jié)果婚禮上荠察，老公的妹妹穿的比我還像新娘置蜀。我一直安慰自己，他們只是感情好悉盆，可當(dāng)我...
茶點(diǎn)故事閱讀 67,892評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布盯荤。她就那樣靜靜地躺著，像睡著了一般舀瓢。火紅的嫁衣襯著肌膚如雪廷雅。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,692評(píng)論 1贊 305
城市分裂傳說
那天京髓，我揣著相機(jī)與錄音航缀，去河邊找鬼。笑死堰怨，一個(gè)胖子當(dāng)著我的面吹牛芥玉，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播备图，決...
沈念sama閱讀 40,416評(píng)論 3贊 419
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼灿巧，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了揽涮？” 一聲冷哼從身側(cè)響起抠藕，我...
開封第一講書人閱讀 39,326評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎蒋困，沒想到半個(gè)月后盾似，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,782評(píng)論 1贊 316
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡雪标，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,957評(píng)論 3贊 337
?白月光啟示錄
正文我和宋清朗相戀三年零院，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片村刨。...
茶點(diǎn)故事閱讀 40,102評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡告抄，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出嵌牺，到底是詐尸還是另有隱情打洼，我是刑警寧澤龄糊，帶...
沈念sama閱讀 35,790評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站拟蜻，受9級(jí)特大地震影響绎签，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜酝锅，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,442評(píng)論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一诡必、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧搔扁，春花似錦爸舒、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,996評(píng)論 0贊 22
一樁弒父案扭勉，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至苛聘，卻和暖如春涂炎，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背设哗。一陣腳步聲響...
開封第一講書人閱讀 33,113評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工唱捣，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人网梢。一個(gè)月前我還...
沈念sama閱讀 48,332評(píng)論 3贊 373
代替公主和親
正文我出身青樓震缭，卻偏偏與公主長得像，于是被迫代替她去往敵國和親战虏。傳聞我的和親對(duì)象是個(gè)殘疾皇子拣宰，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,044評(píng)論 2贊 355