Abstract We study how decisions for word ordering and word choice in surface natural language generation can be automatically learned from annotated data. We examine four trainable systems for surface natural language generation in the air travel domain, called NLG[1–4]. NLG1 is a lookup table which stores the most frequent phrase to express a concept, and is intended as a baseline system for comparison purposes. NLG2 and NLG3 attempt to find the highest probability word sequence with respect to a maximum entropy probability model. They differ in that NLG2 predicts words left-to-right, while NLG3 predicts words in dependency tree order. NLG4 requires a dependency-style grammar of phrase fragments and conditions on their use, and attempts to find the highest probability word sequence that is consistent with the rules and conditions of the grammar. NLG4 has been implemented in a dialog strategy for a prototype air travel conversational system, in which word order is dynamically modified to emphasize certain aspects of the run-time dialog state.