Testing and learning Boolean functions

Given a function f on n inputs, we consider the problem of testing whether f belongs to a concept class C, or is far from every member of C. An algorithm that achieves this goal for a particular C is called a property testing algorithm, and can be viewed as relaxation of a proper learning algorithm, which must also return an approximation to f if it is in C. We give property testing algorithms for many different classes C, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of n, better than the best possible learning algorithm.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Matulef, Kevin Michael

Advisor dc:contributor.advisor

• Ronitt Rubinfeld.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/54663

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/54663