Основы логики и теории множеств

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

В этой главе мы рассмотрим нечто более фундаментальное:Как описывать «условия»(логика),Как описывать «совокупность объектов»(теория множеств).

В машинном обучении почти всё, что связано с «вероятностью» и «неопределённостью», по своей сути выражается на языке теории множеств; всё, что связано с «условными суждениями» и «алгоритмическими потоками», по своей сути выражается на языке логики.


Основные логические операции: AND, OR, NOT, IMPLIES

Логическое И (AND, символ ∧)

истинно тогда и только тогда, когда p и qоба истинны。

Интуиция: оба условия должны быть выполнены одновременно; если хотя бы одно из них отсутствует, ничего не выйдет — так же, как «ты промокнешь, только если идёт дождь и у тебя нет зонта».

Логическое ИЛИ (OR, символ ∨)

истинно, если p и qхотя бы одно из них истинно。

«Или» в математике — это «включающее или»: когда оба истинны, всё высказывание также истинно. Оно не означает «или то, или другое» из повседневной речи.

Логическое НЕ (NOT, символ ¬)

Оно просто переворачивает значение истинности p: когда p истинно,оно ложно; когда p ложно,оно истинно.

Логическая импликация (IMPLIES, символ ⇒)

Читается как «если p, то q»; это тот случай, который чаще всего противоречит интуиции:

p (антецедент)q (консеквент)Объяснение
истинаистинаистинаОбычный случай
истинаfalsefalseЕдинственный ложный случай: «антецедент истинен, консеквент ложен»
falseистинаистинаЕсли антецедент ложен, всё утверждение истинно
falsefalseистинаЕсли антецедент ложен, всё утверждение истинно

Две самые контринтуитивные строки: когда p ложно, каким бы ни был q,считаютсяистинными。

Пример для понимания: «Если завтра пойдёт дождь (p), я возьму зонт (q)».

Если завтране будет дождя(p ложно), то независимо от того, возьмёте вы зонт или нет, нельзя сказать, что утверждение «ложно», — оно просто ничего не обещает о ситуации «нет дождя».

Логическая эквивалентность (IFF, символ ⇔)

Читается как «p тогда и только тогда, когда q»; это означает, что p и q всегда имеют одинаковое истинностное значение (либо оба истинны, либо оба ложны).

Нажимайте переключатели ниже, чтобы самостоятельно "зажечь" каждую комбинацию и наблюдать результаты четырёх операций.

Интерактивная демонстрация: переключатели истинности для логических операций
Нажимайте переключатели p и q, чтобы переключать между истиной и ложью, а четыре карточки ниже отображают результат каждой логической операции в реальном времени. Обратите внимание, что когда p ложно, p ⇒ q всегда истинно.
p
истина
q
истина
p ∧ q
истина
p ∨ q
истина
¬p
false
p ⇒ q
истина
Попробуйте установить p в "ложь", а q оставить "истина" — p ⇒ q всё равно "истина". Это самая контринтуитивная часть импликации.

Почему эти символы важны для ИИ

Когда вы читаете псевдокод алгоритмов и условные проверки при обучении модели (например, условие срабатывания для "ранней остановки"), всё это комбинации логических выражений.

Модель дерева решений по сути состоит из слоёв суждений "if...then..." (импликация).

Многие теоремы теории вероятностей широко используют логические операции для описания связей между событиями в ходе доказательств.

Примеры

# Вывести полную таблицу истинности с помощью булевых операций Python
# Примечание: в Python нет оператора "импликация"; p ⇒ q эквивалентно (not p) or q

print('p      q      p∧q    p∨q    ¬p     p⇒q')

for p in [True, False]:
    for q in [True, False]:
        implies = (not p) or q     # Импликация: единственный ложный случай — "p истинно и q ложно"
        print(p, q, p and q, p or q, not p, implies)

Выполнение приведённого выше кода даёт следующий вывод:

p      q      p∧q    p∨q    ¬p     p⇒q
True True True True False True
True False False True False False
False True False True True True
False False False False True True

Вторая строка — это то самое единственное «ложное»: p истинно, q ложно, импликация не выполняется.

Упражнение: p = «Сегодня выходной» ложно, q = «Мне нужно идти на работу» истинно. Пожалуйста, определитеистинностное значение.

Нажмите, чтобы увидеть ответ

p ложно. Согласно таблице истинности, независимо от того, каким является q,это истинно.


Понятия множеств: пересечение, объединение, подмножество

Что такое множество?

Множество — это целое, состоящее из «набора определённых вещей», напримерпредставляет множество, содержащее три элемента 1, 2, 3.

СимволЗначениеПример
x является элементом множества A (принадлежит)
x не является элементом множества A
Пустое множество, не содержит элементов
Универсальное множество, "всё" в рамках обсужденияВсе возможные исходы бросания игральной кости

Подмножество

Если каждый элемент множества A также является элементом множества B, то A является Bподмножеством, обозначается как。

Например, тогда。

Объединение, пересечение, разность, дополнение

дизайн:

ДействиеСимволЗначениеРезультат
ОбъединениеЭлементы A и B, объединённые вместе (дубликаты учитываются только один раз)
ПересечениеЭлементы, которые находятся как в A, так и в B
РазницаПринадлежит A, но не принадлежит B
ДополнениеЧасть универсального множества U, не входящая в A, т. е.Зависит от U

Соответствие между операциями над множествами и логическими операциями

Теория множеств и логические операции — это фактически "два языка для одного и того же":

Язык множествЛогический язык

Именно поэтому эти два раздела помещены в одну главу: это два выражения одной и той же лежащей в основе логики.

Нажмите кнопку, чтобы переключать операции над множествами и видеть выделенные области на диаграмме Венна.

Интерактивная демонстрация: диаграмма Венна и операции над множествами
Пусть U = {1..10}, A = {1,2,3,4,5}, B = {4,5,6,7}. Нажмите кнопку, чтобы переключать операции; оранжевая область — выбранный результат.
Universal set box U The normal outlines of the two circles A B Highlight layer: displays according to the selected operation

Примеры

# Операции над множествами в Python: взаимно однозначное соответствие математическим символам
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}
U = set(range(1, 11))     # Универсальное множество {1, 2, ..., 10}

print(A | B)      # Объединение A ∪ B
print(A & B)      # Пересечение A ∩ B
print(A - B)      # Разность A \ B
print(A ^ B)      # Симметрическая разность A △ B (элементы, входящие только в одно из множеств)
print(U - A)      # Дополнение Ā = U \ A

Вывод после выполнения приведённого выше кода:

{1, 2, 3, 4, 5, 6, 7}
{4, 5}
{1, 2, 3}
{1, 2, 3, 6, 7}
{6, 7, 8, 9, 10}

Упражнение:,(В диапазоне 1~12). Найдитеи。

Нажмите, чтобы увидеть ответ


Почему теория вероятностей строится на теории множеств

События — это множества

«Событие» в теории вероятностей по сути является множеством: множеством всех «возможных исходов», удовлетворяющих некоторому условию.

Например, при бросании игральной кости множество, соответствующее событию «выпадение чётного числа», — это。

Операции над вероятностями напрямую соответствуют операциям над множествами

Язык теории вероятностейЯзык теории множествЗначение
A или B происходитПроисходит хотя бы одно из событий A и B
Происходят и A, и BСобытия A и B происходят одновременно
A не происходитДополнение A
A и B несовместныЭти два события не могут происходить одновременно

Формула сложения: принцип включения-исключения

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

Это очень наглядно видно с помощью диаграммы Венна (графического представления множеств).

Условная вероятность

Это читается как «вероятность наступления A при условии, что B уже произошло».

Интуиция: как только мы узнаём, что B произошло, «вселенная» обсуждения сжимается с исходного U до B.

В этот момент вероятность наступления A естественно равна доле «пересечения A и B» в «новой вселенной B».

Прототип теоремы Байеса

Условную вероятность можно также записать в обратном виде:

Переставив это, получаем основную формулу теоремы Байеса:

Это теоретическая основа многих моделей машинного обучения (таких как наивный байесовский классификатор), и её вывод начинается именно с простой интуиции о множествах: «условная вероятность — это доля пересечения множеств».

Классическая задача обнаружения заболеваний лучше всего демонстрирует силу Байеса: точность теста «95%» — это не то же самое, что «вероятность 95% оказаться больным после положительного теста». Перетащите ползунок и рассчитайте сами.

Интерактивная демонстрация: теорема Байеса и тестирование на заболевание
100 точек обозначают 100 человек. Изменяйте распространённость, чувствительность теста и долю ложноположительных результатов, чтобы увидеть, как меняется доля «действительно больных после положительного результата теста».
Больны и положительный результат Больны, но не выявлены Здоровы, но ложноположительный результат Здоровы и отрицательный результат
Попробуйте увеличить распространённость до 1%: даже если чувствительность теста достигает 90%, меньше двух из десяти получивших положительный результат могут быть действительно больны — большое число ложноположительных результатов заглушает истинно положительные.

Примеры

# Теорема Байеса: классический расчёт для выявления заболевания
# A = болен, B = положительный тест

p_a = 0.01       # Распространённость (априорная вероятность)
p_b_given_a = 0.95   # Чувствительность: вероятность того, что больной человек получит положительный результат теста
p_b_given_na = 0.05  # Доля ложноположительных результатов: вероятность того, что здоровый человек получит положительный результат теста

# Формула полной вероятности: P(B) = P(B|A)P(A) + P(B|¬A)P(¬A)
p_b = p_b_given_a * p_a + p_b_given_na * (1 - p_a)

# Теорема Байеса: P(A|B) = P(B|A)P(A) / P(B)
p_a_given_b = p_b_given_a * p_a / p_b
print(p_b)          # Полная вероятность положительного теста составляет примерно 5.9%
print(p_a_given_b)  # Доля истинно положительных среди положительных: только около 16.1%!

Вывод при выполнении приведённого выше кода:

0.059000000000000004
0.16101694915254236

Вывод очень контринтуитивен: точность теста «95%», но вероятность действительно быть больным среди положительных результатов составляет лишь около 16% -- потому что сама распространённость составляет лишь 1%, большое количество ложноположительных результатов заглушает истинно положительные.

В этом и заключается ценность теоремы Байеса: она говорит вам, как использовать новые свидетельства (результат теста), чтобы обновить старые убеждения (распространённость), что также является общим интеллектуальным истоком наивного байесовского классификатора и байесовской оптимизации.

Упражнение: В стандартной колоде из 52 карт событие A = 'вытянуть черву' (13 карт), событие B = 'вытянуть туза' (4 карты, 1 из которых — туз червей). Найдитеи。

Нажмите, чтобы увидеть ответ


Итоги главы

ТемаСуть в одном предложении
Логические операции∧ требует, чтобы оба были истинны, ∨ требует истинности хотя бы одного, ⇒ ложно только когда «антецедент истинен, а консеквент ложен» (наиболее контринтуитивно)
Операции над множествами∪ — это объединение, ∩ — пересечение, и они взаимно однозначно соответствуют логическим операциям
Вероятность и множестваСобытия — это множества; P(A∪B), P(A∩B) и условную вероятность можно интуитивно понять через отношения пересечения множеств
Другие расширения