Sample complexity: Difference between revisions

Revision as of 17:31, 1 March 2020

Revision as of 18:50, 1 March 2020

Line 61:

=== An example of a PAC-learnable hypothesis space ===

<math>X = \R^d, Y = \{-1, 1\}</math>, and let <math>\mathcal H</math> be the space of affine functions on <math>X</math>, that is, functions of the form <math>x\mapsto \langle w,x\rangle+b</math> for some <math>w\in\R^d,b\in\R</math>. This is the linear classification with offset learning problem. Now, note that four coplanar points in a square cannot be shattered by any affine function, since no affine function can be positive on two diagonally opposite vertices and negative on the remaining two. Thus, the VC dimension of <math>\mathcal H</math> is <math>d + 1</math>, inso particularit is finite. It follows by the above characterization of PAC-learnable classes that <math>\mathcal H</math> is PAC-learnable, and by extension, learnable.

=== Sample-complexity bounds ===