퍼셉트론

기계 학습에서 퍼셉트론은 이진 분류기의 지도 학습을 위한 알고리즘이다. 이진 분류기는 숫자 벡터로 표현된 입력이 특정 클래스에 속하는지 여부를 판별할 수 있는 함수이다. 이것은 선형 분류기의 일종으로, 즉 가중치 집합과 특징 벡터를 결합한 선형 예측 함수를 기반으로 예측을 수행하는 분류 알고리즘이다.

역사

![마크 I 퍼셉트론 기계, 퍼셉트론 알고리즘의 최초 구현체. 400픽셀 이미지를 만들기 위해 20×20 [황화카드뮴 광전지가 달린 카메라에 연결되었다. 가장 눈에 띄는 특징은 입력 특성의 다양한 조합을 설정하는 감각-연합 플러그보드이다. 오른쪽에는 적응 가중치를 구현한 가변저항기 배열이 있다.|alt=]] [[File:330-PSA-80-60 (USN 710739) (20897323365).jpg|thumb|Charles Wightman(마크 I 퍼셉트론 프로젝트 엔지니어)이 조정 중인 마크 1 퍼셉트론.[^15] 왼쪽에 감각 유닛, 중앙에 연합 유닛, 맨 오른쪽에 제어판과 반응 유닛이 있다. 감각-연합 플러그보드는 조작자 오른쪽의 닫힌 패널 뒤에 있다. 전면 패널의 글자 "C"는 감각 입력의 현재 상태를 표시한 것이다.[^16]]] 인공 신경망은 1943년 Warren McCulloch와 Walter Pitts가 *신경 활동에 내재된 관념의 논리적 계산(A logical calculus of the ideas immanent in nervous activity)*에서 발명하였다.[^17]

1957년, Frank Rosenblatt는 코넬 항공 연구소에 재직하고 있었다. 그는 IBM 704에서 퍼셉트론을 시뮬레이션하였다.[^1][^18] 이후 그는 미국 해군연구국 정보시스템부와 로마 항공개발센터로부터 자금을 확보하여 맞춤 제작 컴퓨터인 마크 I 퍼셉트론을 제작하였다. 이 기계는 1960년 6월 23일에 처음 공개 시연되었다.[^3] 이 기계는 "이 알고리즘을 사진 판독관을 위한 유용한 도구로 개발하기 위해 1963년부터 1966년까지 진행된 이전에 비밀이었던 4년간의 NPIC[미국 국립사진판독센터] 프로젝트의 일부"였다.[^2]

Rosenblatt는 1958년 논문에서 퍼셉트론의 세부 사항을 기술하였다.[^19] 그의 퍼셉트론 구성은 세 종류의 셀("유닛")으로 이루어져 있다: AI, AII, R이며, 각각 "투영", "연합", "반응"을 나타낸다. 그는 1958년 11월에 열린 최초의 국제 인공지능 심포지엄 *사고 과정의 기계화(Mechanisation of Thought Processes)*에서 발표하였다.[^20]

Rosenblatt의 프로젝트는 1959년부터 1970년까지 지속된 계약 Nonr-401(40) "인지 시스템 연구 프로그램"과, 1957년[^1]부터 1963년까지 지속된 계약 Nonr-2381(00) "프로젝트 PARA"("PARA"는 "인식 및 인지 오토마타(Perceiving and Recognition Automata)"의 약자)의 자금을 지원받았다.[^21][^22]

1959년, 국방분석연구소는 그의 연구팀에 10,000달러 계약을 수여하였다. 1961년 9월까지 해군연구국은 추가로 153,000달러 상당의 계약을 수여하였으며, 1962년에는 108,000달러가 배정되었다.[^23]

해군연구국의 연구 관리자 Marvin Denicoff는, ARPA가 아닌 해군연구국이 퍼셉트론 프로젝트에 자금을 지원한 이유는 이 프로젝트가 단기 또는 중기적으로 기술적 성과를 낼 가능성이 낮았기 때문이라고 밝혔다. ARPA의 자금 지원은 수백만 달러 규모인 반면, 해군연구국의 지원은 만 달러 규모였다. 한편, ARPA의 IPTO 책임자 J.C.R. Licklider는 1950년대에 '자기조직화', '적응적' 및 기타 생물학적 영감을 받은 방법에 관심이 있었으나, 1960년대 중반에는 퍼셉트론을 포함한 이러한 방법들을 공개적으로 비판하였다. 대신 그는 Simon과 Newell의 논리적 인공지능 접근법을 강력히 지지하였다.[^24]

마크 I 퍼셉트론 기계

퍼셉트론은 프로그램이 아닌 기계로 의도되었으며, 최초 구현은 IBM 704용 소프트웨어였지만, 이후 "프로젝트 PARA"라는 프로젝트명으로 이미지 인식을 위해 설계된 맞춤 제작 하드웨어인 마크 I 퍼셉트론으로 구현되었다.[^5] 이 기계는 현재 스미소니언 국립 미국사 박물관에 소장되어 있다.[^25]

마크 I 퍼셉트론은 세 개의 층으로 구성되었다. 한 버전은 다음과 같이 구현되었다:

• 20x20 격자로 배열된 400개의 광전지 배열로, "감각 유닛"(S-유닛) 또는 "입력 망막"이라 명명되었다. 각 S-유닛은 최대 40개의 A-유닛에 연결할 수 있다.
• 512개의 퍼셉트론으로 구성된 은닉층으로, "연합 유닛"(A-유닛)이라 명명되었다.
• 8개의 퍼셉트론으로 구성된 출력층으로, "반응 유닛"(R-유닛)이라 명명되었다. Rosenblatt는 자신이 실험한 다른 퍼셉트론 모델들과 구별하기 위해 이 3층 퍼셉트론 네트워크를 알파-퍼셉트론이라 불렀다.[^3]

S-유닛은 "퍼셉트론에서 특정한 의도적 편향을 제거하기 위해" 플러그보드(사진 참조)를 통해 난수표에 따라 무작위로 A-유닛에 연결되었다. 연결 가중치는 고정되어 있으며 학습되지 않았다. Rosenblatt는 망막이 시각 피질에 무작위로 연결되어 있다고 믿었고, 자신의 퍼셉트론 기계가 인간의 시각 인식을 닮기를 원했기 때문에 무작위 연결을 고집하였다.[^26]

A-유닛은 가변저항기로 인코딩된 조정 가능한 가중치로 R-유닛에 연결되었으며, 학습 중 가중치 업데이트는 전기 모터에 의해 수행되었다.[^4] 하드웨어 세부 사항은 조작 매뉴얼에 기술되어 있다.[^5]

![마크 I 퍼셉트론의 구성 요소. 조작 매뉴얼에서 발췌.^5 ]

1958년 미국 해군이 주관한 기자 회견에서 Rosenblatt는 퍼셉트론에 대해 발언하였고, 이는 초기 인공지능 커뮤니티에서 격렬한 논쟁을 일으켰다. Rosenblatt의 발언에 근거하여 뉴욕 타임스는 퍼셉트론이 "[해군이] 걷고, 말하고, 보고, 쓰고, 스스로를 복제하며, 자신의 존재를 인식할 수 있을 것으로 기대하는 전자 컴퓨터의 원형"이라고 보도하였다.[^6]

중앙정보국 사진부는 1960년부터 1964년까지 항공 사진에서 군사적으로 중요한 실루엣 표적(비행기, 선박 등)을 인식하기 위한 마크 I 퍼셉트론 기계의 활용을 연구하였다.[^27][^28]

신경역학의 원리(Principles of Neurodynamics) (1962)

Rosenblatt는 저서 신경역학의 원리(Principles of Neurodynamics) (1962)에서 퍼셉트론 기계의 다양한 변형에 대한 실험을 기술하였다. 이 책은 1961년 보고서의 출판본이다.[^29]

변형들 중에는 다음이 포함된다:

• 폐쇄 루프가 있을 수 있는 "교차 결합"(같은 층 내 유닛 간 연결),
• "역방향 결합"(후속 층의 유닛에서 이전 층의 유닛으로의 연결),
• 마지막 두 층에 조정 가능한 가중치가 있는 4층 퍼셉트론(따라서 진정한 다층 퍼셉트론),
• 순차 데이터 처리를 가능하게 하기 위해 퍼셉트론 유닛에 시간 지연을 도입,
• (이미지 대신) 오디오 분석. 이 기계는 해군연구국이 관리한 정부 이전 절차에 따라 1967년 코넬에서 스미소니언으로 이송되었다.[^2]

퍼셉트론즈(Perceptrons) (1969)

퍼셉트론은 처음에 유망해 보였으나, 퍼셉트론이 많은 종류의 패턴을 인식하도록 훈련될 수 없다는 것이 곧 증명되었다. 이로 인해 신경망 연구 분야는 수년간 정체되었으며, 이후 두 개 이상의 층을 가진 순방향 신경망(다층 퍼셉트론이라고도 함)이 한 개 층을 가진 퍼셉트론(단층 퍼셉트론이라고도 함)보다 더 큰 처리 능력을 가진다는 것이 인식되었다.

단층 퍼셉트론은 선형 분리 가능한 패턴만 학습할 수 있다.[^7] 계단 활성화 함수를 사용하는 분류 작업에서 단일 노드는 패턴을 형성하는 데이터 포인트를 나누는 하나의 직선을 가진다. 더 많은 노드는 더 많은 구분선을 만들 수 있지만, 그 선들은 더 복잡한 분류를 형성하기 위해 어떻게든 결합되어야 한다. 퍼셉트론의 두 번째 층, 또는 선형 노드만으로도 많은 비분리 문제를 해결하기에 충분하다.

1969년, Marvin Minsky와 Seymour Papert가 저술한 유명한 책 *퍼셉트론즈(Perceptrons)*는 이러한 종류의 네트워크가 XOR 함수를 학습하는 것이 불가능함을 보여주었다. 그들이 다층 퍼셉트론 네트워크에도 유사한 결과가 적용될 것이라고 추측했다고 흔히 잘못 알려져 있다. 그러나 이는 사실이 아니며, Minsky와 Papert 모두 다층 퍼셉트론이 XOR 함수를 생성할 수 있다는 것을 이미 알고 있었다. (자세한 정보는 퍼셉트론즈(책) 페이지를 참조하라.) 그럼에도 불구하고, 자주 잘못 인용되는 Minsky와 Papert의 저서는 신경망 연구에 대한 관심과 자금의 상당한 감소를 초래하였다. 1980년대에 신경망 연구가 부흥하기까지 10년이 더 걸렸다.[^7] 이 저서는 1987년에 "퍼셉트론즈 - 증보판"으로 재출간되었으며, 원본의 일부 오류가 표시되고 수정되었다.

후속 연구

Rosenblatt는 자금 지원이 줄어들었음에도 퍼셉트론 연구를 계속하였다. 마지막 시도는 1961년에서 1967년 사이에 제작된 음성 인식용 토버모리(Tobermory)였다.[^30] 이 기계는 방 하나를 가득 채웠다.[^8] 이 기계는 토로이달 자기 코어로 구현된 12,000개의 가중치를 가진 4개의 층으로 이루어져 있었다. 완성될 즈음에는 디지털 컴퓨터에서의 시뮬레이션이 전용 퍼셉트론 기계보다 빨라져 있었다.[^31] 그는 1971년 보트 사고로 사망하였다.

신경망 시뮬레이션 프로그램이 IBM 7090/7094용으로 작성되었으며, 문자 인식, 거품 상자 사진의 입자 궤적, 음소·고립 단어·연속 음성 인식, 화자 검증, 이미지 처리를 위한 주의 중심 메커니즘 등 다양한 패턴 인식 응용을 연구하는 데 사용되었다.[^32][^9]

![토버모리 1단계의 등축 투영도^8 ] 커널 퍼셉트론 알고리즘은 이미 1964년 Aizerman 등에 의해 도입되었다.[^33] 마진 한계 보장은 일반적인 비분리 경우에 대해 Freund와 Schapire(1998)가 처음 제시하였으며,[^10] 최근에는 Mohri와 Rostamizadeh(2013)가 이전 결과를 확장하고 새롭고 더 유리한 L1 한계를 제시하였다.[^34][^35]

퍼셉트론은 생물학적 뉴런의 단순화된 모델이다. 신경 행동을 완전히 이해하기 위해서는 생물학적 뉴런 모델의 복잡성이 종종 필요하지만, 연구에 따르면 퍼셉트론과 유사한 선형 모델이 실제 뉴런에서 관찰되는 일부 행동을 재현할 수 있다.[^36]

모든 이진 함수에 대한 결정 경계의 해 공간과 학습 행동은 다음에서 연구되었다.[^37]

정의

현대적 의미에서 퍼셉트론은 임계 함수라 불리는 이진 분류기를 학습하기 위한 알고리즘이다. 이는 입력 \mathbf{x}(실수값 벡터)를 출력값 f(\mathbf{x})(단일 이진값)로 매핑하는 함수이다:

여기서 h는 헤비사이드 계단 함수이고(입력이 > 0이면 1을 출력하고, 그렇지 않으면 0을 출력), \mathbf{w}는 실수값 가중치 벡터이며, \mathbf{w} \cdot \mathbf{x}는 내적 \sum_{i=1}^m w_i x_i이고, 여기서 m은 퍼셉트론에 대한 입력의 수이며, b는 편향이다. 편향은 결정 경계를 원점에서 이동시키며 어떤 입력값에도 의존하지 않는다.

동등하게, \mathbf{w}\cdot \mathbf{x} + b = (\mathbf{w}, b) \cdot (\mathbf{x}, 1)이므로, 편향 항 b를 또 다른 가중치 \mathbf{w}_{m+1}로 추가하고 각 입력 \mathbf{x}에 좌표 1을 추가하면, 원점을 통과하는 선형 분류기로 다음과 같이 쓸 수 있다: f(\mathbf{x}) = h(\mathbf{w} \cdot \mathbf{x})

f(\mathbf{x})의 이진값(0 또는 1)은 \mathbf{x}를 양성 또는 음성 사례로 이진 분류하는 데 사용된다. 공간적으로, 편향은 평면 결정 경계의 위치를 이동시키지만 방향은 변경하지 않는다.

신경망의 맥락에서, 퍼셉트론은 헤비사이드 계단 함수를 활성화 함수로 사용하는 인공 뉴런이다. 퍼셉트론 알고리즘은 다층 퍼셉트론과 구별하기 위해 단층 퍼셉트론이라고도 불리는데, 다층 퍼셉트론은 더 복잡한 신경망에 대한 잘못된 명칭이다. 선형 분류기로서 단층 퍼셉트론은 가장 단순한 순방향 신경망이다.

표현의 능력

정보 이론

정보 이론의 관점에서, K개의 입력을 가진 단일 퍼셉트론은 2K 비트의 정보 용량을 갖는다.[^11] 이 결과는 토머스 커버의 연구에 기인한다.[^38]

구체적으로 T(N, K)를 K 차원에서 N개의 점을 선형 분리하는 방법의 수라 하면,T(N, K)=\left{\begin{array}{cc} 2^N & K \geq N \ 2 \sum_{k=0}^{K-1}\left(\begin{array}{c} N-1 \ k \end{array}\right) & K<N \end{array}\right.K가 클 때, T(N, K)/2^N은 N \leq 2K이면 1에 매우 가깝지만, N> 2K이면 0에 매우 가깝다. 다시 말해, 하나의 퍼셉트론 유닛은 N \leq 2K일 때 N개의 점에 대한 이진 레이블의 무작위 배정을 거의 확실히 암기할 수 있지만, N> 2K일 때는 거의 확실히 암기할 수 없다.

부울 함수

이진 입력에 대해서만 작동할 때, 퍼셉트론은 선형 분리 가능한 부울 함수 또는 임계 부울 함수라고 불린다. n개의 입력에 대한 임계 부울 함수의 수열은 OEIS A000609이다. 그 값은 n=9인 경우까지만 정확히 알려져 있지만, 크기의 차수는 상당히 정확하게 알려져 있다: 상한은 2^{n^2 - n \log_2 n + O(n)}이고 하한은 2^{n^2 - n \log_2 n - O(n)}이다.[^12]

모든 부울 선형 임계 함수는 정수 가중치만으로 구현할 수 있다. 또한, 단일 정수 가중치 매개변수를 표현하는 데 필요하고 충분한 비트 수는 \Theta(n \ln n)이다.[^12]

보편 근사 정리

단일 퍼셉트론은 임의의 반공간을 분류하는 것을 학습할 수 있다. 그러나 부울 배타적 논리합 문제(유명한 "XOR 문제")와 같은 선형 분리 불가능한 벡터는 풀 수 없다.

하나의 은닉층을 가진 퍼셉트론 네트워크는 임의의 콤팩트 부분집합을 임의의 정밀도로 분류하는 것을 학습할 수 있다. 마찬가지로, 콤팩트 지지를 갖는 임의의 연속 함수를 임의의 정밀도로 근사할 수도 있다. 이것은 본질적으로 조지 시벤코와 쿠르트 호르닉의 정리의 특수한 경우이다.

결합적 국소 퍼셉트론

퍼셉트론(민스키와 패퍼트, 1969)은 다양한 부울 함수를 학습하는 데 필요한 퍼셉트론 네트워크의 종류를 연구하였다.

n개의 입력 유닛, 하나의 은닉층, 그리고 하나의 출력을 가진 퍼셉트론 네트워크를 고려하자. 이는 마크 I 퍼셉트론 기계와 유사하다. 이 네트워크는 f: 2^n \to 2 유형의 부울 함수를 계산한다. 은닉층의 각 유닛이 최대 k개의 입력 유닛에 연결되는 퍼셉트론 네트워크가 존재할 때, 그 함수를 차수 k의 결합적 국소 함수라고 한다.

정리. (정리 3.1.1): 패리티 함수는 차수 n의 결합적 국소 함수이다.

정리. (5.5절): 연결성 함수는 차수 \Omega(n^{1/2})의 결합적 국소 함수이다.

단층 퍼셉트론의 학습 알고리즘

아래는 단일 출력 유닛을 가진 단층 퍼셉트론의 학습 알고리즘 예시이다. 다중 출력 유닛을 가진 단층 퍼셉트론의 경우, 하나의 출력 유닛의 가중치는 다른 모든 유닛의 가중치와 완전히 분리되어 있으므로, 각 출력 유닛에 대해 동일한 알고리즘을 실행할 수 있다.

은닉층이 존재하는 다층 퍼셉트론의 경우, 역전파와 같은 보다 정교한 알고리즘을 사용해야 한다. 활성화 함수 또는 퍼셉트론이 모델링하는 기저 과정이 비선형인 경우, 활성화 함수가 미분 가능하기만 하면 델타 규칙과 같은 대안적 학습 알고리즘을 사용할 수 있다. 그럼에도 불구하고, 아래 단계에서 설명하는 학습 알고리즘은 비선형 활성화 함수를 가진 다층 퍼셉트론에서도 종종 작동한다.

여러 퍼셉트론이 인공 신경망으로 결합될 때, 각 출력 뉴런은 다른 모든 뉴런과 독립적으로 작동한다. 따라서 각 출력의 학습은 개별적으로 고려할 수 있다.

정의

먼저 몇 가지 변수를 정의한다: *r은 퍼셉트론의 학습률이다. 학습률은 일반적으로 1보다 작게 선택되는 양수이다. 값이 클수록 가중치 변화의 변동성이 커질 가능성이 높아진다. *D = {(\mathbf{x}1,d_1),\dots,(\mathbf{x}s,d_s)} 는 s개의 샘플로 이루어진 훈련 집합이며, 여기서: ** \mathbf{x}j는 n차원 유클리드 공간 \mathbb{R}^n에서의 j번째 입력 벡터이다. ** d_j \in {0,1}는 해당 입력에 대한 퍼셉트론의 원하는 출력 값이다. 특징의 값은 다음과 같이 나타낸다: *x{j,i} 는 j번째 훈련 입력 벡터의 i번째 특징 값이다. *x{j,0} = 1 . 가중치를 나타내기 위해: *w_i 는 가중치 벡터의 i번째 값으로, i번째 입력 특징의 값과 곱해진다. *x{j,0} = 1 이므로, w_0 은 편향 상수 b 대신 사용하는 사실상의 편향이다. \mathbf{w}의 시간 의존성을 나타내기 위해 다음을 사용한다: *w_i(t) 는 시각 t에서의 가중치 i이다.

단계

오프라인 학습의 경우, 반복 오차 \frac{1}{s} \sum_{j=1}^s |d_j - y_j(t)| 가 사용자가 지정한 오차 임계값 \gamma 보다 작아지거나, 미리 정해진 반복 횟수가 완료될 때까지 두 번째 단계를 반복할 수 있다. 여기서 s는 다시 표본 집합의 크기이다.

이 알고리즘은 단계 2b에서 매 훈련 샘플마다 가중치를 갱신하지만, d_j = y_j(t)일 때는 가중치가 변하지 않는다는 점에 유의할 수 있다.

선형 분리 가능한 데이터셋에서 단일 퍼셉트론의 수렴

단일 퍼셉트론은 선형 분류기이다. 모든 입력 벡터가 올바르게 분류된 경우에만 안정 상태에 도달할 수 있다. 훈련 집합이 선형 분리 가능하지 않은 경우, 즉 양의 예제와 음의 예제를 초평면으로 분리할 수 없는 경우, 해가 존재하지 않으므로 알고리즘은 수렴하지 않는다. 따라서 훈련 집합의 선형 분리 가능성이 사전에 알려지지 않은 경우, 아래의 훈련 변형 중 하나를 사용해야 한다. 수렴 정리에 대한 상세한 분석과 확장은 퍼셉트론(1969)의 11장에 수록되어 있다.

선형 분리 가능성은 시간 \min(O(n^{d/2}), O(d^{2n}), O(n^{d-1} \ln n)) 내에 검증 가능하며, 여기서 n은 데이터 점의 수이고 d는 각 점의 차원이다.[^39]

훈련 집합이 선형 분리 가능한 경우, 퍼셉트론은 유한 번의 오류를 범한 후 수렴이 보장된다.[^40] 이 정리는 Rosenblatt 등에 의해 증명되었다.

다음의 간단한 증명은 Novikoff (1962)에 의한 것이다. 증명의 핵심 아이디어는 가중치 벡터가 항상 음의 내적을 갖는 방향으로 유한한 양만큼 조정되므로, 가중치 벡터의 변경 횟수를 라 할 때 위로 로 유계된다는 것이다. 그러나 만족스러운 (미지의) 가중치 벡터가 존재한다면, 모든 변경이 이 (미지의) 방향으로 입력 벡터에만 의존하는 양의 양만큼 진전을 이루므로, 아래로 로도 유계된다.

퍼셉트론 알고리즘은 선형 분리 가능한 훈련 집합의 경우 어떤 해에 수렴함이 보장되지만, 어떤 해든 선택할 수 있으며, 문제가 다양한 품질의 여러 해를 허용할 수 있다.[^41] 오늘날 선형 서포트 벡터 머신으로 더 잘 알려진 최적 안정성 퍼셉트론은 이 문제를 해결하기 위해 설계되었다 (Krauth and Mezard, 1987).[^13]

퍼셉트론 순환 정리

데이터셋이 선형 분리 가능하지 않을 때, 단일 퍼셉트론이 수렴할 방법은 없다. 그러나 다음이 여전히 성립한다.[^42] 이것은 Bradley Efron에 의해 처음 증명되었다.[^43]

부울 함수 학습

x가 {-1, +1}^n, 즉 원점을 중심으로 한 n차원 초입방체의 꼭짓점에서 오고, y = \theta(x_i)인 데이터셋을 고려하자. 즉, x_i가 양인 모든 데이터 점은 y=1이고, 그 반대도 마찬가지이다. 퍼셉트론 수렴 정리에 의해, 퍼셉트론은 최대 n번의 오류를 범한 후 수렴한다.

동일한 작업을 수행하는 논리 프로그램을 작성한다면, 각 양의 예제는 좌표 중 하나가 올바른 것임을 보여주고, 각 음의 예제는 그 보수가 양의 예제임을 보여준다. 알려진 모든 양의 예제를 수집하면, 결국 하나의 좌표를 제외한 모든 좌표가 제거되며, 그 시점에서 데이터셋이 학습된다.[^14]

이 한계는 최악의 경우에 대해 점근적으로 타이트하다. 최악의 경우, 처음 제시된 예제는 완전히 새로운 것으로 n 비트의 정보를 제공하지만, 이후의 각 예제는 이전 예제와 최소한으로만 달라 각각 1비트씩 제공한다. n+1개의 예제 후에는 2n 비트의 정보가 있으며, 이는 퍼셉트론(2n 비트의 정보를 가진)에 충분하다.[^11]

그러나 예제가 균일 무작위로 제시되는 경우 기대값 면에서는 타이트하지 않은데, 첫 번째가 n 비트, 두 번째가 n/2 비트 등을 제공하여 총 O(\ln n)개의 예제만 필요하기 때문이다.[^14]

변형

래칫을 사용한 포켓 알고리즘(Gallant, 1990)은 지금까지 본 최적의 해를 "포켓에" 보관함으로써 퍼셉트론 학습의 안정성 문제를 해결한다. 포켓 알고리즘은 마지막 해가 아닌 포켓에 저장된 해를 반환한다. 이 알고리즘은 비분리 가능한 데이터 세트에도 사용할 수 있으며, 이 경우 목표는 오분류 수가 적은 퍼셉트론을 찾는 것이다. 그러나 이러한 해는 순전히 확률적으로 나타나므로 포켓 알고리즘은 학습 과정에서 점진적으로 해에 접근하지 않으며, 주어진 학습 단계 수 내에서 해가 나타난다는 보장도 없다.

맥스오버 알고리즘(Wendemuth, 1995)은 데이터 세트의 선형 분리 가능성에 대한 (사전) 지식과 무관하게 수렴한다는 점에서 "강건"하다.[^44] 선형 분리 가능한 경우, 이 알고리즘은 훈련 문제를 해결하며 — 원하는 경우 최적의 안정성(클래스 간 최대 마진)을 달성할 수도 있다. 비분리 가능한 데이터 세트에 대해서는 계산 가능한 적은 수의 오분류를 가진 해를 반환한다.[^45] 모든 경우에서 이 알고리즘은 이전 상태를 기억하거나 확률적 도약 없이 학습 과정에서 점진적으로 해에 접근한다. 분리 가능한 데이터 세트에서는 전역 최적으로, 비분리 가능한 데이터 세트에서는 국소 최적으로 수렴한다.

투표 퍼셉트론(Freund and Schapire, 1999)은 여러 개의 가중 퍼셉트론을 사용하는 변형이다. 이 알고리즘은 예제가 잘못 분류될 때마다 새로운 퍼셉트론을 시작하며, 마지막 퍼셉트론의 최종 가중치로 가중치 벡터를 초기화한다. 각 퍼셉트론에는 하나를 잘못 분류하기 전까지 올바르게 분류한 예제 수에 해당하는 또 다른 가중치가 부여되며, 최종 출력은 모든 퍼셉트론에 대한 가중 투표로 결정된다.

분리 가능한 문제에서 퍼셉트론 훈련은 클래스 간 최대 분리 마진을 찾는 것을 목표로 할 수도 있다. 소위 최적 안정성 퍼셉트론은 민오버 알고리즘(Krauth and Mezard, 1987)[^13]이나 아다트론(Anlauf and Biehl, 1989))[^46] 같은 반복적 훈련 및 최적화 방식을 통해 결정할 수 있다. 아다트론은 대응하는 이차 최적화 문제가 볼록하다는 사실을 이용한다. 최적 안정성 퍼셉트론은 커널 트릭과 함께 서포트 벡터 머신의 개념적 기초가 된다.

\alpha-퍼셉트론은 임계값 출력 유닛을 가진 고정 랜덤 가중치의 전처리 층을 추가로 사용하였다. 이를 통해 퍼셉트론은 아날로그 패턴을 이진 공간으로 투영하여 분류할 수 있었다. 실제로 충분히 높은 차원의 투영 공간에서는 패턴이 선형 분리 가능해질 수 있다.

다중 층을 사용하지 않고 비선형 문제를 해결하는 또 다른 방법은 고차 네트워크(시그마-파이 유닛)를 사용하는 것이다. 이 유형의 네트워크에서는 입력 벡터의 각 요소가 입력의 모든 쌍별 곱의 조합(2차)으로 확장된다. 이는 n차 네트워크로 확장될 수 있다.

퍼셉트론 모델의 일반화인 리셉트론은 입력 간의 비선형 상호작용을 포함한다. 단일 리셉트론은 비선형 불리언 함수를 분류할 수 있다.

그러나 최적의 분류기가 반드시 모든 훈련 데이터를 완벽하게 분류하는 것은 아니라는 점을 명심해야 한다. 실제로 데이터가 등분산 가우시안 분포에서 온다는 사전 제약이 있다면, 입력 공간에서의 선형 분리가 최적이며, 비선형 해는 과적합된 것이다.

다른 선형 분류 알고리즘으로는 위노우, 서포트 벡터 머신, 로지스틱 회귀 등이 있다.

다중 클래스 퍼셉트론

대부분의 다른 선형 분류기 훈련 기법과 마찬가지로, 퍼셉트론은 자연스럽게 다중 클래스 분류로 일반화된다. 여기서 입력 x와 출력 y는 임의의 집합에서 추출된다. 특징 표현 함수 f(x,y)는 가능한 각 입력/출력 쌍을 유한 차원의 실수값 특징 벡터로 매핑한다. 이전과 마찬가지로 특징 벡터에 가중치 벡터 w를 곱하지만, 이제 결과 점수는 여러 가능한 출력 중에서 선택하는 데 사용된다:

\hat y = \operatorname{argmax}_y f(x,y) \cdot w.

학습은 다시 예제들을 반복하면서 각각에 대한 출력을 예측하고, 예측된 출력이 목표와 일치하면 가중치를 변경하지 않고, 일치하지 않으면 변경한다. 갱신 규칙은 다음과 같다:

w_{t+1} = w_t + f(x, y) - f(x,\hat y).

이 다중 클래스 피드백 공식은 x가 실수값 벡터이고, y가 {0,1}에서 선택되며, f(x,y) = y x일 때 원래의 퍼셉트론으로 축소된다.

특정 문제에서는 y가 매우 크거나 무한한 집합에서 선택되더라도 \mathrm{argmax}_y f(x,y) \cdot w를 효율적으로 찾을 수 있도록 입력/출력 표현과 특징을 선택할 수 있다.

2002년 이후 퍼셉트론 훈련은 품사 태깅 및 구문 분석(Collins, 2002)과 같은 작업에서 자연어 처리 분야에서 널리 사용되고 있다. 또한 분산 컴퓨팅 환경에서의 대규모 기계 학습 문제에도 적용되었다.[^47]

더 읽을거리

• Aizerman, M. A. and Braverman, E. M. and Lev I. Rozonoer. 패턴 인식 학습에서 포텐셜 함수 방법의 이론적 기초. Automation and Remote Control, 25:821–837, 1964.
• Rosenblatt, Frank (1958), 퍼셉트론: 뇌에서의 정보 저장 및 조직화를 위한 확률적 모델, Cornell Aeronautical Laboratory, Psychological Review, v65, No. 6, pp. 386–408. .
• Rosenblatt, Frank (1962), 신경역학의 원리. Washington, DC: Spartan Books.
• Minsky, M. L. and Papert, S. A. 1969. 퍼셉트론. Cambridge, MA: MIT Press.
• Gallant, S. I. (1990). 퍼셉트론 기반 학습 알고리즘. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
• Olazaran Rodriguez, Jose Miguel. 신경망 연구의 역사사회학. 박사 학위 논문. University of Edinburgh, 1991.
• Mohri, Mehryar and Rostamizadeh, Afshin (2013). 퍼셉트론 오류 한계 arXiv:1305.0208, 2013.
• Novikoff, A. B. (1962). 퍼셉트론의 수렴 증명에 관하여. Symposium on the Mathematical Theory of Automata, 12, 615–622. Polytechnic Institute of Brooklyn.
• Widrow, B., Lehr, M.A., "적응형 신경망 30년: 퍼셉트론, 매달라인, 역전파," Proc. IEEE, vol 78, no 9, pp. 1415–1442, (1990).
• Collins, M. 2002. 은닉 마르코프 모델을 위한 판별 학습 방법: 퍼셉트론 알고리즘을 이용한 이론과 실험 in Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '02).
• Yin, Hongfeng (1996), 퍼셉트론 기반 알고리즘 및 분석, Spectrum Library, Concordia University, Canada

외부 링크

• 이진 NAND 함수를 학습하기 위해 MATLAB으로 구현된 퍼셉트론
• 제3장 가중 네트워크 - 퍼셉트론 및 제4장 퍼셉트론 학습 - Raúl Rojas 저 신경망 - 체계적 입문 ()
• 퍼셉트론의 역사
• 다층 퍼셉트론의 수학
• scikit-learn을 사용한 퍼셉트론 모델 적용 - https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Perceptron.html

---

참고 문헌

[^1]: Rosenblatt, Frank. 퍼셉트론—인지하고 인식하는 자동 장치. Cornell Aeronautical Laboratory

[^2]: O'Connor, Jack. 비밀 알고리즘: 인공지능과 위성 영상 초기 역사의 숨겨진 장. (2022-06-21)

[^3]: Nilsson, Nils J.. 인공지능의 탐구. Cambridge University Press. (2009)

[^4]: Bishop, Christopher M.. 패턴 인식과 기계 학습. Springer

[^5]: Hay, John Cameron. Mark I 퍼셉트론 운용자 매뉴얼 (프로젝트 PARA) /. Cornell Aeronautical Laboratory. (1960)

[^6]: Olazaran, Mikel. 퍼셉트론 논쟁의 공식 역사에 대한 사회학적 연구

[^7]: Sejnowski, Terrence J.. 딥러닝 혁명. MIT Press. (2018)

[^8]: Nagy, George. 1963. ''[https://web.archive.org/web/20231230204827/https://apps.dtic.mil/sti/trecms/pdf/AD0607459.pdf 토버모리 퍼셉트론의 시스템 및 회로 설계]''. 기술 보고서 번호

[^9]: Nagy, George. 신경망—과거와 현재. (1991년 3월)

[^10]: Freund, Y.. 퍼셉트론 알고리즘을 이용한 대마진 분류

[^11]: MacKay, David. 정보 이론, 추론 및 학습 알고리즘. [[Cambridge University Press]]. (2003-09-25)

[^12]: Šíma, Jiří. 신경망을 이용한 범용 계산: 복잡도 이론적 결과에 대한 개관. (2003-12-01)

[^13]: Krauth, W.. 신경망에서 최적 안정성을 갖는 학습 알고리즘

[^14]: Simon, Herbert A.. 인공의 과학, 제3판 재발행 및 John Laird의 새로운 서문 포함. The MIT Press. (2019-08-13)

[^15]: Hecht-Nielsen, Robert. 뉴로컴퓨팅. Addison-Wesley. (1991)

[^16]: Block, H. D.. 퍼셉트론: 뇌 기능을 위한 모델. I. (1962-01-01)

[^17]: McCulloch, W. 신경 활동에 내재한 관념의 논리적 계산. (1943)

[^18]: Rosenblatt, Frank. 퍼셉트론 시뮬레이션 실험. (1960년 3월)

[^19]: Rosenblatt, F.. 퍼셉트론: 뇌에서의 정보 저장 및 조직화를 위한 확률적 모델.. (1958)

[^20]: Frank Rosenblatt, '''퍼셉트론에서의 통계적 분리 가능성에 관한 두 가지 정리''', 사고의 기계화에 관한 심포지엄, National Physical Laboratory, Teddington, UK, 1958년 11월, vol. 1, H. M

[^21]: Rosenblatt, Frank, and CORNELL UNIV ITHACA NY. [https://apps.dtic.mil/sti/citations/trecms/AD0720416 ''인지 시스템 연구 프로그램''.] 기술 보고서, Cornell University, 72, 1971.

[^22]: Muerle, John Ludwig, and CORNELL AERONAUTICAL LAB INC BUFFALO NY. ''[https://apps.dtic.mil/sti/citations/tr/AD0633137 프로젝트 Para, 인지 및 인식 자동 장치]''. Cornell Aeronautical Laborat

[^23]: Penn, Jonathan. 지능의 발명: 20세기 중반 미국에서의 복잡한 정보 처리와 인공지능의 역사에 관하여. [object Object]. (2021-01-11)

[^24]: Guice, Jon. 논쟁과 국가: ARPA 경과 지능형 컴퓨팅. (1998)

[^25]: 퍼셉트론, Mark I

[^26]: 대화하는 네트워크: 신경망의 구술 역사. The MIT Press. (2000)

[^27]: 지각 개념에서 사진 판독까지

[^28]: Irwin, Julia A.. 인공 세계와 퍼셉트론적 객체: CIA의 20세기 중반 자동 표적 인식. (2024-09-11)

[^29]: ''[[iarchive:DTIC AD0256582/ 신경역학의 원리: 퍼셉트론과 뇌 메커니즘 이론]]'', by Frank Rosenblatt, Report Number VG-1196-G-8, Cornell Aeronautical Laboratory, published

[^30]: Rosenblatt, Frank (1962). "''[https://web.archive.org/web/20231230210135/https://apps.dtic.mil/sti/tr/pdf/AD0420696.pdf#page=163 토버모리 퍼셉트론에 대한 설명]''." Cognitive Research Progr

[^31]: Nagy, George. "신경망—과거와 현재." ''IEEE Transactions on Neural Networks'' 2.2 (1991): 316-318.

[^32]: Barker, Trevor H.. 퍼셉트론 및 유사 신경망의 시뮬레이션을 위한 컴퓨터 프로그램: 사용자 매뉴얼. Cornell University. (1966-07-14)

[^33]: Aizerman, M. A.. 패턴 인식 학습에서 포텐셜 함수 방법의 이론적 기초

[^34]: Mohri, Mehryar. 퍼셉트론 오류 한계

[^35]: [https://mitpress.mit.edu/books/foundations-machine-learning-second-edition] 기계 학습의 기초, MIT Press (제8장).

[^36]: Cash, Sydney. CA1 피라미드 뉴런에 의한 흥분성 입력의 선형 합산

[^37]: Liou, D.-R.. 퍼셉트론의 학습 행동. iConcept Press

[^38]: Cover, Thomas M.. 패턴 인식에의 응용을 포함한 선형 부등식 시스템의 기하학적 및 통계적 성질. (1965년 6월)

[^39]: 기계 학습 입문, 제3장: 퍼셉트론

[^40]: Novikoff, Albert J.. 퍼셉트론의 수렴 증명에 관하여. (1963)

[^41]: Bishop, Christopher M. 패턴 인식과 기계 학습. Springer Science+Business Media, LLC. (2006-08-17)

[^42]: Block, H. D.. 선형 부등식 시스템을 풀기 위한 반복 절차의 유계성에 관하여. (1970)

[^43]: Efron, Bradley. "비분리 상황에서의 퍼셉트론 수정 절차." ''Rome Air Dev. Center Tech. Doc. Rept'' (1964).

[^44]: Wendemuth, A.. 학습 불가능한 것의 학습

[^45]: Wendemuth, A.. 신경망을 위한 강건한 훈련 알고리즘의 성능

[^46]: Anlauf, J. K.. 에이다트론: 적응형 퍼셉트론 알고리즘

[^47]: McDonald, R.. 인간 언어 기술: 2010년 ACL 북미 지부 연례 학술대회. Association for Computational Linguistics