超平面

本文的閱讀等級:初級

在最佳化與機器學習領域,譬如線性規劃、線性判別分析 (linear discriminant analysis)、Logit 模型 (logistic regression) 和多層類神經網路 (multilayer network),超平面 (hyperplane) 是一個常見的模型元件。許多最佳化方法,如梯度下降法、Lagrange 乘數法和對偶理論,也都與超平面有關。本文從幾何與代數兩種觀點介紹超平面的基礎知識,並以凸集為例說明超平面於分割向量空間的應用 (見“凸組合、凸包與凸集”)。

 
在三維空間中,一平面上的所有點 (x,y,z) 受方程式 ax+by+cz=d 規範。推廣至一般幾何座標空間 \mathbb{R}^n,超平面定義為下列線性方程的所有解 \mathbf{x}=(x_1,\ldots,x_n)^T 形成的集合:

a_1x_1+\cdots+a_nx_n=d

其中 a_1,\ldots,a_n 是不全為零的實數,d 也是實數。給定 \mathbf{a}=(a_1,\ldots,a_n)^T,超平面 H 的向量表達式即為

H=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}=d\}

除了上面的代數定義,超平面還有等價的幾何定義。若 W\mathbb{R}^n 的一個子空間,W 自原點平移 \mathbf{q} 後所成的集合 S 稱為仿射空間 (affine space,見“仿射組合與仿射空間”),記作

S=W+\mathbf{q}=\{\mathbf{w}+\mathbf{q}\vert\mathbf{w}\in W\}

因為仿射空間 S 由子空間 W 生成,我們指定 S 的維數等於 W 的維數。在 \mathbb{R}^n 中,超平面是一個維數等於 (n-1) 的仿射空間。換句話說,除了 \mathbb{R}^n 本身,超平面是具有最大維數的仿射空間 (見下圖)。

Hyperplane

超平面

 
超平面的代數定義等價於幾何定義,論證於下。

代數定義\Rightarrow幾何定義:設 H=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}=d\}\mathbf{a}\neq\mathbf{0}。令 \mathbf{q}H 中任一向量。將 H 平移 -\mathbf{q} 可得一向量集 H_0=H-\mathbf{q}。對於任一 \mathbf{y}\in W\mathbf{y}+\mathbf{q}\in H,即有 \mathbf{a}^T(\mathbf{y}+\mathbf{q})=d。但 \mathbf{a}^T\mathbf{q}=d,可知 \mathbf{a}^T\mathbf{y}=0,表明 H_01\times n 階非零矩陣 A=\begin{bmatrix}  a_1&\cdots&a_n  \end{bmatrix} 的零空間。因為 \hbox{rank}A=1,根據秩—零度定理 \hbox{rank}A+\dim N(A)=n,可知 \dim H_0=\dim N(A)=n-1,即證明 H 是一個 (n-1) 維仿射空間。

幾何定義\Rightarrow代數定義:設 H 是一個維數等於 (n-1) 的仿射空間。考慮 \mathbf{q}\in H,將 H 平移 -\mathbf{q} 得到 H_0=H-\mathbf{q};由仿射空間的定義可知 H_0 是一 (n-1) 維子空間。令非零向量 \mathbf{a} 屬於正交補餘 H_0^{\perp},其維數等於 1。據此,H_0=\{\mathbf{x}\in\mathbb{R}^n\vert \mathbf{a}^T\mathbf{x}=0\}。令 d=\mathbf{a}^T\mathbf{q}。對於任一 \mathbf{z}\in H\mathbf{z}-\mathbf{q}\in H_0 同義於 \mathbf{a}^T(\mathbf{z}-\mathbf{q})=0,也就有 \mathbf{a}^T\mathbf{z}=d,意味 H\subseteq\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}=d\}。因為 \dim H=n-1,上半部證明已確定 \{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}=d\} 的維數等於 (n-1),故證明兩向量集相等。

 
接著說明超平面的一些幾何性質。我們知道 \mathbb{R}^3 的一平面將空間分割為兩個半空間 (half space)。同樣地,超平面 H=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}=d\}\mathbb{R}^n 分成閉 (closed) 正半空間與閉負半空間,表示如下:

H^+=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}\ge d\},~~H^-=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}\le d\}

若等號不成立,則有開 (open) 正半空間與開負半空間:

\tilde{H}^+=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}> d\},~~\tilde{H}^-=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}< d\}

明顯地,H^+H^- 的聯集即為 \mathbb{R}^n,且 H\tilde{H}^+ 以及 \tilde{H}^- 的聯集也為 \mathbb{R}^n。超平面 H 的方向 (orientation) 由法向量 \mathbf{a} 決定,H 至原點的距離則與純量 d 有關。令 \mathbf{z}\in H 為距離原點最近的點。根據正交原則,\mathbf{z} 必位於穿越原點,指向方向為 \mathbf{a} 的直線上,因此 \mathbf{z}=c\mathbf{a}。(另一個說法,\mathbf{z}H 中任一點至法向量 \mathbf{a} 的正交投影。) 將上式代入超平面表達式,d=\mathbf{a}^T\mathbf{z}=c\Vert\mathbf{a}\Vert^2,可得 c=d/\Vert\mathbf{a}\Vert^2。所以 \mathbf{z}=d(\mathbf{a}/\Vert\mathbf{a}\Vert^2)H 至原點的距離即為 \Vert\mathbf{z}\Vert=\vert d\vert/\Vert\mathbf{a}\Vert

 
超平面常應用於分離 \mathbb{R}^n 的向量集。定理一說,給定凸集外的任一點,必存在一穿越該點且不與凸集相交的超平面[1]

定理一:若 K 為一有界 (bounded) 閉凸集,且 \mathbf{p}K 之外的一點,則存在一向量 \mathbf{a} 使得 \mathbf{a}^T\mathbf{p}<\inf_{\mathbf{x}\in K}\mathbf{a}^T\mathbf{x}[2]

因為 \mathbf{p}K 之外的點,故可令 \delta=\inf_{\mathbf{x}\in K}\Vert\mathbf{x}-\mathbf{p}\Vert>0。設 \mathbf{x}_0 位於 K 的邊界使得 \Vert\mathbf{x}_0-\mathbf{p}\Vert=\delta。下面我們證明 \mathbf{a}=\mathbf{x}_0-\mathbf{p} 滿足命題條件。對於 \mathbf{x}\in K0\le\alpha\le 1,由凸集定義可知點 \alpha\mathbf{x}+(1-\alpha)\mathbf{x}_0 屬於 K,即有

\Vert\mathbf{x}_0+\alpha(\mathbf{x}-\mathbf{x}_0)-\mathbf{p}\Vert^2\ge\Vert\mathbf{x}_0-\mathbf{p}\Vert^2

展開可得

2\alpha(\mathbf{x}_0-\mathbf{p})^T(\mathbf{x}-\mathbf{x}_0)+\alpha^2\Vert\mathbf{x}-\mathbf{x}_0\Vert^2\ge 0

\alpha\to 0^+,上式通除以 \alpha,可得

(\mathbf{x}_0-\mathbf{p})^T(\mathbf{x}-\mathbf{x}_0)\ge 0

乘開化簡,

\begin{aligned}  (\mathbf{x}_0-\mathbf{p})^T\mathbf{x}&\ge(\mathbf{x}_0-\mathbf{p})^T\mathbf{x}_0\\  &=(\mathbf{x}_0-\mathbf{p})^T\mathbf{p}+(\mathbf{x}_0-\mathbf{p})^T(\mathbf{x}_0-\mathbf{p})\\  &=(\mathbf{x}_0-\mathbf{p})^T\mathbf{p}+\delta^2.\end{aligned}

\mathbf{a}=\mathbf{x}_0-\mathbf{p} 即證得所求。

 
從幾何面來看,定理一宣稱給定凸集 K 之外的一點 \mathbf{p},我們可以找到一穿越 \mathbf{p} 的超平面 H,稱為分離 (separating) 超平面,使得凸集 K 被超平面的一個開半空間 \tilde{H}^+\tilde{H}^- 所包含 (見下圖左)。設想點 \mathbf{p} 朝凸集 K 移動,超平面也隨之漸進移動。在連續的改變過程中,當 \mathbf{p} 位於 K 的邊界時,必存在一支持 (supporting) 超平面,意思是 H 不僅穿越 K 的一個邊界點,而且 KH 的一個閉半空間 H^{+}H^{-} 所包含 (見下圖右)。我們將這個結果放在下面的定理。

定理二:若 K 為一有界閉凸集且 \mathbf{p}K 的一邊界點,則必存在一支持超平面穿越點 \mathbf{p}

Separating and supporting hyperplanes

分離超平面與支持超平面

 
超平面所定義的半空間是凸集,多個閉半空間的交集也是一凸集,稱為多胞形 (polytope)。此類特殊凸集出現在各式各樣的應用中,譬如,線性規劃和賽局理論 (game theory)。這個主題將留待他日另文介紹。

 
來源與註解:
[1] 定理與證明取自 David G. Luenberger 所著 Linear and Nonlinear Programming,第二版,1984, 頁466-470。
[2] \inf 表示最大下界 (infimum) 而非極小值 (minimum)。兩者的差異在於最大下界必定存在,極小值則未必存在。譬如,S=\{x\in\mathbb{Q},~x>0\} 是正有理數集合,S 不存在最小值,但 \inf S=0

Advertisements
本篇發表於 線性代數專欄, 仿射幾何 並標籤為 , 。將永久鏈結加入書籤。

17 則回應給 超平面

  1. 張盛東 說道:

    妄自猜測一下,老師最近的一系列文章都應該是為simplex method做準備吧?

  2. 陳威丞 說道:

    老師~~請問一下您有email嗎~~
    我有關於待四函數如何證明是為正負定or不定矩陣的問題想要請教老師~~
    但這裡沒有辦法複製上去,所以我想要電子郵件的方式寄給老師,再給我一點方向~~
    我的email:flymancarter@gmail.com

  3. 陳威丞 說道:

    老師我大概看了一下依然有以下一些小問題~~
    1.因為我想要知道的是否為全域極大,且式子中的阿法跟貝塔和嘎瑪都為向量所以是否有一個矩陣表示的hessian矩陣可以說明~~??
    2.若矩陣A為對稱矩陣則其特性向量所形成之矩陣亦為對稱!!??

  4. 陳威丞 說道:

    謝謝老師~~
    問題已解決~~感恩nn

  5. 張盛東 說道:

    老師,最近我在看統計學習的書籍中的分類問題,有一個疑問:應該如何判斷某一數據集合是否線性可分?不知到這個問題是否已經有解答,但我有的書中沒找到相關信息,望老師指點。

    • ccjou 說道:

      判定一組數據集是否線性可分(LS)並不是一件非常容易的事。下文列舉了一些測試方法,但未必總是有效:
      http://sci2s.ugr.es/keel/pdf/specific/articulo/IEEETNN06.pdf

      以文中提到的neural networks(應該稱Perceptron)來說,若數據集是LS,則保證學習過程於有限次數停止並可得到一分割超平面。但若數據集是NLS,則學習過程不可能停止,這時我們又如何確定究竟是學習尚未結束(LS情況),還是根本就永不停止(NLS情況)?

      近期我會另文介紹一些以超平面為判別函數(discriminant functions)的線性分類法。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s