套磁过程中学的一些知识

7.30

样本方差

在统计学中无法直接计算所有个体的方差，只能用样本方差来代替考虑全部的个体。

示性函数

IA表示A事件发生的时候为1，不发生的时候为0。

马尔可夫不等式

很简单可以发现，X>a 的示性函数 <= x/a恒成立。取数学期望得P(X>=a) <= EX/a。

此即Markov 不等式（inequality）

从理解上来说，如果非负随机变量X的期望存在，则X超过某个定值a的概率不超过 EX/a . 举个简单的例子：如果我们知道所有人收入的平均数a，那么随机抽一个人收入超过10a的概率不超过10

切比雪夫不等式

函数变为 (x-u)^2 / a^2

P(|X-u|>=a) <= E((x-u)^2 / a^2) = DX/a^2 (分子可以视为方差)

从理解上来说，如果随机变量X的期望和方差存在，则X和期望值的距离大于a的概率不超过 DX/a^2. 给定的范围越大（a越大），或X的方差越小，则偏离的概率越小，这和直觉是相符的。

（它的数学证明用到了放缩，也很有意思）

大数定律

Xn的均值无限趋近于EX

马尔可夫大数定律

由切比雪夫，epsilon > 0 时，P(|Xn均 - EXn均| < ε) >= 1 - D(Xn均)/ε^2. (就是切比雪夫反号)

切比雪夫大数定律

独立同分布大数定律

伯努利大数定律

辛钦大数定律

中心极限定理

林德贝格-勒维/独立同分布中心极限定理

无偏估计：

可通过证明，S^2 = 1/(n-1) 求和（Xi - X均）^2是准确无偏的估计。

协方差矩阵

多维变量两两之间的协方差作为矩阵元素。

散度矩阵

？

特征值与特征向量

Av = λv

v是特征向量，λ是v对应的特征值。

特征值分解矩阵

对于矩阵A，有一组特征向量v，将这组向量进行正交化单位化，就能得到一组正交单位向量。特征值分解，就是将矩阵A分解为如下式：

其中，Q是矩阵A的特征向量组成的矩阵，Σ则是一个对角阵，对角线上的元素就是特征值。

实对称矩阵

1. 实对称矩阵A的不同特征值对应的特征向量是正交的；
2. n阶实对称矩阵A必可相似对角化，且对角阵上的元素即为特征值；
3. 若A有k重特征值λ则必有k个线性无关特征向量或者说r(λE-A)=n-k；
4. A的秩等于非零特征值的个数；
5. n阶实对称矩阵A有n个特征值的话（含重根），若r(A)<n，则有n-r(A)个零特征值；
6. A的特征值均为实数，特征向量均为实向量。

PCA算法两种实现方法

(1) 基于特征值分解协方差矩阵实现PCA算法

输入：数据集 ，需要降到k维。

1. 去平均值(即去中心化)，即每一位特征减去各自的平均值。

2. 计算协方差矩阵 ,注：这里除或不除样本数量n或n-1,其实对求出的特征向量没有影响。

3. 用特征值分解方法求协方差矩阵 的特征值与特征向量。

4. 对特征值从大到小排序，选择其中最大的k个。然后将其对应的k个特征向量分别作为行向量组成特征向量矩阵P。

5. 将数据转换到k个特征向量构建的新空间中，即Y=PX