|
|
|
发新文章 |
|
|
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中一个闪亮的新星,中国留学生之骄傲。现在他们一个在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上,一个短文。可以预见的是,这个方法还会被发扬光大。
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)多流形的问题。现在的流形学习算法能处理的流形情况非常的弱,前提建设的条件非常的强,比如单坐标系统覆盖,与欧式空间的开子集等距等等。对于具有不同维数的多流形混合的问题,还没有人能解。而
这恰恰是模式识别中一个合理的情况!(具有不同维数的多流形混合的问题)
而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) 两者之间可以互相转化。时域函数通过傅立叶或者拉普拉斯变换就变成了频域函数。
傅立叶变换作为一种数学工具,作用不只是在一两个方面得以体现。 就象微分方程,要说作用,在很多学科都有应用。大到人造卫星,小大微观粒子。
比较常用的应用,可以变换一种函数域到另一域。具体的,比如信号处理里,可以把信号 的时间域变换到信号的频域。信号处理的应用同样广泛,比如图象处理。对吧
变换可以处理一些微分方程,在数学物理方法里都学过的,我也就不赘言。
量子力学基本原理和傅氏变换有关系。(参考彭桓武若干著作)
通常工科学生,尤其是自动化和信号处理专业理解傅氏变换比理科的要强一些。因为在信 号与系统以及自动控制原理里傅氏变换和拉氏变换是最基本的概念与工具。
|