Check whether your leave-one-out procedure leaves out a single sample each time or a triplet of samples (one for each class). If it leaves only a single sample, then your training set is always biased against the test sample. That can explain below chance performance.
For example, consider a classifier that instead of looking at the data, simply outputs the most common label of the training set - that would achieve 0% classification rate in a leave one-sample out scheme. You are of course not using such classifier, but classifiers like SVM do have some susceptibility to bias.
It seems that k-fold cross-validation error is very sensitive to the type of performance measure. It also has an error in itself because the training and validation sets are chosen randomly.
I think you've discovered the high variance of performance measures that are proportions of case counts such as $\frac{\text{# correct predictions}}{\text{# test cases}}$. You try to estimate e.g. the probability that your classifier returns a correct answer. From a statistics point of view, that is described as a Bernoulli trial, leading to a binomial distribution. You can calculate confidence intervals for binomial distributions and will find that they are very wide. This of course limits your ability to do model comparison.
With resampling validation schemes such as cross validation you have an additional source of variation: the instability of your models (as you build $k$ surrogate models during each CV run)
Moreover, changing the number of folds gives me different optimal parameter values.
That is to be expected due to the variance. You may have an additional effect here: libSVM splits the data only once if you use their built-in cross validation for tuning. Due to the nature of SVMs, if you built the SVM with identical training data and slowly vary the parameters, you'll find that support vectors (and consequently accuracy) jumps: as long as the SVM parameters are not too different, it will still choose the same support vectors. Only when the paraters are changed enough, suddenly different support vectors will result. So evaluating the SVM parameter grid with exactly the same cross validation splits may hide variability, which you see between different runs.
IMHO the basic problem is that you do a grid search, which is an optimization that relies on a reasonably smooth behaviour of your target functional (accuracy or whatever else you use). Due to the high variance of your performance measurements, this assumption is violated. The "jumpy" dependence of the SVM model also violates this assumption.
Accuracy metrics for cross validation may be overly optimistic. Usually anything over a 2-fold cross-validation gives me 100% accuracy. Also, the error rate is discretized due to small sample size. Model selection will often give me the same error rate across all or most parameter values.
That is to be expected given the general problems of the approach.
However, usually it is possible to choose really extreme parameter values where the classifier breaks down. IMHO the parameter ranges where the SVMs work well is important information.
In any case you absolutely need an external (double/nested) validation of the performance of the model you choose as 'best'.
I'd probably do a number of runs/repetitions/iterations of an outer cross validation or an outer out-of-bootstrap validation and give the distribution of
- hyperparameters for the "best" model
- reported performance of the tuning
- observed performance of outer validation
The difference between the last two is an indicator of overfitting (e.g. due to "skimming" the variance).
When writing a report, how would I know that a classification is 'good' or 'acceptable'? In the field, it seems like we don't have something like a goodness of fit or p-value threshold that is commonly accepted. Since I am adding to the data iteratively, I would like to know when to stop- what is a good N where the model does not significantly improve?
(What are you adding? Cases or variates/features?)
First of all, if you do an iterative modeling, you either need to report that due to your fitting procedure your performance is not to be taken seriously as it is subject to an optimistic bias. The better alternative is to do a validation of the final model. However, the test data of that must be independent of all data that ever went into training or your decision process for the modeling (so you may not have any such data left).
Best Answer
The performance of a random classifier depends on the fraction of times it predicts positive, e.g. $P(\hat{y} = 1)$. A random model essentially means a model whose predictions $\hat{y}$ are independent of the true label $y$, which means: $$ P(\hat{y} = 1\ |\ y = 1) = P(\hat{y} = 1), $$ and $$ P(y = 1\ |\ \hat{y} = 1) = P(y = 1). $$ The probability of being right, that is the expected accuracy is then: $$ P(\hat{y} = y) = P(\hat{y} = 1) P(y = 1) + P(\hat{y} = 0) P(y = 0). $$ If the dataset is imbalanced, then the 'random' model with the best expected accuracy is the one that always predicts the majority class, with expected accuracy equal to the fraction of data in the majority class.
The main issue with highly imbalanced datasets (say 99% negative) is that you are likely to end up with trivial models as described above, that is a model which always predicts the majority class (negative) and achieves high accuracy (99%) so this useless model actually looks good. If you use a poor scoring function (such as accuracy) when optimizing hyperparameters you are quite likely to obtain a very bad model in imbalanced settings.
This is one of the many reasons why discrete measures like accuracy should be avoided. You won't have such issues with measures like area under the ROC or PR curve.