【算法工程师的数学基础】系列将会从线性代数、微积分、数值优化、概率论、信息论五个方面进行介绍,感兴趣的欢迎关注【搜索与推荐Wiki】公众号,获得最新文章。

《算法工程师的数学基础》已更新:


概率论主要研究的是大量随机现象中的数学规律,应用十分广泛,比如贝叶斯、多分类等。

样本空间

样本空间是一个随机实验所有可能结果的集合。比如在抛硬币实验中,样本空间为:{正面,反面};掷骰子实验中,样本空间为:{1,2,3,4,5,6}。随机实验中的每个可能结果都称为样本点。

有些实验可能包含两个或者多个样本空间。比如在扑克牌的抽取实验中,样本空间可以是数字A到K,也可以是花色(红黑方梅)。此时,如果需要完整的描述一张扑克牌,需要花色+数字,这时样本空间可以通过构建上述两个样本的笛卡尔积来得到。

样本空间中的样本涉及 总体方差和样本方差分母为$N、N-1$以及无偏估计问题,这里我们简单进行说明。

  • 总体方差(variance):总体中变量离其平均值距离的平均。比如一组数据$x_1, x_2, …, x_n$,则其方差表达式为:

  • 样本方差(variance):样本中变量离其平均值距离的平均。比如一组样本数据为$x_1, x_2, …, x_n$,则其方差表达式为:

到这你可能会想:为什么样本方差中分母是n-1而不是n?直接的原因是:样本方差已经利用到n个数,在求方差时,只有$n-1$个数和均值信息是不相关的,即第$n$个数可以有其余的$n-1$个数和均值来唯一确定,实际上并没有什么信息量。所以在计算方差时,分母是$n-1$。

下面从公式上解释一下,这里假设样本方差$S^2$的分母为$n$。

从公式推理上可以看出,如果分母是$n$的话得到的方差会比总体的方差小那么一点。接下来进行一个修正,上述公式两边同时乘上$\frac{n}{n-1}$得:

进行转化如下:

所以$\frac{1}{n-1}\sum_{i=1}^{n}(x_i - \bar x)$是总体方差得无偏估计量,而不能使用$\frac{1}{n}\sum_{i=1}^{n}(x_i - \bar x)$

事件和概率

随机事件(或简称事件)指的是一个被赋予概率的事物集合,也就是样本空间中的一个子集。概率表示一个随机事件发生可能性的大小,为0到1之间的一个非负实数。比如0.5表示一个事件有50%的可能性发生。

对于一个机会均等的抛硬币事件来讲,其样本空间为正面或者负面,我们可以定义各个随机事件,并计算其概率。比如:

  • {正面}:概率为0.5
  • {负面}:概率为0.5
  • 空集:即不是正面,也不是负面,概率为0
  • {正面 | 负面}:正面或者负面,概率为1

随机变量

在随机实验中,实验的结果可以用一个数X表示,这个数X是随着实验结果的不同而变化的,是样本点的一个函数,我们把这种数称为随机变量。例如随机投掷一枚骰子,得到的点数就可以看作是一个随机变量X,X的取值为$\{1,2,3,4,5,6\}$。

如果投掷两枚骰子,整个事件空间$\Omega$可以由36个元素组成:

一个随机事件也可以定义多个随机变量。比如在掷两个骰子的随机实验中,可以定义随机变量$X$为获得的两个骰子的点数和,也可以定义随机变量$Y$为获得的两个骰子的点数差。随机变量$X$可以有11个整数值,而随机变量Y只有6个。

离散型随机变量

如果随机变量$X$所有可能取的值为有限可列举的,有n个有限取值:$\{x_1,…,x_n\}$,则称$X$为离散型随机变量。

要了解$X$的统计规律,就必须要知道他取每种可能取值的$x_i$的概率,即:

$p(x_1),…,p(x_n)$称为离散型随机变量$X$的概率分布(Probability Distributuin)或分布,并且满足:

常见的离散型随机变量概率分布有:

  • 伯努利分布
  • 二项分布

伯努利分布
在一次实验中,事件$A$出现的概率为$\mu$,不出现的概率为$1- \mu$,若用变量$X$表示事件$A$出现的次数,则$X$的取值为0或1,其相应的分布为:

这个分布称为伯努利分布(Bernoulli Distribution),又名两点分布或者0-1分布。

二项分布
在$n$项伯努利分布中,若以变量$X$表示事件$A$出现的次数,则$X$的取值为:$\{0,1,2,3,…,n\}$,其相应的分布为二项分布(Binomial Distribution)。

其中$\binom{n}{k}$为二项式系数(这就是二项式分布的名称的由来),表示从$n$个元素中取出$k$个元素而不考虑其顺序的组合的总数。

连续型随机变量

与离散型随机变量不同,一些随机变量$X$的取值是不可列举的,由全部实数或者由一部分区间组成,比如:

则称$X$为连续随机变量,连续随机变量的值是不可数或者无穷尽的。

对于连续型随机变量$X$,他取一个具体值$x_i$的概率为0,这和离散随机变量截然不同,因此用列举连续随机变量取某个值的概率来描述这种随机变量不但做不到,也毫无意义。

连续随机变量$X$的概率分布一般用概率密度函数(probability density function,PDF)$p(x)$来描述,$p(x)$为可积函数,并满足:

给定概率密度函数$p(x)$,便可以计算出随机变量落入某一区间的概率,而$p(x)$本身反映了随机变量取值落入$x$的非常小的邻近区间中的概率大小。

常见的连续随机变量的概率分布有:

  • 均匀分布
  • 正态分布

均匀分布

若$a,b$为有限数,则$[a,b]$上的均匀分布(uniform distribution)概率密度函数定义为:

正态分布
正态分布(Normal Distribution),又名高斯分布(Guassian Distribution),是最常见的一种分布,并且具有很多良好的性质,其概率密度函数为:

其中$\sigma>0$,$\mu,\sigma$均为常数。若随机变量$X$服从一个参数为$\sigma$和$\mu$的概率分布,简记为:$X~N(\mu, \sigma^2)$,其中$\mu$为均值,$\sigma^2$为方差。

当$\mu=0, \sigma=1$称为标准正态分布(Standard Normal Distribution)。

均匀分布和正态分布的图像如下图所示:

均匀分布和正态分布的图像

累积分布函数

对于一个随机变量$X$,其累积分布函数(Cumulative Distribution Function,CDF)是随机变量$X$的取值小于等于$x$的概率。

以随机变量$X$为例,累积分布函数定义为:

其中$p(x)$为概率密度函数,下图给出了标准正态分布的累积分布函数:
标准正态分布的累积分布函数

随机向量

随机向量是指一组随机变量构成的向量,如果$[x_1,x_2,…,x_n]$为$n$个随机变量,那么称$[x_1,x_2,…,x_n]$为一个$n$维随机向量,一维随机向量称为随机变量。

随机向量也分为离散随机向量和连续随机向量。

离散随机向量

离散随机变量的联合概率分布(Joint Probability Distribution)为:

其中$x_i \in w_i$为变量$X_i$的取值,$w_i$为变量$X_i$的样本空间。

和离散随机变量类似,离散随机向量的概率分布满足:

多项分布
一个常见的离散随机向量概率分布为多项分布(Multinomial Distribution),多项分布是二项分布在随机向量的推广。假设一个袋子中装了很多球,总共有$K$个不同颜色,我们从袋子中取出$n$个球,每次取出一个球时,就在袋子中放入一个同样颜色的球,这样保证同一颜色的球在不同实验中被取出的概率是相等的。

令$X$为一个$K$维随机向量,每个元素$X_k(k=1,2,3,…,K)$为取出的$K$个球中颜色为$k$的球的数量,则$X$服从多项分布,其概率分布为:

其中$\mu=[\mu_1, …, \mu_K]^T$分别为每次抽取的球的颜色为1,…,$K$的概率,$x_1,…,x_K$为非负整数,并且满足$\sum_{k=1}^{K}x_k=n$。

多项分布的概率分布也可以用gamma函数表示:

其中$\Gamma(z) = \int_{0}^{\infty}\frac{t^{z-1}}{exp(t)}d(t) $为gamma函数,这种表示形式和Dirichlet分布类似,而Derichlet分布可以作为多项分布的共轭先验。

连续随机向量

连续随机向量的联合概率密度函数(Joint Probability Density Function)满足:

多元正态分布
一个常见的连续随机向量分布为多元正态分布(Multivariate Normal Distribution),也称为多元高斯分布(Multivariate Gaussian Distribution)。若$n$维随机向量$X=[X_1, …, X_n]^T$服从$n$元正态分布,其密度函数为:

其中$\mu$为多元正态分布的均值向量,$\Sigma$为多元正态分布的协方差矩阵,$|\Sigma|$表示$\Sigma$的行列式。

各项同性高斯分布

如果一个多元高斯分布的协方差矩阵简化为$\Sigma=\sigma^2 I$,即每一维随机变量都独立并且方差相同,那么这个多元高斯分布称为各项同性高斯分布(Isotropic Guassian Distribution)

Dirichlet分布

一个$n$维随机向量$X$的Dirichlet分布为:

其中$a=[a_1, …, a_K]^T$为Dirichlet分布的参数。

边际分布

对于二维离散随机向量$(X,Y)$,假设$X$取值空间为$\Omega_x$,$Y$取值空间为$\Omega_y$,其联合概率分布满足

对于联合概率分布$p(x,y)$,我们可以分别对$x$和$y$进行求和。

(1)对于固定的$x$:$\sum_{y \in \Omega_y} p(x,y)=P(X=x)=p(x)$

(2)对于固定的$y$:$\sum_{x \in \Omega_x} p(x,y)=P(Y=y)=p(y)$

由离散随机向量$(X,Y)$的联合概率分布,对$Y$的所有取值进行求和得到$X$的概率分布,而对$X$的所有取值进行求和得到$Y$的概率分布。这里$p(x),p(y)$就称为$p(x,y)$的边际分布(Marginal Distribution)。

对于二维连续随机向量$(X,Y)$,其边际分布为:

一个二元正态分布的边际分布仍为正态分布。

条件概率分布

对于离散随机向量$(X,Y)$,已知$X=x$的条件下,随机变量$Y=y$的条件概率(Conditional Probability)为:

这个公式定义了随机变量$Y$关于随机变量$X$的条件概率分布(Conditional Probability Distribution),简称条件分布。

对于二维连续随机向量$(X,Y)$,已知$X=x$的条件下,随机变量$Y=y$的条件概率密度函数(Contidional Probability Density Function)为:

同理,已知$Y=y$的条件下,随机变量$X=x$的条件概率密度函数为:

通过上边的两个公式,我们可以得到两个条件概率$p(y|x)$和$p(x|y)$之间的关系。

这个公式称为贝叶斯定理(Bayes’ theirem)或者贝叶斯公式。

独立与条件独立

对于两个离散(或连续)随机变量$X,Y$,如果其联合概率(或联合概率密度函数)$p(x,y)$满足:

则称$X,Y$相互独立(independence),记为$X \perp Y$

对于三个离散(或连续)随机变量$X,Y,Z$,如果条件概率(或联合概率密度函数)$p(x,y|z)$满足:

则称在给定变量$Z$时,$X,Y$条件独立(conditional independence)记为:$X \perp Y \perp Z$

期望和方差

期望

对于离散变量$X$,其概率分布为$p(x_1), …, p(x_n)$,$X$的期望(expection)或均值定义为:

对于连续随机变量$X$,概率密度函数为$p(x)$,其期望定义为:

方差
随机变量$X$的方差(variance)用来定义他的概率分布的离散程度,定义为:

随机变量$X$的方差也称为他的二阶距。$\sqrt{var(X)}$称为$X$的根方差或标准差。

协方差

两个连续随机变量$X,Y$的协方差(covariance)用来衡量两个随机变量的分布之间的总体变化性,定义为:

协方差经常也用来衡量两个随机变量之间的线性相关性。如果两个随机变量的协方差为0,那么称这两个随机变量是线性不相关。两个随机变量之间没有线性相关性,并非表示它们之间独立的,可能存在某种非线性的函数关系。反之,如果$X,Y$是统计独立的,那么它们之间的协方差一定为0。

协方差矩阵

两个$m$和$n$维连续随机向量$X$和$Y$,它们的协方差(covariance)为$m*n$的矩阵,定义为:

协方差矩阵$cov(X,Y)$的第$(i,j)$个元素等于随机变量$X_i$和$Y_j$的协方差。两个向量变量的协方差$cov(X,Y)$与$cov(Y,X)$互为转置关系。

如果两个随机向量的协方差矩阵为对角阵,那么称这两个随机向量时无关的。

单个随机向量$X$的协方差矩阵定义为:

随机过程

随机过程(Stochastic Process)是一组随机变量$X_t$的集合,其中$t$属于一个索引(index)集合$\tau$。索引集合$\tau$可以定义在时间域或者空间域,但一般为时间域,以实数或正数表示。当$t$为实数时,随机过程为连续随机过程;当$t$为整数时,为离散随机过程。

日常生活中的很多例子包括股票的波动、语音信号、身高的变化等都可以看作是随机过程。常见的和时间相关的随机过程模型包括:伯努利分布过程、随机游走、马尔可夫过程等。和空间相关的随机过程常称为随机场(Random Field)。比如一张二维的照片,每个像素点(变量)通过空间的位置进行索引,这些像素就组成了一个随机过程。

马尔可夫过程

马尔科夫性质

在随机过程中,马尔科夫性质(Markov Property)是指一个随机过程在给定现在状态及所有过去状态情况下,其未来状态的条件概率分布仅依赖于当前状态。

以离散随机过程为例,假设随机变量$X_0,X_1,…,X_T$构成一个随机过程。这些随机变量的所有可能取值的集合被称为状态空间(State Space)。如果$X_{t+1}$对于过去状态的条件概率分布仅是$X_t$的一个函数,则:

其中$X_0:t$表示变量集合$X_0, X_1, …, X_t$,$x_{0:t}$为状态空间中的状态序列。

马尔可夫性质也可以描述为给定当前状态时,将来的状态与过去状态是条件独立的。

马尔可夫链
离散时间的马尔可夫过程也称为马尔可夫链(Markov Chain)。如果一个马尔可夫链的条件概率为:

在不同时间都是不变的,即和时间$t$无关,则称为时间同质的马尔可夫链(Time Homogeneous Markov Chain)。如果状态空间是有限的,$T(s_i, s_j)$也可以用一个矩阵$T$表示,称为状态转移矩阵(Transition Matrix),其中元素$t_{ij}$表示状态$s_i$转移到状态$s_j$的概率。

平稳分布假设状态空间大小为$M$,向量$\pi = [\pi_1, …, \pi_M]^T$为状态空间中的一个分布,满足$0 \geq \pi_i \geq 1$和$\sum_{i=1}^{M}\pi_i = 1$。

对于状态转移矩阵为$T$的时间同质的马尔可夫链,如果存在一个分布$\pi$满足:

即分布$\pi$就称为该马尔可夫链的平稳分布(Stationary Distribution)。根据特征向量的定义可知,$\pi$为矩阵$T$的(归一化)的对应特征值为1的特征向量。

如果一个马尔可夫链的状态转移矩阵$T$满足所有状态可遍历性以及非周期性,那么对于任意一个初始状态分布$\pi^{(0)}$,将经过一定时间的状态转移之后,都会收敛到平稳分布,即:

细致平稳条件(Detailed Balance Condition) 如果一个马尔可夫链满足:

则一定会收敛到平稳分布$\pi$。

细致平稳条件保证了从状态$i$转移到状态$j$的数量和从状态$j$转移到状态$i$的数量相一致,相互抵消,所以数量不发生改变。

细致平稳条件只是马尔可夫链收敛的充分条件,不是必要条件。

高斯过程

高斯过程(Gaussian Process)

高斯过程也是一种应用广泛的随机过程模型。假设有一组连续随机变量$X_0, X_1,…,X_T$,如果由这组随机变量构成的任一有限集合:

都服从一个多元正态分布,那么这组随机变量为一个随机过程。高斯过程也可以定义为:如果$X_{t_1,…,t_k}$的任一线性组合都服从一元正态分布,那么这组随机变量为一个随机过程。

高斯过程回归
高斯过程回归(Gaussion Process Regression)是利用高斯过程来对一个函数分布进行建模。和机器学习中参数化建模(比如贝叶斯线性回归)相比,高斯过程是一种非参数模型,可以拟合一个黑盒函数,并给出拟合结果的置信度。

假设一个未知函数$f(x)$服从高斯过程,且为平滑函数。如果两个样本$x_1,x_2$比较接近,那么对应的$f(x_1), f(x_2)$也比较接近。假设从函数$f(x)$中采样有限个样本$X=[x_1, x_2, …, x_N]$,这$N$个点服从一个多元正态分布,记作:

其中$\mu(X)=[\mu(x_1), \mu(x_2), …, \mu(x_N)]^T$是均值向量,$K(X,X)=[k(x_i, x_j)]_{N*N}$是协方差矩阵,$k(x_i, x_j)$为核函数,可以衡量两个样本的相似度。

在高斯过程回归,一个常用的核函数是平方指数(Squard Exponential)函数:

其中$l$为超参数。当$x_i$和$x_j$越接近,其核函数的值越大,表明$f(x_i)$和$f(x_j)$越相关。

假设$f(x)$的一组带噪声的观测值为$\{ (x_n, y_n)\}_{n=1}^{N}$,其中$y_n \sim N(f(x_n), \sigma^2)$为正态分布,$\sigma$为噪声方差。

对于一个新的样本点$x^$,我们希望预测函数$y^=f(x^)$。令$y=[y_1, y_2,…,y_n]$为已有的观测值,根据高斯过程的假设,$[y; y^]$满足:

其中$K(x^, X)=[k(x^, x_1), …, k(x^*, x_n)]$。

根据上面的联合分布,$y^*$的后验分布为:

其中均值$\tilde {\mu}$和方差$\tilde{\sigma}$为:

从上面的公式可以看出,均值函数$\mu(x)$可以近似地互相抵消。在实际应用中,一般假设$\mu(x)=0$,均值$\tilde{\mu}$可以化简为:

高斯过程回归可以认为是一种有效的贝叶斯优化方法,广泛地应用于机器学习中。


【技术服务】,详情点击查看: https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg


扫一扫 关注微信公众号!号主 专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!