Основы логики и теории множеств
В предыдущих главах мы познакомились с алгеброй, функциями и геометрией — все они имеют дело с «числами» и «фигурами».
В этой главе мы рассмотрим нечто более фундаментальное:Как описывать «условия»(логика),Как описывать «совокупность объектов»(теория множеств).
В машинном обучении почти всё, что связано с «вероятностью» и «неопределённостью», по своей сути выражается на языке теории множеств; всё, что связано с «условными суждениями» и «алгоритмическими потоками», по своей сути выражается на языке логики.
Основные логические операции: AND, OR, NOT, IMPLIES
Логическое И (AND, символ ∧)
истинно тогда и только тогда, когда p и qоба истинны。
Интуиция: оба условия должны быть выполнены одновременно; если хотя бы одно из них отсутствует, ничего не выйдет — так же, как «ты промокнешь, только если идёт дождь и у тебя нет зонта».
Логическое ИЛИ (OR, символ ∨)
истинно, если p и qхотя бы одно из них истинно。
«Или» в математике — это «включающее или»: когда оба истинны, всё высказывание также истинно. Оно не означает «или то, или другое» из повседневной речи.
Логическое НЕ (NOT, символ ¬)
Оно просто переворачивает значение истинности p: когда p истинно,оно ложно; когда p ложно,оно истинно.
Логическая импликация (IMPLIES, символ ⇒)
Читается как «если p, то q»; это тот случай, который чаще всего противоречит интуиции:
| p (антецедент) | q (консеквент) | Объяснение | |
|---|---|---|---|
| истина | истина | истина | Обычный случай |
| истина | false | false | Единственный ложный случай: «антецедент истинен, консеквент ложен» |
| false | истина | истина | Если антецедент ложен, всё утверждение истинно |
| false | false | истина | Если антецедент ложен, всё утверждение истинно |
Две самые контринтуитивные строки: когда p ложно, каким бы ни был q,считаютсяистинными。
Пример для понимания: «Если завтра пойдёт дождь (p), я возьму зонт (q)».
Если завтране будет дождя(p ложно), то независимо от того, возьмёте вы зонт или нет, нельзя сказать, что утверждение «ложно», — оно просто ничего не обещает о ситуации «нет дождя».
Логическая эквивалентность (IFF, символ ⇔)
Читается как «p тогда и только тогда, когда q»; это означает, что p и q всегда имеют одинаковое истинностное значение (либо оба истинны, либо оба ложны).
Нажимайте переключатели ниже, чтобы самостоятельно "зажечь" каждую комбинацию и наблюдать результаты четырёх операций.
Почему эти символы важны для ИИ
Когда вы читаете псевдокод алгоритмов и условные проверки при обучении модели (например, условие срабатывания для "ранней остановки"), всё это комбинации логических выражений.
Модель дерева решений по сути состоит из слоёв суждений "if...then..." (импликация).
Многие теоремы теории вероятностей широко используют логические операции для описания связей между событиями в ходе доказательств.
Примеры
# Примечание: в 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 |
Соответствие между операциями над множествами и логическими операциями
Теория множеств и логические операции — это фактически "два языка для одного и того же":
| Язык множеств | Логический язык |
|---|---|
Именно поэтому эти два раздела помещены в одну главу: это два выражения одной и той же лежащей в основе логики.
Нажмите кнопку, чтобы переключать операции над множествами и видеть выделенные области на диаграмме Венна.
Примеры
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% оказаться больным после положительного теста». Перетащите ползунок и рассчитайте сами.
Примеры
# 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) и условную вероятность можно интуитивно понять через отношения пересечения множеств |