cs131課程筆記（8）

05-23

cs131課程筆記（8）

Lecture_12 人臉識別和特徵壓縮

1.SVD分解。任意一個矩陣可以分解為 $extbf{A}= extbf{U}Sigma extbf{V}^T$ ，其中， $extbf{U}, extbf{V}$ 為旋轉矩陣，即 $extbf{U}^T extbf{U}= extbf{I}$ $Sigma$ 為只有對角元素不為0的矩陣。

2.SVD分解中， $extbf{A}= extbf{U}Sigma imes extbf{V}^T$ ，設 $extbf{U}Sigma=(p_1,p_2,...,p_m), extbf{V}^T=(q^T_1,q^T_2,...,q^T_m)^T$ ，其中， $p_i$ 為 $n imes1$ 的列向量， $q_i$ 為 $1 imes{m}$ 的行向量。那麼表達式可以寫為 $extbf{A}=sum_{i=1}^{m}{p_icdot{q_i}}$ ，而 $extbf{U}Sigma=(p_1,p_2,...,p_m)=(u_1,u_2,...,u_m)egin{pmatrix}v_1&0&...&0\ 0&v_2&...&0\ 0&...&...&0end{pmatrix}=(v_1u_1,v_2u_2,...,v_mu_m)$ ，因為 $extbf{U}$ 是旋轉矩陣，列向量模為1，當奇異值 $v_i$ 非常小時， $p_i$ 也會非常小，導致對矩陣 $extbf{A}$ 的貢獻非常小，可以省略。因此可以取奇異值最大的前幾個分量，捨去奇異值小的分量對應的 $extbf{U}, extbf{V}^T$ ，這樣壓縮了空間同時不會造成較大的失真。

3.SVD計算。 $extbf{A} extbf{A}^T$ 的特徵值開根號就是 $extbf{A}$ 的奇異值；特徵向量就是 $extbf{U}$ 的列向量。 $extbf{A}^T extbf{A}$ 的列向量就是 $extbf{V}$ 的列向量。

4.PCA（主成分分析）。也是機器學習里天天見到的演算法了，簡單介紹下。

訓練：

對於訓練數據集 $mathbb{D}={x_1,...,x_n},x_iin{mathbb{R}^d}$ 。

1）計算均值： $hat{mu}=frac{1}{n}sum_i{x_i}$

2）計算協方差： $hat{Sigma}=frac{1}{n}sum_i{(x_i-hat{mu})}(x_i-hat{mu})^T$

3）計算 $hat{Sigma}$ 的特徵值 $hat{Sigma}=PhiLambdaPhi^T,Lambda=diag(sigma^2_1,...sigma^2_n),Phi^TPhi=I$

4）將特徵向量從小到大排序

5）保留前 $k$ 個特徵值和特徵向量，其餘的捨去。

測試：

對於測試集 $mathbb{T}={t_1,...,t_n},t_iin{mathbb{R}^d}$ 。

1）減去均值： $t_i=t_i-hat{mu}$

2）投影到低維： $y_i=At_i,A=egin{pmatrix}phi^T_1\...\phi^T_k\end{pmatrix}$

5.用SVD算PCA。在訓練的第二步中， $hat{Sigma}=frac{1}{n}sum_i{(x_i-hat{mu})}(x_i-hat{mu})^T=frac{1}{n}(x^c_1,...x^c_n)(x^c_1,...x^c_n)^T=frac{1}{n}X_cX^T_c$ ，對 $X_c$ 做SVD，則 $X_c=UPi{V^T},hat{Sigma}=frac{1}{n}UPi^2V^T$ ，對應的特徵向量為 $U,V^T$ ，特徵值為 $lambda_i=frac{1}{n}pi^2_i$ 。

6. $k$ 的選取。選擇解釋了 $p\%$ 的數據變化的 $k$ ，可以用比例 $r_k=frac{sum^k_{i=1}lambda^2_i}{sum^n_{i=1}lambda^2_i}$ 來求。

7.圖像壓縮。把圖像分成小的網格，比如分成12x12的小格子（無重疊），每個小格子可以看做是144維的數據，然後對其做PCA。

Lecture_13 人臉識別

1.假設有張100x100的圖像，那麼可以看作是一個10000維的特徵空間，將其用坐標表示需要1000個互不相關的基才能張成這個空間，而其中人臉是這個特徵空間內的一個子空間，因此我們想找到一個特徵子空間，這個子空間里的基可以很好的表示人臉，而這個方法就是pca。

2.eigenfaces演算法

訓練：

1）將 $N$ 張人臉圖像對齊，然後按照像素拉平成 $n imes{m}$ 維的向量 $(x_1,...,x_N),x_iinmathbb{R}^{mn}$ 。

2）去均值，求協方差，求協方差的特徵值和特徵向量，取前 $k$ 大的特徵值對應的特徵向量作為人臉子空間的一組基 $(phi_1,...,phi_k)$ 。

3）計算每個訓練圖像 $x_i$ 在這組基下的坐標 $(a_1,...,a_k)=(x^c_1cdotphi_1,...,x^c_kcdotphi_k)$ 。

4）可視化訓練的人臉 $x_i=mu+a_1phi_1+...+a_kphi_k$ 。

測試：

1）取測試圖像 $t$ 。

2）投影到人臉空間計算坐標 $(w_1,...,w_k)=((t-mu)cdotphi_1,...,(t-mu)cdotphi_k)$ 。

3）根據這個坐標與訓練樣本做k近鄰，度量準則用歐式距離，得到測試人臉對應的人。

3.eigenfaces優點：不用迭代，全局最優解。缺點：人臉需要在中心且大小一致，對角度敏感；從低維重建是最優的，但對於分辨力（discrimination）來說不是最優的。

4.LDA(Linear Discriminant Analysis)。也是一種投影降維的方式，但是主要保存差異性，找到最大化類間距離，最小化類內距離的投影。如圖所示，PCA是最大方差，LDA是最大分類差異。

5.考慮用LDA將二維點投影到一維點上， $z=w^Tx,zinmathbb{R}^1,xinmathbb{R}^2$ , $w$ 為投影矩陣。設每一類的樣本均值為 $E_{X|Y}[X|Y=i]=mu_i$ ，每一類的類內協方差為 $E_{X|Y}[(X-mu_i)(X-mu_i)^T|Y=i]=Sigma_i$ ，我們的目標函數為 $J(w)=maxfrac{類間差異}{類內差異}=frac{(E_{Z|Y}[Z|Y=1]-E_{Z|Y}[Z|Y=0])^2}{var[Z|Y=1]+var[Z|Y=0]}$ 。其中分子可以表示為 $(E_{Z|Y}[Z|Y=1]-E_{Z|Y}[Z|Y=0])^2=(w^T[mu_1-mu_0])^2\ =w^T[mu_1-mu_0][mu_1-mu_0]^Tw$ 分母可以表示為 $egin{align} var[Z|Y=i]&=E_{Z|Y}{(z-E_{Z|Y}[Z|Y=i])^2|Y=i}\ &=E_{Z|Y}{(w^T[x-mu_i])^2|Y=i}\ &=w^TSigma_i{w} end{align}$

所以，優化目標可以寫為 ${max}J(w)=frac{w^T(mu_1-mu_0)(mu_1-mu_0)^Tw}{w^T(Sigma_1+Sigma_0)w}=frac{w^TS_Bw}{w^TS_Ww}$ .

這個目標函數等價於 $max_ww^TS_Bw,s.t.w^TS_Ww=K$ ,然後用拉格朗日乘子法 $L=w^TS_Bw-lambda(w^TS_Ww-K)\ riangledown_wL=2(S_B-lambda{S_W})w=0\ S_Bw=lambda{S_Ww},假設S_W^{-1}存在\ S^{-1}_W(mu_1-mu_0)(mu_1-mu_0)^Tw=lambda{w}\ S^{-1}_W(mu_1-mu_0)=frac{lambda}{alpha}w\ w^*=S^{-1}_W(mu_1-mu_0)=(Sigma_1+Sigma_0)^{-1}(mu_1-mu_0)$

其中 $alpha=(mu_1-mu_0)^Tw$ 是一個數值，而 $w$ 前面的係數我們並不關心。

6.當有 $N$ 個變數和 $C$ 個類時， $S_W=sum^C_{i=1}S_i$ , $S_B=sum^c_{i=1}N_i(mu_i-mu)(mu_i-mu)^T,mu=frac{1}{N}sum_{i=1}^Nx_i$ ，解為 $S_Bw_i=lambda_iS_Ww_i,i=1,...,m$ 。

7.總體來說LDA性能比PCA要好。