Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights
演讲者： Gene Cheung
Abstract: In a semi-supervised learning scenario, (possibly noisy) partially observed labels are used as input to train a classifier, in order to assign labels to unclassified samples. We construct a complete graph-based binary classifier given only samples' feature vectors and partial labels. Specifically, we first build appropriate similarity graphs with positive and negative edge weights connecting all samples based on inter-node feature distances. By viewing a binary classifier as a piecewise constant graph-signal, we cast classifier learning as a signal restoration problem via a classical maximum a posteriori (MAP) formulation. One unfortunate consequence of negative edge weights is that the graph Laplacian matrix L can be indefinite, and previously proposed graph-signal smoothness prior x^T L x for candidate signal x can lead to pathological solutions. In response, we derive a minimum-norm perturbation matrix Del that preserves L's eigen-structure---based on a fast lower-bound computation of L's smallest eigenvalue via a novel application of the Haynsworth inertia additivity formula---so that L + Del is positive semi-definite, resulting in a stable signal prior. Finally, we propose an algorithm based on iterative reweighted least squares (IRLS) that solves the posed MAP problem efficiently. Extensive simulation results show that our proposed algorithm outperforms both SVM variants and previous graph-based classifiers using positive-edge graphs noticeably.
Bio：Gene Cheung博士是日本东京国立情报学研究所副教授、香港科技大学兼职副教授。他的研究方向包括三维图像处理、图信号处理和睡眠信号处理分析等。发表期刊论文40余篇，会议论文100余篇，曾担任IEEE Transactions on Multimedia、DSP Applications Column in IEEE Signal Processing Magazine和SPIE Journal of Electronic Imaging的副主编，现任IEEE Transactions on Image Processing、IEEE Transactions on Circuits and Systems for Video Technology、EURASIP Signal Processing: Image Communication和APSIPA Transactions on Signal and Information Processing的副主编。Gene Cheung博士于1995年获康奈尔大学电气工程学士学位，1998年获美国加州大学伯克利分校信息科学技术学院硕士学位，2000年获美国加州大学伯克利分校信息科学技术学院博士学位。曾任东京惠普实验室高级研究员。