{"id":{"repo_id":"duquesne","oai_identifier":"oai:dsc.duq.edu:etd-2586"},"canonical_url":"https://search.ndltd.org/etd/duquesne/oai:dsc.duq.edu:etd-2586","repository":{"repo_id":"duquesne","name":"Duquesne","base_url":"https://dsc.duq.edu/do/oai/"},"display":{"title":"Algorithm for Learning from a Random Walk Oracle","abstract":"Learning Disjunctive Normal Form and Threshold of Parity functions are well-studied problems in computational learning theory. Under different learning models we can achieve different time complexities with respect to the size of the input. In this thesis, I consider using an oracle whose power lies in between membership and example oracles, the random walk oracle. I first study a heuristic algorithm for estimating the sum of squares of Fourier coefficients. Then I propose a new algorithm for learning under a random walk oracle and compare the performance of this algorithm with an algorithm previously proposed by Jackson and Wimmer. The performance of these two algorithms is evaluated empirically based on experiments on linear threshold functions, a special case of TOP. Finally, I prove a theorem showing how to efficiently generate a richer subclass of TOP functions from linear threshold functions, which could allow for broader testing of these algorithms.","abstract_html":"Learning Disjunctive Normal Form and Threshold of Parity functions are well-studied problems in computational learning theory. Under different learning models we can achieve different time complexities with respect to the size of the input. In this thesis, I consider using an oracle whose power lies in between membership and example oracles, the random walk oracle. I first study a heuristic algorithm for estimating the sum of squares of Fourier coefficients. Then I propose a new algorithm for learning under a random walk oracle and compare the performance of this algorithm with an algorithm previously proposed by Jackson and Wimmer. The performance of these two algorithms is evaluated empirically based on experiments on linear threshold functions, a special case of TOP. Finally, I prove a theorem showing how to efficiently generate a richer subclass of TOP functions from linear threshold functions, which could allow for broader testing of these algorithms.","abstract_has_math":false,"creators":["Yang, Xiaolin"],"institution":null,"degree_name":"MS","degree_level":"Campus Only","degree_discipline":"Computational Mathematics","degree_department":null,"school":null,"contributors":["Jeffrey C. Jackson","Donald L. Simon"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:51:57Z","subjects":["Computational Learning","Fourier Analysis","Random Walk Oracle"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://dsc.duq.edu/etd/1569","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://dsc.duq.edu/etd/1569","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://dsc.duq.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adsc.duq.edu%3Aetd-2586","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jeffrey C. Jackson","Donald L. Simon"]},{"key":"dc:creator","label":"Author","values":["Yang, Xiaolin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2023-01-05T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2009-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computational Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Campus Only"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Learning","Fourier Analysis","Random Walk Oracle"]}]},{"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/1569"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Learning Disjunctive Normal Form and Threshold of Parity functions are well-studied problems in computational learning theory. Under different learning models we can achieve different time complexities with respect to the size of the input. In this thesis, I consider using an oracle whose power lies in between membership and example oracles, the random walk oracle. I first study a heuristic algorithm for estimating the sum of squares of Fourier coefficients. Then I propose a new algorithm for learning under a random walk oracle and compare the performance of this algorithm with an algorithm previously proposed by Jackson and Wimmer. The performance of these two algorithms is evaluated empirically based on experiments on linear threshold functions, a special case of TOP. Finally, I prove a theorem showing how to efficiently generate a richer subclass of TOP functions from linear threshold functions, which could allow for broader testing of these algorithms."]},{"key":"dc:title","label":"Title","values":["Algorithm for Learning from a Random Walk Oracle"]}]}],"canonical_facts":{"dc:contributor":["Jeffrey C. Jackson","Donald L. Simon"],"dc:creator":["Yang, Xiaolin"],"dc:date.available":["2023-01-05T08:00:00Z"],"dc:date.created":["2009-01-01T08:00:00Z"],"dc:description.abstract":["Learning Disjunctive Normal Form and Threshold of Parity functions are well-studied problems in computational learning theory. Under different learning models we can achieve different time complexities with respect to the size of the input. In this thesis, I consider using an oracle whose power lies in between membership and example oracles, the random walk oracle. I first study a heuristic algorithm for estimating the sum of squares of Fourier coefficients. Then I propose a new algorithm for learning under a random walk oracle and compare the performance of this algorithm with an algorithm previously proposed by Jackson and Wimmer. The performance of these two algorithms is evaluated empirically based on experiments on linear threshold functions, a special case of TOP. Finally, I prove a theorem showing how to efficiently generate a richer subclass of TOP functions from linear threshold functions, which could allow for broader testing of these algorithms."],"dc:identifier":["https://dsc.duq.edu/etd/1569"],"dc:language":["English"],"dc:subject":["Computational Learning","Fourier Analysis","Random Walk Oracle"],"dc:title":["Algorithm for Learning from a Random Walk Oracle"],"thesis:degree_discipline":["Computational Mathematics"],"thesis:degree_level":["Campus Only"],"thesis:degree_name":["MS"]},"updated_at":"2026-11-19T07:51:57Z"}