感知机原理小结
损失函数为误分类点到分离超平面的总距离，$M$为误分类点集合：$$-\frac{1}{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)$$
不考虑$\frac{1}{||w||}$，就得到感知机学习的损失函数：$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$
感知机学习算法是误分类驱动的，采用随机梯度下降法对损失函数进行极小化。
$$\min_{w,b}L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$
1.选取初值 $w_0$ ，$b_0$$(x_i,y_i)$ $y_i(w\cdot x_i+b)\leq0$ ，则$w\leftarrow w+\eta y_i x_i$，$b\leftarrow b+\eta y_i$
对偶形式的基本思想是，将 $w,b$ 表示为 $x_i,y_i$ 的线性组合，通过求解其系数而求得 $w,b$ 。假设 $w_0$ ，$b_0$ 均为0，对误分类点通过上面的步骤3逐步修改 $w,b$ ，最后学习到的 $w,b$ 可以分别表示为：
$$w=\sum_{i=1}^{N}\alpha_i y_i x_i$$
$$b=\sum_{i=1}^{N}\alpha_i y_i$$
$\alpha_i=n_i\eta$ ，当$\eta=1$时，表示第 $i$ 个实例点由于误分而更新的次数，实例点更新次数越多，说明距离分离超平面越近，越难正确分类。$(x_i,y_i)$ $y_i(\sum_{j=1}^{N}\alpha_j y_j x_j\cdot x_i+b)\leq0$ ，则$\alpha_i\leftarrow \alpha_i+\eta$，$b\leftarrow b+\eta y_i$
简单易于实现，分为原始形式和对偶形式，是神经网络和支持向量机的基础。当训练集线性可分时，感知机学习算法收敛，存在无穷多个解（采用不同的初值或不同的迭代顺序）；线性不可分时，算法不收敛，迭代结果会发生震荡。感知机因为是线性模型，所以不能表示复杂的函数，如异或。
支持向量机通俗导论（理解SVM的三层境界） 数据挖掘（机器学习）面试--SVM面试常考问题 $y$ 为 +1 或 -1，模型 $f(x)=\text{sign}(w\cdot x+b)$ 。
函数间隔 ：几何间隔 ：
硬间隔最大化。求解能够正确划分训练数据集并且间隔最大的分离超平面。线性可分训练数据集的最大间隔分离超平面存在且唯一。$y_i(w\cdot x_i+b)-1=0$ ；间隔边界间的距离：$\frac{2}{||w||}$；在决定分离超平面时只有支持向量起作用，而其他实例点不起作用。原始最优化问题 ：$$\max_{w,b}\frac{\hat{\gamma}}{||w||} \quad \quad \text{s.t.} \quad y_i(w\cdot x_i+b)\geq\hat{\gamma}$$
$$\rightarrow \quad \min_{w,b}\frac{1}{2}{||w||}^2 \quad \quad \text{s.t.} \quad y_i(w\cdot x_i+b)-1\geq0$$ 对偶算法 ：$\alpha_i\geq0$ ，定义拉格朗日函数：$$L(w,b,\alpha)=\frac{1}{2}{||w||}^2-\sum_{i=1}^{N}\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^{N}\alpha_i$$
原始问题的对偶问题是极大极小问题：
$$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$$
1.求 $\min_{w,b}L(w,b,\alpha)$ ：$$\frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\alpha_iy_i x_i=0$$
$$\frac{\partial L}{\partial b}=-\sum_{i=1}^{N}\alpha_iy_i=0$$
代入得：
$$\min_{w,b}L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i$$
2.求 $\min_{w,b}L(w,b,\alpha)$ 对$\alpha$的极大，即求 $-\min_{w,b}L(w,b,\alpha)$ 对$\alpha$的极小，得到对偶最优化问题 $$\min_{\alpha}\quad\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i \quad\quad \text{s.t.}\quad\sum_{i=1}^{N}\alpha_iy_i=0, \quad \alpha_i\geq0$$
设 $\alpha^{\star}=({\alpha_1}^{\star},{\alpha_2}^{\star},\cdots,{\alpha_N}^{\star})^{\text T}$ 是对偶最优化问题的解，则存在下标 $j$ ，使得 ${\alpha_j}^{\star}>0$ ，并可按下式求得原始最优化问题的解：
$$w^{\star}=\sum_{i=1}^{N}{\alpha_i}^{\star}y_i x_i$$
$$b^{\star}=y_j-\sum_{i=1}^{N}{\alpha_i}^{\star}y_i(x_i\cdot x_j)$$
从而得到分离超平面：$w^{\star}\cdot x+b^{\star}=0$
软间隔最大化。对近似线性可分数据，对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\xi_i$ ，约束条件为 $y_i(w\cdot x_i+b)\geq1-\xi_i$ ，同时对每个松弛变量，支付一个代价。$(w,b,\xi)$ 的解是存在的，可以证明 $w$ 的解唯一，而 $b$ 的解可能不唯一，而是存在一个区间。原始最优化问题 ：$$\min_{w,b,\xi}\quad\frac{1}{2}{||w||}^2+C\sum_{i=1}^N\xi_i \quad \quad \text{s.t.} \quad y_i(w\cdot x_i+b)\geq1-\xi_i, \quad \xi_i\geq0$$
对偶算法 ：$$\min_{\alpha}\quad\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i \quad\quad \text{s.t.}\quad\sum_{i=1}^{N}\alpha_iy_i=0, \quad 0\leq\alpha_i\leq C$$
设 $\alpha^{\star}=({\alpha_1}^{\star},{\alpha_2}^{\star},\cdots,{\alpha_N}^{\star})^{\text T}$ 是对偶最优化问题的解，选择 $\alpha^{\star}$ 的一个分量 ${\alpha_j}^{\star}$ ，使得 $0<{\alpha_j}^{\star}< C$ ，计算：
$$w^{\star}=\sum_{i=1}^{N}{\alpha_i}^{\star}y_i x_i$$
$$b^{\star}=y_j-\sum_{i=1}^{N}{\alpha_i}^{\star}y_i(x_i\cdot x_j)$$
核技巧和软间隔最大化。$x_i \cdot x_j$ 用核函数 $K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j)$ 来代替。
SVM的核函数如何选取？ 线性核函数 (Linear) ：$K(x_1,x_2)=x_1\cdot x_2$，用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。高斯核函数 (RBF) ：$K(x_1,x_2)=\exp(-\frac{||x_1-x_2||^2}{2\sigma^2})$，高斯径向基函数，主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。多项式核函数 ：$K(x_1,x_2)=(x_1\cdot x_2+1)^p$字符串核函数 ：在文本分类、信息检索、生物信息学等方面有应用。
整个 SMO 算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。
优点 ：缺点 ：
逻辑回归 (logistic regressive) 线性回归原理小结 逻辑回归算法面经 LR与SVM的异同 SVM和logistic回归分别在什么情况下使用？ $P(Y|X)$ 表示，随机变量 $X$ 取实数，$Y$ 取值 1 或 0 。
$$P(Y=1|x)=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}$$
$$P(Y=0|x)=\frac{1}{1+\exp(w\cdot x)}$$
一个事件发生的几率 (odds) 指该事件发生的概率与该事件不发生的概率的比值。如果事件发生的概率是 $p$ ，则该事件的对数几率或 logit 函数为：$\text{logit}(p)=\log\frac{p}{1-p}$。对逻辑回归而言，$\log\frac{P(Y=1|x)}{1-P(Y=1|x)}=w\cdot x$。
给定数据集，$x_i\in R^n$，$y_i$ 为 0 或 1，使用极大似然估计法估计模型参数，从而得到逻辑回归模型。设：$$P(Y=1|x)=\pi(x), \quad\quad P(Y=0|x)=1-\pi(x)$$
似然函数为：
$$\prod_{i=1}^{N}[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$$
对数似然函数为：
$$\begin{aligned}
L(w)&=\sum_{i=1}^{N}[y_i\log\pi(x_i)+(1-y_i)\log(1-\pi(x_i))] \newline$L(w)$ 求极大值，得到 $w$ 的估计值。梯度下降或拟牛顿法。$$\frac{\partial L}{\partial w}=\sum_{i=1}^{N}(y_ix_i-\pi(x_i)x_i)\quad\rightarrow\quad w=w+\eta(y_i-\pi(x_i))x_i$$
$Y$ 的取值为 $1,2,\cdots, K$ ，多项逻辑回归模型为：
$$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{i=1}^{K-1}\exp(w_i\cdot x)},\quad k=1,2,\cdots,K-1$$
$$P(Y=K|x)=\frac{1}{1+\sum_{i=1}^{K-1}\exp(w_i\cdot x)}$$
最大熵模型 (maximum entropy model) 离散随机变量 $X$ 的概率分布是 $P(X)$ ，则其熵为：
$$H(P)=-\sum_{x}P(x)\log P(x)$$ $X$ 给定的条件下随机变量 $Y$ 的条件熵：
$$H(Y|X)=\sum_{x}P(x)H(Y|X=x)$$ $X$ 取值的个数，当且仅当 $X$ 的分布是均匀分布时右边等号成立，熵最大。
最大熵模型可以由最大熵原理推导得出，最大熵原理应用到分类模型的学习中，得到一个约束最优化问题，求解此最优化问题的对偶问题得到最大熵模型。$$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_i f_i(x,y))$$
$$Z_w(x)=\sum_y\exp(\sum_{i=1}^{n}w_i f_i(x,y))$$
$Z_w(x)$ 是规范化因子，$f_i$ 为特征函数，$w_i$ 为特征的权值。
优点 ：缺点 ：
基本的分类与回归方法。输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k近邻法假设给定一个训练数据集，其中的实例类别已定，分类时，对新的实例，根据其 $k$ 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻法不具有显示的学习过程，实际上利用训练数据集对特征向量空间进行划分，并作为其分类的模型。$k$ 值的选择、距离度量、分类决策规则是k近邻法的三个基本要素。$k$ 值的选择$k$ 值减小，整体模型变得复杂，容易发生过拟合，近似误差减小，估计误差增大；$k$ 值增大，整体模型变得简单，估计误差减小，近似误差增大。距离度量 ：$L_p$ 距离 (Minkowski 距离)：$p\geq1$。$p=1$ ：曼哈顿距离；$p=2$：欧氏距离距离；$p=\infty$：切比雪夫距离。分类决策规则 ：往往是多数表决，多数表决规则等价于经验风险最小化。$k$ 个最近邻点。kd树是一种便于对 $k$ 维空间中的数据进行快速检索的数据结构，是二叉树，表示对 $k$ 维空间的一个划分，其每个结点对应于 $k$ 维空间划分中的一个超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。
常见的距离度量：欧氏距离、曼哈顿距离、切比雪夫距离、余弦距离。K-Means聚类算法原理 BIRCH聚类算法原理 DBSCAN密度聚类算法 谱聚类（spectral clustering）原理总结
基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率密度；然后基于此模型，对给定的输入 $x$ ，利用贝叶斯定理求出后验概率最大的输出 $y$ 。朴素贝叶斯法实现简单，学习与预测的效率都很高，但分类的准确率不一定高。
先验概率分布：$P(Y=c_k),\quad k=1,2,\cdots, K$$P(X,Y)$ 。
用极大似然估计 法估计相应的概率。$P(Y=c_k)$ 的极大似然估计：
$$P(Y=c_k)=\frac{\sum_{i=1}^{N}I(y_i=c_k)}{N}$$
条件概率 $P(X^{(j)}=a_{jl}|Y=c_k)$ 的极大似然估计：$$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^{N}I(y_i=c_k)}$$
用极大似然估计可能会出现所要估计的概率值为0的情况，这时会影响到后验概率的计算结果，使分类产生偏差，解决方法是采用贝叶斯估计 。$\lambda\geq0$，$\lambda=1$ 时称为拉普拉斯平滑。$$P_\lambda(Y=c_k)=\frac{\sum_{i=1}^{N}I(y_i=c_k)+\lambda}{N+K\lambda}$$
$$P_\lambda(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum_{i=1}^{N}I(y_i=c_k)+S_j\lambda}$$
分类时 ，对给定的输入 $x$ ，通过学习到的模型计算后验概率分布 $P(Y=c_k|X=x)$ ，将后验概率最大的类作为 $x$ 的类输出。后验概率的计算根据贝叶斯定理进行：$$y=\text{arg}\max_{c_k} P(Y=c_k)\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_k)$$
后验概率最大化等价于0-1损失函数时的期望风险最小化。
EM算法原理总结 $Y$ ，隐变量数据 $Z$ ，EM算法通过迭代求 $L(\theta)=\log P(Y|\theta)$ 的极大似然估计，每次迭代包含两步：E步，求期望；M步，求极大化。$\theta^{(0)}$ ，开始迭代；$\theta^{(i)}$ 为第 $i$ 次迭代参数 $\theta$ 的估计值，在第 $i+1$ 次迭代的E步，计算：$Q(\theta,\theta^{(i)})$ 极大化的 $\theta$ ，确定第 $i+1$ 次迭代的参数的估计值 $\theta^{(i+1)}$ ：$$\theta^{(i+1)}=\text{arg}\max_\theta Q(\theta,\theta^{(i)})$$ $Q(\theta,\theta^{(i)})$ 是EM算法的核心，称为 $Q$ 函数，为完全数据的对数似然函数 $\log P(Y,Z|\theta)$ 关于在给定观测数据 $Y$ 和当前参数 $\theta^{(i)}$ 下对未观测数据 $Z$ 的条件概率分布 $P(Z|Y,\theta^{(i)})$ 的期望。$P(X,Y)$ 表示，可以认为非监督学习训练数据是联合概率分布产生的数据，$X$ 是观测数据，$Y$ 是未观测数据。
高斯混合模型（GMM）
隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态的序列，再由各个状态随机生成一个观测而产生观测的序列的过程。由初始状态概率向量 $\pi$ 、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。因此，隐马尔可夫模型可以写成 $\lambda=(A,B,\pi)$ 。
给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$ 。
已知观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大，即用极大似然估计的方法估计参数。Baum-Welch算法，也就是EM算法可以高效地对隐马尔可夫模型进行训练，它是一种非监督学习算法。
也称为解码问题，已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_i,i_2,\cdots,i_T)$ ，即给定观测序列，求最有可能的对应的状态序列。
条件随机场CRF(一)从随机场到线性链条件随机场 如何轻松愉快地理解条件随机场（CRF）？ HMM、MEMM vs CRF 对比？
又称马尔可夫随机场 (MRF)，是一个可以由无向图表示的联合概率分布。无向图上的结点之间的连接关系表示了联合分布的随机变量集合之间的条件独立性，即马尔可夫性。$P(Y)$ ，由无向图 $G=(V,E)$ 表示，在图 $G$ 中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布 $P(Y)$ 满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型或马尔可夫随机场。
是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。即，条件随机场是给定随机变量 $X$ 条件下，随机变量 $Y$ 的马尔可夫随机场。线性链条件随机场 ：由输入序列对输出序列预测的判别模型，一般表示为给定观测序列条件下的标记序列的条件概率分布，形式为参数化的对数线性模型，其学习方法通常是极大似然估计或正则化的极大似然估计。$$P(y|x)=\frac{1}{Z(x)}\exp(\sum_{i,k}\lambda_k t_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_l s_l(y_i,x,i))$$
$$Z(x)=\sum_y\exp(\sum_{i,k}\lambda_k t_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_l s_l(y_i,x,i))$$
给定条件随机场 $P(Y|X)$ ，输入序列 $x$ 和 输出序列 $y$ ，计算条件概率 $P(Y_i=y_i|x)$ ，$P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 以及相应的数学期望。使用前向-后向算法递归地计算。
给定训练数据集估计条件随机场模型的参数，条件随机场模型实际上是定义在时序数据上的对数线性模型，其学习方法包括极大似然估计和正则化的极大似然估计，具体的优化实现算法有改进的迭代尺度法、梯度下降法、拟牛顿法。
给定条件随机场 $P(Y|X)$ 和输入序列（观测序列）$x$，求条件概率最大的输出序列（标记序列）$y^{\star}$，即对观测序列进行标注，使用维特比算法。
决策树算法原理(上) 决策树算法原理(下)
特征选择在于选取对训练数据具有分类能力的特征。
熵表示随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为 $P(X=x_i)=p_i,\quad i=1,2,\cdots,n$ ，则随机变量 $X$ 的熵定义为：
$$H(p)=H(X)=-\sum_{i=1}^{n}p_i\log p_i$$
设随机变量 $(X,Y)$ ，条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$$H(Y|X)=\sum_{i=1}^{n}p_iH(Y|X=x_i)$$
信息增益表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ ，定义为集合 $D$ 的经验熵与特征 $A$ 给定条件下 $D$ 的经验条件熵之差：$$g(D,A)=H(D)-H(D|A)$$
$$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}\log\frac{|C_k|}{|D|}$$
$$H(D|A)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}\log\frac{|D_{ik}|}{|D_i|}$$
以信息增益作为划分训练数据集的特征，偏向于选择取值较多的特征。特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益与训练数据集 $D$ 关于特征 $A$ 的值的熵之比：
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
$$H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}\log\frac{|D_i|}{|D|}$$
分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为：
$$\text{Gini}(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}{p_k}^2$$
对于给定的样本集合 $D$ ，其基尼指数为：
$$\text{Gini}(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2$$
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为：
$$\text{Gini}(D,A)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2)$$
基尼指数 $\text{Gini}(D)$ 表示集合 $D$ 的不确定性，基尼指数 $\text{Gini}(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也就越大。
通常使用信息增益最大 (ID3)、信息增益比最大 (C4.5)、基尼指数最小 (CART) 作为特征选择的准则。通过计算上述指标，从根结点开始，递归地产生决策树。这相当于用上述准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。
剪枝：在决策树学习中将已生成的树进行简化的过程，从已生成的树上剪掉一些叶节点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点。通过极小化决策树整体的损失函数来实现。
$$C_\alpha(T)=C(T)+\alpha|T|$$
$C(T)$ 表示模型对训练数据的预测误差，$|T|$ 表示模型复杂度，$\alpha\geq0$，较大的 $\alpha$ 促使选择较简单的树，较小的 $\alpha$ 促使选择较复杂的树，$\alpha=0$ 不考虑模型的复杂度。
CART可用于分类与回归。假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
集成学习原理小结
集成学习之Adaboost算法原理小结 $$f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)$$
AdaBoost的每次迭代可以减少它在训练数据集上的分类误差率，这说明了它作为提升方法的有效性。
提升树是以分类树或回归树为基本分类器的提升方法，被认为是统计学习中性能最好的方法之一。梯度提升决策树 (GBDT) ：梯度提升树(GBDT)原理小结 $$f_0(x)=\text{arg}\min_c\sum_{i=1}^N L(y_i,c)$$
2.对 $m=1,2,\cdots,M$ $i=1,2,\cdots,N$ ，计算：$$r_{mi}=-\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\right] \quad \leftarrow f(x)=f_{m-1}(x)$$
(b) 对 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶结点区域 $R_{mj}$ $j=1,2,\cdots,J$ ，计算：$$c_{mj}=\text{arg}\min_c\sum_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$$
(d) 更新：$$f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J}c_{mj}I(x\in R_{mj})$$
3.得到回归树：$$\hat{f}(x)=f_M(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c_{mj}I(x \in R_{mj})$$
算法第1步初始化，估计使损失函数极小化的常数值，它是只有一个根结点的树。第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差，对于一般损失函数，它就是残差的近似值。第2(b)步估计回归树叶结点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计叶结点区域的值，使损失函数最小化。第2(d)步更新回归树。第3步得到输出的最终模型。
XGBoost算法原理小结 RF、GBDT、XGBoost、lightGBM原理与区别
Bagging与随机森林算法原理小结 Bagging和Boosting 概念及区别
奇异值分解(SVD)原理与在降维中的应用 特征分解 ：$$A[w_1,w_2,\cdots,w_n]=[w_1,w_2,\cdots,w_n]\Sigma$$
$\Sigma$ 为这 $n$ 个特征值为主对角线的 $n\times n$ 维矩阵。若 $w_1,w_2,\cdots,w_n$ 线性无关，则
$$A=W\Sigma W^{-1}$$ $n\times n$ 的实对称矩阵 $A$ ，有 $n$ 个特征值 $\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n$ ，及对应的特征向量 $w_1,w_2,\cdots,w_n$ ，可正交相似对角化。对特征向量标准化后，这 $n$ 个特征向量为标准正交基，满足 $W^TW=I$ ，即 $W$ 为酉矩阵，则$$A=W\Sigma W^{T}$$ SVD ：$$A_{m \times n} = U_{m \times m}\Sigma_{m \times n} V_{n \times n}^T$$
$U$ 和 $V$ 都是酉矩阵，$V$ 由 $A^TA$ 的所有特征向量组成，$U$ 由 $AA^T$ 的所有特征向量组成，奇异值 $\sigma_i = \sqrt{\lambda_i}$ ，$\lambda_i$ 为 $A^TA$ 的非0特征值， $A^TA$ 和 $AA^T$ 的非0特征值相同。$k$ 个的奇异值和对应的左右奇异向量来近似描述矩阵。
$$A_{m \times n} = U_{m \times m}\Sigma_{m \times n} V_{n \times n}^T\approx U_{m \times k}\Sigma_{k \times k} V_{n \times k}^T$$
PCA的数学原理 主成分分析（PCA）原理总结 典型关联分析(CCA)原理总结 $m$ 个 $n$ 维的样本 $X_{n\times m}$ ，降到 $k$ 维。$XX^T$ $XX^T$ 进行特征值分解：$XX^T=W\Sigma W^T$$k$ 个特征值对应的特征向量 $w_1,w_2,\cdots,w_k$ ，将所有的特征向量标准化后，组成特征向量矩阵 $P$ $x$ ，转化成新的样本 $z=P^Tx$ $Z_{k\times m}$
线性判别分析LDA原理总结 $k-1$ 的维数，而PCA没有这个限制；
局部线性嵌入(LLE)原理总结 $W$ ；第三步就是利用权重系数来在低维里重构样本数据。
监督学习的任务就是学习一个模型，应用这一模型，对给定的输入预测相应的输出。这个模型的一般形式为决策函数：$Y=f(X)$，或者条件概率分布：$P(Y|X)$。朴素贝叶斯、隐马尔可夫模型 (HMM)、高斯混合模型、隐含狄利克雷分布 (LDA) 优点 ：可以还原出联合概率分布${P(X,Y)}$；学习收敛速度更快；当存在隐变量时，仍可以用生成方法学习，而不能用判别方法。k近邻法、感知机、决策树、逻辑回归、线性回归、最大熵模型、支持向量机 (SVM)、提升方法 (boosting)、条件随机场 (CRF)、神经网络、线性判别分析 (LDA) 优点 ：直接面对预测，往往学习的准确率更高；可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
特征工程之特征选择 特征工程之特征表达 特征工程之特征预处理
最小二乘法小结
交叉验证(Cross Validation)原理小结