Week5

Feature selection task 

• 若在做prediction時weight的數目超多，這樣要花大量的時間來運算
• 若weight的數量很少(sparse)，只計算weight不為0的，這樣就有比較好的efficiency
• 另一方面來說，只加入真正跟prediction有關的feature也比較具有代表性(Interpretability)

Option 1: All subset

• 從選擇0個Feature開始，一直到8個全選，每次都找出最小的RSS組合

• Complexity:
• 假設有D個Feature
• 總共要計算的model數量為2的D+1次方 (因為包含constant)

Option2: Greedy algorithms

• 和All subset類似，差別在於每選完一個數量的feature，選下一個數量的時候必須包含先前選的

• Complexity
• Steps:
• 選0個1次
• 選1個D次
• 選2個D-1次
• ...
• 選D個1次

Regularize

• 選擇Feature的時候使用regularization
• 從full model開始(選擇所有feature)
• 把某些coefficient shrink到0
• 非0的coefficient代表所選擇的feature
• 設定一個coefficient的threshold，小於threshold的coefficient就shrink為0

• Lasso regression

• Coefficient path
• Ridge
• 就算𝛌很大，coefficient還是很小但不會是0的值

• Lasso
• 可以看到𝛌還沒有到很大的數字時，就已經有好幾個coefficient被shrink為0了

Fitting the lasso regression model (for given 𝛌)

• 由於絕對值wj無法微分，所以沒辦法算出lasso regression的closed-form solution

• Coordinator descent

• 對Feature做Normalize

• Coordinate descent for unregularized regression (for normalized features)

• Coordinator Descent演算法

Coordinate descent for lasso (for normalized features)

• 演算法:

• Threshold即為-𝛌/2到𝛌/2之間

• 怎麼決定演算法是否收斂完成
• 對Convex Problem來說，step會越來越小
• 統計每次loop所有Feature的step
• 當最大的step < 𝛆時就代表收斂完成