11장. 최적화 알고리즘 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학.

Presentation on theme: "11장. 최적화 알고리즘 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학."— Presentation transcript:

1 11장. 최적화 알고리즘 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학

2 들어가는 말 패턴인식은 최적화 문제를 많이 다룬다. SVM은 여백을 최대로 하는 결정 직선을 찾는다.
퍼셉트론이나 MLP는 오류를 최소로 하는 가중치 값을 찾는다. …

3 들어가는 말 패턴 인식의 문제 풀이는 크게 두 단계로 나누어 볼 수 있다.
매개 변수 θ는 연속 공간일 수도 이산 공간일 수도 있음 SVM, MLP는 연속 공간, 특징 선택은 이산 공간

4 들어가는 말 11 장의 목적 이미 1-10 장에서 배운 최적화 알고리즘을 보다 명시적으로 드러내고 그들을 비교함으로써 알고리즘에 대한 이해의 깊이를 더함 새로운 최적화 알고리즘 소개 시뮬레이티드 어닐링, 유전 알고리즘 (기존 알고리즘이 안고 있는 지역 최적점 수렴 문제를 해결할 수 있는 여지를 가짐)

5 11.1 패턴인식의 최적화 문제와 풀이

6 11.1.1 최적화 문제들 분류기 학습 학습 집합 X={(x1,t1), (x2,t2), …, (xN,tN)} θ는 가중치 벡터

7 11.1.1 최적화 문제들 선택 특징 선택 (9 장), 분류기 앙상블 선택 (12 장), k-NN을 위한 프로토타입 선택 등

8 최적화 문제들 군집화

9 최적화 문제들

10 이들 문제를 어떻게 풀어 최적의 매개 변수 값을 찾아 낼 것인가? 문제의 난이도
문제 풀이 이들 문제를 어떻게 풀어 최적의 매개 변수 값을 찾아 낼 것인가? 문제의 난이도 θ의 차원. 작게는 수십~수백 , 크게는 수천~수만 차원 목적 함수 J(θ)의 복잡도. 지역 최적점이 하나뿐인 single-modal인 경우 미분식을 풀어 해결 가능, multi-modal인 경우는 보다 복잡한 알고리즘 필요 해 공간을 효율적으로 탐색하는 알고리즘 필요

11 11.1.2 문제 풀이 문제 풀이 분석적 방법 예, 미분식을 풀어 해를 구함 (11.2.1 절) 수치적 방법 (그림 11.6)
초기 해에서 출발하여 그것을 조금씩 개선해 나가는 방법

12 문제 풀이 수치적 방법 (그림 11.6) 세 가지 사항을 고려해야 한다.

13 문제 풀이 수치적 방법 최적 해 (전역 최소점, θ4)을 보장하는 것은 아니다. 지역 최소 점 (θ1) 또는 최소 점 근방 (θ2, θ3, θ5)을 찾고 멈출 수도 있다.

14 11.2 미분을 이용한 방법 11.2.1 분석적 풀이 11.2.2 내리막 경사법 11.2.3 라그랑제 승수
최적화 알고리즘과 패턴인식 문제들

15 분석적 풀이

16 두 가지 예제

17 11.2.2 내리막 경사법gradient descent method
내리막 경사법은 해를 반복 개선하는 수치적 방법의 일종 현재 위치에서 경사가 가장 급격하게 떨어지는 방향을 찾고 그 방향으로 해를 약간 이동. 방향은 도함수로 알아냄 ρ는 학습률로서 이동량을 조절

18 내리막 경사법은 욕심 알고리즘 (지역 최적점으로 수렴할 위험)
내리막 경사법 내리막 경사법은 욕심 알고리즘 (지역 최적점으로 수렴할 위험)

19 도함수는 초기값을 θ0=(-0.5,0.5)T, 학습률 ρ=0.01로 하면, 예제 11.1의 낙타 등 함수
점점 낮은 곳을 찾아간다.

20

21 11.2.3 라그랑제 승수 조건부 최적화 문제 예 최소 점은 (0,0)T
하지만 ‘2θ1+ θ2=0이라는 조건 하’에 최소점을 구하는 문제라면?

22 등식 조건부 최적화 문제equality constrained optimization problem
라그랑제 승수 등식 조건부 최적화 문제equality constrained optimization problem 라그랑제 함수와 라그랑제 승수 (11.6)은 라그랑제 함수 조건식마다 라그랑제 승수 λi를 할당

23 이제 라그랑제 함수를 최소화하는 해를 구하면 된다!
라그랑제 승수 이제 라그랑제 함수를 최소화하는 해를 구하면 된다! 결국 (11.7)을 만족하는 해를 구하면 됨

24 그림 11.11의 풀이 ‘2θ1+ θ2=1이라는 조건 하’에 의 최소점을 구하라. 이 식을 풀면,

25 부등식 조건부 최적화 문제inequality constrained optimization problem
라그랑제 승수 부등식 조건부 최적화 문제inequality constrained optimization problem

26 그림 11.11을 부등식 조건으로 바꾸어 보면, ‘2θ1+ θ2>1이라는 조건 하’에 의 최소점을 구하라.
‘2θ1+ θ2>1이라는 조건 하’에 의 최소점을 구하라.

27 KKT 조건을 구하고 그것을 풀면,

28 2~10 장의 문제들에 적용된 최적화 알고리즘들을 정리해 보면,
최적화 알고리즘과 패턴인식 문제들 2~10 장의 문제들에 적용된 최적화 알고리즘들을 정리해 보면,

29

30 11.3 시뮬레이티드 어닐링simulated annealing
시뮬레이티드 어닐링의 기본 원리 내리막 경사법과 비슷함 (해를 하강시키기만 하는 내리막 경사법과 달리) 조건에 따라 해를 상승시키기도 함 (이 기능으로 지역 최저점 탈출하는 여지 생김) 온도라는 뜻을 갖는 변수 T를 조절함으로써 상승 확률 조절 (초기에는 온도가 높아 상승 확률이 크지만 시간이 지남에 따라 온도를 낮추어 확률을 줄임)

31

32 11.4 유전 알고리즘genetic algorithm
발상 !

33 11.4.1 원리: 내리막 경사법, 시뮬레이티드 어닐링, 유전 알고리즘
유전 알고리즘의 차별성 해 집단을 가짐 (단일 해가 아닌 다수 해를 개선해 나가는 전략) 생물 진화와 마찬가지로 교배와 돌연변이 연산을 통해 해를 개선해 나감

34 11.4.1 원리: 내리막 경사법, 시뮬레이티드 어닐링, 유전 알고리즘
내리막 경사법, 시뮬레이티드 어닐링과 비교

35 11.4.1 원리: 내리막 경사법, 시뮬레이티드 어닐링, 유전 알고리즘
내리막 경사법, 시뮬레이티드 어닐링, 유전 알고리즘의 비유 히말라야 산맥에서 가장 높은 에베레스트 봉을 찾는 문제

36 11.4.2 유전 알고리즘의 구조 용어 해집단population: 해 의 집합 적합도: 해의 품질 세대 자식 해
유전 연산: 교차, 돌연 변이

37 11.4.2 유전 알고리즘의 구조 원리 라인 7의 선택 적합도가 높은 해일수록 선택될 확률이 높다.
하지만 못난 해도 0 이상의 확률을 갖는다. 라인 8 의 교차로 만들어진 자식 해는 부모 해의 형질을 이어 받는다. 라인 9의 돌연 변이는 지역 최적점을 벗어날 가능성을 제공한다. (조숙한 수렴premature convergence 방지 역할) 자식 해의 품질은 해 집단의 평균 품질을 넘을 가능성이 높다. 따라서 세대를 거듭하면 해 집단의 품질은 점점 좋아진다.

38 안정 상태형과steady-state 세대형generational
유전 알고리즘의 구조 안정 상태형과steady-state 세대형generational 안정 상태형: 라인 6-11에서 k=1로 두어 한 세대에 하나의 해 생산 세대형: k=n으로 두어 한 세대에 해집단 전체를 대치 해 표현과 초기해 생성 문제에 적합한 해 표현을 개발해야 한다. 예) 특징 선택: 이진 열 예) 신경망 훈련: 실수 코딩 초기해는 보통 난수를 이용하여 생성 멈춤 조건 수렴이 되면 멈춘다. 그런데 수렴 여부는 어떻게 알 수 있나? 주어진 문제에 적합하게… 보통 아래 조건을 적절히 and 또는 or 하여 사용

39 유전 연산

40 11.4.3 유전 연산 적합도 계산 해 품질을 그대로 사용 적절할수도 그렇지 않을수도…
초기에는 우열이 두드러지지만 세대가 지남에 따라 품질 값의 차이가 미세해져 더 이상 진화가 안 일어 날 수 있음 품질 비례 방법 fi는 i 번째 해의 적합도. qi는 i 번째 해의 품질 qbest와 qworst는 각각 가장 좋은 해와 가장 나쁜 해의 품질 가장 좋은 해는 가장 나쁜 해의 r 배 적합도 (r이 클수록 ‘선택 압력’ 높다.) 순위 기반 방법 해를 품질에 따라 정렬하고 순위에 따라 적합도를 부여 q가 클수록 선택 압력 높다.

41

42 유전 연산 공유sharing 해 집단의 다양성을 높이려는 목적 (다양성이 높다는 것은 탐색 공간을 골고루 살핀다는 뜻이므로 전역 최적 점에 도달할 가능성을 높여줌) 원리 식 (11.13)으로 서로 비슷한 해의 적합도를 낮추어 줌 dij는 해 i와 j 사이의 거리 s(d)는 d가 클수록 작아지는 함수

43 유전 연산 선택 룰렛 휠 방법 예)

44 유전 연산 선택 (계속) 토너먼트 방법

45 교차 (부모해로부터 자식 해 생성. 부모 형질 이어받음)
유전 연산 교차 (부모해로부터 자식 해 생성. 부모 형질 이어받음) 자름선 교차 (이진 염색체) 자름선 개수가 많아지면 선택 압력은 어떻게 될까?

46 유전 연산 교차 (계속) 균등 교차 (이진 염색체) 산술 교차 (실수 염색체)

47 변이 (부모해가 가지지 못한 형질을 부여하여 더 광범위한 공간 탐색)
유전 연산 변이 (부모해가 가지지 못한 형질을 부여하여 더 광범위한 공간 탐색) 이진 염색체의 변이 (변이 확률 pm과 선택 압력의 관계는?) 실수 염색체의 변이

48 선택 압력selection pressure
매개 변수 설정과 선택 압력 선택 압력selection pressure 선택 압력이 높다는 말은 우수한 해에게 기회를 더 줌을 뜻함 너무 높으면 조기 수렴의 위험. 너무 낮으면 수렴 시간이 너무 긴 문제 다양성과 선택 압력은 반비례 관계이다. 탐사와exploitation 탐험exploration 탐사는 가능성 높아 보이는 지점을 집중적으로 찾아보는 성향 탐험은 탐색 공간 전체를 고루고루 찾아보는 성향 유전 알고리즘이 추구하는 바는 탐사와 탐험의 절묘한 조화 그러기 위해서는 여러 매개 변수를 조화롭게 설정해야 한다!

49 매개 변수 설정과 선택 압력

50 찬반 논쟁