[BUG] SVC hang with linear kernel, degree 3, probability: True

[JohnZed]

Reported by a user via Slack. Running on a 1080ti.

Most hyperparameters work, but hangs with "C: 25.239...", linear kernel, degree 3, probability: True"

[h4pZ]

Hi, I was the one who reported the issue. If more info is needed just let me know. The data comes from the MoA kaggle comeptition

[teju85]

Tagging @tfeher

[tfeher]

Thanks for the info, I will try to reproduce.

[h4pZ]

Update: I just did another run with probability=False and it got stuck again

[tfeher]

Thanks for the update! I believe that I have managed to reproduce the problem. Here is the code that I used:

import numpy as np
import cupy as cp
from sklearn.preprocessing import StandardScaler
import cudf
import cuml
import zipfile

zfile = zipfile.ZipFile("lish-moa.zip", "r")
with zfile.open('train_features.csv') as f:
    train_features = cudf.read_csv(f)
with zfile.open('train_targets_scored.csv') as f:
    train_targets = cudf.read_csv(f)

def preprocess(df):
    df['cp_type'] = df['cp_type'].astype('category').cat.codes
    df['cp_dose'] = df['cp_dose'].astype('category').cat.codes
    df = df.drop(columns=['sig_id'])
    return df

train_features = preprocess(train_features)

def fix_dtypes(gdf):
    for col in gdf.columns:
        gdf[col] = gdf[col].astype('float32')
    return gdf

train_features = fix_dtypes(train_features)

params = {'C':25.239315235912294, 'kernel':'linear', 'verbose':True, 'cache_size':2000} #, 'probability':True}

scaler = StandardScaler()
X = cp.array(scaler.fit_transform(X.to_pandas().to_numpy()))

# Train on target column 5:
target_id = 5
print('Training on target ', train_targets.columns[target_id], ", id", target_id)
clf = cuml.svm.SVC(**params)
y = train_targets.iloc[:,target_id]
clf.fit(X, y)
print('Train score', clf.score(X, y))

The verbose=True flag gives some info about how the training progresses. Normally we should see monotonic decrease in the diff. For some targets this does not happen. This indicates that we have a problem in the solver. Here is an example output which shows the problem.

Training on target  acetylcholine_receptor_antagonist , id 5
[D] [14:19:19.298936] /rapids/cuml/cpp/src/svm/workingset.cuh:107 Creating working set with 1024 elements
[D] [14:19:19.303184] /rapids/cuml/cpp/src_prims/cache/cache.cuh:163 Creating cache with size=2000.000000 MiB, to store 21984 vectors, in 687 sets with associativity=32
[D] [14:19:29.319768] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 500, diff 16.738316
[D] [14:19:41.273842] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 1000, diff 11.583463
[D] [14:19:52.934022] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 1500, diff 7.673965
[D] [14:20:01.113319] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 2000, diff 4.426059
[D] [14:20:05.349232] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 2500, diff 3.663629
[D] [14:20:09.123213] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 3000, diff 1.789166
[D] [14:20:13.967603] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 3500, diff 2.439624
[D] [14:20:19.558834] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 4000, diff 1.346448
[D] [14:20:24.982638] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 4500, diff 0.348033
[D] [14:20:30.917890] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 5000, diff 0.411049
[D] [14:20:36.522165] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 5500, diff 0.526585
[D] [14:20:42.302658] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 6000, diff 1.161356
[D] [14:20:47.735268] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 6500, diff 1.134723
[D] [14:20:53.090460] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 7000, diff 0.365634
[D] [14:20:58.370606] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 7500, diff 0.264841
[D] [14:21:04.216149] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 8000, diff 1.179785
[D] [14:21:10.078033] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 8500, diff 0.721057
[D] [14:21:15.685951] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 9000, diff 1.625063
[D] [14:21:22.579324] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 9500, diff 1.044267
[D] [14:21:29.464410] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 10000, diff 2.071042
[D] [14:21:36.667137] /rapids/cuml/cpp/src/svm/smosolver.cuh:163 SMO iteration 10500, diff 0.68637

I will have to study this further.

[teju85]

@tfeher just curious, is this happening only on this dataset or can it be repro'd using, for eg, make_blobs kind of datasets too?

[tfeher]

I think it is related to #1664 (at least the symptoms are similar), and there we could use make_regression to trigger the problem. This is the first time I see similar issue with SVC. We can probably reproduce it with make_blobs too, just need to find the rng seed that generates to the MoA dataset. :) Jokes aside, I will look into what property of the dasatet might be responsible for the problem.

[tfeher]

I have found the root cause, will PR the fix soon.

[tfeher]

The fix that I had in mind does not work in general, please ignore my previous comment.

TL;DR: This is not a bug. SVC appears to hang because convergence is very slow due to the scale of the input parameters.

Here is an explanation why do we have this problem, and how one can avoid it.

Problem with the input value range

The SVM solver is sensitive to the input value range, and it works best when the input features are scaled to be small (eg to be in the [0, 1] range).

While in the above example I apply a StandardScaler(), it only sets the standard deviation to be 1. The X matrix still has a few hundred values whose abs value > 10. The input training vectors x_i are used to calculate the kernel matrix K. For linear kernel it is simply K = np.dot(X, X.T). In the example above K has several thousand elements with an absolute value larger than 10 000.

Large K values make large change in the gradient of the optimization target. (The gradient is used to select the vectors whose coefficients we are optimizing during an inner iteration). Large changes in the gradient makes the solver converge very slowly. In the example above we need around 7 million inner iteration to fit the SVM, while with properly scaled input one can converge in 60k inner iteration.

Workarounds

1. MinMaxScaler
   If we replace the StandardScaler() in the above example with sklearn.preprocessing.MinMaxScaler((0,1)) then the solver converges quickly.

2. Emulate linear kernel with poly

params = {'C':25.239315235912294, 'kernel':'poly', 'degree':1 'verbose':True, 'cache_size':2000} 

The linear kernel is the only SVM kernel which does not have a built in scaling factor gamma. Note that a 'poly' kernel with degree=1 is basically equivalent to a linear kernel, but it has a gamma factor. Setting gamma properly avoids large kernel values and ensures fast convergence. The default value for gamma is 1 / (X.var() * X.shape[1]) and that is usually a good starting point.

3. Use different solver for linear SVM
   The SMO solver used in cuML or scikit learn SVC is good for nonlinear kernels, but a classifier with a linear kernel can be optimized significantly faster using dual coordinate descent method (or other solvers introduced in LIBLINEAR). Scikit learn provides the LinearSVC to fit linear SVM with such methods. We do not have an equivalent in cuML yet.

Improvements in cuML

To avoid this issue we need to make the solver faster for these cases. We can think about the following feature requests:

1. Implement LinearSVC in cuML [FEA] Implement fast solver for LinearSVC #2773

2. Implement shrinking in the SMO solver
   LIBSVM (used by scikit-learn) can solve such problems relatively fast because it uses 'shrinking' heuristic to decrease the active working set. We could try to implementing similar idea in cuML's SMO solver. It is not clear to me how well would that work in the hierarchical decomposition solver that we have in cuML.

3. Optimize SmoBlockSolve
   The inner SMO iteration take a large fraction of the execution time for the example above. Improving the SmoBlockSolve kernel would help to decrease the time to solution. But I expect that a specific solver for LinearSVC would lead to a much faster solution.