Designers of mobile, social systems must carefully think about how to help their users manage spatial, semantic, and social modes of navigation. Here, we describe our deployment of MobiTags, a system to help museum visitors interact with a collection of "open storage" exhibits, those where the museum provides little curatorial information. MobiTags integrates social tagging, art information, and a map to support navigation and collaborative curation of these open storage collections. We studied 23 people's use of MobiTags in a local museum, combining interview data with device use logs and tracking of people's movements to understand how MobiTags affected their navigation and experience in the museum. Despite a lack of social cues, people feel a strong sense of social presence--and social pressure--through seeing others' tags. The tight coupling of tags, item information, and map features also supported a rich set of practices around these modes of navigation.

Technologies in museums often support learning goals, providing information about exhibits. However, museum visitors also desire meaningful experiences and enjoy the social aspects of museum-going, values ignored by most museum technologies. We present ArtLinks, a visualization with three goals: helping visitors make connections to exhibits and other visitors by highlighting those visitors who share their thoughts; encouraging visitors' reflection on the social and liminal aspects of museum-going and their expectations of technology in museums; and doing this with transparency, aligning aesthetically pleasing elements of the design with the goals of connection and reflection. Deploying ArtLinks revealed that people have strong expectations of technology as an information appliance. Despite these expectations, people valued connections to other people, both for their own sake and as a way to support meaningful experience. We also found several of our design choices in the name of transparency led to unforeseen tradeoffs between the social and the liminal.

We consider the use of two additive control variate methods to reduce the variance of performance gradient estimates in reinforcement learn- ing problems. The first approach we consider is the baseline method, in which a function of the current state is added to the discounted value estimate. We relate the performance of these methods, which use sam- ple paths, to the variance of estimates based on iid data. We derive the baseline function that minimizes this variance, and we show that the vari- ance for any baseline is the sum of the optimal variance and a weighted squared distance to the optimal baseline. We show that the widely used average discounted value baseline (where the reward is replaced by the difference between the reward and its expectation) is suboptimal. The second approach we consider is the actor-critic method, which uses an approximate value function. We give bounds on the expected squared error of its estimates. We show that minimizing distance to the true value function is suboptimal in general; we provide an example for which the true value function gives an estimate with positive variance, but the op- timal value function gives an unbiased estimate with zero variance. Our bounds suggest algorithms to estimate the gradient of the performance of parameterized baseline or value functions. We present preliminary exper- iments that illustrate the performance improvements on a simple control problem. 1 Introduction, Background, and Preliminary Results In reinforcement learning problems, the aim is to select a controller that will maximize the average reward in some environment. We model the environment as a partially ob- servable Markov decision process (POMDP). Gradient ascent methods (e.g., [7, 12, 15]) estimate the gradient of the average reward, usually using Monte Carlo techniques to cal- (cid:3)Most of this work was performed while the authors were with the Research School of Information Sciences and Engineering at the Australian National University. culate an average over a sample path of the controlled POMDP. However such estimates tend to have a high variance, which means many steps are needed to obtain a good esti- mate. GPOMDP [4] is an algorithm for generating an estimate of the gradient in this way. Compared with other approaches, it is suitable for large systems, when the time between visits to a state is large but the mixing time of the controlled POMDP is short. However, it can suffer from the problem of producing high variance estimates. In this paper, we investi- gate techniques for variance reduction in GPOMDP. One generic approach to reducing the variance of Monte Carlo estimates of integrals is to use an additive control variate (see, for example, [6]). Suppose we wish to estimate the integral of f : X ! R, and we know the integral of another function ’ : X ! R. Since RX f = RX (f (cid:0) ’) +RX ’, the integral of f (cid:0) ’ can be estimated instead. Obviously if ’ = f then the variance is zero. More generally, Var(f (cid:0) ’) = Var(f ) (cid:0) 2Cov(f; ’) + Var(’), so that if (cid:30) and f are strongly correlated, the variance of the estimate is reduced. In this paper, we consider two approaches of this form. The first (Section 2) is the technique of adding a baseline. We find the optimal baseline and we show that the additional variance of a suboptimal baseline can be expressed as a weighted squared distance from the optimal baseline. Constant baselines, which do not depend on the state or observations, have been widely used [13, 15, 9, 11]. In particular, the expectation over all states of the discounted value of the state is a popular constant baseline (where, for example, the reward at each step is replaced by the difference between the reward and the expected reward). We give bounds on the estimation variance that show that, perhaps surprisingly, this may not be the best choice. The second approach (Section 3) is the use of an approximate value function. Such actor- critic methods have been investigated extensively [3, 1, 14, 10]. Generally the idea is to minimize some notion of distance between the fixed value function and the true value function. In this paper we show that this may not be the best approach: selecting the fixed value function to be equal to the true value function is not always the best choice. Even more surprisingly, we give an example for which the use of a fixed value function that is different from the true value function reduces the variance to zero, for no increase in bias. We give a bound on the expected squared error (that is, including the estimation variance) of the gradient estimate produced with a fixed value function. Our results suggest new algorithms to learn the optimum baseline, and to learn a fixed value function that minimizes the bound on the error of the estimate. In Section 5, we describe the results of preliminary experiments, which show that these algorithms give performance improvements. POMDP with Reactive, Parameterized Policy A partially observable Markov decision process (POMDP) consists of a state space, S, a control space, U, an observation space, Y, a set of transition probability matrices fP(u) : u 2 Ug, each with components pij (u) for i; j 2 S; u 2 U, an observation pro- cess (cid:23) : S ! PY , where PY is the space of probability distributions over Y, and a reward function r : S ! R. We assume that S; U; Y are finite, although all our re- sults extend easily to infinite U and Y, and with more restrictive assumptions can be extended to infinite S. A reactive, parameterized policy for a POMDP is a set of map- pings f(cid:22)((cid:1); (cid:18)) : Y ! PU j(cid:18) 2 RKg. Together with the POMDP, this defines the con- trolled POMDP (S; U; Y; P ; (cid:23); r; (cid:22)). The joint state, observation and control process, fXt; Yt; Utg, is Markov. The state process, fXtg, is also Markov, with transition prob- abilities pij ((cid:18)) = Py2Y;u2U (cid:23)y(i)(cid:22)u(y; (cid:18))pij (u), where (cid:23)y(i) denotes the probability of observation y given the state i, and (cid:22)u(y; (cid:18)) denotes the probability of action u given pa- rameters (cid:18) and observation y. The Markov chain M((cid:18)) = (S; P((cid:18))) then describes the behaviour of the process fXtg. Assumption 1 The controlled POMDP (S; U; Y; P ; (cid:23); r; (cid:22)) satisfies: For all (cid:18) 2 RK there exists a unique stationary distribution satisfying (cid:25) 0((cid:18)) P((cid:18)) = (cid:25)0((cid:18)). There is an R < 1 such that, for all i 2 S, jr(i)j (cid:20) R. There is a B < 1 such that, for all u 2 U, y 2 Y and (cid:18) 2 RK the deriva- tives @(cid:22)u(y; (cid:18))=@(cid:18)k (1 (cid:20) k (cid:20) K) exist, and the vector of these derivatives satisfies kr(cid:22)u(y; (cid:18))=(cid:22)u(y; (cid:18))k (cid:20) B, where k (cid:1) k denotes the Euclidean norm on RK. implies that this limit exists, and does not depend on the start state X0. The aim is to select a policy to maximize this quantity. Define the discounted value function, J(cid:12)(i; (cid:18)) def= We consider the average reward, (cid:17)((cid:18)) def= limT !1 Eh 1 t=0 r(Xt)i. Assumption 1 X0 = i i. Throughout the rest of the paper, dependences limT !1 EhPT (cid:0)1 Var(A) = Eh(A (cid:0) E [A])2i, where a2 denotes a0a, and a0 denotes the transpose of the upon (cid:18) are assumed, and dropped in the notation. For a random vector A, we denote t=0 (cid:12)tr(Xt)(cid:12)(cid:12)(cid:12)

Abstract Generalized matrix–matrix multiplication forms the kernel of many mathematical algorithms, hence a faster matrix–matrix multiply immediately benefits these algorithms. In this paper we implement efficient matrix multiplication for large matrices using the Intel Pentium single instruction multiple data (SIMD) floating point architecture. The main difficulty with the Pentium and other commodity processors is the need to efficiently utilize the cache hierarchy, particularly given the growing gap between main‐memory and CPU clock speeds. We give a detailed description of the register allocation, Level 1 and Level 2 cache blocking strategies that yield the best performance for the Pentium III family. Our results demonstrate an average performance of 2.09 times faster than the leading public domain matrix–matrix multiply routines and comparable performance with Intel's SIMD small matrix–matrix multiply routines. Copyright © 2001 John Wiley & Sons, Ltd.

Gradient-based approaches to direct policy search in reinforcement learning have received much recent attention as a means to solve problems of partial observability and to avoid some of the problems associated with policy degradation in value-function methods. In this paper we introduce GPOMDP, a simulation-based algorithm for generating a biased estimate of the gradient of the average reward in Partially Observable Markov Decision Processes POMDPs controlled by parameterized stochastic policies. A similar algorithm was proposed by (Kimura et al. 1995). The algorithm's chief advantages are that it requires storage of only twice the number of policy parameters, uses one free beta (which has a natural interpretation in terms of bias-variance trade-off), and requires no knowledge of the underlying state. We prove convergence of GPOMDP, and show how the correct choice of the parameter beta is related to the mixing time of the controlled POMDP. We briefly describe extensions of GPOMDP to controlled Markov chains, continuous state, observation and control spaces, multiple-agents, higher-order derivatives, and a version for training stochastic policies with internal states. In a companion paper (Baxter et al., this volume) we show how the gradient estimates generated by GPOMDP can be used in both a traditional stochastic gradient algorithm and a conjugate-gradient procedure to find local optima of the average reward.

In this paper, we present algorithms that perform gradient ascent of the average reward in a partially observable Markov decision process (POMDP). These algorithms are based on GPOMDP, an algorithm introduced in a companion paper (Baxter & Bartlett, this volume), which computes biased estimates of the performance gradient in POMDPs. The algorithm's chief advantages are that it uses only one free parameter beta, which has a natural interpretation in terms of bias-variance trade-off, it requires no knowledge of the underlying state, and it can be applied to infinite state, control and observation spaces. We show how the gradient estimates produced by GPOMDP can be used to perform gradient ascent, both with a traditional stochastic-gradient algorithm, and with an algorithm based on conjugate-gradients that utilizes gradient information to bracket maxima in line searches. Experimental results are presented illustrating both the theoretical results of (Baxter & Bartlett, this volume) on a toy problem, and practical aspects of the algorithms on a number of more realistic problems.

Generalised matrix-matrix multiplication forms the kernel of many mathematical algorithms. A faster matrix-matrix multiply immediately benefits these algorithms. In this paper we implement efficient matrix multiplication for large matrices using the floating point Intel SIMD (Single Instruction Multiple Data) architecture. A description of the issues and our solution is presented, paying attention to all levels of the memory hierarchy. Our results demonstrate an average performance of 2.09 times faster than the leading public domain matrix-matrix multiply routines.

Many control, scheduling, planning and game-playing tasks can be formulated as reinforcement learning problems, in which an agent chooses actions to take in some environment, aiming to maximize a reward function. We present an algorithm for computing approximations to the gradient of the average reward from a single sample path of a controlled partially observable Markov decision process. We show that the accuracy of these approximations depends on the relationship between a time constant used by the algorithm and the mixing time of the Markov chain, and that the error can be made arbitrarily small by setting the time constant suitably large. We prove that the algorithm converges with probability 1.

Artificial neural networks with millions of adjustable parameters and a similar number of training examples are a potential solution for difficult, large-scale pattern recognition problems in areas such as speech and face recognition, classification of large volumes of web data, and finance. The bottleneck is that neural network training involves iterative gradient descent and is extremely computationally intensive. In this paper we present a technique for distributed training of Ultra Large Scale Neural Networks 1 (ULSNN) on Bunyip, a Linux-based cluster of 196 Pentium III processors. To illustrate ULSNN training we describe an experiment in which a neural network with 1.73 million adjustable parameters was trained to recognize machine-printed Japanese characters from a database containing 9 million training patterns. The training runs with a average performance of 163.3 GFlops/s (single precision). With a machine cost of $150,913, this yields a price/performance ratio of 92.4¢ /MFlops/s (single precision). For comparison purposes, training using double precision and the ATLAS DGEMM produces a sustained performance of 70 MFlops/s or $2.16 / MFlop/s (double precision).

A major problem in machine learning is that of inductive bias: how to choose a learner's hypothesis space so that it is large enough to contain a solution to the problem being learnt, yet small enough to ensure reliable generalization from reasonably-sized training sets. Typically such bias is supplied by hand through the skill and insights of experts. In this paper a model for automatically learning bias is investigated. The central assumption of the model is that the learner is embedded within an environment of related learning tasks. Within such an environment the learner can sample from multiple tasks, and hence it can search for a hypothesis space that contains good solutions to many of the problems in the environment. Under certain restrictions on the set of all hypothesis spaces available to the learner, we show that a hypothesis space that performs well on a sufficiently large number of training tasks will also perform well when learning novel tasks in the same environment. Explicit bounds are also derived demonstrating that learning multiple tasks within an environment of related tasks can potentially give much better generalization than learning a single task.

In this paper we present TDLEAF(λ), a variation on the TD(λ) algorithm that enables it to be used in conjunction with game-tree search. We present some experiments in which our chess program “KnightCap” used TDLEAF(λ) to learn its evaluation function while playing on Internet chess servers. The main success we report is that KnightCap improved from a 1650 rating to a 2150 rating in just 308 games and 3 days of play. As a reference, a rating of 1650 corresponds to about level B human play (on a scale from E (1000) to A (1800)), while 2150 is human master level. We discuss some of the reasons for this success, principle among them being the use of on-line, rather than self-play. We also investigate whether TDLEAF(λ) can yield better results in the domain of backgammon, where TD(λ) has previously yielded striking success.

In this paper the problem of learning appropriate bias for an environment of related tasks is examined from a Bayesian perspective. The environment of related tasks is shown to be naturally modelled by the concept of an {\em objective} prior distribution. Sampling from the objective prior corresponds to sampling different learning tasks from the environment. It is argued that for many common machine learning problems, although we don't know the true (objective) prior for the problem, we do have some idea of a set of possible priors to which the true prior belongs. It is shown that under these circumstances a learner can use Bayesian inference to learn the true prior by sampling from the objective prior. Bounds are given on the amount of information required to learn a task when it is simultaneously learnt with several other tasks. The bounds show that if the learner has little knowledge of the true prior, and the dimensionality of the true prior is small, then sampling multiple tasks is highly advantageous.

Abstract only given. We present an adaptive coding technique which is shown to achieve optimal coding in the limit as the size of the text grows, while the data structures associated with the code only grow linearly with the text. The approach relies on Huffman codes which are generated relative to the context in which a particular character occurs. The Huffman codes themselves are inferred from the data that has already been seen. A key part of the paper involves showing that the loss per character incurred by the learning process tends to zero as the size of the text tends to infinity. This involves an analysis in an on-line learning framework bounding the cumulative loss, where loss is defined to be the excess code length. By using the Bayes prediction distribution and code the expected loss per character converges to zero at the best possible rate of O(log n/n). By allowing the length of contexts to grow in response to commonly occurring subsequences, the coding is efficient precisely where it needs to be, hence achieving a high compression rate at a relatively low overhead in terms of data structure storage.

Probablythe most important, problem in maperiment, provides strong qualitative support for the theoretical results.