A natural language interface is a feature of many modem services such as search engines, notification services, and customer service to name a few. The natural language interface allows a user to provide user-input in natural or conversational manner. Rather than provide the user-input in a structured manner that is specified by the service, a user may simply “converse” with the service—i.e., the user may provide the user-input, which in some instances may be speech or may be text, to the natural language interface as if the user were conversing with another human. Such natural language interfaces may be taught using machine learning techniques.