大数据处理平滑算法：Good-Turing估计

大数据处理中，不管数据如何大，由于不能穷举一切，总是有限的。那么在有限的数据规模下，参数平滑算法就十分重要。参数平滑算法是在训练数据不足时，采用某种方式对统计结果和概率估计进行必要的调整和修补，以降低由于数据稀疏现象带来的统计误差。

比如，在自然语言处理（NLP）中，语料库是按照一定原则组织在一起的真实自然语言数据集合，用于研究自然语言的规律，特别是统计语言学模型的训练以及相关系统的评价。由于语料库的规模和它所包含的语言现象有限，从而导致数据稀疏现象的产生，也就是说，在语料库的规模不够大的条件下，大多数词或邻接词及各属性的搭配在语料中出现的次数很少，甚至根本不出现的现象。在实际应用中，数据稀疏的存在会产生大量空值，严重影响后续处理的性能和效果。这时，就需要平滑算法。

假设元素的集合是 X = {x1,...,xm}，这些元素可能是n-grams，简单起见，假设是unigram。比如 X = {the,bad,cat,dog}。我们有一个序列W，包含N个独立的样本：W = w1,wn,?其中wk ∈ X。现在我们需要估计θ[j]，就是将出现的样本是xj的概率。需要满足θ[j] > 0，就算之前没有出现过，将来也可能出现。这就意味着用相对频率 #(xj)/N，其中#(xj ) 是xj在W中出现的次数，来估计小的次数的元素是不理想和正确的。而且碰到一个问题：怎么估计从来没有见到的元素的概率。

Good-Turing估计是许多数据平滑技术的核心。它的基本思想是：将统计参数按出现次数聚类（如果 #(xj ) = #(xj‘),then θ[j] = θ[j’]），出现一次的多少，出现两次的多少，等等，然后用出现次数加一的类来估计当前类。比如，用出现次数为n+1的类来估计出现次数为n的类。