Sequential Learning of Classifiers for Structured Prediction Problems

Dan Roth, Kevin Small, Ivan Titov
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:440-447, 2009.

Abstract

Many classification problems with structured outputs can be regarded as a set of interrelated sub-problems where constraints dictate valid variable assignments. The standard approaches to these problems include either independent learning of individual classifiers for each of the sub-problems or joint learning of the entire set of classifiers with the constraints enforced during learning. We propose an intermediate approach where we learn these classifiers in a sequence using previously learned classifiers to guide learning of the next classifier by enforcing constraints between their outputs. We provide a theoretical motivation to explain why this learning protocol is expected to outperform both alternatives when individual problems have different ‘complexity’. This analysis motivates an algorithm for choosing a preferred order of classifier learning. We evaluate our technique on artificial experiments and on the entity and relation identification problem where the proposed method outperforms both joint and independent learning.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-roth09a, title = {Sequential Learning of Classifiers for Structured Prediction Problems}, author = {Dan Roth and Kevin Small and Ivan Titov}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {440--447}, year = {2009}, editor = {David van Dyk and Max Welling}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/roth09a/roth09a.pdf}, url = {http://proceedings.mlr.press/v5/roth09a.html}, abstract = {Many classification problems with structured outputs can be regarded as a set of interrelated sub-problems where constraints dictate valid variable assignments. The standard approaches to these problems include either independent learning of individual classifiers for each of the sub-problems or joint learning of the entire set of classifiers with the constraints enforced during learning. We propose an intermediate approach where we learn these classifiers in a sequence using previously learned classifiers to guide learning of the next classifier by enforcing constraints between their outputs. We provide a theoretical motivation to explain why this learning protocol is expected to outperform both alternatives when individual problems have different ‘complexity’. This analysis motivates an algorithm for choosing a preferred order of classifier learning. We evaluate our technique on artificial experiments and on the entity and relation identification problem where the proposed method outperforms both joint and independent learning.} }
Endnote
%0 Conference Paper %T Sequential Learning of Classifiers for Structured Prediction Problems %A Dan Roth %A Kevin Small %A Ivan Titov %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-roth09a %I PMLR %J Proceedings of Machine Learning Research %P 440--447 %U http://proceedings.mlr.press %V 5 %W PMLR %X Many classification problems with structured outputs can be regarded as a set of interrelated sub-problems where constraints dictate valid variable assignments. The standard approaches to these problems include either independent learning of individual classifiers for each of the sub-problems or joint learning of the entire set of classifiers with the constraints enforced during learning. We propose an intermediate approach where we learn these classifiers in a sequence using previously learned classifiers to guide learning of the next classifier by enforcing constraints between their outputs. We provide a theoretical motivation to explain why this learning protocol is expected to outperform both alternatives when individual problems have different ‘complexity’. This analysis motivates an algorithm for choosing a preferred order of classifier learning. We evaluate our technique on artificial experiments and on the entity and relation identification problem where the proposed method outperforms both joint and independent learning.
RIS
TY - CPAPER TI - Sequential Learning of Classifiers for Structured Prediction Problems AU - Dan Roth AU - Kevin Small AU - Ivan Titov BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-roth09a PB - PMLR SP - 440 DP - PMLR EP - 447 L1 - http://proceedings.mlr.press/v5/roth09a/roth09a.pdf UR - http://proceedings.mlr.press/v5/roth09a.html AB - Many classification problems with structured outputs can be regarded as a set of interrelated sub-problems where constraints dictate valid variable assignments. The standard approaches to these problems include either independent learning of individual classifiers for each of the sub-problems or joint learning of the entire set of classifiers with the constraints enforced during learning. We propose an intermediate approach where we learn these classifiers in a sequence using previously learned classifiers to guide learning of the next classifier by enforcing constraints between their outputs. We provide a theoretical motivation to explain why this learning protocol is expected to outperform both alternatives when individual problems have different ‘complexity’. This analysis motivates an algorithm for choosing a preferred order of classifier learning. We evaluate our technique on artificial experiments and on the entity and relation identification problem where the proposed method outperforms both joint and independent learning. ER -
APA
Roth, D., Small, K. & Titov, I.. (2009). Sequential Learning of Classifiers for Structured Prediction Problems. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:440-447

Related Material