Graphical models are powerful descriptions of joint probability distributions. We have developed techniques for efficiently scaling exact methods to thousands of variables.
Tutorial at ICDM-15, with Francois Petitjean.
Presentation of our award winning paper at SDM15.
Check out the promotional video for our KDD-2106 paper:
Check out our interactive visualisation of the network Chordalysis learns about associated stock movements within the S&P500:
Publications
Lee, Loong Kuan; Webb, Geoffrey I.; Schmidt, Daniel F.; Piatkowski, Nico
Knowledge and Information Systems, vol. 66, pp. 7527-7556, 2024, ISSN: 0219-3116.
@article{Lee2024,
title = {Computing marginal and conditional divergences between decomposable models with applications in quantum computing and earth observation},
author = {Loong Kuan Lee and Geoffrey I. Webb and Daniel F. Schmidt and Nico Piatkowski},
doi = {10.1007/s10115-024-02191-7},
issn = {0219-3116},
year = {2024},
date = {2024-01-01},
journal = {Knowledge and Information Systems},
volume = {66},
pages = {7527-7556},
publisher = {Springer Science and Business Media LLC},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Lee, Loong Kuan; Piatkowski, Nico; Petitjean, Francois; Webb, Geoffrey I.
Computing Divergences between Discrete Decomposable Models
Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 10, pp. 12243-12251, 2023.
@article{Lee2023,
title = {Computing Divergences between Discrete Decomposable Models},
author = {Loong Kuan Lee and Nico Piatkowski and Francois Petitjean and Geoffrey I. Webb},
doi = {10.1609/aaai.v37i10.26443},
year = {2023},
date = {2023-06-01},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
volume = {37},
number = {10},
pages = {12243-12251},
abstract = {There are many applications that benefit from computing the exact divergence between 2 discrete probability measures, including machine learning. Unfortunately, in the absence of any assumptions on the structure or independencies within these distributions, computing the divergence between them is an intractable problem in high dimensions. We show that we are able to compute a wide family of functionals and divergences, such as the alpha-beta divergence, between two decomposable models, i.e. chordal Markov networks, in time exponential to the treewidth of these models. The alpha-beta divergence is a family of divergences that include popular divergences such as the Kullback-Leibler divergence, the Hellinger distance, and the chi-squared divergence. Thus, we can accurately compute the exact values of any of this broad class of divergences to the extent to which we can accurately model the two distributions using decomposable models.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
There are many applications that benefit from computing the exact divergence between 2 discrete probability measures, including machine learning. Unfortunately, in the absence of any assumptions on the structure or independencies within these distributions, computing the divergence between them is an intractable problem in high dimensions. We show that we are able to compute a wide family of functionals and divergences, such as the alpha-beta divergence, between two decomposable models, i.e. chordal Markov networks, in time exponential to the treewidth of these models. The alpha-beta divergence is a family of divergences that include popular divergences such as the Kullback-Leibler divergence, the Hellinger distance, and the chi-squared divergence. Thus, we can accurately compute the exact values of any of this broad class of divergences to the extent to which we can accurately model the two distributions using decomposable models.
Lee, Loong Kuan; Webb, Geoffrey I; Schmidt, Daniel F; Piatkowski, Nico
Computing Marginal and Conditional Divergences between Decomposable Models with Applications
Proceedings of the IEEE International Conference on Data Mining (ICDM), pp. 239-248, IEEE 2023.
@inproceedings{Lee2023a,
title = {Computing Marginal and Conditional Divergences between Decomposable Models with Applications},
author = {Loong Kuan Lee and Geoffrey I Webb and Daniel F Schmidt and Nico Piatkowski},
doi = {10.1109/ICDM58522.2023.00033},
year = {2023},
date = {2023-01-01},
booktitle = {Proceedings of the IEEE International Conference on Data Mining (ICDM)},
pages = {239-248},
organization = {IEEE},
abstract = {The ability to compute the exact divergence between two high-dimensional distributions is useful in many applications but doing so naively is intractable. Computing the alpha-beta divergence\textemdasha family of divergences that includes the Kullback-Leibler divergence and Hellinger distance\textemdashbetween the joint distribution of two decomposable models, i.e chordal Markov networks, can be done in time exponential in the treewidth of these models. However, reducing the dissimilarity between two high-dimensional objects to a single scalar value can be uninformative. Furthermore, in applications such as supervised learning, the divergence over a conditional distribution might be of more interest. Therefore, we propose an approach to compute the exact alpha-beta divergence between any marginal or conditional distribution of two decomposable models. Doing so tractably is non-trivial as we need to decompose the divergence between these distributions and therefore, require a decomposition over the marginal and conditional distributions of these models. Consequently, we provide such a decomposition and also extend existing work to compute the marginal and conditional alpha-beta divergence between these decompositions. We then show how our method can be used to analyze distributional changes by first applying it to a benchmark image dataset. Finally, based on our framework, we propose a novel way to quantify the error in contemporary superconducting quantum computers. Code for all experiments is available at: https://lklee.dev/pub/2023-icdm/code.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The ability to compute the exact divergence between two high-dimensional distributions is useful in many applications but doing so naively is intractable. Computing the alpha-beta divergence—a family of divergences that includes the Kullback-Leibler divergence and Hellinger distance—between the joint distribution of two decomposable models, i.e chordal Markov networks, can be done in time exponential in the treewidth of these models. However, reducing the dissimilarity between two high-dimensional objects to a single scalar value can be uninformative. Furthermore, in applications such as supervised learning, the divergence over a conditional distribution might be of more interest. Therefore, we propose an approach to compute the exact alpha-beta divergence between any marginal or conditional distribution of two decomposable models. Doing so tractably is non-trivial as we need to decompose the divergence between these distributions and therefore, require a decomposition over the marginal and conditional distributions of these models. Consequently, we provide such a decomposition and also extend existing work to compute the marginal and conditional alpha-beta divergence between these decompositions. We then show how our method can be used to analyze distributional changes by first applying it to a benchmark image dataset. Finally, based on our framework, we propose a novel way to quantify the error in contemporary superconducting quantum computers. Code for all experiments is available at: https://lklee.dev/pub/2023-icdm/code.
Petitjean, F.; Webb, G. I.
Scalable Learning of Graphical Models
Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD-16, pp. 2131-2132, ACM Press, 2016.
@inproceedings{PetitjeanWebbTut16,
title = {Scalable Learning of Graphical Models},
author = {F. Petitjean and G. I. Webb},
url = {http://dl.acm.org/authorize?N19101},
year = {2016},
date = {2016-01-01},
booktitle = {Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD-16},
pages = {2131-2132},
publisher = {ACM Press},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Webb, Geoffrey I.; Petitjean, Francois
A multiple test correction for streams and cascades of statistical hypothesis tests
Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD-16, pp. 1255-1264, ACM Press, 2016.
@inproceedings{WebbPetitjean16,
title = {A multiple test correction for streams and cascades of statistical hypothesis tests},
author = {Geoffrey I. Webb and Francois Petitjean},
url = {http://dl.acm.org/authorize?N19100},
doi = {10.1145/2939672.2939775},
year = {2016},
date = {2016-01-01},
booktitle = {Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD-16},
pages = {1255-1264},
publisher = {ACM Press},
abstract = {Statistical hypothesis testing is a popular and powerful tool for inferring knowledge from data. For every such test performed, there is always a non-zero probability of making a false discovery, i.e.~rejecting a null hypothesis in error. Familywise error rate (FWER) is the probability of making at least one false discovery during an inference process. The expected FWER grows exponentially with the number of hypothesis tests that are performed, almost guaranteeing that an error will be committed if the number of tests is big enough and the risk is not managed; a problem known as the multiple testing problem. State-of-the-art methods for controlling FWER in multiple comparison settings require that the set of hypotheses be pre-determined. This greatly hinders statistical testing for many modern applications of statistical inference, such as model selection, because neither the set of hypotheses that will be tested, nor even the number of hypotheses, can be known in advance.
This paper introduces Subfamilywise Multiple Testing, a multiple-testing correction that can be used in applications for which there are repeated pools of null hypotheses from each of which a single null hypothesis is to be rejected and neither the specific hypotheses nor their number are known until the final rejection decision is completed.
To demonstrate the importance and relevance of this work to current machine learning problems, we further refine the theory to the problem of model selection and show how to use Subfamilywise Multiple Testing for learning graphical models.
We assess its ability to discover graphical models on more than 7,000 datasets, studying the ability of Subfamilywise Multiple Testing to outperform the state of the art on data with varying size and dimensionality, as well as with varying density and power of the present correlations. Subfamilywise Multiple Testing provides a significant improvement in statistical efficiency, often requiring only half as much data to discover the same model, while strictly controlling FWER.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Statistical hypothesis testing is a popular and powerful tool for inferring knowledge from data. For every such test performed, there is always a non-zero probability of making a false discovery, i.e.~rejecting a null hypothesis in error. Familywise error rate (FWER) is the probability of making at least one false discovery during an inference process. The expected FWER grows exponentially with the number of hypothesis tests that are performed, almost guaranteeing that an error will be committed if the number of tests is big enough and the risk is not managed; a problem known as the multiple testing problem. State-of-the-art methods for controlling FWER in multiple comparison settings require that the set of hypotheses be pre-determined. This greatly hinders statistical testing for many modern applications of statistical inference, such as model selection, because neither the set of hypotheses that will be tested, nor even the number of hypotheses, can be known in advance.
This paper introduces Subfamilywise Multiple Testing, a multiple-testing correction that can be used in applications for which there are repeated pools of null hypotheses from each of which a single null hypothesis is to be rejected and neither the specific hypotheses nor their number are known until the final rejection decision is completed.
To demonstrate the importance and relevance of this work to current machine learning problems, we further refine the theory to the problem of model selection and show how to use Subfamilywise Multiple Testing for learning graphical models.
We assess its ability to discover graphical models on more than 7,000 datasets, studying the ability of Subfamilywise Multiple Testing to outperform the state of the art on data with varying size and dimensionality, as well as with varying density and power of the present correlations. Subfamilywise Multiple Testing provides a significant improvement in statistical efficiency, often requiring only half as much data to discover the same model, while strictly controlling FWER.
This paper introduces Subfamilywise Multiple Testing, a multiple-testing correction that can be used in applications for which there are repeated pools of null hypotheses from each of which a single null hypothesis is to be rejected and neither the specific hypotheses nor their number are known until the final rejection decision is completed.
To demonstrate the importance and relevance of this work to current machine learning problems, we further refine the theory to the problem of model selection and show how to use Subfamilywise Multiple Testing for learning graphical models.
We assess its ability to discover graphical models on more than 7,000 datasets, studying the ability of Subfamilywise Multiple Testing to outperform the state of the art on data with varying size and dimensionality, as well as with varying density and power of the present correlations. Subfamilywise Multiple Testing provides a significant improvement in statistical efficiency, often requiring only half as much data to discover the same model, while strictly controlling FWER.
Petitjean, F.; Webb, G. I.
Scaling log-linear analysis to datasets with thousands of variables
Proceedings of the 2015 SIAM International Conference on Data Mining, pp. 469-477, 2015.
@inproceedings{PetitjeanWebb15,
title = {Scaling log-linear analysis to datasets with thousands of variables},
author = {F. Petitjean and G. I. Webb},
url = {http://epubs.siam.org/doi/pdf/10.1137/1.9781611974010.53},
year = {2015},
date = {2015-01-01},
booktitle = {Proceedings of the 2015 SIAM International Conference on Data Mining},
pages = {469-477},
abstract = {Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We have recently shown that, if we ensure that the graph supporting the log-linear model is chordal, log-linear analysis can be applied to datasets with hundreds of variables without sacrificing the statistical soundness [21]. However, further scalability remained limited, because state-of-the-art techniques have to examine every edge at every step of the search. This paper makes the following contributions: 1) we prove that only a very small subset of edges has to be considered at each step of the search; 2) we demonstrate how to efficiently find this subset of edges and 3) we show how to efficiently keep track of the best edges to be subsequently added to the initial model. Our experiments, carried out on real datasets with up to 2000 variables, show that our contributions make it possible to gain about 4 orders of magnitude, making log-linear analysis of datasets with thousands of variables possible in seconds instead of days.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We have recently shown that, if we ensure that the graph supporting the log-linear model is chordal, log-linear analysis can be applied to datasets with hundreds of variables without sacrificing the statistical soundness [21]. However, further scalability remained limited, because state-of-the-art techniques have to examine every edge at every step of the search. This paper makes the following contributions: 1) we prove that only a very small subset of edges has to be considered at each step of the search; 2) we demonstrate how to efficiently find this subset of edges and 3) we show how to efficiently keep track of the best edges to be subsequently added to the initial model. Our experiments, carried out on real datasets with up to 2000 variables, show that our contributions make it possible to gain about 4 orders of magnitude, making log-linear analysis of datasets with thousands of variables possible in seconds instead of days.
Petitjean, F.; Allison, L.; Webb, G. I.
A Statistically Efficient and Scalable Method for Log-Linear Analysis of High-Dimensional Data
Proceedings of the 14th IEEE International Conference on Data Mining, pp. 480-489, 2014.
@inproceedings{PetitjeanEtAl14a,
title = {A Statistically Efficient and Scalable Method for Log-Linear Analysis of High-Dimensional Data},
author = {F. Petitjean and L. Allison and G. I. Webb},
url = {http://dx.doi.org/10.1109/ICDM.2014.23},
year = {2014},
date = {2014-01-01},
booktitle = {Proceedings of the 14th IEEE International Conference on Data Mining},
pages = {480-489},
abstract = {Log-linear analysis is the primary statistical approach to discovering conditional dependencies between the variables of a dataset. A good log-linear analysis method requires both high precision and statistical efficiency. High precision means that the risk of false discoveries should be kept very low. Statistical efficiency means that the method should discover actual associations with as few samples as possible. Classical approaches to log-linear analysis make use of Chi-square tests to control this balance between quality and complexity. We present an information-theoretic approach to log-linear analysis. We show that our approach 1) requires significantly fewer samples to discover the true associations than statistical approaches \textendash statistical efficiency \textendash 2) controls for the risk of false discoveries as well as statistical approaches \textendash high precision - and 3) can perform the discovery on datasets with hundreds of variables on a standard desktop computer \textendash computational efficiency.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Log-linear analysis is the primary statistical approach to discovering conditional dependencies between the variables of a dataset. A good log-linear analysis method requires both high precision and statistical efficiency. High precision means that the risk of false discoveries should be kept very low. Statistical efficiency means that the method should discover actual associations with as few samples as possible. Classical approaches to log-linear analysis make use of Chi-square tests to control this balance between quality and complexity. We present an information-theoretic approach to log-linear analysis. We show that our approach 1) requires significantly fewer samples to discover the true associations than statistical approaches – statistical efficiency – 2) controls for the risk of false discoveries as well as statistical approaches – high precision - and 3) can perform the discovery on datasets with hundreds of variables on a standard desktop computer – computational efficiency.
Petitjean, F.; Webb, G. I.; Nicholson, A. E.
Scaling log-linear analysis to high-dimensional data
Proceedings of the 13th IEEE International Conference on Data Mining, pp. 597-606, 2013.
@inproceedings{PetitjeanEtAl13,
title = {Scaling log-linear analysis to high-dimensional data},
author = {F. Petitjean and G. I. Webb and A. E. Nicholson},
doi = {10.1109/ICDM.2013.17},
year = {2013},
date = {2013-01-01},
booktitle = {Proceedings of the 13th IEEE International Conference on Data Mining},
pages = {597-606},
abstract = {Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We develop an efficient approach to log-linear analysis that scales to hundreds of variables by melding the classical statistical machinery of log-linear analysis with advanced data mining techniques from association discovery and graphical modeling.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We develop an efficient approach to log-linear analysis that scales to hundreds of variables by melding the classical statistical machinery of log-linear analysis with advanced data mining techniques from association discovery and graphical modeling.