UNIVERSALLY CONSISTENT VERTEX CLASSIFICATION FOR LATENT POSITIONS GRAPHS

• 成果类型: Article
• 署名作者: Tang, Minh; Sussman, Daniel L.; Priebe, Carey E.
• 署名单位: Johns Hopkins University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/13-AOS1112
• 发表日期: 2013
• 页码: 1406-1430
• 关键词: Kernel; matrix; error

摘要

In this work we show that, using the eigen-decomposition of the adjacency matrix, we can consistently estimate feature maps for latent position graphs with positive definite link function kappa, provided that the latent positions are i.i.d. from some distribution F. We then consider the exploitation task of vertex classification where the link function kappa belongs to the class of universal kernels and class labels are observed for a number of vertices tending to infinity and that the remaining vertices are to be classified. We show that minimization of the empirical phi-risk for some convex surrogate phi of 0-1 loss over a class of linear classifiers with increasing complexities yields a universally consistent classifier, that is, a classification rule with error converging to Bayes optimal for any distribution F.