机器学习的数学基础

来源:https://www.bilibili.com/video/av15673238/

机器学习概述


该图说明了编程能力、数学统计知识和专业知识之间的关系。

  1. 大多数人刚入门的人都是编程能力和数学统计知识相结合的,这样被称为“机器学习(Machine Learning)”,大致指的是机器学习里的典型算法和典型模型;
  2. 而传统的学术研究者一般都是数学统计知识和专业知识相结合;
  3. 编程能力和专业知识相结合,被称为“危险区域”,有待商榷,但是没有什么典型的例子;
  4. 三者结合为数据科学家,即可以将机器学习的理论知识应用到工业中,有实际的领域和方向应用,发挥作用。

该图展示的是机器学习算法里主要的三大分类。

该图展示的是机器学习的主要算法。按列分为监督学习和无监督学习,根据样本是否拥有标签判断;按行分为离散和连续,根据样本的属性值判断。

微积分

夹逼定理

当$x \in U(x_0,r)$时,有$g(x)\leq f(x)\leq h(x)$成立,并且$\lim_{x\to x_0}g(x)=A$,$\lim_{x\to x_0}h(x)=A$,那么

方向导数

如果函数$z=f(x,y)$在点$P(x,y)$是可微分的,那么,函数在该点沿任一方向$L$的方向导数都存在,且有:

其中,$\phi$为x轴到方向$L$的转角。

梯度

设函数$z=f(x,y)$在平面区域$D$内具有一阶连续偏导数,则对于每一个点$P(x,y) \in D$,向量

为函数$z=f(x,y)$在点$P$的梯度,记做$gradf(x,y)$。梯度的方向是函数在该点上升最快的方向,相反方向为该点下降最快的方向。

概率论

概率公式

条件概率:$P(A|B) = \frac{P(AB)}{P(B)}$
全概率公式:$P(A) = \sum_i P(A|B_i)P(B_i)$
贝叶斯(Bayes)公式:​
$P(B_i|A) = \frac{P(A|B_i)P(B_i)}{\sum_j P(A|B_j)P(B_j)}$

概率与统计

大二的时候上“概率论与数理统计”,一学期上完,一脸懵逼,搞不清楚这门课到底讲的什么。
B站这门课看到这里恍然大悟,一张图说明:

  • 概率:根据是否已知整体进行区分

  • 统计:统计问题是概率问题的逆向工程

  • 两者结合:监督学习

简单地说,由已知样本去估计全体,再由全体去预测未知样本。

统计量

期望

  • 离散型:$E(X)=\sum_i x_ip_i$
  • 连续型:$E(X)=\int_{-\infty}^{\infty}xf(x)dx$

方差

  • 定义:$Var(X)=E\{[X-E(X)]^2\}=E(X^2)-E^2(X)$
  • 性质:
    $Var(c)=0$
    $Var(X+c)=Var(X)$
    $Var(kX)=k^2Var(X)$

  • X和Y独立:$Var(X+Y)=Var(X)+Var(Y)$

协方差

  • 定义:$Cov(X,Y)=E\{[X-E(X)][Y-E(Y)]\}$
  • 性质:
    $Cov(X,Y)=Cov(Y,X)$
    $Cov(aX+b,cY+d)=acCov(Y,X)$
    $Cov(X_1+X_2,Y)=Cov(X_1,Y)+Cov(X_2,Y)$
    $Cov(X,Y)=E(XY)-E(X)E(Y)$

协方差表示的是两个向量之间的线性关系,无法处理非线性关系。

相关系数

先验分布与后验分布

http://blog.sina.com.cn/s/blog_b9a335010102vfdf.html

$X$是一个随机变量对于任何正整数$n$,定义

当$n=1$时,$E(X)$为随机变量的期望

当$n=2$时,$E(X^2)-E(X)^2$为随机变量的方差

特征函数,$E(e^{itX})=\sum_{n=0}^\infty \frac{E(X^n)}{n!}(it)^n$

样本k阶矩:$\alpha_k(X)=\frac{1}{n}\sum_{i=1}^nX_i^k,m_k(X)=\frac{1}{n}\sum_{i=1}^n(X_i-\overline X)^k$

总体k阶矩:$\alpha_k(X)=E(X^k),\mu_k(X)=E((X-E(X))^k)$

矩可以描述随机变量的一些特征,期望是$X$“中心”位置的一种描述,方差可以描述$X$的分散程度,特征函数可以全面描述概率分布。

大数定律

$X$是随机变量,$\mu$是$X$的期望,$\sigma$是$X$的方差。$\{X_k\}_{k=1}^\infty$是服从X的独立同分布随机变量,那么$\bar X_n=\frac{\sum_{k=1}^nX_k}{n}$依概率收敛于$\mu$。也就是说对于任何$\epsilon>0$有

中心极限定理

$X$是随机变量,$\phi(X)$是$X$的特征函数。$\{X_k\}_{k=1}^\infty$是服从$X$的独立同分布随机变量,那么

依分布收敛于正态分布$N(0,1)$。
也就是说对于任何$\epsilon>0$有

其中$\Phi$是标准正态分布的分布函数。

参数估计问题

已知一个随机变量的分布函数$Xf_\theta(x)$,其中$\theta=(\theta_1,…,\theta_k)$为未知参数。

样本$X_1,…,X_n$

利用样本对参数$\theta$做出估计,或者估计$\theta$的某个函数$g(\theta)$

点估计:用样本的一个函数$T(X_1,…X_n)$去估计$g(\theta)$

区间估计:用一个区间去估计$g(\theta)$

点估计

矩估计

基本原理:大数定律


e.x.(两点分布的参数估计)
$X$服从两点分布取值为$\{-1,1\}$,$P(-1)=1-\theta$,$P(1)=\theta$。现在独立重复实验$n$次,得到样本$X_1,…,X_n$。请利用矩估计来估计参数$\theta$。
首先考虑哪一个矩可以用来估计参数$\theta$。对于两点分布来说

我们看到一阶矩$E(X)$与$\theta$有简单直接的关系$\theta=\frac{1+E(X)}{2}$
所以我们使用一阶样本矩估计。得到一个参数估计量$\hat{\theta}=\frac{1+\bar X}{2}$

极大似然估计

给定随机变量的分布与未知参数,利用观测到的样本计算似然函数,选择最大化似然函数的参数作为参数估计量。
基本原理:最大化似然函数

假设样本$\{X_1,···,X_n\}$服从概率密度函数$f_θ(x)$. 其中$θ=(θ_1,···,θ_k)$是未知参数. 当固定$x$的时候, $f_θ(x)$就是$θ$的函数, 我们把这个函数称为似然函数, 记为$L_x(θ)$ 或 $L(θ)$. 假设$x=(x_1,···,x_n)$是样本的观测值. 那么整个样本的似然函数就是

$这是一个关于θ的函数, 选取使得L_x(θ)最大化的(\hat θ)作为θ的估计量.$

最大化似然函数θ, 相当于最大化似然函数的对数, $lx(θ) = ln(Lx(θ))$. 一般我们求解似然函数或者对数似然函数的驻点方程

然后判断整个驻点是否最大点. (求驻点可以用牛顿法, 或者梯度法等等)


e.x.(正态分布的参数估计)

$X$服从参数为$θ=(\mu,σ)$的正态分布, 独立重复实验$n$次得到样本$X_1,···,X_n$. 请利用极大似然估计来估计参数$θ$。

所以似然方程为$\frac{\partial l}{\partial σ}=\frac{\partial l}{\partial \mu}=0$, 也就是

因此得到极大似然估计量​

点估计的评判准则

  • 相合性(consistency):当样本数量趋于无穷时,估计量收敛于参数真实值。
  • 无偏性(bias):对于有限的样本,估计量所符合的分布之期望等于参数真实值。
  • 有效性(efficiency):估计值所满足的分布方差越小越好。
  • 渐进正态性(asymptotic normality):当样本趋于无穷时,去中心化去量纲化的估计量符合标准正态分布。

区间估计:置信区间

置信区间可以认为是点估计的一个扩展。分为如下扩展:

  1. 找到一个点估计$T$
  2. 找出一个$T$与$θ$的函数满足某一个已知的分布$F$
  3. 利用这个已知的分布$F$的$\frac{α}{2}$分位数,来求出参数的置信区间

如果这个分布$F$很难找到,那么还有一种近似的方法:

  1. 找到一个点估计$T$
  2. 利用渐进正态的性质,发现$T$在$n$很大的时候满足某种正态分布
  3. 利用这个已知的正态分布的$\frac{α}{2}$分位数,来求出参数的置信区间

矩阵

摘自周志华老师《机器学习》的附录。

基本演算

转置与逆

对于$n$阶方阵A,它的迹(trace)是主对角线上的元素之和,即$tr(A)=\sum_{i=1}^nA_{ii}。迹有如下性质:$

行列式

Frobenius范数

导数

向量$a$相对于标量$x$的导数(derivative),以及$x$相对于$a$的导数都是向量,其第$i$个分量分别为

类似的,矩阵$A$对于标量$x$的导数,以及$x$对于$A$的导数都是矩阵,其第$i$行第$j$列上的元素分别为

对于函数$f(x)$,假定其对向量的元素可导,则$f(x)$关于$x$的一阶导数是一个向量,其第$i$个分量为

$f(x)$关于$x$的二阶导数是称为海森矩阵(Hessian matrix)的一个方阵,其第$i$行第$j$列上的元素为

向量和矩阵的导数满足乘法法则(product rule)

由$A^{-1}A=I$和上式,逆矩阵的导数可表示为

另外地,

(后半部分的条件是A对称)

若求导的标量是矩阵$A$的元素,则有

链式法则(chain rule)是计算复杂导数时的重要工具。简单地说,若函数$f$是$g$和$h$的复合,即$f(x)=g(h(x))$,则有

例如在计算下式时,将$Ax-b$看作一个整体可简化计算:

奇异值分解

任意实矩阵$A \in \mathbb {R}^{m×n}$都可分解为

其中,$U \in \mathbb {R}^{m×m}$是满足$U^TU=I$的$m$阶酉矩阵(unitary matrix);$V \in \mathbb {R}^{n×n}$是满足$V^TV=I$的$n$阶酉矩阵;$\Sigma \in \mathbb {R}^{m×n}$是$m×n$的矩阵,其中$(\Sigma)_{ii}=\sigma_i$且其他位置的元素均为$0$,$\sigma_i$为非负实数且满足$\sigma_1 \geq \sigma_2 \geq … \geq0$。

线性代数

线性映射与矩阵

  • 矩阵时线性映射在特定基下的一种定量描述

  • 基变换下的矩阵变换公式的推导方法

自身映射

实数平面$\mathbb {R}^2$到自身的映射:

  • 拉伸T:$[\begin{matrix}x_1\\x_2\end{matrix}]=[\begin{matrix}1/2 & 0 \\0 & 2\end{matrix}][\begin{matrix}x_1\\x_2\end{matrix}]$
  • 反转T:$[\begin{matrix}x_1\\x_2\end{matrix}]=[\begin{matrix}1 & 0 \\0 & -1\end{matrix}][\begin{matrix}x_1\\x_2\end{matrix}]$
  • 旋转T:$[\begin{matrix}x_1\\x_2\end{matrix}]=[\begin{matrix}cos(\pi/6) & -sin(\pi/6) \\sin(\pi/6) & cos(\pi/6)\end{matrix}][\begin{matrix}x_1\\x_2\end{matrix}]$

相似矩阵

如果两个方阵$A$和$\tilde A$满足$\tilde A=P^{−1}AP$,那么这两个方阵就互为相似矩阵。相似矩阵的几何意义是同一个线性变换在不同的基下的表达形式。

相似变换下不变的性质

  • 行列式(det)

  • 迹(trace)

  • 秩(rank)

  • 特征值:特征方程$det(A-\lambda)I)=0$的根。
    如果$det(A-\lambda I)=0$,那么$det(P^{-1}(A-\lambda I)P)=0$,于是$det(P^{-1}AP-\lambda I)=0$。

相合变换

如果两个对称方阵$A$和$\tilde A$满足,$\tilde A=P^TAP$。 那么这两个方阵就互为相合矩阵。相合矩阵的几何意义是同一个内积结构在不同积下的表示形式。

正交相似变换

正交相似变换同时满足相似与相合变换的条件,也就是说它同时保持了矩阵的相似与相合不变量。

  • 如果两个对称方阵$A$和$\tilde A$满足,$\tilde A=P^TAP$. 而且$P$是正交矩阵: $P^T=P^{-1}$. 那么这$A$与$\tilde A$就互为正交相似。
  • 任何一个对称矩阵$A$都可以正交相似于一个对角矩阵$D$。即,总存在一个正交矩阵$P$使得,$A=P^TDP$。

SVD

  • 长方矩阵的奇异值分解(SVD)
    对于任何一个矩阵$B_{m×n}$, 存在正交矩阵$P_{m×m},Q_{n×n}$. 使得

    其实$D_{m×n}$是一个只有对角元素不为零的矩阵.

优化与凸优化

优化问题

优化问题的一般形式
最小化:$f_0(x)$,
条件:$f_i(x) \leq b_i,i=1,…,m$,
其中$f_0(x)$为目标函数,条件里的不等式是限制条件。

凸优化问题

一个优化问题如果满足如下条件则为凸优化问题

  • 凸优化问题的条件,$f_0,f_1,…,f_m$都是凸函数.

  • 凸优化问题的特点,局部最优等价于全局最优.​

凸集合定义

如果一个集合$Ω$中任何两个点之间的线段上任何一个点还属于$Ω$, 那么 $Ω$ 就是一个凸集合。$i.e.$

凸函数定义

如果一个函数 $f$ 定义域$Ω$ 是凸集,而且对于任何两点. 以及两点之间线段上任意一个点都有

凸函数的判定

定理:$f(x)$在区间$[a,b]$上连续,在$(a,b)$内二阶可导,那么:
若$f’’(x) > 0$,则$f(x)$是凸的;
若$f’’(x) < 0$,则$f(x)$是凹的。
即:一元二阶可微的函数在区间上是凸的,当且仅当它的二阶导数是非负的。

函数的上境图

假设 $f$ 是一个定义在 $Ω$ 上的函数,区域$\{(x,y):y≥f(x),\forall x \in Ω\}$就是$f$的上境图。上境图就是函数图像上方的部分区域。

凸集合与凸函数

一个函数是凸函数当且仅当 $f$ 的上境图是凸集合。

凸组合

对于任何n个点$\{x_i\}_{i=1}^n$,以及权重系数$\{\omega_i\}_{i=1}^n$。若权重系数非负$\omega_i ≤ 0$ 而且$\sum_{i=1}^n\omega_i = 1$,则线性组合

为一个凸组合。凸组合的物理意义可以理解成 $n$ 个重量为 $\omega_i$ 的点的整体重心。

集合的凸包

$n$个点$\{x_i\}_{i=1}^n$的全部凸组合就构成$\{x_i\}_{i=1}^n$的凸包。

函数的凸闭包

如果$C$是函数$f$的上境图,$\overline C$是$C$的凸包,那么以$\overline C$为上境图的函数称为$f$的凸闭包。

集合的凸包的性质

若$\overline C$是$C$的凸包,那么

  • $C \subset \overline C$
  • $C$的支撑平面也是$\overline C$的支撑平面,反之亦然

函数的凸闭包的性质

若$g$是$f$的凸闭包,那么

  • $g \leq f$
  • $inf\{g\}=inf \{f\}$

凸集合性质

  • 假设 $Ω$ 是一个凸集合,那么 $Ω$ 任何子集的凸包仍包含于 $Ω$。
  • 任意多个凸集合的交集仍是凸集合。

凸函数性质:琴生 (Jensen) 不等式

如果 $f : Ω \rightarrow \mathbb {R}$ 是一个凸函数, 则对于任何 $\{x_i \in Ω\}_{i=1}^n$, 以及凸组合$\sum_{i=1}^n \omega_ix_i$都有

凸函数性质

  • 任意多个凸函数的逐点上确界仍是凸函数。​
  • 固定一个凸函数的若干个变量,所得的函数仍然是凸函数。​
  • 凸函数的 sublevel set 都是凸集合。​

凸集分离定理

若$C,D$分别为$\mathbb {R}^n $中的两个不交的非空凸集合,i.e.$C \cap D = ∅$,则一定存在向量$ a \in \mathbb {R}^n $以及实数 $b \in \mathbb {R}$ 使得任何

$x_C \in C, x_D \in D$ 有 $a^Tx_C ≤ b $以及 $a^Tx_D ≥ b.$

定理中不等式的几何意义在于$C,D$ 分别位于超平面 $a^Tx=b$ 的两边.

共轭函数

如果$f:\mathbb {R}^n \rightarrow \mathbb {R}$是一个函数,那么$f$的共轭函数

其中$f^x(y)$的定义域是使得等式右边有上界的那些$y$.

共轭函数的基本性质

  • 共轭函数$f^-$是一个凸函数
  • 如果$g$是$f$的凸闭包,那么$g^-=f^-$
  • 对一般的函数$f$,$ f^{—} \leq f$
  • 如果$f$是一个凸函数, 那么$f^{—}=f$

共轭函数的进一步性质

  • $f(x)+f^-(y) \geq x^Ty$
  • 如果$f$是凸函数而且可微,那么
  • $f^x(y)=x^T\nabla f(x^-)-f(x^-),其中x^-满足\nabla f(x^-)=y$
  • 如果$g(x)=f(Ax+b)$,则$g^-(y)=f^-(A^{-T}y)-b^TA^{-T}y$
  • 如果$f(u,v)=f_1(u)+f_2(v)$,那么$f^-(w,z)=f_1^-(w)+f_2^-(z)$

对偶函数

对偶函数为原问题提供下界。

Karush-Kuhn-Tucker(KKT)条件

m个等式约束和n个不等式约束

引入拉格朗日乘子$\lambda=(\lambda_1,\lambda_2,…,\lambda_m)^T和\mu=(\mu_1,\mu_2,…,\mu_n)^T$, 相应的拉格朗日函数为

KKT条件为

递推式时间复杂度

一分一毛也是心意