内容交付适应资源有限,推断出用户的兴趣

文摘

探讨适应信息系统受到政策动态和随机上下文如移动多媒体网站的访问。在我们的方法中,适应代理应用序贯决策策略下的不确定性。我们专注于此类决策的建模过程取决于上下文是完全或部分可观测的。我们的案例研究是一个电影浏览服务在移动环境中,我们利用马尔可夫决策过程模型(MDP)和部分可观测的MDP (POMDP)。我们推导出适应政策服务,考虑到有限的网络带宽等资源。我们进一步完善这些政策根据部分可观测的用户宏观利益水平估计从隐式反馈。通过大量的模拟验证了我们的理论模型。

1。介绍

访问选择计算机服务继续进步,促进我们与家人,朋友,或工作场所。这些新的访问选择包含广泛的移动和分布式设备,我们的技术环境变得真正普及。这些设备操作的执行上下文异构是很自然的。无线网络提供的资源随用户的数量和连接的位置。也可用内存和处理能力动态波动。最后但同样重要的是,用户的需求和期望在任何瞬间可以改变。因此,有许多研究项目旨在提供现代信息系统根据环境变化与适应能力。

为了处理高度动态的情况下,本文中,我们提出的方法是基于一种适应性的代理。代理感知的连续状态的背景下,由于观察,和实施适应行为。通常,适应方法在文献提出假设上下文数据很容易感知或至少是没有可能的歧义识别当前上下文的状态。称之为一个可观察到的上下文。在这项工作中,我们放松这个假设,因此处理部分可观测的上下文。

我们的案例研究是一个信息系统在移动设备上浏览多媒体的描述电影。是说明给定的关键理念适应策略可以根据用户兴趣的估计。用户的兴趣显然不是直接可见的系统。

我们研究建立“隐含的反馈”,以便适应代理估计用户兴趣水平虽然与上下文交互(1,2]。第一部分综述重要元素的艺术和细节我们适应的状态的方法。接下来,我们介绍我们的模型所使用的两种形式:马尔可夫决策过程(MDP)和部分可观测的MDP (POMDP)。以下部分介绍我们的案例研究和建立信息系统的操作原则。由于MDP,我们为信息系统形式化一个适应政策视为一个可观测的上下文。然后我们展示如何完善这一政策根据用户兴趣使用POMDP(精制本身从一个MDP)。各种实验验证这种方法并给出一个实际的观点适应代理的行为。我们在文章结尾给出了一些观点。

2。相关工作

本节介绍有用的当前文学领域的适应动态执行上下文帮助位置我们适应的方法。自适应系统通常提供适应能力,因此,这些系统可以根据可用的资源分类,用户首选项,或更一般的上下文。

2.1。基于资源的适应

鉴于现代网络和移动设备的异构特性,有一个明显的需要适应有限的资源。网络的QoS参数不同的可用带宽,损失率,或延迟。终端的功能也非常异构的内存大小,处理能力,显示区域。

来管理这些限制,可以适应的内容要显示或访问/分销模式。当考虑内容适应,几位作者提出分类3)的基本组成部分的内容(一个媒体,例如)或整个文档的结构转换。媒体可以被转换(4),转换为另一种形态(5),或总结6]。分布或访问也适用,例如,通过优化流(7]或通过修改服务的交互的程度。

2.2。User-Aware适应

除了适应能力可用的资源,一个还应该考虑应用程序的适应根据人为因素是用户首选项和满意度。从今以后,我们将描述三个主要研究方向的文学。

第一个研究方向包括转换适应机制,最大化用户服务感知的质量。一个典型的场景是流的转换策略的选择(例如,视频)为了最大化感知质量给予有限的带宽(8]。最好的参数调整:是什么视频的大小,其彩色分辨率,或帧频吗?模型被提出(9,10)来评估质量变异来自技术和用户的观点。他们被组织在三个不同的层面:网络、媒体和内容的水平。这一研究考虑的关键因素是如何影响用户感知的客观多媒体质量变化。

第二个方向与活动用户建模。这里的想法是由建模用户配置文件定制应用程序为了以后认出他们。例如,自适应超媒体内容或服务(11为用户提供导航支持”更容易/更好的学习使用在线教育服务”或支持“电子商务站点更高效的销售”根据用户配置文件。通常,这些系统使用数据挖掘技术来分析使用数据访问模式和发现有趣的关系(12]。这些知识可能是有用的识别资料并选择最合适的修改来改善内容的有效性。

第三个研究方向发现在前两个的动机。为了学习用户模型或评价内容改编的感知影响的解决方案,有必要明确要求用户评估或者获取隐含的反馈信息。研究旨在评估“隐式反馈”(如果)正在经历一场越来越感兴趣,因为它避免了结合重要的显式返回的集合(侵入和昂贵的)(1]。这些如果方法被用于特定的解码用户反应在信息搜索系统2]。这个想法是为了测量用户对查询结果的列表,以适应搜索功能。研究中隐含的反馈信号可以考虑:总浏览时间,点击的数量,滚动的互动,互动的一些特征序列。在我们的工作中,我们估计用户兴趣使用如果通过解释交互序列(2,13]。此外,从元数据的角度来看,如果可以提供隐式描述符如用户兴趣描述符所示(14]。

2.3。混合资源和User-Aware适应

更一般的适应机制可以通过结合资源型和基于用户的适应。用户和资源的特征混合设计对于一个给定的一种适应性策略上下文。例如,流的一个沉重的媒体内容可以通过预取改编而考虑用户特点和资源约束(15]。

为移动和普遍的系统资源和用户之间的联系的geolocalization首先考虑用户,甚至可以及时追踪和预测(16]。

在数字项MPEG-21适应(DIA)标准,上下文描述符组织网络和终端的功能和用户的偏好和适应多媒体作品作者的建议。由于这种复杂性,规范只能提出工具简单描述的运行上下文作为一组精心挑选和可扩展的描述符(17]。这是通过元数据的方法,让自由的概念适应组件,而授权高水平的互操作性(18]。

自然环境变化的元素。因此,动态上下文的一个说话,推而广之,动态适应。重要的是要注意,静态适应静态上下文元素是可能的:一个人可以协商一次,总是以同样的方式目前用户最喜爱的语言进入一个多语言的服务。相反,适应算法本身和/或其参数可以动态地改变根据上下文状态(19]。我们适应方法是符合后者的情况下。

研究的一个重要元素在环境适应适应决策的区别及其有效实施(18]。在普遍的系统中,一个可以决定一个文档必须被转换成另一种格式,但仍有些问题需要回答。是一个代码转换组件可用?在哪里可以找到吗?应该组成一个转码服务吗?为了找到这些问题的解决方案,许多作者提出使用人工学习技术来选择正确的决定和/或适当的适应机制的实现(参见[20.]审查)。在这种情况下,运行环境的描述给出决策代理人作为输入,预测的最佳适应行动根据它以前学到的东西。我们把这个想法与强化学习原理。

我们模型的上下文动态马尔可夫决策过程的状态是完全或部分可观测的。这种方法提供了手段,找到最优决策根据当前上下文(适应行动)。下一节介绍我们的MDP-based适应的方法。

3所示。马尔可夫决策过程我们正式的方法

图1总结了我们适应的方法,介绍了在21),在本文中进一步完善。摘要动态应用环境的一种适应性策略适应代理。这个代理顺序感知,在离散的时间轴,通过观察上下文的变化。

从其观察,代理将计算上下文状态以应用一种适应性策略。这样的政策只是一个函数映射上下文状态适应决策。因此,背景上的代理行为而决定一个适应行动:它消耗带宽,影响未来用户的交互,增加或减少用户的利益。因此有用,测量其效果将奖励(立即或延迟)与适应行动决定在一个给定的上下文状态。代理可以从其与环境的交互学习和执行被称为强化学习的“试错”的学习22]。它试图加强行动导致一个好的奖励和积累,相反,避免更新结果决定。这个过程是一个持续改进的”决定政策。”

这种动态适应方法是常见的框架序贯决策的政策下的不确定性。在这些框架,不确定性来自两个来源。一方面,上下文可以随机的动态结果可用资源的变化(例如,带宽);另一方面,一个代理的影响本身的决定可以随机的。例如,如果一个适应行动旨在预测用户交互,预测质量显然是不确定的,受到用户的行为变化。

在这种情况下,采用马尔可夫的定义上下文状态,代理的动力学可以建模为一个马尔可夫决策过程(MDP)。这部分介绍了形式主义。

我们最初假设上下文状态变量可观测的代理使其充分条件来识别决策状态没有任何歧义。本文以一步通过精炼适应政策根据用户兴趣。通过用户行为顺序我们估计这个隐藏信息所显示的研究“隐式反馈的评价。“因此,新的决策状态同时包含可观测变量以及一个隐藏的元素与用户兴趣相关。

然后我们继续从MDP部分可观测马尔可夫决策过程(POMDP)。我们最好的知识,应用程序的POMDP部分可观测环境的适应问题尚未被研究。给具体的表达这原始的想法,一个案例研究将在部分4。

3.1。MDP定义

MDP是一个随机过程控制,分配奖励状态之间的转换(23]。它被定义为4倍在哪里状态空间,是行动的空间,是离散时间轴的瞬间是采取行动的时候,状态之间的转换的概率分布,然后呢是一个函数转换的奖励。我们发现在一个正式的方式理解图所需的成分1:在每一个瞬间,代理观察它的状态,适用于行动让系统(随机,根据)到一个新的状态,并接收一个奖励。

正如前面提到的,我们正在寻找最好的策略对累积奖励。政策是一个函数相关联一个动作与每个国家。我们的目标是找到最好的一个:。

MDP分配一个理论框架值函数 每一个政策。这个值函数将每一个国家全球奖励,得到应用开始。这样一个价值函数允许比较政策。一项政策优于另一项政策如果 通过应用获得的预期回报的总和从是由一个参数加权为了限制的影响无限遥远的奖励, 总之,对于每一个国家,这个值函数给出了预期和未来可以获得奖励,如果政策从这个国家应用。这个值函数允许最优政策的形式化研究这是一个与最佳值函数。

贝尔曼最优性方程的最优值函数的特点和最优政策可以获得它。在的情况下三准则和静止的奖励,他们可以编写如下:

3.2。分辨率和强化学习

在考虑解决MDP,我们可以区分两种情况,根据是否已知或未知的模型。当模型(概率)和奖励是已知的,可以找到一个动态编程解决方案。

操作员验证根据 是一个收缩。贝尔曼方程在可以通过使用一个不动点迭代方法解决而选择随机,然后反复应用算子改善当前的政策有关。如果奖励是有界的,序列收敛于并允许计算。

如果模型是未知的,我们可以用强化学习算法解决MDP (22]。强化学习方法旨在通过迭代寻找最优政策最优值函数的估计。的q学习的算法是一种强化学习方法,能够解决贝尔曼方程三标准。它使用模拟迭代估计价值函数基于瞬时变化的观察和与它们相关的奖励。为此,Puterman [23]介绍了一个函数相似,有意义但更容易提取相关的政策,因为它不需要过渡概率。我们可以表达“问价值”作为一个给定的函数的政策和它的价值功能, 因此,很容易看到,尽管缺乏过渡的可能性,我们可以追溯到最优政策, 的原理q学习的算法1说,每次观测后过渡当前值函数为这对夫妇更新,代表当前状态,选择和应用行动,导致状态最直接的奖励。

在该算法中,是一个初始参数表示迭代的数量。的学习速率 是每一对特定的国家行为,在每一次迭代时降低为0。函数”“返回一个新的状态及其相关奖励根据系统的动力学。当前状态的选择和行动的执行是由功能””和“。“函数””是用来初始化值来。

这个算法的收敛已经彻底研究,现在。我们假设以下。

(我) 和是有限的,。(2)每一对访问无限次数。(3) 。在这些假设下,函数收敛几乎肯定。让我们回想一下,几乎肯定意味着收敛序列收敛于用一个概率等于1。实际上,序列通常是定义如下: 在哪里代表国家的次数访问,决定。

3.3。部分观察和POMDP定义

在许多情况下,观察决定代理能够捕获(见图1只有部分和不允许没有歧义识别上下文的状态。因此,一种新的问题需要解决:部分可观测马尔可夫决策过程。美国潜在的MDP是隐藏的,只有观察过程将有助于重新认识过程的运行状态。

部分可观测马尔可夫决策过程被定义为:

(我) 底层MDP;(2) 一组观测;(3) 一个观察函数映射每个州在观察一个概率分布的空间。观察到的概率了解代理的状态将引用如下:。

Non-Markovian行为
值得注意的是,在这个新模型中,我们松散的一种广泛使用的财产mdp的分辨率,即马尔可夫过程的观察过程。下一个观察的概率可能不仅取决于当前的观察和采取行动,但也在前观察和操作,

随机的政策
它已被证明的结果和使用MDP分辨率算法收敛不适用了。POMDPs需要使用随机和不确定性的政策,至于MDP (24]。

3.4。决议

POMDP经典方法试图带回底层MDP解决问题。两种情况是可能的。如果MDP模型是已知的,一个不能确定的确切状态集上的系统,但概率分布(一种可能的状态信念状态)。在第二的情况下,不知道模型参数,代理尝试构建MDP模型仅依赖观察的历史。

我们的实验测试床使用提供的分辨率软件包卡桑德拉et al。25),相信国家的潜在的无限空间使用线性编程方法。

4所示。案例研究:电影演示移动终端系统

我们在这里介绍一个系统在移动设备上浏览电影描述。对于这个系统,我们的战略目标是适应多媒体内容(即表示。,电影描述)而不是将媒体本身。这个案例研究的目的是既简单的教学,同时整合程度的现实的交互性。

4.1。互动的电影数据库的访问

图2介绍了信息系统从pda等移动终端访问。关键字搜索允许用户获得各种电影描述有序列表的链接。在这个列表中,用户可以跟踪一个链接到一个有趣的电影将被称为(相关的交互clickMovie);然后,他或她可以咨询关于电影的细节问题。这磋商将调用一个全屏互动表示和导航场景详细如下。浏览一部电影的详细信息,用户可以返回查询结果的列表(交互回来在图2)。然后可以访问另一个有趣的电影的描述。访问的索引将被称为电影描述。

为了简化上下文建模,我们选择考虑浏览序列索引。我们的问题变成了一个旨在调整内容(电影描述)在这个序列。我们的执行环境是动态的,因为带宽的()变化,移动网络非常频繁的问题。为简单起见,我们不考虑其他重要参数等移动终端的信号强度,用户的移动性和权力约束。

当我们考虑到浏览会话在高级别上,我们不需要提供特殊规格的最终目标服务可以租赁/购买DVD,下载一个媒体,等等。正确地管理整个的下载或流媒体是一个单独的问题,这里不考虑。

4.2。从最简单到最富有的描述

介绍电影的细节,是可能的(参见图三种形式的描述3)。穷人版本(称为“文本”)组织一起小海报图片,一个简短的文本描述,链接指向更多生产照片以及视频的链接悬垂型。中介版本()提供了一个幻灯片的还是照片和拖车的链接。最富有的版本()包括,此外,该视频预告片。

可用带宽()是可变的,三个版本的使用并不是等价的。下载内容所需的带宽增加的复杂性版本()。换句话说,对于一个给定的带宽,延迟被用户在不同版本的下载成长与内容的大小比例。

更准确地说,我们现在指出两个问题所产生的动态适应的不存在可用带宽变化时的内容。适应策略可以系统地只选择其中一个上面提到的三种可能的选择。如果它总是选择最富有的版本(),这影响用户体验糟糕的网络环境的行为(低带宽)。虽然强大的延迟可以被容忍而浏览第一个查询结果(小指数),如果很快就变得不可接受的生长。如果适应策略选择系统的最简单的版本(),这也会产生有害影响用户的行为。尽管对其他资源的链接(法师和ideo,缺乏这些可视化组件,通常激发兴趣,不鼓励进一步浏览。提出一个重要的和一个合法的问题可以被称为一个“合适”的适应策略。

4.3。适当的适应政策的性质

上述两个例子的政策(一个“雄心勃勃,”另一个“温和的”)显示之间的关系有多复杂的版本,浏览电影的数量,所花费的时间服务,服务的质量,可用带宽和用户兴趣。深入分析这些关系可以表示一个研究项目。我们不主张将这种分析在这篇文章中,但我们只是想展示一个政策,适应代理可以从模型自动生成上下文状态可观测或部分可观测的地方。

良好的适应政策的三个属性可以确定如下。

(1)版本选择呈现的内容必须简化可用带宽减少(是简单的比,自己简单的比(2)必须简化版本增加:直接选择丰富的第一浏览电影版本的描述,通常是最相关的(正如我们已经提到的,我们应该避免大延迟大的值和小。(3)版本必须丰富如果用户显示查询结果的高利息。简单的基本想法是非常感兴趣的用户更可能是病人和更容易容忍大下载延迟。前两个属性相关的上下文参数的变化,我们认为可观测(和),而第三个是一个隐藏的相关元素,即用户的兴趣。在这个阶段,鉴于这三个属性,一个适应政策对我们的案例研究可以表示:版本(的选择T,我,或V)了解和并估计利息的一种方法。

4.4。在导航场景

这一段介绍了一些可能的导航场景示例。图4显示了不同的可能步骤在导航和介绍不同的事件跟踪。在这个图中,用户选择一个电影(事件clickMovie),表示在版本T下载(事件页面加载没有用户打断这个下载)。对这部电影感兴趣,用户请求生产照片,下面的链接图片(事件linkI)。在一个案例中,下载太长,用户中断(事件stopDwl意味着stopDownload)然后返回到电影列表(事件回来)。在其它情况下,用户等待下载的图片完成,然后开始查看幻灯片(事件startSlide)。要么这个幻灯片显示完全,然后一个事件EI(简称EndImages),或可视化是不完整的,导致事件stopSlide(不代表图中)。接下来,可以跟随链接到拖车(事件linkV);这里一个不耐烦的用户可以中断下载(stopDwl)或开始播放视频(玩)。然后完全可以观看视频(事件电动汽车EndVideo)或停止(stopVideo),返回(事件之前回来)。

显然,这个例子不介绍所有的可能性,特别是如果视频没有下载但流。流场景介绍不同的挑战和需要播放缓冲区,丰富的集合可能交互(例如,stopBuffering)。与此同时,用户可以选择不与该媒体:我们引入了一系列事件页面加载,noInt(没有交互),回来。同样,一个回来可能只是在吗页面加载,一个stopDwl后可能发生事件吗clickMovie前,看视频图片也是可能的。

5。问题陈述

5.1。奖励精心挑选的适应策略

从之前的例子和定义相关的交互,可以提出一个简单的机制旨在奖励相关的适应策略。一个版本(,,或)被认为是选择在一个给定的情况下,如果不是由用户质疑。一个版本的重新评估太简单的建议,例如,通过完整的消费的图片。同样,一个版本的重新评估太丰富的表示的部分消费视频下载。四个简单原则指导我们的奖励制度如下。

(我)我们奖励活动EI的版本和。(2)我们奖励活动电动汽车如果所选的版本。(3)我们惩罚的中断事件(“停止”)。(iv)我们支持的更简单的版本没有或很少交互。因此,一个版本是充分的,如果用户不请求(或至少不完全消耗)的照片。一个版本最好是如果用户足够感兴趣,并获得足够的资源下载和查看照片的集合(奖励吗EI)。同样,一个版本如果用户查看所有照片(采用奖励EI),试图下载视频,被迫中断,因为有限的带宽。最后,一个丰富的版本如果用户采用消费状况良好的视频完全(奖励电动汽车)。以下这些原则决策模型形式化。

5.2。向一个隐式的兴趣

前面介绍了导航和交互可以估计用户的利益。我们继续通过评估“隐式反馈”和使用事件的序列来估计用户的兴趣水平。我们的方法是受26),是基于以下两个想法。

第一个想法是确定根据他们的建议:两种类型的交互越来越感兴趣(linkI、linkV startSlide、玩、EI、电动车)或减少利息(stopSlide、stopVideo stopDwl noInt)。因此,事件分发(视为发生的概率)取决于用户的兴趣浏览电影。

第二个想法是考虑不仅一个正在运行的事件更新用户兴趣的估计也把整个的事件序列是更重要的。事实上,它最近建立的用户操作响应页面搜索(如谷歌)不仅取决于当前响应的相关性也对全球的相关的查询结果集2]。

后的工作26),模型是自然产生的事件或观测序列的隐马尔科夫模型(HMM)我们在这里不详细定义(例如,看到27])。一个可以简单地翻译前两个想法通过使用一个嗯(隐藏)的几个州的利益。感兴趣的三个州图所示5被称为年代,米,B分别为小的、中等的、大的兴趣。可观测事件的三个分布在每个国家是不同的强调在上面提到的第一个念头。这些差异解释不同的观测序列的事件的顺序演进(第二想法)。这些演进编码由于隐状态之间的转移概率(点画)的兴趣。给定一个序列的观测,嗯可以提供最可能的潜在的隐状态序列或最可能的隐藏状态运行。在这一点上,我们信息系统足够丰富的特性定义一个适应剂应用在不确定性下的政策决策。这些政策可以形式化的框架部分中给出3所示。1。

6。建模内容分发策略

在本节中,我们模型的动态背景下浏览系统(部分4)为了获得适当的适应代理。我们的目标是描述适应政策的马尔可夫决策过程(mdp或POMDP)。

6.1。MDP建模

首先,被认为是一个可观测的上下文。让我们介绍提出的MDP模型。验证的目的是描述适应政策属性1和2中描述的部分4所示。3:介绍电影描述必须简化可用带宽减少或者增加。

一个国家(可见)的上下文是一个元组与电影的排名咨询,可用的带宽,适应代理提出的版本运行事件(见图6)。与,(clickMovie stopDwl,页面加载,noInt linkI startSlide stopVideo stopSlide、EI linkV,玩,电动汽车,回来 )。

获得一个有限和合理数量的州(限制因此MDP大小),我们将数字转换变量根据我们的需求。因此(职责。根据三个层次)可以量化意义开始、中间和结束(分别地。低,三个地区的平均水平,而高),而分段间隔(职责。)。

时间轴MDP所代表的自然顺序的事件,每个事件暗示改变状态。

动态MDP的制约的动态背景下,特别是由用户导航。因此,从一个电影指数来是不可能的。同样,每一个紧随其后的是一个事件。带宽的动态也会产生影响(根据量子化的能级)之间的动态MDP的州。

这部电影描述的选择版本(,,或)提出的适应代理完成当用户遵循电影的链接。这是编码模型的事件。MDP的状态可分为:

(我)决定国家()代理执行的实际行动(有效选择之一T,我,或V);(2)nondecision或中介()州代理不执行任何操作。MDP框架,代理决定在每一个国家。因此,该模型需要丰富的人工操作()以及吸收剂的强罚款收入()。因此,任何有效的行动选择吸收剂中代理处于中间状态的状态,这将是强烈的惩罚。同样,代理将避免决定在决策状态,需要一个有效的行动。因此,有效的行动马克决定国家的访问而上下文的动态(受用户导航和带宽变化)所获得的中介状态之间的转换的行动(行动)。显然这些属性如图6。

换句话说,没有改变的版本在中介状态之间的转换。这个动作(表示该版本)选择决策状态是因此,记忆()在所有下面的中间状态,直到下一个决定状态。因此,MDP捕捉环境的变化动态根据所选的版本。因此,它将能够识别哪些是版本的不错的选择(复制以后在类似的条件下),如果它是对他们的回报。

奖励相关的决定根据所选择的行动。中介状态对应于事件的发生EI和电动汽车获得奖励,根据部分5。1。奖励(其他配方也可能包括,例如,负回报中断事件)定义如下: 喜欢简单版本的用户不与内容交互,不把任何媒体(出口的部分5。1),让我们选择。总结,模型表现在以下方式:代理从一个决定开始状态,它决定一个有效的行动它接收一个“初始”奖励;简单的版本,更大的奖励。根据转换概率基于上下文动态,模型经过中介州它可以接收新的奖励或的时候出现的EI(职责。电动汽车),如果采取了行动是或(职责。)。作为小这些事件更加频繁和高,而更有可能如果没有交互又大又低,MDP

(我)最富有的版本将支持小和高;(2)将有利于最简单的版本大吗和低;(3)将建立一个权衡(根据奖励最佳),所有其他案件。最好的策略的模型显然是与所选的值。为了控制这种选择在实验部分,MDP将定义的简化版本。

一个简化的MDP可以通过记忆的事件的发生和在两个事件之间的导航。因此,我们可以推迟的回报或。这个简化的模型不包含非决策,如果两个布尔值(和(图)被添加到状态结构7)。布尔(职责。)通过1如果事件(职责。两个国家之间的)是观察。其定义的简化MDP州(),行动时间轴的事件顺序,奖励重新定义如下: 可观测的结束表示模型和我们继续通过整合用户兴趣更丰富的POMDP模型。

6.2。POMDP模型

新的部分可观测模型添加一个隐藏变量(它)的状态。的价值它代表了用户的兴趣量子化的三个层次(小,平均大)。能够预测用户的兴趣,我们遵循节中描述的原则5。2和图5。(交互)的事件被从以前的MDP成为POMDP模型中的观测状态。这些观察根据分布它(利息水平)。一个观测序列提供了一个隐式的它后,嗯在图描述的同样的原则5。因此,它成为可能的适应代理提炼其决定根据运行的概率用户的兴趣:s购物中心,平均大。换句话说,这样做细化是根据信仰状态。这个POMDP如图的原则8。

一个隐藏的状态我们的POMDP变成一个元组。符号包括布尔值不变和。

时间轴和行动 是不变的。

的动态模型。当一个事件发生,适应代理决定状态。它选择一个有效的行动和移动模型的随机转换,一个中间状态在哪里和等于0。版本提出的代理是记忆的中介状态在浏览当前的电影。的布尔值和1,如果事件或者,分别观察和维护这个值,直到下一个决定。在运行的电影,浏览和保持不变,而其他因素(,和布尔值)可以改变。

观察结果 发生的事件:。根据美国他们分布。在图8,事件可以观察到和概率(1.0),不能观察到其他地方(和)。

在每一个中间状态,事件分布特征的价值利益。因此,正如图的嗯5,POMDP将知道如何评估,从一系列事件,目前的信仰状态。最可能的兴趣值将发展因此,随着事件发生;如果增加,吗?,吗?,吗?减少的情况下。保持兴趣水平在整个决策状态,当前的利益接收的值对应于最后一次(图8)。

奖励与行动决策状态有关收集以下决策状态我们有所有必要的信息:,吗?,;

7所示。实验结果

为了使用模拟实验验证模型。等开发的软件模拟导航一见图4。每连续两个状态之间的转移概率的导航是一个随机函数的三个参数:,吗?,。带宽模拟是一个随机变量均匀分布在一个时间间隔与今天移动网络兼容。代表一个家庭的随机变量的期望随。的参数是向用户提出的电影版。与此同时,其他实验装置涉及不同分布低点(如正态分布)带宽动态或用户的兴趣进行类似的结果。

7.1。MDP验证为可观测的上下文

验证的MDP模型部分6.1,让我们选择的问题和。最初,间隔的和2日是量子化的粒度级别:和。而不是继续任意选择的值,吗?,吗?,吗?,吗?定义的奖励,我们可以寻找那些开车最优政策表所示1。事实上,这一政策尊重的原则制定4所示。3,可以事先提出由一个专家(表1给了只有对自。)

函数的值对应于简化的MDP,估计在1层长度(两个决策之间的状态和)可以写成: 因为,所有不依赖于行动。 在哪里和代表观察事件的概率分别,知道的版本。

每一对我们已经计算,基于模拟,概率,吗?,吗?。方面的政策保证当且仅当吗 4双写这些不平等从表1和使用估计为,我们获得一个12线性不等式系统变量,,,吗?,吗?。两个系统的解决方案在一个无穷如下: 实验从这些值,我们可以检查我们的MDP模型的正确行为。表2显示了政策由动态编程或自动获得问则算法,与4粒度级别和和奖励。这个表改进之前的粗粒度的政策;这不是一个简单的复制操作(例如,看到双:从来,:从来等)。这项新政策是最优的回报这种细的粒度级别。

解决MDP第二组奖励()给不同的优化(表3),显示了丰富的版本(下划线)比较。解释保持增长的事件相关的奖励,产生一个更复杂的版本的选择,很长一段时间(持续3类,当)。

7.2。POMDP验证:Interest-Refined政策

一旦mdp校准并返回适当的适应政策,他们的奖励可以重用求解POMDP模型。MDP政策的目标是改进的可观察到的情况下估计用户的兴趣。

两个实验步骤是必要的。学习的第一步由POMDP模型和第二解决决策问题。

学习的过程,简单的方法包括实证估算转换和观察概率模拟器的痕迹。从这些痕迹,从频率的计算获得的概率是 POMDP模型,该决议是下一步。解决POMDP是出了名的精致和计算量(例如,见www.pomdp.org提出的教程)。我们使用软件包pomdp-solve 5.3结合最大化策略(与最近的策略称为有限网格)。

pomdp-solve返回的结果是一个自动机,实现了一个“最优”确定的政策,由决策图(策略图)。图的节点包含的操作(),而根据观测转换完成。只有转换由导航过程中被利用。

为了说明这种形式的结果,让我们展示一个足够小的自动机A4页面(图上显示9)。我们选择一个单一的粒度级别和和三个层次。另外,我们考虑到消费的幻灯片之前消费的视频。获得适应政策因此只考虑用户兴趣变化的估计(和不发挥任何作用)。

图9表明POMDP代理学习以一致的方式做出反应。例如,从一个版本,观察页面加载,linkI startSlide、EI noInt,回来以下版本POMDP代理人决定的将序列转换为一个兴趣上升。这一增长更为强大,如果在事件之后EI,用户的链接linkV。这是足以让代理选择版本进一步。

相反,从版本兴趣,一个重要的减少可以观察序列stopVideo startSlide, stopSlide,玩,回来,所以系统决定。一个更小的可以与序列相关的兴趣减少startSlide stopSlide,玩耍,电动汽车,回来,下一个版本选择。这些例子表明,存在一个自然的财富之间的相关性选择版本和隐式的用户兴趣。对于这个问题,和不涉及,给出的版本吗策略图翻译的估计运行(越来越多的兴趣)。因此每个电影版本的选择是仅基于观察的事件而浏览以前的电影。

其他序列导致决策不太直观的或难以解释。例如,序列页面加载,linkI startSlide、stopSlide noInt,回来离开导致这个决定。在这个序列中,利息上升(建议之间的妥协linkI, startSlide)和减少(建议stopSlide, noInt)必须建立。因此,一个决定不会是不合法的。POMDP交易掉这个决定根据其动力学和回报。获得修改图导致的决定对于这个序列,该产品就足够了减少,代表的概率去观察EI的版本,对于一个中等的兴趣。在这种情况下,stopSlide节点,而不是引发环回5,将代理节点1。然后代理将决定自相关的期望收益将会更小。

一般来说,决策自动机取决于和。当,,各有不同,要显示自动机变得太复杂。结果POMDP需要不同的表示。从今以后,使用3粒度级别,2,3和奖励导致policy图超过100个节点。我们把它应用在大量的模拟导航序列。表4给出了统计数据的决策。每三个一组(,,),“代理不知道——清点,转化为百分比。

我们注意到该内容统计时富有兴趣增加,再次证明利息估计从以前的观测。让我们举一个例子,考虑右下方的表的一部分4(对应于和)。政策的概率提出版本增加的利益:从0%(小利益)到2%(平均利息),那么10%(大的兴趣)。

此外,当和/或增加,利益的趋势是正确的。例如,对于一个给定的一组和(和),该版本越来越富裕和带宽的增加(1%T,99%的我,0%的V)(0%T,51%的我,49%的V)。

POMDP能力完善适应政策根据用户兴趣从而验证。一旦POMDP模型解决(离线分辨率),获得自动机很容易实施在线通过编码成一个适应代理。

8。结论

本文表明,连续的不确定性条件下的决策过程非常适合定义动态环境的适应机制。根据上下文状态的类型(可见或部分可观测的),我们展示了如何描述适应政策通过求解马尔可夫决策过程(MDP)或部分可观测的MDP (POMDP)。这些想法已经应用于适应电影浏览服务。特别是,我们提出了一个方法提炼一个给定的适应政策根据用户兴趣。这项工作是多方面的视角。我们的方法可以应用于奖励的情况明确相关的服务(例如,最大化租dvd)的数量。有趣也将扩展我们的模型与功能耦合的推荐系统和/或从多媒体搜索系统。在后一种情况下,我们会受益很多从真实数据的集合,也就是说,航海日志。这些研究方向将指导我们的未来的工作。

引用

1. d·凯利和j . Teevan“隐式反馈推断用户偏好:参考书目,“市立图书馆论坛,37卷,不。2,18-28,2003页。视图:出版商的网站|谷歌学术搜索
2. t . joachim l . Granka锅,h . Hembrooke g .同性恋,“准确解释点击数据隐含的反馈,”学报》第28届年度国际市立图书馆会议在信息检索的研究和开发(SIGIR 05)萨尔瓦多,页154 - 161年,巴西,2005年8月。视图:出版商的网站|谷歌学术搜索
3. t . Lemlouma和n . Layaida“适应媒体资源有限的设备,”第七届国际会议上电子出版学报》(ICCC / 03年联合会)葡萄牙米尼奥,页209 - 218,,2003年6月。视图:谷歌学术搜索
4. m . Margaritidis和g·c . Polyzos“适应无处不在的互联网多媒体技术,”无线通信和移动计算,1卷,不。2、141 - 163年,2001页。视图:出版商的网站|谷歌学术搜索
5. t . c . Thang y . j .荣格,y . m . Ro“基于动态规划的适应乌玛的多媒体内容”第五届环太平洋学报》会议上先进的多媒体信息处理(PCM 04年)卷,3332在计算机科学的课堂讲稿施普林格,页347 - 355年,东京,日本,2004年11 - 12月刊。视图:谷歌学术搜索
6. a . Divakaran k . a .狮子狗r . Radhakrishnan z,和r . Cabasson视频摘要使用MPEG-7运动活动和音频视频挖掘中描述符Kluwer学术出版商,多德雷赫特,荷兰,2003年。
7. b·吉伦特·m·卡尔曼y . j .梁和r·张“channel-adaptive视频流的进步,”学报IEEE国际会议上图像处理(ICIP ' 02),1卷,页9 - 12,罗切斯特,纽约,美国,2002年9月。视图:出版商的网站|谷歌学术搜索
8. g . Ghinea g . Magoulas,“感知的服务质量考虑:一个集成的角度来看,“学报IEEE国际会议多媒体和世博会(ICME ' 01),页571 - 574,东京,日本,2001年8月。视图:谷歌学术搜索
9. s r·格列佛t .衬线,g . Ghinea”普遍的和独立的计算:变量的感知影响多媒体质量,”国际人类计算机研究杂志》上,60卷,不。5 - 6,640 - 665年,2004页。视图:出版商的网站|谷歌学术搜索
10. s . r .格列佛和g . Ghinea”定义用户感知的分布式多媒体质量”,ACM交易多媒体计算、通信和应用程序,卷2,不。4、241 - 257年,2006页。视图:出版商的网站|谷歌学术搜索
11. p . Brusilovsky文澜和大肠”,用户模型自适应超媒体和自适应教育系统,”自适应网络:Web个性化的方法和策略卷,4321在计算机科学的课堂讲稿页3-53 Springer,柏林,德国,2007年。视图:出版商的网站|谷歌学术搜索
12. c·罗梅罗,s·文图拉和p . De胸罩”知识发现与遗传编程对课件作者提供反馈,”用户建模和User-Adapted交互,14卷,不。5,425 - 464年,2004页。视图:出版商的网站|谷歌学术搜索
13. t . Syeda-Mahmood和d . Ponceleon学习视频浏览行为及其应用生成的视频预览”诉讼的ACM国际多媒体会议和展览(多媒体的01),9卷,页119 - 128,渥太华,加拿大,2001。视图:出版商的网站|谷歌学术搜索
14. c . Pleşca诉Charvillat, r . Grigoras”User-aware适应通过主观的元数据和推断出隐含的描述符,”多媒体Semantics-The元数据的作用卷,101研究计算智能施普林格,页127 - 147年,柏林,德国,2008年。视图:出版商的网站|谷歌学术搜索
15. r . Grigoras诉Charvillat, m . Douze”优化hypervideo导航使用马尔可夫决策过程的方法,”第十届ACM国际多媒体会议学报》上页39-48 Juan-les-Pins,法国,2002年12月。视图:出版商的网站|谷歌学术搜索
16. g . Yavaşd . Katsaros O。Ulusoy, y马诺洛波洛斯,”位置预测的数据挖掘方法在移动环境中,“数据和知识工程,54卷,不。2、121 - 146年,2005页。视图:出版商的网站|谷歌学术搜索
17. h·科施l . Boszormenyi m .痛单位m . Libsie p . Schojer和a . Kofler“多媒体元数据的生命周期,”IEEE多媒体,12卷,不。1,第86 - 80页,2005。视图:出版商的网站|谷歌学术搜索
18. c·蒂莫和h . Hellwagner可互操作的自适应多媒体通信,”IEEE多媒体,12卷,不。1,第79 - 74页,2005。视图:出版商的网站|谷歌学术搜索
19. o . Layaida s . b . Atallah, d . Hagimont”一个动态可配置和可重构框架基于网络的多媒体改编,“互联网技术杂志》,5卷,不。4、363 - 372年,2004页。视图:谷歌学术搜索
20. p . m . Ruiz j . a . Botia, a . Gomez-Skarmeta“通过machine-learning-driven自适应多媒体应用提供QoS,”IEEE系统,人,控制论B,34卷,不。3、1398 - 1411年,2004页。视图:出版商的网站|谷歌学术搜索
21. 诉Charvillat和r . Grigoras”,强化学习动态多媒体适应。”网络和计算机应用》杂志上,30卷,不。3、1034 - 1058年,2007页。视图:出版商的网站|谷歌学术搜索
22. r·s·萨顿和a·g·Barto强化学习:介绍美国剑桥,麻省理工学院出版社,质量,1998年。
23. m . Puterman马尔可夫决策过程:离散随机动态规划Wiley-Interscience,纽约,纽约,美国,1994年。
24. s p·辛格,t . Jaakkola和乔丹,“学而不状态估计在部分可观测马尔可夫决策过程,”学报》第11届国际会议上机器学习(ICML ' 94)新布伦瑞克,页284 - 292年,新泽西,美国,1994年7月。视图:谷歌学术搜索
25. a . r .卡桑德拉,l . p . Kaelbling和m·l·利特曼“最优行为在部分可观测的随机领域,”12国家会议上人工智能(AAAI 94),卷2,页1023 - 1028,西雅图,洗,美国,1994年7 - 8月。视图:谷歌学术搜索
26. t . Syeda-Mahmood”,学习和跟踪用户的浏览行为使用隐马尔科夫模型,”IBM方便会议的程序美国加州圣何塞,2001年6月。视图:谷歌学术搜索
27. r·o·杜达·e·哈特和d . g .鹳,模式分类Wiley-Interscience,纽约,纽约,美国,第二版,2000年版。

版权

版权©2008 Cezar Plesca等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。