A theory of the learnable

Valiant, L. G.·1984·Communications of the ACM
DOI 10.1145/1968.1972

Cited by (1,004)

Items 301–400 of 1,004

  1. ‘Ideal learning’ of natural language: Positive results about learning from positive evidence
    Nick Chater, Paul M. B. Vitanyi · 2007 · Journal of Mathematical Psychology
  2. Posterior Probability Support Vector Machines for Unbalanced Data
    Qing Tao, Guo-xiang Wu, Feng Wang, Jue Wang · 2005 · IEEE Transactions on Neural Networks
  3. Learnability with respect to fixed distributions
    Gyora M. Benedek, Alon Itai · 1991 · Theoretical Computer Science
  4. Deep learning-based classification of posttraumatic stress disorder and depression following trauma utilizing visual and auditory markers of arousal and mood
    Schultebraucks, Katharina, Yadav, Vijay, Shalev, Arieh Y., Bonanno, George A., Galatzer-Levy, Isaac R. · 2022 · Psychological Medicine
  5. Reliable prediction intervals with regression neural networks
    Harris Papadopoulos, Haris Haralambous · 2011 · Neural Networks
  6. Intrinsically Motivated Hierarchical Skill Learning in Structured Environments
    Christopher M. Vigorito, Andrew G. Barto · 2010 · IEEE Transactions on Autonomous Mental Development
  7. A theory of formal synthesis via inductive learning
    Susmit Jha, Sanjit Arunkumar Seshia · 2017 · Acta Informatica
  8. Machine Learning
    Xian‐Da Zhang · 2020 · Springer eBooks
  9. Threats to Training: A Survey of Poisoning Attacks and Defenses on Machine Learning Systems
    Zhibo Wang, Jingjing Ma, Xue Wang, Jiahui Hu, Zhan Qin, Kui Ren · 2022 · ACM Computing Surveys
  10. Formal grammar and information theory: together again?
    Fernando M. B. Pereira · 2000 · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences
  11. Sampling algorithms
    Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar · 2001 · ACM Symposium on Theory of Computing (STOC)
  12. Cryptographic hardness for learning intersections of halfspaces
    Adam R. Klivans, Alexander A. Sherstov · 2008 · Journal of Computer and System Sciences
  13. Learning Linear Temporal Properties
    Daniel Neider, Ivan Gavran · 2018 · Formal Methods in Computer-Aided Design
  14. Noise modelling and evaluating learning from examples
    Ray J. Hickey · 1996 · Artificial Intelligence
  15. Data-driven shape analysis and processing
    Kai Xu, Vladimir G. Kim, Qi-xing Huang A, Niloy J. Mitra, Evangelos Kalogerakis · 2016 · SIGGRAPH Asia Courses
  16. Differentially Private Release and Learning of Threshold Functions
    Mark Bun, Kobbi Nissim B, Uri Stemmer, Salil Vadhan · 2015 · Annual Symposium on Foundations of Computer Science
  17. A PAC-Style Model for Learning from Labeled and Unlabeled Data
    Maria-Florina Balcan, Avrim L. Blum · 2005 · Lecture notes in computer science
  18. A universal theorem on learning curves
    Шун-ичи Амари · 1993 · Neural Networks
  19. On the Boosting Ability of Top–Down Decision Tree Learning Algorithms
    Michael J. Kearns, Yishay Mansour · 1999 · Journal of Computer and System Sciences
  20. Learning submodular functions
    Maria-Florina Balcan, Nicholas J. A. Harvey · 2011 · ACM Symposium on Theory of Computing (STOC)
  21. Theory and Applications of Agnostic PAC-Learning with Small Decision Trees
    Peter L. Auer, Robert C. Holte, Wolfgang Maass · 1995 · Elsevier eBooks
  22. Queries revisited
    Dana Angluin · 2003 · Theoretical Computer Science
  23. Probabilistic inductive inference
    Leonard Pitt · 1989 · Journal of the ACM
  24. Machine Learning Modeling for Accelerated Battery Materials Design in the Small Data Regime
    Sendek, Austin D., Ransom, Brandi, Cubuk, Ekin D., Pellouchoud, Lenson A., Nanda, Jagjit, Reed, Evan J. · 2022 · Advanced Energy Materials
  25. An Introduction to Feature Selection
    Max Kühn, Kjell Johnson · 2013 · Springer eBooks
  26. Learning juntas
    Elchanan Mossel, Ryan O’Donnell, Rocco P. Servedio · 2003 · ACM Symposium on Theory of Computing (STOC)
  27. Recommendation systems: a probabilistic analysis
    Ravi Kumar, Prabhakar Raghavan, S. Rajagopalan, Andrew Tomkins · 2002 · Annual Symposium on Foundations of Computer Science
  28. Machine learning for intelligent support of conflict resolution
    Katia P. Sycara · 1993 · Decision Support Systems
  29. Multiclass Learning With Partially Corrupted Labels
    Ruxin Wang, Tongliang Liu, Dacheng Tao · 2017 · IEEE Transactions on Neural Networks and Learning Systems
  30. Quantum optimization with a novel Gibbs objective function and ansatz architecture search
    Li, Li, Fan, Minjie, Coram, Marc, Riley, Patrick, Leichenauer, Stefan · 2020 · Physical Review Research
  31. An information theoretic framework for data mining
    Tijl De Bie · 2011 · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)
  32. Tolerating Concept and Sampling Shift in Lazy Learning Using Prediction Error Context Switching
    Marcos Salganicoff · 1997 · Artificial Intelligence Review
  33. Boosting Regression Estimators
    Ran Avnimelech, Nathan Intrator · 1999 · Neural Computation
  34. Probability and plurality for aggregations of learning machines
    Leonard Pitt, Carl H. Smith · 1988 · Information and Computation
  35. An experimental study of the learnability of congestion control
    Anirudh Sivaraman, Keith Winstein, Pratiksha Thaker, Hari Balakrishnan · 2014 · ACM SIGCOMM Conference (SIGCOMM)
  36. Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao · 2017 · Journal of the ACM
  37. Learning Monotone Decision Trees in Polynomial Time
    Ryan O’Donnell, Rocco A. Servedio · 2007 · SIAM Journal on Computing
  38. Statistical Foundations of Actuarial Learning and its Applications
    Wüthrich, Mario V., Merz, Michael · 2023 · Springer Actuarial
  39. Hypernetworks: A Molecular Evolutionary Architecture for Cognitive Learning and Memory
    Byoung‐Tak Zhang · 2008 · IEEE Computational Intelligence Magazine
  40. Positive and negative evidence in language acquistion
    Jane Grimshaw, Steven A. Pinker · 1989 · Behavioral and Brain Sciences
  41. Big data analytics: six techniques
    Hong Shu · 2016 · Geo-spatial Information Science
  42. Positive and Unlabeled Examples Help Learning
    Francesco de Comité, François Denis, Rémi Gilleron, Fabien Letouzey · 1999 · Lecture notes in computer science
  43. Bounds on the Sample Complexity for Private Learning and Private Data Release
    Amos Beimel, Shiva Prasad Kasiviswanathan, Kobbi Nissim B · 2010 · Lecture notes in computer science
  44. Parameter Estimation for Statistical Parsing Models: Theory and Practice of Distribution-Free Methods
    Michael Collins · 2004 · Text, speech and language technology
  45. Local search for satisfiability (SAT) problem
    Jun Gu · 1993 · IEEE Transactions on Systems Man and Cybernetics
  46. LEARNING DNF UNDER THE UNIFORM DISTRIBUTION IN QUASI-POLYNOMIAL TIME
    Karsten Verbeurgt · 1990 · Elsevier eBooks
  47. Wireless Network Intelligence at the Edge
    Park, Jihong, Samarakoon, Sumudu, Bennis, Mehdi, Debbah, Merouane · 2019 · Proceedings of the IEEE
  48. The adaptive complexity of maximizing a submodular function
    Eric Balkanski, Yaron Singer · 2018 · ACM Symposium on Theory of Computing (STOC)
  49. Apple tasting
    David P. Helmbold, Nicholas Littlestone, Philip M. Long · 2000 · Information and Computation
  50. When Does Diversity Help Generalization in Classification Ensembles?
    Yijun Bian, Huanhuan Chen · 2021 · IEEE Transactions on Cybernetics
  51. Price graphs: Utilizing the structural information of financial time series for stock prediction
    Junran Wu, Ke Xu, Xueyuan Chen, Shangzhe Li, Jichang Zhao · 2021 · Information Sciences
  52. How many queries are needed to learn?
    Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn E. Wilkins · 1996 · Journal of the ACM
  53. Reactive search, a history-sensitive heuristic for MAX-SAT
    Roberto Battiti, Marco Protasi · 1997 · ACM Journal of Experimental Algorithmics
  54. Genetic programming and evolutionary generalization
    Ibrahim Kushchu · 2002 · IEEE Transactions on Evolutionary Computation
  55. Neural Networks with Quadratic VC Dimension
    Pascal Koiran, Eduardo D. Sontag · 1997 · Journal of Computer and System Sciences
  56. Learning Nested Differences of Intersection-Closed Concept Classes
    David P. Helmbold, Robert H. Sloan, Manfred K. Warmuth · 1990 · Machine Learning
  57. The simplicity principle in perception and cognition
    Jacob Feldman · 2016 · Wiley Interdisciplinary Reviews Cognitive Science
  58. Is there a role for statistics in artificial intelligence?
    Sarah Friedrich, Gerd Antes, Sigrid Behr, Harald Binder, Werner Brannath, Florian Dumpert, Katja Ickstadt, Hans Armin Kestler, Johannes Lederer, Heinz Leitgöb et al. · 2021 · Advances in Data Analysis and Classification
  59. Defining and simulating open-ended novelty: requirements, guidelines, and challenges
    Wolfgang Banzhaf, Bert O. Baumgaertner, Guillaume Beslon, René Doursat, James A. Foster, Barry McMullin, Vinícius Veloso de Melo, Thomas Miconi, Lee C. Spector, Susan Stepney et al. · 2016 · Theory in Biosciences
  60. Approximate dependency inference from relations
    Jyrki Kivinen, Heikki Mannila · 1992 · Lecture notes in computer science
  61. Neural networks, nativism, and the plausibility of constructivism
    Steven R. Quartz · 1993 · Cognition
  62. Verification as Learning Geometric Concepts
    Rahul Sharma, Saurabh Gupta, Bharath Hariharan, Alex Aiken, Aditya V. Nori · 2013 · Lecture notes in computer science
  63. Review and Analysis of Zero, One and Few Shot Learning Approaches
    Suvarna Kadam, Vinay G. Vaidya · 2019 · Advances in intelligent systems and computing
  64. Learning probabilistic prediction functions
    Alfredo De Santis, George Markowsky, Mark N. Wegman · 1988 · Annual Symposium on Foundations of Computer Science
  65. An algorithmic theory of learning: robust concepts and random projection
    Rosa I. Arriaga, Santosh Vempala · 2003 · Annual Symposium on Foundations of Computer Science
  66. A survey on the complexity of learning quantum states
    Anurag Anshu, Srinivasan Arunachalam · 2023 · Nature Reviews Physics
  67. Artificial Intelligence and Generalized Qualitative‐Response Models: An Empirical Test on Two Audit Decision‐Making Domains
    James V. Hansen, James B. McDonald, James D. Stice · 1992 · Decision Sciences
  68. Safe Exploration for Active Learning with Gaussian Processes
    Jens Schreiter, Duy Nguyen-Tuong, Mona Eberts, Bastian Bischoff, Heiner Markert, Marc Toussaint · 2015 · Lecture notes in computer science
  69. Understanding quantum machine learning also requires rethinking generalization
    Elies Gil-Fuster, Jens Eisert, Carlos Bravo-Prieto · 2024 · Nature Communications
  70. Learning DNF in time
    Adam R. Klivans, Rocco A. Servedio · 2001 · ACM Symposium on Theory of Computing (STOC)
  71. Learning Boolean Functions in an Infinite Attribute Space
    Avrim L. Blum · 1992 · Machine Learning
  72. An empirical generative framework for computational modeling of language acquisition
    Heidi Waterfall, Ben Sandbank, Luca Onnis, Shimon Edelman · 2010 · Journal of Child Language
  73. On the Quantum versus Classical Learnability of Discrete Distributions
    Ryan Sweke, Jean‐Pierre Seifert, Dominik Hangleiter, Jens Eisert · 2021 · Quantum
  74. Quantum Machine Learning: A Review and Current Status
    Nimish Mishra, Manik Kapil, H R Rakesh, Amit Kumar Anand, Nilima Mishra, Aakash Warke, Soumya Sarkar, Sanchayan Dutta, Sabhyata Gupta, Aditya Prasad Dash et al. · 2020 · Advances in intelligent systems and computing
  75. Complexity Results on Learning by Neural Nets
    Jyh-Han Lin, Jeffrey Scott Vitter · 1991 · Machine Learning
  76. Constraint acquisition
    Christian Bessière, Frédéric Koriche, Nadjib Lazaar, Barry O’Sullivan · 2015 · Artificial Intelligence
  77. Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
    Nader H. Bshouty, Jeffrey C. Jackson · 1998 · SIAM Journal on Computing
  78. Application of Artificial Neural Networks to Predict Speeds on Two-Lane Rural Highways
    John McFadden, Wen-Tai Yang, S. Durrans · 2001 · Transportation Research Record Journal of the Transportation Research Board
  79. Universal Algorithmic Intelligence: A Mathematical Top→Down Approach
    Marcus Hütter · 2007 · Cognitive technologies
  80. Ensemble learning with label proportions for bankruptcy prediction
    Zhensong Chen, Wei Chen, Yong Shi · 2019 · Expert Systems with Applications
  81. Neural Network Modeling Attacks on Arbiter-PUF-Based Designs
    Nils Wisiol, Bipana Thapaliya, Khalid T. Mursi, Jean‐Pierre Seifert, Yu Zhuang · 2022 · IEEE Transactions on Information Forensics and Security
  82. Short-term wind power forecasting using hybrid method based on enhanced boosting algorithm
    Yu Jiang, Xingying Chen, Kun Yu, Yingchen Liao · 2015 · Journal of Modern Power Systems and Clean Energy
  83. Learning to reason
    Roni Khardon, Dan Roth · 1997 · Journal of the ACM
  84. The perceptron algorithm versus winnow: linear versus logarithmic mistake bounds when few input variables are relevant
    Jyrki Kivinen, Manfred K. Warmuth, Peter L. Auer · 1997 · Artificial Intelligence
  85. Lazy Incremental Learning of Control Knowledge for Efficiently Obtaining Quality Plans
    Daniel Borrajo, Manuela Veloso · 1997 · Artificial Intelligence Review
  86. Property testing and its connection to learning and approximation
    Oded Goldreich, Shafi Goldwasser, Dana Ron · 2002 · Annual Symposium on Foundations of Computer Science
  87. Preface to the special issue on connectionist symbol processing
    Geoffrey E. Hinton · 1990 · Artificial Intelligence
  88. Data Analytics for Non-Life Insurance Pricing
    Mario V. Wüthrich, Christoph Buser · 2017 · SSRN Electronic Journal
  89. Statistical algorithms and a lower bound for detecting planted cliques
    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao · 2013 · ACM Symposium on Theory of Computing (STOC)
  90. Agnostically Learning Halfspaces
    Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio · 2005 · Annual Symposium on Foundations of Computer Science
  91. On the role of locality in learning stress patterns
    Jeffrey Nicholas Heinz · 2009 · Phonology
  92. Algorithmic Aspects of Machine Learning
    Ankur Moitra · 2018 · Cambridge University Press eBooks
  93. Using the Tsetlin Machine to Learn Human-Interpretable Rules for High-Accuracy Text Categorization With Medical Applications
    Geir Thore Berge, Ole‐Christoffer Granmo, Tor Oddbjørn Tveit, Morten Goodwin, Lei Jiao, Bernt Viggo Matheussen · 2019 · IEEE Access
  94. Probabilistic finite-state machines - part II
    Enrique Vidal, Franck Thollard, Colin de la Higuera, Francisco Casacuberta, Rafael C. Carrasco · 2005 · IEEE Transactions on Pattern Analysis and Machine Intelligence
  95. Lower Bound Methods and Separation Results for On-Line Learning Models
    Wolfgang Maass, Gy�rgy Tur�n · 1992 · Machine Learning
  96. Prediction of daily maximum ozone threshold exceedances by preprocessing and ensemble artificial intelligence techniques: Case study of Hong Kong
    Bing Gong, Joaquín B. Ordieres-Meré · 2016 · Environmental Modelling & Software
  97. Applying learning algorithms to preference elicitation
    Sebastien M. Lahaie, David C. Parkes · 2004 · ACM Conference on Electronic Commerce (EC)
  98. Probable correctness theory
    Richard G. Hamlet · 1987 · Information Processing Letters
  99. Quantum learning robust against noise
    Cross, Andrew W., Smith, Graeme, Smolin, John A. · 2015 · Physical Review A
  100. Conceptual challenges for interpretable machine learning
    David Watson · 2022 · Synthese