M.Sc Thesis

M.Sc StudentOrbach Matan
SubjectSemi-Supervised Learning with Confidence
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROF. Yacov Crammer


We present a new multi-class graph-based transduction algorithm. Examples are associated with nodes in an undirected weighted graph and edge weights measure similarity between examples. Typical algorithms in this setting perform label propagation between neighbours, ignoring the quality, or estimated quality, in the labeling of various nodes. We introduce an additional quantity of confidence in label assignments. Confidence information is learned jointly with the label assignments, while being used to dynamically tune the influence each node has on its neighbours during label propagation. We cast learning as a convex optimization problem, and derive an efficient iterative algorithm for solving it. Empirical evaluations on Natural Language Processing (NLP) and speech (TIMIT) data sets, with more than one million examples, demonstrate our algorithm improves over other state-of-the-art graph-based transduction algorithms.