  In noisy environments, speech can be hard to understand for humans. Spoken
dialog systems can help to enhance the intelligibility of their output, either
by modifying the speech synthesis (e.g., imitate Lombard speech) or by
optimizing the language generation. We here focus on the second type of
approach, by which an intended message is realized with words that are more
intelligible in a specific noisy environment. By conducting a speech perception
experiment, we created a dataset of 900 paraphrases in babble noise, perceived
by native English speakers with normal hearing. We find that careful selection
of paraphrases can improve intelligibility by 33% at SNR -5 dB. Our analysis of
the data shows that the intelligibility differences between paraphrases are
mainly driven by noise-robust acoustic cues. Furthermore, we propose an
intelligibility-aware paraphrase ranking model, which outperforms baseline
models with a relative improvement of 31.37% at SNR -5 dB.
