A major challenge in machine learning and artificial intelligence is to reduce the dependency in full direct supervision and learn from various undirected resources as well. Most successful machine-learning systems require some amount of human supervision. Currently, a dominant paradigm for building a statistical parser, for example, is to first have human annotators to manually parse a large amount of sentences, and then use the parsed sentences to learn the parameters of the parsing system. For example, a parser built using the Penn Tree Bank, a large corpora of parsed sentences from the Wall Street Journal, is expected to parse well newswire text fragments, but not e-mails, which are different in nature. Yet, one would like to employ all data available from various resources, genres and types to build either a general system or a system that is adapted to a particular task. The goal of the proposed project is to design new paradigms for large-scale learning of natural language problems in various languages from heterogeneous data sources of variable size, quality, amount of supervision and type. Our primary objective is to develop theory, design algorithms, analyze them and build systems for processing written and spoken natural language. Furthermore, the world-wide-web and similar available resources contain a huge amount of heterogeneous collections of data. I propose to make use of the heterogeneous data and based on the tools I will develop to build statistical-based automated systems for various natural language processing tasks, with applications ranging from automatic document classification, via a full range of information extractions to speech analysis and recognition.