El algoritmo de Prim

Considere un grafo $G$ conexo y no dirigido, se dice que un árbol generador es un subgrafo que contiene todos los vértices de $G$. En un grafo ponderado, el peso de un subgrafo es la suma de los pesos de cada una de las aristas en el subgrafo. Así, un árbol generador mínimo (MST por sus siglas en inglés) es un subgrafo ponderado no dirigido que es un árbol generador con peso mínimo.

Hay muchos problemas en los que se requiere hallar un MST de un grafo no dirigido. Por ejemplo, la longitud mínima del cable necesaria para conectar un conjunto de computadores en una red, puede ser determinada por un MST del grafo no dirigido que contiene todas las posibles conexiones.

El Algoritmo de Prim, es el primero y el más sencillo de los algoritmos de la teoría de grafos para encontrar un árbol generador mínimo en un grafo ponderado, conexo y no dirigido, este problema se conoce como el problema del árbol generador mínimo. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible.

Este algoritmo fue desarrollado por primera vez por el matemático checo Vojtêch Jarník, no sería hasta más tarde, en 1957, cuando aparecería publicado de forma independiente bajo la autoría del ingeniero informático estadounidense Robert C. Prim. Es él quien le dio fama y por cuyo apellido es hoy conocido. Creado durante su etapa en Bell Labs, Prim trataba de abordar el problema de cómo conectar redes, ya fueran de telecomunicaciones o de transporte y distribución, mediante un número reducido o barato de conexiones.

¿Cómo funciona el algoritmo Prim?¶

La solución al problema del árbol generador propuesta por Prim se basa en la idea de ir conectando vértices secuencialmente hasta alcanzarlos a todos. Si se tiene como dato de entrada un grafo no dirigido $G=(V, A, W)$, donde $V$ son los vértices, $A$ las aristas y $W$ la matriz de pesos. El algoritmo empieza a construir el árbol a partir de un vértice seleccionado arbitrariamente como punto de inicio. A continuación se itera seleccionando en cada etapa la arista de menor peso (una cualquiera si hay varias posibilidades) que une un vértice del árbol con otro que aún no está en él; luego se incorpora dicha arista y el vértice de destino al árbol. El proceso se repite hasta añadir todos los vértices, obteniendo como resultado un árbol generador cuyo peso será mínimo.

El algoritmo podría ser informalmente descrito siguiendo los siguientes pasos:

1. Inicializar un árbol $T$ con un único vértice, elegido arbitrariamente del grafo $G$.
2. Aumentar el árbol por una arista. Encontrar la arista de menor costo de las posibles aristas que pueden conectar el árbol a los vértices que no están aún en el árbol y agregarla al árbol.
3. Repetir el paso 2 hasta que todos los vértices del grafo pertenezcan al árbol.

Con más detalle, se debe implementar el siguiente pseudocódigo:

Algoritmo de Prim

Input: $G=(V, A, W), s\in V$ 

1.     $V^{\top}\leftarrow \{s\}$ 

2.     $A^{\top}\leftarrow \emptyset$ 

3.     while $card(V^{\top}) < card(V)$ do: 

4.          $\displaystyle (i, j)=\operatorname*{argmin\,\,}_{(i, j)}\{w_{ij}:i\in V^{\top}, j\in V\setminus V^{\top}\}$ 

5.           $A^{\top} \leftarrow A^{\top}\cup\{(i, j)\}$ 

6.           $V^{\top} \leftarrow V^{\top}\cup\{j\}$ 

8.     end 

return: $T$, $V(T)\leftarrow V^{\top}$, $A(T)\leftarrow A^{\top}$.

Ejemplo¶

En la figura 1 se ilustra la ejecución del algoritmo de Prim sobre un grafo $G$. Se empieza por el vértice $v_{_0}$. Dado que $(v_{_0},v_{_1})$ es la arista de peso mínimo que incide sobre $v_{_0}$, se incluye en el árbol generador que se está construyendo (figura 1a). En la figura 1a , se añade la arista $(v_{_1}, v_{_5})$ porque es la arista más pequeña entre $\{v_{_0}, v_{_1}\}$ y $V(G)\setminus \{v_{_0}, v_{_1}\}$. Cuando hay un empate, como en la figura 1c, cualquier arista más pequeña podría funcionar bien. Se procede de esta forma hasta que se pasa por todos los vértices. El árbol generador mínimo definitivo se muestra en la figura 1f.

La complejidad de tiempo del algoritmo de Prim depende de las estructuras de datos usada para el grafo y para ordenar las aristas por peso, lo que se puede hacer usando una cola de prioridad. La siguiente muestra las opciones típicas:

1. Para una matriz de adyacencia y un algoritmo de busqueda clásico la complejidad de ejecución es del orden de $O(\operatorname*{card\,\,}(V)^{2})$.
2. Para una pila binaria y una lista de adyacencia la complejidad de ejecución es del orden de $O((\operatorname*{card\,\,}(V)+\operatorname*{card\,\,}(E))\log\operatorname*{card\,\,}(V))$.
3. Para una pila de Fibonacci y una lista de adyacencia la complejidad de ejecución es del orden de $O(\operatorname*{card\,\,}(E) + \operatorname*{card\,\,}(V)log(\operatorname*{card\,\,}(V))$.

¿Cómo se implementa en Python el algoritmo de Prim?¶

Una forma de implementar el algoritmo de Prim es así:

In [1]:

import numpy as np
import timeit

In [2]:

from graphs import NotOrientedGraph
from graphs import Vertex

El módulo graph contiene la estructura de datos utilizada para el grafo y la puedes encontrar en el repositorio de Nerve. El resto del algoritmo es:

In [3]:

def prim(graph: NotOrientedGraph, initial_vertex: Vertex) -> NotOrientedGraph:
    """
    Input:
        graph: It's a graph not oriented and connected.
        initial_vertex: It's one vertex from graph.
    Output:
        The return is a graph not oriented and connected.
    """
    # Initialize empty edges array and empty minimum spanning tree:
    minimum_spanning_tree = dict()
    visited_vertices = list()
    edges = list()
    min_edge = (None, None, np.infty)
    # Arbitrarily choose initial vertex from graph:
    vertex = initial_vertex
    # Indices:
    start_vertex, end_vertex, weight = range(3)
    # Run prim's algorithm until we create an minimum spanning tree that
    # contains every vertex from the graph:
    
    try:
        while len(visited_vertices) < graph.num_vertices - 1:
            # Mark this vertex as visited:
            visited_vertices.append(vertex)
            # Set of potential edges:
            edges += vertex.edges
            # Find edge with the smallest weight to a vertex that has not yet
            # been visited:
            for edge in edges:
                inequality = edge[weight] < min_edge[weight]
                membership = edge[end_vertex] not in visited_vertices
                if inequality and membership:
                    min_edge = edge
            # Get the start and end node from minimum edge:
            start_min_edge = min_edge[start_vertex]
            end_min_edge = min_edge[end_vertex]
            min_weight = min_edge[weight]
            # Add the minimum edge to minimum spanning tree:
            if minimum_spanning_tree.get(start_min_edge.id):
                edge = (end_min_edge.id, min_weight)
                minimum_spanning_tree[start_min_edge.id].append(edge)
            else:
                edge = [(end_min_edge.id, min_weight)]
                minimum_spanning_tree[start_min_edge.id] = edge
            # Remove min weight edge form list of edges:
            edges.remove(min_edge)
            # Start at new vertex and reset min edge:
            vertex = end_min_edge
            min_edge = (None, None, np.infty)
            
    except Exception as e:
        print('The graph is not connected or has no edges!')
    # Return the optimal tree:
    return NotOrientedGraph(minimum_spanning_tree)

Para usar el algoritmo de Prim es necesario tener un grafo no orientado que podemos construir de la siguiente manera:

In [4]:

data = {
    'a': [('c', 0)], 
    'b': [('c', 1), ('e', 3)], 
    'c': [('a', 3), ('b', 3), ('d', 2), ('e', 1)]
}

In [5]:

graph = NotOrientedGraph(data)

La clase NotOrientedGraph tiene varios métodos que permite consultar algunas de las propiedades de nuestro grafo, a continuación veamos algunos ejemplos:

In [6]:

graph.get_vertices()

Out[6]:

['a', 'c', 'b', 'e', 'd']

In [7]:

graph.get_edges()

Out[7]:

([('a', 'c', 0),
  ('c', 'a', 3),
  ('c', 'd', 2),
  ('c', 'b', 3),
  ('c', 'e', 1),
  ('b', 'e', 3)],
  ('b', 'c', 1),
 graphs.NotOrientedGraph)

In [8]:

graph.weight_matrix()

Out[8]:

(matrix([[inf,  0., inf, inf, inf],
         [ 3., inf,  3.,  1.,  2.],
         [inf, inf, inf, inf, inf],
         [inf,  1., inf,  3., inf],
 ['a', 'c', 'b', 'e', 'd'])
         [inf, inf, inf, inf, inf]]),

In [9]:

graph.adjacency_matrix()

Out[9]:

(matrix([[0, 1, 0, 0, 0],
         [1, 0, 1, 1, 1],
         [0, 0, 0, 0, 0],
         [0, 1, 0, 1, 0],
 ['a', 'c', 'b', 'e', 'd'])
         [0, 0, 0, 0, 0]]),

Además también se necesita de un vértice inicial que para nuestro ejemplo será:

In [10]:

initial_vertex = graph.get_vertex('a')

Al ejecutar el algoritmo de Prim se obtiene un nuevo grafo conexo y no orientado:

In [11]:

tree = prim(graph, initial_vertex)

Para nuestro ejemplo, se peude verificar que en efecto el grafo obtenido pasa por todos los vertices y además también nos entrega cuales son la arista que se usando para construirlo.

In [12]:

tree.get_vertices()

Out[12]:

['a', 'c', 'e', 'd', 'b']

In [13]:

tree.get_edges()

Out[13]:

([('a', 'c', 0), ('c', 'e', 1), ('c', 'd', 2), ('c', 'b', 3)],
 graphs.NotOrientedGraph)

¿Por qué funciona el algoritmo de Prim?¶

A continuación vamos a establecer el siguiente resultado:

---

Teorema. Sea $G$ un grafo conexo, no orientado y ponderado. Entonces al aplicar el algoritmo de Prim desde cualquier vértice se obtiene un árbol de expansión con costo mínimo.

---

Como $G$ es un grafo conexo entonces siempre es posible encontrar una camino $r$ que une a cualquier par de vértices de $G$. Observe que para la $k$ - ésima iteración del algoritmo de Prim el subgrafo $T_{_k}$ es conexo, no orientado y ponderado. Es fácil ver ue cada par de vértices de $T_{_k}$ está conectado por exactamente un camino. Además es claro que existe una $n$ - ésima iteración, $n < \operatorname*{card\,\,}(V(G))$, donde $T_{_n}$ es un grafo que contiene todo los vértices de $G$, es decir $V(T_{_n}) )= V(G)$. Es claro que $T_{_n}$ es un árbol.

¿Es $T_{_n}$ un árbol de expansión con costo mínimo para el graho $G$? Suponga que $Y_{_1}$ es un árbol de expansión con costo mínimo para el grafo $G$. Si $T_{_n} = Y_{_1}$ entonces $T_{_n}$ es un árbol mínimo. Por otro lado si $T_{_n} \neq Y_{_1}$, entonces considera la $k$ - ésima iteración del algoritmo de Prim donde se agregó la primera arista $e$ al subgrafo $T_{_{k-1}}$ que no está en $Y_{_1}$. Observe que uno de los extremos de $e$ esta en $V(T_{_{k-1}})$ y el otro no. Como $Y_{_1}$ es un árbol de expansión con costo mínimo de $G$, entonces existe un camino $r$ en $Y_{_1}$ que une los extremos de $e$. En el camino $r$ debe existir una arista $f$ que une al subgrafo $T_{_{k-1}}$ con algún vértice que no está en $V(T_{_{k-1}})$. Observe que en la $k$ - ésima iteración en donde se agregó $e$ también era posible agregar $f$ en vez de $e$ si y sólo si el peso $w(f)$ de $f$ era menor o igual al peso $w(e)$ de $e$, como $f$ no se agregó se concluye que $w(f)\geq w(e)$.

Sea $Y_{2}$ es grafo tal que $A(Y_{_2}) = (A(Y_{_1})\setminus\{f\})\cup \{e\}$, es decir, el grafo que resulta de remover de $Y_{_1}$ la arista $f$ y agregar la arista $e$. Es fácil ver que $Y_{_2}$ es conexo, tiene el mismo número de vértices que $Y_{_1}$ y su costo total no supere al coso total de $Y_{_1}$, por lo tanto $Y_{_2}$ también es un árbol de expansión con costo mínimo de $G$ que contiene a $e$ y a todas las aristas de $T_{_{k-1}}$. Repitiendo este mismo proceso para $Y_{2}$, buscamos la $k$ - ésima iteración en el algoritmo de Prim donde se haya agregado una arista que está en $T_{_{k-1}}$ pero no está en $Y_{_2}$, eventualmente se encontrará un árbol de expansión con costo mínimo para $G$ que será igual a $T_{_n}$. Esto prueba que el árbol obtenido por el algoritmo de Prim es un árbol de expansión con costo mínimo.

Conclusiones¶

Una implementación simple de Prim, usando una matriz de adyacencia o una representación del grafo en una lista de adyacencia y buscando linealmente una matriz de pesos para encontrar el borde de peso mínimo para agregar, requiere un tiempo de ejecución de $O( \operatorname*{card\,\,}(V)^2)$. Sin embargo, este tiempo de ejecución se puede mejorar mucho más mediante el uso de pilas para implementar la búsqueda de aristas de peso mínimo en el bucle interno del algoritmo.

Una primera versión mejorada usa una pila para almacenar todos las del grafo de entrada, ordenados por su peso. Esto conduce a un tiempo de ejecución en el peor de los casos de $O ( \operatorname*{card\,\,} (E) \log \operatorname*{card\,\,}(E))$. Pero almacenar vértices en lugar de arista puede mejorarlo aún más. La pila debe ordenar los vértices por el peso de borde más pequeño que los conecte a cualquier vértice en el árbol de expansión mínimo parcialmente construido (MST) (o infinito si no existe tal arista). Cada vez que se elige un vértice $v$ y se agrega al MST, se realiza una operación de disminución de clave en todos los vértices $w$ fuera del MST parcial de manera que $v$ está conectado a $w$, estableciendo la clave al mínimo de su valor anterior y el costo de la arista de $(v, w)$.

Usando una estructura de datos de pila binaria simple, ahora se puede mostrar que el algoritmo de Prim se ejecuta en el tiempo $O ( \operatorname*{card\,\,}(E) \log \operatorname*{card\,\,}( V))$ donde $ \operatorname*{card\,\,}(E)$ es el número de aristas y $\operatorname*{card\,\,}(V)$ es el número de vértices. Usando una pila de Fibonacci más sofisticada, esto se puede reducir a $O ( \operatorname*{card\,\,}( E) + \operatorname*{card\,\,}( V ) \log \operatorname*{card\,\,}( V ))$, que es asintóticamente más rápido cuando el grafo es lo suficientemente denso que $\operatorname*{card\,\,}( E)$ es $\omega ( \operatorname*{card\,\,}(V))$, y el tiempo lineal cuando $\operatorname*{card\,\,}( E)$ es al menos $ \operatorname*{card\,\,}( V ) \log \operatorname*{card\,\,}( V )$. Para grafos de densidad aún mayor (que tienen al menos $c\operatorname*{card\,\,}( V )$ aristas con $c> 1$), se puede hacer que el algoritmo de Prim se ejecute en tiempo lineal de manera aún más simple, utilizando una pila d-aria en lugar de una pila de Fibonacci.

No olvides comentar y suscribirte al blog para que estés enterando de los posts que voy a ir subiendo semana a semana. También sientete en libertad de seguirme en Twitter, Github e Instagram.

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

Á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