Basic Probability Theorem

Bernoulli Distribution vs Binomial Distribution

• Bernoulli 事件只有兩種結果，且發生某一事件機率p的分佈
• Binomial 事件有兩種結果，且發生某一事件機率p，發生x次，在全部n次實驗中的機率分佈
• X~BIN(10,0.6)：事件在10次實驗中，成功機率0.6，X次成功的機率分佈

Geometric Distribution

• 事件機率已知p，事件在第x次才發生事件的機率分佈：(1-p)^(x-1)*p：有點像等比級數（幾何級數）
• 失憶性

Pascal Distribution

• 事件機率已知p，事件在第x次才第k次發生事件的機率分佈：
  C(x-1)取(k-1)*(1-p)^(x-k)*p^k
• X~Pascal(k,p)：事件在X次的實驗中，成功的機率p，成功k次的機率分佈
  
  
  P(X<=x) = P(Y>=k)

Posson Distribution

• 已知頻率lambda，時間T後，發生x次的機率分佈
  
  可由Binomial(n→無窮大)來推導

• 題目：
  有三個門A, B, C，其中門後有一台車，小明選中門後有車，就可以把車帶回家！
  今天小明選了A門後，主持人開了B門（空的），問小明換還是不換？
  答案：
  ！！！！換！！！！
  認為最直覺的想法：你最初選車的機率為1/3，車在另外兩個門後的機率為2/3，主持人選羊以後，車在最後那張門後的機率還是原來兩張門後有車的機率，2/3。

Machine Learning-3 Types of Learning

TOPIC

• 除了是非題（二元分類），機器學習還有哪些種類。

Learning Target

• Multi-class Classification Learning
• Regression Learning: output as real number
• Structure Learning: output as structure (huge classes without explicit class definition)
  (舉例像是語音辨識，語音之間就含有隱藏不明顯的關係，是一種structure)
• ...

Learning Type

• Supervised Learning 監督式: all y
  - 全部資料都有標記。
  eg: classification(分類), ...
• Unsupervised Learning 非監督式: no y
  - 沒有資料有標記。
  eg: clustering(分群), density estimation, outlier detection, ...
  (目標較分散，較難衡量好壞)
• Semi-Supervised Learning 半監督式: some y
  - 小部分資料有標記。(可以省下很多標記成本)
• Reinforcement Learning 強化學習:
  - 透過 reward/ punishment來訓練機器: implicit y
  (learn with implicit information, 通常是一個序列/過程)

Learning Method

• Batch Learning
  - 一組資料一次學習完 (常見作法)
  (duck feeding)
• Online Learning
  - 一筆一筆新資料修正的學習
  (passive sequential)
  eg: email filter, reinforcement learning
• Active Learning
  - 標記成本很高的狀況下，希望透過機器主動問問題，減少資料的需求量。
  (question asking)
  eg: "選擇性的"找出驗證老鼠癌症最好的實驗方法。

Features

• Concrete Features
  含有人類智慧預先處理過得輸入資料，對於機器來說是較容易學習。舉例如下：
• 錢幣分類（大小、質量）
• 信用卡評估（客戶資訊）
• Raw Features
  含有最原始的物理意義輸入資料，對於機器來說較難學習。
• 所以獲取好的Concrete Feature是非常重要的議題
• 透過深度學習
• 透過專家設計
• Abstract Features
  沒有物理相關意義的輸入資料，抽象的輸入對於機器來說非常難學習。舉例如下：
• 評分預測（使用者id, 項目id, 分數）
• 以上三種常常會一起出現舉例如下：
• 推薦廣告系統
• Concrete→使用者資料
• Raw→推薦的圖像廣告
• Abstract→使用者編號，廣告編號

REF

Types of Learning :: Learning with Different Output Space @ Machine Learning Foundations

Machine Learning-2 Learning to Answer Yes/No

Perceptrons Learning Algorithm (PLA)

• 就是一種 linear (binary) classifiers （二分學習演算法）

How

• IDEAS: 我們無法一開始就知道正確的hypothesis function g，於是就先找一個g0當作起點，過程不斷透過犯錯的資料來調整，直到錯誤減少到一定程度。
  （A fault confessed is half redressed - 知錯能改善莫大焉）

一定會收斂媽

假設是線性可分的狀況下，確實會收斂

證明：

• 但現實問題中，即使是線性的，資料中也會有雜訊(noise)導致問題變成非線性。可用Pocket PLA來嘗試解決（把最好的留在pocket，但會比PLA慢，因為多了比較的動作）

REF

Learning to Answer Yes/No :: Perceptron Hypothesis Set @ Machine Learning Foundations

Dynamic Programming

Dynamic Programming

• DP 
• Careful Brute Force
• Sub-problems + memorization + Reuse + guessing
• Must be DAG (Directed Acyclic Graph)

Fibonacci Example

假設想求取F(n)，過程中F(n-3) 會重算兩次

→直覺的想法就是算了第一次以後存起來，以後可以直接用，不用在往下算。

• Recursive想法：
• T(n) = T(n-1) + T(n-2) +T(1)
  >= 2(T(n-2))
• Time = O(2^(n/2)) exponential time cost
• DP想法：
• 只需要把F(1),F(2),...,F(n)每個都呼叫一次，且每次只需要O(1) constant（把兩個子問題相加）
• Time = O(n) linear time cost
• Bottom-Up (實際運作時可以省下很多function call，因為沒有recursive只有loop）

REF:

Dynamic Programming I: Fibonacci, Shortest Paths

[C++] Passing Pareameters

C支援Call by Value和Call by Pointer，C++多一個Call by Reference

Call by Value

• int main() { 
•     int x = 5; 
•     foo(x); 
• }
• void foo(int x) { 
•     x++; 
• }

在"foo中的x"和"main中的x"是分開的兩個記憶體空間。

Call by Pointer

• int main() { 
•     int x = 5; 
•     foo(&x); 
• }
• void foo(int *x) { 
•     (*x)++; // 指向，並加1 
• }

把變數的Reference傳入，foo的*x會指向這個Reference，共用同一快記憶體空間。

Call by Reference 

（C++新增，作用和目的雷同Call by Pointer，但在撰寫程式碼的時候方便很多，只需要在接入時多加一個&即可，特別注意int& xx; 是不行的，會出現 error: ‘xx’ declared as reference but not initialized，這個用法必定要被初始化。）

• int main() { 
•     int x = 5; 
•     foo(x); // 不用加& 
• }
• void foo(int &x) { 
•     x++; // 修改此x就是修改main的x 
• }

把變數傳入，foo的&x會指向這個變數的Reference，共用同一快記憶體空間。

Machine Learning-1: The Learning Problem

When can machine learn:

• 有資料
• 沒有明確定義的函式 (有的話就直接寫死更快不用學習了）
• 有可能的pattern （存在潛在的規則）

A takes D and H to get g

Target to learn from ML:

• target function f: 未知，理想的data→label函式
  (如果已知，就不用機器學習了）
• hypothesis function g: 機器學習目標，"盡可能"接近f

Terms:

• Data Mining vs Machine Learning
• DM: 尋找大量資料彼此之間的關係，供給人類參考依據。
• ML: 尋找Hypothesis Function模擬預測資料和答案皆的關係。
• 兩者其實密不可分，但傳統的DM還會研究如何有效的計算管理大量資料庫。
• Artificial Intelligence vs Machine Learning
• ML是實現AI的一種方式
• Statistics vs Machine Learning
• S是實現ML的一種方式
• 傳統的S比較注重在數學公式的推導，但對實際計算方式探討較少。

REF:

Machine Learning Foundations by Hsuan-Tien Lin

Perceptual Generative Adversarial Networks for Small Object Detection

20160621_Perceptual Generative Adversarial Networks for Small Object Detection

Basic CS Algorithm Review

• Quick Sort
• 直覺想法：
  divide and conquer
• divide:
  一個陣列輸入，透過pivot來分三類：
• 小於（丟進子問題排序）
• pivot
• 大於（丟進子問題排序）
• conquer:
  把上述三類合再一起
• return:
  當子問題輸入的陣列長度小於等於1 (不用再排序了，所以回傳)
• 平均複雜度：Ｏ(nlogn)
  每個點走一次和pivot比較大小 -> n
  binary divide and conquer -> logn (樹的深度）
• code：

數位廣告相關的各種名詞

• RTB (Real Time Bidding)
  針對到訪的客戶，進行特徵分析，然後判斷出是什麼樣廣告的目標，進行有效率的廣告投放。
• 是一種win-win-win：
• 消費者：買到想要的
• 廣告主：'有效'行銷廣告
• 媒體：成本降低，有效販售廣告
• AD Exchange
  媒體提供廣告，AD Exchange是媒合廣告主的平台，用勁價方式媒合。
• DSP, Demand Side Platform
  提供給廣告主的平台，分析各種廣告的效益，協助廣告主更好的投放廣告。
• SSP, Supply Side Platform
  提供給各媒體的平台，、讓媒體可以更好的賣出廣告。
• DMP, Data Management Platform
  整合行為數據的技術平台，可讓投放廣告更精準。
• Retargeting
  把原本錯過得客戶，讓他在其他網站看到廣告，被拉回來消費。
• 個性化retargeting（藉由瀏覽的內容，分析客戶的喜好）
• 商品retargeting（分析客戶單一方品，投放類似商品）
• 購買車retargeting（分析客戶已經'想'購買的清單，透放廣告）
• 投放目標：
• 來過得人
• 把商品加入喜愛、購物車清單的人
• 一段時間沒來的人
• 客戶屬性：
• 人口：性別、地區、來源
• 行為：購物車、新註冊、入站次數
• 興趣：3C、汽車、旅行

Ref:
數位廣告大智慧

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

Word Embedding

Why

機器只懂0和1，看不懂單字，如何'有效'的表達單字變成解決目標。

What

大概常見的方法：

1. one of n
   就是所謂one hot vector [0, 0, 1, 0, ..., 0]，每個維度表示不同單字。
2. counting-based
   去計算單字出現的頻率來編碼
3. prediction-based
   去計算前後文出現的機率來編碼 
1. 直覺
   舉例兩個句子，'蘋果' '很甜'，'鳳梨' '很甜'，'蘋果'和'鳳梨'編碼後的結果應該會非常接近，因為他們後面接的單字都是 '很甜'
2. 作法
   可透過NN來實作，舉例input X是one of n vector，output是該X前後文單字的one of n vector，training後，NN其中的hidden layer取出，當成encoder。之後任何的單字都可以透過該hidden layer來進行編碼）