1、确定性模式(Deterministic Patterns):确定性系统

  考虑一套交通信号灯,灯的颜色变化序列依次是红色-红色/黄色-绿色-黄色-红色。这个序列可以作为一个状态机器,交通信号灯的不同状态都紧跟着上一个状态。
    机器学习---算法---马尔科夫
  注意每一个状态都是唯一的依赖于前一个状态,所以,如果交通灯为绿色,那么下一个颜色状态将始终是黄色——也就是说,该系统是确定性的。确定性系统相对比较容易理解和分析,因为状态间的转移是完全已知的。

2、非确定性模式(Non-deterministic patterns):马尔科夫

  为了使天气那个例子更符合实际,加入第三个状态——多云。与交通信号灯例子不同,我们并不期望这三个天气状态之间的变化是确定性的,但是我们依然希望对这个系统建模以便生成一个天气变化模式(规律)。
  一种做法是假设模型的当前状态仅仅依赖于前面的几个状态,这被称为马尔科夫假设,它极大地简化了问题。显然,这可能是一种粗糙的假设,并且因此可能将一些非常重要的信息丢失。
  当考虑天气问题时,马尔科夫假设假定今天的天气只能通过过去几天已知的天气情况进行预测——而对于其他因素,譬如风力、气压等则没有考虑。在这个例子以及其他相似的例子中,这样的假设显然是不现实的。然而,由于这样经过简化的系统可以用来分析,我们常常接受这样的知识假设,虽然它产生的某些信息不完全准确。
          机器学习---算法---马尔科夫 机器学习---算法---马尔科夫 机器学习---算法---马尔科夫
  一个马尔科夫过程是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为n阶马尔科夫模型,其中n是影响下一个状态选择的(前)n个状态。最简单的马尔科夫过程是一阶模型,它的状态选择仅与前一个状态有关。这里要注意它与确定性系统并不相同,因为下一个状态的选择由相应的概率决定,并不是确定性的。
  下图是天气例子中状态间所有可能的一阶状态转移情况:
    机器学习---算法---马尔科夫
  对于有M个状态的一阶马尔科夫模型,共有M^2个状态转移,因为任何一个状态都有可能是所有状态的下一个转移状态。每一个状态转移都有一个概率值,称为状态转移概率——这是从一个状态转移到另一个状态的概率。所有的M^2个概率可以用一个状态转移矩阵表示。注意这些概率并不随时间变化而不同——这是一个非常重要(但常常不符合实际)的假设。
  下面的状态转移矩阵显示的是天气例子中可能的状态转移概率:
    机器学习---算法---马尔科夫
  -也就是说,如果昨天是晴天,那么今天是晴天的概率为0.5,是多云的概率为0.375。注意,每一行的概率之和为1。
  要初始化这样一个系统,我们需要确定起始日天气的(或可能的)情况,定义其为一个初始概率向量,称为pi向量。
          机器学习---算法---马尔科夫
  -也就是说,第一天为晴天的概率为1。
我们定义一个一阶马尔科夫过程如下:
   状态:三个状态——晴天,多云,雨天。
   pi向量:定义系统初始化时每一个状态的概率。
   状态转移矩阵:给定前一天天气情况下的当前天气概率。

任何一个可以用这种方式描述的系统都是一个马尔科夫过程。

 

 转自:http://blog.sina.com.cn/s/blog_14167e8810102x7nd.html

3、马尔科夫模型

随机过程最早是用于统计物理学的数学方法,研究空间粒子的随机运动。后来这门科学蓬勃发展,随机过程应用的领域越来越广。这里介绍随机过程的一种——马尔科夫链模型。

马尔科夫的无后效性:系统在t>t0时刻所处的状态与系统在t0时刻以前的状态无关,这就是马尔科夫性或者无后效性。

马尔科夫模型具体公式描述如下

 

有随机过程{Xn,n为整数},对于任意n和I0,I1,In,满足条件概率:
机器学习---算法---马尔科夫

就称为马尔科夫链。

但凡学过概率论的对这个条件概率应该都能看懂吧!

 

4、举例说明

 

下面是一个马尔科夫模型在天气预测方面的简单例子。如果第一天是雨天,第二天还是雨天的概率是0.8,是晴天的概率是0.2;如果第一天是晴天,第二天还是晴天的概率是0.6,是雨天的概率是0.4。问:如果第一天下雨了,第二天仍然是雨天的概率,第十天是晴天的概率;经过很长一段时间后雨天、晴天的概率分别是多少?

 

机器学习---算法---马尔科夫

 

首先构建转移概率矩阵,初学者很容易构建错误:

 

雨天

晴天

 

0.8

0.4

雨天

0.2

0.6

晴天

 

 

 

 

 

 

 

 

 

注意:每列和为1,分别对雨天、晴天,这样构建出来的就是转移概率矩阵了。

 

机器学习---算法---马尔科夫

 

初始状态第一天是雨天,我们记为

 

机器学习---算法---马尔科夫

 

这里【1,0】分别对应于雨天,晴天。

 

初始条件:第一天是雨天,第二天仍然是雨天(记为P1)的概率为:

 

 

P1 = AxP0

 

得到P1 = 【0.8,0.2】,正好满足雨天~雨天概率为0.8,当然这根据所给条件就是这样。

 

 

 

下面计算第十天(记为P9)是晴天概率:

 

机器学习---算法---马尔科夫

 

 

 

>> A= [0.8 0.4;0.2 0.6];

 

>> p = [1;0];

 

>> for i = 1:9

 

p = A*p;

 

end

 

>> p

 

 

 

p =

 

 

 

    0.6668

 

    0.3332

 

得到,第十天为雨天概率为0.6668,为晴天的概率为0.3332。

 

下面计算经过很长一段时间后雨天、晴天的概率,显然就是公式(1.1)

 

机器学习---算法---马尔科夫

 

直接算A的n次方显然不行,我们知道任意一个可逆矩阵总可以化为(1.2)形式。其中,T为A的特征值对应的两个特征向量组成的矩阵,这两个特征向量分别为【2,1】、【1 -1】。D为一个对角矩阵(1.4)。

 

那么,我们可以这样算,就简单多了:

 

机器学习---算法---马尔科夫

 

显然,当n趋于无穷即很长一段时间以后,Pn = 【0.67,0.33】。即雨天概率为0.67,晴天概率为0.33。并且,我们发现:初始状态如果是P0 =【0,1】,最后结果仍然是Pn = 【0.67,0.33】。这表明,马尔科夫过程与初始状态无关,跟转移矩阵有关。

 

 

下面,简单验证一下,分别求第50天,100天,1000天时,Pn的取值情况是否与理论一致:Pn = 【0.67,0.33】。
机器学习---算法---马尔科夫

 

 

 

p =

 

 

 

    0.6667

 

    0.3333

 

 

 

 

 

p =

 

 

 

    0.6667

 

    0.3333

 

 

 

 

 

p =

 

 

 

    0.6667

 

    0.3333

 

        可以看出第50天时与第1000天在0.00001精度下是一样的,最终结果与理论值Pn = 【0.67,0.33】一致。马尔科夫过程与初始状态无关,跟转移矩阵有关。