Ученые выяснили, как определить обучаемость в универсальной онлайн-классификации

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

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

Ключевым инструментом стало новое комбинаторное дерево — Level-Constrained-Littlestone-Littlestone (LCLL), которое вместе со свойством безразличия (indifference property) определяет обучаемость.

Результаты обобщены на агностический случай и ситуацию, когда известен только стохастический процесс генерации последовательности объектов. Это расширяет понимание фундаментальных границ онлайн-обучения.

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