Conditional Graphical Models
Fernando Perez-Cruz, Massimiliano Pontil and Zoubin Ghahramani
Predicting Structured Data
, Cambridge, MA (USA)
In this chapter we propose a modification of CRF-like algorithms that allows
for solving large-scale structured classification problems. Our approach consists
in upper bounding the CRF functional in order to decompose its training into
independent optimisation problems per clique. Furthermore we show that each
sub-problem corresponds to solving a multiclass learning task in each clique, which
enlarges the applicability of these tools for large-scale structural learning problems.
Before presenting the Conditional Graphical Model (CGM), as we refer to this
procedure, we review the family of CRF algorithms. We concentrate on the best
known procedures and standard generalisations of CRFs. The objective of this
introduction is analysing from the same viewpoint the proposed solutions in the
literature to tackle this problem, which allows comparing their different features.
We complete the chapter with a case study, in which we show the possibility to
work with large-scale problems using CGM and that the obtained performance is
comparable to the result with CRF-like algorithms.