PAGE
PAGE2
马尔科夫模型分析综述
马尔科夫模型被提出主要针对于对序列信息进行建模。由于马尔科夫的序列建模能力，因此在早期的兴趣点中基于马尔科夫的兴趣点建模方法被广泛的引用进行下一个兴趣点推荐。马尔可夫模型是一种统计模型，已经被广泛的应用于语音识别、序列推荐领域等等。
在马尔科夫模型中，为了预测，将序列信息编码成状态形式。K阶马尔科模型根据用户的最后的k个行为动作定义一个状态。针对不同的应用可以定义不同的“动作”，它可以是用户访问某特定网页的行为，或者用户购买某些特定物品的行为，或者用户访问过的兴趣点的行为。我们假设符号集为={,,...}。状态的表示Q=由k个动作行为定义。
通常来说，一个序列定义了马尔科夫链之间的转换。在一个k阶的模型里，当前状态是由马尔科夫链的最后k个动作行为决定。必须考虑一个序列的兴趣点的签到行为，到目前状态为止已经发生了t个动作行为，其中属于，那么，t时刻的k阶马尔科夫模型的当前状态就是取最后的k个行为。在这个序列中，最后的动作是，是由从状态,转化到。因此，马尔科夫链中的状态通过边相连，相当于转化，其中每条边都被标注上一个中提取的动作行为和转移概率。在这个案例中，状态,转化到与动作行为相关。由于每一种状态都有||种可能。因此k阶马尔科夫模型中边的总数等于||。一个状态的转移概率之和总是1。可以从训练的序列数据中学习到转移概率，比如兴趣点签到行为数据。下面本文拿4个签到兴趣点举例{A，B，C，D}，我们绘制一阶马尔科夫链。
图2.SEQ图2.\*ARABIC4一阶马尔科夫链
说明：该马尔科夫模型包括4个状态和4x4=16条边。
Fig2.SEQFig2.\*ARABIC4FirstorderMarkovchain
Note:theMarkovmodelconsistsoffourstatesand4x4=16edges.
假如用户的签到动作行为序列为ABCAABC，那么一阶马尔科夫链的状态路径如下表示：
A-B-C-A-A-B-C
如果是一个2阶的马尔科夫模型，那么就会有4x4=16个状态和=64条边。这样就难像上图中用简单的图形来展示了。2阶马尔科夫链签到动作序列AABCBCA对应的状态转化序列可以用下面序列表示：
AA-AB-BC-CB-BC-CA
马尔科夫建模通常分为两个阶段训练阶段和预测阶段
1）训练阶段。
另S为长度为k的||个可能的的动作序列的集合。对于出现的每个可能的动作序列s属于S。使用序列的序列数据学习||中的概率，对于每个候选动作的概率。学习的概率总共有个，即构建k阶马尔科夫模型的边数。学习到的每个概率对应于马尔科夫模型中每条边的转移概率。
2）预测阶段
例如对于用户签到动作行为的当前序列，使用用户最后k个签到动作行为确定马尔科夫链中的相关状态，返回中转移概率值最大的前TOP-K个动作行为作为推荐结果。
基于马尔科夫的模型依赖于用户动作行为序列的短记忆假设。它的的想法是，用户的动作行为之取决于当前的k个动作的集合。虽然这种加上在现实生活可能不是特别的准确，但是，在现实的应用场景下，基于马尔科夫的序列模型通常具有不错的表现能力。
从上面所述可以发现，基于马尔科夫模型的计算量很大。大量的状态也使得训练模型需要付出更多的代价，评估一个k阶的马尔科夫模型有个可能概率，对于较大的k值，这种模型在应用中显然是不切合实际的。