[Study]Chapter 4, 복잡한 환경의 검색

이번 챕터에서는 현실 세계에 좀 더 가까이 다가가기 위해 이전 장의 단순화 가정들을 완화한다.

CHAPTER 4. 복잡한 환경의 검색

1. 국소 검색과 최적화문제

국소 검색\(_{local-search}\) 알고리즘들은 현재 상태에서 이웃 상태들을 찾는 방식으로 작동하며, 경로나 도달된 상태들의 집합을 추적하지 않는다. 이는 체계적이지 않지만 메모리를 적게 소비하고, 체계적인 알골지즘이 적합하지 않은 커다란 상태태 공간에서도 적당한 해답을 찾아내는 경우가 많다.

목적함수를 기준으로해서 가장 좋은 상태를 찾는 최적화 문제를 푸는데에도 유요ㅕㅇ하다./

Figure 1 : state-space landscape

언덕오르기 : 다음에 어디로 갈지를 고려하지 않고 눈앞의 상황에서 가장 좋은 이웃을 선택한다는 점에서, 언덕오르기를 탐욕적 국소검색이라고 부르기도 한다.

극대값 능선 ridge : 극댓값들이 연이어 있는 상황. 대지 palteau 오르막으로 가는 출구가 없는 평평한 극댓값이거나 진척이 가능한 어꺠 shoulder이다.

위의 경우에 도달하게 되면 더 이상의 진척이 불가능한 지점에 다다르게 된다. 더 많은 문제를 풀려면 어떻게 해야할까? 횡이동 sideway move를 허용하는 방법이있다. 언덕오르기의 여러 변형이 고안되었는데,

• 확률적 언덕 오르기(Stochastic hill climbing)
  • 오르막 이동 중 하나를 무작위로 선택
  • 확률 : 경사(steepness)에 따라 달라짐
• 최초 선택 언덕 오르기(First-choice hill climbing)
  • 현재 상태보다 더 나은 후행자가 나올 때까지 후행자들을 무작위로 생성
• 무작위 재시작 언덕오르기(Random-restart hill climbing)
  • 목표를 찾을 때까지 초기 상태를 무작위로 생성(리세마라)
  • 목표 상태와 일치하는 초기 상태가 생성된다면, 검색에 성공할 확률은 1
  • 각 climbing-hill 성공확률이 p인 경우, 필요한 재시작(반복) 횟수의 기댓값은 1/p

언덕 오르기의 성공은 상태공간지형의 형태에 아주 크게 의존한다.

모의 정련 simulated Annealing 순수한 무작위 보행, 즉 값을 신경 쓰지 않고 후행자들 중 하나를 무작위로 선택하는 방식은 결국에는 전ㄷ역 최댓값에 도달하지만 극도로 비효율적이다. 따라서 효율성과 완결성을 모두 제공하는 방식으로 언덕 오르기와 무작위 보행을 결합해 보는 것은 합당한 시도이다. 모의 정련 simulated annealing 이 바로 그러한 시도에서 나온 알고리즘의 하나이다. 야금학에서 정련은 금속을 노퓨은 온도로 가열한 후 점차 식혀서 해당 물질이 저에너지 결정 상태에 도달하게 함으로써 단련하거나 강화하는 과정을 말한다. 경사 하강법으로 관점을 바꾸어서 굴곡진 지형에서 탁구공을 가장 깊은 계곡 바닥으로 내린다고 상상하고 지형을 세게 흔드는것에서 점차 감소시키는 방법으로. 모의 정련 알고리즘의 전반적인 구조는 언덕 오르기와 비슷하다. 그러나 최상의 이동을 선택하는 대신 무작위로 이동을 선택한다는 점이 다르다. 그떄문에 상황이 나아지면 항상 그 이동을 챝택한다. 상황이 나아지지 않으면 알고리즘은 1보다 낮은 확률로 그 이동을 채택하고, 확률은 이동의 ‘나쁨’ 정도에 지수적으로 감소한다. 여기서 나쁨 정도란 상황 평가의 감소량 $ΔE$ 를 말한다.이 확률은 똫란 ‘온도’ T가 감소함에 따라 감소한다. T가 높은 시작 시점에[서는 ‘나쁜’ 이동이 채택될 확률이 높지만,. T가 감소함에 따라 그확률이 점차 낮아진다. 따라서 모든 확률은 전역 최댓값에 집중한다면 볼츠만 분포Boltzmann distribution \(e^{ΔE/T}\)의 성질에 따라, 알고리즘이 전역 최적값을 찾을 확률은 1에 접근하게 된다.

국소 빔 검색 하나가 아니라 무작위로 생성한 상태 k개의 상태를 추적. 무직위 재시작 검색에서 각 검색 과정은 서로 독립적으로 실행, 반면 국소 빔검색에서는 병렬적인 검색 스레드들이 유용한 정보를 주고 받는다. k개의 상태들 사이의 다양성 부족 떄문에 문제를 겪으면 k배 느려질 수 있는데 이러한 문제는 확률적 빔 검색이라는 변형을 사용하면 완화가 된다.

진화 알고리즘 활률적 빔 검색의 한 변형으로 개체들의 군집, 즉 개체군 population에서 생존에 가장 적합한 개체들을 선택하고 재조합recombination이라고 부르는 과정을 통해 자손 offspring들을 생성한다.유전 알고리즘의 형탠는 무궁무진한데 각 형태를 특정 짓는 요소들은 다음과 같다.

Figure 2 : 4-2

개체군의 크기 각 개체의 표현 방식 - 진화전력에서는 각 개체가 실수 수열이고 유전 프로그래밍 genetic programming에서는 각 개체가 컴퓨터 프로그램이다. 혼합수 mixing number - 보통 p=2, p=1인 경우 확률적 빔 검색과 같음. 다음 세대의 부모가 될 개체들을 선택하는 과정 재조합 절차 돌연변이 비율 mutation rate 다음세대형성방법 선별 culling 특정 문턱값 아래의 무든 개체를 폐기하거나 점수가 높은 몇개를 포함하는 정예주의 eltism이 있다.

확률적 빔 검색과 비슷하되, 교차 연산이 추가되었다는 점이 특징. ㅇ뉴전 알고리즘 이론은 알고리즘의 작동 방식을 스키마 schema라는 개념을 이용해서 설명한다. 스키마는 문자를 구체적으로 지정하지 않은 자리들이 있는 부분 문자열(236***)이다. 이 스키마와 부합하는 문자열(236123)을 그 스키마의 사례 instance라고 부른다.

확률적 빔 검색과 진화의 주된 차이점은, 진화에 서는 후행자가 하나가 아니라 여러 개의 개체로부터 발생하는 유성생식이 일어난다는 것이다.

학습은 적합도 지형을 효과적으로 완화하며, 그러면 진화의 속도가 빨라진다.

볼드윈 효과(Baldwin Effect)

환경과는 잘 맞지 않는 어떤 형질을 갖고 있는 어떤 유기체가 생존에 도움이 되는 방식으로 환경에 유연하게 적응하는 방법을 배운다면, 유기체는 살아 남아서 자신의 형질을 후손에게 전달 가능

2. 연속 공간의 국소 검색

이산적인 환경과 연속적인 환경의 구분을 설명하면서 대부분의 실세계 환경은 연속적이고 연속 동작 공간은 분기 계쑤가 무한대이기 떄문에 지금까지의 알고리즘은 잘 작동하지 않는다.

이러한 연속 상태 공간과 관련된 무제를 피하는 한 가지 방법은 연속 상태 공간을 그냥 이산화 discretization 하는 것이다. 예를 들어 연속 2차 연속공간을 델타δ인 정규 격자의 고정된 점들로만 제한한다. 인접한 두 점 사이에서 목적함수의 값을 변경해서 진척 정도를 측정하는 방법들을 실험적 경사법 emprical gradient method 라고 부른다. 목적함수를, 미적분을 이용해서 문제를 실험적이 아니라 해석적으로 풀 수 이쓴ㄴ 형태의 수학 공식으로 표현하곤 한다. 이는 기울기를 국소적으로 풀 수 있음을(그러나 전역적으로는 풀 수는 없음을) 뜻한다.

\[x \leftarrow x + \alpha\nabla f(x)\]

여기서 $\alpha$ 는 흔히 단계 크기 라고 부르는 작은 상수이다. 이 값이 너무 작으면 단계수가 너무 많아지고, 너무크면 검색이 최댓값을 지나 칠 수 있다.

직선 검색 line-search 기법은 f가 다시 감소할 떄까지 현재의 기울기 방향을 연장해서 이 딜레마를 극복한다.

뉴턴-랩슨법 Newton-Raphson method 유서깊고 가장 효과적인 알고리즘으로 아래와 같이 변형이 가능하다.

\[x \leftarrow x - g(x)/g'(x) \\ x \leftarrow x - H_f^{-1}(x)\nabla f(x)\]

여기서 헤세 행렬$H_f(x)$은 행렬 성분 $H_{ij}$들은 $\partial^2 f/ \partial x x_i \partial x_j$로 이루어진다.

제한된 최적화 constrained optimization 방법은 해달들이 변수 값에 대한 어떤 엄격한 제약을 충족해야 하는 최적화 문제를 가리킨다. 문제의 난이도는 제약들의 셩격과 목적함수에 의존한다. 가장 잘 알려진 범주는 성형 계획법 문제로 반드시 하나의 볼록집합 convex set을 형성하는 선형 부등식들이다. 선형 계쵝법은 좀 더 일반적인 볼록 최적화 convex optimization 문제의 한 특수 경우이다.

3. 비결정론적 동작들을 수반한 검색

환경이 부분 관측 가능이면 에이전트는 자신이 어떤 상태에 있는지 확실히 알 수 없다. 또한, 자신의 동작에 의해 환경이 어떤 상태로 전이하는 지도 알 수가 없어 에이전트가 자신이 현재 처해 있을 가능성이 있다고 믿는 물리적 상태들의 집합인 믿음 상태 belief state라고 생각한다.

AND-OR 트리 이러한 환경에서 문제의 해답은 향후 받을 지각에 따라 어떤 동작을 수행할 것인지를 명시한 조건부 계획으로 해답이 if 문을 통해 트리 구조가 된다. 에이전트의 선택은 실행 가능한 여러 동작 중 하나를 택(OR 노드)하거나 각 동작의 결과에 대한 환경의 선택(AND 노드)에 의해서도 일어난다.

반복시도 가끔 에이전트가 동작이 실패해서 실패를 돌려주게 되는 경우 반복해서 시도하는 순환 해답 cyclic solution이 존재하는데, 이는 모든 잎 노드가 목표 상태이고 계획의 모든 지점에서 각 잎 노드에 도달할 수 있어야 한다는 것 그리고 기존에 관측되지 않은 사실 때문에 비결정론이 발생하지 않는다는 가정이 있어야 한다.

4. 부분 관측 가능 환경의 검색

자신의 지각들로만으로는 정확한 상태를 결정할 수 없다. 따라서 에이전트들은 목표를 달성하기 위한 동작들 뿐만 아니라 현재 상태에 관한 불확실성을 줄이는 동작드롣 수행할 필요가 있다.

1. 관측 없는 검색.

아무런 정보도 제공하지 않는 문제를 가리켜 무감지기 sensorless 문제 또는 순응 conformant 문제라고 부른다. 무감지 문제의 해답은 조건부 계획이 아니라 동작열이다. 단, 물리적 상태들이 아니라 믿음 상태들의 공간을 검색한다. 여기서 믿음 상태 공간에서 문제는 완전 관측 가능이고, 환경은 비결정론적이어도 가능하다는 점을 주목하기 바란다.

믿음 상태 문제는 다음 요소들로 구성된다.

• 상태들
• 초기상태
• 동작들
• 전이 모형
• 목표 판정
• 동작 비용

1. 부분 관측 가능 환경의 검색

약간의 감지만 가능해도 상황이 크게 달라진다. 부분 관측 가능 문제에 대한 믿음 상태들의 전이모형은 아래와 같은 3-stage로 생각할 수 있다.

Figure 4-3

• 예측 믿음 상태 b에서 동작 a를 수행해서 나온 결과 미등ㅁ 상태 result(b,a)를 계산한다.
• 가능한 지각 possible percpts 믿음상태에서 관측될 수 있는 지각 o들의 집합을 계산한다..
• 갱신 update - 지각의 결과로 나올 수 있는 믿음 상태를 계산한다.

위와 같은 세 단계를 결합하면, 주어진 동작에서 나올 수 있는 믿음 상태들과 그로부터 가능한 지각들을 얻게 된다.

그러면 조건부 계획인 AND-OR 검색 알고리즘 등을 이용해 해답을 도출할 수 있게 된다.

에이전트 결정론적 환경의 에이전트와 이 에이전트와 주된 차이점은 해답이 동작열이 아닌 조건부 계획이고, 자신의 믿음 상태를 유지하는 재귀적 상태 추정기가 필요하다는 것이다.

\[b' = Update(Predict(b,a),o)\]

이러한 재귀적 상태 추정기는 모든 지능 시스템의 핵심 기능으로 감시 mnonitoring, 필터링 filtering, ㅅ상태 추정 sttate estimation 등으로 다양하다.

5. 온라인 검색 에이전트와 미지 환경

지금까지는 해답을 계싼한 후에야 첫 동작을 실행하는 오프라인 검색 offline search 알고리즘을 사용했다. 반면 온라인 검색 online search 에이전트는 계산과 동작을 교대로 실행한다. 이는 동적 또는 준 동적환경과 같이 머물러있으면 불이익이 생기는 환경에 유용하고 비결정론적인 문제 영역에서도 실제로 발생하지 않는 우발 사건에 계산 노력을 줄이는 도움이 있다.

해당 문제에서 에이전트는 계산, 감지, 동작을 번걸아 실행해서 푸는데에이전트가 상태 s에서 실제로 동작 a를 수행하기 전까지는 result(s,a)를 결정할 수 없다.마지막으로, 에이전트가 현재 상태에서 목표 상태까지의 거리를 추정하는 허용가능한 발견적 함수 $h(s)$에 접근할 수 도 있따.

일반적으로 에이전트의 목적은 최소의 비용으로 목표 상태에 도달하는 것으로 이 비용은 에이전트가 실제로 이동하는 경로의 총 경로 비용이고, 이 비용을 만일 에이전트가 검색 공간을 미리 알고 있었다면 따랐을 경로, 즉 기지 환경의 최적경로의 비용과 비교한다. 이 둘의 비를 경쟁비 competitive ratio라고 부른다. 이렇게 되면 목적은 경쟁비를 가능한 낮추는 것이다.

온라인 검색은 막다른 골목 dead-end 상황에 처할 수 있따.일반적으로, 모든 상태 공간에서 막다른 골목을 피ㅣ할 수 있는 알고리즘은 없다. 그러므로 에이전트로서는 두 상태 공간에서 적절한 동작이 무엇인지 알 방법이 없는 대립 논거 adversary argument의 한 예이다. 로봇 탐험 분제에서 자연 지형 떄문에 일부 동작들이 비가역적 irreversible 동작이 되는 상태들이 있따.

온라인 검색 에이전트 관측 가능 환경에서 온라인 에이전트는 동작 하나를 실행할 때마다 자신이 어떤 상태에 도달했는지를 말해 주는 지각을 받아 자신의 환경 지도를 증강해 다음에 어디로 갈것인지를 계획한다. 여기서 오프라인 알고리즘은 상태공간에서 자신의 모형을 탐색하지만 온라인 알고리즘은 실제 세계를 탐색한다. 이는 다음 노드를 확장하기 위해 멀리 있는 상태까지 가야하는 비효율 성을 비하려면 노드들을 국소적인 순서로 확장하는 것이 바람직한 것으로 보인다.

온라인 국소 검색

dfs처럼 언덕 오르기 검색도 노드 확장이 국소적이라는 속성을 가지고 있다.또한, 무작위 보행을 이용하는 탐험 방법도 생각해볼만 하다.

H(s)는 발견적 추정치 h(s)로 시작하나, 에이전트가 상태 공간에 대한 경험을 쌓을 수록 점차 갱신된다.

FIgure 4-4 LRTA* learning real-teim A*

온라인 검색의 학습 온라인 검색의 에이전트는 초기에는 무지한 상태이며, 따라서 여러 가지 학습의 기회가 존재한다. 첫쨰로, 에이전트는 환경의 ‘지도’를 배운다. 각 상태의 각 동작의 결과를 배운다. 둘쨰로, LRTA* 처럼 국소 갱신 규칙을 이용해서 각 상태의 좀 더 정확한 추정치를 얻게 된다. 일단 참값을 얻었다면, 그냥 비용이 제일 낮은 후행자를 따르기만해도 최적해를 얻게 되는 순수한 언덕 오르기가 최적의 전략이된다.

. REFERENCES

1. temp
2. temp
3. temp
4. temp