台大資工 林軒田老師 日期: 2015/11 How can machines learn? # Lecture 9: Linear Regression linear regression hypothesis: h(x) = w^Tx 不像 perceptron 不用取正負號，輸出實數 誤差叫 residuals 餘數 E_in(h) = 1/N sum( h(x_n) - y_n )^2 E_in(w) = 1/N sum( h(w^Tx_n) - y_n)^2 怎樣讓 E_in(w) 越小越好? E_in(w) 是 continuous, differentiable, convex 連續可微分函數 如果要谷底的話，梯度會是0 (微分) task: find W_LIN 使梯度 E_in(w) = 0 if invertible X^T X W_LIN = (X^TX)^-1 X^T y ------------ 叫做 pseudo-inverse X 通常成立因為 N >> d+1，所以自由度夠高讓 X 有反矩陣存在 if sigular X^T X 有很多 optimal 解 要找 pseudo-inverse X 怎麼定義跟求出來 實務上，直接用工具提供的 pseudo-inverse X 數值解來計算(就不考慮有沒有反矩陣了) analytic (closed-form) solution 算是機器學習演算法嗎? 計算反矩陣其實是 iterative 的，也是學習的過程 if E_out is good, 就是有學到東西 計算 E_in 的平均 == to be shown == noise level (1 - (d+1)/N ) y hat = X W_LIN Hat Matrix: project y to ^y 2 span trace(I-H) = N - (d+1) N 個自由度的向量，投影到 D+1 維的空間，餘數最多 N-(d+1) 這麼多 E_in(W_LIN) = 1/N || y - yhat || ^2 = 1/N || (I-H) noise || ^ 2 = 1/N( N - (d+1) ) ||noise||^2 E_in 平均 = noise level ( 1 - (d+1)/N) 這是看到的東西，所以減掉雜訊變比較準 E_in 平均 = noise level ( 1 + (d+1)/N) 相反，會比較不準，所以加上雜訊 The Learning Curve (圖3.4) expected generalization error 是 2(d+1)/N 拿 linear regression 處理 binary classification 可以嗎? yes 最大差別在 err 計算方式 err_0/1 <= err_sqr 因此只要 err_sqr 夠低，也可以 bound 住 err_0/1 實務上，可以先拿 linear regression 算出來的 w 當作 PLA 的 w_0 來加速 PLA 演算法 # Lecture 10: Logistic Regression 想算出風險、機率、可能性，又叫 "soft" binary classification target function f(x) = P(+1|x) 屬於 [0,1] 但輸入資料跟做 hard binary classifiation 一樣，只是 target function 不同 用 logistic function 把 score 轉成 estimated probability h(x) = theta( w^T x) theta(s) = e^s / (1+e^s) = 1 / ( 1 + e^-s ) theta(-無限大) = 0 theta(0) = 1/2 theta(無限大) = 1 怎麼定義 err = ? g = argmax likehood(h) 從 h 裡面找機率最接近 f 的 找 likelihood of logistic hypothesis 機率的最大值 用 ln 把連乘的公式變成 sum，而且希望把問題變成找最小值 推倒出 min 1/N sum -ln theta( y_n w^T x_n) min 1/N sum ln( 1 + exp(-y_n w^T x_n) ) 就叫做 => min 1/N sum err(w, x_n, y_n) 這一段就是 E_in(w) 下一步是如何找 w 讓 E_in(w) 最小: E_in(w) 是一個 continuous, 可微分, convex 有谷底的函數 做微分推導...... 求梯度 = 1/N sum theta(-y_n w^T x_n) (-y_n x_n) = 0 (看成用 theta 當權重，把資料點加起來) 但這是非線性方程式，沒有 closed-form solution 要用 iterative optimization 來解 Gradient Descent: w_t+1 <- w_t + (step size)*(direction v) 其中 v (泰勒展開)近似於 - ( 微分(w_t) / ||微分(w_t)|| ) step size 太小逼進會 too slow step size 太大會 too unstable 用 changing step size，坡度大 step size 大, 坡度小 step size 小 fixed learning rate logistic regression algorithm 1. 計算 微分E_in(w_t) 2. w_t+1 <- w_t - purple * 微分E_in(w_t) 直到接近0或迭代夠多次 # Lecture 11: Linear Models for Classification linear classification 是 NP-hard 問題 Q: 可以用 linear regression/logistic 替代嗎? 是不是好的方法來解 classification 問題? 當 y 屬於 {+1, -1}，推論和統合三種 err function 方便比較 ys 可看成 classification correctness score 0/1 error: 1 iff ys <= 0 sqr error: large if ys << 1, but 過大 if ys >> 1 這不好 small err_SQR -> small err_0/1 small err_CE <-> small err_0/1 不錯 通常 scale err_CE 讓 ys=0 時對齊 err=1 (透過取 log2) 讓後續推導比較方便 因為 err_0/1 <= err_SCE = (1/ln2)err_CE 所以 logistic/linear reg 可以用來作 classification linear regression: pros: easiest optimization, cons: 當 |ys| 大時，bound 很寬鬆 logistic regression: pros: easy optimization, cons: 當 ys negative 很大時，bound 很寬鬆 PLA: 如果 separable 的話，一切非常美好。用 pocket 好處就小了 實務上，用linear regression 先找 w0，在用這個 w0 跑 PLA/pocket/logistic 實務上又偏好 logistic regression 勝過 pocket，因為比較好做最佳化 Stochastic Gradient Descent (SGD) 本來的 logistic regression 算法是 O(N) time per iteration 如何改進到 O(1) time per iteration? 改用隨機梯度 Stochastic Gradient 來下降，而不是真實的梯度 pros: simple & cheaper 適合 big data 或 online learning(資料是一筆一筆來) cons: less stable in nature 比較不穩定 w_t+1 <- w_t + (step size) * theta( -y_n w_t^T x_n) ( y_n x_n) 發現其實很接近 'soft' PLA 更新公式 實務上的問題: 1.怎麼決定 stopping 條件? 2. step size 怎麼決定 1. 只能相信說跑久一點 2. 經驗上 step size 用 0.1 fun time: SGD 用在 linear regression 上也可以: 2(y_n - w_t^T*x_n) * x_n Multiclass via Logistic Regression 怎麼做選擇題? 應用: recognition 辨識(聲音、視覺)的問題 方法一: 多少類別就各做一次 binary classification 有些區域很確定是哪一種分類 但有些區域會有重複可能有兩種分類，或是都沒有的，怎麼辦? 方法二: 用 softly 方式計算每種分類的可能機率 然後選分類機率最大的 又叫做 One-Versus-All (OVA) Decomposition 演算法: => 對每個類別跑 logistic regression，選 g(x) = argmax ( W_k^T x ) pros: efficient, 可用任何 logistic regression-like approaches cons: often unbalanced D_k when K large 當 K 很大，在資料會很歪斜的情況，表現會不好。因為每個分類算出來的機率都很小，差異不大 統計延伸版: multinomial (coupled) logistic regression (機率加起來是1，更漂亮) 實務上 OVA 是很常用的方法 Multiclass via Binary Classification Q: 怎麼解決上述資料 unbalance 的問題? (當K很多時，是A和非A就會很懸殊)，怎麼解決? A: 改成 one versus one，挑兩個分類對比(pairwise)計算，也就是 C K 取 2 種對比 (k=4 的話，會有 6 種對比) 把每個對比的結果當作投票，看哪一種分類最多人遠 One-versus-one (OVO) decomposition 演算法: g(x) = tournament champion{ w^T x } (voting of classifiers) pros: efficient (雖然對比變多，但是每次需要的資料量也比較小), stable, 可用任何 binary classification approaches cons: use O(K^2) 需要更多 space, slower prediction, more training 需要資源 實務上，當 K 沒有非常非常大，還蠻好用的 fun time: 算 OVO 的 big(o)，此範例如果用 OVA 反而比較差 # Lecture 12: Nonlinear Transformation 非線性變換 二次方 Quadratic Hypothesis Q: linear 的優點是複雜度 d_VC 受限，缺點是有些 data 不管怎麼切，E_in 都很大，那要怎麼辦? 把每個點都平方變成 z 世界 h(x) = sign( w0 - w1x1^2 - w2x2^2) = sign( w^t z ) { (xn, yn) } 如果是 circular separable => { (zn, yn) } 是 linear separable 這個把 x 變成 z 過程叫做 (nonlinear) feature transform (1, x1^2, x2^2 ) 變成 (z0, z1, z2) lines in Z-space <-> special quadratic curves in X-space 上述仍有限制，對應回 x-space 仍沒有包含所有的二次曲線(圓形、橢圓、二次曲線、常數) 如果要全部的需要把一次項也加上去: general quadratic hypothesis set a bigger z-space (1, x1, x2, x1^2, x1x2, x2^2 ) 當然也包含直線和常數 Nonlinear Transform 怎麼作? 1. feature transform: 把 original data {(xn,yn)} 轉換成 {(zn,yn)} 2. linear model: 用 linear classification algorithm 取解 z 空間的 w 從此可以作二次項，甚至可以作三次項、多次項 feature transform 是 ML 的原力 the force fun time: 假設要作二次項變換在 d 維度上，最後總共有幾項? d^/2 + 3d/2 + 1 Price of Nonlinear Transform 代價是什麼? 代價一: Computation/Storage Price: 假設 Q 次 polynomial transform，會有 O( Q^d ) 這麼多項。當 Q large 時，會很難計算 代價二: VC 複雜度也增加了，但仍有上限限制。 Q large => large d_vc generalisation issue: 會有 trade off: 如果 Q 大: E_in 跟 E_out 差距大，但 E_in 小 如果 Q 小: E_in 跟 E_out 差距小，但 E_in 大 小心挑過的特徵變化，也就是你自己先 human learning 挑過 feature 後，再用 machine learning fun time: 計算代價 d = (Q+2 取 2) -1 ) Structure Hypothesis Sets structure: nested H_i 的從屬結構 H0 < H1 < H2 < …… d_vc(H0) <= d_vc(H1) <= …… E_in(g0) >= E_in(g1) >= …….. 這就是我們之前看過的圖。model complex 高，E_in 雖然很低，但是真正的 error 其實很大。雖然一開始不會從高維度開始做 => 先從低維度開始作，如果 E_in 足夠小，那就很棒 如果 E_in 不夠小，才開始提高維度。因此 linear model first。