Полигон алгоритмов

Материал из MachineLearning.

Версия 18:19, 27 февраля 2011

Полигон алгоритмов или «Полигон» — проект по созданию распределённой системы тестирования алгоритмов классификации на данных реальных прикладных задач. Сайт проекта: http://poligon.machinelearning.ru.

Назначение системы

Система «Полигон» предназначена для массового тестирования алгоритмов классификации на реальных задачах и представления результатов тестирования через web-интерфейс.

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

Цели создания «Полигона»

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

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

Основные функциональные возможности

Поддержка базы задач

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

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

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

Поддержка базы алгоритмов

Алгоритм классификации принимает на входе матрицу обучающей выборки, матрицу тестовой выборки и набор управляющих параметров, а на выходе выдаёт матрицы классификаций обучающей и тестовой выборки. Алгоритм реализуется в виде вычислительного модуля (плагина, plug-in), в соотвествии с внутренними стандартами системы «Полигон», и размещается на собственном компьютере пользователя.

Взаимодействие системы «Полигон» с пользовательскими алгоритмами осуществляется при помощи веб-сервисов.

Разграничение прав доступа

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

Методика тестирования

Методика тестирования основана на процедуре N-кратного скользящего контроля (N-fold cross-validation). Выборка N раз разбивается на блоки примерно одинаковой длины, случайным образом, но со cтратификацией классов. Каждый из N блоков поочерёдно объявляется контрольной подвыборкой, остальные N–1 блоков объединяются в обучающую подвыборку. Производится настройка алгоритма по обучающей подвыборке, затем настроенный алгоритм классифицирует объекты контрольной подвыбоки. Процедура обучения повторяется N раз, в результате все объекты оказываются классифицированными как контрольные ровно по одному разу, и как обучающие по (N–1) раз.

Процедура T×N-кратного скользящего контроля (T×N-fold cross-validation) является T-кратным выполнением описанной выше процедуры при T различных случайных разбиениях на N блоков, со стратификацией классов. В результате T×N-кратного скользящего контроля все объекты оказываются классифицированными как контрольные ровно по T раз, и как обучающие по T(N–1) раз.

Результаты всех классификаций используются для вычисления набора показателей, некоторые из которых представляются в виде графиков:

1. Основной показатель качества — средняя частота ошибок на контроле, с доверительным интервалом.
2. Средняя переобученность (разность частоты ошибок на контроле и обучении).
3. Графики эмпирических распределений частоты ошибок на контроле и переобученности. Эмпирические распределения позволяют оценивать риски, свзязанные с переобучением.
4. ROC-кривые на обучающих и контрольных данных. Если число классов превышает 2, то для каждого класса строится своя ROC-кривая.
5. Разложение средней ошибки на вариацию и смещение (bias-variance decomposition).
6. График распределения объектов выборки по значениям вариации и смещения.
7. Профиль разделимости (distribution of margin) вычисляется только для вещественнозначных алгоритмов классификации. График профиля разделимости наглядно разделяет объекты выборки на шумовые, пограничные (зону неуверенности) и эталонные.
8. Профиль представительности объектов. Для каждого объекта вычисляется доля разбиений, при которых он попадает в контроль, и на нём допускается ошибка. График профиля представительности позволяет идентифицировать объекты, являющиеся выбросами с точки зрения данного алгоритма.
9. Эффективный локальный коэффициент разнообразия (shatter coefficient) — это эмпирическая оценка того, какой должна быть функция роста в оценках Вапника-Червоненкиса, чтобы они не были завышенными. Эта величина представляет теоретический интерес.

Список показателей будет расширяться.

Формирование отчётов

Пользователь формирует запрос на получение отчёта, задавая:

• список задач из репозитория системы;
• список алгоритмов, из числа доступных в системе;
• внешние (управляющие) параметры каждого алгоритма, если таковые имеются;
• параметры методики тестирования.

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

Доступны также детальные отчёты:

• по данной задаче и данному алгоритму все показатели и графики, рассчитанные согласно методике;
• по данной задаче таблица «алгоритмы × показатели»;
• по данному алгоритму таблица «задачи × показатели»;

Формы представления отчётов будут расширяться.

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

Защита от возможных фальсификаций результатов тестирования

Теоретически возможно несколько видов фальсификации результатов тестирования:

• Некоторые задачи, находящиеся в базе «Полигона», являются общедоступными. Недобросовестный разработчик вычислительного сервера мог бы просто подставлять заранее известные правильные ответы, создавая иллюзию высокого качества работы своего алгоритма.
• При N-кратном скользящем контроле правильные ответы на всех объектах уже при втором обращении к алгоритму становятся известны. Поэтому фальсификация возможна и для задач, не являющихся общедоступными.

Центральный сервер «Полигона» предпринимает несколько мер, затрудняющих фальсификацию, и реализует несколько оригинальных методик выявления возможных фальсификаций.

Преимущества «Полигона»

Зачем разрабатывать новую систему, если уже есть RapidMiner, WEKA, R, Matlab, STATISTICA и многое другое?

• Перечисленные системы не гарантируют воспроизводимость и верифицируемость результатов тестирования. Все они устанавливаются локально на компьютере пользователя, оставляя ему возможность по-своему реализовать методику тестирования, модифицировать исходные данные, а в некоторых случаях — и сами алгоритмы. Как следствие, эмпирические результаты, представленные в разных статьях, оказываются несопоставимыми, даже если тестирование проводилось на одних и тех задачах (как правило, из репозитория UCI).
• В системах с открытым кодом RapidMiner, WEKA, R невозможно использовать коммерческие алгоритмы. В то же время, их владельцы вполне могли бы предоставлять их для тестирования, которое не предполагает извлечения коммерческой выгоды. Как раз наоборот, сами владельцы получат выгоду от рекламы, разумеется, если их алгоритм действительно работает хорошо. Однако предоставление коммерческих алгоритмов для целей тестирования наталкивается на технические и юридические сложности. «Полигон» решает эти проблемы, поскольку алгоритмы остаются «на территории» владельца, и владелец имеет возможность ограничивать доступ к алгоритму.
• Нет никаких ограничений на язык программирования, используемый для реализации алгоритмов. RapidMiner и WEKA допускают только Java, что снижает скорость выполнения алгоритмов и затрудняет перенос в систему готовых алгоритмов, написанных на других языках.
• К настоящему времени сложилась де факто стандартная методика тестирования, основанная на T×N-кратном скользящем контроле. «Полигон» существенно расширяет эту методику. Вычисляется не только средняя ошибка на контрольных данных, но и масса других показателей, с разных сторон характеризующих поведение алгоритма.

Разработка системы

Разработка системы инициирована научной группой члена-корреспондента РАН К. В. Рудакова в Вычислительном центре РАН и компанией Форексис. Проект поддержан грантом РФФИ № 07-07-00372.

Подстраницы

• TODO-лист
• Документация
• Мастер загрузки задач
• Мастер формирования отчета
• Общий отчёт задачи-алгоритмы
• Подробный отчет по задаче
• Подробный отчёт задача-алгоритм
• Формат данных задачи
• Мастер регистрации алгоритмов
• Взаимодействие с пользовательскими алгоритмами
• Пошаговая реализация собственного алгоритма
• Права доступа к объектам Системы
• Формат результатов тестирования алгоритма на задаче

Литература

1. Воронцов К.В., Инякин А.С., Лисица А.В. Система эмпирического измерения качества алгоритмов классификации // Всеросс. конф. Математические методы распознавания образов-13 — М.: МАКС Пресс, 2007. — С. 577–580.
2. Воронцов К.В., Ивахненко А.А., Инякин А.С., Лисица А.В., Минаев П.Ю. «Полигон» — распределённая система для эмпирического анализа задач и алгоритмов классификации // Всеросс. конф. Математические методы распознавания образов ММРО-14 — М.: МАКС Пресс, 2009. — С. 503–506.
3. Лисица А.В., Воронцов К.В., Ивахненко А.А., Инякин А.С., Синцова В.В. Системы тестирования алгоритмов машинного обучения: MLcomp, TunedIt и Полигон // Межд. конф. Интеллектуализация обработки информации ИОИ-8 — М.: МАКС Пресс, 2010. — С. 157–160.

В настоящее время «Полигон» находится в стадии разработки. Высказывайте Ваши предложения на странице Обсуждение:Полигон алгоритмов. К команде разработчиков можно присоединяться!