# Boolean classification on strings

I have a supervised learning (boolean classification) problem that involves strings. Are there any resources where I can learn about the state of the art in techniques for this?

I'm familiar with many supervised learning techniques where we assume that each instance has a fixed number of attributes: e.g., the instance is represented by a feature vector. But now I have something different; I have a string, i.e., a sequence of characters. I don't know a priori what suitable features might be. Are there any general techniques for doing machine learning in this context?

I'm especially interested in techniques that work given an existing training set (I don't have the ability to label additional data; I don't want an active learning algorithm), and that support some kind of regularization or can handle noisy labels.

Research I've done and approaches that don't meet the above requirements:

• I'm familiar with regexps, finite automata, grammar induction, LearnLib, Angluin's algorithm, and similar concepts. However, most of that work is in the active learning context, where the algorithm generates a new instance (a query) and asks the human to label that instance. In my setting, I must work with passive learning: I have a training set $(x_i,y_i)$ where each $x_i$ is a string and $y_i$ is its class (positive or negative), but I can't obtain any more examples.

• I'm also familiar with automata minimization, so I know how to find the minimal DFA that can generate all positive instances in the training set, but that's not really a good solution. It doesn't have any notion of regularization or Occam's razor and is not robust to a small amount of error/noise in the labels. There might be a very small DFA that predicts the proper label with 99% accuracy, but automata minimization won't find it; it is overly focused on finding an automaton that generates all positive instance, even if this yields a much larger automaton.

• I'm also familiar with the notion of separating automata, i.e., the smallest DFA that has 100% accuracy on the training set (accepts all positive instances and rejects all negative instances). However, this has the same problems as automata minimization. Also, this seems likely to overfit and essentially end up memorizing the training set. Finally, the research literature I've seen stops at noting that finding the smallest separating automaton is NP-hard, and doesn't concern itself with practical algorithms for finding a separating automaton that is as small as possible.

• I'm familiar with recurrent neural networks, but my impression is that they tend to require very large training sets, so probably won't be useful in my setting. Are there variants of this technique that work with training sets that aren't enormous (say, hundreds of examples in the training set)?

• I'm familiar with some techniques from the natural language processing (NLP) literature, but they seem very specialized to parsing human languages. Are there any general techniques that apply to other structured strings? In my situation, the strings are not human-readable text written in some human language, but rather have some other content.

## migrated from stats.stackexchange.comJan 5 '17 at 18:40

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

• You give a lot of examples of your research and your concerns about why the techniques might not apply. But you do not give the same level of detail about your problem, so it is impossible to tell if your assessment is correct. If your problem is so specialised that you cannot find an example in the literature, and you are not willing or able to share it in detail, then I don't see any way you can get help online. Instead, you should start by implementing some of the ideas that you are unsure of, and measure the performance. Then you will know whether your concerns are justified. – Neil Slater Feb 5 '17 at 21:10