[c++] 빠른 log sigmoid 계산

sigmoid 함수는 연속이고 미분가능하면서 비선형이라는 특징 덕분에 여러 기계 학습 및 신경망에 두루 쓰이는 함수이죠. 최근에 word2vec을 확장한 모형을 공부하면서 목적함수에 log sigmoid를 잔뜩 사용하는 코드를 구현한 적이 있었는데, log sigmoid 계산 비용이 꽤나 컸기에 전반적인 속도 향상에 어려움이 있었습니다. 그래서 Look Up Table을 이용해 최적화를 실시했었는데 그 결과를 포스팅으로 공유하고자 합니다.

먼저 log sigmoid 함수는 다음과 같이 정의됩니다. 

이름처럼 sigmoid 함수에 log를 취한 형태이구요, 그 그래프 모양은 다음과 같습니다.

전 범위에서 음수 값을 가지며, x > 0일는 그 값이 0에 극도로 가까워집니다. 이 함수를 계산하기 위해서는 exp 연산 한 번과 log 연산 한 번을 수행해야 하는데, 딥러닝의 특성상 수많은 가중치들에 대해 log sigmoid를 계산하게 되므로 그 부하가 보통이 아닙니다. 따라서 최적화가 필요한 부분이라고 할 수 있겠습니다.

빠른 계산을 위해서 log sigmoid의 특성을 살펴보도록 합시다. 먼저 x<0인 부분을 살펴봅시다. t = -x라고 하면

가 되는데, t가 커질수록 exp(t)의 값은 말 그대로 지수적으로 커집니다. 따라서 충분히 큰 t에 대해

라고 할 수 있으므로

,

x가 충분히 작은 값일때 log sigmoid의 값은 x로 근사할 수 있습니다. 그러먼 이 때 근사값과 참값의 차이는 어느 정도 될까요?

여기서 log sigmoid 함수의 재미난 특성이 드러납니다. s(x)에서 x를 빼면 그 값이 s(-x)와 일치하게 됩니다. 다르게 말하면 s(x)를 x로 근사할 때 그 오차는 s(-x)와 같다는 것이고, 따라서 우리는 x>=0인 부분의 s(x)값을 알면 전 범위의 x값에 대해서 s(x)를 구할 수 있습니다.

그런데 x가 충분히 크다면 s(x)는 0과 거의 같습니다. 그렇기에 우리는 적당히 큰 수 n에 대해 0 <= x < n 범위의 s(x)값만 안다면 사실상 거의 모든 범위의 s(x)를 빠르게 계산할 수 있습니다.

x	s(x)
0	-0.6931
10	-4.539E-5
20	-2.061E-9
30	-9.357E-14
40	-4.248E-18

몇 개의 x값에 대한 log sigmoid 값은 위와 같습니다. 보다시피 x가 30을 넘어가면 사실상 0이라고 봐도 될 정도입니다. 그러면 적당히 n = 32로 정하고 0 <= x < 32인 x에 대해 s(x)의 값을 미리 계산하여 테이블에 넣어두고 사용하면 되겠네요.

다음은 LUT을 생성하는 c++ 코드입니다.

#include <array> #include <cmath> /* _Func : LUT를 생성할 함수 N : LUT 의 크기 S : 분할 개수 */ template<class _Func, size_t N, size_t S> class SimpleLUT { protected: std::array<double, N> points; static constexpr double P = 1. / S; SimpleLUT() { _Func fun; for (size_t i = 0; i < N; i++) { points[i] = fun(i * P); } } double _get(double x) const { size_t idx = (size_t)(x * S); if (idx >= N) return _Func{}.forLarge(x); return points[idx]; } public: static const SimpleLUT& getInst() { static SimpleLUT lg; return lg; } static double get(double x) { return getInst()._get(x); } }; /* LUT 계산에 사용할 함수 */ struct F_logsigmoid { double operator()(double x) { return -log(1 + exp(-x)); } double forLarge(double x) { return -0.f; } // 충분히 큰 x에 대해선 -0을 돌려줌 }; /* LUT를 사용해 빠르게 logsigmoid를 계산 [0, 32) 범위를 1/128 단위로 나누어 LUT를 계산하고, 이를 조회하여 logsigmoid의 근사값을 반환 */ inline double logsigmoid(double x) { if (x >= 0) return SimpleLUT<F_logsigmoid, 32 * 128, 128>::get(x); return SimpleLUT<F_logsigmoid, 32 * 128, 128>::get(-x) + x; }

이 log sigmoid 근사 함수의 평균 오차를 계산해보면 다음과 같습니다.

상대 오차 = |(근사값 - 참값) / 참값|

x범위	평균 상대 오차 (%)
-32~-16	0%
-16~-8	0.0000018%
-8~-4	0.00036%
-4~-2	0.0079%
-2~0	0.102%
0~2	0.332%
2~4	0.381%
4~8	0.391%
8~16	0.443%
16~32	1.539%

x가 커질수록 상대 오차가 점점 커지는 것을 확인할 수 있습니다. 사실 x가 음수인 경우 거의 오차가 없다고 봐도 될 정도인 반면, x가 양수일수록 상대 오차가 커지고 있습니다. 그런데 이는 상대오차의 특성도 고려해야합니다. 상대오차는 참값과 근사값의 차이가 참값 대비 얼마나 큰지를 보는 것이기 때문에 참값이 작을수록 오차가 크게 계산됩니다. 16~32 범위의 평균 오차가 1%가 나온 이유는 사실, 이 범위에서 참값과 오차값의 차이가 1e-11 이하 임에도 참값이 사실상 0이다보니 상대 오차가 크게 계산된 것이지요. 따라서 실제 사용에는 전혀 지장이 없다고 볼 수 있겠습니다.

그럼 속도 차이는 어느 정도 날까요? 기존의 log 및 exp 연산을 이용한 logsigmoid 구현과 LUT를 이용한 logsigmoid 구현을 각각 5억번 호출하여 그 실행시간 총합을 비교하여 보았습니다.

log, exp 사용(ms)	LUT 사용(ms)	속도 향상
21934.1	8359.91	+162.4(%)

거의 2~3배 빨라졌다고 볼 수 있겠습니다. 실제로 제 word2vec 구현에 적용해본 결과 evaluation 시간 향상은 약 1.5배 정도 있었구요. 룩업테이블로 32*128크기의 double 배열만 사용하므로, 4096 * 8Byte = 32KB의 메모리만 추가로 소비한다는 것도 아주 마음에 드네요. double 대신 float를 사용할 경우 16KB를 더 아낄수도 있겠습니다. 마음에 드는 LUT 최적화였습니다.