1. A computer-implemented method of generating a natural language spoken dialog system, the method comprising: at each turn in a dialog, nominating a set of allowed dialog actions and a set of contextual features; selecting an optimal action from the set of nominated allowed dialog actions using a machine learning algorithm; and generating a response based on the selected optimal action at each turn in the dialog.