On Exact Learning of d-Monotone Functions

In this paper, we study the learnability of the Boolean class of d-monotone functions f:cal X→0,1 from membership and equivalence queries, where (cal X,≤) is a finite lattice. We show that the class of d-monotone functions that are represented in the form f=F(g1,g2,ldots,gd), where F is any Boolean function F:0,1d→0,1 and g1,ldots,gd:cal X→ 0,1 are any monotone functions, is learnable in time σ(cal X)· (size(f)/d+1)d where σ(cal 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 cal X and size(f)=size(g1)+cdots+size(gd), where size(gi) is the number of minimal elements in gi-1(1). For the Boolean function f:0,1n→0,1, the class of d-monotone functions that are represented in the form f=F(g1,g2,ldots,gd), where F is any Boolean function and g1,ldots,gd are any monotone DNF, is learnable in time O(n2)· (size(f)/d+1)d where size(f)=size(g1)+cdots+size(gd). In particular, this class is learnable in polynomial time when d is constant. Additionally, this class is learnable in polynomial time when size(gi) is constant for all i and d=O(log n).