In this paper, we study the learnability of the Boolean class of d-monotone functions \(f:\mathcal{X}\rightarrow \{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,\ldots ,g_d)\) , where F is any Boolean function \(F:\{0,1\}^d\rightarrow \{0,1\}\) and \(g_1,\ldots ,g_d:\mathcal{X}\rightarrow \{0,1\}\) are any monotone functions, is learnable in time \(\sigma (\mathcal{X})\cdot (\textrm{size}(f)/d+1)^{d}\) where \(\sigma (\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 \(\textrm{size}(f)=\textrm{size}(g_1)+\cdots +\textrm{size}(g_d)\) , where \(\textrm{size}(g_i)\) is the number of minimal elements in \(g_i^{-1}(1)\) . For the Boolean function \(f:\{0,1\}^n\rightarrow \{0,1\}\) , the class of d-monotone functions that are represented in the form \(f=F(g_1,g_2,\ldots ,g_d)\) , where F is any Boolean function and \(g_1,\ldots ,g_d\) are any monotone DNF, is learnable in time \(O(n^2)\cdot (\textrm{size}(f)/d+1)^{d}\) where \(\textrm{size}(f)=\textrm{size}(g_1)+\cdots +\textrm{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 \(\textrm{size}(g_i)\) is constant for all i and \(d=O(\log n)\) .

On Exact Learning of d-Monotone Functions

会议论文
发表日期：

2025年

查看全文

Nader H. Bshouty

摘要

In this paper, we study the learnability of the Boolean class of d-monotone functions \(f:\mathcal{X}\rightarrow \{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,\ldots ,g_d)\) , where F is any Boolean function \(F:\{0,1\}^d\rightarrow \{0,1\}\) and \(g_1,\ldots ,g_d:\mathcal{X}\rightarrow \{0,1\}\) are any monotone functions, is learnable in time \(\sigma (\mathcal{X})\cdot (\textrm{size}(f)/d+1)^{d}\) where \(\sigma (\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 \(\textrm{size}(f)=\textrm{size}(g_1)+\cdots +\textrm{size}(g_d)\) , where \(\textrm{size}(g_i)\) is the number of minimal elements in \(g_i^{-1}(1)\) . For the Boolean function \(f:\{0,1\}^n\rightarrow \{0,1\}\) , the class of d-monotone functions that are represented in the form \(f=F(g_1,g_2,\ldots ,g_d)\) , where F is any Boolean function and \(g_1,\ldots ,g_d\) are any monotone DNF, is learnable in time \(O(n^2)\cdot (\textrm{size}(f)/d+1)^{d}\) where \(\textrm{size}(f)=\textrm{size}(g_1)+\cdots +\textrm{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 \(\textrm{size}(g_i)\) is constant for all i and \(d=O(\log n)\) .