Author name cluster

Andrew W. Moore

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

IJCAI Conference 2011 Conference Paper

Theoretical Justification of Popular Link Prediction Heuristics

Purnamrita Sarkar
Deepayan Chakrabarti
Andrew W. Moore

There are common intuitions about how social graphs are generated (for example, it is common to talk informally about nearby nodes sharing a link). There are also common heuristics for predicting whether two currently unlinked nodes in a graph should be linked (e. g. for suggesting friends in an online social network or movies to customers in a recommendation network). This paper provides what we believe to be the first formal connection between these intuitions and these heuristics. We look at a familiar class of graph generation models in which nodes are associated with locations in a latent metric space and connections are more likely between closer nodes. We also look at popular linkprediction heuristics such as number-of-commonneighbors and its weighted variants [Adamic and Adar, 2003] which have proved successful in predicting missing links, but are not direct derivatives of latent space graph models. We provide theoretical justifications for the success of some measures as compared to others, as reported in previous empirical studies. In particular we present a sequence of formal results that show bounds related to the role that a node's degree plays in its usefulness for link prediction, the relative importance of short paths versus long paths, and the effects of increasing non-determinism in the link generation process on link prediction quality. Our results can be generalized to any model as long as the latent space assumption holds.

PDF Details DOI

JMLR Journal 2008 Journal Article

Forecasting Web Page Views: Methods and Observations

Jia Li
Andrew W. Moore

Web sites must forecast Web page views in order to plan computer resource allocation and estimate upcoming revenue and advertising growth. In this paper, we focus on extracting trends and seasonal patterns from page view series, two dominant factors in the variation of such series. We investigate the Holt-Winters procedure and a state space model for making relatively short-term prediction. It is found that Web page views exhibit strong impulsive changes occasionally. The impulses cause large prediction errors long after their occurrences. A method is developed to identify impulses and to alleviate their damage on prediction. We also develop a long-range trend and season extraction method, namely the Elastic Smooth Season Fitting (ESSF) algorithm, to compute scalable and smooth yearly seasons. ESSF derives the yearly season by minimizing the residual sum of squares under smoothness regularization, a quadratic optimization problem. It is shown that for long-term prediction, ESSF improves accuracy significantly over other methods that ignore the yearly seasonality. [abs] [ pdf ][ bib ] &copy JMLR 2008. ( edit, beta )

PDF Details

JMLR Journal 2006 Journal Article

New Algorithms for Efficient High-Dimensional Nonparametric Classification

Ting Liu
Andrew W. Moore
Alexander Gray

This paper is about non-approximate acceleration of high-dimensional nonparametric operations such as k nearest neighbor classifiers. We attempt to exploit the fact that even if we want exact answers to nonparametric queries, we usually do not need to explicitly find the data points close to the query, but merely need to answer questions about the properties of that set of data points. This offers a small amount of computational leeway, and we investigate how much that leeway can be exploited. This is applicable to many algorithms in nonparametric statistics, memory-based learning and kernel-based learning. But for clarity, this paper concentrates on pure k -NN classification. We introduce new ball-tree algorithms that on real-world data sets give accelerations from 2-fold to 100-fold compared against highly optimized traditional ball-tree-based k -NN. These results include data sets with up to 10 6 dimensions and 10 5 records, and demonstrate non-trivial speed-ups while giving exact answers. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

PDF Details

JMLR Journal 2002 Journal Article

Policy Search using Paired Comparisons

Malcolm J. A. Strens
Andrew W. Moore

Direct policy search is a practical way to solve reinforcement learning (RL) problems involving continuous state and action spaces. The goal becomes finding policy parameters that maximize a noisy objective function. The Pegasus method converts this stochastic optimization problem into a deterministic one, by using fixed start states and fixed random number sequences for comparing policies (Ng and Jordan, 2000). We evaluate Pegasus, and new paired comparison methods, using the mountain car problem, and a difficult pursuer-evader problem. We conclude that: (i) paired tests can improve performance of optimization procedures; (ii) several methods are available to reduce the 'overfitting' effect found with Pegasus; (iii) adapting the number of trials used for each comparison yields faster learning; (iv) pairing also helps stochastic search methods such as differential evolution.

PDF Details

JMLR Journal 2000 Journal Article

Learning Evaluation Functions to Improve Optimization by Local Search

Justin Boyan
Andrew W. Moore

This paper describes algorithms that learn to improve search performance on large-scale optimization tasks. The main algorithm, STAGE, works by learning an evaluation function that predicts the outcome of a local search algorithm, such as hillclimbing or Walksat, from features of states visited during search. The learned evaluation function is then used to bias future search trajectories toward better optima on the same problem. Another algorithm, X-STAGE, transfers previously learned evaluation functions to new, similar optimization problems. Empirical results are provided on seven large-scale optimization domains: bin-packing, channel routing, Bayesian network structure-finding, radiotherapy treatment planning, cartogram design, Boolean satisfiability, and Boggle board setup.

PDF Details

IJCAI Conference 1999 Conference Paper

Multi-Value-Functions: Efficient Automatic Action Hierarchies for Multiple Goal MDPs

Andrew W. Moore
Leemon C Baird
Leslie Kaelbling

If you have planned to achieve one particular goal in a stochastic delayed rewards problem and then someone asks about a different goal what should you do? What if you need to be ready to quickly supply an answer for any possible goal? This paper shows that by using a new kind of automata caily generated abstract action hierarchy that with N states, preparing for all of N possible goals can be much much cheaper than N times the work of preparing for one goal. In goal-based Markov Decision Problems, it is usual to generate a policy mapping states to actions, and a value function mapping states to an estimate of minimum expected cost-to-goal, starting at In this paper we will use the terminology that a multi-policy (for all state-pairs maps a state to the first action it should take in order to reach with expected minimum cost and a multi-valuefunction is a definition of this minimum cost. Building these objects quickly and with lit tle memory is the main purpose of this paper, but a secondary result is a natural, automatic, way to create a set of parsimonious yet powerful abstractactions for MDPs. The paper concludes with a set of empirical results on increasingly large MDPs.

PDF