Active sampling for multiple output identification |
| |
Authors: | Shai Fine Yishay Mansour |
| |
Affiliation: | (1) IBM Research Laboratory in Haifa, Mount Carmel, Haifa, 31905, Israel;(2) School of Computer Science, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | We study functions with multiple output values, and use active sampling to identify an example for each of the possible output
values. Our results for this setting include: (1) Efficient active sampling algorithms for simple geometric concepts, such
as intervals on a line and axis parallel boxes. (2) A characterization for the case of binary output value in a transductive
setting. (3) An analysis of active sampling with uniform distribution in the plane. (4) An efficient algorithm for the Boolean
hypercube when each output value is a monomial.
Editors: Hans Ulrich Simon, Gabor Lugosi, Avrim Blum.
A preliminary version of this work was presented in the 19th Annual Conference on Learning Theory (COLT), 2006.
This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778,
by a grant No. 1079/04 from the Israel Science Foundation, by a grant from BSF and an IBM faculty award. This publication
only reflects the authors’ views. |
| |
Keywords: | Active learning Active sampling Hitting VC dimension Transductive learning Output identification Separation dimension |
本文献已被 SpringerLink 等数据库收录! |
|