记录一下对AdaBoost的理解，参考了李航大大的《统计学习方法》。

Boost通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类器性能。
提升方法是从弱学习算法出发，反复学习，得到一系列弱分类器 (又称为基本分类器)，然后组合这些弱分类器，构成一个强分类器。

大多数的提升方法都是改变训练数据的概率分布 (训练数据的权值分布)。

1. 每一轮训练时如何改变训练数据的权值活概率分布;
2. 如何将弱分类器组合成一个强分类器。

针对问题1,AdaBoost通过提高前一轮弱分类器错误分类样本的权值，来提升此类样本的关注程度;针对问题2,AdaBoost采用加权多数表决的方法，即加大分类误差小的弱分类器的权值，减小分类误差大的弱分类器的权值。

Comment and share

回顾一下GMM以及HMM等模型的求解方法，即著名的Expectation Maximization (EM) 算法。参考李航老师的《统计学习方法》，EM算法是一种迭代算法，用于含有隐含变量的概率模型参数的极大似然估计（MLE），或极大后验概率估计 (MPE).

EM算法

定义$Y$为观测随机变量，$Z$为隐含随机变量，则$Y$和$Z$一起构成完全数据 (complete-data)。假设待估计的概率模型参数为$\theta$，则观测数据的概率分布为$P(Y|\theta)$, 即为其似然函数，对应的对数似然函数为$L(\theta) = \log{P(Y|\theta)}$. 设$Y$和$Z$Z的联合概率分布为$P(Y,Z|\theta)$，那么完全数据的对数似然函数为$\log{P(Y,Z|\theta)}$.

EM算法的目的就是求解参数$\theta$，极大化观测量的对数似然函数$L(\theta)$。因为包含隐含量，所以采用迭代的方法，分为E (期望) 和M (极大化)两步，求解算法如下。

1. 初始化参数$\theta^{(0)}$;

2. E step: 记$\theta^{(i)}$为第$i$次迭代参数$\theta$的估计值，则第$i+1$次迭代，计算如下期望.

   $$\begin{align} Q(\theta,\theta^{(i)}) &= E_{z}[\log{P(Y,Z|\theta)}|Y,\theta^{(i)}] \notag \\ &=\sum_{z}{\log{P(Y,Z|\theta)P(Z|Y,\theta^{(i)})}}, \end{align}$$

   其中$P(Z|Y,\theta^{(i)})$是在给定观测数据$Y$和当前估计的参数$\theta^{(i)}$下隐含变量$Z$的条件概率分布；$Q(\theta,\theta^{(i)})$定义为完全数据的对数似然函数在给定观测数据和当前参数下对隐含数据$Z$的条件概率分布$P(Z|Y,\theta^{(i)})$的期望，即$\log{P(Y|\theta)}$。

3. M step: 求使$Q(\theta, \theta^{(i)})$极大化的参数$\theta$，以确定第$i+1$次迭代的参数的估计值$\theta^{(i+1)}$, 即计算

   $$\begin{align} \theta^{(i+1)} = \mathrm{arg}\max\limits_{\theta}{Q(\theta,\theta^{(i)})} \end{align}$$

4. 重复E和M两步，直到收敛.

李航老师也强调了一点：EM算法与初值的选择有关，选择不同的初值可能得到不同的参数估计值。 我在这个notebook里给了一个样例，即“三硬币模型”。

高斯混合模型的求解

EM算法最经典的应用就是高斯混合模型的参数估计，该模型是语音信号处理的基础模型之一，其定义如下，

其中，$c_k$是系数，$c_k\geq0$, $\sum_{k=1}^{K}{c_k=1}$; $\phi(\mathbf{y}|\mathbf{\theta_k})$是高斯分布，$\mathbf{\theta_k} = (\mathbf{\mu_k},\Sigma_k^2)$,

在GMM模型中有，

• 观测变量：$\mathbf{Y}$，
• 隐含变量：$\gamma_k\in{0,1}, k=1,~2,~,\cdots,~K$，表示$\mathbf{y}$是否来自第$k$个高斯分量
• 模型参数：$\mathbf{\theta} = {c_k, \mathbf{\theta_k}}, k=1,~2,~,\cdots,~K$.

详细的推导见《统计学习方法》，这里给出GMM模型的E和M步骤.
设观测数据$\mathbf{Y} = \{\mathbf{y1},~\mathbf{y2},~\cdots,~\mathbf{y_N}\}$

• E step

  $$\begin{align} \hat{\gamma_{jk}} = \frac{c_k\phi(\mathbf{y_j}|\mathbf{\theta_k})}{\sum_{k=1}^{K}{c_k\phi(\mathbf{y_j}|\mathbf{\theta_k})}} \end{align}$$

  其中$j=1,~2,~\cdots,~,N, k=1,~2,~\cdots,~K$.

• M step

  $$\begin{align} \hat{\mu}_{km} &= \sum_{j=1}^{N}{\hat{\gamma}_{jk}y_{jm}}/{\sum^{N}_{j=1}{\hat{\gamma}_{jk}}} \notag \\ \hat{\sigma}^{2}_{km} &= \sum_{j=1}^{N}{\hat{\gamma}_{jk}(y_{jm}-\mu_{km})^2}/{\sum_{j=1}^{N}{\hat{\gamma}_{jk}}} \notag \\ \hat{c}_{k} &= {\sum_{j=1}^{N}{\hat{\gamma}_{jk}}} / N \end{align}$$

  其中$m=1,~2,~\cdots,~,M, k=1,~2,~\cdots,~K$.

最后，给出一个样例，简单的二维GMM，如下图，notebook见这里.

可以看出，EM的估计效果还是不错的，并且提供初始化参数值的结果 (左下) 比随机初始化 (右下) 的结果要好。

Reference

[1] 李航，统计学系方法，2012 清华大学出版社
[2] Generating random variables from a mixture of Normal distributions

Comment and share

在机器学习中，二分类 (binary classification) 问题是最常出现且最经典的问题。本文首先解释二分类的样本标签问题，包括正例 (Positive)/反例 (Negative) 和真例 (True)/假例 (False) 这两组集合；紧接着介绍几种常用的分类器评估指标，例如精确度 (precision)、准确率 (accuracy)、敏感性 (sensitivity)、特异性 (specificity)等；最后，讨论对ROC曲线及其衍生的AUC指标的理解，并给出样例。

二分类标签

应用于二分类的样本通常用正例 (Positive, P) 和反例 (Negative, N) 进行标注，作为实际标签。而经过分类器估计后的输出，根据其结果的正确与否，划分为真例 (True, T) 和假 (False, F)两个集合。因此，需要注意的是T和F两个集合均包含正例和反例样本。

根据实际标签和预测结果进行两两组合，得到四个子集，分别为真正率 (True positive, TP)、真反例 (True negative, TN)、假正率 (False positive, FP) 和假反例 (False negative, FN)，如下表所示。

通过对这四个子集样本的组合，可以得到一些评估指标，用于评价分类器的表现。这里我想强调一下对FN和FP的理解，其中FN指的是实际为反例，但被分类器判断为正例，而FP指的是实际为正例，但被分类器判断为反例，二者的合集为F。

评估指标

下面讨论常用的二分类器的评估指标 (index or measure)。定义$S$为所有的样本数量，$S_{P}$和$S_{N}$对应实际标注为正例和反例的样本数；$S_{T}$和$S_{F}$表示分类器估计的标签中正确和错误的样本数。相应的，定义$S_{\mathrm{TP}}$、$S_{\mathrm{TN}}$、$S_{\mathrm{FP}}$和$S_{\mathrm{FN}}$为TP、TN、FP、FN样本的数目。因此，定义如下的评估指标

• 准确率 (accuracy)
  准确率为分类器预测结果中判断正确的样本占所有样本的比例，即$\mathrm{acc} = S_{T}/S = (S_{\mathrm{TP}} + S_\mathrm{TN}) / S$.

• 精确度 (precision)
  精确度又称为查准率，衡量分类器预测为正的样本中实际为正例的样本比例，即 $\mathrm{pre} = S_{\mathrm{TP}} / (S_{\mathrm{TP}} + S_{\mathrm{FP}})$.

• 敏感性 (sensitivity)
  敏感性又称为召回率或真正率，衡量实际为正例的样本经过分类器预测后标记正确的样本所占比例，即$\mathrm{sen} = S_{\mathrm{TP}} / (S_{\mathrm{TP}} + S_{\mathrm{FN}})$.

• F1-score
  F1-score是对精确度和敏感性的结合，因为这两者本质上是矛盾的，通常敏感性越高则精确度会较低。F1-score的表达式为, $\mathrm{F1} = (2 \times \mathrm{pre} \times \mathrm{sen}) / (\mathrm{pre} + \mathrm{sen})$.

• 特异性 (specificity)
  特异性是实际标注为反例的样本经过分类器预测正确的样本的比例，即$\mathrm{spe} = S_\mathrm{TN} / (S_\mathrm{FP} + S_\mathrm{TN})$.

• 假正率 (fasle positive rate)
  假正率表示分类器预测为反例的样本中实际为反例的样本的比例，即$\mathrm{fpr} = S_\mathrm{TN} / (S_\mathrm{FN} + S_\mathrm{TN})$.

对于这些评估指标，我的理解见下表，

ROC和AUC

以上的评估指标均要求分类器的输出为确定的标签，而分类器通常输出的是样本被判断为正例的概率，为了得到标签，需要设定概率的门限，即大于该门限的概率对应的样本判断为正例，否则为反例。门限的设定，影响分类器的泛化能力。

因此，人们提出了receiver operating characteristic (ROC) 的概念，最早出现二战时检测敌机的雷达分析技术。在信号处理中，有这样一组指标，即捕获率 (catch rate) 和追踪率 (follow rate)，前者衡量了系统对于目标信号的捕获能力，后者衡量系统在捕获信号后继续追踪的能力。这两个指标，对应到二分类问题中就是敏感性或真正率 (truu positive rate, TPR)和假正率。

通过TPR和FRP即可求解ROC曲线。对分类器输出的样本概率进行排序，设定概率门限thrs，将高于该门限的样本判断为正例，反之判断为反例。而后，与实际的样本标签进行比较，计算对应该门限的TPR和FPR。记录不同门限处的TPR和FRP，则得到了该分类器的ROC曲线。

如下为ROC曲线的求解算法，

1
2
3
4
5
6
7

Step1. input labels and probs estimated by classifier;
Step2. set thresholding step
Step3. for thrs = 1.0 : step : 0.0
		labels_est = zeros(size(labels))
        labels_Est[probs > thrs] = 1
        calculate fpr and tpr w.r.t. thrs
Step4. Draw the ROC curve

针对不同的分类器，若某个分类器的ROC曲线整体在其他分类器的上方，则可认为该分类器最优。但往往存在ROC曲线交叉的情形，此时通过计算ROC曲线下方的面积，即AUC (area under curve)值来进行对比，AUC数值越大，分类器的分类效果越好，泛化能力越强。

给出一个ROC曲线和AUC的求解样例，具体的代码实现见这里.

首先，设样本的标签和二分类器输出的概率为，

1
2

labels = [1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0]
probs = [0.5, 0.6, 0.2, 0.9, 0.5, 0.3, 0.1, 0.7, 0.3, 0.9, 0.5]

设定thrs的步长为0.1，则求解的TPR和FPR分别为，

1
2

tpr = [0.0, 0.4, 0.4, 0.4, 0.6, 0.8, 1.0, 1.0, 1.0, 1.0, 1.0]
fpr = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.33, 0.33, 0.67, 0.83, 1.0]

最后，求解得到auc=0.967. 下图为该样例的ROC曲线，

scikit-learn也提供了求解auc的函数，其用法如下，

1
2
3

from sklearn import metrics
fpr, tpr, thresholds = metrics.roc_curve(labels+1, p, pos_label=2)
auc = metrics.auc(fpr, tpr)

在我的notebook中，分别给出了我的实现和sklearn.metrics.auc的实现，二者结果相同。最后吐个槽，因为haroopad的bug，这篇是我重新写的！！！

References

[1] 周志华，机器学习，2017 清华大学出版社
[2] 机器学习和统计里面的auc怎么理解？
[3] sklearn.metrics.auc

Comment and share