1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Without negative examples, the problem seems to be ill-defined. If you ask for the simplest regex then it will be .*, which overgeneralises. If you ask for the most specific regex, it will be word1|word2|...|wordn. Since you use the word example, I assume that this would be too specific. Do you have any ideas for criteria to say which of two candidate regexes is "better"? $\endgroup$ – Peter Taylor May 20 at 8:41
  • $\begingroup$ So, the problem is to approximate the generator which may be using a regex to generate the inputs. So, even though the algorithm requested can not know of the original regex, we (examiners) can use the regex inside the blackbox to determine if the learned regex is correct (or if it over or under generalizes). Does this help? There does seen to be some research (e.g. core.ac.uk/download/pdf/81942815.pdf) in this regard; so it is reasonably well defined. But I would like to know where the field is at. $\endgroup$ – rahul May 20 at 9:14
  • $\begingroup$ The problem is a rather classical one. See en.wikipedia.org/wiki/Language_identification_in_the_limit for references including one to Gold's original paper. $\endgroup$ – Kai May 20 at 9:52
  • $\begingroup$ @kai Indeed. Gold shows that learning with positive examples only is impossible. However, what is the best one can do? $\endgroup$ – rahul May 20 at 10:00
1
$\begingroup$

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.

$\endgroup$

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.