2020年8月3日

中文斷詞

在中文自然語言處理NLP中,要對一堆文字詞語組成的文章進行分析, 分析前要先拆解文章,也就是斷詞,我們要分析的對象是詞語,而不是一個一個中文字,這跟英文完全不同,因為英文的斷詞就直接用標點符號、空白去區隔即可。

目前繁體中文斷詞系統有 中研院 CKIP 以及 jieba,在一些舊的文章中都提到 jieba 無法適當地處理繁體中文,而有替換繁體中文字典的改進作法,不過目前 jieba 已經到了 0.42 版,以下先了解官方的套件的功能,再看看需不需要修改繁體中文字典。

jieba 演算法

  • 基於前綴詞典實現高效的詞圖掃描,生成句子中漢字所有可能成詞情況所構成的有向無環圖 (DAG)
  • 採用了動態規劃查找最大概率路徑,找出基於詞頻的最大切分組合
  • 對於未登錄詞,採用了基於漢字成詞能力的 HMM 模型,使用了 Viterbi 算法

安裝

可直接用 pip 安裝,或是將 jieba source code 的 jieba 目錄放在目前的工作目錄,或是 site-packages 目錄中

如果要使用 paddle 的分詞語詞性標注功能,必須安裝 paddlepaddle-tiny

pip3 install paddlepaddle-tiny==1.6.1

先直接下載 source code 試試看

wget https://github.com/fxsjy/jieba/archive/v0.42.1.tar.gz -O jieba-0.41.1.tgz

tar zxvf jieba-0.41.1.tgz

virtual environemnt

virtualenv --system-site-packages /root/venv-jieba
source /root/venv-jieba/bin/activate

## 如果不使用 paddlepaddle,這兩個套件也可以不安裝
pip3 install numpy==1.16.4
pip3 install paddlepaddle-tiny==1.6.1

# 把 soruce code 中的 jieba 目錄移動到工作目錄中
mv ~/temp/download/jieba-0.41.1/jieba ~/temp

斷詞

有四種斷詞模式

  • 精確模式,試圖將句子最精確地切開,適合文本分析
  • 完整模式,把句子中所有的可以成詞的詞語都掃描出來, 速度非常快,但是不能解決歧義;
  • 搜索引擎模式,在精確模式的基礎上,對長詞再次切分,提高召回率,適合用於搜索引擎分詞。
  • paddle模式,利用PaddlePaddle深度學習框架,訓練序列標注(雙向GRU)網絡模型實現分詞。同時支持詞性標注。paddle模式使用需安裝 paddlepaddle-tiny

函式

  • jieba.cut 方法接受四個輸入參數: 需要分詞的字符串;cutall 參數用來控制是否採用全模式;HMM 參數用來控制是否使用 HMM 模型;usepaddle 參數用來控制是否使用paddle模式下的分詞模式,paddle模式採用延遲加載方式,通過enable_paddle接口安裝paddlepaddle-tiny,並且import相關代碼
  • jieba.cutforsearch 方法接受兩個參數:需要分詞的字符串;是否使用 HMM 模型。該方法適合用於搜索引擎構建倒排索引的分詞,粒度比較細
  • 待分詞的字符串可以是 unicode 或 UTF-8 字符串、GBK 字符串。注意:不建議直接輸入 GBK 字符串,可能無法預料地錯誤解碼成 UTF-8
  • jieba.cut 以及 jieba.cutforsearch 返回的結構都是一個可迭代的 generator,可以使用 for 循環來獲得分詞後得到的每一個詞語(unicode),或者用 jieba.lcut 以及 jieba.lcutforsearch 直接返回 list
  • jieba.Tokenizer(dictionary=DEFAULT_DICT) 新建自定義分詞器,可用於同時使用不同詞典。jieba.dt 為默認分詞器,所有全局分詞相關函數都是該分詞器的映射。

# encoding=utf-8
import jieba

print()
print("完整模式:")
seg_list = jieba.cut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。", cut_all=True)
print("Full Mode: " + "/ ".join(seg_list))  # 全模式

print()
print("精確模式:")
seg_list = jieba.cut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。", cut_all=False)
print("Default Mode: " + "/ ".join(seg_list))  # 精確模式

print()
print("預設是精確模式:")
seg_list = jieba.cut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。")  # 預設是精確模式
print(", ".join(seg_list))

print()
print("搜索引擎模式:")
seg_list = jieba.cut_for_search("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。")  #
print(", ".join(seg_list))

print()
print("Paddle Mode:")
jieba.enable_paddle()# 啓動paddle模式。 0.40版之後開始支持,早期版本不支持
strs=["肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。","乒乓球拍賣完了","新竹清華大學"]
for str in strs:
    seg_list = jieba.cut(str,use_paddle=True) # 使用paddle模式
    print("Paddle Mode: " + '/'.join(list(seg_list)))

執行結果

完整模式:
Building prefix dict from the default dictionary ...
Loading model from cache /tmp/jieba.cache
Loading model cost 0.433 seconds.
Prefix dict has been built successfully.
Full Mode: 肺炎/ 疫情/ 的/ 挑/ 戰/ 日益/ 嚴/ 峻/ ,/ 新竹/ 清/ 華/ 大/ 學/ 自/ 農/ 曆/ 年/ 起/ 陸/ 續/ 已/ 採/ 取/ 了/ 量/ 測/ 體/ 溫/ 等/ 全面/ 的/ 防疫/ 措施/ 。

精確模式:
Default Mode: 肺炎/ 疫情/ 的/ 挑戰/ 日益/ 嚴峻/ ,/ 新竹/ 清華大學/ 自農/ 曆/ 年/ 起/ 陸續/ 已/ 採取/ 了/ 量/ 測體/ 溫/ 等/ 全面/ 的/ 防疫/ 措施/ 。

預設是精確模式:
肺炎, 疫情, 的, 挑戰, 日益, 嚴峻, ,, 新竹, 清華大學, 自農, 曆, 年, 起, 陸續, 已, 採取, 了, 量, 測體, 溫, 等, 全面, 的, 防疫, 措施, 。

搜索引擎模式:
肺炎, 疫情, 的, 挑戰, 日益, 嚴峻, ,, 新竹, 清華大學, 自農, 曆, 年, 起, 陸續, 已, 採取, 了, 量, 測體, 溫, 等, 全面, 的, 防疫, 措施, 。

Paddle Mode:
W0327 11:45:31.179752 21561 init.cc:157] AVX is available, Please re-compile on local machine
Paddle enabled successfully......
Paddle Mode: 肺炎/疫情/的/挑戰/日益/嚴/峻,新竹清華大學自農曆年起陸續/已/採取/了/量測體溫/等/全面/的/防疫/措施/。
Paddle Mode: 乒乓/球拍/賣/完/了
Paddle Mode: 新竹/清華大學
  • jieba.lcut() lcut(),意思跟cut()是一樣的,只是返回的型態變成list

# encoding=utf-8
import jieba

print()
print("完整模式:")
seg_list = jieba.lcut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。", cut_all=True)
print("Full Mode: ", seg_list)  # 全模式


print()
print("精確模式:")
seg_list = jieba.lcut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。", cut_all=False)
print("Default Mode: ", seg_list)  # 精確模式

print()
print("預設是精確模式:")
seg_list = jieba.lcut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。")  # 預設是精確模式
print(seg_list)

print()
print("搜索引擎模式:")
seg_list = jieba.lcut_for_search("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。")  #
print(seg_list)

print()
print("Paddle Mode:")
jieba.enable_paddle()# 啓動paddle模式。 0.40版之後開始支持,早期版本不支持
strs=["肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。","乒乓球拍賣完了","新竹清華大學"]
for str in strs:
    seg_list = jieba.lcut(str,use_paddle=True) # 使用paddle模式
    print("Paddle Mode: ", seg_list)

自訂詞典

  • 雖然 jieba 有新詞識別能力,但是自行添加新詞可以保證更高的正確率

  • 用法: jieba.loaduserdict(filename)

    file_name 為文件類對象或自定義詞典的路徑

  • 詞典格式和 dict.txt 一樣,一個詞佔一行;每一行分三部分:詞語、詞頻(可省略)、詞性(可省略),用空格隔開,順序不可顛倒。file_name 若為路徑或二進制方式打開的文件,則文件必須為 UTF-8 編碼。

  • 詞頻省略時使用自動計算的方式處理,能保證分出該詞的詞頻。

  • 使用 addword(word, freq=None, tag=None) 和 delword(word) 可在程序中動態修改詞典。

  • 使用 suggest_freq(segment, tune=True) 可調節單個詞語的詞頻,使其能(或不能)被分出來。

  • 注意:自動計算的詞頻在使用 HMM 新詞發現功能時可能無效。

在專案路徑下新增一個檔案叫做:userdict.txt

內容如下:

農曆年
量測
體溫
日益嚴峻

可在程式一開始,就載入自訂詞典

jieba.load_userdict('userdict.txt')

執行結果

精確模式:
Default Mode:  ['肺炎', '疫情', '的', '挑戰', '日益嚴峻', ',', '新竹', '清華大學', '自', '農曆年', '起陸續', '已', '採取', '了', '量測', '體溫', '等', '全面', '的', '防疫', '措施', '。']

可動態調整詞語的頻率

jieba.suggest_freq(('陸續'), True)
print()
print("精確模式2:")
seg_list = jieba.lcut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。", cut_all=False)
print("Default Mode: ", seg_list)  # 精確模式

執行結果

精確模式2:
Default Mode:  ['肺炎', '疫情', '的', '挑戰', '日益嚴峻', ',', '新竹', '清華大學', '自', '農曆年', '起', '陸續', '已', '採取', '了', '量測', '體溫', '等', '全面', '的', '防疫', '措施', '。']

也可以直接替換詞典

ithomeironman/day16NLP_Chinese/ 可下載一個繁體中文的字典 dict.txt.big

# encoding=utf-8
import jieba

jieba.set_dictionary('dict.txt.big')
# with open('stops.txt', 'r', encoding='utf8') as f:
#     stops = f.read().split('\n')

print()
print("精確模式:")
seg_list = jieba.lcut("肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。", cut_all=False)
print("Default Mode: ", seg_list)

關鍵詞抽取

TF-IDF 方法

# jieba.analyse.extract_tags(sentence, topK=20, withWeight=False, allowPOS=())
# sentence 為待提取的文本
# topK 為返回幾個 TF/IDF 權重最大的關鍵詞,默認值為 20
# withWeight 為是否一並返回關鍵詞權重值,默認值為 False
# allowPOS 僅包括指定詞性的詞,默認值為空,即不篩選
# jieba.analyse.TFIDF(idf_path=None) 新建 TFIDF 實例,idf_path 為 IDF 頻率文件

TextRank 方法

jieba.analyse.textrank(sentence, topK=20, withWeight=False, allowPOS=('ns', 'n', 'vn', 'v')) 直接使用,接口相同,注意默認過濾詞性。
jieba.analyse.TextRank() 新建自定義 TextRank 實例
# -*- coding: utf-8 -*-
import jieba
import jieba.analyse

jieba.set_dictionary('dict.txt.big')

print()
text = '肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。'
tags = jieba.analyse.extract_tags(text, topK=10)
print(tags)
# ['挑戰', '嚴峻', '清華大學', '農曆年', '陸續', '採取', '測體溫', '防疫', '新竹', '肺炎']

print()
print('textrank:')
for x, w in jieba.analyse.textrank(text, withWeight=True):
    print('%s %s' % (x, w))

# textrank:
# 日益 1.0
# 全面 1.0
# 肺炎 0.6631715416020616
# 防疫 0.6631715416020616
# 疫情 0.6605033585768562
# 措施 0.6605033585768562
# 新竹 0.3607120276929184
# 了量 0.3607120276929184

詞性標注

ref: 彙整中文與英文的詞性標註代號:結巴斷詞器與FastTag / Identify the Part of Speech in Chinese and English

結巴預設會將標點符號標示為「x」,而不是「w」。而且英文會被標示為「eng」

# -*- coding: utf-8 -*-
import jieba
import jieba.posseg as pseg

text = '肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。'
seg_list = pseg.lcut(text)
# print("Default Mode: ", seg_list)

for word, flag in seg_list:
    print("", word, " : ", flag)

執行結果

 肺炎  :  n
 疫情  :  n
 的  :  uj
 挑戰  :  vn
 日益  :  n
 嚴峻  :  a
 ,  :  x
 新竹  :  ns
 清華大學  :  nt
 自  :  p
 農  :  ng
 曆  :  zg
 年  :  q
 起  :  v
 陸  :  nr
 續  :  v
 已  :  d
 採  :  v
 取  :  v
 了  :  ul
 量  :  n
 測  :  v
 體  :  ng
 溫  :  v
 等  :  u
 全面  :  n
 的  :  uj
 防疫  :  vn
 措施  :  n
 。  :  x

word cloud

參考這篇文章中文自然語言處理基礎 以及資源

下載檔案:

cloud_mask7.png
sumsun.ttf
stops.txt

安裝其它套件

pip3 install collections
pip3 install wordcloud
pip3 install matplotlib
yum -y install python-imaging
import jieba
jieba.set_dictionary('dict.txt.big')  # 如果是使用繁體文字,請記得去下載繁體字典來使用
with open('stops.txt', 'r', encoding='utf8') as f:
    stops = f.read().split('\n')

text = "肺炎疫情的挑戰日益嚴峻,新竹清華大學自農曆年起陸續已採取了量測體溫等全面的防疫措施。"

from collections import Counter
from wordcloud import WordCloud
from matplotlib import pyplot as plt

stops.append('\n')  ## 換行符號,加入停用字中,可以把它拿掉
stops.append('\n\n')
terms = [t for t in jieba.cut(text, cut_all=True) if t not in stops]

sorted(Counter(terms).items(), key=lambda x:x[1], reverse=True)  ## 這個寫法很常出現在Counter中,他可以排序,list每個item出現的次數。


plt.clf()
wordcloud = WordCloud(font_path="simsun.ttf")  ##做中文時務必加上字形檔
wordcloud.generate_from_frequencies(frequencies=Counter(terms))
plt.figure(figsize=(15,15))
plt.imshow(wordcloud, interpolation="bilinear")
plt.axis("off")
plt.savefig('cloud1.png')


from PIL import Image
import numpy as np

alice_mask = np.array(Image.open("cloud_mask7.png"))  ## 請更改cloud_mask7.png路徑
wc = WordCloud(background_color="white", max_words=2000, mask=alice_mask, font_path="simsun.ttf")
wc.generate_from_frequencies(Counter(terms))  ## 請更改Counter(terms)

wc.to_file("cloud2.png")  ##如果要存檔,可以使用

# plt.clf()
# plt.imshow(wc, interpolation='bilinear')
# plt.axis("off")
# plt.figure()
# plt.imshow(alice_mask, cmap=plt.cm.gray, interpolation='bilinear')
# plt.axis("off")
# plt.savefig('cloud2.png')

中文斷詞.png

References

pypi jieba

jieba 原始 github

python-11-利用jieba實現中文斷詞

NLP 中文斷詞最方便的開源工具之一 —— Jieba

Python-知名Jieba中文斷詞工具教學

2017

結巴中文斷詞台灣繁體版本 APCLab

結巴中文斷詞台灣繁體版本 ldkrsi

2020年7月20日

馬可夫鏈 Markov Chain

有許多自然或社會現象,其發展或演變會隨時間進行而呈現出幾種可能的狀態,稱為狀態空間,這種隨機變化的過程稱為隨機過程 stochastic process。如果記錄狀態的時間點是離散的,就稱為離散時間隨機過程, Markov Process 或是高速公路每天的意外事件數量就是一種離散時間隨機過程,如果記錄狀態的時間點是連續的,就稱為連續時間隨機過程,布朗運動 Brownian Motion 或是在銀行等待服務的人數就是一種連續時間隨機過程。

如果時間與狀態都是離散的 Markov Process 就稱為 Markov Chain。Markov Chain 是隨機變數 \(X_0, X_1, X_2, X_3, ...\) ,也就是 \({X_n, n>=0}\) 的一個數列,其中 \(X_0, X_1, ... X_{n-1}\) 都是過去時間的狀態, \(X_n\) 是目前的狀態, \(X_{n+1}, X_{n+2}, ...\) 是未來的狀態,每一個狀態可轉移到其他狀態,轉移的機率總和為 1,因此目前的狀態都是由前一個狀態以及轉移機率來決定的。

討論 Markov Chain 有兩個先決條件

  1. 目前的狀態都是由前一個狀態的轉移機率來決定的
  2. 在任何時間點,系統的事件只存在於某一種狀態中

Makov Chain 的表示方式

  1. transition diagram

  2. transition matrix 轉移矩陣

    \( \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0.5 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix} \)

  3. tree diagram

transition matrix

為方便計算,以 transition matrix 作為表示方式

\( T = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \)

選定某一個狀態為起點,根據轉移矩陣改變狀態,當狀態不斷地改變,會產生一個狀態變化的路徑。如考慮所有的狀況,可計算出每一個路徑的發生機率,這些路徑就稱為 Markov Chain。


問題:如果一開始的狀態在 \(a_1\) ,三天後,在 \(a_2\) 的機率為?

一天後: \( \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0.5 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 \end{bmatrix} \)

兩天後: \( \begin{bmatrix} 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0.5 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix} = \begin{bmatrix} 0 & 0.5 & 0.5 \end{bmatrix} \)

三天後: \( \begin{bmatrix} 0 & 0.5 & 0.5 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0.5 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix} = \begin{bmatrix} 0.3 & 0.25 & 0.45 \end{bmatrix} \)

如果直接一次計算:\( \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} T^3 = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}(\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0.5 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix})^3 = \begin{bmatrix} 0.3 & 0.25 & 0.45 \end{bmatrix} \)

結果為 0.25

吸收馬可夫鏈

在 Markov Process 中,當事件進入某個狀態時,就一直停留在該狀態,稱該狀態為吸收狀態 absorbing state

如果 Markov Chain 有下列兩種特性,就稱為 Absorbing Markov Chain

  1. 至少存在一個吸收狀態
  2. 事件在任何非吸收狀態時,經過有限時間後,就會進入 absorbing state

ex:

\( \begin{bmatrix} 0.2 & 0.3 & 0 & 0.5 \\ 0 & 0.4 & 0 & 0.6 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \) 是一種 Absorbing Markov Chain

\( \begin{bmatrix} 0.2 & 0 & 0.4 & 0.4 \\ 0 & 1 & 0 & 0 \\ 0.1 & 0 & 0.5 & 0.4 \\ 0.5 & 0 & 0.3 & 0.2 \end{bmatrix} \) 不是一種 Absorbing Markov Chain,雖然 \(a_2\) 是 absorbing state,但是其他三種狀態,都不能到達 \(a_2\),因此這不是 Absorbing Markov Chain

醫院是一種 absorbing markov chain 的實例,如果將進入醫院住院的病患,分為住院可走動,住院臥床,痊癒出院,死亡四種狀態,這四種狀態可以構成一個 absorbing markov chain,其中痊癒出院即死亡,都分別為 absorbing state

工廠品管商品,生產線製造的新品(狀態1),通過品管後為合格品(狀態2),失敗的商品會進入再造品(狀態3),再造品可再重新加工,變成修復品(狀態4),重新加工失敗最終成為報廢品(狀態5)

\( \begin{matrix} \begin{matrix} \quad\quad\quad\quad & 合格品 & 報廢品 & 新品 & 再造品 & 修復品 \end{matrix} \\ \begin{matrix} 合格品 \\ 報廢品 \\ 新品 \\ 再造品 \\ 修復品 \end{matrix} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0.7 & 0 & 0 & 0.3 & 0 \\ 0.9 & 0 & 0 & 0 & 0.1 \\ 0.6 & 0.4 & 0 & 0 & 0 \end{bmatrix} \end{matrix} \)

m 階馬可夫鏈

前面討論的 Markov Chain,用前一個單位時間的狀態可以預測下一個狀態,這稱為一階馬可夫鏈 first-order Markov Chain,如果需要前 m 個狀態,才能預測下一個狀態,就稱為 m 階馬可夫鏈。當然也有零階馬可夫鏈,也就是一般的機率分佈模型。

通常討論的馬可夫鏈都是一階馬可夫鏈,最重要的是無記憶性,因為系統不需要記錄前面經過的狀態,只需要目前的狀態,就可以預測下一個狀態。

HMM: Hidden Markov Model

當系統存在一些外部看不見的內部狀態,隨著系統內部狀態不同,表現出來的外部狀態也不同,我們可以直接觀察到外部狀態。

以買飲料為例,假設目前有三種飲料可以選擇:可樂、茶、牛奶,我們只能觀察到使用者每天早上9:00吃早餐,正在喝哪一種飲料,但是我們不知道他今天是在 7-11、FamilyMart 或是 HiLife 買到的。便利商店是內部狀態,三種飲料是外部狀態。

內部狀態的變化可用一個 transition matrix 表示

\( A= \begin{bmatrix} 0.7 & 0.1 & 0.2 \\ 0.3 & 0.2 & 0.5 \\ 0.4 & 0.3 & 0.3 \end{bmatrix} \)

不同的內部狀態,會產生不同的外部狀態,也可以用另一個 matrix 表示

\( B = \begin{bmatrix} 0.2 & 0.2 & 0.6 \\ 0.3 & 0.3 & 0.4 \\ 0.5 & 0.3 & 0.2 \end{bmatrix} \)

如果以 h 為內部狀態, \(h^{t}\) 為 t 單位時間的內部狀態, y 為外部狀態,\(y^{t}\) 是 t 單位時間的外部狀態,則

\(h^{t} = h^{t-1}A\)

\(y^{t} = h^{t}B\)

在實務上的問題,我們只知道外部狀態的觀察值,內部狀態被隱藏無法得知,也就是我們不會知道 transition matrix 實際的機率值,也就是我們不知道 A 與 B 的數值,只有一堆數據資料。

例如我們目前有甲乙丙三個人半年來每一週買飲料的歷史資料,當給定某一週買飲料的序列清單時,我們可以根據歷史資料,找出每一個人的購買習慣,也就是計算出 transition matrix,訓練模型,最後利用這個模型,將新的那一週的資料,分類判斷可能是哪一個人購買的。

在已知觀察序列,但未知轉移矩陣的條件下,找出其對應的的所有可能狀態序列,以及其中最大機率之狀態序列。

HMM 是有關時間序列的數據資料建立的模型,也是所有時間模型(ex: RNN, NLP, RL)的基礎。

HMM 三個基本問題

定義HMM參數為 λ,S 為狀態值集合, O 為觀察值集合,初始機率 π (Initial Probability)、轉移機率 A (Transition Probability)、發射機率 B (Emission Probability),因此 λ = ( π, A, B )

  1. Evaluation Problem

    評估問題最簡單,將所有機率做乘積就可以得到觀測序列發生的機率。

    根據觀察序列O及已知的模型參數λ,得出發生此序列的機率 P(O|λ)

    可用 Forward-backward Algorithm 降低計算複雜度

  2. Decoding Problem

    根據觀察序列O及模型參數λ,得出最有可能的隱藏狀態序列(hidden state sequence),也就是要求得哪一種狀態序列發生的機率最大,求給定觀測序列條件概率P(I|Q,λ)最大的狀態序列I

    可用 Viterbi Algorithm

    Viterbi算法是求最短路徑的過程,由於不知道每個觀測狀態的隱藏狀態是什麼,所以初始化時,每種隱藏狀態都有可能,計算在每種隱藏狀態下的整個觀測序列發生的機率,機率最大的那條路徑就是每個觀測狀態對應的唯一隱藏狀態。

  3. Learning Problem

    學習問題最複雜

    在已知隱藏狀態與觀察狀態的條件下,根據觀察序列O,找到最佳的參數 狀態轉移矩陣 A、觀察轉移矩陣 B、起始值機率 π,調整模型參數 λ = [A, B, π] 使得 P(O|λ) 最大化

    可用 EM Algorithm

語音辨識 HMM

語音辨識 HMM

語音辨識的目標,是事先使用大量語料,對每一個辨識語句建立一個 DHMM,然後當我們取得使用者輸入的測試語句後,即對測試語句進行端點偵測及 MFCC 特徵擷取,然後再將 MFCC 送至各個辨識語句所形成的 DHMM,算出每一個模型的機率值,機率值最大的 DHMM,所對應的辨識語句就是此系統的辨識結果。每一個音框的特徵向量都是39維的 MFCC

建立 0~9 數字語音辨識的方法

  1. 建立 0, 1, 2 ~ 9 的 HMMs
  2. 利用 Viterbi Decoding 找到新語句中,計算針對每一個 HMM 發音音素順序的序列的發生機率,也就是計算輸入語句和每個模型的相似度
  3. 最大機率值的 HMM,就是預測的 digit

進行 DHMM 的設計時,我們必須對每一個數字建立一個 HMM 模型,以數字「九」的發音為例,相關的 HMM 模型可以圖示如下:

把「九」的發音切分成三個「狀態」(States),分別代表 ㄐ、ㄧ、ㄡ 的發音,每一個狀態可以包含好幾個音框,而每一個音框隸屬於一個狀態的程度,是用一個機率值來表示,稱為「狀態機率」(State Probability)。此外,當一個新的音框進來時,我們可以將此音框留在目前的狀態,也可以將此音框送到下一個狀態,這些行為模式也都是用機率來表示,統稱為「轉移機率」(Transition Probability),其中我們使用「自轉移機率」(Self-transition Probability)來代表新音框留在目前狀態的機率,而用「次轉移機率」(Next-transition Probability)來代表新的音框跳到下一個狀態的機率。

由於每一個音框都會轉成一個語音特徵向量,我們首先使用 VQ 來將這些特徵向量轉成符號(Symbols),換句話說,每一個音框所對應的 VQ 群聚的索引值(Index),即是此音框的符號。若以數學來表示,k = O(i) 即代表 frame i 被分到 cluster k。

定義一些常用的數量:

  • frameNum:一段語音所切出的音框個數。
  • dim:每一個音框所對應的語音特徵向量的維度(例如基本的 MFCC 有 12 維)。
  • stateNum:一個 DHMM 的狀態個數
  • symbolNum:符號的個數,也就是 VQ 後的群數

HMM 的參數,就是指「狀態機率」和「轉移機率 Transition Probability」,說明如下:

  • 我們通常以矩陣 A 來表示轉移機率,其維度是 stateNum x stateNum,其中 A(i, j) 即是指由狀態 i 跳到狀態 j 的機率值。例如在上圖中,由狀態 1 跳到狀態 2 的機率是 0.3,因此 A(1, 2) = 0.3。一般而言,A(i, j) 滿足下列條件:
    • 在進行轉移時,我們只允許搜尋路徑跳到下一個相鄰的狀態,因此 A(i, j) = 0 if j≠i and j≠i+1。
    • 對於某一個狀態而言,所有的轉移機率總和為 1,因此 A(i, i) + A(i, i+1) = 1。
  • 我們通常以矩陣 B 來表示狀態機率,其維度是 symbolNum x stateNum,B(k,j) 即是指符號 k 隸屬於狀態 j 的機率值。換句話說,B 定義了由「符號」到「狀態」的機率,因此給定第 i 個音框,我們必須先由 O(i) 找出這個音框所對應的符號 k,然後再由 B(k,j) 找出此音框屬於狀態 j 的機率。

假設我們已經知道「九」的 HMM 所包含相關的參數 A 和 B,此時當我們錄音得到一段語音,我們如何算出來此語音隸屬於「九」的機率或程度?如何計算輸入語句和每個模型的相似度?換句話說,我們如何將每個音框分配到各個狀態之中,使得我們能夠得到整段語音最高的機率值?最常用的方法稱為 Viterbi Decoding,這是基於「動態規劃」(Dynamic Programming)的方法,可用數學符號定義如下:

  1. 目標函數:定義 D(i, j) 是 t(1:i) 和 r(1:j) 之間的最大的機率,t(1:i) 是前 i 個音框的特徵向量所成的矩陣,r(1:j) 則是由前 j 個狀態所形成的 DHMM,對應的最佳路徑是由 (1, 1) 走到 (i, j)。
  2. 遞迴關係:D(i, j) = B(O(i), j) + max{D(i-1, j)+A(j, j), D(i-1, j-1)+A(j-1, j)}
  3. 端點條件:D(1, j) = p(1, j) + B(O(1), j), j = 1 ~ stateNum
  4. 最後答案:D(m, n)

在上述數學式中,我們所用的所有機率都是「對數機率」(Log Probabilities),所以原來必須連乘的數學方程式,都變成了連加,具有下列好處:

  • 以加法來取代乘法,降低計算的複雜度。
  • 避開了由於連乘所造成的數值誤差。

假設轉移機率 A 和狀態機率 B 已知,那麼經由 Viterbi Decoding,我們可以找到最佳路徑(即是最佳分配方式),使整段路徑的機率值為最大,此機率值及代表輸入語音隸屬於此 DHMM 的機率,若是機率越高,代表此輸入語音越可能是「九」。

有關於 B(O(i),j)的定義,都是「音框 i 隸屬於狀態 j 的機率」,但是在 DHMM 和 CHMM 的算法差異很大,說明如下:

  • 在 DHMM,若要計算 B(O(i),j),我們必須先找到音框 i 所對應的符號 O(i),然後在經由查表法查到此符號 O(i) 屬於狀態 j 的機率是 B(O(i), j)。
  • 在 CHMM,B(O(i),j) 是由一個連續的機率密度函數所定義。

如何經由大量語料來估測每個 HMM 模型的最佳參數值 A 和 B?

首先,我們必須先定義什麼是「最佳參數」:對某一個特定模型而言,最佳參數值 A 和 B 應能使語料產生最大的對數機率總和。這個定義和最大似然估計(maximum likelihood estimation,縮寫為MLE) 完全相同,也非常合理。

計算最佳參數的方法,稱為 Re-estimation,其原理非常類似 batch k-means (Forgy's method) 的方法,先猜 A 和 B 的值,再反覆進行 Viterbi Decoding,然後再重新估算 A 和 B 的值,如此反覆計算,我們可以證明在疊代過程中,機率總和會一路遞增,直到逼近最佳值。(但是,就如同 k-means Clustering,我們並無法證明所得到的機率值是 Global Maximum,因此在訓練的過程中,可以使用不同的啟始參數,看看是否在反覆疊代後,能夠得到更好的機率總和。)求取參數的方法說明如下:

  1. 將所有的訓練語句切出音框,並將每一個音框轉成語音特徵向量,例如 39 維的 MFCC。

  2. 對所有語音特徵向量進行向量量化編碼(Vector Quantization, VQ),找出每一個向量所對應的 symbol(此即為對應的中心點或codeword)

  3. 先猜一組 A 和 B 的啟始值。如果沒有人工的標示資料,我們可以使用簡單的「均分法」,示意圖如下:

  4. 反覆進行下列兩步驟,直到收斂

    • Viterbi decoding:在 A 和 B 固定的情況下,利用 Viterbi decoding,找出 n 句「九」的語料所對應的 n 條最佳路徑。
    • Re-estimation:利用這 n 條最佳路徑,重新估算 A 和 B。

估算 A 的方法

\( A= \begin{bmatrix} 3/4 & 1/4 & 0 \\ 0 & 4/5 & 1/5 \\ 0 & 0 & 1 \end{bmatrix} \)

估算 B 的方法:

\( B= \begin{bmatrix} 1/4 & 3/5 & 0 \\ 1/4 & 2/5 & 2/6 \\ 2/4 & 0 & 0 \\ 0 & 0 & 4/6 \end{bmatrix} \)

假設我們的目標函數可以寫成 P(A, B, Path),則上述求參數的方法會讓 P(A, B, Path)逐次遞增,直到收斂,因為:

  1. 在 A, B 固定時,Viterbi decoding 會找出最佳的路徑,使 P(A, B, Path) 有最大值
  2. 在路徑(Path)固定時,Re-estimation 會找出最佳的 A, B 值以使 P(A, B, Path)有最大值

References

隨機過程.pdf

Markov Chain

Markov Model

Hidden Markov Model (part 1)

Markov chain 及 HMM

HMM(Hidden Markov Model)簡介

機器不學習:HMM模型解析

Hidden Markov Model (part 3)

hmmDiscrete_chinese

即時語音辨識系統

2020年7月13日

BRD、MRD、PRD Requirement Documents

文件用途

  • BRD:Bussiness Requirement Document 商業需求文件

    討論市場中的市場趨勢、商業模型。一份BRD可能不止一個產品,而是數個產品為主的切入商業模式。用來決定公司大戰略的方向,去看數個產品對於公司的「總體戰略」與「商業價值」。

    主要給產品、運營、研發、財務、老闆等管階層看的,用來決定是否要開始某個產品。

  • MRD:Market Requirement Document 市場需求文件

    決定產品對於用戶的價值,一份MRD內需有該產品的市場分析、用戶分析、需求分析、競品策略、產品路線圖等,用來看公司現在醞釀的產品能提供哪些與其他競爭對手們,增加哪些不同的功能去切入這個市場。

    主要是給產品、運營、研發等專案人員看的,在大家一致認可需求成立的時候,來商量該怎麼做,如何做,什麼時間做。

  • PRD:Product Requirement Document 產品需求文件

    決定產品該做成什麼樣子,包含產品功能、功能流程邏輯、互動方式、產品雛形等等,用以跟開發團隊溝通。

    主要是給專案經理、UI 設計師、開發團隊、測試工程師、運營等人員查看,是具體的產品設計文件,開發者可以根據PRD得知整個產品的邏輯,測試人員可以根據PRD 產生測試項目,專案經理可以根據PRD拆分工作。PRD是專案啓動之前,必須要通過評審確定的最重要文檔,PRD決定了成品的結果!

簡單地說:

  • BRD 討論現在做什麼產品比較好,決定要不要做
  • MRD 討論如何做有特色具有競爭力的產品,決定如何開始做
  • PRD 決定做成什麼樣子

BRD 文件內容

  • Background
    • Market
    • Client
    • Competitor
  • Business Model
    • Niche point
    • Growth point
    • Margin analysis
  • Product Description
    • Product Positioning
    • Product Vision
    • Product Roadmap
    • Product Core Feature
  • Profit & Cost
    • Revenue
    • Fixed Cost
    • Variable Cost
  • Risk
    • Risk Assessment
    • Risk Control

MRD 文件內容

  • Market Research
    • Character
    • Opportunity
    • Trend
    • Segment
    • Barriers
    • Timing
  • Target Market
    • Target Point
    • Scale
    • Character
    • Trend
  • Target User
    • Persona
    • Journey
    • Category
    • Core User
  • Competitor
    • Direct & Indirect
    • Business Model
    • TA
    • Operation
    • Techonics
    • Market Share
  • Adv. & Positioning
    • SWOT
    • Porter Five Force
    • 4P, 4C
    • STP
  • Product Description
    • Product Positioning
    • Product Vision
    • Product Roadmap
    • Product Core Feature

PRD 文件內容

  • File Description
    • File name
    • Version
    • Revised History
    • Table
    • Term Explanation
  • Product Description
    • Background
    • Vision
    • Roadmap
    • Goal
    • Value
  • Funciton Requirement
    • Global Rule
    • Product Structure
    • Flow Chart
    • Function List
    • Detailed Description
  • Non-Function Requirement
    • Data Need
    • Historical Data
    • API
    • Security
    • Performance
    • Compatibility

References

PM 文件指南 - 產品經理一定要掌握的 PRD/SPEC 心法與撰寫教學

如何撰寫新產品開發相關文件?MRD與PRD是甚麼?又有何不同?

【SOP不藏私】系列#EP1「連猴子也會的PRD指南」

產品需求文檔

互聯網產品設計常用文檔類型BRD、MRD、PRD、FSD

BRD、MRD 和 PRD 之間的區別與聯繫有哪些?

如何撰寫一份合格的產品需求文件PRD?

PRD文檔範例,產品經理值得收藏的寫作手冊