커널 퍼셉트론
Kernel perceptron시리즈의 일부 |
기계 학습 및 데이터 마이닝 |
---|
![]() |
기계학습에서, 커널 퍼셉트론은 커널 머신을 학습할 수 있는 인기 있는 퍼셉트론 학습 알고리즘의 변형이다. 즉, 보이지 않는 샘플과 훈련 샘플의 유사성을 계산하기 위해 커널 함수를 사용하는 비선형 분류기이다.이 알고리즘은 1964년에 [1]발명되어 최초의 커널 분류 [2]학습자가 되었다.
예단
퍼셉트론 알고리즘
퍼셉트론 알고리즘은 "오류 주도 학습"이라는 원리로 작동하는 온라인 학습 알고리즘입니다.교육용 샘플에서 모델을 실행한 후 감독된 신호에 대해 잘못된 분류가 발견될 때마다 모델을 업데이트하여 모델을 반복적으로 개선합니다.표준 퍼셉트론 알고리즘에 의해 학습된 모델은 선형 이진 분류기이다: 표본 벡터 x를 다음과 같이 클래스 "1" 또는 클래스 "-1"로 분류하는데 사용되는 가중치 w의 벡터(및 단순성을 위해 생략됨)
여기서 0은 임의로 1 또는 마이너스 1에 매핑됩니다.()의 "모자"는 추정치를 나타냅니다.)
의사 코드에서 퍼셉트론 알고리즘은 다음과 같이 지정됩니다.
- w를 길이 p, 즉 예측 변수(피처)의 모두 0인 벡터로 초기화합니다.
- 일정한 반복 횟수 또는 정지 기준이 충족될 때까지 다음 절차를 수행합니다.
- 각 교육 예i x에 대해 y { {-1, 1)의 실측 라벨이i 붙어 있습니다.
- θ = sgn(wTi x)로 하자.
- ŷ y일i 경우 w ← w + yi x를i 업데이트합니다.
- 각 교육 예i x에 대해 y { {-1, 1)의 실측 라벨이i 붙어 있습니다.
커널 방식
퍼셉트론에 의해 학습된 선형 모델과 대조적으로 커널[3] 방법은 훈련 예 x의i 서브셋을 저장하고, 각각의 가중치i α와 관련지어 평가함으로써 새로운 샘플 x'에 대한 결정을 내리는 분류기이다.
- i i ( i , \ \ __{
여기서 K는 커널 함수입니다.형식적으로 커널 함수는 비음성 반정의 커널(머서 조건 참조)로, 예를 들어 샘플이 함수 δ: K(x, x') · δ(x')에 의해 추가 피쳐를 포함하도록 확장되어 있는 것처럼 고차원 공간에서 샘플 간의 내적을 나타낸다.직관적으로 샘플간의 유사함수로 생각할 수 있기 때문에 커널 머신은 트레이닝 세트와의 가중치 비교에 의해 새로운 샘플의 클래스를 확립한다.각 함수 x' k K(xi, x')는 분류에서 기본 함수로 기능한다.
알고리즘.
퍼셉트론 알고리즘의 커널화된 버전을 도출하기 위해, 우리는 먼저 무게 벡터 w가 n개의 훈련 샘플의 선형 조합으로 표현될 수 있다는 관찰에서 시작하여, 그것을 이중 형태로 공식화해야 한다.무게 벡터의 방정식은
여기서i α는 x가 잘못 분류된 횟수이며i, w ← w + yi x의i 갱신을 강제한다.이것에 의해, 종래와 같이 샘플을 루프 하는 듀얼 퍼셉트론 알고리즘을 공식화해 예측을 할 수 있지만, 웨이트 벡터 w를 격납·갱신하는 대신에, 「실수 카운터」벡터α를 갱신한다.또한 w:를 제거하기 위해 예측식을 다시 작성해야 합니다.
이 두 방정식을 트레이닝 루프에 연결하면 듀얼 퍼셉트론 알고리즘으로 바뀝니다.
마지막으로 샘플에 대해 명시적으로 δ(x)를 계산하지 않고 임의의 커널 함수로 듀얼 퍼셉트론의 닷 곱을 대체할 수 있다.이렇게 하면 커널 퍼셉트론 [4]알고리즘이 생성됩니다.
- α를 길이 n의 전체 제로 벡터(훈련 샘플 수)로 초기화합니다.
- 일정한 반복 횟수 또는 정지 기준이 충족될 때까지 다음 절차를 수행합니다.
- 각j 트레이닝 예 x, yj:
- ^ ( , x) { hat { y } = \{} \_ { } \ { } _ { } ( \ { { x} , \ {} ) 。
- " " " yj 의 경우 오류 카운터를 증가시켜 업데이트를 수행합니다.
- αjj ← α + 1
- 각j 트레이닝 예 x, yj:
변종 및 확장 기능
위에서 설명한 바와 같이 커널 퍼셉트론의 한 가지 문제는 스파스 커널 머신을 학습하지 않는다는 것입니다.처음에는 모든 α가i 0이므로 θ를 얻기 위한 결정 함수를 평가할 때 커널 평가가 전혀 필요하지 않지만, 업데이트마다 하나의i α가 증가하므로 평가 비용이 높아진다.또한 커널 퍼셉트론을 온라인 환경에서 사용하면 0이 아닌i α의 수가 알고리즘에 제시된 예에 따라 선형적으로 증가한다.
이 문제를 다루기 위해 커널 퍼셉트론의 포겟론 변형이 제안되었습니다.α가 0이i 아닌 활성 예제를 유지하고, 사전 결정된 예산을 초과하면 활성 집합에서 예제를 제거("잊기")하고, 새로운 예제가 [5]0이i 아닌 α로 승격되면 이전 예제의 가중치를 낮추기(낮추기)한다.
커널 퍼셉트론의 또 다른 문제는 정규화되지 않아 과적합에 취약하다는 것입니다.NORMA 온라인 커널 학습 알고리즘은 [6]정규화와 함께 커널 퍼셉트론 알고리즘의 일반화라고 볼 수 있다.서포트 벡터 머신을 학습하기 위해 사용되는 순차적 최소 최적화(SMO) 알고리즘은 커널 퍼셉트론의 [6]일반화로도 간주될 수 있습니다.
또한 Freund와 Schapire의 투표된 퍼셉트론 알고리즘은 커널화된 [7]사례로 확장되어 커널 SVM에 [2]필적하는 일반화 한계를 제공한다.
레퍼런스
- ^ Aizerman, M.A.;Braverman, 엠마뉴엘 M.;Rozoner, L. 나(1964년)."패턴 인식에서 잠재적인 함수 법의 이론적 기초를 배우는 것".자동화 원격 제어이다.25:821–837.귀용, 이사벨은;Boser, B;Vapnik, 블라디미르(1993년)에 영향.매우 큰 VC-dimension classifiers의 자동 용량 튜닝신경 정보 처리 시스템의 발전.CiteSeerX 10.1.1.17.7215.
- ^ a b Bordes, Antoine; Ertekin, Seyda; Weston, Jason; Bottou, Léon (2005). "Fast kernel classifiers with online and active learning". JMLR. 6: 1579–1619.
- ^ Schölkopf, Bernhard, Smola, Alexander J., Learning with Kernels, MIT Press, Cambridge, MA, 2002.ISBN 0-262-19475-9
- ^ Shawe-Taylor, John; Cristianini, Nello (2004). Kernel Methods for Pattern Analysis. Cambridge University Press. pp. 241–242.
- ^ Dekel, Ofer; Shalev-Shwartz, Shai; Singer, Yoram (2008). "The forgetron: A kernel-based perceptron on a budget" (PDF). SIAM Journal on Computing. 37 (5): 1342–1372. CiteSeerX 10.1.1.115.568. doi:10.1137/060666998.
- ^ a b Kivinen, Jyrki; Smola, Alexander J.; Williamson, Robert C. (2004). "Online learning with kernels". IEEE Transactions on Signal Processing. 52 (8): 2165–2176. CiteSeerX 10.1.1.578.5680. doi:10.1109/TSP.2004.830991.
- ^ Freund, Y.; Schapire, R. E. (1999). "Large margin classification using the perceptron algorithm" (PDF). Machine Learning. 37 (3): 277–296. doi:10.1023/A:1007662407062.