Free resolutions of function classes via order complexes

DOI10.1016/J.AAM.2020.102074MaRDI QIDQ2197912zbMATH OpenOpenAlexFDO

Authors Justin Chen, Christopher Eur, Greg Yang, Mengyuan Zhang

Publication date 1 September 2020

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.02159

Möbius function order complexes Stanley-Reisner ideal suboplexes VC dimension

Combinatorics of partially ordered sets (06A07) Syzygies, resolutions, complexes and commutative rings (13D02) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Computational learning theory (68Q32)

Abstract: Function classes are collections of Boolean functions on a finite set, which are fundamental objects of study in theoretical computer science. We study algebraic properties of ideals associated to function classes previously defined by the third author. We consider the broad family of intersection-closed function classes, and describe cellular free resolutions of their ideals by order complexes of the associated posets. For function classes arising from matroids, polyhedral cell complexes, and more generally interval Cohen-Macaulay posets, we show that the multigraded Betti numbers are pure, and are given combinatorially by the M"obius functions. We then apply our methods to derive bounds on the VC dimension of some important families of function classes in learning theory.

Review text

Suppose that \(C\) is a collection of Boolean functions on \([n]=\{0,\ldots, n-1\}\) and \(U \subseteq [n]\). It is said that \(U\) is shattered by \(C\), if every possible Boolean function on \(U\) is a restriction of a function in \(C\). In learning theory the VC dimension of \(C\) is defined as \(\dim_{VC} C=\max\{|U|\big| U \text{ is shattered by }C\}\). This quantity tries to measure how much data is required to learn an unknown function, given that the function is in \(C\). Now consider the simplicial complex \(\diamond_C\) on the vertex set \([n]\times [2]\), whose facets are \(\{(i,f(i))|i\in [n]\}\) for all \(f\in C\). This is called the suboplex associated to \(C\). The Stanley-Reisner ideal of \(\diamond_C\) is called the suboplex ideal of \(C\) and is denoted by \(I_C\) and its Alexander dual is denoted by \(I^*_C\). The homological dimension of \(C\) is defined as the projective dimension of \(I^*_C\) and is denoted by \(\dim_h(C)\). In the paper [``A homological theory of functions, Preprint, \url{arXiv:1701.02302}], \textit{G. Yang} showed that \(\dim_{VC}(C)\leq \dim_h(C)\). Now in the current paper, the authors present a free resolution for \(I^*_C\) when \(C\) is ``intersection-closed, and use this to derive upper bounds on the VC dimension of some families of function classes. More concretely, the authors first note that under the correspondence \(f \leftrightarrow f^{-1}(1)\), the function class \(C\) corresponds to a poset of subsets of \([n]\). For a poset \(P\), the corresponding function class is denoted by \(C(P)\). They call a poset \(P\) intersection-closed, when from \(A,B\in P\) it follows that \(A\cap B\in P\). When \(P\) is intersection-closed, they construct a cellular free resolution of \(I^*_{C(P)}\) on the order complex of \(P\) and show that \(\dim_h C(P)\leq \mathrm{rank}(P)\), where \(\mathrm{rank}(P)\) denotes the length of a longest chain in \(P\). Then they consider interval Cohen-Macaulay posets, that is, posets \(P\) with the property that for every open interval \(I\) of \(P\), the order complex of \(I\) is Cohen-Macaulay. The authors present a formula for the Betti numbers of \(I^*_{C(P)}\), in terms of the Möbius function on \(P\), when \(P\) is intersection-closed and interval Cohen-Macaulay. They show that lattices of flats of matroids and face posets of polyhedral cell complexes have these two properties and use this to find the VC dimension of the former ones and give bounds on the VC dimension of the latter ones. Finally, they utilize these results to find the VC dimension or give bounds on the VC dimension of some families of function classes which are important in learning theory.

Recommendations

Cites work

Cited in

(1)

A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma

Describes a project that uses

Uses Software

Macaulay2

This page was built for publication: Free resolutions of function classes via order complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197912)