There are many practical applications in which the ability to localize devices such as phones, tablets, and mobile equipment is important. One of the issues which makes this difficult is the fact that devices are all different, so an approach which is robust against device heterogeneity would be an advance. In this paper, a method for estimating the positions of transmitting devices using Wi-Fi and a network of access points (APs) is proposed and investigated. The APs can also function as transmitters; as such the method allows simultaneous calibration and localization, so no fingerprinting or separate calibration is required. A hierarchical Bayesian probabilistic model is used with separate but conditionally-related parameters for each transmitter and receiver to tackle the device inhomogeneity problem. The output is a probability distribution over the location of each device from which the expected location and measures of uncertainty in location can be obtained. The system was implemented in an office environment using heterogeneous transmitters and receivers. The system localized the devices with a median error of 1.7 meters and within 4.32 meters with 95% confidence. We discovered that it is more important to account for inhomogeneity in the transmitters than in the receivers. Removing the former from the model results in a median error of 6.57 m(10.56 m) whereas removing the latter results in a median error 1.93 m(4.64 m), We argue that the technique could be used to cope with other types of inhomogeneities in the environments or the Wi-Fi equipment.

We consider the problem of learning an effective strategy online in a hidden information game against an opponent with a changing strategy. We want to model and exploit the opponent and make three proposals to do this; first, to infer its hidden information using an expectation-maximization (EM) algorithm; second, to predict its actions using a sequence prediction method; and third, to simulate games between our agent and our opponent model in-between games against the opponent. Our approach does not require knowledge outside the rules of the game, and does not assume that the opponent's strategy is stationary. Experiments in simplified poker games show that it increases the average payoff per game of a state-of-the-art no-regret learning algorithm.

Simultaneously co-adapting agents in an uncooperative setting can result in a non-stationary environment where optimisation or learning is difficult and where the agents' strategies may not converge to solutions. This work looks at simple simultaneous-move games with two or three actions and two or three players. Fictitious play is an old but popular algorithm that can converge to solutions, albeit slowly, in self-play in games like these. It models its opponents assuming that they use stationary strategies and plays a best-response strategy to these models. We propose two new variants of fictitious play that remove this assumption and explicitly assume that the opponents use dynamic strategies. The opponent's strategy is predicted using a sequence prediction method in the first variant and a change detection method in the second variant. Empirical results show that our variants converge faster than fictitious play. However, they do not always converge exactly to correct solutions. For change detection, this is a very small number of cases, but for sequence prediction there are many. The convergence of sequence prediction is improved by combining it with fictitious play. Also, unlike in fictitious play, our variants converge to solutions in the difficult Shapley's and Jordan's games.

This paper analyses a generational evolutionary algorithm using only selection and uniform crossover. With a probability arbitrarily close to one the evolutionary algorithm is shown to solve onemax in O(n log2(n)) function evaluations using a population of size c,n, log(n). We then show that this algorithm can solve onemax with noise variance n again in O(n log2(n)) function evaluations.

Thompson Sampling has recently been shown to achieve the lower bound on regret in the Bernoulli Multi-Armed Bandit setting. This bandit problem assumes stationary distributions for the rewards. It is often unrealistic to model the real world as a stationary distribution. In this paper we derive and evaluate algorithms using Thompson Sampling for a Switching Multi-Armed Bandit Problem. We propose a Thompson Sampling strategy equipped with a Bayesian change point mechanism to tackle this problem. We develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (Per-Arm Switching), when the switching rate is known and when it must be inferred from data. This leads to a family of algorithms we collectively term Change-Point Thompson Sampling (CTS). We show empirical results in 4 artificial environments, and 2 derived from real world data: news click-through and foreign exchange data, comparing them to some other bandit algorithms. In real world data CTS is the most effective.

Estimation of distribution algorithms replace the typical crossover and mutation operators by constructing a probabilistic model and generating offspring according to this model. In previous studies, it has been shown that this generally leads to diversity loss due to sampling errors. In this paper, for the case of the simple Univariate Marginal Distribution Algorithm (UMDA), we propose and test several methods for counteracting diversity loss. The diversity loss can come in two phases: sampling from the probability model (offspring generation) and selection. We show that it is possible to completely remove the sampling error during offspring generation. Furthermore, we examine several plausible model construction variants which counteract diversity loss during selection and demonstrate that these update rules work better than the standard update on a variety of simple test problems.

In this paper, a cross-validation and early-stopping algorithm is devised for parameter updating in the Univariate Marginal Distribution Algorithm (UMDA) to reduce overftting. Our hypothesis is that the well-known problem of diversity loss in UMDA is a consequence of overfitting during the parameter estimation step at each generation. It is tested by experiments on two different optimization problems.

A variant of a sparse distributed memory (SDM) is shown to have the capability of storing and recalling patterns containing rank-order information. These are patterns where information is encoded not only in the subset of neuron outputs that fire, but also in the order in which that subset fires. This is an interesting companion to several recent works in the neuroscience literature, showing that human memories may be stored in terms of neural spike timings. In our model, the ordering is stored in static synaptic weights using a Hebbian single-shot learning algorithm, and can be reliably recovered whenever the associated input is supplied. It is shown that the memory can operate using only unipolar binary connections throughout. The behavior of the memory under noisy input conditions is also investigated. It is shown that the memory is capable of improving the quality of the data that passes through it. That is, under appropriate conditions the output retrieved from the memory is less noisy than the input used to retrieve it. Thus, this memory architecture could be used as a component in a complex system with stable noise properties and, we argue, it can be implemented using spiking neurons.

There have been major advances in programming languages over the last 20 years. Given this, it seems appropriate to ask why systems programmers continue to largely ignore these languages. What are the deficiencies in the eyes of the systems programmers? How have the efforts of the programming language community been misdirected (from their perspective)? What can/should the PL community do address this?As someone whose research straddles these areas, I was asked to give a talk at this year's PLOS workshop. What follows are my thoughts on this subject, which may or not represent those of other systems programmers.

Estimation of Distribution Algorithms (EDAs) are a class of evolutionary algorithms that use machine learning techniques to solve optimization problems. Machine learning is used to learn probabilistic models of the selected population. This model is then used to generate next population via sampling. An important phenomenon in machine learning from data is called overfitting. This occurs when the model is overly adapted to the specifics of the training data so well that even noise is encoded. The purpose of this paper is to investigate whether overfitting happens in EDAs, and to discover its consequences. What is found is: overfitting does occur in EDAs; overfitting correlates to EDAs performance; reduction of overfitting using early stopping can improve EDAs performance. Categories and Subject Descriptors

This paper presents the design of an associative memory with feedback that is capable of on-line temporal sequence learning. A framework for on-line sequence learning has been proposed, and different sequence learning models have been analysed according to this framework. The network model is an associative memory with a separate store for the sequence context of a symbol. A sparse distributed memory is used to gain scalability. The context store combines the functionality of a neural layer with a shift register. The sensitivity of the machine to the sequence context is controllable, resulting in different characteristic behaviours. The model can store and predict on-line sequences of various types and length. Numerical simulations on the model have been carried out to determine its properties.

This paper considers a phenomenon in Estimation of Distribution Algorithms (EDA) analogous to drift in population genetic dynamics. Finite population sampling in selection results in fluctuations which get reinforced when the probability model is updated. As a consequence, any probability model which can generate only a single set of values with probability 1 can be an attractive fixed point of the algorithm. To avoid this, parameters of the algorithm must scale with the system size in strongly problem-dependent ways, or the algorithm must be modified. This phenomenon is shown to hold for general EDAs as a consequence of the lack of ergodicity and irreducibility of the Markov chain on the state of probability models. It is illustrated in the case of UMDA, in which it is shown that the global optimum is only found if the population size is sufficiently large. For the needle-in-a haystack problem, the population size must scale as the square-root of the size of the search space. For the one-max problem, the population size must scale as the square-root of the problem size.

Population-based Incremental Learning is shown require very sen(cid:173) sitive scaling of its learning rate. The learning rate must scale with the system size in a problem-dependent way. This is shown in two problems: the needle-in-a haystack, in which the learning rate must vanish exponentially in the system size, and in a smooth function in which the learning rate must vanish like the square root of the system size. Two methods are proposed for removing this sensitiv(cid:173) ity. A learning dynamics which obeys detailed balance is shown to give consistent performance over the entire range of learning rates. An analog of mutation is shown to require a learning rate which scales as the inverse system size, but is problem independent.

Animal data on delayed-reward conditioning experiments shows a striking property - the data for different time intervals collapses into a single curve when the data is scaled by the time interval. This is called the scalar property of interval timing. Here a simple model of a neural clock is presented and shown to give rise to the scalar property. The model is an accumulator consisting of noisy, linear spiking neurons. It is analytically tractable and contains only three parameters. When coupled with reinforcement learning it simulates peak procedure experiments, producing both the scalar property and the pattern of single trial covariances.

Mobile robots require the ability to build their own maps to operate in unknown environments. A fundamental problem is that odometry-based dead reckoning cannot be used to assign accurate global position information to a map because of drift errors caused by wheel slippage. The paper introduces a fast, online method of learning globally consistent maps, using only local metric information. The approach differs from previous work in that it is computationally cheap, easy to implement and is guaranteed to find a globally optimal solution. Experiments are presented in which large, complex environments were successfully mapped by a real robot, and quantitative performance measures are used to assess the quality of the maps obtained.