🎲 Теория вероятностей: где она используется и нужна ли она рядовому разработчику

Расскажем, где может пригодиться теория вероятностей, и как базовое понимание теорвера могло бы в свое время спасти разработчиков iPod от серьезного конфуза.

Теория вероятностей исследует свойства случайных величин, вероятности наступления случайных событий и их взаимосвязь. Первой серьезной попыткой использования математики для вычисления вероятностей стала «Книга об азартных играх» миланского врача, математика и заядлого игрока Джероламо Кардано, написанная в 1563 году. Брошюра оставалась неизданной почти 100 лет; когда ее наконец-то издали, свой вклад в теорию вероятностей уже внесли Христиан Гюйгенс, Блез Паскаль и Пьер Ферма.

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

• В физике для анализа квантовых событий и случайных процессов в наноэлектронике.
• В экономике и финансах для создания моделей риска и определения вероятности колебаний на рынке ценных бумаг. Один из самых известных примеров использования теории вероятностей в финансах – модель Блэка-Шоулза для определения цены опционов на акции.
• В биоинформатике для анализа биологических данных – последовательностей ДНК, РНК и белков. Теорвер помогает определить вероятность существования определенной последовательности нуклеотидов и оценить ее значимость для функционирования гена. Кроме того, теорвер используют для анализа геномных данных и определения генетических взаимодействий: вероятностные модели помогают выявить связь между генами и заболеваниями, оценить риски наследственности, а также помочь в разработке новых лекарств и терапий.
• В математической статистике для анализа данных, проверки статистических гипотез и прогнозирования.
• В инженерно-технических расчетах для оценки надежности систем, прогнозирования отказов и определения вероятности возникновения аварийных ситуаций.
• В разработке ПО – в криптографии, анализе данных, машинном обучении, тестировании и оптимизации алгоритмов. С недавних пор вероятностное программирование стало считаться новой парадигмой: появилось первое поколение вероятностных языков программирования – специфических диалектов существующих ЯП, – которые оптимально подходят для создания систем, помогающих принимать решения в условиях неопределенности.

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

Зачем разработчику теория вероятностей

Как уже упоминалось выше, теория вероятностей применяется, прежде всего, в сложных отраслях разработки. Но это не значит, что разработчику софта попроще никогда не придется с ней столкнуться – вот один интересный случай из реальной жизни.

Недостаточно случайный random

Пользователи первых iPоd'ов были сильно разочарованы функцией Shuffle: они ожидали, что список воспроизведения будет перемешиваться так, чтобы треки воспроизводились в совершенно случайном порядке и без повторов. В реальности же плейлисты получались странными: многие песни сохраняли оригинальный альбомный порядок, некоторые проигрывались очень редко, а другие повторялись несколько раз подряд. Стиву Джобсу даже пришлось объяснять публике, что именно так и работает функция рандомизации. Это действительно так – использование генератора псевдослучайных чисел в любом языке программирования приводит к не самому случайному результату, как это демонстрирует, например, функция random в Python:

>>> import random
>>> print(*[random.randint(1, 12) for i in range(12)])
9 9 9 6 2 3 5 9 8 12 10 4

Пользователей это объяснение не удовлетворило, и разработчикам пришлось делать алгоритм смешивания «менее случайным». Неизвестно, как именно программисты Apple решили эту проблему: возможно, воспользовались алгоритмом тасования Фишера-Йетса. В том же Python этот алгоритм используется в методе random.shuffle и выдает результат, который понравился бы любому владельцу iPоd'а:

>>> lst = [int(i) for i in range(1, 13)]
>>> random.shuffle(lst)
>>> print(*lst)
9 6 1 10 12 2 7 5 11 4 8 3

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

import random
import math

# Количество треков в плейлисте
num_elements = 120

# Вероятность того, что хотя бы два трека будут одинаковыми
collision_prob = 1 - (1 - 1 / num_elements)**num_elements

# Вероятность того, что все треки уникальны
uniqueness_prob = 1 - collision_prob

print(f"Процент вероятности того, что все треки в списке будут уникальными: {uniqueness_prob * 100:.2f}%")

Результат:

Процент вероятности того, что все треки в списке будут уникальными: 36.63%

Среднюю уникальность списков можно определить эмпирическим путем. Проведем 10000 испытаний:

import random

num_tests = 10000
uniqueness_percentages = []

for _ in range(num_tests):
   list_numbers = [random.randint(1, 120) for _ in range(120)]
   unique_set = set(list_numbers)
   # Если количество элементов в множестве равно количеству в списке, то список уникален
   if len(unique_set) == len(list_numbers):
       uniqueness_percentages.append(100)
   else:
       uniqueness_percentages.append((len(unique_set) / len(list_numbers)) * 100)

# Вычисление среднего процента уникальности
average_uniqueness = sum(uniqueness_percentages) / num_tests
print(f"Средний процент уникальности: {average_uniqueness:.2f}%")

Результат показывает, что в среднем сгенерированные без специальных алгоритмов списки будут на ≈36,7% состоять из повторяющихся элементов:

Средний процент уникальности: 63.33%

Как теория вероятностей используется в разработке

Теория вероятностей тесно связана со статистикой и комбинаторикой: во всех приведенных ниже примерах подразумевается использование статистических и комбинаторных методов наряду с вероятностными.

Машинное обучение

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

Наивный байесовский классификатор – простой алгоритм машинного обучения, который использует теорию вероятностей для классификации данных. Алгоритм предполагает, что все признаки независимы друг от друга – это обеспечивает быструю и эффективную обработку больших объемов данных. Наивный Байес помогает классифицировать текстовые документы, фильтровать спам, распознавать речь.

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

Скрытые марковские модели – вероятностные модели, которые используют для анализа последовательностей данных, где каждое состояние не наблюдается напрямую, но может быть выведено из наблюдаемых данных. Такие модели состоят из конечного числа скрытых состояний, в которых может находиться система, и наблюдаемых событий, которые описывают систему, но не полностью. Каждое состояние имеет определенную вероятность перехода в другое скрытое состояние, и вероятности переходов определяются только текущим скрытым состоянием.

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

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

Анализ данных и Data Science

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

Предсказание будущих результатов – с помощью теории вероятности прогнозируют будущие результаты на основе имеющихся данных. Модели, основанные на вероятностных методах, могут прогнозировать показатели эффективности бизнеса, поведение пользователей и т.д.

Классификация данных – уже упомянутые байесовские сети помогают определить, к какому классу должен быть отнесен определенный объект.

Анализ неопределенности – теория вероятности помогает оценить риски и вероятности появления разных событий и исходов.

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

Анализ временных рядов – вероятностные модели помогают предсказать доходы, расходы и другие показатели, которые зависят от множества различных факторов.

Криптография

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

Анализ стойкости шифров – теорвер помогает определить вероятность расшифровки сообщения без знания ключа шифрования. Методы теории вероятностей применяют для брутфорс-атак (перебора ключей) на криптографические алгоритмы и для определения стойкости алгоритмов перед их использованием.

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

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

Что почитать по теории вероятностей и статистике

Рекомендуем начать с увлекательной книги «Игра случая. Математика и мифология совпадения» Джозефа Мазура. Минимум сухой теории и вычислений, максимум поразительных историй о мистических совпадениях, которые можно объяснить математически – то, что нужно, чтобы избавиться от мыслей о том, что теория вероятностей – это нечто невероятно сложное и невыносимо скучное.

После «Игры случая» можно переходить к признанной классике – книгам Е. С. Вентцель, написанным самостоятельно и в соавторстве с Л. А. Овчаровым:

• «Теория вероятностей (первые шаги)», 1977
• «Теория вероятностей», 2006
• «Задачи и упражнения по теории вероятностей», 2003
• «Прикладные задачи теории вероятностей», 1983
• «Теория вероятностей и ее инженерные приложения», 2000

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

• «Задачник-практикум по теории вероятностей с элементами комбинаторики и математической статистики», Н. Я. Виленкин, В. Г. Потапов. Это сборник интересных задач, которые можно использовать для подготовки к олимпиаде (или к собеседованию). Все задачи снабжены ответами, а сложные задания – подробными решениями.
• «Руководство к решению задач по теории вероятностей и математической статистике», В. Е. Гмурман. Задачи здесь расположены в порядке возрастания сложности.
• «Теория вероятностей и математическая статистика», Н. Ш. Кремер. Это одновременно и учебник, и руководство по решению практических задач, причем основное внимание здесь уделяется финансово-экономическим задачам.
• «Теория вероятностей и математическая статистика. Конспект лекций», А. И. Волковец, А. Б Гуринович. Этот сборник состоит из 17 лекций, которые охватывают типовую современную программу изучения теорвера в вузе.
• «Теория вероятности. Курс лекций НГУ», Н. И. Чернова. Еще один сборник университетских лекций, в который входит весь необходимый минимум теорвера для решения практических экономических задач.

От теории – к практике

Из книг можно почерпнуть необходимую теоретическую базу и основные подходы к решению умеренно сложных задач. Однако в ходе разработки сложных вероятностных моделей начинающие программисты неизбежно сталкиваются с одним и тем же вопросом – как воплотить теоретические знания в коде, который решает практические задачи. Эту проблему успешно решила «Библиотека программиста» на курсе Математика для Data Science – приходи, все прояснится.