Узнайте, как работают алгоритмы перцептрона и что за ними стоит интуиция.

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

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

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

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

Перцептрон

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

# 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 θ, θ₀

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

Конвергенция персептронов

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

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

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

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

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

# 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 + 1
return (sum_θ/counter), (sum_θ₀/counter)

Пегас

Алгоритм 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 показано обновление границы принятия решения различными алгоритмами персептрона. Обратите внимание, что данные данные линейно неразделимы, поэтому граница решения, проведенная алгоритмом перцептрона, расходится. И алгоритм среднего персептрона, и алгоритм пегаса быстро достигают сходимости. λ для алгоритма pegasos здесь использует 0,2.

Образец кода

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

Ссылка

[1]

Ф. Розенблатт, Персептрон: вероятностная модель хранения и организации информации в мозге, Psychological Review, 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