A Simple Additive Re-weighting Strategy for Improving Margins

1 Introduction

In this paper we introduce a simple additive re-weighting method that is able to improve the margin distribution on the training set. Recent results in computational learning theory [Vapnik, 1998; Schapire et al., 1998; Bartlett, 1998] have tightly linked the expected risk of a classifier (i.e. the probability of misclassification of a pattern drawn from an independent random distribution), with the distribution of the margins in the training set. In general, it results that we can expect best performances on generalization (minimal error on test data) when most of the patterns have high margins.

The aforementioned results are at the basis of the theory of two of the most impressive algorithms: Support Vector Machines and Boosting. Either SVM's and Boosting effectiveness is largely due to the fact that they, directly or not, effectively improve the margins on the training set. In particular, SVM explicitly finds the hyper-plane with the largest minimum margin in a dimensional-augmented space where training points are mapped by a kernel function. In this case, margin theory permits to explain impressive performances even in very high dimensional spaces where data are supposed to be more separated. Most of the recent efforts in SVMs are in the choice of the right kernels for particular applications. For example, in OCR problems, the polynomial kernel was proven to be very effective.

On the other side, boosting algorithms, and in particular the most famous version AdaBoost, produce weighted ensemble of hypotheses, each one trained in such a way to minimize the empirical error in a given "difficult" distribution of the training set. Again, it has been shown [Schapire, 1999] that boosting essentially is a procedure for finding a linear combination of weak hypotheses which minimizes a particular loss function dependent on the margins on the training set, literally ✂ ✄ ✆ ✆ ✟ ✡ ☞ ✍ ✎ ✑ ✓ ✕ ✗ ☞ ✙ . Recently, research efforts related to boosting algorithms faced the direct optimization of the margins on the training set. For example, this has been done by defining different margin-based cost functions and searching for combinations of weak hypotheses so to minimize these functions [Mason et al., 1998].

We will follow a related approach that aims to find a single (eventually non linear) optimal hypothesis where the optimality is defined in terms of a loss-function dependent on the distribution of the margins on the training set. In order to minimize this loss we propose a re-weighting algorithm that maintains a set of weights associated with the patterns in the training set. The weight associated to a pattern is iteratively updated when the margin of the current hypothesis does not reach a predefined threshold on it. In this way a new distribution on the training data will be induced. Furthermore, a new hypothesis is then computed that improves the expectation of the margin on the new distribution. In the following we prove that the distribution converges to a uniform distribution on a subset of the training set.

We apply the above scheme to an OCR pattern recognition problem, where the classification is based on a 1-NN tangent distance classifier [Simard et al., 1993], obtaining a significant improvement in generalization. Basically, the algorithm builds a set of models for each class by an extended version of the Learning Vector Quantization procedure (LVQ [Kohonen et al., 1996]) adapted to tangent distance. In the following we will refer to this new algorithm as Tangent Vector Quantization (TVQ).

The paper is organized as follows. In Section 2, we introduce the concept of margin regularization via the input distribution on the training set. Specifically, we present the ✛ - Margin Re-weighting Strategy, which holds the property to guarantee the convergence of the input distribution. In Section 3, we introduce a definition for the margins in a 1-NN scheme that considers the discriminative ratio observed for a particular pattern, and in Section 4 we define the TVQ algorithm. Finally, in Section 5 we present empirical results comparing TVQ with other 1-NN based algorithms, including SVM. ✜

2 Regularization of the margins

When learning takes place, the examples tend to influence in a different way the discriminant function of a classifier. A discriminant function can be viewed as a resource that has to be shared among different clients (the examples). Often, when pure Empirical Risk Minimization (ERM) principle is applied, that resource is used in a wrong way since, with high probability, it is almost entirely used by a fraction of the training set. Margin theory formally tells us that it is preferable to regularize the discriminant function in such a way to make the examples sharing more equally its support.

Inspired on the basic ideas of margin optimization, here, we propose a simple general procedure applicable, eventually, to any ERM-based algorithm. It permits to regularize the parameters of a discriminant function so to obtain hypotheses with large margins for many examples in the training set.

Without generality loss we consider the margin for a training example as a real number, taking values in ✢ ✕ ✣ ✥ ✧ ✣ ✪ , representing a measure of the confidence shown by a classifier in the prediction of the correct label. In a binary classifier, e.g. the perceptron, the margin is usually defined as ✬ ✭ ✓ ✯ ✙ where ✬ is the target and ✭ ✓ ✯ ✙ is the output computed by the classifier. Anyway, it can be easily re-conduced to the ✢ ✕ ✣ ✥ ✧ ✣ ✪ range by a monotonic (linear or sigmoidal) transformation of the output. In any case, a positive value of the margin must correspond to a correct classification of the example.

Given the function ✗ ✱ ✓ ✯ ☞ ✙ that, provided an hypothesis ✳ , associates to each pattern its margin, we want to define a lossfunction that, when minimized, permits to obtain hypotheses with largemargins (greater than a fixed threshold ✴ ) for many examples in the training set. For this, we propose to minimize a function that, basically, is a re-formulation of SVM's slack variables:

where ■ is a training set with ❏ examples, and ✣ ❄ ❅ ❆ ❇ ❉ ❊ ✸ ✹ ❋ ● ✟ ✣ if ✗ ✱ ✓ ✯ ☞ ✙ ▲ ✴ , and 0 otherwise. The ✂ function is null for margins higher than the threshold ✴ and is linear with respect to the values of the margins when they are below this threshold.

We suggest to minimize ✂ indirectly via a two-step iterative method that "simultaneously" (1) searches for an a priori distribution ◆ ❖ ☞ a80 for the examples that, given the current hypothesis ✳ , better approximates the function ✣ ❄ ❅ ❆ ❇ ❉ ❊ ✸ ❋ ● and (2) searches for a hypothesis ✳ (e.g. by a gradient based procedure) that, provided the distribution ◆ ❖ ☞ a80 , improves the weighted function

This new formulation is equivalent to that given in eq. (1) provided that ◆ ❖ ☞ a80 converges to the uniform distribution on the ✴ -mistakes (patterns that havemargin less than the threshold).

❬ -Margin Re-weighting Strategy

Figure 1: The ✛ -Margin Re-weighting Strategy.

The algorithm, shown in Figure 1, consists of a series of trials. An optimization process, that explicitly maximizes the function ✗ ✱ ✓ ✯ ✙ according to the current distribution for the examples, works on an artificial training set ■ ❶ , initialized to be equal to the original training set ■ . For each ♣ , ❪ ✓ ♣ ✙ replicas of those patterns in ■ that have margin below the fixed threshold ✴ are added to ■ ❶ augmenting their density in ■ ❶ and consequently their contribution in the optimization process. Note that ❧ ☞ ✓ ♣ ✙ denotes the number of occurrences in the extended training set ■ ❶ of the pattern ✯ ☞ .

In the following, we will prove that the simple iterative procedure just described makes the distribution approaching a uniform distribution on the ✴ -mistakes, provided that ❪ ✓ ♣ ✙ is bounded.

2.1 Convergence of the distribution

For each trial ♣ , given the margin of each example in the training set ■ , we can partition the training sample as ■ ✟ ■ ❸ ✓ ♣ ✙ ❺ ■ ❼ ✓ ♣ ✙ where ■ ❸ ✓ ♣ ✙ is the set of ✴ -mistakes and ■ ❼ ✓ ♣ ✙ ✟ ■ ✕ ■ ❸ ✓ ♣ ✙ is the complementary set of ✴ -correct patterns.

Let denote ❾ ✓ ♣ ✙ ✟ ❿ ■ ❶ ✓ ♣ ✙ ❿ and let ❧ ☞ ✓ ♣ ✙ be the number of occurrences of pattern ✯ ☞ in ■ ❶ at time ♣ , with density ❖ ☞ ✓ ♣ ✙ ✟ ❧ ☞ ✓ ♣ ✙ ➁ ❾ ✓ ♣ ✙ . Moreover, let ➂ ✓ ♣ ✙ be a suitable function of ♣ such that ❾ ✓ ♣ ✧ ✣ ✙ ✟ ❾ ✓ ♣ ✙ ➂ ✓ ♣ ✙ .

Let ❧ ☞ ✓ ♣ ✧ ✣ ✙ ✟ ❧ ☞ ✓ ♣ ✙ ✧ ❪ ✓ ♣ ✙ be the update rule for the number of occurences in ■ ❶ , where ❪ ✓ ♣ ✙ is bounded and takes values in ✓ ❛ ✥ ❜ ✪ (note that ❪ ✓ ♣ ✙ may change at different iterations but it is independent from ✐ ). It's easy to verify that ➂ ✓ ♣ ✙ ➇ ✣ for each ♣ because of the monotonicity of ❾ ✓ ♣ ✙ , and that ➂ ✓ ♣ ✙ ➈

✣ with the number of iterations. In fact

At time ♣ ✧ ✣ we have

First of all we show that the distribution converges. This can be shown by demonstrating that the changes tend to zero with the number of iterations, i.e., ➓ ✯ ☞ ❴ ■ ✥ ❿ ➌ ❖ ☞ ✓ ♣ ✙ ❿ ➈ ❛ ❩

We have

which can be easily bounded in module by a quantity that tends to 0:

We now show to which values they converge. Let ↔ ☞ and ↕ ☞ be, respectively, the cumulative number and the mean ratio of ✴ -mistakes for ✯ ☞ on the first ♣ epochs, ↕ ☞ ✟ ➙ ✹ ❊ a114 ❋ a114 , then

Given the convergence of the optimization process that maximizes ❘ in eq. (2), the two sets ■ ❸ and ■ ❼ are going to become stable and the distribution on ■ will tend to a uniform distribution in ■ ❸ (where ↕ ☞ ➈ ✣ ) and will be null elsewhere (where ↕ ☞ ➈ ❛ ). This can be understood in the following way as well.

Given the definition of the changes made on the gamma values on each iteration of the algorithm, we calculate the function that we indeed minimize. Since ➌ ❧ ✓ ♣ ✙ ✟ ❪ ✓ ♣ ✙ ❫ ✣ ❄ ❅ ❆ ❇ ❊ a114 ❋ ● , after some algebra, we can rewrite ➌ ❖ ☞ ✓ ♣ ✙ as:

Thus, ➌ ❖ ☞ ✓ ♣ ✙ ✟ ❛ when ❖ ☞ ✟ ❳ ➢ ✽ ➤ ❊ a114 ❋ ➢ ✣ ❄ ❅ ❆ ❇ ✹ ❊ a114 ❋ ● , for which the minimum of function

is reached. Note that, the minimum of ➜ ➥ is consistent with the constraint ✡ ☞ ❖ ☞ ✟ ✣ .

In general, the energy function is modulated by a term decreasing with the number of iterations, dependent on the ❪ ✓ ♣ ✙ used but independent from gamma, that can be viewed as a sort of annealing introduced in the process.

In the following, we study a specific instance of the ✛ - Margin Re-weighting Strategy.

3 Margins in a 1-NN framework and tangent distance

Given a training example ✓ ✯ ☞ ✥ ✬ ☞ ✙ ❴ ■ , ✬ ☞ ❴ ➭ and a fixed number of models for each class, below, we give a definition of the margin for the example when classified by a distance based 1-NN classifier.

Given the example ✓ ✯ ☞ ✥ ✬ ☞ ✙ , let ➯ ❱ ☞ and ➯ ➲ ☞ be the squared distances between the nearest of the positive set of models and the nearest of the negative sets of models, respectively. We can define the margin of a pattern in the training set as:

This formula takes values in the interval ✢ ✕ ✣ ✥ ✧ ✣ ✪ representing the confidence in the prediction of the 1-NN classifier. Higher values of the ✗ ☞ 's can also be viewed as an indication of a higher discriminative power of the set of models with respect to the pattern. Moreover, a pattern will result correctly classified in the 1-NN scheme if and only if its margin is greater than zero.

In this paper, we are particularly interested in distances that are invariant to given transformations. Specifically, we refer to the one-sided tangent distance [Simard, 1994; Hastie et al., 1995; Schwenk and Milgram, 1995b; 1995a], which computes the distance between a pattern ✯ ❳ and a pattern ✯ ➩ as the minimum distance between ✯ ❳ and the linear subspace ➳ ✯ ➩ ✓ ➵ ✙ approximating the manifold induced by transforming the pattern ✯ ➩ according to a given set of transformations:

If the transformations are not known a priori, we can learn them by defining, for each class ✬ , a (one-sided) tangent distance model ➶ ➹ , compounded by a centroid ➴ ➹ (i.e., a prototype vector for class ✬ ) and a set of tangent vectors ➷ ➹ ✟ ◆ a113 ➐ a80 (i.e., an orthonormal base of the linear subspace ➳ ➴ ➹ ✓ ➵ ✙ ), that can be written as ➶ ➹ ✓ ➵ ✙ ✟ ➴ ➹ ✧ ✡ ➢ ➬ ➮ ➢ ➐ ❲ ❳ ➵ ➐ a113 ➐ .

This model can be determined by just using the ❏ ➹ positive examples of class ✬ , i.e. ✓ ✯ ☞ ✥ ✬ ✙ ❴ ■ , as

which can easily be solved by resorting to principal component analysis (PCA) theory, also called Karhunen-Lo´eve Expansion. In fact, equation (5) can be minimized by choosing ➴ ➹ as the average over all available positive samples ✯ ❱ , and ➷ ➹ as the set of the most representative eigenvectors (principal components) of the covariance matrix a207 ➹ ✟

The corresponding problem for the two-sided tangent distance can be solved by an iterative algorithm, called (twosided) HSS, based on Singular Value Decomposition, proposed by Hastie et al. [Hastie et al., 1995]. When the onesided version of tangent distance is used, HSS and PCA coincide. So, in the following, the one sided version of this algorithm will be simply referred as to HSS.

Given a one-sided tangent distance model ➶ ➹ , it is quite easy to verify that the squared tangent distance between a pattern ✯ and the model ➶ ➹ can be written as:

where a208 ✟ ✯ ✕ ➴ ➹ , ➵ ➐ ✟ a208 a114 a113 ➐ and a208 a114 denotes the transpose of a208 . Consequently, in our definition of margin, we have ➯ ❱ ☞ ✟ ↔ ✐ a213 ➤ ➮ a214 ➮ ✹ ➸ ➩ ⑩ ✓ ✯ ☞ ✥ ➶ ➹ ✙ , and ➯ ➲ ☞ ✟ ↔ ✐ a213 ➤ ➮ a215 a214 ➮ ✹ ➸ ➩ ⑩ ✓ ✯ ☞ ✥ ➶ ➹ ✙ .

Given this definition of margin, we can implement the choice of the new hypothesis in the ✛ -Margin Re-weighting Strategy by maximizing the margin using gradient ascent on the current input distribution.

3.1 Improving margins as a driven gradient ascent

Considering the tangent distance formulation as given in equation (6) we can verify that it is defined by scalar products. Thus, we can derivate it with respect to the centroid ➴ and the tangent vectors ➷ ✟ ◆ a113 ➐ a80 of the nearest positive model obtaining:

Considering that a216 ❇ ✹ a216 ❼ ✟ a216 ❇ ✹ a216 a217 ❰ ✹ a216 a217 ❰ ✹ a216 ❼ and a216 ❇ ✹ a216 ⑩ a218 ✟ a216 ❇ ✹ a216 a217 ❰ ✹ a216 a217 ❰ ✹ a216 ⑩ a218 we can compute the derivative of the margin with respect to changes in the nearest positive model:

A similar solution is obtained for the nearest negative model since it only differs in changing the sign and in exchanging indexes a213 and a221 . Moreover, the derivatives are null for all the other models.

Thus, we can easily maximize the average margin in the training set if for each pattern presented to the classifier we move the nearest models in the direction suggested by the gradient. Note that, like in the LVQ algorithm, for each training example, only the nearest models are changed.

When maximizing the expected margin on the current distribution ◆ ❖ ☞ a80 , i.e., ❘ , for each model ➶ ✟ ✓ ➴ ✥ ◆ a113 ➐ a80 ✙ we have:

where a222 is the usual learning rate parameter. In the algorithm (see Figure 2), for brevity, we will group the above variations by referring to the whole model, i.e., ➌ ➶ ✟ a222 ✡ ➢ ✽ ➢ ☞ ❲ ❳ ❖ ☞ a216 ❇ ✹ a216 ❸ ❩

TVQ Algorithm

Input:

• T: no. of iterations;
• Q: no. of models per class;
• ✴ : margin threshold;

Initialize

➓ ✬ ✥ a223 , initialize ➶ ❊ a224 ❋ ➹ ♠ ✓ ➴ ❊ a224 ❋ ➹ ✥ ➷ ❊ a224 ❋ ➹ ✙ with random models;

✟ ✣ ❩ ❩ a113

➓ ✓ ✯ ☞ ✥ ✬ ☞ ✙ ❴ ■ , select ✓ a223 ❱ ✥ a225 ✬ ☞ ✥ a223 ➲ ✙ s.t. ➶ ❊ a224 ❰ ❋ ➹ ✹ and ➶ ❊ a224 a226 ❋ a227 ➹ ✹ are the nearest, positive and negative, models. Compute ✗ ☞ as in eq. (3) and accumulate the changes on the nearest models

➓ ✬ ✥ ➓ a223 ✥ ➶ ❊ a224 ❋ ➹ ✟ ➶ ❊ a224 ❋ ➹ ✧ a222 ➌ ➶ ❊ a224 ❋ ➹ and orthonormalize its tangents;

➓ ✓ ✯ ☞ ✥ ✬ ☞ ✙ ❴ ■ , update the distribution ❖ ☞ by the rule

❾ Normalize ❖ ☞ 's such that ✡ ❚ ☞ ❲ ❳ ❖ ☞ ✟ ✣ ; ❾ ♠ ❾ ✧ ❿ ◆ ✓ ✯ ☞ ✥ ✬ ☞ ✙ ❿ ✗ ☞ ▲ ✴ a80 ❿ ; End

Figure 2: The TVQ Algorithm.

4 The TVQ algorithm

The algorithm (see Figure 2) starts with random models and a uniform distribution on the training set. For each pattern, the variation on the closest positive and the closest negative models are computed accordingly to the density of that pattern on the training set ■ ❶ . When all the patterns in ■ are processed, the models are updated performing a weighted gradient ascent on the values of the margin. Moreover, for each pattern in the training set such that the value of the margin is smaller than a fixed value, the distribution is augmented. The effect is to force the gradient ascent to concentrate on hardest examples in the training set. As we saw in Section 2 the increment to the distribution is simply the effect of adding a replica ( ❪ ✓ ♣ ✙ ✟ ✣ ) of incorrectly classified patterns to the augmented training set.

The initialization of the algorithm may be done in different ways. The default choice is to use random generated models however, when the training set size is not prohibitive, we can drastically speed up the algorithm by taking as initial models the ones generated by any algorithm (e.g., HSS). However, in the case of multiple models per class the initialization through the HSS method would generate identical models for each class and that would invalidate the procedure. A possible choice in this case, is to generate HSS models by using different random conditional distributions for different models associated to the same class. Another solution, which is useful when the size of the training set is relatively large, is to initialize the centroids as the average of the positive instances and then generating random tangents. Experimental results have shown that the differences on the performance obtained by using different initialization criteria are negligible. As we could expect the speed of convergence with different initialization methods may be drastically different. This is due to the fact that when TVQ is initialized with HSS models it starts with a good approximation of the optimal hypothesis (see Figure 3- ✓ a231 ✙ ), while random initializations implicitly introduce an initial poor estimate of the final distribution due to the mistakes that most of the examples do on the first few iterations.

5 Results

We compared the TVQ algorithm versus SVMs and other 1-NN based algorithms: 1-sided HSS, 2-sided HSS, TDNeuron [Sona et al., 2000], and LVQ. The comparison was performed using exactly the same split of a dataset consisting of 10705 digits randomly taken from the NIST-3 dataset. The binary 128x128 digits were transformed into 64-grey level 16x16 images by a simple local counting procedure 1 . The only preprocessing performed was the elimination of empty borders. The training set consisted of 5000 randomly chosen digits, while the remaining digits were used in the test set.

The obtained results for the test data are summarized in Table 1. For each algorithm, we reported the best result, without rejection, obtained for the dataset. Specifically, for the SVM training we used the SVMa232 ☞ a233 ✱ a114 package available on the internet 2 . Different kernels were considered for the SVMs: linear and polynomial with degrees 2,3 and 4 (we used the default for the other parameters). Since SVMs are binary classifiers, we built 10 SVMs, one for each class against all the others, and we considered the overall prediction as the label with higher margin. The best performance has been obtained with a polynomial kernel of degree 2. We ran the TVQ algorithm with two different values for ✴ and four different architectures. Moreover, we ran also an experiment just using a single centroid for class (i.e., ❿ ➷ ➹ ❿ ✟ ❛ ) with ✴ ✟ ❛ ❩ ✣ . The smaller value for ✴ has been chosen just to account for the far smaller complexity of the model.

1 The number of pixel with value equal to 1 is used as the grey value for the corresponding pixel in the new image.

2 http://www-ai.cs.uni-dortmund.de/SOFTWARE/SVM LIGHT/

In almost all the experiments the TVQ algorithm obtained the best performance. Results on the test data are reported in Table 2. Specifically, the best result for SVM is worst than almost all the results obtained with TVQ. Particularly interesting is the result obtained by just using a single centroid for each class. This corresponds to perform an LVQ with just 10 codebooks, one for each class.

In addition, TVQ returns far more compact models allowing a reduced response time in classification. In fact, the 1NN using polynomial SVMs with ➸ ✟ ➨ , needs 2523 support vectors, while in the worst case the models returned by the TVQ involve a total of 480 vectors (one centroid plus 15 tangents for each model).

In Figure 3, typical error curves for the training and test errors (3- ✓ a237 ✙ ), as well as themargin distributions on the training set (3- ✓ a238 ✙ ) and the induced margin distribution on the test set (3- ✓ ➸ ✙ ) are reported. From these plots it is easy to see that the TVQ doesn't show overfitting. This was also confirmed by the experiments involving the models with higher complexity and smaller values of ✴ . Moreover, the impact of the ✴ -margin on the final margin distribution on the training set is clearly shown in 3- ✓ a238 ✙ , where a steep increase of the distribution is observed in correspondence of ✴ at the expenses of higher values of margin. Even if at a minor extent, a similar impact on the margin distribution is observed for the test data.

In Figure 4 we have reported the rejection curves for the different algorithms. As expected, the TVQ algorithm was competitive with the best SVM, resulting to be the best algorithm for almost the whole error range.

6 Conclusions

We proposed a provably convergent re-weighting scheme for improving margins, which focuses on "difficult" examples. On the basis of this general approach, we defined a Vector Quantization algorithm based on tangent distance, which experimentally outperformed state of the art classifiers both in generalization and model compactness. These results confirm that the control of the shape of the margin distribution has a great effect on the generalization performance.

When comparing the proposed approach with SVM, we may observe that, while our approach shares with SVM the Statistical Learning Theory concept of uniform convergence of the empirical risk to the ideal risk, it exploits the input distribution to directly work on non-linear models instead of resorting to predefined kernels. This way to proceed is very similar to the approach adopted by Boosting algorithms. However, in Boosting algorithms, several hypotheses are generated and combined, while in our approach the focus is on a single hypothesis. This justifies the adoption of an additive re-weighting scheme, instead of a multiplicative scheme which is more appropriate for committee machines.

Acknowledgments

Fabio Aiolli wishes to thank Centro META - Consorzio Pisa Ricerche for supporting his PhD fellowship.