A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning

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.

Name thesis:degree_name

MS

Level thesis:degree_level

Immediate Access

Discipline thesis:degree_discipline

Computational Mathematics

Year dc:date.available

2004

Author dc:creator

• Bi, Wenzhu

Contributors dc:contributor

• Jeffrey Jackson
• Donald L. Simon
• Frank D'Amico

• Monotone DNF
• PAC Learning
• Parity Function
• Threshold Function
• Uniform Distribution

Language dc:language

English

Repository record dc:identifier

https://dsc.duq.edu/etd/312

OAI identifier oai:identifier

oai:dsc.duq.edu:etd-1325