Полигон алгоритмов
Материал из MachineLearning.
(Различия между версиями)
| Строка 1: | Строка 1: | ||
| - | '''Полигон алгоритмов''' или | + | '''Полигон алгоритмов''' или «Полигон» — проект по созданию распределённой системы тестирования [[алгоритм]]ов [[Классификация|классификации]] на данных [[Прикладные задачи анализа данных|реальных прикладных задач]]. |
== Назначение системы == | == Назначение системы == | ||
| - | Система «Полигон» предназначена для массового тестирования алгоритмов классификации на [[ | + | Система «Полигон» предназначена для массового тестирования алгоритмов классификации на [[реальные данные|реальных задачах]] и представления результатов тестирования через web-интерфейс. |
| + | |||
Пользователями Системы являются специалисты по анализу данных, эксперты в различных предметных областях, разработчики алгоритмов, научные работники, учащиеся и преподаватели вузов. | Пользователями Системы являются специалисты по анализу данных, эксперты в различных предметных областях, разработчики алгоритмов, научные работники, учащиеся и преподаватели вузов. | ||
| - | == Цели | + | == Цели создания «Полигона» == |
| - | Создать общедоступный инструмент для массового решения задач классификации и распознавания образов, возникающих в различных предметных областях. | + | * Создать общедоступный инструмент для массового решения задач [[классификация|классификации]] и [[распознавание образов|распознавания образов]], возникающих в различных предметных областях. |
| - | Обеспечить пользователей удобным и гибким механизмом разграничения прав доступа к алгоритмам, исходным данным | + | * Предоставить открытую технологию пополнения библиотеки алгоритмов и базы задач. |
| - | + | * Предоставить современную методику тестирования, основанную на [[скользящий контроль|скользящем контроле]] и расширенном наборе показателей качества алгоритмов. | |
| + | * Обеспечить пользователей удобным и гибким механизмом разграничения прав доступа к алгоритмам, исходным данным и результатам тестирования, с целью сохранения авторских прав и конфиденциальности. | ||
| - | == | + | <!--- |
| - | + | Одной из целей создания Системы является поднятие престижа российских научных школ в области [[машинное обучение|машинного обучения]] и [[интеллектуальный анализ данных|интеллектуального анализа данных]]. | |
| - | # | + | --> |
| - | # | + | |
| - | # | + | == Основные функциональные возможности == |
| - | + | ||
| - | + | === Методика тестирования === | |
| + | Методика тестирования основана на процедуре ''N''-кратного [[Скользящий контроль|скользящего контроля]] (''N''-fold cross-validation). | ||
| + | Выборка ''N'' раз разбивается на блоки примерно одинаковой длины, случайным образом, но со [[стратификация|cтратификацией классов]]. | ||
| + | Каждый из ''N'' блоков поочерёдно объявляется контрольной подвыборкой, остальные ''N''–1 блоков объединяются в обучающую подвыборку. | ||
| + | Производится настройка алгоритма по обучающей подвыборке, затем настроенный алгоритм классифицирует объекты контрольной подвыбоки. | ||
| + | Процедура обучения повторяется ''N'' раз, в результате все объекты оказываются классифицированными ''как контрольные'' ровно по одному разу, и ''как обучающие'' по (''N''–1) раз. | ||
| + | |||
| + | Процедура ''T×N''-кратного скользящего контроля (''T×N''-fold cross-validation) является ''T''-кратным выполнением описанной выше процедуры при ''T'' различных случайных разбиениях на ''N'' блоков, со стратификацией классов. | ||
| + | {{S|В результате}} ''T×N''-кратного скользящего контроля все объекты оказываются классифицированными ''как контрольные'' ровно по ''T'' раз, и ''как обучающие'' по ''T''(''N''–1) раз. | ||
| + | |||
| + | Результаты всех классификаций используются для вычисления набора показателей, некоторые из которых представляются в виде графиков: | ||
| + | # ''Основной показатель качества'' — средняя частота ошибок на контроле, с доверительным интервалом. | ||
| + | # Средняя переобученность (разность частоты ошибок на контроле и обучении). | ||
| + | # Графики эмпирических распределений частоты ошибок на контроле и переобученности. Эмпирические распределения позволяют оценивать риски, свзязанные с переобучением. | ||
| + | # Разложение средней ошибки на [[вариация и смещение|вариацию и смещение]] (bias-variance decomposition). | ||
| + | # График распределения объектов выборки по значениям вариации и смещения. | ||
| + | # [[Профиль разделимости]] (distribution of margin) вычисляется только для вещественнозначных алгоритмов классификации. График профиля разделимости наглядно разделяет объекты выборки на шумовые, пограничные (зону неуверенности) и эталонные. | ||
| + | # [[Профиль представительности]] объектов. Для каждого объекта вычисляется доля разбиений, при которых он попадает {{S|в контроль}}, {{S|и на нём}} допускается ошибка. График профиля представительности позволяет идентифицировать объекты, являющиеся выбросами с точки зрения данного алгоритма. | ||
| + | # Эффективный локальный коэффициент разнообразия (shatter coefficient) — это эмпирическая оценка того, какой должна быть [[функция роста]] в оценках [[Теория Вапника-Червоненкиса|Вапника-Червоненкиса]], чтобы они не были завышенными. Эта величина представляет теоретический интерес. | ||
| + | |||
| + | Список показателей будет расширяться. | ||
| + | |||
| + | === Формирование отчётов === | ||
| + | Пользователь формирует запрос на получение отчёта, задавая: | ||
| + | * список задач из репозитория системы; | ||
| + | * список алгоритмов, доступных в системе; | ||
| + | * внешние (управляющие) параметры каждого алгоритма, если таковые имеются; | ||
| + | * параметры методики тестирования. | ||
| + | |||
| + | В ответ на запрос строится основной отчёт в виде таблицы {{S|«задачи × алгоритмы»}}, в ячейках которых по умолчанию записан ''основной показатель качества''. | ||
| + | Показатель можно заменить на другой, например, вывести значения средней вариации и смещения. | ||
| + | |||
| + | Доступны также детальные отчёты: | ||
| + | * по данной задаче и данному алгоритму все показатели и графики, рассчитанные согласно методике; | ||
| + | * по данной задаче таблица {{S|«алгоритмы × показатели»}}; | ||
| + | * по данному алгоритму таблица {{S|«задачи × показатели»}}; | ||
| + | |||
| + | Формы представления отчётов будут расширяться. | ||
| + | |||
| + | Один раз вычисленные результаты тестирования сохраняются в центральной базе данных «Полигона» и при повторном запросе выдаются без обращения к алгоритмам. Когда алгоритм обновляется, его сохранённые результаты стираются. | ||
| + | Во многих случаях это позволяет получать отчёты очень быстро. Если Ваш алгоритм сравнивается со стандартными на стандартном наборе задач, то системе остаётся запустить только Ваш алгоритм. | ||
| + | |||
| + | === Пополнение базы задач === | ||
| + | База задач хранится централизованно на главном сервере «Полигона». | ||
| + | Пользователь имеет возможность загрузить в систему свою задачу и установить на неё права доступа (для себя, для группы или для всех). | ||
| + | |||
| + | Исходные данные по задаче представляются в виде матрицы [[признаковое описание|признаковых описаний]] объектов, в которой выделен целевой (прогнозируемый) признак. | ||
| + | Дополнительно могут задаваться: | ||
| + | * типы признаков (номинальный, порядковый или количественный); | ||
| + | * матрица (или вектор) штрафов за ошибочную классификацию. | ||
| + | |||
| + | === Пополнение базы алгоритмов === | ||
| + | Алгоритмы выполняются на удалённых вычислительных серверах. | ||
| + | Любой зарегистрированный пользователь имеет возможность объявить в системе свой компьютер как вычислительный сервер и разместить на нём программу, выполняющую его алгоритм. | ||
| + | Вычислительный сервер должен быть всё время включён, чтобы центральный сервер «Полигона» мог посылать ему запросы на выполнение алгоритма. | ||
| + | |||
| + | На одном вычислительном сервере может быть реализовано несколько алгоритмов. | ||
| + | |||
| + | Разработчикам вычислительных серверов предоставляется необходимое программное обеспечение и документации для разработки и отладки алгоритмов. | ||
| + | |||
| + | === Разграничение прав доступа === | ||
| + | Пользователям и группам пользователей предоставляется возможность устанавливать права доступа к своим задачам и алгоритмам для других пользователей и групп. | ||
| + | |||
| + | === Защита от возможных фальсификаций результатов тестирования === | ||
| + | Теоретически возможно несколько видов ''фальсификации'' результатов тестирования: | ||
| + | * Некоторые задачи, находящиеся в базе «Полигона», являются общедоступными. Недобросовестный разработчик вычислительного сервера мог бы просто подставлять заранее известные правильные ответы, создавая иллюзию высокого качества работы своего алгоритма. | ||
| + | * При ''N''-кратном скользящем контроле правильные ответы на всех объектах уже при втором обращении к алгоритму становятся известны. Поэтому фальсификация возможна и для задач, не являющихся общедоступными. | ||
| + | |||
| + | Центральный сервер «Полигона» реализует несколько оригинальных методик выявления возможных фальсификаций. | ||
| + | |||
| + | == Преимущества «Полигона» == | ||
| + | |||
| + | Зачем разрабатывать новую систему, если уже есть [[WEKA]], [[R]], [[Matlab]], [[STATISTICA]] и многое другое? | ||
| + | * Перечисленные системы не гарантируют воспроизводимость и верифицируемость результатов тестирования. Все они устанавливаются локально на компьютере пользователя, оставляя ему возможность по-своему реализовать методику тестирования, модифицировать исходные данные, а в некоторых случаях — и сами алгоритмы. Как следствие, эмпирические результаты, представленные в разных статьях, оказываются несопоставимыми, даже если тестирование проводилось на одних и тех задачах (как правило, из [[Репозиторий UCI|репозитория UCI]]). | ||
| + | * В системах с открытым кодом [[WEKA]], [[R]] невозможно использовать коммерческие алгоритмы. {{S|В то же время}}, их владельцы вполне могли бы предоставлять их для тестирования, которое не предполагает извлечения коммерческой выгоды. Как раз наоборот, сами владельцы получат выгоду от рекламы, разумеется, если их алгоритм действительно работает хорошо. Однако предоставление коммерческих алгоритмов для целей тестирования наталкивается на технические и юридические сложности. «Полигон» решает эти проблемы, поскольку алгоритмы остаются {{S|«на территории»}} владельца, и владелец имеет возможность ограничивать доступ к алгоритму. | ||
| + | * Нет никаких ограничений на язык программирования, используемый для реализации алгоритмов. [[WEKA]] допускает только Java, что снижает скорость выполнения алгоритмов и затрудняет перенос в систему готовых алгоритмов, написанных на других языках. | ||
| + | * К настоящему времени сложилась де факто стандартная методика тестирования, основанная на ''T×N''-кратном скользящем контроле. «Полигон» существенно расширяет эту методику. Вычисляется не только средняя ошибка на контрольных данных, но и масса других показателей, с разных сторон характеризующих поведение алгоритма. | ||
== Разработка системы == | == Разработка системы == | ||
| - | Разработка системы осуществляется при поддержке [[РФФИ]] (проект № 07-07-00372). Разработка осуществляется группой ученых и студентов. | + | Разработка системы инициирована осуществляется при поддержке [[РФФИ]] (проект {{S|№ 07-07-00372}}). |
| + | <!--- Разработка осуществляется группой ученых и студентов. | ||
| + | ---> | ||
| + | |||
| + | {{well|Содержание= | ||
| + | '''В настоящее время «Полигон» находится в стадии разработки.''' | ||
| + | #Высказывайте Ваши предложения на странице [[Обсуждение:Полигон алгоритмов]]. | ||
| + | #К команде разработчиков можно присоединяться! | ||
| + | }} | ||
{{Stub}} | {{Stub}} | ||
Версия 11:14, 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) раз.
Результаты всех классификаций используются для вычисления набора показателей, некоторые из которых представляются в виде графиков:
- Основной показатель качества — средняя частота ошибок на контроле, с доверительным интервалом.
- Средняя переобученность (разность частоты ошибок на контроле и обучении).
- Графики эмпирических распределений частоты ошибок на контроле и переобученности. Эмпирические распределения позволяют оценивать риски, свзязанные с переобучением.
- Разложение средней ошибки на вариацию и смещение (bias-variance decomposition).
- График распределения объектов выборки по значениям вариации и смещения.
- Профиль разделимости (distribution of margin) вычисляется только для вещественнозначных алгоритмов классификации. График профиля разделимости наглядно разделяет объекты выборки на шумовые, пограничные (зону неуверенности) и эталонные.
- Профиль представительности объектов. Для каждого объекта вычисляется доля разбиений, при которых он попадает в контроль, и на нём допускается ошибка. График профиля представительности позволяет идентифицировать объекты, являющиеся выбросами с точки зрения данного алгоритма.
- Эффективный локальный коэффициент разнообразия (shatter coefficient) — это эмпирическая оценка того, какой должна быть функция роста в оценках Вапника-Червоненкиса, чтобы они не были завышенными. Эта величина представляет теоретический интерес.
Список показателей будет расширяться.
Формирование отчётов
Пользователь формирует запрос на получение отчёта, задавая:
- список задач из репозитория системы;
- список алгоритмов, доступных в системе;
- внешние (управляющие) параметры каждого алгоритма, если таковые имеются;
- параметры методики тестирования.
В ответ на запрос строится основной отчёт в виде таблицы «задачи × алгоритмы», в ячейках которых по умолчанию записан основной показатель качества. Показатель можно заменить на другой, например, вывести значения средней вариации и смещения.
Доступны также детальные отчёты:
- по данной задаче и данному алгоритму все показатели и графики, рассчитанные согласно методике;
- по данной задаче таблица «алгоритмы × показатели»;
- по данному алгоритму таблица «задачи × показатели»;
Формы представления отчётов будут расширяться.
Один раз вычисленные результаты тестирования сохраняются в центральной базе данных «Полигона» и при повторном запросе выдаются без обращения к алгоритмам. Когда алгоритм обновляется, его сохранённые результаты стираются. Во многих случаях это позволяет получать отчёты очень быстро. Если Ваш алгоритм сравнивается со стандартными на стандартном наборе задач, то системе остаётся запустить только Ваш алгоритм.
Пополнение базы задач
База задач хранится централизованно на главном сервере «Полигона». Пользователь имеет возможность загрузить в систему свою задачу и установить на неё права доступа (для себя, для группы или для всех).
Исходные данные по задаче представляются в виде матрицы признаковых описаний объектов, в которой выделен целевой (прогнозируемый) признак. Дополнительно могут задаваться:
- типы признаков (номинальный, порядковый или количественный);
- матрица (или вектор) штрафов за ошибочную классификацию.
Пополнение базы алгоритмов
Алгоритмы выполняются на удалённых вычислительных серверах. Любой зарегистрированный пользователь имеет возможность объявить в системе свой компьютер как вычислительный сервер и разместить на нём программу, выполняющую его алгоритм. Вычислительный сервер должен быть всё время включён, чтобы центральный сервер «Полигона» мог посылать ему запросы на выполнение алгоритма.
На одном вычислительном сервере может быть реализовано несколько алгоритмов.
Разработчикам вычислительных серверов предоставляется необходимое программное обеспечение и документации для разработки и отладки алгоритмов.
Разграничение прав доступа
Пользователям и группам пользователей предоставляется возможность устанавливать права доступа к своим задачам и алгоритмам для других пользователей и групп.
Защита от возможных фальсификаций результатов тестирования
Теоретически возможно несколько видов фальсификации результатов тестирования:
- Некоторые задачи, находящиеся в базе «Полигона», являются общедоступными. Недобросовестный разработчик вычислительного сервера мог бы просто подставлять заранее известные правильные ответы, создавая иллюзию высокого качества работы своего алгоритма.
- При N-кратном скользящем контроле правильные ответы на всех объектах уже при втором обращении к алгоритму становятся известны. Поэтому фальсификация возможна и для задач, не являющихся общедоступными.
Центральный сервер «Полигона» реализует несколько оригинальных методик выявления возможных фальсификаций.
Преимущества «Полигона»
Зачем разрабатывать новую систему, если уже есть WEKA, R, Matlab, STATISTICA и многое другое?
- Перечисленные системы не гарантируют воспроизводимость и верифицируемость результатов тестирования. Все они устанавливаются локально на компьютере пользователя, оставляя ему возможность по-своему реализовать методику тестирования, модифицировать исходные данные, а в некоторых случаях — и сами алгоритмы. Как следствие, эмпирические результаты, представленные в разных статьях, оказываются несопоставимыми, даже если тестирование проводилось на одних и тех задачах (как правило, из репозитория UCI).
- В системах с открытым кодом WEKA, R невозможно использовать коммерческие алгоритмы. В то же время, их владельцы вполне могли бы предоставлять их для тестирования, которое не предполагает извлечения коммерческой выгоды. Как раз наоборот, сами владельцы получат выгоду от рекламы, разумеется, если их алгоритм действительно работает хорошо. Однако предоставление коммерческих алгоритмов для целей тестирования наталкивается на технические и юридические сложности. «Полигон» решает эти проблемы, поскольку алгоритмы остаются «на территории» владельца, и владелец имеет возможность ограничивать доступ к алгоритму.
- Нет никаких ограничений на язык программирования, используемый для реализации алгоритмов. WEKA допускает только Java, что снижает скорость выполнения алгоритмов и затрудняет перенос в систему готовых алгоритмов, написанных на других языках.
- К настоящему времени сложилась де факто стандартная методика тестирования, основанная на T×N-кратном скользящем контроле. «Полигон» существенно расширяет эту методику. Вычисляется не только средняя ошибка на контрольных данных, но и масса других показателей, с разных сторон характеризующих поведение алгоритма.
Разработка системы
Разработка системы инициирована осуществляется при поддержке РФФИ (проект № 07-07-00372).
| {{{1}}} |
