数学知识点整理

主要内容包括:

  1. 矩阵的中心化,归一化,标准化与正规化。
  2. 范数,包括向量的范数和矩阵的范数。协方差矩阵。
  3. PCA算法与详细证明。
  4. 置信区间和置信度

矩阵的中心化,归一化,标准化与正规化

很常见的机器学习中的概念。这里的矩阵是针对数据集来讲的,对于一个数据集合来讲,一共有n个数据,每个数据可以用k个维度表示(也就是每个数据是一个k长度的vector),那么就可以整合为一个k行n列的矩阵,每行是一个维度特征。

中心化

对于每个数据样本(也就是对矩阵的每一列单独处理),原数据除以该数据样本向量的均值。

归一化

归一化是数据scaling(缩放)中的一种,是把数据缩放到[0,1]或[-1,1]之间。常用的数据归一化方法是线性函数归一化,公式为:

其他scaling方式,譬如用标准差$\mu$除以列上的各个元素。


样例

下面是MATLAB上的样例,分别对应中心化,使用标准差的scaling,缩放到[0,1]的归一化。

标准化

矩阵标准化的目的是,得到均值为0,标准差为1的服从标准正态分布的数据。使得不同维度上的量纲统一调整。

$\mu$代表每一列的均值,$\sigma$代表每一列的标准差

正规化

正则化主要思想是对每个样本计算其p-范数,然后对该样本中每个元素除以该范数,这样处理的结果是使得每个处理后样本的p-范数之和等于1。

关于向量的范数计算方法见下


样例

分别是标准化,一范数正规化和二范数正规化之和的结果。

范数

范数有向量的范数和矩阵的范数。

向量的范数

一范数:$|x|_1=\sum\limits_{i=1}^{N}|x_i|$曼哈顿距离,向量元素绝对值之和。matlab调用函数norm(x, 1)
二范数:$|x|_2=\sqrt{\sum\limits_{i=1}^{N}|x_i|^2}$欧式距离, 向量元素绝对值的平方和开方。matlab调用函数norm(x, 2)
$\infty$范数:$|x|_\infty = \mathop{max}\limits_{i}|x_i|$所有向量元素绝对值中的最大值,matlab调用函数norm(x, inf)
-$\infty$范数:$|x|_{-\infty} = \mathop{min}\limits_{i}|x_i|$所有向量元素绝对值中的最小值,matlab调用函数norm(x, -inf)
更普遍的
p范数:$|x|_p=(\sum\limits_{i=1}^{N}|x_i|^p)^{\frac{1}{p}}$向量元素绝对值的p次方和的1/p次幂,matlab调用函数norm(x, p)

矩阵的范数

一范数:$|A|_1 = \mathop{max}\limits_j\sum\limits_{i=1}^m|a_{i,j}| $ 列和范数,即所有矩阵列向量绝对值之和的最大值。matlab调用函数norm(A, 1)。
二范数: $|A|_2 = \sqrt{\lambda_1}$,$\lambda$为$A^{T}A$的最大特征值谱范数,即$A^{T}A$矩阵的最大特征值的开平方。matlab调用函数norm(A, 2)。
$\infty$范数:$|A|_{\infty} = \mathop{max}\limits_i\sum\limits_{j=1}^{n}|a_{i,j}|$,行和范数,即所有矩阵行向量绝对值之和的最大值,matlab调用函数norm(A, inf)。
F范数:$|A|_F = \sqrt{\sum\limits_{i=1}^{m}\sum\limits_{j=1}^n|a_{i,j}|^2}$,Frobenius范数,即矩阵元素绝对值的平方和再开平方,matlab调用函数norm(A, ‘fro’)。

协方差矩阵

在统计学中方差是用来度量单个随机变量的离散程度,而协方差则一般用来刻画两个随机变量的相似程度。

其中,方差的计算公式为

其中,m代表样本量,符号$\overline{x}$表示样本的均值

下面看协方差的计算公式

公式中$\overline{x},\overline{y}$分别表示两个随机变量所对应的样本均值。

这里除以m-1不是除以m,是基于样本的无偏估计,m-1是修正方差。当然也有除以m的计算方法(初高中都是m)

所以方差视作随机变量$x$关于自身的协方差$\sigma(x,x)$。

对于一个矩阵,含有n个随机变量

它的协方差矩阵

下面以一个例子讲述基本计算步骤

求每个维度的均值

X的每一列减去对应的平均值

X乘以X的转置矩阵,求取协方差矩阵

相关系数矩阵

相关系数和协方差都是反映两变量之间的相关关系密切程度的指标

PCA降维

算法介绍

PCA(Principal Component Analysis)的流程。对于PCA的应用很多,信号数据的去噪处理,图片的压缩等等(把一张长为d宽为n的图片看成是d-dimension的n个数据点组成)。

algorithm PCA (P is a set of n points in d-dimensional space, now we need to convert P into a set P’ of points in a k-dimensional space, $k\leq d$)

algorithm PCA
output: k directional vectors

  • shift P such that its geometric mean is at the origin of the data space
  • A $\leftarrow$ the co-variance matrix of P
  • compute all the d unit eigenvectors
  • arrange the eigenvectors in descending order of their eigenvalues
  • return the first k eigenvectors $v1,…,vk$

Each point p in P is then converted to a k-dimensional point whose i-th($1\leq i\leq d$)coordinate is $v_i\cdot p$

计算样例

下面用个二维例子进行举例,点集(-2,-2)、(1,-1)、(-1,1)、(2,2),点集的几何中心就在数据空间原点(不用再进行预先调整) 求个这个点集的协方差矩阵是(这里为了计算方便,协方差的计算不使用无偏估计的方式,直接除以点集个数m)

对于x变量和y变量之间的协方差

对于x的方差或者y的方差(数值一样)

下面对上面的协方差矩阵求取特征值和特征向量

$I$是单位矩阵(identity matrix), $ I = {\left [ \begin{array}{ccc} 1 & 0 \\ 0 & 1 \end{array} \right ]}$

简单转化之后

也就是求解 $|A-\lambda I| = 0$

针对上面的协方差矩阵

求解得 $\lambda_1 = 4$ $\lambda_2 = 1$ 由于点集是二维,现在降为一维,使用从大到小前$k=1$个特征值,也就是把$\lambda_1 = 4$代入式子:

原理解释

那么我们来判断这一次转换的质量。对于k个dimension中的一个特定维度,让 $\overrightarrow{w}$作为一个对应的eigenvector方向的单位向量,把P映射到$\overrightarrow{w}$代表的方向上,$S = {\overrightarrow{p} \cdot \overrightarrow{w} \bracevert p \in P}$。在这个例子里,转化到一维度,由于例子里d=2,那么$\overrightarrow{w}$就是 $(\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2})$。 也就是我们现在把点集转移到x=y这条坐标上,那么原来的四个点变成一维度,集合S中的值分别为$-2 \sqrt{2}、0、0、2 \sqrt{2}$

对于每个d维度的点集P有n个点,转换到k维度之后,每个维度求得一个对应集合S,判断各维度信息保留质量的方式如下,variance()是进行求方差:

由于geometric mean已经调整为坐标原点。

对于点集P,它的大小是$n\times d$,构造出的协方差矩阵A的大小是$d\times d$,每个$\overrightarrow{w}$的大小是$d\times 1$,又由协方差矩阵的定义,上述quality的公式也可以转换为:

$\overrightarrow{w}$是单位向量,那么我们现在在$\overrightarrow{w^{T}}\overrightarrow{w} = 1$这个constraint下,尽可能提升quality的数值。那么其实上述的问题变成了一个maximize的问题, 利用拉格朗日数乘法构造下面一个式子

进一步计算能得到

那么可以发现这个优化问题也就是求取协方差矩阵特征向量的问题。那么这么多特征值结果和对应的特征向量都能让求导结果为0,从这么多极值中怎么找最大值,为什么认定最大的特征值就对应这个优化问题的最大值呢?

更一步的$A\overrightarrow{w} = \lambda \overrightarrow{w}$,$w^{T}w = 1$ 代入quality公式

所以我们选用的特征值越大越好,在例子中:$\frac{1}{4}(8+0+0+8) = 4$,正好就是我们刚刚求得的$\lambda_1 $的数值。

那么上述我们证明了一个定理:

定理一:PCA 算法输出的第一个特征向量具有最好的质量

那么怎么确定第二个构建坐标的单位向量是什么呢,与第一个坐标向量形成正交的向量那么多,为什么PCA选用的是第二个特征向量

这里还有一个定理,下面进行进一步证明:

定理二:在所有和第一个特征向量$v_1$正交的向量中,PCA 算法输出的第二个特征向量具有最好的质量(以此类推)

这里,pca要构建的坐标系是个正交系,同时协方差矩阵是个实对称矩阵,实对称矩阵的特性就是特征向量互相正交(证明下方图片)

这时候上面的证明变成了,maximize $quality(\overrightarrow{w}) = \overrightarrow{w^T} A \overrightarrow{w}$ 但是constraint变成了两个$\overrightarrow{w^{T}}\overrightarrow{w} = 1$和$\overrightarrow{w^{T}}\overrightarrow{v1} = 0$

同理使用拉格朗日定理引入另一个变量$\phi$构造

求导为0,计算极值情况:

两边同时乘以$\overrightarrow{v_1^T}$

我们知道$\overrightarrow{v_1^T} \overrightarrow{w} = 0$ (在和$v_1$正交的向量中选)。$\overrightarrow{v_1^T} \overrightarrow{v_1} = 1$($v_1$本身也是单位向量),同时:

所以上面的式子里面 我们可以证明 $ \phi = 0$,这个优化问题又完全变成了我们证明第一个定理的形式,同时$\lambda_1$已经被使用过去掉,所以我们接着选取第二大的特征值。以此类推就可以知道PCA为什么选择从大到小排序后的协方差矩阵特征值对应的特征向量构建正交系。

所以在实际情况中,一般我们要把d-dimension的数据压缩到什么程度,也就是k选取多少。譬如想保留至少百分之70的信息。计算出协方差矩阵之后对求解出的所有特征值从大到小进行排序。当选取的前k1个特征值的数值达到或者超过所有特征值总和的百分之70,那么我们就选定压缩为k1个。

FastMap

当维度d实在是很大的时候,构造协方差矩阵和求解特征值的过程计算量很大,所以有一些FastMap的方法,相当于是heuristic version of PCA, PCA算法的贪心算法版。主要由两个部分构成:

Heuristic 1 of FastMap

Assume the vector between the farthest pair of points in P captures a large amount of variance of P.

Heuristic 2 of FastMap

Use the following algorithm to find the farthest pair of points in P

  • $p_1 \leftarrow$ a random point in P
  • $p_2 \leftarrow$ farthest point from $p_1$
  • $p_1 \leftarrow$ farthest point from $p_2$

概率学相关

置信度与置信区间

https://www.zhihu.com/question/26419030/answer/274472266

大数定律与中心极限定律

(1)大数定律是说,n只要越来越大,把这n个独立同分布的数加起来去除以n得到的这个样本均值(也是一个随机变量)会依概率收敛到真值u,但是样本均值的分布是怎样的我们不知道。

(2)中心极限定理是说,n只要越来越大,这n个数的样本均值会趋近于正态分布,并且这个正态分布以u为均值,sigma^2/n为方差。

(3)综上所述,这两个定律都是在说样本均值性质。随着n增大,大数定律说样本均值几乎必然等于均值。中心极限定律说,它越来越趋近于正态分布,并且这个正态分布的方差越来越小。