Я. Гудфеллоу, И. Бенджио, А. Курвилль

x
, мы ищем в обучающем наборе 
X
k
ближайших соседей 
x
, а затем возвращаем среднее соответствующих им меток 
y
. Эта 
идея работает для любого вида обучения с учителем, при условии что можно опре-
делить понятие средней метки. В случае классификации усреднять можно по уни-
тарным кодовым векторам 
c
, в которых 
c
y
= 1 и 
c
i
= 0 для всех остальных 
i
. Среднее 
по таким векторам можно интерпретировать как распределение вероятности классов. 
Алгоритм 
k
ближайших соседей, являясь непараметрическим, может достигать очень 
высокой емкости. Предположим, к примеру, что имеются задача многоклассовой 
классификации и мера производительности с бинарной функцией потерь. В таком 
случае метод одного ближайшего соседа сходится к удвоенной байесовской частоте 
ошибок, когда число обучающих примеров стремится к бесконечности. Превышение 
над байесовской ошибкой связано с тем, что мы случайным образом выбираем одного 
из равноудаленных соседей. Если число обучающих примеров бесконечно, то у всех 
тестовых точек 
x
будет бесконечно много соседей из обучающего набора на нулевом 
расстоянии. Если бы алгоритм разрешал соседям проголосовать, а не выбирал слу-
чайного соседа, то процедура сходилась бы к байесовской частоте ошибок. Высокая 
емкость алгоритма 
k
ближайших соседей позволяет получить высокую верность, если 
имеется большой обучающий набор. Но за это приходится расплачиваться высокой 
стоимостью вычислений, а при малом обучающем наборе алгоритм плохо обобща-
ется. Одно из слабых мест алгоритма 
k
ближайших соседей – неумение понять, что 
один признак является более отличительным, чем другой. Возьмем, к примеру, задачу 
регрессии, в которой 
x
∈ ℝ
100
выбирается из изотропного нормального распределения, 
но результат зависит только от переменной 
x
1
. Предположим еще, что результат по-
просту совпадает с этим признаком, т. е. 
y
= 
x
1
во всех случаях. Регрессия методом 
ближайшего соседа не сможет уловить эту простую закономерность. Ближайший со-
сед большинства точек 
x
будет определяться по большому числу признаков от 
x
2
до 
x
100
, а не только по признаку 
x
1
. Поэтому на небольшом обучающем наборе результат 
будет, по существу, случайным.
Еще один тип алгоритма обучения, также разбивающий пространство входов на 
области, каждая из которых описывается отдельными параметрами, –