You are currently browsing the category archive for the ‘math.ML’ category.

   Revisando comentarios acerca de machine leanring, hallé una pequeña explicación que hice sobre el algoritmo LMS (Least Mean Square) para el aprendizaje de funciones lineales.

   El objetivo del proceso es hallar los parámetros {\omega_i}, con {i=1,2,\dots,n}, de la función lineal

\displaystyle  h_\omega(x) = \omega_0 + \omega_1 x_1 + \omega_2 x_2 + \dotsb + \omega_n x_n,

donde {n} es la cantidad de parámetros de los datos de entrenamiento, la entrada de entrenamiento es {x} y {h_\omega(x)} es la salida de nuestra función de aprendizaje. Además, notar que {\omega_0} es la bias o el término de intersección; si la función lineal fuera {y = a + bx}, en este caso {\omega_0} cumple el mismo papel que {a}.

   Ahora, lo que queremos es hallar los valores de {\omega_0, \omega_1, \dotsc, \omega_n}. Es posible usar la notación de matrices y vectores para facilitar la representación. Así, tenemos los vectores {\mathbf w} de parámetros y {\mathbf x} que es el valor de entrenamiento:

\displaystyle  \mathbf w = \begin{pmatrix} \omega_0 \\ \omega_1 \\ \vdots \\ \omega_n \end{pmatrix} \qquad\text{y}\qquad \mathbf x = \begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_n \end{pmatrix},

de los cuales podemos obtener la suma original mediante

\displaystyle  \begin{array}{rcl} \mathbf w^T\mathbf x & = & (\omega_0 \; \omega_1 \; \dotsm \; \omega_n)\begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_n \end{pmatrix} \\ & = & \omega_0 x_0 + \omega_1 x_1 + \omega_2 x_2 + \dotsb + \omega_n x_n, \end{array}

donde {\mathbf w^T} es la transpuesta de {\mathbf w}. Notar que la suma es la misma que la función de aprendizaje cuando {x_0 = 1}, lo cual se hace para fijar el término de intersección {\omega_0} (ya que {\omega_0x_0 = \omega_0 1 = \omega_0}). Simplificando nuestra notación:

\displaystyle  h(\mathbf x) = \sum_{i=0}^n \omega_i x_i = \mathbf w^T \mathbf x.

   Finalmente, supongamos que tenemos {m} elementos en nuestro conjunto de entradas de entrenamiento {W}. Se necesita definir una función de costo {E\colon W\rightarrow \mathbf R} para medir el error de la función de aprendizaje:

\displaystyle  E(w) = \frac{1}{2} \sum_{i=1}^m (h_\omega(x^{(i)}) - y^{(i)})^2,

donde {x^{(i)}} es la entrada de entrenamiento y {y^{(i)}} su salida, siendo ambas el {i}-ésimo elemento. (Se usa esta notación para no confundir con el {i}-ésimo parámetro de {x} que es {x_i}.)

Algoritmo LMS. Considerando el descenso gradiente, se inicia el proceso con un {\omega} aleatorio y se repite la actualización de los parámetros:

\displaystyle  \omega_j := \omega_j - \eta \frac{\partial}{\partial \omega_j} E(\omega).

(Esta actualización es simultánea, i.e., Primero se calculan todos los errores, luego se actualizan los parámetros.)

   Para implementar este algoritmo cuando se tiene una función lineal, evaluamos la razón de cambio de la función de error (respecto al parámetro {\omega}):

\displaystyle  \begin{array}{rcl}\displaystyle\frac{\partial}{\partial \omega_j}E(\omega)&=&\displaystyle\frac{\partial}{\partial \omega_j}\frac{1}{2}\sum_{i=1}^m(h_\omega(x^{(i)}) - y^{(i)})^2\\&=&\displaystyle\frac{1}{2}\sum_{i=1}^m\frac{\partial}{\partial \omega_j}(h_\omega(x^{(i)}) - y^{(i)})^2\\&=&\displaystyle\frac{1}{2}\sum_{i=1}^m2(h_\omega(x^{(i)}) - y^{(i)})x_j\\&=&\displaystyle\frac{1}{2}2\sum_{i=1}^m(h_\omega(x^{(i)}) - y^{(i)})x_j\\&=&\displaystyle\sum_{i=1}^m(h_\omega(x^{(i)}) - y^{(i)})x_j.\end{array}

   Así, debemos actualizar los parámetros mediante

\displaystyle  \omega_j := \omega_j + \eta \sum_{i=1}^m(y^{(i)}-h_\omega(x^{(i)}))x_j^{(i)}.

   Procedemos de manera análoga para usar la notación vectorial {\mathbf w^T\mathbf x}. Calculamos el error usando las operaciones entre matrices y vectores. Suponiendo que nuestro conjunto de entrenamiento es

\displaystyle  X = \begin{pmatrix}-(x^{(1)})^T-\\-(x^{(2)})^T-\\\vdots\\-(x^{(m)})^T-\end{pmatrix}.

Además, tenemos que {\mathbf y} es un vector {m}-dimensional con los valores objetivo:

\displaystyle  \mathbf y=\begin{pmatrix}y^{(1)}\\y^{(2)}\\\vdots\\y^{(m)}\end{pmatrix}.

Ahora, ya que {h_\omega(x^{(i)})=(x^{(i)})^T\mathbf w}, tenemos que

\displaystyle  \begin{array}{rcl}X\mathbf w -\mathbf y&=&\begin{pmatrix}(x^{(1)})^T\mathbf w\\\vdots\\(x^{(m)})^T\mathbf w\end{pmatrix}-\begin{pmatrix}y^{(1)}\\\vdots\\y^{(m)}\end{pmatrix}\vspace{1ex}\\&=&\begin{pmatrix}(x^{(1)})^T\mathbf w-y^{(1)}\\\vdots\\(x^{(m)})^T\mathbf w-y^{(m)}\end{pmatrix}.\end{array}

Como {\mathbf v^T\mathbf v = \sum_i\mathbf v_i^2} para un vector {\mathbf v}, obtenemos

\displaystyle  \begin{array}{rcl}E(\omega)&=&\displaystyle\frac{1}{2}\sum_{i=1}^m(h_\omega(x^{(i)}) - y^{(i)})^2\\&=&\displaystyle\frac{1}{2}(X\mathbf w-\mathbf y)^T(X\mathbf w-\mathbf y).\end{array}

   Resumiendo, para obtener

\displaystyle \mathbf w=\begin{pmatrix}w_0\\w_1\end{pmatrix},

, procedemos:

  1. Fijando las colecciones {x} e {y}:

    \displaystyle  x=\begin{pmatrix}1\\3\\5\\7\\9\end{pmatrix}\qquad y=\begin{pmatrix}1\\3\\4\\3\\5\end{pmatrix}.

  2. Iterando hasta que {\omega_j} converja (probar con {10} iteraciones) {

       Desde {i=1} hasta {m} {

    \displaystyle  \omega_j := \omega_j+\eta\sum_{i=1}^m(y^{(i)}-h_\omega(x^{(i)}))x_j^{(i)}\qquad(\text{por cada }j)

    } }

   O usando las fórmulas vectoriales

  1. Asignando la matriz {X} y el vector {\mathbf y}:

    \displaystyle  X=\begin{pmatrix}1&1\\1&3\\1&5\\1&7\\1&9\end{pmatrix}\qquad\mathbf y=\begin{pmatrix}1\\3\\4\\3\\5\end{pmatrix}.

  2. Iterando hasta que {\mathbf w} converja (probar con {10} iteraciones) {

    \displaystyle  \mathbf w := \mathbf w- \frac{\eta}{m} \left((X\mathbf w-\mathbf y)^TX\right)

    }

Observación 1. Es posible obtener los parámetros {\omega} de manera analítica usando la ecuación normal para calcular {\mathbf w} mediante

\displaystyle  \mathbf w=(X^TX)^{-1}X^T\mathbf y.

Este artículo es el primero de una serie acerca de los conceptos y herramientas que se manejan en el campo de estudio conocido como Machine Learning, que es un tópico de Inteligencia Artificial, Estadística y Teoría de la Probabilidad.

— 1. Regresión por el método de mínimos cuadrados —

Una de las maneras más sencillas de obtener una función a base de datos experimentales es el método de “mínimos cuadrados”. Supongamos que necesitamos determinar experimentalmente una dependencia de la magnitud {y} en función de {x}:

\displaystyle  y = \varphi(x).

Del experimento obtenemos como resultado {n} valores de la función {y} para los valores correspondientes del argumento {x}:

\displaystyle  \begin{array}{c|cccc} \mathbf x & x_1 & x_2 & \quad\dotso\quad & x_n \\\hline \mathbf y & y_1 & y_2 & \quad\dotso\quad & y_n \end{array}

La forma de la función {y = \varphi(x)} se determina teóricamente o usando la disposición en el plano de coordenadas de los puntos correspondientes a los valores experimentales. Dependiendo de la distribución de estos puntos elegiremos la forma de la función desconocida {y = \varphi(x)}. Por ejemplo, si vemos que los puntos experimentales no se separan mucho de una recta, entonces se puede buscar la función {y = \varphi(x)} en la forma de una función lineal {y = ax + b}; si los puntos experimentales tienden a “ir hacia arriba”, entonces es natural pensar que podemos buscar la función {y = \varphi(x)} en la forman {y = ax^b}; así sucesivamente, es decir, viendo la distribución de los puntos experimentales debemos elegir una función conocida (lineal, potencial, trigonométrica, exponencial, logarítmica, etc.) que nos parezca más la adecuada para buscar la función {y = \varphi(x)}. Elegida la forma de la función {y = \varphi(x, a, b, c, \dotsc)}, tenemos que buscar los parámetros {a,b, c, \dotsc} que la integran, de moto tal que la función describa de la mejor manera el proceso examinado.

El método que tratamos ahora es el de mínimos cuadrados que consiste en lo siguiente.

Examinemos una suma de los cuadrados de las diferencias de los valores {y_i}, obtenidas de experimento, y la función {\varphi(x,a,b,c,\dotsc)} en los puntos correspondientes:

\displaystyle   S(a,b,c,\dotsc) = \sum_{i=1}^n [y_i - \varphi(x,a,b,c,\dotsc)]^2. \ \ \ \ \ (1)

Elijamos los parámetros {a,b,c,\dotsc} de manera que esta suma tenga valor mínimo:

\displaystyle S(a,b,c,\dotsc) = \sum_{i=1}^n [y_i - \varphi(x,a,b,c,\dotsc)]^2 = \min.

Así, el problema se ha reducido a la búsqueda de los valores de los parámetros {a,b,c,\dotsc}, para los cuales la función {S(a,b,c,\dotsc)} tiene un mínimo. Esto es posible por la prueba de la primera derivada, estudiada en un curso de Cálculo diferencial; así, en virtud de lo anterior, tenemos que estos valores {a,b,c,\dotsc} satisfacen el sistema de ecuaciones

\displaystyle \frac{\partial S}{\partial a} = 0, \frac{\partial S}{\partial b} = 0, \frac{\partial S}{\partial c} = 0, \dotsc,

o, en la forma desarrollada

\displaystyle   \begin{aligned} \sum_{i=1}^n [y_i - \varphi(x,a,b,c,\dotsc)]\frac{\partial \varphi(x,a,b,c,\dotsc)}{\partial a} = 0, \\ \sum_{i=1}^n [y_i - \varphi(x,a,b,c,\dotsc)]\frac{\partial \varphi(x,a,b,c,\dotsc)}{\partial b} = 0, \\ \sum_{i=1}^n [y_i - \varphi(x,a,b,c,\dotsc)]\frac{\partial \varphi(x,a,b,c,\dotsc)}{\partial c} = 0, \\ \vdots \quad\; \end{aligned} \ \ \ \ \ (2)

Notar que el número ecuaciones es igual al número de incógnitas. En cada caso concreto se investiga la cuestión sobre la existencia de la solución del sistema de ecuaciones (2) y del mínimo de la función {S(a,b,c,\dotsc)}.

Veamos algunos casos de la determinación de la función {y = \varphi(x,a,b,c,\dotsc)}.

I. Sea {y = ax + b}. Entonces, la función {S(a,b)}, en la expresión (1), tiene la forma

\displaystyle S(a,b) = \sum_{i=1}^n [y_i - (ax_i + b)]^2.

Esta es una función con dos variables, {a} y {b} ({x_i} e {y_i} son parte de los datos experimentales). Por consiguiente,

\displaystyle  \begin{aligned} \frac{\partial S}{\partial a} & = -2 \sum_{i=1}^n [y_i - (ax_i + b)]x_i = 0,\\ \frac{\partial S}{\partial b} & = -2 \sum_{i=1}^n [y_i - (ax_i + b)] = 0, \end{aligned}

es decir, el sistema de ecuaciones (2) en este caso, toma la forma

\displaystyle  \begin{aligned} &\sum_{i=1}^n y_i x_i - a \sum_{i=1}^n x_i^2 - b \sum_{i=1}^n x_i = 0,\\ &\sum_{i=1}^n y_i - a \sum_{i=1}^n x_i - bn = 0. \end{aligned}

Hemos obtenido el sistema de dos ecuaciones lineales con dos incógnitas {a} y {b}. Es fácil ver que el sistema tiene una solución determinada y la función {S(a,b)} tiene un mínimos para los valores hallados {a} y {b}. Esto se verifica fácilmente también a base de las condiciones suficientes para la existencia del mínimo. Recordemos. Sea {(x_0,y_0)} es un punto crítico de la función {f(x,y)}, es decir,

\displaystyle  \frac{\partial f(x_0,y_0)}{\partial x} = 0, \qquad \frac{\partial f(x_0,y_0)}{\partial y} = 0.

Entonces, para {x = x_0} e {y = y_0} se cumple que {f(x,y)} tiene mínimo, si

\displaystyle  \frac{\partial^2 f(x_0,y_0)}{\partial x^2} \times \frac{\partial^2 f(x_0,y_0)}{\partial y^2} - \left(\frac{\partial^2 f(x_0,y_0)}{\partial x\,\partial y}\right)^2 > 0 \;\;\text{y}\;\; \frac{\partial^2 f(x_0,y_0)}{\partial x^2} > 0.

En efecto, tenemos

\displaystyle \frac{\partial^2 S}{\partial a^2} = \sum_{i=1}^n x^2_i; \quad \frac{\partial^2 S}{\partial a\,\partial b} = \sum_{i=1}^n x_i; \quad \frac{\partial^2 S}{\partial b^2} = n.

Así,

\displaystyle  \begin{aligned} &\frac{\partial^2 S}{\partial a^2}\frac{\partial^2 S}{\partial b^2}-\left(\frac{\partial^2 S}{\partial a\,\partial b}\right)^2 = n \sum_{i=1}^n x_i^2 - \left(\sum_{i=1}^n x_i\right)^2 = \sum_{i\ne j} (x_i - x_j)^2 > 0,\\ &\frac{\partial^2 S}{\partial a^2} > 0. \end{aligned}

II. Sea la función de aproximación un trinomio de segundo grado {y = ax^2 + bx + c}. En este caso la expresión (1) tiene la forma

\displaystyle  S(a,b,c) = \sum_{i=1}^n [y_i - (ax_i^2 + bx_i + c)]^2.

El sistema de ecuaciones (2) toma la forma

\displaystyle  \begin{aligned} &\sum_{i=1}^n [y_i - (ax_i^2 + bx_i + c)]x_i^2 = 0, \\ &\sum_{i=1}^n [y_i - (ax_i^2 + bx_i + c)]x_i = 0, \\ &\sum_{i=1}^n [y_i - (ax_i^2 + bx_i + c)] = 0, \end{aligned}

o, en la forma desarrollada

\displaystyle  \begin{aligned} &\sum_{i=1}^n y_i x_i^2 - a \sum_{i=1}^n x_i^4 - b \sum_{i=1}^n x_i^3 - c \sum_{i=1}^n x_i^2 = 0, \\ &\sum_{i=1}^n y_i x_i - a \sum_{i=1}^n x_i^3 - b \sum_{i=1}^n x_i^2 - c \sum_{i=1}^n x_i = 0, \\ &\sum_{i=1}^n y_i - a \sum_{i=1}^n x_i^2 - b \sum_{i=1}^n x_i - cn = 0. \end{aligned}

Obtenemos un sistema de ecuaciones lineales para determinar las incógnitas {a,b,c}. De las condiciones del problema se deduce que el sistema tiene una solución determinada y, además, la función {S(a,b,c)} tiene un mínimo para los valores obtenidos de {a,b,c}.

Continuará…