nils-herrmann/clean_scirepeval huggingface dataset:
0 Speeding up Backpropagation Algorithms

Table 2. Results of the best runs for the Geneeproblem. CENNBPROP yields both the lowest training and the lowest testing error. Training set Testing set Algorithm SSE Class. rate SSE Class. achieved the lowest SSE although RPROP normally outperforms BPROP. F or the Thyroiddproblem CENNBPROP proved to be comparable with standard RPROP. CENNRPROP always yields the best results SSE=0.0 and beats the standard RPROP which still left some residual errors. In the beginning of training, CENNBPROP has worked best for both benchmark problems. This can be explained by the fact that RPROP needs some time to adapt its step widths. The CENNoptimization improves BPROP training with respect to convergence speed and the nal quality of the trained networks. Especially, t h i s is exploited in the case of the Thyroiddproblem. Since CENNBPROP updates the weights after each pattern presentation online training, it should be well suited for applications with feedback, e.g. neural controllers. In summary, CENNoptimization has proven to outperform all the investigated BP algorithms and we guess that it is the fastest training algorithm at the time being. Of course, this claim needs to be veriied by using much more benchmarks and comparisons to other training algorithms. A direct adaptive method for faster backpropagation learning: The rprop algorithm. Table 1. Results of the best runs for the Thyroiddproblem. CENNRPROP yields both the lowest training error and the lowest testing error. training set testing set Algorithmus SSE Class. rate SSE Class. rate BPROP 246.0 For each problem 10 networks were created which are then used for the four different training algorithms. Before training, the networks were initialized by random numbers drawn from a normal distribution with zero mean and a standard deviation of 0.01. Thus, all algorithms had equal initial conditions. BPROP and CENNBPROP used a learning rate of 0.01 and a momentum of 0.9. RPROP and CENNRPROP used an initial step width of 0.001, uppdown factors of 0.551.2 and a minimallmaximal step width of 10 ,6 50.0, repectively. The results are displayed in gure 1 for the Thyroiddproblem and in gure 2 for the Geneeproblem. All the 10 runs were plotted simultaneously. Note that the standard and the CENNoptimized versions can only be compared if the SSE is plotted over the numberofepochs. In table 1 and in table 2, the results of the best runs are summarized. The generalization performance is estimated by the error with respect to …
Using Mixtures of Factor Analyzers for Segmentation and Pose Estimation

To read a hand-written digit string, it is helpful to segment the image into separate digits. Bottom-up segmentation heuristics often fail when neighboring digits overlap substantially. We describe a system that has a stochastic generative model of each digit class and we show that this is the only knowledge required for segmentation. The system uses Gibbs sampling to construct a perceptual interpretation of a digit string and segmentation arises naturally from the \explaining away" e ects that occur during Bayesian inference. By using conditional mixtures of factor analyzers, it is possible to extract an explicit, compact representation of the instantiation parameters that describe the pose of each digit. These instantiation parameters can then be used as the inputs to a higher level system that models the relationships between digits. The same technique could be used to model individual digits as redundancies between the instantiation parameters of their parts.
GTM through time

The standard GTM (generative topographic mapping) algorithm assumes that the data on which it is trained consists of independent, identically distributed (i.i.d.) vectors. For time series, however, the i.i.d. assumption is a poor approximation. In this paper we show how the GTM algorithm can be extended to model time series by incorporating it as the emission density in a hidden Markov model. Since GTM has discrete hidden states we are able to find a tractable EM algorithm, based on the forward-backward algorithm, to train the model. We illustrate the performance of GTM through time using flight recorder data from a helicopter.
nerative Models for andwritten Digit Recognition

We describe a method of recognizing handwritten digits by fitting generative models that are built from deformable B- splines with Gaussian "ink generators" spaced along the length of the spline. The splines are adjusted using a novel elastic matching procedure based on the Expectation Maximization (EM) algorithm that maximizes the likelihood of the model generating the data. This approach has many advantages. 1) After identifying the model most likely to have generated the data, the system not only produces a classification of the digit but also a rich description of the instantiation parameters which can yield information such as the writing style. 2) During the process of explaining the image, generative models can perform recognition driven segmentation. 3) The method involves a relatively small number of parameters and hence training is relatively easy and fast. 4) Unlike many other recognition schemes, it does not rely on some form of pre-normalization of input images, but can handle arbitrary scalings, translations and a limited degree of image rotation. We have demonstrated our method of fitting models to images does not get trapped in poor local minima. The main disadvantage of the method is it requires much more computation than more standard OCR techniques. Index Terms-Deformable model, elastic net, optical character recognition, generative model, probabilistic model, mixture model
Glove-TalkII: an adaptive gesture-to-formant interface

Glove-TaikII is a system which translates hand gestures-· to speech through an adaptive interface. Hand gestures are mapped continuously to 10 control parameters of a parallel formant speech synthesizer. The mapping allows the hand to act as an artificial vocal tract that produces speech in real time. This gives an unlimited vocabulary, multiple languages in addition to direct control of fundamental frequency and volume. Currently, the best version of Glove-TaikII uses several input devices (including a Cyberglove, a ContactGlove, a polhemus sensor, and a foot-pedal), a parallel formant speech synthesizer and 3 neural networks. The gestureto-speech task is divided into vowel and consonant production by using a gating network to weight the outputs of a vowel and a consonant neural network. The gating network and the consonant network are trained with examples from the user. The vowel network implements a fixed, user-defined relationship between hand-position and vowel sound and does not require any training examples from the user. Volume, fundamental frequency and stop consonants are produced with a fixed mapping from the input devices. One subject has trained for about 100 hours to speak intelligibly with Glove-TalkII. He passed through eight distinct stages while learning to speak. He speaks slowly with speech quality similar to a text-to-speech synthesizer but with far more natural-sounding pitch variations.
The Helmholtz Machine

Discovering the structure inherent in a set of patterns is a fundamental aim of statistical inference or learning. One fruitful approach is to build a parameterized stochastic generative model, independent draws from which are likely to produce the patterns. For all but the simplest generative models, each pattern can be generated in exponentially many ways. It is thus intractable to adjust the parameters to maximize the probability of the observed patterns. We describe a way of finessing this combinatorial explosion by maximizing an easily computed lower bound on the probability of the observations. Our method can be viewed as a form of hierarchical self-supervised learning that may relate to the function of bottom-up and top-down cortical processing pathways.
Spatial coherence as an internal teacher for a neural network

Supervised learning procedures for neural networks have recently met with considerable success in learning di cult mappings. So far, however, they have been limited by their poor scaling behaviour, particularly for networks with many hidden layers. A promising alternative is to develop unsupervised learning algorithms by de ning objective functions that characterize the quality of an internal representation without requiring knowledge of the desired outputs of the system. Our major goal is to build self-organizing network modules which capture important regularities in the environment in a simple form. A layered hierarchy of such modules should be able to learn in a time roughly linear in the number of layers. We propose that a good objective for perceptual learning is to extract higher-order features that exhibit simple coherence across time or space. This can be done by transforming the input representation into an underlying representation in which the mutual information between adjacent patches of the input can be expressed in a simple way. We have applied this basic idea to develop several interesting learning algorithms for discovering spatially coherent features in images. Our simulations show that a network can discover depth of surfaces when trained on binary random dot stereograms with discrete global shifts, as well as on real-valued stereograms of surfaces with continuously varying disparities. Once a module of depth-tuned units has developed, we show that units in a higher layer can discover a simple form of surface interpolation of curved surfaces, by learning to predict the depth of one image region based on depth measurements in surrounding regions.
Using Pairs of Data-Points to Define Splits for Decision Trees

Conventional binary classification trees such as CART either split the data using axis-aligned hyperplanes or they perform a computationally expensive search in the continuous space of hyperplanes with unrestricted orientations. We show that the limitations of the former can be overcome without resorting to the latter. For every pair of training data-points, there is one hyperplane that is orthogonal to the line joining the data-points and bisects this line. Such hyperplanes are plausible candidates for splits. In a comparison on a suite of 12 datasets we found that this method of generating candidate splits outperformed the standard methods, particularly when the training sets were small.
How Learning Can Guide Evolution

The assumption that acquired character istics are not in­ herited is ofte n taken to imply t hat t he adaptations t hat an organism learns dur ing its lifeti me cannot guide t he course of evolut ion . This infere nce is incor rec t (2). Learni ng alt ers the shape of t he search space in which evolu tio n operates and thereby pro vides good evolut ion ar y paths towa rds sets of co-adapted alleles. We demonst r at e t hat th is effect allows learning organisms to evolve much faster than their 000 ­ learning equivalents, even though the characteris tics acquired by t he phenotype are not communicated to the genotype.
A construction of a cipher from a single pseudorandom permutation

We suggest a scheme for a block cipher which uses only one randomly chosen permutation,F. The key, consisting of two blocks,K1 andK2, is used in the following way. The message block is XORed withK1 before applyingF, and the outcome is XORed withK2, to produce the cryptogram block. We show that the resulting cipher is secure (when the permutation is random or pseudorandom). This removes the need to store, or generate a multitude of permutations.
From External to Internal Regret

External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an online algorithm to the loss of a modified online algorithm, which consistently replaces one action by another. In this paper, we give a simple generic reduction that, given an algorithm for the external regret problem, converts it to an efficient online algorithm for the internal regret problem. We provide methods that work both in the full information model, in which the loss of every action is observed at each time step, and the partial information (bandit) model, where at each time step only the loss of the selected action is observed. The importance of internal regret in game theory is due to the fact that in a general game, if each player has sublinear internal regret, then the empirical frequencies converge to a correlated equilibrium. For external regret we also derive a quantitative regret bound for a very general setting of regret, which includes an arbitrary set of modification rules (that possibly modify the online algorithm) and an arbitrary set of time selection functions (each giving different weight to each time step). The regret for a given time selection and modification rule is the difference between the cost of the online algorithm and the cost of the modified online algorithm, where the costs are weighted by the time selection function. This can be viewed as a generalization of the previously-studied sleeping experts setting.
Harnessing Machine Learning to Improve the Success Rate of Stimuli Generation

The initial state of a design under verification has a major impact on the ability of stimuli generators to successfully generate the requested stimuli. For complexity reasons, most stimuli generators use sequential solutions without planning ahead. Therefore, in many cases, they fail to produce a consistent stimuli due to an inadequate selection of the initial state. We propose a new method, based on machine learning techniques, to improve generation success by learning the relationship between the initial state vector and generation success. We applied the proposed method in two different settings, with the objective of improving generation success and coverage in processor and system level generation. In both settings, the proposed method significantly reduced generation failures and enabled faster coverage
Harnessing machine learning to improve the success rate of stimuli generation

The initial state of a design under verification has a major impact on the ability of stimuli generators to successfully generate the requested stimuli. For complexity reasons, most stimuli generators use sequential solutions without planning ahead. Therefore, in many cases they fail to produce consistent stimuli due to an inadequate selection of the initial state. We propose a method, based on machine learning techniques, to improve generation success by learning the relationship between the initial state vector and generation success. We applied the proposed method in two different settings, with the objective of improving generation success and coverage in processor and system level generation. In both settings, the proposed method significantly reduced generation failures and enabled faster coverage.
Planning in POMDPs Using Multiplicity Automata

Planning and learning in Partially Observable MDPs (POMDPs) are among the most challenging tasks in both the AI and Operation Research communities. Although solutions to these problems are intractable in general, there might be special cases, such as structured POMDPs, which can be solved efficiently. A natural and possibly efficient way to represent a POMDP is through the predictive state representation (PSR) — a representation which recently has been receiving increasing attention. 
 
In this work, we relate POMDPs to multiplicity automata — showing that 
 
POMDPs can be represented by multiplicity automata with no increase in the representation size. Furthermore, we show that the size of the multiplicity automaton is equal to the rank of the predictive state representation. Therefore, we relate both the predictive state representation and POMDPs to the well-founded multiplicity automata literature. 
 
Based on the multiplicity automata representation, we provide a planning algorithm which is exponential only in the multiplicity automata rank rather than the number of states of the POMDP. As a result, whenever the predictive state representation is logarithmic in the standard POMDP representation, our planning algorithm is efficient.
Improved Second-Order Bounds for Prediction with Expert Advice

This work studies external regret in sequential prediction games with arbitrary payoffs (nonnegative or non-positive). External regret measures the difference between the payoff obtained by the forecasting strategy and the payoff of the best action. We focus on two important parameters: M, the largest absolute value of any payoff, and Q*, the sum of squared payoffs of the best action. Given these parameters we derive first a simple and new forecasting strategy with regret at most order of $\sqrt{Q^{*}({\rm ln}N)}+M {\rm ln} N$, where N is the number of actions. We extend the results to the case where the parameters are unknown and derive similar bounds. We then devise a refined analysis of the weighted majority forecaster, which yields bounds of the same flavour. The proof techniques we develop are finally applied to the adversarial multi-armed bandit setting, and we prove bounds on the performance of an online algorithm in the case where there is no lower bound on the probability of each action.
Combining Online Algorithms for Acceptance and Rejection

Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both under benefit models (e.g., with a goal of approximately maximizing the number of requests accepted) and under cost models (e.g., with a goal of approximately minimizing the number of requests rejected). Unfortunately, algorithms designed for these two measures can often be quite different, even polar opposites. In this work we consider the problem of combining algorithms designed for each of these objectives in a way that is good under both measures simultaneously. More formally, we are given an algorithm A that is cA competitive with respect to the number of accepted requests and an algorithm R that is cR competitive with respect to the number of rejected requests. We show how to derive a combined algorithm with competitive ratio O(cRcA) for rejection and O(cA) for acceptance. We also build on known techniques to show that given a collection of k algorithms, we can
Reinforcement Learning in POMDPs Without Resets

We consider the most realistic reinforcement learning setting in which an agent starts in an unknown environment (the POMDP) and must follow one continuous and uninterrupted chain of experience with no access to "resets" or "offline" simulation. We provide algorithms for general connected POMDPs that obtain near optimal average reward. One algorithm we present has a convergence rate which depends exponentially on a certain horizon time of an optimal policy, but has no dependence on the number of (unobservable) states. The main building block of our algorithms is an implementation of an approximate reset strategy, which we show always exists in every POMDP. An interesting aspect of our algorithms is how they use this strategy when balancing exploration and exploitation.
Agnostically Learning Halfspaces

We give the first algorithm that (under distributional assumptions) efficiently learns halfspaces in the notoriously difficult agnostic framework of Kearns, Schapire, & Sellie, where a learner is given access to labeled examples drawn from a distribution, without restriction on the labels (e.g. adversarial noise). The algorithm constructs a hypothesis whose error rate on future examples is within an additive /spl epsi/ of the optimal halfspace, in time poly(n) for any constant /spl epsi/ > 0, under the uniform distribution over {-1, 1}/sup n/ or the unit sphere in /spl Ropf//sup n/ , as well as under any log-concave distribution over /spl Ropf/ /sup n/. It also agnostically learns Boolean disjunctions in time 2/sup O~(/spl radic/n)/ with respect to any distribution. The new algorithm, essentially L/sub 1/ polynomial regression, is a noise-tolerant arbitrary distribution generalization of the "low degree" Fourier algorithm of Linial, Mansour, & Nisan. We also give a new algorithm for PAC learning halfspaces under the uniform distribution on the unit sphere with the current best bounds on tolerable rate of "malicious noise".
Adaptive AIMD Congestion Control

AbstractThe main objectives of a congestion control algorithm are
high bandwidth utilization, fairness and responsiveness in a
changing environment. However, these objectives are contradicting 
in particular situations since the algorithm
 constantly has to probe available bandwidth,
which may affect its stability. This paper proposes a novel congestion 
control algorithm that achieves high bandwidth utilization
providing fairness among competing connections 
and, on the other hand, is sufficiently responsive to 
changes of available bandwidth. The main idea of the algorithm
is to use adaptive setting for the additive increase/multiplicative decrease (AIMD)
congestion control scheme, where parameters may change
dynamically, with respect to the current network conditions.
Improved Competitive Guarantees for QoS Buffering

AbstractWe consider a network providing Differentiated
Services (DiffServ), which allow Internet Service
Providers (ISPs) to offer different levels of
Quality of Service (QoS) to different traffic streams.
We study two types of buffering policies that are used in network
switches supporting QoS. In the FIFO
type, packets must be transmitted in the order they arrive.
In the uniform bounded delay type, there is a maximal delay time
associated with the switch and each packet
must be transmitted within this time, or otherwise it is dropped.
In both models the buffer space is limited, and packets are lost
when the buffer overflows.
Each packet has an intrinsic value, and the goal is to
maximize the total value of transmitted packets.
Our main contribution is an algorithm
for the FIFO model with arbitrary packet values
that for the first time achieves a competitive ratio
better than 2, namely 2-ε for a constant ε gt; 0.
We also describe an algorithm for the uniform bounded delay
model which simulates our algorithm for the FIFO
model, and show that it achieves the same competitive ratio.
Mechanism design via machine learning

We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or /spl beta/-approximation) algorithm for the standard algorithmic problem, we can convert it into a (1 + /spl epsi/)-approximation (or /spl beta/(1 +/spl epsi/)-approximation) for the incentive-compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the comparison class of solutions. We apply these results to the problem of auctioning a digital good, the attribute auction problem, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a learning perspective, these settings present several challenges: in particular the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large.