Låt oss nu titta på en slumpsekvens av mönster \(\mathbf{x}_{1},\mathbf{x}_{2},\ldots\) och targets \(t_{1},t_{2},\ldots\). Vad är fördelningen av det största heltalet sådant att problemet \(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_n\) är separerbart i embedding-dimension m, men \(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_n,\mathbf{x}_{n+1}\) inte är det?
\(P(n,m)\) är sannolikheten att n mönster är linj. separerbara i embedding-dimension m. Vi kan skriva \(P(n+1,m)=q(n+1|n)P(n,m)\) där \(q(n+1|n)\) är sannolikheten att n+1 mönster är linj.separerbara om de n mönstren var det.
Då är sannolikheten att n+1 mönster inte är separerbara (men n var det): \((1-q)P(n,m)=P(n,m)-P(n+1,m)\). HL kan tolkas som en fördelning \(p_{n}\) av slumpvariabeln n, det maximala antalet separerbara mönster i embedding-dimension m:
\(p_{n}=P(n,m)-P(n+1,m)=\left(\frac{1}{2}\right)^{2}\binom{n-1}{m-1}\quad\textrm{for}\quad n=0,1,2,\ldots\)
Det följer att det förväntade antalet maximala antal separerbara mönster är
\(\left\langle n\right\rangle =\sum_{n=0}^{\infty}np_{n}=2m\)
Så väntevärdet är dubbla embedding-dimensionen, vilket kvantifierar påståendet att det är lättare att separera mönster i högre embedding-dimensioner.
"Comparing with the discussion of linear separability in Chapter 5 we see that Cover’s theorem determines the separation capacity of a single-layer perceptron"
