Когда сегодня важен «Ближайший сосед»?

В 1999 году Beyer et al. спросил, когда смысл "Ближайший сосед"?

Существуют ли лучшие способы анализа и визуализации влияния плоскостности расстояний на поиск NN с 1999 года?

Предоставляет ли [данный] набор данных значимые ответы на проблему 1-NN? Проблема 10-НН? Проблема 100-НН?

Как бы вы, эксперты, подошли к этому вопросу сегодня?

Изменения: понедельник, 24 января:

Как насчет «расстояния белого» как более короткого названия для «плоскостности расстояния с увеличивающимся измерением»?

Простой способ взглянуть на «дистанционное исчезновение» - это запустить 2-NN и построить расстояния до ближайшего соседа и второго ближайшего соседа. График ниже показывает dist ₁ и dist ₂ для диапазона кластеров и размеров по Монте-Карло. Этот пример показывает довольно хороший контраст расстояния для масштабированной абсолютной разности | dist ₂ - dist ₁ |. (Относительные различия | dist ₂ / dist ₁ | → 1 при измерении → ∞, поэтому становятся бесполезными.)

То, следует ли использовать абсолютные или относительные ошибки в данном контексте, зависит, конечно, от «реального» присутствующего шума: трудно.

Предложение: всегда бегать 2-нн; 2 соседа полезны, когда они рядом, и полезны, когда нет.

введите описание изображения здесь

machine-learning k-nearest-neighbour Денис
источник

Бейер и соавт. Похоже, что мы рассматриваем немного другой аспект проблемы NN. Но для (двоичной) классификации в мягких условиях классическим результатом является то, что классификация 1-NN в худшем случае вдвое увеличивает вероятность ошибки байесовского (т. Е. Оптимального) классификатора асимптотически. Другими словами, первый ближайший сосед содержит «как минимум половину информации» о метке цели, как это делает лучший классификатор. В этом смысле 1-NN кажется весьма актуальным. (Подробнее см. Cover & Hart (1967). Я удивлен, что Бейер и др. Не цитирует это.)

кардинал

@cardinal, границы Cover-Hart, кажется, вообще не зависят от измерения, как вы говорите, другой аспект?

Денис

да, я верю, что это правда, и это было, по большей части, моей целью поднять это. 1-NN кажется довольно уместным в этом смысле, т. Е. Тот факт, что он работает (так) хорошо (теоретически) равномерно в измерении пространства признаков, кажется, помогает ему стоять самостоятельно, независимо от поведения ближайшего и самые дальние соседи находятся в большом пространстве. Это заставляет меня задуматься, знал ли Бейер об этом (классическом) результате.

кардинал

@cardinal Верхняя часть страницы 24 в «Обложке и Харте» выглядит как место, где проблема может возникнуть в их доказательстве, на этапе, когда Обложка и Харт утверждают, что каждый RV x \ in X обладает свойством, которое имеет каждая открытая сфера вокруг x ненулевая мера. Если мы рассмотрим геометрию гиперсферы, то увидим, что объем внутренней части гиперсферы уменьшается с увеличением размерности, поэтому в пределе открытый шар около x содержит только x внутри. Альтернативно, через SLLN, iid RVs x в метрическом пространстве X все лежат на поверхности гиперсферы с вероятностью один.

Боб Даррант

См. Также метрики L1 или L.5 для кластеризации .

Денис

Ответы:

У меня нет полного ответа на этот вопрос, но я могу дать частичный ответ на некоторые аналитические аспекты. Предупреждение: я работал над другими проблемами, начиная с первой статьи ниже, поэтому очень вероятно, что есть и другие хорошие вещи, о которых я не знаю.

Во-первых, я думаю, что стоит отметить, что, несмотря на название их статьи «Когда имеет значение« ближайший сосед »», Бейер и др. Фактически ответили на другой вопрос, а именно, когда NN не имеет смысла. Мы доказали обратное к их теореме при некоторых дополнительных мягких предположениях о размере выборки в статье «Когда ближайший сосед» имеет смысл: обратная теорема и следствия. Журнал Сложности, 25 (4), август 2009, с. 385-397.и показал, что существуют ситуации, когда (в теории) концентрация расстояний не возникает (мы приводим примеры, но, по сути, число нешумных элементов должно расти с размерностью, поэтому, конечно, они редко возникают на практике). Ссылки 1 и 7, цитируемые в нашей статье, дают некоторые примеры способов, которыми концентрация расстояния может быть уменьшена на практике.

В статье моего руководителя, Ата Кабана, рассматривается вопрос о том, сохраняются ли эти проблемы концентрации на расстоянии, несмотря на применение методов уменьшения размерности, в разделе «Сведения о концентрации на расстоянии некоторых методов сокращения данных». Распознавание образов. Том 44, выпуск 2, февраль 2011 г., с.265-277. , Там тоже есть хорошая дискуссия.

$k$

Боб Даррант
источник

Спасибо Боб, +1. Смежный вопрос, будет ли у вас практическое правило для выбора значения дробно-метрической q (или я должен задать это как отдельный вопрос)?

Денис

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

q = 1 / p

$q=1/p$

p > 1

$p>1$

p

$p$

l_{0}

$l_0$

p = 1

$p=1$

l_{1}

$l_{1}$

l_{q = 1 / p}

$l_{q=1/p}$

p > 1

$p>1$

p

$p$

\sum | a_{j} - b_{j} |^{q}

$\sum |a_j - b_j|^q$

1 / q

$1/q$

< q <

$< q <$

ℓ_{p}

$\ell_{p}$

С таким же успехом вас может заинтересовать анализ компонентов окрестностей, выполненный Goldberger et al.

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

В качестве побочного эффекта (ожидаемое) число соседей определяется из данных.

bayerj
источник

Спасибо, Байер. Кажется, что «дистанционное обучение метрикам» находится на подъеме - scholar.goo имеет 50 названий с 2008 года. Но это бума бума или реальное использование? Сноска, код для nca гласит: «итерации ... не менее 100000 для достижения хороших результатов». Сноска 2, большая часть работы по дистанционному метрическому обучению, кажется, моделирует расстояние Махаланобиса; Вы знали бы о других моделях расстояния?

Денис

У меня разный опыт работы с NCA - он обычно довольно быстро сходится для меня. Оформление заказа «Сокращение размерности посредством изучения инвариантного отображения» от LeCun и «Хэширование минимальных потерь для компактных двоичных кодов» от Norouzi.

Bayerj