טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMatan Orbach
SubjectSemi-Supervised Learning with Confidence
DepartmentDepartment of Electrical Engineering
Supervisor Professor Crammer Yacov
Full Thesis textFull thesis text - English Version


Abstract

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.