Условная алгебра событий

Стандартная булева алгебра событий — это набор событий, связанных друг с другом знакомыми операциями и , или , и not . Алгебра условных событий ( УЭА ) содержит не только обычные события, но и условные события, которые имеют вид «если А , то В ». Обычная цель CEA - дать возможность определить функцию вероятности P , которая удовлетворяет уравнению P (если A , то B ) = P ( A и B ) / P ( A ).

Мотивация

В стандартной теории вероятностей событие представляет собой набор результатов, любой из которых будет возникновением события. P ( A ), вероятность события A , представляет собой сумму вероятностей всех A -исходов, P ( B ) является суммой вероятностей всех B -исходов, а P ( A и B ) является суммой вероятности всех исходов, которые являются как A -исходами, так и B -исходами. Другими словами, и , обычно обозначаемые логическим символом ∧, интерпретируются как пересечение множеств: P ( A ∧ B ) = P ( A ∩ B ). Точно так же или , ∨ становится объединением множеств, ∪, а не , ¬ становится дополнением множеств, ′. Любая комбинация событий с использованием операций и , или , а также not также является событием, а присвоение вероятностей всем результатам генерирует вероятность для каждого события. С технической точки зрения это означает, что набор событий и три операции вместе составляют булеву алгебру множеств с соответствующей функцией вероятности .

P (если A , то B ) обычно интерпретируется не как обычная вероятность — не конкретно как P ( A ′ ∪ B ) — а как условная вероятность B при заданном A , P ( B | A ) = P ( A ∩ Б ) / п ( А ). Возникает вопрос: а как насчет вероятности типа P (если A , то B , а если C , то D )? На этот вопрос не существует стандартного ответа. Для обеспечения согласованности потребуется обработка if-then как бинарной операции →, такой, что для условных событий A → B и C → D , P ( A → B ) = P ( B | A ), P ( C → D ) = P ( D | C ), а P (( A → B ) ∧ ( C → D )) четко определено и разумно. Именно такую обработку пытаются обеспечить алгебры условных событий. ^[1]

Типы условной алгебры событий

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

1. Функция вероятности подтверждает обычные аксиомы .

2. Для любых двух обычных событий A и B , если P ( A ) > 0, то P ( A → B ) = P ( B | A ) = P ( A ∧ B )/ P ( A ).

3. Для обычного события A и приемлемой функции вероятности P , если P ( A ) > 0, то PA _A = P ( ⋅ | A ), функция, полученная путем обусловления , также является приемлемой функцией вероятности.

Однако Дэвид Льюис (1976) показал , что эти условия могут быть выполнены только тогда, когда есть только два возможных результата — как, скажем, при одном подбрасывании монеты. При наличии трех или более возможных результатов построение функции вероятности требует выбора, какое из трех вышеуказанных условий следует нарушить. Интерпретация A → B как A ′ ∪ B дает обычную булеву алгебру, которая нарушает условие 2. При использовании CEA выбор делается между 1 и 3.

CEA трехмерного мероприятия

CEA с тремя событиями черпают вдохновение из трехзначной логики , где идентификация логического соединения, дизъюнкции и отрицания с помощью простых операций над множествами больше не применяется. Для обычных событий A и B тройное событие A → B происходит, когда происходят оба события A и B , не происходит, когда происходит A , но B не происходит , и остается неопределенным, когда A не происходит. (Термин «три события» взят из Финетти (1935): triévénement .) Обычные события, которые никогда не остаются неопределенными, включаются в алгебру как три события, обусловленные Ω, пустым событием, представленным всем выборочным пространством результаты; образом, A становится Ω → A. таким

Поскольку существует много трехзначных логик, существует множество возможных трехсобытийных алгебр. Однако два типа вызвали больший интерес, чем остальные. В одном типе A ∧ B и A ∨ B являются нерешительными только тогда, когда оба A и B не определены; когда есть только один из них, соединение или дизъюнкция следует за другим соединением или дизъюнктом. Когда отрицание обрабатывается очевидным способом, когда ¬ A не определено только в случае, если A не определено, этот тип алгебры трех событий соответствует трехзначной логике, предложенной Собоциньским (1920) и поддерживаемой Белнапом (1973), а также подразумеваемой «квазисоюзию» Адамса (1975) для кондиционалов. Шай (1968) был первым, кто предложил алгебраическую трактовку, которую Калабрезе (1987) развил более правильно. ^[2]

Другой тип CEA с тремя событиями обрабатывает отрицание так же, как и первый, но он рассматривает соединение и дизъюнкцию как минимальную и максимальную функции соответственно, с возникновением как высоким значением, отказом как низким значением и нерешительностью между ними. Этот тип алгебры трех событий соответствует трехзначной логике, предложенной Лукасевичем (1920), а также одобренной де Финетти (1935). Гудман, Нгуен и Уокер (1991) в конечном итоге предоставили алгебраическую формулировку.

Вероятность любого тройного события определяется как вероятность того, что оно произойдет, деленная на вероятность того, что оно произойдет или не произойдет. ^[3] При таком соглашении условия 2 и 3, приведенные выше, удовлетворяются двумя ведущими типами CEA с тремя событиями. Однако условие 1 не выполняется. В алгебре типа Собоциньского ∧ не распределяется по ∨, поэтому P ( A ∧ ( B ∨ C )) и P (( A ∧ B ) ∨ ( A ∧ C )) не обязательно должны быть равны. ^[4] В алгебре типа Лукасевича ∧ распределяется по ∨, но не по исключительным или, $\oplus$ ( А $\oplus$ B = ( А ∧ ¬ B ) ∨ (¬ A ∧ B )). ^[5] Кроме того, трехсобытийные CEA не являются дополняемыми решетками , а только псевдодополняемыми , потому что в общем случае ( A → B ) ∧ ¬( A → B ) не может возникнуть, но может быть неопределенным и, следовательно, не идентично Ω → ∅, нижнему элементу решетка. Это означает, что P ( C ) и P ( C $\oplus$ (( A → B ) ∧ ¬( A → B ))) могут отличаться, хотя классически это не так.

Пространство продуктов CEA

Если Р (если А , то В ) рассматривать как вероятность того, что А -и -В произойдет раньше А -и-не- В в серии испытаний, это можно вычислить как бесконечную сумму простых вероятностей: вероятность А ) -и- В в первом испытании плюс вероятность не- А (и либо В, либо не- В в первом испытании и А -и- В во втором, плюс вероятность не- А в первом испытании. первые два испытания и A - и - B в третьем и так далее, то есть P ( A ∧ B ) + P (¬ A ) P ( A ∧ B ) + P (¬ A ) ²P ( A ∧ B ) + … или, в факторизованной форме, P ( A ∧ B )[1 + P (¬ A ) + P (¬ A ) ² +…]. Поскольку второй множитель представляет собой разложение в ряд Маклорена 1 / [1 – P ( ¬A )] = 1 / P ( A ), бесконечная сумма равна P ( A ∧ B ) / P ( A ) = P ( B | A ).

Бесконечная сумма сама по себе является простой вероятностью, но пространство выборки теперь содержит не обычные результаты отдельных испытаний, а бесконечные последовательности обычных результатов. Таким образом, условная вероятность P ( B | A ) превращается в простую вероятность P ( B → A ) путем замены Ω, выборочного пространства всех обычных результатов, на Ω*, выборочного пространства всех последовательностей обычных результатов, и путем идентификации условное событие A → B с набором последовательностей, в которых первый ( A ∧ B )-исход предшествует первому ( A ∧ ¬ B )-исходу. В декартовых обозначениях произведения Ω* = Ω × Ω × Ω × …, а A → B — бесконечное объединение [( A ∩ B ) × Ω × Ω × …] ∪ [ A ′ × ( A ∩ B ) × Ω × Ω × …] ∪ [ А ′ × А ′ × ( А ∩ B ) × Ω × Ω × …] ∪ …. Безусловное событие A снова представлено условным событием Ω A. → ^[6] В отличие от CEA с тремя событиями, этот тип CEA поддерживает идентификацию ∧, ∨ и ¬ с помощью знакомых операций ∩, ∪ и ′ не только для обычных безусловных событий, но и для условных. Поскольку Ω* — это пространство, определяемое бесконечно длинным декартовым произведением, булева алгебра подмножеств условных событий Ω* называется пространством-произведением CEA. Этот тип СЕА был введен ван Фраассеном (1976) в ответ на результат Льюиса, а позже независимо открыт Гудманом и Нгуеном (1994).

Функции вероятности, связанные с CEA в пространстве продуктов, удовлетворяют условиям 1 и 2, указанным выше. Однако для данной функции вероятности P , которая удовлетворяет условиям 1 и 2, если P ( A 0, можно показать, что P _A ( C | B ) = P ( C | A ∧ B ) и PA ₍ ) > B → C ) знак равно п ( B ∧ C | А ) + п ( B ′ | А ) п ( C | B ). ^[7] Если A , B и C попарно совместимы, но P ( A ∧ B ∧ C ) = 0, то P ( C | A ∧ B ) = P ( B ∧ C | A ) = 0, но P ( B ′ | A ) P ( C | B > 0. Следовательно, ( _→ B B C ) не всегда равно PA ₍ ) C | PA ). Поскольку P _A не соответствует условию 2, P не соответствует условию 3.

Вложенное если-то

А как насчет вложенных условных конструкций? В CEA с тремя событиями право-вложенные конструкции обрабатываются более или менее автоматически, поскольку естественно сказать, что A → ( B → C ) принимает значение B → C (возможно, неопределённое), когда A истинно и не определено . когда А ложно. Однако левое вложение требует более осознанного выбора: когда A → B не определено, должно ли ( A → B ) → C быть неопределенным или оно должно принимать значение C ? Мнения различаются. Калабрезе придерживается последней точки зрения, отождествляя ( A → B ) → ( → D ) с ((¬ A ∨ B ) ∧ C ) → D. C ^[8]

При использовании CEA в пространстве продукта вложенные условные выражения требуют вложенных конструкций последовательностей: для оценки P (( A → B ) → ( C → D )) требуется выборочное пространство метапоследовательностей последовательностей обычных результатов. Вероятности обычных последовательностей рассчитываются, как и раньше. Для данной серии испытаний, исходами которых являются последовательности обычных исходов, P (( A → B ) → ( C → D )) равно P ( C → D | A → B ) = P (( A → B ) ∧ ( C → D )) / P ( A → B ), вероятность того, что (( A → B ) ∧ ( C → B )) -последовательность встретится перед (( A → B ) ∧ ¬( C → B )) -последовательность. Итерации условных операторов более высокого порядка требуют метапоследовательных конструкций более высокого порядка. ^[9]

В любом из двух ведущих типов трехсобытийного CEA A → ( B → C ) = ( A ∧ B ) → C . ^[10] CEA для продуктового пространства, с другой стороны, не поддерживают эту идентичность. Последний факт можно вывести из уже отмеченного невыполнения P _A ( B → C ) равенства P _A ( C | B ), поскольку P _A ( C | B ) = P (( A ∧ B ) → C ) и P _A ( B → C ) = P ( A → ( B → C )). Однако для прямого анализа рассмотрим метапоследовательность, первая последовательность членов которой начинается с ( A ∧ ¬ B ∧ C )-исхода, за которым следует (¬ A ∧ B ∧ C )-исход, за которым следует ( A ∧ B ∧ ¬ C )-исход. Эта метапоследовательность будет принадлежать событию A → ( B → C ), поскольку первая последовательность-член является ( A ∧ ( B → C )) -последовательностью, но метапоследовательность не будет принадлежать событию ( A ∧ B ) → C , поскольку первая последовательность-член является (( A ∧ B ) → ¬ C )-последовательностью.

Приложения

Первоначальный стимул для CEA является теоретическим, а именно, проблемой реагирования на результат Льюиса, но были предложены практические приложения. Если, например, события A и C включают сигналы, излучаемые военными радиолокационными станциями, а события B и D связаны с запусками ракет, противостоящая военная сила с системой противоракетной обороны, управляемой ИИ, может захотеть, чтобы система была способна вычислить P (( A → B ) ∧ ( C → D )) и/или P (( A → B ) → ( C → D )). ^[11] Другие приложения варьируются от интерпретации изображений ^[12] для обнаружения атак типа «отказ в обслуживании» в компьютерных сетях. ^[13]

Примечания

^ В литературе по CEA на самом деле используется ( B | A ) для обозначения «если A , то B », но из-за этого соглашения некоторые моменты сложнее четко сформулировать. для улучшения разборчивости в настоящей статье используется более знакомое A → B. По этой причине, а также
^ Шай фактически определил две алгебры, одну связанную с ∧, а другую с ∨. Этой линии развития не последовали другие.
^ Де Финетти 1935, с. 184. Технически существует две функции вероятности: P , которая распространяется на обычные события, и P *, которая определяется P и распространяется на условные события. Эта нотационная тонкость здесь будет проигнорирована.
^ Рассмотрим случай, когда A истинно, B не определено, а C ложно.
^ С А $\oplus$ B не определился, когда будет A или B , сравните A ∧ ( B $\oplus$ С ) и ( А ∧ B ) $\oplus$ ( A ∧ C ), когда A не определено, а B и C оба верны.
^ Поскольку Ω ∩ A = A и Ω′ = ∅, бесконечное объединение, представляющее Ω → A, сводится к A × Ω × Ω × Ω ×….
^ Гудман, Малер и Нгуен 1999, с. 7, дает формулу, необходимую для получения последнего результата: P (( A → B ) ∧ ( C → D )) = [ P ( A ∧ B ∧ C ∧ D ) + P ( A ′ ∧ C ∧ D ) P ( B А C ) + ( C ′ ∧ А ∧ B ) п ( D | п )] / п ( А ∨ C ). Интерес представляет особый случай P ((Ω → A ) ∧ ( B → C )).
^ Калабрезе 1987, с. 217.
^ Гудман и Нгуен 1995, стр. 281-283.
^ Это тождество по логике соответствует закону импорта-экспорта, как его называют.
^ Гудман, Малер и Нгуен 1999.
^ Келли, Дерин и Гонг 1999.
^ Сан и др. 2014.

Ссылки

Адамс, EW 1975. Логика условных предложений. Д. Райдель, Дордрехт.

Бамбер Д., Гудман И.Р. и Нгуен Х.Т. 2004. «Вывод из условного знания». Мягкие вычисления 8: 247–255.

Белнап, Н.Д. 1973. «Ограниченная количественная оценка и условное утверждение», в Х. Леблане (редактор), « Истина, синтаксис и модальность» , Северная Голландия, Амстердам. 48–75.

Калабрезе, П. 1987. «Алгебраический синтез основ логики и вероятности». Информационные науки 42:187-237.

Финетти, Бруно. 1935. «Логика вероятности». Материалы Международного научно-философского конгресса . Париж.

ван Фраассен, Бас К. 1976. «Вероятности условных предложений» в книге У.Л. Харпера и К.А. Хукера (ред.), « Основы теории вероятностей, статистических выводов и статистических теорий науки» , том И.Д. Рейделя, Дордрехт, стр. 261–308. .

Гудман, И. Р., Малер, Р. П. С. и Нгуен, Х. Т. 1999. «Что такое алгебра условных событий и почему вас это должно волновать?» Труды SPIE , Vol. 3720.

Гудман, И.Р., Нгуен, Х.Т. и Уокер, Э.А. 1991. Условный вывод и логика для интеллектуальных систем: теория безмерной обусловленности . Офис начальника военно-морских исследований, Арлингтон, Вирджиния.

Гудман, И. Р. и Нгуен, Х. Т. 1994. «Теория условной информации для вероятностного вывода в интеллектуальных системах: II, подход пространства продуктов; III Математическое приложение». Информационные науки 76:13-42; 75: 253-277.

Гудман, И. Р. и Нгуен, Х. Т. 1995. «Математические основы условных выражений и их вероятностные назначения». Международный журнал неопределенности, нечеткости и систем, основанных на знаниях 3 (3): 247-339

Келли, Пенсильвания, Дерин, Х. и Гонг, В.-Б. 1999. «Некоторые применения условных событий и случайных наборов для оценки изображений и моделирования систем». SPIE Proceedings 3720: 14-24.

Лукасевич, Дж. 1920. «О трехзначной логике» (на польском языке). Философское движение 5: 170–171. Английский перевод: «О трехзначной логике», в Л. Борковски (редактор), Избранные работы Яна Лукасевича , Северная Голландия, Амстердам, 1970, стр. 87–88. ISBN 0-7204-2252-3

Шай, Геза. 1968. «Алгебра условных событий». Журнал математического анализа и приложений 24: 334-344.

Собоциньский, Б. 1952. «Аксиоматизация частичной системы трехзначного исчисления высказываний». Журнал вычислительных систем 1 (1): 23-55.

Сунь Д., Ян К., Цзин Х., Лв Б. и Ван Ю. 2014. «Обнаружение аномального сетевого трафика на основе алгебры условных событий». Прикладная механика и материалы 644-650: 1093-1099.

[1] В литературе по CEA на самом деле используется ( B | A ) для обозначения «если A , то B », но из-за этого соглашения некоторые моменты сложнее четко сформулировать. для улучшения разборчивости в настоящей статье используется более знакомое A → B. По этой причине, а также

[2] Шай фактически определил две алгебры, одну связанную с ∧, а другую с ∨. Этой линии развития не последовали другие.

[3] Де Финетти 1935, с. 184. Технически существует две функции вероятности: P , которая распространяется на обычные события, и P *, которая определяется P и распространяется на условные события. Эта нотационная тонкость здесь будет проигнорирована.

[4] Рассмотрим случай, когда A истинно, B не определено, а C ложно.

[5] С А $\oplus$ B не определился, когда будет A или B , сравните A ∧ ( B $\oplus$ С ) и ( А ∧ B ) $\oplus$ ( A ∧ C ), когда A не определено, а B и C оба верны.

[6] Поскольку Ω ∩ A = A и Ω′ = ∅, бесконечное объединение, представляющее Ω → A, сводится к A × Ω × Ω × Ω ×….

[7] Гудман, Малер и Нгуен 1999, с. 7, дает формулу, необходимую для получения последнего результата: P (( A → B ) ∧ ( C → D )) = [ P ( A ∧ B ∧ C ∧ D ) + P ( A ′ ∧ C ∧ D ) P ( B А C ) + ( C ′ ∧ А ∧ B ) п ( D | п )] / п ( А ∨ C ). Интерес представляет особый случай P ((Ω → A ) ∧ ( B → C )).

[8] Калабрезе 1987, с. 217.

[9] Гудман и Нгуен 1995, стр. 281-283.

[10] Это тождество по логике соответствует закону импорта-экспорта, как его называют.

[11] Гудман, Малер и Нгуен 1999.

[12] Келли, Дерин и Гонг 1999.

[13] Сан и др. 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]