贝叶斯定理、拼写纠正、生日悖论

本周天气非常好。

一、贝叶斯定理

贝叶斯定理解决的是，在事件B已经发生的情况下，事件A发生的概率。

最重要的公式有两个:

贝叶斯公式

全概率公式

直观的解释就是，无论是事件B发生情况下，事件A发生，或者事件A发生情况下，事件B发生，其结果都是事件A和事件B同时发生了。反映到文氏图上，就是 A∩B 。

二、拼写纠正

拼写纠正是一个很常见的功能，比如把 config 拼写成 conf，软件提示输错了，并推荐正确写法。

git conf
git: 'conf' is not a git command. See 'git --help'.

Did you mean this?
	config
```    

此类问题有很多解决方法，贝叶斯是其中之一。贝叶斯方法的思路是，在输入conf的情况下，计算正确值是config或其它单词的概率是多少，并找出概率最大的单词。

其中的数学原理并不能，但是要解决两个问题：

1.寻找备选项。如果conf可能是错误的，那么如何找到与conf类似的词如confs、config、confidence等  
2.如何确认备选项的概率

对于问题1，简单的方法是通过编辑距离找出相近的单词，如增加、减少、替换、更换位置等，找到所有的备选项。

对于问题2，简单的方法是找一本英文书，分离出所有的单词，计算每个单词出现的次数。

我做了个简单的demo。首先有一个单词表的文件 `words.txt`，列出一本书中出现的所有单词。示例如下：

the
tha
the

另外用于检查拼写的文件：

package main

import (
“bufio”
“fmt”
“log”
“os”
)

var model = make(map[string]int)
var alphalet = “abcdefghijklmnopqrstuvwxyz”
//找到所有编辑距离为1的单词集合
func edit1(word string) []string {
s := make([]string, 1)
wordLen := len(word)
//add 1 word
for i := range word {
for _, c := range alphalet {
s = append(s, word[0:i]+string(c)+word[i:])
}
}

//delete 1 word
for i := range word {
    s = append(s, word[0:i]+word[i+1:])
}

//change 1 word
for i := range word {
    for _, c := range alphalet {
        s = append(s, word[0:i]+string(c)+word[i+1:])
    }
}

// change position
for i := range word[0 : wordLen-1] {
    s = append(s, word[0:i]+string(word[i+1])+string(word[i])+word[i+2:])
}

return s

}

//计算所有的候选单词
func candidates(word string) []string {
s := make([]string, 1)
s = append(s, word)
s1 := append(s, edit1(word)…)

return s1

}

//计算最优解
func calc(word string) string {
words := candidates(word)
var maxProb = 1
var correctWord = word

for _, w := range words {
    prob, prs := model[w]
    if prs == true {
        if prob > maxProb {
            maxProb = prob
            correctWord = w
        }
    }
}
return correctWord

}

func main() {
file, err := os.Open(“./words.txt”)
if err != nil {
log.Fatal(err)
}
defer file.Close()

scanner := bufio.NewScanner(file)

for scanner.Scan() {
    word := scanner.Text()
    model[word]++
}

fmt.Println(calc("tae"))
if err := scanner.Err(); err != nil {
    log.Fatal(err)
}

}

当输入 `tha` 时，会自动纠正为 `the`。

# 三、生日悖论
在23人中，有2人生日相同的概率大于50%；若有50人，则概率增至97。这可能与人们的直觉相悖，因为一年有365天，两人同天生日，通常就是人们常说的“太巧了”。

但经过[计算](https://zh.wikipedia.org/wiki/%E7%94%9F%E6%97%A5%E5%95%8F%E9%A1%8C#%E6%A6%82%E7%8E%87%E4%BC%B0%E8%AE%A1)，发现其概率要高得多。
![](/images/2018/birthday-probability.svg)


我写了一段代码来模拟一下，从1到365的数字中，随机取出2个数，算出2个数相同的概率。

package main
import “fmt”
import “time”
import “math/rand”

//return a random number of 1~365
func generateBirth() int{
rand.Seed(time.Now().UnixNano())
return 1+rand.Intn(364)
}

//check if at least 2 persons have same birthday
func checkSameBirthDay(num int) bool{
brithDays := make(map[int]int)
for i:=0;i<num;i++{
day := generateBirth()
brithDays[day]++
if(brithDays[day] >1){
return true
}
}
return false
}

func main(){
personNum := 50
loopNum := 10000
sameNum := 0
for i:=0;i<loopNum;i++{
if true == checkSameBirthDay(personNum){
sameNum++
}
}
fmt.Printf(“The probability of same birthday in %d persons is %f\n”,personNum,float64(sameNum)/float64(loopNum))
}

当人数为50人，结果如下：

go run birthday.go
The probability of same birthday in 50 persons is 0.973000

与计算的值相差无几。
# 四、参考链接
[贝叶斯推断及其互联网应用（一）：定理简介](http://www.ruanyifeng.com/blog/2011/08/bayesian_inference_part_one.html)  

[哈希碰撞与生日攻击](http://www.ruanyifeng.com/blog/2018/09/hash-collision-and-birthday-attack.html)

[维基百科：生日问题](https://zh.wikipedia.org/wiki/%E7%94%9F%E6%97%A5%E5%95%8F%E9%A1%8C)

[
朴素贝叶斯案例2：拼写纠错（python实现）](https://blog.csdn.net/PbGc396Dwxjb77F2je/article/details/78786980)