Fit

简单拟合

最小二乘法: Least Square

计算

• Input: $X^T=(X_1,X_2,\cdots ,X_p)$,

• predict output via the model: $\hat{Y}=\widehat{{\beta }_0}+{\sum }_{j=1}^p{X}_j{\hat{\beta }}_j$

  ${\hat{\beta }}_j$: bias or intercept, 偏差

  而$\widehat{{\beta }_j}$和$\widehat{{\beta }_0}$都是需要求解的参数,

• Include the constant variable 1 in X: 在向量X中包含常数1: $\hat{Y}=X^T\hat{\beta }$

  可令$X_0=[1]$, 则$X^T=(X_0,X_1,\cdots ,X_p)$, 那么$\hat{\beta }=\left[\begin{array}{c}{\hat{\beta }}_0\\ {\hat{\beta }}_1\\ ⋮\\ {\hat{\beta }}_p\end{array}\right]$. 相当于是把最开头的那个${\hat{\beta }}_0$收到了参数向量$\hat{\beta }$里面

• 这里的$\hat{Y}$可以是标量, 可以是向量. 如果$\hat{Y}$是k维向量, 那么就有$\hat{\beta }$是一个$p\times K$的参数矩阵(多元回归)

• 在(p+1)维的输入输出空间中, $(X,\hat{Y})$代表一个超空间. 如果${\hat{\beta }}_o$在$\hat{\beta }$中, 那么这个超空间就经过原点.

  ground-truth: $f(X)=X^T\beta$, it’s gradient(梯度): $f^{\prime }(X)=\beta$ 是一个指向最陡的上升方向的向量.

Tip

补充: 矩阵导数:

$$\frac{\partial f_{\theta }(X)}{\partial \beta }=\left[\begin{array}{c}{X}_1\\ X_2\\ ⋮\\ X_p\end{array}\right]=X$$ $$\frac{\partial {\beta }^{T}A\beta }{\partial \beta }=(A+A^T)\beta$$ $$\frac{\partial {\beta }^T{X}^{T}X\beta }{\partial \beta }=(X^{T}X+X{X}^T)\beta$$

其中, $X$是一个向量, $A$是一个二次型系数矩阵.

残差

• N: # observations 观测量(样本空间)
• minimize the residual sum of squares: $$RSS(\beta )=\sum _{i=1}^N(y_i-x_i^T{)}^2$$ 向量(矩阵): $$RSS(\beta )=(\vec{y}-\mathbf{X}\vec{\beta }{)}^T(\vec{y}-\mathbf{X}\vec{\beta })=||\vec{y}-\mathbf{X}\vec{\beta }|{|}_2^2$$ $||\vec{y}-\mathbf{B}\vec{\beta }||$是范数, 关于$\beta$的函数, 是一个抛物面.

  $||a|{|}_2=\sqrt{a^{T}a},\forall a\in {\mathbb{R}}^{p\times 1}$$

  范数: $

要找到最小值点, 需要求导数:

$$RSS(\beta )=(y-X\beta {)}^T(y-X\beta )=y^{T}y-X^T{\beta }^{T}y-y^{T}X\beta +{\beta }^T{X}^{T}X\beta$$ $$RS{S}^{\prime }(\beta )=X^T(y-X\beta )$$

如果$X$不是奇异矩阵, 那么$\hat{\beta }=(X^{T}X{)}^{-1}{X}^{T}y$

最近邻项: Nearest Neighbor

分类.

• model: $\hat{Y}(x)=\frac{1}{k}{\sum }_{x_o\in N_k(x)}{y}_i$

• $N_k(x)$: 最近的$k$个元素的集合.

• $y$: 类别.

• 分类依据: 计算$\hat{Y}(x)$, 与0.5(二元)去对比

回归方程：$\hat{f}(x)=\mathbf{Ave}(y_i|x_i\in N_k(x))$

$N_k$表示前k个最近的元素。

需要极大样本量，才能够保证有均值与期望相接近。当$k\to \infty$的时候，才会有$\frac{k}{N}\to 0\Rightarrow \hat{f}(x)=E(Y|X=x)$

如果当每一个样本点的维数增多的时候(即特征维度增多)，所需要的N的数量会急速增加。

条件概率公式展开

期望: $E[x]={\sum }_{x}xP(X=x)\text{， 当x是非连续变量；}E(x)=\int xP(X=x)\mathbf{d}x\text{ ，当x是连续变量}$

损失函数：$L(X,f(X))=(Y-f(X){)}^2$，也写作$L_2$。还有一个$L_1=|Y-f(X)|$也是损失函数。第一类损失函数比第二类的优点：第一类鲁棒性更好，面对误差或者错误标注的数据能更好的抵抗

EPE, Excepted prediction error, 描述$y$与$\hat{y}$之间的差异:

$$EPE(f)=E(Y-F(X){)}^2=\int (y-f(x){)}^{2}Pr(dx,dy)$$ $$\text{Since }Pr(X,Y)=Pr(Y|X)Pr(X),\text{EPE can also be written as}$$ $$EPE(f)=E_X{E}_{Y|X}([Y-f(X){]}^2|X)$$

所以说，可以通过找EPE的最小值来进行寻找合适的参数，如：

$$f(x)=\text{arg}\underset{c}{\min }{E}_{Y|X}([Y-c{]}^2|X=x)$$

回归方程: $f(x)=E(Y|X=x)$

Linear Regression

$f(x)\approx x^T\beta$，是一个有模型预测的回归模型。这里我们假设了线性模型。

由于有了对回归模型的假设，我们对样本量的需求比kNN算法小了很多。这里的EPE为：

$$EPE(f)=E(Y-f(X){)}^2=E((Y-X^T\beta {)}^T(Y-X^T\beta ))=E(||Y-X^T\beta |{|}_2^2)$$ $$\frac{\partial ((Y-X^T\beta {)}^T(Y-X^T\beta ){)}^{\prime }}{\partial \beta }=\frac{\partial (Y^{T}Y-{\beta }^{T}XY-Y^T{X}^T\beta +{\beta }^{T}X{X}^T\beta {)}^{\prime }}{\partial \beta }$$ $$=0-XY-Y^T{X}^T+(X{X}^T+X^{T}X)\beta =0$$ $$\therefore \beta =[E(X{X}^T){]}^{-1}E(XY)$$

而根据残差平方和，

$$\mathbf{RSS}(\beta )=\sum _{i=1}^N(y_i-x_i^T\beta {)}^2$$

当残差平方和最小的时候，有$\beta =(X^{T}X{)}^{-}1X^{T}y$

协方差

Covariance，$\mathbf{Cov}(X,Y)=E[(X-E[X]{)}^{T}T(Y-E[Y])]=Var+Bia{s}^2$，是方差加上偏差的平方。

方差$\mathbf{Var}(X)=\mathbf{Cov}(X,X)$

kNN

分类输出变量$G$ 的程序，其值来自$g$。损失函数是一个$K\times K$的矩阵$L$，而$K=card(g)$

• $L(k,l)$是错误把$g_k$里的内容估计成$g_l$中内容所付出的代价。

所以，我们有了一个0-1损失方程：$L(k,l)=1-{\delta }_{kl},{\delta }_{kl}=1\text{ if and only if k == l}$

$$EPE=E_X\sum _{k=1}^{K}L[g_k,\hat{G}(X)]Pr(g_k|X)$$ $$\hat{G}(X)=argmi{n}_{g\in G}\sum _{k=1}^{K}L(g_k,g)Pr(g_k|X=x)$$ $$\text{Or simply, }\hat{G}(x)=argma{x}_{g\in G}Pr(g|X=x)$$

Cross Validation

交叉验证

把一个数据集分成$n$份，验证$m$个$k$的取值，那么对于每一次循环，把$n$份中的一份座位测试集，循环$m$次，计算$k$

循环$n$次之后去计算每一个$k$的取值的平均准确度，找到准确度最大的一个

高维中的本地模型（local model）

• 随着维度的上升，本地模型逐渐演化成广域模型（global model）
  • 如：在一个边长为1的p维的立方体中，取一个覆盖了$r\%$的数据（体积），那么设小立方体的边长为$e_p(r)=r^{\frac{1}{p}}$.
  • 那么有：$e_{10}(0.01)=0.63,e_{10}(0.1)=0.80,e_1(0,01)=0.01,e_2(0.01)=0.1$
• 高维空间中，数据去向样本空间的边缘。
  • 假设有N个数据点，p维的空间，假设数据空间是一个单位球体（$r=1$）。那么中位距离（所有数据到样本空间中心点的距离的中位数）是$d(p,N)={\left(1-{\frac{1}{2}}^{\frac{1}{N}}\right)}^{\frac{1}{p}}$。那么就有$d(10,500)\approx 0.52$

Tip

对于一个p维的球体样本空间，有以下推论：

$$\prod _{i=1}^{n}Pr(||x_i||>r)=\frac{1}{2}$$ $$Pr(||x_i||>r)=1-Pr(||x_i||\le 2)=1-V_p(r)=1-\frac{{\pi }^{\frac{p}{2}}}{\Gamma (\frac{p}{2}+1)}{r}^p\approx 1-r^p\text{(当p极大时)}$$ $$(1-r^p{)}^N=\frac{1}{2}$$

可以得出中位距离的公式

函数拟合

1. 数据集：$(x_i,y_i)$的数值对，在$(p+1)$维中。有以下函数(ground-truth): $y_i=f(x_i)+{\epsilon }_i,f:{\mathbb{R}}^p\to \mathbb{R}$
2. 目标：找到一个对于$f(x)$的好的逼近。给定训练样本集$\tau$

text{给定参数集合$\theta$，那么对于线性模型，有}f(x)=x^T\beta$$

$$\text{而θ=β，其中这两个可以是scalar，也可以是vector或matrix}$$ $$f_{\theta }(x)=\sum _{k=1}^K{h}_k(x){\theta }_k$$ $$h_k\text{：一个函数，可以将非线性的输入转换成线性的输入}$$

如：有$x_1,x_2$两个轴，组成的样本集的分界线是一个圆。那么可以令

$$h_k(x_1,x_2)=\sqrt{x_1^2+x_2^2}\text{转换成一个线性的问题}$$

$h_k$的例子:

$$h_k(x)=x_1{x}_2^2\text{(Polynomial expansion)},h_k(x)=\cos (x_1)\text{(Trigonometric expansion)}$$ $$h_k(x)=\frac{1}{1+\exp (-x^T{\beta }_k)}\text{(Sigmoid expansion)}$$

然后利用$RSS$进行拟合$\theta$：

$$RSS(\theta )=\sum _{i=1}^N(y_i-f_{\theta }(x_i){)}^2$$

最大似然估计 MLE

使用$P{r}_{\theta }(y)$（预测值）去估计$Pr(y)$（真实值） Lamma：KL散度：

$$KL(p||q)=\int p(x)\log \frac{p(x)}{q(x)}dx=\int p(x)\log p(x)dx-\int p(x)\log q(x)dx=-H[x]-E[\log q(x)]$$

推导MLE：

$$\underset{\theta }{\min }KL(p(y)||p_{\theta }(y))=\int p(y)\log p(y)dy-\int p(y)\log p_{\theta }(y)dy=C-\int p(y)\log p_{\theta }(y)dy$$

由于$\int p(y)\log p(y)dy$是对$y$的焓，所以是一个常数。考虑Monte Carlo方法抽样：

$$E[x]=\int xp(x)dx=\frac{1}{K}\sum _{k=1}^K{x}_k,x_k\sim p(x)$$

即在$p(x)$中抽样。当$K$足够大，可以认为与期望是相等的。那么有：

$$\underset{\theta }{\min }KL(p(y)||p_{\theta }(y))=C-\frac{1}{N}\sum _{i=1}^N\log p_{\theta }(y_i)$$

去掉常数（因为是对$\theta$求最小），有：

$$\underset{\theta }{\max }l(\theta )=\sum _{i=1}^N\log P{r}_{\theta }(y_i)$$

注意求最小，但是有个负号，所以是对这个求最大。

对于高斯分布的概率密度函数求MLE:

$$l(\theta )=\sum _{i=1}^N\log P{r}_{\theta }(X)=-\frac{N}{2}\log (2\pi )-N\log \sigma -\frac{1}{2{\sigma }^2}\sum _{i=1}^N(y_i-f_{\theta }(x_i){)}^2$$

求最大值那么对$l$求偏导，因为$\theta$包含了两个参数，$\mu ,\sigma$

对训练数据集$\tau$，那么

$$l(\theta |\tau )=\sum _{i=1}^N\log P{r}_{\theta }(x_i,y_i)=\sum _{i=1}^N\log P{r}_{\theta }(y_i|x_i)P{r}_{\theta }(x_i)=\sum _{i=1}^N\log P{r}_{\theta }(y_i|x_i)$$

注意这里省去了$P{r}_{\theta }(x_i)$是因为这个不是我们需要估计的，是给定的随机变量$x$

简单线性估计

最小二乘法

单变量的求解：

$${\hat{\beta }}_0,\hat{\beta }={\text{argmin}}_{{\beta }_0,\beta }\sum _{i=1}^N(y_i-{\beta }_0-\beta x_i{)}^2$$ $$\hat{\beta }=\frac{{\sum }_{i=1}^N(x_i-\bar{x})(y_i-\bar{y})}{{\sum }_{i=1}^N(x_i-\bar{x}{)}^2}$$ $${\hat{\beta }}_0=\bar{y}-\hat{\beta }\bar{x}$$

但是求解单变量的时候，尽量是从${\beta }_0$入手，为了以后求解正则化项作保障。正则化项不能包含${\beta }_0$，因为${\beta }_0$只是斜率，与自变量没有任何关系，惩罚这个项没有任何意义。

对于多变量，$X=(X_1,X_2,\cdots ,X_p{)}^T$

$$f(X)={\beta }_0+\sum _{j=1}^p{X}_j{\beta }_j$$ $$RSS(\beta )=\sum _{i=1}^N(y_i-f(x_i){)}^2=\sum _{i=1}^N(y_i-{\beta }_0-\sum _{j=1}^p{x}_{ij}{\beta }_j)=(\vec{y}-X\vec{\beta }{)}^T(\vec{y}-X\vec{\beta })$$ $$\frac{\partial RSS(\beta )}{\partial \beta }=-2X^T(\vec{y}-X\vec{\beta })=0$$ $$\Rightarrow \hat{\beta }=(X^{T}X{)}^{-1}{X}^T\vec{y}$$

需要满足：$X^{T}X$是可逆的。

$$\hat{y}=X\hat{\beta }=X(X^{T}X{)}^{-1}{X}^{T}y=Hy$$

其中，$H$是一个投影矩阵。相当于是从$x$空间向$y$空间的投影

对于多输出：

$$Y_k={\beta }_{ok}+\sum _{j=1}^p{X}_j{\beta }_{jk}+{\epsilon }_k=f_k(X)+{\epsilon }_k$$ $$Y=XB+E$$ $$RSS(B)=\sum _{k=1}K\sum _{i=1}^N(y_{ik}-f_k(x_i){)}^2=||Y-XB|{|}_F^2$$ $$||A|{|}_F^2=tr(A^{T}A)=\sum _{ij}{a}_{ij}^2$$ $$RSS(B)=tr((Y-XB{)}^T(Y-XB))=tr(Y^{T}Y)-2tr(B^T{X}^{T}Y)+tr(B^T{X}^{T}XB)$$ $$\frac{\partial RSS(B)}{\partial B}=-2X^{T}Y+2X^{T}XB=0\Rightarrow \hat{B}=(X^{T}X{)}^{-1}{X}^{T}Y$$

$tr(A)$是迹，是对角线上的元素相加

关于奇异性

假设有一个矩阵，$p$维，训练样本集有$N$个数据$\Rightarrow$输入样本集$X$是一个$N\times p$的矩阵

要想$X^{T}X$是一个非奇异的矩阵，需要满足$rank(X)=p$，即满秩的矩阵

矩阵的描述	秩	奇异性
胖	$rank(X)\le N<p$	一定是奇异矩阵
方阵	$rank(X)\le N,p$，$N=p$	需要有$rank(X)=p=N$
瘦	$rank(X)\le p<N$	需要有$rank(X)=p$

非满秩：有多余信息，维度高，样本少$\Rightarrow$解决方案：1. 特征选择（降维，去掉某些不必要的特征）2. 正则化（添加一个正则化项使$\hat{\beta }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$）

$X^{T}X+\lambda I$一定是满秩的：$X^{T}X+\lambda I=(UV{U}^T{)}^T(UV{U}^T)+\lambda I=U{V}^2{U}^T+\lambda U{U}^T=U(V^2+\lambda I)U^T$，因为$V^2$是一个每个项都是大于等于0的对角矩阵，那么加上一个大于0的单位矩阵一定是一个满秩的对角矩阵

岭回归 Ridge Regression

$${\hat{\beta }}^{\text{ridge}}=\arg \underset{\beta }{\min }\left\{\sum _{i=1}^N(y_i-{\beta }_0-\sum _{j=1}^p{x}_{ij}{\beta }_j{)}^2+\lambda \sum _{j=1}^p{\beta }_j^2\right\}$$

注意正则化不包含${\beta }_0$截距

另一种表示方式：

$${\hat{\beta }}^{\text{ridge}}=\arg \underset{\beta }{\min }||Y-{\beta }_0-X\beta |{|}_2^2\text{，subject to }||\beta |{|}_2^2\le t$$ $$PRSS(\lambda ,\beta )=(y-X\beta {)}^T(y-X\beta )+\lambda {\beta }^T\beta$$ $$\frac{\partial PRSS(\lambda ,\beta )}{\partial \beta }=-2X^{T}y+2(X^{T}X+\lambda I)\beta =0\Rightarrow {\hat{\beta }}^{\text{ridge}}=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$$

与最小二乘法对比：

$$X{\beta }^{\text{ls}}=(X^{T}X{)}^{-1}{X}^{T}y=\sum _{j=1}^p{u}_j{u}_j^{T}y$$ $$X{\beta }^{\text{ridge}}=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y=\sum _{j=1}^p\frac{d_j^2}{d_j^2+\lambda }{u}_j^{T}y$$

其中，$X^{T}X$进行SVD分解之后的结果是$UD{U}^T$，$u$属于$U$，$d$属于$D$

有效自由度（表示复杂度的一种方法）：

$$df(\lambda )=\sum _{j=1}^p\frac{d_j^2}{d_j^2+\lambda }{u}_j^{T}y$$

假设训练样本集的输入是一个$p$维的：

$$\lambda \to 0\Rightarrow df(\lambda )\to p\text{，相当于没有正则化}$$ $$\lambda \to \infty \Rightarrow df(\lambda )\to 0\text{，正则化惩罚过强，不在关心Loss函数，导致原来的模型极端简单}$$

Lasso回归

是一种稀疏的回归方式

我们希望对${\beta }_i$不为零的项进行惩罚，因为只有${\beta }_i\ne 0$才会导致模型变得复杂。所以需要使用“零范数”用作惩罚项。（岭回归用的是二范数座位惩罚项）

使用零范数的时候称为“最佳子集回归”，best subset regression。

但是零范数是一个非凸曲线，无法使用求导来进行分析最小值。包括所有$p$范数($0<p<1$)都是非凸的。那么距离零范数最近的一个最小的凸曲线的范数是一范数。（注意，在一范数的顶点位置还是不能求导，因为不连续）。所以Lasso回归使用了一范数

$${\hat{\beta }}^{\text{lasso}}=\arg \underset{\beta }{\min }\left\{\frac{1}{2}\sum _{i=1}^N(y_i-{\beta }_0-\sum _{j=1}^p{x}_{ij}\beta |j{)}^2+\lambda |{\beta }_j|\right\}$$ $$=\arg \underset{\beta }{\min }\left\{\frac{1}{2}||Y-\beta -X\beta |{|}_2^2+\lambda ||\beta |{|}_1\right\}$$

与最小二乘法对比

$${\hat{\beta }}^{\text{ridge}}=\frac{1}{1+\lambda }{\hat{\beta }}^{\text{ls}}$$ $${\hat{\beta }}_j^{\text{lasso}}=sign({\hat{\beta }}_j^{\text{ls}})(|{\hat{\beta }}_j^{\text{ls}}|-\lambda {)}_{+}$$

MAP

$${\hat{\beta }}^{MAP}=\arg \underset{\beta }{\max }Pr(y|X,\beta )Pr(\beta )$$ $$Pr(\beta )\text{是由岭回归或者Lasso回归计算的，}Pr(y|X,\beta )\text{是最小二乘法计算的}$$ $$ridge:Pr(\beta )=N(\beta |0,\frac{1}{\lambda }{I}_p)\text{，高斯分布}$$ $$lasso:Pr(\beta )=\frac{\lambda }{2}{e}^{-\lambda ||\beta |{|}_1}$$

简单分类器

线性分类器

利用不同类别赋值不同，把每个类别赋值作为输出($y_i$)，进行线性回归，找到$y_i=x^T\hat{\beta }=0.5$的那条线

拟合函数需要满足

$$\hat{f}(x)={\hat{B}}^T\left(\begin{array}{c}1\\ x\end{array}\right)=\left(\begin{array}{c}{\hat{f}}_1(x)\\ {\hat{f}}_2(x)\\ ⋮\\ {\hat{f}}_K(x)\end{array}\right)\in {\mathbb{R}}^K$$

对x的分类：$\hat{G}(X)=\arg {\max }_{k\in g}{\hat{f}}_k(x)$，相当于是寻找可能性最大的那个类别$k$，或者等效写作：

$$\hat{G}(x)=\arg \underset{k\in g}{\min }||\hat{f}(x)-t_k|{|}_2^2\text{，tk是类别标号，即寻找相关性最强，类别最近的一个}$$ $$\hat{G}(x)=\arg \underset{k\in g}{\max }Pr(G=k|X=x)\text{，后验概率}$$

如果是简单的线性回归去拟合，可能会导致掩盖掉某些类。具体情况查看L5-p14

所以需要把线性回归拓展到非线性空间：加上一些二次项或者更高次的项然后再进行回归，最后把回归的结果映射回线性空间，得到一个非线性的分界线

LDA

使用基于贝叶斯的后验概率

$$Pr(G=k|X=x)=\frac{Pr(X=x|G=k)Pr(G=k)}{Pr(X=x)}=\frac{Pr(X=x|G=k)Pr(G=k)}{{\sum }_{l=1}^{K}Pr(X=x|G=l)Pr(G=l)}$$ $$f_k(x)=Pr(X=x|G=k)$$ $${\pi }_k=Pr(G=k)$$ $$\text{类别分布}={\Pi }_{k=1}^K{\pi }_k^{1_{x=k}}$$ $$1_{x=k}=\{\begin{array}{cc}1& x=k\\ 0& x\ne k\end{array}$$

边界（概率相等的地方）：

$$\{x|Pr(G=k|X=x)=Pr(G=l|X=x)\}$$ $$\Rightarrow \frac{\mathrm{Pr}(G=k|X=x)}{Pr(G=l|X=x)}=1\Rightarrow \ln \frac{Pr(X=x|G=k)Pr(G=k)}{Pr(X=x|G=l)Pr(G=l)}=0$$ $$\Rightarrow \text{LDA：}{\beta }^{T}X+{\beta }_0=0$$ $$Pr(G=k|X=x)=\frac{f_k(x){\pi }_k}{{\sum }_{l=1}^K{f}_l(x){\pi }_l}$$

对于高维高斯分布的LDA:

$$f_k(x)=\frac{1}{(2\pi {)}^{\frac{p}{2}}|{\Sigma }_k{|}^{\frac{1}{2}}}\exp (-\frac{1}{2}(x-{\mu }_k{)}^T{\Sigma }_k^{-1}(x-{\mu }_k))$$

我们做一个假设：对于所有的${\Sigma }_k=\Sigma$，即任意的${\Sigma }_k$都相等。这里的${\Sigma }_k$是$k$分类的方差（${\sigma }_k^2$）

$$\text{Logit：}\ln \frac{Pr(G=k|X=x)}{Pr(G=l|X=x)}=\ln \frac{f_k(x)}{f_l(x)}+\ln \frac{{\pi }_k}{{\pi }_l}$$ $$=\ln \frac{{\pi }_k}{{\pi }_l}-\frac{1}{2}({\mu }_k+{\mu }_l{)}^T{\Sigma }^{-1}({\mu }_k-{\mu }_l)+x^T{\Sigma }^{-1}({\mu }_k-{\mu }_l)$$ $$\Rightarrow {\hat{\pi }}_k=\frac{N_k}{N},{\hat{\mu }}_k=\sum _{g_i=k}\frac{x_i}{N_k},\hat{\Sigma }=\sum _{k=1}^K\sum _{g_i=k}\frac{(x_i-{\hat{\mu }}_k)(x_i-{\hat{\mu }}_k{)}^T}{N-K}$$

	$X_1$	$X_2$	G
$x_1^T$	0.2	0.3	1
$x_2^T$	0.8	0.7	3
$x_3^T$	0.4	0.6	2
$x_4^T$	0.6	0.4	2
$x_5^T$	0.3	0.2	1
$x_6^T$	0.7	0.8	3

$${\hat{\pi }}_1={\hat{\pi }}_2={\hat{\pi }}_3=\frac{1}{3}$$ $${\hat{\mu }}_1=\frac{1}{2}(x_1+x_5)=\frac{1}{2}\left(\begin{array}{c}0.2\\ 0.3\end{array}\right)+\frac{1}{2}\left(\begin{array}{c}0.3\\ 0.2\end{array}\right)=\left(\begin{array}{c}0.25\\ 0.25\end{array}\right)$$ $${\hat{\mu }}_2=\frac{1}{2}(x_3+x_4)=\left(\begin{array}{c}0.5\\ 0.5\end{array}\right)$$ $${\hat{\mu }}_3=\frac{1}{2}(x_2+x_6)=\left(\begin{array}{c}0.75\\ 0.75\end{array}\right)$$ $$\hat{\Sigma }=\frac{\left(\begin{array}{cc}0.005& -0.005\\ -0.005& 0.005\end{array}\right)+\left(\begin{array}{cc}0.02& -0.02\\ -0.02& 0.02\end{array}\right)+\left(\begin{array}{cc}0.005& -0.005\\ -0.005& 0.005\end{array}\right)}{6-3}=\left(\begin{array}{cc}0.01& -0.01\\ -0.01& 0.01\end{array}\right)$$ $$\ln \frac{Pr(G=1|X=x)}{Pr(G=2|X=x)}=\ln \frac{{\hat{\pi }}_1}{{\hat{\pi }}_2}-\frac{1}{2}({\hat{\mu }}_1+{\hat{\mu }}_2{)}^T{\hat{\Sigma }}_{\lambda }^{-1}({\mu }_1-{\mu }_2)+x^T{\hat{\Sigma }}_{\lambda }^{-1}({\hat{\mu }}_1-{\hat{\mu }}_2)$$ $$=0.1875-(x_1,x_2)\left(\begin{array}{c}0.25\\ 0.25\end{array}\right)=0$$ $$\Rightarrow \text{边界为}\{(x_1,x_2)|x_1+x_2=0.75\}\text{，其中}{\hat{\Sigma }}_{\lambda }=\hat{\Sigma }+\lambda I,\lambda =1$$

定义线性判别函数为${\delta }_k(x)=x^T{\Sigma }^{-1}{\mu }_k-\frac{1}{2}{\mu }_k^T{\Sigma }^{-1}{\mu }_k+\ln {\pi }_k$

在$x$点，哪一个类的${\delta }_k(x)$大，这个点就是哪一类的。当${\delta }_k(x)={\delta }_l(x)$的时候，说明这个点事$l$类和$k$类的边界线上

QDA

相对LDA，少了一个假设：${\Sigma }_k=\Sigma ,\forall k\in G$

所以特征表达更好，但是计算的特别多。

LDA计算$K\times p+p\times p$个参数，只需要估计$\pi ,\mu ,\Sigma$

QDA计算$K\times p+K\times p\times p$个参数，需要估计$\pi ,\mu ,{\Sigma }_k\forall k\in G$

判别式：${\delta }_k(x)=-\frac{1}{2}\ln |{\Sigma }_k|-\frac{1}{2}(x-{\mu }_k{)}^T{\Sigma }_K^{-1}(x-{\mu }_k)+\ln {\pi }_k$

LDA 正则化与降维

RLDA 正则化LDA

$$\hat{\Sigma }(\gamma )=\gamma \hat{\Sigma }+(1-\gamma )\mathbf{diag}(\hat{\Sigma }),\gamma \in [0,1]$$

Diagonal LDA 对角LDA

$$\hat{\Sigma }=diag(\hat{\Sigma })$$

低方差（高复杂度），高偏差				高方差，低偏差（高准确度）
Diag LDA	RLDA	LDA	RQDA	QDA
$diag(\hat{\Sigma })$	$\hat{\Sigma }(\gamma )$	$\hat{\Sigma }$	${\hat{\Sigma }}_k(\alpha )$	${\hat{\Sigma }}_k$

Fisher Formulation of Discriminant Analysis

$$\log \frac{Pr(G=k|X=x)}{Pr(G=l|X=x)}={\delta }_k(x)-{\delta }_l(x)$$ $${\delta }_k(x)\propto \log Pr(G=k|X=x)$$ $$\log Pr(G=k|X=x)=-\frac{1}{2}(x-{\hat{\mu }}_k{)}^T{\hat{\Sigma }}^{-1}(x-{\hat{\mu }}_k)+\ln {\hat{\pi }}_k+C$$ $$=-\frac{1}{2}||x^{\ast }-{\hat{\mu }}_k^{\ast }|{|}^2+\ln {\hat{\pi }}_k+C$$ $$\hat{G}(x)=\arg \underset{k\in g}{\max }{\delta }_k(x)=\arg \underset{k\in g}{\min }\frac{1}{2}||x^{\ast }-{\hat{\mu }}_k^{\ast }|{|}^2-\ln {\hat{\pi }}_k$$

其中，$x^{\ast }={\hat{\Sigma }}^{-\frac{1}{2}}x$，${\hat{\mu }}_k^{\ast }={\hat{\Sigma }}^{-\frac{1}{2}}{\hat{\mu }}_k$

目的：白化（球化），使协方差矩阵变成单位矩阵。目的：降低两个类别之间的重叠区域。

高级分类器

Boosting

通过弱分类器投票决定一个强分类器 Input:

$$S=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_m,y_m)\}$$

$D_t$是$\{x_1,\cdots ,x_m\}$这些点的权重，$\alpha$是每一个分类器在投票里面所占权重 Run $A$ on $D_t$ producing

$$h_t:X\to \{-1,1\}$$ $${ϵ}_t=P_{x_i\sim D_t}(h_t(x_i)\ne y_i)=\frac{1}{M}\sum _{n=1}^{M}1[h_t(x_i)\ne y_i]\text{，即错误分类的概率}$$ $$H_{\text{final}}(x)=\mathbf{sign}(\sum _t{\alpha }_t{h}_t(x))$$

计算流程：

$$\text{初始化：}{D}_1(i)=\frac{1}{m}$$ $${ϵ}_t=\frac{1}{m}\sum _{n=1}^{m}1[h_t(x_i)\ne y_i]$$ $${\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$$ $$Z_t=2\sqrt{{ϵ}_t(1-{ϵ}_t)}$$ $$D_{t+1}(i)=\{\begin{array}{cc}\frac{D_t(i)}{Z_t}{e}^{-{\alpha }_t}& \text{分类正确，减少该点权重，更注意分类错误的点}\\ \frac{D_t(i)}{Z_t}{e}^{{\alpha }_t}& \text{分类错误，提高权重}\end{array}$$

训练次数为$T=O(\frac{1}{{\gamma }^2}\ln \frac{1}{ϵ})$

SVM

间隔$\gamma =\min \frac{y{\omega }^{\ast T}x}{||{\omega }^{\ast }||}$

求解： 应用拉格朗日乘数法：

$$\mathcal{L}(\vec{w},b,\vec{\alpha })=\frac{1}{2}||\vec{w}|{|}^2+\sum {\alpha }_i(1-y_i(\vec{w}\cdot {\vec{x}}_i-b))$$ $$\{\begin{array}{c}\frac{\partial L}{\partial \vec{w}}=0\\ \frac{\partial L}{\partial b}=0\end{array}\Rightarrow \begin{array}{c}\vec{w}=\sum {\alpha }_i{y}_i{\vec{x}}_i\\ 0=\sum {\alpha }_i{y}_i\end{array}\Rightarrow \mathcal{L}(\vec{w},b,\vec{\alpha })=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i^T\cdot {\vec{x}}_j)$$

上面的${\vec{x}}_i^T\cdot {\vec{x}}_j$可以使用核函数进行升维

$$\Rightarrow \{\begin{array}{c}{\alpha }_i\ge 0\\ y_{i}f({\vec{x}}_i)-1\ge 0\\ {\alpha }_i(y_{i}f({\vec{x}}_i)-1)=0\end{array}$$

然后使用SMO (Sequential Minimal Optimization)求解

SMO相关简介

详情参见KKT Condition

半监督SVM

根据有标签的点进行分类，计算得出一个模型，然后根据这个模型对无标签的样本点分类，然后对分好类的样本点再一次计算模型，重复迭代。

聚类

假设$P(X_1,\cdots .X_N)$是多分布的混合模型，处于一个$n$维的变量空间，使用离散的随机变量$Z$指示是哪一个分布正在被使用。所以$P(X_1\cdots X_N)={\sum }_{i}P(Z=i)P(X_1\cdots X_N|Z)$，其中$Z$是一个隐变量，$P(Z=i)$属于某个高斯分布的先验。贝叶斯图像如图：

graph TB
Z-->X1
Z-->X2
Z-->...
Z-->XN

1. 假设每个数据点都是$n$维的数据，即$X=⟨X_1,\cdots ,X_n⟩$，假设$X_i$之间相互独立（高斯分布的朴素贝叶斯假设）

   $$P(X|Z=j)=\prod _{i}N(x_i|{\mu }_{ij},{\sigma }_{ij})$$

2. 根据先验的Gaussian分布$P(Z=i)$进行随机采样$i$（假设只有两个类，并且$\forall i,j,{\sigma }_{ji}=\sigma$，假设认为所有的方差相同）

   $$P(X)=\sum _{j=1}^{2}P(Z=j|\pi )\prod _{i}N(x_i|{\mu }_{ij},\sigma )$$

3. 根据$N({\mu }_i,{\Sigma }_i)$随机生成数据点$⟨x_1,\cdots ,x_n⟩$

   假设已经知道了$\sigma$，还需要知道${\pi }_1,\cdots ,{\pi }_k$和${\mu }_{1i},\cdots ,{\mu }_{Ki}$

   观测值：$X=⟨X_1,\cdots ,X_n⟩$，隐变量：$Z$

使用EM算法进行估计：

Define $Q({\theta }^{\prime }|\theta )={\mathbb{E}}_{Z|X,\theta }[\log P(X,Z|{\theta }^{\prime })],\theta =⟨\pi ,{\mu }_{ji}⟩$

E-step:

$$P(z(n)=k|x(n),\theta )=\frac{{\prod }_{i}N(x_i(n)|z(n)=k,\theta )({\pi }^k(1-\pi {)}^{1-k})}{{\sum }_{j=0}^1[{\prod }_{i}N(x_i(n)|{\mu }_{ji},\sigma )]({\pi }^j(1-\pi {)}^{1-j})}$$

M-step:

$$\pi \leftarrow \frac{1}{N}\sum _{n=1}^N\mathbb{E}[z(n)]$$ $${\mu }_{ji}\leftarrow \frac{{\sum }_{n=1}^{N}P(z(n)=j|x(n),\theta )x_i(n)}{{\sum }_{n=1}^{N}P(z(n)=j|x(n),\theta )}$$

使用贝叶斯网络进行优化

最小化$\mathbf{KL}(P||T)=-{\sum }_{i}I(X_i,Pa(X_i))+{\sum }_{i}H(X_i)-H(X_1\cdots X_n)$

其中，边缘概率密度分布$I(A,B)={\sum }_a{\sum }_{b}P(a,b)\log \frac{P(a,b)}{P(a)P(b)}$，$Pa(X_i)$指的是在图中$X_i$的直接父节点。$H$是焓。

给定$I$，然后根据最大化$I$的思路去建树，根据这个树进行优化

GMM

协同训练

假设有一个样本多个特征，其中一个特征的分类置信度很高，那么认为这个样本其他的特征都是这一个分类的，然后根据这个分类进行再训练迭代

缺点：容易把错误放大

假设只有两个视角（两个类别的特征，训练分别是$h_1$和$h_2$）

$${\mathrm{argmin}}_{h_1,h_2}\sum _{l=1}^2\sum _{i=1}^{m_l}l(h_l(x_i),y_i)+C\sum _{i=1}^{m_u}\mathbf{agreement}(h_1(x_i),h_2(x_i))$$

其中$l(h_l(x_i),y_i)$是损失函数，一般是距离或者0/1损失，$\mathbf{agreement}(h_1(x_i),h_2(x_i))$是$h_1$和$h_2$之间的差距，可以自定义

Similarity Based Regularity

找到距离最近的几个点，然后把自己的类别传递过去

如：根据相似度建图，取相似度小于等于$\epsilon$的之间连一条边，然后根据已经有的样本标签传递

相似度可以使用Gaussian Kernel来计算：$K(x,z)=\exp \left[-\frac{||x_i-x_j|{|}^2}{2{\sigma }^2}\right]$，其中$x_i$和$x_j$是两个样本点的特征向量

可以把相似度组成一个矩阵（对称的）：$w_{ij}=\exp \left[-\frac{||x_i-x_j|{|}^2}{2{\sigma }^2}\right]\Rightarrow W$，然后只需要进行最小化目标函数：

$$\underset{f}{\min }\sum _{e=(i,j)}{w}_e||f_i-f_j|{|}^2=2f^T(D-W)f$$

其中，$f$是标签组成的一个矩阵，D是W的对角矩阵，现在令$L=D-W$有${\min }_f{f}^{T}Lf$。这种方法叫做Spectral Clustering

然后因为有一些标签是已知信息，所以要加上Loss：

$$\underset{f}{\min }\sum _{ij}{w}_{ij}||f_i-f_j|{|}^2-C\sum _{i=1}^{m_e}||y_i-f_i|{|}^2$$

令$f=\beta X$,

$$\Rightarrow f^{T}Lf={\beta }^T{X}^{T}LX\beta \Rightarrow \min {\beta }^T{X}^{T}LX\beta +\lambda ||y-X\beta |{|}_2^2+\alpha ||\beta |{|}^2$$

最终的类似一个岭回归，当时还存在local的信息（${\beta }^T{X}^{T}LX\beta$）

GMM

Generative Model中的高斯混合模型（Gaussian Mixture Model）

变量：$\theta =\{{\pi }_i,{\mu }_i,{\Sigma }_i{\}}_{i=1}^K$，其中${\pi }_i$是分类的先验概率，${\mu }_i$是高斯的均值，${\Sigma }_i$是高斯的协方差矩阵

联合概率密度分布：$p(x,y|\theta )={\sum }_{i=1}^K{\pi }_i\mathcal{N}(x;{\mu }_i,{\Sigma }_i)$

分类：$p(y|x,\theta )=\frac{p(x,y|\theta )}{{\sum }_{i=1}^{K}p(x,y_i|\theta )}$

kernel函数

找到内积$X{X}^T$才能使用（$d\times n$的矩阵，至少结果需要是一个$d\times d$的矩阵）

常用kernel：

$$\text{Linear: }K(x,z)=x\cdot z$$ $$\text{Polynomial: }K(x,z)=(x\cdot z{)}^d\text{ or }K(x,z)=(x\cdot z+1{)}^d$$ $$\text{Gaussian: }K(x,z)=\exp \left[-\frac{||x-z|{|}^2}{2{\sigma }^2}\right]\text{，σ是超参数}$$ $$\text{Laplace: }K(x,z)=\exp \left[-\frac{||x-z||}{2{\sigma }^2}\right]$$

直接对内积使用核函数，可以将原本是时间复杂度极大的矩阵乘法降低为$O(n)$

核函数可以相加可以相乘，所以可以根据这点直接构建一个新的核函数（称为多核学习）