nils-herrmann/clean_scirepeval huggingface dataset:
Generalized^2 Linear^2 Models

We introduce the Generalized2 Linear2 Model, a statistical estimator which combines features of nonlinear regression and factor analysis. A (GL)2M approximately decomposes a rectangular matrix X into a simpler representation f(g(A)h(B)). Here A and B are low-rank matrices, while f, g, and h arc link functions. (GL)2Ms include many useful models as special cases, including principal components analysis, exponential-family PCA, the infomax formulation of independent components analysis, linear regression, and generalized linear models. They also include new and interesting special cases, one of which we describe below. We also present an iterative procedure which optimizes the parameters of a (GL)2M. This procedure reduces to well-known algorithms for some of the special cases listed above; for other special cases, it is new.
Distributed Planning in Hierarchical Factored MDPs

We present a principled and efficient planning algorithm for collaborative multiagent dynamical systems. All computation, during both the planning and the execution phases, is distributed among the agents; each agent only needs to model and plan for a small part of the system. Each of these local subsystems is small, but once they are combined they can represent an exponentially larger problem. The subsystems are connected through a subsystem hierarchy. Coordination and communication between the agents is not imposed, but derived directly from the structure of this hierarchy. A globally consistent plan is achieved by a message passing algorithm, where messages correspond to natural local reward functions and are computed by local linear programs; another message passing algorithm allows us to execute the resulting policy. When two portions of the hierarchy share the same structure, our algorithm can reuse plans and messages to speed up computation.
Policy-contingent state abstraction for hierarchical MDPs

Hierarchically structured planning problems often provid e great opportunities for state abstraction: high-level planners can ig nore fine details, while low-level planners can focus only on specific tasks. Mo st previous hierarchical MDP algorithms rely on hand-designed, k nowledgeintensive state abstractions. We propose instead an automa tic, lazy algorithm which plans from the bottom of the hierarchy up and fin s good abstractions for high-level planners contingent on their s ubtasks’ optimal policies. This policy-contingent approach can often abstr act away more details than a human, specifically because it has access to mo re inf rmation (namely its subtasks’ policies) when it decides whet her o cluster states. We demonstrate that our algorithm finds better abstr actions than human designers on well-known planning tasks.
Reinforcement Learning with Function Approximation Converges to a Region

Many algorithms for approximate reinforcement learning are not known to converge. In fact, there are counterexamples showing that the adjustable weights in some algorithms may oscillate within a region rather than converging to a point. This paper shows that, for two popular algorithms, such oscillation is the worst that can happen: the weights cannot diverge, but instead must converge to a bounded region. The algorithms are SARSA(0) and V(0); the latter algorithm was used in the well-known TD-Gammon program.
Learning Filaments

This paper is about new statistics and new ef-cient algorithms for a form of mixture model that learns lamentary structures. Such models are important in several areas of sci-entiic data analysis, but in this paper our main example is identiication of large-scale structure among galaxies. We describe software which can extract the positions of spherical and line-shaped clusters from data about the locations of objects such as galaxies. We do so by tting a particular type of Gaussian mixture model to the galaxy locations. The most interesting feature of our model is that it directly represents line segments in the distribution , unlike standard Gaussian mixture models which can only handle ellipses. Because we t the line segments directly, we do not need to do any post-processing to extract their locations. We use a modiication of the k-means algorithm to nd model parameters. Since our software needs to deal with large data sets, it is important to accelerate model-tting as much as possible. So, we store the galaxy locations in a multi-resolution kd-tree, and we introduce new pruning algorithms that allow us to skip over large parts of the tree in each k-means step. We provide evaluations on both synthetic and real data sets.
Approximate solutions to markov decision processes

One of the basic problems of machine learning is deciding how to act in an uncertain world. For example, if I want my robot to bring me a cup of coffee, it must be able to compute the correct sequence of electrical impulses to send to its motors to navigate from the coffee pot to my office. In fact, since the results of its actions are not completely predictable, it is not enough just to compute the correct sequence; instead the robot must sense and correct for deviations from its intended path. 
In order for any machine learner to act reasonably in an uncertain environment, it must solve problems like the above one quickly and reliably. Unfortunately, the world is often so complicated that it is difficult or impossible to find the optimal sequence of actions to achieve a given goal. So, in order to scale our learners up to real-world problems, we usually must settle for approximate solutions. 
One representation for a learner's environment and goals is a Markov decision process or MDP. MDPs allow us to represent actions that have probabilistic outcomes, and to plan for complicated, temporally-extended goals. An MDP consists of a set of states that the environment can be in, together with rules for how the environment can change state and for what the learner is supposed to do. 
One way to approach a large MDP is to try to compute an approximation to its optimal state evaluation function, the function which tells us how much reward the learner can be expected to achieve if the world is in a particular state. If the approximation is good enough, we can use a shallow search to find a good action from most states. Researchers have tried many different ways to approximate evaluation functions. This thesis aims for a middle ground, between algorithms that don't scale well because they use an impoverished representation for the evaluation function and algorithms that we can't analyze because they use too complicated a representation.
Online Fitted Reinforcement Learning

My paper in the main portion of the conference deals with tted value iteration or Q-learning for ooine problems, i.e., those where we h a ve a model of the environment so that we can examine arbitrary transitions in arbitrary order. The same techniques also allow us to do Q-learning for an online problem, i.e., one where we h a ve n o m o del but must instead perform experiments inside the MDP to gather data. I will describe how.
Tracking the Best Expert

AbstractWe 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 
$$O\left( {klogn + k\log \left( {{\ell \mathord{\left/ {\vphantom {\ell k}} \right. \kern-\nulldelimiterspace} k}} \right)} \right)$$
. 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 
$$O\left( {klogn + k\log \left( {{\ell \mathord{\left/ {\vphantom {\ell k}} \right. \kern-\nulldelimiterspace} k}} \right)} \right)$$
 , 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.
Relative loss bounds for predicting almost as well as any function in a union of Gaussian reproducing kernel spaces with varying widths ?

We consider a two-layer network algorithm. The first layer consists of an uncountable number of linear units. Each linear unit is an LMS algorithm whose inputs are first “kernelized.” Each unit is indexed by the value of a parameter corresponding to a parameterized reproducing kernel, here an isotropic Gaussian Kernel parameterized by its width. The first-layer outputs are then connected to an Exponential Weights algorithm which combines them to produce the final output. We give performance guarantees for this algorithm. As a guarantee of performance, we give a relative loss bound for this online algorithm. By online, we refer to the fact that learning proceeds in trials where on each trial the algorithm first receives a pattern, then it makes a prediction, after which it receives the true outcome, and finally incurs a loss on that trial measuring the discrepancy between its prediction and the true outcome. By relative loss bound, we refer to the fact on any trial, we can bound the cumulative of loss of the algorithm by the cumulative loss of any predictor in a comparison class of predictors plus an additive term. Hence the goal is that the performance of algorithm be almost as good as any predictor in the class; therefore we desire a small additive term. Often these bounds may be given without any probabilistic assumptions. In this note the comparison class is the set of functions obtained by a union of reproducing kernel spaces formed by isotropic Gaussian kernels of varying widths.
Relative Loss Bounds and Polynomial-Time Predictions for the k-lms-net Algorithm

We consider a two-layer network algorithm. The first layer consists of an uncountable number of linear units. Each linear unit is an LMS algorithm whose inputs are first “kernelized.” Each unit is indexed by the value of a parameter corresponding to a parameterized reproducing kernel. The first-layer outputs are then connected to an exponential weights algorithm which combines them to produce the final output. We give loss bounds for this algorithm; and for specific applications to prediction relative to the best convex combination of kernels, and the best width of a Gaussian kernel. The algorithm’s predictions require the computation of an expectation which is a quotient of integrals as seen in a variety of Bayesian inference problems. Typically this computational problem is tackled by mcmc, importance sampling, and other sampling techniques for which there are few polynomial time guarantees of the quality of the approximation in general and none for our problem specifically. We develop a novel deterministic polynomial time approximation scheme for the computations of expectations considered in this paper.
A combined Bayes - maximum likelihood method for regression

In this paper we propose an efficient method for model selection. We apply this method to select the degree of regularization, and either the number of basis functions or the parameters of a kernel function to be used in a regression of the data. The method combines the well-known Bayesian approach with the maximum likelihood method. The Bayesian approach is applied to a set of models with conventional priors that depend on unknown parameters, and the maximum likelihood method is used to determine these parameters. When parameter values determine the complexity of a model, a determination of model complexity is thus obtained. Under the assumption of Gaussian noise the method leads to a computationally feasible procedure for determining the optimum number of basis functions and the degree of regularization in ridge regression. This procedure is an inexpensive alternative to cross-validation. In the non-Gaussian case we show connections to support vectors methods. We also present experimental results comparing this method to other methods of model complexity selection, including cross-validation.
Learning Additive Models Online with Fast Evaluating Kernels

We develop three new techniques to build on the recent advances in online learning with kernels. First,w e show that an exponential speed-up in prediction time per trial is possible for such algorithms as the Kernel-Adatron,the Kernel-Perceptron,and ROMMA for specific additive models. Second,w e show that the techniques of the recent algorithms developed for online linear prediction when the best predictor changes over time may be implemented for kernel-based learners at no additional asymptotic cost. Finally,w e introduce a new online kernel-based learning algorithm for which we give worst-case loss bounds for the Ɛ-insensitive square loss.
Tracking the Best Linear Predictor

In most on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best off-line predictor u from a comparison class of predictors. We call such bounds static bounds. The interesting feature of these bounds is that they hold for an arbitrary sequence of examples. Recently some work has been done where the predictor ut at each trial t is allowed to change with time, and the total on-line loss of the algorithm is compared to the sum of the losses of ut at each trial plus the total "cost" for shifting to successive predictors. This is to model situations in which the examples change over time, and different predictors from the comparison class are best for different segments of the sequence of examples. We call such bounds shifting bounds. They hold for arbitrary sequences of examples and arbitrary sequences of predictors.Naturally shifting bounds are much harder to prove. The only known bounds are for the case when the comparison class consists of a sequences of experts or boolean disjunctions. In this paper we develop the methodology for lifting known static bounds to the shifting case. In particular we obtain bounds when the comparison class consists of linear neurons (linear combinations of experts). Our essential technique is to project the hypothesis of the static algorithm at the end of each trial into a suitably chosen convex region. This keeps the hypothesis of the algorithm well-behaved and the static bounds can be converted to shifting bounds.
Learning algorithms for tracking changing concepts and an investigation into the error surfaces of single artificial neurons

This thesis is divided into two distinct parts. 
In part I, we present on-line learning algorithms which are designed for combining classifiers or experts in nonstationary environments. The motivating assumption of our work is as follows: given a set of classifiers, and a data sequence whose underlying generative process is changing over time, we expect that different classifiers will perform well over different segments of the sequence. We give an algorithm whose performance is an additive term larger than the performance of the “best” sequence of classifiers. The additive term measures the degree of nonstationarity in the sequence of classifiers. 
In Part II, we consider some simple results which characterize certain properties of the error surface of an artificial neuron. We prove three results: one result is a sufficient condition for local minima (in fact “exponentially” many local minima), and two results are sufficient conditions for no local minima. These results hold for a wide variety of artificial neurons.
Tracking the best regressor

In most of the on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best off-line predictor u from a comparison class of predictors. We call such bounds static bounds. The interesting feature of these bounds is that they hold for an arbitrary sequence of examples. Recently some work has been done where the comparison vector ut at each trial t is allowed to change with time, and the total online loss of the algorithm is compared to the sum of the losses of ut at each trial plus the total “cost” for shifting to successive comparison vectors. This is to model situations in which the examples change over time and different predictors from the comparison class are best for different segments of the sequence of examples. We call such bounds shifting bounds. Shifting bounds still hold for arbitrary sequences of examples and also for arbitrary partitions. The algorithm does not know the offline partition and the sequence of predictors that its performance is compared against. Naturally shifting bounds are much harder to prove. The only known bounds are for the case when the comparison class consists of a finite sets of experts or boolean disjunctions. In this paper we develop the methodology for lifting known static bounds to the shifting case. In particular we obtain bounds when the comparison class consists of linear neurons (linear combinations of experts). Our essential technique consists of the following. At the end of each trial we project the hypothesis of the static algorithm into a suitably chosen convex region. This keeps the hypothesis of the algorithm well-behaved and the static bounds can be converted to shifting bounds so that the cost for shifting remains reasonable. The authors were supported by the NSF grant CCR-9700201 Permission to make digital or h,a.rd copies of all or part oftbis work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. COLT 98 Madison WI 1JSA
Fast learning rates for plug-in classifiers under the margin condition

It has been recently shown that, under the margin (or low noise) assumption, there exist classiflers attaining fast rates of convergence of the excess Bayes risk, i.e., the rates faster than n i1=2 . The works on this subject suggested the following two conjectures: (i) the best achievable fast rate is of the order n i1 , and (ii) the plug-in classiflers generally converge slower than the classiflers based on empirical risk minimization. We show that both conjectures are not correct. In particular, we construct plug-in classiflers that can achieve not only the fast, but also the super-fast rates, i.e., the rates faster than n i1 . We establish minimax lower bounds showing that the obtained rates cannot be improved.
A BETTER VARIANCE CONTROL FOR PAC-BAYESIAN CLASSIFICATION

The common method to understand and improve classification rules is to prove bounds on the generalization error. Here we provide localized data-based PAC-bounds for the difference between the risk of any two randomized estimators. We derive from these bounds two types of algorithms: the first one uses combinatorial technics and is related to compression schemes whereas the second one involves Gibbs estimators. We also recover some of the results of the Vapnik-Chervonenkis theory and improve them by taking into account the variance term measured by the pseudo-distance (f1, f2) 7→ P[f1(X) 6= f2(X)]. Finally, we present different ways of localizing the results in order to improve the bounds and make them less dependent on the choice of the prior. For some classes of functions (such as VC-classes), this will lead to gain a logarithmic factor without using the chaining technique (see  for more details).
DATA-DEPENDENT GENERALIZATION ERROR BOUNDS FOR (NOISY) CLASSIFICATION: A PAC-BAYESIAN APPROACH

The common method to understand and improve classification rules is to prove bounds on the generalization error. Here we provide localized data-based PAC-bounds for the difference between the risk of any two randomized estimators. We derive from these bounds two types of algorithms: the first one uses combinatorial technics and is related to compression schemes whereas the second one involves Gibbs estimators. We also recover some of the results of the Vapnik-Chervonenkis theory and improve them by taking into account the variance term measured by the pseudo-distance (f1, f2) 7→ [f1(X) 6= f2(X)]. Finally, we present different ways of localizing the results in order to improve the bounds and make them less dependent on the choice of the prior. For some classes of functions (such as VC-classes), this will lead to gain a logN factor (without using the chaining technique (see  for more details)).
Classification under polynomial entropy and margin assump-tions and randomized estimators

The aim of this paper is two-fold. First we want to develop the PAC-Bayesian point of view [13, 3, 4, 1] and show how the efficiency of a Gibbs estimator relies on the weights given by the prior distribution to the balls centered at the best function in the model and associated with the pseudodistance (f1, f2) 7→ [f1(X) 6= f2(X)]. Secondly, we show how to recover and improve results under empirical and non empirical polynomial entropy assumptions and Tsybakov’s margin assumption. We also study the links between empirical and non empirical nets and give an observable version of the integral entropy [6, 9, 14].
Friedman derive a “ gradient boosting machine ” to estimate a function for some specified loss criteria

Numerous empirical results have shown that combining regression procedures can be a very efficient method. This work provides PAC bounds for the L2 generalization error of such methods. The interest of these bounds are twofold. First, it gives for any aggregating procedure a bound for the expected risk depending on the empirical risk and the empirical complexity measured by the Kullback-Leibler divergence between the aggregating distribution ρ̂ and a prior distribution π and by the empirical mean of the variance of the regression functions under the probability ρ̂. Secondly, by structural risk minimization, we derive an aggregating procedure which takes advantage of the unknown properties of the best mixture f̃ : when the best convex combination f̃ of d regression functions belongs to the d initial functions (i.e. when combining does not make the bias decrease), the convergence rate is of order (log d)/N . In the worst case, our combining procedure achieves a convergence rate of order p (log d)/N which is known to be optimal in a uniform sense when d > √ N (see [10, 15]). As in AdaBoost, our aggregating distribution tends to favor functions which disagree with the mixture on mispredicted points. Our algorithm is tested on artificial classification data (which have been also used for testing other boosting methods, such as AdaBoost).
PAC-Bayesian Generic Chaining

There exist many different generalization error bounds for classification. Each of these bounds contains an improvement over the others for certain situations. Our goal is to combine these different improvements into a single bound. In particular we combine the PAC-Bayes approach introduced by McAllester , which is interesting for averaging classifiers, with the optimal union bound provided by the generic chaining technique developed by Fernique and Talagrand . This combination is quite natural since the generic chaining is based on the notion of majorizing measures, which can be considered as priors on the set of classifiers, and such priors also arise in the PAC-bayesian setting.