Thesis linked to the implementation of the María de Maeztu Strategic Research Program.

Open access to PhD thesis carried out at the Department can be found at TDX

Please visit these pages for information on our PhD, MSc and BSc programs.

 

Back Barceló P, Baumgartner A, Dalmau V, Kimelfeld B. Regularizing Conjunctive Features for Classification. 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Barceló P, Baumgartner A, Dalmau V, Kimelfeld B. Regularizing Conjunctive Features for Classification. 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We consider the feature-generation task wherein we are given a database with entities labeled as positive and negative examples, and the goal is to find feature queries that allow for a linear separation between the two sets of examples. We focus on conjunctive feature queries, and explore two fundamental problems: (a) deciding whether separating feature queries exist (separability), and (b) generating such queries when they exist. In the approximate versions of these problems, we allow a predefined fraction of the examples to be misclassified. To restrict the complexity of the generated classifiers, we explore various ways of regularizing (i.e., imposing simplicity constraints on) them by limiting their dimension, the number of joins in feature queries, and their generalized hypertree width (ghw). Among other results, we show that the separability problem is tractable in the case of bounded ghw; yet, the generation problem is intractable, simply because the 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 ever explicitly generating the feature queries.

https://doi.org/10.1145/3294052.3319680