Discount.cc Discount.h
文档作者：rickjin
创立时间：08.09.27
--------------
1、基本类
--------------
Discount.h Discount.cc 这两个文件主要实现了最重要的几个平滑算法, 包括
a. Katz smoothing (基于 Good-Turing smoothing)
b. Absolute Discounting
c. Natural law of succession [Eric Sven Ristad, 1995]
d. Additive smoothing [Lidstone-Johnson-Jeffrey]
e Witten-Bell smoothing
f. Kneser-Ney smoothing
g. Modified Kneser-Ney mooothing, [Chen, Goodman, 1998]
----------------
2、类接口说明
----------------
2.1) Discount 类主要接口
class Discount
{
public:
/* 使用平滑算法， 返回频率 count 平滑之后的结果
* @param count 当前 ngram 频率
* @param totalCount 总频率
* @param oberservedVocab 语料中统计到的中所有 ngram 的 type 数目
* */
virtual double discount(Count count, Count totalCount, Count observedVocab);
virtual double discount(FloatCount count, FloatCount totalCount,
Count observedVocab);
/* 在回退模型中， 低阶模型的权值大小
*
* @param min2Vocab 频率>=2 的ngram type 数目
* @param min3Vocab 频率>=3 的ngram type 数目
* */
virtual double lowerOrderWeight(Count totalCount, Count observedVocab,
Count min2Vocab, Count min3Vocab);
virtual double lowerOrderWeight(FloatCount totalCount, Count observedVocab,
Count min2Vocab, Count min3Vocab);
/* 是否支持该平滑操作 */
virtual Boolean nodiscount();
/* 保存平滑参数 */
virtual void write(File &file);
/* 读入平滑参数 */
virtual Boolean read(File &file);
/* 进行平滑操作， 进行参数估计计算
*
* @param counts ngram 计数器
* @param order 对 order 阶ngram 进行平滑计算
* */
virtual Boolean estimate(NgramStats &counts, unsigned order);
virtual Boolean estimate(NgramCounts &counts, unsigned order);
/* 在平滑之前， 对 ngram 的频率进行调整，在 KneserNey 平滑算法中使用 */
virtual void prepareCounts(NgramCounts &counts,
unsigned order, unsigned maxOrder);
virtual void prepareCounts(NgramCounts &counts,
unsigned order, unsigned maxOrder);
/* 是否支持插值 */
Boolean interpolate;
protected:
/* Vocab 中有效条目的 ngram 数目 */
static unsigned vocabSize(Vocab &vocab);
};
2.2) GoodTuring 类主要接口
class GoodTuring: public Discount
{
public:
/* 构造函数 */
GoodTuring(unsigned mincount = GT_defaultMinCount,
unsigned maxcount = GT_defaultMaxCount);
protected:
/* 小于该值的频率将被设置为 0 */
Count minCount;
/* 大于该值的频率将不平滑， 保持不变 */
Count maxCount;
/* 平滑系数 */
Array discountCoeffs;
};
说明：
a. 该函数实现标准的基于图灵平滑的 Katz 平滑算法
b. 图灵平滑算法为 r* = (r + 1) * n_(r+1) / n_r, Katz 平滑算法如下
|-- d_r * r (0 < r < k)
r_katz = |-- r (r > k)
|-- alpha (r = 0)
d_r = (r*/r - commonTerm ) / (1 - commonTerm)
commonTerm = (k+1) * n_(k+1) / n_1
在此处 k 默认值为 GT_defaultMaxCount = 5;
2.3) ConstDisCount 类主要接口
class ConstDiscount: public Discount
{
public:
double lowerOrderWeight(Count totalCount, Count observedVocab,
Count min2Vocab, Count min3Vocab)
{ return _discount * observedVocab / totalCount; }
protected:
/* 打折的常数项 */
double _discount;
/* 低于此值的频率被设置为 0 */
double _mincount;
};
说明：
a. 此平滑算法即为 Absolute Discounting
b. 算法思想就是对每个频率count, 打折频率为一个常数 _discount,
所以变为 (count - _discount), 则平滑系数为 (count-_discount) / count
2.4) NaturalDiscount 类主要接口
class NaturalDiscount: public Discount
{
public:
...
protected:
/* ngram 的条目数 */
unsigned _vocabSize; /* vocabulary size */
/* 低于此值的频率被设置为 0 */
double _mincount; /* minimum count to retain */
};
说明：
a. 此平滑算法为 Natural law of succession [Eric Sven Ristad, 1995]
b. 算法思想就是对每个频率count, 使用如下固定的平滑系数
d = ( n(n+1) + q(1-q) ) / ( n^2 + n + 2q )
其中 n 为 totalCount(总频率), q 为 observedVocab(ngram type 数)
2.5) AddSmooth 类主要接口
class AddSmooth: public Discount
{
public:
AddSmooth(double delta = 1.0, unsigned mincount = 0)
: _delta(delta < 0.0 ? 0.0 : delta),
_mincount(mincount) {};
protected:
double _delta; /* the additive constant */
/* 低于此值的频率被设置为 0 */
double _mincount; /* minimum count to retain */
/* ngram 的条目数 */
unsigned _vocabSize; /* vocabulary size */
};
说明：
a. 此平滑算法为 Additive smoothing, 可以视为 Laplace add 1 smoothing 的扩展
b. 算法思想就是对每个频率c, 使用如下方法计算概率
p = (c + delta) / (T + N * delta)
其中 T 为 totalCount(总频率), N 为 observedVocab(ngram type 数)
由此， 平滑系数为
d = (1 + delta/c) / (1 + N * delta / T)
c. 该平滑算法可以看作是最大似然估计ML 和 均匀分布之间的插值
p = lambda * p_ML + （1 － lambda) * 1/N
-------------------
3、主要函数功能说明
-------------------
待续...
