nils-herrmann/clean_scirepeval huggingface dataset:
Spectral techniques for expander codes

This paper introduces methods based on generalized Fourier analysis jor working with a class of errorcorrecting codes constructed in terms of Cayleygmphs. t%r work is motivated by the recent results of Sipser and Spielman  showing graph expansion to be essential for eficient decoding of certain low-density parity-check codes. They leave open the problem of sub-quadratic encoding for this class of codes, and it is this problem that we address. We show that when the codes are constructed in terms of Cayley graphs, the symmetry of the gmphs can be ezploited by using the representation theory of the underlying group to devise a sub-quadmtic encoding algorithm that, in the case where the group is PSLz(Z/qZ), requires 0(n4/3) operations, where n = 0(q3) is the block length. Our results indicate that this new class of codes may combine many of the strengths of two of the most powerful and successful, but previously dispamte areas of coding theory: the class of cyclic codes where the rich algebmic structure yields a large collection of techniques for finding and manipulating the codes, and the class of low-density paritycheck codes which have simple and eficient decoding algorithms and good asymptotic properties.
Cheating with imperfect transcripts

Most speech recognition systems try to reconstruct a word sequence given an acoustic input, using prior information about the language being spoken. In some cases, there is more information available to the decoder than simply the acoustics. When decoding a television news broadcast, for example, the closed-caption information that is often recorded for hearing-impaired viewers may also be available. While these captions are generally not completely accurate transcriptions, they can be considered to be a strong hint as to what was actually spoken. In this paper, we present a formalization of this problem in terms of the source channel paradigm. We propose a simple translation model for mapping caption sequences to word sequences which updates the language model with the prior information inherent in the captions. We also describe an efficient implementation of the search in a Viterbi decoder and present results using this system in the broadcast news domain.
A Robust Parsing Algorithm for Link Grammars

In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by making three dynamic programming passes. In the first pass, the input is parsed using the original algorithm which enforces the constraints on links to ensure grammaticality. In the second pass, the total cost of each substring of words is computed, where cost is determined by the number of null links necessary to parse the substring. The final pass counts the total number of parses with minimal cost. All of the original pruning techniques have natural counterparts in the robust algorithm. When used together with memoization, these techniques enable the algorithm to run efficiently with cubic worst-case complexity. We have implemented these ideas and tested them by parsing the Switchboard corpus of conversational English. This corpus is comprised of approximately three million words of text, corresponding to more than 150 hours of transcribed speech collected from telephone conversations restricted to 70 different topics. Although only a small fraction of the sentences in this corpus are “grammatical” by standard criteria, the robust link grammar parser is able to extract relevant structure for a large portion of the sentences. We present the results of our experiments using this system, including the analyses of selected and random sentences from the corpus. We placed a version of the robust parser on the Word Wide Web for experimentation. It can be reached at URL http://www.cs.cmu.edu/afs/es.emu.edu/project/link/www/robust.html. In this version there are some limitations such as the maximum length of a sentence in words and the maximum amount of memory the parser can use.
Gibbs-markov Models

In this paper we present a framework for building prob-abilistic automata parameterized by context-dependent probabilities. Gibbs distributions are used to model state transitions and output generation, and parameter estimation is carried out using an EM algorithm where the M-step uses a generalized iterative scaling procedure. We discuss relations with certain classes of stochastic feedforward neural networks, a geometric interpretation for parameter estimation, and a simple example of a statistical language model constructed using this methodology .
Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking

Discriminative reranking is one method for constructing high-performance statistical parsers (Collins, 2000). A discriminative reranker requires a source of candidate parses for each sentence. This paper describes a simple yet novel method for constructing sets of 50-best parses based on a coarse-to-fine generative parser (Charniak, 2000). This method generates 50-best lists that are of substantially higher quality than previously obtainable. We used these parses as the input to a MaxEnt reranker (Johnson et al., 1999; Riezler et al., 2002) that selects the best parse from the set of parses for each sentence, obtaining an f-score of 91.0% on sentences of length 100 or less.
Interpolating between types and tokens by estimating power-law generators

Standard statistical models of language fail to capture one of the most striking properties of natural languages: the power-law distribution in the frequencies of word tokens. We present a framework for developing statistical models that generically produce power-laws, augmenting standard generative models with an adaptor that produces the appropriate pattern of token frequencies. We show that taking a particular stochastic process - the Pitman-Yor process - as an adaptor justifies the appearance of type frequencies in formal analyses of natural language, and improves the performance of a model for unsupervised learning of morphology.
Effective Use of Prosody in Parsing Conversational Speech

We identify a set of prosodic cues for parsing conversational speech and show how such features can be effectively incorporated into a statistical parsing model. On the Switchboard corpus of conversational speech, the system achieves improved parse accuracy over a state-of-the-art system which uses only lexical and syntactic features. Since removal of edit regions is known to improve downstream parse accuracy, we explore alternatives for edit detection and show that PCFGs are not competitive with more specialized techniques.
Reviewers for Volume 31

This journal has a knowledgeable and hardworking editorial board, whose members are listed on the inside front cover of each issue, but for most submissions we also enlist the aid of specialist reviewers outside the editorial board. The Editor of Computational Linguistics would like to express his gratitude to the external reviewers listed below who anonymously reviewed papers for the journal during the preparation of this volume (Volume 31). Their generosity, judicious judgment, and prompt response substantially helped us to publish a journal that both is timely and maintains exacting scientific standards; it is a genuine pleasure to thank them collectively for their dedicated service.
Representational Bias in Unsupervised Learning of Syllable Structure

Unsupervised learning algorithms based on Expectation Maximization (EM) are often straightforward to implement and provably converge on a local likelihood maximum. However, these algorithms often do not perform well in practice. Common wisdom holds that they yield poor results because they are overly sensitive to initial parameter values and easily get stuck in local (but not global) maxima. We present a series of experiments indicating that for the task of learning syllable structure, the initial parameter weights are not crucial. Rather, it is the choice of model class itself that makes the difference between successful and unsuccessful learning. We use a language-universal rule-based algorithm to find a good set of parameters, and then train the parameter weights using EM. We achieve word accuracy of 95.9% on German and 97.1% on English, as compared to 97.4% and 98.1% respectively for supervised training.
Multi-component Word Sense Disambiguation

This paper describes the system MC-WSD presented for the English Lexical Sample task. The system is based on a multicomponent architecture. It consists of one classifier with two components. One is trained on the data provided for the task. The second is trained on this data and, additionally, on an external training set extracted from the Wordnet glosses. The goal of the additional component is to lessen sparse data problems by exploiting the information encoded in the ontology.
A TAG-based noisy-channel model of speech repairs

This paper describes a noisy channel model of speech repairs, which can identify and correct repairs in speech transcripts. A syntactic parser is used as the source model, and a novel type of TAG-based transducer is the channel model. The use of TAG is motivated by the intuition that the reparandum is a "rough copy" of the repair. The model is trained and tested on the Switchboard disfluency-annotated corpus.
Reviews: Books, Films, Music

In a series of books, one co-authored with linguist George Lakoff, Mark Johnson has articulated a vision of human thinking that is compelling and important. That vision centers on the key insight that our conceptual frameworks and ways of thinking are structured by metaphors. Often hidden, these metaphors play a central role in our thinking. Johnson draws on emerging interdisciplinary work in cognitive science to support his claims. His views are noteworthy because of their philosophical sophistication, their appeal to contemporary cognitive science, and their focus on one of the most significant philosophical problems of this century: how we can understand human thinking in such a way that we avoid a dangerous and problematic form of objectivism and moral absolutism without falling into an equally dangerous form of relativism. The account of mind that emerges in this account is one that gives central place to the imagination in constructing conceptual frameworks and in making sense of experience. It opposes any account of cognition that does not find a role for imaginative uses of metaphor, similarity, narrative, the framing of descriptions, paradigmatic exemplars of concepts, and so forth. The imaginative uses of these devices takes the place held by rule-governed concepts in more intellectualist accounts of mind and knowledge. But in avoiding what Johnson calls the myth of objectivism (the mind making a mirror of a prestructured world), he also attempts to stear clear of the equally troublesome myth of subjectivism (the mind being free to think whatever it likes).
Discriminative Language Modeling with Conditional Random Fields and the Perceptron Algorithm

This paper describes discriminative language modeling for a large vocabulary speech recognition task. We contrast two parameter estimation methods: the perceptron algorithm, and a method based on conditional random fields (CRFs). The models are encoded as deterministic weighted finite state automata, and are applied by intersecting the automata with word-lattices that are the output from a baseline recognizer. The perceptron algorithm has the benefit of automatically selecting a relatively small feature set in just a couple of passes over the training data. However, using the feature set output from the perceptron algorithm (initialized with their weights), CRF training provides an additional 0.5% reduction in word error rate, for a total 1.8% absolute reduction from the baseline of 39.2%.
Sentence-Internal Prosody Does not Help Parsing the Way Punctuation Does

This paper investigates the usefulness of sentence-internal prosodic cues in syntactic parsing of transcribed speech. Intuitively, prosodic cues would seem to provide much the same information in speech as punctuation does in text, so we tried to incorporate them into our parser in much the same way as punctuation is. We compared the accuracy of a statistical parser on the LDC Switchboard treebank corpus of transcribed sentence-segmented speech using various combinations of punctuation and sentence-internal prosodic information (duration, pausing, and f0 cues). With no prosodic or punctuation information the parser’s accuracy (as measured by F-score) is 86.9%, and adding punctuation increases its F-score to 88.2%. However, all of the ways we have tried of adding prosodic information decrease the parser’s F-score to between 84.8% to 86.8%, depending on exactly which prosodic information is added. This suggests that for sentence-internal prosodic information to improve speech transcript parsing, either different prosodic cues will have to used or they will have be exploited in the parser in a way different to that used currently.
Priors in Bayesian Learning of Phonological Rules

This paper describes a Bayesian procedure for unsupervised learning of phonological rules from an unlabeled corpus of training data. Like Goldsmith's Linguistica program (Goldsmith, 2004b), whose output is taken as the starting point of this procedure, our learner returns a grammar that consists of a set of signatures, each of which consists of a set of stems and a set of suffixes. Our grammars differ from Linguistica's in that they also contain a set of phonological rules, specifically insertion, deletion and substitution rules, which permit our grammars to collapse far more words into a signature than Linguistica can. Interestingly, the choice of Bayesian prior turns out to be crucial for obtaining a learner that makes linguistically appropriate generalizations through a range of different sized training corpora.
Supersense Tagging of Unknown Nouns in WordNet

We present a new framework for classifying common nouns that extends named-entity classification. We used a fixed set of 26 semantic labels, which we called supersenses. These are the labels used by lexicographers developing WordNet. This framework has a number of practical advantages. We show how information contained in the dictionary can be used as additional training data that improves accuracy in learning new nouns. We also define a more realistic evaluation procedure than cross-validation.
DAML Reality Check : A Case Study of KAoS Domain and Policy Services

Description-logic-based knowledge representations and reasoning methods are being used increasingly as the basis for semantically-rich software services. Using such representations and reasoning methods in comprehensive applications is among one of the best ways to identify and understand gaps and limitations. KAoS domain and policy services, which rely extensively on a DAML-based ontology, are used as a case study to investigate an in-depth application of DAML. In this context, we explore the current limitations of DAML semantics. We also describe our observations about the place of ontology description at the heart of KAoS services, and outline requirements for effective interfaces for humans and for translation to and from efficient programming environments. Next, we present the problems implicated by development of ontology descriptions in a distributed dynamic environment. Finally, we assess the utility and maturity of available tools such as editors, programming libraries and inference engines. An application of KAoS to provide policies for DAML-S Web services concludes the paper.
BioSPICE: access to the most current computational tools for biologists.

The goal of the BioSPICE program is to create a framework that provides biologists access to the most current computational tools. At the program midpoint, the BioSPICE member community has produced a software system that comprises contributions from approximately 20 participating laboratories integrated under the BioSPICE Dashboard and a methodology for continued software integration. These contributed software modules are the BioSPICE Dashboard, a graphical environment that combines Open Agent Architecture and NetBeans software technologies in a coherent, biologist-friendly user interface. The current Dashboard permits data sources, models, simulation engines, and output displays provided by different investigators and running on different machines to work together across a distributed, heterogeneous network. Among several other features, the Dashboard enables users to create graphical workflows by configuring and connecting available BioSPICE components. Anticipated future enhancements to BioSPICE include a notebook capability that will permit researchers to browse and compile data to support model building, a biological model repository, and tools to support the development, control, and data reduction of wet-lab experiments. In addition to the BioSPICE software products, a project website supports information exchange and community building.
Learning and Parsing Stochastic Unification-Based Grammars

Stochastic Unification-Based Grammars combine knowledge-rich and data-rich approaches to natural language processing. This provides a rich structure to the learning and parsing (decoding) tasks that can be described with undirected graphical models. While most work to date has treated parsing as a straight-forward multi-class classification problem, we are beginning to see how this structure can be exploited in learning and parsing. Exploiting this structure is likely to become more important as the research focus moves from parsing to more realistic tasks such as machine translation and summarization.
Truncation to Subminimal Words in Early French

<p>It has commonly been proposed that there is a stage in development where children's early productions are binary feet, or minimal words. However, the present study of a French-speaking child (1;1–1;8) finds an extended period where both CVC and disyllabic target words are truncated to CV after initially being produced as reduplicated CiVCiV forms. That is, the child appears to regress, failing to produce disyllabic forms that could be produced earlier. This article proposes an explanation for this apparent regression in terms of segmental-prosodic constraint interaction, where the child's limited segmental inventory, in conjunction with the high frequency of CV lexical items in everyday French, conspire to yield subminimal truncations as "optimal" at this stage in development. These findings provide support for a growing body of literature showing the importance of both constraint interaction and frequency effects in early production, arguing for a more probabilistic approach to theories of language learning.</p> <p> Plusieurs chercheurs ont proposé l'existence d'un stade d'acquisition pendant lequel les productions chez les enfants ont la forme non marquée d'un pied binaire (mots minimaux). Cependant, la présente étude d'un enfant de langue maternelle française (1;1–1;8) révèle une période prolongée où les mots cibles CVC et disyllabiques sont réduits (en formes CV) après avoir été produits comme des formes rédupliquées (CiVCiV). Des analyses plus précises suggèrent que ces troncations résultant en des formes sous-minimales peuvent être expliquées : les interactions de contraintes segmentales et prosodiques, l'inventaire de phonèmes limité de l'enfant et la haute fréquence des mots lexicaux CV en français font en sorte que ces troncations sous-minimales soient optimales à ce stade de développement. Ces résultats sont en accord avec la documentation grandissante montrant l'importance des effets de fréquence dans les stades précoces de la production chez l'enfant et soutiennent une approche probabilistique des théories d'acquisition du langage </p>
Parsing and Disfluency Placement

It has been suggested that some forms of speech disfluencies, most notable interjections and parentheticals, tend to occur disproportionally at major clause boundaries [6] and thus might serve to aid parsers in establishing these boundaries. We have tested a current statistical parser  on Switchboard text with and without interjections and parentheticals and found that the parser performed better when not faced with these extra phenomena. This suggest that for current parsers, at least, interjection and parenthetical placement does not help in the parsing process.
Squibs and Discussions: The DOP Estimation Method is Biased and Inconsistent

A data-oriented parsing or DOP model for statistical parsing associates fragments of linguistic representations with numerical weights, where these weights are estimated by normalizing the empirical frequency of each fragment in a training corpus (see Bod [1998] and references cited therein). This note observes that this estimation method is biased and inconsistent that is, the estimated distribution does not in general converge on the true distribution as the size of the training corpus increases.
Edit Detection and Parsing for Transcribed Speech

We present a simple architecture for parsing transcribed speech in which an edited-word detector first removes such words from the sentence string, and then a standard statistical parser trained on transcribed speech parses the remaining words. The edit detector achieves a misclassification rate on edited words of 2.2%. (The NULL-model, which marks everything as not edited, has an error rate of 5.9%.) To evaluate our parsing results we introduce a new evaluation metric, the purpose of which is to make evaluation of a parse tree relatively indifferent to the exact tree position of EDITED nodes. By this metric the parser achieves 85.3% precision and 86.5% recall.
Joint and Conditional Estimation of Tagging and Parsing Models

This paper compares two different ways of estimating statistical language models. Many statistical NLP tagging and parsing models are estimated by maximizing the (joint) likelihood of the fully-observed training data. However, since these applications only require the conditional probability distributions, these distributions can in principle be learnt by maximizing the conditional likelihood of the training data. Perhaps somewhat surprisingly, models estimated by maximizing the joint were superior to models estimated by maximizing the conditional, even though some of the latter models intuitively had access to "more information".
Unsupervised learning of multi-word verbs

Collocation is a linguistic phenomenon that is difficult to define and harder to explain; it has been largely overlooked in the field of computational linguistics due to its difficulty. Although standard techniques exist for finding collocations, they tend to be rather noisy and suffer from sparse data problems. In this paper, we demonstrate that by utilising parsed input to concentrate on one very specific type of collocation—in this case, verbs with particles, a subset of the socalled “multi-word” verbs—and applying an algorithm to promote those collocations in which we have more confidence, the problems with statistically learning collocations can be overcome.
Compact non-left-recursive grammars using the selective left-corner transform and factoring

The left-corner transform removes left-recursion from (probabilistic) context-free grammars and unification grammars, permitting simple top-down parsing techniques to be used. Unfortunately the grammars produced by the standard left-corner transform are usually much larger than the original. The selective left-corner transform described in this paper produces a transformed grammar which simulates left-corner recognition of a user-specified set of the original productions, and top-down recognition of the others. Combined with two factorizations, it produces non-left-recursive grammars that are not much larger than the original.