Cited By
View all- Meyer L(2001)Aspects of complexity of probabilistic learning under monotonicity constraintsTheoretical Computer Science10.1016/S0304-3975(00)00273-5268:2(275-322)Online publication date: 17-Oct-2001
Aspects of complexity of conservative probabilistic learning
Author: 
Léa MeyerAuthors Info & Claims
Pages 72 - 78
References
[1]
D. Angluin, Inductive In.tErence of formal languages from positive data, Information and Control 45 (1980) 117 - 135.
[2]
M. Blum, Maclfine independent theory of complexity of recursive functions, Journal of the ACM 14 (1967) 322 - 336.
[3]
R. Freiwfids, Finite identification of general recursive functions by probabilistic strategies, in: Proc. of the Conf. on Fundamentals of Computation Theory (Akademie-Verlag, Berlin, 1979) 138 - 145.
[4]
L. Fortnow, M. Gasarch, S. Jain, E. B. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman, R. Solovay, E Stephan, Extremes in the degrees in inferability, Ann. Pure Appl. Logic 66 (1994) 231 - 276.
[5]
R. Freivaids, E. Kinber, C.S. Smith, Oil the Intrinsic Complexity of Learning, Information and Computation 123 (1)64-71.
[6]
Gas~ch, W., Plezkoch, M., Learning via Queries to an oracle, in: Proc. 2th ACM Conf. on Comp. Learning lheory (ACM Press, Santa Cruz, July 1989) 175- 188.
[7]
Gasarch, W., Smith, C., Learning via queries, Journal of the ACM 39 l (1992) 649 - 675.
[8]
E.M. Gold, Language identification in the limit, Information and Control 10 (1967) 447 - 474.
[9]
S. Jain, A. Sharma, On tile intrinsic complexity of learning, in: Proc. of the 7th ACM Conf. on Comp. Learning Theory (ACM Press, 1994) 278 - 286.
[10]
J. Hopcrofi, J. Ullman, Introduction to Automata Theory Languages and Computation (Addison-Wesley Publ. Company, 1979).
[11]
M. Kummer, F. Stephan, On the structure of degrees of inferability, ill: Journal of Computer and System Sciences 52 (1996) 214- 238.
[12]
S. Lange, T. Zeugmann, Language learning ill the dependence on the space of hypotheses, in: Proc. of the 6th ACM Conf. on Comp. Learning Theory (ACM Press, Santa Cruz, July 1993) 127- 136.
[13]
L. Meyer, Probabilistic language learning under monotonicity constraints, in: K.P. Jantke, T. Shinohara, T. Zeugmann, eds., Proc. ofALT'95, Lect. notes in AI 997 (Springer, Berlin, 1995), 169- 185.
[14]
L. Meyer, Probabilistic language learning under monotonicity constraints, in: TCS 185 (1997) 81 - 128.
[15]
P. Odifreddi, Classical Recursion lheory, North Holland, 1989.
[16]
D. Osherson, M. Stob, S. Weinstein, Systems that nitive and Computer Scientists (MIT Press, Cambridge MA, 1986).
[17]
L. Pitt, Probabilistic Inductive Inference, d. of the ACM 36, 2 (1989) 383 - 433.
[18]
T. Slaman, R. Solovay, When oracles do not help, Proc. of the 4th ACM Conf. on Comp. Learning Theory (ACM Press, Santa Cruz, July 1991), 379 - 383.
[19]
R. Soare, Recursively Enumerable Sets and Degrees (Springer, 1987)
[20]
F. Stephan, Noisy inference and oracles, in: TCS 185 (1997) 129- 157.
[21]
L. Valiant, A Theory of the Learnable, Comm. of the ACM 27, 11 (1984) 1134 - 1142.
[22]
. Wiehagen, R. Freivalds, E.B. Kinber, On the Power of Probabilistic Strategies in Inductive Inference, Theoretical Computer Science 2g (1984), 111 - 133.
[23]
R. Wiehagen, R. Freivalds, E.B. Kinber, Probabilistic versus Deterministic Inductive Inference in Nonstandard Numberings, Zeitschr. f. math. Logik und Grundlagen d. Math. 34 (1988) 531 - 539.
[24]
T. Zeugmann, S. Lange, A Guided Tour Across the Boundaries of Learning Recursive Languages, in: K.P. Jantke and S. Lange, eds., Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Artificial Intelligence 961 (Springer, Berlin, 1995) 193- 262.
Index Terms
- Aspects of complexity of conservative probabilistic learning
Recommendations
A less conservative robust stability criteria for uncertain neutral systems with mixed delays
This paper is concerned with the problem of the delay-dependent robust stability of neutral systems with mixed delays and time-varying structured uncertainties. By considering the cross-terms with additional design parameters, a complete form of ...
Less conservative stability criteria for neural networks with interval time-varying delay based on delay-partitioning approach
This paper is concerned with the problem of delay-dependent asymptotic stability for neural networks with interval time-varying delay. A delay-partitioning approach is used in this paper, in which the delay interval is partitioned into multiple ...
Aspects of complexity of probabilistic learning under monotonicity constraints
Algorithmic learning theoryIn the setting of learning indexed families, probabilistic learning under monotonicity constraints is more powerful than deterministic learning under monotonicity constraints, even if the probability is close to 1, provided the learning machines are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1998 ACM.
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]
Sponsors
- University of Wisconsin: University of Wisconsin
- SIGAI: ACM Special Interest Group on Artificial Intelligence
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- UC @ Santa Cruz: UC @ Santa Cruz
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 1998
Check for updates
Qualifiers
- Article
Conference
COLT98: The 11th Annual Conference on Computational Learning Theroy
July 24 - 26, 1998
Wisconsin, Madison, USA
Acceptance Rates
Overall Acceptance Rate 35 of 71 submissions, 49%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 201Total Downloads
- Downloads (Last 12 months)48
- Downloads (Last 6 weeks)7
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
Cited By
View all- Meyer L(2001)Aspects of complexity of probabilistic learning under monotonicity constraintsTheoretical Computer Science10.1016/S0304-3975(00)00273-5268:2(275-322)Online publication date: 17-Oct-2001
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in