BIGDATA: F: Computationally Efficient Algorithms for Large-Scale Crossed Random Effects Models

决定买什么、去哪里吃饭、看哪部电影等问题，对消费者、销售者以及从事这些商品和服务的人来说，都具有巨大的经济价值。公司试图使用记录购买和意见的大量数据集来匹配人和产品。即使有一个大的数据集，获得可靠的结果也是一个挑战。对相同或相似产品的测量是相关的，就像由相同或相似的人进行的测量一样;然而，相关数据产生的信息比不相关数据少。 即使在现代大型计算机上，要正确地解释这种相关性也需要太多的计算，因为计算量随着数据大小的增加而增加。 忽视这些相关性将导致分析变得过于自信，结果不可复制，导致效率低下和浪费决策。 该项目将开发计算效率高和可靠的方法来处理这类数据以及更复杂的数据结构。 本研究的结果将有助于行业和个人做出购买决策。上述问题在统计文献中被称为交叉随机效应。 统计上合适的工具是线性混合模型和广义线性混合模型。 拟合线性混合模型的常用方法在数据集的大小方面具有比线性增长更快的成本。 指数是三个二分之一。 在贝叶斯方法中也会产生相同的成本。对于大型现代数据集，这些成本完全无法承受。最近的一些解决方案与矩量法一起工作，其成本随数据大小线性缩放。 这个项目将开发一个从矩方法开始，然后向最大似然解迭代的回拟合方法。 它还将扩展到广义线性混合模型的情况下，以处理二元结果，如客户是否购买了特定的项目。 虽然交叉随机效应在电子商务中很普遍，但它们可能出现在任何环境中，其中存在将一种实体与另一种实体连接起来的多对多关系。 我们在二分图的边上观察到的任何地方都是可能出现交叉随机效应的地方。 这项工作还将包括随机坡度模型。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

The problems of deciding what to buy, where to eat, which movie to watch, and so forth are of enormous economic value to consumers, sellers, and the people employed making those goods and services. Companies try to match people and products using vast data sets recording purchases and opinions. Even with a large data set it is a challenge to get reliable results. Measurements on the same or similar products are correlated, as are measurements by the same or similar people; however, correlated data yield less information than uncorrelated data. Properly accounting for the correlation requires too much computation, even on modern large computers, because the amount of computation grows as a power of the size of the data. Ignoring those correlations will produce an analysis that becomes overconfident and findings that are not reproducible, leading to inefficiency and wasteful decisions. This project will develop computationally efficient and reliable methods to handle data of this kind as well as more complicated data structures. The results of this research will benefit both industry and individuals making purchasing decisions.The problems described above are known as crossed random effects in the statistical literature. The statistically proper tools are linear mixed models and generalized linear mixed models. The usual ways to fit linear mixed models have a cost that grows faster than linearly in the size of the data set. The exponent is three halves. The same cost arises in a Bayesian approach. With large modern data sets these costs are completely out of reach. Some recent solutions work with the method of moments at a cost that scales linearly with the data size. This project will develop a backfitting method that starts with the moment method and then iterates towards the maximum likelihood solution. It will also extend to the generalized linear mixed model case in order to handle binary outcomes, such as whether the customer did or did not buy a particular item. While crossed random effects are prevalent in electronic commerce, they can arise in any setting where there are many to many relationships connecting one sort of entity to another. Any place where we have observations on the edges of a bipartite graph is a place where crossed random effects may arise. This work will also include random slope models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.