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

Authors

  • Chris Wendler ETH Zurich
  • Andisheh Amrollahi ETH Zurich
  • Bastian Seifert ETH Zurich
  • Andreas Krause ETH Zurich
  • Markus Püschel ETH Zurich

Keywords:

Learning Preferences or Rankings, Active Learning, Auctions and Market-Based Systems

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.

Downloads

Published

2021-05-18

How to Cite

Wendler, C., Amrollahi, A., Seifert, B., Krause, A., & Püschel, M. (2021). Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10283-10292. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17232

Issue

Section

AAAI Technical Track on Machine Learning V