机器学习算法推导（一）

作者: 咸鱼干lili | 来源:发表于2018-09-04 17:46 被阅读0次

python数据分析与机器学习(Numpy,Pandas,Mat
机器学习算法推导（一）
机器学习学习规划
机器学习：SVM算法推导
机器为什么能学习(上)
杭州7月python大数据机器学习高级工程师实战研讨会
AI 入门书单推荐及学习方法
逻辑回归代价函数及其梯度下降公式推导
2018-05-18
机器学习算法推导「代码已经更新」

Content

PCA(Principal Components Analysis) 主成分分析

主要用于对数据降维：把高维数据投影到方差最大的几个方向上
- 高维数据中有很多特征相关
- 高维数据难以计算
衡量指标
- 前K大个特征与总特征m之比
- 一般要大于85%
手推计算过程
- 参考文章：http://blog.codinglabs.org/articles/pca-tutorial.html
- 降维问题实际上是一种基变换，当基的个数K小于数据维度N时，达到降维的目的
- 基变换的矩阵表示为：其中基为，每一条记录为
  $\begin{equation} \left( \begin{matrix} p_1 \\ p_2 \\ .\\ .\\ .\\ P_k \\ \end{matrix} \right) \ \left( a_1 \ a_2\ ...\ a_n \right) \end{equation}$
- 协方差矩阵：是一个实对称矩阵。负对角元素为字段a和b的方差，主对角元素为字段a和b的协方差。我们需要找到方差最大的方向，和字段之间无线性相关性（即协方差为0）的新的基。
  $X = \left( \begin{matrix} a_1\ a_2\ ...\ a_n \\ b_1\ b_2\ ...\ b_n \\ \end{matrix} \right) \tag{3} \\ \frac{1}{m}XX^T = \left( \begin{matrix} \frac{1}{m} \sum_{i=1}^m a_i^2 \ \ \ \frac{1}{m} \sum_{i=1}^m a_ib_i \\ \frac{1}{m} \sum_{i=1}^m a_ib_i \ \ \ \frac{1}{m} \sum_{i=1}^m b_i^2 \\ \end{matrix} \right) \$
- 实对称矩阵：设A为实对称矩阵，则存在正交矩阵Q，使得A对角化，即 $Q^{-1}AQ = Q^TAQ = \Lambda$
  由性质：1）不同特征值对应的特征向量必然正交；2）设特征向量λλ重数为r，则必然存在r个线性无关的特征向量对应于λλ，因此可以将这r个特征向量单位正交化。一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量。
- 优化目标变成了寻找一个矩阵P，满足 $PCP^T$ 是一个对角矩阵，并且对角元素按从大到小依次排列，那么P的前K行就是要寻找的基，用P的前K行组成的矩阵乘以X就使得X从N维降到了K维并满足上述优化条件。P为协方差矩阵对角化的P
PCA 计算过程
计算实例：求矩阵特征值与特征向量的步骤
求矩阵特征值与特征向量的步骤

具体例子：

求特征值和特征向量

求特征值和特征向量g

KNN(K Nearest Neighbor) K近邻

KNN Regression: $f(x) = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i$

$K \to 1$ , more flexible

$K \to \infty$ , a traight line that is similar to linear regression

在高维数据下误差增大

LR(Logistic Regression）

OLS (Ordinary Least Squares)+ Lasso + Ridge

OLS

设 $X = (x_1, x_2, …, x_n)^T \in R^{n*p}$ , $y = (y_1, y_2,…, y_n)^T \in R^n$ 分别表述数据矩阵和标签向量

那么 $\hat{f(x)} = \sum_{i=1}^n \hat{\beta_0} + \hat{\beta_1}x_1 + … +\hat{\beta_p }x_p = \beta^TX$ , 其中 $\beta$ 为列向量

损失函数为预测值尽可能靠近真实值，因此：
$J(\beta) = \frac{1}{n} \sum_{i=1}^n(y_i - \hat{f(x_i)})^2 = \frac{1}{n} ||y-\beta^TX||^2 = \frac{1}{n} ||y-X\beta||^2$

求导令其等于0，可解得解析解：
$X^T(y - X \beta) = 0 \\ X^TX\beta = X^Ty \\ \hat{\beta} = (X^TX)^{-1}X^Ty$

那么 $\hat{y} = X(X^TX)^{-1}X^Ty$

Goodness of Fit: $R^2= 1- \frac{RSS}{\sum(y_i - \bar{y})}$

Ridge Regression minimizes loss function：
$\sum_{i=1}^n(y_i - \beta_0-\sum_{j=1}^p \beta_jx_{ij})^2 +\lambda\sum_{j=1}^p\beta_j^2$

主要：1）解决 $X^TX$ 矩阵奇异 2）使预测值方差小

Lasso
$\sum_{i=1}^n(y_i - \beta_0-\sum_{j=1}^p \beta_jx_{ij})^2 +\lambda\sum_{j=1}^p|\beta_j|$

主要解决：1）不重要的变量衰减至0

可以利用交叉验证定 $\lambda$ , $\lambda \to 0$ 与OLS相同, $\lambda \to \infty$ 所有系数为0

SVM(Support Vector Machine)

线性可分的情况

线性可分的情况

需要找到一个超平面(hyperplane)分开两类不同的点，标签 $y \in \{-1,1\}$ 。定义超平面为 $\{x: W^Tx + b = 0\}$ , 任意 $x_0$ 在该超平面的点满足 $W^Tx_0 = -b$ 。
定义间隔(margin)为 $m$ , 表示支持向量到超平面的距离，即所有距离里的最小值。当间隔 $m$ 越大，表示分类越正确。
对任意的点 $x_i$ 到超平面的距离为 $<\frac{W}{||W||}, x_i- x_0> = \frac{W^Tx_i -W^Tx_0}{||W||} = \frac{W^Tx_i+b}{||W||}$ 。距离可正可负，因此乘以 $y$ 恒大于等于0。

因此上述问题可以写为一个凸优化问题：
$max \ \ \ m \\ s.t. \ \frac{1}{||W||}y_i(W^Tx_i+b) \ge m \ \ \ \forall x_i$

令 $m = \frac{1}{||W||}$ ，上述等价于
$max \ \ \ \frac{1}{||W||} \\ s.t. \ \ \ y_i(W^Tx_i+b) \ge 1 \ \ \ \forall x_i$

又等价于
$min \ \ \ \frac{1}{2} ||W||^2\\ s.t. \ \ \ y_i(W^Tx_i+b) \ge 1 \ \ \ \forall x_i$
如何求解？首先转化为对偶问题：https://www.jianshu.com/p/96db9a1d16e9
$L(W, b, \alpha) = \frac{1}{2} ||W||^2 - \sum_{i=1}^m \alpha_i (y_i (b+W^Tx_i) -1)$
$g(\alpha) = inf_{W, b} L(W, b, \alpha) = inf_{W,b}(\frac{1}{2} ||W||^2 - \sum_{i=1}^m \alpha_i (y_i (b+W^Tx_i) -1)$

对 $W, b$ 求导
$\frac{\partial L}{\partial W} = W- \sum_{i=1}^m \alpha_iy_ix_i = 0 \\ \frac{\partial L}{\partial b} = - \sum_{i=1}^m \alpha_i y_i = 0$

因此
$L(W,b,\alpha)= \frac{1}{2}||W||^T - b\sum_{i=1}^m \alpha_iy_i - W^T \sum_{i=1}^m \alpha_i y_ix_i + \sum_{i=1}^m \alpha_i \\ = \frac{1}{2}W^T(W-2\sum_{i=1}^m \alpha_i y_ix_i) - b\sum_{i=1}^m \alpha_iy_i + \sum_{i=1}^m \alpha_i \\ = -\frac{1}{2}(\sum_{i=1}^m \alpha_i y_ix_i)^T(\sum_{i=1}^m \alpha_i y_ix_i) - b\sum_{i=1}^m \alpha_iy_i + \sum_{i=1}^m \alpha_i \\= - \frac{1}{2} \sum_{i,j=1}^m \alpha_i \alpha_j x_i x_j y_i y_j - b\sum_{i=1}^m \alpha_iy_i + \sum_{i=1}^m \alpha_i$

那么其对偶问题为：
$max \ \ \ \sum_{i=1}^m \alpha_i- \frac{1}{2} \sum_{i,j=1}^m \alpha_i \alpha_j x_i x_j y_i y_j \\ s.t. \ \ \ \alpha_i \ge 0 \ \ \ \forall i \\ \sum_{i=1}^m \alpha_i y_i = 0$

Naive Bayse 朴素贝叶斯(生成模型)

假设某个体有n项特征（Feature），分别为 $F_1, F_2,…,F_n$ ; 有m个类别（Category），分别为 $C_1, C_2, …, C_m$ 。

由贝叶斯公式得到：

$P(C_i|F_1, F_2,..F_n) = \frac{P(F_1,F_2,…,F_n|C_i)P(C_i)}{P(F_1,F_2,..,F_n)} \\ \propto P(F_1,F_2,…,F_n)P(C_i)$

重要假设：所有特征条件独立

那么上式等价于： $P(C_i|F_1, F_2,..F_n) \propto P(F_1|C_i)P(F_2|C_i)…P(F_n|C_i)$

最后计算出概率最大的那个分类： $C^* = argmax_{C_i} P(F_1|C_i)P(F_2|C_i)…P(F_n|C_i)$

离散的情况：可直接根据样本计算 $P(F_1|C_i) = \frac{ \#F_1}{\#C_i}$

连续的情况：假设 $P(X|C_i)$ 服从正态分布，参数估计出 $\hat{\mu} |_{C_i} = \bar X |_{C_i} , \ \hat{\sigma^2} |_{C_i}= \frac{1}{n-1}\sum_{i=1}^n(x_i-\bar{x})|_{C_i}$

那么 $P(x_i|C_i) =\frac{1}{\sqrt{2 \pi} \hat{\sigma}}e^{-\frac{(x-\hat{\mu})^2}{2 \hat{\sigma}^2}}|_{C_i}$ 再带回计算即可。

Tree-Based

A Single Tree : Grow a large tree, then prune it.

Nodes：Root Node、Terminal Node（Leaf Node）、Parent Node、Child Node

纯度（Impurity）是树分裂判断标准(Split Criteria)，包括：Gini index、Entropy、Misclassification Error

Gini index： $Gini(node) = \sum_{i=1}^n p_k(1-p_k)$
Entropy: $Entropy(node) = -\sum_{k=1}^k p_k \ log\ p_k$
Misclassification Error: $Error(node) = 1- max_{k} p_k$

以红色点和绿色点二分类为例子， $p_k = \frac{\# red \ points}{\# total \ points}$

每次选择使纯度(Impurity)降低最多的划分，属于贪心算法，不是全局优化。

$X_{Split} = argmax \{Q_{split}\} =\\ argmax \{ Impurity(parent) - [\frac{N_{left}}{N_{parent}} Impurity(left) + \frac{N_{right}}{N_{parent}} Impurity(left)] \}$

决策树足够大时，会出现过拟合。一般来说，会进行CCP剪枝。

CCP(Cost-Complexity Pruning): 实际上是纯度与模型复杂度的Trade Off，模型复杂度(叶子结点的个数)作为正则项。

$C_\alpha = \sum_{t=1}^{|T|} N_t Impurity(S_t) + \alpha * |T|$

其中 $|T|$ 为叶子节点个数， $S_t$ 为第t个小空间

优点：1）容易实现；2）可以做变量选择；3）交互项的影响可以表示；4）树小的时候模型解释性好；5）连续型和离散型变量均可；

缺点：2）不稳定：对扰动和噪声非常敏感

Bagging ：Fit many large trees to bootstrap resampled versions of the training data, and classify by majority vote

1）有放回抽样至原来数据集大小。假设每次被采到的概率是 $\frac{1}{n}$ ，那么一次也没有采到的概率是 $(1-\frac{1}{n})^n$ , 当 $n \to \infty \ \ ， \lim \limits_{n \to \infty } (1-\frac{1}{n})^n = \frac{1}{e} \approx 0.368$ 。即每一颗树大约有1/3的数据没有使用，称之为袋外数据（Out of Bag）

2）采取Majority Vote的方式给出最后的分类

3）主要是降低方差

4）树与树之间是高度相关的（协方差高）

Random Forests：a random sample of m predictors is chosen as split candidates from the full set of p predictors (Usually $m ≈ \sqrt{p}$ ).

1）有放回的从所有特征里随机抽取m个特征，根据这m个特征构建树（小树即可）

2）减小树与树之间的相关性，能减少更多的方差

3）优点

几乎没有需要提前设置的参数
高维度数据依然可行
可以输出特征的重要性

AdaBoost ：调整分类错误的数据点的权重

1）每一次新建一颗树都是在上一颗分类结果上调整权重后，初始权重均为 $\frac{1}{n}$

2）权重调整公式：

$w_i \leftarrow w_i*exp[\alpha_m * I(y_i \ne T_m(x_i)]$

最后renormalize $w_i$ ，使得和为1；

其中
$\alpha_m = log(\frac{1-err_m}{err_m}) \\ err_m = \frac{\sum_{i=1}^n w_i I(y_i \ne T_m{x_i}) }{\sum_{i=1}^n w_i}$

可以看到 $0 \le err_m \le 1 \ \ , \frac{1-err_m}{err_m} \ge 0$ ，当 $err_m = \frac{1}{2}$ 时， $\alpha_m = 0$ ，意思是有一半的分类是错误的。而我们知道完全随机的情况，猜错的概率为1/2，因此如果该树具有一定的判断能力，那么一定有 $err_m \le \frac{1}{2}$ 。此时 $\alpha_m \ge 0$ ，对于错误的分类的权重会变大。

最后的分类结果： $\hat{C(x)} = sign[\sum_{m=1}^M \alpha_m T_m(x)]$

python数据分析与机器学习(Numpy,Pandas,Mat
机器学习怎么学？机器学习包含数学原理推导和实际应用技巧，所以需要清楚算法的推导过程和如何应用。深度学习是机器学...
机器学习算法推导（一）
目录 PCA(Principal Components Analysis) 主成分分析主要用于对数据降维：把高维...
机器学习学习规划
工作三年，近期打算重新深入学习机器学习： 1.西瓜书机器学习基本概念和基础算法理解以及背后数学原理推导，经典算法...
机器学习：SVM算法推导
理论推导自己手操一遍加深记忆!
机器为什么能学习(上)
本篇文章是台湾大学《机器学习基石上》的课程笔记。以PLA算法为例，推导证明机器学习的可行性。问题概述机器学习在...
杭州7月python大数据机器学习高级工程师实战研讨会
课程介绍本课程特点是从数学层面推导最经典的机器学习算法，以及每种算法的示例和代码实现（Python）、如何做算法...
AI 入门书单推荐及学习方法
关于机器学习，非数学/统计专业的人都会有这些疑问：到底要把数学学到什么程度才能够无障碍地推导机器学习算法？实变、...
逻辑回归代价函数及其梯度下降公式推导
逻辑回归是机器学习算法中常用的算法之一，其简单，容易理解，故被后人广泛使用。今天来总结下它的损失函数及其推导过程。...
2018-05-18
《算法》跳跃游戏思路分析举例如下：代码实现《机器学习》朴素贝叶斯分类器公式推导一条数据x，具有特征...
机器学习算法推导「代码已经更新」
在重新实现机器学习算法时，重新认识到理论和数学的可理解性，通过非常简单的编程就可以实现BP、Lagrange mu...