圖強化學習--原理與實踐入門

 

目   錄

第一部分  圖強化學習研究對象

第1章  圖與復雜系統  3

1.1  為什麽是圖  3

1.1.1  圖的普遍性  3

1.1.2  圖的表示性  4

1.1.3  圖的抽象性  4

1.2  圖與復雜系統  5

1.2.1  復雜系統定義  5

1.2.2  復雜系統的圖表示  6

1.2.3  復雜系統問題與圖  7

1.3  復雜系統與強化學習  7

1.3.1  強化學習  8

1.3.2  智能決策  8

1.3.3  基於強化學習的智能決策  9

1.4  復雜系統與智能決策  9

1.4.1  復雜金融系統風險管理問題  10

1.4.2  復雜社會系統輿情傳播和虛假信息防控問題  12

1.5  應用實踐  12

1.5.1  圖數據集  13

1.5.2  圖可視化和分析工具  13

第1章習題  14

第2章  圖論基礎  15

2.1  圖論的起源  15

2.1.1  提出問題  16

2.1.2  形式化問題  16

2.1.3  求解問題  16

2.2  圖論的發展  17

2.2.1  隨機圖理論  17

2.2.2  拓撲圖論  17

2.2.3  幾何圖論  18

2.2.4  代數圖論  18

2.3  圖論的概念  18

2.3.1  圖定義  19

2.3.2  節點  19

2.3.3  連邊  19

2.3.4  鄰接矩陣  20

2.3.5  度  20

2.3.6  鄰域  20

2.3.7  途徑  21

2.3.8  最短路  22

2.3.9  帶自環圖  23

2.3.10  圈  23

2.3.11  子圖  24

2.3.12  連通分量  24

2.3.13  最大連通子圖  25

2.3.14  簡單圖  25

2.3.15  平面圖  26

2.3.16  對偶圖  26

2.3.17  樹  28

2.4  經典圖示例  29

2.4.1  完全圖  29

2.4.2  二部圖  30

2.4.3  彼得森圖  31

2.4.4  星狀圖  31

2.4.5  網格圖  32

2.4.6  正十二面體圖  33

2.5  經典問題示例  33

2.5.1  圖同構  33

2.5.2  TSP問題  34

2.5.3  最小點覆蓋問題  35

2.5.4  最大割問題  35

2.5.5  最大獨立集問題  35

2.6  可視圖  35

2.6.1  可視圖算法  36

2.6.2  水平可視圖算法  36

2.6.3  水平可視圖度分佈  37

2.6.4  有向水平可視圖度分佈 39

2.7  應用實踐  41

第2章習題  42

第3章  圖與復雜網絡  44

3.1  復雜網絡背景  44

3.1.1  復雜網絡簡介  44

3.1.2  復雜網絡簡史  45

3.1.3  復雜網絡應用  45

3.1.4  復雜網絡分析概述  46

3.1.5  網絡表示  47

3.2  節點指標  48

3.2.1  節點的度  48

3.2.2  節點的強度  49

3.2.3  聚簇系數  49

3.2.4  接近中心性  50

3.2.5  介數中心性  50

3.2.6  特性向量中心性  50

3.2.7  PageRank中心性  51

3.2.8  權威值得分和樞紐值得分  51

3.2.9  k核中心性  52

3.3  網絡連邊指標  53

3.3.1  連邊權重  53

3.3.2  顯著性測度  53

3.3.3  邊介數中心性  55

3.3.4  共同鄰居數  55

3.3.5  網絡關系Adamic/Adar量  56

3.3.6  網絡關系Resource Allocation量  56

3.4  網絡模體結構  56

3.4.1  模體的定義  56

3.4.2  無向網絡的四元模體  56

3.4.3  有向網絡的三元模體  57

3.4.4  有向網絡三元模體與節點位置結構  58

3.5  網絡模塊結構  59

3.5.1  網絡模塊定義  60

3.5.2  模塊內度  60

3.5.3  參與系數  61

3.5.4  模塊外度  61

3.5.5  模塊穩定性  61

3.6  網絡全局結構  62

3.6.1  網絡密度  62

3.6.2  網絡同配性和異配性  63

3.6.3  網絡穩健性  63

3.6.4  網絡效率  64

3.7  復雜網絡分類  65

3.7.1  異質網絡  65

3.7.2  多層網絡  66

3.7.3  多重網絡  66

3.7.4  超圖網絡  66

3.7.5  動態網絡  67

3.8  復雜網絡任務  68

3.8.1  節點任務  68

3.8.2  網絡連邊任務  68

3.8.3  全局網絡任務  69

3.9  復雜網絡生成  69

3.9.1  隨機網絡模型  69

3.9.2  隨機模塊模型  70

3.9.3  優先連接模型  72

3.9.4  同質性偏好連接模型  73

3.9.5  異質性或互補性偏好連接模型  74

3.9.6  機器學習或智能算法類模型  74

3.10  網絡建模實例  74

3.10.1  效用函數  75

3.10.2  成本函數  76

3.10.3  決策函數  77

3.11  應用實踐  79

第3章習題  81

第二部分  圖強化學習基礎知識

第4章  圖嵌入與網絡嵌入  85

4.1  圖的特徵表示  85

4.1.1  多尺度圖特徵表示  85

4.1.2  如何表示復雜系統  86

4.1.3  如何表示復雜圖或復雜網絡  86

4.1.4  如何表示圖節點  86

4.1.5  如何表示圖連邊  87

4.1.6  多層次的圖特徵表示方法  87

4.2  圖與機器學習  88

4.2.1  機器學習簡介  88

4.2.2  機器學習分類  88

4.3  機器學習框架  89

4.3.1  框架簡介  89

4.3.2  目標函數  89

4.3.3  優化參數  90

4.4  自編碼器框架  90

4.4.1  自編碼器模型介紹  90

4.4.2  簡單應用  91

4.5  機器學習模型  91

4.5.1  典型的數據類型  92

4.5.2  多層感知機網絡  92

4.5.3  捲積神經網絡  92

4.5.4  循環神經網絡  94

4.6  圖表示學習  94

4.6.1  圖表示學習的一般框架  94

4.6.2  編碼-解碼框架  95

4.6.3  編碼器  95

4.6.4  解碼器  96

4.6.5  模型優化  97

4.7  基於矩陣分解的圖嵌入  97

4.7.1  圖分解方法  98

4.7.2  GraRep方法  98

4.7.3  HOPE方法  99

4.8  基於隨機游走的圖嵌入  99

4.8.1  DeepWalk算法  99

4.8.2  Node2Vec方法  102

4.9  可解釋性圖嵌入  104

4.9.1  問題背景介紹  105

4.9.2  天然氣貿易決策模型  105

4.9.3  效用函數  106

4.9.4  收益函數  106

4.9.5  成本函數  106

4.9.6  機器學習模型損失函數  107

4.9.7  模型優化  108

4.10  應用實踐  108

第4章習題  109

第5章  圖神經網絡  110

5.1  圖神經網絡介紹  110

5.2  圖神經網絡特徵  111

5.2.1  圖數據特徵  111

5.2.2  端到端學習特徵  112

5.2.3  歸納學習特徵  112

5.3  圖神經網絡框架  113

5.3.1  圖神經網絡框架簡介  113

5.3.2  消息傳遞神經網絡框架  113

5.3.3  鄰域信息匯聚函數  114

5.3.4  信息更新函數  114

5.3.5  圖信息池化函數  115

5.4  圖捲積神經網絡  115

5.4.1  譜圖理論介紹 115

5.4.2  拉普拉斯矩陣定義  116

5.4.3  隨機游走歸一化拉普拉斯矩陣  116

5.4.4  對稱歸一化拉普拉斯矩陣  116

5.4.5  拉普拉斯矩陣簡單應用  117

5.4.6  圖信號處理  118

5.4.7  圖傅里葉變換  118

5.4.8  圖傅里葉逆變換  119

5.4.9  圖濾波器  120

5.4.10  圖譜濾波  121

5.4.11  K階截斷多項式濾波算子  123

5.4.12  切比雪夫多項式濾波算子  124

5.4.13  圖捲積神經網絡  125

5.5  圖註意力神經網絡  127

5.5.1  註意力機制簡介  127

5.5.2  基於註意力機制的信息匯聚函數  127

5.5.3  多頭註意力模型框架  129

5.6  圖網絡  129

5.6.1  更新連邊信息  130

5.6.2  匯聚連邊信息  130

5.6.3  更新節點信息  130

5.6.4  匯聚全局信息  130

5.7  應用實踐 131

第5章習題  133

第6章  強化學習基礎  134

6.1  強化學習背景  134

6.1.1  強化學習與圖神經網絡  135

6.1.2  強化學習與序貫決策問題  135

6.1.3  強化學習求解序貫決策問題  135

6.1.4  強化學習特徵  136

6.2  強化學習與圖  136

6.2.1  圖上決策問題  136

6.2.2  強化學習與圖上決策問題  137

6.3  強化學習概念  138

6.3.1  馬爾可夫決策過程  138

6.3.2  狀態和狀態空間  139

6.3.3  動作和動作空間  139

6.3.4  狀態轉移函數  140

6.3.5  即時回報函數  140

6.3.6  回報折扣系數  140

6.3.7  策略函數  141

6.3.8  狀態值函數  141

6.3.9  狀態--動作值函數  142

6.4  蒙特卡洛方法  142

6.4.1  蒙特卡洛採樣  143

6.4.2  狀態值函數估計  143

6.4.3  狀態--動作值函數估計  143

6.4.4  值函數增量更新方法  144

6.4.5  蒙特卡洛強化學習偽代碼  146

6.5  時序差分學習  147

6.5.1  時序差分簡介  148

6.5.2  Q--learning算法簡介  149

6.5.3  Q--learning算法偽代碼  150

6.5.4  SARSA算法簡介  151

6.5.5  SARSA算法偽代碼  151

6.5.6  SARSA與Q--learning對比分析  152

6.6  策略梯度方法  153

6.6.1  軌跡概率  153

6.6.2  策略梯度  154

6.6.3  目標函數  154

6.6.4  蒙特卡洛策略梯度算法  155

6.6.5  REINFORCE算法偽代碼  156

6.7  強化學習分類  156

6.7.1  值函數方法和策略函數方法  157

6.7.2  On-policy 和 Off-policy強化學習  157

6.7.3  Online 和 Offline強化學習  157

6.7.4  Model-based 和 Model-free強化學習  157

6.8  應用實踐  158

6.8.1  狀態空間  158

6.8.2  動作空間  159

6.8.3  狀態轉換  159

6.8.4  即時獎勵  159

6.8.5  折扣系數  160

6.8.6  狀態價值函數  160

6.8.7  最優策略函數  161

第6章習題  161

第7章  深度強化學習  163

7.1  深度強化學習背景  163

7.1.1  深度學習  163

7.1.2  深度強化學習  164

7.2  深度Q網絡方法  165

7.2.1  Q表格  165

7.2.2  軌跡採樣  165

7.2.3  深度神經網絡近似策略函數  166

7.2.4  TD目標  167

7.2.5  TD誤差  167

7.2.6  目標函數  167

7.2.7  目標函數梯度  168

7.2.8  深度神經網絡參數更新  168

7.2.9  最優策略  169

7.3  深度Q網絡算法關鍵技術  169

7.3.1  -貪心策略  169

7.3.2  目標網絡  170

7.3.3  經驗回放  170

7.3.4  DQN算法偽代碼  170

7.4  深度Q網絡算法面臨的挑戰  171

7.4.1  離策略  172

7.4.2  自舉  172

7.4.3  函數近似  172

7.5  深度策略梯度方法  172

7.5.1  深度Q神經網絡算法的局限  172

7.5.2  深度策略梯度算法簡介  173

7.6  深度策略梯度算法關鍵技術  174

7.6.1  策略梯度估計  174

7.6.2  策略函數參數更新  175

7.6.3  優勢函數估計  175

7.6.4  狀態值函數估計  176

7.6.5  深度策略梯度算法偽代碼  177

7.7  行動者--評論家方法  178

7.7.1  AC（Actor--Critic）算法簡介  178

7.7.2  A2C算法簡介  178

7.7.3  A2C算法偽代碼  179

7.8  應用與實踐的通用框架  180

7.8.1  馬爾可夫決策過程模型  180

7.8.2  狀態空間  181

7.8.3  動作空間  181

7.8.4  狀態轉移函數  181

7.8.5  即時獎勵函數  181

7.8.6  折扣系數  182

7.9  基於策略梯度算法的應用與實踐  182

7.9.1  復雜環境模型  182

7.9.2  深度學習模型  182

7.9.3  深度強化學習算法  183

7.9.4  智能體模型  185

7.9.5  深度強化學習模型訓練結果  186

7.10  基於深度Q網絡算法的應用與實踐  187

7.10.1  游戲環境狀態空間  187

7.10.2  智能體動作空間  188

7.10.3  游戲即時獎勵  188

7.10.4  游戲狀態轉移模型  189

7.10.5  游戲環境模型  189

7.10.6  游戲策略模型  189

7.10.7  深度強化學習算法  189

7.10.8  模型訓練分析  190

7.10.9  模型結果分析  191

7.10.10  模型改進分析  192

第7章習題 194

第三部分  圖強化學習模型框架和應用實踐

第8章  圖強化學習基礎  197

8.1  圖強化學習背景  197

8.1.1  多學科交叉融合  197

8.1.2  多學科關聯關系圖  198

8.1.3  圖與網絡的基礎理論和方法  199

8.1.4  圖與機器學習的基礎理論和方法  199

8.1.5  圖神經網絡的基礎理論和方法  199

8.1.6  深度強化學習的基礎理論和方法  199

8.2  圖神經網絡和強化學習  200

8.2.1  圖神經網絡和強化學習的融合  200

8.2.2  圖強化學習和強化學習的區別  201

8.2.3  圖神經網絡提升強化學習性能  201

8.2.4  強化學習提升圖神經網絡性能  202

8.3  圖強化學習模型概要  202

8.3.1  復雜系統  203

8.3.2  環境模型  203

8.3.3  圖和網絡  203

8.3.4  深度神經網絡  203

8.3.5  深度強化學習  204

8.3.6  優化算法  204

8.3.7  圖強化學習框架概要  205

8.4  圖強化學習框架硬件層  206

8.4.1  中央處理器  206

8.4.2  圖形處理器  206

8.4.3  張量處理器  206

8.4.4  其他處理器  207

8.5  圖強化學習框架平臺層  207

8.5.1  深度學習平臺簡介  207

8.5.2  深度學習平臺：TensorFlow  207

8.5.3  深度學習平臺：PyTorch  208

8.5.4  深度學習其他平臺  208

8.6  圖強化學習框架算法層  208

8.6.1  深度強化學習框架簡介  209

8.6.2  深度強化學習框架：Stable--baselines  209

8.6.3  深度強化學習框架：Reinforcement Learning Coach  210

8.6.4  深度圖神經網絡框架簡介  210

8.6.5  深度圖神經網絡框架：PyTorch Geometric  210

8.6.6  深度圖神經網絡框架：Deep Graph Library  211

8.7  圖強化學習框架應用層  211

8.8  圖強化學習建模  211

8.8.1  圖強化學習與馬爾可夫決策過程  211

8.8.2  圖強化學習建模流程  212

8.8.3  問題提出  212

8.8.4  環境建模  213

8.8.5  智能體建模  213

8.8.6  模型訓練  214

8.8.7  模型測試  214

8.9  應用實踐  214

8.9.1  深度強化學習模塊  214

8.9.2  圖神經網絡模塊  215

8.9.3  其他圖神經網絡模塊  217

第8章習題  218

第9章  圖強化學習應用  219

9.1  圖強化學習模型框架  219

9.2  圖強化學習模塊概述  220

9.2.1  復雜環境模塊  221

9.2.2  圖神經網絡模塊  221

9.2.3  強化學習模塊  221

9.2.4  智能體模塊  221

9.2.5  工具類模塊  222

9.2.6  其他模塊  222

9.3  復雜環境模塊  222

9.3.1  環境模塊定義  222

9.3.2  環境模塊定義代碼  222

9.3.3  基於圖的環境模塊定義  224

9.3.4  基於圖的環境模塊重置定義  224

9.3.5  基於圖的環境狀態轉移定義  224

9.4  圖神經網絡模塊  225

9.4.1  圖神經網絡模型選擇  225

9.4.2  圖神經網絡模塊代碼示例  225

9.4.3  圖神經網絡模塊代碼解析  226

9.5  強化學習模塊  227

9.5.1  強化學習算法選擇  227

9.5.2  強化學習算法示例代碼  227

9.5.3  強化學習算法示例代碼解析  228

9.6  智能體模塊  229

9.6.1  智能體模塊示例代碼  229

9.6.2  智能體模塊示例代碼解析  230

9.6.3  模型訓練結果  231

9.7  工具類模塊  232

9.8  圖強化學習模型改進  232

9.8.1  模型改進目標  233

9.8.2  模型改進方向  233

9.8.3  圖神經網絡模型改進代碼示例  234

9.8.4  圖神經網絡模塊代碼解析  234

9.8.5  強化學習算法改進  234

第9章習題  235

第10章  圖強化學習展望  237

10.1  圖強化學習概括  237

10.1.1  方法的起源  237

10.1.2  方法的發展  238

10.1.3  層次關系  238

10.2  圖強化學習特色  238

10.2.1  學科交叉性  239

10.2.2  系統復雜性  239

10.2.3  框架普適性  239

10.3  圖數據分析方法  239

10.3.1  數值分析方法  240

10.3.2  模擬模擬方法  240

10.3.3  優化方法  241

10.3.4  數據驅動方法  241

10.3.5  圖強化學習方法  241

10.4  圖強化學習應用  242

10.4.1  網絡關鍵節點識別  242

10.4.2  網絡關鍵連邊識別  242

10.4.3  知識圖譜  243

10.4.4  組合優化  243

10.5  圖神經網絡展望  243

10.5.1  人工智能的新引擎  243

10.5.2  圖神經網絡進展  244

10.5.3  圖神經網絡的可解釋性  244

10.6  深度強化學習展望  245

10.6.1  自動強化學習  246

10.6.2  分層強化學習  246

10.6.3  多智能體強化學習  246

10.7  圖強化學習前沿領域  247

10.7.1  圖上的組合優化  247

10.7.2  圖理論應用的前沿  247

10.7.3  交叉研究的前沿  248

10.8  人工智能三大學派融合  248

10.8.1  人工智能的三大學派  248

10.8.2  圖強化學習融合三大學派  249

第10章習題  250