Участник:Vokov

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Изображение:VorontsovFace.jpg    Воронцов Константин Вячеславович

д.ф.-м.н.
Зам. директора по науке ЗАО «Форексис», www.forecsys.ru.
С.н.с. Вычислительного центра РАН.
Зам. зав. каф. «Интеллектуальные системы» ФУПМ МФТИ.
Доц. каф. «Математические методы прогнозирования» ВМиК МГУ.
Преподаватель Школы анализа данных Яндекс.

Один из идеологов и Администраторов ресурса MachineLearning.RU.

Прочие подробности — на подстранице Curriculum vitæ.

Мне можно написать письмо.


Учебные материалы

Курсы лекций

Семинары

Рекомендации для студентов и аспирантов

Методические рекомендации для преподавателей

Диссертация

Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с.  (подробнее)

Защита состоялась 22 апреля 2010 года в ВЦ РАН. Учёный совет квалифицировал работу как новое направление в теории статистического обучения. Текст автореферата. Презентация доклада на защите. Замечания, вопросы, найденные ошибки и опечатки, пожалуйста, присылайте по почте. Дискуссию можно вести в обсуждении страниц Расслоение и сходство алгоритмов (виртуальный семинар) и Слабая вероятностная аксиоматика.

Выступления на конференциях и семинарах

  • 12 января 2011. Интеллектуальный анализ данных и объектно-ориентированное программирование. Лекция на Зимней компьютерной школе 2011, МФТИ. (PDF, 960 КБ).
  • 7 ноября 2010. Generalization bounds based on the splitting and connectivity properties of a set of classifiers. International conference PRIA-10 (PDF, 1.4 MБ).
  • 20 октября 2010. Точные комбинаторные оценки обобщающей способности онлайнового обучения. Конференция ИОИ-8 (PDF, 400 KБ).
  • 18 октября 2010. Комбинаторный подход к выводу точных оценок вероятности переобучения. Конференция ИОИ-8 (PDF, 1.2 MБ).
  • 22 апреля 2010. Комбинаторная теория надёжности обучения по прецедентам. Защита докторской диссертации. (PDF, 1760 КБ).
  • 3 марта 2010. Интеллектуальный анализ данных и распознавание образов. Теоретические и практические проблемы. Доклад на семинаре «Глобальные изменения климата» (руководители академик Г.И.Марчук, академик В.П.Дымников), Москва, ИВМ. (PDF, 828 КБ).
  • 13 января 2010. Задачи и методы машинного обучения. Лекция на Зимней компьютерной школе 2010, МФТИ. (PDF, 1023 КБ).
  • 22 сентября 2009. Комбинаторный подход к проблеме переобучения. Доклад на конференции ММРО-14, Суздаль. (PDF, 1106 КБ).
  • 27 июля 2009. Методы машинного обучения, основанные на индукции правил (логические методы классификации). Доклад на семинаре Знания и онтологии ELSEWHERE, Москва, ВШЭ. (PDF, 1202 КБ).
  • 10 ноября 2008. Методы коллаборативной фильтрации и их применение. Выступление на семинаре Б.Г.Миркина, ВШЭ. (PDF, 1083 КБ).
  • 17 сентября 2008. Пути повышения точности оценок обобщающей способности (комбинаторный подход). Пленарный доклад на международной конференции РОАИ-9-2008, Нижний Новгород. Презентация на английском (PDF, 846 КБ), на русском (PDF, 844 КБ), тезисы доклада на русском (PDF, 243 КБ).
  • 17 сентября 2008. Презентация ресурса www.MachineLearning.ru в рамках международной конференции РОАИ-9-2008, Нижний Новгород. (PDF, 285 КБ, на английском).
  • 13 июня 2008. Вики-ресурс MachineLearning.RU: концепция и перспективы, круглый стол в рамках конференции ИОИ-2008, Крым, Алушта. (PDF, 198 КБ).
  • 12 июня 2008. Слабая вероятностная аксиоматика, оценки надёжности эмпирических предсказаний, расслоение и различность алгоритмов. Конференция ИОИ-2008, Крым, Алушта. (PDF, 950 КБ)
  • 28 апреля 2008. О некоторых задачах интеллектуального анализа данных — одна лекция в рамках курса «Современные проблемы прикладной математики» для студентов 5 курса ВМиК МГУ. (PDF, 764Кб).
  • 28 апреля 2008. Ломоносовские чтения 2008. Оценки надёжности эмпирических предсказаний (комбинаторный подход). (PDF, 804 КБ).
  • 20 august 2007. 7th Open German/Russian Workshop (OGRW-7) on Pattern Recognition and Image Understanding, Ettlingen, Germany. Combinatorial Approach to Generalization Bounds Tightening. (PDF, 1895 KБ, на английском).
  • 5 ноября 2005. ММРО-12. Измерение локальной эффективной функции роста в задачах поиска логических закономерностей. (PDF, 285 КБ), вместе с речью — (PDF, 308 КБ).

Научные интересы

Всё, что скрывается за терминами «интеллектуальный анализ данных» (data mining) и «машинное обучение» (machine learning): распознавание образов, прогнозирование, математическая статистика, дискретная математика, численные методы оптимизации, а также практический анализ данных в разнообразных областях (экономика, медицина, техника, биоинформатика, интернет).

Теория обобщающей способности

Основная статья: Расслоение и сходство алгоритмов (виртуальный семинар)

Проблема обобщающей способности является ключевой и в то же время наиболее сложной в машинном обучении. Её даже выделяют в отдельную дисциплину — теорию вычислительного обучения. Если алгоритм, восстанавливающий некоторую неизвестную зависимость, построен по конечной обучающей выборке прецедентов, то как предсказать качество его работы на контрольной выборке, состоящей из новых прецедентов? Почему это вообще возможно? Как надо обучать алгоритм, чтобы он редко ошибался на новых данных?

Активное исследование этих вопросов началось в конце 60-х, когда В.Н.Вапник и А.Я.Червоненкис предложили статистическую теорию восстановления зависимостей по эмпирическим данным (VC theory) и получили верхние оценки вероятности ошибки обученного алгоритма (VC-bounds). Эти оценки позволили обосновать давно замеченный эмпирический факт: по мере увеличения сложности используемого семейства алгоритмов качество обучения сначала улучшается, затем начинает ухудшаться. Ухудшение связано с эффектом переобучения. Если алгоритм имеет избыточное число параметров («степеней свободы»), то он может слишком точно настроиться на конкретную обучающую выборку в ущерб качеству восстановления зависимости в целом. В теории Вапника-Червоненкиса разработан метод структурной минимизации риска (СМР), позволяющий автоматически находить модель оптимальной сложности. К сожалению, оценки вероятности ошибки чрезвычайно завышены (осторожны, пессимистичны), что может приводить к переупрощению модели в методе СМР. Несмотря на 40-летние усилия многих ученых и существенное усложнение математического аппарата, точные оценки до сих пор не были получены.

Комбинаторная теория переобучения — это принципиально новый подход, основанный на слабой вероятностной аксиоматике, впервые позволивший получить точные (не завышенные, не асимптотические) комбинаторные оценки вероятности переобучения и показать ключевую роль эффектов расслоения и сходства в семействах алгоритмов. Пока что точные оценки получены лишь для ряда модельных семейств алгоритмов, обладающих некоторой регулярной структурой. Для реальных смейств удалось получить верхние оценки расслоения-связности — SC-оценки (splitting and connectivity bounds). Они завышены в разы, тогда как VC-оценки завышены на 5–8 порядков. Для некоторых модельных семейств SC-оценки являются точными. Тем не менее, проблемы остаются, и дело не только в завышенности оценок. Во-первых, SC-оценки могут быть ненаблюдаемыми, то есть в них могут входить некоторые функции от скрытых контрольных данных. Эти функции вполне можно оценивать по наблюдаемым обучающим данным, но это дополнительная работа. Во-вторых, SC-оценки могут быть вычислительно неэффективными и требовать неадекватно больших затрат памяти и времени. Получение приближённых или асимптотических SC-оценок гарантированной точности также является отдельной работой.

Пока имеется лишь два примера практического применения комбинаторных оценок обобщающей способности:

  • Модификация критериев информативности для уменьшения переобучения конъюнктивных закономерностей в логических алгоритмах классификации (Андрей Ивахненко).
  • Эффективный алгоритм отбора эталонных объектов в методе ближайших соседей (Максим Иванов).

Основная цель дальнейших исследований — доведение комбинаторной теории переобучения до уровня практической применимости.

Основные направления дальнейших исследований:

  • разработка математической техники для перехода от ненаблюдаемых оценок к наблюдаемым (возможно, как на основе комбинаторики, так и на основе теории концентрации вероятностной меры);
  • исследование комбинаторно-статистических свойств графа расслоения-связности модельных и реальных семейств алгоритмов.
  • получение оценок вероятности переобучения через наблюдаемый профиль расслоения-связности;
  • разработка эффективных методов оценивания нижних слоёв профиля расслоения-связности в конкретных методах обучения;
  • разработка логических алгоритмов классификации с управляемой переобученностью логических закономерностей;
  • развитие понятия «плотности» семейства алгоритмов и изучение возможности аппроксимации «плотных» семейств их «разреженными» подсемействами малой мощности;
  • развитие понятия «комбинаторного отступа» и его использование для повышения обобщающей способности линейных классификаторов;
  • развитие понятия локальной радемахеровской сложности для более аккуратного учёта эффектов расслоения и сходства;
  • обобщение понятий расслоения и сходства алгоритмов для непрерывных функций потерь;
  • разработка эффективных метрических алгоритмов классификации на основе комбинаторных оценок полного скользящего контроля;
  • исследование связи профилей компактности с функциями конкурентного сходства;
  • разработка методики тестирования и анализа обобщающей способности для «Полигона алгоритмов классификации».

Ключевые слова: overfitting, generalization bounds, computational learning theory, Vapnik-Chervonenkis theory, local Rademacher complexity.

Комбинаторная (перестановочная) статистика

Основная статья: Слабая вероятностная аксиоматика

Это направление логично вытекает из предыдущего и является его обобщением. Оказывается, многие фундаментальные факты теории вероятностей и математической статистики можно переформулировать и доказать, не опираясь на колмогоровскую аксиоматику, то есть не используя теорию меры, и даже не употребляя само понятие вероятности. В задачах анализа данных мы всегда имеем дело с выборками конечной длины. Поэтому естественно ставить вопрос не «какова вероятность события?», а «какой может быть частота этого события на скрытых (пока еще не известных) данных?». Ответы на эти два вопроса, вообще говоря, различны, причем на выборках малой длины различие существенно. Вероятность события — абстрактная идеализированная величина. Частота события — это как раз то, что реально измеряется в эксперименте. Именно её и имеет смысл оценивать (предсказывать).

Слабая вероятностная аксиоматика основана на одной единственной аксиоме: рассматривается конечная выборка неслучайных объектов, которые появляются в случайном порядке, причём все перестановки равновероятны. Событие — это бинарная функция на множестве всех перестановок выборки. Вероятность события определяется как доля перестановок выборки, при которых эта бинарная функция принимает единичное значение (т.е. событие имеет место).

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

Основные направления исследований:

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

Ключевые слова: exchangeability, permutational statistics, concentration of probability measure.

Алгоритмические композиции

Основная статья: Композиция алгоритмов

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

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

Идея алгоритмических композиций была выдвинута в середине 70-х годов в работах академика РАН Ю.И.Журавлева. В зарубежных исследованиях это тема стала чрезвычайно популярной в 90-е годы, после изобретения алгоритмов бустинга, бэггинга, смесей экспертов и других композитных конструкций.

Основные направления исследований:

Ключевые слова: multiple classifier systems, ensemble learning, classifier fusion, mixture of experts.

Анализ клиентских сред и коллаборативная фильтрация

Основная статья: Анализ клиентских сред

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

Имеется некоторый набор ресурсов (товаров, услуг, предметов), которыми пользуется огромное количество клиентов. Все действия пользователей протоколируются в электронном виде. Эти данные содержат ценнейшую информацию, необходимую для повышения качества оказываемых услуг, однако извлечь её не так просто ввиду огромного объема данных. Какие ресурсы наиболее популярны, и среди каких групп клиентов? Возможно ли угадать интересы клиента и сформировать для него персональное предложение, от которого он с высокой вероятностью не откажется? Как выявить клиентов, собирающихся в ближайшее время отказаться от обслуживания? Эти и другие задачи решаются в системах управления взаимоотношениями с клиентами (client relationship management, CRM). Создание математического обеспечения для них является актуальной наукоемкой задачей.

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

Основные направления исследований:

Ключевые слова: collaborative filtering, recommender systems, personalization, web mining, web usage mining, client relationship management, matrix factorization, probabilistic latent semantic indexing.

Адаптивное обучение

Основная статья: Адаптивное обучение

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

Основные направления исследований:

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

Ключевые слова: online learning, incremental learning, adaptive learning, reinforcement learning.

Прогнозирование объёмов продаж

Основная статья: Прогнозирование объёмов продаж

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

Основные направления исследований:

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

Ключевые слова: sales forecast, density forecast, forecasting under asymmetric loss.

Биоинформатика

Основная статья: Биоинформатика

Основные направления исследований:

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

Другие проекты

Публикации

Список публикаций

Софт

Библиотека деловой и научной графики. Удобный инструмент для аналитических исследований, генерации графиков в Internet, подготовки отчетов, выполнения курсовых и дипломных работ, встраивания графиков в приложения на Delphi и C#. Имеет собственный формат входных данных CHD (CHart Description), позволяющий описывать как таблицы данных, так и внешний вид графика. Поддерживается более 150 команд, более 50 свойств точек графика, имеется встроенный калькулятор арифметических выражений. Графики могут быть выведены в окно прикладной программы, на принтер, в буфер обмена, в файлы графических форматов BMP, EMF, PNG, JPEG, GIF. Имеется программа chdView.exe для просмотра CHD-файлов.

Планы по развитию MachineLearning.RU

Сильно недописанные статьи

Немного недописанные статьи

Статьи, нуждающиеся в доработке

Базовые понятия

Статистика

Теория вычислительного обучения

Байесовская теория классификации

Классификация на основе сходства

Классификация на основе разделимости

Байесовский вывод

Нейронные сети

Логические алгоритмы классификации

Кластерный анализ

Корреляционный анализ и регрессия

Прогнозирование

Сокращение размерности

Алгоритмические композиции

Предварительный анализ данных

Projection pursuit

Интеллектуальный анализ данных

Теории, научные школы

Предметные области

Внутренняя кухня MachineLearning.ru

Служебные страницы

Интересные спецстраницы

Шаблоны

Мои шаблоны

Основные шаблоны для библиографий:

Вспомогательные шаблоны для библиографий:

Программирование в шаблонах:

Литература (страницы публикаций)

  1. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 416 с.  (подробнее)
  2. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с.  (подробнее)
  3. Журавлёв, Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики: Вып.33. — 1978. — С. 5–68.  (подробнее)
  4. Журавлёв, Ю. И., Рязанов, В. В., Сенько, О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: ФАЗИС, 2006. — 176 с.  (подробнее)
  5. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. — 270 с. — ISBN 5-86134-060-9  (подробнее)
  6. Зиновьев, А. Ю. Визуализация многомерных данных. — Издательство Красноярского государственного технического университета, 2000. — 180 с.  (подробнее)
  7. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр АН СССР, 1992. — 274 с.  (подробнее)
  8. Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p.  (подробнее)

Аспиранты и студенты

Аспиранты ФУПМ МФТИ ВМиК МГУ
  • Юрий Янович
  • Никита Спирин
  • Игорь Литвинов
  • Александр Фирстенко
  • Александр Мафусалов
  • Никита Животовский
  • Дмитрий Солодкин
  • Марина Дударенко
  • Александр Колесников
  • Ольга Исупова
  • Иван Шанин
  • Евгений Соколов
  • Валентин Полежаев
Выпускники:

Cсылки

Мои подстраницы

Vokov/CVVokov/Publications
Vokov/Вики-ресурс MachineLearning.RU: концепция и перспективы
Vokov/Иллюзия простоты выбораVokov/Интервью для InTalent.proVokov/Интервью для Кота Шрёдингера 2017-10-04
Vokov/Интервью для Новой газеты 2019-02-25Vokov/Интервью для ПостНауки 2017-09-27Vokov/Интервью для РИА Новости 2020-05-25
Vokov/Комбинаторная статистика
Vokov/НаучпопVokov/Некоторые задачи интеллектуального анализа данных (лекция)
Vokov/ПесочницаVokov/Планы по развитию MachineLearning.RUVokov/Публикации

Написать письмо К.В.Воронцову.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Vokov»
Личные инструменты