Learning decision trees using the Fourier spectrum

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning decision trees using the Fourier spectrum

Full text

Pdf (828 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 455 - 464

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Eyal Kushilevitz	Technion, Haifa, Israel
Yishay Mansour	Harvard Univ., Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 120, Citation Count: 24

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103466 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AM91	William Aiello , Milena Mihail, Learning the Fourier spectrum of probabilistic lists and trees, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 28-30, 1991, San Francisco, California, United States
	Ang87	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	Bel91	M. Bellare, THE SPECTRAL NORM OF FINITE FUNCTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1991
	BHO90	Y. Brandman , A. Orlitsky , J. Hennessy, A Spectral Lower Bound Technique for the Size of Decision Trees and Two-Level AND/OR Circuits, IEEE Transactions on Computers, v.39 n.2, p.282-287, February 1990 [doi>10.1109/12.45216]
	BS89	J. Bruck and R. Smolensky. Polynomial threshold functions, AC~ functions and spectral norms. Technical Report RJ 7140, IBM Research, 1989.
	Dia83	Persi Diaconis. The use of Group representation in probability and statistics. 1983.
	EH89	A. Ehrenfeucht , D. Haussler , M. Kearns, Learning decision trees from random examples needed for learning, Information and Computation, v.82 n.3, p.231-246, Sep. 1989 [doi>10.1016/0890-5401(89)90001-1]
	GL89	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	Han90	Thomas R. Hancock, Identifying μ-formula decision trees with queries, Proceedings of the third annual workshop on Computational learning theory, p.23-37, August 06-08, 1990, Rochester, New York, United States
	Han91	Thomas Hancock. Learning 2# DNF and k# decision trees. Unpublished Manuscript, 1991.
	HR89	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	LMN89	N. Linial, Y. M#nsour, #nd N. Nisan. Constant depth circuits, fourier transform and leurnubility. In 30th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, p#ges 574-579, October 1989.
	RB89	M. Ron Roth and Gyora M. Benedek. Interpolation and approximation of light boolean functions. (unpublished manuscript), 1980.
	Val84	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

CITED BY 24

	Mihir Bellare, A technique for upper bounding the spectral norm with applications to learning, Proceedings of the fifth annual workshop on Computational learning theory, p.62-70, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.219-228, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Michael Kearns , Yishay Mansour, On the boosting ability of top-down decision tree learning algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.459-468, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Thomas R. Hancock, Learning k&mgr; decision trees on the uniform distribution, Proceedings of the sixth annual conference on Computational learning theory, p.352-360, July 26-28, 1993, Santa Cruz, California, United States
	Noam Nisan , Mario Szegedy, On the degree of Boolean functions as real polynomials, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.462-467, May 04-06, 1992, Victoria, British Columbia, Canada
	Howard Aizenstein , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Robert E. Schapire , Linda M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Proceedings of the sixth annual conference on Computational learning theory, p.17-26, July 26-28, 1993, Santa Cruz, California, United States
	Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Meera Sitharam, Pseudorandom generators and learning algorithms for AC, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.478-486, May 23-25, 1994, Montreal, Quebec, Canada
	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
	Hillol Kargupta , Byung-Hoon Park , Sweta Pittie , Lei Liu , Deepali Kushraj , Kakali Sarkar, MobiMine: monitoring the stock market from a PDA, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
	Dan Boneh, Learning using group representations (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.418-426, July 05-08, 1995, Santa Cruz, California, United States
	Nader H. Bshouty , Vitaly Feldman, On using extended statistical queries to avoid membership queries, The Journal of Machine Learning Research, 2, p.359-395, 3/1/2002
	Hillol Kargupta , Byung-Hoon Park, A Fourier Spectrum-Based Approach to Represent Decision Trees for Mining Data Streams in Mobile Environments, IEEE Transactions on Knowledge and Data Engineering, v.16 n.2, p.216-229, February 2004
	Hillol Kargupta, Gene expression and scalable genetic search, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2003
	Nader H. Bshouty, The monotone theory for the PAC-model, Information and Computation, v.186 n.1, p.20-35, 10 October 2003
	Hillol Kargupta , Rajeev Ayyagari , Samiran Ghosh, Learning Functions Using Randomized Genetic Code-Like Transformations: Probabilistic Properties and Experimentations, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.894-908, August 2004
	Nader H. Bshouty , Richard Cleve , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.130-139, July 12-15, 1994, New Brunswick, New Jersey, United States
	A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	B. Park , H. Kargupta , E. Johnson , E. Sanseverino , D. Hershberger , L. Silvestre, Distributed, Collaborative Data Analysis from Heterogeneous Sites Using a Scalable Evolutionary Technique, Applied Intelligence, v.16 n.1, p.19-42, January-February 2002
	Jeffrey Jackson, On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries, Annals of Mathematics and Artificial Intelligence, v.39 n.3, p.291-313, November 2003
	Hillol Kargupta , Samiran Ghosh, Toward Machine Learning Through Genetic Code-like Transformations, Genetic Programming and Evolvable Machines, v.3 n.3, p.231-258, September 2002
	Ali A. Kanso, An efficient cryptosystem Delta for stream cipher applications, Computers and Electrical Engineering, v.35 n.1, p.126-140, January, 2009
	Yuval Ishai , Tal Malkin , Martin J. Strauss , Rebecca N. Wright, Private multiparty sampling and approximation of vector combinations, Theoretical Computer Science, v.410 n.18, p.1730-1745, April, 2009