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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (добавила Бравермана в литературу)
 
Строка 1: Строка 1:
'''Гипотеза компактности''' — в задачах классификации предположение о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества в пространстве объектов. Это также означает, что граница между классами имеет достаточно простую форму.
'''Гипотеза компактности''' — в задачах классификации предположение о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества в пространстве объектов. Это также означает, что граница между классами имеет достаточно простую форму.
-
В математическом анализе ''компактными'' называются ограниченные замкнутые множества.
+
В математическом анализе и топологии есть понятие ''компактного множества'' (в некоторых случаях, например, в конечномерных пространствах, компактность равносильна замкнутости и ограниченности множества).
-
''Гипотеза компактности'' не имеет ничего общего с этим понятием и должна пониматься в «более бытовом» смысле этого слова.
+
''Гипотеза компактности'' с этим понятием не имеет ничего общего и должна пониматься в «более бытовом» смысле этого слова.
Для формализации понятия «сходства» вводится функция расстояния или метрика <tex>\rho(x,x')</tex> в пространстве объектов&nbsp;<tex>X</tex>.
Для формализации понятия «сходства» вводится функция расстояния или метрика <tex>\rho(x,x')</tex> в пространстве объектов&nbsp;<tex>X</tex>.

Текущая версия

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

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

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

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

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

Литература

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