Don't understand a part of derivation of Curse of dimensionality equation
Hello!
On the last lecture about kNN classifier there was a derivation of inequality that illustrates curse of dimensionality and I don't understand one step when deriving it in General case. There is first written the following:
I first thought it was a mistake and that inequality could be applied so \(P(y \ne y') \le 2 \eta(x) [1 - \eta(x)] + \eta(x) - \eta(x')\) which would make sense for the next step, but \([\eta(x) - \eta(x')][2\eta(x) - 1] \le \eta(x) - \eta(x') \) doesn't seem to apply as \(2\eta(x) - 1\) could be negative.
Thank you for your message. You are right, I did a mistake in my computation (but that was to see if someone was following ;) ).
The result is still correct and well derived in the lecture note. The argument is the following:
First, you can always upper bound a real by its absolute value:
Don't understand a part of derivation of Curse of dimensionality equation
Hello!
On the last lecture about kNN classifier there was a derivation of inequality that illustrates curse of dimensionality and I don't understand one step when deriving it in General case. There is first written the following:
$$P(y \ne y') = \eta(x)[1-\eta(x')] + \underline{\eta(x)[\eta(x) - \eta(x')]} + \eta(x)[1 - \eta(x)] + \underline{[\eta(x')-\eta(x)][1 - \eta(x)]}$$
And afterwards we got:
$$P(y \ne y') = 2 \eta(x) [1 - \eta(x)] + \eta(x) - \eta(x')$$
But clearly \(\eta(x)[\eta(x) - \eta(x')] + [\eta(x')-\eta(x)][1 - \eta(x)] = [\eta(x) - \eta(x')][2\eta(x) - 1] \ne \eta(x) - \eta(x')\).
I first thought it was a mistake and that inequality could be applied so \(P(y \ne y') \le 2 \eta(x) [1 - \eta(x)] + \eta(x) - \eta(x')\) which would make sense for the next step, but \([\eta(x) - \eta(x')][2\eta(x) - 1] \le \eta(x) - \eta(x') \) doesn't seem to apply as \(2\eta(x) - 1\) could be negative.
2
Hi,
Thank you for your message. You are right, I did a mistake in my computation (but that was to see if someone was following ;) ).
The result is still correct and well derived in the lecture note. The argument is the following:
First, you can always upper bound a real by its absolute value:
$$[2 \eta(x)-1] [\eta(x)-\eta(x')] \leq | [2 \eta(x)-1] [\eta(x)-\eta(x')] | = | 2 \eta(x)-1| |\eta(x)-\eta(x') | $$
Then by definition of \( \eta(x) = \mathbb P ( y=1|x) \), we have that \( \eta(x) \in[0,1] \) and therefore \( | 2 \eta(x)-1| \leq 1\). Thus we obtain
$$[2 \eta(x)-1] [\eta(x)-\eta(x')] \leq |\eta(x)-\eta(x') | $$
My apologies for this mistake. I was in too much of a hurry on the board.
Best,
Nicolas
2
I understand now. Thank you for your answer!
Add comment