论文标题
在非正交傅立叶基础中稀疏的学习集功能
Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases
论文作者
论文摘要
机器学习在离散域上的许多应用，例如在推荐系统中或拍卖中的学习偏好功能，可以简化为估计傅立叶域中稀疏的设置函数。在这项工作中，我们介绍了一种新的算法系列，用于学习傅立叶式套件集功能。它们最多需要$ NK -K \ log_2 k + k $ Queries（设置功能评估），在傅立叶系数的轻度条件下，其中$ n $是接地套件的大小和$ k $的非零傅立叶系数的数量。与其他集中在正交Walsh-Hadamard变换上的工作相反，我们的小说算法运作了最近引入的非正交傅立叶变换，这些变换提供了不同的傅立叶范围。这些自然会在建模时，例如形成替代品和补充的项目集。我们证明了对几种现实应用程序的有效性。
Many applications of machine learning on discrete domains, such as learning preference functions in recommender systems or auctions, can be reduced to estimating a set function that is sparse in the Fourier domain. In this work, we present a new family of algorithms for learning Fourier-sparse set functions. They require at most $nk - k \log_2 k + k$ queries (set function evaluations), under mild conditions on the Fourier coefficients, where $n$ is the size of the ground set and $k$ the number of non-zero Fourier coefficients. In contrast to other work that focused on the orthogonal Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms that offer different notions of Fourier-sparsity. These naturally arise when modeling, e.g., sets of items forming substitutes and complements. We demonstrate effectiveness on several real-world applications.
