ВВЕДЕНИЕ 4
ГЛАВА 1. ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. Что такое метаэвристики 9
1.2. Описание методов метаэвристического поиска 11
1.2.1. Методы с одним состоянием 12
1.2.2. Популяционные методы 17
1.2.3 Некоторые другие виды методов 17
1.3. Вероятностное программирование 19
ВЫВОДЫ 22
ГЛАВА 2. РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ В ВЕРОЯТНОСТНЫХ ЯЗЫКАХ ПРОГРАММИРОВАНИЯ 23
2.1. Вероятностные языки 23
2.1.1. Основные сведения о вероятностном программировании 23
2.1.2. Реализованный язык 26
2.2. Разработка генетических операторов для оптимизационных запросов 27
2.2.1. Мутации 27
2.2.2. Имитация отжига 29
2.2.3. Скрещивание 30
ВЫВОДЫ 34
ГЛАВА 3. ОСОБЕННОСТИ РЕАЛИЗАЦИИ ОПТИМИЗАЦИОННЫХ ЗАПРОСОВ 35
3.1. Реализация вероятностного языка с оптимизационными запросами на c++ 35
3.1.1. Реализация языка на основе конструкторов классов 35
3.1.2. Несоответствие поведения оптимизационных и семплирующих запросов 38
3.2. Автоматическое применение принципа минимальной длины описания 40
3.2.1. Байесовская бритва Оккама в вероятностном программировании 40
3.2.2. Принцип минимальной длины описания 40
3.2.3. Автоматическая оценка сложности генеративных моделей 41
ВЫВОДЫ 42
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА 43
4.1. Исследование эффективности реализации оптимизационных запросов 43
4.1.1. Полиномиальная аппроксимация 43
4.1.2. Задача суммы подмножеств 46
4.1.3. Предсказание целочисленных последовательностей 48
4.2. Проверка применимости оптимизационных запросов в задачах с реальными данными 49
ВЫВОДЫ 53
ЗАКЛЮЧЕНИЕ 54
СПИСОК ЛИТЕРАТУРЫ
Настоящая работа посвящена оптимизационному подходу в области вероятностного программирования, которое является новой парадигмой машинного обучения. Объект нашего исследования – вероятностные языки программирования, а предмет – процессы вывода при интерпретации программ на вероятностных языках. Актуальность данной темы обусловлена недостатком эффективных средств вывода в вероятностных языках общего назначения, что ограничивает их применимость.
Цель работы – разработка интерпретатора вероятностного языка, поддерживающего оптимизационные запросы.
Гипотеза: оптимизационные запросы являются более эффективными, чем запросы на основе семплирования.
Задачи, которые необходимо решить, чтобы достигнуть поставленную цель, следующие:
- реализовать интерпретатор опорного языка, который будет расширяться вероятностной семантикой;
- реализовать метаэвристические методы оптимизации, включая имитацию отжига и генетическое программирование;
- реализовать поддержку оптимизационных запросов в интерпретаторе вероятностного языка на основе метаэвристических методов;
- экспериментально сравнить эффективность вероятностных языков на основе семплирования и оптимизационных запросов.
Основные источники представлены двумя ресурсами. Первый – книга «Probabilistic models of Cognition» [1], которая является описанием одного из общепринятых языков вероятностного программирования Church и его применением к задачам когнитивного моделирования. Второй – книга «The essentials of Metaheuristics» [2], где описываются основные концепции и методы метаэвристического поиска.
Основная часть работы состоит из 4 глав. В обзорной главе дан обзор проблемы поиска в области искусственного интеллекта. В заключении представлены выводы.
Мы разработали методы имитации отжига и генетического программирования над следами выполнения программ. Насколько нам известно, это первая реализация этих методов таким образом.
Были использованы одинаковые функции для генетических операторов над следами выполнения программ для решения оптимизационных задач очень разных типов объектов, включая параметрически определенные функции, множества, символьные выражения и даже изображения без производства некорректных кандидатов на решения. Наша реализация соответствует однородному кроссоверу. Должны быть реализованы другие типы генетических операторов, так как наша реализация показывает преимущество над имитацией отжига только в задачах, где выучиваются модели с вещественными значениями. Интересно совместить вероятностное программирование и такие продвинутые системы генетического программирования, как MOSES [15].
Несмотря на простоту использованных метаэвристических методов поиска, они показали лучшие результаты, чем стандартный mh-query. Хотя это сравнение не означает, что annealing-query или evolution-query могут заменить mh-query, так как они решают несколько разные задачи, но показывает, что они могут быть совмещены, и также оптимизационные запросы могут быть полезны для расширения семантики вероятностных языков программирования. До сих пор остается недостаточной эффективность общих методов вывода, и это может быть одним из принципиальных препятствий на пути к сильному ИИ. Возможно, один общий метод вывода не может быть эффективен во всех предметных областях, так что метод вывода должен быть автоматически специализирован по отношению к каждой области, встреченной агентом сильного ИИ [29, 30], которая предполагает, что такие методы должны быть тесно связаны с когнитивными архитектурами.
Разработанный метод автоматического использования принципа минимальной длины описания в вероятностном программировании как сокращает разрыв между свободно применимым принципом МДО и основанным на теории и непрактичной колмогоровской сложности, так и помогает избежать переобучения в оптимизационных запросах, делая их эффективной альтернативой более традиционным запросам, оценивающим условные вероятности. Были проведены эксперименты на примере задачи анализа изображений, подтверждающие приемлемость этого подхода.
Однако даже неспециализированные оптимизационные запросы не смогли эффективно решить произвольные задачи индукции, особенно связанные с общим ИИ. В самом деле, задача такого эффективного вывода может сама по себе быть рассмотрена как ИИ-полная задача. Поэтому должны быть установлены более глубокие связи между общим ИИ и областью вероятностного программирования.
