Review Articles

Compression schemes for concept classes induced by three types of discrete undirected graphical models

Tingting Luo ,

School of Mathematics and Statistics, Xidian University, Xi'an, People's Republic of China

Benchong Li

School of Mathematics and Statistics, Xidian University, Xi'an, People's Republic of China

Pages | Received 08 Nov. 2022, Accepted 14 Jul. 2023, Published online: 26 Sep. 2023,
  • Abstract
  • Full Article
  • References
  • Citations

Sample compression schemes were first proposed by Littlestone and Warmuth in 1986. Undirected graphical model is a powerful tool for classification in statistical learning. In this paper, we consider labelled compression schemes for concept classes induced by discrete undirected graphical models. For the undirected graph of two vertices with no edge, where one vertex takes two values and the other vertex can take any finite number of values, we propose an algorithm to establish a labelled compression scheme of size VC dimension of associated concept class. Further, we extend the result to other two types of undirected graphical models and show the existence of labelled compression schemes of size VC dimension for induced concept classes. The work of this paper makes a step forward in solving sample compression problem for concept class induced by a general discrete undirected graphical model.


  • Anstee, R. P., Rányai, L., & Sali, A. (2002). Shattering news. Graphs and Combinatorics18(1), 59–73. 
  • Ben-David, S., & Litman, A. (1998). Combinatorial variability of Vapnik–Chervonenkis classes with applications to sample compression schemes. Discrete Applied Mathematics86(1), 3–25. . 
  • Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987). Occam's razor. Information Processing Letters24(6), 377–380. .  
  • Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM36(4), 929–965. . 
  • Bollobás, B., & A. J. Radcliffe (1995). Defect sauer results. Journal of Combinatorial Theory, Series A72(2), 189–208. 
  • Chalopin, J., Chepoi, V., Moran, S., & Warmuth, M. K. (2019). Unlabeled sample compression schemes and corner peelings for ample and maximum classes. ICALP34, 1–15. . 
  • Chepoi, V., Knauer, K., & Philibert, M. (2021). Labeled sample compression schemes for complexes of oriented matroids. arXiv:2110.15168v1.  
  • Floyd, S., & Warmuth, M. K. (1995). Sample compression, learnability, and the Vapnik–Chervonenkis dimension. Machine Learning21(3), 269–304. . 
  • Friedman, N. (2004). Inferring cellular networks using probabilistic graphical models. Science303(5659), 799–805. 
  • Geiger, D., Heckerman, D., King, H. P., & Meek, C. (2001). Stratified exponential families: graphical models and model selection. The Annals of Statistics29(2), 505–529. 
  • Geiger, D., Meek, C., & Sturmfels, B. (2006). On the toric algebra of graphical models. Annals of Statistics34(3), 1463–1492. 
  • Haussler, D., Sloan, R., & Warmuth, M. K. (1994). Predicting {0,1} functions on randomly drawn points. Inf. Comput.115(2), 248–292.  
  • Helmbold, D., Sloan, R., & Warmuth, M. K. (1990). Learning nested differences of intersection-closed concept classes. Machine Learning5, 165–196. . 
  • Knauer, K., & Marc, T. (2020). On tope graphs of complexes of oriented matroids. Discrete & Computational Geometry63(2), 377–417.  
  • Kuzmin, D., & Warmuth, M. K. (2007). Unlabeled compression schemes for maximum classes. Journal of Machine Learning Research8, 2047–2081.  
  • Lauritzen, S. L. (1996). Graphical models. Oxford University Press. 
  • Li, B., & Yang, Y. (2018). Complexity of concept classes induced by discrete Markov networks and Bayesian networks. Pattern Recognition82, 31–37.
  • Littlestone, N., & Warmuth, M. K. (1986). Relating data compression and learnability [Unpublished manuscript].
  • Marc, T. (2022). Unlabeled sample compression schemes for oriented matroids. arXiv:2203.11535v2.  
  • Moran, S., & Warmuth, M. K. (2016). Labeled compression schemes for extremal classes. In ALT (pp. 34–39). Springer. 
  • Moran, S., & Yehudayoff, A. (2016). Sample compression schemes for VC classes. In ITA (pp. 1–14). IEEE.
  • Pálvölgyi, D., & Tardos, G. (2020). Unlabeled compression schemes exceeding the VC-dimension. Discrete Applied Mathematics276, 102–107.  
  • Pistone, G., Riccomagno, E., & Wynn, H. P. (2001). Algebraic statistics: Computational commutative algebra in statistics. Chapman and Hall/CRC. 
  • Rubinstein, B. I. P., & Rubinstein, J. H. (2012). A geometric approach to sample compression. Journal of Machine Learning Research13(42), 1221–1261. 
  • Settimi, R., & Smith, J. Q. (2000). Geometry, moments and conditional independence trees with hidden variables. Annals of Statistics28(4), 1179–1205.  
  • Warmuth, M. K. (2003). Compressing to VC dimension many points. In Proceedings of the 16th Annual Conference on Learning Theory (pp. 743–744). Springer.

To cite this article: Tingting Luo & Benchong Li (26 Sep 2023): Compression schemes for concept classes induced by three types of discrete undirected graphical models, Statistical Theory and Related Fields, DOI: 10.1080/24754269.2023.2260046

To link to this article: