ngram是一种在自然语言处理中经常使用的技术，通常来说，我会把它作为一些初步处理和数据分析的方法，也会用来做一些快速模型，其具有可解释性强，实现简单等优点。
原先的理解比较土鳖，最近刚好重新读《统计自然语言处理基础》和《统计自然语言处理》，补充下这块的知识。

背景及主要问题

香农游戏和语言模型问题

香农游戏，即在给定前N个词的情况下，需要尽可能准确预测下一个词。这是语言模型一个比较形象的描述，通常我们所指的语言模型，说白了就是计算某语言片段在上下文的概率。可以认为分别针对两类典型的实际问题：
* 给定前文，给出下一个词的概率分布，也即需要计算
$P(w_n|w_0, ..., w_n-1)$
* 给定一篇完整的文章，计算其在某语言生成模型下的似然概率，也即需要计算
$P(w_0, ..., w_n)$

ngram方法

对于上述问题，ngram是一种经典的解决方法，其通过估计$P(w_i|w_{i-1}, ..., w_{i-n})$来作为概率分布。
显然，由于组合爆炸问题，n的范围不能太大，一般来说实际使用中n介于2-3。

而对于ngram模型，最大的问题在于数据稀疏导致的分布估计不准。可以想见，在测试集上统计的大量长尾频率为0和1的ngram组合，往往是随机不精确的。这部分如何处理，通常认为是平滑问题（如何使得分布更加平滑）。

评测方式

对于语言模型（或者ngram模型）的评测方法，可以使用测试集上的似然估计来衡量。通俗来说，就是当一个机器阅读完训练语料后应该能比较高效地把测试语料压缩。

一种办法就是使用信息熵。信息熵本身是衡量压缩一个事件需要的bit位个数。可以通过计算测试集文本的信息熵，来估算一个模型的好坏（Entropy越小，说明压缩效率越高）

$$... </div> <a href="/ngram/" class="read-more">Read More</a> </article> <article class="post"> <h1><a href="/gbdt/">GBDT笔记</a></h1> <div class="entry"> <p>@(机器学习、NLP和IR)[GBDT]</p> <h2 id="section">基础原理</h2> <h3 id="dt">DT</h3> <h3 id="gb">GB</h3> <p>首先Gradient Boosting是一种boosting方法，它通过汇聚多个弱分类器的能力，来提升学习的效果。<br /> 其基本思路是：</p> <ul> <li>基础思想：所谓梯度下降，对残差持续学习，每次用<script type="math/tex">H$$ 去拟合$y-F_{m-1}(x)$，然后更新$F_m(x)=F_{m-1}(x)+H$

具体操作：既然我们拟合的目标是$y-F_{m-1}(x)$而拟合本身也需要选择一个评估函数，标准方法使用MSE来作为拟合目标，也即：

对于第$m$次学习，我们以MSE作为H的目标函数进行拟合：$argmin\frac{1}{2}(y-F)^2$

同时，$F_m=F_{m-1}+\theta H(x, y, F_{m-1})$

• 其中，H是根据之前学习的结果进行学习的树，学习的目标就是MSE。
• $theta$是一维搜索获取的值。

类比泰勒展开式的思路，泰勒展开式相当于用多项式作为弱分类器，来学习任意一个函数在某点附近的情况。

toy实现

根据上述简介，我们非常容易实现一个伪代码

for round...