这是2009年发表在CVPR上的一篇文章。Transductive Learning是半监督学习的一种情况,也是利用数据的部分约束信息来得到整体的数据分类。本文主要有两个贡献,第一个是使用一种无参的算法构建双随机矩阵,这种矩阵受噪声数据影响很小并且能近似的描述数据的簇类信息。下面,首先介绍如何学习图的邻接矩阵,然后介绍如何进行标签传递。
1. 图邻接矩阵的构建
本文目标在于构建一个双随机矩阵,这种矩阵在谱聚类中表现良好,能够得到分段常数的特征向量。双随机矩阵满足矩阵是对称和非负的,并且W1=1.文中在学习带约束的相似度矩阵时只采用了处于不同类的标签信息,将不同类和对角线上的相似度置为0。学习新的相似度矩阵时假设最终结果矩阵和原始的矩阵要足够的接近。要满足以上几个方面,目标函数如下所示:
上面的优化问题是一个标准的二次规划问题,文中求解时将其转化为两个子凸优化问题。
2.多分类的标签传递过程
同很多问题一样也使用了谱图理论中的平滑度衡量目标tr(F'LF),其余的每个小约束是从概率的角度考虑的。Yl是给定的约束信息,Fl=Yl是当然要满足的,F1c=1是指每一个点属于每个类的高楼之和要等于1.
第三个约束条件是从每个类出发的,其中
。
W'1c=1代表在整个数据集中每个类的概率之和为1.然后将p(Ck)用条件概率的形式展开并整理得到上式的结果。该部分问题的核心在于用Fij代表第i个点属于第j个类的概率。
https://blog.sciencenet.cn/blog-795564-646640.html
下一篇:
NMF with label constraints