<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 11 -- Linear Models for Classification 上一節課,我們介紹了Logistic Regression問題,建立cross-entropy error,并提出使用梯度下降算法gradient descnt來獲得最好的logistic hypothesis。本節課繼續介紹使用線性模型來解決分類問題。 ### **一、Linear Models for Binary Classification** 之前介紹幾種線性模型都有一個共同點,就是都有樣本特征x的加權運算,我們引入一個線性得分函數s: 三種線性模型,第一種是linear classification。線性分類模型的hypothesis為![](https://img.kancloud.cn/ab/a6/aba626de8d652cf3f7ad0be019e51487_104x18.jpg),取值范圍為{-1,+1}兩個值,它的err是0/1的,所以對應的![](https://img.kancloud.cn/38/c5/38c5fb73e6a2346c8d7a29e992a7421c_48x18.jpg)是離散的,并不好解,這是個NP-hard問題。第二種是linear regression。線性回歸模型的hypothesis為![](https://img.kancloud.cn/aa/c7/aac77e05910407ded2dd73b9afc7722b_60x18.jpg),取值范圍為整個實數空間,它的err是squared的,所以對應的![](https://img.kancloud.cn/38/c5/38c5fb73e6a2346c8d7a29e992a7421c_48x18.jpg)是開口向上的二次曲線,其解是closed-form的,直接用線性最小二乘法求解即可。第三種是logistic regression。邏輯回歸模型的hypothesis為![](https://img.kancloud.cn/4c/9c/4c9c0dcaf18968131d56df27f160c6ee_80x18.jpg),取值范圍為(-1,1)之間,它的err是cross-entropy的,所有對應的![](https://img.kancloud.cn/38/c5/38c5fb73e6a2346c8d7a29e992a7421c_48x18.jpg)是平滑的凸函數,可以使用梯度下降算法求最小值。 ![這里寫圖片描述](https://img.kancloud.cn/7f/ed/7fed7bc8ba38bb6ae551f4791d48db37_566x210.jpg) 從上圖中,我們發現,linear regression和logistic regression的error function都有最小解。那么可不可以用這兩種方法來求解linear classification問題呢?下面,我們來對這三種模型的error function進行分析,看看它們之間有什么聯系。 對于linear classification,它的error function可以寫成: 對于linear regression,它的error function可以寫成: 對于logistic regression,它的error function可以寫成: 上述三種模型的error function都引入了ys變量,那么ys的物理意義是什么?ys就是指分類的正確率得分,其值越大越好,得分越高。 ![這里寫圖片描述](https://img.kancloud.cn/ff/50/ff50c9d9ee37ec8c0ddede3c87c4db62_566x252.jpg) 下面,我們用圖形化的方式來解釋三種模型的error function到底有什么關系: ![這里寫圖片描述](https://img.kancloud.cn/7b/9e/7b9ef65021454ddf9864157741b57e39_566x330.jpg) 從上圖中可以看出,ys是橫坐標軸,![](https://img.kancloud.cn/e0/44/e044308c73d4b4eac418bac8fd3a5a82_39x13.jpg)是呈階梯狀的,在ys&gt;0時,![](https://img.kancloud.cn/e0/44/e044308c73d4b4eac418bac8fd3a5a82_39x13.jpg)恒取最小值0。![](https://img.kancloud.cn/a0/b3/a0b31fbc4643e27f3bf72823366768e1_48x12.jpg)呈拋物線形式,在ys=1時,取得最小值,且在ys=1左右很小區域內,![](https://img.kancloud.cn/e0/44/e044308c73d4b4eac418bac8fd3a5a82_39x13.jpg)和![](https://img.kancloud.cn/a0/b3/a0b31fbc4643e27f3bf72823366768e1_48x12.jpg)近似。![](https://img.kancloud.cn/10/15/10155896527ea6410125cee04910d6e5_41x10.jpg)是呈指數下降的單調函數,ys越大,其值越小。同樣在ys=1左右很小區域內,![](https://img.kancloud.cn/e0/44/e044308c73d4b4eac418bac8fd3a5a82_39x13.jpg)和![](https://img.kancloud.cn/10/15/10155896527ea6410125cee04910d6e5_41x10.jpg)近似。但是我們發現![](https://img.kancloud.cn/10/15/10155896527ea6410125cee04910d6e5_41x10.jpg)并不是始終在![](https://img.kancloud.cn/e0/44/e044308c73d4b4eac418bac8fd3a5a82_39x13.jpg)之上,所以為了計算討論方便,我們把![](https://img.kancloud.cn/10/15/10155896527ea6410125cee04910d6e5_41x10.jpg)做幅值上的調整,引入![](https://img.kancloud.cn/6e/4f/6e4f665778c74d3f54e60f142c4053b0_295x35.jpg),這樣能保證![](https://img.kancloud.cn/de/cd/decdaaa37689750c739b2b641e6d6dd8_48x10.jpg)始終在![](https://img.kancloud.cn/e0/44/e044308c73d4b4eac418bac8fd3a5a82_39x13.jpg)上面,如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/b1/30/b130fccb088e2c438136e4d4bd7add2a_566x330.jpg) 由上圖可以看出: 那么由VC理論可以知道: 從0/1出發: 從CE出發: ![這里寫圖片描述](https://img.kancloud.cn/8a/94/8a94596c7b2eec5633a454af04d00e42_566x367.jpg) 通過上面的分析,我們看到err 0/1是被限定在一個上界中。這個上界是由logistic regression模型的error function決定的。而linear regression其實也是linear classification的一個upper bound,只是隨著sy偏離1的位置越來越遠,linear regression的error function偏差越來越大。綜上所述,linear regression和logistic regression都可以用來解決linear classification的問題。 下圖列舉了PLA、linear regression、logistic regression模型用來解linear classification問題的優點和缺點。通常,我們使用linear regression來獲得初始化的![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg),再用logistic regression模型進行最優化解。 ![這里寫圖片描述](https://img.kancloud.cn/7b/bb/7bbbee71f5a5e953aae75b3fe2b54be1_566x292.jpg) ### **二、Stochastic Gradient Descent** 之前介紹的PLA算法和logistic regression算法,都是用到了迭代操作。PLA每次迭代只會更新一個點,它每次迭代的時間復雜度是O(1);而logistic regression每次迭代要對所有N個點都進行計算,它的每時間復雜度是O(N)。為了提高logistic regression中gradient descent算法的速度,可以使用另一種算法:隨機梯度下降算法(Stochastic Gradient Descent)。 隨機梯度下降算法每次迭代只找到一個點,計算該點的梯度,作為我們下一步更新w的依據。這樣就保證了每次迭代的計算量大大減小,我們可以把整體的梯度看成這個隨機過程的一個期望值。 ![這里寫圖片描述](https://img.kancloud.cn/90/1a/901a13d730b7f11d046118b6d48a39ff_566x360.jpg) 隨機梯度下降可以看成是真實的梯度加上均值為零的隨機噪聲方向。單次迭代看,好像會對每一步找到正確梯度方向有影響,但是整體期望值上看,與真實梯度的方向沒有差太多,同樣能找到最小值位置。隨機梯度下降的優點是減少計算量,提高運算速度,而且便于online學習;缺點是不夠穩定,每次迭代并不能保證按照正確的方向前進,而且達到最小值需要迭代的次數比梯度下降算法一般要多。 ![這里寫圖片描述](https://img.kancloud.cn/79/d6/79d6bbcf981a01e8cbf7b3c2ccfa75e8_566x174.jpg) 對于logistic regression的SGD,它的表達式為: 我們發現,SGD與PLA的迭代公式有類似的地方,如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/f7/5c/f75c31f73720a5e3d7a557ce5da73024_566x132.jpg) 我們把SGD logistic regression稱之為’soft’ PLA,因為PLA只對分類錯誤的點進行修正,而SGD logistic regression每次迭代都會進行或多或少的修正。另外,當![](https://img.kancloud.cn/8d/50/8d502b471c77d4535bbf91eb97e0fda6_38x15.jpg),且![](https://img.kancloud.cn/f6/88/f6887809b6229fa2da28481b265c0a75_38x18.jpg)足夠大的時候,PLA近似等于SGD。 ![這里寫圖片描述](https://img.kancloud.cn/ee/e1/eee10a912766138933a7175d4c6617e8_566x59.jpg) 除此之外,還有兩點需要說明:1、SGD的終止迭代條件。沒有統一的終止條件,一般讓迭代次數足夠多;2、學習速率![](https://img.kancloud.cn/fa/a8/faa8fa58ba31bedd69c7f03b2b3885e9_9x10.jpg)。![](https://img.kancloud.cn/fa/a8/faa8fa58ba31bedd69c7f03b2b3885e9_9x10.jpg)的取值是根據實際情況來定的,一般取值0.1就可以了。 ### **三、Multiclass via Logistic Regression** 之前我們一直講的都是二分類問題,本節主要介紹多分類問題,通過linear classification來解決。假設平面上有四個類,分別是正方形、菱形、三角形和星形,如何進行分類模型的訓練呢? 首先我們可以想到這樣一個辦法,就是先把正方形作為正類,其他三種形狀都是負類,即把它當成一個二分類問題,通過linear classification模型進行訓練,得出平面上某個圖形是不是正方形,且只有{-1,+1}兩種情況。然后再分別以菱形、三角形、星形為正類,進行二元分類。這樣進行四次二分類之后,就完成了這個多分類問題。 ![這里寫圖片描述](https://img.kancloud.cn/44/e6/44e601556fee0b061018d54bc41a0e9d_566x378.jpg) 但是,這樣的二分類會帶來一些問題,因為我們只用{-1,+1}兩個值來標記,那么平面上某些可能某些區域都被上述四次二分類模型判斷為負類,即不屬于四類中的任何一類;也可能會出現某些區域同時被兩個類甚至多個類同時判斷為正類,比如某個區域又判定為正方形又判定為菱形。那么對于這種情況,我們就無法進行多類別的準確判斷,所以對于多類別,簡單的binary classification不能解決問題。 針對這種問題,我們可以使用另外一種方法來解決:soft軟性分類,即不用{-1,+1}這種binary classification,而是使用logistic regression,計算某點屬于某類的概率、可能性,去概率最大的值為那一類就好。 soft classification的處理過程和之前類似,同樣是分別令某類為正,其他三類為負,不同的是得到的是概率值,而不是{-1,+1}。最后得到某點分別屬于四類的概率,取最大概率對應的哪一個類別就好。效果如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/00/b9/00b98d4930d15bf47360fbdd6551ae56_566x454.jpg) 這種多分類的處理方式,我們稱之為One-Versus-All(OVA) Decomposition。這種方法的優點是簡單高效,可以使用logistic regression模型來解決;缺點是如果數據類別很多時,那么每次二分類問題中,正類和負類的數量差別就很大,數據不平衡unbalanced,這樣會影響分類效果。但是,OVA還是非常常用的一種多分類算法。 ![這里寫圖片描述](https://img.kancloud.cn/35/e7/35e7f99a3e8450ec8be54f6de5c8fdcc_566x383.jpg) ### **四、Multiclass via Binary Classification** 上一節,我們介紹了多分類算法OVA,但是這種方法存在一個問題,就是當類別k很多的時候,造成正負類數據unbalanced,會影響分類效果,表現不好。現在,我們介紹另一種方法來解決當k很大時,OVA帶來的問題。 這種方法呢,每次只取兩類進行binary classification,取值為{-1,+1}。假如k=4,那么總共需要進行![](https://img.kancloud.cn/c1/63/c163fab93d7992da47b0ea5cf62e6642_49x18.jpg)次binary classification。那么,六次分類之后,如果平面有個點,有三個分類器判斷它是正方形,一個分類器判斷是菱形,另外兩個判斷是三角形,那么取最多的那個,即判斷它屬于正方形,我們的分類就完成了。這種形式就如同k個足球對進行單循環的比賽,每場比賽都有一個隊贏,一個隊輸,贏了得1分,輸了得0分。那么總共進行了![](https://img.kancloud.cn/03/c5/03c5934ce7ddcb7eaa508ffd64fcbff7_19x18.jpg)次的比賽,最終取得分最高的那個隊就可以了。 ![這里寫圖片描述](https://img.kancloud.cn/2f/dc/2fdcb964602a651e97f4d2948f49f32e_566x401.jpg) 這種區別于OVA的多分類方法叫做One-Versus-One(OVO)。這種方法的優點是更加高效,因為雖然需要進行的分類次數增加了,但是每次只需要進行兩個類別的比較,也就是說單次分類的數量減少了。而且一般不會出現數據unbalanced的情況。缺點是需要分類的次數多,時間復雜度和空間復雜度可能都比較高。 ![這里寫圖片描述](https://img.kancloud.cn/2a/ea/2aea7830f4cd2c4fea7a35802135a2ed_566x377.jpg) ### **五、總結** 本節課主要介紹了分類問題的三種線性模型:linear classification、linear regression和logistic regression。首先介紹了這三種linear models都可以來做binary classification。然后介紹了比梯度下降算法更加高效的SGD算法來進行logistic regression分析。最后講解了兩種多分類方法,一種是OVA,另一種是OVO。這兩種方法各有優缺點,當類別數量k不多的時候,建議選擇OVA,以減少分類次數。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看