智能算法之马尔可夫模型
前言
可能大家更常见到隐马尔科夫模型(HMM),马尔科夫模型可以看成是一个更基础的模型,它是对能直接观察到的事件进行建模,所以与HMM相对应,有时也叫它为显马尔科夫(VMM)。马尔科夫模型要处理的是序列问题,核心思想就是统计所有样本的过程,得到系统中状态之间的转移概率。
马尔可夫过程
马尔可夫过程是一个随机过程,系统从一个状态到另外一个状态存在转移概率,而转移概率仅通过前一状态来计算出来,与过去的状态和初始状态都没有关系。这里的随机过程主要是说该过程随时间而变化,且每个时刻的状态值是随机的,按照一定的概率分布。
随机过程相关状态如果向之前的状态推广,那么过程中的每个状态的转移依赖于之前的n个状态,此模型就为n阶模型。所以上面提到的马尔可夫过程为一阶过程,它的特点是每个状态的转移都只依赖于前一个状态。以此类推,根据之前n个状态计算转移概率的则为n阶过程。
马尔可夫链
时间和状态都是离散的马尔可夫过程即为马尔可夫链。假设马尔可夫链包含的所有可能的值的集合为,则S称为状态空间。设一个马尔科夫链,其中的每个变量的取值范围都在S集合内,且t表示一共有t个时刻。
与前面n阶过程对应,同样存在n阶马尔科夫链。比如,如果某个状态出现的概率与它的前一个状态有关,这时就为一阶马尔科夫链,在处理自然语言中则是对应二元语法。同样的,如果某个状态出现的概率与它的前两个状态有关,则为二阶马尔科夫链,对应的是三元语法。其中n阶马尔科夫模型对应的是n+1元语法。
关于n元语法可以参考之前写的文章《n元语法》。
马尔科夫假设
对于n阶马尔科夫过程,可以假设状态与前一个或几个词相关,这个就是马尔科夫假设。一阶马尔科夫链,转移过程状态概率与前一状态有关,此时可以表示为,
举个例子
用简单的“中国人中午要吃午饭”一句话看下不同状态的转换及其概率。“中”到“国”“午”概率各50%,“午”到“饭”“要”概率各50%,其他状态转化为100%。当我们用大量语料进行训练后,就能得到很大的转移矩阵,每个字后面可能都会有很多种状态连接,并且有相应的概率。
实现
其中某次输出可能为“吃 午 要”。
import random words = ["中", "国", "人", "中", "午", "要", "吃", "午", "饭"] cache = {} size = 3 def binary(): for i in range(len(words) - 1): yield (words[i], words[i + 1]) for w1, w2 in binary(): key = w1 if key in cache: cache[key].append(w2) else: cache[key] = [w2] seed = random.randint(0, len(words) - 1) seed_word = words[seed] word1 = seed_word _words = [] for i in range(size): _words.append(word1) word1, = random.choice(cache[word1]) print(' '.join(_words))
-------------推荐阅读------------
我的2017文章汇总——机器学习篇
我的2017文章汇总——Java及中间件
我的2017文章汇总——深度学习篇
我的2017文章汇总——JDK源码篇
我的2017文章汇总——自然语言处理篇
我的2017文章汇总——Java并发篇
------------------广告时间----------------
公众号的菜单已分为“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。
鄙人的新书《Tomcat内核设计剖析》已经在京东销售了,有需要的朋友可以购买。感谢各位朋友。
为什么写《Tomcat内核设计剖析》
欢迎关注: