확률 체계를 유도하며 정보의 상태에 확률을 부여하는 것에 대해 언급하였다. 이와 관련하여 상태 공간state space에 대해 생각해보자.
현상을 표현하는데 충분한 모든 정보를 모은 것을 상태state라고 부른다. 가령 뉴턴 역학에서 어떤 계에, 외부에서 힘이 가해지지 않는다면, 모든 입자의 운동을 기술하는 데에 필요한 정보는 입자들의 위치와 모멘텀 정보이다. 모든 입자의 위치 및 모멘텀 정보가 하나의 상태에 대응되며 상태 공간은 계가 가질 수 있는 모든 상태의 집합을 일컫는다.
하나의 동전을 던져서 나올 수 있는 면은 앞면과 뒷면 총 두 가지이다. 어떤 면이 나왔는지로 어떤 계의 상태가 결정된다고 하면 해당 계는 총 두 개의 상태 중 하나를 상태로 가지게 된다. 즉, 이 계의 상태 공간은, 앞면인 상태와 뒷면인 상태, 두 개 상태로 구성되었다고 할 수 있다.
상태 공간이 유한할 필요는 없다. 가령 어떤 계의 온도가 해당 계의 상태를 결정한다고 하자. 우리는 보통 온도의 상한이 없다고 생각하기 때문에, 그리고 온도가 실수로 표현된다고 생각하기 때문에, 해당 계의 상태 공간은 무한히 많은 상태를 갖게 된다.
상태 공간을 바라보는 관점과 이게 추론과 어떤 부분에서 닿아있는지 느끼기 위해 예시를 몇 가지 들어보도록 하겠다.
어떤 계의 상태 공간에 총 다섯 개의 상태가 존재한다고 생각해보자. 이제 각각의 상태에 이름을 부여한다.
각각을 줄여서 '1a', 'a2', '8f', '9c', '8e'라고 부르자.
이 정보만 주어진 상황에서 우리가 상태와 상태 사이의 관계에 관해 이야기할 수 있는 것은 별로 없다. '1a'와 'a2'가 '1a'와 '8f'보다 서로 더 비슷한가? 상태 공간이 그저 상태들의 집합에 불과하다면 이로부터 어떤 의미 있는 직관을 추출하기는 쉽지 않다.
상태 공간이 그저 가능한 모든 상태 집합을 지칭한다면 굳이 공간이라는 표현을 사용하지는 않았을 것이다. 두 상태 사이의 관계를 생각해보자.
Traveling salesman problem(TSP)을 생각해보자. 열 개 도시를 모두 방문하고 원래의 위치로 돌아오는 최단 경로를 찾고 싶다. 각 도시에 순서대로 1부터 10까지 번호를 부여하면 도시의 방문 순서는 열 개 숫자의 순서쌍으로 표현할 수 있다. 염두에 두어야 하는 사실은 도시에 부여한 번호에 특별한 의미가 있지 않다는 것이다. 1번 도시와 2번 도시가 가까워야 한다든지 등의 제약이 전혀 없다. 이렇게 표현된 하나의 순회 방법을 하나의 해solution라고 부르자. 열 개의 도시를 가정하면 총 가능한 순회의 개수는 $(n-1)!/2 = 181,440$ 개이다.
서로 다른 두 해 사이의 관계를 상상해볼 수 있다. 모든 방문 순서가 같고 두 도시만 서로 바뀐 경우를 생각해보자.
이런 식으로 한 쌍의 도시만 바뀐 관계에 있는 해는 서로 "이웃"하다고 생각해보자. 그렇다면 각각의 해를 정점으로 하고 서로 두 개의 도시 순서를 뒤바꾼 관계에 있는 해들끼리 간선으로 연결된 그래프를 상상할 수 있다.
상태 공간이 그래프로 표현된 것이다. 이제 두 상태의 관계에 대해 논할 수 있다. 가령 단 한 번만 간선을 통과해서 도달할 수 있는 해는 최소 두 번 간선을 통과해야만 하는 해보다 더 가깝다고 이야기할 수 있다.
상태 공간의 구조가 주어지면 이를 활용하여 상태 간의 관계에 대해 논할 수 있다.
전통적인 물리학의 관점에서 닫힌 계에 주어진 입자의 위치와 모멘텀을 알면 미래를 예측하는 것이 가능하므로 주어진 계의 모든 입자의 위치와 모멘텀의 정보를 하나의 상태라고 부를 수 있다.
3차원 공간에 총 $n$ 개의 입자가 있다면 하나의 상태는 $6n$ 개의 숫자로 표현 가능하다(차원 별로 위치를 표현하기 위해 하나씩, 모멘텀을 표현하기 위해 하나씩).
이렇게 표현된 하나의 상태는 $6n$-차원 공간 위의 하나의 점으로 생각할 수 있다. 이는 어떤 의미로 일반적인 그래프 구조보다 훨씬 강력한 가정이다. 가령 이렇게 되면 각 차원이 실수값을 갖기 때문에 두 상태에 partial order를 생각해 볼 수 있다.
그래프의 예에서와 마찬가지로 이렇게 표현된 상태 공간의 모양에 대해 논할 때 공간의 구조를 활용할 수 있다.
각각의 상태마다 값이 주어졌다고 상상해보자.
위의 예에서는 전수조사가 가능하므로 가장 큰 값을 가진 상태가 1a라는 것을 쉽게 확인할 수 있다. 하지만 만약 상태의 개수가 아주 많다면 이는 어려운 문제가 된다. 만약 딱히 구조가 주어지지 않은 상태 공간에 상태가 $100^{100}$개 있다면 그중 가장 큰 값을 찾는 것은 사실상 불가능할 것이다. 특별한 구조가 없다는 가정이므로 $100^{100}$개의 모든 상태를 확인해봐야 가장 큰 값을 찾을 수 있기 때문이다. 하지만 상태 공간이 이루는 구조를 알고 있다면 이를 활용해서 현실적인 시간에 답을 찾을 수 있을지도 모른다. 가령 특정 상태에서 값이 더 큰 이웃을 따라가면 무조건 전체 상태 공간에서 가장 큰 값에 도달하는 구조를 상태 공간이 띠고 있다면 이를 활용해서 그리디하게 이웃을 따라가면서 전역 최적해에 도달할 수 있다.
세상에 존재하는 모든 웹페이지를 각각 하나의 상태로 생각하자. 상태에 어떤 구조가 없을 때 임의의 페이지를 고를 확률을 $\frac{1}{n}$로 생각할 수 있다. 하지만 랜덤한 페이지에서 출발해서 랜덤하게 링크를 따라다니는 것을 상상해보자. 이 링크에 의해 상태 공간의 구조가 정의된다. 이제 무한히 링크를 클릭하며 상태 공간을 탐색하는 것을 상상해보자. 위의 과정을 거친다면 웹을 돌아다니는 에이전트가 특정 페이지에 도달할 확률은 $\frac{1}{n}$이 아닌 어떤 값을 가질 것이다. 이런 식으로 상태 공간의 각각의 상태에 확률을 부여하는 것도 가능하다.
의자를 상상해보자. 의자의 종류는 아주 많다. 등받이가 있는 의자, 바퀴가 달린 의자, 나무 밑동 같이 생긴 의자 등. 조금 더 가보면 의자인지 아닌지 모호한 것도 있다. 가령 빈백은 의자인가? 혹은 요가볼 위에 앉으면 이를 의자라 부를 수 있는가? 건물만큼 커다란 의자 모양의 구조체는 어떠한가?
우리는 직관적으로 물건/개념을 질적으로 비교한다. 이런 비교는 물건이 지닌 속성을 바탕으로 이루어진다. 의자의 예로 생각해보면 사람이 앉을 수 있는가? 크기는 어떠한가? 등등이 있을 것이다. 현실에서의 상태 공간은 물건/개념에 붙어있는 설명을 위치로 변환하여 만들어진 공간이라고 생각할 수 있다. 그렇다면 위에서와 마찬가지로 이 공간에 부여된 구조를 바탕으로 공간을 탐색하는 것이 가능할 것이다.
어떤 물건의 위치, 속도, 온도, 색깔, 촉감 등 해당 물건을 설명할 수 있는 모든 속성을 각각 차원으로 분리해서 $n$-차원 공간을 구성할 수 있다. 해당 속성의 성질에 따라 각 차원의 축은 실수축일 수도 있고 예/아니오의 선택지만 있을 수도 있다. 속성이 많다면 $n$이 매우 커질 수도 있다.
차원이 늘어나면 아주 빠르게 가능한 상태의 개수도 늘어난다. 가령 가로, 세로 각각 30 픽셀의 이미지를 생각해보자. 이는 현대적인 기준에서 별로 큰 이미지가 아니다. 하지만 각 픽셀이 256개의 값을 가질 수 있음을 생각해보면 임의의 이미지가 차지할 수 있는 상태의 개수는 $256^{30 \times 30}$으로 2,000 자리가 넘는 숫자가 나온다.
앞서 예로 들었던 TSP를 생각해보면 백 개의 도시만 순회하고자 하여도 대략 $10^{155}$ 정도의 상태를 갖는다.
Topology/geometry가 정의되면 이를 활용하여 더 효율적인 탐색이 가능하다.
앞서 살펴본 것과 같이 공간은 이산적일 수도 있고 연속적일 수도 있다. 연속적인 공간은 특히 미분 가능한 목적함수가 주어졌다면 gradient 정보를 바탕으로 효율적인 탐색이 가능하다. 반면 이산적인 공간은 미분 가능하지 않으므로 gradient 정보가 없다. 그러므로 이산적인 공간의 탐색은 어떤 방식으로 neighbor를 정의하느냐에 달려있다.
공간이 어떤 모양으로 생겼는지 사실 우리가 미리 알 방법은 없다. 그러므로 때문에 임의의 공간에 대해 잘 동작하는 탐색/학습 알고리즘은 존재하지 않는다. 이를 수학적으로 엄밀하게 서술한 것이 no free lunch theorem이다. 공간적인 관점에서 왜 inductive bias가 필요한지도 자명하다. 공간의 구조에 대한 가정이 없이는 일반화가 불가능하기 때문이다. 현대의 기계학습은 어떤 방식으로든 공간상에서 가까이 있는 것들은 서로 비슷하고 그사이가 어느 정도는 부드럽다는 가정을 담고 있다.
우리가 조합 최적화 문제를 풀면서 좋은 local search 알고리즘을 사용해야 한다고 하는 것은 결국 좋은 local search 알고리즘이라 불리는 것들이 공간의 모양을 탐색하기 쉽게 만들기 때문이다. $n$-차원 벡터 공간에 현실의 개념과 물건을 표현할 때에도, 이 공간을 나이브하게 바라보면 개념과 물건이 복잡하게 꼬여있는 것처럼 보이더라도 사실은 낮은 차원의 manifold가 존재하고, 이를 찾고자 하는 방식으로 접근한다.
이에 접근하는 한 가지 방법은 개념/물건을 설명하는 내용, 즉 피쳐를 늘리는 것이다. Feature expansion을 자동으로 하는 한 가지 방법으로 커널 기반의 학습이 있고, 뉴럴넷도 이런 feature expansion 기법의 하나로 바라볼 수도 있다.
흔히 우리가 추론한다고 하는 것은 데이터를 설명하는 어떤 모델을 찾는 것을 뜻한다. 이때 각각의 데이터는 이를 구성하는 다양한 속성으로 이루어져 있다. 가령 $30 \times 30$ 픽셀의 개와 고양이의 이미지가 주어지고 이를 개인지 고양이인지 판단하는 문제를 푼다고 해보자. 모든 상상할 수 있는 개의 이미지가 $256^{30 \times 30}$ 공간의 일부 영역에 위치할 것이며 마찬가지로 고양이의 이미지도 이 공간의 일부 영역을 덮을 것이다. 그렇다면 개와 고양이를 분류한다는 것은 이렇게 만들어진 상태 공간을 두 개의 영역으로 나누는 것을 의미한다. 이처럼 데이터가 만드는 상태 공간을 데이터 공간data space이라 부르기로 하자.
모델은 주어진 데이터를 통해 데이터 공간을 어떻게 나누면 좋을지 결정하는 패러미터로 구성되어 있다. 이런 가능한 모델의 공간을 모델 공간model space이라 부르기로 하자.
학습을 통해 좋은 모델을 찾는다는 것은 모델의 공간을 탐색하여 데이터 공간을 잘 분류, 설명하는 패러미터를 찾는 것을 의미한다.
The strange attractor lives in phase space, one of the most powerful inventions of modern science. Phase space gives a way of turning numbers into pictures, abstracting every bit of essential information from a system of moving parts, mechanical or fluid, and making a flexible road map to all its possibilities.
특정 패러미터로 표현되는 하나의 모델은 모델 공간의 한 점인 셈이다.
In phase space the complete state of knowledge about a dynamical system at a single instant in time collapses to a point. That point is the dynamical system--at that instant. At the next instant, though, the system will have changed, ever so slightly, and so the point moves. The history of the system time can be charted by the moving point, tracing its orbit through phase space with the passage of time.
모델을 구성하는 패러미터를 조금 바꾸면 해당 모델은 모델 공간에서 아주 약간 달라진 위치의 새로운 한 점으로 표현될 것이다.
이처럼 물건/개념을 공간의 점으로 사상시키고 이를 다루는 것을 상상하기 때문에 공간을 다루는 아이디어가 중요하게 활용된다. 선형대수학이 기계 학습에서 다방면으로 활용되는 이유 중 하나이다.
David D. Nolte의 The tangled tale of phase space에서 여러 개의 변수를 각각 축으로 삼는 다차원 공간을 상상하는 기법의 역사를 살펴볼 수 있다. Configuration space, parameter space, phase space, problem space, state space 등 다양한 용어가 비슷한 아이디어를 지칭하는 데 사용된다. 문맥에 따라 정확한 의미는 다를 수 있으니 염두에 두어야 한다.
위의 따옴글은 James Gleick의 Chaos: Making a New Science에서 가져온 글이다.
선형대수학은 MIT OpenCourseWare에 공개된 Gilbert Strang의 Linear Algebra 강의를 추천한다.