PythonTip >> 博文 >> python

最大熵模型的python实现 - 信息抽取技术交流 - Web信息抽取技术论坛 - WebInfoExtract

zihua 2014-01-20 23:01:54 点击: 2138 | 收藏


  1. # -*- coding:utf8 -*-

  2. import math

  3. import sys

  4. def load_data(fname):

  5. """

  6. 从文件加载训练或测试数据

  7. 返回得到的输入矩阵x,输出向量y,

  8. 以及各维特征的最大值,y的最大值(用于确定x,y的取值范围,它们都是离散值)

  9. """

  10. f = open(fname)

  11. y=[]

  12. x=[]

  13. for line in f:

  14. line=line.strip('\n')

  15. str_list=line.split(' ')

  16. xi=[]

  17. for v in str_list:

  18. if v[0] == 'c':

  19. yi=v[-1:]

  20. y.append(int(yi))

  21. if v[0] == 'f':

  22. xij=v[-1:]

  23. xi.append(int(xij))

  24. x.append(xi)

  25. f.close()

  26. y_max=1

  27. for yval in y:

  28. if yval > y_max:

  29. y_max=yval

  30. x_max=[]

  31. for xval in x[0]:

  32. x_max.append(xval)

  33. for xvec in x:

  34. for i in range(len(xvec)):

  35. if xvec[i] > x_max[i]:

  36. x_max[i] = xvec[i]

  37. return x,y,x_max,y_max

  38. # 特征函数及其对应的参数

  39. class FeatureParam:

  40. def __init__(self,ft_index,except_class,except_ft_val):

  41. self.w=0.0

  42. self.ft_index=ft_index

  43. self.except_class=except_class

  44. self.except_ft_val=except_ft_val

  45. def feature_func(self,xvec,y):

  46. if y == self.except_class and xvec[self.ft_index] == self.except_ft_val:

  47. return 1

  48. else:

  49. return 0

  50. def init_feature_func_and_param(x_max_vec,y_max):

  51. # 生成特征函数:

  52. # 每个不同的<特征i,特征值的值v,分类label的值c>三元组都确定一个特征函数f

  53. # f(x,y),当向量x的第i维=v,且y=c时,特征函数值为1,否则为0.

  54. fvec=[]

  55. ft_index=-1

  56. for x_max in x_max_vec:

  57. ft_index+=1

  58. for xval in range(0,x_max+1):

  59. for yval in range(1,y_max+1):

  60. fp=FeatureParam(ft_index,yval,xval)

  61. fvec.append(fp)

  62. return fvec

  63. def estimated_except_feature_val(x_mat,y_vec,fparam):

  64. esti_efi = 0.0

  65. n_data=len(y_vec)

  66. # 将每条训练数据的特征函数值相加

  67. # 除以训练数据总数,即得经验特征函数期望值

  68. for i in range(n_data):

  69. x_vec = x_mat[i]

  70. esti_efi += fparam.feature_func(x_vec,y_vec[i])

  71. # perhaps there's no data match the feature function

  72. # to make the computation possible, let it be a small float number

  73. if esti_efi == 0.0:

  74. esti_efi = 0.0000001

  75. esti_efi /= 1.0*n_data

  76. return esti_efi

  77. def max_ent_predict_unnormalized(x_vec,y,fvec):

  78. """

  79. 未归一化的概率值

  80. 即各特征函数值的加权和

  81. 加权系数即对模型训练出来的参数

  82. """

  83. weighted_sum=0.0

  84. for fparam in fvec:

  85. weighted_sum += fparam.w * fparam.feature_func(x_vec,y)

  86. return math.exp(weighted_sum)

  87. def max_ent_normalizer(x_vec,y_max,fvec):

  88. zw=0.0

  89. for y in range(1,y_max+1):

  90. zw += max_ent_predict_unnormalized(x_vec,y,fvec)

  91. return zw

  92. def model_except_feature_val(x_mat,y_max,fparam,fvec,p_cached):

  93. data_size=len(x_mat)

  94. efi=0.0

  95. index=0

  96. ix=-1

  97. # 对各训练数据x:对所有可能的y的取值,求P(y|x)与特征函数值的乘积和

  98. # 并求其平均值

  99. # 即得模型的预测特征函数期望值

  100. for x_vec in x_mat:

  101. ix += 1

  102. zw=0.0

  103. tmp_efi=0.0

  104. for y in range(1,y_max+1):

  105. # compute p(y|x) at current w

  106. # in same iteration, p(y|x) not change, so can cache it

  107. if index < len(p_cached):

  108. p_y_given_x = p_cached[index]

  109. else:

  110. p_y_given_x = max_ent_predict_unnormalized(x_vec,y,fvec)

  111. p_cached.append(p_y_given_x)

  112. zw += p_y_given_x

  113. tmp_efi += p_y_given_x * fparam.feature_func(x_vec,y)

  114. index+=1

  115. tmp_efi /= zw

  116. efi += tmp_efi

  117. efi /= data_size

  118. if efi == 0.0:

  119. efi = 0.0000001

  120. return efi

  121. def feature_func_sum(fvec,xvec,y):

  122. m = 0.0

  123. for f in fvec:

  124. m += f.feature_func(xvec,y)

  125. return m

  126. def update_param(x_mat,y_vec,y_max,fvec):

  127. """

  128. 更新每个特征函数对应的参数:

  129. x_mat: 训练数据的输入矩阵

  130. y_vec: 训练数据的label向量

  131. y_max: label的最大取值,label取值范围为[1,y_max]

  132. fvec: 特征函数及对应参数组成的向量

  133. """

  134. # 所有特征函数的值相加,对不同的x,y来说,它是一个常量

  135. m = feature_func_sum(fvec,x_mat[0],y_vec[0])

  136. # 是否收敛

  137. convergenced = True

  138. # 参数更新向量各维的平方和,即模的平方

  139. sigma_sqr_sum=0.0

  140. # 更新后的参数

  141. w_updated=[]

  142. # 缓存P(y|x)的结果,避免重复计算

  143. p_cached=[]

  144. # 对每一个特征函数,分别更新对应的参数

  145. for fparam in fvec:

  146. # 计算训练数据的特征函数平均值

  147. esti_efi = estimated_except_feature_val(x_mat,y_vec,fparam)

  148. # 计算当前模型的特征函数期望值

  149. efi = model_except_feature_val(x_mat,y_max,fparam,fvec,p_cached)

  150. # 计算当前参数的更新值

  151. # 由于m是个常数,所以可以用这种方法计算

  152. sigma_i= math.log(esti_efi/efi) / m

  153. w_updated.append(fparam.w + sigma_i)

  154. # 如果对参数的更新较大,则认为不收敛

  155. if abs(sigma_i/(fparam.w+0.000001)) >= 0.10:

  156. convergenced = False

  157. sigma_sqr_sum += sigma_i*sigma_i

  158. i=0

  159. for fparam in fvec:

  160. fparam.w = w_updated[i]

  161. i+=1

  162. # 打印当前更新向量的长度

  163. print("sigma_len=%f"%math.sqrt(sigma_sqr_sum))

  164. return convergenced

  165. def log_likelihood(x_mat,y_vec,y_max,fvec):

  166. """

  167. 对每条训练数据的x,求其模型预测概率P(y|x),

  168. 相乘并取对数,即得对数似然函数值,

  169. 该值越大,说明模型对训练数据的拟合越准确

  170. """

  171. ix=-1

  172. log_likelihood = 0.0

  173. data_size = len(x_mat)

  174. for i in range(data_size):

  175. x_vec = x_mat[i]

  176. y = y_vec[i]

  177. log_likelihood += math.log(max_ent_predict_unnormalized(x_vec,y,fvec))

  178. log_likelihood -= math.log(max_ent_normalizer(x_vec,y_max,fvec))

  179. log_likelihood /= data_size

  180. return log_likelihood

  181. def max_ent_train(x_mat,y_vec,x_max_vec,y_max):

  182. """

  183. 最大熵模型训练,使用IIS(improved iterative scaling)迭代算法

  184. """

  185. fvec = init_feature_func_and_param(x_max_vec,y_max)

  186. iter_time=0

  187. while True:

  188. # 更新参数,返回是否收敛

  189. convergenced=update_param(x_mat,y_vec,y_max,fvec)

  190. # 计算对数似然值

  191. log_lik=log_likelihood(x_mat,y_vec,y_max,fvec)

  192. print("log_likelihood=%0.12f"%log_lik)

  193. if convergenced:

  194. break

  195. iter_time+=1

  196. if iter_time >= 100000:

  197. break

  198. # 将训练得到的模型写到文件,一行一个参数

  199. fmodel=open('./model.txt','w')

  200. for fparam in fvec:

  201. fmodel.write(str(fparam.w))

  202. fmodel.write('\n')

  203. fmodel.close()

  204. print("Max-ent train ok!")

  205. def load_model():

  206. """

  207. 加载已训练好的最大熵模型

  208. """

  209. x_mat,y_vec,x_max_vec,y_max=load_data("./zoo.train")

  210. fvec = init_feature_func_and_param(x_max_vec,y_max)

  211. fmod=open('./model.txt')

  212. i=-1

  213. for line in fmod:

  214. i+=1

  215. line=line.strip('\n')

  216. fvec[i].w=float(line)

  217. fmod.close()

  218. return fvec,y_max

  219. def max_ent_test():

  220. fvec,y_max = load_model()

  221. x_mat_test,y_vec_test,x_max_vec_test,y_max_test=load_data("./zoo.test")

  222. test_size=len(x_mat_test)

  223. ok_num=0

  224. for i in range(test_size):

  225. x_vec=x_mat_test[i]

  226. y=y_vec_test[i]

  227. most_possible_predict_y=0

  228. max_p=0.0

  229. sum_p=0.0

  230. for predict_y in range(1,y_max+1):

  231. p = max_ent_predict_unnormalized(x_vec,predict_y,fvec)

  232. sum_p += p

  233. if p > max_p:

  234. most_possible_predict_y = predict_y

  235. max_p = p

  236. if y == most_possible_predict_y:

  237. ok_num += 1

  238. p_normalized = max_p / sum_p

  239. print("y=%d predict_y=%d p=%f"%(y,most_possible_predict_y,p_normalized))

  240. print("precision-ratio=%f"%(1.0*ok_num/test_size))

  241. if __name__=="__main__":

  242. if len(sys.argv) != 2:

  243. print 'Usage: %s [train|test]'%(sys.argv[0])

  244. print 'train-data:./zoo.train'

  245. print 'test-data:./zoo.test'

  246. print 'model:./model.txt'

  247. exit()

  248. if sys.argv[1] == 'train':

  249. # 最大熵模型训练

  250. # 训练数据zoo.train,模型输出到文件model.txt

  251. x_mat,y_vec,x_max_vec,y_max=load_data("./zoo.train")

  252. max_ent_train(x_mat,y_vec,x_max_vec,y_max)

  253. if sys.argv[1] == 'test':

  254. # 最大熵模型测试

  255. max_ent_test()

原文链接:http://www.wumii.com/item/1628semfP

作者:zihua | 分类: python | 标签: python | 阅读: 2138 | 发布于: 2014-01-20 23时 |