TensorTonic의 Averaged Perceptron 문제를 NumPy만으로 풀면서 정리했다. 지금까지 다뤘던 선형 회귀 로지스틱 회귀 소프트맥스 회귀는 전체 데이터에 대한 손실을 한 번에 미분해서 경사하강법으로 파라미터를 움직였고 KNN은 아예 학습이 없었다. 퍼셉트론은 또 다른 위치에 있다. 한 번에 한 점만 보고 즉시 가중치를 갱신하는 온라인 학습이다. 평균 퍼셉트론은 거기에 "학습 중 거쳐간 모든 가중치의 평균을 최종 모델로 쓴다"라는 한 줄을 더한 변형이다.

퍼셉트론 모델

퍼셉트론은 1958년 Frank Rosenblatt이 발표한 가장 오래된 분류 알고리즘 중 하나다. 모델 자체는 단순하다. 입력 $\mathbf{x} \in \mathbb{R}^d$ 를 받아 선형 결합으로 점수를 매기고 그 부호로 $\pm 1$ 을 결정한다.

\hat{y} = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b)

여기서 $\mathbf{w} \cdot \mathbf{x} + b = 0$ 이 결정 경계가 되는 초평면이고 그 양쪽이 각각 $+1$ 클래스와 $-1$ 클래스의 영역이 된다. 로지스틱 회귀가 이 점수를 시그모이드에 통과시켜 확률로 바꿨다면 퍼셉트론은 부호만 본다. 확률도 없고 손실 함수의 미분 같은 것도 등장하지 않는다.

라벨 표기에 주의할 점이 있다. 퍼셉트론은 라벨이 $\{-1, +1\}$ 이어야 알고리즘 식이 그대로 돌아간다. $\{0, 1\}$ 라벨을 쓰는 로지스틱 회귀와 다른 부분이다. 이유는 다음 섹션에서 드러난다.

마진

퍼셉트론을 이해하는 핵심 개념은 마진(margin)이다. 점 $i$ 의 부호 있는 마진을 다음으로 정의한다.

m_i = y_i (\mathbf{w} \cdot \mathbf{x}_i + b)

라벨 $y_i$ 와 점수 $\mathbf{w} \cdot \mathbf{x}_i + b$ 를 그냥 곱한 값이다. 별다른 연산이 없는데 이 한 번의 곱셈이 "맞췄는지 틀렸는지"를 부호 하나로 압축해 준다.

점수 부호	라벨 $y_i$	마진 $y_i \cdot \text{score}$	의미
$+$	$+1$	$+$	정확 분류
$-$	$-1$	$+$	정확 분류
$+$	$-1$	$-$	오분류
$-$	$+1$	$-$	오분류

라벨과 점수의 부호가 일치하면 곱이 양수가 되고 어긋나면 음수가 된다. 라벨이 $\{0, 1\}$ 이면 이 트릭이 깨진다. $y_i = 0$ 일 때 곱이 무조건 0이 되어 부호 정보가 사라지기 때문이다. $\{-1, +1\}$ 이라는 표기가 알고리즘에 본질적으로 박혀 있다.

마진의 절댓값은 "얼마나 강하게" 맞췄는지를 나타낸다. 결정 경계에서 멀리 떨어진 점은 점수의 절댓값이 크고 따라서 마진의 절댓값도 크다. 경계 위에 정확히 놓인 점은 마진이 0이다. 기하학적 의미를 살리려면 $\lVert \mathbf{w} \rVert$ 로 나눠서 정규화한 기하 마진 $\gamma = m_i / \lVert \mathbf{w} \rVert$ 을 쓰지만 퍼셉트론의 업데이트 규칙은 부호만 쓰므로 정규화 없이도 충분하다.

업데이트 규칙

마진이 $\le 0$ 인 점을 만나면 가중치를 다음과 같이 움직인다.

\mathbf{w} \leftarrow \mathbf{w} + y_i \mathbf{x}_i, \quad b \leftarrow b + y_i

이 단순한 덧셈이 왜 "정답 방향으로의 보정"이 되는지는 업데이트 직후 같은 점을 다시 봤을 때 점수가 어떻게 변하는지를 계산하면 곧바로 드러난다.

\text{score}_{\text{new}} = (\mathbf{w} + y_i \mathbf{x}_i) \cdot \mathbf{x}_i + (b + y_i) = \text{score}_{\text{old}} + y_i (\lVert \mathbf{x}_i \rVert^2 + 1)

$\lVert \mathbf{x}_i \rVert^2 + 1$ 은 항상 양수다. 따라서 점수의 변화량 $y_i (\lVert \mathbf{x}_i \rVert^2 + 1)$ 의 부호는 정답 $y_i$ 의 부호와 같다.

$y_i = +1$ 이면 점수가 커진다 ⇒ 다음번에 $+1$ 로 분류될 가능성이 높아진다
$y_i = -1$ 이면 점수가 작아진다 ⇒ 다음번에 $-1$ 로 분류될 가능성이 높아진다

한 번의 업데이트로 그 점이 즉시 올바르게 분류된다는 보장은 없다. 점수가 충분히 멀리 있던 경우엔 여러 번에 걸쳐 끌어와야 한다. 다만 매 업데이트가 정답 방향으로 단조적으로 움직인다는 것 자체가 핵심이다.

$\mathbf{w}$ 와 $b$ 가 받는 양이 다른 이유

$\mathbf{w}$ 는 $y_i \mathbf{x}_i$ 만큼 움직이고 $b$ 는 $y_i$ 만큼 움직인다. 같은 라벨인데 더해지는 값의 모양이 다르다.

점수 식을 다시 보면 이유가 분명하다.

\mathbf{w} \cdot \mathbf{x} + b = w_1 x_1 + w_2 x_2 + \cdots + w_d x_d + b \cdot 1

$\mathbf{w}$ 의 각 원소는 $\mathbf{x}$ 의 해당 원소와 곱해진 뒤 합산된다. 반면 $b$ 는 그냥 더해질 뿐 어떤 입력과도 곱해지지 않는다. 다음번 점수에 영향을 주려면 자신과 짝지어진 양에 비례하게 움직여야 한다.

	짝지어지는 양	업데이트
$w_j$	$x_{ij}$	$w_j \mathrel{+}= y_i x_{ij}$
$b$	$1$	$b \mathrel{+}= y_i \cdot 1$

$b$ 를 "항상 1인 가짜 입력에 대응하는 가중치"로 보면 두 식이 같은 패턴(짝지어진 입력에 $y_i$ 를 곱해 더하기)으로 통일된다.

기하학적으로도 깔끔하게 정리된다. $\mathbf{w}$ 를 바꾸면 결정 경계의 기울기가 변하고 $b$ 를 바꾸면 결정 경계가 평행이동한다. 두 자유도가 합쳐져야 임의의 위치와 방향의 초평면을 만들 수 있다.

왜 평균을 내는가

기본 퍼셉트론은 학습이 끝난 시점의 $\mathbf{w}, b$ 를 그대로 모델로 쓴다. 문제는 이 값이 마지막 몇 번의 업데이트에 크게 좌우된다는 것이다. 학습 막바지에 우연히 본 노이즈 데이터 하나가 결정 경계를 흔들어 놓는 일이 흔하다.

평균 퍼셉트론은 학습 중 거쳐간 모든 가중치 벡터의 평균을 최종 모델로 쓴다.

\bar{\mathbf{w}} = \frac{1}{T} \sum_{t=1}^{T} \mathbf{w}_t, \quad \bar{b} = \frac{1}{T} \sum_{t=1}^{T} b_t

여기서 $T = n \times \text{epochs}$ 는 학습 데이터를 거쳐간 총 횟수다. 업데이트가 일어났든 안 일어났든 매 스텝의 $\mathbf{w}_t, b_t$ 를 누적합에 더하고 마지막에 $T$ 로 나눈다. 이 디테일이 평균 퍼셉트론의 본질이다.

"오래 살아남은 가중치"가 큰 발언권을 갖는 메커니즘

왜 모든 스텝을 더하는가. 업데이트가 일어난 시점만 모으면 좋은 가중치와 마지막에 잠깐 등장한 가중치가 동등하게 취급된다. 매 스텝마다 더하면 그렇지 않다.

예를 들어 4스텝 학습에서

스텝	업데이트?	그 시점의 $\mathbf{w}$
1	O	$A$
2	X	$A$ (변화 없음)
3	X	$A$ (변화 없음)
4	O	$B$

매 스텝마다 합산한 평균은 $(A + A + A + B) / 4$ 다. $A$ 가 세 번 등장해 더 큰 비중을 받는다. 의미는 분명하다. $A$ 는 두 번이나 데이터를 잘 분류해서 살아남은 좋은 가중치다. 업데이트 없이 오래 살아남았다는 것 자체가 그 가중치가 학습 데이터에 잘 맞는다는 증거다. 매 스텝 합산은 이 증거를 자동으로 평균에 반영해 준다.

다르게 말하면 평균 퍼셉트론의 결과는 학습 중 본 모든 가중치 벡터의 암묵적 앙상블과 같다. 좋은 분류기일수록 더 많은 표를 행사하는 가중 투표가 평균 안에 녹아 있다. 이론적으로도 일반화 한계(generalization bound)가 기본 퍼셉트론보다 타이트하다.

NumPy 구현

import numpy as np

def averaged_perceptron(X_train, y_train, X_test, n_epochs=10):
    """
    Returns: A list of predicted labels (-1 or +1) for each test point
    """
    X_train = np.asarray(X_train, dtype=float)
    y_train = np.asarray(y_train, dtype=int)

    n_samples, n_features = X_train.shape

    w = np.zeros(n_features)
    b = 0.0

    w_sum = np.zeros(n_features)
    b_sum = 0.0

    for _ in range(n_epochs):
        for i in range(n_samples):
            score = X_train[i] @ w + b
            margin = y_train[i] * score

            if margin <= 0:
                w += y_train[i] * X_train[i]
                b += y_train[i]

            w_sum += w
            b_sum += b

    w = w_sum / (n_epochs * n_samples)
    b = b_sum / (n_epochs * n_samples)

    return [1 if x @ w + b > 0 else -1 for x in X_test]

이전 모델들에 비해 코드가 짧다. 경사하강법도 없고 손실 함수의 미분도 없다. 안쪽 루프 한 번이 "점수 계산 → 마진 → 필요시 업데이트 → 누적합"의 네 줄로 정리된다.

영 벡터 초기화

w = np.zeros(n_features)
b = 0.0

신경망에서는 가중치를 0으로 초기화하면 대칭성 문제 때문에 학습이 망가지지만 퍼셉트론은 그렇지 않다. 첫 데이터를 만나면 $\mathbf{w} \cdot \mathbf{x} + b = 0$ 이라 마진이 정확히 0이 된다. 업데이트 조건 $m_i \le 0$ 이 발동되어 무조건 업데이트가 일어나고 그 즉시 비대칭이 깨진다. 그래서 퍼셉트론은 관례적으로 영 벡터에서 출발한다.

`w_sum`은 벡터, `b_sum`은 스칼라

w_sum = np.zeros(n_features)
b_sum = 0.0

$\mathbf{w}$ 가 벡터이므로 w_sum도 같은 모양이어야 한다. w_sum = 0으로 둬도 numpy의 broadcasting이 알아서 벡터로 만들어 주긴 하지만 의도를 명확히 하는 게 안전하다.

누적합은 `if` 블록 바깥

if margin <= 0:
    w += y_train[i] * X_train[i]
    b += y_train[i]

w_sum += w
b_sum += b

w_sum += w를 if 블록 안에 넣으면 업데이트가 일어난 스텝만 더해진다. 그러면 일반 퍼셉트론과 다를 게 없어진다. 업데이트 여부와 무관하게 매 스텝 합산이 평균 퍼셉트론의 정의 그 자체이므로 들여쓰기 하나가 알고리즘을 바꾼다.

마진 조건은 $\le 0$

업데이트 조건이 $< 0$ 이 아니라 $\le 0$ 인 점을 짚어 둔다. 마진이 정확히 0이라는 것은 결정 경계 위에 점이 놓였다는 뜻이다. 이때 모델은 그 점을 어느 쪽으로 분류할지 결정할 수 없다. 학습 단계에서는 "애매하면 그냥 업데이트해서 더 확실하게 만들자"라는 의도로 0도 업데이트 대상에 포함시킨다.

예측에서는 $> 0$ 만 $+1$

return [1 if x @ w + b > 0 else -1 for x in X_test]

예측 단계에서는 반대로 $> 0$ 만 $+1$ 로 보낸다. 점수가 정확히 0인 경계 케이스는 $-1$ 로 분류된다. 이진 분류기는 모든 입력에 대해 한쪽을 골라야 하므로 어디로든 보내야 하는데 이 문제의 명세가 그렇게 정해 두었다. 부동소수점 연산에서 점수가 정확히 0이 되는 일은 드물어서 실무적 영향은 거의 없지만 자동 채점에서 엣지 케이스로 걸릴 수 있다.

학습의 $\le 0$ 과 예측의 $> 0$ 은 서로 다른 관례를 쓰는 것이고 그 자체로 모순이 아니다. 학습은 "애매하면 보정"이고 예측은 "애매하면 음성"이라는 두 정책이 분리돼 있을 뿐이다.

SVM과의 관계

퍼셉트론과 SVM은 둘 다 선형 결정 경계를 학습한다. 차이는 어떤 초평면을 고르느냐다.

퍼셉트론: 데이터를 분리하는 초평면이면 아무거나
SVM: 분리하는 초평면 중 마진이 최대인 것

업데이트 규칙에 등장하는 $y_i (\mathbf{w} \cdot \mathbf{x}_i + b)$ 는 SVM이 명시적으로 최대화하려는 양과 정확히 같은 마진이다. 퍼셉트론은 마진이 양수이기만 하면 만족하고 SVM은 그 양수를 최대로 키우려 한다. 평균 퍼셉트론은 학습 중 거쳐간 가중치를 평균 내는 과정에서 어느 정도의 마진 최대화 효과를 암묵적으로 누리고 그래서 실전에서 SVM에 견줄 만한 성능을 낸다. NLP에서 품사 태깅이나 개체명 인식 같은 작업이 딥러닝 이전 시대에 평균 퍼셉트론으로 풀렸던 배경이다.

선형 분리와 수렴

퍼셉트론에는 유명한 수렴 정리가 있다. 데이터가 선형 분리 가능하면 유한 번의 업데이트로 수렴이 보장된다. 업데이트 횟수의 상한은 $R^2 / \gamma^2$ 로 알려져 있는데 $R$ 은 데이터의 반경이고 $\gamma$ 는 최선의 분리 초평면이 갖는 기하 마진이다.

반대로 선형 분리가 불가능하면 기본 퍼셉트론은 절대 수렴하지 않는다. 영원히 업데이트가 일어나고 가중치가 진동한다. 이 경우 어디서 학습을 멈추느냐에 따라 최종 모델이 들쭉날쭉해진다.

평균 퍼셉트론은 이 비분리 상황에서도 쓸 만한 결과를 낸다. 진동하는 가중치들의 평균이 진동을 완화하기 때문이다. 수렴이 필요하다면 별도의 보장이 있는 알고리즘으로 가야 한다. 포켓 알고리즘(pocket algorithm)은 학습 중 거쳐간 가중치 중 학습 데이터에서 가장 많이 맞춘 것을 따로 보관하는 방식이고 로지스틱 회귀나 SVM은 비분리 데이터에서도 수렴이 보장된다.

다른 모델들과 나란히 보기

지금까지 다룬 모델들과 비교하면 퍼셉트론의 위치가 분명해진다.

	학습 방식	손실 함수	출력	비분리 데이터
선형 회귀	배치 경사하강법	MSE	실수	학습 가능
로지스틱	배치 경사하강법	BCE	확률 $(0, 1)$	학습 가능
소프트맥스	배치 경사하강법	Cross-Entropy	확률 분포 $K$ 차원	학습 가능
KNN	학습 없음	-	다수결	학습 가능
퍼셉트론	온라인 업데이트	0-1 (계단)	$\pm 1$	수렴 안 함
평균 퍼셉트론	온라인 + 가중치 평균	0-1	$\pm 1$	진동 완화

손실 함수가 미분 가능한 부드러운 함수(MSE, BCE, CE)에서 계단 함수로 바뀌면 경사하강법을 쓸 수 없다. 대신 "틀렸을 때만 정답 방향으로 보정한다"라는 매우 단순한 규칙으로 학습이 진행된다. 출력도 확률이 아닌 하드 라벨이다.

신경망 관점에서 보면 퍼셉트론은 계단 활성화를 가진 단일 뉴런이다. 활성화를 시그모이드로 바꾸면 로지스틱 회귀가 되고 출력을 $K$ 개로 늘려 소프트맥스를 씌우면 소프트맥스 회귀가 된다. 뉴런을 여러 층으로 쌓고 활성화를 비선형으로 두면 다층 퍼셉트론(MLP)이 되며 이것이 현대 딥러닝의 직접적인 조상이다.

마무리

이번 구현에서 남는 포인트는 네 가지다.

마진은 라벨과 점수의 곱이다. $\{-1, +1\}$ 라벨이라는 점이 부호 트릭의 본질이고 한 번의 곱셈으로 "맞췄는지"가 부호로 표현된다.
업데이트는 정답 방향으로의 보정이다. $\mathbf{w} \mathrel{+}= y_i \mathbf{x}_i$ 를 적용하면 다음 점수가 $y_i (\lVert \mathbf{x}_i \rVert^2 + 1)$ 만큼 정답 방향으로 움직인다. 한 번에 다 고치지는 못해도 반복하면 결정 경계가 수렴한다.
평균은 암묵적 앙상블이다. 매 스텝의 가중치를 누적해서 평균을 내면 오래 살아남은 가중치가 자동으로 더 큰 비중을 받는다. 마지막 업데이트의 노이즈에 흔들리지 않는다.
업데이트 여부와 무관하게 매 스텝 누적한다. w_sum += w를 if 블록 안에 두면 일반 퍼셉트론이 돼 버린다. 들여쓰기 하나가 알고리즘을 가른다.

평균 퍼셉트론은 손실 함수도 미분도 없이 "틀리면 보정하고 매 순간을 기록한다"라는 두 규칙으로 SVM에 견줄 만한 성능을 낸다. 단순함에 비해 결과가 인상적인 알고리즘이다.

이 글은 학습 내용을 AI의 도움을 받아 정리했습니다.