问题标签 [markov-chains]

我编写了一个 C++ 程序来模拟我正在研究的某个过程。它在模拟的每个时间步输出离散的“状态”。例如：

将是以 a 作为初始条件（由我设置或随机生成）的模拟运行的输出，而 b & c 将是系统不断在其间振荡的状态。

我想将其中的许多运行组合成一个马尔可夫链，以便它变成一个具有以下顶点和边的图。（最好在运行时，因为首先保存输出会占用大量磁盘空间。）括号之间的数字表示遇到某个顶点或边的次数，因此也应该存储它。

真实状态包含 112 位信息，我正在生成数十亿个这样的转换。问题是我还没有找到一个图形库或程序来高效快速地生成马尔可夫链。我一直在玩弄：

• 谷歌稀疏散列在 C++ 中构建我自己的图形类。
• Neo4J（我刚刚开始使用这个）
• 柠檬图书馆

我刚刚完成了“Google 稀疏散列图”，但结果在运行中途变得非常缓慢。大约一天后（内存使用量超过 20 GB，本身不是问题，因为还有更多），它变慢了，大约需要三周才能完成。

我可以使用 12 或 16 核和 256 或 512 GB 内存的计算机，我的感觉是它们应该能够胜任这项工作。

由于我不是受过训练的程序员，而且我的编码速度很慢，所以在我花费大量时间研究另一个不完美的解决方案之前，我正在寻找一些信息。

• 可以快速接受大量顶点和边来构建马尔可夫链的最佳程序/库是什么？
• 缓慢是由于使用了错误的工具或不完善的编码（我怀疑）还是我只是试图做一些总是需要很多时间的事情？

我希望我能把我的问题说清楚。提前感谢任何智慧或答案。

编辑：

根据评论中的问题和答案，我想我的问题应该是：什么是适合 C++ 的快速矩阵库？

为什么值迭代算法的终止条件（例如http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/probability/mdp/search/ValueIteration.java )

在 MDP（马尔可夫决策过程）中是

||Ui+1-Ui||< 误差*(1-gamma)/gamma, 其中

Ui 是效用向量
Ui+1 更新的效用向量

error - 算法中使用的错误界限

算法中使用的 gamma 折扣因子

“error*(1-gamma)/gamma”从何而来？“除以伽玛”是因为每一步都被伽玛打折吗？但是错误*（1-伽玛）？错误必须有多大？

我想从给定的一组数据序列（即点击流数据）中估计一阶马尔可夫链的转移概率矩阵。可能在java中，否则Matlab就可以了。

我将每个序列放在不同的文件中（但当然我可以将所有内容合并到一个文件中），其中一个问题是我没有序列的标准长度。我知道状态空间，我只对状态转换感兴趣。

我读过这篇文章：Estimate Markov Chain Transition Matrix in MATLAB With different State Sequence Lengths，但我不确定它是否适合我的问题。我还想知道是否有处理这个问题的 Java 库。如果是这样，我找不到他们。

我有以下马尔可夫链：

该链显示了位于小行星带中的宇宙飞船的状态：S1 - 可用，S2 - 已损坏。0.12 - 与小行星碰撞摧毁宇宙飞船的概率。0.88 - 碰撞的概率并不重要。需要计算第三次碰撞后船舶处于可用状态的概率。

分析解决方案显示响应 - 0.681。但是这个问题需要通过任何建模工具（MATLAB Simulink、AnyLogic、Scilab等）的仿真方法来解决。

您知道在 Simulink 或任何其他仿真环境中应该使用哪些组件来仿真这个过程吗？任何示例或链接。

I am attempting to do some evaluation of the relative rates of different algorithms in the C# and F# realms using WekaSharp and one of the algorithms I was interested in was Markov Chains. I know Weka has an HMM application but I have not been able to implement this into WekaSharp and was wondering if there was a way to modify the J48 Algorithm to suit this purpose. I know there is some similarity between J48 and first order Markov chains but am trying to determine what needs to be modified and if this is a reasonable thing to do. Here is the J48 as implemented in Yin Zhu's WekaSharp:

Thank you very much.

这是PyMC 的后续：马尔可夫系统中的参数估计

我有一个系统，它由每个时间步的位置和速度定义。系统的行为定义为：

所以，这是我的 PyMC 模型。估计vel，pos也是最重要的damping。

这就是我运行采样的方式：

的值damping由先验支配。即使我将之前的内容更改为 Uniform 或其他内容，情况仍然如此。

我究竟做错了什么？它与前面的示例非常相似，只是多了一层。

此问题的完整 IPython 笔记本可在此处获得：http: //nbviewer.ipython.org/github/sotte/random_stuff/blob/master/PyMC%20-%20HMM%20Dynamic%20System.ipynb

[编辑：一些说明和采样代码。]

[EDIT2：@Chris 的回答没有帮助。我无法使用AdaptiveMetropolis，因为 *_states 似乎不是模型的一部分。]

马尔可夫链如何工作？我已经阅读了马尔可夫链的维基百科，但我没有得到的是无记忆。无记忆指出：

下一个状态仅取决于当前状态，而不取决于之前的事件顺序。

如果马尔可夫链具有这种性质，那么在马尔可夫模型中链有什么用呢？
解释这个属性。

谁能建议我一个好的 C++ 库，用于基于 GMM 的 MRF 学习和使用信念传播进行推理？

如果这不是提出这个问题的正确堆栈交换站点，请建议我正确的一个..

我正在构建一个阵容模拟器，它使用吸收马尔可夫链来模拟某个阵容将得分的运行次数。阵容中的 9 名球员中的每名球员都有一个不同的转换矩阵，并且使用以下函数模拟一场比赛：

Mat 1-9 是单独的 25x25 转换矩阵。是的，我知道我应该使用列表！然后，我使用下一个函数来模拟 1000 个赛季的游戏，并使用此函数尝试让它趋向于“真实”数字。

R 是一个矩阵，它基本上告诉函数从一个状态到另一个状态的运行次数。

所以我的问题是，有没有办法欺骗这个系统以获得每个阵容模拟的“真实”数字而不运行它 1000 次？这样做的目的是查看哪个阵容产生了最“真实”的跑动。

因为有9个！设置阵容的方法，每个运行 362880 个不同的阵容 1000 次是不可行的。

谢谢！

我有一系列事件：

使用这个序列，我得到一个使用以下函数的马尔可夫链：

考虑下一个状态是"LHR - BA"; 那么我如何以以下格式识别跨州的概率分布：