Skip to content
Назад к результатам поиска

Активное обучение с K-ближайшими соседями (K-Nearest Neighbors, KNN)

Автор метода
Settles, B. (active learning framework); Fix & Hodges (KNN base)
Год
1951–2010
Тип
Active learning with KNN base learner
Семейство
Machine learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Активное обучение с K-ближайшими соседями сочетает инстанс-ориентированное предсказание KNN с итеративной стратегией запросов, которая отбирает наиболее информативные неразмеченные примеры для аннотирования.

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

Интуиция метода

KNN классифицирует точку, рассматривая её k ближайших размеченных соседей и применяя мажоритарное голосование. Когда эти соседи почти поровну распределены между классами, модель испытывает подлинную неуверенность — и именно эта неуверенность указывает, какой неразмеченный пример будет наиболее ценным для разметки. Активное обучение использует этот сигнал: на каждой итерации алгоритм находит неразмеченный пример, окрестность которого наиболее равномерно разделена, запрашивает у оракула его метку, добавляет его в набор размеченных данных и повторяет процесс. В результате усилия по разметке концентрируются вблизи границ принятия решений, где новые метки дают наибольший прирост знаний.

История

Классификатор K-ближайших соседей берет свое начало в работе Fix и Hodges (1951) и был формализован Cover и Hart (1967). Активное обучение как принципиальная структура было систематически рассмотрено Burr Settles (2010), который описал выборку по неопределенности из пула, запрос-по-комитету и стратегии с взвешиванием по плотности. KNN фигурировал в качестве базового ученика в бенчмарках активного обучения из пула по крайней мере с основополагающей работы Cohn, Atlas и Ladner (1994), ценимый за его прозрачный сигнал неопределенности и нулевую стоимость переобучения на каждой итерации.

Когда применять

Используйте активное обучение с KNN, когда размеченные данные редки или дороги в получении, неразмеченных экземпляров много, размерность признакового пространства умеренная, и ожидается, что граница принятия решений будет локально гладкой. Это особенно практично на ранних этапах классификационных проектов, где разметку необходимо нормировать. Избегайте этого, когда набор данных имеет очень высокую размерность (метрики расстояния KNN деградируют в высоких размерностях, проклятие размерности), когда пул размеченных данных уже велик (достаточно пассивного KNN), когда требуется низкая задержка предсказания в масштабе (предсказание KNN имеет сложность O(n) по размеру размеченного набора) или когда бюджет разметки настолько мал, что оценки окрестности ненадежны.

Ограничения и замечания

  • Стоимость предсказания линейно зависит от размера размеченного набора, что замедляет инференс по мере роста пула итераций.
  • Оценка неопределенности на основе расстояния резко деградирует в пространствах высокой размерности из-за проклятия размерности.
  • Потолок точности KNN ниже, чем у ансамблевых методов; активная стратегия не может компенсировать ограниченную мощность базового ученика.
  • Чувствителен к выбору k и метрики расстояния; плохие значения по умолчанию приводят к ненадежным оценкам неопределенности.
  • Все размеченные точки хранятся в памяти; большие бюджеты приводят к высокому потреблению памяти.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Непараметрический и свободный от предположений: не требуется никаких предположений о распределении данных.
  • Оценка неопределенности естественна и интерпретируема — она напрямую отражает разделение голосов среди ближайших соседей.
  • Ленивое обучение означает отсутствие затрат на переобучение на каждой итерации; расширенный размеченный набор является обновленной моделью.
  • Эффективен при концентрации меток вблизи границ принятия решений, обеспечивая хорошее разрешение границы при малом количестве аннотаций.
  • Хорошо работает на табличных данных умеренной размерности как с непрерывными, так и с бинарными признаками.

Применение

  • Аннотирование медицинских записей или изображений, где время экспертной разметки ограничено, а границы принятия решений локально гладкие.
  • Классификация текстов или документов с небольшими размеченными корпусами и обильными неразмеченными документами с использованием расстояний на основе вложений.
  • Задачи обнаружения неисправностей датчиков и промышленных систем, где только часть событий может быть проверена вручную.
  • Экологические обследования, где полевое подтверждение меток видов дорого и локально сгруппировано.
  • Прототипы классификаторов на ранних стадиях перед переходом к модели с большей мощностью после сбора достаточного количества меток.

Как это работает

Как это работает

1

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

2

Классификатор KNN подгоняется на текущем размеченном наборе с использованием выбранного k и метрики расстояния (обычно евклидово или косинусное). Поскольку KNN является ленивым учеником и хранит все точки обучения, подгонка происходит мгновенно, но стоимость предсказания линейно зависит от размера размеченного набора — это важный фактор, поскольку пул растет с каждой итерацией.

3

Каждый неразмеченный экземпляр оценивается по критерию информативности. Выборка по разнице (margin sampling) вычисляет разрыв между долями голосов двух ведущих классов среди k соседей; выборка по энтропии (entropy sampling) вычисляет H(y-hat | x) по пропорциям всех классов. Запрашивается экземпляр с наименьшей разницей или наибольшей энтропией: x* = argmax H(y-hat | x).

Формула
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)
4

Запрошенный экземпляр отправляется оракулу — человеку-аннотатору или автоматическому механизму разметки — для получения его истинной метки. Метка добавляется в обучающий набор, а экземпляр удаляется из пула неразмеченных. Следует контролировать надежность аннотатора, поскольку зашумленные метки резко ухудшают производительность KNN вблизи границ.

5

Поскольку KNN является ленивым учеником, явное переобучение не требуется; расширенный размеченный набор немедленно формирует новую модель. Цикл запрос-оценка-метка повторяется до тех пор, пока не будет исчерпан бюджет разметки, не будет достигнут порог точности на валидационном наборе или не будет достигнуто максимальное количество итераций. Итоговая производительность оценивается на независимом отложенном тестовом наборе.

Частые ошибки

  • Ненормализация признаков перед вычислением расстояний, что приводит к доминированию признаков с высокой магнитудой в окрестности.
  • Использование тестового набора для управления или оценки выбора запросов, что представляет собой утечку данных.
  • Установка слишком малого k (k=1) вблизи границы принятия решений, что приводит к сильно варьирующимся оценкам неопределенности, не отражающим истинную неоднозначность.
  • Игнорирование дисбаланса классов в начальном наборе, что смещает ранние запросы к границам большинства классов.
  • Рассмотрение точности активного обучения как эквивалентной полностью контролируемому базовому уровню без указания используемого количества меток.

Часто задаваемые вопросы

Почему использовать KNN вместо более мощной модели в качестве базовой для активного обучения?

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

Как выбрать k для активного обучения?

Распространенный начальный диапазон — k от 5 до 15. Меньшие значения k дают более шумные оценки неопределенности; большие значения k сглаживают границу, но могут упустить тонкую неоднозначность. Выполните кросс-валидацию k на начальном размеченном наборе и корректируйте по мере роста пула размеченных данных.

Имеет ли значение масштабирование признаков?

Да, критически. Расстояние KNN доминируется признаками с высокой магнитудой, если признаки не нормализованы. Всегда применяйте масштабирование min-max или стандартизацию z-оценки перед вычислением расстояний и оценок неопределенности.

Сколько начальных размеченных примеров необходимо?

Минимум, один или два размеченных экземпляра на класс необходимы, чтобы KNN мог сформировать окрестности для всех классов. На практике 5–20 размеченных экземпляров дают более стабильные начальные оценки неопределенности; меньшее количество рискует вырождением окрестностей, которые дают неинформативные ранние запросы.

Когда следует остановить активный цикл?

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

Похожие методы

Источники

  1. Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.

    Открыть ссылку на публикацию
    Скопировано.
  2. Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.

    Открыть ссылку на публикацию
    Скопировано.