KIT | KIT-Bibliothek | Impressum | Datenschutz

Iterative estimation of mutual information with error bounds

Vollmer, M.; Böhm, K.

Mutual Information (MI) is an established measure for linear and nonlinear dependencies between two variables. Estimating MI is nontrivial and requires notable computation power for high estimation quality. While some estimation techniques allow trading result quality for lower runtimes, this tradeoff is fixed per task and cannot be adjusted. If the available time is unknown in advance or is overestimated, one may need to abort the estimation without any result. Conversely, when there are several estimation tasks, and one wants to budget computation time between them, there currently is no efficient way to adjust it dynamically based on certain targets, e.g., high MI values or MI values close to a constant. In this article, we present an iterative estimator of MI. Our method offers an estimate with low quality near-instantly and improves this estimate in fine grained steps with more computation time. The estimate also converges towards the result of a conventional estimator. We prove that the time complexity for this convergence is only slightly slower than non-iterative estimation. Additionally, with each step our estimator also tightens statistical guarantees regarding the convergence result, i.e., confidence intervals, progressively. ... mehr

Open Access Logo

Verlagsausgabe §
DOI: 10.5445/IR/1000095164
Veröffentlicht am 11.06.2019
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Proceedingsbeitrag
Jahr 2019
Sprache Englisch
Identifikator ISBN: 978-3-89318-081-3
ISSN: 2367-2005
KITopen-ID: 1000095164
Erschienen in 22nd International Conference on Extending Database Technology, EDBT 2019; Lisbon; Portugal; 26 March 2019 through 29 March 2019. Ed.: Z. Kaoudi
Verlag, Konstanz
Seiten 73-84
Serie Advances in Database Technology - EDBT ; 2019-March
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page