Max-margin Classification of Data with Absent Features

摘要: We consider the problem of learning classifiers in structured domains, where some objects have a subset features that are inherently absent due to complex relationships between features. Unlike case feature exists but its value is not observed, here we focus on may even exist (structurally absent) for samples. The common approach handling missing discriminative models first complete their unknown values, and then use standard classification procedure over completed data. This paper focuses known be non-existing, rather than an value. show how incomplete data can classified directly without any completion using max-margin framework. formulate objective function, based geometric interpretation margin, aims maximize margin each sample own relevant subspace. In this formulation, linearly separable transformed into binary search series second order cone programs (SOCP), convex solved efficiently. also describe two approaches optimizing general case: approximation as quadratic program (QP) iterative solving exact problem. By avoiding pre-processing phase which completed, both these could offer considerable computational savings. More importantly, elegant values by our allows it outperform other methods when non-trivial structure, competitive with at random. demonstrate results several benchmarks real-world problems: edge prediction metabolic pathways, automobile detection natural images.