Профиль компактности

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{TOCright}} '''Профиль компактности''' выборки в метрических алгоритмах [[клас...)
(дополнение)
Строка 7: Строка 7:
Имеется множество объектов <tex>X</tex> и множество имён классов <tex>Y</tex>.
Имеется множество объектов <tex>X</tex> и множество имён классов <tex>Y</tex>.
Задана [[обучающая выборка]] пар «объект—ответ»
Задана [[обучающая выборка]] пар «объект—ответ»
-
<tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \in X\times Y</tex>.
+
<tex>X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\} \in X\times Y</tex>.
Пусть на множестве объектов задана функция расстояния <tex>\rho(x,x')</tex>.
Пусть на множестве объектов задана функция расстояния <tex>\rho(x,x')</tex>.
Строка 16: Строка 16:
объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>u</tex>:
объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>u</tex>:
::<tex>\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}),</tex>
::<tex>\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}),</tex>
-
где через <tex>x_{i; u}</tex> обозначается <tex>i</tex>-й сосед объекта <tex>u</tex>.
+
где через <tex>x_{i; u}</tex> обозначается элемент обучающей выборки, который является <tex>i</tex>-м соседом объекта&nbsp;<tex>u</tex>.
Аналогичное обозначение введём и для ответа на <tex>i</tex>-м соседе:
Аналогичное обозначение введём и для ответа на <tex>i</tex>-м соседе:
<tex>y_{i; u}</tex>.
<tex>y_{i; u}</tex>.
Строка 22: Строка 22:
Рассматривается [[метод ближайшего соседа]], который относит классифицируемый объект <tex>u</tex> к тому классу <tex>y_i</tex>, которому принадлежит ближайший объект обучающей выборки <tex>x_i</tex>:
Рассматривается [[метод ближайшего соседа]], который относит классифицируемый объект <tex>u</tex> к тому классу <tex>y_i</tex>, которому принадлежит ближайший объект обучающей выборки <tex>x_i</tex>:
-
::<tex>a(u) = y_{1;u}.</tex>
+
::<tex>a(u,X^m) = y_{1;u}.</tex>
 +
 
 +
[[Изображение:ChartLib-1NNProfile.png‎|frame]]
'''Определение.'''
'''Определение.'''
Строка 36: Строка 38:
В&nbsp;сложных задачах или при неудачном выборе функции расстояния
В&nbsp;сложных задачах или при неудачном выборе функции расстояния
ближайшие объекты практически не&nbsp;несут информации о&nbsp;классах,
ближайшие объекты практически не&nbsp;несут информации о&nbsp;классах,
-
и&nbsp;профиль вырождается в&nbsp;константу, близкую к&nbsp;$0{.}5$, см.&nbsp;Рис.
+
и&nbsp;профиль вырождается в&nbsp;константу, близкую к&nbsp;0.5.
 +
 
 +
На рисунке показаны профили компактности для серии плоских модельных задач классификации с двумя классами.
 +
Чем ниже проходит начальный участок профиля,
 +
тем выше [[обобщающая способность]] метода ближайшего соседа.
== Связь с полным скользящем контролем ==
== Связь с полным скользящем контролем ==
 +
 +
Выборка <tex>X^L</tex> разбивается всевозможными <tex>N=C_L^k</tex> способами на две непересекающиеся подвыборки:
 +
<tex>X^L = X^m_n \cup X^k_n</tex>,
 +
где
 +
<tex>X^m_n</tex> — обучающая подвыборка длины&nbps;<i>m</i>,
 +
<tex>X^k_n</tex> — контрольная подвыборка длины <tex>k=L-m</tex>,
 +
<tex>n=1,\ldots,N</tex> — номер разбиения.
 +
 +
Для каждого разбиения ''n'' строится алгоритм <tex>a_n(u,X^m_n)</tex>.
 +
Функционал ''полного скользящего контроля'' (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>
 +
 +
Функционал ''полного скользящего контроля'' характеризует [[обобщающая способность|обобщающую способность]] метода ближайшего соседа
 +
'''Теорема.'''
'''Теорема.'''
 +
Справедлива формула для эффективного вычисления CCV через профиль компактности:
 +
::<tex>CCV(X^L)= \sum_{j=1}^k R(j) \Gamma(j),</tex>
 +
где <tex>\Gamma(j) = \frac{C_{L-1-j}^{m-1}}{C_{L-1}^{m}}.</tex>
 +
Комбинаторный множитель <tex>\Gamma(j)</tex> быстро убывает с ростом&nbsp;<tex>j</tex>.
 +
Поэтому для минимизации функционала CCV достаточно, чтобы при малых j профиль принимал значения, близкие к нулю.
 +
Но&nbsp;это и&nbsp;означает, что близкие объекты должны лежать преимущественно в&nbsp;одном классе.
 +
Таким образом, профиль действительно является формальным выражением [[гипотеза компактности|гипотезы компактности]].
== См. также ==
== См. также ==
Строка 50: Строка 78:
== Литература ==
== Литература ==
-
# ''Воронцов К. В.'' [www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов] // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
+
# ''Воронцов К. В.'' [http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов] // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
-
# ''Воронцов К. В.'', ''Колосков А. О.'' [www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf Профили компактности и выделение опорных объектов в метрических алгоритмах классификации] // Искусственный Интеллект. — 2006. — С. 30–33.
+
# ''Воронцов К. В.'', ''Колосков А. О.'' [http://www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf Профили компактности и выделение опорных объектов в метрических алгоритмах классификации] // Искусственный Интеллект. — 2006. — С. 30–33.
 +
# ''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:07, 22 сентября 2008

Содержание

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

Определения

Рассматривается задача классификации. Имеется множество объектов X и множество имён классов Y. Задана обучающая выборка пар «объект—ответ» X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\} \in X\times Y.

Пусть на множестве объектов задана функция расстояния \rho(x,x'). Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта x,x'.

Для произвольного объекта u расположим объекты обучающей выборки x_i в порядке возрастания расстояний до u:

\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}),

где через x_{i; u} обозначается элемент обучающей выборки, который является i-м соседом объекта u. Аналогичное обозначение введём и для ответа на i-м соседе: y_{i; u}. Каждый объект u\in X порождает свою перенумерацию выборки.

Рассматривается метод ближайшего соседа, который относит классифицируемый объект u к тому классу y_i, которому принадлежит ближайший объект обучающей выборки x_i:

a(u,X^m) = y_{1;u}.

Определение. Профиль компактности выборки X^m есть функция

R(j,X^m) = \frac1m \sum_{i=1}^L \left[ y_i \neq y_{j;x_i} \right].

Профиль компактности является формальным выражением гипотезы компактности — предположения о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных. Чем проще задача, то есть чем чаще близкие объекты оказываются в одном классе, тем сильнее «прижимается к нулю» начальный участок профиля. В сложных задачах или при неудачном выборе функции расстояния ближайшие объекты практически не несут информации о классах, и профиль вырождается в константу, близкую к 0.5.

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

Связь с полным скользящем контролем

Выборка X^L разбивается всевозможными N=C_L^k способами на две непересекающиеся подвыборки: X^L = X^m_n \cup X^k_n, где X^m_n — обучающая подвыборка длины&nbps;m, X^k_n — контрольная подвыборка длины k=L-m, n=1,\ldots,N — номер разбиения.

Для каждого разбиения n строится алгоритм a_n(u,X^m_n). Функционал полного скользящего контроля (complete cross-validation, CCV) определяется как средняя (по всем разбиениям) ошибка на контроле:

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].

Функционал полного скользящего контроля характеризует обобщающую способность метода ближайшего соседа

Теорема. Справедлива формула для эффективного вычисления CCV через профиль компактности:

CCV(X^L)= \sum_{j=1}^k R(j) \Gamma(j),

где \Gamma(j) = \frac{C_{L-1-j}^{m-1}}{C_{L-1}^{m}}.

Комбинаторный множитель \Gamma(j) быстро убывает с ростом j. Поэтому для минимизации функционала CCV достаточно, чтобы при малых j профиль принимал значения, близкие к нулю. Но это и означает, что близкие объекты должны лежать преимущественно в одном классе. Таким образом, профиль действительно является формальным выражением гипотезы компактности.

См. также

Литература

  1. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
  2. Воронцов К. В., Колосков А. О. Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. — С. 30–33.
  3. Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. — 2000.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D1%84%D0%B8%D0%BB%D1%8C_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8»
Личные инструменты