PAC Learning, VC Dimension, and the Arithmetic Hierarchy

2014-06-04 · Wesley Calvert

We compute that the index set of PAC-learnable concept classes is $m$-complete $\Sigma^0_3$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable $\Pi^0_1$ classes, in a sense made precise here. This family of concept classes is sufficient to cover all standard examples, and also has the property that PAC learnability is equivalent to finite VC dimension.

📄 PDF Abstract BibTeX arXiv:1406.1111

Code (0)

등록된 구현이 없습니다.

Tasks

AllPAC learning

CLeAR: Continual Learning on Algorithmic Reasoning for Human-like Intelligence

2023-09-21 · NeurIPS 2023 11

Continual learning (CL) aims to incrementally learn multiple tasks that are presented sequentially. The significance of CL lies not only in the practical importance but also in studying the learning mechanisms of humans …

On the Computability of Solomonoff Induction and Knowledge-Seeking

2015-07-15 · Jan Leike, Marcus Hutter

Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the arithmetical hierarchy. We also …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

BOLD: Boolean Logic Deep Learning

2024-05-25 · Van Minh Nguyen, Cristian Ocampo, Aymen Askri, Louis Leconte 외

Deep learning is computationally intensive, with significant efforts focused on reducing arithmetic complexity, particularly regarding energy consumption dominated by data movement. While existing literature emphasizes i…

Benchmarking Deep Learning Image Super-Resolution Natural Language Understanding+2

Norm-Hierarchy Transitions in Representation Learning: When and Why Neural Networks Abandon Shortcuts

2026-03-07 · Truong Xuan Khanh, Truong Quynh Hoa arxiv

Neural networks often rely on spurious shortcuts for many epochs before discovering structured representations. However, the mechanism governing when this transition occurs and whether its timing can be predicted remains…

Representation Learning

On the Computability of AIXI

2015-10-19 · Jan Leike, Marcus Hutter

How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both a…

BIG-bench Machine Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)