2018 & 2019's One algrithm per day

Clustering

Clustering中文譯“聚類(lèi)”袄简，目的是將相似的東西分到一類(lèi)。因?yàn)椴恍枰獛?biāo)簽的數(shù)據(jù)進(jìn)行訓(xùn)練學(xué)習(xí)泛啸，因而是一種無(wú)監(jiān)督學(xué)習(xí)過(guò)程绿语，需要和Classification（分類(lèi)）區(qū)別開(kāi)來(lái)。

Day 5 | K-Means - 1.19?

K-means是最基本的聚類(lèi)算法(baseline般的存在)候址，以歐氏距離為特征把m維的數(shù)據(jù)點(diǎn)映射到歐氏空間中進(jìn)行聚類(lèi)吕粹。

算法的核心思想是根據(jù)數(shù)據(jù)初始化K個(gè)中心點(diǎn)(center)，然后按樣本點(diǎn)和中心點(diǎn)的距離將樣本點(diǎn)劃分到不同的類(lèi)中岗仑。使得每個(gè)樣本點(diǎn)到所在聚類(lèi)中心的距離盡可能地小于到其他類(lèi)中心的距離匹耕。而剩下的誤差就是問(wèn)題的不可分性以及算法的固有缺陷了≤瘢基于上述要求可以寫(xiě)出目標(biāo)函數(shù) $J=\sum_{n=1}^N\sum_{k=1}^K\pi_{nk} ||X_n-\mu_k||^2$ 泌神。優(yōu)化時(shí)，令 $\frac{dJ}{d\mu_k} =0$ 有 $\mu_k=\frac{\sum_n\pi_{nk}x_n}{\sum_n\pi_{nk}}$ ---①舞虱。

由此可得K-means的偽代碼：

1欢际、隨機(jī)選取k個(gè)中心點(diǎn) $\mu_k$ ;

2、將每個(gè)數(shù)據(jù)點(diǎn)歸類(lèi)到離它最近中心點(diǎn)的類(lèi)中矾兜；（固定 $\mu_k$ 更新 $\pi_{nk}$ ）

3损趋、固定 $\pi_{nk}$ ，由①式更新 $\mu_k$ 椅寺；

4浑槽、重復(fù)2、3步優(yōu)化J直到迭代至最大步數(shù)或者J收斂為止返帕。

最后桐玻，總結(jié)一下K-means算法的一些特點(diǎn)：首先算法有簡(jiǎn)單，運(yùn)算時(shí)間短的優(yōu)點(diǎn)荆萤。但因?yàn)槌跏贾行狞c(diǎn)的隨機(jī)性只能收斂到局部最優(yōu)镊靴，這是其最大的缺陷铣卡。所以K-means算法都需要重復(fù)多次試驗(yàn)再選取最優(yōu)的結(jié)果。

K-means實(shí)現(xiàn)

Day 6 | K-Medoids & Hungarian algorithm - 1.21

K-means 與 K-medoids不同的地方在于中心點(diǎn)的選取偏竟。K-means算法的中心點(diǎn)相當(dāng)于直接取同類(lèi)數(shù)據(jù)的”均值“煮落，這樣對(duì)非數(shù)值類(lèi)型的特征是不友好的。比如狗的品種（薩摩踊谋、柯基）蝉仇，距離 $||x_i-x_j||^2$ 是無(wú)法度量的。

而K-medoids的中心點(diǎn)相當(dāng)于取樣本的“中值”殖蚕，其中心點(diǎn)將會(huì)從原樣本點(diǎn)中產(chǎn)生轿衔，只要將K-means的歐式距離度量改為相似度度量，得目標(biāo)函數(shù) $J=\sum_{n=1}^N\sum_{k=1}^K\pi_{nk}V(x_n,\mu_k)$ --V為 $x_n$ 和 $\mu_k$ 的dissimilarity度量函數(shù)睦疫，可以用相似矩陣來(lái)實(shí)現(xiàn)害驹，有點(diǎn)相對(duì)距離的意味。

總結(jié)：除了應(yīng)用范圍更廣外笼痛，K-medoids還比K-means更好地消除outlier的影響裙秋。不過(guò)初始化中心點(diǎn)的方法同樣決定其結(jié)果只能是局部最優(yōu)琅拌。

Day 7 | GMM - 1.22

混合高斯模型是一種基于數(shù)據(jù)學(xué)習(xí)出概率密度函數(shù)的參數(shù)缨伊，是一種soft assignment。其好處是同時(shí)獲得每個(gè)樣本的cluster和assign到每個(gè)cluster的概率进宝。所以除了用在clustering外刻坊，還能用于density estimation。對(duì)于風(fēng)險(xiǎn)較大的任務(wù)党晋，算法能根據(jù)概率判斷是否對(duì)決策有把握谭胚，在把握比較低的時(shí)候能拒絕參與決策。

介紹完背景未玻，接著切入算法的原理灾而。首先，m維向量的正態(tài)概率密度是長(zhǎng)這樣的 $N(x)=\frac{1}{(2\pi)^{\frac{n}{2} }|\sum|^{\frac{1}{2} }} e^{-\frac{1}{2}(x-\mu)^T \sum^{-1}(x-\mu)}$ 扳剿，高斯混合分布為 $p_m(x)=\sum_{i=1}^kp(k)p(x|\mu_k,\Xi_ k)$ 旁趟。貝葉斯分類(lèi)器的最佳劃分為 $argmax_{（k）}p_m(k=i|x_j)=\frac{p(k=i)p(x_j|\mu_i,\Xi_i)}{\sum_{k=1}^Kp(k)p(x_j|\mu_i,\Xi_i)}$ --①。

優(yōu)化上式其實(shí)相當(dāng)于求出每個(gè)k類(lèi)分布下最有可能的高斯分布參數(shù)（最大化似然）以及在每個(gè)混合高斯模型下可能性最大的K類(lèi)（K的后驗(yàn)概率分布 $p(k|x_j,\theta _k)$ ）庇绽。是應(yīng)用EM算法解最大似然估計(jì)的一個(gè)具體例子锡搜，在原數(shù)據(jù)x不完整的情況下，引入隱變量k能“補(bǔ)全”缺少的信息解出似然函數(shù)瞧掺。EM算法就是分別處理隱變量k（E步）以及模型參數(shù) $\theta$ （M步）的一個(gè)過(guò)程耕餐。即：

1、根據(jù)當(dāng)前參數(shù)求①式樣本關(guān)于k的后驗(yàn)概率（E步）辟狈；

2肠缔、對(duì)似然函數(shù) $LL(\Theta )=ln(\prod\nolimits_{j=1}^np_m(xj) )$ 分別求導(dǎo)更新 $\mu_k,\Xi _k,p(k)$ (M步)

Day 8 | EM(Expectation Maximization)算法 - 1.24

EM算法是一種解決特殊最大似然問(wèn)題的迭代方法。這類(lèi)問(wèn)題通常引入合適的隱變量來(lái)獲得最大似然解，當(dāng)估計(jì) $p(X|\theta )$ 中的 $\theta$ 很困難桩砰，而優(yōu)化 $p(X,Z|\theta)$ 卻容易得多時(shí)拓春，此時(shí)EM算法就適用了。

推導(dǎo)過(guò)程

對(duì)數(shù)似然函數(shù)引入一個(gè)關(guān)于隱變量的分布q(Z)作分解: $logp(X|\theta)=\sum_Zq(Z)log{\frac{p(X,Z|\theta)}{q(Z)} +(-\sum_Zq(Z)log{\frac{p(Z|X,\theta)}{q(Z)}})}=g(q,\theta)+KL(q||p)$ ▲

$KL(q||p)$ 是散度（非負(fù)的）亚隅，所以肯定有 $g(q,\theta)≤logp(X|\theta)$ 硼莽，即 $g(q,\theta)$ 是 $logp(X|\theta)$ 的下界。

E步

這時(shí)對(duì)數(shù)似然函數(shù)已經(jīng)得到了很大的化簡(jiǎn)匆光， $Q(\theta,\theta^t)$ 是包含樣本變量和隱變量的似然函數(shù) $logp(X,Z|\theta)$ 關(guān)于后驗(yàn)概率 $p(Z|X,\theta^t)$ 的期望。

M步

是固定的酿联，對(duì) $logp(X|\theta)$ 求導(dǎo)更新相當(dāng)于對(duì) $Q(\theta,\theta^t)$ 求導(dǎo)终息。更新 $\theta$ 時(shí)，若KL散度仍是0贞让，則說(shuō)明達(dá)到某一個(gè)局部最優(yōu)解了周崭，迭代可以停止了；一般KL散度變?yōu)榉?喳张，更新會(huì)提升對(duì)數(shù)似然的上界续镇。

有時(shí)M步除了做最大似然之外，也可以引入先驗(yàn)概率做Maximum a Posterior（MAP）來(lái)做销部。而當(dāng)似然函數(shù)求不出最大值時(shí)摸航，還可以做Generalized EM(GEM)，只需要能得到比舊值更好的結(jié)果就行舅桩。

Day 9 | 向量量化(Vector Quantization) - 1.26

VQ可以理解為：將一個(gè)向量空間中的點(diǎn)用其中的一個(gè)有限向量子集來(lái)進(jìn)行編碼(聚類(lèi)后的索引總能起到壓縮效果的)酱虎。

Day 1 | 譜聚類(lèi)（Spectral Clustering）- 11.15

比起傳統(tǒng)K-Means，譜聚類(lèi)對(duì)數(shù)據(jù)分布的適應(yīng)性更強(qiáng)擂涛，聚類(lèi)效果優(yōu)秀读串，計(jì)算量小同時(shí)實(shí)現(xiàn)起來(lái)也不復(fù)雜。

主要思想是把數(shù)據(jù)看作空間中的點(diǎn)歼指，通過(guò)圖論的無(wú)向圖描述數(shù)據(jù)關(guān)系并通過(guò)矩陣分析進(jìn)行“切圖”聚類(lèi)爹土。

?無(wú)向權(quán)重圖

主要由對(duì)稱(chēng)的鄰接矩陣W和對(duì)角矩陣D描述。

度矩陣

頂點(diǎn)的度

vol（A）可看作子圖的權(quán)重

?鄰接矩陣

鄰接矩陣常用KNN（K近鄰）方法獲取踩身，為了保持對(duì)稱(chēng)性胀茵，一般加條件：

或者通過(guò)加核的方法處理點(diǎn)的鄰接度，常用高斯核函數(shù)RBF

?拉普拉斯矩陣

拉普拉斯矩陣L=D-W挟阻，有良好的性質(zhì)：對(duì)稱(chēng)琼娘，特征數(shù)都是實(shí)數(shù)峭弟，矩陣半正定以及以下關(guān)系：

矩陣降維特征空間的獲取

▲另一個(gè)常用的形式是 $f^TLf=\sum_{1\leq i<j\leq n}w_{ij}(f_i-f_j)^2$

?無(wú)向圖切圖

兩個(gè)子圖間切圖的（損失）權(quán)重

k個(gè)子圖的切圖

被切斷的邊的權(quán)值之和就是cut值。讓子圖內(nèi)的點(diǎn)權(quán)重和大脱拼，子圖間的點(diǎn)權(quán)重和小终畅。最小化cut（A1,A2,..Ak）可實(shí)現(xiàn)裆泳，但會(huì)存在只切小權(quán)重邊緣點(diǎn)的問(wèn)題假栓。

Like this

?RatioCut切圖

為了解決上面的問(wèn)題年鸳，RatioCut不僅最小化切圖損失權(quán)重，還考慮最大化每個(gè)子圖的個(gè)數(shù)（類(lèi)似于平均權(quán)重）

RatioCut

引入指示向量（特征向量）hij（表示樣本i屬于j類(lèi)）有 $h_i^Th_i=|A_j|*\frac{1}{|A_j|}=1,h_i^Th_j=0$

j=1,2,...k

轉(zhuǎn)化為最小化跡

目標(biāo)函數(shù)

?Ncut切圖

子圖樣本個(gè)數(shù)多并不意味子圖的權(quán)重大（子圖類(lèi)內(nèi)相似性大）赌蔑，所以Ncut采用子圖的權(quán)重和vol(Ai)進(jìn)行正規(guī)化：

Ncut切圖

目標(biāo)函數(shù)

解的過(guò)程與RatioCut相近俯在，不同的是 $H^TH\neq I$ 。將D拆開(kāi)有另一個(gè)表示形式：

拆解H的形式

*這里的指示向量相當(dāng)于 $h_i=D^{-\frac{1}{2}}f_i$

$D^{-\frac{1}{2}} LD^{-\frac{1}{2} }$ 是標(biāo)準(zhǔn)化拉普拉斯矩陣娃惯，即 $\frac{Lij}{\sqrt{didj} }$

最后跷乐，譜聚類(lèi)還是有點(diǎn)缺點(diǎn)的：（1）若譜聚類(lèi)的最終的維度非常高，聚類(lèi)的效果以及運(yùn)算時(shí)間也不友好趾浅；（2）譜聚類(lèi)比較依賴(lài)相似矩陣愕提，所取的相似矩陣不同會(huì)影響到聚類(lèi)效果。

頻譜切圖

Optimize

目標(biāo)函數(shù)有了皿哨，怎么解出結(jié)構(gòu)矩陣H卻是個(gè)NP hard浅侨。引入瑞利商-Rayleigh Quotient后可以巧妙地解目標(biāo)函數(shù)，以Radio Cut為例：

$argmin_{(H)}tr(H^TLH)$ 相當(dāng)于分別對(duì)每個(gè)向量 $h_i$ 求 $argmin_{(h_i)}h_i^TLh_i$

?而Rayleigh quotient指出往史， $R(L,h)=\frac{h^TLh}{h^Th}$ 的最大值和最小值分別在 $L$ 的最大特征值以及最小特征值取得仗颈，并且極值也在對(duì)應(yīng)的其他特征值取得佛舱。由于 $h_i^Th_i=1$ 椎例，所以 $minR(L,h)->minh^TLh$

分別求出 $L$ 的k個(gè)最小特征值對(duì)應(yīng)的特征向量，就有 $H$ 的輪廓了请祖。最后給這k個(gè)特征向量做Kmeans就能得到樣本的聚類(lèi)結(jié)果了订歪。

Day 14 | Hierarchical Clustering - 2.1

Day 2 | 馬爾可夫鏈（Markov Chains）- 11.23

Day 3 | 評(píng)估準(zhǔn)則 - 12.8

轉(zhuǎn)自維基百科

Day 4 | 協(xié)方差的意義 - 1.18

協(xié)方差Cov(X,Y)描述兩個(gè)隨機(jī)變量X和Y之間的相互關(guān)系，具體可以分為如下三種情況：

在圖中的區(qū)域（1）中肆捕，有 X>EX 刷晋，Y-EY>0 ，所以(X-EX)(Y-EY)>0慎陵；

在圖中的區(qū)域（2）中眼虱，有X<EX ，Y-EY>0 席纽，所以(X-EX)(Y-EY)<0捏悬；

在圖中的區(qū)域（3）中，有X<EX 润梯，Y-EY<0 过牙，所以(X-EX)(Y-EY)>0甥厦；

在圖中的區(qū)域（4）中，有X>EX 寇钉，Y-EY<0 刀疙，所以(X-EX)(Y-EY)<0。

平均來(lái)說(shuō)扫倡，就是正相關(guān)的面積大部分分布在（1）（3）谦秧，負(fù)相關(guān)的面積大部分分布在（2）（4）。

協(xié)方差的意義如同（1）（3）的面積減去（2）（4）的面積撵溃，說(shuō)明X,Y的相關(guān)關(guān)系油够。

由此可看出方差是失去方向信息的協(xié)方差，只指示數(shù)據(jù)分布離平均值的離散程度征懈。

正相關(guān)

負(fù)相關(guān)

不相關(guān)

Day 9 | t test & p-value - 1.25

Day 10 | Soft Thresholding - 1.29

Soft Thresholding又稱(chēng)軟閾值石咬，一般在稀疏規(guī)則化的文章中都會(huì)出現(xiàn)。

Soft Thresholding 有三種常用表達(dá)方式：

1卖哎、 $soft(\omega ,\lambda)=sgn(\omega)(|\omega|-\lambda)_+$

2鬼悠、 $soft(\omega ,\lambda)=sgn(\omega)max(0,|\omega|-\lambda)$

3、 $soft(\omega,\lambda)=\omega+\lambda亏娜，\omega\leq-\lambda|or|0焕窝，|\omega|\leq\lambda|or|\omega-\lambda，\omega\geq\lambda$

第三種表達(dá)方式

Soft Thresholding 可以優(yōu)化以下問(wèn)題：

$argmin_{(x)}||x-b||_2^2+\lambda||x||_1$ 或 $argmin_{x}\alpha x^2-2\beta x+2\lambda |x|$

上式(第一項(xiàng))相當(dāng)于解 $f(x_i)=(x_i-b_i)^2+\lambda|x_i|$ 的最小值维贺，逐一對(duì) $x_i$ 求導(dǎo)并令導(dǎo)數(shù)為0即可得到解為 $\tilde{x} =soft(b,\frac{\lambda}{2})=sgn(b)(|b|-\frac{\lambda}{2})_+$ 或 $\frac{1}{\alpha}sgn(\beta)(|\beta|-\lambda)_+$

Day 11 | Dimesionality Reduction - 1.30

首先它掂，關(guān)于特征“feature”有兩種重要的處理方法-feature selection 和 dimensionality reduction。前者（選出重要的特征并拋棄不重要的特征）可以看作是后者（把高維向量映射成低維向量）的特例溯泣。

降維的通常目標(biāo)是最大限度地降低數(shù)據(jù)的維度同時(shí)保留目標(biāo)的重要信息虐秋。

PCA、LDA...

Day 12 | (瑞利商)Rayleigh Quotient - 1.31

瑞利商常用于優(yōu)化拉普拉斯矩陣構(gòu)成的算子垃沦，除了優(yōu)化譜聚類(lèi)外客给，還能優(yōu)化PCA、Fisher LDA等結(jié)構(gòu)相似的算子

1肢簿、普通瑞利商 $R(L,h)=\frac{h^TLh}{h^Th}$

可以看出對(duì) $h$ 的幅值進(jìn)行正則化既不影響 $R(L,h)$ 的取值靶剑，也不改變 $h$ 的方向

$maxR(L,h)$ 可以轉(zhuǎn)化為拉格朗日乘子問(wèn)題 $maxR(L,h)=\frac{h^TLh}{h^Th}，s.t.h^Th=c$

$J(h)=h^TLh-\lambda (h^Th-c)$ 池充， $\frac{dJ(h)}{dh}=0\Rightarrow Lh=\lambda h$

所以 $R(L,h)$ 的極值為 $L$ 的特征值 $\lambda$ 桩引，對(duì)應(yīng)的解為其特征向量。

普通瑞利商能解Ratio Cut和PCA： $maxp^TA^TAp=p^TRp收夸，s.t.p^Tp=1$

2坑匠、泛化瑞利商 $R(L,h)=\frac{h^TLh}{h^TDh}=\frac{f^T(D^{-\frac{1}{2}}LD^{-\frac{1}{2}})f}{f^Tf}$

上式加上正則化約束 $h^TDh=c$ 后的解為 $Lh=\lambda Dh$

作變形 $h=D^{-\frac{1}{2}}f$ ，可得 $D^{-\frac{1}{2}}LD^{-\frac{1}{2}}f= \lambda f$

泛化瑞利商能解Ncut和Fisher LDA(線性判別分析).

Day 13 | AUC & ROC - 3.1

ROC曲線全稱(chēng)為受試者工作特征曲線（Receiver operating characteristic curve）咱圆。最早運(yùn)用實(shí)在軍事上笛辟，雷達(dá)兵會(huì)難以區(qū)分?jǐn)硻C(jī)和飛鳥(niǎo)功氨，每個(gè)雷達(dá)兵的預(yù)報(bào)標(biāo)準(zhǔn)（謹(jǐn)慎程度）不同，將他們漏報(bào)和錯(cuò)報(bào)的概率畫(huà)到二維坐標(biāo)上（縱軸為敏感性-對(duì)應(yīng)準(zhǔn)確預(yù)報(bào)概率手幢，橫軸為特異性-對(duì)應(yīng)錯(cuò)報(bào)概率）捷凄。匯總后會(huì)發(fā)現(xiàn)預(yù)報(bào)性能分布在一條曲線上，對(duì)應(yīng)于不同取閥值區(qū)分正負(fù)樣本的性能围来。

從列聯(lián)表中引出不同指標(biāo)

減小判別正類(lèi)的閥值跺涤，會(huì)同時(shí)提高準(zhǔn)確率和誤報(bào)率，這說(shuō)明離左上角最近的點(diǎn)是這個(gè)系統(tǒng)的最佳性能监透。通常我們只關(guān)心上報(bào)的情況桶错，所以以TPR為縱坐標(biāo)和以TNR為橫坐標(biāo)即可畫(huà)出ROC曲線，分別對(duì)應(yīng)與收益和代價(jià)胀蛮。

分類(lèi)的四種情況

由于ROC曲線不能直接說(shuō)明分類(lèi)器的效果院刁，所以就引入了數(shù)值A(chǔ)UC（Area Under Curve）來(lái)直觀地衡量分類(lèi)器的效果。AUC即ROC曲線下與坐標(biāo)軸圍成的面積粪狼。

用一句話來(lái)說(shuō)明AUC的意義退腥，就是：隨機(jī)取一個(gè)正例和一個(gè)負(fù)例，分類(lèi)器給正樣本打分高于負(fù)樣本的概率再榄。

AUC判斷分類(lèi)器的幾種情況：

1狡刘、AUC=1，是完美分類(lèi)器困鸥，至少存在一個(gè)閥值能得出完美預(yù)測(cè)嗅蔬。

2、AUC=0.5疾就，跟隨機(jī)預(yù)測(cè)一樣澜术，模型沒(méi)有預(yù)測(cè)價(jià)值。

3虐译、AUC<0.5瘪板，比隨機(jī)預(yù)測(cè)還差吴趴；但只要反預(yù)測(cè)漆诽，就能優(yōu)于隨機(jī)預(yù)測(cè)。

最后說(shuō)一下ROC和AUC的一個(gè)很好的特性锣枝，測(cè)試集中的正負(fù)樣本分布變化時(shí)厢拭，ROC曲線能保持穩(wěn)定。如下圖所示：

Reference

-?zhwhong的文章（簡(jiǎn)書(shū)）：機(jī)器學(xué)習(xí)之分類(lèi)性能度量指標(biāo) : ROC曲線撇叁、AUC值供鸠、正確率、召回率

Day 14 | 絕對(duì)中位差（MAD）- 3.15

絕對(duì)中位差是對(duì)單變量數(shù)值型數(shù)據(jù)樣本偏差的魯棒性測(cè)量陨闹，表示為 $MAD=median(|X_i-median(X)|)$

是數(shù)據(jù)點(diǎn)到中位數(shù)絕對(duì)偏差的中位數(shù)楞捂，比標(biāo)準(zhǔn)差的魯棒性更佳薄坏。因?yàn)闃?biāo)準(zhǔn)差使用距離的平方，偏差大的權(quán)重更大寨闹，因而異常值對(duì)其影響更大胶坠。而MAD能消除少量異常值的影響。

Day 15 | 維度災(zāi)難 - 3.19

維度災(zāi)難：隨著維度的增加繁堡，樣本將會(huì)在維度空間里變得越來(lái)越稀疏沈善，而要取得足夠覆蓋范圍的數(shù)據(jù)，就只能增大樣本數(shù)量（指數(shù)級(jí)）椭蹄，否則只能陷入過(guò)擬合闻牡，導(dǎo)致預(yù)測(cè)性能下降。(比如總數(shù)為1000的屬性空間中要求樣本屬性覆蓋總體的60%绳矩，選定一個(gè)屬性所需的樣本數(shù)為600罩润，選定兩個(gè)屬性需774個(gè)，選定三個(gè)屬性則需要843個(gè)樣本)

集成聚類(lèi)評(píng)估

Day 16 | 算法集成聚類(lèi)的集成效果分析 - 3.22

優(yōu)秀的算法集成方法往往能發(fā)現(xiàn)數(shù)據(jù)的一致性并挖掘數(shù)據(jù)的互補(bǔ)信息翼馆，但是也存在引入沖突信息甚至得出錯(cuò)誤結(jié)構(gòu)的問(wèn)題哨啃。關(guān)于這幾種情況，通過(guò)下圖一一介紹：

首先写妥，為了簡(jiǎn)化分析拳球，我們?nèi)【植拷Y(jié)構(gòu)進(jìn)行對(duì)比，因?yàn)榇_保了局部結(jié)構(gòu)的發(fā)掘也就逐漸確保了全局結(jié)構(gòu)識(shí)別珍特。因此祝峻，我們主要分析關(guān)于樣本1、2的劃分情況扎筒。

1莱找、一致性：劃分的子結(jié)果統(tǒng)一且正確或者錯(cuò)誤的子結(jié)果相互抵消，子結(jié)果的集成增強(qiáng)了穩(wěn)定性（如C1和C21或C22嗜桌、C23奥溺、C3）

2、互補(bǔ)性：劃分的子結(jié)果不統(tǒng)一骨宠，但是正確的子劃分信號(hào)較強(qiáng)浮定，帶來(lái)了正確的互補(bǔ)信息（如C1和C22、C23层亿、C3桦卒，這里沒(méi)有顯示強(qiáng)度）

3、矛盾性：劃分的子結(jié)果不統(tǒng)一匿又，正確和錯(cuò)誤的子信號(hào)強(qiáng)度相當(dāng)方灾，混淆了正確的結(jié)構(gòu)（同互補(bǔ)性）

4、錯(cuò)誤性：錯(cuò)誤的子信號(hào)掩蓋了正確的子信號(hào)碌更，導(dǎo)致判定的結(jié)構(gòu)錯(cuò)誤（同互補(bǔ)性）

三樣本的劃分集

Day 17 | 規(guī)范化互信息（NMI）- 4.9

? ? 首先裕偿，描述互信息I(X; Y)的一些性質(zhì)：

??(1)?I(X; Y)≥0 (2)I(X; Y)=I(Y; X)

(3)X,Y獨(dú)立時(shí)洞慎，I(X; Y)=0 (4)當(dāng)X,Y能相互推出時(shí)，I(X; Y)=H(X)=H(Y)

其次嘿棘，I(X; Y)的定義為

拢蛋，實(shí)際上是更廣泛的相對(duì)熵的特殊形式。如果X, Y不獨(dú)立蔫巩，可通過(guò)聯(lián)合概率分布和邊緣概率分布乘積的KL散度來(lái)判斷他們是否接近獨(dú)立谆棱，

這就是X和Y之間的互信息。同時(shí)它也能表示為自信息和條件熵的關(guān)系：

通俗地說(shuō)圆仔，互信息可以看作知道y值而使得x不確定性的減少（即Y透露了多少關(guān)于X的信息量）因?yàn)閄的熵H(X)指X的不確定度垃瞧，H(Y|X)表示已知X的情況下，Y的不確定度坪郭。

互信息个从、條件熵和聯(lián)合熵的關(guān)系圖：

關(guān)于NMI的缺點(diǎn)：只考慮變量的分布而沒(méi)有考慮變量的出現(xiàn)頻率，如文本分類(lèi)任務(wù)中判斷一個(gè)詞和某類(lèi)的相關(guān)程度歪沃，但往往未考慮詞頻的影響嗦锐。

Day 18 | *希爾伯特空間(Hilber Space) - 4.15（較散亂，有待梳理）

希爾伯特空間與線性空間有著不少的關(guān)聯(lián)沪曙，可以將希爾伯特空間理解為：

把函數(shù)投影到函數(shù)空間（核函數(shù)）的一個(gè)點(diǎn)上奕污，而這個(gè)點(diǎn)又能映射到一個(gè)無(wú)窮維的（特征函數(shù)）特征空間。最終液走，該特征空間的基底（特征函數(shù)向量）又能夠重構(gòu)出這個(gè)函數(shù)空間碳默。

首先，需要介紹一下距離缘眶、范數(shù)以及內(nèi)積嘱根。所有空間都有距離和角度的概念：

距離的定義要滿足非負(fù)性、對(duì)稱(chēng)性和三角不等式三個(gè)條件巷懈；

范數(shù)的定義需要滿足非負(fù)性该抒、數(shù)乘性和三角不等式；

內(nèi)積的定義也有對(duì)稱(chēng)性顶燕、數(shù)乘性和正定性凑保；

內(nèi)積可以導(dǎo)出范數(shù)，而范數(shù)也可以導(dǎo)出距離割岛，同時(shí)內(nèi)積還能導(dǎo)出角度愉适。

其次，對(duì)一個(gè)函數(shù)按照 $x$ 以無(wú)窮小間隔采樣就能將其表示為一個(gè)無(wú)窮維向量的形式 $(f(x_{0}),f(x_{1}),...,f(x_{∞}) )$ 癣漆，其內(nèi)積可以定義為 $<f,g>=\int f(x)g(x)dx$ 。

所以剂买，具有線性結(jié)構(gòu)且定義了內(nèi)積的惠爽，具有完備性的無(wú)窮維空間就稱(chēng)為希爾伯特空間癌蓖。

都知道一個(gè)矩陣可以進(jìn)行特征值分解時(shí)，其特征向量構(gòu)成了這n維空間的一組基底婚肆。

函數(shù)空間中的無(wú)窮維矩陣 $K(x,y)$ 若滿足：

正定性 $\int \int f(x)K(x,y) f(y)dxdy \geq 0$

對(duì)稱(chēng)性 $K(x,y)=K(y,x)$

則這個(gè)函數(shù)稱(chēng)為核函數(shù)租副，有特征函數(shù) $\int K(x,y)\psi (x)dx=\lambda \psi(y)$ ，所有的特征函數(shù) $\{ \psi_i\}^{∞}_{i=1}$ 就構(gòu)成核函數(shù)空間的一組基地较性。

最后介紹再生希爾伯特空間 - RKHS

RKHS 是由核函數(shù)構(gòu)成的空間用僧，其中任意函數(shù)都可以由基底 $\{\sqrt{\lambda_i} \psi_i\}^{∞}_{i=1}$ 表示。將核函數(shù)的一個(gè)元素固定赞咙，其內(nèi)積為 $<K(x_0,y),K(y_0,x)>_H=\sum^{∞}_{i=0}\lambda_i\psi _i(x_0)\psi _i(y_0)=K(x_0,y_0)$ 责循，這就是RKHS的再生性。

Day 19 | Graph Embeddings - 4.16

Day 20 | L2 norm Regularization - 4.17

Day 21 | Lagrange Methods & KKT & 對(duì)偶問(wèn)題 - 4.22

用于優(yōu)化的Lagrange Multiplier（LM）的缺點(diǎn)是收斂困難攀操，在接近最優(yōu)解的時(shí)候會(huì)有振蕩院仿。Augmented Lagrange Multiplier （ALM）加入二次偏差項(xiàng)，提高了Lagrange Function 的收斂性速和，但又會(huì)引入分解特性差的問(wèn)題歹垫。所以有人提出Augmented lagrange + Alternating Direction Minimzation（ADMM），固定其他“方向”來(lái)優(yōu)化其中一個(gè)“方向”颠放，能進(jìn)行二次項(xiàng)解耦并優(yōu)化排惨，進(jìn)而保留了可分解性又能收斂。

?(Lagrange Multiplier)拉格朗日乘子法

拉格朗日乘子法能尋找多元函數(shù)在一組約束下的極值碰凶。通過(guò)引入拉格朗日乘子

?KKT 條件

?對(duì)偶問(wèn)題

Day 22 | Pseudo Inverse 偽逆 - 4.28

在秩 $r<m,n$ 的情況下若贮，沒(méi)有合適的左逆或者右逆矩陣來(lái)重構(gòu)出單位矩陣。而阻礙求逆的因素在于零空間中的向量痒留，所以采用偽逆矩陣 $A^?$ 是一種逼近單位矩陣的辦法谴麦。

由于行列空間的秩都為 $r$ ，行空間中的點(diǎn) $x$ 可以通過(guò) $A$ 一一對(duì)應(yīng)地映射到列空間的 $Ax$ 上伸头，而列空間中的 $Ax$ 也可以通過(guò)偽逆矩陣 $A^?$ 映射回行空間中匾效，分割開(kāi)了零空間的影響。

重要的四個(gè)子空間

偽逆可以通過(guò)SVD來(lái)求取恤磷。

Day 23 | Trace norm regularization - 5.20

低秩約束能應(yīng)用在很多問(wèn)題上面哼，例如matrix completion。

低秩約束常用核范數(shù) $||X||_*=\sum^r_{i=1}\sigma_i(X)$ ?扫步，而 $||X||_F^2= \sqrt{Tr(X^TX)} =(\sum^m_{i=1}\sum^n_{j=1}X^2_{ij})=\sum^r_{i=1}\sigma^2_i$

所以 $||X||^2_F=||XX^T||_*$ 對(duì) $XX^T$ 有同樣的低秩約束效果魔策。

假設(shè) $M\in R^{n×n}$ 是原本的低秩矩陣，且有m 個(gè)非零項(xiàng) $M_{ij}\in \Omega$ 河胎， $P_\Omega (X)_{ij}=X_{ij}, if(i,j)\in \Omega$ 闯袒。則低秩優(yōu)化的問(wèn)題寫(xiě)成：

${min||X||_*\\s.t. X_{ij}=M_{ij}，(i,j)\in\Omega }或 {min||X||_*\\s.t. P_\Omega(X)=P_\Omega(M) }$

*上式有個(gè)前提： $m\ge Cn^{6/5}rlogn$ ?，C某個(gè)正數(shù)政敢。

解上式常用SVT算法[cai, 2010]其徙，該算法能在一分鐘內(nèi)恢復(fù)低秩大樣本（n=1000）的矩陣，且有稀疏的特性喷户。算法具體如下：

${X^k=shrink(Y^{k-1}, \tau)=UD_{\tau}(\Sigma )V^T\\ Y^k=Y^{k-1}+\delta_kP_\Omega(M-X^k)}$

$shrink(Y,\tau)$ 是作用在奇異值上的軟閾值函數(shù)唾那， $\delta_k$ 是步長(zhǎng)序列。閾值和步長(zhǎng)的設(shè)置見(jiàn)于后文褪尝。

最終收斂的條件為：

${X=D_\tau(Y)=argmin_X\frac{1}{2}||X-Y||^2_F+\tau||X||_*\\ P_\Omega(X-M)=0}$

*奇異值閾值算子的迭代更新規(guī)則：

首先經(jīng)驗(yàn)值取 $\tau=5n$ 闹获，再設(shè)奇異值數(shù)目 $s_k=rank(X^{k-1})+1$ ，然后查看 $Y^{k-1}$ 的前 $s_k$ 個(gè)奇異值是否有小于 $\tau$ （最小的）的值河哑，有就不用變更 $s_k$ 避诽；否則更新 $s_k=s_k+l$ ，常取 $l=5$

步長(zhǎng)的設(shè)法：一般 $0<\delta<2$ 能保證收斂灾馒，但其更新速度會(huì)很慢茎用，作者建議采用 $\delta =1.2\frac{n_1n_2}{m}$

最后編輯于：2019.05.21 00:49:26

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市睬罗，隨后出現(xiàn)的幾起案子轨功，更是在濱河造成了極大的恐慌，老刑警劉巖容达，帶你破解...
沈念sama閱讀 216,402評(píng)論 6贊 499
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件古涧，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡花盐，警方通過(guò)查閱死者的電腦和手機(jī)羡滑，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,377評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)算芯，“玉大人柒昏，你說(shuō)我怎么就攤上這事∥踝幔” “怎么了职祷？”我有些...
開(kāi)封第一講書(shū)人閱讀 162,483評(píng)論 0贊 353
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)届囚。經(jīng)常有香客問(wèn)我有梆，道長(zhǎng)，這世上最難降的妖魔是什么意系？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,165評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任泥耀，我火速辦了婚禮，結(jié)果婚禮上蛔添，老公的妹妹穿的比我還像新娘痰催。我一直安慰自己兜辞，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,176評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布陨囊。她就那樣靜靜地躺著弦疮，像睡著了一般夹攒。火紅的嫁衣襯著肌膚如雪蜘醋。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 51,146評(píng)論 1贊 297
城市分裂傳說(shuō)
那天咏尝，我揣著相機(jī)與錄音压语，去河邊找鬼。笑死编检，一個(gè)胖子當(dāng)著我的面吹牛胎食，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播允懂，決...
沈念sama閱讀 40,032評(píng)論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼厕怜，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了蕾总？” 一聲冷哼從身側(cè)響起粥航，我...
開(kāi)封第一講書(shū)人閱讀 38,896評(píng)論 0贊 274
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎生百，沒(méi)想到半個(gè)月后递雀，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,311評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡蚀浆，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,536評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年缀程，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片市俊。...
茶點(diǎn)故事閱讀 39,696評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡杨凑，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出摆昧，到底是詐尸還是另有隱情撩满，我是刑警寧澤，帶...
沈念sama閱讀 35,413評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布据忘，位于F島的核電站鹦牛，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏勇吊。R本人自食惡果不足惜曼追，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,008評(píng)論 3贊 325
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望汉规。院中可真熱鬧礼殊，春花似錦驹吮、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,659評(píng)論 0贊 22
一樁弒父案碟狞，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至婚陪，卻和暖如春族沃，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背泌参。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,815評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工脆淹，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人沽一。一個(gè)月前我還...
沈念sama閱讀 47,698評(píng)論 2贊 368
代替公主和親
正文我出身青樓盖溺，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親铣缠。傳聞我的和親對(duì)象是個(gè)殘疾皇子烘嘱，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,592評(píng)論 2贊 353