机器学习--最大熵模型实践

Posted on Edited on

机器学习 | 最大熵模型实践

今天我们来手动实现最大熵模型。

首先，我们知道最大熵的模型 \[ P_w(y | x) = \frac{1}{Z_w(x)}exp(\sum^{n}_{i}w_if_i(x,y)) \] 其中： \[ Z_w(x) =\sum_{y}exp(\sum^n_{i}w_if_i(x,y)) \] 这里，\(f_i(x,y)\)代表特征函数，\(w_i\)代表每个特征函数对应的权值。

\(f_i(x,y)\)反映的是x和y的特征，也就是说它是对输入和输出同时抽取特征的。 它的定义是：\(f(x,y)=1\), x与y满足某一事实, 否则0

值得注意的是，这里在判断x,y是否满足某一事实的时候不是简单判断x整体与y的关系，而是判断x的特征与y的关系。举个例子： \[ x＝dict(a=1, b=1, c=1)，y='1' \] 这样一个训练数据,我们对它进行特征提取时： 对x的第一个特征抽取，用一个三元组表示就是(x某一特征名，特征名对应的值，y) 分别对x的特征进行抽取得到三个特征函数: $('a',1,'1'), ('b',1,'1'),('c',1,'1') $

求解\(w_i\)时，可以通过GIS算法求解，算法流程如下：

1.任意初始化\(w_i\),一般为0： \[ w_i(0)=0,i∈{1,2,3,...,n} \] 这里的下标表示第i个特征对应的w。 2.重复以下更新直至收敛： \[ w_i(t+1)=w_i(t)+\frac{1}{C}log⁡E_P^{(f_i)}E_P(n)(fi),i∈{1,2,...,n} \] 其中C一般取样本的最大特征数，反应了w更新速度。 \[ Ep^{f}=\sum_{x,y}P^{(x,y)}f(x,y) \] 表示的是某一个特征函数关于经验分布\(P^{(x,y)}\)的期望值

\[ E_P(f)=\sum_{x,y}P^{(x)}P(y|x)f(x,y) \] 表示的是某一个特征函数关于模型P(y|x)与经验分布\(P^{(x)}\)的期望值 先来看和\(P^{(x,y)}\)和\(P^{(x)}\): \[ P^{(X=x,Y=y)}=v(X=x,Y=y)N \\P^{(X=x)}=v(X=x)N \] 其中v(X=x,Y=y)表示样本(x,y)出现的频率，v(X=x)表示样本x出现的频率，N表示样本个数。 由于我们在训练时，样本数据存在唯一性，因此： \[ P^{(X=x,Y=y)}＝P^{(X=x)}=\frac{1}{N} \] 所以有： \[ E_P^{(f)}=\frac{1}{N}\sum_{x,y}f(x,y) \\ E_P{(f)}=\frac{1}{N}\sum_{x,y}P(y|x)f(x,y) \\E_P^{(fi)}E_P(n)(fi)=\sum_{x,y}f_i(x,y)\sum_{x,y}P(y|x)f_i(x,y) \] \(\sum_{x,y}f_i(x,y)\)表示的所有样本在被某一个特征函数抽取的特征值之和。

所以，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import numpy as np
def encode(featureset, label, mapping):
    encoding = []
    for (fname, fval) in featureset.items():
        if(fname,fval,label) in mapping:
            encoding.append((mapping[(fname,fval,label)],1))
    return encoding

# 求解∑x,yfi(x,y)
def calculate_empirical_fcount(train_toks, mapping):
    fcount = np.zeros(len(mapping))
    for tok, label in train_toks:
        for(index, val) in encode(tok,label,mapping):
            fcount[index] += val
    return fcount

# 求解P(y|x)
def prob(tok, labels, mapping, weights):
    prob_dict = {}
    for label in labels:
        total = 0.0
        for(index,val) in encode(tok,label,mapping):
            total += weights[index]*val
        prob_dict[label] = np.exp(total)
    value_sum = sum(list(prob_dict.values()))
    for(label, value) in prob_dict.items():
        prob_dict[label] = prob_dict[label]/value_sum
    return prob_dict

# 求解∑x,yP(y|x)fi(x,y)
def calculate_estimated_fcount(train_toks, mapping, labels, weights):
    fcount = np.zeros(len(mapping))
    for tok, label in train_toks:
        prob_dict = prob(tok,labels,mapping,weights)
        for label, p in prob_dict.items():
            for (index, val) in encode(tok, label, mapping):
                fcount[index] += p*val
    return fcount

# 抽取样本中所有特征函数
def maxent_train(train_toks):
    mapping = {}  # maps (fname, fval, label) -> fid
    labels = set()
    feature_name = set()
    for(tok, label) in train_toks:
        for(fname, fval) in tok.items():
            if (fname,fval,label) not in mapping:
                mapping[(fname,fval,label)] = len(mapping)
            feature_name.add(fname)
        labels.add(label)
    C = len(feature_name)+1
    Cinv = 1/C
    empirical_fcount = calculate_empirical_fcount(train_toks,mapping)
    weights = np.zeros(len(empirical_fcount))
 
    iter = 1
    while True:
        if iter == 100:
            break
        estimated_fcount = calculate_estimated_fcount(train_toks, mapping, labels, weights)
        weights += (empirical_fcount / estimated_fcount) * Cinv
        iter+=1
    return weights, labels, mapping
 
if __name__ == '__main__':
    train_data = [
        (dict(a=1, b=1, c=1), '1'),
        (dict(a=1, b=1, c=0), '0'),
        (dict(a=0, b=1, c=1), '1')]
 
    maxent_train(train_data)

以上就是今天的内容，谢谢大家的观看！