ACL2017 | 香港中文大學：基於傳播結構核學習的微博謠言檢測

04-22

你和「懂AI」之間，只差了一篇論文

很多讀者給芯君後台留言，說看多了相對簡單的AI科普和AI方法論，想看點有深度、有厚度、有眼界……以及重口味的專業論文。

為此，在多位AI領域的專家學者的幫助下，我們解讀翻譯了一組頂會論文。每一篇論文翻譯校對完成，芯君和編輯部的老師們都會一起笑到崩潰，當然有的論文我們看得抱頭痛哭。

同學們現在看不看得懂沒關係，但芯君敢保證，你終有一天會因此愛上一個AI的新世界。

讀芯術讀者論文交流群，請加小編微信號：zhizhizhuji。等你。

這是讀芯術解讀的第21篇論文

ACL 2017 Long Papers

基於傳播結構核學習的微博謠言檢測

Detect Rumors in Microblog Posts Using Propagation Structure via Kernel Learning

香港中文大學

The Chinese University of Hong Kong

【摘要】虛假的消息如何通過社交媒體進行病毒傳播？它的傳播模式與真實消息的有何不同？在本文中，我們嘗試基於其傳播結構來解決從微博帖子中識別謠言即虛假信息的問題。我們首先利用傳播樹對微博帖子擴散過程進行建模，為原始消息隨時間推移的傳播和發展趨勢提供有價值的線索。然後，我們提出了一種稱為傳播樹核（Propagation Tree Kernel）的基於內核的方法，它通過評估傳播樹結構之間的相似性來捕獲區分不同類型謠言的高階模式。兩個實際數據集的實驗結果表明，本文提出的基於內核的方法可以比最先進的謠言檢測模型更快速、準確地檢測謠言。

1 引言

在2016年11月9日，Eric Tucker是一名基層用戶，他在Twitter上只有大約40個粉絲，他發布了自己未經證實的觀點，認為參與德克薩斯州奧斯汀的反特朗普遊行中的抗議者是事先給錢僱傭的。後來此條推文被證明是虛假的，但在幾天內這條推文在Twitter上分享了16000多次，在Facebook上分享了35萬次，推動了全國的陰謀論。故事的傳播圖如圖1所示，它給出了故事沿著時間線的關鍵傳播點。我們可以看到，在最初的帖子之後，一些有影響力的在線社區和用戶（包括特朗普自己）分享或推廣了這個推文，導致其廣泛傳播。

圖1 關於「僱傭抗議者到達德克薩斯州奧斯汀進行反特朗普遊行」的傳言如何傳播變成病毒，「*」表示影響的程度。

圖2 兩個源tweets的傳播片段。節點大小：表示發布帖子的用戶的熱門程度（由粉絲數量表示）；紅色、黑色、藍色節點：用戶內容分別表示懷疑/拒絕，支持、中立的推文；實體（虛線）邊緣：從更多（較少）人氣用戶到較少（更多）人氣用戶的信息流；虛線同心圓：時間戳。

廣泛接受的謠言定義是「傳播中未經驗證的和極其有用的相關信息表達」（DiFonzo和Bordia，2007）。這種未經驗證的信息可能最終證明是真實的，或部分或完全是錯誤的。在當今世界不斷變化的世界，謠言可能會因為社會化媒體平台的產生以閃電般的速度迅速增長，謠言內容不僅僅是錯誤的，但是會對公共社會造成誤導和危害。因此，及時跟蹤和揭露這些謠言至關重要。

新聞記者和事實檢查網站，如http://snopes.com已經努力跟蹤和檢測謠言。然而，這樣的努力是人工的，因此覆蓋範圍有限且速度低。基於特徵的方法（Castillo et al., 2011; Yang et al., 2012; Ma et al., 2015）通過使用從消息內容、用戶簡介和擴散模式的整體統計（例如，轉發次數，傳播時間等）來提取特徵，並獲得了一定的成果。但是，這種做法過於簡單，因為它們忽視了謠言傳播的動態。考慮傳播特徵的現有研究主要集中在時間特徵上（Kwon et al., 2013，2017），而不是傳播結構。

那麼傳播結構可以區分謠言和非謠言嗎？最近的研究表明，謠言傳播者是想獲得關注和人氣的人（Sunstein，2014）。然而，在Twitter上更多關注的人氣用戶（例如，更多粉絲）實際上不太可能傳播謠言，因為高粉絲量可能阻礙用戶參與宣傳未經驗證的信息（Kwon等，2017）。直觀地說，對於「成功」的謠言與流行的真實消息一樣廣泛傳播，初始傳播者（通常不受歡迎）必須吸引一定數量的傳播源，例如，人氣用戶的關注或有很多成員的社區參與促進傳播。我們將其稱為約束模式傳播，相對於每個人都可以共享的普通消息的開放模式傳播。這種不同的傳播模式可能意味著謠言與非謠言之間，甚至不同類型的謠言之間的一些明顯的傳播結構。

由於信息擴散的複雜性，基於傳播結構明確定義判別式特徵是困難和有誤差的。圖2舉例說明了由兩個顯示為根節點（綠色）的用戶發起的兩個Twitter帖子（謠言和非謠言）的傳播結構。這裡的信息流量說明了這個謠傳的推文首先由低影響力的用戶發布，然後一些人氣用戶加入來促進傳播，但是非謠言的推文最初是由人氣用戶發布的，並被許多普通用戶直接傳播；基於內容的信號，如各種用戶的立場（Zhao et al., 2015）和基於邊緣的信號，如相對影響（Kwon等，2017）也可以表明源Twitter的不同性質。消息傳播中的許多這樣的隱含區別很難用以前工作使用的統計匯總手段進行模擬。另外，與純文本的表現學習不同，一般來說，網路結構表示學習還不夠成熟。因此，傳統和最新的基於文本的模型（Castillo et al., 2011; Ma et al., 2015，2016）不能輕易應用於這種複雜的動態結構。

為了捕獲謠言檢測的高階傳播模式，我們首先用傳播樹來表示每個源推特的傳播，該傳播樹是通過捕獲由源推特觸發的用戶間的互動而產生的。然後，我們提出一種稱為傳播樹核Propagation Tree Kernel（PTK）的基於內核的數據驅動方法來自動生成相關特徵（即子樹），以估計兩個傳播樹之間的相似度。與傳統基於解析樹建模句法結構的樹核（Moschitti，2006; Zhang et al., 2008）不同，我們的傳播樹由對應於博文的節點組成，每個表示為連續向量，邊表示傳播方向，並為每個帖子提供上下文。其基本思想是找到並捕獲傳播樹中指示謠言的突出子結構。我們還將PTK擴展到一個上下文豐富的PTK（cPTK），以通過考慮來自源推特到子樹根的不同傳播路徑來增強模型，從而捕獲傳播上下文。兩個真實Twitter數據集的廣泛實驗表明，所提出的方法大幅優於最先進的謠言檢測模型。

此外，大多數現有方法將謠言檢測視為二分類問題，將候選假設作為謠言預測。由於謠言一開始經常是未經驗證的，後來證明是真實的或虛假的，或者仍然未被證實（Zubiaga et al., 2016），這裡我們考慮一套更實用、更細粒度的類：虛假的謠言、真實的謠言、未經證實的謠言和非謠言，這成為一個更具挑戰性的問題。

2 相關工作

跟蹤錯誤信息或揭露謠言一直是多門學科的熱門研究課題（DiFonzo和Bordia，2007; Morris et al., 2012; Rosnow，1991）。Castillo et al. (2011)利用廣泛的手動收集特徵研究了Twitter上的信息可信度。其次，在許多研究中提出了與消息內容、用戶簡介和傳播模式統計相對應的各種特徵（Yang et al., 2012; Wu et al., 2015; Sun et al., 2013; Liu et al., 2015 ）。Zhao et al. (2015) 專註於早期謠言檢測，通過使用正則表達式尋找質疑和否認的推文，並將其作為揭開謠言的關鍵。所有這些方法都過於簡單化，因為它們忽視了社交媒體數據豐富結構的動態傳播模式。

一些研究集中在發現並理解謠言擴散的時間模式。Kown等人（2013; 2017）引入了基於推文時間屬性的時間序列擬合模型。Ma et al.,（2015）使用時間序列擴展了模型，以捕捉隨時間變化的特徵。Friggeri等人（2014）和Hannak等人（2014）通過分析謠言揭露網站鏈接的評論，研究了錯誤信息級聯的結構。最近，Ma et al.,（2016）使用遞歸神經網路來學習來自不同時間推文文本的謠言信號表示。我們的工作將在基於傳播樹核的統一框架中考慮時間、結構和語言信號。

大多數以前的工作將其定義為事件級別的分類，其中事件由許多源Twitter提供，每個都與一組轉發和回復相關聯。在這裡，我們專註於對關於索引的給定的源推文進行分類，這是一個更細粒度的任務。（Wu et al., 2015; Qazvinian et al., 2011）也考慮了類似的情況。

核方法被設計來評估兩個對象之間的相似性，而樹核是特別針對於結構化數據的，並已經成功應用於許多自然語言任務中，如句法分析（Collins和Duffy，2001）、問答（Moschitti，2006）、語義分析（Moschitti，2004）、關係提取（Zhang et al., 2008）和機器翻譯（Sun et al., 2010）。這些內核不適合於對社交媒體傳播結構進行建模，因為節點不是作為離散值給出，如詞性標籤，而是表示為高維實數向量。我們提出的方法是用於建模這種結構的樹核的實質性擴展。

3 推文傳播表示

在微博平台上，粉絲/朋友關係在用戶之間嵌入了共同的興趣。一旦用戶發布了一個推文，他的所有粉絲將收到推文。此外，Twitter允許用戶轉發或評論另一個用戶的帖子，以便信息可以超出原始創建者的網路。

我們將每個源tweet的傳播建模為樹結構T(r)= <V,E>，其中r是源tweet以及樹的根，V指的是一組節點，每個節點表示在某一時間對源推文 r 的一個回應帖子（即轉發或回復），進而發起循環；E是對應於V中的節點之間的響應關係的一組有向邊。如果存在從vi到vj的有向邊，則意味著vj是對vi的直接響應。

更具體地，每個節點vV被表示為元組v =（uv, cv, tv），其提供以下信息：uv是帖子的創建者，cv表示帖子的文本內容，並且tv是源tweet r和v之間的滯後時間。在我們的例子中，uv包含用戶的屬性，例如粉絲/朋友的數量、驗證狀態、歷史帖子數等，cv是基於一元文法和二元文法來表示該帖子的內容。

4 傳播樹核建模

在本節中，我們描述了基於傳播樹核方法的謠言檢測模型，稱為傳播樹核Propagation Tree Kernel (PTK)，我們的任務是給定一個源tweet r的傳播樹T(r)，以預測r的標籤。

4.1 樹核背景

在介紹我們提出的演算法之前，我們簡要介紹一下我們的PTK模型所基於的傳統樹核(tree kernel)。

樹核旨在通過隱含計算相應解析樹之間常見子樹的數量來計算兩個自然語言句子之間的句法和語義相似度。給定一個句法解析樹，其孩子的每個節點都與語法生成規則相關聯。圖3說明了「cut a tree」及其子樹的句法分析樹。子樹被定義為具有多於一個節點的任何子圖，限制是必須包括整個（非部分）規則生成。例如，片段[NP [D a]]被排除，因為它只包含生成NP->DN的一部分！（Collins and Duffy，2001）。

圖3 句法分析樹和子樹

在Collins和Duffy（2001）之後，給出了兩個解析樹T1和T2，核函數K（T1，T2）被定義為：

其中V1和V2分別是T1和T2中所有節點的集合，並且每個節點與生成規則相關聯，並且

評估以vi和vj為根的公共子樹。

可以使用以下遞歸過程計算（Collins和Duffy，2001）：

1）如果vi和vj的生成規則不同，則

= 0;

2）否則，如果vi和vj的生成規則相同，並且vi和vj只有葉子（即它們是前端符號），則

；

3）否則

。

其中nc(v)是節點v的子節點數，ch（v,k）是節點v的第k個子節點，l（0 <l￡1）是一個衰減因子。l = 1產生公共子樹的數量；l<1減少較大子樹的貢獻，使核值相對於子樹大小變化較小。

4.2 PTK模型

為了對傳播樹進行分類，我們可以計算出樹之間的相似性，這些樹根據結構、語言和時間屬性來反映不同類型的謠言和非謠言的區別。然而，現有的樹核不能簡單地應用於傳播樹，因為1）與分析樹不同，其中節點由可枚舉的標稱值（例如，詞性標籤）表示，傳播樹節點被給定為連續數字的向量表示，表示節點的基本屬性；2）兩個解析樹的相似度是基於共同子樹的數量，通過檢查相同的生成規則和相同子項是否與兩個子樹中的節點相關聯來評估子樹的共性，而在我們的上下文相似度應該被定義為軟函數，因為來自不同傳播樹的兩個節點很難是相同的。

利用傳播樹的表示，我們首先定義一個函數f來評估兩個節點vi和vj之間的相似度（我們簡化例如vi =（ui，ci，ti）的節點表示）如下：

其中t = | ti-tj |是vi和vj的時間滯後之間的絕對值，

和

分別是基於用戶的相似性和基於內容的相似度，α是平衡參數。使用t的指數函數來縮小相似度，以在不同的傳播階段捕獲判別式信號或模式。例如，很早之前發布的一個質疑信息可能會預示一個錯誤的謠言，而發布時間遠晚於初始帖子的帖子則表示謠言仍然未被驗證，儘管這兩個消息在語義上相似。

基於用戶的相似性被定義為歐氏距離

，其中ui和uj是節點vi和vj的用戶向量，||?|| 2是向量的2範數。這裡

用於在整個傳播階段捕獲參與傳播謠言的用戶作為判別信號的特徵。

在內容上，我們使用Jaccard係數來測量帖子內容的相似性：

其中ci和cj是兩個節點中的內容詞集合。對於這裡的n-gram，我們採用一元文法uni-gram和二元文法bi-gram。它可以捕獲通常發生在謠言但不是非謠言中的提示術語，例如「假」、「揭開」、「不真實」等。

給定兩個傳播樹

和

，PTK旨在基於枚舉所有最相似的子樹對來迭代計算T1和T2之間的相似性。首先，對於每個節點

，我們得到

，V2中最相似的vi節點：

類似地，對於每個

，我們獲得

：

然後，傳播樹核KP（T1，T2）定義為：

其中

評估以v和

為根的兩個子樹的相似度，其遞歸計算如下：

1）如果v或

是葉節點，則

;

2）否則，

注意，與傳統的樹核不同，在PTK中，節點相似度

用於軟計數相似子樹而不是普通子樹。另外，

在樹核中不需要，因為由於節點相似度f，子樹大小在這裡不是一個問題。

PTK旨在從包含用戶、內容和時間特徵的傳播樹中捕獲判別模式，靈感來自於先前關於謠言傳播分析，例如，用戶信息可能是初始傳播中強有力的線索，內容特徵在整個傳播周期中是重要的，結構和時間模式有助於縱向擴散（Zubiaga et al., 2016; Kwon et al., 2017）。

4.3 上下文感知的PTK擴展模型

PTK的一個缺點是它忽略了子樹外的線索，例如信息如何從源文件傳播到當前的子樹。直觀地，傳播路徑為確定信息的真實性提供了進一步的線索，因為它們嵌入了傳播路徑和上下文。因此，我們通過考慮從樹根到子樹根的傳播路徑，提出上下文感知的PTK（cPTK），其靈感與上下文感知的樹核一致（Zhou等人，2007）。

對於傳播樹節點

，令

是從根r到v的傳播路徑的長度（即，#節點數），v [x]是v的第x個祖先從

開始的路徑。cPTK評估兩個樹T1（r1）和T2（r2）之間的相似性如下：

其中

測量根據

和

的子樹的相似性，用於上下文相關性評估，其計算如下：

1）如果x> 0，

，其中

和

是v和v』的第x個祖先節點相應的傳播路徑。

2）否則

，即PTK。顯然，當x = 0時，PTK是cPTK的特殊情況（參見等式3）。cPTK評估無上下文（不考慮傳播路徑上的祖先）和上下文感知的情況。

4.4 基於核學習的謠言檢測

基於核方法的優點是我們可以避免那些精心設計的特徵。這是可能的，因為核函數可以在計算兩個對象之間的相似性時探索隱式特徵空間（Culotta和Sorensen，2004）。

我們將所提出的樹核函數，即PTK（等式2）或cPTK（等式3）合併到監督學習框架中，為此我們利用基於核的SVM分類器。我們將每個樹視為一個實例，其所有訓練實例的相似度值作為特徵空間。因此，訓練集的核心矩陣為m×m，測試集的核心矩陣為n×m，其中m和n分別為訓練集和測試集的大小。

對於我們的多分類任務，我們為每個標籤執行一個one-vs-all分類，然後分配四類中可能性最高的一個，即非謠言、虛假的謠言、真實的謠言或未經驗證的謠言。我們選擇這種方法是由於結果的可解釋性，類似於最近的職業類別分類工作（Preotiuc-Pietro et al., 2015; Lukasik等，2015）。

5 實驗和結果

5.1 數據集

據我們所知，沒有公共大數據集可用於傳播樹分類，其中我們需要大量的源tweet，更準確地說，樹根與相應的傳播結構一起基於事實進行標註。我們基於幾個參考數據集構建了我們的數據集，即Twitter15（Liu et al., 2015）和Twitter16（Ma et al., 2016）。原始數據集被發布，並用於對包含其相關推文的給定事件的謠言和非謠言的二分類。

首先，我們提取了高轉發或回復的熱門源tweets。然後，我們收集所有傳播線程（即轉發和回復）這些源Twitter。由於Twitter API無法檢索轉發或回復，因此我們收集了Twrench的轉發用戶，並通過Twitter的Web界面爬取回復。

表1 數據集統計

最後，我們通過引用他們來自的事件的標籤來標註源tweet。我們首先根據謠言揭秘網站（例如http://snopes.com，http://Emergent.info等）中的文章的真實性標籤，將Twitter15和Twitter16中的每個事件的標籤從二類轉換為四類。然後，我們按照以下規則標記了原始推文：1）來自未驗證的謠言事件或非謠言事件的源推文被標記為與相應事件相同的標籤; 2）對於假謠言事件中的源推文，如果表示了否定類立場，我們對源推文取相反標籤為真，否則標籤被分配為假；3）類似的翻轉/不變規則也適用於來自真實謠言事件的源Twitter。

我們使數據集公開可訪問。表1給出了所得數據集的統計。

5.2 實驗設置

我們將基於核的方法與以下基線進行比較：

SVM-TS：線性SVM分類模型，其使用時間序列來模擬一組手工特徵的變化（Ma et al., 2015）。

DTR：基於決策樹的排名方法，用於識別趨勢傳播的謠言（Zhao et al., 2015），其中搜索查詢短語，並對有爭議的事實性聲明進行聚類，並根據統計特徵對聚類結果進行排名。

DTC和SVM-RBF：使用決策樹分類器（Castillo et al., 2011）和基於SVM的RBF核模型（Yang et al., 2012）的Twitter信息可信度模型，都採用基於對帖子全局統計信息的人工特徵。

RFC：Kwon等人（2017）提出的隨機森林分類器，使用三個參數來適應時間性質和，並採用與用戶、語言和結構特徵相關的廣泛的人工特徵。

GRU：Ma等（2016）提出的基於RNN的謠言檢測模型，具有門控遞歸單元，用於表示從跨時間相關帖子來學習高級特徵。

BOW：我們通過使用詞袋（bag-of-words）代表每個樹中的文本，並使用線性SVM構建謠言分類器，這是一個naive基線。

我們的模型：PTK和cPTK分別是我們完整的PTK和cPTK模型；PTK-和cPTK-是只使用內容而忽略用戶屬性設置的模型。

我們使用帶有Theano的LibSVM和GRU的Weka，SVM模型實現了DTC和RFC。我們在每個數據集中拿出10％的樹進行模型調優，而對於其餘的樹，我們進行了3次交叉驗證。我們使用精確率、F1值作為評估指標。

5.3 實驗結果

表2顯示了我們提出的方法優於兩個數據集的所有基線。

在所有基線中，GRU表現最好，其通過捕獲文本和時間信息，學習響應式推文的低維表示。這表明如提示詞或短語（例如，「什麼？」，「真的？」，「不確定」等）的複雜信號的有效性。這也證明了BOW的良好性能，即使它只使用一元文法進行表示。雖然DTR使用一組正則表達式，但是我們在包含這些表達式的數據集中只發現了19.59％和22.21％的推文。這就是為什麼DTR的結果不令人滿意。

表2 謠言檢測結果(NR: 非謠言; FR: 虛假謠言r; TR: 真實謠言; UR:未經驗證的謠言)

圖4 謠言早期檢測發現結果

圖5 在傳播早期由演算法捕獲到的謠言的示例子樹

SVM-TS和RFC是可比較的，因為它們都利用廣泛的特徵，特別是關注時間特徵。但是，沒有一個模型可以直接結合傳播樹的深度相似性比較的結構化傳播模式。SVM-RBF雖然使用非線性內核，但是基於傳統的人工特徵，而不是像我們這樣的結構核。所以，他們表現明顯比我們的方法差。

像GRU這樣的表徵學習方法不能輕易地利用複雜的結構信息，來從網路數據中學習重要的特徵。相比之下，我們的模型可以從豐富的語言、用戶和時間信號的結構化數據中捕獲複雜的傳播模式。因此，我們的模型的優越性是顯而易見的：僅使用文本的PTK已經比GRU更好，表明了傳播結構的重要性。結合文本和用戶的PTK在兩個數據集上產生更好的結果，這意味著兩個屬性是互補的，並且集成平面和結構化信息的PTK顯然更有效。

還有人指出，除非謠言類別，cPTK勝過PTK。這表明基於PTK的上下文感知建模對於不同類型的謠言是有效的，但對於非謠言來說，似乎考慮到傳播路徑的上下文並不總是有幫助的。這可能是由於在非謠言擴散期間，路徑上節點屬性通常是較弱的信號，因為非謠言中的用戶分布模式似乎不像謠言中那麼明顯。這不是cPTK中的一個問題，因為用戶信息根本不被考慮。在所有類中，cPTK在兩個數據集上都達到最高精度。

此外，我們觀察到所有的基線方法在非謠言方面比謠言表現得更好。這是因為現有方法的特徵是針對二分類（謠言與非謠言）問題進行定義的。所以對於細粒度的分類來說，它們的表現不好。我們的方法可以通過基於傳播結構不同模式的深入詳細比較來更好地區分各種類別。

5.4 早期檢測效果

在傳播的早期階段檢測謠言是非常重要的，以便儘快採取預防措施。在早期檢測任務中，檢測期限後的所有帖子在測試期間不可見。截止日期越早，傳播信息就越少。

圖4顯示了針對各種期限的PTK和cPTK模型與RFC（基於特徵工程的最佳系統）、GRU（基於RNN的最佳系統）和DTR（早期檢測特定演算法）的性能。在最初的幾個小時，我們的方法表現出優於其他早期檢測模型的性能。特別地，cPTK在24小時內在Twitter15上達到75％的準確率，在Twitter16上達到73％，這比其他模型快得多。

我們的分析表明，謠言通常表現出更複雜的傳播子結構，特別是在早期階段。圖5顯示了在其最初幾個小時內檢測到的虛假謠言蔓延的子樹，其中有影響力的用戶以某種方式增強其傳播，並且信息流在用戶之間具有明顯的從不受歡迎的流行到受歡迎的再到不受歡迎的趨勢，但這種模式在早期的非謠言中沒有見到。早期也可以觀察到許多文字信號（下劃線）。我們的方法可以自然地學習這樣的結構和模式，但是在特徵提取工程中很難獲取和手工製作它們。

6 結論和未來工作

我們提出了一種基於使用傳播樹的核學習方法來檢測微博帖子中的謠言的新穎方法。傳播樹使用複雜的結構化模式和關於與樹結點相關聯的內容、用戶和時間的基礎信息對假設（即源tweet）進行編碼。基於樹核技術的啟發，我們通過核函數直接測量傳播樹之間的相似性，學習識別細粒度謠言的判別線索。兩個Twitter數據集的實驗表明，我們的方法比一般和早期謠言檢測任務具有較大的優勢，優於最先進的基線。

由於基於核的方法涵蓋了比基於特徵的方法更多的結構信息，因此它允許核進一步融入來自高維空間的信息，以獲得更好的判別結果。未來，我們將重點通過探索網路表示學習框架來改進謠言檢測任務。此外，考慮到社會媒體上大規模未標記的謠言數據，我們計劃調研無監督模式。

論文下載鏈接：

http://www.aclweb.org/anthology/P/P17/P17-1066.pdf

留言點贊發個朋友圈

我們一起探討AI落地的最後一公里