跳到主要內容

發表文章

[凸分析] 凸優化最佳解所成之集合為凸集

下面的結果刻劃了凸優化最佳解的性質,常被用來檢驗最佳解的存在性,是個十分有用的結果。


Theorem: (凸優化最佳解的集合為凸集)
令 $S \subseteq \mathbb{R}^n$ 為 凸集合 且 $f: S\to \mathbb{R}$ 為 凸函數。令 $S^*$ 為所有極小點所成之集合亦即
\[
S^* := \{x\in S: f(x) \leq f(y), \forall \; y \in S\; \}
\] 則 $S^*$ 為凸集。

Proof: 若 $S^* = \emptyset$ 則上述定理陳述自動成立。若 $S^* \neq \emptyset$,則存在 $x_0 \in S^*$。考慮 level set
\[
S_{\leq f(x_0)} := \{x\in S: f(x) \leq f(x_0)\}
\] 則不難驗證 $S_{\leq f(x_0)} = S^*$。接著由下述 Lemma 可知 $S^*$ 為 convex。至此證明完畢。$\square$


Lemma: 令 $S \subseteq \mathbb{R}^n$為凸集,且 $f:S \to \mathbb{R}$  為凸函數。則對任意 $\alpha \in \mathbb{R}$, (lower) level set
$$
S_{\leq \alpha}:= \{x \in \mathbb{R}^n: f(x) \leq \alpha\}
$$ 為 凸集。

Proof: 若 level set $S_{\leq \alpha}$ 為空集合或者單點集,則陳述自動成立。若不然,取 $x_1,x_2 \in S_{\leq \alpha}$ ,則 $f(x_1) \leq \alpha$ 且 $f(x_2) \leq \alpha$。我們要證明 convex combination of $x_1$ 與 $x_2$ 仍落在 $S_{\leq \alpha}$ 之中:由 $f$ 的凸性,我們看可之對任意 $\lambda \in (0,1)$,
\[
f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) \leq \alpha
\]故 $\lambda x_1 + (1-\lambda…
最近的文章

[機器學習] 主成分分析 (1)

以下我們介紹機器學習/統計學習理論 中把 高維度資料 降維 的一種常用工具,稱作 主成分分析 (Principal Component Analysis)。假設我們有 $n$ 組 $m$ 維度 (去除平均) 資料點集,下圖 顯示 $n=100$ 組 $m=2$ 維 資料點集

注意到上述資料集已經先預先處理使其資料集 中心 在 $(0,0)$。任意(有限維度)資料集皆可預先做此處理將其資料點的平均值 預先 移除。此為主成分分析的首要步驟。


主成分分析(Principal Component Analysis):
我們的目標為 找到一個向量 ${\bf x} \neq {\bf 0}$ 使得 由此向量所 線性張成(span) 的子空間,記作 $X:=span\{{\bf x}\}$ ,能 最佳適配我們得資料集 (此 subspace $X$ 又稱作 "best line ") 使得\[
\min_{\bf x} \sum_{i=1}^n d_i^2
\]其中 $d_i$ 為第 $i$ 個 資料點 到此  best line (subspace) $X$ 的距離。

Comments: (1) 此處最佳 "best line" 意指我們要找 ${\bf x}$ 使得 資料點到此 best line 的距離平方最小,此想法可參閱下方示意圖,其中 ${\bf a}_i$ 為代表 第 $i$ 個資料點的向量,$proj_X{\bf a}_i$ 代表 ${\bf a}_i$ 投影到 我們的 subspace $X$ 的投影向量。

(2) 當然,距離平方最小並不是唯一的選擇,讀者可以考慮使用 $\sum_i |d_i|$ 當作 最佳化的目標函數或者其他種類的目標函數,但為求簡單起見,且符合經典 主成分分析的內容,在此我們僅考慮 距離平方誤差 作為我們的 目標函數。

(3) 由下圖,讀者不難發現對任意資料向量 ${\bf a}_i$ 而言,此向量 與 subspace $X$ 的 距離平方 $d_i^2$ 可表為
\[
d_i^2  = \| {\bf a}_i - proj_X {\bf a}_i \|_2^2
\]其中 $proj_X {\bf a}_i$ 表示 ${\bf a}_i$ 投影到 subspace $X$ 的向量 。


Claim:

[線性代數] 一類含有反矩陣的等式

Claim:
令 $A \in \mathbb{R}^{m \times n}$,且 $\lambda >0$ 則以下等式成立
\[
(A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1}
\]

Proof: 觀察 $A^TAA^T+\lambda A^T$ 可對其從左方或者右方提出 $A^T$,亦即
\[\begin{align*}
A^T(AA^T+\lambda I) = (A^TA+\lambda I)A^T
\end{align*}\]由於 $(AA^T +\lambda I)$ 為可逆,$(AA^T+\lambda I)^{-1}$存在,故對上式兩邊從右方同乘此項可得
\[
A^T = (A^TA+\lambda I)A^T(AA^T+\lambda I)^{-1}
\]又注意到 $(A^TA+\lambda I)$ 為可逆,$(A^TA+\lambda I)^{-1}$存在,對上式從左方同乘此項可得
\[
(A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1}
\]至此證明完畢。$\square$


Comments:
上述結果多出現於一類稱作 Tikhonov Regularization (或者有拘束的最小二乘方問題)問題之中:亦即令 $A \in \mathbb{R}^{m \times n}$ 且 ${\bf x},{\bf y}\in \mathbb{R}^{n}$,$\lambda >0$考慮
\[
\min_{\bf x}\|A{\bf x} - {\bf y}\|_2^2 + \lambda \|{\bf x}\|_2^2
\]則不難證明上述最佳化問題之解為
\[
{\bf x}= (A^TA+\lambda I)^{-1}A^T {\bf y}  = A^T(AA^T+\lambda I)^{-1}{\bf y}
\]上述第二等式成立因為 前述 claim。故我們在實際計算反矩陣時,可以決定到底要用 哪一個 inverse來加速計算速度,比如 $A \in \mathbb{R}^{5000\times 100}$ 那麼 $(A^TA+\lambda I)^{-1}$ 要求對 $100\times 100$ 矩陣做 反矩陣,但是 $(…

[機器學習] 回歸問題應用例:Dow Jones 指數的 回歸模型估計

考慮歷史 Dow Jones 指數如下圖所示


令 $v(t)$ 表示 從1795年到 2019年每年的 Dow Jones 指數其中 $t=1,1,\ldots,T$ 且 $t=1$表示 1795年,$t=T$表示至今 (上圖為2019年,但任意年皆可)。由上圖,我們假設 $v_t$ 可由以下 指數函數 近似:亦即  $v: \mathbb{N} \to \mathbb{R}$ 滿足
\[
v(t):= e^{at+b}
\]其中  $t=1,...,T$,$a,b$ 為 待估計參數。我們想問是否能找出 $a,b$ 使得我們可以用此模型來預估未來 Dow Jones 指數的走向:

上述問題可化簡為回歸問題。首先對 $v_t$ 等式兩邊同取 $\log$,我們可得
\[
\log v(t) = at+b
\]故對任意 $t=1,...,T$我們有
\[
\begin{bmatrix}\log v(1)\\\log v(2)\\ \vdots \\ \log v(T) \end{bmatrix} = \begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1  \end{bmatrix} \begin{bmatrix} a\\b\end{bmatrix}
\]
令  ${\bf x}=[a \;\; b]^T$,${\bf b}=\begin{bmatrix}\log v(1) & \log v(2) & \vdots \log v(T) \end{bmatrix}^T$ 且 $$A:=\begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1  \end{bmatrix} \in \mathbb{R}^{T \times 2} $$ 則我們得到 $
A{\bf x} = {\bf b}
$ 。由於 $T>>2$,方程 $A{\bf x} = {\bf b}$無解 (參閱 comment 2),但我們可問是否有近似解。為此, 欲求解 ${\bf x}$ 一種常見的手段是採用最小平方法:考慮以下無拘束最小平方最佳化問題
\…

[線性代數] 構造 正定矩陣 其元素含有負值的例子

首先回憶 正定 (positive definite)矩陣 定義:

Definition: 令 $Q \in \mathbb{R}^{n\times n}$且 $Q^T=Q$。我們說 $Q$ 為 positive definite 若下列條件成立: 對任意 ${\bf x} \in \mathbb{R}^n$ 且 ${\bf x} \neq {\bf 0}$,
$$
{\bf x}^TQ{\bf x}>0
$$


我們想問是否有可能構造出一正定矩陣其部分元素取值為負。答案是肯定的。請看以下例子:

==============
Example: 
令 $Q = \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix}$。試証 $Q$ 為 positive definite。
================

Proof: 首先注意到 $Q^T=Q$ 為顯然。故我們僅需証明 對任意 ${\bf x} \neq 0$, ${\bf x}^TQ{\bf x}>0。$為此,取${\bf x}=[x_1\;\;x_2]^T$ 且 $x_1,x_2$不全為零, 觀察
$$
{\bf x}^TQ{\bf x} = [x_1 \;\; x_2]  \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix}x_1\\x_2 \end{bmatrix} = 2x_1^2+2x_2^2-2x_1x_2$$上述稱為 矩陣二次式(quadratic form)。

以下我們分幾個情況討論:

Case 1: 若 $x_2 \neq 0$ 且 $x_1 \neq 0$:
若 $x_1\geq x_2$ ,則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_2^2>0$
若 $x_2 \geq x_1$,則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_1^2>0$

Case 2: 若 $x_2 \neq 0$ 且 $x_1 = 0$:則我們有
$$
 2x_1^2+2x_2^2-2x_1x_2 = 2x_2^2 > 0
$$

Case 3: 若 $x_1 \neq 0$ 且 $x_2 = 0$:則我們有
$$
 2x_…