About This Item

Ask the MINDS@UW Librarian

Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions

Show full item record

File(s):

Author(s)
Hellerstein, Lisa; Rosell, Bernard; Bach, Eric; Ray, Soumya; Page, David
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Date
Mar 15, 2012
Abstract
A Boolean function f is correlation immune if each input variable is independent of the output, under the uniform distribution on inputs. (For example, the parity function is correlation immune.) We consider the problem of identifying relevant variables of a correlation immune function, in the presence of irrelevant variables. We address this problem in two different contexts. First, we analyze Skewing, a heuristic method that was developed to improve the ability of greedy decision tree algorithms to identify relevant variables of correlation immune Boolean functions, given examples drawn from the uniform distribution. We present theoretical results revealing both the capabilities and limitations of skewing. Second, we explore the problem of identifying relevant variables in the Product Distribution Choice (PDC) learning model, a model in which the learner can choose product distributions and obtain examples from them. We give two new algorithms for finding relevant variables of correlation immune functions in the PDC model.
Permanent link
http://digital.library.wisc.edu/1793/60618 
Export
Export to RefWorks 
‚Äč

Part of

Show full item record

Search and browse




About MINDS@UW

Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.