机器学习

您所在的位置:网站首页 机器的组成分为几部分 机器学习

机器学习

2023-07-02 10:24| 来源: 网络整理| 查看: 265

    KKT优化条件是支持向量机算法SVM中相当重要的组成部分,本质上就是利用朗格朗日乘数法来求解在约束条件下的最值问题。

    

基础的二元拉格朗日极值问题最小值问题

   在二维平面上为例,圆形代表目标函数f(x)的等高线,这里的自变量x是向量的形式,图像上每一圈就是取得相同的函数值, 约束条件是由多条直线边界组成约束集,二维平面上时直线三维空间就是平面了。

    由图像可知,决定函数极值时发挥作用的一般只是两条直线α和β,相交于某一点x*,在这一点处直线函数值刚好取得边界值零,二者的梯度的线性组合等于目标函数f(x)的逆梯度方向。

    因为求的是目标函数最小值,而梯度是增大的方向,f(x)的梯度方向指向发散,逆梯度也就是指向最小值。而约束条件组成的区域是使得边界函数小于0,所以边界函数的梯度方向是指向条件区域外的方向,而目标函数f(x)的逆梯度方向正好在二者的夹角之内,对应的系数λ必须大于0.

    这也就解释了为什么只有两条直线在求取最值时发挥作用,即使是多条直线相交于同一点,但在梯度线性组合出目标函数逆梯度的时候,只用两条直线的梯度线性组合就可以了。其余的直线不会参与组成约束空间,就可以不用考虑了,因为多条直线相交,约束区域一定是某两条夹角较小的直线组成的空间,发挥作用的肯定只有两条直线。

    与此同时其他的组成约束区域的边界函数,带入x*可得,对应的边界函数值均小于0(条件区域要求),而它们在极值点取值时又不发挥作用,对应的λi就等于0 .

拉格朗日系数λi

当目标函数的最小值点就在函数区域内部时,就直接取得x*即可,约束边界函数不发挥作用。

目标函数最值点在条件区域内拉格朗日乘数法与其对偶问题

    首先是基础的f0(x)的最小值与约束条件fi(x)和h(x),将这个问题使用拉格朗日乘数法添加λ和v两个系数,L函数的最小值对应也就是f0(x)的最小值,而fi(x)小于零,所以λ和v都求最大值,对应的l也就是最小了。

     可行域就是约束条件fi(x)和h(x),当x固定,λ和v变化时求取L的最大值时,自变量x不在可行域内时,λ乘以fi(x)无上限,相加之后一定是无穷大。当x取值在可行域内时,fi(x)小于零,λ大于零,乘积小于0恒成立,所以最大值就是f0(x)。二者取值相结合再求最小值,就是目标函数f0(x)的最小值。

将L函数分成两个区域

    虽然h(x)恒等于0,但是其对应的梯度值是不为零的,这个也是拉格朗日乘数法需要满足的条件之一必须写入函数式L。

    对应的对偶问题,注意这里是单向箭头,就相当于是调换了求最值的顺序,然后对于拉格朗日函数求最值就是让其对应的偏导数为0.改变写法就可以得到下面的式子,将其换到条件区域上要求满足。

将梯度为0的点放入条件区域



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3