# computational learning theory

Published articles for computational learning theory.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Occam's Razor and PAC-learning

DevFeed: [Occam's Razor and PAC-learning](<https://devfeed.tech/articles/occam-s-razor-and-pac-learning-40366.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/09/19/occams-razor-and-pac-learning/>)

Published: 2014-09-19T10:00:47Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Occam's razor machine learning](<https://devfeed.tech/topics/occam-s-razor-machine-learning.md>), [Learning](<https://devfeed.tech/topics/learning.md>), [data](<https://devfeed.tech/topics/data.md>)

Tags: [chernoff](<https://devfeed.tech/tags/chernoff.md>), [chernoff-bound](<https://devfeed.tech/tags/chernoff-bound.md>), [computational-learning-theory](<https://devfeed.tech/tags/computational-learning-theory.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [occam-s-razor](<https://devfeed.tech/tags/occam-s-razor.md>), [pac-learning](<https://devfeed.tech/tags/pac-learning.md>), [vc-dimension](<https://devfeed.tech/tags/vc-dimension.md>)

### AI overview

This tutorial develops a simple PAC-learning theorem for a finite hypothesis class. It explains that if a hypothesis consistent with observed data can always be found, the class can be learned efficiently, and it uses the Chernoff-Hoeffding bound to quantify the sample requirement for achieving low error.

### Source excerpt

So far our discussion of learning theory has been seeing the definition of PAC-learning, tinkering with it, and seeing simple examples of learnable concept classes. We've said that our real interest is in proving big theorems about what big classes of problems can and can't be learned. One major tool for doing this with PAC is the concept of VC-dimension, but to set the stage we're going to prove a simpler theorem that gives a nice picture of PAC-learning when your hypothesis class is small.

## A problem that is not (properly) PAC-learnable

DevFeed: [A problem that is not (properly) PAC-learnable](<https://devfeed.tech/articles/a-problem-that-is-not-properly-pac-learnable-40356.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/04/21/an-un-pac-learnable-problem/>)

Published: 2014-04-21T10:00:16Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Learning](<https://devfeed.tech/topics/learning.md>), [math](<https://devfeed.tech/topics/math.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [boolean-satisfiability](<https://devfeed.tech/tags/boolean-satisfiability.md>), [classes](<https://devfeed.tech/tags/classes.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computational-learning-theory](<https://devfeed.tech/tags/computational-learning-theory.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [logical](<https://devfeed.tech/tags/logical.md>), [math](<https://devfeed.tech/tags/math.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [misconceptions](<https://devfeed.tech/tags/misconceptions.md>), [np](<https://devfeed.tech/tags/np.md>), [np-completeness](<https://devfeed.tech/tags/np-completeness.md>), [pac-learning](<https://devfeed.tech/tags/pac-learning.md>), [reduction](<https://devfeed.tech/tags/reduction.md>), [rp](<https://devfeed.tech/tags/rp.md>)

### AI overview

This technical learning-theory article presents a standard example of a problem that is not learnable under the previously introduced PAC model, then explains how a more expressive hypothesis class changes that result. Its addendum clarifies that 3-term DNF formulas are not shown to be unlearnable under the standard PAC definition, only under the earlier restricted definition.

### Source excerpt

In a previous post we introduced a learning model called Probably Approximately Correct (PAC). We saw an example of a concept class that was easy to learn: intervals on the real line (and more generally, if you did the exercise, axis-aligned rectangles in a fixed dimension). One of the primary goals of studying models of learning is to figure out what is learnable and what is not learnable in the various models.