最优化建模、算法与理论（三）—— 优化建模

参考书籍《最优化：建模、算法与理论》

1 建模设计

1.1 目标函数的设计

• 最小二乘法：常见于线性 / 非线性方程问题，其思想是极小化误差的的 ℓ2 范数平方，即：
  $$mi{n}_{x\in R^n}\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2$$
  当m < n时，最优解很可能不止一个。

• 正则化：为了让解具有某种光滑性以及克服问题的病态性质，常常会加入一个正则项，则改进模型为：
  $$mi{n}_{x\in R^n}\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu ||x|{|}_n^m$$
  正则项的含义是我们需要其同时满足“误差尽量小”以及“欧几里得长度尽量短”，参数μ的作用是调整最小二乘项和正则项的权重，当μ较大时该模型更侧重于 ℓ2 范数较小的解。

• 最大似然估计：是统计中常用的一种估计概率分布的方法，其通过最大化似然函数，使得观测数据尽可能地服从假定的模型。常用于从数据反推概率分布模型。
  假设最大似然估计存在，则求解最大似然估计本质上是在一族分布中寻找最有可能产生该样本的参数，实际中似然函数的对数的最大值往往更容易求解，所以在统计中更倾向于使用对数似然函数 ℓ(x)。
  似然函数：在参数x下的数据集 {ai, i = 1, 2,··· ,n} 发生的概率

• 代价、损失、收益函数：其目标函数或者是极小化代价（损失），或者是极大化收益，或者是两者兼顾。

• 泛函、变分：一般来说，能量泛函是定义在函数空间上的，即相应优化问题的自变量是无穷维空间中的函数．我们可以通过变分来得到其相应的最优性条件等。实际中常用的另一种方式，是利用合适的离散化，将能量泛函的极小化问题从无穷维空间中拉回到有限维空间中，从而得到相应问题的离散解。

• 松弛问题：原始问题不容易求解时，常用技巧为松弛，基本思想是：在保留原问题部分性质的条件下，使用简单的项替代目标函数中难以处理的项，进而使得问题更易求解。

1.2 约束设计

• 问题本身的物理性质：如速度与加速度之间的关系等
• 等价转换
• 松弛

2 建模技巧

2.1 监督学习

在机器学习中，监督学习的任务是根据给定包含输入信息的数据集，学习一个模型，使得模型能够对新的输入数据做出好的预测，经典的监督学习包括回归和分类两类问题。

2.1.1 回归

• 回归模型：
  回归模型就是利用 m 个观测值 (ai, bi) 来求解出 f 的具体形式，然后可以利用新观测的自变量对响应变量做出预测。
  回归模型的一般形式：b = f(a) + ε，其中 a ∈ $R^d$ 为自变量，b ∈ R 为响应变量，ε ∈ R 是模型的误差（或噪声）。
  线性回归模型：其模型简写为$b_i=a_i^{T}x+{\epsilon }_i$
  正则化线性回归模型：当解不唯一时，需要借助正则项来选出性质不同得解。

2.1.2 分类

在分类问题中，输出变量取值于离散空间．对于二分类问题，预测变量只有两个取值，即 −1, 1。

• 逻辑回归：逻辑回归属于机器学习中一种经典二分类模型
• 支持向量机：定训练数据集 D 中的样本点 (ai, bi) 且 ai ∈ $R^n$, bi ∈ {−1, 1}，SVM（支持向量机） 的基本思想是找到一个超平面将 $R^n$ 中的样本点划分成两类。比较理想的超平面应该具有下面的特点：数据点距此平面的距离都比较远．使用这样的超平面建立的二分类模型会有比较好的鲁棒性。

2.2 概率图模型

概率图模型是概率论中一个重要的概念，它是一种利用图结构来描述多元随机变量之间条件独立关系的概率模型，对于高维空间中的概率模型的研究具有重要作用。当概率模型中变量比较多时，其相应的依赖关系也会比较复杂，图模型可以帮助我们更加直观地了解随机变量之间的条件独立关系。

• 无向图模型：也称为马尔可夫（Markov）随机场或马尔可夫网络，其利用无向图来描述一组具有马尔可夫性质的随机变量的联合分布。马尔可夫随机场中对于给定变量$X_k$满足
  $$P(X_k=x_k|X_{-k})=P(X_k=x_k|X_{N(k)})$$
  其中$X_{-k}$表示除了 $X_k$ 外其他随机变量的集合，$X_{N(k)}$ 表示 $X_k$的邻居集合，即和 $X_k$ 有边直接相连的随机变量的集合。

马尔可夫性质：一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态，换而言之，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的。

2.3 相位恢复

相位恢复是信号处理中的一个重要问题，它是从信号在某个变换域的幅度测量值来恢复该信号。相位恢复问题本质上是求解如下的二次方程组：
$$b_k^2=|{\bar{a}}_k^{T}x{|}^2，k=1,2,...,m$$
求解二次方程组问题是NP难得，可将二次方程组转化为以下两种模型求解：

• 最小二乘模型：将二次方程组转换为非线性最小二乘问题：
  $$\underset{x\in C^n}{\min }\sum (|{\bar{a}}_k^{T}x{|}^2-b_i^2{)}^2$$

• 相位提升：
  $\because |{\bar{a}}_k^{T}x{|}^2={\bar{a}}_i^{T}x{\hat{x}}^T{a}_i=Tr(x{\hat{x}}^T{a}_i{\bar{a}}_i^T)$ ；
  令$X=x{\hat{x}}^T$，则二次方程组可转化为$Tr(X{a}_i{\bar{a}}_i^T)=b_i^2，i=1,2\dots ,m；X⪰0,rank(X)=1$
  $\therefore$ X即为方程组得解

2.4 主成分分析

主成分分析是数据处理和降维中的一个重要技巧，它提供了一种将高维空间中的点在低维子空间中表达的方法。其思想是寻找样本点方差最大的若干方向构成的子空间，之后将数据点投影到该子空间内来实现降维。

2.5 矩阵分离问题

矩阵分离问题，也称鲁棒主成分分析，也是一类重要的低秩矩阵计算问题．给定矩阵 M ∈ Rm×n，将它分解成低秩矩阵 X 和稀疏矩阵 S，使得 X + S = M，同时尽量使得矩阵 X 的秩和矩阵 S 的 ℓ0 范数都比较小。

• 目标：此模型目标是在图像处理中最大程度地去除原有数据中的噪声，寻找数据在低维空间上的最佳投影。
• 应用举例：视频分割问题，此问题是指把人们感兴趣的对象从视频场景中提取出来，例如分割出一段视频中的静止部分。
  视频的每一帧实际上是一个静态图片，虽然每幅图片中的静止对象可能受到光照变化、遮挡、平移、噪声等影响，造成不同图片之间有细微差别，但是不可否认的是它们彼此之间具有高度的相似性。
  如果把所有图片中的静止部分表示成一个矩阵，显然它们是相似的，并且由于静止对象具有一定的内部结构，由静止对象构成的矩阵一定是低秩的（各行或各列线性相关）。
  类似地，视频中的动态部分以及其他背景因素可以看作噪声．那么我们的任务就变成将视频含有的信息矩阵分解为含有内部结构的低秩矩阵和稀疏噪声矩阵之和。
  

2.6 字典学习

字典学习的目的就是将已有的（超）大规模的数据集进行压缩，找到蕴藏在这些数据点背后的最基本的原理。字典学习模型不同于多元线性回归模型，我们需要在字典学习模型中同时解出字典 D 和系数 x。

• 线性模型：a = Dx + e
  $D\in R^{m\times k}$ 是某个未知的字典，它的每一列 di 是字典的一个基向量，x是字典中基的系数，同样是未知的；e 是某种噪声。

2.7 K-均值聚类

聚类分析是统计学中的一个基本问题，其在机器学习、数据挖掘、模式识别和图像分析中有着重要应用。聚类分析的任务就是将一些无标签的数据点按照某种相似度来进行归类，进而从数据点本身来学习其内蕴的类别特征。

2.8 图像处理中的全变差(TV)模型

• 模型：对于定义在区域$\Omega \subset R^2$ 的函数 u(x,y)，其全变差$\Vert u{\Vert }_{TV}={\int }_{\Omega }\Vert Du\Vert dx$，其中梯度算子 D 满足$Du=(\frac{\partial u}{\partial x},\frac{\partial u}{\partial y}{)}^T$
  其中$\Vert Du\Vert$ 采用 ℓ1 范数，即$||Du|{|}_1=|\frac{\partial u}{\partial x}|+|\frac{\partial u}{\partial y}|$ 称对应的全变差是各向异性的；
  采用 ℓ2 范数，即$||Du|{|}_2=\sqrt{(\frac{\partial u}{\partial x}{)}^2+(\frac{\partial u}{\partial y}{)}^2}$ 称对应的全变差是各向同性的。

2.9 小波模型

小波分析是图像重构的另外一种方法．它通过不同尺度变化对失真图像进行多尺度分析，进而保留想要的尺度信息，去掉噪声等对应的干扰信息。小波分析的一个最重要的概念是小波框架，它是空间中基函数的推广。具体地，将图像理解成一个向量$x\in R^n$，令 $W\in R^{m\times n}$ 为小波框架。

• 常用基于小波框架的重构模型：
  1.分解模型：直接求解重构图像，其通过惩罚图像的小波系数的 ℓ1 范数来去除图像中不必要的噪声信息。其模型为：$$\underset{x\in R^n}{\min }\Vert \lambda \odot (Wx){\Vert }_1+\frac{1}{2}\Vert Ax-b{\Vert }_2^2$$ 其中 b 为实际观测的图像数据，$\lambda \in R^m$ 是给定的非负向量，⊙ 表示逐个分量相乘。
  2.合成模型：求解图像对应的小波系数来重构图像，其通过小波系数的ℓ1 范数来去除图像中不必要的噪声信息。其模型为：$$\underset{\alpha \in R^n}{\min }\Vert \lambda \odot \alpha {\Vert }_1+\frac{1}{2}\Vert A{W}^T\alpha -b{\Vert }_2^2$$。
  3.平衡模型：求解图像对应的小波系数来重构图像．在合成模型中，α 不一定对应于真实图像的小波系数，因此，平衡模型添加 $(I-W{W}^T)\alpha$的二次罚项来保证 α 更接近真实图像的小波系数，其模型为：$$\underset{\alpha \in R^n}{\min }\Vert \lambda \odot \alpha {\Vert }_1+\frac{1}{2}\Vert A{W}^T\alpha -b{\Vert }_2^2+\frac{k}{2}2\Vert (I-W{W}^T)\alpha {\Vert }_2^2$$ 其中 κ 为给定常数。

2.10 强化学习

推荐书籍：《强化学习（第2版）》
强化学习处理的实际问题千差万别，但是它们一般可以抽象出智能体（agent）和环境（environment）两个概念．智能体持续地与环境互动并从环境中学到经验和规则，如下图所示。智能体在状态 st 下执行动作 at后，环境根据其内在的规则回应，到达新的状态 st+1，奖励 rt+1，这个系统持续不断地重复这个过程，直到系统中止。
强化学习经常可以用马尔可夫决策过程（Markov decision process，MDP）来描述，在马尔可夫决策过程中，环境状态转移的概率只取决于当前的状态和动作，而与所有历史信息无关，环境所反馈的奖励的期望也只依赖于当前的状态和动作。
强化学习跟其他机器学习相比有如下不同点：

• 这个过程是无监督的．没有标签告诉智能体做什么动作是最好的，只有之前动作所获得的奖励会让智能体更偏向于执行某一类动作
• 环境给智能体动作的反馈是有延迟的．当前动作的效果也许不会立刻体现，但是它可能影响许多步后的奖励
• 时间顺序在强化学习中是非常重要的．所做决策的顺序将会决定最终的结果
• 智能体所做的动作会影响观察到的环境状态．在这个学习过程中观察到的环境状态或接收到的反馈不是独立的，它们是智能体动作的函数，这一点与监督学习中的样本独立性假设有很大差别。