혼동하기 쉬운 점과 요약

토론 1. 표를 채울 차례가 없으면 동적 계획법을 못 쓰나

「동적 계획법」 절의 5 × 5 격자에서 이번에는 오른쪽·아래뿐 아니라 위·왼쪽으로도 한 칸씩 갈 수 있다. 칸마다 「여기서 도착까지 가장 짧은 시간」을 적는 표를 채울 수 있는가?

바둑판 동네에서 이번에는 위로도, 왼쪽으로도 갈 수 있게 해요. 칸마다 표지판을 세울 수 있을까요?

식부터 적어 볼게요. 칸의 표지판 값은 그 칸의 시간에 이웃 넷의 표지판 값 가운데 가장 작은 것을 더한 거예요. 그런데 오른쪽·아래로만 갈 때는 도착 칸에서 거꾸로 훑으면 오른쪽 이웃과 아래 이웃이 늘 먼저 채워져 있었는데, 지금은 오른쪽 칸의 값을 구하려면 다시 내 칸의 값이 필요해요. 먼저 채울 칸이 없으니 이 격자는 표로는 못 풀겠어요.

벨먼의 도시 문제에도 차례가 없었죠. 그때는 어디서 시작했어요?

「모든 도시에서 곧장 도착 도시로 간다」는 처음 값에서 시작해서, 도시마다 고르기를 한 번씩 다시 했어요. 아, 처음 값은 맞지 않아도 되는 거였네요.

격자에는 곧장 도착으로 가는 길이 없으니, 도착 칸에만 그 칸의 시간 2분을 적고 나머지 칸에는 아직 모른다는 뜻으로 ∞ 를 적어 봐요. 민준 학생이 모든 칸을 한꺼번에 다시 적는 일을 한 바퀴로 쳐서 되풀이해 볼래요?

돌려 볼게요. 한 바퀴 돌 때마다 숫자가 적힌 칸이 도착 칸에서 한 칸씩 번져 나가요. 출발 칸에는 여덟째 바퀴에 처음 33이 적히고, 아홉째 바퀴에서는 아무 칸도 안 바뀌어요.

굳은 표는 어때?

오른쪽·아래로만 갈 때의 표와 칸마다 똑같아. 이 칸 시간에서는 위나 왼쪽으로 돌아가서 더 빨라지는 칸이 없었나 봐. 도착 칸에서 거꾸로 다익스트라를 돌려 봐도 출발 칸은 33분이야.

출발 칸에 숫자가 처음 적힌 것이 여덟째 바퀴인 건 우연일까요?

음, 한 바퀴에 한 칸씩 번졌으니까 k 바퀴 뒤에 숫자가 있는 칸은 도착까지 k 번 안에 옮겨 갈 수 있는 칸이에요. 출발에서 도착까지는 적어도 여덟 번 옮겨야 하니까 여덟째 바퀴고요. 그러면 k 바퀴 뒤에 적힌 값은 「k 번 안에 옮겨 가는 길 가운데 가장 짧은 시간」이겠네요.

그러면 많아야 몇 바퀴면 끝날까요?

칸의 시간이 모두 양수라 가장 짧은 길은 같은 칸을 두 번 지나지 않아요. 그러니 많아야 칸 수 − 1, 24번 옮기고, 24바퀴 안에는 표가 굳어요.

벨먼이 도시 N 개면 많아야 N − 1 번 되풀이한다고 한 것과 같네. 그럼 오른쪽·아래로만 갈 때 차례를 따졌던 건 뭐였어?

차례가 있으면 한 번 훑고 끝나니까 빨리 끝내 준 거지. 표가 맞는 데 필요한 건 남은 길이 지금 칸에만 달려 있다는 성질이었고, 차례는 그 표를 몇 번에 채우느냐만 정했어.

그래요. 차례가 있으면 한 번 훑기, 없으면 아무 처음 값에서 값이 굳을 때까지 되풀이하기. 강화학습의 가치 반복이 둘째 길이고, 그때는 할인율이 되풀이를 한 점으로 모아 줘요.

토론 2. 개미 군집은 생물을 흉내 낸 방법이라 분포를 고치는 방법들과 원리가 다른가

「개미 군집」 절의 짧은 길·긴 길 장난감(개미 10마리, ρ = 0.1, 씨앗 3)에서 짧은 길을 고를 확률 p 가 한 판에 어떻게 바뀌는지 적고, 크로스 엔트로피 방법의 업데이트 p ← (1 − ρ)p + ρ·(좋은 샘플의 비율)과 비교하라.

개미 군집 최적화와 크로스 엔트로피 방법, CMA-ES 를 나란히 놓으면 무엇이 같고 무엇이 달라 보여요?

개미 군집은 아르헨티나 개미의 냄새 길을 흉내 낸 거고, 크로스 엔트로피 방법이랑 CMA-ES 는 확률분포를 통계로 맞추는 거잖아요. 출발이 생물이냐 통계냐부터 다르니까, 겉은 비슷해도 원리는 다른 방법 같아요.

장난감 하나로 확인해 봐요. 개미 쪽에서 판마다 고치는 것은 냄새 τ 이고, 크로스 엔트로피 방법에서 고치는 것은 확률 p 예요. 개미의 p 는 한 판에 어떻게 바뀌죠?

일단 한 판을 식으로 적어 볼게요. 두 길의 냄새 합을 S, 이번 판에 개미들이 남긴 냄새 합을 A 라 하면, 다음 판의 p 는 ((1 − ρ)τ_짧은 + 짧은 길에 남긴 냄새) ÷ ((1 − ρ)S + A) 예요.

분자를 둘로 나눠 볼까요. 옛 냄새에서 온 것과 이번 판에 남긴 것으로요.

옛 냄새 쪽은 τ_짧은 = pS 니까 (1 − ρ)S ÷ ((1 − ρ)S + A) 에 p 를 곱한 거예요.

이번 판에 남긴 쪽은요?

이번 판 냄새 가운데 짧은 길 쪽 비율을 q 라 하면 A ÷ ((1 − ρ)S + A) 에 q 를 곱한 거고요. 어, 두 무게를 더하면 1이에요. 뒤쪽 무게를 ρ̃(로 틸드)라 하면 p ← (1 − ρ̃)p + ρ̃q, 크로스 엔트로피 방법의 업데이트와 같은 형태예요.

숫자로 확인해 볼게. 씨앗 3의 열한째 판은 냄새 합 55.50, p = 0.8075 에서 시작해서 개미 아홉 마리가 짧은 길로 갔어. 남긴 냄새가 9.5, q = 0.9474 라서 ρ̃ = 0.1598 이고, (1 − ρ̃)p + ρ̃q = 0.8299 야. 냄새로 바로 계산한 것도 0.8299 고.

거봐, 똑같지?

그런데 ρ̃ 가 0.16이면 ρ = 0.1 이랑 다르잖아요. 형태만 같은 거 아니에요?

판이 오래 지나면 냄새 합 S 는 어디쯤에 머물까요?

음, 다음 판의 냄새 합이 (1 − ρ)S + A 니까, 더는 안 바뀌려면 S = (1 − ρ)S + A, 다시 말해 S = A / ρ 예요.

개미가 다 짧은 길로 가면 A = 10 이니까 냄새 합이 100이고, 그럼 ρ̃ = 10 / (90 + 10) = 0.1, ρ 랑 같아. 마흔한째 판을 보니 냄새 합이 94.50 이고 ρ̃ 가 0.1005 야. 냄새 합이 굳고 나면 개미의 냄새 규칙이 ρ = 0.1 인 크로스 엔트로피 방법의 업데이트가 되고, 처음 몇 판만 ρ̃ 가 커서 더 크게 움직이는 거네.

증발을 끈 ρ = 0 이면 ρ̃ 는요?

냄새 합이 판마다 남긴 만큼 쌓이니까… 첫 판 0.76, 열째 판 0.115, 백째 판 0.011, 이백째 판 0.005 예요. 판이 갈수록 작아지는 학습률이네요. 문제 9에서 α = 1 로 고르면 처음 몇 판의 비율에서 굳던 것도 이 때문이었어요.

그래요. 냄새는 다음 답을 뽑는 분포의 파라미터이고, 증발률은 그 분포를 한 판에 얼마나 고칠지 정하는 학습률이에요. 크로스 엔트로피 방법은 확률을 바로 고치고, CMA-ES 는 좋은 점들로 정규분포의 평균과 공분산을 고치고, 자연 진화 전략은 분포의 파라미터를 고치는 일을 그래디언트 한 스텝으로 적어요. 출발이 생물이든 통계든, 뽑는 분포를 두고 좋은 샘플 쪽으로 그 분포를 옮기는 한 집안이에요.

토론 3. 하한으로 잘라 내면 답을 조금 잃는 대신 빨라지는가

「A와 가지치기」 절의 20 × 12 격자에서 남은 비용의 추정값 h 를 0, 맨해튼 거리의 절반, 맨해튼 거리, 실제로 남은 비용 그 자체로 바꿔 가며 A 를 돌린다. 연 칸 수와 찾은 길은 어떻게 바뀌는가?

진흙 연못 격자에서 A* 는 74칸만 열고 길을 찾았어요. 다익스트라 알고리즘은 232칸을 열었고요. 158칸을 안 본 대가로 무엇을 치렀을까요?

빔 탐색처럼 좋아 보이는 후보만 남기고 나머지를 버린 거니까, 가끔은 더 좋은 길을 놓치겠죠. 언어 모델 디코딩에서 빔 폭을 줄이면 빨라지는 대신 가끔 더 좋은 문장을 놓치는 것처럼요. 빨라진 만큼 답을 조금 포기하는 근사라고 봐요.

그 격자에서 A* 가 찾은 길은 몇 분이었죠?

25분이요. 다익스트라도 25분이었고요. 이 격자에서는 운이 좋았던 거 아닐까요?

A* 가 도착 칸을 열고 멈춘 순간, 아직 열지 않은 칸들에는 「이미 온 비용 + 추정값」이 얼마쯤 적혀 있었을까요?

음, 가장 작은 칸부터 열었으니까, 도착 칸을 25로 열 때 남은 칸들은 다 25 이상이었어요.

추정값 h 가 하한이면, 그 「25 이상」은 무슨 뜻이 되죠?

그 칸을 거치는 길은 아무리 싸도 25분은 든다는 뜻이에요. 그러니 버린 칸을 거치는 길은 모두 25분 이상이고요.

아, 그럼 운이 아니었네. 버린 곳에 더 싼 길이 있을 수가 없으니까, 하한으로 자르면 답을 하나도 잃지 않아. 빔 탐색은 버린 후보가 나중에 얼마나 좋아질 수 있는지 하한을 따지지 않고 지금 순위로만 잘라서 놓치는 거고.

그럼 하한은 낮게 잡을수록 안전하니까 좋은 거겠네요. 0으로 두면 아무것도 안 놓치잖아요.

민준 학생이 추정값을 0, 맨해튼 거리의 절반, 맨해튼 거리, 실제로 남은 비용으로 바꿔 돌려 볼래요?

돌려 볼게. 연 칸이 232, 196, 74, 26이고 넷 다 25분이야. 실제로 남은 비용을 쓰면 연 26칸이 찾은 길 위의 칸 26개와 똑같아.

넷 다 맞는데 연 칸은 아홉 배 가까이 차이가 나네. 낮은 하한은 틀리지 않게 해 줄 뿐이고 빠르게 해 주지는 않는구나. 0이면 다익스트라 그대로고.

립시츠 상수로 하한을 그은 1차원 탐색에서 L 을 키웠을 때는 어땠죠?

L 을 두 배, 세 배로 잡으면 잰 횟수가 55에서 105, 163으로 늘었어요. L 이 클수록 하한이 낮아지니까 같은 이야기예요. 실제를 넘지 않는 범위에서 실제에 가까울수록 덜 보고, 넘으면 맨해튼 거리를 두 배로 부풀렸을 때처럼 33분짜리 틀린 답이 나와요.

그래요. 하한으로 자르는 가지치기는 답을 잃지 않아요. 답을 잃는 것은 하한이 아닌 값으로 자를 때고요. 그리고 하한 안에서는 실제에 가까울수록 많이 잘라 내니, 좋은 하한을 찾는 일이 곧 문제에 대해 더 아는 일이에요.

혼동하기 쉬운 점

혼동하기 쉬운 생각	나온 문제	바로잡는 법
잰 그래디언트가 거의 0이면 손실이 가장 낮은 답에 닿았다고 봄	개념 다지기	그 수치로는 더 내려갈 수 없다는 뜻일 뿐이다. 물리 면역이 있으면 전사→마법사 항 0.25가 탐색 공간 어디서나 0.25로 남는다. 손실을 항으로 나눠, 남은 항이 고칠 수 있는 수치에 기대는지 본다
열 판에 3승이면 그 상성이 30%로 약하다고 봄	1	반반인 상성에서도 10판에 3승 이하가 여섯 번에 한 번꼴(0.172)로 나온다. 판 수로 오차 한계부터 잰다. ±2.5%p 로 재려면 1,600판이 든다
체감 승률이 가장 높은 영웅을 내리면 된다고 봄	2	체감 승률은 그 주에 사람들이 고른 비율에 따라 바뀐다. 승률표와 고르는 비율을 갈라 보고, 고치는 동안 목표가 움직이면 두 쪽이 서로를 보고 고치는 놀이로 본다
고칠 수치가 셋이고 맞출 상성이 셋이면 풀린다고 봄	3	명중률 셋을 함께 0.8배 해도 승률표가 거의 그대로라 쓸 수 있는 방향은 둘쯤이다. 고리를 따라 맞힘 수를 곱해, 한 방향의 곱과 거꾸로 곱이 다르면(24 대 48) 수치로는 못 맞춘다
엘로 점수가 비슷한 두 모델은 서로 반반쯤 이긴다고 봄	4	점수 하나는 서로 물고 물리는 성분을 담지 못한다. 고리를 따라 오즈를 곱해 1인지 본다(60% 고리면 3.375)
그때그때 가장 좋아 보이는 것을 고르면 전체도 가장 좋다고 봄	5	1·4·6회권으로 8번 타기에서 큰 것부터 사면 3장, 표로 풀면 2장이다. 남은 문제의 가장 좋은 답(표의 값)을 모두 보고 고른다
칸 위치만으로 표를 세우면 늘 맞는다고 봄	6	남은 시간이 들어온 방향에 달리면 칸 하나에 값 하나로는 모자란다(43분 대 41분). 남은 선택에 필요한 것을 모두 처지에 넣는다(칸 × 들어온 방향, 50칸)
표를 채울 차례가 없으면 동적 계획법을 못 쓴다고 봄	토론 1	아무 처음 값에서 모든 칸을 다시 적기를 값이 굳을 때까지 되풀이한다(네 방향 격자는 9바퀴, 많아야 칸 수 − 1 바퀴). 차례는 한 번 훑고 끝내게 해 줄 뿐이다
단어 오류율은 비율이니 100%를 넘지 않는다고 봄	7	정답 문장의 단어 수로 나누므로 넣기가 많으면 넘는다(정답 7단어 뒤에 「음」 10번이면 143%)
냄새를 강화하기만 하면 언제나 한 길로 몰린다고 봄	9	냄새에 비례해 고르면 다음 판 냄새 비율의 기댓값이 지금 비율과 같아, 처음 몇 판의 우연이 정한 비율에서 굳는다. 한 길로 몰리려면 비례보다 세게 끌려야 한다(냄새를 제곱해서 고르기)
좋은 샘플의 비율을 그대로 쓰는 ρ = 1이 가장 정확하다고 봄	10	샘플 4개짜리 추정은 0이나 1을 쉽게 내고, 0이나 1이 된 자리는 다시 반대 값을 뽑지 못한다(1000번 가운데 80.8%가 틀린 값에 박힘). 옛 확률을 섞어 아직 안 본 가능성을 남긴다
개미 군집은 생물 흉내라 분포를 고치는 방법들과 원리가 다르다고 봄	토론 2	냄새 규칙을 확률로 다시 적으면 크로스 엔트로피 방법의 업데이트와 같은 형태고, 냄새 합이 굳으면 그 무게가 증발률과 같아진다. CMA-ES·자연 진화 전략과 함께 뽑는 분포를 고치는 한 집안이다
실제에 가까운 추정(평균 속도)으로 후보를 버려도 된다고 봄	11	평균은 어떤 후보에서는 실제보다 길게 나와 가장 빠른 집(28분)을 재 보지도 않고 버린다. 버리는 근거는 어디서도 실제를 넘지 않는 하한이어야 한다
탐색이 멈추며 내놓은 답이면 가장 싼 답이라고 봄	12	추정값이 실제를 넘으면 가장 싼 길의 점을 비싸다고 믿고 열지 않은 채 멈춘다(5 대신 6, 격자에서는 25분 대신 33분). 허용 가능한 휴리스틱일 때만 보장된다
하한으로 잘라 내면 답을 조금 잃는다고 봄, 하한은 낮을수록 좋다고 봄	토론 3	하한으로 자르면 답을 잃지 않는다. 하한 안에서는 실제에 가까울수록 덜 연다(추정값 0이면 232칸, 맨해튼 거리 74칸, 실제로 남은 비용 26칸, 모두 25분)
잰 점들 사이의 가장 큰 기울기를 립시츠 상수로 쓰면 된다고 봄	13	두 점 사이 기울기는 가장 가파른 곳을 넘지 못해 늘 작게 나온다(1.10 대 8.28). 함수에 대한 바깥 지식으로 정하거나, DIRECT 처럼 가능한 립시츠 상수를 모두 따진다
노이즈 섞인 검증 손실과 손실이 치솟는 곳의 값도 그대로 하한에 쓴다고 봄	14	노이즈 폭만큼 여유를 두고(버릴 수 있는 범위가 양쪽으로 0.1씩 준다), 발산 근처에서 잰 값으로는 이웃을 버리지 않는다

요약

이 장에서 한 일을 정리해 보자. 값만 잴 수 있는 탐색에서, 문제에 대해 무엇을 더 알면 덜 재고도 답을 찾는지를 물었다.

밸런스 패치에서 명중률처럼 승률이 매끄럽게 따라 변하는 수치는 테스트 플레이로 잰 그래디언트가 손실을 내려 주었지만, 그 대가는 판 수였다. 상성마다 200판으로 재면 패치 한 번에 3,600판이 들었다. 공격력은 맞힘 수가 바뀌는 곳에서만 승률이 뛰는 계단이었고, 물리 면역처럼 규칙이 정한 상성은 탐색 공간 어디에서도 50%에 닿지 않았다. 고칠 수 있는 방향의 수와 맞출 목표의 수, 고리를 따라 곱한 맞힘 수를 먼저 세면 수치로 풀릴 문제인지 미리 알 수 있고, 사람들이 패치를 보고 옮겨 가면 목표 자체가 움직였다. 수치를 돌려 풀리지 않는 문제는 규칙을 바꿔 탐색 공간을 바꾸는 수밖에 없다.

그렇다면 어떤 원리가 0차 최적화를 도와줄 수 있을까? 이 장의 세 탐색은 값 말고 아는 것이 하나씩 달랐고, 그에 따라 세 원리가 나왔다.

분해. 큰 문제의 답이 같은 형태의 작은 문제의 답으로 적히면, 작은 문제의 답을 표에 한 번씩 적어 두고 다시 쓴다(동적 계획법). 5 × 5 격자에서 길 70가지를 다 재는 셈 629번이 표 채우기 40번이 되었고, 20 × 20 격자면 길 약 353억 가지 대신 칸 400개를 채운다. 벨먼이 최적성의 원리라 부른 성질, 남은 길이 지금 처지에만 달려 있다는 성질이 있어야 표가 맞고, 모자라면 들어온 방향처럼 필요한 것을 처지에 넣어 표를 늘린다.
기억. 좋은 답들이 서로 닮았으면, 답을 버리고도 다음 답을 뽑는 분포를 남겨 둔다(개미 군집 최적화). 집 50곳을 도는 좋은 경로 둘은 길의 70.2%를 함께 썼고, 길 1225개마다 냄새 숫자 하나면 그 닮음을 담는다. 증발률은 그 분포를 한 판에 얼마나 고칠지 정하는 학습률이라, 증발이 없으면 먼저 쌓인 긴 길에서 거의 빠져나오지 못했다(500번 가운데 487번). 냄새 규칙을 확률로 다시 적으면 크로스 엔트로피 방법의 업데이트와 같은 형태여서, 진화 알고리즘의 CMA-ES 와 자연 진화 전략도 같은 집안이다.
하한. 남은 비용이 적어도 얼마인지 알면, 하한이 이미 찾은 답보다 높은 곳은 재지 않고 잘라 낸다(A와 가지치기). 맨해튼 거리라는 허용 가능한 휴리스틱으로 A 는 232칸 대신 74칸을 열고 같은 25분 길을 찾았고, 두 배로 부풀린 추정은 43칸만 열었지만 33분짜리 틀린 답을 냈다. 0차 최적화에서는 립시츠 상수가 그 하한을 주어, 가장 낮은 값을 0.01 안으로 보증하는 데 고른 격자 1,661점 대신 55번만 쟀다.

세 원리가 아끼는 것은 같다. 분해는 같은 뒷부분을 두 번 계산하지 않게 하고, 기억은 이미 잰 답에서 배운 것을 다음 판으로 넘기고, 하한은 재 볼 필요가 없는 곳을 재기 전에 알려 준다. 어느 원리를 쓸 수 있는지는 문제의 구조에 달려 있어서, 구조를 모르면 밸런스 패치의 운영사처럼 판 수를 늘려 노이즈를 줄이는 수밖에 없다.

정리 연습문제

물음. 「세 영웅」에서 마법사가 물리 면역을 얻은 뒤 명중률 셋을 고쳤더니, 잰 그래디언트가 거의 0인 자리에서 손실이 0.25로 멈췄다. 그래디언트가 0에 가깝다는 것은 무엇을 뜻하는가?

[ ] 손실이 가장 낮은 답에 닿았으니 더 할 일이 없다 〔틀림: 그래디언트가 0이라는 것은 명중률로는 더 내려갈 수 없다는 뜻일 뿐이다. 0.25는 전사→마법사 항 하나에서 나온다.〕
[ ] 테스트 플레이 판 수를 늘려 그래디언트를 더 잘 재면 0까지 내려간다 〔틀림: 판 수는 그래디언트의 노이즈를 줄일 뿐이다. 전사가 마법사에게 0%인 항은 명중률에 기대지 않는다.〕
[x] 남은 항이 탐색 공간 어디에서도 줄지 않으니, 규칙을 바꿔 탐색 공간을 바꿔야 한다 〔맞음: 면역을 「물리 피해 절반」으로 바꾸자 그 상성이 다시 명중률에 따라 움직였다. 다만 새 규칙은 새 고리를 만들 수 있다.〕

물음. 오른쪽·아래로만 가는 5 × 5 격자에 「방향을 바꿀 때마다 3분」을 더했다. 칸마다 「여기서 도착까지 가장 짧은 시간」 하나를 적는 표는 어떻게 되는가?

[ ] 그대로 맞는다. 이웃을 비교할 때 회전 비용만 더하면 된다 〔틀림: 그렇게 채우면 출발 칸에 43분이 적히지만, 70가지를 다 재면 41분 길이 있다.〕
[x] 남은 시간이 그 칸에 어느 방향으로 들어왔는지에 달려, 칸마다 들어온 방향별로 값을 둘씩 적어야 한다 〔맞음: 처지에 방향을 넣으면 표는 50칸이고 출발 칸에 41분이 나온다.〕
[ ] 동적 계획법을 쓸 수 없으니 길을 다 재야 한다 〔틀림: 처지를 늘린 표 50칸으로 풀린다. 20 × 20 격자면 길은 약 353억 가지인데 값은 800개다.〕

물음. 짧은 길·긴 길 장난감에서 처음 30판은 긴 길만 열어 두었다가 짧은 길을 연다. 증발이 없으면(ρ = 0) 어떻게 되는가?

[ ] 짧은 길로 간 개미가 먼저 돌아오니 결국 짧은 길로 옮겨 간다 〔틀림: 30판 동안 쌓인 긴 길 냄새 151이 줄지 않아, 500번 가운데 487번이 2000판 안에 짧은 길을 고를 확률 0.5에 닿지 못했다.〕
[x] 쌓인 긴 길 냄새를 잊지 못해 대부분 긴 길에 갇힌다. 증발은 옛 기억을 얼마나 빨리 잊을지 정한다 〔맞음: ρ = 0.1이면 중앙값 47판 만에 0.5를 넘었다. 증발률은 분포를 한 판에 얼마나 고칠지 정하는 학습률 구실을 한다.〕
[ ] 증발을 켜기만 하면 언제나 짧은 길로 옮겨 간다 〔틀림: ρ = 0.1에서도 500번 가운데 102번은 짧은 길 냄새가 같이 증발해 사라졌다. 냄새에 아래 한계를 두어야 모두 옮겨 갔다.〕

물음. 진흙 연못 격자에서 A* 의 추정값을 맨해튼 거리의 두 배로 부풀리면 어떻게 되는가?

[ ] 연 칸이 줄면서 같은 25분 길을 찾는다 〔틀림: 연 칸은 74칸에서 43칸으로 줄지만, 찾은 길은 연못을 건너는 33분이다.〕
[ ] 추정값을 바꾸면 다익스트라 알고리즘과 같아진다 〔틀림: 다익스트라는 추정값을 0으로 둔 경우다. 232칸을 열고 25분 길을 찾는다.〕
[x] 추정값이 실제로 남은 비용을 넘는 칸이 생겨, 가장 싼 길의 칸을 비싸다고 믿고 열지 않은 채 멈춘다 〔맞음: 출발 칸에서 부풀린 추정은 34분인데 실제로 남은 비용은 25분이다. 하한일 때만 잘라 낸 곳에 더 싼 길이 없다고 말할 수 있다.〕

물음. 값만 돌려주는 함수에서 립시츠 상수로 하한을 그어 가장 낮은 값을 찾는다. 립시츠 상수를 정하는 방법으로 옳은 것은?

[ ] 잰 점들 사이의 가장 큰 기울기를 쓰면 안전하다 〔틀림: 두 점 사이 기울기는 가장 가파른 곳을 넘지 못해 늘 작게 나온다. 아홉 점으로 1.10을 얻었지만 실제는 8.28이라, 좁은 골짜기를 버리고 틀린 보증을 냈다.〕
[x] 실제보다 크게 잡으면 보증은 맞지만 잴 곳이 늘고, 작게 잡으면 보증이 틀릴 수 있다 〔맞음: 8.3을 두 배, 세 배로 잡으면 잰 횟수가 55에서 105, 163으로 늘었다. 하한은 실제를 넘지 않는 범위에서 높을수록 많이 잘라 낸다.〕
[ ] 립시츠 상수는 클수록 하한이 높아져 더 많이 잘라 낸다 〔틀림: 거꾸로다. 상수가 클수록 하한을 긋는 두 직선이 가팔라져 하한이 낮아지고, 잘라 내는 구간이 준다.〕

막힌 곳

이 장의 세 원리는 문제의 구조를 알 때만 쓸 수 있었다. 길찾기는 길 하나의 시간이 구간 시간의 합이라 표로 쪼개졌고, 외판원 경로는 좋은 경로들이 길을 함께 써서 냄새로 기억할 만했고, 직선거리와 립시츠 상수는 남은 비용의 하한을 주었다. 그래도 하한 탐색은 1차원 구간 하나에서 55번을 쟀고, 파라미터가 늘면 하한으로 잘라 내기 전에 재 봐야 할 곳이 차원마다 곱으로 불어난다. 신경망의 파라미터는 수백만, 수십억 개다.

그런데 신경망의 손실은 승률표처럼 판을 돌려야 읽히는 값이 아니다. 곱하고 더하고 비선형 함수를 씌우는 계산을 층마다 거친 결과이고, 그 계산 과정은 우리가 다 적어 둔 것이다. 길찾기의 표가 같은 뒷부분을 한 번만 계산해 다시 썼듯이, 계산 과정을 다 안다면 파라미터 하나하나를 흔들어 볼 필요 없이 그래디언트 전체를 함수 값 한두 번 계산하는 품으로 얻을 수는 없을까?