1）简单内部类

1
2
3
4
5
6
7
8

module ActiveSupport::Concern
  .....
  class MultipleIncludedBlocks < StandardError #:nodoc:
    def initialize
      super "Cannot define multiple 'included' blocks for a Concern"
    end
  end
end

ActiveSupport::Concern简单定义了一个内部的错误类型， 这个自定义错误类型主要用于提醒我们在扩展了ActiveSupport::Concern的模块中

只能够显式调用模块方法ActiveSupport::Concern::included一次，

第二次调用的话就会抛出这个自定义的错误类型。

2）设置“胎记”

我们前面说过扩展了ActiveSupport::Concern的模块我把它简称为依赖模块，那我们怎么知道一个模块是不是依赖模块呢？答案就在这个类方法。

1
2
3
4
5
6

module ActiveSupport::Concern
  .....
  def self.extended(base) #:nodoc:
    base.instance_variable_set(:@_dependencies, [])
  end
end

写过Ruby的应该都知道，这个是当一个模块被扩展(extend)之后就会被调用的一个回调方法，

并以扩展它的模块做为参数(base)传入该回调方法。

当一个模块扩展了ActiveSupport::Concern之后就会在模块内部设置一个实例变量

@_dependencies并设置为空数组，我们姑且把它看做是ActiveSupport::Concern的“胎记”，

后面我们会利用这个“胎记”所包含的依赖项，优雅地增强我们的终端模块。

3) 收集并扩展相关方法

在分析后面的方法之前我们先来简单看一下的原理。

我们都知道在Ruby里面如何定义一个类，并且定义相关的类方法，和实例方法

（我们只需要用class关键字就能够很容易做到这一点），但不知道大家是否了解还有这样一种方式？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

instance_block = Proc.new do
  def instance_method
    puts "I am instance method"
  end

  def self.class_method_in_instance_block
    puts "I am class method in instance block"
  end
end

class_block = Proc.new do
  def class_method
    puts "I am class method"
  end
end


Example = Class.new

Example.class_eval(&instance_block)
ClassModule = Module.new
ClassModule.module_eval(&class_block)
Example.extend(ClassModule)

Example.class_method
Example.class_method_in_instance_block
Example.new.instance_method

运行结果

I am class method I am class method in instance block I am instance method

运行结果有点意思，下面简单来分析一下: 我们以代码块的方式收集了类方法class_method，class_method_in_instance_block，

以及实例方法instance_method。然后我们创建一个空的类Example，

用Class#class_eval方法来打开类，在类的上下文环境下运行块instance_block，

其实这就相当于我们在类上下文中运行相应的语句，这样就能够得到Example#instance_method,

Example::class_method_in_instance_block这两个方法了。 另外，我们从已有的知识中了解到，可以通过Class#extend扩展模块的方式来获得类方法。

为此我们可以把class_block这个代码块包裹在模块ClassModule中，

最后我们只需要扩展(extend)这个模块就可以得到相应的类方法Example#class_method了。

ActiveSupport::Concern其实就是这种黑科技，

这里我简单把接下来的过程分为两部分

1）收集方法。

2）对收集的方法进行功能扩展

1. 方法收集 来看看依赖模块如何收集方法的？

1
2
3
4
5
6
7
8
9
10
11
12

module ActiveSupport::Concern
  .....
  def included(base = nil, &block)
    if base.nil?
      raise MultipleIncludedBlocks if instance_variable_defined?(:@_included_block)

      @_included_block = block
    else
      super
    end
  end
end

首先我们来看ActiveSupport::Concern#included，

当ActiveSupport::Concern被扩展之后这个included方法就会变成相应模块的类方法了。

咦，这不是一个模块被包含之后才会被调用的回调函数吗？没错，为了不影响它原来的功能rails团队采用了个巧妙的做法，

当我们在扩展了ActiveSupport::Concern的模块的上下文中显式调用included方法，

并且不带任何参数而只传入代码块的情况下，便会在模块内部设置一个@_included_block实例变量来接收这个代码块，

换句话说这个实例变量就是我们将来需要在终端模块上下文运行的代码块。

而在其他情况下则通过super关键字来调用原始版本的included方法。

这样既增强了included方法又不影响原始方法的使用。

另外我们也注意到了，在一个模块里面included方法只能被显式调用一次，

否则会抛出MultipleIncludedBlocks这个自定义的错误，这便是前面定义的内部类的应用场景。

OK，收集完需要在模块上下文运行的代码，我们接下来要收集类方法了。

1
2
3
4
5
6
7
8
9
10

module ActiveSupport::Concern
  .....
  def class_methods(&class_methods_module_definition)
    mod = const_defined?(:ClassMethods, false) ?
      const_get(:ClassMethods) :
      const_set(:ClassMethods, Module.new)

    mod.module_eval(&class_methods_module_definition)
  end
end

其实这个东西跟前面的included方法原理差不多，也是通过代码块来收集方法，只是有一点点不同，

我们需要把这个收集到的代码块包裹到一个模块中，以后再扩展这个模块。

首先通过const_defined?来判断常量ClassMethods是否存在，

该方法的第二个参数false表示只从当前模块查找该常量，而不会从祖先链中去查找。

如果没有则以ClassMethods为名定义一个模块，

然后以Module#module_eval方法打开该模块并在模块的上下文运行我们所接收的代码块class_methods_module_definition。

这样模块ClassMethods就会包含对应的方法了。

在以后的日子里我们只需要扩展ClassMethods，该模块里面的方法就能成为目标模块的类方法了。

1. 功能增强 收集完相关功能之后可以来看如何增强我们的终端模块了。在分析代码之前，

先来认识一下append_features，我们需要知道的是它会在模块被包含的时候调用，并且它会在included回调方法之前被调用。

接下来我们看看扩展功能的源代码，它应该是ActiveSupport::Concern里面最复杂的方法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

module ActiveSupport::Concern
  ....
  def append_features(base)
    if base.instance_variable_defined?(:@_dependencies)
      base.instance_variable_get(:@_dependencies) << self
      return false
    else
      return false if base < self
      @_dependencies.each { |dep| base.include(dep) }
      super
      base.extend const_get(:ClassMethods) if const_defined?(:ClassMethods)
      base.class_eval(&@_included_block) if instance_variable_defined?(:@_included_block)
    end
  end
end

现在我们可以看到之前设置“胎记”起作用了，设置了“胎记”的依赖模块也可以被其他的依赖模块所包含，

但他们并不会进行相应的功能扩展，他们会做的只是在“胎记”列表@_dependencies里面添加对应的依赖选项。

然后返回false。这也是我们第一个条件分支的逻辑。 当我们的依赖模块终于被终端模块（不含“胎记”的模块）包含的时候我们程序便可以走else分支的逻辑。

如果该依赖模块已经在终端模块的祖先链中的话则表明这个模块已经在终端模块增强过了，我们就没必要做重复工作，直接返回false。

否则的话继续执行后面的代码，接下来这个语句有点意思 @_dependencies.each { |dep| base.include(dep) }

我们会以终端模块的身份去包含当前依赖模块的@_dependencies列表里面的所有模块，

这个时候我们@_dependencies的模块又会进入各自相应的append_features方法，并且都会走else分支，

然后查看各自@_dependencies接下来又会以终端模块的身份再去包含列表里的那些模块，

以此类推。这递归的过程就像是链式反应，这样就能保证不管各个依赖模块之间的依赖关系如何，

我们的终端模块都不用太过在意了，反正最后都会被我们终端模块给包含掉。

接下来调用super关键字来调用原始的append_features方法，保证了原始的功能。

毕竟我们这里做的是对原始功能加强，而并不是要复写掉原始功能。

最后我们在每一个依赖模块内部都会执行大家所熟悉的语句 base.extend const_get(:ClassMethods) if const_defined?(:ClassMethods) base.class_eval(&@included_block) if instance_variable_defined?(:@included_block)

最最最后，咱们的终端模块就会具备我们预先定义好的类方法，实例方法。

并且可以直接运行一些预先定义好需要在模块上下文运行的类方法了。

优雅的Ruby

源码分析暂时告一段落，为了让我们对ActiveSupport::Concern印象更加深刻一些。最后我用一个简单的例子来展示一下这个库的优雅之处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

require 'active_support'

module A
  extend ActiveSupport::Concern

  included do
    def number1
      "number1 method"
    end
  end

  class_methods do
    def active1
      "active1 class method"
    end
  end
end

module B
  extend ActiveSupport::Concern
  include A

  included do
    def number2
      "number2 method"
    end
  end

  class_methods do
    def active2
      "active2 class method"
    end
  end
end

module C
  extend ActiveSupport::Concern
  include B

  included do
    def number3
      "number3 method"
    end

    def number2
      "number2 in C"
    end
  end

  class_methods do
    def active3
      "active3 class method"
    end

    def active2
      "active2 in C"
    end
  end
end

class Example
  include C
end

p "#{A.instance_variable_get("@_dependencies")}"
p "#{B.instance_variable_get("@_dependencies")}"
p "#{C.instance_variable_get("@_dependencies")}"

puts Example.active3
puts Example.active2
puts Example.active1

puts Example.new.number3
puts Example.new.number2
puts Example.new.number1

最后的打印结果是

“[]” “[A]” “[B]” active3 class method active2 in C active1 class method number3 method number2 in C number1 method

利用ActiveSupport::Concern我们可以用少量的代码，优雅地定义我们的扩展模块，并在需要的时候进行功能增强。

在该例子中我通过打印“胎记”可以知道依赖模块之间的依赖关系，

而且他们之间的依赖关系终端模块根本不会在意，它只需要包含一个依赖模块，

便可以得到有依赖关系其他依赖模块中所定义的功能了。

另外，我在模块C中做了些手脚，复写了它所依赖的模块B中所收集的方法，

是为了展示我们所收集方法在各个有依赖关系模块中的优先级关系。



文本建模算法入门（一）

0x1 文本建模

文本并不像其他数值型的数据一样可以比较轻易的通过运算、函数、方程、矩阵等来表达他们之间的相互关系。

在处理一篇文本的时候，假设每一个文本储存为一篇文档，那么从人的视角来看，这可以说是一段有序的词序列 $$Document=(w_1,w_2,...,w_n)$$
统计学家将这些序列的生成，生动地描绘成了一个“上帝的游戏”，即人类产生的所有语料的文本都可以看作是：一个伟大的上帝在天堂中掷骰子形成的。我们所看到的文本其实就是这个游戏掷了若干次后产生的序列。

那么，在这个游戏中，我们最需要关注的两个核心问题就出现了：

1. 上帝有怎样的骰子？
2. 上帝是怎么掷的骰子？

对应这两个问题，各大学家持着不同的观点，于是便有了以下三种模型：

1. Unigram Model
2. Topic Model(PLSA)
3. LDA

0x11 Unigram Model

Unigram Model是非常简单直接的，它假设

1. 上帝只有一个V面的骰子，每一个面对应一个词，同时每个面的概率不一样。（这里可以通过“老千骰子”来理解下，有些面因为被做过了“手脚”，所以抛到的几率就大了，那如果没个面都这样，那么每个面抛到的几率也就不一样了）
2. 每抛一次骰子，抛出的面就对应有一个词，那么抛n次骰子后，按抛掷顺序产生的序列就生成了一篇n个词的文档

那现在我们把上帝这个唯一的骰子各个面的概率记为$\vec{p}=\{p_1,p_2,...,p_v\}$，然后我们把掷这个V面骰子的实验记作$w \sim Mult(w|\vec{p})$

那么对应一篇文档d，该文档生成的概率就是
$$p(\vec{w})=p(w_1,w_2,...,w_n)=p(w_1)p(w_2)...p(w_n)$$

而文档和文档之间我们认为是独立的，所以如果语料中有多篇文档$W=(\vec{w_1},\vec{w_2},...,\vec{w_m})$，则该语料生成的概率就是 $$p(W)=p(\vec{w_1})p(\vec{w_2})...p(\vec{w_m})$$

在Unigram Model中，我们又假设了文档之间是独立可交换的。即，词与词之间的顺序对文档表示并不造成影响，一篇文档相当于一个袋子，里面装着一些词。这样的模型也称为词袋模型（Bag-of-words）。

那么，如果语料中的总词频是N，在N个词中，如果我们关注每一个词$w_i$的发生次数$n_i$，则$\vec{n}=(n_1,n_2,...,n_V)$正好是一个多项分布
$$p(\vec{n})=Mult(\vec{n}|\vec{p},N)$$
此时，语料的概率是
$$p(W)=p(\vec{w_1})p(\vec{w_2})...p(\vec{w_m})=\prod_{k=1}^Vp_k^{n_k}$$

0x110 贝叶斯Unigram Model假设

在贝叶斯统计学派看来，上帝拥有唯一一个固定的骰子是不合理的。于是他们觉得以上模型的骰子$\vec{p}$不应该唯一固定，而应该也是一个随机变量。

那这样我们就可以将整个掷骰子的游戏过程更新成以下形式：

1. 上帝有一个装着无穷多骰子的罐子，里面有各种骰子，每个骰子有V个面。每一个面对应一个词
2. 上帝从罐子抽出一个骰子，然后用这个骰子不断的抛，每抛一次骰子，抛出的面就对应有一个词，那么抛n次骰子后，按抛掷顺序产生的序列就生成了一篇n个词的文档
   

在以上的假设之下，由于我们事先并不知道上帝用了哪个骰子$\vec{p}$，所以每个骰子都是有可能被使用的，只是使用的概率由先验分布$p(\vec{p})$决定，对每一个具体的骰子$\vec{p}$，由该骰子产生数据的概率是$p(W|\vec{p})$，所以最终数据产生的概率就是对每个骰子上产生的数据概率进行积分累加求和
$$P(W)=\int p(W|\vec{p})p(\vec{p})d\vec{p}$$
在贝叶斯分析的框架之下，此处的先验分布概率其实就是一个多项分布的概率，其中一个比较好的选择即多项分布对应的共轭分布：Dirichlet分布

0x12 PLSA Topic Model

再来回顾Unigram Model我们发现：这个模型的假设过于简单，和人类真实的书写有着较大的差距

从人类视角看，我们在日常构思文章中，我们往往要先确定自己文章的主旨，包含了哪些主题，然后再围绕着这些主题展开阐述。

例如，一篇关于现代教育的文章，它可能就包含了这些主题：教育方法、多媒体技术、互联网等。篇幅上可能以教育方法为主，而其他为辅。然后，在不同的主题里面就包含了许多主题领域内常见的关键词。例如，谈到互联网时，我们会提及Web、Tcp等。

这样一种直观的想法就在PLSA模型中进行了明确的体现，如果我们再利用这个想法更新“掷骰子”的游戏就有以下情形：

1. 上帝有两种类型骰子，一类是doc-topic骰子，骰子共k个面代表了k个主题；一类是topic-word骰子，骰子V个面，每面对应主题内的一个词
2. 生成文章的时候，首先要先创造一个特定的doc-topic骰子，使得骰子内的主题围绕文章要阐述的主题
3. 投掷doc-topic骰子，得到一个主题z
4. 根据得到的主题z，找到对应的topic-word骰子，投掷它得到一个词
5. 不断重复3，4步，直至文章生成完成

在上面的游戏规则中，文档与文档之间顺序无关，同一个文档内的词的顺序也是无关的。所以还是一个bag-of-words模型。

那么，在第m篇文档Dm中每个词的生成概率为：
$$p(w|D_m)=\sum^K_{z=1}p(w|z)p(z|D_m)=\sum^K_{z=1}\phi_{zw_i}\theta_{dz}$$
$\phi_{zw_i}$:对应游戏中K个topic-word骰子中第z个骰子对应的词列表

$\theta_{dz}$:文档对应的第z个主题，即对应的doc-topic

所以整篇文档的生成概率就为：
$$p(w|D_m)=\prod^n_{i=1}\sum^K_{z=1}p(w_i|z)p(z|D_m)$$

0x13 LDA(Latent Dirichlet Allocation)

就像Unigram Model 加入贝叶斯框架那样，doc-topic和topic-word都是模型的参数，即随机变量。于是类似对Unigram Model的改造对以上两个骰子模型加入先验分布。然后由于$\vec{\theta}$，$\vec{\phi}$都对应着多项分布，因此先验分布依旧选择Drichlet分布。于是得到的这个新模型就是LDA(Latent Dirichlet Allocation)模型

在LDA模型中，上帝的游戏规则就又被更新成如下情形：

1. 上帝有两个罐子，第一个装着都哦doc-topic骰子，第二个装着topic-word骰子
2. 上帝随机的从第二个罐子中独立抽出K个topic-doc骰子，编号1-K
3. 每次生成新文档时，从第一个罐子随机抽一个doc-topic骰子
4. 投掷得到的doc-topic骰子。得到一个主题编号z
5. 在K个主题骰子里面选择编号为z的骰子，投掷骰子，得到一个词
6. 重复4，5步，直至文档生成完成

0x2 后记

至此，入门篇（一）的内容就写到这了。由于是第一篇，文章中避过了许多较为复杂的数学证明和计算，尤其是关于LDA模型的。这样是为了，先建立对文本建模思路和过程的直观认识，而不是一上来就深究细节。

加上笔者目前也是在学习阶段，后面的细节再慢慢地一一补充，大家共同进步 !!
\(^_^)/

穷举搜索的例子－Google方程式

　问题描述

有一个由字符组成的等式，WWWDOT-GOOGLE = DOTCOM，每个字符代表一个0-9之间的数字，WWWDOT、GOOGLE和DOTCOM都是合法的数字，不能以零开头。请找出一组字符与数字的对应关系，使得他们可以互相转换，并且替换之后能够满足等式。

问题分析

从排列组合的角度来看，这道题是一道典型的排列组合问题，题目中一共出现了9个字母。

如果不考虑0开头的情况下，这样的组合应该有10x9x8x7x6x5x4x3x2=3628800种组合。

在这样的情况之下，计算机的穷举处理应该是毫无压力的。

问题求解

首先为了能够表示这样一种可变的字符元素列表，我们需要自定义一种数据结构。首先我们知道这个自定义结构中应该包含有三个属性，分别是 字符本身，字符代表的数字以及是否为数字的最高位，因为最高位是不能为0的，所以在这里我们要区别对待。

1
2
3
4
5
6

typedef struct tagCharItem
{
  char c;
  int value;
  bool leading;
}CHAR_ITEM;

接着我们初始化这个列表。=

1
2
3
4
5

CHAR_ITEM charItem[]={
{'W',-1,true},{'D',-1,true},{'O',-1,true},
{'T',-1,false},{'G',-1,true},{'L',-1,false},
{'E',-1,false},{'C',-1,false},{'M',-1,false}
};

因为这是一个组合问题，那么两个字母就不能被指定为相同的数字，这样我们需要定义额外的占用标识。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

typedef struct tagCharValue
{
  bool isused;
  int value;
}CHAR_VALUE;

//穷举算法实现如下
void SearchingResult(CHAR_ITEM ci[],CHAR_VALUE cv[],
int index,CharListReadyFuncPtr callback)
{
if(index == max_char_count)
{
  callback(ci);
  return;
}
for(int i = 0;i<max_number_count;++i)
{
  if(IsValueValid(ci[index],cv[i]))
  {
      cv[i].isused= true;
      ci[index].value = cv[i].value;
      SearchingResult(ci,cv,index+1,callback);
      cv[i].isused = false;
  }
}
}

根据题目要求，W，G，D三者都不能为0，为了加快穷举速度可以对他们为0的情况进行剪枝。
IsValueValid是评估函数，在剪枝操作之后，callback的被调用次数可以减少约30%。

1
2
3
4
5
6
7
8
9
10
11
12
13

//callback代码实现
void OnCharListReady(CHAR_ITEM ci[])
{
  char * minuend = "WWWDOT";
  char * subtrahend = "GOOGLE";
  char * diff = "DOTCOM";
  int m = MakeIntegerValue(ci,minuend);
  int s = MakeIntegerValue(ci,subtrahend);
  int d = MakeIntegerValue(ci,diff);
  if((m-s)==d){
      std::cout << m << "-" <<s<< "=" << d << std::endl;
  }
}

问题答案
777589 - 188103 = 589486
777589 - 188106 = 589483



隐马尔可夫模型（HMM）的原理

简介

隐马尔可夫模型是一个基于马尔可夫链的统计模型。

马尔可夫链因安德烈·马尔可夫（Andrey Markov，1856－1922）得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。

虽然从维基百科上摘取下来的概念和定义看着十分的晦涩难懂，但是模型背后的思想是非常简单的，即：首先假设你的系统可以建模为马尔可夫链，然后，系统所发出的信号（输出的可见结果）仅取决于系统当前的状态。那么，隐马尔可夫模型代表的一种情景就是：系统的状态对你而言是不可见的，你仅仅只能观测到系统所发出的信号或者说是系统所输出的结果。

举个通俗易懂的栗子。

假设你有一个住在国外的朋友，他通常会根据天气来安排他的日常活动。你不知道他的国家那边的天气如何（系统的状态），但你确可以在跟他的聊天中知道他今天进行了什么活动（系统的输出），然后这就是一个简单的隐马尔可夫模型。

我们将整个模型

现在有三个比较关键的问题有待我们解决：
1. 知道整个模型后，你朋友告诉你他这三天的活动是：散步（Walk），购物（Shop），清洁屋子（Clean），那么根据模型，计算产生这些行为序列的概率是多少？
2. 知道整个模型后，朋友让你根据他的活动猜一猜他那边这三天天气怎么样
3. 朋友告诉你三天里他做了些什么，然后让你找出他活动规律的模型。

为了解决以上的问题我们首先要了解一些有关HMM的基本元素先：

初始概率分布$\pi$：初始概率分布即事件初始时发生的概率，我们这里隐藏的状态是天气，然后我们在图中可以看出的初始概率有：天气为晴天的概率为0.8 ; 天气为雨天的概率为0.2

转移概率矩阵P：转移功率矩阵就可以通过一副图来描述了。

其中，列参数表示第一天的状态，行参数表示第二天状态。表格中的第一行的含义就是已知第一天为晴天，那么第二天为晴天的概率是0.7，而为雨天的概率只是0.3。

观测量的概率分布B：在这个问题中观测量就是朋友的活动，其概率分布就分别表示为朋友在晴天和雨天的情况下进行散步，购物，打扫屋子各项活动的可能性（概率）。

现在，我们再次回到上面提到的三个问题。其实，每个问题的解决解决在历史上早有前人给出了算法。

问题1 -> Forward Algorithm，向前算法 或 Backward Algorithm，向后算法。

问题2 -> Viterbi Algorithm，维特比算法。

问题3 -> Baum-Welch Algorithm，鲍姆-维尔奇算法。

算法思路

假设前提：
已知，雨天，朋友选择去散步，购物，收拾的概率分别是0.1，0.4，0.5， 而如果是晴天，选择去散步，购物，收拾的概率分别是0.6，0.3，0.1。
三天活动序列：散步（Walk），购物（Shop），清洁屋子（Clean）

Forward Algorithm

然后我们先计算 t = 1 时，发生 “散步” 行为的概率，如果下雨，则$P(Walk,Rain) = P_{t=1}(Rain) * P(Walk|Rain) = 0.2 \times 0.1 = 0.02$；如果为晴天，则$P(Walk,Sunny) = 0.8 \times 0.6 = 0.48$

t = 2 时，发生 “购物” 的概率，如果 t = 2 下雨，则$P(Walk_{t=1},Shop_{t=2},Rain_{t=2}) = [P(Walk_{t=1},Rain_{t=1}) \times P(Rain_{t=2}|Rain_{t=1}) \\ + P(Walk_{t=1},Sunny_{t=1})\times P(Rain_{t=2}|Sunny_{t=1})]\times P(Shop_{t=2}|Rain_{t=2}) \\ = [0.02*0.4+0.48*0.3]*0.4 = 0.0608$

如果为晴天，则

$P(Walk_{t=1},Shop_{t=2},Sunny_{t=2}) = [0.02*0.6 +0.48*0.7]*0.3 = 0.1044$

t = 3 时的算法也可以依此类推，
$P(Walk_{t=1},Shop_{t=2},Clean_{t=3},Rain_{t=3}) = [0.0608*0.4+0.1044*0.3]*0.5 = 0.02782$；
$P(Walk_{t=1},Shop_{t=2},Clean_{t=3},Sunny_{t=3}) = [0.0608*0.6+0.1044*0.7]*0.7 = 0.076692$

所以，最终：
$P(Walk_{t=1},Shop_{t=2},Clean_{t=3}) = 0.02782 + 0.076692 = 0.104512$

从上面的例子可以看出，向前算法计算了每个时间点时，每个状态的发生观测序列的概率，看似复杂，但在T变大时，复杂度也会随之降低。

Backward Algorihm

既然，向前算法是在时间 t = 1 的时候，一步一步向前计算。那么反过来，向后算法就是从最后一个状态往前推。
假设最初时$\beta_3(Rain) = 1；\beta_3(Sunny) = 1$

那么：

$\beta_2(Rain) = a_{Rain \to Rain}b_{Rain}(O_3=Clean)\beta_3(Rain) \\+ a_{Rain \to Sunny}b_{Sunny}(O_3=Clean)\beta_3(Sunny)\\=0.4*0.5*1+0.6*0.1*1 = 0.26$
其中第一项则是转移概率，第二天下雨转到第三天下雨的概率为0.4；第二项则是观测概率，第三天下雨的状况下，在家收拾的概率为0.5；第三项就是我们定义的向后变量（backward variable）。

同理也可推得其他数据，并且最终答案与向前算法的求解相同。

Viterbi Algorithm（维比特算法）

利用动态规划求解概率最大的路径（最优路径）。利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图（Lattice）的最短路径提出的。

我们假设用符号$x_{ij}$来表示系统的第 i 种状态$x_i$的第j个可能的值。如果把每个状态按照不同的值展开，就可以得到以下的篱笆网络（Lattice）：

那么从第一个状态到最后一个状态的任何一条路径（path）都可能产生我们观察到的输出序列Y。当然，这些路径的可能性不一样，而我们要做的就是找到最可能的这条路径。对于每一条给定的路径我们都可以用公式:

$x_1,x_2,...,x_N = \text{ArgMax}\left[P\left(x_1,x_2,...,x_N|y_1,y_2,...,y_N\right)\right(x \in X)]\\=\text{ArgMax}\left[\prod _{i=1}^N P\left(x_i|x_{i-1}\right)P\left(y_i|x_i\right)\right (x \in X)]$

计算出它的可能性，但是随着组合增多，它使得序列状态数的增长呈指数爆炸式。

为了解决这个问题，需要一个最好能和状态数成正比的算法。也就是我们要讲的维特比算法。

维特比算法的基础可以概括成三点：

1. 如果概率最大的路径P（或者说最优路径）经过某个点，如果上图中的$x_{22}$，那么这条路径上从起始点S 到 $x_{22}$的这一段子路径Q，一定是S到$x_{22}$的最短路径。否则用S到$x_{22}$的最短路径R来代替Q，便构成了一条比P更短的路径。

2. 从S到E的路径必定经过第i个时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所以k个节点的最短路径，最终最短路径必经过其中的一条。这样，在任何时刻，只要考虑非常有限条最短路径即可。

3. 结合上述两点，假定当我们从状态 i 进入状态 i + 1 时，从 S 到状态 i 上各个节点的最短路径已经找到，并且记录在这些节点上，那么在计算从起点 S 到第 i + 1 状态的某个节点$x_{i+1}$的最短路径时，只要考虑从S到前一个状态 i 所有的 k 个节点的最短路径，以及从这 k 个节点到$x_{i+1}$，j 的距离即可。

实现过程

1. 从点S出发，对于第一个状态$x_1$的各个节点，不妨假定有$n_1$个。计算出 S 到它们的距离$d(S，x_{1i})$,其中$x_{1i}$代表任意状态 1 的节点。因为只有一步，所以这些距离都是S到它们各自的最短距离。
2. 对于第二个状态$x_2$的所有节点，要计算出从S到它们的最短距离。我们知道，对于特定的节点$x_{2i}$，从S到它的路径可以经过状态1的$n_1$中任何一个节点$x_{1i}$，当然，对应的路径长度就是$d(S,x_{2i}) = d(S,x_{1j}) + d(x_{1j},x_{2j})$。由于 j 有$n_1$种可能性，我们要一一计算，然后找到最小值。即：$d(S,x_{2i}) = min_{i=1,n_1}d(S,x_{1j}) + d(x_{1j},x_{2j})$
3. 这样对于第二状态的每个节点，需要$n_1$次乘法计算。假定这个状态有$n_2$个节点，把S这些节点的距离都算一遍，就有$O(n_1 * n_2)$次计算。

接下来，类似地按照上述方法从第二个状态走到第三个状态，一直走到最后一个状态，就得到了整个网格从头到尾的最短路径。每一步计算的复杂度都和相邻两个状态$S_i和S_{i+1}$各自的节点数目$n_i，n_{i+1}$的乘积成正比，即$O(n_i,n_{i+1})$。如果假定在这个隐含马尔可夫链中的节点最多的状态有D个节点，也就是说整个网络的宽度为D，那么任何一布的复杂度不超过$O(D^2)$,由于网络长度是N，所以整个维特比算法的复杂度是$O(N*D^2)$ ——本段推理节选自<<数学之美>>第二版