Structured Prediction Theory Based on Factor Graph Complexity
We present a general theoretical analysis of structured prediction with a series of new results. We give new data-dependent margin guarantees for structured prediction for a very wide family of loss functions and a general family of hypotheses, with an arbitrary factor graph decomposition. These are the tightest margin bounds known for both standard multi-class and general structured prediction problems. Our guarantees are expressed in terms of a data-dependent complexity measure, factor graph complexity, which we show can be estimated from data and bounded in terms of familiar quantities. We further extend our theory by leveraging the principle of Voted Risk Minimization (VRM) and show that learning is possible even with complex factor graphs. We present new learning bounds for this advanced setting, which we use to design two new algorithms, Voted Conditional Random Field (VCRF) and Voted Structured Boosting (StructBoost). These algorithms can make use of complex features and factor graphs and yet benefit from favorable learning guarantees. We also report the results of experiments with VCRF on several datasets to validate our theory.
Code (0)
등록된 구현이 없습니다.
Tasks
PredictionStructured PredictionSimilar Papers 제목 키워드 기반
Minimax bounds for structured prediction
Structured prediction can be considered as a generalization of many standard supervised learning tasks, and is usually thought as a simultaneous prediction of multiple labels. One standard approach is to maximize a score…
PredictionStructured PredictionA Theory of Random Graph Shift in Truncated-Spectrum vRKHS
This paper develops a theory of graph classification under domain shift through a random-graph generative lens, where we consider intra-class graphs sharing the same random graph model (RGM) and the domain shift induced …
Graph ClassificationDomain AdaptationGraph LearningMulti-Factor Spatio-Temporal Prediction based on Graph Decomposition Learning
Spatio-temporal (ST) prediction is an important and widely used technique in data mining and analytics, especially for ST data in urban systems such as transportation data. In practice, the ST data generation is usually …
PredictionL-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data
We study instancewise feature importance scoring as a method for model interpretation. Any such method yields, for each predicted instance, a vector of importance scores associated with the feature vector. Methods based …
Feature ImportanceFurther results on structured regression for multi-scale networks
Gaussian Conditional Random Fields (GCRF), as a structured regression model, is designed to achieve higher regression accuracy than unstructured predictors at the expense of execution time, taking into account the object…
regression