提出可高效学习的d-单调布尔函数类,适用于多种实际场景。
On Exact Learning of $d$-Monotone Functions
- 通过单调函数组合构建d-单调函数,利用查询学习框架实现精确学习。
- 在d为常数时,学习时间复杂度为多项式,对n维布尔函数同样有效。
- 适合研究形式化学习、布尔函数结构分析的学者参考。
本文研究从成员查询和等价查询中精确学习布尔函数类d-单调函数的可能性,其中({\cal X},\le)为有限格。证明了形如f=F(g_1,…,g_d)的d-单调函数类是可学习的,其中F为任意布尔函数,g_i为任意单调函数,学习时间复杂度为σ({\cal X})·(size(f)/d+1)^d,σ({\cal X})为格中从最大元到最小元链上最多前驱之和,size(f)为各g_i的最小1值元素数之和。对于{0,1}^n上的布尔函数,若各g_i为单调DNF,则学习时间复杂度为O(n^2)·(size(f)/d+1)^d。当d为常数时,该类可在多项式时间内学习;当所有size(g_i)有界且d=O(log n)时亦然。
原文摘要 · Abstract (English)
In this paper, we study the learnability of the Boolean class of $d$-monotone functions $f:{\cal X}\to\{0,1\}$ from membership and equivalence queries, where $({\cal 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\to\{0,1\}$ and $g_1,\ldots,g_d:{\cal X}\to \{0,1\}$ are any monotone functions, is learnable in time $σ({\cal X})\cdot (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(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,\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 (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)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。