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

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

Версия 17:13, 30 марта 2008

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

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

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

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

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

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

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

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

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

Методика тестирования основана на процедуре 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) — это эмпирическая оценка того, какой должна быть функция роста в оценках Вапника-Червоненкиса, чтобы они не были завышенными. Эта величина представляет теоретический интерес.

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

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

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

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

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

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

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

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

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

Пополнение базы задач

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

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

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

Пополнение базы алгоритмов

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

На одном вычислительном сервере может быть реализовано несколько алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

Разработка системы инициирована осуществляется при поддержке РФФИ (проект № 07-07-00372).

{{{1}}}