Sample complexity: Difference between revisions

Revision as of 12:32, 1 January 2017

Revision as of 11:55, 27 April 2017

Line 62:

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

Let ''X'' = '''R'''^''d'', ''Y'' = {-1, 1}, and let <math>\mathcal H</math> be the space of affine functions on ''X'', 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 3<math>d + 1</math>, in particular 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 ===