Большие данные

1

Анализ текстов

(паспорт проекта)

Задачи Natural language processing встречаются во многих отраслях, не стал исключением и банкинг. Участники проекта смогут самостоятельно пройти по всему пайплайну задачи промышленного анализа данных (школьники займутся постановкой задач, изучением существующих методов, прототипированием, созданием продукта) на примере задачи Fact Сhecking. Задача заключается в проверке входного утверждения на истинность. Fact Checkingом занимаются во многих исследовательских центрах. В настоящее время это «нерешенная задача»: постоянно появляются новые подходы и улучшаются результаты по существующим. Работа над ней поможет на высоком уровне разобраться в анализе текстов и машинном обучении. По итогам проекта будет создан чат-бот, проверяющий входные утверждения на истинность (первый шаг к созданию вопросно-ответной системы)

Никитин Александр Викторович,
разработчик, «Яндекс», ООО «Сбертех»

2

Анализ транзакций (SDSJ)
(паспорт проекта)

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

Дербаносов Роман Юрьевич, руководитель направления в Корпоративном университете Сбербанка

3

Двуслойный ацтекский бриллиант

(паспорт проекта)

Как устроено типичное разбиение большого двуслойного ацтекского бриллианта на «домино» 1x1x2 и как быстро растет число разбиений в зависимости от его размера?

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

Христофоров Михаил Игоревич, научный сотрудник Санкт-Петербургского Государственного Университета

4

Формальные языки над полем GF(2)

(паспорт проекта)

Формальный язык — это математическая модель языка как способа представления информации в виде символьных строк. Теория формальных языков изучает способы определения синтаксиса языков, алгоритмы их обработки,  а также, более широко, модели вычислительных устройств, обрабатывающих строковые данные. Эта область хорошо изучена, ее основы преподаются в стандартных университетских курсах. Проект посвящен изучению новой разновидности формальных языков,  в которых классическая булева логика заменена на иную, основанную на операции «исключающее ИЛИ» вместо обычного «ИЛИ», в терминах алгебры полученная логика соответствует полю GF(2). Поскольку такая модель ранее не изучалась, участники проекта получат возможность первыми открыть и доказать  свойства этих языков. Например, можно будет изучить такие вопросы, как способы описания синтаксиса с помощью новых операций, придуманных в рамках проекта, трудоемкость обработки информации с помощью этих операций

Охотин Александр Сергеевич, Ph.D., профессор образовательной программы «Математика» Санкт-Петербургского Государственного Университета

5

Компьютерное моделирование динамических систем

(паспорт проекта)

В проекте «Компьютерное моделирование динамических систем» рассматриваются различные способы моделирования на компьютере систем, эволюционирующих во времени. Рассматривается два класса задач:

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

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

Тихомиров Сергей Борисович, кандидат физико-математических наук, доцент Санкт-Петербургского Государственного Университета

6

Автоматическая проверка корректности теорем

(паспорт проекта)

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

Яковлев Павел Андреевич, директор департамента вычислительной биологии в компании «BIOCAD»

7

Комбинаторная жесткость: алгоритмы и приложения

(паспорт проекта)

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

Воронов Всеволод Александрович, кандидат технических наук, научный сотрудник Института динамики систем и теории управления СО РАН

8

Convex optimization for Big Data applications

(паспорт проекта)

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

Нестеров Юрий Евгеньевич, доктор физико-математических наук, профессор, Universite Catholique de Louvain-la-Neuve, Бельгия, ВШЭ, Россия

9

Reinforcment Learning and Sheduling

(паспорт проекта)

Обучение с подкреплением — популярная ветвь современной науки о данных. Мы постараемся сначала подготовить математический фундамент, проводя внутренние вводные лекции по марковским цепям, управляемым марковским процессам, принципу динамического программирования (Вальда-Беллмана), формуле Байеса. Материал планируется закреплять разбором многочисленных простых примеров. Затем мы начнем готовить проектную часть. В проекте рассматривается реальная задача составления оптимального расписания базовой станции (сотовой вышки), вокруг которой имеются клиенты (пользователи мобильных телефонов и других гаджетов, имеющих доступ в интернет). Задача составления расписания заключается в определении того, в каком порядке обслуживать запросы пользователей по скачиванию (загрузке) различных web-страниц (в общем случае — файлов). Проектную часть планируется связать с работой с реальными данными. Для этого со школьниками будут проводиться занятия на языке Python, чтобы они смогли впоследствии самостоятельно работать с этими данными, проверяя свои алгоритмы. Параллельно обучению техническим премудростям на занятиях школьники узнают об уже более продвинутых алгоритмах/подходах в решении задачи о многоруких бандитах (марковские бандиты, беспокойные бандиты); индексах Гиттинса и Уиттла как способе решения уравнения Вальда-Беллмана; примерах применения индексов (многорукие бандиты, ящик Пандоры и др.); элементах эргодической теории случайных процессов; скейлинге случайных процессов (теорема Куртца) и Proportional-Fair Sharin алгоритме; элементах теории систем массового обслуживания; Shortest Remaning Processing Time (Scharge theorem), которые должны позволить «собрать» наилучший метод. Цель — построить такое расписание (на базе индексов и обучения с подкреплением), чтобы предложенные школьниками индексы в среднем работали лучше использующихся сейчас

Гасников Александр Владимирович, доктор физико-математических наук, доцент МФТИ, ИППИ РАН

10

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

(паспорт проекта)

Проект посвящен теоретическому и практическому анализу сложных сетей (complex networks). Под сложными сетями обычно понимают совершенно разные графы (сети), которые встречаются в природе и обладают нетривиальными топологическими свойствами, от компьютерных и социальных сетей до биологических и экономических. Удивительно, но, несмотря на столь разные области происхождения, все эти сети обладают многими общими свойствами: малым диаметром (теория 6 рукопожатий), степенным законом распределения степеней вершин, выраженной кластерной структурой и другими. В данном проекте на реальных примерах сложных сетей будут разбираться и анализироваться их основные свойства. Предполагается как экспериментальный, так и математический анализ. Особое внимание будет уделено кластерной структуре сложных сетей. Будут проанализированы различные определения кластеров и алгоритмы кластеризации. Кластерная структура сети — это наличие групп вершин, внутри которых плотность ребер высокая, при этом между группами ребер мало. Кластерная структура является важным свойством сети, т. к. она существенно влияет, в частности, на распространение информации (вирусов, рекламных сообщений и т. д.) по графу

Прохоренкова Людмила Александровна, ккандидат физико-математических наук, старший научный сотрудник лаборатории продвинутой комбинаторики и сетевых приложений МФТИ, исследователь, «Яндекс».

Райгородский Андрей Михайлович, доктор физико-математических наук, федеральный профессор математики, директор Физтех-школы прикладной математики и информатики, главный научный сотрудник и заведующий лабораторией продвинутой комбинаторики и сетевых приложений МФТИ, заведующий кафедрой дискретной математики МФТИ, профессор механико-математического факультета МГУ, руководитель исследовательской группы в «Яндексе»

11

Распознавание объектов на спутниковых снимках

(паспорт проекта)

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

1. построить собственное решение для данных из соревнования Dstl Satellite Imagery Feature Detection, что потребует обучения глубоких нейронных сетей;

2. скачать спутниковые снимки через открытое API «Яндекс.Карт» и с помощью библиотеки scikit-learn научиться распознавать дома или другие объекты

Технология blockchain для следующего поколения интернета
(паспорт проекта)

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

Соловьев Алексей Викторович, генеральный директор "Киви Блокчейн Технологии"

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