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.

Anuncios