¿Diferencia entre un problema lineal y un problema no lineal? Esencia de Dot-Product y Kernel truco

Question

El truco del kernel mapea un problema no lineal en un problema lineal.

Mis preguntas son:
1. ¿Cuál es la principal diferencia entre un problema lineal y un problema no lineal? ¿Cuál es la intuición detrás de la diferencia de estas dos clases de problemas? ¿Y cómo funciona el truco del kernel para usar los clasificadores lineales en un problema no lineal?
2. ¿Por qué el producto escalar es tan importante en los dos casos?

Gracias.

Answer 1

Muchos clasificadores, entre ellos el Support Vector Machine (SVM) lineal, solo pueden resolver problemas que son separables linealmente, es decir, donde los puntos pertenecientes a la clase 1 pueden separarse de los puntos pertenecientes a la clase 2 por un hiperplano.

En muchos casos, un problema que no es separable linealmente se puede resolver aplicando una transformación phi() a los puntos de datos; se dice que esta transformación transforma los puntos a espacio de característica. La esperanza es que, en el espacio de características, los puntos serán linealmente separables. (Nota: este no es el truco del núcleo aún ... estad atentos.)

Se puede demostrar que, cuanto mayor es la dimensión del espacio de características, mayor es la cantidad de problemas que son separables linealmente en ese espacio. Por lo tanto, lo ideal sería que el espacio de funciones fuera tan alto como sea posible.

Lamentablemente, a medida que aumenta la dimensión del espacio de características, también lo hace la cantidad de cálculos requeridos. Aquí es donde entra el truco del kernel. Muchos algoritmos de aprendizaje automático (entre ellos el SVM) se pueden formular de tal manera que la única operación que realizan en los puntos de datos es un producto escalar entre dos puntos de datos. (. Voy a denotar un producto escalar entre x1 y x2 por <x1, x2>)

Si transformamos nuestros puntos para ofrecer espacio, el producto escalar ahora se ve así:

<phi(x1), phi(x2)>

La idea clave es que existe una clase de funciones llamadas núcleos que se pueden utilizar para optimizar el cálculo de este producto escalar. El núcleo es una función K(x1, x2) que tiene la propiedad de que

K(x1, x2) = <phi(x1), phi(x2)>

para alguna función phi(). En otras palabras: podemos evaluar el producto escalar en el espacio de datos de baja dimensión (donde x1 y x2 "vivo") sin tener que transformarse en el espacio de características de alta dimensión (donde phi (x1) y phi (x2) "viven ") - pero aún así obtenemos los beneficios de transformarnos en el espacio de funciones de alta dimensión. Esto se llama kernel truco.

Muchos núcleos populares, tales como la Gaussian kernel, en realidad corresponden a una transformación phi() que se transforma en un infinte dimensiones espacio función. El truco del kernel nos permite calcular productos escalares en este espacio sin tener que representar puntos en este espacio explícitamente (lo cual, obviamente, es imposible en computadoras con cantidades finitas de memoria).

Answer 2

1. Las ecuaciones lineales son homogéneas y se aplica la superposición. Puede crear soluciones usando combinaciones de otras soluciones conocidas; esta es una razón por la cual las transformadas de Fourier funcionan tan bien. Las ecuaciones no lineales no son homogéneas, y la superposición no se aplica. Las ecuaciones no lineales generalmente tienen que resolverse numéricamente utilizando técnicas iterativas e incrementales.
2. No estoy seguro de cómo expresar la importancia del producto escalar, pero toma dos vectores y devuelve un escalar. Ciertamente, una solución a una ecuación escalar es menos trabajo que resolver un vector o una ecuación de tensor de orden superior, simplemente porque hay menos componentes con los que lidiar.

Mi intuición en este asunto se basa más en la física, así que estoy teniendo dificultades para traducir a AI.

Answer 3

La principal diferencia (a efectos prácticos) es: un problema lineal tiene una solución (y luego se encuentra fácilmente), o se obtiene una respuesta definitiva de que no hay solución. Usted sabe tanto, incluso antes de saber el problema. Mientras sea lineal, obtendrás una respuesta; con rapidez.

La intuición beheind esto es el hecho de que si usted tiene dos líneas rectas en el espacio, es bastante fácil de ver si se cruzan o no, y si lo hacen, es fácil saber dónde.

Si el problema no es lineal, bueno, puede ser cualquier cosa, y usted sabe casi nada.

El producto punto de dos vectores solo significa lo siguiente: La suma de los productos de los elementos correspondientes. Así que si su problema es

c1 * x1 + c2 * x2 + c3 * x3 = 0 

(donde normalmente se conocen los coeficientes c, y que está buscando para las variables x), el lado izquierdo es el producto escalar de los vectores (c1,c2,c3) y (x1,x2,x3).

La ecuación anterior es (más o menos) la definición misma de un problema lineal, por lo que existe la conexión entre el producto escalar y los problemas lineales.

Answer 4

Cuando la gente dice un problema lineal con respecto a un problema de clasificación, generalmente significan problemas linealmente separables. Linealmente separable significa que hay alguna función que puede separar las dos clases que es una combinación lineal de la variable de entrada. Por ejemplo, si tiene dos variables de entrada, x1 y x2, existen algunos números theta1 y theta2 de modo que la función theta1.x1 + theta2.x2 será suficiente para predecir la salida. En dos dimensiones esto corresponde a una línea recta, en 3D se convierte en un plano y en espacios dimensionales superiores se convierte en un hiperplano .

Puede obtener algún tipo de intuición sobre estos conceptos pensando en puntos y líneas en 2D/3D. Aquí hay un par de ejemplos muy artificial ...

Este es un gráfico de un problema lineal inseparables. No hay una línea recta que pueda separar los puntos rojo y azul.

Sin embargo, si le damos a cada punto de un extra de coordenadas (en concreto 1 - sqrt(x*x + y*y) ...Te dije que fue ideado), entonces el problema se vuelve separable linealmente ya que los puntos rojo y azul se pueden separar por un plano bidimensional que pasa por z=0.

Esperamos que estos ejemplos demuestran parte de la idea detrás del truco del núcleo:

Asignación de un problema en un espacio con un mayor número de dimensiones hace que sea más probable que el problema se hará linealmente separables.

La segunda idea detrás del truco del kernel (y la razón por la cual es tan complicado) es que generalmente es muy incómodo y computacionalmente costoso trabajar en un espacio de muy alta dimensión. Sin embargo, si un algoritmo solo utiliza los productos de puntos entre los puntos (que puedes considerar como distancias), entonces solo tienes que trabajar con una matriz de escalares. Puede realizar implícitamente los cálculos en el espacio de mayor dimensión sin tener que hacer la asignación o manejar los datos de mayor dimensión.

Answer 5

Creo siguiente enlace también es útil ...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data