Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases
| Autor: | Chris Wendler, Andisheh Amrollahi, Bastian Seifert, Andreas Krause, Markus Püschel |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Signal Processing (eess.SP)
FOS: Computer and information sciences Computer Science - Machine Learning Artificial Intelligence (cs.AI) Discrete Mathematics (cs.DM) Computer Science - Artificial Intelligence Statistics - Machine Learning FOS: Electrical engineering electronic engineering information engineering Machine Learning (stat.ML) General Medicine Electrical Engineering and Systems Science - Signal Processing Computer Science - Discrete Mathematics Machine Learning (cs.LG) |
| DOI: | 10.48550/arxiv.2010.00439 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|