강화학습 Flashcards
몬테카를로 트리 탐색(MTCS)
[리드] 효율적 경로 탐색
[정의] 전체 경로 탐색 불가능 시 효율적 경로 탐색을 통해 최적의 판단을 수행하는 알고리즘
* 전수조사등 시간적 제약에 문제에 대해 무작위 시뮬레이션을 통한 효율적 트리 탐색
[핵심개념]
- 정책(Policy) : 트리 검색의 ‘폭’ 제한, 확장 단계에서 가장 높은 승률 예측
- 가치(Value) : 트리 검색의 ‘깊이’ 제한, 현재 승산
[알고리즘] (분석 Tree 예시) 선택 -> 확장 -> 시뮬레이션 -> 역전파
[절차]
1. 선택 : 현재 상태에서 특정 경로 예측 (수 읽기)
2. 확장 : 트리 확장 (수 읽기 확장)
3. 시뮬레이션 : 종료 시점까지 경로 예측 (임의 수 예측)
4. 역전파 : 시뮬레이션 결과 반영 (승산가능성 예측)
* 병렬컴퓨팅 기반 1~4 반복 처리 수행하며 정확도 증가
Q-Learning
[정의] 주어진 상태에서 주어진 행동을 수행하는 것이 가져다 줄 효용의 기대값을 예측하는 함수인 Q함수를 학습하는 강화학습 기법
[구성도]1.Q 테이블 초기화 2.Q에 기반하여 액션 선택 3.액션 수행 4.리워드 측정 5.보상값 업데이트 –> 2 반복
[구성요소]
- 정책 (Policy) : 최고 Q값기반 액션 선택
- 벨만 방정식 : 재귀함수(최적의 정책을 찾는 반복 수행), 현재 최고보상(즉시보상), 미래보상
- Q-러닝 알고리즘 : 벨만 방정식 반복 수행, 반복기반 Q함수 근사
[문제점/해결방안]
- (문) 테이블 기반 Q러닝의 사이즈 문제
- (해) DQN : ConvNet 활용, Feed Forward 수행
마코프 디시즌 프로세스(MDP)
[리드] 최적 Policy 수립, MDP
[정의] 이산시간 확률제어 과정으로, 상태, 행동 및 전이확률 기반 최적의 의사결정 정책 (π) 을 탐색하는 강화학습 기법
[구성요소]
- 상태 (State) : 상태의 유한 집합
- 행동 (Action) : Agent가 상태(S)에서 할 수 있는 행동의 유한 집합
- 상태전이 확률 분포 (State Transation) : 전이확률, T(s’, a, s)
- 보상 (Reward) : 행동 A에 대한 보상 기대값, R(s, a)
- 할인율 (Discount Factor) : 현재의 보상의 미래 보상에 대한 가치 비율 (0과 1사이의 값)
- 정책 (Policy) : 보상을 극대화하는 행동 A를 결정하는 확률 함수 (π)
[주요 알고리즘]
- Value Iteration : 동적 계획법 사용, π 함수 미사용, V(s)로 대체, Vi(s)의 i차수 반복 수행
- Policy Iteration : 명확한 종료 조건, π(s) 계산 단계 1회 수행, 수렴 시까지 V(s) 반복
HMM
[정의] 관측 불가능한 은닉 상태를 관측이 가능한 결과를 통해 모델링(모형화)하는 이중 확률론적 모델
[가정] 특정 사건이 관측될 확률은 이전 시간 관측 결과에 의존하며, 상태를 직접 볼 수는 없음
[모델]
- Ergodic : 상태확률 연계, 순환 모델
- Left to Right : 상태 전이가 순차 발생, 일자형 모델
[구성요소]
- 초기화 확률, 상태 전이 확률, 관측 확률 초상관
- 은닉상태 집합, 관찰가능상태 집합, 상태전이 행렬, 관찰확률 행렬, 파이벡터
유전 알고리즘
[리드] 진화의 개념 활용 최적화 문제 해결
[정의] 미지의 함수 Y=f(x)를 최적화하는 해 x를 찾기위해 선택,교차,변이 과정을 반복 수행하는 탐색 알고리즘
[특징] 최적해 탐색, 진화 모방한 탐색 알고리즘, 문제 풀이 접근방법론
* 직관적 판단 어렵고 다수의 해가 존재하는 경우 최적의 알고리즘
[절차]
1. 유전자 형들의 결정 : 대상 문제를 기호열(배열)로 변환 수행 ( 모델링)
2. 초기 해집단의 결정 : 다양한 개체 생성 (난수값 생성)
3. 초기 적합도 평가 : 각 개체의 적합도와 평가기준 만족 여부 - 만족시 종료 (적합도 함수)
4. 선택(selection), 재생 : 적합도가 높은 해만 남김 (룰렛 휠, Rank, 토너먼트)
5. 교배 교차(cross over) : 해(부모)를 서로 접목 새로운 집단(자시) 생성 (단일점 교차, 두점교차, 균등교차)
6. 돌연변이 : 돌연변이 연산 (전형적 변이, 비균등 변이)
7. 적합도 평가 : 거짓 또는 참 결과 확인, 거짓의 경우 3으로 이동 (적합함수 검사)
* 초기 해집단이 결정되고 적합도와 평가기준의 만족 기준에 따라 선택-교차-돌연변이 과정으로 진행
[룰렛 휠 선택 활용]
- (개념) 우월한 유전자를 가질수록 부모 해로 선택될 확률 상승하는 기법
* 적합도 기준 염색체 선택 시 룰렛 휠 선택 방법 이용
[활용사례]
- 학습 : 최적화, 기계 학습, 진화와 학습
- 산업 : 자동 프로그래밍, 경제학, 면역체계
* 기울기 정보를 필요치 않으므로 미분가능성 제약을 받지 않아 연속/불연속 변수 혼합된 문제 적합
