标题： 通过局部混合随机游走的DNF学习 显示英文标题

标题： DNF Learning via Locally Mixing Random Walks

摘要： 我们在使用隶属查询的 PAC 学习框架下关于学习 DNF 公式给出了两个结果，这个框架非常具有挑战性，因为在其中学习算法必须对于任意未知的分布都成功，该分布作用于 $\{0,1\}^n$ 上。 (1) 我们首先给出一个关于学习未知 DNF 公式的单个项的准多项式时间“清单解码”算法。 更精确地说，对于任何目标 $s$-项 DNF 公式 $f = T_1 \vee \cdots \vee T_s$ 在 $\{0,1\}^n$上，以及任何未知分布 $D$ 在 $\{0,1\}^n$上，我们的算法使用成员查询和来自 $D$的随机样本，在 $\textsf{quasipoly}(n,s)$时间内运行，并输出候选术语列表 $L$，使得以高概率某些术语 $T_i$ 属于 $f$ 包含在 $L$中。 (2) 随后，我们利用结果 (1) 给出了一个$\textsf{quasipoly}(n,s)$时间算法，在带有成员查询的分布无关 PAC 学习模型中，用于学习大小为$s$的 DNF 类，其中所有项具有相同的大小。 我们的算法使用 DNF 假设进行学习。 用于建立结果 (1) 的关键工具是对“局部混合随机游走”的新结果，粗略地说，它表明在一个由少数扩展图覆盖的图上的随机游走有非可忽略的概率在这些扩展图的子集上快速混合。 显示英文摘要

摘要： We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an arbitrary and unknown distribution over $\{0,1\}^n$. (1) We first give a quasi-polynomial time "list-decoding" algorithm for learning a single term of an unknown DNF formula. More precisely, for any target $s$-term DNF formula $f = T_1 \vee \cdots \vee T_s$ over $\{0,1\}^n$ and any unknown distribution $D$ over $\{0,1\}^n$, our algorithm, which uses membership queries and random examples from $D$, runs in $\textsf{quasipoly}(n,s)$ time and outputs a list $L$ of candidate terms such that with high probability some term $T_i$ of $f$ belongs to $L$. (2) We then use result (1) to give a $\textsf{quasipoly}(n,s)$-time algorithm, in the distribution-free PAC learning model with membership queries, for learning the class of size-$s$ DNFs in which all terms have the same size. Our algorithm learns using a DNF hypothesis. The key tool used to establish result (1) is a new result on "locally mixing random walks," which, roughly speaking, shows that a random walk on a graph that is covered by a small number of expanders has a non-negligible probability of mixing quickly in a subset of these expanders.