Machine Learning, On-line Decision Making, and Algorithms for Computationally Hard Problems

Summary (abbreviated):

The focus of this research is on developing efficient combinatorial algorithms for key problems in Artificial Intelligence and Optimization, as well as providing an improved understanding of the inherent nature of these problems. This project involves three areas in particular: machine learning, on-line decision-making, and the study of algorithms for computationally hard problems. In the area of machine learning, this includes problems of how to best combine a multiple low-quality sources of advice, learnability questions with close relations to coding theory and cryptography, and general questions about algorithms and sample complexity. In the area of on-line algorithms and on-line decision making, this research will investigate new algorithms, including the potential for using methods from machine learning (for instance, algorithms for combining sources of advice) to produce improved solutions to a number of problems in this area. In the study of computationally hard problems, this project will continue exploration of new and better approximation algorithms, as well as a new approach to general purpose planning based on representing planning problems in a compact graph structure, and then bringing in tools and ideas from graph algorithms. This planning method was first demonstrated in the Graphplan planner, and empirically appears to be substantially faster than more traditional planning algorithms in a wide variety of settings.

Progress: 1998-1999

• Machine Learning. A classic, yet still critically important question in Machine Learning is: how can we best predict how well a hypothesis produced by a given learning algorithm on a given set of data will perform on new, unseen data? One standard method for addressing this issue is to partition data into a training set and a holdout set --- the training set is given to the learning algorithm, and the resulting prediction rule is tested on the holdout set to gauge its true effectiveness. Another standard method is called k-fold Cross-Validation. In this method, we split the data into k pieces, and for each piece, we view that piece as a holdout set in the previous method, finally averaging the k estimates produced.

  In Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation (1999 Conference on Computational Learning Theory), we give a new analysis giving broad conditions under which the second method is, in fact, to be preferred over the first. We also describe a new method, progressive validation, that enjoys several advantages over these approaches.

  In Microchoice Bounds and Self Bounding Learning Algorithms (1999 Conference on Computational Learning Theory), we describe a new analytical approach that can be used within the learning algorithm itself, without need for a holdout set. This improves on similar proposed methods by being much more efficient computationally (in many cases, turning an exponential-time computation into a linear or quadratic one) with little if any loss in performance.

• On-line Algorithms. In Finely-Competitive Paging (1999 Symposium on Foundations of Computer Science, pp. 450-458), we give a new algorithm for the classic disk-paging problem with performance guarantees that are in a sense better than the standard "optimal" online algorithms, under a more fine-grained notion of competitive ratio. The proposed algorithm is not currently practical because of the large computational resources needed to compute its decisions. Nonetheless, it provides a glimpse into what might be achievable, and we are currently working on improving its efficiency. An interesting feature of the algorithm is its use of Machine Learning techniques in its inner decision-making loop.

• Planning. The problem of "general-purpose propositional planning" is a classic computationally hard problem. In previous work, we developed the Graphplan planner, that uses a representation based on viewing planning as a network flow problem to attack the problem in a new way. This method has been determined empirically to perform substantially better than previous approaches on a wide variety of problems. In Probabilistic Planning in the Graphplan Framework (5th European Conference on Planning), we explore the extent to which this approach can be used for probabilistic planning. Probabilistic planning involves its own set of difficult challenges, and requires a substantial overhaul of the basic algorithm. Nonetheless, preliminary results look quite good so far.

Progress: 1999-2000

• PAC Learning in the presence of noise. The goal of this work is to understand the kinds of concepts that can be learned efficiently from noisy data in the standard 'random misclassification noise' PAC model. Kearns in 1993 developed a key framework called the 'statistical query' model and proved that anything learnable in that model can also be learned in the presence of random noise in the standard PAC model. However, this left open the question whether there might exist radically different algorithms for learning concepts in the presence of noise that are *not* learnable via Statistical Queries. For example, parity functions are provably not learnable via Statistical Queries, but it is unknown whether or not they are learnable with noise (this is closely related to a longstanding open problem in cryptography).

  In Noise-tolerant Learning, the Parity problem, and the Statistical Query model (32nd Annual Symposium on Theory of Computing) we developed the first known algorithm for learning a class of concepts in the presence of noise that provably cannot be learned in the Statistical Query model. The specific class is a subclass of parity functions, and this result also implies a (somewhat small) improvement in the best running time known for learning the general class of parity functions (reducing the time from 2^n to 2^{O(n / log n)}. There are a number of connections between these problems and issues in cryptography and approximation algorithms, and we are hopeful that these methods will lead to further improvements in the future.

• Learning "Robust" prediction rules. Standard machine learning algorithms are in some sense 'lazy': they only extract the minimum amount of information from their data needed to classify the training set. They do not search for other, secondary, information that might be useful to know of in case the primary information is somehow missing or obscured when the algorithm is applied 'in the field'. Our goal was to develop new kinds of learning methods that would be more robust in this sense.

  In FeatureBoost: A Meta Learning Algorithm that Improves Model Robustness (ICML 2000), we develop a formal framework for studying this problem, as well as new algorithms that appear promising in preliminary experiments. These algorithms involve applying a "boosting-like" wrapper around a standard learning algorithms, subjecting them to data in which different subsets of features have been corrupted, and then combining the results in a weighted vote. A number of experiments on synthetic data suggest that this method can provide a substantial amount of robustness even when the original learning algorithm was quite brittle.

Progress: 2000-2001

• Using graph cuts for machine learning. There is a long history of work on algorithms for different kinds of graph partitioning problems. The simplest of these is the minimum s-t cut, which can be found using Network Flow. Recently, these algorithms have found use in Computer Vision as tools for image segmentation and various "image cleaning" types of applications. In this work, we have begun an invesigation into how graph cut algorithms can be used in machine learning. The basic idea is to construct a graph whose nodes are (labeled and unlabeled) examples, and whose edges are weighted based on how "similar" the two endpoints are. Labeled examples are also connected to special class-nodes indicating their given label. The idea, then, is that graph cut algorithms can implement a kind of nearest-neighbor learning in which we add an additional clustering-style objective that similar unlabeled examples should generally be given the same label. The end result can be viewed as a maximally "self-consistent" classification of the unlabeled data.

  In Learning from Labeled and Unlabeled Data using Graph Mincuts (Avrim Blum and Shuchi Chawla, ICML'01) we explore a number of design issues involved with this approach, and demonstrate that it can indeed provide significant benefit when large amounts of unlabeled data are available, as well as when labeled data is noisy.

• Online admission control. In the admission control problem, we are charged with managing a communication network (a graph with edge capacities) in the presence of online requests for communication (calls). Requests may be accepted or rejected, and the goal of an online algorithm is to accept as many as possible while staying within the edge capacities of the network. Prior work on this problem has focused on the ratio of the number of calls accepted by the online algorithm to the maximum possible that could have been accepted in hindsight. In most cases, online algorithms can be constructed to achieve a 1/log(n) ratio: accepting at least 1/log(n) times as many calls as the optimal offline algorithm.

  In Admission control to minimize rejections (Avrim Blum, Adam Kalai, and Jon Kleinberg, WADS '01 (LNCS 2125, pp.155-164, 2001)), we revisit this problem from the point of view of approximately minimizing the number of calls rejected. In a number of cases, we show it is possible to reject at most twice as many calls as the best in hindsight. Thus, if the optimal straegy in hindsight accepted 99% of calls, then this algorithm accepts at least 98%. In contrast, algorithms designed for the "benefit" formulation might accept only an 0.99/log(n) fraction of the calls. Thus, by changing the focus (from the accept ratio to the reject ratio) we can achieve what may be a much better guarantee.

• Smoothed complexity of linear programming (in progress). In joint work with John Dunagan, we show that the simple Perceptron Algorithm achieves good perormance for linear programming in the recently developed "smoothed complexity" model, comparable to (and in some ways better than) what has been shown for the Simplex algorithm.

• Machine learning for adaptive data structures (in progress). In joint work with Shuchi Chawla and Adam Kalai, we are exploring how ideas from online machine learning can be used to give new bounds for a number of problems in adaptive data structures. For example, we show how to achieve a (1+epsilon) static competitive ratio for the list update problem, and how to achieve something we call "dynamic search-optimality" for adaptive search trees.

This material is based upon work supported by the National Science Foundation under Grant No. CCR-9732705. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).