Выбор ответа Middle kNN и SVM обновлено
Стоимость kNN
Вопрос
В чём основная вычислительная проблема kNN в проде на миллионах объектов?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Обучения почти нет, а предсказание ищет соседей среди всех объектов; спасают индексы и ANN. kNN «ленивый»: он хранит весь трейн, а наивный поиск соседей стоит O(n·d) на каждый запрос.
Варианты ответа
- Долгое обучение: построение матрицы попарных расстояний n×n, зато предсказание затем почти мгновенное
- Обучения почти нет, а предсказание ищет соседей среди всех объектов; спасают индексы и ANNправильный ответ
- Модель хранит отдельный вектор весов на каждый объект, и при миллионах объектов он не влезает в память
- kNN не масштабируется: любые индексы вроде KD-tree или HNSW дают неверных соседей и ломают качество
Разбор
kNN «ленивый»: он хранит весь трейн, а наивный поиск соседей стоит O(n·d) на каждый запрос. Для малых размерностей помогают KD-tree и Ball-tree, для эмбеддингов приближённый поиск: HNSW, IVF, product quantization (Faiss и векторные БД). Так работают поиск похожих товаров и retrieval в RAG.
- Обучение как раз мгновенное, матрицу n×n никто не строит.
- Весов нет, хранятся данные.
- С ANN-индексами kNN отлично масштабируется.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.