【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 論文連結：http://hanj.cs.illinois.edu/pdf/wsdm18_mqu.pdf
代碼連結：https://github.com/mnqu/DRL
會議：WSDM 2018
本文将深度強化學習應用到了異構星型網絡的表示學習中。在異構星型網絡表示的學習過程中通常需要采樣一系列的邊來得到點之間的相似性，作者發現這些邊的順序會顯著影響表示學習的效果。作者借鑒了課程學習（Curriculum Learning）的思想，研究如何在網絡表示學習中學習這些邊的采樣順序。該問題可以形式化為馬爾可夫決策過程，作者提出了一個基于深度強化學習的解決方法。
1 摘要
本文聚焦于異構星型網絡的節點表示學習問題。異構星型網絡有一個中心節點，通過不同類型的邊和多個不同類型的屬性節點相連。在異構星型網絡中，不同類型邊的訓練順序會影響模型的表現效果。作者在異構星型網絡的節點表示學習中，引入課程學習的思想。為節點表示學習學習到一個最優順序的邊序列。
問題可被形式化為馬爾科夫決策過程，動作是為訓練選擇特定類型的邊，狀态是到目前為止選擇的邊的類型序列。獎勵由實際任務中的準确度定義，目标是采取一系列的動作以實作最大化積累獎勵。
作者提出基于深度強化學習的方法解決上述問題。利用LSTM模型編碼狀态（state），并估計每個狀态-動作對（state-action pair）的期望累計獎勵。（在節點分類任務上做了實驗）
2 介紹
異構星型網絡有一個中心節點，通過不同類型的邊和多個不同類型的屬性節點相連。許多問題都可以形式化為異構星型網絡上的問題，例如author identification、predictive text embedding、user attribute prediction。下圖是一個引文領域的異構星型網絡：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 節點表示學習的關鍵就是擷取編碼在邊中的節點間相似度資訊，是以需要采樣不同類型的邊作為訓練資料。現有的方法通常采用随機采樣、權重采樣的方式，不考慮不同類型邊之間的相對順序。然而，每種類型的邊都編碼了特定的知識，可能會對不同的訓練步驟帶來影響，也就是說邊類型的訓練順序在訓練中很重要。
例如上圖所示，在學習paper節點的表示時，venue粗略反映了文獻的類型，而keywords和references更具體地刻畫了文獻的語義資訊。
受課程學習的啟發，粗略的語義資訊可能更易了解，且可能對更具體的語義資訊的學習起到幫助作用。先選擇簡單的樣本進行學習，然後逐漸增加學習難度。
2.1 動機
盡管課程學習已被廣泛研究，但是在異構星型網絡的節點表示學習中，如何學習到有意義的訓練資料順序，還沒有被研究過。其中，課程被定義為用于訓練的邊類型序列。問題實際上是一個連續的決策任務，作者将其形式化為馬爾科夫決策過程。每一步的動作是為訓練選擇特定類型的邊，狀态是到目前為止選擇的邊的類型序列。在每個狀态采取了一個動作後，轉移到下一個狀态且得到了一個回報。目标是學習到一個邊類型的序列以最大化整體的回報和。但是搜尋空間是序列長度的指數倍，作者提出的方法可以有效高效地進行學習。
2.2 作者提出
基于深度強化學習的方法，進行異構星型網絡的表示學習。通過估計每個狀态-節點對（state-action pair）的回報值Q，學習到最優的課程式列。
Q值的學習來源于計劃子產品和學習子產品。給定狀态後，計劃子產品通過向前看（looking ahead）計算Q，通過模拟發掘出了子序列動作，然後用模拟出來的回報估計Q值。然而，學習子產品是通過向後看（looking back）來估計Q。作者使用了LSTM模型，通過學習過去的經驗進一步做預測。
使用這兩個子產品，可以高效準确地估計Q值。進而高效有效地學習到有意義的課程。
2.3 貢獻
（1）定義了一個新問題——使用課程學習方法解決異構星型網絡的節點表示學習；
（2）上上述問題形式化為馬爾科夫決策過程，提出基于深度強化學習的解決方法；
（3）在真實存在的異構星型網絡上進行了實驗，證明了本文方法的有效性和高效性。
3 方法
3.1 問題定義
（1）異構星型網絡：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 ，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是中心節點，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是和
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 相連的屬性節點，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是中心節點和屬性節點之間的連邊，每條邊都有w>0的權重，表示連接配接節點之間的關系強度。
（2）問題定義：給定異構星型網絡
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 和回報函數
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 。對于每個狀态-動作對(s, a)，采取一系列的動作以最大化回報的總和，為訓練過程學習到一個邊類型序列。
3.2 METHODOLOGY
問題形式化為馬爾科夫決策過程，每一步的動作是選擇一個特定類型的邊（記為
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 ,
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 ），或者是判斷終止條件（a=STOP ）。狀态定義為到目前為止所選邊類型的序列，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 。在每個狀态下完成一次動作後，會轉移到下一個狀态，并且通過回報函數R(s,a) ，計算得到一個回報Q(s,a) 。對于不同的任務，回報函數也不同，例如節點分類任務的回報為動作發生後的準确度增益。最終的目标是采取一系列的動作以最大化回報，為訓練過程學習到一個邊類型序列。
一旦學習得到Q值，就可以通過連續地選擇每一步使Q最大化的動作，組成最優的動作序列。
Q值的學習來源于計劃子產品和學習子產品。為了權衡有效性和高效性，對每個動作都有一定的懲罰。當為一個動作計算回報時，根據回報函數的計算結果，減去一個常值懲罰。小的懲罰值鼓勵學習到更長的序列，這有益于有效性，但不利于高效性；大的懲罰值鼓勵學習到更短的序列，這不利于有效性，但有利于高效性。
架構的整體結構如下圖所示：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 3.2.1 Planning Module
計劃子產品是從給定的狀态出發向前看，模拟出子序列動作，估計Qp 的值。每次模拟時，先選擇動作序列，然後使用節點表示學習算法模拟動作，并計算回報，根據回報進一步優化Qp 。具體流程如下：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 狀态-動作對（state-action pair）的回報值
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是使用look-up table計算的。像蒙特卡洛樹搜尋一樣，給定狀态s，每次模拟都遞歸地選擇一些動作，直到通路到未被通路的狀态為止（上圖中的黃色狀态）。針對狀态s，使用如下的公式選擇動作a：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 分别是計劃子產品和學習子產品計算出的Q值，N(s, a)通路次數，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是狀态s的通路次數和。
到達未被通路的狀态後，使用節點表示算法模拟被選的動作，也就是使用相應類型的邊更新節點表示，或者是終止訓練過程。接着，在學習得到的節點表示上應用回報函數就可計算出回報值。基于下式，更新
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 ：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 其中
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是學習率，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是在狀态
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 處采樣動作
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 後的即時回報，
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是對長期回報的估計。
3.2.2 Learning Module
學習子產品是向後看（looking back），回看過去的經驗，使用深度神經網絡記憶曆史資料，估計
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 。
在DNN中，用向量表示每種類型的邊
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 和動作
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 。用LSTM層編碼狀态
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 ，然後将狀态s和動作a的編碼向量拼接起來，使用兩層全連接配接網絡計算
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 。網絡結構如下圖所示：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 使用LSTM編碼狀态序列，可以有效的擷取不同狀态之間的相關性。基于新的狀态-動作對（state-action pair）與之前的相關性，可以有效地推斷出
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 的值。
為了學習到DNN的參數，作者将計劃子產品模拟得到的state-action pairs和相對應的回報作為訓練資料。模拟得到的state-action序列記為
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 ，相對應的回報序列記為
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 。基于下式進行參數更新：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 3.2.3 整合兩個子產品
給定目前狀态s，為動作a計算回報值：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是基于前向搜尋的，相對更精确，是以在式中占更大的權重。Ql
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是基于過去的經驗進行學習的，權重值會随着通路次數的增加而減小。
回報值Q估計了在狀态s采取動作a的回報期望，讓Q最大的動作
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 是目前步驟的最好選擇。選擇動作
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 也就是為節點表示學習選擇了合适的邊類型，或者是實作了訓練過程的終止條件。
本文提出的基于課程學習的節點表示學習過程，整體算法如下：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 4 實驗
資料集：DBLP、Yelp、IMDB
實驗任務：中心節點分類任務（有監督和無監督兩種實驗設定）
對比方法：
（1）LINE和node2vec都是用于同質圖的方法，為了适用于本文工作的異構星型網絡，作者給不同類型的邊賦予了不同的權重。
（2）Rand：在每步訓練選擇不同類型的邊，并使用LINE學習節點的表示。
（3）Greedy：根據每步最大的即時回報，貪婪地選擇動作，并使用LINE學習節點表示。
（4）DRL：使用本文的深度強化學習的方法，學習得到合适的序列，并使用LINE學習節點表示。
（5）DRL-Shuf：打亂本文方法學習到的序列，并使用LINE學習節點表示。
（6）DRL-P：隻使用計劃子產品，學習子產品的回報值保持為0。
（7）DRL-L：隻使用學習子產品，計劃子產品的回報值保持為0。
實驗結果：
無監督設定下的實驗結果如下：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 半監督設定下的實驗結果如下：
【論文解讀 WSDM 2018 | DRL】Curriculum Learning for Heterogeneous Star Network Embedding via DRL1 摘要2 介紹3 方法4 實驗5 總結 5 總結
本文的工作是針對異構星型網絡的節點表示學習。
前人的方法都沒有考慮到不同類型邊的訓練順序，作者的動機就是學習到有意義的不同類型邊的訓練順序，以提高表示學習的能力。
作者使用深度強化學習的方法解決了這一問題，具體來講用的是課程學習（curriculum learning）的方法，并且使用了強化學習中的學習（learning）和計劃（planning）政策。第一個将課程學習，應用到了異構星型網絡的節點表示學習上。
本文的工作是針對異構星型網絡的，課程（curriculum）指的是邊類型的序列。作者考慮未來将這一架構擴充至一般的異構網絡中，那時的課程就可以定義成meta-path的序列，或者hyper-edges的序列。
研究的問題很有新意，想到的解決方法（課程學習）也很有新意。本文在HIN表示學習的具體貢獻展現在模型的訓練過程中，即如何擷取更有效的按照一定順序的訓練資料，以優化模型的節點表示學習能力。并沒有像以往大多數的論文一樣，提出更好的HIN嵌入學習方法。但作者的想法還是非常有新意的。
