{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:12:40Z","timestamp":1762809160315,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T00:00:00Z","timestamp":1636675200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This article presents a novel and remarkably efficient method of computing the statistical G-test made possible by exploiting a connection with the fundamental elements of information theory: by writing the G statistic as a sum of joint entropy terms, its computation is decomposed into easily reusable partial results with no change in the resulting value. This method greatly improves the efficiency of applications that perform a series of G-tests on permutations of the same features, such as feature selection and causal inference applications because this decomposition allows for an intensive reuse of these partial results. The efficiency of this method is demonstrated by implementing it as part of an experiment involving IPC\u2013MB, an efficient Markov blanket discovery algorithm, applicable both as a feature selection algorithm and as a causal inference method. The results show outstanding efficiency gains for IPC\u2013MB when the G-test is computed with the proposed method, compared to the unoptimized G-test, but also when compared to IPC\u2013MB++, a variant of IPC\u2013MB which is enhanced with an AD\u2013tree, both static and dynamic. Even if this proposed method of computing the G-test is presented here in the context of IPC\u2013MB, it is in fact bound neither to IPC\u2013MB in particular, nor to feature selection or causal inference applications in general, because this method targets the information-theoretic concept that underlies the G-test, namely conditional mutual information. This aspect grants it wide applicability in data sciences.<\/jats:p>","DOI":"10.3390\/e23111501","type":"journal-article","created":{"date-parts":[[2021,11,14]],"date-time":"2021-11-14T20:48:36Z","timestamp":1636922916000},"page":"1501","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Accelerating Causal Inference and Feature Selection Methods through G-Test Computation Reuse"],"prefix":"10.3390","volume":"23","author":[{"given":"Camil","family":"B\u0103ncioiu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Electrical Engineering, Lucian Blaga University of Sibiu, 550024 Sibiu, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8100-1379","authenticated-orcid":false,"given":"Remus","family":"Brad","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Electrical Engineering, Lucian Blaga University of Sibiu, 550024 Sibiu, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1214\/09-SS057","article-title":"Causal inference in statistics: An overview","volume":"3","author":"Pearl","year":"2009","journal-title":"Stat. Surv."},{"key":"ref_2","unstructured":"Pearl, J. (2008). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Revised Second Printing; Kaufmann."},{"key":"ref_3","unstructured":"Margaritis, D., and Thrun, S. (2000). Bayesian network induction via local neighborhoods. Advances in Neural Information Processing Systems, MIT Press."},{"key":"ref_4","first-page":"321","article-title":"Markov blanket based feature selection: A review of past decade","volume":"Volume 1","author":"Fu","year":"2010","journal-title":"Proceedings of the World Congress on Engineering"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.ijar.2006.06.008","article-title":"Towards scalable and data efficient learning of Markov boundaries","volume":"45","author":"Pena","year":"2007","journal-title":"Int. J. Approx. Reason."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Fu, S., and Desmarais, M.C. (2008, January 28\u201330). Fast Markov blanket discovery algorithm via local learning within single pass. Proceedings of the Conference of the Canadian Society for Computational Studies of Intelligence, Windsor, ON, Canada.","DOI":"10.1007\/978-3-540-68825-9_10"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tsamardinos, I., Aliferis, C.F., and Statnikov, A. (2003, January 24\u201327). Time and sample efficient discovery of Markov blankets and direct causal relations. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956838"},{"key":"ref_8","first-page":"85","article-title":"Efficiency Optimizations for Koller and Sahami\u2019s feature selection algorithm","volume":"22","author":"Vintan","year":"2019","journal-title":"Rom. J. Inf. Sci. Technol."},{"key":"ref_9","unstructured":"Koller, D., and Sahami, M. (1996, January 3\u20136). Toward optimal feature selection. Proceedings of the 13th International Conference on Machine Learning, Bari, Italy."},{"key":"ref_10","first-page":"27","article-title":"Conditional likelihood maximisation: A unifying framework for information theoretic feature selection","volume":"13","author":"Brown","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"ref_11","unstructured":"Tsamardinos, I., Aliferis, C., Statnikov, A., and Statnikov, E. (2003, January 12\u201314). Algorithms for Large Scale Markov Blanket Discovery. Proceedings of the 16th International FLAIRS Conference, St. Augustine, FL, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Spirtes, P., Glymour, C., and Scheines, R. (2000). Causation, Prediction, and Search, MIT Press.","DOI":"10.7551\/mitpress\/1754.001.0001"},{"key":"ref_13","first-page":"21","article-title":"HITON: A novel Markov Blanket algorithm for optimal variable selection","volume":"2003","author":"Aliferis","year":"2003","journal-title":"AMIA Annu. Symp. Proc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.453","article-title":"Cached sufficient statistics for efficient machine learning with large datasets","volume":"8","author":"Moore","year":"1998","journal-title":"J. Artif. Intell. Res."},{"key":"ref_15","unstructured":"Komarek, P., and Moore, A.W. (2000). A Dynamic Adaptation of AD\u2013trees for Efficient Machine Learning on Large Data Sets. Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc.. ICML \u201900."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Liu, J., Cheung, Y., and Yin, H. (2003). AD+Tree: A Compact Adaptation of Dynamic AD\u2013Trees for Efficient Machine Learning on Large Data Sets. Intelligent Data Engineering and Automated Learning, Springer.","DOI":"10.1007\/b11717"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s10994-018-5748-7","article-title":"A greedy feature selection algorithm for Big Data of high dimensionality","volume":"108","author":"Tsamardinos","year":"2019","journal-title":"Mach. Learn."},{"key":"ref_18","unstructured":"Tsagris, M. (2017). Conditional independence test for categorical data using Poisson log-linear model. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Agresti, A. (2003). Categorical Data Analysis, John Wiley & Sons.","DOI":"10.1002\/0471249688"},{"key":"ref_20","unstructured":"Lehmann, E.L., and Romano, J.P. (2005). Testing Statistical Hypotheses, Springer. [3rd ed.]."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Al-Labadi, L., Fazeli Asl, F., and Saberi, Z. (2021). A test for independence via Bayesian nonparametric estimation of mutual information. Can. J. Stat.","DOI":"10.1002\/cjs.11645"},{"key":"ref_22","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley-Interscience. [2nd ed.]."},{"key":"ref_23","unstructured":"McDonald, J.H. (2014). Handbook of Biological Statistics, Sparky House Publishing. [3rd ed.]."},{"key":"ref_24","unstructured":"Everitt, B. (2002). The Cambridge Dictionary of Statistics, Cambridge University Press."},{"key":"ref_25","unstructured":"Lamont, A. (2015). What Exactly Are Degrees of Freedom?: A Tool for Graduate Students in the Social Sciences, University of South Carolina."},{"key":"ref_26","unstructured":"B\u0103ncioiu, C. (2021, September 10). MBTK, a Library for Studying Markov Boundary Algorithms. Available online: https:\/\/github.com\/camilbancioiu\/mbtk."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","article-title":"Array programming with NumPy","volume":"585","author":"Harris","year":"2020","journal-title":"Nature"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","article-title":"SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python","volume":"17","author":"Virtanen","year":"2020","journal-title":"Nat. Methods"},{"key":"ref_29","unstructured":"(2021, May 03). Lark\u2014A Parsing Toolkit for Python. Available online: https:\/\/github.com\/lark-parser\/lark."},{"key":"ref_30","unstructured":"Scutari, M. (2020, June 06). bnlearn\u2014An R Package for Bayesian Network Learning and Inference. Available online: https:\/\/www.bnlearn.com\/."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Hunter, J., Cookson, J., and Wyatt, J. (1989). The ALARM Monitoring System: A Case Study with two Probabilistic Inference Techniques for Belief Networks. AIME 89, Springer.","DOI":"10.1007\/978-3-642-93437-7"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Jameson, A., Paris, C., and Tasso, C. (1997). On-Line Student Modeling for Coached Problem Solving Using Bayesian Networks. User Modeling, Springer.","DOI":"10.1007\/978-3-7091-2670-7"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1501\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:29:25Z","timestamp":1760167765000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,12]]},"references-count":32,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["e23111501"],"URL":"https:\/\/doi.org\/10.3390\/e23111501","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,11,12]]}}}