CSVM 프로세서 설계 및 구현

工 學 博 士 學 位 論 文 CSVM 프로세서 설계 및 구현 Desgn and Implementaton of Concurrent Support Vector Machne Processor 2005 年 2 月 仁 荷 大 學 校 大 學 院 電 氣 工 學 科 (제어 및 시스템 전공) 魏 載 玗

工 學 博 士 學 位 論 文 CSVM 프로세서 설계 및 구현 Desgn and Implementaton of Concurrent Support Vector Machne Processor 2005 年 2 月 指 導 敎 授 李 鍾 浩 이 論 文 을 博 士 學 位 論 文 으로 提 出 함 仁 荷 大 學 校 大 學 院 電 氣 工 學 科 (제어 및 시스템 전공) 魏 載 玗

이 論 文 을 魏 載 玗 의 博 士 學 位 論 文 으로 認 定 함. 2005 年 2 月 主 審 印 副 審 印 委 員 印 委 員 印 委 員 印

요약 본 논문에서는 통합 기능을 가지는 고속의 support vector machne (SVM) 프 로세서를 개발하고 이를 여러 가지 문제에 적용하여 프로세서의 성능을 검증한 다. SVM은 통계적 학습 이론에 기반하여 최적 분류를 함으로서 뛰어난 일반 화 성능을 보이는 학습 방법이다. Local mnma에 강인하고 사용자가 초기에 설 정해 주어야 할 파라미터가 적은 장점을 가지고 있어 bonformatcs, 통신 등의 많은 분야에서 널리 사용되고 있다. SVM을 실시간 처리 등이 요구되는 문제 에 적용하기 위해서는 통합형, 고속의 SVM 전용 프로세서가 절실히 요구되지 만 기존의 SVM 프로세서는 SVM에 필요한 모든 연산들을 포함하지 못 하였다. 본 논문에서 제안하는 SVM 프로세서는 SVM이 필요로 하는 커널 연산, 학 습 연산, 재현 연산 회로를 모두 포함한다. 하드웨어 구현에 부적합한 quadratc programmng (QP) 학습 방법 대신에 kernel adatron (KA)과 kernel perceptron (KP) 학습 알고리즘을 사용한다. 적용 문제에 따라서 프로세서 사용자는 최고의 성 능을 위하여 학습 방법을 선택 사용 가능하다. 병렬로 설계된 기본 블록의 동 시 수행은 빠른 속도를 가능하게 한다. 양자화 오차가 발생하는 고정소수점 연산 실험을 하여 결과를 부동소수점 연산 결과와 비교하고 하드웨어 설계 사양을 결정하였다. 실험은 수중 음파 데 이터, 백혈병 환자 데이터의 분류를 수행하였고 비선형 통신 채널 등화 문제에 도 적용하였다. KA를 사용하여 채널 등화 문제에 적용하여 QP 방법에 의한 결과와 비교하였다. 소프트웨어를 사용한 SVM 처리 시간이 샘플의 수에 따라

요약 2차적으로 증가하는 반면, 하드웨어 설계 결과 처리 시간이 선형적으로 증가하 여 많은 샘플을 가지는 문제에 대하여 상당히 처리 속도가 증가하는 것을 알 수 있었다. 하드웨어 성능인 처리 시간과 회로 면적에 있어서 기존의 프로세서 와 비교하여 더 우수한 성능을 보였다.

Abstract The objectve of ths thess s to desgn a hgh-speed support vector machne (SVM) processor. The crcut s desgned usng hardware descrpton languages (HDL) and FPGA mplementatons are presented for evaluatons of some problems. The SVM s a new learnng-by-example paradgm. The man advantage of SVM over artfcal neural network resdes n the structure of the learnng algorthm, characterzed by the resoluton of a constraned quadratc programmng problem, where the drawback of local mnma s completely avoded. The SVM are traned wth relatvely small amounts of data, and the tranng s rather straghtforward, requrng less ad hoc nput from the desgner. The concurrent support vector machne (CSVM) processor that performs all phases of recognton process ncludng kernel computng, learnng, and recall on a chp s proposed. Quadratc programmng (QP) n orgnal SVM tranng algorthm s not sutable for hardware mplementaton, due to ts complexty and large memory consumpton. Thus we use kernel adatron (KA) and kernel perceptron (KP) learnng algorthms can be mplemented on a slcon chp snce these algorthms make use of recursve-updatng equatons nstead of QP. Dependng on the applcaton problems, one of the two learnng modules s chosen for best result. Concurrent operaton due to parallel composton of buldng blocks generates hgh speed and throughput. Experments on fxed-pont algorthm havng quantzaton error are performed and ther results are compared wth floatng-pont algorthm. Results of nonlnear channel

Abstract equalzaton by KA are compared wth those by QP. Whereas the computatonal complexty of the SVM wth the KA ncreases quadratcally, that of the CSVM chp ncreasng lnearly. The CSVM mplemented on FPGA chp performs fast and accurate results on hgh dmensonal cancer data classfcaton and nonlnear channel equalzaton. v

목 차 국문요약 영문요약 목차 표목차 그림목차 영문약어목록 ⅰ ⅲ ⅴ ⅷ ⅸ x 제1장 서론... 1 1.1. 연구 배경 및 목표... 1 1.2. 연구 내용 및 범위... 2 1.3. 논문의 구성... 5 제2장 Support Vector Machne... 6 2.1. SVM 개관... 7 2.1.1. 선형 SVM 분리 가능한 경우... 7 2.1.2. 선형 SVM 분리 불가능한 경우... 12 2.1.3. 비선형 SVM... 13 2.2. 다중 클래스 분류 SVM... 17 2.2.1. 승자독식 방법... 18 2.2.2. 쌍단위 분류 방법... 18 2.3. 학습 알고리즘... 19 v

목차 2.3.1. Kernel Adatron... 19 2.3.2. Kernel Perceptron... 22 2.3.3. 복잡도 계산... 25 제3장 기존의 연구... 27 3.1. 디지털 SVM 프로세서... 28 3.1.1. DSVM... 28 3.1.2. Dgtal Kernel Perceptron... 32 3.1.3. H-SVM... 34 3.2. 아날로그 SVM 프로세서... 36 제4장 Concurrent SVM 프로세서... 38 4.1. 주요 블록과 신호... 39 4.2. 각 블록의 구조... 46 4.2.1. Support Vector Element... 46 4.2.2. 커널 계산부... 48 4.2.3. 학습부... 50 4.2.4. 제어부... 51 4.3. 단순화된 CSVM의 구조... 55 제5장 SVM 소프트웨어 실험 결과... 59 5.1. Sonar data 실험... 60 5.2. Leukema data 실험... 63 v

목차 5.2.1. 마이크로어레이 DNA칩 데이터... 63 5.2.2 실험 결과... 65 5.3. 비선형 채널 등화 실험... 69 5.3.1. 비선형 채널 등화기... 69 5.3.2. 실험 결과... 71 제6장 CSVM 하드웨어 구현 및 성능... 83 6.1. 하드웨어 구현 실험 결과... 84 6.2. 하드웨어 테스트 실험 결과... 90 제7장 결론... 94 7.1. 연구결과... 94 7.2. 향후과제... 95 부록... 97 참고 문헌... 105 v

표목차 표 2.1. 커널함수 14 표 2.2. KA 알고리즘 22 표 2.3. 퍼셉트론 알고리즘 24 표 2.4. KP 알고리즘 24 표 2.5. 각 단계에 필요한 연산량 25 표 4.1. CSVM 입출력 신호와 역할 42 표 4.2. CSVM의 동작 모드 43 표 4.3. status 신호에 따른 CSVM의 상태 44 표 4.4. CSVM의 내부 제어 신호와 역할 52 표 5.1. 다양한 데이터폭과 LUT의 어드레스비트수에 대한 수중 음파 테스 트 데이터의 오분류율 61 표 5.2. 수중 음파 데이터에 대한 부동소수점과 고정소수점 연산 알고리즘 실험 62 표 5.3. 다양한 데이터폭과 커널 스케일율에 대한 백혈병 데이터의 테스트 오차개수 65 표 5.4. 백혈병 데이터에 대한 부동소수점과 고정소수점 연산 알고리즘 실험 68 표 5.5. 다양한 계수값의 RBF 커널에 대한 오차율 78 표 5.6. 다양한 계수값의 다항함수 커널에 대한 오차율 78 표 6.1. CSVM 프로세서를 사용한 각 단계의 처리 사이클수 84 표 6.2. HDL 합성 결과 87 표 6.3. KA와 KP 알고리즘을 내장한 CSVM의 성능 88 표 6.4. CSVM과 S-CSVM의 성능 비교 89 표 6.5. 회로 소자 수 비교 90 v

그림목차 그림 2.1. 선형 최대 마진 분류기 8 그림 2.2. 초평면의 선형 특징 공간으로의 사상 15 그림 2.3. SVM의 기본 구조 17 그림 2.4. 샘플의 수에 따라 필요한 곱셈 연산의 수 26 그림 3.1. dsvm 블록 31 그림 3.2. DKP의 구조 33 그림 3.3. H-SVM의 구조 35 그림 4.1. CSVM 구조 39 그림 4.2. 칩 간 연결을 통한 확장 40 그림 4.3. CSVM의 입출력 신호 41 그림 4.4. Support Vector Element 47 그림 4.5. 커널 계산부 49 그림 4.6. 학습부 50 그림 4.7. 학습 동작을 위한 상태 천이도 53 그림 4.8. 재현 동작을 위한 상태 천이도 55 그림 4.9. S-CSVM의 SVE 회로 56 그림 4.10. S-CSVM의 KCE 회로 57 그림 4.11. S-CSVM의 LE 회로 58 그림 5.1. 수중 음파 데이터에 대한 KA 알고리즘의 마진 수렴 곡선 60 그림 5.2. 유전자 발현 데이터를 얻는 과정 64 그림 5.3. 백혈병 데이터에 대한 KA 알고리즘의 마진 수렴 곡선 66 그림 5.4. 일반적인 횡단 등화기의 구조 70 그림 5.5. 모델 1에 대한 데이터의 분포와 결정 평면 72 그림 5.6. 모델 2에 대한 데이터의 분포와 결정 평면 72 그림 5.7. 채널모델 1에서 RBF 커널함수의 계수 변화에 따른 결정평면 75 그림 5.8. 채널모델 2에서 RBF 커널함수의 계수 변화에 따른 결정평면 77 x

그림목차 그림 5.9. KA 학습 알고리즘과 QP 방법을 사용한 실험 결과의 평균 BER 79 그림 5.10. 부동소수점 연산 모델을 사용한 결정 평면 80 그림 5.11. 고정소수점 연산 모델을 사용한 결정 평면 81 그림 5.12. 데이터의 소수자리 비트폭에 따른 비트 오차율 81 그림 6.1. 다른 샘플수에 따른 처리 시간 85 그림 6.2. 하드웨어를 사용하지 않는 SVM과 CSVM 프로세서의 연산 사이클 곡면 86 그림 6.3. 하드웨어 테스트를 위한 시스템 다이어그램 91 그림 6.4. 호스트 컴퓨터와 FPGA를 연결하는 데이터선 91 그림 6.5. 데이터 전송 프로토콜 92 그림 6.6. PCI버스와 FPGA 연결 블락도와 명령어 93 그림 6.7. PCI버스와 호스트 컴퓨터 연결 블락도와 명령어 93 x

영문약어목록 ANN: BER: BRAM: CQP: CSVM: DSVM: FIR: FPGA: FSM: HDL: ISI: KA: KALE: KCE: KP: KPLE: LE: LUT: MLP: QP: RBF: S-CSVM: SMO: SVE: SVM: PCI: Artfcal Neural Network Bt Error Rate Block Random Access Memory Constraned Quadratc Programmng Concurrent Support Vector Machne Dgtal Support Vector Machne Fnte Impulse Response Feld Programmng Gate Array Fnte State Machne Hardware Descrpton Language Intersymbol Interface Kernel Adatron Kernel Adatron Learnng Element Kernel Computng Element Kernel Perceptron Kernel Perceptron Learnng Element Learnng Element Lookup Table Mult-layer Perceptron Quadratc Programmng Radal Bass Functon Smplfed Concurrent Support Vector Machne Sequental Mnmzaton Optmzaton Support Vector Element Support Vector Machne Perpheral Component Interconnect x

제1장 서론 1.1. 연구 배경 및 목표 Support vector machne (SVM)은 1990년대 중반 Vapnk [1]에 의하여 제안된 샘플들에 의한 학습 방법이다. SVM은 통계적인 이론에 기반을 두고 있기 때 문에 성능에 대한 신뢰성이 우수하다. SVM은 기존의 신경회로망과 비교했을 때 특히 우월한 면을 가지고 있다. 신경회로망과 비교했을 때 SVM의 장점은 constraned quadratc programmng problem (CQP)를 이용하여 학습을 하기 때문에 local mnma에 빠지지 않는다는 점이다. SVM은 상대적으로 적은 양의 데이터 를 가지고 학습이 가능하고, 설계자가 초기에 정해주어야 하는 파라미터가 상대 적으로 적다. 전용 하드웨어로 구현하면 고차원의 데이터를 연산하기 위한 많은 연산을 병렬적으로 수행함으로써 연산시간을 줄일 수 있다. 최근에 SVM을 하드웨어 화하여 실시간 처리가 요구되는 분야에 적용하려는 시도가 있는데, 크게 아날로 그 구현과 디지털 구현 방법으로 진행되고 있다. 아날로그 SVM 하드웨어인 Kerneltron [2]는 내부적으로 아날로그 방식으로 설계하고 외부와는 디지털 신호 로 변환하여 전달한다. 이 하드웨어는 빠른 커널 연산을 하여 물체 검출 등의 실시간 적용 분야에 초점을 맞추고 있지만 칩 안에서 학습까지 이루어지지 않 아 재현 동작만 온라인으로 칩 상에서 이루어진다. 디지털 SVM 하드웨어인 1

제1장 서론 디지털 SVM [3, 4]은 하드웨어에 적합한 학습 알고리즘을 제안하고 학습까지 이 루어지는 디지털 SVM 하드웨어를 구현하였다. 하지만 이 디지털 하드웨어는 커널 연산 부분은 칩 상에서 동작하지 않음으로 인하여 시간 소모가 많은 커널 연산 과정에 의하여 처리 시간 상 병목 현상이 발생하게 되며 또한 칩만의 독 자적 연산 수행(stand-alone operaton)이 불가능하다는 단점이 지적된다. 이 논문에서 제안하는 concurrent support vector machne (CSVM)은 계산속도가 빠른 커널 계산부를 내장형으로 만들어서 한 하드웨어에서 SVM의 모든 과정이 수행되는 통합기능을 구현하였다. 기존에 사용되는 SVM 학습 알고리즘인 quadratc programmng (QP) 방법은 연산이 복잡하고 많은 메모리를 소모하여 하 드웨어 구현에 부적합하다. CSVM은 반복 갱신 방식으로 하드웨어 구현이 용 이하고 수렴성이 보장되는 SVM 학습 알고리즘의 하나인 kernel adatron (KA) [5] 및 kernel perceptron (KP) [4] 알고리즘을 사용한다. 또한 많은 연산이 요구되는 커널 연산을 병렬적으로 수행함으로써 소요시간을 단축시키고자 하며, 커널 값 을 일정한 범위에 제한하는 커널 스케일링 방법 [6]을 사용하여 하드웨어의 면 적을 최소화한다. 1.2. 연구 내용 및 범위 CSVM의 성능을 검증하기 위하여 세 가지의 실용적인 문제에 적용해 보았 다. 첫 번째 적용분야는 sonar 벤치마킹 데이터이다. Sonar 데이터는 선형적으 2

제1장 서론 로 분리 가능한 문제로 잘 알려져 있는 학습 알고리즘의 벤치마킹 목적으로 널 리 사용된다 [7]. 두 번째 적용분야는 질병진단이다. 최근 많은 차원의 데이터를 다루는 바 이오인포매틱스(bonformatcs) 분야의 문제가 대두되고 있으나 고차원의 데이터 를 다루는 데에 어려움을 많이 겪고 있다. DNA 마이크로어레이(mcroarray) 칩 을 통해 환자의 유전자 발현양상을 측정하여 질병의 유형을 분류하는 데에 여 러 종류의 기계 학습 방법이 사용되고 있다. 그 방법 중에 SVM은 고차원의 분류 문제에 탁월한 분류 능력을 발휘하고 있다 [8]. CSVM은 고차원의 데이터 를 가지는 암 진단 분류 문제 등에 적용하며 온라인상에서 즉시(pont-of-care) 진단 결과를 요구하는 분야에서 적합한 구조를 지닌다. 마지막 적용분야는 비선형 통신 채널 등화 문제이다. 이 문제는 Sebald et al. [9]에 의하여 본격적으로 연구되었다. 그들은 SVM과 신경회로망의 성능을 비교하여 SVM이 신경회로망보다 우월 또는 동등한 성능을 얻음을 보였다. 그 들은 QP방법을 사용하여 SVM을 학습하였다. 본 논문에서는 실제적인 리얼타 임 문제인 통신 채널 등화 문제에 적용하기 위하여 특별 제작 프로세서를 제작 하여 소요시간을 빠르게 한다. 이 논문의 목적은 고성능 SVM 프로세서를 개발하는 것이다. 회로는 하드 웨어 설계 언어(hardware descrpton language, HDL)를 사용하여 설계하였고 이를 FPGA에서 구현하여 성능을 세가지 문제에 적용하여 검증하였다. 본 연구에서 하드웨어로 설계하여 구현하는 데에 있어서 다음의 6가지 사 항을 고려하여 개발을 하였다. 3

제1장 서론 1) 포터블한 전용 하드웨어 프로토타입을 개발함. 2) 성능은 소프트웨어보다 빠를 것. : 샘플이 증가함에 따라 하드웨어인 CSVM프로세서가 소프트웨어보다 점점 더 속도가 증가함을 6.1절에서 보였다. 3) 단가를 낮추기 위하여 최소의 면적에 경제적으로 설계할 것. : 최소한의 면적을 소비하기 위하여 여러 가지 하드웨어 설계 기법을 사용하였 고, 이를 제 4장에서 설명하였다. 4) 프로세서 사용자에게 다양한 옵션을 제공할 것. : SVM 학습 알고리즘과 커널 함수를 적용 문제에 따라서 사용자가 선택 가능하 도록 설계하였다. 5) 다양한 응용 대상 문제에 적용하여 좋은 성능을 낼 것. : 벤치마크 문제인 sonar 분류 문제, 고차원의 바이오인포매틱스 문제인 백혈병 환자 진단 문제, 그리고 통신 분야인 비선형 채널 등화 문제에 적용하여 그 성 능을 기존의 방법과 비교하여 우수한 성능을 얻음을 확인하였다. 6) 고차원 또는 다수의 학습 데이터도 입력 가능할 것. : 수천개의 차원을 가진 백혈병 진단 문제에 작용하였고 다수의 학습 데이터를 가진 문제를 위하여 확장 가능하도록 하드웨어 구조를 설계하였다. 4

제1장 서론 1.3. 논문의 구성 논문의 구성은 다음과 같다. 제안하는 CSVM 프로세서 구조를 설명하기 전에 제 2장에서는 SVM과 그의 여러 가지 학습 알고리즘을 기술하였고 하드웨 어를 사용하지 않은 알고리즘 자체의 연산 복잡도를 보였다. 제 3장에서는 기 존의 SVM 프로세서들의 구조를 살펴보고 비교하여 보았다. 제안하는 CSVM의 구조를 제 4장에서 다루었다. 제 5장에서는 세 가지 응용문제를 소개하고 하드 웨어를 설계하기 전에 하드웨어의 데이터 폭 등의 설계명세(specfcaton)를 결정 하기 위하여 고정소수점 실험을 하고 그 결과를 기존의 연구 결과와 비교 분 석하였다. 제 6장에서는 결정된 하드웨어 설계 명세를 사용하여 CSVM 프로세 서를 실제로 설계하고 그 성능을 기존의 프로세서와 비교하였다. 마지막으로 이 논문의 결론과 향후 과제를 제 7장에서 다루었다. 5

제2장 Support Vector Machne 본 논문에서 개발한 CSVM 프로세서에 대하여 다루기 전에 프로세서의 알 고리즘인 SVM 방법에 대하여 기술한다. SVM 학습 알고리즘들에 대하여 알아 보고 QP 학습 방법, KA와 KP 학습 알고리즘을 비교 설명한다. 마지막으로 SVM 학습 알고리즘의 연산 복잡도를 계산하고 SVM의 각 동작 단계에 필요한 연산 복잡도를 비교한다. 6

제2장 Support Vector Machne 2.1. SVM 개관 SVM은 기존의 신경회로망에서 이용된 경험적 위험을 최소화(emprcal rsk mnmzaton)하는 원리보다는 구조적 위험을 최소화(structural rsk mnmzaton)하 는 근사적 방법이고 통계적 학습 이론에 기반하여 최적 분류를 함으로서 뛰어 난 일반화 성능을 보여 준다 [1]. SVM은 커널 함수에 의하여 정의된 특징 공 간(feature space)에서 초평면(hyperplane)을 경계로 학습 데이터를 분리한다. 학습 데이터 중에서 초평면과 가장 근접한 데이터들의 거리의 합인 마진이 최대가 되는 다차원 초평면을 찾는다. 통계 학습 이론에 의하면 초평면의 일반화 (generalzaton) 성능은 속해 있는 공간의 차원이 아닌 마진에 의하여 결정되므로 고차원에서도 분류 능력이 뛰어나다. 이 방법은 1979년 Vapnk에 의하여 발표 된 바 있으나 최근에 와서야 그 성능을 인정받아 각광을 받게 되었다. 2.1.1. 선형 SVM 분리 가능한 경우 학습 데이터가 (x 1, y 1 ),,(x n, y n )이고 입력패턴 x R d (d: 입력 공간의 차원) 에 대하여 두 개의 클래스 y = {+1, 1}로 분류되는 문제를 생각해 보자. 그림 2.1과 같이 결정 함수인 f(x)= sgn( (w x) + b)의 정규(normal) 벡터 w와 바이어스 b는 마진을 최대화하도록 결정된다. 7

제2장 Support Vector Machne Optmal Hyperplane Tranng Example Class 1 w Support Vector b Class 2 Margn 그림 2.1. 선형 최대 마진 분류기 Fg. 2.1. A lnear maxmal margn classfer 초평면 (w x) + b = 0은 다음의 조건을 만족한다. ( w x ) + b > 0, ( w x ) + b < 0, f f y y = 1 = 1 (2.1) 식 (2.1)에서 w와 b를 다른 값으로 하여 표준형태(canoncal form)로 나타내 면 다음과 같이 표현할 수 있다. 8

제2장 Support Vector Machne ( w x ) + b 1, ( w x ) + b 1, f f y y = 1 = 1 (2.2) 위의 표준 형태를 단일항의 식으로 나타내면 다음 식과 같다. y (w x ) + b 1, f = 1, 2,, N (2.3) 식 (2.3)에서 등호의 조건을 만족하는 입력 패턴 (x, y )을 support vector라 하 며, 개념적으로 이 벡터는 초평면에 가장 가까이 위치하여 분류하기가 어려운 벡터들이다. 따라서 분류를 위한 학습은 제약조건 식 (2.3)을 만족하는 최적의 초평면을 찾는 것이다. 이는 제약조건을 가지는 최적화 문제로, 학습패턴이 주 어질 때 최적의 초평면을 위한 최적의 파라미터 w 0 와 b 0 을 찾는 것이다. 여기 에서의 최적은 최대 여유를 가지는 것이며, 최대여유 초평면은 최적으로 2개의 클래스를 분리할 수 있는 초평면이다. 결국 2개의 클래스와 초평면 사이의 거 리에 따른 여유는 2/ w 가 되며, 입력패턴을 최적으로 분류하는 초평면은 다음 의 비용 함수 Θ(w)를 최소화한다. 여기서 비용함수 Θ(w)는 식 (2.4)와 같다. 1 2 Θ ( w ) = w (2.4) 2 식 (2.4)의 비용 함수는 w의 볼록 함수이며, 제약조건 식 (2.3)은 w에 선형임을 알 수 있다. 최적화 문제를 해결하기 위하여 라그랑지안 계수법을 이용하면 다 9

제2장 Support Vector Machne 10 음과 같은 라그랑지안 함수 J(w, b, α)을 얻을 수 있다. = + = n T b x w y w b w J 1 2 1] ) ( [ 2 1 ),, ( α α (2.5) 식 (2.5)에서 α는 라그랑지안 계수(Lagrange multpler) 벡터이다. 식 (2.5)의 최적화 문제에 대한 해는 w와 b에 대해서는 최소화되며 α 0에 대해서는 최대 화되어야 한다. 따라서 w와 b에 대한 J(w, b, α)의 최소는 그 각각에 대한 미분 으로 얻어질 수 있다. = = = = = = n n y x w w J y b J 1 1 0 0 0 α α (2.6) α 를 구하기 위해서 기본 문제에 대한 라그랑지안 함수 J(w, b, α)를 이원문 제(dual problem)의 목적함수 Q(α)로 표현할 수 있다. 여기서 목적함수 Q(α)는 식 (2.6)을 식 (2.5)에 대입하여 얻어지며, 그 표현식은 식 (2.7)과 같다. = = = = n n j j T j j n x x y y Q 1 1 1 ) ( 2 1 ) ( α α α α (2.7) 조건은 식 (2.8)과 같다.

제2장 Support Vector Machne n = 1 α y = 0, α 0 ( = 1, 2, K, N) (2.8) 식 (2.7)의 목적함수는 일반적인 quadratc programmng (QP) 문제의 형태로 학습패턴의 항으로만 구성되며, 입력패턴의 내적(dot product)의 형태인 (x T x j )로 표현된다. 따라서 분류문제를 식 (2.7)의 이원문제로 생각하면, 이는 학습패턴 n n {( x, y )} = 1 이 주어질 때, 제약조건 = 1 α y = 0 와 α 0 ( = 1, 2,, n)을 만족 하는 목적함수 식 (2.7)를 최대화하는 라그랑지안 계수 α 를 찾는 것이다. 따라서 QP 알고리즘에 따라 제약조건 식 (2.3) 하에서 목적함수 식 (2.7)을 최대로 하는 최적의 라그랑지안 계수 α o 를 찾으면, 최적의 가중치 벡터 w o 는 식 (2.6)에 따라 계산될 수 있고, 최적의 바이어스 b o 는 support vector로부터 계산될 수 있다. 각각의 계산식은 식 (2.9)와 같다. w o = n = 1 α x y o 1 b o = bo[ xr + xs ] (2.9) 2 여기에서 x r 과 x s 는 각각 식 (2.10)의 조건을 만족하는 support vector들이다. α α 0, d = 1, d = 1 (2.10) ro so > r s 11

제2장 Support Vector Machne 이 때 SVM에 의한 분류식을 정리하면 식 (2.11)과 같다. f ( x) = sgn( wo x + yo ) n = sgn[ α y ( x x ) + y ] = 1 o o (2.11) 식 (2.11)로부터 선형의 결정면을 가짐을 알 수 있다. 여기서 sgn( )는 이 양수이면 1, 그렇지 않으면 1를 가지는 함수이다. 2.1.2. 선형 SVM 분리 불가능한 경우 선형적으로 분류 가능하지 않는 문제에 대해서도 분류 가능하게 하는 일반 화된 초평면을 구성하기 위해서 음수가 아닌 스칼라 변수 ξ 0을 소개한다. 여기에서의 ξ 는 잘못된 분류와 관계된 오차의 척도로 슬랙변수(slack varable) 이다. 따라서 분류 불가능한 경우를 위한 슬랙변수 ξ 를 포함하는 제약조건은 식 (2.3)을 식 (2.12)와 같이 수정함으로써 얻어질 수 있다. y ( w x ) + b 1 ξ, = 1, 2,..., n (2.12) 또한, 위의 제약조건을 만족하는 가중치 벡터 w와 슬랙변수 ξ 를 포함하는 Θ(w, 12

제2장 Support Vector Machne ξ)는 식 (2.13)과 같다. n 1 2 Θ( w, ) = w + c ξ 2 ξ (2.13) = 1 여기에서 c는 양의 값으로 학습오차와 일반화 능력 사이의 상관관계를 제 어하는 파라미터이다. 식 (2.12)의 제약조건 하에서 식 (2.13)의 최적화 문제에 대한 라그랑지안 함수는 J(w, b, ξ, α, β)로 표현되며, 여기서 β는 ξ 0의 조건을 위한 라그랑지안 계수이다. 한편 주어진 라그랑지안 함수 J(w, b, ξ, α, β)에 대한 이원문제의 목적함수 Q(α)를 최대화하기 위한 조건은 α = 0 와 0 α c (=1, 2,, n)로 α 의 상한이 주어지는 것만 다르다. 여기서도 QP과정에 따라 최적의 라그랑지안 계수를 찾으면, 최적의 가중치 벡터 w o 와 최적의 바이어스 b o 는 각각 식 (2.9)로 구해지며, 그 분류식은 식 (2.11)과 동일하다. n = 1 y 2.1.3. 비선형 SVM 이상에서 살펴 본 분류식은 선형의 결정면만을 설명한 것으로 모든 문제에 적용될 수는 없으며, 비선형 분류도 가능하게 하기 위해서는 좀 더 일반적인 결 정면을 가지도록 하여야 한다. 이를 위한 방법으로 SVM에서는 입력 벡터 x를 고차원의 특징공간 z로의 사상을 이용한다. 이는 분리 가능한 초평면이 입력공 13

제2장 Support Vector Machne 간에서는 비선형이나 변환을 통한 고차원의 특징공간에서는 선형적으로 표현될 수 있다는 것이다. 이를 위한 목적함수 Q(α)를 최대화하는 것은 고차원의 특징 공간에서 내적 (z(x) z(x ))의 계산을 요구한다. 여기서 커널 함수와 특징공간과 의 관계는 식 (2.14)와 같다. T K( x, x ) z( x) z( x ) = (2.14) 이 때 사상을 위한 커널 함수에는 표 2.1과 같이 다항 함수, RBF 함수, 시그모 이드 함수 등이 있다. 표 2.1. 커널 함수 Table 2.1. Kernel functons 커널 종류 K(x, x j ) 선형 커널 다항 커널 x T x j (x T x j + 1) p RBF 커널 exp( c x x j 2 ), where c = 1/2σ 2 시그모이드 커널 tanh(β 0 x T x j +β 1 ) 그림 2.2는 특징 공간으로의 사상에 의하여 입력 공간에서 비선형인 초평면이 선형으로 변환됨을 보여 준다. 14

제2장 Support Vector Machne Input Space Feature Space Φ 그림 2.2. 초평면의 선형 특징 공간으로의 사상 Fg. 2.2. Hyperplane mappng: from nonlnear nput space to lnear feature space 비선형 분류도 가능하게 하는 최적의 초평면을 구성하기 위한 목적함수 Q(α)는 식 (2.15)와 같이 표현된다. n n n 1 Q( α ) = α α α j y y j K( x, x j ) (2.15) 2 = 1 = 1 j= 1 식 (2.15)는 선형 분류의 목적함수에서 입력 벡터의 내적을 커널함수로 대치한 것에 불과하다. 여기에서의 조건도 = n 1 α y = 0 와 0 α c 로 선형적으로 분리 불가능한 경우와 동일하다. 또한 특징공간에서 최적의 분리를 위한 초평면의 분류식도 식 (2.11)과 유사한 식 (2.16)와 같이 나타낼 수 있다. 15

= SVs 제2장 Support Vector Machne f ( x) = sgn[ α y K( x, x ) + b ] (2.16) o o 식 (2.16)에서 SVs는 support vector들을 나타내며, 최적의 가중치 벡터 w o 와 최 적의 바이어스 b o 는 각각 다음과 같이 계산된다. w = α y z( x ) o = SVs o = SVs 1 b o = wo y[ K( x, xr ) + K( x, xs )] 2 (2.17) 위와 같은 방법으로 SVM의 파라미터를 구하는 QP방법은 계산량이 많고 구현 하기 어렵다. 본 논문에서는 QP 방법이 아닌 구현하기 쉬운 KA와 KP 학습 알 고리즘을 사용한다. 그림 2.3은 SVM의 구조를 나타낸다. 입력 x와 support vector x 는 커널 함 수에 의하여 비선형으로 사상된다. 최종적으로 계산된 f(x) 값의 부호에 따라서 입력 x의 클래스를 결정하게 된다. 이 구조는 신경회로망의 다층 퍼셉트론 (mult-layer perceptrom, MLP) 구조와 유사하다. 구조의 한 가운데에 위치해 있는 support vector element (SVE)는 K(x, x )을 계산하고 support vector 값을 저장한다. SVE는 MLP의 은닉 뉴런과 유사한 역할을 하고 동작한다. 기존의 신경회로망 프로세서가 은닉 뉴런을 병렬적으로 계산하여서 속도를 증가한 것과 같이 SVM 의 경우도 SVE를 병렬적으로 연산하면 더 빠르게 연산하는 강력한 성능을 갖 게 된다. 본 논문에서는 이 병렬성을 이용하여 CSVM 프로세서를 제안하였다. 16

제2장 Support Vector Machne b f(x) = n = 1 α y K ( x, x ) + b α 1 y 1 α 2 y 2 α 3 y 3 α n y n K(x,x 1 ) K(x,x 2 ) K(x,x 3 ) K(x,x n ) x = {x 1, x 2,,x d } 그림 2.3. SVM의 기본 구조 Fg. 2.3. Fundamental archtecture of the SVM 2.2. 다중 클래스 분류 SVM SVM은 이진 패턴 분리 문제를 위한 알고리즘인데, K개의 클래스가 있는 문제를 학습시키려면 여러 개의 SVM을 조합하여야 한다. SVM 다중 클래스 분류 학습을 위한 조합 방법으로 승자독식 방법(wnner-take-all)과 쌍단위 분류 방법(parwse classfcaton) 등이 사용되고 있다. 17

제2장 Support Vector Machne 2.2.1. 승자독식 방법 승자독식 방법은 가장 간단하며 효율적인 조합방법으로, 두 범주의 결정함 수를 이용하여 각각의 k개의 클래스에 대하여 이원 결정함수를 구축함으로써 K 개의 클래스로 확장하는 방법이다 [10]. f k : R N { ± 1 }, + 1 1 for all samplesn class k else (2.18) 이 경우 다음과 같이 각 클래스 당 하나씩 총 K개의 SVM 분류기를 학습 시킨다. 그리고 SVM의 출력으로 ±1 값을 얻는 것이 아니라 실수값을 얻어서 각 분류기가 선거를 치루게 된다. 만일 어떤 테스트 패턴에 대하여 k번째 분류 기의 출력이 가장 큰 값이라면 이 패턴은 k번째 클래스에 속한다고 결론을 내 린다. 2.2.2. 쌍단위 분류 방법 승자독식 방법은 간단하고 효율적인 방법이지만, 경계면을 동시에 만족시 킬 수 있는 최적의 다원 범주 결정면을 구축하지는 못 한다. 이러한 단점을 보 완하기 위해 두 범주 간의 경계선을 직접적으로 처리하는 쌍단위 분류 방법이 18

제2장 Support Vector Machne 제안되었다 [11]. 쌍단위 분류 방법은 각 쌍마다 분류기를 만드는 방법으로, K(K 1)/2개의 모든 조합에 대하여 SVM 분류기를 학습시키는 것이다. f kl : R N { ± 1 }, + 1 1 for all samplesnclass k for all samplesnclassl (2.19) 학습과정을 거친 후 구축된 K(K 1)/2개의 쌍단위 결정함수(parwse decson functon) f k l = f 중에서 최대값을 갖는 범주에 할당하게 된다. kl f ( x) = arg max f (2.20) k l kl 2.3. 학습 알고리즘 2.3.1. Kernel Adatron Kernel Adatron (KA) 알고리즘은 통계적인 학습 방법의 하나인 adatron 알고 리즘에 커널을 사용함으로서 비선형 feature 공간에서 마진을 최대화하게 한 것 이다. Adatron 알고리즘은 이론적으로 최적해로의 수렴이 알고리즘의 반복에 지수 함수적으로 빠르게 일어난다고 알려져 있다 [5]. 결국 KA 알고리즘은 19

제2장 Support Vector Machne SVM의 특징공간에 adatron을 도입하는 것으로 용이한 구현성 뿐만 아니라 커널 에 의한 비선형 특징공간에서의 단순한 동작 특성도 동시에 얻을 수 있어, 기존 QP 학습 알고리즘이 가지는 계산과 구현상의 제약들을 효과적으로 해결할 수 있다. n = 1 α y = 0 의 조건 하에서 오목한 목적함수 Q(α)를 최대화하는 α를 찾는 것은 기울기 상승법의 이용으로 가능하다. 이는 변수 α 에 대한 2차 함수로 표 현되는 등식의 선형 제약조건을 가지는 최적화 문제인 표준 QP 문제 (CQP)이 다. 여기서 조건을 포함하는 목적함수인 라그랑지안 함수 Q(α)는 식 (2.21)과 같이 표현된다. n n n n 1 Q( ) = α α α j y y j K( x, x j ) λ α y 2 α (2.21) = 1 = 1 j= 1 = 1 식 (2.21)에서 마지막 항은 = n 1 α y = 0 의 제약조건을 위한 항이며, λ는 이 를 위한 라그랑지안 계수이다. 제약조건 0 α c 는 α 의 값이 음수이면 0으 로, c보다 큰 값이면 c로 제한하면 된다. 라그랑지안 함수 Q(α)의 최대화는 미 분에 기초를 둔 기울기 상승법으로 가능하며, 이 때 최대화를 위한 α 의 변화 량 δα 와 λ를 구하는 식은 다음과 같다. 20

제2장 Support Vector Machne Q δα ( t + 1) = η α ( t) = η 1 n j= 1 n λ ( t) = λ( t 1) + ρ α ( t) = 1 α ( t) y K( x, j y j x j ) λ( t) y (2.22) 식 (2.22)에서 t는 반복수(epoch)이며, η와 ρ는 각각 학습률(learnng rate)로 양수값 이다. 식에서 K(x, x j )는 대칭이며 양수로 정의되는(postve-defnte) n n의 행렬 K의 요소이다. KA 알고리즘에서는 좀 더 빠른 알고리즘의 수렴을 위해 라그랑지안 계수 λ를 식 (2.22)에서와는 달리 할선법(secant lne method)을 이용하여 구하였다. 본 논문에서는 표 2.2와 같은 바이어스를 사용하지 않는 KA 알고리즘이 사용된 다. 일부 연구가들은 KA 알고리즘이 사용하는 경사상승방법(gradent ascent technque)이 바람직하지 않은 상태를 갖는 커널 함수에 대해서는 제대로 성능을 발휘하지 못할 수도 있다고 주장한다. Kecman et al. [12]의 논문에서, radal bass functon (RBF) 가우시안 커널과 같은 명확한 (postve defnte) 커널 함수를 사용 한다면, 분석적인 프로그램 과정에 기반하여 성능이 입증된 sequental mnmzaton optmzaton (SMO) 방법과 KA 알고리즘은 분석적인 형태나 수치적 인 구현에 있어서 동일하다는 것을 입증하였다. 또한 명확한 커널 함수들은 바 이어스 항을 필요로 하지 않음을 주장하였다. 따라서 본 논문에서는 바이어스 항이 없는 KA학습을 사용하는 RBF 커널 SVM을 선택하였다. 21

제2장 Support Vector Machne 표 2.2. KA 알고리즘 Table 2.2. KA algorthm {초기화} 모든 에 대해서 α = 0, 학습율 η을 세팅 {학습 루프} repeat for = 1,,n z = n j= 1 α y K( x, x ), α = η(1 y z ) j j j f (α + α ) > 0 then α α + α else α 0 end for {종료 조건} untl (최대학습회수에 도달하거나 r = 1 2 mn ( z ) { y =+ 1} max ( z ) 1 y = 1} { ) 2.3.2. Kernel Perceptron Kernel Perceptron (KP) 알고리즘은 퍼셉트론의 w 영역으로부터 SVM의 α 영 역으로 바꾼 것이다 [4]. Rosenblatt의 퍼셉트론의 가중치 갱신 알고리즘은 식 (2.23)과 같다. 22

제2장 Support Vector Machne f y ( w w + x y (2.23) k x ) 0 then wk+1 k 그런데, 최종 학습 가중치는 식 (2.24)와 같은 데이터의 조합으로 표현할 수 있으므로 퍼셉트론의 학습 알고리즘을 식 (2.25)와 같이 데이터의 가중치 변경으로 생각할 수 있다. w = n = 1 α (2.24) y x f y ( w x ) 0 then α α + η (2.25) k 이 때, 학습된 퍼셉트론은 식 (2.26)과 같이 데이터의 조합으로 표현할 수 있다. n f ( x) = w x = y α ( x x) (2.26) = 1 식 (2.26)이 학습 데이터에 대한 가중치 α 와 데이터 x의 내적으로 표현되므 로 커널 함수로의 확장을 생각할 수 있다. 따라서 식 (2.27)과 같은 커널 퍼셉 트론을 얻을 수 있다. n f ( x) = w x = y α K( x, x) (2.27) = 1 KP 알고리즘은 퍼셉트론 알고리즘과 마찬가지로 수렴성이 보장된다. 퍼셉 트론 알고리즘과 KP 알고리즘을 정리하여 표 2.3과 표 2.4에 나타내었다. 23

제2장 Support Vector Machne 표 2.3. 퍼셉트론 알고리즘 Table 2.3. Perceptron algorthm {초기화} 모든 에 대해서 w = 0, b = 0으로 세팅 {학습 루프} repeat for = 1,,n n o = y ( w j xj + j= 1 b) f o 0 then update w w + x y, b = b + y end for {종료 조건} untl (최대학습회수에 도달하거나 모든 에 대하여 o > 0 ) 표 2.4. KP 알고리즘 Table 2.4. KP algorthm {초기화} 모든 에 대해서 α = 0, b = 0으로 세팅 {학습 루프} repeat for = 1,,n n o = α j qj + b, qj = y j = 1 y K ( x, x ) j j f o 0 then update α α + 1, b = b + y end for {종료 조건} untl (최대학습회수에 도달하거나 모든 에 대하여 o > 0 ) 24

제2장 Support Vector Machne 2.3.3. 복잡도 계산 SVM은 커널 계산, 학습, 그리고 재현 단계 동작을 수행하게 된다. K(x, x j ) = exp( 1/2σ 2 x x j 2 )의 커널 함수를 사용하여 각 단계의 계산 복잡도를 표 2.5 에서 나타내었다. 표 2.5로부터 커널 단계와 학습 단계에 필요한 계산량이 더 많다는 것을 알 수 있다. 표 2.5. 각 단계에 필요한 연산량 Table 2.5. Numbers of operatons for each phase Number of operatons Kernel computaton Learnng (KA) Recall addton or substtuton (2d + 1)n 2 n (n + 1) n 1 multplcaton 2dn 2 2n (n + 1) 2n exp( ) n 2 N/A N/A comparson N/A n N/A d = 2이고 커널 연산에 대하여 샘플의 수와 그에 필요한 곱셈 연산의 수와 의 관계를 그림 2.4에 나타내었다. 곱셈 연산은 다른 연산에 비하여 가장 복잡 도가 상대적으로 높기 때문에 이를 사용하여 비교하였다. 샘플의 수가 증가할 수록 커널 계산을 위한 연산량, 즉 곱셈의 수가 학습단계를 위한 수보다 더 빨 25

제2장 Support Vector Machne 리 증가하는 것을 알 수 있다. 따라서 본 논문에서는 더 큰 샘플의 문제에 대 하여 속도 증가 효과를 최대화하기 위하여 커널 계산 단계에 필요한 회로를 CSVM 프로세서에 포함시키기로 결정하였다. CSVM은 한 칩에 모든 단계의 회로를 수행하는 최초의 SVM 프로세서이다. 800 multplcatons ( 10 3 ) 700 600 500 400 300 200 kernel computng learnng 100 0 100 200 300 400 500 samples 그림 2.4. 샘플의 수에 따라 필요한 곱셈 연산의 수 Fg. 2.4. The requred number of multplcaton operatons wth the number of samples 26

제3장 기존의 연구 Support vector machne을 실시간의 적용 분야에서 더 빠르게 동작시키기 위 해서 90년대 말부터 하드웨어 구조의 연구들이 꾸준히 되어 왔다. SVM 프로 세서 연구를 크게 분류하자면, 디지털 프로세서와 아날로그 프로세서로 나누어 진다. 대체로 계산이 정확하고 잡음에 강인한 디지털 SVM 프로세서 연구가 더 많이 되고 있다. 연구 분야를 기능 측면에서 나눈다면, SVM의 주요 동작 중 커널 연산만을 하드웨어로 한 연구와 학습 연산만을 하드웨어로 한 연구 등 이 있다. 본 논문에서는 SVM의 모든 동작을 지원하는 최초의 프로세서인 CSVM 프로세서를 개발하였다. 본 논문에서 개발한 CSVM 프로세서를 소개하기 전에 기존의 SVM 프로세 서들의 소개와 장단점에 대하여 기술한다. 27

제3장 기존의 연구 3.1. 디지털 SVM 프로세서 3.1.1. DSVM Anguta et al. [3]에 의하여 제안된 디지털 SVM 프로세서이며 학습과 재현 동작이 칩 상에서 이루어지지만 커널 연산 부분은 칩 상에서 동작하지 않는다. 새로운 디지털 하드웨어에 적합한 학습 알고리즘을 제안하였고 이를 통신 채널 등화 문제에 적용하고 FPGA에 구현하였다. 본 논문에서 개발된 CSVM을 동일 한 채널 등화 문제에 적용하였고, DSVM의 설계 면적과 연산 시간을 제 6장에 서 비교하였다. DSVM에서 수행되지 않는 SVM의 동작인 커널 연산을 CSVM 에서는 학습, 재현 동작과 함께 수행 가능하다. 알고리즘은 크게 두 부분으로 이루어진다. 한 부분은 SVM의 파라미터를 찾는 반복연산 네트워크이고, 다른 한 부분은 문턱값(threshold)을 계산하는 부분 이다. 제약이 있는 최적화 문제를 하드웨어에 적합하게 만들기 위한 핵심 아이디 어는 식 (3.1)과 같은 미분방정식에 의하여 표현되는 동적 시스템으로 문제를 사상하였다. & ν = FA(ν ) (3.1) 여기에서 ν T = [α T, b]이고 안정점은 최적화 문제의 해와 일치한다. 식 (3.1)은 반 복 신경회로망 (recurrent neural network)로 구현 가능하며, [13]에서는 간단한 아날 28

제3장 기존의 연구 로그 회로로 구현하였다. 디지털 구조에서는 위의 반복 계산식과 유사한 방법 으로 다음과 같이 사용하였다. k+ ν 1 = F ( ν k ) D (3.2) 적분을 위한 오일러의 방법(Euler s method)을 사용하여 다음과 같이 식 (3.1)로부 터 식 (3.3)을 얻는다. k+ 1 k k ν = ν + η F ( ν ) A (3.3) 여기에서 η 는 적분 단계이다. 제약이 있는 QP문제인 식 (2.15)를 최소화하기 위한 DSVM의 핵심 알고리즘은 다음과 같다. z k = α k + ηg (3.4) α k+1 = max(0, mn(z k, C)) (3.5) 여기에서 g = Qα + r 이고 η 2/n 의 조건을 만족하면 수렴이 보장된다. 위에 설명한 DSVM 알고리즘의 일반화 능력을 보강하기 위하여 문턱값 연 산을 하였다. 따라서 학습 알고리즘은 다음의 두 부분이 반복적으로 연산되면 서 이루어진다. 한 부분은 고정된 문턱값 b를 사용하여 CQP의 해를 구하고 다 29

제3장 기존의 연구 른 한 부분에서는 최적의 문턱값인 b * 을 구하기 위하여 b의 값을 반복 갱신한다. DSVM의 데이터 입력신호와 데이터 출력신호는 모두 16비트로 설계되었다. SVM 블록은 로딩, 학습, 출력 단계로 동작한다. 제어부와 데이터를 주고 받기 위한 버스는 3상태 게이트를 근간으로 연결이 되어 있다. 데이터는 데이터 버 스를 이용하고 주소 버스를 통하여 주고 받는 데이터는 커널 행렬의 각 요소의 주소이다. 그림 3.1과 같이 DSVM 알고리즘은 m개의 기본 처리 유니트(Processng Unt, PE)로 이루어지는 일차원 시스토릭(systolc) 배열 구조로 dsvm 블록을 설계하였 다. 기본 처리 유니트에서는 벡터 g을 갱신하는 역할을 한다. 커널 함수값에 해당하는 Q ~ 는 미리 호스트 컴퓨터에서 계산되고 m N Q 비트 크기의 RAM에 저장한다. N Q 는 q j 의 워드길이를 나타낸다. 주어진 시간 단계 k에서, 각 PE 는 레지스터 reg에 α k 을 저장하고 g = Σ q ~ k j α + r ~ 을 계산한다. 첫 단계에서 q ~ α k 가 계산되고 acc에 저장된다. α k 는 PE +1 로 전달되고 PE 는 PE 1 로부터 α k 1 를 받는다. 단계가 증가함에 따라서 이 동작이 계속 반복되고 최종 m단계 에서는 최종값 g k 가 각 PE 의 출력에 준비가 된다. 그 밖의 블록으로 Counters-block에서는 RAM에 저장되어 있는 커널값을 읽 기 위한 주소값을 생성한다. Bas-block은 문턱값을 계산하는 블록으로 이동 레 지스터, 덧셈기, MUX, 이진 비교기를 이용하여 설계한다. S-block의 역할은 y T α 값인 s을 계산하는 블록이다. 30

제3장 기존의 연구 sel1 addr dn selm addressbus addr dn 1 RAM 1 1 RAM n ctrlram 2compl 2compl b we y yn + 1 + 1 PE 1 PE n + + c c databus 0 0 MSB MSB akpl 1 akpl n ak 1 ak n comp 1 comp n endrunblk 그림 3.1. dsvm 블록 [3] Fg. 3.1. dsvm block [3] 31

제3장 기존의 연구 Sonar 데이터와 비선형 채널 등화 문제에 대하여 DSVM을 사용하여 학습한 결과, 기존의 방법보다 우수한 성능을 얻었다. 하드웨어의 설계 사양을 결정하 기 위하여 고정고수점 연산 실험을 행하여 여러 가지 설계 사양을 비교하였다. 설계 후 회로는 학습 샘플 개수가 8개인 경우와 32개의 경우에 대하여 각 각 설계되었다. 기능적 시뮬레이션 결과, m = 8인 경우에 학습 단계는 14,000사 이클에 종료되었고 로딩 단계는 290사이클이 소요되었다. 더 실제적인 크기인 m = 32인 경우 140,000사이클의 학습 단계가 소요되었고 4226사이클의 로딩이 필요하였다. 3.1.2. Dgtal Kernel Perceptron DSVM을 개발했던 연구자들이 SVM 알고리즘 중의 하나인 kernel perceptron (KP) 방법을 구현한 단순한 하드웨어 구조를 설계하였다 [4]. 사용한 KP 알고 리즘은 표 2.4와 같고 DSVM과 마찬가지로 커널값은 하드웨어에서 연산하지 않 고 미리 계산된 커널값을 사용하였으며 학습 연산과 재현 연산만을 하드웨어 위에서 실행된다. 반면에 본 논문에서 개발된 CSVM은 SVM의 모든 연산이 하 드웨어 위에서 실행된다. Dgtal kernel perceptron (DKP)의 구조는 그림 3.2와 같다. 기본 처리 유니트 (Processng Unt, PE)은 식 (3.6)을 연산한다. 32

제3장 기존의 연구 RAM q UCPE α j k + acc PE MSB 0 EN count 0 EN count α 1 k+1 α n k+1 그림 3.2. DKP의 구조 [4] Fg. 3.2 Archtecture of DKP [4] n MSB = sgn( α q ) (3.6) j= 1 j j 간단한 포화상승 카운터를 사용하여 분류되지 않은 점에 대한 갱신 회로를 설계하였다. 곱셈 연산을 하는 PE는 매우 단순한 구조로 이루어져 있으며 MSB 는 누적 결과의 최상위비트이다. DKP 알고리즘에 따라서 카운터의 EN-입 력인 MUX는 제어기에 의하여 해당 단계에서 선택된다. UCPE는 메모리를 제 어하는 역할을 하고 각 단계에서 PE로 α j 와 q j 를 전달한다. 33

제3장 기존의 연구 Sonar 데이터 실험 결과, DSVM보다 단순한 구조이면서 동일한 결과인 8개 의 테스트 패턴만을 오분류하였다. 이 실험을 위해서 DSVM은 24비트의 q j 와 8비트의 α j 을 사용한 반면, DKP는 단지 3비트 카운터들와 3비트의 q j 을 사용하 였다. 3.1.3. H-SVM R-Rojas et al. [14]에 의하여 제안된 디지털 SVM 프로세서이며 주로 영상 처 리 실시간 고속 처리를 위하여 개발되었다. H-DSVM은 고속의 커널 연산과 재 현 동작을 수행 가능하지만, 학습 연산은 하드웨어에서 이루어지지 않는다. 이 와 비교하여, CSVM은 커널 연산, 학습, 그리고 재현 동작이 모두 하드웨어에서 이루어지는 장점을 가지고 있다. H-DSVM은 하드웨어-소프트웨어를 함께 설계하는 방식을 사용하였고 전체 구조는 그림 3.3과 같다. H-SVM은 SIMD 구조이며 파이프라인으로 데이터를 처리한다. 256단계의 그레이 영상 데이터를 위하여 입력 버스는 8비트의 크기로 설계되었고 출력은 +1 또는 1이므로 1비트로 버스를 설계하였다. 가중치의 비트 폭은 실험을 통 하여 24비트로 결정하였다. 입력 차원은 64 또는 256이며 SV의 수는 128개, 커 널은 2-4차의 다항 함수를 지원한다. 34

제3장 기존의 연구 8 Kp Module 0 Kp Module 1 Kp Module d-1 chp select 24bt hgh-z bus Sgma Module 32 32 그림 3.3. H-SVM 구조 [14] Fg. 3.3. H-SVM archtecture [14] Kp 모듈은 입력 벡터와 support vector 행렬의 요소를 곱하는 곱셈 후 덧셈 연산을 한다. Sgma 모듈은 Kp 모듈의 병렬 곱셈기의 결과를 파이프라인으로 연산한다. Sgma 모듈은 1024클럭 사이클 동안 연산을 수행한다. 60만 게이트를 포함하는 XCV600EFG900-6 VrtexE FGPA을 사용하여 합성한 결과, 33MHz의 주파수를 지원하는 PCI버스와 연동하기 적당한 35MHz의 최대 클럭 속도를 얻었고 52%의 슬라이스와 6%의 플립플롭을 소비하였다. 연산 능 력은 1초에 528백만 개의 곱셈-덧셈을 실행 가능한 프로세서이다. 35

제3장 기존의 연구 3.2. 아날로그 SVM 프로세서 Genov et al. [2] 에 의하여 제안된 아날로그 SVM 프로세서인 커널트론 (Kerneltron)은 빠른 커널 연산을 하지만 학습 동작이 칩 상에서 이루어지지 않 아서 재현 동작만 온라인으로 칩 상에서 이루어진다. 커널트론은 병렬적인 구 조를 사용하여 빠른 물체 검출 분야에 적용되고 SVM의 뛰어난 일반화 성능을 가진다. 커널트론의 중심부는 내부적으로 아날로그 배열 연산을 하고, 외부적 으로는 디지털의 형태로 연산한다. 웨이블릿과 SVM연산은 같은 칩에서 효과적으로 한 번에 이루어진다. 디 지털 입력들이 직-병렬 이동 레지스터를 통하여 프로세서로 입력된다. 가중치가 있는 커널값들을 디지털 영역에서 문턱화(threshold)하여 패턴을 분류한다. 커널 값들은 룩업테이블(lookup table)에 저장되어 있는 f( )을 통하여 X X m 의 내적을 사상하여 얻게 된다. 웨이블릿 특징 추출 방법과 내적 연산은 선형 변환이며 식 (3.7)과 같이 두 행렬을 곱함에 의하여 이루어진다. W mr = N n= 1 X mn A nr (3.7) 입력 벡터 X와 주형(template) 벡터 W m 을 병렬적으로 내적 연산하는 것은 식 (3.8)과 같은 행렬-벡터 곱셈 연산이다. 36

제3장 기존의 연구 N 1 = Y m Wmn X n (3.8) = n 0 이 방법은 디지털 처리와 재구성 가능한 디지털 인터페이스를 하는 아날로 그 배열 처리 방법을 하여 효율적인 계산을 가능하게 한다. 다시 말해서, 아날 로그 배열 구조에 디지털로 표현한 데이터가 임베드된 것이다. 커널트론의 프로토타입은 0.5µm CMOS 기술로 3mm 2 크기의 칩에 집적되었 다. 3mm 3mm 의 면적을 가지며 소비전력은 5.9mW이다. Throughput은 6.5 GMACS이고 8-bt의 output resoluton의 성능을 보인다. 커널트론을 사용하여 실 시간, 온라인, 대규모 연산이 필요한 문제에 적합하도록 빠른 연산을 지원한다. 37

제4장 Concurrent SVM 프로세서 본 논문에서 개발한 CSVM 프로세서의 구조를 세부적으로 기술한다. 먼저 CSVM의 전체 구조를 설명하고 칩의 동작과 주요한 세부 블록을 자세히 기술한 다. KA 알고리즘과 RBF 커널 함수만을 포함하는 단순화된 CSVM (S-CSVM)의 구조를 보인다. 38

제4장 Concurrent SVM 프로세서 4.1. 주요 블록과 신호 CSVM 프로세서의 구조는 그림 4.1과 같다. 본 하드웨어는 SVM의 마진 상에 위치하는 support vector을 기본단위로 하여 Support Vector Element (SVE) 모 듈을 병렬 처리하여 연산속도를 증가시켰다. SVE의 개수는 학습샘플의 개수이 며 학습결과 0이 아닌 값을 갖는 SVE가 support vector가 된다. 학습샘플의 개 수가 많을 경우는 그림 4.2와 같이 칩을 확장하여 사용 가능하게 설계되었다. 칩의 확장은 각 CSVM의 공유버스를 연결하고 출력선과 확장 입력선을 연결한 다. 학습 단계를 위해서는 그림에서 가장 아래에 위치하는 하나의 CSVM의 Learnng Element (LE)만 동작하게 된다. shared bus Class 1 x SVE 1 Σ z or o >0 <0 SVE 2 Class 2 SVE n control module LE 그림 4.1. CSVM 구조 Fg. 4.1. CSVM archtecture 39

제4장 Concurrent SVM 프로세서 모든 SVE 간은 공유버스로 연결을 시켜서 커널 연산이 동시에 이루어지게 하였다. KA와 KP 학습 알고리즘의 유사한 점을 이용하여 칩에 KA, KP 두 가 지 학습방법을 함께 내장하였고 SVE를 이용하여 커널 계산, 학습과 재현 동작 을 모두 함으로써 적은 면적에 효과적으로 설계하였다. LE는 학습 단계의 파 라미터 갱신을 위한 계산 시에만 사용된다. SVE SVE Σ SVE Control LE SVE SVE Σ SVE Control LE SVE SVE Σ SVE Control LE 그림 4.2. 칩 간 연결을 통한 확장 Fg. 4.2. CSVM expanson usng the chp connectons 40

제4장 Concurrent SVM 프로세서 clk reset start learn_sel mode overflow sample_sze status data_sze learn_count kernel_sel CSVM data_out kernel_scale data_to_from_bus kernel_coeff max_learn data_n data_ext data_to_from_bus 그림 4.3. CSVM의 입 출력 신호 Fg. 4.3. Input and output sgnals of CSVM CSVM의 입력과 출력 신호는 그림 4.3과 같고 CSVM의 제어를 위한 외부 제어 신호는 표 4.1과 같다. 데이터의 시작을 칩이 인식하도록 칩으로 data_n 신호를 최초로 넣을 때 start신호를 1로 해 준다. 샘플이 상당히 많은 데이터를 분류할 때 m개의 CSVM 칩을 함께 사용하기 위하여 1번째 CSVM의 data_out 출력 신호를 번째 CSVM의 data_ext 핀을 통해서 입력을 받고 두 개의 CSVM의 공유 데이터 버스 입출력핀인 data_to_from_bus를 서로 연결해 준다. 41

제4장 Concurrent SVM 프로세서 표 4.1. CSVM의 입출력 신호와 역할 Table 4.1. Input and output sgnals of CSVM 신호 종류 비트폭 신호명 역 할 데이터 입력 13 / 17 data_n 입력 데이터 데이터 입력 13 / 17 data_ext 여러칩 사용시 다른칩으로부터 데이터 입력 데이터 입출력 17 / 21 data_to_from_bus 공유 버스 데이터 제어 입력 1 clk 외부 클럭 제어 입력 1 reset 칩의 리셋 제어 입력 1 start 최초 데이터 입력 시점 표시 제어 입력 1 learn_sel KA 학습 / KP 학습 설정 제어 입력 2 mode 칩의 동작 설정 제어 입력 8 sample_sze 샘플 데이터 수 설정 제어 입력 13 data_sze 데이터의 차원(dmenson) 설정 제어 입력 3 kernel_sel 선형 커널 / 다항 커널 / RBF 커널 선택 제어 입력 4 kernel_scale 커널 스케일링율 설정 제어 입력 17 / 21 kernel_coeff 커널 계수 설정 제어 입력 15 max_learn 최대 학습 회수 설정 데이터 출력 17 / 21 data_out 출력 데이터 제어 출력 1 out_vald 최종 출력값이 출력될 때를 알림 제어 출력 1 overflow 연산 중 자리 넘침 알림 제어 출력 2 status 칩의 동작상태 알림 제어 출력 15 learn_count 학습 회수 알림 42

제4장 Concurrent SVM 프로세서 mode 입력 신호는 표 4.2와 같이 칩의 동작을 결정한다. mode=0에서는 학습 동작만 이루어지고 mode=3에서는 학습이 종료된 후 재현 동작도 연속으로 이루 어진다. 표 4.2. CSVM 의 동작 모드 Table 4.2. The modes of CSVM mode 신호 칩의 동작 0 학습 동작 1 재현 동작 (내부 파라미터 사용) 2 재현 동작 (외부 파라미터 사용) 3 학습 동작 + 재현 동작 재현 동작만을 할 경우, 칩 내에 이미 저장되어 있는 파라미터를 이용할 때 는 mode=1을 설정하면 되고 외부에서 파라미터를 입력 받아 사용하고자 할 때 는 mode=2로 설정한다. 출력 신호 status 신호는 표 4.3과 같이 현재 칩의 상태를 사용자에게 알려 준다. status=0은 대기상태, status=1은 학습 동작 상태를 나타내며, status=2는 재 현 동작 상태, status=3은 동작 종료 상태를 알려주게 된다. 43

제4장 Concurrent SVM 프로세서 표 4.3. status 신호에 따른 CSVM 의 상태 Table 4.3. The status of CSVM status 신호 칩의 상태 0 대기 상태 1 학습 동작 상태 2 재현 동작 상태 3 동작 종료 상태 칩의 동작은 로딩, 커널 계산, 학습, 재현 단계로 나누어진다. 1) 로딩 단계: 외부로부터 x, y를 로드하는 단계이다. 한 샘플에 해당하는 x, y는 공유 버스를 통하여 순차적으로 각 SVE의 내부 메모리로 저장된다. 이 동작 은 칩의 입력 핀의 수가 한정되어 있으므로 병렬적인 수행이 불가능하고 순 차적으로 이루어지므로 하드웨어 구조에 관계 없이 샘플의 수에 따라서 일정 한 로딩 시간이 소요된다. 2) 커널 계산 단계: SVE의 커널 계산부를 동시에(concurrent) 수행하도록 하여 커 널 계산에 걸리는 시간을 상당히 감소시켰다. 하나의 SVE 에서 x 를 공유버 스로 보내면 모든 나머지 SVE j (j )들이 이를 동시에 받아 자신의 x j 와 커널 함수 K(x, x j )를 계산하고 이를 내부 메모리에 저장하게 된다. 이 동작은 병 44

제4장 Concurrent SVM 프로세서 렬적으로 수행됨에 따라 순차적인 커널 계산 방법보다 속도가 이론적으로 n 배만큼 빨라지게 된다. 3) 학습 단계: 표 2.2와 표 2.4에서 기술한 KA 또는 KP 학습 알고리즘을 이용하 여 마진을 최대화하는 α와 b를 찾는 과정이다. 이 과정은 SVE와 LE 모두를 사용되게 된다. 이전 동작인 커널 계산 단계에서 계산한 K(x, x j )를 메모리에 서 읽어서 각 SVE는 KA학습인 경우, z j = α j y j K(x, x j )의 연산을 하게 되고, KP 학습인 경우는 o j = α j y y j K(x, x j ) 연산을 한다. 그 후에 모든 SVE는 모든 SVE로부터 계산된 z j 값이나 (o j + b) 값을 더하여 z 또는 o 값을 얻게 된다. 그 후 학습 알고리즘의 갱신 조건에 해당하는 연산을 학습부에서 하게 되고 LE에서 계산된 새로운 α와 b는 공유버스를 통하여 해당 SVE의 메모리로 보 내져서 종료조건이 만족될 때까지 위에서 기술한 학습 과정을 반복하게 된다. 이 과정에서도 z j 또는 o j 를 얻기 위하여 병렬적인 연산이 이루어지므로 그만 큼 학습 속도가 향상되게 된다. 4) 재현 단계: 학습에서 얻은 파라미터 α와 b, 그리고 α가 0이 아닌 SVE에 저 장된 x값을 이용하여 입력된 테스트 데이터 x t 의 클래스를 결정하게 된다. 테스트 샘플에 대한 마진 값 m t 는 식 (4.1)에 의하여 계산된다. m n = α j y j K( xt, x) b (4.1) t + j= 1 45

제4장 Concurrent SVM 프로세서 마진 값이 양수이면 1계열로, 음수이면 2계열로 판정한다. 이 단계에서는 커널 연산이나 학습 연산에서 사용한 회로를 그대로 재사용하므로 회로 면적을 그만큼 절약하게 된다. 재현 단계에서도 SVE의 병렬 동작으로 순차적 동작보 다 이론적으로 n배 빠른 연산을 하게 된다. 4.2. 각 블록의 구조 4.2.1. Support Vector Element SVE는 그림 4.4와 같이 공유버스 인터페이스부와 메모리부, 식 (4.2)의 연 산을 하는 부분으로 이루어진다. SVE의 출력 신호인 z j 와 o j 는 식 (4.2)에 의하 여 계산된다. z o j j = α y K( x, x ) j j j = α y y K( x, x ) j j j (4.2) z j 는 KA학습 또는 재현 동작에 사용되고 o j 는 KP학습 동작에서만 사용되므 로 KA학습 또는 재현 동작에서는 y 곱셈 연산은 이루어지지 않고 bypass된다. y 값은 1 또는 1 값이기 때문에 곱셈기 대신에 보수 변환기(two's complementer) 를 사용하여 면적을 절약하였다. 재현 단계에서는 커널 계산부(kernel computng 46

제4장 Concurrent SVM 프로세서 element)에서 신호를 받아서 y 를 곱하게 되고 학습 단계에서는 메모리에서 이미 계산되어 저장된 커널 값을 받아서 y 값을 곱하게 된다. send_en address y_en learn _sel yj _en alpha_en shared data bus memory 18 0 x j sel_n x j K(x, x j ) α j y b y y j b α j reg reg reg kernel computng two s complementer two s complementer o j / z j learn 그림 4.4. Support Vector Element Fg. 4.4. Support Vector Element 메모리에 저장되어있는 x j 와 y는 로딩 단계에서 저장되고 커널 연산 단계에 서 K(x, x j )가 계산되어 메모리의 해당부분에 저장된다. α와 b는 매회 학습마다 갱신되어서 메모리에 저장된 후 각 해당 레지스터에 저장된다. 하나의 메모리 출력 포트로부터 여러 파라미터를 레지스터로 보내야 하기 때문에 각각의 레지 스터들은 해당 파라미터가 메모리로부터 도착할 때만 해당 y_en, yj_en, alpha_en 신호를 1로 하여 저장한다. 원하지 않는 신호가 도착했을 때 저장하지 않고, 47

제4장 Concurrent SVM 프로세서 이전 값을 유지하기 위하여 해당 y_en, yj_en, alpha_en 신호를 0으로 설정한다. 공유버스 인터페이스부의 입력부분에서 입력은 해당 동작에 따라서 공유버 스 값, 외부 입력 값, 메모리에 저장될 커널 연산 값 중에 선택된다. 인터페이 스부의 출력부분은 3상태 게이트를 이용하여 공유버스에 두 개 이상의 데이터 가 올려지는 것을 막아 주게 된다. 데이터를 보내고자 하는 SVE는 send_en=1 로 하여 신호를 보내게 되며 한꺼번에 두 개의 SVE에서 신호를 보낼 수 없도 록 제어부에서 각 SVE의 send_en을 통제한다. 4.2.2. 커널 계산부 커널 계산부는 커널 계산 단계와 재현 단계에서 사용되고 학습 단계에서는 커널 계산 단계에서 계산되어 메모리에 저장된 커널값을 사용한다. 커널 함수는 선형, 다항 함수, RBF 커널을 그림 4.5와 같이 내장하였다. RBF 커널 함수 exp( 1/2σ 2 x x j 2 )에서 1/2σ 2 항의 연산에 필요한 나눗셈 연 산은 회로 구현 시 많은 면적과 연산 시간이 소모된다. 따라서 1/2σ 2 항을 하 나의 외부입력 파라미터 c로 받아 들이여 더 경제적인 설계를 하였다. 커널 함수 모듈은 면적을 최소화하기 위하여 곱셈기 2개만으로 3종류의 커 널 함수를 설계하였다. 그림 4.5에서 누산기(accumulator) 앞에 위치하는 첫 번째 곱셈기에서는 선형, 다항 함수의 x x 연산을 하고 RBF 함수의 (x x ) (x x ) 연산을 한다. LUT 앞에 위치하고 있는 두 번째 곱셈기에서는 다항 함 48

제4장 Concurrent SVM 프로세서 수의 (x x ) (x x ) 연산을 하고 RBF함수의 c x x j 2 연산을 한다. RBF 연산에서 두 번째 곱셈기의 출력 값은 지수함수 LUT로 통과하게 된다. LUT의 입력비트의 크기에 비례하여 메모리 공간을 차지하므로 실험을 통하여 입력비트의 크기를 결정하였다. sel_kernel rst kernel_scale n_1 n_2 accumulator shfter + exponental LUT out RBF coeff poly coeff sel_kernel 그림 4.5. 커널 계산부 Fg 4.5. Kernel computng element 고차원의 데이터의 커널 계산 시 커널 값이 너무 커질 수 있으므로 커널 스케일링 방법을 사용하여 커널 계산 값의 범위를 줄여서 데이터 비트의 정수 부분을 효과적으로 절약시켰다. 49

제4장 Concurrent SVM 프로세서 send_en load send_sel learn_sel KALE 1 shared data bus α new b new reset reg MSB + α old + y two s complementer MSB o / z reg y reg α old reg b old + 1 + y KPLE 그림 4.6. 학습부 Fg. 4.6. Learnng element 4.2.3. 학습부 학습부는 파라미터 α와 b를 학습 종료 조건이 만족할 때까지 갱신하는 부 분으로서 KA학습알고리즘의 식 (4.3)과 KP학습알고리즘의 식 (4.4)에 따라서 그 림 4.6과 같이 구현된다. α = η 1 y z ) ( f (α + α )>0 then α α + α else α 0 (4.3) 50

제4장 Concurrent SVM 프로세서 f o 0 then update α α + 1, b = b + y (4.4) 학습부는 커널 값을 사용하여 모든 SVE에서 계산되어서 더해진 o 또는 z 을 받고 갱신되어야 할 SVE 의 메모리에 저장되어 있는 파라미터인 α old, b old, y 값을 공유버스를 통하여 받는다. 공유버스로부터 온 값들을 load신호에 따라 α old, b old, y 레지스터에 차례대로 저장한다. Kernel Adatron Learnng Element (KALE)와 Kernel Perceptron Learnng Element (KPLE)에서 계산되어 갱신된 α new, b new 값은 send_en 신호가 활성화되면 공유버스를 통하여 SVE 의 메모리에 저장 된다. 학습 종료 조건이 만족하면 학습 단계는 끝나게 되고 최종 파라미터 α 와 b가 모든 SVE의 메모리에 저장되게 된다. 4.2.4. 제어부 제어부는 CSVM의 동작을 통제하는 내부와 외부 제어신호들을 생성하고 fnte state machne (FSM)으로 이루어진다. 사용자의 외부 제어신호 mode에 따라 서 제어부는 mode에 맞는 단계 동작 시작, 반복, 종료를 각 부분에 명령하게 된 다. 적당한 메모리의 번지에 데이터나 파라미터가 저장되도록 주소를 생성시켜 역할을 한다. 메모리로부터 데이터 내용이 적당한 타이밍에 파라미터 레지스터 에 저장되도록 enable 신호를 생성시켜 준다. 또한 공유버스에서 데이터 충돌 51

제4장 Concurrent SVM 프로세서 이 일어나는 것을 막는 중요한 역할도 한다. 표 4.4에서 제어부 회로에서 발생하는 내부 제어 신호와 그의 역할에 대하 여 정리하였다. 표 4.4. CSVM의 내부 제어 신호와 역할 Table 4.4. Internal control sgnal of CSVM 제어 모듈 비트폭 내부 제어 신호명 역 할 SVE sample_sze+1 send_en 데이터를 공유버스로 보낼지를 결정 SVE 1 y_en, yj_en, alpha_en y, y j, α 값의 해당 레지스터로 저장 여부 선택 SVE sample_sze we SVE 의 메모리에서 데이터를 저장 또는 로드 선택 SVE 2 sel_n SVE의 입력을 외부 또는 공유버스 또는 KCE 중 어디에서 받을지 선택 SVE 1 learn SVE 1 sel_mem SVE의 메모리 또는 KCE로부터 신호를 받을 지 선택 데이터 메모리/ 파라미터 메모리 선택 KCE 1 rst Accumulator의 리셋 LE 3 load 공유버스로부터 데이터를 y, α old, b old 레지스터에 저장할지 선택 52

제4장 Concurrent SVM 프로세서 데이터와 파라미터의 비트폭이 4비트가 차이가 나므로 회로 면적을 효과적 으로 사용하기 위하여 SVE의 분산 메모리를 데이터 메모리와 파라미터 메모리 로 따로 설계하였다. sel_mem 신호를 이용하여 사용할 메모리를 선택하게 된 다. 그림 4.7에서 단순화된 학습 동작을 위한 상태 천이도를 보였다. 초기 제어신호 설정 we = 0 0 sel_mem = 1 sel_n = 11 en_send = 0 0 rst = 1 learn = 0 load = 1 1 addr = 0~N S0 IDLE we = 1 1 S1 데이터 입력 S21 커널값 계산 we = 1 1 / sel_n = 10 / en_send = 10 0 ~ 0 010 rst =1 S22 커널값 저장 we = 0 0 / sel_n = 00 / en_send = 10 0 / rst = 0 S31 파라미터값 읽음 (SVE) S32 학습 시작 sel_mem = 1 / learn = 1 / load = 0 0111 we = 0 0 / sel_mem = 0 / en_send = 10 0 ~ 0 010 load = 01 1 S33 파라미터값 읽음 (LE) en_send = 00 0 / load = 1 1 S34 파라미터값 계산 (LE) we = 10 0 / sel_n = 10 / en_send = 0 01 en_send=0 01 아니오 예 we = 0 0 / sel_mem = 0 / sel_n = 00 en_send = 0 0 / load = 0 0 S35 파라미터값 저장 (SVE) 아니오 종료조건 만족 예 학습 종료 그림 4.7. 학습 동작을 위한 상태 천이도 Fg. 4.7. State transton dagram for learnng process 53

제4장 Concurrent SVM 프로세서 초기화 설정 상태인 IDLE상태에서는 초기 제어신호를 그림과 같이 설정한 다. 학습이 시작되면 상태 S1에서 외부로부터 입력 패턴인 x j 와 y j 값을 로딩 받는다. 상태 S21과 S22에서 커널값을 계산한 후에 저장을 하게 되고, 마지막 SVE의 x j 을 공유버스에 보내어 커널값을 계산할 때까지 S21과 S22을 반복한다. 이 커널값 계산 단계에서 제어신호 en_send의 값은 처음에 N+1 비트 (N: 샘플크 기)에서 최상위비트만을 1로 하는데, 이는 SVE 1 의 값만을 공유버스로 보내는 것 을 의미한다. 다음 반복 단계에서는 en_send의 값을 오른쪽으로 자리이동을 하 여 SVE 2 의 값만을 공유버스로 보내게 된다. 상태 S31에서는 SVE의 메모리로 부터 α j 와 b 값을 읽어서 해당 레지스터에 저장하게 된다. 이제 비로소 학습 단계가 S32에서 시작된다. LE는 학습 알고리즘에 따라서 계산하기 위해서 상 태 S33과 같이 y, α j old 와 b old 값을 해당 SVE로부터 공유버스를 통해서 받아서 해당 레지스터에 저장하게 된다. S34에서 새로운 α j new 와 b new 값들을 계산하게 되고 S35에서 이 새로운 파라미터 값들을 공유버스를 통해 해당 SVE로 보내주 어서 해당 SVE의 메모리에 저장되게 된다. 그 후에 종료조건을 만족하면 학습 이 종료되고, 만족하지 않는다면 상태 S31로 가서 학습 동작이 반복된다. 그림 4.8에서는 재현 동작을 위한 상태 천이도를 나타냈다. 초기의 제어신 호 설정은 그림과 같고 재현 동작이 시작되면 상태 S1과 같이 SVE의 메모리로 부터 파라미터 값들을 해당 레지스터에 저장하게 된다. 상태 S2에서는 SVE의 재현 동작회로 연산을 하게 되어서 제어신호 out_vald 값이 1이 될 때 최종 결 과가 출력된다. 54

제4장 Concurrent SVM 프로세서 초기 제어신호 설정 we = 0 0 sel_mem = 1 sel_n = 00 en_send = 0 0 rst = 1 learn = 0 load = 1 1 S0 IDLE load = 1..10 ~ 1 1011 S1 파라미터값 읽음 (SVE) sel_mem = 0 / sel_n = 11 / rst = 0 / load = 1 1 S2 재현 동작회로 연산 addr = 0~N 결과 출력 Result value (+) : class1 cancer (-) : class2 cancer 그림 4.8. 재현 동작을 위한 상태 천이도 Fg. 4.8. State transton dagram for recall process 4.3. 단순화된 CSVM의 구조 면적을 최소화하기 위하여 몇 가지 기능을 제외한 단순화 구조를 가진 S- CSVM (Smplfed CSVM)을 설계하였다. 기존의 CSVM에서 RBF커널과 KA 알 고리즘만을 포함시킨 구조이다. 커널 함수와 알고리즘 선정은 이론적으로 검증 이 잘 되어 있고 성능이 가장 우수했기 때문이다. 전체 구조에서는 변함이 없 고 각 블록에서 회로 구성이 단순화되었다. 55

제4장 Concurrent SVM 프로세서 send_en address yj _en alpha_en shared data bus memory 18 0 x j sel_n x j K(x, x j ) α j y y j reg α j reg kernel computng two s complementer z j learn_sel 그림 4.9. S-CSVM의 SVE 회로 Fg. 4.9. Support vector element for S-CSVM 그림 4.9는 S-CSVM의 SVE 구조이다. KP 알고리즘을 사용하지 않으므로 식 (4.2)에서 알 수 있듯이 KP 알고리즘의 학습과 재현 연산 식에서 y 항이 제 외된다. 따라서 그림 4.9에서와 같이 y 곱셈 연산을 위한 보수기가 제외되었고 바이어스를 사용하지 않는 KA 알고리즘을 사용하므로 메모리에서 바이어스를 저장을 위한 공간이 없어진다. 56

제4장 Concurrent SVM 프로세서 rst n_1 accumulator shfter exponental LUT out n_2 RBF coeff 그림 4.10. S-CSVM의 KCE 회로 Fg. 4.10. Kernel computng element for S-CSVM 그림 4.10은 S-CSVM의 KCE 구조이다. 선형 커널과 다항 커널 연산에 해 당하는 회로가 제외되어 상당히 단순화된 것을 알 수 있다. CSVM의 KCE에서 는 2개의 곱셈기를 포함하는 반면에 S-CSVM에서는 하나의 곱셈기만을 사용된 다. 이는 실험 결과 외부 입력 파라미터인 RBF coeff 신호를 2의 배수로 한정 했을지라도 알고리즘 수렴 성능에 이상이 없기 때문이다. 2의 배수의 곱셈이므 로 곱셈기를 shfter로 대체하였다. S-CSVM의 LE 회로를 그림 4.11에서 나타내었다. KCE와 마찬가지로 SVM 의 LE회로에 비하여 많은 면적이 감소되었음을 알 수 있다. 그림의 KPLE 회 로와 바이어스 레지스터가 제외되었다. 57

제4장 Concurrent SVM 프로세서 send_en load reset 1 shared data bus reg MSB + two s complementer z reg reg y α old 그림 4.11. S-CSVM의 LE 회로 Fg 4.11. Learnng element for S-CSVM 6장에서 회로 합성 결과 S-CSVM이 CSVM에 비하여 면적과 연산 시간에서 얼마나 향상되었는지를 비교한다. 58

제5장 SVM 소프트웨어 실험 결과 제 6장에서 보일 예정인 하드웨어 설계에 앞서서 설계할 알고리즘들이 실 제적인 문제에서 좋은 성능을 내는지 검증해 보았다. 본 논문에서는 실제적인 문제로서 수중 음파 데이터 분류 문제, 백혈병 질병 진단 문제, 비선형 채널 등 화 문제를 사용하여 알고리즘의 성능을 비교하고 분석하였다. 또한 하드웨어의 데이터 폭 등의 설계 명세를 결정하기 위하여 고정소수점 연산을 수행하는 알고리즘을 사용하여 같은 문제에서 부동소수점 연산 알고리 즘과 대등한 성능을 낼 수 있는지 실험을 하여 분석을 하고 설계 명세를 정하 였다. 본 논문의 부동 소수점 실험과 고정 소수점 실험은 MATLAB을 사용하 여 수행하였고 Statstcal Pattern Recognton Toolbox [15]의 SVM 소스 프로그램을 수정하여 실험하였다. 59

제5장 SVM 소프트웨어 실험 결과 5.1. Sonar data 실험 60개의 특징(feature)을 가진 수중 음파 데이터 (sonar dataset)는 104개의 학습 패턴과 104개의 테스트 패턴으로 되어 있다. 이 문제는 수중 음파 탐지기 신호 를 입력 받아 그 해저 지형이 광석인지 암석인지 분류해 내는 문제로 분류기의 성능을 평가하는 벤치마킹 데이터셋으로 널리 사용된다. 수중 음파 데이터의 분류 문제는 데이터의 차원이 높고 학습 데이터와 테스트 데이터 간의 중복 정 도가 낮아서 어려운 문제로 알려져 있다 [7]. 1 0.5 margn r 0-0.5-1 -1.5 0 20 40 60 80 100 120 140 160 180 200 epochs 그림 5.1. 수중 음파 데이터에 대한 KA 알고리즘의 마진 수렴 곡선 Fg. 5.1. A convergence curve of KA algorthm on sonar dataset 60

제5장 SVM 소프트웨어 실험 결과 본 논문에서 사용된 SVM 학습 알고리즘의 수렴성을 검증하기 위하여 수중 음파 데이터를 분류해 보았다. η = 1, RBF 커널의 KA 학습 알고리즘을 사용하 여 실험한 결과, 그림 5.1과 같이 100회 학습 후에 마진이 1로 수렴하는 것을 알 수 있다. 표 5.1. 다양한 데이터 폭과 LUT 의 어드레스 비트 수에 대한 수중 음파 테스트 데이터 오분류율 Table 5.1. Percentage of msclassfed test patterns on sonar dataset for dfferent data wdths and address bts of LUT 데이터 폭 LUT 의 어드레스 비트 수 12 14 16 18 20 14.4% 19.2% 15.4% 15.4% 22 15.4% 6.7% 6.7% 6.7% 24 9.6% 6.7% 6.7% 6.7% KP학습과 RBF커널 함수를 사용한 부동소수점 실험 결과 104 테스트 패턴 중에 7개의 패턴만을 오분류하였다. 이는 Anguta et al. [4]의 연구결과보다 우수 한 결과이다. KP알고리즘이 9개의 패턴을 오분류한 KA알고리즘보다 성능이 좋았다. 표 5.1은 다양한 데이터 폭과 LUT의 어드레스 비트 수에 대한 고정소 수점 실험 결과이다. 데이터의 정수 부분은 6비트로 고정하였다. 22비트의 데 61

제5장 SVM 소프트웨어 실험 결과 이터 폭과 14비트의 LUT의 어드레스 비트 수 이상일 때 부동소수점 알고리즘 과 성능이 동일했다. 표 5.2. 수중 음파 데이터에 대한 부동소수점과 고정소수점 연산 알고리즘 실험 Table 5.2. Floatng and fxed-pont algorthm experments for sonar dataset nsv teratons errors dev(m FL -m FI ) dev(α FL -α FI ) Floatng-pont 65 167 7 18-6-8-4 67 153 10 1.79 7.07 18-6-12-4 65 167 7 0.01 0 Fxed- pont 16-4-16-4 95 1000+ 62 52.73 66.05 16-6-8-4 69 309 16 6.67 25.77 16-6-10-4 65 167 7 0.05 0 14-6-14-6 66 113 9 1.98 5.64 표 5.2에서는 수중 음파 데이터에 대하여 부동소수점 연산과 고정소수점 연 산을 사용한 결과를 나타내었다. 이 실험에서도 KP학습과 RBF커널 함수를 사 용하였다. 고정소수점 실험에서는 표 5.1의 실험과는 다르게 데이터의 정수비 트폭을 고정하지 않고 변화시키면서 실험하였다. nsv는 support vector들의 개수 이다. 표의 두번째 열의 aa-bb-cc-dd 에서 aa는 데이터의 소수비트폭이고 bb는 정수비트폭을 표시하고 cc는 RBF함수 LUT의 어드레스 비트 중 소수비트폭, dd 62

제5장 SVM 소프트웨어 실험 결과 는 RBF함수 LUT의 어드레스 비트 중에 정수비트폭을 나타낸다. dev(m FL -m FI ) 는 부동소수점의 실험결과 마진값와 고정소수점의 실험결과 마진값의 편차, 즉 차이를 나타내고 dev(α FL -α FI )는 부동 소수점과 고정소수점 결과의 라그랑지안 계수의 차이를 나타낸다. 표를 보면, 고정소수점 실험의 16-6-10-4, 18-6-12-4 실험의 두 경우에만 부동소수점과 동일한 테스트 오차를 발생한다. 마진값의 약간한 차이에도 불구하고 한정된 비트폭을 가지고도 같은 성능을 낼 수 있음 을 알 수 있다. 또한 이 두 경우에 가장 적고 부동소수점 실험과 같은 수의 support vector를 가지게 된다. 16-4-16-4 실험의 경우는 정수비트폭을 2비트에 의하여 감소함에 따라 오타가 상당히 증가하여 정수비트폭이 6비트가 최소한 필요한 것을 알 수 있다. 5.2. Leukema data 실험 5.2.1. 마이크로어레이 DNA칩 데이터 DNA 마이크로어레이 칩은 용액이 투과하지 않는 고형 지지체 위에 고밀도 로 DNA를 고정해 놓은 보합용 "probe array" 이다 [16]. 기존에 유전공학에서 사용하던 방법들과는 달리 한 개의 DNA Mcroarray 위에는 최소한 수백 개 이 상의 유전자가 놓여지므로, 다수의 유전자 발현변이 분석을 빠른 시간에 해결 할 수 있다. 63

제5장 SVM 소프트웨어 실험 결과 유전자 발현 데이터를 얻은 과정은 그림 5.2와 같다. 두 개의 다른 환경에 서 채집된 유전물질에 각각 다른 색깔의 형광물질(빨간색(Cy5)과 녹색(Cy3))을 합성한 것을 똑같은 양만큼 보합한 것들이 DNA Mcroarray의 각 셀을 이룬다. 그러므로 이것을 레이저 형광 스캐너로 읽어들이면 서로 다른 두 개의 환경 중 어떤 환경에서 유전물질이 많이 발현했느냐의 정도에 따라 빨간색에서부터 녹 색 사이의 다양한 색상을 갖는 점들의 집합을 얻을 수 있으며, 이를 이용하여 시각적으로 수천 개의 유전 물질의 발현변이 정도를 한번에 확인 할 수 있다. 또한 두 가지의 색상이 발현되는 정도를 각각 양수와 음수로 하여 수치화 할 수 있으므로 컴퓨터를 이용한 분석이 가능하다. 그림 5.2. 유전자 발현 데이터를 얻는 과정 [16] Fg. 5.2. Procedure of obtanng gene expresson data [16] 64

제5장 SVM 소프트웨어 실험 결과 5.2.2 실험 결과 백혈병 데이터 [17]는 DNA 마이크로어레이칩으로부터 얻은 유전자 발현 양 상 데이터이다. 이 데이터는 72명의 환자에 대한 각 7129개의 유전자로 이루어 져 있다. 72명의 환자 샘플 중에 38명의 데이터는 학습을 위해서 사용되었고 나머지 34명의 데이터는 테스트용으로 사용되었다. 급성 림프구성 백혈병(ALL, acute lymphoblastc leukema)과 급성 골수성 백혈병(AML, acute myelod leukema)의 두 가지 클래스로 분류된다. 전처리 과정 [18]을 통해서 얻은 3571개의 유전자 를 실험에 사용하였다. 수중 음파 데이터 실험과 마찬가지로 학습 알고리즘의 수렴성 검증 실험을 수행하였다. 그림 5.3과 같이 150회 학습 후에 마진이 수렴한다. η = 1, RBF 커 널의 KA 학습 알고리즘을 사용하였다. 고차원의 백혈병 데이터의 경우 연산 데이터의 범위가 너무 커지는 것을 막기 위하여 커널 스케일링율 s k = 128을 주 어서 실험하였다. 65

제5장 SVM 소프트웨어 실험 결과 1 0.8 0.6 margn r 0.4 0.2 0-0.2-0.4-0.6-0.8 0 20 40 60 80 100 120 140 160 180 200 epochs 그림 5.3. 백혈병 데이터에 대한 KA 알고리즘의 마진 수렴 곡선 Fg. 5.3. A convergence curve of KA algorthm on leukema dataset 표 5.3. 다양한 데이터 폭과 커널 스케일율에 대한 백혈병 데이터의 테스트 오차 개수 Table 5.3. Test errors on leukema dataset for dfferent data wdths and kernel scales 데이터 폭 커널 스케일율 1 4 16 64 256 14 14 15 17 13 1 16 20 18 17 1 1 18 20 17 1 1 1 20 16 1 1 1 1 66

제5장 SVM 소프트웨어 실험 결과 KP 알고리즘과 RBF커널 함수를 사용한 부동소수점 알고리즘 실험을 통해 서 단지 1개의 테스트 패턴을 오분류하였다. 표 5.3은 고정소수점 알고리즘을 사용하여 다양한 데이터 폭과 커널 스케일율에 따라 얻은 테스트오차의 수를 나타내고 있다. 데이터의 소수 부분은 12비트로 고정하였다. 데이터 폭이 14 비트로 감소할지라도 256의 비율로 커널 스케일을 한다면 테스트 오차는 1로 감소한다. 데이터의 차원이 커진다면 커널 스케일율을 크게 정해주어야 좋은 결과를 얻을 수 있다. 비교적 적은 60개의 특징을 가진 수중 음파 데이터에서 는 커널 스케일 방법의 효과가 덜 했다. 앞서 기술한 표 5.2와 마찬가지로 표 5.4에서 백혈병 데이터에 대해서도 부 동소수점 연산과 고정소수점 연산을 사용한 결과를 나타내고 비교하였다. 이 실험에서도 KP학습과 RBF커널 함수를 사용하였다. 표의 두번째 열의 aa-bbcc-dd 에서 aa는 데이터의 소수비트폭이고 bb는 정수비트폭을 표시하고 cc는 RBF함수 LUT의 어드레스 비트 중 소수비트폭, dd는 RBF함수 LUT의 어드레스 비트 중에 정수비트폭을 나타낸다. 백혈병 데이터의 차원이 수중 음파 데이터 와 비교하여 상당히 크기 때문에 표 5.2보다 마진값과 라그랑지안 계수의 차이 가 더 많이 발생함을 알 수 있다. 또한 학습이 조기에 수렴했을 경우에 결과가 우수하였고 support vector의 개수는 가장 많았다. 67

제5장 SVM 소프트웨어 실험 결과 표 5.4. 백혈병 데이터에 대한 부동소수점 연산과 고정소수점 연산 알고리즘 실험 Table 5.4. Floatng and fxed-pont algorthm experments for leukema dataset nsv teratons errors dev(m FL -m FI ) dev(α FL -α FI ) Floatng-pont 20 27 1 14-10-14-10 20 27 1 24.33 0.00006 Fxed- pont 14-4-10-4 8 1000+ 17 973.4 19.86 12-10-12-10 20 27 1 22.09 0.003 12-8-12-8 11 1000+ 16 982.7 252.8 10-4-6-4 6 1000+ 16 973.3 21.01 68

제5장 SVM 소프트웨어 실험 결과 5.3. 비선형 채널 등화 실험 5.3.1. 비선형 채널 등화기 높은 데이터를 전송하는 밴드가 제한된 통신 채널은 자주 분산 시간 응답 으로 인하여 심볼간 간섭을 일으킨다 [19]. 송신기, 채널, 수신기에서 발생하는 모든 미지의 비선형 효과들은 유한 임펄스 응답 (fnte-mpulse response, FIR) 필 터로 모델링 가능하다. ~ x ( n) = xˆ( n) = N k= 0 P p= 0 h u( n k) c ~ x ( n) x( n) = xˆ( n) + e( n) k p p (5.1) 식 (5.1)에서 e는 평균이 0이고 분산이 σ e 2 인 가우시안 분포 잡음이고 h k 는 채 널 계수이다. 전달된 심볼 신호열 u(k)는 통계적으로 독립적이고 {+1, 1}의 범 위에서 균등한 확률을 가지는 신호이다. 69

제5장 SVM 소프트웨어 실험 결과 e(n) u(n) Nonlnear channel xˆ ( n) + + z -1 z -1 x(n) x(n-1) x(n-m+1) Equalzer uˆ ( n D) 그림 5.4. 일반적인 횡단 등화기의 구조 Fg. 5.4. Schematc dagram of a generc transversal equalzer 그림 5.4에서 보이는 횡단 등화기는 가장 일반적인 등화기의 형태이다. 등 화기의 역할은 채널 출력 벡터 x(t)가 주어졌을 때 u(t D)의 추정값인 û (t D) 을 구하는 것이다. 여기에서 D는 실제의 채널을 통하여 전송된 신호의 시간의 지연을 나타낸다. M은 등화기의 차수(order)라고 할 때, 채널 출력을 식 (5.2)와 같이 구성한다. x ( t) + )] T = [ x( t), x( t 1),..., x( t M 1 (5.2) 다양한 지연 D를 두는 이유는 u(t D)와 x(t) 사이에 존재하는 상관도가 D 에 따라서 변화하고 이로 인해서 등화기의 성능이 달라지기 때문이다. 길이가 N인 채널이 ISI를 가지고 등화기가 (M 1)개의 지연을 가지고 있을 때, 식 (5.3) 70

제5장 SVM 소프트웨어 실험 결과 과 같이 등화기의 출력은 (M + N 1)개의 채널 입력에 의존하게 된다. ˆ ( n D) = f ( u( n), u( n 1),..., u( n M N + 2)) u (5.3) 식 (5.3)은 등화기를 위한 신호가 2 M+N 1 개의 점들을 가지고 있다는 것이다. 그 점들은 다양한 입력들의 잡음이 없는 채널의 출력들이고 D의 값에 따라서 분류된다. {u(n)}이 독립적이라고 가정할 때 D max = M + N 2보다 큰 지연을 갖는 등화기는 좋지 않은 결과들을 얻게 된다. 그 이유는 u(n D)이 u(n),, u(n M N + 2)에 독립적이기 때문이다. 5.3.2. 실험 결과 첫 번째 실험 모델은 비선형 채널 xˆ (n) = ~ x (n) 0.9 ~ x 3 (n), ~ x (n) = u(n) + 0.5 2 u(n 1)이다. 부가되는 백색 잡음의 분산 σ e = 0.2, M = 2, RBF 커널의 파라미터 σ 2 = 0.5이다. D = 0일 경우를 모델 1, D = 2일 때를 모델 2라고 명명하도록 한다. 결과는 10번 실험 후에 평균값을 취하고 500개의 샘플로 학습을 하고 2400개의 샘플로 테스트를 한다. 71

제5장 SVM 소프트웨어 실험 결과 1 0.8 x(n-1) 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 x(n) 그림 5.5. 모델 1에 대한 데이터의 분포와 결정 평면 Fg. 5.5. Dstrbuton of data and decson surface for Model 1 1 0.8 x(n-1) 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 x(n) 그림 5.6. 모델 2에 대한 데이터의 분포와 결정 평면 Fg. 5.6. Dstrbuton of data and decson surface for Model 2 72

제5장 SVM 소프트웨어 실험 결과 그림 5.5와 그림 5.6은 학습 샘플과 KA에 의하여 학습한 결정 평면의 그림 이다. u(t D) = +1인 샘플은 O로 표시하고 u(t D) = 1인 샘플은 X로 표시하 였다. D = 0일 때 샘플들의 분포가 밀집되어 있고 결정 평면이 더 굽어지는 형 상을 띠는 것을 그림으로부터 알 수 있다. 그림 5.7에서는 RBF 커널 함수의 계수인 σ 2 의 변화가 결정 평면에 어떤 영 향을 주는지를 실험하여 보았다. 이 실험에서는 Anguta et al. [3]의 논문에서 사 용한 32개의 학습샘플과 2900개의 테스트샘플의 모델 1에 대하여 수행되었다. 그림에서 실선으로 표시된 곡선은 결정평면을 나타내고, 점선으로 표시된 곡선 은 마진평면을 나타내며, support vector에 해당하는 샘플은 원으로 표시되어 있다. 그림에서 보는 것과 같이, RBF의 계수 σ가 더 커질수록 결정평면은 평평해지는 경향이 있으므로, 앞서 그림 5.5와 같이 데이터가 밀집되어 있을 때는 σ를 더 작게 설정하여야 분류 오차를 감소시킬 수 있다. σ 2 = 0.1일 경우에는 마진평면 밖에 있음에도 support vector로 판단한 샘플이 있는 것을 알 수 있고, σ 2 = 10일 경우에는 결정평면이 불연속적으로 형성되었다. 본 논문에서는 가장 안정적인 성능을 보이는 σ 2 = 1 인 RBF 커널 함수를 사용하였다. 73

제5장 SVM 소프트웨어 실험 결과 x(n-1) x(n) (a) x(n-1) x(n) (b) 74

제5장 SVM 소프트웨어 실험 결과 x(n-1) x(n) (c) 그림 5.7. 채널 모델 1에서 RBF 커널함수의 계수의 변화에 따른 결정평면 (a) σ 2 = 0.1일 때, (b) σ 2 = 1일 때, (c) σ 2 = 10일 때 Fg. 5.7. Decson surface for Model 1 usng varous coeffcents of RBF kernel functon (a) For σ 2 = 0.1, (b) For σ 2 = 1, (c) For σ 2 = 10 그림 5.8에서는 32개의 학습샘플을 사용한 모델 2에 대하여 RBF 커널 함수 의 계수인 σ 2 의 변화 실험을 수행하였다. σ 2 = 10일 때 마진평면이 불연속이었고, σ 2 = 1일 때 가장 안정적인 분류 성능을 보이는 것을 알 수 있었다. 75

제5장 SVM 소프트웨어 실험 결과 x(n-1) x(n) (a) x(n-1) x(n) (b) 76

제5장 SVM 소프트웨어 실험 결과 x(n-1) x(n) (c) 그림 5.8. 채널 모델 2에서 RBF 커널함수의 계수의 변화에 따른 결정평면 (a) σ 2 = 0.1일 때, (b) σ 2 = 1일 때, (c) σ 2 = 10일 때 Fg. 5.8. Decson surface for Model 2 usng varous coeffcents of RBF kernel functon (a) For σ 2 = 0.1, (b) For σ 2 = 1, (c) For σ 2 = 10 Anguta et al. [3]의 실험 결과와 비교하여, KA의 결과가 우월하다는 것을 알 수 있었다. KA 학습을 사용한 CSVM은 모델 1에 대하여 17.75%와 모델 2에 대하여 3.95%의 오차율을 얻는다. 모델 2에 대한 결과는 Anguta et al. [3]의 논 문에서 실험한 4.2%을 능가하였고 모델 1의 결과는 유사했다. RBF 커널함수를 사용한 SVM의 성능과 비교하기 위하여 다항 함수 커널의 SVM에 대하여 같은 실험을 수행하였다. 표 5.5에서는 채널 모델 1과 모델 2에 77

제5장 SVM 소프트웨어 실험 결과 대하여 RBF 커널의 계수 값 σ 2 을 변화시키면서 실험을 하였다. 표 5.6은 다항 함수의 계수 값 p를 변화시키면서 실험을 수행하였다. 두 개의 표를 비교하면, 최고의 오차율은 계수 5의 RBF 커널을 사용하였을 때 얻는 것을 알 수 있었다. 또한 RBF 커널의 SVM은 계수에 따라서 오차율의 차이가 심하지 않은 반면, 다 항함수 커널을 사용한 SVM은 특히 모델 2에서, 계수 값에 따라서 오차율의 차 이가 상당히 컸다. 표 5.5. 다양한 계수 값의 RBF 커널에 대한 오차율 Table 5.5. Error rate of RBF kernel for dfferent coeffcents 계수값 모델 0.1 0.5 1 5 10 모델 1 51.3% 49.5% 36.9% 27.8% 32.5% 모델 2 5.3% 4.2% 4.2% 3.95% 4.9% 표 5.6. 다양한 계수 값의 다항함수 커널에 대한 오차율 Table 5.6. Error rate of polynomal kernel for dfferent coeffcents 계수값 모델 1 2 4 6 8 10 모델 1 41.4% 36.8% 48.5% 45.9% 46.4% 44.2% 모델 2 4.4% 51.4% 15.6% 48.6% 5.4% 7.9% 78

제5장 SVM 소프트웨어 실험 결과 10 0 10-1 10-2 BER 10-3 10-4 10-5 QP KA 10-6 5 10 15 20 SNR (db) 그림 5.9. KA 학습 알고리즘과 QP 방법을 사용한 실험 결과의 평균 BER Fg. 5.9. Average BER for the KA learnng algorthm vs. QP method 두 번째 실험은 RBF 커널의 KA학습을 사용할 경우와 QP 방법을 사용할 경우에 대하여 SNR에 따른 비트 에러율(bt error rate, BER)을 비교하였다. 채널 모델은 xˆ (n) = ~ x (n) + 0.2 ~ x 2 (n), ~ x (n) = 0.3482 u(n) + 0.8704 u(n 1) + 0.3482 u(n 2)을 사용하였고 파라미터는 M = 3, D = 1, σ 2 = 1로 설정하였다. 학습 샘플수는 500개를 사용하였고 테스트 샘플은 2000개를 사용하여 10번 실험하였다. 그림 5.9와 같이 5-10dB 범위에서는 KA 알고리즘과 QP 방법을 사용하여 학습한 Sebald et al. [9]의 논문의 결과와 유사했다. 15dB 이상의 범위에서는 KA의 성능 이 QP보다 더 우월했다. RBF 커널을 사용한 학습은 Sebald et al. [9]의 논문에서 사용한 다항 커널을 사용한 경우보다 더 좋은 결과를 보이는 것을 알 수 있었 79