ML-凸优化初识

凸优化的入门

ML问题 = 模型 + 优化

• 类似于, 程序 = 数据结构 + 算法
• 模型(objective): DL, LR, SCV, Tree, XGBoost.....
• 优化(train): GD/SGD, Adagrand/ Adam, Coordinate Descent, EM ....

确定问题的性质, 是否为凸优化问题, 然后再确定相应的优化方式和算法去解决.

优化-标准写法

\(Minimize \ f_0 = (x) \\ s.t. \\ f_i(x) <= 0, \ i = (1,2,...k) \\ g_j(x) = 0, \ j = (1,2,....l)\)

• 一般都是min的, 如果是max的, 即 -min = max , 大于/小于亦如此
• \(f_0(x)\)
• s.t. 部分表示约束条件(subject to), 满足约束条件的 x 称为可行解.

常见ML的目标函数

• 线性回归: \(\sum_{i=1}^{n}(w^tx_i - y_i)^2 + ||w||^2_2\) 或矩阵形式 \(||Xw-y||^2_2 + ||w||^2_2\)
• 逻辑回归: \(\sum _{i=1}^{n}y_i \ log(\sigma(w^tx+b)) + (1-y_i)log(1-\sigma(w^tx-b))\)
• 支持向量机: \(min_{w,b} = \frac {1}{2} ||w||^2_2,\ s.t \ \ y_i(w^tx+b)>=1, \ i=1,2,...\)
• 协同过滤: \(\sum _{i,j->\Omega} (u_i^tv_j-r_ij)^2 + \lambda||u||^2_F + \gamma ||v||_F^2\)
• k-means: \(min \sum _{i=1} ^n \sum _{k=1}^k \gamma_{i,k} ||x_i -\mu_k||^2 \ ,s.t. \, \gamma_{i,k} = 1 \ if 样本属于k-cluster, otherwise 0\)

优化分类

将优化问题划分为标准型后, 紧接着需要判断是属于哪个类型的优化问题.

• convex or non-convex 是否为凸函数?
• continuous or discrete 连续还是离散?
• constraint or non-constraint 是否有约束?
• smooth or non-smooth 是否为平滑函数?

首先对于convex (凸函数 "U" 这个形状的, 当然其实我们最希望的是构造的目标函数是convex, 就是咱平时见到的"U"形状的(ps, 即二阶导的Hessian Matrix 是半正定), 这样的好处是它有一个Global optimum (全局最优解), 比如逻辑回归就是一个典型的例子. 而与之对一的是non-convex 最经典的例子是神经网络, 它的目标函数一般是"unuu.." 这样形状的, 求解时只是通过不断迭代求 Local optimum. 对于非凸函数我们追求的是Better local optimum. 尤其在深度学习中, 做预训练时非常重要的, 目的也是为了找到到更好的初始化的解. 在NLP领域, 也是会通过词向量的方式, 用别人训练好的数据来进行更好的初始化过程.同时在深度学习领域,也是比较注重优化器的调整. 当然, 最为重要的还是关注convex了呀.

就我自己而言, 工作涉及的大都是convex, 基本上我是不会用深度学习的, 原因在于,

• 我自己都不知道里面有多少function及其运行机制 (不可控制)
• 很难跟老板解释参数的实际意义 (很难解释)

第二是关于函数是离散还是连续. 当然绝大多数都是假设是连续, 可微可导, 当然也有离散, 离散处理起来有些麻烦了.

第三 是关于目标函数是否有约束条件, 没有约束条件,像线性回归这种, 就可以直接通过梯度下降或最小二乘的方式就可轻易求解了. 然而对于带约束条件的, 比如smv这类, 处理方式通常是将约束条件"带入"目标函数, 比如通过拉格朗日乘子等方式.然后用到的底层知识其实是duality(对偶), 如KKT conditon

第四是关于函数smooth. 对于smooth的函数, 我们可以求出在每个点的梯度(偏导数的函数值组成的向量), 而对于non-smooth, 有可能存在不可微的情况哦, 最常见的应该是L1正则了吧.

Convex Set (凸集)

定义假设对任意的 \(x,y \in C\) 且任意参数 \(\alpha \in [0,1], 满足 \alpha x + (1-\alpha)y \in C\), 则该集合为凸集.

通俗理解就是定义域形状是"连续封闭且外张"的呗.

哎呀,其实数学的东西有些很难"形象", 超出3维就在几何上就画不出来了, 而理解的关键并不是"想象力" 而是从"定义和规则", 比如理解"维度", "对加法和数乘封闭"...这样的, 理解定义和规则, 而非"举个栗子", 很多是不太能"举个栗子的".

常见的凸集

• 所有的\(R^n\)

• 证明by定义: $\forall x, y \in R^n, ax + (1-a)y \in R^n $

• 范数\(||x||<=1\)

• \(\forall x, y, ||x||<=1, ||y||<=1\),
• \(||ax + (1-a)y|| <= ||ax|| + ||(1-a)y|| = ||x|| + (1-a)||y|| <= a + (1-a) = 1\)

• 线性方程组\(Ax=b\)的所有解

• \(Ax=b, Ay=b \rightarrow A(ax+(1-a)y) = b\)

• 不等式\(Ax <= b\)的所有解

有个很明显的定理: 两个凸集的交集也是凸集

凸函数(convex function)

定义 函数的定义域dom为凸集, 对于定义域内任意\(x,y\), 满足\(f(\theta x + (1-\theta)y) <= \theta f(x) + (1-\theta)f(y), \theta \in [0,1]\)

画一个二维的"U" 就可以比较直观认识了, 但还是觉得逐步去理解定义吧

• 取一段区间 [x, \(\theta x + (1-\theta)y, y\)] .. 当时比较直观

范数 Norm: 用来类似衡量向量/矩阵的"大小"的一个量

• L1-norm: \(||w|| = w_1+w_2+w_3+...w_n\)
• L2-norm: \(||w||^2_2 = w_1 ^2 + w_2 ^2 + ...w_n ^2\)
• \(||w||_p = (w_1^p + w_2 ^p + w_3 ^p + ...w_n ^p) ^{\frac {1}{p}}\)
• 常用来看, L1范数表示向量各分量之和; L2范数表示向量的欧式距离的平方..

convex 一阶导

假设\(f: R^n \rightarrow R\) 是可微的(differentiable), f 为凸函数, 当且仅当 \(f(y) >= f(x) +\nabla (x)^T (y-x)\), 对于任意的\(x,y\).

在写代码会用, 如在编写梯度下降的code时会作为循环的break条件

convex 二阶导

假设\(f: R^n \rightarrow R\)

\(\nabla ^2 (x) \succ 0, 对于任意的x \in domf\)

就是二阶导数值"大于0", 需要回顾一波大一的内容. 主要用来证明吧, 比如证明逻辑回归的sujective function是凸函数等.

• 一元函数求二阶导, 得到一个变量, 即是一个值
• 二元函数求二阶导, 得到一个偏导混合的2x2 海塞矩阵
• n元函数求二阶导, 也是得到一个偏导混合 海塞矩阵
• 对于多元" \(\succ 0\)" 表示该 Hessian Matrix 是一个半正定矩阵(PSD)

凸函数案例

case 1: 线性函数: \(f(x) = b^Tx + c\)

\(\forall x_1,x_2, \\ f(x_1) = b^Tx_1+c \\ f(x_2)=b^Tx_2 +c\)

用定义做判断证明:

\(b^T(\theta x_1 + (1- \theta)x2 + c <= \theta (b^Tx_1) + (1-\theta)(b^Tx_2+c)\)

\(b^T \theta x_1 +(1-\theta) b^Tx_2 + c <= \theta b^Tx_1 + (1-\theta)(b^Tx_2) + (1-c)\theta\)

\(c <= c, 证毕\)

case 2: 二次方函数\(f(x) = \frac {1}{2}x^tAx + b^tx +c\), A是半正定矩阵

这里用二阶导来证明即可

$\frac {\partial f(x)} {f(x)} = Ax + b $

\(\frac {\partial ^2 x}{f(x)} = A \\ 由条件A \succ 0, 证毕\)

矩阵求导: ​​http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=3274​​