【文献阅读】【2018 IEEE/WIC/ACM (WI)】 Boosting Reinforcement Learning in Competitive Influence Maximization with Transfer Learning

回到主页

1. 问题背景 企业的目标是在竞争中推销自己的产品，并试图获得比其他企业更多的利润。 2. 主要任务 使用迁移学习方法在较小的传播网络上训练传播模型（传播策略），然后迁移到较大的网络中使用。要求在源网络上训练的模型迁移到更大的社交网络中使用时传播效果更好或相似，进而节省时间。 3. 模型与方法

  • 竞争线性阈值模型（TV-CLT）加入了时间因素
  • 强化学习用于寻找最优策略
  • 迁移学习用于迁移网络模型

4. 实验结论 文章基于竞争线性阈值模型（TV-CLT）使用迁移学习和强化学习方法解决了竞争影响力最大化问题（TC-CIM）。

一、背景知识

1. 影响力最大化（Influence Maximization） 竞争影响最大化（CIM）同样是影响力最大化（IM）问题，目的同样是扩大影响力。影响力最大化相关介绍请参考:【大数据网络传播模型和算法-陈卫】——影响力最大化.

2. 竞争影响最大化（Competitive Influence Maximization） 竞争影响最大化（CIM）问题考虑提供相同或相似产品的多方在社交网络中争夺买家或用户。即用户在生活中会受到两种或多种传播影响。以市场营销为例，企业需要使用某种策略（强化学习寻找下一轮最优解）来投放自己的产品（种子节点），使得在别的公司的影响到来之前影响该用户（节点），从而达到利润最大化（影响力最大）。
3. 线性阈值模型（Linear Threshold Model） alt text 详细介绍参考：【大数据网络传播模型和算法-陈卫】——影响力最大化. 4. 迁移学习（Transfer Learning） 强化学习中迁移学习的目的是利用在源任务中获得的知识来更快地学习目标任务。

二、相关工作

1. 时变竞争线性阈值模型（TV-CLT） 文章在线性阈值模型（LT）的基础上定义了一种新的传播模型——时变竞争线性阈值模型（TV-CLT）。与LT相比，TV-CLT增加了信息在扩散过程中的时间影响因素，用来反映网络传播的动态性。增加了时间衰减函数和时间传播延迟函数。 具体定义如下图所示： alt text 具体传播过程为：TV-CLT模型的扩散过程与传统LT模型相同。在扩散开始时，每个顶点有一个激活阈值。节点v在时间步长被方激活，当，其中 为节点u在时间步长t之前到节点v的随时间衰减的影响边权重和时延传播，Op t为p方在时间步长t之前激活的节点集合。我们使用渐进扩散过程，也就是说，一旦一个节点v被p方激活，它将一直被p方激活，直到扩散过程结束。如果节点v可以同时被多于一方激活，那么它就会被对节点v总影响力最大的一方激活,。每一方都可以选择实施一定的策略，以提高自己在目标网络中的影响力。策略描述了一方如何在每一轮中分配预算来选择种子节点。具体来说，策略可以描述为网络状态、回合和剩余预算的函数。根据输入，该策略描述了该方在这一轮中将选择哪些种子节点。当1)没有剩余的预算，或2)达到政党的最后期限时，政党将停止选择节点。一方的总影响力将在其截止日期到达时计算。 2. 时间约束竞争影响最大化（TC-CIM） TC-CIM问题的NP-Hard通过将其简化为一方时间约束影响最大化。使用强化学习推导最优解是不切实际的，于是文章将迁移学习的方法集成到TC-CIM问题中的强化学习中。 强化学习的目标是学习一个最优策略，以决定特定状态下采取什么行动。

三、模型建立与迁移过程

1. 建立模型： 建立学习的种子组合和种子选择（SCSS）框架来解决时间约束竞争影响最大化问题，作为迁移的基础。使用TV-CLT扩散模型传播当前活动节点的影响。并讨论了SCSS框架的环境、奖励、行动和状态等相关变量。

  • 传播环境： 使用TV-CLT传播模型作为实验的传播环境。
  • 奖励设置： 给模型设置一个最大化预期积累奖励，使用状态的期望累积奖励函数和给定状态-动作对的期望累积奖励，来确定策略π对于最大化累积奖励的效果有多好。
  • 种子策略： 文章考虑了四种影响力最大化的行动策略，即每一轮种子节点的选择方法，基于贪心算法分别是（Degree、Weight、Blocking、SubGreedy）四种行动（种子选择）策略。一直迭代，直到种子节点分配完毕。
  • 状态特征规范化： 使用相同的一组特征来表示网络状态，使源社会网络和目标社会网络具有相似的状态表示，以便轻松地将在源社会网络上学习到的q -解转换为目标社会网络。

2. 迁移学习：

  • 迁移方法（Starting-Point Methods） 使用Starting-Point Methods(起点转移)方法将源社交网络中多方的最终解转移过来，作为目标社交网络各方的起点初始解。首先将源社会网络的最终解进行迁移，并在目标社会网络的训练过程中将其作为初始解提供给。其次，在目标社交网络上利用源策略，让它从一个更好的解决方案开始，而不是随机解决方案（零），并利用在源社会网络上学习到的最优行为来达到目标社会网络的某个状态。

3. 模型训练：

  • 训练过程：
  • 定义源社交网络、目标社交网络以及源和目标社交网络上的训练设置 源社交网络：从头开始训练NSQ模型并保存学习到的模型，即源q表，以便使用它来转移知识。 目标社交网络：通过初始化目标q表作为源网络的最终q表，然后训练模型来训练NSQ-TL模型。 目标训练设置：通过设置源网络的最终q表，初始化目标网络中的组合和选择q表。 训练流程如下图所示： alt text
  • 数据集选取 选取小型 alt text
  • 模型训练 针对竞争对手的已知策略对NSQ- b、NSQ（FB）、NSQ（CEL）五个模型进行了训练，每个模型运行1500个训练集。然后，我们选择平均奖励最高的最好的一个，进行1000个测试集的比赛。 在竞争阶段，各算法不经探索，根据已有的组合和选择q表，使用贪心算法确定组合和选择策略。同样，在源网络上训练了5个NSQ-TL（FB）和NSQ-TL（CEL）模型，每个模型运行1500个训练集。然后选择具有最高平均奖励的最佳模型，在目标网络上使用额外的800个训练集进行进一步的再训练。在进行竞争之前，根据竞争对手的已知策略在目标网络上重新训练了三个模型。然后选择平均奖励最高的最好的一个进行竞争。
  • 参数设置： greedy probability = 0.5 decay factor = 0.998 discount factor = 0.98

四、实验结果

alt text alt text 实验结果表明，当迁移模型在更大的源网络上进行训练，然后再迁移到目标网络上时，迁移模型可以达到与基线模型（从头开始训练）更好或相近的性能。当考虑到时间效率时，我们应该选择一个较小的源网络，以便快速训练模型并在目标网络上重新训练。这将显著减少训练时间，并获得与基线模型相似的结果。此外，源网络上的模型，无论是小网络还是大网络，都只训练一次，可以应用于许多目标网络进行竞争和重新训练，而不需要从头开始训练模型。

五、总结

本文提出了一种基于TV-CLT模型的迁移学习强化学习方法来解决TC-CIM问题。具体来说，我们将源网络和目标网络的状态表示归一化，以便有效地利用源网络上获得的知识。进一步，我们在RL域扩展了TL的起点方法，提出了NSQ-TL算法来解决源目标网络和代理设置之间的异构性。

本文章使用limfx的vscode插件快速发布