第八章 随机过程

马尔科夫链

看来要从老套路开始了,今天天气不错。昨天的天气如何?昨天的天气跟今天的天气会不会有关系?有什么关系?我们都比较清楚,如果说昨天的是个大晴天,天气是20度,那么今天的天气不太可能是下雪,零下10度。假设每天的天气是一种状态,天气的变化可以看成是,昨天的状态,转移到今天的状态。假设昨天的天气,用向量的方式来表示:[晴,雨] = [1.0,0.0],表示是晴天,今天的天气[晴,雨] = [1.0,0.0]也是晴天。昨天天气的状态转移到今天的状态的概率为:

$$\begin{bmatrix} 0.8 & 0.2 \ 0.2 & 0.8 \ \end{bmatrix}$$

表示从晴天转移到晴天的概率为0.8,从晴天转移到阴天的概率为0.2。只要我们知道今天的天气情况,知道转移概率,就能推测出明天的天气了。有人可能会这样问,如果按照这种假设下去的话,一开始是晴天以后永远都是晴天的,但是要知道我们之所以这样的假设是为了好懂,现实过程中,会把天气的每一种情况进行细分,细分以后就比较从一个状态转移到另一个状态了,而转移矩阵的数值,都可以通过从历史的经验数据中得到。

这种模型,就叫做马尔科夫链,马尔科夫是个人名,来自战斗的民族,关于彼得堡的数学故事很好玩,有空可以去看看。

隐马尔科夫链

现实中还有另外一个中情况,他属于隐马尔可夫链。再来看一个例子: 假设这里有三个瓶子如下:

第一个瓶子:红球(3),白球(7) 第二个瓶子:红球(5),白球(5) 第三个瓶子:红球(4),白球(6)

现在从这些瓶子中抽了五次的球结果分别为:红,白,白,白,红。但是我们并不清楚,这五次中,到底球是从哪个瓶子里抽出来的,这就是隐藏的变量。这种模型称为隐马尔可夫链。

为了方便理解,大部分文章的例子都是举红球和白球的故事,他是数据挖掘中的李雷和韩梅梅。但最重要的还是要能够理解每个模型的意义。在数据挖掘中也是存在着很多的隐形变量。记得之前,很多人在讨论数据统计和数据挖掘有什么区别,有个例子比较形象。孙悟空总共参加了100次战斗,有99次是胜利,1次失败,如果仅仅是把这些数据画成图,我们可以看出孙悟空的战胜率是比较高的,如果孙悟空再去战斗的话,我们会继续猜测他会继续获胜,这是数据统计,通过历史的数据看一种趋势。而数据挖掘要做的事情是从这些数据中挖出背后的关系,假如胜败的关系跟技能,装备,武器等有关系,这些就是隐藏在数据里的隐藏因数,而这些关系中,占用的比率到底是多少呢?我们并不是非常的清楚,这就是要通过我们能够观察到的变量和结果,来推测出隐藏变量的关系,知道这些隐藏变量的关系以后,在下一次的战斗中,能更有把握的进行推测,而不是单单的去看一种趋势而已。

世界的很多模型,隐隐约约隐藏着一种看不见的联系关系,如果把这种关系的转移看清楚了,就能对这个模型进行相应的估计了。

定义

隐马尔科夫模型是关于时序的概率模型,描述由一个隐藏的马尔科夫链随机生成不可观察的状态的序列,再由各个状态生成一个观测而产生观测随机序列的过程。 设Q是所有可能的状态的集合,V是所有可能的观测的集合。

$$Q= \begin{Bmatrix} q_1,q_2,...,q_N \ \end{Bmatrix},V=\begin{Bmatrix} v_1,v_2,...,v_N \ \end{Bmatrix}$$

其中,N是可能的状态数,M是可能的观测数。

A是状态转移概率矩阵:

$$A=|a<>{ij}|{N \times N}$$

其中,

$$a<>{ij}=P(i{t+1}=q_j|i_t=q_i),i=1,2,...,N;j=1,2,...,N$$

是在时刻t处于状态$q_i$的条件下在时刻t+1状态到状态q_j的概率。 B是观测概率矩阵:

$$B=|b<>j(k)|{N \times M}$$

其中,

$$b_j(k) = P(o_t=v_k|i_t=q_j),k=1,2,...,M;j=1,2,...,N$$

是在时刻t处于状态$q_i$的条件下生成观测$v_i$的概率。

是初始状态概率向量:

$$\pi = (\pi_i)$$

其中,

$$\pi_i = P(i_1=q_i),i=1,2,...,N$$

是时刻t=1处于状态$q_i$的概率。 A,B,$\pi$成为隐马尔可夫模型的三要素。 先看一个例子,再来解释这三个变量的意义。 还是盒子和球模型:

盒子 1 2 3 4
红球数 5 3 6 8
白球数 5 7 4 2

从当前盒子转移到下一个盒子,规则是确定的,也就是转移概率分布为:

$$A=\begin{bmatrix} {0}&{1}&{0}&{0}\ {0.4}&{0}&{0.6}&{0}\ {0}&{0.4}&{0}&{0.6}\ {0}&{0}&{0.5}&{0.5}\ \end{bmatrix}$$

A矩阵表示如下的规则:如果当前盒子是盒子1,那么下一个盒子一定是盒子2,即$a<>{12}=1$,如果当前盒子为2,那么以概率0.4转移到盒子1,即$a{21}=0.4$,以此类推。

而观察概率可以通过表格里的数据算出来,就是盒子里取到白球,红球的概率。

$$B=\begin{bmatrix} {0.5}&{0.5}\ {0.3}&{0.7}\ {0.6}&{0.4}\ {0.8}&{0.2}\ \end{bmatrix}$$

初始取到哪个盒子,这里取的是平均值:

$$\pi = (0.25,0.25,0.25,0.25)^T$$

进行了五次试验,每次得到的球颜色为:

$$O={红,红,白,白,红}$$

在这个例子中有两个随机序列,一个是盒子的序列(状态序列),一个是球颜色的观察序列(观察序列),前者是隐藏的,后者是可观察的。

取那个盒子(状态序列)和哪些因素有关系呢?状态转移概率矩阵A与初始状态概率向量$\pi$确定取哪个盒子。

而观测概率矩阵B确定了如何从状态生成观测,与状态序列综合确定了如何产生观测序列。

维特比算法

很多时候就会怀疑,我们即使把状态顺序都估计出来,这样我们能够解决哪些问题呢?从一个盒子跳到另外一个盒子,这样的模型符合我们实际中哪一些现象呢? 相信这世界的状态,并不是胡乱跳的,总是有一定的规律,而发现这种规律后,利用这个规律做出来的效果是最好,因为他最符合我们观察到的,而我们通过观察的现象,推测出这些规律,是符合概率论的基础的。如果把取盒子的次序,当成一条条路径的话,比如取到盒子1假设为路径1,取到盒子2假设为路径2,那么如果在某种状态下所取到的盒子,代表了我们该走的路径。 知道这个状态的变化,我们就能够解决动态规划的问题。 这个算法叫做维特比算法。 算法的描述如下: 输入:模型$\lambda$和观察$O=(o_1,o_2,...,o_r)$ 输出:最优路径$I^{\ast}=(i_1^\ast,i_2^\ast,...,i_r^\ast)$ (1)初始化

$$\delta_1(1)=\pi_ib_i(o_1),i=1,2,...,N$$ $$\psi_1(1)=0,i=1,2,...,N$$

(2)递推,对t=2,3,...,T

$$\delta<>t(i)= max|delta{t-1}(j)a<>{ji}|b i(o_t),i=1,2,...,N$$ $$\psi<>1(1)=arg max [\delta{t-1}(j)a_{ji}],i=1,2,...,N$$

(3)终止

$$P^\ast=max \delta_r(i)$$ $$i_r^\ast=argmax \delta_r(i)$$

(4)最优路径回溯,对t=T-1,T-2,...,1

$$i<>t^\ast=\psi{t+1}(i_{t+1}^\ast)$$

求得最优路径$I^\ast=(i_1^\ast,i_2^\ast,...,i_r^\ast)$。 通过维特比算法就能够找到最优路径,即最优状态序列。

用隐马尔科夫模型判断词性

在汉字里,可能出现一个词多种词性的情况,例如,好好生活,生活不错,生活这个词,前者是动词,后者是名词。如何区分这句子词语的词性呢? 有 农民 则 忧虑 , 一旦 土地 被 徵收 、 房子 拆 了 , 家族 从此 也 就 散 了 。 在中文语句中,词性的转移是有一定规律的,就像天气的变化一样有些词性会紧跟在另外一个词性后面,但是这种规律是没办法通过专家进行总结的,因为总是有些特殊的情况,但这种转移,隐马尔科夫模型就非常擅长做这种事情。如何用隐马尔科夫模型来描述这种词性的转变呢?加入多词性相当于一个盒子的话,摸出哪个颜色的球代表哪种词性,观察到的结果就是上面的那个句子,而我们通过维特比求出的路径,就是我们所要的词性。 在这里的转移矩阵为,每个词性到另外一种词性的概率。 观察概率为:已知词性时为指定单词的概率 初始状态概率向量为这个词在开头的概率。 这三个概率向量,可以通过一组已知的数据进行训练。 训练:

# starts[] 某个词性出现在句首的概率
self.starts = [ 0 for i in self.state_nums() ]
# transitions[] 从一个词性转移到另一个词性的概率
self.transitions = [ [ 0 for j in self.state_nums()] for i in self.state_nums() ]
# emissions[] 已知词性时为指定单词的概率
self.emissions = [ [ 0 for j in self.observe_nums()] for i in self.state_nums() ]

# 接着分析输入文件,用统计方法生成hmm模型的参数
first_loop = 1
for pos,word,tag in self.datafile(train_data):
    state_index = self.get_state_idx(tag)
    observe_index = self.get_observe_idx(word)

    if (int(pos) == 1):     # 句首,记录该state在句首位置出现的次数
        self.starts[state_index] += 1
    self.emissions[state_index][observe_index] += 1

    if (first_loop == 1):
        first_loop = 0
        last_state = state_index
    else:
        self.transitions[last_state][state_index] += 1
        last_state = state_index

self.start_count = sum(self.starts)
assert self.start_count != 0
self.starts = map(lambda x: float(x)/self.start_count, self.starts)

for state in self.state_nums():
    state_count = state_counts[self.get_state(state)]
    self.transitions[state] = map(lambda x: float(x)/state_count, self.transitions[state])

for state in self.state_nums():
    state_count = state_counts[self.get_state(state)]
    self.emissions[state] = map(lambda x: float(x)/state_count, self.emissions[state])

根据维特比算法求出路径:

def viterbi(self, observe_list, return_trellis=False):
    """
    Returns the most likely sequence of hidden states, for a given
    sequence of observations. Uses the Viterbi algorithm.
    # <Usage>
    # final, path, viterbis = hmm.viterbi(test_list, True)
    # hmm.print_trellis(viterbis)
    # print "%s: %5.2f%%, %s" % (test_list, final*100, [hmm.get_state(state).encode("ascii") for state in path])
    """
    trellis = self._init_trellis(observe_list, forward=True)
    path = {state: [state] for state in self.state_nums()}

    for step in range(1, len(observe_list)):
        newpath = {}
        for state in self.state_nums():
            emission_prob = self.emission(state, self.get_observe_idx(observe_list[step]))
            (max_prob, max_state) = max([(trellis[step-1][old_state]
                    * self.transition(old_state, state) * emission_prob,
                    old_state) for old_state in self.state_nums()
            ])
            trellis[step][state] = max_prob
            newpath[state] = path[max_state] + [state]
        path = newpath

    (final, state) = max([(trellis[-1][state], state) for state in self.state_nums()])
    return (final, path[state]) if not return_trellis else (final, path[state], trellis)

这世界除了黑天鹅意外,很多的事情都是一步一步的发生的,如果能够捕捉到里面的核心,很容易可以应用隐马尔科夫模型,对隐藏的变量进行求解,而解的路径就是符合某种最优的条件。 条件随机场模型(CRF)与之类似,总的来说CRF优于HMM的地方在于,它可以引入更多的特征,按上面词性的解法,条件随机场模型包括词语本身特征和词语所在上下文的特征,而非单词本身。

PS: 如本文对您有帮助,不妨通过一下方式支持一下博主噢 ^_^

官方
微信
官方微信
Q Q
咨询
意见
反馈
返回
顶部