机器学习数学基础以及数值计算数值优化方法

Posted on Edited on In
Symbols count in article: 7.3k Reading time ≈ 7 mins.

以下内容由我的CSDN博客迁移。

正值假期，决定恶补机器学习、深度学习及相关领域（顺便开个博客）。首先学习一下数学基础以及数值计算的方法（主要参考《深度学习》）

一、数学基础

这里简单复习一下机器学习相关的数学

1.线性代数

范数 衡量一个向量的大小,对Lp范数，有： \[\left\| x\right\| _{p}=\left( \sum_{i}\left| x_{i}\right| ^{p}\right) ^{\dfrac {1}{p}}\] 其中 \(p\in \mathbb{R} , p\geq1\). 对一切范数（包括Lp），满足下列性质：

  • \(t\left( x\right) =0\Rightarrow x=0;\)

  • \(f\left( x+y\right) \leq f\left( x\right) +f\left( y\right);\)(三角不等式）

  • \(\forall \alpha \in \mathbb{R} ,f\left( ax\right) =\left| a\right| f\left( x\right).\)

  1. L0范数指的是向量中非零元素的个数
  2. L1范数可以用于机器学习中0与非0元素之间的差异十分重要时。也能让模型变得更加稀疏。（常替代L0）
  3. 最大范数：L∞范数 表示向量中具有最大幅值元素的绝对值。\(\left\| x\right\| _{\infty }=\max_{i}\left| x\right|_i\)
  4. 要衡量矩阵的大小，最常用的是使用Frobenius范数,即\(\left\| A\right\| _{F}=\sqrt {\sum_{i,j}A^{2} _{i,j}}\).

进一步学习： L0、L1、L2范数在机器学习中的应用 范数对于数学的意义？1范数、2范数、无穷范数

正交矩阵 行向量和列向量是分别标准正交的方阵 \[\begin{aligned}AA^{T}=I;\\ A^{-1}=A^{T}\end{aligned}\]

特征分解 特征分解可以知晓一些矩阵隐含的性质。

  • 特征向量：与\(A\)相乘后相当于对该向量进行缩放的非零向量\(v\) \[Av=\lambda v\] 其中λ为特征向量对应的特征值。（通常指右特征向量） 由于\(kv\)与\(v\)y特征值相同，一般情况下只考虑单位特征向量。
  • 若\(A\)有n个线性无关的特征向量\(\left\{ v^{(1)},v^{(2)},\ldots ,v^{\left( n\right) }\right\}\)，对应n个特征值\(\{\lambda_1,\lambda_2,\ldots,\lambda_n\}\)。将特征向量连接成一个矩阵，使得每一列都是一个特征向量\(V=[v^{(1)},v^{(2)},\ldots ,v^{( n)}]\)特征值也连接成一个向量λ。 \(A\)的特征分解指 \[A=Vdiag\left( \lambda \right) V^{-1}\]

机器学习中通常不会遇到复数的特征分解，一般我们会处理实对称矩阵，它一定可以分解为\(A=Q\Lambda Q^{T}\) 其中\(Q\)为正交矩阵，由\(A\)的特征向量组成。

  • 矩阵是奇异的等价于矩阵含零特征值
  • 矩阵特征值非负称半正定矩阵，满足\(\forall x, x^TAx\geq0\).

奇异值分解(SVD) 另一种分解矩阵的方式，将矩阵分解为奇异向量和奇异值。每个实数矩阵都有奇异值分解，因此它比特征分解应用更广。\[A=UDV^T\]

若\(A\)是\(m\times n\),则\(D\)是\(m\times m\)，\(U\)是\(m\times n\)，\(V\)是\(n\times n\)。

  • \(U、V\)是正交矩阵，两者的列向量分别是左奇异向量和右奇异向量。事实上，\(D\)就是\(AA^T\)的特征向量，\(V\)就是\(A^TA\)的特征向量。
  • \(D\)称为奇异值，为对角矩阵（不一定方阵），事实上是\(A^TA\)或\(AA^T\)的特征值的平方根。

奇异值分解(SVD)原理详解及推导

Moore-Penrose伪逆 对于非方矩阵，若希望求方程\(Ax=y\)，也就是要找一矩阵使得 \(x=By\)，这时可以用伪逆去求解。 定义为\[A^{+}=\lim _{\alpha\searrow 0}(A^TA+\alpha I)^{-1}A^T\]

但实际上使用下面这个公式计算 \[A^+=VD^+U^T \Leftrightarrow A^+=(svd (A))^+\]

其中\(D^+\)是非零元素取倒数再转置得到的。

  • 当\(A\)的行数多于列数时，可能没有解。此时通过伪逆得到的\(x\)使得\(Ax\)与\(y\)的欧氏距离最小。
  • 当\(A\)的行数少于列数时。此时通过伪逆得到的\(x=A^+y\)是所有可行解中L2范数最小的。

迹运算 \[Tr(A) = \sum_{i}A_{i,i}\] 有些矩阵运算可以通过矩阵乘法和迹运算表示，省去了求和符号。 eg :
\[\|A\|_F=\sqrt{Tr(AA^T)}\]

性质：

  • \(Tr(A) =Tr(A^T)\)
  • \(Tr(ABC)=Tr(BAC)\) 循环置换 尽管形状变了但值依然不变。
  • \(Tr(AB)=Tr(BA)\)
  • 对标量 \(Tr(a)=a\)

行列式 记作\(det(A)\),将方阵映射到实数，等于特征值的乘积。可以衡量矩阵参与矩阵乘法后空间扩大或缩小了多少。若行列式是0.则可认为空间至少沿着某一维完全收缩了。若是1则转换保持空间体积不变。

一个机器学习算法应用小实例：主成分分析 如何通俗易懂地讲解什么是 PCA 主成分分析？

2.概率论

基本概念

  • 频率派概率：概率直接与频率关联
  • 贝叶斯概率：涉及确定性水平
  • 概率质量函数（PMF)：离散型随机变量的概率分布
  • 概率密度函数（PDF)：连续型随机变量的概率分布
  • \(x⊥y\)表示两个事件相互独立，\(x⊥y|z\)表示二者条件独立
  • 期望：\(x\)由\(P\)生成，当\(f\)作用于\(x\)时，\(f(x)\)的平均值
  • 方差：随机变量函数呈现的差异大小
  • 协方差：两个变量的线性相关强度 随机向量\(x \in\mathbb{R}^n\)的协方差矩阵是\(n\times n\)的矩阵并且有 \[Cov(x)_{i,j}=Cov(x_i,x_j)\]

高斯分布 当缺乏对某个实数分布的先验知识时，正态分布是默认的较好的选择。原因：

  • 中心极限定理说明很多独立的随机变量的和近似服从于正态分布。
  • 在具有相同方差的所有可能的概率分布中，正态分布在实数上具有最大的不确定性。（熵最大）
多维正态分布

混合分布 通过简单的概率分布的组合来生成更丰富的分布 eg(组件的分布取决于一个范畴分布）: \[P(x)=\sum_{i}P(c=i)P(x|c=i)\] 高斯混合模型（GMM) 是一个万能近似器，即任何概率密度都可以用足够多组件的GMM来逼近。

注意：概率论的一些结论对于连续型随机变量实际上由测度论得只能是几乎处处成立

3.信息论

我们使用信息论来描述概率分布或量化概率分布的相似性。

  • 信息论的基本思想：一个较不可能的事的发生比一个很可能的事情的发生会提供更多信息。为了量化信息，规定：

    1. 非常可能发生的事情信息量很少，且极端情况下无信息量。
    2. 较不可能发生的事提供更多信息。
    3. 独立事件有增量的信息。

  • 规定一个事件\(x\)的自信息为：\(I(x)=-\log P(x)\) 这里令log为自然对数，因此自信息的单位是奈特（nats)。（以2为底的单位就是比特或者香农）

  • 对于整个概率分布的不确定性总量，我们用香农熵衡量： \[H(x)=\mathbb{E}_{x\sim P}[I(x)]=-\mathbb{E}_{x\sim P}[\log P(x)]\] 也记作\(H(P)\)。一个分布的香农熵是指遵循这个分布的事件所产生的期望信息总量。x是连续的时候，香农熵又被称为微分熵

  • 若对于一个随机变量x有两个单独的概率分布\(P(x)、Q(x)\)我们可以用KL 散度衡量两个分布的差异： \[D_{KL}(P\| Q)=\mathbb{E}_{x\sim P}[\log \dfrac{P(x)}{Q(x)}]\]

    KL散度是非对称的，但由于它非负，常被用来测量两个分布的“距离”，这意味着如果要令一个分布\(q\)近似分布\(p\)，那么抉择是最小化\(D_{KL}(P\| Q)\)或者\(D_{KL}(Q\| P)\)是很重要的

  • 交叉熵：\(H(P,Q)=H(P)+D_{KL}(P\| Q)=-\mathbb{E}_{x\sim P}\log Q(x)\)针对Q的最小化交叉熵过程相当于最小化KL散度。

  • 信息论中规定\(\lim _{x\rightarrow 0}x\log x=0\)

二、数值计算

1. 溢出

计算机表示实数总会有一些误差，因此我们在设计算法时应该考虑到最小化舍入误差的积累。

  • 下溢：当接近0的数被舍为0时发生。很多函数在输入为0时会发生严重错误。

  • 上溢：当大量级的数被近似为\(\infty\)时发生

    很多底层的库在设计时就考虑了很多溢出的情况，可以自动保持数值稳定。

2. 病态条件

条件数指函数对于输入的微小变化而变化的快慢程度。当条件数很大时，舍入误差会对数值造成很大的影响。此时就是病态条件。 [数值计算] 条件数

3. 基于梯度的优化方法

我们常常会最小化多变量输入函数\(f:\mathbb{R^n\rightarrow R}\)，函数输出是一个标量，此时这个函数称为目标函数或者准则（机器学习中也叫损失函数等）

  • 梯度是针对一个向量求导的导数，包含所有偏导，记为\(\nabla_x f(\boldsymbol{x})\)
  • 对于单位向量\(\boldsymbol{u}\)的方向导数是函数\(f\)在\(\boldsymbol{u}\)方向上的斜率，即\(f(x+\alpha u)\)关于α的导数（α=0时取得）。即\(\dfrac {\partial }{\partial \alpha }f(\boldsymbol{x}+\alpha \boldsymbol{u})=\boldsymbol{u}^T\nabla_x f(\boldsymbol{x})\)

为了最小化\(f\)，我们要找到使它下降最快的方向，计算方向导数： \[\min_{u,u^Tu=1}\boldsymbol{u}^T\nabla_x f(\boldsymbol{x})=\min_u \cos \theta\]

即\(\boldsymbol{u}\)与梯度方向相反时取得最小。因此这被称为梯度下降法或者最速下降法 \[x^\prime=x-\epsilon\nabla_x f(\boldsymbol{x})\]

其中\(\epsilon\)为学习率，确定步长大小。

  • 梯度下降也可以扩展到离散空间，此时称为爬山算法

4.Jacobian和Hessian矩阵

对于输入和输出都为向量的函数，它的所有偏导数的矩阵称为Jacobian矩阵。定义为\(J_{i,j}=\dfrac{\partial}{\partial x_j}f(\boldsymbol{x})_i\) 有时我们也会考察二阶导数，它反映了只基于梯度信息的梯度下降步骤的效果，也是对曲率的衡量。负曲率使函数下降更快，正曲率更慢。 \(H(f)(\boldsymbol{x})_{i,j}=\dfrac{\partial^2}{\partial x_i \partial x_j}f(\boldsymbol{x})\) 相当于梯度的Jacobian矩阵。

  • 在深度学习中，Hessian矩阵大多为实对称矩阵，因此可将其分解为一组特征值和特征向量的正交基。在方向\(\boldsymbol{d}\)上的二阶导数可以写成\(\boldsymbol{d}^T\boldsymbol{Hd}\)。通过方向二阶导数可以预期一个梯度的下降步骤表现得多好。
  • 二阶导数还可以用于确定临界点是否局部极值点或是鞍点，当一阶导为0而二阶导非0时就是极值点，而二阶导也为0时不能确定。这称为二阶导数测试。
  • 在多维情况下我们观察Hessian矩阵的特征值，若是正定矩阵则为极小值。然而多数情况下特征值由正有负，则该点应当是鞍点。 另外，每个方向的二阶导数是不相同的。Hessian矩阵的条件数衡量这些二阶导数的变化范围。可以避免梯度下降步长太大以至于冲过最小点，又不至于使步长太小使曲率小的方向进展不明显。

因此我们可以用Hessian矩阵的信息来指导搜索（直接找到局部最优点），主要有牛顿法等。现实中Hessian矩阵很难计算，因此有许多近似方法，具体不在这里详述了。这类二阶优化算法很容易被吸引到鞍点。 牛顿法、拟牛顿法（BFGS），L-BFGS算法

注：由于深度学习中的函数族十分复杂，因此深度学习算法往往缺乏理论保证（炼丹).可以通过限制函数或其导数满足Lipschitz连续,其中\(\mathcal{L}\)称为Lipchitz常数，满足： \[||\nabla f(x) - \nabla f(y)|| \leq \mathcal{L} || x - y||,~~~x,y\in R^n\] 可以描述为：函数\(f(x)\)二次可微，且Hessian矩阵在 \(R^n\)上有界。Lipschitz连续对分析复杂函数非常有用，因为它可以近似将优化复杂函数的问题，转化为二次规划问题。 同时很多优化问题可以经过微小的修改就满足利普希茨连续。

5. 约束优化

若希望在x的某些集合中寻找\(f(x)\)的最大或最小值，称为约束优化，集合\(\mathbb{S}\)内的点x称为可行点

  • 一种简单的想法是将约束考虑在内并对梯度下降进行修改，即将梯度下降的结果投影回 \(\mathbb{S}\) 内
  • 另一种是设计一个不同的无约束优化问题，使其解可以转化为原始优化问题的解。 Karush-Kuhn-Tucker(KKT)方法是一个通用的方法，是对Lagrange乘子法的推广.
    • 广义Lagragian定义为 \[L(\boldsymbol{x,\lambda,\alpha})=f(\boldsymbol{x})+\sum_i\lambda_ig^{(i)}(\boldsymbol{x})+\sum_j\alpha_jh^{(j)}(\boldsymbol{x})\]
    其中\(g^{(i)}\)为等式约束，\(h^{(j)}\)为不等式约束（\(h^{(j)}(x)\leq0\)）。\(\alpha_j、\lambda_i\)称为KKT乘子。

因此我们可以通过求解\(\boldsymbol{\min_x\max_\lambda\max_{\alpha,\alpha\geq0}}L(\boldsymbol{x,\lambda,\alpha})\)来获得与\(\min_{x\in \mathbb{S}}f(x)\)相同的解（只要有一个不使\(f(x)\)取无穷的可行点）。对于最大化相当于求负的最小化。

  • KKT条件 确定一个点是最优点的必要条件，但不一定是充分条件。具体有：
    1. 广义Lagrangian的梯度为零。
    2. 所有关于x和KKT乘子的约束都满足 3. 不等式约束显示的”互补松弛性“：\(\boldsymbol{\alpha\odot h(x)=0}\). 即对每一对\(\alpha、h(x)\)，必有一个是活跃的（为零）

6. 拉格朗日对偶性

在约束最优化问题中，我们常利用拉格朗日对偶性将原始问题转换为对偶问题。

  • 原始问题： \[\boldsymbol{\min_x\max_\lambda\max_{\alpha,\alpha\geq0}}L(\boldsymbol{x,\lambda,\alpha})\] 称为广义拉格朗日函数的极小极大问题，记\(p^*\)为原始问题的最优值。

  • 对偶问题： \[\boldsymbol{\max_\lambda\max_{\alpha,\alpha\geq0}\min_x}L(\boldsymbol{x,\lambda,\alpha})\] 称为广义拉格朗日函数的极大极小问题，记\(d^*\)为对偶问题的最优值

  • 原始问题与对偶问题的关系： 定理1：若原始问题和对偶问题都有最优值，则 \[d^*=\boldsymbol{\max_{\lambda,\alpha:\alpha\geq0}\min_x}L(\boldsymbol{x,\lambda,\alpha})\leq\boldsymbol{\min_x\max_{\lambda,\alpha:\alpha\geq0}}L(\boldsymbol{x,\lambda,\alpha})=p^*\]

推论1：当\(d^*=p^*\)时，它们都取相同的最优点。 在某些条件下，原始问题和对偶问题的最优值相等，具体有：

  • 定理2：若函数\(f(x)\)和不等式约束\(h^{(j)}\)是凸函数，等式约束\(g^{(i)}\)是仿射函数（即最高次数为1的多项式函数）；并且假设不等式约束是严格可行的，即存在\(x\),对所有\(i\)有\(h^{(j)}<0\)成立。则存在\(x^*,\lambda^*,\alpha^*\)，使得\(p^*=d^*=L(x^*,\lambda^*,\alpha^*)\)
  • 定理3：若函数\(f(x)\)和不等式约束\(h^{(j)}\)是凸函数，等式约束\(g^{(i)}\)是仿射函数（即最高次数为1的多项式函数）；并且假设不等式约束是严格可行的。那么\(x^*,\lambda^*,\alpha^*\)是原始问题和对偶问题的解的充分必要条件是\(x^*,\lambda^*,\alpha^*\)满足KKT条件。

简单应用：线性最小二乘 最小二乘法#也可以简单的使用梯度下降求解 线性最小二乘和非线性最小二乘

以上内容如有谬误还请告知。之后还会持续更新（应该）