本系列为在温习《统计学习方法》过程中的思考总结
生成模型与判别模型
学习一个模型就是对给定的输入预测相应的输出，也就是写出一个决策函数（对应回归问题）：$Y = f(X)$ 或条件概率（对应分类问题）： $P(Y|X)$
生成方法
生成方法出发点是学习联合概率分布函数$P(X, Y)$, 然后求出条件概率分布 $P(Y|X)$。
$$
\begin{align}
P(Y|X) = \frac{P(X, Y)}{P(X)}
\end{align}
$$
而联合分布函数$P(X, Y)$和$P(X)$由概率最大似然估计从观测数据中求得。典型的生成模型有 朴素贝叶斯法 和 隐含马尔科夫型 。
判别方法
判别方法是由数据直接学习决策函数$f(X)$或条件概率分布$P(Y|X)$。
基本思路是设定一个含有模型参数的决策模型，然后通过最大似然拟合观测数据来选出最优化模型参数，从而得到最终的决策模型。
典型的判别模型有 k-means，感知机，决策树，logistic regression，最大熵模型，支持向量机，提升方法和条件随机场。
对比
生成方法的学习收敛速度快，当样本容量增加的时候，学到的模型可以更快的收敛于真是模型。当存在隐变量的时候，仍然可以使用生成方法。
判别方法直接面对预测，往往学习的准确率更高。并且可以对数据进行各种程度上的抽象、定义特征并使用特征，可以简化学习问题。
似然估计与似然函数
最大似然估计原理
给定一个概率分布$D$， 已知其概率分布函数（模型） 为$f_D$, 该概率分布函数包含一个模型参数$\theta$。在这个概率分布中进行采样得到数据集$T = {x_1, x_2, x_3, x_4,… x_n}$。 求解参数$\theta$来确定该分布$f_D$。
我们可以构建似然函数：
$$
\begin{align}
L(\theta|x_1, …, x_n) = f_D(x1, x2, …, x_n|\theta)
\end{align}
$$
注意$L(\theta|x_1, …, x_n)$是$\theta$的函数，而$f_D(x1, x2, …, x_n|\theta)$是$x_1, …, x_n$的函数。$f_D(x1, x2, …, x_n|\theta)$表示在确定$\theta$的情况下，产生数据集$T$的概率。
通过最大化似然函数$L(\theta)$我们可以找到使得数据集$T$出现概率最大的模型。
进行独立分布假设
似然函数可以写成
形式1
$$
\begin{equation}
L(\theta|x_1, …, x_n) = f_D(x1, x2, …, x_n|\theta) = \prod_{i=1}^{n} f_D(x_i|\theta)
\end{equation}
$$
假设随机变量X是离散的，具有取值范围为${v_1, v_2, … v_k}$ 那么上述极大似然函数可以写为
形式2：
$$
\begin{align}
L(\theta|x_1, …, x_n) = \prod_{i=1}^{k} f_D(v_i)^{C(x=v_{i})}
\end{align}
$$
两边对等开n次方可得：
$$
\begin{align}
L(\theta|x_1, …, x_n)^{1/n} = \prod_{i=1}^{k} f_D(v_i)^{C(x=v_{i})/n}
\end{align}
$$
其中$C(x=v_{i})$是随机变量X取得$v_i$的数量，$n$为所有样本总数
此时注意到$\bar{f_D}(x)=C(x=v_{i})/n$，就是从数据中得来的经验概率。
而求$L(\theta|x_1, …, x_n)^{1/n}$的最大值和求$L(\theta|x_1, …, x_n)$是等价的，所以我们就可以把似然函数写成
形式3：
$$ L(\theta|x) = \prod_{i=1}^{n}P(x|\theta)^{\bar{P}(x)} $$
这也就是似然函数的一般形式
$$
\begin{align}
L(\theta|x) = \prod_{i=1}^{n}P(x)^{\bar{P}(x)}
\end{align}
$$
求解模型参数
$$
\begin{align}
\hat{\theta} = \mathop{\arg\max}_{\theta} L(\theta|x)
\end{align}
$$
朴素贝叶斯估计-生成模型
（1）估计$P(x, y) = \bar{P}(x|y) \bar{P}(y)$, 其中$\bar{P}(x|y)$和$\bar{P}(y)$是从数据集中得来的经验概率（条件概率和先验概率）
（2）进行独立分布假设
$\bar{P}(X=x|Y=c_k)=\bar{P}(X=x_1,x_2,…,x_n|Y=c_k) = \prod_{j=1}^{n} P(X = x_j|Y=c_k)$
（3）计算分入某个类的概率(贝叶斯公式)
$$
\begin{align}
P(Y=c_k|X=x) = \frac{P(X=x|Y=c_k) P(Y=c_k)}{\sum_k P(X=x|Y=c_k) P(Y=c_k)}
\end{align}
$$
注意分母是全概率$P(X=x)$与$Y$没有关系。
(4) 选取概率最大的那个类作为估计输出 $\mathop{\arg\max}{c_k} P(c_k | X=x)$
$$
\begin{align}
y = \mathop{\arg\max}{c_k} P(Y=c_k) \prod_j(X=x_j|Y=c_k)
\end{align}
$$
朴素贝叶斯估计是将实例分到后验概率最大的类中，等价于期望风险最小化。
Logistic Regression (二元) - 判别模型
(1) 设定模型为logistic model：
认为一个事件发生的概率为p，那么定义其对数几率(log odds)为$logit(p) = \frac{p}{1-p}$。
模型认为$logit(p) = w\cdot x+b$，也就是一个事件发生的对数几率是其输入的线性模型。
由此推出的：
$$ p(Y=1|X) = \frac{exp(w\cdot x+b)}{1+exp(w\cdot x+b)} = \pi(x)$$
$$ P(Y=0|X) = 1-p(Y=1|X) = \frac{1}{1+exp(w\cdot x+b)} = 1-\pi(x)$$
(2) 参数模型估计，极大似然估计 （采用形式2）
$$L(w) = \mathop{\prod}{i=1}^{N} [\pi(x_i)]^{y_i} [1-\pi(x_i)]^{1-y_i}$$
对数似然函数为
$$ L(w) = \mathop{\sum}{i=1}^{N}[y_i(w \cdot x_i) - log(1+exp(w \cdot x_i))]$$
最大化似然估计求得模型参数
最大熵模型 - 判别模型
最大熵原理
最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。（对比于上式logistic regression认为极大似然概率最大的模型是最好的模型，当然极大似然估计可能会出现overfitting的问题）。
直观的来说，最大熵原理认为要选择的概率模型首先必须满足已有的实时，即在约束条件下，在没有更多信息的情况下，那么不确定的部分都是”等可能的“。这时候熵可以来作为可优化的指标。
模型定义
（1）特征函数$f(x, y)$描述输入x和输出y之间的某一个事实，是一个二值函数，当x，y满足这个事实的时候取值为1，否则取值为0。
（2）特征函数关于经验分布$\bar{P}(x, y)$的期望为
$$ E_{\bar{P}}(f) = \mathop{\sum}_{x,y}\bar{P}(x, y) f(x,y)$$
关于模型$P(Y|X)$和经验分布$\bar{P}(X)$的期望为
$$ E_{P}(f) = \mathop{\sum}_{x,y}\bar{P}(x) P(Y|X) f(x,y)$$
如果模型能够获取训练数据的信息，那么两个期望应该相等。注意，这个模型可能有很多个，凡是能够拟合训练数据的模型都满足这个约束条件。
（3）最大熵模型，假设满足所有约束条件的模型集合为C，那么定义在条件概率分布$P(Y|X)$上的条件熵为
$$H(P) = -\mathop{\sum}_{x,y}\bar{P}(x) P(Y|X) log(P(Y|X))$$
则模型中条件熵$H(P)$最大的模型成为最大熵模型。