基于增强学习的旅行计划推荐系统

标签: 程序设计 推荐系统 旅行计划 | 发表时间:2012-01-12 11:40 | 作者:标点符
出处:http://www.biaodianfu.com

1 概述

推荐系统是一种智能化电子商务应用,可以协助用户搜索信息,为用户提供个性化的产品推荐。旅游推荐系统的目的是支持旅行者在旅游前和旅游中面临的重要旅行规划决定。此类系统明确(通过问)或暗示(通过挖掘用户的在线活动日志)获取用户需求,并提供各种产品和服务,如前往目的地、兴趣点、事件或活动。近年来,研究者设计了很多旅游推荐系统,某些已经运行于主要的旅游门户网站。

传统推荐系统支持很简单的非交互检索流程:在旅行者交互的各个阶段,仅支持一种活动类型,例如,决定推荐给用户哪种产品。为了支持更真实的互动过程,人们提出了会话推荐系统。该系统支持对话,在每个阶段,系统能从可得的系统活动中选择一个行动。例如,推荐一些产品或向用户询问一些信息。系统选取的特别活动由推荐策略指定。例如,查询会话系统得到适合用户偏好的旅馆。可以采用以下2 种策略:

  1. 详细询问用户偏好,利用这些信息提取一个小的产品子集;
  2. 为用户推荐一系列产品,利用用户的反馈意见改进今后的建议。

这2 个会话策略最初应用于DieToRecs系统中,现在是Trip@dvice 技术的一部分。会话系统通常采用刚性策略,即在设计阶段已经确定而且在系统中使用严格编码。例如,Trip@dvice 允许用户选择这2 个策略中的任意一个,但必须严格遵照已选取策略中的步骤。该方法的主要局限在于,对于一个推荐任务可能有大量会话而不是刚性策略,如多种服务类型的旅游计划。此外,选取策略的过程基于直觉和系统设计者的先前经验,不一定适合用户。因此,设计者必须评估策略以发现最优策略,但考虑到必要开支、预算、精力、时间等,这不可行的。上述限制要求会话系统能自己确定最佳策略以协助用户。

文献提出一种新型基于会话的推荐系统来解决上述问题,而不是遵循硬性交互设计,提供了广泛的信息和决策支持功能,在交互过程中能改善最初的策略并采取最优策略。最优策略基本上可以最大化受益功能,用户能从每个交互步
骤中获益。笔者还基于人机模拟详细讨论了该方法的技术细节,并对评价结果进行描述。在评价中,当查询旅游服务(如旅馆)返回太多建议时,系统应当能决定是否向用户询问额外的服务特征以获取较小的服务集,或者让用户自动决定或手动更改查询。结果表明,推荐系统能改善最初的建议,严格地说,仅当结果集大于给定范围时才向用户询问以获取额外特征。但上述结果是在有限条件下得到的,即在一种情况下
系统必须做出决定,系统行为集只包含2 种行为。为了解决这些限制,本文提出一种基于会话推荐系统的自适应推荐系
统一般模型,将该模型用于旅行计划(Travel Planning, TP)工具中并描述了评价计划。

2 学习个性化的会话推荐互动策略

本文提出的推荐模型如图 1 所示,包含2 个实体,即信息系统IS 和推荐代理RA。信息系统是非自适应实体,功能完全由用户控制,可以提供简单的用户请求,如显示查询结果、热门搜索等。推荐代理是自适应实体,能自动协助用户,在交互过程的适当阶段为用户提供相关信息,这一协助过程基于系统的优化推荐策略。

在模型中,利用基于马尔可夫决策进程数学框架中的加固学习RL 技术学习最佳政策。马尔可夫决策过程是指决策者周期地或连续地观察具有马尔可夫性的随机动态系统,序贯地做出决策,即根据每个时刻观察到的状态,从可用的行动集合中选用一个行动做出决策。系统下一步(未来)的状态是随机的,且其状态转移概率具有马尔可夫性。决策者根据新观察到的状态,做新的决策,依此反复地进行。加固学习技术以此为基础,通过交互过程达到学习最优政策的目的。本文使用术语最优政策而不是最佳策略,策略只是政策规定如何根据系统行为选择规则实施策略。为通过RL 学习最优政策,认为RA 是决策制定代理必须实现的一个目标,即最优政策。通过与用户执行一些试错互动来实现,这些用户是代理环境的一部分。具体来说,在每个阶段,用户采取一些措施后,代理人指出当前形势或系统的状态(如图1 所示)。被观察的系统状态可能包括当前用户的状态信息(如目标和偏好)、正在进行的交互(如有多少产品用户已经浏览)、甚至代理自身的状态(如是否已经执行了一项推荐)。为学习最佳政策,这是代理必须具备的信息。

在一个或多个系统状态下,多系统行为可提供给代理执行(会话步骤)。例如,可能有这样的情形,系统不确定是提供旅馆建议更好还是其他选择更好。本文把这些状态标记为系统决策点(System Decision Point, SDP)。在系统决策点,代理尝试交互过程中不同的系统行为。对于每一个行为的执行,代理从环境中收到加强信号,通知它用户是否已接收先前行为。信号的大小由用户接收水平决定,例如,大的正信号(+10)可能标志最受欢迎的行为(如用户接收建议),大的副信号(-10)可能标志最不受欢迎的行为(如用户退出)。在交互进行中,代理利用收到的反馈避免不能接受的行为,并采取可以接受的行为。这在政策迭代算法中执行,最大化立即回报和下一个阶段预期贴现值的行为定义该阶段的新最优行为。为计算下一阶段的预期贴现值,使用交互过程中学习到的状态转换概率。RL 政策迭代过程确保这一进程将最终导致代理学习每个系统决策点的最佳行为,即学习最佳政策。在非系统决策点状态,只有一个单一的行动可以执行,本文认为这是最佳行动。

3 自适应旅游计划建议

本节将上述方法采用旅游计划工具合并自适应推荐方法,并将该方法应用于奥地利门户网站,为用户提供多种旅行推荐方案。旅游计划工具由Trip@dvice 技术支持。Trip@dvice 允许用户从目录中选择旅行组件(旅馆、景点、活动),将其绑定到一个新的计划中,或选择一个现有的旅行计划根据具体要求定制(删除或添加旅行组件)。如上所述,本文做法是基于学习一个或多个系统决策点的最佳行动,当用户在交互过程中通过系统浏览时,代理可能遇到这些系统决策点。用户导航流图基本模型如图2 所示。一个浏览状态代表用户交互中可能浏览的任意一个网页(如一个查询输入表单)。在每个浏览状态中,用户可以采取一个或多个用户行动导航到系统状态(如提交一个查询或返回到先前的交互状态)。

系统状态可能是 SDP 或非SDP 状态,因此,可用于选择下一个系统行为,其结果在下一个新的网页中呈现给用户。例如,假设在查询输入浏览状态,用户提交一个查询。为确保系统状态是SDP,此处系统必须决定如何继续会话以及下一个浏览状态需要呈现什么信息,如询问更多的偏好或执行查询。目前使用 Trip@dvice CBR 方法计算相关产品建议(如在相似过程中选择更高档次的产品)。提供2 种产品查询功能:

  1. 寻求启示,为用户循环提供建议产品清单直到用户选择一些产品;
  2. 查询搜索,用户限制逻辑查询产品目录以便搜索。

Trip@dvice 严格的会话政策决定了当前非自适应用户导航流图必须采用TP。流程图由单一的SDP 构成,该SDP 决定用户提交的产品查询以及系统得到的大量产品。Trip@dvice 的政策规定,当结果集大于某一阈值时系统建议给用户更多的功能。为了更好地学习最优政策,研究者提议增设3 个SDP纳入到非自适应流和更详细的系统设置。本文只展示导航流图的4 个SDP(见图3 和图4),而不是完整的自适应导航流图。

在图 3 中,用户通过欢迎页面输入系统。在此页面中,如果选择QrySrch 功能(用户行为SlctQrySrch),系统在SDP1输入,SDP1 应当决定是否在浏览状态ViewSrchOpts(系统行为ShowOpts)向用户显示不同的查找目录(目的地、事件等)或是在显示各种服务类别之前询问用户一些旅行特点(系统行为AskChars)。具体来说,用户在浏览状态SpecChars 输入自己的特点(用户行为EnterChars)。系统进入非SDP 系统状
态(黑色圆圈1),在此唯一可能的系统行为执行ShowOpts。此外,如果用户选择Seeklnsp 功能(用户行为Slct Seeklmp),则系统在SDP2 输入,SDP2 应当决定是否在浏览状态ViewProposals(系统行为ShowProps)向用户显示产品建议列表或在显示完整的旅行计划建议前询问用户一些旅行特点(系统行为AskChars)。一旦用户在SpecChars 输入自己的特点,系统便进入非SDP 状态(黑色圆圈2)。其中,唯一可能的系统行为是ShowProps。

如果用户限制条件并提交了具体的搜索查询(如旅馆),则系统进入SDP(见图4)。在浏览状态ViewTightFtrs(系统行为SuggTight),如果查询的结果集大小大于一定阈值,则系统应决定是否提出产品特性以减小结果集或执行查询并显示所有检索(系统行为Exec)。另外,如果查询结果集为空,即没有旅馆满足条件,系统也应决定是否建议用户在浏览状态ViewRelaxFtrs(系统行为SuggRelax)放宽一些条件或从查询(系统行为autoRelax)自动放宽一个条件(由系统而不是用户选择)以便产生一个结果集。在产品列表准备显示给用户的情形下,系统达到SDP4(见图4),必须决定如下页面之一:

  1. ShowRP1,显示页面ViewRP1,系统简单显示推荐产品列表;
  2. ShowRP2,显示页面ViewRP2,系统除了显示产品列表外还要求用户输入一些旅行特色;
  3. ShowRP3,显示页面ViewRP3,系统除了显示产品列表外还推动用户提出一些其他类型产品相关的搜索;
  4. ShowRP,显示页面ViewRP4,系统除了显示产品列表外还推动用户向他们的购物篮添加顶级产品,并提出其他产品类型的一些相关搜索。

在完整的自适应导航流图中,本文以20 个浏览状态和4 个系统决策点为示范,同时按照图形化的系统规范Petri 网来执行流程。模仿Petri 网中的术语,本文称浏览状态、用户行为、系统状态、系统行为分别为地点、输入、过渡、输出。这种表示对于通过图形挖掘工具(如ProM 框架)跟踪用户的导航流(评估过程中产生)以及获取不同信息(用户的一般导航模型、用户采取的独特导航路径、最常见的路径)非常有用。

4 系统设计与评价

根据图 1 所示推荐模型,系统架构包括2 个主要实体,即学习最佳政策功能的推荐代理和环境。环境表示用户和信息系统,包含API,允许推荐代理及其内部之外的对象进行交互以获取学习最优政策必须的数据,例如在某些互动阶段用户采取的行为、系统到达的状态等。系统架构如图5 所示。

在环境里,用户请求推荐系统以满足一个或多个导航/信息目标。这些请求传递给系统的对话管理器组件,对话管理器组件处理这些请求并根据系统的业务逻辑(从产品目录提取数据)和应用服务组件进行交互。状态管理器在每个用户请求后计算系统状态,在每个SDP 向推荐代理询问应用系统行为。此外,它通知推荐代理状态的改变,使代理可以在用户会话的每个阶段获取和存储(在日志数据组件)用户采取的行为、确保系统状态的相关信息、在此状态执行的系统行为、由对话管理器生成的结果浏览状态(页面)。在推荐代理中,决策管理器是在SDP 要求执行的系统行为的信息系统界面。它与用于存储当前代理政策的政策管理器组件交互。此外,决策管理器还记录每个阶段的所有相关数据(日志管理器),此类数据被学习管理器再利用以学习最优政策。

上述旅行推荐创新办法需要一个新的具体评价方法。本文基于旅行推荐系统的2 个替代变量设计了一种方法:非自适应和自适应版本。第1 个变量基本遵循缺省的交互政策集,为用户提供设计好的严格编码逻辑建议。第2 个变量遵循学习过程的结果交互政策。本文基于一系列可靠措施对这些变量的性能进行假设测试,假设基于用户的搜索和产品选择行为以及对系统行为的满意度。评价中必须选择一组参与者(满足特定要求),他们将随机分配到2 组实验,每组要求评价推荐系统中的变量。评价分2 个阶段进行。在训练阶段,首先进行的是第1 组实验,推荐变量采用替代的手工政策集。此变量构成基准系统。在此阶段,日志管理器记录所有相关序列数据的日志(用户行为、系统状态信息、系统行为、浏览状态),然后被学习管理器组件利用,以学习TP 自适应流图的最优政策。在测试阶段、训练阶段之后执行第2 组实验,评估所采用的最优政策的推荐变量。

在每个阶段,要求参与者在蒂罗尔、奥地利地区规划度假的一般范围内执行一些任务。必须记录一系列操作步骤,在交互过程中(通过日志数据组件)一些会被自动记录,另一些则要求用户在交互后填写一张调查问卷。评价的目的是通过确定这些措施从训练阶段到测试阶段的改善来测验本文假设。主要测量由推荐代理获得的总回报(使用一种特殊政策)和系统的成功率,从而在系统评价中发现更有助于找到最优政策的状态变量。根据模拟实验,学习政策依赖用户和会话
模型,即最佳交互政策受用户知识的影响,在人-机交互中获取,并由推荐代理使用。

5 结束语

本文对旅行和旅游业应用推荐系统的概念设计提出了一些意见。提出的模型已由一系列离线实验验证,但还需要进一步分析。本文方法需要模拟应包含在系统状态表示的用户相关信息(人口统计、用户目标等)。信息可显性(询问用户)或隐性(从交互日志中)获取。隐性获取方法是强制性的,因为用户通常对系统问题都不作答复。但考虑到在线用户行为通常是不可预测的或错误的,这些隐性信息的质量可能是可疑的。因此,需要可靠的研究方法确定哪些信息在系统状态是相关的。这将扩大基于模拟提出的结果。此外,需要更好的方法来评价由推荐代理分配给新状态的数值回报价值,这是用户响应的结果。这些值应该尽可能接近用户的满意度,而这一般通过观察用户活动来推断。尽管存在诸多困难,离线评价的结果证明,使用本文提出的模型和方法可以改善系统性能,有利于加快会话旅行推荐系统的开发。

本文作者:刘小燕,陈艳丽,贾宗璞,沈记全 (河南理工大学计算机科学与技术学院,河南焦作 454003)

Related posts:

  1. 提升网站转化率的六种方法
  2. 新浪微博客试用体会
  3. 手机客户端开发定位


相关 [增强学习 旅行 计划] 推荐:

基于增强学习的旅行计划推荐系统

- - 标点符
推荐系统是一种智能化电子商务应用,可以协助用户搜索信息,为用户提供个性化的产品推荐. 旅游推荐系统的目的是支持旅行者在旅游前和旅游中面临的重要旅行规划决定. 此类系统明确(通过问)或暗示(通过挖掘用户的在线活动日志)获取用户需求,并提供各种产品和服务,如前往目的地、兴趣点、事件或活动. 近年来,研究者设计了很多旅游推荐系统,某些已经运行于主要的旅游门户网站.

旅行的计划与记录

- 高春辉 - 坏脾气的小肥
今年春节,我去柬埔寨旅行,杭州→暹粒→西哈努克市→金边→杭州,是11天还是13天来着. 旅行回来,开始动心思设计一款针对“长途旅行”的产品,主题是“旅行的计划与记录”,以APP为主,网站为辅. 简单来说,它能帮助我做一份更好的旅行计划,以及在旅途中轻松记录一路见闻. 你看,时隔半年,我连去柬埔寨玩了多少天,甚至去过哪些景点都记不清了.

即将从创新工场助跑计划毕业,“途客圈”希望帮你更快捷的制定旅行计划

- Stan - 36氪
曾经在今年5月份36氪开放日做过展示,后来进入创新工场助跑计划的途客圈项目终于浮出水面了. 途客圈是一个可以帮助用户制定旅行计划,并针对旅行目的地、计划进行点评讨论的平台. 如果你打算去一个城市,你可以在途客圈(tukeq.com)找到这个城市的所有景点,将感兴趣的加入自己的行囊中. 然后,在制定计划的时候,你所需要做的就是把这些景点合理的规划到每一天中.

旅行之道

- tongxin - 译言-每日精品译文推荐
  |善行无辙迹,善言无瑕谪——老子. I’m not the world’s most seasoned traveler, but I have made a number of trips lately and have learned a few things that work well..

oracle执行计划

- - Oracle - 数据库 - ITeye博客
所谓执行计划,顾名思义,就是对一个查询任务,做出一份怎样去完成任务的详细方案. 举个生活中的例子,我从珠海要去英国,我可以选择先去香港然后转机,也 可以先去北京转机,或者去广州也可以. 但是到底怎样去英国划算,也就是我的费用最少,这是一件值得考究的事情. 同样对于查询而言,我们提交的SQL仅仅是 描述出了我们的目的地是英国,但至于怎么去,通常我们的SQL中是没有给出提示信息的,是由数据库来决定的.

旅行中的他们

- realrocking - 酷啡生活 {Cooffee Life}
旅行的一个好处是可以多认识一些人,听听别人的生活,反省或回顾自己的生活,旅行中遇到的朋友们都是生活的老师. 浙江姐姐,在喜洲认识的,因为她没带伞,我邀她一起打伞,然后我们一起买喜洲粑粑吃,一起坐车到大理古城. 因为严家大院收门票,她没有进去看,白去了一趟. 回城的一路上她一直抱怨今天来喜洲让她白白浪费了14元车费.

旅行箱的玄机

- houy25 - 创意酷
  你有多少次面对带大箱子还是小箱子而纠结呢. 每当假期、出差、旅行,我们都需要整理行李,东西多的时候希望箱子大一点,东西少的时候又希望箱子小一点便携一点. 这个由Steffen Molgaard Larsen 设计的旅行箱,或许可以让你舒展眉头. 这个箱子可以变身哦,可以通过推拉改变箱子容量大小,两种模式,可满足你长期或者短途的出行需要,作者把它称为箱中箱.

旅行推销员 2.0

- Shan - 科学松鼠会

旅行箱变猫窝

- apple - 玩意儿
这是作者 AtomicAttic 将老旧的旅行箱,再次利用,在四角加上一个个小木块,就变成了一个猫窝,看起来貌似还是不错的,后面还有古老的电视机挖空后所变得窝窝,如果有兴趣的倒可以拆了那种大头显示器. 本文原始链接:http://www.cngadget.cn/atomic-attic.html. m square 创意旅行化妆包/洗漱包.

豪华舒适旅行椅

- jacky - 创意酷
该文来源于创意酷,这里还有能买到的创意点此购买.