【Alex Nowak-Vila博士论文】有理论保证的结构化预测， Structured Prediction with Theoretical Guarantees

分类是监督学习的一个分支，其目的是估计由输入-输出对组成的数据的离散值映射。最经典和研究得最充分的设置是二值分类，其中离散预测器取0或1作为值。然而，大多数实际的分类设置处理大型结构化输出空间，如序列、网格、图、排列、匹配等。结构化预测与普通的二进制或多类分类之间有许多基本的区别，例如输出空间相对于输出对象的自然维数呈指数级大，以及学习任务的代价敏感性质。本文的重点是结构化预测的替代方法，其中典型的棘手的离散问题是通过一个凸连续替代问题来解决的，而这个问题又可以使用回归技术来解决。在结构化设置中，输出空间的大小和任务的成本敏感性定义了二进制情况下不存在的新挑战。本论文的主要工作是建立代理方法的一般理论，研究Fisher一致性、校准、训练复杂性和推理复杂性等统计和计算性质。更具体地说，本文中出现了两种主要的代理策略:概率方法(也称为插件分类器)和非概率方法。对第一种类型的主要贡献是对现有的和最近提出的结构化概率代理的定量校准分析，这是获得这些估计的保证的关键因素。第二种类型的主要贡献包括对最大最小损失的统计和计算分析、最近提出的用于结构化预测的校准多面体替代损失以及对结构化最大损失(也称为结构性支持向量机)的一致性分析、这是二进制支持向量机的经典扩展到结构化输出空间。