正文之前
這周二開博士沙龍,大老板對我想做的方向养篓,很感興趣秃流。。我他么有點害怕柳弄,聽同組師兄的女朋友舶胀,也是一個大老板門下的師姐說,在他們那一次博士沙龍碧注,大老板對我大加褒獎嚣伐,不吝溢美之詞,讓我更害怕了萍丐。這是一份沉甸甸的壓力纤控,我自覺我還是個小菜雞,還不至于成為大老板手上的小紅人碉纺,所以我怕自己讓大老板失望船万,那樣就不好了刻撒。不過既然都這樣了,那就好好學吧耿导。對吧声怔,大老板還推薦大家都來看看《漢字》 這個紀錄片。舱呻。也就是他想讓我做的方向的一個很好地啟蒙片醋火。。箱吕。我就推薦下吧
正文
最近讀了一個博客芥驳,里面簡述了一些中文分詞算法,現(xiàn)在正在深入研究維特比算法茬高,鏈接如下 兆旬,有興趣的朋友可以去看看全文:
具體的內容不多說,下面就簡單講下我對這里面的Viterbi算法的理解怎栽。
首先需要介紹下隱馬爾科夫模型(Hidden Markov Model丽猬,HMM):
HMM包含如下的五元組:
狀態(tài)值集合Q={q1,q2,...,qN},其中N為可能的狀態(tài)數熏瞄;在本文的例子中脚祟,就是漢字有可能的四個狀態(tài)(B,M,E,S),分別表示詞的開始强饮、結束由桌、中間(begin、end邮丰、middle)及字符獨立成詞(single)
觀測值集合V={v1,v2,...,vM}沥寥,其中M為可能的觀測數;觀測值就是文本中的字咯柠座;
轉移概率矩陣A=[aij]邑雅,其中aij表示從狀態(tài)i轉移到狀態(tài)j的概率;這個在本中文是指從一個狀態(tài)轉移到另一個狀態(tài)的概率妈经;
發(fā)射概率矩陣(也稱之為觀測概率矩陣)B=[bj(k)]淮野,其中bj(k)表示在狀態(tài)j的條件下生成觀測vk的概率;本文中指一個字在某一狀態(tài)的可能性吹泡。這個是先驗的(就是說通過統(tǒng)計方法得到的)
初始狀態(tài)分布π.(初始值骤星,內部給定)
一般地,將HMM表示為模型λ=(A,B,π)爆哑,狀態(tài)序列為I洞难,對應測觀測序列為O。對于這三個基本參數揭朝,HMM有三個基本問題:
概率計算問題队贱,在模型λ下觀測序列O出現(xiàn)的概率色冀;
學習問題,已知觀測序列O柱嫌,估計模型λ的參數锋恬,使得在該模型下觀測序列P(O|λ)最大;
解碼(decoding)問題编丘,已知模型λ與觀測序列O与学,求解條件概率P(I|O)最大的狀態(tài)序列I。
更詳細的嘉抓,簡潔的說法請參見wiki吧索守,or有個博客講的也還算清晰,主要看以天氣和治病為例子的那些真實世界映射抑片,骰子那個不是那么好理解wiki百科關于維特比和 ||||||||||||| 一文搞懂HMM(隱馬爾可夫模型) |||||||||||||
想象一個鄉(xiāng)村診所卵佛。村民有著非常理想化的特性,要么健康要么發(fā)燒蓝丙。他們只有問診所的醫(yī)生的才能知道是否發(fā)燒。 聰明的醫(yī)生通過詢問病人的感覺診斷他們是否發(fā)燒望拖。村民只回答他們感覺正常渺尘、頭暈或冷。
假設一個病人每天來到診所并告訴醫(yī)生他的感覺说敏。醫(yī)生相信病人的健康狀況如同一個離散馬爾可夫鏈鸥跟。病人的狀態(tài)有兩種“健康”和“發(fā)燒”,但醫(yī)生不能直接觀察到盔沫,這意味著狀態(tài)對他是“隱含”的医咨。每天病人會告訴醫(yī)生自己有以下幾種由他的健康狀態(tài)決定的感覺的一種:正常、冷或頭暈架诞。這些是觀察結果拟淮。 整個系統(tǒng)為一個隱馬爾可夫模型(HMM)。
醫(yī)生知道村民的總體健康狀況谴忧,還知道發(fā)燒和沒發(fā)燒的病人通常會抱怨什么癥狀很泊。 換句話說,醫(yī)生知道隱馬爾可夫模型的參數沾谓。 這可以用Python語言表示如下:
states = ('Healthy', 'Fever')
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
transition_probability = {
'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
'Fever' : {'Healthy': 0.4, 'Fever': 0.6},
}
emission_probability = {
'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
上面關于HMM的敘述大部分來自原文委造,所以大家可以去看原文,結合我的看就好了
如何從HMM模型到維特比算法均驶,還請大家移步原文看昏兆,我就不多贅述,還是上代碼加注釋會比較好妇穴,畢竟我主要的工作就是加了一些注釋爬虱。
# -*- coding: utf-8 -*-
'''
start:初始概率分布隶债,大概就是第一個字的狀態(tài)的概率吧
tran :狀態(tài)轉移概率,從當前狀態(tài)到下一個狀態(tài)的轉移的概率饮潦,
emit :發(fā)射概率燃异,表示在某一狀態(tài)下生成某個觀測狀態(tài)(在這一狀態(tài)下,這個字是這個狀態(tài))的概率
'''
import sys
import re
import getopt
MIN_FLOAT = -3.14e100
PROB_START_P = "prob_start.p"
PROB_TRANS_P = "prob_trans.p"
PROB_EMIT_P = "prob_emit.p"
#某一個詞的狀態(tài)為key時继蜡,prevStatus表示前一個詞的狀態(tài)的框定范圍
PrevStatus = {
'B': 'ES',
'M': 'MB',
'S': 'SE',
'E': 'BM'
}
Force_Split_Words = set([])
from prob_start import P as start_P
from prob_trans import P as trans_P
from prob_emit import P as emit_P
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}] # tabular
path = {}
for y in states: # init 獲取這一句子的初始狀態(tài)分布
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
path[y] = [y]
# 對之后的每一個字做狀態(tài)轉移概率的分析
for t in range(1, len(obs)):
V.append({})
newpath = {}
# 考察當前字回俐,對于上一個字的發(fā)射概率,取其中最大的那個
for y in states:
#獲取當前詞在y狀態(tài)下的發(fā)射概率
em_p = emit_p[y].get(obs[t], MIN_FLOAT)
# y狀態(tài)在prevStatus的限定后稀并,前一個詞的限定范圍內某一狀態(tài)y0的概率 + y0對當前字的y狀態(tài)的轉移概率 + 當前詞在y狀態(tài)下的發(fā)射概率(其實就是這個詞是某個狀態(tài)的概率的意思)
# state表示前一個字到當前字的y狀態(tài)的最大概率仅颇,prob表示這個概率。
(prob, state) = max(
[
(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0)
for y0 in PrevStatus[y]
]
)
#得到了當前字的所有可能觀測狀態(tài)的最大概率值
V[t][y] = prob
# 更新路徑碘举,state表示當前字的前一個字到當前字的y狀態(tài)的最大可能概率忘瓦,所以是path[state],因為要取前一個字的最大概率路徑
newpath[y] = path[state] + [y]
path = newpath
# 最后一個要重新復盤,因為最后一個字只能是E or S
(prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')
for i in path:
print((i,path[i]))
for v in V:
print((v))
return (prob, path[state])
def __cut(sentence):
prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)
begin, nexti = 0, 0
# print pos_list, sentence
for i, char in enumerate(sentence):
pos = pos_list[i]
if pos == 'B':
begin = i
elif pos == 'E':
yield sentence[begin:i + 1]
nexti = i + 1
elif pos == 'S':
yield char
nexti = i + 1
if nexti < len(sentence):
yield sentence[nexti:]
re_han = re.compile("([\u4E00-\u9FD5]+)")
re_skip = re.compile("([a-zA-Z0-9]+(?:\.\d+)?%?)")
def cut(sentence):
sentence = sentence.strip().decode('utf-8')
blocks = re_han.split(sentence)
lseg = []
for blk in blocks:
if re_han.match(blk):
for word in __cut(blk):
if word not in Force_Split_Words:
lseg.append(word)
else:
for c in word:
lseg.append(c)
else:
tmp = re_skip.split(blk)
for x in tmp:
if x:
lseg.append(x)
return lseg
if __name__ == "__main__":
ifile = 'input.txt'
ofile = 'seg.txt'
# try:
# opts, args = getopt.getopt(sys.argv[1:], "hi:o:", ["ifile=", "ofile="])
# except getopt.GetoptError:
# print('seg_hmm.py -i <inputfile> -o <outputfile>')
# sys.exit(2)
# for opt, arg in opts:
# if opt == '-h':
# print('seg_hmm.py -i <inputfile> -o <outputfile>')
# sys.exit()
# elif opt in ("-i", "--ifile"):
# ifile = arg
# elif opt in ("-o", "--ofile"):
# ofile = arg
with open(ifile, 'rb') as inf:
for line in inf:
rs = cut(line)
print(' '.join(rs))
with open(ofile, 'a',encoding='utf8') as outf:
outf.write(' '.join(rs) + "\n")
OK引颈,該說的都在代碼上了耕皮,想要我細細道來也別想了。蝙场。麻煩凌停,好人做到底,我再附個圖,這下應該簡單明了了:
----------圖片上傳不了售滤。罚拟。。---------去下面看吧----------
圖片來源知乎:如何通俗地講解 viterbi 算法完箩?
正文之后
OK赐俗,溜了,在代碼中還學習到了yield和enumerate的用法弊知,開心`