Профиль компактности
Материал из MachineLearning.
(дополнение) |
(Отбор опорных объектов (столпов) путём минимизации CCV) |
||
| Строка 21: | Строка 21: | ||
Каждый объект <tex>u\in X</tex> порождает свою перенумерацию выборки. | Каждый объект <tex>u\in X</tex> порождает свою перенумерацию выборки. | ||
| - | Рассматривается [[метод ближайшего соседа]], который относит классифицируемый объект <tex>u</tex> к тому классу | + | Рассматривается [[метод ближайшего соседа]], который относит классифицируемый объект <tex>u</tex> к тому классу, которому принадлежит ближайший к <tex>u</tex> объект обучающей выборки: |
::<tex>a(u,X^m) = y_{1;u}.</tex> | ::<tex>a(u,X^m) = y_{1;u}.</tex> | ||
| Строка 28: | Строка 28: | ||
'''Определение.''' | '''Определение.''' | ||
''Профиль компактности'' выборки <tex>X^m</tex> есть функция | ''Профиль компактности'' выборки <tex>X^m</tex> есть функция | ||
| - | ::<tex>R(j,X^m) = \frac1m \sum_{i=1}^ | + | ::<tex>R(j,X^m) = \frac1m \sum_{i=1}^m \left[ y_i \neq y_{j;x_i} \right].</tex> |
Профиль компактности является формальным выражением | Профиль компактности является формальным выражением | ||
| Строка 49: | Строка 49: | ||
<tex>X^L = X^m_n \cup X^k_n</tex>, | <tex>X^L = X^m_n \cup X^k_n</tex>, | ||
где | где | ||
| - | <tex>X^m_n</tex> — обучающая подвыборка длины& | + | <tex>X^m_n</tex> — обучающая подвыборка длины <tex>m</tex>, |
<tex>X^k_n</tex> — контрольная подвыборка длины <tex>k=L-m</tex>, | <tex>X^k_n</tex> — контрольная подвыборка длины <tex>k=L-m</tex>, | ||
<tex>n=1,\ldots,N</tex> — номер разбиения. | <tex>n=1,\ldots,N</tex> — номер разбиения. | ||
| - | Для каждого разбиения | + | Для каждого разбиения <tex>n</tex> строится алгоритм <tex>a_n(u,X^m_n)</tex>. |
Функционал ''полного скользящего контроля'' (complete cross-validation, CCV) | Функционал ''полного скользящего контроля'' (complete cross-validation, CCV) | ||
определяется как средняя (по всем разбиениям) ошибка на контроле: | определяется как средняя (по всем разбиениям) ошибка на контроле: | ||
| - | ::<tex>CCV(X^L)=\frac1N \sum_{n=1}^N \sum_{x_i \in X^k_n} \left[ a_n(x_i,X^m_n) \neq y_i \right].</tex> | + | ::<tex>CCV(X^L)=\frac1N \sum_{n=1}^N \frac1k \sum_{x_i \in X^k_n} \left[ a_n(x_i,X^m_n) \neq y_i \right].</tex> |
Функционал ''полного скользящего контроля'' характеризует [[обобщающая способность|обобщающую способность]] метода ближайшего соседа | Функционал ''полного скользящего контроля'' характеризует [[обобщающая способность|обобщающую способность]] метода ближайшего соседа | ||
| Строка 66: | Строка 66: | ||
Комбинаторный множитель <tex>\Gamma(j)</tex> быстро убывает с ростом <tex>j</tex>. | Комбинаторный множитель <tex>\Gamma(j)</tex> быстро убывает с ростом <tex>j</tex>. | ||
| - | Поэтому для минимизации функционала CCV достаточно, чтобы при малых j профиль принимал значения, близкие к нулю. | + | Поэтому для минимизации функционала CCV достаточно, чтобы при малых <tex>j</tex> профиль принимал значения, близкие к нулю. |
Но это и означает, что близкие объекты должны лежать преимущественно в одном классе. | Но это и означает, что близкие объекты должны лежать преимущественно в одном классе. | ||
Таким образом, профиль действительно является формальным выражением [[гипотеза компактности|гипотезы компактности]]. | Таким образом, профиль действительно является формальным выражением [[гипотеза компактности|гипотезы компактности]]. | ||
| + | |||
| + | == Отбор опорных объектов (столпов) путём минимизации CCV == | ||
| + | |||
| + | В статье [Воронцов, Колосков] процедура оптимизации профиля компактности положена в основу нового алгоритма выделения опорных объектов. В отличие от алгоритма СТОЛП, основанного на «жадной» стратегии последовательного добавления опорных объектов [Загоруйко], данный алгоритм работает в противоположном направлении — начиная с полной выборки, он последовательно исключает объекты. На каждом шаге выбирается тот объект, исключение которого минимизирует CCV. Оказывается, что процесс отсева объектов разбивается на две стадии. Сначала исключаются ''шумовые выбросы'', что приводит к понижению начального (левого) участка профиля и уменьшению CCV. Затем исключаются неинформативные ''периферийные объекты''. При этом изменяется правый участок профиля, а значение функционала практически не изменяется. Процесс останавливается, когда остаются объекты, исключение которых заметно увеличивает CCV, это и есть ''столпы'' или ''опорные объекты''. | ||
| + | Таким образом, возникает естественное деление обучающих объектов на шумовые, периферийные и опорные. | ||
| + | Эксперименты показывают, что при отборе объектов по критерию CCV практически нет переобучения. | ||
| + | В процессе отсева шумовых и периферийных объектов число ошибок на независимой тестовой выборке изменяется практически синхронно со значением CCV, вычисляемым по обучающей выборке. | ||
== См. также == | == См. также == | ||
| Строка 80: | Строка 87: | ||
# ''Воронцов К. В.'' [http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов] // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36. | # ''Воронцов К. В.'' [http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов] // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36. | ||
# ''Воронцов К. В.'', ''Колосков А. О.'' [http://www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf Профили компактности и выделение опорных объектов в метрических алгоритмах классификации] // Искусственный Интеллект. — 2006. — С. 30–33. | # ''Воронцов К. В.'', ''Колосков А. О.'' [http://www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf Профили компактности и выделение опорных объектов в метрических алгоритмах классификации] // Искусственный Интеллект. — 2006. — С. 30–33. | ||
| + | # ''Загоруйко Н. Г.'' Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. | ||
# ''Mullin M.'', ''Sukthankar R.'' [http://citeseer.ist.psu.edu/309025.html Complete cross-validation for nearest neighbor classifiers] // Proceedings of International Conference on Machine Learning. — 2000. | # ''Mullin M.'', ''Sukthankar R.'' [http://citeseer.ist.psu.edu/309025.html Complete cross-validation for nearest neighbor classifiers] // Proceedings of International Conference on Machine Learning. — 2000. | ||
Версия 22:36, 24 сентября 2008
|
Профиль компактности выборки в метрических алгоритмах классификации — функция , выражающая долю объектов выборки, для которых правильный ответ не совпадает с правильным ответом на
-м соседе.
Определения
Рассматривается задача классификации.
Имеется множество объектов и множество имён классов
.
Задана обучающая выборка пар «объект—ответ»
.
Пусть на множестве объектов задана функция расстояния .
Эта функция должна быть достаточно адекватной моделью сходства объектов.
Чем больше значение этой функции, тем менее схожими являются два объекта
.
Для произвольного объекта расположим
объекты обучающей выборки
в порядке возрастания расстояний до
:
где через обозначается элемент обучающей выборки, который является
-м соседом объекта
.
Аналогичное обозначение введём и для ответа на
-м соседе:
.
Каждый объект
порождает свою перенумерацию выборки.
Рассматривается метод ближайшего соседа, который относит классифицируемый объект к тому классу, которому принадлежит ближайший к
объект обучающей выборки:
Определение.
Профиль компактности выборки есть функция
Профиль компактности является формальным выражением гипотезы компактности — предположения о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных. Чем проще задача, то есть чем чаще близкие объекты оказываются в одном классе, тем сильнее «прижимается к нулю» начальный участок профиля. В сложных задачах или при неудачном выборе функции расстояния ближайшие объекты практически не несут информации о классах, и профиль вырождается в константу, близкую к 0.5.
На рисунке показаны профили компактности для серии плоских модельных задач классификации с двумя классами. Чем ниже проходит начальный участок профиля, тем выше обобщающая способность метода ближайшего соседа.
Связь с полным скользящем контролем
Выборка разбивается всевозможными
способами на две непересекающиеся подвыборки:
,
где
— обучающая подвыборка длины
,
— контрольная подвыборка длины
,
— номер разбиения.
Для каждого разбиения строится алгоритм
.
Функционал полного скользящего контроля (complete cross-validation, CCV)
определяется как средняя (по всем разбиениям) ошибка на контроле:
Функционал полного скользящего контроля характеризует обобщающую способность метода ближайшего соседа
Теорема. Справедлива формула для эффективного вычисления CCV через профиль компактности:
где
Комбинаторный множитель быстро убывает с ростом
.
Поэтому для минимизации функционала CCV достаточно, чтобы при малых
профиль принимал значения, близкие к нулю.
Но это и означает, что близкие объекты должны лежать преимущественно в одном классе.
Таким образом, профиль действительно является формальным выражением гипотезы компактности.
Отбор опорных объектов (столпов) путём минимизации CCV
В статье [Воронцов, Колосков] процедура оптимизации профиля компактности положена в основу нового алгоритма выделения опорных объектов. В отличие от алгоритма СТОЛП, основанного на «жадной» стратегии последовательного добавления опорных объектов [Загоруйко], данный алгоритм работает в противоположном направлении — начиная с полной выборки, он последовательно исключает объекты. На каждом шаге выбирается тот объект, исключение которого минимизирует CCV. Оказывается, что процесс отсева объектов разбивается на две стадии. Сначала исключаются шумовые выбросы, что приводит к понижению начального (левого) участка профиля и уменьшению CCV. Затем исключаются неинформативные периферийные объекты. При этом изменяется правый участок профиля, а значение функционала практически не изменяется. Процесс останавливается, когда остаются объекты, исключение которых заметно увеличивает CCV, это и есть столпы или опорные объекты. Таким образом, возникает естественное деление обучающих объектов на шумовые, периферийные и опорные. Эксперименты показывают, что при отборе объектов по критерию CCV практически нет переобучения. В процессе отсева шумовых и периферийных объектов число ошибок на независимой тестовой выборке изменяется практически синхронно со значением CCV, вычисляемым по обучающей выборке.
См. также
Литература
- Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
- Воронцов К. В., Колосков А. О. Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. — С. 30–33.
- Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.
- Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. — 2000.
