커널 퍼셉트론

기계학습에서, 커널 퍼셉트론은 커널 머신을 학습할 수 있는 인기 있는 퍼셉트론 학습 알고리즘의 변형이다. 즉, 보이지 않는 샘플과 훈련 샘플의 유사성을 계산하기 위해 커널 함수를 사용하는 비선형 분류기이다.이 알고리즘은 1964년에 ^[1]발명되어 최초의 커널 분류 ^[2]학습자가 되었다.

예단

퍼셉트론 알고리즘

퍼셉트론 알고리즘은 "오류 주도 학습"이라는 원리로 작동하는 온라인 학습 알고리즘입니다.교육용 샘플에서 모델을 실행한 후 감독된 신호에 대해 잘못된 분류가 발견될 때마다 모델을 업데이트하여 모델을 반복적으로 개선합니다.표준 퍼셉트론 알고리즘에 의해 학습된 모델은 선형 이진 분류기이다: 표본 벡터 $x$ 를 다음과 같이 클래스 "1" 또는 클래스 "-1"로 분류하는데 사용되는 $가중치$ $w$ 의 벡터(및 단순성을 위해 생략됨)

{hat {y}}=\operatorname {sgn}(\mathbf {w}^{\top}\mathbf {x})

여기서 0은 임의로 1 또는 마이너스 1에 매핑됩니다.()의 "모자"는 추정치를 나타냅니다.)

의사 코드에서 퍼셉트론 알고리즘은 다음과 같이 지정됩니다.

w를 길이

p

, 즉 예측 변수(피처)의 모두 0인 벡터로

초기화

합니다.

일정한 반복 횟수 또는 정지 기준이 충족될 때까지 다음 절차를 수행합니다.

각 교육

예 i

x에 대해 y { {-

1, 1

)의 실측

라벨

이_i 붙어 있습니다.

θ

=

sgn(w T i

x

)

로 하자.

ŷ y

일_i 경우 w

\leftarrow w

+

y i

x

를_i

업데이트

합니다.

커널 방식

퍼셉트론에 의해 학습된 선형 모델과 대조적으로 커널^[3] 방법은 훈련 예 $x$ 의_i 서브셋을 저장하고, 각각의 $가중치 i$ α와 관련지어 평가함으로써 $새로운$ 샘플 x $'$ 에 대한 결정을 내리는 분류기이다.

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

i

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

i

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

(

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

i ,

){ displaystyle

\

operatorname {sgn}

\

sum

_

{i}\alpha

_{

i}y_{i}K(\mathbf {x} _{i},\mathbf {x'}

\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )

여기서 $K$ 는 커널 함수입니다.형식적으로 커널 함수는 비음성 반정의 커널(머서 조건 참조)로, 예를 들어 샘플이 함수 $δ$ : $K (x,$ $x')$ · $δ(x')$ 에 의해 추가 피쳐를 포함하도록 확장되어 있는 것처럼 고차원 공간에서 샘플 간의 내적을 나타낸다.직관적으로 샘플간의 유사함수로 생각할 수 있기 때문에 커널 머신은 트레이닝 세트와의 가중치 비교에 의해 새로운 샘플의 클래스를 확립한다.각 $함수$ x $' k$ K $(x i,$ $x')$ 는 분류에서 기본 함수로 기능한다.

알고리즘.

퍼셉트론 알고리즘의 커널화된 버전을 도출하기 위해, 우리는 먼저 $무게$ 벡터 w가 $n개$ 의 훈련 샘플의 선형 조합으로 표현될 수 있다는 관찰에서 시작하여, 그것을 이중 형태로 공식화해야 한다.무게 벡터의 방정식은

\mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x}_{i

$여기$ 서_i α는 x가 잘못 분류된 $횟수$ 이며_i, $w \leftarrow$ $w$ + $y i$ $x$ 의_i 갱신을 강제한다.이것에 의해, 종래와 같이 샘플을 루프 하는 듀얼 퍼셉트론 알고리즘을 공식화해 예측을 할 수 있지만, $웨이트$ 벡터 w를 격납·갱신하는 대신에, 「실수 카운터」 $벡터α$ 를 갱신한다.또한 w:를 제거하기 위해 예측식을 다시 작성해야 합니다.

{\hat {y}&=operatorname {sgn}(\mathbf {w}^{\mathbf {x})\&=\operatorname {sgn} \left(\sum_i}^{n}\alpha_i}y_i}\mathbf {x}_right}_i}_right

이 두 방정식을 트레이닝 루프에 연결하면 듀얼 퍼셉트론 알고리즘으로 바뀝니다.

마지막으로 $샘플$ 에 대해 명시적으로 δ $(x)$ 를 계산하지 않고 임의의 커널 함수로 듀얼 퍼셉트론의 닷 $곱$ 을 대체할 수 있다.이렇게 하면 커널 퍼셉트론 ^[4]알고리즘이 생성됩니다.

α를 길이

n

의 전체 제로 벡터(훈련 샘플 수)로 초기화합니다.

일정한 반복 횟수 또는 정지 기준이 충족될 때까지 다음 절차를 수행합니다.

각 j

트레이닝 예 x,

y j

:

y

^

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

(

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

, x

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

) {

style {

hat { y } = \

operatorname

{

sgn

} \

sum

_ {

i

} \

alpha _

{

i

}

y

_ {

i

}

K

( \

mathbf

{

x } _

{ x

{\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})

} , \

mathbf

{

x

} )

）

。

" " "

y j

의 경우 오류 카운터를 증가시켜 업데이트를 수행합니다.

α j j \leftarrow α + 1

변종 및 확장 기능

위에서 설명한 바와 같이 커널 퍼셉트론의 한 가지 문제는 스파스 커널 머신을 학습하지 않는다는 것입니다.처음에는 모든 $α$ 가_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.

[1] Aizerman, M.A.;Braverman, 엠마뉴엘 M.;Rozoner, L. 나(1964년)."패턴 인식에서 잠재적인 함수 법의 이론적 기초를 배우는 것".자동화 원격 제어이다.25:821–837.귀용, 이사벨은;Boser, B;Vapnik, 블라디미르(1993년)에 영향.매우 큰 VC-dimension classifiers의 자동 용량 튜닝신경 정보 처리 시스템의 발전.CiteSeerX 10.1.1.17.7215.

[lasvm-2] Bordes, Antoine; Ertekin, Seyda; Weston, Jason; Bottou, Léon (2005). "Fast kernel classifiers with online and active learning". JMLR. 6: 1579–1619.

[3] Schölkopf, Bernhard, Smola, Alexander J., Learning with Kernels, MIT Press, Cambridge, MA, 2002.ISBN 0-262-19475-9

[shawe-4] Shawe-Taylor, John; Cristianini, Nello (2004). Kernel Methods for Pattern Analysis. Cambridge University Press. pp. 241–242.

[5] 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.

[norma-6] 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.

[7] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search