Foundations of Unsupervised and Weakly Supervised Learning

点击翻译按钮获取中文摘要

The development of computational tools that can extract useful structures from the ever-growing sources of data is transforming the way complex systems are analyzed or engineered. The constant push to use machine learning in new applications poses new theoretical and practical challenges, as the fundamental assumptions under which the standard machine learning methods work are no longer valid. While practitioners often resort to case-specific solutions in these situations as the first line of defense, it is essential to establish more generic and reliable design principles. Our plan is to address this for a number of related unsupervised (and weakly supervised) learning problems: we aim at mathematically characterizing the success of learning methods in those settings. The significance of unsupervised learning stems from the fact that these methods can utilize unannotated data (which is abundant in many domains). Unsupervised learning problems arise frequently in science and engineering (e.g., in exploratory data analysis, recommender systems, speech/text/image generation, and medical imaging). From the theoretical point of view, however, many areas of unsupervised learning are still under-developed compared to supervised learning, and heuristic methods are routinely adopted without offering meaningful user-level guarantees. We aim at addressing this shortcoming by formulating and analyzing a set of unsupervised learning paradigms, and providing provably efficient methods (in terms of computational and/or statistical complexities) for solving them. We will work on these directions: Systematic Model Selection Schemes for Clustering. Clustering methods are widely used in practice, but for the basic question of "which clustering method is good for my use case?" it is hard to find an established solution beyond trial and error. To address this, we seek to exploit domain knowledge in a principled way (e.g., interactive clustering or clustering with weak supervision). Efficient Learning and Testing of Distributions. Learning and testing an unknown distribution (given a sample generated from it) are classic problems in statistics. Fresh challenges, however, are arising from the need for handling high-dimensional data. We seek to develop methods that are not only statistically efficient but are also computationally tractable. Also, motivated by applications such as natural-language/speech generation, we study distribution learning/testing with respect to fundamentally different distance measures (e.g., adversarial distances). Supervised Learning with Scarce Training Data. In many applications (e.g., medical diagnosis) it is costly or even impossible to annotate the training data. Therefore, we seek to develop solutions that are less demanding in terms of annotated training data (using, e.g., unsupervised and weakly supervised learning). We also study the "effective sample complexity" of learning particularly for deep neural networks.