{"id":{"repo_id":"duquesne","oai_identifier":"oai:dsc.duq.edu:etd-1325"},"canonical_url":"https://search.dev.ndltd.org/etd/duquesne/oai:dsc.duq.edu:etd-1325","repository":{"repo_id":"duquesne","name":"Duquesne","base_url":"https://dsc.duq.edu/do/oai/"},"display":{"title":"A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Bi, Wenzhu"],"institution":null,"degree_name":"MS","degree_level":"Immediate Access","degree_discipline":"Computational Mathematics","degree_department":null,"school":null,"contributors":["Jeffrey Jackson","Donald L. Simon","Frank D'Amico"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004-01-01T08:00:00Z","date_published":"2004-01-01T08:00:00Z","updated_at":"2026-07-24T02:09:20Z","subjects":["Monotone DNF","PAC Learning","Parity Function","Threshold Function","Uniform Distribution"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dsc.duq.edu/etd/312","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jeffrey Jackson","Donald L. Simon","Frank D'Amico"]},{"key":"dc:creator","label":"Author","values":["Bi, Wenzhu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2018-08-03T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computational Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Immediate Access"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Monotone DNF","PAC Learning","Parity Function","Threshold Function","Uniform Distribution"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dsc.duq.edu/etd/312"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning"]}]}],"canonical_facts":{"dc:contributor":["Jeffrey Jackson","Donald L. Simon","Frank D'Amico"],"dc:creator":["Bi, Wenzhu"],"dc:date.available":["2018-08-03T07:00:00Z"],"dc:description.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."],"dc:identifier":["https://dsc.duq.edu/etd/312"],"dc:language":["English"],"dc:subject":["Monotone DNF","PAC Learning","Parity Function","Threshold Function","Uniform Distribution"],"dc:title":["A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning"],"thesis:degree_discipline":["Computational Mathematics"],"thesis:degree_level":["Immediate Access"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T02:09:20Z"}