对于大多数机器学习中的分类器而言,每个样本由输入 、输出 构成,而我们的任务就是寻找一个针对输入到输出的映射,即 ,在传统方法中,通常输入空间属于多维空间 ,而输出等于某个有限大小离散集合  中的一个数,虽然用一个数字来表示输出在大多数情况下都适用,但在诸如视觉、自然语言处理等一些特殊领域应用时可能会存在一些局限性,因为输出可能并不能由一个一维数字比较完整的代表,于是structured learning应运而生,在这里,输出y被允许取值为和输入x类似的多维结构,以此提出和实际情况更加符合的模型,这里以Structural SVM为例进行说明,主要参考文献: Support vector machine learning for interdependent and structured output spaces. Tsochantaridis I, Hofmann T, Joachims T, et al. ICML 2004.

假设我们的模型参数为 ,输入输出分别为 ,我们的目标是学习一个用以预测的判别函数f:

(当然我们也可以设计一个类似-F这样的函数当做损失函数,然后求其最小值)。

我们假设F与输入、输出的某种综合特征具有线性关系:

具体选取的特征 随实际应用场景而定。

此外,我们还需要设计一个对预测结果评价的损失函数 ,并且如果预测值和真实值越接近,损失应该越小,反之,则越大,于是总的risk可以定义为:

这里P是数据的概率分布,一般对我们而言都是未知的,所以需要用训练样本数据计算的empirical risk 来代替。

理想情况下,应该可以找到一个或多个参数w使得在训练样本 上计算出的empirical risk为0,并且其条件为:

上式由n个包含max函数的linear inequalities约束条件构成,可以继续展开成 个普通的式子:

这里

对于上面的多个约束条件而言,可能会由多个解,这里可以借助经典SVM的maximum-margin原则,在 的情况下,使得hyper-plane和最近的数据点距离最大,于是可以把原问题转化成一个类似经典SVM的优化问题:

然后加上软边界得到:

这里加上的是margin violations 的和,文章还提到可以换成其二范数和,得到另一种SVM变形;观察从Structural SVM提取出来的数学优化问题,可以看出其目标函数其实与经典SVM类似,都是通过最小化 来实现maximum-margin思想,然后附加一个软边界regularizer防止异常点的存在使超平面偏离太离谱,所不同的地方主要在于地下的约束条件,经典SVM通过限制样本点分布在超平面两侧并且保持足够的距离,而Structural SVM则是通过限制事先构造的 损失函数大小来约束,这里避免了前者简单粗暴的惩罚方式(比如分错惩罚1,分对惩罚0),对分类错误程度不同的样本进行程度不同的惩罚,显然会对分类器的准确率有比较好的提高。