Least Square with Regularization

by allenlu2007

本文參考 Kim’s “An Interior-Point Method for Large-Scale L1-Regularized Least Squares

 

先說結論:

Least square with regularization primal problem 如下 (一般 n < k, overfit)

NewImage

where A is fat matrix.  dim(A) = n x k;  dim(x) = k x 1;  dim(b) = n x 1

如果 n > k, underfit 也行,不過不大 make sense.  因為已經 underfit.  例如前文 linear regression, 如果為了 minimize ||x||2 而讓直線偏一些,就會造成 least square error 大量增加。因此在 n > k (under fit) 情況下增加 regularization term 並不會改變原來的 solution 太多。

相反在 k > n, overfit 情況下,滿足 ||Ax-y||=0 的 solution 很多,regularization 此時 play an important role to nail down the solution. 

 

Dual problem 就是 unconstraint quadratic function 而非 least square linear function (underfit)

因為 unconstraint, 同時 A’A or AA’ 看那一個是 full rank.   不論 n > k or n < k or n =k 都 ok.

 

標準的 Least Square 如下

NewImage

dim(A) = n x k  (n >> k), i.e. tall matrix

dim(x) = k x 1;  dim(b) = n x 1

標準的 LS 是 underfit.

 

Analytic solution: 

NewImage

A’A  (dim=k x k) 是 PSD matrix.  假設A’A 是 full rank 所以 invertible.  但若 eigenvalue 太小,收歙上仍可能 非常慢。

 

 

Regularization 在 Optimization 是常用的技巧

NewImage

為什麼要加上 regularization? 

 

* 要解決 overfit 的問題!!

 當有太多的 x 可以滿足 Ax = b  (i.e. || Ax-b || 是 minimum), 要挑最小的 norm (L1 or L2?)

==>  所以原先 underfit 的 A (tall matrix), 突然不適用!!!  反而是變成類似 least norm 問題,但不要求 Ax=b.

  此時 A 是 fat matrix, n x k.   k > n

 

* 為何 regularization 可以解決 overfit 的問題?

1. SNR 觀點:  yn (w’ xn + b) > = 1  where yn = +1 or -1.  

因此 |wn| 愈小,代表 |xn| cos(theta) 愈大。xn 基本上是定值,所以 cos(theta) 變大,也就是 xn 在 decision boundary 的法向量投影愈大,也就是 margin 最大。在有 noise 的時候,仍可以 reliably detect/classify。或許會疑惑 overfit 和  noise 有什麼關係。可以參考林軒田教授的 ML foundation lecture.

Model complexity (due to overfit) 可以視為 deterministic noise.  因此 regularization by minimize |w| 所造出的 margin 可以對抗 overfit 的問題。

 

2. Model complexity 觀點: 同樣參考林軒田的 lectures.  Regularization 的效果是等效 VC (Vanpnik .) dimension 變小。根據 learning theory (請參林軒田 lecture), regularization 雖然不會讓 in-sample error 變小,但會讓 out-sample error 變小,這非常重要。也是 learning theory 最 critical 的部份。

 

 

其他的 regularization 的用途:

* Prior knowledge:  ||x||  is small.  (Baysian view)

* Small signal optimal design:  Ax ~ b holds when x is small

* Robust design:  || (A + ΔA) x – b || = || Ax -b + ΔA.x ||.   Robust design when x is small

 

 

Tikhonov (L2) Regularization

 

NewImage

NewImage

因為 I 的關係,A’A + λI 為 PD, 不論 A 是 tall or fat matix.  所以 matrix 一定是 invertible, 同時收歙會更好。

如果 λ -> 0, 變成 LS optimization, A 必須是 tall matrix.  

 

Lagrange dual

以下是 Lagrange dual 的推導,假設 L2 norm regularization (minimum energy).  

如果是用 L1 norm regularization (下文,x 會是 sparsity vector). 

NewImage

以上是 Lagrange dual.  再來是找 maximum point 如下。

注意 x 是 linear function of b!! 代表 L2 regularization 得到 linear filter!  

NewImage

補充一下如何把 λ(AA’ + λI)^(-1)  變成 I – A(A’A+λI)^(-1)A’

NewImage

 

再補充一下如何 left inverse = right inverse.  注意這並非 in general true, 只有在以下 two conditions hold.

NewImage

 

以下是包含 kernel, 參考 Rifkin “Regularized Least-Squares Classification

NewImage

 

 

L1-Regularization

可以參考 Kim and Boyd “An Interior-Point Method for Large-Scale L1-Regularized Least Squares

NewImage

 L1 norm 沒有 close form.  但可用 quadratic programming.  

可用 Matlab 求解。見 reference.

 

Lagrange dual

 在做 dual 之前,可以把 (3) 變得更 general 如 (5).  如果 λi = λ.  (5) 就變為 (3).

NewImage

因為沒有 constraint, 所以先製造 equality constraints.

NewImage

 

NewImage

注意在 minimize 過程中,可得到 z + v = 0 ;  x 則是用 z = Ax – y 得出。    

 

另一個推導見於見 reference.

注意上面的 eq. (10) 和 下面的 eq. (5) 有些不同。 Eq. (10) 來自上面的 Eq. (5), 是假設 weighted L1 regularization.  下面的 eq. (5) 則是假設 global L1 regularization. 

NewImage

NewImage

以上的 z 就是前文的 v.    r  + z = 0  =>  r = -z  => r = Ax -b =>  -z = Ax – b => solve x as above!!

注意 x 並非 linear function of b, 因為 z 是由 QP 決定!!!  這是 L1 和 L2 重要的差別!

在後文 filter 可看出。

 

Least Square with L1 or L2 Regularization?

L2 regularization 是 LS 最常用的 regularization.  部份的原因和 L2 norm 的歷史有關。

數學上漂亮且有 close form, 還有 iterative solution (Kalman filter, LMS).  同時對於 low pass signal + Gaussian noise or Gaussian signal (e.g. match filter) 是 optimal controller (Wiener filter, Kalman filter).

L1 regularization 長久以來都只是 publication purpose.  並無實際用途。

但 Stanford Boyd group 以及其他 researchers driver L1 norm/regularization 在解法 (convex optimization) 以及 large scale 算法,以及很多實際的應用 (compressed sensing, medical imaging, sparse signal processing).  請見另文討論。

以下為 a sparse signal recovery example.

x ∈ R(4096), 包含 160 spikes of +1 or -1, 如下圖。  

A ∈ R(1024×4096) 是 fat matrix, overfit. 

y = Ax + v   v ~ N(0, 0.01^2 I) on R(1024).  

NewImage 

LS filter with L2 and L1 norm regularization 結果分別如下圖。第一圖是用 L2 regularization (minimum energy).  第二圖是用 L1 regularization.  

Signal process 中 x (4096) -> y (1024) 是個 decimation or under-sampling process, 同時加上 gaussian noise.   傳統的 signal processing 中有 Nyquist sampling theorem, 可以看到原始的 signal spikes 需要很高的 over-sampling 才有可能 recovery x.  此處不但沒有 over-sampling, 反而是 under-sampling.

如果使用 LS with L2 regularization 類似傳統的 LMS filter.  Recovered signal 如下第一圖,沒有任何的 signal.

神奇的是如果使用 LS with L1 regularization,  recovered signal 如下第二圖,幾乎可以恢復原來的 x.

這似乎完全違背 Nyquist sampling theorem!!!

關鍵是:

1. Sparsity: 請見 Wiki compressed sensing.  Candes, Tao, Donoho 証明在 sparsity condition, 可以用少量的 sample to reconstruct original signal.

2. Nyquist sampling theorem 只是 sufficient condition, 而不是 necessary condition.  例如對於 bandpass signal, 也可以 under-sampling.  同樣對於 sparsity signal, 也可以 reconstruct orignal signal.  不過不是用 LS with L2 regularization!!

3. 為什麼 L1 regularization 比 L2 regularization 適合 sparsity signal 或高頻信號或影像信號?

高頻或影像信號在 L2 regularization 都會造成很大的 penalty.  L1 則是 a lot better.  當然這只是 hand-waving 解釋。影像信號包含很多 edge (高頻), L1 似乎比較好。同時 L2 似乎容易有 aliasing problem. 

NewImage 

 

 

Questions:

1. How about CVBS, AHD, CVI, etc.  use L1 regularization

2. How about mixed L1 and L2? 

   * Not use LS, but use Huber loss function?

   * Mixed L1 and L2 regulariation

3. Re-weighted, iterative L1 regularization?

Advertisements