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