嶺回歸與Lasso算法:

alpha的作用:調(diào)整正則化權(quán)重

嶺回歸:ridge模塊

from sklearn.linear_model import Ridge

np.random.seed(42)

m=20

X = 3*np.random.rand(m,1)

y = 0.5 *X +np.random.randn(m,1)/1.5 +1

X_new = np.linspace(0,3,100).reshape(100,1)

def plot_model(model_calss,polynomial,alphas,**model kargs):

for alpha,style in zip(alphas,('b-''g--,'r:')):

model = model calss(alpha,**model kargs)

if polynomial:

model = Pipeline([('poly_features',PolynomialFeatures

(degree =10,include bias = False)).('StandardScaler',

StandardScaler()),(’lin_reg', model)])

model.fit(X,y)

y_new_regul = model.predict(X_new)

lw = 2 if alpha > 0 else 1

plt.plot(X new,y new regul,style, linewidth = lw, label = 'alpha = ['.format(alpha))

plt.plot(X,y,'b.,linewidth =3)

plt.lenged0

plt.figure(figsize=(10,5))

plt.subplot(121)

plot model(Ridge,polynomial=False,alphas = (0,10,100))

plt.subplot(122)

plot_model(Ridge,polynomial=True,alphas = (0,10**-5.1))

?

正則化公式:

?

?

?

邏輯回歸優(yōu)化與調(diào)參7:

初始化:將線性回歸__init__拿過來

修改labels=np.unique(labels)

?

num_features = self.data.shape[1]

num_unique_labels = np.unique(labels).shape[0]

self.theta = np.zeros((num_unique_labels,num_features))

?

L1正則與L2正則8:

對原始損失函數(shù)引入額外信息，以便防止過擬合和提高模型泛化性能的一類方法的統(tǒng)稱

中文稱作L1正則化和L2正則化，或者L1范數(shù)和L2范數(shù)（L1實際是L2范數(shù)的平方）。

使用L1正則化的模型叫做Lasso回歸，使用L2正則化的模型叫做Ridge回歸（嶺回歸）。

L1正則損失函數(shù):

L2正則損失函數(shù):

?

L1正則化是指權(quán)值向量w中各個元素的絕對值之和，通常表示為||w||1。

L2正則化是指權(quán)值向量w中各個元素的平方和然后再求平方根（可以看到Ridge回歸的L2正則化項有平方符號），通常表示為∥w∥22

?

一般都會在正則化項之前添加一個系數(shù)λ。Python中用α表示，這個系數(shù)需要用戶指定（也就是我們要調(diào)的超參）。

?

L1正則化可以使得參數(shù)稀疏化，即得到的參數(shù)是一個稀疏矩陣，可以用于特征選擇。

稀疏性，說白了就是模型的很多參數(shù)是0。通常機器學(xué)習(xí)中特征數(shù)量很多，例如文本處理時，如果將一個詞組（term）作為一個特征，那么特征數(shù)量會達到上萬個（bigram）。在預(yù)測或分類時，那么多特征顯然難以選擇，但是如果代入這些特征得到的模型是一個稀疏模型，很多參數(shù)是0，表示只有少數(shù)特征對這個模型有貢獻，絕大部分特征是沒有貢獻的，即使去掉對模型也沒有什么影響，此時我們就可以只關(guān)注系數(shù)是非零值的特征。這相當(dāng)于對模型進行了一次特征選擇，只留下一些比較重要的特征，提高模型的泛化能力，降低過擬合的可能。

?

“帶正則項”和”帶約束條件”是等價的

?

s.t.:subject to受限于

?

問題轉(zhuǎn)化成了帶約束條件的凸優(yōu)化問題，寫出拉格朗日函數(shù)(易知Loss函數(shù)是凸優(yōu)化問題):

設(shè)W?和λ?是原問題的最優(yōu)解，則根據(jù)KKT條件得:

λ?>=0就是在曲圖式的上方極值點

?

L1正則化是權(quán)值的絕對值之和,J是帶有絕對值符號的函數(shù)，因此J是不完全可微的。機器學(xué)習(xí)的任務(wù)就是要通過一些方法（比如梯度下降）求出損失函數(shù)的最小值。

此時我們的任務(wù)變成在L約束下求出J0取最小值的解。

?

考慮二維的情況，即只有兩個權(quán)值w1和w2，此時L=|w1|+|w2|對于梯度下降法，求解J0的過程可以畫出等值線，同時L1正則化的函數(shù)L也可以在w1、w2的二維平面上畫出來。

?

越往里相交的點越最優(yōu)

上圖中等值線是J0的等值線，黑色方形是L函數(shù)的圖形。在圖中，當(dāng)J0等值線與L圖形首次相交的地方就是最優(yōu)解。上圖中J0與L在L的一個頂點處相交，這個頂點就是最優(yōu)解。注意到這個頂點的值是(w1,w2)=(0,w2)

?？梢灾庇^想象，因為L函數(shù)有很多突出的角（二維情況下四個，多維情況下更多），J0與這些角接觸的機率會遠大于與L其它部位接觸的機率，而在這些角上，會有很多權(quán)值等于0，這就是為什么L1正則化可以產(chǎn)生稀疏模型，進而可以用于特征選擇。

?

而正則化前面的系數(shù)λ，可以控制L圖形的大小。λ越小，L的圖形越大（上圖中的黑色方框)；λ 越大，L的圖形就越小，可以小到黑色方框只超出原點范圍一點點，這是最優(yōu)點的值(w1,w2)=(0,w2)中的w2可以取到很小的值。

因為訓(xùn)練集的不規(guī)則,L2函數(shù)仍具有一定的稀疏性.

?

正則化底層原理9:

擬合過程中通常都傾向于讓權(quán)值盡可能小，最后構(gòu)造一個所有參數(shù)都比較小的模型。因為一般認為參數(shù)值小的模型比較簡單，能適應(yīng)不同的數(shù)據(jù)集，也在一定程度上避免了過擬合現(xiàn)象?？梢栽O(shè)想一下對于一個線性回歸方程，若參數(shù)很大，那么只要數(shù)據(jù)偏移一點點，就會對結(jié)果造成很大的影響；但如果參數(shù)足夠小，數(shù)據(jù)偏移得多一點也不會對結(jié)果造成什么影響，專業(yè)一點的說法是抗擾動能力強。

?

而正則化可以獲得值很小的參數(shù):λ 越大，L2圓的半徑越小，最后求得代價函數(shù)最值時各參數(shù)也會變得很小

?

?

?

拉格朗日乘數(shù)法9:

是一種尋找變量受一個或多個條件所限制的多元函數(shù)的極值的方法(梯度極值) 這種方法將一個有n 個變量與k 個約束條件的最優(yōu)化問題轉(zhuǎn)換為一個有n + k個變量的方程組的極值問題，n+k變量不受任何約束

這種方法引入了一種新的標量未知數(shù)，即拉格朗日乘數(shù),就是約束方程的梯度（gradient）的線性組合里每個向量的系數(shù)

此方法的證明牽涉到偏微分，全微分或鏈法，從而找到能讓設(shè)出的隱函數(shù)的微分為零的未知數(shù)的值。??????????????????????????????????????????????????

?

隱函數(shù): 如果方程F(x,y)=0能確定y是x的函數(shù)，那么稱這種方式表示的函數(shù)是隱函數(shù)

?

例子:

設(shè)給定二元函數(shù)z=?(x,y)和附加條件φ(x,y)=0，為尋找z=?(x,y)在附加條件下的極值點，先做拉格朗日函數(shù)

其中, λ為參數(shù)

令F(x,y,λ)對x和y和λ的一階偏導(dǎo)數(shù)等于零,用λ來湊,即

?

F'x=?'x(x,y)+λφ'x(x,y)=0

?

F'y=?'y(x,y)+λφ'y(x,y)=0

?

F'λ=φ(x,y)=0

曲線L為約束條件φ(x,y);f(x,y)=C為目標線族

極值點從幾何上看，必是目標函數(shù)等值線曲線族中與約束條件曲線能相切的那個切點。

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

最優(yōu)參數(shù)-凸優(yōu)化基礎(chǔ)Convex Optimization basics 8:

步長可以考慮衰減步長來優(yōu)化

?

SciPy's truncated newton（TNC）9:

fmin_tnc ( func , x0 , fprime = None , args = () , approx_grad = 0 , bounds = None , epsilon = 1e-08 , scale = None , offset = None , messages = 15 , maxCGit = -1 , maxfun = None , eta = -1 ,步長x= 0、精度= 0、 fmin = 0、 ftol = -1、 xtol = -1、 pgtol = -1、重新縮放= -1、 disp = None、回調(diào)= None）[來源]

?

該函數(shù)用于流式的在線學(xué)習(xí)大數(shù)據(jù)問題(無法將所有數(shù)據(jù)裝入內(nèi)存)

截斷梯度法(Truncated Gradient)即此:與梯度下降是一種東西的

?

L1正則能夠產(chǎn)生稀疏的解。為了能夠在利用在線學(xué)習(xí)的同時產(chǎn)生稀疏解，最直接的想法是采用截斷的方法，截斷，即通過某個閾值來控制系數(shù)的大小，若系數(shù)小于某個閾值便將該系數(shù)設(shè)置為0，這便是簡單截斷的含義。

?

?

1.簡單截斷:

簡單截斷的含義是給定某個閾值,在在線學(xué)習(xí)的過程中，每隔K步進行一次截斷，截斷是指將小于閾值theta的系數(shù)直接賦值為0，具體的形式如下：

該方法的主要缺點是對于K值得選擇是很難解決的問題，其次是通過簡單截斷，有點太暴力。簡單截斷可以應(yīng)用于每一次學(xué)習(xí)，但它可能會導(dǎo)致模型在生成時不完整或不連貫。缺少上下文.

?

2.次梯度:

對于可導(dǎo)的凸函數(shù)，我們通常使用常規(guī)的梯度下降法處理，但當(dāng)目標函數(shù)不可導(dǎo)（在某些點上導(dǎo)數(shù)不存在）時，我們就沒法使用常規(guī)的梯度下降法處理。于是引入次梯度（Subgradient）用于解決此類目標函數(shù)并不總是處處可導(dǎo)的問題。

不足之處就是算法收斂速度慢。

?

對于凸函數(shù)f,如果它可導(dǎo)，那么對?x,y∈domf ，都有：

標量的轉(zhuǎn)置還是它本身

g為次梯度

凸函數(shù)總有次梯度，非凸函數(shù)即使可微也不一定有次梯度。凸函數(shù)的次微分總是非空，凹函數(shù)的次微分是空集。

將f在x處所有次梯度構(gòu)成的集合稱為f在x處的次微分（Subdifferential）

例如y=|x|,則g={sgn(x) ,x≠0??

?{any∈[-1,1] ，x=0

其中sgn為符號函數(shù)，any表示任意一個元素。

Sgn 函數(shù)返回一個整型變量，指出參數(shù)的正負號

?

用次梯度對原函數(shù)做出的一階展開估計總是比真實值要小

?

?

?

?

?

?

?

?

?

?

?

若lasso問題訓(xùn)練時本身沒有權(quán)重權(quán)重項:

可化簡為:

?

lamda>0

可以得到軟閾值算子soft_threshold:

?

?

次梯度法有O(1/?2)的收斂率，其慢于梯度下降的O(1/?)收斂率。

?

?

?

3.截斷梯度法:

在截斷梯度法中，將截斷的步驟適當(dāng)放緩，其具體的更新公式如下：

?

gi稱為重力參數(shù)(gravity parameter)，截斷函數(shù)Ti的具體形式如下：

與簡單截斷類似，每隔K次對參數(shù)gi進行更新，其更新公式如下：

其中，gi可以通過調(diào)節(jié)參數(shù)g和參數(shù)theta控制稀疏度，參數(shù)g和參數(shù)theta越大，解越稀疏。

?

?

[亮張1]?4.投影次梯度法projected subgradient method:

在可微函數(shù)中，負梯度方向是函數(shù)的下降方向，而在不可微函數(shù)中，負次梯度方向?qū)⒉灰欢ㄊ窍陆捣较?，函?shù)的光滑將不再滿足

考慮約束條件的情況下,投影次梯度法在每一次迭代中計算目標函數(shù)的次梯度（subgradient），然后將次梯度的負方向作為搜索方向。這樣可以朝著目標函數(shù)的下降方向更新變量值，以減小目標函數(shù)的值。同時，為了滿足約束條件，投影次梯度法還會對更新后的變量值進行投影操作，將其限制在可行解空間內(nèi)。

若不考慮約束條件，直接沿次梯度的反方向更新變量值有可能會導(dǎo)致超出約束域的范圍，得到非可行解。

為了避免這種情況，投影次梯度法引入了投影運算。投影運算將迭代更新得到的變量值限制在可行解空間內(nèi)，確保每次迭代都滿足約束條件。通過將變量投影回可行解空間，投影次梯度法可以保證求解的解是可行解，從而有效地控制優(yōu)化過程。

凸集（Convex set）是一個點集合，其中每兩點之間的線段點都落在該點集合中。

區(qū)間是實數(shù)的凸集。

依據(jù)定義，中空的圓形稱為圓（circle），它不是凸集；實心的圓形稱為圓盤（disk），它是凸集。

凸多邊形是歐幾理得平面上的凸集，它們的每只角都小于180度。

單純形是凸集，對于單純形的頂點集合來說，單純形是它們的最小凸集，所以單純形也是一個凸包。

定寬曲線是凸集。

在可微函數(shù)中，負梯度方向是函數(shù)的下降方向，而在不可微函數(shù)中，負次梯度方向?qū)⒉灰欢ㄊ窍陆捣较?，函?shù)的光滑將不再滿足，之前多次采用的由光滑性導(dǎo)出的Descent lemma 將不再成立。

?

公式:

???P(G(x))

P()是投影算子,G(x)計算梯度

?

?

?

5.近端梯度法Proximal Gradient Descent:

有沒有既可求不可導(dǎo),又收斂快的梯度下降方法?

?

前提條件: 可分解的目標函數(shù)

考慮一個目標函數(shù)可以分解為如下形式的兩個函數(shù)

????????????????????????????

g(x)是凸函數(shù)且是可微分的,h(x)也是凸函數(shù)但可能不可微分

?

三級收斂速率中近端梯度下降最快

?

如果f不可微，但可以分解為上述的兩個函數(shù)g和h，則我們?nèi)匀豢梢允褂闷交糠謌的二次近似來定義向最小值走的一步：

?

近端映射(proximal mapping)

對于這樣的凸優(yōu)化問題，需定義近端映射算子

arg 是變元（即自變量argument）的英文縮寫。arg min 就是使后面這個式子達到最小值時的變量的取值

?

這里的prox(x)=>賦給z

不可微函數(shù)h(x)分別為0,Ic(x)和||x||1時

分別是常規(guī)梯度下降,投影梯度下降,和軟閾值算法.

?

例:近端梯度下降法求解lasso問題

?

scipy:minimize(method=’TNC’)

https://blog.csdn.net/qq_38048756/article/details/103208834

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

對偶duality 1:

線性規(guī)劃對偶:

?

假設(shè)我們想要尋找一個凸優(yōu)化問題的下界（lower bound），即尋找B ≤ min[f(x)],以線性規(guī)劃（LP）問題為例，考慮一個簡單的LP問題：

???min p*x+q*y

???s.t. x+y=2

???x,y>=0

那么對于任意a,b,c≥0，都有p*x + q*y = (a + b)*x + (a + c)*y = (a*x + a*y) + b*x + b*y ≥ 2*a

?

更一般的形式:

min px+qy

subject to??x+y≥2

x,y≥0

一步轉(zhuǎn)化?

?a,b,c>=0 , px+qy=(a+b)x+(a+c)y=(ax+ay)+bx+cy≥2a。

再轉(zhuǎn)化?

max 2a

subject to??a+b=p

a+c=q

a,b,c≥0

我們把上面的形式稱為原問題（primal LP）的對偶（dual LP）。注意到對偶變量的數(shù)量等于該問題的約束條件數(shù)目（這里都為3）。

?

min?cx

subject toAx=b

Gx≤h

其對偶:

max ?bTu?hTv

解釋:?u,v>0,

?

所以如果令c = ? ATu ? GTv , 那么我們就可以得到原問題的一個下界

?

例子:最大流最小割(max flow and min cut)

給定一個圖G = ( V,E )，定義流（flow）fij , ( i,j )∈E滿足：

（所有流都是正的）

（所有流都是有限的）

（除了始末節(jié)點外，流入某個節(jié)點的所有流等于流出該節(jié)點的所有流）

最大流問題：找到從s流向t的所有流的最大值。這是一個LP問題：

?

?