nils-herrmann/clean_scirepeval huggingface dataset:
MULTIARMED BANDITS IN THE WORST CASE

We present a survey of results on a recently formulated variant of the classical (stochastic) multiarmed bandit problem in which no assumption is made on the mechanism generating the rewards. We describe randomized allocation policies for this variant and prove bounds on their regret as a function of the time horizon and the number of arms. These bounds hold for any assignment of rewards to the arms and are tight to within logarithmic factors.
Algorithmic Learning Theory

The 15th International Conference on Algorithmic Learning Theory (ALT’04) and the 7th International Conference on Discovery Science will be held at Padova University, Padova, Italy, October 2 5, 2004 as part of the Padova Dialogues. The Conferences are sponsored by the Institute for Theoretical Computer Science, University at Lübeck, by the Division of Computer Science, Hokkaido University, Department of Information Engineering of the University of Padova, Yokohama National University, and the Research Institute on High Performance Computing and Networking of the Italian National Research Council (ICAR-CNR)
A Second-Order Perceptron Algorithm

We introduce a variant of the Perceptron algorithm called second-order Perceptron algorithm, which is able to exploit certain spectral properties of the data. We analyze the second-order Perceptron algorithm in the mistake bound model of on-line learning and prove bounds in terms of the eigenvalues of the Gram matrix created from the data. The performance of the second-order Perceptron algorithm is affected by the setting of a parameter controlling the sensitivity to the distribution of the eigenvalues of the Gram matrix. Since this information is not preliminarly available to on-line algorithms, we also design a refined version of the second-order Perceptron algorithm which adaptively sets the value of this parameter. For this second algorithm we are able to prove mistake bounds corresponding to a nearly optimal constant setting of the parameter.
Minimax regret under log loss for general classes of experts

We study sequential strategies for assigning probabilities to the elements that may appear next in a sequence of data. The goal is to minimize the regret under log loss over the worst possible sequence. That is, to minimize the worst-case drop in the log-likelihood of the final sequence when measured under the assigned probabilities, as opposed to being measured under the best assignment in a given class of strategies (or experts). Using tools from empirical process theory, we prove a general upper bound on the best possible (minimax) regret that depends on the metric properties of the class of experts. This extends previous results by Opper and Haussler. In the special case of parametric experts, we obtain nonasymptotical versions of results proven by Rissanen and others under much stronger conditions on the expert class. Finally, we point out a suboptimal behavior of the popular Bayesian weighted average algorithm.
On Bayes Methods for On-Line Boolean Prediction

We examine a general Bayesian framework for constructing on-line prediction algorithms in the experts setting. These algorithms predict the bits of an unknown Boolean sequence using the advice of a finite set of experts. In this framework we use probabilistic assumptions on the unknown sequence to motivate prediction strategies. However, the relative bounds that we prove on the number of prediction mistakes made by these strategies hold for any sequence. The Bayesian framework provides a unified derivation and analysis of previously known prediction strategies, such as the Weighted Majority and Binomial Weighting algorithms. Furthermore, it provides a principled way of automatically adapting the parameters of Weighted Majority to the sequence, in contrast to previous ad hoc doubling techniques. Finally, we discuss the generalization of our methods to algorithms making randomized predictions.
On Prediction of Individual Sequences

Sequential randomized prediction of an arbitrary binary sequence is investigated. No assumption is made on the mechanism of generating the bit sequence. The goal of the predictor is to minimize its relative loss, i.e., to make (almost) as few mistakes as the best ``expert'' in a fixed, possibly infinite, set of experts. We point out a surprising connection between this prediction problem and empirical process theory. First, in the special case of static (memoryless) experts, we completely characterize the minimax relative loss in terms of the maximum of an associated Rademacher process. Then we show general upper and lower bounds on the minimax relative loss in terms of the geometry of the class of experts. As main examples, we determine the exact order of magnitude of the minimax relative loss for the class of autoregressive linear predictors and for the class of Markov experts.
On Prediction of Individual Sequences

Sequential randomized prediction of an arbitrary binary sequence is investigated. No assumption is made on the mechanism of generating the bit sequence. The goal of the predictor is to minimize its relative loss (or regret), i.e., to make almost as few mistakes as the best “expert” in a fixed, possibly infinite, set of experts. We point out a surprising connection between this prediction problem and empirical process theory. First, in the special case of static (memoryless) experts, we completely characterize the minimax regret in terms of the maximum of an associated Rademacher process. Then we show general upper and lower bounds on the minimax regret in terms of the geometry of the class of experts. As main examples, we determine the exact order of magnitude of the minimax regret for the class of autoregressive linear predictors and for the class of Markov experts.
How to use expert advice

We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictins. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We then show how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context. We also compare our analysis to the case in which log loss is used instead of the expected number of mistakes.
Recent Results in On-line Prediction and Boosting

The successful design of practical algorithms for solving a class of problems very often depends on the existence of a formal model where algorithmical ideas can be developed, analyzed, and compared. In the case of machine learning, a number of such formal models have been proposed in the past. Some of them have been successful in generating elegant mathematical results but, on the other hand, they have had a rather limited impact on the practical side. In this paper, we suggest that the on-line prediction model is a good source of interesting algorithmic ideas with a great potential for new applications. To this end, we will describe a simple algorithm based on “multiplicative weights,” we will analyze this algorithm within the on-line prediction model, and finally we will show some of its variants and applications.
Noise-tolerant learning near the information-theoretic bound

Nicolb Cesa-Bianchi Eli Dichterman DSI, Universit~ di Milano Department of Computer Science Via Comelico 39, Technion 1-20135 Milano, Italy Haifa 32000, Israel cesabian@dsi .u.nimi. it eli@cs. technion. ac. il Paul Fischer Hans Ulrich Simon Lehrstuhl Informatik II Universitat Dortmund D-44221 Dortmund, Germany {paulf, simon}@goedel. inf ormat ik. uni-dortmund. de We investigate the sample size necessary for PAC learning in the presence of malicious noise, a type of adversarial noise model introduced by Kearns and Li. We prove the first nontrivial sample complexity lower bound in this model by showing that order of &/A2 + d/A examples are necessary for PAC learning any target class of {O, 1}-valued functions of VC dimension d, where e is the desired accuracy and q = &/(1 + e) – A the malicious noise rate (it is well known that any nontrivial target class cannot be PAC learned with accuracy E and malicio-us noise rate q > &/(1 + &), this irrespective to sample complexity.) This result cannot be significantly improved in general. In fact, we show a learning algorithm for the same noise model that. for each d. learns the class of all subsets of d elements using a number of examples of the same order as that proven necessary by our lower bound (disregarding logarithmic factors). In contrast, we show that to learn any target class of VC-dimension d in the presence of a high malicious noise rate ~ (i.e. A = o(s)), the popular strategy choosing any hypothesis that minimizes disagreements on the sample needs fl(de/A2 ) examples. This implies that, for high noise rate and for any target class of VC-dimension large enough, there are distributions over the target domain where the minimum disagreement strategy is outperformed by our algorithm. Permiaaion to make digital/hard copies of all or pati of tlds material for personal or classroom use is granted without fee provided that the copies are not made or dktributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copyright is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers or to redkibute to lists, requires specific permission and/or fee. STOC’96, Philadelphia PA,USA ~ 1996 ACM &89791-785.5/96/05. .$3.50
Worst-case quadratic loss bounds for prediction using linear functions and gradient descent

Studies the performance of gradient descent (GD) when applied to the problem of online linear prediction in arbitrary inner product spaces. We prove worst-case bounds on the sum of the squared prediction errors under various assumptions concerning the amount of a priori information about the sequence to predict. The algorithms we use are variants and extensions of online GD. Whereas our algorithms always predict using linear functions as hypotheses, none of our results requires the data to be linearly related. In fact, the bounds proved on the total prediction loss are typically expressed as a function of the total loss of the best fixed linear predictor with bounded norm. All the upper bounds are tight to within constants. Matching lower bounds are provided in some cases. Finally, we apply our results to the problem of online prediction for classes of smooth functions.
Tight bounds on the cumulative profit of distributed voters

Packaging apparatus for making vacuum or gas-filled packages of the type including a flanged cup-shaped receptacle with a closure film sealed to the flanges and stretched down into the cup to engage and press against the product. The apparatus comprises a first packaging station where the film is sealed to the cup flanges part way around the cup mouth; simultaneously the film is heated in pre-selected locations to soften it for subsequent stretching. In a subsequent station, the partially-completed package is placed in a vacuum chamber and evacuated. Thereafter, a plug is driven against the still heated film, to force it down into the cup interior adjacent the product. Before or after the plug movement, the film is fully sealed to the cup, to make a hermetically-sealed package. While the plug holds the film in its stretched condition, the spaces outside of the film are vented to apply fluid pressure to the film, to cause the film to conform closely to the product shape, and to match closely the contour of the cup.
La musique et les lettres chez Barthes

Dans ses ecrits sur la musique, des l'epoque des Mythologies et jusqu'a la fin de sa vie, Barthes repete le geste symboliste, mallarmeen, qui consiste a definir la litterature (voire l'art en general) a travers les caracteristiques propres a la musique. La musique serait un phenomene sensible, inconcevable en dehors de son rapport au corps, et qui ne peut s'epuiser dans le mouvement de la signification ; de meme la litterature. L'analyse de ce geste aide a voir comment et pourquoi Barthes maintient sa foi en l'existence d'un art haut (par opposition a l'art bourgeois), en la litterature (par opposition au discours non litteraire), en une 'essence' du chant ou de la photographie. Mais si la litterature, chez Barthes, se definit a travers une analogie avec la musique, l'inverse est tout aussi vrai : la musique est dite lettre, texte, prosodie ; Barthes affirme qu'il faut que le chant ecrive. En effet, la critique barthesienne doit evaluer chaque art en fonction de ce qu'il n'est pas ; car 's'il y a une signification des phenomenes sensibles, c'est toujours dans le deplacement, la substitution, bref, en fin de compte, l'absence, qu'elle se manifeste avec le plus d'eclat' ('Le Chant romantique').
De La Traduction En Musique Chez Baudelaire

Baudelaire seems, in his essay on Wagner, to affirm that music (or at least, Wagner's music) can translate positive ideas, and that this can be demonstrated by analysis of the similarities between the reactions of different people to a given musical work. However, he also consistently undermines his own demonstration: the implication is always present that perceived translation into and out of music is never independent of extra-musical suggestion; and it is always also possible, thanks to the constant duplicity of Baudelaire's syntax, to interpret the message apparently conveyed by music, not as a positive and specific one, but as the absolutely general idea of art conceived as a universal. In this way, the relationship between music and letters becomes the indescribable but necessary bridge between the positive and the absolute, or between the real and the ideal; and the Baudelairean doctrine of 'correspondances' may be re-interpreted as the means of maintaining that bridge.
A Tutorial on Learning with Bayesian Networks

A Bayesian network is a graphical model that encodes probabilistic relationships among variables of interest. When used in conjunction with statistical techniques, the graphical model has several advantages for data analysis. One, because the model encodes dependencies among all variables, it readily handles situations where some data entries are missing. Two, a Bayesian network can be used to learn causal relationships, and hence can be used to gain understanding about a problem domain and to predict the consequences of intervention. Three, because the model has both a causal and probabilistic semantics, it is an ideal representation for combining prior knowledge (which often comes in causal form) and data. Four, Bayesian statistical methods in conjunction with Bayesian networks offer an efficient and principled approach for avoiding the overfitting of data. In this paper, we discuss methods for constructing Bayesian networks from prior knowledge and summarize Bayesian statistical methods for using data to improve these models. With regard to the latter task, we describe methods for learning both the parameters and structure of a Bayesian network, including techniques for learning with incomplete data. In addition, we relate Bayesian-network methods for learning to techniques for supervised and unsupervised learning. We illustrate the graphical-modeling approach using a real-world case study.
The First Conference on E-mail and Anti-Spam

The First Conference on E-mail and Anti-Spam was held from July 30 to July 31, 2004 in Mountain View, California. The conference, attended by 180 researchers, featured 29 papers that covered a number of topics, including e-mail in general, nonstatistical techniques for stopping spam, machine learning techniques, issues of identity in e-mail, as well as law and policy. The 2005 conference will be held at Stanford University from July 21 to 22.
On the Path to an Ideal ROC Curve: Considering Cost Asymmetry in Learning Classifiers

Receiver Operating Characteristic (ROC) curves are a standard way to display the performance of a set of binary classifiers for all feasible ratios of the costs associated with false positives and false negatives. For linear classifiers, the set of classifiers is typically obtained by training once, holding constant the estimated slope and then varying the intercept to obtain a parameterized set of classifiers whose performances can be plotted in the ROC plane. In this paper, we consider the alternative of varying the asymmetry of the cost function used for training. We show that the ROC curve obtained by varying the intercept and the asymmetry—and hence the slope—always outperforms the ROC curve obtained by varying only the intercept. In addition, we present a path-following algorithm for the support vector machine (SVM) that can compute efficiently the entire ROC curve, that has the same computational properties as training a single classifier. Finally, we provide a theoretical analysis of the relationship between the asymmetric cost model assumed when training a classifier and the cost model assumed in applying the classifier. In particular, we show that the mismatch between the step function used for testing and its convex upper bounds usually used for training leads to a provable and quantifiable difference around extreme asymmetries.
HLA-driven optimization of an HIV vaccine immunogen

HIV diversity has been driven in large part by the intense selective pressure of HLA-restricted immune responses and is a significant challenge in HIV vaccine design. Sites of HLA-associated polymorphisms indicate potential immunogenic peptides that should be incorporated into an HIV vaccine. 
 
 Full-length (pretreatment) HIV sequencing and high-resolution HLA-A, -B, and -C genotyping was undertaken on 245 individuals in the Western Australian HIV Cohort Study. We determined statistically significant associations between polymorphisms in HIV sequences and HLA genotypes. 
 
Given these HLA associations we consider alternative measures of protection on the basis of the match between a viral peptide sequence and a corresponding segment of the vaccine. The measure is defined for all overlapping HIV peptides in the dataset. Each peptide contains a putative epitope and its associated flanking region. The vaccine is said to protect against a peptide sequence if the sites of HLA association in both the peptide sequence and the corresponding segment of the vaccine have nonescaped amino acids, and one of the following three criteria hold: (1), "no play"— the remaining sites in the peptide sequence and corresponding segment of the vaccine match exactly, (2), "mid-play"— the remaining sites in the sequence and vaccine differ only by conservative amino-acid substitutions, and (3) "full-play"—the remaining sites in the sequence and vaccine need have no relationship.The three criteria represent different assumptions about the degree to which T cells cross-react. An optimal vaccine immunogen of a given length is the one that contains the largest number of (possibly overlapping) protected against peptides. We provide a general machine-learning approach to optimization of such immunogens. 
 
 We optimized vaccines of length up to 2000 aa. The predicted efficacy of the optimized vaccine immunogens depends considerably on which criterion is used. For instance, an optimized vaccine immunogen of length 1300aa can protect against all peptides in the data under the full-play assumption, compared with 80% of all peptides under the mid-play assumption and 65% under the no-play assumption. 
 
 These data demonstrate a novel, rational approach to optimizing the immunogenicity of an HIV vaccine against diverse circulating viruses in a human population, guided by knowledge of the population HLA.
Using ``epitomes'' to model genetic diversity: Rational design of HIV vaccine cocktails

We introduce a new model of genetic diversity which summarizes a large input dataset into an epitome, a short sequence or a small set of short sequences of probability distributions capturing many overlapping subsequences from the dataset. The epitome as a representation has already been used in modeling real-valued signals, such as images and audio. The discrete sequence model we introduce in this paper targets applications in genetics, from multiple alignment to recombination and mutation inference. In our experiments, we concentrate on modeling the diversity of HIV where the epitome emerges as a natural model for producing relatively small vaccines covering a large number of immune system targets known as epitopes. Our experiments show that the epitome includes more epitopes than other vaccine designs of similar length, including cocktails of consensus strains, phylogenetic tree centers, and observed strains. We also discuss epitome designs that take into account uncertainty about T-cell cross reactivity and epitope presentation. In our experiments, we find that vaccine optimization is fairly robust to these uncertainties.
Efficient approximations for learning phylogenetic HMM models from data

We consider models useful for learning an evolutionary or phylogenetic tree from data consisting of DNA sequences corresponding to the leaves of the tree. In particular, we consider a general probabilistic model described in Siepel and Haussler that we call the phylogenetic-HMM model which generalizes the classical probabilistic models of Neyman and Felsenstein. Unfortunately, computing the likelihood of phylogenetic-HMM models is intractable. We consider several approximations for computing the likelihood of such models including an approximation introduced in Siepel and Haussler, loopy belief propagation and several variational methods.



We demonstrate that, unlike the other approximations, variational methods are accurate and are guaranteed to lower bound the likelihood. In addition, we identify a particular variational approximation to be best-one in which the posterior distribution is variationally approximated using the classic Neyman-Felsenstein model. The application of our best approximation to data from the cystic fibrosis transmembrane conductance regulator gene region across nine eutherian mammals reveals a CpG effect.