Sparse Coding and Autoencoder

by allenlu2007

Reference: 無监督学習中的兩個非機率模型:稀疏编碼与自编碼器

前兩文討論 autoencoder (MNIST with Autoencoder, Sparse Autoencoder) 已經差不多 cover 我自己想到的主題。

但是在機器之心看到 reference, 覺得寫的很好。就再節錄 reference 的重點。


Unsupervised Learning 無監督學習

下圖幫助我分類 Probabilistic Models and Non-probabilistic Models for unsupervised learning.

 

NewImage

 

Non-probabilistic Models 主要的方向都是 explore data structure:

– 降維 : PCA, Autoencoder

– Sparsity: Sparse encoder, Sparse Autoencoder

– Clustering: K-mean, GMM(應該是 probabilistic model?)


 

Probabilistic Models 主要方向:(A) explore data structure; (B) 生成 data.

一類和 Non-probabiistic models 基本一致。Dimension reduction, Sparsity, Clustering, 只是導入機率詮釋。

例如 PCA 也可視為 maximum variance dimension reduction.   Sparsity 則有 denoise.  Clustering 則有 GMM.


更有趣或有用的是 Probabilistic Generative Models, 這和 non-probabilistic model 目標不同。重點是藉著生成 (generative) data, 特別是近似原始 data 的 generative model to explore data structure.  

所以 Generative model 的好處是兩面: (1) 生成 data; (2) explore data.  (1) and (2) 是互為因果。同時也有廣泛應用!!  另外 debugging 更方便。

例如最近非常熱門的 GAN (Generative Adversarial Networks).   即使 autoencoder 雖然是 non-probabilistic model,但有類似的效果 (encoder -> decoder).  


Sparse Coding

前文提到 sparsity penalty 是用 KL divergence 以及 sparsity parameter (~0) 規範 sparsity training.

Overall cost function is now:

\begin{align}
J_{\rm sparse}(W,b) = J(W,b) + \beta \sum_{j=1}^{s_2} {\rm KL}(\rho || \hat\rho_j),
\end{align}
Where J is L2 cost function.  


Convex optimization 學到的 Lasso 也可以用來規範 sparsity in neural network!

1996 Olshausen and Field 提出 sparse coding 用於解釋大腦初級視覺處理。

目标:给定一组輸入数据向量 { x1,x2,…,xN },去學習一组基字典(dictionary of bases):

 

满足:

其中 a_nk 的值大部分都為 0,所以稱為“稀疏”。每一個数据向量都由稀疏线性權值与基的组合形式来表達。


Sparse coding 的 training

為輸入图像片段;

為要學習的基字典(dictionary of bases)。

 

Cost function and optimization 如下:

 

 

這個 Lasso 表達式的第一项為重構误差项 (reconstruction error);第二项為稀疏懲罰项 (sparsity penalty)。唯一的問題是 both dictionary of bases and a_nk 兩者都是未知

 

解決的方法是交替優化 (alternating optimization)!這在 probability, statistics, learning 常常用到, e.g. EM method, GMM, etc.


Alternating Optimization for training

1. 固定 basis,求解 weight, a_nk(這是一個标准的 Lasso 問题)。

2. 固定 weight, a_nk,優化 basis(convex QP problem)。

* 1 and 2 是在 training 時交替優化。

 

Sparse coding 的 testing:

  • 輸入為一個新图像片段 x* , 和 K 個可学習的 basis;
  • 輸出為一個图像片段 x* 的稀疏表達 a (sparse representation). 

 

 

 

最後再加上一個分類器 (softmax or SVM) 作為 object detection (ImageNet).

[0, 0, …, 0.8, …, 0.3 …, 0.5, …] 為系数矩阵,也叫做特征表示(feature representation)。

下图為应用稀疏编碼进行图像分类的相关实验结果,该实验是在 Caltech101 物体类别数据集中完成的,并且用经典的 SVM 作為分類算法。

 

 

 

Autoencoder

上文 training 的交替優化 (alternating optimization) 其實就是 autoencoder 的一種 !!

只是 learning 的角度和方法都有所不同。

 

1. 固定 basis,求解 weight, a_nk(這是一個标准的 Lasso 問题)。Encoder

2. 固定 weight, a_nk,優化 basis(convex QP problem)。Decoder



 

 

Learning 的角度:

  • a 是稀疏,且 over-complete 的表征; => a vector 就是 feature (vector)!  也就是 true output!
  • Encoder 编碼函数 a = f(x) 是 x 的隐函数和非线性函数;=> phi_k (basis) 就是 neural network 的 weight!
    • Encoder 是 feed-forward and nonlinear function!
  • Decoder 解碼函数 x’ = g(a) 是线性且显性的。=> x’ 就是生成的 pseudo-input.
    • Decoder 是 feed-back, generative, and linear function!  其實就是 back propagation.



常見的 autoencoder 例子。

Example 1: Linear autoencoder.  圖示如下。其實就是 PCA.


Example 2: Nonlinear autoencoder.  就是前文的 autoencoder.

 

如上图所示,编碼器的過滤器(filters)為 W,函数為 Sigmoid 函数,

 

解碼器的過滤器(filters)為 D , 函数為线性回归函数。

 

這是一個擁有 D 個輸入和 D 個輸出的自编碼器,并且包括 K 個隐单元(hidden units), K<D。给定輸入 x,它的重構函数為:

我们可以通過使重構误差(reconstruction error)最小化来决定网络的参数 W 和 D :


Example 3: Binary autoencoder.  更進一步的 nonlinearize, 或是 binarized autoencoder

以上結構和 RBM 相關。


 

Multi-layer or Stacked Autoencoder

Multi-layer or stacked autoencoder 是 autoencoder 自然的延伸。

唯一的問題是如何 train multi-layer autoencoder?  簡單的想法就是分層學習 (Greedy?) 



Advertisements