5,337
edits
Line 765: | Line 765: | ||
Proof: | Proof: | ||
Consider the region with the correct classification: <math>R=\{x \mid c(x)=c</math>. Here <math>u(R) = f_c \leq 1/2</math>. | Consider the region with the correct classification: <math>R=\{x \mid c(x)=c</math>. | ||
Consider the compliment <math>R^c</math>. <math>u_1(R^c) \geq \frac{1}{2}</math>. | Here <math>u(R) = f_c \leq 1/2</math>. | ||
Consider the compliment <math>R^c</math>. | |||
The area of the complement is <math>u_1(R^c) \geq \frac{1}{2}</math>. | |||
The area of the epsilon expansion is <math>u_1(R^c(\epsilon)) \geq 1 - (\pi/8)^{1/2} \exp(-\frac{d-1}{2}\epsilon^2}</math>. Thus the ''safe zone'' is very small in high dimension. | |||
;Lemma | ;Lemma |