A Sampling Theory Perspective of Graph-Based Semi-Supervised Learning
A Sampling Theory Perspective of Graph-Based Semi-Supervised Learning
复制标题
DOI：
10.1109/tit.2018.2879897
复制
发表时间：
2019-04-01
影响因子：
2.5
通讯作者：
Ortega, Antonio
中科院分区：
文献类型：
--
作者：
Anis, Aamir;El Gamal, Aly;Ortega, Antonio
基于图的方法在解决无监督和半监督学习问题方面非常成功，因为它们提供了一种捕获数据集底层几何形状的方法。通常期望构造的图满足两个性质：第一，在特征空间中相似的数据点应该在图上强连接，第二，类标签信息应该相对于图平滑地变化，其中平滑度使用图拉普拉斯矩阵的谱性质来测量。最近的工作证明了这些光滑条件，表明它们与半监督光滑假设及其变体密切相关。在这项工作中，我们加强了这种连接，从图形采样理论的角度来看，类指标函数被视为带限图形信号（在特征向量的基础上的图形拉普拉斯算子）和标签预测作为一个带限重建问题的问题。我们的方法包括分析带宽的类指标信号产生的统计数据模型与可分离和不可分离的类。这些模型非常通用，并且模仿了大多数真实世界数据集的性质。我们的结果表明，在渐近极限，任何类指标的带宽也密切相关的数据集的几何形状。这使得人们可以从理论上证明类指示信号的带宽限制的假设，从而提供了一个基于图的半监督分类的采样理论解释。
Graph-based methods have been quite successful in solving unsupervised and semi-supervised learning problems, as they provide a means to capture the underlying geometry of the dataset. It is often desirable for the constructed graph to satisfy two properties: first, data points that are similar in the feature space should be strongly connected on the graph, and second, the class label information should vary smoothly with respect to the graph, where smoothness is measured using the spectral properties of the graph Laplacian matrix. Recent works have justified some of these smoothness conditions by showing that they are strongly linked to the semi-supervised smoothness assumption and its variants. In this work, we reinforce this connection by viewing the problem from a graph sampling theoretic perspective, where class indicator functions are treated as bandlimited graph signals (in the eigenvector basis of the graph Laplacian) and label prediction as a bandlimited reconstruction problem. Our approach involves analyzing the bandwidth of class indicator signals generated from statistical data models with separable and nonseparable classes. These models are quite general and mimic the nature of most real-world datasets. Our results show that in the asymptotic limit, the bandwidth of any class indicator is also closely related to the geometry of the dataset. This allows one to theoretically justify the assumption of bandlimitedness of class indicator signals, thereby providing a sampling theoretic interpretation of graph-based semi-supervised classification.