Database Seminar: Pablo Barcelo (PUC Chile) – “Regularizing Conjunctive Features for Classification”

Speaker: Pablo Barcelo

Location: Soda 380

Date: September 6, 2023

Time: 11 AM – 12 PM PST

Title: “Regularizing Conjunctive Features for Classification”


In this presentation, we study how data management tools can be used in enhancing feature generation for machine learning classification tasks. This allows us to use the rich relational structure embedded in the data to construct appropriate features for separating our training set. In particular, 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.