姓名:唐來賓? 學號:17101223417
轉載
http://mp.weixin.qq.com/s/bATbcnF-SO-sYClgNLHngw
【嵌牛鼻子】拼音輸入，隱馬爾可夫模型
【嵌牛導讀】隱馬爾可夫模型 (Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程焚刺。其難點是從可觀察的參數中確定該過程的隱含參數，然后利用這些參數來作進一步的分析稠歉。拼音輸入法中可觀察的參數就是拼音名惩，隱含的參數就是對應的漢字碟摆。
【嵌牛提問】如何學好算法述暂？
【嵌牛正文】在網上看到一篇關于隱馬爾科夫模型的介紹痹升，覺得簡直不能再神奇，又在網上找到大神的一篇關于如何用隱馬爾可夫模型實現中文拼音輸入的博客（http://sobuhu.com/ml/2013/03/07/hmm-pinyin-input-method.html）畦韭，無奈大神沒給可以運行的代碼视卢，只能純手動網上找到了結巴分詞的詞庫，根據此訓練得出隱馬爾科夫模型廊驼，用維特比算法實現了一個簡單的拼音輸入法据过。githuh地址：https://github.com/LiuRoy/Pinyin_Demo
原理簡介
隱馬爾科夫模型
抄一段網上的定義：
隱馬爾可夫模型 (Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程妒挎。其難點是從可觀察的參數中確定該過程的隱含參數绳锅，然后利用這些參數來作進一步的分析。
拼音輸入法中可觀察的參數就是拼音酝掩，隱含的參數就是對應的漢字鳞芙。
viterbi算法
參考 https://zh.wikipedia.org/wiki/維特比算法，思想是動態(tài)規(guī)劃期虾，代碼比較簡單就不贅述原朝。
代碼解釋
model定義
代碼見model/table.py文件，針對隱馬爾科夫的三個概率矩陣镶苞，分別設計了三個數據表存儲喳坠。這樣的好處很明顯，漢字的轉移概率矩陣是一個非常大的稀疏矩陣茂蚓，直接文件存儲占用空間很大壕鹉，并且加載的時候也只能一次性讀入內存，不僅內存占用高而且加載速度慢聋涨。此外數據庫的join操作非常方便viterbi算法中的概率計算晾浴。
數據表定義如下：
class Transition(BaseModel):
? ? __tablename__ = 'transition'
? ? id = Column(Integer, primary_key=True)
? ? previous = Column(String(1), nullable=False)
? ? behind = Column(String(1), nullable=False)
? ? probability = Column(Float, nullable=False)
class Emission(BaseModel):
? ? __tablename__ = 'emission'
? ? id = Column(Integer, primary_key=True)
? ? character = Column(String(1), nullable=False)
? ? pinyin = Column(String(7), nullable=False)
? ? probability = Column(Float, nullable=False)
class Starting(BaseModel):
? ? __tablename__ = 'starting'
? ? id = Column(Integer, primary_key=True)
? ? character = Column(String(1), nullable=False)
? ? probability = Column(Float, nullable=False)
模型生成
代碼見train/main.py文件，里面的initstarting牍白，initemission脊凰，init_transition分別對應于生成隱馬爾科夫模型中的初始概率矩陣，發(fā)射概率矩陣茂腥，轉移概率矩陣狸涌，并把生成的結果寫入sqlite文件中。訓練用到的數據集是結巴分詞里的詞庫础芍，因為沒有訓練長句子杈抢，最后運行的結果也證明只能適用于短句輸入数尿。
初始概率矩陣
統計初始化概率矩陣仑性，就是找出所有出現在詞首的漢字，并統計它們出現在詞首的次數右蹦，最后根據上述數據算出這些漢字出現在詞首的概率诊杆，沒統計的漢字就認為出現在詞首的概率是0歼捐，不寫入數據庫。有一點注意的是為了防止概率計算的時候因為越算越小導致計算機無法比較晨汹，所有的概率都進行了自然對數運算豹储。統計的結果如下：
轉移概率矩陣
此處用到的是最簡單的一階隱馬爾科夫模型，即認為在一個句子里淘这，每個漢字的出現只和它前面的的一個漢字有關剥扣，雖然簡單粗暴，但已經可以滿足大部分情況铝穷。統計的過程就是找出字典中每個漢字后面出現的漢字集合钠怯，并統計概率。因為這個概率矩陣非常的大曙聂，逐條數據寫入數據庫過慢晦炊，后續(xù)可以優(yōu)化為批量寫入，提高訓練效率宁脊。結果如下：
上圖展示的一后面出現概率最高的十個字断国，也挺符合日常習慣。
發(fā)射概率矩陣
通俗點就是統計每個漢字對應的拼音以及在日常情況下的使用概率榆苞，已暴舉例稳衬，它有兩個讀音：bao和pu，難點就是找bao和pu出現的概率坐漏。此處統計用到了pypinyin模塊宋彼，把字典中的短語轉換為拼音后進行概率統計，但是某些地方讀音也不完全正確仙畦，最后運行的輸入法會出現和拼音不匹配的結果输涕。統計結果如下：
viterbi實現
代碼建input_method/viterbi.py文件，此處會找到最多十個局部最優(yōu)解慨畸，注意是十個局部最優(yōu)解而不是十個全局最優(yōu)解莱坎，但是這十個解中最優(yōu)的那個是全局最優(yōu)解，代碼如下：
def viterbi(pinyin_list):
? ? """
? ? viterbi算法實現輸入法
? ? Aargs:
? ? ? ? pinyin_list (list): 拼音列表
? ? """
? ? start_char = Emission.join_starting(pinyin_list[0])
? ? V = {char: prob for char, prob in start_char}
? ? for i in range(1, len(pinyin_list)):
? ? ? ? pinyin = pinyin_list[i]
? ? ? ? prob_map = {}
? ? ? ? for phrase, prob in V.iteritems():
? ? ? ? ? ? character = phrase[-1]
? ? ? ? ? ? result = Transition.join_emission(pinyin, character)
? ? ? ? ? ? if not result:
? ? ? ? ? ? ? ? continue
? ? ? ? ? ? state, new_prob = result
? ? ? ? ? ? prob_map[phrase + state] = new_prob + prob
? ? ? ? if prob_map:
? ? ? ? ? ? V = prob_map
? ? ? ? else:
? ? ? ? ? ? return V
? ? return V
結果展示
運行input_method/viterbi.py文件寸士，簡單的展示一下運行結果：
問題統計：
統計字典生成轉移矩陣寫入數據庫的速度太慢檐什，運行一次要將近十分鐘。
發(fā)射概率矩陣數據不準確弱卡，總有一些漢字的拼音不匹配乃正。
訓練集太小，實現的輸入法不適用于長句子婶博。
