563 research outputs found
A Flexible Solver for Finite Arithmetic Circuits
No full textArithmetic circuits arise in the context of weighted logic programming languages, such as Datalog with aggregation, or Dyna. A weighted logic program defines a generalized arithmetic circuit—the weighted version of a proof forest, with nodes having arbitrary rather than boolean values. In this paper, we focus on finite circuits. We present a flexible algorithm for efficiently querying
node values as they change under updates to the circuit's inputs. Unlike traditional algorithms, ours is agnostic about which nodes are tabled (materialized), and can vary smoothly between the traditional strategies of forward and backward chaining. Our algorithm is designed to admit future generalizations, including cyclic and infinite circuits and propagation of delta updates
Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars
No full textSeveral recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n 4 ) parsing algorithms for two bilexical formalisms, improving the previous upper bounds of O(n 5 ). Also, for a common special case that was known to allow O(n 3 ) parsing (Eisner, 1997), we present an O(n 3 ) algorithm with an improved grammar constant. 1 Introduction Lexicalized grammar formalisms are of both theoretical and practical interest to the computational linguistics community. Such formalisms specify syntactic facts about each word of the language---in particular, the type of arguments that the word can or must take. Early mechanisms of this sort included categorial grammar (BarHillel, 1953) and subcategorization frames (Chomsky, 1965). Other lexicalized formalisms include (Schabes et al., 1988; Mel'cuk, 1988; Pollard and Sag, 1994). Besides the possible arguments of a word, a natural-language gra..
FootForm Decomposed: Using primitive constraints in OT
No full textHayes (1995) gives a typology of the world's metrical stress systems, which is marked by several striking asymmetries (parametric gaps). Most work on metrical stress within Optimality Theory (OT) has adopted this typology without explaining the gaps. Moreover, the OT versions use uncomfortably non-local constraints (Align, FootForm, FtBin).
This paper presents a rather different and in some ways more explanatory typology of stress, couched in the restrictive framework of primitive Optimality Theory (OTP), which allows only primitive, radically local constraints. For example, Generalized Alignment is not allowed. The paper presents a single, coherent system of rerankable constraints that yields the basic facts about iambic and trochaic foot form, iambic lengthening, quantity sensitivity, unbounded feet, simple word-initial and word-final stress, directionality of footing, syllable (and foot) extrametricality, degenerate feet, and word-level stress.
The metrical part of the account rests on the following intuitions:
(a) iambs are special because syllable structure allows them to lengthen their strong ends;
(b) directionality of footing is really the result of local lapse avoidance;
(c) any lapses are forced by a (localist) generalization of right extrametricality;
(d) degenerate feet are absolutely banned, but primary stress does not require a foot in all languages.
An interesting prediction of (b) and (c) is that left-to-right trochees should be incompatible with extrametricality. This prediction is robustly confirmed in Hayes.The definitive version of this paper was published in the Proceedings of the 8th Student Conference in Linguistics (1997) and is available at http://mitwpl.mit.edu/catalog/mwpl31/Eisner, J. (1997). FootForm decomposed: Using primitive constraints in OT. In B. Bruening (Ed.) Proceedings of the 8th Student Conference in Linguistics (pp. 115-143). Cambridge, MA: Department of Linguistics and Philosophy, Massachusetts Institute of Technology.This material is based upon work supported under a National Science Foundation Graduate Fellowship
An Empirical Comparison of Probability Models for Dependency Grammar
No full textThis technical report is an appendix to Eisner (1996): it gives superior experimental results that were reported only in the talk version of that paper, with details of how the results were obtained. Eisner (1996) trained three probability models on a small set of about 4,000 conjunction-free, dependencygrammar parses derived from the Wall Street Journal section of the Penn Treebank, and then evaluated the models on a held-out test set, using a novel O(n³) parsing algorithm. The present paper describes some details of the experiments and repeats them with a larger training set of 25,000 sentences. As reported at the talk, the more extensive training yields greatly improved performance, cutting in half the error rate of Eisner (1996). Nearly half the sentences are parsed with no misattachments; two-thirds of sentences are parsed with at most one misattachment. Of the models described in the original paper, the best score is obtained with the generative "model C," which attaches 87--..
Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars
No full textSeveral recent stochastic parsers use bilexical grammars � where each word type idiosyncrat� ically prefers particular complements with particular head words. We present O�n 4 � parsing algorithms for two bilexical formalisms � improv� ing the prior upper bounds of O�n 5 �. For a common special case that was known to allow O(n³) parsing �Eisner � 1997� � we present an O(n³) algorithm with an improved grammar constant
Rewriting Dante: The Creation of an Author from the Middle Ages to Modernity
No full textRewriting Dante explores Dante’s reception and the construction of his figure as an author in early lyric anthologies and modern editions. While Dante’s reception and his transformation into a cultural authority have traditionally been investigated from the point of view of the Commedia, I argue that these lyric anthologies provide a new perspective for understanding how the physical act of rewriting Dante’s poems in various combinations and with other texts has shaped what I call after Foucault the "Dante-function” and consecrated Dante as an author from the Middle Ages to Modernity. The study of these lyric anthologies widens our understanding of the process of Dante’s canonization as an author and, thus, as an authority (auctor & auctoritas), advancing our awareness of authors both as entities that generate power and that are generated by power. By addressing the creation of his authoritative figure from its inception, this study sheds light on cultural production, both as a collective, almost anonymous, process and as a result of the intervention of prominent (and less prominent) individuals. By concentrating on the part of Dante’s oeuvre that may be considered less authoritative, that is, his lyric poetry, my study emphasizes aspects of the “Dante-function” that go unobserved when focusing exclusively on the Commedia. This research interweaves the critical discourses related to the emergence of the author in the Late Middle Ages (Minnis, Ascoli, Auctor et Auctoritas) and the birth of the songbook as a literary genre (Barolini, Bertolucci Pizzorusso, Galvez, Holmes), also touching on the twentieth-century alleged ‘death of the author’ (Barthes, Foucault, Benedetti). I concentrate on the crucial function of editors and anthologists as mediators in the canonization of Dante through the material construction of manuscripts and books. This question has led me to explore canon making as a structure of power and the interplay of cultural hegemonies in its creation. I approach this problem through the lens of material philology because it is a productive interdisciplinary methodology, as is seen in the work of historians of the book McKenzie and Petrucci, and literary critics Eisner, Storey, and Nichols.</p
�Ì�ÜØÓ�Ø��×ÔÖ�ÔÖ�ÒØÑ�Ý�����Ö×Ð���ØÐÝ�×�Ó��ÔØ�ÖÔ���ÒÓ×℄ �ÖÓÑÀ�ÖÖÝ��ÙÒØ�Ò��ÒØÓÒÆ���ÓÐØ�� × New Developments in Natural Language Parsing ÃÐÙÛ�Ö����Ñ�ÈÙ�Ð�×��Ö× Chapter 1 BILEXICAL GRAMMARS AND THEIR CUBIC-TIME PARSING ALGORITHMS
No full textAbstract This chapter introduces weighted bilexical grammars, a formalism in which individual lexical items, such as verbs and their arguments, can have idiosyncratic selectional influences on each other. Such ‘bilexicalism ’ has been a theme of much current work in parsing. The new formalism can be used to describe bilexical approaches to both dependency and phrase-structure grammars, and a slight modification yields link grammars. Its scoring approach is compatible with a wide variety of probability models. The obvious parsing algorithm for bilexical grammars (used by most previous authors) takes timeÇÒ�. A more efficientÇÒmethod is exhibited. The new algorithm has been implemented and used in a large parsing experiment (Eisner, 1996b). We also give a useful extension to the case where the parser must undo a stochastic transduction that has altered the input. 1
Chapter 1 BILEXICAL GRAMMARS AND THEIR CUBIC-TIME PARSING ALGORITHMS
No full textAbstract This chapter introduces weighted bilexical grammars, a formalism in which individual lexical items, such as verbs and their arguments, can have idiosyncratic selectional influences on each other. Such ‘bilexicalism ’ has been a theme of much current work in parsing. The new formalism can be used to describe bilexical approaches to both dependency and phrase-structure grammars, and a slight modification yields link grammars. Its scoring approach is compatible with a wide variety of probability models. The obvious parsing algorithm for bilexical grammars (used by most previous authors) takes time O(n 5). A more efficient O(n 3) method is exhibited. The new algorithm has been implemented and used in a large parsing experiment (Eisner, 1996b). We also give a useful extension to the case where the parser must undo a stochastic transduction that has altered the input
Annealing structural bias in multilingual weighted grammar induction
No full textWe first show how a structural locality bias can improve the accuracy of state-of-the-art dependency grammar induction models trained by EM from unannotated examples (Klein and Manning, 2004). Next, by annealing the free parameter that controls this bias, we achieve further improvements. We then describe an alternative kind of structural bias, toward “broken ” hypotheses consisting of partial structures over segmented sentences, and show a similar pattern of improvement. We relate this approach to contrastive estimation (Smith and Eisner, 2005a), apply the latter to grammar induction in six languages, and show that our new approach improves accuracy by 1–17 % (absolute) over CE (and 8–30% over EM), achieving to our knowledge the best results on this task to date. Our method, structural annealing, is a general technique with broad applicability to hidden-structure discovery problems.
Guiding unsupervised grammar induction using contrastive estimation
No full textWe describe a novel training criterion for probabilistic grammar induction models, contrastive estimation [Smith and Eisner, 2005], which can be interpreted as exploiting implicit negative evidence and includes a wide class of likelihood-based objective functions. This criterion is a generalization of the function maximized by the Expectation-Maximization algorithm [Dempster et al., 1977]. CE is a natural fit for log-linear models, which can include arbitrary features but for which EM is computationally difficult. We show that, using the same features, log-linear dependency grammar models trained using CE can drastically outperform EMtrained generative models on the task of matching human linguistic annotations (the MATCHLIN-GUIST task). The selection of an implicit negative evidence class—a “neighborhood”—appropriate to a given task has strong implications, but a good neighborhood one can target the objective of grammar induction to a specific application.
- …
