Информационная алгебра

Термин « информационная алгебра » относится к математическим методам обработки информации . Классическая теория информации восходит к Клоду Шеннону . Это теория передачи информации, рассматривающая связь и хранение. Однако до сих пор не учитывалось, что информация поступает из разных источников и поэтому обычно ее объединяют. Более того, в классической теории информации игнорировалось, что из части информации нужно извлечь те части, которые имеют отношение к конкретным вопросам.

Математическая формулировка этих операций приводит к алгебре информации , описывающей основные способы обработки информации. Такая алгебра включает в себя несколько формализмов информатики , которые на первый взгляд кажутся разными: реляционные базы данных, многочисленные системы формальной логики или численные задачи линейной алгебры. Это позволяет разрабатывать общие процедуры обработки информации и, таким образом, унифицировать основные методы информатики, в частности распределенной обработки информации .

Информация касается конкретных вопросов, поступает из разных источников, должна быть агрегирована и может быть сосредоточена на интересующих вопросах. Исходя из этих соображений, информационные алгебры ( Колас 2003 ) являются двухсортными алгебрами. $(\Phi ,D)$ :

Где $\Phi$ является полугруппой , представляющей комбинацию или агрегацию информации, и

$D$ представляет собой решетку доменов представляющую (связанных с вопросами), частичный порядок которых отражает степень детализации домена или вопроса, а также смешанную операцию, фокусировку или извлечение информации.

Информация и ее операции

Точнее, в двусортной алгебре $(\Phi ,D)$ , определены следующие операции

Комбинация: $\otimes :\Phi \otimes \Phi \rightarrow \Phi ,~(\phi ,\psi )\mapsto \phi \otimes \psi$
Фокусировка: $\Rightarrow :\Phi \otimes D\rightarrow \Phi ,~(\phi ,x)\mapsto \phi ^{\Rightarrow x}$

Кроме того, в $D$ определены обычные операции решетки (встреча и объединение).

Аксиомы и определения

Аксиомы двусортной алгебры $(\Phi ,D)$ , помимо аксиом решетки $D$ :

Полугруппа: $\Phi$ является коммутативной полугруппой при сочетании с нейтральным элементом (представляющим пустую информацию).
Распределение фокусировки по комбинации: $(\phi ^{\Rightarrow x}\otimes \psi )^{\Rightarrow x}=\phi ^{\Rightarrow x}\otimes \psi ^{\Rightarrow x}$

Чтобы сосредоточить информацию на $x$ в сочетании с другой информацией в домене $x$ , можно также сначала сфокусировать вторую информацию на $x$ а потом объединить.

Транзитивность фокусировки: $(\phi ^{\Rightarrow x})^{\Rightarrow y}=\phi ^{\Rightarrow x\wedge y}$

Чтобы сосредоточить информацию на $x$ и $y$ , можно сосредоточить его на $x\wedge y$ .

Идемпотентность: $\phi \otimes \phi ^{\Rightarrow x}=\phi$

Информация в сочетании с частью себя не дает ничего нового.

Поддерживать: $\forall \phi \in \Phi ,~\exists x\in D$ такой, что $\phi =\phi ^{\Rightarrow x}$

Каждая информация относится как минимум к одному домену (вопросу).

Двусортная алгебра $(\Phi ,D)$ удовлетворяющее этим аксиомам, называется информационной алгеброй .

Порядок информации

Частичный порядок информации можно ввести, определив $\phi \leq \psi$ если $\phi \otimes \psi =\psi$ . Это означает, что $\phi$ менее информативен, чем $\psi$ если это не добавляет новой информации к $\psi$ . Полугруппа $\Phi$ является полурешеткой относительно этого порядка, т.е. $\phi \otimes \psi =\phi \vee \psi$ . Относительно любого домена (вопроса) $x\in D$ частичный порядок можно ввести, определив $\phi \leq _{x}\psi$ если $\phi ^{\Rightarrow x}\leq \psi ^{\Rightarrow x}$ . Он представляет собой порядок информационного содержания $\phi$ и $\psi$ относительно домена (вопроса) $x$ .

Маркированная информационная алгебра

Пары $(\phi ,x)\$ , где $\phi \in \Phi$ и $x\in D$ такой, что $\phi ^{\Rightarrow x}=\phi$ сформировать помеченную информационную алгебру . Точнее, в двусортной алгебре $(\Phi ,D)\$ , определены следующие операции

Маркировка: $d(\phi ,x)=x\$
Комбинация: $(\phi ,x)\otimes (\psi ,y)=(\phi \otimes \psi ,x\vee y)~~~~$
Проекция: $(\phi ,x)^{\downarrow y}=(\phi ^{\Rightarrow y},y){\text{ for }}y\leq x$

Модели информационных алгебр

Ниже следует неполный список примеров информационных алгебр:

Реляционная алгебра . Редукция реляционной алгебры с естественным объединением в качестве комбинации и обычной проекцией представляет собой помеченную информационную алгебру, см. Пример .
Системы ограничений : Ограничения образуют информационную алгебру ( Jaffar & Maher 1994 ).
Алгебры со значениями полукольца : C-полукольца порождают информационные алгебры ( Бистарелли, Монтанари и Росси, 1997 ); ( Бистарелли и др., 1999 ); ( Колас и Уилсон, 2006 ).
Логика : Многие логические системы порождают информационные алгебры ( Wilson & Mengin 1999 ). Редукты цилиндрических алгебр ( Хенкин, Монк и Тарски, 1971 ) или полиадических алгебр — это информационные алгебры, связанные с логикой предикатов ( Халмос, 2000 ).
Модульные алгебры : ( Бергстра, Хиринг и Клинт 1990 ) ( де Лавалетт 1992 );
Линейные системы : системы линейных уравнений или линейных неравенств порождают информационные алгебры ( Колас, 2003 ).

Проработанный пример: реляционная алгебра

Позволять ${\mathcal {A}}$ быть набором символов, называемых атрибутами (или именами столбцов ). Для каждого $\alpha \in {\mathcal {A}}$ позволять $U_{\alpha }$ быть непустым множеством, набором всех возможных значений атрибута $\alpha$ . Например, если ${\mathcal {A}}=\{{\texttt {name}},{\texttt {age}},{\texttt {income}}\}$ , затем $U_{\texttt {name}}$ могбыть набором строк, тогда как $U_{\texttt {age}}$ и $U_{\texttt {income}}$ оба являются набором неотрицательных целых чисел.

Позволять $x\subseteq {\mathcal {A}}$ . Ан $x$ -tuple — это функция $f$ так что ${\hbox{dom}}(f)=x$ и $f(\alpha )\in U_{\alpha }$ для каждого $\alpha \in x$ Набориз всех $x$ -кортежи обозначаются $E_{x}$ . Для $x$ -кортеж $f$ и подмножество $y\subseteq x$ ограничение $f[y]$ определяется как $y$ -кортеж $g$ так что $g(\alpha )=f(\alpha )$ для всех $\alpha \in y$ .

Отношение  $R$ над $x$ представляет собой набор $x$ -кортежи, т.е. подмножество $E_{x}$ .Набор атрибутов $x$ называется областью $R$ и обозначается $d(R)$ . Для $y\subseteq d(R)$ проекция $R$ на $y$ определяетсяследующее:

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

Соединение отношения $R$ над $x$ и отношение $S$ над $y$ являетсяопределяется следующим образом:

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

В качестве примера позвольте $R$ и $S$ быть следующие отношения:

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}}

Тогда объединение $R$ и $S$ является:

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$ как комбинация и обычная проекция $\pi$ является информационной алгеброй.Операции четко определены, поскольку

$d(R\bowtie S)=d(R)\cup d(S)$
Если $x\subseteq d(R)$ , затем $d(\pi _{x}(R))=x$ .

Легко видеть, что реляционные базы данных удовлетворяют аксиомам помеченной базы данных.информационная алгебра:

полугруппа: $(R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})$ и $R\bowtie S=S\bowtie R$
транзитивность: Если $x\subseteq y\subseteq d(R)$ , затем $\pi _{x}(\pi _{y}(R))=\pi _{x}(R)$ .
комбинация: Если $d(R)=x$ и $d(S)=y$ , затем $\pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)$ .
идемпотентность: Если $x\subseteq d(R)$ , затем $R\bowtie \pi _{x}(R)=R$ .
поддерживать: Если $x=d(R)$ , затем $\pi _{x}(R)=R$ .

Соединения

Алгебры оценки: Отказ от аксиомы идемпотентности приводит к алгебрам нормирования . Эти аксиомы были введены ( Shenoy & Shafer 1990 ) для обобщения схем локальных вычислений ( Lauritzen & Spiegelhalter 1988 ) от байесовских сетей до более общих формализмов, включая функцию доверия, потенциалы возможностей и т. д. ( Kohlas & Shenoy 2000 ). Подробное изложение этой темы в книге см. в Pouly & Kohlas (2011) .
Домены и информационные системы: Компактные информационные алгебры ( Колас, 2003 ) связаны с областями Скотта и информационными системами Скотта ( Скотт, 1970 ); ( Скотт, 1982 ); ( Ларсен и Винскель, 1984 ).
Неопределенная информация: Случайные переменные со значениями в информационных алгебрах представляют собой вероятностные системы аргументации ( Haenni, Kohlas & Lehmann 2000 ).
Семантическая информация: Информационные алгебры вводят семантику, связывая информацию с вопросами посредством фокусировки и комбинирования ( Groenendijk & Stokhof 1984 ); ( Флориди 2004 ).
Информационный поток: Информационные алгебры связаны с информационными потоками, в частности с классификациями ( Barwise & Seligman 1997 ).
Разложение дерева: Информационные алгебры организованы в иерархическую древовидную структуру и разложены на более мелкие задачи.
Теория полугрупп: ...
Композиционные модели: Такие модели могут быть определены в рамках информационных алгебр: https://arxiv.org/abs/1612.02587.
Расширенные аксиоматические основы информационных и оценочных алгебр: Концепция условной независимости является базовой для информационных алгебр, и доступна новая аксиоматическая основа информационных алгебр, основанная на условной независимости и расширяющая старую (см. выше): https://arxiv.org/abs/1701.02658 .

Исторические корни

Аксиомы информационных алгебр выводятся из систему аксиом, предложенную в (Shenoy and Shafer, 1990), см. также (Shafer, 1991).

Ссылки

Барвайз, Дж .; Селигман, Дж. (1997), Информационный поток: логика распределенных систем , Кембридж, Великобритания: номер 44 в Кембриджских трактатах по теоретической информатике, Cambridge University Press.
Бергстра, JA; Хиринг, Дж.; Клинт, П. (1990), «Модульная алгебра», Журнал ACM , 73 (2): 335–372, doi : 10.1145/77600.77621 , S2CID 7910431
Бистарелли, С.; Фарджер, Х. ; Монтанари, У.; Росси, Ф.; Шиекс, Т.; Верфайли, Г. (1999), «CSP на основе полуринга и ценные CSP: структуры, свойства и сравнение» , Constraints , 4 (3): 199–240, doi : 10.1023/A:1026441215081 , S2CID 17232456 , заархивировано из оригинал от 10 марта 2022 г.
Бистарелли, Стефано; Монтанари, Уго; Росси, Франческа (1997), «Удовлетворение ограничений и оптимизация на основе полуринга», Journal of the ACM , 44 (2): 201–236, CiteSeerX 10.1.1.45.5110 , doi : 10.1145/256303.256306 , S2CID 4003767
де Лавалетт, Жерар Р. Ренардель (1992), «Логическая семантика модуляризации» , у Эгона Бёргера; Герхард Ягер; Ганс Кляйне Бюнинг; Майкл М. Рихтер (ред.), CSL: 5-й семинар по логике компьютерных наук , том 626 конспектов лекций по информатике, Springer, стр. 306–315, ISBN 978-3-540-55789-0
Флориди, Лучано (2004), «Очерк теории строго семантической информации» (PDF) , Minds and Machines , 14 (2): 197–221, doi : 10.1023/b:mind.0000021684.50925.c9 , S2CID 3058065
Гроенендейк, Дж.; Стокхоф, М. (1984), Исследования семантики вопросов и прагматики ответов , докторская диссертация, Университет Амстердама.
Хэнни, Р.; Кохлас Дж.; Леманн, Н. (2000), «Вероятностные системы аргументации» (PDF) , в книге Дж. Кохласа; С. Морал (ред.), Справочник по отстранимым рассуждениям и системам управления неопределенностью , Дордрехт: Том 5: Алгоритмы неопределенности и отстранимых рассуждений, Kluwer, стр. 221–287, заархивировано из оригинала 25 января 2005 г.
Халмос, Пол Р. (2000), «Автобиография полиадических алгебр», Logic Journal of the IGPL , 8 (4): 383–392, doi : 10.1093/jigpal/8.4.383 , S2CID 36156234
Хенкин, Л .; Монк, доктор медицинских наук; Тарский, А. (1971), Цилиндрические алгебры , Амстердам: Северная Голландия, ISBN 978-0-7204-2043-2
Джаффар, Дж.; Махер, MJ (1994), «Логическое программирование с ограничениями: обзор», Journal of Logic Programming , 19/20: 503–581, doi : 10.1016/0743-1066(94)90033-7
Колас Дж. (2003), Информационные алгебры: общие структуры для вывода , Springer-Verlag, ISBN 978-1-85233-689-9
Кохлас Дж.; Шеной, П. П. (2000), «Вычисления в алгебрах нормирования», Дж. Колас; С. Морал (ред.), Справочник по отменяемым рассуждениям и системам управления неопределенностью, Том 5: Алгоритмы неопределенности и отстранимых рассуждений , Дордрехт: Kluwer, стр. 5–39
Кохлас Дж.; Уилсон, Н. (2006), Точные и приближенные локальные вычисления в алгебрах оценок, индуцированных полукольцами (PDF) , Технический отчет 06-06, Факультет информатики Фрибурского университета, заархивировано из оригинала 24 сентября 2006 г.
Ларсен, КГ; Винскель, Г. (1984), «Использование информационных систем для эффективного решения уравнений рекурсивной области», Жилль Кан; Дэвид Б. Маккуин; Гордон Д. Плоткин (ред.), Семантика типов данных, Международный симпозиум, София-Антиполис, Франция, 27–29 июня 1984 г., Proceedings , vol. 173 конспектов лекций по информатике, Берлин: Springer, стр. 109–129.
Лауритцен, СЛ; Шпигельхальтер, DJ (1988), «Локальные вычисления с вероятностями на графических структурах и их применение к экспертным системам», Журнал Королевского статистического общества, серия B , 50 (2): 157–224, doi : 10.1111/j.2517- 6161.1988.tb01721.x
Пули, Марк; Колас, Юрг (2011), Общий вывод: объединяющая теория для автоматизированного рассуждения , John Wiley & Sons, ISBN 978-1-118-01086-0
Скотт, Дана С. (1970), Очерк математической теории вычислений , Техническая монография PRG–2, Вычислительная лаборатория Оксфордского университета, Группа исследований по программированию
Скотт, Д.С. (1982), «Области денотационной семантики», М. Нильсен; Э.М. Шмитт (ред.), Автоматы, языки и программирование , Springer, стр. 577–613.
Шафер, Г. (1991), Аксиоматическое исследование вычислений в гипердеревьях , Рабочий документ 232, Школа бизнеса, Канзасский университет.
Шеной, ПП; Шафер, Г. (1990). «Аксиомы вероятности и распространения функции убеждения». У Росса Д. Шахтера; Тод С. Левитт; Лавин Н. Канал; Джон Ф. Леммер (ред.). Неопределенность в искусственном интеллекте 4 . Том. 9. Амстердам: Эльзевир. стр. 169–198. дои : 10.1016/B978-0-444-88650-7.50019-6 . hdl : 1808/144 . ISBN 978-0-444-88650-7 . {{cite book}}: |journal= игнорируется ( помогите )
Уилсон, Ник; Менгин, Жером (1999), «Логическая дедукция с использованием локальной вычислительной среды» , Энтони Хантер; Саймон Парсонс (ред.), Символические и количественные подходы к рассуждению и неопределенности, Европейская конференция, ECSQARU'99, Лондон, Великобритания, 5–9 июля 1999 г., Труды, том 1638 конспектов лекций по информатике , Springer, стр. 386 –396, ISBN 978-3-540-66131-3