Semi-definite Programming and Optimization on Stiefel-Grassmann Manifolds

by Li He

In this seminar, we will take a detailed look at semi-definite programming (SDP) and optimization on Stiefel-Grassmann optimization. The audience should be familiar with some basic ideas in optimization, such as gradient descent, conjugate gradient (CG) methods and basic concepts frequently employed in this area (e.g. feasible set, convexity, primal and dual formulation of an optimization problem).

In this talk I will cover the following topics:

• Some basic ideas of interior point methods.
• The interior point methods for SDP.
• Some common examples of SDP.
• Some applications of SDP in machine learning.
• Some basic concepts about Stiefel-Grassmann manifolds.
• How to design gradient-based optimization techniques on Stiefel-Grassmann manifolds.
• Applications of these algorithms in machine learning.

References

• Convex Optimization, by Stephen Boyd and Lieven Vandenberghe.
• Numerical Optimization (2nd ed.), by Jorge Nocedal, and Stephen J. Wright.
  
• Semidefinite Programming, by Lieven Vandenberghe and Stephen Boyd, Siam Review, 1996.
  
• The geometry of algorithms with orthogonality constraints, by Alan Edelman, Tomas A. Arias and Steven T. Smith.

Statistical Independence or Conditional Random Fields

There are two topics, statistical independence and conditional random fields, either of which I'd like to talk about in the seminar. I am not sure I can finish the former slides in time. Here are the outlines of both topics and references which you may be interested in.

Statistical Independence

• Statistical Independence
  • definition of independence;
  • several concepts (moments, cumulants, moment generating functions, characteristic functions, skewness, kurtosis);
  • numerical estimation of independence.
    
• Kernel Method for Independence Test
  • the main theorem;
  • numerical estimators;
  • the choice of kernels.
    
• Applications
  • independent component analysis;
  • clustering;
  • sufficient dimensionality reduction;
  • unsupervised kernel dimensionality reduction;
  • test of the same distribution;
  • iid test
    

References

• [Bach and Jordan 2002], Kernel independent component analysis, JMLR.
• [Fukumizu et al 2004], Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces, JMLR.

An Introduction to Conditional Random Fields

• Probabilistic Graphical Models
  • Bayesian belief networks;
  • Markov random fields.
    
• Conditional Random Fields
  • naive Bayes and logistic regression;
  • hidden Markov model and linear-chain conditional random fields;
  • general CRFs and skip-chain CRFs;
  • computational problems.
    
• Several Extensions
  • maximum margin Markov networks;
  • semi-Markov CRFs;
  • Bayesian CRFs;
  • non-parametric Bayesian methods
    

References

• [Berger et al 1996], A maximum entropy approach to natural language processing, Computational Linguistics.
• [Lafferty et al 2001], Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, ICML.
• [Taskar et al 2003], Max-margin Markov Networks, NIPS.

Saliency Detection

Saliency Detection是指检测一副图像/视频截图中最能吸引人注意力的区域的技术，通常基于某区域与周围区域的差别的程度来定义saliency值的大小。不同模型中的saliency值定义不一样，主要有以下几个大类的模型：
1.基于各个特征（比如颜色、灰度、方向）center-surround contrast的大小来定义。
2.基于图像的复杂度来定义。
3.基于频谱分析的方法。

以下为参考的资料：

Scholapedia

http://www.scholarpedia.org/article/Visual_salience

computational modelling of visual attention. Itti.

www.cnbc.cmu.edu/~tai/readings/tom/itti_attention.pdf

Saliency Based on Information Maximization. Bruce

www.citeulike.org/user/jborn/article/3366681

Saliency Detection: A Spectral Residual Approach

bcmi.sjtu.edu.cn/~houxiaodi/papers/cvpr07.pdf

Manifold Alignment Using Procrustes Analysis

icml08的文章，作者将统计学中做形状分析的一种叫Procrustes analysis的方法用于流形对齐 － 基于流形的两组数据通过一定数量标定点的训练，形成两组数据在整个流形上的对应关系。这种方法可以运用在知识的迁移（例如基于不同语言文档的对应查询、马尔可夫决策过程等等)。

Procrustes Analysis的主要思想就是将一组数据通过旋转、放缩、平移等变换使它和另一组数据形成最优的对应，它的特点是计算量较小，并且保持了流形的基本结构。

文章还详细介绍了几个应用：跨语言文档查询，马尔科夫决策过程中的迁移学习。

Procrustes Analysis 常用于步态识别.

相关文献可参阅： http://icml2008.cs.helsinki.fi/papers/229.pdf

Human Gait Recognition With Matrix Representation

PCA作为模式识别的常用方法，也存在着诸多不足之处。比如依然存在curse of dimensionality。又比如说在生物识别诸如人脸识别，步态识别等应用中，常遇到小样本问题，而要处理的数据维数又比较大，PCA有时不能有效地提取主要特征。
本篇论文中【1】，作者提出了一个CSA+DATER的scheme，替代传统的PCA+LDA的scheme，并成功地应用于人脸识别、步态识别等领域。这个方法组合的一个很重要的观点就是用矩阵（二阶张量）来表示原始数据——而不是如PCA常见的那样，用一个列向量来表示原始数据——这样，可以缓解“维数灾”带来的影响，以及在小样本的条件下更有效的提取主要信息。在论文最后的实验中，我们也可以看到，这种方法识别效果也是不错的。

[1]IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 16, NO. 7, JULY 2006
Human Gait Recognition With Matrix Representation
Dong Xu, Shuicheng Yan, Dacheng Tao, Lei Zhang, Xuelong Li, and Hong-Jiang Zhang

速读注意事项

以后几点需要讲清楚:

1.  文章的主要思路是什么?

2. 文章的贡献,创新点在哪里?

3. 文章的不足在哪里?

4. 作者的单位和作者自己的研究方向是哪些?

5.  文章关注的重点是什么, 反映了哪些机器学习领域的研究趋势?

6. 为什么能被录用?

7. 研究的动机是什么?

其它需要讲的, 请各位补充..

Fast Image/Video Upsampling

本文发表于sa08，文章提出了一种基于图像成像过程(Image Formation Process)的提升采样算法，可以应用于图像与视频超分。文章主要的idea是使用一个反馈网络（包括逆卷积，重新计算卷积，像素替换，其中像素替换过程是本文的一个创新点）对原始图像进行迭代计算，文中提出的算法可以较好的保持原图的局部结构信息。与其他的算法相比，本文的算法有如下好处：

1. 不需要额外的训练数据来学习一些结构特征，因此应用范围较广，但是与基于学习的算法相比对原始图像的要求更高；
2. 尽管算法设计是基于图像成像过程的提升采样，但是算法对其他模型的效果也很好，甚至可以直接应用到视频的提升采样中，并且在保持连贯性上表现十分出色；
3. 这个算法的效率很高，可以推广到实时计算上。
   

相关文献可参阅:http://www.cse.cuhk.edu.hk/~leojia/projects/upsampling/upsampling_sa08.pdf

周末讨论班

作为周二讨论班的补充，讲一本书和2－4篇会议论文的大致框架。

时间：周末下午1：30－3：00 The Element of Statistical Learning Theory
3:15-4:30 2－4 篇会议论文的思想和相关内容的介绍。

书由浦剑主讲，谭奔，王晓丹，周骥等轮流讲相关章节。。有时间的话我也讲一部分。

下学期再讲其他相关书。

论文主要以报告NIPS, ICML,CVPR等一档会议的内容为主，每次可定一个主题。

第一次报告：4.19日，浦剑。


欢迎大家拍砖 :D

增加 LaTeX 公式支持

现在可以使用如下方式插入 \text{\LaTeX} 公式，

• 使用行间公式可以用 HTML 的 pre 环境，<pre lang="eq.latex">Your Equation Here</pre>，如

  (a + b)^n = \sum_{i = 0}^n \binom{n}{i} a^i b^{n - i}.

• 使用行内公式可以用 HTML 的 code 环境，<code lang="eq.latex">Your Equation Here</code>，如\inline \sum_{n = 1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}。

欢迎大家使用。

关于讲书的讨论班

由于我的安排受到了大家广泛的批判，所以由何力同学和张老师重新组织吧。

Relative Margin Machine

我们知道,传统的SVM是基于最大化margin的,目标函数仅考虑使得margin最大同时错误率最小.但这种方法没有考虑到数据的扩散(spread)情况.例如有两组采样数据,第一组从(1,1)点开始向x轴正向扩散,第二组从(-1,-1)点开始向x轴负向扩散.传统的SVM会将y=x作为分类器,而事实上最好的分类器是y=0,并且如果数据沿x轴放缩(scale),采用SVM得到的分类器错误率还会上升.所以在最大化margin的同时,还需要考虑数据的扩散情况,使数据沿w方向的扩散程度最小.这就需要在目标函数中再加进一个正则项.接下来就是对新的目标函数的求解问题.

相关文献可参阅:

• http://books.nips.cc/papers/files/nips21/NIPS2008_0839.pdf

Seam Carving for Image Resizing

Seam Carving 是一种图像缩放技术。Shai Avidan 和 Ariel Shamir在07 Siggraph 提出，在08 siggraph 做了改进使得这种方法能扩展到video 的缩放。传统的图像缩放是基于如双线性差值的技术。这些技术在保持图像结构上是很好的，特别是在图像的相似变换（即图像宽和高之比不变的情况下）缩放是很好的。但是在实际应用中，由于各类显示屏的宽和高之比不完全相同，往往要有基于宽和高之比发生变化的图像缩放。对于这种缩放，通常是先在一个维度（比如宽）方向上缩放到目标宽度，然后再在高方向上做类似缩放。由于在seam carving 技术中，图像放大技术完全是基于图像缩小技术来做的，所以讨论seam carving性能时往往只考虑单独将图像宽（高）缩小一定比例来考察的。这个比例一般是1/3到1/2。 假如现在要将图像宽度缩一半，最直观的做法是将图像的某些不重要的列拿掉以达到宽度缩小的目的。而seam carving 的做法是更大胆的，它将图像中从第1行到最后一行8邻域连接路径（保证每行一个像素点）的seam 去掉。去掉k条seam，宽度缩小k。至于决定去掉哪些seam，backward seam carving 用了一阶梯度，forward seam carving 考察去掉seam后对图像的影响。

具体内容参见以下网站，里面有文章和demo以及做好的应用程序：

• http://www.faculty.idc.ac.il/arik/site/subject-seam-carve.asp
• http://www.faculty.idc.ac.il/Arik/SCWeb/vidret/index.html

Adaptive Template Matching with Shift-Invariant Semi-NMF

本文主要是使用semi-NMF(半非负的矩阵分解)解决模板匹配(template matching)问题。我们知道波形可以由一系列基本波形线性叠加而成，而模板匹配问题就是利用这样一些基本波形作为模板把原波形分离出来，通常都是要先知道模板然后才能做匹配找出每个模板对应的振幅(amplitude)，但是这样无疑需要事先存在一个模板字典，本文主要贡献是找到一种方法可以直接从原波形找出这样的基本波形,也即模板。由于NMF具有可以从源数据中找出组件的特性，本文就是利用了NMF的这一特性，直接分解出模板和振幅，由于模板本身不要求非负性，因此作者只拘束振幅为非负并且是稀疏的，这转化为一个semi-NMF问题，它的求解思路和C.Ding等人的semi-NMF非常类似，只不过C.Ding等人是用它解决聚类问题。
作者在合成数据和胞外记录(exteacellular recordings)上分别做了实验，结果显示该方法在合成数据上可以把有噪声的信号重构后形成无噪声信号，在胞外记录的实验上，该方法成功分离出两种基本信号(SD spike,IS spike).

文章下载地址：http://liinc.bme.columbia.edu/~lparra/publish/NIPS2008-SSNMF.pdf

MCboost:Multiple Classifier Boosting for Perceptual Co-Clustering of Images and Visual Features

本文主要介绍一种对Images和features进行同时聚类的方法。对于二分问题(object,non-object)，我们知道boost是一种非常有效的方法，它通过对简单弱分类器进行线性组合，够成一个强分类器来获得更精确的分类结果，其中每一个弱分类器通过一些或者单个简单的特征对图像进行分类。但是当object有多种表现形式时，如人脸有正面、侧面，各种形态的站姿等，这时对特征的简单线性组合并不能获得好的效果。

如果我们利用多个强分类器对图像进行分类，可能会获得比较好的结果。其中强分类的个数为object不同表现形式的种类，每个强分类器对不同的表现类进行负责(a Expert in one specified class)。只要有一个强分类器认为输入样本为正例，则为正例。只有所有分类器均认为是反例时，才判定输入样本为反例。强分类中的弱分类器仍然是特征的简单线性组合，但在每个强分类器中所作的贡献不相同。这样通过对一些给定样本的学习后，就能够得到一组强分类器，以及强分类中的重要分类特征(Co-Clustering)。

相关文章链接地址：

MCboost:Multiple Classifier Boosting for Perceptual Co-Clustering of Images and Visual Features

mi.eng.cam.ac.uk/~tkk22/doc/nips08_final.pdf

InformationTheoretic Co-clustering

www.cs.utexas.edu/users/inderjit/public_papers/kdd_cocluster.pdf

上学期讨论班(2008.9-2009.1)的博客

http://semi-supervised.blogspot.com/

如何做科研和写论文

http://www.iipl.fudan.edu.cn/~zhangjp/Resume/Advices.html

机器学习介绍

PPT 请从下面链接下载： 

http://www.iipl.fudan.edu.cn/~zhangjp/MachineLearningSeminar/ML_ZJP_2009.pdf

Compressed Sensing & Compressed Learning

Compressed sensing 又可以称为compressive sampling，是对香农采样定理的一种扩充。香农采样定理告诉我们，如果需要保证采样后信号的完全恢复，采样频率需要达到信号最高频的两倍。然而，对于稀疏信号（如信号覆盖了整个频率段，但其覆盖又是稀疏的）时，香农采样定理就显得比较保守。compressed sensing则告诉我们，对于属于R^n空间的，含有k个非零点的稀疏信号（ k << n )，我们不需要采集那么多点，而只需要采集O(C*k*logn)个点就足够了。

对于机器学习来说，若把数据存在的空间称为data domain，而我们观测到的数据所存在的空间称为measurement domain，通常情况下，这两个domain可能都非常大，就会遇到curse of dimensionality的问题，当然，machine learning有很多解决办法。Compressed learning其实也可以看成是属于其中的一种叫做“降维”的方法，就是使用m×n的采样矩阵A（ m << n ）对数据进行采样，再在采样后的数据上进行分类。Ref[2]讲的就是，当A满足(k,\epsilon)-RIP条件时，使用SVM在原始数据和在降维数据上的分类误差小于O(\sqrt{\epsilon})。

Ref：

1. E. J. Candès. Compressive sampling. Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006. http://www.acm.caltech.edu/~emmanuel/papers/CompressiveSampling.pdf
2. Robert Calderbank, Sina Jafarpour, and Robert Schapire, Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain (Preprint, 2009)

机器学习讨论班日程安排

内容安排：

3.17: 何力: Approximate Inference.
3.24: 张军平, 机器学习基础; 浦剑，Compressive Sensing;
3.31: 王晓丹, NMF; 谭奔: 多侧面学习;
4.7: 周骥：在线学习；骆思强：Image Resizing
4.14: 王晨: 图像超分; 潘墨益: Trust-Region
4.21: 范一鸣; 顾海杰: 步态识别
4.28: 张晨栋: 非负矩阵; 康卓梁: 视觉感知的Saliency Map

5.5:   宋海：多示例学习；李想: CCA
5.12: 何力 (TBA) 
5.19: 浦剑；王晓丹;  (TBA)
5.26: 谭奔；周骥 (TBA)

具体时间：每周二晚6:30

地点：老逸夫楼2-202小报告厅

Introduction to Approximate Inference Methods

This talk includes a gentle introduction of statistical modelling methodology in machine learning for the new audience in this seminar and its aim is to make its audience aware of several common approximate inference algorithms in nowadays Bayesian models, namely:

• Laplace approximation,
• (global) variational approximation,
• (local) variational bounds,
• expectation propagation.

You may find most of the topics and examples in Bishop's book Pattern Recognition and Machine Learning.

Date 6:30 pm, March 17