Rounding error, Underflow, Overflow

DDME·2020년 9월 24일
0

TIMESTAMP
@200924 시작

다음은 이안 굿펠로우의 Ch4 슬라이드를 참고한 것이다.

Numerical Precision: A deep learning super skill

  • 딥러닝은 종종 잘 작동하는 것처럼 보인다.
    • 손실함수는 작아지고 SOTA의 정확도에 도달한다.
    • 그 자체로 버그가 없어보인다
  • 반대로 딥러닝은 폭발하는 것처럼 보이기도 한다(NaNs, large values)

    원흉은 주로 loss of numerical precision이다.

Rounding and truncation errors

  • 디지털컴퓨터에서 실수를 표현하기 위해 float32와 같은 것을 사용한다.
  • 실수 xx+delta로 반올림된다(작은 값의 델타).
  • Overflow : 큰 값의 xinf로 대체된다
  • Underflow : 작은 값의 x0으로 대체된다

Example

  • 아주 작은 숫자를 큰 값에 더하는 것은 아무런 영향이 없어보인다. 하지만 이것은 나중에 커다란 변화를 일으킬 수 있다:
>>> a=np.array(0., 1e-8]).astype('float32')
>>> a.argmax()
1
>>> (a+1).argmax()
0

Secondary effects

  • xyinf로 오버플로우될 때 x-y를 계산하면, x-y=inf-inf=NaN이다.

exp

  • large x에 대해 exp(x)는 오버플로우된다.

    • 이때 very large가 아니더라도 오버플로우된다
    • float32: 89가 오버플로우된다.

      절대로 large x를 쓰지 마라!

  • very negative x에 대해 exp(x)는 언더플로우된다.

    • exp(x)가 분모일 경우 최악이다 (예: log)

Subtraction

  • xxyy가 유사한 크기이고 xxyy보다 항상 크다고 가정해보자.
  • 컴퓨터에서 rounding error로 인해 xyx-y는 음수일 수 있다.
  • 예: 분산
    Var(f(x))=E[(f(x)E[f(x)]2)]=E[f(x)2]E[f(x)]2\operatorname{Var}(f(x))=\mathbb{E}[(f(x)-\mathbb{E}[f(x)]^2)] \\ =\mathbb{E}[f(x)^2]-\mathbb{E}[f(x)]^2
    첫번째 식은 safe한 반면 두번째 식은 dangeruos하다.

log and sqrt

  • log(0)=-inf
    • log(<negative>) is imaginary, usually nan in software
  • sqrt(0)is 0, but its derivative has a divide by zero

    반드시 argument에 언더플로우나 round-to-negative을 피해라

    • 예: standard_dev=sqrt(variance)

log exp

  • log exp(x)x로 단순화되어야 한다.

    exp에서 오버플로우를 피하고, log에서 -inf를 일으키는 exp의 언더플로우를 피하라.

Which is the better hack?

  • normalized_x = x / st_dev
  • eps=1e^-7
  • Should we use
    • st_dev=sqrt(eps+variance)
    • st_dev=eps+sqrt(variance)?
  • What if variance is implemented safely and will never round to negative?

log(sum(exp))

  • Naive implementation:
    tf.log(tr.reduce_sum(tf.exp(array)))
  • Failure modes:
    • If any entry is very large, exp overflows
    • If all entries are very negative, all exp underflow... and then log is -inf

Stable version

mx = tf.reduce_max(array)
safe_array = array - mx
log_sum_exp = mx + tf.log(tf.reduce_sum(exp(safe_array))
  • built in version: tf.reduce_logsumexp

Why does the logsumexp trick work?

  • Algebraically equivalent to the original version:
    m+logiexp(aim)=m+logiexp(ai)exp(m)=m+log1exp(m)iexp(ai)=mlogexp(m)+logiexp(ai)m+\log\sum_i\exp(a_i-m) \\=m+\log\sum_i\frac{\exp(a_i)}{\exp(m)} \\=m+\log\frac{1}{\exp(m)}\sum_i\exp(a_i) \\=m-\log\exp(m)+\log\sum_i\exp(a_i)
  • No overflow:
    • Entries of safe_array are at most 0
  • Some of the exp terms underflow, but not all
    • At least one entry of safe_array is 0
    • The sum of exp terms is at least 1
    • The sum is now safe to pass to the log

Softmax

  • Softmax: use your library's built-in softmax function
  • If you build your own, use:
    safe_logits = logits - tf.reduce_max(logits)
    softmax = tf.nn.softmax(safe_logits)
  • Silmilar to logsumexp

Sigmoid

  • Use your library's built-in sigmoid function
  • If you build your own:
    • Recall that sigmoid is just softmax with one of the logits hard-coded to 0

Cross-entropy

  • Cross-entropy loss for softmax (and sigmoid) has both softmax and logsumexp in it
  • Compute it using the logits not the probabilities
  • The probabilities lose gradient due to rounding error where the softmax saturates
  • Use tf.nn.softmax_cross_entropy_with_logits
    or similar
  • If you roll your own, use the stabilization tricks for softmax and logsumexp

Bug hunting strategies

  • If you increase your learning rate and the loss gets stuck, you are probably rounding your gradient to zero somewhere: maybe computing cross-entropy using probabilities instead of logits
  • For correctly implemented loss, too high of learning rate should usually cause explosion

  • If you see explosion (NaNs, very large values) immediately suspect:

    • log
    • exp
    • sqrt
    • division
  • Always suspect the code that changed most recently

profile
NULL

0개의 댓글