关于最优化的那些事（一）：构造目标函数

随着机器学习，特别是深度学习的广泛普及和应用，作为解决这类问题的重要工具，最优化问题和方法也越来越被大家所熟悉。甚至在机器学习领域中，可以比较粗略的认为，所有的机器学习问题最后都可以转化为最优化问题。因为大多数机器学习或者人工智能的问题，我们都是在所有可能的假设空间中去寻找最优的模型或者策略。最优化问题可以分为两个子问题：如何构造合理的目标函数以及如何求解目标函数。作为这个系列的第一讲，本文将简要说明一些构造目标函数的具体例子，以及将一些常见的算法纳入到最优化的体系中来，可以看到有些我们熟悉的算法原来可以看成是一些具体求解最优化问题的过程。

这种通过构建目标函数将问题转化到最优化框架的方法在计算机视觉，计算机图形学，机器学习等领域都有着广泛的应用。在我们如视，这一框架可以被应用在图形的拼接，图像的补全，三维网格模型的生成，三维模型的纹理贴图等业务里。在本文的最后，我们给出了一些这一最优化框架的应用实例。

最优化问题可以概况为下面的数学问题：

其中 f 为所构建的目标函数，X 为我们所考虑的问题的解可能存在的空间。

二维数据的线性拟合大概最简单的机器学习问题了，我们以它为例子简要说明构造合理的目标函数的一些需要考虑的点。

二维数据线性拟合考虑的是二维平面上有一些点，求一个最优的线性函数来描述这些点的横纵坐标的对应关系。如下图：

使用最小二乘法，可以轻松求得该问题的解,具体解的过程中将涉及到矩阵的求逆运算。我们可以通过下图来理解所构建的目标函数的几何意义，我们实际是通过每个数据点做平行于 y 轴的直线，将该直线与预测的线性函数的交点作为模型预测的值，目标函数是预测的 y 值与实际数据的 y 值的平方和。

通过上图可以清晰的看到基于最小二乘法的线性拟合目标函数的几何意义。一个自然的想法是为什么将过数据点与 y 轴平行的直线和预测直线的交点作为对应的预测点，因为从几何图形上来看，一个更自然的预测点是数据点到预测直线的最近距离点，即过数据点向预测直线做垂直线与预测直线的交点，如下图所示：

对应的目标函数为：

事实上对主成分分析(PCA)理解的同学可以一眼看出所求目标函数的方向即为数据点的第一个主成分。求解上面的目标函数将涉及到矩阵的特征值的求解。

所以我们可以看到哪怕是在逻辑上非常接近的目标也可能导致不同的目标函数，从而引出差异非常巨大的求解方法。

在一些实际的应用中，我们可能还需要目标函数对数据有一定的鲁棒性，因为实际的数据中可能会有一些异常点(outlier)。仍然以上面基于最小二乘法的线性拟合为例子。如下图所示：

若仍然采用原先的目标函数，由于异常点的影响，所得的最优解可能类似图中实线部分的直线，而若是能够准确的检测出异常点，则可能更为合理的最优解应该是类似图中虚线所示的直线。此时可以使用关于 M - estimator 的方法使得目标函数对异常点有一定的鲁棒性， 一个可能的选择是使用 Huber 函数：

其中

这样做的好处是当误差比较小时，目标函数为范数，当误差较大时，目标函数为线性函数，不至于由于个别 outlier 极大的影响最终的解。

很多机器学习和计算机视觉中的优化问题都有两个部分构成，不仅要考虑跟数据的拟合程度，还需要考虑模型的范化能力，这就引入了一种防过拟合的方法：正则化。

例如在我们考虑使用多项式函数拟合曲线的时候，误差函数不仅仅包含数据拟合部分：

还包含正则项：

此时整体的目标函数为：

更一般的，监督式机器学习都可以大致看成下面目标函数的最优化：

对于第一项数据误差部分，当使用平方和误差，就对应前面所说的最小二乘法，当使用 log 误差，则变成逻辑回归，当使用 Hing 误差，则变成 SVM 问题，当使用指数误差，就变成 Boosting 问题。对于第二项正则化的部分，一般有各种不同的范数可以选择。其中，范数隐形的带来稀疏性的约束，所以早期的机器学习通常通过这些范数来实现稀疏编码和压缩感知等技术。稀疏性自动的实现了特征的重要性选择，对我们理解和解释数据和模型有着非常重要的意义。范数可以在一定程度上限制模型的复杂程度，增强模型的范化能力，避免过拟合。同时在直接全局求解优化问题时，不加范数对应着高斯牛顿方法，需要求解一个由数据构成的矩阵的逆(参考前面的线性拟合问题)，而加了范数对应这 Levenberg-Marquardt 方法，从这个角度来看，加如了数可以有效应对数据矩阵不可逆，或者可逆但是 condition number 非常大所带来的数值不稳定，收敛速度慢等问题。

几何直观的来看，加入了范数，使得原目标函数在可能的梯度极其平坦，收敛极慢的地方（极端情况，局部是一条平行 x 轴的平面，梯度为 0），目标函数的主要成分由二次正则项主导，使得目标函数的凸性至少是二次函数的水平。核范数是对低秩这一先验的凸近似，这就又一次和 PCA 产生了汇合，事实上 PCA 认为数据空间可以通过远低于空间维度数目的主元构成的基来描述，除此之外都是噪音。而低秩也是类似的假设。事实上鲁棒 PCA 可以描述为下面的最优化问题：

其中为数据矩阵，为低秩主元成分，为噪音。使用核范数凸近似非凸的 rank 函数，凸近似非凸函数到核范数问题：

除此之外还有比较常用的 Frobenius 范数等。

一些我们熟知的算法在建立的合适的目标函数后会变成相应的优化问题的解。其中的一个例子就是 K-means 算法，K-means 算是聚类算法中最简单的一种了。论文 K-means Clustering Is Matrix Factorization 证明了 K-means 算法对应了如下最优化问题的解：

该最优化问题可以通过数值的求解 Poisson 方程得到最优解。下图是修补前和修补后的效果：

最后，我们展示一些基于最优化求解的一些应用：

基于图割目标函数的抠图效果

基于动态规划目标函数图像拉伸效果，b 图为简单重复填充，d 图为动态优化选取纹理路径结果

基于 CRF 目标函数的语义分割结果

基于 TV-L1 目标函数的三维重建结果

作者介绍：

笨象（企业代号名）老师，贝壳如视算法架构师，负责视觉建模算法研发。

本文转载自公众号贝壳产品技术（ID：gh_9afeb423f390）。

原文链接：

https://mp.weixin.qq.com/s/ePzJgMRT9Xv-XH06d0xFrw