133
5.7.3. Другие простые алгоритмы обучения с учителем
Мы уже встречались с другим невероятностным алгоритмом обучения с учителем –
регрессией методом ближайшего соседа. В общем случае для классификации или
регрессии используется семейство методов с
k
ближайшими соседями. Будучи не-
параметрическим алгоритмом обучения, метод
k
ближайших соседей не ограничен
фиксированным числом параметров. Обычно считается, что этот алгоритм вообще
не имеет параметров, а реализует простую функцию от обучающих данных. На са-
мом деле в нем даже нет настоящего этапа обучения. Просто на этапе тестирования,
желая породить выход
y
для тестового примера
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
. Поэтому на небольшом обучающем наборе результат
будет, по существу, случайным.
Еще один тип алгоритма обучения, также разбивающий пространство входов на
области, каждая из которых описывается отдельными параметрами, –
Do'stlaringiz bilan baham: |