You are currently browsing the monthly archive for agosto 2015.

   Consideremos un conjunto no numerable de números positivos. ¿Es posible que su suma sea finita? En otras palabras, se quiere verificar que la serie infinita definida mediante este conjunto es convergente. De hecho, trabajar con series sobre conjuntos no numerables es algo complicado de entender. Veremos algunas aproximaciones: una intuitiva y otra rigurosa.

   Podríamos considerar el conjunto {S} de números y definir

\displaystyle  \sum S = \left\{\sum A : A\subseteq S, A \text{ finito}\right\}.

Sin embargo esta definición falla cuando se permite que un mismo número ocurra más de una vez en la suma, ya que podría ocurrir una infinidad no numerable de veces.

   Corrigiendo lo anterior, supongamos que {\{s_i : i\in I\}} es un conjunto de números positivos. Definimos

\displaystyle  \sum_{i\in I} s_i = \sup\left\{ \sum_{i\in I_0} s_i : I_0\subseteq I, I_0 \text{ finito}\right\}.

(Si tanto números positivos como negativos están involucrados, hablamos acerca de un límite en lugar de un supremo; lo que hace la definición más complicada ya que tenemos que tratar con la convergencia condicional y reordenamientos.)

   Ahora, consideremos

\displaystyle \begin{aligned}  & \{i\in I : s_i \ge 1\} \\  & \{i\in I : 1/2 \le s_i < 1 \} \\  & \{i\in I : 1/3 \le s_i < 1/2 \} \\  & \{i\in I : 1/4 \le s_i < 1/3 \} \\  & \quad \quad \quad \vdots  \end{aligned}

Si uno de estos conjuntos es infinito, obtenemos {\sum_{i\in I} s_i=\infty}. Pero si todos son finitos, tenemos que {I} es a lo sumo infinito numerable.

   Así, la suma de infinitos números positivos no numerable es infinito.

   Ahora bien, podemos mostrar esto desde un punto de vista riguroso. Partamos de la definición

Definición 1 (Series sobre conjuntos numerables). Sea {X} un conjunto numerable, y sea {f\colon X\rightarrow\mathbf R} una función. Decimos que la serie {\sum_{x\in X}f(x)} es absolutamente convergente si, y sólo si, para alguna biyección {g\colon\mathbf N\rightarrow X}, la suma {\sum_{n=0}^\infty f(g(n))} es absolutamente convergente. Entonces definimos la suma {\sum_{x\in X}f(x)} mediante la fórmula

\displaystyle \sum_{x\in X}f(x)=\sum_{n=0}^\infty f(g(n)).

   Con esta definición podemos mostrar una caracterización de las series absolutamente convergentes.

Lema 2. Sea {X} un conjunto a lo más numerable, y sea {f\colon X\rightarrow\mathbf R} una función. Entonces la serie {\sum_{x\in X} f(x)} es absolutamente si, y sólo si,

\displaystyle \sup\left\{\sum_{x\in A}|f(x)|:A\subseteq X, A\text{ finito}\right\}<\infty.

   Inspirados por esta proposición, podemos definir el concepto de serie absolutamente convergente incluso cuando el conjunto {X} podría ser no numerable.

Definición 3. Sea {X} un conjunto (que podría ser no numerable), y sea {f\colon X\rightarrow\mathbf R} una función. Decimos que la serie {\sum_{x\in X} f(x)} es absolutamente convergente si, y sólo si,

\displaystyle \sup\left\{\sum_{x\in A}|f(x)|:A\subseteq X, A\text{ finito}\right\}<\infty.

   Notar que todavía nos hemos dicho a qué es igual la serie {\sum_{x\in X} f(x)}. Cumpliremos con esto mediante la siguiente proposición:

Lema 4. Sea {X} un conjunto (que podría ser no numerable), y sea {f\colon X\rightarrow\mathbf R} una función tal que la serie {\sum_{x\in X} f(x)} es absolutamente convergente. Entonces el conjunto {\{x\in X:f(x)\ne0\}} es a lo sumo numerable.

   Debido a esto, podemos definir el valor de {\sum_{x\in X} f(x)} para cualquier serie absolutamente convergente sobre un conjunto no numerable {X} mediante la fórmula

\displaystyle \sum_{x\in X} f(x):=\sum_{x\in X:f(x)\ne0} f(x),

ya que hemos reemplazado una suma sobre un conjunto no numerable {X} por una suma sobre el conjunto numerable {\{x\in X:f(x)\ne0\}}. (Notar que si la primera suma es absolutamente convergente, la última también lo es.) También, notar que esta definición es consistente con las definiciones para series sobre conjuntos numerables.

   Leía un problema propuesto sobre límites de sucesiones. Me pareció interesante como de manera intuitiva se puede formar una expresión exacta de “un índice tiende a infinito cuando el otro índice tiende a infinito, y viceversa”. Es evidente que lo primero que uno se podría preguntar es ¿qué es lo que se desea probar, que toda subsucesión de una sucesión convergente, es también convergente y converge al mismo límite? ¿Cómo damos sentido a que un índice tienda a infinito mientras otro lo hace? ¿No deberíamos tener como premisa que hay al menos una relación (tal vez funcional) entre ellos?

   Veamos… El problema en cuestión es

Ejercicio 1. Sea {(a_n)^\infty_{n=p}} una sucesión de números reales, y sea {L} un número real. Supongamos que {(a_n)^\infty_{n=p}} es convergente y su límite es {L}, es decir, tenemos que {\lim_{n\rightarrow\infty}a_n=L}. Además, tenemos que {n\rightarrow\infty} siempre que {m\rightarrow\infty} y el recíproco también es cierto. ¿Cómo probar rigurosamente que {\lim_{n\rightarrow\infty}a_n=\lim_{m\rightarrow\infty}a_n=L}.

   El punto aquí es que no tenemos una definición clara de qué debe entenderse por “{n\rightarrow\infty} siempre que {m\rightarrow\infty}” ni de {\lim_{m\rightarrow\infty}a_n}. Aunque es más o menos compresible lo que se quiere decir: hay alguna relación entre {m} y {n} de modo que crece mientras la otra también lo hace.

   El primer intento presentado fue el siguiente: sea {m(n)} una función monótona desde {\mathbf N} hasta {\mathbf N}. Entonces {(a_m)^\infty_{m=q}:=(a_{m(n)})^\infty_{n=p}} es una subsucesión de {(a_n)^\infty_{n=p}}. Como sabemos que toda subsucesión converge al mismo límite que la sucesión convergente original, podemos afirmar que {\lim_{n\rightarrow\infty}a_{m(n)}=L}.

   Pero se asume mucho… La existencia de una función monótona ya es una sugerencia a que dicha función ha de ser creciente, de otro modo no podría definir una subsucesión y el problema es trivial. Afirma que “{m\rightarrow\infty} cuando {n\rightarrow\infty}” implica la existencia de dicha función, y en esto estamos de acuerdo: ha de existir una función que relacione ambos índices. Lo que si me parece una suposición fuerte es que esta sea monótona; es más, esto lleva a decir que dicha función define una subsucesión convergente.

   Ahora bien, {m(n)} no tiene porqué ser monótona. Basta ver la sucesión {1,1,1,10,2,2,50,3,60,1,100,0,200,\dotsc} para notar que esta tiende a infinito pero no es estrictamente monótona. Ya que estamos de acuerdo en que existe una relación funcional, partiré sólo de esa premisa.

   Sea {m\colon\mathbf N\rightarrow\mathbf N} una función con {f(n)\in\mathbf N}. (Esto es irrelevante, pero lo pongo para que se note el uso del índice {n}.) Con esto, la afirmación “{m\rightarrow\infty} cuando {n\rightarrow\infty}” puede expresarse con {\lim_{n\rightarrow\infty}m(n)=\infty}. Por definición, tenemos que para cualquier {M>0}, existe un {N\ge q} tal que {m(n)\ge M} para todo {n\ge N}.

   Por definición de convergencia, tenemos que {(a_n)^\infty_{n=p}} converge a {L} siempre que para cualquier {\epsilon>0}, existe un {N\ge p} tal que {d(a_j,L)\le\epsilon} para todo {j\ge N}.

   Así ¿podemos fijar un {N':=m(j)} para algún {j\in\mathbf N} y {j\ge q} de manera que {N'\ge N} sirva para satisfacer la definición de convergencia con {(a_m)^\infty_{m=q}}?

   La respuesta es obvia. Con esto vemos que suponer que dicha función permite definir una subsucesión es una afirmación fuerte y usarla es asumir demasiado de las premisas. Finalmente dejo el enunciado de la proposición que supongo fue la que llevo a considerar la existencia de una subsucesión.

Proposición 1. Sea {(a_n)^\infty_{n=0}} una sucesión de números reales, y sea {L} un número real. Entonces los siguientes dos enunciados son lógicamente equivalentes (cada una implica la otra):

  1. La sucesión {(a_n)^\infty_{n=0}} converge a {L}.
  2. Toda subsucesión de {(a_n)^\infty_{n=0}} converge a {L}.

(Notar que una de las dos implicaciones tiene una prueba muy breve.) 🙂

   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.