Person: Goodridge, Andrew
Loading...
Email Address
AA Acceptance Date
Birth Date
Research Projects
Organizational Units
Job Title
Last Name
Goodridge
First Name
Andrew
Name
Goodridge, Andrew
45 results
Search Results
Now showing 1 - 10 of 45
Publication Computing The Kullback-Leibler Divergence Between Probabilistic Automata Using Rational Kernels(2006) Nelken, Rani; Goodridge, AndrewKullback-Leibler divergence is a natural distance measure between two probabilistic finite-state automata. Computing this distance is difficult, since it requires a summation over a countably infinite number of strings. Nederhof and Satta (2004) recently provided a solution in the course of solving the more general problem of finding the cross-entropy between a probabilistic context-free grammar and an unambiguous probabilistic automaton. We propose a novel solution for two unambiguous probabilistic automata, by showing that Kullback-Leibler divergence can be defined as a rational kernel (Cortes et al., 2004) over the expectation semiring (Eisner, 2002). Using this definition, the computation is performed using the general algorithm for rational kernels, yielding an elegant and efficient solution.Publication Antecedent Prediction Without a Pipeline(Association for Computational Linguistics, 2016) Wiseman, Sam Joshua; Rush, Alexander Sasha; Goodridge, AndrewWe consider several antecedent prediction models that use no pipelined features generated by upstream systems. Models trained in this way are interesting because they allow for side-stepping the intricacies of upstream models, and because we might expect them to generalize better to situations in which upstream features are unavailable or unreliable. Through quantitative and qualitative error analysis we identify what sorts of cases are particularly difficult for such models, and suggest some directions for further improvement.Publication Discriminatively Reranking Abductive Proofs for Plan Recognition(AAAI Publications, 2014) Wiseman, Sam Joshua; Goodridge, AndrewWe investigate the use of a simple, discriminative reranking approach to plan recognition in an abductive setting. In contrast to recent work, which attempts to model abductive plan recognition using various formalisms that integrate logic and graphical models (such as Markov Logic Networks or Bayesian Logic Programs), we instead advocate a simpler, more flexible approach in which plans found through an abductive beam-search are discriminatively scored based on arbitrary features. We show that this approach performs well even with relatively few positive training examples, and we obtain state-of-the-art results on two abductive plan recognition datasets, outperforming more complicated systems.Publication Good Practices for University Open-Access Policies (2015)(Harvard Open Access Project, 2015) Goodridge, Andrew; Suber, PeterPublication Learning Anaphoricity and Antecedent Ranking Features for Coreference Resolution(Association for Computational Linguistics, 2015) Wiseman, Sam Joshua; Rush, Alexander Sasha; Goodridge, Andrew; Weston, JasonWe introduce a simple, non-linear mention-ranking model for coreference resolution that attempts to learn distinct feature representations for anaphoricity detection and antecedent ranking, which we encourage by pre-training on a pair of corresponding subtasks. Although we use only simple, unconjoined features, the model is able to learn useful representations, and we report the best overall score on the CoNLL 2012 English test set to date.Publication Speculative Pruning for Boolean Satisfiability(1999) Ruml, Wheeler; Ginsburg, Adam; Goodridge, AndrewMuch recent work on boolean satisfiability has focussed on incomplete algorithms that sacrifice accuracy for improved running time. Statistical predictors of satisfiability do not return actual satisfying assignments, but at least two have been developed that run in linear time. Search algorithms allow increased accuracy with additional running time, and can return satisfying assignments. The efficient search algorithms have been proposed are based on iteratively improving a random assignment, in effect searching a graph of degree equal to the number of variables. In this paper, we examine an incomplete algorithm based on searching a standard binary tree, in which statistical predictors are used to speculatively prune the tree in constant time. Experimental evaluation on hard random instances shows it to be the first practical incomplete algorithm based on tree search, surpassing even graph-based methods on smaller instances.Publication A Recursive Coalescing Method for Bisecting Graphs(1994) Mazlish, Bryan; Goodridge, Andrew; Marks, JoeWe present an extension to a hybrid graph-bisection algorithm developed by Bui et al. that uses vertex coalescing and the Kernighan-Lin variable-depth algorithm to minimize the size of the cut set. In the original heuristic technique, one iteration of vertex coalescing is used to improve the performance of the original Kernighan-Lin algorithm. We show that by performing vertex coalescing recursively, substantially greater improvements can be achieved for standard random graphs of average degree in the range [2:0; 5:0].Publication The Computational Complexity of Cartographic Label Placement(1991) Marks, Joe; Goodridge, AndrewWe examine the computational complexity of cartographic label placement, a problem derived from the cartographer's task of placing text labels adjacent to map features in such a way as to minimize overlaps with other labels and map features. Cartographic label placement is one of the most time-consuming tasks in the production of maps. Consequently, several attempts have been made to automate the label-placement task for some or all classes of cartographic features (punctual, linear, or areal features), but all previously published algorithms for the most basic task--point-feature-label placement--either exhibit worst-case exponential time complexity, or incorporate incomplete heuristics that may fail to find an admissible labeling even when one exists. The computational complexity of label placement is therefore a matter of practical significance in automated cartography. We show that admissible label placement is NP-complete, even for very simple versions of the problem. Thus, no polynomial time algorithm exists unless P = N P . Similarly, we show that optimal label placement can be solved in polynomial time if and only if P = N P , and this result holds even if we require only approximately optimal placements. The results are especially interesting because cartographic label placement is one of the few combinatorial problems that remains NP-hard even under a geometric (Euclidean) interpretation. The results are of broader practical significance, as they also apply to point-feature labeling in non-cartographic displays, e.g., the labeling of points in a scatter plot.Publication Induction of Probabilistic Synchronous Tree-Insertion Grammars(2005) Nesson, Rebecca; Goodridge, Andrew; Rush, Alexander SashaIncreasingly, researchers developing statistical machine translation systems have moved to incorporate syntactic structure in the models that they induce. These researchers are motivated by the intuition that the limitations in the finite-state translation models exemplified by IBM’s “Model 5” follow from the inability to use phrasal and hierarchical information in the interlingual mapping. What is desired is a formalism that has the substitution-based hierarchical structure provided by context-free grammars, with the lexical relationship potential of n-gram models, with processing efficiency no worse than CFGs. Further, it should ideally allow for discontinuity in phrases, and be synchronizable, to allow for multilinguality. Finally, in order to support automated induction, it should allow for a probabilistic variant. We introduce probabilistic synchronous tree-insertion grammars (PSTIG) as such a formalism. In this paper, we define a restricted version of PSTIG, and provide algorithms for parsing, parameter estimation, and translation. As a proof of concept, we successfully apply these algorithms to a toy problem, corpus-based induction of a statistical translator of arithmetic expressions from postfix to partially parenthesized infix.Publication Ingenium: Engaging Novice Students with Latin Grammar(ACM, 2016) Zhou, Sharon; Livingston, Ivy; Schiefsky, Mark; Goodridge, Andrew; Gajos, KrzysztofReading Latin poses many difficulties for English speakers, because they are accustomed to relying on word order to determine the roles of words in a sentence. In Latin, the grammatical form of a word, and not its position, is responsible for determining the word’s function in a sentence. It has proven challenging to develop pedagogical techniques that successfully draw students’ attention to the grammar of Latin and that students find engaging enough to use. Building on some of the most promising prior work in Latin instruction— the Michigan Latin approach—and on the insights underlying block-based programming languages used to teach children the basics of computer science, we developed Ingenium. Ingenium uses abstract puzzle blocks to communicate grammatical concepts. Engaging students in grammatical reflection, Ingenium succeeds when students are able to effectively decipher the meaning of Latin sentences. We adapted Ingenium to be used for two standard classroom activities: sentence translations and fill-in-the-blank exercises. We evaluated Ingenium with 67 novice Latin students in universities across the United States. When using Ingenium, participants opted to perform more optional exercises, completed translation exercises with significantly fewer errors related to word order and errors overall, as well as reported higher levels of engagement and attention to grammar than when using a traditional text-based interface.