使用 Winnow 进行上下文感知拼写校正
4.88/5 (9投票s)
实现一个复杂的拼写检查器，该检查器利用语言模型来考虑单词出现的上下文。
目录
引言
上下文敏感拼写纠错的任务是修正那些导致有效单词的拼写错误，例如 I’d like to eat desert，其中 desert 本应输入 dessert。
这些错误将无法被传统的拼写检查器检测到，因为它们只标记单词列表中不存在的单词。
上下文敏感的拼写纠错涉及学习描述不同单词（如 dessert 和 desert）倾向于出现的语言上下文。问题在于，可能用来描述这些上下文的特征多种多样：有些特征测试目标词附近是否存在特定单词；有些特征测试目标词周围的词性模式；等等。通常，特征的数量会从几百个到一万多个不等。
现在又出现了另一个问题，我们如何确定实际要考虑哪些特征？如何去芜存菁？
请注意，我不是在谈论特征选择，因为即使在过滤或移除噪声特征后，您仍然会得到一个庞大的特征空间，而目标概念（在此例中是 desert 可能出现的上下文）仅取决于一小部分。
对于这个问题，我们将采用Winnow 算法。
本文遵循 ANDREW R. GOLDING 和 DAN ROTH 的工作，《基于 Winnow 的上下文敏感拼写纠错方法》。(许可)
下载
从 bitbucket 分叉或克隆。
Winnow 简介
简单来说，Winnow 是一种机器学习技术，用于从带标签的示例中辨别析取式（即 OR 运算）。
具体来说，这意味着，给定 m 个带标签的样本，每个样本都有一个 n 个布尔特征的向量 x = (x1, . . . , xn)，Winnow 会学习哪些特征需要进行“或”运算以获得正确的标签。
以电子邮件垃圾邮件过滤为例，基本级别是，我们取许多电子邮件的正文，并将它们分词成单词数组，这将是我们的特征向量。
每个特征（单词）如果存在于示例中则表示为 1，不存在则表示为 0。
现在您将得到这个
| x1 | x2 | x3 | x4 | x5 | ... | xn | 垃圾邮件？（是/否） |
| $$$ | 100% free | viagra | the | weight loss | ... | f(x) | |
| 0 | 1 | 0 | 1 | 0 | ... | ? |
现在您看到了问题，特征集可能非常大，许多特征被设置为 true（例如 the 几乎出现在每封电子邮件中），而正确的标记仅取决于一小部分特征 r。
Winnow 的工作原理
- 在 n 个变量（特征向量）上初始化权重 w1 = w2 = . . . = wn = 1。
- 给定一个示例 x = (x1, . . . , xn)
如果
则输出 1，否则输出 0。
θ是我们自行设定的阈值 - 如果算法出错
- 如果预测为 0 而 f (x) = 1，则对于每个等于 1 的 xi ，增加 wi 的值。（值太低，提升有贡献的特征）
- 如果预测为 1 而 f (x) = 0，则对于每个等于 1 的 xi，减小 wi 的值。（值太高，降低有贡献的特征）
Winnow 给出 O(r log n) 的错误界限。
其中
r：相关特征
n：总特征数
Winnow 实战
设置θ=6（特征计数）
| x1 w1=1 |
x2 w2=1 |
x3 w3=1 |
x4 w4=1 |
x5 w5=1 |
x6 w6=1 |
f(x) 的预测 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 (Σixiwi=1 ≥6?) |
| 0 w1=1 |
1 w2=2 |
0 w3=1 |
1 w4=2 |
1 w5=2 |
1 w6=2 |
0 (Σixiwi=4 ≥6?) 将 xi=1 的 wi 加倍 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 (2 ≥6?) |
| 0 w1=1 |
0 w2=2 |
0 w3=1 |
1 w4=1 |
1 w5=1 |
1 w6=1 |
1(6 ≥6?) 将 xi=1 的 wi 除以二 |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 (2 ≥6?) |
| ... | ... | |||||
（错误在于red；目标 f(x) = x2 ∨ x3, n = 6, r = 2）
public class Sample
{
public bool[] Features { get; set; }
public bool Class { get; set; }
public Sample ToggleClass()
{
var invertedSample = (Sample)this.MemberwiseClone();
invertedSample.Class = !invertedSample.Class;
return invertedSample;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder("(" + Class + ")[");
for (int i = 0; i < Features.Length; i++)
{
sb.Append(Convert.ToInt16(Features[i]));
if (i < Features.Length - 1)
{
sb.Append(',');
}
}
sb.Append("]");
return sb.ToString();
}
}
/// <summary>
/// Algorithm for learning monotone disjunction function from labeled examples
/// </summary>
public class Winnow : ISupervisedLearning
{
#region Member Variables
private readonly double[] _weights;
private readonly double _threshold;
private readonly double _promotion;
private readonly double _demotion;
#endregion
public int Mistakes { get; private set; }
#region Constructor
public Winnow(int featuresCount, double threshold, double promotion, double demotion, double initialWeight)
{
this._threshold = threshold;
this._promotion = promotion;
this._demotion = demotion;
this._weights = new double[featuresCount];
for (int i = 0; i < _weights.Length; i++)
{
_weights[i] = initialWeight;
}
}
#endregion
#region ISupervisedLearning
public void Train(IEnumerable<Sample> samples)
{
Train(samples.ToArray());
}
public void Train(params Sample[] samples)
{
lock (this)
{
foreach (var s in samples)
{
bool prediction = Predict(s);
if (prediction != s.Class)//prediction was wrong
{
Mistakes++;
if (!prediction && s.Class)
{
AdjustWeights(s, _promotion);
}
else
{
AdjustWeights(s, _demotion);
}
}
}
}
}
public bool Predict(Sample sample)
{
double sum = GetScore(sample);
return sum >= _threshold;
}
public double GetScore(Sample sample)
{
double sum = 0;
for (int i = 0; i < _weights.Length; i++)
{
if (sample.Features[i])
{
sum += _weights[i];
}
}
return sum;
}
#endregion
#region Public Methods
public override string ToString()
{
var sb = new StringBuilder();
foreach (var item in _weights)
{
sb.Append(item);
sb.Append(",");
}
return sb.ToString();
}
#endregion
#region Private Methods
private void AdjustWeights(Sample s, double adjustment)
{
for (int i = 0; i < _weights.Length; i++)
{
if (s.Features[i])
{
_weights[i] *= adjustment;
}
}
}
#endregion
}
问题定义
好的，现在我们对 Winnow 的工作原理有了一定的了解，让我们回到当前的问题；上下文敏感拼写纠错作为一种词语消歧任务。
我们需要向 Winnow 提供两样东西；一个 **布尔特征向量**，和一个 **标签**；这构成了一个 *单一* 的训练样本。
这里的 **标签** 将是两个或多个混淆词中的一个，这些词共同组成一个 *混淆集*。
a 混淆集 C ={W1;....;Wn} 意味着集合中的每个词 Wi 都与其他词混淆。
具体来说，如果 C ={hear, here}，则输出标签将是 hear 或 here。
显然，我们有很多 *混淆集*；每个混淆集都有自己独特的特征向量。
C1 ={hear, here}
C2 ={by, buy}
C3 ={to, two,too}
等等……在代码中，我使用了一些来自常用混淆词的集合。
这些就是标签，那么另一个组成部分（*特征*）呢？
给定一个句子，我们想提取目标词上下文中的特定语言模式。
我们将使用两种类型的特征：**上下文词**和**搭配**。
**上下文词** 特征测试目标词 ±k 个词范围内是否存在特定单词。
**搭配** 特征测试目标词周围最多 ℓ 个连续单词和/或词性标签的模式。在代码中，k 被设置为 10，ℓ 被设置为 2。
对于混淆集 {weather, whether} 有用的特征示例包括
（1）±10 个词范围内的 *cloudy*
（2）__to VERB
特征（1）是一个上下文词特征，倾向于暗示 weather。特征 2 是一个搭配，检查目标词后面紧跟着的“to VERB”模式，倾向于暗示 whether（例如 I don’t know whether to laugh or cry）。
高层图
以下操作针对单个混淆集进行
细则
语料库预处理
语料库首先被分割成完整的句子；每个句子被分词成单词列表和词性标签。Richard Northedge 的词性标注器被使用。
public class Sentence
{
public string[] Words { get; set; }
public string[] POSTags { get; set; }
}
private IEnumerable<Sentence> PreProcessCorpora(IEnumerable<string> corpora)
{
var sentences = new ConcurrentBag();
Parallel.ForEach(corpora, phrase =>
{
string[] tokens = SplitIntoWords(phrase);
string[] posTags;
lock (_lock)
{
posTags = _posTagger.Tag(tokens);
}
sentences.Add(new Sentence
{
Words = tokens,
POSTags = posTags
});
});
return sentences;
}
获取上下文特征
在训练语料库中（*即每句话*）逐一梳理，每次出现混淆集中的一个词时，提取上下文的所有可能特征—即，对于±k 词范围内的每个不同单词，生成一个上下文词特征。
public class ContextFeaturesExtractor : AbstractExtractor
{
public ContextFeaturesExtractor(int k)
: base(k)
{
}
public override HashSet<string> Extract(string[] tokens, int targetPosition)
{
var features = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
int backward = targetPosition - 1;
int forward = targetPosition + 1;
for (int counter = 0; counter < n; counter++)
{
if (backward <= -1 && forward >= tokens.Length)
{
break;
}
if (backward > -1)
{
AddFeature(features, tokens[backward]);
backward--;
}
if (forward < tokens.Length)
{
AddFeature(features, tokens[forward]);
forward++;
}
}
return features;
}
}
获取搭配特征
……以及 2 个搭配（*出现在词之前和之后*），用于表达最多ℓ 个连续元素的每种方式。
public class CollocationFeaturesExtractor : AbstractExtractor
{
public CollocationFeaturesExtractor(int l)
: base(l)
{
}
public override HashSet<string> Extract(string[] posTags, int targetPosition)
{
var features = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
for (int c = 0; c < n; c++)
{
var preceding = string.Empty;
int backward = targetPosition - (c + 1);
while (backward < targetPosition && backward > -1)
{
preceding += posTags[backward] + " ";
backward++;
}
if (!string.IsNullOrEmpty(preceding))
{
preceding += "_";
AddFeature(features, preceding);
}
string succeeding = "_ ";
int forward = targetPosition + 1;
for (int j = 0; j <= c && forward < posTags.Length; j++, forward = targetPosition + j + 1)
{
succeeding += posTags[forward] + " ";
}
succeeding = succeeding.TrimEnd();
if (succeeding != "_")
{
AddFeature(features, succeeding.TrimEnd());
}
}
return features;
}
}
统计数据收集
在此过程中，还会收集特征出现次数的统计数据，即，对于目标词 W 的每个特征 F，我们记录
N11 ：包含 F 和 W 的文档（*句子*）数量。
N10 ：仅包含 F 的文档数量。
N01 ：仅包含 W 的文档数量。
N00 ：未找到 W 或 F 的文档数量。F 。
N ：文档总数。
特征剪枝
完成这些步骤后，会生成一个训练语料库中找到的所有特征的详尽列表，此时；可以应用剪枝标准来消除不可靠或信息量不足的特征。使用了两个标准（它们利用了上述出现次数的统计数据）
（1）特征 F 的存在/不存在对 W 的正确分类决策有多大信息贡献。（*互信息*）
（2）特征的存在与目标词的身份没有显着相关性（通过 0.05 显着性水平的卡方检验确定）。
public class MutualInformation : IFeatureSelector
{
#region Member Variables
private readonly int k;
#endregion
#region Constructor
public MutualInformation(int k)
{
this.k = k;
}
#endregion
#region IFeatureSelector
public IDictionary<string, Stats> Select(IDictionary<string, Stats> terms)
{
var features = new Dictionary<string, double>(terms.Count, StringComparer.OrdinalIgnoreCase);
foreach (var term in terms)
{
var value = Calculate(n: term.Value.N,
n00: term.Value.N00,
n01: term.Value.N01,
n10: term.Value.N10,
n11: term.Value.N11);
features.Add(term.Key, value);
}
var orderedFeatures = features
.OrderByDescending(s => s.Value)
.Select(s => s.Key);
var prunedFeatures = orderedFeatures
.Take(k)
.ToDictionary(key => key, key => terms[key]);
return prunedFeatures;
}
#endregion
#region Private Methods
private double Calculate(int n, double n00, double n01, double n10, double n11)
{
double n1_ = n10 + n11;
double n_1 = n01 + n11;
double n0_ = n00 + n01;
double n_0 = n10 + n00;
double sum = 0;
sum += (n11 / n) * Math.Log((n * n11) / (n1_ * n_1), 2);
sum += (n01 / n) * Math.Log((n * n01) / (n0_ * n_1), 2);
sum += (n10 / n) * Math.Log((n * n10) / (n1_ * n_0), 2);
sum += (n00 / n) * Math.Log((n * n00) / (n0_ * n_0), 2);
return sum;
}
#endregion
}
public class ChiSquaredTest : IFeatureSelector
{
#region Member Variables
private readonly double _significanceLevel;
private readonly Dictionary<double, double> _distributionTable;
#endregion
#region Constructor
public ChiSquaredTest(double significanceLevel)
{
this._significanceLevel = significanceLevel;
_distributionTable = new Dictionary<double, double> {
{0.1,2.71},
{0.05,3.84},
{0.01,6.63},
{0.005,7.88},
{0.001,10.83}
};
}
#endregion
#region IFeatureSelector
public IDictionary<string, Stats> Select(IDictionary<string, Stats> features)
{
var prunedFeatures = new Dictionary<string, Stats>(StringComparer.OrdinalIgnoreCase);
foreach (var feature in features)
{
var featureValue = Calculate(feature.Value.N, feature.Value.N00, feature.Value.N01, feature.Value.N10, feature.Value.N11);
if (featureValue > _distributionTable[_significanceLevel])
{
prunedFeatures.Add(feature.Key, feature.Value);
}
}
return prunedFeatures;
}
#endregion
#region Private Methods
private double Calculate(int n, double n00, double n01, double n10, double n11)
{
var numerator = n * Math.Pow(((n11 * n00) - (n10 * n01)), 2);
var denominator = (n11 + n01) *
(n11 + n10) *
(n10 + n00) *
(n01 + n00);
var value = numerator / denominator;
return value;
}
#endregion
}
添加带标签的样本
训练样本由一个句子组成，*表示为一组激活的特征*，以及对该句子正确的混淆集中的词 Wc。
private class RoughSample
{
public HashSet<string> Features { get; set; }
public string Word { get; set; }
}
培训
现在我们有了合适的训练数据列表，我们为混淆集中的每个词训练一个分类器。
var cloudClassifiers = new Dictionary<string, ISupervisedLearning[]>(confusionSet.Count());
foreach (var word in confusionSet)
{
var classifiers = new ISupervisedLearning[1];
int i = 0;
for (double beta = 0.5; beta < 1 && i < classifiers.Length; beta += 0.1, i++)
{
classifiers[i] = new Winnow.Winnow(features.Length, threshold: 1, promotion: 1.5, demotion: beta, initialWeight: 1);
}
cloudClassifiers[word] = classifiers;
}
训练以在线方式进行，每个样本被视为 Wc 分类器的正例，而对混淆集中其他词的分**类器**则视为负例。（*一对多*）
Parallel.ForEach(trainingData, sample =>
{
var positive = new Sample
{
Class = true,
Features = CreateFeaturesVector(sample.Features, features)
};
Sample negative = positive.ToggleClass();
foreach (var cloud in cloudClassifiers)
{
var example = cloud.Key == sample.Word ? positive : negative;
foreach (var classifier in cloud.Value)
{
classifier.Train(example);
}
}
});
预测
当呈现一个句子时，系统会检查每个混淆集的分类器，如果句子包含来自混淆集中的一个词，则提取特征并运行相应的分类器，返回得分最高的预测。
/// <summary>
/// Checks every word in given sentence to check its contextually correct
/// </summary>
/// <param name="phrase">sentence to check</param>
/// <returns> a Dictionary of the wrong word position in sentence as Key and its correction as Value</returns>
public Dictionary<int, string> Predict(string phrase)
{
string[] tokens = SplitIntoWords(phrase);
var correctWords = new Dictionary<int, string>();
foreach (var comparator in _comparators)
{
foreach (var confusedWord in comparator.ConfusionSet)
{
for (int i = 0; i < tokens.Length; i++)
{
if (!tokens[i].Equals(confusedWord, StringComparison.OrdinalIgnoreCase))
{
continue;
}
string[] posTags;
lock (_lock)
{
posTags = _posTagger.Tag(tokens);
}
var features = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
features.UnionWith(_contextFeaturesExtractor.Extract(tokens, i));
features.UnionWith(_collocationtFeaturesExtractor.Extract(posTags, i));
var sample = new Sample
{
Features = CreateFeaturesVector(features, comparator.Features)
};
var predictions = new Dictionary<string, double>(comparator.Cloud.Count);
foreach (var classifier in comparator.Cloud.Keys)
{
predictions[classifier] = comparator
.Cloud[classifier]
.Sum(c => c.GetScore(sample));
}
string correctedWord = predictions.Aggregate((a, b) => a.Value > b.Value ? a : b).Key;
if (!tokens[i].Equals(correctedWord, StringComparison.OrdinalIgnoreCase))
{
correctWords.Add(i, correctedWord);
}
}
}
}
return correctWords;
}
评估版
在接下来的实验中，训练集和测试集来自美国国家语料库（OANC）的文本部分（约 1100 万词，按句子随机 80-20% 分割），以及 28 个混淆集。
总体准确率为 94%。 在我的 i7, 3.4 GHz, 8 GB RAM 机器上，特征提取 + 训练 + 测试的平均运行时间为 59 分钟。 上述结果是在**禁用**剪枝的情况下实现的，启用剪枝后，准确率下降，运行时间增加。
|
改进领域
- 在训练中，每个词都有一个分类器数组，在代码中我保持为 1，我们可以添加更多算法，如逻辑回归甚至神经网络，然后使用加权多数算法选择最佳结果。
- 在上下文特征提取中，我们可以使用字典 API 来正确地词干化和单数化标记。
参考文献
- 机器学习理论，Winnow 算法（Avrim Blum 的笔记）
- Vasilis Vryniotis：文本分类中的特征选择方法使用
- Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze，信息检索导论，剑桥大学出版社。2008：特征选择
- Richard Northedge：英语句子统计解析
- Littlestone, N.; Warmuth, M. (1994). "The Weighted Majority Algorithm".
- ANDREW R. GOLDING and DAN ROTH，基于 Winnow 的上下文敏感拼写纠错方法。