What is the best algorithm known to learn the regular expression from a set of positive examples?

Question

I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I only have positive examples. (Checking whether a string is accepted or rejected is possible but rather costly). I see that algorithms like RPNI and L* requires both positive and negative examples.

I especially want to avoid over-generalization.

Update: I have been making do with using Sequitur to identify repeating patterns in single strings, and then lining up the resulting patterns to identify common repetitions. However, this feels really kludgy and I would like to improve it. Is this the best one can do? are there better ways?

Answer 1

I have wondered something similar and failed to find much in the way of satisfying answers in the literature. Here is what I tentatively came up with.

It seems perhaps what we need is some kind of regularization. If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the regular expression). Also, let $\ell$ be a loss function, so that $\ell(\theta(x),y)$ denotes the loss incurred based on the model's prediction on string $x$, given that the ground-truth label is $y$. Given a training set $(x_1,y_1),\dots,(x_n,y_n)$, define the total loss as

$$L(\theta) = \sum_i \ell(\theta(x_i),y_i) + \lambda c(\theta),$$

for some hyperparameter $\lambda>0$.

Then we could frame the learning task as finding a model $\theta$ that minimizes $L(\theta)$.

In your case, $\theta$ is a regexp, $c(\theta)$ is the length of the regexp, $x_i$ is a string, $\theta(x_i)$ is true or false according to whether $\theta$ matches $x_i$ or not, and you have only positive examples so all of your $y_i$'s are true. You could also consider other models as well, such as a finite-state automaton (whose complexity is given by the number of states) or a neural network (e.g., a CNN or RNN).

The term $\lambda c(\theta)$ is a regularization term that penalizes model complexity, and thereby combats overfitting. Basically, we're applying Occam's razor, that simpler explanations are more likely to be true. If we omitted this term (or equivalently, set $\lambda=0$), we would indeed overfit and obtain poor generalization: e.g., we might learn the regexp $x_1|x_2|\cdots|x_n$. If we over-regularize (and set $\lambda=+\infty$, say), then we underfit and might learn the regexp $.*$, which also is not good. The hope is that the regularization term will find a happy medium between these two extremes.

So now the problem reduces to, how can we solve the optimization problem above? Unfortunately, I don't know of any good ways to do this, for the case of regexps.

One approach would be to set an upper bound on the size of the regexp, i.e., choose some hyperparameter $s$, and limit consideration to regexps of length $\le s$; then try to find a regexp $\theta$ that minimizes $\sum_i \ell(\theta(x_i),y_i)$ subject to $c(\theta) \le s$. (This formulation is closely connected to the formulation at the top of the question; the theory of Lagrange multipliers tells us that there is a one-to-one correspondence between $\lambda \leftrightarrow s$ that yields equivalent solutions to the optimization problems.) Unfortunately, I don't know of any good algorithms for solving this optimization problem, i.e., for finding such a regexp $\theta$ that minimizes this loss. Perhaps you could use a SAT solver to solve it; I don't know.

Another possibility is to choose a different model. With CNNs or RNNs, it is easier to fix the size of the neural network architecture (thus implicitly fixing an upper bound on the complexity of the model), and then use gradient descent to find weights $\theta$ that minimize $\sum_i \ell(\theta(x_i),y_i)$. Or, you could use a DFA instead of a regexp as your model, and then I think there are methods you could use to solve this optimization problem. In particular, there are known algorithms for using a SAT solver to find whether there exists a DFA with $\le s$ states that matches every string in a given set of strings; and to minimize $\sum_i \ell(\theta(x_i),y_i)$, you culd plausibly repeatedly choose random subsets of $x_1,\dots,x_n$, find a DFA that matches every string in the subset, and check its total loss on the entire training set.

It seems hard to imagine that these are the best one can do, but I haven't been able to find better methods in the literature yet; this is the best I've been able to come up with so far.

Related: https://datascience.stackexchange.com/q/16115/8560.