El término " álgebra de la información " se refiere a técnicas matemáticas de procesamiento de 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 analiza la comunicación y el almacenamiento. Sin embargo, hasta ahora no se ha considerado que la información provenga de diferentes fuentes y que, por lo tanto, se suele combinar. Además, en la teoría clásica de la información se ha descuidado que se desea extraer de un dato aquellas partes que son relevantes para cuestiones específicas.
Una redacció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. Tal álgebra involucra varios formalismos de la informática , que parecen ser diferentes en la superficie: 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 información y, por lo tanto, una unificación de métodos básicos de informática, en particular de procesamiento de información distribuida .
La información se relaciona con preguntas precisas, proviene de diferentes fuentes, debe ser agregada y puede enfocarse en preguntas de interés. A partir de estas consideraciones, las álgebras de información ( Kohlas 2003 ) son álgebras clasificadas en dos, dónde es un semigrupo , que representa una combinación o agregación de información,es un entramado de dominios (relacionado con preguntas) cuyo orden parcial refleja la granularidad del dominio o la pregunta, y una operación mixta que representa el enfoque o extracción de información.
Información y sus operaciones
Más precisamente, en el álgebra de dos ordenamientos , se definen las siguientes operaciones
|
Además, en Se definen las operaciones de celosía habituales (reunirse y unirse).
Axiomas y definición
Los axiomas del álgebra de dos ordenamientos , además de los axiomas de la celosía :
Para enfocar una información en combinado con otra información al dominio , uno puede enfocar primero la segunda información para y luego combinar.
Para enfocar una información en y , uno puede enfocarlo a .
Una información combinada con una parte de sí misma no aporta nada nuevo.
Cada información se refiere al menos a un dominio (pregunta). |
Un álgebra de dos ordenamientos Satisfacer estos axiomas se llama Álgebra de Información .
Orden de información
Se puede introducir un orden parcial de información definiendo Si . Esto significa que es menos informativo que si no agrega nueva información a . El semigrupo es una semirrejilla relativa a este orden, es decir . Relativo a cualquier dominio (pregunta) se puede introducir un orden parcial definiendo Si . Representa el orden del contenido de la información de y relativo al dominio (pregunta) .
Álgebra de información etiquetada
Las parejas , dónde y tal que formar un Álgebra de la información etiquetada . Más precisamente, en el álgebra de dos ordenamientos, se definen las siguientes operaciones
|
Modelos de álgebras de información
A continuación se muestra una lista incompleta de instancias de álgebras de información:
- Álgebra relacional : la reducción de un álgebra relacional con combinación natural como combinación y la proyección habitual es un álgebra de información etiquetada, consulte el Ejemplo .
- Sistemas de restricciones : las restricciones forman un álgebra de información ( Jaffar y Maher 1994 ).
- Álgebras valoradas de Semiring : C-Semirings 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
Dejar ser un conjunto de símbolos, llamados atributos (o nombres de columnas ). Para cada dejar ser un conjunto no vacío, el conjunto de todos los valores posibles del atributo. Por ejemplo, si, luego podría ser el conjunto de cadenas, mientras que y son ambos el conjunto de números enteros no negativos.
Dejar . Un-tuple es una función así que eso y para cada El conjunto de todos -tuplas se denota por . Por un-tupla y un subconjunto la restricción se define como el -tupla así que eso para todos .
Una relación encima es un conjunto de -tuplas, es decir, un subconjunto de . El conjunto de atributosse llama el dominio de y denotado por . Parala proyección de sobre se define de la siguiente manera:
La unión de una relación encima y una relación encima se define de la siguiente manera:
Como ejemplo, dejemos y ser las siguientes relaciones:
Entonces la unión de y es:
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 desde
- Si , luego .
Es fácil ver que las bases de datos relacionales satisfacen los axiomas de un álgebra de información etiquetada:
- semigrupo
- y
- transitividad
- Si , luego .
- combinación
- Si y , luego .
- idempotencia
- Si , luego .
- apoyo
- Si , luego .
Conexiones
- Álgebras de valoración
- Dejar de lado el axioma de idempotencia conduce a álgebras de valoración . Estos axiomas han sido introducidos por ( Shenoy y Shafer 1990 ) para generalizar los esquemas de cálculo local ( Lauritzen y Spiegelhalter 1988 ) desde las redes bayesianas a formalismos más generales, incluida la función de creencias, los potenciales de posibilidad, etc. ( Kohlas y Shenoy 2000 ). Para una exposición del tamaño de un libro sobre el tema, consulte Pouly & 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 & Lehmann 2000 ).
- Información semántica
- Las álgebras de información introducen la semántica relacionando la información con las preguntas mediante el 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 las clasificaciones ( Barwise y Seligman 1997 ).
- Descomposición del árbol
- ...
- Teoría del semigrupo
- ...
- Modelos composicionales
- Dichos modelos pueden definirse en el 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 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, ampliando la anterior (ver arriba) está disponible: https://arxiv.org/abs/1701.02658
Raíces históricas
Los axiomas de 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), 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), "Módulo de álgebra", 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" , Restricciones , 4 (3): 199–240, doi : 10.1023 / A: 1026441215081 , S2CID 17232456[ enlace muerto permanente ]
- 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[ enlace muerto permanente ]
- 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 de la informática , volumen 626 de las notas de clase en informática, Springer, págs. 306–315, ISBN 978-3-540-55789-0
- Floridi, Luciano (2004), "Esquema de una teoría de 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: Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, págs. 221-287, archivado desde el original (PDF) 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 .; Monk, JD; Tarski, A. (1971), Álgebras cilíndricas , Amsterdam: Holanda Septentrional, ISBN 978-0-7204-2043-2
- Jaffar, J .; Maher, MJ (1994), "Programación lógica de restricción: una encuesta", J. Of Logic Programming , 19/20: 503–581, doi : 10.1016 / 0743-1066 (94) 90033-7
- Kohlas, J. (2003), Álgebras de la 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.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning , Dordrecht: Kluwer, págs. 5-39
- Kohlas, J .; Wilson, N. (2006), Cálculo local exacto y aproximado en álgebras de valoración inducidas por semiring (PDF) , Informe técnico 06-06, Departamento de Informática, Universidad de Friburgo, archivado desde el original (PDF) el 24 de septiembre de 2006
- Larsen, KG; Winskel, G. (1984), "Uso de sistemas de información para resolver con eficacia ecuaciones de dominio recursivo", en Gilles Kahn; David B. MacQueen; Gordon D. Plotkin (eds.), Semantics of Data Types, International Symposium, Sophia-Antipolis, Francia, 27-29 de junio de 1984, Actas , 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", Revista de la Royal Statistical Society, Serie B , 50 : 157-224
- 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), "Domains for denotational semántica", en M. Nielsen; EM Schmitt (eds.), Autómatas, lenguajes y programación , Springer, págs. 577–613
- Shafer, G. (1991), An axiomatic study of computation in hypertrees , Working Paper 232, School of Business, Universidad de Kansas
- Shenoy, PP; Shafer, G. (1990). "Axiomas de probabilidad y proagación de función de creencias". En Ross D. Shachter; Tod S. Levitt; Laveen N. Kanal; John F. Lemmer (eds.). Incertidumbre en Inteligencia Artificial 4 . Inteligencia de máquina y reconocimiento de patrones . 9 . Amsterdam: Elsevier. págs. 169–198. doi : 10.1016 / B978-0-444-88650-7.50019-6 . hdl : 1808/144 . ISBN 978-0-444-88650-7.
- 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 del razonamiento y la incertidumbre, Conferencia europea, ECSQARU'99, Londres, Reino Unido, 5 al 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