Benny Kimelfeld

RL2, Publisher: Journal of Computer and System Sciences, Link>


Alexander Baumgartner, Benny Kimelfeld, Pablo Barceló, Victor Dalmau


We consider the feature-generation task wherein we are given a database with entities A1:K111 as positive and negative examples, and we want to find feature queries that linearly separate the two sets of examples. We focus on conjunctive feature queries, and explore two problems: (a) deciding if separating feature queries exist (separability), and (b) generating such queries when they exist. To restrict the complexity of the generated classifiers, we explore various ways of regularizing them by limiting their dimension, the number of joins in feature queries, and their generalized hypertreewidth (ghw). We show that the separability problem is tractable for bounded ghw; yet, the generation problem is not because feature queries might be too large. So, we explore a third problem: classifying new entities without necessarily generating the feature queries. Interestingly, in the case of bounded ghw we can efficiently classify without explicitly generating such queries.

38 visualizaciones Ir a la publicación

RL2, Publisher: ACM SIGMOD Record, Link>


Benny Kimelfeld, Ester Livshits, Leopoldo Bertossi, Moshe Sebag


Database tuples can be seen as players in the game of jointly realizing the answer to a query. Some tuples may contribute more than others to the outcome, which can be a binary value in the case of a Boolean query, a number for a numerical aggregate query, and so on. To quantify the contributions of tuples, we use the Shapley value that was introduced in cooperative game theory and has found applications in a plethora of domains. Specifically, the Shapley value of an individual tuple quantifies its contribution to the query. We investigate the applicability of the Shapley value in this setting, as well as the computational aspects of its calculation in terms of complexity, algorithms, and approximation.

13 visualizaciones Ir a la publicación