Exact Inference in High-order Structured Prediction
In this paper, we study the problem of inference in high-order structured prediction tasks. In the context of Markov random fields, the goal of a high-order inference task is to maximize a score function on the space of labels, and the score function can be decomposed into sum of unary and high-order potentials. We apply a generative model approach to study the problem of high-order inference, and provide a two-stage convex optimization algorithm for exact label recovery. We also provide a new class of hypergraph structural properties related to hyperedge expansion that drives the success in general high-order inference problems. Finally, we connect the performance of our algorithm and the hyperedge expansion property using a novel hypergraph Cheeger-type inequality.
Code (0)
등록된 구현이 없습니다.
Tasks
PredictionStructured PredictionVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
On the Fundamental Limits of Exact Inference in Structured Prediction
Inference is a main task in structured prediction and it is naturally modeled with a graph. In the context of Markov random fields, noisy observations corresponding to nodes and edges are usually involved, and the goal o…
Computational EfficiencyStructured PredictionA Learning Error Analysis for Structured Prediction with Approximate Inference
In this work, we try to understand the differences between exact and approximate inference algorithms in structured prediction. We compare the estimation and approximation error of both underestimate and overestimate mod…
Dependency ParsingGeneral ClassificationStructured Predictiontext-classification+1Structured prediction models for RNN based sequence labeling in clinical text
Sequence labeling is a widely used method for named entity recognition and information extraction from unstructured natural language data. In clinical domain one major application of sequence labeling involves extraction…
named-entity-recognitionNamed Entity RecognitionNamed Entity Recognition (NER)Structured PredictionDeep Structured Mixtures of Gaussian Processes
Gaussian Processes (GPs) are powerful non-parametric Bayesian regression models that allow exact posterior inference, but exhibit high computational and memory costs. In order to improve scalability of GPs, approximate p…
Gaussian ProcessesGraph Structured Prediction Energy Networks
For joint inference over multiple variables, a variety of structured prediction techniques have been developed to model correlations among variables and thereby improve predictions. However, many classical approaches suf…
PredictionStructured Prediction