<small>Exploiting Generative Models in Discriminative Classifiers</small>
---

### Abstract

這世界上有很多feature不是一個固定的大小，意即data.size()可能不是一致的(例如一張圖片的透過SIFT所抓出來的Keypoint，或是具有不同長度序列的資料，如語音)。這樣可能會造成模型無法正常實施。那究竟要如何解決這個問題呢?
> 例如一般的Linear/Logistic Regression，乃至於Support Vector Machine，這些設定都是建立在資料的維度都是固定的，並將其中各個維度給予分數並轉換成需要預測的分數。

首先，我們可以先整理有甚麼技術是我們可以應用的。
1. 現今機器學習上(即便是paper當年的1998年)，有很多很強的"Discriminative Classifier"，意即可以辨別資料是否為某個類別，例如SVM。
2. 除了Discriminative Classifier，亦有一個很特別的模型 -- Generative Probability Model，例如GMM(Gaussian Mixture Model)，這類型的模型可以為每個資料的類別生出數個最具代表性的(假想)資料，並以這個代表性的資料來判斷其他資料是不是屬於同個類別。 舉例來說，GMM就是會生出數個Gaussian Distribution，以新進來的點判斷屬於這個Distribution的機率到底多高。

而我們是否可以結合上述兩個模型類別，做出一種可以解決維度不一的資料呢?
### Setting
##### Notation

* $X$: sample data.
* $\sum$: covariance matrix. (Assuming $X$ is zero-mean)
* $S$: labels of $X$, where $S_{i} \in {[+1, -1]}$.
* $\theta$ : parameter vector.

##### Predict by Kernel Function
* predicted label, $\hat{S} = sign(\sum_i S_i \cdot \lambda_i \cdot K(X_i, X))$
* $\lambda_i$: some coefficient representing for importance.
* $K$: A measurement of calculating pairwise "similarity".

##### Kernel Logistic Regression
* Model Description: $P(S | X, \theta) = \sigma(S \theta^TX)$
* Target Function: $\min_{\theta} \sum_{i} \log P(S_i| X_i, \theta) + \log P(\theta)$ = $\sum_{i} \log \sigma(S_i \theta^T X_i) - \frac12 \theta^T \sum^{-1} \theta + C$
* 上述式子可以經過繁瑣的證明變成以下。
* $\hat{\theta} = \sum_{i} S_i \lambda_i \sum X_{i}$, where $\lambda_i = \frac{\partial}{\partial z} \log \sigma(z)$, and $z = S_i \theta^T X_i$
* 因此， $P(S | X, \hat{\theta}) = \sigma(S \sum_{i} S_{i} \lambda_{i}(X_{i}^T\sum X))$.
* 透過定義 $K(X_i, X) = X^{T}_{i} \sum X$，我們就可以算出如何利用Kernel去預測label。

##### Valid General Kernel Function
是否還有其他的Kernel Function可以使用呢? 在此節我們直接引用[軒田老師的投影片](https://www.csie.ntu.edu.tw/~htlin/course/mltech18spring/doc/203_handout.pdf)。
* 基本上只要$K$是個Positive semi-definite就滿足kernel function的條件了。另外，基於Mercer's condition，kernel function較為簡單的表達方式就是需要可以將$K(X_i, X_j)$表達成$\phi^T_{X_i} \cdot \phi_{X_j}$。
* 以上述Logistic Kernel Regression來說，$\phi_{X}$ 其實就等於$\sum^{\frac12} X.$
* 在這邊註記一點: 我們其實可以純粹的利用Kernel Function來描述兩個資料經過$\phi$轉換的L2距離。
* $||\phi_{X_i} - \phi_{X_j}||^2 = \phi_{X_i}^2 - 2\phi_{X_i}\phi_{X_j} + \phi_{X_j}^2 = K(X_i, X_i) - 2K(X_i, X_j) + K(X_j, X_j)$
* 如果我們將$K_{ij}$表示成$K(X_i, X_j)$，則可以得出下列公式。
* $||\phi_{X_i} - \phi_{X_j}||^2 =K_{i,i} - 2K_{i,j} + K_{j,j}$

##### \[Proposed\] Fisher Vector: Kernels from generative probability models
總而言之，前面的部分是Kernel Function的介紹，以及如何使用Kernel Function去預測label。現在我們則著重如何利用Generative Model**生成**這個Kernel Function，以此達到製作出具有representative的$\phi$轉換的效果。

* 首先，假設我們已經有一個Generative Propability Model，計作$P(X|\theta)$，表示以$\theta$這個參數製作出$X$的機率到底多高。
* 其次，我們定義一個有趣的分數，**Fisher score**, 計作$U_X = \nabla_{\theta} P(X|\theta)$。這個指標的意涵為: 在原本的模型參數($\theta$)內，到底為了製作出這個特別的資料$X$花了多少心力。
* **Fisher Information Matrix** $I = \mathbb{E}_{P(X|\theta)} [U_X U_X^T]$
* 關於Fisher Info Matrix，以及各式各樣的證明，可以參考[link](https://bluefisher.github.io/2020/02/16/Natural-Gradient-Descent/)
<!-- * 兩個相近的模型(假設$\delta$極小)的距離，可以透過KL-divergence估計成$D(\theta, \theta + \delta) = \frac 12 \delta^T I \delta$。 -->
* 總而言之，如果要利用有限的距離$\delta$，使得$\theta$偏離到可以生成X的Generative Function，我們會發現其方向最佳為$\nabla_{\theta} U_X$，經過證明後得$\nabla_{\theta} U_X = I^{-1}U_X$ (事實上這就是$P(X|\theta)$的**natural gradient descent的公式**)。而在這篇paper中，這就是我們想要的$\phi$轉換。意即$\phi_{X} = I^{-1} U_{X}$。

* 最後，我們將這個轉換還原回去Kernel，得到paper所提出的fisher kernel，$K_{fisher}(X_i, X_j)$。
* 其正比於$\phi^T_{X_i}I\phi_{X_j} = (U^T_{X_i} (I^{-1})^T) I (I^{-1} U_{X_j}) = U^T_{X_i} I^{-1} U_{X_j}$。
* 利用這種方式，我們就可以用Generative Probability Model生成出Kernel Function，以此來作Discrimination，或當作更有意義的特徵來做各種事情。
* 需要特別注意的是，作者鼓勵使用更高維度的Kernel Function來操作。例如本文的主軸任務(DNA序列判別)，作者的$\hat{K}(X_i, X_j) = (1+K(X_i, X_j))^m$，$m$為超參數，論文實驗取2。
### Comment
1. 這種方法對於GMM等參數比較少的生成模型看起來是沒問題的。因為其$U_X$的維度是與$\theta$有關的。但在現今NN滿街跑的情況，貌似就不太適用。因為NN的參數實在是太多了，用Fisher score 或用 Fisher Information等方法來獲得一個資料的特徵可能不是很合適。
2. 我們看的出來這個方法大致上都會假定生成模型是Gaussian-like的方法，但不幸的是這個假設可能太模糊或強烈了，畢竟不是所有資料都是符合Gaussian Distribution (或很難找到一個轉換使其變成Gaussian Distribution)。
3. 綜合前兩個Comment，我們不難發現其實現今有很多Unsupervised Learning的方法可以抽取一張圖片的特徵都可以解決掉上述兩個問題。 例如我們可以使用Auto-Encoder來壓縮資料，而且這個資料也沒有受到維度的限制。(例如Encoder和Decoder都是RNN-based的model，就可以接受sequence-level的資料。) 因此如果要將Fisher vector的模式帶進來，其實就會變得很俗。方法大概率就會變成如下所述:
* 利用AE抽取資料的特徵，每個資料的特徵維度都會是固定的。
* 抽取完資料的特徵，利用這些特徵去作Logistic Regression。
* 看起來就十分的"不novel"，老實說。
4. 即使如此，我們還是有其他方向可以思考。如第一點所述，雖然我們做不到$\nabla_{\theta}U_X$當作特徵，因為NN的參數實在太多。但何必要所有參數都全下呢?事實上我們可以只拿某一層參數的微分當作是Fisher Score也說不定，其的意義相當於是將這層的上一層當作是這篇paper的原始$X$，也許這樣的方法也有不錯的效果。 (當然我想直接AE還是最快的啦。)

---

### About Natural Gradient Descent
* 某天有空再補，這是paper的第一個reference，與取得Fisher Vector有強烈的關係，以及詳細的證明。