In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
--------
Question: This paper presents generalized probabilistic models for high-order projective dependency parsing and an algorithmic framework for learning these statistical models involving dependency trees. Partition functions and marginals for high-order dependency trees can be computed efficiently, by adapting our algorithms which extend the inside-outside algorithm to higher-order cases. To show the effectiveness of our algorithms, we perform experiments on three languages— English, Chinese and Czech, using maximum conditional likelihood estimation for model training and L-BFGS for parameter estimation. Our methods achieve competitive performance for English, and outperform all previously reported dependency parsers for Chinese and Czech.

Answer: Probabilistic Models for High-Order Projective Dependency Parsing


Question: We consider a general framework of online learning with expert advice where the regret is defined with respect to a competitor class defined by a weighted automaton over sequences of experts. Our framework covers several problems previously studied, in particular that of competing against k-shifting experts. We give a series of algorithms for this problem, including an automata-based algorithm extending weightedmajority and more efficient algorithms based on the notion of failure transitions. We further present efficient algorithms based on a compact approximation of the competitor automaton, in particular efficient n-gram models obtained by minimizing the Rényi divergence, and present an extensive study of the approximation properties of such models. We also extend our algorithms and results to the framework of sleeping experts. Finally, we describe the extension of our approximation methods to online convex optimization and a general mirror descent setting.

Answer: Online Learning against Expert Automata


Question: To improve the efficiency of Monte Carlo estimation, practitioners are turning to biased Markov chain Monte Carlo procedures that trade off asymptotic exactness for computational speed. The reasoning is sound: a reduction in variance due to more rapid sampling can outweigh the bias introduced. However, the inexactness creates new challenges for sampler and parameter selection, since standard measures of sample quality like effective sample size do not account for asymptotic bias. To address these challenges, we introduce a new computable quality measure based on Stein’s method that quantifies the maximum discrepancy between sample and target expectations over a large class of test functions. We use our tool to compare exact, biased, and deterministic sample sequences and illustrate applications to hyperparameter selection, convergence rate assessment, and quantifying bias-variance tradeoffs in posterior inference.

Answer:
Measuring Sample Quality with Stein’s Method