Abstract
We consider a few particular exact learning models based on a random walk stochastic process, and thus more restricted than the well known general exact learning models. We give positive and negative results as to whether learning in these particular models is easier than in the general learning models.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angluin, D.: Queries and concept learning. Machine Learning 2, 319–342 (1987)
Bshouty, N.H.: Simple Learning Algorithms Using Divide and Conquer. Computational Complexity 6(2), 174–194 (1997)
Bartlett, P.L., Fischer, P., Höffgen, K.: Exploiting Random Walks for Learning. Information and Computation 176, 121–135 (2002)
Bshouty, N.H., Mossel, E., O’Donnell, R., Servedio, R.A.: Learning DNF from Random Walks. In: FOCS 2003, page.189 (2003)
Diaconis, P., Graham, R., Morrison, J.: Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures and Algorithms 1, 51–72 (1990)
Ficher, P., Simon, H.: On learning ring-sum expansions. SIAM J. Comput. 21, 181–192 (1992)
Hancock, T., Mansour, Y.: Learning Monotone kμ DNF Formulas on Product Distributions. In: Proc. 4th Ann. Workshop on Comp. Learning Theory, pp. 179–183 (1991)
Kearns, M., Li, M., Pitt, L., Valiant, L.: On the Learnability of Boolean Formulae. In: Proceedings of the 19th ACM Symposium on the Theory of Computing, pp. 285–195 (1987)
Littlestone, N.: Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm. Machine Learning 2(4), 285–318 (1987)
Mossel, E., O’Donnell, R., Servedio, R.A.: Learning juntas. STOC 2003: 206-212. Learning functions of k relevant variables. Journal of Computer and System Sciences 69(3), 421–434 (2004)
Pitt, L., Warmuth, M.K.: Prediction-preserving reducibility. Journal of Computer and System Science 41(3), 430–467 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bshouty, N.H., Bentov, I. (2006). On Exact Learning from Random Walk. In: Balcázar, J.L., Long, P.M., Stephan, F. (eds) Algorithmic Learning Theory. ALT 2006. Lecture Notes in Computer Science(), vol 4264. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11894841_17
Download citation
DOI: https://doi.org/10.1007/11894841_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-46649-9
Online ISBN: 978-3-540-46650-5
eBook Packages: Computer ScienceComputer Science (R0)