"La ley distributiva en matemáticas es la ley que relaciona las operaciones de multiplicación y suma, expresada simbólicamente, ; es decir, el factor monomio se distribuye, o se aplica por separado, a cada término del factor binomial , resultando en el producto " - Britannica [2]
Como se puede observar en la definición, la aplicación de la ley distributiva a una expresión aritmética reduce el número de operaciones en ella. En el ejemplo anterior, el número total de operaciones se redujo de tres (dos multiplicaciones y una suma en) a dos (una multiplicación y una suma en ). La generalización de la ley distributiva conduce a una gran familia de algoritmos rápidos . Esto incluye el algoritmo FFT y Viterbi .
Esto se explica de una manera más formal en el siguiente ejemplo:
dónde y son funciones de valor real, y (decir)
Aquí estamos "marginando" las variables independientes (, , y ) para obtener el resultado. Cuando calculamos la complejidad computacional, podemos ver que para cada pares de , existen términos debidos al triplete que necesita participar en la evaluación de cada paso tiene una suma y una multiplicación. Por lo tanto, el número total de cálculos necesarios es. Por tanto, la complejidad asintótica de la función anterior es.
Si aplicamos la ley distributiva al RHS de la ecuación, obtenemos lo siguiente:
Esto implica que se puede describir como un producto dónde y
Ahora, cuando estamos calculando la complejidad computacional, podemos ver que hay adiciones en y cada uno y hay multiplicaciones cuando estamos usando el producto para evaluar . Por lo tanto, el número total de cálculos necesarios es. De ahí la complejidad asintótica de calcular reduce a de . Esto muestra con un ejemplo que la aplicación de la ley distributiva reduce la complejidad computacional, que es una de las buenas características de un "algoritmo rápido".
Historia
Algunos de los problemas que utilizaron la ley distributiva para resolver se pueden agrupar de la siguiente manera
1. Algoritmos de decodificación Gallager utilizó un algoritmo similar a GDL para decodificar códigos de verificación de paridad de baja densidad. Basado en el trabajo de Gallager, Tanner introdujo el gráfico de Tanner y expresó el trabajo de Gallager en forma de transmisión de mensajes. El gráfico de los curtidores también ayudó a explicar el algoritmo de Viterbi .
Forney observa que la decodificación de máxima verosimilitud de códigos convolucionales de Viterbi también utilizó algoritmos de generalidad similar a GDL.
MPF o marginar una función de producto es un problema computacional general que, como caso especial, incluye muchos problemas clásicos como el cálculo de la transformada discreta de Hadamard , la decodificación de máxima verosimilitud de un código lineal sobre un canal sin memoria y la multiplicación de la cadena de matrices . El poder del GDL radica en el hecho de que se aplica a situaciones en las que se generalizan las sumas y multiplicaciones. Un semiring conmutativo es un buen marco para explicar este comportamiento. Se define sobre un conjunto con operadores "" y "" dónde y son monoides conmutativos y se cumple la ley distributiva.
Dejar ser variables tales que dónde es un conjunto finito y . Aquí. Si y , dejar , , , , y
Dejar dónde . Supongamos que una función se define como, dónde es un semirrendado conmutativo . También,se denominan los dominios locales ycomo los núcleos locales .
Ahora el kernel global Se define como :
Definición de problema de MPF : para uno o más índices, calcula una tabla de los valores de - marginación del núcleo global, que es la función definido como
Aquí es el complemento de con respecto a y el se llama el función objetivo , o la función objetivo en. Se puede observar que el cálculo de la función objetiva de la manera obvia necesita operaciones. Esto es porque hay adiciones y multiplicaciones necesarias en el cálculo de la función objetiva. El algoritmo GDL que se explica en la siguiente sección puede reducir esta complejidad computacional.
El siguiente es un ejemplo del problema de MPF. Dejar y ser variables tales que y . Aquí y . Las funciones dadas que utilizan estas variables son y y necesitamos calcular y definido como:
Aquí los dominios locales y los núcleos locales se definen de la siguiente manera:
dominios locales
núcleos locales
dónde es el función objetivo y es el función objetiva.
Considere otro ejemplo donde y es una función de valor real. Ahora, consideraremos el problema MPF donde el semiring conmutativo se define como el conjunto de números reales con suma y multiplicación ordinarias y los dominios locales y los núcleos locales se definen de la siguiente manera:
dominios locales
núcleos locales
Ahora, dado que el kernel global se define como el producto de los kernels locales, es
y la función objetivo en el dominio local es
Esta es la transformada de Hadamard de la función. Por tanto, podemos ver que el cálculo de la transformada de Hadamard es un caso especial del problema MPF. Se pueden demostrar más ejemplos para demostrar que el problema MPF forma casos especiales de muchos problemas clásicos como se explicó anteriormente, cuyos detalles se pueden encontrar en [1]
GDL: un algoritmo para resolver el problema de MPF
Si uno puede encontrar una relación entre los elementos de un conjunto dado , entonces se puede resolver el problema de MPF basándose en la noción de propagación de creencias, que es un uso especial de la técnica de "transmisión de mensajes". La relación requerida es que el conjunto dado de dominios locales se puede organizar en un árbol de unión . En otras palabras, creamos un árbol teórico de grafos con los elementos decomo los vértices del árbol, de modo que para dos vértices arbitrarios cualesquiera digamos y dónde y existe un borde entre estos dos vértices, luego la intersección de las etiquetas correspondientes, a saber , es un subconjunto de la etiqueta en cada vértice en la ruta única de a .
Por ejemplo,
Ejemplo 1: considere los siguientes nueve dominios locales:
Para el conjunto de dominios locales dado anteriormente, uno puede organizarlos en un árbol de unión como se muestra a continuación:
De manera similar, si se da otro conjunto como el siguiente
Ejemplo 2: considere los siguientes cuatro dominios locales:
Entonces, construir el árbol solo con estos dominios locales no es posible ya que este conjunto de valores no tiene dominios comunes que puedan colocarse entre dos valores cualesquiera del conjunto anterior. Pero, sin embargo, si agrega los dos dominios ficticios como se muestra a continuación, organizar el conjunto actualizado en un árbol de unión también sería posible y fácil.
5., 6.,
De manera similar, para este conjunto de dominios, el árbol de unión se ve como se muestra a continuación:
Algoritmo de ley distributiva generalizada (GDL)
Entrada: un conjunto de dominios locales. Resultado: Para el conjunto de dominios dado, se calcula el número mínimo posible de operaciones que se requieren para resolver el problema. Así que si y están conectados por un borde en el árbol de unión, luego un mensaje de a es un conjunto / tabla de valores dados por una función: :. Para empezar con todas las funciones, es decir, para todas las combinaciones de y en el árbol dado, se define para ser idénticamente y cuando se actualiza un mensaje en particular, sigue la ecuación que se indica a continuación.
=
dónde significa que es un vértice adyacente a en el árbol.
De manera similar, cada vértice tiene un estado que se define como una tabla que contiene los valores de la función , Del mismo modo que los mensajes se inicializan en 1 de forma idéntica, el estado de se define como kernel local , pero cuando sea se actualiza, sigue la siguiente ecuación:
Funcionamiento básico del algoritmo
Para el conjunto dado de dominios locales como entrada, averiguamos si podemos crear un árbol de unión, ya sea usando el conjunto directamente o agregando dominios ficticios al conjunto primero y luego creando el árbol de unión, si la unión de construcción no es posible, entonces resultado del algoritmo que no hay forma de reducir el número de pasos para calcular el problema de ecuación dado, pero una vez que tengamos el árbol de unión, el algoritmo tendrá que programar mensajes y calcular estados, al hacer esto podemos saber dónde se pueden reducir los pasos, por lo tanto se analiza esto a continuación.
Programación del paso del mensaje y cálculo del estado.
Hay dos casos especiales de los que vamos a hablar aquí, a saber, problema de vértice único en el que la función objetivo se calcula en un solo vérticey el segundo es el problema de todos los vértices, donde el objetivo es calcular la función objetivo en todos los vértices.
Comencemos con el problema de un solo vértice , GDL comenzará dirigiendo cada borde hacia el vértice objetivo. Aquí los mensajes se envían solo en la dirección hacia el vértice objetivo. Tenga en cuenta que todos los mensajes dirigidos se envían solo una vez. Los mensajes se inician desde los nodos hoja (donde el grado es 1) suben hacia el vértice de destino. El mensaje viaja de las hojas a sus padres y luego de allí a sus padres y así sucesivamente hasta llegar al vértice de destino. El vértice de destinocalculará su estado solo cuando reciba todos los mensajes de todos sus vecinos. Una vez que tenemos el estado, tenemos la respuesta y, por lo tanto, el algoritmo termina.
Por ejemplo, consideremos un árbol de unión construido a partir del conjunto de dominios locales dado anteriormente, es decir, el conjunto del ejemplo 1, ahora la tabla de programación para estos dominios es (donde el vértice de destino es).
Por lo tanto, la complejidad de GDL de vértice único se puede mostrar como
operaciones aritméticas Donde (Nota: La explicación de la ecuación anterior se explica más adelante en el artículo) es la etiqueta de . es el grado de (es decir, número de vértices adyacentes av).
Para resolver el problema de todos los vértices , podemos programar GDL de varias maneras, algunas de ellas son implementaciones paralelas donde en cada ronda, cada estado se actualiza y cada mensaje se calcula y transmite al mismo tiempo. En este tipo de implementación, los estados y mensajes se estabilizarán después de un número de rondas que sea como máximo igual al diámetro del árbol. En este punto, todos los estados de los vértices serán iguales a la función objetivo deseada.
Otra forma de programar GDL para este problema es la implementación en serie, donde es similar al problema de vértice único, excepto que no detenemos el algoritmo hasta que todos los vértices de un conjunto requerido no hayan obtenido todos los mensajes de todos sus vecinos y hayan calculado su Expresar. Por lo tanto, el número de aritmética que requiere esta implementación es como máximo operaciones aritmeticas.
Construyendo un árbol de unión
La clave para construir un árbol de unión radica en el gráfico de dominio local , que es un gráfico completo ponderado con vértices es decir, uno para cada dominio local, con el peso del borde definido por . Si, entonces decimos está contenido en. Denotado por (el peso de un árbol de expansión de peso máximo de ), que se define por
donde n es el número de elementos de ese conjunto. Para obtener más claridad y detalles, consulte estos. [3] [4]
Teorema de programación
Dejar ser un árbol de unión con un conjunto de vértices y conjunto de bordes . En este algoritmo, los mensajes se envían en ambas direcciones en cualquier borde, por lo que podemos decir / considerar el conjunto de bordes E como un conjunto de pares ordenados de vértices. Por ejemplo, de la Figura 1 se puede definir de la siguiente manera
NOTA: arriba le da todas las direcciones posibles en las que un mensaje puede viajar en el árbol.
El programa para el GDL se define como una secuencia finita de subconjuntos de. Que generalmente está representado por{}, Dónde es el conjunto de mensajes actualizados durante el ronda de ejecución del algoritmo.
Habiendo definido / visto algunas notaciones, veremos que el teorema dice, cuando se nos da un horario , el enrejado del mensaje correspondiente es un gráfico dirigido finito con un conjunto de vértices de, en el que un elemento típico se denota por por , Luego, después de completar el paso del mensaje, indique en el vértice será el objetivo definido en
y si hay un camino desde a
Complejidad computacional
Aquí intentamos explicar la complejidad de resolver el problema MPF en términos del número de operaciones matemáticas necesarias para el cálculo. es decir, comparamos el número de operaciones necesarias cuando se calcula utilizando el método normal (aquí por método normal nos referimos a métodos que no utilizan el paso de mensajes o árboles de unión en métodos cortos que no utilizan los conceptos de GDL) y el número de operaciones que utilizan la ley distributiva generalizada.
Ejemplo: considere el caso más simple en el que necesitamos calcular la siguiente expresión .
Para evaluar esta expresión ingenuamente se requieren dos multiplicaciones y una suma. La expresión cuando se expresa usando la ley distributiva se puede escribir como una optimización simple que reduce el número de operaciones a una suma y una multiplicación.
De manera similar al ejemplo explicado anteriormente, expresaremos las ecuaciones en diferentes formas para realizar la menor cantidad de operaciones posible aplicando el GDL.
Como se explicó en las secciones anteriores, resolvemos el problema utilizando el concepto de árboles de unión. La optimización obtenida mediante el uso de estos árboles es comparable a la optimización obtenida al resolver un problema de semigrupo en árboles. Por ejemplo, para encontrar el mínimo de un grupo de números podemos observar que si tenemos un árbol y los elementos están todos en la parte inferior del árbol, entonces podemos comparar el mínimo de dos elementos en paralelo y el mínimo resultante será escrito a los padres. Cuando este proceso se propaga por el árbol, el mínimo del grupo de elementos se encontrará en la raíz.
La siguiente es la complejidad para resolver el árbol de unión usando el paso de mensajes
Reescribimos la fórmula utilizada anteriormente en la siguiente forma. Esta es la ecuación para que un mensaje se envíe desde el vértice v hasta w
---- ecuación del mensaje
De manera similar, reescribimos la ecuación para calcular el estado del vértice v de la siguiente manera
Primero analizaremos el problema de un solo vértice y asumiremos que el vértice objetivo es y por lo tanto tenemos una ventaja de a . Supongamos que tenemos una ventajacalculamos el mensaje usando la ecuación del mensaje. Calcular requiere
adiciones y
multiplicaciones.
(Representamos el como .)
Pero habrá muchas posibilidades de por eso posibilidades para . Por lo tanto, todo el mensaje necesitará
adiciones y
multiplicaciones
El número total de operaciones aritméticas necesarias para enviar un mensaje hacia a lo largo de los bordes del árbol será
adiciones y
multiplicaciones.
Una vez que se han transmitido todos los mensajes, el algoritmo termina con el cálculo del estado en El cálculo estatal requiere más multiplicaciones. Por lo tanto, el número de cálculos necesarios para calcular el estado se da a continuación.
adiciones y
multiplicaciones
Por tanto, el gran total del número de cálculos es
----
dónde es un borde y su tamaño está definido por
La fórmula anterior nos da el límite superior.
Si definimos la complejidad del borde como
Por lo tanto, Se puede escribir como
Ahora calculamos la complejidad del borde para el problema definido en la Figura 1 de la siguiente manera
La complejidad total será que es considerablemente bajo en comparación con el método directo. (Aquí por método directo nos referimos a métodos que no utilizan el paso de mensajes. El tiempo que se tarda en utilizar el método directo será el equivalente a calcular el mensaje en cada nodo y el tiempo para calcular el estado de cada uno de los nodos).
Ahora consideramos el problema de todos los vértices donde el mensaje tendrá que enviarse en ambas direcciones y el estado debe calcularse en ambos vértices. Esto tomaría pero al precalcular podemos reducir el número de multiplicaciones a . Aquíes el grado del vértice. Ej: si hay un conjunto con números. Es posible calcular todos los productos d de de El con como máximo multiplicaciones en lugar de lo obvio . Hacemos esto calculando previamente las cantidades y esto toma multiplicaciones. Entonces sí denota el producto de todos excepto por tenemos y así sucesivamente necesitará otro multiplicaciones haciendo el total
No hay mucho que podamos hacer cuando se trata de la construcción del árbol de unión, excepto que podemos tener muchos árboles de expansión de peso máximo y deberíamos elegir el árbol de expansión con el menor ya veces esto podría significar agregar un dominio local para reducir la complejidad del árbol de unión.
Puede parecer que GDL es correcto solo cuando los dominios locales se pueden expresar como un árbol de unión. Pero incluso en los casos en los que hay ciclos y varias iteraciones, los mensajes serán aproximadamente iguales a la función objetivo. Los experimentos con el algoritmo Gallager-Tanner-Wiberg para códigos de verificación de paridad de baja densidad respaldaron esta afirmación.
Referencias
^ a b c Aji, SM; McEliece, RJ (marzo de 2000). "La ley distributiva generalizada" (PDF) . Transacciones IEEE sobre teoría de la información . 46 (2): 325–343. doi : 10.1109 / 18.825794 .
^"ley distributiva" . Encyclopædia Britannica. Encyclopædia Britannica Online . Enciclopedia Británica Inc . Consultado el 1 de mayo de 2012 .
^"Copia archivada" (PDF) . Archivado desde el original (PDF) el 19 de marzo de 2015 . Consultado el 19 de marzo de 2015 .CS1 maint: copia archivada como título ( enlace ) Los algoritmos del árbol de unión
^ Http://www-anw.cs.umass.edu/~cs691t/SS02/lectures/week7.PDF Archivado 2012-05-26 en la Wayback Machine The Junction Algoritmo del árbol