Álgebra lineal y redes neuronales

Las redes neuronales son modelos cuantitativos que aprende como asociar una «entrada» y una «salida» con el uso de algoritmos de aprendizaje. El objetivo aquí, será exponer cuatro conceptos principales del álgebra lineal que son esenciales para el análisis de estos modelos: 1) la proyección de un vector, 2) la descomposición por valores propios y singulares, 3) el gradiente de una matriz Hessiana de una función vectorial, y 4) la expansión en Taylor de una función vectorial. Estos conceptos son ilustrados con el análisis de las reglas de Hebbian y Widrow-Hoff y algunas arquitecturas simples de las redes neuronales (es decir, el auto asociador lineal, el heteroasociador y el error de redes por propagación regresiva). Se muestra también que las redes neuronales son equivalente a versiones iterativas de la estadística estándar y modelos de optimización tales como el análisis de regresión multiple y el análisis por componentes principales.

El álgebra lineal es usada particularmente para analizar la clase de redes neuronales denominadas «asociadores». Estos modelos de aprendizaje cuantitativo asocian una «entrada» y una «salida» mediante patrones adaptativos que hacen uso de algoritmos de aprendizaje. Cuando el conjunto de patrones de entrada es diferente del conjunto de salida, los modelos se denominan heteroasociadores. Cuando los patrones de entrada y los de salida son iguales, el modelo se denomina autoasociador. Los asociadores consisten de capas de unidades elementales denominadas neuronas. La información fluye a través de todas las capas. Algunas arquitecturas puede incluir capas intermedias (capas ocultas). Típicamente las neuronas de una capa están conectadas con las neuronas de otra capa. El objetivo será entender como algunas operaciones del álgebra lineal describe las transformaciones de la información a través de cada una de las capas.

Como es usual, los vectores serán representados por letras minúsculas (p. ej., $x$), las matrices por letras mayúsculas (p. ej.., $X$). Además se supone que las siguientes nociones son conocidas: La operación de transposición (p. ej., $x^\top$), la norma de un vector (p. ej.,$||x||$), el producto escalar ( p. ej., $x^{\top}w$) y el producto de dos matrices ( p. ej., $AB)$. También se usará el producto de Hadamard (p. ej., $A\odot B$).

Proyección de un vector¶

Coseno entre dos vectores¶

El coseno entre dos vectores $x$ y $y$ es el coseno del ángulo formado por el origen del espacio y los puntos definidos por las coordenadas de los vectores. Por lo tanto,

\begin{equation}\nonumber \cos(x, y) = \frac{x^\top y}{||x||||y||}. \end{equation}

El coseno indica la similaridad entre los vectores. Cuando dos vectores tienen la misma dirección (p. ej. $v=\lambda w, \lambda >0$), su coseno es igual a uno; si tienen dirección opuesta (p. ej. $v=\lambda w, \lambda <0$), su coseno es igual a menos uno; y cuando ellos son ortogonales (p. ej. $v^{\top}w=0$), su coseno es igual a cero.

Distancia entre vectores¶

Entre una gran familia de distancias entre vectores, la más popular es la distancia euclidiana. Ésta está relacionada con el coseno entre vectores y se define como

\begin{equation}\nonumber d_{2}(x,y)=\sqrt{(x-y)^\top(x-y)}=||(x-y)|| \end{equation}

Proyección de un vector sobre otro vector¶

La proyección ortogonal de un vector $x$ sobre un vector $w$ se define como:

\begin{equation}\nonumber \operatorname{proy}_{\langle w\rangle} x = \frac{x^{\top} w}{w^{\top}w}w. \end{equation}

La norma de $\operatorname*{proy}_{\langle w\rangle} x$ es su distancia al origen del espacio. Esto es igual a:

\begin{equation}\nonumber ||\operatorname{proy}_{\langle w\rangle} x||=\frac{|x^{\top}w|}{||w||}=|\cos(x,y)|||x||. \end{equation}

Las reglas de aprendizaje de Hebbian y Widrow-Hoff¶

Una red neuronal consiste de células conectadas a otras células vía conexiones de peso denominadas sinapsis. Considere una red neuronal de $m$ entradas dada por una capa de células y solo una célula de salida. La información es transmitida vía la sinapsis, del conjunto de entrada de las células externas a las células de salida con la respuesta correspondiente al estado de activación. Si el patrón de entrada y el conjunto de pesos sinápticos son dados por un vector $m$ - dimensional denotado por $x$, y $w$, la activación de la célula de salida es dada por

\begin{equation}\nonumber a = x^{\top}w. \end{equation}

Así la activación es proporcional a la norma de la proyección del vector de entradas sobre el vector de pesos. La respuesta o salida de la célula es denotada por $r$. Para una célula lineal, esta es proporcional a la activación (por conveniencia, se asume que la constante de proporcionalidad es igual a uno). Los heteroasociadores lineales y los autoasociadores son construidos con células lineales. En general, la salida de una célula es una función (no necesariamente continua), denominada la función de transferencia, y su activación es:

\begin{equation}\nonumber \label{eqn:función} r = f(a). \end{equation}

Por ejemplo, en redes de retropropagación, la función de transferencia (no lineal) suele ser la función logística

\begin{equation}\nonumber r = f(a) = \operatorname{logit}(w^{\top}x) = \frac{1}{1 + \exp(-w^{\top}x)}. \end{equation}

A menudo,una red neuronal está diseñada para asociar, a una entrada dada, una respuesta específica llamada objetivo, denotada como $t$. El aprendizaje es equivalente a definir una regla que especifique cómo agregar una pequeña cantidad a cada peso sináptico en cada iteración del algoritmo. El algoritmo acerca la salida de la red al objetivo.

Las reglas de aprendizaje vienen en dos sabores principales: supervisadas (p. ej. Widrow-Hoff) que tienen en cuenta el error o la distancia entre la respuesta de la neurona y el objetivo, y sin supervisión (p ej. Hebbian) que no requieren tal «retroalimentación». La regla de aprendizaje hebbiana modifica el vector de peso en la iteración $k + 1$ como

\begin{equation}\nonumber w_{k+1} = w_{k} + \eta t x, \end{equation}

donde $\eta$ es una pequeña constante positiva llamada constante de aprendizaje. Entonces, en cada iteración de la relgla aprendizaje hebbiana se mueve el vector de peso en la dirección del vector de entrada en una cantidad proporcional al objetivo.

La regla de aprendizaje de Widrow-Hoff utiliza el error y la derivada de la función de transferencia $f$ para calcular la corrección como:

\begin{equation}\nonumber \label{eqn:corrección} w_{k+1} = w_{k} + \eta (t-r_{k})f'(a_k)x. \end{equation}

Entonces, una iteración de aprendizaje de Widrow-Hoff mueve el vector de peso en la dirección del vector de entrada en una cantidad proporcional al error.

Para redes con varias celulas (p. ej. $n$) en la capa de salida, el patrón de activación, salida y objetivo se convierten en vectores $n$ - dimensionales (denotados $a$, $r$ y $t$, respectivamente), y los pesos sinápticos se almacenan en una matriz $W$ de dimensión $m \times n$. Las ecuaciones de aprendizaje se reescriben de la siguiente forma:

\begin{equation}\nonumber W_{k+1} = W_{k}+\eta x t^{\top}\hbox{(Hebbian)} \end{equation}

\begin{equation}\nonumber W_{k+1} = W_{k}+\eta(f'(a_{k})\odot x)(t- r_{k})^{\top} \hbox{ (Widrow-Hoff)}, \end{equation}

en donde la derivada $f'$ aplica sobre $a$ por cada componente, es decir, $f'(a)=(f'(a_{1}),\dots,f'(a_{n}))$.

En general, se deben aprender varias ($l$) asociaciones de entrada / destino. Luego, el conjunto de patrones de entrada se almacena en una matriz $m \times l$ denotada como $X$, los patrones de activación y objetivo respectivamente se almacenan en matrices de dimensión $n \times l$ indicadas como $A$ y $T$, respectivamente. Las iteraciones de activación y aprendizaje se pueden calcular para todos los patrones a la vez (esto se llama aprendizaje por lotes). La matriz de salida se calcula como:

\begin{equation}\nonumber r = f(A) = f(WX^{T}), \end{equation}

en donde $f$ también aplica sobre cada componente de $WX^{\top}$, es decir $f(WX^{\top})=[f([WX^{\top}]_{ij})]$.

Las ecuaciones de aprendizaje se convierten

\begin{equation}\tag{1} W_{k+1} = W_{k} + \eta X T^{\top} \hbox{ (Hebbian)}, \end{equation}

\begin{equation}\tag{2} W_{k+1} = W_{k} + \eta (f'(A_{k}) \odot X)(T- R_{k})^{\top} \hbox{ (Widrow-Hoff).} \end{equation}

Valores propios, vectores propios y la descomposición en valores singulares¶

Los vectores propios de una matriz cuadrada $W$ dada (resultante de su descomposición propia) son vectores invariantes bajo multiplicación por $W$. La descomposición propia se define mejor para una subclase de matrices llamadas matrices semi-definidas positivas. Una matriz $X$ es positiva semi-definida si existe otra matriz $Y$ tal que $X = YY^{\top}$. Este es el caso de la mayoría de las matrices utilizadas en redes neuronales, por lo que se considera solo este caso aquí.

Formalmente, un vector (distinto de cero) $u$ es un vector propio de una matriz cuadrada $W$ si

\begin{equation}\nonumber Wu = \lambda u. \end{equation}

El escalar $\lambda$ es el valor propio asociado con $u$. Entonces $u$ es un vector propio de $W$ si su dirección es invariante bajo la multiplicación por $W$ (solo su longitud cambia si $\lambda \neq 1$). En general, hay varios vectores propios para una matriz dada (como máximo, la dimensión de $W$). En general, se ordenan por orden decreciente de su valor propio. Entonces, el primer vector propio, $u_{1}$ tiene el mayor valor propio $\lambda_{1}$. El número de vectores propios con un valor propio distinto de cero es el rango de la matriz.

Los valores propios de las matrices semidefinidas positivas son siempre positivos o cero (una matriz con valores propios estrictamente positivos, es definida positiva). Además, cualquier par de vectores propios $u_i$, $u_j$, con valores propios diferentes, son ortogonales, es decir:

\begin{equation}\nonumber u_i^{\top} u_{j} = 0 \,\, \forall\,\, i \neq j. \end{equation}

Además, el conjunto de vectores propios de una matriz constituye una base ortogonal para los espacios fila y columna. Esto se expresa definiendo dos matrices, la matriz de vectores propios $U$, y la matriz diagonal de los valores propios $\Lambda$. Así la descomposición propia de $W$ (con rango $n$) es:

\begin{equation}\nonumber W = U \Lambda U^{\top}. \end{equation}

La descomposición de valores singulares (SVD) generaliza la descomposición propia en matrices rectangulares. Si $X$ es una matriz $m \times l$, su SVD se define como:

\begin{equation}\nonumber X = U \Delta V^{\top} \end{equation}

con $U U^{\top} = V^{\top} V = I$ y $\Delta$ una matriz diagonal ($I$ siendo la matriz identidad).

Los elementos diagonales de $\Delta$ son números reales positivos llamados valores singulares de $X$. Las matrices $U$ y $V$ son las matrices izquierda y derecha de vectores singulares (que también son vectores propios, ver más abajo).

El SVD está estrechamente relacionado con la descomposición propia porque $U$, $V$ y $\Delta$ pueden obtenerse a partir de la descomposición propia de las matrices $X^{\top} X$ y $X X^{\top}$ como

\begin{equation}\nonumber X^{\top} X = U \Lambda U^{\top},\,\, X X^{\top} = V \Lambda V^{\top},\hbox{ y } \Delta = \Lambda^{1/2}. \end{equation}

Tenga en cuenta que $X^{\top} X$ y $X X^{\top}$ tienen los mismos valores propios.

Las descomposiciones de valores propios y singulares se utilizan en la mayoría de los campos de las matemáticas aplicadas, incluidas las estadística, el procesamiento de imágenes, la mecánica y los sistemas dinámicos. Para las redes neuronales, son esenciales para estudiar la dinámica de los autoasociadores y heteroasociadores lineales.

Procesos iterativos¶

Un heteroasociador lineal que usa la regla de Widrow-Hoff, el aprendizaje modifica solo los valores propios de la matriz de peso. Específicamente, si los patrones a aprender se almacenan en una matriz $X$ de orden $m \times l$, con una descomposición de valores singulares como $X = U \Delta V^{\top}$, entonces la Ecuación 2 de la regla aprendizaje de Widrow-Hoff se convierte en

\begin{equation}\tag{3} W_{k+1} = W_{k} + \eta X(T - R_{k})^{\top} = U\Delta^{-1}[I - (I - \eta\Delta^2)^{n+1}] V^{\top} T^{\top}, \end{equation}

porque para un heteroasociador lineal $A_{k}=R_{k}$ y $f'(R_{k}) = I$. (ver Abdi, 1994, p.54 ff.).

La matriz de peso de Widrow-Hoff corresponde a la primera iteración del algoritmo, es decir,

\begin{equation}\nonumber W_{1} = U\Delta^{-1}[I - (I - \eta \Delta^2)] V^{\top} T^{\top} = \eta U \Delta V^{\top} T^{\top} = \eta X T^{\top}. \end{equation}

La ecuación Ecuación 3 caracteriza los valores de $\eta$ que permiten que el proceso iterativo converja. Denotando por $\delta_{max}$ el mayor valor singular de $X$, si $\eta$ es tal que:

\begin{equation}\tag{4} 0 < \eta < 2 \delta^{-2}_{max} \end{equation}

entonces se puede demostrar que (ver Abdi, 1994)

\begin{equation}\nonumber \lim_{n \to \infty}(I - \eta \Delta^{2})^{n} = 0 \end{equation}

y por lo tanto

\begin{equation}\nonumber \lim_{n \to \infty} W_{n} = U \Delta^{-1} V^{\top} T^{\top} = X^{+} T. \end{equation}

La matriz $X^{+} = U \Delta^{-1} V^{\top} $ es el pseudoinverso de $X$. Da una solución óptima de mínimos cuadrados para la asociación entre la entrada y el objetivo. Por lo tanto, el heteroasociador lineal es equivalente a la regresión múltiple lineal. Si $\eta$ está fuera del intervalo definido por la Ecuación 4, tanto los valores singulares como los elementos de la matriz de peso crecerán en cada iteración. En la práctica, debido a que las redes neuronales son simuladas por computadoras digitales, la matriz de peso eventualmente alcanzará los límites de la precisión de la máquina.

Cuando los vectores objetivo son los mismos que los vectores de entrada (es decir, cuando cada entrada está asociada a sí misma), el heteroasociador lineal se convierte en un autoasociador lineal. El enfoque anterior muestra que, ahora, la matriz Hebbiana de peso es la matriz de productos cruzados:

\begin{equation}\nonumber W_{1} = X X^{\top} = U \Lambda U^{\top}. \end{equation}

Con el aprendizaje de Widrow-Hoff, cuando se alcanza la convergencia, todos los valores propios distintos de cero de la matriz de peso son iguales a 1. La matriz de peso se dice que es esférica; esto es igual a:

\begin{equation}\nonumber W_{\infty} = U U^{\top}. \end{equation}

Debido a que la técnica estadística del análisis de componentes principales (PCA) calcula la descomposición propia de una matriz de productos cruzados similar a $W$, el autoasociador lineal se considera como la red neuronal equivalente de PCA.

Optimización, Derivadas y Matrices¶

Las redes neuronales se utilizan a menudo para optimizar una función de los pesos sinápticos. La diferenciación de una función es el concepto principal para explorar problemas de optimización y, para redes neuronales, implica la diferenciación de vectores o funciones matriciales. En este contexto, debemos considerar la función de transferencia como una función del vector de peso. Esto es:

\begin{equation}\nonumber r = f(w). \end{equation}

La derivada de $f(w)$ con respecto al vector $w$ de $m$ - dimensional se denota por $\nabla f (w)$. También se llama el gradiente de $f$, es decir,

\begin{equation}\nonumber \nabla f(w) = \frac{\partial f}{\partial w} = \left[\frac{\partial f}{\partial w_{1}},..., \frac{\partial f}{\partial w_{i}},..., \frac{\partial f}{\partial w_{I}} \right]^{\top}. \end{equation}

Por ejemplo, la derivada de la salida de una neurona lineal es

\begin{equation}\nonumber \frac{\partial f}{\partial w} = \left[\frac{\partial w^{\top} x}{\partial w_{1}},\dots, \frac{\partial w^{\top} x}{\partial w_{m}} \right]^{\top} = [x_{1},\dots, x_{m}]^{\top} = x. \end{equation}

Cuando una función es dos veces diferenciable, las derivadas de segundo orden se almacenan en una matriz llamada matriz Hessiana de la función. A menudo se denota por $\nabla^{2}(f)$ (recuerde que $\nabla^{2}(f) = [\nabla\nabla^{\top}](f)$) y se define formalmente como

\begin{equation}\nonumber \nabla^{2}(f) = \left[\begin{array}{cccc} \frac{\partial^{2}_{f}}{\partial w^{2}_{1}} & \frac{\partial^{2}_{f}}{\partial w_{1} w_{2}} & \cdots & \frac{\partial^{2}_{f}}{\partial w_{1} w_{m}} \\ \frac{\partial^{2}_{f}}{\partial w_{2} w_{1}} & \frac{\partial^{2}_{f}}{\partial w^{2}_{2}} & \cdots & \frac{\partial^{2}_{f}}{\partial w_{2} w_{m}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^{2}_{f}}{\partial w_{I}w_{1}} & \frac{\partial^{2}_{f}}{\partial w_{I}w_{2}} & \cdots & \frac{\partial^{2}_{f}}{\partial w^{2}_{m}}. \end{array} \right]. \end{equation}

Condiciones para mínimo¶

Un problema estándar es mostrar que una regla de aprendizaje dada encuentra una solución óptima en el sentido de que una función del vector de peso (o matriz) llamada función de error alcanza su valor mínimo cuando el aprendizaje ha convergido. A menudo, la función de error se define como la suma del error al cuadrado sobre todos los patrones.

Cuando se puede evaluar el gradiente de la función de error, una condición necesaria para la optimización (es decir, mínimo o máximo) es encontrar un vector de peso $w^{*}$ tal que

\begin{equation}\nonumber \nabla f (w^{*}) = 0. \end{equation}

Esta condición también es suficiente siempre que $\nabla^{2}(f)$ sea definida positiva (cf. Haykin, 1999).

Expansión de Taylor¶

La expansión de Taylor es la técnica estándar utilizada para obtener una aproximación lineal o cuadrática de una función de una variable. Recuerde que la expansión de Taylor de una función continua $f(x)$ es

\begin{equation}\nonumber f(x) = \sum_{n=0}^{\infty}(x-a)^{n}\frac{f^{(n)}(a)}{n!} = f(a) +(x-a)\frac{f'(a)}{1!} + (x-a)^{2} \frac{f''(a)}{2!} + \mathcal{R}_{2}, \end{equation}

en donde $\mathcal{R}_{2}$ representa todos los términos de orden superior a 2, y $a$ es un valor «conveniente» para evaluar $f$.

Esta técnica puede extenderse a funciones de matrices y vectores. Implica la noción de gradiente y de Hessiano. Ahora para una función vectorial $f(x)$ se expresa como:

\begin{equation}\nonumber f(x) = f(a) + f(x - a)^{\top}\nabla f(a) + f(x - a)^{\top} \nabla^{2}f(a)f(x - a) + \mathcal{R}_{2}. \end{equation}

Minimización iterativa¶

Se puede demostrar que una regla de aprendizaje converge a un valor óptimo si disminuye el valor de la función de error en cada iteración. Cuando se puede evaluar el gradiente de la función de error, la técnica de gradiente (o descenso más pronunciado) ajusta el vector de peso moviéndolo en la dirección opuesta al gradiente de la función de error. Formalmente, la corrección para la iteración $(k + 1)$ es

\begin{equation}\nonumber w_{k+1} = w_{k} + \nabla = w_{k} - \eta \nabla f(w_k) \end{equation}

Como ejemplo, demostremos que para un heteroasociador lineal, la regla de aprendizaje de Widrow-Hoff minimiza iterativamente el error al cuadrado entre el objetivo y la salida. La función de error es

\begin{equation}\nonumber e^{2} = (t-r)^{2} = t^{2} + r^{2} - 2tr = t^{2} + x^{\top}w w^{\top} -2tw^{\top}x. \end{equation}

El gradiente de la función de error es:

\begin{equation}\nonumber \frac{\partial e}{\partial w} = 2(w^{\top} x)x - 2t x = -2(t - w^{\top} x) x. \end{equation}

El vector de peso se corrige moviéndose en la dirección opuesta del gradiente. Esto proporciona la siguiente corrección para la iteración $k + 1$:

\begin{equation}\nonumber w_{k+1} = w_{k} - \eta \frac{\partial e}{\partial w} = w_{k} + \eta (t-w^{\top}_{k}x)x = w_{k} + \eta(t-o_{k})x. \end{equation}

Esto da la regla de aprendizaje de Widrow-Hoff en su expresión más simple.

El método de gradiente funciona porque el gradiente de $w_{n}$ es una aproximación de Taylor de primer orden del gradiente del vector de peso óptimo $w^{*}$. Es una técnica favorita en las redes neuronales porque el error de propagación posterior popular es una técnica de gradiente.

El método de Newton es una aproximación de Taylor de segundo orden, utiliza el inverso del hessiano de $w$ (suponiendo que exista). Proporciona una mejor aproximación numérica pero requiere más cómputo. Aquí la corrección para la iteración $k + 1$ es

\begin{equation}\nonumber w_{k+1} = w_{k} - [\nabla^{2}f(w_{k})]^{-1} \nabla_{f(w_{k})}. \end{equation}

Referencias¶

• Hervé Abdi. 2001. Linear Algebra for Neural Networks.
• Hervé Abdi et al. 1999. Neural networks. Thousand Oak.

Contacto¶

• Participa de la canal de Nerve a través de Discord.
• Se quieres conocer más acerca de este tema me puedes contactar a través de Classgap.

Read More

Geometría de Incidencia

Una geometría de incidencia está formada por un conjunto $\mathbb{E}$ al que se denomina espacio y a cuyos elementos se conocerán como puntos, junto con dos familias disyuntas y no vacías $\mathcal{L}$, $\mathcal{P}$ de subconjuntos no vacíos del espacio a cuyos elementos se denominaran respectivamente rectas y planos, de modo que se satisfacen los siguientes axiomas:

• Axioma AI1. Cualquier par de puntos distintos pertenecen a una única recta.
• Axioma AI2. Para toda recta, existe al menos dos puntos distintos que pertenecen a ella.
• Axioma AI3. Para cualquier tripleta de puntos distintos, tales que no pertenecen simultáneamente a ninguna recta, pertenecen a un único plano.
• Axioma AI4. Para todo plano, existe al menos tres puntos distintos que pertenecen a él y no pertenecen simultaneamente a ninguna recta.
• Axioma AI5. Si un plano y una recta tienen al menos dos puntos en común, entonces la recta está contenida en el plano.
• Axioma AI6. Si dos planos tienen un punto en común, entonces tienen dos puntos en común.
• Axioma AI7. Para todo plano existe al menos un punto que no pertenece a él.

Cuando tres puntos o más pertenecen simultáneamente a una única recta, entonces se dice que son colineales. También se dirá que cuatro puntos o más son coplanares si pertenecen simultáneamente a un único plano.

Los axiomas anteriores pueden tener muchas interpretaciones, debido a que el espacio $\mathbb{E}$ se considera como un conjunto del cuál no se ha especificado la naturaliza de sus elementos. Con el objetivo de estimular el entendimiento de estos conceptos, inclusive sus limitaciones, se le sugiere al lector que estudie cuidadosamente los siguientes ejemplos, y descubra que estos ejemplos cumplen con la definición de una geometría de incidencia.

Ejemplo 1. Considere el conjunto $\mathbb{E}=\{A, B, C\}$ y la familia de rectas $\mathcal{L}=\{\{A,B\},\{A,C\}, \{B, C\}\}$. Sin duda el lector podrá verificar que $\mathbb{E}$ y $\mathcal{L}$ satisface los axiomas AI1, AI2, AI3 y AI4. Si asumimos que los demás axiomas se cumplen por vacuidad, entonces el par $(\mathbb{E},\mathcal{L})$ es una geometría de incidencia.

Ejemplo 2. Considere el conjunto $\mathbb{E}=\{A, B, C, D\}$, la familia de rectas $\mathcal{L}=\{\{A,B\},\{A,C\}, \{A, D\}, \{B, C\}, \{B, D\}, \{C, D\}\}$ y la familia de planos definidos por $\mathcal{P}=\{\{A, B, C\}, \{A, B, D\}, \{A, C, D\}, \{B, C, D\}\}$. En esta ejemplo, el lector podrá verificar que $\mathbb{E}$, $\mathcal{L}$ y $\mathcal{P}$ satisface todos los axiomas de una geometría de incidencia.

Ahora que el lector ha entendido los ejemplos 1 y 2, ya está en la capacidad de resolver las siguientes preguntas: ¿Es posible en el conjunto $\mathbb{E}=\emptyset$ definir una geometría de incidencia? ¿Y en $\mathbb{E}=\{\emptyset\}$?

Para los lectores más atrevidos, les sugiero pensar en el siguiente problema, el cual involucra algunos aspectos de combinatoria:

Problema 1. Considere un conjunto finito $\mathbb{E}=\{A_{1}, \cdots, A_{n+1}\}$. ¿De cuántas formas se puede definir las familias de rectas y planos de tal forma que $(\mathbb{E}, \mathcal{P}, \mathcal{L})$ sea una geometría de incidencia?

Ejemplo 3. Geometría Incidencia Clásica. Considere a $\mathbb{E}$ como un «lienzo infinito plano» donde los puntos son todas las posibles posiciones sobre el lienzo y las rectas será todos los «trazos» definidos por una «regla infinita». Bajo esta interpretación, podemos entender cada uno de los axiomas de la siguiente manera:

1. Axioma AI1. Cualquier par de puntos distintos pertenecen a una única recta. Para representar este axioma en terminos del lienzo y los trazos infinitos, se consideran inicialmente dos posiciones $A$ y $B$ del lienzo como los puntos $A$ y $B$ por los que mediante una «regla» se traza una «trazo infinito». Para indicar que la recta se extiende infinitamente se agregan flechas en los extremos tal como se puede apreciar en la siguiente figura:

1. Axioma AI2. Para toda recta, existe al menos dos puntos distintos que pertenecen a ella. En este caso, se considera inicialmente una recta y luego de ella se pueden seleccionar dos puntos $A$ y $B$ distintos tal como se puede apreciar a continuación:

• Axioma AI3. Para cualquier tripleta de puntos distintos, tales que no pertenecen simultáneamente a ninguna recta, pertenecen a un único plano. Considere inicialmente tres puntos $A$, $B$, $C$ distintos, este axioma afirma que existe único plano o «lienzo» que los contiene. En este caso el plano es el conjunto $\mathbb{E}$ que se ha definido como un lienzo infinito. En la siguiente figura, el plano se representa como un rectángulo de bordes redondeados, es importante aclarar que se extiende infinitamente.

• Axioma AI4. Para todo plano, existe al menos tres puntos distintos que pertenecen a él y no pertenecen simultaneamente a ninguna recta. En este caso, en $\mathbb{E}$ existe tres puntos $A$, $B$, $C$ distinto y que no pertenecen simultaneamente a ninguna recta.

• Axioma AI5. Si un plano y una recta tienen al menos dos puntos en común, entonces la recta está contenida en el plano. El lector podrá estar de acuerdo en que este axioma se cumple trivialmente ¿o tal vez no?

En cuanto a los axiomas AI5, AI6 y AI7 se asumen por obviedad, sin embargo el conjunto $\mathbb{E}$ podría ser modificado para que existe una familia de planos o lienzos. ¿Podrías hacer esta modificación?

En los siguientes ejemplos se verá una definición más formal de este ejemplo.

Ejemplo 4. Considere al espacio $\mathbb{E}$ como el conjunto $\mathbb{R}^{2}$ de los pares ordenados de números reales. Entonces las rectas son los conjuntos de la forma $\lambda_{_{(a, b, c)}}=\{(x,y)\in \mathbb{E}^{2}: ax+by=c\}$ con $a$, $b$ reales y no todos nulos. Este ejemplo tiene muchas similaridades con el ejemplo anterior.

Ejemplo 5. Considere el espacio $\mathbb{E}$ como el conjunto de las tripletas ordenadas de número reales. Los planos son los conjuntos $\pi_{_{(a, b, c, d)}}=\{(x,y,z)\in \mathbb{E}^{3}: ax+by+cz+d =0\}$ con $a$, $b$, $c$ reales y no todos nulos y las rectas son la intersección de dos planos $\pi_{_1}=\{(x,y,z)\in \mathbb{E}^{3}: a_{_1}x+b_{_1}y+c_{_1}z+d_{_1} =0\}$ y $\pi_{_2}=\{(x,y,z)\in \mathbb{E}^{3}: a_{_2}x+b_{_2}y+c_{_2}z+d_{_2} =0\}$, siempre que la tripleta $(a_{_1}, b_{_1}, c_{_1})$ no sea un múltiplo de la tripleta $(a_{_2}, b_{_2}, c_{_2})$.Este ejemplo se puede considerar como una extensión del ejemplo anterior.

Los siguente ejemplos permiten entender que en una geometría de incidencia las rectas no siempre son las nociones intuitivas usuales.

Ejemplo 6. Considere el espacio $\mathbb{E}$ como el conjunto $\mathbb{H}^{2}=\{(x,y)\in\mathbb{R}^{2}:y>0\}$. Hay dos tipos de rectas, las verticales dadas por $l_{_a}=\{(x,y)\in \mathbb{H}^{2}:x=a\}$ con $a$ un número real y los arcos definidos por $l_{_{p,r}}=\{(x,y)\in \mathbb{H}:(x-p)^{2}+y^{2}=r^{2}\}$ con $p$, $r$ números reales. Te reto a hacer una interpretación gráfica de este ejemplo y probar que es una geometría de incidencia de dimensión dos.

Ejemplo 7. Considere el conjunto $\mathbb{H}^{3}=\{(x,y,z)\in \mathbb{R}^{3}:z>0\}$ como el conjunto de puntos. Los planos son de dos tipos, los planos verticales dados por $\pi_{_{(a, b, c)}}=\{(x,y,z)\in \mathbb{H}:ax+by+c=0\}$ con $a$, $b$, $c$ reales no todos nulos y los semiesféricos $\pi_{_{(p, q, r)}}=\{(x,y,z)\in \mathbb{H}:(x-p)^{2}+(y-q)^{2}+z^2=r^2\}$ con $p$, $q$ y $r$ números reales y las rectas son la intersección de dos de estos planos, resultando también dos tipos de rectas, las verticales y las semiesféricas.

Los principales resultados de esta teoria son los siguientes:

Teorema 1. Punto exterior a una recta. En una geometría de incidencia, para toda recta contenida en un plano, existe al menos un punto del plano dado que no pertenece a ella.

En efecto si $l$ es una recta y $\pi$ es un plano tales que $l\subset \pi$. Por el axioma AI2 existe dos puntos $A$, $B$ distintos tales que $A, B\in l$ y por lo tanto $A, B\in \pi$. Finalmente por el axioma AI3 debe existir un tercer punto $C\in \pi$ tal que $C\notin l$ lo que confirma el teorema.

Teorema 2. Intersección de rectas. Dos rectas distintas en una geometría de incidencia tienen como máximo un punto en común.

Si se consideran a $\lambda_{1}, \lambda_{2}$ como dos rectas diferentes del espacio. Si se supone que se cortan en más de un punto, entonces por el axioma AI1 ellas tienen que ser iguales. Es muy imporante que el lector hace énfasis en la unicidad de la recta que pasan por cualquier par de puntos.

Teorema 3. Colinealidad. En una geometría de incidencia, si $A$, $B$ son puntos de una recta $\lambda$ y $C$ es un punto exterior a $\lambda$, entonces los puntos $A, B, C$ no son colineales.

Si $A$, $B$, $C$ fueran colineales existiría una recta $\gamma$ tal que $A, B, C\in \gamma$ y por el axioma AI1 se concluye que $\gamma =\lambda$, esto quiere decir que $C\in \lambda$ lo que contradice la hipótesis del teorema. Por lo tanto $A$, $B$, $C$ no son colineales.

Teorema 4. Coplanaridad de rectas. En un geometría de incidencia, si dos rectas tiene un punto en común, entonces existe un único plano que las contiene.

Sean $l$ y $m$ dos rectas diferentes que se cortan. Sea $A$ el punto de intersección (Teorema de la intercepción de rectas). Por el axioma AI2 existen otro punto $B$ diferente de $A$ en $l$ y otro punto $C$ diferente de $A$ en $m$. Luego $A, B, C$ son no colineales ya que $B$ no está en la recta $m$ y $C$ no está en la recta $l$. Entonces por el axioma AI3, los puntos $A, B,C$ determinan un plano único. Por el axioma AI5 las rectas $l$ y $m$ están contenidas en ese plano. Este es el único plano que las contiene. Si existiera otro, $A, B, C$ estarán en él, contradiciendo el axioma AI3.

Teorema 5. Si $l_{_1}$ y $l_{_2}$ son rectas en una geometría de incidencia y $l_{_1}\cap l_{_2}$ tiene dos o más puntos distintos en común, entonces $l_{_1}=l_{_2}$.

¿Cómo se demostraría este teorema?

Definición 1. Se dirá que dos rectas son paralelas si son iguales o bien ambas están contenidas en un mismo plano y no tienen puntos en común. Si dos rectas no tienen puntos en común, pero no están contenidas en el mismo plano, se dirá que se cruzan. La única alternativa a estos casos es que las rectas tengan un único punto en común, en cuyo caso se dice que son secantes.

Los siguientes teoremas se sugierene como ejercicios para el lector:

Teorema 6. En una geometría de incidencia, dados un plano y una recta, o bien no tienen puntos comunes, o bien tienen un único punto en común, o bien la recta está contenida en el plano.

Teorema 7. En una geometría de incidencia, una recta y un punto exterior a ella están contenidos en un único plano

Teorema 8. En una geometría de incidencai, dos planos no paralelos en una geometría de incidencia se cortan en una única recta.

Bibliografía¶

1. Jaime Escobar Acosta. 1992. Elementos de geometría. Universidad de Antioquia.
2. David Hilbert. 1950. The Foundations of Geometry. University of Göttingen.
3. Carlos Ivorra Castillo. 2013. Geometría. Universidad de Valencia.
4. John Haas. 2018. What is a geometry?
5. Gerard A. Venema. 2016. Exploring Advanced Euclidean Geometry with GeoGebra.
6. Ian Biringer. 2015. Euclidean and Non-Euclidean Geometry.
7. Millman and Parke. Geometry: A Metric Approach with Models.

Contacto¶

• Participa de la canal de Nerve a través de Discord.
• Se quieres conocer más acerca de este tema me puedes contactar a través de Classgap.

Read More

Sistema formal MIU - Acertijo MU

En esta ocasión se hará una breve introdución a el acertijo $MU$; el cual representa un pequeño sistema formal. Este acertijo fue planteado por Hofstadter en 1979 en su libro Godel, Escher, Bach. An Eternal Golden Braid. El objetivo del acertijo propuesto por Hofstadter es producir la cadena MU (de ahí su nombre de Acertijo $MU$) dentro de un sistema formal conocido como el sistema $MIU$; el nombre del sistema se toma del hecho de que sólo emplea tres letras del alfabeto: $M$, $I$, $U$. Esto significa que las cadenas del sistema $MIU$ estarán formadas exclusivamente por esas tres letras. Para comenzar, el sistema $MIU$ parte de una cadena inicial, la cadena $MI$, es decir, $MI$ es el único axioma del sistema en cuestión. Las cadenas que sean producidas deberán conseguirse aplicando las reglas que se mencionan a continuación:

• Regla 1. Si se tiene una cadena cuya última letra sea $I$, se le puede agregar una $U$ al final. Dicho en otras palabras, si $xI$ es un teorema, también lo es $xIU$. En este caso $x$ representa cualquier cadena arbitraria. Por ejemplo, si se tiene la cadena $MII$, entonces se puede obtener $MIIU$.

• Regla 2. Suponga que $Mx$ es un teorema. En tal caso también $Mxx$ es un teorema. Por ejemplo, si se tiene la cadena $MIU$ se puede obtener la cadena $MIUIU$.

• Regla 3. Si en una de las cadenas de la colección aparece la secuencia $III$, puede elaborarse una nueva cadena sustituyendo $III$ por $U$. Por ejemplo, si se tiene la cadena $UMIIIMU$ se puede elaborar $UMUMU$. Observe que las tres $III$ deben ser consecutivas.

• Regla 4. Si aparece $UU$ en el interior de una de las cadenas, está permitida su eliminación. Por ejemplo, dado $MUUUIII$ se puede obtener $MUIII$.

Un primer intento para resolver este acertijo, es proceder a generar de manera manual algunas cadenas, como primer paso, se observa que a partir de el axioma $MI$ y aplicando las reglas, se pueden obtener las siguientes cadenas:

1. $MIU$
2. $MII$

La primera cadena se obtiene después de aplicar la regla 1, y la segunda, casualmente después de aplicar la regla 2. Es posible observar que no se pueden aplicar las reglas 3 y 4 a $MI$.

Después se tiene que ver qué cadenas se pueden generar de $MIU$ y cuáles de $MII$. De $MIU$ solo es posible generar $MIUIU$; sin embargo, de $MII$ se pueden generar $MIIU$ y $MIIII$. Si se sigue aplicando este proceso, se tendrá que buscar qué cadenas ahora se pueden formar de $MIUIU$, $MIIU$ y $MIII$, y seguir así secuencialmente hasta que en alguna de esas generaciones se encuentre la cadena $MU$.

De lo anterior se puede deducir que, esta búsqueda nos lleva a la generación de un árbol de teoremas como el mostrado en la Figura 1 , y como puede observarse, cada nodo puede tener una cantidad variada de hijos. En un principio, se podría pensar que cada nodo solo puede tener a lo máximo cuatro hijos, pero si se analiza detenidamente el problema, se puede llegar a la conclusión de que no necesariamente será así, por ejemplo, de la cadena $MIIIIIIIU$ aplicando solamente la regla 3 se pueden obtener las siguientes cadenas:

1. $MUIIIIU$
2. $MIUIIIU$
3. $MIIUIIU$
4. $MIIIUIU$
5. $MIIIIUU$

De aquí se deduce que el número de hijos de cada nodo es variable y puede ser muy grande.

Para facilitar el ejercicio se puede hacer uso de algún lenguaje de programación como por ejemplo python y hacer una codificación de las reglas del sistema formal MIU, algo como lo que se muestra a continuación:

In [1]:

import re
class MIU:
    
    def __init__(self):
        # Definition of the primary chain.
        self.state = 'MI'
    
    def get_state(self):
        # Check the game status.
        return self.state
    
    def reset(self):
        # Restart the game state. 
        self.state = 'MI'
        
    def rule_one(self):
        # Definition of rule one of the MIU system.
        if self.state[-1] == 'I':
            
            self.state = self.state + 'U'
            
        else:
            
            print('Can not use this rule...')
            
        return self.state
    
    def rule_two(self):
        # Definition of rule two of the MIU system.
        self.state = self.state + self.state[1:]
        
        return self.state
    
           
    def rule_three(self):
        # Definition of rule three of the MIU system.
        word = self.state
        result = re.finditer(r'(?=(III))', word)  
        
        words = dict()
        for i, j in enumerate(result):
            slices = [word[:j.start(1)], word[j.end(1):]]
            chain = 'U'.join(slices)
            words[i] = chain
            print('Option {}:'.format(i), new_chain)
            
        if words.keys():  
            
            option = int(input('Choose an option: '))
            self.state = words.get(option)
            
        else:
            
            print('Can not use this rule...')
        
        return self.state
    
    
    def rule_four(self):
        # Definition of rule four of the MIU system.
        word = self.state
        result = re.finditer(r'(?=(UU))', word) 
            
        words = dict()
        for i, j in enumerate(result):
            new_chain = word[:j.start(1)] + word[j.end(1):]
            words[i] = new_chain
            print('Option {}:'.format(i), new_chain)
            
        if words.keys():
        
            option = int(input('Choose an option: '))
            self.state = words.get(option)
            
        else:
            
            print('Can not use this rule...')
        
        return self.state    

Para utilizarlo, solo tienes que hacer una instancia del clase MIU:

In [2]:

game = MIU()

Luego sería usar cada uno de los métodos de la clase:

• rule_one(), rule_two(), rule_three() y rule_four() para hacer uso de cualquiera de las reglas del sistema MIU.
• get_state() para ver el estado del juego.
• reset() para reiniciar el juego.

A continuación algunos ejemplos del uso:

In [3]:

game.rule_one()

Out[3]:

'MIU'

In [4]:

game.rule_one()

Can not use this rule...

Out[4]:

'MIU'

In [5]:

game.rule_four()

Can not use this rule...

Out[5]:

'MIU'

In [6]:

game.rule_two()

Out[6]:

'MIUIU'

In [7]:

game.rule_two()

Out[7]:

'MIUIUIUIU'

In [8]:

game.reset()

In [9]:

game.get_state()

Out[9]:

'MI'

Finalmente, la pregunta es ¿Puedes encontrar MU? ¿Puedes construir un nuevo algoritmo que permita decidir si una cadena $x$ es demostrable dentro del sistema MIU? ¿Qué quiere decir que una cadena es demostrable en MIU? Espero seguir discutiendo estas preguntas en el futuro, por ahora les recomiendo que se pasen por la referencia que motivo esta entrada.

Referencias¶

• Hofstadter. 1979. Godel, Escher, Bach. An Eternal Golden Braid.

Read More