Notes on Text Mining and Analytics - 2

Syntagmatic Relation Discovery: Entropy

  • 组合关系(syntagmatic relations):

    \[Syntagmatic Relation = Correlated Occurrences\]
  • 在信息论与概率统计中,熵(entropy)是量化一个变量的随机程度(熵一般情况下是非负的),表示随机变量不确定性的度量。

  • Entropy H(X) Measures Randomness of X, H(X)是对称函数(symetric function)

H(X) Measures Randomness of X

H(X) Measures Randomness of X

那么哪种情况下熵更高呢? - 类似的:Entropy H(X): Coin Tossing 抛硬币有两种结果,正面(head)或者反面(tail), 我们定义一个随机变量X(coin)。假设理想情况下,有一个完美的硬币(completely fair coin), 硬币正面朝上和反面朝上的概率相等 p(X=0) = p(X=1) = 1/2。那么,再考虑另外一种极端情况(completely biased),假如硬币永远正面朝上,即p(X=1) = 1。那么这两种情况的熵各自是怎样呢? - Conclusion: 熵高的words更难预测(High entropy words are harder to predict)

Syntagmatic Relation Discovery: Conditional Entropy

  • 条件熵H(X|Y),表示在已知随机变量Y的条件下随机变量X的不确定性,定义为Y在给定条件下X的条件概率分布的熵对Y的数学期望(若有0概率,定义 0log0 = 0)。在《统计学习方法》[1]中,5.22章节对熵和条件熵也有详细描述。 Conditional Entropy: Complete Definition

  • In general, for any discrete random variables X and Y, we have H(X) >= H(X|Y)

  • 对于

    \[H(X_{w}|X_{meat})\]

    当w = meat时,相当于均已知,条件熵为0,得到条件熵的最小值;假设the是与meat关系最不密切的,那么w = the时,条件熵达到最大值,这是最不容易预测meat的情况。(个人理解,这似乎可以看做一种极限?eat处于meat和the之间)

  • Conclusion: 一般来说,熵越小,越容易做预测。

  • H(Xw1|Xw2) 和 H(Xw1|Xw3) 是可比较的, H(Xw1|Xw2) 和 H(Xw3|Xw2) 是不可比较的。因为对于不同的Xw,有不同的upper bound,所以不可比较

Syntagmatic Relation Discovery: Mutual Information

I(X; Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) 互信息(Mutual information): 由于已知X(或Y)带来的Y(或X)的熵损失,用来衡量两个随机分布的差距。强相关的词,I(X; Y)会更大;反之会更小。 - 互信息性质: - 非负: I(X; Y) >= 0 - 对称性: I(X; Y) = I(Y; X) - I(X; Y) = 0: iif(if and only if)当且仅当X和Y相互独立

  • 怎样衡量MI? 用KL散度计算互信息 KL(Kullback-Leible) divergence,用作相似性度量 Rewriting Mutual Information (MI) Using KL-divergence
  • 语料中没有出现过某个词,可能出现0概率的词,解决方法:Smoothing > 进行数据平滑,为这些在训练语料中没有出现过的词分配一些概率,使其不为0,且最后的概率和为1。
  • 总结:互信息(MI) 对于发掘语义关联非常有用。MI可以对不同的可比较的两个词取值,所以我们可以根据值对这些成对的词进行排序,从而发掘他们中的语义关联。

Topic Mining and Analysis: Motivation and Task Definition

Probabilistic Topic Models: Overview of Statistical Language Models

两种estimating parameters的方法:

  1. 极大似然估计 maximum likelihood
  2. Bayesian

Reference

[1] 李航. “统计学习方法.” 清华大学出版社, 北京 (2012). <br>[2] Chris Manning and Hinrich Schütze, Foundations of Statistical Natural Language Processing, MIT Press. Cambridge, MA: May 1999. (Chapter 5 on collocations) <br>[3] Chengxiang Zhai, Exploiting context to identify lexical atoms: A statistical view of linguistic context. Proceedings of the International and Interdisciplinary Conference on Modelling and Using Context (CONTEXT-97), Rio de Janeiro, Brzil, Feb. 4-6, 1997. pp. 119-129. <br>[4] Shan Jiang and ChengXiang Zhai, Random walks on adjacency graphs for mining lexical relations from big text data. Proceedings of IEEE BigDataConference 2014, pp. 549-554.