In this paper, we introduce the online and streaming MAP inference and learning problems for Non-symmetric Determinantal Point Processes (NDPPs) where data points arrive in an arbitrary order and the algorithms are constrained to use a single-pass over the data as well as sub-linear memory. The online setting has an additional requirement of maintaining a valid solution at any point in time. For solving these new problems, we propose algorithms with theoretical guarantees, evaluate them on several real-world datasets, and show that they give comparable performance to state-of-the-art offline algorithms that store the entire data in memory and take multiple passes over it.
翻译:在本文中,我们引入了非对称威慑点进程(NDPPs)的在线和流式 MAP 推论和学习问题,即数据点的到达顺序是任意的,而算法则只能对数据以及亚线性内存使用单一通道。 在线设置还有在任何时间保持有效解决方案的额外要求。 为了解决这些新问题,我们提出了带有理论保证的算法,对几个真实世界数据集进行了评估,并显示这些算法的性能与将全部数据存储在记忆中并取得多个传票的最新离线算法的性能相当。