Center for Advanced Intelligence Project

Speaker: Miao Xu (PhD student at Nanjing University, China)
http://lamda.nju.edu.cn/xum

Title: Incomplete Multi-Label Learning

Abstract: Multi-label learning, which assumes one instance is associated with multiple labels, has got wide range of applications in the last decade. Although multi-label learning has got successful applications, it will cost a lot of time and efforts for human beings to annotate all the multiple labels for all data. Thus in reality, we are always facing the problem of incomplete annotations in multi-label learning. This presentation will describe our efforts on solving the incomplete multi-label learning problem. Specially, when entries in the annotation matrix are uniformly random missing, one direct solution is to use the matrix completion technique to recover the partial matrix. Since existing matrix completion techniques cannot use side information in multi-label learning, we propose a novel algorithm and show theoretically that exploiting side information in matrix completion can dramatically reduce the number of entries required to do perfect recovery. We further noticed that in incomplete multi-label learning, some instances/labels may have complete annotations while for other instances/labels, annotation information are randomly missing. We propose a CUR-style algorithm which can deal with partial matrix to solve this problem, with theoretical guarantee on both low-rank and high-rank matrices. Experimental results validate our proposed methods’ merit compared to baselines.