The past two decades have shown an unexpected effectiveness of "Web-scale" data in natural language processing. Even the simplest models, when paired with unprecedented amounts of unstructured and unlabeled Web data, have been shown to outperform sophisticated ones. It has been argued that the effectiveness of Web-scale data has undermined the necessity of sophisticated modeling or laborious data set curation. In this thesis, we argue for and illustrate an alternative view, that Web-scale data not only serves to improve the performance of simple models, but also can allow the use of qualitatively more sophisticated models that would not be deployable otherwise, leading to even further performance gains. We investigate this hypothesis through the use of both "parametric" and "Bayesian non-parametric" modeling techniques. First, by comparing rich parametric models against simpler models, we show that richer modeling of Web data brings about qualitative and quantitative performance gains. Experimental results in the application domain of "sentence compression" show that richer models lead to systems with improved robustness and generalization power. In the domain of "lexical correction" we augment a coarse "generative model" with a "discriminative reranking" component that incorporates richer contextual information and achieve improvements in performance. Second, by using the Bayesian nonparametric modeling framework, we show how to induce rich models in fully automatic, data-driven ways as opposed to heuristically. We propose principled and unified solutions to not only the estimation but also the "model selection" problem of the linguistically sophisticated grammar formalisms of "tree-insertion grammars" and "tree-adjoining grammars." When evaluated in the domain of "syntactic parsing," our induced grammars do not only lead to improved performance but are also "compact," allowing for efficient computational processing and linguistic analysis. Further we show that these compact grammars can achieve the same performance gains as the parametric rich models in Web-scale sentence compression experiments. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://bibliotheek.ehb.be:2222/en-US/products/dissertations/individuals.shtml.]