Name
Title | ||
|---|---|---|
Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions |
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 (Page and Ray, 2003). 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 prove a lemma establishing a property of Boolean functions that may be of independent interest. Using this lemma, we give two new algorithms for finding relevant variables of correlation immune functions in the PDC model. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1577069.1755866 | Journal of Machine Learning Research |
Keywords | Field | DocType |
boolean function,correlation immune functions,uniform distribution,boolean functions,relevant variables,identify relevant variables,exploiting product distributions,relevant variable,product distributions,correlation immune function,skewing,product distribution,parity function,independent interest,pdc model,correlation immune boolean function,product distribution choice,immune function,decision tree | Boolean network,Boolean function,Decision tree,Heuristic,Mathematical optimization,Parity function,Uniform distribution (continuous),Correlation,Artificial intelligence,Lemma (mathematics),Machine learning,Mathematics | Journal |
Volume | ISSN | Citations |
10, | 1532-4435 | 0 |
PageRank | References | Authors |
0.34 | 32 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lisa Hellerstein | 1 | 710 | 121.90 |
| Bernard Rosell | 2 | 6 | 1.18 |
| Eric Bach | 3 | 14 | 3.13 |
| Soumya Ray | 4 | 94 | 8.89 |
| David Page | 5 | 390 | 31.33 |