nils-herrmann/clean_scirepeval huggingface dataset:
Noise-Tolerant Parallel Learning of Geometric Concepts

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constant-dimensional space. The algorithms are robust even against malicious classification noise of any rate less than 1/2. We first give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d?1)-dimensional hyperplanes against an arbitrary distribution where each hyperplane has a slope from a set of known slopes. We then describe how boosting techniques can be used so that our algorithms' dependence on?and?does not depend ond. Next, we give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d?1)-dimensional hyperplanes (of unrestricted slopes) against a uniform distribution. We then show how to extend our algorithm to learn this class against any (unknown) product distribution. Next we define a complexity measure of any setSof (d?1)-dimensional surfaces that we call thevariantofSand prove that the class of geometric concepts defined by surfaces of polynomial variant can be efficiently learned in parallel under a product distribution (even under malicious classification noise). Furthermore, we show that the VC-dimension of the class of geometric concepts defined by a single surface of variant one is ∞. Finally, we give an efficient, parallel, noise-tolerant algorithm to PAC-learn any 2-dimensional geometric concept defined by a setSof 1-dimensional surfaces of polynomial length under a uniform distribution.
A Space-bounded Learning of Classes with Vc-dim = 1 Proof: Combine Theorem 3 with Corollary 2. 5 Extensions

If the algorithm has in its memory two points x + ; x ? then the algorithm performs a binary search on the path connecting x + and x ? as follows: the algorithm picks the node y 2 which is the middle point on the path connecting x + and x ? ; the algorithm deenes an hypothesis h using the branch leading to y 2 and asks an equivalence query EQ(h). If the answer to the query is \YES" it stops with output h. Otherwise, if the counterexample z is a point on the path connecting x + and x ? satisfying f(z) 6 = h(z) (i.e., a point below y 2) the algorithm sets x + z; if the counterexample z is a point on the path connecting x + and x ? satisfying f(z) = h(z) (i.e., a point above y 2) the algorithm sets x ? z; if z is not at the path at all (in this case f(z) 6 = h(z)) the algorithm sets x + z and removes x ? (that is, in the next iteration it will perform Step 1). Since Step 2 performs a binary search on the path connecting x + and x ? then each sequence of iterations that perform Step 2 is of length at most the logarithm of the length of this path which is at most log jXj. Such a sequence ends with either identifying f or with a new x + outside the path. The number of times that Step 1 is performed is log jXj, because at each step we either nd a new x + which by the deenition of y 1 has in its subtree at most 1=2 of the number of nodes that we had before, or we start a sequence of iterations of Step 2 in which (unless we identify f before) we nd a new x + outside the path to x ? (and y 1) in which again, by the deenition of y 1 , leaves us with at most half the size of the tree. All together the number of iterations is bounded by (log jXj) 2 and the space is bounded by 2 points. Corollary 8 For every class C as above, the class C ? is learnable using number of queries which is polynomial in log X and m. 14 8f : f(x) = …
Making Maximum Entropy Computations Easier ByAdding Extra Constraints

This paper presents a new way to compute the probability distribution with maximum entropy satisfying a set of constraints Unlike previous ap proaches our method is integrated with the planning of data collection and tabulation We show how adding constraints and performing the associated additional tabulations can substantially speed up computation by replacing the usual iterative techniques with a straight forward computation These extra constraints are shown to correspond to the intermediate tables used in Cheeseman s method We also show that the class of constraint graphs that our method handles is a proper generalization of Pearl s singly connected networks An open problem is to determine a minimal set of constraints necessary to make a hypergraph acyclic We conjecture that this problem is NP complete and discuss heuristics to approximate the optimal solution
Learning from examples with unspecified attribute values (extended abstract)

1 INTRODUCTION We introduce the UAV learning model in which some of the attributes in the examples are un-specified. In our model. an example 2 is classified positive (resp., negative) if all possible assignments for the unspecified attributes result in a positive (resp., negative) classification. Otherwise the classification given to z is 'l'? " (for unknown). Given an example z in which some attributes are unspecified, the oracle UA\y-MQ responds with the classification of 2. Given a hypothesis h, the oracle UAV-EQ returns an example r (that could have unsper-ified at,tributes) for which h(z) is incorrect. We show that any class learnable in the exact model using the MQ and EQ oracles is also learnable in the U.4V model using the MQ and IJA\'-EQ oracles as long as the counterexamples provided by the UAV-EQ oracle have a logarithmic number of unspecified attributes. We also show that any class learnable in the exact, model using the MQ and EQ oracles is also learnable in the UA\' model using the UAV-MC) and UA4V-EQ oracles as well as an oracle t,o evaluate a given boolean formula on an example with unspecified attributes. (For some hypothesis classes such as decision trees and unate formulas the evaluation can be done in polynomial time without an oracle.) We also study the learnability of a universal class of decision trees under the UAV model and of DNF formulas under a representation-dependent variation of t,he CJAV model. Most theoretical work on learning boolean functions assumes that the examples are drawn from (0, l}n and each example is classified as positive (" + ") or negative ("-") by the unknown target concept f. However, consider the situation of trying to predict whether or not an individual will default on a loan. There are a large number of attributes that one might consider (some about the individual and some about t,he individ-ual's employer). Using standard approaches to learning boolean functions, a learning algorithm could consider each loan application as an example from (0, l}* where n is the number of attributes under consideration for loan applications. Let's assume that if we had correct data for all of the attributes, then such an algorithm could make a very good prediction as t,o whether or not the individual will default on the loan. However, in practice some attributes' values will not be provided (or specified). For example: some states may prohibit the …
Agnostic learning of geometric patterns (extended abstract)

1 INTRODUCTION Goldberg, Goldman, and Scott demonstrated how the problem of recognizing a landmark from a one-dimensional visual image can be mapped to that of learning a one-dimensional geometric pattern and gave a PAC algorithm to learn that class. We present an on-line agnostic learning algorithm for learning the class of one-dimensional geometric patterns. Since, when moving from the processed visual image to a one-dimensional pattern some key information is lost, we define a class of two-dimensional geometric patterns for which the important features from the visual image are incorporated in the geometric pattern, and show how to extend our agnostic learning algorithm to this class of two-dimensional patterns. Consider a robot designed to navigate through a large-scaled environment'. Suppose a set of key " landmarks " have already been selected (by another component of the navigation system). It is crucial that the robot be able to recognize whether or not it is in the vicinity of a given landmark from data taken at the robot's current location. We refer to this problem as the landmark matching problem. The landmark matching algorithm should run in real-time and be noise-tolerant. Next, we extend our construction to obtain an efficient agnostic learning algorithm (that tolerate classification and attribute noise) for the class of geometric patterns of arbitrary (constant) dimension d. This mapping and learning algorithm is applicable to any data rep-resentable as a constant-dimensional array of values, e.g. sonar data, temporal difference information , or amplitudes of a waveform. To our knowledge, these classes of patterns are more complex than any class of geometric patterns previously studied. Also our results are easily adapted to learn the union of fixed-dimensional boxes from multiple-instance examples. Finally, our algorithms can be made to tolerate concept shift. Much work on designing landmark matching algorithms uses a pattern matching approach to match the visual image (or whatever form of data is available) to the data taken at landmark position L. The matching algorithm must determine if the robot is near L (i.e. in a small circle centered around L). Because the visual image may change significantly as small movements around L are made, the pattern matching ap preach encounters difficulties. Goldberg, Goldman and Scott [5, 7] proposed using a learning algorithm to construct an accurate hypothesis for performing landmark matching. They obtained their training data by converting the visual data into one-dimensional geometric patterns. Then by applying …
Computational Learning Theory

1 Preface This manuscript is a compliation of lecture notes from the graduate level course CS 582, Computational Learning Theory," I taught a t W ashington University in the spring of 1991. Students taking the course were assumed to have background in the design and analysis of algorithms as well as good mathematical background. Given that there is no text available on this subject, the course material was drawn from recent research papers. I selected the rst twelve topics and the remainder were selected by the students from a list of provided topics. This list of topics is given at the end of these notes. These notes were mostly written by the students in the class and then reviewed by me. However, there are likely to be errors and omissions, particularly with regard to the references. Readers nding errors in the notes are encouraged to notify me by electronic mail sg@cs.wustl.edu so that later versions may be corrected. 2 3 Acknowledgements This compilation of notes would not have been possible without the hard work of the following students: I thank Mike Kearns and Umesh Vazirani for providing me with a draft of the scribe notes from their Computational Learning Theory course taught at University of California at Berkeley in the Fall of 1990. Some of my lectures were prepared using their notes. Also most of the homework problems which I g a v e came from the problems used by Ron Rivest for his Machine Learning course at MIT taught during the Falls of 1989 and 1990. I thank Ron for allowing me to include these problems here.
On-line Scheduling with Hard Deadlines (Extended Abstract)

We study non-preemptive, online admission control in the hard deadline model: each job must be either serviced prior to its deadline, or be rejected. Our setting consists of a single resource that services an online sequence of jobs; each job has a length indicating the length of time for which it needs the resource, and a delay indicating the maximum time it can wait for the service to be started. The goal is to maximize total resource utilization. We obtain a series of results, under varying assumptions of job lengths and delays.
Teaching a Smarter Learner

We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible. Not surprisingly, such a model remedies the nonintuitive aspects of other models in which the teacher must successfully teach any consistent learner. We prove that any class that can be exactly identified by a deterministic polynomial-time algorithm with access to a very rich set of example-based queries is teachable by a computationally unbounded teacher and a polynomial-time learner. In addition, we present other general results relating this model of teaching to various previous results. We also consider the problem of designing teacher/learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher/learner pairs for the classes of 1-decision lists and Horn sentences
Noise-tolerant distribution-free learning of general geometric concepts

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over {fancy R superscript d} for fixed d. More specifically, let {T} be any set of s halfspaces. Let x = (x1,...,xd) be an arbitrary point in {fancy R superscript d}. With each t {lying in} T we associate a boolean indicator function I{sub t}(x) which is 1 if and only if x is in the halfspace t. The concept class C{super script d, subscript s} that we study consists of all concepts formed by any boolean function over It1, ...Its for ti {lying in} T. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any boolean combination of a polynomial number of concepts selected from any concept class C over {fancy R superscript d} given that the VC-dimension of C has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from C consistent with a... Read complete abstract on page 2.
Asking Questions to Minimize Errors

A number of efficient learning algorithms achieve exact identification of an unknown function from some clas using membership and equivalence queries. Using a standard transformation such algorithms can easily be converted to on-line learning algorithms that use membership queries. Under such a transformation the number of equivalence queries made by the query algorithm directly corresponds to the number of mistakes made by the on-line algorithm. In this paper we consider several of the natural classes known to be learnable in this setting, and investigate the minimum number of equivalence queries with accompanying counterexamples (or equivalently the minimum number of mistakes in the on-line model) that can be made by a learning algorithm that makes a polynomial nubmer of membership queries and uses polynomial computation time. We are able both to reduce the nubmer of equivalence queries used by the previous algorithms and often to prove matching lower bounds. As an example, consider the class of DNF formulas over n variables with at most k = O(logn) terms. Previously, the algorithm of Blum and Rudich... Read complete abstract on page 2.
Learning from a Consistently Ignorant Teacher

One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We consider the impact of knowledge gaps on learning, for example, monoton DNF and d-dimensional boxes, and show that leraning is still possible. Negatively, we show that knowledge gaps make learning conjunctions of Horn clauses as hard as learning DNF. We also present general results describing when known learning algorithms can be used to obtain learning algorithms using a consistently ignorant teacher.
Learning with unreliable boundary queries

We introduce a model for learning from examples and membership queries in situations where the boundary between positive and negative examples is somewhat ill-defined. In our model, queries near the boundary of a target concept may receive incorrect or “don't care” responses, and the distribution of examples has zero probability mass on the boundary region. The motivation behind our model is that in many cases the boundary between positive and negative examples is complicated or “fuzzy.” However, one may still hope to learn successfully, because the typical examples that one sees do not come from that region. We present several positive results in this new model. We show how to learn the intersection of two arbitrary halfspaces when membership queries near the boundary may be answered incorrectly. Our algorithm is an extension of an algorithm of Baum (1990, 1991) that learns the intersection of two halfspaces whose bounding planes pass through the origin in the PAC-with-membership-queries model. We also describe algorithms for learning several subclasses of monotone DNF formulas.
Noise-tolerant parallel learning of geometric concepts

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constantdimensional space. The algorithms are robust even against malicious classification noise of any rate less than 1/2. We first give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d-1)-dimensional hyperplanes against an arbitrary distribution where each hyperplane has a slope from a set of known slopes. We then describe how boosting techniques can be used so that our algorithms' dependence on {GREEK LETTER} and {DELTA} does not depend on d. Next we give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d-1)-dimensional hyperplanes (of unrestricted slopes) against a uniform distribution. We then show how to extend our algorithm to learn this class against any (unknown) product distribution. Next we defined a complexity measure of any set S of (d-1)-dimensional surfaces that we call the variant of S and prove that the class of geometric concepts defined by surfaces of polynomial variant can... Read complete abstract on page 2.
On the complexity of teaching

While most theoretical work in machine learning has focused on the complexity of learning, recently there has been increasing interest in formally studying the complexity of teaching. In this paper we study the complexity of teaching by considering a variant of the on-line learning model in which a helpful teacher selects the instances. We measure the complexity of teaching a concept from a given concept class by a combinatorial measure we call the teaching dimension, Informally, the teaching dimension of a concept class is the minimum number of instances a teacher must reveal to uniquely identify any target concept chosen from the class.
Prediction of protein stability changes for single‐site mutations using support vector machines

Accurate prediction of protein stability changes resulting from single amino acid mutations is important for understanding protein structures and designing new proteins. We use support vector machines to predict protein stability changes for single amino acid mutations leveraging both sequence and structural information. We evaluate our approach using cross‐validation methods on a large dataset of single amino acid mutations. When only the sign of the stability changes is considered, the predictive method achieves 84% accuracy—a significant improvement over previously published results. Moreover, the experimental results show that the prediction accuracy obtained using sequence alone is close to the accuracy obtained using tertiary structure information. Because our method can accurately predict protein stability changes using primary sequence information only, it is applicable to many situations where the tertiary structure is unknown, overcoming a major limitation of previous methods which require tertiary information. The web server for predictions of protein stability changes upon mutations (MUpro), software, and datasets are available at http://www.igb.uci.edu/servers/servers.html. Proteins 2006.
Large‐scale prediction of disulphide bridges using kernel methods, two‐dimensional recursive neural networks, and weighted graph matching

The formation of disulphide bridges between cysteines plays an important role in protein folding, structure, function, and evolution. Here, we develop new methods for predicting disulphide bridges in proteins. We first build a large curated data set of proteins containing disulphide bridges to extract relevant statistics. We then use kernel methods to predict whether a given protein chain contains intrachain disulphide bridges or not, and recursive neural networks to predict the bonding probabilities of each pair of cysteines in the chain. These probabilities in turn lead to an accurate estimation of the total number of disulphide bridges and to a weighted graph matching problem that can be addressed efficiently to infer the global disulphide bridge connectivity pattern. This approach can be applied both in situations where the bonded state of each cysteine is known, or in ab initio mode where the state is unknown. Furthermore, it can easily cope with chains containing an arbitrary number of disulphide bridges, overcoming one of the major limitations of previous approaches. It can classify individual cysteine residues as bonded or nonbonded with 87% specificity and 89% sensitivity. The estimate for the total number of bridges in each chain is correct 71% of the times, and within one from the true value over 94% of the times. The prediction of the overall disulphide connectivity pattern is exact in about 51% of the chains. In addition to using profiles in the input to leverage evolutionary information, including true (but not predicted) secondary structure and solvent accessibility information yields small but noticeable improvements. Finally, once the system is trained, predictions can be computed rapidly on a proteomic or protein‐engineering scale. The disulphide bridge prediction server (DIpro), software, and datasets are available through www.igb.uci.edu/servers/psss.html. Proteins 2006.
ENERGY-AWARE ADAPTIVE LOW POWER LISTENING FOR SENSOR NETWORKS

Energy efficiency is a central issue for all wireless sensor network applications. Idle listening on the wireless channel constitutes a large portion of overall energy consumption in sensor networks. The need to reduce idle listening energy consumption has led recently to the design of BMAC , a MAC protocol for sensor networks which provides 8 low power listening modes and 8 corresponding transmit modes. Here, we propose a cross-layer mechanism called Energy Aware Adaptive Low Power Listening (EA-ALPL) that enables each individual sensor node running BMAC to set its own listening mode according to its duty cycle and its number of descendants in the routing tree. EA-ALPL also enables nodes to learn the listening modes of their neighbors and to choose the appropriate transmit mode in order to ensure correct packet reception. We show through deployment experiments that EA-ALPL yields overall power savings ranging between 16% and 55% depending on a node's logical topology position.