SVM code that worked with version 2.11.0.0, fails to converge with 2.14.0

[mathias-brandewinder]

I had an F# sample for multiclass SVM that work perfectly with version 2.11.0.0, but when I run the same code upgrading to version 2.14.0, SVM fails to converge.

The sample code I am using is here (relevant code part highlighted) - it's a multi-class SVM model on a subset of the MINST/digit recognition dataset:
https://github.com/mathias-brandewinder/Presentations/blob/master/Machine-Learning-With-FSharp/code/Classification/Script.fsx#L49-67

When I upgraded to 2.14.0, I get the error message below. Was there any significant change to the library that would explain this?

Thanks in advance!

Mathias

System.AggregateException: One or more errors occurred. ---> System.AggregateException: One or more errors occurred. ---> Accord.ConvergenceException: Convergence could not be attained. Please reduce the cost of misclassification errors by reducing the complexity parameter C or try a different kernel function.
at Accord.MachineLearning.VectorMachines.Learning.SequentialMinimalOptimization.Run(CancellationToken token, Double[] c)
at Accord.MachineLearning.VectorMachines.Learning.BaseSupportVectorLearning.Run(Boolean computeError, CancellationToken token)
at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<>c__DisplayClass6.b__1(Int32 j)
at System.Threading.Tasks.Parallel.<>c__DisplayClassf1.<ForWorker>b__c() at System.Threading.Tasks.Task.InnerInvoke() at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask) at System.Threading.Tasks.Task.<>c__DisplayClass11.<ExecuteSelfReplicating>b__10(Object param0) --- End of inner exception stack trace --- at System.Threading.Tasks.Task.ThrowIfExceptional(Boolean includeTaskCanceledExceptions) at System.Threading.Tasks.Task.Wait(Int32 millisecondsTimeout, CancellationToken cancellationToken) at System.Threading.Tasks.Task.Wait() at System.Threading.Tasks.Parallel.ForWorker[TLocal](Int32 fromInclusive, Int32 toExclusive, ParallelOptions parallelOptions, Action1 body, Action2 bodyWithState, Func4 bodyWithLocal, Func1 localInit, Action1 localFinally)
at System.Threading.Tasks.Parallel.For(Int32 fromInclusive, Int32 toExclusive, Action1 body) at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<Run>b__0(Int32 i) at System.Threading.Tasks.Parallel.<>c__DisplayClassf1.b__c()
at System.Threading.Tasks.Task.InnerInvoke()
at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask)
at System.Threading.Tasks.Task.<>c__DisplayClass11.b__10(Object param0)
--- End of inner exception stack trace ---
at System.Threading.Tasks.Task.ThrowIfExceptional(Boolean includeTaskCanceledExceptions)
at System.Threading.Tasks.Task.Wait(Int32 millisecondsTimeout, CancellationToken cancellationToken)
at System.Threading.Tasks.Task.Wait()
at System.Threading.Tasks.Parallel.ForWorker[TLocal](Int32 fromInclusive, Int32 toExclusive, ParallelOptions parallelOptions, Action1 body, Action2 bodyWithState, Func4 bodyWithLocal, Func1 localInit, Action1 localFinally) at System.Threading.Tasks.Parallel.For(Int32 fromInclusive, Int32 toExclusive, Action1 body)
at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.Run(Boolean computeError, CancellationToken token)
at <StartupCode$FSI_0002>.$FSI_0002.main@() in c:\Users\Mathias Brandewinder\Documents\Visual Studio 2013\Projects\AccordDemo\AccordDemo\Script.fsx:line 59
---> (Inner Exception #0) System.AggregateException: One or more errors occurred. ---> Accord.ConvergenceException: Convergence could not be attained. Please reduce the cost of misclassification errors by reducing the complexity parameter C or try a different kernel function.
at Accord.MachineLearning.VectorMachines.Learning.SequentialMinimalOptimization.Run(CancellationToken token, Double[] c)
at Accord.MachineLearning.VectorMachines.Learning.BaseSupportVectorLearning.Run(Boolean computeError, CancellationToken token)
at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<>c__DisplayClass6.b__1(Int32 j)
at System.Threading.Tasks.Parallel.<>c__DisplayClassf1.<ForWorker>b__c() at System.Threading.Tasks.Task.InnerInvoke() at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask) at System.Threading.Tasks.Task.<>c__DisplayClass11.<ExecuteSelfReplicating>b__10(Object param0) --- End of inner exception stack trace --- at System.Threading.Tasks.Task.ThrowIfExceptional(Boolean includeTaskCanceledExceptions) at System.Threading.Tasks.Task.Wait(Int32 millisecondsTimeout, CancellationToken cancellationToken) at System.Threading.Tasks.Task.Wait() at System.Threading.Tasks.Parallel.ForWorker[TLocal](Int32 fromInclusive, Int32 toExclusive, ParallelOptions parallelOptions, Action1 body, Action2 bodyWithState, Func4 bodyWithLocal, Func1 localInit, Action1 localFinally)
at System.Threading.Tasks.Parallel.For(Int32 fromInclusive, Int32 toExclusive, Action1 body) at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<Run>b__0(Int32 i) at System.Threading.Tasks.Parallel.<>c__DisplayClassf1.b__c()
at System.Threading.Tasks.Task.InnerInvoke()
at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask)
at System.Threading.Tasks.Task.<>c__DisplayClass11.b__10(Object param0)
---> (Inner Exception #0) Accord.ConvergenceException: Convergence could not be attained. Please reduce the cost of misclassification errors by reducing the complexity parameter C or try a different kernel function.
at Accord.MachineLearning.VectorMachines.Learning.SequentialMinimalOptimization.Run(CancellationToken token, Double[] c)
at Accord.MachineLearning.VectorMachines.Learning.BaseSupportVectorLearning.Run(Boolean computeError, CancellationToken token)
at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<>c__DisplayClass6.b__1(Int32 j)
at System.Threading.Tasks.Parallel.<>c__DisplayClassf`1.b__c()
at System.Threading.Tasks.Task.InnerInvoke()
at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask)
at System.Threading.Tasks.Task.<>c__DisplayClass11.b__10(Object param0)<---
<---

---> (Inner Exception #1) System.AggregateException: One or more errors occurred. ---> Accord.ConvergenceException: Convergence could not be attained. Please reduce the cost of misclassification errors by reducing the complexity parameter C or try a different kernel function.
at Accord.MachineLearning.VectorMachines.Learning.SequentialMinimalOptimization.Run(CancellationToken token, Double[] c)
at Accord.MachineLearning.VectorMachines.Learning.BaseSupportVectorLearning.Run(Boolean computeError, CancellationToken token)
at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<>c__DisplayClass6.b__1(Int32 j)
at System.Threading.Tasks.Parallel.<>c__DisplayClassf1.<ForWorker>b__c() at System.Threading.Tasks.Task.InnerInvoke() at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask) at System.Threading.Tasks.Task.<>c__DisplayClass11.<ExecuteSelfReplicating>b__10(Object param0) --- End of inner exception stack trace --- at System.Threading.Tasks.Task.ThrowIfExceptional(Boolean includeTaskCanceledExceptions) at System.Threading.Tasks.Task.Wait(Int32 millisecondsTimeout, CancellationToken cancellationToken) at System.Threading.Tasks.Task.Wait() at System.Threading.Tasks.Parallel.ForWorker[TLocal](Int32 fromInclusive, Int32 toExclusive, ParallelOptions parallelOptions, Action1 body, Action2 bodyWithState, Func4 bodyWithLocal, Func1 localInit, Action1 localFinally)
at System.Threading.Tasks.Parallel.For(Int32 fromInclusive, Int32 toExclusive, Action1 body) at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<Run>b__0(Int32 i) at System.Threading.Tasks.Parallel.<>c__DisplayClassf1.b__c()
at System.Threading.Tasks.Task.InnerInvoke()
at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask)
at System.Threading.Tasks.Task.<>c__DisplayClass11.b__10(Object param0)
---> (Inner Exception #0) Accord.ConvergenceException: Convergence could not be attained. Please reduce the cost of misclassification errors by reducing the complexity parameter C or try a different kernel function.
at Accord.MachineLearning.VectorMachines.Learning.SequentialMinimalOptimization.Run(CancellationToken token, Double[] c)
at Accord.MachineLearning.VectorMachines.Learning.BaseSupportVectorLearning.Run(Boolean computeError, CancellationToken token)
at Accord.MachineLearning.VectorMachines.Learning.MulticlassSupportVectorLearning.<>c__DisplayClass4.<>c__DisplayClass6.b__1(Int32 j)
at System.Threading.Tasks.Parallel.<>c__DisplayClassf`1.b__c()
at System.Threading.Tasks.Task.InnerInvoke()
at System.Threading.Tasks.Task.InnerInvokeWithArg(Task childTask)
at System.Threading.Tasks.Task.<>c__DisplayClass11.b__10(Object param0)<---
<---

Stopped due to error

[mathias-brandewinder]

OK, got it to work again by reducing complexity from 1.0 by default to 0.9:
https://gist.github.com/mathias-brandewinder/0685734f8f47d811356e
Still curious as to what changed between the versions!
Cheers,
Mathias

[cesarsouza]

Hi Mathias!

Thank you very much for submitting this bug report. Of course this breaking change should't have happened. I am writing more unit tests based on your code to understand what happened. Thanks!

Best regards,
Cesar

[cesarsouza]

Hi Mathias!

The largest previous change was done in version 2.13. The library was expanded with several new learning algorithms, many of them specially suited for creating linear models and logistic regression (probabilistic SVM) models:

• http://accord-framework.net/docs/html/N_Accord_MachineLearning_VectorMachines_Learning.htm

In the process, I also refactored the SMO class to add support for weighted samples and class weights, and added this functionality to a base class shared across the new learning algorithms. I also slightly updated the way numeric precision errors were handled in SMO, in the sense the optimization algorithm was now more precise, specially when different weights are used for each sample. As such, this had a direct impact on the way the algorithm detects whether the optimization is likely to diverge.

In the sample code you posted, the problem is that the the initial default value (1.0) for the complexity value C was a bit too large for a linear kernel in that case. It was just on the verge of becoming unsolvable, and the updated precision made sure the algorithm detected this case faster. As a fix, I will change the behavior of the SMO class so it computes an optimal C value by default, unless it is manually set by the user. Using this approach the accuracy in your test program goes from 0.90 to 0.92, so it should be an improvement.

I am also adding some better exception handling to prevent the ugly stack trace you got. Sorry about that!

Best regards,
Cesar

[mathias-brandewinder]

Hi Cesar,
Thanks, that makes sense, and automatically detecting an optimized value for C is a great improvement, looking forward to trying that out! And no worries about the exception/stack trace, I prefer a large stack trace to nothing at all :)
Cheers,
Mathias

[cesarsouza]

A new pre-release NuGet package has been created with the fix. Thanks again for reporting the issue!