Influence without Authority: Maximizing Information Coverage in Hypergraphs

目录 DM

Influence maximization，影响力最大化，是信息传播相关的一个经典问题，差不多发展有 20 年。传统的影响力最大化工作，主要是基于普通图，寻找到 k 个种子，最大化它们的影响力。即便如此，它也产生了非常多的变体，模型也趋于复杂。

跳出这个问题本身，可以发现很多相关的工作，并不能提供一个真实的验证场景。如何量化用户传递信息的概率，以及被激活的概率，是无法回避的问题。真实世界的社交网络中，可以获得很多额外数据，进而给用户画像，并得到量化后的数值。然而，科研工作很难做到这一步。这是无解的一个部分，除非去公司。

可不可以找一个好的问题切入角度，做模型简单优雅又比较有创新的工作？我从前几年的一篇 information coverage 工作中得到一些启发：既然很难去判断用户是否被激活，那为什么不考虑信息传播能达到的最大覆盖，也就是只考虑信息传达，而不考虑后续的激活等一系列操作。于是，我做了这个 超图上信息覆盖最大化 的工作。简单来说，就是 找哪几个微信群转发信息，最后更可能达到 10w+。

问题还是传统问题，但选取的是一个比较新的场景，问题分析，到解决，都做的比较扎实。自我评价为 A。

好问题+牛逼的方法，A+

好问题+经典方法，A

经典问题+牛逼的方法，A+

经典问题+经典方法，B+

Workshop in Vienna

目录 DM, Life

最近一个星期在维也纳大学，参与导师与师母组织的两个组之间的交流活动，感触挺多的。

国外的学生，在文献阅读方面，并不充分；但相比起来，他们的基本功更加扎实，遇到问题，可以更快做出demo；而我可能会提出很多思路，但在有限的时间里，很难做出demo。

想到了套瓷时候的经历，一个导师提供了面试机会，给了一个问题一天的时间，我列了三个思路，但并没有实现，然后就GG了。

国外导师，某种程度上，更注重demo？idea不一定靠谱，demo至少看上去有用。

或许，我需要转换一下研究思路了。

现在至少有5个一般的点子在堆着，积极合作，尽快做点东西出来。

Visualization of My Research Interests

目录 DM

Tools

  1. Mendeley
  2. Python
  3. WordArt.com

Steps

  1. Export papers in Mendeley to bib file.
  2. Cleaning via Python nltk.
  3. Frequency counter via Python (Github)
  4. Cleaning via Python nltk.
    • remove phrases with low frequency.
    • remove meaningless phrases
  5. Import the output file to WordArt
  6. Visualization
 

Lecture Note of Scientometrics

目录 DM

Rectenly, Prof. Liu JianGuo, from SUFE, gave a lecture about scientometrics in our center. The content is mainly resolved to real applications, and it shows very interesting problems. The lecture has four parts:

  • Ranking of Research Institutions Based on Citation Relations
  • Research of Deep Learning Based Quantitative Trading Strategies
  • Quantitative Trading Strategies Based on the Degree of Attention of Stocks
  • Which Kinds of Disclosed Information Can Help You Get a Loan From P2P

组会随笔（2018-05-12）

目录 DM

两个报告，分别是关于轨迹中的交通流，以及深度学习在推荐系统中的应用。

由于主要是在做应用，是典型的问题驱动，所以这里仅仅列出一些有趣的问题。至于方法，我目前对深度学习不了解，所以不评述。

轨迹交通流有关的研究问题：

  • 某个地区出租车的供需预测
  • 交通灯控制（红绿灯 – 交通摄像头）

其中，第一个问题可以抽象成 时序数据上的回归问题，和传统的机器学习比较接近。第二个问题，在我自己了解到的方向中较少出现，因为是涉及到决策的东西。摄像头提供交通流数据，以此作为切换红绿灯或者红绿灯频率的决策基础，而决策也会影响下一个时间点的交通流。这个过程可以建模成强化学习。

此外，姚还提到了一些当前轨迹交通流研究的热门：

  • coordination in the transportation network
  • continual adaption with changing environment
  • events detection
  • data quality（sparsity, noise）

确实是很有趣的问题，但以实验室目前的环境，做不了。相信大部分同学都有这样的感觉，实验室研究的东西，虽然还是数据挖掘的主流方向，但已经脱离应用很远了；至于数据挖掘的基础理论研究，也不见得做的有多深入，因此处于很尴尬的境地。

失落会有一些，但乐观一点想，我们在研究的问题，至少是自己喜欢的，很好奇的问题。即使目前看，它对于学科的发展和社会的推动毫无作用。但我们自己还是在前进，每次向前走一点点，也是一件开心的事情。

何况，目前的环境和研究的内容，对于长期发展，还是存在一定的帮助：

虽然研究的内容是传统的数据挖掘与机器学习，以shallow model为主，但其中涉及到的基础问题也是DL中关注的问题。与一开始就做DL的同学相比，我们对于各种基础理论的学习，如压缩感知，线性代数，各种凸优化非凸优化；以及一些不入流的“小技巧”，锚点的学习，信息的传播和最大化间隔，等等；要更加熟悉。这些思想，在DL中也存在，也还待发掘。保持一种积极学习的心态，兼收并蓄，相信长期的积累，还是会带来回报。

十年了。

Structural SVMs with its Application in Recommender System [Seminar Note]

目录 DM
Paper Sharing: Predicting Diverse Subsets Using Structural SVMs [ICML’08]

Motivation
Diversity in retrieval tasks, reduces redundancy, showing more information.
e.g. A set of documents with high topic diversity ensures that fewer users abandon the query because no results are relevant to them.
In short, high diversity will cover more needs for different users, though the accuracy may not be good.

Preliminary
Candidate set: x = {x_i}, i = 1 … n
Topic set: T = {T_i}, i = 1 … n; T_i contains x_i, different topic sets may overlap.

Idea
The topic set T is unknow, thus the learning problem is to find a function for predicting y in the absence of T.
Is T the latent variable ??
– In general, the subtopics are unknown. We instead assume that the candidate set contains discriminating features which separates subtopics from each other, and these are primarily based on word frequencies.
The goal is to select K documents from x which maximizes subtopic coverage.

Keypoint: Diversity -> Covering more subtopics -> Covering more words

Method Overview

D1, D2, D3 are three documents, V1, V2, … , V5 are words.
weight word importance (more distinct words = more information)

After D1 is selected in the first iteration, which covers V3, V4, V5;
In the second iteration, we only focus on V1 and V2.

Remark:
– Feature space based on word frequency
– Optimizes for subtopic loss (Structural-SVM)

The process of this model is sophisticated. Feature space is based on word frequency, and it further divided into “bag of words” (subtopic).

From my point of view, a reason should be: each document has too many words, so dividing document into subtopics is reasonable, and this approach will reduce the overlapping between subtopics of different documents.
In each iteration, we learn the most representative subtopic, then choose the related document until we get K documents.

Remark: Structural-SVM repeatedly finds the next most violated constraint until set of constraints is a good approximation.

Comments
This paper is very interesting.
My doubts are:

  1. Can frequency of word reflect the true relevance of the document to a certain topic?
  2. How to find subtopics?

Further Reading
Learning to Recommend Accurate and Diverse Items [WWW’17]

An Intro to Subspace Clustering [Seminar Note]

目录 DM

Subspace Clustering

For the generation of clusters, often a part of features are relevant, especially for the high dimensional data. From this point of view, a number of clustering methods are proposed to find clusters in different subspaces within a dataset.

Two Perspectives

  • There exists subspace in data, so we search for the most representative feature subsets.
  • As there are clusters in different subspaces, features are more dense in each subspace cluster. Instance within a cluster can be represented by other instances within the same cluster. From this perspective, we seek to learn a representation of data, which yield X=XC.

The first perspective motivates many data mining algorithms (see survey by Parsons L. et. [1]). But due to the complexity of those algorithms, they can not handle large scale datasets. Recently, the majority of subspace clustering researchs are considering from the second perspective. By making different assumptions: the sparsity or the low-rank property, these methods can be generally divided into sparse subspace clustering [2] or low-rank subspace clustering [3].

Note that learning a representation of itself in the form of X=XC is very simple. To improve this model, a sort of algorithms consider using dictionary learning in subspace clustering, to learn a clean dictionary and an informative code, which yield X=DC. That is a big topic, see survey by Zhang Z. etc. [4] and survey by C Bao. etc [5].

Paper Sharing: Deep Adaptive Clustering [6]

Motication
In image clustering, existing methods often ignore the combination between feature learning and clustering.

Method
DAC is based on deep network, so we just give the flowchart. Firstly, a trained ConvNet is given to generate features, which guarantee the basic capacity of separation. Based on the learned features, traditional similarity learning is applied to find similar pairs and dissimilar pairs, similar to must-link and cannot-link in network mining. After obtaining those constraints, DAC goes back to train the ConvNet. That is one iteration.

The hint of DAC are that:

  • It adopts a classification framework for clustering.
  • The learned features tend to be one-hot vectors by introducing a constraint into DAC. Thus clustering can be performed by locating the largest response of the learned features.

Doubts
The performance of DAC is strongly dependent on the initialization of ConvNet. It is learned by another method.

Others
There are other ideas that using “supervised” model to clustering task. For example [7]

References

[1] Parsons L, Haque E, Liu H. Subspace clustering for high dimensional data: a review[J]. Acm Sigkdd Explorations Newsletter, 2004, 6(1): 90-105.

[2] Elhamifar E, Vidal R. Sparse subspace clustering[C]//Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009: 2790-2797.

[3] Vidal R, Favaro P. Low rank subspace clustering (LRSC)[J]. Pattern Recognition Letters, 2014, 43: 47-61.

[4] Zhang Z, Xu Y, Yang J, et al. A survey of sparse representation: algorithms and applications[J]. IEEE access, 2015, 3: 490-530.

[5] Bao C, Ji H, Quan Y, et al. Dictionary learning for sparse coding: Algorithms and convergence analysis[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(7): 1356-1369.

[6] Chang J, Wang L, Meng G, et al. Deep Adaptive Image Clustering[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017: 5879-5887.

[7] Liu H, Han J, Nie F, et al. Balanced Clustering with Least Square Regression[C]//AAAI. 2017: 2231-2237.

Feature Selection相关笔记

目录 DM

计划做一篇属性网络（Attributed Network）有关的工作。不同于拓扑网络，属性网络中的节点带有“特征”，因此，该问题中，除了网络的邻接矩阵，也存在节点属性构成的矩阵。研究属性网络，对理解网络的生成机制具有很现实的意义，如社交网络中好友关系的形成，也可以更好地解决社团挖掘（community detection）、链路预测（link predicting）这些衍生问题。

在了解的过程中，发现，属性网络的研究，有一部分是做在 特征选择 上。因为属性网络中节点的特征维度一般很低，且不稀疏，所以存在特征选择的可行性。联想到社交网络中，连边的产生并不一定是因为两节点所有的特征都很相似，可能是因为某些特别的地方，两节点之间的连边产生了，因此特征选择在理论上也具有一定合理性。

读相关的survey，发现了17年KDD上的一个tutorial与我想解决的问题比较相关。把阅读笔记分享出来:

矩阵有关梳理（待续）

目录 DM

在深度学习横行的今天，思考传统机器学习、数据挖掘有关的思想、流派和方法论，具有很实际的意义。

矩阵，在大多数问题中，都是二维数组。行表示item，对应列表示item的feature。从压缩感知开始，矩阵有关的方法开始井喷：基于低秩分解、稀疏表征的方法层出不穷，在图像处理上取得了非常卓越的效果，直到近年才被深度学习的有关算法超越；而NMF的分解形式早已有，近些年原理上的创新较少，多数工作还是在应用层面。

基于矩阵的方法优势在于，可以加各种形式的约束来达到想要的效果（好坏又是另一回事了⊙﹏⊙）。只要是非凸的优化函数，都比较好解，对非凸问题，在众多大牛的努力下，现在也有非常多的求解框架。劣势在于，矩阵有关的算法在线性问题上可以取得较好效果，但并不是很适合非线性问题。因此也有了概率矩阵分解（Probabilistic Matrix Factorization, PMF），在矩阵分解中引入概率，在推荐系统中有较多应用。

目前思考的还是很简单，没有加引用文献，很不学术。挖了个坑，慢慢填咯～

学期总结(学习篇)

目录 DM, Life

研一的学习生活结束了，做一个小小的总结。

主要课程有：
– 矩阵理论
– 随机过程
– 最优化
– 凸分析
– 机器学习

个人最喜欢的课程是《矩阵》《随机》《凸分析》以及《机器学习》，课程内容是一方面，老师的授课方式授课态度也不无关系。

《矩阵》的老师是本科时教授过我的《线性代数》的李老师，后来做美赛的时候他又是我的指导老师，研究生又选上了他的课，缘分颇深。李老师授课方式温文儒雅，是一位很“慢”的老师，也因此，不习惯他授课方式的同学经常会打瞌睡，我也是保持这听一小半、自学一大半的节奏。可能是因为研一上学期的时候，科研上很多地方都要用到矩阵，上课内容有些契合，学得挺开心。下学期的时候请教他矩阵优化有关的问题，李老师很耐心地解答，是一位很好的老师。

教授《随机》的覃老师是数院大boss之一，选课的人数非常多，他讲课也很有激情。覃老师的授课方式偏应试，会跳过很多“不重要”的内容，尽管如此，《随机》是我听的最认真的课程。因为它很有意思。概率是在刻画单个随机变量，随机过程则是在刻画样本中的所有随机变量。从水滴到波浪，还是波浪好看些。

《最优化》是研一学得最差的一门课，这个得拿出来说说。非数院的老师讲数学方面的专业课程，实力确实有所欠缺。于是，授课变成了听PPT复读机，可惜了这门好课。

《凸分析》是研一下的课程了。数院的张老师讲课非常细致，上课的课件是所用教材的PDF，然而基本没用上，张老师的板书非常好。学习这门课最大的收获是基本可以理解论文中的优化方法了，之前只知道how，现在对why也有一定理解了。虽然现在科研中遇到优化问题，第一反应还是去找其它工作有没有类似的，看看它们的解法，但谁又说得清以后会不会遇到不仅要求解、还要做收敛性分析的情况呢？

上面提到的主要是数学方面的课程，同在这个范围的还有《模式识别》、《图论》。这么一看，我选的大部分研究生课程都是数学课。数学确实是科研的有力武器！计算机方面选的最重要的课是《机器学习》。

徐老师开设的《机器学习》课程是计算机学院最火的两门课之一（还有一个是肖老师的《算法》），然而徐老师觉得大班的讲课效果并不理想，于是只开设42个人的小班。庆幸在选课那天的最后一轮，晚上11点多，刷了十多分钟，把别人退下的名额给重新选上了。这是一门很容易“发呆”的课程，因为课程上的内容与我所做的工作有很大的联系，所以上课的时候经常会想怎么用课程有关的内容来解决我的问题。因此，产生了很多不太靠谱的点子，虽然做paper review的时候发现大部分都被人做过了，但至少说明我的思考方向没有错，嗯，我就是这么安慰自己的:)

研一的课程学习已经结束，考试也都考完。暑假以及研二，没有课的生活，科研和工程，怎么走，考不考虑读博，需要思考决定的事情很多，希望这样的总结能对我的规划产生帮助。

自动文本摘要（Auto Text Summarization）

目录 DM

自动文本摘要（Auto Text Summarization>）是自然语言处理（NLP, Natural Language Processing）中一个比较难的任务。新闻的摘要要求编辑能够从新闻事件中提取出最关键的信息点，然后重新组织语言进行描述；一般论文的摘要要求作者先表述清楚问题，对前人工作中不完善的地方进行总结，然后用更凝练的语言描述自己的工作；综述性质的论文要求作者通读大量相关领域的工作，用最概括性的语言将每份工作的贡献、创新点写出来，并对每份工作的优缺点进行比较。本质上，文本摘要是一种信息过滤，输出的文本比输入的文本少很多，但却包含了主要的信息，有点类似主成分分析（PCA）。从某种意义上，文本摘要与推荐系统的功能类似，都是为了提取出用户感兴趣的内容，只是使用的方法有很大不同。

自动摘要技术应用最广的领域在新闻，由于新闻信息的过载，也由于很多新闻媒体为了哗众取宠，故意将标题起的特别吸引人眼球，但却名不副实，人们迫切地希望有一个工具可以帮助自己用最短的时间了解最多的最有用的新闻。搜索引擎也是应用之一，基于查询（Query）的自动文本摘要技术会帮助用户尽快找到感兴趣的内容。另外，随着智能设备的普及，自动摘要技术的使用也会为新的信息浏览与人机交互方式带来变革。

按照文档数量，文本摘要可以分为单文档摘要与多文档摘要，前者是后者的基础，但后者不只是前者结果的简单叠加。前者经常应用于新闻信息的过滤，而后者，在搜索引擎中有很大的潜力，难度也随之加大。

按照实现方式，可以分为两大类，提取式（Extractive）和摘要式（Abstractive）。

提取式的方法基于一个假设：一篇文档的核心思想可以用文档中的某一句或者几句话来概括。因此，文本摘要的任务就变成了找到文本中最重要的几句话，这通常是一个排序问题。在文档摘要问题中，基于图的排序算法，是以文档的每句话作为节点，句子之间的相似度作为边的权值构构建图模型，用PageRank算法进行求解，得到每个句子的得分，代表算法有TextRank【1】和LexRank【2】。基于特征工程的排序算法实用性更强，然而需要人为进行调整的部分也变得更多。文本摘要问题中经常使用到的特征包括句子长度、句子位置、句子是否包含标题词和句子关键词打分等，代表算法是TextTeaser，它由Jolo Balbin开发，作为他研究生课题的一部分，诞生伊始就应用于商业，直至2013年开源。由于只考虑了相关性而没有考虑新颖性，以上的排序算法很可能出现排名靠前的几句话表达的都是相似的意思，所以需要引入一个惩罚因子，在对排在后面的句子进行评分时，对它与在它之前的句子的相似度进行惩罚，也就是MMR（Maximum Margin Relevance）算法【3】。以上是提取式的自动摘要算法，其输出结果是不同段落中选择出来的Top K的句子，因此摘要的连贯性、一致性很难保证。

摘要式的方法是一种生成式的方法，它要求系统理解文本所表达的意思，然后用可读性强的人类语言将其简练地总结出来。这里包含几个难点：

  1. 理解文本。与人类阅读文本类似，需要明白文本表达的意思，涉及到的话题等。
  2. 可读性强。可读性是指生成的摘要能够连贯与衔接。
  3. 简练总结。即在理解文本的基础上，用尽可能简洁的文本表达最核心的部分。

上述难点即使对于人类也不是一件容易的事情，对于计算机更是。虽然在一些领域中，由于计算机强大的计算能力，人工智能能够领先于人类，但在更多的领域，例如机器翻译、文本摘要，AI离人类的水平还很遥远。

近几年随着深度学习（Deep Learning）的发展，研究者们开始尝试将一些最新的研究成果应用于自动文本摘要，尤其是机器翻译（Machine Translation）中的Encoder-Decoder框架和Attention机制。从这个思路可以将文本摘要问题转化为一个Sequence-2-Sequence问题，由此产生了基于RNN的Attention Model【4】，基于CNN的ABS（Attention-Based Summarization）【5】等。在一定程度上，它们实现了摘要式的自动文本摘要，但还是处于研究初期，效果不算太好。

目前使用到的语料数据分为两种，一种是用于训练深度网络的大型语料，一种是用来参加测评的小型语料。前者经常使用CNN、Daily Mail等提供的新闻数据集。后者通常使用TAC（Text Analysis Conference）提供的小型数据集。关于中文语料数据集，常用的是哈尔滨工业大学（深圳）智能计算研究中心开放的LCSTS（Large Scale Chinese Short Text Summarization Dataset），数据主要采自新浪微博，是一个短文本摘要数据集。

关于评价方法，人工评价自不用提，自动评价目前公认的只有Lin在2003年提出的ROUGE（Recall-Oriented Understudy for Gisting Evaluation）指标【6】，基本思想是将待审的摘要和参考摘要的n元组共现统计量作为评价作为评价依据，然后通过一系列标准进行打分，包括：ROUGH-N、ROUGH-L、ROUGH-W、ROUGH-S和ROUGH-SU几个类型。通俗来说是通过一些定量化的指标来描述待审摘要和参考文摘之间的相似性，例如共同出现次数、最长相同文本长度、带权最长相同文本长度等。

 
 
 

相关链接：(site: 自动文摘)

[1] Mihalcea R, Tarau P. TextRank: Bringing order into texts[C]. Association for Computational Linguistics, 2004.

[2] Erkan G, Radev D R. Lexrank: Graph-based lexical centrality as salience in text summarization[J]. Journal of Artificial Intelligence Research, 2004, 22: 457-479.

[3] Carbonell J, Goldstein J. The use of MMR, diversity-based reranking for reordering documents and producing summaries[C]. Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1998: 335-336.

[4] Lopyrev K. Generating news headlines with recurrent neural networks[J]. arXiv preprint arXiv:1512.01712, 2015.

[5] Rush A M, Chopra S, Weston J. A neural attention model for abstractive sentence summarization[J]. arXiv preprint arXiv:1509.00685, 2015.

[6] Lin C Y, Hovy E. Automatic evaluation of summaries using n-gram co-occurrence statistics[C]. Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume 1. Association for Computational Linguistics, 2003: 71-78.

高维语义与低维表征

目录 DM

回家在车上想到的，我能否通过高维语义与低维表征中的这种不匹配关系来刻画子空间之间的相关性，而不是通过学习出的相似性矩阵中存在的重合(overlapping) ?!

【组会】从稀疏表征到低秩表征

目录 DM


稀疏性(sparse)与低秩性(low-rank)是矩阵最重要的两个性质，数学家在研究矩阵分解(Matrix Decomposition, Matrix Factorization, Matrix Completion)的过程中，从最开始的纯数学上的分解(如 SVD,NMF)，终于发展到从矩阵自身性质的角度考虑，产生了稀疏分解与低秩分解两个流派。一般情况下，矩阵不会同时具有稀疏性与低秩性，但注意到在矩阵分解中，分解出的矩阵不止一个，因此 X = L + E 可以分解出一个稀疏矩阵与一个低秩矩阵，称为稀疏低秩分解(Low-rank & Sparse Matrix Decomposition)，代表是robust PCA算法。目前，矩阵分解或者矩阵恢复在各种类型的工作中都被充分利用，产生了压缩感知的方法，图像领域的图像恢复，识别，使用矩阵分解做聚类等。与之相关的，我们先了解矩阵的这两种表征方式，然后再介绍有关的应用。

稀疏表征

稀疏表征，从字面上的意思，是希望矩阵很稀疏，也就是大部分元素为0。给定原始空间中的矩阵 X ，找到某个空间中的一组基 Y ， X 在 Y 上的表达为 Z ，因此有：

min L0(Z) s.t. X = YZ

既然 Z 是矩阵在另外一个空间上的表达，希望 Z 更加稀疏，也就是稀疏表征的目的，本质上，也是一种降维的思路。换一种说法，给定的 m维空间中有一组 过完备的基(m*n的矩阵，m << n)，如何选择最少个数的 基向量，重构它自己。

task

问题来了，注意到 X 是两个变量的乘积，在没有先验知识的情况下是不可解的。我们寻求的是 X 的稀疏表征 Z ，在这里， Y 并不是主要因素。如果将 Y 用 X 替代，不也可以理解为通过 X 来寻找它自身空间里的一个更稀疏的表征：

min L0(Z) s.t. X = XZ

 

min L1(Z) s.t. X = XZ

现在只有一个待求解变量了，而且也有正则项，可以通过范数求解。但L0范数的求解是一个NP问题，所以选取了它的近似，L1范数。求解过程这里不作讨论，其对应算法，会在之后单独介绍。

低秩表征

随着对现实数据认识的加深，发现矩阵的表象(稀疏性)在很多场合已经不能起到更多的作用，所以数学家们开始考虑更多的情况。如在稀疏表征中考虑噪声E的影响，但由于原有的数据已经很稀疏，分离出一个稀疏矩阵与一个更稀疏的噪声矩阵E，这种思路的可行性值得怀疑，实验检验也表示这种方法的鲁棒性很差。稀疏性已经不足以满足需要，所以自然想到矩阵的另一个重要性质——低秩性。矩阵的秩表示矩阵非零奇异值的个数。矩阵的低秩性表示矩阵可以使用更少的向量去进行表征，在高维数据中的体现尤为明显。先给出一个朴素的优化函数：

min rank(Z) s.t. X = XZ

核范数是矩阵秩的凸，比较好求解，因此，很多时候直接使用核范数表示。

考虑到现实数据中存在的各种噪声，可以确认我们的目标：给出 X ，X = L + E ，恢复出低秩矩阵 L 与稀疏矩阵 E 。这是低秩性在矩阵恢复中的应用，在低秩表征中，优化函数有细微不同。

min rank(Z) + L0(E) s.t. X = XZ + E

同样，这个优化函数不能直接求解，需要使用到它们的凸近似。最终，LRR的优化函数可以写成：

min norm(Z) + L1(E) s.t. X = XZ + E

对随机的噪声，选取L1范数效果较好；对列稀疏的噪声，选取2-1范数；对白噪声(噪声服从高斯分布)，选取F范数。

这里简单介绍一下LRR的推导。低秩表征可以写成：

min norm(Z) s.t. X = XZ

考虑噪声后：

min norm(Z) + L1(E) s.t. X – E = (X – E)Z

注意到这个优化函数是非凸的，很难求解，需要用到特殊的方法(Paolo, Rene, and Avinash, “A Closed Form Solution to Robust Subspace Estimation and Clustering”, CVPR’11)。这不太优雅，于是继续研究，发现E是一个稀疏的噪声矩阵， EZ≈0 ，于是约束条件变成了 X = XZ + E ，后来的证明表示，在一定条件下这两个函数等价。

总结

SR与LRR是矩阵表征最重要的两种方式，在数据挖掘中，SR常与聚类结合在一起，LRR不只可以做聚类，也常用在矩阵恢复。(如需要进一步了解，可以阅读笔者的组会报告：slider)

参考文献

  • Elhamifar E, Vidal R. Sparse subspace clustering[C]. Computer Vision and Pattern Recognition, 2009. CVPR 2009.
  • Elhamifar E, Vidal R. Sparse subspace clustering: Algorithm, theory, and applications[J]. IEEE transactions on pattern analysis and machine intelligence, 2013.
  • Liu G, Lin Z, Yu Y. Robust subspace segmentation by low-rank representation[C]. Proceedings of the 27th international conference on machine learning, ICML-10.

 

【组会】从稀疏表征到低秩表征

目录 DM

稀疏性(sparse)与低秩性(low-rank)是矩阵最重要的两个性质，数学家在研究矩阵分解 (Matrix Decomposition, Matrix Factorization, Matrix Completion)的过程中，从最开始的纯数学上的分解(如 SVD, NMF)，终于发展到从矩阵自身性质的角度考虑，产生了稀疏分解与低秩分解两个流派。一般情况下，矩阵不会同时具有稀疏性与低秩性，但注意到在矩阵分解中，分解出的矩阵不止一个，因此…