科学网—标签 - 马尔科夫

相关帖子	版块	作者	回复/查看	最后发表

luria 2019-8-8 22:19

本文接上一篇，继续探讨隐马尔科夫模型三个基本问题中最后一个问题，也是最复杂的一个问题。在此之前还是欢迎主角 HMM 登场！ 3. 隐马尔科夫模型的三个基本问题 Problem 3. 学习问题 ( Learning Problem) 已知观测序列 O=( o 0 , o 1 , o 2 , o 3 , …, o T-1 ) ，需通过调整 HMM 的参数λ = (A, B, π ) 使是概率 P(O| λ ) 最大。用气温与年轮的例子来讲就是，已知感兴趣的这十年年轮大小分别为 S-M-S-L-M-L-M-S-M-M ，求最可能出现这种情况的初始概率、状态转移矩阵和观测矩阵。对于这个问题枚举法显然是行不通了。因为不可控的元素太多了，不可能像第一类问题 ( Evaluation Problem ) 或第二类问题 ( Decoding Problem ) 那样得到一个唯一解，不同的初始值和不同的初始矩阵会得到不同的结果，学习类问题通常是这样。同时对于这个问题，通常需要观察链比较长（即需要输入更多信息）。 3.1 算法推导目前有一种专门的算法来处理这个问题，即 Baum-Welch 算法，它是 EM 算法在解决 HMM 学习问题时的一个特例。 PS. Baum-Welch 算法的两位作者分别是 Leonard Baum 和 Lloyd Welsh ，其中 Leonard Baum 是一位传奇人物，他是著名金融公司——文艺复兴科技公司的核心创始人，咱们将要讲到的 Baum-Welch 算法帮助该公司在对冲基金中连续 27 年回报率打败巴菲特。有兴趣的朋友可以搜索这段故事来看看，相信看完对学习 Baum-Welch 算法会充满动力！另外，有关 EM 算法 (Expectation Maximization Algorithm) 欢迎参考我的另一篇博文： EM算法简介大家在看完 EM 算法后，对 EM 算法的套路已经有了一个大致的了解，那么具体到 Baum-Welch 算法，推导如下：在推导之前，我们回顾一下在第一类问题 ( Evaluation Problem ) 中有介绍到前向算法 (Forward Algorithm) ，其中前向概率同理，还有一个后向算法 (Backward Algorithm) ，其中后向概率 (1) E-step 我们先定义两个变量ξ t ( i, j ) 和γ t (i) ： (1) ------------------------------------------------------------------------------------------------------- (2) 这两个变量看起来好像很复杂，但是它们想要表达的概念并不复杂。ξ t ( i, j ) 表示在 t 时刻状态为 i ，在 t+1 时刻状态转为状态 j 的概率。再具体一些来讲，例如ξ 2 (H, L) 表示第二年是高温 (H) ，而第三年为低温 (L) 的概率。而γ t (i) 表示 t 时刻为状态 i 的概率，例如γ 2 (H) 表示第二年是高温 (H) ，而第三年为低温 (L) 或高温 (H) 的概率之和，也即仅考虑第二年为高温 (H) 的概率。如果还是不太明白，可以看看下图于是有 (2) M-step 有了上述的两个式子后，我们可以轻松地写出当前状态转移矩阵中 A 的元素 a ij 和观测矩阵 B 中的元素 b j (k) ：如何理解这个式子？打个比方，如果用 a HL 表示当前参数条件下整个链中由高温转低温的概率，那么式子中的分子表示所有（ t 从第一年至倒数第二年，因为是有转移，这里是写为到倒数第二年）高温 (H) 转到低温 (L) 时刻的概率之和；分母 t 时刻为高温 (H) 的概率 ( 无论 t+1 时刻的状态是什么 ) 。两者相除即由 i 状态转移到 j 状态的概率。式子中，分子是所有满足观测为 k 的这些时刻，状态为 j 的概率之和，例如所有观测到大年轮 (L) 的那些年份状态为高温 (H) 的期望值；分母为所有 t 时刻 ( 第一年至倒数第二年 ) 状态为 j 的概率之和，例如在所有年份中状态为高温 (H) 的期望值。两者相除即观测为 k 时状态为 j 的概率，即由状态 j 转为观测 k 的概率。另外，还需指定初始状态分布。如果有经验值，可按照经验；如果没有可随机取值：这样就获取到当前状态 (t=1) 的转移矩阵 A 1 和当前观测矩阵 B 1 ，以及初始状态π，即当前λ 1 =(A 1 , B 1 , π ) 。 (3) 用λ 1 代替λ 0 ，不断地迭代 M-step 和 E-step ，直到收敛在计算的过程中通常会用 log 函数来简化计算，因此也即：或者直接指定迭代多少次后就退出迭代过程，终止计算 3.2 实例分析提到 HMM 当然要提到晴雨预测例子，假设观测了三天，观测结果为 O={o 1 =soggy, o 2 =dry, o 3 =dryish} 。再次强调，实际应用中，必须要有足够多的信息才能得到较好的结果，也就是说观测链通常会比较长。这里为了简化计算，观测链长度仅为 3 。先初始化一组参数 λ 1 =(A 1 , B 1 , π ) ，其中的值是随机的 ( 当然如果有经验的人可以找到一些初始化里的细微套路，使得算出的局部最优解为全局最优解的可能性更大 ) ，本例中设置的值如下： = 状态转移矩阵 A 1 = 初始状态分布π = 观测矩阵 B 1 将状态转移矩阵 A 1 和观测矩阵 B 1 的所有元素标记在一张图中，如下： (1) 基于以上数据，利用向前向后算法计算出所有的前向概率和后向概率再利用前向算法计算 t=2 和 t=3 时的前向概率，如下：在计算完前向概率后，我们可以算出在当前参数条件下，观测链 O 出现的概率： P(O| λ 1 )= α 3 (1) + α 3 (2)+ α 3 (3)=0.013 同理我们也计算出所有的后向概率。注意：后向概率是从后往前算的 ( 即先计算 t=3 ，再算 t=2 ，最后算 t=1) ， t=3 时：再利用后向算法求出所有的后向概率： (2) 计算中间变量ξ t ( i, j ) 和γ t (i) (3) 计算当前的参数 λ 2 =(A 2 , B 2 , π ) ，并用当前的参数代替 λ 1 ，完成一次迭代 (4) 不断迭代直到收敛这里将 t=1 和 t=2 时计算结果列出来，有兴趣的读者可以试着计算一下我们可以看到表中 P(O| Δ ) 变化较大，表明未收敛。注：这里写的 P(O| Δ ) 就是上文中的 P(O| λ ) ，只是写法不同，内容一致当迭代至第 9 次后结果收敛，计算终止。如下表因此，最终结果如下表：参考材料： Dmitry Shemetov. Bayesian structural inference and the Baum-Welch algorithm. Leonard E. Baum, Ted Petrie, George Soules and Norman Weiss. A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. Loc Nguyen. Tutorial on Hidden Markov Mode

个人分类: Algorithm|3790 次阅读|0 个评论

隐马尔科夫模型简介(三)

luria 2019-7-15 20:33

本篇继续讨论隐马尔科夫模型的第二个基本问题——解码问题在讨论之前，还是欢迎我们的主角——隐马尔科夫模型 (HMM) 出场！ Problem 2. 解码问题 ( Decoding Problem) 已知 HMM 模型λ =(A, B, π ) ，以及观测序列 O ，求最可能的状态序列。之前的博文 http://blog.sciencenet.cn/blog-2970729-1188964.html 中讨论的问题就属于这一类问题。其实这个问题和之前讨论的评估问题 (第一类问题) 相比，已知的条件是一致的，只是所求不同。因此理论上也可以用枚举法，事实上，在第一篇隐马尔科夫模型简介博文中我们也这样做了。同样因为计算量比较大，所以枚举法并不可取。在此介绍一种目前主流的解决方案，叫做维特比算法 (Viterbi Algorithm) ，算法演示如下： Viterbi Algorithm.gif Viterbi 算法的思想是步步为营，每一步都是当前最佳的路。如果用气温和年轮的例子来说： 1. 首先写出第一年的情况因为第一年观测到的是小年轮，于是 δ 1 (H) 表示第一年观测到小年轮的同时气温为高温的概率： δ 1 (H) = 0.6 × 0.1=0.06 注：其中 0.6 表示初始为 H 的概率， 0.1 表示观测到小年轮而且为高温的概率。同时，第一年观测到小年轮而且气温为低温的概率为： δ 1 (C) = 0.4 × 0.7=0.28 δ 1 (C) δ 1 (H) ，因此第一年为低温的可能性更大，所以下一步计算时不考虑第一年为高温的情况 2. 计算第二年的情况第二年观测到的是中年轮 (M) ，于是 δ 2 (H) = δ 1 (C) × 0.4 × 0.4 = 0.0448 注：第一个 0.4 表示由低温转高温的概率，第二个 0.4 为观测为中年轮，且状态为高温的概率同理，δ 2 (C) = δ 1 (C) × 0.6 × 0.2 = 0.0336 δ 2 (H) δ 2 (C) ，因此第二年为高温的可能性更大，所以下一步计算时不考虑第二年为低温的情况。 3. 计算第三年的情况第三年观测为小年轮，计算方法同第二年，直接写出结果如下： δ 3 (H) = δ 2 (H) × 0.7 × 0.1 = 0.003136 δ 3 (C) = δ 2 (H) × 0.3 × 0.7 = 0.009408 δ 3 (C) δ 3 (H) ，因此第三年是低温的可能更高，所以下一步计算时不考虑第三年为高温的情况。 4. 计算第四年的情况第四年观测为大年轮，计算方法同第二年，直接写出结果如下： δ 4 (H) = δ 3 (C) × 0.4 × 0.5 = 0.0018816 δ 4 (C) = δ 3 (C) × 0.6 × 0.1 = 0.00056448 δ 3 (H) δ 3 (C) ，因此第四年是高温的可能更高。综上，这四年最可能的状态是 C-H-C-H ，这一结果和第一篇隐马尔科夫简介博文( http://blog.sciencenet.cn/blog-2970729-1188964.html )中 HMM 算法得到的结果一致。但是通过计算过程来看，更加高效。如果用数学公式表示，如下：参考材料： https://sens.tistory.com/m/320?category=501289 Guy Leonard Kouemou. History and Theoretical Basics of Hidden Markov Models Mark Stamp. A Revealing Introduction to Hidden Markov Models 李航 . 统计学习方法

个人分类: Algorithm|2312 次阅读|0 个评论

隐马尔科夫模型简介(一)

luria 2019-7-10 18:43

1. 一个简单的例子假设我们想知道某个固定的地区一些年来的平均年平均气温。为了让这个问题变得有趣，我们假设我们关注的这些年份是在温度计发明之前的遥远过去。我们不能回到过去，所以需要寻找与温度相关的非直接证据。为了简化问题，仅会考虑两种年平均温度， hot 和 cold 。假设现代的证据证明 hot year 之后又是一个 hot year 的概率是 0.7 ， cold year 之后又是一个 cold year 的概率是 0.6 ，而且这个概率在过去的岁月里都适用，那么目前的信息总结如下：（ 1 ）其中 H 代表 hot ， C 代表 ''cold 。另外，当前的研究证实树的年轮与温度相关。也为了简化起见，我们将树的年轮分为三种大小： small ， medium 和 large ，分别用 S, M 和 L 表示。最后基于存在的证据显示，年平均温度与树的年轮之间的关系如下：（ 2 ）对于这个例子来说，状态 (state) 是年平均气温， H 或 C 。从一种状态到另一种状态的转移过程是马尔科夫过程 (Markov process) 。因为下一个状态仅依赖于当前状态，而且符合如矩阵 (1) 的固定概率。然而，真实的状态是隐藏的 (hidden) ，因为我们不能直接获取到过去那些年份的气温。虽然我们不能观测到过去那些年的状态（气温），但是我们可以观测到树的年轮大小。通过矩阵 (2) ，树的年轮告诉我们关于气温的概率信息。因为状态是隐藏的，这种类型的系统我们称为隐马尔科夫模型 (Hidden Markov Model ， HMM) 。我们的目标是有效地，且高效地利用观测到的数据了解马尔科夫过程的不同特征。我们称矩阵 (1) 为状态转移矩阵 (state transition matrix) ：（ 3 ）称矩阵 (2) 为观测矩阵 (state transition matrix) ：（ 4 ）在这个例子中，还需要知道一个初始状态分布 (initial state distribution) ，记为 π，而且假设（ 5 ）这里的初始状态分布指关注的这几年中，最开始的那一年，高温的概率为 0.6 ，低温的概率是 0.4 ( 注：这个对应关系在文章中虽未明说，但从后面的算式中可查看到) A 、 B 和π中每个元素都是概率值，矩阵中每行都是一个概率分布，每行之和为 1 。现在我们关注的四年 ( 例如 2007-2010 年 ) ，我们观测到这四年树的年轮分别为 S, M, S 和 L ，且用 0 表示 S ， 1 表示 M ， 2 表示 L ，那么观测链如下：（ 6 ）如下图：通过观测到的年轮结果，我们想推测出最可能（ most likely ）的马尔科夫过程状态链 ( 注：也即这四年气温情况分别是怎样的 ) 。这个问题不像看起来那么可以一刀切（ clear-cut ），因为对 most likely 人们有不同的理解。一方面，我们可以将 most likely 大致地定义为，所有长度为 4 的可能状态链中概率最高的那种状态链。 ( 注：也即所有可能的 2^4 种状态，每种状态都有对应的概率，这其中概率最大的那种 ) 。我们可以采用动态规划算法 (Dynamic programming, DP) 来求解出这个特殊解。另一方面，我们可能会将 most likely 合理地定义为，使状态链中每个状态的可能最大化 ( 注：例如状态链中第一个状态最可能是低温，第二、三、四个状态最可能是高温、低温、高温，那么最后整条状态链最可能是低温 - 高温 - 低温 - 高温 ) 。其实，动态规划算法得到的解与隐马尔科夫算法得到的解并一定完全一致。动态规划算法必须要有合理的状态转移，而这个在隐马尔科夫模型算法中不是必须的。 ( 注：老实说读到这里才开始真正佩服 HMM ！另外，有关动态规划算法，欢迎关注我的另一篇博文： http://blog.sciencenet.cn/blog-2970729-1112311.html ) 而且，即使所有的状态转移都是合理的， HMM 方法也不同于 DP 方法，那就是在处理标记问题时（ notation ）。 2. 标记问题所有可能的观测结果通常用｛ 0,1,...,M-1 ｝表示，因为这样可以在不失普遍性的前提下，使标记问题简单化。观测到的序列依次用 O i 表示，其中 O i ∈ V for i = 0, 1,...,T-1 。注：用上面的例子来说， T 为 4 ，表示观测的年份数，从 2007-2012 共 4 年； N 为 2 ，表示观测状态数，气温要么是高温，要么是低温； M 是 3 ，表示树的年轮大小数，年轮要么是大号 (L) ，要么是中号 (M) ，要么是小号 (S) ； Q 是高温和低温，即 {H ， C} ，它是一个集合！是所有可能的马尔科夫状态集合； V 是大号 (L) 、中号 (M) 和小号 (S) ，对应为数字即 {0, 1, 2} ，是一个集合！是所有可能的观测结果集合； A 是状态转移矩阵，是一个矩阵！如果写成概率公式，如下： B 是观测矩阵，是一个矩阵！如果写成概率公式，如下：注意：这两个公式后面会有用到！另外， A 和 B 矩阵是行随机的。它们和状态无关，是客观存在的规律。 π是初始状态分布； O 是观测的序列，例如 (S, M, S, L) ，或者换算为数字 (0, 1, 0, 2) 整个马尔科夫过程用图展示如下：其中 X i 代表隐状态，其它的解释如上。隐藏于虚线上方的状态链，即马尔科夫过程，取决于当前状态和 A 矩阵。我们仅能观测到 Oi ，它通过 B 矩阵与隐状态关联起来。 HMM 可以通过 A, B 和 π确定，因此可以用以下公式表示： λ = (A, B, π ) 那么，一个长度为 4 的状态链可以写为：例如：低温，高温，低温，高温。这个是我们最终想要知道的。与其相对应的观测链如下：例如：年轮 S, 年轮 M, 年轮 S ，年轮 L 。是我们观测到的于是，状态 x 0 的概率为π x0 。在 x0 的条件下观测到 O 0 的概率是 b x 0 ( O 0 ) ，从 x0 转移到 x 1 的概率为 a x0,x1 。依次类推，最终观测为 O ，推测为 X 这种链 ( 例如高温 - 高温 - 低温 - 低温 ) 的概率是：在上面通过年轮推测气温的例子中，观测 O=(0,1,0,2) ，对应 ( 小年轮，中年轮，小年轮，大年轮 ) 。那么高温 - 高温 - 低温 - 低温这种可能的状态链的概率是： P(HHCC) = 0.6(0.1)(0.7)(0.4)(0.3)(0.7)(0.6)(0.1) = 0.000212 同理，我们可以算出每种可能情况 ( 总的是 2^4 种可能，有四年，每年两种可能的温度情况 ) ，如下表：其中， normalized probability 是这 16 种可能的状态链的概率归一化之后的结果。如果是动态规划算法，推测最可能状态链是 CCCH ，因为其 normalized probability 最大；如果是隐马尔科夫模型，则计算如下： 1. 先算出上表中所有第一个状态为 H 的可能性之和，即 HHHH ， HHHC ， HHCH ， HHCC ， HCHH ， HCHC ， HCCH ， HCCC 的 normalized probability 之和，为 0.188182 。第一状态为 C 的可能性之和为 1-0.188182=0.811818 2.再依次算出第二个状态，第三个状态和第四个状态的 H/C 概率，如下表：因为链的各个 element 计算是独立的，这里只需要挑选出每个 element 概率最大的状态，构成概率最高的状态链，本例中 HMM 计算出的最可能状态链是 CHCH 。注意：两种算法计算出的最可能状态链不同，但是两种状态链都是合理的。参考文献： Mark Stamp. A Revealing Introduction to Hidden Markov Models

个人分类: Algorithm|7483 次阅读|0 个评论

[转载]隐马尔科夫链接

itso310 2014-11-27 22:01

1、有计算步骤： http://www.cnblogs.com/tornadomeet 2、举例通俗： http://blog.csdn.net/wangxinginnlp/article/details/7849208

个人分类: 复杂网络|1105 次阅读|0 个评论

水分循环有马尔科夫性质? (14)-水分在各个纬圈中的循环例子(下）

zhangxw 2014-1-27 12:36

水分循环有马尔科夫性质 ?! (14)- 水分在各个纬圈中的循环的例子 ( 下 ) 张学文 ,2014/1/21-27 1. 过去的水分循环分析基本是根据有关数据在海洋、陆地的两个单元的情况下讨论它们的在本区域内部的水分循环或者彼此的水分循环。这被称为水分的小循环和大循环。我们这里的讨论则是把水分循环模型化了。即给出一般的水分循环关系，公式，符号。对于究竟选取几个不重叠的水体分区单元则由研究者自己选定。 2. 我们还给出了不同水体互相转化的统一的表达工具，即转移矩阵。它承认下一个时刻的水分转移量仅与最近的水体相对分布有关，即水分循环具有马尔科夫性质。由此我们可以从任何初始水体分布开始，让水体进行水分循环（迭代）而求得任何时间步长的不同水体的相对数量，而且知道它有一个平衡状态：各个水体占有的百分比不再随时间而变化了。 3. 我们不再具体细化我们的基本模型了 ( 欢迎各位进一步发展它 ) 。现在则讨论另外两个概念，它们既可以联系前面介绍的各个纬圈的水分循环的一般模型，也是认识水分循环的另外一种思路。这两个概念就是降水来源函数和蒸发去向函数。 4. 降水来源函数 C(x,y) ，也称为水分辐合函数，它给出在 x 处的单位面积上的单位降水量中 , 来自 y 处的水分占有的权重（百分比）。 5. 蒸发去向函数 D(x,y) ，也称为水分辐散函数，它给出在 x 处的单位面积上的单位蒸发量中 , 降落到 y 者占 ( 蒸发量 ,1) 的权重（百分比）。 6. 显然以上的变量 x,y 可以是指地球上的任何一个点附近的单位面积。以上两个定量概念会成为我们分析降水来源、蒸发去向的理论工具。需要指出这里给的这两个函数是气候意义下的函数。 7. 对这两个函数的更细致的说明请参考“大气水分循环方程”一文（ 2006 ，高原气象杂志 190-194 ，或者《空中水文学初探》一书第 8 章（ 2010 ，气象出版社）。利用这两个函数可以在各地的蒸发量的配合下计算各地的降水，或者在降水量的配合下计算各地的蒸发量。 8. C(x,y) ， D(x,y) 中的 x ， y 都是代表地球球面上的面积元。这种表达方式对理论处理有其方便之处。显然它也可以粗粒化为离散的、有限的“若干块面积”，例如让各个 x ，或者 y 代表地球上的各个纬圈。这样 C(x,y) ， D(x,y) 也就与前面我们讨论的水分循环的转移矩阵对应了。所以 C(x,y) ， D(x,y) 可以看作是前面讨论的水分循环转移矩阵的理论化的一部分。 9. 在前述文献中就给出过一种设想的离散化的 C(x,y) ， D(x,y) ，即转移矩阵的值。下面就是对应的数值表。表13 离散的大气水分辐合函数 C ( x,y ) 的示例取自《空中水文学初探》一书表 8.3 （表左侧纬度带蒸发的水分在上侧纬度区间降落而变成的降水中占的比例 , 权重）纬度区间水分降落的纬度带 x x 1 x 2 x 3 x 4 x 5 x 6 x 7 90-70 ° N 70-40 ° N 40-10 ° N 10 ° N-10 ° S 10-40 ° S 40-70 ° S 70-90 ° S 该水分蒸发纬度带 y y 1 0.5 0.01 0 0 0 0 0 y 2 0.35 0.5 0.1 0 0 0 0 y 3 0.15 0.4 0.8 0.2 0 0 0 y 4 0 0.09 0.1 0.55 0.12 0 0 y 5 0 0 0 0.25 0.78 0.57 0.04 y 6 0 0 0 0 0.1 0.43 0.49 y 7 0 0 0 0 0 0 0.47 合计 1 1 1 1 1 1 1 表14 离散的大气水分辐散函数 D ( x,y ) 的示例取自《空中水文学初探》一书表 8.4 （表中的值就是单位蒸发在该纬度区间变成降水而降落所占的比例）纬度区间水分蒸发的原始纬度带 x x 1 x 2 x 3 x 4 x 5 x 6 x 7 90-70 ° N 70-40 ° N 40-10 ° N 10 ° N-10 ° S 10-40 ° S 40-70 ° S 70-90 ° S 该水分降落的纬度带 y y 1 0.8 0.03 0 0 0 0 0 y 2 0.15 0.8 0.18 0 0 0 0 y 3 0.05 0.17 0.62 0.15 0 0 0 y 4 0 0 0.2 0.67 0.25 0 0 y 5 0 0 0 0.18 0.55 0.09 0.04 y 6 0 0 0 0 0.2 0.9 0.11 y 7 0 0 0 0 0 0.01 0.85 合计 1.00 1.00 1.00 1.00 1.00 1.00 1.00 10. 在空中水文学初探一书中给了利用这个转移矩阵和对应的纬圈降水量、蒸发量去计算蒸发量、降水量。获得的结果是比较满意的。这样我们关于各个纬圈的水分循环就有了初步的水分循环数值解了。 11. 对此的更多的说明欢迎参考《空中水文学初探》和高原气象上的文章。这里不再细说了。总之那里的工作与这里的马尔科夫转移矩阵是互相呼应的。

个人分类: 空中水科学|2619 次阅读|0 个评论

今天是李亚普诺夫自杀的日子

热度 6 xiegming 2012-10-31 21:25

94年前的今天，经过一年多的折磨，李亚普诺夫的妻子最终没有逃脱肺结核的魔抓而去世，而这位伟大的力学家数学家拔枪饮弹自尽，抢救无效于三天后离世。今天我的课程刚好讲到系统稳定性，真是冥冥之中似有天意。李亚普诺夫出生于1857年，1885年在圣彼得堡大学获得硕士学位，1892年在莫斯科大学获得博士学位，博士论文就是那篇著名的《运动稳定性的一般性问题》，今年刚好是发表120周年。以下摘自百度百科的介绍：李亚普诺夫是常微分方程运动稳定性理论的创始人，他1884年完成了《论一个旋转液体平衡之椭球面形状的稳定性》一文，1888年，他发表了《关于具有有限个自由度的力学系统的稳定性》.特别是他1892年的博士论文《运动稳定性的一般问题》是经典名著，在其中开创性地提出求解非线性常微分方程的李雅普诺夫函数法，亦称直接法，它把解的稳定性与否同具有特殊性质的函数（现称为李亚普诺夫函数）的存在性联系起来，这个函数沿着轨线关于时间的导数具有某些确定的性质.正是由于这个方法的明显的几何直观和简明的分析技巧，所以易于为实际和理论工作者所掌握，从而在科学技术的许多领域中得到广泛地应用和发展，并奠定了常微分方程稳定性理论的基础，也是常微分方程定性理论的重要手段. 李亚普诺夫28岁硕士毕业，35岁才博士毕业，这要在当今中国，估计承受压力之大难以想象。不过人家毕业即教授。其他几个八卦： ·李亚普诺夫还证明了概率论中的“中心极限定理” ·他的挚友也是大名鼎鼎——马尔科夫！ ·他的老师是切比雪夫，圣彼得堡学派的创始人不知道现在有多少人应该感谢李亚普诺夫和马尔科夫，是他们养活了这么多科技工作者。补张照片吧： Aleksandr Mikhailovich Lyapunov (Russian: Алекса́ндр Миха́йлович Ляпуно́в, pronounced )

个人分类: 记忆·感触·工作|10694 次阅读|6 个评论

再谈‘白-杰时间链’

TUGJAYZHAB 2012-7-31 09:00

在给内蒙数学分会的‘申请数学模型鉴定’ http://blog.sciencenet.cn/blog-333331-590944.html 中，我把超球面模型总结成三个公式： Y （ i,k+1 ） = /2 T （ i,k ） = Y' （ i,k ） / Y' （ i,k-1 ） Y' （ i,k ） = Y （ i,k ） /(√Σ( Y （ i,k ） ^2))= Y （ i,k ） /| Y （ k ） | 这三个公式在‘超球面模型讲座’中分别被列为 8-3 ， 8-4 ，和 8-5 。参见‘重发：议“拉普拉斯向量方程”’ http://blog.sciencenet.cn/blog-333331-549891.html 把公式 8-3 展开，我们可以逆时间导出‘白 - 杰时间链’： Y （ i,k+1 ） = /2 （脱括号，移项）我们很容易得到公式 8-7 ： Y （ i,k+1 ） =0.5 D （ i,k+1 ） +0.5 T （ i,k ） * Y （ i,k ）由公式 8-3 ： Y （ i,k ） =0.5 D （ i,k ） +0.5 T （ i,k-1 ） * Y （ i,k-1 ）代入 8-7 ，得： Y （ i,k+1 ） =0.5 D （ i,k+1 ） +0.5 T （ i,k ） * （ 0.5 D （ i,k ） +0.5 T （ i,k-1 ） * Y （ i,k-1 ））因公式 8-3 ： Y （ i,k-1 ） =0.5 D （ i,k-1 ） +0.5 T （ i,k-2 ） * Y （ i,k-2 ）代入上式，得： Y （ i,k+1 ） =0.5 D （ i,k+1 ） +0.5 T （ i,k ） * （ 0.5 D （ i,k ） +0.5 T （ i,k-1 ） *0.5 D （ i,k-1 ） +0.5 T （ i,k-2 ） * Y （ i,k-2 ））为了看得更清楚，我们省略第一下标和下标用的括号，得到： Y k+1 =0.5 D k+1 +0.5 T k * （ 0.5 D k +0.5 T k-1 * （ 0.5 D k-1 +0.5 T k-2 * Y k-2 ）） …. 如此循环迭代 k 步，直到初始： Y k+1 =0.5 D k+1 +0.5 T k * （ 0.5 D k +0.5 T k-1 * （ 0.5 D k-1 +0.5 T k-2 *(0.5 D k-2 …+0.5 T k-k D k-k ）））令 T 的初始值 T k=0 =1 ，则有： Y k+1 =0.5 D k+1 +0.5 T k * （ 0.5 D k +0.5 T k-1 * （ 0.5 D k-1 +0.5 T k-2 *(0.5 D k-2 +… +0.5*0.5 D 0 ）））和我们在第八讲里从系统状态 k 推出 k+6 一样，我们逆时间推导出同样结论：对于多元演替系统，一个给定的状态和之前的每一个状态都有关，但相关程度递减。越近的影响越大，越远的影响越小，也即所谓的‘记忆消退（ Fading Memory ）’。我把由‘超球面模型’导出来的时间链，称为‘白图格吉扎布 - 杰木森时间链’，简称‘白 - 杰链’，以便和其它时间链相比较。与马尔科夫时间链比较：白 - 杰链至少有两个特点： 1）马尔科夫时间链的‘概率转移矩阵’不在已知数据中，凭的是历史积累，靠的是经验。而，超球面模型的‘状态转移’在已知数据中，见公式 8-4 ： T （ i,k ） = Y' （ i,k ） / Y' （ i,k-1 ）。 2）马尔科夫时间链‘无后效性’。而，白 - 杰时间链中每一给定状态与全部历史数据有关，以不同权重使用全部历史数据。希望‘白杰时间链’能很快找到用武之地。我在别处介绍过，道纳德 . 杰木森（ Donald A Jameson ）。他是我在科罗拉多州立大学（ CSU ）读博士的指导老师之一，他在 CSU 教授 NR675 ，环境监测与适应管理（ Environmental Monitoring and Adaptive Management ）。链接：“兰州大学的赵松岭和科罗拉多的杰木森” http://blog.sciencenet.cn/blog-333331-478405.html 相关阅读：超球面模型第八讲：白-杰时间链 http://blog.sciencenet.cn/home.php?mod=spaceuid=333331do=blogid=494130

个人分类: 第八讲|2361 次阅读|1 个评论

白-杰时间链（4）：推导与命名

TUGJAYZHAB 2011-10-7 14:12

超球面模型第八讲（ 4 ）白-杰时间链在前面的博文里，我们用系统的连续三个状态为例，简单介绍了‘杰-白滤波’的基本过程。现在我们把它进一步展开，延长到 6 步，把它展开成一个时间链，说明在系统动态监测中如何使用历史数据，同时提高精度，降低预算。先把前面的表8-1挪过来，为方便，把趋势值的计算放在最下面，则有：样本实测值 D D k-1 D k D k+1 D k+2 … 系统预测值 P D k-1 D k D k ^2/ D k-1 … 系统期望值 E D k-1 D k (D k ^2/D k-1 +D k+1 )/2 … 变化趋势 T D k-1 /D k-1 D k /D k-1 (D k ^2/D k-1 +D k+1 )/2/D k … 再把相关的定义重复一遍。 D k 是系统在时刻k的实测值。 P k 是根据系统在时刻k-1的状态对时刻k状态的预测： P k = T k-1 * E k-1 。 E k 是系统期望，预测和实测的平均： E k = ( D k *+ P k )/2 T k 是系统演替趋势，是时刻k和时刻k-1系统期望的比： T k = E k / E k-1 我们把表延长到第3 个时间段，并根据定义使用相应的符号，得到表8-1-2 ：样本实测值 D D k+2 D k+3 D k+4 … 系统预测值 P T k+1 *E k+1 T k+2 *E k+2 … 系统期望值 E (T k+1 *E k+1 +D k+2 )/2 (T k+2 *E k+2 +D k+3 )/2 … 变化趋势 T E k+2 /E k+1 E k+3 /E k+2 … 我们把表再延长到第5个时间段，得到表8-1-3 ：样本实测值 D D k+4 D k+5 D k+6 … 系统预测值 P T k+3 *E k+3 T k+4 *E k+4 … 系统期望值 E (T k+3 *E k+3 +D k+4 )/2 (T k+4 *E k+4 +D k+5 )/2 … 变化趋势 T E k+4 /E k+3 E k+5 /E k+4 … 延长到第6个时间段，得到表8-1-4：样本实测值 D D k+6 系统预测值 P T k+5 *E k+5 系统期望值 E (T k+5 *E k+5 +D k+6 )/2 变化趋势 T E k+6 /E k+5 至表8-1-4 ，我们得到： P k+6 = T k+5 *E k+5 。而据表8-1-3 第二列， E k+5 =0.5 (T k+4 *E k+4 +D k+5 ) 代入得： P k+6 = 0.5 *T k+5 *(T k+4 *E k+4 +D k+5 ) =0.5 *T k+5 *(D k+5 +T k+4 *E k+4 ) 再据表8-1-3 的第一列， E k+4 =0.5(T k+3 *E k+3 +D k+4 ) 代入得到： P k+6 = 0.5 *T k+5 *(D k+5 +T k+4 *0.5(T k+3 *E k+3 +D k+4 )) 据表8-1-2 第二列， E k+3 =0.5*(T k+2 *E k+2 +D k+3 ) 代入得， P k+6 = 0.5 *T k+5 *(D k+5 +T k+4 *0.5(T k+3 *0.5*(T k+2 *E k+2 +D k+3 )+D k+4 )) 继续下去， E k+2 = 0.5* (T k+1 *E k+1 +D k+2 ) 代入得， P k+6 =0.5 *T k+5 *(T k+4 *0.5(T k+3 *0.5*(T k+2 * 0.5* (T k+1 *E k+1 +D k+2 )+D k+3 )+D k+4 )+ D k+5 ) 最后一步，因为， E k+1 = 0.5 (D k ^2/D k-1 +D k+1 ) 所以，我们最后得到： P k+6 = 0.5 *T k+5 *(T k+4 *0.5(T k+3 *0.5*(T k+2 * 0.5* (T k+1 * 0.5 (D k ^2/D k-1 +D k+1 )+D k+2 )+D k+3 )+D k+4 )+D k+5 ) 我们进一步假定 D k =D k-1 ，所以 D k ^2/D k-1 = D k 预测6可以表示为： P k+6 = 0.5 T k+5 (0.5T k+4 (0.5T k+3 (0.5T k+2 (0.5T k+1 (D k +D k+1 )+D k+2 )+D k+3 )+D k+4 )+D k+5 ) 消掉常量 k，把上面式子稍加整理，得到： P 6 =0.5*T 5 (D 5 +0.5*T 4 (D 4 +0.5*T 3 (D 3 +0.5*T 2 (D 2 +D 1 )))) (8-7) 式子(8-7)说明：使用‘杰-白滤波’的‘预测’不仅和系统监测全过程的所有‘实测’数据有关，而且和历史上所计算出来的所有‘趋势’都有关系。同时，我们也知道，‘趋势’是从‘实测数据’派生、计算出来的。也就是说，预测所用的所有数据都是已经知道的，没有未知数。从另一个角度说，所有的‘实测数据’在‘预测’里都有用，但作用呈递减。文献里有个专门术语‘记忆消退（ Fading Memory ） ’描述这种现象。与马尔科夫时间链‘无后效性’不同，这里，‘杰-白滤波’用历史上所有的数据形成的时间链来预测邻域。这个时间链，如果过去没有命名过，我们将称它为‘白图格吉扎布-杰木森道纳德（Donald A. Jameson）时间链 ’，简称 ‘白-杰时间链 (Bai-Jameson Chain) ’。‘滤波’称为‘杰-白滤波’，而时间链称‘白-杰时间链’。在‘白-杰时间链 ’里，尽量使用了所有历史数据。单从‘历史数据没有浪费’这个角度看，‘白-杰时间链 ’比较科学。由于使用了历史数据，取样规模可以比较小，监测所需要预算也就比较少（参见：两不同来源数据的不同权重）。而且，这样做‘有增益’，效率比较高（略，暂不讨论）。未完待续：超球面模型第八讲（ 5 ）两不同来源数据的不同权重超球面模型第八讲的链接：白-杰时间链（ 1 ） ‘ 上帝不掷骰子 ’ 白-杰时间链（ 2 ）：议拉普拉斯向量方程白-杰时间链（ 3 ）确定性在邻域（上）白-杰时间链（ 3 ）确定性在邻域（下）白杰时间链（ 4 ）白-杰时间链的推导与命名超球面模型第八讲（ 5 ）两不同来源数据的不同权重 2014-2-22 补充： P 6 =0.5*T 5 (D 5 +0.5*T 4 (D 4 +0.5*T 3 (D 3 +0.5*T 2 (D 2 +D 1 )))) (8-7) 把公式（8-7）的特指的时间下标6换成通用的k则有通式（8-8）： P k =0.5*T k-1 (D k-1 +0.5*T k-2 (D k-2 +0.5*T k-3 (D k-3 +...+0.5*T 2 (D 2 +D 1 )))) ‘杰-白时间链’的意义就更清楚了。

个人分类: 第八讲|2434 次阅读|1 个评论

初学马氏链

热度 4 yanghualei 2011-3-29 08:07

初学马氏链：对于将来的事物的态势，一般取决于当前事物的态势的累积量，故如果对于将来进行计算，只需知道当前就行，把这种对过去历史没有记忆性，而只对当前状态有关的随机过程叫做马尔科夫链，而其又分为离散的和连续的，一个离散马过程有n个随机变量构成，可用空间联系，也可用时间联系，若这些随机变量服从同一分布，即在同一状态空间上定义，则任一次观察就是一样本路径，就是n个这样的状态空间中各选取一点生成的新n维状态空间，此时路径就是这个状态空间中的一个点，如果要求此点的概率，则通过马链的无记忆性，则可以把其整理为：只与初始态和转移概率有关，如果每一个状态的选取不与空间和时间有关，即其又是齐次的马链，而最终在n维空间中，此样本的概率就是 P=Πp(0)p(12)p(23)...p((n-1)n) 喜欢的映射：证明区间（0,1）和闭区间等势，先分别上述两个区间中分别选取其两个真子集，不妨设为A={1/2,1/3,1/4...}和B={0,1,1/2,1/3...},然后构造一个映射f：A→B，此映射可记为f（1/2）=0,f（1/n）=1/(n-2);且当x∈（0,1）/A,则f（x）=x,特喜欢这种构造，还有一个映射是自己比较喜欢的，就是行列式的映射，就是把一个矩阵转换为一个数，如任A∈Mn（R）,则g:A→g(A)=det(A);还有一个证明可逆充要条件时候构造的映射，当b∈h(A),且h(a)=b时,g(b)=a；当b∈B/h(A)时，g(b)=c, 一般对于一映射其既有左逆又有右逆，并且左右相等相等，则此映射才存在逆映射，这要求我们学会左右侧思想，因为有时候左右侧是不等的或者不对称的，甚至连存在都还是待证。看几天的紧性：一维直线上的有界闭集，而有界闭集上的连续函数，有很多优良性质：如可积和可以达到上下确界，如果在加点条件还可以满足许多构造性性质，数学和其他科学很多都是根据一定法则推广来的，如从一维到多维，从离散到连续或者反之等，所以研究多维空间上类似有界闭集的集合也很重要，而紧集就类似于一维中的闭区间，而对紧的引入先从定义一背景空间X开始，然后考察其上的A，若A中的任何点列都收敛于X中的某一点，就称A是列紧集，列就是点列，若A中的任何点列都收敛于A中的某一点，则A就是自列紧集，因为连其极限还是自己的，故就是自己的点列，如果A与X等同，则A就是列紧空间；同时自爱距离空间中，即使满足完备等优良性质，则有界点列同样有可能不存在收敛点列。特有意思的超平面：在一个n维的欧式空间中把Σa(i)x(i)=c称为其中的超平面，这是因为n维的欧式空间中存在很多线性流型，而可以认为其一个n-1的欧式空间，而n-1维中的超平面又可以看着n-2的欧式空间，如此继续下去，则三维中的超平面就是平面，二维中的是线，一维中的是点，有意思不，如果提高一个维度，相差太大了，更别说辈分和平起平坐了，其简直就可以忽略不计，就像在无穷集合上忽略有限一样。

个人分类: 数学沙滩|4046 次阅读|20 个评论

帐号		自动登录	找回密码
密码			注册

关闭安全验证

标签: 马尔科夫

相关帖子

相关日志

关闭 安全验证

标签: 马尔科夫

相关帖子

相关日志

关闭安全验证