Learning Algorithms from Natural Proofs
Learning Algorithms from Natural Proofs
复制标题
从自然证明中学习算法
DOI：
10.4230/lipics.ccc.2016.10
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Kolokolova
中科院分区：
文献类型：
--
作者：
M. Carmosino;R. Impagliazzo;Valentine Kabanets;A. Kolokolova
基于Hastad(1986)的电路下界，Linial，Mansour和Nisan(1993)给出了均匀分布的PAC模型中AC0(具有与、或和非门的恒定深度电路)的准多时间学习算法。对于AC0[p]类电路(质数p的恒定深度门、带AND门、OR门、NOT门和MODp门)来说，(任何种类的)学习算法都是一个悬而未决的问题。我们的主要结果是在具有成员查询的均匀分布上的PAC模型中AC0[p]的一个准多时间学习算法。这个算法是我们展示的自然证明(在Razborov和Rudich(1997)的意义上)和学习算法之间的一般联系的应用。我们认为，对于任何(足够强大的)电路类，对电路下界的自然证明会产生同一电路类的学习算法。由于Razborov(1987)和Smolensky(1987)关于AC0[p]的下界是自然的，我们得到了关于AC0[p]的学习算法。
Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (1993) gave a quasipolytime learning algorithm for AC0 (constant-depth circuits with AND, OR, and NOT gates), in the PAC model over the uniform distribution. It was an open question to get a learning algorithm (of any kind) for the class of AC0[p] circuits (constant-depth, with AND, OR, NOT, and MODp gates for a prime p). Our main result is a quasipolytime learning algorithm for AC0[p] in the PAC model over the uniform distribution with membership queries. This algorithm is an application of a general connection we show to hold between natural proofs (in the sense of Razborov and Rudich (1997)) and learning algorithms. We argue that a natural proof of a circuit lower bound against any (sufficiently powerful) circuit class yields a learning algorithm for the same circuit class. As the lower bounds against AC0[p] by Razborov (1987) and Smolensky (1987) are natural, we obtain our learning algorithm for AC0[p].