針對一個機器學習的演算法，一般來說我們會希望他的泛化能力（generalization ability）是好的，也就是說倘若模型在訓練資料集的 loss 很低，則在測試資料集的 loss 應該也要很低才對，這樣的想法並不侷限於訓練與測試，offline 與 online、development 與 production、A 資料集與 B 資料集等應用場域都是互相呼應的，而穩定性（Stability）與稀疏性（Sparsity）正是兩個用以描述演算法泛化能力的性質。這篇文章主要想透過 介紹這兩個性質並進一步探討兩者之間的關係。

穩定性本身描繪了在兩個極為相似的資料集中，演算法所給出的預測應該也要非常相近才對，具體地來說假設有兩個資料集只有一個資料點的差異，則一個機器學習演算法應該要給出相近的輸出，這篇論文沿用 所定義的 Uniform stability 作為論證基礎：

An algorithm $\mathbb{L}$ has uniform stability $\beta_n$ with respect to the loss function $l$ if the following holds:
\begin{align*}
\forall (\mathbf{b}, A) \in \mathcal{Z}^n, \forall i \in \left\{1, \ldots, n \right \}: \\
\max_{\mathbf{z}’ \in \mathcal{Z}} \mid l(\mathbb{L}_{(\mathbf{b}, A)}, \mathbf{z}’) – l(\mathbb{L}_{(\mathbf{b}, A)^{\backslash i}}, \mathbf{z}’) \mid \leq \beta_n
\end{align*}
簡單來說如果一個演算法 $\mathbb{L}$ 有 $\beta_n$ 的 stability 的話，則對所有的資料點 $i$，用所有資料來學習的 $\mathbb{L}$ 與用少了第 $i$ 筆資料所習得的 $\mathbb{L}$ 之間的最大誤差應該要不大於 $\beta_n$，概念上其實就是 leave-one-out error。

稀疏性則是一個演算法所給出的解會有較高的解釋性，在計算上也會比較快速、有效率，想像一個 $n \times p$ 的資料矩陣 $A$ 與一個 $p \times 1$ 的解 $w$，若 $w$ 有很多元素為 0，則在計算 $Aw$ 的時候只要考慮 $w$ 非零的元素就好了。實務上也有許多主打稀疏性的演算法如 Lasso、1-norm SVM、Deep Belief Network 與 Sparse PCA。這篇論文則進一步將可以去找到冗餘的特徵（identify redundant features）的性質作為稀疏性演算法的必要條件：

A weight vector $\mathbf{w}^*$ identifies redundant features of $A$ if $$ \forall i \neq j, \quad \mathbf{a}_{(i)} = \mathbf{a}_{(j)} \Rightarrow w_i^* w_j^* = 0$$
也就是說資料裡面若有兩個特徵是一模一樣的話，其所對應的權重應該至少要有一個是零。一個演算法 $\mathbb{L}$ 若基於冗餘的特徵提供很多 0 的解，則說他可以 identify redundant features，且是一個 sparse algorithm。

最後想從特徵挑選 feature selection 的角度來看一下這件事情，實務上常透過特徵挑選來減少訓練時的特徵數量，避免維度的詛咒（curse of dimensionality），進而降低 overfitting 的風險，而一個穩定的特徵挑選演算法在不盡相同但高度相似的資料集中，應該要挑出類似的特徵們。另外一方面，Lasso 時常被拿來當作特徵挑選的演算法，他的特點是因為 L1 regularization，所以很常給出稀疏的解，而那些擁有非零權重的特徵便是最後挑選出來的結果，然而若這些解是不穩定的，那麼即使在資料上有很小的擾動，也有可能在輸出上有很大的差異，這顯然不是一件好事。以上則是從特徵挑選的視角來看待泛化能力，並且可以發現在特徵挑選中稀疏性與穩定性都是最好可以被滿足的性質。

稀疏性與穩定性的取捨

這篇研究主要就是透過上面的定義，去證明擁有稀疏性的演算法是不穩定的，並且也給出以下主要的 Theorem：

Let $\mathcal{Z} = \mathcal{Y} \times \mathcal{X}$ be the sample space with $m$ features, where $\mathcal{Y} \subseteq \mathbb{R}, \mathcal{X} \subseteq \mathbb{R}^m, 0 \in \mathcal{Y}$ and $\mathbf{0} \in \mathcal{X}$. Let $\hat{\mathcal{Z}} = \mathcal{Y} \times \mathcal{X} \times \mathcal{X}$ be the sample place with $2m$ features. If a learing algorithm identifies redundant features, its uniform stability bound $\beta$ is lower bounded and in particualr does not go to zero with $n$.

基本上作者主要想去證明「有稀疏性的演算法就不會有穩定性」，而整個證明的過程透過建構一個極端的例子（直接複製原本的特徵，使得有一半的特徵都是冗餘的），推導出 uniform stability $\beta_n$ 會大於等於某個數字，而這個數字並不會因為樣本數量增加而減少至 0。

我一方面覺得把整段定理打上來不太明智，一方面又覺得如果大家仔細看作者的敘述的話，可以發現這個 setting 著實有點極端，且整個定理只有一個方向，作者沒有證明「如果有穩定性就不是稀疏的」這一個方向，所以似乎有點不足以去說這是一個取捨（trade-off，作者在原文中有明示暗示這件事情），不過我覺得直覺上應該是通的，除了理論證明之外，我也認為也可能可以透過大量的 numerical experiments 去描繪出這一個取捨關係。

穩定與稀疏的演算法們

這邊最想提及的還是 $L_p$ regularization，如果 $p \leq 1$ 的話，則這樣的正則化會使得解變的稀疏或近乎稀疏；若 $p > 1$的話，則是一種相對穩定的演算法。

Sparse Algorithms

• $L_1$ regularization
• $L_0$ regularization

結論

這篇論文定義了機器學習演算法中可以用來表示泛化能力的稀疏性與穩定性，並透過證明「擁有稀疏性的演算法是不穩定的」，暗示這兩種性質之間不可兼得的關係，實務上我認為還是需要考慮應用場景來選擇演算法，畢竟若兩個性質之間真的是一種權衡，那就沒有絕對的好演算法與壞演算法。

對我來說這篇還是蠻有趣的，可以從不同視角看待市面上的那些演算法們，也希望讀者會覺得這些事情很有趣。撰文經驗匱乏，有任何建議或意見都可以進一步討論。

References

作者: boboru

A NTU IM master student. I am interested in causal inference, statistics and machine learning. / boru0713@gmail.com 檢視「boboru」的全部文章