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

Tingting Luo and Benchong Li

Statistical Theory and Related Fields, 2023, vol. 7, issue 4, 287-295

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.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24754269.2023.2260046 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tstfxx:v:7:y:2023:i:4:p:287-295

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tstf20

DOI: 10.1080/24754269.2023.2260046

Access Statistics for this article

Statistical Theory and Related Fields is currently edited by Zhao Wei

More articles in Statistical Theory and Related Fields from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().