Structure Learning

(Energy-based Model/ Structure SVM/ Graphical Model/ Hidden Markov Model)

Why: 

因為我們在某些狀況下，input和output都是object (Tree, list, bounding box...)

（舉例: 翻譯，語音辨識，物件位置辨識，語意歸納）
這個時候我們就無法用一般DNN分類的概念來處理。

How:

• Unified Framework
  
  
  直覺想法：找一個F比較兩個物件X, Y之間的對應性。

1. 一般deep learning的概念：
   找一個 f，輸入x，輸出y
2. 用structure learning的想法來思考deep learning：
   f 會窮舉找出對應性F(X,Y)最高的一個結果，就是輸出y。
   (Deep Neural Network可以想成Structure Learning的一種特例，如下圖的Cross Entropy)
   
   原來也可以把Cross Entropy看成Structure Learning尋找到的F，照這個思路理解，很多object to object的應用，都有對應特別的loss function，想必和Structure Learning有很大的關聯。（像是語音辨識使用的就是CTC loss function，Single Shot Detection偵測bounding box也是使用特別的loss function結合Intersection over Union來計算）

• GAN其實和Structure Learning很有關係，也和Deep Learning越來越有關係。

需要解三個問題：

1. F怎麼定義
   
   φ: feature
   通常比較新的作法會使用DNN來決定這些feature
   （bounding box detection其實就是DNN + Structure Learning）
2. 窮舉y來比較作的到媽
   根據不同的目標，互有不同的方法來窮舉，舉例object detection，就可以用selective search（FRCNN）或anchor boxes（SSD） 來解決。
3. F要怎麼獲得
   其實目標就是要找到W來滿足所有的training data，讓正確的y比其他窮舉出的y值還大。和binary perceptron learning很像，透過不斷修正錯誤預測來更新W。

• Formula
  
  
  定義好delta也是重要的問題，以上圖為例，找到背景應該要比找到人還差，遠離目標要比靠近目標差，上圖的狀況可以用IOU（intersection over union）來解決。
  經過改寫後，原本的式子會有上圖 特性：
  weight 內積（特徵答案 - 特徵其他）>= 定義差異 - slack margin(可接受的範圍)
  （跟SVM公式一模一樣，是個quadratic programming Problem）
  但由於太多condition要同時去optimize，通常會使用Cutting Plane Algorithm來解決。

What:

• state of the art method: 利用DNN來抽取出non-linear的feature給Strucure SVM來同時學習！

Sequence Labeling

• HMM: Hidden Markov Model
• 直覺想法：
  就是藉由統計資料中的相互關係，找出讓 P(x| y) 機率最大的y值。
• 優點：簡單易算
• 缺點：會根據training資料腦補預測結果，可能在training看過答案，卻在predict的時候因為其他非答案的training資料，導致預測錯誤。
  （但在training data少的時候，performance會比較好，比較不會overfitting?!）
  （可以用更複雜的HMM來解決->可能會overfitting）
  （CRF可以解決）
• CRF: Conditional Random Field

Ref:

李宏毅老師 - ML Lecture 2015