How to calculate the cache size in respect of the available ram

[endeffects]

Hi,

i'd like to calculate the correct cache size in respect of the available ram for the given column and row size. Is there any way to do this?

[endeffects]

I ran some tests for 10.000 rows and 50 columns with the following setup and the result looks bugged for me.

Setup

var teacher = new MultilabelSupportVectorLearning<Polynomial>
{
	Learner = (param) => new SequentialMinimalOptimization<Polynomial>
	{
	    Kernel = kernel
	}
};

Results

Cache Size	Execution Time
not set		43.72s
0		156.70s
10		273.13s
100		361.81s
1000		816.61s
2000		942.71s
5000		908.37s
10000		42.08s

So setting the cache size seems to be useless until the size is greater or equal to the default (calculated) value. Which is not an option for large training sets, because having the cache size not set ends up in an out of memory exception or takes much longer if the cache size is zero.

[endeffects]

I ran a performance profiler and the problem above seems to be a result of the LinkedList Implementation you use for the Chunk Caching Mode in the KernelFunctionCache.cs. Still without the LinkedList more than 30% CPU usage is taken by the GetOrCompute() calls.

Did you ever thought about to use the .net caching classes here?
https://msdn.microsoft.com/en-us/library/system.runtime.caching(v=vs.100).aspx

[cesarsouza]

Hi there,

Many thanks for opening the issue. Well... At this point, I suppose it would be better to rewrite the KernelFunctionCache to use more low-level collections than the ones offered by the .NET Framework. A good idea would be to base the implementation on existing open source ones with compatible licenses, such as the ones from the Shark C++ library:

• https://github.com/Shark-ML/Shark/blob/master/include/shark/LinAlg/CachedMatrix.h
• https://github.com/Shark-ML/Shark/blob/master/include/shark/LinAlg/LRUCache.h

I will try to track the progress of the task of rewriting the kernel cache in this issue. Thanks again for opening it.

In any case, maybe it should also be worth to mention that since version 3.5 the SMO algorithm supports a third selection strategy that is supposed to be faster than the others, even though it does not currently make use of a cache. You can try it by setting SMO's Strategy property to SelectionStrategy.SecondOrder.

Regards,
Cesar

[endeffects]

The cache implementations looks nice, i also thought about a self cleaning cache and tried to work it out with Weak References. But the Garbage Collector seems to be faster than the training, so it does not work (see below).

Anyways, i think the cache itself is just a side problem. In my scenario (OneVsRest) the underlying TrainBinaryMachine calls are creating alot of caches on the fly to solve the "sub problems". Which is fine so far, but they remain in the memory.

I was not able to understand the whole process here so far, but the question is: Do we create too many Learners at the same time or do we not free them (in time) when they are done? Or is there any way to chunk them?

        private Dictionary<int, WeakReference> matrix;

        public KernelFunctionCache(TKernel kernel, TInput[] inputs)
        {
            if (kernel == null) throw new ArgumentNullException(nameof(kernel));

            this.kernel = kernel;
            this.inputs = inputs;

            this.Size = inputs.Length;

            // Create cache for diagonal elements
            this.diagonal = new double[ inputs.Length ];

            // Create whole cache.
            this.matrix = new Dictionary<int, WeakReference>();

            for(var i = 0; i < this.Size; i++)
            {
                this.diagonal[i] = kernel.Function(inputs[i], inputs[i]);

                var subMatrix = new double[ this.Size ];
                this.matrix.Add(i, new WeakReference( subMatrix, false));;

                for (var j = 0; j < this.Size; j++)
                {
                    subMatrix[ j] = kernel.Function(inputs[i], inputs[j]);
                }
            }   
        }

        public double GetOrCompute(int i)
        {
            return this.diagonal[i];
        }

        public double GetOrCompute(int i, int j)
        {
            var result = 0.0;

            if (i == j)
            {
                result = this.diagonal[i];
            }
            else if (j > i)
            {
                result = GetOrComputeFromMatrix(j, i);
            }
            else
            {
                result = GetOrComputeFromMatrix( i, j );               
            }

            return result;
        }

        private double GetOrComputeFromMatrix( int i, int j )
        {
            var subMatrix = this.matrix[i].Target as double[];

            if (subMatrix != null)
            {
                return subMatrix[j];
            }

            subMatrix = new double[ this.Size ];
            this.matrix[ i ].Target = subMatrix;

            for( var e = 0; e < this.Size; e++ )
            {
                subMatrix[ e ] = this.kernel.Function( this.inputs[ i ], this.inputs[ j ] );
            }

            return subMatrix[j];
        }

[cesarsouza]

Well, the caches shouldn't remain in memory after all references to the learning algorithms had been lost. The caches do include a Clear() method, but in fact right now they are never being called by any of the learning algorithms.

Maybe I should consider making those algorithms implement the IDisposable interface, or something similar.

In any case, I am running some more experiments on how to best use those caches. It might be more worth to have the caches store entire rows of computations instead of single values.

Regards,
Cesar

[cesarsouza]

For some reason "Find References" in Visual Studio didn't work quite right. The .Clear() method of the cache is indeed being called at the end of the SMO algorithm. It is weird that the memory is not being freed afterwards.

[endeffects]

I think i found the biggest memory leak in the caching class. The Input and Diagonal Fields will not be cleared and for the reason that the Caches are never been disposed these Arrays stay alife.

By changing this i can train much larger sets now, but i think there are more leaks left. So for 50.000 rows and 50 columns it consumes about 15GB ram instead of endless.

    public class EnhancedKernelFunctionCache<TKernel, TInput> where TKernel : IKernel<TInput>
    {                                                    
        private double[] diagonal;    

        private double[][] matrix;

        public EnhancedKernelFunctionCache(TKernel kernel, TInput[] inputs)
        {
            if (kernel == null)
            {
                throw new ArgumentNullException(nameof(kernel));
            }
                                 
            this.Size = inputs.Length;
                                   
            this.matrix = new double[inputs.Length][];
            this.diagonal = new double[inputs.Length];

            Parallel.For(0, inputs.Length, i =>
            {
                this.diagonal[ i ] = kernel.Function( inputs[ i ], inputs[ i ] );
                this.matrix[i] = new double[i];

                for (var j = 0; j < this.matrix[i].Length; j++)
                {
                    this.matrix[i][j] = kernel.Function(inputs[i], inputs[j]);
                }
            });   
        }

        public int Size { get; }

        public int Hits { get; private set; }

        public int Misses { get; private set; }  

        public double GetOrCompute(int i)
        {
            return this.diagonal[i];
        }

        public double GetOrCompute(int i, int j)
        {
            if (i == j) return this.diagonal[i];

            return (j > i) ? this.matrix[j][i] : this.matrix[i][j];  
        }

        /// <summary>
        ///   Clears the cache.
        /// </summary>
        /// 
        public void Clear()
        {
            this.diagonal = null;
            this.matrix = null;   
        }

        /// <summary>
        ///   Resets cache statistics.
        /// </summary>
        /// 
        public void Reset()
        {
            this.Hits = 0;
            this.Misses = 0;
        }   
    }

[cesarsouza]

Hi there,

I am glad you found some solutions! I've also did some modifications to the KernelFunctionCache as well that seems to have improved performance. I've also added a method that could be used to compute the cache size given how much RAM we are willing to give it.

I've updated the function cache to cache partial rows of the kernel matrix instead of individual elements, and also reuse already allocated memory when possible. It also now implements IDisposable to make sure all those large fields are set to null after learning is done.

Another thing that I realized is that the cache seems to perform better when .Sequential strategy rather than WorstPair in the experiments that I was doing. However, this might be dependent on the problem being solved rather than being a rule.

It seemed faster in the experiments I was doing, but I could also try to test in the data you are using. Would you mind sharing your test case/training data so I can measure the performance on it as well?

Regards,
Cesar

[endeffects]

Hi,

sounds like some great improvements, i'll have a look into this.
You can download my sample data here: https://1drv.ms/u/s!AvfU-VGBgXuLg7MO9Q7bt7mNdUwP4A

It's the training set i'm using atm, but i'm not using all of these columns (just 50 of ~130).
Also the last two columns are containing two different output sets.

I ran some more profiling sessions over the last two hours and saw, that the kernel function gets called million of times (from the cache?) within a few minutes. The computing here takes more than 50% of the whole training. So it would be nice if it is possible to reduce the number of calls.

public struct Polynomial : IDistance, IReverseDistance, ICloneable
{
        /// <summary>
        ///   Polynomial kernel function.
        /// </summary>
        /// 
        /// <param name="x">Vector <c>x</c> in input space.</param>
        /// <param name="y">Vector <c>y</c> in input space.</param>
        /// <returns>Dot product in feature (kernel) space.</returns>
        ///          
        public double Function(double[] x, double[] y)
        {
            var sum = this.constant;
            for (var i = 0; i < x.Length; i++) sum += x[i] * y[i];

            return Math.Pow(sum, this.degree);
        }

[cesarsouza]

If the the cache size is larger than the number of rows n in the dataset, then indeed the kernel function will be called at least (n*n)/2 times right at the beginning, before the actual training even starts, because in this case the entire kernel matrix can be fit in memory and is thus computed in its entirety.

In this case, this number (n*n)/2 is actually the minimum number of times the kernel function will be called during training. Unfortunately, it is not possible to reduce the number of calls to something less than this (unless we use a different learning algorithm than SMO).

One possibility to avoid all those calls would be use a first-order optimization algorithm such as averaged stochastic gradient descent. However, if you would like to use a non-linear SVM then it would be necessary to first transform your data using an explicit kernel mapping from one of the kernels that support it (e.g. using Polynomial.Transform(double[])).

[endeffects]

Yes, you are right. I spent too much time with profiling so i missed to understand whats going on.

At the moment i'm using the SecondOrder Strategy with Shrinking enabled, which seems to be the only way to get the learning done within an acceptable time. But i'll have a look into the suggested algorithms also.

I also played around with Alea to enable GPU support, e.g. for building the cache matrix, but it turns out that this is not working well in a decoupled world. So there was no great performance boost.

[cesarsouza]

If you need to get absolute performance, you can also try to train your SVMs using liblinear or libSVM directly (you can call their executables from the command line in C#). The framework should be able to import models generated by any of those libraries back into .NET if you need to use them in C# afterwards.