Timezone: »

 
Poster
Structured Prediction Theory Based on Factor Graph Complexity
Corinna Cortes · Vitaly Kuznetsov · Mehryar Mohri · Scott Yang

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #66 #None
in Wednesday Posters »

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, \emph{factor graph complexity}, which we show can be estimated from data and bounded in terms of familiar quantities for several commonly used hypothesis sets, and a sparsity measure for features and graphs. Our proof techniques include generalizations of Talagrand's contraction lemma that can be of independent interest. 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 devise two new algorithms, \emph{Voted Conditional Random Field} (VCRF) and \emph{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.

Keywords: Learning Theory · Structured Prediction · Ensemble Methods and Boosting · Regularization and Large Margin Methods

Author Information

Corinna Cortes (Google Research)
Vitaly Kuznetsov (Courant Institute)

Vitaly Kuznetsov is a research scientist at Google. Prior to joining Google Research, Vitaly received his Ph.D. in mathematics from the Courant Institute of Mathematical Sciences at New York University. Vitaly has contributed to a number of different areas in machine learning, in particular the development of the theory and algorithms for forecasting non-stationary time series. At Google, his work is focused on the design and implementation of large-scale machine learning tools and algorithms for time series modeling, forecasting and anomaly detection. His current research interests include all aspects of applied and theoretical time series analysis, in particular, in non-stationary environments.

Mehryar Mohri (Google Research & Courant Institute of Mathematical Sciences)
Scott Yang (New York University)

More from the Same Authors