|
|
|
發新文章 |
|
 |
Matrix power A^B mpower(A,B)
Arraywise power A.^B power(A,B)
如果求矩陣A的1/2次方，即用A^(1/2) mpower(A,1/2)； 不能用sqrt(A),查sqrt的幫助即知是對每個元素開根，等同于A.^(1/2)或者 power(A,1/2)
SDP的標準形式見 Fast Low-Rank Semidefinite Programming for Embedding and Clustering的公式(1)。半正定規劃是一個凸優化問題
以Distance Metric Learning for Large Margin Nearest Neighbor Classification該文為代表的Metric Learning 用SDP求解。Matrix completion也有用SDP求解
SDP的問題：大家都知道很慢，離實用很遠。只要做SDP都是說我們的方法比現有的很快，Ling Zhu實驗發現快不了多少。SDP的工具包很多，Boyd(凸優化教材作者)主頁，總結了以下，Ling Zhu說幾個包能夠自適應選擇哪個包
(1)在JCR查詢中，搜索Title Word: IEEE Transactions on發現有69個雜志
IEEE-ACM Transactions on Computational Biology and Bioinformatics 不在上述范圍之類
(2)如何查找相關的Society？
以IEEE Transactions on Image Processing為例，搜索到其主頁，上面有Published by: IEEE Signal Processing Society
以IEEE Transactions on Knowledge and Data Engineering為例，搜索到其主頁，上面有Published by: IEEE Computer Society
做下一筆記
wiki里面的定義 http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation
關鍵所在：it posits that each document is a mixture of a small number of topics and that each word's creation is attributable to one of the document's topics。
將文檔看成是一組主題的混合，詞有分配到每個主題的概率。
Probabilistic latent semantic analysis（PLSA） LDA可以看成是服從貝葉斯分布的PLSA
|
matlab中，每個figure都有（而且僅有）一個colormap，翻譯過來就是色圖。
COLORMAP(MAP) 用MAP矩陣映射當前圖形的色圖。
COLORMAP('default') 默認的設置是 JET.
MAP = COLORMAP 獲得當前色圖矩陣.
COLORMAP(AX,...) 應用色圖到AX坐標對應的圖形，而非當前圖形。
MAP實際上是一個mx3的矩陣，每一行的3個值都為0-1之間數，分別代表顏色組成的rgb值，
[1 0 0] 代表紅色，[0 1 0]代表綠色，[0 0 1]代表藍色。系統自帶了一些colormap，如：winter、autumn等。輸入winter，就可以看到它是一個64x3的矩陣。用戶可以自定義自己的colormap，而且不一定是64維的。
[0 0 0] is black, [1 1 1] is white,
[1 0 0] is pure red, [.5 .5 .5] is gray, and
[127/255 1 212/255] is aquamarine.
那么顏色在fill或patch，SURFACE等函數中到底是如何顯示的呢？本質上，是把具體的顏色變成colormap中的相應index，也就是行數。這個過程叫做換算映射：將指定的數值顏色向量（矩陣）C，映射到對應的顏色。顏色矩陣C的數值范圍為[Cmin, Cmax], Cmin 和Cmax的數值或者為
min(min(C)) max(max(C))，也可以在CAXIS中設置。
在matlab中，圖形窗的屬性'CdataMapping‘缺省設置值為'scaled'，也就是線性的映射。
Cmin對應的值映射到colormap的第一行，Cmax對應的值映射到colormap的最后一行。
映射過程如下：
首先，需要根據caxis取得Cmin和Cmax兩個變量（默認值為0和1），畫圖時如果指定了數值顏色向量（矩陣）C，Cmin和Cmax自動設置為C中的最大值和最小值。當你想控制時，可以自定義。比如將Cmax減小，這樣將把所有大于Cmax的C值，全部都映射到同一個顏色（colormap 中index最大的行代表的顏色）。
根據Cij在Cmin和Cmax之間的比例關系，確定對應的顏色的index，默認為線性映射。
也就是說，當制定了數值顏色向量（矩陣）C之后畫圖，圖中顏色的使用范圍會自動占滿整個顏色范圍！
實例：
clc;
clear all;
x=[0 1 1 0];
y=[0 0 1 1]; %定義四個點 [0 0] [1 0] [1 1] [0 1]
H_F=fill(x,y,[0 0.1 0.2 0.6]); %定義四個點的C值
row_cmap = 15; %定義色圖矩陣的行數
color_map1=zeros(row_cmap,3); %定義色圖矩陣
color_r = 0:1/(row_cmap-1):1;
color_g = 0:1/(row_cmap-1):1;
color_b = 0:1/(row_cmap-1):1;
color_map1(:,1) = color_r;
color_map1(:,2) = color_g;
colormap(color_map1);
colorbar;
%本例中顏色從[0 0 0] 變化到[1 1 0]
%增加row_cmap的值，如變化到100，則可看到顏色的漸變，而非跳躍型變化。
|
| 本文引用地址： http://www.sciencenet.cn/m/user_content.aspx?id=281377 |
摘要: 理解矩陣（一）
前不久chensh出于不可告人的目的，要充當老師，教別人線性代數。于是我被揪住就線性代數中一些務虛性的問題與他討論了幾次。很明顯，chensh覺得，要讓自己在講線性代數的時候不被那位強勢的學生認為是神經病，還是比較難的事情。
可憐的chensh，誰讓你趟這個地雷陣？！色令智昏??！
線性代數課程，無論你從行列式入手還是直接從矩陣入手，從一開始就充斥著莫名其妙。比... 閱讀全文
(1)Dimensionality Reduction: A Comparative Review的P15頁The presence of free parameters has both advantagesand disadvantages. The main advantage of the presence of free parameters is that they provide more flexibility to the technique, whereas their main disadvantage is that they need to be tuned to optimize the performance of the dimensionality reduction technique.
(2)Zhongqiu Zhao's Ph.D. thesis P87:雖然此參數可能會給半監督學習帶來可靈活機動的好處，但是同時它也增加了程序調試的難度。
(3)Fei Wang's Ph.D. thesis P13:圖上半監督學習算法大都需要用高斯函數(式(1-6))計算數據之間的相似度，并且該函數中的自由參數\sigma是需要由用戶指定的，這給這類算法在實際中的應用帶來了很大的麻煩。
流形學習 (manifold learning)
流形學習是個很廣泛的概念。這里我主要談的是自從2000年以后形成的流形學習概念和其主要代表方法。自從2000年以后，流形學習被認為屬于非線性降維的一個分支。眾所周知，引導這一領域迅速發展的是2000年Science雜志上的兩篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形學習的基本概念
那流形學習是什莫呢？為了好懂，我盡可能應用少的數學概念來解釋這個東西。所謂流形（manifold）就是一般的幾何對象的總稱。比如人，有中國人、美國人等等；流形就包括各種維數的曲線曲面等。和一般的降維分析一樣，流形學習把一組在高維空間中的數據在低維空間中重新表示。和以往方法不同的是，在流形學習中有一個假設，就是所處理的數據采樣于一個潛在的流形上，或是說對于這組數據存在一個潛在的流形。對于不同的方法，對于流形性質的要求各不相同，這也就產生了在流形假設下的各種不同性質的假設，比如在Laplacian Eigenmaps中要假設這個流形是緊致黎曼流形等。對于描述流形上的點，我們要用坐標，而流形上本身是沒有坐標的，所以為了表示流形上的點，必須把流形放入外圍空間（ambient space）中，那末流形上的點就可以用外圍空間的坐標來表示。比如R^3中的球面是個2維的曲面，因為球面上只有兩個自由度，但是球面上的點一般是用外圍R^3空間中的坐標表示的，所以我們看到的R^3中球面上的點有3個數來表示的。當然球面還有柱坐標球坐標等表示。對于R^3中的球面來說，那末流形學習可以粗略的概括為給出R^3中的表示，在保持球面上點某些幾何性質的條件下，找出找到一組對應的內蘊坐標（intrinsic coordinate）表示，顯然這個表示應該是兩維的，因為球面的維數是兩維的。這個過程也叫參數化（parameterization）。直觀上來說，就是把這個球面盡量好的展開在通過原點的平面上。在PAMI中，這樣的低維表示也叫內蘊特征（intrinsic feature）。一般外圍空間的維數也叫觀察維數，其表示也叫自然坐標（外圍空間是歐式空間）表示,在統計中一般叫observation。
了解了流形學習的這個基礎，那末流形學習中的一些是非也就很自然了，這個下面穿插來說。由此，如果你想學好流形學習里的方法，你至少要了解一些微分流形和黎曼幾何的基本知識。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap開創了一個數據處理的新戰場。在沒有具體說Isomap之前，有必要先說說MDS（Multidimensional Scaling）這個方法。我們國內的很多人知道PCA，卻很多人不知道MDS。PCA和MDS是相互對偶的兩個方法。MDS就是理論上保持歐式距離的一個經典方法，MDS最早主要用于做數據的可視化。由于MDS得到的低維表示中心在原點，所以又可以說保持內積。也就是說，用低維空間中的內積近似高維空間中的距離。經典的MDS方法，高維空間中的距離一般用歐式距離。
Isomap就是借窩生蛋。他的理論框架就是MDS，但是放在流形的理論框架內，原始的距離換成了流形上的測地線（geodesic）距離。其它一模一樣。所謂的測地線，就是流形上加速度為零的曲線，等同于歐式空間中的直線。我們經常聽到說測地線是流形上兩點之間距離最短的線。其實這末說是不嚴謹的。流形上兩點之間距離最短的線是測地線，但是反過來不一定對。另外，如果任意兩個點之間都存在一個測地線，那末這個流形必須是連通的鄰域都是凸的。Isomap就是把任意兩點的測地線距離（準確地說是最短距離）作為流形的幾何描述，用MDS理論框架理論上保持這個點與點之間的最短距離。在Isomap中，測地線距離就是用兩點之間圖上的最短距離來近似的，這方面的算法是一般計算機系中用的圖論中的經典算法。
如果你曾細致地看過Isomap主頁上的matlab代碼，你就會發現那個代碼的實現復雜度遠超與實際論文中敘述的算法。在那個代碼中，除了論文中寫出的算法外，還包括了 outlier detection和embedding scaling。這兩樣東西，保證了運行他們的程序得到了結果一般來說相對比較理想。但是，這在他們的算法中并沒有敘述。如果你直接按照他論文中的方法來實現，你可以體會一下這個結果和他們結果的差距。從此我們也可以看出，那幾個作者做學問的嚴謹態度，這是值得我們好好學習的。
另外比較有趣的是，Tenenbaum根本不是做與數據處理有關算法的人，他是做計算認知科學（computational cognition science）的。在做這個方法的時候，他還在stanford，02年就去了MIT開創一派，成了CoCoSci 的掌門人，他的組成長十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT帶的學生就從來再也沒有做過類似的工作。其原因我今年夏天有所耳聞。他在今年參加 UCLA Alan Yuille 組織的一個summer school上說，（不是原文，是大意）我們經常忘了做研究的原始出發點是什莫。他做Isomap就是為了找一個好的visual perception的方法，他還堅持了他的方向和信仰，computational cognition，他沒有隨波逐流。而由他引導起來的 manifold learning 卻快速的發展成了一個新的方向。
這是一個值得我們好好思考的問題。我們做一個東西，選擇一個研究方向究竟是為了什么。你考慮過嗎？
b) LLE (Locally linear Embedding)
LLE在作者寫出的表達式看,是個具有十分對稱美的方法. 這種看上去的對稱對于啟發人很重要。LLE的思想就是，一個流形在很小的局部鄰域上可以近似看成歐式的，就是局部線性的。那末，在小的局部鄰域上，一個點就可以用它周圍的點在最小二乘意義下最優的線性表示。LLE把這個線性擬合的系數當成這個流形局部幾何性質的刻畫。那末一個好的低維表示，就應該也具有同樣的局部幾何，所以利用同樣的線性表示的表達式，最終寫成一個二次型的形式，十分自然優美。
注意在LLE出現的兩個加和優化的線性表達，第一個是求每一點的線性表示系數的。雖然原始公式中是寫在一起的，但是求解時，是對每一個點分別來求得。第二個表示式，是已知所有點的線性表示系數，來求低維表示（或嵌入embedding）的，他是一個整體求解的過程。這兩個表達式的轉化正好中間轉了個彎，使一些人困惑了，特別后面一個公式寫成一個二次型的過程并不是那末直觀，很多人往往在此卡住，而阻礙了全面的理解。我推薦大家去精讀 Saul 在JMLR上的那篇LLE的長文。那篇文章無論在方法表達還是英文書寫，我認為都是精品，值得好好玩味學習。
另外值得強調的是，對于每一點處擬合得到的系數歸一化的操作特別重要，如果沒有這一步，這個算法就沒有效果。但是在原始論文中，他們是為了保持數據在平行移動下embedding不變。
LLE的matlab代碼寫得簡潔明了，是一個樣板。
在此有必要提提Lawrence Saul這個人。在Isomap和LLE的作者們中，Saul算是唯一一個以流形學習（并不限于）為研究對象開創學派的人。Saul早年主要做參數模型有關的算法。自從LLE以后，坐陣UPen創造了一個個佳績。主要成就在于他的兩個出色學生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多獎，在此不多說，可以到他主頁上去看。Weinberger把學習核矩陣引入到流形學習中來。他的這個方法在流形學習中影響到不是很顯著，卻是在 convex optimization 中人人得知。Fei Sha不用多說了，machine learning中一個閃亮的新星，中國留學生之驕傲?，F在他們一個在Yahoo,一個在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要說哪一個方法被做的全面，那莫非LE莫屬。如果只說LE這個方法本身，是不新的，許多年前在做mesh相關的領域就開始這莫用。但是放在黎曼幾何的框架內，給出完整的幾何分析的，應該是Belkin和Niyogi（LE作者）的功勞。
LE的基本思想就是用一個無向有權圖來描述一個流形，然后通過用圖的嵌入（graph embedding）來找低維表示。說白了，就是保持圖的局部鄰接關系的情況把這個圖從高維空間中重新畫在一個低維空間中（graph drawing）。
在至今為止的流行學習的典型方法中，LE是速度最快、效果相對來說不怎莫樣的。但是LE有一個其他方法沒有的特點，就是如果出現outlier情況下，它的魯棒性（robustness）特別好。
后來Belkin和Niyogi又分析了LE的收斂性。大家不要忽視這個問題，很重要。鼓勵有興趣數學功底不錯的人好好看看這篇文章。
d) Hessian Eigenmaps
如果你對黎曼幾何不懂，基本上看不懂這個方法。又加作者表達的抽象，所以絕大多數人對這個方法了解不透徹。在此我就根據我自己的理解說說這個方法。
這個方法有兩個重點：（1）如果一個流形是局部等距（isometric）歐式空間中一個開子集的，那末它的Hessian矩陣具有d+1維的零空間。（2）在每一點處，Hessian系數的估計。
首先作者是通過考察局部Hessian的二次型來得出結論的，如果一個流形局部等距于歐式空間中的一個開子集，那末由這個流形patch到開子集到的映射函數是一個線性函數，線性函數的二次混合導數為零，所以局部上由Hessian系數構成的二次型也為零，這樣把每一點都考慮到，過渡到全局的Hessian矩陣就有d+1維的零空間，其中一維是常函數構成的，也就是1向量。其它的d維子空間構成等距坐標。這就是理論基礎的大意，當然作者在介紹的時候，為了保持理論嚴謹，作了一個由切坐標到等距坐標的過渡。
另外一個就是局部上Hessian系數的估計問題。我在此引用一段話：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
dave
這段話是dodo在初學HE時候，寫信問Dave Donoho，他給dodo的回信。希望大家領會。如果你了解了上述基本含義，再去細看兩遍原始論文，也許會有更深的理解。由于HE牽扯到二階導數的估計，所以對噪聲很敏感。另外，HE的原始代碼中在計算局部切坐標的時候，用的是奇異值分解(SVD)，所以如果想用他們的原始代碼跑一下例如圖像之類的真實數據，就特別的慢。其實把他們的代碼改一下就可以了，利用一般PCA的快速計算方法，計算小尺寸矩陣的特征向量即可。還有，在原始代碼中，他把Hessian系數歸一化了，這也就是為什莫他們叫這個方法為 Hessian LLE 的原因之一。
Dave Dohono是學術界公認的大牛，在流形學習這一塊，是他帶著他的一個學生做的，Carrie Grimes。現在這個女性研究員在Google做 project leader，學術界女生同學的楷模 : )
e) LTSA (Local tangent space alignment)
很榮幸，這個是國內學者（浙江大學數學系的老師ZHANG Zhenyue）為第一作者做的一個在流行學習中最出色的方法。由于這個方法是由純數學做數值分析出身的老師所做，所以原始論文看起來公式一大堆，好像很難似的。其實這個方法非常直觀簡單。
象 Hessian Eigenmaps 一樣，流形的局部幾何表達先用切坐標，也就是PCA的主子空間中的坐標。那末對于流形一點處的切空間，它是線性子空間，所以可以和歐式空間中的一個開子集建立同構關系，最簡單的就是線性變換。在微分流形中，就叫做切映射 (tangential map)，是個很自然很基礎的概念。把切坐標求出來，建立出切映射，剩下的就是數值計算了。最終這個算法劃歸為一個很簡單的跌代加和形式。如果你已經明白了MDS，那末你就很容易明白，這個算法本質上就是MDS的從局部到整體的組合。
這里主要想重點強調一下，那個論文中使用的一個從局部幾何到整體性質過渡的alignment技術。在spectral method（特征分解的）中，這個alignment方法特別有用。只要在數據的局部鄰域上你的方法可以寫成一個二次項的形式，就可以用。
其實LTSA最早的版本是在02年的DOCIS上。這個alignment方法在02年底Brand的 charting a manifold 中也出現，隱含在Hessian Eigenmaps中。在HE中，作者在從局部的Hessian矩陣過渡到全局的Hessian矩陣時，用了兩層加號，其中就隱含了這個alignment方法。后來國內一個叫 ZHAO Deli 的學生用這個方法重新寫了LLE，發在Pattern Recognition上，一個短文?？梢灶A見的是，這個方法還會被發揚光大。
ZHA Hongyuan 后來專門作了一篇文章來分析 alignment matrix 的譜性質，有興趣地可以找來看看。
f) MVU (Maximum variance unfolding)
這個方法剛發出來以后，名字叫做Semi-definite Embedding (SDE)。構建一個局部的稀疏歐式距離矩陣以后，作者通過一定約束條件（主要是保持距離）來學習到一個核矩陣，對這個核矩陣做PCA就得到保持距離的embedding，就這莫簡單。但是就是這個方法得了多少獎，自己可以去找找看。個人觀點認為，這個方法之所以被如此受人賞識，無論在vision還是在learning，除了給流形學習這一領域帶來了一個新的解決問題的工具之外，還有兩個重點，一是核方法（kernel），二是半正定規劃（semi-definite programming），這兩股風無論在哪個方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
這個方法不太被人所知，但是我認為這個是流形學習發展中的一個典型的方法（其實其他還有很多人也這莫認為）。就效果來說，這個方法不算好，說它是一個典型的方法，是因為這個方法應用了黎曼幾何中一個很直觀的性質。這個性質和法坐標(normal coordinate)、指數映射(exponential map)和距離函數(distance function)有關。
如果你了解黎曼幾何，你會知道，對于流形上的一條測地線，如果給定初始點和初始點處測地線的切方向，那莫這個測地線就可以被唯一確定。這是因為在這些初始條件下，描述測地線的偏微分方程的解是唯一的。那末流形上的一條測地線就可以和其起點處的切平面上的點建立一個對應關系。我們可以在這個切平面上找到一點，這個點的方向就是這個測地線在起點處的切方向，其長度等于這個測地線上的長。這樣的一個對應關系在局部上是一一對應的。那末這個在切平面上的對應點在切平面中就有一個坐標表示，這個表示就叫做測地線上對應點的法坐標表示（有的也叫指數坐標）。那末反過來，我們可以把切平面上的點映射到流形上，這個映射過程就叫做指數映射（Logmap就倒過來）。如果流形上每一個點都可以這樣在同一個切平面上表示出來，那末我們就可以得到保持測地線長度的低維表示。如果這樣做得到，流形必須可以被單坐標系統所覆蓋。
如果給定流形上的采樣點，如果要找到法坐標，我們需要知道兩個東西，一是測地線距離，二是每個測地線在起點處的切方向。第一個東西好弄，利用Isomap中的方法直接就可以解決，關鍵是第二個。第二個作者利用了距離函數的梯度，這個梯度和那個切方向是一個等價的關系，一般的黎曼幾何書中都有敘述。作者利用一個局部切坐標的二次泰勒展開來近似距離函數，而距離是知道的，就是測地線距離，局部切坐標也知道，那末通過求一個簡單的最小二乘問題就可以估計出梯度方向。
如果明白這個方法的幾何原理，你再去看那個方法的結果，你就會明白為什莫在距離中心點比較遠的點的embedding都可以清楚地看到在一條條線上，效果不太好。
最近這個思想被北大的一個年輕的老師 LIN Tong 發揚光大，就是ECCV‘06上的那篇，還有即將刊登出的TPAMI上的 Riemannian Manifold Learning，實為國內研究學者之榮幸。Lin的方法效果非常好，但是雖然取名叫Riemannian，沒有應用到黎曼幾何本身的性質，這樣使他的方法更容易理解。
Lin也是以一個切空間為基準找法坐標，這個出發點和思想和Brun（S-Logmaps）的是一樣的。但是Lin全是在局部上操作的，在得出切空間原點處局部鄰域的法坐標以后，Lin采用逐步向外擴展的方法找到其他點的法坐標，在某一點處，保持此點到它鄰域點的歐式距離和夾角，然后轉化成一個最小二乘問題求出此點的法坐標，這樣未知的利用已知的逐步向外擴展。說白了就像縫網一樣，從幾個臨近的已知點開始，逐漸向外擴散的縫。效果好是必然的。
有人做了個好事情，做了個系統，把幾個方法的matlab代碼放在了一起 http://www.math.umn.edu/~wittman/mani/以上提到方法論文，都可以用文中給出的關鍵詞借助google.com找到。
3. 基本問題和個人觀點
流形學習現在還基本處于理論探討階段，在實際中難以施展拳腳，不過在圖形學中除外。我就說說幾個基本的問題。
a. 譜方法對噪聲十分敏感。希望大家自己做做實驗體會一下，流形學習中譜方法的脆弱。
b. 采樣問題對結果的影響。
c. 收斂性
d. 一個最尷尬的事情莫過于，如果用來做識別，流形學習線性化的方法比原來非線性的方法效果要好得多，如果用原始方法做識別，那個效果叫一個差。也正因為此，使很多人對流形學習產生了懷疑。原因方方面面 : )
e. 把偏微分幾何方法引入到流形學習中來是一個很有希望的方向。這樣的工作在最近一年已經有出現的跡象。
看一些問到人臉識別有關的問題。由于此文結尾寫得有點草，我這里再補充一下。
dodo
1）人臉識別的識別效果首先取決于 visual feature，圖片中表示的模式和一般的向量模式還是有很大差別的。visual feature的好壞，決定了你所用的向量到底能不能代表這個圖像中的模式和這個模式與其他模式的正確關系，如果能，那再談降維識別的事情。
結構能保持，效果就好；不能保持，就很難說。
2）現在流形學習中的極大多數方法不收斂。正因為這樣，在原始樣本集中，如果增添少部分點，或是減少少部分點，或是擾動少部分點，都會對最后的nonlinear embedding產生影響。也就是說，極不穩定。
到現在為止，就 Laplacian Eigenmaps 有收斂性的證明。但是，這個被證明的結果的前提條件是啥，這個很重要。如果是均勻采樣，那么基本對實際用處不大，理論上有引導作用。
3）采樣的問題，包括采樣密度和采樣方式，都對最后結果有顯著影響。而實際數據都是非常復雜的。
4）最后降到多少維的問題。這個對于流行學習來說，也是一個正在爭論探討的問題。
5）多流形的問題。現在的流形學習算法能處理的流形情況非常的弱，前提建設的條件非常的強，比如單坐標系統覆蓋，與歐式空間的開子集等距等等。對于具有不同維數的多流形混合的問題，還沒有人能解。而
這恰恰是模式識別中一個合理的情況?。ň哂胁煌S數的多流形混合的問題）
而4）5）后兩者是緊緊聯系在一起。
這幾點也是流形學習能發揮其威力必須克服的問題。實際的情況并不是像一些人說的“流形學習已經做爛了”，問題在于
1）沒有找到真正的問題在哪，
2）知道問題在哪兒，解決不了。
這就是流形學習目前的狀況，如果你能用恰當的理論，而不是技巧和實驗，解決了2）、5）其中一個問題，你就會是流形學習進入下一個黃金時期的功臣。
而現在的情況是，引導和開創流形學習進入第一個黃金時期和為這個黃金時期推波助瀾的那第一撥人，大都不再為此而努力了。現在就M. Belkin還在第一線為2）問題而奮斗。
另外一個可喜的局面是，那些專職搞數值和幾何的數學人開始涉足此領域，這必將帶動流形學習這個方向深入發展，這也是這個方向發展的一個必然。
The algorithm of NMF is so simple and elegant (just three or four lines in Matlab). Yaoliang Yu said the code can be downloaded :http://www.mathworks.com/matlabcentral/linkexchange/links/1041-matlab-code-nmf(First submitted by MATLAB Central Team on 13 Jun 2005 )
There is another version of the matlab code of NMF: http://www.csie.ntu.edu.tw/~cjlin/nmf/index.html The code of [http://www.mathworks.com/matlabcentral/linkexchange/links/1041-matlab-code-nmf]:
function [w,h]=nmf(v,r,verbose)
%
% Jean-Philippe Brunet
% Cancer Genomics
% The Broad Institute
% brunet@broad.mit.edu
%
% This software and its documentation are copyright 2004 by the
% Broad Institute/Massachusetts Institute of Technology. All rights are reserved.
% This software is supplied without any warranty or guaranteed support whatsoever.
% Neither the Broad Institute nor MIT can not be responsible for its use, misuse,
% or functionality.
%
% NMF divergence update equations :
% Lee, D..D., and Seung, H.S., (2001), 'Algorithms for Non-negative Matrix
% Factorization', Adv. Neural Info. Proc. Syst. 13, 556-562.
%
% v (n,m) : N (genes) x M (samples) original matrix
% Numerical data only.
% Must be non negative.
% Not all entries in a row can be 0. If so, add a small constant to the
% matrix, eg.v+0.01*min(min(v)),and restart.
%
% r : number of desired factors (rank of the factorization)
%
% verbose : prints iteration count and changes in connectivity matrix elements
% unless verbose is 0
%
% Note : NMF iterations stop when connectivity matrix has not changed
% for 10*stopconv interations. This is experimental and can be
% adjusted.
%
% w : N x r NMF factor
% h : r x M NMF factor
% test for negative values in v
if min(min(v)) < 0
error('matrix entries can not be negative');
return
end
if min(sum(v,2)) == 0
error('not all entries in a row can be zero');
return
end
[n,m]=size(v);
stopconv=40; % stopping criterion (can be adjusted)
niter = 2000; % maximum number of iterations (can be adjusted)
cons=zeros(m,m);
consold=cons;
inc=0;
j=0;
%
% initialize random w and h
%
w=rand(n,r);
h=rand(r,m);
for i=1:niter
% divergence-reducing NMF iterations
x1=repmat(sum(w,1)',1,m);
h=h.*(w'*(v./(w*h)))./x1;
x2=repmat(sum(h,2)',n,1);
w=w.*((v./(w*h))*h')./x2;
% test convergence every 10 iterations
if(mod(i,10)==0)
j=j+1;
% adjust small values to avoid undeflow
h=max(h,eps);w=max(w,eps);
% construct connectivity matrix
[y,index]=max(h,[],1); %find largest factor
mat1=repmat(index,m,1); % spread index down
mat2=repmat(index',1,m); % spread index right
cons=mat1==mat2;
if(sum(sum(cons~=consold))==0) % connectivity matrix has not changed
inc=inc+1; %accumulate count
else
inc=0; % else restart count
end
if verbose % prints number of changing elements
fprintf('\t%d\t%d\t%d\n',i,inc,sum(sum(cons~=consold))),
end
if(inc>stopconv)
break, % assume convergence is connectivity stops changing
end
consold=cons;
end
end
最近在上數字圖像處理，時域和頻域的概念我沒有直觀的概念，搜索一下，歸納如下：
1.最簡單的解釋
頻域就是頻率域，
平常我們用的是時域，是和時間有關的，
這里只和頻率有關，是時間域的倒數。時域中，X軸是時間，
頻域中是頻率。頻域分析就是分析它的頻率特性！
2. 圖像處理中：
空間域，頻域，變換域，壓縮域等概念！
只是說要將圖像變換到另一種域中，然后有利于進行處理和計算
比如說：圖像經過一定的變換（Fourier變換，離散yuxua DCT 變換），圖像的頻譜函數統計特性：圖像的大部分能量集中在低，中頻，高頻部分的分量很弱，僅僅體現了圖像的某些細節。
2.離散傅立葉變換
一般有離散傅立葉變換和其逆變換
3.DCT變換
示波器用來看時域內容，頻普儀用來看頻域內容?。?！
時域是信號在時間軸隨時間變化的總體概括。
頻域是把時域波形的表達式做傅立葉變化得到復頻域的表達式，所畫出的波形就是頻譜圖。是描述頻率變化和幅度變化的關系。
時域做頻譜分析變換到頻域;空間域做頻譜分析變換到波數域;
信號通過系統，在時域中表現為卷積，而在頻域中表現為相乘。
無論是傅立葉變換還是小波變換，其實質都是一樣的，既：將信號在時間域和頻率域之間相互轉換，從看似復雜的數據中找出一些直觀的信息，再對它進行分析。由于信號往往在頻域比有在時域更加簡單和直觀的特性，所以，大部分信號分析的工作是在頻域中進行的。音樂——其實就是時/頻分析的一個極好例子，樂譜就是音樂在頻域的信號分布，而音樂就是將樂譜變換到時域之后的函數。從音樂到樂譜，是一次傅立葉或小波變換；從樂譜到音樂，就是一次傅立葉或小波逆變換。
時域（時間域）——自變量是時間,即橫軸是時間,縱軸是信號的變化。其動態信號x（t）是描述信號在不同時刻取值的函數。
頻域（頻率域）——自變量是頻率,即橫軸是頻率,縱軸是該頻率信號的幅度,也就是通常說的頻譜圖。頻譜圖描述了信號的頻率結構及頻率與該頻率信號幅度的關系。
對信號進行時域分析時，有時一些信號的時域參數相同，但并不能說明信號就完全相同。因為信號不僅隨時間變化，還與頻率、相位等信息有關，這就需要進一步分析信號的頻率結構，并在頻率域中對信號進行描述。
動態信號從時間域變換到頻率域主要通過傅立葉級數和傅立葉變換實現。周期信號靠傅立葉級數，非周期信號靠傅立葉變換。
很簡單時域分析的函數是參數是t，也就是y=f(t)，頻域分析時，參數是w，也就是y=F(w)
兩者之間可以互相轉化。時域函數通過傅立葉或者拉普拉斯變換就變成了頻域函數。
傅立葉變換作為一種數學工具，作用不只是在一兩個方面得以體現。
就象微分方程，要說作用，在很多學科都有應用。大到人造衛星，小大微觀粒子。
比較常用的應用，可以變換一種函數域到另一域。具體的，比如信號處理里，可以把信號
的時間域變換到信號的頻域。信號處理的應用同樣廣泛，比如圖象處理。對吧
變換可以處理一些微分方程，在數學物理方法里都學過的，我也就不贅言。
量子力學基本原理和傅氏變換有關系。（參考彭桓武若干著作）
通常工科學生，尤其是自動化和信號處理專業理解傅氏變換比理科的要強一些。因為在信
號與系統以及自動控制原理里傅氏變換和拉氏變換是最基本的概念與工具。
|