nils-herrmann/clean_scirepeval huggingface dataset:
Sparse Distributed Memories in Reinforcement Learning : Case Studies

In this paper, we advocate the use of Sparse Distributed Memories (SDMs) (Kanerva, 1993) for on-line, value-based reinforcement learning (RL). The SDMs model was originally designed for the case, where a very large input (address) space has to be mapped into a much smaller physical memory. SDMs provide a linear, local function approximation scheme, which is often preferred in RL. In our recent work (Ratitch & Precup 2004), we developed an algorithm for learning simultaneously the structure and the content of the memory online. In this paper, we investigate the empirical performance of the Sarsa algorithm using the SDM function approximator on three domains: the traditional Mountain-car task, a variant of a hunter-prey task and a motor-control problem called Swimmer (Coulom 2002). The second and third tasks are highly-dimensional and exhibit complex dynamics, yet our approach provides good solutions.
Using MDP Characteristics to Guide Exploration in Reinforcement Learning

We present a new approach for exploration in Reinforcement Learning (RL) based on certain properties of the Markov Decision Processes (MDP). Our strategy facilitates a more uniform visitation of the state space, a more extensive sampling of actions with potentially high variance of the action-value function estimates, and encourages the RL agent to focus on states where it has most control over the outcomes of its actions. Our exploration strategy can be used in combination with other existing exploration techniques, and we experimentally demonstrate that it can improve the performance of both undirected and directed exploration methods. In contrast to other directed methods, the exploration-relevant information can be precomputed beforehand and then used during learning without additional computation cost.
Combining TD-learning with Cascade-correlation Networks

Using neural networks to represent value functions in reinforcement learning algorithms often involves a lot of work in hand-crafting the network structure, and tuning the learning parameters. In this paper, we explore the potential of using constructive neural networks in reinforcement learning. Constructive neural network methods are appealing because they can build the network structure based on the data that needs to be represented. To our knowledge, such algorithms have not been used in reinforcement learning. A major issue is that constructive algorithms often work in batch mode, while many reinforcement learning algorithms work on-line. We use a cache to accumulate data, then use a variant of cascade correlation to update the value function. Preliminary results on the game of Tic-Tac-Toe show the potential of this new algorithm, compared to using static feed-forward neural networks trained with backpropagation.
A Planning Algorithm for Predictive State Representations

We address the problem of optimally controlling stochastic environments that are partially observable. The standard method for tackling such problems is to dene and solve a Partially Observable Markov Decision Process (POMDP). However, it is well known that exactly solving POMDPs is very costly computationally. Recently, Littman, Sutton and Singh (2002) have proposed an alternative representation of partially observable environments, called predictive state representations (PSRs). PSRs are grounded in the sequence of actions and observations of the agent, and hence relate the state representation directly to the agent’s experience. In this paper, we present a policy iteration algorithm for nding policies using PSRs. In preliminary experiments, our algorithm produced good solutions.
Learning Options in Reinforcement Learning

Temporally extended actions (e.g., macro actions) have proven very useful for speeding up learning, ensuring robustness and building prior knowledge into AI systems. The options framework (Precup, 2000; Sutton, Precup & Singh, 1999) provides a natural way of incorporating such actions into reinforcement learning systems, but leaves open the issue of howgood options might be identified. In this paper, we empirically explore a simple approach to creating options. The underlying assumption is that the agent will be asked to perform different goalachievement tasks in an environment that is otherwise the same over time. Our approach is based on the intuition that states that are frequently visited on system trajectories, could prove to be useful subgoals (e.g., McGovern & Barto, 2001; Iba, 1989).We propose a greedy algorithm for identifying subgoals based on state visitation counts. We present empirical studies of this approach in two gridworld navigation tasks. One of the environments we explored contains bottleneck states, and the algorithm indeed finds these states, as expected. The second environment is an empty gridworld with no obstacles. Although the environment does not contain any obvious subgoals, our approach still finds useful options, which essentially allow the agent to explore the environment more quickly.
Developing Collaborative Golog Agents by Reinforcement Learning

We consider applications where agents have to cooperate without any communication taking place between them, apart from the fact that they can see part of the environment in which they act. We present a multi-agent system, defined in Golog, that needs to service tasks whose value degrades in time. Initial plans, reflecting prior knowledge about the environment, are expressed as Golog procedures, and are provided to the agents. Then the agents are trained using reinforcement learning, in order to ensure coordination both at the action level and at the plan level. This ensures better scalability and increased performance of the system.
Combining and adapting software quality predictive models by genetic algorithms

The goal of quality models is to predict a quality factor starting from a set of direct measures. Selecting an appropriate quality model for a particular software is a difficult, non-trivial decision. In this paper, we propose an approach to combine and/or adapt existing models (experts) in such way that the combined/adapted model works well on the particular system. Test results indicate that the models perform significantly better than individual experts in the pool.
Characterizing Markov Decision Processes

Problem characteristics often have a significant influence on the difficulty of solving optimization problems. In this paper, we propose attributes for characterizing Markov Decision Processes (MDPs), and discuss how they affect the performance of reinforcement learning algorithms that use function approximation. The attributes measure mainly the amount of randomness in the environment. Their values can be calculated from the MDP model or estimated on-line. We show empirically that two of the proposed attributes have a statistically significant effect on the quality of learning. We discuss how measurements of the proposed MDP attributes can be used to facilitate the design of reinforcement learning systems.
A Convergent Form of Approximate Policy Iteration

We study a new, model-free form of approximate policy iteration which uses Sarsa updates with linear state-action value function approximation for policy evaluation, and a "policy improvement operator" to generate a new policy based on the learned state-action values. We prove that if the policy improvement operator produces e-soft policies and is Lipschitz continuous in the action values, with a constant that is not too large, then the approximate policy iteration algorithm converges to a unique solution from any initial policy. To our knowledge, this is the first convergence result for any form of approximate policy iteration under similar computational-resource assumptions.
Developing collaborative Golog agents by reinforcement learning

We consider applications where agents have to cooperate without any communication taking place between them, apart from the fact that they can see part of the environment in which they act. We present a multi-agent system, defined in Golog, that needs to service tasks whose value degrades in time. Initial plans, reflecting prior knowledge about the environment, are expressed as Golog procedures, and are provided to the agents. Then the agents are trained using reinforcement learning, in order to ensure coordination both at the action level and at the plan level. This ensures better scalability and increased performance of the system.
Algorithms for the multi-armed bandit problem

The stochastic multi-armed bandit problem is an important model for studying the explorationexploitation tradeo in reinforcement learning. Although many algorithms for the problem are well-understood theoretically, empirical conrmation of their eectiveness is generally scarce. This paper presents a thorough empirical study of the most popular multi-armed bandit algorithms. Three important observations can be made from our results. Firstly, simple heuristics such as -greedy and Boltzmann exploration outperform theoretically sound algorithms on most settings by a signicant margin. Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identies for each algorithm the settings where it performs well, and the settings where it performs poorly. These properties are not described by current theory, even though they can be exploited in practice in the design of heuristics. Thirdly, the algorithms’ performance relative each to other is aected only by the number of bandit arms and the variance of the rewards. This nding may guide the design of subsequent empirical evaluations. In the second part of the paper, we turn our attention to an important area of application of bandit algorithms: clinical trials. Although the design of clinical trials has been one of the principal practical problems motivating research on multi-armed bandits, bandit algorithms have never been evaluated as potential treatment allocation strategies. Using data from a real study, we simulate the outcome that a 2001-2002 clinical trial would have had if bandit algorithms had been used to allocate patients to treatments. We nd
Using Finite Experiments to Study Asymptotic Performance

In the analysis of algorithms we are interested in obtaining closed form expressions for algorithmic complexity, or at least asymptotic expressions in O(ċ)-notation. It is often possible to use experimental results to make significant progress towards this goal, although there are fundamental reasons why we cannot guarantee to obtain such expressions from experiments alone. This paper investigates two approaches relating to problems of developing theoretical analyses based on experimental data.We first consider the scientific method, which views experimentation as part of a cycle alternating with theoretical analysis. This approach has been very successful in the natural sciences. Besides supplying preliminary ideas for theoretical analysis, experiments can test falsifiable hypotheses obtained by incomplete theoretical analysis. Asymptotic behavior can also sometimes be deduced from stronger hypotheses which have been induced from experiments. As long as complete mathematical analyses remains elusive, well tested hypotheses may have to take their place. Several examples are given where average complexity can be tested experimentally so that support for hypotheses is quite strong.A second question is how to approach systematically the problem of inferring asymptotic bounds from experimental data. Five heuristic rules for "empirical curve bounding" are presented, ogether with analytical results guaranteeing correctness for certain families of functions. Experimental evaluations of the correctness and tightness of bounds obtained by the rules for several constructed functions and real datasets are described.
Using Options for Knowledge Transfer in Reinforcement Learning

One of the original motivations for the use of temporally extended actions, or options, in reinforcement learning was to enable t he transfer of learned value functions or policies to new problems. Many experimenters have used options to speed learning on single problems, but options have not been studied in depth as a tool for transfer. In this paper we introduce a formal model of a learning problem as a distribution of Markov Decision Problems (MDPs). Each MDP represents a task the agent will have to solve. Our model can also be viewed as a partially observable Markov decision problem (POMDP), with a special structure that we describe. We study two learning algorithms, one which keeps a single value function that generalizes across tasks, and an increm ental POMDPinspired method maintaining separate value functions for each task. We evaluate the learning algorithms on an extension of the Mountain Car domain, in terms of both learning speed and asymptotic performance. Empirically, we find that temporally extended options can fa cilitate transfer for both algorithms. In our domain, the single value func tion algorithm has much better learning speed because it generalizes its ex perience more broadly across tasks. We also observe that different sets of options can achieve tradeoffs of learning speed versus asymptotic perf ormance.
Learning to Schedule Straight-Line Code

Program execution speed on modern computers is sensitive, by a factor of two or more, to the order in which instructions are presented to the processor. To realize potential execution efficiency, an optimizing compiler must employ a heuristic algorithm for instruction scheduling. Such algorithms are painstakingly hand-crafted, which is expensive and time-consuming. We show how to cast the instruction scheduling problem as a learning task, obtaining the heuristic scheduling algorithm automatically. Our focus is the narrower problem of scheduling straight-line code (also called basic blocks of instructions). Our empirical results show that just a few features are adequate for quite good performance at this task for a real modern processor, and that any of several supervised learning methods perform nearly optimally with respect to the features used.
Learning Policies for Local Instruction Scheduling

Execution speed of programs on modern computer architectur es is sensitive, by a factor of two or more, to the order in which instructions are presented to t he processor. To realize potential execution efficiency, it is now customary for an optimizing compiler to employ a heuristic algorithm for instruction scheduling. These algorithms are currently hand-crafted. We show how to cast the local instruction scheduling problem as a machine learning task, so that one obtains a heur istic scheduling algorithm automatically. Our empirical results demonstrate that just a few features are a dequate for competence at this task for a real modern processor, and that any of several supervised learni ng methods perform nearly optimally with respect to the features used. The learning goal is to minimize the cyc les needed for each basic block, in isolation and assuming all memory accesses hit in the cache. We found th at competence at this task resulted in good measured execution times for entire scheduled programs. In the end, we essentially match the performance of commercial compilers for the same processor, and offer some evidence that our learned heuristics are nearly optimal.
How to Find Big-Oh in Your Data Set (and How Not to)

The empirical curve bounding problem is defined as follows. Suppose data vectors X, Y are presented such that E(Y[i])=f(X[i]) where f(x) is an unknown function. The problem is to analyze X, Y and obtain complexity bounds O(g u (x)) and Ω(g i (x)) on the function −f(x). As no algorithm for empirical curve bounding can be guaranteed correct, we consider heuristics. Five heuristic algorithms are presented here, together with analytical results guaranteeing correctness for certain families of functions. Experimental evaluations of the correctness and tightness of bounds obtained by the rules for several constructed functions f(x) and real datasets are described. A hybrid method is shown to have very good performance on some kinds of functions, suggesting a general, iterative refinement procedure in which diagnostic features of the results of applying particular methods can be used to select additional methods.
Benchmarking Non-Parametric Statistical Tests

Although non-parametric tests have already been proposed for that purpose, statistical significance tests for non-standard measures (different from the classification error) are less often used in the literature. This paper is an attempt at empirically verifying how these tests compare with more classical tests, on various conditions. More precisely, using a very large dataset to estimate the whole "population", we analyzed the behavior of several statistical test, varying the class unbalance, the compared models, the performance measure, and the sample size. The main result is that providing big enough evaluation sets non-parametric tests are relatively reliable in all conditions.
Machine Learning for Automatic Environmental Mapping : When and How

This paper discusses the opportunity of using Machine Learning techniques in an automatic environmental mapping context, as was the case for the SIC2004 exercise. First, the Machine Learning methodology is quickly described and compared to Geostatistics. From there, some clues about when to apply Machine Learning are proposed, and what outcomes can be expected from this choice. Finally, three well known regression algorithms: K-Nearest Neighbors, Multi Layer Perceptron and Support Vector Regression, are used on SIC2004 data in a Machine Learning context, and compared to Ordinary Kriging. This illustrates some potential drawbacks of SVR and MLP for applications such as SIC2004.
A Score-Level Fusion Benchmark Database for Biometric Authentication

Fusing the scores of several biometric systems is a very promising approach to improve the overall system's accuracy. Despite many works in the literature, it is surprising that there is no coordinated effort in making a benchmark database available. It should be noted that fusion in this context consists not only of multimodal fusion, but also intramodal fusion, i.e., fusing systems using the same biometric modality but different features, or same features but using different classifiers. Building baseline systems from scratch often prevents researchers from putting more efforts in understanding the fusion problem. This paper describes a database of scores taken from experiments carried out on the XM2VTS face and speaker verification database. It then proposes several fusion protocols and provides some state-of-the-art tools to evaluate the fusion performance.
Extracting information from multimedia meeting collections

Multimedia meeting collections, composed of unedited audio and video streams, handwritten notes, slides, and electronic documents that jointly constitute a raw record of complex human interaction processes in the workplace, have attracted interest due to the increasing feasibility of recording them in large quantities, by the opportunities for information access and retrieval applications derived from the automatic extraction of relevant meeting information, and by the challenges that the extraction of semantic information from real human activities entails. In this paper, we present a succint overview of recent approaches in this field, largely influenced by our own experiences. We first review some of the existing and potential needs for users of multimedia meeting information systems. We then summarize recent work on various research areas addressing some of these requirements. In more detail, we describe our work on automatic analysis of human interaction patterns from audio-visual sensors, discussing open issues in this domain.
A graphical model for chord progressions embedded in a psychoacoustic space

Chord progressions are the building blocks from which tonal music is constructed. Inferring chord progressions is thus an essential step towards modeling long term dependencies in music. In this paper, a distributed representation for chords is designed such that Euclidean distances roughly correspond to psychoacoustic dissimilarities. Parameters in the graphical models are learnt with the EM algorithm and the classical Junction Tree algorithm. Various model architectures are compared in terms of conditional out-of-sample likelihood. Both perceptual and statistical evidence show that binary trees related to meter are well suited to capture chord dependencies.
How do correlation and variance of base-experts affect fusion in biometric authentication tasks?

Combining multiple information sources such as subbands, streams (with different features) and multimodal data has been shown to be a very promising trend, both in experiments and to some extents in real-life biometric authentication applications. Despite considerable efforts in fusions, there is a lack of understanding on the roles and effects of correlation and variance (of both the client and impostor scores of base-classifiers/experts). Often, scores are assumed to be independent. In this paper, we explicitly consider this factor using a theoretical model, called variance reduction-equal error rate (VR-EER) analysis. Assuming that client and impostor scores are approximately Gaussian distributed, we showed that equal error rate (EER) can be modeled as a function of F-ratio, which itself is a function of 1) correlation; 2) variance of base-experts; and 3) difference of client and impostor means. To achieve lower EER, smaller correlation and average variance of base-experts, and larger mean difference are desirable. Furthermore, analysing any of these factors independently, e.g. focusing on correlation alone, could be miss-leading. Experimental results on the BANCA multimodal database confirm our findings using VR-EER analysis. We analyzed four commonly encountered scenarios in biometric authentication which include fusing correlated/uncorrelated base-experts of similar/different performances. The analysis explains and shows that fusing systems of different performances is not always beneficial. One of the most important findings is that positive correlation "hurts" fusion while negative correlation (greater "diversity", which measures the spread of prediction score with respect to the fused score), improves fusion. However, by linking the concept of ambiguity decomposition to classification problem, it is found that diversity is not sufficient to be an evaluation criterion (to compare several fusion systems), unless measures are taken to normalize the (class-dependent) variance. Moreover, by linking the concept of bias-variance-covariance decomposition to classification using EER, it is found that if the inherent mismatch (between training and test sessions) can be learned from the data, such mismatch can be incorporated into the fusion system as a part of training parameters.