Finding (functional) dependencies between attributes in databases is a well-known problem with applications in knowledge discovery, feature selection, and database management. While the recently introduced reliable fraction of information measure allows to soundly quantify dependence in a way that avoids overfitting when optimizing over high-dimensional spaces, the algorithmic implications of using this score have not yet been systematically explored. This includes the computational complexity of the resulting optimization problem.
To this end, this paper provides the following contributions: We show that the problem of maximizing the reliable fraction of information is NP-hard, which justifies the usage of worst-case exponential-time as well as heuristic search methods that do not guarantee optimal solutions. We then greatly improve the practical performance for both of these optimization styles by deriving a novel admissible bounding function, which has an unbounded potential for additional pruning over the previously proposed one. Finally, we empirically investigate for the first time the approximation ratio of the greedy algorithm and show that in fact it produces highly competitive results in a fraction of time needed for complete branch-and-bound style search. All findings are evaluated on a wide range of real-world datasets that are publicly available along with the implementation of the algorithmic contributions.
Our results suggest that in scenarios where no hard optimality guarantees are required, greedy optimization is a good alternative to branch-and-bound for dependency discovery. Also, the definition of the tighter bounding function is potentially more generally applicable than just to the reliable fraction of information and might be transferrable to other dependency measures.
History
Preferred Citation
Panagiotis Mandros, Mario Boley and Jilles Vreeken. Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms (Extended Abstract). In: International Joint Conference on Artificial Intelligence (IJCAI). 2019.
Primary Research Area
Algorithmic Foundations and Cryptography
Secondary Research Area
Empirical and Behavioral Security
Name of Conference
International Joint Conference on Artificial Intelligence (IJCAI)
Legacy Posted Date
2019-12-09
Open Access Type
Unknown
BibTeX
@inproceedings{cispa_all_3003,
title = "Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms (Extended Abstract)",
author = "Mandros, Panagiotis and Boley, Mario and Vreeken, Jilles",
booktitle="{International Joint Conference on Artificial Intelligence (IJCAI)}",
year="2019",
}