I have a corpus of many short entries. Because of this it is very rare that for two entries $x_i, x_j: \ <x_i,x_j> \neq 0$. Therefore for almost all the entries, $x\in TeS$, in the test set I get $\forall x_i\in TrS, \ <x,x_i>=0 $ where $TrS$ is the training set. Therefore SVM is unable to classify most of the entries in the test set. Is SVM the wrong approach to take with short entries? What other algorithms do not face this problem?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
It is not an issue of the algorithm. The problem is that the dimensionality of the space is vast compared to the number of available data. In these cases, you have to either try to find more data, or use different features of lower dimensionality. For text, I don't think you have many options... you need more data.
$\begingroup$
$\endgroup$
Support Vector Machines work fine with high dimensional data.
If you provide an array (n_samples, n_features) and a kernel function, then the first step the library takes is to compute the Gram Matrix, containing the pairwise similarities of the training data [k(x_i, x_j)].
Alternatively, you can provide the Gram matrix. In that case, instead of feature extraction, your preparatory task is to define a kernel function appropriate to the problem - which you have done.
By Morgan's Theorem, the two approaches are equivalent: any kernel function induces a Hilbert space, and a basis for it can be considered to be a list of features. But, I repeat, you don't need to decide what those features are. In general, the basis set is not just large but infinite.
However, some bad news: I don't know of an implementation of SVM that accepts a sparse Gram matrix, so for n samples you have to compute the whole n^2 matrix. This limits you to about 10,000 samples unless you have a big computer. It is also hard to parallelize. If that isn't good enough I would suggest drawing multiple samples and building an ensemble of SVMs.
