Learning with Structured Data: Applications to Computer Vision

This thesis addresses structured machine learning problems. Here "structured" refers to situations in which the input or output domain of a prediction function is non-vectorial. Instead, the input instance or the predicted value can be decomposed into parts that follow certain dependencies, relations and constraints. The first part of the thesis considers structure in the input domain and a general framework based on the notion of substructures is developed. The framework is broadly applicable and two computer vision problems illustrate this: class-level object recognition and human action recognition. The second part of the thesis addresses structure in the output domain of a prediction function. Specifically image segmentation problems in which the produced segmentation must satisfy global properties such as connectivity are analyzed. As a result, a principled method to incorporate global interactions into computer vision random field models by means of linear programming relaxations is given.