2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

It's hard to say what will be most appropriate for your particular situation, without knowing more about your learning task.


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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Umbert Apr 26 '17 at 20:18
  • $\begingroup$ @Umbert, see last paragraph in edited answer. $\endgroup$ – D.W. Apr 26 '17 at 21:27
  • $\begingroup$ 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?) $\endgroup$ – Umbert Apr 27 '17 at 0:25
  • $\begingroup$ @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). $\endgroup$ – D.W. Apr 27 '17 at 6:00
  • $\begingroup$ No underying knowledge, but the requirement is imposed for research purposes. Finally thanks for the various answers $\endgroup$ – Umbert Apr 28 '17 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.