Averaged Perceptron [medium]

v1 퍼셉트론 은 마지막 $w$ 를 그대로 반환. 문제:

• 분리 가능 데이터에서도 마지막 몇 step 이 outlier 로 크게 흔들림.
• 분리 불가능 데이터에서는 영원히 발산.

Averaged Perceptron (Freund & Schapire 1999, Collins 2002): 모든 step 의 $w$ 를 평균 해서 반환. 결과적으로:

• 학습 중간 지점들이 서로 상쇄 → 안정된 경계.
• 노이즈/outlier 에 덜 민감.
• 분리 불가능 데이터에서도 "좋은 근사" 로 수렴.
• 간단한 코드 변경으로 큰 일반화 개선.

알고리즘

w = 0, b = 0
w_sum = 0, b_sum = 0
t = 0
for epoch in range(n_iter):
    for each (x, y):
        if y * (w·x + b) <= 0:
            w += y * x
            b += y
        w_sum += w
        b_sum += b
        t += 1
return w_sum / t, b_sum / t

중요: w_sum += w 는 모든 step 마다 (오분류 여부 무관). 현재 $w$ 가 오래 살아있을수록 평균에서 큰 비중.

Collins 의 효율 trick (선택)

매 step 누적 합을 저장하면 $O(NT)$ 메모리. 대신 두 쌍 $(u, \beta)$ 을 유지해 $O(D)$ 로:

w = 0, u = 0, c = 1
if 오분류:
    w += y·x
    u += c · y · x
c += 1
return w - u/c

간편성 위해 직접 누적 방식 사용.

과제

함수 fit_avg_perceptron(X, y, n_iter) 를 완성하세요.

• 반환: (w, b) — 평균된 가중치.
• y ∈ {-1, +1}.

테스트 케이스

#	이름	검증
1	반환 (w (D,), b float)
2	분리 가능 → 모두 맞음
3	노이즈 섞인 데이터에서 일반 퍼셉트론 대비 평균 테스트 정확도 ≥
4	초기 대비 w != 0
5	학습 중 오분류된 샘플 중 다수가 분리 불가능이어도 finite
6	2D 데이터에서 경계가 합리적 (정답 중심 예측 > 0)
7	n_iter 증가 시 평균이 안정화 (분산 감소)