魚和熊掌如何兼得？基於強化學習的多尺度信息傳播預測

「論文訪談間」是由 PaperWeekly 和中國中文信息學會社會媒體處理專委會（SMP）聯合發起的論文報道欄目，旨在讓國內優質論文得到更多關注和認可。

信息傳播預測，也稱爲級聯預測，主要研究信息如何在用戶之間進行傳播，已經在很多實際場景中得到了應用，例如產品推廣，流行病學以及新聞和觀點的傳播。

近期傳播預測的工作利用深度學習技術的優勢，將信息傳播過程建模爲基於循環神經網絡（RNN）的序列模型，並取得了很好的成果。

但是現有工作要麼專注於預測下一個受影響的用戶的微觀尺度傳播預測，要麼致力於估算傳播過程中受影響用戶的總數的宏觀尺度傳播預測，沒能將微觀和宏觀尺度的預測模型統一起來。

▲ 圖1. 宏觀尺度的傳播預測（左）和微觀尺度的傳播預測（右）

針對已有研究的侷限性，楊成等人提出了一種基於強化學習（RL）的多尺度信息傳播預測模型同時進行微觀尺度與宏觀尺度的預測。具體地，論文通過使用強化學習框架將宏觀尺度的監督信號引入微觀級聯模型，並採用了快速有效的結構上下文提取方法來利用社交網絡結構信息。

他們的研究成果 Multi-scale Information Diffusion Prediction with Reinforced Recurrent Networks 發表在 2019 年的 IJCAI 會議上。爲了方便大家瞭解該領域的工作，作者也 整理了一份近年來信息傳播預測任務的相關論文列表：

https://github.com/albertyang33/DiffusionPapers

論文標題： Multi-scale Information Diffusion Prediction with Reinforced Recurrent Networks

論文來源： IJCAI 2019

論文鏈接： https://www.ijcai.org/Proceedings/2019/560

代碼鏈接： https://github.com/albertyang33/FOREST

問題介紹

論文中使用的數據集有 Twitter、Douban 以及 Memetracker。以 Twitter 數據集爲例，Twitter 數據集記錄了 2010 年 10 月包含有 URL 的推特，其中每個 URL 都是在用戶之間傳播的信息項。

論文按照時間順序對轉發某個 URL 的用戶進行排序，作爲該 URL 的級聯。數據集除包含有這些級聯外還包含有這些用戶的社交網絡圖信息。論文數據集的統計信息如下表所示：

▲ 表1. 數據集統計

下面給出微觀與宏觀尺度預測的形式化定義：

給定用戶集合 V 和級聯集合 C，每個級聯是按受影響時間排序的用戶序列，其中是級聯的規模，即對應傳播對象影響的用戶總數。此外，當信息傳播發生在社交網絡服務上時，社交網絡結構 G=(V,E) 也可以作爲傳播預測的額外輸入。

微觀尺度的傳播預測旨在給定級聯中已經被影響的用戶的條件下，預測下一個被影響用戶，其中。

宏觀尺度的傳播預測旨在給定前 k 個被影響用戶的條件下，預測級聯的最終規模。

模型框架

2.1 微觀傳播建模

這部分採用帶門循環單元 GRU 作爲微觀尺度建模基礎。給定級聯序列，GRU 在每一步中，將用戶作爲輸入並計算隱狀態。通過採用 GRU 將級聯中所有已經被影響的用戶的歷史信息編碼到隱狀態中。

如圖2所示，除使用 GRU 編碼歷史信息之外，論文采用基於圖神經網絡的結構上下文提取方法提取用戶的社交網絡結構作爲額外的用戶特徵表示。

▲ 圖2. 結構上下文提取算法

直覺上講，所有最近受影響的用戶都可能影響下一個用戶的預測。論文定義最近受影響的用戶爲最近 m 個用戶，其中 m 是控制這個窗口大小的超參數。然後使用平均池化來聚合用戶的結構上下文特徵爲，並將其與 GRU 隱狀態表示拼接，預測下一個受影響用戶的概率如下：

微觀傳播預測的訓練目標爲最大化所有級聯的對數似然：

2.2 宏觀傳播建模

宏觀傳播建模的關鍵在於如何賦予微觀級聯模型預測宏觀級聯規模的能力，整個流程如下圖所示：

▲ 圖3. 宏觀尺度信息傳播預測框架

爲了在步驟 (b) 中使得微觀級聯模型能夠進行級聯規模預測，首先在每個級聯序列數據末尾添加虛擬用戶 < STOP > 並讓模型也將其看作普通用戶進行預測。

給定前 K 個受影響用戶，爲了估算整個級聯的規模，模型遞歸地根據預測的概率分佈採樣一個用戶，將其作爲下一步的輸入並繼續預測。一旦採樣到 < STOP > 信號，認爲該級聯的傳播停止並統計已經被預測的用戶數作爲級聯的最終規模。

論文采用 Mean Square Log-transformed Error (MSLE) 作爲級聯規模預測的評價標準。雖然修改後的微觀級聯模型能夠通過模擬預測級聯的規模，但是模型缺乏監督信號來引導模型更新獲得更好的效果。

因爲計算級聯規模時的採樣操作是不可導的，模型無法後向傳播更新參數。爲了解決這個問題，模型將模擬過程放入強化學習的框架中並使用 policy gradient 算法更新參數。

GRU 及其隱狀態（包括結構上下文）對應強化學習中的 agent 和 state 概念。每一步的 action 是選取下個受影響用戶。當 <STOP> 這個特殊的 action 被選中時，將 MSLE 的相反數作爲 reward。模型目標是最大化級聯的 reward 的期望:

其中 Pr 是選取action序列 seq 的概率，可以被分解爲每個 action 的概率的乘積，模型採用 REINFORCE 算法來計算的梯度，最後，參數通過最大化 reward 的期望的梯度上升來更新。

模型實驗效果

他們將模型命名爲 reinFOrced REcurrent networks with STructural context (FOREST) 。 FOREST 在微觀傳播預測任務上一致地超過所有基線方法，並在 HITS 和 MAP 指標上取得了超過 10% 的相對提升。

FOREST 在宏觀傳播預測任務上一致地超過包含最先進的級聯規模預測算法 DeepCas 在內的所有基線方法，並在 MSLE 評價指標上取得了 12% 的相對提升。

論文總結

論文提出了一種新穎的多尺度傳播預測模型 FOREST ，能夠同時進行微觀和宏觀尺度的傳播預測。統一模型在實現微觀與宏觀尺度聯合預測的同時，能夠利用訓練數據中的更多信息，本質上是一種多任務學習的解決方案。

模型通過強化學習框架賦予了微觀傳播模型預測宏觀性質（即級聯規模）的能力，相比於將級聯規模預測視爲迴歸問題的現有宏觀預測工作，可以額外利用具體受影響的用戶序列及其受影響順序的信息。

此外，論文考慮到當信息通過社交網絡服務進行傳播時，可以進一步利用社交網絡的結構信息幫助預測，因爲信息很可能是通過用戶間的社交鏈接傳播的。

文中提出了一種結構上下文提取方法來提取用戶的社交網絡結構信息輔助信息傳播預測。下個受影響用戶預測和級聯規模預測任務上的實驗結果證明了方法的有效性。

關於作者

楊成，北京郵電大學計算機系助理教授。 於2014年、2019年獲得清華大學學士、博士學位，清華大學計算機科學與技術系優秀博士畢業生。主要研究方向包括圖數據挖掘與自然語言處理。在國際頂級學術期刊及會議上發表論文十餘篇，Google Scholar 引用超1000次，並擔任 ACL、EMNLP、AAAI、IEEE TKDE 等國際會議期刊程序委員會委員和審稿人。

唐建，加拿大蒙特利爾高等商學院&蒙特利爾學習算法研究所（MILA）助理教授。 2014年獲北京大學博士學位。曾在密歇根大學和卡內基梅隆大學任博士後和訪問學者。主要研究深度圖表示學習及其應用。曾獲 ICML’14 最佳論文、WWW’16 最佳論文提名。

孫茂松，博士，清華大學計算機科學與技術系教授，博士生導師，清華大學人工智能研究院常務副院長。 2007-2018年任計算機科學與技術系主任、黨委書記。主要研究領域爲自然語言處理、互聯網智能、機器學習、社會計算和計算教育學。國家重點基礎研究發展計劃（973計劃）項目首席科學家，國家社會科學基金重大項目首席專家。在重要國際刊物、國際會議、國內核心刊物上發表論文200餘篇，Google Scholar 論文引用數1萬餘次。

崔淦渠，清華大學計算機科學與技術專業碩士研究生。 2019年獲清華大學學士學位。研究方向爲網絡表示學習和圖神經網絡。

劉知遠，清華大學計算機系副教授、博士生導師。 主要研究方向爲表示學習、知識圖譜和社會計算。2011年獲得清華大學博士學位，已在人工智能領域的著名國際期刊和會議發表相關論文80餘篇，Google Scholar統計引用超過7000次。曾獲清華大學優秀博士學位論文、中國人工智能學會優秀博士學位論文、清華大學優秀博士後、中文信息學會青年創新獎，入選中國科協青年人才託舉工程、中國計算機學會青年學者提升計劃，擔任 ACL、EMNLP、COLING、IJCNLP 領域主席。