This paper studies the probability of error associated with the social
machine learning framework, which involves an independent training phase
followed by a cooperative decision-making phase over a graph. This framework
addresses the problem of classifying a stream of unlabeled data in a
distributed manner. We consider two kinds of classification tasks with limited
observations in the prediction phase, namely, the statistical classification
task and the single-sample classification task. For each task, we describe the
distributed learning rule and analyze the probability of error accordingly. To
do so, we first introduce a stronger consistent training condition that
involves the margin distributions generated by the trained classifiers. Based
on this condition, we derive an upper bound on the probability of error for
both tasks, which depends on the statistical properties of the data and the
combination policy used to combine the distributed classifiers. For the
statistical classification problem, we employ the geometric social learning
rule and conduct a non-asymptotic performance analysis. An exponential decay of
the probability of error with respect to the number of unlabeled samples is
observed in the upper bound. For the single-sample classification task, a
distributed learning rule that functions as an ensemble classifier is
constructed. An upper bound on the probability of error of this ensemble
classifier is established.

本文研究了社交机器学习框架中的错误概率，包括独立训练阶段和在图上进行合作决策阶段。针对两种有限观测的分类任务，我们描述了分布式学习规则并相应地分析了错误概率。针对统计分类问题，我们采用几何社交学习规则进行性能分析。针对单样本分类任务，我们建立了一个分布式学习规则作为集成分类器，并构建了该集成分类器的错误概率上界。

有限数据下社交机器学习的非渐进性能

Non-Asymptotic Performance of Social Machine Learning Under Limited Data

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 范数下导出分类风险的保证性。