Sample compression schemes were first proposed by Littlestone and Warmuth in 1986.Undi-rected graphical model is a powerful tool for classification in statistical learning.In this paper,we consider labelled compressio...Sample compression schemes were first proposed by Littlestone and Warmuth in 1986.Undi-rected 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.展开更多
基金This work was supported byNationalNatural Science Foundation of China(Research Plan in Shaanxi Province[GrantNumber 12171382])the Natural Science Basic Research Plan in Shaanxi Province[Grant Number 2020JM-188]the Fundamental Research Funds for the Central Universities[Grant Number QTZX23002].
文摘Sample compression schemes were first proposed by Littlestone and Warmuth in 1986.Undi-rected 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.
