机器学习数学基础：无约束优化

老齐

发布于 2021-05-20 10:28:27

4320

发布于 2021-05-20 10:28:27

文章被收录于专栏：老齐教室老齐教室

本文为《机器学习数学基础》补充资料，《机器学习数学基础》一书预计2021年6月份由电子工业出版社出版。

定义

给定一个目标函数（或称成本函数）

f:\mathbb{R}^n \to \mathbb{R}

，无约束优化（uncontrained optimization）是指找到

\pmb{x}\in\mathbb{R}^n

使得

f(\pmb{x})

有最小值，即：

\min_{\pmb{x}\in\mathbb{R}^n}f(\pmb{x})

若希望找到最大值，将目标函数前面加负号即可。

通常，寻找

f(\pmb{x})

的局部最小值，即在某个范围内的最小值。

单变量的目标函数

令

f:D\to\mathbb{R}

为一个定义于

D \subseteq\mathbb{R}

的光滑可导函数，其中

是一个开集，根据泰勒定理：

f(x)=f(y)+f'(y)(x-y)+\frac{f''(y)}{2}(x-y)^2+O(|x-y|^3)\tag{1.1}

若

f'(y)=0

，则

为

的一个驻点（stationary point），或称临界点（critical point）。

当

是驻点时，若

|x-y|

足够小，则（1.1）式近似为：

f(x)-f(y)\approx \frac{f''(y)}{2}(x-y)^2 \tag{1.2}

如果

f''(y)=0

，则

为一个局部最小值（local minimum），即：存在一个

\delta\gt0

，对有所

满足

|x-y|\le\delta

都有

f(y)\le f(x)

。

如果

f''(y)\lt0

，则

为一个局部最大值（local maximum）。

如果

f''(y)=0

，必须计算

f(x)

和

f(y)

的值才能决定。

所以，驻点是函数

的一个局部最小值的必要条件。

多变量的目标函数

令

\pmb{x} = \begin{bmatrix}x_1&\cdots&x_n\end{bmatrix}^{\rm{T}}

为

的变量，

f(\pmb{x})

为定义域

\pmb{D}\subseteq\mathbb{R}^{\rm{n}}

的可导实函数，根据泰勒定理，得：

\begin{split}f(\pmb{x})=&f(\pmb{y})+\sum_{i=1}^n\frac{\partial f}{\partial x_i}\bigg|_{\pmb{y}}(x_i-y_i)\\&+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\frac{\partial^2f}{\partial x_i\partial x_j}\bigg|_{\pmb{y}}(x_i-y_i)(x_j-y_j)+O(\begin{Vmatrix}\pmb{x}-\pmb{y}\end{Vmatrix}^3)\end{split}\tag{1.3}

函数

在点

\pmb{y}

的梯度

^{[2]}

：

\nabla f(\pmb{y})=\begin{bmatrix}\frac{\partial f}{\partial x_1}\bigg|_{\pmb{y}}\\\vdots\\\frac{\partial f}{\partial x_n}\bigg|_{\pmb{y}}\end{bmatrix}

在

\pmb{y}

点的黑塞矩阵（Hessian）

^{[2]}

：

[H(\pmb{y})]_{ij}=\frac{\partial^2 f}{\partial x_i\partial x_j}\bigg|_{\pmb{y}}

则式（1.3）可以写成：

f(\pmb{x})=f(\pmb{y})+(\nabla f(\pmb{y}))^{\rm{T}}(\pmb{x}-\pmb{y})+\frac{1}{2}(\pmb{x}-\pmb{y})^{\rm{T}}H(\pmb{y})(\pmb{x}-\pmb{y})+O(\begin{Vmatrix}\pmb{x}-\pmb{y}\end{Vmatrix}^3)\tag{1.4}

若

\pmb{y}

是一个驻点，即

\nabla f(\pmb{y})=\pmb{0}

，当

\begin{Vmatrix}\pmb{x}-\pmb{y}\end{Vmatrix}

足够小，（1.4）式化为：

f(\pmb{x})-f(\pmb{y})\approx\frac{1}{2}(\pmb{x}-\pmb{y})^{\rm{T}}H(\pmb{y})(\pmb{x}-\pmb{y}) \tag{1.5}

因为：

\frac{\partial^2f}{\partial x_i\partial x_j}=\frac{\partial^2f}{\partial x_j\partial x_i}

所以

H(\pmb{y})

是一个对称矩阵。

H(\pmb{y})

是正定的，即

\pmb{z}^{\rm{T}}H(\pmb{y})\pmb{z}\gt0

，则

\pmb{z}\ne0

，

\pmb{y}

是

的一个局部最小值。

H(\pmb{y})

是负定的，

\pmb{y}

是

的一个局部最大值。

H(\pmb{y})

是未定的，称

\pmb{y}

是鞍点（saddle point）。

梯度下降法是寻找函数局部最小值的常用方法，具体参阅参考文献[2]。

参考文献

[1]. 线代启示录：最佳化理论与正定矩阵

[2]. 齐伟. 机器学习数学基础. 北京：电子工业出版社. （预计2021年6月出版）

---------

《机器学习数学基础》简介

本书就是要帮助读者将已经灌注在大脑里的“高数内功”激发出来——注意不是重新“灌输”一遍。所以，本书所介绍数学内容不是“高数”的翻版，而是默认读者已经将一些最基本的高等数学知识内化了。我只是根据个人经验，遴选与机器学习有关的内容，唤起读者大脑中沉睡已久的“数学潜意识”，引导读者大胆地进入机器学习领域。

按照这样的目的，对本书内容做了如下安排：

不将微积分的有关内容作为独立章节，因为这些内容在“高数”中是重点。但为了避免遗忘，本书的附录和在线资料中，分别提供了有关微积分的基本知识。
以机器学习的直接需要为标准，选择基本的数学内容，从工程应用的角度给予介绍。一般数学教材因聚焦于严谨的数学内容而忽略了工程应用，而一般的机器学习资料又缺乏相关的数学基本概念介绍——甚至有不少不合“数学之理”的地方，学习者看后仅“知其然”，但“不知其所以然”，乃至于“茫然不知所措”。本书的定位就是在二者之间，帮助读者打通数学基本概念和机器学习的工程实践。所以，读者会在数学知识之后，会看到它们的如何在机器学习中应用。
书中省略了一些严格的数学证明，这是本书不同于数学教材的重要方面，但这并不意味着数学证明不重要。如果读者对有关数学证明感兴趣，可以参阅本书提供的在线资料。

再次强调，不要将本书当做数学教材，本书不会面面俱到地介绍高等数学内容。

所以，当读者阅读本书的时候，不会看到常规数学教材的样子：定理、简要说明、例题、习题。而是更像一个有点数学经验的人给你介绍他自己的心得体会，因此，这本书就不会侧重于“解题”技能的训练，书中也会大量演示一些手工计算，必要的手工计算演示是为了帮助理解某些概念，更复杂的计算，都会用编程语言实现——本书采用Python语言，但书中并不会介绍这种语言的使用方法，请读者自行解决编程语言问题（我在这方面有几本书，推荐读者参阅）。

如果不进行拣选，针对机器学习的数学内容，不是一本书能够涵盖的——太厚的书会让人。但考虑到不同读者有不同的需要，因此会在本书的在线资料上发布补充内容，包括但不限于：