Learning Set Functions with Implicit Differentiation
Gözde Özcan, Chengzhi Shi, Stratis Ioannidis · 2024
Read Learning Set Functions with Implicit Differentiation by Gözde Özcan, Chengzhi Shi, Stratis Ioannidis (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11239.txt.
Introduction
Gözde Özcan, Chengzhi Shi, and Stratis Ioannidis improve a method for learning set functions, the kind of model that scores whole collections of items at once. Earlier work learned such functions from an oracle that reveals optimal subsets, fitting an energy-based model by fixed-point iterations. The catch was cost: backpropagating through many iterations stacks up huge Jacobians and quickly becomes impractical. The authors replace that step with implicit differentiation and study when the fixed-point process settles down.
Tests on synthetic and real tasks back up the efficiency claim. The applications include product recommendation, spotting anomalous sets, and selecting compounds. In each case the new method reaches good answers with far less computation than the direct approach. The work makes oracle-based set learning usable at scales where the older training loop would have stalled.
Catalog record
| CREATOR | Gözde Özcan, Chengzhi Shi, Stratis Ioannidis |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11239
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Set Functions with Implicit Differentiation Gözde Özcan, Chengzhi Shi, Stratis Ioannidis Abstract Ou et al. (2022) introduce the problem of learning set functions from data generated by a so-called optimal subset oracle. Their approach approximates the underlying utility function with an energy-based model, whose parameters are estimated via mean-field variational inference. Ou et al. (2022) show this reduces to fixed point iterations; however, as the number of iterations increases, automatic differentiation quickly becomes computationally prohibitive due to the size of the Jacobians that are stacked during backpropagation. We address this challenge with implicit differentiation and examine the convergence conditions for the fixed-point iterations. We empirically demonstrate the efficiency of our method on synthetic and real-world subset selection applications including product recommendation, set anomaly detection and compound selection tasks. Department of Electrical and Computer Engineering Northeastern University Boston, MA 02115, USA {gozcan, cshi, ioannidis}@ece.neu.edu 1 Introduction Many interesting applications operate with set-valued outputs and/or inputs. Examples include product recommendation ( Bonab et al. 2021 ; Schafer, Konstan, and Riedl 1999 ) , compound selection ( Ning, Walters, and Karypis 2011 ) , set matching ( Saito et al. 2020 ) , set retrieval ( Feng, Zhou, and Lan 2016 ) , point cloud processing ( Zhao et al. 2019 ; Gionis, Gunopulos, and Koudas 2001 ) , set prediction ( Zhang, Hare, and Prugel-Bennett 2019 ) , and set anomaly detection ( Mašková et al. 2024 ) , to name a few. Several recent works ( Zaheer et al. 2017 ; Lee et al. 2019 ) apply neural networks to learn set functions from input/function value pairs, assuming access to a dataset generated by a function value oracle. In other words, they assume having access to a dataset generated by an oracle that evaluates the value of the set function for any given input set. Recently, Ou et al. (2022) proposed an approximate maximum likelihood estimation framework under the supervision of a so-called optimal subset oracle. In contrast to traditional function value oracles, a label produced by an optimal subset oracle is the subset that maximizes an (implicit) utility set function, in the face of several alternatives. The goal of inference is to learn, in a parametric form, this utility function, under which observed oracle selections are optimal. As MLE is intractable in this setting, Ou et al. (2022) propose performing variational inference instead. In turn, they show that approximating the distribution of oracle selections requires solving a fixed-point equation per sample. However, these fixed-point iterations may diverge in practice. In addition, Ou et al. (2022) implement these iterations via loop unrolling , i.e., by stacking up neural network layers across iterations, and calculating the gradient using automatic differentiation; this makes backpropagation expensive, limiting their experiments to only a handful of iterations. In this work, we establish a condition under which the fixed-point iterations proposed by Ou et al. (2022) are guaranteed to converge. We also propose a more effective gradient computation utilizing the recent advances in implicit differentiation ( Bai, Kolter, and Koltun 2019 ; Kolter, Duvenaud, and Johnson 2020 ; Huang, Bai, and Kolter 2021 ) , instead of unrolling the fixed-point iterations via automatic differentiation ( Paszke et al. 2017 ) . This corresponds to differentiating after infinite fixed point iterations, while remaining tractable; we experimentally show that this improves the predictive performance of the inferred models. We make the following contributions: • We prove that, as long as the multilinear relaxation ( Calinescu et al. 2011 ) of the objective function is bounded, and this bound is inversely proportional to the size of the ground set, the fixed-point iterations arising during the MLE framework introduced by Ou et al. (2022) converge to a unique solution, regardless of the starting point. • We propose a more effective gradient computation by using implicit differentiation instead of unrolling the fixed-point iterations via automatic differentiation. To the best of our knowledge, we are the first ones to propose utilizing implicit differentiation in the context of learning set functions. • We conduct experiments to show the advantage of our approach on multiple subset selection applications including set anomaly detection, product recommendation, and compound selection tasks. We also show, in practice, that the fixed-point iterations converge by normalizing the gradient of the multilinear relaxation. The remainder of the paper is organized as follows. We present related literature in Sec. 2 . We summarize the learning set functions with optimal subset oracle setting introduced by Ou et al. (2022) in Sec. 3 . We state our main contributions in Sec. 4 . We present our experimental results in Sec. 5 and we conclude in Sec. 6 . 2 Related Work Learning Set Functions from Oracles. There is a line of work where a learning algorithm is assumed to have access to the value of an unknown utility function for a given set ( Feldman and Kothari 2014 ; Balcan and Harvey 2018 ; Zaheer et al. 2017 ; Lee et al. 2019 ; Wendler et al. 2021 ; De and Chakrabarti 2022 ) . This is the function value oracle setting. Zaheer et al. (2017) and De and Chakrabarti (2022) regress over input set - function value pairs by minimizing the squared loss of the predictions while Lee et al. (2019) minimize the mean absolute error. However, obtaining a function value to a given subset is not an easy task for real-world applications. The value of a set may not be straightforward to quantify or can be expensive to compute. Alternatively, Tschiatschek, Sahin, and Krause (2018) and Ou et al. (2022) assume having access to an optimal subset oracle for a given ground set in the training data. Similarly, we do not learn the objective function explicitly from input set - output value pairs. We learn it implicitly in the optimal subset oracle setting. Learning Set Functions with Neural Networks. Multiple works aim to extend the capabilities of neural networks for functions on discrete domains, i.e., set functions ( Zaheer et al. 2017 ; Wendler, Püschel, and Alistarh 2019 ; Soelch et al. 2019 ; Lee et al. 2019 ; Wagstaff et al. 2019 ; Kim et al. 2021 ; Zhang et al. 2022a ; Giannone and Winther 2022 ) . Diverging from the traditional paradigm where the input data is assumed to be in a fixed dimensional vector format, set functions are characterized by their permutation invariance , i.e., the output of a set does not depend on the order of its elements. We refer the reader to a survey about permutation-invariant networks by Kimura et al. (2024) for a more detailed overview. In this work, we also enforce permutation invariance by combining the energy-based model in Sec. 3.1 with deep sets ( Zaheer et al. 2017 ) , following the proposed method of Ou et al. (2022) (see also App. A ). Karalias et al. (2022) integrate neural networks with set functions by leveraging extensions of these functions to the continuous domain. Note that, their goal is not to learn a set function but to learn with a set function, which differs from our objective. Learning Submodular Functions. It is common to impose some structure on the objective when learning set