# rp

Published articles for rp.

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

## 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.