Large Margin Methods for Structured and Interdependent Output Variables
Large Margin Methods for Structured and Interdependent Output Variables
复制标题
DOI：
--
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
Ioannis Tsochantaridis;T. Joachims;Thomas Hofmann;Y. Altun
中科院分区：
文献类型：
--
作者：
Ioannis Tsochantaridis;T. Joachims;Thomas Hofmann;Y. Altun
学习任意输入和输出空间之间的一般功能依赖性是计算智能中的关键挑战之一。尽管机器学习的最新进展主要集中在设计灵活而强大的输入表示形式上，但本文解决了设计分类算法的互补问题，该算法可以处理更复杂的输出，例如树，序列或集合。更一般而言，我们考虑涉及多个相关输出变量，结构化输出空间以及类别属性的分类问题的问题。为了实现这一目标，我们建议适当地概括分离边缘的众所周知的概念，并得出相应的最大边缘公式。尽管这导致了一个二次程序，该程序具有潜在的刺激性（即指数，约束的数量），但我们提出了一种切割平面算法，该算法解决了多项式时间的优化问题，以解决大量问题。所提出的方法在计算生物学，自然语言处理，信息检索/提取和光学特征识别等领域具有重要的应用。来自涉及不同类型输出空间的各种领域的实验强调了我们方法的广度和一般性。
Learning general functional dependencies between arbitrary input and output spaces is one of the key challenges in computational intelligence. While recent progress in machine learning has mainly focused on designing flexible and powerful input representations, this paper addresses the complementary issue of designing classification algorithms that can deal with more complex outputs, such as trees, sequences, or sets. More generally, we consider problems involving multiple dependent output variables, structured output spaces, and classification problems with class attributes. In order to accomplish this, we propose to appropriately generalize the well-known notion of a separation margin and derive a corresponding maximum-margin formulation. While this leads to a quadratic program with a potentially prohibitive, i.e. exponential, number of constraints, we present a cutting plane algorithm that solves the optimization problem in polynomial time for a large class of problems. The proposed method has important applications in areas such as computational biology, natural language processing, information retrieval/extraction, and optical character recognition. Experiments from various domains involving different types of output spaces emphasize the breadth and generality of our approach.