Русский
Русский
English
Статистика
Реклама

Вшэ спб

В разработчики пойду, пусть меня научат. Бакалаврские программы при поддержке JetBrains

02.06.2021 14:09:29 | Автор: admin

JetBrains поддерживает образовательные программы для разработчиков в лучших университетах страны. Мы предоставляем экспертную и финансовую помощь разным направлениям в НИУ ВШЭ, Университете ИТМО, СПбГУ, МФТИ, НГУ и ЛЭТИ. Но несколько программ особенные, они реализуются в тесном партнерстве с компанией. JetBrains участвует в формировании учебного плана, подбирает преподавателей, выплачивает студентам спонсорские стипендии, помогает с организацией практик и стажировок.

В преддверии приемной кампании в вузы рассказываем о наших самых ближайших партнерах бакалаврских программах Современное программирование в СПбГУ и Прикладная математика и информатика в петербургском кампусе НИУ ВШЭ.

Занятие у Александра ХраброваЗанятие у Александра Храброва

Современное программирование появилось на рынке образования Петербурга в 2018 году. Прикладная математика и информатика формально открылась в Питерской Вышке также в 2018 году, но фактически переехала из Академического университета, где реализовывалась с 2014 года.

Программы имеют довольно много общего:

1. Тесное партнерство с индустрией

В реализации обеих программ принимают участие ведущие IT-компании. Учебные планы регулярно обновляются в соответствии с потребностями индустрии. Программистские курсы читают разработчики, а математические действующие ученые и заслуженные преподаватели: Денис Москвин, Александр Храбров, Даниил Березун, Богдан Бугаев и др.

2. Индивидуальный подход

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

3. Проектная деятельность

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

4. Обратная связь

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

5. Кураторы

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

6. Стипендии

JetBrains выплачивает студентам спонсорские стипендии до 15 тысяч рублей в месяц. Также с этого года будут введены дополнительные стипендии для студентов-участников школьных международных олимпиад IOI и IMO. Так, члены сборных получат по 10 тысяч рублей в месяц, а медалисты от 15 до 25 тысяч рублей в месяц в зависимости от уровня награды. Стипендия присуждается на два года первый и второй курсы университета.

Если обе программы такие классные, как же тогда выбрать, куда поступать? Расскажем про особенности каждой из программ.

Программа Современное программирование МКН СПбГУ

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

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

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

Программа СП делает акцент на преподавание различных языков и стилей программирования, что позволяет студентам свободно себя чувствовать в любой сфере ИТ и не бояться выйти за пределы традиционных подходов. В обязательных дисциплинах программы студенты изучают и используют такие языки программирования как Kotlin, Python, C/C++, Assembler, Haskell, Prolog, Go, а в рамках дисциплин по выбору также имеют возможность познакомиться с языками Java, Scala, C#, Rust, Javascript и PHP. Поближе познакомиться с учебным планом программы можно здесь.

Преподаватели: Александр Куликов, Виталий Брагилевский, Евгений Линский, Михаил Сенин и другие. Плейлист с представлениями всех курсов первого семестра от лекторов по ссылке.

Как поступить: Для абитуриентов доступны две траектории поступления:

  1. По ЕГЭ. Нужно сдать математику на 76 и более баллов, информатику на 75 и более, русский язык на 55 и более баллов. Учитываются индивидуальные достижения, подробнее о правилах приема: joinmkn.ru/rules.

  1. Без вступительных испытаний по результатам олимпиад: Всероссийской олимпиады школьников по математике, информатике, физике и астрономии, а также олимпиад РСОШ из списка, доступного по ссылке.

Количество мест: 30 бюджетных и 5 платных.

Где проходят занятия: Все пары проходят в центре Санкт-Петербурга на Васильевском острове. Общежитие квартирного типа (Дом студента) расположено там же, в двадцати минутах ходьбы.

Полезные ссылки:

Факультет математики и компьютерных наук СПбГУ объединяет три бакалаврские программы: кроме СП, это программа Математика, возникшая на базе исследовательской лаборатории им. П.Л. Чебышева, а также программа Науки о данных, поддерживаемая компанией Яндекс. Студенты разных направлений часто пересекаются за время учебы, помогая друг другу формировать широкий кругозор и изучать разные варианты карьеры.

Программа Прикладная математика и информатика в НИУ ВШЭ Санкт-Петербург

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

не в теории, а на практике. В первый же год студенты проходят двухсеместровый курс по C++, семестровый курс по Python и Unix, большую часть полуторагодового курса по алгоритмам и структурам данным. Также с самого начала обучения студентов погружают в проектную деятельность. На первом курсе все работают над учебными проектами на С++, на втором пишут на Java или Kotlin. О некоторых проектах можно почитать в блоге факультета на Хабре: анализатор C++, приложение для визуализации аттракторов, гексагональные шахматы, футболка с контролем осанки.

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

Следующая особенность программы это специализации на старших курсах. Сейчас студенты могут выбрать одно из пяти направлений: машинное обучение, промышленное программирование, теоретическая информатика, теория языков программирования и биоинформатика. В каждой специализации есть обязательные дисциплины (например, для машинного обучения это Базы данных, Методы оптимизации, Численные методы, Deep learning, Обработка естественного языка, Анализ изображений и Глубокое обучение с подкреплением), но часть предметов студент выбирает самостоятельно или вместе с научным руководителем. Полный список дисциплин есть на странице.

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

И последняя, но одна из самых приятных особенностей: набор в Питерской Вышке больше, чем в СПбГУ, что делает программу более доступной для абитуриентов, поступающих по результатам ЕГЭ. Если же все бюджетные места займут абитуриенты с БВИ, Вышка традиционно добавляет 25% мест за счет собственных средств для поступающих по ЕГЭ.

Преподаватели: Александр Омельченко, Сергей Копелиович, Егор Суворов, Тимофей Брыксин, Алексей Шпильман, Иван Ямщиков и др.

Как поступить: Тут также две траектории поступления:

  1. По ЕГЭ. Нужно сдать математику и информатику на 75 и более баллов, русский язык не менее, чем на 60 баллов. Проходной балл в 2020 году 297 за три экзамена.

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

Количество мест: 60 бюджетных и 40 платных.

Где проходят занятия: Все занятия проходят в новом корпусе университета по адресу ул. Кантемировская, д.3А, в десяти минутах на транспорте от Петроградской. Студенческое общежитие расположено на улице Герасимовской, в получасе езды от корпуса университета.

Полезные ссылки:

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

Подробнее..

MLHCI что исследуют на стыке машинного обучения и человеко-компьютерного взаимодействия

03.07.2020 16:05:03 | Автор: admin
Многие убеждены, что область Human Computer Interaction (HCI или человеко-компьютерное взаимодействие) сводится только к проектированию сайтов или приложений, а основная задача специалиста удовлетворить пользователей, увеличивая на несколько пикселей кнопку лайка. В посте мы хотим показать, что это совсем не так, и рассказать, что происходит в HCI на стыке с исследованиями машинного обучения и искусственного интеллекта. Возможно, это позволит читателям посмотреть на эту область с новой для себя стороны.

Для обзора мы взяли труды конференции CHI: Conference on Human Factors in Computing Systems за 10 лет, и с помощью NLP и анализа сетей социтирования посмотрели на темы и области на пересечении дисциплин.




В России особенно силен фокус на прикладных задачах проектирования UX. Многие события, которые помогали росту HCI за рубежом, у нас не произошли: не появилось iSchools, ушли из науки многие специалисты, занимавшиеся близкими аспектами инженерной психологии, и т. д. В результате профессия возникала заново, отталкиваясь от прикладных задач и исследований. Один из результатов этого виден даже сейчас это крайне низкая представленность российских работ по HCI на ключевых конференциях.

Но и за пределами России HCI развивался очень по-разному, фокусируясь на множестве тем и направлений. На магистерской программе Информационные системы и взаимодействие человек-компьютер в Питерской Вышке мы, в том числе, обсуждаем со студентами, коллегами, выпускниками схожих специальностей европейских университетов, партнерами, которые помогают развивать программу, что же относится к области человеко-компьютерного взаимодействия. И эти обсуждения показывают разнородность направления, в котором у каждого специалиста своя, неполная, картина области.

Время от времени мы слышим вопросы, как это направление связано (и связано ли вообще) с машинным обучением и анализом данных. Чтобы ответить на них, мы обратились к исследованиям последних лет, представленным на конференции CHI.

В первую очередь мы расскажем, что происходит в таких областях, как xAI и iML (eXplainable Artificial Intelligence и Interpretable Machine Learning) со стороны интерфейсов и пользователей, а также как в HCI изучают когнитивные аспекты работы специалистов data science, и приведем примеры интересных работ последних лет в каждой области.

xAI и iML


Методы машинного обучения интенсивно развиваются и что важнее с точки зрения обсуждаемой области активно внедряются в автоматизированное принятие решений. Поэтому исследователи все чаще обсуждают вопросы: как пользователи, не являющиеся специалистами в машинном обучении, взаимодействуют с системами, где подобные алгоритмы применяются? Один из важных вопросов такого взаимодействия: как сделать, чтобы пользователи доверяли решениям, принятым на основе моделей? Поэтому с каждым годом все более горячей становится тематика интерпретируемого машинного обучения (Interpretable Machine Learning iML) и объяснимого искусственного интеллекта (eXplainable Artificial Intelligence XAI).

При этом, если на таких конференциях, как NeurIPS, ICML, IJCAI, KDD, обсуждают сами алгоритмы и средства iML и XAI, на CHI в фокусе оказываются несколько тем, связанных с особенностями дизайна и опытом использования этих систем. Например, на CHI-2020 этой тематике были посвящены сразу несколько секций, включая AI/ML & seeing through the black box и Coping with AI: not agAIn!. Но и до появления отдельных секций таких работ было достаточно много. Мы выделили в них четыре направления.

Дизайн интерпретирующих систем для решения прикладных задач


Первое направление это дизайн систем на основе алгоритмов интерпретируемости в различных прикладных задачах: медицинских, социальных и т. д. Такие работы возникают в очень разных сферах. Например, работа на CHI-2020 CheXplain: Enabling Physicians to Explore and Understand Data-Driven, AI-Enabled Medical Imaging Analysis описывает систему, которая помогает врачам исследовать и объяснять результаты рентгенографии органов грудной клетки. Она предлагает дополнительные текстовые и визуальные пояснения, а также снимки с таким же и противоположным результатом (поддерживающие и противоречащие примеры). Если система предсказывает, что на рентгенографии видно заболевание, то покажет два примера. Первый, поддерживающий, пример это снимок легких другого пациента, у которого подтверждено это же заболевание. Второй, противоречащий, пример это снимок, на котором заболевания нет, то есть снимок легких здорового человека. Основная идея сократить очевидные ошибки и уменьшить число обращений к сторонним специалистам в простых случаях, чтобы ставить диагноз быстрее.


CheXpert: автоматизированное выделение областей + примеры (unlikely vs definitely)



Разработка систем для исследования моделей машинного обучения


Второе направление разработка систем, которые помогают интерактивно сравнивать или объединять несколько методов и алгоритмов. Например, в работе Silva: Interactively Assessing Machine Learning Fairness Using Causality на CHI-2020 была представлена система, которая строит на данных пользователя несколько моделей машинного обучения и предоставляет возможность их последующего анализа. Анализ включает построение причинно-следственного графа между переменными и вычисление ряда метрик, оценивающих не только точность, но и честность (fairness) модели (Statistical Parity Difference, Equal Opportunity Difference, Average Odds Difference, Disparate Impact, Theil Index), что помогает находить перекосы в предсказаниях.


Silva: граф связей между переменными + графики для сравнения метрик честности + цветовое выделение влиятельных переменных в каждой группе

Общие вопросы интерпретируемости моделей


Третье направление обсуждение подходов к задаче интерпретируемости моделей в целом. Чаще всего это обзоры, критика подходов и открытые вопросы: например, что понимать под интерпретируемостью. Здесь хотелось бы отметить обзор на CHI-2018 Trends and Trajectories for Explainable, Accountable and Intelligible Systems: An HCI Research Agenda, в котором авторы рассмотрели 289 основных работ, посвященных объяснениям в искусственном интеллекте, и 12 412 публикаций, цитирующих их. С помощью сетевого анализа и тематического моделирования они выделили четыре ключевых направления исследований 1) Intelligent and Ambient (I&A) Systems, 2) Explainable AI: Fair, Accountable, and Transparent (FAT) algorithms and Interpretable Machine Learning (iML), 3) Theories of Explanations: Causality & Cognitive Psychology, 4) Interactivity and Learnability. Кроме того, авторы описали основные тренды исследований: интерактивное обучение и взаимодействие с системой.

Пользовательские исследования


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

Инструментов и алгоритмов интерпретации появилось очень много, поэтому возникает вопрос: как понять, какой же алгоритм выбрать? В работе Questioning the AI: Informing Design Practices for Explainable AI User Experiences как раз обсуждаются вопросы мотивации использования объясняющих алгоритмов и выделяются проблемы, которые при всем многообразии методов еще не решены в достаточной степени. Авторы приходят к неожиданному выводу: большинство существующих методов построены так, что отвечают на вопрос почему (почему у меня такой результат), в то время как пользователям для принятия решений нужен еще и ответ на вопрос почему нет (почему не другой), а иногда что сделать, чтобы результат изменился.

В работе говорится также о том, что пользователям нужно понимать, каковы границы применимости методов, какие у них есть ограничения и это нужно явно внедрять в предлагаемые инструменты. Более ярко эта проблема показана в статье Interpreting Interpretability: Understanding Data Scientists' Use of Interpretability Tools for Machine Learning. Авторы провели небольшой эксперимент со специалистами в области машинного обучения: показали им результаты работы нескольких популярных инструментов для интерпретации моделей машинного обучения и предложили ответить на вопросы, связанные с принятием решения на основе этих результатов. Оказалось, что даже специалисты слишком доверяют подобным моделям и не относятся к результатам критически. Как любой инструмент, объясняющие модели можно использовать неправильно. При разработке инструментария важно учитывать это, привлекая накопленные знания (или специалистов) в области человеко-компьютерного взаимодействия, чтобы учитывать особенности и потребности потенциальных пользователей.

Data Science, Notebooks, Visualization


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

Поэтому предметом этой области HCI становится разработка новых способов визуализации неопределенности в предсказаниях моделей, создание систем для сравнения анализа, проведенного разными способами, а также анализ работы аналитиков с инструментами, например с Jupyter notebooks.

Визуализация неопределенности


Визуализация неопределенности одна из особенностей, которые отличают научную графику от презентационной и бизнес-визуализации. Довольно долго ключевым в последних считался принцип минималистичности и фокуса на основных трендах. Однако это приводит к чрезмерной уверенности пользователей в точечной оценке величины или прогноза, что может быть критичным, особенно, если мы должны сравнивать прогнозы с разной степенью неопределенности. Работа Uncertainty Displays Using Quantile Dotplots or CDFs Improve Transit Decision-Making анализирует, насколько способы визуализации неопределенности в предсказании для точечных графиков и кумулятивных функций распределения помогают пользователям принимать более рациональные решения на примере задачи оценки времени прибытия автобуса по данным мобильного приложения. Что особенно приятно, один из авторов поддерживает пакет ggdist для R с различными вариантами визуализации неопределенности.


Примеры визуализации неопределенности (https://mjskay.github.io/ggdist/)

Однако часто встречаются и задачи визуализации возможных альтернатив, например, для последовательностей действий пользователя в веб-аналитике или аналитике приложений. Работа Visualizing Uncertainty and Alternatives in Event Sequence Predictions анализирует, насколько графическое представление альтернатив на основе модели Time-Aware Recurrent Neural Network (TRNN) помогает экспертам принимать решения и доверять им.

Сравнение моделей


Не менее важный, чем визуализация неопределенности, аспект работы аналитиков сравнение того, как часто скрытый выбор исследователем разных подходов к моделированию на всех его этапах может вести к различным результатам анализа. В психологии и социальных науках набирает популярность предварительная регистрация дизайна исследования и четкое разделение эксплораторных и конфирматорных исследований. Однако в задачах, где исследование в большей степени основано на данных, альтернативой могут стать инструменты, позволяющие оценить скрытые риски анализа за счет сравнения моделей. Работа Increasing the Transparency of Research Papers with Explorable Multiverse Analyses предлагает использовать интерактивную визуализацию нескольких подходов к анализу в статьях. По сути, статья превращается в интерактивное приложение, где читатель может оценить, что изменится в результатах и выводах, если будет применен другой подход. Это кажется полезной идеей и для практической аналитики.

Работа с инструментами организации и анализа данных


Последний блок работ связан с исследованием того, как аналитики работают с системами, подобными Jupyter Notebooks, которые стали популярным инструментом организации анализа данных. Статья Exploration and Explanation in Computational Notebooks анализирует противоречия между исследовательскими и объясняющими целями, изучая найденные на Github интерактивные документы, а в Managing Messes in Computational Notebooks авторы анализируют, как эволюционируют заметки, части кода и визуализации в итеративном процессе работы аналитиков, и предлагают возможные дополнения в инструменты, чтобы поддерживать этот процесс. Наконец, уже на CHI 2020 основные проблемы аналитиков на всех этапах работы, от загрузки данных до передачи модели в продакшн, а также идеи по улучшению инструментов обобщены в статье Whats Wrong with Computational Notebooks? Pain Points, Needs, and Design Opportunities.


Преобразование структуры отчетов на основе логов выполнения (https://microsoft.github.io/gather/)

Подводя итог


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

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

Где учиться программированию в Петербурге программы при поддержке JetBrains

22.06.2020 16:10:43 | Автор: admin
Мы заинтересованы в том, чтобы повышать образовательный уровень в IT-сфере, и готовы строить высшее образование вместе с вузом.

В этом посте мы расскажем об образовательных проектах в Петербурге, которые поддерживает JetBrains: о бакалаврских и магистерских программах в НИУ ВШЭ, ИТМО, СПбГУ и о Computer Science Center.



Бакалаврские программы:
Прикладная математика и информатика в НИУ ВШЭ Санкт-Петербург
Современное программирование в СПбГУ

Магистратура:
Разработка программного обеспечения / Software Engineering на базе Университета ИТМО
Машинное обучение и анализ данных в НИУ ВШЭ Санкт-Петербург
Программирование и анализ данных в НИУ ВШЭ Санкт-Петербург

Дополнительное образование:
Computer Science Center

В чем особенность наших программ?


Участие IT-компаний в обучении


Учебные программы разрабатываются при участии IT-компаний, чтобы давать действительно полезные знания. Курсы читают действующие программисты и учёные. Наши преподаватели: Виталий Брагилевский, Дмитрий Ицыксон, Александр Куликов, Евгений Линский, Денис Москвин, Александр Храбров, Алексей Шпильман.

Индивидуальный подход


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

Практические занятия проходят в небольших группах.

Обратная связь


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

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

Проектная деятельность


Студенты всех программ работают над семестровыми научно-исследовательскими проектами под руководством преподавателей или сотрудников компаний-партнёров. Так они получают опыт разработки в условиях, максимально приближенных к реальным. Задачи, которые они решают в рамках проектной работы, имеют научную или практическую ценность: например, магистранты Машинного обучения и анализа данных работали над плагином для улучшения поддержки естественного языка в IntelliJ IDEA. Смотрите примеры проектов студентов Computer Science Center или студентов Питерской Вышки: здесь, здесь и здесь.

Бакалавриат


Прикладная математика и информатика в НИУ ВШЭ Санкт-Петербург


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

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


Подробнее
Программа состоит из двух больших частей. На первом и втором годах обучения студенты проходят общеобразовательные дисциплины. Сразу начинаются математика, курс алгоритмов и программирование (на первом курсе годовой курс С++, затем годовой курс Java, а также Unix, Python, функциональное программирование и Haskell, операционные системы и так далее). С третьего года обучения у каждого студента появляется индивидуальная образовательная программа. Можно выбирать спецкурсы из нескольких базовых треков: машинное обучение и анализ данных, software engineering, языки программирования, теоретическая информатика, биоинформатика, низкоуровневое программирование.

Проектная деятельность начинается уже на первом курсе (на Хабре можно почитать статью первокурсников об игровом движке, который они написали на С++, другие примеры проектов есть в нашем Instagram). С третьего курса студенты решают практические задачи от компаний JetBrains, Яндекс, Ростелеком и др. Мы рассказали о некоторых проектах в нашем блоге на Хабре: Как учиться с помощью машинного обучения у экспертов в Dota 2, Как я научила робота бегать по видео с YouTube, Mountain Car: решаем классическую задачу при помощи обучения с подкреплением

Стипендии. Все студенты, которые сдают экзамены без троек, получают спонсорскую стипендию от JetBrains. Она составляет 9-15 тыс. рублей в месяц и зависит от среднего балла. Отличники, а также победители и призеры Всероссийской олимпиады школьников могут претендовать на дополнительные стипендии, и в сумме получать 20-25 тыс рублей в месяц.

Место. Все занятия проходят в отдельном корпусе (отремонтирован в 2019 году) по адресу ул. Кантемировская, д.3А.

42 бюджетных места, 40 платных мест

Полезные ссылки:
Чат программы в Telegram
Блог Питерской Вышки на Хабре
Отзывы студентов

Бакалавриат Современное программирование на факультете математики и компьютерных наук СПбГУ


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

На первых курсах студенты изучают необходимые базовые предметы, а на третьем и четвертом составляют себе индивидуальную траекторию обучения, выбирая из ста с лишним математических спецкурсов. Курсы читают ученые из России и из-за рубежа и разработчики IT-компаний. Во время учебы можно посещать открытые научные семинары лаборатории имени П.Л. Чебышева под руководством С.К. Смирнова, лауреата премии Филдса.

Бакалавриат лидер по количеству призёров Всероссийской олимпиады школьников в 2015-2019 г. в России. Учиться сложно и интересно: рассказ студентки об обучении на первом курсе программы.

Подробнее
Что в программе. Алгебра, дискретная математика, математический анализ. Алгоритмы и структуры данных, C++, парадигмы и языки программирования, функциональное программирование, Java, принципы организации и архитектура компьютерных систем и другие курсы по математике и программированию. Смотрите подробный учебный план и список спецкурсов, доступных для выбора на третьем и четвертом годах обучения.

Помимо учёбы можно заниматься спортивным программированием под руководством тренера сборной СПбГУ.

Программа готовит IT-специалистов: бэкенд- и веб-разработчиков, аналитиков и не только.

Преподаватели: Александр Куликов, Виталий Брагилевский, Денис Москвин, Фёдор Бахарев, Дмитрий Ицыксон, Евгений Линский и другие.

Практические проекты. С первого курса ребята работают над проектами под руководством специалистов IT-компаний. Например, в этом году они сделали веб-приложение Big sister, которое отслеживает активность студентов в течение семестра. Другие проекты: ассистент поэта сервис генерации стихотворений на русском языке; игра в жанре 2D-платформер; тренажёр для публичных выступлений; графическая программа под Android.

Стипендии. Студенты, поступившие без вступительных испытаний, получают спонсорские стипендии JetBrains от 10 до 15 тысяч рублей. В дальнейшем спонсорская стипендия платится по результатам успеваемости. Студенты также получают дополнительные стипендии от государства (например, стипендию КНВШ).

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

30 бюджетных мест, 8 платных мест

Полезные ссылки:
Статья о программе на РБК
Блог первокурсника СП
Чат с руководителями программы для поступающих в 2020 году

Магистратура


На Разработку программного обеспечения в ИТМО и на Машинное обучение и анализ данных в Питерскую Вышку могут попасть студенты с базовыми знаниями математики и программирования. При этом первая магистратура специализируется на разработке программного обеспечения и смежных областях, в том числе на теории языков программирования, а вторая на машинном обучении и анализе данных. Подробнее о сходствах и различиях между программами.

На Программировании и анализе данных в Питерской Вышке ждут выпускников бакалаврских программ с углубленным изучением программирования и математики. Здесь учится большинство выпускников Прикладной математики и информатики НИУ ВШЭ Санкт-Петербург.

Разработка программного обеспечения / Software Engineering на базе Университета ИТМО



В магистерской программе Разработка программного обеспечения / Software Engineering много очных занятий и самостоятельной работы над практическими задачами и проектами.

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

Отдельное внимание уделяется работе в команде. В первом и во втором семестре студенты в течение недели участвуют в хакатоне DevDays. Ребята сами придумывают проекты, объединяются в команды, распределяют роли и в конце недели презентуют результаты. Рассказы о проектах от первых лиц читайте здесь и здесь.

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

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

  • промышленная разработка ПО,
  • машинное обучение,
  • теория языков программирования,
  • анализ данных в биоинформатике.

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

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

Место. Почти все занятия проходят в офисе JetBrains у Кантемировского моста (Кантемировская ул., д. 2). В распоряжении студентов есть кухня, где можно отдохнуть между занятиями, выпить чай или кофе и разогреть еду, а также студенческие комнаты для работы над домашними заданиями и проектами.

Стипендии. Студентам магистратуры в зависимости от успехов в учёбе выплачивается дополнительная спонсорская стипендия от 10 000 до 15 000 рублей. Организаторы помогают с поездками на соревнования, конференции и другие образовательные мероприятия.

30 бюджетных мест, 5 платных мест

Полезные ссылки:
Чат программы в Telegram
Интервью со студентами

Машинное обучение и анализ данных в НИУ ВШЭ Санкт-Петербург


Программа для выпускников бакалавриата, обучавшихся как по профильным (программирование, физмат), так и по непрофильным (экономика, социология и др.) специальностям, и желающих освоить с нуля или углубить знания в области машинного обучения и анализа данных. Упор сделан на индивидуальную практическую работу и участие в промышленных и научно-исследовательских проектах. Результаты этой работы студенты представляют на специальных семинарах, в которых принимают участие представители IT-компаний и сотрудники научно-исследовательских лабораторий НИУ ВШЭ.

Подробнее
Программа. На первом году обучения во время осеннего модуля магистранты проходят базовые курсы по алгебре, теории вероятности и математической статистике. Затем базовые курсы по машинному обучению: Основы алгоритмов, Методы оптимизации и др. На втором году начинаются спецкурсы, и каждый студент выбирает те дисциплины, которые ему интересны. Например, магистранты учатся работать с алгоритмами и программным обеспечением для обучения беспилотных автомобилей, изучают Анализ данных на Python в примерах и задачах, проходят курс по нейробайесовским методам, чтобы создавать генеративные модели. В результате за 2 года магистранты постепенно осваивают область машинного обучения и анализа данных от азов до последних достижений науки.

Выпускники программы работают программистами-исследователями в российских и зарубежных компаниях или продолжают обучение в аспирантурах университетов мира.

Проекты. JetBrains тесно сотрудничает с программой Машинное обучение и анализ данных. Компания предлагает научно-исследовательские проекты для студентов, приглашает на стажировки, а часть ее сотрудников преподаёт дисциплины магистратуры. Ещё работать над проектами можно в Центре анализа данных и машинного обучения НИУ ВШЭ Санкт-Петербург. Им заведует Алексей Александрович Шпильман преподаватель Питерской Вышки и руководитель лабораторий Прикладное машинное обучение и глубинное обучение и Агентные системы и обучение с подкреплением в JetBrains Research. Студенты проходят летние стажировки и выполняют проекты в этих лабораториях или в других партнёрских компаниях программы.

Стипендии. Спонсорскую стипендию JetBrains от 10 000 до 15 000 рублей в месяц получают те, кто учится без троек. Размер стипендии зависит от успеваемости.

Место. Занятия проходят в отдельном корпусе (отремонтирован в 2019 году) по адресу ул. Кантемировская, д.3А

10 бюджетных мест, 10 мест за счет средств НИУ ВШЭ, 5 платных мест

Полезные ссылки:
Чат в Telegram
Статья о программе
Запись вебинара о программе

Программирование и анализ данных


На этой программе ждут выпускников бакалавриата с углублённым изучением программирования и математики. Это научная магистратура, куда приходят люди с серьёзной подготовкой в области программирования, а также в области машинного обучения и анализа данных. Упор сделан на продвинутые спецкурсы (их не так много: 5-6 занятий в неделю) и научно-исследовательскую работу, которая начинается с первого семестра.

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


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

Учёбу в этой магистратуре можно совмещать с работой при условии, что задачи, которые студент решает на работе, имеют научную или практическую ценность. Партнёры программы компании JetBrains, Яндекс, Ростелеком, Газпромнефть и другие предлагают такие проекты.

Стипендии. Именные стипендии размером до 15 000 рублей выплачивают компании-партнёры.

Место. Занятия проходят в отдельном корпусе (отремонтирован в 2019 году) по адресу ул. Кантемировская, д.3А

15 бюджетных мест, 5 мест за счет средств НИУ ВШЭ, 5 платных мест

Полезные ссылки:
Чат в Telegram
Рассказ студентки о программе
Запись вебинара о программе

Дополнительное образование в CS центре


Computer Science Center это совместная инициатива Computer Science клуба, компании JetBrains и Школы анализа данных Яндекса.

Программа. Центр предлагает двух- или трёхлетние очные вечерние курсы в Санкт-Петербурге и Новосибирске, чтобы талантливые студенты и выпускники вузов развивались в направлениях Computer Science, Data Science или Software Engineering. Программа состоит из базовых курсов по каждому направлению, курсов по выбору и практики или научно-исследовательской работы. Примеры практических проектов наших студентов.

Преподаватели. Учёные, сотрудники JetBrains, Яндекса, выпускники центра. Чтобы познакомиться с программой и преподавателями, смотрите курсы, опубликованные на YouTube.

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

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

Полезные ссылки:
Видео об атмосфере в CS центре
Онлайн-курсы центра на Stepik
Записи открытых лекций центра
Канал для поступающих в 2020 году: там много ответов на вопросы

Набор на бакалаврские и магистерские программы уже начался. Приходите учиться!
Подробнее..

Анализатор C на первом курсе миф, иллюзия или выдумка?

06.11.2020 12:09:31 | Автор: admin
Для программистов настали тяжёлые времена. Хотя Утечка Памяти была уничтожена valgrind-ом, оставшиеся силы UB преследовали программистов по всей галактике.

Избегая встречи с грозными знаковыми переполнениями, группа борцов за свободу, ведомая Кириллом Бриллиантовым, Глебом Соловьевым и Денисом Лочмелисом, обустроила новый секретный репозиторий.

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


Мы трое студентов бакалавриата Прикладная математика и информатика в Питерской Вышке. В качестве учебного проекта во втором полугодии мы решили написать UB-tester анализатор кода на С++.




Вступление


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

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

Небольшое введение в контекст
Анализаторы кода делятся на две группы: статические и динамические. Статические анализируют код без реального выполнения программы. Динамические, напротив, пытаются извлечь информацию во время ее исполнения. Самые известные примеры статический clang static analyzer с большим функционалом, его платный аналог PVS studio, а также динамические valgrind и sanitizer.

Нам предстояло выбрать основной метод обнаружения ошибок. Источником вдохновения послужил достопочтенный С-шный макрос assert. Если программист регулярно проверяет инварианты с помощью assert-а, то поиск ошибки при отладке становится намного более локализованной и простой задачей. Но вряд ли кто-то в здравом уме использовал бы такую проверку постоянно, обращаясь к массиву или складывая два int-а. Мы решили создать инструмент, который будет анализировать пользовательский код, а затем заменять ошибкоопасные места на написанные нами обертки, в случае чего выбрасывающие пользователю подробный лог ошибки. К примеру:


Пример: программа, складывающая два числа типа int, может вызывать UB при переполнении знакового числа, а ее обработанная версия нет.

Безусловно, производить такие замены в исходном коде пользователя далеко не вежливо, поэтому результатом работы нашей программы является новая версия оригинального кода со вставленными обертками.

Такой подход к обнаружению ошибок оказался удачным или, по крайней мере, интересным. Пользователь получил возможность автоматически тестировать свою программу на предмет простых UB без лишних усилий и затрат времени.

Финальной версии не было суждено стать новым valgrind-ом, а функционалу покорить сердца миллионов, но процесс разработки оказался весьма захватывающим. Про это мы и расскажем далее.

Сlang и AST


Первым шагом работы ub-tester является нахождение всех ошибкоопасных мест в программе. Парсить код на C++ вручную и с нуля путь в могилу (или по крайней мере в отдельный проект), поэтому нам предстояло подобрать инструменты для решения этой задачи. Пожалуй, самым известным и наиболее практичным инструментом по разбору исходного кода на плюсах является clang, поэтому мы выбрали его в качестве основы для нашего проекта. Сlang большая библиотека, поэтому остановимся только на важных для понимания статьи понятиях.

Сперва стоит сказать об AST (Abstract Syntax Tree). Это структура данных дерево (как можно было догадаться из названия), внутренние вершины которого соответствуют операторам языка, а листья операндам. Вот пример AST для простой программы.

Исходный код:
if (a > b) {print(a);} else { print(b);}

AST:


Описанная абстракция и используется в clang-е для представления исходного кода. Такой структуры данных достаточно для обнаружения ошибкоопасных мест. К примеру, чтобы найти в программе теоретически возможные index out of bounds, нужно изучить все вершины AST, соответствующие операторам обращения к массиву по индексу.

Теперь дело остается за малым: получить доступ к AST. В clang-е существует несколько механизмов для решения этой задачи. Мы пользовались Visitor-ами.

В clang-е реализован базовый класс RecursiveASTVisitor, осуществляющий дфсный обход AST. Каждый Visitor должен от него наследоваться, чтобы уметь путешествовать по дереву. Далее, чтобы выполнять специфичные для определенных вершин операции, класс-наследник должен иметь набор методов вида Visit***, где *** название узла AST. Оказываясь в вершине дерева, Visitor вызывает соответствующий ее названию метод Visit***, затем рекурсивно спускается в ее детей. Таким образом, чтобы создать своего Visitor-а, достаточно реализовать методы обработки конкретных вершин.

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

class FindBinaryOperatorVisitor : public clang::RecursiveASTVisitor<FindBinaryOperatorVisitor> { public:bool VisitBinaryOperator(clang::BinaryOperator* BinOp) { std::cout << BinOp->getBeginLoc() << \n;return true;}};

Теперь можно со спокойной душой переходить к следующему пункту: к замене участков исходного кода.

CodeInjector


Сразу скажем, что, вероятно, мы избрали далеко не лучшее решение этой задачи. Мы разработали класс CodeInjector, который
  • лениво применяет предоставленные ему замены исходного кода: сохраняет все пришедшие ему запросы, а затем разом их выполняет в конце обработки файла;
  • никак не связан с clang-ом: сам открывает файл на чтение, сам ищет нужные строки и так далее.

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

Простой пример. Есть такое выражение:
arr[1] + arr[2];

Пусть мы сначала захотим поменять сложение на ASSERT_SUM, получим следующее:
ASSERT_SUM(arr[1], arr[2]);

Кроме того, мы хотим проверить, что не произойдет выход за границы массива. Снова обратимся к этому же участку кода:
ASSERT_SUM(ASSERT_IOB(arr, 1), ASSERT_IOB(arr, 2));

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

Мы заметили, что схемы замен состоят из чередования кусков, которые мы оставляем, и кусков, которые мы заменяем. Проиллюстрируем на примере: выражение: arr[1+2]. В нем есть два ошибкоопасных места: обращение к массиву и операция сложения. Должны произойти следующие замены:
  • arr[1+2] заменяется на ASSERT_IOB(arr, 1 + 2)
  • ASSERT_IOB(arr, 1 + 2) заменяется на ASSERT_IOB(arr, ASSERT_SUM(1, 2))
    arr[1 + 2] ~~~~~> ASSERT_IOB(arr, 1 + 2) ~~~~~~> ASSERT_IOB(arr, ASSERT_SUM(1, 2)




Далее мы, внутри команды, договорились об интерфейсе для взаимодейстия с CodeInjector-ом, основанном на этой идее.

Все готово! Можно приступать к самому интересному работе с конкретными видами UB.

Функционал


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

Основные ошибки, выявляемые нашей программой:
  • выход за границы С-шного массива;
  • UB в целочисленной арифметике;
  • обращение к неинициализированной переменной.

Подробно про некоторые аспекты функционала мы расскажем далее.

Целочисленная арифметика


Известнейшие представители UB арифметике целочисленные переполнения в самых разных операциях. Есть и более изощренные UB, которыми могут похвастаться, например, остаток от деления и особенно битовые сдвиги. Кроме того, часто можно встретить составные операторы присваивания (+= и другие) и операторы инкремента/декремента. Во время их использования происходит целая цепочка неявных преобразований типов, которая и может повлечь крайне неожиданный и нежеланный результат. Да и неявные касты сами по себе могут служить большой бедой.

Так или иначе, общее правило для всех UB в арифметике их сложно найти, легко проглядеть (никаких segfault-ов!) и невозможно простить.

Важно: впредь и далее речь пойдет про стандарт С++17, на который и ориентирован ub-tester. Он также поддерживает C++20, но из-за того, что в нем исчезли некоторые виды UB в арифметике (а новых не добавилось), про него говорить не так интересно.

int a = INT_MIN, b = -1, z = 0;int test1 = a + b; // overflowint test2 = a * b; // overflowint test3 = a << 5; // lhs is negative => UBint test5 = 5 % z; // % by 0 => UBint test6 = --a; // overflow

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

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

template <typename T>ArithmCheckRes checkSum(T Lhs, T Rhs) {  FLT_POINT_NOT_SUPPORTED(T);  if (Rhs > 0 && Lhs > std::numeric_limits<T>::max() - Rhs)    return ArithmCheckRes::OVERFLOW_MAX;  if (Rhs < 0 && Lhs < std::numeric_limits<T>::lowest() - Rhs)    return ArithmCheckRes::OVERFLOW_MIN;  return ArithmCheckRes::SAFE_OPERATION;}

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

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

Например
Например, неопределенное поведение во время взятия остатка INT_MIN % (-1), вызванное тем, что результат не помещается в int. Если же вы, как и я, всегда немного осторожничали с битовыми сдвигами то не зря. Битовый сдвиг влево может похвастаться рекордом по количеству различных UB, которые может вызывать. К примеру, сдвиг на отрицательное число бит это неопределенное поведение. Сдвиг на большее число бит, чем есть в типе тоже. А если попробовать битово сдвинуть влево отрицательное число, то до C++20, безусловно, снова UB. Но если вам повезло, и ваше число в знаковом типе неотрицательно, то корректность результата будет зависеть от возможности представить его в беззнаковой версии, что тоже можно не удержать в голове. В общем, хоть эти правила и понятные, но, в случае неаккуратного с ними обращения, последствия могут оказаться весьма плачевными.

int a = INT_MIN, b = -1;int test = a % b; // -INT_MIN > INT_MAX => UBint test1 = a << 5; // lhs is negative => UBint test2 = 5 << b; // rhs is negative => UBint32_t c = 1, d = 33;int32_t test3 = c << d; // rhs is >= size of c in bits => UBint test4 = 2e9 << c; // test = -294967296, not UBint test5 = 2e9 << (c + 1); // (2e9 << 2) > UINT_MAX => UB


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

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

Вы с другом пошли в лес и решили прибавить к чару единицу Красиво прибавить, то есть ++c. Будет ли вас ожидать в следующем примере UB?

char c = 127;++c;

И тут понеслось. Во-первых, безобидный префиксный инкремент решил вычисляться наподобие своему старшему собрату, то есть как составное присваивание c += 1. Для этого он привел c и 1 к общему типу, в данном случае к int-у. Затем честно посчитал сумму. И перед записью результата обратно в c, не забыл вызвать неявное преобразование к char-у. Уф.

И UB не случилось. Действительно, само сложение произошло в большом типе int, где число 128 законно существует. Но при этом результат все равно получился с изюминкой, благодаря неявному приведению результата к char-у. Более того, такое приведение чисто теоретически могло закончится не -128, а чем-то особенным в зависимости от компилятора документация это допускает, ведь тип знаковый.

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

В случае с операторами составного присваивания AST не жалеет информации, поэтому проследить цепочку преобразований типов несложно. Далее несложно и проверить корректность вычисления в одном типе, затем неявное приведение к исходному (обе такие проверки уже есть в арсенале). Однако по поводу инкремента/декремента AST отказалось сотрудничать, скрыв всю кухню преобразований. Решением было внимательно прочитать документацию С++, а затем начать цепочку приведений с std::common_type от типа аргумента и int-a (типа единицы). Искушенный clang-ом читатель может поймать нас за руку, заметив, что именно по поводу таинственных ++ и AST, вообще говоря, знает, возможно переполнение или нет.

Однако мы здесь собрались не просто так

Читатель ловит нас за руку, в то время как AST делает нашу работу

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


Вывод ub-tester-а на примере с char c = 127; ++c;

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

Неинициализированные переменные


Каждому, кто знаком с C++, известно (но зачастую это анти-интуитивно для новичков, пришедших из других языков): если объявить переменную базового типа, но не проинициализировать её никаким значением, а потом в неё посмотреть возникает UB. В то же время, такой синтаксис бывает удобен и иногда даже необходим, к примеру, для использования `cin` или `scanf`, поэтому мы решили побороться с этим типом ошибок.

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

template <typename T>class UBSafeType final {public:  UBSafeType() : Value_{}, IsInit_{false} {}  UBSafeType(T t) : Value_{t}, IsInit_{true} {}  T assertGetValue_() const;  T& assertGetRef();  T& setValue_(T Val);  private:  T Value_;  bool IsInit_;};

А затем возникают вопросы. Как мы понимаем, когда происходит именно чтение значения переменной, а когда она просто упоминается каким-либо другим образом? Суть в том, что согласно стандарту, UB возникает именно в момент lvalue to rvalue cast, а его Clang AST выделяет в отдельную вершину `ImplicitCastExpr` нужного типа. Хорошо, тогда более сложный вопрос: пусть есть `scanf`, читающий несколько переменных, но пользователь дал некорректный ввод и прочиталась только одна переменная. Тогда как понять, что происходит внутри наших оберток?

После некоторых размышлений волевым усилием отвечаем: никак. Если нет доступа к исходному коду функции, которая принимает переменную по ссылке или указателю, и при этом на момент вызова этой функции переменная не была проинициализирована, мы можем только сказать пользователю: Эй, у тебя тут потенциально опасная ситуация, но мы за это не отвечаем, а затем про эту переменную забыть.

Чтобы понять, доступны ли нам исходники этой функции, мы заранее пройдемся по AST всех переданных файлов и поищем в них определения вызываемых функций. Если исходники есть они будут обработаны нашим анализатором, поэтому такой функции можно смело передавать обертку целиком и, таким образом, сохранить необходимую информацию.


Пример: обработанная версия программы, читающая IP-адрес по шаблону при помощи scanf, не может обнаружить UB, возникающее при выводе результата на экран

Перейдем к тому, как мы использовали AST. По вершинам `VarDecl` мы находим объявления переменных и заменяем их на конструкторы оберток, по операторам присваивания находим собственно присваивания, которые и являются инициализациями. Интереснее с доступом к значению: информацию о переменной содержат вершины `DeclRefExpr`, но мы-то ищем `ImplicitCastExpr`, находящийся выше в дереве. При этом принципиально важно обработать случаи доступа по значению (с кастом) и по ссылке (без него) по-разному. На помощь приходит технология Parent-ов, позволяющая подниматься по дереву независимо от обхода Visitor-ов. (Передаю привет неполной документации ParentMapContext, из-за которой пришлось долго гулять по исходникам clang-а). Увы, это палка о двух концах из-за потенциального обхода целого дерева асимптотика нашего анализатора возрастает до квадратной, и время работы самого анализатора ухудшается значительно. А что же делать, если обращение к переменной по ссылке? Возможно, эта ссылка куда-то передается, возможно, сохраняется в новую переменную И что делать с полями классов? А вложенных классов?

int main() {  int a = 5;  int& b{a};  int c = b++ + (int&)a;  (b = c) = (b);}


Пример: страшный сон исследователей неинициализированных переменных и его AST

Не будем утомлять читателя миллионом вопросов, которые мы сами себе задавали и вынуждены были искать ответы. Скажем только, что ключевой сложностью оказалось отсутствие какого бы то ни было источника информации, в котором были бы собраны все пререквизиты и ценные мысли, объясняющие, каким вообще образом стоит реализовывать данную идею. Как следствие, пришлось наступать на все старательно разложенные языком C++ и clang-ом грабли, и по мере осмысления всё большего количества тонкостей и деталей задачи, глобальное представление об этой части проекта сильно видоизменялось и обрастало подробностями и замысловатостями. На продумывание и размышления ушло много больше времени, чем на саму реализацию.

Результаты


Полномасштабное тестирование мы, к сожалению, не успели провести. Тем не менее, мы проверяли, как наша программа работает, на 1) отдельных изощренных ситуациях, 2) примерах простеньких программ на C++ из интернета, 3) своих решениях контестов и домашек. Вот пример преобразования, получающегося в результате работы нашего анализатора:

Пример до:
#include "../../include/UBTester.h"#include <iostream>int main() {  int a, b;  std::cin >> a;    char c = 89;  c = 2 * c; // unsafe conversion    int arr[10];  arr[a] = a; // possible index out of bounds    a = b; // uninit variable}

Пример после:
#include "../../include/UBTester.h"#include <iostream>int main() {  UBSafeType<int> a, b;  std::cin >> ASSERT_GET_REF_IGNORE(a);    UBSafeType<char> c(IMPLICIT_CAST(89, int, char));  ASSERT_SET_VALUE(c, IMPLICIT_CAST(ASSERT_BINOP(Mul, 2, IMPLICIT_CAST(c, char, int), int, int), int, char)); // unsafe conversion    UBSafeCArray<int, 10> arr(ASSERT_INVALID_SIZE(std::vector<int>({10})));  ASSERT_IOB(arr, ASSERT_GET_VALUE(a)) = ASSERT_GET_VALUE(a); // possible index out of bounds    ASSERT_SET_VALUE(a, ASSERT_GET_VALUE(b)); // uninit variable}

Видно, что код достаточно сильно раздувается в объеме. Впрочем, мы считаем, что сохранить читабельность на каком-то уровне нам удалось, а главное, ошибки действительно находятся!


Пример: вот так работает код, приведенный выше, на входных данных 5 и 15

Ради интереса мы также проверили, насколько медленнее работают более-менее реальные программы после обработки нашим анализатором. В качестве примера мы взяли собственную реализацию алгоритма Флойда. Результаты оказались неутешительными:


В заключение скажем: перед нами не стояло цели создать готовый продукт нам было важно столкнуться с LLVM, clang и С++ и разбиться насмерть. Возможно, результат вышел не самым практичным, но чтение документаций и стандарта оказалось занимательным и особенно полезным времяпрепровождением. Будьте осторожны при использовании С++ и да хранит вас Бьёрн Страуструп.

Ссылка на гитхаб
Подробнее..

Positive-Unlabeled learning and where to find it

22.07.2020 14:19:29 | Автор: admin
Привет! В этой статье я начну рассказ про Positive-Unlabeled (PU) learning. Расскажу, что это за область машинного обучения и в каких задачах она применяется. В конце будет немного про наше применение PU learning для поиска коррупции в аукционах государственных закупок.




Кто я


Меня зовут Дмитрий Иванов. Я учусь на 2-м курсе аспирантуры по экономике в Питерской Вышке. Работаю в исследовательской группе Агентные Системы и Обучение с Подкреплением в JetBrains Research, а также в международной лаборатории Теории Игр и Принятия Решений в ВШЭ. Помимо PU learning я интересуюсь обучением с подкреплением и исследованиями на стыке машинного обучения и экономики.

Преамбула



Рис. 1а. Положительные данные

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

Ответ здесь

Рис. 1б. Эллипс отделяет положительные данные от возможных отрицательных


Возможно, вы представили себе что-то подобное рисунку 1б: обвели данные в эллипс. На самом деле, так и работают многие методы детекции аномалий.

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

Ответ здесь

Рис. 1в. Прямые отделяют положительные данные от возможных отрицательных (прямые предсказаны алгоритмом детекции аномалий One-Class SVM)

В случае прямой разделяющей линии нет однозначного ответа. В каком направлении рисовать прямую непонятно.

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


Рис. 1г. Положительные (синие) и неразмеченные (красные) точки. Неразмеченные точки состоят из положительных и отрицательных

Ответ здесь

Рис. 1д. Прямая отделяет положительные точки от отрицательных исходя из неразмеченных данных


Стало легче! Хотя мы заранее не знаем, как сгенерирована каждая конкретная неразмеченная точка, мы можем примерно их разметить, сравнив с положительными. Красные точки, похожие на синие, вероятно, положительные. Наоборот, непохожие наверняка отрицательные. В итоге, несмотря на то что у нас нет чистых отрицательных данных, информацию о них можно получить из неразмеченной смеси и использовать ее для более точной классификации. Это и делают алгоритмы Positive-Unlabeled learning, о которых я хочу поведать.

Введение


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

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

PU learning задача довольно естественная. Данные, которые встречаются в реальном мире, часто являются грязными. Возможность обучаться на грязных данных относительно качественно кажется полезным лайфхаком. Несмотря на это, я встречал парадоксально мало людей, которые слышали о PU learning, и еще меньше тех, кто знал бы о каких-то конкретных методах. Поэтому я решил рассказать об этой области.


Рис. 2. Jrgen Schmidhuber and Yann LeCun, NeurIPS 2020

Применение PU learning


Я неформально разделю случаи, в которых PU learning может быть полезен, на три категории.

Первая категория, наверное, наиболее очевидная: PU learning можно применять вместо обычной бинарной классификации. В некоторых задачах данные по своей природе немного грязные. В принципе, это загрязнение можно игнорировать и использовать обычный классификатор. Но можно совсем немного изменить лосс-функцию при тренировке классификатора (Kiryo et al., 2017) или даже сами предсказания уже после тренировки (Elkan & Noto, 2008), и классификация станет точнее.

В качестве примера рассмотрим идентификацию новых генов, отвечающих за развитие каких-либо заболеваний (disease genes). Стандартный подход считать уже найденные disease genes положительными данными, а все остальные гены отрицательными. Очевидно, что в этих отрицательных данных могут присутствовать еще не найденные disease genes. Более того, сама задача состоит в поиске таких disease genes среди отрицательных данных. Это внутреннее противоречие замечают здесь: (Yang et al., 2012). Исследователи отошли от стандартного подхода и рассмотрели гены, не относящиеся к уже обнаруженным disease genes, как неразмеченную смесь, а затем применили методы PU learning.

Другой пример обучение с подкреплением на основе демонстраций эксперта. Задача заключается в том, чтобы обучить агента действовать так же, как эксперт. Этого можно добиться при помощи метода generative adversarial imitation learning (GAIL). В GAIL используется GAN-подобная (generative adversarial networks) архитектура: агент генерирует траектории так, чтобы дискриминатор (классификатор) не мог отличить их от демонстраций эксперта. Недавно исследователи из DeepMind заметили, что в GAIL дискриминатор решает задачу PU learning (Xu & Denil, 2019). Обычно экспертные данные дискриминатор считает положительными, а сгенерированные отрицательными. Это приближение достаточно точно в начале обучения, когда генератор не способен производить данные, похожие на положительные. Однако по мере обучения сгенерированные данные все больше походят на экспертные, пока не станут неотличимыми для дискриминатора в конце обучения. По этой причине исследователи (Xu & Denil, 2019) считают сгенерированные данные неразмеченными данными с непостоянной пропорцией смеси. Позднее похожим образом был модифицирован GAN при генерации картинок (Guo et al., 2020).


Рис. 3. PU learning как аналог стандартной PN классификации

Во второй категории PU learning может быть применен для детекции аномалий как аналог одноклассовой классификации (OCC). Мы уже видели в Преамбуле, чем конкретно неразмеченные данные могут помочь. Все методы ОСС без исключений вынуждены делать предположение о распределении отрицательных данных. Например, разумно обвести положительные данные в эллипс (гиперсферу в многомерном случае), вне которого все точки отрицательны. В этом случае мы предполагаем, что негативные данные распределены равномерно (Blanchard et al., 2010). Вместо того чтобы делать такие предположения, методы PU learning могут оценить распределение отрицательных данных на основе неразмеченных. Это особенно важно, если распределения двух классов сильно пересекаются (Scott & Blanchard, 2009). Один из примеров детекции аномалий с применением PU learning обнаружение фейковых обзоров (Ren et al., 2014).


Рис. 4. Пример фейкового обзора

Детекция коррупции в аукционах российских государственных закупок


В третью категорию применения PU learning можно отнести задачи, в которых ни бинарная, ни одноклассовая классификации не могут быть использованы. В качестве примера я расскажу про наш проект по детекции коррупции в аукционах российских государственных закупок (Ivanov & Nesterov, 2019).

По законодательству полные данные по всем аукционам госзакупок размещаются в открытом доступе для всех желающих потратить месяц на их парсинг. Мы собрали данные по более чем миллиону аукционов, проведенных с 2014 по 2018 года. Кто, когда и сколько поставил, кто выиграл, в какой период проходил аукцион, кто проводил, что закупал все это в данных есть. Но, разумеется, нет метки тут коррупция, так что обычный классификатор не построишь. Вместо этого мы применили PU learning. Основное предположение: участники с нечестным преимуществом всегда выигрывают. Используя это предположение, проигравших в аукционах можно рассмотреть как честных (положительных), а победителей как потенциально нечестных (неразмеченных). При такой постановке методы PU learning могут находить подозрительные паттерны в данных на основе тонких различий между победителями и проигравшими. Конечно, на практике возникают сложности: необходимы аккуратный дизайн признаков для классификатора, анализ интерпретируемости его предсказаний, статистическая проверка предположений о данных.

По нашей очень консервативной оценке около 9% аукционов в данных коррумпированы, вследствие чего государство теряет около 120 миллионов рублей в год. Потери могут показаться не очень большими, но исследуемые нами аукционы занимают лишь около 1% рынка госзакупок.



Рис. 5. Доля коррумпированных аукционов госзакупок в разных регионах России (Ivanov & Nesterov, 2019)

Завершающие ремарки


Чтобы не создавалось впечатление, что PU решение всех бед человечества, упомяну подводные камни. В обычной классификации чем больше у нас данных, тем точнее можно построить классификатор. Более того, увеличивая количество данных до бесконечности, мы можем приближаться к идеальному (по формуле Байеса) классификатору. Так вот, основной подвох PU learning в том, что это ill-posed задача, то есть задача, которая не решается однозначно даже при бесконечном количестве данных. Ситуация становится лучше, если известна пропорция двух классов в неразмеченных данных, однако определение этой пропорции тоже ill-posed задача (Jain et al., 2016). Лучшее, что мы можем определить это интервал, в котором находится пропорция. Более того, методы PU learning часто не предлагают способов оценки этой пропорции и считают ее известной. Есть отдельные методы, которые ее оценивают (задача называется Mixture Proportion Estimation), однако часто они медленны и/или нестабильны, особенно когда два класса представлены в смеси сильно неравномерно.

В этом посте я рассказал про интуитивное определение и применения PU learning. Помимо этого, я могу рассказать про формальное определение PU learning с формулами и их пояснениями, а также про классические и современные методы PU learning. Если этот пост вызовет интерес напишу продолжение.

Список литературы


Blanchard, G., Lee, G., & Scott, C. (2010). Semi-supervised novelty detection. Journal of Machine Learning Research, 11(Nov), 29733009.

Elkan, C., & Noto, K. (2008). Learning classifiers from only positive and unlabeled data. Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD 08, 213. https://doi.org/10.1145/1401890.1401920

Guo, T., Xu, C., Huang, J., Wang, Y., Shi, B., Xu, C., & Tao, D. (2020). On Positive-Unlabeled Classification in GAN. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 83858393.

Ivanov, D. I., & Nesterov, A. S. (2019). Identifying Bid Leakage In Procurement Auctions: Machine Learning Approach. ArXiv Preprint ArXiv:1903.00261.

Jain, S., White, M., Trosset, M. W., & Radivojac, P. (2016). Nonparametric semi-supervised learning of class proportions. ArXiv Preprint ArXiv:1601.01944.

Kiryo, R., Niu, G., du Plessis, M. C., & Sugiyama, M. (2017). Positive-unlabeled learning with non-negative risk estimator. Advances in Neural Information Processing Systems, 16751685.

Ren, Y., Ji, D., & Zhang, H. (2014). Positive Unlabeled Learning for Deceptive Reviews Detection. EMNLP, 488498.

Scott, C., & Blanchard, G. (2009). Novelty detection: Unlabeled data definitely help. Artificial Intelligence and Statistics, 464471.

Xu, D., & Denil, M. (2019). Positive-Unlabeled Reward Learning. ArXiv:1911.00459 [Cs, Stat]. http://arxiv.org/abs/1911.00459

Yang, P., Li, X.-L., Mei, J.-P., Kwoh, C.-K., & Ng, S.-K. (2012). Positive-unlabeled learning for disease gene identification. Bioinformatics, 28(20), 26402647.
Подробнее..

Music2Dance как мы пытались научиться танцевать

19.05.2021 08:16:04 | Автор: admin

Всем привет! Меня зовут Владислав Мосин, я учусь на 4-м курсе бакалаврской программы Прикладная математика и информатика в Питерской Вышке. Прошлым летом вместе с Алиной Плешковой, магистранткой нашего факультета, я проходил стажировку в JetBrains Research. Мы работали над проектом Music2Dance, цель которого научиться генерировать танцевальные движения, подходящие под заданную музыку. Это может быть использовано, например, при самостоятельном обучении танцам: услышал музыку, запустил приложение, и оно показало движения, которые гармонично с этой музыкой сочетаются.

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

Из к/ф Криминальное чтивоИз к/ф Криминальное чтиво

Существующие подходы

Идея генерации танца по музыке довольно стара. Наверное, самый яркий пример это танцевальные симуляторы типа Dance Dance Revolution, где игрок должен наступать на светящиеся в такт музыке панели на полу, и таким образом создается некоторое подобие танца. Также красивый результат в этой области это создание танцующих геометрических фигур или 2D-человечков.

Cуществуют и более серьезные работы генерация 3D-движений для людей. Большинство таких подходов основываются исключительно на глубоком обучении. Лучшие результаты на лето 2020 года показывала архитектура DanceNet, и мы решили взять именно её в качестве бейзлайна. Дальше мы обсудим их подход подробнее.

Предобработка данных

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

Музыка: onset, beats, chroma

Наверное, самый распространенный способ извлечение фичей из аудио это подсчет спектрограммы или мелграммы преобразование звука из амплитудного домена в частотный при помощи преобразования Фурье. Однако, в нашей задаче мы работаем с музыкой, а не произвольным аудиосигналом, и низкоуровневый анализ в данном случае не подходит. Нас интересуют ритм и мелодия, поэтому мы будем извлекать onset, beats и chroma (начало ноты, ритм и настроение мелодии).

Видео: извлечение позы человека

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

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

Синим отмечены ключевые точкиСиним отмечены ключевые точки

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

Важной особенностью этого метода является способ хранения положений ключевых точек. Например, если хранить просто абсолютные положения в 3D-пространстве, то возникает проблема нефиксированной длины костей: расстояние между голенью и коленом или плечом и локтем может изменяться от кадра к кадру, что не является ожидаемым поведением. Для избежания таких проблем фиксируется положение одной точки человека, а именно середины таза, а положение всех остальных задается через длину кости и угол поворота относительно предыдущей точки. Поясню на примере: положение кисти задается через длину лучевой кости, а также поворот относительно локтя.

Архитектура DanceNet

Архитектура DanceNet. Источник: https://arxiv.org/abs/2002.03761Архитектура DanceNet. Источник: https://arxiv.org/abs/2002.03761

Архитектура DanceNet cocтоит из нескольких основных частей:

  • Кодирование музыки;

  • Классификация музыки по стилю;

  • Кодирование кадров видео;

  • Предсказание следующего кадра по предыдущим и музыке;

  • Декодирование полученного кадра.

Рассмотрим немного подробнее каждую из частей:

  1. Кодирование музыки. Предобратанный аудиосигнал кодируется при помощи сверточной нейросети с Bi-LSTM слоем.

  2. Классификация музыки по стилю. Аналогично предыдущему пункту, сверточная нейросеть с Bi-LSTM слоем.

  3. Кодирование-декодирование кадра. Маленькая двухслойная сверточная сеть.

  4. Предсказание следующего кадра. Самая содержательная часть архитектуры, которая собственно и предсказывает следующую позу по предыдущим и музыке. Состоит из блоков из dilated (расширенных) сверток со скип-соединениями.

На вход DanceNet принимает музыку и набор поз, а вот выдает не просто позу, а параметризацию нормального распределения математическое ожидание и дисперсию, из которого и сэмплируется ответ, а качестве функции потерь используется минус вероятность правильного положения.

Наше решение

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

Архитектура решения. Эпоха тренировкиАрхитектура решения. Эпоха тренировки

Наше решение состоит из четырех основных частей:

  • Датасет

  • Модель для предсказания следующего положения (DanceNet)

  • Модель для исправления следующего положения положения (RL модель)

  • Функция потерь

Датасет

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

DanceNet

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

RL модель

Задача RL модели исправить положение тела так, чтобы оно выглядело более реалистичным. На вход модель принимает движение (для каждой точки разность между новым и старым положениями) и старое положение тела, на выход выдает исправленное новое положение.

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

Структура алгоритмов обучения с подкреплениемСтруктура алгоритмов обучения с подкреплением

В качестве алгоритмов обучения с подкреплением мы решили выбрать один алгоритм, использующий Q-Learning (наш выбор пал на TD3, как на наиболее стабильный и выразительный) и один не использующий (мы остановились на PPO).

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

Функция потерь

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

L(S, S_{real},R)=-\parallel S-S{real} \parallel_2-R ,

где S положение, Sreal правильное положение, R награда среды.

Модель на фазе тестирования

Архитектура решения. Эпоха тестированияАрхитектура решения. Эпоха тестирования

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

Результаты

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

Наш грустный танец. Спасибо за ваш интерес!


Другие материалы из нашего блога о стажировках:


Подробнее..

Шаблоны и концепты в С20

15.04.2021 14:13:15 | Автор: admin

Привет, Хабр!

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

Важное уточнение: эта лекция не попытка объять необъятное, а краткий экскурс по полезным возможностям C++ для членов олимпиадного сообщества: от извлечения кода в класс до внутренних механизмов работы лямбда-функций и щепотки ограничений (constraints) из C++20. Если интересно, приглашаем к просмотру.

Подробные таймкоды

00:53 Что нужно знать перед просмотром лекции

02:00 Особенности С++

03:10 Хорошие источники знаний и практик в C++

04:45 Классы. Стек с минимумом

06:21 Создание своей структуры

09:03 Запрещаем прямой доступ

09:53 Упрощаем отладку

10:29 Шаблоны классов

11:24 Статический полиморфизм в разных языках

12:03 Оптимизация

12:27 Ошибки компиляции и инстанцирование

13:40 Ограничения (С++20)

15:01 Шаблоны функций

15:27 Автовывод параметров

16:21 Class Template Argument Deduction (CTAD, С++17)

16:56 Ошибки компиляции и инстанцирование

17:47 Обобщенное программирование

19:12 Вложенные типы

20:10 Продвинутые техники

20:33 Функторы

21:00 Функциональные объекты

21:56 Как параметр шаблона

22:30 Функторы с состоянием

23:26 Функторы с состоянием для контейнеров

24:42 Лямбда-выражения

25:38 Расшифровка лямбды

26:28 Сохранение в переменную

27:27 Рекурсия не поддерживается

27:56 Захваты по значению и ссылке

29:18 Захват с инициализатором

30:29 Комбинированные захваты

31:16 Применение функторов

32:15 IIFE

33:18 Вектор лямбд и стирание типов (type erasure)

34:36 Функтор как параметр функции

35:51 Функтор как поле класса

37:45 Более сложные структуры данных (декартово дерево, дерево отрезков)

38:34 За кадром: лямбды-компараторы

39:48 За кадром: более сложные шаблоны

41:23 Студенческие проекты на C++ (в прошлом году рассказывали о проектах наших первокурсниках)

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

Подробнее..

Обучение с подкреплением в Super Mario Bros. Сравнение алгоритмов DQN и Dueling DQN

17.06.2021 10:17:44 | Автор: admin

Этой весной Питерская Вышка и JetBrains впервые провели проектную смену для старшеклассников Школу по практическому программированию и анализу данных. В течение пяти дней 50 участников со всей страны работали над групповыми проектами по машинному обучению, NLP, мобильной и web-разработке.

Первое место заняла команда Deep Q-Mario ребята создали нейронную сеть, которая использует reinforcement learning для обучения агента играть в Super Mario Bros. В этом посте они рассказывают, какие алгоритмы использовали и с какими проблемами столкнулись (например, в какой-то момент Марио просто отказался прыгать).

О нас

Мы Владислав и Дмитрий Артюховы, Артём Брежнев, Арсений Хлытчиев и Егор Юхневич учимся в 10-11 классах в разных школах Краснодара. С программированием каждый из нас знаком довольно давно, мы писали олимпиады на С++. Однако почти все члены команды раньше не работали на Python, а для написания проекта в короткий пятидневный срок он был необходим. Поэтому первым испытанием для нас стало преодоление слабой типизации Python и незнакомого синтаксиса. Но обо всем по порядку.

Немного теории

На школе Питерской Вышки нам предстояло создать нейронную сеть, которая использует reinforcement learning для обучения агента играть в Super Mario Bros.

Reinforcement Learning

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

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

Q-learning

В основу нашей модели лег алгоритм Q-learning. Q-learning это модель, которая обучает некоторую функцию полезности (Q-функцию). Эта функция на основании текущего состояния и конкретного действия агента вычисляет прогнозируемую награду за весь эпизод (Q-value).Агент совершает действия на основании некоторого свода правил политики. Политика нашего агента называется Epsilon-Greedy: с некоторой вероятностью агент совершает случайное действие, иначе он совершает действие, которое соответствует максимальному значению Q-функции.

# implementation of Epsilon-Greedy Policy:def act(state):rand_float = random.random() # returns random float in range: [0, 1)if rand_float <= EPS:action = random_action()else:action = model.get_action(state) # returns action that brings max Q-valuereturn action

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

Обучение происходит так: мы добавляем к рассматриваемому значению Q-функции разность между оптимальным значением и текущим значением данной функции:

Q(s_t,a_t):=Q(s_t,a_t)+(Q_{target}(s_t,a_t)-Q(s_t,a_t))Q_{target}(s_t,a_t)=r_t(s_t,a_t)+ maxQ(s_{t+1},a)

Где Q(s, a) значение Q-функции для состояния и действия;

Qtarget(s, a) это оптимальное, по нашему предположению, значение Q-функции, к которому мы пытаемся свести текущее значение Q-функции;

st, at состояние среды и выбранное действие в момент времени $t$;

rt(st, at) награда за текущее состояние среды и совершенное действие;

коэффициент дисконтирования. Он необходим для того, чтобы уменьшать "значимость" награды в последующих моментах времени;

коэффициент обучения. Он определяет насколько сильно мы изменим текущее значение Q-функции.

Deep Q-Learning

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

Deep Q-learningDeep Q-learning

Experience Replay Buffer

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

# implementation of transition collecting:transition = (state, action, next_state, reward, done)replay_buffer.append(transition)  

Target network

Для того, чтобы весь алгоритм обучения работал, необходимо иметь вторую нейронную сеть target model, которая определяет оптимальное значение Q-функции (Q-target) и является копией модели, взаимодействующей со средой (online model). Единственное отличие этих сетей друг от друга заключается в том, что веса target model обновляются несколько реже, чем у online model у нас это примерно каждый 500-й эпизод. Это нужно для корректного обучения модели: если online model будет производить вычисления Q-target и Q-функций самостоятельно, при изменении весов сети следующие значения Q-target и Q-функций изменятся примерно одинаково, то есть разница между ними останется такой же, и мы не будем сводиться к оптимальному значению.

Существуют два метода обновления весов target model: hard update и soft update. Первый копирует online model в target model каждую n-ую итерацию обучения. Во втором методе веса target model также пересчитываются при обучении, но медленнее, как взвешенное среднее весов двух сетей

Q_{target}:=Q_{target}+(Q_{agent}-Q_{target})

Работа над проектом

Стоит отметить, что до школы никто из нашей команды не делал проекты по машинному обучению. За несколько недель нам сообщили тему проекта, и мы заранее, еще в Краснодаре, начали готовиться. Мы читали статьи, смотрели видео по машинному обучению и нейронным сетям, изучали математику, которая нам может пригодиться. Поэтому можно сказать, что на смену приехали уже подготовленными. Конечно, мы не знали нюансов, но во время школы наш куратор Дмитрий Иванов каждый день давал задания, благодаря которым мы смогли разобраться с деталями.Первые дни после начала школы мы занимались тем, что изучали необходимую теорию по нейронным сетям и обучению с подкреплением вместе с Дмитрием. После настало время кодинга: первая наша попытка реализовать DQN (Deep Q-learning Network) алгоритм и научить агента играть в Марио успехом не увенчалась. После девяти часов обучения прогресса не было, и мы не знали, в чем, собственно, дело. После тщетных попыток дебаггинга на питоне, командой было принято единственное разумное решение переписать код с нуля, что принесло свои плоды. Имея рабочую реализацию DQN, мы решили на этом не останавливаться, а написать модификацию Dueling DQN, сравнить ее со стандартным алгоритмом и посмотреть, какой агент лучше покажет себя в игре после обучения.

Dueling DQN

Основная идея Dueling DQN заключается в том, что нейронная сеть предсказывает не значения Q для всех действий, а отдельно средневзвешенное значение Q-функции по всем действиям (так называемое V-value), а также преимущества для каждого действия, которые определяются как разность между Q-функцией и средневзвешенным значением (подробнее можно почитать здесь).

advantage(s,a)=Q(s,a)-V(s)Визуализация архитектуры модели Dueling DQN (где-то на просторах интернета)Визуализация архитектуры модели Dueling DQN (где-то на просторах интернета)

Дополнительный функционал

Помимо алгоритмов обучения, нам необходимо было сделать еще несколько полезных вспомогательных фич: saver, logger, plotting, visualization.

Saver

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

Logger and Plotting

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

Visualization

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

Возникшие проблемы

На самом деле проблем во время работы над проектом была масса. Бороться с ними команде помогал куратор. Однако одна проблема заставила нас поломать головы над ее решением на определенном этапе вычислений Марио стал упираться в трубы, не пытаясь их перепрыгнуть.

Возникшая проблема с трубамиВозникшая проблема с трубами

Мы считаем, что эта особенность поведения связана с тем, что отрицательная награда от исхода времени на прохождение эпизода была меньше, чем отрицательная награда от смерти Марио при ударе с врагом. Другими словами, Марио "считал", что завершить уровень из-за истечения времени для него более предпочтительно, чем смерть.Эта проблема действительно поставила нас в тупик: мы не знали, как заставить агента проходить уровень. Мы бились над решением в течение многих часов, пока Арсений Хлытчиев не придумал модификацию функции награды, названную Punishment-оптимизацией (за что мы всей командой выражаем Арсению благодарность!) Он предложил добавлять отрицательную награду за "простой" Марио, чтобы восстановить значимость передвижения агента вперед по уровню. Это улучшение оказало сильное влияние на поведение агента в среде: Марио больше не застревал перед трубами.

Решение проблемы с трубамиРешение проблемы с трубами

Результаты

К окончанию школы мы получили агента, который неплохо справлялся с частичным прохождением первого уровня игры: Марио сумел пройти около 50%. При этом каждый член команды сумел одолеть Марио, дойдя до второго уровня.

Лучший gameplay МариоЛучший gameplay Марио

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

Функция потери

 DQN (слева) и Dueling DQN (справа) DQN (слева) и Dueling DQN (справа)

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

Функция награды

DQN (слева) и Dueling DQN (справа)DQN (слева) и Dueling DQN (справа)

Функция средней награды постепенно возрастает, это свидетельствует о том, что агенты узнают о среде больше, то есть проходят дальше по уровню. Из графиков видно, что агент с моделью обучения Dueling DQN в среднем получает такую же награду, что агент с DQN, однако модифицированной версии понадобилось практически в два раза меньше итераций, чтобы научиться получать такое среднее количество награды.

Заключение

Наш проект еще можно и нужно дорабатывать. Например, можно продолжить обучать агента, пока он не завершит уровень, подумать над другими оптимизациями алгоритма DQN и т.д. Но сейчас мы заняты другим: кто-то сдает ЕГЭ, кто-то готовится к летним школам по программированию, поэтому добавлять какие-либо изменения пока не планируем.

За время школы мы получили много опыта в командной разработке и базовые знания о машинном обучении, на основе которых можем создавать свои собственные ML-проекты. А еще мы познакомились с большим количеством интересных людей, которые также хотят развиваться в сфере IT. Поэтому хотим выразить безмерную благодарность организаторам смены, нашему куратору и всем, кто принимал участие в школе. Это был незабываемый и очень полезный опыт.

Подробнее..

Стратегия выбрать самую нелогичную стратегию, или как мы заняли второе место в Математической регате Тинькофф

14.08.2020 16:23:02 | Автор: admin
Всем привет! Мы студенты четвертого курса Прикладной математики и информатики Питерской Вышки. В июле мы поучаствовали в Математической регате Тинькофф, и в этом посте расскажем о том, что это за соревнование, о том, какова была наша стратегия, и покажем примеры задач.


Картинка с официального сайта Математической регаты

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

Итак, 18 июля пятеро студентов-программистов, которые вошли в состав команды Just4Fun, собрались участвовать в первом туре соревнования. С нами соперничала 391 команда, в каждой было по 35 человек. Всего 1628 участников из 131 города мира.

Правила первого тура


Первый тур длился два с половиной часа. Было предложено 25 задач, разбитых по 5 уровням сложности и 5 темам: комбинаторика, числовые задачи, алгебра, теория вероятностей, геометрия.

Начальный капитал команды 1000 очков. Каждая задача стоит от 100 до 500 очков: чем выше стоимость, тем сложнее задача. Если команда покупает задачу, ее стоимость вычитается из начального капитала (при этом нельзя уходить в минус). За верное решение с первой попытки начисляется $inline$2x$inline$ от стоимости задачи, со второй $inline$1.5x$inline$, с третьей $inline$1x$inline$.

Каждая задача имеет ответ в виде числа, которое нужно ввести в соответствующее поле на сайте. Покупать и сдавать задачи может только капитан.

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



Также было несколько способов получить бонусные очки. Например, их присуждали команде, которая первой решила все задачи из одной темы или одного уровня сложности, и первой команде, сдавшей все задачи без единой ошибки. Чем сложнее было выполнить условие для получения бонуса, тем больше баллов он приносил.

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

Первый тур


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

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

Мы решили бороться за бонус, который дадут первой команде, решившей все задачи стоимостью в 400 баллов. Мы выбрали такую стратегию, чтобы уменьшить конкуренцию: план показался нам самым нелогичным, ведь в начале соревнования нельзя открыть три задачи такой стоимости (начальный капитал всего лишь 1000) и в то же время бонус за эти задачи не самый ценный.

Наш план увенчался успехом! В итоге мы решили все задачи первого тура, причем все, кроме одной, сдали с первой попытки. Вместе с бонусом это позволило нам занять второе место в первом этапе и пройти в финал.



Отдельно хочется остановиться на процессе решения задач. Все-таки мы скорее программисты, чем математики, и во время соревнования мы активно пользовались компьютером (это было разрешено правилами). Более половины задач мы решили при помощи Wolfram, Python и, неожиданно, C++ (для действительно быстрых переборов). С одной стороны, это не математично, но с другой позволило решить задачи в максимально короткие сроки.

Правила второго тура


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



Каждой задаче соответствовала доминошка (0:1, 0:2, ..., 6:6 всего 27 штук). В первые 2,5 часа команды решали задачи и собирали себе снаряды в виде доминошек.

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

Допустим, наша команда поставила доминошку [2:5] против команды N и решила, что число 5 будет соответствовать атаке, а 2 защите. Команда N поставила против нас доминошку с защитой 3 и атакой 4. Тогда наша команда получит урон, равный 2 $inline$(4-2=2)$inline$, и команда N тоже $inline$(5-3=2)$inline$. Каждое из этих чисел вычитается из очков команды, которая защищалась, и прибавляется к очкам нападающей команды. Побеждает команда с наибольшим количеством очков по итогам трех раундов.

Второй тур


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

К началу первого раунда мы решили порядка 15 задач разной сложности и этого не хватало на все три тура (нужна 21 задача). Во время боя нам в авральном режиме пришлось решать задачи попроще, которые прежде казались скучными, чтобы получить хоть сколько-нибудь очков. В итоге мы почти справились, но в поле ответа 21-ой задачи все-таки был отправлен рандом.

По результатам финального тура мы заняли второе место, сильно отстав от первой команды и прилично обогнав третью. У нас 25 очков, у первой 55 и у третьей 14.

Общие впечатления


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

Задачки с турнира


Задача из первого тура


Тема: Вероятность.
Стоимость: 500.
У Вани есть два доллара. Он подбрасывает монетку. Если выпадает орел, Ваня получает 2 доллара; если решка, он теряет половину своих денег. Если решка выпала два раза подряд, то игра заканчивается, при этом в последнем раунде Ваня не теряет деньги. Найти матожидание количества денег у Вани после окончания игры.

Решение:
Найдем количество последовательностей длины $inline$n$inline$ из орлов и решек с фиксированным последним элементом, в которых нет двух решек, идущих подряд.

Число последовательностей длины $inline$n$inline$ с последней решкой обозначим как $inline$h(n)$inline$, с последним орлом $inline$F(n)$inline$.
$inline$h(n) = F(n 1)$inline$ (нельзя, чтобы предпоследний элемент тоже был решкой).
$inline$F(n) = F(n 1) + h(n - 1) = F(n - 1) + F(n - 2)$inline$ (предпоследний элемент любой)

Получили последовательность Фибоначчи c начальными данными $inline$F(0) = F(1) = 1$inline$.

Допустим, Ваня сделал $inline$n$inline$ бросков и игра не закончилась. Зафиксируем последнюю выпавшую сторону монетки (орел или решка) и обозначим сумму Ваниных выигрышей по всем последовательностям, удовлетворяющим условиям (последняя сторона зафиксирована и нет двух решек подряд), как $inline$f(n)$inline$ (последний орел) и $inline$g(n)$inline$ (последняя решка).

Осталось написать рекуррентные соотношения на $inline$f$inline$ и $inline$g$inline$.

Для начала разберемся с $inline$g$inline$. Заметим, что если последовательность оканчивается на решку, то предпоследним должен идти орел (т. к. двух последовательных решек быть не может), следовательно, $inline$g(n) = \frac{f(n 1)}{2}$inline$, при выпадении решки Ванина сумма уменьшилась в два раза.

Теперь с $inline$f$inline$. В этом варианте предпоследним может быть как орел, так и решка. По условию, выпадения орла просто добавляет 2 к сумме,т. е. $inline$f(n) = f(n 1) + g(n - 1) + 2F(n)$inline$ (вот для этого $inline$F$inline$ были посчитаны заранее).

Все промежуточные вычисления сделаны, осталось только посчитать ответ.

Игра заканчивается тогда, когда Ваня выбрасывает вторую решку подряд. Заметим, что вероятность в итоге получить конкретную последовательность длины $inline$n > 1$inline$ (с двумя решками в конце) это $inline$\frac{1}{2^n}$inline$ (случайно равновероятно выбираем каждый элемент). Тогда осталось найти $inline$\sum\limits_{i = 2}^{+\infty} \frac{g(i 1)}{2^i} = \frac{f(i - 2)}{2^{i + 1}}$inline$.

Это некоторое техническое упражнение, далее идут соответствующие выкладки. Опустим корректность перестановки слагаемых в суммах.

Сперва вспомогательная сумма:

$$display$$S_1 = \sum_{n = 1}^{\infty} \frac{F(n)}{2^n} = F(1) + \sum_{n=2}^{\infty} \frac {F(n 1) + F(n - 2)} {2 ^ n} = \\ = F(1) + \frac{3}{4} \sum_{n = 1}^{\infty} \frac{F(n)}{2 ^ n} = F(1) + \frac{3}{4} S_1 \implies S_1 = 4$$display$$



И аналогичные действия уже для нашей рекурренты:

$$display$$S_2 = \sum \frac{f(n)}{ 2 ^ {n + 3}} = \sum \frac {F(n)} {2 ^ {n + 2}} + \sum \frac {f(n 1) + f(n - 2) / 2} {2 ^ {n + 3}} = \\ = S_1 / 4 + \frac{5}{8} S_2 \implies S_2 = \frac{8}{3}$$display$$



Ответ: $inline$\frac{8}{3}$inline$

Задача из второго тура


Соответствовала доминошке [2:3].

Больше всего запомнилась одна простая задачка из второго тура. В ней требовалось посчитать, сколько раз нужно проделать операцию $inline$DF$inline$ с кубиком Рубика, чтобы он вернулся в исходное состояние (операция $inline$DF$inline$: сначала по часовой стрелке повернуть фронтальную часть, затем по часовой стрелке повернуть нижнюю часть).

Математическое решение:
Заметим, что повороты кубика рубика можно описать с помощью некоторой подгруппы симметрической группы S_48.

Обозначим поворот фронтальной части как $inline$F$inline$, а нижней как $inline$D$inline$. В таких обозначениях мы с кубиком сначала совершаем операцию $inline$F$inline$, а затем операцию $inline$D$inline$. Таким образом, если кубик находился в состоянии $inline$x$inline$, то он после одного хода перейдет в состояние $inline$DFx$inline$. Мы хотим найти минимальное количество шагов, которое нужно, чтобы перевести кубик в исходное состояние. Т. е. нужно посчитать порядок элемента $inline$DF$inline$. И $inline$D$inline$, и $inline$F$inline$ описываются перемножением перестановок. Давайте перемножим их все и обозначим результат как некоторую перестановку p. Чтобы посчитать ее порядок, достаточно найти НОК длин ее циклов.

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

Ответ: 105.
Подробнее..

Как мы управляли поездами на соревновании NeurIPS 2020 Flatland

15.01.2021 12:16:15 | Автор: admin
Всем привет! Мы команда из Питерской Вышки, и в этом году мы заняли первое место в RL треке соревнования NeurIPS 2020: Flatland. Цель Flatland разработать алгоритм, способный как можно лучше управлять трафиком движения поездов по сети железных дорог, при этом система должна принимать решения за ограниченное время.

О том, что это за соревнование и как нам удалось в нем победить (а на контест прислали большее 2000 решений из 51 страны) читайте под катом.




Наша команда


В команде JBR_HSE было пять участников: Константин Махнев (учится на 4-м курсе бакалаврской программы Прикладная математика и информатика) Олег Свидченко и Владимир Егоров (оба учатся в магистратуре Программирование и анализ данных), аспирант Дмитрий Иванов и заведующий Центром анализа данных и машинного обучения НИУ ВШЭ Санкт-Петербург Алексей Шпильман. Все, кроме Константина, также работают в лаборатории Агентных систем и обучения с подкреплением JetBrains Research отсюда и название команды. Во время участия в соревновании Костя стажировался в этой же лаборатории.

NeurIPS 2020: Flatland что это?


Flatland это соревнование, которое проходило с 10 июля по 15 ноября на основе платформы AIcrowd и при поддержке известной международной конференции NeurIPS. Цель соревнования разработать алгоритм, способный как можно лучше управлять железнодорожным трафиком. Важным ограничением было то, что решения нужно принимать за ограниченное время (5 секунд на один шаг симулятора), что не позволяло просто подбирать оптимальные действия.



В NeurIPS 2020: Flatland было два направления: общее и Reinforcement Learning (RL). Первое направление было открыто для любых решений, а второе только для тех, которые используют обучение с подкреплением.

Организаторы предоставили участникам симулятор Flatland, который представляет собой двумерную сетку, где каждая клетка имеет свой тип: дорога, поворот, развилка или непроходимая местность. Каждый поезд занимает ровно одну клетку на сетке и имеет направление, по которому он сейчас перемещается. Симуляция происходит пошагово, на каждом шаге для каждого поезда нужно определить, какое действие ему совершить: остановиться, ехать по самому левому пути или ехать по самому правому пути. Поскольку в текущей реализации полного перекрестка не предусмотрено, т.е. не бывает так, что можно поехать одновременно вперед, направо и налево, то и действие ехать вперед тоже не нужно. В случае, когда никаких поворотов нет, второе и третье действие эквивалентны. Поезда могут сталкиваться между собой получается deadlock. Задача соревнования заставить все поезда как можно быстрее доехать до их пунктов назначения. Решения оцениваются по сумме времени, которое потратили поезда на достижение цели. В случае, если поезд не доехал, его время равно максимальному времени симуляции.

Решение: как агент будет взаимодействовать с симулятором


На Хабре уже было достаточно много постов про обучение с подкреплением, поэтому не будем подробно останавливаться на основных понятиях. Скажем только, что в случае Flatland в качестве среды выступает симуляция железной дороги, а в качестве агентов поезда. Важно отметить, что поскольку в симуляции участвует множество поездов, то данное окружение является мультиагентным.

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

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

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

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



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

Осталось определить только функцию награды для агента. После некоторого подбора, мы остановились на довольно простой: $0.01 \cdot \Delta d 5 \cdot \text{is\_deadlocked} + 10 \cdot \text{is\_succeed}$, т.е. награда отражает то, насколько изменилось расстояние $d$ до пункта назначения после принятия решения, с дополнительными наградой в случае успешного завершения эпизода и наказанием в случае попадания в дедлок.

Алгоритм PPO


Существует множество алгоритмов обучения с подкреплением, которые разработаны для решения мультиагентных задач. Однако в качестве baseline алгоритма мы решили использовать алгоритм PPO Proximal Policy Optimization, поскольку его код можно было бы переиспользовать для реализации алгоритмов multiagent RL (например, COMA). Позже, правда, оказалось, что PPO (с некоторыми модификациями) сам по себе решает задачу неплохо, а вот мультиагентные методы обучаются значительно хуже, поэтому PPO остался основной частью нашего финального решения.

Классический алгоритм PPO состоит из двух частей: актора и критика. Критик приближает value-function, а актор учит рандомизированную политику $\pi_\theta(a | s)$, которая максимизирует математическое ожидание суммарной награды.



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

Обучать PPO решили с картой небольшого размера и маленьким количеством агентов, предположив, что поскольку агент наблюдает только то, что находится рядом с ним, после обучения он будет хорошо работать и в окружениях большего размера.

Как решить, каким поездам когда стартовать?


Попробовав просто применить алгоритм PPO, мы довольно быстро пришли к выводу, что большая часть дедлоков происходит именно из-за того, что поезда начинают двигаться одновременно и мешают друг другу. Эту проблему мы решили так: стали одновременно запускать только несколько агентов. Когда один из агентов заканчивал свой эпизод, другому агенту позволялось начать движение. В таком подходе важно понять, в какой последовательности нужно запускать поезда.

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

Результаты соревнования


В результате наше решение заняло первое место в треке RL и восьмое место в общем зачете. Это значит, что на данный момент не-RL подход пока решает лучше, однако показывает, что у обучения с подкреплением есть потенциал. В нашем подходе довольно много слабых мест и нерешенных вопросов (например, серьезные проблемы с масштабируемостью на окружения большого размера), поэтому нам есть, над чем еще поработать. Сейчас мы вместе с организаторами соревнования готовим статью для отправки ее в competition book NeurIPS 2020.
Подробнее..

Категории

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

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru