Wenzhu Bi

Defense Date

7-28-2004

Graduation Date

Summer 2004

Availability

Immediate Access

Submission Type

thesis

Degree Name

MS

Department

Computational Mathematics

School

McAnulty College and Graduate School of Liberal Arts

Committee Chair

Jeffrey Jackson

Committee Member

Donald L. Simon

Committee Member

Frank D'Amico

Keywords

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

Abstract

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.

Format

PDF

Language

English

Download

Share

COinS