1.1　机器学习中的优化问题举例

机器学习中的优化问题十分常见．我们给出两个代表性的例子，第一个是分类/回归问题中常用的正则化的经验损失模型，第二个是数据处理中常用的低秩学习模型．

1.1.1　正则化的经验损失模型

给定m个样本，其中xi表示第i个样本的特征，表达为一个向量，yi表示第i个样本所属的类别，用独热（One-hot）向量来表示．我们希望从训练数据中学习一个映射函数p（x；w），使得给定xi，映射函数可以给出其对应的yi，即p（xi；w）=yi，其中w是映射函数p的参数．如果使用全连接神经网络来表达该映射，则

p（x；w）=ϕ（WLϕ（WL-1…ϕ（W1x）…）），　（1.1）

其中Wk表示第k层网络的权重矩阵，k=1，…，L，ϕ是激活函数．我们希望学习到一组参数w={W1，…，WL}，使得神经网络能够尽可能地拟合训练数据．为此，我们通过求解下述模型来学习参数w：

如果可以找到参数w使得，那么该神经网络可以完美地拟合训练数据，即将训练数据中的所有输入都映射到其对应的输出．越小，模型对训练数据的拟合能力越强．因此，给定一个机器学习模型，我们需要找到一组好的参数w．“优化”则用于寻找这组好的参数．

上述模型可以推广到更一般的形式，即正则化的经验损失模型．很多分类/回归问题可以建模成如下形式

其中w是分类/回归模型的参数，维数为n，p（x；w）是学习模型中的预测函数，l是损失函数，用于衡量模型预测和真实结果之间的差异，（xi，yi）是第i个样本，R是正则化项，用于表达关于参数w的先验知识，λ≥0是权重因子．

损失函数l（p，y）的典型例子包括用于多分类的二次损失函数l（p，y）=以及用于二分类的逻辑斯蒂（Logistic）损失函数l（p，y）=log（1+exp（-py））和合页（Hinge）损失函数l（p，y）=max{0，1-py}．预测函数p（x；w）的典型例子包括用于线性分类/回归的p（x；w）=wTx-b和用于深度神经网络中前向传播的（1.1）．正则化项R（w）的典型例子包括ℓ2正则化项和ℓ1正则化项R（w）=‖w‖1．

损失函数、预测函数和正则化项的不同组合产生不同的机器学习模型．例如，合页损失函数、线性分类函数和ℓ2正则化项的组合得到支持向量机（SVM）［Cortes and Vapnik，1995］，逻辑斯蒂损失函数、线性预测函数和ℓ2正则化项的组合得到正则化的逻辑斯蒂回归问题［Berkson，1944］，二次损失函数、前向传播函数的组合（无正则化项）得到多层感知机模型（1.2）［Haykin，1999］，二次损失函数、线性回归模型和ℓ1正则化项的组合得到LASSO模型［Tibshirani，1996］．

在有监督机器学习中，我们通过在训练数据上求解机器学习模型（1.3），得到该模型的参数w，然后固定参数w，通过预测函数p（x；w）来预测未知测试数据对应的分类标签或回归值．

1.1.2　矩阵填充及低秩学习模型

除了（1.3），机器学习中也存在很多其他形式的训练模型．例如在信号处理和数据挖掘中被广泛使用的矩阵填充模型可以写成如下形式

其中Ω表示矩阵所有被观测到的元素的位置的集合．子空间聚类问题中的低秩矩阵表示模型［Liu et al.，2010］可以写成如下形式

为了节省计算时间和存储空间，研究者根据一个低秩矩阵可以表达成两个更小矩阵的乘积这一特性，即X = UVT，将矩阵填充（Matrix Completion）问题重新建模成如下非凸模型

其中Ui：和Vj：分别为U、V的第i行和第k行．

从优化的角度分类，在上述模型中，（1.3）是无约束优化问题，（1.4）和（1.5）是带约束凸优化问题，而（1.6）是非凸优化问题．因此，机器学习中有多种多样的优化问题．读者若需要了解更多的机器学习中的优化问题，可参考由Gambella、Ghaddar和Naoum-Sawaya写的综述［Gambella et al.，2021］．