Проект «Новые алгоритмы машинного обучения и компьютерного зрения и их высокопроизводительные реализации»

Краткое описание

Машинное обучение — актуальная и интенсивно развивающаяся область научного знания и передовая технологическая дисциплина. Общая задача машинного обучения заключается в восстановлении заранее не известной зависимости по выборке, составленной из пар «вход–выход». Если выход представляет вещественную переменную, то задача называется задачей восстановления регрессии, если выход принимает конечное число значений, то получаем задачу классификации, если входы и выходы — это значения некоторых величин в моменты времени, то говорят о задаче прогнозирования. Восстановление регрессии появляется уже в работах К. Гаусса и А. Лежандра. Задачи прогнозирования и классификации появляются значительно позже. Всплеск интереса к машинному обучению начался в 60-х годах прошлого века. В настоящее время ведутся интенсивные теоретические и прикладные исследования в этой области как в России, так и за рубежом (Ю.И. Журавлев, В.Н. Вапник, А.Я. Червоненкис,  К.В. Рудаков, Н.Г. Загоруйко, К.В. Воронцов, J. Friedman, L. Breiman, Y. Freund, R. Schapire, P.L. Bartlett, R. Tibshirani, T. Hastie и многие другие). Данной дисциплине посвящены  многие регулярно проводимые международные конференции, например:

  • «Интеллектуализация обработки информации»,
  • «Распознавание образов и анализ изображений»,
  • «Математические методы распознавания образов»,
  • «International Conference on Machine Learning»,
  • «Computation Learning Theory»,
  • «IEEE Conference on Computer Vision and Pattern Recognition»,
  • «International Conference on Computer Vision»,
  • «IEEE International Conference on Data Mining»;

научные журналы:

  • «Pattern Recognition and Image Analysis»,
  • «Journal of Machine Learning Research»,
  •  «IEEE Transactions on Pattern Analysis and Ma­chine Intelligence»,
  • «Machine Learning Journal»

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

  • распознавание образов,
  • интеллектуальный анализ данных (Data Min­ing),
  • обработка естественных языков,
  • компьютерное зрение,
  • медицин­ская диагностика,
  • биоинформатика,
  • ро­бототехника

и др.

Цели

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

Коллектив

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

Основные направления работы

Чрезвычайно актуальной в машинном обучении является проблема обработки больших объемов данных (обучающей выборки). Многие современные алгоритмы, обладающие хорошей обобщающей способностью, имеют высокую вычислительную сложность, и поэтому их не удается применять для решения больших задач. Кроме того, многие алгоритмы вообще не имеют свободно распространяемых реализаций, сравнимых с передовым коммерческим программным обеспечением, что затрудняет использование алгоритмов в приложениях. Другой проблемой, возникающей в машинном обучении, является нарушение принципа независимости наблюдений в обучающей выборке, в то время когда большинство алгоритмов предполагает этот принцип соблюденным.

Проект призван в некоторой степени решить данные проблемы. Среди алгоритмов машинного обучения хорошо зарекомендовали себя на практике ансамбли деревьев решений, в частности алгоритм Gradient Boosting Trees (GBT). Его основная идея — использование аналога метода наискорейшего спуска для построения аддитивной модели, компонентами которой являются деревья решений. Алгоритм устойчив и хорошо работает с пропущенными значениями. Многие исследователи сообщали о положительном опыте его использования, как для задач восстановления регрессии, так и для задач классификации. Открытая реализация этого метода, в настоящее время входящая в состав библиотеки с открытым кодом OpenCV, выполнена участниками проекта в рамках работ по государственному контракту №02.740.11.5131 федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы. Однако, как уже отмечалось, объемы данных в ряде прикладных задач, например, возникающих при оценке качества интернет-рекламы (predicting bounce rates in sponsored search advertising), поисковом ранжировании (web-search ranking) и др., таковы, что требуется разработка и реализация высокопроизводительной модификации алгоритма, предназначенной для работы с данными, распределенными по вычислительным узлам.

Одно из возможных направлений использования алгоритма Gradient Boosting Trees заключается в его применении в задачах распознавания и детектирования объектов на изображениях. В частности, в последнее время все больше внимания в этой области уделяется системам ADAS (передовым системам помощи водителю, Advanced Driver Assistance Systems), предназначенным для анализа обстановки, в которой находится транспортное средство, и принятия действий по предотвращению аварийных ситуаций в случае необходимости. Особое значение имеют системы, предотвращающие столкновения транспортных средств с пешеходами. Разработки в этой области ведутся многими мировыми автопроизводителями, например Volvo (http://www.volvocars.com/intl/top/about/corporate/volvo-sustainability/safety/pages/default.aspx). Системы данного типа представляют собой сложные многоуровневые программные комплексы, составной частью которых неотъемлемо являются методы машинного обучения. Традиционно, при решении данной задачи используются такие алгоритмы обучения с учителем, как машина опорных векторов (SVM) и адаптивный бустинг (AdaBoost). Планируется провести анализ эффективности использования других классификаторов, представляющих собой ансамбли деревьев решений, а также различных типов признаков, выделяемых из изображения, с целью повышения точности работы системы. Также необходимо отметить, что наряду с точностью, для систем подобного уровня крайне важна скорость работы (детектирование пешеходов на видео потоке в режиме реального времени), что требует применения техник выделения интересующих областей на изображениях (ROI) и снижения количества используемых для работы классификатора признаков. В рамках данного проекта планируется разработка и реализация алгоритмов выделения значимых признаков на основе ансамблей деревьев решений.

Другим возможным применением алгоритма Gradient Boosting Trees является его использование в задачах классификации изображений с большим числом категорий объектов (задачи подобного рода возникают в различных прикладных областях: например, поиск изображений по ключевым словам, корректное распознавание объектов для робототехники). До последнего времени задачи подобного рода не исследовались, в том числе и ввиду вычислительной сложности. Впервые проведенные в 2010 г. вычислительные эксперименты подобного рода показали, что применение общепризнанных на настоящее время алгоритмов не дает удовлетворительной точности распознавания. В работах выдвинута и экспериментально подтверждена гипотеза, что использование знаний о семантической иерархии категорий объектов может привести к улучшению качества распознавания.  Предполагается разработка и реализация модифицированной версии алгоритмов классификации, учитывающих семантическую иерархию объектов, на основе ансамблей деревьев решений (в частности, Gradient Boosting Trees). Для целого ряда приложений представляет значительный интерес метод Latent SVM. Его основная идея взята из алгоритма MI-SVM, который, в свою очередь, есть модификация хорошо известного метода SVM — Support Vector Machine (машина опорных векторов). В результате получаем итерационный алгоритм, в ходе работы которого попеременно фиксируется латентная переменная, и затем решается задача квадратичного программирования. Многими авторами сообщается о положительном опыте его использования для задач распознавания объектов. Открытая реализация этого метода, в настоящее время входящая в состав библиотеки с открытым кодом OpenCV, выполнена в рамках работ по государственному контракту №02.740.11.5131 федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы. Предполагается адаптация и модификация алгоритма с целью его использования в задаче подсчета числа транспортных средств, пересекающих определенный участок дороги.

Задача не является новой, о чем свидетельствуют многочисленные разработки в данном направлении (http://www.againc.net/ru/production/its), (http://ru-patent.info/21/30-34/2132073.html). Тем не менее, она не теряет актуальности до настоящего момента, т.к. решение указанной задачи позволит эффективно выполнять  автоматическое регулирование движения, принимать обоснованные решения о необходимости строительства дорог-дублеров и развязок, целенаправленно проектировать дорожную сеть в масштабах города и страны. Большинство предлагаемых решений используют различного рода датчики, что осложняет этап апробации и приводит к повышению его стоимости. Существуют решения (например, http://mcajournal.org/volume14/Vol14No3p187.pdf), которые позволяют решать задачу на основании видеоинформации, но они, как правило, проводят упрощенную классификацию транспортных средств и используют более примитивные объекты (в частности, автомобильные номера) для детектирования транспортных средств. Необходимым условием решения задачи с использованием Latent SVM является повышение качества поиска объектов на следующих классах транспортных средств: автомобили, автобусы, велосипеды, мотоциклы. Модуль подсчета количества транспортных средств впоследствии может быть использован для регулирования транспортного потока, а также для сбора статистики на различных контрольно-пропускных пунктах (заводы, торговые комплексы, пассажирские предприятия). Планируется разработка новых алгоритмов, методов и высокопроизводительных компьютерных программ в области машинного обучения и компьютерного зрения, а именно:

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

Проекты

  1. НИР по теме «Высокопроизводительные вычисления в машинном обучении для анализа больших объемов данных», госконтракт №02.740.11.5131 (2010-2011). Руководитель проекта – проф. Мошков М.Ю.
  2. НИР по теме «Новые алгоритмы машинного обучения и компьютерного зрения и их высокопроизводительные реализации», госконтракт №11.519.11.4015 (2011-2013). Руководитель проекта – проф. Гергель В.П.

Основные результаты

  1. Разработаны рекомендации по модернизации учебного курса по машинному обучению. Проведен анализ существующих курсов по машинному обучению, читаемых в ведущих университетах мира. Разработано описание новой лабораторной работы «Градиентный бустинг деревьев решений (Gradient Boosting Trees)».
  2. Разработаны рекомендации к совершенствованию учебных курсов по высокопроизводительным вычислениям. Выработаны требования к разработке новой лабораторной работы «Оптимизация и распараллеливание вычислений в задаче детектирования объектов на изображениях с использованием алгоритма Latent SVM».
  3. Разработана программа внедрения результатов НИР в учебный процесс. Сформулированы основные направления по использованию результатов НИР в учебном процессе факультета ВМК ННГУ.
  4. Разработаны последовательные и параллельные реализации алгоритмов Latent SVM и Gradient Boosting Trees. Реализации интегрированы в библиотеку компьютерного зрения с открытым исходным кодом OpenCV. Исходные коды зарегистрированы: свидетельство о регистрации программы для ЭВМ № 2011616620 (Мееров И.Б., Золотых Н.Ю., Половинкин А.Н., Козинов Е.А., Кустикова В.Д., Сиднев А.А., Капралов Е.И., Рябикин Н.М., Ерухимов В.Л. Скрытый метод опорных векторов для решения задач машинного обучения, зарегистрировано 25 августа 2011 г.) и № 2011616621 (Золотых Н.Ю., Дружков П.Н., Половинкин А.Н., Ерухимов В.Л. Метод решения задач машинного обучения с использованием жадных бустинг-деревьев, зарегистрировано 25 августа 2011 г.).
  5.  Выполнена апробация разработанного алгоритмического и программного обеспечения на практических задачах большой размерности. В частности, протестирована предложенная система динамического обучения ансамбля решающих правил. Проведена апробация разработанных последовательной и параллельной реализаций алгоритма Latent SVM и каскадного алгоритма Latent SVM на реальных задачах по детектированию объектов на изображении (на данных конкурса PASCAL VOC 2007). Выполнено экспериментальное исследование точности решения задач машинного обучения методом градиентного бустинга деревьев решений на задачах из коллекции UCI. Предлагается подход по использованию алгоритма градиентного бустинга деревьев решений для решения следующих практических задач: автоматическое построение классификаторов текстов, детектирование территорий, пострадавших от пожаров, по снимкам; определение стабильности водородной связи в молекуле белка. Для всех решаемых задач подходы, предлагаемые исполнителями НИР, дает лучшие или сравнимые с аналогами результаты по точности предсказания и быстродействия.

Основные публикации

  1. Зелоско Б., Мошков М.Ю., Чикалов И.В. Оптимизация решающих правил, основанная на методах динамического программирования // Вестник Нижегородского государственного университета им. Н.И. Лобачевского. 2010. № 6. С. 195-200.
  2.  Дружков П.Н., Золотых Н.Ю., Половинкин А.Н. Программная реализация алгоритма градиентного бустинга деревьев решений // Вестник Нижегородского государственного университета им. Н.И. Лобачевского. 2011. № 1. С. 193–200.
  3. Druzhkov P.N., Eruhimov V.L., Kozinov E.A., Kustikova V.D., Meyerov I.B., Polovinkin A.N., Zolotykh N.Yu. On some new object detection features in OpenCV library // Международный журнал Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 2011. V.21. № 3. P. 384-386.
  4. Дружков П. Н., Золотых Н. Ю., Половинкин А. Н. Параллельная реализация алгоритма предсказания с помощью модели градиентного бустинга деревьев решений // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2011. №37. С. 82-89.
  5. Е.А. Козинов, В.Д. Кустикова, И.Б. Мееров, А.Н. Половинкин, А.А. Сиднев. Подходы к оптимизации и распараллеливанию вычислений в задаче детектирования объектов разных классов на изображении // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2012.  №47.  С.68-82.

Публикации в материалах конференций

  1. Дружков П.Н., Золотых Н.Ю., Мееров И.Б., Половинкин А.Н. Реализация алгоритма градиентного бустинга деревьев решений // 10-я Международная конференция «Высокопроизводительные вычисления на кластерных системах (HPC-2010)»: Материалы конференции (Пермь, ноябрь 1–3, 2010). Пермь: Изд. ПГТУ, 2010. С. 231–238.
  2. Золотых Н.Ю., Козинов Е.А., Кустикова В.Д., Мееров И.Б., Половинкин А.Н. Об одном подходе к решению задачи поиска объектов на изображениях // 10-я Международная конференция «Высокопроизводительные вычисления на кластерных системах (HPC-2010)»: Материалы конференции (Пермь, ноябрь 1–3, 2010). Пермь: Изд. ПГТУ, 2010. С. 270–277.
  3. Druzhkov P.N., Eruhimov V.L., Kozinov E.A., Kustikova V.D., Meyerov I.B., Polovinkin A.N., Zolotykh N.Yu. On some new object detection features in OpenCV Library // 10th International Conference on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-10-2010). St. Petersburg, December 5–12, 2010. Conference Proceedings (Vol. I–II). Volume II. SPb: Politechnika, 2010. P. 91–93.
  4. Chikalov I., Moshkov M., Zielosko B. Online learning algorithm for ensemble of decision rules. In: Proceedings of the 13th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (RSFDGrC-2011), Moscow, Russia, June 25-27, 2011.
  5. Chikalov I., Moshkov M., Zielosko B. Decision rules for decision tables with many-valued decisions. The 6th International Conference on Rough Sets and Knowledge Technology (RSKT’11), Banff, Canada, October 9-12, 2011.
  6.  Дружков П.Н., Золотых Н.Ю., Половинкин А.Н. Параллельная реализация алгоритма предсказания с помощью модели градиентного бустинга деревьев решений // Параллельные вычислительные технологии (ПаВТ’2011): труды международной научной конференции (Москва, 28 марта – 1 апреля 2011 г.) [Электронный ресурс]. Челябинск: Издательский центр ЮУрГУ, 2011. C. 471–477. – URL:http://omega.sp.susu.ac.ru/books/conference/PaVT2011/short/122.pdf.
  7. Золотых Н.Ю., Козинов Е.А., Кустикова В.Д., Мееров И.Б., Половинкин А.Н. Инфраструктура для параллельного поиска объектов разных классов на изображениях // Параллельные вычислительные технологии (ПаВТ’2011): труды международной научной конференции (Москва, 28 марта – 1 апреля 2011 г.) [Электронный ресурс]. Челябинск: Издательский центр ЮУрГУ, 2011. C. 690.  URL: http://omega.sp.susu.ac.ru/books/conference/PaVT2011/poster/121.pdf.
  8. Золотых Н.Ю., Козинов Е.А., Кустикова В.Д., Мееров И.Б., Половинкин А.Н. Об одном методе повышения скорости поиска объектов методом скрытых опорных векторов за счет применения каскадных схем //11-ая Всероссийская конференция Высокопроизводительные параллельные вычисления на кластерных системах (HPC-2011): Труды конференции (Н.Новгород, 17-19 ноябрь 2011). – Н.Новгород: Изд. ННГУ, 2011. – С. 134-139.
  9. Борисюк Ф.В., Дружков П.Н., Половинкин А.Н. Автоматизация построения тематических классификаторов с использованием алгоритмов машинного обучения // XIII Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции (RCDL’2011)» (Воронеж, 19–22 октября 2011 г.) [Электронный ресурс]. URL: [http://rcdl2011.vsu.ru/doc/full_text/Report.5.3.pdf].
  10.  Е.А. Козинов, В.Д. Кустикова, И.Б. Мееров, А.Н. Половинкин, А.А. Сиднев Подходы к оптимизации и распараллеливанию вычислений в задаче детектирования объектов разных классов на изображении // Параллельные вычислительные технологии (ПаВТ’2012): труды международной научной конференции (Новосибирск, 26-30 марта 2012г.). Челябинск: Издательский центр ЮУрГУ, 2012. С. 202-211.
  11. П.Н. Дружков, А.Н. Половинкин Реализация параллельного алгоритма обучения в методе градиентного бустинга деревьев решений для систем с распределенной памятью // Параллельные вычислительные технологии (ПаВТ’2012): труды международной научной конференции (Новосибирск, 26-30 марта 2012г.). Челябинск: Издательский центр ЮУрГУ, 2012. С. 459-465.

Другие доклады в рамках конференций и научных школ

  1. Stam J., Eruhimov V., Rusu R. B. Extending OpenCV with GPU Acceleration // nVidia GPU Technology Conference 2010.
  2. Ерухимов В.Л. Новые возможности OpenCV // Молодежная школа в рамках международной конференции «Графикон-2010», Санкт-Петербург, 21 сентября 2010. – лекция.
  3. Ерухимов В.Л. Применение технологий машинного обучения // Технологии Microsoft в теории и практике программирования, Нижний Новгород, 13 мая 2010.
  4. М. Ю. Мошков, В. П. Гергель. Высокопроизводительные вычисления в машинном обучении для анализа больших объемов данных // Тезисы всероссийской конференции «Опыт и результаты исследований, проводимых под руководством приглашенных ученых-соотечественников», Москва, 14-15 марта 2011.
  5. Дружков П.Н., Золотых Н.Ю., Козинов Е.А., Кустикова В.Д., Мееров И.Б., Половинкин А.Н. Параллельная реализация некоторых алгоритмов машинного обучения в библиотеке OpenCV // Доклад на IV сессии научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования», Санкт-Петербург, Россия, 12-15 апреля 2011.