Regularizing conjunctive features for classification

We consider the feature-generation task wherein we are given a database with entities labeled 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 sep...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2021-08, Vol.119, p.97-124
Main Authors: Barceló, Pablo, Baumgartner, Alexander, Dalmau, Victor, Kimelfeld, Benny
Format: Article
Language:English
Subjects:
Classification
Conjunctive queries
Feature generation
Generalized hypertree width
Separability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the feature-generation task wherein we are given a database with entities labeled 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.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2021.01.003