NTU

在這一講中，要介紹的是 RL 中的 supervised 系方法 - Imitation Learning。想法是收集 expert (or say, “ground-truth” agent) 與 environment 互動的$(s,a)$ pairs 去 train 我們的 agent/actor。那麼該如何利用這些 $(s,a)$ pair 呢？

Lec1 - Lec4 分別介紹了 Policy-based 及 Value-based 的 RL algorithm ，而這一講要 介紹的 Actor Critic 則是同時用到了兩個演算法的部份，並在 biased 與否 (準不準) 及 variance 高低 (好不好 train) 提供一個可以調控的 hyperparameter 讓我們選擇。

在這講中，要討論的是 non-tabular case 的問題 (就是上一講中無法保證收斂的那些QQ)，我們選定 Neural Network 作為拿來 approximate $Q(s,a)$ 的 function family，且不是用一般 regression 的方法找 $\phi$ (畢竟它的 target $y$ 也只是中間產物，並非 optimal Q)，而是 N-step 的 gradient descent。

前兩講 focus 在 policy-based 的 RL 演算法，直接 learn 一組參數去 parametrize policy。而後續兩講則會 focus 在 value-based 的方法，想法是算出 $V^\pi(s), Q^\pi(s,a)$ (同樣可以 approximately parametrized by $\theta$)，而所對應的 policy 則是去選擇 Given $s$，好度最高的 action $a$ (w/ appropriate exploration)。

上回提到了 policy gradint 的方法，及其缺點，這一講會介紹各種改進的方法。包括降低 sample 的 variance 及 off-policy (使得 data 更有效地被利用)。

今年1 月的目標想複習三下時學的 RL，主要的參考教材為李宏毅老師的 DRL 8 講及 Sergey 在 Berkeley 開的 CS294。

先讓我們從 Policy Gradient 開始吧！

前一講提到了無論是 stochastic noise 或是 ground truth 過複雜而引進的 deterministic noise ，對本身就複雜 (VC dimension 高) 的 model 而言，overfitting 是很容易發生的，而解決之道其一就是這一講所要介紹的 Regularization。

上一講提到了利用 nonlinear transform 來處理 data 並不 linear separable 的情形，讓 ML model 具備了更強的 fitting 能力，但在這麼做的同時，也提高了 hypothesis set 的 VC dimension，使得 model 的 complexity 增加，變得不容易 generalizaion ，而這也是這一講要探討的 overfitting 。

ASR 做的其實就是以下這件事，

$$ \Pr(\text{words|sounds}) = \frac{\Pr(\text{sounds|words})}{\Pr(\text{sounds})} $$

當中我們視 $\Pr(\text{sounds})$ 為 uniform distribution ，不管它。 \
$\Pr(\text{words})$ 由 Language Model 負責，評估產生的 transcription 之合理性 (e.g 電腦聽聲音 vs 點老天呻吟)\
$\Pr(\text{sounds|words})$ 則是 Acoustic Model， 也就是前一講中用 Viterbi 所算的 Likelihood 。

我覺得自己之前做的投影片真的蠻好的XD (自己講)，因此這一講中，只會偏重在原本寫的比較簡略的 Learning Problem ， Evaluation 及 Decoding Problem 僅會附上程式碼及做定義。

在能夠將聲音訊號轉為數值向量給 machine 處理後，我們要怎麼判斷這串 vector 是 mapping 到哪一段文字呢？ \
在進入 continuous ASR 前，讓我們先來想一想怎麼辨識一個 word ？想法是針對這個 word 建一個 model ，給定一段聲音訊號， output 該訊號 map 到此 word 的機率為多少。

在此之前，針對 linear separable 的 data ，我們利用找可以切分這些數據點的 hyper-plane 來做 classification (或 regression )。但這個強大的假設並不適用於每筆真實世界中的 data ，所以我們勢必得處理 non-linear 的問題。換句話說，我們希望 hypothesis set 中可以包含更多的候選人（可以 match nonlinear 特性的那些 function ），同時去驗證在這樣的情況下，學習依然是可行的。

總結目前學到的 3 個 linear model。

Linear Model 的核心在於 feature 分量的 weighted sum $\mathbf{w}^T \mathbf{x}$， 在 binary classification ，我們用 step function 將其二分 ($\mathcal{Y} = \lbrace , -1,1,\rbrace$)，而在 linear regression 中，我們將其直接作為輸出。而這一講要介紹的則是將 $\mathbf{w}^T \mathbf{x}$ 通過一個 nonlinear function mapping 到[$0,1$]，賦予他機率的意義 ($\Pr[y = +1 | \mathbf{x}]$)。

在前幾講的討論中，我們討論了 binary classification 的問題，及這個問題在機器學習上的可行性。但很多時候，我們不希望機器只會說是或不是，亦即不希望它的 output space $\mathcal{Y}$ 只是單純的 {$1, -1$}。舉例來說，給定一些資料，請你預測明天的股價，除了想預測會漲或會跌之外，到底漲多少或跌多少也是我們有興趣知道的事情，而這也是接下來兩講想解決的事情 - Regression。

上一回介紹了 LPC ，來做為我們抽取 feature 的一個方法，今天要來談談目前最常被使用的 feature - MFCC 。

語音辨識的基本架構中，第一步便是要把聲音訊號轉成可被紀錄的數位形式以供 machine 處理。科學家們從人類究竟是如何發出特定聲音作為出發點，去找出訊號當中哪些是屬於那個聲音 unique 的 feature，並移除那些無關的資訊 (e.g noise) ，並利用這些 extract 出來的 feature 來作為辨識的基本元素。

隨著變成菸酒生的日子逐漸逼近，最近開始重追尤達大師數位語音的連載，希望在進 Speech Lab 之前，將這些知識掌握地更加純熟，這個系列主要會雜揉以前在台大所修的 數位語音處理概論 以及在 KTH 所修的 Speech and Speaker Recognition 之相關內容。

前面幾講的討論中，我們都假設有一個 ground truth function $f$ 去 generate data，且我們所拿到的 $\mathcal{D}$ 是乾淨的，然而在真實世界中，無可避免地會遇到 noise 加在 data 上，如此情況下 learning 是否還是可行？ (VC bound 是否還是 work ?) 另外，前方討論時，我們都以 0/1-error 作為衡量 model 好壞的 metric，如果換成不同的 metric 呢？

於前一講中，我們證明了 growth function 為 POLY(N) iff break point 存在，而這件事可以說明在 training data 上的表現不會和 testing data 差的太多 $E_i(h) \approx E_o(h)$ (if 數據點夠多 $N$ )。而這一講中，我們由 break point 引進 VC Dimension $d \scriptscriptstyle VC$ ，來當作衡量 $\mathcal{H}$ 複雜度的一個指標。

前一講中講述了 break point 的存在，壓制了 growth function $m_H(N)$ 的成長速度，於這一講中，我們想嚴格地說明只要存在 break point ，$m_H(N)$ 便會是 POLY(N) 。

上一講提到了在 hypothesis set $\mathcal{H}$ 為有限，且sample size $|\mathcal{D}|$ 足夠大的情況下，是 PAC-learnable 的。但當 $|\mathcal{H}| , \rightarrow , \infty$的時候呢？ (e.g 2D linear perceptron)

這一講要討論的是機器學習真的是可行的嗎？能推廣到所有 scenerio 嗎？或是只有部份？是否需要某些假設才能證明可行呢？

這講建構了一個大略的 ML 世界觀。

於前一講講述了 ML 的 framework ，於這一講中，我們會利用一個簡單的 learning model ， 去解決 binary classification 的問題。

其實是大一升大二的暑假，閒來無事找的開放式課程，那時也做了一些筆記，沒想到兩三年過後，自己做專題也走向了這個領域XD，於是順手把它整理上來囉！

在 第一講中，我們證明了有很高的機率，任意 slot 中 element 的個數均為 $\mathcal{\Theta}(\frac{\ln n}{\ln (\ln n)})$ ，而這一講想討論的是，如果今天我們手上有兩個 hash function (from same $\mathcal{H}$)可以選，每次我們就看哪一個 $h$ 回傳的 slot 中元素比較少，就將 element hash 到 slot，那麼現在 $\mathbb{E}[, \text{max num of elements in any slots} , ]$ ?

Hashing 的一個 criteria 是希望儘可能不要發生 collision (也就是 Worst Case 也在 $\mathcal{O}(1)$ lookup)，今天假設我們已知元素的個數，該如何設計一個 hash function 使得不會有任何 collition 發生？

前面提到過一個較為複雜的優化問題， Metric Facility Location Problem ，並給出了一個 4-Approx. Algorithm ，於這講中，我們要來利用前面提到的 Primal-Dual method 來設計演算法。

呈之前的討論，對於 WSC 問題，我們有了利用 LP solver 去對解做 deterministic rounding 及 randomized rounding 的演算法，解法的共通點是必須要先 run 過 LP solver (雖然理論上是 POLY ，實務上現行的 solver 也很有效率)，但我們仍想問說，是否存在不須使用 LP solver 的演算法呢？ 而這也是這講所要提到的 Primal-Dual Method 。

接續前面幾講，一個常用的技巧是，利用 LP solver 得出來的解 $\mathbf{x}^{\star}$， 拿去做 rounding 推出原先問題的解 $\mathbf{x}^{\prime}$ (with 一個還不錯的 approx. ratio)。而這講會講述一個較為複雜的問題 - Metric Facility Location Problem (MFL)。

前兩講討論的是給定起點，問到其他點的最短距離，稱為單源最短路徑問題，而現在我們想考慮 $V$ 中兩兩點對彼此間的最短距離，又稱全點對最短路徑問題。

呈前一講的討論，我們有了個求單源最短路徑的演算法Bellman-Ford (複雜度為 $\mathcal{O}(VE)$ )，現下我們考慮額外的限制條件(邊權重為非負)，想找出是否存在更有效率的演算法

圖的一個常見應用場合是想找出某兩點之間的最短(/長)路徑，此時的邊權重又視為兩節點之間的距離。

給定一張圖，要如何讀取當中的資訊呢？簡單來說就是從一給定點開始，依某種順序去拜訪相鄰(有關係)的點，最後走完所有點，收集完圖中的資訊。以下簡介兩種簡本的 traversal 方法以及應用。

Disjoint Set 顧名思義，代表了一群兩兩交集為空的集合們，常用於處理依據某種關係將元素們「分類」的問題。我們的目標是去 maintain collection of disjoint sets $S_1,S_2,\cdots,S_k$，而每個 $S_i$ (每個 category) 以一個代表值 (representative) 去紀錄。

呈前一講，我們對有限制的 WSC 問題有 $l$-approx. algorithm，但可能並不是太好(比方說 $l=|U|$ 之類)，於是我們嘗試引進一些隨機性，雖然犧牲了 deterministic 的 approx. ratio ，有時候甚至會得到更爛的結果(甚至不滿足 constraint @@)，但可以證明在大部分時候，都可以得到一個還不錯 (approx. ratio ISN'T too bad)的結果。

這一講會展示將問題轉化為線性規劃的 form (但可能是 ILP)，利用 LP solver 得到解，做 LP relaxation 並證明這個解不會太差 (approx. ratio 不太大)。

**Definition:**
A linear programming is a problem of maximizing or minimizing a linear multivariate function subject to some linear constraints

從前兩講關於分配 (在一堆物品中，決定哪些是要拿的一群，哪些不拿) 的最佳化問題中，我們延伸出新的問題，Bin Packing Problem。不同於在 Knapsack Problem 中，我們只有一個箱子(可以想成你聘了一個工人搬一個箱子)；在Bin Packing 問題中，要取走所有寶物(所有寶物的重量都小於 1 單位)，而你需要聘請一些工人來搬，但今天每個工人都只帶了一個負重為 1 單位的箱子，該如何分配這些寶物(雖說是寶物，但其實我們不care價值惹)，使得需帶的箱子(聘請的工人)為最少？

簡單的 formulation 如下：

Subset Sum Problem 與 Knapsack Problem 相同，也是一個 NPC 問題(可以想成 Knapsack Problem weight 均為 1 的特例)。而在 Knapsack Problem 中，我們發展出等差 的rounding 技巧，犧牲精確度去換取更低的時間複雜度，而這一講中，將利用等比的方式去做 rounding 。

背包問題為一個典型的最佳化問題，想像你來到了一個寶庫，裡頭有一些寶物，都有各自的價值和重量，但你只帶了一個背包(而且負重還有限制)，要怎麼取寶物才能在背得走的前提下，帶走價值總和儘可能高的寶物們呢？

這裡我們考慮最基本的 0/1 - Knapsack Problem 。簡單的 formulation 如下:

Hashing 可以想成是一種 renaming 的方式，原先的名字 (key) 可能很長，但可能的組合並不完全隨機，且數量相對整個宇集少上不少，若我們要建立一個跟宇集一樣大的 Hash Table 並不符合成本(且大部份 slot 是空的)，所以想透由 Hashing 的方式，重新命名 key’ ，並依據 key’ 將資料放到 size 跟資料個數差不多的 Hash Table 中。