超平面

Posted on 05/14/2013 by ccjou

本文的閱讀等級：初級

在最佳化與機器學習領域，譬如線性規劃、線性判別分析 (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_0 是 1\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 K 且 0\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 的一個邊界點，而且 K 被 H 的一個閉半空間 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。

This entry was posted in 線性代數專欄, 仿射幾何 and tagged , . Bookmark the permalink.

17 Responses to 超平面

  1. 張盛東 says:
    05/14/2013 at 11:34 pm

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

    Reply
    • ccjou says:
      05/15/2013 at 7:18 am

      是的。先前我在

      線性規劃 (一)：標準型問題


      底下有云：

      在討論可行解集合(滿足所有約束等式與不等式的解)的性質與單形法之前，我們最好先瞭解一些線性代數很少討論的向量空間幾何知識，如凸組合、超平面和多胞形(polytope)。所以等我寫完這些介紹文之後才會有線性規劃(二)。

      Reply
      • 張盛東 says:
        05/15/2013 at 10:15 am

        這樣太好了。我看了不少關于線性規劃的課程，無論是美國的還是大陸的，都很少從這個角度講述線性規劃，大部分都只關于如何建模或者解題。從線性代數角度講述這個主題的，就我所見過的課程就只有convex programming了，但這個課程應該是屬于EE的研究生課程吧。

        Reply
        • ccjou says:
          05/15/2013 at 2:34 pm

          別的學校我不清楚，交大電控所開授的Optimization Theory不討論Linear Programming，內容集中在向量空間方法。

          Reply
  2. 陳威丞 says:
    05/15/2013 at 4:50 pm

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

    Reply
  3. 陳威丞 says:
    05/18/2013 at 10:51 pm

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

    Reply
  4. 陳威丞 says:
    05/20/2013 at 8:52 am

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

    Reply
  5. 張盛東 says:
    08/26/2013 at 6:49 am

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

    Reply
    • ccjou says:
      08/26/2013 at 9:03 am

      判定一組數據集是否線性可分(LS)並不是一件非常容易的事。下文列舉了一些測試方法，但未必總是有效：

      Click to access IEEETNN06.pdf

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

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

      Reply

Leave a reply to ccjou Cancel reply