# Machine Learning technique for learning string patterns

I have a list of words, belonging to different selfdefined categories. Each category has its own pattern (for example one has a fixed length with special characters, another exists of characters which occur only in this category of "word", ...).

For example:

"ABC" -> type1
"ACC" -> type1
"a8 219" -> type2
"c 827" -> type2
"ASDF 123" -> type2
"123123" -> type3
...


I am searching for a machine learning technique to learn these pattern on its own, based on training data. I already tried to define some predictor variables (for example wordlength, number of special characters, ...) on my own and then used a Neural-Networks to learn and predict the category. But thats acutally not what i want. I want a technique to learn the pattern for each category on its own - even to learn patterns which I never thought about.

So i give the algorithm learning data (consisting of the word-category examples) and want it to learn patterns for each category to predict later the category from similar or equal words.

Is there a state-of-the-art way to do it?

• From my point of view, you can do smth like this cistrome.org/cr/images/Figure4.png , but instead of ACGT you can use patterns such as "number, uppercase, lowercase, space", etc. Sep 7 '16 at 12:53
• @GermanDemidov thanks for your comment. i already thought about something like this. But i actually want the learning algorithm to do it on its own and detect the patterns. (I don't know if it's possible for ML). Sep 7 '16 at 13:12
• actually this patterns are machine learning. Of course you can do it with machine learning, but a person needs to do a feature extraction first before giving it as an input to ML algorithm. Which features would you extract from this examples? I can think about hash functions, but it will work quite bad for strings of unequal length. So since you will find a way how to extract features, you will be able to use ML methods. You can also do smth like Levenshtein distance between symbols of different classes, clusterize them and use minimum distance to centroids for classification. Sep 7 '16 at 13:38
• @chresse you might want to add the unsupervised learning tag to your question. For doing this with neural networks, this LeCun paper might be of interest. Since I do not have much experience with text mining or neural networks, I cannot say how good this approach might be. Sep 7 '16 at 13:41
• So transform your vectors using features you naturally use (u - uppercase, l - lowercase, n - number, s - space), so your vectors will be "ABC" - "uuu", "a8 219" - "lnsnnn" and so on. Then you need to introduce some distance measure, for example, using this algorithm: en.wikipedia.org/wiki/Smith–Waterman_algorithm. After this you will be able to perform a classification/clusterisation/visualization of your data. Sep 7 '16 at 13:46

Could your problem be restated as wanting to discover the regular expressions that will match the strings in each category? This is a "regex generation" problem, a subset of the grammar induction problem (see also Alexander Clark's website).

The regular expression problem is easier. I can point you to code frak and RegexGenerator. The online RegexGenerator++ has references to their academic papers on the problem.

You could try recurrent neural networks, where your input is a sequence of the letters in the word, and your output is a category. This fits your requirement such that you don't hand code any features.

However for this method to actually work you will require a fairly large training data set.

You can refer Supervised Sequence Labelling with Recurrent Neural Networks by Alex Graves chapter 2 for more details.

This is a link to the preprint

• Could you add a full citation for your final reference, in case the "preprint.pdf" link breaks in the future? (I believe this is the relevant chapter?) Sep 7 '16 at 15:21