我用朴素贝叶斯分类器写了一个能识别代码语言的小工具，但是计算联合概率的时候遇到了点问题。
polythene · 2015-05-11 13:49:02 +08:00 · 3861 次点击这是一个创建于 3475 天前的主题，其中的信息可能已经有所发展或是发生改变。
Hey all，
这是我目前的思路：
对输入的程序进行简单的词法分析
对上一步获得的每一个token进行统计，计算出给定某个token的条件下，这个程序属于某个语言的概率，即 P(lang | token)
P(lang | token) = P(token | lang) * P(lang) / P(token) n_token_on_lang(token, lang) n_lang_tokens(lang) n_token(token) = ------------------------------ * -------------------- / --------------- n_lang_tokens(lang) n_tokens() n_tokens() n_token_on_lang(token, lang) = ------------------------------ n_token(token)
获得了每一个token的概率后，计算他们的联合概率
P(lang | tok1, tok2, tok3...tokN) P(tok1, tok2, tok3...tokN | lang) * P(lang) = -------------------------------------------- P(tok1, tok2, tok3...tokN) (naively assume that tokens are independent from each other) P(tok1|lang) * P(tok2|lang) * P(tok3|lang) ... P(tokN|lang) * P(lang) = --------------------------------------------------------------------- P(tok1) * P(tok2) * P(tok3) ... P(tokN) P(tok|lang) P(lang|tok) ( ----------- = ----------- ) P(tok) P(lang) P(lang|tok1) * P(lang|tok2) * P(lang|tok3) ... P(lang|tokN) * P(lang) = --------------------------------------------------------------------- P(lang)^N
那么问题来了，通过我上面推导出来的公式计算发现，有些情况下联合概率算出来的结果是大于1的，不知道是我推导出错了，还是那个假设太naive的原因？不知道谁有相关经验，求助~~
目前简陋的实现在这里https://github.com/polyrabbit/polyglot
 |
1
liluo 2015-05-11 14:07:19 +08:00  1
|
 |
2
polythene OP @liluo 谢谢提醒，在动手写这个程序之前，我也参考过linguist(包括你的python移植版 :D)，发现它主要是基于规则的匹配，规则匹配不到的才上贝叶斯分类器，我觉得用规则来匹配的一个缺点就是前期为每种语言指定规则有点麻烦，所以才直接用贝叶斯，让机器去学习规则。
另一方面，linguist计算联合概率的方法就是把各个token的概率相乘，虽然可能对最终结果影响不大，但其实这种算法是不全面的，语言的因素他没有考虑进去，具体见我上面的推导。 |
 |
3
billlee 2015-05-11 15:15:45 +08:00
这个等式似乎有问题吧？
P(tok|lang) P(lang|tok) ----------- = --------------- P(tok) P(lang) 去分母 P(tok|lang) P(lang) = P(lang|tok) P(tok) 再化简？ P(tok) = P(lang) |
|
4
billlee 2015-05-11 15:17:22 +08:00
我想错了，上面的回复请无视吧
|
|
5
billlee 2015-05-11 15:29:20 +08:00
我觉得是 P(lang) 的问题
第2步里面的 P(lang) 应该是在样本集合中，属于语言 lang 的样本出现的概率，即 P(lang) = n_example_in_class(lang) / n_examples 而第3补里面的 P(lang) 应该是在待预测的集合中，属于语言 lang 的样本出现的概率。这个如果无法确定，可以取 P(lang = Lang1) = P(lang = Lang2) = ... = 1 / n_langs |
|
6
billlee 2015-05-11 15:46:36 +08:00 1
BTW, 在实际实现程序时，由于 P(tok1, tok2, tok3...tokN) 是与类别 lang 无关的常量，一般是直接把它扔掉的，最后的化简形式常见的是
p(lang| tok_1, tok_2, ..., tok_n) = \frac{1}{Z} p(lang) \prod_{i=0}^{n} p(tok_i | lang) 其中 Z = \frac{1}{P(tok_1, tok_2, tok_3)} 所以其实第2步本来是只要计算 P(tok_i | lang) 就可以 |
|
7
polythene OP @billlee 嗯，我目前P(lang)的计算方法就是计算属于语言 lang 的样本出现的概率，而不是平均成1 / n_langs
我把p(lang| tok_1, tok_2, ..., tok_n) 拆分到最后的一个原因就是，我希望不仅能知道哪个是最有可能的语言，我还想得到这个语言可信度是多少，现在看来，第二个目标很难实现~ |
 |
8
staticor 2015-05-11 17:13:35 +08:00
只是觉得independent的假设有点奇怪, 如果不独立从不能考虑联合分布了吧
|
|
9
polythene OP @staticor 没有这个假设的话，数据会变得非常稀疏，或者根本没法计算，但算下来发现这个假设真的好naive，不知道大家做文本分类的时候用的是什么方法。。。
|
|
10
staticor 2015-05-11 17:43:20 +08:00 1
@polythene 这个领域还真没关注过, 刚刚看了这本书 http://link.springer.com/chapter/10.1007%2F978-3-319-08979-9_39#page-1
的reference 也许会有的链接有所帮助... |
 |
11
khowarizmi 2015-05-12 00:36:04 +08:00
计算上可能是以下这点：
 )同时我对 token 之间互相独立这个假设也表示怀疑。 try 和 catch 这两个应该是显然的不独立吧。 |
|
12
polythene OP @khowarizmi 谢谢提供的参考，这个浮点数下溢出的问题我是遇到过的，也是通过去对数来解决的。
朴素贝叶斯之所以称之为朴素，正是因为这个独立性假设显得太naive，但是如果没有这个假设，在有限的训练集中 P(tok_1, tok_2, tok_3...tok_n | lang) 很难估算出来，马尔科夫假设的提出也是为了解决这个问题。大家测试了以后发现这个假设很有效，可不知道为什么到了我这里起得作用就不大了呢。。 |
|
13
staticor 2015-05-12 18:30:46 +08:00
|
Select Language