제 4 장 패턴인식 이해.

Presentation on theme: "제 4 장 패턴인식 이해."— Presentation transcript:

1 제 4 장 패턴인식 이해

2 패턴 인식이란 ? 패턴은 일정한 이름(label)을 갖는 물체, 처리 과정, 또는 이벤트 등을 총칭한다 패턴 인식
물리적인 물체나 이벤트 등에 사전에 정의된 어떤 이름을 할당하는 작업 -- Duda & Hart 인공 지능의 한 영역 인간 지능의 많은 부분이 패턴 인식 작업에 구현된다 : 자기 조직화 (self-organization) 작업의 본질적인 부분 2

3 Examples of Patterns 3

4 패턴인식의 응용 의학 분야의 진단 및 처방 영상인식 음성인식 Genome Sequence Analysis
Medical imaging, EEF, ECG, X-ray mammography 영상인식 공장 자동화, Robot Navigation 얼굴식별, Gesture Recognition Automatic Target Recognition 음성인식 Speaker identification Speech recognition Genome Sequence Analysis 4

5 생체 인식 불변의 생체 특징을 이용한 사람 식별 정적 패턴 동적 패턴 출입통제 전자상거래 인증 지문, 홍채, 얼굴, 장문
손등의 정맥 동적 패턴 Signature, 성문 Typing pattern 출입통제 전자상거래 인증 5

6 제스쳐 인식 가상현실에서 가상 객체 제어 원거리에서 동작 가능 펜 컴퓨터에서 텍스트 에디팅
제스쳐 입력을 통해 원격에서 제어 t 손 제스쳐를 통해 TV 제어 펜 컴퓨터에서 텍스트 에디팅 사인 언어 (Sign language) 번역 6

7 데이터로부터 패턴의 추출 Data Mining
데이타 의사결정 정보 인구통계 Point of Sale ATM 금융통계 신용정보 문헌 첩보자료 진료기록 신체검사기록 A상품 구매자의 80%가 B상품도 구매한다 (CRM) 미국시장의 자동차 구매력이 6개월간 감소 A상품의 매출 증가가 B상품의 2배 탈수 증상을 보이면 위험 광고전략은 ? 상품의 진열 최적의 예산 할당은 ? 시장점유의 확대방안은 ? 고객의 이탈 방지책은 ? 처방은 ? 국내 사례: 신용카드 사용 패턴의 학습에 의한 분실 카드 사용 방지 7

8 자율 주행 차량 (DARPA’s GrandChallenge contest)
8

9 단백질 구조 분석 9

10 패턴 인식 문제의 유형들 분류 (Classification) 군집화 (Clustering) 회귀 분석 (Regression)
From Ricardo Gutierrez-Osuna,Texas A&M Univ. 패턴 인식 문제의 유형들 분류 (Classification) 물체에 이름 (label) 할당 Output: label Ex: 제품 제조 과정에서 품질 조정을 위해 제품에 ‘good’ 또는 ‘bad’ 레이블 할당하는 작업 군집화 (Clustering) 각 물체들을 의미 있는 그룹들에 포함시키는 작업 Output: grouping of objects Ex: taxonomy of species 회귀 분석 (Regression) 관측값들로 부터 예측값 생성 Ex: predict stock price, future prediction 설명 (Description) 물체를 기본 요소들의 적절한 결합으로 설명하는 작업 Output: a structural or linguistic description Ex: labeling ECG signals, video indexing, protein structure indexing 10

11 분류 vs 군집화 Classification (카테고리를 미리 알고 있음)
Clustering (새로운 카테고리를 생성하는 작업) Category “A” Category “B” Clustering (Unsupervised Classification) Classification (Recognition) (Supervised Classification) 11

12 패턴 인식 : 목표 감지된 데이터에서 잡음 제거 Data vs Noise 클래스에 속하는 데이터들을 이용하여 각 클래스의 속성 (모델) 정의 (class modelling) 클래스 모델이 만들어지면 클래스에서 패턴이 생성되는 과정 추론 가능 입력된 데이터 (감지 데이터)에 가장 적합한 클래스 모델 선택하여 클래스 레이블 할당 12

13 일반적인 분류 과정 (classification)
Sensor signal Sensor Feature Extractor Feature Classifier Class Membership 13

14 Example : Salmon or Sea Bass
컨베이어 벨트 위에 들어오는 생선을 두 부류로 분류 : Salmon or Sea Bass Steps: 전처리(segmentation) 특징 추출 (measure features or properties) 분류 (make final decision) 14

15 Sea bass vs Salmon Discrimination
사용 가능한 특징 : Length Lightness Width Number and shape of fins Position of the mouth Etc … 15

16 Salmon vs. Sea Bass (by length)
16

17 Salmon vs. Sea Bass (by lightness)
Best Decision Strategy with lightness 17

18 오분류 비용 (Cost of Misclassification)
두 가지 유형의 오분류 (1) sea bass를 salmon으로 분류 (2) salmon을 sea bass로 분류 어떤 유형의 오분류가 더 심각한가 ? 이 문제를 손실 함수 (Loss function)를 이용하여 일반화 리스크를 최소화하는 결정 규칙은 ? Risk = Expected Loss Loss Function Salmon Sea Bass -10 Sea bass -20 decision truth 18

19 두 특징을 사용한 분류 작업 (by length and lightness)
It is possibly better. Really ?? 19

20 인식 : 기계학습 기법을 사용하여 Slides adapted from Fei-Fei Li, Rob Fergus, Antonio Torralba, Kristen Grauman, and Derek Hoiem

21 f( ) = “tomato” f( ) = “cow” 기계 학습 원리
영상에서 특징을 구한 후, 예측 함수 (prediction function)를 사용하여 클래스 레이블 출력: f( ) = “apple” f( ) = “tomato” f( ) = “cow”

22 기계 학습 원리 y = f(x) 학습 (Training) : 레이블이 할당된 학습 예제들 {(x1,y1), …, (xN,yN)} 을 사용하여, 예측 에러를 최소화하는 예측 함수를 작성하는 과정 평가 (Testing) : 학습에 사용되지 않았던 평가 예제 x에 예측 함수 f 를 적용하여 예측된 레이블 y = f(x)을 출력하는 과정 output prediction function Image feature

23 Steps Training Testing Training Labels Training Images Image Features
Learned model Learned model Testing Image Features Prediction Test Image Slide credit: D. Hoiem

24 특징 Raw pixels Histograms GIST descriptors …

25 최소 이웃 분류기 f(x) = x 에 가장 가까운 학습 예제의 레이블 거리 계산 함수 필요함 사전 학습 필요하지 않음 !!
Training examples from class 2 Training examples from class 1 Test example f(x) = x 에 가장 가까운 학습 예제의 레이블 거리 계산 함수 필요함 사전 학습 필요하지 않음 !!

26 선형 분류기 두 클래스를 분리하는 선형 함수 생성 : f(x) = sgn(w  x + b)

27 어떤 특징 그리고 얼마나 많은 특징을 사용하여야 하나?
좋은 특징 추출 작업이 분류기 성능 결정 특징이 결정되면 학습 데이터를 이용하여 최적의 분류 규칙을 만들 수 있다 분류 규칙을 만드는 과정을 학습, 훈련, 또는 파라미터 값 결정 과정이라 한다 기계 학습과 관련된 주요한 이슈 특징 추출과 관련된 이슈 : 서로 연관성이 높은 특징들을 성능 향상에 도움이 되지 않음 어떤 특징은 성능 향상에는 도움이 되더라도 추출 과정이 많은 계산 시간을 요할 수 있다 많은 양의 특징을 추출하는 것은 많은 계산 시간을 요한다 차원의 저주 (Curse of dimensionality) … 27

28 From Ricardo Gutierrez-Osuna,Texas A&M Univ.
28

29 From Ricardo Gutierrez-Osuna,Texas A&M Univ.
29

30 패턴 인식 시스템의 구성 요소 Learning algorithm Sensors and preprocessing
From Vojtěch Franc 패턴 인식 시스템의 구성 요소 Sensors and preprocessing Feature extraction Class assignment Pattern Classifier Learning algorithm Teacher Sensors and preprocessing 특징 추출 (feature extraction) : 변별력 높은 특징 추출 분류기 (classifier) 학습 가이드 (teacher) : 학습 성능 향상을 위해 부수적인 정보 제공, 예: 클래스 레이블 등 학습 알고리즘 (learning algorithm) : 학습 예제들로 부터 분류 규칙 생성 30

31 패턴 인식 방법들 템플릿 정합 (Template matching) 통계적 패턴 인식 (Statistical PR):
The pattern to be recognized is matched against a stored template Works only simple problems 통계적 패턴 인식 (Statistical PR): based on underlying statistical model of patterns(features) and pattern classes. Class-conditional probability Pr(X|Ci) 구조적 패턴 인식 (Structural PR) : pattern classes represented by means of formal structures as grammars, automata, strings, etc. Based on measures of structural similarity Not only for classification but also description Often called Syntactic pattern recognition 신경망 (Neural networks) : Classifier is represented as a network of cells modeling neurons of the human brain (connectionist approach). Knowledge is stored in the connectivity and strength of synaptic weights Trainable, requires minimum a priori knowledge, works for complex decision boundaries 통계-구조 분석 방법 (Statistical structure Analysis) : Combining Structure and statistical analysis Bayesian Network, MRF 등의 Probabilistic framework을 활용 31 Modified From Vojtěch Franc

32 템플릿 정합 (Template Matching)
32 Input scene

33 변형 가능 템플릿 정합 (Deformable Template Matching: Snake)
Example : Corpus Callosum Segmentation Prototype registration to the low-level segmented image Shape training set Prototype and variation learning Prototype warping 33

34 From Ricardo Gutierrez-Osuna,Texas A&M Univ.
34

35 분류기 (Classifier) 분류기는 특징 공간 (feature space)을 클래스 레이블이 할당된 결정 공간 (decision region)들로 분할하는 작업 결정 공간들 간의 경계  결정 경계 (decision boundaries) 입력된 특징 벡터 X 가 어떤 결정 공간에 속하는 가를 판단 35

36 변별 함수 (discriminant fuction)에 의한 분류기 표현
From Vojtěch Franc 변별 함수 (discriminant fuction)에 의한 분류기 표현 분류기를 변별 함수 (discriminant functions)들의 집합으로 구성 … 분류 규칙 : If , assign x to i-the class Class identifier …. Feature vector 36 Discriminant function

37 Discriminant Function
변별 함수의 형태에 따른 분류기 유형들 Discriminant Function Classifier A posteriori Probability P( yi | X) Bayesian Linear Function Linear Discrinant Analysis, Support Vector Machine Non-Linear Function Non-Linear Discrinant Analysis Output of artificial Neuron Artificial Neural Network 37

38 베이지안 분류기 (Bayesian Decision)
통계적 방법 최소 에러를 보장하는 최적의 분류기 각 클래스에 대한 완벽한 통계 정보를 알고 있어야 함 결정 규칙은 사후 확률 (posterior probabilities) 값으로 X is an observation : if P(1 | x) > P(2 | x) decide that x belongs to 1 if P(1 | x) < P(2 | x) decide that x belongs to 2 38

39 변별 함수 분류기 변별 함수 G(x) 를 다항식으로 표현 : 2차 (Quadratic) 함수
From Vojtěch Franc 변별 함수 분류기 변별 함수 G(x) 를 다항식으로 표현 : 2차 (Quadratic) 함수 1차 선형 함수 (Linear function) – Linear Discriminant Analysis (LDA) 결정 경계는 영역을 분리하는 다차-평면 (hyperplane)으로 구성됨 39

40 LDA Example height Task: jockey-hoopster recognition.
From Vojtěch Franc LDA Example height Task: jockey-hoopster recognition. The set of hidden state is The feature space is weight Training examples … Linear classifier: 40

41 인공 신경망 (Artificial Neural Network)
주어진 네트웍 구조에서 학습 예제들 {(x1,y1), …,(x,y)} 에 대한 에러 함수 J(w) 값을 최소화하는 가중치 집합을 구하는 문제 41

42 분류기 설계 과정 학습 데이터 수집 (Data collection) 특징 추출 및 선택 (Feature choice)
Probably the most time-intensive component of project How many examples are enough ? 특징 추출 및 선택 (Feature choice) Critical to the success of the PR project Require basic prior knowledge, engieering sense 모델 선택 및 설계 (Model choice and design) Statistical, neural and structural Parameter settings 학습 (Training) Given a feature set and ‘blank’ model, adapt the model to explain the training data Supervised, unsupervised, reinforcement learning 평가 (Evaluation) How well does the trained model do ? Overfitting vs. generalization 42

43 분류기 학습 과정 Learning algorithm 주어진 클래스들을 분류하는데 어떤 특징들을 사용할 것인가?
Sensors and preprocessing Feature extraction Class assignment Pattern Classifier Learning algorithm Teacher 주어진 클래스들을 분류하는데 어떤 특징들을 사용할 것인가? 특징 분석 (Feature analysis) 필요한 확률 분포 또는 결정 경계를 구할 수 있는 가 ? 학습 데이터를 사용하여 학습하는 과정 43

44 학습 알고리즘 (Learning Algorithms)
개략적인 아이디어 (General Ideas) 성능을 최대화하기 위해 가장 좋은 파라메터 값을 결정하는 방법 제시 학습 과정에서 파라메터 값을 변화시키며 성능을 평가하여, 최적의 파라메터 값에 도달하는 방법 제시 44

45 분류기 모델 복잡도 (Model Complexity)
Salmon 과 Sea bass 분류를 위한 두 유형의 결정 경계 : Which is better ? A or B A B 45

46 분류기 모델 복잡도 (Model Complexity)
복잡한 모델을 선택하여 주어진 학습 데이터에 대해서는 높은 성능을 보일 수 있으나, 학습 데이터가 아닌 다른 데이터에 대해서는 ? 복잡한 모델은 특정 학습 데이터에 대해 과적합된 결정 경계를 만들어 낼 수 있다 Issue of generalization 46

47 일반화 (Generalization) 패턴 분류 시스템은 학습에 사용되지 않았던 데이터에 대해서 옳은 클래스 레이블을 할당할 수 있도록 일반화되어야 함 매우 복잡한 결정 경계는 일반화 측면에서 도움이 되지 않음 너무 단순한 결정 경계 역시 좋은 성능을 보이지 않음 성능 과 단순성 간의 트레이드-오프 (tradeoff)를 고려하여 일반화 이슈는 통계적 패턴 인식에서 매우 중요한 기능임 47

48 일반화 전략 (Generalization Strategy)
일반화 능력을 향상시키는 방법은 ? 학습 데이터 양을 증가 시킴 (i.e., better pdf estimates). 모델을 단순화 시킴 (i.e., simpler classification boundaries) 48 Simplify the decision boundary!

49 과적합과 부적합 (Overfitting and underfitting)
From Vojtěch Franc 과적합과 부적합 (Overfitting and underfitting) underfitting good fit overfitting 일반화 문제 : 학습 데이터에 대해 얻어진 적은 리스크 Remp 가 일반 데이터에 대한 리스크 R를 나타내지 않을 수 있다 49

50 차원의 저주 (Curse of Dimensionality)
너무 많은 특징을 사용하면, 역설적으로, 성능 저하를 가져올 수 있다 각 특징 값이 M 개의 구간 값을 갖는다고 하면, d 개의 특징을 사용할 경우 총 Md (d: # of features) 개의 구간이 필요함 (구간의 개수는 d 와 함께 기하급수적으로 증가) 한정된 개수의 학습 데이터를 사용하는 경우, 특징의 개수를 증가시키면 한 구간 내에 포함될 수 있는 학습 데이터의 수가 감소함  일반화 능력을 저하 시킴 구간 개수의 증가는 각 구간 내에 포함될 데이터 수의 감소를 야기 적은 수의 학습 데이터  낮은 일반화 능력 학습 데이터 양은 늘 부족하다 !! 50

51 차원의 저주 (Curse of Dimensionality)
제한된 양의 training Data로 훈련 시에 Feature 수를 늘리면 일반화 능력 감소 적절한 일반화 능력 향상을 위하여 요구되는 훈련데이터의 양은 feature dimension에 따라 급격히 증가 주어진 학습 데이터 양에 적합한 특징 수를 찾는 작업은 매우 어려운 작업 !! 51

52 패턴 인식의 다른 이슈들

53 Difficulty of Class Modeling
53

54 인식에는 문맥 (Context) 정보가 필수
54

55 Context 없을 경우 사람의 영문 필기 인식률 : 95 %
문자인식에서의 문맥 정보 Context 없을 경우 사람의 영문 필기 인식률 : 95 % 55

56 전역적 일관성 (Global Consistency)
Local decision is not enough 56

57 여러 분류기의 결합 (Combining Multiple Classifiers)
여러 전문가의 의견을 종합하여 분류 성능 향상 Best single classifier vs Combining multiple classifiers Two heads (experts, classifiers) are better than one 각 분류기의 출력은 Best (single) class Ranking Score as each class 어떤 분류기 들을 결합할 것인가 ? 상호 연관성이 높은 (correlated) 분류기들은 성능 향상에 도움이 안됨 분류기들을 결합하는 방법은 ? Majority rules, borda count, decorelated combination, etc. A study on combining multiple classifiers has been investigated in pattern recognition during the last decade. For a classifier, it is well known that it makes a decision in the form of one of the three classification results; measurement score, ranking, and single choice. We consider only classifiers producing single choice level decision. For a combination type of classifiers according to the arrangements of them, only parallel combination type is chosen in this paper. 57

58 패턴 인식 성능의 평가 실제 (정) 인식률 = (p+q)/(p+q+r+s) 오인식률 = (r+s)/(p+q+r+s)
Miss detection = r/(p+r) False alarm = s/(p+s) Recall = p/p+r Precision = p/p+s 기각율 (refuse to make decision) 처리율 A not A 인식결과 p a s q not a r A case: 20% 기각했는데 결과에는 0.5% error B case : 10% 기각했는데 결과에는 1.0% error Which is better ? 58

59 패턴인식의 성능 향상 100% 를 향하여 성능 시간, 노력 59