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