CiteULike: bsilverthorn's library [142 articles]

Failure of intuition in elementary rigid body dynamics

Nivaldo Lemos — 2008-07-11T21:09:52-00:00

(10 Jan 2008)

Suppose a projectile collides perpendicularly with a stationary rigid rod on a smooth horizontal table. We show that, contrary to what one naturally expects, it is not always the case that the rod acquires maximum angular velocity when struck at an extremity. The treatment is intended for first year university students of Physics or Engineering, and could form the basis of a tutorial discussion of conservation laws in rigid body dynamics.

Exploration exploitation in Go: UCT for Monte-Carlo Go

Sylvain Gelly — 2008-07-01T16:07:03-00:00

Twentieth Annual Conference on Neural Information Processing Systems (NIPS 2006) (2006)

Theoretical impediments to artificial intelligence

Michael Rabin — 2008-04-25T23:19:09-00:00

Information Processing (1974), pp. 615-619.

Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms

Frank Hutter — 2008-04-24T00:53:29-00:00

Principles and Practice of Constraint Programming - CP 2006 (2006), pp. 213-228.

Machine learning can be used to build models that predict the run-time of search algorithms for hard combinatorial problems. Such empirical hardness models have previously been studied for complete, deterministic search algorithms. In this work, we demonstrate that such models can also make surprisingly accurate predictions of the run-time distributions of incomplete and randomized search methods, such as stochastic local search algorithms. We also show for the first time how information about an algorithm’s parameter settings can be incorporated into a model, and how such models can be used to automatically adjust the algorithm’s parameters on a per-instance basis in order to optimize its performance. Empirical results for Novelty+ and SAPS on structured and unstructured SAT instances show very good predictive performance and significant speedups of our automatically determined parameter settings when compared to the default and best fixed distribution-specific parameter settings.

On Portfolios for Backtracking Search in the Presence of Deadlines

Huayue Wu — 2008-04-24T00:51:01-00:00

Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on, Vol. 1 (2007), pp. 231-238.

Constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that portfolios of backtracking algorithms--a selection of one or more algorithms plus a schedule for executing the algorithms--can dramatically improve performance on some instances. In this paper, we consider a setting that often arises in practice where the in- stances to be solved arise over time, the instances all belong to some class of problem instances, and a limit or deadline is placed on the computational resources that the backtrack- ing algorithm can consume in solving any instance. For such a scenario, we present a simple scheme for learning a good portfolio of backtracking algorithms from a small sample of instances. We demonstrate the effectiveness of our approach through an extensive empirical evaluation on a real-world instruction scheduling testbed.

Applying Machine Learning to Low-Knowledge Control of Optimization Algorithms

Tom Carchrae — 2005-10-02T09:03:26-00:00

Computational Intelligence, Vol. 21, No. 4. (November 2005), pp. 372-387.

Restart Policies with Dependence among Runs: A Dynamic Programming Approach

Yongshao Ruan — 2008-04-23T16:11:16-00:00

Principles and Practice of Constraint Programming - CP 2002 (2002), pp. 175-200.

The time required for a backtracking search procedure to solve a problem can be minimized by employing randomized restart procedures. To date, researchers designing restart policies have relied on the simplifying assumption that runs are probabilistically independent from one another. We relax the assumption of independence among runs and address the challenge of identifying an optimal restart policy for the dependent case. We show how offline dynamic programming can be used to generate an ideal restart policy, and how the policy can be used in conjunction with real-time observations to control the timing of restarts. We present results of experiments on applying the methods to create ideal restart policies for several challenging search problems using two different solvers.

Randomization and Restart Strategies

Huayue Wu — 2008-04-23T16:02:25-00:00

(2006)

Dynamic restart policies

Henry Kautz — 2008-04-23T16:01:16-00:00

(2002), pp. 674-681.

Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions

Kevin Leyton-Brown — 2008-04-23T02:17:55-00:00

Principles and Practice of Constraint Programming - CP 2002 (2002), pp. 91-100.

We propose a new approach for understanding the algorithm-specific empirical hardness of $$ \mathcalN\mathcalP $$ -Hard problems. In this work we focus on the empirical hardness of the winner determination problem—an optimization problem arising in combinatorial auctions—when solved by ILOG’s CPLEX software. We consider nine widely-used problem distributions and sample randomly from a continuum of parameter settings for each distribution. We identify a large number of distribution-nonspecific features of data instances and use statistical regression techniques to learn, evaluate and interpret a function from these features to the predicted hardness of an instance.

Adaptation in Natural and Artificial Systems

John Holland — 2008-04-22T20:35:19-00:00

(1975)

A Study of Reproduction in Generational and Steady-State Genetic Algorithms

G Syswerda — 2008-04-22T20:25:01-00:00

Foundations of Genetic Algorithms (1991)

Generation gaps revisited

Kenneth De Jong — 2008-04-22T20:22:34-00:00

Foundations of Genetic Algorithms, Vol. 2 (1993), pp. 19-28.

Approximation to Bayes risk in repeated plays

James Hannan — 2008-04-17T22:15:41-00:00

Contributions to the Theory of Games, Vol. 3 (1957), pp. 97-139.

A new approach to linear filtering and prediction problems

Rudolf Kalman — 2008-04-16T01:26:04-00:00

Journal of Basic Engineering, Vol. 82, No. 1. (1960), pp. 35-45.

Intelligence without representation

Rodney Brooks — 2008-03-20T23:15:04-00:00

Artificial Intelligence, Vol. 47 (1991), pp. 139-159.

From External to Internal Regret

Avrim Blum — 2008-03-19T15:55:56-00:00

The Journal of Machine Learning Research, Vol. 8 (2007), pp. 1307-1324.

An Approach to Bounded Rationality

Eli Ben-Sasson — 2008-03-19T15:37:34-00:00

(2007)

Using Confidence Bounds for Exploitation-Exploration Trade-offs

Peter Auer — 2008-03-19T14:44:35-00:00

The Journal of Machine Learning Research, Vol. 3 (2003), pp. 397-422.

The Multiplicative Weights Update Method: a Meta Algorithm and Applications

Sanjeev Arora — 2008-03-18T21:37:50-00:00

(2005)

The Nonstochastic Multiarmed Bandit Problem

Peter Auer — 2008-03-17T16:33:15-00:00

SIAM Journal on Computing, Vol. 32, No. 1. (2002), pp. 48-77.

Using upper confidence bounds for online learning

Peter Auer — 2008-03-14T03:10:50-00:00

Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on (2000), pp. 270-279.

We show how a standard tool from statistics, namely confidence bounds, can be used to elegantly deal with situations which exhibit an exploitation/exploration trade-off. Our technique for designing and analyzing algorithms for such situations is very general and can be applied when an algorithm has to make exploitation-versus-exploration decisions based on uncertain information provided by a random process. We consider two models with such an exploitation/exploration trade-off. For the adversarial bandit problem our new algorithm suffers only O˜(T1/2) regret over T trials which improves significantly over the previously best O˜(T2/3) regret. We also extend our results for the adversarial bandit problem to shifting bandits. The second model we consider is associative reinforcement learning with linear value functions. For this model our technique improves the regret from O˜(T3/4) to O˜(T1/2)

Robbing the bandit: less regret in online geometric optimization against an adaptive adversary

Varsha Dani — 2008-02-07T14:23:47-00:00

(2006), pp. 937-943.

How to Beat the Adaptive Multi-Armed Bandit

Varsha Dani — 2008-03-14T03:02:13-00:00

Arxiv preprint cs.DS/0602053 (2006)

On Following the Perturbed Leader in the Bandit Setting

Jussi Kujala — 2008-03-13T16:07:48-00:00

Algorithmic Learning Theory (2005), pp. 371-385.

In an online decision problem an algorithm is at each time step required to choose one of the feasible points without knowing the cost associated with it. An adversary assigns the cost to possible decisions either obliviously or adaptively. The online algorithm, naturally, attempts to collect as little cost as possible. The cost difference of the online algorithm and the best static decision in hindsight is called the regret of the algorithm. Kalai and Vempala [1] showed that it is possible to have efficient solutions to some problems with a linear cost function by following the perturbed leader. Their solution requires the costs of all decisions to be known.Recently there has also been some progress in the bandit setting, where only the cost of the selected decision is observed. A bound of O( T 2/3) on T rounds was first shown by Awerbuch and Kleinberg [2] for the regret against an oblivious adversary and later McMahan and Blum [3] showed that a bound of is obtainable against an adaptive adversary. In this paper we study Kalai and Vempala’s model from the viewpoint of bandit algorithms. We show that the algorithm of McMahan and Blum attains a regret of O( T 2/3) against an oblivious adversary. Moreover, we show a tighter bound for the expert setting using m experts.

Adaptive Treatment Allocation and the Multi-Armed Bandit Problem

Tze Lai — 2008-03-12T17:33:16-00:00

The Annals of Statistics, Vol. 15, No. 3. (1987), pp. 1091-1114.

Finite-time Analysis of the Multiarmed Bandit Problem

Peter Auer — 2008-03-12T17:29:41-00:00

Machine Learning, Vol. 47, No. 2. (1 May 2002), pp. 235-256.

Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.

An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem

Matthew Streeter — 2008-03-12T16:13:36-00:00

(2006)

A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem

Matthew Streeter — 2008-03-12T15:57:20-00:00

Principles and Practice of Constraint Programming - CP 2006 (2006), pp. 560-574.

The max k-armed bandit problem is a recently-introduced online optimization problem with practical applications to heuristic search. Given a set of k slot machines, each yielding payoff from a fixed (but unknown) distribution, we wish to allocate trials to the machines so as to maximize the maximum payoff received over a series of n trials. Previous work on the max k-armed bandit problem has assumed that payoffs are drawn from generalized extreme value (GEV) distributions. In this paper we present a simple algorithm, based on an algorithm for the classical k-armed bandit problem, that solves the max k-armed bandit problem effectively without making strong distributional assumptions. We demonstrate the effectiveness of our approach by applying it to the task of selecting among priority dispatching rules for the resource-constrained project scheduling problem with maximal time lags (RCPSP/max).

The Max K-Armed Bandit: A New Model for Exploration Applied to Search Heuristic Selection

Vincent Cicirello — 2008-03-12T15:53:02-00:00

(2005)

Efficient Algorithms for Universal Portfolios

Adam Kalai — 2008-03-12T00:30:12-00:00

Journal of Machine Learning Research, Vol. 3, No. 3. (April 2003), pp. 423-441.

A constant rebalanced portfolio is an investment strategy that keeps the same distribution of wealth among a set of stocks from day to day. There has been much work on Cover's Universal algorithm, which is competitive with the best constant rebalanced portfolio determined in hindsight (Cover, 1991, Helmbold et al, 1998, Blum and Kalal, 1999, Foster and Vohra, 1999, Vovk, 1998, Cover and Ordentlich, 1996a, Cover, 1996c). While this algorithm has good performance guarantees, all known implementations are exponential in the number of stocks, restricting the number of stocks used in experiments (Helmbold et al, 1998, Cover and Ordentlich, 1996a, Ordentlich and Cover, 1996b, Cover, 1996c, Blum and Kalai, 1999). We present an efficient implementation of the Universal algorithm that is based on non-uniform random walks that are rapidly mixing (Applegate and Kannan, 1991, Lovasz and Simonovits, 1992, Frieze and Kannan, 1999). This same implementation also works for non-financial applications

Multi-Armed Bandits in Metric Spaces

Robert Kleinberg — 2008-03-11T23:13:40-00:00

(May 2008)

Adaptive Routing with End-to-End Feedback: Distributed Learning and Geometric Approaches

Baruch Awerbuch — 2008-03-11T23:08:49-00:00

(2004), pp. 45-53.

Efficient algorithms for online decision problems

Adam Kalai — 2007-11-24T13:17:25-00:00

Journal of Computer and System Sciences, Vol. 71, No. 3. (October 2005), pp. 291-307.

Following the Perturbed Leader to Gamble at Multi-armed Bandits

Jussi Kujala — 2008-03-11T21:30:23-00:00

Algorithmic Learning Theory (2007), pp. 166-180.

Following the perturbed leader (fpl) is a powerful technique for solving online decision problems. Kalai and Vempala [1] rediscovered this algorithm recently. A traditional model for online decision problems is the multi-armed bandit. In it a gambler has to choose at each round one of the k levers to pull with the intention to minimize the cumulated cost. There are four versions of the nonstochastic optimization setting out of which the most demanding one is a game played against an adaptive adversary in the bandit setting. An adaptive adversary may alter its game strategy of assigning costs to decisions depending on the decisions chosen by the gambler in the past. In the bandit setting the gambler only gets to know the cost of the choice he made, rather than the costs of all available alternatives. In this work we show that the very straightforward and easy to implement algorithm Adaptive Bandit fpl can attain a regret of against an adaptive adversary. This regret holds with respect to the best lever in hindsight and matches the previous best regret bounds of .

A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

Yoav Freund — 2008-03-11T16:03:16-00:00

Journal of Computer and System Sciences, Vol. 55, No. 1. (1997), pp. 119-139.

The Weighted Majority Algorithm

Nick Littlestone — 2007-06-05T18:23:57-00:00

30th Annual Symposium on Foundations of Computer Science (1989), pp. 256-261.

The construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes is studied. It is assumed that the learner has reason to believe that one of some pool of known algorithms will perform well but does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. It is called the weighted majority algorithm and is shown to be robust with respect to errors in the data. Various versions of the weighted majority algorithm are discussed, and error bounds for them that are closely related to the error bounds of the best algorithms of the pool are proved

Tracking the Best Expert

Mark Herbster — 2008-03-09T23:01:20-00:00

Machine Learning, Vol. 32, No. 2. (1998), pp. 151-178.

We generalize the recent relative loss bounds for on-line algorithms where the additional loss of the algorithm on the whole sequence of examples over the loss of the best expert is bounded. The generalization allows the sequence to be partitioned into segments, and the goal is to bound the additional loss of the algorithm over the sum of the losses of the best experts for each segment. This is to model situations in which the examples change and different experts are best for certain segments of the sequence of examples. In the single segment case, the additional loss is proportional to log n, where n is the number of experts and the constant of proportionality depends on the loss function. Our algorithms do not produce the best partition; however the loss bound shows that our predictions are close to those of the best partition. When the number of segments is k+1 and the sequence is of length &ell, we can bound the additional loss of our algorithm over the best partition by . For the case when the loss per trial is bounded by one, we obtain an algorithm whose additional loss over the loss of the best partition is independent of the length of the sequence. The additional loss becomes , where L is the loss of the best partitionwith k+1 segments. Our algorithms for tracking the predictions of the best expert aresimple adaptations of Vovk's original algorithm for the single best expert case. As in the original algorithms, we keep one weight per expert, and spend O(1) time per weight in each trial.

Asymptotically efficient adaptive allocation rules

Tze Lai — 2008-03-09T22:29:31-00:00

Advances in Applied Mathematics, Vol. 6, No. 1. (1985), pp. 4-22.

Online computation and competitive analysis

Allan Borodin — 2008-03-09T20:03:44-00:00

(1998)

On-line Learning and the Metrical Task System Problem

Avrim Blum — 2008-03-09T20:00:51-00:00

Machine Learning, Vol. 39, No. 1. (1 April 2000), pp. 35-58.

The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include:

On-line choice of on-line algorithms

Yossi Azar — 2008-03-09T19:51:21-00:00

(1993), pp. 432-440.

Minimizing Regret with Label Efficient Prediction

Nicolò Cesa-Bianchi — 2008-03-08T22:05:54-00:00

Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004: Proceedings (2004)

Gambling in a rigged casino: the adversarial multi-armed bandit problem

Peter Auer — 2006-10-07T12:07:39-00:00

(1995), pp. 322-331.

In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to find the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the...

Master Algorithms for Active Experts Problems based on Increasing Loss Values

Jan Poland — 2008-03-08T21:27:17-00:00

Arxiv preprint cs.LG/0502067 (2005)

The best expert versus the smartest algorithm

Peter Chen — 2008-03-07T00:38:43-00:00

Theoretical Computer Science, Vol. 324, No. 2-3. (20 September 2004), pp. 361-380.

In this paper, we consider the problem of online prediction using expert advice. Under different assumptions, we give tight lower bounds on the gap between the best expert and any online algorithm that solves the problem.

On the Mathematical Foundations of Learning

Felipe Cucker — 2008-03-05T16:15:29-00:00

Bulletin of the American Mathematical Society, Vol. 39, No. 1. (2002), pp. 1-49.

Search Space Features Underlying the Performance of Stochastic Local Search Algorithms for MAX-SAT

Holger Hoos — 2008-03-05T00:15:09-00:00

Parallel Problem Solving from Nature - PPSN VIII (2004), pp. 51-60.

MAX-SAT is a well-known optimisation problem that can be seen as a generalisation of the propositional satisfiability problem. In this study, we investigate how the performance of stochastic local search (SLS) algorithms – a large and prominent class of algorithms that includes, for example, Tabu Search, Evolutionary Algorithms and Simulated Annealing – depends on features of the underlying search space. We show that two well-known measures of search space structure, the autocorrelation length of random walks and the so-called fitness distance correlation, reflect complementary factors underlying instance hardness for high-performance SLS algorithms. While the autocorrelation measure is computationally cheap, the fitness distance correlation serves mainly as an a posteriori measure for explaining performance. We also study the dependence of SLS performance on features of the distribution of clause weights for individual instances and show that, depending on the variance of the clause weight distribution, different search strategies seem to be suited best for dealing with the structure of the respective search spaces.

Correlated and uncorrelated fitness landscapes and how to tell the difference

Edward Weinberger — 2008-03-05T00:13:50-00:00

Biological Cybernetics, Vol. 63, No. 5. (1990), pp. 325-336.

The properties of multi-peaked “fitness landscapes” have attracted attention in a wide variety of fields, including evolutionary biology. However, relaively little attention has been paid to the properties of the landscapes themselves. Herein, we suggest a framework for the mathematical treatment of such landscapes, including an explicit mathematical model. A central role in this discussion is played by the autocorrelation of fitnesses obtained from a random walk on the landscape. Our ideas about average autocorrelations allow us to formulate a condition (satisfied by a wide class of landscapes we call AR(1) landscapes) under which the average autocorrelation approximates a decaying exponential. We then show how our mathematical model can be used to estimate both the globally optimal fitnesses of AR(1) landscapes and their local structure. We illustrate some aspects of our method with computer experiments based on a single family of landscapes (Kauffman's “N-k model”), that is shown to be a generic AR(1) landscape. We close by discussing how these ideas might be useful in the “tuning” of combinatorial optimization algorithms, and in modelling in the experimental sciences.

NK fitness landscapes

Lee Altenberg — 2008-03-04T23:41:51-00:00

Handbook of Evolutionary Computation, Vol. 2 (1997)