Introduction to Pattern Recognition

Posted 2011.10.25 15:03
출처: http://drcarter.tistory.com/3

1. 패턴인식의 정의


패턴인식(Pattern Recognition)은 인지과학(Cognitive Science)과 인공지능(Artificial Intelligence) 분야에 속하는 문제 중 하나이다. 인지과학은 심리학, 컴퓨터 과학, 인공지능, 신경생물학과 언어학, 철학을 이용하여 지능과 인식의 문제를 다루는 포괄적인 학제적 과학 분야를 말하며, 인공지능은 인간의 학습능력과 추론능력을 인공적으로 모델링하여 외부 대상을 지각하는 능력, 나아가 자연언어와 같은 구문적 패턴까지 이해하는 능력 등을 컴퓨터 프로그램으로 구현하는 기술을 말한다. 

인공지능에 관한 연구는 현재 지능형 시스템(Intelligence System)이라는 인공지능에 기반한 정보 시스템 분야로까지 발전하고 있다. 정보화 시대에 쉽게 얻을 수 있는 수 많은 데이터들을 적절히 가공하는 것은 물론 정보의 표현과 처리에도 지능형 시스템이 적용되고 있으며 금융, 제조, 스포츠, 서비스 분야 등의 비정보기술 부문에까지 널리 이용되고 있다. 

패턴인식은 공학적 접근법을 이용하여 인공지능의 실제 구현 문제인 센싱된 대상을 인식하는 문제를 주로 다룬다. 패턴인식을 여러 방식으로 정의할 수 있겠지만 "계산이 가능한 기계적인 장치(컴퓨터)가 어떠한 대상을 인식하는 문제를 다루는 인공지능의 한 분야"라고 정의한다.

외국의 패턴인식 분야 대가들이 여러 문헌에서 패턴인식에 대하여 나름대로 정의한 것들을 몇 가지 소개한다. 여기에 소개하는 문헌들은 패턴인식 분야에서 아주 유명한 문헌들이기도 한다.
■ 여러 유명 문헌에서 소개하는 패턴인식의 정의

"The assignment of a physical object or event to one of several prespecified categories(물리적 객체 혹은 사건에 이미 정해진 몇 가지 카테고리 중의 하나로 할당하는 것)" 

-Duda, Hart, Stork의 "Pattern Classification" 

"A problem of estimating density function in a high-dimensional space and dividing the space into the regions of categories or classes(다차원 공간 내에서 밀도 함수를 추정하고 공간을 카테고리 혹은 클래스 영역으로 나누는 문제)" 

- Keinosuke Fukunaga "Introduction to Statistical Pattern Recognition (Computer Science and Scientific Computing Series)"

"Given some examples of complex signals and the correct decisions for them, make decisions automatically for a stream of future examples(복잡한 신호의 몇 가지 표본과 이들에 대한 정확한 결정이 주어질 때, 연이어 주어지는 미래 표본들에 대하여 자동적으로 결정을 내리게 하는 것)" 

- B. Ripley, Pattern Recognition and Neural Networks,Cambridge University Press, Cambridge, 1996.

"The science that concerns the description or classification (recognition) of measurements(척도의 설명 혹은 분류(인식)와 관련된 과학)" 

- R. Schalkoff "Pattern Recognition. Statistical, Structural, and Neural Approaches"John Wiley & Sons, Inc., 1992. ISBN 0-471-55238-0

"The process of giving names to observations x(관측치 x에 이름 를 부여하는 과정)" 

- J. Schuermann, Pattern classification, a unified view of statistical and neural approaches,John Wiley & Sons, New York, 1996.

"Pattern Recognition is concerned with answering the question "What is this?"(패턴인식은 다음 질문에 답하는 것이다. "이것이 무엇인가?")" 

- Morse

2. 특징과 패턴

패턴이란 무엇일까? 패턴을 정의하기 전에 우선 앞으로 여러분들이 지겹도록 듣게 될 특징이 무엇인지부터 이야기하도록 하겠다. 

특징이란 어떤 객체가 가지고 있는 객체 고유의 분별 가능한 측면(aspect), 양(quality) 혹은 특성(characteristic)이라고 정의될 수 있다. 특징은 색깔과 같은 상징 기호가 될 수도 있고, 높이, 넓이, 무게와 같은 수치적인 값이 될 수도 있다. 특징이 하나 이상의 수치 값을 가질 경우에는 특징 벡터(feature vector)라고 하는 d-차원의 열 벡터로 표현된다. 그리고 이러한 특징 벡터가 정의되는 d-차원의 공간을 특징 공간(feature space)이라고 한다. 

그러므로 인식 대상이 되는 객체들은 특징 공간상에서 특징 벡터가 형성하는 점들로 표현된다. 특히, 특징 공간상에 표현된 점들로 표현된 특징들의 그림을 "분산 그림(scatter plot)"이라고 한다. 물론 3차원 특징 공간까지만 시각적으로 표현 가능하다. 특징 공간이 4차원 이상이 되면 플롯시켜 볼 수는 없지만, 엄연히 특징 벡터 공간 상의 한 점으로 존재한다. 


[그림 2-1] 특징 벡터, 특징 공간, 분산 플롯

그럼, 패턴이란 무엇일까? 패턴이란 개별 객체의 특색(traits) 혹은 특징(features)을 의미하며, 특징을 모아놓은 집합으로 정의할 수 있다. 즉, 특징과 패턴은 유사한 개념이지만 특징들이 모여서 패턴을 이루게 된다고 볼 수 있다. 패턴인식에서 패턴은 관측된 특징 벡터 x와 이 특징 벡터가 속한 클래스 ω로 이루어진 변수 쌍 {x,ω}으로 표현된다. 여기서 클래스(class)는 카테고리(category), 그룹(group), 라벨(label)이라고도 하는데 같은 소스로부터 발생된 공통된 속성 혹은 특징 집합을 공유하는 패턴 집합을 의미한다. 

패턴인식에서 패턴을 이루는 특징 벡터를 어떤 것으로 선택할 것인가? 의 문제는 중요한 결정 사항이다. 어떠한 패턴을 이루는 개별 특징의 선택은 패턴인식 알고리즘의 결정과 더불어 인식률에 결정적인 영향을 미친다. 그러므로 특징은 서로 다른 클래스 표본간에 분별 가능한 성질을 되도록이면 많이 가지도록 선택되어야 한다. 즉, 같은 클래스로부터의 표본은 동일하거나 유사한 특징 값을 가져야 하며, 다른 클래스로부터 취해진 표본은 다른 클래스와 서로 다른 특징 값을 가져야 할 것이다. [그림 2-2]는 좋은 특징과 나쁜 특징의 예를 극단적으로 보여주고 있다. 


[그림 2-2] 좋은 특징과 나쁜 특징

그리고, 패턴을 이루는 특징 벡터는 특징 공간상에서 분포하는 유형에 따라 다음과 같이 분류가 가능하다.

① 선형 분리 가능한 유형
② 비선형 분리 가능한 유형
③ 높은 상관을 가진 유형
④ 멀티 모달 유형 

[그림2-3]은 패턴의 유형에 따른 분산 그림이다. 선형 분리 가능한 유형으로 특징 패턴들이 분포될 때 각 클래스를 분류하기가 당연히 쉬울 것이다.


[그림 2-3] 패턴의 유형

또한, 패턴은 시변성(시간에 따라 변하는)에 따라 분류하면, 정적 패턴과 동적 패턴으로 나눌 수 있다. 정적 패턴은 시간에 따른 패턴의 변화가 없는 패턴으로 보통 카메라로 획득된 영상인 지문, 홍채, 정맥, 필기체 문자 등 패턴인식의 대상이 되는 대부분의 패턴이 정적 패턴에 속한다. 그러나 많은 분야에서 시간에 따라 변하는 패턴(시계열 패턴)을 관측할 수 있다. 

가장 대표적인 동적 패턴이 바로 음성 신호이다. 음성은 시간에 따라 그 특징 패턴이 변한다. 음성 말고도 생체 공학에서의 EEG(뇌전도), ECG(심전도) 신호, 로보트 공학에서의 모바일 로보트 네비게이션 분야 그리고 생체 정보 공학(Bioimfomatics)에서의 DNA 서열 할당과 같은 문제에서는 동적 패턴이 인식의 대상 패턴이 된다. 

3. 패턴인식 시스템의 구성 요소와 설계 사이클

이제, 패턴인식 시스템은 어떠한 요소들로 이루어져 있는지, 그리고 설계 순서는 어떠한 과정을 거쳐 이루어지는지 알아보도록 하자. 우리가 편리하게 사용하는 공학적인 기술 중 많은 것이 자연계에서 아이디어를 얻어 이를 응용하고 모델링하여 사용하고 있다. 패턴인식 과정은 앞에서 이야기한 것과 같이 인간이 어떠한 대상을 인식하는 과정과 유사한 과정으로 이루어진다. 

간단히 패턴인식 시스템의 구성 요소에 따른 처리 과정을 그림으로 나타내면 [그림 2-4]와 같다. 


[그림 2-4] 패턴인식 시스템의 구성요소와 처리과정

(1) 패턴인식 시스템 설계 5단계

패턴인식 시스템은 다음과 같은 설계 단계를 따른다. 

1단계 : 데이터 수집 단계 
패턴인식 과정에서 가장 많은 시간이 소비되는 지루한 과정이다. 그러나 안정된 패턴인식 성능을 얻기 위해서 꼭 필요한 단계이기도 하다. 이 단계에서는 얼마나 많은 표본 데이터가 안정된 성능에 필요 충분한가를 고려하여 데이터를 수집하여야 한다. 

2단계 : 특징 선택 단계
앞에서 이야기 한 것처럼 패턴인식 시스템의 성능에 결정적인 영향을 미치는 단계이다. 대상 패턴에 대한 충분한 사전 분석을 통하여 어떠한 특징을 선택할 것인가를 결정하여야 한다. 당연히 garbage in이면 garbage out 이다. 

3단계 : 모델 선택 단계 
패턴인식을 위한 여러 접근법 중에서 어느 모델을 어떠한 알고리즘을 이용하여 어떻게 구성할 것인가를 결정하는 단계이다. 특징 선택과 마찬가지로 사전에 특징에 관한 선험적인 지식이 요구되며, 각 접근법에 따라 모델에 필요한 각종 파라미터의 설정이 필요하다. 

4단계 : 학습 단계
수집된 데이터로부터 추출된 특징 집합을 이용하여 선택된 모델에 대하여 비어 있는 브랭크(blank) 모델을 학습을 통하여 완전한 모델로 만드는 단계이다. 학습은 그 방법에 따라서 교사 학습, 비교사 학습 그리고 강화 학습이 있다.

5단계 : 인식 단계
패턴인식의 마지막 단계로 임의의 특징이 주어질 때, 이 특징이 속한 클래스 혹은 카테고리를 결정하는 단계이다. 

4. 패턴인식의 유형과 분류기

(1) 문제의 유형

패턴인식에서 해결해야 하는 문제의 유형은 다음과 같이 4가지로 요약할 수 있다. 

분류(Classification)
분류는 어떠한 대상 객체를 특정한 클래스에 할당하는 것을 말한다. 패턴인식의 대부분이 이러한 분류의 문제이다. 또한 분류의 문제를 다루는 패턴인식 시스템의 출력은 모호한 퍼지(Fuzzy)적인 결과가 아니라 정수 라벨의 명확한 결정이 요구된다. 예를 들어, 품질 검사 분류는 제품의 합격/불합격과 같은 명확한 결정을 요구하는 분류의 대표적인 예이다. 

회귀(Regression)
회귀란 분류를 일반화한 것을 말한다. 여기서 일반화(generalization)라는 말은 학습 데이터로부터 모델링된 모델로 시험 데이터에서도 그 모델로부터 유효한 결과를 얻을 수 있는 경우에 붙일 수 있는 말이다. 회귀를 통하여 우리는 패턴인식 시스템의 출력으로부터 실수 라벨로 추정된 결과를 얻을 수 있다. 즉, 회귀를 이용하면 예측이 가능하게 되는데, 예를 들어, 어떤 회사의 주식에 대한 배당 가치를 예측하는 문제는 과거의 실적과 주가에 근거하여 추정하는 회귀의 문제에 해당한다. 더 엄밀한 회귀라는 용어의 기원은 뒤에 상세히 설명하도록 하겠다.

군집화(Clustering)
군집화는 그냥 원문 그대로 "클러스터링"이라고 보통 말하는데 어떤 집합을 의미 있는 복수개의 그룹들로 조직하는 문제를 말한다. 군집화 시스템의 출력은 객체들이 속한 클래스가 된다. 군집화는 생명체를 종으로 분류하는 경우처럼 때로는 계층적으로 처리될 수도 있다. 

서술(Description)
서술은 대상 객체를 일련의 원형(prototype) 혹은 기본형(primitive)으로 표현하는 문제를 말한다. 패턴인식 시스템은 객체에 대한 구조적 혹은 언어적인 서술을 행할 수도 있다. 예를 들어 ECG(심전도) 생체 신호를 P, QRS 그리고 T의 항으로 라벨을 붙이는 경우가 이에 해당한다. 

한편, 패턴인식의 대부분을 이루는 분류 작업은 분류기에 의하여 이루어진다. 분류 작업이란 특징 벡터들로 이루어진 특징 공간을 라벨이 있는 클래스들 간의 결정 영역으로 분할(partition)하는 것을 말한다. 이 때, 결정 영역의 경계들을 결정 경계(decision boundaries)라고 한다. 결국, 특징 벡터 x의 분류는 어느 결정 영역에 이 특징 벡터가 속해있는지를 결정하고, x를 이 클래스중의 하나로 할당하는 것이다. 


[그림 2-5] 결정 경계

(2) 분류기

분류기는 [그림 2-6]과 같이 판별 함수(discriminant functions)의 집합으로 표현될 수 있다. 

만약  이라면 특징 벡터 X를 클래스에 속한다고 결정하였을 경우 [그림 2-6]과 같다.


[그림 2-6] 판별 함수에 의한 분류

5. 패턴인식의 접근법

(1) 패턴인식의 접근법

통계적 접근법
통계적 접근법은 통계적 모델을 기반으로 하여 패턴을 분류하는 방법이다. 패턴들의 통계적 모델은 해당 클래스에서의 확률 밀도 함수가 되며, 베이즈의 결정 규칙을 이용하여 분류하여 인식한다. 

신경망 접근법
신경망 접근법은 패턴의 분류를 입력 자극(pattern)에 대한 처리 단위(neurons)로 이루어진 망(network)의 응답 과정으로 분류를 행하는 접근법이다. 이 때, 패턴의 정보(knowledge)는 시냅스의 연결 강도 가중치들로 저장된다. 신경망 접근법은 학습이 가능하고, 알고리즘적이지 않으며, 블랙박스와 같이 취급 가능하다. 또한 사전 지식을 최소화하고, 뉴런의 층이 충분하면 이론적으로 어떤 복잡한 결정 영역도 만들어 낼 수 있는 매우 매력적인 방법이다. 

구조적 접근법
구조적 접근법은 패턴의 구조적인 유사성을 조사하여, 이를 이용하여 분류를 행하는 방법이다. 이 때, 패턴의 정보(knowledge)는 형식 문법 혹은 그래프적인 관계 설명으로 표현된다. 구조적 접근법은 분류뿐만 아니라 해당 객체를 서술하기 위해서도 사용된다. 구조적 접근법은 유사한 부분 패턴들로부터 구축된 복잡한 패턴들의 계층적 서술을 수식화하는 접근법이라고 할 수 있다. 

[그림 2-7]은 OCR 패턴 A문자에 대하여 위의 3가지 패턴인식 접근법을 아주 잘 설명하고 있는 그림이다.


[그림 2-7] 패턴인식의 접근법

6. 패턴인식의 응용 분야

패턴인식 기술은 알게 모르게 우리의 실생활에 광범위하게 활용되고 있다. 축적된 매출 기록에서 구매 패턴을 파악하여 판매 전략을 수립하고 웹사이트를 분류하는 것과 같이 자료로부터 정보를 추출하는 업무에도 패턴인식 기술이 이용되며, DNA 유전자 염기 배열의 분석 같은 분야에도 패턴인식 기술이 적용된다. 

(1) 패턴인식의 응용 분야

대표적인 응용 분야로는 문자인식, 생체인식과 인간 행동 패턴 분석, 의료영상 분석 (medical diagnosis) 및 진단 시스템, 도면 인식 (line drawing recognition), 예측 시스템, 보안과 군사 분야 등이 있다. 

문자 인식 분야 
자동 우편물 분류기, 스캐너로 받아들인 텍스트 이미지를 컴퓨터에서 편집 가능한 코드화된 문자로 변환하는 장치, 필기체 문자 인식, 수표 및 지폐 인식, 차량 번호판 인식 등에 많이 활용된다.


[그림 2-8] 자동 우편물 분류기

생체 인식과 인간 행동 패턴 분석 분야 
음성인식, 지문인식, 홍체인식, 얼굴인식, DNA 매핑, 보행 패턴 분석 및 분류, 발화 습관 분석 및 분류 등에 사용된다.

진단 시스템 분야 
자동차 오동작 진단, 의료 진단, EEG(뇌전도), ECG(심전도) 신호 분석 및 분류 시스템, X-Ray 판독 시스템 (예 : X-Ray 판독의 10-30%가 오판독의 가능성이 있는데 이를 적절한 영상 분석 처리를 통하면 이들 중 2/3는방지 가능)등에 많이 사용된다.


[그림 2-9] ECG 신호 

예측 시스템 분야 
인공 위성 데이터에 기반한 날씨 예측, 지진 패턴 분석과 예측 시스템, 주가 예측 시스템에 활용된다.

보안과 군사 분야 
네트워크 트래픽(traffic) 패턴 분석을 통하여 컴퓨터 공격 확인, 물품 자동 검색 시스템, 인공위성 영상 분석을 통한 테러리스트 캠프 혹은 지형 목표물 추적 공격, 레이더 신호 분류, 항공기 피아(彼我)식별 시스템에 사용된다.


[그림 2-10] 물품 검색과 목표물 추적

(2) 패턴인식 관련 분야



7. 패턴인식의 응용 예

(1) 간단한 영문자 인식 시스템

영문자 L,P,O,E,Q를 인식하는 인식 시스템의 예를 들어 특징의 의미와 비교적 단순한 구조의 트리-구조 분류기에 관하여 알아보겠다. 먼저, 특징을 무엇으로 할 것인가를 결정하여야 한다. L,P,O,E,Q 문자의 구조를 분석하여 보니, 다음과 같은 특징 척도를 설정하면 각 문자에 대하여 분류가 가능할 것 같다. 



그리고, 인식은 [그림 2-11]과 같은 간단한 트리-구조의 분류기를 사용하여 문자를 분류할 수 있다. 


[그림 2-11] 트리-구조의 단순한 분류기

(2) 자동 어류 분류 시스템

이 절에서는 고기들을 자동으로 분류하는 공장에서 고기의 종류를 자동으로 분류하는 시스템을 구축하는 예를 생각해 보겠다. 자동 분류 시스템의 구성 요소는 다음과 같이 구성될 것이다. 


[그림 2-12] 자동 어류 분류 시스템의 구성

일단, 고기는 연어(salmon) 혹은 농어(sea bass) 만이라고 가정한다. 비전 시스템으로부터 분류 영역에 들어오는 새로운 고기에 대한 영상을 획득하고, 영상 처리 알고리즘을 통하여 영상의 명암값을 정규화하고 영상에서 배경과 고기를 분리하는 분할(segmentation) 전처리 과정을 거친다. 그리고 평균적으로 농어가 연어보다 더 커다는 사전 지식을 바탕으로 분할된 영상으로부터 고기의 길이를 측정하는 특징 추출이 끝나면, 두 종류의 고기에 대한 표본 집합에 대하여 길이의 분포를 계산하고 분류 오류를 최소로 하는 결정 경계의 문턱값을 [그림 2-13]과 같이 결정한다. 이렇게 어류 분류 시스템을 구성한 결과 분류율이 60% 라는 실망스러운 결과를 얻을 수 있었다. 


[그림 2-13] 고기의 길이만을 특징으로 사용한 경우

패턴인식 시스템의 성능이 안정적이기 위해서는 인식률이 95%이상은 되어야 한다. 그래서 좀 더 안정된 인식률을 얻기 위해서 고기의 특징들을 다시 관찰해보니, 폭, 면적, 입에 따른 눈의 위치 등의 특징들이 관측되었다. 그러나 이러한 특징들을 분류 정보로 활용하기에는 부족한 특징들이였다. 좀 더 관찰해보니, 고기의 평균 명암 스케일들이 [그림 2-14]와 같이 결정 경계가 결정되어 좋은 특징이 됨을 찾아내었다. 


[그림 2-14] 고기의 평균 명암 스케일만을 특징으로 사용한 경우

이제, 좀 더 인식률을 올리기 위해서 길이와 평균 명암 스케일을 조합하여 [그림 2-15]와 같이 2차원 특징 벡터를 만들었다. 간단한 선형 판별 함수를 이용하여 분류한 결과 비로소 95.7%의 인식률을 얻을 수 있었다.


[그림 2-15] 길이와 평균 명암 스케일을 특징으로 사용한 경우

비용 Vs 분류율

우리가 만든 선형 분류기는 전체 오인식률을 최소화하도록 설계되어졌다. 그러나 과연 이 분류기가 어류 처리 플랜트에 대한 가장 객관적이고, 이상적인 판별 함수일까? 연어를 농어로 잘못 분류할 비용은 최종 고객이 우연히 농어를 구입할 때 맛있는 한 마리의 연어를 발견하고 좋아하는 경우이고, 농어를 연어로 잘못 분류할 비용은 최종 고객이 연어의 가격으로 농어를 구입했다는 것을 발견하고 질겁하는 경우이다. 따라서 우리는 이 비용 함수를 최소화하기 위해서 [그림 2-16]과 같이 결정 경계를 조정할 필요가 있다. 


[그림 2-16] 비용 개념의 적용

일반화의 문제

우리의 선형 분류기의 인식률이 95.7%로 설계 사양은 충족하지만 신경망 알고리즘을 이용하면 분류 시스템의 성능을 개선할 수 있다. 5개의 은닉층을 가지고 로그와 하이퍼볼릭 탄젠트 활성화 함수를 조합하고 Levenberg-Marquardt 알고리즘으로 학습하니, [그림 2-17]과 같은 결정 경계를 가지고 99.9975%의 환상적인 인식률을 얻을 수 있었다. 


[그림 2-17] 비선형 결정 경계 

이제, 우리가 만든 자동 어류 분류 시스템의 각 요소들을 결합하고, 어류 분류 플랜트에 적용하였다. 그런데, 며칠 후, 플랜트의 관리자에게서 전화가 왔다. 고기의 25%가 잘못 분류되고 있다고 알려왔다. 도대체 무엇이 잘못된 것일까?
신고

'Enginius > Machine Learning' 카테고리의 다른 글

Least Squres  (2) 2011.10.26
퍼셉트론 패턴인식 데모  (0) 2011.10.25
Introduction to Pattern Recognition  (0) 2011.10.25
Expectation of X^n; X~N(u,sigma^2)  (0) 2011.10.24
using FLDA to classify IRIS data set  (0) 2011.10.14
HMM viterbi algorithm  (0) 2011.10.13
« PREV : 1 : ··· : 420 : 421 : 422 : 423 : 424 : 425 : 426 : 427 : 428 : ··· : 586 : NEXT »