CIF: Small: Learning Mixed Membership Models with a Separable Latent Structure: theory, provably efficient algorithms, and applications

在科学和工程领域的广泛问题中，包括高光谱成像、基因表达分析和代谢网络，观察到的数据是高维的，并且是由一小部分未知的共同潜在原因的未知随机混合产生的。能够从观察到的数据中成功有效地识别潜在原因不仅对科学理解很重要，而且对有效的数据表示和决策也很重要。这类问题的流行算法利用近似和启发式来计算可跟踪性。因此，这些算法的一致性或效率保证要么非常弱，要么根本不存在。本研究涉及从具有可证明的统计和计算效率保证的高维数据中学习潜在原因模型的算法的开发。本研究的关键是共享潜在因素的自然可分离性。每个潜在因素的特征成分是否存在？这与常用方法得出的估计值大致相符。本研究旨在证明近似可分性不仅是混合隶属度潜因子模型的一种自然而方便的结构性质，而且实际上是高维的必然结果。本研究还涉及开发一套可证明一致的、统计和计算效率高的算法，通过适当地利用由特征分量引起的几何形状来解决各种混合成员潜在因子问题。关键的洞察力是将每个潜在因素的特征部分识别为合适空间中的极值点。这可以通过适当定义的随机投影有效地完成。基于随机投影的算法自然适用于低通信成本的分布式实现，这对于web规模的分布式数据挖掘应用程序具有吸引力。

In a wide spectrum of problems in science and engineering that includes hyperspectral imaging, gene expression analysis, and metabolic networks, the observed data is high-dimensional and arises from an unknown random mixture of a small set of unknown shared latent (hidden) causes. Being able to successfully and efficiently identify the latent causes from the observed data is important not only for scientific understanding, but also for efficient data representation and decision making. Popular algorithms for such problems make use of approximations and heuristics for computational tractability. As a consequence, consistency or efficiency guarantees for such algorithms are either very weak or nonexistent. This research involves the development of algorithms for learning latent-cause models from high-dimensional data with provable statistical and computational efficiency guarantees.The linchpin of this research is a natural separability property of the shared latent factors ? the presence of a signature component for each latent factor ? that is approximately satisfied by the estimates produced by popular approaches. This research aims to establish that approximate separability is not only a natural and convenient structural property of mixed-membership latent-factor models, but is, in fact, an inevitable consequence of high-dimensionality. This research also involves the development of a suite of provably consistent and statistically and computationally efficient algorithms for a diverse set of mixed-membership latent-factor problems by suitably leveraging the geometry induced by the signature components. The key insight is to identify the signature parts of each latent factor as extreme points in a suitable space. This can be done efficiently through appropriately defined random projections. The random-projections-based algorithm is naturally amenable to a low-communication-cost distributed implementation that is attractive for web-scale distributed data-mining applications.