jmlr jmlr2007 jmlr2007-14 jmlr2007-14-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Manu Chhabra, Robert A. Jacobs, Daniel Štefankovič
Abstract: In a search problem, an agent uses the membership oracle of a target concept to find a positive example of the concept. In a shaped search problem the agent is aided by a sequence of increasingly restrictive concepts leading to the target concept (analogous to behavioral shaping). The concepts are given by membership oracles, and the agent has to find a positive example of the target concept while minimizing the total number of oracle queries. We show that for the concept class of intervals on the real line an agent using a bounded number of queries per oracle exists. In contrast, for the concept class of unions of two intervals on the real line no agent with a bounded number of queries per oracle exists. We then investigate the (amortized) number of queries per oracle needed for the shaped search problem over other concept classes. We explore the following methods to obtain efficient agents. For axis-parallel rectangles we use a bootstrapping technique to obtain gradually better approximations of the target concept. We show that given rectangles R ⊆ A ⊆ R d one can obtain a rectangle A ⊇ R with vol(A )/vol(R) ≤ 2, using only O(d · vol(A)/vol(R)) random samples from A. For ellipsoids of bounded eccentricity in Rd we analyze a deterministic ray-shooting process which uses a sequence of rays to get close to the centroid. Finally, we use algorithms for generating random points in convex bodies (Dyer et al., 1991; Kannan et al., 1997) to give a randomized agent for the concept class of convex bodies. In the final section, we explore connections between our bootstrapping method and active learning. Specifically, we use the bootstrapping technique for axis-parallel rectangles to active learn axis-parallel rectangles under the uniform distribution in O(d ln(1/ε)) labeled samples. Keywords: computational learning theory, behavioral shaping, active learning
Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1988. Martin Anthony and Norman Biggs. Computational Learning Theory: An Introduction. Cambridge University Press, New York, NY, USA, 1992. 1862 B EHAVIORAL S HAPING FOR G EOMETRIC C ONCEPTS Peter Auer, Philip M. Long, and Aravind Srinivasan. Approximating hyper-rectangles: Learning and pseudorandom sets. Journal of Computer and System Sciences, 57(3):376–388, 1998. Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM, 51(4):540–556, July 2004. doi: 10.1145/1008731.1008733. Jean Bourgain. Random Points in Isotropic Convex Sets. Convex Geometric Analysis, pages 53–58. Cambridge University Press, Cambridge, 1999. Nader H. Bshouty and Nadav Eiron. Learning monotone DNF from a teacher that almost does not answer membership queries. Journal of Machine Learning Research, 3:49–57, 2003. Rui Castro, Rebecca Willett, and Robert Nowak. Faster rates in regression via active learning. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, Advances in Neural Information Processing Systems o 18, pages 179–186. MIT Press, Cambridge, MA, 2006. Sanjoy Dasgupta. Analysis of a greedy active learning strategy. In Lawrence K. Saul, Yair Weiss, and L´ on Bottou, editors, Advances in Neural Information Processing Systems 17, pages 337– e 344. MIT Press, Cambridge, MA, 2005. ¨ Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Y. Weiss, B. Sch olkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, pages 235–242. MIT Press, Cambridge, MA, 2006. Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based active learning. In Proceedings of the eighteenth Annual Conference on Learning Theory, pages 249– 263, 2005. Thomas G. Dietterich, Richard H. Lathrop, and Tom´ s Lozano-P´ rez. Solving the multiple instance a e problem with axis-parallel rectangles. Artificial Intelligence, 89(1-2):31–71, 1997. ISSN 00043702. Marco Dorigo and Marco Colombetti. Robot shaping: Developing autonomous agents through learning. Artificial Intelligence, 71(2):321–370, 1994. Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38(1):1–17, 1991. Bonnie Eisenberg and Ronald L. Rivest. On the sample complexity of PAC-learning using random and chosen examples. In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 154–162, San Francisco, CA, USA, 1990. Morgan Kaufmann Publishers Inc. Shai Fine and Yishay Mansour. Active sampling for multiple output identification. In Proceedings of the Nineteenth Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 2006, volume 4005 of Lecture Notes in Artificial Intelligence, pages 620–634. Springer, Berlin, 2006. Yoav Freund, H. Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28(2-3):133–168, 1997. 1863 ˇ ˇ C HHABRA , JACOBS , AND S TEFANKOVI C Paul W. Goldberg, Sally A. Goldman, and H. David Mathias. Learning unions of boxes with membership and equivalence queries. In COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, pages 198–207, New York, NY, USA, 1994. ACM Press. ISBN 0-89791-655-7. Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. In COLT ’91: Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pages 303–314, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc. ISBN 1-55860-213-5. Sally A. Goldman and H. David Mathias. Teaching a smart learner. In COLT ’93: Proceedings of the Sixth Annual Conference on Computational Learning Theory, pages 67–76, New York, NY, USA, 1993. ACM Press. ISBN 0-89791-611-5. Sally A. Goldman, Ronald L. Rivest, and Robert E. Schapire. Learning binary relations and total orders. SIAM J. Comput., 22(5):1006–1034, 1993. ISSN 0097-5397. Martin Gr¨ tschel, L´ szl´ Lov´ sz, and Alexander Schrijver. Geometric Algorithms and Combinatoo a o a rial Optimization. Springer-Verlag, Berlin, 1988. Tibor Heged˝ s. Combinatorial results on the complexity of teaching and learning. In MFCS ’94: u Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994, pages 393–402, London, UK, 1994. Springer-Verlag. ISBN 3-540-58338-6. Jeffrey C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414–440, 1997. doi: http://dx.doi.org/10.1006/jcss.1997.1533. Ravi Kannan, L´ szl´ Lov´ sz, and Mikl´ s Simonovits. Random walks and an O∗ (n5 ) volume algoa o a o rithm for convex bodies. Random Structures and Algorithms, 11(1):1–50, 1997. Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, 1994. George Konidaris and Andrew Barto. Autonomous shaping: Knowledge transfer in reinforcement learning. In Proceedings of the Twenty-third International Conference on Machine Learning, pages 489–496, New York, NY, USA, 2006. ACM Press. Nati Linial, Michael Luby, Michael Saks, and David Zuckerman. Efficient construction of a small hitting set for combinatorial rectangles in high dimension. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pages 258–267, New York, NY, USA, 1993. ACM Press. L´ szl´ Lov´ sz. An Algorithmic Theory of Numbers, Graphs and Convexity, volume 50 of CBMSa o a NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1986. Maja J. Mataric. Reward functions for accelerated learning. In Proceedings of the Eleventh International Conference on Machine Learning, pages 181–189, 1994. 1864 B EHAVIORAL S HAPING FOR G EOMETRIC C ONCEPTS Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995. ISBN 0-521-47465-5. Andrew Y. Ng, Daishi Harada, and Stuart J. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning, pages 278–287, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. Jette Randløv and Preben Alstrøm. Learning to drive a bicycle using reinforcement learning and shaping. In Proceedings of the Fifteenth International Conference on Machine Learning, pages 463–471, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. Mark Rudelson. Random vectors in isotropic position. Journal of Functional Analysis, 164(1): 60–72, 1999. Burrhus F. Skinner. The Behavior of Organisms. Appleton-Century-Crofts, New York, NY, USA, 1938. Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. 1865