In the framework of agnostic learning, one of the main open problems of the
theory of multi-category pattern classification is the characterization of the
way the complexity varies with the number C of categories. More precisely, if
the classifier is characterized only through minimal learnability hypotheses,
then the optimal dependency on C that an upper bound on the probability of
error should exhibit is unknown. We consider margin classifiers. They are based
on classes of vector-valued functions with one component function per category,
and the classes of component functions are uniform Glivenko-Cantelli classes.
For these classifiers, an L p-norm Sauer-Shelah lemma is established. It is
then used to derive guaranteed risks in the L $\infty$ and L 2-norms. These
bounds improve over the state-of-the-art ones with respect to their dependency
on C, which is sublinear.

该研究探讨了在不确定学习框架下，多类别模式分类理论中的一个主要开放问题，即分类器的复杂性如何随类别数目变化。通过使用基于边界的分类器，并结合 Lp - 范数 Sauer-Shelah 引理，建立了一种理论界限，可以在 L∞和 L2 范数下导出分类风险的保证性。

Margin 多类别分类器的 Lp-norm Sauer-Shelah 引理

L p -norm Sauer-Shelah Lemma for Margin Multi-category Classifiers

Pac-Bayes bounds are among the most accurate generalization bounds for
classifiers learned from independently and identically distributed (IID) data,
and it is particularly so for margin classifiers: there have been recent
contributions showing how practical these bounds can be either to perform model
selection (Ambroladze et al., 2007) or even to directly guide the learning of
linear classifiers (Germain et al., 2009). However, there are many practical
situations where the training data show some dependencies and where the
traditional IID assumption does not hold. Stating generalization bounds for
such frameworks is therefore of the utmost interest, both from theoretical and
practical standpoints. In this work, we propose the first - to the best of our
knowledge - Pac-Bayes generalization bounds for classifiers trained on data
exhibiting interdependencies. The approach undertaken to establish our results
is based on the decomposition of a so-called dependency graph that encodes the
dependencies within the data, in sets of independent data, thanks to graph
fractional covers. Our bounds are very general, since being able to find an
upper bound on the fractional chromatic number of the dependency graph is
sufficient to get new Pac-Bayes bounds for specific settings. We show how our
results can be used to derive bounds for ranking statistics (such as Auc) and
classifiers trained on data distributed according to a stationary {\ss}-mixing
process. In the way, we show how our approach seemlessly allows us to deal with
U-processes. As a side note, we also provide a Pac-Bayes generalization bound
for classifiers learned on data from stationary $\varphi$-mixing distributions.

提出了第一篇关于在具有内在依赖性的数据上训练分类器的 Pac-Bayes 泛化界的研究，该方法基于依赖图的分解，通过图分数覆盖将依赖关系编码在数据的独立数据集中。