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.

References

• Anstee, R. P., Rányai, L., & Sali, A. (2002). Shattering news. Graphs and Combinatorics, 18(1), 59–73. https://doi.org/10.1007/s003730200003. 
• Ben-David, S., & Litman, A. (1998). Combinatorial variability of Vapnik–Chervonenkis classes with applications to sample compression schemes. Discrete Applied Mathematics, 86(1), 3–25. https://doi.org/10.1016/S0166-218X(98)00000-6 . 
• Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987). Occam's razor. Information Processing Letters, 24(6), 377–380. https://doi.org/10.1016/0020-0190(87)90114-1 .  
• Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM, 36(4), 929–965. https://doi.org/10.1145/76359.76371 . 
• Bollobás, B., & A. J. Radcliffe (1995). Defect sauer results. Journal of Combinatorial Theory, Series A, 72(2), 189–208. https://doi.org/10.1016/0097-3165(95)90060-8. 
• Chalopin, J., Chepoi, V., Moran, S., & Warmuth, M. K. (2019). Unlabeled sample compression schemes and corner peelings for ample and maximum classes. ICALP, 34, 1–15. https://doi.org/10.4230/LIPIcs.ICALP.2019.34 . 
• 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 Learning, 21(3), 269–304. https://doi.org/10.1023/A:1022660318680 . 
• Friedman, N. (2004). Inferring cellular networks using probabilistic graphical models. Science, 303(5659), 799–805. https://doi.org/10.1126/science.1094068. 
• Geiger, D., Heckerman, D., King, H. P., & Meek, C. (2001). Stratified exponential families: graphical models and model selection. The Annals of Statistics, 29(2), 505–529. https://doi.org/10.1214/aos/1009210550. 
• Geiger, D., Meek, C., & Sturmfels, B. (2006). On the toric algebra of graphical models. Annals of Statistics, 34(3), 1463–1492. https://doi.org/10.1214/009053606000000263. 
• Haussler, D., Sloan, R., & Warmuth, M. K. (1994). Predicting {0,1} functions on randomly drawn points. Inf. Comput., 115(2), 248–292. https://doi.org/10.1006/inco.1994.1097.  
• Helmbold, D., Sloan, R., & Warmuth, M. K. (1990). Learning nested differences of intersection-closed concept classes. Machine Learning, 5, 165–196. https://doi.org/10.1023/A:1022696716689 . 
• Knauer, K., & Marc, T. (2020). On tope graphs of complexes of oriented matroids. Discrete & Computational Geometry, 63(2), 377–417. https://doi.org/10.1007/s00454-019-00111-z.  
• Kuzmin, D., & Warmuth, M. K. (2007). Unlabeled compression schemes for maximum classes. Journal of Machine Learning Research, 8, 2047–2081. https://doi.org/10.1007/11503415_40.  
• 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 Recognition, 82, 31–37. https://doi.org/10.1016/j.patcog.2018.04.026.
• Littlestone, N., & Warmuth, M. K. (1986). Relating data compression and learnability [Unpublished manuscript]. http://www.cse.ucsc.edu/manfred. 
• 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. https://doi.org/10.1007/978-3-319-46379-7_3 
• Moran, S., & Yehudayoff, A. (2016). Sample compression schemes for VC classes. In ITA (pp. 1–14). IEEE. https://doi.org/10.1109/ITA.2016.7888187
• Pálvölgyi, D., & Tardos, G. (2020). Unlabeled compression schemes exceeding the VC-dimension. Discrete Applied Mathematics, 276, 102–107. https://doi.org/10.1016/j.dam.2019.09.022.  
• 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 Research, 13(42), 1221–1261. 
• Settimi, R., & Smith, J. Q. (2000). Geometry, moments and conditional independence trees with hidden variables. Annals of Statistics, 28(4), 1179–1205. https://doi.org/10.1214/aos/1015956712.  
• Warmuth, M. K. (2003). Compressing to VC dimension many points. In Proceedings of the 16th Annual Conference on Learning Theory (pp. 743–744). Springer. https://doi.org/10.1007/978-3-540-45167-9_60

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: https://doi.org/10.1080/24754269.2023.2260046