Спецкурс "Оптимизация систем реального времени"

1. Цель изучения дисциплины: Ознакомление студентов с современными методами стохастической оптимизации и обучение их решать с помощью этих методов сложные технические и экономические задачи. В частности, при проектировании и разработке электронных устройств, работающих в режиме реального времени одним из основных является вопрос об оптимизации их процесса их работы. До последнего времени оптимизация достигалась за счет предварительного моделирования работы и выбора наилучших параметров системы. Использование механизмов «обратной связи», корректирующих параметры во время работы ограничивалось неразвитостью теории последовательной оптимизации. В частности, сильным ограничением в применении стандартных процедур оптимизации было предположение о случайном характере неопределенностей в системе и приписывание им свойств независимости и центрированности. Но именно в системах реального времени эти ограничения, как правило, не удовлетворяются. Поэтому на практике используются некоторые эвристические алгоритмы, теоретически необоснованные. Развитие основ теории последовательной оптимизации при почти произвольных помехах в значительной степени снимает эти ограничения.

2. Задачи курса: Изучение некоторых стохастических информационных моделей, методов стохастической оптимизации и оценивания, фильтрации сигналов, кластеризации.

3. Место курса в профессиональной подготовке выпускника: Дисциплина “Стохастическое программирование” является одной из основных для студентов, планирующих в дальнейшем использование математических методов при проектировании работы вычислительных устройств и систем, обеспечивающей связь общематематических курсов с методами решения конкретных задач оптимизации и оценивания.

4. Требования к уровню освоения дисциплины - "Стохастическое программирование"

· знать содержание дисциплины "Стохастическое программирование" и иметь достаточно полное представление о потенциальных возможностях и применимости методов стохастической оптимизации и оценивания;

· иметь представление о способах математического моделирования сложных технических и экономических задач;

· уметь самостоятельно решать академические задачи стохастического программирования;

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

5. Объем дисциплины, виды учебной работы, форма текущего промежуточного и итогового контроля

Всего аудиторных занятий	128 часов
из них: - лекций	64 часов
- практические занятия	64 часов

Изучение дисциплины по семестрам:

7 семестр: лекции - 32 ч., практические занятия – 0 ч.

8 семестр: лекции - 32 ч., практические занятия – 32 ч., экзамен

9 семестр: лекции - 0 ч., практические занятия – 32 ч., зачет

6. Содержание дисциплины

6.1 Содержание разделов дисциплин и виды занятий

7-й семестр

Оптимизация, оценивание, фильтрация

I. Введение в стохастическое программирование: 2 ч. лекц., 0 ч. практ. зан.

Целевая функция, математическая модель системы, неконтролируемые и случайные факторы, стратегия управления, критерий оптимальности.

II. Классификация задач стохастического программирования: 2 ч. лекц., 0 ч. практ. зан.

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

III. Задача об оценивании скалярного параметра сигнала, наблюдаемого на фоне помех. Усиленный закон больших чисел.: 2 ч. лекц. и 0 ч. практ. зан.

IV. Регрессионный анализ: 2 ч. лекц. и 0 часов практ. зан.

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

V. Оценивание параметров линейных регрессионных моделей по конечному числу наблюдений: 2 ч. лекц. и 0 ч. практ. зан.

Понятия о состоятельности и несмещенности оценок, оценки МНК. Марковские оценки. Теорема Гаусса-Маркова.

VI. Рекуррентные модификации МНК: 2 ч. лекц. и 0 ч. практ. зан.

VII. Фильтр Винера-Колмогорова: 2 ч. лекц. и 0 ч. практ. зан.

VIII. Фильтр Калмана-Бьюси: 2 ч. лекц. и 0 ч. практ. зан.

IX. Байесовское оценивание: 2 ч. лекц., 0 ч. практ. зан.

X. Метод эмпирического функционала: 2 ч. лекц., 0 ч. практ. зан.

Введение в метод статистических испытаний. Применение метода Монте-Карло для вычисления статистических характеристик, доверительная вероятность, гарантирующее число испытаний при априорном подходе, гарантирующее число испытаний при апостериорном подходе, пуассоновская и гауссовская оценки гарантирующего числа испытаний.

XI. Метод максимума правдоподобия. Наилучшая точность оценивания: 2 ч. лекц. и 0 ч. практ. зан.

XII. Метод стохастической аппроксимации: 2 ч. лекц. и 0 ч. практ. зан.

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

XIII. Дифференцируемость функций вероятности и квантили: 2 ч. лекц. и 0 ч. практ. зан.

Градиент функции вероятности в форме поверхностного интеграла и сведение его к объемному, статистические способы вычисления этих интегралов, условия дифференцируемости функции вероятности, случай кусочно-линейной целевой функции, градиент функции квантили).

XIV. Квазиградиентные алгоритмы решения задач стохастического программирования: 2 ч. лекц. и 0 ч. практ. зан.

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

XV. Рандомизированные алгоритмы стохастической аппроксимации: 2 ч. лекц. и 0 ч. практ. зан.

XVI. Введение в динамическое программирование: 2 ч. лекц. и 0 ч. практ. зан.

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

8-й семестр

Кластеризация

I. Задача кластеризации и машинное обучение: 2 ч. лекц. и 2 ч. практ. зан.

Кластеризация в информатике, основные понятия. Обучения по прецедентам. Объекты и признаки. Вероятностная постановка задачи. Типы задач: классификация, кластеризация, регрессия, прогнозирование. Примеры прикладных задач.

II. Основы анализа данных: 2 ч. лекц. и 2 ч. практ. зан.

Основные характеристики описательной статистики. Выделение векторов свойств. Кепстральные коэффициенты и коэффициенты линейного предсказания. Основы корреляционного и регрессионного анализа. Логистическая регрессия.

III. Байесовские алгоритмы классификации: 2 ч. лекц. и 2 ч. практ. зан.

Оптимальный байесовский классификатор. Теорема об оптимальности байесовского решающего правила. Непараметрическое оценивание плотности распределения.

IV. Метрические алгоритмы классификации: 2 ч. лекц. и 2 ч. практ. зан.

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

V. Метод опорных векторов: 2 ч. лекц. и 0 часов практ. зан.

Оптимальная разделяющая гиперплоскость. Случаи линейной разделимости и отсутствия линейной разделимости. Понятие опорных векторов. Способы конструктивного построения ядер. Обучение SVM методом активных ограничений.

VI. Стимулируемое обучение (Reinforcement learning): 2 ч. лекц. и 2 ч. практ. зан.

Основные определения. Примеры прикладных задач.

VII. Нейронные сети: 2 ч. лекц. и 2 ч. практ. зан.

Нейронные сети и их разновидности. Элементы и архитектура, процесс обучения, явление переобучения нейронной сети. Персептрон. Самоорганизующиеся карты Кохонена.

VIII. Иерархические методы кластерного анализа: 2 ч. лекц. и 2 ч. практ. зан.

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

IX. Итеративные методы кластерного анализа: 2 ч. лекц. и 2 ч. практ. зан.

Процесс кластерного анализа. Основа факторного анализа и итеративная кластеризация. Алгоритм k-means.

X. Нечеткие множества: 2 ч. лекц. и 2 ч. практ. зан.

Нечеткие отношения. Классы нечетких отношений. Методы построения функции принадлежности, классификация. Алгоритм Fuzzy c-means.

XI. EM-алгоритм: 2 ч. лекц. и 2 ч. практ. зан.

Смесь распределений. EM-алгоритм: основная идея, понятие скрытых переменных. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси. Стохастический EM-алгоритм.

XII. Параметрическое оценивание плотности: 2 ч. лекц. и 2 ч. практ. зан.

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

XIII. Методы устойчивой кластеризаци: 2 ч. лекц. и 2 ч. практ. зан.

Индексные методы. C-index, Dunn, Calinski-Harabasz, Krzanowski-Lai, Hartigan, Kaufman-Rousseeuw и др. Устойчивая кластеризация на основе функции устойчивости. Cheng- Milligan. Устойчивая кластеризация на основе оценок плотностей распределений. Levine- Domany.

XIV. Параметры алгоритмов кластеризации: 2 ч. лекц. и 2 ч. практ. зан.

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

XV. Способы визуального представления данных: 2 ч. лекц. и 2 ч. практ. зан.

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

XVI. Рынок инструментов для кластеризации и классификации: 2 ч. лекц. и 2 ч. практ. зан.

Рынок программных средств кластеризации и классификации, его развитие, поставщики, классификация инструментов. SPSS, SAS Enterprise Miner, Система PolyAnalyst, Cognos и система STATISTICA Data Miner.

9-й семестр

Рандомизированные алгоритмы

I. Постановки задач стохастического программирования: 0 ч. лекц., 2 ч. практ. зан.

II. Примеры решения задач стохастического программирования: 0 ч. лекц., 2 ч. практ. зан.

III. Оценивание параметров линейной регрессии: 0 ч. лекц. и 2 ч. практ. зан.

IV. Идентификация динамического объекта: 0 ч. лекц. и 2 ч. практ. зан.

V. Адаптивная l_1 оптимизация: 0 ч. лекц. и 2 ч. практ. зан.

VI. Фильтрация в линейном случае: 0 ч. лекц. и 2 ч. практ. зан.

VII. Ранд. алгоритмы с 1-м и 2-мя измерениями: 0 ч. лекц. и 2 ч. практ. зан.

VIII. Опт.скорость сходимости: 0 ч. лекц. и 2 ч. практ. зан.

IX. Модификации алгоритмов СА: 0 ч. лекц., 2 ч. практ. зан.

X. Q-обучение, обучение с подкреплением: 0 ч. лекц. и 2 ч. практ. зан.

XI. Метод отжига: 0 ч. лекц., 2 ч. практ. зан.

XII. Генетические алгоритмы: 0 ч. лекц. и 2 ч. практ. зан.

XIII. Оптимизация работы сервера: 0 ч. лекц. и 2 ч. практ. зан.

XIV. Оптимизация работы маршрутизатора: 0 ч. лекц. и 2 ч. практ. зан.

XV. Антенные решетки: 0 ч. лекц. и 2 ч. практ. зан.

XVI. Применение рагдомизированных алгоритмов оптимизации в техническом анализе при торговле: 0 ч. лекц. и 2 ч. практ. зан.

6.2 Темы курсовых работ

· Оптимизация моделей экономических и технических систем методами стохастического программирования (СРС – 48 ч.).

При выполнении КР предусматривается разработка математических методов и программно-алгоритмического обеспечения ЭВМ для решения прикладных задач: моделирование функционирования средств ВТ и разработки ПО, планирование капиталовложений, оптимизация размещения предприятий, планирование штатного расписания больницы, хеджирование call-опциона, определение гарантирующего числа статистических испытаний, построение доверительных множеств.

· Реализация индексных методов устойчивой кластеризации

· Создание программной библиотеки для визуального изображения многомерных данных

· Анализ методов устойчивой кластеризации, выделение общего вычислителного ядра

· Программная реализация средств для анализа эффективности алгоритмов кластеризации

· Исследование новых методов кластеризации в среде Матлаб

6.3 Темы рефератов

· История задач кластерного анализа

· Методы устойчивой кластеризации

· Программные средства для решения задач кластеризации

· Алгоритмы кластеризации в поисковых системах сети Интернет

· Алгоритмы кластеризации в задаче сжатия данных

· Алгоритмы кластеризации в задаче сегментации изображений

· Использование алгоритмов классификации для настройки нейронных сетей

6.4 Примерный перечень вопросов к экзамену по всему курсу

· Функционал среднего риска.

· Задача об оценивании скалярного параметра сигнала, наблюдаемого на фоне помех.

· Наилучшая аппроксимация одной случайной величины с помощью другой, понятие условного математического ожидания.

· Оценивание параметров линейных регрессионных моделей по конечному числу наблюдений.Оценки МНК.

· Марковские оценки. Теорема Гаусса-Маркова.

· Рекуррентные модификации МНК.

· Фильтр Винера-Колмогорова.

· Фильтр Калмана-Бьюси.

· Байесовское оценивание..

· Метод эмпирического функционала.

· Метод максимума правдоподобия.

· Наилучшая точность оценивания.

· Метод стохастической аппроксимации. Алгоритм Роббинса-Монро.

· Алгоритма Кифера-Вольфовица.

· Лемма о сходимости "почти" супермартингалов.

· Рандомизированные алгоритмы стохастической аппроксимации.

· Классификация и кластеризация. определения и примеры задач. метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска.

· Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.

· Теория обработки сигналов. Выделение векторов свойств. Кепстральные коэффициенты и коэффициенты линейного предсказания.

· Основы корреляционного и регрессионного анализа. Определения. Примеры задач.

· Оптимальный байесовский классификатор. Ошибки I и II рода. Наивный байесовский классификатор.

· Непараметрическое оценивание плотности распределения. Робастное оценивание плотности. Метод парзеновского окна.

· Параметрическое оценивание плотности распределения. Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.

· Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.

· Метод k ближайших соседей и его обобщения. Подбор числа k по критерию скользящего контроля.

· Метод потенциальных функций, градиентный алгоритм.

· Рандомизированный алгоритм стохастической аппроксимации.

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

· Обучение SVM методом активных ограничений. Алгоритм INCAS.

· Стимулируемое обучение. Определения. Примеры прикладных задач.

· Нейронные сети и их разновидности. Элементы и архитектура, процесс обучения, явление переобучения нейронной сети. Персептрон.

· Нейронные сети. Самоорганизующиеся карты Кохонена.

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

· Агломеративная кластеризация и таксономия. Формула Ланса-Вильямса и её частные случаи.

· Итеративные методы кластерного анализа. Алгоритм k-means. Основы факторного анализа.

· Нечеткие множества. Классы нечетких отношений. Алгоритм Fuzzy c-means.

· Смесь распределений. Смесь многомерных нормальных распределений. EM-алгоритм. Стохастический EM-алгоритм.

· Методы устойчивой кластеризаци. Индексные методы.

· Определение количества кластеров на основе оценок плотностей распределений и функций устойчивости.

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

· Способы визуального представления данных. Методы визуализации. Анализ главных компонент. Самоорганизующаяся карта Кохонена.

· Программные средства для кластеризации и классификации. Классификация инструментов.

Литература:

Основная

1. Граничин О.Н. "Введение в стохастические методы оптимизации и оценивания". –СПб.: Изд-во СПбГУ, 2003, 131 c.

2. Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. – М.: Hаука. 2003. 291с.

3. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. – М.: Hаука. 1979. 447с.

Дополнительная

1. Фомин В.Н. “Рекуррентное оценивание и адаптивная фильтрация”. М.: Наука, 1984, 288 с.

2. Kushner H.J., Yin G.G. “Stochastic Approximation and Recursive Algorithms and Applications”. – Springer. 2003. 475 p.

3. Spall J.C. “Introduction to Stochastic Search and Optimization”. – Wiley-Interscience. 2003. 597 p.

4. Borkar V.S. “Stochastic Approximation”. – Cambridge Univ. Press. 2008. 164 p.

5. Катковник В. Я. Линейные оценки и стохастические задачи оптимизации. М.: Наука, 1976

6. Webb A. Statistical pattern recognition. Wiley. 2002.

7. Кибзун А.И., Горяинова Е.Р., Наумов А.В. Теория вероятностей и математическая статистика. Базовый курс с примерами и задачами. М.: Физматлит, 2005.

Спецкурс "Стохастическое программирование"