标签: markov

马尔可夫链模型和隐马尔可夫模型有什么区别？我在维基百科上读过,但无法理解这些差异.

我最近一直在阅读很多关于Markov Decision Processes(使用价值迭代)的内容,但我根本无法理解它们.我在互联网/书籍上找到了很多资源,但他们都使用的数学公式对我的能力来说过于复杂.

由于这是我上大学的第一年,我发现网上提供的解释和公式使用的概念/术语对我来说太复杂了,他们认为读者知道我从未听说过的某些事情. .

我想在2D网格上使用它(填充墙壁(无法实现),硬币(可取)和移动的敌人(必须不惜一切代价避免)).整个目标是收集所有硬币而不触及敌人,我想使用马尔可夫决策过程(MDP)为主要玩家创建AI .以下是它的部分外观(请注意,与游戏相关的方面在这里并不是很重要.我只是想了解一般的MDP):

根据我的理解,MDP的粗略简化是它们可以创建一个网格,它保持我们需要去的方向(指向我们需要去的地方的"箭头"网格的类型,从网格上的某个位置开始)达到某些目标并避免某些障碍.具体到我的情况,这意味着它允许玩家知道去哪个方向收集硬币并避开敌人.

现在,使用MDP术语,这意味着它创建了一个状态集合(网格),它保存某个特定状态的某些策略(要采取的操作 - >上,下,右,左)(网格上的一个位置) ).这些政策由每个州的"效用"值决定,这些价值本身是通过评估在短期和长期内获得多少益处来计算的.

它是否正确？还是我完全走错了路？

我至少想知道以下等式中的变量在我的情况中代表什么:

(取自Russell&Norvig的"人工智能 - 现代方法"一书)

我知道这s将是网格中所有方块的列表,a将是一个特定的动作(上/下/右/左),但其余的呢？

如何实施奖励和效用函数？

如果有人知道一个简单的链接,显示伪代码以非常慢的方式实现与我的情况相似的基本版本,那将是非常好的,因为我甚至不知道从哪里开始.

谢谢你宝贵的时间.

(注意:随意添加/删除标签或在评论中告诉我是否应该提供有关某些内容或类似内容的更多详细信息.)

我不太明白这个马尔科夫...它需要两个单词前缀和后缀保存它们的列表并随机生成单词？

    /* Copyright (C) 1999 Lucent Technologies */
/* Excerpted from 'The Practice of Programming' */
/* by Brian W. Kernighan and Rob Pike */

#include <time.h>
#include <iostream>
#include <string>
#include <deque>
#include <map>
#include <vector>

using namespace std;

const int  NPREF = 2;
const char NONWORD[] = "\n";    // cannot appear as real line: we remove newlines
const int  MAXGEN = 10000; // maximum words generated

typedef deque<string> Prefix;

map<Prefix, vector<string> > statetab; // prefix -> suffixes

void …

我的问题在概念上类似于解决字谜,除了我不能只使用字典查找.我试图找到合理的词而不是真实的词.

我已经基于一堆文本中的字母创建了一个N-gram模型(现在,N = 2).现在,给定一个随机的字母序列,我想根据转移概率将它们置于最可能的序列中.我认为在开始时我需要维特比算法,但随着我看起来更深入,维特比算法根据观察到的输出优化了一系列隐藏的随机变量.我正在尝试优化输出序列.

有没有一个众所周知的算法,我可以阅读？或者我是否与Viterbi走在正确的轨道上,我只是没有看到如何应用它？

更新

我已经添加了一笔赏金来要求更深入地了解这个问题.(分析解释为什么不能采用有效的方法,除模拟退火之外的其他启发式/近似等)

我想在R中做一个简单的一阶马尔可夫链.我知道有像MCMC这样的包,但找不到一个以图形方式显示它.这甚至可能吗？如果给定一个转换矩阵和一个初始状态,可以直观地看到通过马尔可夫链的路径(也许我可以手工完成这个......).

谢谢.

马尔可夫链是一种(几乎标准的)产生随机乱码的方式,对于未经训练的眼睛看起来很聪明.您将如何从人类书面文本中识别马尔可夫生成的文本.

如果您指向的资源是Python友好的,那将是非常棒的.

我已经在Python中为简单的Markov决策过程Wikipedia实现了值迭代算法.为了保持特定马尔可夫过程的结构(状态,动作,转换,奖励)并迭代它,我使用了以下数据结构:

1. 可用于这些状态的状态和操作的字典:

   SA = { 'state A': {' action 1', 'action 2', ..}, ...}

2. 转换概率字典:

   T = {('state A', 'action 1'): {'state B': probability}, ...}

3. 奖励词典:

   R = {('state A', 'action 1'): {'state B': reward}, ...}.

我的问题是:这是正确的方法吗？MDP最适合的数据结构(在Python中)是什么？

我对鸟的运动进行了500次观察.我想预测这只鸟的第501次运动是什么.我在网上搜索,我想这可以通过使用HMM完成,但我没有任何关于该主题的经验.任何人都可以解释用于解决此问题的算法的步骤吗？

我一直在研究Markov聚类算法细节的以下示例:

http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf

我觉得我已经准确地表示了算法,但我得到的结果与本指南至少得到的结果相同.

当前代码位于:http: //jsfiddle.net/methodin/CtGJ9/

我不确定是否我错过了一个小事实,或者只是需要在某个地方进行小调整,但我尝试了一些变化,包括:

1. 交换通货膨胀/扩张
2. 根据精度检查相等性
3. 删除规范化(因为原始指南不需要它,尽管官方MCL文档规定在每次传递时规范化矩阵)

所有这些都返回了相同的结果 - 节点只影响自身.

我甚至在VB中找到了类似的算法实现:http: //mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb

我的代码似乎与它们的编号(例如600 - 距离)相匹配.

这是扩展功能

// Take the (power)th power of the matrix effectively multiplying it with
// itself pow times
this.matrixExpand = function(matrix, pow) {
    var resultMatrix = [];
    for(var row=0;row<matrix.length;row++) {
        resultMatrix[row] = [];
        for(var col=0;col<matrix.length;col++) {
            var result = 0;
            for(var c=0;c<matrix.length;c++)
                result += matrix[row][c] * matrix[c][col];
            resultMatrix[row][col] = result;
        }
    }
    return resultMatrix;
}; 

这就是通胀功能

// Applies a power …

我试图在Python中设计迭代马尔可夫决策过程(MDP)代理,具有以下特征:

• 可观察的状态
  • 我通过保留一些状态空间来回答DP所做的查询类型移动来处理潜在的"未知"状态(t + 1处的状态将识别先前的查询[或者如果之前的移动不是查询则为零]以及嵌入式结果向量)此空间用0填充到固定长度,以保持状态帧对齐,无论查询是否应答(其数据长度可能不同)
• 所有州可能并不总是可以采取的行动
• 奖励功能可能随时间而变化
• 政策融合应该是增量的,只能按行动计算

因此,基本思想是MDP应该使用其当前概率模型在T处进行其最佳猜测优化移动(并且由于其概率,它所做的移动预期随机性暗示可能的随机性),将T + 1处的新输入状态与奖励耦合从之前的T移动并重新评估模型.收敛不能是永久性的,因为奖励可能会调整或可用的行动可能会改变.

我想知道的是,是否有任何当前的python库(最好是跨平台,因为我必须改变Windoze和Linux之间的环境)可以做这种事情(或者可以通过合适的自定义来支持它,例如:派生类支持,允许重新定义说自己的奖励方法).

我发现有关在线移动MDP学习的信息相当稀少.我能找到的MDP的大多数使用似乎都集中在将整个策略作为预处理步骤来解决.