Abstract
In real applications,data is not always explicitly-labeled.For instance,label ambiguity exists when we associate Iwo persons appearing in a news photo with two names provided in the caption.We propose a matrix completion-based method for predicting the actual labels from the ambiguously labeled instances,and a standard supervised classifier can learn from the disambiguated la-bels to classifjy new data.We further generalize the method to handle the labeling constraints between instances when such prior knowledge is available.Compared to existing methods,our approach achieves 2.9% improvement on the labeling accuracy of the Lost dataset and comparable per-formance on the Labeled Yahoo!News dataset.