1. 回顧拉格朗日乘數(shù)法

想象一下关霸，目標(biāo)函數(shù)

image.png

是一座山的高度传黄，約束

image.png

是鑲嵌在山上的一條曲線如下圖。

image.png

為了找到曲線上的最低點(diǎn)队寇，就從最低的等高線（0那條）開始網(wǎng)上數(shù)膘掰。數(shù)到第三條，等高線終于和曲線有交點(diǎn)了（如上圖所示）佳遣。因?yàn)楸冗@條等高線低的地方都不在約束范圍內(nèi)识埋，所以這肯定是這條約束曲線的最低點(diǎn)了。
而且約束曲線在這里不可能和等高線相交零渐，一定是相切窒舟。因?yàn)槿绻窍嘟坏脑挘缦聢D所示诵盼，那么曲線一定會(huì)有一部分在B區(qū)域惠豺，但是B區(qū)域比等高線低银还，這是不可能的。

image

兩條曲線相切洁墙，意味著他們在這點(diǎn)的法線平行蛹疯，也就是法向量只差一個(gè)任意的常數(shù)乘子（取為

image.png

：

image.png

, 我們把這個(gè)式子的右邊移到左邊，并把常數(shù)移進(jìn)微分算子热监，就得到

image.png

捺弦。

把這個(gè)式子重新解釋一下，這個(gè)就是函數(shù)

image.png

無約束情況下極值點(diǎn)的充分條件

2. 回顧對偶問題

localdualitytheorem.png

更多信息見
https://www.camdemy.com/media/1585

證明見
http://sma.epfl.ch/~niemeier/opt09/opt09_ch05.pdf
https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture05.pdf

優(yōu)化原問題和其對偶問題

對偶.png

本來是有約束的極值問題孝扛，可以轉(zhuǎn)換為其對偶問題的無約束極值問題
優(yōu)化理論系列1——拉格朗日對偶及強(qiáng)弱定理證明

3. 回顧 Karush-Kuhn-Tucker(KKT)

那么針對不等式的約束如何處理呢列吼？
KKT是用來解釋哪些點(diǎn)是重要的，即找到support vector

KKT1.png

梯度是變化率最大的方向

針對極值x來說苦始，可以看到
g1=0,(active constraint),
g2=0,(active constraint),
g3<0,(inactive constraint),
對于,(active constraint),我們認(rèn)為對于確定極值是有用的寞钥，而(Inactive constraint)我們認(rèn)為對確定極值是沒有用的。
x的梯度方向可以用g1,g2的負(fù)梯度方向來表示盈简。此時(shí)ａ1>0,ａ2>0.
若將x*的梯度方向可以用g1,g2的負(fù)梯度方向和g3的梯度方向來表示凑耻，則此時(shí)ａ1>0,ａ2>0，ａ3=0.
也就是說針對哪些有用的active constraint柠贤，他們的拉格朗日系數(shù)大于零香浩，而針對哪些無用的inactive constraint,他們的拉格朗日系統(tǒng)等于0.

KKT2.png

由三式可知，若拉格朗日系數(shù)ａ>0臼勉，則相應(yīng)的g=0,即為active constraint邻吭，為有用的約束，也就是這些約束點(diǎn)為支撐向量點(diǎn)宴霸，落在g=0上囱晴。
若g<0,則ａ＝0，即為inactive constraint瓢谢，無用的約束畸写，則這些點(diǎn)不是支撐向量點(diǎn)。

4. Feature mapping

特征映射從低維空間映射到高維空間氓扛，便于“線性可分”

kernel.png

kerneltype.png

5. SVM的思想起源

在感知機(jī)模型中枯芬，我們可以找到多個(gè)可以分類的超平面將數(shù)據(jù)分開，并且優(yōu)化時(shí)希望所有的點(diǎn)都離超平面遠(yuǎn)采郎。但是實(shí)際上離超平面很遠(yuǎn)的點(diǎn)已經(jīng)被正確分類千所，我們讓它離超平面更遠(yuǎn)并沒有意義。反而我們最關(guān)心是那些離超平面很近的點(diǎn)淫痰，這些點(diǎn)很容易被誤分類。如果我們可以讓離超平面比較近的點(diǎn)盡可能的遠(yuǎn)離超平面待错，那么我們的分類效果會(huì)好有一些烛占。

支持向量機(jī)(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的沟启，它在解決小樣本德迹、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢芽卿，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。

svm1.png

找到對局部擾動(dòng)“容忍”性最好的超平面是最優(yōu)超平面胳搞。

6. Hard-Margin

large-margin.png

optimization.png

lagrange.png

Kernel Lagrange

kernellagrange.png

dual.png

dual2.png

dual3.png

Quadratic Problem

quadraticproblem.png

kkt.png

kkt2.png

supportvectors.png

rbf.png

How to find "b"

b.png

newtest.png

7. Soft-Margin:

容忍一些誤差卸例，也就是說一些樣本會(huì)落在最大間隔兩邊支持向量邊界的內(nèi)部。
overfitting的問題肌毅，小樣本容易出現(xiàn)overfitting筷转，樣本不具備代表性。

problem1.png

problem2.png

softoptimization.png

softlagrange.png

softkernel.png

softdual.png

softdual1.png

softdual2.png

softdual3.png

softktt.png

softktt1.png

softktt2.png

softrbf.png

softb.png

svm1.png

losshingle.png

svmhingleloss.png

scikit-learn 支持向量機(jī)算法庫使用小結(jié)

支持向量機(jī)高斯核調(diào)參小結(jié)

本文從實(shí)踐的角度對scikit-learn SVM算法庫的使用做一個(gè)小結(jié)悬而。scikit-learn SVM算法庫封裝了libsvm 和 liblinear 的實(shí)現(xiàn)呜舒，僅僅重寫了算法了接口部分。

scikit-learn SVM算法庫使用概述

scikit-learn中SVM的算法庫分為兩類笨奠，一類是分類的算法庫袭蝗，包括SVC， NuSVC般婆，和LinearSVC 3個(gè)類到腥。另一類是回歸算法庫，包括SVR蔚袍， NuSVR乡范，和LinearSVR 3個(gè)類。相關(guān)的類都包裹在sklearn.svm模塊之中页响。

對于SVC篓足， NuSVC，和LinearSVC 3個(gè)分類的類闰蚕，SVC和 NuSVC差不多栈拖，區(qū)別僅僅在于對損失的度量方式不同，而LinearSVC從名字就可以看出没陡，他是線性分類涩哟，也就是不支持各種低維到高維的核函數(shù)索赏，僅僅支持線性核函數(shù)，對線性不可分的數(shù)據(jù)不能使用贴彼。

同樣的潜腻，對于SVR， NuSVR器仗，和LinearSVR 3個(gè)回歸的類融涣， SVR和NuSVR差不多，區(qū)別也僅僅在于對損失的度量方式不同精钮。LinearSVR是線性回歸威鹿，只能使用線性核函數(shù)。

我們使用這些類的時(shí)候轨香，如果有經(jīng)驗(yàn)知道數(shù)據(jù)是線性可以擬合的忽你，那么使用LinearSVC去分類或者LinearSVR去回歸，它們不需要我們?nèi)ヂ恼{(diào)參去選擇各種核函數(shù)以及對應(yīng)參數(shù)臂容，速度也快科雳。如果我們對數(shù)據(jù)分布沒有什么經(jīng)驗(yàn)，一般使用SVC去分類或者SVR去回歸脓杉，這就需要我們選擇核函數(shù)以及對核函數(shù)調(diào)參了糟秘。

什么特殊場景需要使用NuSVC分類和 NuSVR 回歸呢？如果我們對訓(xùn)練集訓(xùn)練的錯(cuò)誤率或者說支持向量的百分比有要求的時(shí)候丽已，可以選擇NuSVC分類和 NuSVR 蚌堵。它們有一個(gè)參數(shù)來控制這個(gè)百分比。

這些類的詳細(xì)使用方法我們在下面再詳細(xì)講述沛婴。

回顧SVM分類算法和回歸算法

svm.png

svm2.png

SVM核函數(shù)概述

在scikit-learn中吼畏，內(nèi)置的核函數(shù)一共有4種，當(dāng)然如果你認(rèn)為線性核函數(shù)不算核函數(shù)的話嘁灯，那就只有三種泻蚊。

1）線性核函數(shù)（Linear Kernel）表達(dá)式為：K(x,z)=x?z

，就是普通的內(nèi)積丑婿，LinearSVC 和 LinearSVR 只能使用它性雄。

2) 多項(xiàng)式核函數(shù)（Polynomial Kernel）是線性不可分SVM常用的核函數(shù)之一，表達(dá)式為：K(x,z)=（γx?z+r)d
羹奉，其中秒旋，γ,r,d

都需要自己調(diào)參定義,比較麻煩。

3）高斯核函數(shù)（Gaussian Kernel）诀拭，在SVM中也稱為徑向基核函數(shù)（Radial Basis Function,RBF）迁筛，它是libsvm默認(rèn)的核函數(shù)，當(dāng)然也是scikit-learn默認(rèn)的核函數(shù)耕挨。表達(dá)式為：K(x,z)=exp(γ||x?z||2)
细卧，其中尉桩，γ

大于0，需要自己調(diào)參定義贪庙。

4）Sigmoid核函數(shù)（Sigmoid Kernel）也是線性不可分SVM常用的核函數(shù)之一蜘犁，表達(dá)式為：K(x,z)=tanh（γx?z+r)
，其中止邮，γ,r

都需要自己調(diào)參定義这橙。

一般情況下，對非線性數(shù)據(jù)使用默認(rèn)的高斯核函數(shù)會(huì)有比較好的效果农尖，如果你不是SVM調(diào)參高手的話析恋，建議使用高斯核來做數(shù)據(jù)分析。

SVM分類算法庫參數(shù)小結(jié)

svmp1.png

svmp2.png

svmp3.png

SVM回歸算法庫參數(shù)小結(jié)

svmr.png

svmr1.png

SVM算法庫其他調(diào)參要點(diǎn)

上面已經(jīng)對scikit-learn中類庫的參數(shù)做了總結(jié)盛卡，這里對其他的調(diào)參要點(diǎn)做一個(gè)小結(jié)。

1）一般推薦在做訓(xùn)練之前對數(shù)據(jù)進(jìn)行歸一化筑凫，當(dāng)然測試集中的數(shù)據(jù)也需要?dú)w一化滑沧。。
　　　　2）在特征數(shù)非常多的情況下巍实，或者樣本數(shù)遠(yuǎn)小于特征數(shù)的時(shí)候滓技，使用線性核，效果已經(jīng)很好棚潦，并且只需要選擇懲罰系數(shù)C即可令漂。
　　　　3）在選擇核函數(shù)時(shí)，如果線性擬合不好丸边，一般推薦使用默認(rèn)的高斯核'rbf'叠必。這時(shí)我們主要需要對懲罰系數(shù)C和核函數(shù)參數(shù)γ 進(jìn)行艱苦的調(diào)參，通過多輪的交叉驗(yàn)證選擇合適的懲罰系數(shù)C和核函數(shù)參數(shù)γ妹窖。
　　　　4）理論上高斯核不會(huì)比線性核差纬朝，但是這個(gè)理論卻建立在要花費(fèi)更多的時(shí)間來調(diào)參上。所以實(shí)際上能用線性核解決問題我們盡量使用線性核骄呼。

SVM調(diào)參

SVM模型有兩個(gè)非常重要的參數(shù)C與gamma共苛。其中 C是懲罰系數(shù)，即對誤差的寬容度蜓萄。c越高隅茎，說明越不能容忍出現(xiàn)誤差,容易過擬合。C越小嫉沽，容易欠擬合辟犀。C過大或過小，泛化能力變差耻蛇。

gamma是選擇RBF函數(shù)作為kernel后踪蹬，該函數(shù)自帶的一個(gè)參數(shù)胞此。隱含地決定了數(shù)據(jù)映射到新的特征空間后的分布，gamma越大跃捣，支持向量越少漱牵，gamma值越小，支持向量越多疚漆。支持向量的個(gè)數(shù)影響訓(xùn)練與預(yù)測的速度酣胀。

此外大家注意RBF公式里面的sigma和gamma的關(guān)系如下：

image

這里面大家需要注意的就是gamma的物理意義，大家提到很多的RBF的幅寬娶聘，它會(huì)影響每個(gè)支持向量對應(yīng)的高斯的作用范圍闻镶，從而影響泛化性能。如果gamma設(shè)的太大丸升，

image.png

會(huì)很小铆农，

image

很小的高斯分布長得又高又瘦，會(huì)造成只會(huì)作用于支持向量樣本附近狡耻，對于未知樣本分類效果很差墩剖，存在訓(xùn)練準(zhǔn)確率可以很高，(如果讓

image

無窮小夷狰，則理論上岭皂，高斯核的SVM可以擬合任何非線性數(shù)據(jù)，但容易過擬合)而測試準(zhǔn)確率不高的可能沼头，就是通常說的過訓(xùn)練爷绘；而如果設(shè)的過小，則會(huì)造成平滑效應(yīng)太大进倍，無法在訓(xùn)練集上得到特別高的準(zhǔn)確率土至，也會(huì)影響測試集的準(zhǔn)確率。

rbf實(shí)際是記憶了若干樣例背捌，在sv中各維權(quán)重重要性等同毙籽。線性核學(xué)出的權(quán)重是feature weighting作用或特征選擇

隨機(jī)搜索Random search與網(wǎng)格搜Grid search

在沙堆上淘金,把沙堆按比例分成格子，淘了一格再去淘下一格毡庆，這是網(wǎng)格搜索坑赡。網(wǎng)格搜索其實(shí)可以理解成暴力搜索，一般當(dāng)超參數(shù)的數(shù)目稍小的時(shí)候(三四個(gè)或者更少的超參數(shù))么抗，才會(huì)用網(wǎng)格搜索.當(dāng)超參數(shù)的數(shù)量增長時(shí)毅否，網(wǎng)格搜索的計(jì)算復(fù)雜度會(huì)呈現(xiàn)指數(shù)增長.，用戶列出一個(gè)較小的超參數(shù)值域蝇刀，這些超參數(shù)值域的笛卡爾集（排列組合）為一組組超參數(shù)螟加。網(wǎng)格搜索算法使用每組超參數(shù)訓(xùn)練模型并挑選驗(yàn)證集誤差最小的超參數(shù)組合。
3.2. Tuning the hyper-parameters of an estimator
在沙堆上淘金，閉上眼睛每次隨便選個(gè)方向走捆探，每次再隨便選個(gè)步數(shù)然爆，走到這步數(shù)就停下來淘一把，這是隨機(jī)搜索黍图。隨機(jī)搜索一般會(huì)根據(jù)超參數(shù)的邊緣分布采樣曾雕。為每個(gè)參數(shù)定義了一個(gè)分布函數(shù)并在該空間中采樣（sampling）.
Bergstra, J. and Bengio, Y., Random search for hyper-parameter optimization, The Journal of Machine Learning Research (2012)

優(yōu)缺點(diǎn)比較：
Randomized Search指數(shù)級高效于Grid Search，因?yàn)镚rid Search將大量的計(jì)算浪費(fèi)在了指數(shù)級的對結(jié)果無影響的參數(shù)中助被，而Randomized Search幾乎每次都搜索了對結(jié)果有影響的參數(shù)的值剖张。
Grid Search網(wǎng)格搜索可以得到全局最優(yōu), (C,gamma)相互獨(dú)立，便于并行化進(jìn)行

關(guān)于深度學(xué)習(xí)中超參數(shù)優(yōu)化方法中的隨機(jī)搜索和網(wǎng)格搜索的解釋揩环？

SVM的兩個(gè)參數(shù) C 和 gamma

# -*- coding: UTF-8 -*-
from __future__ import division
#from __future__ import print_function
print("0. import dependency----------------------------------------------")


from sklearn.model_selection import validation_curve
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import LabelEncoder
from sklearn.model_selection import GridSearchCV
from sklearn.model_selection import RandomizedSearchCV
from sklearn.svm import SVC
from sklearn.ensemble import RandomForestClassifier
from scipy.stats import randint as sp_randint # 用于產(chǎn)生隨機(jī)分布的整數(shù)


# 使用隨機(jī)搜索,使用SVM分類器
def RS_SVM(X_train, y_train):
    # 構(gòu)造模型
    pipe_svc = Pipeline([('scl', StandardScaler()),
                         ('clf', SVC(random_state=1))])
    param_range = [10 ** c for c in range(-4, 4)]
    param_dist = {  #  對于核SVM則需要同時(shí)調(diào)優(yōu)C和gamma值
        'clf__C': param_range,
        'clf__gamma': param_range,
        'clf__kernel': ['linear', 'rbf']
    }

    # run randomized search
    n_iter_search = 20
    random_search = RandomizedSearchCV(pipe_svc,
                                       param_distributions=param_dist,
                                       n_iter=n_iter_search)
    random_search.fit(X_train, y_train)
    report(random_search.cv_results_)

    return random_search.best_estimator_


# 使用網(wǎng)格搜索,使用SVM分類器
def GS_SVM(X_train, y_train):
    # 構(gòu)造模型
    pipe_svc = Pipeline([('scl', StandardScaler()),
                         ('clf', SVC(random_state=1))])

    param_range = [10**c for c in range(-4, 4)]
    # param_range = np.linspace(0.0001, 1, 10)

    param_grid = [
        {'clf__C': param_range, 'clf__kernel': ['linear']}, # 對于線性SVM只需要調(diào)優(yōu)正則化參數(shù)C
        {'clf__C': param_range, 'clf__gamma': param_range, 'clf__kernel': ['rbf']}   #  對于核SVM則需要同時(shí)調(diào)優(yōu)C和gamma值
    ]

    gs = GridSearchCV(estimator=pipe_svc,
                      param_grid=param_grid,
                      scoring='accuracy',
                      cv=10,
                      n_jobs=-1)
    gs = gs.fit(X_train, y_train)
    # print(gs.best_score_)
    # print(gs.best_params_)

    # 使用最優(yōu)模型進(jìn)行性能評估
    # clf = gs.best_estimator_
    # clf.fit(X_train, y_train)
    # print('Test Accuracy: %.3f' % clf.score(X_test, y_test))

    report(gs.cv_results_)

    return gs.best_estimator_

[讀書筆記] 《Python 機(jī)器學(xué)習(xí)》 - 使用RandomParameterOpt與GridSearch進(jìn)行超參調(diào)整