02/02/2021

Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases

Chris Wendler, Andisheh Amrollahi, Bastian Seifert, Andreas Krause, Markus Püschel

Keywords:

Abstract Paper Similar Papers

Abstract: 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 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 (WHT), 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949297
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 24:33 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 17:23 
 0
 0
 0
 0
 4:46 
 0
 0
 0
 0
 14:26 
 0
 0
 0
 0
 10:55 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 7:41 
 0
 0
 0
 0
 3:25 
 0
 0
 0
 1
 3:31 
 0
 1
 0
 0
 5:10 
 0
 0
 0
 0
 18:51 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 13:10 
 0
 0
 0
 0
 3:07 
 0
 0
 0
 0
 13:14 
 0
 0
 0
 0
 5:33 
 0
 0
 0
 0
 13:22 
 0
 0
 0
 0
 12:11 
 0
 0
 0
 0
 3:54 
 0
 0
 0
 0
 16:59 
 0
 0
 0
 1
 5:11 
 0
 0
 0
 0
 13:54 
 0
 0
 0
 0
 8:38 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 8:04 
 0
 0
 0
 0
 3:55 
 0
 0
 0
 0
 3:44 
 0
 0
 0
 0
 4:25 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 12:32 
 0
 0
 0
 0
 24:38 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 13:00 
 0
 0
 0
 0
 14:50