Спецкурсы кафедры математических методов прогнозирования для аспирантов



Скачать 484,43 Kb.
страница1/3
Дата21.04.2016
Размер484,43 Kb.
  1   2   3
Спецкурсы кафедры математических методов прогнозирования для аспирантов

на 2015/16 учебный год






Спецкурс

Семестр

Лектор

1

«Прикладные задачи анализа данных»

Applied data mining problems



Осень

д.ф.-м.н., профессор

Дьяконов Александр Геннадьевич



2

«Непрерывные морфологические модели и алгоритмы»

Continuous morphological models and algorithms




Осень

д.т.н., профессор

Местецкий Леонид Моисеевич




3

«Задачи и алгоритмы вычислительной геометрии»

Problems and algorithms of computational geometry




Весна

д.т.н., профессор

Местецкий Леонид Моисеевич




4

«Логический анализ данных в распознавании»

Logical data analysis in pattern recognition



Осень

д.ф.-м.н, доцент

Дюкова Елена Всеволодовна



5

«Методы машинного обучения и поиск достоверных закономерностей в данных»

Machine learning and knowledge discovery



Осень

д.ф.-м.н. Сенько Олег Валентинович

6

«Нестатистические методы анализа данных и классификации»,

Non-statistical methods of data mining and classification



Осень


д.ф.-м.н., профессор Рязанов Владимир Васильевич

7

«Нестатистический анализ данных»,

Non-statistical data mining



Весна

д.ф.-м.н., профессор Рязанов Владимир Васильевич

8

«Методы оптимизации в машинном обучении»

Optimization in machine learning



Осень

н.с. Кропотов Дмитрий Александрович

9

«Метрические методы интеллектуального анализа данных»

Metric methods of machine learning



Весна

к.ф.-м.н., доцент Майсурадзе Арчил Ивериевич

10

«Вероятностное тематическое моделирования»

Probabilistic topic modelling



Весна

д.ф.-м.н.

Воронцов Константин Вячеславович




11

«Исчисления высказываний классической и интуиционистской логик»

Propositional calculus of classical and intuitionistic logics



Осень

доцент, к.ф.-м.н. Гуров Сергей Исаевич


Курс «Прикладные задачи анализа данных»
Дьяконов А.Г.
Аннотация
Основная цель: практика решения современных задач классификации, прогнозирования, регрессии, рекомендации и т.п., подготовка участников к соревнованиям на платформах Kaggle и Algomost.
Программа

Вводное занятие: цели курса, материалы, правила, участие в соревнованиях. Соревнование Learning Social Circles in Networks по определению кругов в эго-подграфах графа социальной сети (задача, данные, их загрузка, редакторское расстояние), приложения анализа социальных сетей.

Анализ социальных сетей, определение кругов пользователей: динамические графы, приложения анализа социальных сетей, погружение графов в признаковое пространство, сходство вершин, важность вершин, прогнозирование появления рёбер в динамическом графе, решение задачи соревнования IJCNN Social Network Challenge, признаки рёбер, алгоритм PageRank и его модификации, сообщества в графах и их выделение, спектральные методы на графах, генерация случайных графов.
Искусство визуализации данных: игра "Что за данные", признаки в задаче [bioresponse], выделение групп признаков, что можно увидеть в данных, оценка признаков и фолдов, деформация ответов, устойчивость закономерностей, профили лет (в прогнозировании вр.рядов), плотности, оценка качества признаков с помощью RF и удалений, результаты алгоритмов и их линейные комбинации, ручная деформация пространств, визуализация и сглаживание плотностей, построение профилей. Что надо знать о признаках. Визуализация по-вертикали и по-горизонтали. Шумы и шумовые признаки. Задачи [cause-effect-pairs], [GiveMeSomeCredit], [DarkWorlds].
Оценка среднего, оценка вероятности, оценка плотности. Весовые схемы: проблема оценки среднего, выбросы, разные целевые функционалы, оценка минимального контраста, среднее по Колмогорову, SMAPE-минимизация, двухэтапные алгоритмы и их настройка, пересчёт вероятности и прямая оценка, введение весовых схем, устойчивость весовых схем, ансамблирование, непараметрическое восстановление плотности, весовые схемы при оценке плотности. Задача [dunnhumby's Shopper Challenge]. Задача [пробки].
Линейная классификация и регрессия: персептронный алгоритм, режимы обучения, концепция поощрение-наказание, концепция минимизации функционала, линейная регрессия, SGD, хэширование признаков, регуляризация, обобщения регрессии, прогноз раскупаемости, прогноз методом kNN, прогноз линейным оператором, линейный алгоритм над SVD, признаковое прогнозирование спроса, профили товаров, сезонность, LibSVM, LibLinear. Задачи: [JRS12], [NN5], [tourism2]. Разбор решения задачи соревнования Learning Social Circles in Networks.  Tradeshift Text Classification.
Анализ текстов: классификация и регрессия - этапы работы с текстом, токенизация, стоп-слова, векторное представление документа, n-граммы, стемминг, алгоритм Портера, TF*IDF, оценки качества (точность, полнота, F-мера), классификация спама, Local and Global Consistency, этапные алгоритмы, устойчивые признаки, иерархическая классификация текстов, основные методы (Роше, kNN, SVM), приведение к шаблону, обнаружение оскорблений, распределение по топикам (задача со многими классами), блендинг алгоритмов, фонетические алгоритмы. Задачи: [spam], [LSHTC], [JRS12]. Представление программы Vowpal Wabbit.
Случайные леса: универсальные методы анализа данных, бэггинг и бустинг, построение одного дерева, OOB(out of bag)-проверка, параметры случайного леса (random forest: mtry, nodesize, samplesize) и их настройка, рейтинг признаков (importance). Программирование случайного леса. Области устойчивости функционалов. Искусство генерации признаков: географические и временные признаки. Концепция чёрного ящика на примере GBM. Настройка параметров GBM, суммирование. Нестандартные функционалы и настройка на них. Калибровка ответов алгоритмов. Сведение задачи рекомендации к регрессии. Критерии расщепления.

Разбор задач [see-click-predict-fix], [wikimart].


k ближайших соседей, настройка комбинаций алгоритмов: Сглаживание функционалов качества при использовании весовых схем. Ограничение методов типа kNN (тренд, некорректность метрики).

Примитивная настройка линейных комбинаций алгоритмов и метрик. Технология LENKOR (синтез близостей, составление комбинации близостей, настройка коэффициентов, добавление нелинейностей). Подробный разбор задачи детектирования оскорблений. Задачи [PhotoQualityPrediction] (определение качества фотографии по метаданным), [unimelb] (предсказывание успешности выполнения гранта), [VLNetChallenge] (рекомендация видеолекций для просмотра). Деформация ответов, теоремы Колмогорова, Горбаня и Пинкуса, алгебраический подход к коррекции и его правильное применение на практике.




Курс «Непрерывные морфологические модели и алгоритмы»
Местецкий Л.М.
Аннотация
В компьютере изображения представляются прямоугольными матрицами точек, обладающих определенным цветом и яркостью. Такое дискретное представление является удобным для ввода, запоминания, обработки в компьютере. Однако для анализа формы объектов такое представление неудобно. Человеку привычнее и проще при описании формы объектов оперировать непрерывными геометрическими фигурами. Основные преимущества непрерывного представления: адекватность его с физической сущностью «сплошных» объектов реального мира, возможность использования для анализа, преобразований и распознавания формы методов «непрерывной» математики.

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



Программа

  • Основные понятия вычислительной геометрии. Мера сложности вычислений. Асимптотический анализ сложности. Рекурсивные алгоритмы. Оценка вычислительной сложности задачи.

  • Алгоритмическая парадигма «разделяй и властвуй». Геометрический поиск. Локализация точки в простом и в выпуклом многоугольнике при уникальном и массовом запросе. Локализация точки в планарном подразбиении.

  • Построение выпуклых оболочек. Алгоритмы Джарвиса, Грэхема. Слияние выпуклых оболочек. Метод редукции для оценки сложности задачи.

  • Пересечения геометрических объектов. Пересечения конечного множества отрезков. Алгоритмическая парадигма плоского заметания. Структуры данных в алгоритме заметания.

  • Близость геометрических объектов. Разбиения Вороного и триангуляции Делоне. Преобразования двойственных графов. Алгоритмы построения триангуляции Делоне: наивные, жадные, инкрементные, флип-флоп, рекурсивные. Обобщенные диаграммы Вороного для различных множеств сайтов – кругов, отрезков, многоугольников.

  • Обобщенная диаграмма Вороного и скелет многоугольной фигуры.

Литература

  1. Препарата Ф., М.Шеймос М. Вычислительная геометрия: введение. Москва: «Мир», 1989.

  2. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. Москва: Физматлит. 2009.

  3. Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013. Конспект [1.46 Мб]

  4. Местецкий Л.М. Лекции по непрерывным морфологическим моделям Презентации PowerPoint [3.8 Мб]


Курс «Задачи и алгоритмы вычислительной геометрии»
Местецкий Л.М.
Аннотация
Эффективные алгоритмы работы с геометрической информацией являются непременным атрибутом всех современных систем компьютерной графики, анализа и распознавания изображений, машинного зрения, геоинформационных систем. Геометрические алгоритмы предоставляют хорошее поле для развития алгоритмического мышления, необходимого в прикладной математике.

В этом спецкурсе будут рассмотрены классические темы вычислительной геометрии: геометрический поиск, выпуклые оболочки, пересечение и близость объектов, диаграммы Вороного, триангуляции Делоне, скелеты многоугольников.


Программа

  • Бинарное изображение как результат сегментации формы. Фигура, как модель формы, открытое множество, связное множество, область, односвязная и многосвязная области, замкнутая область, жорданова кривая

  • Непрерывные и дискретные модели формы. Граничное и скелетное описание фигуры, их достоинства и недостатки. Дискретные модели границы и скелета фигуры. Эквивалентность непрерывной и дискретной моделей формы.

  • Непрерывные границы дискретной фигуры. Связность в дискретном пространстве, дискретная фигура. Треугольные структуры соседства, гексагональные структуры соседства (6-смежность), объектная и компонентная структуры соседства. Граничные пары, граничные треугольники, граничные коридоры дискретной сцены.

  • Поиск и прослеживание границы. Постановка задачи прослеживания границ дискретной сцены. Симплексное прослеживание. Прослеживание методом подвижного моста.

  • Аппроксимация граничного коридора разделяющей фигурой минимального периметра. Алгоритм вытягивания нити. Аппроксимация границы составными кривыми Безье.

  • Обобщения диаграммы Вороного и триангуляции Делоне: в манхэттенской и в шахматной метриках, для сайтов-окружностей в метрике Лагерра, для разделённых сайтов-сегментов.

  • Диаграмма Вороного многоугольной фигуры. Связь диаграммы Вороного многоугольника и его скелета, алгоритм построения скелета многоугольника по его диаграмме Вороного. Обобщённая триангуляция Делоне для коллекции сайтов.

  • Регуляризация скелета методом стрижки. Силуэт скелетного графа, силуэт подграфа, расстояние между силуэтами. Последовательная стрижка скелета с контролем точности. Стрижка тонких элементов.

  • Циркулярные фигуры и жирные линии. Преобразования формы изображений в компьютерной графике и в распознавании образов. Жирная кривая, циркулярная фигура, осевой граф, функция ширины, силуэт. Деформация циркуляра и задача подгонки, аппроксимация скелета циркуляром.



Курс «Логический анализ данных в распознавании»
Дюкова Е.В.
Аннотация
В спецкурсе будут изложены общие принципы, лежащие в основе дискретных методов анализа информации в задачах распознавания, классификации и прогнозирования. Будут рассмотрены подходы к конструированию процедур распознавания на основе использования аппарата логических функций и методов построения покрытий булевых и целочисленных матриц. Будут изучены основные модели и рассмотрены вопросы, связанные с исседованием сложности их реализации и качества решения прикладных задач.
Программа
Постановка задачи распознавания. Сущность дискретного подхода к задачам распознавания. Общие принципы построения дискретных (логических) процедур распознавания. Понятие элементарного классификатора. Основные модели дискретных (логических) процедур распознавания и используемые в них семейства элементарных классификаторов.

Модели алгоритмов голосования по представительным наборам. Детерминированные и стохастические модели тестовых алгоритмов. Модели алгоритмов голосования, основанные на построении покрытий классов. Модели, основанные на построении решающих деревьев. Методы построения элементарных классификаторов.

Основные понятия теории дизъюнктивных нормальных форм. Задача построения сокращенной дизъюнктивной нормальной формы двузначной логи-ческой функции, заданной конъюнктивной нормальной формой. Критерии допустимости, неприводимости и максимальности элементарной конъюнкции для двузначной логической функции, заданной конъюнктивной нормальной формой. Способы построения сокращенной дизъюнктивной нормальной формы для всюду определенной двузначной логической функции и частичной двузначной логической функции. Построение элементарных классификаторов на основе преобразования нормальных форм двузначных логических функций.

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

Сложность реализации дискретных (логических) процедур распознавания. Метрические свойства множества покрытий целочисленной матрицы.

Асимптотические оценки типичных значений числа покрытий и длины покрытия целочисленной матрицы. Асимптотические оценки типичных значений числа тупиковых покрытий и длины тупикового покрытия целочисленной матрицы в случае, когда число строк матрицы существенно превосходит число столбцов. Асимптотические оценки типичных значений числа (тупиковых) покрытий с длиной близкой к минимальной. Подходы к оценке сложности трудно решаемых перечислительных задач. Асимптотически оптимальный алгоритм поиска тупиковых покрытий целочисленной матрицы с полиномиальной задержкой.

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

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



Литература

Основная литература

  1. Дискретная математика и математические вопросы кибернетики / Под ред. С.Б. Яблонского, О.Б. Лупанова. М.: Наука. 1974.

  2. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. Учебное пособие для студентов математических факультетов педвузов. М: МПГУ. 2003. Пособие (PDF), Приложение к пособию (PDF).

  3. Дюкова Е.В. Алгоритмы распознавания типа Кора: сложность реализации и метрические свойства / Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1989. Вып. 2. С. 99-125.

  4. Дюкова Е.В. О числе тупиковых покрытий целочисленной матицы // Ж. вычисл. матем. и матем. физ. 2005. Т. 27, № 1. С. 114-127.

  5. Дюкова Е.В., Журавлёв Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. 2000. Т. 40, №8. С. 1264-1278.

  6. Дюкова Е.В., Журавлев Ю.М., Рудаков К.В. Об алгебро-логическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // Ж. вычисл. матем. и матем. физ. 1996. Т. 36, № 8. С. 217-225.

  7. Дюкова Е.В., Инякин А.С. О процедурах классификации, основанных на построении покрытий классов // Ж. вычисл. матем. и матем. физ. 2003. Т. 43, № 12. С. 1910-1921.

  8. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и ма-тем. физ. 2002. Том 42, № 5. С. 741-753.

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

  1. Баскакова Л.В., Журавлёв Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // Ж. вычисл. матем. и матем. физ. 1981. Т. 21, №5. С. 1264-1275.

  2. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов «Кора» / Ал-горитмы обучения распознаванию образов. М.: Сов. Радио. 1973. С. 82-91.

  3. Дмитриев А.И., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов или явлений / Дискретный анализ. Новоси-бирск: ИМ СО АН СССР. 1966. Вып. 7. С. 3-17.

  4. Донской В.И. Алгоритмы обучения, основанные на построении решающих деревьев // ЖВМиМФ. 1982. Т. 22, № 4. С. 963-974.

  5. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. 233, № 4. С. 527-530.

  6. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания / Пробл. кибернетики. М.: Наука. 1982. Вып. 39. С. 165-199.

  7. Дюкова Е.В. О сложности реализации некоторых процедур распознавания // Ж. вычисл. матем. и матем. физ. 1987. Т. 27, №1. С.114-127.

  8. Дюкова Е.В. Асимптотические оценки некоторых характеристик множества представительных наборов и задача об устойчивости //Ж. вычисл. матем. и матем. физ. 1995. Т. 35, № 1. С. 122-134.

  9. Дюкова Е.В. О сложности реализации дискретных (логических) процедур распознавания // Ж. вычисл. матем. и матем. физ. 2004. Т. 44, № 3. С. 550-572.

  10. Журавлев Ю.И. Избранные научные труды. М.: Изд. Магистр. 1998. 416 с.

  11. Кузнецов В.Е. Об одном стохастическом алгоритме вычисления информативных характеристик таблиц по методу тестов / Дискретный анализ. Новоси-бирск: ИМ СО АН СССР. 1973. Вып. 23. С. 8-23.

  12. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач / Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1988. Вып. 1. С. 229-279.

  13. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем // Тр. МИАН СССР. М.: 1958.

  14. Яблонский С.В. Введение в дискретную математику. М.: Наука. 1986.



Курс «Методы машинного обучения и поиск достоверных закономерностей в данных»
Сенько О.В.
Аннотация
В курсе обсуждаются основные проблемы, возникающие при использовании методов обучения по прецедентам (машинного обучения). Даётся краткий обзор существующих методов распознавания и регрессионного анализа. Рассказывается о способах оценки точности на генеральной совокупности (обобщающей способности). Обсуждаются различные способы повышения обобщающей способности методов машинного обучения.
Рассказывается о тесно связанной с задачей машинного обучения задаче поиска закономерностей в данных. Под закономерностью понимается некоторое относительно простое правило, связывающее прогнозируемую величину с другими переменными. Рассказывается о современных методах статистической верификации закономерностей, основанных на перестановочных тестах. Обсуждаются методы распознавания и регрессионного анализа, основанные методы, основанные на вычислении коллективных решений по системам закономерностей. Рассказывается также о различных методах кластерного анализа и способах их применения.
Приведены примеры успешно решённых задач диагностики, прогнозирования, интеллектульного анализа данных в различных областях, включая медицину, антропологию, социологию, химию др.

Программа


  1. Область использования и основные задачи методов машинного обучения (ММО)

  2. Основные проблемы, возникающие при использовании ММО

  3. Методы точности прогнозирования для обученных алгоритмов

  4. Краткий обзор методов линейного регрессионного анализа, включая методы, основанные на регуляризации (гребневая регрессия, Лассо, эластичная сеть)

  5. Краткий обзор методов распознавания, включая

    • статистические методы;

    • нейросетевые методы;

    • решающие деревья и леса;

    • комбинаторно-логические методы;

    • метод опорных векторов;

    • методы, основанные на голосовании по системам закономерностей,

    • метод мультимодельных статистически взвешенных синдромов.

  6. Анализ ROC-кривых как способ оценки эффективности методов распознавания

  7. Понятие обобщённой ошибки прогнозирования в машинном обучении.

  8. Структура обобщённой ошибки (трёх компонентное разложение )

  9. Краткий обзор коллективных методов в машинном обучении, включая

    • простейшие комитеты;

    • логическая коррекция;

    • алгебраическая коррекция.

  10. Выпуклые комбинации (ВК) прогностических алгоритмов

    • структура ошибки ВК;

    • структура составляющих обобщённой ошибки для ВК,

    • методы поиска оптимальных ВК, основанные на концепции несократимых и нерасширяемых наборов;

    • метод выпуклой регрессии, сравнение с Лассо и эластичной сетью.

  11. Методы верификации закономерностей, основанные на перестановочных тестах, включая

    • верификацию простейших моделей;

    • оценка обоснованности использования более сложной модели по отношению к простой (лезвие Оккама).

  12. Метод интеллектуального анализа данных (ИАД), основанный на оптимальных достоверных разбиениях.

  13. Примеры использования в ММО и ИАД для решения медицинских задач.

Литература

  1. Журавлёв Ю.И. Рязанов В.В. Сенько О.В. РАСПОЗНАВАНИЕ. Математические методы. Программная система. Применения. - Москва: Фазис, 2006

  2. Сенько О.В. Перестановочный тест в методе оптимальных разбиений. // Ж. выч. матем. и матем. физ. N9, 2003, с.1438-1447.

  3. А.В. Кузнецова, И.В. Костомарова, Н.Н. Водолагина, Н.А. Малыгина, О.В. Сенько. Изучение влияния клинико-генетических факторов на течение дисциркуляторной энцефалопатии с использованием методов распознавания // Матем. биолог. и биоинформ., 2011, том 6, выпуск 1, страницы 115–146.

  4. Oleg V.Senko and Anna V. Kuznetsova. The Optimal Valid Partitioning Procedures. InterStat. Statistics on the Internet, April, 2006.

  5. Сенько О.В., Докукин А.А. Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности. ЖВМиМФ, Т. 51, №9 с.1751-1760, 2011.

  6. Senko O., Kuznetsova A. A recognition method based on collective decision making using systems of regularities of various types // Pattern Recognition and Image Analysis, MAIK Nauka/Interperiodica. Vol. 20, No. 2, 2010, pp. 152-162.



Курс «Нестатистические методы анализа данных и классификации»
Рязанов В.В.
Аннотация
Основная цель спецкурса состоит в изложении основанных на оптимизационных, дискретных и эвристических подходах методов анализа данных. Будут рассмотрены логические модели распознавания (классификации с учителем) и анализа разнотипных многомерных данных, методы оптимизации моделей распознавания, алгоритмы поиска скрытых логических закономерностей и связей по признаковым описаниям, алгоритмы обработки множеств логических закономерностей, методы создания качественных моделей объектов, ситуаций, явлений или процессов. Будут рассмотрены практические численные методы решения данных задач, и их применения в медицине, бизнесе, химии, технике и других областях.

Программа

  1. Задача распознавания (классификации) по прецедентам. Тупиковые тесты и их вычисление, случаи вещественных признаков, стохастический тестовый алгоритм.

  2. Логические модели распознавания для разнотипных признаков (алгоритмы вычисления оценок, алгоритм «Кора», модели с представительными наборами, практические реализации).

  3. Эффективное вычисление оценок для различных типов признаков.

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

  5. Логические закономерности классов, эвристический критерий качества логических закономерностей.

  6. Сведение задачи поиска логических закономерностей классов к задаче целочисленного линейного программирования.

  7. Логические закономерности классов, стандартный критерий качества логических закономерностей и его оптимизация.

  8. Генетические методы поиска, генетический алгоритм поиска логических закономерностей классов.

  9. Веса признаков и прецедентов, логические корреляции. Минимизация признакового пространства.

  10. Логические описания классов. Обработка множеств логических закономерностей. Минимальные и кратчайшие описания классов.

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

  12. Построение минимальных по сложности логических закономерностей классов.

  13. Бинарные решающие деревья. Допустимые разбиения единичного куба.

  14. Алгоритм построения допустимого разбиения, представление допустимого разбиения бинарным решающим деревом.

  15. Прямые методы построения бинарных решающих деревьев, критерии ветвления.

Литература

  1. Журавлев Ю.И. Избранные научные труды. М.: Магистр. 1998.

  2. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики. М.: Наука. 1978. Вып. 33. С.5-68.

  3. Донской В.И., Башта А.И. Дискретные модели принятия решений при неполной информации. Симферополь: Таврия. 1992.

  4. Рязанов В.В. Логические закономерности в задачах распознавания (параметрический подход) // Журнал вычислительной математики и математической физики. Т.47, № 10. 2007. С. 1793-1808.

  5. Ковшов Н.В., Моисеев В.Л., Рязанов В.В. Алгоритмы поиска логических закономерностей в задачах распознавания // Журнал вычислительной математики и математической физики. 2008. Т.48, № 2. С. 329-344.



Курс «Нестатистический анализ данных»
Рязанов В.В.
Аннотация
В спецкурсе будут рассмотрены проблемы и методы кластерного анализа (подходы и алгоритмы кластеризации с известным и неизвестным числом кластеров, критерии кластеризации, вопросы устойчивости, построение оптимальных решений), дискретные методы для решения задач классификации множествами алгоритмов, новые подходы и алгоритмы в регрессионном анализе и анализе данных (решение задач восстановления зависимостей на основе решения задач классификации, задачи классификации с большим числом классов). Будут рассмотрены практические задачи классификации и поиска зависимостей по прецедентам, применения в медицине, бизнесе и технике.
Программа

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

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

  3. Критерии кластеризации при неизвестном числе кластеров, меры концентрации.

  4. Итеративная оптимизация критериев кластеризации на примере дисперсионного критерия.

  5. Алгоритмы иерархической группировки.

  6. Критерии устойчивости кластеризаций и их вычисление.

  7. Алгоритмы кластеризации, основанные на поиске центров сгущений (алгоритмы к-средних, нечетких к-средних, ФОРЕЛЬ, построения оптимальных покрытий).

  8. Эвристические алгоритмы кластеризации, алгоритмы «к-эталонов» и «взаимного поглощения».

  9. Восстановление компонент смеси по заданной обучающей выборке.

  10. Нейросетевые алгоритмы обучения и самообучения. Метод встречного распространения, сеть Хопфильда, алгоритмы Хэбба.

  11. Логические корректоры для решения задач классификации.

  12. Решение задач кластерного анализа коллективами алгоритмов, метод коллективных к-средних.

  13. Комитетный синтез коллективных кластеризаций, критерии качества коллективных кластеризаций.

  14. Нахождение оптимальных коллективных решений задачи кластерного анализа.

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

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

Курс «Методы оптимизации в машинном обучении»


Кропотов Д.А.
Аннотация
Настройка модели алгоритмов по данным – это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
Программа
Основные понятия и примеры задач

  • Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;

  • Матричные разложения, их использование для решения СЛАУ;

  • Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;

  • Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации;

  • Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.


Методы одномерной оптимизации

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

  • Гибридный метод минимизации Брента;

  • Методы решения уравнения f’(x)=0: метод деления отрезка пополам, метод секущей;

  • Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;

  • Поиск ограничивающего сегмента;

  • Условия Армихо-Голдштайна-Вольфа для неточного решения задачи одномерной оптимизации;

  • Неточные методы одномерной оптимизации, backtracking.


Методы многомерной оптимизации

  • Методы линейного поиска и доверительной области;

  • Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;

  • Сходимость общего метода линейного поиска с неточной одномерной минимизацией;

  • Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;

  • Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;

  • Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;

  • Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;

  • Применение неточного метода Ньютона для обучения линейного классификатора и нелинейной регрессии, аппроксимация Гаусса-Ньютона и адаптивная стратегия Levenberg-Marquardt;

  • Квазиньютоновские методы оптимизации: DFP, BFGS и L-BFGS;


Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра

  • Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента;

  • Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость;

  • Пример применения метода для обучения LASSO;

  • Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии;

  • Построение оценок с помощью касательных и замены переменной;

  • Оценка Jaakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента;

  • Применение оценок для обучения вероятностных моделей линейной регрессии;

  • Выпукло-вогнутая процедура, примеры использования.


Методы внутренней точки

  • Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера и условия Джона, соотношение между ними;

  • Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;

  • Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;

  • Прямо-двойственный метод Ньютона, неточный вариант метода;

  • Метод логарифмических барьерных функций;

  • Методы первой фазы;

  • Прямо-двойственный метод внутренней точки;

  • Использование методов внутренней точки для обучения SVM.


Разреженные методы машинного обучения

  • Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;

  • Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;

  • Метод наискорейшего субградиентного спуска;

  • Проксимальный метод;

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


Методы отсекающих плоскостей

  • Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);

  • Надграфная форма метода отсекающих плоскостей;

  • Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;

  • Применение bundle-метода для задачи обучения SVM;

  • Добавление эффективной процедуры одномерного поиска;

  • Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.


Стохастическая оптимизация

  • Общая постановка задачи стохастической оптимизации, пример использования;

  • Задачи минимизации среднего и эмпирического риска;

  • Метод стохастического градиентного спуска, две фазы итерационного процесса, использование усреднения и инерции;

  • Стохастический градиентный спуск как метод оптимизации и как метод обучения;

  • Метод SAG;

  • Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);



Литература


  1. Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2012.

  2. J. Nocedal, S.J. Wright. Numerical Optimization, Springer, 2006.

  3. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.

  4. Yu. Nesterov. https://yandex.st/lego/_/la6qi18z8lwgnzdsar1qy1gwcwo.gifIntroductory Lectures on Convex Programming, 1998.

  5. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.

  6. Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.

  7. M. Schmidt. https://yandex.st/lego/_/la6qi18z8lwgnzdsar1qy1gwcwo.gifLimited-Memory Quasi-Newton and Hessian-Free Newton Methods for Non-Smooth Optimization // NIPS workshop on optimization for machine learning, 2010.

  8. D. Bertsekas. Convex Analysis and Optimization, Athena Scientific, 2003.

  9. M. Schmidt. https://yandex.st/lego/_/la6qi18z8lwgnzdsar1qy1gwcwo.gifNotes on Big-n Problems, 2012.



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

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



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

Классическое определение метрики и метрического пространства. Аксиоматическое задание метрики. Построение топологии по метрике. Пространства сходящихся последовательностей. Фундаментальные последовательности и полные пространства. Роль аксиомы треугольника и непрерывность метрики. Роль аксиомы сепарабельности и единственность предела сходящейся последовательности. Сопоставление метрик и отношений эквивалентности, 0,1-метрики. Различные модификации системы аксиом метрики и их интерпретация: расстояние, полуметрика, ультра-метрика, квази-метрика, неравенство Птолемея.

Локальные метрики и их продолжение на всё пространство. Формализация понятия «между» в метрическом пространстве. Выпуклость метрического пространства по Менгеру. Аксиомы существования и единственности точек между заданными точками. Аксиомы существования и единственности продолжения луча. Теорема о единственности продолжения локально совпадающих метрик. Практический пример проверки аксиом и использования локального продолжения метрики.

Геометрические подмножества общих метрических пространств. Понятия открытого и замкнутого шара, их согласованность с топологией метрического пространства. Понятия открытого и замкнутого обобщенного эллипсоида. Клетки Дирихле («сферы влияния»), автоматическое исправление ошибок. Геометрическое место точек, равноудаленных от заданных точек, проблема меры указанного подмножества. Понятие кривой в метрическом пространстве, длина кривой. Геодезическая линия, кривая наименьшей длины, сегмент. Свойство совпадения геодезических с множествами равноудаленных точек в обобщенных евклидовых пространствах.

Примеры метрических пространств. Пространство изолированных точек, дискретная топология. Метрики l_1 (городских кварталов), l_2 (евклидова), l_\infty (Чебышёва). Их физический смысл. Метрика l_p (Минковского). Форма шаров, вложенность единичных шаров. Зависимость объема шара от размерности пространства. Проблема сопоставления объема шаров в разных метриках с ростом размерности. Проблема единственности кратчайшего пути. Хаусдорфова метрика и другие метрики между подмножествами метрического пространства, индуцированные исходной метрикой между точками. Расстояния между функциями (графиками). Метрики на декартовом произведении метрических пространств. Случай конечного и бесконечного числа сомножителей, метрики на последовательностях.

Классификация функций сходства. Сопоставление значений: номинальные, порядковые, арифметические (интервальные, относительные, разностные, абсолютные) шкалы. Понятие о граничных объектах. Аксиомы сходства, главный и вспомогательный аргументы. Классификация мер сходства по одному свойству (признаку). Функции сходства на декартовом произведении пространств со значениями в различных шкалах.

Характеристики метрик. Инвариантность расстояния относительно сдвига, поворота. Инвариантность формы шаров относительно положения центра и направления на центр. Инвариантность объема шаров относительно положения центра и направления на центр. Ограниченность метрики. Ограниченность шаров. Понятие полностью абсолютных и полностью относительных метрик, промежуточные метрики. Выпуклость шаров. Односвязность шаров. Существование и единственность сегментов, непрерывность сегментов.

Преобразования метрик. Изометрические преобразования пространств. Преобразования функций, сохраняющие метрические свойства. Некоторые достаточные условия преобразований, сохраняющих метрические свойства. Ограничение значений метрики (range companders). Примеры универсальных компандеров. Возможность монотонного преобразования произвольной функции в метрику. Возможность линейного преобразования произвольной ограниченной функции в метрику. Нормализация метрик, зависимость от точки отсчета. Переход от булеанов конечных множеств к пространствам бинарных векторов, соответствие мощности множества и длины вектора.

Реализация метрик. Реализация конечных метрик точками ЛВП, точечные конфигурации. Алгоритмическая сложность решения задачи точного вложения в линейные пространства с метриками. Примеры МК, имеющих или не имеющих точную реализацию. Задача поиска оптимальной точечной конфигурации в пространстве малой размерности, методы метрического и неметрического многомерного шкалирования. Реализация многомерных данных элементами функциональных пространств. Методы визуализации многомерных данных: параллельные координатные оси, графики Эндрюса, шкалирование и иерархии, таблицы проекций, параметризованные глифы (звезды, лица Чернова).

Принцип самоорганизации. Принцип самоорганизации при построении эвристических информационных моделей. Понятие представителей, мера сходства между объектами и представителями. Функции представительства и назначений, структура метода. Самоорганизация в задаче кластеризации. Самоорганизация и задача факторного анализа, самоорганизация и задача дискриминантного анализа. Модификация прецедентной информации, понятие типологического дискриминантного анализа. Самоорганизация и задача восстановления пропусков.

Метрики на конечных множествах. Представление метрик таблицами попарных расстояний. Метрическая конфигурация (МК). Специальное линейное пространство метрических конфигураций. Система неравенств треугольника как определение полиэдрального конуса полуметрик. Грани и экстремальные лучи полуметрического конуса, проблема их определения. Векторное представление метрических конфигураций. Достаточные условия сохранения метрических свойств покомпонентными корректорами метрических конфигураций. Примеры использования достаточных условий. Несовместимость метрических свойств и ортогональности метрических конфигураций.

Разложение МК по конечным системам МК. Полные системы, базисы МК. Проблема использования переполненных систем МК. Гомогенные базисы, интерпретация коэффициентов разложения. Ранг МК. Ранговые и полуметрические ранговые базисы. Неполные системы, оптимальная аппроксимация МК. Разложение по системе «отдельных объектов», метрика попарных сумм, эффективное вычисление признака «общая удаленность» для индивидуальных объектов.

Литература

Каталог: sites -> cmc -> files -> docs
sites -> Выпускных квалификационных работ
sites -> Федеральное государственное бюджетное
sites -> Рабочая программа дисциплины Педагогика высшей школы Направление подготовки 030100 Философия
sites -> Тьюторская система обучения в современном образовании англии 13. 00. 01 общая педагогика, история педагогики и образования
sites -> Образовательная программа подготовки научно-педагогических кадров в аспирантуре по направлению подготовки 44. 06. 01 Образование и педагогические науки
sites -> Работа с семьей: проблемы и методы их решения. На заметку социальному работнику
sites -> Пояснительная записка Содержание и контекст Методы обучения
sites -> Проблематика сопровождения детей из неблагополучных семей
docs -> Кафедра ая спецкурсы для аспирантов (все курсы полугодовые, осенний семестр) «Алгоритмическая поддержка Интернет-технологий»


Поделитесь с Вашими друзьями:
  1   2   3


База данных защищена авторским правом ©psihdocs.ru 2019
обратиться к администрации

    Главная страница