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.