# How to tackle different sample size in the training set in SVM

I have to train a SVM for a classification problem. I have some strings that are the paths in a deterministic finite automata (DFA). If the alphabet is -01- then possible strings are 011101110 or 0110 for example. The purpose of classifier (SVM) is the correct prediction (label) of unseen strings like accepting or rejecting(label 1 or label -1, binary classification). The problem is that the strings have different lenghts. How can I tackle this problem?

A SVM classifier requires a fixed-length feature vector, i.e., all feature vectors must have the same length. There are multiple solutions:

• Pad out the strings to fixed length.

• Choose a different set of features, so that there is a fixed number of features.

• Pick a fixed number $k$, and look at windows of length $k$ (i.e., substrings of length $k$). Classify each window of length $k$ using your SVM, then combine those results somehow (e.g., majority vote).

• Use a different classifier, such as a recurrent neural network (e.g., LSTM). See also https://datascience.stackexchange.com/q/16115/8560 for more possibilities.

Based on your subsequent comments, it sounds like you want to learn a DFA. There's lots written on learning DFAs, using Angluin's algorithm, SAT solvers, or other methods. Follow the link above for some entry points into the literature on that. I don't think a SVM is the right tool for that job -- this sounds like an XY problem.

• I must build a classifier that is able to predict if an unseen string is accepting or rejecting for the underlying DFA. Practically the builded SVM have to be a good approximation of regular language(DFA) captured(you hope) from string of trainining set. I was forced to use SVM. What could be a good concrete technique?
– Nick
Commented Apr 26, 2017 at 20:18
• @Umbert, see last paragraph in edited answer.
– D.W.
Commented Apr 26, 2017 at 21:27
• I have to implement in the active learning (L*,Observation Pack algorithms) an oracle approximate. I don't want learn exactly a dfa from strings ma learn in a approximate way the dfa(the language) with svm from strings like this I use the classifier for do approximate membership and equivalences queries. I also think that SVMs are not perfectly suitable but I have been forced to use them.So what could be the best technique to do equal string length in my case? (I do not think there is literature, it's a specific problem. But is there no such similar (no exact) example?)
– Nick
Commented Apr 27, 2017 at 0:25
• @Umbert, what forces you to use a SVM? It seems like it might to understand the source and nature of that requirement. If it helps, there are ways to learn an approximate DFA (e.g., choose a random sample of the training set and learn a DFA for that, say using SAT; or other methods are possible).
– D.W.
Commented Apr 27, 2017 at 6:00
• No underying knowledge, but the requirement is imposed for research purposes. Finally thanks for the various answers
– Nick
Commented Apr 28, 2017 at 15:12