SamBaTen: Sampling-based Batch Incremental Tensor Decomposition
SamBaTen: Sampling-based Batch Incremental Tensor Decomposition
复制标题
DOI：
10.1137/1.9781611975321.44
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Ekta Gujral;Ravdeep Pasricha;E. Papalexakis
中科院分区：
文献类型：
--
作者：
Ekta Gujral;Ravdeep Pasricha;E. Papalexakis
张量分解在分析多模态数据集方面是非常宝贵的工具。在许多现实场景中，此类数据集远非静态的，相反，它们往往会随着时间增长。例如，在在线社交网络环境中，随着我们随着时间观察到新的交互，我们的数据集在其“时间”模式下得到更新。我们如何在不对每次更新后都重新计算整个分解的情况下，对这样一个动态演变的多模态数据集保持有效且准确的张量分解呢？在本文中，我们介绍SaMbaTen，一种基于采样的批量增量张量分解算法，它在张量数据集有新的更新时增量式地维护分解。由于SaMbaTen能够有效地总结现有张量和传入的更新，并在简化的总结空间中执行所有计算，它能够扩展到增量张量分解的现有技术无法处理的数据集。我们使用合成数据集和真实数据集对SaMbaTen进行了广泛评估。例如，SaMbaTen达到了与现有增量和非增量技术相当的准确性，同时速度快25 - 30倍。此外，SaMbaTen可扩展到维度高达100K x 100K x 100K的非常大的稀疏和密集动态演变张量，而现有的增量方法无法处理这些张量。
Tensor decompositions are invaluable tools in analyzing multimodal datasets. In many real-world scenarios, such datasets are far from being static, to the contrary they tend to grow over time. For instance, in an online social network setting, as we observe new interactions over time, our dataset gets updated in its "time" mode. How can we maintain a valid and accurate tensor decomposition of such a dynamically evolving multimodal dataset, without having to re-compute the entire decomposition after every single update? In this paper we introduce SaMbaTen, a Sampling-based Batch Incremental Tensor Decomposition algorithm, which incrementally maintains the decomposition given new updates to the tensor dataset. SaMbaTen is able to scale to datasets that the state-of-the-art in incremental tensor decomposition is unable to operate on, due to its ability to effectively summarize the existing tensor and the incoming updates, and perform all computations in the reduced summary space. We extensively evaluate SaMbaTen using synthetic and real datasets. Indicatively, SaMbaTen achieves comparable accuracy to state-of-the-art incremental and non-incremental techniques, while being 25-30 times faster. Furthermore, SaMbaTen scales to very large sparse and dense dynamically evolving tensors of dimensions up to 100K x 100K x 100K where state-of-the-art incremental approaches were not able to operate.