博客若干事
博客更新
根据目前的学习进度、自己的空闲时间以及时间的充裕度，现将博客的更新时间定于周三，更新周期为每一周或者两周更新一次。另由于目前自己对于Latex公式还不是特别熟，所以博文中的公式可能会出现部分错误，请大家谅解。此外，博客刚刚创建，很多东西都在完善当中，包括博客的插件，博文的排版等等，这些方面之后会慢慢完善，目前已开放的功能仅基本支持博文的显示以及评论。
由于机器学习领域问题一般涉及公式较多，目前采取的渲染方式是通过相应的JS插件，导致的直接后果是页面的载入速度较慢，这方面以后可能将公式转换为图片然后输出。
好吧，博客方面要说的就这么多吧。
机器学习浅谈
机器学习要研究的问题无非有四:
- 为什么要学习?
- 学习什么？
- 怎么学习？
- 怎么更好地学习？
也许所有的理论，所有的事无非要解决的就是这四件事吧，为什么、做什么、怎么做、怎么做好。(作者注)
大概所有的思想、理论、模型大致是围绕这四个方向进行的，而且这四个问题都得到了较好的解决。以上这些理论比较繁杂，而且我也没完全弄懂，所以咱们慢慢啃吧。
今天我们要谈的是主要是生成模型，与之对应的则是判别模型。生成模型和判别模型的区别在于：
- 生成模型首先计算联合概率分布$p(x,y)$,然后据此计算$p(y|x)$;而判别模型往往直接计算$p(y|x)$;
- 生成模型关注数据是怎么生成的，然后进行预测；判别模型不关注数据的具体生成过程，直接预测。
本文主要介绍针对离散数据的生成模型，限于篇幅，本文仅对其中其中的两个模型进行介绍------Dirichlet-Multinomial Model以及朴素贝叶斯分类器，Dirichlet-Multinomial Model被广泛使用在各种语言模型中，而朴素贝叶斯分类器最为人所知的应用大概就是垃圾邮件过滤(Spam Filtering)了吧。
以下我们正式开始介绍这两个模型。
Dirichlet-multinomial Model
我们现在要Model的问题很简单，假设现有一个$K$面的骰子，我们需要推断它出现第$k$面的概率。
Likelihood
假设我们掷骰子$N$次，$D={x_1,...,x_N}$,其中，$x_i\in {1,...,K}$.我们假设数据是独立同分布的(iid),Likelihood则有如下形式： \begin{equation} p(D|\theta) = \prod_{k=1}^{K}\theta_k^{N_k} \end{equation} 其中，$N_k = \sum_{i=1}^{N}1_{y_i=k}$是第$k$面出现的次数。(1为指示函数，下同)
先验分布
Machine Learning:A probabilistic perspective一书告诉我们如果先验分布和Likelihood的形式相同(共轭先验分布，conjugate prior)时，能够很好的简化我们的计算过程。基于此理，我们选择Dirichlet分布作为我们的先验分布，Dirichlet分布具有如下形式:
\begin{equation}
Dir(\theta|\alpha) = \frac{1}{B(\alpha)}\prod_{k=1}^{K} \theta_k^{\alpha_k-1}1_{x \in S_k}
\end{equation}
后验分布
将Likelihood乘以Prior，后验分布的形式告诉我们后验分布也服从Dirichlet Distribution: \begin{equation} p(\theta|D) \propto p(D|\theta)p(\theta) \ \propto \prod_{k=1}^{K} \theta_k^{N_k}\theta_{k}^{\alpha_k-1}=\prod_{k=1}^{K}\theta_k^{\alpha_k+N_k-1} \ =Dir(\theta|\alpha_1+N_1,...,\alpha_K+N_K) \end{equation} 现在我们计算关于参数$\theta$的极大后验估计(MAP),其中,$\sum_{k}\theta_k=1$. 引入Lagrange乘子之后我们需要优化的目标函数为: \begin{equation} l(\theta,\lambda) = \sum_{k} N_klog\theta_k+\sum_{k}(\alpha_k-1)log\theta_k+\lambda(1-\sum_{k}\theta_k) \end{equation} 为简便起见，记$N\prime_k\triangleq N_k+\alpha_k-1$.对$\lambda$求导得： \begin{equation} \frac{\partial l}{\partial \lambda}=(1-\sum_{k}\theta_k) = 0 \end{equation} 对$\theta_k$求导得， \begin{equation} \frac{\partial l}{\partial \theta_k}=\frac{N\prime_k}{\theta_k}-\lambda=0 \ N\prime_k = \lambda\theta_k \end{equation} 由上两式得： \begin{equation} \sum_{k} N\prime_k = \lambda\sum_{k}\theta_k \ N+\alpha_0-K=\lambda \end{equation} 其中，$\alpha_0\triangleq \sum_{k=1}^{K}\alpha_k$是先验的有效样本大小。因此我们可以得出极大后验估计值为： \begin{equation} \hat{\theta}_k=\frac{N_k+\alpha_k-1}{N+\alpha_0-K} \end{equation} 如果采用uniform prior $\alpha_k=1$，这时得到的最大后验估计值即与经验值相同。 \begin{equation} \hat{\theta_k} = \frac{N_k}{N} \end{equation}
Posterior predicative
\begin{equation} p(X=j|D) = \int P(X=j|\theta)p(\theta|D)d\theta \ =\int P(X=j|\theta_j)[\int p(\theta_{-j},\theta_j|D)d\theta{-j}]d\theta_j \ =\int \theta_jp(\theta_j|D)d\theta_j=E[\theta_j|D] = \frac{\alpha_j+N_j}{\sum_{k}\alpha_k+N_k}=\frac{\alpha_j+N_j}{\alpha_0+N} \end{equation} 其中，$\theta_{-j}$代表$\theta$中除$\theta_j$之外的所有分量。
Example
上述模型的一个很重要的应用场景是语言模型，即预测一个序列中下一个可能出现的词。以下我们举一个非常简单的例子，我们假定每一个词$X_i \in {1,...,K}$都是通过$Cat(\theta)$独立取样得到的，该模型被称为bag of words model.给定一已知的样本序列，我们需要预测下一个最可能出现的是什么词?
如，假设我们取样得到如下样本:
Mary had a little lamb,little lamb,little lamb,
Mary had a little lamb, its fleece as white as snow
另外，我们假设我们的字典中有如下词:
这里unk代表unknown，表示未在样本中出现过的所有词。为了给上述样本中的每一行进行编码，我们先从采样样本中去掉标点符号以及停用词(即没有实际意义的词，一般只是各种助词等),如，a,as,the等。此外我们还需要对所有的词进行处理仅得到其词根，如saw处理为see，running处理为run等。最后，我们对每一行进行索引编号,得到如下结果:
这里我们不考虑词序，仅考虑每个词在样本中出现的次数。统计得到如下结果:
将以上每个计数值记为$N_j$,如果对于$\theta$我们采用Dirichlet先验分布，则有:
\begin{equation} P(\bar{X}_j|D)=E[\theta_j|D]=\frac{\alpha_j+N_j}{\sum_t \alpha_t+N_t}=\frac{1+N_j}{10+17} \end{equation}
通过代入每一个计数值，我们便能得出每个词出现的概率。至此，我们得到了该语言模型的所有参数，进而可以进行各种预测。
Naive Bayes Classifier
引子
朴素贝叶斯分类是一种十分简单的分类算法，它的思想很naive,但是其实际应用效果还是不错的。所以一个模型的好坏并非在于其复杂度，而在于我们是否将它用到了正确的地方，就算一个非常Naive的模型，如果用在了恰当的地方，也能产生很好的效果。具体就机器学习算法而言，只有真正对一个算法的特性、适用条件、优缺点有非常深刻的理解，才能真正把机器学习算法或模型用好。朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。
引用CodingLabs提到的一个例子来抛出我们的问题，并以此为基础介绍我们的模型:
对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。
如果通过纯人工检测，需要耗费大量的人力，效率也十分低下，如能引入自动检测机制，必将大大提升工作效率。这个问题说白了，就是要将社区中所有账号在真实账号和不真实账号两个类别上进行分类。
首先设C=0表示真实账号，C=1表示不真实账号。
假设我们目前确定能作为评判用户帐号是否真实的特征属性有如下几个:(实际上在机器学习领域确定特征属性是一项特别重要且复杂的工作，我们这里为了简化，直接给出本问题的特征属性)
F1：日志数量/注册天数；F2：好友数量/注册天数；F3：是否使用真实头像。在SNS社区中这三项都是可以直接从数据库里得到或计算出来的。(对这些属性进行区间划分保证这些属性取离散值)
接下来的工作是我们从数据库得到了一些新的记录，给出了如上三个特征，我们需要预测这些用户是否真实的用户。
Introduction to Naive Bayes Classifier
Naive Bayes Classifier要解决的问题是对于具有D个特征属性，每个属性可以取${1,...,K}$中任意一个值的样本进行分类，即$x \in {1,...,K}^D$。朴素贝叶斯分类器是一个生成模型，我们需要计算关于类别的条件概率$p(x|y=c)$.朴素贝叶斯假定给定类别c的条件下，各特征属性之间是相互独立的。于是我们有: \begin{equation} p(x|y=c,\theta) = \prod_{j=1}^{D} p(x_j|y=c,\theta{jc}) \end{equation} 我们得到的模型即为Naive Bayes Classifier(NBC).在上面的SNS真实用户检测的例子中，C=2,D=3。
Naive Bayes Classifier的基本算法流程如下所示:
Algorithm 2.2 Naive Bayes Classifier算法框架
1. 根据得到的样本数据计算在每一可能的类别下各属性取值的条件概率，即计算p(x|y=c);
2. 根据计算得到的条件概率计算新样本属于各个类别的概率，即计算p(y|x*);
3. 比较计算得到的新样本属于不同类别的概率值，选择值最大的那个类别作为新样本的类别。
这里不给出针对具体数据的计算过程，想了解具体每一步怎么算的亲们请参考算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)。
Mutual Information
NBC需要计算关于很多特征的联合概率分布，可能会导致过拟合；此外，算法的运行时间是$O(CD)$,对于有些应用来说可能计算量太大了。一个解决上述问题的普遍被采用的方案是进行特征选取，去掉和分类无关的无用属性。最简单的方法是考察每个特征与分类属性之间的相关性，并权衡复杂性以及准确度选取K个最相关的属性用于训练。该方法被称为variable ranking,filtering,or screening
衡量相关性的一种方式是通过互信息，如下: \begin{equation} I(X,Y)=\sum_{x_j}\sum_{Y}P(x_j,y)log\frac{p(x_j,Y)}{p(x_j)p(y)} \end{equation} 互信息可被理解为当我们观察到特征$x_j$时对于分类属性造成的熵减。对每个特征属性分别计算互信息后，选取较大的若干个用于训练即可。
Appendix I:Mutual Information
KL divergence
衡量两个概率分布$p$和$q$差异性的一种方法是KL距离(Kullback-Leibler divergence or relative entropy).定义如下: \begin{equation} KL(p||q)\triangleq \sum_{k=1}^{K} p_klog\frac{p_k}{q_k} \end{equation} 上式可以改写为: \begin{equation} KL(p||q) \triangleq \sum_{k}p_klogp_k-\sum_{k}p_klogq_k = -H(p)+H(p,q) \end{equation} 其中，$H(p,q)$称为联合熵，定义为: \begin{equation} H(p,q)\triangleq -\sum_{k}p_klogq_k \end{equation} 其实，联合熵可被理解为用分布$q$编码来自分布$p$的数据时所需要的最小位数，$H(p)$即是用本身分布编码本身信息所需要的最小比特位数，因此KL距离的含义即是使用$q$编码来自$p$的信息相对于分布$p$本身而言多需要的位数。
Theorem 2.1 $KL(p,q) \ge 0$,且当且仅当$p=q$时等号成立；
为证明上式，我们引入琴生不等式，即任意凸函数$f$,有: \begin{equation} f(\sum_{i=1}^{n}\lambda_ix_i) \le \sum_{i=1}^{n}\lambda_if(x_i) \end{equation} 其中$\lambda_i\ge 0,\sum_{i=1}^{n}\lambda_i=1$
Proof: \begin{equation} -KL(p||q)=-\sum_{x \in A}p(x)log\frac{p(x)}{q(x)}=-\sum_{x \in A}p(x)log\frac{q(x)}{p(x)} \ \le log \sum_{x \in A}p(x)log\frac{q(x)}{p(x)}=log \sum_{x \in A} q(x) \ \le log \sum_{x \in X}q(x)=log 1=0 \end{equation}
另外一个重要的推论是离散分布中一致分布的熵最大，即$H(X) \le log |X|$.
\begin{equation} 0 \le KL(q||u) = \sum_{x} p(x)log \frac{p(x)}{u(x)} \ = \sum_{x}p(x)logp(x)-\sum_{x}p(x)logu(x) = -H(X)+log|X| \end{equation} 该式是Laplace不充分理由原则的公式表示，它的含义是当没有其他理由证明其他分布好于一致分布时，应当采用一致分布。
Mutual Information
考察两个随机变量，$X$和$Y$。假如我们想知道一个变量包含关于另一变量的多少信息，我们可以计算相关系数，但那只针对实数随机变量而言。一个更通用的办法是衡量联合分布和分布乘积的相关性，即MI.定义如下： \begin{equation} I(X;Y) \triangleq KL((p(X,Y)||p(X)p(Y)) = \sum_{x}\sum_{y}p(x,y)log\frac{p(x,y)}{p(x)p(y)} \end{equation} $I(X;Y) \ge 0 $成立且当且仅当$p(X,Y=P(X)P(Y)$时取等。
\begin{equation} I(X;Y) = H(X)-H(X|Y) = H(Y)-H(Y|X) \end{equation} 其中，减式的后半部分称为条件熵，证明此处从略。