Гипотеза компактности

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

Перейти к: навигация, поиск

Гипотеза компактности — в задачах классификации предположение о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества в пространстве объектов. Это также означает, что граница между классами имеет достаточно простую форму.

В математическом анализе и топологии есть понятие компактного множества (в некоторых случаях, например, в конечномерных пространствах, компактность равносильна замкнутости и ограниченности множества). Гипотеза компактности с этим понятием не имеет ничего общего и должна пониматься в «более бытовом» смысле этого слова.

Для формализации понятия «сходства» вводится функция расстояния или метрика \rho(x,x') в пространстве объектов X. Алгоритмы, основанные на анализе сходства объектов, часто называют метрическими, даже в тех случаях, когда функция \rho не удовлетворяет всем аксиомам метрики; в частности, далеко не всегда выполняется аксиома треугольника.

В задачах классификации введение метрики позволяет применять широкий класс метрических алгоритмов классификации. Наиболее простые из них:

Эти методы основаны на предположении, что эксперт уже построил достаточно адекватную метрику, для которой действительно выполняется гипотеза компактности. Однако выбор адекватной метрики является наиболее сложной и наименее исследованной подзадачей. В более «продвинутых» методах делается попытка автоматического подбора метрики.

Литература

  1. Аркадьев А. Г., Браверман Э. М. Обучение машины распознаванию образов. — М.: Наука, 1964.
Личные инструменты