  We consider higher-order linear-chain conditional random fields (HO-LC-CRFs)
for sequence modelling, and use sum-product networks (SPNs) for representing
higher-order input- and output-dependent factors. SPNs are a recently
introduced class of deep models for which exact and efficient inference can be
performed. By combining HO-LC-CRFs with SPNs, expressive models over both the
output labels and the hidden variables are instantiated while still enabling
efficient exact inference. Furthermore, the use of higher-order factors allows
us to capture relations of multiple input segments and multiple output labels
as often present in real-world data. These relations can not be modelled by the
commonly used first-order models and higher-order models with local factors
including only a single output label. We demonstrate the effectiveness of our
proposed models for sequence labeling. In extensive experiments, we outperform
other state-of-the-art methods in optical character recognition and achieve
competitive results in phone classification.
