# -*- coding: utf-8 -*-
import math
import nltk

# 6.6 最大熵分类器
"""
最大熵分类器使用了一个与朴素贝叶斯分类器使用的模型非常相似的模型。不是使用概
率设置模型的参数，它使用搜索技术找出一组将最大限度地提高分类器性能的参数。特别的，
它查找使训练语料的整体可能性最大的参数组。其定义如下：
(10) P(features) = Σx ∈ corpus P(label(x)|features(x))
其中 P(label|features)，一个特征为 features 将有类标签 label 的输入的概率，被定义为：
(11) P(label|features) = P(label, features)/Σlabel P(label, features)
由于相关特征的影响之间的潜在的复杂的相互作用，没有办法直接计算最大限度地提高
训练集的可能性的模型参数。因此，最大熵分类器采用迭代优化技术选择模型参数，该技术
用随机值初始化模型的参数，然后反复优化这些参数，使它们更接近最优解。这些迭代优化
技术保证每次参数的优化都会使它们更接近最佳值，但不一定提供方法来确定是否已经达到
最佳值。由于最大熵分类器使用迭代优化技术选择参数，它们花费很长的时间来学习。当训
练集的大小、特征的数目以及标签的数目都很大时尤其如此。
一些迭代优化技术比别的快得多。当训练最大熵模型时，应避免使用广义
迭代缩放（Generalized Iterative Scaling，GIS）或改进的迭代缩放（Improv
ed Iterative Scaling，IIS），这两者都比共轭梯度（Conjugate Gradient，CG）
和 BFGS 优化方法慢很多
"""

# 最大熵模型
"""
最大熵分类器模型是一朴素贝叶斯分类器模型的泛化。像朴素贝叶斯模型一样，最大熵
分类器为给定的输入值计算每个标签的可能性，通过将适合于输入值和标签的参数乘在一
起。朴素贝叶斯分类器模型为每个标签定义一个参数，指定其先验概率，为每个（特征，标
签）对定义一个参数，指定独立的特征对一个标签的可能性的贡献。
相比之下，最大熵分类器模型留给用户来决定什么样的标签和特征组合应该得到自己的
参数。特别的，它可以使用一个单独的参数关联一个特征与一个以上的标签；或者关联一个
以上的特征与一个给定的标签。这有时会允许模型“概括”相关的标签或特征之间的一些差
异。
每个接收它自己的参数的标签和特征的组合被称为一个联合特征。请注意，联合特征是
有标签的的值的属性，而（简单）特征是未加标签的值的属性。
描述和讨论最大熵模型的文字中，术语“特征 features”往往指联合特征；术
语“上下文 contexts”指我们一直说的（简单）特征。
通常情况下，用来构建最大熵模型的联合特征完全镜像朴素贝叶斯模型使用的联合特
征。特别的，每个标签定义的联合特征对应于 w[label]，每个（简单）特征和标签组合定义
的联合特征对应于 w[f, label]。给定一个最大熵模型的联合特征，分配到一个给定输入的标
签的得分与适用于该输入和标签的联合特征相关联的参数的简单的乘积。
(12) P(input, label) = ∏joint-features(input,label)w[joint-feature]
"""

# 熵的最大化

# 假设我们被分配从 10 个可能的任务的列表（标签从 A-J）中为一个给定的词找出正确
# 词意的任务。首先，我们没有被告知其他任何关于词或词意的信息。我们可以为 10 种词意
# 选择的概率分布很多，例如：
#       A   B   C    D   E   F   G   H   I   J
# (i)  10% 10% 10% 10% 10% 10%  10%  10%  10%  10%
# (ii) 5%  15% 0%  30%  0%  8%  12%  0%  6%  24%
# (iii) 0% 100% 0%  0%  0%  0%   0%  0%  0%  0%
"""
虽然这些分布都可能是正确的，我们很可能会选择分布（i），因为没有任何更多的信息，
也没有理由相信任何词的词意比其他的更有可能。另一方面，分布（ii）及（iii）反映的假
设不被我们已知的信息支持。
直觉上这种分布（i）比其他的更“公平”，解释这个的一个方法是引用熵的概念。在决
策树的讨论中，我们描述了熵作为衡量一套标签是如何“无序”。特别的，如果是一个单独
的标签则熵较低，但如果标签的分布比较均匀则熵较高。在我们的例子中，我们选择了分布
（i）因为它的标签概率分布均匀——换句话说，因为它的熵较高。一般情况下，最大熵原
理是说在与我们所知道的一致的的分布中，我们会选择熵最高的
接下来，假设我们被告知词意 A 出现的次数占 55%。再一次，有许多分布与这一条新
信息一致，例如：
      A   B   C  D  E  F  G  H  I  J
(iv) 55% 45% 0% 0% 0% 0% 0% 0% 0% 0%
(v)  55% 5%  5% 5% 5% 5% 5% 5% 5% 5%
(vi) 55% 3% 1% 2% 9% 5% 0% 25% 0% 0%
但是，我们可能会选择最少无根据的假设的分布——在这种情况下，分布（v）。
最后，假设我们被告知词 up 出现在 nearby 上下文中的次数占 10%，当它出现在这个上
下文中时有 80%的可能使用词意 A 或 C。从这个意义上讲，将使用 A 或 C。在这种情况下，
我们很难手工找到合适的分布；然而，可以验证下面的看起来适当的分布：
           A     B     C     D     E     F     G     H    I     J
(vii) +up 5.1%  0.25% 2.9% 0.25% 0.25% 0.25% 0.25% 0.25% 0.25% 0.25%
      -up 49.9% 4.46% 4.46% 4.46% 4.46% 4.46% 4.46% 4.46% 4.46% 4.46%
      
    特别的，与我们所知道的一致的分布：如果我们将 A 列的概率加起来是 55％，如果我
们将第 1 行的概率加起来是 10％；如果我们将+up 行词意 A 和 C 的概率加起来是 8%（或+
up 行的 80％）。此外，其余的概率“均匀分布”。
纵观这个例子，我们将自己限制在与我们所知道的一致的分布上。其中，我们选择最高
熵的分布。这正是最大熵分类器所做的。特别的，对于每个联合特征，最大熵模型计算该特
征的“经验频率”——即它出现在训练集中的频率。然后，它搜索熵最大的分布，同时也预
测每个联合特征正确的频率。
"""
#  生成式分类器对比条件式分类器
"""
朴素贝叶斯分类器和最大熵分类器之间的一个重要差异是它们可以被用来回答问题的
类型。朴素贝叶斯分类器是一个生成式分类器的例子，建立一个模型，预测 P(input, label)，
即(input, label)对的联合概率。因此，生成式模型可以用来回答下列问题：
1. 一个给定输入的最可能的标签是什么？
2. 对于一个给定输入，一个给定标签有多大可能性？
3. 最有可能的输入值是什么？
4. 一个给定输入值的可能性有多大？
5. 一个给定输入具有一个给定标签的可能性有多大？
6. 对于一个可能有两个值中的一个值（但我们不知道是哪个）的输入，最可能的标签是什么？
最大熵分类器是条件式分类器的一个例子。条件式分类器建立模型预测 P(label|input)——一个给定输入值的标签的概率。
因此，条件式模型仍然可以被用来回答问题 1 和 2。然而，条件式模型不能用来回答剩下的问题 3-6。一般情况下，
生成式模型确实比条件式模型强大，因为我们可以从联合概率 P(input, label)计算出条件概率 P(label|input)，但反过来不行。
然而，这种额外的能力是要付出代价的。由于该模型更强大的，它也有更多的“自由参数”需要学习的。而训练集的大小是固定的。
因此，使用一个更强大的模型时，我们可用来训练每个参数的值的数据也更少，使其难以找到最佳参数值。
结果是一个生成式模型回答问题 1 和 2 可能不会与条件式模型一样好，因为条件式模型可以集中精力在这两个问题上。
然而，如果我们确实需要像 3-6 问题的答案，那么我们别无选择，只能使用生成式模型。生成式模型与条件式模型之间的差别类似与
一张地形图和一张地平线的图片之间的区别。虽然地形图可用于回答问题的更广泛，制作一张精确的地形图也明显比制作一张精确的
地平线图片更加困难。
"""