机器学习的数学基础

来源: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

$当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)

点估计

矩估计

基本原理:大数定律


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.(正态分布的参数估计)

$所以似然方程为\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条件为$

递推式时间复杂度

一分一毛也是心意