¿Existe una $R^2 \rightarrow R^2$ ¿Transformación lineal para que el problema XOR sea separable?

Question

Según el teorema de Cover (1965), es posible hacer que los patrones sean separables si el espacio de características original se transforma en un espacio de mayor dimensión.

Piensa en el problema XOR.

No es posible separar las dos clases con un hiperplano. Un truco es utilizar las redes neuronales, que transforman el espacio de características linealmente a un espacio de mayor dimensión. Otro es el truco del kernel con transformación no lineal.

Pero, ¿podemos hacer que las clases sean separables sólo con una transformación lineal de baja dimensión, es decir $R^2 \rightarrow R^2$ ¿Transformación lineal? Creo que no encuentro ninguna. ¿Hay alguna manera de demostrar que tal transformación no existe?

Answer 1

Dos conjuntos de vectores $x_i$ y $y_i$ son linealmente separables si existe algún vector $w$ y una constante $k$ tal que $w\cdot x_i \ge k$ y $w\cdot y_i < k$ . Estás preguntando si hay alguna transformación lineal (o afín, no importa) que pueda hacer que dos conjuntos que no son linealmente separables sean linealmente separables.

Supongamos que $M$ es una transformación de este tipo. Tenga en cuenta que $w\cdot (M x_i)=(M^T w)\cdot x_i$ , donde $M^T$ es el adjunto/transpuesto de $M$ . Entonces, es evidente que si $M$ le permite separar $Mx_i$ y $My_i$ con el vector $w$ los conjuntos originales eran separables mediante $M^T w$ . Ninguna transformación lineal de ese tipo funcionará. Alternativamente, los hiperplanos seguirán siendo hiperplanos bajo transformaciones lineales (de rango completo).