waashk/dblp huggingface dataset:
budget constrained auctions with heterogeneous items. in this paper, we present the first approximation algorithms for the problem of designing revenue optimal bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have arbitrary demand and budget constraints (and additive valuations). our mechanisms are surprisingly simple: we show that a sequential all-pay mechanism is a 4 approximation to the revenue of the optimal ex-interim truthful mechanism with a discrete type space for each bidder, where her valuations for different items can be correlated. we also show that a sequential posted price mechanism is a o(1) approximation to the revenue of the optimal ex-post truthful mechanism when the type space of each bidder is a product distribution that satisfies the standard hazard rate condition. we further show a logarithmic approximation when the hazard rate condition is removed, and complete the picture by showing that achieving a sub-logarithmic approximation, even for regular distributions and one bidder, requires pricing bundles of items. our results are based on formulating novel lp relaxations for these problems, and developing generic rounding schemes from first principles.
improving exhaustive search implies superpolynomial lower bounds. the p vs np problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. we still do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all np problems, and to date no major consequences have been derived from the assumption that an improvement exists. we show that there are natural np and bpp problems for which minor algorithmic improvements over the trivial deterministic simulation already entail lower bounds such as nexp is not in p/poly and logspace is not equal to np. these results are especially interesting given that similar improvements have been found for many other hard problems. optimistically, one might hope our results suggest a new path to lower bounds; pessimistically, they show that carrying out the seemingly modest program of finding slightly better algorithms for all search problems may be extremely difficult (if not impossible). we also prove unconditional superpolynomial time-space lower bounds for improving on exhaustive search.
cross-lingual semantic relatedness using encyclopedic knowledge. in this paper, we address the task of crosslingual semantic relatedness. we introduce a method that relies on the information extracted from wikipedia, by exploiting the interlanguage links available between wikipedia versions in multiple languages. through experiments performed on several language pairs, we show that the method performs well, with a performance comparable to monolingual measures of relatedness.
weighted alignment matrices for statistical machine translation. current statistical machine translation systems usually extract rules from bilingual corpora annotated with 1-best alignments. they are prone to learn noisy rules due to alignment mistakes. we propose a new structure called weighted alignment matrix to encode all possible alignments for a parallel text compactly. the key idea is to assign a probability to each word pair to indicate how well they are aligned. we design new algorithms for extracting phrase pairs from weighted alignment matrices and estimating their probabilities. our experiments on multiple language pairs show that using weighted matrices achieves consistent improvements over using n-best lists in significant less extraction time.
non-projective parsing for statistical machine translation. we describe a novel approach for syntax-based statistical mt, which builds on a variant of tree adjoining grammar (tag). inspired by work in discriminative dependency parsing, the key idea in our approach is to allow highly flexible reordering operations during parsing, in combination with a discriminative model that can condition on rich features of the source-language string. experiments on translation from german to english show improvements over phrase-based systems, both in terms of bleu scores and in human evaluations.
simple coreference resolution with rich syntactic and semantic features. coreference systems are driven by syntactic, semantic, and discourse constraints. we present a simple approach which completely modularizes these three aspects. in contrast to much current work, which focuses on learning and on the discourse component, our system is deterministic and is driven entirely by syntactic and semantic compatibility as learned from a large, unlabeled corpus. despite its simplicity and discourse naivete, our system substantially outperforms all unsupervised systems and most supervised ones. primary contributions include (1) the presentation of a simple-to-reproduce, high-performing baseline and (2) the demonstration that most remaining errors can be attributed to syntactic and semantic factors external to the coreference phenomenon (and perhaps best addressed by non-coreference systems).
graph alignment for semi-supervised semantic role labeling. unknown lexical items present a major obstacle to the development of broad-coverage semantic role labeling systems. we address this problem with a semi-supervised learning approach which acquires training instances for unseen verbs from an unlabeled corpus. our method relies on the hypothesis that unknown lexical items will be structurally and semantically similar to known items for which annotations are available. accordingly, we represent known and unknown sentences as graphs, formalize the search for the most similar verb as a graph alignment problem and solve the optimization using integer linear programming. experimental results show that role labeling performance for unknown lexical items improves with training data produced automatically by our method.
active learning by labeling features. methods that learn from prior information about input features such as generalized expectation (ge) have been used to train accurate models with very little effort. in this paper, we propose an active learning approach in which the machine solicits "labels" on features rather than instances. in both simulated and real user experiments on two sequence labeling tasks we show that our active learning method outperforms passive learning with features as well as traditional active learning with instances. preliminary experiments suggest that novel interfaces which intelligently solicit labels on multiple features facilitate more efficient annotation.
global learning of noun phrase anaphoricity in coreference resolution via label propagation. knowledge of noun phrase anaphoricity might be profitably exploited in coreference resolution to bypass the resolution of non-anaphoric noun phrases. however, it is surprising to notice that recent attempts to incorporate automatically acquired anaphoricity information into coreference resolution have been somewhat disappointing. this paper employs a global learning method in determining the anaphoricity of noun phrases via a label propagation algorithm to improve learning-based coreference resolution. in particular, two kinds of kernels, i.e. the feature-based rbf kernel and the convolution tree kernel, are employed to compute the anaphoricity similarity between two noun phrases. experiments on the ace 2003 corpus demonstrate the effectiveness of our method in anaphoricity determination of noun phrases and its application in learning-based coreference resolution.
on the role of lexical features in sequence labeling. we use the technique of svm anchoring to demonstrate that lexical features extracted from a training corpus are not necessary to obtain state of the art results on tasks such as named entity recognition and chunking. while standard models require as many as 100k distinct features, we derive models with as little as 1k features that perform as well or better on different domains. these robust reduced models indicate that the way rare lexical features contribute to classification in nlp is not fully understood. contrastive error analysis (with and without lexical features) indicates that lexical features do contribute to resolving some semantic and complex syntactic ambiguities -- but we find this contribution does not generalize outside the training corpus. as a general strategy, we believe lexical features should not be directly derived from a training corpus but instead, carefully inferred and selected from other sources.
discriminative substring decoding for transliteration. we present a discriminative substring decoder for transliteration. this decoder extends recent approaches for discriminative character transduction by allowing for a list of known target-language words, an important resource for transliteration. our approach improves upon sherif and kondrak's (2007b) state-of-the-art decoder, creating a 28.5% relative improvement in transliteration accuracy on a japanese katakana-to-english task. we also conduct a controlled comparison of two feature paradigms for discriminative training: indicators and hybrid generative features. surprisingly, the generative hybrid outperforms its purely discriminative counterpart, despite losing access to rich source-context features. finally, we show that machine transliterations have a positive impact on machine translation quality, improving human judgments by 0.5 on a 4-point scale.
supervised learning of a probabilistic lexicon of verb semantic classes. the work presented in this paper explores a supervised method for learning a probabilistic model of a lexicon of verbnet classes. we intend for the probabilistic model to provide a probability distribution of verb-class associations, over known and unknown verbs, including polysemous words. in our approach, training instances are obtained from an existing lexicon and/or from an annotated corpus, while the features, which represent syntactic frames, semantic similarity, and selectional preferences, are extracted from unannotated corpora. our model is evaluated in type-level verb classification tasks: we measure the prediction accuracy of verbnet classes for unknown verbs, and also measure the dissimilarity between the learned and observed probability distributions. we empirically compare several settings for model learning, while we vary the use of features, source corpora for feature extraction, and disam-biguated corpora. in the task of verb classification into all verbnet classes, our best model achieved a 10.69% error reduction in the classification accuracy, over the previously proposed model.
language models based on semantic composition. in this paper we propose a novel statistical language model to capture long-range semantic dependencies. specifically, we apply the concept of semantic composition to the problem of constructing predictive history representations for upcoming words. we also examine the influence of the underlying semantic space on the composition task by comparing spatial semantic representations against topic-based ones. the composition models yield reductions in perplexity when combined with a standard n-gram language model over the n-gram model alone. we also obtain perplexity reductions when integrating our models with a structured language model.
sinuhe - statistical machine translation using a globally trained conditional exponential family translation model. we present a new phrase-based conditional exponential family translation model for statistical machine translation. the model operates on a feature representation in which sentence level translations are represented by enumerating all the known phrase level translations that occur inside them. this makes the model a good match with the commonly used phrase extraction heuristics. the model's predictions are properly normalized probabilities. in addition, the model automatically takes into account information provided by phrase overlaps, and does not suffer from reference translation reachability problems. we have implemented an open source translation system sinuhe based on the proposed translation model. our experiments on europarl and gigafren corpora demonstrate that finding the unique map parameters for the model on large scale data is feasible with simple stochastic gradient methods. sinuhe is fast and memory efficient, and the bleu scores obtained by it are only slightly inferior to those of moses.
multi-word expression identification using sentence surface features. much nlp research on multi-word expressions (mwes) focuses on the discovery of new expressions, as opposed to the identification in texts of known expressions. however, mwe identification is not trivial because many expressions allow variation in form and differ in the range of variations they allow. we show that simple rule-based baselines do not perform identification satisfactorily, and present a supervised learning method for identification that uses sentence surface features based on expressions' canonical form. to evaluate the method, we have annotated 3350 sentences from the british national corpus, containing potential uses of 24 verbal mwes. the method achieves an f-score of 94.86%, compared with 80.70% for the leading rule-based baseline. our method is easily applicable to any expression type. experiments in previous research have been limited to the compositional/non-compositional distinction, while we also test on sentences in which the words comprising the mwe appear but not as an expression.
learning linear ordering problems for better translation. we apply machine learning to the linear ordering problem in order to learn sentence-specific reordering models for machine translation. we demonstrate that even when these models are used as a mere preprocessing step for german-english translation, they significantly outperform moses' integrated lexicalized reordering model. our models are trained on automatically aligned bitext. their form is simple but novel. they assess, based on features of the input sentence, how strongly each pair of input word tokens wi, wj would like to reverse their relative order. combining all these pairwise preferences to find the best global reordering is np-hard. however, we present a non-trivial o(n3) algorithm, based on chart parsing, that at least finds the best reordering within a certain exponentially large neighborhood. we show how to iterate this reordering process within a local search algorithm, which we use in training.
latent document re-ranking. the problem of re-ranking initial retrieval results exploring the intrinsic structure of documents is widely researched in information retrieval (ir) and has attracted a considerable amount of time and study. however, one of the drawbacks is that those algorithms treat queries and documents separately. furthermore, most of the approaches are predominantly built upon graph-based methods, which may ignore some hidden information among the retrieval set. this paper proposes a novel document re-ranking method based on latent dirichlet allocation (lda) which exploits the implicit structure of the documents with respect to original queries. rather than relying on graph-based techniques to identify the internal structure, the approach tries to find the latent structure of "topics" or "concepts" in the initial re-trieval set. then we compute the distance between queries and initial retrieval results based on latent semantic information deduced. empirical results demonstrate that the method can comfortably achieve significant improvement over various baseline systems.
graded word sense assignment. word sense disambiguation is typically phrased as the task of labeling a word in context with the best-fitting sense from a sense inventory such as wordnet. while questions have often been raised over the choice of sense inventory, computational linguists have readily accepted the best-fitting sense methodology despite the fact that the case for discrete sense boundaries is widely disputed by lexical semantics researchers. this paper studies graded word sense assignment, based on a recent dataset of graded word sense annotation.
chinese novelty mining. automated mining of novel documents or sentences from chronologically ordered documents or sentences is an open challenge in text mining. in this paper, we describe the preprocessing techniques for detecting novel chinese text and discuss the influence of different part of speech (pos) filtering rules on the detection performance. experimental results on apwsj and trec 2004 novelty track data show that the chinese novelty mining performance is quite different when choosing two dissimilar pos filtering rules. thus, the selection of words to represent chinese text is of vital importance to the success of the chinese novelty mining. moreover, we compare the chinese novelty mining performance with that of english and investigate the impact of preprocessing steps on detecting novel chinese text, which will be very helpful for developing a chinese novelty mining system.
classifying relations for biomedical named entity disambiguation. named entity disambiguation concerns linking a potentially ambiguous mention of named entity in text to an unambiguous identifier in a standard database. one approach to this task is supervised classification. however, the availability of training data is often limited, and the available data sets tend to be imbalanced and, in some cases, heterogeneous. we propose a new method that distinguishes a named entity by finding the informative keywords in its surrounding context, and then trains a model to predict whether each keyword indicates the semantic class of the entity. while maintaining a comparable performance to supervised classification, this method avoids using expensive manually annotated data for each new domain, and thus achieves better portability.
parser adaptation and projection with quasi-synchronous grammar features. we connect two scenarios in structured learning: adapting a parser trained on one corpus to another annotation style, and projecting syntactic annotations from one language to another. we propose quasi-synchronous grammar (qg) features for these structured learning tasks. that is, we score a aligned pair of source and target trees based on local features of the trees and the alignment. our quasi-synchronous model assigns positive probability to any alignment of any trees, in contrast to a synchronous grammar, which would insist on some form of structural parallelism. in monolingual dependency parser adaptation, we achieve high accuracy in translating among multiple annotation styles for the same sentence. on the more difficult problem of cross-lingual parser projection, we learn a dependency parser for a target language by using bilingual text, an english parser, and automatic word alignments. our experiments show that unsupervised qg projection improves on parses trained using only high-precision projected annotations and far outperforms, by more than 35% absolute dependency accuracy, learning an unsupervised parser from raw target-language text alone. when a few target-language parse trees are available, projection gives a boost equivalent to doubling the number of target-language trees.
geo-mining: discovery of road and transport networks using directional patterns. one of the most desired information types when planning a trip to some place is the knowledge of transport, roads and geographical connectedness of prominent sites in this place. while some transport companies or repositories make some of this information accessible, it is not easy to find, and the majority of information about uncommon places can only be found in web free text such as blogs and forums. in this paper we present an algorithmic framework which allows an automated acquisition of map-like information from the web, based on surface patterns like "from x to y". given a set of locations as initial seeds, we retrieve from the web an extended set of locations and produce a map-like network which connects these locations using transport type edges. we evaluate our framework in several settings, producing meaningful and precise connection sets.
gazpacho and summer rash: lexical relationships from temporal patterns of web search queries. in this paper we investigate temporal patterns of web search queries. we carry out several evaluations to analyze the properties of temporal profiles of queries, revealing promising semantic and pragmatic relationships between words. we focus on two applications: query suggestion and query categorization. the former shows a potential for time-series similarity measures to identify specific semantic relatedness between words, which results in state-of-the-art performance in query suggestion while providing complementary information to more traditional distributional similarity measures. the query categorization evaluation suggests that the temporal profile alone is not a strong indicator of broad topical categories.
detecting speculations and their scopes in scientific text. distinguishing speculative statements from factual ones is important for most biomedical text mining applications. we introduce an approach which is based on solving two sub-problems to identify speculative sentence fragments. the first sub-problem is identifying the speculation keywords in the sentences and the second one is resolving their linguistic scopes. we formulate the first sub-problem as a supervised classification task, where we classify the potential keywords as real speculation keywords or not by using a diverse set of linguistic features that represent the contexts of the keywords. after detecting the actual speculation keywords, we use the syntactic structures of the sentences to determine their scopes.
collocation extraction using monolingual word alignment method. statistical bilingual word alignment has been well studied in the context of machine translation. this paper adapts the bilingual word alignment algorithm to monolingual scenario to extract collocations from monolingual corpus. the monolingual corpus is first replicated to generate a parallel corpus, where each sentence pair consists of two identical sentences in the same language. then the monolingual word alignment algorithm is employed to align the potentially collocated words in the monolingual sentences. finally the aligned word pairs are ranked according to refined alignment probabilities and those with higher scores are extracted as collocations. we conducted experiments using chinese and english corpora individually. compared with previous approaches, which use association measures to extract collocations from the co-occurring word pairs within a given window, our method achieves higher precision and recall. according to human evaluation in terms of precision, our method achieves absolute improvements of 27.9% on the chinese corpus and 23.6% on the english corpus, respectively. especially, we can extract collocations with longer spans, achieving a high precision of 69% on the long-span (>6) chinese collocations.
k-best combination of syntactic parsers. in this paper, we propose a linear model-based general framework to combine k-best parse outputs from multiple parsers. the proposed framework leverages on the strengths of previous system combination and re-ranking techniques in parsing by integrating them into a linear model. as a result, it is able to fully utilize both the logarithm of the probability of each k-best parse tree from each individual parser and any additional useful features. for feature weight tuning, we compare the simulated-annealing algorithm and the perceptron algorithm. our experiments are carried out on both the chinese and english penn treebank syntactic parsing task by combining two state-of-the-art parsing models, a head-driven lexicalized model and a latent-annotation-based un-lexicalized model. experimental results show that our f-scores of 85.45 on chinese and 92.62 on english outperform the previously best-reported systems by 1.21 and 0.52, respectively.