# 李宏毅_ATDL_Lecture_16
###### tags: `Hung-yi Lee` `NTU` `Advance Topics in Deep Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## RL and GAN for Sentence Generation and Chat-bot
[課程連結](https://www.youtube.com/watch?v=pbQ4qe8EwLo&list=PLJV_el3uVTsPMxPbjeX7PicgWbY7F8wW9&index=16)
### Review: Chat-bot

訓練Chat-bot的第一件事就是收集大量的對話資料_{(電影台詞也可以)}。

手上會有Encoder與Generator，輸入一句話經過Encoder，再經過Generator之後我們希望Generator的輸出愈接近資料集中說的下一句話愈好。_{(這邊可以加入注意力機制提高效能)}

當然你也可以把過去的歷史資訊連同這次的對話一併做為Encoder的輸入，這可以帶入上下文的概念。

### Review: Encoder

上面以『我很好』做為本次的對話，『你好嗎』做為上次的對話，實務上依個人需求來定義Encoder的複雜度。如果Chat-bot是有開cam的話，也可以連帶將人臉做為資訊讀入。

但如果要帶入Context的話就需要使用`Hierachical Encoder`_{(階層式編碼器)}，先將上下文各自編碼之後再匯整編碼一次，最後這個編碼才是Generator的輸入。

### Review: Generator

1. Encoder的輸出做為Generator的輸入，為Vector
2. Generator根據輸入產生Word Distribution，代表生成語句的第一個詞彙
3. 根據第一個時步生成的詞彙_(範例為B)搭配Encoder的資訊做為第二個時步的輸入，產生第二個Word Distribution
4. 再根據第二個時步生成的詞彙_(範例為A)搭配Encoder的資訊做為第三個時步的輸入，產生第三個Word Distribution
5. ......so on....

如果加入注意力機制的話，那每一個時步的Encoder Vector就會是不一樣的。

註1：簡報錯誤，左下應該是`from encoder`：
註2：`<BOS>`:Begin of Sentence
### Review: Training Generator

訓練過程中可以利用實際資料來告訴機器正確答案，因此訓練過程中機器會計算輸出的資料與實際資料的差異性_{(即計算corss-entropy)}

訓練與測試的時候最大差異在於，訓練過程中會將`Reference`_{(即正確資料)}做為下一個時步的輸入，但測試的時候以將模型輸出做為下一個時步的輸入，在之前的課程有提過，這會造成`Miss-Match`的問題，也提過可以採用`Schedual-sampling`來改善。

將每個時步的Cross-entropy加總起來，就是我們要優化的對象，以此更新Encoder與Generator的參數。
### Review: Training Generator

$h, \hat{x}$都是句子，Word Sequence：
* $h$：加入上下文或歷史資訊的輸入句子
* $\hat{x}$：輸出的句子，案例來看是回應的句子。
* $\hat{x}_t$：代表第$t$個時步的詞彙

實際優化的目標：
* $C_t=-logP_\theta(\hat{x}_t|\hat{x}_{1:t-1},h)$
* 這是單一個time step的cost
* $C=-\sum_tlogP(\hat{x}_t|\hat{x}_{1:t-1},h)$
* 這是一個句子的cost，log加總拆開項即為連乘，得到如下式子：
* $-logP(\hat{x}_1|h)P(\hat{x}_t|\hat{x}_{1:t-2},h)...P(\hat{x}_T|\hat{x}_{1:T-2},h)$
* $=-logP(\hat{x}|h)$
* 實際上我們優化的目標就是最大化似然概率，Maximum Likelihood，也就是給定$h$有情況下，decoder出來的是$\hat{x}$的機率愈大愈好

這是一種傳統訓練的方式，下面要說明的就是這節課程要提的，利用強化學習來訓練語句的生成。
### Introduction

假設，人與機器談話的過程中會有回饋資訊：
* 人：How are you?
* 機器：Bye bye.
* 人：-10分

回饋資訊的給定是按實際系統設置，但最終都會給定一個數值。

機器要學習的就是依據過去得到的資訊來最大化未來預期得到的`reward`。
### Maximizing Expected Reward

原始的function，輸入$h$之後經過Encoder、Generator而產生輸出$x$，現在，加入一個新的function-Human，這個function主要用來評斷輸出結果的好壞，並給予分數，即Reward-$R(h,x)$，它的輸出是一個數值。

接著，Encoder與Generator再依據所得的Reward來更新參數$\theta$，希望讓$\overline{R}$的值愈大愈好：
* $\overline{R}_\theta=\sum_hP(h)\sum_xR(h,x)P_\theta(x|h)$
* $\sum_h$：所有可能的輸入句子
* $P(h)$：句子出現的機率
* $\sum_hP(h)$：窮舉所有可能的$h$
* $P_\theta(x|h)$：給定$h,\theta$情況下，輸出為$x$的機率
* 相同的輸入會有不同的回應輸出，這是因為Generator本身有隨機性，每一個時步都會根據分佈做一次採樣。
* $\sum_x$：加總所有可能的輸出
* $R(h,x)$：衡量這個句子回應好壞
* $=E_{h\sim P(h)}\left[E_{x\sum P_\theta(x|h)}\left[R(h,x)\right]\right]$
* 利用計算期望值的方式來求解
* $=E_{h\sum P(h),x\sim P_\theta(x|h)}\left[R(h,x)\right]$
* $\approx\dfrac{1}{N}\sum_{i=1}^NR(h^i,x^i)$

從之前的課程我們已經知道，我們不可能窮舉所有資料來計算期望值，因此我們能做的就是sample，再利用sample出來的資料計算近似的期望值。

現在有個問題，我們要最大化機率就要用梯度上升來求解，拿$\theta$來微$\overline{R}$，但近似期望值的部份是用sample計算而得，這跟參數-$\theta$無關，即使我們知道，輸出結果跟參數$\theta$是息息相關，但在function-Human上是看不到與$\theta$相關的資訊，沒辦法計算$\theta$的偏微分就沒有辦法求最佳解。

### Policy Gradient

$\overline{R}_\theta=\sum_hP(h)\sum_xR(h,x)P_\theta(x|h) \approx\dfrac{1}{N}\sum_{i=1}^NR(h^i,x^i)$

我們只對$\theta$相關做偏微分，得到：
$\nabla\overline{R}_\theta=\sum_hP(h)\sum_xR(h,x)\nabla P_\theta(x|h)$

接下來將分子分母都乘上$P_\theta(x|h)$：
$=\sum_hP(h)\sum_xR(h,x)P_\theta(x|h)\dfrac{\nabla P_\theta(x|h)}{P_\theta(x|h)}$

剛才調整的$\dfrac{\nabla P_\theta(x|h)}{P_\theta(x|h)}$可以調整如下：
$=\sum_hP(h)\sum_xR(h,x)P_\theta(x|h)\nabla logP_\theta(x|h)$

以期望值來計算，調整如下：
$E_{h\sim P(h),x\sim P_\theta(x|h)}\left[R(h,x)\nabla logP_\theta(x|h)\right]$

一樣的，期望值我們只能sample：
$\dfrac{1}{N}\sum_{i=1}^NR(h^i,x^i)\nabla logP_\theta(x^i|h^i)$
* sample出$N$組的$h,x$計算
### Policy Gradient

$\nabla\overline{R}_\theta\approx \dfrac{1}{N}\sum_{i=1}^NR(h^i,x^i)\nabla logP_\theta(x^i|h^i)$
* $R(h^i,x^i)$：如果給定$h$而輸出$x$的部份是好的，那我們會希望更新參數之後，機器輸出$P_\theta(x^i|h^i)$的機率變大。
* $R(h^i,x^i)$：如果給定$h$而輸出$x$的部份是不好的，那我們會希望更新參數之後，機器輸出$P_\theta(x^i|h^i)$的機率變小。

直觀來看，好的回應我們希望它的發生機率，不好的回應我們希望愈不要出現愈好。
### Implementation

上圖說明Maximum Likelihood與Reinforcement Learning的差異，其中RL最大的差異在於訓練資料是SAMPLE出來的，藉由採樣出來的資料做訓練資料，再給每一個訓練資料一個權重，即$R(h^i,x^i)$。

事實上，我們也可以將Maximum Likelihood中加入這個項目，只是因為標準訓練神經網路的時候我們會給資料與正確答案，因此每一筆的$R(h^i,x^i)$權重我們都賦值為1。

### Implementation

實作大致流程如下：
1. 有一個Chatbot，參數為$\theta^t$，假設是seq2seq的nn。
2. 人與Chatbot溝通，即$(h^1,x^1)$，給予評分，即$R(h^1,x^1)$...共搜集$N$筆資料
3. 取得資料之後利用Gradient Ascent更新參數
* $\theta^{t+1}\leftarrow\theta^t+\eta\nabla\bar{R}_{\theta^t}$
* $\dfrac{1}{N}\sum_{i=1}^NR(h^i,x^i)\nabla logP_{\theta^t}(x^i|h^i)$
* 加總這N筆資料訓練資料，每一筆都以$\theta^t$計算機率，取$log$，取梯度，再乘上Reward，$R(h^i,x^i)$
* 利用框架的時候我們只需要定義目標函數，梯度計算就交給框架就可以了。
* $\dfrac{1}{N}\sum_{i=1}^NR(h^i,x^i) logP_{\theta}(x^i|h^i)$
4. 參數更新為$\theta^{t+1}$
5. 再做sample....

實作上，如果以亂數初始化$\theta$的話，機器一開始會胡說八道一堆，不好訓練，因此可以先以傳統訓練方式取得權重之後再開始。
### Add a Baseline

如果Reward永遠是正的，那可能會有個小問題：
理論上Reward是正沒什麼問題，上圖來看，不論是sample到那一個，它們所得的Reward皆為正數_{(綠色箭頭)}，差別只有得到的Reward大小，而Reward較小的那個選擇，它後續被sample到的機率就下降了，因此上圖範例可以看的到$x^2$的Reward相對較小，因此迭代之後它的機率也下降了。

但實際上，我們並不可能sample到所有的可能，或許你只sample到$x^2,x^3$，那被sample到的機率就上升了，而沒有被sample到的$x^1$機率就降了，因為機率總合為1，有人上就一定有人下。

### Add a Baseline

要預防上述問題的一個解法，就是將Reward減掉一個值-$b$：
$\dfrac{1}{N}\sum_{i=1}^N(R(h^i,x^i)-b)log\nabla P_\theta(x^i|h^i)$

加入baseline之後，$x^2$的Reward可能會因為較小而變為負，機率也跟著下降，而$x^3$的Reward依然上升，因此機率也上升。

Baseline-b的設置需要自己找方法，課程是由助教說明。

### Alpha GO style training!

訓練Chatbot遇到的問題就是我們不大可能整天在sample資料，因此最好的方法就是讓Chatbot訓練Chatbot。

論文的作者說明到，訓練過程中會定義幾個句子讓Chatbot互動。

### Example Reward

Reward function可以自行定義，論文上的定義如下：
$R(h,x)=\lambda_1r_1(h,x)+\lambda_2r_2(h,x)+\lambda_3r_3(h,x)$

Reward取決於三個項目，$r_1,r_2,r_3$，它們的weight為$\lambda_1,\lambda_2,\lambda_3$，三個項目都有它的定義：
* $r_1(h,x)$：Ease of answering
* 避免機器產出讓人接不下去的話，如，嗯嗯，呵呵，去洗澡。
* $r_2(h,x)$：Information Flow
* 避免機器產出重覆的句子，即這次產出的句子與上次產出的句子差距愈大愈好
* $r_3(h,x)$：Semantic Coherence
* 避免機器回頭牛頭不對馬嘴

### Example Results

左邊是未採用RL訓練的結果，右邊是採用RL訓練的結果。

未採RL的部份可以明顯的發現，很輕易的就陷入無窮迴圈的問答，雖然採RL的部份依然會進入無窮迴圈，但較慢，而且對答語句看起來似乎較佳。
### Reinforcement Learning?

Policy Gradient只是RL眾多技術中的其中一個，還有其它可以應用，如`actor-critic`
### SeqGAN

SeqGAN是一種利用GAN生成句子的方式。

### Basic Idea - Sentence Generation

使用GAN來生成句子的概念與生成影像相似，從空間中sample出一個分佈，經過Generator得到sentence-x，再讓Discriminator判斷是真的假的。

### Basic Idea - Sentence Generation

一個差別是，RNN本身已經具有隨機性，即使相同的輸入也會有不相同的輸出，因此以RNN建構的Generator不需要從空間中sample出一個樣本。
### Algorithm - Sentence Generation

演算法說明如下：
1. 有一個Generator與Discriminator
2. 每次迭代：
* 從實際資料中sample出一個句子$x$
* Generator生成一個句子$\tilde{x}$
* 更新Discriminator，讓實際資料輸出愈大愈好，生成資料輸出愈小愈好。
* 以上訓練Discriminator
* 訓練Generator的時候我們希望生成的資料經過Discriminator的輸出是愈大愈好
### Basic Idea - Chat-bot

訓練Chat-bot的時候會應用到Conditional GAN。

Chat-bot由一個Encoder與Decoder組成，輸入-$h$為句子與相關需求資訊，輸出為回應-$x$。

而Discriminator的輸入必須是成對的，因為Conditional GAN我們要知道我們輸入的資料有多麼的匹配，因此輸入的部份為$h,x$。

Disctiminator的實際資料可以爬文、電影、社群網站...等來源取得，瞭解每一個發文人們的對應為何。

### Algorithm - Chat-bot

Chat-bot演算法如下：
1. 初始化一個Generator與Discriminator
2. 每次迭代：
* 從實際資料中sample出一筆資料$h,x$
* sample出一筆資料$h'$，經過Chat-bot得到$\tilde{x}$
* 更新Discriminator，我們希望實際的資料$Dis(h,x)$的輸出愈大愈好，而生成資料$Dis(h',\tilde{x})$愈小愈好。
* 更新Generator，我們希望生成的資料經過Discriminator的輸出愈大愈好。
### Algorithm - Chat-bot

在Generator_(Chat-bot)生成資料的時候，中間有一個sampling的過程，它產生的每一個time step都是依據RNN的分佈做sample_{(上圖範例sample出B、A、A)}，將sample出來的資料經過Discriminator得到一個scalar。其中Discriminator可以是RNN也可以是CNN，只要可以輸入sequence、輸出scalar就可以。

在原始GAN中，我們可以利用反向傳播一路更新，但在這個案例中卻沒有辦法這麼做。因為反向傳播無法通過sample這段。

梯度，就是對參數做細微的調整之後對輸出的影響。但我們沒有辦法確認Generator對Discriminator的Output的Gradient。即使是WGAN，我們也只是將sampling process這部份當做沒看到，因此在WGAN中吃的輸入就是一個分佈。
### Reinforcement Learning?

不能使用反向傳播情況下，我們將這件事想成是RL的問題。我們要調整Chat-bot的參數讓Discriminator的輸出愈大愈好。因此，將Discriminator的輸出視為『Reward』。

相同的，利用策略梯度的方式，上一節課提到的優化：
* $\nabla\bar{R}_\theta \approx \dfrac{1}{N}\sum_{i=1}^N(R(h^i,x^i)-b)\nabla logP_\theta(x^i|h^i)$

唯一需要調整的就是將Reward調整為Discriminator的輸出，即：
* $\nabla\bar{R}_\theta \approx \dfrac{1}{N}\sum_{i=1}^N(D(h^i,x^i)-b)\nabla logP_\theta(x^i|h^i)$

### Sequence-GAN

使用Sequence-GAN訓練Chat-bot會有兩個step：
* g-step：
* 訓練Chat-bot
* 從空間中sample出$N$筆資料之後，由Discriminator判斷這對話有多麼真，再來更新。
* 訓練過程中凍結Discriminator
* d-step：
* 訓練Discriminator
* 利用Chat-bot的假資料與實際的對話資料來訓練判斷真假對話

### Reward for Every Generation Step

上圖範例對話，看起來就是有問題，因此經過$D(h^i,x^i)-b$得到的結果會是負數_{(上面已有說明為何$-b$)}，那我們就會希望這種對話出現的機率$logP_\theta(x^i|h^i)$愈小愈好，我們可以這麼看：
$logP_\theta(x^i|h^i)=logP(x_1^i|h^i)+logP(x_2^i|h^i,x^i_1)+logP(x_3^i|h^i,x^i_{1:2})$

$x$是一個sequence，包含了三個詞彙"i don't know"，因此拆成了三項。意思是說，要減小$logP_\theta(x^i|h^i)$的值等價於減小後面三個項目的值。

但整個句子來看，"I"並不是造成句子壞掉的主因，而是後面的"don't know"，這樣子似乎會造成"I"的機率也降低，理論上是，但實際上只要sample出的句子是以"I"開頭的好的句子多了，那機率的上升或下降就是取決於sample的過程中得到的"I"開頭的句子是好的多還是壞的多。

但這部份都取決於過程中的sample。
### Reward for Every Generation Step

我們希望可以進一步的讓機器知道在回覆的過程中那些用詞是好或不好，舉例：
* $h^i:$"What's your name?"
* $x^i:$"I don't know"

很明顯的，"don't"與"know"的出現機率應該下降，而"I"的機率應該提高，這可以透過調整梯度數學式做到，原始數學式如下：
$\nabla\bar{R}_\theta\approx\dfrac{1}{N}\sum_{i=1}^N(D(h^i,x^i)-b)\nabla logP_\theta(x^i|h^i)$

原始的式子我們對整個句子做計算，調整為對每一個詞彙計算：
$\nabla\bar{R}_\theta\approx\dfrac{1}{N}\sum_{i=1}^N\sum_{t=1}^T(Q(h^i,x^i_{1:t})-b)\nabla logP_\theta(x^i_t|h^i,x^i_{1:t-1})$
* $\nabla logP_\theta(x^i|h^i)$拆解為$\sum_{t=1}^T\nabla logP_\theta(x^i_t|h^i,x^i_{1:t-1})$
* 每一個詞彙都給一個分數$Q(h^i,x^i_{1:t})-b$
* input:$h^i$，output:$x^i$的前$t$個詞彙有多好。

有兩種方法可以評估$Q$：
1. Monte Carlo(MC) Search
2. Discriminator For Partially Decoded Sequences
### Monte Carlo Search

$Q$("What is your name?", "I")

現在，第一個字出來是"I"，評估的方式就是sample很多以"I"起始的回答，這需要一個Generator，實作中我們可以直接將Chat-bot當做這個Generator，並強迫它的第一個輸出字為"I"，後面的其它字就任由它生成即可。

接著，讓Discriminator對每一個sample出來的"I"開頭的回應評分，得到每一個回答的分數，將所有得分做平均(見上圖分別對四個生成語句評分)，得到的這個平均數值就可以做為以"I"開頭的分數。
### Discriminator For Partially Decoded Sequences

另一種評估$Q$的方式是讓機器去判斷生成一半的句子有多好。

原本我們給Discriminator是一個成對的資料，正樣本與負樣本，用這種方式讓Discriminator知道怎麼樣是好的回答，現在，我們要同步給Discriminator知道生成一半的句子跟回應一半的句子，用這種方式訓練。
### Teacher Forcing

課程開始的時候提到，不要讓Chat-bot由亂數生成的參數開始學習，這會很困難，就跟叫一個小學生計算大學的微積分一樣，這會造成生成的資料都是negative，它永遠無法生成positive的樣本。

直觀來看，除了從實際資料中sample出來的資料用Discriminator評估好壞之外，再另外的由實際資料中sample出另一堆資料，直接賦值為1，直接跟模型說這個就是好的回答。
### Experiments in paper

論文中提出一種評估的方式，Synthetic data：
1. 有一個沒訓練過的亂數生成LSTM模型
2. 由這模型生成的資料就視為是實際資料
3. 訓練一個Generator，學習上面LSTM的分佈。
4. 利用Generator生成句子
5. 利用第1步生成的LSTM計算negative log likelihood(NLL)
* 愈小愈好

### Experiments in paper - Real data

上面是論文中的比較，MLE是原始，比較唐詩、歐巴馬的演講資料、音樂等三個，看起來都是SeqGAN效果較好。
### Resluts - Chat-bot

上面是Chat-bot生成出來的狀態，Vanilla是MLE訓練，REINFORCE以句子評分，而REGS Monte Carlo是以詞彙評分。