每週問題 March 31, 2014

這是證明半正定矩陣和 Hermitian 矩陣乘積的特徵值必為實數。

Let A and B be n\times n Hermitian matrices. Prove that following statements.

(a) If A or B is positive semidefinite, then all the eigenvalues of AB are real.
(b) If A and B are positive semidefinite, then all the eigenvalues of AB are nonnegative.

繼續閱讀

張貼在 pow 二次型, 每週問題 | 標記 , , | 發表迴響

邏輯斯迴歸

本文的閱讀等級:中級

假設我們有一筆維數等於 d,樣本大小為 n,包含 k\ge 2 個類別的數據 \mathcal{X}=\{\mathbf{x}_1,\ldots,\mathbf{x}_n\}。數據點 \mathbf{x}_1,\ldots,\mathbf{x}_n 散布在 \mathbb{R}^d 空間,以 \mathcal{C}_1,\ldots,\mathcal{C}_k 標記類別或代表類別的指標集,例如,i\in\mathcal{C}_j 表示 \mathbf{x}_i 來自 (歸屬) 第 j 類。我們的問題是利用給定的樣本 \mathcal{X},設計一個分類器;具體地說,給定一數據點 \mathbf{x},判定它應歸於何類。貝氏定理 (Bayes’ theorem) 提供了分類問題的理論基礎 (見“貝氏定理──量化思考的利器”):

\displaystyle  P(\mathcal{C}_j\vert\mathbf{x})=\frac{p(\mathbf{x}\vert\mathcal{C}_j)P(\mathcal{C}_j)}{p(\mathbf{x})},~~~j=1,\ldots,k

其中

  1. P(\mathcal{C}_j) 是類別 \mathcal{C}_j 出現的機率,稱為先驗機率 (priori probability);
  2. p(\mathbf{x}\vert\mathcal{C}_j) 是條件密度函數,即給定類別 \mathcal{C}_j,數據點 \mathbf{x} 的機率密度函數,也稱為似然 (likelihood);
  3. p(\mathbf{x}) 是數據點 \mathbf{x} 的機率密度函數,稱為證據 (evidence),算式為

    p(\mathbf{x})=p(\mathbf{x}\vert\mathcal{C}_1)P(\mathcal{C}_1)+\cdots+p(\mathbf{x}\vert\mathcal{C}_k)P(\mathcal{C}_k)

  4. P(\mathcal{C}_j\vert\mathbf{x}) 是指在給定數據點 \mathbf{x} 的情況下,該點屬於 \mathcal{C}_j 的機率,稱為後驗機率 (posterior probability)。

從機率學的觀點,貝氏最佳分類器判定數據點 \mathbf{x} 應歸屬具有最大後驗機率的類別:若 P(\mathcal{C}_l\vert\mathbf{x})=\max_{1\le j\le k}P(\mathcal{C}_j\vert\mathbf{x}),則 \mathbf{x} 歸於 \mathcal{C}_l。因為每一類別的後驗機率 P(\mathcal{C}_j\vert\mathbf{x}) 有相同的分母 p(\mathbf{x}),分類法則可改寫為:若 p(\mathbf{x}\vert\mathcal{C}_l)P(\mathcal{C}_l)=\max_{1\le j\le k}p(\mathbf{x}\vert\mathcal{C}_j)P(\mathcal{C}_j),則 \mathbf{x} 歸於 \mathcal{C}_l。對應上述最佳分類法則,分類器有兩種主要的設計方法:

  • 機率歧視模型法 (discriminative model),亦稱直接法,使用給定樣本來估計後驗機率 P(\mathcal{C}_j\vert\mathbf{x})
  • 機率產生模型法 (generative model),亦稱間接法,使用給定樣本來估計條件密度函數 p(\mathbf{x}\vert\mathcal{C}_j) 和先驗機率 P(\mathcal{C}_j)

線性判別分析 (linear discriminant analysis) 是一種間接法,它假設每一類別的數據點服從常態分布並有相同的共變異數矩陣 (見“線性判別分析”)。本文介紹與線性判別分析相對應的一種直接法,稱為邏輯斯迴歸 (logistic regression)。

繼續閱讀

張貼在 應用之道, 主題專欄 | 標記 , , , , , , , | 發表迴響

每週問題 March 24, 2014

這是一個特殊形態行列式計算問題。

Let

\displaystyle  A=\begin{bmatrix}  p_1&a&a&\cdots&a&a\\  a&p_2&a&\cdots&a&a\\  a&a&p_3&\cdots&a&a\\  \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\  a&a&a&\cdots&p_{n-1}&a\\  a&a&a&\cdots&a&p_n  \end{bmatrix}.

Show that

\displaystyle  \det A=a\sum_{i=1}^{n-1}\prod_{1\le j\le n\atop j\neq i}(p_j-a)+p_n\prod_{1\le j\le n-1}(p_j-a).

繼續閱讀

張貼在 pow 行列式, 每週問題 | 標記 | 發表迴響

線性判別分析

本文的閱讀等級:中級

在機器學習和模式識別中,分類 (classication) 可視為一種決策問題:給定一數據點,判斷它所屬的類別。本文介紹源自於統計學多變量分析的一個古典分類法,稱作線性判別分析 (linear discriminant analysis,簡稱 LDA)。就理論面來說,線性判別分析與費雪 (Ronald Fisher) 的判別分析 (一種應用於分類問題的降維方法,見“費雪的判別分析與線性判別分析”) 和邏輯斯迴歸 (logistic regression,一種應用於分類問題的非線性模型) 有著密切的關係。就應用面而言,由於線性判別分析建立於嚴苛的假設上,它的分類效能並不突出,或許因為這個緣故,線性判別分析經常被當作與其他方法比較的基準。

繼續閱讀

張貼在 應用之道, 主題專欄 | 標記 , , , , , | 2 則迴響

答Regan Yuan──關於向量範數的凸性

網友Regan Yuan留言:

老师您好,最近有些问题,还望您不吝赐教,谢谢。请问在凸优化的范畴中,范数 \ell_1 与范数 \ell_2 都是凸的(convex),这是如何证明的呢?我知道这个结论,我想学会证明的方法,了解证明的思路,请您明示。如果 f\ell_1\ell_2 的范数比值,f 是否为convex呢?怎么证明或是判断呢?如果我们将这个关系再度引申,设 f=\ell_x/\ell_y,其中 \ell_x\ell_y 是范数,如果 x=1y=2,就是上述的例子,现在 xy 均是介于 [0,+\infty),如何证明或判断 fx,y 取值于 [0,+\infty) 时的凸性呢?最近正为凸优化的问题大伤脑筋,还望老师帮我。

繼續閱讀

張貼在 特別主題, 答讀者問 | 標記 , | 發表迴響

線性變換的轉置

本文的閱讀等級:中級

A 為一 m\times n 階矩陣且 \mathbf{x}\mathbf{y}n 維向量。通過矩陣乘法,矩陣 An 維向量 \mathbf{x} 映射至 m 維向量 A\mathbf{x}。矩陣 A 一個從幾何向量空間 \mathbb{C}^n 映至 \mathbb{C}^m 的線性變換,因為矩陣乘法滿足 A(\mathbf{x}+\mathbf{y})=A\mathbf{x}+A\mathbf{y}A(c\mathbf{x})=cA\mathbf{x}c 是一純量。類似地,n\times m 階轉置矩陣 (transpose) A^T 是一個從 \mathbb{C}^m 映至 \mathbb{C}^n 的線性變換 (見“轉置矩陣的意義”)。既然矩陣是一個線性變換,我們可以反過來問:對於線性變換 T:\mathcal{V}\to\mathcal{W},其中 \mathcal{V}\mathcal{W} 是有限維向量空間,如何定義線性變換 T 的轉置變換?1970年代以前出版的線性代數教本經常從線性變換的轉置來定義矩陣的轉置[1]。這套論述固然嚴謹扎實,但必須建立在線性泛函 (linear functional) 和對偶空間 (dual space) 的基礎上,對於非數學專業的讀者多少總會增加負擔,故現今大概只有專為數學系課程撰寫的教科書才會納入這個論點[2]。在開始討論之前,我們先回顧相關的線性泛函和對偶空間的預備知識 (詳見 “線性泛函與對偶空間”)。

繼續閱讀

張貼在 線性變換, 主題專欄 | 標記 , , , , , | 發表迴響

每週問題 March 17, 2014

Let A be an n\times n Hermitian matrix with eigenvalues \lambda_i, 1\le i\le n. Prove that

(A-\lambda_1I)(A-\lambda_2I)\cdots(A-\lambda_nI)=0.

繼續閱讀

張貼在 pow 二次型, 每週問題 | 標記 | 2 則迴響

費雪的判別分析與線性判別分析

本文的閱讀等級:高級

在許多現實應用中,我們往往要面對高維度 (多變數) 數據,為便利分析,降維 (dimension reduction) 常是一個必要的前處理工作。主成分分析 (principal components analysis) 是目前普遍被採用的降維技術 (見“主成分分析”)。主成分分析是一種非教導式學習法 (unsupervised learning),完全根據樣本自身的統計性質來進行降維,並不在乎 (甚至不知道) 這些數據的後續應用。在機器學習領域,分類 (classification) 與迴歸 (regression) 是兩個最具代表性的問題描述典範。所謂分類是指識別出數據點所屬的類別。本文介紹英國統計學家費雪 (Ronald Fisher) 最早提出的一個專為包含二個類別樣本所設計的教導式 (supervised) 降維法,稱作費雪的判別分析 (Fisher’s discriminant analysis),隨後並討論三個延伸問題:

  • 甚麼是線性判別分析 (linear discriminant analysis)?它與費雪的判別分析有何關係?
  • 線性判別分析與最小平方法有甚麼關聯性?
  • 費雪的判別分析如何推廣至多類別 (類別數大於2) 判別分析?

繼續閱讀

張貼在 應用之道, 主題專欄 | 標記 , , , , , , , , | 4 則迴響

答cwj──關於奇異值分解背後的涵義

網友cwj留言:

周老師,您好!我是大陸的學生,幾乎每週都到您的“線代啟示錄”上光顧至少2次 (我是翻牆過來的,大陸這邊網路把控得很嚴)。您學問廣博,同時嚴謹而認真,真是我學習的榜樣!今天給您寫信是有一個問題要問您,我在看文獻時碰到這樣的一段描述:

Given a matrix W_{2f\times p}, decompose W into U_{2f\times K}, D_{K\times K} and V_{K\times p}^T by SVD, assuming \text{rank}(W) is K. Normalize each column of V^T . Each column unit vector \mathbf{v}_i (i=1,\ldots,p) becomes the new representation of the corresponding \mathbf{w}_i (i=1,\ldots,p) (\mathbf{w}_i is the ith column of W). This transformation is an operator that projects a \mathbb{R}^{2f} vector \mathbf{w}_i onto the \mathbb{R}^K unit sphere which preserves the subspace property, which is that any subset of \mathbf{w}_i (i=1,\ldots,p) spans a subspace of the same rank of the corresponding subset of \mathbf{v}_i (i=1,\ldots,p).

我想問的問題是:

  1. 為什麼說 \mathbf{v}_i (i=1,\ldots,p)\mathbf{w}_i (i=1,\ldots,p) 的新的表示,幾何意義我想不明白。
  2. Any subset of \mathbf{w}_i (i=1,\ldots,p) spans a subspace of the same rank of the corresponding subset of \mathbf{v}_i (i=1,\ldots,p),這個性質怎麼推導出來?

最後再次謝謝周老師!

繼續閱讀

張貼在 答讀者問, 二次型 | 標記 , , | 1 則迴響

每週問題 March 10, 2014

證明任一主對角元為零的方陣必可表示為交換子 [B,C]=BC-CB

Let A=[a_{ij}] be an n\times n matrix with a_{ii}=0 for all i. Show that there exist n\times n matrices B and C such that A=BC-CB.

繼續閱讀

張貼在 pow 線性方程與矩陣代數, 每週問題 | 標記 , | 發表迴響