kNN и SVM за 6 минут

kNN и SVM сейчас редко стоят в проде как основные модели, но вопросы о них проверяют базу: метрики расстояния, масштабирование, проклятие размерности, зазор и ядра. А поиск ближайших соседей живёт в каждом рекомендательном сервисе и RAG.

kNN

Для нового объекта находим k ближайших объектов трейна и голосуем их классами (в регрессии усредняем). Можно взвешивать соседей по 1/расстояние.

import math

def knn_predict(X, y, x, k):
    idx = sorted(range(len(X)), key=lambda i: math.dist(X[i], x))[:k]
    votes = {}
    for i in idx:
        votes[y[i]] = votes.get(y[i], 0) + 1
    return max(votes, key=votes.get)

• k маленькое: рваная граница, переобучение. k большое: всё сглаживается, недообучение. k подбирают кросс-валидацией.
• Масштабирование обязательно: доход в рублях задавит возраст в годах.
• Проклятие размерности: в тысячах измерений расстояния до ближайшего и дальнего соседа почти равны. Помогают снижение размерности и обученные эмбеддинги.
• Стоимость: обучения нет, а предсказание наивно стоит O(n·d) на запрос.

Поиск соседей в проде

Для миллионов векторов используют приближённый поиск (ANN):

• HNSW: многоуровневый граф близости, высокий recall, ест память;
• IVF: поиск только в ближайших кластерах;
• Product quantization: сжатие векторов.

Инструменты: Faiss, векторные базы. Качество меряют recall@k относительно точного поиска. Векторы нормируют, тогда косинус равен скалярному произведению.

SVM

Линейный SVM ищет разделяющую гиперплоскость с максимальным зазором. В мягком варианте минимизирует:

|w|²/2 + C · Σ max(0, 1 - yᵢ(w·xᵢ + b))

• Второе слагаемое это hinge loss: ноль, если объект с правильной стороны с отступом ≥ 1.
• Опорные векторы: объекты на границе зазора, внутри него или с неверной стороны. Только они определяют решение.
• C: большой C жёстко штрафует ошибки (узкий зазор, риск переобучения), маленький разрешает их ради широкого зазора.

Ядровой трюк

Двойственная задача SVM зависит от данных только через скалярные произведения xᵢ·xⱼ. Заменив их функцией ядра K(xᵢ, xⱼ), получаем линейный классификатор в пространстве признаков высокой (даже бесконечной) размерности без явного отображения.

• RBF: K = exp(-γ|x - x'|²). Большой γ делает ядро узким, модель запоминает трейн.
• Полиномиальное: (x·x' + c)^d.

Цена: матрица ядра n×n, поэтому ядровой SVM плохо масштабируется на миллионы объектов.

SVM против логистической регрессии

Обе линейные. Логрегрессия минимизирует log loss и даёт откалиброванные вероятности. SVM минимизирует hinge loss, зависит только от опорных векторов, а вероятности получают калибровкой (Platt scaling).

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

• Запускать kNN, SVM с RBF или k-means без масштабирования.
• Считать, что большое k всегда лучше.
• Путать направление влияния C.
• Говорить, что ядро явно отображает данные в новое пространство.

Что спросят на собесе

• Как работает kNN, влияние k, почему важно масштабирование.
• Проклятие размерности.
• Как искать ближайших соседей среди миллионов векторов.
• Что такое зазор, опорные векторы, hinge loss и параметр C.
• Суть ядрового трюка и роль γ в RBF.