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

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.
   Web of Science ®Google Scholar
• 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 .
   Web of Science ®Google Scholar
• 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 .
   Web of Science ®Google Scholar
• 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 .
   Web of Science ®Google Scholar
• 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.
   Web of Science ®Google Scholar
• 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 .
   Google Scholar
• Chepoi, V., Knauer, K., & Philibert, M. (2021). Labeled sample compression schemes for complexes of oriented matroids. arXiv:2110.15168v1.
   Google Scholar
• 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 .
   Web of Science ®Google Scholar
• Friedman, N. (2004). Inferring cellular networks using probabilistic graphical models. Science, 303(5659), 799–805. https://doi.org/10.1126/science.1094068.
   PubMed Web of Science ®Google Scholar
• 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.
   Web of Science ®Google Scholar
• 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.
   Web of Science ®Google Scholar
• 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.
   Web of Science ®Google Scholar
• 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 .
   Web of Science ®Google Scholar
• 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.
   Web of Science ®Google Scholar
• 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.
   Web of Science ®Google Scholar
• Lauritzen, S. L. (1996). Graphical models. Oxford University Press.
   Google Scholar
• 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.
   Web of Science ®Google Scholar
• Littlestone, N., & Warmuth, M. K. (1986). Relating data compression and learnability [Unpublished manuscript]. http://www.cse.ucsc.edu/manfred.
   Google Scholar
• Marc, T. (2022). Unlabeled sample compression schemes for oriented matroids. arXiv:2203.11535v2.
   Google Scholar
• 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
   Google Scholar
• 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
   Google Scholar
• 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.
   Web of Science ®Google Scholar
• Pistone, G., Riccomagno, E., & Wynn, H. P. (2001). Algebraic statistics: Computational commutative algebra in statistics. Chapman and Hall/CRC.
   Google Scholar
• Rubinstein, B. I. P., & Rubinstein, J. H. (2012). A geometric approach to sample compression. Journal of Machine Learning Research, 13(42), 1221–1261.
   Google Scholar
• 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.
   Web of Science ®Google Scholar
• 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
   Google Scholar