Almost all predictions of a SVM are positives(or are all negatives)

Question

I'm facing a binary classification problem using svm light. However using 5-fold-validation I noticed that later I train SVM with training set (Half positive and half negative samples about) the predictions on the test set(Half positive and half negative samples about) are almost all positives or all negatives causing an accuracy of 50% about.

What could be the reason for this problem? Thanks in advance!

Update: Added the code of k-fold-validation

double gi::approximateOracle::k_fold_validation(const vector< pair<vector<double> , labelType> > &mapped_samples ,const int * indices ,const int k,const string &C ,const double &gamma)
{
double error;
double accuracy=0.0;
double mean_accuracy;

int num_samples = mapped_samples.size(); //num of samples
int remainder = num_samples % k; //reminder of division num_samples/k
int num_samples_less_remainder = num_samples - remainder;
int base_dimension_one_fold  = num_samples_less_remainder / k; //It's sure that rest of this division is zero. This is the base dimension of test set too
int base_dimension_train_set = base_dimension_one_fold * (k-1); //dimension of one fold multiplied for k-1 (because one fold go in test set)

/*In the k-fold-validation in turn a fold have to be inserted in test set and the others in testing set. Starting from
 * the last (those with index of the fold higher) in the test set, the first k-remainder times the training set dimesion
 * have to be base_dimension_train_set+remainder and the others remainder times the dimension of training set have to be
 * base_dimension_train_set+remainder-1 . The dimension of trainig set, in anlogous way, is the first k-remainder times
 * is base_dimension_one_fold and the other remainder times is base_dimension_one_fold+1
 */
vector< pair<vector<double> , labelType> > train_samples(base_dimension_train_set+remainder);
vector< pair<vector<double> , labelType> > test_samples;
test_samples.reserve(base_dimension_one_fold+1);
test_samples.resize(base_dimension_one_fold);//This operation and that above for avoid reallocation.

for(int num_round = 1 ; num_round<k+1 ; num_round++) //CAUTION the kfold function of gi_utilities.cpp return indices from 0 to k-1
{
    if(num_round == (k-remainder+1))
    {
        train_samples.resize(base_dimension_train_set+remainder-1); //this doesn't cause reallocation because the size is minor than previous
        test_samples.resize(base_dimension_one_fold+1); //this doesn't cause reallocation for the reserve above
    }

    for(int index_samples=0,index_train=0,index_test=0 ; index_samples<mapped_samples.size() ;index_samples++)
    {
        if(indices[index_samples] == (k-num_round)) //in the cycle indices(num_round) go from 1 to k. I must have indices from k-1 to 0 
        {   
           test_samples[index_test] = mapped_samples[index_samples];
           index_test++;
        }
        else
        {
            train_samples[index_train] = mapped_samples[index_samples];
            index_train++;
        }
    }

    write_samples_file_svm_light_format(train_samples,TRAIN_FILE);
    write_samples_file_svm_light_format(test_samples,TEST_FILE);
    error = build_classifier(C , gamma , false); //false i.e. doesn't calculate LOO. return -1 in this case 
    accuracy += testing();
}

mean_accuracy = accuracy / k ;
assert(("L'accuracy media trovata con k-fold-validation non è compresa tra 0 e 100",(mean_accuracy>=0 && mean_accuracy<=100.0)));
return mean_accuracy;
}

and here the functions shuffle and kfold used for create the indices

    /*Implemented following Knuth shuffle. More details at https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle */
void shuffleArray(int* array,int size) 
{
  int k;
  int temp; 
  int n = size;
  while (n > 1) 
  {
   // 0 <= k < n.
   k = rand()%n;        

   // n is now the last pertinent index;
   n--;                 

   // swap array[n] with array[k]
   temp = array[n]; 
   array[n] = array[k];
   array[k] = temp;
  }
 }

   //Don't forget to delete the memory returned from this method
   int* kfold( int size, int k )
   {
  int* indices = new int[ size ];

  for (int i = 0; i < size; i++ )
    indices[ i ] = i%k;

  shuffleArray( indices, size );

  return indices;
    }

The indices are created in this way:

    srand(time(0));
    indices = kfold(mapped_samples.size() , 5 ); //this method return dynamic memory

The function build_classifier() do the training (there is there a call to a function of svm_light). testing() use the test set (writed in the file) and the model (writed in another file) for do predictions and return the accuracy and in another file return for each sample of the test set a number that point the prediction is positive or negative (>0 or not)

Answer 1

I assume that your cross validation is implemented correctly the first glance at your code does not exhibit anything weird.

I also assume that you use svmlight without modifications and it works correctly.

The only thing that can cause your problems can be the improper selection of parameters. Please check this: https://en.wikipedia.org/wiki/Support_vector_machine#Parameter_selection as well as the documentation of SVM light. Try multiple combinations.

I have not seen your data, but my intuition is that:

• They are not separable and in combination with that...
• ...the parameters cause something like majority voting. If the training set has majority of positives, it results into all positives in the test set.

My advice:

• Evaluate different values of parameters.
• Plot the data in some dimensions to see if there is any change to reach separability.
• Try different classifier such as k-neighbors as a reference. Also available in C++ easily: http://docs.opencv.org/3.1.0/de/d63/kmeans_8cpp-example.html