Home Course Descriptions Scholarship & Service
Mission Schedule of Classes

Careers

Programs Seminar Announcements Financial Assistance
Faculty & Staff 4/1 Program Apply
Department News Positions

Department of Mathematics and Computer Science Seminars

Upcoming Seminars
Department of Mathematics & Computer Science

Title: "Algorithm for Learning From a Random Walk Oracle"
Speaker: Xiaolin Yang
Date: Thursday, July 23
Time: 2:00 pm - 3:00 pm
Place: 351 College Hall

Abstract: Learning Disjunctive Normal Form (DNF) and Threshold of Parity (TOP) 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. The best results to date have been obtained in an active learning model based on membership oracle queries, where algorithms exist that nearly exponentially outperform the best current TOP algorithms for the passive learning model based on uniform random instances provided by an example oracle. 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 topic which is closely related to certain learning algorithms, specifically, 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.

   
Mission and Identity | Undergraduate Programs | Graduate Programs | Contact DU | Copyright 2005 Contact Duquesne Graduate Programs Undergraduate Programs Mission and Identity
 
 
Undergraduate College
Graduate School
Programs
Liberal Arts Home
Human Resources DU Daily & Events Athletics Newsroom Contact Duquesne Graduate Programs Undergraduate Programs Mission and Identity