flaght / blog Goto Github PK

• 概念:观测值与状态不是一一对应的，而是通过 一组概率分布相联系。HMM 是一个双内嵌式随机过程，即 HMM 是由两个随机过程组成，一个是隐含的状态转移序列，它对应一个单纯的 Markov 过程;另一个则是与隐状态有关的观测序列。并且在这两个随机过程中， 有一个随机过程(状态转移序列)是不可观测的，只能通过另一个随机过 程的输出观测序列进行推断，所以称之为隐马尔可夫模型

• HMM模型的基本要素:

  • (1) 模型的状态数N。如果S是状态集合，则S={$S_{1},S_{2},S_{3},...S_{N}$}。模型在时间t的状态记为$q_{t}$∈S, 1 ≤ t ≤ T，T是观察序列的长度。模型经历的状态序列记为Q={$q_{1}$,$q_{2}$,...$q_{t}$}.

  • (2) 观察符号数M。设V是所有观察符号的集合，则V={$v_{1}$,$v_{2}$,...$v_{M}$}

  • (3) 状态转移的概率分布A。状态转移的概率分布可表示为A=$a_{ij}$,其中，A = P{$q_{t+1}$=$S_{j}$|$q_{t}$=$S_{i}$}, 1≤i,j≤N,且满足$a_{ij}$≥0, $ \sum_{i=1}^{n}a_{ij}$,表示时刻t从状态$S_{i}$转移到时刻t+1状态$S_{j}$的转化概率

  • (4) 状态$S_{i}$条件下输出的观测变量概率分布B。假设观测变量的样本空间为V，在状态$S_{i}$时输出观测变量的概率分布可表B={$b_{i}$(v),1≤i≤N,v∈V},其中，$b_{i}$(V)=P{$Q_{t}$=v|$q_{t}$=$S_{t}$},$Q_{t}$为时刻t的观测随机变量，可以是一个数值或向量，观测序列记为O={$Q_{1}$,$Q_{2}$,...$Q_{t}$}。值得注意的是，此处观测变量的样本空间和概率分布式可以为离散型，也可以为连续型。

  • (5) 系统初始状态概率分布$\pi_{i}$，系统初始状态概率分布可表示为$\pi_{i}$={$\pi_{i}$，1≤i≤N},其中, $\pi_{i}$=P{$q_{1}$=$S_{i}$}

  综上所述，要描述一个完整的HMM，需要的确定模型参数{N,M,A,B,$S\pi$},为了简化,常用下面的形式来表示，即λ ={A,B,$S\pi$}.此外，对于一个标准的HMM模型，需要解决模型训练，隐含态估计和似然计算三个基本问题。

• HMM模式识别模型关键算法:
  隐马尔科夫模型(HMM)应用到实际中，需解决三个问题:

  • 问题1: 知道隐含状态数量，转换概率，根据可见状态链，求得结果的概率

    • 给定模型参数λ={M,N,A,B,π}和观测序列O=($O_{1},O_{2},O_{3},...O_{T}$)，如 何快速求出在该模型下，观测序列发生的概率P(O|λ)?
      • 1. 向前算法
           给定模型λ产生某一状态序列Q = {$q_{1}$,$q_{2}$,$q_{3}$,.....$q_{t}$}的概率为P(O|λ),使用向前-向后算法对P(O|λ)进行求解如下:
        • 首先,定义前向变量：$a_{t}$(i) = P($o_{1}$,$o_{2}$,$o_{3}$,.....$o_{t}$,$q_{t}$ = $s_{i}$|λ),$a_{t}$(i)可按如下步骤进行迭代计算:
          • 1. 初始化: $a_{1}$(i) = $\pi_{i}b_{i}$($o_{1}$) (1≤i≤N);
          • 2. 递归计算:
               $a_{t+1}$(j) = [$\sum_{i=1}^{N}a_{t}$(i)$a_{ij}$]$b_{j}$($O_{t+1}$), 1≤t≤T-1; 1≤j≤N;
          • 3. 终止:
               P(O|λ) = $\sum_{i=1}^{N}a_{T}$(i)
      • 2. 向后算法
           其实，类似地定义后向变量:$\beta_{T}$(i)=P($O_{t+1},O_{t+2},O_{t+3},...O_{T}$|$q_{t}$=i,λ),($O_{t+1},O_{t+2},O_{t+3},...O_{T}$)表示从终止时刻T到时刻t+1的观测事件序列，则$\beta_{T}$(i)按如下步骤进行迭代机计算:
           • 1. 初始化: $\beta_{T}$(i) = 1 (1≤i≤N);
           • 2. 递归计算:
                $\beta_{t}$(i) = $\sum_{j=1}^{N}a_{ij}b_{j}$($o_{t+1}$)$\beta_{t+1}$(j), t=T-1,T-2,...,1; 1≤i≤N;
           • 3. 终止:
                P(O|λ) = $\sum_{i=1}^{N} \pi\beta_{1} $(i)
           • 4)则给定模型λ下，产生状态序列Q={$q_{1}$,$q_{2}$,$q_{3}$,.....$q_{t}$}的概率为
             P(O|λ) = $\sum_{i=1}^{N} \pi\beta_{1} $(i)

  • 问题2: 知道隐含状态数量，转换概率，根据可见状态链，求得隐含状态链

    • 给定模型参数λ={M,N,A,B,π}和观测序列O=($O_{1},O_{2},O_{3},...O_{T}$)，如何找出对应的最佳状态序列S=($S_{1},S_{2},S_{3},...S_{N}$)?

    • 给定观测序列 O 以及模型λ，如何选择对应的状态序列Q=($q_{1},q_{2},q_{3},...q_{t}$), 使得Q能够最为合理的解释观测序列O?

      首先定义:$\delta_{t}$(i) = max P[$q_{1},q_{2},q_{3},...q_{t-1}$, $q_{t}=i$, $o_{1},o_{2},o_{3}...o_{t}$|λ],我们所要找的就是T时刻最大的$\delta_{T}$(i)所代表的那个状态序列。可使用运用Viterbi算法求解Q，步骤如下:

      • 1. 初始化:
      $$\delta_{t}(i) = \pi_{i}b_{i}(o_{1});$$
      • 2. 递归计算:
      $$\delta_{t}(j) = max[\delta_{t-1}(i)a_{ij}]b_{j}(o_{t}) 1\le i \le N,2\le t \le T, 1 \le j \le T \Psi_{t}(j) = arg max[\delta_{t-1}(i)a_{ij}] 1\le i \le N,2\le t \le T, 1 \le j \le T$$
      • 3. 终结
      $$P^* = max[\delta_{T}(i)], q^*_{T} = arg max[\delta_{T}(i)] 1\le i \le N$$
      • 4. 求序列Q:
      $$q^*_{t} = \Psi_{t+1}(q^*_{t+1}) t=T-1,T-2,...,1$$

• 应用实例:

  • 场景描述:

    A现在在北京工作，而B在法国读书。每天下班之后，A会根据天气情况有相应的活动：或是去商场购物，或是去公园散步，或是回家收拾房间。AB有时候会通电话，A会告诉B,A这几天做了什么，B则要通过A的行为猜测这几天对应的天气最有可能是什么样子的。

    以上就是一个简单的 HMM，天气状况属于状态序列，而A的行为则属于观测序列。天气状况的转换是一个马尔可夫序列。而根据天气的不同，有相对应的概率产生不同的行为。在这里，为了简化，把天气情况简单归结为晴天和雨天两种情况。雨天，A选择去散步，购物，收拾的概率分别是0.1，0.4，0.5， 而如果是晴天，A选择去散步，购物，收拾的概率分别是0.6，0.3，0.1。而天气的转换情况如下：这一天下雨，则下一天依然下雨的概率是0.7，而转换成晴天的概率是0.3；这一天是晴天，则下一天依然是晴天的概率是0.6，而转换成雨天的概率是0.4. 同时还存在一个初始概率，也就是第一天下雨的概率是0.6， 晴天的概率是0.4.
    

  • 解决问题1实例:
    已知整个模型，我女朋友告诉我，连续三天，她下班后做的事情分别是：散步，购物，收拾。那么，根据模型，计算产生这些行为的概率是多少。

    • 向前算法:

      先计算 t=1时刻，发生『散步』一行为的概率，如果下雨，则为 P(散步，下雨)=P（第一天下雨）X P（散步 | 下雨）=0.6X0.1=0.06；晴天，P（散步，晴天）=0.4X0.6=0.24

      t=2 时刻，发生『购物』的概率，当然，这个概率可以从 t=1 时刻计算而来。

      如果 t=2晴天，则 P（第一天散步，第二天购物，第二天晴天）=0.0486 （同理可得，请自行推理）

      如果 t=3，下雨，则 P（第一天散步，第二天购物，第三天收拾，第三天下雨）=【P（第一天散步，第二天购物，第二天下雨）X P（第三天下雨 | 第二天下雨）+ P（第一天散步，第二天购物，第二天天晴）X P（第三天下雨 | 第二天天晴）】X P（第三天收拾 | 第三天下雨）=【0.0552X0.7+0.0486X0.4】X0.5= 0.02904

      如果t=3，晴天，则 P（第一天散步，第二天购物，第三天收拾，第三天晴天）= 0.004572

      那么 P（第一天散步，第二天购物，第三天收拾），这一概率则是第三天，下雨和晴天两种情况的概率和。0.02904+0.004572=0.033612.

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

      

    • 向后算法:
      顾名思义，向前算法是在时间 t=1的时候，一步一步往前计算。而相反的，向后算法则是倒退着，从最后一个状态开始，慢慢往后推。

      初始化：$\beta_{3}$(Rainy) = 1
      递推: $\beta_{2}$ = $a_{Rainy->Rainy}b_{Rainy}$($O_{3}$=Clean)$\beta_{3}$(Rainy)+$a_{Rainy->Sunny}b_{Sunny}$($O_{3}$=Clean)$\beta_{3}$(Sunny) = 0.7 * 0.5 * 1 + 0.3 * 0.1 * 1 =0.38

      其中第一项则是转移概率，第二天下雨转到第三天下雨的概率为0.7；第二项则是观测概率，第三天下雨的状况下，在家收拾的概率为0.5；第三项就是我们定义的向后变量（backward variable）
      同理推得:

      \beta_{2}(Sunny) = 0.26
      
      \beta_{1}(Rainy) = 0.1298
      
      \beta_{1}(Sunny) = 0.1076
      

      结束：P(散步，购物，收拾) =
      $\pi_{Rainy}b_{Rainy}$($O_{1}$=Walke)$\beta_{1}$(Rainy) + $\pi_{Sunny}b_{Sunny}$($O_{1}$=Walke)$\beta_{Sunny}$= 0.6×0.1×0.1298+0.4×0.6×0.1076 = 0.033612

      

  • 解决问题2实例:
    同样知晓这个模型，同样是这三件事，我女朋友要我猜，这三天她下班后北京的天气是怎么样的。这三天怎么样的天气才最有可能让她做这样的事情。

    • 维特比算法:致力于寻找一条最佳路径，以便能最好地解释观测到的序列。

      • 初始化:

       \delta_{1}(Rainy) = \pi_{R} * b_{R}(O_{1}=Walk) = 0.06
       
       \delta_{1}(Sunny) = \pi_{S} * b_{S}(O_{1}=Walk) = 0.24
      

      • 初始路径:

      \psi_{1}(Rainny) = 0
      
      \psi_{1}(Sunny) = 0
      

      • 递推:
        当然是要找出概率比价大的那条路径。

      \delta_{2}(Rainy) = max[\delta_{1}(R) * a_{R->R},\delta_{1}(S)*a_{S->R}] * b_{R}(O_{2} = Shop) = 0.0384
      

      那么第二天下雨的这一状态的最佳路径，应该是:

      \psi_{2}(Rainy) = arg max[\delta{1}(R) * a_{R->R}, \delta_{1}(S) * a_{S->R}] = Sunny
      

      也就是说，第一天是晴天的可能性更大。

      同样地，可以推得:

      \delta_{2}(Sunny) = 0.432
      
      \psi_{2}(Sunny) = Sunny
      
      \delta_{3}(Rainy) = 0.01344
      
      \psi_{3}(Rainy) = Rainy
      
      \delta_{3}(Sunny) = 0.002592
      
      \psi_{3}(Sunny) = Sunny
      

    结束:比较$\delta_{3}$(Rainy) and $\delta_{3}$(Sunny)的大小，发现前者较大，则最后一天的状态最有可能是下雨天。

    回推:根据$\psi_{3}$(Rainy) = Rainy可知,到达第三天下雨这一状态，最有可能是第二天也下雨，最根据$\psi_{3}$(Rainy) = Sunny可知，到达第二天下雨这一状态，最有可能的是第一天是晴天。

    确定最佳路径是，晴天，雨天，雨天。

项目名:backtest

项目名: mcrawler

项目名: BasicCore

项目名: mylib

• [ ]

高等数学上册-154页 第五节:函数极值与最大值最小值

• 定义: 设函数f(x)在$x_{0}$的某邻域U($x_{0}$)内有定义，如果对于去心邻域U($x_{0}$)内的任一 x,有

那么就称$f(x_{0})$是函数$f(x)$的一个极大值(或极小值)。函数的极大值与极小值统称为函数的极值，使函数取得极值的点成为极值点。

函数的极大值和极小值概念是局部性的，如果$f(x_{0})$是函数f(x)的一个极大值，那只是就$x_{0}$附近的一个局部范围来说，$f(x_{0})$是$f(x)$的一个最大值;如

• 根据费马引理可知，如果函数$f(x)$在$x_{0}$处可导，且$f(x)$在$x_{0}$处取得极值，那么$f'(x_{0})=0$.这就是可导函数取得极值的必要条件，现将此论述为如下定理:

  • 定理1(必要条件) 设函数$f(x)$在$x_{0}$处可导，且在$x_{0}$处取的极值，那么$f'(x_{0})=0$.

  定理1就是说:可导函数$f(x)$的极值点必定是它的驻点.但反过来,函数的驻点却不一定是极值点。例如:$f(x)$=$x^3$的导数$f'(x)$=$3x^2$, $f'(0)$=0,因此x=0是这可导函数的驻点，但x=0却不是这个函数的极值点。所以，函数的驻点只能是极值点。此外，函数在它的导数不存在的点出可能取得极值。

  • 定理2(第一充分条件) 设函数$f(x)$在$x_{0}$处连续，且$x_{0}$的某去心邻域U($x_{0},\psi$)内可导.

    • (1) 若x∈($x_{0} - \psi, x_{0}$)时，$f'(x) > 0$,而x∈($x_{0}, x_{0} + \psi$)时,$f'(x) < 0 $,则$f(x)$在$x_{0}$处取的极大值。

    • (2) 若x∈($x_{0} - \psi, x_{0}$)时，$f'(x) < 0$,而x∈($x_{0}, x_{0} + \psi$)时,$f'(x) > 0 $,则$f(x)$在$x_{0}$处取的极小值。

    • (3) 若x∈($x_{0},\psi$)时，$f'(x)$的符号保持不变，则$f(x)$在$x_{0}$处没有极值。

  定理2也可以简单地这样说:当x在$x_{0}$的邻近渐增地经过$x_{0}$时，如果$f'(x)$的符号由正变负，那么$f(x)$在$x_{0}$出取的极大值;如果$f'(x)$的符号由负变成正，那么$f(x)$在$x_{0}$处取得极小值；如果$f'(x)$的符号并不改变,那么$f(x)$在$x_{0}$处没有极值。

  • 根据上面两个定理，如果函数$f(x)$在所讨论的区间内连续，除个别点外处处可导，那么就可以按下列步骤来求$f(x)$在该区间内的极值点和相应的极值:

    • (1) 求出导出$f'(x)$;
    • (2) 求出$f(x)$的全部驻点与不可导点
    • (3) 考察$f'(x)$的符号在每个驻点或不可导点的左，右邻近的情形，以确定该点是否为极值点；如果极值点，进一步判断是否极大值点还是极小值点。
    • (4) 求出各极值点的函数值，就得函数$f(x)$的全部极值。

  • 定理3(第二充分条件) 设函数$f(x)$在$x_{0}$处具有二阶导数且$f'(x)$=0,$f''(x)$≠0，那么:

    • (1) 当$f''(x_{0})$ < 0时，函数$f(x)$在$x_{0}$处取的极大值
    • (2) 当$f''(x_{0})$ > 0时，函数$f(x)$在$x_{0}$处取的极小值