nips nips2009 nips2009-166 nips2009-166-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Robert Nowak
Abstract: This paper addresses the problem of noisy Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued hypothesis through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. GBS is used in many applications, including fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and active learning. In most of these cases, the responses to queries can be noisy. Past work has provided a partial characterization of GBS, but existing noise-tolerant versions of GBS are suboptimal in terms of query complexity. This paper presents an optimal algorithm for noisy GBS and demonstrates its application to learning multidimensional threshold functions. 1
[AMM+ 98] E. M. Arkin, H. Meijer, J. S. B. Mitchell, D. Rappaport, and S.S. Skiena. Decision trees for geometric models. Intl. J. Computational Geometry and Applications, 8(3):343– 363, 1998. [Ang01] D. Angluin. Queries revisited. Springer Lecture Notes in Comp. Sci.: Algorithmic Learning Theory, pages 12–31, 2001. [BBZ07] M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In Conf. on Learning Theory (COLT), 2007. [Buc43] R. C. Buck. Partition of space. The American Math. Monthly, 50(9):541–544, 1943. [BZ74] M. V. Burnashev and K. Sh. Zigangirov. An interval estimation problem for controlled observations. Problems in Information Transmission, 10:223–231, 1974. [CN08] R. Castro and R. Nowak. Minimax bounds for active learning. IEEE Trans. Info. Theory, pages 2339–2353, 2008. [Das04] S. Dasgupta. Analysis of a greedy active learning strategy. In Neural Information Processing Systems, 2004. [FRPU94] U. Feige, E. Raghavan, D. Peleg, and E. Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001–1018, 1994. [GG74] M. R. Garey and R. L. Graham. Performance bounds on the splitting algorithm for binary testing. Acta Inf., 3:347–355, 1974. [GJ96] D. Geman and B. Jedynak. An active testing model for tracking roads in satellite images. IEEE Trans. PAMI, 18(1):1–14, 1996. [Heg95] T. Heged¨ s. Generalized teaching dimensions and the query complexity of learning. u In 8th Annual Conference on Computational Learning Theory, pages 108–117, 1995. [Hor63] M. Horstein. Sequential decoding using noiseless feedback. IEEE Trans. Info. Theory, 9(3):136–143, 1963. [HPRW96] L. Hellerstein, K. Pillaipakkamnatt, V. Raghavan, and D. Wilkins. How many queries are needed to learn? J. ACM, 43(5):840–862, 1996. [HR76] L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Inf. Process. Lett., 5:15–17, 1976. [K¨ a06] a¨ M. K¨ ari¨ inen. Active learning in the non-realizable case. In Algorithmic Learning a¨ a Theory, pages 63–77, 2006. [KK00] A. P. Korostelev and J.-C. Kim. Rates of convergence fo the sup-norm risk in image models under sequential designs. Statistics & Probability Letters, 46:391–399, 2000. [KK07] R. Karp and R. Kleinberg. Noisy binary search and its applications. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 881– 890, 2007. [KPB99] S. R. Kosaraju, T. M. Przytycka, and R. Borgstrom. On an optimal split tree problem. Lecture Notes in Computer Science: Algorithms and Data Structures, 1663:157–168, 1999. [Lov85] D. W. Loveland. Performance bounds for binary testing with arbitrary weights. Acta Informatica, 22:101–114, 1985. [Now08] R. Nowak. Generalized binary search. In Proceedings of the 46th Allerton Conference on Communications, Control, and Computing, pages 568–574, 2008. [Now09] R. Nowak. The geometry of generalized binary search. 2009. Preprint available at http://arxiv.org/abs/0910.4397. [R´ n61] e A. R´ nyi. On a problem in information theory. MTA Mat. Kut. Int. Kozl., page 505516, e 1961. reprinted in Selected Papers of Alfred R´ nyi, vol. 2, P. Turan, ed., pp. 631-638. e Akademiai Kiado, Budapest, 1976. [SS93] M.J. Swain and M.A. Stricker. Promising directions in active vision. Int. J. Computer Vision, 11(2):109–126, 1993. 9