Студенческий контест по Machine Learning Обучающие задачи Первый открытый контест ok.ru: Возраст по графу По мотивам онлайн-игр Задача с секретом Предсказание ССЗ ok.ru: Связи пользователей Прогноз отклика аудитории на интернет-опрос Telecom Data Cup Ответы Mail.ru (Хакатон, МФТИ) SNA Hackathon - Коллаборативная система SNA Hackathon - Картинки SNA Hackathon - Тексты ML Boot Camp 9
Участники
  • 1
    Михаил Карачун
  • 2
    Евгений Цацорин
  • 3
    Mikhail Novikov
  • 4
    Андрей Селиванов
  • 5
    Vasja Solodovnikov
Задача "Оценка производительности"

За какое время можно умножить две квадратные матрицы порядка n? Студент-математик или студент-программист 1-го курса скажет, что за O(n3). Продвинутый студент наверняка упомянет метод Штрассена, умножащий матрицы за O(nlog 7) операций, ну а эксперт вам расскажет про алгоритм Винограда… Инженер-программист, находящийся ближе к “железу”, возможно, воспримет этот вопрос буквально: сколько реальных секунд или миллисекунд будут умножаться на компьютере две матрицы порядка, например, 1000x1000? Конечно, все зависит и от используемого алгоритма, и от быстродействия компьютера, и от низкоуровневых оптимизаций кода…

 

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

 

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

 

Все предоставленные для задачи данные разбиты на две части: обучающую (x_train.csv и y_train.csv) и тестовую (x_test.csv). Каждая строка файлов x_train.csv и x_test.csv содержит набор признаков, описывающий отдельный вычислительный эксперимент: параметры задачи (m, k, n)  и характеристики вычислительной системы, на которой запускался алгоритм:

 

  • пиковая теоретическая производительность для чисел с плавающей запятой двойной точности;
  • информация о каждом уровне кэш-памяти процессора: размер кэш-памяти, является кэш общим для нескольких ядер или принадлежит только одному;
  • количество портов доступа к кэш-памяти;
  • тактовая частота процессора;
  • тактовая частота процессора в turbo-режиме;
  • тактовая частота системной шины;
  • информация о подсистеме памяти: количество каналов доступа, тайминг памяти: CAS Latency, RAS to CAS Delay, RAS Precharge, Cycle Time;
  • количество вычислительных ядер, количество процессоров;
  • включена ли технология Hyper-Threading;
  • тип процессора: для мобильных устройств, настольный, серверный; производитель процессора: Intel, AMD;
  • тип ядра: Ivy Bridge, Sandy Bridge, Conroe, Haswell, Wolfdale, Arrandale, Brisbane, Yorfield, Pineview, Penryn, Lynnfield;
  • поддерживаемый набор инструкций: AVX, FMA4, SSE5, SSE4a, SSE4.2

 

и др.

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

 

Файл y_train.csv содержит время (в секундах) выполнения умножения матриц для экспериментов, характеристики которых записаны в файле x_train.csv. Обучающая выборка (x_train.csv и y_train.csv) содержит информацию о 4993 экспериментах, тестовая (x_test.csv) – о 4947 экспериментах. Каждый эксперимент характеризуется 951 признаком.

 

В качестве ответа для данной задачи принимается файл в формате csv, состоящий из 4947 строк ровно. Каждая строка файла должна соответствовать строке в файле x_test.csv и содержать предсказанное время. Обращаем ваше внимание, в отличие от y_train.csv, строчка time в начале файла с решением не нужна. В день можно отправить не более 5 решений.

 

В качестве критерия качества решения задачи используется наименьшая средняя относительная ошибка (MAPE, в некоторых источниках упоминается как MRE) для реализаций, работающих больше одной секунды:

где N – количество объектов в выборке, yi – истинное время работы в i ­м эксперимента, gi – предсказанное время. В отличие от предыдущих конкурсов, в этот раз наша задача минимизировать критерий, а не максимизировать его (то есть, чем меньше MAPE, тем ближе результат к идеальному).

 

Тестовая выборка случайным образом разбита на две части в соотношении 40/60. Результат на первых 40% будет определять положение участников в рейтинговой таблице на всем протяжении конкурса. Результат на оставшихся 60% станет известен после окончания конкурса и именно он определит финальную расстановку участников.

 

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

 

Успехов!