728x90 Drawing (AI)/Reinforcement Learning7 Algorithm design - DP / Levenshtein Distance Dynamic ProgrammingDynamic Programming은 동적 계획법이라는 뜻이지만 실제로 그렇게 동적이지는 않다. 오히려 기록해둔 과거 기록을 저장해두고 꺼내서 이용한다는 점에서 Tabular Method라는 이름이 어울린다.Divide-And-Conquer는 top-down approach로 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. 반면Dynamic programming은 bottom-up approach로 큰 문제를 작은 문제로 나눈 다는 점은 Divide-And-Conquer와 동일하나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 것이 아니고 그 저장된 결과를 이용한다는 점이 다르다. 해답을 구축하.. 2024. 5. 2. 강화학습 - (BellmanOptEq) Optimal Policy 우선 매 상태마다 적합한 policy들이 존재할 텐데 이때 아래와 같이 optimal policy가 존재한다는 것을 전재로 한다. 1. 어떤 마르코프 결정 과정에 대해서도, 모든 다른 정책보다 좋거나 같은 최적 정책 π*이 존재한다. 2. 모든 최적 정책은 최적 가치 함수를 달성한다. 3. 모든 최적 정책은 최적 행동-가치 함수를 달성한다. 최적 정책 π*는 주어진 상태 s에서 가장 높은 가치를 가지는 행동 a를 선택한다. 이를 수학적으로 표현하면 아래와 같다. 최적 상태-가치 함수 v는 주어진 상태 s에서 가능한 모든 행동 a에 대해 최적 행동-가치 함수 q의 최대값을 취한다. 수학적으로는 아래와 같이 표현할 수 있다. Bellman Optimality Equation 특정한.. 2024. 1. 31. 강화학습 - (Markov Decision Process) Markov Decision Process MRP까지는 어느쪽의 보상이 더 좋은지에 관한 얘기였다면 MDP는 강화학습의 본목적인 action을 선택하는 과정이 포함된다. 따라서 튜플에 action의 A가 추가되어 로 나타낸다. Reward function은 R_s = E[R_t+1|S_t=s, A_t=a]가 된다. 보상이 action에도 종속되는 것을 볼 수 있다. 또한 각 상태에서 어떤 decision을 가져갈지 정하는 규칙을 policy라고 한다. 따라서 MDP는 각 상태에서 최적의 선택 즉 optimal policy를 찾는 것이 최종적인 목적이다. Recycling Robot example 수집한 쓰레기 수에 따라 reward를 주고 움직여서 쓰레기를 찾거나 멈춰서 쓰레기를 누군가가 버려주기를 기다.. 2024. 1. 25. 강화학습 - (Markov Reward Process) Markov Property 마르코프 속성(Markov Property)은 확률론과 통계학, 특히 확률 과정에서 중요한 개념이다. 이는 강화학습의 핵심 문제인 Markov Decision Process를 정의하고 해결하는 것에도 핵심적으로 쓰인다. 이 속성은 미래의 상태가 오직 현재의 상태에만 의존하며 과거의 상태에는 의존하지 않는다는 것을 나타낸다. 해당 특성을 수식화하면 아래와 같이 나타낼 수 있다. 마르코프 속성은 복잡한 확률 과정을 단순화한다. 과거의 모든 정보를 고려할 필요 없이, 현재 상태만을 이용하여 미래를 예측할 수 있다. 또한 마르코프 속성은 계산상의 복잡성을 줄여준다. 과거의 모든 상태를 추적하고 고려하는 대신, 현재 상태만을 고려함으로써 더 효율적인 계산이 가능하다. 마르코프 속성은 .. 2024. 1. 16. 강화학습 - (UCB) Upper Confidence Bound UCB는 random하게 선정하는 것의 불확실성을 해소하기 위해 이용되는 방법이다. 우연히 나쁜 표본이 선택되어 potential이 있는 slot machine을 배제하고 다른 slot machine을 선택하게 되는 일을 방지하기 위한 알고리즘이다. 자세히 알아보자면 아래와 같다. UCB 알고리즘은 보상 값의 잠재적 가능성을 상한 신뢰 경계 U_t(a)로 측정하여, 실제 값 q_*(a)가 (Q_t(a) + U_t(a)) 이하일 확률이 높게 된다. 여기서 상한 경계 U_t(a)는 (N_t(a)), 즉 시간 t 이전에 액션 a가 선택된 횟수에 대한 함수이다. 액션 a가 더 자주 선택될수록 U_t(a) 는 더 작아진다. UCB 알고리즘에서는 항상 상한 신뢰 경계를 최대.. 2024. 1. 13. 강화학습 - (Multi-armed Bandits) K-armed Bandits 아래의 그림과 같이 여러개의 손으로 Slot machine을 다루는 컨셉에서 시작한 기법이다. 여러개의 Slot machine이 있다는 것은 각기 다른 확률을 갖고 있는 event중 선택을 하여 최선의 결과를 이끌어내야 한다는 것을 의미한다. 위와 같이 5가지 경우가 있다면 D5를 선택하는 것이 좋은 선택이 될 것이다. 이때 좋은 선택을 해내는 가장 간단한 방법은 각각을 몇번씩 선택해보고 그 결과치를 평균을 내어 그 평균값이 최대인 결과를 계속해서 선택하면 될 것이다. 그러나 그런 방법은 안정도는 높은 수 있지만 최선의 방법을 찾기에는 어려움이 있을 수 있다. 따라서 아직 잘 알려지지 않은 팔을 당겨서 더 높은 보상을 주는 팔을 찾는 과정인 exploration과 현재까지 알.. 2024. 1. 9. 강화학습 - Intro Introduction 강화학습은 근본적으로 Trial and error learning을 기반으로 한다. 대표적으로 Skinner's experiment처럼 원하는 행동을 하면 보상을 주고 다른 행동을 하면 처벌을 하여 학습을 시키는 것이다. 강화학습(Reinforcement Learning)은 Machine Learning의 한 분야로, 어떤 환경에서 에이전트가 최적의 결정 또는 행동 순서를 학습하는 과정을 다룬다. 강화학습의 핵심은 에이전트가 시행착오를 통해 학습하며, 자신의 행동이 어떤 결과를 가져오는지를 이해하고, 최종적으로는 목표를 달성하거나 최대의 보상을 얻기 위해 최적의 행동 전략을 개발하는 것이다. 강화학습의 주요 구성 요소는 아래와 같다. 에이전트(Agent): 학습하는 주체로, 환경에.. 2024. 1. 7. 이전 1 다음 728x90
