标题： 张量，学习和有限字母随机向量的‘柯尔莫戈洛夫扩张’ 显示英文标题

标题： Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors

摘要： 估计一组随机变量的联合概率质量函数（PMF）是统计学习和信号处理的核心问题。如果没有结构假设，比如将这些变量建模为马尔可夫链、树或其他图模型，那么联合PMF估计通常被认为是不可能完成的任务——未知数的数量随变量数量呈指数增长。但是谁赋予我们这种结构模型呢？是否存在一种通用的、“非参数”的方法来控制联合PMF的复杂性，而不依赖于关于潜在概率模型的先验结构假设？是否有可能在不预先偏向分析的情况下发现操作结构？如果我们只能观察到变量的随机子集，我们是否仍然可以可靠地估计所有变量的联合PMF？本文显示，也许令人惊讶的是，如果任意三个变量的联合PMF可以被估计，则在相对较温和的条件下，所有变量的联合PMF可以被证明恢复。这一结果让人想起柯尔莫哥洛夫的扩张定理——一致指定低维分布会诱导整个过程的唯一概率测度。不同之处在于，对于复杂度有限的过程（高维PMF的秩），只需从三维分布就可以获得完整的特征化。实际上，并不需要所有的三维PMF；在更严格的条件下，二维PMF就足够了。利用多线性代数，本文证明了这种更高维度的PMF补全是可以保证的——推导出几个相关的可识别性结果。它还提供了一个实用且高效的算法来执行恢复任务。精心设计的仿真和电影推荐及数据分类的真实数据实验展示了该方法的有效性。 显示英文摘要

摘要： Estimating the joint probability mass function (PMF) of a set of random variables lies at the heart of statistical learning and signal processing. Without structural assumptions, such as modeling the variables as a Markov chain, tree, or other graphical model, joint PMF estimation is often considered mission impossible - the number of unknowns grows exponentially with the number of variables. But who gives us the structural model? Is there a generic, `non-parametric' way to control joint PMF complexity without relying on a priori structural assumptions regarding the underlying probability model? Is it possible to discover the operational structure without biasing the analysis up front? What if we only observe random subsets of the variables, can we still reliably estimate the joint PMF of all? This paper shows, perhaps surprisingly, that if the joint PMF of any three variables can be estimated, then the joint PMF of all the variables can be provably recovered under relatively mild conditions. The result is reminiscent of Kolmogorov's extension theorem - consistent specification of lower-dimensional distributions induces a unique probability measure for the entire process. The difference is that for processes of limited complexity (rank of the high-dimensional PMF) it is possible to obtain complete characterization from only three-dimensional distributions. In fact not all three-dimensional PMFs are needed; and under more stringent conditions even two-dimensional will do. Exploiting multilinear algebra, this paper proves that such higher-dimensional PMF completion can be guaranteed - several pertinent identifiability results are derived. It also provides a practical and efficient algorithm to carry out the recovery task. Judiciously designed simulations and real-data experiments on movie recommendation and data classification are presented to showcase the effectiveness of the approach.