基于最大熵模型的人名分类

矫情吗；* 2022-08-17 14:16 194阅读 0赞

“熵”最初是热力学中的一个概念，上世纪40年代，香农首先在信息论中引入了信息熵的概念。信息熵用来表示不确定度的度量，不确定度越大，熵值越大。极限情况，当一个随机变量均匀分布时，熵值最大；完全确定时，熵值为0。如果没有外界干扰，随机变量总是趋向于无序，在经过足够时间的稳定演化，它应该能够达到的最大程度的熵。

最大熵模型的核心思想就是：为了估计随机变量的状态，在已知部分知识的前提下，关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断，其原则是承认已知事物（知识），且对未知事物不做任何假设，没有任何偏见。这样也就等价于最大化熵，认为在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。

## 熵 ##

熵公式如下

![20151126154228094][]

容易得到熵始终大于0的。

联合熵：两个随机变量X，Y的联合分布，可以形成联合熵Joint Entropy，用H(X,Y)表示。  
条件熵：在随机变量X发生的前提下，随机变量Y发生所新带来的熵定义为Y的条件熵，用H(Y|X)表示，用来衡量在已知随机变量X的条件下随机变量Y的不确定性。  
H(Y|X) = H(X,Y) – H(X)，整个式子表示(X,Y)发生所包含的熵减去X单独发生包含的熵。至于怎么得来的请看推导：

![20151126154355685][]

这个式子的实际含义就是加入x的标记后，相当于引入了一定的知识，那么就会减小y的不确定性，也就是减小了熵。

## 最大熵模型 ##

最大熵模型的一般表达式

![20151125233723154][]

定义特征函数

![20151125233836956][]

x为上下文信息，而并非仅仅是目标词

y代表标签

特征考虑一个例子：记者王大勇，假设已经分过词，当前词为王大勇，前接词为记者。可以定义一条特征为：

![20151125235544150][]

下面两个期望要分清，这是算法的关键

定义特征函数f的经验期望如下：

![20151126101511342][]

![20151126103417794][]示样本(x,y)在所有样本库中出现的概率，如果认为训练样本是真实情况的很好的近似，可以用训练语料D=\{(x\_1 y\_1 ),(x\_2 y\_2 )…(x\_N y\_N)\}中出现的经验概率表示：

![20151126103523782][]

C(x,y)代表样本库中(x,y)出现的次数，N为样本库的样本数。

定义特征函数f的模型期望为：

![20151126104000707][]

![20151126104601981][]同上，也用x在训练语料里出现的经验概率表示，也就是数数然后归一化。

最大熵模型的约束就是使得任意特征fi的经验期望和模型期望相等

![20151126104438585][]

根据概率公式的定义，我们还有另外一个约束：

![20151126105054759][]

所以我们就得到了一个有约束条件的最优化问题：

max：

![20151126135916934][]

subject to：

![Image 1][]

![20151126104438585][]![Image 1][]

![20151126105054759][]

里面p(y|x)相当于自变量，我们需要得到的就是条件熵H(p)最大的模型p。

通过拉格朗日乘子法，求解

![20151126140624531][]

的极大值。

对p求偏导，并令偏导数等于0，得到取极值的条件

用λ和μ表示p，再利用![20151126105054759][]消去μ，得到只含有λ的式子

则p用λ表示为

![20151126143151161][]

z(x)为归一化因子

z(x)=![20151126113335317][]

将求得的最优解P\*(y|x)带回之前建立的拉格朗日函数L

![20151126143444483][]

化简得到只关于λ的式子

![20151126143537737][]

这样我们极大化L(λ)，求得λ的具体数值后模型也就确定了。这个问题的解法比较多，一般用GIS、IIS、LBFGS等方法。

from collections import defaultdict
    import math
    import random
    from os.path import*
    
    def get_features(data, letters="abcdefghijklmnopqrstuvwxyz"):
            """From NLTK's names_demo_features: first & last letters, how many
            of each letter, and which letters appear."""
            name = data
            return ([name[0].lower(), name[-1].lower()] +
                    [name.lower().count(letter) for letter in letters] +
                    [letter in name.lower() for letter in letters])
    
    class maxent:
        def __init__(self):
            self.label_feature_pair = defaultdict(int)         
            self.all_instances = []                          
            self.labels = []
            self.max_instance = 0
    
        def initial(self, instances):
            for instance in instances:
                label = instance[0]
                if label not in self.labels:
                    self.labels.append(label)
                features=get_features(instance[1])
                for feature in features:
                    self.label_feature_pair[(label, feature)] += 1
                label_features = []
                label_features.append(label)
                label_features += get_features(instance[1])
                self.all_instances.append(label_features)
            self.size = len(self.all_instances)
            self.current_lambda = [0.0] * len(self.label_feature_pair)
            for instance in self.all_instances:
                if len(instance) - 1 > self.max_instance:
                    self.max_instance = len(instance) - 1
            self.real_expectation = [0.0] * len(self.label_feature_pair)
            for i, f in enumerate(self.label_feature_pair):
                self.real_expectation[i] = float(self.label_feature_pair[f])/self.size
                self.label_feature_pair[f] = i
    
        def cal_numerator(self, features, label):
            numerator = 0
            for f in features:
                if(label, f) in self.label_feature_pair:
                    numerator += self.current_lambda[self.label_feature_pair[(label, f)]]
            return math.exp(numerator)
    
        def cal_posterior(self, features):
            numerators_label = []
            for label in self.labels:
                numerator = self.cal_numerator(features, label)
                numerators_label.append((numerator, label))
            denominator = 0;
            for numerator, label in numerators_label:
                denominator += numerator;
            posterior_label = []
            for numerator,label in numerators_label:
                posterior_label.append((numerator/denominator, label))
            return posterior_label
    
        def cal_expectation(self):
            expectation = [0.0] * len(self.label_feature_pair)
            for instance in self.all_instances:
                features = instance[1:]
                probability = self.cal_posterior(features)
                for feature in features :
                    for posterior,label in probability:
                        if(label, feature) in self.label_feature_pair:
                            index = self.label_feature_pair[(label, feature)]
                            expectation[index] += posterior * (1.0/self.size)
            return expectation
      
        def is_convergence(self, last_lambda, current_lambda):
            for i in range(len(last_lambda)):
                if abs (last_lambda[i] - current_lambda[i])>=0.0005:
                    return False
            return True
        
        #calculate the nth lambda and (n+1)th lambda  
        def cal_step(self, index):
            step_size = 1.0/self.max_instance * math.log(self.real_expectation[index]/self.expectation[index])
            return step_size
        
        def GIS(self):
            while 1 :
                last_lambda = self.current_lambda[:]
                self.expectation = self.cal_expectation()
                for index in range(len(self.current_lambda)):
                    step_size = self.cal_step(index)
                    self.current_lambda[index] += step_size
                if self.is_convergence(last_lambda, self.current_lambda):
                    break
        
        def train(self, instances):
            self.initial(instances)
            self.GIS()
        
        def classify(self, instance):
            probability = self.cal_posterior(get_features(instance[1]))
            probability.sort(reverse=True)
            return probability[0][1]
    
        def classify1(self, name):
            probability = self.cal_posterior(get_features(name))
            probability.sort(reverse=True)
            return probability[0][1]
    
    def accuracy(classifier, test):
        correct = [classifier.classify(x) == x[0] for x in test]
        return float(sum(correct)) / len(correct)
    
    
    def load_data(namelist,datafile="names/*.txt"):
            label = splitext(basename(datafile))[0]
            with open(datafile, "r") as file:
                for line in file:
                    data = line.strip()
                    namelist.append((label,data))
    
    def test_names_nltk(namelist):
            """Classify names using NLTK features"""
            print "\ntest_names_nltk"
            load_data(namelist,"names/male.txt")
            load_data(namelist,"names/female.txt")
            random.seed(hash("names"))
            random.shuffle(namelist)
            train, test = namelist[:6000], namelist[6000:]
            classifier = maxent()
            classifier.train(train)
            print accuracy(classifier, test)
            s=''
            while s!='q':
                  s=raw_input("input a name \n")
                  print classifier.classify1(s)
    if __name__=="__main__":
       namelist=[]
       test_names_nltk(namelist)

[最大熵学习笔记][Link 1]

[熵][Link 2]

[exponential family][]

[20151126154228094]: /images/20220731/b2a47435fe6a4a0aa9a87d822f3336b3.png
[20151126154355685]: /images/20220731/0a04f45e1e4543e08bfe1705c8d8bbb4.png
[20151125233723154]: /images/20220731/0e8d04bac15a459fb725dc99478bd91b.png
[20151125233836956]: /images/20220731/a12c66611c6841ad8ad4616321447878.png
[20151125235544150]: /images/20220731/2b78e62759de4b22a6c0c47d1b29304f.png
[20151126101511342]: /images/20220731/bf22b1d80c4c4948a74edbba56551898.png
[20151126103417794]: /images/20220731/7140b4625c594602bc18017e3f13f4e4.png
[20151126103523782]: /images/20220731/1136363a00054c869be18b78e1d1ba06.png
[20151126104000707]: /images/20220731/865af2e7517e4aa98887d671cdcf8464.png
[20151126104601981]: /images/20220731/9ccc649b36124786a2bdcd2f981380da.png
[20151126104438585]: /images/20220731/15af9dcce7ce4a9087b54425b81ae923.png
[20151126105054759]: /images/20220731/4aa24c906dd24865933fbb98081ffb65.png
[20151126135916934]: /images/20220731/7f66c07e933a4d109185eceeae1a59d9.png
[Image 1]: 
[20151126140624531]: /images/20220731/b1e8958ad6804460a0c73a61ecef0081.png
[20151126143151161]: /images/20220731/d0095980e75c44b7a3d1bddfae8a4843.png
[20151126113335317]: /images/20220731/5749499113af42178d1adff58364a61b.png
[20151126143444483]: /images/20220731/bc6c7d789d9b49c38c2110a3e68c7daf.png
[20151126143537737]: /images/20220731/c97a1ceab83c40baa848fe4719ebe826.png
[Link 1]: http://blog.csdn.net/itplus/article/details/26550597
[Link 2]: http://blog.csdn.net/richard2357/article/details/9744545
[exponential family]: http://blog.csdn.net/richard2357/article/details/16969335