algorithm - son - ¿Diferencia entre un problema lineal y un problema no lineal? Esencia de Dot-Producto y truco Kernel
programacion lineal youtube (5)
- Las ecuaciones lineales son homogéneas, y se aplica la superposición. Puede crear soluciones utilizando combinaciones de otras soluciones conocidas; Esta es una de las razones por las cuales las transformaciones 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.
- No estoy seguro de cómo expresar la importancia del producto punto, pero toma dos vectores y devuelve un escalar. Ciertamente, una solución a una ecuación escalar es menos laboriosa que resolver una ecuación vectorial o de tensor de orden superior, simplemente porque hay menos componentes con los que tratar.
Mi intuición en este asunto se basa más en la física, por lo que me cuesta mucho traducir a AI.
El truco del núcleo 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 ayuda el kernel trick a usar los clasificadores lineales en un problema no lineal?
2. ¿Por qué es tan importante el producto punto en los dos casos?
Gracias.
Creo que el siguiente enlace también es útil ...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data
Cuando la gente dice problema lineal con respecto a un problema de clasificación, por lo general significa un problema linealmente separable. Linealmente separables 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 , hay algunos números theta1 y theta2 , por lo 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 de dimensiones superiores se convierte en un hiperplano .
Puede obtener algún tipo de intuición sobre estos conceptos si piensa en puntos y líneas en 2D / 3D. Aquí hay un par de ejemplos muy artificiales ...
Esta es una gráfica de un problema lineal inseparable. No hay una línea recta que pueda separar los puntos rojos y azules.
Sin embargo, si le damos a cada punto una coordenada adicional (específicamente 1 - sqrt(x*x + y*y) ... Les dije que fue ideado), entonces el problema se puede separar linealmente ya que los puntos rojo y azul se pueden separar por un plano bidimensional que pasa por z=0 .
Con suerte, estos ejemplos demuestran parte de la idea detrás del truco del kernel:
Asignar un problema a un espacio con un número mayor de dimensiones hace que sea más probable que el problema se pueda separar linealmente.
La segunda idea detrás del truco del kernel (y la razón por la que es tan complicado) es que generalmente es muy incómodo y computacionalmente costoso trabajar en un espacio de dimensiones muy altas. Sin embargo, si un algoritmo solo usa los productos de punto entre puntos (que puede considerarse como distancias), entonces solo tiene que trabajar con una matriz de escalares. Puede realizar implícitamente los cálculos en el espacio de dimensión superior sin tener que realizar el mapeo o manejar los datos de dimensión superior.
La principal diferencia (para fines 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 ninguna solución. Usted sabe mucho, incluso antes de que sepa el problema en absoluto. Mientras sea lineal, obtendrás una respuesta; con rapidez.
La intuición de esto es el hecho de que si tiene dos líneas rectas en algún espacio, es bastante fácil ver si se intersecan o no, y si las tienen, es fácil saber dónde.
Si el problema no es lineal, bueno, puede ser cualquier cosa, y usted no sabe casi nada.
El producto puntual de dos vectores solo significa lo siguiente: La suma de los productos de los elementos correspondientes. Así que si tu problema es
c1 * x1 + c2 * x2 + c3 * x3 = 0
(donde normalmente conoce los coeficientes c, y busca las variables x), el lado izquierdo es el producto puntual de los vectores (c1,c2,c3) y (x1,x2,x3) .
La ecuación anterior es (en gran medida) la definición misma de un problema lineal, por lo que existe su conexión entre el producto de puntos y los problemas lineales.
Muchos clasificadores, entre ellos la Máquina de vectores de soporte (SVM) lineal, solo pueden resolver problemas que son linealmente separables, es decir, donde los puntos que pertenecen a la clase 1 pueden separarse de los puntos que pertenecen a la clase 2 mediante un hiperplano.
En muchos casos, un problema que no se puede separar linealmente puede resolverse aplicando una transformación phi () a los puntos de datos; se dice que esta transformación transforma los puntos en espacio de características . La esperanza es que, en el espacio de características, los puntos sean linealmente separables. (Nota: este no es el truco del kernel todavía ... estad atentos.)
Se puede mostrar que cuanto más alta sea la dimensión del espacio de la característica, mayor será el número de problemas que se pueden separar linealmente en ese espacio. Por lo tanto, uno desearía idealmente que el espacio de características sea lo más dimensional posible.
Desafortunadamente, a medida que aumenta la dimensión del espacio de características, también lo hace la cantidad de cómputo requerida. Aquí es donde entra en juego 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. (Indicaré un producto escalar entre x1 y x2 por <x1, x2> ).
Si transformamos nuestros puntos en espacio de características, el producto escalar ahora se ve así:
<phi(x1), phi(x2)>
La idea clave es que existe una clase de funciones llamadas kernels que se pueden usar para optimizar el cálculo de este producto escalar. Un kernel 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 "viven") sin tener que transformar el espacio de características de alta dimensión (donde phi (x1) y phi (x2) "en vivo ") - pero aún tenemos los beneficios de transformarnos en el espacio de características de alta dimensión. Esto se llama el truco del kernel .
Muchos núcleos populares, como el kernel gaussiano , en realidad corresponden a una transformación phi () que se transforma en un espacio característico infintidimensional . 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 limitadas de memoria).