Моделирование поведения сложных динамических систем

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

Структура системы
Игра генерирует некоторые события
Их надо оценить и прокомментировать
переводчик
Система
генерации текста
ИГРА
Система комментирования

Структура системы
Игра генерирует некоторые события
Их надо оценить и прокомментировать
Проблема: широкий класс предметных областей вынуждает использовать адаптирующийся к конкретной задаче алгоритм.
переводчик
Система
генерации текста
ИГРА
Система комментирования

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

Что такое модель поведения?
Внутреннее поведение
скрыто
Вход
Выход
Наблюдаемое поведение

Что такое модель поведения?
Внутреннее поведение
скрыто
Вход
модель
Выход
Выход

Что такое модель поведения?
Оценки качества модели
Ошибка обучения
– Суммированная по обучающей выборке норма невязки модели
Ошибка обобщения
– Норма невязки модели на каких-либо новых данных
Как измеряют качество модели?
Основной целью при обучении является уменьшение ошибки обобщения.
Точно смоделировать систему невозможно.

Адекватно оценивать настоящее
Предсказывать будущее
Зачем нужна модель поведения?
предсказывать следующий выход системы на основе входа и наблюдаемого поведения системы.
выход моделируемой системы
=
выход модели

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

Особенности нашей задачи
Внутреннее поведение
скрыто
Вход
модель
Выход
Выход
?

Обзор некоторых моделей
Нейронные сети
Самоорганизующиеся карты Кохонена.
Статистические модели
Скрытые Марковские модели.
Synapse [http://www.peltarion.com/products/synapse/]
WEBSOM [http://websom.hut.fi/websom/]
TreeAge Pro Healthcare [http://www.treeage.com]
HTS [http://hts.sp.nitech.ac.jp/]

Нейронные сети
Модель представляет из себя сеть, сплетенную из одинаковых по функциям элементам с помощью синаптических связей.
Каждый элемент (нейрон) выполняет одну функцию – обрабатывая определенным образом входные сигналы x1,…,xn генерирует выходной y:
y = F(x1,…,xn)

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

Карты Кохонена
Отображение набора входных векторов высокой размерности в карту кластеров меньшей размерности, причем, таким образом что близким кластерам на карте отвечают близкие друг к другу входные вектора в исходном пространстве.
Задачи
- Наглядное упорядочивание многопараметрической информации.
- Группировка близких входных сигналов для другой нейросети.

Карты Кохонена
Наглядное упорядочивание многопараметрической информации.
- Выявление различий в режимах поведения системы.
Задачи
- Нахождение взаимосвязей в многопараметрических данных.

Карты Кохонена
Карта Кохонена группирует близкие входные сигналы X, а требуемая функция Y=G(X) строится на основе применения обычной нейросети.
Входной слой
Слой Кохонена
Другая нейросеть
Задачи

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

Нейронные сети
Внутреннее поведение
скрыто
Вход
Нейросеть
Выход
Выход
?
Вход

Нейронные сети
+ Даже малая обучающая выборка не дает большой ошибки обобщения
Неэффективная реализация на ПК.
Сложный процесс проектирования топологии
Плюсы и минусы

Скрытые Марковские модели
Имеет набор скрытых внутренних состояний (скрытая переменная) x(t)
Имеет набор наблюдаемых состояний (наблюдаемая переменная) y(t)
x(t) зависит только от x(t-1)
y(t) зависит только от x(t)
Общие сведения

Скрытые Марковские модели
На каждом шаге система может перейти в новое скрытое состояние и как-то поменять значение наблюдаемой переменной (сменить наблюдаемое состояние)
Время – дискретное.
Общие сведения

Скрытые Марковские модели
-Имеется матрица А[NxN]
-Имеется матрица В[NxM]
Скрытые состояния
вероятностей возникновения каждого из наблюдаемых событий на каждом из скрытых состояний.
вероятностей переходов между скрытыми состояниями.
N
M
Наблюдаемые состояния
Общие сведения

Скрытые Марковские модели
Наиболее вероятная скрытая последовательность погоды ['Sunny', 'Rainy', 'Rainy', 'Sunny', 'Sunny']
Вероятность наблюдения при этом - 4%
Пусть Аня знает, что Ваня сначала гулял, потом ходил за покупками, потом убирался.
['walk', 'shop', 'clean‘,‘walk’,’walk’]
пример

Скрытые Марковские модели
Для заданной модели вычислить вероятность появления некоторой наблюдаемой последовательности.
2. Для модели и наблюдаемой последовательности определить наиболее вероятную последовательность скрытых состояний.
3. Для набора наблюдаемых последовательностей требуется скорректировать матрицы переходов некоторой модели, чтобы эти последовательности были наиболее вероятны в ней.
Задачи
[алгоритм вперёд-назад]
[алгоритм Витерби]
[алгоритм Баума-Уэлша]

Скрытые Марковские модели
Внутреннее поведение
скрыто
Вход
СММ
Выход
Выход
?
Приложение к нашей задаче

Скрытые Марковские модели
+ Имитирует внутреннюю жизнь моделируемой системы.
+ Простые итерационные алгоритмы обучения.
+ Простота и быстрота работы.
+ Соответствие большинству наших требований
+ Хорошие результаты применения в схожих задачах
Не учитывается время, прошедшее между сменой состояний.
Зависимость вероятности перехода лишь от текущего состояний.
Плюсы и минусы

Модификации
Фильтр Калмана
Алгоритм для работы СММ с непрерывными зашумленными наблюдаемыми состояниями.
Многоуровневые СММ
Строится каскад СММ, где каждый следующий уровень генерирует наблюдаемые последовательности для предыдущего.
Иерархические СММ
СММ, где каждое состояние может само являться ИСММ
Что мы хотим, возможно, применить