3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neil Slater
    Commented Feb 5, 2017 at 21:10
  • $\begingroup$ Related: cs.stackexchange.com/q/109583/755 $\endgroup$
    – D.W.
    Commented Nov 30, 2019 at 22:19

1 Answer 1

Reset to default
2
$\begingroup$

There are many approaches to this type of problem, which would be defined as text classification. You could create a Term Frequency or Term Frequency Inverse Document Frequency matrix based on the tokens (words) in the strings, then use standard machine learning algorithms such as SVM, Random Forest, Gradient Boosted Trees, Logistic Regression, Naive Bayes. You could also potentially use word embedding's and neural networks. In this case, each word would be represented as a vector of similar words. Finally, I have recently been experimenting with character level convolutional neural networks and this seems to work well for user generated text classification. There is link below.

https://papers.nips.cc/paper/5782-character-level-convolutional-networks-for-text-classification.pdf

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! Those kinds of approaches would indeed be suitable for human-readable text (e.g., English text). I guess what I didn't make clear in my question is that I'm working with strings that are not English text, but rather are some other format (e.g., computer logs, binary files, etc.). Regarding character-level convolutional neural networks, my understanding is that they're an instance of recurrent neural nets and require large training sets -- but they look very promising otherwise. Is is also your experience that they require large training sets? $\endgroup$
    – D.W.
    Commented Jan 6, 2017 at 18:49
  • $\begingroup$ For instance, in that paper, their training sets contain 100K - 3.5M instances -- though it is also dealing with a challenging classification task. Is there a way to make character-level convolutional networks work well with a much smaller training set, assuming the classification task is not so hard? $\endgroup$
    – D.W.
    Commented Jan 6, 2017 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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