nils-herrmann/clean_scirepeval huggingface dataset:
A theoretical framework for learning from a pool of disparate data sources

Many enterprises incorporate information gathered from a variety of data sources into an integrated input for some learning task. For example, aiming towards the design of an automated diagnostic tool for some disease, one may wish to integrate data gathered in many different hospitals. A major obstacle to such endeavors is that different data sources may vary considerably in the way they choose to represent related data. In practice, the problem is usually solved by a manual construction of semantic mappings and translations between the different sources. Recently there have been attempts to introduce automated algorithms based on machine learning tools for the construction of such translations.In this work we propose a theoretical framework for making classification predictions from a collection of different data sources, without creating explicit translations between them. Our framework allows a precise mathematical analysis of the complexity of such tasks, and it provides a tool for the development and comparison of different learning algorithms. Our main objective, at this stage, is to demonstrate the usefulness of computational learning theory to this practically important area and to stimulate further theoretical and experimental research of questions related to this framework.
The Computational Complexity of Densest Region Detection

We investigate the computational complexity of the task of detecting dense regions of an unknown distribution from unlabeled samples of this distribution. We introduce a formal learning model for this task that uses a hypothesis class as it “anti-overfitting” mechanism. The learning task in our model can be reduced to a combinatorial optimization problem. We can show that for some constants, depending on the hypothesis class, these problems are NP-hard to approximate to within these constant factors. We go on and introduce a new criterion for the success of approximate optimization geometric problems. The new criterion requires that the algorithm competes with hypotheses only on the points that are separated by some margin ? from their boundaries. Quite surprisingly, we discover that for each of the two hypothesis classes that we investigate, there is a “critical value” of the margin parameter ?. For any value below the critical value the problems are NP-hard to approximate, while, once this value is exceeded, the problems become poly-time solvable.
Limitations of Learning Via Embeddings in Euclidean Half Spaces

The notion of embedding a class of dichotomies in a class of linear half spaces is central to the support vector machines paradigm. We examine the question of determining the minimal Euclidean dimension and the maximal margin that can be obtained when the embedded class has a finite VC dimension. We show that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in low-dimensional half spaces. (In fact, we show that the Euclidean dimension must be almost as high as the size of the instance space.) We strengthen this result even further by showing that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in half spaces (of arbitrarily high Euclidean dimension) with a large margin. (In fact, the margin cannot be substantially larger than the margin achieved by the trivial embedding.) Furthermore, these bounds are robust in the sense that allowing each image half space to err on a small fraction of the instances does not imply a significant weakening of these dimension and margin bounds. Our results indicate that any universal learning machine, which transforms data into the Euclidean space and then applies linear (or large margin) classification, cannot enjoy any meaningful generalization guarantees that are based on either VC dimension or margins considerations. This failure of generalization bounds applies even to classes for which "straight forward" empirical risk minimization does enjoy meaningful generalization guarantees.
Agnostic Boosting

We extend the boosting paradigm to the realistic setting of agnostic learning, that is, to a setting where the training sample is generated by an arbitrary (unknown) probability distribution over examples and labels. We define a β-weak agnostic learner with respect to a hypothesis class F as follows: given a distribution P it outputs some hypothesis h ∈ F whose error is at most erP (F) + β, where erP (F) is the minimal error of an hypothesis from F under the distribution P (note that for some distributions the bound may exceed a half). 
 
We show a boosting algorithm that using the weak agnostic learner computes a hypothesis whose error is at most max{c1(β)er(F)c2(β), Ɛ}, in time polynomial in 1/Ɛ. While this generalization guarantee is significantly weaker than the one resulting from the known PAC boosting algorithms, one should note that the assumption required for β-weak agnostic learner is much weaker. In fact, an important virtue of the notion of weak agnostic learning is that in many cases such learning is achieved by efficient algorithms.
A Note on Non-complete Problems in NPImage

This note deals with the structure of the class NP R introduced by L. Blum, M. Shub, and S. Smale (1989, . It is shown that, assuming NP R ⊈P R /poly, there exists a problem NP R \(P R /poly) which is not NP R -complete (w.r.t P R /poly reductions). It also clarifies the scope of a padding technique used in a former similar result by R. Ladner (1975, ) concerning the structure of the class NP (in the common, Turing machine, model).
On the Di cultyof Approximately Maximizing Agreements

We address the computational complexity of learning in the agnostic framework. For a variety of common concept classes we prove that, unless P=NP, there is no polynomial time approximation scheme for nding a member in the class that approximately maximizes the agreement with a given training sample. In particular our results apply to the classes of monomials, axis-aligned hyper-rectangles, closed balls and monotone monomials. For each of these classes we prove the NP-hardness of approximating maximal agreement to within some xed constant (independent of the sample size and of the dimensionality of the sample space). For the class of half-spaces, we prove that, for any > 0, it is NP-hard to approximately maximize agreements to within a factor of (418=415 ), improving on the best previously known constant for this problem, and using a simpler proof. An interesting feature of our proofs is that, for each of the classes we discuss, we nd patterns of training examples that, while being hard for approximating agreement within that concept class, allow e cient agreement maximization within other concept classes. These results bring up a new aspect of the model selection problem { they imply that the choice of hypothesis class for agnostic learning from among those considered in this paper can drastically e ect the computational complexity of the learning process.
Localized Boosting

We introduce and analyze LocBoost, a new boosting algorithm, which leads to the incremental construction of a mixture of experts type architecture. We provide upper bounds on the expected loss of such models in terms of the smoothness properties of the gating functions appearing in the mixture of experts model. Furthermore, an incremental algorithm is proposed for the construction of the classifier, based on a maximum-likelihood approach and the EM algorithm.  to be promising.
Hardness Results for Neural Network Approximation Problems

We consider the problem of efficiently learning in two-layer neural networks. We show that it is NP-hard to find a linear threshold network of a fixed size that approximately minimizes the proportion of misclassified examples in a training set, even if there is a network that correctly classifies all of the training examples. In particular, for a training set that is correctly classified by some two-layer linear threshold network with k hidden units, it is NP-hard to find such a network that makes mistakes on a proportion smaller than c=k3 of the examples, for some constant c. We prove a similar result for the problem of approximately minimizing the quadratic loss of a two-layer network with a sigmoid output unit.
On the Existence of Optimal Propositional Proof Systems and Oracle-relativized Propositional Logic

We investigate suucient conditions for the existence of optimal propositional proof systems. We concentrate on conditions of the form CoNF = NF. We introduce a purely combinatorial property of complexity classes-the notions of slim vs. fat classes. These notions partition the collection of all previously studied time-complexity classes into two complementary sets. We show that for every slim class an appropriate collapse entails the existence of an optimal propositional proof system. On the other hand, we introduce a notion of a propositional proof system relative to an oracle and show that for every fat class there exists an oracle relative to which such an entailment fails. As the classes P (polynomial functions), E (2 O(n) functions) and EE (2 O(2 n) functions) are slim, this result includes all the previously known suuciency conditions for the existence of optimal propositional proof systems. On the other hand, the classes N EX P, QP (the class of quasi-polynomial functions) and EEE (2 O(2 2 n) functions), as well as any other natural time-complexity class which is not covered by our suuciency result, are fat classes. As the proofs of all the known suuciency conditions for the existence of optimal propositional proof systems carry over to the corresponding oracle-relativized notions, our oracle result shows that no extension of our suuciency condition to non-slim classes can be obtained by the type of reasoning used so far in proofs on these issues.
Computational learning theory : Third European Conference, EuroCOLT '97, Jerusalem, Israel, March 17-19, 1997, proceedings

Sample compression, learnability, and the Vapnik-Chervonenkis dimension.- Learning boxes in high dimension.- Learning monotone term decision lists.- Learning matrix functions over rings.- Learning from incomplete boundary queries using split graphs and hypergraphs.- Generalization of the PAC-model for learning with partial information.- Monotonic and dual-monotonic probabilistic language learning of indexed families with high probability.- Closedness properties in team learning of recursive functions.- Structural measures for games and process control in the branch learning model.- Learning under persistent drift.- Randomized hypotheses and minimum disagreement hypotheses for learning with noise.- Learning when to trust which experts.- On learning branching programs and small depth circuits.- Learning nearly monotone k-term DNF.- Optimal attribute-efficient learning of disjunction, parity, and threshold functions.- learning pattern languages using queries.- On fast and simple algorithms for finding Maximal subarrays and applications in learning theory.- A minimax lower bound for empirical quantizer design.- Vapnik-Chervonenkis dimension of recurrent neural networks.- Linear Algebraic proofs of VC-Dimension based inequalities.- A result relating convex n-widths to covering numbers with some applications to neural networks.- Confidence estimates of classification accuracy on new examples.- Learning formulae from elementary facts.- Control structures in hypothesis spaces: The influence on learning.- Ordinal mind change complexity of language identification.- Robust learning with infinite additional information.
A composition theorem for learning algorithms with applications to geometric concept classes

This paper solves the open problem of exact learning geometric objects bounded by hyperplanes (and more generally by any constant degree algebraic surfaces) in the constant dimensional space from equivalence queries only (i.e., in the on-line learning model). We present a novel approach that allows, under certain conditions, the composition of learning algorithms for simple classes into an algorithm for a more complicated class. Informally speaking, it shows that if a class of concepts C is learnable in time t using a small space then @, the class of all functions of the form ~(gl, . . , gm) With 91, . . . . gm E C and any boolean function ~, is learnable in polynomial time in t and m. We then show that the class of halfspaces in a fixed dimension space is learnable with a small space.
Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher

We propose a mathematical model for learning the high-density areas of an unknown distribution from (unlabeled) random points drawn according to this distribution. While this type of a learning task has not been previously addressed in the computational learnability literature, we believe that this it a rather basic problem that appears in many practical learning scenarios. From a statistical theory standpoint, our model may be viewed as a restricted instance of the fundamental issue of inferring information about a probability distribution from the random samples it generates. From a computational learning angle, what we propose is a few framework of unsupervised concept learning. The examples provided to the learner in our model are not labeled (and are not necessarily all positive or all negative). The only information about their membership is indirectly disclosed to the student through the sampling distribution. We investigate the basic features of the proposed model and provide lower and upper bounds on the sample complexity of such learning tasks. We prove that classes whose VC-dimension is finite are learnable in a very strong sense, while on the other hand,�-covering numbers of a concept class impose lower bounds on the sample size needed for learning in our models. One direction of the proof involves a reduction of the density-level learnability to PAC learning with respect to fixed distributions (as well as some fundamental statistical lower bounds), while the sufficiency condition is proved through the introduction of a generic learning algorithm.
Learning Changing Concepts by Exploiting the Structure of Change

This paper examines learning problems in which the target function is allowed to change. The learner sees a sequence of random examples, labelled according to a sequence of functions, and must provide an accurate estimate of the target function sequence. We consider a variety of restrictions on how the target function is allowed to change, including infrequent but arbitrary changes, sequences that correspond to slow walks on a graph whose nodes are functions, and changes that are small on average, as measured by the probability of disagreements between consecutive functions. We first study estimation, in which the learner sees a batch of examples and is then required to give an accurate estimate of the function sequence. Our results provide bounds on the sample complexity and allowable drift rate for these problems. We also study prediction, in which the learner must produce online a hypothesis after each labelled example and the average misclassification probability over this hypothesis sequence should be small. Using a deterministic analysis in a general metric space setting, we provide a technique for constructing a successful prediction algorithm, given a successful estimation algorithm. This leads to sample complexity and drift rate bounds for the prediction of changing concepts.
On self-directed learning

We study several issues concerning the selfdmected model of learning [G RS93, GS94). In particular, we show that the mistake bound of the self-directed learner cannot be smaller than the mistake bound of the on-line learner [L88, L89] by more than a factor of log IX], where X is the instance space. Concept classes which exhibit such a gap are known. In fact, we prove that such a gap exists even between the mistake bound of the self-directed learner and of a learner which is allowed to choose, off-line, the order in which the elements of X will be presented to it (but not adaptively as is the case in the self-directed model); hence, showing the power of adaptiveness. We also study the relations between the VCdimension of a concept class and its self-directed complexity. We show that for certain concept classes the seIf-directed comp~exity can be arbitrarily high, while their VC-dimension remains a fixed constant.  Moreover, we show that there are “intersection-closed” concept classes for which the self-directed complexity is 3/2 times the VC-dimension. This disproves a conjecture of [GS94]. Computer Science Department, Technion, Haifa 32000, Israel. shai@cs.technion .ac.il t Computer Science Department, Tecllnion, Haifa 32000,  Technion, Haifa 32000,  on.ac.il Permission to m~ke digital/hard copies of all or port of this material without fee is granted provided that the copies are not nmde or distributed for urotit or commercial advantage, the ACM copyright/server not~ce, the title of the publication and its date app-e’ar,-and notice is given that copyright is by permission of the Association for Computing Machinery> Inc. (ACM). To copy otherwise, to republish,to post on servers or to We also prove a lower bound on the product of the number of querves made by a selfdirected algorithm and the number of mistakes it makes. This lower bound indicates that lowering the mistake bound of a self-directed algorithm results in an increase of the number of queries it has to go through.
Establishing PCI compliance using formal verification: a case study

This paper presents a case study in the practical application of formal verification. Specifically, we describe our experience in applying the formal verification technique of symbolic model checking to the verification of PCI bus bridges. During the last 2 years, we have used symbolic model checking to verify more than 12 hardware designs, including a number of PCI bus bridges. This use of formal verification has led to the better understanding of formal verification capabilities and the establishment of formal verification techniques as a standard verification tool in the Haifa Design Group at IBM's Haifa Research Laboratory. More than 5 PCI bus bridge designs have been verified using formal verification, including a design in which formal verification was used to do all checks at the unit level. A PCI bus bridge design that was verified with formal verification was announced as an IBM product and became available to customers after a single tape-out.<<ETX>>
Online learning versus offline learning

We present an off-line variant of the mistake-bound model of learning. Just like in the well studied on-line model, a learner in the offline model has to learn an unknown concept from a sequence of elements of the instance space on which he makes “guess and test” trials. In both 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.
Localization vs. Identification of Semi-Algebraic Sets

How difficult is it to find the position of a known object using random samples? We study this question, which is central to Computer Vision and Robotics, in a formal way. We compare the information complexity of two types of tasks: the task of identification of an unknown object from labeled examples input, and the task of localization in which the identity of the target is known and its location in some background scene has to be determined.We carry out the comparison of these tasks using two measuring rods for the complexity of classes of sets; The Vapnik-Chervonenkis dimension and the ∈-entropy of relevant classes. The VC-dimension analysis yields bounds on the sample complexity of performing these tasks in the PAC-learning scenario whereas the ∈-entropy parameter reflects the complexity of the relevant learning tasks when the examples are generated by the uniform distribution (over the background scene). Our analysis provides a mathematical ground to the intuition that localization is indeed much easier than identification.Our upper-bounds on the hardness of localization are established by applying a new, algebraic-geometry based, general tool for the calculation of the VC-dimension of classes of algebraically defined objects. This technique was independently discovered by Goldberg and Jerrum. We believe that our techniques will prove useful for further VC-dimension estimation problems.
Multivariate Information Bottleneck

The information bottleneck (IB) method is an unsupervised model independent data organization technique. Given a joint distribution, p(X, Y), this method constructs a new variable, T, that extracts partitions, or clusters, over the values of X that are informative about Y. Algorithms that are motivated by the IB method have already been applied to text classification, gene expression, neural code, and spectral analysis. Here, we introduce a general principled framework for multivariate extensions of the IB method. This allows us to consider multiple systems of data partitions that are interrelated. Our approach utilizes Bayesian networks for specifying the systems of clusters and which information terms should be maintained. We show that this construction provides insights about bottleneck variations and enables us to characterize the solutions of these variations. We also present four different algorithmic approaches that allow us to construct solutions in practice and apply them to several real-world problems.
Query by Committee Made Real

Training a learning algorithm is a costly task. A major goal of active learning is to reduce this cost. In this paper we introduce a new algorithm, KQBC, which is capable of actively learning large scale problems by using selective sampling. The algorithm overcomes the costly sampling step of the well known Query By Committee (QBC) algorithm by projecting onto a low dimensional space. KQBC also enables the use of kernels, providing a simple way of extending QBC to the non-linear scenario. Sampling the low dimension space is done using the hit and run random walk. We demonstrate the success of this novel algorithm by applying it to both artificial and a real world problems.
Extracting Continuous Relevant Features

The problem of extracting the relevant aspects of data, in face of multiple conflicting structures, is inherent to modeling of complex data. Extracting continuous structures in one random variable that are relevant for another variable has been principally addressed recently via the method of Sufficient dimensionality reduction. However, such auxiliary variables often contain both structures that are relevant and others that are irrelevant for the task in hand. Identifying the relevant structures was shown in the context of clustering to be considerably improved by minimizing the information about another, irrelevant, variable. In this paper we address the problem of extracting continuous relevant structures and derive its formal, as well as algorithmic, solution. Its operation is demonstrated in a synthetic example and in a real world application of face images, showing its superiority over current methods such as oriented principal component analysis.