Deconstructive learning

This dissertation introduces the novel notion of deconstructive learning and it proposes a practical computational framework for deconstructing a broad class of binary classifiers commonly used in computer vision applications. While the ultimate objective of most learning problems is the determination of classifiers from labeled training data, for deconstructive learning, the objects of study are the classifiers themselves. As its name suggests, the goal of deconstructive learning is to deconstruct a given classifier by determining and characterizing (as much as possible) the full extent of its capability, revealing all of its powers, subtleties and limitations. In particular, this work is motivated by the seemingly innocuous question that given an image-based binary classifier C as a black-box oracle, how much can we learn of its internal working by simply querying it? To formulate and answer this question computationally, I will first describe a general two-component design model employed by many current computer vision binary classifiers, a clear demonstration of the division of labor between practitioners in computer vision and machine learning. In this model, an input image is first transformed via a (nonlinear) feature transform to a feature space and a classifier is applied to the transformed feature to produce the classification output. The deconstruction of such a classifier therefore aims to identify the specific feature transform and the feature-space classifier used in the model.;Accordingly, the process of deconstructing a classifier C will be formulated as the identification problem for its two internal components from a finite list F of candidate features and a finite list C of candidate classifiers. As the main technical components of the deconstruction algorithm, I will introduce three novel ideas: feature identifiers, classifier deconstructors and the geometric feature-classifier compatibility. Specifically, feature identifiers are a set of image-based operations that can be applied to the input images, and the different degree of sensitivity and stability of the features in the feature list F under these operations would allow us to exclude elements in F. The classifier deconstructors, on the other hand, are algorithms that can deconstruct classifiers in the candidate list C using a (relatively) small number of features by recognizing certain geometric characteristics of the classifier's decision boundary such as its parametric form. In this dissertation, I will present deconstruction algorithms for two popular families of classifiers in computer vision: cascades of linear classifiers and support vector machines. The interaction between elements in the feature and classifier lists during the deconstruction process is based on the notion of geometric feature-classifier compatibility that provides a principled and effective criterion for selecting the correct pair of feature and classifier as the output of the deconstruction process.;The bulk of this work will be devoted to realize the deconstruction framework in concrete and practical terms. In particular, I will present a variety of experimental results that validate the proposed deconstruction methods and demonstrate the viability of deconstructing computer vision algorithms. Interesting highlights of the experimental results include the deconstruction of the popular OpenCV pedestrian and face detectors and the demonstration of a kernel machine update/upgrade without using its source code. To the best of my knowledge, no similar results have been reported in the literature previously. Finally, in the last part of this dissertation, I will briefly speculate on the future application potential of deconstuctive learning.