Skip to content

Latest commit

 

History

History
135 lines (90 loc) · 7.47 KB

07.classification.md

File metadata and controls

135 lines (90 loc) · 7.47 KB
Raw

Classification

考虑简单的 K-NN 模型, 利用投票法可以用于分类, 但其度量指标的选择比较麻烦, 且复杂度为 $O(nd)$, 其中的 $k$ 更是需要调参.

因此应当考虑: 划分规则简单一些, 其 VC-dim 更低, $\epsilon$-net 越小; 而 VC-dim 越高, 越容易出现过拟合. 因此这里考虑线性模型.

若设训练集为 ${P^+, P^-}$, 所有数据点为 ${A^+, A^-}$, 分类器结果为 ${H+, H^-}$. 则可以认为 $P^$ 是 $A^$ 的一个 $\epsilon$-net, 因此可以以概率 $&gt;1-\delta$ 保证 $$\frac{|A^\backslash H^|}{|A^|} < \epsilon$$ 这里 $$ 表示 $+$ 或 $-$. 其中 $|P^*|=\widetilde{\Theta}(\frac{d}{\epsilon})$

模型

模型: $y(x)=w^Tx+b$, 不妨记为 $y(x)=[w^T, b]^T[x, 1]=\widetilde{w}^T\widetilde{x}$, 因此在 $d+1$ 维空间上, 就是一个经过原点的超平面.

在上述模型的基础上, 希望找到一个经过原点的超平面, 并且假设模型是线性可分的, 所有数据都限制在单位球内(可做归一化得到).

输入数据是 ${(x_i, y_i)|x_i \in R^{d+1}, y_i=\pm 1}$

目标是找到 margin 最大的线性分类器 $w^*$. 这里 margin 是 $\gamma=\min{y_i\left&lt; w, x_i \right&gt;}$

感知机算法

其主要思想就是依次使用各数据点, 不断以"偏差" $y_i x_i$ 纠正 $w$

算法步骤
  1. Initialize. $w=y_s x_s$, $(x_s, y_s)$ 为 $X$ 中任取的一个数据. 令 $i=1, t=0$
  2. 重复下列步骤直到 $t=T$
    1. 若 $y_i \left&lt; x_i, w \right&gt; &lt; 0$, 则 $w\leftarrow w+y_ix_i $, $t\leftarrow t+1$
    2. $i \leftarrow (i+1) % n$
  3. 返回 $w=\frac{w}{|w|}$
正确性分析
  1. $|w|^2\le t$: $w_t=w_{t-1}+y_ix_i$, 故 $$\begin{aligned} |w_t|^2 &= |w_{t-1}+y_ix_i|^2 \ &=|w_{t-1}|^2+2\left< w_{t-1}, y_ix_i \right> + |y_i x_i|^2 \ &\le |w_{t-1}|^2 + 1 \end{aligned}$$
  2. $\left< w_t, w^* \right> \ge t\gamma^$ ($\gamma^$ 是 $w^$ 对应的 Margin) $$\begin{aligned} \left< w_t, w^ \right> &= \left< w_{t-1}+y_ix_i, w^* \right> \ &= \left< w_{t-1}, w^* \right> + \left< y_ix_i, w^* \right> \ &\ge \left< w_{t-1}, w^* \right> + \gamma^* \ &\ge t\gamma^* \end{aligned}$$

因为 $|w^* |=1$, $t\gamma^* \le \left&lt; w_t, w^* \right&gt; \le \left&lt; w_t, \frac{w_t}{|w_t|} \right&gt;=\frac{|w_t|^2}{|w_t|}=|w_t| \le \sqrt{t}$, 因此只需要 $t \le \frac{1}{(\gamma^*)^2}$

因此复杂度是 $\Theta(nd\frac{1}{(\gamma^*)^2})$

SVM(Support Vector Machine)

目标是找到 Margin 最大的分类器, 离平面 $H$ 最近的数据都被称为 support vector, 其个数 $\le d+1$(意为 $d+1$ 个就能确定 d 维超平面)

凸包有 facet, 考虑把 $F_1$ 投影到 $H^-$ 得到 $\widetilde{F}_1$, 把 $F_2$ 投影到 $H^+$ 得到 $\widetilde{F}_2$. 有以下几种情况:


凸包示意图

若 $F_1 \cap \widetilde{F}_2\not=\varnothing$, 考虑 3 种情况:

  1. $F_1 \subseteq \widetilde{F}_2$. 设 $P_1$ 是 $F_1$ 中任一顶点, 若$\widetilde{P}_1 \in F_2$, 则 $\widetilde{P}_1$ 是 $F_2$ 中 $\le d$ 个点的一个凸组合.
  2. $F_2 \subseteq \widetilde{F}_1$. 类似
  3. $F_2 \not\subseteq \widetilde{F}_1$

Gilbert Algorithm for SVM

$P^+={u_1,\cdots,u_n} \subset R^d, P^-={v_1,\cdots,v_m} \subset R^d$

则 $P_1$ 能表示为 $P_1=\sum\limits_{i=1}^n\alpha_i u_i$, $\sum\limits_{i=1}^n \alpha_i=1$, $\forall \alpha_i \ge 0$ $P_2$ 能表示为 $P_2=\sum\limits_{j=1}^m\beta_j v_i$, $\sum\limits_{j=1}^n \beta_j=1$, $\forall \beta_j \ge 0$

那么 $P_1-P_2=\sum\limits_{i=1}^n \alpha_i u_i - \sum\limits_{j=1}^m \beta_j v_j=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\alpha_i \beta_j (u_i-v_j)$, 即 $P_1-P_2$ 是 ${u_i-v_j|1\le i\le n, 1\le j\le m}$(即两个凸包 minkowski difference $MD(P^+,P^-)$) 的凸组合.

$|P_1-P_2|=\min{|h||h\in Conv(MD(P+,P^-))}$, 其中 $Conv(\cdot)$ 是凸包的意思.

有了上述推导, SVM 问题就转化成为了 寻找 $Conv(MD(P^+, P^-))$ 中离原点最近的点. 这个问题被称为 Polytope Distance 问题.

Polytope Distance

$Q={q_1,\cdots,q_n}$, 目标是 $obj: |\sum\alpha_i q_i|^2$, s.t. $$\begin{aligned}\left{\begin{array}{cc}\alpha_i\ge 0 & i=1,2,\cdots,n\ \sum\limits_{i=1}^n \alpha_i = 1 \end{array}\right.\end{aligned}$$

Gilbert 算法 itself
  1. pick $q_0 \in Q$, 使之最接近原点(实际不一定要最近). 令 $x_1 = q_0$
  2. 重复以下步骤: 取 $q_i \in Q$, 满足 $proj_{\vec{x}i}(q_i)$ 最小. 令 $x{i+1}$ 为原点在 $\overline{p_i x_i}$ 的垂足.


polytope
算法证明
  1. $x_{i+1}$ 一定落在线段 $\overline{x_i q_i}$ 上. 若不成立, 则 若 $x_{i+1}$ 在 $\overline{x_i q_i}$ 延长线上, $\angle Oq_i x_i$ 为钝角(左图) 那么, $|x_i|=f_i &gt; |q_i|$, 故 $|x_i| &gt; |q_i| \ge |q_0| = |x_1|$, 这与 $|x_1|&gt;\cdots&gt;|x_i|$ 矛盾. 另外若 $\angle q_i x_i O$ 为钝角(右图), 是违背 $q_i$ 选择的条件的.

  1. 关于 $h_i=f_i - \rho$ 的变化(以定出迭代次数). 定义 $g_i=f_i-\omega_i$ $h_i-h_{i-1}=f_i-f_{i+1}=(1-\cos\alpha)f_i \ge \frac{1}{2}\sin^2\alpha f_i=\frac{1}{2}\frac{g_i^2}{|q_i-x_i|^2}f_i$ 设 $D=\max{|q_i-q_j| | q_i, q_j \in Q}$, 则由于 $|q_i-x_i|^2 \le D^2$ 且 $f_i \ge \rho$, 故 $h_i - h_{i+1} \ge \frac{1}{2}\frac{\rho}{D^2}g_i^2$

    不妨记 $h'i=\frac{\rho}{2D^2}h_i$, $g_i'=\frac{\rho}{2D^2}g_i \ge h_i'$ 则$$h_i'-h{i+1}'\ge(g_i')^2\ge(h_i')^2$$, 进而 $h_{i+1}' \le h_i'(1-h_i') \le \frac{h_i'}{1+h_i'}$

    现在用数学归纳法定出 $h_{i}'$ 的界:

    1. 初始值: $h_1'^2 \le h_1' - h_2'=\frac{\rho}{2D^2}(f_i-f_{i+1})=\frac{\rho}{2D^2}\frac{(f_i-f_{i+1})^2}{f_i+f_{i+1}} \le \frac{\rho}{4D^2}(f_i-f_{i+1})^2 \le \frac{1}{4D^2}|x_1-x_2|^2 \le \frac{1}{4}$
    2. 归纳步: $h_{i+1}'\le\frac{h_i'}{1+h_i'}$
    3. 结论: $h_k'\le\frac{1}{1+k} \Leftrightarrow h_k \le \frac{2D^2}{\rho}\frac{1}{1+k} \Leftrightarrow f_k \le \frac{2D^2}{\rho}\frac{1}{1+k} + \rho$

  2. 考虑近似比, 我们希望达到 $f_k \le (1+\epsilon)\rho$, 那么迭代次数就应当满足 $k \ge \Theta(\frac{D^2}{\epsilon \rho^2})$

  3. 同时, 为了得到离原点最近的点, 还希望 $\omega_k$ 尽可能大(因为 $\omega_k \le q_k\le$ 最小距离$\rho$, 近似比是 $\omega_i=(1-\epsilon)\rho$) 因为 $h_k'-h_{k+1}' \ge g_k'^2$, 故 $\forall t, h_k' - h_{k+t}' \ge \sum\limits_{j=1}^t g_{k+j}'^2$

    若能保证 $g_i &gt; \epsilon'=\frac{1}{\sqrt{k(1+k)}}$, 就有 $h_k'-h_{k+t}' &gt; t\cdot \epsilon'^2 = t\cdot \frac{1}{k(1+k)}$, 而 $h_k'-h_{k+t}' &lt; h_k' \le \frac{1}{1+k}$, 故这要求 $\frac{1}{1+k} &gt; t \cdot \frac{1}{k(1+k)} \Rightarrow t &lt; k$

    如果不能保证, 也就是 $t \ge k$, 这时 $\left{\begin{array}{l}g_{k+t}'\le \epsilon'=\frac{1}{\sqrt{k(1+k)}} \ h_{k+t}'\le \frac{1}{1+k+t}<\frac{1}{1+k}\end{array}\right.$, 故 $\omega_{k+t}=f_{k+t}-g_{k+t} \ge \rho - \frac{1}{\sqrt{k(1+k)}}$ (当 $t \ge k$), 这时如果我们希望 $\omega$ 接近 $\rho$, 即 $\omega_{k+t}=(1-\epsilon)\rho$, 就要求 $\sqrt{k(1+k)}\ge\frac{2D^2}{\epsilon \rho^2}$, 即 $k=\Theta(\frac{D^2}{\epsilon \rho^2})$. (这恰和考虑近似比的结果是一致的)