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

Abstract

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.

Keywords:

• Discrete undirected graphical models
• concept classes
• VC dimension
• sample compression schemes

Acknowledgments

We would like to thank the Editor, Managing Editor, the Associate Editor and the reviewer for constructive comments and helpful suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by National Natural Science Foundation of China (Research Plan in Shaanxi Province [Grant Number 12171382]), the Natural Science Basic Research Plan in Shaanxi Province [Grant Number 2020JM-188], and the Fundamental Research Funds for the Central Universities [Grant Number QTZX23002].