| Abstract
|
:
|
Classification problems in machine learning involve assigning labels to various kinds of output types,from single assignment binary and multi-class classification to more complex assignments such ascategory ranking, sequence identification, and structured-output classification. Traditionally, mostmachine learning algorithms and theory is developed for the binary setting. In this dissertation,we provide a framework to unify these problems. Through this framework, many algorithms andsignificant theoretic understanding developed in the binary domain is extended to more complexsettings.First, we introduce Constraint Classification, a learning framework that provides a unified viewof complex-output problems. Within this framework, each complex-output label is viewed as a setof constraints, sufficient enough to capture the information needed to classify the example. Thus,prediction in the complex-output setting is reduced to determining which constraints, out of apotentially large set, hold for a given examplea task that can be accomplished by the repeatedapplication of a single binary classifier to indicate whether or not each constraint holds. Using thisinsight, we provide a principled extension of binary learning algorithms, such as the support vectormachine and the Perceptron algorithm to the complex-output domain. We also show that desirabletheoretical and experimental properties of the algorithms are maintained in the new setting.Second, we address the structured output problem directly. Structured output labels are col-lections of variables corresponding to a known structure, such as a tree, graph, or sequence thatcan bias or constrain the global output assignment. The traditional approach for learning struc-tured output classifiers, that decomposes a structured output into multiple localized labels to learnindependently, is theoretically sub-optimal. In contrast, recent methods, such as constraint clas-,..tested for theQ1 PC1 bus cardBoth these projects mere sofixare des elopment efforts tonards contributing to dlfferentaspects of Roboucs and lZ1echatronics projects m the Controls and Roboucs Group..
|