Can SVM solution change after shuffling the inputs

Question

When training a support vector machine (SVM) for classification with exactly the same data I obtain different results based on the order of the inputs, ie. if I shuffle the data I get different SVMs.

If I understood the theory correctly, the SVM solution should be the same regardless of the order of the inputs, so how come I get the different results? Is there any implementation "detail" in SVM why shuffling would change the solution? I have already checked my code several times, because I think this smells.

I use the SVM implementation in OpenCV.

EDIT: in this case, by shuffling I refer to changing the order of the data points not features.

Answer 1

I am not familiar with the OpenCV implementation. But do this: run several trials on exactly the same data set -- no shuffling, same order, same data points. See if the SVM changes. Obviously, in theory, it shouldn't. But it could be that there is some small randomization step somewhere in the implementation that produces different outputs for the same input.

Edit: As Chris A. asks, do the feature vectors correspond to their proper labels after shuffling? If not, that would obviously destroy your results.

Answer 2

SVM is for solving convex optimization problem, so maximum is unique. That means any random optimization algorithms will solve problem very close to unique optimal solution. And shuffling can't change result above float-point operation accuracy.