简谈马尔可夫模型在个性化推荐中的应用

随着互联网的飞速发展,个性化推荐已经成为各大网站、手机客户端的必备服务。如何持续优化、进一步提高推荐的精准度是一项复杂又令人兴奋的工程。主流的推荐系统协同过滤、基于内容的推荐、基于社交网络的推荐等等。很多推荐算法没有考虑到用户的短期兴趣,而用户的兴趣又是随着时间动态变化的,所以有效地捕获用户的兴趣偏好转换对提高推荐的准确性有着很大的辅助作用。

马尔可夫模型通过观察用户短期的行为数据,生成一个状态转移矩阵,根据该矩阵预测接下来一个时间点的用户行为,有效地利用了用户的短期兴趣偏好信息。

了解一下概念

安德雷·安德耶维齐·马尔可夫Андрей Андреевич Марков(1856年6月14日-1922年7月20日),俄国数学家。1874年马尔可夫入圣彼得堡大学,师从切比雪夫,毕业后留校任教。1886年当选为圣彼得堡科学院院士。马尔可夫的主要研究领域在概率和统计方面,他因提出马尔可夫链的概念而享有盛名。

马尔可夫链已经成功应用到物理、化学、语音识别、信息科学、金融等领域,谷歌所使用的网页排序算法就是由马尔可夫链定义的。

图1 安德雷·安德耶维齐·马尔可夫

1

马尔可夫过程

对于一个随机过程,如果其未来所处的状态仅与其当前状态有关,而与过去的状态无关,则该随机过程被称为马尔可夫过程。

2

马尔可夫链

假设马尔可夫过程参数集T是离散的时间集合,T={0,1,2,3,…},则相应取值集合空间是离散的状态集I=

设有随机过程,若对于任意的整数和任意,条件概率满足

则称马尔可夫链

简单点就是说,时间和状态都是离散的马尔可夫过程即为马尔可夫链

3

转移概率

马尔可夫链在时刻n的一步转移概率,其中,简称为转移概率。

4

移概率矩阵

设P表示一步转移概率所组成的矩阵,且状态空间I={1,2,…},则:

称为系统状态的一步转移概率矩阵,它具有的性质:

5

n步转移概率、转移矩阵

马尔可夫链的n步转移概率,并称马尔可夫链的n步转移矩阵。

举个栗子

说到这里,可能还会有人问“随机过程是啥玩意儿”,“马尔可夫链到底是什么鬼”。数学定义总是简单、精准、严谨,几乎没有逻辑漏洞,但可能不是特别容易理解,那么这个小节我们举几个栗子,更形象的解释下这些概念。


随机过程,就是一系列随机变量的集合。比如说,每丢一次硬币,便产生一个随机变量X,那么一次又一次的丢下去,便产生一系列的随机变量X1,X2,…,Xi,…。随机变量序列集合起来就是一个随机过程

那么马尔可夫链又是什么呢?它其实是随机过程的一种,具体是什么还是举个例子吧。


无忌是达观数据的员工,每天下午4点到5点有仨状态:吃水果(公司免费提供的、各种管饱)、写代码、技术交流,这就是传说中的状态分布。那么明天的这个时间段无忌会做什么呢?后天呢?大后天呢?

假如他的状态转移是有概率的,比如今天吃水果,那么明天还吃水果的概率是0.3,写代码的概率是0.6,技术交流的概率是0.1。直接看下表:

表1 无忌的状态转移概率

左边一列是今天的状态,上面一行是明天的状态。图中的0.1表示的是无忌今天吃水果,第二天技术交流的概率。这就构成了一阶转移概率矩阵。这个例子中,无忌明天的状态仅仅与今天的状态有关,与过去无关,同时三种状态是离散的,构成了一个马尔可夫链

推荐应用

1

用户行为分析

为了让推荐结果符合用户口味,我们需要深入了解用户。如何才能了解一个人呢?《论语 公冶长》中说“听其言,观其行”,也就是说可以通过用户留下的文字和行为了解用户的需求。用户行为数据最简单的存在方式就是日志,用户的每次浏览、点击、购买、收藏等都记录在日志中,这些行为数据对于接下来的构建转移概率矩阵有着至关重要的作用。

假如在某购物网站中,对某物品的一次购买,称作一个状态。某用户在时刻购买了物品a,这里我们定义为状态{a};在接下来时刻该用户又购买了物品b和c,则由状态{a}转移到了状态{b}或{c};这时在时刻购买了d,状态转移到了{d},这样的话用戶不停的购买,状态也不停地转移。形成了一条购买链,如图。

图2 某用户的购买链

在这个例子中,我们仅仅讨论了针对单个用户如何构建购买链,对于所有用户来说,道理一样,只不过状态集扩大了而已。

2

转移矩阵的构建及使用

我们先讨论下非个性化马尔可夫模型,即假设每一个用户的转移矩阵是相同的,这样的话个性化推荐只能体现在将转移矩阵应用在用户的最后一次行为操作。

继续举个例子,通过对某段时间内所有用户行为进行分析,抽取出这些状态转移样本数据:(a,b,c)->(b,c)、(b,c)->(a,b),然后我们可以得到如下转移矩阵M:

表2 转移矩阵

假如某个用户当前的操作物品是a、c,那么根据上面得出的转移矩阵,我们就可以计算出接下来该用户操作各个物品的程度,对这些结再进行标准化后就可以认为是接下来对各个物品进行操作的概率,= 0.5*(0 + 0.25) = 0.125;= 0.5*(0.5 + 0.5) = 0.5;= 0.5*(0.5 + 0.5) = 0.5;

= 0.11,=0.44,=0.44,

这个计算逻辑看起来可能不是特别容易理解,直接上公式,简洁明了!

最后对进行标准化即可得到接下来对a、b、c的操作概率。

,其中A是用户当前的行为矩阵,M为计算出来的转移矩阵,对结果F进行标准化后即可得到未来用户行为的概率预测矩阵有了当前行为以及概率预测矩阵,我们就可以根据概率大小进行排序,优先推出概率大的物品,达到个性化的目的。

而对于个性化马尔可夫模型,可以怎么处理呢?这里我们可以将对物品的偏好转化为对特征的偏好,假如某个物品的特征是“娱乐、影视”,那么对该物品的一次行为操作可以转化为对“娱乐”、“影视”的操作。

这样,通过对某个用户的历史行为日志进行挖掘分析,就可以得出用户在操作“娱乐”特征的情况下,下个时间段操作“影视”的概率,也就构成了用户的特征喜好状态转移矩阵。这样的话,可以计算出每个用户的特征喜好状态转移矩阵,达到真正意义上的个性化。

3

多行为加权融合

上面提到的转移矩阵的计算是基于用户的某一种行为操作,即通过用户的单一行为来得到用户的偏好转换。为了能更好的表示用户的喜好状态转换,可以通过多行为加权融合的方式来解决。

假如用户的行为操作有点击、购买、收藏、点赞,那么可以对每种行为类型计算出特征喜好状态转移矩阵,并得出用户在下个时刻的操作列表,也就是推荐列表,最后将多个推荐列表进行加权融合得出最终的列表结果。

4

多阶马尔科夫融合

考虑到用户操作行为的随机性,用户从状态s1到状态s5可能受到s2、s3或者其他因素的影响。并且在个性化推荐长尾现状的部分影响下,单个用户在极短时间内兴趣偏好不会发生太大变化。这里可以通过采用多阶马尔可夫模型融合的方式进行对这种情况进行优化。比如一段时间内用户从状态s1到s2,再到s5,即s1->s2->s5,那么这次的状态转移记为s1->s5的二阶转移次数。

通过计算用户行为的多阶状态转移矩阵,基于相关矩阵得出预测列表,最后加权融合即可得到我们需要的推荐列表。这里具体采用几阶模型,可以根据实际场景进行效果测试,阶数越高,预测的结果更大的基于用户长期的兴趣偏好,阶数约低,预测的结果更大的是基于用户短时间内的兴趣偏好。

总结

本文首先简单介绍了马尔可夫相关的数学概念,然后通过例子形象地解释了随机过程、马尔可夫、转移概率等实际含义。在推荐系统的应用上,分析了如何通过用户操作记录进行构建状态转移矩阵以及转移矩阵的使用。考虑到推荐的效果,我们又进一步介绍了多行为加权融合以及多阶马尔可夫融合的两个方案。

关于作者

张可  达观数据推荐算法工程师,负责达观数据个性化推荐引擎的研发、优化,以及推荐系统机器学习算法的具体应用。一直在路上。

达观数据
达观数据

达观数据是一家专注于文本智能处理技术的国家高新技术企业,获得2018年度中国人工智能领域最高奖项 “吴文俊人工智能科技奖”,也是本年度上海市唯一获奖企业。达观数据利用先进的自然语言理解、自然语言生成、知识图谱等技术,为大型企业和政府客户提供文本自动抽取、审核、纠错、搜索、推荐、写作等智能软件系统,让计算机代替人工完成业务流程自动化,大幅度提高企业效率。

入门应用个性化推荐系统马尔可夫模型
31
相关数据
达观数据机构

达观数据成立于2015年,是中国领先的文本智能处理企业,利用先进的文字语义自动分析技术,为企业、政府等各大机构提供文本自动抽取、审核、纠错、搜索、推荐、写作等智能软件系统,让计算机代替人工实现业务流程自动化,大幅度提高运营效率。 达观数据为企业提供完善的文本挖掘、知识图谱、搜索引擎和个性化推荐等大数据服务,是国内唯一一家将自动语义分析技术应用于企业数据化运营的人工智能公司。

http://www.datagrand.com/
排序算法技术

排序算法是将一串数据依照特定排序方式进行排列的算法,最常用到的排序方式是数值顺序以及字典顺序。基本上,排序算法的输出必须遵守下列两个原则:输出结果为递增序列(递增是针对所需的排序顺序而言);输出结果是原输入的一种排列、或是重组。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

协同过滤技术

协同过滤(英语:Collaborative Filtering),简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要。协同过滤又可分为评比(rating)或者群体过滤(social filtering)。其后成为电子商务当中很重要的一环,即根据某顾客以往的购买行为以及从具有相似购买行为的顾客群的购买行为去推荐这个顾客其“可能喜欢的品项”,也就是借由社区的喜好提供个人化的信息、商品等的推荐服务。除了推荐之外,近年来也发展出数学运算让系统自动计算喜好的强弱进而去芜存菁使得过滤的内容更有依据,也许不是百分之百完全准确,但由于加入了强弱的评比让这个概念的应用更为广泛,除了电子商务之外尚有信息检索领域、网络个人影音柜、个人书架等的应用等。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

随机过程技术

在概率论概念中,随机过程是随机变量的集合。若一随机系统的样本点是随机函数,则称此函数为样本函数,这一随机系统全部样本函数的集合是一个随机过程。实际应用中,样本函数的一般定义在时间域或者空间域。随机过程的实例如股票和汇率的波动、语音信号、视频信号、体温的变化,反对法随机运动如布朗运动、随机徘徊等等。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

马尔可夫模型技术

「马尔可夫模型」是指基于马尔可夫性质的模型,其假设一个给定过程的未来状态仅取决于当前状态。根据系统状态是否完全可被观测以及系统是自动的还是受控的,可以将常见的马尔可夫模型分成四种:马尔可夫链、隐马尔可夫模型(HMM)、马尔可夫决策过程(MDP)和部分可观测马尔可夫决策过程(POMDP)。另外还有马尔可夫随机场(MRF)和马尔可夫链蒙特卡洛(MCMC)这两个模型也常常被用于近似和预测。

语音识别技术

自动语音识别是一种将口头语音转换为实时可读文本的技术。自动语音识别也称为语音识别(Speech Recognition)或计算机语音识别(Computer Speech Recognition)。自动语音识别是一个多学科交叉的领域,它与声学、语音学、语言学、数字信号处理理论、信息论、计算机科学等众多学科紧密相连。由于语音信号的多样性和复杂性,目前的语音识别系统只能在一定的限制条件下获得满意的性能,或者说只能应用于某些特定的场合。自动语音识别在人工智能领域占据着极其重要的位置。

马尔可夫链技术

马尔可夫链,又称离散时间马尔可夫链,因俄国数学家安德烈·马尔可夫得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

推荐文章
表2的c行数据之和为什么是1.25呢,不应该是1吗