Автоматы и сознание
В тумане - POMDP
Цели урока
- Понимать ограничение MDP - полная наблюдаемость нереалистична в большинстве задач
- Освоить концепцию belief state как распределения вероятностей по состояниям
- Уметь применять Байесовское обновление belief (prediction + correction + normalization)
- Видеть ценность информационных действий и трейдофф exploration vs exploitation
- Знать практические методы решения POMDP (POMCP, Deep RL, LLM)
Предварительные знания
- Markov Decision Process (MDP) - урок aut-04-mdp
- Hidden Markov Models (HMM) - урок aut-03-hmm
- Теорема Байеса: P(A|B) = P(B|A)*P(A)/P(B)
Rover Opportunity на Марсе в пыльную бурю, хирург перед разрезом, покерный игрок на финале - все принимают решения без полной информации. POMDP - математика этого.
- NASA Mars Rover (2004) - ориентация в условиях нулевой видимости через particle filter POMDP
- Медицинская диагностика - системы IBM Watson Health используют POMDP для рекомендаций лечения при неполных данных
- AlphaGo Zero (2017) - MCTS по belief space стратегий оппонента, победа над чемпионом мира
- Сурдопереводчики и стенографисты - HMM/POMDP для распознавания речи с 95%+ точностью при 30% шуме
- Диалоговые системы (Siri, Alexa, Claude) - неявный belief через контекст трансформера
Эдвард Сондик и кусочно-линейная ценность
POMDP были формально определены в 1960-х, но алгоритмов решения не было. Сондик в диссертации 1971 года доказал ключевую теорему: оптимальная функция ценности V(b) над belief space - кусочно-линейная и выпуклая. Это значит V(b) = max_{alpha} (alpha * b) где Gamma - конечный набор alpha-векторов. Открытие сделало POMDP вычислимым - вместо континуума нужно хранить конечный набор векторов. Практические алгоритмы появились в 2000-х с PBVI (Pineau et al., 2003) и POMCP (Silver & Veness, 2010).
Когда MDP ломается
**NASA Mars Rover Opportunity, 2004. Ровер потерял ориентацию - пыльная буря стёрла видимость до нуля. GPS на Марсе нет. Датчики дают шум. При этом ровер не мог просто остановиться - 90-дневная миссия, каждый час на счету.** Rover использовал POMDP: не знал точно где находится, но принимал решения, опираясь на распределение вероятностей по возможным позициям.
MDP предполагает полную наблюдаемость: агент знает точное состояние s и выбирает действие a. Но в реальности это почти никогда не так. Врач не видит патологию напрямую - только симптомы. ChatGPT не знает точного намерения пользователя - только текст. Робот внутри здания не получает GPS - только показания датчиков.
MDP: агент точно знает состояние s. Это предположение нарушается в большинстве реальных задач.
| Задача | Что не наблюдается напрямую | Что видит агент |
|---|---|---|
| Медицинская диагностика | Истинный диагноз | Симптомы, результаты анализов |
| Автономный робот | Точная позиция в помещении | Показания лидара, одометрия |
| Покер | Карты противника | Ставки, поведение, стол |
| Диалоговый агент (LLM) | Истинное намерение пользователя | Текст запроса, контекст |
| Финансовое планирование | Будущее состояние рынка | Текущие цены, новости |
Решение - POMDP (Partially Observable Markov Decision Process). Вместо точного состояния агент работает с **belief** - распределением вероятностей по всем возможным состояниям.
Если добавить больше датчиков, POMDP превращается в MDP
Полная наблюдаемость - это идеализация, достижимая только в синтетических задачах
Любой реальный датчик имеет шум. Даже с идеальными датчиками существует неопределённость относительно намерений других агентов, будущих состояний среды, скрытых переменных модели. MDP - удобная аппроксимация, POMDP - более честная модель.
Что главное отличает POMDP от MDP?
Belief State - вера агента о мире
**Belief state b** - это распределение вероятностей по всем возможным состояниям. Для n состояний это вектор из n чисел, где b(s) - вероятность того, что истинное состояние равно s. Все b(s) >= 0 и сумма равна 1.
Belief учитывает всю историю наблюдений и действий. Это компактное резюме всего что агент знает о мире прямо сейчас.
Belief в диалоговом агенте
Пользователь пишет: "исправь ошибку" Начальный belief (равномерный): bug_fix: 0.33 new_feature: 0.33 refactoring: 0.34 Пользователь добавляет: "приложение крашится на iOS" Обновлённый belief: bug_fix: 0.90 // наблюдение сильно указывает на баг new_feature: 0.05 refactoring: 0.05 Claude может не спрашивать - belief достаточно уверен.
Геометрически belief живёт в simplex (симплексе) - области где все вероятности неотрицательны и суммируются в 1. Для 3 состояний это треугольник: вершины - полная уверенность, центр - максимум неопределённости.
| Точка в симплексе | Значение | Пример |
|---|---|---|
| Вершина (1, 0, 0) | Полная уверенность в состоянии 1 | Агент точно знает: это bug_fix |
| Центр (1/3, 1/3, 1/3) | Максимум неопределённости | Агент совсем не знает намерение |
| Середина ребра (0.5, 0.5, 0) | Уверен что одно из двух | Либо bug, либо feature - не refactor |
| Ближе к вершине (0.9, 0.07, 0.03) | Почти уверен | Наблюдения сильно указали на состояние 1 |
Весь алгоритм управления POMDP-агента сводится к одному: поддерживать актуальный belief и выбирать действие, максимизирующее ожидаемую награду с учётом этого belief.
Belief state (0.95, 0.03, 0.02) означает что агент:
Байесовское обновление belief
Когда агент делает действие a и получает наблюдение o, belief обновляется по формуле из двух шагов: prediction (предсказание куда мог попасть) и correction (насколько наблюдение соответствует каждому состоянию). Это в точности Forward algorithm из HMM, расширенный на действия.
| Шаг | Что делается | Формула |
|---|---|---|
| Prediction | Распределить текущий belief по возможным новым состояниям | predicted(s') = sum_s P(s'|s,a) * b(s) |
| Correction | Умножить на вероятность наблюдения в каждом состоянии | unnorm(s') = Z(o|s',a) * predicted(s') |
| Normalization | Разделить на сумму, чтобы получить правильное распределение | b'(s') = unnorm(s') / sum_s unnorm(s') |
Врач обновляет диагноз
Начальный belief: { грипп: 0.6, простуда: 0.4 } Наблюдение: высокая температура (>38°) Likelihood (из медицинских данных): Z(температура | грипп) = 0.9 // часто при гриппе Z(температура | простуда) = 0.3 // реже при простуде Шаг correction (нет перехода состояний - только update на основе obs): unnorm(грипп) = 0.9 * 0.6 = 0.54 unnorm(простуда) = 0.3 * 0.4 = 0.12 Нормализация: total = 0.54 + 0.12 = 0.66 b'(грипп) = 0.54 / 0.66 = 0.818 b'(простуда) = 0.12 / 0.66 = 0.182 Вывод: высокая температура - сильное свидетельство в пользу гриппа.
Связь с HMM: обновление belief в POMDP - это Forward algorithm. Разница: в HMM просто наблюдают последовательность, в POMDP ещё выбирают действия, влияющие на переходы.
Belief обновляется только при наблюдении - действие само по себе не меняет belief
Действие меняет belief через prediction step, наблюдение - через correction step
Если агент делает шаг вправо, он знает что переместился - и даже без нового наблюдения belief уже другой (prediction). Наблюдение потом уточняет этот новый belief (correction). Оба шага обязательны.
Belief: { A: 0.5, B: 0.3, C: 0.2 }. Робот делает шаг вправо: A->B, B->C, C->C (детерминированный). Каков новый belief до наблюдения?
Ценность информации и решение POMDP
**AlphaGo Zero (2017) обыграл лучшего игрока мира в Go, используя MCTS по belief space.** В Go противник скрывает намерения - агент не знает точную стратегию оппонента. AlphaGo строил распределение над стратегиями и выбирал ходы, максимизирующие ожидаемый выигрыш. Информационные действия - зондирующие ходы - были ключевым элементом.
В POMDP существует особый тип действий - **информационные**: они не приближают к цели напрямую, но снижают неопределённость. Уточняющий вопрос, диагностический тест, зондирующий ход - всё это инвестиции в информацию.
Info Gain(a) = H(b) - E_o[H(b' | o, a)], где H(b) - энтропия belief. Вот почему хорошие агенты задают уточняющие вопросы: они максимизируют снижение энтропии относительно стоимости вопроса.
Выбрать: действовать или спросить
Текущая уверенность: P(правильно | belief) = 0.6 Результат немедленного ответа: 5 * 0.6 = 3.0 Альтернатива: уточняющий вопрос (стоимость = 0) После вопроса: P(правильно | новый belief) = 0.95 Результат после вопроса: 5 * 0.95 = 4.75 Вывод: вопрос выгоден, хотя сам по себе не даёт наград. Инвестиция в информацию окупается.
Точное решение POMDP - PSPACE-complete (экспоненциально сложнее MDP). На практике используют приближённые методы:
| Метод | Идея | Когда применять |
|---|---|---|
| PBVI | Сэмплировать точки в belief space, строить alpha-векторы | Небольшие дискретные задачи (до ~100 состояний) |
| POMCP | Monte Carlo Tree Search по belief space | Онлайн планирование, большие задачи |
| QMDP | Решить MDP как если бы состояние стало известно, использовать Q_MDP | Быстрая аппроксимация, когда неопределённость низкая |
| Deep RL + RNN | Нейросеть неявно кодирует belief через историю в hidden state | Непрерывные задачи, большой belief space |
| LLM + контекст | Контекст диалога = неявный belief через attention | Диалоговые агенты, задачи с текстом |
LLM-агенты (ChatGPT, Claude) - это POMDP с неявным belief. Контекст диалога кодирует всю историю наблюдений, attention mechanism вычисляет неявный belief state при каждом шаге генерации.
Всегда лучше сначала собрать всю информацию, потом действовать
Информация имеет цену - оптимальный агент балансирует exploration vs exploitation
Каждый уточняющий вопрос стоит времени и терпения пользователя. Медицинский тест - это процедура с риском и стоимостью. Оптимальный агент задаёт вопрос только если info gain превышает его стоимость. Иногда действовать с 60% уверенностью выгоднее чем задавать 10 вопросов.
Вопросы для размышления
- В каких ситуациях принятия решений, с которыми сталкиваешься в работе программиста, неопределённость о состоянии системы наиболее значима - и как это связано с POMDP?