On learning embedded midbit functions
Pages 13 - 23
Abstract
A midbit function on l binary inputs x1,...,xl outputs the middle bit in the binary representation of x1+...+xl. We consider the problem of Probably Approximately Correct (PAC) learning embedded midbit functions, where the set S ⊂ {x1,...,xn} of relevant variables on which the midbit depends is unknown to the learner.To motivate this problem, we first point out that a result of Green et al. implies that a polynomial time learning algorithm for the class of embedded midbit functions would immediately yield a fairly efficient (quasipolynomial time) (PAC) learning algorithm for the entire complexity class ACC. We then give two different subexponential learning algorithms, each of which learns embedded midbit functions under any probability distribution in 2√n log n time. Finally, we give a polynomial time algorithm for learning embedded midbit functions under the uniform distribution.
References
[1]
{1} E. Allender, U. Hertrampf, Depth reduction for circuits of unbounded fan-in, Inform. Comput. 112 (2) (1994) 217-238.
[2]
{2} D. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1, J. Comput. System Sci. 38 (1) (1989) 150-164.
[3]
{3} D. Barrington, D. Therien, Finite monoids and the fine structure of NC 1, J. Assoc. Comput. Math. 35 (4) (1988) 941-952.
[4]
{4} R. Beigel, J. Tarui, On ACC, Comput. Complexity 4 (1994) 350-366.
[5]
{5} A. Blum, P. Chalasani, J. Jackson, On learning embedded symmetric concepts, in: Proc. Sixth Annu. Conf. on Computational Learning Theory, 1993, pp. 337-346.
[6]
{6} A. Blumer, A. Ehrenfeucht, D. Haussler, M. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, J. Assoc. Comput. Math. 36 (4) (1989) 929-965.
[7]
{7} P. Fischer, H.U. Simon, On learning ring-sum expansions, SIAM J. Comput. 21 (1) (1992) 181-192.
[8]
{8} R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1994.
[9]
{9} F. Green, J. Kobler, K. Regan, T. Schwentick, J. Toran, The power of the middle bit of a #P function, J. Comput. System Sci. 50 (3) (1998) 456-467.
[10]
{10} D. Helmbold, R. Sloan, M. Warmuth, Learning integer lattices, SIAM J. Comput. 21 (2) (1992) 240-266.
[11]
{11} A. Klivans, R. Servedio, Learning DNF in time 2O(n 1/3), in: Proc. Thirty-Third Annu. Symp. on Theory of Computing, 2001, pp. 258-265.
[12]
{12} P. McKenzie, D. Therien, Automata theory meets circuit complexity, in: Proc. Internat. Colloq. on Automata, Languages and Programming, 1989, pp. 589-602.
[13]
{13} M. Minsky, S. Papert, Perceptrons: An Introduction to Computational Geometry, MIT Press, Cambridge, MA, 1968.
[14]
{14} C. Ramus, Solution générale d'un problè d'analyse combinatoire, J. Reine Angew. Math. 11 (1834) 353-355.
[15]
{15} J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, 1958.
[16]
{16} J. Riordan, Combinatorial Identities, Wiley, New York, 1968.
[17]
{17} L. Valiant, A theory of the learnable, Comm. ACM 27 (11) (1984) 1134-1142.
[18]
{18} A. Yao, Separating the polynomial time hierarchy by oracles, in: Proc. Twenty-Sixth Annu. Symp. on Foundations of Computer Science, 1985, pp. 1-10.
[19]
{19} A. Yao, On ACC and threshold circuits, in: Proc. Thirty-First Annu. Symp. on Foundations of Computer Science, 1990, pp. 619-627.
Index Terms
- On learning embedded midbit functions
Recommendations
On Learning Embedded Midbit Functions
ALT '02: Proceedings of the 13th International Conference on Algorithmic Learning TheoryA midbit function on l binary inputs x 1 , ..., x l outputs the middle bit in the binary representation of x 1 + ... + x l . We consider the problem of PAC learning embedded midbit functions, where the set S { x 1 , ..., x n } of ...
On learning monotone boolean functions under the uniform distribution
Algorithmic learning theory(ALT 2002)In this paper, we prove two general theorems on monotone Boolean functions which are useful for constructing a learning algorithm for monotone Boolean functions under the uniform distribution.A monotone Boolean function is called fair if it takes the ...
Perceptron, Winnow, and PAC Learning
We analyze the performance of the widely studied Perceptron and Winnow algorithms for learning linear threshold functions under Valiant's probably approximately correct (PAC) model of concept learning. We show that under the uniform distribution on ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 18 January 2006
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024