距離Lec10更新已經(jīng)過(guò)去三個(gè)半月了，漫長(zhǎng)的考試與寒假……囧！今天終于鼓起勇氣繼續(xù)寫(xiě)下去，正好這學(xué)期有《統(tǒng)計(jì)學(xué)習(xí)方法》課程，結(jié)合著回顧一下。

按照慣例，開(kāi)頭是對(duì)上一節(jié)做出總結(jié)，由于時(shí)間久遠(yuǎn)，就算了……吧。

不過(guò)還是有一點(diǎn)其他東西想講一講。上周剛剛上了第一節(jié)統(tǒng)計(jì)學(xué)習(xí)方法課，基本是在宏觀(guān)上介紹概念，很多名詞和基石課叫法不一樣，聽(tīng)起來(lái)怪怪的，但思想基本一樣，有時(shí)候一下子聯(lián)想不到基石中講過(guò)的具體的知識(shí)點(diǎn)，所以也又想著再回來(lái)回顧一下。

碰巧，去年總結(jié)的最后一個(gè)Lec講了LogReg，里面也提出來(lái)另一種err measure：likelihood。而統(tǒng)計(jì)學(xué)習(xí)方法中是把它與0/1 err、square err并列列出的，沒(méi)有解釋?zhuān)麨椋簩?duì)數(shù)損失函數(shù)or對(duì)數(shù)似然函數(shù)。當(dāng)時(shí)看到的時(shí)候一下子就懵了，想不起具體是什么情況下出現(xiàn)的這個(gè)了，今天回顧才一下子想起來(lái)?，F(xiàn)在只想說(shuō)，難怪都說(shuō)國(guó)內(nèi)的教材看不得?。×幸粋€(gè)式子在那擺著，告訴別人叫什么，看的人如果之前沒(méi)有接觸過(guò)，根本理解不到其中的精髓呀！無(wú)論對(duì)錯(cuò)，就是小感慨一下！其實(shí)老師上課的時(shí)候講概念還是挺嚴(yán)謹(jǐn)生動(dòng)的，舉了很多例子，但是不知道如果我之前沒(méi)有上這門(mén)課聽(tīng)起來(lái)會(huì)是什么感覺(jué)？我猜是一頭霧水，只是被灌輸了一堆概念而不得其真意吧~！

下面回到正題，囧………………

Lec11： Linear Models for Classification

這節(jié)主要回顧三個(gè)線(xiàn)性模型，并對(duì)比講解之間的聯(lián)系。還會(huì)進(jìn)一步介紹如何實(shí)現(xiàn)多分類(lèi)

1、三個(gè)線(xiàn)性模型

先回顧一下三個(gè)線(xiàn)性模型：線(xiàn)性分類(lèi)，線(xiàn)性回歸，邏輯回歸，它們的共同點(diǎn)是都要計(jì)算一個(gè)score。既然它們這么像，而且線(xiàn)性回歸和邏輯回歸的優(yōu)化似乎很容易計(jì)算，那么是不是可以用回歸help分類(lèi)呢？

先再回顧一下各自的error function，這里如果用作二元分類(lèi)，則y取值為{-1,1}，進(jìn)一步將err都整理成 ys 形式。ys有其物理意義，y代表正確性，s代表score，乘積>0則正確，<0則錯(cuò)誤。

這三個(gè)err函數(shù)畫(huà)圖，發(fā)現(xiàn)

至此，再在ce err上動(dòng)點(diǎn)手腳，scale一下，變ln為log2：

這樣三條線(xiàn)關(guān)系如下，可以看出，sqr小的時(shí)候那么0/1也會(huì)??；scaled ce 與 0/1 相切；這兩個(gè)線(xiàn)都在0/1err的上面，恩，這是用回歸做分類(lèi)的關(guān)鍵！upper bound！

使用upper bound在圖上看很直接，理論上也很好理解，就是最小化0/1 err的上限，那么0/1 err也會(huì)小，所以可以用回歸來(lái)做分類(lèi)，算法為：

使用線(xiàn)性回歸和邏輯回歸的好處是優(yōu)化簡(jiǎn)單，弊端是loose bound：

通常實(shí)際中，使用線(xiàn)性回歸計(jì)算出來(lái)的w做為初始值w0，然后再進(jìn)行PLA、pocket、邏輯回歸；

此外，通常邏輯回歸 prefer “pocket”，其實(shí)它們?cè)趦?yōu)化過(guò)程中每一步的工作差不多……

2、Iterative Optimization方案 & 隨機(jī)梯度下降（SGD）

前面已經(jīng)介紹過(guò)PLA和梯度下降，都是迭代優(yōu)化方法。

在PLA種，每一輪只選一個(gè)錯(cuò)誤點(diǎn)更新w，復(fù)雜度是 O（1）；而在LogReg的梯度下降方法中， 每一輪更新要把每一個(gè)點(diǎn)都要計(jì)算進(jìn)去，復(fù)雜度是O（N）；那么在梯度下降方法中，能不能做到每一輪更新的復(fù)雜度是O（1）呢？可以的：

回顧一下梯度下降中的迭代式子：

目標(biāo)：計(jì)算direction時(shí)只使用一個(gè)點(diǎn)，而不是全部的（x，y）

技巧：把 ∑部分看做是期望，用隨機(jī)選取一個(gè)點(diǎn)（xn，yn）計(jì)算的梯度取代梯度的期望值，稱(chēng)為隨機(jī)梯度。

也可以把隨機(jī)梯度看做是 true gradient + noise gradient，隨機(jī)梯度下降法如下。其實(shí)在經(jīng)過(guò)足夠多步以后，隨機(jī)梯度的平均和真實(shí)梯度的平均是接近的 ，這個(gè)類(lèi)似隨機(jī)抽樣。這樣會(huì)使計(jì)算簡(jiǎn)單高效，尤其是在data很大 以及 online learning（data是一個(gè)一個(gè)的in）。但這種方法會(huì)不太穩(wěn)定，尤其是當(dāng)η較大時(shí)，很可能會(huì)“一步踏空”。

將SGD用在LogReg上面：

這個(gè)式子更新跟（yx）有關(guān)，是和什么相似呢？PLA！回顧again：

PLA是用前面部分控制有錯(cuò)的時(shí)候更新，沒(méi)錯(cuò)的時(shí)候不更新。這樣，其實(shí)SGD LogReg就可以看成是soft PLA，這時(shí)不是有錯(cuò)更新，而是錯(cuò)的多一點(diǎn)就多更新一點(diǎn)，錯(cuò)的少一點(diǎn)就少更新一點(diǎn)。反過(guò)來(lái)看，如果WtXn很大，η=1時(shí)，其實(shí)θ（）要么接近0要么接近1，PLA ≈ SGD 。雖然如此，但是在實(shí)際應(yīng)用中要注意兩點(diǎn)：一是SGD何時(shí)停下？梯度等于0嗎？不，否則省的計(jì)算就白省了，一般 t 夠大就停止；而是η的取值，經(jīng)驗(yàn)上0.1126是不錯(cuò)的選擇。后面會(huì)介紹取值選擇方法。

3、多分類(lèi)

下面介紹多類(lèi)別分類(lèi)，從是非題到選擇題的轉(zhuǎn)變，從二元分類(lèi)延伸到多類(lèi)別……

這里介紹兩種思路：one vs all 和 one vs one。

第一種one vs all（OVA）：

每次還是做二元分類(lèi)，比如先把方塊和其他分開(kāi)；再把菱形和其他分開(kāi)……最后組合四個(gè)分類(lèi)器，得到下圖?？梢钥闯銎鋵?shí)會(huì)有兩個(gè)問(wèn)題：有些區(qū)域重疊，分類(lèi)器會(huì)互相爭(zhēng)搶?zhuān)挥行﹨^(qū)域未被分類(lèi)器覆蓋。分類(lèi)器總是會(huì)犯錯(cuò)的…………

那么怎么辦呢？softly classification，使用LogReg計(jì)算可能性，選擇可能性最大的類(lèi)別作為分類(lèi)結(jié)果！實(shí)際上，score越大可能性也就越大，直接比較score就可以了。組合起來(lái)：

這里是拿LogReg做例子，實(shí)際上只要是輸出值可以比大小的算法都可以用在OVA上面。

雖然這種方法是最簡(jiǎn)單基本的多分類(lèi)方法，效率很高，但是數(shù)據(jù)會(huì)經(jīng)常unbalanced：比如 o 很少，而 × 非常多的時(shí)候，如果把所有data都分為 × 就可以做的很好。下面方法可以解決這個(gè)問(wèn)題……

第二種 one vs one（OVO ）：

方塊跟菱形分類(lèi)，再方塊跟三角形分類(lèi)…………有4個(gè)分類(lèi)，4選2，共有6種分類(lèi)問(wèn)題。最后如何根據(jù)6個(gè)分類(lèi)器決定最后的結(jié)果呢？4個(gè)類(lèi)別打了6場(chǎng)循環(huán)賽，贏(yíng)得最多的類(lèi)別勝出。如：前三個(gè)分類(lèi)器都把某個(gè)data分類(lèi)為方塊，第四個(gè)分為菱形，第五個(gè)分為星星，第六個(gè)說(shuō)比較像星星，最后方塊勝出！

這個(gè)方法也很有效率（每一輪的問(wèn)題規(guī)模較小），更穩(wěn)定也可以跟任何的二元分類(lèi)算法搭配。缺點(diǎn)是O（k平方），預(yù)測(cè)時(shí)間長(zhǎng)，空間復(fù)雜度大，需要訓(xùn)練更多的分類(lèi)器。

OVO也是很簡(jiǎn)單的多分類(lèi)算法，尤其是類(lèi)別不是很多的時(shí)候還是很好用的。

（還沒(méi)從假期綜合癥中清醒過(guò)來(lái)，寫(xiě)的不細(xì)致，好在問(wèn)題比較簡(jiǎn)單……就這樣了）