Timezone: »

Relations between machine learning problems - an approach to unify the field
Robert Williamson · John Langford · Ulrike von Luxburg · Mark Reid · Jennifer Wortman Vaughan

Thu Dec 15 10:30 PM -- 11:00 AM (PST) @ Melia Sierra Nevada: Dilar
Event URL: http://rml.anu.edu.au/ »

The workshop proposes to focus on relations between machine learning problems. We use “relation” quite generally to include (but not limit ourselves to) notions such as: one type of problem being viewed special case of another type (e.g., classification as thresholded probability estimation); reductions between learning problems (e.g., transforming ranking problems into classification problems); and the use of surrogate losses (e.g., replacing misclassification loss with some other, convex loss). We also include relations between sets of learning problems, such as those studied in the (old) theory of “comparison of experiments”, as well as recent connections between machine learning problems and what could be construed as "economic learning problems" such as prediction markets and forecast elicitation.

Why: The point of studying relations between machine learning problems is that it stands a reasonable chance of being a way to be able to understand the field of machine learning as a whole. It could serve to prevent re-invention, and rapidly facilitate the growth of new methods. The motivation is not dissimilar to Hal Varian’s notion of combinatorial innovation. Another analogy is to consider the development of function theory in the 19th century and observe the rapid advances made possible by the development of functional analysis, which, rather than studying individual functions, studied operators that transformed one function to another.

Much recent work in machine learning can be interpreted as relations between problems. For example:
• Surrogate regret bounds (bound the performance attained for one learning problem in terms of that obtained for another) [Bartlett et al, 2007]
• Relationships between binary classification problems and distances between probability distributions [Reid and Williamson 2011]
• Reductions from class probability estimation to classification, or reinforcement learning to classification [Langford et al; 2005-]
More recently there have been connections to problems that do not even seem to be about machine learning, such as the equivalence between
• Cost-function based prediction markets and no-regret learning [Chen and Wortman-Vaughan 2010]
• Elicitability of properties of distributions and proper losses [Lambert 2011]

In fact some older work in machine learning can be viewed as relations between problems:
• Learning with real-valued functions in the presence of noise can be reduced to multiclass classification [Bartlett, Long & Williamson 1996]
• Comparison of Experiments [Blackwell 1955]

If one attempts to construct a catalogue of machine learning problems at present one is rapidly overwhelmed by the complexity. And it is not at all clear (on the basis of the usual description of them) whether or not two problems with different names are really different. (If the reader is unconvinced, consider the following partial list: batch, online, transductive, off-training set, semi-supervised, noisy (label, attribute, constant noise / variable noise, data of variable quality), data of different costs, weighted loss functions, active, distributed, classification (binary weighted binary multi-class), structured output, probabilistic concepts / scoring rules, class probability estimation, learning with statistical queries, Neyman-Pearson classification, regression, ordinal regression, ranked regression, ranking, ranking the best, optimising the ROC curve, optimising the AUC, regression, selection, novelty detection, multi-instance learning, minimum volume sets, density level sets, regression level sets, sets of quantiles, quantile regression, density estimation, data segmentation, clustering, co-training, co-validation, learning with constraints, conditional estimators, estimated loss, confidence / hedging estimators, hypothesis testing, distributional distance estimation, learning relations, learning total orders, learning causal relationships, and estimating performance (cross validation)!

Specific topics: We would solicit contributions on novel relations between machine learning problems, as well as theoretical and practical frameworks to construct such relations. We are not restricting the workshop to pure theory, although it seems natural the workshop will have a theoretical bent.

Who: We believe the workshop will be of considerable interest to theoretically inclined machine learning researchers, as it offers a new view as to how to situate one’s work. Furthermore we also believe it should be of interest to practitioners because being able to relate a new problem to an old one can save substantial work in having to construct a new solution.

• New relations between learning problems – not individual solutions to individual problems
• Visibility and promulgation of the “meme” of relating problems;
• We believe the nature of the workshop would suit the publication of workshop proceedings.
• Potential agreement to a shared community effort to build a comprehensive map of the relations between machine learning problems.

Author Information

Robert Williamson (Australian National University & Data61)
John Langford (Microsoft Research)

John Langford is a machine learning research scientist, a field which he says "is shifting from an academic discipline to an industrial tool". He is the author of the weblog hunch.net and the principal developer of Vowpal Wabbit. John works at Microsoft Research New York, of which he was one of the founding members, and was previously affiliated with Yahoo! Research, Toyota Technological Institute, and IBM's Watson Research Center. He studied Physics and Computer Science at the California Institute of Technology, earning a double bachelor's degree in 1997, and received his Ph.D. in Computer Science from Carnegie Mellon University in 2002. He was the program co-chair for the 2012 International Conference on Machine Learning.

Ulrike von Luxburg (University of Tübingen)
Mark Reid (Apple)
Jennifer Wortman Vaughan (Microsoft Research)
Jennifer Wortman Vaughan

Jenn Wortman Vaughan is a Senior Principal Researcher at Microsoft Research, New York City. Her research background is in machine learning and algorithmic economics. She is especially interested in the interaction between people and AI, and has often studied this interaction in the context of prediction markets and other crowdsourcing systems. In recent years, she has turned her attention to human-centered approaches to transparency, interpretability, and fairness in machine learning as part of MSR's FATE group and co-chair of Microsoft’s Aether Working Group on Transparency. Jenn came to MSR in 2012 from UCLA, where she was an assistant professor in the computer science department. She completed her Ph.D. at the University of Pennsylvania in 2009, and subsequently spent a year as a Computing Innovation Fellow at Harvard. She is the recipient of Penn's 2009 Rubinoff dissertation award for innovative applications of computer technology, a National Science Foundation CAREER award, a Presidential Early Career Award for Scientists and Engineers (PECASE), and a handful of best paper awards. In her "spare" time, Jenn is involved in a variety of efforts to provide support for women in computer science; most notably, she co-founded the Annual Workshop for Women in Machine Learning, which has been held each year since 2006.

More from the Same Authors