www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home
Занимательная история, выдающиеся люди, малоизвестные факты, находки, открытия, фальсификации. Присоединяйся!

Персептронные алгоритмы для линейной классификации

Дата публикации Aug 20, 2019

Основной алгоритм персептрона был впервые введенСсылка 1в конце 1950-х гг. Это двоичный линейный классификатор для контролируемого обучения. Идея бинарного линейного классификатора может быть описана следующим образом.

гдеИксвектор признаков,θвектор веса, иθ₀ это уклон. Функция знака используется для различенияИкскак положительный (+1) или отрицательный (-1) ярлык. Существует граница принятия решения для разделения данных с разными метками, что происходит на

Граница решения разделяет гиперплоскость на две области. Данные будут помечены как положительные в регионе, которыйθ⋅ x+θ0> 0,и быть помечены как отрицательные в регионе, которыйθ⋅ x+θ0. <0. Если все экземпляры в данных данныхлинейно отделимыйсуществуетθиθ₀ такой, что y⁽⁾ (θ⋅ x⁾ +θ0)> 0 за каждыйя-я точка данных, где y⁽⁾ Это ярлык.

Рисунок 1 иллюстрирует вышеупомянутые концепции с двумерным случаем, когдаИксзнак равноИксИкс₂] ᵀ,θзнак равноθθAnd] иθA - скаляр смещения. Обратите внимание, что границы полей связаны с регуляризацией для предотвращения переобучения данных, что выходит за рамки, обсуждаемые здесь.

Рисунок 1. Понятия бинарного линейного классификатора с двумерным случаем.

Perceptron

Один из способов найти границу решения - использовать алгоритм персептрона. Обновления алгоритма персептронаθа такжеθWhen только когда граница принятия решения неправильно классифицирует точки данных. Псевдокод алгоритма описывается следующим образом.

# Perceptron Algorithm# initialize θ and θ₀ with 0
θ = 0 (vector)
θ₀ = 0 (scalar)# totally T epoches to iterate
for t = 1 .. T do
# totally m data points
for i = 1 .. m do
# misclassify data points
if y⁽ⁱ⁾(θ ⋅ x⁽ⁱ⁾ + θ₀) ≦ 0
then
θ = θ + y⁽ⁱ⁾ ⋅ x⁽ⁱ⁾
θ₀ = θ₀ + y⁽ⁱ⁾return θ, θ₀

Алгоритм персептрона перебирает все точки данных с метками и обновлениемθа такжеθ₀ соответственно. Интуиция, лежащая в основе правила обновления, заключается в том, чтобы нажать⁾ (θ⋅ x⁾ +θCloser) ближе к положительному значению, если у⁽⁾ (θ⋅ x⁾ +θ≦) ≦ 0, так как y⁽⁾ (θ⋅ x⁾ +θ0)> 0 представляет классификациюя-годанные указывают правильно.


Сходимость перцептрона

Факторами, определяющими количество ошибок, допущенных алгоритмом персептрона, являются максимальная норма точек данных и максимальный разрыв между положительными и отрицательными точками данных. Теоремы о сходимости персептрона были доказаны вСсылка 2.При заданном наборе точек данных, которые линейно разделяются через начало координат, инициализацияθне влияет на способность алгоритма персептрона в конечном итоге сходиться.

Номер итерацииКимеет конечное значение, что означает, что после того, как точки данных линейно разделяются через начало координат, алгоритм персептрона в конечном итоге сходится независимо от начального значенияθявляется. Концепции также означают наличиеθ₀.

Однако этот алгоритм персептрона может столкнуться с проблемами сходимости, когда точки данных линейно неразделимы. Существует два варианта алгоритма персептрона для решения проблем. Один из них - алгоритм среднего персептрона, а другой - алгоритм Пегаса.


Средний персептрон

Подобно алгоритму персептрона, алгоритм среднего перцептрона использует то же правило для обновления параметров. Окончательные возвращаемые значенияθа такжеθ₀ однако возьмите среднее значение всех значенийθа такжеθ₀ в каждой итерации. Псевдокод алгоритма описывается следующим образом.

# Average Perceptron Algorithm# initialize θ, θ₀, sum_θ, sum_θ₀, and counter with 0
θ = 0 (vector)
θ₀ = 0 (scalar)
sum_θ = 0 (vector)
sum_θ₀ = 0 (scalar)
counter = 0# totally T epoches to iterate
for t = 1 .. T do
# totally m data points
for i = 1 .. m do
# misclassify data points
if y⁽ⁱ⁾(θ ⋅ x⁽ⁱ⁾ + θ₀) ≦ 0
then
θ = θ + y⁽ⁱ⁾ ⋅ x⁽ⁱ⁾
θ₀ = θ₀ + y⁽ⁱ⁾ sum_θ = sum_θ + θ
sum_θ₀ = sum_θ₀ + θ₀
counter = counter + 1return (sum_θ/counter), (sum_θ₀/counter)

Pegasos

Алгоритм Pegasos имеет гиперпараметрλ, придавая большую гибкость модели, подлежащей настройке.θобновляются независимо от того, неправильно ли классифицированы точки данных. Детали обсуждаются вСсылка 3.Псевдокод алгоритма описывается следующим образом.

# Pegasos Algorithm# initialize θ, θ₀, and counter with 0
θ = 0 (vector)
θ₀ = 0 (scalar)
counter = 0# totally T epoches to iterate
for t = 1 .. T do
# totally m data points
for i = 1 .. m do
counter = counter + 1
η = 1/√counter

if y⁽ⁱ⁾(θ⋅x⁽ⁱ⁾ + θ₀) ≦ 1
then
θ = (1 - ηλ)θ + ηy⁽ⁱ⁾⋅x⁽ⁱ⁾
θ₀ = θ₀ + ηy⁽ⁱ⁾
else
then
θ = (1 - ηλ)θ
θ₀ = θ₀return θ, θ₀

Визуализация алгоритмов персептрона

Рисунок 2. Визуализация обновления границы решения с помощью различных алгоритмов персептрон. Обратите внимание, что данные являются линейно неразделимыми, поэтому граница решения, построенная алгоритмом персептрона, расходится. И алгоритм среднего персептрона, и алгоритм Пегаса быстро достигают сходимости.λАлгоритм Пегаса использует 0,2 здесь.

Рисунок 2. Обновление границ решения с помощью различных алгоритмов персептрона. Может занять время, чтобы загрузить.

Образец кода

Пример кода, написанный в блокноте Jupyter для алгоритмов персептрона, можно найтиВот, Вы можете сами поиграть с данными и гиперпараметрами, чтобы увидеть, как работают разные алгоритмы персептрона.


Ссылка

[1]

Ф. Розенблатт, «Перцептрон: вероятностная модель для хранения и организации информации в мозге»Психологический обзор, 1958, DOI:10,1037 / h0042519

[2]

М. Мори и А. Ростамизаде, «Перцептрон ошибочные границы»Arxiv, 2013.https://arxiv.org/pdf/1305.0208.pdf

[3]

С. С.-Шварц, Ю. Сингер, Н. Сребро и А Коттер, «Пегасос: первичный оцененный субградиентный решатель для SVM»,Математическое программирование, 2010. doi:10,1007 / s10107-010-0420-4

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map