McAnulty College and Graduate School of Liberal Arts
Donald L. Simon
Monotone DNF, PAC Learning, Parity Function, Threshold Function, Uniform Distribution
In 1984 Valiant introduced the distribution-independent model of Probably Approximately Correct (PAC) learning from random examples and brought up the problem of whether polynomial-size DNF functions are PAC learnable in polynomial time. It has been about twenty years that the DNF learning problem has been widely regarded as one of the most important ---and challenging --- open questions in Computational Learning Theory. We consider a related but simpler question: are polynomial-size monotone DNF functions PAC learnable in polynomial time if examples of the function are uniformly generated? Our research develops an algorithm that we hope to learn a monotone DNF in polynomial time by using Threshold Function Hypotheses. We tested with some interesting cases and got some impressive and encouraging results. However, further testing revealed other cases for which the algorithm appears to fail. Some ideas for addressing these problem cases will be discussed.
Bi, W. (2004). A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning (Master's thesis, Duquesne University). Retrieved from https://dsc.duq.edu/etd/312