{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23171"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23171","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Topics in computational learning theory and graph algorithms","abstract":"\"The distribution-independent model of concept learning from examples (\"\"PAC-learning\"\") due to Valiant is investigated. It has previously been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class. (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) It is shown here that for any class satisfying the property of closure under exception lists, the PAC-learnability of the class implies the existence of an Occam algorithm for the class. Thus the existence of randomized Occam algorithms exactly characterizes PAC-learnability for all concept classes with this property. This reveals a close relationship between PAC-learning and information compression for a wide range of interesting classes.\"","abstract_html":""The distribution-independent model of concept learning from examples (""PAC-learning"") due to Valiant is investigated. It has previously been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class. (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) It is shown here that for any class satisfying the property of closure under exception lists, the PAC-learnability of the class implies the existence of an Occam algorithm for the class. Thus the existence of randomized Occam algorithms exactly characterizes PAC-learnability for all concept classes with this property. This reveals a close relationship between PAC-learning and information compression for a wide range of interesting classes."","abstract_has_math":false,"creators":["Board, Raymond Acton"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Pitt, Leonard"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:04:41Z","date_published":"2011-05-07T14:04:41Z","updated_at":"2026-07-22T22:25:21Z","subjects":["Mathematics","Computer Science"],"languages":["eng"],"rights":["Copyright 1990 Board, Raymond Acton"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114177","(UMI)AAI9114177"],"render_values":[{"text":"AAI9114177","href":null,"code":true},{"text":"(UMI)AAI9114177","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23171","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Pitt, Leonard"]},{"key":"dc:creator","label":"Author","values":["Board, Raymond Acton"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:04:41Z","10000-01-01","1990"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1990 Board, Raymond Acton"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114177","(UMI)AAI9114177","http://hdl.handle.net/2142/23171"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"The distribution-independent model of concept learning from examples (\"\"PAC-learning\"\") due to Valiant is investigated. It has previously been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class. (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) It is shown here that for any class satisfying the property of closure under exception lists, the PAC-learnability of the class implies the existence of an Occam algorithm for the class. Thus the existence of randomized Occam algorithms exactly characterizes PAC-learnability for all concept classes with this property. This reveals a close relationship between PAC-learning and information compression for a wide range of interesting classes.\"","The PAC-learning model is then extended to that of semi-supervised learning (ss-learning), in which a collection of disjoint concepts is to be simultaneously learned with only partial information concerning concept membership available to the learning algorithm. It is shown that many PAC-learnable concept classes are also ss-learnable. Several sets of sufficient conditions for a class to be ss-learnable are given. A prediction-based definition of learning multiple concept classes has been given and shown to be equivalent to ss-learning.","The predictive ability of automata less powerful than Turing machines is investigated. Models for prediction by deterministic finite state machines, 1-counter machines, and deterministic pushdown automata are defined, and the classes of languages that can be predicted by these types of automata are precisely characterized. In addition, upper bounds are given for the size of classes that can be predicted by such automata.","Two new online protocols for graph algorithms are defined. Bounds on the performance of online algorithms for the graph bandwidth, vertex cover, independent set, and dominating set problems are demonstrated. Various results are proved for algorithms operating according to a standard online protocol as well as the two new protocols.","Made available in DSpace on 2011-05-07T14:04:41Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114177.pdf: 6524201 bytes, checksum: 75041016a17f27d5eb472ec134b9d446 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:02:40Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:49-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Topics in computational learning theory and graph algorithms"]}]}],"canonical_facts":{"dc:contributor":["Pitt, Leonard"],"dc:creator":["Board, Raymond Acton"],"dc:date":["2011-05-07T14:04:41Z","10000-01-01","1990"],"dc:description":["\"The distribution-independent model of concept learning from examples (\"\"PAC-learning\"\") due to Valiant is investigated. It has previously been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class. (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) It is shown here that for any class satisfying the property of closure under exception lists, the PAC-learnability of the class implies the existence of an Occam algorithm for the class. Thus the existence of randomized Occam algorithms exactly characterizes PAC-learnability for all concept classes with this property. This reveals a close relationship between PAC-learning and information compression for a wide range of interesting classes.\"","The PAC-learning model is then extended to that of semi-supervised learning (ss-learning), in which a collection of disjoint concepts is to be simultaneously learned with only partial information concerning concept membership available to the learning algorithm. It is shown that many PAC-learnable concept classes are also ss-learnable. Several sets of sufficient conditions for a class to be ss-learnable are given. A prediction-based definition of learning multiple concept classes has been given and shown to be equivalent to ss-learning.","The predictive ability of automata less powerful than Turing machines is investigated. Models for prediction by deterministic finite state machines, 1-counter machines, and deterministic pushdown automata are defined, and the classes of languages that can be predicted by these types of automata are precisely characterized. In addition, upper bounds are given for the size of classes that can be predicted by such automata.","Two new online protocols for graph algorithms are defined. Bounds on the performance of online algorithms for the graph bandwidth, vertex cover, independent set, and dominating set problems are demonstrated. Various results are proved for algorithms operating according to a standard online protocol as well as the two new protocols.","Made available in DSpace on 2011-05-07T14:04:41Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114177.pdf: 6524201 bytes, checksum: 75041016a17f27d5eb472ec134b9d446 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:02:40Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:49-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9114177","(UMI)AAI9114177","http://hdl.handle.net/2142/23171"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Board, Raymond Acton"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Topics in computational learning theory and graph algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:21Z"}