报告题目：Compression schemes for concept classes induced by three types of discrete undirected graphical models

报告人： 李本崇（西安电子科技大学数学与统计学院，副教授）

报告时间：2022年11月18日星期五 13:30-15:00

报告地点：腾讯会议ID：133-974-062

校内联系人：李天然

报告摘要：样本压缩方案由Littlestone和Warmuth于1986年首次提出，适当的压缩可以保证良好的泛化性能。无方向图形模型是机器学习中分类的有力工具，本文中我们考虑由离散无向图形模型诱导的概念类的标记压缩方案。对于没有边的两个顶点的无向图X1∈{0,1},X1∈{0,1}，X2∈{0,1,...k2－1}，(K2 ∈N,K2≥2), 我们建立了一个大小为K2+1的标记压缩方案。此外，我们还为与具有X1 ,X2, X3三个顶点和两条边的无向图相关的类构造了一个尺寸为VC维的标记压缩格式，其中X1∈{0,1}，Xi∈{0,1,...ki－1}(Ki ∈N,Ki≥2)，i=2,3.因此，对于其基础图具有两个团K1={X1 ,X2,..., Xn1}，K2={X1 ,X2,..., Xn}，且X1∈{0,1} ,存在对应概念类的大小为VC维的标记压缩方案。由一般离散无向图形模型诱导的概念类是否具有大小为VC维的样本压缩方案是一个悬而未决的问题。