Bernard Ng
email: bernardyng@gmail.com

Viviana Siless

Gael Varoquaux

Jean-Baptiste Poline

Bertrand Thirion

Rafeef Abugharbieh

Connectivity-informed Sparse Classifiers for fMRI Brain Decoding

Keywords: connectivity, DTI, fMRI, sparse classifiers I

In recent years, sparse regularization has become a dominant means for handling the curse of dimensionality in functional magnetic resonance imaging (fMRI) based brain decoding problems. Enforcing sparsity alone, however, neglects the interactions between connected brain areas. Methods that additionally impose spatial smoothness would account for local but not long-range interactions. In this paper, we propose incorporating connectivity into sparse classifier learning so that both local and long-range connections can be jointly modeled. On real data, we demonstrate that integrating connectivity information inferred from diffusion tensor imaging (DTI) data provides higher classification accuracy and more interpretable classifier weight patterns than standard classifiers. Our results thus illustrate the benefits of adding neurologically-relevant priors in fMRI brain decoding.

INTRODUCTION

The use of functional magnetic resonance imaging (fMRI) for brain decoding has gained substantial research interest in the past decade [START_REF] Haynes | Decoding Mental States from Brain Activity in Humans[END_REF]. With the signal intensity at each voxel or brain area treated as a feature, the goal of brain decoding is to discriminate different cognitive states based on the brain signal patterns. Due to the high dimensionality of fMRI data and the typically small sample sizes, special caution must be taken to control for overfitting [START_REF] Haynes | Decoding Mental States from Brain Activity in Humans[END_REF]. The traditional approach for dealing with the curse of dimensionality is to apply univariate feature selection in isolating brain areas that display significant activation or discriminability [START_REF] Mitchell | Learning to Decode Cognitive States from Brain Images[END_REF]. However, this approach discards the collective information encoded by the brain signal patterns [START_REF] Haynes | Decoding Mental States from Brain Activity in Humans[END_REF]. To circumvent this limitation, multivariate feature selection techniques, such as support vector machines with recursive feature elimination (SVM-RFE) [START_REF] Hanson | Brain Reading Using Full Brain Support Vector Machines for Object Recognition: There is no Face Identification Area[END_REF], have been proposed but tend to be computationally expensive.

Recently, sparse regularization has become a primary means for handling overfitting [START_REF] Yamashita | Sparse Estimation Automatically Selects Voxels Relevant for the Decoding of fMRI Activity Patterns[END_REF][START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF][START_REF] Carroll | Prediction and Interpretation of Distributed Neural Activity with Sparse Models[END_REF][START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF][START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF][START_REF] Michel | Total Variation Regularization for fMRI-based Prediction of Behavior[END_REF][START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF][START_REF] Van Gerven | Efficient Bayesian Multivariate fMRI Analysis Using a Sparsifying Spatiotemporal Prior[END_REF]. By enforcing sparsity, classifier weights associated with irrelevant features are shrunk to exactly zero. This approach thus enables feature selection and classifier learning to be simultaneously and cooperatively performed. Imposing sparsity is typically achieved by incorporating a least absolute shrinkage and selection operator (LASSO) penalty into classifier learning [START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF]. However, in the presence of correlated features, LASSO tends to arbitrarily select one feature among each correlated set, which is especially problematic for fMRI decoding since signals of interacting brain areas are certainly correlated [START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF][START_REF] Carroll | Prediction and Interpretation of Distributed Neural Activity with Sparse Models[END_REF]. To encourage correlated brain areas to be jointly selected, incorporation of an elastic net penalty has been proposed [START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF][START_REF] Carroll | Prediction and Interpretation of Distributed Neural Activity with Sparse Models[END_REF], but its effectiveness appears limited by the strong noise in fMRI data [START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF]. Structured sparsity [START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF] has also been explored to enforce joint selection of predefined groups of voxels (e.g. voxels grouped by anatomical regions or functional parcels [START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF]), but these penalties alone do not account for the local spatial correlations between neighboring voxels [START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF][START_REF] Michel | Total Variation Regularization for fMRI-based Prediction of Behavior[END_REF][START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF].

To explicitly model local spatial correlations, total variation regularization has been explored, which penalizes the spatial gradient of the classifier weight patterns [START_REF] Michel | Total Variation Regularization for fMRI-based Prediction of Behavior[END_REF]. A Bayesian approach for incorporating a spatiotemporal prior while enforcing sparsity has also been put forth [START_REF] Van Gerven | Efficient Bayesian Multivariate fMRI Analysis Using a Sparsifying Spatiotemporal Prior[END_REF]. Furthermore, a recent method called, GraphNet, which imposes spatial smoothness through a graph-constrained elastic net penalty [START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF] as well as a generalized sparse regularization (GSR) strategy [START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF] that additionally facilitates incorporation of structured sparse penalties have been proposed. Encouraging spatial smoothness accounts for local correlations but neglects the longer range interactions. Since it is now well established that the brain is organized into distributed areas that are interconnected by white matter fiber pathways [START_REF] Damoiseaux | Greater than the Sum of its Parts: A Review of Studies Combining Structural Connectivity and Resting-state Functional Connectivity[END_REF], integrating connectivity into sparse classifier learning may provide additional relevant information in improving identification of task discriminant brain areas.

In this paper, we propose incorporating connectivity into sparse classifier learning to explicitly model the integrative property of the brain [START_REF] Damoiseaux | Greater than the Sum of its Parts: A Review of Studies Combining Structural Connectivity and Resting-state Functional Connectivity[END_REF]. Both GraphNet and GSR permit integration of connectivity, but entail converting discrete labels into continuous variables using e.g. optimal scoring (OS) [START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF] or graph embedding (GE) [START_REF] Yan | Graph Embedding and Extension: A General Framework for Dimensionality Reduction[END_REF] for classifier learning. In this work, we show that the learning of connectivity-informed sparse classifiers can be posed as a single unified optimization and solved using existing sparse optimizers [START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF][START_REF] Schmidt | Projected Netwon-type Methods in Machine Learning[END_REF] with only a minimal change in the gradient update. For validation, we build a connectivity-informed sparse logistic regression (SLR) classifier with connectivity inferred from diffusion tensor imaging (DTI) data. On a face viewing task, we demonstrate that incorporating connectivity improves classification accuracy and result interpretability.

II. METHODS

Restricting our attention to linear classifiers so that the relevance of the features can be directly discerned from the magnitude of linear classifier weights [START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF], the general problem of classifier learning can be posed as finding the optimal d×1 weight vector, w, and an intercept, b, such that the n×1 predicted labels, f(Xw+b), best match the n×1 ground truth labels, y, associated with the n×d feature matrix, X. n is the number of samples, d is the number of features, and f(•) is a function that maps Xw+b to the label space. In the context of fMRI decoding, we treat the signal intensity of a voxel or brain area as a feature with different cognitive states being the labels. Since n << d typically, controlling overfitting through e.g. regularization is crucial.

A. Overview of Sparse Regularization

Linear classifier learning with regularization can be expressed as the following optimization problem:

( ) (
)

) ( , min , w y Xw w R b f E b λ + + , (1)
where E(•) is a mis-classification loss (see Section II-C), R(w) is a regularization penalty, and λ balances the influence of E(•) and R(w). To enforce sparsity, the most widely-used approach is to set R(w) to ||w|| 1 , which is the well known LASSO penalty [START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF]. However, LASSO's difficulties with correlated features render it less effective for fMRI decoding [START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF][START_REF] Carroll | Prediction and Interpretation of Distributed Neural Activity with Sparse Models[END_REF]. To encourage joint selection of correlated features, elastic net has been proposed, which is equivalent to adding a ridge penalty to LASSO, i.e.

( )

2 2 1 1 w w α α - +
, with the relative weightings between the two terms controlled by α.

However, the performance of elastic net in jointly selecting correlated features highly depends on the level of noise in the data [START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF]. To explicitly model local spatial correlations, total variation regularization, , 1 w ∇ α has been explored [START_REF] Michel | Total Variation Regularization for fMRI-based Prediction of Behavior[END_REF]. GraphNet [START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF], which comprises a graph-constrained elastic net penalty, ( )

, 1 1 Lw w T w α α - +
can also be used with spatial smoothness enforced through a graph Laplacian matrix, L. Alternatively, one may employ GSR [START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF], which involves a penalty of the form:

( ) , 1 ) ( 2 2
Γw w α α -+ J with J(w) being a structured sparsity term and spatial contiguity imposed through Γ. Overviews of structured sparsity can be found in [START_REF] Ng | Generalized Sparse Regularization with Application to fMRI Brain Decoding[END_REF] and [START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF]. To exploit existing optimizers that are designed for sparse regression models in learning priorinformed sparse classifiers, GraphNet employs OS [START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF] to transform discrete class labels, y, into continuous variables, z, while GSR uses GE [START_REF] Yan | Graph Embedding and Extension: A General Framework for Dimensionality Reduction[END_REF] for this purpose. The effects of applying OS and GE prior to classifier learning, as opposed to directly optimizing (1), are unclear. In this work, we present a simple approach to mitigate the need for converting y into continuous variables so that the learning of sparse classifiers informed by prior information, such as connectivity, can be performed as a single optimization.

B. Connectivity-informed Sparse Classifiers

To integrate connectivity into sparse classifier learning, we consider the following formulation:

( ) ( ) ( ) ( ) Lw w w y Xw w T b J b f E α α λ - + + + 1 ) ( , min , , (2)
where L is a d×d weighted graph Laplacian matrix with L ij = -l ij for i ≠ j, L ij = Σ i l ij for i = j, and l ij being the connectivity between features i and j (Section II-C). We note that L being a Laplacian matrix is not essential and other priors may be employed [START_REF] Grosenick | A Family of Interpretable Multivariate Models for Regression and Classification of Whole-brain fMRI Data[END_REF]. If L = Γ T Γ, the penalty in (2) reduces to that of GSR's. The difference is that (2) directly takes Laplacian matrices as input, whereas GSR would require computing a matrix square root. Also, if J(w) = ||w|| 1 , the penalty in [START_REF] Mitchell | Learning to Decode Cognitive States from Brain Images[END_REF] becomes that of GraphNet's. To optimize [START_REF] Mitchell | Learning to Decode Cognitive States from Brain Images[END_REF], if E(•) is differentiable with a gradient, g(w), one may use proximal gradient [START_REF] Jenatton | Multi-scale Mining of fMRI Data with Hierarchical Structured Sparsity[END_REF] with only a simple modification to the gradient required: g mod (w) = g(w)+2λ(1-α)Lw. In this work, we focus on the case where J(w) = ||w|| 1 , which we optimize using two metric projection in combination with limited memory BFGS [START_REF] Schmidt | Projected Netwon-type Methods in Machine Learning[END_REF]. This permits an approximation of the Hessian of E(•) to be exploited in learning the step direction, which helps speed up convergence [START_REF] Schmidt | Projected Netwon-type Methods in Machine Learning[END_REF]. We describe how connectivityinformed SLR classifiers can be built by optimizing (2) next.

C. Connctivity-informed Sparse Logistic Regression

The mis-classification loss of LR is given by [START_REF] Ryali | Sparse Logistic Regression for Whole-brain Classification of fMRI Data[END_REF]:

( ) ( ) ( ) ( ) ( )
∑ + - + = + = n i i T i n b b f E 1 1 exp 1 ln , x y y Xw w , (3)
where x i is a d×1 vector with x i T being the i th row of X. Since (3) is differentiable:

( ) ( ) ∑ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + + - = + ∇ = n i i T i i i b n b f E 1 )) ( exp( 1 1 , x w y y x y Xw w , (4)
incorporation of connectivity in learning a SLR classifier can be achieved by applying e.g. two metric projection [START_REF] Schmidt | Projected Netwon-type Methods in Machine Learning[END_REF] with J(w) = ||w|| 1 in (2) and 2λ(1-α)Lw added to (4). As a measure of connectivity, we use the fiber count between brain areas derived from DTI tractography [START_REF] Damoiseaux | Greater than the Sum of its Parts: A Review of Studies Combining Structural Connectivity and Resting-state Functional Connectivity[END_REF]. Due to crossing fibers as well as how diffusion tensors are more isotropic near gray matter brain areas, the location of the fiber end points is subjected to errors (Fig. 1(a)). To partially alleviate these limitations, we employ a group fiber estimation strategy [START_REF] Goodlett | Group Analysis of DTI Fiber Tract Statistics with Application to Neurodevelopment[END_REF] (Section III) to improve end point localization (Fig. 1(b)).

III. MATERIALS

Task fMRI data were collected from 10 healthy subjects. Each subject performed a passive face viewing task over a period of ~5 min, where ten 18 s blocks of face stimulus interleaved with nine 18 s control blocks of triangles were displayed. Resting state (RS) fMRI data of ~7 min were also collected. Data were acquired at multiple centers using 3T scanners with TR = 2200 ms, TE = 30 ms, and flip angle = 75 o . Slice timing correction, motion correction, temporal detrending, and spatial normalization, were performed on the task fMRI data using the SPM8 software. Similar preprocessing was performed on the RS-fMRI data except a band-pass filter with cutoff frequencies at 0.01 to 0.1 Hz was applied. White matter and cerebrospinal fluid confounds were regressed out from the gray matter voxel time courses.

To account for the delay in hemodynamic response in labeling the fMRI volumes as associated with viewing faces or triangles, we generated a regressor for each stimulus by convolving a boxcar function (having an amplitude of one and time-locked to stimulus) with a hemodynamic response function, and extracted volumes in which the regressor value exceeded 0.5. Only volumes of the last nine blocks for each stimulus were used to ensure equal sample sizes for both stimulus classes. This results in 72 samples per class. DTI data were collected from the same 10 subjects. Acquisition sequence similar to that in [START_REF] Jones | Isotropic Resolution Diffusion Tensor Imaging with Whole Brain Acquisition in a Clinically Acceptable Time[END_REF] was used with TR = 15000 ms, TE = 104 ms, flip angle = 90 o , 36 gradient directions, and b-value = 1300 s/mm 2 . Tensor estimation and fiber tractography were performed at both intra-subject and group level using MedINRIA [START_REF] Toussaint | MedINRIA: Medical Image Navigation and Research Tool by INRIA[END_REF]. For generating group fibers, we first warped all subjects' tensor volumes onto that of an arbitrary subject. We then averaged the tensor volumes across subjects, performed fiber tractography on the average tensor volume, and warped the group fibers back onto each subject's native space. To enable fiber count computation, we divided the brain into P parcels with the parcel template warped onto each subject's B 0 volume. Parcellation was performed by concatenating RS-fMRI time courses across subjects and applying Ward clustering [START_REF] Michel | A Supervised Clustering Approach for fMRI-based Inference of Brain States[END_REF]. P was set to 500 to permit finer brain partitioning than facilitated by standard brain atlases (typically P < 150). This choice of P provides a balance between functional localization and robustness to errors in the location of fiber end points. The parcel template was further used for the generation of task fMRI parcel time courses by averaging voxel time courses within each parcel.

IV. RESULTS AND DISCUSSION

For validation, we considered the task of discriminating fMRI volumes associated with viewing faces against viewing triangles. The average intensity within each parcel was taken as a feature with each volume being a sample. 9-fold crossvalidation was performed to compute classification accuracy. Using 9 folds ensures that volumes within the same stimulus block would not be erroneously assigned to both the training and test set, which inflates classification accuracy due to correlations between temporally adjacent volumes. We compared connectivity-informed SLR with anatomical connectivity prior learned using the group fiber estimation strategy (GASLR) against SVM [START_REF] Mitchell | Learning to Decode Cognitive States from Brain Images[END_REF], LR, LR with ridge penalty (ENLR), and connectivityinformed SLR with intra-subject anatomical connectivity prior (ASLR). Since local spatial correlations between voxels are implicitly modeled in generating functional parcels, comparison against total variation regularization was not performed. To set the parameters α and λ for each training fold, 8-fold internal cross validation [START_REF] Mitchell | Learning to Decode Cognitive States from Brain Images[END_REF] was performed with α = {0.1, 0.3, 0.5, 0.7, 0.9} and λ = {10 -4 , 10 -3 , 10 -2 , 10 -1 , 10 0 , 10 1 }. For qualitative assessment, we performed 9-fold cross validation on the whole sample set to determine the optimal α and λ. We then generated 100 subsamples of size 72 (i.e. half of the total number of samples) and learned a classifier for each subsample with α and λ fixed to the optimal value. The classifier weights across subsamples were averaged to identify parcels consistently assigned higher weights.

Results of the contrasted classifiers are shown in Fig. 2. Only classifier weight patterns of an exemplar subject are displayed due to space limitation. Among the contrasted methods, SVM obtained the lowest average classification accuracy over subjects, and the classifier weight patterns seemed spatially spurious. Using LR resulted in 2% higher accuracy compared to SVM, but the classifier weight patterns appeared similar. Controlling overfitting with a ridge penalty led to a further 2% increase in accuracy, but only a slight improvement in localization of relevant parcels. Enforcing sparsity using SLR provided an additional 1% increase in accuracy over using a ridge penalty with more localized classifier weight patterns obtained. However, rather small weights were assigned to parcels in the fusiform face area (FFA), which is known to be specialized for face recognition. Using LR with elastic net resulted in a 0.5% accuracy gain over SLR and more weights assigned to parcels within the FFA, but localization power was reduced compared to SLR. Incorporating intra-subject anatomical connectivity into SLR actually led to lower accuracy than the contrasted sparse classifiers. We suspect the decrease in accuracy was due to errors in fiber tractography, which could have a major impact on the connectivity estimates. By using the group fiber extraction strategy to improve connectivity estimation and integrating the resulting connectivity prior into SLR, the highest classification accuracy was attained with weights consistently assigned to parcels within the FFA.

V. CONCLUSIONS

We proposed informing sparse classifier learning with connectivity for fMRI decoding. We showed that with only a minor change to the gradient, integration of connectivity is facilitated. On real data, we demonstrated that incorporating connectivity inferred from a group fiber estimation strategy improves classification accuracy over standard classifiers, such as SVM and LR, as well as a number of sparse linear classifiers. Classifier weights were also more consistently assigned to neurologically-relevant brain areas. Our results thus provide further evidence for the presence of intrinsic relationships between brain structure and function.

  (a) intra-subject fibers (b) group fibers Figure 1. Fiber estimation strategies. Fibers passing through a box around the FFA displayed. (a) Fibers estimated from a single exemplar subject's tensor volume. (b) Fibers estimated from subject-average tensor volume.

  Classification Accuracy Figure 2. Classifier comparison. (a)-(g) Classifier weights averaged over 100 subsamples for an exemplar subject. Only positive weights displayed for clarity. The fusiform face area (FFA), which is involved with face recognition, is roughly encircled in blue. (h) Average classification accuracy over subjects. Adding a group connectivity prior resulted in the highest accuracy among all contrasted methods with classifier weights localized in the FFA.

ACKNOWLEDGMENT This work was supported by the ANR grant, BrainPedia ANR-10-JCJC 1408-01, and the Berkeley INRIA Stanford grant. The data were acquired within the IMAGEN project. J.B. Poline was partly funded by the IMAGEN project, which receives funding from the E.U. Community's FP6, LSHM-CT-2007-037286. This manuscript reflects only the authors' views and the Community is not liable for any use that may be made of the information contained therein.


István Hegedűs
email: ihegedus@inf.u-szeged.hu

Róbert Busa-Fekete

Róbert Ormándi
email: ormandi@inf.u-szeged.hu

Márk Jelasity
email: jelasity@inf.u-szeged.hu

Balázs Kégl
email: balazs.kegl@gmail.com

Peer-to-Peer Multi-Class Boosting ⋆

Keywords: P2P, gossip, multi-class classification, boosting, FilterBoost

We focus on the problem of data mining over large-scale fully distributed databases, where each node stores only one data record. We assume that a data record is never allowed to leave the node it is stored at. Possible motivations for this assumption include privacy or a lack of a centralized infrastructure. To tackle this problem, earlier we proposed the generic gossip learning framework (GoLF), but so far we have studied only basic linear algorithms. In this paper we implement the well-known boosting technique in GoLF. Boosting techniques have attracted growing attention in machine learning due to their outstanding performance in many practical applications. Here, we present an implementation of a boosting algorithm that is based on FilterBoost. Our main algorithmic contribution is a derivation of a pure online multi-class version of FilterBoost, so that it can be employed in GoLF. We also propose improvements to GoLF, with the aim of maximizing the diversity of the evolving models gossiped in the network, a feature that we show to be important. We evaluate the robustness and the convergence speed of the algorithm empirically over three benchmark databases. We compare the algorithm with the sequential AdaBoost algorithm and we test its performance in a failure scenario involving message drop and delay, and node churn.

Introduction

Making data analysis possible in fully distributed systems via data mining tools has been an important research direction in the past decade. Tasks such as information retrieval, recommendations, detecting spam, vandalism and intrusion require sophisticated models that are based on large amounts of data. This data is often generated in a fully distributed fashion on routers, PCs, smart phones or sensor nodes. In many cases local data cannot be collected centrally due to privacy constrains or due to the lack of computing infrastructure.

In this paper we are concerned with the scenario in which there is a very large number of nodes, all of which store small amounts of data, such as personal profiles or recent sensor readings. In our previous work, we have proposed the gossip learning framework (GoLF) for data mining in such environments [START_REF] Ormándi | Asynchronous peer-to-peer data mining with stochastic gradient descent[END_REF][START_REF] Ormándi | Efficient p2p ensemble learning with linear models on fully distributed data[END_REF]. The basic idea is that models perform random walks in the network, while being improved by an arbitrary online learning method. Convergence can be improved significantly if nodes combine the models that pass through them, or if they use other techniques such as voting. In this framework we have so far only studied learning linear models.

In this paper we develop a boosting algorithm, which proves the viability of gossip learning also for implementing state-of-the-art machine learning algorithms. In a nutshell, a boosting algorithm constructs a classifier in an incremental fashion by adding simple classifiers (that is, weak classifiers) to a pool. The weighted vote of the classifiers in the pool determines the final classification.

Our contributions are the following. First, to enable P2P boosting via gossip, we derive a purely online multi-class boosting algorithm that can be proven to minimize a certain negative log likelihood function. We also introduce efficient multi-class weak learners to be used by the online boosting algorithm. Second, we improve GoLF to make sure that the diversity of the models in the network is preserved. This makes it meaningful to spread the current best model in the network; a technique we propose to improve local prediction performance. Finally, we perform simulation experiments where we study our algorithm under extreme message drop, message delay and node churn to prove its robustness.

System Model and Data Distribution

Our system model is a network of computers (peers). Each node in the network has a unique network address and can communicate with other nodes through messages if the address of the target node is locally available. We also assume that a peer sampling service is available that provides addresses of random available peers at any time. Here we use Newscast [START_REF] Tölgyesi | Adaptive peer sampling with newscast[END_REF] as our peer sampling service. Messages can be delayed or dropped, moreover, new nodes can join and leave the network without any warning. We assume that when a node rejoins the network it has the same state as at the time of going offline.

Regarding data distribution, we assume that the data records are distributed horizontally, that is, all the nodes store full records. At the same time, all the nodes store only very few records, perhaps only a single record. This excludes the possibility of any local statistical processing of the data. Another important assumption is that the data never leave the nodes, that is, it is not allowed to collect the data centrally due to privacy or infrastructural constraints.

Background and Related Work

The problem we tackle in this paper is supervised classification that can be formally defined as follows. We are given a training database in the form of a set of training instances. Each training instance consists of a feature vector and a corresponding class label. Let us denote this training dataset by S = {(x 1 , y 1 ), . . . ,

(x n , y n )} ⊂ R d × {-1, +1} K ,

8:

currentModel ← m samples, including those not in the training set, with high probability (generalization). In multi-class classification problems-where K > 2-one and only one of the elements of y i is +1, whereas in multi-label (or multi-task ) classification y i is arbitrary, meaning that the observation x i can belong to several classes at the same time. In the former case we will denote the index of the correct class by ℓ(x i ). In classical multi-class classification the elements of f (x) are treated as posterior scores corresponding to the labels, so the predicted label is ℓ(x) = arg max ℓ=1,...,K f ℓ (x) where f ℓ (x) is the ℓth element of f (x). The function f is called the model of the data.

As mentioned before, in this paper we focus on online boosting in GoLF. A few proposals for online boosting algorithms are known. An online version of AdaBoost [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF] is introduced in [START_REF] Fan | The application of AdaBoost for distributed, scalable and on-line learning[END_REF] that requires a random subset from the training data for each boosting iteration, and the base learner is trained on this small sample of the data. The algorithm has to sample the data according to a non-uniform distribution making it inappropriate for pure online training. A gradient-based online algorithm is presented in [START_REF] Babenko | A family of online boosting algorithms[END_REF], which is an extension of Friedman's gradient-based framework [START_REF] Friedman | Stochastic gradient boosting[END_REF]. However, their approach is for binary classification, and it is not obvious how it can be extended to multi-class problems. Another notable online approach is Oza's online algorithm [START_REF] Oza | Online bagging and boosting[END_REF] whose starting point is AdaBoost.M1 [START_REF] Freund | Experiments with a new boosting algorithm[END_REF]. However, AdaBoost.M1 requires the base learning algorithm to achieve 50% accuracy for any distribution over the training instances. This makes it impractical in multi-class classification since most of the weak learners used as a base learner do not satisfy this condition.

We also discuss work related to fully distributed P2P data mining in general. We note that we do not overview the extensive literature of parallel machine learning algorithms because they have a completely different underlying system model and motivation. We do not discuss those distributed machine learning approaches either that assume the availability of sufficient local data to build models locally (a survey can be found in [START_REF] Park | Distributed data mining: Algorithms, systems, and applications[END_REF]).

One notable and relevant research direction is gossip-based algorithms where convergence to global functions over fully distributed data is achieved through local communication. Perhaps the simplest example is gossip-based averaging [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF][START_REF] Kempe | Gossip-based computation of aggregate information[END_REF], where the gossip approach is extremely robust, scalable, and efficient. However, gossip algorithms support more sophisticated algorithms that compute more complex global functions. Examples include the EM algorithm [START_REF] Kowalczyk | Newscast EM[END_REF], LDA [START_REF] Asuncion | Asynchronous distributed estimation of topic models for document analysis[END_REF] or PageRank [START_REF] Jelasity | Asynchronous distributed power iteration with gossip-based normalization[END_REF]. Numerous other P2P machine learning algorithms have also been proposed, as in [START_REF] Luo | Distributed classification in peer-to-peer networks[END_REF][START_REF] Siersdorfer | Automatic document organization in a P2P environment[END_REF]. A survey of many additional ideas can be found in [START_REF] Datta | Distributed data mining in peer-to-peer networks[END_REF]. This work builds on the Gossip Learning Framework (GoLF) [START_REF] Ormándi | Asynchronous peer-to-peer data mining with stochastic gradient descent[END_REF][START_REF] Ormándi | Efficient p2p ensemble learning with linear models on fully distributed data[END_REF], which offers an abstraction to implement a wide range of machine learning algorithms.

The skeleton of GoLF is shown in Alg. 1. This algorithm runs on each node. The algorithm consists of an active loop that runs periodically and an event handler (onReceiveModel) which is called when a new model arrives. The models take random walks over the network by selecting a random node (line 4)

Algorithm 2 FilterBoost(Init(), Update(•, •, •, •), T, C) 1: f (0) (x) ← 0 2: for t ← 1 → T do 3: Ct ← C log(t + 1)
4:

h (t) (•) ← Init 5: for t ′ ← 1 → Ct do
⊲ Online base learning 6:

x, y, w ← Filter f (t-1) (•) ⊲ Draw a weighted random instance 7:

h (t) (•) ← UPDATE x, y, w, h (t) (•) 8: γ ← 0, W ← 0 9:
for t ′ ← 1 → Ct do ⊲ Estimate the edge on a filtered data 10:

x, y, w ← Filter f (t-1) (•) ⊲ Draw a weighted random instance 11:

γ ← γ + K ℓ w ℓ h (t) ℓ (x)y ℓ , W ← W + K ℓ w ℓ 12:
γ ← γ/W ⊲ Normalize the edge 13:

α (t) ← 1 2 log 1+γ
1-γ 14:

f (t) (•) = f (t-1) (•) + α (t) h (t) (•) 15: return f (T ) (•) = T t=1 α (t) h (t) (•)
16: procedure Filter(f (•)) 17:

(x, y) ← RandomInstance() ⊲ Draw random instance

18:

for ℓ ← 1 → K do 19:

w ℓ ← exp f ℓ (x)-f ℓ(x) (x) K ℓ ′ =1 exp f ℓ ′ (x)-f ℓ(x) (x)

20:

return (x, y, w)

and jumping there (line 5). Procedure onReceivedModel updates the received model using the training sample stored by the node (line 7, where x and y represent a training example and the corresponding class label, respectively). It then stores the model as the current model (line 8). In this skeleton the model is an abstract class which provides the update possibility. We note that models can also be combined [START_REF] Ormándi | Efficient p2p ensemble learning with linear models on fully distributed data[END_REF] or they can interact through ensemble learning techniques (like voting) [START_REF] Ormándi | Asynchronous peer-to-peer data mining with stochastic gradient descent[END_REF], which results in a substantial performance improvement. Regarding model interaction, additional details will be given later in relation to the boosting algorithm.

Multi-Class Online FilterBoost

This section introduces our main contribution, a multi-class online boosting algorithm that can be applied in GoLF. We build on FilterBoost [START_REF] Bradley | FilterBoost: Regression and classification on large datasets[END_REF] where the main idea is to filter (sample) the training examples in each boosting iteration and to give the base learner only this smaller, filtered subset of the original training dataset, leading to fast base learning. The performance of the base classifier is also estimated on an additional random subset of the training set resulting in further improvement in speed.

Our formulation of the FilterBoost algorithm is given as Alg. 2. This is not yet in a form to be applied in GoLF, but the transformation is trivial as discussed in Section 6. This fully online formulation is equivalent to FilterBoost, except that it handles multi-class problems as well. To achieve this, while ensuring that the algorithm can still be theoretically proven to converge, our key contribution is the derivation of a new weight formula calculated in line 19. First we introduce this formula, then we explain Alg. 2 in more detail.

A boosting algorithm can be thought of as a minimization algorithm of an appropriately defined target function over the space of models. The target function is related to the classification error over the training dataset. The key idea is that we select an appropriate target function that will allow us to both derive an appropriate weight, as well as argue for convergence. Inspired by the logistic regression approach of [START_REF] Collins | Logistic regression, AdaBoost and Bregman distances[END_REF], we will use the following negative log likelihood function as our target function:

R L f = - n i=1 ln exp f ℓ(xi) (x i ) K ℓ ′ =1 exp f ℓ ′ (x i ) = n i=1 ln   1 + K ℓ =ℓ(xi) exp f ℓ (x i ) -f ℓ(xi) (x i )  
(1) Note that the FilterBoost algorithm returns a vector-valued classifier f : R d → R K . The rest of the definitions and notations were introduced in Section 3.

FilterBoost builds the final classifier f as a weighted sum of base classifiers h (t) : R d → {-1, +1} K returned by a base learner algorithm which has to be able to handle weighted training data. The class-related weight vector assigned to x i in iteration t is denoted by w (t) i and its ℓth element is denoted by w

(t) i,ℓ . It can be shown that selecting w (t)
i,ℓ so that it is proportional to the output of the current strong classifier

w (t) i,ℓ = exp f (t) ℓ (x i ) -f (t) ℓ(xi) (x i ) K ℓ ′ =1 exp f (t) ℓ ′ (x i ) -f (t) ℓ(xi) (x i ) . (2)
ensures that our target function in (1) will decrease in each boosting iteration.

The proof is outlined in the Appendix. The pseudocode of FilterBoost is shown in Alg. 2. Here, the algorithm is implemented according to the practical suggestions given in [START_REF] Bradley | FilterBoost: Regression and classification on large datasets[END_REF]: first, the number of randomly selected instances is C log(t + 1) in the tth iteration (where C is a constant parameter), and second, in the Filter method the instances are first randomly selected then re-weighted based on their scores given by f (t) (•). Procedure Init() initializes the parameters of the base classifier (line 4), and Update(•, •, •, •) updates (line 7) the parameter of the base classifier using the current training instance x given by Filter(•). The input parameter T is the number of iterations, and C controls the number of instances used in one boosting iteration. α (t) is the base coefficient, h (t) (•) is the vector-valued base classifier, and f (T ) (•) is the final (strong) classifier. Procedure RandomInstance() selects a random instance from the training data X, Y.

Let us point out that there is no need to store more than one training instance anywhere during execution. Second, the algorithm does not need any global information about the training data, such as the size, so this implementation can be readily applied in a pure online environment.

Multi-Class Online Base Learning

For the online version of FilterBoost, we need to propose online base learners as well. In FilterBoost, for theoretical reasons, the base classifiers are restricted to output discrete predictions in {-1, +1} K and, in addition, they have to minimize the weighted exponential loss

E h, f (t) = n i=1 K ℓ=1 w (t) i,ℓ exp -h ℓ (x i )y i,ℓ . (3)
We follow this approach and, in addition, we build on our base learning framework [START_REF] Kégl | Boosting products of base classifiers[END_REF] and assume that the base classifier h(x) is vector-valued and represented as h Θ (x) = sign(vϕ Θ (x)), parameterized by v ∈ R K (the vote vector ), and ϕ Θ (x) : R d → R, a scalar base classifier parameterized by Θ. The coordinatewise sign function is defined as sign : R K → {-1, +1} K . In this framework, learning consists of tuning Θ and v to minimize the weighted exponential loss (3). Since it is hard to optimize the non-differentiable function h Θ even in batch mode, we take into account only h Θ (x) = vϕ Θ (x). This approach is heuristic as it is hard to say anything about the relation between E h Θ , f (t) and E h Θ , f (t) , but in practice this base learning approach performs quite well.

Since ϕ Θ (•) is differentiable, the stochastic gradient descent (SGD) [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF] algorithm provides a convenient way to train the base learner in an online fashion. The SGD algorithm updates the parameters iteratively based on one training instance at a time. Let us denote Q(x, y, w, v, Θ)

= K ℓ=1 w ℓ exp -y ℓ v ℓ ϕ Θ (x) .
Then the gradient based parameter update can be calculated as follows:

Θ (t ′ +1) ← Θ (t ′ ) + γ (t ′ ) ▽ Θ Q(x, y, w, v, Θ) (4)
v (t ′ +1) ← v (t ′ ) + γ (t ′ ) ▽ v Q(x, y, w, v, Θ) (5)
This update rule can be used in line 7 of FilterBoost to update the base classifier. A simple decision stump or AdaLine [START_REF] Widrow | Adaptive Switching Circuits[END_REF] can be easily accommodated to this multi-class base learning framework. In the following we derive the update rules for a decision stump, that is, a one-decision two-leaf decision tree having the form

ϕ j,b (x) = 1 if x (j) ≥ b, -1 otherwise, ( 6
)
where j is the index of the selected feature and b is the decision threshold. Since ϕ j,b (x) is not differentiable with respect to b, we decided to approximate it by the differentiable sigmoidal function, whose parameters can be tuned using SGD.

The sigmoidal function can be written as

s j,θ (x) = s j,(c,d) (x) = 1 1 + exp -cx (j) -d .
where Θ = (c, d). And ϕ j,b (•) can be approximated by ϕ j,b (x) ≈ 2s j,θ (x) -1.

Then the weighted exponential loss of this so-called sigmoidal decision stump for a single instance can be written as

Q j = Q j (x, y, w, v, Θ) = K ℓ=1 w ℓ exp (-v ℓ (2s j,θ (x) -1) y ℓ )
and its partial derivatives are

∂Q j ∂v ℓ = -exp (-v ℓ (2s j,θ (x) -1) y ℓ ) w ℓ (2s j,θ (x) -1) y ℓ ∂Q j ∂c = -2 K ℓ=1 exp (-v ℓ (2s j,θ (x) -1) y ℓ ) w ℓ v ℓ y ℓ x (j) s j,θ (x) (1 -s j,θ (x)) ∂Q j ∂d = -2 K ℓ=1 exp (-v ℓ (2s j,θ (x) -1) y ℓ ) w ℓ v ℓ y ℓ s j,θ (x) (1 -s j,θ (x))
The initial value of c and d were set to 1 and 0, respectively (line 4 of Alg. 2). So far, we implicitly assumed that the index of feature j is given. To choose j, we trained sigmoidal decision stumps in parallel for each feature and we estimated the edge of each of them using the sequential training data as

γ j = Ct t ′ =1 K ℓ=1 w t ′ ,ℓ y t ′ ,ℓ sign v (t ′ ) ℓ ϕ j,Θ (t ′ ) j (x t ′ )
. Finally, we chose the feature with the highest edge estimate j * = arg max j γ j .

In every boosting iteration we also train a constant learner (also known as yintercept) and use it if its edge is higher than the edge of the best decision stump we found. The output of the constant learner does not depend on the input vector x, that is ϕ(•) ≡ 1, in other words it returns the vote vector v itself. Thus only v has to be learnt but this can be done easily by calculating the classwise edge

v ℓ = Ct t ′ =1 w t ′ ,ℓ y t ′ ,ℓ .

GoLF Boosting

In order to adapt Alg. 2 to GoLF (Alg. 1), we need to define the permanent state of the FilterBoost model class, and we need to provide an implementation of the updateModel method. This is rather straightforward: the model instance has to store the the actual strong learner f (t) as well as the state of the inner part of the two for loops in Alg. 2 so that updateModel could simulate these loops every time a new sample is processed.

This way, every model that is performing a random walk is theoretically guaranteed to converge so long as we assume that peer sampling works perfectly. However, there is a catch. Since in each iteration some nodes will receive more than one model, while others will not receive any, and since the number of models in the network is kept constant if there is no failure (since in each iteration all the nodes send exactly one model) it is clear that the diversity of models will decrease. That is, some models get replicated, while others "die out". Introducing failure makes things a lot worse, since we can lose models due to message loss, delay, and churn as well, which speeds up homogenization. This is a problem, because diversity is important when we want to apply techniques such as combination or voting [START_REF] Ormándi | Asynchronous peer-to-peer data mining with stochastic gradient descent[END_REF][START_REF] Ormándi | Efficient p2p ensemble learning with linear models on fully distributed data[END_REF]. Without diversity these important techniques are guaranteed not to be effective.

The effects of decreasing diversity are negligible during the timespan of a few gossip cycles, but a boosting algorithm needs a relatively large number of cycles to converge (which is not a problem, since the point of boosting is not speed, but classification quality). So we need to tackle the loss of diversity. We propose Alg. 3 to deal with this problem.

This protocol works as follows. A node sends models in an active cycle (line 4) only in two cases: it sends the last received model if there was no incoming model until 10 active cycles (line 6), otherwise it sends all of the models received since the last cycle (line 13). If there is no failure, then this protocol is guaranteed to keep the diversity of models, since all the models in the network will perform independent random walks. Due to the Poisson distribution of the number of incoming models in one cycle, the probability of bottlenecks is diminishing, and for the same reason the probability that a node does not receive messages for 10 cycles is also practically negligible.

If the network experiences message drop failures or churn, then the number of models circulating in the network will converge to a smaller value due to the

22:

currentModel ← m 10 cycle waiting time, and the diversity can also decrease, since after 10 cycles a model gets replicated in line 9. Interestingly, this is actually useful because if the diversity is low, it makes sense to circulate fewer models and to wait most of the time, since information is redundant anyway. Besides, with reliable communication channels that eliminate message drop (but still allow for delay), diversity can still be maintained.

Finally, note that if there is no failure, Alg. 3 has the same total message complexity as Alg. 1 except for the extremely rare messages sent in line 4. In case of failure, the message complexity decreases as a function of failure rate; however, the remaining random walks do not get slower relative to Alg. 1, so the convergence rate remains the same on average, at least if no model-combination techniques are used.

Experimental Results

In our experiments we examined the performance of our proposed algorithm as a function of gossip cycles, which is about the same as the number of training samples seen by any particular model. To validate the algorithm, we compared it with three baseline multi-class boosting algorithms, all using the same decision stump (DS) weak learner. The first one is the multi-class version of the well known AdaBoost [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF] algorithm, the second one is the original FilterBoost [START_REF] Bradley | FilterBoost: Regression and classification on large datasets[END_REF] method implemented for a single processor, with the setting C = 30, and the third one is the online version of FilterBoost (Alg. 2). We used three multiclass classification benchmark datasets to evaluate our method, namely the CTG, the PenDigits and the Segmentaion databases. These were taken from the UCI repository [START_REF] Frank | UCI machine learning repository[END_REF] and have different size, number of features, class distributions and characteristics. The basic properties of the datasets can be found in Table 1.

In the P2P experiments we used the PeerSim [23] simulation environment to model message delay, drop and peer churn. We used two scenarios: a perfect network without any delay, drop or churn; and a scenario with heavy failure where the message delay was drawn uniformly at random from the interval [∆; 10∆], a message was dropped with a probability of 0.5 and the online/offline session lengths of peers were modeled using a real P2P bittorrent trace [1]. As our performance metric, we applied the well known 0-1 error (or error rate), which is the proportion of test instances that were incorrectly classified.

Figure 1 illustrates the effect of parameter C. Larger values result in slower convergence but better eventual performance. The setting C = 30 represents a good tradeoff in these datasets, so from now on we fix this value. We compared our online boosting algorithm to baseline algorithms as can be seen in Figure 2 (left hand side). The figure shows that the algorithms converge to a similar error rate, which was expected. Moreover, our online FilterBoost converges faster than the AdaBoost algorithm and it has almost the same convergence rate as that for the sequential FilterBoost method. Note that since two of these algorithms are not online, we had to approximate the number of (not necessarily different) training samples used in one boosting iteration. We used a lower bound to be conservative.

In our P2P evaluations of GoLF Boosting we used the mean error rate of 100 randomly selected nodes in the network to approximate the performance of the algorithm. Figure 2 (right hand side) shows that without failure the performance is very similar to that of our online FilterBoost algorithm. Moreover, in the extreme failure scenario, the algorithm still converges to the same error rate, although with a delay. This delay can be accounted for using a heuristic argument: since message delay in itself represents a slowdown of a factor of 5 on average, message drop and churn contributes approximately another factor of 2.

Finally, we demonstrate a novel way of exploiting model diversity (see Section 6): through gossip-based minimization one can spread the model with the best training performance, thus the best model can be made available to all nodes at all times. Figure 3 demonstrates this technique for different algorithms. We include results over the segmentation database only, the other two datasets produce similar results.

The top left plot shows results with GoLF Boosting. It can be seen that the best model based on training performance is not necessarily the best over the test set, but it is reasonably good, and results in a speedup of about a factor of 2. The top right plot belongs to the original GoLF implementation (Alg. 1). Due to the complete lack of diversity, the best model's performance is almost identical to the average one. The bottom left plot is a baseline experiment that represents the case with the maximal possible diversity, based on 100 completely independent runs of the online FilterBoost algorithm. Finally, the bottom right plot collects the most interesting curves from the other three plots allowing a better comparison.

Conclusions

We demonstrated that the GoLF is suitable for the implementation of multiclass boosting. The significance of this result is that boosting is a state-of-the-art machine learning technique from the point of view of the quality of the learned models, which is now available in the P2P system model with fully distributed data. To achieve this, we proposed a modification of FilterBoost that allows it to learn multi-class models in a purely online fashion, and we proved theoretically that the resulting algorithm optimizes a suitably defined negative log likelihood measure. Our experimental results demonstrate the robustness of the method. We also identified the lack of model diversity as a potential problem with GoLF.

We provided a solution that was demonstrated to be effective in preserving the difference between the best model and the average models; this allowed us to propose spreading the best model as a way to benefit from the large number of models in the network.

6 :

 6 where d is the dimension of the problem and K defines the number of classes. The goal of the classification problem is to find a function f : R d → {-1, +1} K that can correctly classify any Algorithm 1 Skeleton of original GoLF learning protocol 1: currentModel ← initModel() procedure onReceiveModel(m) 7:m.updateModel(x, y)

Algorithm 3

 3 Diversity Preserving GoLF 1: currentModel ← initModel() 2: modelQueue.add(currentModel) 3: counter ← 0

Fig. 1 .

 1 Fig. 1. The effect of parameter C in online FilterBoost (Alg. 2).

Fig. 2 .

 2 Fig. 2. Comparison of boosting algorithms (left column) and P2P simulations (right column). FB and AF stand for FilterBoost and the "all failures" scenario, respectively.

Table 1 .

 1 The main properties of the data sets, and the prediction errors of the baseline algorithms.

						CTG		PenDigits	Segmentation
			Training set size		1,701		7494	2100
			Test set size			425		3,492	210
			Number of features			21		16	19
			Class labels	1325/233/143 10 classes (uniform) 7 classes (uniform)
			AdaBoost (DS)		0.109347	0.060715	0.069048
			FilterBoost (DS, C30)		0.094062	0.071657	0.062381
				CTG -C Trade-off				PenDigits -C Trade-off	Segmentation -C Trade-off
	Error Rate	0.1 0.12 0.14 0.16 0.18 0.2 0.22 0.24	C=5 C=10 C=30 C=100	Error Rate	0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9	C=100 C=5 C=30 C=10	Error Rate	0.1 0.2 0.3 0.4 0.5 0.6 0.8 0.7	C=5 C=10 C=30 C=100
		100	1000 10000 100000 1e+06	100	1000 10000 100000 1e+06	100	1000 10000 100000 1e+06
				Num. of Samples					Num. of Samples	Num. of Samples

  The improvement due to estimating the best model based on training performance. The Segmentation dataset is shown.

			Diversity Preserving GoLF			Original GoLF
		0.8 0.9		Estimated Min. Average		0.9 0.8		Estimated Min. Average
		0.7				0.7
	Error Rate	0.4 0.5 0.6			Error Rate	0.4 0.5 0.6
		0.3				0.3
		0.2				0.2
		0.1				0.1
		100	1000	10000	100000	100	1000	10000	100000
			Num. of Samples			Num. of Samples
			Online FilterBoost			Comparison of Minimums
		0.8 0.9		Estimated Min. Average		0.9 0.8		Original GoLF Div. Pres. GoLF
	Error Rate	0.4 0.5 0.6 0.7			Error Rate	0.4 0.5 0.6 0.7		Online FB
		0.3				0.3
		0.2				0.2
		0.1				0.1
		100	1000	10000	100000	100	1000	10000	100000
			Num. of Samples			Num. of Samples
	Fig. 3.

⋆ M. Jelasity was supported by the Bolyai Scholarship of the Hungarian Academy of Sciences. This work was partially supported by the FET programme FP7-COSI-ICT of the European Commission through project QLectives (grant no.: 231200) and by the ANR-2010-COSI-002 grant of the French National Research Agency.

Appendix

The second order expansion of multi-class negative log likelihood for fixed α and h(x) = 0 can be written as

where

. Let us note that the last term does not depend on h(•), consequently minimizing this approximation of R L f (t) + αh with respect to h(x) is equivalent to maximizing the weighted accuracy and the weight of the ℓth label is