Abstract | ||
---|---|---|
A new research frontier in AI and data mining seeks to develop methods to automatically discover relevant variables among many irrelevant ones. In this paper, we present four algorithms that output such crucial variables in PAC model with membership queries. The first algorithm executes the task under any unknown distribution by measuring the distance between virtual and real targets. The second algorithm exhausts virtual version space under an arbitrary distribution. The third algorithm exhausts universal set under the uniform distribution. The fourth algorithm measures influence of variables under the uniform distribution. Knowing the number r of relevant variables, the first algorithm runs in almost linear time for r. The second and the third ones use less membership queries than the first one, but runs in time exponential for r. The fourth one enumerates highly influential variables in quadratic time for r. |
Year | DOI | Venue |
---|---|---|
1999 | 10.1007/3-540-46769-6_26 | ALT |
Keywords | Field | DocType |
arbitrary distribution,uniform distribution,number r,relevant variable,membership query,membership queries,unknown distribution,quadratic time,finding relevant variables,time exponential,linear time,pac model,algorithm measure,data mining | Information processing,Exponential function,Computer science,Concept learning,Uniform distribution (continuous),Algorithm,Statistical theory,Time complexity,Version space,Universal set | Conference |
Volume | ISSN | ISBN |
1720 | 0302-9743 | 3-540-66748-2 |
Citations | PageRank | References |
7 | 0.49 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Guijarro | 1 | 33 | 2.22 |
Jun Tarui | 2 | 134 | 16.16 |
Tatsuie Tsukiji | 3 | 50 | 7.14 |