Article

Free access

Exploiting random walks for learning

Authors:

Peter L. Bartlett,

Paul Fischer,

Klaus-Uwe HöffgenAuthors Info & Claims

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

Pages 318 - 327

https://doi.org/10.1145/180139.181167

Published: 16 July 1994 Publication History

PDF eReader

Abstract

In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. We define deterministic and probabilistic learning models of this sort and investigate the relationships between them and with other models. The fact that successive examples are related can often be used to gain additional information similar to the information gained by membership queries. We show that this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions, 2-term RSE, and 2-term-DNF, when the examples are generated by a random walk on {0,1}ⁿ.

References

[1]

D. Aldous and U. Vazirani. A Markovian extension of Valiant's learning model. In Proc. of the 31st Symposium on the Foundations of Cornp. Sci., pages 392-396. IEEE Computer Society Press, Los Alamitos, CA, 1990.

Digital Library

Google Scholar

[2]

P. L. Bartlett. Learning with a slowly changing distribution. In Proc. 5th Annu. Workshop on Cornput. Learning Theory, pages 243-252. ACM Press, New York, NY, 1992.

Digital Library

Google Scholar

[3]

A. Blum. Separating PAC and mistake-bound learning models over the boolean domain. Proc. 31th Annu. IEEE Sympos. Found. Comput. Sci., 1990.

Crossref

Google Scholar

[4]

A. Blum and S. Rudich. Fast learning of k-term DNF formulas with queries. In Proc. ~~th Annu. ACM Sympos. Theory Comput., pages 382-389. ACM Press, New York, NY, 1992.

Digital Library

Google Scholar

[5]

P. Diaconis, R. Graham, and J. Morrison. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures and Algorithms, 1:51-72, 1990.

Crossref

Google Scholar

[6]

P. Fischer and H. Simon. On learning ring-sum expansions. SIAM J. Comput., 21:181-192, 1992.

Digital Library

Google Scholar

[7]

M. Flammini, A. Marchetti-Spaccamela, and L. K. Kucera. Learning DNF formulae under classes of probability distributions. In Proc. 5th Annu. Workshop on Comput. Learning Theory, pages 85-92. ACM Press, New York, NY, 1992.

Digital Library

Google Scholar

[8]

Y. Freund, M. Kearns, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie. Efficient learning of typical finite automata from random walks. In Proc. 25ih Annu. ACM Sympos. Theory Comput., pages 315-324. ACM Press, New York, NY, 1993.

Digital Library

Google Scholar

[9]

D. Haussler, M. Kearns, N. Littlestone, and M. Warmuth. Equivalence of models for polynomial learnability. Information and Computation, 95:129-161, 1991.

Digital Library

Google Scholar

[10]

D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting {0,1} functions on randomly drawn points. In Proceedings of the ~9th Annual IEEE Symposium on Foundations of Computer Science, pages 100-109. IEEE Computer Society Press, 1988.

Google Scholar

[11]

M. Kearns, L. Pitt, and L. Valiant. Recent results on boolean concept learning. In Proc. Jth Workshop on Machine Learning, 1987.

Crossref

Google Scholar

[12]

N. Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1988.

Crossref

Google Scholar

[13]

L. Pitt and L. Valiant. Computational limitations on learning from examples. J. ACM, 35:965-984, 1988.

Digital Library

Google Scholar

[14]

L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, Nov. 1984.

Digital Library

Google Scholar

Cited By

View all

Katselis DBeck CSrikant R(2019)Mixing Times and Structural Inference for Bernoulli Autoregressive ProcessesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2018.28295206:3(364-378)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TNSE.2018.2829520
Bresler GGamarnik DShah D(2014)Learning graphical models from the Glauber dynamics2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2014.7028584(1148-1155)Online publication date: Sep-2014
https://doi.org/10.1109/ALLERTON.2014.7028584
Perkins THallett M(2010)A Trade-Off between Sample Complexity and Computational Complexity in Learning Boolean Networks from Time-Series DataIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2008.387:1(118-125)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1109/TCBB.2008.38
Show More Cited By

Index Terms

Exploiting random walks for learning

Recommendations

Learning DNF from random walks
Special issue: Learning theory 2003

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0,1}^n. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for ...
Pseudorandom generators from polarizing random walks
CCC '18: Proceedings of the 33rd Computational Complexity Conference

We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1, 1]ⁿ. ...
Speeding up random walks with neighborhood exploration
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

We consider the following marking process (rw-rand) made by a random walk on an undirected graph G. Upon arrival at a vertex v, it marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v. We also consider a variant of this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

July 1994

376 pages

ISBN:0897916557

DOI:10.1145/180139

Chairman:
Manfred Warmuth
Univ. of California, Santa Cruz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

7COLT94

Sponsor:

7COLT94: 7th Annual Conference on Computational Learning Theory

July 12 - 15, 1994

New Jersey, New Brunswick, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
69
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)7

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Katselis DBeck CSrikant R(2019)Mixing Times and Structural Inference for Bernoulli Autoregressive ProcessesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2018.28295206:3(364-378)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TNSE.2018.2829520
Bresler GGamarnik DShah D(2014)Learning graphical models from the Glauber dynamics2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2014.7028584(1148-1155)Online publication date: Sep-2014
https://doi.org/10.1109/ALLERTON.2014.7028584
Perkins THallett M(2010)A Trade-Off between Sample Complexity and Computational Complexity in Learning Boolean Networks from Time-Series DataIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2008.387:1(118-125)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1109/TCBB.2008.38
Bshouty NMossel EO'Donnell RServedio R(2005)Learning DNF from random walksJournal of Computer and System Sciences10.1016/j.jcss.2004.10.01071:3(250-265)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1016/j.jcss.2004.10.010
Gamarnik D(2003)Extension of the PAC framework to finite and countable Markov chainsIEEE Transactions on Information Theory10.1109/TIT.2002.80613149:1(338-345)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1109/TIT.2002.806131
Bshouty NMossel EO'Donnell RServedio R(2003)Learning DNF from random walks44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.10.1109/SFCS.2003.1238193(189-198)Online publication date: 2003
https://doi.org/10.1109/SFCS.2003.1238193
Najarian KDumont GDavies MHeckman N(2000)Neural ARX Models and PAC LearningAdvances in Artificial Intelligence10.1007/3-540-45486-1_25(305-315)Online publication date: 19-May-2000
https://doi.org/10.1007/3-540-45486-1_25
Gamarnik DBen-David SLong P(1999)Extension of the PAC framework to finite and countable Markov chainsProceedings of the twelfth annual conference on Computational learning theory10.1145/307400.307478(308-317)Online publication date: 6-Jul-1999
https://dl.acm.org/doi/10.1145/307400.307478
Campi MKumar P(1998)Learning dynamical systems in a stationary environmentSystems & Control Letters10.1016/S0167-6911(98)00005-X34:3(125-132)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1016/S0167-6911%2898%2900005-X

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Learning DNF from random walks

Pseudorandom generators from polarizing random walks

Speeding up random walks with neighborhood exploration