*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Metric Space>
Metric space란?
- A metric space는 ordered pair 이며, 여기서
- 은 집합(set)
- 는 metric(거리 함수)
Metric의 조건 (Axioms)
x, y, 에 대해, 거리 함수 는 다음을 만족해야 함:
항등성(Identity of Indiscernibles)
- 한 점에서 자기 자신까지의 거리는 0이다.
양의 성질(Positivity)
- 서로 다른 두 점 사이의 거리는 항상 0보다 크다.
대칭성(Symmetry)
- 거리 함수는 대칭적이다.
삼각 부등식(Triangle Inequality)
- 삼각 부등식이 성립한다.
이러한 조건을 만족하면, (M,d)(M, d)는 metric space라고 한다.
<거리 함수(distance function)>
거리 함수(distance function)의 핵심 성질 중 하나는 '삼각 부등식(triangle inequality)'이다.
삼각 부등식은 다음과 같이 설명할 수 있다:
- 상단 그림: 세 점 x, y, z가 있고, 각 점 사이의 거리가 d(x,y), d(y,z), d(x,z)로 표시되어 있다. 이 세 점은 삼각형을 형성한다.
- 하단 수식: d(x,z) ≤ d(x,y) + d(y,z)
이 부등식은 "두 점 사이의 직접적인 거리는 제3의 점을 경유하는 거리보다 항상 작거나 같다"는 것을 의미한다.
삼각 부등식이 중요한 이유:
- 이것은 모든 거리 함수(metric)가 반드시 만족해야 하는 조건.
- 유클리드 공간, 맨해튼 거리, 코사인 유사도 등 다양한 거리 측정 방식에 적용.
- 알고리즘(특히 최단 경로 알고리즘)의 기본 원리로 사용.
- 기계학습에서 클러스터링이나 근접성 계산에 활용.
실생활에서의 예: 서울에서 부산까지 직접 가는 거리는 서울에서 대전을 경유해 부산으로 가는 거리보다 항상 짧거나 같다(같은 경우는 세 점이 일직선상에 있을 때).
<p-노름 (p-norm)>
이 수식은 벡터
의 p-노름을 나타낸다.
p-노름은 벡터의 각 성분의 절댓값을 p제곱한 후 합하고, 그 합의 p제곱근을 취한 값이며 p가 무한대로 갈 때, p-노름은 최대 노름(max-norm)으로 수렴:
거리 측정(metric)으로 활용
p-norm은 두 벡터 사이의 거리를 측정하는 metric으로 활용될 수 있다:
- L¹ 거리(맨해튼 거리): d₁(x, y) = |x₁ - y₁| + ... + |xₙ - yₙ| 두 점 사이를 격자 경로로 이동할 때의 거리를 의미.
- L² 거리(유클리드 거리): d₂(x, y) = (|x₁ - y₁|² + ... + |xₙ - yₙ|²)^(1/2) 일상적으로 생각하는 두 점 사이의 직선 거리를 의미.
- L∞ 거리(Chebyshev 거리): d∞(x, y) = max(|x₁ - y₁|, ..., |xₙ - yₙ|) 각 좌표축 방향으로의 거리 중 가장 큰 값을 의미.
<수축 매핑(Contraction mapping)>
- 거리 공간 (X, d)에서 매핑 T: X → X가 있을 때
- 0 ≤ c < 1인 상수 c가 존재하여
- 모든 x, y ∈ X에 대해 d(T(x), T(y)) ≤ c·d(x, y)를 만족하면
- T를 수축 매핑 또는 수축이라고 함
수축 매핑과 앞서 배운 개념들의 연계성 설명:
- 수축 매핑의 의미:
- 수축 매핑은 공간의 점들 사이의 거리를 줄이는 함수.
- 즉, 두 점 x, y가 있을 때, 이 점들을 T라는 함수에 통과시키면 T(x)와 T(y) 사이의 거리는 원래 거리의 c배 이하로 줄어든다(c < 1).
- p-norm과의 연계:
- p-norm은 벡터 공간에서 거리를 측정하는 방법을 제공.
- 수축 매핑 T가 p-norm 공간에서 정의될 때, d(T(x), T(y)) ≤ c·d(x, y)의 조건은 다음과 같이 표현: ‖T(x) - T(y)‖ₚ ≤ c·‖x - y‖ₚ
- 삼각 부등식과의 관계:
- 삼각 부등식은 d(x, z) ≤ d(x, y) + d(y, z)를 말한다.
- 수축 매핑 T는 이 성질을 보존하면서 거리를 줄인다.
- 즉, d(T(x), T(z)) ≤ d(T(x), T(y)) + d(T(y), T(z)) 또한 여전히 성립한다.
- 중요성과 응용:
- 수축 매핑은 부동점 정리(Fixed Point Theorem)의 기초가 된다.
- 반복적 알고리즘, 미분방정식의 근사해, 프랙탈 생성, 그리고 머신러닝의 수렴성 분석 등에 활용.
- 특히, 반복 함수 시스템(IFS)을 통한 프랙탈 생성에서는 수축 매핑이 핵심 원리.
|응용|
그리드월드 문제에서 수축 매핑 과정 풀이
1. 환경 설정
- 3×3 그리드월드
- 상태: s₀(0,0)부터 s₈(2,2)까지 9개 상태
- 행동: 상(0), 우(1), 하(2), 좌(3) 네 방향
- 보상:
- 목표 지점 s₈(2,2)에 도달하면 +1
- 그 외 상태에서는 모든 행동에 -0.1 (이동 비용)
- 감가율(γ): 0.9
2. 초기 가치 함수
모든 상태의 가치 함수를 0으로 초기화:
3. 첫 번째 벨만 업데이트 (수축 매핑 적용)
3-1. 각 상태별 계산
상태 s₈(2,2) - 목표 지점: 이미 목표 지점이므로 다른 상태로 이동할 필요가 없다. V₁(s₈) = 1 (목표 지점 보상)
상태 s₇(2,1):
- 위로 이동(a=0): 보상 -0.1 + γ·V₀(s₄) = -0.1 + 0.9·0 = -0.1
- 오른쪽 이동(a=1): 보상 -0.1 + γ·V₀(s₈) = -0.1 + 0.9·0 = -0.1
- 아래로 이동(a=2): 불가능, 그리드 밖으로 나가므로 제자리에 머물기 = -0.1 + 0.9·0 = -0.1
- 왼쪽 이동(a=3): 보상 -0.1 + γ·V₀(s₆) = -0.1 + 0.9·0 = -0.1
최대값은 -0.1이므로, V₁(s₇) = -0.1
상태 s₄(1,2):
- 위로 이동(a=0): 보상 -0.1 + γ·V₀(s₁) = -0.1 + 0.9·0 = -0.1
- 오른쪽 이동(a=1): 보상 -0.1 + γ·V₀(s₅) = -0.1 + 0.9·0 = -0.1
- 아래로 이동(a=2): 보상 -0.1 + γ·V₀(s₇) = -0.1 + 0.9·0 = -0.1
- 왼쪽 이동(a=3): 보상 -0.1 + γ·V₀(s₃) = -0.1 + 0.9·0 = -0.1
최대값은 -0.1이므로, V₁(s₄) = -0.1
상태 s₅(1,1) - 중앙:
- 위로 이동(a=0): 보상 -0.1 + γ·V₀(s₂) = -0.1 + 0.9·0 = -0.1
- 오른쪽 이동(a=1): 보상 -0.1 + γ·V₀(s₆) = -0.1 + 0.9·0 = -0.1
- 아래로 이동(a=2): 보상 -0.1 + γ·V₀(s₈) = -0.1 + 0.9·1 = 0.8
- 왼쪽 이동(a=3): 보상 -0.1 + γ·V₀(s₄) = -0.1 + 0.9·0 = -0.1
최대값은 0.8이므로, V₁(s₅) = 0.8
(나머지 상태들도 유사하게 계산)
3-2. 첫 번째 업데이트 후 가치 함수
첫 번째 벨만 업데이트 후 가치 함수는 다음과 같다:
4. 두 번째 벨만 업데이트
4-1. 각 상태별 계산 (일부 예시)
상태 s₅(1,1) - 중앙:
- 위로 이동(a=0): 보상 -0.1 + γ·V₁(s₂) = -0.1 + 0.9·0.8 = 0.62
- 오른쪽 이동(a=1): 보상 -0.1 + γ·V₁(s₆) = -0.1 + 0.9·0.8 = 0.62
- 아래로 이동(a=2): 보상 -0.1 + γ·V₁(s₈) = -0.1 + 0.9·1.0 = 0.8
- 왼쪽 이동(a=3): 보상 -0.1 + γ·V₁(s₄) = -0.1 + 0.9·(-0.1) = -0.19
최대값은 0.8이므로, V₂(s₅) = 0.8
상태 s₂(0,2):
- 위로 이동(a=0): 불가능, 그리드 밖으로 나가므로 제자리에 머물기 = -0.1 + 0.9·V₁(s₂) = -0.1 + 0.9·0.8 = 0.62
- 오른쪽 이동(a=1): 보상 -0.1 + γ·V₁(s₃) = -0.1 + 0.9·(-0.1) = -0.19
- 아래로 이동(a=2): 보상 -0.1 + γ·V₁(s₅) = -0.1 + 0.9·0.8 = 0.62
- 왼쪽 이동(a=3): 불가능, 그리드 밖으로 나가므로 제자리에 머물기 = -0.1 + 0.9·V₁(s₂) = -0.1 + 0.9·0.8 = 0.62
최대값은 0.62이므로, V₂(s₂) = 0.62
4-2. 두 번째 업데이트 후 가치 함수
5-1. 거리 계산 (최대 변화량)
첫 번째 업데이트와 초기값 사이의 거리:
두 번째 업데이트와 첫 번째 업데이트 사이의 거리:
5-2. 수축 비율 계산
이 값은 감가율 γ = 0.9보다 작으므로 수축 매핑 조건을 만족한다!
6. 최종 수렴을 향한 추가 업데이트
계속해서 더 많은 업데이트를 수행하면, 가치 함수는 점차 수렴한다.
V₃, V₄, ... 등을 계산하면 각 업데이트 간 최대 변화량이 점점 감소하며, 변화량의 비율이 항상 γ = 0.9 이하로 유지된다.
V* (최적 가치 함수)에 도달하면 더 이상 변화가 없어집니다. 이 함수는 벨만 방정식의 해, 즉 벨만 연산자의 고정점이 된다.
7. Q-학습 예시: 한 번의 업데이트
Q-학습에서는 하나의 샘플 경험 (s, a, r, s')에 대해 Q-함수를 업데이트한다:
상태 s₄(1,0)에서 오른쪽으로 이동(a=1)하여 s₅(1,1)로 갔다고 가정한다:
- 초기 Q-값: Q₀(s₄, a=1) = 0
- 보상: r = -0.1 (이동 비용)
- 다음 상태에서의 최대 Q-값: max_a Q₀(s₅, a) = 0
- 학습률: α = 0.1
Q-함수 업데이트:
여러 에피소드를 거치면서 이런 업데이트가 반복되고, 결국 Q-함수는 최적 Q-함수 Q*로 수렴한다. 이 과정에서도 수축 매핑의 원리가 적용된다.
이것이 강화학습에서 수축 매핑 이론이 실제 알고리즘에 적용되는 과정이다. 감가율 γ < 1인 한, 벨만 업데이트는 항상 수축 매핑이 되어 최적 해로 수렴하게 된다.
|인증|
-------
패스트캠퍼스 링크