What is the expected cost of using LDA?

Question

Suppose that you observe $(X_1,Y_1),...,(X_{100}Y_{100})$, which you assume to be i.i.d. copies of a random pair $(X,Y)$ taking values in $\mathbb{R}^2 \times \{1,2\}$.

I have that the cost of misclassification are equal, $c_1=c_2=1$.

The distributions $X|Y=1$ and $X|Y=2$ are each rotationally symmetric.

I would like to perform LDA to classify the data points.

I have that $a=\hat\Sigma^{-1}_p(\hat{\mu}_1-\hat{\mu}_2)=(0.132-0.0732)$ and $\frac{1}{2}a^T(\hat{\mu}_1+\hat{\mu}_2)\approx 0$

And now I would like to calculate the approximate expected cost of using LDA.

So, in the textbook i'm using, the expected cost of misclassification is defined as:

Suppose we use the classification rule $g:\mathbb{R}^p\rightarrow \{1,2\}$, that assigns to group $1$ when $x \in R_1$ adnto group $2$ when $x\in R_2$. The expected cost of misclassification associated to the rule $g$ is $$\mathbb{E}[\text{cost}(Y,g(X))]=c_2\mathbb{P}(x\in R_1 | Y=2)\pi_2+c_1\mathbb{P}(x\in R_2 | Y=1)\pi_1$$ Where $\pi_1=\mathbb{P}(Y=1|x)$ and $\pi_2=\mathbb{P}(Y=2|x)$

And so my attempt is:

$$\mathbb{E}[\text{cost}(Y,g(X))]=c_2\mathbb{P}(x\in R_1 | Y=2)\pi_2+c_1\mathbb{P}(x\in R_2 | Y=1)\pi_1=\mathbb{P}(0.132x_1-0.0732x_2\gt 0|Y=2)\pi_2+\mathbb{P}(0.0132x_1-0.0722x_2 \lt 0|Y=1)\pi_1$$

And i'm stuck here. I'm not sure how to continue from here. In particular, I don't know what $\mathbb{P}(0.0132x_1-0.0722x_2 \lt 0|Y=1)$ and $\mathbb{P}(0.132x_1-0.0732x_2\gt 0|Y=2)$ are equal to, also $\pi_1,\pi_2$.

Answer 1

Estimating this quantity is simple: $\pi_i=Pr(y=c_i)$ is just the prior that a point belongs to a certain class. For your finite dataset, you can estimate it via

$$\pi_i \approx \frac{1}{N}\sum_{j=1}^N [y_j=c_i] = n_i/N$$

Secondly, $Pr(a^Tx>0\mid y=x_i)$ is the probability that a datapoint gets correctly classified, which you can estimate as

$$Pr(a^Tx>0\mid y=c_i)\approx\frac{1}{n_i}\sum_{j=1}^N [y_j = c_i]\cdot [a^Tx_j>0]$$

However, to get a good estimate, you should compute this on a hold-out test set or by leave-one-out cross validation.

---

Now if you want to analytically compute this quantity, I am not sure if we have enough information about the distributions $p(x\mid y=c_i)$. However, we can deduce quite a few things from the two clues

1. The distributions X|Y=1 and X|Y=2 are each rotationally symmetric. (around their mean?)
2. $\frac{1}{2}a^T(\hat\mu_1+\hat\mu_2)$

The first one implies that $p(x\mid y=c_i)=g_i(\|x-\mu_i\|_2)$ for some $g_i\colon\mathbb R_{\ge 0} \to\mathbb R_{\ge 0}$. Moreover, due to the rotational symmetries I think we must have $E[(x-\mu_i)(x-\mu_i)^T]=\Sigma_i = \alpha_i I$ for some $\alpha_i>0$, and consequently LDA will estimate the covariance as $\Sigma=\pi_1 \Sigma_1 + \pi_2\Sigma_2 = (\alpha_1\pi_1 + \alpha_2\pi_2)I$. Thus the second clue suggests that

$$\begin{aligned} &&\frac{1}{2}a^T(\hat\mu_1 +\hat\mu_2) &\approx 0 \\&\iff&(\hat\mu_1 -\hat\mu_2)^T\hat\Sigma^{-1}(\hat\mu_1 +\hat\mu_2) &\approx 0 \\&\;\;\leftrightsquigarrow&(\mu_1-\mu_2)^T\Sigma^{-1}(\mu_1+\mu_2) &=0 \\&\iff& \mu_1^T\Sigma^{-1}\mu_1 &= \mu_2^T\Sigma^{-1}\mu_2 \\&\iff& \frac{\mu_1^T\mu_1}{\alpha_1\pi_1 + \alpha_2\pi_2} &= \frac{\mu_2^T\mu_2}{\alpha_1\pi_1 + \alpha_2\pi_2} \\&\iff& \|\mu_1\|_2 &= \|\mu_2\|_2 \end{aligned}$$

In particular, after appropriate centering we have $\mu_1 = -\mu_2$. Now, if both $x\mid y=c_1$ and $x\mid y=c_2$, are normally distributed, we can analytically integrate and are done more of less. However, if they are not, I am not sure if there is a way to proceed.

Answer 2

Your description makes it seem like we assume $E[x\mid y=c_1] = E[x\mid y=c_2]=0$ (otherwise, let me know). Then from the statement

The distributions X|Y=1 and X|Y=2 are each rotationally symmetric.

We can conclude that any decision boundary that's just a straight line through the origin will have an accuracy of precisely 50%. We can prove this intuitive observation as follows: Since the distributions are rotationally symmetric, there exists $g_i\colon\mathbb R_{\ge 0}\to\mathbb R_{\ge 0}$ such that $p(x\mid y=c_i) = g_i(\|x\|_2)$.

In particular, note that $\|Rx\|_2^2 =x^TR^TRx=x^T x = \|x\|_2^2$ for any rotation matrix $R$.

Now, we want to figure out

$$Pr(a^T x>0\mid y=c_i) = \int\limits_{\{x:a^Tx>0\}} p(x\mid y=c_i) dx = \int\limits_{\{x:a^Tx>0\}} g_i(\|x\|_2) dx$$

Now, we can rotate the coordinate system by 180 degree such that $a$ is mapped onto $-a$, by substituting $x= Rz$, were $R=\big(\begin{smallmatrix}\cos(\theta)&-\sin(\theta)\\ +\sin(\theta)&\cos(\theta)\end{smallmatrix}\big)$ for $\theta=\pi$.

$$\int\limits_{\{x:a^Tx>0\}} g_i(\|x\|_2) dx =\int\limits_{\{z:a^TRz>0\}} g_i(\underbrace{\|Rz\|_2}_{=\|z\|_2}) \underbrace{|\det(R)|}_{=1}dz =\int\limits_{\{z:a^Tz<0\}} g_i(\|z\|_2)dz $$

Which is the same as $Pr(a^T x<0\mid y=c_i)$, and thus

$$ 1 = Pr(a^T x<0\mid y=c_i) + Pr(a^T x>0\mid y=c_i) = 2Pr(a^T x>0\mid y=c_i)$$

so $Pr(a^T x>0\mid y=c_i)=\frac{1}{2}$ for any $a\neq 0$