nils-herrmann/clean_scirepeval huggingface dataset:
The Mixture Approach to Universal Model Selection

We build a model selection algorithm which has a mean Kullback risk upper bounded by the mean risk for the best model applied to half the sample augmented by an explicit penalty term of order one over the sample size. This estimator is not a \true" selection rule, but instead an adaptive convex combination of the models: this mixture approach is inspired by the context tree weighting method of information theory by Willems, Shtarkov and Tjalkens [6, 7], which is a \universal" data compression algorithm for stationary binary sources. Our algorithm is \universal" with respect to the statistical mean Kullback risk in the sense that it is almost optimal for any exchangeable sample distribution. We give an application to the estimation of a probability measure by adaptive histograms. We detail a factorised computation of the mixture which weights M models performing a number of operations of order log(M), when the subdivisions underlying the histograms have nested cells. The end of the paper shows that in the case of a dense family of models, a true selection rule can be built in a second step. We give an upper bound for the mean square Hellinger distance of the estimator from the sample distribution, which tends to zero at the optimal rate, up to an explicit multiplicative constant, in the case when the square Hellinder distance and the Kullback divergence are comparable.
Metropolis, Simulated Annealing, and Iterated Energy Transformation Algorithms: Theory and Experiments

In this paper, we compare from the theoretical and experimental points of view three stochastic optimization algorithms: the Metropolis, simulated annealing, and iterated energy transformation algorithms. We give the optimal exponents for the concentration of the marginal distribution of the final state of these algorithms around the global minima of the virtual energy function. Experiments are performed on an N.P. complete benchmark which tries to retain the main aspects of scheduling problems. They lead to the same qualitative ranking of algorithms as the theory does.
The Legendre transform of two replicas of the Sherrington-Kirkpatrick spin glass model

SummaryWe prove a variational inequality linking the values of the free energy per site at different temperatures. This inequality is based on the Legendre transform of the free energy of two replicas of the system. We prove that equality holds whenβ≤1/
$$\sqrt 2 $$
 and fails when 1/
$$\sqrt 2 $$
<β≤1. We deduce from this that the mean entropy per site of the uniform distribution with respect to the distribution of the coupling σi1σi2=ψi between two replicas is null when 0≤β≤1/
$$\sqrt 2 $$
 and strictly positive when 1/
$$\sqrt 2 $$
<β≤1. We exhibit thus a new secondary critical phenomenon within the high temperature region 0≤β≤1. We given an interpretation of this phenomenon showing that the fluctuations of the law of the coupling with the interactions remains strong in the thermodynamic limit whenβ>1/
$$\sqrt 2 $$
. We also use our inequality numerically within the low temperature region to improve (slightly) the best previously known lower bounds for the free energy and the ground state energy per site.
Provably Secure Steganography

Steganography is the problem of hiding secret messages in "innocent-lookingrdquo public communication so that the presence of the secret messages cannot be detected. This paper introduces a cryptographic formalization of steganographic security in terms of computational indistinguishability from a channel, an indexed family of probability distributions on cover messages. We use cryptographic and complexity-theoretic proof techniques to show that the existence of one-way functions and the ability to sample from the channel are necessary conditions for secure steganography. We then construct a steganographic protocol, based on rejection sampling from the channel, that is provably secure and has nearly optimal bandwidth under these conditions. This is the first known example of a general provably secure steganographic protocol. We also give the first formalization of "robustrdquo steganography, where an adversary attempts to remove any hidden messages without unduly disrupting the cover channel. We give a necessary condition on the amount of disruption the adversary is allowed in terms of a worst case measure of mutual information. We give a construction that is provably secure and computationally efficient and has nearly optimal bandwidth, assuming repeatable access to the channel distribution.
Suboptimal behavior of Bayes and MDL in classification under misspecification

We show that forms of Bayesian and MDL inference that are often applied to classification problems can be inconsistent. This means that there exists a learning problem such that for all amounts of data the generalization errors of the MDL classifier and the Bayes classifier relative to the Bayesian posterior both remain bounded away from the smallest achievable generalization error. From a Bayesian point of view, the result can be reinterpreted as saying that Bayesian inference can be inconsistent under misspecification, even for countably infinite models. We extensively discuss the result from both a Bayesian and an MDL perspective.
Weighted One-Against-All

The one-against-all reduction from multiclass classification to binary classification is a standard technique used to solve multiclass problems with binary classifiers. We show that modifying this technique in order to optimize its error transformation properties results in a superior technique, both experimentally and theoretically. This algorithm can also be used to solve a more general classification problem "multi-label classification," which is the same as multiclass classification except that it allows multiple correct labels for a given example.
Error limiting reductions between classification tasks

We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ε then the cost-sensitive classifier has cost at most 2ε times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning.
A comparison of tight generalization error bounds

We investigate the empirical applicability of several bounds (a number of which are new) on the true error rate of learned classifiers which hold whenever the examples are chosen independently at random from a fixed distribution.The collection of tricks we use includes:1. A technique using unlabeled data for a tight derandomization of randomized bounds.2. A tight form of the progressive validation bound.3. The exact form of the test set bound.The bounds are implemented in the semibound package and are freely available.
Relating reinforcement learning performance to classification performance

We prove a quantitative connection between the expected sum of rewards of a policy and binary classification performance on created subproblems. This connection holds without any unobservable assumptions (no assumption of independence, small mixing time, fully observable states, or even hidden states) and the resulting statement is independent of the number of states or actions. The statement is critically dependent on the size of the rewards and prediction performance of the created classifiers.We also provide some general guidelines for obtaining good classification performance on the created subproblems. In particular, we discuss possible methods for generating training examples for a classifier learning algorithm.
Tutorial on Practical Prediction Theory for Classification

We discuss basic prediction theory and its impact on classification success evaluation, implications for learning algorithm design, and uses in learning algorithm execution. This tutorial is meant to be a comprehensive compilation of results which are both theoretically rigorous and quantitatively useful.There are two important implications of the results presented here. The first is that common practices for reporting results in classification should change to use the test set bound. The second is that train set bounds can sometimes be used to directly motivate learning algorithms.
Sensitive Error Correcting Output Codes

We present a reduction from cost-sensitive classification to binary classification based on (a modification of) error correcting output codes. The reduction satisfies the property that e regret for binary classification implies l 2 -regret of at most 2e for cost estimation. This has several implications: 1. Any regret-minimizing online algorithm for 0/1 loss is (via the reduction) a regret-minimizing online cost-sensitive algorithm. In particular, this means that online learning can be made to work for arbitrary (i.e., totally unstructured) loss functions. 2. The output of the reduction can be thresholded so that e regret for binary classification implies at most 4√∈Z regret for cost-sensitive classification where Z is the expected sum of costs. 3. For multiclass problems, e binary regret translates into l 2 -regret of at most 4e in the estimation of class probabilities. For classification, this implies at most 4√∈ multiclass regret.
Covert two-party computation

We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs xA and xB respectively, to compute a function f(xA,xB) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(xA,xB) only when it equals a certain value of interest (such as "Yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xA,xB) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the "honest but curious" model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.
An objective evaluation criterion for clustering

We propose and test an objective criterion for evaluation of clustering performance: How well does a clustering algorithm run on unlabeled data aid a classification algorithm? The accuracy is quantified using the PAC-MDL bound  in a semisupervised setting. Clustering algorithms which naturally separate the data according to (hidden) labels with a small number of clusters perform well. A simple extension of the argument leads to an objective model selection method. Experimental results on text analysis datasets demonstrate that this approach empirically results in very competitive bounds on test set performance on natural datasets.
An iterative method for multi-class cost-sensitive learning

Cost-sensitive learning addresses the issue of classification in the presence of varying costs associated with different types of misclassification. In this paper, we present a method for solving multi-class cost-sensitive learning problems using any binary classification algorithm. This algorithm is derived using hree key ideas: 1) iterative weighting; 2) expanding data space; and 3) gradient boosting with stochastic ensembles. We establish some theoretical guarantees concerning the performance of this method. In particular, we show that a certain variant possesses the boosting property, given a form of weak learning assumption on the component binary classifier. We also empirically evaluate the performance of the proposed method using benchmark data sets and verify that our method generally achieves better results than representative methods for cost-sensitive learning, in terms of predictive performance (cost minimization) and, in many cases, computational efficiency.
Subject index

Ablabesmyia, 301 Abramis, 57,261,277 absorption, 227 Acalyptonotus, 293 Acanthocyclops, 1 8 1 Acari, 29,293,301 Achnanthes, 39,205,283 acidification, 223 Acipenser, 57 acoustic current profiler, 117 Acroperus, 18 1 Actinoptychus, 205 active radar techniques, 227 Aeolosoma, 29 agricultural loading, 1 agriculture. 1,2 1 7 air pollution, 223 aidwater interface, 227 Alburnus, 57,277 algal bloom, 149 Alona, 29, 18 1,283 Alonella, 181,283 Alonopsis, 1 8 1 aluminium, 241 Amphichaeta, 29 Amphipoda, 23,29,39, 187,293 Amphiprora, 205 Amphora, 199 Anabaena, 9,39,149,261,42 Ancylus Lake, 199,205 Anguilla, 57 anionic detergenl, 1 43 Annelids, 29 Anuraeopsis, 18 1 AOX simulation, 1 17 Aphanizomenon, 9,39,149,255,261,267 Arcteonais, 29,301 ARIMA-processes, 99 Arrenurus, 293 Artemisia, 199 Ascomorpha, 18 1 Asellus, 39,49,  Atlantic salmon, 57 atmospheric moisture, 227 Atractides, 293 Attheyella, 29 Aulacoseira, 9,23,39,199,205,261,267,283 Aulodrilus, 29
Computable Shell Decomposition Bounds

Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase transitions. Here we use a variant of their ideas to derive an upper bound on the generalization error of a hypothesis computable from its training error and the histogram of training errors for the hypotheses in the class. In most cases this new bound is significantly tighter than traditional bounds computed from the training error and the cardinality of the class. Our results can also be viewed as providing a rigorous foundation for a model selection algorithm proposed by Scheffer and Joachims.
Microchoice Bounds and Self Bounding Learning Algorithms

A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we demonstrate new adaptive bounds designed for learning algorithms that operate by making a sequence of choices. These bounds, which we call Microchoice bounds, are similar to Occam-style bounds and can be used to make learning algorithms self-bounding in the style of Freund (1998). We then show how to combine these bounds with Freund's query-tree approach producing a version of Freund's query-tree structure that can be implemented with much more algorithmic efficiency.
Lessons from learning theory for benchmark design

This discussion/tutorial consists of a few short discussions on the (theoretical) trade-offs of various choices in constructing benchmarks. Most of the results discussed here are "common sense" at high level. However, all of this "common sense" is (to some extent) quantifiable common sense, and occasionally that quantification is useful. These short discussions cover: 1) Prediction Domains & Loss functions, 2) Prediction settings, 3) Assumption Failures.
MACHINE LEARNING REDUCTIONS

1. Why Reductions? Charlie and Susan1 each have a problem to solve: given information from car sensors, predict if a car repair is required before the car fails. Some standard characteristics of this problem include: (1) Dependent data. Sensor values are correlated in time. (2) Very rare events. Most of the time, cars don't fail, so data drawn from the natural measure will have only a small portion representing car failures. (3) Varying value events. Having the third rear brake light fail ( x at next opportunity ) is not nearly as catastrophic as a blowout ( stop the car RIGHT NOW ). Charlie solves the problem directly. He considers the problem carefully, constructing and tuning a model making predictions about car failures given the sensory inputs from a large number of examples. Charlie works for several years on this, and eventually gets a system that works reasonably well. Susan solves the problem indirectly. She rst notices that the problem is an instance of cost sensitive learning with dependent data. She applies a reduction from cost sensitive learning to classi cation, tries a few classi cation algorithms, and picks the best. Susan spends only a week, producing a system that works reasonably well. Susan's method (an advanced machine learning approach) is much faster, requires much less training, takes advantage of past work by many researchers, and is easily veri ed. Charlie's method (a statistics-like approach) is surer and might be superior in the long run (or not. What if Charlie's sensors are obsolete by the time he succeeds?). Reductions naturally aid Susan's method in several ways.
CAPTCHA: Using Hard AI Problems for Security

We introduce captcha, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a captcha can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of captchas. Since captchas have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of AI problems that can be used to construct captchas and we show that solutions to such problems can be used for steganographic communication. captchas based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
Exploration in Metric State Spaces

We present metric-E3, a provably near-optimal algorithm for reinforcement learning in Markov decision processes in which there is a natural metric on the state space that allows the construction of accurate local models. The algorithm is a generalization of the E3 algorithm of Kearns and Singh, and assumes a black box for approximate planning. Unlike the original E3, metric-E 3 finds a near optimal policy in an amount of time that does not directly depend on the size of the state space, but instead depends on the covering number of the state space. Informally, the covering number is the number of neighborhoods required for accurate local modeling.
Cost-sensitive learning by cost-proportionate example weighting

We propose and evaluate a family of methods for converting classifier learning algorithms and classification theory into cost-sensitive algorithms and theory. The proposed conversion is based on cost-proportionate weighting of the training examples, which can be realized either by feeding the weights to the classification algorithm (as often done in boosting), or by careful subsampling. We give some theoretical performance guarantees on the proposed methods, as well as empirical evidence that they are practical alternatives to existing approaches. In particular, we propose costing, a method based on cost-proportionate rejection sampling and ensemble aggregation, which achieves excellent predictive performance on two publicly available datasets, while drastically reducing the computation required by other methods.
Reducing T-step reinforcement learning to classifica-tion

A photographic element comprising a glass support and a photosensitive emulsion layer on said support comprising a film-forming proteinaceous colloid is described. The adherence of the emulsion layer to the glass support is enhanced by including the emulsion layer an organic silicon compound having hydrocarbon groups directly or indirectly attached to a silicon atom wherein at least one of the hydrocarbon groups carries a group or atom which has chemical affinity for the free reactive groups of the proteinaceous colloid or which can be cross-linked to the free reactive groups through the intermediary of a cross-linking agent. The adherence of the photosensitive emulsion layer to the glass support is enhanced without affecting the photosensitive properties of the emulsion layer.
Correlated equilibria in graphical games

We examine correlated equilibria in the recently introduced formalism of graphical games, a succinct representation for multiplayer games. We establish a natural and powerful relationship between the graphical structure of a multiplayer game and a certain Markov network representing distributions over joint actions. Our first main result establishes that this Markov network succinctly represents all correlated equilibria of the graphical game up to expected payoff equivalence. Our second main result provides a general algorithm for computing correlated equilibria in a graphical game based on its associated Markov network. For a special class of graphical games that includes trees, this algorithm runs in time polynomial in the graphical game representation (which is polynomial in the number of players and exponential in the graph degree).
Telling Humans and Computers Apart Automatically or How Lazy Cryptographers do AI

If you try to get a new email account at Yahoo, you’ll be asked to prove that you’re a human and not a computer. Why? Because a single computer program can get thousands of free email accounts per second. And that’s bad for Yahoo. But how do you prove to a computer that you’re a human? Proving that you’re a human to another human can be done using an idea from the 1950s: the Turing Test [11]. A human judge asks you a bunch of questions and decides, depending on your answers, whether he’s talking to a human or a computer. Proving that you’re a human to a computer is another matter. It requires a test (or a set of tests) that computers can grade, humans can pass, but paradoxically, computers can’t pass. In our lingo, it requires a captcha.
Provably secure steganography: (Extended abstract)

Informally, steganography is the process of sending a secret message from Alice to Bob in such a way that an eavesdropper (who listens to all communications) cannot even tell that a secret message is being sent. In this work, we initiate the study of steganography from a complexity-theoretic point of view. We introduce definitions based on computational indistinguishability and we prove that the existence of one-way functions implies the existence of secure steganographic proto- cols.
Non-Parametric Fault Identification for Space R overs

Autonomous fault detection is prerequisite for autonomous system repair which is of great value for spacecraft where human intervention is expensive, slow, unreliable, and occasionally impossible. We present a method which successfully achieves autonomous fault detection in simulation. The approach uses a nonparametric estimate of the system state updated based upon sensor measurements. Our system does state estimation using a decision-theoretic generalization of particle filters which takes into account the difference in utility of fault detection vs. fault nondetection.