統(tǒng)計(jì)學(xué)習(xí)方法概論

這篇文章是對(duì)《統(tǒng)計(jì)學(xué)習(xí)方法》10個(gè)監(jiān)督學(xué)習(xí)算法的概論和總結(jié)。分別是感知機(jī)、k近鄰法蚁袭、樸素貝葉斯法删性、決策樹(shù)巴帮、邏輯斯蒂回歸與最大熵模型、支持向量機(jī)起愈、提升方法、EM算法笛辟、隱馬爾可夫模型围来、條件隨機(jī)場(chǎng)。

統(tǒng)計(jì)學(xué)習(xí)方法概論

統(tǒng)計(jì)學(xué)習(xí)是關(guān)于計(jì)算機(jī)基于數(shù)據(jù)構(gòu)建概率統(tǒng)計(jì)模型并運(yùn)用模型對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)與分析的一門(mén)學(xué)科桶错，統(tǒng)計(jì)學(xué)習(xí)也稱為統(tǒng)計(jì)機(jī)器學(xué)習(xí)航唆。

統(tǒng)計(jì)學(xué)習(xí)的方法

假設(shè)數(shù)據(jù)獨(dú)立同分布產(chǎn)生，并且假設(shè)要學(xué)習(xí)的模型屬于某個(gè)函數(shù)的集合院刁，稱為假設(shè)空間糯钙；應(yīng)用某個(gè)評(píng)價(jià)準(zhǔn)則窝革，從假設(shè)空間選取一個(gè)最優(yōu)的模型供鸠，使它對(duì)已知訓(xùn)練數(shù)據(jù)及測(cè)試數(shù)據(jù)在給定的評(píng)價(jià)準(zhǔn)則下有最優(yōu)的預(yù)測(cè)；最優(yōu)模型的選取由算法實(shí)現(xiàn)哨啃。所以統(tǒng)計(jì)學(xué)習(xí)包含三要素：

模型：模型的假設(shè)空間
策略：模型選擇的準(zhǔn)則
算法：模型學(xué)習(xí)的算法

監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)

監(jiān)督學(xué)習(xí)的訓(xùn)練數(shù)據(jù)有標(biāo)簽的標(biāo)注，非監(jiān)督學(xué)習(xí)則沒(méi)有桦卒。

輸入空間快压、特征空間與輸出空間

輸入空間 $\mathcal X$ ：輸入 $x$ 所有可能取值的集合稱為輸入空間
特征空間：所有特征向量存在的空間稱為特征空間
輸出空間 $\mathcal Y$ ：輸出 $y$ 所有可能取值的集合稱為輸出空間

模型的學(xué)習(xí)都是在特征空間上進(jìn)行的外驱。通常情況下惠爽，輸入空間等同于特征空間糟港。但是在有些情況下省有，通過(guò)輸入空間無(wú)法對(duì)數(shù)據(jù)進(jìn)行很好的劃分政敢，此時(shí)需要通過(guò)轉(zhuǎn)換將輸入空間映射到特征空間，在特征空間上進(jìn)行學(xué)習(xí)茎用。例如非線性的支持向量機(jī)或者最大熵模型遣总。

回歸問(wèn)題、分類問(wèn)題與標(biāo)注問(wèn)題

回歸問(wèn)題：輸入變量與輸出變量均為連續(xù)變量的預(yù)測(cè)問(wèn)題稱為回歸問(wèn)題
分類問(wèn)題：輸出變量為有限個(gè)離散變量的預(yù)測(cè)問(wèn)題稱為分類問(wèn)題
標(biāo)注問(wèn)題：輸入變量與輸出變量均為變量序列的預(yù)測(cè)問(wèn)題稱為標(biāo)注問(wèn)題

聯(lián)合概率分布

監(jiān)督學(xué)習(xí)假設(shè)輸入與輸出隨機(jī)變量 $x$ 和 $Y$ 遵循聯(lián)合概率分布 $P(X,Y)$ 轨功。這是監(jiān)督學(xué)習(xí)關(guān)于數(shù)據(jù)的基本假設(shè)旭斥。

統(tǒng)計(jì)學(xué)習(xí)三要素

統(tǒng)計(jì)學(xué)習(xí)的三要素：模型、策略古涧、算法垂券。

模型

模型的假設(shè)空間 $\mathcal F$ 通常有兩類表示方式：決策函數(shù) $f(X)$ 或條件概率 $P(Y|X)$

決策函數(shù)：
$\mathcal F= \{f|Y=f_\theta(X),\theta\in\textbf R^n\}$
條件概率：
$\mathcal F= \{P|P_\theta(Y|X),\theta\in\textbf R^n\}$
其中 $\theta$ 是模型參數(shù)。由決策函數(shù)表示的模型稱為非概率模型羡滑，由條件概率表示的模型稱為概率模型菇爪。

策略

學(xué)習(xí)策略通常是經(jīng)驗(yàn)風(fēng)險(xiǎn) $R_{\mathrm{emp}(f)}$ 最小化或者結(jié)構(gòu)風(fēng)險(xiǎn)最小化。

期望風(fēng)險(xiǎn)（損失） $R_{\mathrm{exp}(f)}$ ：模型關(guān)于聯(lián)合分布的期望損失柒昏，這個(gè)期望一般求不出凳宙，所以轉(zhuǎn)而求經(jīng)驗(yàn)風(fēng)險(xiǎn)（損失）。
$R_{\mathrm{exp}(f)}=E_{P(X,Y)}[L(Y,f(X))]=\int_{\mathcal X\times\mathcal Y}P(X,Y)L(y,f(X))\mathrm dx\mathrm dy$
經(jīng)驗(yàn)風(fēng)險(xiǎn)（損失） $R_{\mathrm{emp}(f)}$ ：模型在樣本上的平均損失职祷。
$R_{\mathrm{exp}(f)}=\frac1N\sum_{i=1}^NL(y_i,f(x_i))$
結(jié)構(gòu)風(fēng)險(xiǎn)（損失）：為了防止過(guò)擬合加上正則化的經(jīng)驗(yàn)損失氏涩。
$R_{\mathrm{srm}(f)}=\frac1N\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$

極大似然估計(jì)是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的一個(gè)例子，例如深度學(xué)習(xí)中定義并最小化損失函數(shù)堪旧。假設(shè)模型是條件概率分布，損失函數(shù)是對(duì)數(shù)損失函數(shù)時(shí)奖亚，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化就等價(jià)于極大似然估計(jì)淳梦。

算法

一般指模型的最優(yōu)化算法，每個(gè)模型都不一樣昔字。

過(guò)擬合和欠擬合

過(guò)擬合：在訓(xùn)練集上誤差小爆袍，但是在測(cè)試集上誤差大。低偏差作郭，高方差陨囊。

欠擬合：在訓(xùn)練集和測(cè)試集上誤差都很大。高偏差夹攒，低方差蜘醋。

正則化

對(duì)模型參數(shù)復(fù)雜度的一個(gè)懲罰。通常使用模型參數(shù) $w$ 的 $L1$ 范數(shù)或者 $L2$ 范數(shù)咏尝。
$L(w)=\frac1N\sum_{i=1}^N(f(x_i;w)-y_i)^2+\frac\lambda2||w||^2$

$L(w)=\frac1N\sum_{i=1}^N(f(x_i;w)-y_i)^2+|w|$

S折交叉驗(yàn)證

把樣本分成 $S$ 份压语，留一份用于測(cè)試啸罢，其余 $S-1$ 份用于測(cè)試。這樣胎食，測(cè)試樣本的選取有 $S$ 個(gè)可能扰才，將 $S$ 次測(cè)試結(jié)果平均，作為最終的測(cè)試結(jié)果厕怜。留一交叉驗(yàn)證是 $S$ 折交叉驗(yàn)證的特例衩匣，每個(gè)樣本為一折。

生成模型與判別模型

判別模型：直接學(xué)習(xí) $f(X)$ 和 $P(Y|X)$ 的參數(shù)的模型粥航。常見(jiàn)的判別模型有： $k$ 近鄰法琅捏、感知機(jī)、決策樹(shù)躁锡、邏輯斯諦回歸午绳、最大熵模型、支持向量機(jī)映之、提升方法和條件隨機(jī)場(chǎng)拦焚。
生成模型：學(xué)習(xí)聯(lián)合分布 $P_\theta(X,Y)$ 的參數(shù)，然后通過(guò) $P(Y|X)=\frac{P(X,Y)}{P(X)}$ 杠输，進(jìn)行預(yù)測(cè)的模型赎败。常見(jiàn)的生成模型有：樸素貝葉斯法和隱馬爾可夫模型。

一蠢甲、感知機(jī)

具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第二章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-感知機(jī)僵刮。

感知機(jī)是二分類的線性分類模型，即通過(guò)一個(gè)超平面將數(shù)據(jù)集分割在兩側(cè)鹦牛，同在一個(gè)側(cè)的為同一個(gè)分類搞糕，一般上側(cè)的為正例，下側(cè)的為負(fù)例曼追。模型直接學(xué)習(xí) $f_\theta(X)$ 的參數(shù)窍仰，給出分類。

感知機(jī)的定義

感知機(jī)的決策函數(shù)為：
$f(x)=\mathrm{sign}(w\cdot x+b)$
其中礼殊， $w$ 和 $b$ 為感知機(jī)模型參數(shù)驹吮， $w\in\textbf R^n$ 叫做權(quán)值或權(quán)值向量， $b\in\textbf R$ 叫做偏置晶伦， $w\cdot x$ 表示 $w$ 和 $x$ 的內(nèi)積碟狞， $\mathrm{sign}$ 是符號(hào)函數(shù)。

感知機(jī)的損失函數(shù)

損失定義為誤分類點(diǎn)到超平面的距離之和：
$L(w,b)=-\frac1{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)$
可以簡(jiǎn)化為：
$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$

感知機(jī)的學(xué)習(xí)算法

通常采用梯度下降算法婚陪，該梯度下降分為原始形式和對(duì)偶形式族沃，對(duì)偶形式通過(guò) $\mathrm{Gram}$ 矩陣加速優(yōu)化。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第二章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-感知機(jī)。

二竭业、k近鄰法

k近鄰法既可以用于分類智润，也可以用于回歸，這里只討論分類的k近鄰法未辆。k近鄰法的思路是：給定一個(gè)輸入窟绷，在訓(xùn)練集中找出 $k$ 個(gè)最相近的實(shí)例，然后分到這 $k$ 個(gè)實(shí)例大多數(shù)歸屬的一個(gè)類咐柜。

k近鄰法包含三個(gè)要素：

k值的選擇
距離度量（如歐氏距離兼蜈、曼哈頓距離等等）
分類決策規(guī)則（如多數(shù)表決）

具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第三章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-k近鄰法。

k近鄰算法

根據(jù)給定的距離度量拙友，在訓(xùn)練集 $T$ 中找出與 $x$ 最鄰近的 $k$ 個(gè)點(diǎn)为狸，涵蓋這 $k$ 個(gè)點(diǎn)的 $x$ 的領(lǐng)域記做 $N_k(x)$ ；
在 $N_k(x)$ 中根據(jù)分類決策規(guī)則（如多數(shù)表決）決定 $x$ 的類別 $y$ ：

$y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_k), \ \ i=1,2,\cdots,N;\ \ j=1,2,\cdots,K$
其中 $I$ 是指示函數(shù)遗契，當(dāng) $y_i=c_j$ 時(shí)為1辐棒，否則為0。

k近鄰法的三個(gè)要素

k值的選擇牍蜂、距離度量（如歐氏距離漾根、曼哈頓距離等等）、分類決策規(guī)則（如多數(shù)表決）鲫竞。

k值的選擇

k值的選擇會(huì)對(duì)k近鄰法的結(jié)果產(chǎn)生重大影響辐怕。一般k越小代表模型變復(fù)雜，容易出現(xiàn)過(guò)擬合（低偏差从绘，高方差）寄疏，尤其是當(dāng)近鄰點(diǎn)是噪聲點(diǎn)時(shí)，預(yù)測(cè)就會(huì)出錯(cuò)僵井。k越大陕截，模型越簡(jiǎn)單。當(dāng)k等于樣本數(shù) $N$ 時(shí)批什，模型最簡(jiǎn)單农曲，但是忽略了樣本中大量的有用信息。在應(yīng)用中渊季，k值一般取一個(gè)較小的數(shù)值朋蔫，然后采用交叉驗(yàn)證法來(lái)選取最優(yōu)的k值罚渐。

距離度量

距離可以選擇如下度量方式：

$L_p$ 距離：
$L_p(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\bigg)^{\frac1p}$
歐氏距離（ $L_2$ 距離）：
$L_2(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2\bigg)^{\frac12}$
曼哈頓距離（ $L_1$ 距離）：
$L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|$

分類決策規(guī)則

通常使用多數(shù)表決規(guī)則却汉，即有輸入實(shí)例的 $k$ 個(gè)鄰近的訓(xùn)練實(shí)例中的多數(shù)類決定輸入實(shí)例的類。多數(shù)表決相當(dāng)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化荷并。

kd樹(shù)

k近鄰法需要計(jì)算輸入實(shí)例和訓(xùn)練集中所有實(shí)例的距離合砂。當(dāng)訓(xùn)練集很大時(shí)，如果采用線性掃描的方式源织，是十分費(fèi)時(shí)的翩伪。為了提高效率微猖，對(duì)訓(xùn)練樣本可以采用樹(shù)結(jié)構(gòu)存儲(chǔ)，減少計(jì)算距離的次數(shù)缘屹。kd樹(shù)是平衡二叉搜索（排序）樹(shù)凛剥，即左子樹(shù)小于右子樹(shù)，且任意子樹(shù)高度差小于等于1轻姿。構(gòu)造和搜索方法犁珠，具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第三章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-k近鄰法。

三互亮、樸素貝葉斯法

樸素貝葉斯法首先學(xué)習(xí)輸入/輸出的聯(lián)合概率分布 $P(Y|X)$ 犁享。然后基于此模型給定的輸入 $x$ ，利用貝葉斯定理求出后驗(yàn)概率最大的輸出 $y$ 平酿，即概率最大的 $P(y|X=x)$ 盈厘。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第四章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-樸素貝葉斯法

條件獨(dú)立性假設(shè)

由于 $P(y|X=x)$ 需要計(jì)算每個(gè)分類的概率：
$P(y=c_k|X=x)=\frac{P(X=x,Y=c_k)}{P(X=x)}$
其中分布可以通過(guò) $P(X=x)$ 在訓(xùn)練樣本中的經(jīng)驗(yàn)分布獲得其參數(shù)茂洒，但是統(tǒng)計(jì)分子
$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)\\$
是不可行的。所以樸素貝葉斯做出如下條件獨(dú)立性假設(shè)：
$\begin{align} P(X=x|Y=c_k)&=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)\\ &=\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k),\ \ k=1,2,\cdots,K \end{align}$
其中 $P(X^{(j)}=x^{(j)}|Y=c_k)$ 可以通過(guò)樣本中統(tǒng)計(jì)的方式學(xué)到經(jīng)驗(yàn)分布凤巨。

樸素貝葉斯算法

在樣本中通過(guò)統(tǒng)計(jì)的方式，計(jì)算先驗(yàn)概率 $P(Y=c_k)$ 和條件概率的 $P(X^{(j)}=a_{jl}|Y=c_k)$ 的經(jīng)驗(yàn)分布医窿。然后給定實(shí)例 $x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T$ 磅甩，計(jì)算：
$P(Y=c_k)=\prod_jP(X^{(j)}=x^{(j)}|Y=c_k),\ \ k=1,2,\cdots,K$
選擇概率最大的分類作為預(yù)測(cè)。原因是根據(jù) $P(y=c_k|X=x)=\frac{P(X=x,Y=c_k)}{P(X=x)}$ 姥卢，給定 $x$ 卷要，其分母都是相同的，所以只需考慮分子独榴。

貝葉斯估計(jì)

在訓(xùn)練數(shù)據(jù)集中僧叉，可能出現(xiàn) $P(X^{(j)}=x^{(j)}|Y=c_k)=0$ 的情況，即樣本中這種情況一次都沒(méi)有出現(xiàn)棺榔，這樣會(huì)造成 $P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)=0$ 瓶堕，使分類產(chǎn)生偏差。解決這個(gè)問(wèn)題的方法是貝葉斯估計(jì)症歇，即在統(tǒng)計(jì) $P(Y=c_k)$ 和 $P(X^{(j)}=x^{(j)}|Y=c_k)$ 時(shí)加入一個(gè)平滑
$P_\lambda(X^{(j)}=x^{(j)}|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}$

$P_\lambda(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda}$

其中 $\lambda\gt0$ 郎笆，可以看出，此時(shí) $P_\lambda(Y=c_k)$ 和 $P_\lambda(X^{(j)}=x^{(j)}|Y=c_k)$ 仍是符合概率分布的忘晤。 $\lambda$ 通常取1宛蚓，這時(shí)稱為拉普拉斯平滑。

四设塔、決策樹(shù)

決策樹(shù)是一種基本的分類與回歸方法凄吏。ID3和C4.5決策樹(shù)可以用于分類，CART（分類與回歸樹(shù)）既可以用于分類，也可以用于回歸痕钢。決策樹(shù)的學(xué)習(xí)通常包括3個(gè)步驟：特征選擇图柏、決策樹(shù)的生成和決策樹(shù)的修剪。這里主要介紹分類決策樹(shù)任连。決策樹(shù)學(xué)習(xí)的是條件概率 $P(Y|X)$ 的參數(shù)蚤吹，具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第五章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-決策樹(shù)。

決策樹(shù)的定義

分類決策樹(shù)模型是一種描述對(duì)實(shí)例進(jìn)行分類的樹(shù)形結(jié)構(gòu)随抠，決策樹(shù)由結(jié)點(diǎn)和有向邊組成距辆。結(jié)點(diǎn)由兩種類型：內(nèi)部結(jié)點(diǎn)和葉結(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩阅喝校~結(jié)點(diǎn)表示一個(gè)類跨算。由決策樹(shù)的根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑構(gòu)建一條規(guī)則：路徑上內(nèi)部結(jié)點(diǎn)的特征對(duì)應(yīng)著規(guī)則的條件，而葉結(jié)點(diǎn)的類對(duì)應(yīng)著規(guī)則的結(jié)論椭懊。決策樹(shù)的路徑對(duì)應(yīng)的規(guī)則互斥且完備诸蚕，每一個(gè)實(shí)例都只被一條路徑所覆蓋。

決策樹(shù)學(xué)習(xí)的三個(gè)步驟

特征選擇氧猬、生成背犯、剪枝。

特征選擇：選擇一個(gè)特征對(duì)當(dāng)前樣本進(jìn)行劃分
生成：生成一棵決策樹(shù)
剪枝：刪減生成決策樹(shù)的一些子樹(shù)盅抚，減少模型復(fù)雜度漠魏，提高模型泛化能力

特征選擇

通常選信息增益（比）最大的特征作為依據(jù)對(duì)當(dāng)前訓(xùn)練集進(jìn)行劃分，生成子樹(shù)妄均。

信息增益：
$g(D,A)=H(D)-H(D|A)$
其中 $H(X)$ 和 $H(Y|X)$ 分別是信息熵和條件熵柱锹， $D$ 是數(shù)據(jù)集， $A$ 是特征集合：
$H(X)=-\sum_{i=1}^nP(X=x_i)\log P(X=x_i)$

$H(Y|X)=\sum_{i=1}^nP(X=x_i)H(Y|X=x_i)$

信息增益比：
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中
$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$
使用信息增益比的原因是：以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征丰包，存在偏向于選擇取值較多的特征的問(wèn)題，使用信息增益比可以對(duì)這一問(wèn)題進(jìn)行校正寄症。

決策樹(shù)的生成算法

通常有ID3生成算法和C4.5生成算法，區(qū)別在于ID3使用信息增益最大選擇劃分的特征，而C4.5使用信息增益比最大。

決策樹(shù)的剪枝

剪枝根據(jù)最小化損失：
$C_\alpha(T)=C(T)+\alpha|T|$
上式中 $C(T)$ 表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差譬胎， $|T|$ 表示模型復(fù)雜度镐侯。參數(shù) $\alpha$ 控制兩者之間的影響，較大的 $\alpha$ 促使選擇簡(jiǎn)單的模型季稳，較小的 $\alpha$ 促使選擇復(fù)雜的模型鲫构， $\alpha=0$ 表示不考慮模型復(fù)雜度。該損失函數(shù)的極小化等價(jià)于正則化的極大似然估計(jì)劣像。

CART算法

CART是分類與回歸樹(shù)的簡(jiǎn)寫(xiě)乡话，即既可以實(shí)現(xiàn)分類，也可以實(shí)現(xiàn)回歸的樹(shù)耳奕。CART是二叉樹(shù)蚊伞，內(nèi)部結(jié)點(diǎn)有兩個(gè)分支，左邊是“是”吮铭，右邊是“否”时迫，對(duì)特征進(jìn)行遞歸的二分。

CART算法由以下兩步組成：

決策樹(shù)生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹(shù)谓晌，生成的決策樹(shù)要盡量大掠拳；
決策樹(shù)剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹(shù)進(jìn)行剪枝并選擇最優(yōu)子樹(shù)，這時(shí)用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)纸肉。

（最小二乘）回歸樹(shù)的生成

使用平方誤差最小尋找切分的特征和切分點(diǎn)溺欧。

分類樹(shù)的生成

使用切分后基尼指數(shù)最小的特征進(jìn)行切分。即：
$\mathrm{Gini}(D,A)=\frac{|D_1|}{|D|}\mathrm{Gini}(D_1)+\frac{|D_2|}{|D|}\mathrm{Gini}(D_2)$
最小柏肪〗愕螅基尼指數(shù) $\mathrm{Gini}(D)$ 表示集合 $D$ 的不確定性，基尼指數(shù)越大烦味，不確定性越高聂使，和熵有相似的性質(zhì)∶恚基尼指數(shù) $\mathrm{Gini}(D,A)$ 表示按特征 $A=a$ 劃分后的不確定性柏靶。

CART剪枝

對(duì)每個(gè)內(nèi)部結(jié)點(diǎn)計(jì)算
$\alpha=g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$
每次，選擇 $g(t)$ 最小的子樹(shù)不斷剪枝得到子樹(shù)序列 $T_0,T_1,\cdots,T_n$ 溃论，然后用驗(yàn)證集驗(yàn)證選擇最優(yōu)屎蜓。

五、邏輯斯諦回歸與最大熵模型

邏輯斯諦回歸（邏輯回歸）模型钥勋，是統(tǒng)計(jì)學(xué)習(xí)中的經(jīng)典分類方法炬转。最大熵是概率模型學(xué)習(xí)的一個(gè)準(zhǔn)則辆苔，推廣到分類問(wèn)題得到最大熵模型。邏輯斯諦回歸和最大熵模型都屬于對(duì)數(shù)線性模型扼劈。邏輯斯諦回歸學(xué)習(xí)的是條件概率 $P(Y|X)$ 的參數(shù)驻啤，具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第六章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-邏輯斯諦回歸與最大熵模型。

邏輯斯諦回歸

二項(xiàng)邏輯斯諦回歸

二項(xiàng)邏輯斯諦回歸模型是如下的條件概率分布：
$P(Y=1|x)=\frac{\exp(w\cdot x+b)}{1+\exp(w\cdot x+b)}$

$P(Y=0|x)=\frac1{1+\exp(w\cdot x+b)}$

這里测僵， $x\in\textbf R^n$ 是輸入， $Y= \{0,1\}$ 是輸出谢翎， $w\in\textbf R^n$ 和 $b\in\textbf R$ 是參數(shù)捍靠， $w$ 稱為權(quán)值向量， $b$ 稱為偏置森逮， $w\cdot x$ 為 $w$ 和 $x$ 的內(nèi)積榨婆。

二項(xiàng)邏輯斯諦回歸的參數(shù)估計(jì)

似然函數(shù)為：
$\prod_{i=1}^N\bigg[[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}\bigg]$
對(duì)數(shù)似然函數(shù)為：
$L(w)=\sum_{i=1}^N\bigg[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))\bigg]$
通過(guò)極大似然估計(jì)求解參數(shù) $w$ 。主要的方法是梯度下降褒侧，具體可以查看統(tǒng)計(jì)機(jī)器學(xué)習(xí)-梯度下降法良风。

多項(xiàng)邏輯斯諦回歸

多分類的多項(xiàng)邏輯斯諦回歸模型，假設(shè)隨機(jī)變量 $Y$ 的取值集合是 $\{1,2,\cdots,K\}$ 闷供，其概率分布為：
$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}(w_k\cdot x)},\ \ k=1,2,\cdots,K-1$

$P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}(w_k\cdot x)}$

類似的烟央，其似然函數(shù)為 $N$ 個(gè)樣本中每個(gè) $x_i$ 預(yù)測(cè)為標(biāo)簽 $y_i$ 概率的乘積。

最大熵模型

最大熵原理是概率模型學(xué)習(xí)的一個(gè)準(zhǔn)則歪脏。最大熵原理認(rèn)為疑俭，學(xué)習(xí)概率模型時(shí)，在所有可能的概率模型中婿失，熵最大的模型是最好的模型钞艇。最大熵原理是選擇模型的思想，將其應(yīng)用到分類模型就叫做最大熵模型豪硅。其中熵：
$H(P)=-\sum_xP(x)\log P(x)$
熵代表了 $X$ 的不確定性哩照。對(duì)未知的變量，給予它每個(gè)取值相同的概率懒浮，此時(shí)不確定最大飘弧，熵也最大，并且這種假設(shè)也是合理的砚著。

最大熵模型的定義

最大熵模型是指在滿足已知的約束下眯牧，熵最大的分類的模型。例如：假設(shè)隨機(jī)變量 $X$ 有5個(gè)取值 $\{A,B,C,D,E\}$ 赖草，并且已知 $P(A)+P(B)=\frac3{10}$ 学少，要求各個(gè)取值的概率。根據(jù)最大熵原理秧骑， $P(A)=P(B)=\frac3{20}$ 版确， $P(C)=P(D)=P(E)=\frac7{30}$ 扣囊。

約束的定義通過(guò)特征函數(shù) $f(x,y)$ 表示：
$f(x,y)= \begin{cases} 1,&x與y滿足某一事實(shí)\\ 0,&否則 \end{cases}$
如果模型能夠獲取訓(xùn)練數(shù)據(jù)中的信息，那么就可以假設(shè)下面兩個(gè)期望（特征函數(shù)關(guān)于聯(lián)合分布 $P(X,Y)$ 和聯(lián)合分布的經(jīng)驗(yàn)分布 $P(X,Y)$ 的期望）相等：
$E_{P(X,Y)}(f(x,y))=E_{\tilde P(X,Y)}(f(x,y))$
于是绒疗，在這些約束下選擇條件熵 $H(P(Y|X))$ 最大的模型：
$\max_{P\in\mathcal C}\ \ H(P)=-\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]$
可以表述為以下最優(yōu)化問(wèn)題：

$\min_{P\in\mathcal C}\ \ -H(P)=\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]$

$\mathrm{s.t.}\ \ E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n$

$\sum_yP(y|x)=1\tag{14}\sum_yP(y|x)=1$

通過(guò)拉格朗日對(duì)偶性侵歇，轉(zhuǎn)為求解對(duì)偶問(wèn)題。得到對(duì)偶問(wèn)題的解后吓蘑，代入拉格朗日函數(shù)惕虑，得到最大熵模型的形式：
$\max_w\Psi(w)=\max_wL(P_w,w)$
其中 $P_w$ ：
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

這個(gè)形式和邏輯斯諦回歸相同，都是對(duì)數(shù)線性模型磨镶，即對(duì)數(shù)幾率 $\log\frac p{1-p}$ 為線性模型溃蔫。這個(gè)問(wèn)題可以通過(guò)IIS算法（迭代極大化似然函數(shù)增量的下界），或者梯度下降法（取反轉(zhuǎn)化為凸函數(shù)極小化問(wèn)題）琳猫、擬牛頓法求解伟叛。

六、支持向量機(jī)

考慮一個(gè)二分類問(wèn)題脐嫂。假設(shè)輸入空間與特征空間為兩個(gè)不同的空間统刮。輸入空間為歐氏空間或離散集合，特征空間為歐式空間或希爾伯特空間账千。線性可分支持向量機(jī)侥蒙、線性支持向量機(jī)假設(shè)這兩個(gè)空間的元素一一對(duì)應(yīng)，并將輸入空間中的輸入映射為特征空間中的特征向量匀奏。非線性支持向量機(jī)利用一個(gè)從輸入空間到特征空間的非線性映射將輸入映射為特征向量（核技巧）辉哥。支持向量機(jī)的學(xué)習(xí)是在特征空間進(jìn)行的。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第七章攒射。

線性可分支持向量機(jī)醋旦、線性支持向量機(jī)處理的樣本在輸入空間上就通過(guò)線性劃分，所以輸入空間和特征空間一一對(duì)應(yīng)会放。非線性支持向量機(jī)處理的樣本在輸入空間上不可以線性劃分饲齐，所以需要通過(guò)映射函數(shù)從輸入空間映射到特征空間使其在特征空間上可以線性劃分，最終轉(zhuǎn)化成線性可分支持向量機(jī)咧最、線性支持向量機(jī)的形式捂人。

線性可分支持向量機(jī)

假設(shè)數(shù)據(jù)線性可分（用一個(gè)超平面可以將正負(fù)例完全正確的劃分在超平面兩側(cè)），學(xué)習(xí)的目的是找到一個(gè)超平面：
$w^*\cdot x+b^*=0$
對(duì)于一個(gè)新的輸入 $x$ 的分類決策函數(shù)為：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
滿足條件的這樣的超平面可能有很多個(gè)矢沿，但是支持向量機(jī)通過(guò)幾何間隔在超平面的選擇上加上了約束滥搭，即最大化幾何間隔，使最后得到的超平面是唯一的捣鲸。具體可以查看統(tǒng)計(jì)機(jī)器學(xué)習(xí)-線性可分支持向量機(jī)與硬間隔最大化瑟匆。

函數(shù)間隔

一般來(lái)說(shuō)，一個(gè)樣本點(diǎn)到超平面的距離代表了支持向量機(jī)對(duì)這個(gè)樣本分類的確信程度栽惶。由于當(dāng)超平面確定愁溜，點(diǎn)到平面的距離公式
$\frac {|w\cdot x+b|}{||w||}$
的分母為一個(gè)常量疾嗅，所以確信程度的大小由分子 $|w\cdot x+b|$ 決定。于是定義樣本點(diǎn) $(x_i,y_i)$ 的函數(shù)間隔：
$\hat \gamma_i=y_i(w\cdot x_i+b)$
對(duì)于 $T$ 中所有樣本的函數(shù)間隔：
$\hat \gamma=\min_{i=1,\cdots N}\hat\gamma_i$
當(dāng)超平面能夠完全分類正確時(shí) $y_i(w\cdot x_i+b)\geq0$ 冕象，所以函數(shù)間隔代表確信程度最小樣本的確信程度代承，最大化函數(shù)間隔就等于最大化支持向量機(jī)對(duì)樣本分類的確信程度。在線性可分支持向量機(jī)中渐扮，這也成為硬間隔最大化论悴。

幾何間隔

由于對(duì)參數(shù) $w$ 和 $b$ 成比例縮放，就可以改變函數(shù)間隔 $\hat\gamma$ 的大小墓律，但這仍然表示同一個(gè)超平面膀估。所以對(duì)提出幾何間隔 $\gamma$ 對(duì) $w$ 規(guī)范化：
$\gamma_i=\frac{\hat \gamma_i}{||w||}$

$\gamma=\frac{\hat \gamma}{||w||}$

$||w||$ 代表 $w$ 的 $L2$ 范數(shù)。

線性可分支持向量機(jī)的最優(yōu)化問(wèn)題

線性可分支持向量機(jī)可以表示為以下最優(yōu)化問(wèn)題只锻，即極大化幾何間隔（提高分類確信程度）：
$\max_{w,b}\gamma$

$\mathrm{s.t.}\ \ y_i(\frac{w}{||w||}\cdot x_i+\frac玖像{||w||})\geq\gamma,\ \ i=1,2,\cdots,N$

轉(zhuǎn)化為以下最優(yōu)化問(wèn)題：
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

通過(guò)拉格朗日對(duì)偶性紫谷，轉(zhuǎn)化為極大極小問(wèn)題：
$\max_\alpha\min_{w,b}L(w,b,a)$
其中：
$L(w,b,a)=\frac12||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i$
為拉格朗日函數(shù)齐饮。求解內(nèi)部極小問(wèn)題的解 $w^*,b^*$ 后，代入得到外部極大化問(wèn)題：
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

線性可分支持向量機(jī)解的形式

$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$

$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$

分離超平面
$w^*\cdot x+b^*=0$
分類決策函數(shù)：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$

間隔邊界

支持向量是使約束條件公式 $1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$ 等號(hào)成立的點(diǎn)笤昨，即
$w\cdot x_i+b=y_i$
對(duì)于正例 $y_i=+1$ 祖驱，支持向量在超平面
$H_1:w\cdot x+b=1$
對(duì)于負(fù)例 $y_i=-1$ ，支持向量在超平面
$H_2:w\cdot x+b=-1$
如圖所示

間隔邊界

落在 $H_1$ 和 $H_2$ 上的實(shí)例點(diǎn)稱為支持向量瞒窒， $H_1$ 和 $H_2$ 之間的距離稱為間隔捺僻， $H_1$ 和 $H_2$ 稱為間隔邊界。在決定超平面時(shí)崇裁，只有支持向量起作用匕坯，所以這種模型叫做支持向量機(jī)。

支持向量

根據(jù)解的公式
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
可以知道對(duì) $w^*$ 的結(jié)果有影響的樣本點(diǎn) $(x_i,y_i)$ 拔稳，其 $\alpha_i^*\neq0$ 葛峻，又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Calpha_i%5E*%5Cgeq0" alt="\alpha_i^*\geq0" mathimg="1">，所以 $\alpha_i^*\gt0$ 巴比，根據(jù) $KKT$ 條件：
$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0$
所以
$1-y_i(w^*\cdot x_i+b^*)=0$
這樣的樣本點(diǎn)落在間隔邊界上
$w^*\cdot x_i+b^*=\pm1$

線性支持向量機(jī)

假設(shè)給定一個(gè)特征空間上的訓(xùn)練數(shù)據(jù)集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
其中术奖， $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y= \{+1,-1\}$ 轻绞， $i=1,2,\cdots,N$ 采记， $x_i$ 為第 $i$ 個(gè)特征向量，也稱為實(shí)例政勃， $y_i$ 為 $x_i$ 的類標(biāo)記唧龄，當(dāng) $y_i=+1$ 時(shí)，稱 $x_i$ 為正例奸远；當(dāng) $y_i=-1$ 時(shí)选侨，稱 $x_i$ 為負(fù)例掖鱼， $(x_i,y_i)$ 稱為樣本點(diǎn)。再假設(shè)訓(xùn)練數(shù)據(jù)集不是線性可分的援制。通常情況是戏挡，訓(xùn)練數(shù)據(jù)中有一些特異點(diǎn)，將這些特異點(diǎn)除去后晨仑，剩下大部分的樣本點(diǎn)組成的集合是線性可分的褐墅。

線性不可分意味著某些樣本點(diǎn) $(x_i,y_i)$ 不能滿足函數(shù)間隔大于等于1的約束條件。為了解決這個(gè)問(wèn)題洪己，可以對(duì)每個(gè)樣本點(diǎn) $(x_i,y_i)$ 引進(jìn)一個(gè)松弛變量 $\xi_i\geq0$ 妥凳，使函數(shù)間隔加上松弛變量大于等于1。這樣答捕，約束條件變?yōu)?br> $1-\xi_i-y_i(w\cdot x_i+b)\leq0$
目標(biāo)函數(shù)由原來(lái)的最小化 $\frac12||w||^2$ 變成最小化
$\frac12||w||^2+C\sum_{i=1}^N\xi_i$
$C$ 是對(duì)誤分類的懲罰逝钥， $C$ 越大，對(duì)誤分類懲罰越大拱镐。相對(duì)于線性可分支持向量機(jī)的硬間隔最大化艘款，這叫做軟間隔最大化。具體可以查看統(tǒng)計(jì)機(jī)器學(xué)習(xí)-線性支持向量機(jī)與軟間隔最大化沃琅。

線性支持向量機(jī)學(xué)習(xí)算法

類似線性可分支持向量機(jī)哗咆，可以使用拉格朗日對(duì)偶性，通過(guò)求解對(duì)偶問(wèn)題的解來(lái)得到原始問(wèn)題的解益眉。

其解的形式：
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$

$b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)$

求得分離超平面
$w^*\cdot x+b^*=0$
分類決策函數(shù)：
$f(x)=\mathrm{sign}(w^*\cdot x)+b^*$

支持向量

由公式
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
得知 $\alpha_i^*\neq0$ 的樣本點(diǎn) $x_i$ 能夠影響支持向量機(jī)的參數(shù)晌柬。而 $0\leq\alpha_i^*\leq C$ ，所以支持向量為 $0\lt\alpha_i^*\leq C$ 的樣本點(diǎn) $x_i$ 郭脂。這些支持向量分布在間隔邊界上年碘、間隔邊界與分離超平面之間或者在分離超平面誤分一側(cè)。若 $\alpha_i^*\lt C$ 展鸡，則 $\xi_i=0$ （由 $KKT$ 條件可以推出屿衅，由于 $\xi^*$ 的結(jié)果不影響分離超平面，所以一般也不去算娱颊，其計(jì)算過(guò)程略）傲诵，支持向量恰好落在間隔邊界上；若 $\alpha_i^*=C$ 箱硕， $0\lt\xi_i\lt1$ 拴竹，則分類正確，支持向量在間隔邊界與分離超平面之間剧罩；若 $\alpha_i^*=C$ 栓拜， $\xi_i=1$ ，則 $x_i$ 在分離超平面上；若 $\alpha_i^*=C$ 幕与， $\xi_i\gt1$ 挑势，則 $x_i$ 在分離超平面誤分一側(cè)。

合頁(yè)損失函數(shù)

線性支持向量機(jī)的學(xué)習(xí)還等價(jià)于最小化以下目標(biāo)函數(shù)：
$\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2$
其中目標(biāo)函數(shù)的第一項(xiàng)是經(jīng)驗(yàn)損失或經(jīng)驗(yàn)風(fēng)險(xiǎn)啦鸣，函數(shù)
$L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+$
稱為合頁(yè)損失函數(shù)潮饱。下標(biāo)"+"表示 $ReLU$ 函數(shù)，由于函數(shù)形狀像一個(gè)合頁(yè)诫给，故名合頁(yè)損失函數(shù)香拉。合頁(yè)損失函數(shù)相比感知機(jī)的0-1損失，不僅要求分類正確中狂，還要求確信度足夠高時(shí)（函數(shù)間隔大于等于1）損失才是0凫碌，所以支持向量機(jī)的學(xué)習(xí)比感知機(jī)有更高的要求。

非線性支持向量機(jī)

非線性支持向量機(jī)在輸入空間上不可分胃榕，通過(guò)映射 $z=\phi(x)$ 將輸入映射到特征空間盛险，在特征空間上類似線性支持向量機(jī)進(jìn)行學(xué)習(xí)。具體可以查看統(tǒng)計(jì)機(jī)器學(xué)習(xí)-非線性支持向量機(jī)勋又。

非線性支持向量機(jī)的解

$\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)$

$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_iK(x_i\cdot x_j)$

其中 $K(x,z)$ 是正定核函數(shù)苦掘。

決策函數(shù)
$f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)+b^*\bigg)$

核函數(shù)（正定核）

上式只需計(jì)算核函數(shù) $K(x,z)$ 而無(wú)需知道具體的映射函數(shù) $\phi(x)$ 。那么如何判斷一個(gè)函數(shù)是否具備這樣的的映射函數(shù) $\phi(x)$ 滿足核函數(shù)的要求呢赐写？我們可以根據(jù)核函數(shù)的充要條件判斷：

設(shè) $K:\mathcal X\times\mathcal X\rightarrow\textbf R$ 是對(duì)稱函數(shù)鸟蜡，則 $K(x,z)$ 為正定核函數(shù)的充要條件是對(duì)任意 $x_i\in\mathcal X$ 膜赃， $i=1,2,\cdots,m$ 挺邀， $K(x,z)$ 對(duì)應(yīng)的 $\mathrm{Gram}$ 矩陣：
$K=[K(X_i,X_j)]_{m\times m}$
是半正定矩陣。所以核函數(shù)也叫正定核函數(shù)跳座。

常用的核函數(shù)

多項(xiàng)式核函數(shù)

$K(x,z)=(x\cdot z+1)^p$

高斯核函數(shù)

$K(x,z)=\exp\bigg(-\frac{||x-z||^2}{2\sigma^2}\bigg)$

字符串核函數(shù)

$k_n(s,t)=\sum_{u\in\Sigma^n}[\phi_n(s)]_u[\phi_n(t)]_u=\sum_{u\in\Sigma^n}\sum_{(i,j):s(i)=t(j)=u}\lambda^{l(i)}\lambda^{l(j)}$

計(jì)算字符串 $s$ 和 $t$ 的相似程度端铛。

序列最小最優(yōu)化算法

通過(guò)對(duì)偶問(wèn)題求解支持向量機(jī)的參數(shù)，都需要計(jì)算最優(yōu)解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 疲眷。通過(guò)解析求解是很困難的禾蚕，而序列最小最優(yōu)化算法（SMO）算法通過(guò)迭代方式，逐步更新 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 的值狂丝，使其滿足 $KKT$ 條件换淆，從而得到最優(yōu)解。同時(shí)優(yōu)化所有參數(shù)是很復(fù)雜的几颜，SMO的思路是每次只選擇兩個(gè)變量進(jìn)行優(yōu)化倍试。選擇的標(biāo)準(zhǔn)是：外層循環(huán)在訓(xùn)練樣本中選取違反 $KKT$ 條件最嚴(yán)重的樣本點(diǎn)，并將其對(duì)應(yīng)的變量作為第1個(gè)變量 $\alpha_1$ 蛋哭，內(nèi)層循環(huán)選擇標(biāo)準(zhǔn)是希望能使 $\alpha_2$ 有足夠大的變化县习。具體可以查看統(tǒng)計(jì)機(jī)器學(xué)習(xí)-序列最小最優(yōu)化算法（SMO）。

七、提升方法

提升方法的思路就是學(xué)習(xí)多個(gè)分類器躁愿，對(duì)多個(gè)分類器進(jìn)行線性組合叛本，提高分類的性能。首先定義強(qiáng)可學(xué)習(xí)和弱可學(xué)習(xí)彤钟。如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法可以學(xué)習(xí)一個(gè)分類来候，并且正確率很高，則稱為強(qiáng)可學(xué)習(xí)逸雹。如果一個(gè)多項(xiàng)式的學(xué)習(xí)算法可以學(xué)習(xí)一個(gè)分類吠勘，并且正確率相比隨機(jī)猜測(cè)要略好，那么稱為弱可學(xué)習(xí)峡眶。事實(shí)上剧防，兩者是等價(jià)的，即一個(gè)問(wèn)題弱可學(xué)習(xí)辫樱，則可以強(qiáng)可學(xué)習(xí)峭拘。提升方法的目標(biāo)就是組合弱分類器，使其稱為一個(gè)強(qiáng)分類器狮暑。大多數(shù)的提升方法都是改變訓(xùn)練數(shù)據(jù)的概率分布（訓(xùn)練數(shù)據(jù)的權(quán)值分布）鸡挠，針對(duì)不同的訓(xùn)練數(shù)據(jù)分布調(diào)用弱學(xué)習(xí)算法學(xué)習(xí)一系列弱分類器。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第八章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-提升方法搬男。

提升方法需要解決兩個(gè)問(wèn)題：

每一輪如何改變訓(xùn)練數(shù)據(jù)的權(quán)值或概率分布
如何將若分類器組合成一個(gè)強(qiáng)分類器

Adaboost算法

對(duì)于上述兩個(gè)問(wèn)題拣展，Adaboost（適應(yīng)性提升方法）的做法是：

訓(xùn)練數(shù)據(jù)被分類錯(cuò)誤，權(quán)值上升缔逛，被分類正確备埃，權(quán)值下降
加權(quán)多數(shù)表決，誤差率越小褐奴，權(quán)值越高

回歸提升樹(shù)

在每一步使用一棵回歸樹(shù) $T(x;\Theta_m)$ 擬合預(yù)測(cè)樣本的殘差（均方損失情況下）按脚。通過(guò) $M$ 步得到回歸提升樹(shù)：
$f_M(x)=\sum_{m=1}^MT(x;\Theta_m)$

梯度提升

在每一步使用一棵回歸樹(shù) $T(x;\Theta_m)$ 擬合預(yù)測(cè)樣本的殘差的近似，即損失函數(shù)的負(fù)梯度：
$-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}$
通過(guò) $M$ 步得到回歸提升樹(shù)敦冬。

八辅搬、EM算法

EM算法用于含有隱變量的概率模型參數(shù)的極大似然估計(jì)。這里首先對(duì)隱變量解釋脖旱，舉下面的例子

（三硬幣模型）假設(shè)有3枚硬幣浪读，分別記做 $A$ 陡舅， $B$ ， $C$ ，這些硬幣正面出現(xiàn)的概率分別是 $\pi$ 吐葵， $p$ 和 $q$ 砾赔。進(jìn)行如下擲硬幣試驗(yàn)：先擲硬幣 $A$ 犹赖，根據(jù)其結(jié)果選出硬幣 $B$ 或硬幣 $C$ 芭碍，正面選硬幣 $B$ 佳恬，反面選硬幣 $C$ ；然后擲選出的硬幣于游，擲硬幣的結(jié)果毁葱，出現(xiàn)正面記做1，出現(xiàn)反面記做0贰剥；獨(dú)立的重復(fù) $n$ 次試驗(yàn)（這里倾剿， $n=10$ ），觀測(cè)結(jié)果如下：
$1,1,0,1,0,0,1,0,1,1$
假設(shè)能觀測(cè)到擲硬幣的結(jié)果蚌成，不能觀測(cè)擲硬幣的過(guò)程前痘，問(wèn)如何估計(jì)三硬幣正面出現(xiàn)的概率，即三硬幣模型的參數(shù) $\pi$ 担忧， $p$ 和 $q$ 芹缔。

其中擲硬幣 $A$ 的結(jié)果是未觀測(cè)的，叫做隱變量瓶盛，記做 $z$ 最欠。將觀測(cè)數(shù)據(jù)表示為 $Y=(Y_1,Y_2,\cdots,Y_n)^T$ ，未觀測(cè)數(shù)據(jù)表示為 $Z=(Z_1,Z_2,\cdots,Z_n)^T$ 惩猫，則觀測(cè)數(shù)據(jù)的似然函數(shù)為
$P(Y|\theta)=\sum_ZP(Y,Z|\theta)=\sum_ZP(Z|\theta)P(Y|Z,\theta)\tag1$
即
$P(Y|\theta)=\prod_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_i}+(1-\pi)q^{y_j}(1-q)^{1-y_j}]\tag2$
對(duì)模型參數(shù) $\theta=(\pi,p,q)$ 進(jìn)行極大似然估計(jì)芝硬，即
$\hat\theta=\arg\max_\theta\log P(Y|\theta)\tag3$
因?yàn)閿S硬幣 $A$ 的結(jié)果未知，所以沒(méi)有這個(gè)問(wèn)題解析解轧房，只能通過(guò)迭代的方式拌阴，逐步增加對(duì)數(shù)似然函數(shù)，找到一個(gè)解奶镶。EM算法解決的就是這樣的一類問(wèn)題迟赃。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第九章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-EM算法（期望極大算法）。

EM算法的推出

EM算法叫做Exception maximization算法实辑，顧名思義捺氢，包含求期望（Exception ）和極大化（maximization）兩個(gè)步驟藻丢。

E步：記 $\theta^{(i)}$ 為第 $i$ 次迭代參數(shù) $\theta$ 的估計(jì)值剪撬，在第 $i+1$ 次迭代的E步，計(jì)算
$\begin{align} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align}$
這里 $P(Z|Y,\theta^{(i)})$ 是在給定觀測(cè)數(shù)據(jù) $Y$ 和當(dāng)前參數(shù)估計(jì) $\theta^{(i)}$ 下隱變量數(shù)據(jù) $Z$ 的條件概率分布悠反；
M步：求使 $Q(\theta,\theta^{(i)})$ 極大化的 $\theta$ 残黑，確定第 $i+1$ 次迭代的參數(shù)的估計(jì)值 $\theta^{(i+1)}$
$\theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})$

Q函數(shù)是 $Y$ 關(guān)于參數(shù) $\theta$ 的對(duì)數(shù)似然函數(shù)的下界：
$L(\theta)=\log P(Y|\theta)=\log\sum_ZP(Y,Z|\theta)=\log\bigg(\sum_ZP(Y|Z,\theta)P(Z|\theta)\bigg)\geq Q(\theta,\theta^{(i)})$
所以，在EM算法中最大化Q函數(shù)斋否，就等同于最大對(duì)數(shù)似然函數(shù)的下界梨水，從而進(jìn)行極大似然估計(jì)。但是這種算法并不能保證找到全局最優(yōu)值茵臭。

九疫诽、隱馬爾可夫模型

隱馬爾可夫模型（HMM）是用于標(biāo)注問(wèn)題的統(tǒng)計(jì)學(xué)習(xí)模型，描述由隱藏的馬爾科夫鏈隨機(jī)生成觀測(cè)序列的過(guò)程，屬于生成模型奇徒。隱馬爾可夫模型在語(yǔ)音識(shí)別雏亚、自然語(yǔ)言處理、生物信息摩钙、模式識(shí)別等領(lǐng)域有著廣泛的應(yīng)用罢低。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第十章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-隱馬爾可夫模型。

隱馬爾可夫模型的定義

隱馬爾可夫模型由初始狀態(tài)概率向量 $\pi$ 胖笛，狀態(tài)轉(zhuǎn)移概率矩陣 $A$ 和觀測(cè)概率矩陣 $B$ 決定网持。 $\pi$ 和 $A$ 決定狀態(tài)序列， $B$ 決定觀測(cè)序列长踊。因此隱馬爾可夫模型 $\lambda$ 可以用三元符號(hào)表示功舀，即
$\lambda=(A,B,\pi)$
隱馬爾可夫模型做了兩個(gè)基本假設(shè)：

齊次馬爾可夫性假設(shè)，即假設(shè)隱藏的馬爾可夫鏈在任意時(shí)刻 $t$ 的狀態(tài)只依賴于其前一時(shí)刻的狀態(tài)身弊，與其他時(shí)刻的狀態(tài)及觀測(cè)無(wú)關(guān)日杈，也與時(shí)刻 $t$ 無(wú)關(guān)。（當(dāng)前狀態(tài)只依賴上個(gè)狀態(tài)佑刷，而與再前面的狀態(tài)無(wú)關(guān)）
$P(i_t|i_1,o_1,\cdots,i_{t-1},o_{t-1})=P(i_t|i_{t-1}),\ \ t=1,2,\cdots,T$
觀測(cè)獨(dú)立性假設(shè)莉擒，即假設(shè)任意時(shí)刻的觀測(cè)只依賴于該時(shí)刻的馬爾可夫鏈的狀態(tài)，與其他觀測(cè)及狀態(tài)無(wú)關(guān)瘫絮。（每個(gè)時(shí)刻的觀測(cè)只依賴于當(dāng)前時(shí)刻的狀態(tài)）

$P(o_t|i_1,o_1,\cdots,i_{t-1},o_{t-1},i_t,i_{t+1},i_{t+1},\cdots,i_T,o_T)=P(o_t|i_t)$

隱馬爾可夫模型的3個(gè)基本問(wèn)題

概率計(jì)算問(wèn)題涨冀。給定模型 $\lambda=(A,B,\pi)$ 和觀測(cè)序列 $O=(o_1,o_2,\cdots,o_T)$ ，計(jì)算在模型 $\lambda$ 下觀測(cè)序列 $O$ 出現(xiàn)的概率 $P(O|\lambda)$ 麦萤。
學(xué)習(xí)問(wèn)題鹿鳖。已知觀測(cè)序列 $O=(o_1,o_2,\cdots,o_T)$ ，估計(jì)模型 $\lambda=(A,B,\pi)$ 參數(shù)壮莹，使得在該模型下觀測(cè)序列概率 $P(O|\lambda)$ 最大翅帜。即用極大似然估計(jì)的方法估計(jì)參數(shù)。
預(yù)測(cè)問(wèn)題命满，也稱為解碼問(wèn)題涝滴。已知模型 $\lambda=(A,B,\pi)$ 和觀測(cè)序列 $O=(o_1,o_2,\cdots,o_T)$ ，求對(duì)給定觀測(cè)序列條件概率 $P(I|O)$ 最大的狀態(tài)序列 $I=(i_1,i_2,\cdots,i_T)$ 胶台。即給定觀測(cè)序列歼疮，求最有可能的對(duì)應(yīng)狀態(tài)序列。

三個(gè)問(wèn)題都有各自的算法诈唬。

概率計(jì)算法

解決的是第一個(gè)問(wèn)題：概率計(jì)算問(wèn)題韩脏。給定模型 $\lambda=(A,B,\pi)$ 和觀測(cè)序列 $O=(o_1,o_2,\cdots,o_T)$ ，計(jì)算在模型 $\lambda$ 下觀測(cè)序列 $O$ 出現(xiàn)的概率 $P(O|\lambda)$ 铸磅。通常的計(jì)算方法有直接計(jì)算法（事實(shí)上不太可行）赡矢、前向-后向算法杭朱。

學(xué)習(xí)算法

解決的是第二個(gè)問(wèn)題：學(xué)習(xí)問(wèn)題。已知觀測(cè)序列 $O=(o_1,o_2,\cdots,o_T)$ 吹散，估計(jì)模型 $\lambda=(A,B,\pi)$ 參數(shù)痕檬，使得在該模型下觀測(cè)序列概率 $P(O|\lambda)$ 最大。即用極大似然估計(jì)的方法估計(jì)參數(shù)送浊。該問(wèn)題分為無(wú)監(jiān)督和監(jiān)督學(xué)習(xí)兩種方式梦谜。在狀態(tài)序列標(biāo)注的情況下，可以使用無(wú)監(jiān)督方式袭景，但是情況通常是不知道狀態(tài)序列唁桩，這時(shí)候就需要通過(guò)無(wú)監(jiān)督學(xué)習(xí)的方式，估計(jì)模型參數(shù)耸棒。無(wú)監(jiān)督學(xué)習(xí)的算法叫做Baum-Welch算法荒澡，是EM算法在隱馬爾可夫模型中的具體應(yīng)用。

預(yù)測(cè)算法

解決的是第二個(gè)問(wèn)題：預(yù)測(cè)問(wèn)題与殃，也稱為解碼問(wèn)題单山。已知模型 $\lambda=(A,B,\pi)$ 和觀測(cè)序列 $O=(o_1,o_2,\cdots,o_T)$ ，求對(duì)給定觀測(cè)序列條件概率 $P(I|O)$ 最大的狀態(tài)序列 $I=(i_1,i_2,\cdots,i_T)$ 幅疼。即給定觀測(cè)序列米奸，求最有可能的對(duì)應(yīng)狀態(tài)序列∷瘢可是使用近似算法和維特比算法悴晰。

近似算法：缺點(diǎn)是沒(méi)有考慮整個(gè)序列，如果存在轉(zhuǎn)移概率 $a_{ij}=0$ 逐工，序列 $q_j,q_i$ 是不可能出現(xiàn)的铡溪，但是依然會(huì)存在這樣的預(yù)測(cè)。
維特比算法：采用動(dòng)態(tài)規(guī)劃思想泪喊，劃分子問(wèn)題棕硫，逐步取最優(yōu)。

十袒啼、條件隨機(jī)場(chǎng)

條件隨機(jī)場(chǎng)是給定一組輸入隨機(jī)變量條件下另一組隨機(jī)變量的條件概率分布模型 $P(Y|X)$ 哈扮，其特點(diǎn)是假設(shè)輸出隨機(jī)變量構(gòu)成馬爾可夫隨機(jī)場(chǎng)。類似隱馬爾可夫模型瘤泪，條件隨機(jī)場(chǎng)也有概率計(jì)算問(wèn)題灶泵，學(xué)習(xí)問(wèn)題和預(yù)測(cè)問(wèn)題。具體可以查看《統(tǒng)計(jì)學(xué)習(xí)方法》第十一章或統(tǒng)計(jì)機(jī)器學(xué)習(xí)-條件隨機(jī)場(chǎng)对途。

條件隨機(jī)場(chǎng)和概率無(wú)向圖

條件隨機(jī)場(chǎng)模型 $P(Y|X)$ 其實(shí)是有輸入變量 $X$ 決定的 $Y$ 的一個(gè)概率無(wú)向圖：

條件隨機(jī)場(chǎng)

沒(méi)有連線的兩個(gè)隨機(jī)變量之間獨(dú)立。條件隨機(jī)場(chǎng)為了簡(jiǎn)化問(wèn)題髓棋，通常使用鏈?zhǔn)降臈l件隨機(jī)場(chǎng)：

線性鏈條件隨機(jī)場(chǎng)

每個(gè)隨機(jī)變量 $Y_i$ 只依賴于有邊相連接的隨機(jī)變量 $Y_{i-1}$ 实檀， $Y_{i+1}$ 惶洲。

線性鏈條件隨機(jī)場(chǎng)的參數(shù)化形式

設(shè) $X=(X_1,X_2,\cdots,X_n)$ ， $Y=(Y_1,Y_2,\cdots,Y_n)$ 均為線性鏈表示的隨機(jī)變量序列膳犹，若在給定隨機(jī)變量序列 $X$ 的條件下恬吕，隨機(jī)變量序列 $Y$ 的條件概率分布 $P(Y|X)$ 構(gòu)成條件隨機(jī)場(chǎng)，即滿足馬爾可夫性
$P(Y_i|X,Y_i,\cdots,Y_{i-1},Y_{i+1},\cdots,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})\\ i=1,2,\cdots,n\ \ (在i=1和n時(shí)只考慮單邊)$
則稱 $P(Y|X)$ 為線性鏈條件隨機(jī)場(chǎng)须床。在標(biāo)注問(wèn)題中铐料， $X$ 表示輸入觀測(cè)序列， $Y$ 表示對(duì)應(yīng)的輸出標(biāo)記序列或狀態(tài)序列豺旬。

線性鏈條件隨機(jī)場(chǎng)的簡(jiǎn)化形式

線性鏈條件隨機(jī)場(chǎng)的參數(shù)形式可以簡(jiǎn)化為
$P(y|x)=\frac1{Z(x)}\exp{\sum_{k=1}^Kw_kf_k(y,x)}$

$Z(x)=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x)$

其中 $f_k(y,x)$ 是特征函數(shù)钠惩。回顧最大熵模型：
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

可以看出兩者有著非常類似的形式族阅，并且線性鏈條件隨機(jī)場(chǎng)也是對(duì)數(shù)線性模型篓跛。

條件隨機(jī)場(chǎng)模型的3個(gè)基本問(wèn)題

概率計(jì)算問(wèn)題、學(xué)習(xí)問(wèn)題坦刀、預(yù)測(cè)問(wèn)題愧沟。

概率計(jì)算問(wèn)題

條件隨機(jī)場(chǎng)的概率計(jì)算問(wèn)題是給定條件隨機(jī)場(chǎng) $P(Y|X)$ ，輸入序列 $x$ 和輸出序列 $y$ 鲤遥，計(jì)算條件概率 $P(Y_i=y_i|x)$ 沐寺， $P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 以及相應(yīng)的數(shù)學(xué)期望的問(wèn)題。類似隱馬爾可夫模型盖奈，使用前向-后向算法芽丹。

條件隨機(jī)場(chǎng)的學(xué)習(xí)算法

條件隨機(jī)場(chǎng)模型實(shí)際上是定義在時(shí)序數(shù)據(jù)上的對(duì)數(shù)線性模型，類似最大熵模型卜朗，所以也可以用IIS法拔第，梯度下降法以及擬牛頓法。

條件隨機(jī)場(chǎng)的預(yù)測(cè)算法

條件機(jī)場(chǎng)的預(yù)測(cè)問(wèn)題是給定條件隨機(jī)場(chǎng) $P(Y|X)$ 和輸入序列（觀測(cè)序列） $x$ 场钉，求條件概率最大的輸出序列（標(biāo)記序列） $y^*$ 蚊俺。常用的算法是維特比算法，使用了動(dòng)態(tài)規(guī)劃的思路逛万。

最后編輯于：2020.08.22 02:15:19

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

人面猴
序言：七十年代末泳猬，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子宇植，更是在濱河造成了極大的恐慌得封，老刑警劉巖，帶你破解...
沈念sama閱讀 211,376評(píng)論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件指郁，死亡現(xiàn)場(chǎng)離奇詭異忙上，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)闲坎，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,126評(píng)論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)疫粥，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)茬斧，“玉大人，你說(shuō)我怎么就攤上這事梗逮∠畋” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 156,966評(píng)論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵慷彤，是天一觀的道長(zhǎng)娄蔼。經(jīng)常有香客問(wèn)我，道長(zhǎng)底哗，這世上最難降的妖魔是什么岁诉？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,432評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮艘虎，結(jié)果婚禮上唉侄，老公的妹妹穿的比我還像新娘。我一直安慰自己野建，他們只是感情好属划，可當(dāng)我...
茶點(diǎn)故事閱讀 65,519評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著候生，像睡著了一般同眯。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上唯鸭，一...
開(kāi)封第一講書(shū)人閱讀 49,792評(píng)論 1贊 290
城市分裂傳說(shuō)
那天须蜗，我揣著相機(jī)與錄音，去河邊找鬼目溉。笑死明肮，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的缭付。我是一名探鬼主播柿估，決...
沈念sama閱讀 38,933評(píng)論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼陷猫！你這毒婦竟也來(lái)了秫舌？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 37,701評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤绣檬，失蹤者是張志新（化名）和其女友劉穎足陨，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體娇未，經(jīng)...
沈念sama閱讀 44,143評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡墨缘，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,488評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片飒房。...
茶點(diǎn)故事閱讀 38,626評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡搁凸，死狀恐怖媚值，靈堂內(nèi)的尸體忽然破棺而出狠毯，到底是詐尸還是另有隱情，我是刑警寧澤褥芒，帶...
沈念sama閱讀 34,292評(píng)論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布嚼松，位于F島的核電站，受9級(jí)特大地震影響锰扶，放射性物質(zhì)發(fā)生泄漏献酗。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,896評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一坷牛、第九天我趴在偏房一處隱蔽的房頂上張望罕偎。院中可真熱鬧，春花似錦京闰、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,742評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)痊土。三九已至犯祠，卻和暖如春酌呆，著一層夾襖步出監(jiān)牢的瞬間肪笋，已是汗流浹背月劈。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,977評(píng)論 1贊 265
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留藤乙，地道東北人猜揪。一個(gè)月前我還...
沈念sama閱讀 46,324評(píng)論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像坛梁，于是被迫代替她去往敵國(guó)和親而姐。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,494評(píng)論 2贊 348