벨만 방정식(Bellman equation)은 동적 프로그래밍과 강화학습 분야에서 핵심적인 역할을 하는 개념입니다. 이 방정식은 리처드 벨(Richard Bellman)에 의해 도입되었으며, 시간에 따른 의사결정 문제를 해결하는데 사용됩니다. 벨만 방정식은 결정 과정의 최적성을 기술하며, 이를통해 복잡한 문제를 더 작고 관리 가능한 부분 문제로 분해하여 해결합니다. 최적의 원리(Optimality Principle): 벨만 방정식은 최적의 원리에 기초하며, 이는 최적 정책의 부분경로도 최적임을 의미합니다. 재귀적인 구조: 최적화 문제를 재귀적으로 풀기 위해 현재 상태의 최적 가치는 다음 가능한 모든 상태의 가치를 바탕으로 결정됩니다. 벨만 방정식은 다음과 같이 응용할 수 있습니다. 동적 프로그래밍(Dynamic Programming): 벨만 방정식은 동적 프로그래밍 알고리즘의 기초를 형성하며, 복잡한 최적화 문제를 순차적인 의사결정 과정으로 분해하여 해결합니다. 강화학습(Reinforcement Learning): 에이전트가 환경과 상호작용하며 최적의 행동 정책을 학습할 때 벨만 방정식을 사용하여 가치 함수를 추정하고 업데이트합니다. 벨만 방정식을 통해 시간에 따른 최적의 의사결정 과정을 모델링하고 분석할 수 있으며, 이는 많은 의사결정 문제와 최적화 문제를 효과적으로 해결하는 데 기여합니다. 마르코프 결정 프로세스(MDP)에서 에이전트가 확률적으로 행동을 한다고 생각하면, 여러 상황에서도 상태 가치함수를 구할 수 있게 되는데, 이때 핵심이 벨만 방정식입니다. 벨만 방정식은 MDP에서 가장 중요한 방정식입니다.
벨만 기대 방정식(Bellman Expectation Equation): 정책 π에 대한 상태 가치 함수 Vπ(s)를 평가하기 위해 사용됩니다. Vπ(s)=∑a π(a∣s)∑s′,r P(s′,r∣s,a)[r+γV π(s′)] 여기서 P(s′,r∣s,a)는 상태 s에서 행동 a를 취했을 때, 상태 s′로 이동하고 보상 r을 받을 확률을 나타내며, γ는 할인율입니다. 벨만 최적 방정식(Bellman Optimality Equation): 최적 가치 함수 V∗(s)를 찾기 위해 사용됩니다. V∗(s)=max a ∑s′,r P(s′,r∣s,a)[r+γV∗(s′)] 이 방정식은 주어진 상태에서 가능한 모든 행동을 고려하여 최대 보상을 제공하는 행동을 찾습니다.
리처드 벨만(Richard Bellman)이 벨만 방정식을 만든 원리는 최적화 문제를 재귀적으로 해결하기 위한 동적 프로그래밍(Dynamic Programming, DP) 기법의 개발에 근거합니다. 그의 주된 목표는 복잡한 결정 과정을 더 작고 관리 가능한 부분 문제로 분해하는 것이었습니다. -최적의 원리 (Principle of Optimality) 벨만의 핵심 아이디어 중 하나는 최적의 원리입니다. 이 원리는 "최적화 경로의 모든 부분 경로 역시 최적이어야 한다"는 개념에 기반합니다. 즉, 어떤 문제에 대한 최적의 해결책은 그 해결책의 모든 부분 집합에 대해서도 최적이어야 한다는 것을 의미합니다. -재귀적인 구조 벨만 방정식은 문제의 최적 해결책을 찾기 위해 재귀적인 구조를 사용합니다. 각 단계에서의 최적 결정은 다음 단계의 최적 결정에 의존하며, 이러한 방식으로 문제를 순차적으로 해결합니다. 이 과정에서 각 상태의 최적 가치는 다음 상태들의 최적 가치를 기반으로 계산됩니다. -동적 프로그래밍 (Dynamic Programming) 동적 프로그래밍은 이러한 재귀적 구조와 최적의 원리를 사용하여, 복잡한 문제를 더 작은 부분 문제로 나누고, 각 부분 문제의 해결책을 저장한 후 재사용함으로써 전체 문제의 해결책을 효율적으로 찾는 방법입니다. 벨만은 이 접근법을 통해 시간적 및 공간적 복잡성을 줄이는 데 기여했습니다. 리처드 벨만이 개발한 벨만 방정식은 동적 프로그래밍의 근간을 이루며, 최적화 문제를 해결하는 데 있어서 중요한 이론적 기반을 제공합니다. 이 방정식을 통해, 복잡한 최적화 문제를 시간에 따라 분할하여 각 단계에서의 최적 결정을 차례로 찾아갈 수 있습니다.
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. "동적 계획법"과 "동적 프로그래밍"은 같은 의미로 사용되며, 이 방법은 리처드 벨만(Richard Bellman)에 의해 개발되었습니다. 최적의 원리 (Principle of Optimality): 동적 계획법은 최적의 원리에 기반을 두고 있습니다. 이 원리는 어떤 문제의 최적 해결책이 그 문제의 하위 문제에 대한 최적 해결책을 포함해야 한다고 주장합니다. 하위 문제로 분할 (Problem Decomposition): 복잡한 문제를 더 작고 관리 가능한 하위 문제로 분할합니다. 이 하위 문제들은 종종 중복되며, 각각이 한 번만 계산되고 그 결과가 재사용됩니다. 메모이제이션 (Memoization): 동적 계획법은 계산된 하위 문제의 해결책을 저장하고 필요할 때 재사용하는 기법을 사용합니다. 이를 통해 계산 시간을 크게 줄일 수 있습니다. 동적 계획법의 주요 단계는 다음과 같습니다. 문제 정의: 문제를 상태로 정의하고, 각 상태에 대한 결정 및 그 결과를 명확히 합니다. 재귀적 관계 찾기: 문제의 각 상태에 대한 최적 해결책이 하위 문제의 해결책에 어떻게 의존하는지를 나타내는 재귀적 관계(재귀 방정식)를 찾습니다. 하위 문제 풀기: 재귀적 관계를 사용하여 하위 문제를 작은 것부터 차례대로 풀어나갑니다. 솔루션 구성: 하위 문제의 해결책을 결합하여 원래 문제의 해결책을 구성합니다. 동적 계획법의 응용 분야는 다음과 같습니다. 동적 계획법은 많은 분야에서 복잡한 최적화 문제를 해결하는 데 사용됩니다. 예를 들어, 경로 찾기, 자원 할당, 스케줄링, 재고 관리, 금융 모델링 등 다양한 영역에서 응용됩니다. 동적 계획법은 계산 복잡성을 줄이는 효과적인 방법으로, 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제로 나누어 접근합니다. 메모이제이션을 통해 중복 계산을 피하며, 이로 인해 알고리즘의 효율성을 크게 향상시킵니다. 쉽게 말하면 동적 프로그래밍은 한번 계산한 값은 다시 계산하지 않는다는 의미입니다.
피보나치 수열은 수학, 컴퓨터 과학, 자연 현상 연구 등 다양한 분야에서 나타나는 유명한 수열입니다. 이 수열은 13세기 이탈리아의 수학자 레오나르도 피보나치가 소개했으며, 특정 규칙에 따라 수가 연속적으로 나열됩니다. 피보나치 수열은 각 숫자가 바로 앞의 두 숫자의 합으로 이루어진 수열입니다. 0,1,1,2,3,5,8,13,21,34...... 귀납적 정의: 피보나치 수는 재귀적으로 정의되며, 각 항은 이전 두 항의 합으로 계산됩니다. 황금비와의 관계: 피보나치 수열에서 연속하는 두 수의 비율은 황금비(약 1.618)에 근접합니다. 이는 수열이 진행됨에 따라 점점 황금비에 가까워집니다. 자연 현상과의 연관성: 피보나치 수열은 해바라기의 씨앗 배열, 파인애플의 비늘 패턴, 나선형 은하 등 자연에서 발견되는 다양한 구조와 관련이 있습니다. 재귀적 계산: 순수한 재귀적 접근은 많은 중복 계산을 포함하므로, 큰 n에 대해 매우 비효율적일 수 있습니다. 동적 프로그래밍: 중복 계산을 피하기 위해 동적 프로그래밍 기법을 적용하여 피보나치 수를 효율적으로 계산할 수 있습니다. 피보나치 수열은 수학적 아름다움뿐만 아니라 실제로 많은 자연 현상과 공학적 문제 해결에서 그 응용을 찾을 수 있어 중요한 의미를 가집니다. 피보나치 수열의 수학식은 다음과 같습니다. F(0)=0, F(1)=1 그리고 n이 1보다 크면, F(n) = F(n-1) + F(n-2) 이렇게 계산할 수 있습니다.
주사위가 있습니다. 총 1~6까지의 숫자가 있고, 각각의 눈이 나올 확률이 1/6이 되는 이상적인 주사위라고 가정합니다. 실제로는 수백 수천회 이상 던져야 대수의 법칙에 따라 1/6에 근사치로 나올 뿐 적은 횟수를 던졌을때는 정확히 1/6이 아닌 편차가 존재하지만 이번 예시에서는 정확히 1/6이라고 가정해 봅니다. 던져서 나올 주사위의 눈 개수를 x라는 확률변수로 표현하고, 각 눈이 나올 확률은 다음처럼 수식으로 표현합니다. p(x) = 1/6 주사위를 굴렸을때 나올 눈의 기대값을 구해봅니다. E[x] = 1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6 = 3.5 눈의 개수와 확률을 곱한 다음, 그 모두를 더한 값이 기대값이 됩니다. 이것을 수학식으로 표현하면, E[x] = Σx의 전체합 x*p(x)가 됩니다. 그 다음 이 주사위에서 짝수가 나올 경우 앞면이 0.8 확률, 뒷면이 0.2 확률로 나오는 동전이 주어집니다. 주사위에서 홀수가 나올 경우에는 원래 동전처럼 앞뒤가 각각 0.5의 확률의 동전이 주어집니다. 보상은 동전의 앞면이 나오면 그 전의 주사위 갯수만큼의 보상을 얻고 뒷면이 나온다면 보상은 0으로 주어집니다. 그러면 보상에서 처음 주사위 갯수가 3이 나오고 동전도 앞면이면 보상이 3이 되고, 주사위 갯수가 5가 나오고 동전도 앞면이면 보상이 5가 되고, 주사위 갯수가 6이 나오고 동전도 앞면이면 보상이 6이 됩니다. 동전이 뒷면이면 보상은 0이 됩니다. 이런 예에서 보상의 기댓값 계산은 두가지 확률을 동시적으로 계산해야 하는데 이와같은 동시확률 계산 수식은 다음과 같습니다. 여기서 먼저 주사위의 눈을 x, 동전의 결과를 y로 표기하겠습니다. p(x,y) = p(x)p(y|x) 풀어서 설명하자면 주사위 x개가 나왔을때 확률 * 주사위 x일때 y가 나올 확률 이렇게 됩니다. 이것을 모두 풀어서 위 사례의 보상 기댓값을 구해보겠습니다. (1/6 * 1/2 *1) + (1/6 * 1/2 *0) + (1/6 * 4/5 *2) + (1/6 * 1/5 *0) + (1/6 * 1/2 *3) + (1/6 * 1/2 *0) + (1/6 * 4/5 *4) + (1/6 * 1/5 *0) + (1/6 * 1/2 * 5) + (1/6 * 1/2 * 0) + (1/6 * 4/5 * 6) + (1/6 * 1/5 * 0) = (1/6 * 1/2 *1) + (1/6 * 4/5 *2) + (1/6 * 1/2 *3) + (1/6 * 4/5 *4) + (1/6 * 1/2 * 5) + (1/6 * 4/5 * 6) = 2.35 기댓값은 [값*그 값이 발생할 확률]의 합입니다. 보상의 기댓값을 수학식으로 표현하면, E[r(x,y)] = Σx의 전체합 Σy의 전체합 p(x,y)r(x,y) = Σx의 전체합 Σy의 전체합 p(x)p(y|x)r(x,y) 이것으로 벨만 방정식을 맞이할 기대값에 대한 식이 도출되었습니다. 다음 장에서는 위 식을 이용해 벨만 방정식을 도출하는 방법을 알아보도록 하겠습니다.