Learning Distributed Representations for Structured Output Prediction
In recent years, distributed representations of inputs have led to performance gains in many applications by allowing statistical information to be shared across inputs. However, the predicted outputs (labels, and more generally structures) are still treated as discrete objects even though outputs are often not discrete units of meaning. In this paper, we present a new formulation for structured prediction where we represent individual labels in a structure as dense vectors and allow semantically similar labels to share parameters. We extend this representation to larger structures by defining compositionality using tensor products to give a natural generalization of standard structured prediction approaches. We define a learning objective for jointly learning the model parameters and the label vectors and propose an alternating minimization algorithm for learning. We show that our formulation outperforms structural SVM baselines in two tasks: multiclass document classification and part-of-speech tagging.
This is a very inspirational and well-written paper that challenges a fundamental assumption in many supervised classification tasks, namely that class labels are always distinct, discrete units of meaning.Instead, the paper argues that class labels can expose common traits and that some labels are closer to each other than others, a fact that should be exploited during training. Of course, this viewpoint is not entirely new -- such "distributional" arguments have been made in the connectionist literature before, regarding both input and output units, as correctly pointed out in the manuscript.The main novelty in the present manuscript is then to extend such distributional formulations to structured prediction, where not only atomic labels but also compositional parts (such as labels of factors defined over multiple variables) can be modeled in a distributional manner.Towards this end, a model is proposed in which labels of atomic parts are represented as vectors, and compositional parts as well as the corresponding feature spaces are defined in terms of tensor algebra.  A traditional structured prediction model then corresponds to the special case where each atomic label is represented via one-hot encoding.What makes the approach interesting is that both labels and model weights can be learned together in a joint objective function, based on the structured hinge loss.  A rank-penalty regularization term is placed on the matrix of label vectors to encourage the labels to share weights.  The parameters constituting the label vectors and the weights on features are trained by alternating minimization, which seems to work well most of the time, though the objective is not jointly convex.The experiments demonstrate considerable improvements over a standard hinge loss formulation on both multiclass classification and sequence classification.  Interestingly, the approach also allows to learn labels in a lower-dimensional vector space than the standard one-hot encoding, while maintaining excellent performance even for substantially reduced dimensionality.Quality:The paper is technically sound.  The theory backing the approach is plausible and formally developed to a sufficient extent in the manuscript.  The experiments are on the synthetic side, but still demonstrate the plausibility of the intuition underlying the paper convincingly.Clarity:The paper is well-written and the authors take care to give pedagogical examples to make the material easier to understand. A background in tensor algebra is still helpful when reading the paper.Figure 1 runs over the right margin considerably and should be fixed.Originality:The extension of the distributional approach to compositional parts is novel to my knowledge.Significance:   At present, I think neither the theory nor the practical tools (such as the learning algorithm, which seems to struggle with non-convexity now and then) are sufficiently developed for the approach to find broad adoption in the near future.  Also, there needs to be further evidence that the proposed approach yields state-of-the-art results on established benchmark tasks.  Nonetheless, the proposed approach is inspiring and seems to have a lot of potential.