台大資工 林軒田老師
日期: 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。