2
$\begingroup$

So I currently have a text pattern detection challenge to solve at work. I am trying to make an outlier detection algorithm for a database, for string columns.

For example let's say I have the following list of strings:

["abc123", "jkj577", "lkj123", "uio324", "123123"]

I want to develop an algorithm that would detect common patterns in the list of strings, and the indicate which strings are not in this format. For example, in the example above, I would like this algorithm to detect the following regular expression:

r"[a-z]{3}\d{3}"

given that the majority of the entries in the list obey this pattern, except the last one, which should be marked as an outlier.

The first idea that come to my mind was to use a genetic algorithm to find the regular expression pattern, where the fitness function is the number of entries on the list that match the pattern. I haven't worked out the details (crossvers function, etc..), and there is already the difficulty in the sense that the pattern ".*" will match everything, hence will always maximize the fitness function.

Anybody already worked on a similar problem? What are my options here? Thank you!

$\endgroup$
3
  • $\begingroup$ You define a very general problem. You have to narrow down the definition of a 'pattern' to be able to come up with a practical solution. Is this a research question or practical work to be done? $\endgroup$
    – havzhiva
    Jul 27 '20 at 15:37
  • 1
    $\begingroup$ Thinking about the patterns implied by the samples, I would first try to learn a similarity function between two strings and then cluster using this metric. $\endgroup$
    – havzhiva
    Jul 27 '20 at 15:39
  • $\begingroup$ It is practical work. The thing is, I do not have the dataset yet, so I can not be more specific. But I basically want to detect outliers in string patterns. $\endgroup$ Jul 27 '20 at 15:41
2
$\begingroup$

The problem you face is part of what is called in literature grammar learning or grammar inference which is part of both Natural Language Processing and Machine Learning and in general is a very difficult problem.

However for certain cases like regular grammars/languages (ie learning regular expressions / DFA learning) there are satisfactory solutions up to limitations.

A survey and references on grammar inference and inference of regular grammars:

Learning DFA from Simple Examples

Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt, in his seminal paper posed the following open research problem:“Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution?”. We demonstrate that the class of simple DFA (i.e., DFA whose canonical representations have logarithmic Kolmogorov complexity) is efficiently PAC learnable under the Solomonoff Levin universal distribution. We prove that if the examples are sampled at random according to the universal distribution by a teacher that is knowledgeable about the target concept, the entire class of DFA is efficiently PAC learnable under the universal distribution. Thus, we show that DFA are efficiently learnable under the PACS model. Further, we prove that any concept that is learnable under Gold’s model for learning from characteristic samples, Goldman and Mathias’ polynomial teachability model, and the model for learning from example based queries is also learnable under the PACS model

An $O(n^2)$ Algorithm for Constructing Minimal Cover Automata for Finite Languages

Cover automata were introduced in [1] as an ecient representation of finite languages. In [1], an algorithm was given to transforma DFA that accepts a finite language to a minimal deterministic finite cover automaton (DFCA) with the time complexity $O(n^4)$, where $n$ is the number of states of the given DFA. In this paper, we introduce a new efficient transformation algorithm with the time complexity $O(n^2)$, which is a significant improvement from the previous algorithm.

There are even libraries implementing algorithms for grammar-inference and DFA learning:

  1. libalf
  2. gitoolbox for Matlab

source: stackoverflow

$\endgroup$
5
  • $\begingroup$ This is super cool, but is my problem not simpler than that? I literally just want to figure out the most common regex for my given list of strings. What about my genetic algorithm idea, is it really bad? I have not tried it yet, but I will definitely do it when I have the chance $\endgroup$ Jul 28 '20 at 9:03
  • $\begingroup$ @DavidMarques, DFA learning is exactly learning the common regex matching the valid strings. Genetic algorithms are of course an option however since the search space can be enormous they are likely to converge very slowly to a solution unlike more spesialised algorithms like DFA learning (note DFA is another name and format for Regular Expressions) $\endgroup$
    – Nikos M.
    Jul 28 '20 at 11:18
  • $\begingroup$ Ok thank you. I got confused by the term "gramar" and I though it mean actually learning from a corpus of sentences and not necessarily patterns in one word strings like in my example. Thank you! $\endgroup$ Jul 28 '20 at 11:41
  • $\begingroup$ @DavidMarques, no here it is meant as formal grammar not necessarily natural language grammar. So regular expressions form regular grammars and so on. But in any case even if you dont accept this answer, try to learn more about automata theory/formal grammars and how they relate to machine learning , it is a fascinating topic! $\endgroup$
    – Nikos M.
    Jul 28 '20 at 11:43
  • $\begingroup$ You answer was super helpful, I am really unsure weather I should accept your answer or the one from Erwan, I wish I could accept both. $\endgroup$ Jul 28 '20 at 14:31
2
$\begingroup$

Here are a few ideas:

If the number of strings is not too high, you could consider taking a formal approach and use a finite automata determinization algorithm (I'm very rusty about this stuff but I clearly remember that there is such a thing). The idea is to start from a big automaton made of the union of all the strings, then use the algorithm to find the deterministic automaton, which can then be converted to a regular expression.

A more data-science-y idea is to use character-based similarity/distance measures between all the pairs of strings. Then it should be possible to identify outliers, maybe through clustering based on the distance. Typical character-based measures: Jaro-Winckler, Levenshtein edit distance.

Finally an original (but possibly bad) idea would be to try to train a (character-based) language model on the strings (assuming there are sufficiently many of them). Given an input string, the language model gives you a probability that this string belongs to the "language", so an outlier could be detected by its low probability.


[addition following OP's comment]

Language modeling is normally used for representing the valid sentences in a language, e.g. English, based on the likelihood of sequences of words in this language. It's trained from a large number of correct sentences so that it can estimate the probability of the $n$-grams of words in this language. This is a common NLP task (example) but in your case you would use characters instead of words and strings instead of sentences, so there would be a small adaptation compared to the examples you'll find.

$\endgroup$
4
  • 1
    $\begingroup$ the formal approach you mention is called DFA learning algorithm and is part of grammar inference methods as stated in my other comment $\endgroup$
    – Nikos M.
    Jul 27 '20 at 20:00
  • $\begingroup$ @NikosM. right, thank you for the precision $\endgroup$
    – Erwan
    Jul 27 '20 at 20:36
  • $\begingroup$ I have never heard about DFA, sounds complicated. What about the last thing you propose? How would I go about training that? $\endgroup$ Jul 28 '20 at 9:01
  • 1
    $\begingroup$ @DavidMarques see edit $\endgroup$
    – Erwan
    Jul 28 '20 at 10:35

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.