정보 대수

정보대수학이란 정보처리의 수학적 기법을 말한다.고전적인 정보 이론은 클로드 섀넌으로 거슬러 올라간다.통신과 저장을 바라보는 정보전송의 이론이다.그러나 정보가 서로 다른 출처에서 나오고 따라서 대개 결합되는 것은 지금까지 고려되지 않았다.나아가 특정 질문과 관련된 정보 한 조각에서 그러한 부분을 추출하고자 한다는 것은 고전적인 정보 이론에서 무시되어 왔다.null

이러한 연산의 수학적 표현은 정보 처리의 기본 모드를 기술하면서 정보의 대수적 표현으로 이어진다.그러한 대수학에는 컴퓨터 과학의 몇 가지 공식적 표현이 포함되는데, 표면적으로는 서로 다른 것처럼 보이는 관계형 데이터베이스, 형식논리의 다중 시스템 또는 선형대수의 수치적 문제 등이 포함된다.정보처리의 일반적 절차의 개발을 가능하게 하고, 따라서 컴퓨터 과학의 기본 방법, 특히 분산된 정보처리의 통일화를 가능하게 한다.null

정보는 정확한 질문과 관련되고, 서로 다른 출처에서 나오고, 통합되어야 하며, 관심 있는 질문에 집중될 수 있다.Starting from these considerations, information algebras (Kohlas 2003) are two-sorted algebras ${\displaystyle (\Phi ,D)}$, where ${\displaystyle \Phi }$ is a semigroup, representing combination or aggregation of information, ${\displaystyle D}$ is a lattice of domains (related to questions) whose partial order refl도메인 또는 질문의 세분화 및 정보의 집중 또는 추출을 나타내는 혼합 작업.null

정보 및 정보 운영

보다 정확히 말하면, 2개의 대수학 (${\displaystyle \phi }$, D${\displaystyle }$) ${\displaystyle (\Phi ,D)}$에서 다음과 같은 연산을 정의한다$.$

조합 $\displaystyle \otimes :\Phi \otimes \Phi \rightarrow \Phi ,~(\phi ,\psi )\mapsto \phi \otimes \psi }$ 포커싱 ${\displaystyle \Rightarrow :\Phi \otimes D\rightarrow \Phi ,~(\phi ,x)\mapsto \phi ^{\Rightarrow x}}}$

또한 $D{\displaystyle }$ ${\displaystyle D}$에서는 일반적인$$ 격자 연산(만나고 결합)이 정의된다.null

공리와 정의

격자 $D{\displaystyle }$ ${\displaystyle D}$의 공리 외에 두 가지 유형의 대수$({\displaystyle }$ ${\displaystyle \mathrm{\phi }}$, ${\displaystyle D}$) ${\displaystyle(\Phi ,D)}$의 공리$:$

세미그룹 ${\displaystyle \mathrm{\phi }}$ ${\displaystyle \Phi }$은(는) 중립 요소와 결합(빈칸 정보를 나타냄)된 상호 교환적 의미군이다$$. 조합에 따른 집중력 분포도 ${\displaystyle(\phi ^{\Rightarrow x}\otimes \psi )^{\Rightarrow x}=\phi ^{\Rightarrow x}\otimes \psi ^{\Rightarrow x}}}}}}}$ $도메인{\displaystyle }$ $x{\displaystyle }${\displaystyle$$ x$}$에 다른 정보와 $결합$된 x$$$\{\backslash$displaystyle x$}$에 정보를 집중하려면 먼저 두 번째 정보를 x ${\displaystyle x}$에 집중한 다음$$ 결합하는 것이 좋다.null 포커스의 전이성 ${\displaystyle(\phi ^{\Rightarrow x})^{\오른쪽 화살표 y}=\phi ^{\오른쪽 화살표 x\wedge y}}}$ $x{\displaystyle }$ ${\displaystyle x}$ $및$ y ${\displaystyle y}$에 정보를 집중하려면 $x{\displaystyle }$ ${\displaystyle \wedge }$ ${\displaystyle y}$ ${\displaystyle$ x$\wedge$ y$}$에 정보를 집중할 수 있다$.$ 공차 ${\displaystyle \phi \otimes \phi ^{\Rightarrow x}=\phi }$ 그 자체의 일부와 결합된 정보는 새로운 것을 주지 않는다.null 지원 ${\displaystyle \mathrm{\forall }}$ ${\displaystyle \mathrm{\varphi }}$ ${\displaystyle \in }$, , ${\displaystyle \text{,}\mathrm{}}$ x ${\displaystyle x}$ D ${\displaystyle \fall \phi \in \Phi ,~\exists$ x$\d}$과 같이 ${\displaystyle {}^{}}$= $⇒$ =\$phi ^{\Rightarrow x}}}$ 각 정보는 적어도 하나의 영역(질문)을 가리킨다.null

이러한 공리를 만족하는$$ 두 가지 종류의 대수$({\displaystyle }$ ${\displaystyle \phi }$, D${\displaystyle }$) ${\displaystyle (\Phi ,D)}$를 정보 대수라고 한다.null

정보순번

A partial order of information can be introduced by defining ${\displaystyle \phi \leq \psi }$ if ${\displaystyle \phi \otimes \psi =\psi }$. This means that ${\displaystyle \phi }$ is less informative than ${\displaystyle \psi }$ if it adds no new information to ${\displaystyle \psi }$. The semigroup ${\displaystyle \Phi }$ is a semilattice relative to this order, i.e. ${\displaystyle \phi \otimes \psi =\phi \vee \psi }$. Relative to any domain (question) ${\displaystyle x\in D}$ a partial order can be introduced by defining ${\displaystyle \phi \leq _{x}\psi }$ if ${\displaystyle {\varphi }^{\Rightarrow x}\le }$${\displaystyle {\psi }^x}$ ${\$ x$}\leq \psi$ $^{\$$Rightarrow x$ 도메인(질문) $x{\displaystyle }$ {\displaystyle x$${\$displaysty x$}에 $상대적$인 ${$$${\$displaystysty \psi}$의 정보 내용 순서를 나타낸다$.$

라벨 정보 대수

The pairs ${\displaystyle (\phi ,x)\ }$, where ${\displaystyle \phi \in \Phi }$ and ${\displaystyle x\in D}$ such that ${\displaystyle \phi ^{\Rightarrow x}=\phi }$ form a labeled Information Algebra.보다 정확히 말하면, ${\displaystyle \mathrm{2개}}$의 대수학${\displaystyle }$( ${\displaystyle ,}$ ,${\displaystyle D}$ ) ${\$에서 다음과 같은 연산을 정의한다$.$

라벨링 $d(\phi ,x)=x\ }$ 조합 $\displaystyle (\phi ,x)\otimes (\phi ,y)=(\phi \otimes \otimes \doss,x\vee y)~~~}$ 투영 ${\displaystyle (\phi ,x)^{\downarrow y}=(\phi ^{\Rightarrow y}y}{\text{{}y}}}}{}y\text{{{}y\y\leq x})$

정보 알헤브라의 모델

다음은 정보 알헤브라의 불완전한 사례 목록이다.

• 관계 대수:자연 결합을 조합으로 하고 통상적인 투영으로 하는 관계 대수학의 환원은 라벨로 표시된 정보 대수다. 예를 참조한다.
• 제약 조건 시스템:제약조건은 정보 대수학을 형성한다(Jaffar & Maher 1994).
• 의미 부여 값진 알헤브라스: C-세미링스는 정보 알헤브라를 유도한다(비스타렐리, 몬타나리 & 로시1997);(비스타렐리 외 1999), (코흘라스 & 윌슨 2006).
• 논리: 많은 논리 시스템이 정보 알제브라를 유도한다(Wilson & Mengin 1999).원통형 알헤브라(Henkin, Monkin & Tarski 1971) 또는 폴리아디드 알헤브라는 술어 논리(Halmos 2000)와 관련된 정보 알헤브라이다.
• 모듈 알헤브라스: (Bergstra, Heering & Klint 1990);(de Lavalette 1992).
• 선형 시스템:선형 방정식이나 선형 불평등의 시스템은 정보 알제브라를 유도한다(Kohlas 2003).

워크아웃 예제: 관계 대수

이 섹션은 위키피디아의 품질 기준을 충족시키기 위해 정리가 필요할 수 있다.구체적인 문제는 \texttt이다. 가능한 경우 이 섹션을 개선하는 데 도움을 주십시오. (2014년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

$A{\displaystyle \mathcal{}}$ ${\$을(를) 속성(또는 열 이름)이라고 하는 기호 집합으로$$ 두십시오. For each ${\displaystyle \alpha \in {\mathcal {A}}}$ let ${\displaystyle U_{\alpha }}$ be a non-empty set, the set of all possible values of the attribute ${\displaystyle \alpha }$. For example, if ${\displaystyle {\mathcal {A}}=\{{\texttt {name}},{\texttt {age$$}},{\textt$ 그러면 $U{\displaystyle {}_{}}$ ${\displaystyle {\mathtt{\text{이름}}}_{}}$ ${\${\$textt$ {name$}}$이(가) 문자열 집합이 될 수$$ 있고$$, $U{\displaystyle {}_{}}$ ${\displaystyle {\mathtt{\text{나이}}}_{}}${\$displaystyle U_{\texttt}},$ ${\displaystyle {\mathtt{\text{U}}}_{}}$소득 {\$displaystystyle U_{\ttttt}}}}$은 모두 음이 아닌 정수 집합이다$$.null

Let ${\displaystyle x\subseteq {\mathcal {A}}}$. An ${\displaystyle x}$-tuple is a function ${\displaystyle f}$ so that ${\displaystyle {\hbox{dom}}(f)=x}$ and ${\displaystyle f(\alpha )\in U_{\alpha }}$ for each ${\displaystyle \alpha \in x}$ The set of all${\displaystyle x}$-tuples is denoted by ${\displaystyle E_{x}}$. For an ${\displaystyle x}$-tuple ${\displaystyle f}$ and a subset ${\displaystyle y\subseteq x}$ the restriction ${\displaystyle f[y]}$ is defined to be the ${\displaystyle y}$-tuple ${\displaystyle g}$그래서 $모든{\displaystyle }$${\displaystyle }\alpha {\displaystyle }$ ${\displaystyle \alpha }$${\displaystyle \}}$= ${\displaystyle f}$ (${\displaystyle \alpha }$)$${\$displaystyle g(\property )=f(\$$property$\property $\in y$에 대해$$$$.

$x{\displaystyle }$ ${\displaystyle x}$에 대한 $관계{\displaystyle }$ R$${\$displaystyle$R}은 x$${\$displaystyle$x} -tuples$$ 집합, 즉 ${\displaystyle E_{}}$ x ${\$의 부분 집합이다$.$속성 $x{\displaystyle }$ ${\displaystyle x}$의 집합을 $R{\displaystyle }$ ${\displaystyle R}$의 도메인이라고 하며 d ( $R{\displaystyle }$) ${\displaystyle d(R)}$으로 표시한다$.$ y${\displaystyle }y{\displaystyle }$ d${\displaystyle (R)}$ ${\displaystystyle y$$}$에 $대한{\displaystyle }$ R$$${\displaystystystyleeq$ $d($$R$)의 투영은 다음과 같이$$ 정의된다.

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

$x{\displaystyle }$ ${\displaystyle x}$에 대한 $R{\displaystyle }$ ${\displaystyle R}$ 및 $y{\displaystyle }$ ${\displaystyle y}$에 대한 S ${\displaystyle S}$의 결합은 다음과 같이 정의된다$$.

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

예를 들어 $R{\displaystyle }$ ${\displaystyle R}$ 및 $S$ ${\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}}}$

$그러면{\displaystyle }$ R ${\displaystyle R}$ 및 $S$ ${\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}}}$

자연 결합 $\bowtie {\displaystyle }$ ${\displaystyle \bowtie}$을(를) 조합으로$$ 하는 관계형 데이터베이스와 일반적인 투영 $\pi {\displaystyle }$ ${\displaystyle \pi }$은 정보$$ 대수학이다.다음부터 작업이 잘 정의되어 있다.

• ${\displaystyle d(R\bowtie S)=d(R)\cup d(S)}$
• $x{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle d}$( R${\displaystyle }$) ${\displaystyle$ x$\subseteq d($${\displaystyle R}$$)}$인 경우 $d{\displaystyle }$ $($${\displaystyle {}_{}}$ x (${\displaystyle {}_{}{R}_{}}$) =${\displaystyle x}$ ${\displaystyle d(\pi _{x}(R)=x$ .

관계형 데이터베이스가 다음과 같이 라벨이 붙은 정보 대수학의 공리를 만족하는 것을 쉽게 알 수 있다.

세미그룹

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

전이성

$x{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle y}$ ${\displaystyle \subseteq }$ ${\displaystyle d}$( R${\displaystyle }$) ${\displaystyle x\subseteq y\subseteq d(R)}$인 경우,$$$\pi {\displaystyle {}_{}}$ ${\displaystyle x_{}}$( ${\displaystyle {\pi }_{}}$ y${\displaystyle {}_{}}$( ${\displaystyle R}$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle x_{}}$ (${\displaystyle {}_{}R}$) ${\displaystyle \pi _{x}(\pi })(R)$$=\pi _{x}(R)}$.

콤비네이션

If ${\displaystyle d(R)=x}$ and ${\displaystyle d(S)=y}$, then ${\displaystyle \pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)}$.

전적인 가능성

$x{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle d}$( R${\displaystyle }$) ${\displaystyle x\subseteq d($${\displaystyle R}$$)}$인 경우$,$ $R{\displaystyle }$ ${\displaystyle \bowtie }$ ${\displaystyle {\pi }_{}}$ x${\displaystyle {}_{}}$( R${\displaystyle }$)${\displaystyle }$= ${\displaystyle R}$ ${\displaystyle R\bowtie \pi _{x}(R)=R$

지지하다

$x{\displaystyle }$= ${\displaystyle d}$ (${\displaystyle }$R${\displaystyle }$) ${\displaystyle x=d(R)}$인 경우,$$${\displaystyle \pi }$ ${\displaystyle x_{}}$( ${\displaystyle R}$)${\displaystyle }$= R ${\displaystyle \pi _{x}(R)=R}$.

연결

이 구간은 확장이 필요하다.덧셈으로 도와줘도 된다. (2014년 3월)

밸류에이션 알헤브라스

공리를 떨어뜨리는 것은 가치평가 알제브라로 이어진다.이러한 공리는 (Shenoy & Shafer 1990) 베이지안 네트워크에서 믿음 기능, 가능성 가능성 등을 포함한 보다 일반적인 공식으로 지역 연산 체계(Lauritzen & Spiegelhalter 1988)를 일반화하기 위해 도입되었다(Kohlas & Shenoy 2000).이 주제에 대한 장편 박람회는 Pouly & Kholas(2011)를 참조하십시오.

도메인 및 정보 시스템

콤팩트 정보 알헤브라스(Kohlas 2003)는 스콧 도메인 및 스콧 정보 시스템(Scott 1970; (Scott 19822);(Larsen & Winskel 1984)과 관련이 있다.

불확실한 정보

정보 알헤브라의 값을 갖는 랜덤 변수는 확률론적 주장 체계를 나타낸다(Haenni, Khlas & Lehmann 2000).

의미 정보

정보 알헤브라는 포커스와 조합을 통해 질문에 대한 정보를 연관시킴으로써 의미론을 도입한다(Groenendijk & Stokhof 1984). (Floridi 2004).

정보 흐름

정보 알헤브라는 정보 흐름, 특히 분류와 관련이 있다(Barwise & Seligman 1997).

나무 분해

...

세미그룹 이론

...

구성 모델

이러한 모델은 정보 알헤브라의 프레임워크 내에서 정의될 수 있다. https://arxiv.org/abs/1612.02587

정보 및 가치 평가 알헤브라의 확장된 자명성 기반

조건부 독립성의 개념은 정보 알헤브라의 기본이며, 정보 알헤브라의 새로운 자명적 기반으로서, 조건부 독립성에 기초하여 구 알헤브라의 확장(위 참조)을 이용할 수 있다. https://arxiv.org/abs/1701.02658

역사 루트

정보 알헤브라의 공리는 (Shenoy and Shafer, 1990)에서 제안된 공리 체계에서 도출되었다(Shafer, 1991).null

참조

• Barwise, J.; Seligman, J. (1997), Information Flow: The Logic of Distributed Systems, Cambridge U.K.: Number 44 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press
• Bergstra, J.A.; Heering, J.; Klint, P. (1990), "Module algebra", 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), "Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison", Constraints, 4 (3): 199–240, doi:10.1023/A:1026441215081, S2CID 17232456^{[영구적 데드링크]}
• Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca (1997), "Semiring-based constraint satisfaction and optimization", 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), "Logical semantics of modularisation", in Egon Börger; Gerhard Jäger; Hans Kleine Büning; Michael M. Richter (eds.), CSL: 5th Workshop on Computer Science Logic, Volume 626 of Lecture Notes in Computer Science, Springer, pp. 306–315, ISBN 978-3-540-55789-0
• Floridi, Luciano (2004), "Outline of a theory of strongly semantic information" (PDF), Minds and Machines, 14 (2): 197–221, doi:10.1023/b:mind.0000021684.50925.c9, S2CID 3058065
• Groenendijk, J.; Stokhof, M. (1984), Studies on the Semantics of Questions and the Pragmatics of Answers, PhD thesis, Universiteit van Amsterdam
• Haenni, R.; Kohlas, J.; Lehmann, N. (2000), "Probabilistic argumentation systems" (PDF), in J. Kohlas; S. Moral (eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Dordrecht: Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, pp. 221–287, archived from the original (PDF) on January 25, 2005
• Halmos, Paul R. (2000), "An autobiography of polyadic algebras", Logic Journal of the IGPL, 8 (4): 383–392, doi:10.1093/jigpal/8.4.383, S2CID 36156234
• Henkin, L.; Monk, J. D.; Tarski, A. (1971), Cylindric Algebras, Amsterdam: North-Holland, ISBN 978-0-7204-2043-2
• Jaffar, J.; Maher, M. J. (1994), "Constraint logic programming: A survey", Journal of Logic Programming, 19/20: 503–581, doi:10.1016/0743-1066(94)90033-7
• Kohlas, J. (2003), Information Algebras: Generic Structures for Inference, Springer-Verlag, ISBN 978-1-85233-689-9
• Kohlas, J.; Shenoy, P.P. (2000), "Computation in valuation algebras", in J. Kohlas; S. Moral (eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Dordrecht: Kluwer, pp. 5–39
• Kohlas, J.; Wilson, N. (2006), Exact and approximate local computation in semiring-induced valuation algebras (PDF), Technical Report 06-06, Department of Informatics, University of Fribourg, archived from the original (PDF) on September 24, 2006
• Larsen, K. G.; Winskel, G. (1984), "Using information systems to solve recursive domain equations effectively", in Gilles Kahn; David B. MacQueen; Gordon D. Plotkin (eds.), Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27–29, 1984, Proceedings, vol. 173 of Lecture Notes in Computer Science, Berlin: Springer, pp. 109–129
• Lauritzen, S. L.; Spiegelhalter, D. J. (1988), "Local computations with probabilities on graphical structures and their application to expert systems", Journal of the Royal Statistical Society, Series B, 50: 157–224
• Pouly, Marc; Kohlas, Jürg (2011), Generic Inference: A Unifying Theory for Automated Reasoning, John Wiley & Sons, ISBN 978-1-118-01086-0
• Scott, Dana S. (1970), Outline of a mathematical theory of computation, Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group
• Scott, D.S. (1982), "Domains for denotational semantics", in M. Nielsen; E.M. Schmitt (eds.), Automata, Languages and Programming, Springer, pp. 577–613
• Shafer, G. (1991), An axiomatic study of computation in hypertrees, Working Paper 232, School of Business, University of Kansas
• Shenoy, P. P.; Shafer, G. (1990). "Axioms for probability and belief-function proagation". In Ross D. Shachter; Tod S. Levitt; Laveen N. Kanal; John F. Lemmer (eds.). Uncertainty in Artificial Intelligence 4. Machine Intelligence and Pattern Recognition. Vol. 9. Amsterdam: Elsevier. pp. 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), "Logical deduction using the local computation framework", in Anthony Hunter; Simon Parsons (eds.), Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Conference, ECSQARU'99, London, UK, July 5–9, 1999, Proceedings, volume 1638 of Lecture Notes in Computer Science, Springer, pp. 386–396, ISBN 978-3-540-66131-3