• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Контакты

Адрес: 109028, г. Москва, Покровский бульвар, д. 11

Телефон: +7 (495) 531-00-00 *27254

Email: computerscience@hse.ru

 

Руководство
Первый заместитель декана Вознесенская Тамара Васильевна
Заместитель декана по научной работе и международному сотрудничеству Объедков Сергей Александрович
Заместитель декана по учебно-методической работе Самоненко Илья Юрьевич
Заместитель декана по развитию и административно-финансовой работе Плисецкая Ирина Александровна
Образовательные программы
Бакалаврская программа

Прикладная математика и информатика

4 года
Очная форма обучения
126/80/30
126 бюджетных мест
80 платных мест
30 платных мест для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Бакалаврская программа

Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных"

4 года
Очная форма обучения
100/12
100 платных мест
12 платных мест для иностранцев
ENG
Обучение ведётся на английском языке
Бакалаврская программа

Программная инженерия

4 года
Очная форма обучения
124/85/30
124 бюджетных мест
85 платных мест
30 платных мест для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Магистерская программа

Анализ данных в биологии и медицине

2 года
Очная форма обучения
20/5/1
20 бюджетных мест
5 платных мест
1 платное место для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Магистерская программа

Магистр по наукам о данных

2 года
Заочная
100
100 платных мест
ENG
Обучение ведётся на английском языке
Магистерская программа

Науки о данных

2 года
Очная форма обучения
60/15/20
60 бюджетных мест
15 платных мест
20 платных мест для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Магистерская программа

Системная и программная инженерия

2 года
Очная форма обучения
25/5/15
25 бюджетных мест
5 платных мест
15 платных мест для иностранцев
ENG
Обучение ведётся на английском языке
Магистерская программа

Системное программирование

2 года
Очная форма обучения
15/5/2
15 бюджетных мест
5 платных мест
2 платных места для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Магистерская программа

Статистическая теория обучения

2 года
Очная форма обучения
15/5/2
15 бюджетных мест
5 платных мест
2 платных места для иностранцев
ENG
Обучение ведётся на английском языке
Магистерская программа

Финансовые технологии и анализ данных

2 года
Очная форма обучения
35/1
35 платных мест
1 платное место для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Глава в книге
Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise

Kaledin M., Moulines E., Naumov A. et al.

In bk.: Proceedings of Machine Learning Research. Vol. 125: Proceedings of Thirty Third Conference on Learning Theory. 2020. P. 2144-2203.

Глава в книге
Re-pairing brackets

Chistikov D., Mikhail Vyalyi.

In bk.: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020. Association for Computing Machinery (ACM), 2020. P. 312-326.

Статья
Influence of Very Large Spatial Heterogeneity on Estimates of Sea-Level Trends

Shapoval A., Le Mouël J., Courtillot V. et al.

Applied Mathematics and Computation. 2020. Vol. 386. P. 125485.

Статья
Magnetohydrodynamic Modeling of the Solar Wind Key Parameters and Current Sheets in the Heliosphere: Radial and Solar Cycle Evolution

E. V. Maiewski, Kislov R. A., Khabarova O. V. et al.

Astrophysical Journal. 2020. Vol. 892. No. 1. P. 1-17.

Студент ПМИ нашел оптимальный алгоритм решения задачи поиска барицентра Вассерштейна

Даниил Тяпкин

Даниил Тяпкин
Центр "Сириус"

В конце августа в центре "Сириус" прошла школа "Управление, информация и оптимизация". На ней студент 4 курса ПМИ Даниил Тяпкин вывел оптимальный алгоритм решения задачи поиска барицентра Вассерштейна, которой занимался с начала 2020 года. Даниил рассказал об истории задачи и ее возможном практическом применении.

О себе и о математике

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

Учиться на ФКН для меня достаточно напряжно, так как я добрал дополнительные к стандартной программе ФКН курсы: в обучении мне все очень нравится кроме того, что у нас не очень много именно математических предметов по выбору. Однако на моей специализации это компенсируется возможностью добирать различные курсы, поэтому я не сильно жалуюсь.

История решения 

Впервые про барицентры Вассерштейна я услышал зимой на семинаре вышкинской G2PS-group под руководством Кентана Пари. Потом мне снова встретилась эта задача во время работы над проектом по непрерывной оптимизации на курсе Александра Владимировича Гасникова. Тогда я попросил у него задание, связанное с оптимальным транспортом, и он предложил мне подумать над одной из вариаций задачи про барицентры и показал подход, который хотелось бы использовать. В мае — июне я всерьез занимался этой задачей и получил нетривиальные результаты, которые мы попытались подать на конференцию NeurIPS, но спешка на последних этапах сильно ухудшила впечатление от работы, и пройти на неё не получилось.

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

История самой задачи

Поиск барицентра Вассерштейна — это не самая известная задача, но у нее достаточно интересная история. В XVIII веке французский математик Гаспар Монж впервые начал решать задачу оптимальной транспортировки. Насколько я знаю, он задавался вопросом как передвинуть ядра в яму, затратив наименьшие усилия, но в том виде, в каком он сформулировал задачу, она оказалась слишком сложной. В XX веке наш соотечественник Леонид Витальевич Канторович привел эту задачу к более современному виду, после чего ее получилось решить. 

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

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

Способ решения задачи появился почти сразу после формулировки Канторовича, но вопрос оптимальности решения все еще был актуален — им я и занимался. В моем конкретном случае рассматривался пример, когда мы хотим решать задачу не очень точно, но для большого количества картинок, а именно для размера 1000 на 1000; предыдущее решение этой задачи давало ответ только для десяти картинок.

А где применять?

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

Сложно сказать, что ждет это решение дальше. Сейчас мы с Дариной Двинских работаем над препринтом статьи, а потом — посмотрим.