PlanB의 백엔드 엔지니어링

최근에 Markov Chain이라는 것을 듣게 됐다. 이게 사실은 확률론의 '확률 과정'이라는 곳에서 나오는 개념인데, 필자는 수학 찐따라 기본적으로 위키피디아에서 설명하는 정의는 이해하지 못한다.

첫 문장부터 확률 공간, 가측 집합, 가측 공간같은 소리를 하는데다, markov chain에 대해 잘 정리된 것 같은 글들은 수학적 배경이 너무 많이 필요해서 여기에 좀 정리해보려고 한다.

Markov Chain

Markov Chain은, Markov Property를 지닌 이산 시간 확률 과정(Discrete-time Stochastic Process)을 의미한다(라고 설명하고 있다). 무작정 정리하기 전에, 그냥 Markov Chain의 예를 직접 보도록 하자.

Markov Chain의 예와 이의 해석

위 그림의 s, c, r을 state(상태)라고 부르고, 각 state 사이에 이어진 유향 선분(화살표)에 대해 할당된 가중치들은 해당 상태 전이가 이루어질 수 있는 확률을 의미한다(확률론에서 항상 그러는지는 모르겠으나, Markov Chain에서는 확률을 표현할 때 0~100%에 대한 구간을 [0, 1]로 두어 대응시키고 있다). 위 그림의 경우, s에서 c가 될 확률이 0.3(30%)이고, c에서 r이 될 확률이 0.5(50%)같은 식으로 해석하면 된다. 조건부 확률을 떠올려서 P(s|c)=0.3, P(c|r)=0.5같이 봐도 되고. 그렇다면 위 markov chain을 기준으로 했을 때, 오늘 날씨가 맑음(s)이고, 내일 날씨가 비(r)이며 모레 날씨가 맑음(s)이 될 확률은 P(s|r) * P(r|s) = 0.1 * 0.4 = 0.04가 될 것이다.

다시 정리하면

Markov Chain은 그냥 어떤 state를 정의하고, 그 state들 각각에 대한 전이 확률을 정의해둔 채 이거 갖고 짝짝꿍 하는 거다. 다시 정리하면, 위처럼 sunny, cloudy, rainy같은 state(상태)가 존재하고, 각 state를 넘나드는 확률값이 존재해서 이게 chain처럼 구성되어 있고, 상태 전이 확률이 항상 현재 state에만 의존한다면(예를 들어 s → c라는 전이의 확률이 r에 의존하지 않는다면), 이를 Markov Chain이라고 부른다. 여기서 '상태 전이 확률이 항상 현재 state에만 의존하는 것'이 Markov Property를 나타낸다.

근데 뭐 sunny, cloudy, rainy 이런 것만 봐서 이게 도대체 얼마나 유의미한 것을 도출해낼 수 있을까 싶을텐데, real world에선 이런 곳에 쓰이고 있다.

• Markov Chain에서, chain이 커지면(상태 전이 횟수가 늘어나면) 특정 state에 전이될 확률이 고정된 값으로 수렴한다고 한다. 웹 전체를 markov chain으로 두었을 때, '서핑이 오랜 시간 이루어진다'고 가정하면 특정 웹 페이지 X에 도달하는 것은 고정 확률이라고 볼 수 있다. Google의 Page Rank 알고리즘이 markov chain 이론을 기반으로 만들어졌다고 한다.
• 안드로이드의 Google 키보드에는 'Google 키보드를 개선하기 위해 Google 어플리케이션에 입력하는 내용 공유'라는 옵션이 있다. 이게 켜져 있으면, 우리가 타이핑하는 단어들이 Google로 보내져서 Markov Chain에 반영되고, 이를 통해 Google은 단어 예측(Typing Word Prediction)을 수행한다.
• 음성 인식, 추천 엔진 등 상태 전이 확률을 통해 뭔가 예측할 필요가 있는 곳들에서 Markov Chain을 자주 사용하고 있다고 한다.

Currying은 n개의 인자를 가진 함수를 단일 인자를 가진 n개의 함수 체인으로 만드는 것이다. f(x, y, z)를 f(x), g(y), h(z)로 분리하는 것이다. 일반적으로 currying은 함수를 반환하는 함수 형태로 구현한다. 따라서 higher-order function이 직/간접적으로 가능한 언어가 currying을 구현하기 편하다. Currying은 특히 Haskell 입문서에서 자주 다뤄진다.

두 예제에서, 위 함수는 두 개의 인자를 한 번에 받아 그 합을 반환하고, 아래 함수는 한 개의 인자를 받아, 남은 인자 하나가 채워지면 합을 반환하는 새로운 함수를 반환한다. 따라서 두 함수는 각각 다르게 호출하게 된다.(sum(1, 3), sum(1)(3))

만약 인자 a에 대한 연산 비용이 비싸고, 인자 b에 채울 값이 지금 당장 없다면, 인자 b에 채울 값이 생길 때까지 시간이 남으므로 위의 커링은 유용할 수 있다. 그러나 위의 경우 인자 a에 대해 연산 비용이 없으므로(별도의 로직을 적용하지 않고 단지 가지고만 있을 뿐이므로), 연산 비용의 분산 면에서는 큰 의미가 없다.

따라서 currying은 함수의 특정 인자에 대해 연산 비용이 비싼 경우, 그 함수에 인자를 나누어 전달하여 함수의 로직을 점차적으로 수행할 때에 유용하다. 다만 내 경우에는 함수 자체가 계산 비용이 비싼 경우는 있었어도, 함수의 특정 인자에 한정되어 계산 비용이 비싼 경우는 없었기에 이런 상황이 그리 많지 않았고 따라서 메모이제이션으로 충분히 처리할 수 있는 경우가 더 많았다.

이에 더해 인자 a, b 간의 양방향 의존성이 있다면 currying을 적용하기 더 어렵다. 단지 인자 a가 인자 b에 단방향 의존한다면, 인자 b를 먼저 받아 로직을 일부 처리하고 인자 a가 채워질 때 클로저로 인자 b에 접근해 나머지 로직을 처리하면 된다. 그러나 애초에 두 인자가 같이 필요한 로직 뿐이라면 currying의 중간에 인자 여러 개를 받는 함수를 끼워두거나 애초에 a와 b 인자 모두가 채워졌을 때 로직을 수행하는 등의 방식으로 해결한다. 내 경우에는, currying을 Python의 ORM 라이브러리인 SQLAlchemy에서 read db와 write db에 대한 connection을 관리하기 위한 context manager 함수를 정의하는 데에 사용한 적이 있다.

위의 경우 read_session_factory와 write_session_factory는 session 함수의 engine_name에 각각 'read'와 'write'를 전달하여 반환받은 새로운 함수다. 그러나 engine_name 인자는 연산의 양에 큰 영향을 끼치지 않으므로, 그냥 함수로 분리해 내더라도 성능 상에 큰 문제가 생기지 않는다.

프론트엔드 API에서 자주 쓰이기도 하고, Go 내부 라이브러리에도 커링된 함수가 몇 가지 있다고 하지만 사실 이런 커링 기법을 완전히 적용할만한 경우를 찾지는 못했다. 하지만 이런 방식의 함수 작성은 함수형 프로그래밍과 클로저 등에 대한 개념을 강화하는 데에 도움을 주는 것은 맞는 것 같다.

Higher-order function은 Kotlin을 배우면서 마주친 개념이었다. 사실 higher-order function 자체는 이전에 내가 배웠던 다른 언어에서도 사용되던 개념이었는데, Kotlin 이전까지는 이에 대해 따로 설명을 하던 튜토리얼이 없었어서 Kotlin에서 처음으로 알게 되었다. Higher-order function은 고차함수, 또는 고계함수로 번역하며, 아래 두가지 중 하나 이상을 만족하는 함수를 의미한다.

• 함수를 파라미터로 전달받는 함수
• 함수를 리턴하는 함수

정의 자체가 그리 어렵지 않다. 그리고 함수가 값으로서 평가되기만 하면 사용할 수 있는 개념이라 일급 객체로서의 함수가 지원되는 언어는 higher-order function이 가능하다. 따라서 웬만한 프로그래밍 언어들에서 어렵지 않게 마주칠 수 있다. 아래는 Python의 예다.

위의 sum 함수는 덧셈 연산의 피연산자 a, b와 결과를 전달받을 함수인 callback을 인자로 받는다. 함수를 파라미터로 전달받으므로, 위 함수는 higher-order function이다.

위는 파이썬 데코레이터의 기본형이다. timeit 함수는 인자로 함수를 받고, wrapper 함수를 반환한다. 두 조건을 모두 만족하므로, 당연히 이도 higher-order function이다.

JavaScript도 함수가 값이기 때문에, higher-order function을 표현할 수 있다.