호–카샤프 알고리즘은 기계 학습에서 선형 분류기를 훈련시키기 위한 반복 절차이다. 1965년 유치 호(Yu-Chi Ho)와 랑가사미 L. 카샤프(Rangasami L. Kashyap)가 개발했으며, 특징 공간에서 클래스를 분리하는 초평면을 찾는 판별 기반 학습 방법 계열에 속한다. 초기 퍼셉트론 방식 규칙이 단지 가중치 벡터만 조정하는 것과 달리, 호–카샤프 알고리즘은 마진 벡터도 함께 조정하여 훈련 데이터가 엄격히 선형 분리 가능하지 않더라도 완화된 의미의 해가 존재하면 수렴할 수 있게 한다.
이 알고리즘은 제곱 오차 기준 함수를 최소화한다. 훈련 샘플 집합이 주어지고 각 샘플은 특징 벡터로 표현될 때, 특징 행렬과 가중치 벡터의 곱이 양의 마진 벡터와 같아지도록 하는 가중치 벡터와 마진 벡터를 찾는 것이 목표이다. 절차는 경사 하강 단계를 사용하여 마진 벡터를 업데이트하고 최소 제곱 해를 통해 가중치 벡터를 업데이트하는 과정을 번갈아 수행한다. 이러한 이중 업데이트는 각 반복에서 폐쇄형 가중치 업데이트를 제공하여 계산 효율성을 보장하고 기준 함수의 단조 감소를 보장한다.
수학적 공식화
훈련 데이터가 각각 \(d\)개의 특징을 가진 \(n\)개의 샘플로 구성되어 \(n \times d\) 행렬 \(X\)로 배열된다고 하자. 각 샘플은 두 클래스 중 하나에 속하는 것으로 레이블되며, 레이블은 +1 또는 -1로 인코딩된다. 알고리즘은 모든 성분이 양수인 마진 벡터 \(b\)와 가중치 벡터 \(w\)를 찾아 \(Xw = b\)를 만족시키려 한다. 최소화할 기준은 \(J(w, b) = \|Xw - b\|^2\)이다.
업데이트 규칙은 다음과 같다:
- \(b_{k+1} = b_k + \rho (Xw_k - b_k)\), 여기서 \(\rho\)는 학습률이며, \(b\)의 음수 성분은 양성을 유지하기 위해 0으로 설정된다.
- \(w_{k+1} = (X^T X)^{-1} X^T b_{k+1}\), 이는 현재 마진 벡터에 대한 최소 제곱 해이다.
이 두 단계 과정은 기준이 임계값 아래로 떨어지거나 최대 반복 횟수에 도달할 때까지 반복된다. 데이터가 선형 분리 가능하면 알고리즘은 해로 수렴하는 것이 보장되며, 그렇지 않으면 진동할 수 있고, 비분리 가능한 경우 수렴을 강제하기 위해 마진 벡터에 작은 양의 상수를 추가하는 것이 일반적인 관행이다.
역사적 배경
이 알고리즘은 패턴 인식과 신경망이 급속히 발전하던 1960년대 중반에 도입되었다. 유치 호와 랑가사미 L. 카샤프는 1965년 IEEE 전자 컴퓨터 거래(IEEE Transactions on Electronic Computers)에 그들의 연구를 발표했다. 당시 선형 분류기는 문자 인식 및 신호 분류와 같은 작업을 위한 주요 도구였다. 호–카샤프 알고리즘은 데이터가 완벽하게 분리 가능하지 않으면 수렴하지 못할 수 있는 퍼셉트론 학습 규칙보다 개선된 성능을 제공했다. 마진 벡터를 도입함으로써 알고리즘은 잡음이 있거나 중첩된 데이터를 처리할 수 있는 더 강력한 접근 방식을 제공했다.
이 방법은 같은 시기에 버나드 위드로와 그의 동료들이 개발한 최소 평균 제곱(LMS) 알고리즘 및 위드로-호프 규칙과 밀접한 관련이 있다. 그러나 호–카샤프 알고리즘은 마진을 명시적으로 모델링하여 더 나은 일반화를 위해 마진을 강조하는 현대 지원 벡터 머신(SVM)의 선구자 역할을 한다.
응용 및 확장
원래 형태에서 호–카샤프 알고리즘은 손글씨 숫자 분류 및 잡음 속 신호 감지와 같은 패턴 인식 문제에 적용되었다. 수십 년에 걸쳐 여러 방식으로 확장되었다:
- 비선형 확장: 커널 함수를 통해 입력을 매핑함으로써 커널화된 SVM과 유사하게 비선형 분리 가능 데이터에 적용할 수 있다.
- 정규화: \(\lambda \|w\|^2\)와 같은 페널티 항을 기준에 추가하면 일반화가 개선되고 조건이 나쁜 행렬을 처리할 수 있다.
- 다중 클래스 문제: 이진 공식은 일대다 또는 일대일 전략을 사용하여 여러 클래스로 확장할 수 있다.
- 온라인 학습: 샘플이 순차적으로 도착하는 스트리밍 데이터를 위한 변형이 개발되었다.
이러한 확장 덕분에 알고리즘은 현대 기계 학습 교육 과정에서 여전히 관련성을 유지하며, 선형 판별 분석에서 반복 최적화의 예로 자주 가르친다.
다른 방법과의 관계
호–카샤프 알고리즘은 여러 다른 학습 기법과 개념적 유사성을 공유한다. 1958년 프랭크 로젠블라트가 도입한 퍼셉트론 알고리즘도 분리 초평면을 찾지만 비분리 가능 데이터에 대한 수렴을 보장하지 않는다. 호–카샤프 알고리즘의 최소 제곱 업데이트 사용은 Adam 옵티마이저와 유사한데, 둘 다 적응적 조정을 포함하지만 Adam은 확률적 기울기를 사용하는 딥러닝을 위해 설계되었다. 대조적으로 호–카샤프 알고리즘은 결정적이며 배치 기반이다.
또 다른 관련 방법은 이완 방법으로, 마진도 조정하지만 다른 업데이트 규칙을 사용한다. 호–카샤프 알고리즘은 양의 마진을 강제하지 않고 제곱 오차를 최소화하는 최소 제곱 분류기와 자주 비교된다; 마진 제약이 호–카샤프 알고리즘의 수렴 특성을 제공하는 요소이다.
실용적 고려 사항
호–카샤프 알고리즘을 구현할 때 여러 실용적 문제가 발생한다. \((X^T X)^{-1}\)의 계산은 큰 \(d\)에 대해 비용이 많이 들 수 있으며, 특징이 중복되면 행렬이 특이 행렬일 수 있다. 이러한 경우 의사 역행렬 또는 정규화 기법이 사용된다. 학습률 \(\rho\)는 신중히 선택해야 한다; 너무 큰 값은 진동을 유발할 수 있고 너무 작으면 수렴이 느려진다. 일반적인 선택은 \(\rho = 1\)이며, 실제로 종종 잘 작동한다.
알고리즘은 특징의 스케일링에 민감하다. 큰 크기 특징에 의한 지배를 피하기 위해 특징을 평균 0, 분산 1로 표준화하는 것이 권장된다. 텍스트 분류와 같은 고차원 데이터의 경우 알고리즘이 과적합될 수 있으며 정규화가 필수적이다.
수십 년이 지났음에도 호–카샤프 알고리즘은 여전히 가치 있는 교육 도구로 남아 있다. 이는 최적화와 학습 사이의 상호 작용을 보여주며, 그 수렴 증명은 패턴 인식 이론의 고전적 결과이다. 현대 기계 학습 교과서는 종종 단순 퍼셉트론과 더 고급 마진 기반 분류기 사이의 다리로 이 알고리즘을 포함한다.