Rademacher Complexity Bounds for a Penalized Multi-class Semi-supervised Algorithm (Extended Abstract)

1 Introduction

Learning with partially labeled data, or Semi-supervised learning (SSL), has been an active field of study in the ML community these past twenty years. In this case, labeled examples are usually supposed to be very few leading to an inefficient supervised model, while unlabeled training examples contain valuable information on the prediction problem at hand which exploitation may lead to a performant prediction function. For this scenario, we assume available a set of labeled training examples Sℓ = (xi, yi)1≤i≤n ∈ (X × Y)n drawn i.i.d. with respect to a fixed, but unknown, probability distribution D over X ×Y and a set of unlabeled training examples Su = (xn+i)1≤i≤u ∈ X u supposed to be drawn from the marginal distribution, DX , over the domain X. If Su is empty, then the problem is cast into the supervised learning framework. The other extreme case corresponds to the situation where Sℓ is empty and for which the problem reduces to unsupervised learning.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Maximov et al., 2018]

The issue of learnability with partially labeled data was studied under three related yet different hypotheses of smoothness assumption, cluster assumption, and low density separation [Chapelle et al., 2006; Zhu, 2005] and many advances have been made on both algorithmic and theoretical front under these settings.

Although classification problems, for which the design of SSL techniques is appealing, are multi-class in nature, the majority of theoretical results for semi-supervised learning has mainly considered the binary case [K¨a¨ari¨ainen, 2005; Leskes, 2005; Amini et al., 2008; El-Yaniv and Pechyony, 2009; Balcan and Blum, 2010; Urner et al., 2011]. In this paper, we tackle the learning ability of multi-class classifiers trained on partially labeled data by first identifying dense clusters covering labeled and unlabeled examples and then minimizing an objective composed of the margin empirical loss of the classifier over the labeled training set, and also a penalization term measuring the disability of the learner to predict the predominant classes of dense clusters.

Our main result is a data-dependent generalization error bound for classifiers trained under this setting and which exhibits a complexity term depending on the effectiveness of the clustering technique to find homogenous regions of examples belonging to each class, the margin distribution of the classifiers and the Rademacher complexities of the class of functions in use defined for labeled and unlabeled data. The convergence rates deduced from the bound extends those proposed in the literature for the binary case, further experiments carried out on text and image classification problems, show that the proposed approach yields improved classification performance compared to extensions of state-of-the-art SSL algorithms to the multi-class classification case.

In the following section, we first define our framework, then the learning task we address. Section 3 presents the Rademacher generalization bound for a classifier trained with the proposed algorithm. Section 4 positions our theoretical findings corcerning the state-of-the-art, and concludes this work.

2 Framework and Definitions

We are interested in the study of multi-class classification problems where the output space is Y = {1, . . . ,K}, with K > 2. The semi-supervised multi-class classification algorithm that we consider is tailored under the cluster assumption and operates in two steps depicted in the following sections.

2.1 Partitioning of Data and Identifying κ-Uniformly Bounded Clusters with Level η

The first step consists in partitioning the unlabeled training observations, into G > 0 separate clusters with a clustering algorithm A trained on Su, denoted by ΠSu .

Clusters of ΠSu that are well covered by classes in the labeled training set are then kept for learning the classifier (Section 2.2). Formally, for a fixed κ ∈ {1, . . . ,K}, let Yκ(C) be the κ most predominant classes of Y present in cluster C ∈ ΠSu . We then define κ-uniformly bounded clusters with level η, Cκ(η), the set of clusters within ΠSu that are covered by their κ most predominant classes such that the proportion of other classes within C not belonging to Yκ(C) is less than η/G :

Where Pn the uniform probability distribution over Sℓ; is defined for any subset B ⊆ Sℓ, as Pn(B) = card(B)/n.

2.2 Learning Objective

In the second step, we address a learning problem that is to find, in a hypothesis set H ⊆ RX×Y , a scoring function h ∈ H with low risk:

where 1π is the indicator function and mh(x, y) is the margin of the function h at an example (x, y) [Koltchinskii and Panchenko, 2002]:

This is achieved by minimizing a penalized empirical loss, defined for a given ρ > 0 :

composed of an empirical margin loss of h ∈ H on a labeled training set Sℓ

and a penalization term that reflects the ability of the hypothesis h ∈ H to identify the κ most predominant classes within the disjoint clusters of Cκ(η):

where m′h (x, Yκ(C)) is the margin of an unlabeled example Algorithm 1: Pseudo-code of the PMS2L algorithm Input: Labeled data set Sℓ = (xi, yi)1≤i≤n ⊆ (X × Y)n ; Unlabeled data set Su = (xn+i)1≤i≤u ⊆ X u ; Hypothesis space H;

G the number of clusters, ASu : X → {1, . . . ,G} the clustering algorithm found on Su, κ ∈ N∗ , and η > 0;

Stage 1: Using the labeled examples, Sℓ, identify the κbounded clusters in ΠSu with level η, Cκ(η); // in accordance with the definition of Cκ(η)

Stage 2: Find a hypothesis h∗ ∈ H that minimizes the penalized objective function (Eq. 1) :

Output: h∗

taken with respect to the set of κ predominant classes, Yκ(C) :

and, Φρ : R → [0, 1] is the ρ-margin loss defined as [Koltchinskii and Panchenko, 2002] :

The pseudo-code of the proposed 2-step approach, referred to as Penalized Multi-Class Semi-Supervised Learning (PMS2L), is given in Algorithm 1.

3 Theoretical Study

We now analyze how the use of unlabeled training data can improve generalization performance in some cases. Essentially, the trade-off is that clustering offers additional knowledge on the problem, therefore potentially helps to learn, but can also be of lower quality, which may degrade it.

3.1 Stable Clustering with the Bounded Difference Property

Before, let us first introduce notations that are used in the statement of the following results. We consider a hard clustering algorithm AZ defined as a function found over a finite sample Z.

Our analyzes are based on a notion of stability of the clustering algorithm A.; measured as the average number of examples in a given set ˜ Z of size n that are in the exclusive disjunction of clusters (present in one and absent from the other) found by A. over two sets Z and Z ′ , and defined as :

where π : {1, . . . ,G} → {1, . . . ,G} is a permutation. It is straightforward to show that ∆n defines a true metric, sometimes referred to as the minimal matching distance [Luxburg, 2010], on the space of clusterings. Hence, the clustering algorithmA. is said to obey the bounded difference property, if and only if for any i.i.d. samples Z, Z ′ ∼ D|Z| X differing in exactly one observation, and for any i.i.d. sample ˜ Z ∼ DnX of size n, there exists a universal constant L such that :

For some clustering algorithms such as k-means or khyperplane clustering, it has been shown that the bounded difference property is tightly related to their (in)stability. We refer to results of [Luxburg, 2010], [Luxburg et al., 2004], [Rakhlin and Caponnetto, 2006] and [Thiagarajan et al., 2011] and a number of references therein for the algorithmic details as well as various notions of clustering instability, and to that of [Shamir and Tishby, 2007] for the relation between bounded differences property, stability and model selection.

Furthermore, in the case where a clustering algorithm A obeys the bounded difference property; it is said to be stable if for any distribution DX over X there exists a unique limit clustering of the input space Π⋆ , obtained by a particular instantiation of the algorithm denoted by A⋆ , such that for any Z drawn i.i.d. fromDX and for any sample ˜ Z of size n drawn i.i.d. from the same distribution we have :

In this case, it is possible to (tightly) upper-bound the distance between A⋆ and the algorithm A trained on any unlabeled training set Su, estimated over the labeled training set Sℓ: ∆n(ASu ,A⋆ , Sℓ), as it is stated in the following Lemma.

Lemma 1 Let Sℓ = (xi, yi)1≤i≤n and Su = (xn+i)1≤i≤u be a labeled and an unlabeled training sets drawn i.i.d. according respectively to a probability distribution D over X × Y, and its marginal DX . For any 1 > δ > 0 and any stable clustering algorithm A that obeys the bounded differences property with constant L > 0, the average number of examples in Sℓ that are in the exclusive disjunction of clusters found by the clustering algorithm A on Su and by A⋆ is upper-bounded with probability at least 1 - δ as follows :

The proof is given in [Maximov et al., 2018]. This result suggests that for any labeled and unlabeled training data, if a clustering algorithm obeys the bounded differences property and that it is stable, then with high probability, ΠSu covers as well the labeled training data as the limit partition Π⋆ (i.e. most of the labeled examples would more likely be present in the intersection ΠSu ∩ Π⋆ ).

3.2 Semi-Supervised Data-Dependent Bounds

Based on the previous lemma, we can define situations where the Empirical Risk Minimization principle of algorithm PMS2L becomes consistent. This result is stated in Theorem (2) which provides bounds on the generalization error of a multi-class classifier trained with the penalized empirical loss defined above (Eq. 1).

The notion of function class capacity used in the bounds, is the labeled and unlabeled Rademacher complexities of the function class FH = {f : x ↦→ h(x, y) : y ∈ Y, h ∈ H}, defined respectively as:

where σi's, called Rademacher variables, are independent uniform random variables taking values in {-1,+1}; i.e. ∀i, P(σi = -1) = P(σi = +1) = 1 2 .

The proof is provided in [Maximov et al., 2018]. From this result and Lemma 1, we can then derive a data-dependent generalization bound for any semi-supervised multi-class prediction function found by algorithm PMS2L as stated below.

Theorem 2 Let H ⊆ RX×Y be a hypothesis set where Y = {1, . . . ,K}, and let Sℓ = ((xi, yi))ni=1 and Su = (xi)n+u i=n+1 be two sets of labeled and unlabeled training data, drawn i.i.d. respectively according to a probability distribution over X × Y and a marginal distribution DX . Fix ρ > 0 and κ ∈ {1, . . . ,K}, and consider a clustering algorithm A that obeys the bounded difference property with constant L and is stable. If the κ-uniformly bounded clusters found in ΠSu are such that the confident level η satisfies η ≤ ∆n(ASu ,A⋆ , Sℓ), then for any 1 > δ > 0 and all h ∈ H found by the PMS2L algorithm using ASu , the following multi-class classification generalization error bound holds with probability at least 1 - δ :

This result implies that with stable clustering algorithms obeying the bounded differences property, if the proportion of other classes than κ-predominant ones in confident clusters is less than the number of labeled examples in the exclusive disjunction of limit clusters and those found using the unlabeled training data, then with the strategy defined in algorithm PMS2L we can expect to have interesting situations for learning prediction models as it is stated in the following corollary.

In this case, we can show that the convergence rate of the bound for linear classifiers is of the order

where, for any real valued functions f and g the equality f(z) = ˜O(g(z)) holds, if there exists a constant α > 0 such that f(z) = O(g(z) logα g(z)) [Knuth, 1976]. In the following section we present an overview of the related-work and show that in the case where the clustering technique A captures the true structure of the data, measured by the set of κ-uniformly bounded clusters with rate η, resulting in approximations above, then for linear kernel-based hypotheses, the convergence rate (2) is the direct extension of dimensionfree convergence rates proposed in semi-supervised learning for the binary case. We also refer to [Kuznetsov et al., 2014; Lei et al., 2015; Maximov and Reshetova, 2016] for the stateof-the-art excess risk bounds for the supervised multi-class classification. According to these papers, the risk is linear in the number of classes and can not be further improved using the Rademacher or Gaussian complexities analysis.

As for the opposite case n ≫ u the pseudo-labeling step does not help to learn, and even can make the bounds worse than at the supervised case. The same situation takes place when the number of classes is comparable to the number of objects and one can not clarify whether a cluster is consistent or not. Finally, we would like to emphasize that our primary target is the most practical case with u ≫ n and the number of classes comparable to the number of clusters.

4 RelatedWorks and Discussion

Semi-supervised learning (SSL) approaches exploit the geometry of data to learn a prediction function from partially labeled training sets [Seeger, 2000]. The three main SSL techniques; namely graphical, generative and discriminant approaches, were mostly developed for the binary case and tailored under smoothness, low-density separation and cluster assumptions [Zhu, 2005; Chapelle et al., 2006; Amini and Usunier, 2015].

Graphical approaches construct an empirical graph where the nodes represent the training examples, and the edges of the graph reflect the similarity between them. These approaches are mostly based on label spreading algorithms that propagate the class label of each labeled node to its neighbors [Zhou et al., 2003; Zhu, 2002]. Generative approaches naturally exploit the geometry of data by modeling their marginal distributions.

These methods are developed under the cluster assumption and use the Bayes rule to make a decision. In the seminal work of [Castelli and Cover, 1995] it is shown that, without extra assumptions relating marginal distribution and actual distribution of labels, a sample of unlabeled data is of (almost) no help for learning purpose. Recent work from [Ben-David et al., 2008] investigated further the limitations of semi-supervised learning and concluded that theoretical results for semi-supervised learning should be accompanied by an additional assumption on the actual label distribution.

Discriminant approaches directly find the decision boundary without making any assumptions on the marginal distribution of examples. The two most popular discriminant models are without doubts co-training [Blum and Mitchell, 1998] and Transductive SVMs [Vapnik, 2000]. The co-training algorithm supposes that each observation is produced by two sources of information and that each view-specific representation is rich enough to learn the parameters of the associated classifier in the case where there are enough labeled examples available. The two classifiers are first trained separately on the labeled data. A subset of unlabeled examples is then randomly drawn and pseudo-labeled by each of the classifiers. The estimated output by the first classifier becomes the desired output for the second classifier and reciprocally. Under this setting, [Leskes, 2005] proposed a Rademacher complexity bound, where unlabeled data are used to decrease the disagreement between hypotheses from a class of functions H and proved that in some cases, the bound of the excess risk |R(h) - ˆR(h, Sℓ)| for any h ∈ H is of the order ˜O (n-1/2 + u-1/2 ).

However, transductive learning tends to produce a prediction function for only a fixed number of unlabeled examples. Transductive algorithms generally use the distribution of unsigned margins of unlabeled examples in order to guide the search of a prediction function and find the hyperplane in a feature space that separates the best l abeled examples and that does not pass through high density regions. The notion of transductive Rademacher complexity was introduced in [El-Yaniv and Pechyony, 2009]. In the best case, the excess risk bound proposed in this paper is of the order ˜O (u√min(u, n)/(n + u)).

Our two step multi-class SSL approach is in between generative and discriminant approaches, and hence bears similarity with the study of [Urner et al., 2011]. The main difference is however that the proposed approach does not rely on any pseudo-labeling mechanism and that our analyzes are based on the Rademacher complexity leading to dimension free data-dependent bounds.

On another level and under the PAC-Bayes setting, [K¨a¨ari¨ainen, 2005] showed that in the realizable case where the hypothesis set contains the Bayes classifier, the obtained excess risk bound takes the form inf f∈F0 sup g∈F0 ˆ d(f, g) +

˜O (u-1/2 ); where ˆ d(f, g) is a normalized empirical disagreements between two hypothesis that correctly classify the labeled set and can be of order at least ˜O (n-1/2 ).

The contributions of this paper are twofold. First, we proposed a bound on the risk of a multi-class classifier trained over partially labeled training data. We derived datadependent bounds for the generalization error of a classifier trained by minimizing an objective function that consists of an empirical risk term, estimated over the labeled training set, and a penalized term corresponding to the ratio of unlabeled examples of each cluster; within the κ bounded set of clusters, for which their predicted class does not belong to the set of the associated κ predominant classes. We support our results by extensive empirical evaluation given in [Maximov et al., 2018].

Acknowledgments

This work has been partially supported by the THANATOS project funded by Appel `a projets Grenoble Innovation Recherche. The work of YM at LANL was supported by funding from the U.S. Department of Energys Office of Electricity as part of the DOE Grid Modernization Initiative.