Monsieur Jerôme

Malick Chercheur

Madame Marianne

Clausel Professeur

Universite De Lorraine

This thesis focuses on developing scalable algorithms for large scale machine learning.

In this work, we present two perspectives to handle large data. First, we consider the problem of large-scale multiclass classification. We introduce the task of multiclass classification and the challenge of classifying with a large number of classes. To alleviate these challenges, we propose an algorithm which reduces the original multiclass problem to an equivalent binary one. Based on this reduction technique, we introduce a scalable method to tackle the multiclass classification problem for very large number of classes and perform detailed theoretical and empirical analyses.

In the second part, we discuss the problem of distributed machine learning. In this domain, we introduce an asynchronous framework for performing distributed optimization. We present application of the proposed asynchronous framework on two popular domains: matrix factorization for large-scale recommender systems and largescale binary classification. In the case of matrix factorization, we perform Stochastic Gradient Descent (SGD) in an asynchronous distributed manner. Whereas, in the case of large-scale binary classification we use a variant of SGD which uses variance reduction technique, SVRG as our optimization algorithm.

Résumé

L'objectif de cette thèse est de développer des algorithmes d'apprentissage adaptés aux grandes masses de données. Dans un premier temps, nous considérons le problème de la classification avec un grand nombre de classes. Afin d'obtenir un algorithme adapté à la grande dimension, nous proposons un algorithme qui transforme le problème multi-classes en un problème de classification binaire que nous sous-échantillonnons de manière drastique. Afin de valider cette méthode, nous fournissons une analyse théorique et expérimentale détaillée. Dans la seconde partie, nous approchons le problème de l'apprentissage sur données distribuées en introduisant un cadre asynchrone pour le traitement des données. Nous appliquons ce cadre à deux applications phares : la factorisation de matrice pour les systèmes de recommandation en grande dimension et la classification binaire. iv v First and foremost, I would like to express my sincere gratitude to my thesis supervisor, Massih-Reza Amini, for his continuous support and guidance for this thesis.

I really appreciate his knowledge and kindness which made this work possible and always allowed me to work in a stress free environment. I also like to thank my cosupervisor Franck Iutzeler for his valuable guidance and motivation for this thesis. I was always impressed by his brilliance and energy for research.

My appreciation also extends to my jury members for their interesting questions and comments during my thesis defense. Moreover, I would like to thank my theis reviewers for carefully reviewing my thesis report and giving very insightful comments, which immensely helped me to improve the quality of my thesis report.

I am also thankful to the AMA laboratory for providing me the required resources and workspace for conducting my research. I also like to thank my lab colleagues, with whom I spent a wonderful time.

Last but not at all the least, I would like express my gratitude to all my family members for always motivating me and believing in my abilities. Especially, I am indebted to my mother, for her continuous love and support through my entire life. Denote by the set of distinct terms within then x t is the frequency of term t in x, y t = x∈ y x t , | y| = t∈ y t , F t = x∈ x t , l = t∈ t . Finally, I t is the inverse document frequency of term t, len( y) is the length (number of terms) of documents in class y, and av g(len( y)) is the average of document lengths for all the classes . . . Machine Learning (ML) algorithms help to extract useful information from data, so that it can be utilized in future for useful tasks such as prediction or clustering. ML algorithms work by learning a model or pattern from the data and using the model to discover useful information for the future unseen data. These algorithms have proved to have a huge social and economic impact for different stakeholders. This has fueled the popularity of ML in applications such as document analysis, computer vision, natural language processing, voice recognition, recommendation, ranking and many others.

In the last decade we have seen an exponential growth in the quantity of data, mainly due to the popularity of digital technologies. Some of the areas where such large scale data collections are prevalent are Computer Vision, Recommender Systems, Information Retrieval, Social Networks, etc. Efficiently handling and effectively exploiting such large magnitude of data has opened a new area of research. Also such large magnitude of data has posed a serious challenge for the traditional ML techniques. So, there is a need to adapt and improve the existing ML techniques to scale well and cope up with the new applications.

As the title suggests, in this thesis we intend to analyze the challenges of largescale data in ML and devise effective algorithms to tackle it. In our study we consider two different areas involving large-scale data. Even though they are two separate perspectives, they both come under the umbrella of large-scale ML. First, we study and analyze the problem of large-scale multiclass classification. Second, we study distributed computing for handling large-scale data.

LARGE-SCALE MULTICLASS CLASSIFICATION

Multiclass classification refers to classification problems where we need to classify an example to one of finite set of categories. The goal of these algorithms is to learn a function which, given a new example will correctly assign a class label. Some of the popular applications of multiclass classification are text, image or video classification.

Traditionally, multiclass classification problems involved at most hundreds of classes, however, in the past few years we have observed a spectacular increase in data thanks to the popularity of internet and social media websites such as Facebook1 , Wikipedia2 , Flickr3 , Youtube4 etc. As for example there are around thousands of new articles added to Wikipedia5 every day and each of them has to be categorized to one of millions of categories.

Similarly, recent applications involving text or image classification has to deal with very large number of classes (upto millions), hence this is also referred as extreme classification. Extreme classification poses several challenges to the existing approaches of multiclass classification. First set of challenges are related to the computational complexity of the algorithms. More precisely, learning a model using such large magnitude of data significantly increases the total runtime of the algorithm as well as the total memory used during the learning process. Another set of challenges are introduced from the underlying properties of such large scale data collections. First of which is known as class imbalance problem. In large-scale multiclass collections it is observed that most of the classes has very few representative examples as shown in the growth of size of data over the years6 . It is evident from the exponential growth of the size of data that, it is difficult to store such huge amount of data in one single machine. Even if we can keep such data in a single machine it will take tediously long time to perform learning in a sequential manner as in traditional machine learning approaches. So, with the rapid development and availability of computing resources, the obvious solution to tackle this problem is to adopt distributed techniques.

In distributed computing, the data is partitioned and dispatched across several machines and learning is performed simultaneously. In such a setting, each of the computing nodes have their own memory and processing units. The memory is not shared between the machines in distributed setting. This is different from commonly used technology known as shared-memory parallel computing, which is often confused with distributed computing. In parallel computing each of the computing units In distributed computing, information is exchanged between the machines using the network bandwidth, which is often very limited. So, communication is one of the scarcest resources in distributed computing [Li, 2017]. Most of the distributed methods rely on exchanging the gradients of loss function after every iteration [START_REF] Zhang | Fast distributed asynchronous sgd with variance reduction[END_REF], Huo and Huang, 2016, Dean et al., 2012]. Hence, they tend to become expensive in terms of communication cost. Also, many of the distributed algorithms perform information exchange in a synchronized manner [Sra, 2012, Ho et al., 2013, Mairal, 2015]. For such methods, the slower machines become the bottleneck for the whole system, as faster machines has to wait for the slower machines to finish their computation. Hence, there is a need for totally distributed algorithms which can overcome the synchronization problem as well as minimize the total cost of communication between the machines.

THESIS CONTRIBUTIONS

In this thesis, we take into account the above-mentioned problems of large-scale machine learning and propose algorithms in each of these domains which try to overcome the challenges addressed. We will discuss about the specific contributions corresponding to each of the problem in the following sections:

LARGE-SCALE MULTICLASS CLASSIFICATION

In the domain of large-scale multiclass classification we have following contributions:

1. First, we propose an algorithm to reduce multiclass classification problem to an equivalent binary classification problem. The reduced binary problem consists of similar number of positive and negative instances. Hence, it overcomes the class imbalance problem inherent in multiclass classification collection.

2. We further extend the algorithm, and introduce a double sampling strategy during training phase and an efficient candidate pre-selection approach during prediction phase. These modifications help to further improve the computational complexity of the model significantly. So, this makes the algorithm particularly attractive for extreme classification involving huge number of classes.

3. We derive generalization bounds for the proposed algorithm using local fractional Rademacher complexity, taking into account the inter-dependency between examples in the binary reduced dataset.

4. We empirically validate the effectiveness of the proposed algorithms in large text classification collections taking into account upto 100,000 categories.

DISTRIBUTED COMPUTING

In this front, we have following contributions:

1. We present a totally asynchronous distributed framework for distributed com- More precisely, problems where an example can belong to more than one classes, are referred as multilabel multiclass classification or often as multilabel classification.

Whereas, the simplest case of problems where each example belongs to only one class from a finite set of classes, are known as monolabel multiclass classification or commonly as multiclass classification. Throughout this part, we will consider the case of monolabel multiclass classification and we will use the term multiclass classification to denote it.

Multiclass classification is a popular area of research in ML. Some of the popular examples of multiclass classification are text classification [START_REF] Joshi | Aggressive sampling for multi-class to binary reduction with applications to text classification[END_REF][START_REF] Joshi | On binary reduction of large-scale multiclass classification problems[END_REF], Yen et al., 2016], image categorization [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF], Perronnin et al., 2010, Cinbis et al., 2012], face recognition [START_REF] Guo | Ms-celeb-1m: A dataset and benchmark for large-scale face recognition[END_REF], Parkhi et al., 2015] and video annotation [START_REF]Youtube-8m: A large-scale video classification benchmark[END_REF],Vondrick et al., 2013]. With the explosion in generation of data from different sources, modern multiclass classification problems involve very large size of datasets as well as very large number of classes and size of feature vectors. For example: in the case of text classification (as in LSHTC 1 and BioASQ2 challenges) and image classification [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF] the number of classes and size of feature space can be several thousands or even upto the order of millions. This increasing size of multiclass classification problems causes serious problems to the traditional multiclass classification approaches. We will explore those challenges in more detail in upcoming sections.

RELATED WORK

Large-scale multiclass classification, which has evolved as a popular branch of machine learning, considers problems involving extremely large number of classes. Hence it is also referred as extreme classification. A number of prior works have addressed different aspects of this problem, which we are going to review in this section. Different approaches of multiclass classification can be categorized in the following categories.

EXTENSIBLE ALGORITHMS

Multiclass classification problem can be solved by extending the popular binary classification algorithms such as SVM, neural networks, decision trees, k-nearest neighbors, Naive Bayes etc [Aly, 2005].

• Neural Networks: Multilayer Feedforward Neural Networks can be naturally extended to handle multiclass scenario by using K output binary neurons for each of the class in multiclass setting. Different ways of choosing output codewords are proposed [START_REF] Dietterich | Solving multiclass learning problems via error-correcting output codes[END_REF] This algorithm can be naturally extended to multiclass scenario by considering K leafs corresponding to each class label.

• Support Vector Machines (SVM): SVM's are considered as one of the most popular and robust algorithms in ML. The main idea of algorithm lies in maximizing the margin of the separating hyperplane. In normal setting, they are devised to handle binary classification. However, many extensions [START_REF] Allwein | Reducing multiclass to binary: A unifying approach for margin classifiers[END_REF],Dietterich and Bakiri, 1995, Friedman, 1996, Hsu and Lin, 2002] have been proposed to adapt it to handle multiclass scenario. In these extensions, the optimization problem is modified with additional parameters or constraints.

The extensible algorithms do not scale well to handle large-scale problems. In most of the cases, the complexity of algorithm becomes intractable. Because of these limitations, they are rarely used for extreme classification.

TRANSFORMATION TO BINARY (BINARIZATION)

Many research work have been proposed in last years for binary clasification, such as margin based classifiers, decision trees and ensembles [Bishop, 2006]. Some of the techniques can be naturally extended to handle multiclass problems (e.g. decision trees). Whereas other powerful and popular techniques, for e.g. Support Vector

Machines (SVM) [START_REF] Cortes | Support-vector networks[END_REF] cannot be easily adapted to multiclass scenario. So, it is a common practice to decompose the multiclass problem to simple binary classification problems, the process is commonly referred to as binarization [START_REF] Rocha | Multiclass from binary: Expanding one-versus-all, one-versus-one and ecoc-based approaches[END_REF]. Binarization involves mapping one multiclass problem into several binary problems (divide and conquer), solve the individual problems using traditional binary learners (base learners) and finally combine their individual outcomes to derive multiclass prediction [START_REF] Garcia-Pedrajas | Improving multiclass pattern recognition by the combination of two strategies[END_REF]. Broadly these approaches can be classified to three main categories: Ove-Vs-One(OVO), One-Vs-All (OVA) and Error Correcting Output Codes (ECOC).

In OVO, a binary problem is created for each pair of classes of the initial problem.

So, this leads to K(K -1)/2 binary problems, and as many binary classifiers. Figure 2.1 depicts OVO approach with separating hyperplanes of individual SVM classifiers for three classes. The predicted class for a new instance is the one that receives majority In OVA [START_REF] Lorena | A review on the combination of binary classifiers in multiclass problems[END_REF]] K binary problems are created, in each of them one class is seen as the positive class and the others as negative class. Given real-valued predictors g 1 , . . . , g K , the predicted class for an instance x is given by arg max y g y (x)

i.e. the class with highest score by the predictor. This approach is shown in Figure 2.2. This approach has a long history, where the early work dates back to [START_REF] Schiolkopf | Extracting support data for a given task[END_REF]. However, in the popular work of [START_REF] Rifkin | In defense of one-vs-all classification[END_REF], this approach was further revived and their empirical results showed its superiority over OVO, ECOC and M-SVM approaches. Later [Fan et al., 2008a] provided an easy and scalable implementation of the algorithm in their Liblinear package, which is widely used for experiments. The complexity of OVA is O(K X d), where K and d are number of classes and feature dimension respectively. Even though this complexity is better as compared to OVO, it is still high for extreme classification setting. Additionally, this approach is highly affected by class imbalance problem inherent in extreme classification.

In the ECOC-based approach [START_REF] Dietterich | Solving multiclass learning problems via error-correcting output codes[END_REF], each of the L classes are represented with a binary code c k , also known as the codeword. This gives rise have recently been proposed: for example, only a subset of the classifiers may be used at inference time without loss of accuracy [START_REF] Park | Efficient prediction algorithms for binary decomposition techniques[END_REF]; in another direction, a Naive Bayes approach that only requires a single pass over the data for training has proved effective [START_REF] Park | Efficient implementation of class-based decomposition schemes for naïve bayes[END_REF]. However, the key challenge for these methods is to accurately choose the coding matrix.

Usually, a class binarization task involves creating, learning and combining several binary base learners. So, in large-scale setting standard binarization approaches such

EMBEDDING BASED APPROACHES

Extreme multiclass/multilabel problems often involve learning with training examples, features and labels upto the order of millions. Hence, a natural way to handle such large number of class labels is to project the label vectors into a low dimensional space, with the assumption that the label matrix is low-rank. Different embedding based approaches mostly differ in the way the label matrix is compressed to low-rank and then decompressed back to original space. Different compression and decompression techniques are employed such as compressed sensing [START_REF] Hsu | Multilabel prediction via compressed sensing[END_REF], Kapoor et al., 2012], Bloom Filters [START_REF] Cisse | Robust bloom filters for large multilabel classification tasks[END_REF], SVD [START_REF] Tai | Multilabel classification with principal label space transformation[END_REF], output codes [START_REF] Zhang | Multi-label output codes using canonical correlation analysis[END_REF] etc. One state-of-art method LEML [Yu et al., 2014a] uses the Empirical Risk Minimization (ERM) framework while using a regularized least-square objective. In another recently proposed method SLEEC (Sparse Local Embedding for Extreme Classification) [START_REF] Bhatia | Sparse local embeddings for extreme multi-label classification[END_REF], the data is first clustered into smaller regions. It then performs local embeddings of label vectors using K-nearest neighbour classifier. The main advantages of embedding based methods include their simplicity, ease of implementation, strong theoretical foundations, ability to handle label correlations (for multilabel scenario) and their ability to be extended in online or incremental scenarios [START_REF] Bhatia | Sparse local embeddings for extreme multi-label classification[END_REF]. Moreover, their use has been extended beyond classification, and been successfully used in ranking problems as demonstrated in WSABIE system [Weston et al., 2011a]. Hence, they are quite popular approach especially for extreme multilabel classification [START_REF] Hsu | Multilabel prediction via compressed sensing[END_REF], Tai and Lin, 2012, Balasubramanian and Lebanon, 2012, Bi and Kwok, 2013, Chen and Lin, 2012,Ferng and Lin, 2011]. However, the main downside of these approaches include their slow training and prediction times even with the use of considerably low embedding dimension. Also, the critical assumption that the training matrix is low rank, is violated in almost all real world applications. Hence, these approaches often suffer from lower accuracy in such applications.

TREE-BASED APPROACHES

Methods using tree-based classifiers have gained popularity in recent times. These methods rely on binary tree structures where each leaf corresponds to a class and inference is performed by traversing the tree from top to bottom, a binary classifier being used at each node to determine the child node to develop. These methods have logarithmic time complexity. In an earlier work, FilterTree [Beygelzimer et al., 2009b] presents a robust tree-based method for multiclass classification. However, the problem with this approach was the choice of partition. In most cases, the success of this method was related with choice of partition. Partition finding problem was also addressed in conditional probability tree [Beygelzimer et al., 2009a], however the use of conditional probability violates the logarithmic time operation. Later, [START_REF] Bengio | Label embedding trees for large multi-class tasks[END_REF] used recursive spectral clustering on a confusion graph to address the partitioning problem. However, this makes the problem O(k) or even worse during training, making it intractable in extreme classification scenario. In another work, [START_REF] Weston | Label partitioning for sublinear ranking[END_REF] used k-means hierarchial clustering to recover partition of the label sets, focusing their work primarily for multilabel rather than multiclass problems. [START_REF] Choromanska | Extreme multi class classification[END_REF] proposed an efficient method for extreme multiclass classification, using decision trees with an online learning algorithm. FastXML [START_REF] Prabhu | Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning[END_REF] is another popular method useful for both multiclass and multilabel scenario which optimizes an nDCG based ranking loss function. This method employs the partitioning of feature space instead of the label space using the observation that only small number of labels are active in each region of feature space. An extension of this method is proposed as PfastReXML [START_REF] Jain | Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications[END_REF], which uses propensity scores to improve on tail label prediction. Also, another algorithm Log-time Log-space (LTLS) [START_REF] Jasinska | Log-time and log-space extreme classification[END_REF] claims to perform extreme classification in logarithmic time and space by embedding large classification problems into simple prediction problems and using dynamic programming for inference. Their empirical results show significant improvement in time and space usage. However their poor classification accuracy, especially for large-class cases is not justified. Another notable work using decision trees is Recall Tree [START_REF] Daume | Logarithmic time one-against-some[END_REF], which uses a binary tree to map an example to an small subset of candidate labels and uses a more tractable one-against-all classifier for prediction.

The main advantage of using the tree-based methods is to make the training, and/or prediction time logarithmic in number of classes, hence making it more attactive for extreme classification. However, its still a challenging task to find a balanced tree structure which can partition the class labels. Even though the above-mentioned methods have proposed several heuristics to address this problem and are able to reduce the complexity of the model to logarithmic time, empirically they do not show good predictive performance especially in large-class scenario. This is mainly caused by the fact that the prediction error made at the top the tree structure cannot be corrected at lower levels, also known as the cascading effect.

MISCELLANEOUS

In the proposed method also, we design joint features between classes and examples allowing to learn a single parameter vector for the whole problem. Another similar piece of work in [START_REF]Wsabie: Scaling up to large vocabulary image annotation[END_REF] learns representation for each classes. This approach learns a projection of examples and classes into a low dimensional space, hence reducing both training and inference time. However, in contrast to our approach, this method learns one parameter vector per class, while we use joint features of classes and examples allowing to reduce the number of vector parameters to one. In another line of work, [Titsias, 2016] proposed an approximation for the softmax layer for calculating probabilities of multiclass classification. Specifically, the author proposes a new bound on the softmax which factorizes the calculations in a product and thus avoids to evaluate the normalization constant which can become intractable for very large number of classes. In the case of extreme multiclass classification a doubly stochastic approximation scheme is used, without providing any theoretical guarantees, where one randomly selects a number of candidate classes while performing gradient descent. In our proposed method we also introduce a double stochastic procedure as an unbiased empirical risk minimization of the original expected loss.

Another recent algorithm to address extreme classification is PD-sparse method [START_REF] Yen | Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification[END_REF], where authors use sparsity for high-dimensional datasets. However, sparsity is not guaranteed to generate small size models without hurting model accuracy. Similarly many words might be derivationally related words with similar meaning such as democracy, democratic and democratization. Both stemming and lemmatization are used to reduce such multiple derivationally related words to their base form. Stemming is a crude method that chops off the derivational affixes from words. Whereas lemmatization performs it in a more proper way by using the vocabulary and morphological analysis of words.

CHALLENGES IN MULTICLASS CLASSIFICATION

FEATURE REPRESENTATION:

After preprocessing, next step is to represent each text document with a set of features. Individual components of text document are the words. Hence, many feature representations are proposed to represent the words in the document. In this section, we will discuss two representations: Bag of words, which is the most popularly used representation in text applications and dyadic representation, which we will use in our proposed algorithms.

• Bag of Words (BOW) Representation: This model is also known as Vector Space Model (VSM) [START_REF] Raghavan | A critical analysis of vector space model for information retrieval[END_REF], Van Rijsbergen, 1979, Hu, 2011]. In this model, each document is represented as a vector of length same as the total distinct terms in the corpus, also known as the dictionary. Each distinct term present in a document is given a weight and represented as the document vector.

Hence, for each term in the dictionary not present in the document as given a weight as zero. There are many ways to assign the weights for each terms in the document. One simple way is to use the frequency of occurrence of each distinct term in the document as the feature value. It is also commonly known as Term Frequency (TF). Such representation can be used to assess the similarity between two document vectors. However, using raw term frequency suffers from a critical issue [START_REF] Manning | Introduction to information retrieval[END_REF] that it assumes each term to be equally important.

However, certain terms may be used too frequently in all the documents and hence are very less useful to discriminate between two documents. Hence, to mitigate the effect of these popularly occurring words, another representation is proposed which tries to scale down the frequency of the terms with document frequency (number of documents in the collection containing that term). This representation is known as Inverse Document Frequency (IDF) and is given as [START_REF] Manning | Introduction to information retrieval[END_REF]:

id f t = log N d f t
Where N is the total number of documents in the collection and d f t represents the document frequency for the term t. IDF of a rare term is high and frequently appearing terms is low. The most popular bag of words representation, known as tf-idf weighting, which is calculated as the multiplication of tf and idf values.

The tf-idf representation of a term t in a document d is given as:

tf-idf = t f t,d × id f t
So, the tf-idf t,d term assigned for each term in document d is [START_REF] Manning | Introduction to information retrieval[END_REF]:

1. highest when t occurs many times in a few documents.

2. lower when term occurs fewer times in a document; or occurs in many documents.

3. lowest when the term occurs in almost all the documents.

• Dyadic (or Joint) Representation: Another popular feature representation in information retrieval is the one commonly used in ranking of documents according to their relevance to a query. This field of research is known as learning to rank [Liu et al., 2009, Qin et al., 2010, Liu, 2011]. Here, the query-document pair is represented by a multi-dimensional feature vector. The small set of features try to encode the relevance of the document with respect to the query. For example one simple example of a feature can be the total number of terms present in both the query feature vector and the document vector. Similarly, a number of classical information retrieval features can be manufactures by considering this relevance. Moreover, this joint representation can be used to extract specialized similarity features such as BM25, LMIR [START_REF] Qin | Letor: A benchmark collection for research on learning to rank for information retrieval[END_REF]. All the documents belonging to one class can be considered as a single large document.

Hence, the query-document joint feature representation can be extended to the joint representation of a document and the collection of documents belonging to one class. In our work, we use this joint feature representation to classify documents to one of the classes. We have exchangeably used the terms joint or dyadic or similarity-based feature representation throughout this thesis to denote it. In the experiments section we will present the features we have used in the experiments.

EVALUATION MEASURES

The correctness of a classification task can be evaluated using four aspects: examples which are predicted as positive and the true class is also positive (true positives), examples which are predicted as negative and the true class is also negative (true negatives), examples predicted as positive however the true class is negative (false positives) and examples which are predicted to belong to negative class however the true class is positive (false negatives). All these attributes are summed up as a confusion matrix shown in Table 2.1.

We begin with presenting evaluation measure for a binary classification task. These can be extended for multiclass classification case as well. Some of the commonly used evaluation measures are summarized below:

1. Accuracy is measured as the fraction of predictions that are correct. Mathematically, it is represented as: where the class imbalance problem is inherent.

Accur ac y = T P + T N T P + T N + F P + F N

Measure Formula Description

Average Accuracy

l i=1 t p i +t n i t p i + f n i + f p i +t n i l Measures per-class effectiveness of a classifier Error Rate l i=1 f p i + f n i t p i + f n i + f p i +t n i l Measures per-class classification error P r ecision µ l i=1 t p i l i=1 (t p i + f p i )
Agreement of the data class labels with those of a classifier if calculated from sums of per-text decisions

Recall µ l i=1 t p i l i=1 (t p i + f n i )
y i i ) m
i=1 is made of i.i.d pairs distributed according to a fixed but unknown probability distribution , and we consider a class of functions = {g :

× → } as our predictors. We define the instantaneous loss of g ∈ on an example x y as:

e(g, x y ) = 1 K -1 y ∈ \{ y} 1 g(x y )≤g(x y ) , (3.1)
where 1 π is the indicator function that is equal to 1 if the predicate π is true and 0 otherwise. Compared to the classical multiclass error:

e (g, x y ) = 1 y =argmax y ∈ g(x y ) , (3.2)
the loss of (3.1) estimates the average number of classes, given any input data, that get a greater scoring by g than the correct class. The loss (3.1) is hence a ranking criterion, and the multiclass SVM of [START_REF] Weston | Multi-class support vector machines[END_REF]] and AdaBoost.MR [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF] optimize convex surrogate functions of this loss. The multiclass classification problem we are going to study is that of finding a function g ∈ using the labeled training set with small generalization error L(g):

L(g) = x y ∼ [e(g, x y )] . (3.3)
Accordingly, the empirical error of g ∈ over is

Lm (g, ) = 1 m m i=1 e(g, x y i i ) (3.4a) = 1 m(K -1) m i=1 y ∈ \{ y i } 1 g(x y i )≤g(x y i ) (3.4b)
We further work out the empirical loss of Equation (3.4) in order to i) have it ressemble a more usual binary classification loss with, in particular, a single sum running over only one index, ii) make apparent the need of dealing with non-i.i.d. random variables and iii) after a theoretical introduction, set the stage for our practical binary reduction approach.

A first step to reshape the empirical loss is to see that the instantaneous loss (3.1) can be rewritten as

e(g, x y ) = 1 K -1 y ∈ \{ y} 1 ỹh(x y ,x y )≤0 ,
where h is defined as h(x y , x y ) = g(x y ) -g(x y ). This bears strong resemblance with a binary-classification-loss-based risk, a resemblance that can be strengthened by introducing the transformed set T ( ) of size n = m(K -1) defined as

T ( ) = Z j , ỹj : j = 1, . . . , n , (3.5)
where each Z j is one of the pairs (x y i , x y i ), and ỹj = 1 if the first observation in Z j is constituted by an example x i and its true class in (i.e. y = y i ) and the second observation is constituted by the same example and any other of the K -1 classes; and ỹj = -1 otherwise (i.e. if the order is reverse). This allows us to rewrite the empirical loss of (3.4b) as:

L T n (h, T ( )) = 1 n n j=1 1 ỹj h(Z j )≤0 . (3.6)
With these definitions at hand, it is clear that the selection of a hypothesis in minimizing the empirical risk of (3.4) over the training set , is equivalent to the search of a hypothesis in = {h : h(x y , x y ) = g(x y ) -g(x y ), g ∈ } minimizing the empirical risk of (3.6) over T ( ). However, even if the examples in are i.i.d.,

the examples in T ( ) are no longer independent since the same observations x y ∈ are involved in different pairs of T ( ). Thus, in order to obtain generalization error bounds L T n (h, T ( )) we need to address the issue of learning with interdependent data. We will discuss this issue in detail in next sections.

MULTICLASS TO BINARY REDUCTION

REDUCTION STRATEGY

In section 3.1 , we derived an equivalence of multiclass classification problem to a binary problem. Hence, if we can represent each example of our dataset as dyadic pairs of (x, y i ) for all i ∈ K, then based on that equivalence shown in Equation 3.6 we can transform the multiclass dataset to binary. Figure 3.1, depicts this transformation over a toy problem. More precisely, we consider the following transformation:

T ( ) = Z j = x k i , x y i i , ỹj = -1 if k < y i Z j = x y i i , x k i , ỹj = +1 elsewhere j . =(i-1)(K-1)+k , (3.7) for j = (i -1)(K -1) + k with i ∈ [m], k ∈ [K -1], thus T transforms a monolabel K class classification set of m feature/label pairs into a set T ( ) of size N = m(K -1).
We consider the following class of functions

= {h : ( × ) 2 → ; h(x y , x y ) = g(x y ) -g(x y ), g ∈ , (3.8)
Here, one thing to note is that the label assignment in Equation 3.7 is done based on the new hypothesis function learned over the subtraction of dyadic representations as represented in 3.8. Hence, if the first representation in the subtraction pair corresponds to the true label, then the subtraction should be positive making the binary label as +1 and vice versa.

REDUCTION EXAMPLE

LOW-DIMENSIONAL FEATURE MAP

In multiclass classification, the output space is unstructured and the algorithms using the "trivial" feature map need a single parameter vector for each class. So, the parameter for such problems is in fact the concatenation of one parameter vector per class.

However, our reduction technique relies on the dyadic (joint) representation of x y of example and classes. This allows us to make use of a non-trivial feature representation φ(x y ) by using a small number of adequately chosen similarity features between examples and classes. Typical low-dimensional features for text classification can be common terms between example and all examples in a class, similarity features etc (see Section 3.3.3.2). This joint feature space is independent of the number of classes and hence remains same for any number of classes. So, learning can be achieved by combining these features, using same parameter vector for all the classes. The use of such low-dimensional feature representation has a huge benefit in terms of memory usage. We will demonstrate this fact further in the Experiments section later.

NAIVE REDUCTION ALGORITHM (mRb)

ALGORITHM DESCRIPTION

Now, using the reduction strategy introduced in previous section, we present our first classification algorithm based on the reduction of multiclass to binary.

Reduction Phase

The first step of the classification algorithm is the binary reduction phase introduced in 3.2.1. Algorithm 1 outlines the reduction phase of the proposed algorithm. We use a low-dimensional dyadic feature representation rather than using the original feature space as suggested in 3.2.3. The dyadic representation consists of a small number of adequately chosen features. The output of the reduction phase is a binary transformed dataset.

Input:

Labeled training set = (x

y i i ) m i=1 Initialize T ( ) ← for i = 1..m do for k = 1..K do if k < y i then T ( ) ← T ( ) ∪ Z = φ(x k ), φ(x y i ) , ỹ = -1 end else T ( ) ← T ( ) ∪ Z = φ(x y i ), φ(x k ) , ỹ = +1 end end end return T ( ) Algorithm 1:
Multi-class to Binary Reduction Phase

Learning Phase

Since the transformation gives us a binary dataset, we can now train a binary learner.

Some of the popularly used binary learners [Bishop, 2006] are Logistic Regression, SVM etc. The binary learner learns a weight vector, W. These learned weights can be used to classify the future unseen instances.

Prediction Phase

Now, after training the binary learner, we use the learned model to classify the test instances. However, its not very trivial in our case, since the model is learned over binary dataset and the test instances are multiclass. So, the procedure we follow during prediction phase is depicted in Algorithm 2. For each test example, x', we make a dyadic representation with respect to all the class labels in , and the one with the highest dot product with the weight vector is assigned as the predicted class for the test example.

Input: Unlabeled test set = (x i ) T i=1
Learned feature weight vector W Initialize:

P ← forall x ∈ do P ← P ∪ argmax k∈ 〈W, φ(x k )〉
end return predicted classes P Algorithm 2: Prediction with Binary Learned Model

GENERALIZATION BOUND ANALYSIS USING FRACTIONAL RADEMACHER COMPLEXITY

With these definitions at hand, it is clear that the selection of a hypothesis in minimizing the empirical risk of (3.4) over the training set , is equivalent to the search of a hypothesis in = {h : h(x y , x y ) = g(x y ) -g(x y ), g ∈ } minimizing the empirical risk of (3.6) over T ( ). However, even if the examples in are i.i.d., the examples in T ( ) are no longer independent since the same observations x y ∈ are involved in different pairs of T ( ). Thus, in order to obtain generalization error bounds L T n (h, T ( )) we need to address the issue of learning with interdependent data.

There exist several ways to tackle this problem among which two settings received particular attention in the literature. The first one deals with learning from mixing pro-cesses, where the dependency between random variables decreases over time [START_REF] Mohri | [END_REF]Rostamizadeh, 2009,Steinwart and[START_REF] Steinwart | [END_REF]. The second direction, on which the present work is based on, is developed around the idea of graph coloring that divides a graph, representing the relations between random variables, into sets of independent random variables called proper cover of the graph [Janson, 2004].

A proper cover of T ( ) is constituted of K -1 disjoint sets (C k ) K-1
k=1 each containing m independent examples. For all k ∈ {1, . . . , K -1} it is defined as

C k = {(Z k+ j(K-1) , ỹk+j(K-1) ); j ∈ {0, . . . , m -1}} Moreover, (C k , α k ) K-1 k=1 is said to be a proper exact fractional cover of T ( ), if (C k ) K-1 k=1 is a proper cover of T ( ) and if ∀k, α k > 0 and ∀i ∈ {1, . . . , n}, k=1 α k 1 (Z i , ỹi )∈C k = 1. S T (S) (C 1 , ↵ 1 = 1) (C 2 , ↵ 2 = 1) x 1 1 x 2 2 x 3 3 (x 1 1 , x 2 1 ) (x 1 1 , x 3 1 ) (x 2 2 , x 3 2 ) (x 2 2 , x 1 2 ) (x 3 3 , x 1 3 ) (x 3 3 , x 2 3 ) (x 1 1 , x 2 1 ) (x 2 2 , x 1 2 ) (x 3 3 , x 1 3 ) (x 1 1 , x 3 1 ) (x 2 2 , x 3 2 ) (x 3 3 , x 2 3 )
χ * T = 2.
The fractional chromatic number of T , denoted as χ * T is then the minimum sum of weights, or the minimum number of sets containing each independent random variables, which for the proposed transformation is equal to K -1. Figure 3.2 depicts the transformation and its associated proper exact fractional on a toy problem.

Using graph coloring arguments, [Janson, 2004] extended Hoeffding's inequality to sums of interdependent random variables and based on that result, different studies proposed new generalization error bounds for learning with interdependent data, thus proving the consistency of the ERM principle for this case [START_REF] Usunier | Generalization error bounds for classifiers trained with interdependent data[END_REF],Ralaivola et al., 2010]. Here we build on [START_REF] Usunier | Generalization error bounds for classifiers trained with interdependent data[END_REF] who proposed a generalization of [McDiarmid, 1989] concentration inequality to the case of interdependent random variables.

Our theoretical result is the following theorem which provides data-dependent bound on the generalization error of the multiclass classifier (Eq. 3.3). This result is at the basis of the algorithm for the binary classification of pairs of examples that we expose in the next section. We consider here kernel-based hypotheses with κ : → a positive semidefinite (PSD) kernel and φ : × → its associated feature mapping function, defined as:

B = {x y ∈ × → 〈w , φ(x y )〉 | ||w || ≤ B} (3.9)
where w is the weight vector defining the kernel-based hypotheses and 〈•, •〉 denotes the dot product. We further define the following associated function class: Further let κ : → be a PDS kernel, and let φ : × → be the associated feature mapping function. Then for all 1 > δ > 0 with probability at least (1 -δ) over T ( ) the following generalization bound holds for all h w ∈ B :

B = {(x y , x y ) ∈ → g w (x y ) -g w (x y ) | g w ∈ B }.
L T (h w ) ≤ ε T n (h w , T ( )) + 2BG(T ( )) m K -1 + 3 ln( 2 δ ) 2m (3.10) where ε T n (h, T ( )) = 1 n n i=1 ( ỹi h w (Z i )) with the surrogate Hinge loss : t → min(1, max(1- t, 0)), L T (h w ) = T ( ) [L T n (h w , T ( ))] and G(T ( )) = n i=1 d κ (Z i ) with d κ (x y , x y ) = κ(x y , x y ) + κ(x y , x y ) -2κ(x y , x y )
Proof. Exploiting the fact that dominates the 0/1 loss and using the fractional Rademacher data-dependent generalization bound proposed for interdependent data in Theorem 4 of [START_REF] Usunier | Generalization error bounds for classifiers trained with interdependent data[END_REF] one has

L T (h w )≤ε T (h w ) ≤ εT n (h w , T ( ))+ ˆ T n ( • B , )+3 χ * T ln( 2 δ ) 2n Where ε T (h w ) = T ( ) [ εT n (h w , T ( ))] and ˆ T n ( • B , ) is the empirical fractional Rademacher complexity of • B on T ( ). Further, as is 1-Lipschitz, so ˆ T n ( • B , ) ≤ ˆ T n ( B , )
where

ˆ T n ( B , )= K-1 k=1 2α k M σ sup h∈ B m-1 j=0 σ j h w (Z k+ j(K-1) )
Now, for all k ∈{1, .., K-1} and j ∈{0, .., m-1}, let z k j and z k j be the first and the second pair of Z k+ j(K-1) , then from the bilinearity of dot product and the Cauchy-Schwartz

inequality, ˆ T n ( B , ) is upper-bounded by K-1 k=1 2α k n σ sup h w ∈ B w , m-1 j=0 σ j (φ(z k j ) -φ(z k j )) ≤ K-1 k=1 2Bα k n σ m-1 j=0 σ j (φ(z k j ) -φ(z k j ))
Further, for all i, j ∈ {0, . . . , m -1} 2 , i = j, we have σ [σ i σ j ] = 0 so

ˆ T n ( B , ) ≤ K-1 k=1 2Bα k n m-1 j=0 d κ (z k j , z k j ) = 2Bχ * T n K-1 k=1 α k χ * T m-1 j=0 d κ (z k j , z k j ) Now as K-1 k=1 α k χ * T = 1 and that t → t is concave, from Jensen inequality we have ˆ T m ( B , ) ≤ 2Bχ * T n K-1 k=1 α k χ * T m-1 j=0 d κ (z k j , z k j )
The result follows from rearranging the examples and the equalities χ * T = K -1, and n = (K -1)m.

PRELIMINARY EXPERIMENTS WITH mRb

To validate the proposed classification algorithm based on the reduction of multiclass problem to binary, we conducted a series of experiments on text classification.

Dataset

We evaluate the proposed method for multi-class classification in a large-scale scenario using DMOZ and Wikipedia datasets of the Large Scale Hierarchical Text Classification challenge (LSHTC 2011) [START_REF] Partalas | LSHTC: A Benchmark for Large-Scale Text Classification[END_REF]. These datasets contain 27875 and 36504 categories respectively for DMOZ and Wikipedia and they are provided in a pre-processed format using stop-word removal and stemming. The dimension of the vectorial space (d), the size of the training set (m) and the test set are respectively 594158 , 394756 and 104263 for DMOZ and 346299 , 456886 and 81262 for Wikipedia. For each of these datasets we randomly draw several samples with increasing number of classes: 100, 500, 1000, 2000, 3000, 4000, 5000, 7500 and by keeping the same proportion of examples in the training and the test sets than in the initial collections. Various characteristics of these subsets of the two original datesets are listed in Table 3 For the feature mapping, we used the following features in the vector representation of φ(x y ) (Table 3.2) by considering a class y as a mega-document, constituted by the concatenation of all of the documents in the training set belonging to it. The first 8 features are classical ones employed in learning to rank [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF] by resembling class and a document to respectively a document and a query. The last two features represent the distance of an example x to its two nearest neighbors in class y.

Features in the vector representation of φ(x y ).

1.

t∈ x to its two nearest neighbours in class y.

Baselines:

To assess the performance of the proposed algorithm, we perform a comparison of the popular state-of-the-art approaches for multiclass classification. We specifically compared the following methods:

• mRb: The proposed multiclass to binary reduction approach.

• OVA: The Liblinear [Fan et al., 2008b] implementaion of One-Vs-All SVM.

• OVO: The Liblinear implementation of One-Vs-One.

• M-SVM: The Liblinear implementation of Multiclass SVM (Crammer-Singer algorithm [START_REF] Crammer | On the algorithmic implementation of multiclass kernel-based vector machines[END_REF]).

• Log T : Vowpal-Wabbit (a public fast learning system proposed by [START_REF] Choromanska | Logarithmic time online multiclass prediction[END_REF] for extreme multiclass classification). We use their logtree solver for our comparison.

Experimental Settings:

• Platform: In all of our experiments, we used a server with an intel Xenon 1.8HGz processor and 16GB of RAM.

• Parameters: For OVA and M-SVM, we need to choose appropriate value of C parameter. In our experiments, we perform a grid search in the following range of values {10 -2 , 10 -1 , 10 0 , 10 1 , 10 2 }, and use the one that leads to the best performance on the validation set.

• Evaluation Measures: Results are evaluated over the test set first using the accuracy. As we have discussed in previous section, one of the prominent challenges for large-scale multiclass classification is class imbalance problem. When the dataset exhibits such behaviour accuracy cannot be considered as a good measure for evaluation. Hence, we also use macro F 1 -Measure (we will denote it as MaF 1 ) as another measure for evaluation , which is the harmonic average of macro precision and macro recall (see section 2.4.3). We start our evaluation by analyzing the performance measures of different approaches on the setting with the largest number of classes we considered in our experiments (K = 7500). Table 3.3 summarizes results obtained by mRb, OVA and LogT, as the corresponding training processes of M-SVM and OVO were killed by the system and did not pass the scale. Results are averaged over 50 random splits of tests sets.

Evaluation on the largest data part

We use bold face to indicate the highest performance rates, and the symbol ↓ indicates that performance is significantly worse than the best result, according to a Wilcoxon rank sum test used at a p-value threshold of 0.01 [Lehmann, 1975]. The competitive methods are OVA and mRb with a discrepancy over their accuracy and MaF 1 measures on both collections. To analyze this divergence we estimated the proportion of classes that have been covered, or for which at least one true positive document was found. It comes out that mRb covers 6% to 12% more classes than OVA (that is 465 to 900 more classes on both datasets). The reason here is that OVA is affected by the class imbalance problem especially in the extreme case where classes contain very few documents. For the large scale scenario this problem is accentuated as the class distribution is longtailed, as for example in DMOZ-7500, more than half of the classes contain less than 5 documents (Figure 2.5).

Evaluation on all subsets

We also show the comparison of various baselines on data subsets with increasing number of classes. We analyzed their performance in terms of MaF 1 values.

As expected all performance curves decrease monotonically with respect to an increasing number of classes. The breaking points beyond which OVO and M-SVM cannot be trained, happen at the same time on both collections for respectively K = 500 and K = 3000 classes. The performance of mRb are in between of those of OVA and M-SVM before the breaking point, with a slight advantage for M-SVM, while mRb uniformly outperforms OVA with a larger gap on Wikipedia. We notice that on this collection, mRb achieves for 7500 classes MaF 1 score comparable to the OVA's one for 5000 classes.

Comparatively, for K = 3000, the numbers of parameters of these two models are roughly 5.4 × 10 8 to 6.5 × 10 8 on respectively Wikipedia and DMOZ collections which are O(10 7 ). However, since we adopt a low-dimensional feature representation, we have a very small parameter size O( 10). This low-dimensional representation significantly reduces the complexity of the model, especially for cases with higher number of classes.

Evaluation of training time

Another performance comparison we performed was the total training time for all the algorithms. The use of low-dimensional joint feature representation helped to reduce the feature dimension significantly. As we already mentioned, the feature dimension in text classification problem can be very huge (up to the order of millions). Hence, the use of dyadic features helped us to restrict this huge feature dimension to as small as just 10 features. This contributes to significantly lower memory requirements as compared to most of baseline approaches such as OVA, OVO and M-SVM.

However, there are a some new challenges associated with the proposed approach.

Even though the proposed method scales well enough for large-scale cases, it still has fairly large computational cost and memory usage. Let us discuss this with respect to both phases of the algorithm:

• • Testing Phase: During the testing phase, for each test example x we first perform K transformations and then calculate the dot product of the learned weight W with each joint representations (x , y i ) for i ∈ K. This again causes large computational cost.

Hence in order to overcome the above-mentioned challenges of mRb algorithm, we proposed a modified version of the algorithm denoted as DS-mRb, which improves over each of the challenges mentioned above. In the next section, we will discuss the proposed algorithm in detail and in the later sections we will discuss its theoretical and empirical properties. and (ii) an efficient prediction method with candidate pre-selection.

Aggressive Double Sampling

Earlier we discussed that the transformation of Multi-class to binary, T introduced in Section 3.3 can lead to a large computational overhead. In order to improve the memory/computational complexity, we practice a µ, κ-double subsampling on T ( ) by: Still, in cases where the number of classes K becomes large, the initialization of (subsampled) set T ( µ ) can be a computational bottleneck. However, thanks to our loss formulation (Eq. 3.1), its size can be sensibly reduced. Indeed, e(g, x y ) can be seen as the expectation of 1 g(x y )≤g(x y ) on y uniformly over \{ y}:

Input: Labeled training set = (x y i i ) m i=1 initialization: π ← ; T κ ( π ) ← ; for k = 1..K do Draw randomly a set π k of examples of class k from with probability π k ; π ← π ∪ π k ; end forall x y ∈ π do Draw uniformly a set x y of κ classes from \{ y} κ K; forall k ∈ x y do if k < y then T κ ( π ) ← T κ ( π ) ∪ Z = φ(x k ), φ(x y ) , ỹ = -1 ; end else T κ ( π ) ← T κ ( π ) ∪ Z = φ(x y ), φ(x k ) , ỹ = +1 ; end end end return T κ ( π ) Algorithm 3: DS-mRb e(g, x y ) = 1 K -1 y ∈ \{ y} 1 g(x y )≤g(x y ) ≈ y [1 g(x y )≤g(x y ) ].
It means that one can define a new empirical loss by sampling over the classes. Let κ ≤ K -1 be the number of classes to investigate per example. For each example x y , draw uniformly a κ-tuple of distinct elements of \{ y}. The new subsampled loss over µ = (x

y i i ) i=1,..,µK is: Lµ,κ (g, ) = 1 µK µK i=1 1 κ y ∈ x y 1 g(x y i i )≤g(x y i ) .
( 3.11) This loss is an unbiased estimator of the normalized loss L(g) = x y ∼ [e(g, x y )] =

x y ∼ y [1 g(x y )≤g(x y ) | y = y]
where is the distribution of the examples after class normalization. Thus, this new loss enables to approximate the statistical loss L at a much lower computational cost than the classical emprical loss. Finally, one can notice that such reasoning does not hold for the classical loss of Eq. 3.2 due to its non-linear formulation.

Prediction with Candidate Selection

After learning over our reduced problem using the T κ ( µ ) dataset obtained after aggressive sampling, we obtain a vector w such that, for an observation x, the larger 〈w, φ(x y )〉 over y is, the more likely x belongs to class y.

However in the large class scenario, computing the feature representation for all classes may require a huge amount of time. So, in order to improve the prediction time, we apply the trick of selecting a small subset of candidate classes beforehand. variance) information inducing faster convergence rates (Theorem 3.2). Our analysis relies on the notion of graph covering introduced in [Janson, 2004] and defined as :

Definition 3.1 (Exact proper fractional cover of , [Janson, 2004]). Let = ( , ) be

a graph. = {( k , ω k )} k∈[J] ,
for some positive integer J, with k ⊆ and

ω k ∈ [0, 1]
is an exact proper fractional cover of , if:

1. it is proper: ∀k, k is an independent set, i.e., there is no connections between vertices in k ;

2. it is an exact fractional cover of G: ∀v ∈ , k:

v∈ k ω k = 1.
The weight W ( ) of is given by: W ( ) . From this statement, [Janson, 2004] extended Hoeffding's inequality and proposed large deviation bounds for sums of dependent random variables which was the precursor of new generalisation bounds, including a Talagrand's type inequality for empirical processes in the dependent case presented in [START_REF] Ralaivola | Entropy-based concentration inequalities for dependent variables[END_REF].

With the classes of functions and introduced previously, consider the parameterized family r which, for r > 0, is defined as:

r = {h : h ∈ , [h] . = Z, ỹ [1 ỹh(Z) ] ≤ r},
where denotes the variance. The fractional Rademacher complexity introduced in [START_REF] Usunier | Generalization error bounds for classifiers trained with interdependent data[END_REF] entails our analysis :

R T ( ) ( ) . = 2 N ξ k∈[K-1] ω k k sup h∈ α∈ k Z α ∈T ( ) ξ α h(Z α ), with (ξ i ) N i=1 a sequence of independent Rademacher variables verifying (ξ n =1) = (ξ n =-1) = 1
2 . If other is not specified explicitly we assume below all ω k = 1. Our first result that bounds the generalization error of a function h

∈ ; R(h) = T ( ) [ RT( ) (h)],
R(h) ≤ RT( ) (h) + R T ( ) ( • r ) + 5 2 R T ( ) ( • r ) + r 2 log 1 δ m + 25 48 log 1 δ m . Lemma 1. Fractional chromatic number is monotone in graph inclusion: if = 〈 , 〉 ⊆ = 〈 , 〉 implies ⊆ and ⊆ we have χ * ( ) ≤ χ * ( ).
Proof. Consider any exact proper fractional cover [Janson, 2004] of graph , = {( k , ω k )} k∈J for some index set J. By removing from each k vertices that belong to \ and incident edges we get a cover = {( k , ω k )} k∈J of graph . Once for a certain k holds k = ∅ we remove it from which is essentially the same as

assignment ω k . = 0.
The cover is a proper fractional cover of since the number of connections between vertices in k is a subset of those in k for any k ∈ J. The cover is also exact (modulo empty sets in ) since for any v :

v ∈ ∩ : k:v∈ k ω k = k:v∈ k ω k = 1,
where = {( k , ω k )} k∈J is an exact proper fractional cover of graph . That implies that each exact proper fractional cover of graph can be converted to an exact proper fractional cover of graph without increasing the covering cost

W ( ) . = k ∈ ω k ≤ W ( ).
Denote the set of all exact proper fractional coverings of graph as ( ) and coverings obtained by pruning ( ) as above through

( ).
By the definition of fractional chromatic number we have

χ * ( )= min ∈ ( ) W ( ) (1)
≤ min

∈ ( ) W ( ) ≤ χ * ( ),
where

is implied by inclusion ( ) ⊆ ( ).

Lemma 2 (Empirical Bennet inequality, theorem 4 of [START_REF] Maurer | Empirical bernstein bounds and sample variance penalization[END_REF]). Let Z 1 , Z 2 , . . . , Z n be i.i.d. variables with values in [0, 1] and let δ > 0. Then with probability

at least 1 -δ in Z = (Z 1 , Z 2 , . . . , Z n ) we have [Z] - 1 n n i=1 Z i ≤ 2 n (Z) log 2/δ n + 7 log 2/δ 3(n -1) ,
where n (Z) is the sample variance

V n (Z) = 1 n(n -1) 1≤i< j≤n (Z i -Z j ) 2 .
Lemma 3 (Concentration of Fractionally Sub-Additive Functions, theorem 3 of [START_REF] Ralaivola | Entropy-based concentration inequalities for dependent variables[END_REF]). Let be a set of functions from to and assume all functions in are measurable, square-integrable and satisfy

[ f (X n )] = 0, ∀n ∈ [N ] and sup f ∈ f ∞ ≤ 1. Assume that = {( k , ω k )} k∈J is a cover of the dependency graph of X [N ] and let χ f . = k ω k .
Let us define: andc . = 25χ f /16. Then, for any t ≥ 0. Proof. First, decompose the expected risk R(h) as a sum of the conditional risks over the classes

Z . = k∈[J] ω k sup f ∈ n∈ k f (X n ) Let σ k be so that σ 2 k = n∈ k sup f ∈ f 2 (X n ) , v . = k ω k σ 2 k + 2 [Z],
Z ≥ [Z] + 2cv t + c t 3 ≤ e -t (
¯ = ¯ × | , ¯ [ y(x) = k] = π k /π, 1 ≤ i ≤ K,
R(h) = x y ∼ [e h (x y )] (1)
= y∼

x y ∼ | y(x)= y [e h (x y )| y(x) = y] (2) = K y=1 x y ∼ [ y(x) = y] • x y ∼ | y(x)= y [e h (x y )| y(x) = y] , (3.13)
where ( 1) and ( 2) are due to the law of total expectation.

Similarly consider the expected loss x y ∼ ¯ RT(x y ) (h) :

x y ∼ ¯ RT(x y ) (h) = x y ∼ ¯ [e h (x y )] (1) = y∼ ¯ x y ∼ | , y(x)= y [e h (x y )| y(x) = y] (2) = K y=1 x y ∼ ¯ [ y(x) = y] • x y ∼ | y(x)= y [e h (x y )| y(x) = y] = K y=1 π y π • x y ∼ | y(x)= y [e h (x y )| y(x) = y] , (3.14)
where ( 1) and ( 2) are also due to the law of total expectation.

From (3.13) and (3.14) we conclude

R(h) ≤ max y: 1≤ y≤K x y ∼ [ y(x) = y] π y /π • x y ∼ ¯ RT(x y ) (h) (3.15)
Finally, we need to bound the multiplier in front of x y ∼ ¯ RT κ ( π ) (h) in Eq. (3.15).

Denote through η y an empirical probability of the class y ∈ :

η y = 1 m x∈ 1 y(x)= y .
Note, that empirical variance n (η y ) in accordance with lemma 2 is

m (η y ) = η y (1 -η y )m (m -1)
For any y ∈ we have with probability at least 1 -δ/K by lemma 2 :

x y ∼ [ y(x) = y] ≤ η y + 2 m (η y ) log 2K/δ m + 7 log 2K/δ 3(m -1) (1)
=

η y + 2η y (1 -η y ) log 2K/δ m -1 + 7 log 2K/δ 3(m -1) (2)
≤

η y + 2η y log 2K/δ m -1 + 7 log 2K/δ 3(m -1) ,
where (1) is a substitution of m (η y ) by its explicit value;

(2) is due to the fact that 0 < η y ≤ 1.

Then simultaneously for all y ∈ we have with probability at least 1 -δ :

x y ∼ [ y(x) = y] ≤ η y + 2η y log 2K/δ m -1 + 7 log 2K/δ 3(m -1)
Thus with probability at least 1 -δ : From equations (3.15) and (3.16) and the fact that x y ∼ ¯ N RT(x y ) (h) ≤ 1, we have with probability at least 1 -δ :

max y: 1≤ y≤K x y ∼ [ y(x) = y] π y /π ≤ α + 2α log 2K/δ β(m -1) + 7β log 2K/δ 3(m -1) , ( 3
R(h) ≤ α x y ∼ ¯ RT(x y ) (h) + 2α log 2K/δ β(m -1) + 7β log 2K/δ 3(m -1) .
The results of the previous lemmas, hence entail the following lemma.

Lemma 5. Let = (x ), g ∈ }, consider the parameterized family r which, for r > 0, is defined as :

y i i ) m i=1 ∈ ( × ) m be
r = {h : h ∈ , [h] . = Z, ỹ [1 ỹh(Z) ] ≤ r},
where denotes the variance. Then for any δ > 0 and 0/1 loss :

{-1, +1}× → [0, 1],
with probability at least (1 -δ) the following generalization bound holds for all h ∈ r :

R(h) ≤ RT κ ( ) (h) + R T κ ( ) ( • r )+ 5 2 R T κ ( ) ( • r ) + r 2 (K -1) log 1/δ mκ + 25 48 log 1/δ m .
Proof. Consider the function Φ defined as:

Φ(X , r) . = N sup h∈ r X [ RT(X ) (h)] -RT(X ) (h) ,
where X is an i.i.d. copy of X and where we have used the notation X [ RT(X ) (h)]

for T ( ) RN (h, T ( )) to make explicit the dependence on the sequence of dependent variables X . It is easy to see that:

Φ(X , r) ≤ k∈[K-1] ω k sup h∈ r α∈ k ( ỹ ,Z ) [1 ỹ h(Z ) ] -1 ỹα h(Z α ) = Z.
(3.17) Lemma 3 readily applies to upper bound the right hand side of (3.17). Therefore, for t > 0, the following holds with probability at least 1 -e -t :

Φ(X , r) ≤ [Z] + 2cv t + c t 3 , where c = 25χ f /16 = 25(K -1)/16 and v ≤ N r + 2 [Z]. Using a + b ≤ a + b
and 2 ab ≤ ua + b/u for all u > 0, we get,

∀u > 0, Φ(X , r) ≤ (1 + u) [Z] + 2cN r t + 1 3 + 1 u c t.
Furthermore, with a simple symmetrization argument, we have,

[Z] =   k∈[K-1] ω k sup h∈ r α∈ k ỹ ,Z ) [1 ỹ h(Z ) ] -1 ỹα h(Z α )   ≤ N R( • r ),
with ω k = 1 for all k since the fractional chromatic number of the dependency graph corresponds to the sample T ( ) equals to K -1 and stands for the covering determined by Eq. ( 4) with unit weights ω k .

Further, as N = mκ, and fractional chromatic number of T κ ( ) ≤ T ( ) = K -1

(theorem 1 of [Joshi et al., 2015a]), with probability at least 1 -e -t , we have for all

h ∈ r R(h) -RT κ ( ) (h) ≤ inf u>0 (1 + u)R T κ ( ) ( • r ) + 5 4 2(K -1)r t mκ + 25 16 1 3 + 1 u (K -1)t κm . (3.18)
The minimum of the right hand side of the inequality (3.18) is reached for

u * = 5 4 (K-1)t κmR T κ ( ) ( • r )
, plugging back the minimizer and solving for δ = e -t gives the result.

Proof of the theorem 1. Theorem 1 of [Joshi et al., 2015a] states that fractional chromatic number of T ( ) is bounded from above by K -1. Then by the lemma 5 with have with probability at least 1 -δ :

R(h) ≤ RT( ) (h) + R T ( ) ( • r ) + 5 2 R T ( ) ( • r ) + r 2 log 1/δ m + 25 48 log 1/δ m ,
entails the statement of the theorem 1.

Our main result is the following theorems which bounds the generalization error of a function h ∈ learned by minimizing RT κ ( π ) .

Theorem 2 (a). Let = (x

y i i ) m i=1 ∈ ( × ) m be
R(h) ≤ α RT κ ( π ) (h)+αR T κ ( π ) ( • )+α (K -1) log 2/δ 2M κ + 2α log 4K/δ β(m -1) + 7β log 4K/δ 3(m -1) .
holds with probability at least 1 -δ, for any δ > 0, the for all h ∈ , : {-1, +1} × → [0, 1] is the 0/1 loss, and

α = max y: 1≤ y≤K η y /π y , β = max y: 1≤ y≤K 1/π y ,
and η y is strictly positive empirical probability of the class y over .

Proof. By lemma 4 we have for ¯

= ¯ × | , ¯ [ y(x) = i] ∝ π i , 1 ≤ i ≤ K with probability at least 1 -δ/2 : R(h) ≤ α x y ∼ ¯ RT κ ( π ) (h) + 2α log 4K/δ β(m -1) + 7β log 4K/δ 3(m -1)
.

By theorem 4 of [START_REF] Usunier | Generalization error bounds for classifiers trained with interdependent data[END_REF] we have with probability at least 1 -δ/2 :

x y ∼ ¯ RT κ ( π ) (h) ≤ RT κ ( π ) (h) + R( ) + χ * T κ ( π ) log 2/δ 2M κ ,
where a dependency graph for subsample T κ ( π ) is a subgraph of the dependency graph for the whole sample T ( ).

Then by lemma 1 we have χ * T κ ( π ) ≤ χ * T ( ) = K -1, the last is due to theorem 1 of [Joshi et al., 2015a], where χ * T ( ) and χ * T ( ) stand for the fractional chromatic number of the dependency graph for T κ ( π ) and T ( ) resp. Gather together the last two equations we prove the theorem.

Theorem 2 (b). Let = (x

y i i ) m i=1 ∈ ( × ) m

be a dataset of m examples drawn i.i.d. according to a probability distribution over × and T ( ) = ((Z i , ỹi )) N

i=1 the transformed set obtained with the transformation function T defined in Eq. (3.7). Let π ∈ ( × ) M and T κ ( π ) be a training set derived from T ( ) using the algorithm DS-mRb with parameters π 1 , . . . , π K and κ. With the class of functions = {g : × → } and = {h : h(φ(x y ), φ(x y )) = g(x y ) -g(x y ), g ∈ }, consider the parameterized family r which, for r > 0, is defined as :

r = {h : h ∈ , [h] . = Z, ỹ [1 ỹh(Z) ] ≤ r},
where denotes the variance. Then for any δ > 0 with probability at least (1 -δ) the following generalization bound holds for all h ∈ r :

R(h) ≤ α RT κ ( π ) (h) + αR T κ ( π ) ( • r ) + α log 4/δ 2m + 2α log 4K/δ β(m -1) + 7β log 4K/δ 3(m -1) + 5α 2 R T κ ( π ) ( • r ) + r 2 (K -1) log 2/δ κM + 25α 48 log 2/δ M ,
where : {-1, +1} × → [0, 1] is the 0/1 loss and R( r ) is the Local Fractional Rademacher Complexity defined as:

R( r ) . = 2 N ξ   k∈[K-1] ω k Z k   sup h∈ r α∈ k (T ( )) ξ α h(Z α )    
with ξ = (ξ 1 , . . . , ξ N ) a sequence of N independent Rademacher variables such that

(ξ n = 1) = (ξ n = -1) = 1/2
, and α = max y: 1≤ y≤K η y /π y , β = max y: 1≤ y≤K 1/π y , and η y > 0 is the empirical probability of the class y over .

Proof. The proof of the theorem essentially combines the results of theorem 1 and lemma 4.

By lemma 4 we have with probability at least 1 -δ/2 :

R(h) ≤ α x y ∼ ¯ RT(x y ) (h) + 2α log 4K/δ β(m -1) + 7β log 4K/δ 3(m -1) . (3.19)
Lemma 2 (a) applied to T κ ( π ), T κ ( π ) = M κ gives with probability at least 1δ/2 :

x y ∼ ¯ RT(x y ) (h) ≤ RT κ ( π ) (h) + R T κ ( π ) ( • r )+ 5 2 R T κ ( π ) ( • r ) + r 2 (K -1) log 2/δ M κ + 25 48 log 2/δ M (3.20) Substitution (3.19) in (3.20) gives : R(h) ≤ α RT κ ( µ ) (h) + αR T κ ( µ ) ( • r ) + 2α log 4K/δ β(m -1) + 7β log 4K/δ 3(m -1) + 5α 2 R T κ ( µ ) ( • r ) + r 2 (K -1) log 2/δ M κ + 25α 48 log 2/δ M
Proof of the theorem 2. The statement of theorem 2 in the paper is essentially a union of the statements of theorem 2 (a) and theorem 2 (b) proved above.

LARGE-CLASS (EXTREME) CLASSIFICATION EXPERIMENTS USING DS-mRb

In this section, we provide an empirical evaluation of the proposed reduction approach with the DS-mRb sampling strategy for large-scale multi-class classification of document collections. First, we present the mapping φ : × → p . Then, we provide a statistical and computational comparison of our method with state-of-the-art largescale approaches on popular datasets.

Datasets

We evaluate the proposed method using popular datasets from the Large Scale Hierarchical Text Classification challenge (LSHTC) 1 and 2 [START_REF] Partalas | LSHTC: A Benchmark for Large-Scale Text Classification[END_REF]. These datasets are provided in a pre-processed format using stop-word removal and stemming. Various characteristics of these datesets including the statistics of train, test and heldout are listed in Table 3.4. Since, the datasets used in LSHTC2 challenge were in multi-label format, we converted them to multi-class format by replicating the instances belonging to different class labels. Also, for the largest dataset (WIKIlarge) used in LSHTC2 challenge, we used samples with 50,000 and 100,000 classes.

The smaller dataset of LSHTC2 challenge is named as WIKI-Small, whereas the two 50K and 100K samples of large dataset are named as WIKI-50K and WIKI-100K in our result section.

Datasets

Baselines

We compare the proposed approach, denoted as the sampling strategy by DS-mRb, with popular baselines listed below:

• OVA: LibLinear [Fan et al., 2008a] implementation of one-vs-all SVM.

• M-SVM: LibLinear implementation of multi-class SVM proposed in [START_REF] Crammer | On the algorithmic implementation of multiclass kernel-based vector machines[END_REF].

• RecallTree [START_REF] Daume | Logarithmic time one-against-some[END_REF]: A recent tree based multi-class classifier implemented in Vowpal Wabbit.

• FastXML [START_REF] Prabhu | Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning[END_REF]]: An extreme multi-class classification method which performs partitioning in the feature space for faster prediction.

• PfastReXML [START_REF] Jain | Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications[END_REF]: Tree ensemble based extreme classifier for multi-class and multilabel problems.

• PD-Sparse [START_REF] Yen | Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification[END_REF]: A recent approach which uses multi-class loss with 1 -regularization.

For methods FastXML, PfastReXML and PD-Sparse we used the solvers provided by the authors. Also referring to the work [START_REF] Yen | Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification[END_REF], we did not consider other recent methods SLEEC [START_REF] Bhatia | Sparse local embeddings for extreme multi-label classification[END_REF] and LEML [Yu et al., 2014a] in our experiments, since they have been shown to be consistently outperformed by the above mentioned state-of-the-art approaches.

Feature Representation

For our newly proposed method DS-mRb, we used mostly the same features as used for mRb. The only difference is the last two features. Instead of using the to nearest neighbors, we use centroid distance and BM25 as the last two features. The two additional features gave good promise for better result. The feature are summarized in Table 3.5.

Parameter Tuning

Each of these methods require tuning of various hyper-parameters that influence their performance. For each methods, we tuned the hyper-parameters over a heldout validation set and used the combination which gave best predictive performance. In the following section we will discuss the important hyper-parameters that we needed to tune. Features in the joint example/class representation representation φ(x y ).

1.

t∈ • OVA, M-SVM: For both these methods chose SVM with linear kernel as the base classifier, since it was performing the best in our experiments as well as reported in another work [START_REF] Yen | Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification[END_REF]. Here, the parameter to be tuned for both these methods is the penalty term denoted as 'C'.

• RecallTree: For RecallTree method, we tuned four hyper-parameters: bit precision ("b"), learning rate (l), loss function type (loss_function) and number of passes over the training data (passes).

• FastXML and PfastReXML: For FastXML and PfastReXML methods the important hyper-parameters are: number of trees to be grown (t) and SVM weight co-efficient (c).

• PD-Sparse: For PD-Sparse method the hyper-parameters to be tuned are:

L1-regularization weight weight (l) and training with or without hashing (mul-tiTrain or multiTrainHash respectively). Here, it is important to note that the use of hashing causes lower memory usage but increases the training time significantly. However, for larger datasets it was impossible to train without hashing because of huge memory required by the model. Hence, in all our methods we used hashing while training.

• DS-mRb: For the proposed method, we first choose the average number of examples to be taken per class in the first sub-sampling. Then based on the probability distribution of each class we randomly pick examples from each class. Also we tune the number of adversarial classes (κ) and Candidate classes (q).

The list of used hyper-parameters for our final results are reported in the table 3.6. The parameters of the datasets along with the results for compared methods are shown in Table 3.7. The results are provided in terms of train and predict times, total memory usage, and predictive performance measured with accuracy and macro F1-measure (MaF 1 ). For better visualization and comparison, we plot the same results as bar plots in Fig. 3.6 keeping only the best five methods while comparing the total runtime and memory usage.

First, we observe that the tree based approaches (FastXML, PfastReXML and RecallTree) have worse predictive performance compared to the other methods. This is due to the fact that the prediction error made at the top-level of the tree cannot be corrected at lower levels, also known as cascading effect. Even though they have lower runtime and memory usage, they suffer from this side effect.

For large scale collections (WIKI-Small, WIKI-50K and WIKI-100K), the solvers with competitive predictive performance are OVA, M-SVM, PD-Sparse and DS-mRb. there is an improvement in both accuracy and MaF 1 measures.

The recent PD-Sparse method also enjoys a competitive predictive performance but it requires to store intermediary weight vectors during optimization which pre-vents it from scaling well. The PD-Sparse solver provides an option for hashing leading to fewer memory usage during training which we used in the experiments; however, the memory usage is still significantly high for large datasets and at the same time this option slows down the training process considerably.

In overall, among the methods with competitive predictive performance, DS-mRb seems to present the best runtime and memory usage; its runtime is even competitive with most of tree-based methods, leading it to provide the best compromise among the compared methods over the three measures: time, memory and predictive performance.

CLOSING REMARKS

In this part of the thesis we presented a new approach to reduce a large-scale multiclass classification problem to equivalent binary classification problem by subtraction of pairwise joint representation of example, class pairs. First, we proposed a basic algorithm, which helps to overcome the challenges of class imbalance and large-scale classification. However, the reduction process introduces new challenges corresponding to the size of the new binary dataset and the time taken for the reduction process as well as the memory usage. To overcome these new challenges, we introduced an extended version of the algorithm referred to as DS-mRb. This extension of naive approach incorporates a double sampling approach during reduction and candidate selection during prediction phase. This helps to reduce the total runtime and memory usage of the algorithm, whereas the predictive performance remains the same as before. We also experimentally validated the effectiveness of the propsoed approach on popular datasets of text classification considering large class cases (up to 100000).

The experiments were performed on 5 different datasets of different characteristics and sizes. We also present the comparison of result with respect to 6 other recent state-of-the-art approaches for large-scale multiclass classification. The results suggest that the propsoed approach, DS-mRb is the best performance compromise among all compared methods.

II ASYNCHRONOUS FRAMEWORK FOR DIS-

TRIBUTED MACHINE LEARNING 4 DISTRIBUTED MACHINE LEARNING

INTRODUCTION

As the popularity of internet has increased over the last decade, the amount of available data has grown rapidly. So, machine learning algorithms need to be (re)designed to handle these large-scale datasets. Some of the common machine learning domains with such magnitude of data are binary classification and recommender systems. For example, in large-scale binary classification problems, the number of examples and the feature size can be upto the order of millions. Similarly, recommender system applications may involve users, items and ratings of the order of millions or even more.

Handling this magnitude of data has become a prominent challenge in the machine learning community. Even if we are able to keep it in a single machine, running a machine learning algorithm on such huge datasets takes unacceptably large amount of time.

Perhaps the simplest strategy in such situations is to reduce the dataset by discarding many examples, also known as subsampling. However, this strategy can only be useful if the problem is simple enough. However, in most of the machine learning applications, subsampling significantly affects the quality of the machine learning model as we are throwing away useful information.

DISTRIBUTED ALGORITHMS

So, a better solution is to run the machine learning algorithms in a distributed manner simultaneously. Distributed algorithms can be divided into two groups:

1. Shared Memory or Parallel Algorithms : These algorithms make use of multiple cores within the same machine while keeping the entire dataset in the main memory. So, all the processors have access to the data and can perform the machine learning optimization simultaneously [START_REF] Zinkevich | Parallelized stochastic gradient descent[END_REF], Recht et al., 2011, Jaggi et al., 2014, Leblond et al., 2016, Zhao and Li, 2016]. However, one obvious drawback is that the size of datasets can be so huge that it might not fit in the memory of single machine.

2. Shared-Nothing or Distributed Algorithms: Another line of algorithms consider a fully distributed scenario [START_REF] Dean | Large scale distributed deep networks[END_REF], Xu and Yin, 2014, Chang et al., 2015,Zhang et al., 2015,Huo and Huang, 2016], where the individual machines has its private memory which cannot be directly accessed by another machine.

They are suitable for many industry scale applications, since datasets are usually collected and stored in a decentralized manner using a cluster. In such cases, it is a tedious task to move data from different machines to a single machine. In this work, we also consider the fully distributed scenario and will refer it simply with the term "distributed" throughout the rest of the thesis.

DESIRED PROPERTIES OF DISTRIBUTED SYSTEM

In the distributed setting, information needs to be communicated over the network bandwidth, which is a limited resource. Hence, communication cost is one of the most important considerations for distributed frameworks. Moreover, it is also important to make sure that each machine runs reliably without failure, especially when the workload is increased significantly. A good distributed framework should be able to address these challenges inherent in distributed environments. Below we will discuss the main desired properties of a distributed computing system [Li, 2017]:

1. Efficiency: Distributed computing systems should incur least communication cost while making an optimal usage of the computing resources. In the distributed environments the available network bandwith is very limited and has to be shared by several machines for exchanging information. For example, the memory bandwith of a personal computer is around 400 Gbit/sec, whereas the network bandwidth on Amazon AWS is just 10 Gbit/sec [Li, 2017]. Moreover, the communication latency in such systems are significantly worse. For instance, the latency for accessing the main memory in single machine is around 100 ns, whereas in data centers it is around 0.1 ms to 1 ms.

Also, the machines in distributed systems usually have different computing power and are running different workloads. Hence, some of them are significantly faster/slower than the others. So, the distributed algorithms relying on synchronization between the machines do not perform well, since the slower machines become the performance bottleneck of the entire system. Hence, while designing the distributed algorithms such synchronization between the machines should be avoided.

2. Fault Tolerance: One common problem in distributed computing environments is that a machine can fail during computation. Such failures occur more in distributed systems comprising of large number of machines and handling large amount of data. Hence, a good distributed system should be robust to such failures. Many of the advanced distributed frameworks such as Spark1 , OpenMPI2 , MPICH3 have specialized features for fault tolerance.

3. Ease of use: The programming interface of a distributed system should be simple and flexible. It should provide an interface which hides the implementation details, while being flexible enough to implement several different algorithms.

DISTRIBUTED FRAMEWORKS

In this age of big data, there are many programming frameworks available to devise distributed algorithms in parallel and distributed environments. Here we will review two of the widely recognized frameworks for distributed system: Message Passing Interface (MPI) [Snir, 1998] and MapReduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF].

1. MPI: is a message passing library specification utilizing a message passing model for parallel and distributed environments [Snir, 1998]. It is not a programming implementation by itself. There are several available implementation of MPI specification such as OpenMPI, MPICH and GridMPI [START_REF] Diaz | A survey of parallel programming models and tools in the multi and many-core era[END_REF].

MPI provides point-to-point, collective, one-side, and parallel I/O models for communication. Point-to-point communication allows the exchange of information between to communicating processes, whereas a collective communication refers to the broadcast of message from one process to many processes.

MPI also allows message passing in various modes such as blocking and nonblocking communication. It can be used in various platforms such as Linux, OS X, Windows, Solaris etc. It works with different file systems such as NFS, HDFS etc. The main advantage of using MPI is its flexibility of programming. In MPI, the programmer has full control over the framework, hence it can be used to devise complex architectures. Moreover, MPI supports both synchronous and asynchronous communication. Hadoop frameworks which read and write data to and from HDFS file system.

PROBLEM FORMULATION

We consider a fully distributed scenario where training sets are stored over M connected machines. Such applications have attracted much interest in both machine learning and optimization communities. In this work, we consider the minimization of a loss function which can be represented as the sum of smooth functions.

Here, depending on the application, this minimization objective can have different forms. We will list the three possible cases:

• Case 1:

(v, w) = M i=1 i (v i , w) (4.1)
where v = (v 1 , .., v M ). In this model, each loss function i depends on (i) a local version of parameter v, i.e. v i , that does not need to be exchanged across different machines, and (ii) a shared parameter w that has to be exchanged.

• Case 2:

This is the case where each loss i , depends only on local versions of parameter v, the learning problem reduces as shown below. This is a totally parallel scenario that can be solved locally on each machine in parallel.

(v) = M i=1 i (v i ) (4.2)
• Case 3:

The other extreme is a more typical case where each loss i , depends only on the global shared parameter w and the learning problem in this case reduces to:

(w) = M i=1 i (w) (4.3)
This kind of problem is extremely common in ML when one wants to find the best predictor from a dataset split in several batches.

In this work, we will consider two applications, which will represent the two distributed scenarios shown above. First, we will consider distributed matrix factorization problem with Stochastic Gradient Descent (SGD) based optimization. This corresponds to Case 1 above. We will notice that in this problem, we need to update two parameters out of which one is totally local to machines, whereas the other one needs to be shared among the machines. Second, we will consider the problem of binary classification which corresponds to Case 3. In this problem, each machines locally update a parameter vector which needs to be shared among all the machines periodically.

ASYNCHRONOUS DISTRIBUTED STRATEGY

In this section, we present our proposed asynchronous distributed approach by first describing the deduced learning strategy. We then provide a consistency justification in the form of a convergence proof.

DESCRIPTION

The main challenge of distributed learning is to effectively partition the data into computing nodes, and efficiently perform communication between them. Indeed, in the synchronous case, the slowest node becomes the bottleneck of the whole system and a potentially large amount of computational time is lost (Figure 4.1 (a)).

The main idea of our approach is that when a machine finishes an iteration over the subpart of the data it contains, it broadcasts its updated parameter values to the master node; which gathers the received parameter values from the workers (if any, and taking only the last one if multiple parameter values are received from one machine); and updates the parameter vector with the received updates. Then the updated parameter is broadcasted to worker nodes. In this way each computing node runs its iterations independently and gets rid of the synchronization bottleneck. Faster machines will perform their epochs faster, whereas the slower ones will be lagging on time but after finishing each epoch they will receive the most updated parameters from the master.

This situation is depicted in Figure 4. 1 (b).

The main difference with other distributed asynchronous algorithms proposed in the literature [Zhang et al., 2015, Huo and[START_REF] Huo | [END_REF], our approach does not exchange gradients but rather parameter values updated after one complete pass over local subpart of the data. Although these quantities have the same sizes, we show that broadcasting of parameters performs better in practice, since they are exchanged after each epoch, whereas gradients need to be exchanged after every mini-batch update.

CONSISTENCY JUSTIFICATION

In the case where the training data is partitioned into M batches { 1 , . . . , M }, one for each computing machine, in the shared parameter case, the objective Eq. ( 4.3) can be rewritten as

(w) = M i=1 i (w). (4.4)
Here we may take advantage of the differentiability of ( i ) M i=1 and use a gradient algorithm to find a minimizer of the global objective, . With a fixed stepsize gradient as an elementary operation before exchanging, we make the following assumptions : Assumption 1 (on the functions).

a. The objective function, , has a unique minimizer w ; b. Each i is differentiable and ∇

i is 1 L -cococercive, that is ∀w, w ∈ d : 〈w -w ; ∇ i (w) -∇ i (w )〉 ≥ 1 L ∇ i (w) -∇ i (w ) 2 .
As a consequence of the Baillon-Haddad theorem (Th. 18.15 in [START_REF] Bauschke | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]); Assumption 1 (b) is notably verified whenever all functions i are convex and L i -smooth, that is differentiable with an L i -Lipschitz continuous gradient

Asynchronous Distributed Gradient update rule

When machine i finishes computing ∇ i (w [START_REF] Zhu | Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities[END_REF]). In our case, this means that if the (smooth) cost function is non-convex, then one can add a 2 regularization term so that the sum function verifies the sought property.

k-d k i ) (Local step) at i: w k+1 i = w k-d k i -γ∇ i (w k-d k i ) (Master step) w k+1 = 1 M M j=1 w k+1 j Broadcast w k+1 with L = max i L i . Also, if a function i is L i -smooth but not necessarily convex, then, considering g i = i + λ/2 • 2 , it comes that ∇g i is 1/(2λ) cocoercive for λ > L (see Prop. 2 in
In Assumption 2, we also make the rather mild assumption that the delays are bounded, meaning that no machine is infinitely slower than the others. More precisely, we consider that the duration of its computation is bounded by D in the sense that if machine i finishes its computation at time k + 1, then the value of the averaged parameter it used is at most D ticks old. Mathematically, denoting the computation delay for machine i at time k by d k i , our bounded delay assumptions means that when machine i finishes, say at time k, the (outdated) value of the averaged parameter it used is w

k-d k i with d k i ≤ D.
Assumption 2 (on the algorithm). The delays are uniformly bounded, i.e. there is D < ∞ such that for any machine i and iteration k; the delay d k i ≤ D.

The proposed Asynchronous Distributed update rule, corresponding to Figure 4.1 (b), is summarized in the pseudo-code in the right. In the local step, all machines including the master update their parameters; and in the master step, once the master finishes its update, it broadcasts the aggregated parameters (from the latest received ones) to all workers. Furthermore, using a gradient step as an elementary operation, the convergence of the algorithm can be proven with the attractive properties that the considered stepsizes can be chosen fixed, as in the standard gradient algorithm, and thus do not decay or depend on the delay; and that no assumptions are made on the distribution of the delays.

Theorem 1 (Convergence). Suppose that Assumptions 1 and 2 hold. Let γ ∈]0, 2/L[.

Then the sequence (w k ) k produced by our Asynchronous Distributed Gradient update rule converges to w .

Proof. From Assumption 1 (i), w is the unique minimizer of and ∇ (w ) = M i=1 ∇ i (w ) = 0. Let us define for all i = 1, .., M w i = w -γ∇ i (w ). Then at time k for the updating machine i, it comes from the cocoercivity of ∇ i , Assumption 1 (b); and the definition

w k+1 i = w k-d k i -γ∇ i (w k-d k i ): w k+1 i -w i 2 = w k-d k i -γ∇ i (w k-d k i ) -(w -γ∇ i (w )) 2 ≤ w k-d k i -w 2 + γ 2 ∇ i (w k-d k i ) -∇ i (w ) 2 - 2γ L ∇ i (w k-d k i ) -∇ i (w ) 2 .
Now by setting δ = γ 2 L -γ > 0 we get:

w k+1 i -w i 2 ≤ w k-d k i -w 2 -δ ∇ i (w k-d k i ) -∇ i (w ) 2 = 1 M M j=1 (w k-d k i j -w j ) 2 -δ ∇ i (w k-d k i )-∇ i (w ) 2 ≤ 1 M M j=1 w k-d k i j -w j 2 -δ ∇ i (w k-d k i ) -∇ i (w ) 2 ,
where we used the fact that

M j=1 w j = M j=1 w -γ M j=1 ∇ j (w ) = M w .
As the gradient of the objective ∇ (w) = M j=1 ∇ j (w) is null at w . The last inequality is due to the convexity of the squared norm. For all other j = i,

w k+1 j -w j 2 = w k j -w j 2 .
Let

y k d = ( w k-d i -w i 2 ) i=1,.
.,M be the size-M vector of the individual errors at time kd; and let y k be the size-M (D + 1) vector obtained by concatenating the (y k d ) d=0,..,D . From y k to y k+1 , we have that i) the last M values, y k D , are dropped as they cannot intervene as D is the maximal delay; ii) the other ones are moved M coordinates lower

y k+1 d+1 = y k d for d = 0, .., D -1;
iii) for the first M coordinates, they are copied from time k, y k+1 0 = y k 0 , except for the i-th one which verifies

w k+1 i -w i 2 ≤ 1 M M j=1 w k-d k i j -w j 2 thus y k+1 0 (i) ≤ 1 M M j=1 y k d k i ( j).
Thus one can write y k+1 A k+1 y k where ' ' indicates the elementwise inequality and A k+1 represents the linear (in)-equalities mentioned above. A k+1 , seen as a (D + 1) × (D + 1) block matrix has identities on its sub-diagonal, and the top left block is the identity except for line i which has 1/M coefficients on the M columns corresponding to d k i . One can notice that it is non-negative and the row sum is constant equal to 1.

Taking the ∞ -norm, we have

y k+1 ∞ ≤ A k+1 y k ∞ ≤ A k+1 ∞ y k ∞ ≤ y k ∞
as the ∞ -induced matrix • ∞ is the maximal row sum and all rows of non-negative matrix A k+1 have unit sum. This means that ( y k ∞ ) k is a converging sequence, say to some value α. Now, suppose that there is some coordinate that is strictly lower than α, then it cannot be equal to α or greater anymore due to the above inequality; this means, that as the communication time is bounded, any coordinate holding the value α will have to (strictly) decrease due to the averaging with the strictly lower coordinate, which contradicts α being the limit of sequence ( y k ∞ ) k . Thus, all errors converge to the same value which means that ∇ i (w

k-d k i ) -∇ i (w ) 2 → 0, implying that all w k
i and thus w k converge. Furthermore, all limits points of w k null the gradient of ;

w being unique (Assumption 1 (i)), the convergence ensues.

One can notice that using this asynchronous framework, the machines local parameters all converge to different values while their sum converge to the sought minimizer. As this sum is received after each iteration, the agents also have individual knowledge of the full minimizer. Finally, the tools used in this proof make it adaptable to a wide range of elementary operations verifying cocoercive contraction properties.

For instance, if the loss has a smooth and a non-smooth part, the gradient step can be replaced by a proximal gradient step. Other possible extensions here include the Alternating Direction Method of Multipliers (ADMM) and Primal-Dual algorithms. to large industrial potential. The main aim of Recommender Systems is to provide a personalized recommendation of an online product or service to the users, who are usually overloaded with the available information. So, we can also define it as an information filtering system on the web. Hence, the ultimate goal of the Recommender systems is to improve the customer relationship management as well as the revenue from the industrial viewpoint. RS recommends suitable items to users by predicting the user's interest in an item based on the information about the users, items or their interactions [START_REF] Bobadilla | Recommender systems survey[END_REF]. The main feature of RS is to "guess" user's preferences and interests by analyzing information related to the user and/or other users to provide them with personalized recommendation [START_REF] Resnick | Recommender systems[END_REF]. Some

FORMAL DEFINITION

Formally, a recommendation problem involves estimating the ratings for the items that has not been seen or rated by a particular user [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF]. The prediction is performed based on the user's interaction with other items or some meta information related to the users or items.

Hence, in this user-item context, a recommendation problem can be formulated as follows. Let U and I denote set of users and items respectively. In modern applications, the set U and I are very huge, millions or billions in most cases. Recommendation system takes these two sets of users and additionally the partial ratings given by some of the users to some of the items. Usually the number of ratings are very few. The recommendation problem can be divided into two sub-problems:

1. Finding the unknown ratings 2. Sorting the ratings to provide top-k recommendation

Here, the second sub-problem is a sorting problem. Whereas the first sub-problem carries more importance. The problem of estimating the ratings can be considered as the problem of estimating a utility function. Let f be an utility function which outputs an item's importance corresponding to a user. Hence, the recommendation problem can be defined as finding a subset i ∈ I of items to be recommended for each user u ∈ U that maximizes the utility function f. Mathematically:

∀u ∈ U, i = argmax i∈I f(u, i) (5.1)
In the context of RS, user's rating for the items is represented as a matrix known as rating matrix. In this matrix the rows represent the uses and the columns represent each of the items. Each cell of the matrix contains the corresponding user's rating for that item. Figure 5.1 presents a sample rating matrix, where the non-zero values indicate user's rating for items and zeros represent unknown ratings. As already discussed the main aim of the RS is to estimate those unknown values in the rating matrix. As can be seen in the figure, user's provide rating for very few items. Hence, most of the values in the rating matrix are unknown which makes the matrix sparse. In most of the real cases, the sparsity of the rating matrix can be upto 99 %.

TYPES OF RECOMMENDER SYSTEM MODELS

Broadly, RS methods can be divided into two main groups: In CB methods, items are recommended to a user, which are similar to the items user has preferred in the past [START_REF] Pazzani | Content-based recommendation systems[END_REF]. Here the notion of similarity is derived from the metadata of the items. Based on the user's preference in the past, a list of attributes are derived known as the user-profile. Similarly, an item profile is created using the information about the item such as item descriptions or features.

• Content Based Recommendation • Collaborative Recommendation
Hence, the recommendations are done by matching user and item profiles. For example a movie profile could include attributes such as: genre, participating actors, popularity etc and user profile might include attributes such as: demographic information or user's response to some questionnaire. The CB programs hence try to match the users and items based on the similar attributes in their profiles [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

According to [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF], the main limitations of Content-Based RS are as follows:

• Content Scarcity: In real-case scenarios it is observed that obtaining the explicit attributes about the users and items is difficult. In many situations, these information are very scarce. Hence, matching users and items using such limited content directly affects the performance of the recommender system.

• Over-specialization: Another issue with these methods is that they tend to overfit the user's behavior based on the past preference. Hence, the users are always recommended with similar items everytime. This can be reduced by introducing randomness in the user/item profiles.

• New user problem: This is a common problem in most of the RS methods, commonly known as cold-start problem. This problem arises because of the lack of information about a user's past rating.

Collaborative-Filtering Based Recommendation (CF)

These methods identify user-item associations by analyzing the relationships between users and interdependencies among items. These methods rely on user's previous ratings to estimate unknown ratings without requiring to create explicit profiles [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. In practice they are more accurate than the CB methods [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

There are two types of CF-based methods used primarily in RS: memory-based methods and model based methods. Memory based methods use user rating data to compute similarity between users or items. Users are recommended new items based on the similarity. These approaches are effective and easy to implement. However, computing user/item similarity is a tedious task for large RS datasets. Model based approches are one of the most successful approaches of RS and implemented in most of the industries. The main idea of these approaches is to learn a model from the rating data and estimate unknown ratings using the model. Most popular example of model based RS is latent factor models. These methods try to estimate the ratings by characterizing both users and items with low-dimensional factors inferred from the rating patterns.

The main limitations of CF methods includ:

• New user problem (cold-start): This is the problem same as for CB methods, arising while recommending items to a new user.

• New item problem: CF relies on ratings of similar users on an item. But if an item is not rated by enough users, then the recommendation results can be very biased.

• Sparsity: Huge sparsity in rating matrix is another prominent problem of CF methods. Since, its difficult to calculate similarity in the presence of sparsity and the models tend to overfit in such data.

MATRIX FACTORIZATION FOR RECOMMENDER SYSTEM

The most successful approach to realize latent factor model in practice is matrix factorization [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. Matrix factorization for collaborative filtering captured much attention, especially after the Netflix prize [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. The premise behind this approach is to approximate a large rating matrix R with the multiplication of two low-dimensional factor matrices P and Q, i.e. R ≈ R = PQ that model respectively users and items in the same latent space. Hence the interaction between users and items are modeled as the inner product in the latent space. These latent factors are supposed to decode hidden information which defines user's interest for items. This model is closely related to a Singular Value Decomposition (SVD), which is a popular factorization method in linear algebra. We cannot apply SVD to collaborative filtering because of the sparsity of the rating matrix, since conventional SVD is not defined if the matrix is not complete and anyway the complexity of computing SVD in large dimension is prohibitive.

LOSS FUNCTION

For a pair of user and item (u, i) for which a rating r ui exists, the corresponding instantaneous loss is defined as 2 -regularized quadratic error:

(P, Q, u, i) = r ui -q i p u 2 + λ(||p u || 2 + ||q i || 2 ), (5.2)
where p u (resp. q i ) is u-th line of P (resp. i-th line of Q) and λ ≥ 0 is a regularization parameter. The global objective is hence :

(P, Q) = (u,i):r ui exists (P, Q, u, i). ( 5.3)
Note that instantaneous error (P, Q, u, i) depends only on P and Q through p u and q i ; however, item i may also be rated by user u so that the optimal factor q i depends on both p u and p u .

LEARNING ALGORITHMS

Two algorithms are popularly used to minimize the loss function of 5.2.

Alternating Least Squares (ALS)

Equation 5.2 consists of two unknowns p u and q i making the error function nonconvex. However, we can fix one of the two unknowns and make the optimization problem quadratic, for which an optimal solution can be obtained. Hence, in ALS method, we alternately fix one variable and solve the least square problem for the other variable. This iterative process ensures the convergence of overall problem. In the following we will summarize the strong and weak points of this algorithm.

Strong points:

• This changes the originally non-convex problem to a convex (quadratic) problem, for which a closed-form solution can be obtained.

• It is easy to parallelize ALS [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF] as updating individual rows of one of P or Q while fixing the other can be done simultaneously.

Weak points:

• Even though they are good for parallel applications, it becomes a challenge when the size of P or Q becomes large to be fit in the memory of a single machine.

• Per iteration convergence speed of ALS is slower as compared to SGD (which we will discuss next).

• They are not trivial to implement and their predictive performance is not as good as SGD based optimization.

Stochastic Gradient Descent (SGD)

SGD is a popular optimization algorithm in Machine Learning [Bottou, 2010], and it has also been shown to be effective for matrix factorization [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. It has gained popularity, especially after being the winning solution for the Netflix prize competition 1 .

In this case, the approach proceeds as follows: at each iteration k,

• select a user/item pair (u k , i k ) for which a rating exists;

• perform a gradient step on (P, Q, u k , i k ).

Algorithm 5 presents the algorithmic steps of SGD for matrix factorization. Here, m, n and k denote the total users, items and dimension of latent space simultaneously.

Input:

A training set m×n , initial values m×k and n×k while not converged do Select a training point (u,i) ∈ R uniformly at random

P u * ← P u * -α ∂ ∂ P u * (R ui , P u * , Q * i ) Q * i ← Q * i -α ∂ ∂ Q * i (R ui , P u * , Q * i ) P u * ← P u * end Algorithm 5: SGD for Matrix Factorization
Here stochasticity is used in the sense that the gradient on (P, Q, u k , i k ) can be seen as an approximation of the gradient on an underlying global model but the choice of the considered users/items may or may not be random depending on the algorithm.

Here, we will summarize the main strong and weak points of this algorithm.

Strong points:

• Ease of implementation.

• Better predictive performance and convergence speed.

Weak points:

• The updates of SGD are inherently sequential, hence its not straightforward to parallelize it. Moreover, the traditional convergence analysis is based on this assumption of sequential updates.

• Another drawback of a straightforward parallel implementation is that updates on factor matrices might not be independent. For example, for training points that lie on same rows (i.e. ratings corresponding to the same users), an SGD step modifies the same corresponding rows in factor matrix P; thus, these points cannot be learnt over in parallel and efficient communication between the computing nodes is necessary to synchronize the updates on factor matrices.

MATRIX FACTORIZATION WITH USER AND ITEM BASED

REGULARIZATION

From the literature, we noticed that both memory and model based methods have their strong and weak points. Both type of methods rely on different types of information to enhance the RS performance. There is not a single method which acts flawlessly.

Hence, we try to incorporate the benefits of Neighborhood based method in matrix factorization method by introducing new regularization terms for similar users and similar items.

The intuition behind similarity based regularization is that similar users have similar tastes. Hence, we impose that the factor vector of each user (resp. item) should be close to the average factor vector of its similar users (resp. items). For computing the most similar users (or items) we considered a modified version of Pearson correlation coefficient [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF] which for two users u i and u j writes:

sim(u i , u j ) = i k ∈I c (r ik -r i. )(r jk -r j. ) i k ∈I c (r ik -r i. ) 2 i k ∈I c (r jk -r j. ) 2
Where, I c is the items co-rated by both users, r i. and r j. denote the average ratings for u i and u j respectively.

Hence, we are able to find the N most similar users for u i , denoted by N i (resp. N j for items similar to i j ). We now propose a slight modification of the individual ratings objective function of Eq. (5.2) above by adding another regularization term. For a pair of user and item (u i , i j ) for which a rating r i j exists, the similarity-regularized individual objective writes:

1 (u i , i j , P, Q) = (r i j -q j p i ) 2 + λ(||p i || 2 + ||q j || 2 ) +λ u p i - 1 |N i | m∈N i p m 2 + λ i q j - 1 |N j | n∈N j q n 2 (5.4)
where λ u ≥ 0 and λ i ≥ 0 are the regularization parameters linked to the similaruser and similar-item regularizations respectively. Performing the same updates as the conventional SGD but replacing by 1 , we get Algorithm 6 for minimizing the whole matrix factorization problem (Eq. 5.

3) where is replaced by 1 i.e. the similarityregularized problem: min P,Q i, j:r i j exists 1 (u i , i j , P, Q).

(5.5)

Input: R, λ, λ u , λ i Initialize: and randomly while not converged do Choose randomly (u i , i j ) ∈ R N i = GetSimilar Users(i, N )

N j = GetSimilar I t ems( j, N )

Update p i and q j by a gradient step on 1 (u i , i j , , ) (Eq. 5.4) end Algorithm 6: Similarity based regularization

RELATED WORK

Despite its simplicity, there are several computational challenges associated with this problem. As previously, performing SGD sequentially on a single machine takes unacceptably large amount of time to converge for common rating matrices of several million ratings. So, there is a need to perform SGD in an efficient distributed manner for such large datasets. In this section we will show a detailed account of performing large-scale matrix factorization in a distributed manner.

Hence, to handle the large-scale matrix factorization, we can distribute the computation across multiple workers. This gives rise to two distributed architectures:

Shared-memory (parallel) and shared-nothing. In the case of shared-memory methods, the entire data is kept in the memory of a single machine and multiple processors work parallelly on the data. However, this might not be a feasible solution if the size of dataset is very huge to fit in a single machine, which is usually the case in modern RS applications. Hence, to overcome this limitation, shared-nothing (totally distributed) approaches are used, in which the machines do not share memory and the dataset is kept in disjoint machines. Even thought the main focus of this thesis is for sharednothing (distributed) scenario, for the sake of completeness we will present some of the popular shared-memory methods.

SHARED-MEMORY METHODS

Earlier work in this line include methods with the name Parallelized SGD (PSGD), in which the dataset is partitioned into several parts and SGD is run independently and in parallel on different subparts. The updated parameters corresponding to each subpart are averaged either after each pass over the data [START_REF] Hall | Mapreduce/bigtable for distributed optimization[END_REF], McDonald et al., 2010] or once at the end [START_REF] Zinkevich | Parallelized stochastic gradient descent[END_REF]. These methods rely on synchronization between the parallel processes, hence exhibit slow convergence rate in practice. Another popular method is HogWild [START_REF] Recht | Hogwild: A lockfree approach to parallelizing stochastic gradient descent[END_REF], which randomly selects subset of rating matrix and apply the update rules simultaneously in parallel fashion without any synchronization between the threads. They also guarantee the convergence of their method when factorizing a highly sparse matrix, where one can ensure that the occurrence of over-writing problem because of multiple threads trying to update the same user/item factor is rare. In a slightly different line of work, [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF] introduced the idea of Stratified SGD (SSGD) and introduced oen algorithm in this line: Distributed SGD (DSGD). This method partitions the rating matrix into disjoint (interchangeable) blocks in which parameter update corresponding to one block is mutually independent to another one. Hence, these methods can be easily parallelized and extended in shared-nothing settings as well. Both of these methods HogWild and DSGD suffer from problems such as: locking problem (arising because of synchronous operation) and memory discontinuity [START_REF] Zhuang | A fast parallel sgd for matrix factorization in shared memory systems[END_REF].

FPSGD [START_REF] Zhuang | A fast parallel sgd for matrix factorization in shared memory systems[END_REF] alleviates the memory locking problem by introducing a novel blocking scheme. Similarly they solve the memory discontinuity by introducing a solution called partial random method which randomly chooses a free block and accesses the block sequentially.

SHARED-NOTHING METHODS

These methods are designed to handle large-scale matrix factorization problems, typically when the rating matrix or the factor matrices are too large to be fit in the memory of a single machine. Here, the important assumption is that the worker machines have disjoint memory. Hence, the main challenge in shared-nothing methods is to have effective communication between the computing nodes [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. Hence, these methods are not that popular as compared to the shared-memory methods in the literature.

A general workflow of shared-nothing methods can be represented as below:

• Partition the data and factor matrices, and dispatch them across the different computing nodes.

• Each node works on different subparts of data and updates the factor matrices accordingly.

• Nodes communicate (exchange) updated parameters between them to have an agreement on the updates. This communication is done once each epoch or multiple times in an epoch.

Depending on the type of partitioning of the data, these methods can be categorized into two types of methods:

Row (or column) wise splitting

One popular example of this type of splitting is ASGD algorithm presented in [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. In this approach, the rating matrix is partitioned row-wise into several Factor matrices are thus updated independently on each machine for the corresponding ratings. Even though the rating matrix parts on each machine are different, the factor matrix updates are not independent. So, after each epoch the factor matrices present in each machine are synchronized. However, the machines send the updates to the master machine immediately and hence the author has referred this as an asynchronous method. But this cannot avoid the bottleneck of synchronization after every epoch.

Stratified SGD

The main idea of stratified SGD methods is to exploit the structure of matrix factorization problem and induce disjoint blocks which can be parallelized easily. Each of these disjoint parts are referred to as stratum (or blocks). One such exmple of stratification of rating matrix is shown in Figure 5.3. Here, the rating matrix is denoted as V , and the numbers in the superscript represent the row and column numbers respectively.

Also, Algorithm 7 summarizes the generic algorithm of stratifies SGD method. One popular approach based on stratified SGD is, referred to as Distributed SGD (DSGD) [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF], Makari et al., 2015], which we alredy discussed before in the shared memory section. This method can be extended to be applied in distributed memory architecture as well by placing the disjoint blocks in disjoint computing nodes. Even though these methods can overcome the problem of simultaneous updates, they require several synchronizations within an epoch which hurts their computational performance.

ADG MF ALGORITHM

As we saw in the previous section, even though the stratified partitioning helps to make disjoint sections and rules out the problem of locking or overwriting of updates, it requires synchronization even within the epochs. Hence, in this work we stick with the row-wise blocking of the rating matrix. We apply our asynchronous distributed framework introduced in Section 4.3. In order to apply the asynchronous distributed strategy to this problem (referred to as ADG MF in the following), we split the rating matrix in row-wise manner. Hence, in this case, we only need to communicate the matrices Q between machines, whereas the matrices P are updated locally, corresponding to each sub-part, and are later concatenated at the end of the operation. Hence, this corresponds to Case 1 of Section 4.2. In the distributed network, one of the machines acts as the master machine, whereas the other machines act as the workers. The master machine can also act as one of the workers. In our experiments also we used the master machine as one of the workers. The overall optimization is performed into following two steps:

• Worker Step:

As shown in the asynchronous distributed architecture 4.1b, each worker machine works on their local subpart of data. Because of the row-wise splitting, the updates on matrix are disjoint and hence local to each machine. Whereas, all the worker machines update same rows of matrix. Hence, all the machines need to have an agreement on the updates made on matrix for better and faster convergence. Hence, each worker machines communicate the updated matrix to the master machine, which takes care of aggregating all the received updates from the worker machines and broadcasting it back to the workers. We will discuss more about the master step next. Soon, after sending the updated parameter to the master machine, the worker machine checks if it has received an aggregated parameter from the master or not. If it has received the updated parameter from the master machine, it will begin a new epoch with the updated parameter, otherwise it will continue with its previously updated parameter matrices. In this way, even if the workers are disjoint, they have a common view over the whole dataset and this helps them to converge faster. Also, the slower workers will complete each epoch slow as compared to the faster machines, but once they finish their epoch, they will receive the most updated aggregated parameter from the master. The overall steps performed in a worker step are shown in Algorithm 8.

Parameters: learning rate γ Initialize: P j

Receive matrix Q from the master;

From the subpart of the data stored in machine j, pick randomly (u, i) for which r ui exists ;

(P j , Q j ) ← (P j , Q) -γ∇ (P j , Q, u, i);
Send Q j to the master; Hence, we can observe that both master machine and workers perform their task independently and asynchronously. Hence, this approach avoids the performance bottleneck due to slower machines in the network.

EXPERIMENTAL RESULTS

EXPERIMENTAL SETUP

We conducted a number of experiments to empirically validate the proposed asynchronous framework on matrix factorization for recommendation where the recommendation matrix is split into M rows as in Problem (5.6).

1. Datasets: We performed experiments on Movielens-10M (ML-10M) 2 and the Netflix Collection3 that are two popular corpora in collaborative filtering. Baselines: To validate the asynchronous distributed algorithm described in the previous section, we compare the following four strategies:

• The proposed approach ADG MF (Section 5.4),

• The asynchronous distributed ADMM approach (AD-ADMM) [START_REF] Chang | Asynchronous distributed ADMM for large-scale optimization-part I: algorithm and convergence analysis[END_REF],

• Two distributed algorithms specifically proposed for matrix factorization ASGD [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF] and DSGD [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF].

3. Platform: The distributed framework we considered was implemented using PySpark version 1.5.1. by connecting 7 servers with different computational power.

4. Hyper-Parameters: Various free parameters of SGD such as learning rate (γ), regularization parameter (λ) and number of latent factors (K) were set following [START_REF] Chin | A learning-rate schedule for stochastic gradient methods to matrix factorization[END_REF], [START_REF] Yu | Distributed stochastic admm for matrix factorization[END_REF]. For our proposed similaritybased regularization λ u , λ i , and the number of similar users/items N were chosen with values that led to the best RMSE on validation sets for each collection chosen among {10 -1 , 5.10 -2 , 10 -2 , 5.10 -3 , 10 -3 , 5.10 -4 , 10 -4 } for λ u , λ i and {10, 20, 30, 40, 50} for N . These values as well as the datasets characteristics are listed in Table 6.1.

Evaluation Measures:

In our experiments, we used the Mean Absolute Error (MAE) and the Root Mean Square Error (RMSE) as performance measures. Also, we compared the convergence time for each of the algorithms in the synchronous and the asynchronous distributed settings. 5.3) and (5.5) respectively). We tested two scenarios: i) where only the users are regularized with similarity (λ i = 0); and ii) when both users and items are regularized with the same parameter (λ u = λ i ).

THE EFFECT OF SIMILARITY BASED REGULARIZATION

Table 5.2 shows the complete results of our experiments.

It comes out that forcing the vectors of users and items to lie within the centroids of their most similar users and items found by the Pearson similarity measure is effective as the final RMSE and MAE with Algorithm 1 are always better than with classical SGD. Thus, there is a significant benefit to use this regularization in terms of learning.

We also report results by looking at the effect of the similar user regularization and not items (λ u > 0, λ i = 0). As shown in Table 5.2, this user-only regularization also gives uniformly better results than traditional SGD, and even better than the user and item regularization on one dataset.

CLOSING REMARKS

In this Chapter, we extensively studied the Recommender System application. Modern RS application involves dataset of very large magnitude. Hence, it has emerged as a challenging task. While disucssing the approaches for RS, we noticed that Matrix factorization approaches have received a good reputation in the research community because of the success promised by these methods. However, when the size of dataset becomes very huge, it becomes infeasible to perform traditional matrix factorization methods in a single machine. Hence, distributed methods are required to tackle this problem. In this Chapter, we applied our asynchronous distributed framework to perform matrix factorization in a distributed manner. Additionally, we introduced an extra regularization term to incorporate the user and item similairity in the error function of SGD for matrix factorization. The use of neighbourhood information promised to give improvement in the performance of SGD method. Also, in the experiment section we demonstrated the benefits of using asynchronous framework over the synchronization based baselines.

(x i , y i ) ∈ d × {-1, +1}
where, i = 1, ..., n are the training examples, x i is the feature vector and y i is the corresponding label.

LINEAR VS NON-LINEAR MODELS

Given a training set (x i , y i ), binary classification methods construct the followin decision function [START_REF] Yuan | Recent advances of large-scale linear classification[END_REF]:

d(x) = w T φ(x) + b
Where, w is referred as the weight vector and b is an intercept known as bias. This decision function defines a separating plane which separates the instances corresponding to the two classes. Hence, based on the nature of this decision function the binary classification method can be divided into two types: linear classifiers and non-linear classifiers. As the name suggests, linear classifiers use a linear separating boundary, whereas it is non-linear in the case of non-linear classifiers. Non-linear classifiers map each of the training examples to a higher dimensional vector φ(x). In contrary, the linear classifiers use the original feature space.

Since, non-linear classifiers use more features, they are supposed to have better predictive perfomrance as compread to similar linear methods. However, in many applications and experiments [START_REF] Yuan | Recent advances of large-scale linear classification[END_REF], linear classifiers are shown to have similar accuracy as compared to the non-linear classifiers. Whereas, linear classifiers are far more efficient in terms of training and testing time. This makes them very useful for large-scale scenarios. Hence, in this work, we will focus on linear methods for binary classification.

BINARY LINEAR CLASSIFICATION METHODS

Linear binary classification involves the risk minimization of the following error function:

(w) = 1 n n i=1 i (w) + r(w) (6.1)
Where, r(w) is the regularization term and i (w) is the loss function associated with each example in the training set. The loss function in 6.1 penalizes the misclassified instances (x,y). Also, the type of loss function used helps to distinguish between different learning algorithms. Some of the commonly used loss functions are listed below:

i L1 (w) = max(0, 1 -y i w T x i ) (6.2) i L2 (w) = max(0, 1 -y i w T x i ) 2 (6.3) i LR (w) = log(1 + e -y i w T x i ) (6.4)
Here, 6.2 and 6.3 are used in L1-loss and L2-loss Support Vector Machine (SVM) [Boser et al., 1992, Cortes and[START_REF] Cortes | [END_REF] respectively, whereas 6.4 is used by the Logistic Regression algorithm [Cramer, 2002]. These algorithms are popularly used for binary classification. Both of them have advantage and disadvantages for different kind of datasets. The three loss functions in 6.2-6.4 are all convex and non-negative.

Hence, the popular optimization methods can be applied for their minimization. We will explore the different state of the art optimization schemes in the Related Work section (6.2).

RELATED WORK

One of the most popularly used optimization methods to minimize the loss function of the form 4.3 and 6.1 is full gradient descent (FG) method which dates back to [Cauchy, 1847]. FG method uses the iterations of the form:

w k+1 = w k -α k (w k ) = w k - α k n n i=1 i (w k ) (6.5)
The convergence of FG method is fast, it can be unappealing when n becomes significantly large. As the sum in Eq. ( 4.3) becomes very large, computing gradients of would be computationally very expensive. To overcome this issue, it is common to use Stochastic Gradient Descent (SGD) methods where instead of updating the current iterate using a full gradient, only one (or a few) randomly selected terms of the sum are considered [Bottou, 2010, Roux et al., 2012, Shalev-Shwartz and Zhang, 2013].

Updating with this randomly subsambled gradient instead of the true one leads to a variance-like error in the iteration that has to be mitigated, for instance by using decreasing stepsizes which is harmful in practice [Bottou, 2010, Johnson and[START_REF] Zhang | [END_REF]. Another, more performing, way to deal with this variance is to use variance reduced variants of SGD, such as SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF] or SAG/SAGA [START_REF] Roux | A stochastic gradient method with an exponential convergence _rate for finite training sets[END_REF], Defazio et al., 2014]. These methods incorporate incremental benefits of SGD whereas reducing the variance caused by random-sampling in SGD by occasionally computing full-gradients. This reduction in variance contributes to better convergence properties and the use of fixed stepsizes.

However, with the increasing size of the datasets, it has become impossible to store and process data in a single machine. In this case, the most common approach consists in partitioning the dataset into several machines, and to solve the optimization problem in a distributed manner [START_REF] Langford | Slow learners are fast[END_REF]. The majority of the distributed methods rely on a synchronization between the worker machines [START_REF] Shamir | Communicationefficient distributed optimization using an approximate newton-type method[END_REF], Boyd et al., 2011] where, the information from all the workers are gath-ered after every iteration and the parameters are synchronized. For these methods, the loading of machines play a central role in the convergence time of the whole system and in the extreme case, the slowest machine may become a bottleneck. To overcome this shortcoming, recent studies have considered asynchrony in the communication of the shared parameter between the machines [START_REF] Dean | Large scale distributed deep networks[END_REF], Zhang and Kwok, 2014, Zhang et al., 2015, Reddi et al., 2015, Huo and Huang, 2016]. Asynchronous algorithms can be applied either in shared-memory or distributed-memory environments. Shared memory algorithms, commonly referred as parallel distributed algorithms, are mainly devised for multi-core systems. All the cores in such system share the main memory, hence the parameter vector is usually kept in main memory and is accessible by all the processing units for making any updates. Some of the prominent parallel implementation of SGD or its variants are: Hogwild! [START_REF] Recht | Hogwild: A lockfree approach to parallelizing stochastic gradient descent[END_REF], Co-CoA [START_REF] Jaggi | Communication-efficient distributed dual coordinate ascent[END_REF], AsySVRG [START_REF] Zhao | Fast asynchronous parallel stochastic gradient descent: A lock-free approach with convergence guarantee[END_REF] and ASAGA [START_REF] Leblond | Asaga: Asynchronous parallel saga[END_REF]. Even though having promising theoretical/empirical results and ease of implementation these approaches are limited to multi-core systems.

On the other hand, distributed approaches introduce asynchrony in distributed memory environments. One popular architecture for distributed algorithms is parameter server (PS) implementation. The server keeps receiving delayed information from a subset of workers in each iteration, thus avoiding the full synchronization among all workers. One popular example of such architecture is downpour SGD [START_REF] Dean | Large scale distributed deep networks[END_REF]. Here, each worker reads the parameter vector from the server, computes the local gradient and pushes the updates to the server. Hence, the gradient updates for each mini-batch are sent back to the server, which updates the parameter vector for each received gradients. Following this architecture, recently variance reduced versions of SGD has been implemented in asynchronous distributed setting in [Zhang et al., 2015,Huo and[START_REF] Huo | [END_REF]. Even though both the methods communicate the gradients in an asynchronous fashion, they suffer from mainly two drawbacks. First after each mini-batch update the gradient should be communicated. So, if the size of dataset grows large the communication cost will become huge especially for a large number of workers. Secondly, even if the mini-batch updates are asynchronous, these algorithms synchronize after one complete pass over the data which is penalizing as in disparate distributed environments any sort of synchronization can lead to slower performance.

DISTRIBUTED SVRG ALGORITHM

In this section, we will analyze the SVRG method for binary classification. First, we will begin with the single machine SVRG algorihtm. Then, we will present our proposed asynchronous distributed version of the SVRG algorithm denoted as ADG BC .

SINGLE MACHINE SV RG

Single machine SVRG algorithm is presented in Algorithm 10. In this method, at each time (usually after one complete pass over the data), we keep a snapshot of estimated w, denoted as w. Then we maintain an average gradient over the whole data using the snapshot, w as:

µ = ∇ ( w) = 1 n n i=1 ∇ i ( w) (6.6)
For each single or mini-batch updates of inner iteration, parameter w is updated as:

w t ← w t-1 - γ |I t | i∈I t (∇ i (w t-1 ) -∇ i ( w) + µ) (6.7)
where γ is the learning rate.

This modification in update rule of SGD contributes to the reduction of variance of the algorithm near the convergence point and also leads to a linear convergence of the algorithm.

Parameters: Update frequency m, batch size B and learning rate γ The server node can also be used as a worker, updating the parameter on its local sub-part of the data. Here, one thing to note is that we compute the average gradient, µ in SVRG, only over the local data. The average gradient over local data using the parameter updated using the data on all machines gives a good approximation of the full average gradient over the whole dataset. This allows us to avoid the need for synchronization among the machines after one pass over the full data. We performed our experiments on three popular large-scale binary classification datasets:

Initialize: w ∈ d while s = 1, 2, .., S do w ← w ; w 0 ← w Compute µ = 1 n n i=1 ∇ i ( w) for t = 0, 1, 2.., m -1 do Randomly pick a mini-batch I t s.t. |I t | = B v t = 1 |I t | i∈I t (∇ i (w t ) -∇ i ( w) + µ) update w t+1 ← w t -γv t
Webspam, Epsilon and RCV. The various characteristics of the datasets are presented in Table 6.1. Note that Epsilon is fully dense while RCV is the sparsest dataset. The majority of distributed approaches consider the shared-memory scenario, where the parameter vector is kept in the shared memory, which can be updated by all the processors simultaneously [START_REF] Zhao | [END_REF]Li, 2016, Leblond et al., 2016]. But the focus of this paper is for shared-nothing scenario, where the disparate machines do not share memory. Unlike most of the approaches which rely on some sort of synchronization among the machines, we consider a totally asynchronous setting. To validate the asynchronous distributed algorithm described in previous section, we compare the following strategies:

• The proposed approach ADSVRG,

• Sync-SVRG, SVRG based method with synchronization of gradients after every mini-batch update.

• Async-SVRG: Distributed architecture proposed in [START_REF] Huo | Asynchronous stochastic gradient descent with variance reduction for non-convex optimization[END_REF],

which asynchronously communicate gradients after every mini-batch updates.

Since the asynchronous methods were quite sensitive to initial point, we performed a synchronized gradient step during the first pass over the data. This gave a stable start for all the algorithms.

Experimental Settings

We shall now describe the platform, as well as the tuning of the hyper-parameters and the evaluation measures used in our experiments.

1. Platform: Experiments were conducted in a platform with 7 servers. The code was implemented using a python module mpi4py using OpenMPI2 as the MPI library. Since the focus of the paper is for shared-nothing scenario, the disparate machines do not share memory. Three of the servers had Intel Xenon E5-2640

2.60 GHz processors with 32 cores and 256 GB memory each. Two others had Intel Xenon E5-2643 3.40 GHz processors with 24 cores and 128 GB memory each and the last two ones had have Intel Xeon E5-2407 2.20GHz processors with 4 cores and 48 GB memory each. Each core of a server here corresponds to a computing node or a machine that we considered in our analysis presented in the previous sections. Even though some of the servers have identical configuration, they were running different workloads on them making the configuration similar to a real scenario case.

Hyper-parameters:

In all the experiments, we used a fixed regularization rate, λ = 1 n , where n is the size of the dataset. The fixed learning rates were chosen from a set of values in range {10 -4 , 10 -3 , 10 -2 , 10 -1 } and the reported performance were the best obtained with one of those stepsizes. The mini-batch size for Webspam, Epsilon and RCV datasets were respectively fixed to 5, 10 and 20. Webspam and (b) Epsilon Datasets convergence, is lower than the two others, but the difference is not significant. Also it is to be noted that the difference in the convergence speed can become even larger if some of the machines are extremely overloaded, which is generally the case in the cluster environments.

Evaluation Measures

Communication Overhead

We also present the communication overhead incurred by each of the methods. The total communication cost for each algorithm is compared in terms of the total number

Methods

Webspam

Epsilon RCV where we pre-select a small subset of candidates to consider for the final prediction. This helped to make the prediction phase faster.

The performance of the proposed method was validated using popular datasets for text classification application. Also, we compared the results with a number of popular baseline methods. The analysis of the result shows the efficacy of the proposed algorithm. The comparison helped us to conclude that the proposed method is the best performance compromise considering various aspects of evaluation such as the total runtime, memory usage and predictive performance. Additionally, we presented a detailed theoretical analysis of the proposed model. Our reduction strategy brings inter-dependency between the pairs containing the same observation and its true class in the original training set. Thus, we derive new generalization bounds using local fractional Rademacher complexity showing that even with a shift in the original class distribution and also the inter-dependency between the pairs of example, the empirical risk minimization principle over the transformation of the sampled training set remains consistent.

In this part of thesis we showed effectiveness of the proposed double-sampled multi to binary reduction (DS-mRb) algorithm for large-class multiclass classification. This work opens several research directions. First, even though this algorithm works very well for text classification, its performance on other applications is still untested. This remains as an open question for potential future works. However, finding meaningful joint features can be a challenging task in many multiclass classification application.

Another future research direction would be to extend this approach to handle multilabel classification, where one example may belong to more than one classes at once.

In such problems, it will be interesting to incorporate the label dependencies in the algorithm.

In the second part of the thesis, we studied distributed approaches for performing ML optimization. In distributed computing, we partition the data across several machines and simultaneously perform the learning task. We consider the scenarios where the memory is not shared between the machines. In such setting, the main consideration is to minimize the communication between the machines and to avoid the bottleneck of synchronization between the machines. We introduced a framework which overcomes these two challenges. The proposed framework is based on asynchronous distributed optimization. We showed the effectiveness of the framework by considering two applications: matrix factorization for recommender system and large-scale binary classification.

In Chapter 4, we introduced distributed ML. We began by discussing different settings of distributed computing, their desired properties and popularly used distributed computing tools. Later, we formulated the problem structure that we considered throughout the second part of the thesis. Then, we presented our framework for asynchronous distributed machine learning based on averaging of parameters and showed the proof of convergence in this setting. This chapter introduced the proposed framework, which opened the door for utilizing it for ML applications.

In Chapter 5, we used the proposed asynchronous distributed framework for distributing matrix factorization in Recommender System application. We began with introducing the background of Recommender systems and popularly used methods in this domain. We focused on matrix factorization, since it is one of the most popularly used methods. Additionally, we introduced an extra regularization term to incorporate the user and item similarity in the error function of SGD for matrix factorization.

The use of neighbourhood information promised to give improvement in the performance of SGD method. Also, in the experiment section we demonstrated the benefits of using asynchronous framework over the synchronization based baselines.

Finally, in Chapter 6, we performed the distributed optimization of binary classification algorithm using the proposed asynchronous distributed framework. In this chapter, we started with the introduction and the types of binary classification methods. Then we discussed different loss functions popularly used for linear binary classification. We presented different optimization schemes for binary classification. Hence to tackle the problem of large-scale binary classification we used the proposed asynchronous distributed framework for linear binary classification algorithm. The results suggest improvement in the convergence time with the use of proposed framework.

We also demonstrated the scalability of the method for large-scale binary classifica-tion datasets. Hence, the proposed framework shows potential for binary classification application.

The results in this part of thesis give an indication for a potential research direction.

With the popularity of big data and distributed frameworks such as Spark and MPI, asynchronous communication is already an important consideration and will be very essential for applications in future. Because of time and infrastructure constraints we could not analyze various aspects of this research, which leads to several open questions and potential future extensions of this thesis. One interesting direction would be to test such framework in industrial scale applications with large clusters consisting of thousands of machines. However, in such scale the main challenge will be to control the communication frequency to utilize the network bandwidth optimally.

1 5 . 4

 154 Distribution of classes in DMOZ dataset . . . . . . . . . . . . . . . . . . . 1.2 Evolution of size of big data over years . . . . . . . . . . . . . . . . . . . . 1.3 Distributed and Parallel Computing . . . . . . . . . . . . . . . . . . . . . . 2.1 One-Vs-One Multiclass Classification [Fleury et al., 2013] . . . . . . . . 2.2 One-Vs-All Multiclass Classification . . . . . . . . . . . . . . . . . . . . . . 2.3 ECOC Multiclass Classification . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Research Challenges in Extreme Classification . . . . . . . . . . . . . . . 2.5 Long-tailed distribution on DMOZ dataset . . . . . . . . . . . . . . . . . . 3.1 A toy example depicting the transformation T (Eq. 3.7) applied to a training set of size m = 4 and K = 4. . . . . . . . . . . . . . . . . . . . . 3.2 The proper exact fractional cover of the set T ( ) obtained after transformation of the training set = {x 1 For the sake of clarity, the class labels of pairs of examples are omitted. The fractional chromatic number of T is in this case χ * T = 2. . . . . . . . . . . . . . . . . . . . . . . 3.3 MaF 1 of all methods with respect to the number of classes for DMOZ (top) and Wikipedia (down). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Training time in seconds of all methods with respect to the number of classes for Wikipedia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 The dependency graph = {1, . . . , 12} corresponding to the toy problem of Figure 3.1, where dependent nodes are connected with vertices in blue double-line. The exact proper fractional cover 1 , 2 and 3 is shown in dashed. The fractional chromatic number is in this case χ * ( ) = K -1 = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 3.6 Comparisons in Total (Train and Test) Time (min.), Total Memory usage (GB), and MaF 1 of the five best performing methods on LSHTC1, DMOZ, WIKI-Small, WIKI-50K and WIKI-100K datasets. . . . . . . . . . . . . . . . 4.1 Diagrams of the distributed synchronous (a) and asynchronous (b) frameworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 User-Rating Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Types of Recommender Systems . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Strata used by SSGD for a 3 × 3 blocking of V [Makari et al., 2015] . . Top: Test RMSE curves with respect to time for ADG MF , AD-ADMM, ASGD, and DSGD on NetFlix (left), and ML-10M (right) Datasets. Bottom: Total Convergence Time Vs. Number of Cores curves for ADG MF , ASGD, DSGD and AD-ADMM on the NetFlix (left), and ML-10M (right) Datasets. 6.1 The effect of varying batch size for broadcasting parameter for (a) Webspam and (b) Epsilon Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.2 Training Loss Vs Time Plot for (a) Webspam, (b) Epsilon and (c) RCV Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.3 Test Accuracy Vs Time Plot for (a) Webspam, (b) Epsilon and (c) RCV Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.4 Convergence Speedup Result for Epsilon Dataset . . . . . . . . . .

  ) and d 2 (x y ) are the distances of x to its two nearest neighbours in class y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Accuracy, MaF 1 of methods that could be trained with 7500 classes of DMOZ and Wikipedia collections. N c is the proportion of classes that are covered or in other words the fraction of classes that are identified in test set. Statistics are given over 50 random samples of training/test sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Characteristics of the datasets used in our experiments . . . . . . . . . . 3.5 Joint example/class representation for text classification, where t ∈ y ∩x are terms that are present in both the class y's mega-document and document x.

3. 6

 6 Hyper-parameters used in the final experiments . . . . . . . . . . . . . . 3.7 Comparison of the result of various baselines in terms of time, memory, accuracy, and macro F1-measure . . . . . . . . . . . . . . . . . . . . . . . . xvi 5.1 Characteristics of Datasets used in our experiments. | | and | | denote respectively the number of users and items. . . . . . . . . . . . . . . . . . 92 5.2 MAE and RMSE measures for different methods on MovieLens and Net-Flix datasets. Best results are shown in bold. . . . . . . . . . . . . . . . . 93 6.1 Characteristics of Datasets used in our experiments. . . . . . . . . . . . 103 6.2 Comparison of the communication overhead of all approaches on the three collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 .Figure 1 . 1 :

 1111 Figure 1.1. Such distribution is referred to as long-tailed distribution. Presence of such class imbalance in data distribution affects the predictive performance of algorithms in large-scale collections, since it is difficult to properly predict the rare classes (classes with few examples). Similarly, large-scale datasets involve high dimensionality and large sample size, which also makes learning a challenging task.

Figure 1 . 2 :

 12 Figure 1.2: Evolution of size of big data over years

Figure 1 . 3 :

 13 Figure 1.3: Distributed and Parallel Computing

  puting. In the proposed framework, data is partitioned and dispatched across several machines. Each machine performs gradient iterations in parallel over the local sub-part of data and updates local parameter simultaneously. Only after completing one complete pass over the local sub-part, the machines send the updated parameter to the master machine. The master machine integrates all received parameters and broadcasts it back to the worker machines, which use the updated parameter for a new pass over the data. In this way, we overcome the synchronization bottleneck as well as the communication cost is reduced since, we only exchange locally updated parameters as opposed to frequent exchange of gradients. Additionally, We present the convergence results for the proposed framework.2. We empirically present the effectiveness of the proposed framework for binary classication and distributed matrix factorization.1.3 THESIS ORGANIZATIONWe divide the whole thesis in two main parts: I Reduction of Multi-class Classification to Binary Classification: Containing Chapwe discuss in detail the reduction of multiclass classification problems to binary classification. To begin with, we introduce Multiclass classification in chapter 2.We mainly discuss the challenges of performing large-scale classification and present the state-or-art techniques. Then we discuss the ranking loss for multiclass classification and show the equivalence of this loss function to binary classification based loss. This gives main basis for our reduction algorithm. In Chapter 3, we formally present our two reduction algorithms. We also derive a generalization bound based on fractional Rademacher Complexity for the inter-dependent data. At the end, we present our empirical results in very large text classification collections of size up to 100000 classes.In Part II, we explore the distributed techniques for handling large scale data for Machine Learning. In this domain, we propose an asynchronous framework for performing distributed machine learning. We show the application of the proposed framework in two popular domains: distributed matrix factorization in Recommender Systems and distributed binary classification. We begin this section with Chapter 4, where we introduce the distributed machine learning and discuss various research works in the two applications that we consider. Then we present our first application, distributed matrix factorization in Chapter 5. In this chapter, we present the algorithm AsyDM which is an asynchronous algorithm for performing matrix factorization for larges scale Recommender Systems. In Chapter 6, we present another application of the asynchronous algorithm for performing binary classification in large scale binary classification datasets. Theoretical and empirical analysis as well as the comparison with popular state-of-art approaches are discusses in each section. to problems which comprise examples of the input vectors along with their corresponding target vectors[Bishop, 2006]. For such problems, the strategy is to learn a prediction function from the training data. The learned function is later used for prediction on unseen data. Problems where we aim to assign each input vector to one of finite set of categories are referred to as classification problems. Some of the popular examples of classification problems are: digit recognition, spam detection, document classification, image classification etc. Another kind of problems where the output consists of one or more continuous variables, are known as regression problems. Some examples of regression problems are: credit score prediction, house price prediction, stock price prediction over time, user rating prediction in Recommender Systems etc. Many supervised learning techniques aim at performing binary classification, where the number of possible classes is two. However, many real world classification problems involve the classification of an example to one or more classes from a predefined set of classes. Such problems are known as Multiclass classification problems.

  such as: One-per-class coding, Distributed output coding etc. • Decision Trees: Decision trees are widely used and powerful algorithm mainly for binary classification. The algorithm makes a tree shaped structure where the nodes are the features and the leafs represent the class labels. A new examples is classified to one of the classes by following the route from root node to the leaf node. At each node a test is performed for the features of the example.

Figure 2 . 1 :

 21 Figure 2.1: One-Vs-One Multiclass Classification[START_REF] Fleury | Improving supervised classification of activities of daily living using prior knowledge[END_REF]

Figure 2 . 2 :Figure 2 . 3 .

 2223 Figure 2.2: One-Vs-All Multiclass Classification

Figure 2 . 3 :

 23 Figure 2.3: ECOC Multiclass Classification

2 .

 2 Precision: measures the fraction of correctly identified positive examples out of the total positive predicted as positive. Mathematically, it is represented as: P r ecision = T P T P + F P 3. Recall: measures the total fraction of positive examples identified out of the total positive examples. Mathematically, it is represented as: Recall = T P T P + F N 4. F-Measure: (also known as F 1 measure)is the measure that combines both precision and recall as their harmonic mean. Mathematically, it is represented as: F -M easur e = 2. P r ecision * Recall P r ecision + Recall True class Predicted as positive Predicted as

2

 2 Effectiveness of a classifier to identify class labels if calculated from sums of per-text decisions F scor e µ (β 2 +1)P r ecision µ Recall µ β 2 P r ecision µ +Recall µ +1)P r ecision M Recall M β 2 P r ecision M +Recall M Harmonic mean of macro averaged precision and macro averaged recall

Figure 3 . 1 ,

 31 Figure 3.1, presents a toy example of reduction of multiclass classification to binary classification. The example consists of an original multiclass dataset denoted as = x 1 , x 2 , x 3 , x 4 , which consists of 4 examples each of them belong to four classes;= y 1 , y 2 , y 3 , y 4 respectively. We apply our binary transformation function denoted as T to this multiclass dataset and obtain the binary reduced dataset denoted as T (S).As can be seen in the figure, new examples in the transformed set are created by the subtraction of dyadic representations of each example with its true class and all other class labels in the output space following the transformation function in 3.7. We will

Figure 3 . 1 :

 31 Figure 3.1: A toy example depicting the transformation T (Eq. 3.7) applied to a training set of size m = 4 and K = 4.

Figure 3 . 2 :

 32 Figure 3.2: The proper exact fractional cover of the set T ( ) obtained after transformation of the training set = {x 1 1 , x 2 2 , x 3 3 }. For the sake of clarity, the class labels of pairs of examples are omitted. The fractional chromatic number of T is in this case

Theorem 3 . 1 .

 31 Let = (x y i i ) m i=1 ∈ ( × ) m be a dataset of m examples drawn i.i.d. according to a probability distribution over × and T ( ) = ((Z i , ỹi )) n i=1 ∈ ( × {-1, 1}) n the transformed set obtained with the transformation function T defined above.

Figure 3 . 3 :Figure 3 . 4 :

 3334 Figure 3.3: MaF 1 of all methods with respect to the number of classes for DMOZ (top) and Wikipedia (down).

  Reduction Phase: If we denote the number of examples in the training set as m and the total number of classes is K, one complete reduction process refers to m × K transformations of all (example, class) pairs from original feature space to low-dimensional feature set and m × (K -1) subtractions of low-dimensional feature representations as can be seen from Algorithm 1. But since large-scale applications involve both higher number of training examples and class size, the computational cost for these operations can become huge. Also, the number of examples in the binary reduced dataset is m × K. Similarly the memory required to store such huge amount of reduced examples becomes quite high.

3. 4

 4 DOUBLE SAMPLED MULTI TO BINARY REDUC-TION ALGORITHM (DS-mRb) 3.4.1 ALGORITHM DESCRIPTION First, we will introduce our proposed DS-mRb algorithm by detailing its two main characteristics: (i) an aggressive, doubly sampled, multi-class to binary reduction;

1 . 2 .

 12 For each class k ∈ {1, . . . , K}, draw randomly a set π k of examples from of that class with probability π k , and let π = For each example x y in π , draw uniformly κ adversarial classes in \{ y}. After this double sampling, we construct our transformed problem as in Eq. (3.7), leading to a set T κ (S µ ) of size µκK. Algorithm 3 presents in pseudocode the µ, κ-double subsampled reduction of the multiclass problem. This aggressive double sampling practically leads to dramatic improvements in terms of memory consumption, computational complexity, and a higher multiclass prediction accurracy. Majority of large-scale multiclass classification datasets exhibit a long-tailed distribution [Babbar et al., 2014b], which implies that most of the classes contain very few examples, especially when the number of classes is large. In order not to miss out those rare classes during sampling, we first sample randomly a few training examples from each class. This also avoids having a large number of very similar examples in one class leading to minimal performance improvement.

4 :

 4 For a new observation x, the candidate set denoted as σ contains the σ nearest classes for the test example, based on the centroid distance of test example vector with the class centroids. Class centroids are computed by taking mean of all the examples of that particular class. Candidate set is selected by computing the cosine distance between a test example vector and each class centroid vectors and selecting the σ nearest ones. Note that class centroid may already have been computed in the preliminary feature representation and thus represent no additional computation. Algorithm 4 presents the pseudocode of prediction with candidate selection. Input: Unlabeled test set = (x i ) do Select σ candidate set of σ nearest-centroid classes for x P ← P ∪ argmax k∈ σ 〈w, φ(x k )〉 end return predicted classes P Algorithm Prediction with Candidate Selection Algorithm 3.4.2 GENERALIZATION BOUND ANALYSIS USING LOCAL FRAC-TIONAL RADEMACHER COMPLEXITY In this work, we derive a new generalization bounds based on Local Rademacher Complexities introduced in [Ralaivola and Amini, 2015] that implies second-order (i.e.

  = k∈[J] ω k and the minimum weight χ * ( ) = min ∈ ( ) W ( ) over the set ( ) of all exact proper fractional covers of is the fractional chromatic number of .

Figure 3 . 5 :

 35 Figure 3.5: The dependency graph = {1, . . . , 12} corresponding to the toy problem of Figure 3.1, where dependent nodes are connected with vertices in blue double-line. The exact proper fractional cover 1 , 2 and 3 is shown in dashed. The fractional chromatic number is in this case χ * ( ) = K -1 = 3.

Theorem 3 . 2 .

 32 with respect to its empirical error RT( ) (h) over a transformed training set, T ( ), and the fractional Rademacher complexity, R T ( ) ( ), states as : Let = (xy i i ) m i=1 ∈ ( × ) m bea dataset of m examples drawn i.i.d. according to a probability distribution over × and T ( ) = ((Z i , ỹi )) N i=1 the transformed set obtained as in Eq. (3.7). Then for any 1 > δ > 0 and 0/1 loss : {-1, +1} × → [0, 1], with probability at least (1 -δ) the following generalization bound holds for all h ∈ r :

Lemma 4 .

 4 3.12) Let below be a probability measure over × . It can be decomposed into a direct product of = × | with marginal distribution over and conditional | over . Let ¯ = ¯ × | be a measure properly renormalized in accordance with the algorithm, e.g. y∼ ¯ [ y(x) = y] = π y /π, where π = K i= y π y . Let = (x y i i ) m i=1 ∈ ( × ) m be a dataset of m examples drawn i.i.d. according to a probability measure = × | over × and T ( ) = ((Z i , ỹi )) N i=1 the transformed set obtained with the transformation function T defined in Eq. (3.7). Let

  be a measure over × used in the (π, κ)-mRb algorithm. With the class of functions = {g : × → } and= {h : h(φ(x y ), φ(x y )) = g(x y ) -g(x y), g ∈ } for any δ > 0 for all h ∈ with probability at least 1 -δ we have :R(h) ≤ α x y ∼ ¯ RT(x y ) (h) + 2α log 2K/δ β(m -1) + 7β log 2K/δ 3(m -1) .holds the for all h ∈ , where : {-1, +1} × → [0, 1] is the 0/1 loss, and α = max y: 1≤ y≤K πη y /π y , and β = max y: 1≤ y≤K π/π y , and η y > 0 is the proportion the class y in the training set .

  a dataset of m examples drawn i.i.d. according to a probability distribution over × and T κ ( ) = ((Z i , ỹi )) mκ i=1 the transformed set obtained as in Eq. (3.7) and draw κ adversarial samples by algorithm DS-mRb. With the class of functions = {g : × → } and = {h : h(φ(x y ), φ(x y )) = g(x y )g(x y

  a dataset of m examples drawn i.i.d. according to a probability measure = × | over × and T ( ) the transformed set obtained with the transformation function T defined in Eq. (3.7). Let π ∈ ( × ) n and T κ ( π ), |T κ ( π )| = M be a training sets derived from and T ( ) respectively using the algorithm DS-mRb with parameters π 1 , . . . , π K and κ. With the class of functions = {g : × → } and = {h : h(φ(x y ), φ(x y )) = g(x y ) -g(x y ), g ∈ } we have the following bound on the expected risk of the classifier :

Figure 3 . 6 :

 36 Figure 3.6: Comparisons in Total (Train and Test) Time (min.), Total Memory usage (GB), and MaF 1 of the five best performing methods on LSHTC1, DMOZ, WIKI-Small, WIKI-50K and WIKI-100K datasets.

2 .

 2 MapReduce: On the other hand, MapReduce is the programming paradigm used by Hadoop framework, popularly referred as the big data processing framework. Hadoop clusters comprises of thousands of commodity machines and a distributed file system called HDFS. MapReduce organizes the application as Map and Reduce pairs[START_REF] Kang | Performance comparison of openmp, mpi, and mapreduce in practical problems[END_REF]. Normally the data read and write operations are done with HDFS. In such frameworks, programmers do not have to worry about data partitioning, process creation and synchronization. So, the main advantage of using MapReduce paradigm is its ease of use, as most of the tasks are performed behind the scene by the framework itself. Moreover, these frameworks have a better fault tolerance mechanism. However, in contrast to MPI, the downsides of MapReduce paradigm is the lack of flexibility for programmers. One recent framework, following MapReduce paradigm and running on top of Hadoop clusters is Spark. It is an open source processing engine adopted by enterprises across wide range of industries. The main advantages of using Spark over existing Hadoop MapReduce is their speed and advanced ability of fault tolerance. As opposed to existing Hadoop frameworks, Spark uses an inmemory model for computation. Hence, they are several magnitude faster than

Figure 4 . 1 :

 41 Figure 4.1: Diagrams of the distributed synchronous (a) and asynchronous (b) frameworks.

  RS) represent an active area of research in data mining due

  of the popular examples of use of RS in the industry are: movie recommendation by Netflix, song recommendation by Pandora and spotify, product recommendation by Amazon, job recommendation by LinkedIn, content recommendation by Facebook, quora etc.

Figure 5 . 1 :Figure 5 . 2 :

 5152 Figure 5.1: User-Rating Matrix

  blocks and SGD is run on individual blocks on distinct machines. From the decomposition R = PQ , one can see that if the rating matrix is divided by row-blocks, Rb = P b Q , that is; the block b of R depends only on the block b of P then, the block-

Figure 5 . 3 :

 53 Figure 5.3: Strata used by SSGD for a 3 × 3 blocking of V [[START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]

Algorithm 8 :

 8 ADG MF worker step in the computing machine j ∈ {1, . . . , m} • Master Step: Master machine performs the task of collecting the received updates from the workers and aggregating the received matrices. This aggregation can be performed in a timely manner depending on the application. In our experiments, we used master as a worker as well and performed the aggregation after each epoch on master. Hence, after each epoch the master checks for received updates from the worker machines and it averages the received updates. Soon after averaging it broadcasts the aggregated parameter to the workers so that they can use it immediately in their next epoch. The master step is shown in Algorithm 9. Initialize: machines M and Receive matrix i from the subset of workers (m ⊂ M and i ∈ m) ; ADG MF master step in the master machine

Figure 5 . 4 :

 54 Figure 5.4: Top: Test RMSE curves with respect to time for ADG MF , AD-ADMM, ASGD, and DSGD on NetFlix (left), and ML-10M (right) Datasets. Bottom: Total Convergence Time Vs. Number of Cores curves for ADG MF , ASGD, DSGD and AD-ADMM on the NetFlix (left), and ML-10M (right) Datasets.

  to supervised learning problem involving the classification of an example to one of the two class labels. Majority of real-time applications involve binary classification or can be modeled as a binary classification problem. Some of the popular examples of binary classification are: spam detection, cancer detection, deciding whether or not to show an item or add to a user etc. A binary dataset is denoted as:

  end w ← w m end Algorithm 10: Single Machine SVRG Algorithm 6.3.2 ADG BC ALGORITHMIn this section, we present our proposed asynchronous distributed SVRG algorithm, using the asynchronous framework discussed in previous section. The distributed memory algorithm in the master node and the worker nodes are shown in Algorithms 11 and 12. Each machine perform parameter update on their local data and after each iteration the worker machines send the updated parameter to the server node which directly responds by sending the averaged common parameter using the last gathered updates. In this way, all the machines have an overall view of the parameter updates from whole data, while only working with the local data.

  Initialize: Iteration k, machines M and w Receive w i from the subset of workers (m ⊂ M and i ∈ m) ; ADG BC master step in the master machine Input: Maximum number of iterations T , batch size B and learning rate γ Initialize: * Receive parameter w ∈ d from the master, or use the last parameter estimation happened before a new reception ; * w 0 ← w; * Compute μj ← ∇ j ( w) ;for t = 0, .., T -1 doRandomly pick a mini-batch I t j of size B in the subpart of the data stored in machine j;Update w t+1 ← w tγ |I t j | (x i , y i )∈I t j (∇ (w t , x i , y i ) -∇ ( w, x i , y i ) + µ j );end w ← w T and send w T to the master.Algorithm 12: ADG BC local step in the computing machines j ∈ {1, . . . , m}6.4 EXPERIMENTAL RESULTSWe conducted a number of experiments aimed at showing the behaviour of the proposed ADG BC algorithm in learning efficient classification functions optimizing the 2regularized logistic regression surrogate. Specifically, we study the convergence and the communication overhead of the proposed algorithm by comparing it with stateof-the-art distributed approaches.

:

  Convergence result was evaluated in terms of minimization of objective function over time. The communication overhead incurred by n/10000 n/1000 n/100 n

Figure 6 . 1 :

 61 Figure 6.1: The effect of varying batch size for broadcasting parameter for (a)

  collections of communication calls (send, receive, broadcast, gather), as well as the time spent in those calls. Since for Sync-SVRG and Async-SVRG methods the convergence is very slow near the tail, we compare the communication cost till the iteration when all methods achieve the same minimization of the objective function. Table6.2 shows the detailed results obtained for each algorithm on all datasets. It can be observed that the ADSV RG incurs the minimum communication overhead as the number of communication between the machines is very low. Most of the calls shown for ADSV RG are made during the first epoch where the gradients are synchronized. Whereas Sync-SVRG and Async-SVRG methods have to communicate large number of times in order to broadcast their local gradients to the master and receive the updated parameters from the master machine. Since Sync-SVRG is totally synchronous, the communication calls are blocking in nature and hence considerably slow. Whereas for Async-SVRG and ADSV RG the communication calls are mostly non-blocking and hence return immediately.6.4.2.4 Speedup Result with Increasing Number of WorkersFinally, we evaluate the scalability of the proposed framework with respect to the increasing number of worker machines. In this experiment, we vary the number of workers from 5 to 25, each time increasing the number of workers by 5. Figure6.4 illustrates the evolution of the loss function of ADSV RG on the training set (a) as well as the test accuracy (b) with respect to time (in seconds) on the Epsilon collection.

Figure 6 . 4 (Figure 6 . 2 :Figure 6 . 3 :

 646263 Figure6.4 (c) also depicts the speedup in convergence time with respect to the number of workers. In the ideal case, shown in red, when the number of workers double, the convergence time is divided by two; and hence the speedup is linear. From this figure, it comes out that as the number of workers increases the ADSV RG algorithm is able to achieve a near linear speedup, which is mainly due to the fact that, it relies on

Figure 6 . 4 :

 64 Figure 6.4: Convergence Speedup Result for Epsilon Dataset

  2.1 Confusion matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Popular evaluation measures for multiclass classification . . . . . . . . .

3.1 Characteristics of the datasets used in our experiments . . . . . . . . . . 3.2 Let x t represent the term frequency of term t in document x, and the set of distinct terms within , then y t = x∈ y x t , | y| = t∈ y t , t = x∈ x t , l = t∈ t . I t is the inverse document frequency of term t, d 1 (x y

Table 2 .

 2

1: Confusion matrix Table

2

.2 presents the popularly used evaluation measures for multiclass classification

[START_REF] Sokolova | A systematic analysis of performance measures for classification tasks[END_REF]

. For each class C i , the assessment is denoted as t p i , f n i , t n i and f p i . Here, one thing to note is that most of the measures are assessed in two ways: average of the same measures calculated individually for each class (macro-averaging denoted with index M), or the computing the cumulative sum of tp, fp, tn, fn and then calculating the measures (micro averaging denoted as µ subscripts). Macro averaging treats each class equally whereas micro averaging favours the bigger classes. Hence, macro averaging is considered as a superior evaluation measure as compared to average accuracy and micro-averaging in multiclass classification

Table 2 .

 2 2: Popular evaluation measures for multiclass classification2.5 CLOSING REMARKSIn this chapter, we discussed multiclass classification in detail. We begin with the introduction to multiclass classification. In Section 2.2, we presented various state-ofthe-art algorithms to solve multiclass classification problems. Then in section 2.3, we discussed various challenges associated with it. Later in section 2.4, we introduced a popular application involving multiclass classification, which is also the application of choice to validate our proposed methods. In that section, we discussed various steps of text classification such as text preprocessing, feature representations and the popular evaluation measures. Now, with enough background in multiclass classification and the text classification application, we will present our proposed multiclass to binary reduction technique in next chapter.

	3 REDUCTION TO BINARY CLASSIFICATION
	3.1 RANKING LOSS FOR MULTICLASS CLASSIFICA-

TION

We consider monolabel multiclass classification problems defined on a joint space × where ⊆ d is the input space and = {1, . . . , K} the output space, made of K class labels. Elements of × are denoted as x y = (x, y). Furthermore, we assume the training set = (x

Table 3 .

 3 .1.

	# of		DMOZ			WIKI
	classes	Train	Test	Feature	Train	Test	Feature
		size	size	dimension	size	size	dimension
	100	985	258	23382	1481	326	11841
	500	4874	1279	66541	7995	1623	32736
	1000	9479	2478	102745	15615 3288	47520
	2000	18378	4830	177108	30447 6509	74912
	3000	27729	7287	202775	45340 9569	85585
	4000	37634	9886	264216	63375 13422	113074
	5000	47281 12426	271205	76904 16268	114049
	7500 103794 26886	371634	91283 20025	122847

1: Characteristics of the datasets used in our experiments 3.3.3.2 Feature Representation:

Table 3 . 2

 32

				ln(1 + y t )				2.		ln(1 +	l	)	3.	I t
		y∩x									t∈ y∩x		t	t∈ y∩x
	4.	t∈ y∩x	y t | y|	.I t						5.	t∈ y∩x	ln(1 +	y t | y|	)	6.	t∈ y∩x	ln(1 +	y t | y|	.I t )
	7.	t∈ y∩x	ln(1 +	y t | y|	.	l	t	)	8.	t∈ y∩x	1		9. d 1 (x y )
	10. d 2 (x y )

: Let x t represent the term frequency of term t in document x, and the set of distinct terms within , then y t = x∈ y x t , | y| = t∈ y t , t = x∈ x t , l = t∈ t . I t is the inverse document frequency of term t, d 1 (x y ) and d 2 (x y ) are the distances of

Table 3 .

 3 3: Accuracy, MaF 1 of methods that could be trained with 7500 classes of DMOZ

		DMOZ-7500		Wikipedia-7500
	Accuracy	MaF 1	N c	Accuracy	MaF 1	N c
	mRb 0.499 ↓	±.011	0.352 ± .009 0.495	0.467 ↓	±.023	0.378 ± .012 0.551
	OVA 0.549±.036 0.282 ↓	±.018	0.379	0.484±.029 0.348 ↓	±.017	0.489
	LogT 0.311 ↓	±.034	0.096 ↓	±.029	0.194	0.231 ↓	±.035	0.151 ↓	±.021	0.287

and Wikipedia collections. N c is the proportion of classes that are covered or in other words the fraction of classes that are identified in test set. Statistics are given over 50 random samples of training/test sets.

Table 3 .

 3 5: Joint example/class representation for text classification, where t ∈ y ∩ x are terms that are present in both the class y's mega-document and document x.

	Denote by	the set of distinct terms within then x

t is the frequency of term t in x, y t = x∈ y x t , | y| = t∈ y t , F t = x∈ x t , l = t∈ t . Finally, I t is the inverse document frequency of term t, len( y) is the length (number of terms) of documents in class y, and av g(len( y)) is the average of document lengths for all the classes

Table 3 .

 3

6: Hyper-parameters used in the final experiments 3.4.3.5 Comparison Result:

Table 3 .

 3

	complete the training. Furthermore, on this data set and the second largest Wikipedia
	collection (WIKI-50K and WIKI-100K) the proposed approach is highly competitive in
	terms of Time, Total Memory and both performance measures comparatively to all the
	other approaches. These results suggest that the method least affected by long-tailed
	class distributions is DS-mRb, mainly because of two reasons: first, the sampling tends
	to make the training set balanced and second, the reduced binary dataset contains
	similar number of positive and negative examples. Hence, for the proposed approach,

7: Comparison of the result of various baselines in terms of time, memory, accuracy, and macro F1-measure ever, standard OVA and M-SVM have a complexity that grows linearly with K thus the total runtime and memory usage explodes on those datasets, making them impossible to learn. For instance, on Wiki large dataset sample of 100K classes, the memory consumption of both approaches exceeds the Terabyte and they take several days to

Table 5 .

 5 1: Characteristics of Datasets used in our experiments. | | and | | denote respectively the number of users and items.

	Dataset	| |	| |	γ	λ	K training size test size sparsity
	ML-10M	71567 10681 0.005 0.05 100 9301274 698780 98.7 %
	NetFlix (NF) 480189 17770 0.005 0.05 40 99072112 1408395 99.8 %
	NF-Subset	28978 1821 0.005 0.05 40 3255352 100478 93.7 %
	2.

Table 5 .

 5 2: MAE and RMSE measures for different methods on MovieLens and NetFlix datasets. Best results are shown in bold.First, we compare the results between the traditional SGD method and the proposed Modified SGD with Similarity Based Regularization. The difference here is solely on the objective function that is minimized (Pbs. (

	Dataset		SGD	Similarity Based Regularization Similar Users and Items Similar Users Only
		MAE	RMSE	MAE	RMSE	MAE	RMSE
	ML-100K	ua 0.7490 0.9478 0.7390 ub 0.7619 0.9660 0.7555	0.9332 0.9564	0.7404 0.7540	0.9359 0.9590
	ML-1M	ra rb 0.6973 0.8861 0.6928 0.7324 0.9706 0.7208	0.9517 0.8787	0.7188 0.9487 0.6946 0.8799
	ML-10M	rb 0.6523 0.8415 0.6488	0.8384	0.6512	0.8402
	NF-Subset NA 0.6498 0.8287 0.6469	0.8256	0.6477	0.8267

  1

Table 6 .

 6 1: Characteristics of Datasets used in our experiments.

	Dataset	n	d	#nonzer os
	Epsilon	500000 2000 10 9
	Webspam Unigram 350000 253	29,796,333
	RCV	697641 47236 51,055,210
	6.4

.1.2 Baselines

  Table 6.2: Comparison of the communication overhead of all approaches on the three

		N c	time (s)	N c	time (s)	N c	time (s)
	Sync-SVRG 336021 635.44	108009	589.9	83711 4756.25
	Async-SVRG 839831 42.13	108000 110.03	30701 733.47
	ADSV RG	33611	14.93	12004	29.6	8380 631.92

www.facebook.com

http://www.wikipedia.org

https://www.flickr.com

https://www.youtube.com/

https://en.wikipedia.org/wiki/Wikipedia:Size_of_Wikipedia

http://www.unece.org

http://lshtc.iit.demokritos.gr

http://bioasq.org/

http://lshtc.iit.demokritos.gr/

http://manikvarma.org/events/XC13/index.html

http://www.dmoz.org/

www.wikipedia.org

http://www.nltk.org

http://scikit-learn.org

https://spark.apache.org/

https://www.open-mpi.org/

https://www.mpich.org/

https://en.wikipedia.org/wiki/Netflix_Prize

http://grouplens.org/datasets/movielens/

http://www.netflixprize.com/

https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/

https://www.open-mpi.org/

Acknowledgments

The essence of the last theorem is improvement conditional error within classes with low prior probability, which in its turn improves macro MaF 1 -measure of the classifier.

CLOSING REMARKS

In this chapter, we introduced distributed machine learning. We began by introducing distributed algorithms in two different kinds of settings: shared-memory and sharednothing. Then, we discussed the mainly desired properties of distributed frameworks followed by popularly used frameworks. In Section 4.2, we formulated the problem, which we are going to use throughout this part of the thesis. In Section 4.3, we presented our framework for asynchronous distributed machine learning based on averaging of parameters and showed the proof of convergence in this setting. Now, in the next two chapters, we will use the proposed asynchronous distributed frameworks for the optimization in two different applications: matrix factorization for recommender systems and large-scale binary classification.

EVALUATION OF CONVERGENCE TIME

We begin our experiments by comparing the evolution of the loss function of Eq. (5.3) with respect to time until convergence. The convergence points are shown as names of the algorithms vertically (we stopped ASGD after 20 hours on the NF dataset). Figure 5.4 (top) depicts this evolution for ML-10M and NF datasets using 10 and 15 cores respectively. Synchronization based approaches (ASGD and DSGD) aggregate all the information at each epoch and thus begin to converge more sharply at the beginning.

However, with these approaches, when the fastest machines finish their computations, they have to wait for slower machines; thus, they require much more time to converge than the asynchronous methods (AD-ADMM and ADG MF ). Finally, it comes out that ADG MF converges faster than the other algorithms on both datasets. This is mainly due to the fact that ADG MF does not obey to any delay mechanism as in AD-ADMM for instance.

COMPUTATION AND COMMUNICATION TRADE-OFF

We performed another set of experiments aimed at measuring the effect of number of cores on performance of the proposed approach and the baselines. Figure 5.4 (bottom) depicts this effect by showing the evolution of time per epoch of the SGD method used in ADG MF , ASGD, DSGD and AD-ADMM with respect to increasing number of machines.

From these experiments, it comes out that for all approaches the time per epoch of the method decreases as the number of machines increases.

But after a certain number of machines (10 in both experiments), the time per epoch of some approaches begin to be affected as the communication cost takes over the computation time. The approach that is the most affected by this is DSGD, as synchronizations in this case are done after each sub-epoch. We can also see that even though the per epoch speedup is best for ASGD, it requires a much higher number of epochs to converge as compared to ADG MF and DSGD.

each algorithm in the network as well as the communication time are shown in terms of the total number of send/receive calls.

RESULTS

We performed experiments to assess the effect of varying broadcast frequency on the performance of asynchronous methods. We were then interested in the convergence time as well as the communication overhead and the effect of increasing the number of workers.

Effect of Varying Broadcast Frequency

We chose varying batch sizes after which the parameter vectors were broadcasted in each worker machines. The effect of varying batch size for broadcast on the minimization of objective function on training data for Webspam and Epsilon datasets are shown in Figure 6.1. As it can be observed, the broadcasting of the parameter vectors has in general a negative effect on the performance of the algorithm. In Figure 6.1, we can notice that when the parameter was broadcasted after 1/10000 or 1/1000'th pass over the local data, the minimization of the objective function is not very good, whereas broadcasting after a larger pass over the data improves the minimization up to some point when the parameters pooling do not occur often enough. This gives a good motivation for our approach of broadcasting parameter vectors only after updating the parameter vector over one pass of the local data. The objective function is minimized considerably faster for ADSV RG than the other two methods. It can be seen that this behavior becomes more noticeable for larger datasets. For example on the RCV collection, ADSV RG converges three times faster than the other methods. As an effect the test performance reached by ADSV RG, at its very low communication between the workers which is is also shown in Table 6.2. On the other hand, as the number of workers increases the performance of the algorithm slightly deteriorates.

Evaluation of Convergence Time

CLOSING REMARKS

In this chapter, we analyzed the binary classification problem. We started with the introduction and the types of binary classification methods. Then we discussed the different optimization functions for linear binary classification. In the related work section we summarized the different ways of perfoming optimization for linear methods. Hence to tackle the problem of large-scale binary classification we used the proposed asynchronous distributed framework for linear binary classification algorithm.

The results suggest improvement in the convergence time with the use of proposed framework. We also demonstrated the scalability of the method for large-scale binary classification datasets. Hence, the proposed framework shows potential for binary classification application.

CONCLUSION

The goal of this thesis was to explore ML algorithms for large-scale data and devise efficient algorithms. To achieve this objective we studied this problem from two different perspectives. First, we considered the problem of large-scale multiclass classification.

Then we analyzed the distributed algorithms for ML. In both the areas we discussed the challenges of handling large-scale data and proposed efficient algorithms to solve them. We also showed a detailed theoretical and empirical analysis of the proposed algorithms to validate the claims. Analysis of both the problems constitute the two parts of this thesis.

In the first part of the thesis, we study the multiclass classification problem. We proposed an algorithm for the reduction of multiclass classification to a binary classification problem. In Chapter 2, we began with the introduction to multiclass classification. Then, we presented various state-of-the-art algorithms to solve multiclass classification problems. We noticed that there is no single method which is superior to every other methods. Each of the methods has their advantages and drawbacks. We also discussed about the popular challenges associated with multiclass classification, typically for large-class scenario.

To solve the discussed challenges, we introduced our first reduction algorithm re-