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

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.

• Publication year

  2023

• Venue

  Statistical Theory and Related Fields

• Publication date

  2023-09-26

• Fields of study

  Not labeled

• Identifiers
  DOI 10.1080/24754269.2023.2260046
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Unlabeled sample compression schemes for oriented matroids

  2022cited by this paper
• Labeled sample compression schemes for complexes of oriented matroids

  2021cited by this paper
• Graphical Models

  2020cited by this paper
• Unlabeled Compression Schemes Exceeding the VC-dimension

  2018cited by this paper
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes

  2018cited by this paper
• Complexity of concept classes induced by discrete Markov networks and Bayesian networks

  2018influential reference
• On Tope Graphs of Complexes of Oriented Matroids

  2017influential reference
• Labeled Compression Schemes for Extremal Classes

  2015cited by this paper
• Sample compression schemes for VC classes

  2015cited by this paper
• A Geometric Approach to Sample Compression

  2009cited by this paper
• Unlabeled Compression Schemes for Maximum Classes,

  2007cited by this paper
• On the toric algebra of graphical models

  2006cited by this paper
• Inferring Cellular Networks Using Probabilistic Graphical Models

  2004cited by this paper
• Compressing to VC Dimension Many Points

  2003cited by this paper
• Shattering News

  2002cited by this paper
• Stratified exponential families: Graphical models and model selection

  2001cited by this paper
• Geometry, moments and conditional independence trees with hidden variables

  2000cited by this paper
• Combinatorial Variability of Vapnik-chervonenkis Classes with Applications to Sample Compression Schemes

  1998cited by this paper
• Sample compression, learnability, and the Vapnik-Chervonenkis dimension

  1995influential reference
• Defect Sauer Results

  1995cited by this paper
• Learning Nested Differences of Intersection-Closed Concept Classes

  1989cited by this paper
• Learnability and the Vapnik-Chervonenkis dimension

  1989cited by this paper
• Predicting (0, 1)-functions on randomly drawn points

  1988cited by this paper
• Occam's Razor

  1987cited by this paper

• No citing papers are available for this paper.