Seminar Room, ground floor (Building IMAG)
16 February 2017 - 10h00
Multi-label Classification with Pairwise Relations
by Naor Seffi from Technion Haifa
Abstract: Motivated by applications in multi-label learning, we introduce the metric multi-labeling problem. The objective here is to classify objects by labels while optimizing a linear cost function of both assignment costs and separation costs, which are deduced from pairwise relations between objects. Each object can be classified by multiple labels, which may have either positive or negative costs, thus departing from previous works, e.g., metric labeling.. The metric multi-labeling problem is NP-hard, and we tackle it by formulating an integer program capturing the deviation from a benchmark representing an ideal labeling. This approach, reminiscent of the notion of regret in online learning, allows us to cope with the possible negativity of the labeling costs. We develop a tight 2-approximation algorithm for metric multi-labeling by using an approach that distorts the optimal likelihood values computed by our linear programming relaxation. We extend the results to settings where the number of labels that can be given to an object is bounded.
Joint work with Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, and Roy Schwartz.
