비모수적 의사결정 nonparametric decision making
- 실제 세계의 문제에서 관심사가 어떤 타입의 밀도 함수인지 모르는 경우가 많다.
- 일련의 샘플들의 임의의 밀도로 맞추는 방법을 비모수적 의사 결정이라 함
-> 밀도의 일반적인 형태를 추축할만한 근거가 없는 경우 사용
- 샘플 데이터로부터 정확한 파라미터를 구하여 모수적 결정 함수로 클래스 분포를 사용하는것이 아니라 샘플로부터 확률적 파라미터없이 곧바로 분류를 수행함
비모수적 의사 결정의 종류
- 분포 타입을 모를때 근사적인 모수적 결정 함수 사용하는것이 히스토그램 histogram 과 커널 kernel
- 다른 방법이 최근접 이웃 분류 nearest neighbor classification
클러스터링 clustering
- 구분하려는 각 클래스에 대한 지식이 없는 상태에서 분류를 하는것
- 샘플들에대한 지식 없이 유사도에 근거하여 클러스터를 구분
클러스터링의 의미
- 데이터들을 여러개의 부분집합 clusters로 분할하는것
- 각 부분집합의 데이터는 몇가지 공통 특징을 가짐.
- 몇가지 거리측정법으로 유사도 similarity or proximity를 계산
- 클러스터링의 종류 : 계층형 클러스터링 hiearchicla clustering, 파티션 클러스터링 partitional clustering
계층형 클러스터링
- 바텀업 bottom-up(agglomerative), 탑다운 top-down(divisive) 두 가지 경우
- 각 요소들로부터 시작한 클러스터들이 계층 구조를 이룸
- 트리 구조를 이루며 한쪽 끝에는 각 요소가 있고, 다른쪽 끝에는 모든 요소를 가지는 단하나의 클러스터가 있음
파티션 클러스터링
- 클러스터의 계층을 고려하지 않고 평면적으로 클러스터링 하는 방법
- 일반적으로 몇개의 클러스터로 나눠질것을 예상하여 클러스터 갯수를 정함
| 커널과 윈도우 (0) | 2020.06.30 |
|---|---|
| 비모수적 의사 결정 (0) | 2020.06.30 |
| 패턴 인식 (0) | 2020.06.30 |
| 임시방편 가설 ad hoc hypothesis (0) | 2020.06.30 |
| 모의 담금질 (0) | 2020.06.30 |
패턴 인식 pattern recognition
- 데이터로부터 중요한 특징, 속성을 출력하여 입력 데이터를 식별할수 있는 부류로 분류 classification함
패턴 인식 예시
- 의료 진단, 문자 인식, 음성 인식
| 비모수적 의사 결정 (0) | 2020.06.30 |
|---|---|
| 클러스터링 (0) | 2020.06.30 |
| 임시방편 가설 ad hoc hypothesis (0) | 2020.06.30 |
| 모의 담금질 (0) | 2020.06.30 |
| 최적화 (0) | 2020.06.30 |
ad hoc의 의미
- 임시방편, 임기응변
임시방편 가설 ad hoc hypothesis
- 어떤 이론을 반박하는 사실을 설명하기 위해 임시로 만들어내는 가설
- 새 이론이 기존 이론과 상충되거나 필수적으로 설명해야할 기작이 없는 경우 임시방편 가설로 새 이론이 설명못하는 부분을 해결하려 함.
모의 담금질 simulated annealing
- 커다란 탐색 공간에 주어진 함수의 전역 최적점 global optimum에 대한 훌륭한 근사치를 찾으려고 하는 전역 최적화 global optimization 문제에 대한 일반적인 확률적 휴리스틱 probabilistic heuristic 접근방식
모의 담금질의 유례
- 야금학의 담금질에서 따온 것으로 결정치를 크게하고 결함을 작게하기위해 금속에 열을 가하고 냉각시키는 속도를 조절하는 기술에 따옴
- 열을 가하면 최초의 위치(국소 최적점 local minimum)에서 떨어져나가 높은 에너지상태로 방황하다 냉각시키면 더 낮은 내부에너지를 가지는 환경(전역 최적점 global minimum)에 찾을 기회가 더 많아짐
최적화 optimization
- 어떤 제약조건이 있을수 있는 상황에서 함수의 최대치와 최수치 maxima and minima를 찾는 과목
최적화 문제의 예
- 자원들이 어느 한계를 넘지않고 직면하는 요구사항을 대부분 만족하면서, 제조과정의 이익을 최대로 하기위한것
-> 물류, 설계 문제등에서 많이 응용
근 구하기와 최적화의 차이
- 근 구하기는 함수 혹은 함수들의 근을 구하나 최적화는 최소값 혹은 최대값을 찾음
유전 알고리즘 genetic algorithm
- 자연에서 생물의 유전 genetics와 진화 evolution의 메카니즘을 공학적으로 모델화 하는것에의해 샐물의 적응 능력을 취급하는것
- 자연 도태의 원리를 기초로한 최적화 방법
- 탐색, 최적화 및 기계학습 도구로 많이 사용됨
유전 알고리즘의 기본 원리
- 부모로 부터 유전자에 의해 생물의 정보 전달이 행해지면 다음 세대에는 우수한, 환경 적응도가 높은 개체의 유전 정보가 우선적으로 전해짐
- 적응도가 낮은 개체는 수명이 짧고, 증식할수 없게 됨. 적응도가 낮은 종족도 자연 도태됨
- 세대를 거듭해 환경에 적응도가 높은 개체가 많아짐
=> 유전과 진화의 기본 원리
유전 알고리즘 genetic algorithm or 진화 알고리즘 evolution algorithm
- 자연 세계의 진화 과정을 컴퓨터 시뮬레이션함으로 복잡한 실제 세계 문제를 해결하고자 하는 계산 모델
유전 알고리즘 수행 방법
- 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현
- 이들을 점차 변형하여 더 좋은 해들을 생성
-> 풀고자 하는 문제에 대해 가능한 해들을 염색체로 표현한 다음 이들을 점차 변형하여 더 좋은해들을 생성
유전 알고리즘 관련 용어
- 개체 individual, 유기체 organism : 각각 가능한 하나의 해를 유기체나 개체라고 함
- 개체군 population : 이들의 집합
- 유전 연산자 genetic operator : 하나의 개체는 보통 하나나 여러 염색체로 구성되며 염색체를 변형하는 연산자들
유전 연산자의 종류
- 기본적으로 다음 3가지 가 있음
- 선택 selection : 집단 중 적응도 분포에 따라 다음 단계로 교배를 행하는 개체의 생존 분포 결정
- 교배 crossover : 2개의 염색체 사이 유전자를 바꾸어 새 개채 발생
- 돌연변이 mutation : 유전자의 어떤 부분 값을 강제적으로 변화
유전 알고리즘의 모델
- 염색체를 표현하는 방법과 사용되는 유전 연산자 종류, 특성에 따라 여러 모델로 구분
- 진화 전략 evolution strategy : 실수 값을 취하는 유전자들로 구성된 벡터를 염색체로 사용
- 진화 프로그래밍 evolutionary programming, 유전 프로그래밍 genetic programming : 그래프와 트리를 염색체 표현에 사용
유전 알고리즘 응용 예시
- 비결정 난해 NP-hard 군에 속하는 문제들이 대표적임
- 순회 판매원 문제, 작업 공정 스캐줄링, 채널 라우팅, 자동차 스케줄링, 로드 밸런싱 등
의사 결정 이론 decision theory
- 불확실성에 직면하여 결정을 내려야할때, 어떤 결정을 할것이며, 어떤 정보를 어떻게 이용해야하는가를 다루는 이론
-> 기대 효용이 최대가 되도록 판단해야함
=> 정보 가치가 높은 정보는 무엇인지 찾고, 이것으로 어떻게 구체적을 내리는가 제시해야함
의사 결정 이론
- 효용성으로 표현되는 선호 preference는 결정이론 decision theory라고 불리는 합리적 의사 결정의 일반 이론에서 확률과 결합
- 결정 이론 decision theory = 확률 이론 probability theory + 효용 이론 utility theory
결정 이론 기본 개념
- 행동의 모든 가능한 결과에 대해 평균해서, 만일 가장 높은 기대 효용 expected uitility를 낳는 행동을 선택한다면 그 떄에만 그 에이전트는 합리적
=> 기대 효용 최대화 Maximum Expected Uitility, MEU의 원리
A* 탐색 알고리즘 A s* search algorithm 개요
- 초기 노드에서 목표 노드까지 경로 찾는 그래프 탐색 알고리즘
- 목표 노드까지 가장 좋은 경로 estimate of the best route 하기 위해 각 노드에 랭킹 부여하는 heuristic estimate를 사용하고, 그 순서를따라 노드 방문
A* 알고리즘의 장점
- 최단 거리 찾기 문제에서 다른 알고리즘(다익스트라, best-first search)보다 훨씬 빠름
A* 알고리즘 개발 배경
- 휴리스틱 방법(의사 결정시 해당 문제에 대한 정보를 이용하는것)
+ 형식적 방법(formal method : 문제 관련 정보를 사용하지 않지만 정형 분서이 될수있는것)을 결합하기 위해 1968년 개발
A* 알고리즘의 구조
- 그래프 탐색 알고리즘
- 타 그래프 탐색 알고리즘과 차이는 목표에 얼마나 근접한지 평가하기위해 휴리스틱 함수를 사용함
-> 휴리스틱에 의해 먼저 바람직한 방향을 탐색, 그 방향이 실패하면 다른 경로를 찾음
A*의 활용
- 경로 탐색기로 많이 사용
- 공간안 특정 상태에서 인접한 상태를 조사해 나가면서 목표 상태까지 가장 싼 비용의 경로를 찾음