Search

In this paper, we provide a summary of the mathematical and computational techniques that have enabled learning reductions to effectively address a wide class of tasks, and show that this approach to solving machine learning problems can be broadly useful. Our work is instantiated and tested in a machine learning library, Vowpal Wabbit, to prove that the techniques discussed here are fully viable in practice.

We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process. Experiments on passively labeled data show that this approach reduces the label complexity required to achieve good predictive performance on many learning problems.

Discovering the topology of a network and detecting link state changes (e.g.: link failures) is an essential element for various network management and monitoring tasks. In this paper, we investigate scalable mechanisms to monitor the topology and link states of networks based on information available in network nodes' routing tables. We first present an algorithm that infers the network topology based on the full or partial information about network distances between nodes, based on which we obtain a scalable network topology discovery solution via a novel use of random walk in graphs. We then present scalable algorithms to detect the state changes of remote links by monitoring the routing tables of a small fraction of the routers, where the routers to be monitored are selected by a greedy approach to an NP-complete Tree Cover problem. We show the efficacy and scalability of our topology monitoring algorithms through experimental evaluation performed both on synthetic topologies and on a large topology data-set from a real enterprise network.

Machine learning involves optimizing a loss function on unlabeled data points given examples of labeled data points, where the loss function measures the performance of a learning algorithm. We give an overview of techniques, called reductions, for converting a problem of minimizing one loss function into a problem of minimizing another, simpler loss function. This tutorial discusses how to create robust reductions that perform well in practice. The reductions discussed here can be used to solve any supervised learning problem with a standard binary classification or regression algorithm available in any machine learning toolkit. We also discuss common design flaws in folklore reductions.

We consider the problem of localizing network performance bottlenecks and evaluate how various optimization techniques developed for reconstructing link delays perform on this decision problem. We provide some practical suggestions on which approach to use in different scenarios.

Real-time problem diagnosis in large distributed computer systems and networks is a challenging task that requires fast and accurate inferences from potentially huge data volumes. In this paper, we propose a cost-efficient, adaptive diagnostic technique called active probing . Probes are end-to-end test transactions that collect information about the performance of a distributed system. Active probing uses probabilistic reasoning techniques combined with information-theoretic approach, and allows a fast online inference about the current system state via active selection of only a small number of most-informative tests. We demonstrate empirically that the active probing scheme greatly reduces both the number of probes (from 60% to 75% in most of our real-life applications), and the time needed for localizing the problem when compared with nonadaptive (preplanned) probing schemes. We also provide some theoretical results on the complexity of probe selection, and the effect of "noisy" probes on the accuracy of diagnosis. Finally, we discuss how to model the system's dynamics using dynamic Bayesian networks (DBNs), and an efficient approximate approach called sequential multifault; empirical results demonstrate clear advantage of such approaches over "static" techniques that do not handle system's changes.

A common problem encountered in many application scenarios is how to represent some prior knowledge about a system in order to determine its true state as efficiently as possible. The information is typically in the form of tests, or questions about the system. Each test can potentially reduce our uncertainty about the system's state. The problem is to represent the information capturing the dependence between tests, their outcomes, and possible states in an efficiently navigable way to aid diagnosis. The most common such representation is a flowchart with leaf nodes corresponding to possible states, and non-leaf nodes corresponding to tests about the state. The problem with flowcharts is that they are notoriously difficult to maintain. Additional knowledge often has to be manually integrated as the system changes, making it impossible to keep track of all possible decision paths, let alone optimize the flow to maximize performance. We propose an efficient method for optimizing an existing flowchart based on a conversion to an auxiliary matrix representation. The main goal of the paper is show a synergy between the two representations in the hope that this will help practitioners choose a better strategy for their applications. We show that such a conversion suggests ways to improve both representations - ways that were not envisioned when using each representation alone. Finally, we show that the two representations are informationally equivalent in the sense that one can be transformed into the other so that if both are used as black-boxes, one would not be able to tell them apart, regardless of which state the system is in.

We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most e then the cost-sensitive classifier has cost at most 2e times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning.

An important issue in visualizing categorical data is how to order categorical values. The focus of this paper is on constructing such orderings efficiently without compromising their visual quality.