随着信息技术的发展，数据规模呈爆炸式增长，数据压缩作为高效存储和传输信息的重要手段，被广泛应用于多个领域。样本压缩是统计学习领域的一个重要研究方向。概念类的样本压缩方案分为有标签压缩和无标签压缩，压缩过程由学习算法实现，压缩能力可以保证良好的泛化性能。本文针对带标签样本压缩方案展开研究，具体工作如下：
%两种压缩方案都可以将概念类的一个样本压缩为更小的子样本。

(1) 受到最大类无标签样本压缩方案的启发，针对 Vapnik-Chervonenkis (VC) 维数为 d 的最大类，本文给出了一个递归压缩算法，并证明其压缩结果是大小不超过 d 的带标签子样本。随后将递归压缩算法与先前两种带标签压缩算法进行比较，证明三种算法在最大类的情况下输出结果一致。本文给出的递归压缩算法与先前已有的重构算法组成了最大类的一个大小为 d 的新的带标签样本压缩方案。该项工作建立了最大类的无标签样本压缩方案与有标签样本压缩方案之间的联系，这为最大类的带标签样本压缩研究提供了新的算法。

(2) 最大类的任何两个概念对于无标签样本压缩方案的表示映射满足不冲突性是保证无标签样本压缩方案存在的重要条件。一个自然的要求是：若一个概念类的带标签样本压缩方案存在，则概念类中任意两个概念对于带标签样本压缩函数满足不冲突条件。考虑两种特殊的概念类——最大类和极端类，利用最大类单包含图中任意两端点的最短路径与汉明距离之间的关系，证明了该要求对于最大类成立。进一步，考虑到最大类是一种特殊的极端类，本文将该要求推广至极端类的带标签样本压缩函数，并给出严格证明。该项工作对带标签样本压缩方案的研究提供了新的思路。

本文研究了最大类和极端类的带标签样本压缩方案。对于一般的概念类，任意两个概念是否分别存在大小为其 VC 维数的带标签子集满足不冲突条件需要进一步研究。

With the development of information technology, the scale of data is growing explosively. As an important means of efficient storage and transmission of information, data compression is widely used in many fields. Sample compression is an important research direction in the field of statistical learning. The sample compression scheme of concept class is divided into labeled compression and unlabeled compression. The compression process is realized by the learning algorithm, and the compression ability can ensure good generalization performance. This paper focuses on the labeled sample compression scheme, and the specific work is as follows
(1) Inspired by the maximum class unlabeled sample compression scheme, this paper presents a recursive compression algorithm for the maximum classes with Vapnik-Chervonenkis (VC) dimension of d, and proves that the compression result is a labeled subsample of size at most d. Then the recursive compression algorithm is compared with the previous two labeled compression algorithms, and it is proved that the output results of the three algorithms are consistent in the case of the maximum class. The recursive compression algorithm presented in this paper together with previously existing reconstruction algorithms form a new labeled sample compression scheme of size d for the maximum classes. This work establishes the relationship between the unlabeled sample compression scheme and the labeled sample compression scheme for the maximum classes, which provides a new algorithm for the research of the labeled sample compression for the maximum classes.

(2) It is an important condition to ensure the existence of the unlabeled sample compression scheme that the representation mapping of any two concepts of the maximum class satisfies the non-clashing property. A natural requirement is that if a labeled sample compression scheme exists for a concept class, then any two concepts in the concept class satisfy the non-clashing condition with respect to the labeled sample compression function. Considering two special concept classes, maximum class and extreme class, we prove that the requirement holds for maximum classes by using the relationship between the shortest path and Hamming distance of any two end points in the maximum class one inclusion graph. Furthermore, considering that the maximum class is a special extreme class, we extend the requirement to the labeled sample compression function of the extreme classes, and a strict proof is given. This work provides a new idea for the research of labeled sample compression scheme.

In this paper, the compression schemes of labeled samples for the maximum classes and the extreme classes are investigated. For general concept classes, whether there exist labeled subsets of size VC dimension of any two concepts satisfying the non-clashing condition requires further investigation.

[1] UTHAYAKUMAR J, VENGATTARAMAN T, PONNURANGAM D. A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications[J]. Journal of King Saud University - Computer and Information Sciences, 2021, 33(2): 119-140.
[2] LITTLESTONE N, WARMUTH M K. Relating data compression and learnability. Unpublished manuscript, 1986. http://www.cse.ucsc.edu/ manfred.
[3] SMITH C A. A survey of various data compression techniques[J]. International Journal of Recent Technology and Engineering, 2010, 2: 1-20.
[4] FITRIYA L A, PURBOYO T W, PRASASTI A L. A review of data compression techniques[J]. International Journal of Applied Engineering Research, 2017, 12(19): 8956-8963.
[5] CRISTIANINI N, SHAWE-TAYLOR J. An introduction to support vector machines and other kernel based learning methods[M]. Cambridge: Cambridge University Press, 2000.
[6] KETSHABETSWE K L, ZUNGERU A M, MTENGI B et al. Data compression algorithms for wireless sensor networks: a review and comparison[J]. IEEE Access, 2021, 9: 136872-136891.
[7] VIJAYVARGIYA G, SILAKARI S, PANDEY R. A survey: various techniques of image compression[J]. International Journal of Computer Science and Information Security, 2013.
[8] VENUGOPAL D, MOHAN S, SIVANANTHARAJA A. An efficient block based lossless compression of medical images[J]. Optik, 2016, 127(2): 754-758.
[9] YANG Y, AWAIS M K, ANDREW J M. A configurable realtime DWT-based neural data compression and communication VLSI system for wireless implants[J]. Journal of Neuroscience Methods, 2014, 227: 140-150.
[10] MOHRI S, ROSTAMIZADEH A, TALWALKAR A. Foundations of machine learning, Second edition[M]. Cambridge, MA: MIT Press, 2018.
[11] BLUMER A, EHRENFEUCHT A, HAUSSLER D et al. Occam's razor[J]. Information Processing Letters, 1987, 24: 377-380.
[12] VALIANT L G. A theory of the learnable[J]. Communications of the ACM, 1984, 27: 1134-1142.
[13] FLOYD S. On space-bounded learning and the vapnik-chervonenkis dimension[D]. Berkeley: University of California, 1989.
[14] VAPNIK V N, CHERVONENKIS A Y. On the uniform convergence of relative frequencies of events to their probability[J]. Theory of Probability and Its Applications, 1971, 16: 264-280.
[15] BLUMER A, EHRENFEUCHT A, HAUSSLER D et al. Learnability and the Vapnik-Chervonenkis dimension[J]. Journal of Association for Computing Machinery, 1989, 36: 929-965.
[16] BLUMER A, LITTLESTONE N. Learning faster than promised by the Vapnik-Chervonenkis dimension[J]. Discrete Applied Mathematics, 1989, 24(1): 47-53.
[17] LANGFORD J. Tutorial on practical prediction theory for classification[J]. Journal of Machine Learning Research. 2005, 6: 273-306.
[18] SHALEV-SHWARTZ S, BEN-DAVID S. Understanding machine learning: from theory to algorithms[M]. Cambridge: Cambridge University Press, 2014.
[19] CHERNIKOV A, SIMON P. Externally definable sets and dependent pairs[J]. Israel Journal of Mathematics, 2013, 194(1): 409-425.
[20] RUBINSTEIN B I P, BARTLETT P L, RUBINSTEIN J H. Shifting: One-inclusion mistake bounds and sample compression[J]. Journal of Computer and System Sciences, 2009, 75(1): 37-59.
[21] JOHNSON H R, LASKOWSKI M C. Compression schemes, stable definable families, and o-minimal structures[J]. Discrete and Computational Geometry, 2010, 43(4): 914-926.
[22] LIVNI R, SIMON P. Honest compressions and their application to compression schemes[C]. In 26th Annual Conference on Learning Theory, 2013, 30: 77-92.
[23] CUMMINGS R, LIGETT K, NISSIM K et al. Adaptive learning with robust generalization guarantees[C]. In Proceedings of the 29th Conference on Learning Theory, 2016, 772-814.
[24] FLOYD S, WARMUTH M K. Sample compression, learnability, and the Vapnik-Chervonenkis dimension[J]. Machine Learning, 1995, 21(3): 269-304.
[25] WARMUTH M K. Compressing to VC dimension many points[C]. In Proceedings of the 16th Annual Conference on Learning Theory, 2003, 743-744.
[26] FREUND Y. Boosting a weak learning algorithm by majority[J]. Information and Computation, 1995, 121(2):256-285.
[27] MORAN S, SHPILKA A, WIGDERSON A, YEHUDAYOFF A. Teaching and compressing for low VC-dimension[J]. ECCC, 2015, TR15-025.
[28] BEN-DAVID S, LITMAN A. Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes[J]. Discrete Applied Mathematics, 1998, 86: 3-25.
[29] RUBINSTEIN J H, RUBINSTEIN B I P, BARTLETT P L. Bounding embeddings of VC classes into maximum classes[J]. arXiv preprint, arXiv:1401.7388, 2014.
[30] FREUND Y, SCHAPIRE R E. Boosting: foundations and algorithms[M]. Cambridge, MA: MIT Press, 2012.
[31] MORAN S, YEHUDAYOFF A. Sample compression schemes for VC classes[J]. Journal of ACM, 2016, 63: 1-21.
[32] GARTNER B, WELZL E. Vapnik-Chervonenkis dimension and~(pseudo-) hyperplane arrangements[J]. Discrete and Computational Geometry, 1994, 12(4): 399-432.
[33] KUZMIN D, WARMUTH M K. Unlabeled compression schemes for maximum classes[J]. Journal of Machine Learning Research, 2007, 8: 2047-2081.
[34] SAMEI R, YANG B, ZILLES S. Generalizing labeled and unlabeled sample compression to Multi-label concept classes[C]. International Conference on Algorithmic Learning Theory, 2014, 8776: 275-290.
[35] PALVOLGYI D, TARDOS G. Unlabeled compression schemes exceeding the VC-dimension[J]. Discrete Applied Mathematics, 2020, 276: 102-107.
[36] RUBINSTEIN B I P, RUBINSTEIN J H. A geometric approach to sample compression[J]. Journal of Machine Learning Research, 2012, 13: 1221-1261.
[37] CHALOPIN J, CHEPOI V, MORAN S et al. Unlabeled sample compression schemes and corner peelings for ample and maximum classes[C]. In International Colloquium on Automata, Languages, and Programming, 2019, 34: 1-15.
[38] BOLLOBAS B, RADCLIFFE A J. Defect Sauer results[J]. Journal of Combinatorial Theory Series A, 1995, 72(2): 189-208.
[39] ANSTEE R P, RONYAI L, SALI A. Shattering news[J]. Graphs and Combinatoric, 2002, 18(1): 59-73.
[40] DRESS A W M. Towards a theory of holistic clustering[R]. University of Canterbury, Deptment of Mathematics and Statistics, 1997.
[41] LAWRENCE J. Lopsided sets and orthant-intersection of convex sets[J]. Pacific Journal of Mathematics, 1983, 104(1): 155-173.
[42] MORAN S. Shattering-extremal systems[J]. arXiv preprint, arXiv:1211.2980, 2012.
[43] MORAN S, WARMUTH M K. Labeled compression schemes for extremal classes[C]. International Conference on Algorithmic Learning Theory, 2016, 34-39.
[44] RUBINSTEIN J H, RUBINSTEIN B I P. Unlabelled sample compression schemes for Intersection-closed classes and Extremal classes[J]. arXiv preprint, arXiv: 2210.05455v1, 2022.
[45] HAUSSLER D, SLOAN R, WARMUTH M K. Predicting {0,1} functions on randomly drawn points[J]. Information and Computation, 1994, 115(2): 248-292.
[46] SAUER N. On the density of families of sets[J]. Journal of Combinatorial Theory, Series A, 1972, 13(1): 145-147.
[47] SHELAH S. A combinatorial problem, stability and order for models and theories in infinitary languages[J]. Pacific Journal of Mathematics, 1972, 41(1): 247-261.
[48] WELZL E. Complete range spaces. Unpublished notes, 1987.
[49] HAUSSLER D. Space efficient learning algorithms[R]. University of California Santa Cruz, Computer Research Laboratory, 1988.
[50] EDELSBRUNNER H. Algorithms in combinatorial geometry[M]. Berlin: Springer-Verlag, 1987.
[51] GRECO G. Embeddings and the trace of finite sets[J]. Information Processing Letters, 1998, 67(4): 199-203.