Есептеу күрделілігі
Related Papers
Fast Statistical Grammar Induction
The statistical induction of context free grammars from bracketed cor- pora with the Inside Outside Algorithm has often inspired researchers, but the computational complexity has made it impossible to generate …...
Parsing with Semidirectional Lambek Grammar is NP-Complete
We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SD[ there is an additional non- …...
Effect of Cross-Language IR in Bilingual Lexicon Acquisition from Comparable Corpora
Within the framework of translation knowledge acquisition from WWW news sites, this paper studies issues on the effect of cross-language retrieval of relevant texts in bilingual lexicon ac- quisition from …...
Computational Complexity of Statistical Machine Translation
In this paper we study a set of prob- lems that are of considerable importance to Statistical Machine Translation (SMT) but which have not been addressed satis- factorily by the …...
Disambiguating Main POS tags for Turkish
This paper presents the results of main part-of-speech tagging of Turkish sentences using Conditional Ran- dom Fields (CRFs). Although CRFs are applied to many different languages for part-of-speech (POS) tagging, …...
The complexity of finding the maximum spanning DAG and other restrictions for DAG parsing of natural language
Recently, there has been renewed interest in semantic dependency parsing, among which one of the paradigms focuses on parsing di- rected acyclic graphs (DAGs). Considera- tion of the decoding problem …...
Recurrent Neural Networks as Weighted Language Recognizers
AbstractWe investigate the computational complexity of various problems for simple recurrent neural networks (RNNs) as formal models for recognizing weighted languages. We focus on the single-layer, ReLU-activation, rational-weight RNNs with …...
Accelerated High-Quality Mutual-Information Based Word Clustering
AbstractWord clustering groups words that exhibit similar properties. One popular method for this is Brown clustering, which uses short-range distributional information to construct clusters. Specifically, this is a hard hierarchical …...
Tired of Topic Models? Clusters of Pretrained Word Embeddings Make for Fast and Good Topics too!
AbstractTopic models are a useful analysis tool to uncover the underlying themes within document collections. The dominant approach is to use probabilistic topic models that posit a generative story, but …...
Masking and Transformer-based Models for Hyperpartisanship Detection in News
AbstractHyperpartisan news show an extreme manipulation of reality based on an underlying and extreme ideological orientation. Because of its harmful effects at reinforcing one’s bias and the posterior behavior of …...
PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols
AbstractProbabilistic context-free grammars (PCFGs) with neural parameterization have been shown to be effective in unsupervised phrase-structure grammar induction. However, due to the cubic computational complexity of PCFG representation and parsing, …...