On Exact Learning of $d$-Monotone Functions

Abstract

In this paper, we study the learnability of the Boolean class of $d$-monotone functions $f:\mathcal{X}\to \{0,1\}$ from membership and equivalence queries, where $(\mathcal{X},\le )$ is a finite lattice. We show that the class of $d$-monotone functions that are represented in the form $f=F(g_1,g_2,\dots ,g_d)$, where $F$ is any Boolean function $F:\{0,1{\}}^d\to \{0,1\}$ and $g_1,\dots ,g_d:\mathcal{X}\to \{0,1\}$ are any monotone functions, is learnable in time $\ddot{I}ƒ(\mathcal{X})\cdot (size(f)/d+1{)}^d$ where $\ddot{I}ƒ(\mathcal{X})$ is the maximum sum of the number of immediate predecessors in a chain from the largest element to the smallest element in the lattice $\mathcal{X}$ and $size(f)=size(g_1)+\cdots +size(g_d)$, where $size(g_i)$ is the number of minimal elements in $g_i^{-1}(1)$. For the Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, the class of $d$-monotone functions that are represented in the form $f=F(g_1,g_2,\dots ,g_d)$, where $F$ is any Boolean function and $g_1,\dots ,g_d$ are any monotone DNF, is learnable in time $O(n^2)\cdot (size(f)/d+1{)}^d$ where $size(f)=size(g_1)+\cdots +size(g_d)$. In particular, this class is learnable in polynomial time when $d$ is constant. Additionally, this class is learnable in polynomial time when $size(g_i)$ is constant for all $i$ and $d=O(\log n)$.