7 ms·
Automatic Generation of Regular Expressions from Examples
- superasn 14y agoSounds neat, but unfortunately it isn't working with a "Server is busy!" error.
- curiousdannii 14y ago"When there are less than 200 examples, the training set and validation set have the same size. Otherwise, the training set is composed of 100 examples and the other examples constitute the validation set." Why divide the data into sets like that? Assuming the sample data is representative, wouldn't it be better to use much more for training, say 90% with 10% for validation?
- haffi112 14y agoThen you might have the problem of over-fitting the training set. See here for example: http://en.wikipedia.org/wiki/Overfitting http://en.wikipedia.org/wiki/Overfitting
- StavrosK 14y agoYou use the validation set precisely to avoid overfitting. I agree that a 90/10 split would be more reasonable.
- ZoFreX 14y agoYou could also use 10-fold cross validation[1] or similar where you rotate the training/validation sets. [1]: http://en.wikipedia.org/wiki/Cross-validation_%28statistics%29#K-fold_cross-validation http://en.wikipedia.org/wiki/Cross-validation_%28statistics%...
- msellout 14y agoMore training data helps prevent overfitting.
- Cyranix 14y agoThe other replies, directly discussing overfitting, are spot on. However, I did want to point out explicitly that the stated assumption of representative sample data can be a fundamental challenge, not to be taken lightly.
- pathikrit 14y agoFunnily, I had asked this question awhile back on StackOverflow: http://stackoverflow.com/questions/4880402/ http://stackoverflow.com/questions/4880402/
- wib 14y agoCool & handy
- a3_nm 14y agoInterestingly, there is much to say about the theoretical problem of finding the smallest regular expression for a set of positive and negative examples. A nice overview: http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/ http://cstheory.blogoverflow.com/2011/08/on-learning-regular...
- tlarkworthy 14y agoThe sledge hammer approach.
- vineet 14y agoThere is a related cool system: http://groups.csail.mit.edu/uid/lapis/ http://groups.csail.mit.edu/uid/lapis/ It is actually a text editor, and doesn't come up with Regular Expressions but similar textual constraint patterns.
- RyanMcGreal 14y agoI can see how this supports TDD. Write a test suite and it will generate a regex that passes it.
- ajanuary 14y agoI can't find it now, but I've read about projects generating haskell code from unit tests. Anyone got links?
- IsTom 14y agoI don't know about generating code from unit tests, but there's Djinn for generating code from type signatures.
- egonschiele 14y agoDo you mean QuickCheck? http://www.haskell.org/haskellwiki/Introduction_to_QuickCheck http://www.haskell.org/haskellwiki/Introduction_to_QuickChec...
- Evbn 14y agoQC generated random examples from a rule, not the reverse.
- reader5000 14y agoInstead of randomized hill-climbing (genetic programming's search algo) why not try a little A*?
- sunir 14y agoHow would you envision that working? What is the estimated distance function?
- DasIch 14y agoThe "distance" of a regular expression could be the specifity (think CSS) or the size of the language described by the regular expression (with some adjustments to account for repetition as a* being infinite is probably not what is intended.) The real problem is that the space of possible solutions is very large, so you will have to do that lazily, which would make an implementation in a lot of languages rather annoying. I'd also expect this algorithm to be biased towards regular expressions that are more specific than the user intended them to be, especially for example sets that are small or not very diverse.
- __alexs 14y agoIs a* more or less infinite than .*?
- krallja 14y agohttp://en.wikipedia.org/wiki/A*_search_algorithm http://en.wikipedia.org/wiki/A*_search_algorithm
- __alexs 14y agohttp://en.wikipedia.org/wiki/Aleph_number http://en.wikipedia.org/wiki/Aleph_number
- DasIch 14y agoI intended `a` to mean `a` repeated zero or more times, meaning that `a` defines a language of infinite size as there are an infinite number of strings that match that grammar.
- jcromartie 14y agoSlightly off-topic: I was surprised to see a ".it" domain that was actually Italian.
- Ecio78 14y agoIt's an italian university, Università degli Studi di Trieste (northeast of Italy): http://www.units.it/ http://www.units.it/
- ExpiredLink 14y agoMore off-topic: I wonder why 'interesting' top-level domains like '.it' or '.at' aren't used more frequently to create 'interesting' domain names. Edit: you.get.it
- dwwoelfel 14y agoThey're hard to register and cost more. I registered http://canhekick.it http://canhekick.it through iwantmyname.com after someone snatched up canhekickit.com. It cost me $30 instead of $10.
- josephagoss 14y agoIs there any chance to look at the code (application)? I'd be interested in running this locally as I have a need for generation of regular expressions.
- coroxout 14y agoI look forward to trying this once the HN server overload effect has worn off. This is something I would have found useful a year or two ago, considered writing, and decided it would be impossible to get a usefully generalised regex. I'm glad people cleverer and less defeatist than me had the same idea, since it seems it is possible to get useful results after all :)
- csmatt 14y agoI attempted writing something similar when I was bored at work a year ago. I soon discovered how difficult this problem actually is. It's definitely beyond afternoon hacking. I'd love to get a peek at the secret sauce!
- a3_nm 14y agoThere is a paper which explains how it works: http://mllab.inginf.units.it/publications/international-conference-publications/automaticgenerationofregularexpressionsfromexampleswithgeneticprogramming http://mllab.inginf.units.it/publications/international-conf... Note that there are other (non-genetic) approaches to learn regular expressions (some are cited in the above paper).
- csmatt 14y agoThanks for the link. I've been meaning to get into machine learning and this sounds like a good, tractable problem to start with.
- jmmcd 14y agoSumit Gulwani of Microsoft Research has a non-genetic programming approach to this and similar problems, which is interesting to compare: http://dl.acm.org/citation.cfm?doid=2240236.2240260 http://dl.acm.org/citation.cfm?doid=2240236.2240260
- arekp 14y agoThis makes me think. In 2012 people still think that genetic programming, a numerical optimization technique (and not the most efficient one), magically solves random machine learning problems.
- drblast 14y agoMore efficient techniques, such as? It would be interesting for me and others here to learn from what you know rather than be left with what you wrote.
- draegtun 14y agoFor the reverse of this see HN discussion Given a list of regexes, generate all possible strings that matches all of them - http://news.ycombinator.com/item?id=2579783 http://news.ycombinator.com/item?id=2579783
- tlrobinson 14y agoThis is cool, but it doesn't look like it's doing even trivial optimizations... (?:\d\d[\d\d\.\d\.][\d\.](?:(?=([\d\.]+))\1)) "[\d\d\.\d\.]" is equivalent to "[\d\.]", right? It's also got a useless non-capturing group and lookahead.
- merlincorey 14y agoYou have apparently useless genes in your genetic code as well. These regex's are generated with genetic programming techniques, so they are not guaranteed to be an optimal solution, just a good (by the metric of working) one.
- tlrobinson 14y agoYou're right, I was just pointing out that with some basic optimizations you could get a much cleaner result. Applying some fairly simple optimizations to my example result I get the following equivalent regular expression: \d{2}[\d\.]{3,} which isn't too bad. EDIT: Here are the optimizations: The original: (?:\d\d[\d\d\.\d\.][\d\.](?:(?=([\d\.]+))\1)) 1. Remove non-capturing groups and lookahead: \d\d[\d\d\.\d\.][\d\.]([\d\.]+)\1 2. Simplify set: \d\d[\d\.][\d\.]([\d\.]+)\1 3. Remove redundant backreference: \d\d[\d\.][\d\.][\d\.]+ 4. Combine duplicates: \d{2}[\d\.]{3,}
- mdda 14y agoThe optimizations are great to apply to an end result, but the Genetic Programming process probably won't benefit from the expressions being optimized 'along the way' because some of the 'junk' subexpressions allow for more robustness in the face of the genetic operators. Putting it another way, your highly optimized version (4) is likely to be much more brittle to small 'defects' than (1).
- DannyBee 14y agoThe last point can't be overstated. Optimization is highly likely to overfit the training data. For example, given training data 000001 000002 000003 000004 The "optimized" version would be \d+[1-4] If the goal was simply to find the smallest regex that matches all the training data, that's trivial to code, NP-hard to execute. But the goal isn't to find the smallest regexp, it's to find a "good" regexp.
- enraged_camel 14y agoI keep getting "server busy". Why share a link if it won't be able to handle the traffic?
- ColinWright 14y agoSo, every time you share a link, you always test it first to see if it can handle the load? Ah, no, looking at your profile you haven't yet ever shared a link. I can only conclude that you find lots and lots of things that you are eager to share with us, but when you rigorously test them you find that they can't handle the load, so you sadly decline to submit them. Thanks for the feedback. I'll be sure to keep it in mind.
- enraged_camel 14y agoThis is a community for geeks. I believe it is a realistic expectation that one should be wary of sharing with tens of thousands of readers sites that run processor-intensive server-side scripts. (Nice ad hominem, by the way.)
- ColinWright 14y agoThis is a community for geeks ( although there are those who claim otherwise: http://news.ycombinator.com/item?id=4681146 http://news.ycombinator.com/item?id=4681146 ). I believe it is a reasonable expectation that people will want to see things and will understand that sometimes they will need to spread the load. Cutting edge technology sometimes can't handle the load, and geeks will know that, understand, and make allowances. I would have thought that people in this community would want to see new stuff, rather than have it withheld simply because someone thought the server might not be able to handle the load. How can one tell if the server is going to be able to handle the load? Perhaps the owners had anticipated that this would be of interest and were ready to handle it? How could I tell? I think it's a reasonable expectation in a community of geeks that if you are to level criticism at me, then you should offer alternatives and constructive suggestions, and I look forward to your reply as to what one should do when considering submitting a link like this. How would you test it?
- bartolialberto 14y agoI am the "boss" of the research group that put the regex generator tool on line (http://machinelearning.inginf.units.it/ http://machinelearning.inginf.units.it/ "Data and tools"): we are all VERY SORRY for any inconvenience we may have created. We simply did not expect so much interest in our work. Yesterday we received more than 11000 visits. We are not prepared to handle such traffic. We are working toward adding a few more CPUs and will notify the status on our Twitter account: http://twitter.com/@MaleLabTs http://twitter.com/@MaleLabTs. We are afraid we will not be able to fully solve the overload problem anytime soon, though. We are a small research group, with scarce resources. We are also preparing a small faq for addressing several of the interesting points raised in this discussion (e.g., why not executing everything in Javascript ?). We will notify completion via Twitter. Further comments and criticisms are most welcome. Thanks a lot for your interest and patience.
- ColinWright 14y agoThat's a useful response - thanks for taking the time to register and respond. Apologies for the extreme load caused - when geeks find something cool they tend to share it, and not everyone is ready for that level of interest. I, for one, look forward to your updates. What would be really great would be for you to prepare some kind of informal overview and put that up as a blog post, making it clear that it's intended to be informal, and is not in any way your formal research results or anything like that. Then post here a link to it. If you engage with this community you'll get a lot of smart people offering thoughts and suggestions from which you can pick and choose. Great work - thank you.