Цепи Маркова и баланс между исследованием и использованием на Python

Суть простыми словами

ИИ часто приходится действовать в условиях неопределённости. Цепь Маркова моделирует, как система переходит между состояниями с фиксированными вероятностями, а многорукий бандит показывает главный выбор обучения с подкреплением: попробовать новое или использовать то, что пока работало лучше всего.

Предсказывайте будущие состояния с помощью цепи Маркова и балансируйте исследование и использование с epsilon-greedy бандитом.

Главные идеи

В цепи Маркова следующее состояние зависит только от текущего.
Вероятности переходов из одного состояния всегда в сумме дают 1.
Исследование находит лучшие варианты; использование приносит награду от лучшего известного варианта.
Epsilon управляет балансом: чем он больше, тем больше исследования.

Когда это использовать?

Понять, что происходит внутри нейронных сетей и библиотек ИИ.
Разобраться в идее до того, как реализовать её в соответствующих задачах.
Подготовиться к курсам по машинному обучению, собеседованиям и проектам.

Посмотрите в действии

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

Пример кода

Запустить код →

main.py

import random

# Markov chain: tomorrow's weather depends only on today's.
transitions = {"sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}}
dist = {"sunny": 1.0, "rainy": 0.0}
for day in range(1, 4):
    dist = {s: sum(dist[p] * transitions[p][s] for p in dist) for s in dist}
    print(f"day {day}:", {s: round(v, 3) for s, v in dist.items()})

# Epsilon-greedy bandit: usually pick the best arm so far, sometimes explore.
random.seed(1)
true_payouts = [0.3, 0.7]
counts, totals = [0, 0], [0.0, 0.0]
epsilon = 0.1
for _ in range(500):
    if random.random() < epsilon or 0 in counts:
        arm = random.randrange(2)                                  # explore
    else:
        arm = max(range(2), key=lambda a: totals[a] / counts[a])  # exploit
    reward = 1 if random.random() < true_payouts[arm] else 0
    counts[arm] += 1
    totals[arm] += reward
print("pulls per arm:", counts)
print("estimated payouts:", [round(t / c, 2) for t, c in zip(totals, counts)])

Ожидаемый результат

day 1: {'sunny': 0.8, 'rainy': 0.2}
day 2: {'sunny': 0.72, 'rainy': 0.28}
day 3: {'sunny': 0.688, 'rainy': 0.312}
pulls per arm: [25, 475]
estimated payouts: [0.16, 0.7]

Как это работает

Каждый день новые вероятности - это старые, умноженные на вероятности переходов, поэтому «солнечно» за три дня падает с 1.0 до 0.688. Бандит в 10% случаев выбирает случайную ручку, а иначе тянет ручку с лучшим средним на данный момент; вскоре он тратит большинство попыток на лучшую ручку и оценивает её выигрыш примерно в 0.7.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Практические задания

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

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

Запустить в Python IDE →

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи