岭回归与Lasso算法:

alpha的作用:调整正则化权重

岭回归: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))

 

正则化公式:

 

 

 

逻辑回归优化与调参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:

对原始损失函数引入额外信息，以便防止过拟合和提高模型泛化性能的一类方法的统称

中文称作L1正则化和L2正则化，或者L1范数和L2范数（L1实际是L2范数的平方）。

使用L1正则化的模型叫做Lasso回归，使用L2正则化的模型叫做Ridge回归（岭回归）。

L1正则损失函数:

L2正则损失函数:

 

L1正则化是指权值向量w中各个元素的绝对值之和，通常表示为||w||1。

L2正则化是指权值向量w中各个元素的平方和然后再求平方根（可以看到Ridge回归的L2正则化项有平方符号），通常表示为∥w∥22

 

一般都会在正则化项之前添加一个系数λ。Python中用α表示，这个系数需要用户指定（也就是我们要调的超参）。

 

L1正则化可以使得参数稀疏化，即得到的参数是一个稀疏矩阵，可以用于特征选择。

稀疏性，说白了就是模型的很多参数是0。通常机器学习中特征数量很多，例如文本处理时，如果将一个词组（term）作为一个特征，那么特征数量会达到上万个（bigram）。在预测或分类时，那么多特征显然难以选择，但是如果代入这些特征得到的模型是一个稀疏模型，很多参数是0，表示只有少数特征对这个模型有贡献，绝大部分特征是没有贡献的，即使去掉对模型也没有什么影响，此时我们就可以只关注系数是非零值的特征。这相当于对模型进行了一次特征选择，只留下一些比较重要的特征，提高模型的泛化能力，降低过拟合的可能。

 

“带正则项”和”带约束条件”是等价的

 

s.t.:subject to受限于

 

问题转化成了带约束条件的凸优化问题，写出拉格朗日函数(易知Loss函数是凸优化问题):

设W∗和λ∗是原问题的最优解，则根据KKT条件得:

λ∗>=0就是在曲图式的上方极值点

 

L1正则化是权值的绝对值之和,J是带有绝对值符号的函数，因此J是不完全可微的。机器学习的任务就是要通过一些方法（比如梯度下降）求出损失函数的最小值。

此时我们的任务变成在L约束下求出J0取最小值的解。

 

考虑二维的情况，即只有两个权值w1和w2，此时L=|w1|+|w2|对于梯度下降法，求解J0的过程可以画出等值线，同时L1正则化的函数L也可以在w1、w2的二维平面上画出来。

 

越往里相交的点越最优

上图中等值线是J0的等值线，黑色方形是L函数的图形。在图中，当J0等值线与L图形首次相交的地方就是最优解。上图中J0与L在L的一个顶点处相交，这个顶点就是最优解。注意到这个顶点的值是(w1,w2)=(0,w2)

。可以直观想象，因为L函数有很多突出的角（二维情况下四个，多维情况下更多），J0与这些角接触的机率会远大于与L其它部位接触的机率，而在这些角上，会有很多权值等于0，这就是为什么L1正则化可以产生稀疏模型，进而可以用于特征选择。

 

而正则化前面的系数λ，可以控制L图形的大小。λ越小，L的图形越大（上图中的黑色方框)；λ 越大，L的图形就越小，可以小到黑色方框只超出原点范围一点点，这是最优点的值(w1,w2)=(0,w2)中的w2可以取到很小的值。

因为训练集的不规则,L2函数仍具有一定的稀疏性.

 

正则化底层原理9:

拟合过程中通常都倾向于让权值尽可能小，最后构造一个所有参数都比较小的模型。因为一般认为参数值小的模型比较简单，能适应不同的数据集，也在一定程度上避免了过拟合现象。可以设想一下对于一个线性回归方程，若参数很大，那么只要数据偏移一点点，就会对结果造成很大的影响；但如果参数足够小，数据偏移得多一点也不会对结果造成什么影响，专业一点的说法是抗扰动能力强。

 

而正则化可以获得值很小的参数:λ 越大，L2圆的半径越小，最后求得代价函数最值时各参数也会变得很小

 

 

 

拉格朗日乘数法9:

是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法(梯度极值) 这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题，n+k变量不受任何约束

这种方法引入了一种新的标量未知数，即拉格朗日乘数,就是约束方程的梯度（gradient）的线性组合里每个向量的系数

此方法的证明牵涉到偏微分，全微分或链法，从而找到能让设出的隐函数的微分为零的未知数的值。                                                  

 

隐函数: 如果方程F(x,y)=0能确定y是x的函数，那么称这种方式表示的函数是隐函数

 

例子:

设给定二元函数z=ƒ(x,y)和附加条件φ(x,y)=0，为寻找z=ƒ(x,y)在附加条件下的极值点，先做拉格朗日函数

其中, λ为参数

令F(x,y,λ)对x和y和λ的一阶偏导数等于零,用λ来凑,即

 

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为目标线族

极值点从几何上看，必是目标函数等值线曲线族中与约束条件曲线能相切的那个切点。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

最优参数-凸优化基础Convex Optimization basics 8:

步长可以考虑衰减步长来优化

 

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、回调= None）[来源]

 

该函数用于流式的在线学习大数据问题(无法将所有数据装入内存)

截断梯度法(Truncated Gradient)即此:与梯度下降是一种东西的

 

L1正则能够产生稀疏的解。为了能够在利用在线学习的同时产生稀疏解，最直接的想法是采用截断的方法，截断，即通过某个阈值来控制系数的大小，若系数小于某个阈值便将该系数设置为0，这便是简单截断的含义。

 

 

1.简单截断:

简单截断的含义是给定某个阈值,在在线学习的过程中，每隔K步进行一次截断，截断是指将小于阈值theta的系数直接赋值为0，具体的形式如下：

该方法的主要缺点是对于K值得选择是很难解决的问题，其次是通过简单截断，有点太暴力。简单截断可以应用于每一次学习，但它可能会导致模型在生成时不完整或不连贯。缺少上下文.

 

2.次梯度:

对于可导的凸函数，我们通常使用常规的梯度下降法处理，但当目标函数不可导（在某些点上导数不存在）时，我们就没法使用常规的梯度下降法处理。于是引入次梯度（Subgradient）用于解决此类目标函数并不总是处处可导的问题。

不足之处就是算法收敛速度慢。

 

对于凸函数f,如果它可导，那么对∀x,y∈domf ，都有：

标量的转置还是它本身

g为次梯度

凸函数总有次梯度，非凸函数即使可微也不一定有次梯度。凸函数的次微分总是非空，凹函数的次微分是空集。

将f在x处所有次梯度构成的集合称为f在x处的次微分（Subdifferential）

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

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

其中sgn为符号函数，any表示任意一个元素。

Sgn 函数返回一个整型变量，指出参数的正负号

 

用次梯度对原函数做出的一阶展开估计总是比真实值要小

 

 

 

 

 

 

 

 

 

 

 

若lasso问题训练时本身没有权重权重项:

可化简为:

 

lamda>0

可以得到软阈值算子soft_threshold:

 

 

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

 

 

 

3.截断梯度法:

在截断梯度法中，将截断的步骤适当放缓，其具体的更新公式如下：

 

gi称为重力参数(gravity parameter)，截断函数Ti的具体形式如下：

与简单截断类似，每隔K次对参数gi进行更新，其更新公式如下：

其中，gi可以通过调节参数g和参数theta控制稀疏度，参数g和参数theta越大，解越稀疏。

 

 

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

在可微函数中，负梯度方向是函数的下降方向，而在不可微函数中，负次梯度方向将不一定是下降方向，函数的光滑将不再满足

考虑约束条件的情况下,投影次梯度法在每一次迭代中计算目标函数的次梯度（subgradient），然后将次梯度的负方向作为搜索方向。这样可以朝着目标函数的下降方向更新变量值，以减小目标函数的值。同时，为了满足约束条件，投影次梯度法还会对更新后的变量值进行投影操作，将其限制在可行解空间内。

若不考虑约束条件，直接沿次梯度的反方向更新变量值有可能会导致超出约束域的范围，得到非可行解。

为了避免这种情况，投影次梯度法引入了投影运算。投影运算将迭代更新得到的变量值限制在可行解空间内，确保每次迭代都满足约束条件。通过将变量投影回可行解空间，投影次梯度法可以保证求解的解是可行解，从而有效地控制优化过程。

凸集（Convex set）是一个点集合，其中每两点之间的线段点都落在该点集合中。

区间是实数的凸集。

依据定义，中空的圆形称为圆（circle），它不是凸集；实心的圆形称为圆盘（disk），它是凸集。

凸多边形是欧几理得平面上的凸集，它们的每只角都小于180度。

单纯形是凸集，对于单纯形的顶点集合来说，单纯形是它们的最小凸集，所以单纯形也是一个凸包。

定宽曲线是凸集。

在可微函数中，负梯度方向是函数的下降方向，而在不可微函数中，负次梯度方向将不一定是下降方向，函数的光滑将不再满足，之前多次采用的由光滑性导出的Descent lemma 将不再成立。

 

公式:

   P(G(x))

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

 

 

 

5.近端梯度法Proximal Gradient Descent:

有没有既可求不可导,又收敛快的梯度下降方法?

 

前提条件: 可分解的目标函数

考虑一个目标函数可以分解为如下形式的两个函数

                            

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

 

三级收敛速率中近端梯度下降最快

 

如果f不可微，但可以分解为上述的两个函数g和h，则我们仍然可以使用平滑部分g的二次近似来定义向最小值走的一步：

 

近端映射(proximal mapping)

对于这样的凸优化问题，需定义近端映射算子

arg 是变元（即自变量argument）的英文缩写。arg min 就是使后面这个式子达到最小值时的变量的取值

 

这里的prox(x)=>赋给z

不可微函数h(x)分别为0,Ic(x)和||x||1时

分别是常规梯度下降,投影梯度下降,和软阈值算法.

 

例:近端梯度下降法求解lasso问题

 

scipy:minimize(method=’TNC’)

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

对偶duality 1:

线性规划对偶:

 

假设我们想要寻找一个凸优化问题的下界（lower bound），即寻找B ≤ min[f(x)],以线性规划（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

一步转化⇒

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

再转化⇒

max 2a

subject to  a+b=p

a+c=q

a,b,c≥0

我们把上面的形式称为原问题（primal LP）的对偶（dual LP）。注意到对偶变量的数量等于该问题的约束条件数目（这里都为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满足：

（所有流都是正的）

（所有流都是有限的）

（除了始末节点外，流入某个节点的所有流等于流出该节点的所有流）

最大流问题：找到从s流向t的所有流的最大值。这是一个LP问题：