初识随机游走-阿里云开发者社区

开发者社区> 人工智能> 正文

初识随机游走

简介: 一、随机游走简介   随机游走(Random Walk)又称随机游动或随机漫步。在我们生活中处处都存在着与Random Walk有关的自然现象,例如气体分子的运动,滴入水中的墨水,气味的扩散等(如图1.4)。

一、随机游走简介

  随机游走(Random Walk)又称随机游动或随机漫步。在我们生活中处处都存在着与Random Walk有关的自然现象,例如气体分子的运动,滴入水中的墨水,气味的扩散等(如图1.4)。Random Walk是扩散过程的基础,因此它被广泛地用于对物理和化学等扩散现象的模拟上。 

 

 

  此外,Random Walk又是设计随机算法的一个非常广泛的工具,其中一个典型的例子就是 “马尔可夫链蒙特卡罗”法(MCMC)[14] [15]。MCMC是解决近似计算问题一种重要方法,它能以比确定性算法快指数级的速度提供解决问题的最好随机方法,目前已经被广泛地应用在统计领域。 

二、图上的随机游走

  图上的 Random  Walk 是指给定一个图和一个出发点,随机地选择一个邻居结点,移动到邻居结点上,然后把当前结点作为出发点,重复以上过程。那些被随机选出的结点序列就构成了一个在图上的Random Walk过程,如下图所示。

  早期的搜索引擎例如Yahoo!使用的是关键词匹配技术,其性能容易受到关键词频率的欺骗,所以搜索效果不是很好。但是到1998年Jon Kleinberg 提出了HITS[17]算法,以及Sergey Brin  和 Larry Page 提出了 PageRank[18]算法之后,搜索的正确率就得到了巨大的改观,其原因就是这两种技术都建立在共同理论支柱就是图上的 Random  Walk上。

  Random  Walk 是随机过程(Stochastic  Process)的一个重要组成部分,通常描述的是最简单的一维 Random  Walk 过程。下面给出一个例子来说明:考虑在数轴原点处有一只蚂蚁,它从当前位置(记为x(t) )出发,在下一个时刻( x(t+1))以 的概率向前走一步(即 x(t+1)= x(t)+1),或者以 的概率向后走一步(即 x(t+1)= x(t)-1),这样蚂蚁每个时刻到达的点序列 就构成一个一维随机游走过程。

  本质上 Random  Walk 是一种随机化的方法,在实际上生活中,例如醉汉行走的轨迹、花粉的布朗运动、证券的涨跌等都与 Random  Walk 有密不可分的关系。Random Walk已经被成功地应用到数学,物理,化学,经济等各种领域。当前研究者们已经开始将 Random  Walk 应用到信息检索、图像分割等领域,并且取得了一定的成果,其中一个突出的例子就是 Brin 和 Page 利用基于 Random Walk 的 PageRank 技术创建了 Google 公司。

三、相关理论

  马尔科夫链:t+1时刻的状态只与t时刻有关,也就是只与上一步状态有关,如果从i到j的转移概率与时间无关称为齐时马尔科夫链,否则称为非齐时马尔科夫链。

  随机游走与谱图理论,图上的拉普拉斯算子和格林算子。

  我想着如何用RW来扩展信任网络。

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章