六喉前、坐標(biāo)軸下降法
回顧： 當(dāng)加入L1正則項(xiàng)后哩掺，由于沒(méi)法求解出正常的導(dǎo)函數(shù)出來(lái)(導(dǎo)函數(shù)不是連續(xù)的)垄懂，也就沒(méi)法使用梯度下降法和擬牛頓法求解參數(shù)虚汛，此時(shí)一般采用坐標(biāo)軸下降法來(lái)進(jìn)行參數(shù)的求解围来。
坐標(biāo)軸下降法(Coordinate Descent， CD)是一種迭代法才漆，通過(guò)啟發(fā)式的方法一步步的迭代求解函數(shù)的最小值牛曹，和梯度下降法(GD)不同的時(shí)候，坐標(biāo)軸下降法是沿著坐標(biāo)軸的方向去下降醇滥，而不是采用梯度的負(fù)方向下降黎比。
令損失函數(shù) f(x.y) = 5x2-6xy+5y2-0.0259;
1、假設(shè)初始點(diǎn)為(-0.5,-1)鸳玩，代入公式f(x.y)后會(huì)有一個(gè)對(duì)應(yīng)的值阅虫。
2、現(xiàn)在固定住 x= -0.5不跟，讓y不斷變化：(-0.5,-1)颓帝，(-0.5,1)，(-0.5,2)窝革，(-0.5,3) ...
3购城、不斷根據(jù)y值的變化，檢索 f(x.y)的最小值虐译。
4瘪板、固定x，求解得到y(tǒng)值漆诽。（EM思想）
綠色點(diǎn)所在的位置侮攀，是隨著y變化后能夠與目標(biāo)函數(shù)f(x,y)相切的點(diǎn)。這個(gè)點(diǎn)是當(dāng)前情況下的最小值厢拭。那么如何求圖上的這個(gè)綠點(diǎn)的位置兰英？
首先，我們固定了x=-0.5蚪腐，即在損失函數(shù) f(x.y) = 5x2-6xy+5y2-0.0259;中箭昵， 5x2、-6x都成了常數(shù)C回季；
-0.0259和5x2都是常數(shù)家制，合并到了一起變成C正林；
即 f(y) = C+3y+5y2；
然后颤殴，分析 f(y)處于極小值點(diǎn)時(shí)觅廓，y的值是多少？
y=-2a/b時(shí)獲得涵但。即 y=-2*5/3 = -10/3 ≈ -0.3杈绸；
PS： 這些是初中的知識(shí)，很多人希望我對(duì)這方面知識(shí)也進(jìn)行補(bǔ)充矮瘟，但個(gè)人時(shí)間有限這部分知識(shí)也不難理解瞳脓，各位可以自行學(xué)習(xí)補(bǔ)充。我所講的內(nèi)容適合學(xué)過(guò)高等數(shù)學(xué)澈侠、線(xiàn)性代數(shù)劫侧、概率論，并具有初步編程知識(shí)的同行哨啃，在學(xué)術(shù)方面有疑問(wèn)的不要立刻開(kāi)噴烧栋，有針對(duì)性得提出問(wèn)題，我相信都是可以幫助大家一一解惑的拳球。
5审姓、固定y，求解得到x值祝峻。（EM思想）
固定y = -0.3魔吐，求解 f(x)取得最小值時(shí)，x的取值莱找。
即 f(x) = C+1.8x+5x2
當(dāng) f(x)取極小值時(shí)画畅，x=-0.18；
重復(fù)4~5步宋距，會(huì)逐步以下圖中的幾何方式尋找到損失函數(shù)的極小值點(diǎn)：
將EM算法的思想運(yùn)用于坐標(biāo)軸下降法，最終結(jié)果會(huì)收斂在綠色點(diǎn)的這個(gè)位置症脂，這個(gè)點(diǎn)是損失函數(shù)的全局極小值點(diǎn)谚赎。
主要坐標(biāo)軸下降法面對(duì)的是一個(gè)凸函數(shù)，必然能找到一個(gè)全局的最小值點(diǎn)诱篷。
坐標(biāo)軸下降法利用EM算法的思想，在參數(shù)更新過(guò)程中棕所，每次均先固定m-1個(gè)參數(shù)值闸盔，求解剩下的一個(gè)參數(shù)的局部最優(yōu)解；然后進(jìn)行迭代式的更新操作琳省。
坐標(biāo)軸下降法的核心思想是多變量函數(shù)F(X)可以通過(guò)每次沿著一個(gè)方向優(yōu)化來(lái)獲取最小值躲撰；其數(shù)學(xué)依據(jù)是：對(duì)于一個(gè)可微凸函數(shù)f(θ)，其中θ為n*1的向量击费。
如果對(duì)于一個(gè)解θ=(θ1,θ2,...,θn)拢蛋，使得f(θ)在每一個(gè)坐標(biāo)軸θi(i=1,2,..,n)上都能達(dá)到最小值，則θ=(θ1,θ2,...,θn)就是的f(θ)全局的最小值點(diǎn)蔫巩。
在坐標(biāo)軸下降法中谆棱，優(yōu)化方向從算法的一開(kāi)始就固定了，即沿著坐標(biāo)的方向進(jìn)行變化圆仔。在算法中垃瞧，循環(huán)最小化各個(gè)坐標(biāo)方向的目標(biāo)函數(shù)。 即：如果xk給定坪郭，那么xk+1的第i維度為:
因此个从，從一個(gè)初始的x0求得函數(shù)F(x)的局部最優(yōu)解，可以迭代獲取x0截粗、x1信姓、x2... 的序列，從而可以得到:
七绸罗、坐標(biāo)軸下降法算法過(guò)程
- 給θ向量隨機(jī)選取一個(gè)初值意推，記做θ0；
- 對(duì)于第k輪的迭代珊蟀，從θ1k開(kāi)始計(jì)算菊值，θnk到為止，計(jì)算公式如下：
檢查θk和θk-1向量在各個(gè)維度上的變化情況育灸，如果所有維度的變化情況都比較小的話(huà)腻窒，那么認(rèn)為結(jié)束迭代，否則繼續(xù)k+1輪的迭代磅崭。
PS：在求解每個(gè)參數(shù)局部最優(yōu)解的時(shí)候可以求導(dǎo)的方式來(lái)求解儿子。
坐標(biāo)軸下降法和梯度下降法的區(qū)別
坐標(biāo)軸下降法在每次迭代中，計(jì)算當(dāng)前點(diǎn)處沿一個(gè)坐標(biāo)方向進(jìn)行一維搜索 砸喻，固定其它維度的坐標(biāo)方向柔逼，找到一個(gè)函數(shù)的局部極小值。而梯度下降總是沿著梯度的負(fù)方向求函數(shù)的局部最小值割岛；
坐標(biāo)軸下降優(yōu)化方法是一種非梯度優(yōu)化算法愉适。在整個(gè)過(guò)程中依次循環(huán)使用不同的坐標(biāo)方向進(jìn)行迭代，一個(gè)周期的一維搜索迭代過(guò)程相當(dāng)于一個(gè)梯度下降的迭代癣漆；
梯度下降是利用目標(biāo)函數(shù)的導(dǎo)數(shù)來(lái)確定搜索方向的维咸，該梯度方向可能不與任何坐標(biāo)軸平行。而坐標(biāo)軸下降法是利用當(dāng)前坐標(biāo)方向進(jìn)行搜索，不需要求目標(biāo)函數(shù)的導(dǎo)數(shù)癌蓖，只按照某一坐標(biāo)方向進(jìn)行搜索最小值瞬哼；
兩者都是迭代算法，且每一輪迭代都需要O(mn)的計(jì)算量(m為樣本數(shù)费坊，n為維度數(shù))
回顧上一章對(duì)NMF的定義：
NMF的期望 是找到兩個(gè)W附井、H矩陣讨越，使得WH的矩陣乘積結(jié)果和對(duì)應(yīng)的原矩陣V對(duì)應(yīng)位置的值相比誤差盡可能的小。
分析損失函數(shù)：
在損失函數(shù)中永毅，Vij是原始矩陣把跨。W、H是根據(jù)原始矩陣分解出的兩個(gè)矩陣沼死。
Vij - WH 着逐，類(lèi)似 真實(shí)值-預(yù)測(cè)值 的概念。
NMF 矩陣分解的結(jié)果是非負(fù)的意蛀，所以要求W耸别、H矩陣中的元素 Wia、Hbj 大于等于0县钥；
這和之前講的SMO算法中求解β值的問(wèn)題相似：11 SVM - SMO - 序列最小優(yōu)化算法
這里我們和求解SMO算法的思路一樣，首先假如x1求解出來(lái)的結(jié)果小于0若贮，我們強(qiáng)行認(rèn)為x1=0省有；
留個(gè)懸念，后續(xù)我會(huì)根據(jù)代碼來(lái)深入探討這個(gè)問(wèn)題谴麦。
