← вся теориятеория к собесу · Классический ML

kNN, SVM и наивный Байес

Зачем это спрашивают

Бустинг давно стал дефолтом для табличных данных, и именно поэтому собес любит проверить широту базы: понимаешь ли ты алгоритмы с принципиально другой механикой. kNN, SVM и наивный Байес - три разных взгляда на классификацию, и вопрос обычно звучит как «когда возьмёшь их вместо бустинга».

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

// Типовые формулировки: «в чём слабость kNN?», «что такое опорные векторы?», «почему наивный Байес работает, хотя его допущение неверно?».

kNN: не учится вовсе

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

Параметр k двигает ту самую ось между переобучением и недообучением. При k = 1 модель цепляется за каждую случайную точку, и граница между классами получается рваной. При большом k всё сглаживается так, что мелкие настоящие группы исчезают. Подбирают по валидации, обычно нечётным, чтобы голоса не разделились поровну.

// Расстояние здесь - сердце метода, поэтому масштабирование не рекомендация, а условие работы: признак в тысячах задавит признак в единицах, и «ближайшим соседом» окажется тот, кто похож по одному измерению из двадцати.

// И засада, о которой стоит знать: в пространстве большой размерности расстояния вырождаются - все точки оказываются примерно одинаково далеки друг от друга, и слово «ближайший» теряет смысл. Поэтому перед kNN размерность часто снижают.

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

SVM: граница с самым широким коридором

Через два класса можно провести бесконечно много разделяющих линий. SVM (support vector machine) выбирает ту, вокруг которой получается самый широкий пустой коридор до ближайших точек - его называют зазором. Логика такая: чем дальше граница от обоих классов, тем спокойнее она переживёт новые данные.

Отсюда красивое следствие. Границу задают только те точки, что стоят у самого края коридора, - опорные векторы. Все остальные объекты можно удалить, и граница не сдвинется ни на миллиметр. Модель получается компактной и устойчивой.

А если классы линией не разделяются вовсе? Тогда работает приём под названием kernel trick: данные как бы поднимают в пространство большей размерности, где разделить их плоскостью уже можно, а обратно в исходное пространство эта плоскость возвращается изогнутой границей. Слово «как бы» тут ключевое - новые координаты никто не вычисляет, всё делается через пересчёт расстояний.

// Ручка регуляризации называется C. Маленький C даёт широкий коридор и прощает отдельные ошибки, большой поджимает границу вплотную к данным и рискует переобучиться. Плата за силу метода - скорость: обучение растёт примерно квадратично, и миллионы строк SVM не переваривает.

опорные векторы: точки у края коридора; только они и определяют, где пройдёт граница

Наивный Байес: неправильное допущение, работающий результат

Метод считает, с какой вероятностью объект принадлежит каждому классу, и делает при этом смелое упрощение: будто признаки внутри класса друг от друга не зависят. Для текста это означает, что слова в письме появляются независимо друг от друга - утверждение откровенно ложное, слова «банковский» и «счёт» ходят парой.

И всё равно работает. Причина в том, что классификатору не нужна точная вероятность, ему нужно лишь понять, у какого класса она больше. Упрощение искажает сами числа, но порядок между классами чаще всего сохраняет. А расплата за наглость - скорость: обучение сводится к подсчёту частот и занимает секунды.

// Одна обязательная деталь: сглаживание Лапласа. Если слово ни разу не встретилось в обучении, его вероятность окажется нулём, а ноль в произведении обнулит весь класс целиком. Лечится тем, что ко всем счётчикам просто прибавляют единицу.

сглаживание Лапласа: прибавить единицу ко всем счётчикам, чтобы невиданное слово не обнулило вероятность

Как отвечать: «Когда возьмёшь kNN, SVM или наивный Байес вместо бустинга?»

Наивный Байес - когда нужен мгновенный бейзлайн на тексте: спам, тональность, всё где признаки это слова. SVM - когда признаков много, а объектов умеренно: тексты, эмбеддинги, небольшие выборки, там опорные векторы дают устойчивую границу. kNN - когда решает локальное сходство и данных немного, либо как основа рекомендаций и векторного поиска, где он и живёт в проде. Но на большой табличке я всё равно начну с бустинга: он обычно точнее и не боится объёма, а эти три беру под конкретную структуру данных, а не по умолчанию.

Каждый метод привязан к структуре данных, а не к абстрактному «когда-то полезен». И честно сказано, что дефолт всё-таки другой.

На чём валят

−kNN без масштабирования признаков: метрику расстояния начинает диктовать признак с самой крупной шкалой.
−kNN на большой выборке в проде: время предсказания растёт с числом объектов, нагрузку он не вытянет.
−SVM на миллионах строк: обучение растёт квадратично, это метод не про большие данные.
−«Наивному Байесу нужны независимые признаки»: допущение нарушено почти всегда, а метод при этом работает.
−Забыть сглаживание: одно невиданное слово обнуляет вероятность целого класса.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 14, остальные разбираются в тренажёре.

#knn_svm_bayes1 / 5
Как параметр k в kNN связан с балансом переобучения и недообучения?
A)Чем больше k, тем сложнее и рванее граница решения
B)k влияет только на скорость, но не на качество предсказаний
C)Малый k переобучается на шум, большой k сглаживает и недообучает
D)Оптимальный k равен числу классов в задаче
показать ответ и разбор
+C)Малый k переобучается на шум, большой k сглаживает и недообучает
// разбор: k=1 повторяет каждый обучающий объект, включая шумовые, — граница рваная, дисперсия высокая, это переобучение. Растёт k — предсказание усредняется по большему соседству, граница глаже, но слишком большой k размывает реальные различия классов (недообучение). k подбирают по валидации, обычно нечётным, чтобы не было ничьих в голосовании.
#knn_svm_bayes2 / 5
Почему перед kNN признаки почти всегда масштабируют?
A)Иначе признак с наибольшим размахом значений подавит вклад остальных в расстояние
B)Масштабирование ускоряет поиск ближайших соседей и снижает потребление памяти вдвое
C)kNN не работает с отрицательными значениями признаков
D)Без масштабирования kNN не сможет обучиться в принципе
показать ответ и разбор
+A)Иначе признак с наибольшим размахом значений подавит вклад остальных в расстояние
// разбор: kNN опирается на метрику расстояния (обычно евклидову). Признак в тысячах (доход) даст вклад в расстояние на порядки больше, чем признак в единицах (число детей), — соседство определит фактически один признак, а не их совокупность. Стандартизация или min-max уравнивают масштабы, чтобы все фичи влияли соразмерно. На скорость это не про то, а отрицательные значения kNN обрабатывает нормально.
#knn_svm_bayes3 / 5
Как проклятие размерности бьёт по kNN?
A)В высокой размерности признаки становятся линейно зависимыми
B)С ростом числа признаков расстояния между точками выравниваются, и «сосед» теряет смысл
C)kNN в пространстве высокой размерности автоматически переключается на манхэттенскую метрику
D)Проклятие размерности ускоряет kNN, но снижает точность
показать ответ и разбор
+B)С ростом числа признаков расстояния между точками выравниваются, и «сосед» теряет смысл
// разбор: С ростом размерности объём пространства растёт экспоненциально, точки становятся почти равноудалёнными — разница между ближайшим и дальнейшим соседом стирается. Понятие «близости», на котором держится kNN, вырождается, и голосование соседей перестаёт нести сигнал. Лечат отбором признаков или снижением размерности (PCA) до применения kNN.
#knn_svm_bayes4 / 5
Почему kNN тяжело применять на большой обучающей выборке в проде?
A)Обучение kNN на больших данных занимает часы
B)kNN на больших обучающих выборках постепенно теряет способность к обобщению
C)Предсказание требует сравнения с выборкой, стоимость растёт с её размером
D)kNN не умеет сохранять обученную модель на диск
показать ответ и разбор
+C)Предсказание требует сравнения с выборкой, стоимость растёт с её размером
// разбор: У kNN дорогой не train, а inference: каждый запрос ищет ближайших среди всех обучающих точек — наивно это линейно по размеру выборки и по числу признаков. На больших данных и высоком RPS это неприемлемо. Смягчают приближённым поиском (ANN: KD-tree, HNSW, IVF), которые жертвуют точностью соседей ради скорости.
#knn_svm_bayes5 / 5
Что оптимизирует классический SVM при построении границы?
A)Суммарное расстояние от границы до всех объектов выборки
B)Ширину зазора (margin) между классами у разделяющей границы
C)Число объектов, попавших точно на границу решения
D)Энтропию распределения классов по обе стороны границы
показать ответ и разбор
+B)Ширину зазора (margin) между классами у разделяющей границы
// разбор: SVM ищет гиперплоскость с максимальным зазором — наибольшим расстоянием до ближайших объектов классов. Именно эти ближайшие точки (опорные векторы) и определяют границу, остальные на неё не влияют. Широкий зазор даёт лучшую обобщающую способность. При неразделимых данных вводят мягкий зазор, допускающий ошибки со штрафом.

дальше

Теорию прочитали. Навык ставится повторением

В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.

Открыть тренажёр Вся тема: Классический ML