# Scaled Cross-Entropy

$$
log_{2}\left(1+e^{-y_{n}\mathbf{w}^{T}\mathbf{x}_{n}}\right)
$$

只要將原本的 CE 除以 $ln2$ 就可以得到這個版本的 CE，這樣做的原因是，SCE 其實也是 0/1 error 的一個上限。

$$
err_{0/1}(s,y)\le err_{SCE}(s,y)=\frac{err_{CE}(s,y)}{ln2}\\
\Rightarrow E^{0/1}_{in}(\mathbf{w})\le E^{SCE}_{in}(\mathbf{w})=\frac{E^{CE}_{in}(\mathbf{w})}{ln2}\\
E^{0/1}_{out}(\mathbf{w})\le E^{SCE}_{out}(\mathbf{w})=\frac{E^{CE}_{out}(\mathbf{w})}{ln2}\\
$$

所以再次回顧之前的 VC bound 告訴我們的不等式：

$$
E^{0/1}_{out}(\mathbf{w})\le \frac{E^{CE}_{in}(\mathbf{w})}{ln2}+\Omega^{0/1}\\
E^{0/1}_{out}(\mathbf{w})\le \frac{E^{CE}_{out}(\mathbf{w})}{ln2}\le \frac{E^{CE}_{in}(\mathbf{w})}{ln2}+\frac{\Omega^{CE}}{ln2}
$$

也就是說我們可以用 Logistic Regression 的結果來對 binary classification 進行預測。

# Stochastic Gradient Descent (SGD)

由於標準的 GD 每次更新就需要對 N 筆資料做計算，為了降低這個計算量，改成隨便挑一筆資料的 GD 作為更新方向。

理由是相信平均走下來的方向跟原本梯度的走向是一樣的。

$$
\mathbf{w}_{t+1}=\mathbf{w}_{t}+\eta\underbrace{\frac{1}{N}\sum_{n=1}^{N}\theta(-y_{n}\mathbf{w}^{T}\mathbf{x}_{n})(y_{n}\mathbf{x}_{n})}_{-\nabla E_{in}(\mathbf{w}_{t})}
$$

這是原版的梯度，是對 N 筆資料的梯度取平均。

$$
\mathbf{w}_{t+1}=\mathbf{w}_{t}+\eta\ \underbrace{\theta(-y_{n}\mathbf{w}^{T}\mathbf{x}_{n})(y_{n}\mathbf{x}_{n})}_{-\nabla err(\mathbf{w}_{t},\mathbf{w}_{x_{n},y_{n}})}
$$

這是 SGD，指挑一筆資料的 GD 作為更新方向。

如果拿來跟 PLA 比較：

$$
\mathbf{w}_{t+1}=\mathbf{w}_{t}+ 1 \times [[y_{n}\ne sign(\mathbf{w}^{T}\mathbf{x}_{n})]] (y_{n}\mathbf{x}_{n})
$$

可以發現：

- $SGD$ logistic regression $\approx$ soft $PLA$
- $PLA\approx SGD$ logistic regression 當 $\eta=1$ 且 $\mathbf{w}^{T}\mathbf{x}_{n}$ 很大的時候。

:::warning
兩個實務上的要點：
- 何時要停？
- t 足夠大的時候
- $\eta$ 應該要多少？
- 如果 $\mathbf{x}$ 在正常的範圍內，通常來說 0.1 是個好選擇
- 老師喜歡的數字是 $0.1126$
:::

---

# One-Versus-All (OVA) Decomposition

$for\ k\in\mathcal{Y}$

$$
\mathcal{D}_{[k]}=\left\{\left(\mathbf{x}_{n},y^{'}_{n}=2[[y_{n}=k]]-1\right)\right\}^{N}_{n=1}
$$

$$
g(\mathbf{x})=argmax_{k\in\mathcal{Y}}\ \color{gray}{\theta}\left(\mathbf{w}^{T}_{[k]}\mathbf{x}\right)
$$

將想要分的 K 組資料，分成「是第 K 組的」跟「不是第 K 組的」兩種資料來進行 Binary Classification，總共會得出 K 種 $\mathbf{w}_{[k]}$。

但如果是單純用 PLA，會出現重疊部分分不清的情況，所以可以採用 logistic regression 來做 Classification，遇到重疊部分就看哪個權重內積的值最大就好。

:::info
由於 logistic function 是 monotonic，所以其實不一定要把內積的值代進函數內，直接比較內積的值大小就好。
所以上面公式中的 $theta$ 是灰色的。
:::

## 優點

有效率，並可以和任何類似 logistic regression 進行搭配。

## 缺點

如果 K 太大，會導致第 K 組跟其他組別的資料量差異太大，會讓 g 偏向於猜 $\color{red}{\times}$

# Multinomial/multiclass logistic regression

multiclass 的延伸版本，專門給每個 Class 都近似一個 logistic function。

$$
\Large
h_{y}(\mathbf{x})=\frac{e^{\mathbf{w}^{T}_{y}\mathbf{x}}}{\sum_{k=1}^{K}e^{\mathbf{w}^{T}_{k}\mathbf{x}}}
$$

跟 logistic regression 一樣的推導過程，可以得出：

$$
\Large
E_{in}(h_{y}(\mathbf{X}))=\frac{1}{N}\sum_{n=1}^{N}\left(ln\left(\sum_{k=1}^{K}e^{\mathbf{w}^{T}_{k}\mathbf{x}_{n}}\right)-\mathbf{w}^{T}_{y_{n}}\mathbf{x}_{n}\right)
$$

和梯度：

$$
\Large \frac{\partial E_{in}(h_{y}(\mathbf{X}))}{\partial \mathbf{w}_{i}}
=\frac{1}{N}\sum_{n=1}^{N}\left(\left(h_{i}(\mathbf{x}_{n})-[[y_{n}=i]]\right)\mathbf{x}_{n}\right)
$$

:::warning
在推導的時候要記住，不會有 $1 - h(\mathbf{x})$ 這種東西出現，他是第 K 種的機率就是 $h_{K}(\mathbf{x})$。
:::

---

# One-versus-one (OVO) Decomposition

兩組兩組出來訓練出 $\mathbf{w}$，也就是說總共有 $\binom{K}{2}$ 種 $\mathbf{w}_{k,l}$。

$for\ (k,l)\in\mathcal{Y}\times\mathcal{Y}$

$$
\mathcal{D}_{[k,l]}=\left\{\left(\mathbf{x}_{n},y^{'}_{n}=2[[y_{n}=k]]-1:y_{n}=k\ or\ y_{n}=l\right)\right\}
$$

$$
g(\mathbf{x})=tournament\ champion
\left\{\mathbf{w}^{T}_{[k,l]}\mathbf{x}\right\}
$$

tournament champion 就是看在 $\binom{K}{2}$ 種 $\mathbf{w}_{k,l}$ 中，看哪一組的被預測次數最多次。

## 好處

K 較小時很有效率，並且穩定，可以搭配任何 binary classification。

## 缺點

由於有 $\binom{K}{2}$ 種 $\mathbf{w}_{k,l}$，所以跟 OVA 相比，更花空間跟時間。

---

# Newton Direction

這是利用多維情況下的牛頓法，來找到下降的方向；通常來說比梯度下降更快。
> 畢竟是二階導數

$$
\mathbf{w}_{t+1}=\mathbf{w}_{t} + -\left(\nabla ^{2}E(\mathbf{w}_{t})\right)^{2}\nabla E(\mathbf{w}_{t})
$$

其中 $\nabla ^{2}E(\mathbf{w}_{t})$ 是海森矩陣，也就是由二階導數所構成的陣列。