nils-herrmann/clean_scirepeval huggingface dataset:
New Inference Concepts for Analysing Complex Data 2797 Workshop : New Inference Concepts for Analysing Complex Data Table of Contents

The main purpose of this workshop was to assemble international leaders from statistics and machine learning to identify important research problems, to cross-fertilize between the disciplines, and to ultimately start coordinated research efforts toward better solutions. The workshop focused on discussing modern methods for analysis complex high dimensional data with applications to econometrics, finance, biomedicine, genomics etc.  This meeting was well attended with about 45 participants with broad geographic representation from all continents. This workshop was a nice blend of researchers with various backgrounds from the areas of statistics and machine learning. The main purpose of this workshop was to assemble international leaders from statistics and machine learning in the Institute: to identify important research problems, to cross-fertilize between the disciplines, and to ultimately start coordinated research efforts towards better solutions. The program included more than 25 talks organized in sections on various topics: Support Vector Machines (B. Schölkopf, A.J. Smola, G.Wahba), mathematical finance (H. Dette, W. Härdle, S.X. Chen), dimension reduction (Y. Xia, A. Dalalyan, M. Kawanabe, E. Mammen, H. H. Zhang), non-parametric smoothing (D. Belomestny, J. Polzehl), Boosting (P. Bühlmann, Y. Ritov), genomics (A. Nobel, Hepping Zhang), classification (S. van de Geer, G. Blanchard), statistical inverse problem (M. Reiss, A. Goldenshluger), Functional regression (H.-G. Müller, 2796 Oberwolfach Report 52/2004 T.Cai), Clustering (J. M. Buhmann, A. Nobel) among others. P. Bühlmann gave an overview on statistical methods of boosting while D. Yekutieli made an extended presentation on False Discovery Rate. There was one organized discussion on Smoothing methods in classification. The workshop gave an excellent opportunity for exchanging the opinions and expertise as well as for discussing various topics in different areas of modern mathematical statistics and machine learning theory. The discussion revealed a lot of common ideas and principles in these two fields but also differences in the methodology and approaches. An exchange of ideas can clearly contribute to the both fields. Already during workshop some new projects were originated that involve both statisticians and people from machine learning society. The workshop was attended by a number of young statisticians and gave an excellent opportunity for training: both by attending the high level presentation, by presenting their own results and by participating at the numerous informal discussions. New Inference Concepts for Analysing Complex Data 2797 Workshop: New Inference Concepts for Analysing Complex Data
Hierarchical Testing Designs for Pattern Recognition This Reprint Differs from the Original in Pagination and Typographic Detail. 1 2

We explore the theoretical foundations of a " twenty questions " approach to pattern recognition. The object of the analysis is the computational process itself rather than probability distributions (Bayesian inference) or decision boundaries (statistical learning). Our formulation is motivated by applications to scene interpretation in which there are a great many possible explanations for the data, one (" background ") is statistically dominant, and it is imperative to restrict intensive computation to genuinely ambiguous regions. The focus here is then on pattern filtering: Given a large set Y of possible patterns or explanations, narrow down the true one Y to a small (random) subset Y ⊂ Y of " detected " patterns to be subjected to further, more intense, processing. To this end, we consider a family of hypothesis tests for Y ∈ A versus the nonspecific alternatives Y ∈ A c. Each test has null type I error and the candidate sets A ⊂ Y are arranged in a hierarchy of nested partitions. These tests are then characterized by scope (|A|), power (or type II error) and algorithmic cost. We consider sequential testing strategies in which decisions are made iteratively, based on past outcomes, about which test to perform next and when to stop testing. The set Y is then taken to be the set of patterns that have not been ruled out by the tests performed. The total cost of a strategy is the sum of the " testing cost " and the " postprocessing cost " (proportional to | Y |) and the corresponding optimization problem is analyzed. As might be expected, under mild assumptions good designs for sequential testing strategies exhibit a steady progression from broad scope coupled with low power to high power coupled with dedication to specific explanations. In the assumptions ensuring this property a key role is played by the ratio cost/power. These ideas are illustrated in the context of detecting rectangles amidst clutter. 1.  Motivated by problems in machine perception, specifically scene interpretation, we investigate the theoretical foundations of an approach to pattern recognition based on adaptive sequential testing. The basic scenario is familiar to everybody—identify one " pattern " (or " explanation ") from among many by posing a sequence of subset questions. In other words, play a game of " twenty questions. " Intuitively, we should ask more and more precise questions, progressing from general ones which " …
On the Rate of Convergence of Regularized Boosting Classifiers

A regularized boosting method is introduced, for which regularization is obtained through a penalization function. It is shown through oracle inequalities that this method is model adaptive. The rate of convergence of the probability of misclassification is investigated. It is shown that for quite a large class of distributions, the probability of error converges to the Bayes risk at a rate faster than n-(V+2)/(4(V+1)) where V is the VC dimension of the "base" class whose elements are combined by boosting methods to obtain an aggregated classifier. The dimension-independent nature of the rates may partially explain the good behavior of these methods in practical problems. Under Tsybakov's noise condition the rate of convergence is even faster. We investigate the conditions necessary to obtain such rates for different base classes. The special case of boosting using decision stumps is studied in detail. We characterize the class of classifiers realizable by aggregating decision stumps. It is shown that some versions of boosting work especially well in high-dimensional logistic additive models. It appears that adding a limited labelling noise to the training data may in certain cases improve the convergence, as has been also suggested by other authors.
Generalization Error Bounds for Aggregate Classifiers

The use of multiple classifiers has raised much interest in the statistical learning community in the past few years. The basic principle of multiple classifiers algorithms, also called aggregation or ensemble or voting methods, is to construct, according to some algorithm, several (generally a few dozens) different classifiers belonging to a certain family (e.g. support vector machines, classification trees, neural nets...). The “aggregate” classifier is then obtained by majority vote among the outputs of the single constructed classifiers once they are presented a new instance. For some algorithms the majority vote is replaced by a weighted vote, with weights prescribed by the aggregation algorithm. Classical references about this kind of methods include [2, 3, 9, 8, 12, 14, 19].
Towards a Statistical Theory of Clustering

The goal of this paper is to discuss statistical aspects of clus- tering in a framework where the data to be clustered has been sampled from some unknown probability distribution. Firstly, the clustering of the data set should reveal some structure of the underlying data rather than model artifacts due to the random sampling process. Secondly, the more sample points we have, the more reliable the clustering should be. We discuss which methods can and cannot be used to tackle those prob- lems. In particular we argue that generalization bounds as they are used in statistical learning theory of classification are unsuitable in a general clustering framework. We suggest that the main replacements of general- ization bounds should be convergence proofs and stability considerations. This paper should be considered as a road map paper which identifies im- portant questions and potentially fruitful directions for future research about statistical clustering. We do not attempt to present a complete statistical theory of clustering.
A new measure for the study of on-line algorithms

An accepted measure for the performance of an on-line algorithm is the “competitive ratio“ introduced by Sleator and Tarjan. This measure is well motivated and has led to the development of a mathematical theory for on-line algorithms.We investigate the behavior of this measure with respect to memory needs and benefits of lookahead and find some counterintuitive features. We present lower bounds on the size of memory devoted to recording the past. It is also observed that the competitive ratio reflects no improvement in the performance of an on-line algorithm due to any (finite) amount of lookahead.We offer an alternative measure that exhibits a different and, in some respects, more intuitive behavior. In particular, we demonstrate the use of our new measure by analyzing the tradeoff between the amortized cost of on-line algorithms for the paging problem and the amount of lookahead available to them. We also derive on-line algorithms for theK-server problem on any bounded metric space, which, relative to the new measure, are optimal among all on-line algorithms (up to a factor of 2) and are within a factor of 2K from the optimal off-line performance.
Nonparametric change detection in 2D random sensor field

The problem of detecting changes from data collected from a large-scale randomly deployed 2D sensor field is considered. Under a nonparametric change detection framework, we propose detection algorithms using two measures of change. The theoretical performance guarantee is derived from the Vapnik-Chervonenkis theory. By exploiting the structures of the search domain, we design a suboptimal recursive algorithm to detect the area of largest change which, for M sample points, runs in time O(M/sup 2/logM) (compared to an O(M/sup 4/) required for a straightforward exhaustive search). The lost of performance diminishes as M increases.
Self-Directed Learning and Its Relation to the VC-Dimension and to Teacher-Directed Learning

We study the self-directed (SD) learning model. In this model a learner chooses examples, guesses their classification and receives immediate feedback indicating the correctness of its guesses. We consider several fundamental questions concerning this model: the parameters of a task that determine the cost of learning, the computational complexity of a student, and the relationship between this model and the teacher-directed (TD) learning model. We answer the open problem of relating the cost of self-directed learning to the VC-dimension by showing that no such relation exists. Furthermore, we refute the conjecture that for the intersection-closed case, the cost of self-directed learning is bounded by the VC-dimension. We also show that the cost of SD learning may be arbitrarily higher that that of TD learning.Finally, we discuss the number of queries needed for learning in this model and its relationship to the number of mistakes the student incurs. We prove a trade-off formula showing that an algorithm that makes fewer queries throughout its learning process, necessarily suffers a higher number of mistakes.
VC-Dimension Analysis of Object Recognition Tasks

We analyze the amount of data needed to carry out various model-based recognition tasks in the context of a probabilistic data collection model. We focus on objects that may be described as semi-algebraic subsets of a Euclidean space. This is a very rich class that includes polynomially described bodies, as well as polygonal objects, as special cases. The class of object transformations considered is wide, and includes perspective and affine transformations of 2D objects, and perspective projections of 3D objects.We derive upper bounds on the number of data features (associated with non-zero spatial error) which provably suffice for drawing reliable conclusions. Our bounds are based on a quantitative analysis of the complexity of the hypotheses class that one has to choose from. Our central tool is the VC-dimension, which is a well-studied parameter measuring the combinatorial complexity of families of sets. It turns out that these bounds grow linearly with the task complexity, measured via the VC-dimension of the class of objects one deals with. We show that this VC-dimension is at most logarithmic in the algebraic complexity of the objects and in the cardinality of the model library.Our approach borrows from computational learning theory. Both learning and recognition use evidence to infer hypotheses but as far as we know, their similarity was not exploited previously. We draw close relations between recognition tasks and a certain learnability framework and then apply basic techniques of learnability theory to derive our sample size upper bounds. We believe that other relations between learning procedures and visual tasks exist and hope that this work will trigger further fruitful study along these lines.
Algorithmic Learning Theory: 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004. Proceedings

Invited Papers.- String Pattern Discovery.- Applications of Regularized Least Squares to Classification Problems.- Probabilistic Inductive Logic Programming.- Hidden Markov Modelling Techniques for Haplotype Analysis.- Learning, Logic, and Probability: A Unified View.- Regular Contributions.- Learning Languages from Positive Data and Negative Counterexamples.- Inductive Inference of Term Rewriting Systems from Positive Data.- On the Data Consumption Benefits of Accepting Increased Uncertainty.- Comparison of Query Learning and Gold-Style Learning in Dependence of the Hypothesis Space.- Learning r-of-k Functions by Boosting.- Boosting Based on Divide and Merge.- Learning Boolean Functions in AC 0 on Attribute and Classification Noise.- Decision Trees: More Theoretical Justification for Practical Algorithms.- Application of Classical Nonparametric Predictors to Learning Conditionally I.I.D. Data.- Complexity of Pattern Classes and Lipschitz Property.- On Kernels, Margins, and Low-Dimensional Mappings.- Estimation of the Data Region Using Extreme-Value Distributions.- Maximum Entropy Principle in Non-ordered Setting.- Universal Convergence of Semimeasures on Individual Random Sequences.- A Criterion for the Existence of Predictive Complexity for Binary Games.- Full Information Game with Gains and Losses.- Prediction with Expert Advice by Following the Perturbed Leader for General Weights.- On the Convergence Speed of MDL Predictions for Bernoulli Sequences.- Relative Loss Bounds and Polynomial-Time Predictions for the k-lms-net Algorithm.- On the Complexity of Working Set Selection.- Convergence of a Generalized Gradient Selection Approach for the Decomposition Method.- Newton Diagram and Stochastic Complexity in Mixture of Binomial Distributions.- Learnability of Relatively Quantified Generalized Formulas.- Learning Languages Generated by Elementary Formal Systems and Its Application to SH Languages.- New Revision Algorithms.- The Subsumption Lattice and Query Learning.- Learning of Ordered Tree Languages with Height-Bounded Variables Using Queries.- Learning Tree Languages from Positive Examples and Membership Queries.- Learning Content Sequencing in an Educational Environment According to Student Needs.- Tutorial Papers.- Statistical Learning in Digital Wireless Communications.- A BP-Based Algorithm for Performing Bayesian Inference in Large Perceptron-Type Networks.- Approximate Inference in Probabilistic Models.
Change Detection and Estimation in Large Scale Sensor Networks: Linear Complexity Algorithms

We propose algorithms for nonparametric sample-based spacial change detection and estimation in large scale sensor networks. We collect random samples containing the location of sensors and their local decisions, and assume that the local decisions can be stimulated or normal , reflecting the local strength of some stimulating agent. Then change in the location of the agent manifests itself by a change in the distribution of stimulated sensors. In this paper, we are aiming at developing a test that, given two collections of samples, can decide whether the distribution generating the samples has changed or not, and give an estimated changed area if a change is indeed detected. The focus of this paper is to reduce the complexity of the detection and estimation algorithm. We propose two fast algorithms with almost linear complexity and analyze their completeness, flexibility and robustness.
Online Learning versus Offline Learning

We present an off-line variant of the mistake-bound model of learning. This is an intermediate model between the on-line learning model (Littlestone, 1988, Littlestone, 1989) and the self-directed learning model (Goldman, Rivest & Schapire, 1993, Goldman & Sloan, 1994). Just like in the other two models, a learner in the off-line model has to learn an unknown concept from a sequence of elements of the instance space on which it makes “guess and test” trials. In all models, the aim of the learner is to make as few mistakes as possible. The difference between the models is that, while in the on-line model only the set of possible elements is known, in the off-line model the sequence of elements (i.e., the identity of the elements as well as the order in which they are to be presented) is known to the learner in advance. On the other hand, the learner is weaker than the self-directed learner, which is allowed to choose adaptively the sequence of elements presented to him.We study some of the fundamental properties of the off-line model. In particular, we compare the number of mistakes made by the off-line learner on certain concept classes to those made by the on-line and self-directed learners. We give bounds on the possible gaps between the various models and show examples that prove that our bounds are tight.Another contribution of this paper is the extension of the combinatorial tool of labeled trees to a unified approach that captures the various mistake bound measures of all the models discussed. We believe that this tool will prove to be useful for further study of models of incremental learning.
Non-Parametric Approach to Change Detection and Estimation in Large Scale Sensor Networks

We consider a non-parametric, spatial sample-based scheme for the detection and estimation of changes of a random eld by collecting packets from randomly distributed sensors. We assume that each sensor has a xed probability of successfully sending to a mobile access point a packet containing its local state|either \excited" or \baseline" and its location. The task we are concerned with here is as follows: Given two sets of packets collected over two nonover- lapping time-windows, construct a test to determine if the distribution generating the sensor's states has changed between these two time windows. Further- more, if a change of distribution has occurred, we wish to estimate the distribution of the change.
A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering

We consider a framework in which the clustering algorithm gets as input a sample generated i.i.d by some unknown arbitrary distribution, and has to output a clustering of the full domain set, that is evaluated with respect to the underlying distribution. We provide general conditions on clustering problems that imply the existence of sampling based clusterings that approximate the optimal clustering. We show that the K-median clustering, as well as the Vector Quantization problem, satisfy these conditions. In particular our results apply to the sampling – based approximate clustering scenario. As a corollary, we get a sampling-based algorithm for the K-median clustering problem that finds an almost optimal set of centers in time depending only on the confidence and accuracy parameters of the approximation, but independent of the input size. Furthermore, in the Euclidean input case, the running time of our algorithm is independent of the Euclidean dimension.
Exploiting Task Relatedness for Mulitple Task Learning

The approach of learning of multiple “related” tasks simultaneously has proven quite successful in practice; however, theoretical justification for this success has remained elusive. The starting point for previous work on multiple task learning has been that the tasks to be learned jointly are somehow “algorithmically related”, in the sense that the results of applying a specific learning algorithm to these tasks are assumed to be similar. We offer an alternative approach, defining relatedness of tasks on the basis of similarity between the example generating distributions that underline these task.
A theory of multitask learning for learning from disparate data sources

Many endeavors require the integration of data from multiple data sources. One major obstacle to such undertakings is the fact that different sources may vary considerably in the way they choose to represent their data, even if their data collections are otherwise perfectly compatible. In practice, this problem is usually solved by a manual construction of translations between these data representations, although there have been some recent attempts at supplementing this with automated algorithms based on machine learning methods. 
This work addresses the problem of making classification predictions based on data from multiple sources, without constructing explicit translations between them. We view this problem as a special case of the problem of multitask learning problem: both intuition and much empirical work indicate that learning can be improved by attacking multiple related tasks simultaneously. However, thus far, no theoretical work has been able to support this claim, and no concrete definition has been proposed for what it means for two learning tasks to be “related.” 
In this work, we introduce a general notion of relatedness between tasks, provide the standard sort of information complexity bound for such tasks, and give general conditions under which this bound is an improvement over standard single task learning results. 
Finally, we apply these results to the problem of learning from disparate data sources. We give a decision tree learning algorithm for this problem for a particular type of data source disparity and demonstrate its empirical success on real data sets.