License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.31
URN: urn:nbn:de:0030-drops-146124
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14612/
Chen, Lin ;
Esfandiari, Hossein ;
Fu, Gang ;
Mirrokni, Vahab S. ;
Yu, Qian
Feature Cross Search via Submodular Optimization
Abstract
In this paper, we study feature cross search as a fundamental primitive in feature engineering. The importance of feature cross search especially for the linear model has been known for a while, with well-known textbook examples. In this problem, the goal is to select a small subset of features, combine them to form a new feature (called the crossed feature) by considering their Cartesian product, and find feature crosses to learn an accurate model. In particular, we study the problem of maximizing a normalized Area Under the Curve (AUC) of the linear model trained on the crossed feature column.
First, we show that it is not possible to provide an n^{1/log log n}-approximation algorithm for this problem unless the exponential time hypothesis fails. This result also rules out the possibility of solving this problem in polynomial time unless ? = NP. On the positive side, by assuming the naïve Bayes assumption, we show that there exists a simple greedy (1-1/e)-approximation algorithm for this problem. This result is established by relating the AUC to the total variation of the commutator of two probability measures and showing that the total variation of the commutator is monotone and submodular. To show this, we relate the submodularity of this function to the positive semi-definiteness of a corresponding kernel matrix. Then, we use Bochner’s theorem to prove the positive semi-definiteness by showing that its inverse Fourier transform is non-negative everywhere. Our techniques and structural results might be of independent interest.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs.ESA.2021.31,
author = {Chen, Lin and Esfandiari, Hossein and Fu, Gang and Mirrokni, Vahab S. and Yu, Qian},
title = {{Feature Cross Search via Submodular Optimization}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14612},
URN = {urn:nbn:de:0030-drops-146124},
doi = {10.4230/LIPIcs.ESA.2021.31},
annote = {Keywords: Feature engineering, feature cross, submodularity}
}
|
Keywords: |
|
Feature engineering, feature cross, submodularity |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
