Non-Asymptotic Performance of Social Machine Learning Under Limited Data
Ping Hu Virginia Bordignon Mert Kayaalp Ali H. Sayed
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.