In:
Knowledge and Information Systems, Springer Science and Business Media LLC, Vol. 62, No. 11 ( 2020-11), p. 4223-4253
Abstract:
We consider the task of discovering functional dependencies in data for target attributes of interest. To solve it, we have to answer two questions: How do we quantify the dependency in a model-agnostic and interpretable way as well as reliably against sample size and dimensionality biases? How can we efficiently discover the exact or $$\alpha $$ α -approximate top- k dependencies? We address the first question by adopting information-theoretic notions. Specifically, we consider the mutual information score, for which we propose a reliable estimator that enables robust optimization in high-dimensional data. To address the second question, we then systematically explore the algorithmic implications of using this measure for optimization. We show the problem is NP-hard and justify worst-case exponential-time as well as heuristic search methods. We propose two bounding functions for the estimator, which we use as pruning criteria in branch-and-bound search to efficiently mine dependencies with approximation guarantees. Empirical evaluation shows that the derived estimator has desirable statistical properties, the bounding functions lead to effective exact and greedy search algorithms, and when combined, qualitative experiments show the framework indeed discovers highly informative dependencies.
Type of Medium:
Online Resource
ISSN:
0219-1377
,
0219-3116
DOI:
10.1007/s10115-020-01494-9
Language:
English
Publisher:
Springer Science and Business Media LLC
Publication Date:
2020
detail.hit.zdb_id:
2023541-0
detail.hit.zdb_id:
2036569-X
