Recent progress in the development of techniques to optimize large-scale classification problems has extended the use of multi-class classification. Specifically the use of multi-class classification algorithms when the dataset is to large to fit into limited memory available of most computers. The most prominent algorithms used today solve the multi-class classification problem through an optimization approach based on coordinate decent. Two of the most recognized algorithms, Vowpal Wabbit and LIBLINEAR LibSVM have emerged as the most consistent options when solving for a multi-class problems. This paper proposes an analysis of these methods and tests the efficiency and performance of each algorithm. The results are recorded and comparisons are made. After analyzing the results, the conclusion made is that the Vowpal Wabbit algorithm is best suited for solving large-scale multi-class classification problems when computer memory is constrained.
Big Data has affected the way statistical analysis is being
conducted. Many real-world datasets contain hundreds or
thousands of variables of interest which can contain
hundreds of thousand or millions of records. Time spent
on reading/writing between memory and disk becomes
the bottleneck, rendering most algorithms inefficient
In the past, classification models have been shown to
handle large amounts of data well, and several
optimization techniques have been applied to efficiently
train data intensive models
Recent progress has been made in the development of
techniques to optimize over memory constrained systems,
including binary classification. It is a well studied special
case of the classification problem that provides the
foundation for multi-class problem solvers. Statistical
properties of binary classifiers, such as consistency, have
been investigated in a variety of settings. Most
machinelearning algorithms are originally developed for binary
decision problems, and extended to handle multi-class
problems
The goal of this paper is to study the existing multiclass classification methods and provide a noteworthy comparison. In order to provide a thorough and comprehensive comparison, classification tests were run multiple times over contrasting datasets. The paper is organized in the following manner. Section 2 contains background information. Section 3 presents related work. Our approach is in section 4, followed by experiments in section 5. Conclusions follow and finally work cited.
The principles of Multi-class classification are founded
upon the same principles of binary classification. Each
case involves assigning a class label for each instance
present. Given a training data set of the form (xi , yi),
where xi ∈ Rn is the ith example and yi ∈ {1, . . . , K} is
the ith class label, we aim at finding a learning model H
such that H(xi) = yi for new unseen examples
Several algorithms have been proposed to solve the binary problem. Some of these can be easily extended to the multi-class case, and some that involve high levels of computation. In contrast to traditional data classification where each instance is assigned to only one label, instances used in multi-class classification may be simultaneously relevant to several labels. For example: in text categorization, one document can belong to multiple topics.
Existing approaches to handle Large Scale multi-class
classification can be categorized into two types. The first
approach solves problems through a block minimization
scheme. The second approach considers online learning
algorithms
Optimization through block minimization has been used
in the past to efficiently deal with data to large too fit into
memory. One of the most prominent learning algorithms
associated with block minimization is Support Vector
Machine (SVM) algorithm. Proposed by Cortes and
Vapnik in 1995, the algorithm has since grown into one of
the most widely used learning algorithm in the world
The framework for an SVM is modified to solve for
classification problems in the event limited memory is
available. The process entails using an optimization
technique based on block minimization. Where the term
“block” refers to partitions of the dataset that can be read
through the memory available. The size and content of
each block varies from approach to approach.
PérezCruz, Figueiras, and Artes (2004) propose the use of
“double chunking.” Where data is partitioned into both
“large chunks” and “small chunks.” Another approach
described by
Algorithm 1 A block minimization framework for Dual SVM 1. Split {1, . . . , l} to B1 , . . . , Bm and store data into m partitions accordingly. 2. Set initial w 3. For j = 1, . . . , m (inner iterations)
For K = 1, 2, . . . (outer iterations) 3.1. Read xr , ∀r ∈ Bj from disk 3.2 Approximately solve the sub-problem (1) 3.3 Update w by (2)
Here, {B1 , . . . , Bm } are sequential partitions of all
data indices {1, . . . , l}. The size of the blocks are
determined by the known memory constraints. Each
instance is read and randomly assigned a block.
Algorithm 2 explains the process for data splitting.
Optimization over a single block is identified as the inner
iteration, whereas the m steps of going over all blocks is
deemed an outer iteration
Algorithm 2 Framework for block splitting 1. Decide m and create m empty files 2. For i = 1, …. 2.1 Convert xi to a binary format xi . 2.2 Randomly choose number j {1,...,m}. 2.3 append xi into the end of the jth file.
In order to optimize through block minimization only
the dual form of SVM must be used. By examining the
dual form of the optimization problem we are able to
write the entire algorithm in terms of only inner products
between input feature vectors. Updates to the weight
vector w, which corresponds to the entire data set treating
instances uniformly prevent the primal for of SVM to be
used
The sub-problem is solved in the inner iteration step, and the solution is then used to update w. The solution uses only instances that belong to block Bj. The solution to the sub-problem is presented below in (1).
l w = ∑ αiyixi i=1 (1)
The iteration round is then complete after w is updated. To update w, if dBj is an optimal solution for the subproblem: w←w + ∑ dr yrxr r∈Bj (2)
The iteration process continues until optimization is
reached, converging when one of two conditions are met
LIBLINEAR addresses both conditions while solving
for the sub-problem. The software contains a library with
tools used for SVM classification when data cannot fit
into memory
Online learning algorithms are designed to effectively
classify data by building a weight model derived from
sequentially received training examples. Compared to
block minimization which solves for the sub-problem of
each block, online learning updates instances through the
use of a cache file. Each iteration round updates the
cache file where the weight model is stored. The
algorithm classifies each instance, and uses the new
“instance-label pair” to update and improve the stored
model
Several strategies were proposed to optimize online learning algorithms. Most of which aim to extend the original purpose of binary classification to multi-class learning. In the study conducted by Argyriou et al (2005), an extension to a graph-based approach to online learning was discussed. Shalev-Shwartz et al (2007) exploited the dual formation of optimization to create a more efficient online learning algorithm.
John Langford and his colleagues at Yahoo! Research
developed Vowpal Wabbit, a fast online-learning
algorithm that uses stochastic gradient descent. Vowpal
Wabbit can handle very large datasets without ever
needing to load the entire dataset into memory. The
algorithm also requires less computational power and far
fewer resources by learning through online gradient
descent
Algorithm 3 Online-learning framework for Vowpal Wabbit
Inputs:
• threshold θ ≥ 0
• gravity sequence gi ≥ 0
• learning rate η ∈ (0, 1)
initialize weights wj ← 0 ( j = 1, . . . , d)
1. Acquire an unlabeled example x = [x1 , x2 , . . . , xd ]
j j
2. Compute prediction: y = ∑ j w x
3. Acquire the label y from dataset
for all weights wj ( j = 1, . . . , d)
(a) if wj > 0 and wj ≤ θ then wj ← max{wj − gi η, 0}
(b) else if wj < 0 and wj ≥ −θ then wj ← min{wj + gi η, 0}
4. Update weights for all features j: wj ← wj + 2η(y − y)xj
Here, the superscripted symbol wj denotes the jth
component of vector w in order to differentiate from
wi, which references the ith weight vector
Updates to the assigned weights are stored in a cache file that is small enough to be read into the limited memory available. Vowpal Wabbit stores only the cache file, allowing for faster implementation, and increased performance through the optimization process.
In this section we discuss related work pertaining to comparisons of Large-scale Classification problems. The topic has compiled a comprehensive library primarily for binary classification. As such there seems to be a gap in knowledge pertaining to multi-class classification. We derive the techniques used for our comparison from strategies implemented in related work.
Yu et al. first introduced a comparison for large linear classification in his paper published in 2012. His comparison of SVM solvers and online-learning algorithms only extended to binary classification. The study defined one assumption that is significant in our comparison.
Assuming that the amount of available memory is limited, entire datasets cannot be stored in memory, but can be stored in the disk of one computer. The size of the datasets used in this paper are large enough to satisfying this constraint, and must be accessed through the hard drive where they are stored.
Multi-class classification was addressed in the paper by Chang and Roth in 2011. In the paper comparisons were drawn from both batch learning as well as online-learning algorithms. Unfortunately Vowpal Wabbit at that time was limited to binary classification and no comparisons were drawn. Instead the focus was primarily on block minimizing algorithms. Of which LibSVM was deemed superior to several other algorithms. It is our intent to extend this comparison of LibSVM to Vowpal Wabbit.
The aim of this paper is to test the performance of Vowpal
Wabbit
Testing was performed using one-against-all multi-class
solver options implemented in both algorithms. For a
Kclass problem the one-against-all method constructs K
models, where each model separates a class from the rest.
The ith model is trained with all of the binary instances
pertaining to the ith class. The final output of the
oneagainst-all method is the class that corresponds to the
SVM with the highest output value
Figure 2 RCV1 Class Training Frequency
Comparisons were drawn from test conducted over
multiclass datasets. The SensIT Vehicle dataset was used, in
addition to a larger 53 class (RCV1) dataset. Using the
smaller dataset to establish a baseline reading and
evaluation. The classification problem was then extended
the simple classification problem to one more complex in
that of the RCV1 dataset. The tests conducted here would
reinforce the results gathered from the SensIT dataset.
The SensIT Vehicle dataset features 3-class labels. The
instances were extracted from sensor data collected
during a real world experiment carried out at Twenty nine
Palms, CA in November of 2001
The RCV1 dataset was used in part due to its 53-class
problem. The Reuters Corpus Volume I (Reuters RCV1)
is one of the most widely used test collection for text
categorization research
In order to successfully draw comparisons testing criteria was first established. The criteria is based of overall performance of the ability of the algorithms to learn a classification model and successfully label the instance into the the right class. Stopping criteria was also established before tests were conducted. The iteration threshold was set to 78 rounds. Figures 3 – 6 present the individual performance measures of the algorithms from iteration round 1 to the stopping threshold reached in round 78. The algorithms were compiled in C++ and run on the Linux operating system. All experiments were run on a laptop with 6GB of memory. To ensure accurate results each test was repeated 3 times and the averages were used to rate performance.
Before the experiment can be run using the LIBLINEAR extension LibSVM, the training dataset must be partitioned into smaller blocks. The optimal number of partitions was discovered to be 8 for this case. Vowpal Wabbit on the other hand uses a cache file which fulfills the memory constraint. The dataset does not need to be split or compressed, Vowpal Wabbit can access each instance without reading the entire datasets. The algorithms were first trained and tested using the SensIT dataset. The dataset represents a simple scenario where binary classification is extended into a 3-class problem. The results from both algorithms are shown in figures 3 and 4.
On average the runtime per iteration for Vowpal Wabbit was 0.36 seconds, while the average for libSVM was 1.48 seconds. Vowpal Wabbit performed at a pace 4 times as fast as LibSVM. Both algorithms scored over 80% accuracy classifying testing instances. By the end of the 78 iteration the algorithms were close to converging around the 80.3 percentile. The biggest differences recorded can be seen between the first 5 iteration rounds. This is were the optimization approaches can be RCV1 Dataset distinguished. As the Vowpal Wabbit algorithm passes through the dataset and the weights are updated from the initial label, the accuracy of classification begins to rise. While the consistent accuracy rate for LibSVM can be attributed to the block minimization framework. By solving the subproblem within each equally distributed block first, the updated weights do not yield higher accuracy. Instead the rate is consistent throughout the optimization process.
The second experiment was conducting over the RCV1 dataset. Classification using the one-against-all option is increasingly complicated with each additional class. The increased sample, class, and feature size in the RCV1 dataset taxes the memory load in such a constrained environment. Performance from both algorithms stayed consistent with the baseline ratings established with the tests run over the SensIT dataset. Average runtime per iteration for Vowpal Wabbit increases slightly to 0.43 seconds, while LibSVM decreased slightly to 1.43 seconds. The runtime results of RCV1 is presented in figure 5 are similar to those of SensIT testing in figure 3. As with the sensIT data set, Vowpal Wabbit is consistently quicker than libSVM.
Classification accuracy rose 8 percent when comparing the results of figure 6 to figure 4. The larger dataset has had a positive impact on the accuracy rate of classification for the two algorithms. Again LibSVM scores a higher classification accuracy while achieving more consistent results. The accuracy of Vowpal Wabbit begins to rise until the 20th iterations. From there the accuracy begins to drop until the 78th iteration. Unlike the SensIT tests, the algorithms never appear to converge.
Overall the LIBLINEAR extension LibSVM classification algorithm achieved the highest classification rates. At no point in the iteration process did the Vowpal Wabbit algorithm correctly classify more test instances. The highest classification accuracy rate occurred during the first iteration step. LibSVM correctly classified 80.47% of the SensIT testing dataset, whereas Vowpal Wabbit managed to obtain a lower rate of 80.32% after the final iteration. Figure 7 presents a table with the results gathered testing over the SensIT test dataset. Once more LibSVM attained the highest classification rate over the RCV1 testing dataset. The results from both algorithms are presented in figure 8. the highest accuracy mark was obtained during the first iteration round when LibSVM correctly classifies 88.64% of testing instances. This rate was maintained throughout the iteration process. Vowpal Wabbit reached the t highest mark with an accuracy of 86.99% after the 6th iteration round.
The higher accuracy ratings from LibSVM do come at a cost however. The runtime for each iteration was significantly slower than that of Vowpal Wabbit. The total time needed to reach the 78th iteration round presented in figure 7 was only 27.81 seconds. Compared to 116.56 seconds for LibSVM. Figure 8 presented similar results. Vowpal Wabbit was recorded at 33.85 seconds where LibSVM reached the stopping threshold in 111.93 seconds. In both cases Vowpal Wabbit was 4 times as fast.
Surprisingly both algorithms achieved higher levels of performance solving for the larger RCV1 classification problem. Iteration runtime of both algorithms experienced a small increase in time when compared in figures 3 and 5. The classification accuracy improved in figure 6 when compared to the accuracy ratings in figure 3. The lower rates of classification accuracy can can be contributed to the skewed training dataset. The frequency distribution in presented in figures 1 and 2 are unbalanced. As such the classification accuracy over the smaller SensIT data set was lower than the larger RCV1 dataset. The increase in instances correlated with the accuracy of overall classification. The more instances the algorithm had to train over, the more classification accuracy improved. Using the results recorded from figures 3 -8 the following question about Fast Learning large-scale multi-class classification can be answered:
Question: Which algorithm is most efficient when their are constraints to the memory? When compared, Vowpal Wabbit is the most efficient multi-class classification algorithm. The results from the SensIT test case suggested that Vowpal Wabbit was the quicker algorithm while maintaining a slightly lower accuracy percentile than LIBSVM. Moving from the SensIT dataset to the larger RCV1, the results remained consistent. We have concluded that Vowpal Wabbit had a slight advantage in overall efficiency when there is a constraint placed of computer memory size.
The performance of both algorithms was relatively close however. Due to the small size of the experiment, further testing is needed for a thorough comparison. Testing over datasets that are more expansive, both in sample and feature size could be used for a more significant experiment. However, we feel that the size of the datasets used in this paper are adequate to provide conclusive results for the comparisons made.