吐槽完了，现在把今年学过的东西复习一下，顺便立一个小小的目标——希望明年可以去百度IDG或者达摩院或者腾讯 AI lab 去实习。
一、统计机器学习基础
1、监督学习
输入空间：输入所有可能的取值的集合。输出空间：输出所有可能的取值的集合。- 每个具体的输入是一个
实例，通常由特征向量表示，这时，所有特征向量存在的空间称为特征空间。（特征空间有时和输入空间相同，有时则不同，不同的时候就需要将输入空间映射到特征空间。） - 联合概率分布：监督学习假设输入与输出随机变量X和Y服从
联合概率分布P(X,Y)，X和Y具有联合概率分布的假设就是监督学习关于数据的基本假设。 假设空间：监督学习的目的在于学习一个由输入到输出的映射，这个映射由模型表示。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间。假设空间的确定即意味着学习范围的确定。监督学习的模型可以是概率模型或判别模型，由条件概率分布P(Y|X)或者决策函数Y=f(X)决定。在监督学习中，假设训练数据与测试数据是依联合概率分布P(X,Y)独立同分布的。
2、统计学习三要素
方法 = 模型+策略+算法
1）模型
在监督学习中，模型即为所要学习的条件概率分布式或决策函数，模型的假设空间包含所有可能的条件概率分布或决策函数。
针对判别模型，可以得到其假设空间为$${\cal F}=\lbrace f|Y=f(X)\rbrace$$ 其中X和Y是定义在输入空间和输出空间上的变量，这时集合通常是由一个参数向量构成的函数族\({\cal F}=\lbrace f|Y=f_\theta(X),\theta \in R^n\rbrace\)
参数向量属于参数空间。假设空间也可以定义为条件概率的集合$${\cal F}=\lbrace P|P(Y|X)\rbrace$$ 这时\({\cal F}\)通常是由一个参数向量决定的条件概率分布族\({\cal F}=\lbrace P|P_\theta(Y|X),\theta \in R^n\rbrace\)
2)策略
统计机器学习的目的在于从假设空间中选取最优模型。
损失函数：度量模型一次预测的好坏
风险函数：度量平均意义下的模型预测的好坏。
i) 模型f(x)关于训练数据的平均损失称为经验风险，记作\({\cal R_{emp}}\)
$${\cal R_{emp}} = {1 \over N} \sum_i^N L(y_i,f(x_i))$$
经验风险最小化的策略认为，经验风险最小的模型即为最优模型。根据这一策略，按经验风险最小化求最优模型即为求解最优化问题。ii)结构风险最小化是为了防止过拟合而提出的策略，它是在经验风险之后再加上正则化项，它的定义为：
$${\cal R_{emp}} = {1 \over N} \sum_i^N L(y_i,f(x_i)) + \lambda J(f)$$
其中\(\lambda J(f)\)是模型复杂度。
结构风险最小的策略认为，结构风险最小的模型即为最优模型。根据这一策略，按结构风险最小化求最优模型即为求解最优化问题。3）算法
学习模型的具体算法。统计机器学习基于训练数据集，根据学习策略，从假设空间中选取最优模型，算法即考虑用什么样的方法求解最优模型。
3、正则化与交叉验证
1）正则化
正则化是结构经验风险最小化的实现，是在经验风险上加一个正则化项，正则化项一般是模型复杂度的单调递增函数。正则化项可以是参数向量的L1范数，也可以是参数向量的L2范数。
2）交叉验证
当数据集较大时，训练集用于训练模型，验证集用于模型选择，测试集用于对学习方法的评估。但由于许多实际应用中数据是不充分的，为了选择好的模型，可以采用交叉验证的方法。交叉验证的基本思想是重复的使用数据。
i)简单交叉验证：先随机将已给数据分为两部分，一部分作为训练集，另一部分作为测试集，然后用训练集在各种条件下（如不同参数个数）训练模型，从而得到不同模型，在测试机上评估各个模型的测试误差，选出最佳的模型。
ii)S折交叉验证：先随机地将数据分为S个互不相交地大小相同地子集，然后用S-1个子集地数据用于训练，利用余下的子集作为测试集；将此过程对可能的S种选择重复进行，最后选出S次测评中平均测试误差最小的模型。4、生成模型与判别模型
监督学习可以分为生成方法和判别方法。
1）生成方法由数据学习联合概率分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：
$$P(Y|X) = {P(X,Y) \over P(x)}$$
2)判别法由数据直接学习决策函数f(x)或条件概率分布P(Y|X)作为预测模型，即判别模型。
二、感知机
感知机是一种二分类的
线性分类模型，属于判别模型。它旨在求出将训练数据进行线性划分的分离超平面。1、感知机模型
- 输入空间（特征空间）：\(R^n\)
输出空间：\({\cal y} \in \lbrace +1,-1 \rbrace\)
由输入空间到输出空间的如下函数称为感知机$$f(x)=sign(w·x+b)$$
其几何解释为：线性方程w·x+b=0对应于特征空间\(R^n\)中的一个超平面S，其中w是超平面的法向量。超平面将特征空间分为两部分。位于两部分的点被分为正负两类。2、感知机策略
定义（经验）损失函数并将损失函数最小化
现定义损失函数为误分类点到超平面S的总距离：$$L(w,b)=- \sum_{x_i \in M} y_i(w·x_i+b)$$ 其中M为误分类点集合3、感知机学习算法：
1）采用SGD。首先，任意选取一个超平面\(w_0\),\(b_0\)。然后用随机梯度下降不断地极小化目标函数。极小化过程中不是一次使用M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
输入：训练数据集\(T=\lbrace(x_1,y_1),…,(x_N,y_N)\rbrace\),其中\(x_i \in R^n\)，\(y_i \in \lbrace-1,+1\rbrace\)，学习率为\(\eta\)
输出：w，b，感知机模型机\(f(x)=sign(w·x+b)\)。
（1）任意选取初值\(w_0\),\(b_0\)
（2）在训练数据集T中选取数据\((x_i,y_i)\)
（3）若\(y_i(w·x+b)<=0\),即错误分类
w <- w + \(\eta y_i x_i\)
b <- b + \(\eta y_i\)
（4）转至（2），直至T中没有错误分类点。若T是线性可分的，则上述感知机算法收敛，即经过有限次迭代可以得到一个将训练数据集合完全正确划分的超平面。
2）感知机算法对偶形式：将w和b表示为实例\(x_i\)和标记\(y_i\)的线性组合形式，通过求解其系数得到w和b。
输入：线性可分的训练数据集\(T=\lbrace(x_1,y_1),…,(x_N,y_N)\rbrace\),其中\(x_i \in R^n\)，\(y_i \in \lbrace-1,+1\rbrace\)，学习率为\(\eta\)
输出：\(\alpha\)，b，感知机模型机\(f(x)=sign({\sum}_j^N {\alpha}_j y_i x_j · x + b)\)。其中\(\alpha = ({\alpha}_1,{\alpha}_2,…,{\alpha}_N)^T\)
（1）\(w_0\)<-0,\(b_0\)<-0
（2）在训练数据集T中选取数据\((x_i,y_i)\)
（3）若\(y_i({\sum}_j^N {\alpha}_j y_i x_j · x + b)<=0\),即错误分类
\({\alpha}_i <- {\alpha}_i + \eta\)
b <- b + \(\eta y_i\)
（4）转至（2），直至T中没有错误分类点。
三、KNN
1、KNN算法
输入为实例的特征向量，对应于特征空间中的点；输出为实例中的类别，可以取多类。KNN实际上利用训练数据集对特征向量空间进行划分，并作为其分类模型。
K值选择、距离度量和分类决策规则是KNN三个基本要素。KNN算法简单、直观：给定一个训练数据集T，对于新的输入实例，在T中找到与该实例最邻近的k个实例，这k个实例的多数属于某个点就把输入实例分为该类。
2、KNN模型
KNN模型实际上对应于特征空间的划分。模型由三个基本要素——距离度量、k值以及分类决策规定。
3、KNN的实现：kd树
实现KNN算法时，主要考虑的是如何对T进行快速k近邻的搜索，为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储T，以减少计算距离的次数。
四、朴素贝叶斯
朴素贝叶斯算法是基于朴素贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集T，首先基于特征条件独立的假设学习输入、输出的联合概率分布，然后基于此模型，对于新给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。
1、朴素贝叶斯的学习与分类
- 输入空间：\(R^n\)
输出空间：\(y=\lbrace c_1,c_2,…,c_K\rbrace\)
X和Y是定义在输入空间和输出空间上的随机向量\变量。P(X,Y)是X和Y的联合概率分布。现在假设训练数据集\(T=\lbrace(x_1,y_1),…,(x_N,y_N)\rbrace\)由P(X,Y)独立同分布产生。朴素贝叶斯算法则通过训练数据集学习联合概率分布P(X,Y)。
具体地，学习以下先验概率分布以及条件概率分布
$$P(Y=c_K),k=1,2,…,K$$
$$P(X=x|Y=c_K)=P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},…,X^{(n)}=x^{(n)}|Y=c_K)$$
由条件独立地假设，可得$$P(X=x|Y=c_K) = {\prod}^n P(X^{(j)}=x^{(j)}|Y=c_K)$$
朴素贝叶斯实际上学习到的是生成数据地机制，所以属于生成模型。在进行分类时，对于给定的x，通过学习到的模型计算后验概率分布\(P(Y=c_K|X=x)\)$$P(Y=c_K|X=x) = {P(X=x|Y=c_K)P(Y=c_K) \over {\sum}_kP(X=x|Y=c_K)P(Y=c_K)}$$
上式中，分子即为P(X,Y)。故朴素贝叶斯的分类结果即为后验概率最大的对应的那一类。2、朴素贝叶斯的参数估计
1)极大似然估计
在朴素贝叶斯算法中，学习意味着估计\(P(Y=c_K)\)和\(P(X^{(j)}=x^{(j)}|Y=c_K)\),可以用MLE算法估计相应的概率。
$$P(Y=c_K) = {\sum_i^NI(y_i=c_K) \over N},k=1,2,..,K$$
设第j个特征\(x^{(j)}\)可能取值的集合为\(a_1,a_2,…\)
条件概率\(P(X^{(j)}=a_{l}|Y=c_K)\)的MLE是：
$$P(X^{(j)}=a_{l}|Y=c_K) = {\sum_i^NI(x_i^j=a_l,y_i=c_K) \over \sum_i^NI(y_i=c_K)}$$
$$j=1,2,…,n l=1,2,…,S_j, k=1,2,..,K$$2)贝叶斯估计
用MLE可能会出现所要估计的概率值为0的情况，解决这一问题的方法是采用贝叶斯估计，具体的，条件概率的贝叶斯估计是：
$$P(X^{(j)}=a_{l}|Y=c_K) = {\sum_i^NI(x_i^j=a_l,y_i=c_K)+\lambda \over \sum_i^NI(y_i=c_K)+S_j\lambda}$$
$$j=1,2,…,n l=1,2,…,S_j, k=1,2,..,K$$
先验概率的贝叶斯估计是：
$$P_\lambda(Y=c_K) = {\sum_i^NI(y_i=c_K)+\lambda \over N+K\lambda},k=1,2,..,K$$
五、决策树
决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。
1、决策树模型与学习
定义：决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或者属性，叶结点表示一个类。
用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶结点。
决策树还表示给定特征条件下类的概率分布。这一条件概率分布定义在特征空间的一个划分。将特征空间划分为互不相交的单元，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径就对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。
在决策树学习时，假设给定训练数据集\(D=\lbrace(x_1,y_1),…,(x_N,y_N)\rbrace\),其中，\(x_i=(x_i^{(1)},x_i^{2)},…,x_i^{(n)})^T\)为输入实例（特征向量），n为特征个数，\(y_i \in \lbrace1,2,…,K\rbrace\)为类标记，i=1,2,…,N,N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使得它能对实例进行正确的分类。从另一个角度看，决策树学习是由训练数据集估计条件概率模型（详见李航书73页）。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型不仅对训练数据有很好的拟合，且对未知数据也要有很好的预测。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类地过程。
决策树算法包括特征选择，决策树生成以及剪枝过程。由于决策树表示为一个条件概率分布，所以深浅不同地决策树对应着不同复杂度地概率模型。
2、特征选择
特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。
随机变量X的熵定义为：
$$H(X)=-\sum_i^np_ilog(p_i)$$
随机变量X给定条件下随机变量Y的条件熵H(Y|X)，定义为给定条件X下Y的条件概率分布的熵对X的数学期望：$$H(Y|X)=\sum_i^np_iH(Y|X=x_i)$$
$$p_i = P(X=x_i)$$信息增益：特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵\(H(D|A)\)之差，即g(D,A) = H(D)-H(D|A)。
决策树学习应用信息增益准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验熵H(D|A)表示在给定特征A的条件下对数据集D进行分类的不确定性。它们的差即信息增益，就表示由于特征A而使得数据集D的分类的不确定性减少的程度。根据信息增益的选择特征的方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益大的特征。
3、决策树的生成
1）ID3算法：
在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上算法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止。
2）C4.5算法：
和ID3类似，只是在生成过程中，用信息增益比来选择特征。
4、决策树的剪枝
在决策树学习中将以生成的树进行简化的过程称为剪枝。具体的、剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父节点作为新的叶结点。设树T的叶结点个数为|T|，其中k类的样本点由\(N_{tk}，k=1,2,…,K\)个,\(H_t(T)\)为t上的经验熵，\(\alpha >= 0\)为参数，则决策树学习的损失函数可以定义为：
$$C\alpha(T)=\sum_t^{|T|}N_tH_t(T)+\alpha|T|$$
其中经验熵为
在损失函数中，将有段第一项记作C(T)，表示模型对训练数据的预测误差，而|T|表示模型复杂度。算是函数正好表示了C(T)与|T|的平衡。剪枝算法
输入：生成算法产生的整个树T，参数\(\alpha\)
输出：修剪后的子树\(T_\alpha\)
（1）计算每个结点的经验熵
（2）递归地从树的叶结点向上回缩，设一组叶结点回缩到其父结点之前与之后的整体树分别为\(T_B,T_A\),其对应的损失函数分别为
若
则进行剪枝。（3）返回（2），直到不能继续为止，得到损失函数最小的子树。
5、CART算法（分类与回归树）
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部节点特征的取值是“是”或“否”，左分支是取值为“是”的分支、右分支是取值为“否”的分支。
六、Logistic回归和最大熵模型(MEM)
1、Logistic回归
1）LR模型
$$P(Y=1|X)={exp(w·x+b) \over {1+exp(w·x+b)}}$$
$$P(Y=0|X)={1 \over {1+exp(w·x+b)}}$$一个事件的几率指该事件发生的概率与该事件不发生的概率的比值。若某事件发生的概率为p，则该事件的几率是\(p \over {1-p}\)，其对数几率是\(logit(p) = log({p \over {1-p}})\)。对于逻辑回归而言，输出Y=1的对数几率是输入x的线性函数。或者说，输出Y=1的对数几率是由输入X的线性函数表示的模型。即Logistic Regression模型。
LR模型学习时，对于给定的训练数据集\(T={(x_1,y_1),(x_2,y_2),…}\)，其中\(x_i \in R^n,y_i \in {1,-1}\),可以用极大似然估计模型参数，从而得到LR模型。
2）多项LR：
假设离散型随机变量Y的取值集合是{1,2,…,K}，那么多项Logistic回归的模型是：
$$P(Y=k|X)={exp(w_k·x+b) \over {1+\sum_kexp(w_k·x+b)}}$$
$$P(Y=K|X)={1 \over {1+\sum_kexp(w_k·x+b)}}$$
这里\(x \in R^{n+1},w_k \in R^{n+1}\)2、最大熵模型
1）最大熵模型的原理：学习概率模型时，在所有可能的概率模型分布中，选择熵最大的模型作为最好的模型。通常用约束条件来确定概率模型的集合。所以，最大熵原理也可以表述为在满足约束条件的模型集合中选择熵最大的模型。
2）最大熵模型定义：假设分类模型是一个条件概率分布\(P(Y|X)，X \in R^n,Y \in R\)。现在给定一个训练集\(T=\lbrace(x_1,y_1),…,(x_N,y_N)\rbrace\),学习的目标是用最大熵原理来选择最好的分类模型。首先考虑模型应该满足的条件。可以根据数据集T来确定P(X,Y)的经验分布和P(X)的经验分布。
$$P^\sim(X=x,Y=y)={V(X=x,Y=y) \over N}$$
$$P^\sim(X=x)={V(X=x) \over N}$$
用特征函数f(x,y)描述输入x和输入y之间的某一个事实，其定义是：如果x和y满足某个事实，则f(x,y)为1，否则为0.
f(x,y)关于经验分布\(P^\sim(X,Y)\)的期望值，用\(Ep^\sim(f)=\sum_{x,y}P^\sim(x,y)f(x,y)\)表示。f(x,y)关于模型P(Y|X)与经验分布\(P^\sim(X)\)的期望值，用\(Ep(f)=\sum_{x,y}P^\sim(x)P(y|x)f(x,y)\)表示。
如果模型可以获取数据集中的信息，则这两个期望相等，即\(Ep(f)=Ep^\sim(f)\)。此即为约束条件。假设由n个特征函数\(f_i(x,y),i=1,2,…,n\)，既有n个约束条件。
定义：假设满足所有约束条件的模型集合为
$$C=\lbrace p \in P|Ep(f_i)=Ep^\sim(f_i),i=1,2,…,n\rbrace$$
定义在条件概率分布P(Y|X)上的条件熵为：$$H(P)=-\sum_{x,y}P^\sim(x)P(y|x)logP(y|x)$$
则模型集合C中条件熵H(P)最大的模型成为最大熵模型。3、最大熵模型学习
最大熵模型学习等价于约束最优化问题。
$$s.t \ \ \ \ \ \ Ep(f_i)=Ep^\sim(f_i),i=1,2,…,n\ \ \ \ \sum_yP(y|x)=1$$
使用Lagrange数乘法，求得$$P_w(y|x) = {1 \over Z_w(x)}exp(\sum_i^nw_if_i(x,y))\ \ \ \ \ \ Z_w(x)=\sum_yexp(\sum_i^nw_if_i(x,y))$$
这里的\(w_i\)就是特征的权值，即为最大熵模型中的参数。
其中，\(L(P,w)=-H(P)+w_0(1-\sum_yP(y|x))+\sum_i^nw_i(Ep^\sim(f_i)-Ep(f_i))\)4、极大似然估计
极大似然估计就是说最大熵模型学习中的对偶函数最大化等价于最大熵模型的极大似然估计（其实就是说w*的求解过程可以用最大化L(w)来完成）。
最大熵模型与逻辑回归模型具有类似的形式，它们又称为对数线性模型。模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计。
5、模型学习的最优化算法
LR、MEM学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。常用的方法有迭代尺度法、梯度下降法、牛顿法或拟牛顿法。
