Álgebra de información

Álgebra que describe el procesamiento de la información

El término " álgebra de la información " se refiere a las técnicas matemáticas de procesamiento de la información . La teoría clásica de la información se remonta a Claude Shannon . Es una teoría de la transmisión de la información, que se ocupa de la comunicación y el almacenamiento. Sin embargo, hasta ahora no se ha considerado que la información proviene de diferentes fuentes y que, por lo tanto, suele combinarse. Además, se ha descuidado en la teoría clásica de la información el hecho de que se desea extraer de una pieza de información aquellas partes que son relevantes para preguntas específicas.

La formulación matemática de estas operaciones conduce a un álgebra de la información , que describe los modos básicos de procesamiento de la información. Esta álgebra implica varios formalismos de la informática que parecen diferentes a primera vista: bases de datos relacionales, sistemas múltiples de lógica formal o problemas numéricos de álgebra lineal. Permite el desarrollo de procedimientos genéricos de procesamiento de la información y, por lo tanto, una unificación de los métodos básicos de la informática, en particular del procesamiento distribuido de la información .

La información se relaciona con preguntas precisas, proviene de diferentes fuentes, debe ser agregada y puede enfocarse en preguntas de interés. Partiendo de estas consideraciones, las álgebras de información (Kohlas 2003) son álgebras de dos tipos : ${\displaystyle (\Phi ,D)}$

¿Dónde está un semigrupo , que representa una combinación o agregación de información, y ${\displaystyle \Phi }$

${\displaystyle D}$es una red de dominios (relacionados con preguntas) cuyo orden parcial refleja la granularidad del dominio o la pregunta, y una operación mixta que representa el enfoque o la extracción de información.

La información y sus operaciones

Más precisamente, en el álgebra de dos órdenes , se definen las siguientes operaciones ${\displaystyle (\Phi ,D)}$

Además, en la red habitual se definen operaciones (encuentro y unión). ${\displaystyle D}$

Axiomas y definición

Los axiomas del álgebra de dos ordenaciones , además de los axiomas de la red : ${\displaystyle (\Phi ,D)}$ ${\displaystyle D}$

Un álgebra de dos ordenamientos que satisface estos axiomas se denomina álgebra de información . ${\displaystyle (\Phi ,D)}$

Orden de información

Se puede introducir un orden parcial de información definiendo si . Esto significa que es menos informativo que si no añade información nueva a . El semigrupo es una semirretícula relativa a este orden, es decir . En relación con cualquier dominio (pregunta), se puede introducir un orden parcial definiendo si . Representa el orden del contenido de información de y en relación con el dominio (pregunta) . ${\displaystyle \phi \leq \psi }$ ${\displaystyle \phi \otimes \psi =\psi }$ ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle \Phi }$ ${\displaystyle \phi \otimes \psi =\phi \vee \psi }$ ${\displaystyle x\in D}$ ${\displaystyle \phi \leq _{x}\psi }$ ${\displaystyle \phi ^{\Rightarrow x}\leq \psi ^{\Rightarrow x}}$ ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle x}$

Álgebra de información etiquetada

Los pares , donde y tales que forman un álgebra de información etiquetada . Más precisamente, en el álgebra de dos órdenes , se definen las siguientes operaciones ${\displaystyle (\phi ,x)\ }$ ${\displaystyle \phi \in \Phi }$ ${\displaystyle x\in D}$ ${\displaystyle \phi ^{\Rightarrow x}=\phi }$ ${\displaystyle (\Phi ,D)\ }$

Modelos de álgebras de información

A continuación se presenta una lista incompleta de ejemplos de álgebras de información:

• Álgebra relacional : la reducción de un álgebra relacional con unión natural como combinación y la proyección usual es un álgebra de información etiquetada, ver Ejemplo.
• Sistemas de restricciones: Las restricciones forman un álgebra de información (Jaffar y Maher 1994).
• Álgebras valoradas en semirings: Los semirings C inducen álgebras de información (Bistarelli, Montanari & Rossi1997);(Bistarelli et al. 1999);(Kohlas & Wilson 2006).
• Lógica : Muchos sistemas lógicos inducen álgebras de información (Wilson y Mengin, 1999). Las reducciones de álgebras cilíndricas (Henkin, Monk y Tarski, 1971) o álgebras poliádicas son álgebras de información relacionadas con la lógica de predicados (Halmos, 2000).
• Álgebras del módulo : (Bergstra, Heering y Klint 1990); (de Lavalette 1992).
• Sistemas lineales : Los sistemas de ecuaciones lineales o desigualdades lineales inducen álgebras de información (Kohlas 2003).

Ejemplo resuelto: álgebra relacional

Sea un conjunto de símbolos, llamados atributos (o nombres de columna ). Para cada sea un conjunto no vacío, el conjunto de todos los valores posibles del atributo . Por ejemplo, si , entonces podría ser el conjunto de cadenas, mientras que y son ambos el conjunto de números enteros no negativos. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \alpha \in {\mathcal {A}}}$ ${\displaystyle U_{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle {\mathcal {A}}=\{{\texttt {name}},{\texttt {age}},{\texttt {income}}\}}$ ${\displaystyle U_{\texttt {name}}}$ ${\displaystyle U_{\texttt {age}}}$ ${\displaystyle U_{\texttt {income}}}$

Sea . Una -tupla es una función tal que y para cada El conjunto de todas las -tuplas se denota por . Para una -tupla y un subconjunto la restricción se define como la -tupla tal que para todos los . ${\displaystyle x\subseteq {\mathcal {A}}}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle {\hbox{dom}}(f)=x}$ ${\displaystyle f(\alpha )\in U_{\alpha }}$ ${\displaystyle \alpha \in x}$ ${\displaystyle x}$ ${\displaystyle E_{x}}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle y\subseteq x}$ ${\displaystyle f[y]}$ ${\displaystyle y}$ ${\displaystyle g}$ ${\displaystyle g(\alpha )=f(\alpha )}$ ${\displaystyle \alpha \in y}$

Una relación sobre ${\displaystyle R}$ ${\displaystyle x}$ es un conjunto de -tuplas, es decir, un subconjunto de . El conjunto de atributos se denomina dominio de y se denota por . La proyección de sobre se define de la siguiente manera: ${\displaystyle x}$ ${\displaystyle E_{x}}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle d(R)}$ ${\displaystyle y\subseteq d(R)}$ ${\displaystyle R}$ ${\displaystyle y}$

${\displaystyle \pi _{y}(R):=\{f[y]\mid f\in R\}.}$

La unión de una relación sobre y una relación sobre se define de la siguiente manera: ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle y}$

${\displaystyle R\bowtie S:=\{f\mid f\quad (x\cup y){\hbox{-tuple}},\quad f[x]\in R,\;f[y]\in S\}.}$

A modo de ejemplo, sean y las siguientes relaciones: ${\displaystyle R}$ ${\displaystyle S}$

${\displaystyle R={\begin{matrix}{\texttt {name}}&{\texttt {age}}\\{\texttt {A}}&{\texttt {34}}\\{\texttt {B}}&{\texttt {47}}\\\end{matrix}}\qquad S={\begin{matrix}{\texttt {name}}&{\texttt {income}}\\{\texttt {A}}&{\texttt {20'000}}\\{\texttt {B}}&{\texttt {32'000}}\\\end{matrix}}}$

Entonces la unión de y es: ${\displaystyle R}$ ${\displaystyle S}$

${\displaystyle R\bowtie S={\begin{matrix}{\texttt {name}}&{\texttt {age}}&{\texttt {income}}\\{\texttt {A}}&{\texttt {34}}&{\texttt {20'000}}\\{\texttt {B}}&{\texttt {47}}&{\texttt {32'000}}\\\end{matrix}}}$

Una base de datos relacional con unión natural como combinación y la proyección habitual es un álgebra de información. Las operaciones están bien definidas ya que ${\displaystyle \bowtie }$ ${\displaystyle \pi }$

• ${\displaystyle d(R\bowtie S)=d(R)\cup d(S)}$
• Si , entonces . ${\displaystyle x\subseteq d(R)}$ ${\displaystyle d(\pi _{x}(R))=x}$

Es fácil ver que las bases de datos relacionales satisfacen los axiomas de un álgebra de información etiquetada:

semigrupo

${\displaystyle (R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})}$y ${\displaystyle R\bowtie S=S\bowtie R}$

transitividad

Si , entonces . ${\displaystyle x\subseteq y\subseteq d(R)}$ ${\displaystyle \pi _{x}(\pi _{y}(R))=\pi _{x}(R)}$

combinación

Si y , entonces . ${\displaystyle d(R)=x}$ ${\displaystyle d(S)=y}$ ${\displaystyle \pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)}$

idempotencia

Si , entonces . ${\displaystyle x\subseteq d(R)}$ ${\displaystyle R\bowtie \pi _{x}(R)=R}$

apoyo

Si , entonces . ${\displaystyle x=d(R)}$ ${\displaystyle \pi _{x}(R)=R}$

Conexiones

Álgebras de valoración

La eliminación del axioma de idempotencia conduce a las álgebras de valoración . Estos axiomas fueron introducidos por (Shenoy y Shafer 1990) para generalizar los esquemas de cálculo locales (Lauritzen y Spiegelhalter 1988) desde las redes bayesianas hasta formalismos más generales, incluidas las funciones de creencia, los potenciales de posibilidad, etc. (Kohlas y Shenoy 2000). Para una exposición extensa sobre el tema, véase Pouly y Kohlas (2011).

Dominios y sistemas de información

Las álgebras de información compactas (Kohlas 2003) están relacionadas con los dominios de Scott y los sistemas de información de Scott (Scott 1970); (Scott 1982); (Larsen y Winskel 1984).

Información incierta

Las variables aleatorias con valores en álgebras de información representan sistemas de argumentación probabilística (Haenni, Kohlas y Lehmann 2000).

Información semántica

Las álgebras de información introducen la semántica al relacionar la información con las preguntas a través del enfoque y la combinación (Groenendijk y Stokhof 1984); (Floridi 2004).

Flujo de información

Las álgebras de información están relacionadas con el flujo de información, en particular con las clasificaciones (Barwise y Seligman 1997).

Descomposición de los árboles

Las álgebras de información se organizan en una estructura de árbol jerárquica y se descomponen en problemas más pequeños.

Teoría de semigrupos

...

Modelos compositivos

Estos modelos pueden definirse en el marco de las álgebras de información: https://arxiv.org/abs/1612.02587

Fundamentos axiomáticos ampliados de las álgebras de información y valoración

El concepto de independencia condicional es básico para las álgebras de información y una nueva base axiomática de las álgebras de información, basada en la independencia condicional, que extiende la antigua (ver arriba) está disponible: https://arxiv.org/abs/1701.02658

Raíces históricas

Los axiomas para las álgebras de información se derivan del sistema de axiomas propuesto en (Shenoy y Shafer, 1990), ver también (Shafer, 1991).

Referencias

• Barwise, J. ; Seligman, J. (1997), Flujo de información: la lógica de los sistemas distribuidos , Cambridge, Reino Unido: Número 44 en Cambridge Tracts in Theoretical Computer Science, Cambridge University Press
• Bergstra, JA; Heering, J.; Klint, P. (1990), "Álgebra de módulos", Journal of the ACM , 73 (2): 335–372, doi : 10.1145/77600.77621 , S2CID  7910431
• Bistarelli, S.; Fargier, H .; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G. (1999), "CSP basados ​​en semiring y CSP valorados: marcos, propiedades y comparación", Constraints , 4 (3): 199–240, doi :10.1023/A:1026441215081, S2CID  17232456, archivado desde el original el 10 de marzo de 2022
• Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca (1997), "Satisfacción y optimización de restricciones basadas en semiring", Journal of the ACM , 44 (2): 201–236, CiteSeerX  10.1.1.45.5110 , doi :10.1145/256303.256306, S2CID  4003767
• de Lavalette, Gerard R. Renardel (1992), "Semántica lógica de la modularización", en Egon Börger; Gerhard Jäger; Hans Kleine Büning; Michael M. Richter (eds.), CSL: Quinto taller sobre lógica informática , volumen 626 de Lecture Notes in Computer Science, Springer, págs. 306–315, ISBN 978-3-540-55789-0
• Floridi, Luciano (2004), "Esquema de una teoría de la información fuertemente semántica" (PDF) , Minds and Machines , 14 (2): 197–221, doi :10.1023/b:mind.0000021684.50925.c9, S2CID  3058065
• Groenendijk, J.; Stokhof, M. (1984), Estudios sobre la semántica de las preguntas y la pragmática de las respuestas , tesis doctoral, Universiteit van Amsterdam
• Haenni, R.; Kohlas, J.; Lehmann, N. (2000), "Sistemas de argumentación probabilística" (PDF) , en J. Kohlas; S. Moral (eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems , Dordrecht: Volumen 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, pp. 221–287, archivado desde el original el 25 de enero de 2005
• Halmos, Paul R. (2000), "Una autobiografía de álgebras poliádicas", Logic Journal of the IGPL , 8 (4): 383–392, doi :10.1093/jigpal/8.4.383, S2CID  36156234
• Henkin, L .; Monje, JD; Tarski, A. (1971), Álgebras cilíndricas , Ámsterdam: Holanda Septentrional, ISBN 978-0-7204-2043-2
• Jaffar, J.; Maher, MJ (1994), "Programación lógica de restricciones: una encuesta", Journal of Logic Programming , 19/20: 503–581, doi : 10.1016/0743-1066(94)90033-7
• Kohlas, J. (2003), Álgebras de información: estructuras genéricas para la inferencia , Springer-Verlag, ISBN 978-1-85233-689-9
• Kohlas, J.; Shenoy, PP (2000), "Computación en álgebras de valoración", en J. Kohlas; S. Moral (eds.), Manual de razonamiento derrotable y sistemas de gestión de la incertidumbre, volumen 5: Algoritmos para la incertidumbre y el razonamiento derrotable , Dordrecht: Kluwer, págs. 5-39
• Kohlas, J.; Wilson, N. (2006), Cálculo local exacto y aproximado en álgebras de valoración inducidas por semirings (PDF) , Informe técnico 06-06, Departamento de Informática, Universidad de Friburgo, archivado desde el original el 24 de septiembre de 2006
• Larsen, KG; Winskel, G. (1984), "Uso de sistemas de información para resolver ecuaciones de dominio recursivas de manera efectiva", en Gilles Kahn; David B. MacQueen; Gordon D. Plotkin (eds.), Semántica de tipos de datos, Simposio internacional, Sophia-Antipolis, Francia, 27-29 de junio de 1984, Actas , vol. 173 de Lecture Notes in Computer Science, Berlín: Springer, págs. 109-129
• Lauritzen, SL; Spiegelhalter, DJ (1988), "Cálculos locales con probabilidades en estructuras gráficas y su aplicación a sistemas expertos", Journal of the Royal Statistical Society, Serie B , 50 (2): 157–224, doi :10.1111/j.2517-6161.1988.tb01721.x
• Pouly, Marc; Kohlas, Jürg (2011), Inferencia genérica: una teoría unificadora para el razonamiento automatizado , John Wiley & Sons, ISBN 978-1-118-01086-0
• Scott, Dana S. (1970), Esquema de una teoría matemática de la computación , Monografía técnica PRG-2, Laboratorio de Computación de la Universidad de Oxford, Grupo de Investigación en Programación
• Scott, DS (1982), "Dominios para la semántica denotacional", en M. Nielsen; EM Schmitt (eds.), Autómatas, lenguajes y programación , Springer, págs. 577–613
• Shafer, G. (1991), Un estudio axiomático de la computación en hiperárboles , Documento de trabajo 232, Facultad de Negocios, Universidad de Kansas
• Shenoy, PP; Shafer, G. (1990). "Axiomas para la propagación de la probabilidad y la función de creencia". En Ross D. Shachter; Tod S. Levitt; Laveen N. Kanal; John F. Lemmer (eds.). Incertidumbre en la inteligencia artificial 4. Vol. 9. Ámsterdam: Elsevier. págs. 169–198. doi :10.1016/B978-0-444-88650-7.50019-6. hdl : 1808/144 . ISBN . 978-0-444-88650-7. {{cite book}}: |journal=ignorado ( ayuda )
• Wilson, Nic; Mengin, Jérôme (1999), "Deducción lógica utilizando el marco de cálculo local", en Anthony Hunter; Simon Parsons (eds.), Enfoques simbólicos y cuantitativos para el razonamiento y la incertidumbre, Conferencia europea, ECSQARU'99, Londres, Reino Unido, 5-9 de julio de 1999, Actas, volumen 1638 de Lecture Notes in Computer Science , Springer, págs. 386-396, ISBN 978-3-540-66131-3