A Deep Learning Model for Structured Outputs with High-order Interaction

Hongyu Guo, Xiaodan Zhu, Martin Renqiang MinarXiv 2015 · arXiv

Abstract

Traditional machine learning models often assume independence between output variables, a simplification that fails in complex tasks like image reconstruction or natural language processing. This paper introduces HNNSO (High-order Neural Network with Structured Output), a deep learning architecture designed to capture intricate dependencies in both input and output data. By integrating bilinear tensor products and high-order denoising auto-encoders, the model achieves state-of-the-art performance in structured regression tasks.

Introduction

In many real-world "structured" problems—such as predicting the pixels of an image or the dimensions of a word embedding—the outputs are highly correlated. While tools like Conditional Random Fields (CRFs) exist to model these dependencies, they often rely on explicit, hand-defined structures and struggle to capture "high-order" interactions (complex multiplicative relationships between multiple variables). Furthermore, structured regression (predicting continuous values) remains relatively under-explored compared to classification. The HNNSO model aims to bridge this gap using the representational power of deep learning.

The HNNSO Architecture

The HNNSO model consists of three specialized layers designed to model structured data comprehensively:

The HNNSO architecture, illustrating the three-layer approach to modeling structured inputs and outputs.
  1. Input Modeling (Bottom Layer): Instead of a simple linear transformation, this layer uses a bilinear tensor product. It takes the input vector $X$ and its non-linear projection $h(X)$, using a third-order tensor to model how these vectors interact multiplicatively. This allows the model to capture complex patterns in raw input data.
  2. Mapping (Middle Layer): This layer acts as a bridge, mapping high-order input features toward the output space.
  3. Output Modeling (Top Layer): This is a high-order denoising auto-encoder. During training, the model is fed "corrupted" versions of true labels. It uses another tensor to capture covariance patterns (how outputs move together) to "clean" the prediction. This forces the network to learn the underlying structure of the output space.

To optimize this complex stack, the authors use a bottom-up, layer-by-layer discriminative pretraining strategy. This ensures each layer specializes in its specific task—input structure versus output correlation—before the entire network is fine-tuned together.

Experimental Evaluation

The model was evaluated on three distinct benchmarks: the Stanford Sentiment Tree Bank (SSTB), MNIST handwritten digits (predicting PCA components), and USPS image completion (predicting the right half of an image given the left).

Boxplots comparing the prediction error distributions of SVM-Reg and the proposed HNNSO model across various dimensions.

HNNSO consistently outperformed six competitive baselines, including Support Vector Regression (SVM-Reg) and Gaussian CRFs. On the SSTB and MNIST datasets, HNNSO achieved a relative error reduction of roughly 17-18% over the next best model. Qualitatively, in the USPS image completion task, HNNSO successfully recovered sharp, recognizable digit halves, whereas standard Multi-Layer Perceptrons (MLPs) often produced blurry results.

Key Insights and Conclusion

A primary takeaway is the efficiency of multiplicative over additive interactions. By using tensors to multiply inputs, HNNSO captures "gating" effects and complex feature correlations more effectively than standard neural networks. Furthermore, the top-layer auto-encoder acts as a "self-corrector," ensuring that predicted outputs remain consistent with valid structures.

While third-order tensors introduce computational complexity, the performance gains are statistically significant. Future work will explore scaling this architecture to higher-dimensional computer vision tasks, such as full-scale image labeling and scene understanding, where output structures are paramount.

Summary updated

Abstract

Many real-world applications are associated with structured data, where not only input but also output has interplay. However, typical classification and regression models often lack the ability of simultaneously exploring high-order interaction within input and that within output. In this paper, we present a deep learning model aiming to generate a powerful nonlinear functional mapping from structured input to structured output. More specifically, we propose to integrate high-order hidden units, guided discriminative pretraining, and high-order auto-encoders for this purpose. We evaluate the model with three datasets, and obtain state-of-the-art performances among competitive methods. Our current work focuses on structured output regression, which is a less explored area, although the model can be extended to handle structured label classification.
BibTeX
@misc{guo2015deep,
  author = {Hongyu Guo and Xiaodan Zhu and Martin Renqiang Min},
  title = {{A Deep Learning Model for Structured Outputs with High-order Interaction}},
  year = {2015},
  eprint = {1504.08022},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.08022},
}
Figure