More Web Proxy on the site http://driver.im/

article

Free access

Computational limitations on learning from examples

Authors:

Leslie G. ValiantAuthors Info & Claims

Journal of the ACM (JACM), Volume 35, Issue 4

Pages 965 - 984

https://doi.org/10.1145/48014.63140

Published: 01 October 1988 Publication History

Abstract

The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes include (a) disjunctions of two monomials, (b) Boolean threshold functions, and (c) Boolean formulas in which each variable occurs at most once. Relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.

References

[1]

ANGLUIN, D. On the complexity of minimum inference of regular sets. Inf. Control 39 (1978), 337-350.

[2]

ANGLUIN, D. Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21 (1980), 46-62.

[3]

ANGLUIN, D.Inductive inference of formal languages from positive data. Inf. Control 45 (1980), 117-135.

[4]

ANGLUIN, n. Inference of reversible languages. J. ACM 29, 3 (July 1982), 741-765.

[5]

ANGLUIN, D. Remarks on the difficulty of finding a minimal disjunctive normal form for Boolean functions. Unpublished manuscript.

[6]

ANGLUIN, n. Learning regular sets from queries and counter-examples. Yale University Tech. Rep. YALEU/DCS/464, 1986.

[7]

ANGLUIN, n., AND SMITH, C. inductive inference: Theory and methods. AC;vl Comput. Surv. 15, 3 (Sept. 1983), 237-269.

[8]

BLUM, L., AND BLUM, M. Toward a mathematical theory of inductive inference. Inf. Control 28 (1975), 125-155.

[9]

BLUMER, A., EHRENFEUCHT, m., HAUSSLER, D., AND WARMUTH, M. Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension. In Proceedings of the 18th Annual Symposium on the _Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York~ !986, pp. 273-282.

[10]

BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. Occam's Razor. Inf. Process. Lett. 24 (1987), 377-380.

[11]

CASE, J., AND SMITH, C. Comparison of identification criteria for machine inductive inference. Theoret. Comput. Sci. 25 (1983), 193-220.

[12]

CHVATAL, V. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 3 (1979), 233-235.

[13]

DALEY, R. On the error correcting power of pluralism in BC-type inductive inference. Theoret. Comput. Sci. 24 (1983), 95-104.

[14]

DIETTERICH, T. C., AND MICHALSKI, R.S. A comparative review of selected methods for learning from examples. In Machine Learning. An Artificial Intelligence Approach. Tioga, Palo Alto, Calif., 1983.

[15]

FREIVALD, R.V. Functions computable in the limit by probabilistic machines. In Mathematical Foundations of Computer Science (3rd Symposium at Jadwisin near Warsaw, 1974). Springer- Verlag, New York, 1975.

[16]

FREIVALD, R.V. Finite identification of general recursive functions by probabilistic strategies. In Proceedings of the Conference on Algebraic, Arithmetic, and Categorial Methods in Computation Theory. Akadamie-Verlag, New York, 1979, pp. 138-145.

[17]

GAREY, M., AND JOHNSON, D. The complexity of near-optimal graph coloring. J. ACM 23, 1 (Jan. 1976), 43-49.

[18]

GAREY, M. AND JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP- Completeness. Freeman, San Francisco, 1979.

[19]

GILL, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675-695.

[20]

GOLD, E.M. Complexity of automaton identification from given data. Inf. Control 37 (1978), 302-320.

[21]

GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. How to construct random functions. J. ACM 33, 3 (July 1986), 792-807.

[22]

HA USSLER, D. Quantifying the inductive bias in concept learning. In Proceedings of AAAI-86 (Philadelphia, Pa.). Morgan Kaufman, Los Altos, Calif., 1986, pp. 485-489.

[23]

HORNING, J.J. A study of grammatical inference. Ph.D. Dissertation. Computer Science Dept., Stanford Univ., Stanford, Calif., 1969.

[24]

JOHNSON, D. S. Worst case behaviour of graph coloring algorithms. In Proceedings of the 5th South-Eastern Conference on Combinatorics, Graph Theory, and Computing. Utilitas Mathematica, Winnipeg, Canada, 1974, pp. 513-528.

[25]

LEVIN, L. Universal sorting problems. Prob. Pered. Inf. 9, 3 (1973), pp. I 15-116.

[26]

MICHALSKI, R. S., CARBONELL, J. G., AND MITCHELL, T. M. Machine Learning." An Artificial Intelligence Approach. Tioga, Palo Alto, Calif., 1983.

[27]

PITT, L. A characterization of probabilistic inference. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Washington, D.C., 1984, pp. 485-494.

[28]

PODNIEKS, K.M. Probabilistic synthesis of enumerated classes of functions. Soy. Math. Dokl. 16 (1975), I042-1045.

[29]

ROYER, j.S. On machine inductive inference of approximations. Inf. Control, to appear.

[30]

RUDICH, S. Inferring the structure of a Markov chain from its output. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Washington, D.C., 1985, pp. 321-325.

[31]

SMITH, C. H., AND VELAUTHAPILLAI, M. On the inference of approximate programs. Tech. Rep. 1427, Dept. of Computer Science, Univ. of Maryland, College Park, Md.

[32]

VALIANT, L.G. A theory ofthe learnable. Commun. ACM27, 11 (1984), 1134-1142.

[33]

VALIANT, L. G. Learning disjunctions of conjunctions. In Proceedings of the 9th IJCAI (Los Angeles, Calif., Aug. 1985), vol. 1. Morgan Kaufman, Los Altos, Calif., 1985, pp. 560-566.

[34]

WIEHAGEN, R., FREIVALD, R., AND KINBER, E. B. On the power of probabilistic strategies in inductive inference. Theoret. Comput. Sci. 28 (1984), I I 1-133.

[35]

WIGDERSON, A. A new approximate graph coloring algorithm. In Proceedings of the 14th Annual Symposium on the Theory of Computing. ACM, New York, 1982, pp. 325-329.

Cited By

Rivelli L(2024)The evolving hierarchy of naturalized philosophy: A metaphilosophical sketchMetaphilosophy10.1111/meta.1269055:3(285-300)Online publication date: 26-Jun-2024
https://doi.org/10.1111/meta.12690
Golowich NMoitra ARohatgi D(2024)Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00117(1953-1967)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00117
Koch CStrassle CTan L(2024)Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00114(1893-1910)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00114
Show More Cited By

Index Terms

Computational limitations on learning from examples
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Logical and relational learning
        Inductive logic learning
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Models of computation
    1. Probabilistic computation

Recommendations

Efficiency and computational limitations of learning algorithms
Complexity theoretic limitations on learning halfspaces
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution D on Q^n X {-1,1}. We define Err_H(D) as the least error of a halfspace classifier for D. A learner who can access D has to return a ...
Intractability results for problems in computational learning and approximation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 35, Issue 4

Oct. 1988

242 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/48014

Issue’s Table of Contents

Copyright © 1988 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1988

Published in JACM Volume 35, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

378
Total Citations
View Citations
2,141
Total Downloads

Downloads (Last 12 months)204
Downloads (Last 6 weeks)31

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rivelli L(2024)The evolving hierarchy of naturalized philosophy: A metaphilosophical sketchMetaphilosophy10.1111/meta.1269055:3(285-300)Online publication date: 26-Jun-2024
https://doi.org/10.1111/meta.12690
Golowich NMoitra ARohatgi D(2024)Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00117(1953-1967)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00117
Koch CStrassle CTan L(2024)Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00114(1893-1910)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00114
ten Cate BFunk MJung JLutz C(2024)On the non-efficient PAC learnability of conjunctive queriesInformation Processing Letters10.1016/j.ipl.2023.106431183(106431)Online publication date: Jan-2024
https://doi.org/10.1016/j.ipl.2023.106431
Stenseke J(2024)On the computational complexity of ethics: moral tractability for minds and machinesArtificial Intelligence Review10.1007/s10462-024-10732-357:4Online publication date: 31-Mar-2024
https://doi.org/10.1007/s10462-024-10732-3
Jung AJung A(2024)EinführungMaschinelles Lernen10.1007/978-981-99-7972-1_1(1-20)Online publication date: 14-Feb-2024
https://doi.org/10.1007/978-981-99-7972-1_1
Liu YWang SWang YLi YZhu XLai XZhang XLi XXiao XWang J(2023)What makes TMB an ambivalent biomarker for immunotherapy? A subtle mismatch between the sample-based design of variant callers and real clinical cohortFrontiers in Immunology10.3389/fimmu.2023.115122414Online publication date: 25-May-2023
https://doi.org/10.3389/fimmu.2023.1151224
Brand CGanian RSimonov KWilliams BChen YNeville J(2023)A parameterized theory of PAC learningProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i6.25837(6834-6841)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i6.25837
Koch CStrassle CTan L(2023)Properly learning decision trees with queries is NP-hard2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00146(2383-2407)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00146
Hirahara SNanashima M(2023)Learning in Pessiland via Inductive Inference2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00033(447-457)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00033
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents