Generalizing Linear Classification
假設我們有如上圖的 training data，注意到此時 \(\mathcal{X} \subset \mathbb{R}^{2}\)，
那么 decision boundary \(g\)：
\[g(\vec{x}) = w_{1} x_{1}^{2} + w_{2} x_{2}^{2} + w_{0} \]
即，decision boundary 為某種橢圓，例如：半徑為 \(r\) 的圓（\(w_{1} = 1, w_{2} = 1, w_{0}=-r^{2}\)），如上圖中的黑圈所示，我們會發現，此時 decision boundary not linear in \(\vec{x}\)，
但是，\(g(\vec{x}) = w_{1} x_{1}^{2} + w_{2} x_{2}^{2} + w_{0}\) 在某些空間里卻是線性的：
\[\begin{align*} g(\vec{x}) & = w_{1}x_{1}^{2} + w_{2}x_{2}^{2} + w_{0} \qquad \qquad (\text{non-linear in $x_{1}$ and $x_{2}$}) \\ & = w_{1}z_{1} + w_{2}z_{2} + w_{0} \qquad \qquad \; (\text{linear in $z_{1}$ and $z_{2}$}) \end{align*} \]
因此，如果我們對資料進行特征變換（feature transformation）：
\[\phi(x_{1}, x_{2}) \longrightarrow (x_{1}^{2}, x_{2}^{2}) \]
那么 \(g\) 在 \(\phi -\) transformed feature space 中變為線性的，
Geometric view on feature transformation
Feature Transformation for Quadratic Boundaries
\(\mathbb{R}^{2}-\) case
generic quadratic boundary 如下：
\[\begin{align*} g(\vec{x}) & = w_{1} x_{1}^{2} + w_{2} x_{2}^{2} + w_{3} x_{1} x_{2} + w_{4} x_{1} + w_{5} x_{2} + w_{0} \\ & = \sum\limits_{p + q \leq 2} w^{p, q} x_{1}^{p} x_{2}^{q} \end{align*} \]
feature transformation 則為：
\[\phi(x_{1}, x_{2}) \longrightarrow (x_{1}^{2}, x_{2}^{2}, x_{1}x_{2}, x_{1}, x_{2}, 1) \]
\(\mathbb{R}^{d}-\) case
generic quadratic boundary 如下：
\[g(\vec{x}) = \sum\limits_{i, j = 1}^{d} \sum\limits_{p + q \leq 2} w_{i, j}^{p, q}x_{i}^{p}x_{j}^{q} \]
feature transformation 則為：
\[\phi(x_{1}, \ldots, x_{d}) \longrightarrow (x_{1}^{2}, x_{2}^{2}, \ldots, x_{d}^{2}, x_{1}x_{2}, \ldots, x_{d-1} x_{d}, x_{1}, x_{2}, \ldots, x_{d}, 1) \]
- 注意，以上的 \(\mathbb{R}^{2}\) 以及下面會提到的 \(\mathbb{R}^{d}\) 指的是資料的維度，
Theorem.
給定 \(n\) 個互不相同的資料點：\(\mathcal{X} = \left\{ \vec{x_{1}}, \vec{x_{2}}, \ldots, \vec{x_{n}} \right\}\)，總是存在一個 feature transformation \(\phi\)，使得無論的 \(\mathcal{S} = \mathcal{X} \times \mathcal{Y}\) 的 label 如何，它在 transformed space 中總是線性可分的，
Proof.
給定 \(n\) 個資料點，考慮以下映射（映射至 \(\mathbb{R}^{n}\)）：
\[\phi(\vec{x_{i}}) \longrightarrow \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \]
即，映射為一個 one-hot 向量，除第 \(i\) 行處為 \(1\)，其它坐標處的值都為 \(0\)，
那么，由 linear weighting \(\vec{w}^{*} = \begin{pmatrix} y_{1} \\ \vdots \\ y_{n} \end{pmatrix}\) 引出的 decision boundary 完美地分割了 input data，
-
解釋：
證明的意思是，輸入的資料有 \(n\) 個，對于每一個資料點，feature transform 到一個 one-hot vector，只有這條資料在輸入的 \(n\) 個資料中排的位置所對應的坐標處取 \(1\)，其余全部取 \(0\)，假設輸入三個資料：\(\vec{x_{1}}, \vec{x_{2}}, \vec{x_{3}}\)，則：
\[\phi(\vec{x_{1}}) = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \qquad \phi(\vec{x_{2}}) = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \qquad \phi(\vec{x_{3}}) = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \]
這樣極端的操作有利有弊：
-
優點：
任意的問題都將變為 linear separable，
-
缺點：
-
計算復雜度：
generic kernel transform 的時間復雜度通常是 \(\Omega(n)\)，有些常用的 kernel transform 將 input space 映射到 infinite dimensional space 中，
-
模型復雜度：
模型的概括能力（generalization performance）通常隨模型復雜度的下降而下降，即，若向簡化模型，通常需要以犧牲模型的表現作為代價，
-
-
回顧時間復雜度 \(T(n) = \Omega \big( f(n) \big)\) 的定義：
\[\exists c > 0: ~ \exists n_{0} \in \mathbb{N}^{+}: ~ \forall n \geq n_{0}: ~ T(n) \geq c \cdot f(n) \]
那么 \(\Omega(n)\) 滿足：
\[\exists c > 0: ~ \exists n_{0} \in \mathbb{N}^{+}: ~ \forall n \geq n_{0}: ~ T(n) \geq cn \]
也就是說時間復雜度最低也與 \(n\) 呈線性，
The Kernel Trick (to Deal with Computation)
如果直接暴露在 generic kernel space \(\phi(\vec{x_{i}})\) 中進行運算，需要時間復雜度 \(\Omega(n)\)，但是相對而言地，kernel space 中的兩個資料點的點積可以被更快地求出，即：
\[\phi(\vec{x_{i}}) \cdot \phi(\vec{x_{j}}) \]
Examples.
-
在 \(\mathbb{R}^{d}\) 空間中的資料的 quadratic kernel transform：
-
Explicit transform：\(O(d^{2})\)
\[\vec{x} \longrightarrow (x_{1}^{2}, \ldots, x_{d}^{2}, \sqrt{2} x_{1} x_{2}, \ldots, \sqrt{2} x_{d-1} x_{d}, \sqrt{2} x_{1}, \ldots, \sqrt{2} x_{d}, 1) \]
-
Dot products：\(O(d)\)
\[(1 + \vec{x_{i}} \cdot \vec{x_{j}})^{2} \]
-
-
徑向基函式（Radial Basis Function, i.e., RBF）：
-
Explicit transform：infinite dimension！
\[\vec{x} \longrightarrow \Big( \big( \frac{2}{\pi} \big)^{\frac{d}{4}} e^{-||\vec{x} - \alpha||^{2}} \Big)_{\alpha \in \mathbb{R}^{d}} \]
-
Dot products：\(O(d)\)
\[e^{-||\vec{x_{i}} - \vec{x_{j}}||^{2}} \]
-
Kernel 變換的訣竅在于，在實作分類演算法的時候只通過 “點積” 的方式接觸資料，
Examples.
The Kernel Perceptron（核感知機）
回憶感知機演算法，更新權重向量的核心步驟為：
\[\vec{w}^{(t)} \leftarrow \vec{w}^{(t-1)} + y \vec{x} \]
等價地，演算法可以寫為：
\[\vec{w} = \sum\limits_{k=1}^{n} \alpha_{k} y_{k} \vec{x_{k}} \]
其中，\(\alpha_{k}\) 為在 \(\vec{x_{k}}\) 上發生錯誤的次數，
因此，分類問題變為：
\[\begin{align*} f(\vec{x}) & = \text{sign}(\vec{w} \cdot \vec{x}) \\ & = \text{sign} \big( \vec{x} \cdot \sum\limits_{k=1}^{n} \alpha_{k} y_{k} \vec{x_{k}} \big) \\ & = \text{sign} \big( \sum\limits_{k=1}^{n} \alpha_{j} y_{k} (\vec{x_{k}} \cdot \vec{x}) \big) \end{align*} \]
其中 \(\vec{x}\) 輸入函式 \(f\) 的新資料向量，注意與 \(\vec{x_{k}}\) 區分，
因此，在空間內的分類問題：
\[f(\vec{x}) = \text{sign} \big( \sum\limits_{k=1}^{n} \alpha_{j} y_{k} (\vec{x_{k}} \cdot \vec{x}) \big) \]
若在 tranformed kernel space 中處理，則：
\[f\big( \phi(\vec{x}) \big) = \text{sign} \Big( \sum\limits_{k=1}^{n} \alpha_{k} y_{k} \big( \phi(\vec{x_{k}}) \cdot \phi(\vec{x}) \big) \Big) \]
演算法具體如下：
\[\begin{align*} & \text{Initialize}: \vec{\alpha} = \vec{0} \\ & \\ & \text{for } t = 1, 2, 3, \cdots, T: \\ & \\ & \qquad \text{若存在} (\vec{x_{i}}, y) \in \mathcal{S} \text{ s.t. : } \text{sign} \Big( \sum\limits_{k=1}^{n} \alpha_{k} y_{k} \big( \phi(\vec{x_{k}}) \cdot \phi(\vec{x_{i}}) \big) \Big) \neq y_{i}: \\ & \qquad \qquad \alpha_{i} \leftarrow \alpha_{i} + 1 \end{align*} \]
在最后注意到，\(\sum\limits_{k=1}^{n} \alpha_{k} y_{k} \big( \phi(\vec{x_{k}}) \cdot \phi(\vec{x}) \big)\) 中的點積 \(\phi(\vec{x_{k}}) \cdot \phi(\vec{x})\) 是相似度（similarity）的一種衡量方式，故自然能夠被其它自定義的相似度衡量方式所替換，
所以，我們可以在任意自定義的非線性空間中，隱性地（implicitly）進行運算，而不需要承擔可能的巨大計算量成本，
本文來自博客園，作者：車天健，轉載請注明原文鏈接：https://www.cnblogs.com/chetianjian/p/17270426.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548633.html
標籤：其他