---
# System prepended metadata

title: Kernel Logistic Regression
tags: [機器學習技法]

---

# 另一種表示法

觀察 $\xi_{n}$ 的特性後可以把 $\xi_{n}=1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b)$ 這項合併進去：

$$
\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+C\sum_{n=1}^{N}max\left(1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b),0\right)
$$

如果把他跟之前的 Logistic Regression 對比一下會發現他們兩個長很像：

$$
\frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum err_{CE}
$$

既然長很像，為何之前介紹 SVM 的時候不是以這個形式開始解呢？畢竟 Logistic Regression 有個明確的做法。

原因是出在 max 函數，他有無法微分的地方，並且這樣的寫法等於我們把要解的內容都塞在一起，並非 QP 的形式，再來我們也「好像」也無法在這裡使用 Kernel Trick。

## $\mathbf{w}^{T}\mathbf{w}$

在 SVM 中， $\mathbf{w}^{T}\mathbf{w}$ 是「Large Margin」的部分，也就是要找出最大的邊界，而這個操作可以起到「減少超平面」的效果，這個效果就跟  L2 Regularizer 做的一樣

## $\sum_{n=1}^{N}max\left(1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b),0\right)$

而 SVM 中 $\sum_{n=1}^{N}max\left(1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b),0\right)$ 的部分其實就是一種我們想要最小化的 $E_{in}$。

## $C$

- 在 Logistic Regression 中有提到超維球的半徑 $C$，$C$ 越大代表對 $\mathbf{w}$ 長度的限制就越小
- 在 SVM 中， $C$ 越大代表對 $\xi$ 的限制越大，允許的平面越瘦，越瘦的平面就代表 $\frac{1}{\left\|\mathbf{w}\right\|}$ 這個寬度值越小
  - 等同於 $\left\|\mathbf{w}\right\|$ 的值越大，也就是對 $\mathbf{w}$ 的長度限制越小。

也就是說兩者的 $C$ 在做一樣的事情。

## hinge error measur

畫出 $err$ 圖形的話，可以發現 Scaled Logistic Regression 跟 SVM 非常的相似，不論是在趨近正負無限大的時候，或是 $ys=0$ 的時候。

而 max 這個函數因為其獨特的長相，有個名稱叫做 hinge error measur。

# SVM approximate LogReg

既然兩者竟能如此相像，那麼我們來用 SVM 近似 LogReg；或者說把兩者進行合體。

## 直覺 1

$$
g(\mathbf{x})=\theta\left(\mathbf{w}^{T}_{SVM}\mathbf{x}+b_{SVM}\right)
$$

這樣只是單純使用 SVM 的結果。

雖然就結果上來說確實有不錯的效果，但我們就缺少了 LogReg 的調味，也就是尋找 Max Likelihood 時的 GD/SGD步驟。

## 直覺 2

$$
Let\ \mathbf{w}_{SVM}\ to\ be\ the\ \mathbf{w}_{0}\ of\ LogReg
$$

這樣就結果來說只是單純在跑 LogReg，少了 SVM 的調味，也就是 SVM 的結果跟 Kernel Trick。

---

# Platt’s Model / Probabilistic SVM

Platt 這位厲害的人，提出了結合的模型，其簡化的內容大致為：

$$
\min_{A,B} \frac{1}{N}\sum_{n=1}^{N}log\left(1+exp\left(-y_{n}\left(A\left(\mathbf{w}_{SVM}^{T}\phi(\mathbf{x_{n}})+b_{SVM}\right)+B\right)\right)\right)
$$

而這個新的 LogrReg 問題，就是將 SVM 的結果維持住，並且在其上使用 A 跟 B 兩個參數進行「調味」，或者說「微調」。

這個動作叫做 **Two-Level Learning**，顧名思義，我們是將 LogReg 操作在經過 SVM 所轉換的資料上，$\mathbf{w}_{SVM}^{T}\phi(\mathbf{x_{n}})+b_{SVM}$ 就是經過 SVM 所轉換的資料。

:::warning
- N-Level Learning 這個概念可以記起來。
- 以其他演算法作為特徵轉換，可以連結之後的 [Aggregation model](https://hackmd.io/QKHftqsISyO7gz-nsDVLUQ#linear-blending-for-regression) 
:::

:::info
通常來說：

- 如果 $\mathbf{w}_{SVM}$ 夠好，則 $A > 0$
    - 也就代表法向量的方向對了
- 如果 $b_{SVM}$ 夠好，則 $B \approx 0$
    - 也就是說不用做過多的微調
:::

實際上在 Platt’s Model 中

- 經過 SVM 轉換的資料不單單只有 $\mathbf{z}^{'}_{n}=\mathbf{w}_{SVM}^{T}\phi(\mathbf{x_{n}})+b_{SVM}$ 而已，而是更複雜一些
- 並且在對 A 跟 B 執行 LogReg 的時候，也有加入一些特殊的 Regularizer。

而解 LogReg 的方法，除了可以用之前的 GD 或 SGD，更由於因為只有雙變數，有著更好的解法。

## 近似解

一開始的目的是希望以 SVM 的結果來近似 LogReg 來處理輸出為機率的問題，所以才會使用 SVM 在 $\mathcal{Z}$ 空間中找到一個不錯的平面後，再以 $A$ 跟 $B$ 進行微調。

但這終究是個近似的解，接下來我們想要真的找出 LogReg 在 $\mathcal{Z}$ 空間中真的解。

# Kernel Logistic Regression

對於原本的 L2-regularized logistic regression：

$$
\min_{\mathbf{w}} \frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum_{n=1}^{N}log\left(1+exp\left(-y_{n}\mathbf{w}^{T}\mathbf{z}_{n}\right)\right)
$$

我們確實可以使用熟悉的 GD / SGD 或其他解最佳化的方法來解；但是轉換到 $\mathcal{Z}$ 的時候跟 SVM 一樣可能會遇到維度上的問題，所以我們也來使用 Kernel trick。

在 SVM 中我們是由於中間推導梯度時導出 $\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}$ 的結果，這個「最佳 $\mathbf{w}$ 可以被資料所呈現」的特性，在 PLA 和使用 SGD 的 LogReg 等等中也有出現。

## Representer Theorem

對於任何 L2-regularized linear model，也就是說形式如下的：

$$
\min_{\mathbf{w}} \frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum_{n=1}^{N}err(y_{n},\mathbf{w}^{T}\mathbf{z}_{n})
$$

我們可以知道最佳的權重 $\mathbf{w}_{*}$：

$$
\mathbf{w}_{*}=\sum_{n=1}^{N}\beta_{n}\mathbf{z}_{n}
$$

證明可以使用反證法，簡單來說：

- $\mathbf{w}_{*}$ 可以拆成和 $\mathcal{Z}$ 空間平行和垂直的兩個向量：$\mathbf{w}_{//}$ 跟 $\mathbf{w}_{\perp}$
  - $\mathbf{w}_{//}$ 就是由 $\mathcal{Z}$ 空間向量組成的線性組合
- 既然是最佳向量，可知 $\mathbf{w}_{\perp}$ 是 0 向量
    - 也就是說 $\mathbf{w}_{*}$ 只剩下 $\mathcal{Z}$ 空間向量組成的線性組合
- 如果 $\mathbf{w}_{\perp}$ 不是 0 向量，則
    - 在計算 $err(y_{n},\mathbf{w}^{T}\mathbf{z}_{n})$ 的時候，$\mathbf{w}_{*}$ 和單純只有 $\mathbf{w}_{//}$ 計算的結果是一樣的，因為 $\mathbf{w}_{\perp}$ 乘上去後會變成 0。
    - 在計算 $\mathbf{w}^{T}\mathbf{w}$ 的時候， 因為$\mathbf{w}_{*}=\mathbf{w}_{//}+\mathbf{w}_{\perp}$ ， $\mathbf{w}_{//}\cdot\mathbf{w}_{\perp}=0$，如果 $\mathbf{w}_{\perp}\ne\mathbf{0}$，則 $\mathbf{w}_{*}^{2}>\mathbf{w}_{//}^{2}$，代表 $\mathbf{w}_{*}$ 計算得到的值不是最小值，造成矛盾

所以我們得到一個很強的結果，任何 L2-regularized linear model 都可以使用 Kernel Trick，或者說「Can be kernelized」

# Kernel Logistic Regression

所以我們把 $\mathbf{w}_{*}=\sum_{n=1}^{N}\beta_{n}\mathbf{z}_{n}$ 給代入原本的 LogReg：

$$
\min_{\boldsymbol{\beta}} \frac{\lambda}{N}\sum_{n=1}^{N}\sum_{m=1}^{M}\beta_{n}\beta_{m}K(\mathbf{x}_{n},\mathbf{x}_{m})+
\frac{1}{N}\sum_{n=1}^{N}log\left(1+exp\left(-y_{n}\sum_{m=1}^{M}\beta_{m}K(\mathbf{x}_{m},\mathbf{x}_{n})\right)\right)
$$

其中：

$\sum_{m=1}^{M}\beta_{m}K(\mathbf{x}_{m},\mathbf{x}_{n})$ 的部分可以看做是一個 $\boldsymbol{\beta}$ 向量跟「transformed data」之間的內積。

$\sum_{n=1}^{N}\sum_{m=1}^{M}\beta_{n}\beta_{m}K(\mathbf{x}_{n},\mathbf{x}_{m})$ 可以改寫為：

$$
\boldsymbol{\beta}^{T}\mathbf{K}\boldsymbol{\beta}
$$

這個形式跟之前的 $\mathbf{w}^{T}\mathbf{w}$ 類似，多了 $\mathbf{K}$ 縮放的效果，是一種特殊的 Regularizer。

因此 KLR 可以從兩個角度去看：

- linear model of $\mathbf{w}$
    - 帶有隱藏的 kernel transform 和 L2 Regularizer
- linear model of $\boldsymbol{\beta}$
    - 帶有 kernel transform 和 kernel Regularizer

這種以兩個不同角度來看待相同模型，在 Gaussian SVM 的時候也出現過。

:::warning
但是不像 SVM 中 $\alpha_{n}$ 大多等於 0， nonSV 的部分；在 KLR 中的 $\beta_{n}$ 大多不等於 0，是個緻密矩陣。
:::

總之從原本的解 $\mathbf{w}$ 改成解 $\boldsymbol{\beta}$，一樣使用像是 SGD、GD 或是任何其他解最佳化問題的工具，不過不像 SVM，這裡是 nonconstrained optimization，是沒有限制的最佳化問題。