In a semi-supervised learning scenario, (possibly noisy) partially observedlabels are used as input to train a classifier, in order to assign labels tounclassified samples. In this paper, we study this classifier learning problemfrom a graph signal processing (GSP) perspective. Specifically, by viewing abinary classifier as a piecewise constant graph-signal in a high-dimensionalfeature space, we cast classifier learning as a signal restoration problem viaa classical maximum a posteriori (MAP) formulation. Unlike previousgraph-signal restoration works, we consider in addition edges with negativeweights that signify anti-correlation between samples. One unfortunateconsequence is that the graph Laplacian matrix $\mathbf{L}$ can be indefinite,and previously proposed graph-signal smoothness prior $\mathbf{x}^T \mathbf{L}\mathbf{x}$ for candidate signal $\mathbf{x}$ can lead to pathologicalsolutions. In response, we derive an optimal perturbation matrix$\boldsymbol{\Delta}$ - based on a fast lower-bound computation of the minimumeigenvalue of $\mathbf{L}$ via a novel application of the Haynsworth inertiaadditivity formula---so that $\mathbf{L} + \boldsymbol{\Delta}$ is positivesemi-definite, resulting in a stable signal prior. Further, instead of forcinga hard binary decision for each sample, we define the notion of generalizedsmoothness on graph that promotes ambiguity in the classifier signal. Finally,we propose an algorithm based on iterative reweighted least squares (IRLS) thatsolves the posed MAP problem efficiently. Extensive simulation results showthat our proposed algorithm outperforms both SVM variants and graph-basedclassifiers using positive-edge graphs noticeably.
展开▼
