HMM隐马尔可夫模型 #25

rico-c · 2019-09-29T09:50:00Z

问题

问题：

连续三天，做的事情分别是：walk，shop，clean。计算产生这些行为的概率是多少?
同样是三天这三件事，这三天的天气是怎么样的。这三天怎么样的天气才最有可能让她做这样的事情?

隐马尔可夫模型

定义

马尔可夫链

马尔可夫链是一组具有马尔可夫性质的离散随机变量的集合，具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定

隐马尔可夫模型

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。

构成

设 Q 是所有可能的状态的集合，V 是所有可能的观测的集合。记为
S 是长度为T 的状态序列，O 是对应的观测序列。记为：
A 是状态转移概率矩阵：

是在时刻t 处于状态qi 的条件下，在时刻 t+1 转移到状态qj 的概率。
B 是观测概率矩阵：

是在时刻t 处于状态qj的条件下，生成观测值Vk的概率。
初始状态概率向量π
隐马尔可夫模型λ：

例子

其中：

初始概率分布π为:
$π = （0.6,0.4）^T$
状态转移概率分布A为：

$$ A = \begin{bmatrix} 0.7 & 0.3\\ 0.4 & 0.6\\ \end{bmatrix} $$

观测概率分布B为：

$$ B = \begin{bmatrix} 0.1 & 0.4 & 0.5\\ 0.6 & 0.3 & 0.1\\ \end{bmatrix} $$

几个用途

概率计算问题：给定模型 $λ = (A,B,π)$和观测序列 $O = (0_1,0_2, ...,O_T)$,计算在该模型下观测序列 $O$出现的概率 $P(O|λ)$。

连续三天，做的事情分别是：walk，shop，clean。根据模型，计算产生这些行为的概率是多少。

学习问题：已知观测序列$O = (0_1,0_2, ...,O_T)$,估计模型$λ = (A,B,π)$的参数，使该模型下观测序列概率$P(O|λ)$最大。

同样是三天这三件事，而其他什么信息我都没有。建立一个模型，晴雨转换概率，第一天天气情况的概率分布，根据天气情况选择做某事的概率分布。

解码问题：已知模型$λ = (A,B,π)$和观测序列$O = (0_1,0_2, ...,O_T)$,求在指定观测序列下最有可能的状态序列。

同样是三天这三件事，这三天的天气是怎么样的。这三天怎么样的天气才最有可能让她做这样的事情。

解法

概率计算问题

给定模型 λ=(A,B,π)和观测序列 O=(01,02,...,OT),计算在该模型下观测序列 O出现的概率 P(O|λ)。

直接遍历计算

把每一种天气情况下产生这些行为遍历并计算概率的求和。
其中：

状态序列$I=(i_1,i_2,...,i_T)$的概率：
$$P(I|λ) = π_{i_1}a_{i_1i_2}a_{i_2i_3}...a_{i_{T-1}i_T}$$
对固定状态序列$I=(i_1,i_2,...,i_T)$，观测序列$O=(o_1,o_2...,o_T)$的概率是
$$P(O|I,λ)=b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)$$
$O$和$I$同时出现的联合概率为
$$P(O,I|λ)=P(O|I,λ)P(I|λ)$$
对所有的可能的概率求和
$$P(O|λ)=\sum_{I}P(O,I|λ)$$

问题：计算量大，是$O(TN^T)阶的$。

前向算法

前向概率：给定模型λ定义观测序列$o_1,o_2,...,o_t$，且状态为$q_i$的概率
$$α_t(i) =P(o_1,o_2,...o_t,i_t=q_i|λ)$$
计算每个时间点时，每个状态的发生观测序列的概率
其中：

计算初值，对观测序列第一项$o_1$和$i_1$求联合概率：
$$α_1(i)=π_ib_i(o_1)$$
按时间序列一次递推:
$$α_{t+1}(i)=
\begin{bmatrix} \sum_{j=1}^Nα_t(j)a_{ji}\end{bmatrix}b_i(o_{t+1})$$
求和
$$P(O|λ)= \sum_{i=1}^Nα_T(i)$$

例：给定观测序列为$O=(walk,shop,clean)$，求产生该观测序列的概率。

(1) 计算初值
$$α_1(1)=π_1b_1(o_1)=0.60.1=0.06$$
$$α_1(2)=π_2b_2(o_1)=0.40.6=0.24$$
(2) 递推计算
注：由上一阶段的不同状态跳转到状态1的概率和状态1对$o_2$的观测概率
$$a_2(1)=
\begin{bmatrix} \sum_{i=1}^2α_1(i)a_{i1}\end{bmatrix}b_1(o_2)=(0.060.7+0.240.4)0.4$$
$$α_2(2)=
\begin{bmatrix} \sum_{i=1}^2α_1(i)a_{i2}\end{bmatrix}b_2(o_2)=(0.060.3+0.24*0.6)*0.3$$
$$α_3(1)=
\begin{bmatrix} \sum_{i=1}^2α_1(i)a_{i2}\end{bmatrix}b_1(o_3)=...$$
$$α_3(2)=
\begin{bmatrix} \sum_{i=1}^2α_1(i)a_{i3}\end{bmatrix}b_2(o_3)=...$$
(3) 求和
$$P(O|λ)= α_3(1) + α_3(2)$$

复杂度$O(N^2T)阶$

解码问题

已知模型$λ = (A,B,π)$和观测序列$O = (0_1,0_2, ...,O_T)$,求在指定观测序列下最有可能的状态序列。

近似算法

在每个时刻$t$选择在该时刻最有可能出现的状态$i_t$，从而得到一个状态序列$I$,将它作为预测的结果。

只能保证当前时刻最优，不能保证全局最优

维特比算法

从时刻t=1开始，递推地计算在时刻t，状态为i的各条路径的最大概率，直到得到t=T状态为i的各条路径的最大概率。
定义在时刻t状态为i的所有单个路径（i1,i2,...it）中概率最大的值为：
$$δ_t(i) = max P(i_t=i,i_{t-1},...,o_t,...o_1|λ)$$
递推可得
$$δ_{t+1}(i) = max_{1<j<N} [P(δ_t(j)a_{ji}]b_i(o_{t+1}))$$
$ψ_t(i)$为在t时刻第i状态的路径最大概率的上个状态

例：已知模型如下和$O=(walk,shop,clean)$,求最有可能的状态序列。

初始概率分布π为:
$$π = \begin{bmatrix}
0.6\
0.4\
\end{bmatrix}$$
状态转移概率分布A为：

$$ A = \begin{bmatrix} 0.7 & 0.3\\ 0.4 & 0.6\\ \end{bmatrix} $$

观测概率分布B为：

$$ B = \begin{bmatrix} 0.1 & 0.4 & 0.5\\ 0.6 & 0.3 & 0.1\\ \end{bmatrix} $$

(1) 初始化，求t=1时的$δ_1(i)=π_ib_i(o_1)$：
$$δ_1(1)=π_1b_1(o_1)=0.60.1=0.06$$
$$δ_1(2)=π_2b_2(o_1)=0.40.6=0.24$$
(2)递推计算t=2和t=3下各状态的最大概率：
$$δ_2(1)=max{0.060.7,0.240.4}0.4=0.0384$$
$$ψ_2(1)=2$$
$$δ_2(2)=max{0.060.3,0.240.6}0.3=0.0432$$
$$ψ_2(2)=2$$
$$δ_3(1)=max{0.03840.7,0.04320.4}0.5= 0.0134$$
$$ψ_3(1)=1$$
$$δ_3(2)=max{0.03840.3,0.04320.6}0.1=0.0025$$
$$ψ_3(2)=2$$
（3）最优路径的概率
$$P = 0.0134$$
最优终点是
$i_3^ =1$
逆推：
$i_2^=ψ_3(1)=1$
$i_1^*=ψ_2(1)=2$

学习问题

同样是三天这三件事，而其他什么信息我都没有。建立一个模型，晴雨转换概率，第一天天气情况的概率分布，根据天气情况选择做某事的概率分布。

Baum-Welch算法（EM算法）

EM算法：

首先选取参数的初值，然后通过：
1. E步：求期望
2. M步：求极大
直到收敛为止。

HMM应用

结巴切词（源码）

切词方法：

    # 切词 cut方法 ，默认使用HMM隐马尔可夫模型  
    # 例子：sentence： 我来到北京清华大学，今天天气不错,good day!
    # 输出：我/来到/北京/清华大学/，/今天天气/不错/,/good/ /day/!
    def cut(self, sentence, cut_all=False, HMM=True):
        '''
        The main function that segments an entire sentence that contains
        Chinese characters into separated words.
        Parameter:
            - sentence: The str(unicode) to be segmented.
            - cut_all: Model type. True for full pattern, False for accurate pattern.
            - HMM: Whether to use the Hidden Markov Model.
        '''
        sentence = strdecode(sentence)

        if cut_all:
            re_han = re_han_cut_all
            re_skip = re_skip_cut_all
        else:
            re_han = re_han_default
            re_skip = re_skip_default
        if cut_all:
            cut_block = self.__cut_all
        elif HMM:
            cut_block = self.__cut_DAG
        else:
            cut_block = self.__cut_DAG_NO_HMM
        # 按正则先把成块的文本切开         
        # blocks： ['', '我来到北京清华大学', '，', '今天天气不错', ',', 'good', ' ', 'day', '!']
        blocks = re_han.split(sentence)
        for blk in blocks:
            if not blk:
                continue
            if re_han.match(blk):
                # 对文本块使用__cut_DAG进一步切词                
                for word in cut_block(blk):
                    yield word
            else:
                tmp = re_skip.split(blk)
                for x in tmp:
                    if re_skip.match(x):
                        yield x
                    elif not cut_all:
                        for xx in x:
                            yield xx
                    else:
                        yield x
                        
                        
    # HMM下使用的切词
    def __cut_DAG(self, sentence):
        # sentence：我来到北京清华大学
        # 输出对应的DAG图数据
        DAG = self.get_DAG(sentence)
        # {0: [0], 1: [1, 2], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]}
        # DAG[5]=[5,6,8]的意思就是，以’清‘开头的话，分别以5、6、8结束时，可以是一个词语，即’清‘、’清华‘、’清华大学‘
        route = {}
        # 维特比算法计算route
        self.calc(sentence, DAG, route)
        # route: 
        # {9: (0, 0), 8: (-8.142626068614787, 8), 7: (-8.006816355818659, 8), 6: (-17.53722513662092, 6), 5: (-11.085007904198626, 8), 4: (-20.20431518448597, 4), 3: (-18.548194315526874, 4), 2: (-24.22732015246924, 2), 1: (-27.379629658355885, 2), 0: (-32.587853155857076, 0)}
        x = 0
        buf = ''
        N = len(sentence)
        while x < N:
            y = route[x][1] + 1
            l_word = sentence[x:y]
            # 无法形成词的buf，交由HMM进行标注
            if y - x == 1:
                buf += l_word
            else:
                if buf:
                    if len(buf) == 1:
                        yield buf
                        buf = ''
                    else:
                        if not self.FREQ.get(buf):
                            # 当遇到一些dict.txt中没出现的词的时候，会进入这个函数
                            # 使用HMM的方法，对这些未识别成功的词进行标注
                            recognized = finalseg.cut(buf)
                            for t in recognized:
                                yield t
                        else:
                            for elem in buf:
                                yield elem
                        buf = ''
                yield l_word
            x = y
            
            
		# 动态规划 计算最优路径
    def calc(self, sentence, DAG, route):
        N = len(sentence)
        route[N] = (0, 0)
        logtotal = log(self.total)
        # 从后往前遍历句子
        for idx in xrange(N - 1, -1, -1):
            # 对每个字计算最有可能的词组
            route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) - logtotal + route[x + 1][0], x) for x in DAG[idx])

维特比算法切未知词：

# 维特比算法
def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]  # 状态概率矩阵  
    path = {}
    for y in states:  # 初始化状态概率
        # 求第一个字的状态概率          
        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
        path[y] = [y]  # 记录路径
    for t in xrange(1, len(obs)):
        V.append({})
        newpath = {}
        for y in states:
            # 在y状态下为第t个字的概率          
            em_p = emit_p[y].get(obs[t], MIN_FLOAT)
            # t时刻状态为y的最大概率(从t-1时刻中选择到达时刻t且状态为y的状态y0)
            (prob, state) = max(
                [(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
            # 第t个字，状态为y的概率             
            V[t][y] = prob
            newpath[y] = path[state] + [y]
        path = newpath
    # 求出最后一个字哪一种状态的对应概率最大，最后一个字只可能是两种情况：E(结尾)和S(独立词)  
    (prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')

    return (prob, path[state])

  
# HMM标注切词
def __cut(sentence):
    global emit_P
    prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)
    # 输出 pos_list: ['B', 'M', 'E', 'B', 'M', 'E', 'S', 'S']格式用于切词
    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:]

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

HMM隐马尔可夫模型 #25

HMM隐马尔可夫模型 #25

rico-c commented Sep 29, 2019 •

edited

Loading

HMM隐马尔可夫模型 #25

HMM隐马尔可夫模型 #25

Comments

rico-c commented Sep 29, 2019 • edited Loading

问题

隐马尔可夫模型

定义

构成

例子

几个用途

解法

概率计算问题

直接遍历计算

前向算法

例：给定观测序列为$O=(walk,shop,clean)$，求产生该观测序列的概率。

解码问题

近似算法

维特比算法

例：已知模型如下和$O=(walk,shop,clean)$,求最有可能的状态序列。

学习问题

Baum-Welch算法（EM算法）

HMM应用

结巴切词（源码）

切词方法：

维特比算法切未知词：

rico-c commented Sep 29, 2019 •

edited

Loading