Weights in LinearSVC change if we magnify features

Question

I have been experimenting with SK-Learn's Support Vector Machines, specifically the LinearSVM.

I have found myself in the position where I have been given two different calculations of the feature matrix used in the algorithm. However - since they only differ by a constant, I assumed this would have no problem in the estimation of the weights within the LinearSVM algorithm.

Unfortunately I have found in my experiment that it does seem to matter. This doesn't make sense to me. Below is the toy example I have used to experiment with.

Can any one tell me why the weights may differ or point out an error in my example which would explain why the weights differ?

import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer, CountVectorizer

## 3 Fake documents
document = ["one two three one four five",
            "two six eight ten two",
            "one one one one one one"]
n_features = 5

# Method 1
vectorizer = TfidfVectorizer(max_df=0.5, max_features= n_features,
                             ngram_range=(1,3), use_idf=False)

X = vectorizer.fit_transform(document)

## Method 2
count = CountVectorizer(vocabulary=vectorizer.get_feature_names(),ngram_range=(1,3))
countMat = count.fit_transform(document)

count.get_feature_names() == vectorizer.get_feature_names()
Norm = []
for i in xrange(countMat.toarray().__len__()):
    row = countMat.toarray()[i]
    dl = document[i].split().__len__()
    nrm = 1000 / float(dl)
    Norm.append(row / nrm)

## Always correlated between Method 1 & Method 2
for i in xrange(len(Norm)):
    c = np.corrcoef(Norm[i], X.todense()[i])
    print("Correlation: %0.3s" % c[0][1])

## Correlation of rows: nan ## No features extracted
## Correlation of rows: 1.0
## Correlation of rows: 1.0

## Are the weights the same?
from sklearn.svm import LinearSVC
clf = LinearSVC(loss='l2', penalty="l2", dual=False, tol=1e-3)
clf.fit(X, [0, 1, 1])
tf_w = clf.coef_

clf = LinearSVC(loss='l2', penalty="l2", dual=False, tol=1e-3)
clf.fit(Norm, [0, 1, 1])
n_w = clf.coef_

c = np.corrcoef(n_w, tf_w)
print("Correlation of weights: %0.3s" % c[0][1])
## Correlation of weights: 0.8

Answer 1

Scaling the features does make a difference in the solution of SVM because scaling features does not affect the regularization term but it affects the loss term.

Training objective of an SVM can be written as follows: $$ O(w) = \frac{\lambda}{2} R(w) + \sum_{i=1}^n L_w(x_i, y_i) \tag{1} $$ where $R(w)$ is the regularizer (e.g. $R(w) = ||w||^2$) and $L_w(x_i, y_i)$ is the loss function (e.g. $L_w(x_i, y_i) = \max \left\{ 0, 1 - y_i w^T \phi(x_i) \right\}$ for binary linear SVM). SVM classifier is the $w^*$ that minimizes $(1)$; that is $w^* = \arg\min_w O(w)$.

Multiplying the feature function $\phi(x_i)$ by a constant changes $w^* = \arg\min_w O(w)$ because $R$ is not affected by the scaling but $L_w$ is. If you scale up $L$ by a factor, then you have to scale up $\lambda$ by the same factor to get the same classifier.

My favorite tutorials/papers about SVMs:

1. Tutorial by Andrew Moore.

2. Learning Structural SVM with Latent Variables, ICML 2009 paper, by J. Yu and T. Joachims.

3. Tutorial from VLFeat, with cool tricks on how to train SVMs with Stochastic Gradient Descent.