nils-herrmann/clean_scirepeval huggingface dataset:
A Winnow-Based Approach to Context-Sensitive Spelling Correction

A large class of machine-learning problems in natural language require the characterization of linguistic context. Two characteristic properties of such problems are that their feature space is of very high dimensionality, and their target concepts depend on only a small subset of the features in the space. Under such conditions, multiplicative weight-update algorithms such as Winnow have been shown to have exceptionally good theoretical properties. In the work reported here, we present an algorithm combining variants of Winnow and weighted-majority voting, and apply it to a problem in the aforementioned class: context-sensitive spelling correction. This is the task of fixing spelling errors that happen to result in valid words, such as substituting to for too, casual for causal, and so on. We evaluate our algorithm, WinSpell, by comparing it against BaySpell, a statistics-based method representing the state of the art for this task. We find: (1) When run with a full (unpruned) set of features, WinSpell achieves accuracies significantly higher than BaySpell was able to achieve in either the pruned or unpruned condition; (2) When compared with other systems in the literature, WinSpell exhibits the highest performance; (3) While several aspects of WinSpell's architecture contribute to its superiority over BaySpell, the primary factor is that it is able to learn a better linear separator than BaySpell learns; (4) When run on a test set drawn from a different corpus than the training set was drawn from, WinSpell is better able than BaySpell to adapt, using a strategy we will present that combines supervised learning on the training set with unsupervised learning on the (noisy) test set.
A Linear Programming Formulation for Global Inference in Natural Language Tasks

Given a collection of discrete random variables representing outcomes of learned local predictors in natural language. e.g.. named entities and relations. we seek an optimal global assignment to the variables in the presence of general (non-sequential) constraints. Examples of these constraints include the type of arguments a relation can take, and the mutual activity of different relations. etc. We develop a linear programing formulation for this problem and evaluate it in the context of simultaneously learning named entities and relations. Our approach allows us to efficiently incorporate domain and task specific constraints at decision time, resulting in significant improvements in the accuracy and the "human-like" quality of the inferences.
Linear Concepts and Hidden Variables

We study a learning problem which allows for a “fair” comparison between unsupervised learning methods—probabilistic model construction, and more traditional algorithms that directly learn a classification. The merits of each approach are intuitively clear: inducing a model is more expensive computationally, but may support a wider range of predictions. Its performance, however, will depend on how well the postulated probabilistic model fits that data. To compare the paradigms we consider a model which postulates a single binary-valued hidden variable on which all other attributes depend. In this model, finding the most likely value of any one variable (given known values for the others) reduces to testing a linear function of the observed values. We learn the model with two techniques: the standard EM algorithm, and a new algorithm we develop based on covariances. We compare these, in a controlled fashion, against an algorithm (a version of Winnow) that attempts to find a good linear classifier directly. Our conclusions help delimit the fragility of using a model that is even “slightly” simpler than the distribution actually generating the data, vs. the relative robustness of directly searching for a good predictor.
Natural Language Inference via Dependency Tree Mapping: An Application to Question Answering

We describe an approach for answer selection in a free form question answering task. In order to go beyond a key-word based matching in selecting answers to questions, one would like to develop a principled way for the answer selection process that incorporates both syntactic and semantic information. We achieve this goal by (1) representing both questions and candidate passages using dependency trees, augmented with semantic information such as named entities, and (2) computing a generalized edit distance between a candidate passage representation and the question representation, a distance which aims to capture some level of meaning similarity. The sentence that best answers a question is determined to be the one that minimizes the generalized edit distance we define, computed via a dynamic programming based approximate tree matching algorithm. We evaluate the approach on question-answer pairs taken from previous TREC Q/A competitions. Preliminary experiments show its potential by significantly outperforming common bag-of-word scoring methods.
Inference with Classifiers : The Phrase Identification Problem Inference with Classifiers : The Phrase Identification Problem ∗

Machine learning applications often involve learning several different classifiers and combining their outcomes to a global decision in a way that provides a coherent inference that satisfies some constraints. This paper studies three general approaches to this problem concentrating on identifying sequential structure in the text. In all cases, the classifiers’ learning stage is decoupled from the inference stage. The first two models studied are Markovian approaches. One is a generative model that extends standard HMMs and the second is a conditional model; both allow the use of a rich observation structure and of general classifiers to model state-observation dependencies. The last model studied is an extension of constraint satisfaction formalisms. We develop efficient combination algorithms under all models and study them experimentally in the context of identifying the phrase structure of natural language sentences.
On learning visual concepts and DNF formulae

We consider the problem of learning DNF formulae in the mistake-bound and the PAC models. We develop a new approach, which is called polynomial explainability, that is shown to be useful for learning some new subclasses of DNF (and CNF) formulae that were not known to be learnable before. Unlike previous learnability results for DNF (and CNF) formulae, these subclasses are not limited in the number of terms or in the number of variables per term; yet, they contain the subclasses of k-DNF and k-term-DNF (and the corresponding classes of CNF) as special cases. We apply our DNF results to the problem of learning visual concepts and obtain learning algorithms for several natural subclasses of visual concepts that appear to have no natural boolean counterpart. On the other hand, we show that learning some other natural subclasses of visual concepts is as hard as learning the class of all DNF formulae. We also consider the robustness of these results under various types of noise.
Learning via Inference over Structurally Constrained Output

We experimentally analyze learning structured output in a discriminative framework where values of the output variables are estimated by local classifiers. In this framework, complex dependencies among the output variables are captured by constraints that dictate how global labels can be inferred. We compare two strategies, learning plus inference and inference based training, by observing their behaviors in different conditions. We conclude that using inference during learning helps when the local classifiers are difficult to learn but requires more examples.
Learning to detect objects in images via a sparse, part-based representation

We study the problem of detecting objects in still, gray-scale images. Our primary focus is the development of a learning-based approach to the problem that makes use of a sparse, part-based representation. A vocabulary of distinctive object parts is automatically constructed from a set of sample images of the object class of interest; images are then represented using parts from this vocabulary, together with spatial relations observed among the parts. Based on this representation, a learning algorithm is used to automatically learn to detect instances of the object class in new images. The approach can be applied to any object with distinguishable parts in a relatively fixed spatial configuration; it is evaluated here on difficult sets of real-world images containing side views of cars, and is seen to successfully detect objects in varying conditions amidst background clutter and mild occlusion. In evaluating object detection approaches, several important methodological issues arise that have not been satisfactorily addressed in the previous work. A secondary focus of this paper is to highlight these issues, and to develop rigorous evaluation standards for the object detection problem. A critical evaluation of our approach under the proposed standards is presented.
Learning to Reason with a Restricted View

The Learning to Reason framework combines the study of Learning and Reasoning into a single task. Within it, learning is done specifically for the purpose of reasoning with the learned knowledge. Computational considerations show that this is a useful paradigm; in some cases learning and reasoning problems that are intractable when studied separately become tractable when performed as a task of Learning to Reason.In this paper we study Learning to Reason problems where the interaction with the world supplies the learner only partial information in the form of partial assignments. Several natural interpretations of partial assignments are considered and learning and reasoning algorithms using these are developed. The results presented exhibit a tradeoff between learnability, the strength of the oracles used in the interface, and the range of reasoning queries the learner is guaranteed to answer correctly.
Semantic Role Labeling Via Generalized Inference Over Classifiers

We present a system submitted to the CoNLL-2004 shared task for semantic role labeling. The system is composed of a set of classifiers and an inference procedure used both to clean the classification results and to ensure structural integrity of the final role labeling. Linguistic information is used to generate features during classification and constraints for the inference process. Semantic role labeling is a complex task to discover patterns within sentences corresponding to semantic meaning. We believe it is hopeless to expect high levels of performance from either purely manual classifiers or purely learned classifiers. Rather, supplemental linguistic information must be used to support and correct a learning system. The system we present here is composed of two phases.
Learning Hebrew Roots: Machine Learning with Linguistic Constraints

The morphology of Semitic languages is unique in the sense that the major word-formation mechanism is an inherently non-concatenative process of interdigitation, whereby two morphemes, a root and a pattern, are interwoven. Identifying the root of a given word in a Semitic language is an important task, in some cases a crucial part of morphological analysis. It is also a non-trivial task, which many humans find challenging. We present a machine learning approach to the problem of extracting roots of Hebrew words. Given the large number of potential roots (thousands), we address the problem as one of combining several classifiers, each predicting the value of one of the root’s consonants. We show that when these predictors are combined by enforcing some fairly simple linguistics constraints, high accuracy, which compares favorably with human performance on this task, can be achieved.
A Large Deviation Bound for the Area Under the ROC Curve

The area under the ROC curve (AUC) has been advocated as an evaluation criterion for the bipartite ranking problem. We study large deviation properties of the AUC; in particular, we derive a distribution-free large deviation bound for the AUC which serves to bound the expected accuracy of a ranking function in terms of its empirical AUC on an independent test sequence. A comparison of our result with a corresponding large deviation result for the classification error rate suggests that the test sample size required to obtain an ∊-accurate estimate of the expected accuracy of a ranking function with δ-confidence is larger than that required to obtain an ∊-accurate estimate of the expected error rate of a classification function with the same confidence. A simple application of the union bound allows the large deviation bound to be extended to learned ranking functions chosen from finite function classes.
The Role of Semantic Information in Learning Question Classifiers

Classification is commonly used in question answering systems to perform a semantic classification of the target answer in an effort to provide additional information to downstream processes. It is different from the common text categorization task in the sense that questions are relatively short and contain less word-based information compared with classification of the entire text. This work presents a machine learning approach to this task. Our approach is to augment the questions with syntactic and semantic analysis, as well as external semantic knowledge, as input to the text classifier. It is shown that, in the context of question classification, augmenting the input of the classifier with appropriate semantic category information results in significant improvements to classification accuracy.
First-order Probabilistic Inference Revisited

Following ideas in Poole [Poo03], which we correct, formalize and extend, this paper presents the first provable algorithm for reasoning with probabilistic first-order representations at the lifted level. Specifically, the algorithm automates the process of probabilistic reasoning about populations of individuals, their properties and the relations between them, without the need to ground the probabilistic knowledge base. The algorithm makes use of unification to guide an interleaving of variable ordering and first-order variable elimination. Importantly, our contribution includes the formalization of concepts necessary to reason about the algorithm’s correctness and its correctness proof.
Phrasenet: towards context sensitive lexical semantics

This paper introduces PhraseNet, a context-sensitive lexical semantic knowledge base system. Based on the supposition that semantic proximity is not simply a relation between two words in isolation, but rather a relation between them in their context, English nouns and verbs, along with contexts they appear in, are organized in PhraseNet into Consets; Consets capture the nderying lexical concept, and are connected with several semantic relations that respect contextually sensitive lexical information. PhraseNet makes use of WordNet as an important knowledge source. It enhances a WordNet synset with its contextual information and refines its relational structure by maintaining only those relations that respect contextual constraints. The contextual information allows for supporting more functionalities compared with those of WordNet. Natural language researchers as well as linguists and language learners can gain from accessing PhraseNet with a word token and its context, to retrieve relevant semantic information.We describe the design and construction of PhraseNet and give preliminary experimental evidence to its usefulness for NLP researches.
Robust Reading of Ambiguous Writing

A given entity, representing a person, a location or an organization, may be mentioned in text in multiple, ambiguous ways. Understanding natural language requires identifying whether different mentions of a name, within and across documents, represent the same entity. We develop an unsupervised learning approach that is shown to resolve accurately several aspects of the name identity and tracing problem. At the heart of our approach is a generative model of how documents are generated and how names are “sprinkled” into them; in particular, we model appearance similarity between names representing the same entity, contextual correlation among entities, and co-occurrence probabilities of entities within a document. We show how to estimate the model and do inference with it and how this resolves several aspects of the problem from the perspective of applications such as questions answering.
Margin distribution and learning algorithms

Recent theoretical results have shown that improved bounds on generalization error of classifiers can be obtained by explicitly taking the observed margin distribution of the training data into account. Currently, algorithms used in practice do not make use of the margin distribution and are driven by optimization with respect to the points that are closest to the hyperplane. 
 
This paper enhances earlier theoretical results and derives a practical data-dependent complexity measure for learning. The new complexity measure is a function of the observed margin distribution of the data, and can be used, as we show, as a model selection criterion. We then present the Margin Distribution Optimization (MDO) learning algorithm, that directly optimizes this complexity measure. Empirical evaluation of MDO demonstrates that it consistently outperforms SVM.
New algorithms for attribute-efficient on-line linear learning

This thesis describes an investigation of old and new on-line linear learning algorithms and their attribute-efficiency properties. When large amounts of irrelevent information, in the form of noninformative attributes, is given to some on-line learning algorithms, the number of prediction errors for particular concept classes rises drastically. Other learners, those with the property of attribute-efficiency, incur only a small increase in errors. 
The Winnow algorithm class is attribute-efficient, and is a standard alternative to the non-attribute-efficient Perceptron algorithm commonly used to learn on-line linear concepts (Littlestone 1988, Littlestone 1989, Kivenen et al. 1997, Blum 1995, Golding and Roth, 1999). Recent work has identified the Incremental Delta-Bar-Delta (IDBD) algorithm as probably attribute-efficient (Harris and Reichler 2001, Harris 2002). IDBD was proposed by Sutton (1992) as an on-line linear learning algorithm that learns particularly quickly. A major component of this thesis is to argue that IDBD is actually attribute-efficient, and to identify which components of the algorithm underly that property. 
A set of IDBD variations is introduced, allowing targeted experimental work and tractable theoretical work. The most important new algorithm is Second-order Perceptron, exponential and symmetric (2Pes), which omits a complicating factor from IDBD, but improves upon IDBD's attribute-efficiency. 
Two proofs of attribute-efficiency are reported. In one, the 2Pes algorithm is shown to be attribute-efficient to the same extent as Winnow. In the other, another variation on IDBD and 2Pes is shown to have a lesser level of attribute-efficiency. Experimental results support this theoretical work, showing attribute-efficiency for 2Pes that often provides better results than even Winnow. Other experiments identify subtleties important to understanding the relative strengths and weaknesses of each algorithm. 
Another significant goal of this work was to identify the inductive biases of each algorithm, so that they can be fairlycompared with each other. By examining their biases and properties using the results presented here, it is possible to view 2Pes as a particular generalization of the Winnow algorithm, and IDBD as a further generalization of 2Pes. Understanding these relationships furthers the potential of attribute-efficient algorithms for real-world applications.
Proceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 1

On behalf of the program committee for ACL-2003, consisting of 12 area chairs and two program committee co-chairs, we are pleased to present you with this volume. It contains the papers accepted for presentation in the main conference program of the 41st Annual Meeting of the Association for Computational Linguistics held in Sapporo, Japan on July 7-12, 2003.The 41st Annual Meeting of the Association for Computational Linguistics consists of the main program, a student workshop, interactive poster/demo sessions, ten pre- and post-conference workshops, and four tutorials. Associated conferences for ACL-2003 include The Eighth Conference on Empirical Methods in Natural Language Processing (EMNLP2003) and the Sixth International Workshop on Information Retrieval with Asian Languages (IRAL2003). These workshops and associated conferences have published separate proceedings that are available at the conference or from the ACL office (http://www.aclweb.org/).This year, 360 papers were submitted for the main program of the meeting, from which 71 were accepted for presentation and inclusion in the conference proceedings. An acceptance rate of 19.72% makes ACL-2003 one of the most selective international conferences of the year. Among the accepted papers, 32 come from North America and Canada, 22 from Asia and the Pacific Rim area, and 17 from Europe. As a whole, the accepted papers provide a unique overview of cutting-edge research in the field of Computational Linguistics conducted at present.
On Kernel Methods for Relational Learning

Kernel methods have gained a great deal of popularity in the machine learning community as a method to learn indirectly in high-dimensional feature spaces. Those interested in relational learning have recently begun to cast learning from structured and relational data in terms of kernel operations. 
 
We describe a general family of kernel functions built up from a description language of limited expressivity and use it to study the benefits and drawbacks of kernel learning in relational domains. Learning with kernels in this family directly models learning over an expanded feature space constructed using the same description language. This allows us to examine issues of time complexity in terms of learning with these and other relational kernels, and how these relate to generalization ability. The tradeoffs between using kernels in a very high dimensional implicit space versus a restricted feature space, is highlighted through two experiments, in bioinformatics and in natural language processing.
Machine learning for information extraction

The dissertation presents a number of novel machine learning techniques and applies them to information extraction. The study addresses several information extraction subtasks: part of speech tagging, entity extraction, coreference resolution, and relation extraction. Each of the tasks is formalized as a learning problem and appropriate learning algorithms are developed and applied to the problem. The dissertation studies part of speech tagging as a multi-class classification problem, and applies the SNOW (Sparse Network of Winnows) learning system to learn a part of speech classifier. A comprehensive experimental evaluation of the system confirms that it is appropriate for NLP applications. The dissertation addresses the problem of entity extraction is conjunction with coreference resolution. A classification approach is presented for entity extraction, and coreference resolution is treated from the decoding perspective. The dissertation describes novel decoding algorithms that given local coreference decisions produce a global coherent interpretation of document entities. The dissertation studies the problem of relation extraction as a classification problem, and applies kernel methods to learn the relation classifiers. Novel kernels are defined in terms of shallow parses, and efficient algorithms are given for computing the kernels. The study evaluates the kernel approach experimentally, with positive results. The dissertation combines the constituent solutions to present a single coherent information extraction system and concludes that machine learning is a viable methodology for designing natural language processing applications.