This requires defining matching patterns, like a word-based regex though, right? Houndify uses that approach because it is easier to integrate with speech recognition, but it is very cumbersome to use and maintain and doesn't allow learning new utterances.

I don't think Wit.ai works as simply as you believe - it isn't merely matching keywords. Unfortunately I haven't been able to find out exactly how it does work. Alexa, and Nuance Mix work the same way as Wit.ai. In my experience it is the superior approach.

Viv is also one to watch but they haven't really said the NLU works yet.