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

机器学习概述

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

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

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

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

微积分

夹逼定理

当$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$，那么

$\lim_{x\to x_0}f(x)=A$

方向导数

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

$\frac{\partial f}{\partial l} = \frac{\partial f}{\partial x}cos\phi+\frac{\partial f}{\partial y}sin\phi$

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

梯度

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

$(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})$

为函数$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$，定义

$E(X^n)=\int p(x)x^ndx$

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

$lim_{n\rightarrow\infty}P(|\bar X_n-\mu|>\epsilon)=0$

中心极限定理

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

$Z_n=\frac{\sqrt{n}}{\sigma}(\bar X_n-\mu)$

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

$lim_{n\rightarrow\infty}P(Z_n< z)=\Phi(z),\forall z$

其中$\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)=(1-\theta)·(-1)+\theta·1=2\theta-1$ $E(X^2)=(1-\theta)·1+\theta·1=1$

我们看到一阶矩$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(θ)=\prod_{i=1}^nL_{x_i}(θ)$
$这是一个关于θ的函数, 选取使得L_x(θ)最大化的(\hat θ)作为θ的估计量.$

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

$\frac{dl(θ)}{dθ}=0, (或者\frac{dL(θ)}{dθ}=0)$

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

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

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

$L(\mu,σ)=\prod_{i=1}^n\frac1{\sqrt {2π}σ}exp(−\frac{(x-\mu)^2}{2σ^2})$ $l(\mu,σ)=C-\frac{1}{2σ^2}\sum_{i=1}^n(x_i-\mu)^2-\frac{n}{2}ln(σ^2)$

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

$a=\frac{1}{n}\sum_{i=1}^nx_i$ $σ^2=\frac{1}{n}\sum_{i=1}^nx_i$

因此得到极大似然估计量

$\hat a=\overline X$ $\hat σ^2=\frac{1}{n}\sum_{i=1}^n(x_i-\overline X)^2$

点估计的评判准则

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

区间估计：置信区间

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

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

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

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

矩阵

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

基本演算

转置与逆

$(A+B)^T=A^T+B^T$ $(AB)^T=B^TA^T$ $(A^T)^{-1}=(A^{-1})^T$ $(AB)^{-1}=B^{-1}A^{-1}$

迹

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

$tr(A^T)=tr(A)$ $tr(A+B)=tr(A)+tr(B)$ $tr(AB)=tr(BA)$ $tr(ABC)=tr(BCA)=tr(CAB)$

行列式

$det(cA)=c^ndet(A)$ $det(A^T)=det(A)$ $det(AB)=det(A)det(B)$ $det(A^{-1})=det(A)^{-1}$ $det(A^n)=det(A)^n$

Frobenius范数

$||A||_F=(tr(A^TA))^{1/2}=(\sum_{i=1}^m\sum_{j=1}^nA_{ij}^2)^{1/2}$

导数

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

$(\frac{\partial a}{\partial x})_i=(\frac{\partial a_i}{\partial x})$ $(\frac{\partial x}{\partial a})_i=(\frac{\partial x}{\partial a_i})$

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

$(\frac{\partial A}{\partial x})_{ij}=\frac{\partial A_{ij}}{\partial x}$ $(\frac{\partial x}{\partial A})_{ij}=\frac{\partial x}{\partial A_{ij}}$

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

$(\nabla f(x))_i=\frac {\partial f(x)}{\partial x_i}$

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

$(\nabla ^2f(x))_{ij}=\frac{\partial ^2f(x)}{\partial x_i \partial x_j}$

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

$\frac{\partial x^Ta}{\partial x}=\frac{\partial a^Tx}{\partial x}=a$ $\frac{\partial AB}{\partial x}=\frac{\partial A}{\partial x}B+A\frac{\partial B}{\partial x}$

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

$\frac{\partial A^{-1}}{\partial x}=-A^{-1}\frac{\partial A}{\partial x}A^{-1}$

另外地，

$\frac{\partial Ax}{\partial x}=A^T$ $\frac{\partial x^TA}{\partial x}=A$ $\frac{\partial x^Tx}{\partial x}=2x$ $\frac{\partial x^TAx}{\partial x}=Ax+A^Tx=2AX$

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

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

$\frac{\partial tr(AB)}{\partial A_{ij}}=B_{ji}$ $\frac{\partial tr(AB)}{\partial A}=B^T$ $\frac{\partial tr(A^TB)}{\partial A}=B$ $\frac{\partial tr(A)}{\partial A}=I$ $\frac{\partial tr(ABA^T)}{\partial A}=A(B+B^T)$ $\frac{\partial ||A||_F^2}{\partial A}=\frac{\partial tr(AA^T)}{\partial A}=2A$ $\nabla_A trAB = B^T$ $\nabla_{A^T}f(A)=(\nabla_Af(A))^T$ $\nabla_AtrABA^TC=CAB+C^TAB^T$ $\nabla_A|A| = |A|(A^{-1})^T$

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

$\frac{\partial f(x)}{\partial x}=\frac{\partial g(h(x))}{\partial h(x)}·\frac{\partial h(x)}{\partial x}$

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

$\begin{align*} \frac{\partial}{\partial x}(Ax-b)^TW(Ax-b) &=\frac{\partial (Ax-b)}{\partial x}·2W(Ax-b) \\ &=2AW(Ax-b) \end{align*}$

奇异值分解

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

$A=U\Sigma V^T$

其中，$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$。

线性代数

线性映射与矩阵

矩阵时线性映射在特定基下的一种定量描述
$T(\alpha)=\beta·A_{\alpha,\beta}(T)$
基变换下的矩阵变换公式的推导方法
$Q·A_{\tilde \alpha,\tilde \beta}(T)·P^{-1}=A_{\alpha,\beta}(T)$

自身映射

实数平面$\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)
$\begin{align*} det(P^{-1}AP) &=det(P^{-1})det(A)det(P) \\ &=det(P^{-1})det(P)det(A) \\ &=det(A) \end{align*}$
迹(trace)
$tr(AB)=tr(BA)$ $\begin{align*} tr(P^{-1}AP) &= tr(APP^{-1}) \\ &=tr(A·I) \\ &=tr(A) \end{align*}$
秩(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}$. 使得
$B=PDQ$
其实$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.$

$λx_1 + (1 − λ)x_2 \in Ω, \forall x_1,x_2 \in Ω,λ \in (0,1)$

凸函数定义

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

$f(λx_1 + (1 − λ)x_2) ≤ λf(x_1) + (1 − λ)f(x_2)$ $\forall x_1,x_2 \in Ω,λ \in (0,1)$

凸函数的判定

定理：$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$，则线性组合

$S =\sum_{i=1}^n\omega_ix_i$

为一个凸组合。凸组合的物理意义可以理解成 $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$都有

$\sum_{i=1}^n\omega_if(x_i) ≥ f(\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^*(y)=sup_{x\in domf}(y^Tx-f(x))$

其中$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个不等式约束

$min_x f(x)$ $s.t. h_i(x)=0 (i=1,...,m),$ $g_j(x) \leq 0(j=1,...,n).$

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

$L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m\lambda_ih_i(x)+\sum_{i=1}^n\mu_jg_j(x)$

KKT条件为

$g_j(x) \leq 0;$ $\mu_j \geq 0;$ $\mu_jg_j(x)=0.$

递推式时间复杂度

$T(n)=aT(\frac{n}{b})+O(n^d)$ $T(n)=\left\{ \begin{aligned} & O(n^{log_ba}),d<log_ba \\ & O(n^dlog\space n) ,d=log_ba\\ & O(n^d),d>log_ba \end{aligned} \right.$