[关闭]
@knight 2016-06-03T09:34:14.000000Z 字数 1823 阅读 1046

Good-Truing估计法

NLP


古德-图灵的基本思路是:对于任何一个出现了r次的n元语法,都假设它出现了次,这里有:

其中,是训练语料中恰好出现r次的n元语法的数目。把这个统计计数转化为概率,需要归一化处理,对于统计计数为r的n元语法,其概率为:

其中:

也就是说这个N等于这个分布中最初的计数。这样,样本中所有事件的概率之和为:

因此,有的概率剩余量可以分配给所有未出现事件(r=0)

  1. # snownlp 中good-turing实现
  2. # -*- coding: utf-8 -*-
  3. from __future__ import print_function
  4. from __future__ import division
  5. from math import log, exp
  6. def getz(r, nr):
  7. z = [2*nr[0]/r[1]]
  8. for i in xrange(len(nr)-2):
  9. z.append(2*nr[i+1]/(r[i+2]-r[i]))
  10. z.append(nr[-1]/(r[-1]-r[-2]))
  11. return z
  12. def least_square(x, y): # y=a+bx
  13. meanx = sum(x)/len(x)
  14. meany = sum(y)/len(y)
  15. xy = sum((x[i]-meanx)*(y[i]-meany) for i in range(len(x)))
  16. square = sum((x[i]-meanx)**2 for i in range(len(x)))
  17. b = xy/square
  18. return (meany-b*meanx, b)
  19. def main(dic):
  20. values = sorted(dic.values())
  21. r, nr, prob = [], [], []
  22. for v in values:
  23. if not r or r[-1] != v:
  24. r.append(v)
  25. nr.append(1)
  26. else:
  27. nr[-1] += 1
  28. rr = dict(map(lambda x:list(reversed(x)), enumerate(r)))
  29. total = reduce(lambda x, y:(x[0]*x[1]+y[0]*y[1], 1), zip(nr, r))[0]
  30. z = getz(r, nr)
  31. a, b = least_square(map(lambda x:log(x), r), map(lambda x:log(x), z))
  32. use_good_turing = False
  33. nr.append(exp(a+b*log(r[-1]+1)))
  34. for i in xrange(len(r)):
  35. good_turing = (r[i]+1)*(exp(b*(log(r[i]+1)-log(r[i]))))
  36. turing = (r[i]+1)*nr[i+1]/nr[i] if i+1<len(r) else good_turing
  37. diff = ((((r[i]+1)**2)/nr[i]*nr[i+1]/nr[i]*(1+nr[i+1]/nr[i]))**0.5)*1.65
  38. if not use_good_turing and abs(good_turing-turing)>diff:
  39. prob.append(turing)
  40. else:
  41. use_good_turing = True
  42. prob.append(good_turing)
  43. sump = reduce(lambda x, y:(x[0]*x[1]+y[0]*y[1], 1), zip(nr, prob))[0]
  44. for cnt, i in enumerate(prob):
  45. prob[cnt] = (1-nr[0]/total)*i/sump
  46. return nr[0]/total/total, dict(zip(dic.keys(), map(lambda x:prob[rr[x]], dic.values())))
  47. if __name__ == '__main__':
  48. print(main({1:1,2:1,3:1,4:2,5:2,6:3,7:1,8:2,9:3}))
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注