집밖은 위험해

ray casting 광선 투사

 컴퓨터 그래픽스와 계산 기하학의 다양한 문제를 해결하기 위해 광선과 표면의 교차 검사를 사용하는 기법으로

다양한 문제와 기술들과 관련이 있습니다.

- 광선에 처음 교차되는 물체를 가려내는 일반적인 문제

- 카메라 이미지의 각 픽셀을 향한 광선 교차 검사로 은닉면 제거

- 기본적인 광선들만 검사하는 재귀적 광선 추적 렌더링 알고리즘

https://ko.wikipedia.org/wiki/%EA%B4%91%EC%84%A0_%ED%88%AC%EC%82%AC

수치해석 numerical analysis

- 어떤 함수나 방정식의 해를 수치적으로 근사하여 해석하는 알고리즘

- 선형대수 이론의 수치 계산, 방정식의 수치해 계산, 미분방정식의 수치해 계산 등 이론의 계산 방법 다룸

범위

1. 비선형 방정식

2. 에러 해석 error analysis

3. 보간법 interpolation

4. 적분, 미분

5. 선형 대수

6. LU 인수분해 LU factorization

7. QR 인수분해 QR factoriation

9. 반복법 interative method

10. 양의 정부호행렬 positive definite

11. 상미분 방정식 ordinary difeerential equation

12. runge-kutta method

13. 상미분 방정식과 편미분 방정식 O.D.E and P.D.E

커널, 윈도우와 평활화 

- 사각이나 삼각, 정규분포 같은 커널로 컨볼루션하여 더부드럽게 하는 동작 평활화smoothening

다음의 밀도 함수가 주어질때

삼각 함수 커널을 적용한 결과

커널 예시

- 사각, 삼각, 정규분포 함수

- 각 영역의 합은 1, 표준 편차도 1

비모수적 의사결정 nonparametric decision making

- 실제 세계의 문제에서 관심사가 어떤 타입의 밀도 함수인지 모르는 경우가 많다.

- 일련의 샘플들의 임의의 밀도로 맞추는 방법을 비모수적 의사 결정이라 함

-> 밀도의 일반적인 형태를 추축할만한 근거가 없는 경우 사용

- 샘플 데이터로부터 정확한 파라미터를 구하여 모수적 결정 함수로 클래스 분포를 사용하는것이 아니라 샘플로부터 확률적 파라미터없이 곧바로 분류를 수행함

비모수적 의사 결정의 종류

- 분포 타입을 모를때 근사적인 모수적 결정 함수 사용하는것이 히스토그램 histogram 과 커널 kernel

- 다른 방법이 최근접 이웃 분류 nearest neighbor classification

클러스터링 clustering

- 구분하려는 각 클래스에 대한 지식이 없는 상태에서 분류를 하는것

- 샘플들에대한 지식 없이 유사도에 근거하여 클러스터를 구분

클러스터링의 의미

- 데이터들을 여러개의 부분집합 clusters로 분할하는것

- 각 부분집합의 데이터는 몇가지 공통 특징을 가짐.

- 몇가지 거리측정법으로 유사도 similarity or proximity를 계산

- 클러스터링의 종류 : 계층형 클러스터링 hiearchicla clustering, 파티션 클러스터링 partitional clustering

계층형 클러스터링

- 바텀업 bottom-up(agglomerative), 탑다운 top-down(divisive) 두 가지 경우

- 각 요소들로부터 시작한 클러스터들이 계층 구조를 이룸

- 트리 구조를 이루며 한쪽 끝에는 각 요소가 있고, 다른쪽 끝에는 모든 요소를 가지는 단하나의 클러스터가 있음

파티션 클러스터링

- 클러스터의 계층을 고려하지 않고 평면적으로 클러스터링 하는 방법

- 일반적으로 몇개의 클러스터로 나눠질것을 예상하여 클러스터 갯수를 정함

패턴 인식 pattern recognition

- 데이터로부터 중요한 특징, 속성을 출력하여 입력 데이터를 식별할수 있는 부류로 분류 classification함

패턴 인식 예시

- 의료 진단, 문자 인식, 음성 인식

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 군에 속하는 문제들이 대표적임

- 순회 판매원 문제, 작업 공정 스캐줄링, 채널 라우팅, 자동차 스케줄링, 로드 밸런싱 등