PPT《*》

* * Beyond the Graphs: Semi-parametric Semi-supervised Discriminant Analysis Author: Fei Wang, Xin Wang and Tao LiLecturer: Deming Zhai * 作者的相关信息 Fei Wang―第一作者佛罗里达国际大学 博士后简历2003年7月:西安电子科技大学自动化系获硕士学位2008年7月: 清华大学自动化系获博士学位导师: Changshui Zhang 论文题目: Graph-based Semi-supervised Learning研究方向文本挖掘,多媒体分析,信息检索,图像分割人脸识别,社会网络分析,相关性学习,生物信息 作者的相关信息 实习经历:2006.

9 C 2007.7 Vivido Media Inc. Research Internship 2006.11 C 2007.4 IBM China Research Lab: Research Internship2007.6 C 2007.7 Florida International University: Visiting Student2007.9 C 2007.11Hong Kong University of Science and Technology: Visiting Student2007.12 C 2008.8 IBM China Research Lab: Research Internship论文期刊: 13, 会议: 42.个人主页: http://feiwang03.googlepages.com/ 作者的相关信息 最新发表会议文章:Fei Wang, Xin Wang, Tao Li. Beyond the Graphs: Semi-Parametric Semi-Supervised Discriminant Analysis. IEEE Computer Scociety Conference on Computer Vision and Pattern Recognition (CVPR). Miami, Florida, USA. To Appear. 2009Bin Zhao, James Kwok, Fei Wang, Changshui Zhang. Unsupervised Maximum Margin Feature Selection with Manifold Regularization. IEEE Computer Scociety Conference on Computer Vision and Pattern Recognition (CVPR). Miami, Florida, USA. To Appear. 2009Gang Chen, Jianwen Zhang, Fei Wang, Changshui Zhang, Yuli Gao. Efficient Multi-Label Classification with Hypergraph Regularization. IEEE Computer Scociety Conference on Computer Vision and Pattern Recognition (CVPR). Miami, Florida, USA. To Appear. 2009.Fei Wang, Xin Wang, Tao Li. Generalized Cluster Aggregation. The 21st International Joint Conference on Artificial Intelligence (IJCAI). Pasadena, California, USA. To Appear. 2009. Fei Wang, Bin Zhang, Ta-Hsin Li, Wen jun Yin, Jin Dong, Tao Li. Preference Learning with Extreme Examples. The 21st International Joint Conference on Artificial Intelligence (IJCAI). Pasadena, California, USA. To Appear. 2009. Dan Zhang, Fei Wang, Luo Si, Tao Li. Maximum Margin Multiple Instance Clustering. The 21st International Joint Conference on Artificial Intelligence (IJCAI). Pasadena, California, USA. To Appear. 2009.Fei Wang, Chris Ding, Tao Li. Integrated KL (K-means - Laplacian) Clustering: A New?Clustering Approach by Combining Attribute Data and Pairwise Relations. Proc. The 9th SIAM Conference on Data Mining (SDM). Sparks, Nevada. 38-48. 2009. Acceptance rate: 55/351 = 15.67% 作者的相关信息 Xin Wang――第二作者1999-2003 西安电子科技大学自动化系信息 本科2003-2006 北航模式识别智能系统实验室 硕士2006-2008 微软工程从事软件研究及开发2008-至今 佛罗里达国际大学 计算机 博士研究方向音乐信息检索 tag recommendation? 发表论文第一作者论文2篇 主页http://syner.wang.googlepages.com/ * 作者的相关信息 Tao Li――第三作者2004年 美国罗切斯特大学计算机系获 博士学位现在 佛罗里达国际大学 计算机 系 助理教授研究方向数据挖掘 机器学习分类、聚类、半监督学习、相似度和空间模式学习相关应用生物信息学、文本挖掘、音乐信息检索、事件挖掘发表论文09年会议总数13篇,其中第一作者2篇09年期刊5篇,其中第一作者2篇主页http://users.cs.fiu.edu/~taoli/ * 文章出处 Fei Wang, Xin Wang and Tao Li. Beyond the Graphs: Semi-parametric Semi-supervised Discriminant Analysis. (CVPR09).相关文献D. Cai, X. He, and J. Han. Spectral Regression for Efficient Regularized Subspace Learning. Proc. of ICCV, 2007.D. Cai, X. He, and J. Han. Semi-supervised discriminant analysis. ICCV, 2007. * * 摘要 线性判别分析(LDA)是一种流行的特征提取方法,在计算机视觉和模式识别领域中激发了相当多研究者的兴趣.LDA的投影向量通常是通过最大化数据集的类间散度同时最小化类内散度来获得的.然而,在实际中,通常缺乏足够多的有标注数据,这就使得对我们所估计的投影方向不准确.为了解决上面的限制,在这篇文章中,我们提出了一种新的半监督判别分析方法.与传统的基于图的方法不同,我们所提出的方法将有标注数据和未标注数据之间的几何分布信息通过半参数化的形式加入进来.具体的,最终所获得的判别投影包含两部分:判别的部分(在有标注数据上利用传统LDA或是KDA);

保持几何结构的部分(在所有样本点上通过 KPCA学习得到).因此,我们命名我们的算法版参数化的半监督判别分析(SSDA).在人脸识别和图像任务上的实验结果表明了我们方法的有效性. * * 文章结构 AbstractIntroductionRelated WorksSemi-parametric Semi-supervised Discriminant Analysis (SSDA)ExperimentsConclusions and Discussions * * 讲解提纲 谱回归 LDA半参数回归半参数半监督判别分析(SSDA)实验结论 * * 讲解提纲 谱回归 LDA半参数回归半参数半监督判别分析(SSDA)实验结论 * * 传统LDA 训练样本集合:n个样本,C个类别,m维特征有标注数据:未标注数据:LDA目标函数:有监督学习类内与类间散度只能 利用有标注数据计算 基于正则化的LDA半监督扩展 LDA的图嵌入形式 数据中心化 其中:LDA目标函数: SVD+LGE(线性图嵌入)时间复杂度很高n 样本个数m 样本维数谱回归降低复杂度 子空间学习中解决奇异值问题最常用解决办法 LDA解法 LDA标准解法:当维数高于样本总数时 不存在LDA的SVD解法: SVD+LGE Figure: q =

2 和lasso regularizer q = 1时的最优解w示意图 谱回归 LDA 基本步骤:正则化的目的:避免当样本数目小于特征维数时,未知数的个数大于方程的个数,无穷多个解

2、以回归的方式求解w Regularized Least Squares 谱回归 LDA 基本步骤:正则化的目的:避免当样本数目小于特征维数时,未知数的个数大于方程的个数,无穷多个解

2、以回归的方式求解w G为分块对角阵,计算简单 迭代LSQR算法 C.C. Paige and M..A. Saunders. Algorithm

583 LSQR: Sparse linear equations and least squares problems. ACM Transductions on Mathematical Software,8(2):195-209, June 1982. 时间复杂度对比: 2Csmn SRLDA SVD+LGE s:为迭代次数, C:为类别数目 m:维数 n: 样本数 :estimated function 或predictor 讲解提纲 谱回归 LDA半参数回归半参数半监督判别分析(SSDA)实验结论 * * 半参数回归 基本含义:半参数回归指的是回归模型中的predictor既包含参数化又包含非参数化的成分.f:非参数化部分;

h: 参数化部分 :为一族参数化函数参数化模型是指h(x)可以表示成x的显示函数,例如:线性回归非参数模型是指f(x)不能通过显示的参数函数估计,只能通过数据来进行直接估计.例如:kNN Parzen窗方法 半参数回归 优点:非参数化部分:直接通过数据进行估计,因此准确度较高.参数化部分:根据数据特性,将一些额外的知识加入到已有模型中,容易理解,同时可以修正预测值使其朝着某些趋势变化.(correct the data from some (e.g. linear) trend) 讲解提纲 谱回归 LDA半参数回归半参数半监督判别分析(SSDA)实验结论 * * 半参数半监督判别分析 非参数化部分f:利用有标注数据进行kernel DA F是特征空间 需要借助于有标注样本进行估计,因此是非参数模型 为F空间的标准正交基(投影轴) 为第c维的投影方向 半参数半监督判别分析 参数化部分h:基本思想:利用有标注数据和未标注数据所包含的几何信息.采用方法:通过kernel PCA 找到特征空间中包含最大方差的主轴方向,并根据该方向建立参数化函数加入到已有的模型中,修正最终的预测函数.KPCA 是在特征空间的数据集 K包含了数据集中样本点的分布信息 无监督学习样本确定,参数确定,因此是参数化部分 半参数半监督判别分析 半参数化形式: 写成矩阵形式,多类扩展 Eq.(23,24) 算法描述 线性形式算法描述 Eq.(27,28) SSDA复杂度分析 基本步骤:(1)在整个数据集上做KPCA(2)解线性方程系统(组)采用一般解法:(1)――(2)―― 迭代优化,降低复杂度 Nystrom 或block quantized方法优化,降低复杂度 P. Drineas and M. W. Mahoney. On the Nystrom Method for Approximating a Gram Matrix for Improved Kernel-Based Learning. JMLR 6, 2153-2175, 2005.K. Zhang and J. T. Kwok. Block-Quantized Kernel Matrix for Fast Spectral Embedding. Proc. of ICML, 1097-1104, 2003. 讲解提纲 谱回归 LDA半参数回归半参数半监督判别分析(SSDA)实验结论 * * Face Recognition from a Single Training Image 数据库:40个人,每人10张图片,7张训练集,其中1张有标注图像维数: 32*32,共50次随机实验 Face Recognition from a Single Training Image 数据库:20个人,每人28张图片,20张训练集,其中1张有标注图像维数: 32*32,共50次随机实验 Face Recognition from a Single Training Image 数据库:68个人,每人43张图片,30张训练集,其中1张有标注图像维数: 32*32,共50次随机实验 Relevance Feedback for Image Retrieval 相关反馈在基于内容图像检索(CBIR)中一种有效的缩小底层视觉特征和高层语意特征之间的差异的学习框架.典型的半监督学习模型数据库的图像――大量未标注数据用户反馈――少量有标注数据实验设置:数据库:COREL子集(7900图片,79个类别)特征:共128维(64维颜色直方图,64维纹理特征) Relevance Feedback for Image Retrieval ARE: Augmented Relation EmbeddingLPP:Locality Preserving ProjectionsSSP:Semantic Subspace Projection 讲解提纲 谱回归 LDA半参数回归半参数半监督判别分析(SSDA)实验结论 * * 结论 这篇文章提出了一种新的半监督判别分析方法,这种方法是通过半参数回归实现的,而不是传统基于图的正则化的框架.该方法能处理out-of-sample问题,其核心思想可以推广到其他的回归问题.实验验证了该方法的有效性. ........