EML

来吧，还是一门有cheat sheet的考试。不过感觉这个EML主要还是概念和相关的简单计算，所以整好cheat-sheet就是拿1.x分数的关键啊（

入门

任务类型分为两种，prediction和classification。然后classification里又特化出一种任务：find groups (e.g. k-means)

Prediction

一般来说关系都要estimate。
然后输入$X$一般知道，然后想要输出$Y$。
于是有:

$$\hat{Y}=\hat{f}(X)$$

我们一般不关心$\hat{f}$的具体形式。

Error类型

然后Error分为Reducible和Irreducible。以$\mathrm{MSE}$为例：

$$E((Y-\hat{Y})^2)=E((f(x)+\epsilon-\hat{f}(x)))=E(f(x)-\hat{f}(x)^2)-Var(\epsilon)$$

柿子最后的$Var(x)$为irreducible。
Prediction的目的就是最小化$E((f(x)-\hat{f}(x))^2)$这个reducible的误差。

How to get $f$

更形式化地说，给定$n$个observation，怎么fit出$Y\approx\hat{f}(X)$.

这里又有两种思路：

• Parametric: 假定$f$的形式，然后再fit。问题是你选的$f$可能并不能很好的描述数据。
• Non-Parametric: 现找$f$形式。问题是你找的形式可能太符合这几个observation了，导致overfitting。

按interpertability从高到低，flexibility从低到高列出一些经典模型：

Subset Selection/Lasso、Least Square、Generalized Additive Model、Trees、Bagging\Boosting、SVM、NN

Acc和可解释性的关系：
ACC⬆️，Para⬆️，所以：

1. Estimating them will be more expensive
2. Complicated model 更难预测，所以 when inference is the goal, 多用简单模型
3. 样本数过少，没有足够信息去准确预测parameter，可能会overfitting。

Supervised vs. Unsupervised

Supervised：形式基本为 $Y=\hat{f}(x)$
Semi-supervised: 一些$x_i$没有对应的$y_i$
Unsupervised: 一般都是在clustering。

Cluster Intro

Error： 错判率。

Bayes Classifier

We can minimize the error using this classifier:

$$arg \max\limits_{j=1,\dots,K}Pr(Y=j|X=x_0)$$

for a classification problem with $K$ classes.

它的问题是只能在真实概率已知的情况下用，没有也得估计一个

k-NN(K Nearest Neighbors)

柿子为

$$arg\max_{j=1,\dots,C}\frac{1}{k}\sum\limits_{i\in\mathcal{N}_0}I(y_i=j)$$

$\mathcal{N}_0$ 为 $x_0$ 点周围 $k$ 个点。
意思就是你的邻居最多是什么颜色，你就是什么颜色。
$k$ 过小overfitting，过大underfitting。
理论上 $k$ 选的好，在测试集的表现是可以和Bayes Classifier相当的。

MSE

定义由名字可得： Mean Square Error。就是

$$E((y_i-\hat{f}(x))^2)=Var(\hat{f}(x_0))+[Bias(\hat{f}(x))]^2+Var(\epsilon)$$

再进一步讨论bias和variance。

$$Bias(\hat{f}(x_0))=E(\hat{f}(x_0))-f(x_0)$$

为系统偏移。

$$Var( \hat{f}(x) )=E[(\hat{f}(x_0)-E(\hat{f}(x_0)))^2]$$

Least Squares Estimation

RSS（残差平方和）：

$$RSS=\sum_{i=1}^n(y_i-\hat{y_i})^2$$

SE

样本均值的标准差 $SE(\hat{y})=\frac{\sigma}{\sqrt{n}}$

回顾系数的标准差 $SE(\hat{\beta_1})^2=\frac{\sigma^2}{\Sigma(x_i-\hat{x})^2}$

最小二乘解

$H=X(X^TX)^{-1}X^T$

T-F test

t-statistic = coefficient / std error
F-statistic: $F = \frac{(TSS-RSS)/p}{RSS/(n-p-1)}$

$TSS=\sum_{i=1}^n(y_i-\bar{y})^2$

$R^2=1-RSS/TSS$

$CI=\bar{y}+t\cdot \sigma$

t的取值如下：

置信水平	$\alpha$	t
90	0.1	1.645
95	0.05	1.96
98	0.02	2.326
99	0.01	2.576

Discussion

1. Correlated errors -> under-estimate the SE
2. Heteroscedasticity -> transform or weight the observation
3. Outliner -> 3-$\sigma$
4. Leverage: $h_i=\frac{1}{n}+\frac{(x_i-\bar{x})^2}{\Sigma_{i'=1}^n(x_{i'}-\bar{x})^2}$
5. Colinearity: 意思就是 feature 之间也有线性关系

Classification

LDA

Discrimination 的一般形式为：

$$\delta_k(x)=\ln(\pi_kf_k(x))$$

然后 LDA 与 QDA 的区别就是每个类的 covariance matrix 一样不一样->每个类的形状一不一样。

一样->LDA, 不一样-> QDA

Logistic Regression 推导

从最大似然开始：

以投硬币为例，4 中 6 不中概率为 $\binom{4}{10}p^4(1-p)^6$.
这里 $p^4(1-p)^6$ 就是 likelihood.

要找到 $p$ maximize

$$\prod_{i=1}^n p^{y_i}(1-p)^{1-y_i}$$

取 log, 乘上常数 $-\frac{1}{n}$, 有

$$\argmin_{p}-\frac{1}{n}\sum_{i=1}^{n}y_i\log(p_i)+(1-y_i)\log(1-p_i)$$

再带入 Logistic Regression 中， $p=\sigma(x^T\theta)$, 有

$$\argmin_{p}-\frac{1}{n}\sum_{i=1}^{n}y_i\log(\sigma(x^T\theta))+(1-y_i)\log(1-\sigma(x^T\theta))$$

这就是 Cross-entropy 的形式。

Generalization

LOOCV

每次只留一个点做测试：

数据集大 -> 低 bias
测试集小 -> 高 variance

k-fold

常用 k=5 or 10

因为测试集更大，所以 variance 相对小。

同时要先 CV 再选特征， 不能先选再做。不然误差会被低估。

One-Standard-Error Rule

选用 “最小CV误差 + 1 标准差范围内最简单的模型”

Train-Validation-Test

50% train， 25% validation，25% 最终性能评估。

Nested CV

外层选模型，内层调参数。

避免使用统一数据调參和评估，更加保守可靠

Bootstrap

• 有放回抽样，每个 Boostrap 样本包含约 $1-e^{-1}=0.632$ 的数据
• 剩下的 $0.368$ 可以做 OOB (Out-Of-the-Bag) 测试集

Dimension Reduction

PCA

保留最多信息->方差最大->SVD分解后挑 $k$ 个 singular value 最高的列。

选择 $k$ 的时候算结果的方差占之前方差的比例。

Limitation

• can lead to local inconsistencies
• far away points become the nearest neighbor
• depending on the application this is a problem

MDS

这个主要保留几何信息。 输入可以为矩阵也可以不是。

Clustering

K-Means

Gini impurity:

$$G=1-\sum_{K}^{k=1}p^2_2$$

where $p_k$ 是 $k$ 类占的比例。

1. 随机选 $k$ ，再随机选 $k$ 个点，然后分别染色
2. 重复，直到 convergent

分类的方法:

a. 按距离最近中心的颜色染色
b. 移动中心到染的这些点的中心

从优化角度来看，我们的目标是这个柿子：

$$\mathop{\min}\limits_{\mu_k,c_k}\Sigma^K_{k=1}W(C_k)=2\Sigma_{i\in C_k}||x_i-\mu_k||^2$$

Limitation

• need a metric space
• sensitive to outliners

一个小优化是 计算 medoids 而不是 cnetroids
指的是选一个在已有的 cluster 中， 离其他点距离最短的点。
这样就可以：

• 在 dissimilarity matrices given 的情况下用
• 复杂度从 $N$ 到 $N^2$

Hierarchical Clustering

三种：

• Single Linkage: 两个 cluster 的距离 = 两个 cluster 里任意两点的最短距离
• Average Linkage: … = 两个 cluster 间所有 pair wise 距离的平均值
• Complete Linkage： … = 两个 cluster 里任意两点的最长距离

一开始所有点都在自己的 cluster 里。
然后再按照上述三种合并策略一个一个合并。

选 $K$

选在 $Elbow$ 上的点。

以及 Cut at large gap

Evaluation

• Inertia: Sum of squared distance from each data point to its center. Lower inertia -> tighter cluster

Trees and Forests

模型基本目标： 把数据分成不同的区域。

How to build

怎么造棵Regression Tree：

1. 把data space 分为 $R_1,R_2,\dots,R_J$ $J$ 块区域
2. 为每个 region 建个 constant 模—— 所有数据点的平均值。

理论上长成啥样都没问题，但我们只取 rectangles (cuboids).

具体实现

Training error: $\Sigma^J_{i=1}\Sigma_{i\in R_j}(y_i-\hat{y}_{R_j})^2$

Recursively 选一个X里的指标 $X_i$ ,然后找到一个 $s$, 分为 $R_1(j,s)，R_2(j,s)$ 分别表示 $<$ 和 $\ge s$. Minimize $$\Sigma_{i:x_i\in R_1(j,s)}(y_i-\hat{y}{R_1}+)+\Sigma{i:x_i\in R_2(j,s)}(y_i-\hat{y}_{R_2})$$

然后在达到某个指标后停止，(i.e.,递归深度， 区域内点数量)。

Prune a tree

基准是 Ch.6 中提到的 lasso procedure

要优化的参数是子树 $T$:

$$\sum_{m=1}^{|T|}\sum_{i:x_i\in R_m}(yi-\hat{y}_{R_m})+\alpha|T|, T\subset T_0, \text{where } T_0 \text{ is the full tree}$$

Building Regression

最后，我们就能用这些得到 Regression Tree 的生成方法了：

1. grow a full tree using recursive binary splitting
2. 用之前的 Prune 方法整一个关于 $\alpha$ 的函数。
3. use K-fold cross validation:
   1. 在现在的 fold 上重复步骤1，2。
   2. 算新树在其他数据上的 MSE
      选出使得 average error 最小的 $\alpha$
4. 按照 3 中的 $\alpha$ 返回 2 中的 subtree。

然后2.中 prune 的方法是找到 $\Delta R=R(pruned)-R(original)$ 最小的节点

Classification Trees

这里我们选择

$$E=1-\mathop{\max}\limits_{k}(\hat{p}_{mk})$$

作为Loss function
然后 $\hat{p}_{mk}$ 的意思是 $R_m$ 中属于 class $k$ 的比例。

Discussion

Pros and Cons

Pros：
1. 易于解释
2. 和人类决策方式很像
3. 有简单 graphical 表示，易于 interpret
4. 不需要转化编码 (e.g. one hot encoder)
5. 可以系统性处理缺失值
Cons:
1. 相对不准确
2. 鲁棒性可能会很差

Ensemble Methods

1. Bagging：用Bootstrapping做多个 Tree， 输出取平均
2. Random Forest：在Bootstrapping时，每次随机取数据点的 $m$ 个feature（如 $m=\sqrt{p}$ ），这样可以 decorrelate 数据之间的关系。
3. Boosting： 算法懒得抄了，意思就是一直在前一棵树的基础上学习。

这个地方考题一般是判断哪个图像对应什么方法。

SVM

朴素的想法是：

1. 找一个超平面
2. 带入点到超平面方程，按结果的符号分类。

Maximal Margin Classifier

一个更进一步的想法是Maximal Margin Classifier

它最大化“distance of the closet point”, 这个距离叫 margin。
这些点叫 support vector（因为每个data point都是一个n维向量）。

这个优化问题的形式化描述是：

$\max\limits_{\beta_0,\beta_1,\dots,M}M$
subject to $\Sigma_{i=1}^p\beta_j^2=1$
$y_i(\beta_0+\beta_1x_{i1}+\beta_2x_{i2}+\dots+\beta_px_{ip})\ge M,i=1,\dots,n$
$y_i\in\{+1,-1\}$

Support vector classifier

研究之前的问题，我们发现随便加一个点就可能让我们classifier找向量更加困难，而且它过于sensitive了。
为了让它更稳定与好找向量，我们可以舍弃一些准确率之类的。
soft-margin support-vector classifier 做的就是这个工作。
它的理念是允许一些点在margin里或者干脆就直接在平面上。

这个优化问题的形式化描述是：

$\max\limits_{\beta_0,\beta_1,\dots,M}M$
subject to $\Sigma_{i=1}^p\beta_j^2=1$
$y_i(\beta_0+\beta_1x_{i1}+\beta_2x_{i2}+\dots+\beta_px_{ip})\ge M(1-\epsilon_i),i=1,\dots,n$
$y_i\in\{+1,-1\},\epsilon_i\ge 0,\Sigma^n_{i=1}\epsilon_i\le C$ 这里 $C$ 代表budget

C大margin大，更容易underfitting
C小margin小，更容易overfitting
只有margin上或者外面的点会影响classifier生成的超平面。但超级远的点也不会影响。
然后用不同的核函数就能做到non-linear的decision boundary。

形式化表达与核函数

$$f(x^*)=\beta_0+\Sigma_{i\in S}a_i\langle x^*,x_i \rangle$$

常见的核函数有：

• Polynomial kernel with degree $d$： $$K(x_i,x’i)=(1+\Sigma{j=1}^p\langle x_{ij},x’_{ij}\rangle)^d$$
• Radial-based kernel: $$K(x_i,x’_i)=\exp(-\gamma\Sigma^{p_{j=1}(x_{ij}-x’_{ij})}2)$$

和Logistic Regression的关系

SVM的优化问题可以表述为：

$$\min\limits_{\beta_0,\dots,\beta_p}\{\Sigma^n_{i=1}\max[0,1-y_if(x_i)]_++\lambda\Sigma^p_{j=1}\beta_j^2\}$$

和

$$\min\limits_{\beta_0,\dots,\beta_p}\{L(X,y,\beta)+\lambda P(\beta)\}$$

的形式类似。然后 SVM 的 $\max[0,1-y_if(x_i)]_+$这一项叫做hinge loss

所以说线性的 SVM 和 logistic regression 类似但使用了 hinge loss。

NN

首先复习普通的Logistic Regression， 它只能model linear function。

引入Non-linearity的方法就是给它加个线性变换，在新空间上做regression。比如$X\to X^2$
SVM引入一个内积函数 $K(\cdot,\cdot)$ 来完成这一点，其实就是把新空间设定为了$\Phi(X)$, 即RKHS（Reproducing Kernel Hilbert Space）。
这些都是固定的，我们该怎么做才能让机器“学习”呢？

下面引入单Hidden layer的NN

Single Hidden Layer

aka feed-forward NN, MuLtilayer Perception (MLP)

可以用来做regression和classification。

在regression时输出层只有一个Node。
在 $K$ 类分类时，$Y_i$ 代表着分为第 $i$ 类的probability。

每层的数学公式

隐藏层 $Z$: $Z_i = g(\alpha_{0m}+\alpha_m^TX), m=1,\dots,M$
输出层 ：
$T_k=\beta_{0k}+\beta_k^TZ,k=1,...K$
$Y_k=f_k(X)=g_k(T)$

对Regression来说，$g_k(T)=T_k$
对分类任务来说，要加一层softmax, $g_k(T)=\frac{e^{T_k}}{\Sigma_{i=1}^{K}e^{T_i}}$, 保证 $Y$ 求和时相加等于1.

激活函数

我们需要这个是因为如果没有它那么我的模型就还是linear的。

一个useful的函数是 sigmoid: $g(v)=\sigma(v)=\frac{1}{1+e^{-v}}$

Fitting

要求的是权重：

• $\{\alpha_{0m},\alpha_m;m=1,\dots,M\}$ M(p+1)
• $\{\beta_{0m},\beta_k;k=1,\dots,K\}$ K(p+1)

然后assess的标准是：

• Sum of square: $R(\theta)=\Sigma_{i=1}^N\Sigma_{k=1}^K(y_{ik}-f_k(x_i))^2$
• Cross Entropy: $R(\theta)=-\Sigma^N_{i=1}\Sigma^K_{k=1}y_{ik}\log f_k(x_i)$

然后fitting的方法是反向传播（back propagation），基于函数求导的链式法则。

反向传播

• $Z_m=g(\alpha_{0m}+a^T_mX), m=1,\dots,M$
• $T_k=\beta_{0k}+\beta^T_kZ$ and $Y_k=f_k(X)=g_k(T)$
• $z_{mi}=g(\alpha_{0m+}+\alpha^T_mx_i), z_i=(z_{1i},z_{2i},\dots,z_{mi})$

这里用 Sum of square 的话反向传播是这样的：

$\frac{\partial R_i}{\partial\beta_{km}}=\frac{\partial R_i}{\partial f}\frac{\partial f}{\partial g}\frac{\partial g}{\partial T}\frac{\partial T}{\partial \beta} =-2(y_{ik}-f_k(x_i))g'_k(\beta^T_kz_i)z_{mi}$

$\frac{\partial R_i}{\partial \alpha_{ml}}=\frac{\partial R_i}{\partial f}\frac{\partial f}{\partial g}\frac{\partial g}{\partial T}\frac{\partial T}{\partial Z} \frac{\partial Z}{\partial g}\frac{\partial g}{\partial \alpha}=-\sum_{k=1}^K2(y_{ik}-f_k(x_i))g'_k(\beta^T_kz_i)\beta_{km}g'(\alpha^T_mx_i)x_il$

然后取第一个柿子的 $z_mi$的系数为 $\delta_{ki}$, 第二个式子 $x_ml$ 的系数为 $s_mi$, $\gamma_r$ 为学习率。

然后有一个迭代公式：

$\beta^{(r+1)}_{km}=\beta^{(r)}_{km}-\gamma_r\Sigma_{i=1}^N\frac{\partial R_i}{\partial\beta_{km}^{(r)}}$
$\alpha$ 同理。

和一个等式：

$$s_{mi}=g'(\alpha^T_mx_i)\Sigma_{k=1}^K\beta_{km}\delta_{ki}$$

拥有了这些，我们就能描述反向传播的算法了。

1. 先拿现在的weight算出一个 $Y_k$
2. 计算对应的 $\delta_{ki}$, 再用之前的等式计算出 $s_{mi}$，然后用这些值去update。

Issues with training

初始值的选择： 一般randomly near-zero。
- 过大： poor solution
- 0 ： 什么都不会改变
- near zero： 一开始几乎线性，然后模型可以在需要non-linear的时候自主选择。

避免overfitting：
- Early stopping
- weight decay: 给error加一个值，如 $R(\theta)+\lambda J(\theta)$ where $J(\theta)=\Sigma_{km}\beta_km^2+\Sigma_{ml}\alpha_ml$
- Weight drop out: 类似决策树的剪枝。

Normalize the input.

Hidden layer 一般 50 to 100 层。

杂项

几种正则化方法

• L0: subset selection, 惩罚非零向量的个数
• L1: $\lambda\Sigma|\beta_i|$ -> 选择特征
• L2: $\lambda\Sigma|\beta^2_i|$ -> 缩小系数

Fairness

就是在很多分组不同的情况下，保证给出某种结果的概率一致。

Independence

如何达到这种独立性呢，我们可以选择：

1. Post-processing: 在训练后调整classifier
2. Train time constrain: optimization中添加约束。
3. Pre-processing:
   1. 提前打乱数据中的某种关系 (i.e. fair PCA)
   2. 一篇论文(Louizos et al.,2016), 用一个variational fair autoencoder

Separation

Pro: Penalize laziness: it provides incentive to reduce errors uniformly in all groups.

Con: It may not help closing the gap between to groups.

Sufficiency

Pros:
1. Satisfied by the Bayes optimal classifier
2. For predicting $Y$ we don’t need to see $A$ when we have $R$.

Con: It may not help closing the gap.

Tree based model & ML

Definition of C

表头	一般理解	课上定义
定义	C为Cost，Sum后为Penalty	C为Budget
柿子形式	+C$\Sigma\xi_i$	$\Sigma\xi_i<C$
柿子对于Over和Underfitting的影响	C小，总Penalty小，容易underfitting	Budget大，是Underfitting

Bagging & Boosting

Bagging: Parallel
Boosting: Sequential

OOB的好处都有啥（

可以在不用validation set的情况下估算模型error。

Tree Pruning

降低variance，防止overfitting。

SVM

cost parameter C

C decrease, vector的margin变大，数量变多，underfitting。可见C的第一种定义

以及和support vector最相关的是在margin周围的data point。

Soft-margin

对于$\xi_i>1$的data point，解读为misclassification。

Hyper plane

SV实际上是和相关data point距离之和最小的超平面。

对于hard-margin，只和margin周围的点有关。
对于soft-margin，和所有数据点有关

Kernel trick

• Using the kernel trick we can build non-linear SVM
• To train an SVM you only need the kernel matrix for the pairs of training points
• Any valid kernel function K(xi, xj) = <f(xi), f(xj)> in some (possibly infinite-dimensional) feature space.
• A kernel can’t be any symmetric function of its two arguments.
  因为这个Kernel function必须是半正定的

半正定的定义：
有函数：

$$k:X\times X\to R$$

对任意点集$x_1,\dots,x_n\in X$和任意实数$c_1,\dots,c_n$,都有

$$\sum_{i=1}^n\sum_{j=1}^nc_ic_jk(x_i,x_j)\ge 0$$

总结来说，就是由函数k生成的Gram矩阵$K_{i,j}=k(x_i,x_j)$必须是半正定的。
Gram矩阵就是每个向量两两内积生成的矩阵。

ML Model

如果一个模型的Activation function变为Linear的，那么这就是一个Linear model。

CNN的一个实现方法

CNN的一个操作是用一个小的filter去遍历整张图。

如何高效实现呢？观察乘后的矩阵，发现其实可以将图像展平为一个向量，然后构造一个总计算次数 X 向量长度的矩阵，然后拿展平的图去点积，每一行就是一次操作结果的扁平化。这样就可以快速便捷计算了。