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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы сосредоточить информацию на ${displaystyle x}$ и ${displaystyle y}$ , можно сфокусировать это на ${displaystyle xwedge y}$ .

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

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

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

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

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

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

Частичный порядок информации может быть введен путем определения ${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 xin D}$ частичный порядок может быть введен путем определения ${displaystyle phi leq _ {x} psi}$ если ${displaystyle phi ^ {Rightarrow x} leq psi ^ {Rightarrow x}}$ . Он представляет собой порядок информационного содержания ${displaystyle phi}$ и ${displaystyle psi}$ относительно домена (вопрос) ${displaystyle x}$ .

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

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

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

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

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

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

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

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

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

А связь ${displaystyle R}$ над ${displaystyle x}$ это набор ${displaystyle x}$ -наборы, т.е. подмножество ${displaystyle E_ {x}}$ .Набор атрибутов ${displaystyle x}$ называется домен из ${displaystyle R}$ и обозначается ${displaystyle d (R)}$ . За ${displaystyle ysubseteq d (R)}$ то проекция из ${displaystyle R}$ на ${displaystyle y}$ определяется следующим образом:

{displaystyle pi _ {y} (R): = {f [y] средний плавник R}.}

В присоединиться отношения ${displaystyle R}$ над ${displaystyle x}$ и отношение ${displaystyle S}$ над ${displaystyle y}$ определяется следующим образом:

{displaystyle Rowtie S: = {fmid fquad (xcup y) {hbox {-tuple}}, quad f [x] в R,; f [y] в S}.}

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

{displaystyle R = {egin {matrix} {exttt {name}} & {exttt {age}} {exttt {A}} & {exttt {34}} {exttt {B}} & {exttt {47}} end {matrix}} qquad S = {egin {matrix} {exttt {name}} & {exttt {доход}} {exttt {A}} & {exttt {20'000}} {exttt {B}} & {exttt {32'000}} end {matrix}}}

Затем соединение ${displaystyle R}$ и ${displaystyle S}$ является:

{displaystyle Rowtie S = {egin {matrix} {exttt {name}} & {exttt {age}} & {exttt {доход}} {exttt {A}} & {exttt {34}} & {exttt {20 '000}} {exttt {B}} & {exttt {47}} & {exttt {32'000}} end {matrix}}}

Реляционная база данных с естественным соединением ${displaystyle owtie}$ как комбинация и обычная проекция ${displaystyle pi}$ является информационной алгеброй. Операции корректно определены, поскольку

${displaystyle d (Rowtie S) = d (R) cup d (S)}$
Если ${displaystyle xsubseteq d (R)}$ , тогда ${displaystyle d (pi _ {x} (R)) = x}$ .

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

полугруппа: ${displaystyle (R_ {1} owtie R_ {2}) owtie R_ {3} = R_ {1} owtie (R_ {2} owtie R_ {3})}$ и ${displaystyle Rowtie S = S owtie R}$
транзитивность: Если ${displaystyle xsubseteq ysubseteq d (R)}$ , тогда ${displaystyle pi _ {x} (pi _ {y} (R)) = pi _ {x} (R)}$ .
сочетание: Если ${displaystyle d (R) = x}$ и ${displaystyle d (S) = y}$ , тогда ${displaystyle pi _ {x} (Rowtie S) = Rowtie pi _ {xcap y} (S)}$ .
идемпотентность: Если ${displaystyle xsubseteq d (R)}$ , тогда ${displaystyle Rowtie pi _ {x} (R) = R}$ .
поддерживать: Если ${displaystyle x = d (R)}$ , тогда ${displaystyle pi _ {x} (R) = R}$ .

Подключения

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

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

Аксиомы для информационных алгебр получены из системы аксиом, предложенной в (Шеной и Шафер, 1990), см. Также (Шафер, 1991).