Álgebra 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 información que estudia 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, en la teoría clásica de la información se ha descuidado la extracción de las partes de una información que son relevantes para preguntas específicas.

Una 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. Dicha álgebra involucra varios formalismos de la informática que, a primera vista, parecen diferentes: bases de datos relacionales, múltiples sistemas 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 agregarse y puede enfocarse en preguntas de interés. Partiendo de estas consideraciones, las álgebras de información ( Kohlas 2003 ) son álgebras de dos tipos. $(\Phi ,D)$ :

Dónde $\Phi$ es un semigrupo , que representa una combinación o agregación de información, y $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.

Información y sus operaciones

Más precisamente, en el álgebra de dos tipos $(\Phi ,D)$ Se definen las siguientes operaciones

Además, en $D$ Se definen las operaciones reticulares habituales (encontrar y unir).

Axiomas y definición

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

Un álgebra de dos tipos $(\Phi ,D)$ Satisfacer estos axiomas se denomina álgebra de la información .

Orden de la información

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

álgebra de información etiquetada

Las parejas $(\phi ,x)\$ , dónde $\phi \in \Phi$ y $x\in D$ de tal manera que $\phi ^{\Rightarrow x}=\phi$ formar un álgebra de información etiquetada . Más precisamente, en el álgebra de dos tipos $(\Phi ,D)\$ Se definen las siguientes operaciones

Modelos de álgebras de información

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

Álgebra relacional : El reducto 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 y Wilson 2006 ) .
Lógica : Muchos sistemas lógicos inducen álgebras de información ( Wilson y Mengin 1999 ) . Los reductos 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

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

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

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

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

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

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

Como ejemplo, sean $R$ y $S$ las siguientes relaciones:

R={\begin{array}{|c|c|}\hline {\text{name}}&{\text{age}}\\\hline {\text{A}}&{\text{34}}\\{\text{B}}&{\text{47}}\\\hline \end{array}}\qquad S={\begin{array}{|c|c|}\hline {\text{name}}&{\text{income}}\\\hline {\text{A}}&{\text{20,000}}\\{\text{B}}&{\text{32,000}}\\\hline \end{array}}

Entonces, la unión de $R$ y $S$ es:

R\bowtie S={\begin{array}{|c|c|}\hline {\text{name}}&{\text{age}}&{\text{income}}\\\hline {\text{A}}&{\text{34}}&{\text{20,000}}\\{\text{B}}&{\text{47}}&{\text{32,000}}\\\hline \end{array}}

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

$d(R\bowtie S)=d(R)\cup d(S)$
Si $x\subseteq d(R)$ , entonces $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: $(R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})$ y $R\bowtie S=S\bowtie R$
transitividad: Si $x\subseteq y\subseteq d(R)$ , entonces $\pi _{x}(\pi _{y}(R))=\pi _{x}(R)$ .
combinación: Si $d(R)=x$ y $d(S)=y$ , entonces $\pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)$ .
idempotencia: Si $x\subseteq d(R)$ , entonces $R\bowtie \pi _{x}(R)=R$ .
apoyo: Si $x=d(R)$ , entonces $\pi _{x}(R)=R$ .

Conexiones

Álgebras de valuación: Al prescindir del axioma de idempotencia, se obtienen álgebras de valoración . Estos axiomas fueron introducidos por Shenoy y Shafer (1990 ) para generalizar esquemas de computación local ( Lauritzen y Spiegelhalter, 1988 ) desde redes bayesianas a formalismos más generales, incluyendo funciones de creencia, potenciales de posibilidad, etc. ( Kohlas y Shenoy, 2000 ) . Para una exposición más 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 & Winskel 1984 ) .
Información incierta: Las variables aleatorias con valores en álgebras de información representan sistemas de argumentación probabilísticos ( 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 á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 dentro del marco de las álgebras de información: https://arxiv.org/abs/1612.02587
Fundamentos axiomáticos extendidos de las álgebras de información y valoración.: El concepto de independencia condicional es fundamental para las álgebras de información, y se encuentra disponible una nueva base axiomática de las álgebras de información, basada en la independencia condicional, que extiende la anterior (véase más arriba): 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), véase también (Shafer, 1991).

Referencias

Barwise, J.; Seligman, J. (1997), Information Flow: The Logic of Distributed Systems , 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), "CSPs basados en Semiring y CSPs con valores: marcos, propiedades y comparación" , Constraints , 4 (3): 199–240 , doi : 10.1023/A:1026441215081 , S2CID 17232456 , archivado del original el 10 de marzo de 2022
Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca (1997), "Satisfacción de restricciones y optimización 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, Universidad de Ámsterdam
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 del 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 con restricciones: una revisión", 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), "Cálculo 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, pp . 5–39
Kohlas, J.; Wilson, N. (2006), Computación local exacta y aproximada en álgebras de valuación inducidas por semianillos (PDF) , Informe técnico 06-06, Departamento de Informática, Universidad de Friburgo, archivado del original el 24 de septiembre de 2006.
Larsen, KG; Winskel, G. (1984), "Uso de sistemas de información para resolver eficazmente ecuaciones de dominio recursivas", en Gilles Kahn; David B. MacQueen; Gordon D. Plotkin (eds.), Semántica de los 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, pp. 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, pp . 577–613
Shafer, G. (1991), Un estudio axiomático de la computación en hiperárboles , Documento de trabajo 232, Escuela de Negocios, Universidad de Kansas
Shenoy, PP; Shafer, G. (1990). "Axiomas para la probabilidad y la propagación de funciones 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. pp. 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 computación local" , en Anthony Hunter; Simon Parsons (eds.), Enfoques simbólicos y cuantitativos del 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, pp. 386-396 , ISBN 978-3-540-66131-3