nils-herrmann/clean_scirepeval huggingface dataset:
Generalization Bounds for Linear Learning Algorithms

We study generalization properties of linear learning algo rithms and develop a data dependent approach that is used to derive genera lization bounds that depend on the margin distribution. Our method ma kes use of random projection techniques to allow the use of existing VC dimension bounds in the effective, lower, dimension of the data. C omparisons with existing generalization bound show that our bounds are tighter and meaningful in cases existing bounds are not. Our methods is a l o shown to be useful as an analysis tool, alternative to learning cur ves.
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms

We study online learning in Boolean domains using kernels which capture feature expansions equivalent to using conjunctions over basic features. We demonstrate a tradeoff between the computational efficiency with which these kernels can be computed and the generalization ability of the resulting classifier. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Percep-tron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple functions. We also consider an analogous use of kernel functions to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Win-now's behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efficiently computable.
Shallow Parsing by Inferencing with Classifiers

We study the problem of identifying phrase structure. We formalize it as the problem of combining the outcomes of several different classifiers in a way that provides a coherent inference that satisfies some constraints, and develop two general approaches for it. The first is a Markovian approach that extends standard HMMs to allow the use of a rich observations structure and of general classifiers to model state-observation dependencies. The second is an extension of constraint satisfaction formalisms. We also develop efficient algorithms under both models and study them experimentally in the context of shallow parsing.
Relational Representations that Facilitate Learning

Given a collection of objects in the world, along with some relations that hold among them, a fundamental problem is how to learn definitions of some relations and concepts of interest in terms of the given relations. These definitions might be quite complex and, inevitably, might require the use of quantified expressions. Attempts to use first order languages for these purposes are hampered by the fact that relational inference is intractable and, consequently, so is the problem of learning relational definitions. This work develops an expressive relational representation language that allows the use of propositional learning algorithms when learning relational definitions. The representation serves as an intermediate level between a raw description of observations in the world and a propositional learning system that attempts to learn definitions for concepts and relations. It allows for hierarchical composition of relational expressions that can be evaluated efficiently on the observations and thus supports learning complex definitions by learning simple functions of the intermediate representations. The approach is illustrated using examples from natural language and visual processing.
Toward a Theory of Learning Coherent Concepts

We develop a theory for learning scenarios where multiple learners co-exist but there are mutual compatibility constraints on their outcomes. This is natural in cognitive learning situations, where \natural" compatibility constraints are imposed on the outcomes of classiers so that a valid sentence, image or any other domain representation is produced. We suggest that work in this direction may help to resolve the contrast between the hardness of learning as predicted by the current theoretical models and the apparent ease at which cognitive systems seem to learn. A model of concept learning is studied in which the target concept is required to cohere with other concepts of interest. The coherency is expressed via a (Boolean) constraint that the concepts have to satisfy. Under this model, learning a concept is shown to be easier (in terms of sample complexity and mistake bounds) and the concepts learned are shown to be more robust to noise in their input (attribute noise). These properties are established for half spaces and the connection to large margin theory is discussed.
The Use of Classifiers in Sequential Inference

We study the problem of combining the outcomes of several different classifiers in a way that provides a coherent inference that satisfies some constraints. In particular, we develop two general approaches for an important subproblem - identifying phrase structure. The first is a Markovian approach that extends standard HMMs to allow the use of a rich observation structure and of general classifiers to model state-observation dependencies. The second is an extension of constraint satisfaction formalisms. We develop efficient combination algorithms under both models and study them experimentally in the context of shallow parsing.
Hard and Easy Bayesian Networks for Computing the Most Probable Explanation

This paper introduces an experimental paradigm for systematically generating increasingly hard instances for Bayesian networks inference. The approach allows us to control the level of difficulty of the Bayesian network inference problem, providing benchmark Bayesian networks for more systematic experimentation. We investigate two families of synthetic Bayesian networks, in which we study a few structural and distributional parameters and show how changing them (while maintaining network size) can change the hardness of the problem from a very simple inference problem to one that existing algorithms cannot handle. Among the parameters we study are the ratio of the number of root nodes to the number of non-root nodes in the network, the irregularity of the graph and the distributional nature of the conditional probability tables. The hardness of the networks is investigated experimentally using one of the most successful commercial inference algorithms, Hugin, along with a stochastic local search algorithm that we have developed, Stochastic Greedy Search. While both algorithms break down as the hardness of the problem increases we show that they vary significantly along some of the dimensions and that, surprisingly, the performance of the stochastic search algorithm degrades more gracefully in many cases.
A Classification Approach to Word Prediction

The eventual goal of a language model is to curately predict the value of a missing word given its context. We present an approach to word prediction that is based on learning a representation for each word as a function of words and linguistics predicates in its context. This approach raises a few new questions that we address. First, in order to learn good word representations it is necessary to use an expressive representation of the context. We present a way that uses external knowledge to generate expressive context representations, along with a learning method capable of handling the large number of features generated this way that can, potentially, contribute to each prediction. Second, since the number of words "competing" for each prediction is large, there is a need to "focus the attention" on a smaller subset of these. We exhibit the contribution of a "focus of attention" mechanism to the performance of the word predictor. Finally, we describe a large scale experimental study in which the approach presented is shown to yield significant improvements in word prediction tasks.
Learning to Recognize 3D Objects with SNoW

This paper describes a novel view-based learning algorithm for 3D object recognition from 2D images using a network of linear units. The SNoW learning architecture is a sparse network of linear functions over a pre-defined or incrementally learned feature space and is specifically tailored for learning in the presence of a very large number of features. We use pixel-based and edge-based representations in large scale object recognition experiments in which the performance of SNoW is compared with that of Support Vector Machines (SVMs) and nearest neighbor using the 100 objects in the Columbia Image Object Database (COIL-100). Experimental results show that the SNoW-based method outperforms the SVM-based system in terms of recognition rate and the computational cost involved in learning. Most importantly, SNoW's performance degrades more gracefully when the training data contains fewer views. The empirical results also provide insight into practical and theoretical considerations on view-based methods for 3D object recognition.
Stochastic Greedy Search: Efficiently Computing a Most Probable Explanation in Bayesian Networks

Heuristic search and uncertain information constitute two central Themes in artificial intelligence. This article assumes that the uncertain information is represented in Bayesian networks, and introduces and investigates a novel stochastic heuristic local search algorithm, Stochastic Greedy Search. Stochastic Greedy Search searches for a most probable explanation in a Bayesian network. The innovative aspects of Stochastic Greedy Search, compared to existing local search algorithms, are some of its measures of gain, certain noise operators, certain initialization operators, and an operator- based variant. Stochastic Greedy Search uses noisy steps that allow local search to escape local optima. We introduce different measures of gain(or gradient) and an operator-based approach, giving several ways to search locally. We also introduce two novel dynamic programming based initialization algorithms denoted forward and backward dynamic programming. The initialization algorithms start the local search at points closer to local optima than when search starts from an explanation created uniformly at random. Comparisons to the state-of-the-art inference algorithm Hugin show that Stochastic Greedy Search performs significantly better for Bayesian networks from applications as well as on synthetically generated networks. In synthetic networks, Stochastic Greedy Search speeds up computation up to three orders of magnitude compared to Hugin. In application networks, our initialization algorithms, which compute the most probable explanation in bounding cases, prove to be very valuable.
Learning to recognize objects

A learning account for the problem of object recognition is developed within the PAC (Probably Approximately Correct) model of learnability. The proposed approach makes no assumptions on the distribution of the observed objects, but quantifies success relative to its past experience. Most importantly, the success of learning an object representation is naturally tied to the ability to represent at as a function of some intermediate representations extracted from the image. We evaluate this approach an a large scale experimental study in which the SNoW learning architecture is used to learn representations for the 100 objects in the Columbia Object Image Database (COIL-100). The SNoW-based method is shown to outperform other methods in terms of recognition rates; its performance degrades gracefully when the training data contains fewer views and in the presence of occlusion noise.
Learning in Natural Language: Theory and Algorithmic Approaches

This article summarizes work on developing a learning theory account for the major learning and statistics based approaches used in natural language processing. It shows that these approaches can all be explained using a single distribution free inductive principle related to the pac model of learning. Furthermore, they all make predictions using the same simple knowledge representation - a linear representation over a common feature space. This is significant both to explaining the generalization and robustness properties of these methods and to understanding how these methods might be extended to learn from more structured, knowledge intensive examples, as part of a learning centered approach to higher level natural language inferences.
Coherent Concepts, Robust Learning

We study learning scenarios in which multiple learners are involved and "nature" imposes some constraints that force the predictions of these learners to behave coherently. This is natural in cognitive learning situations, where multiple learning problems co-exist but their predictions are constrained to produce a valid sentence, image or any other domain representation.Our theory addresses two fundamental issues in computational learning: (1) The apparent ease at which cognitive systems seem to learn concepts, relative to what is predicted by the theoretical models, and (2) The robustness of learnable concepts to noise in their input. This type of robustness is very important in cognitive systems, where multiple concepts are learned and cascaded to produce more and more complex features.Existing models of concept learning are extended by requiring the target concept to cohere with other concepts from the concept class. The coherency is expressed via a (Boolean) constraint that the concepts have to satisfy. We show how coherency can lead to improvements in the complexity of learning and to increased robustness of the learned hypothesis.
A SNoW-Based Face Detector

A novel learning approach for human face detection using a network of linear units is presented. The SNoW learning architecture is a sparse network of linear functions over a pre-defined or incrementally learned feature space and is specifically tailored for learning in the presence of a very large number of features. A wide range of face images in different poses, with different expressions and under different lighting conditions are used as a training set to capture the variations of human faces. Experimental results on commonly used benchmark data sets of a wide range of face images show that the SNoW-based approach outperforms methods that use neural networks, Bayesian methods, support vector machines and others. Furthermore, learning and evaluation using the SNoW-based method are significantly more efficient than with other methods.
Reasoning with examples: propositional formulae and database dependencies

For humans, looking at how concrete examples behave is an intuitive way of deriving conclusions. The drawback with this method is that it does not necessarily give the correct results. However, under certain conditions example-based deduction can be used to obtain a correct and complete inference procedure. This is the case for Boolean formulae (reasoning with models) and for certain types of database integrity constraints (the use of Armstrong relations). We show that these approaches are closely related, and use the relationship to prove new results about the existence and size of Armstrong relations for Boolean dependencies. Furthermore, we exhibit close relations between the questions of finding keys in relational databases and that of finding abductive explanations. Further applications of the correspondence between these two approaches are also discussed.
Relational Learning for NLP using Linear Threshold Elements

We describe a coherent view of learning and reasoning with relational representations in the context of natural language processing. In particular, we discuss the Neuroidal Architecture, Inductive Logic Programming and the SNoW system explaining the relationships among these, and thereby offer an explanation of the theoretical basis for the SNoW system. We suggest that extensions of this system along the lines suggested by the theory may provide new levels of scalability and functionality.
A Learning Approach to Shallow Parsing

A SNoW based learning approach to shallow parsing tasks is presented and studied experimentally. The approach learns to identify syntactic patterns by combining simple predictors to produce a coherent inference. Two instantiations of this approach are studied and experimental results for Noun-Phrases (NP) and Subject-Verb (SV) phrases that compare favorably with the best published results are presented. In doing that, we compare two ways of modeling the problem of learning to recognize patterns and suggest that shallow parsing patterns are better learned using open/close predictors than using inside/outside predictors.} thus contribute to the understanding of how to model shallow parsing tasks as learning problems.
Learning Based Programming

Learning Based Programming is a programming paradigm that extends conventional programming to support writing programs in which some of the definitions are generated in a data driven way and some are learned from observations the program encounters. The paper introduces the paradigm as well as the design and implementation of a specific learning based programming language (LBP) within it. LBP allows the programming of complex systems whose behaviors depend on naturally occurring data and that require reasoning about data and concepts in ways that are hard, if not impossible, to write explicitly. In LBP the programmer can reason using high level concepts without the need to explicitly define all the variables they might depend on, or the functional dependencies among them. Instead, LBP supports reasoning in terms of the information sources that might contribute to decisions and allows the specifics to be determined in a data-driven way. We provide the formalisms for the main constructs of the language, including knowledge representations and learning constructs as well as the notions of an interaction and sensors through which an LBP program interacts with its environment. Examples and experimental evidence are given from natural language and visual processing applications.
Learning in Natural Language

Statistics-based classifiers in natural language are developed typically by assuming a generative model for the data, estimating its parameters from training data and then using Bayes rule to obtain a classifier. For many problems the assumptions made by the generative models are evidently wrong, leaving open the question of why these approaches work. 
 
This paper presents a learning theory account of the major statistical approaches to learning in natural language. A class of Linear Statistical Queries (LSQ) hypotheses is defined and learning with it is shown to exhibit some robustness properties. Many statistical learners used in natural language, including naive Bayes, Markov Models and Maximum Entropy models are shown to be LSQ hypotheses, explaining the robustness of these predictors even when the underlying probabilistic assumptions do not hold. This coherent view of when and why learning approaches work in this context may help to develop better learning methods and an understanding of the role of learning in natural language inferences.
Connectionist symbol processing : dead or alive ?

Preface In August 1998 Dave Touretzky asked on the connectionists e-mailing list, \Is connectionist symbol processing dead?" This query lead to an interesting discussion and exchange of ideas. We thought it might be useful to capture this exchange in an article. We solicited contributions, and this collective article is the result. Contributions were solicited by a public call on the connectionists e-mailing list. All contributions received were subjected to two to three informal reviews. Almost all were accepted with varying degrees of revision. Given the number and variety of contributions, the articles cover a wide, though by no means complete, range of the work in the eld. The pieces in this article are of varying nature: position summaries, individual research summaries, historical accounts, discussion of controversial issues, etc. We have not attempted to connect the various pieces together, or to organize them within a coherent framework. Despite this, we think, the reader will nd this collection useful. Implementing symbol processing in networks was a good rst step in solving many problems that plagued symbolic systems. Tony Plate's HRR as applied to analogy is a great example 147]. Using connectionist representations and methodologies, an expensive symbolic similarity estimation process was eliminated in the analogy-making MAC/FAC system 60]. Unfortunately, the entire MAC/FAC hybrid model (like many such models) has a fatal aw that prevents it from leading to an autonomous, exible, creative, intelligent (analogy-making) machine: the overall system organization is still rigidly \symbolic". Their method requires that analogies be encoded as symbols and structures, which leaves no room for perception or context eeects during the analogy making process (for a detailed description of this problem, see Hofstadter 86]). For these reasons, implementing Gentner's rigid framework completely in a neural network (or even real neurons) won't help. Plate's hybrid solution, like most hybrid systems, solved many problems of the MAC/FAC purely-symbolic system. No doubt, hybrid systems are better than their symbolic relatives. However, wherever symbols and structures remain, we seem to be faced with other problems of brittleness and rigidity.
Learning to Resolve Natural Language Ambiguities: A Unified Approach

We analyze a few of the commonly used statistics based and machine learning algorithms for natural language disambiguation tasks and observe that they can be recast as learning linear separators in the feature space. Each of the methods makes a priori assumptions which it employs, given the data, when searching for its hypothesis. Nevertheless, as we show, it searches a space that is as rich as the space of all linear separators. We use this to build an argument for a data driven approach which merely searches for a good linear separator in the feature space, without further assumptions on the domain or a specific problem.We present such an approach - a sparse network of linear separators, utilizing the Winnow learning algorithm - and show how to use it in a variety of ambiguity resolution problems. The learning approach presented is attribute-efficient and, therefore, appropriate for domains having very large number of attributes.In particular, we present an extensive experimental comparison of our approach with other methods on several well studied lexical disambiguation tasks such as context-sensitive spelling correction, prepositional phrase attachment and part of speech tagging. In all cases we show that our approach either outperforms other methods tried for these tasks or performs comparably to the best.
On Learning Read-k-Satisfy-j DNF

We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for $k\cdot j=O({\log n\over\log\log n})$, where n is the number of input variables.