Hace una óptima clasificador lineal para realizar mejor oportunidad iff de la clase de las distribuciones tienen la misma media?

Question

Suponiendo que hay algunos bonitos $P(x, y)$$\mathbb R^n \times \{0, 1\}$, podemos aducir que: La espera precisión de la óptima clasificador lineal entrenados en una amplia muestra de $P(x, y)$ no superan los 0,5 si y sólo si $$\mathbb E[x|y=0] = \mathbb E[x|y=1]$$?

Quiero decir, algo como:

$$ P \Big[\mathcal R_P(h^*) \geq 0.5 + \delta \Big] \leq \text{veryfastdecrease}(\delta) \iff \mathbb E[x|y=0] = \mathbb E[x|y=1] $$

Donde

• $\mathcal R_P (h) = \mathbb E_{x, y\sim P}[h(x) \neq y]$
• $h^* = \arg\min_{h\in H}\mathcal R_P(h)$
• $H = \{h : x \mapsto \text{sign}(Ax+b)\}$

Gracias.

Answer 1

La respuesta es no. Te voy a mostrar un contraejemplo sencillo donde $p(x \mid y=0)$ $p(x \mid y=1)$ tienen la misma media, pero es posible construir un clasificador lineal con la clasificación errónea de la tasa mejor que el azar. (Nota: la probabilidad de que el nivel de rendimiento es sólo el 0,5 cuando la marginal de las probabilidades de cada clase son iguales; si una clase eran más probables que las otras, siempre podemos salida de esa clase como nuestra predicción y se haga la mayoría del tiempo).

Vamos a considerar un caso unidimensional, con $X \in \mathbb{R}$. Las entradas de la primera clase tiene una distribución uniforme en el intervalo de $[0, a]$:

$$P(x \a mediados de y=0) = \left \{ \begin{array}{cl} \frac{1}{a} & \text{if } 0 \le x \le a \\ 0 & \text{otherwise} \end{array} \right .$$

Entradas a partir de la segunda clase tiene una distribución exponencial, con una media igual a la de la distribución uniforme (es decir,$\frac{a}{2}$):

$$P(x \a mediados de y=1) = \left \{ \begin{array}{cl} \frac{2}{a} e^{-\frac{2}{a} x} & \text{if } x \ge 0 \\ 0 & \text{otherwise} \end{array} \right .$$

Aquí hay un gráfico de la distribución de entrada para cada clase de al $a=3$:

Construir un clasificador $f_t$ con el umbral de $t \ge 0$, de tal manera que la predicción de la clase es 0 si la entrada es menor o igual que el umbral, y 1 si la entrada supera el umbral. Este clasificador es trivialmente lineal porque estamos usando la entrada a sí misma como la variable de decisión.

$$f_t(x) = \left \{ \begin{array}{cl} 0 & \text{if } x \le t \\ 1 & \text{otherwise} \\ \end{array} \right .$$

Podemos medir el clasificador de rendimiento para un determinado umbral de uso de la tasa de error en la clasificación (es decir, el valor esperado del 0-1 de la pérdida).

$$L(t) = \int_{-\infty}^t P(x \a mediados de y=1) p(y=1) dx + \int_t^\infty P(x \a mediados de y=0) p(y=0) dx$$

Decir que las clases son equiprobables, por lo $p(y=0) = p(y=1) = 0.5$. Así, el azar-el nivel de rendimiento es de 0,5. Conectar todo, tenemos:

$$\begin{array}{ccl} L(t) & = & \int_{0}^t \frac{1}{a} e^{-\frac{2}{a} x} dx + [t \le a] \int_t^a \frac{1}{2a} dx \\ & = & \frac{1}{2} - \frac{1}{2} e^{-\frac{2t}{a}} + [t \le a] \left ( \frac{1}{2} - \frac{t}{2a} \right ) \end{array}$$

donde $[\cdot]$ es la Iverson soporte, que devuelve 1 cuando su argumento es true, de lo contrario 0.

La clasificación errónea de la tasa puede ser menor que 0,5 (nivel de oportunidad en este caso). Aquí está la clasificación errónea de la tasa como una función de un umbral, para el mismo ejemplo de las distribuciones de entrada como en el anterior ($a=3$):