최적화 알고리즘

• 최적화 알고리즘이란 손실함수를 최대화하는 방향으로 지속적으로 모델의 파라미터를 업데이트 해주는 도구이다.
• 물론 몇몇 사람들은 최적화를 손실함수를 최적화하는 블랙박스 장치로 여기는것에 만족할 수 있지만, 최적화를 잘 하기 위해선 더 깊은 지식을 필요로 한다.
  - 최적화 알고리즘이란 딥러닝에 있어 중요하다. 다시 말해, 복잡한 딥러닝 모델을 학습시키는것은 단순 몇시간, 며칠을 넘어 몇주도 넘게 걸릴수도 있는 일이다. 이 상황에서 최적화 알고리즘의 성능은 곧바로 모델의 성능과 직결된다
  - 다시 말해 각기 다른 최적화 알고리즘의 원칙들을 이해하고, 그 하이퍼파라미터들의 역할을 이해한다는 것은 우리가 원하는 딥러닝 모델의 성능 향상에 맞춰 하이퍼파라미터를 잘 조절할수 있게 된다는 것이다
• 딥러닝에서 발생하는 대부분의 최적화 문제는 비볼록nonconvex이다. 그럼에도 불구하고, 볼록convex 문제의 맥락으로 알고리즘을 설계하고 분석하는 것은 매우 유용하다. 그러한 연유로 먼저 최적화 알고리즘과 확률 경사하강법에 대한 간단한 증명으로 시작한다

최적화의 목적

• 최적화는 딥러닝에서 손실함수를 최소화하는 기능을 한다. 본질적으로, 최적화와 딥러닝의 목적은 본질적으로 다르다.
  - 최적화는 목적함수objective function을 최소화하는 것이 관심사인것에 반해, 딥러닝은 주어진 유한한 양의 데이터를 참고하여 이에 적합한 모델을 찾아내는 것이기 때문이다.
  - 깊게 들어가보자면, 학습 오차training error와 일반화 오류generalization error는 근본적으로 다르다. 훈련 데이터셋에 대한 손실함수가 최적화 알고리즘의 목적함수로 되고, 최적화 알고리즘은 학습 오차를 줄여낸다. 그러나 딥러닝의 목적(나아가 통계 추론statistical inference)은 일반화 오류 generalization error를 제거하는 것이다. 이를 이루기 위해선 딥러닝 모델은 과적합overfitting을 경계해야 하는데, 이는 역설적이게도 최적화 알고리즘이 훈련오차를 줄이려는 과정속에서발생하기도 한다
• 예
  - emprical risk란 훈련 데이터셋에서 발생하는 평균적 손실함수이다
  - risk란 모집단 데이터셋에서 발생하는 예측된 손실함수값이다
  - 여기에선 $f$ 를 리스크 함수, $g$ 를 empirical risk 함수라고 표현하여 시각화하였다
  - 훈련 데이터셋엔 전체 데이터셋의 일부만 있기 때문에, 그 결과 $g$ 는 $f$ 보다 덜 smooth한 모습을 보여준다

%matplotlib inline 
import numpy as np 
import torch 
from mpl_toolkits import mplot3d 
from d2l import torch as d2l 

def f(x):
    return x * torch.cos(np.pi * x)

def g(x):
    return f(x) + 0.2 * torch.cos(5 * np.pi *x)

def annotate(text,xy,xytext):
    d2l.plt.gca().annotate(text,xy=xy,xytext=xytext,
                arrowprops=dict(arrowstyle='->'))
    
x= torch.arange(0.5,1.5,0.01)
d2l.set_figsize((4.5,2.5))
d2l.plot(x,f(x),'x','risk')
annotate('min of\n empirical risk',(1.0,-1.2),(0.5,-1.1))
annotate('min of risk',(1.1,-1.05),(0.95,-0.5))

• result)
  

극소값 Local Minima

• 목적함수 $f(x)$ 가 있다고 하자. $f(x ^{*})$이 $x ^{*}$ 의 근방 포인트들에 대하여 같거나 작은 값을 갖고 있는경우, $f(x ^{*})$ 를 극소값local minimum이라고 부른다

• 만약 $f(x ^{*})$ 가 전체 정의역에 대하여 가장 작은 값을 갖는다면, $f(x ^{*})$ 는 최솟값 global minimum이라 불린다

• 예를 들어 $f(x)=x \cdot cos(\pi x)$ for $-1.0 \le x \le 2.0$ 이 있다고 하자

• 이의 극소값,최소값을 찾는 해석적 풀이는 다음과 같고
  - $\cfrac{\partial {f(x)}}{\partial {x}}=cos(\pi x)-\pi x sin(\pi x)=0$
  - $cos(\pi x)=\pi x sin(\pi x)$
  - $\pi=\displaystyle\frac{1}{x} cot (\pi x)$

• 도함수 그래프 코드

x = torch.arange(-1.0, 2.0, 0.01)
pi_arr= torch.pi * torch.ones(300)

def g(x):
    return 1/x * 1/torch.tan(torch.pi *x)

d2l.plot(x, [g(x),pi_arr ], 'x', 'y',ylim=[-(torch.pi+1),torch.pi+1])

![[output.svg]]

• 수치계산

for i in torch.arange(-1.0,2.0,1e-4):
    if abs(g(i)-torch.pi) < 1e-2 : 
        print(i,abs(g(i)-torch.pi))

"""result)
tensor(-0.2741) tensor(0.0078)
tensor(-0.2740) tensor(0.0046) 
tensor(-0.2739) tensor(0.0015) ->국소값
tensor(-0.2738) tensor(0.0017) 
tensor(-0.2737) tensor(0.0048) 
tensor(-0.2736) tensor(0.0080) 
tensor(0.2736) tensor(0.0080) 
tensor(0.2737) tensor(0.0048) 
tensor(0.2738) tensor(0.0017)
tensor(0.2739) tensor(0.0015)
tensor(0.2740) tensor(0.0046) 
tensor(0.2741) tensor(0.0078) 
tensor(1.0902) tensor(0.0083)
tensor(1.0903) tensor(0.0043) 
tensor(1.0904) tensor(0.0003) -> 최소값
tensor(1.0905) tensor(0.0036) 
tensor(1.0906) tensor(0.0076)
"""

• 그래프로 오리지널 함수를 그리면 다음과 같다

x = torch.arange(-1.0, 2.0, 0.01)
d2l.plot(x, [f(x), ], 'x', 'f(x)')
annotate('local minimum', (-0.3, -0.25), (-0.77, -1.0))
annotate('global minimum', (1.1, -0.95), (0.6, 0.8))

안장점 Saddle Points

• 안장점이란 gradient가 소멸vanish(0이 되는) 되지만, 극소 극댓값도 아닌 지점을 의미한다
• 예를 들어 $f(x)=x ^{3}$ 의 경우 $f'(x)=3 x ^{2}$ 로 $x=0$ 에서 기울기가 0이지만, 이는 극소,극대값 모두 아니다.
• 높은 차원에서의 안장점은 더 빈번하게 등장하는데, $f(x,y)=x ^{2}-y ^{2}$ 의 예시를 살펴보자
  - $\cfrac{\partial {f(x,y)}}{\partial {x}}=2x , \cfrac{\partial {f(x,y)}}{\partial {y}}=-2y$ 로 $(x,y)=(0,0)$ 에서 gradient가 0이 된다 그러나 그래프를 그려 살펴보면 이 지점은 극대나 극소지점이 아닌 것을 알 수 있다. 이 그래프의 모양이 마치 안장같이 생겼기 때문에, 안장점saddle point라는 이름이 명명되었다

x, y = torch.meshgrid(
    torch.linspace(-1.0, 1.0, 101), torch.linspace(-1.0, 1.0, 101))
z = x**2 - y**2

ax = d2l.plt.figure().add_subplot(111, projection='3d')
ax.plot_wireframe(x, y, z, **{'rstride': 10, 'cstride': 10})
ax.plot([0], [0], [0], 'rx')
ticks = [-1, 0, 1]
d2l.plt.xticks(ticks)
d2l.plt.yticks(ticks)
ax.set_zticks(ticks)
d2l.plt.xlabel('x')
d2l.plt.ylabel('y');

다차원 공간에서의 미분과 Hessian 행렬

Hessian Matrix

• 어떤 함수 $f:\mathbb{R} ^{n} \to \mathbb{R}$ 이 있다 하자. 그러면 이 함수에 대응되는 Hessian 행렬은 다음과 같이 정의된다
  - $[\boldsymbol{H}(f)]_{i,j}=\cfrac{\partial ^{2} {}}{\partial {x _{i}} \partial x _{j}}f(\boldsymbol{x})$
  -
• 성질
  - $H _{ij} = H _{ji}$ (Clairaut's Theorem)
• 대각화가능성 Diagonalizability
  - 헤시안 행렬은 항상 대각화 가능하다. 대칭행렬이기 때문이다.
  - 조건
  - $\boldsymbol{H} \in \mathcal{M} _{n \times n}(F)$
  - $\boldsymbol{\beta}=\{ \boldsymbol{e}_{1} ,\boldsymbol{e}_{2},\cdots,\boldsymbol{e}_{n}\}$
  - 주장
  - $\boldsymbol{\gamma}=\{v _{1},v _{2},\cdots,v _{n}\}$ $.s.t$ $\boldsymbol{H}(v _{j})=\lambda _{j} v _{j}$ , $\lambda _{j} \in F$ 이 존재한다.
  - 따라서 Hessian 행렬은 다음과 같이 고윳값 분해가 될 수 있다
  - $\boldsymbol{H}=[H]_{\beta}^{}=[I]_{\gamma}^{\beta}[H]_{\gamma}^{}[I]_{\beta}^{\gamma}$
  - 여기서 $[I]_{\gamma}^{\beta}$ 는 다음과 같다.
  - $[I(v _{j})]_{\beta}^{}=[I]_{\gamma}^{\beta}[v _{j}]_\gamma$
  - $col _{j}([H]_{\gamma}^{\beta})=v _{j}$

  	- 특정 방향에 대한 2차미분은 Hessian 행렬과 그 고유벡터의 곱으로 표현된다. 
  		- $v _{j} ^{T} \boldsymbol{H} v _{j}$
  	- 2차 도함수는 경사하강이 어떤 방향으로 움직일지를 보여준다. 함수 $f$ 에 대한 테일러미분의 2차근사는 다음과 같이 표현된다
  		- $f(\boldsymbol{x}) \sim f(\boldsymbol{x} ^{(0)})+(\boldsymbol{x}-\boldsymbol{x} ^{(0)})\boldsymbol{g}+\displaystyle\frac{1}{2}(\boldsymbol{x}-\boldsymbol{x} ^{(0)})^{T}\boldsymbol{H}(\boldsymbol{x}-\boldsymbol{x} ^{(0)})$

• 2차 도함수 테스트 $\mathbb{F} ^{n}$
  - In $\mathbb{F} ^{2}$
  - 만약 $f'(x)=0$ and $f''(x) >0$ 이라면 x 는 극소값이다
  - 만약 $f'(x)=0$ and $f''(x)<0$ 이라면 x is 극대값이다
  - In $\mathbb{F} ^{n}$
  - 만약 $\nabla{_{\boldsymbol{x}}f(\boldsymbol{x})}=0$ 이고, Hessian positive definite (모든 고유값이 양수)라면, $\boldsymbol{x}$ 는 극소값이다
  - 만약 $\nabla{_{\boldsymbol{x}}f(\boldsymbol{x})}=0$ 이고, Hessian negative definite(모든 고유값이 음수)라면, $\boldsymbol{x}$ 는 극대값이다
  - 만약 $\nabla{_{\boldsymbol{x}}f(\boldsymbol{x})}=0$ 이고, Hessian 행렬의 고유값이 모두 동일한 부호가 아니라면, $\boldsymbol{x}$는 안장점saddle point이다.

Vanishing Gradients

• 많은 딥러닝문제에서 발생되는 문제는 기울기 소멸vanishing gradient이다. 우리가 종종 사용하는 활성화 함수, 그리고 그 도함수를 고려하자.
• 예를 들어 $f(x)=tanh(x)$ 라고 하자. 그리고 $x=4$ 에서 시작한다 하자. 이때 $f'(x)=\cfrac{\partial {}}{\partial {x}}(\displaystyle\frac{sinh(x)}{cosh(x)})=\displaystyle\frac{cosh(x)}{cosh(x)}-\displaystyle\frac{sinh(x)}{cosh(x) ^{2}}\cdot sinh(x)$
  - $=\displaystyle\frac{cosh^{2}(x) -sinh^{2}(x)}{cosh ^{2}(x)}=\displaystyle\frac{1}{cosh ^{2}(x)}=sech ^{2}(x)=1-tanh ^{2}(x)$
• $f'(4)=0.0013$ 이다. 결과적으로 최적화가 수렁에 빠지게 된다. 이 원인이 ReLU가 도입되기전 딥러닝 학습에 오랜시간동안 문제를 일으켰었다

x = torch.arange(-2.0, 5.0, 0.01)
d2l.plot(x, [torch.tanh(x)], 'x', 'f(x)')
annotate('vanishing gradient', (4, 1), (2, 0.0))

볼록성 Convexity

• convex 함수는 항상 최솟값 Global minimum이 존재한다. 그에 반해 non-convex 함수는 여러곳의 극소값 local minimum이 존재한다.

집합에서의 볼록성

• 직관적 표현
  - 집합$X$에서 점과 점을 잡고 어떤 선을 그었을 때, 그 선을 포함하는 점 조차 집합 $X$ 에 포함될 때, 집합이 볼록convex하다고 정의한다.
  - 즉 위 그림에선 첫번째와 두번째 집합만이 convex하다고 칭할 수 있다
• 수학적 표현
  - 조건
  - 어떤 집합 $\mathcal{X}$ 가 벡터공간내에 있다고 하자. 그 집합의 임의의 원소원소 $\boldsymbol{x}_{1},\boldsymbol{x} _{2} \in \mathcal{X}$ 가 있다 하자. 그리고 스칼라 $t \in [0,1]$ 가 있다고 하자
  - 정의
  - $t \boldsymbol{x}_{1}+(1-t)\boldsymbol{x}_{2} \in \mathcal{X}$ 일때 집합 $\mathcal{X}$ 를 볼록convex하다고 정의한다
  
• 이 정의하에선 다음과 같은 사실을 알 수 있다
  - 첫번째 집합 $\mathcal{X}$ 와 두번째 집합 $\mathcal{Y}$ 모두 볼록집합이라 하자 이 경우 $\mathcal{X} \cap \mathcal{Y}$ 또한 볼록집합이다

함수-그래프에서의 볼록성

• $(x _{1}, x _{2})$ 택하여 두 점을 잇는 직선을 그었는데 이를 할선이라고 하자. 이 경우 함수 $f$ 는 $(x _{1},x _{2})$ 내에서 항상 할선의 아래에 위치하고 있다.

수식적 표현

• 1변수 함수
  - 조건
  - 정의역 내 임의의 두점 $x _{1},x _{2} \in \mathcal{D}$ 가 존재하고 매개변수 $t \in [0,1]$ 가 존재한다고 하자
  - 정의
  - 함수 $f(x)$ 가 다음의 식이 항상 만족된다면 이 함수는 convex하다고 말할 수 있다
  - $tf(x _{1})+(1-t)f(x _{2}) \ge f(tx _{1}+(1-t)x _{2})$

f = lambda x: 0.5 * x**2  # Convex
g = lambda x: torch.cos(np.pi * x)  # Nonconvex
h = lambda x: torch.exp(0.5 * x)  # Convex

x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
    d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

Jensen의 부등식

• 조건
  - 볼록함수 $f$ 가 주어졌다고 하자
  - $\displaystyle\sum_{i}^{}{\alpha _{i}}=1$ $\alpha _{i} >0$ 이라고 하자
  - $\boldsymbol{X}$ 는 확률변수라고 하자
• 정리
  - $\displaystyle\sum_{i}^{}{\alpha _{i}f(x _{i})} \ge f(\displaystyle\sum_{i}^{}{\alpha _{i}x _{i}})$
  - $\mathbb{E} _{\boldsymbol{X}}[f(\boldsymbol{X})]) \ge f(\mathbb{E} _{\boldsymbol{X}}(\boldsymbol{X}))$
  - 달리 말하자면, 볼록함수의 기댓값은 각 기댓값에 대한 볼록함수값보다 작다는 것이다.

극소값Local Minima가 최소값Global Minima인가?

• 볼록함수의 극소값이 최솟값인것을 증명하자
• 조건
  - 볼록함수$f$ 가 볼록집합 $\mathcal{X}$ 에 정의되었다고 하자
  - $x ^{*} \in \mathcal{X}$ 벡터가 극소값이라고 하자.
• 주장
  - $x ^{*}$ 는 최솟값이다
• 증명
  - 극소값 $x ^{*}$ 가 $f$ 의 최솟값이 아닐 것이라 가정하자. 그렇다면 최솟값 $x' \in \mathcal{X}$ 가 존재하여, $f(x')<f(x ^{*})$ 를 만족시킬 것이다.
  - 그러나 볼록함수의 정의의 의해
  - $f(\lambda x ^{*}+(1-\lambda)x')\le \lambda f(x ^{*})+(1-\lambda)f(x')$
  - $f(\lambda x ^{*}+(1-\lambda)x')< \lambda f(x ^{*})+(1-\lambda)f(x ^{*})=f(x ^{*})$
  - $\lambda \to 1$ 인경우 이는 $x ^{*}$ 근방neighborhood 이 되게 된다. 즉 $\lim_{\lambda \to 1}{f(\lambda x ^{*}+(1-\lambda)x')}=\lim_{\lambda \to 1}{f( x ^{*}+(1-\lambda)(x'-x ^{*}))}<f(x ^{*})$ 가 되는데, 이는 $x ^{*}$ 가 극소값이라는 조건과 모순된다.
  - 따라서 기존 가정이 틀리게 되었고 $x ^{*}=x'$ 즉 최솟값이라고 증명된다
• 이 결과는 볼록함수에 대한 극소값을 찾으면, 이는 항상 최솟값이라는 뜻으로, 손실함수등을 계산하여 함수의 최솟값을 찾는 과정에서 "구덩이에 빠지는" 현상을 겪을 위험이 없다는 뜻이다
• 그러나 이 증명이 최솟값이 존재하거나, 정확히 하나만 존재한다는 것을 증명하진 않는다. 예를 들어 $f(x)=exp(x)$ 의 경우 최솟값은 존재하지 않는다

볼록함수의 Below set

• Below set의 정의
  - convex 집합 $\mathcal{X}$ 위에 정의된 convex function $f$ 이 있다하자
  - $\mathcal{S}_{b}\equiv \{ x|x \in \mathcal{X} \,\,and \,\,f(x) \le b\}$
• 이 경우 $\mathcal{S}_{b}$ 또한 convex set임을 보이자
  - $x,x' \in \mathcal{S} _{b}$ 라고 할때 $\lambda x +(1-\lambda)x' \in \mathcal{S}_{b}$ ($\lambda \in [0,1]$ )임을 보이는 것과 같다
  - $f(x) \le b$ 이고 $f(x') \le b$ 이기 때문에 convex함수의 정의에 따라
  - $\lambda f(x) \le \lambda b$ , $(1-\lambda)f(x') \le (1-\lambda)b$ 이므로 $\lambda f(x)+(1-\lambda)f(x') \le b$
  - $f(\lambda x+(1-\lambda)x') \le \lambda f(x)+(1-\lambda)f(x')\le b$
  - 즉 $f(\lambda x+(1-\lambda)x') \in \mathcal{S} _{b}$

볼록성과 이차미분

• 함수 $f:\mathbb{R} ^{n} \to \mathbb{R}$ 이 있다 하자.
  - 이 함수가 convex한지 판별하는 방법은 다음과 같다
  - 함수의 Hessian 행렬 $\boldsymbol{H}(f)$ 가 positive-semidefinite(임의의 $\boldsymbol{x} \in \mathbb{R} ^{n}$ 에 대하여 $\boldsymbol{x}^{T}\boldsymbol{H}\boldsymbol{x} \ge 0$ 이다. 이는 $\boldsymbol{H}(f))$ 의 eigenvalue가 non-negative로만 구성된 것과 동치이다
  - 예를 들어 $F(\boldsymbol{x})=\displaystyle\frac{1}{2}\| \boldsymbol{x} \| ^{2}$ 의 경우 $\boldsymbol{H}(f)=\mathbb{I}_{n}$ 으로 positive-definite여서 convex함을 보일 수 있다

2차 미분가능 일변수함수 $f : \mathbb{R} \to \mathbb{R}$ 에 대하여 $f$의 convex함은 $f'' \ge 0$ 과 일대일 대응관계이다. 이에 대한 증명을 하자

• $f$ 의 convexity를 보이기 위한 조건으로서 다음의 사실을 활용하자
• $\lambda f(x _{1})+(1-\lambda)f(x _{2}) \ge f(\lambda x _{1}+(1-\lambda)x _{2})$
• $\lambda=\displaystyle\frac{1}{2}$ 이고 $x _{1}=x-\epsilon$ , $x _{2}=x+\epsilon$ 이라고 한다면
• $\displaystyle\frac{1}{2}f(x+\epsilon)+\displaystyle\frac{1}{2}f(x-\epsilon) \ge f(\displaystyle\frac{x+\epsilon}{2}+\displaystyle\frac{x-\epsilon}{2})=f(x)$
• $f''(x)=\lim_{\epsilon \to 0}{\displaystyle\frac{f(x+\epsilon)+f(x-\epsilon)-2f(x)}{\epsilon ^{2}}}$
  - $=\lim_{\epsilon \to 0}{\displaystyle\frac{1}{\epsilon}[\displaystyle\frac{f(x+\epsilon)-f(x)}{\epsilon}-\displaystyle\frac{f(x)-f(x-\epsilon)}{\epsilon}]}\ge 0$
  - $f'' \ge 0$ 란 $f'$ 이 단조-비감소 monotically nondecreasing($x$ 가 커질수록 $f'$ 는 값이 같거나 증가하는 방향으로 변함)의 형태를 띈다는 것을 보여준다
  
• Ref. 평균값 정리 Mean Value Theorem
  - 함수 $f(x)$ 가 닫힌 구간 $[a,b]$ 에서 연속이고, 열린구간 $(a,b)$ 에서 미분가능 하다면 $f'(c)=\displaystyle\frac{f(b)-f(a)}{b-a}$ 를 만족시키는 $c \in (a,b)$ 가 적어도 하나 이상 존재한다
  
• $a < x<b$ 의 세 점이 $\mathbb{R}$ 에 있다하자. 만약 $x=(1-\lambda)a+\lambda b$ , $\lambda \in [0,1]$ 이라고 한다면 평균값 정리에 따라 다음 조건을 만족시키는 $\alpha \in (a,x)$ , $\beta \in (x,b)$ 가 각각 존재한다
  - $f'(\alpha)= \displaystyle\frac{f(x)-f(a)}{x-a}$
  - $f'(\beta)=\displaystyle\frac{f(b)-f(x)}{b-x}$
• 단조성에 따라 $f'(\beta)\ge f'(\alpha)$ 이며, 이는
  - $\displaystyle\frac{f(b)-f(x)}{b-x} \ge \displaystyle\frac{f(x)-f(a)}{x-a}$
  - $\displaystyle\frac{f(b)}{b-x}+\displaystyle\frac{f(a)}{x-a} \ge f(x)[\displaystyle\frac{1}{b-x}+\displaystyle\frac{1}{x-a}]=f(x)(\displaystyle\frac{b-a}{(b-x)(x-a)})$
  - $\displaystyle\frac{x-a}{b-a}f(b)+\displaystyle\frac{b-x}{b-a}f(a) \ge f(x)$
• $x=(1-\lambda)a+\lambda b$ 임을 대입하면
  - $\displaystyle\frac{-\lambda a +\lambda b}{b-a}f(b)+\displaystyle\frac{(1-\lambda)b-(1-\lambda)a}{b-a}f(a)\ge f(x)$
  - $\lambda f(b)+(1-\lambda)f(a) \ge f(x)=f(\lambda b+(1-\lambda)a)$
  
• 즉 $f'' \ge 0$ 이면 $f$ 는 convex하다는 사실이 증명된다

2차 미분가능 다변수 함수 $f:\mathbb{R} ^{n}\to \mathbb{R}$ 에 대해여 $f$ 의 convex는 다음과 일대일 대응임을 증명하자

• $\boldsymbol{x},\boldsymbol{y} \in \mathbb{R} ^{n}$ 에 대하여 $g(\boldsymbol{z}) \equiv f(z \boldsymbol{x}+(1-z )\boldsymbol{y})$ ,where $z \in [0,1]$란 함수가 convex하다

• $f$ 의 convex함이 $g$ 의 convex함을 내포한다는 것을 증명하자
  - $a,b, \lambda \in [0,1]$ 라 하자
  - 그렇다면

  • $0 \le \lambda a \le \lambda$ , $0 \le (1-\lambda)b \le (1-\lambda)$ 이므로
  • $0 \le \lambda a +(1-\lambda)b \le 1$
    
  • $g(\lambda a+(1-\lambda)b)$
  • $=f((\lambda a +(1-\lambda)b)\boldsymbol{x}+(1-(\lambda a +(1-\lambda)b))\boldsymbol{y})$
  • $=f(\lambda a \boldsymbol{x}+(1-\lambda)b \boldsymbol{x}-(1-\lambda)b \boldsymbol{y}-\lambda a \boldsymbol{y}+(1-\lambda+\lambda)\boldsymbol{y})$
  • $=f(\lambda(a \boldsymbol{x}+(1-a)\boldsymbol{y})+(1-\lambda)(b \boldsymbol{x}+(1-b)\boldsymbol{y}))$
  • $\le \lambda f(a \boldsymbol{x}+(1-a)\boldsymbol{y})+(1-\lambda)f(b \boldsymbol{x}+(1-b)\boldsymbol{y})=\lambda g(a)+(1-\lambda) g(b)$
  • 즉 $g$ 는 convex하다

• 역으로 $g$ 의 convex함이 $f$ 의 convex함을 내포한다는 것을 증명하자
  - $g(\lambda)=f(\lambda \boldsymbol{x}+(1-\lambda)\boldsymbol{y})$
  - $=g(\lambda \cdot 1 +(1-\lambda)\cdot 0)$
  - $\le \lambda g(1)+(1-\lambda)g(0)=\lambda f(\boldsymbol{x})+(1-\lambda)f(\boldsymbol{y})$
  - 즉 $f$ 는 convex하다

다변수함수의 Convex 판별공식 증명

• $f: \mathbb{R} ^{n} \to \mathbb{R}$ 이 convex 함의 필요충분조건은 $\boldsymbol{x},\boldsymbol{y} \in \mathbb{R} ^{n}$ 에 대하여 $g(z) \equiv f(z \boldsymbol{x}+(1-z)\boldsymbol{y})$(where $z \in [0,1])$가 convex 하다는 것이다.
  - $h=z \boldsymbol{x}+(1-z)\boldsymbol{y}$ 라 하자 그러면 $g(z)=f(h(z,\boldsymbol{x},\boldsymbol{y}))$ 꼴이다
  - $\cfrac{\partial {g}}{\partial {z}}=\cfrac{\partial {g}}{\partial {f}}\cfrac{\partial {f}}{\partial {h}} \cfrac{\partial {h}}{\partial {z}}=f'(h)(\boldsymbol{x}-\boldsymbol{y})$
  - $\cfrac{\partial {g'}}{\partial {z}}=\cfrac{\partial {}}{\partial {z}}[f'(h)](\boldsymbol{x}-\boldsymbol{y})=(\boldsymbol{x}-\boldsymbol{y})^{T}f''(h)(\boldsymbol{x}-\boldsymbol{y})=(\boldsymbol{x}-\boldsymbol{y})^{T} \boldsymbol{H}(\boldsymbol{x}-\boldsymbol{y})$
  - ($\boldsymbol{H}(f)=\cfrac{\partial {}}{\partial {\boldsymbol{x}}}\cfrac{\partial {}}{\partial {\boldsymbol{x}}}(f)$ 이므로)
  - $g''(\boldsymbol{x},\boldsymbol{y},z)=(\boldsymbol{x}-\boldsymbol{y})^{T} \boldsymbol{H}[f(z \boldsymbol{x}+(1-z)\boldsymbol{y})](\boldsymbol{x}-\boldsymbol{y}) \ge 0$ 이라면 $f'' \ge 0$ 이라는 정리를 얻는다.
  - (본인 생각) 이를 기하학적으로 해석하자면 벡터공간속 두 지점 $\boldsymbol{x}$ 와 $\boldsymbol{y}$ 을 이은 직선영역 위에선 모든 Hessian 행렬값이 positive-semidefinite 해야 한다는 의미이다

제한 조건

• 제한된 최적화문제는 다음과 같이 표현할 수 있다
  - $\underset{\boldsymbol{x}}{\text{min}} \,\, {f(\boldsymbol{x})}$ $\text{subject to }{c _{i}(\boldsymbol{x})} \le 0$ $\text{for all }{i} \in \{1,2,\cdots,n\}$
  - 이때 $f$ 는 목적함수이고, $c _{i}$ 는 제한조건 함수들이다.
• 예를 들어
  - 첫번째 제한조건이 ${c}_{1}(\boldsymbol{x})=\| \boldsymbol{x} \|_{2}-1$ 라고 하자
  - 이 경우 변수 $\boldsymbol{x}$ 는 단위구unit ball 에 히게 된다
  - 두번째 제한조건이 $c _{2}(\boldsymbol{x})=\boldsymbol{v}^{T}\boldsymbol{x}+b$ 라고 하자
  - 이 경우 $\boldsymbol{x}$ 는 절반-공간half-space에 갇히게 된다
  - 두 조건을 만족시키는 $\boldsymbol{x}$ 는 단위구의 어떤 slice 면이 된다

라그랑지 승수법 Lagrange Multiplier

• 라그랑지안 승수법
  - 조건
  - 목적함수 Objective Function $f:\mathcal{D}\subset \mathbb{R} ^{n} \to \mathbb{R}$ 이 있고, 제한조건함수 Constraint Function $g _{i}:\mathcal{D}\subset\mathbb{R} ^{n} \to \mathbb{R}$ $\text{for all }{i} \in \{1,2,\cdots,k\}$ 가 있다고 하자
  - 등위집합 level set $\mathcal{S}=\{ \boldsymbol{x} \in \mathcal{D}: g _{\boldsymbol{1}}(\boldsymbol{x})=g _{2}(\boldsymbol{x})=\cdots=g _{k}(\boldsymbol{x})=0 \}$ 이 있다하자
  - 정리
  - 그러면 $f$를 $S$ 에 제한된 함수 $f| _{S}$ 의 극점extrema $\boldsymbol{x}^{*} \in \mathcal{S}$ 이 존재한다면
  - $\nabla_{}f(\boldsymbol{x}^{*})=\displaystyle\sum_{i=1}^{k}{\lambda _{i} \nabla_{}g _{i}(\boldsymbol{x}^{*})}$ 를 만족시키는 실수 $\lambda _{1},\lambda _{2},\cdots, \lambda _{k}$ 가 존재한다
  • 증명
    - Lemma. $f$ 를 등위집합 $\mathcal{S}$ 에 제한한 함수 $f| _{S}$ 에 대하여, 극값 $\boldsymbol{x}^{*} \in \mathcal{S}$ 가 존재한다면 $\nabla_{\boldsymbol{x}}f(\boldsymbol{x}^{*})$ 는 등위집합 $S$ 위 점 $\boldsymbol{x}^{*}$ 에서 수직이다 ref
    -
    - 점 $P$를 포함하는 등위집합에 속하는 임의의 곡선 $\boldsymbol{x}:[0,1] \to S$ 를 고려하자. 이때 어떤값 $t _{0} \in [0,1]$ 에서 점 $P$ 를 지난다
    - 등위집합 $\mathcal{S}$ 에 속하는 임의의 곡선 $\boldsymbol{x}(t)$ 에 대하여 $f(\boldsymbol{x}(t))$ 에 대하여 고려하자. $\boldsymbol{x}'(t _{0})$는 점 $P=\boldsymbol{x}(t _{0})$ 에서 곡선 $\boldsymbol{x}$ 와 접한다 (이는 $\boldsymbol{x}(t):\mathbb{R} \to \mathbb{R} ^{n}$ 의 도함수 $\boldsymbol{x}'(t)$를 속도곡선이라 부르는데, 속도곡선은 곡선 $\boldsymbol{x}(t$에 항상 접하기 때문이다)
    - $\cfrac{d {}}{d {t}}f(\boldsymbol{x}(t))=\nabla_{\boldsymbol{x}}f(\boldsymbol{x}(t)) \cdot \boldsymbol{x}'(t)=0$
    
  • 제한함수 $g _{i}(\boldsymbol{x})$ 는 $\mathcal{S}$ 상에서 $g _{i}(\boldsymbol{x})=0$ 이므로, 등위면 상의 곡선 $\boldsymbol{x}(t)$ 를 도입하면 $\cfrac{d {}}{d {t}}g _{i}(\boldsymbol{x}(t))= \nabla_{\boldsymbol{x}}g _{i}(\boldsymbol{x}) \cdot \boldsymbol{x}'(t)=0$ . $\nabla_{\boldsymbol{x}}g _{i}(\boldsymbol{x})$ 는 등위면 $S$ 위 모든 점에 대하여 수직임을 알 수 있다
    - 따라서 등위집합 level set $\mathcal{S}=\{ \boldsymbol{x} \in \mathcal{D}: g _{\boldsymbol{1}}(\boldsymbol{x})=g _{2}(\boldsymbol{x})=\cdots=g _{k}(\boldsymbol{x})=0 \}$ 로 제한된 함수 $f,g _{i}$ 에 대하여 (이 아래는 본인의 추론)
    - $g _{i}:\mathbb{R} ^{n} \to \mathbb{R}$ $\text{for all }{i} \in \{1,2,\cdots,k\}$ 에 대한 등위집합은 $n-1$ 차원을 차지하는데, $n$ 차원 공간상에서 $n-1$ 차원의 곡면과 수직인 벡터는 1차원이므로,
    - $f$ 의 극점 $x ^{*}\in \mathcal{S}$ 상에선 $\nabla_{\boldsymbol{x}}f,\nabla_{\boldsymbol{x}}g _{i}$ 가 등위집합 $\mathcal{S}$ 에 수직한, 서로 평행한 방향이다
    
• 라그랑지안 $L$ 을 적용시켜 제한된 최적화문제를 해결할 수 있다
  - $c _{i}(\boldsymbol{x}) \le 0$ 의 조건들을 일일이 적용시키기 보단, 단순히 $\alpha _{i}c _{i}(\boldsymbol{x})$ 를 목적함수$f(\boldsymbol{x})$ 에 더하여 이 값을 라그랑지안으로 지정하는 것이다

경사하강법 Gradient Descent

1차원 경사하강

• 우선 1차원에서의 경사하강법을 고려한다. 연속함수 $f:\mathbb{R} \to \mathbb{R}$ 이 있다고 하자. 테일러 급수를 활용하면
  - $f(x)=\displaystyle\sum_{i=0}^{\infty }{\displaystyle\frac{f ^{(n)}(a)}{n!}}(x-a) ^{n}$
  - $f(x+\epsilon)=\displaystyle\sum_{i=0}^{\infty }{}\displaystyle\frac{f ^{(n)}(\epsilon)}{n!}x ^{n}=\displaystyle\sum_{i=0}^{\infty }{\displaystyle\frac{f ^{(n)}(x)}{n!}}\epsilon ^{n}$ : $x$와 $\epsilon$ 의 형태를 살펴보자
  - $f(x+\epsilon)=f(x)+\epsilon f'(x)+\mathcal{O}(\epsilon ^{2})$
  - $\epsilon$ 만큼 negative gradient 방향으로 이동하였을 때, $f$ 값을 감소시킨다는 추론은 합리적이다. 종합하여, 다음과 같이 식을 세우자
  - $f(x-\eta f'(x))=f(x)-\eta f'(x) ^{2}+\mathcal{O}(\eta ^{2} f'(x))$ 로 두자
  - 만약 도함수 $f'(x) \neq 0$ 이라면 $\eta f'(x)>0$ 의 값을 가질 것이다.
  - 게다가, $\eta$는 원하는 만큼 크기를 조절할 수 있으므로, 충분히 작게한다면 고차항들은 무시할 수 있게 될 것이다. 종합하여
  - $f(x-\eta f'(x))\lessapprox f(x)$ 가 될 것이다.

  	 -  종합하여 $x \leftarrow x-\eta f'(x)$ 으로 반복하여 계산한다면, $f(x)$ 값은 점차 감소하는 방향이 될 것이다. 

• gradient descent는 초깃값 ${x}$ 와 학습률 $\eta >0$ 을 설정하고, 특정 조건에 다다를 때 (예를 들어 gradient의 크기 $|f'(x)|$ 가 충분히 작아지거나, 반복연산수가 특정 값 이상까지 다다른다면)까지 반복 계산하는 방식이다.

• $f(x)=x ^{2}$ 에 대한 반복학습 시연

from unittest import result
import numpy as np 
import torch 
from d2l import torch as d2l 

def f(x):
    return x ** 2 

def f_grad(x):
    return 2 * x 

def gd(eta,f_grad):
    x= 10.0
    results= [x]
    for i in range(10):
        x -= eta * f_grad(x)
        results.append(float(x))
    print(f'epoch 10, x:{x:f}')
    return results 

results= gd(0.2,f_grad)

def show_trace(results, f):
    n= max(abs(min(results)),abs(max(results)))
    f_line = torch.arange(-n,n,0.01)
    d2l.set_figsize()
    d2l.plot([f_line, results], [[f(x) for x in f_line],
            [f(x) for x in results]], 'x','f(x)',fmts=['-','-o'])

show_trace(results,f)

학습률

• 학습률 $\eta$ 는 알고리즘 설계자가 서정할 수 있다. 만약 학습률이 너무 작다면 $\boldsymbol{x}$ 의 업데이트가 매우 느릴것이고, 더 나은 해를 갖기 위하여 더 많은 연산을 요구하게 될것이다
• 반대로 만약 학습률이 너무 크다면, 테일러급수의 $\mathcal{O}(\eta ^{2}f'(x) ^{2})$ 값이 지나치게 커져 오차로서 무시하기 어려울 정도가 될 것이다.

show_trace(gd(0.05,f_grad),f)

show_trace(gd(1.1, f_grad), f)

Local Minima

• non-convex 함수를 묘사하기 위하여 $f(x)=x \cdot cos(cx)$ 를 사용하자 이 함수는 무한개의 많은 극소값을 가지고 있다.
• 우리의 학습률 설정과 어떻게 조건을 설정했는가에 따라, 수 많은 해가 나올수 있다.
• 이 예의 아래는 다음과 같은 높은 학습률이 나쁜 극소값을 찾게 된다는 것을 보여준다

c= torch.tensor(0.15 * np.pi)

def f(x):
    return x * torch.cos(c*x)
def f_grad(x):
    return torch.cos(c*x) - c*x* torch.sin(c*x)

show_trace(gd(2,f_grad),f)

다변수 경사하강

다변수함수의 테일러 급수

• ref
• 조건
  - $k$ 번 미분가능한 함수 $f:\mathbb{R} ^{n} \to \mathbb{R}$ 가 있고, 어떤 포인트 $\boldsymbol{a} \in \mathbb{R} ^{n}$ 이 있다고 하자.
• 정리
  - $f(\boldsymbol{x})=\displaystyle\sum_{|\alpha| \le k}^{}{\displaystyle\frac{\partial _{\alpha}f(\boldsymbol{a})}{\alpha!}}(\boldsymbol{x}-\boldsymbol{a}) ^{\alpha}+\displaystyle\sum_{|\alpha|=K+1}^{}{R_{\alpha,k}(\boldsymbol{h})}$
  - $\alpha=(\alpha _{1}, \alpha _{2},\cdots,\alpha _{n})$
  - $|\alpha|=\alpha _{1}+\alpha _{2}+\cdots+ \alpha _{n}$ 이고 $|\alpha|$ 가 다변수 테일러 급수의 차수degree이다.
  - $\alpha!=\alpha _{1}! \alpha _{2}! \cdots \alpha _{n}!$
  - $\partial _{\alpha}f=\partial _{x _{\alpha1} }\partial _{x _{\alpha2}}\cdots\partial _{x _{\alpha n}}f$
  - $R _{\alpha,k}(\boldsymbol{h})=\displaystyle\sum_{|\alpha|=k+1}^{}{\partial ^{\alpha}f(\boldsymbol{a}+c \boldsymbol{h})\displaystyle\frac{\boldsymbol{h} ^{\alpha}}{\alpha!}}$ for some $c \in (0,1)$

• $\boldsymbol{x}=[x _{1},x _{2},\cdots ,x _{d}]^{T}$ 라고 하자. 그리고 목적함수는 $f:\mathbb{R} ^{d} \to \mathbb{R}$ 이라고 하자.
• 이 목적함수의 gradient는 다음과 같이 정의된다
  - $\nabla_{\boldsymbol{x}}f(\boldsymbol{x})=[\cfrac{\partial {f(\boldsymbol{x})}}{\partial {x _{1}}}, \cfrac{\partial {f(\boldsymbol{x})}}{\partial {x _{2}}},\cdots,\cfrac{\partial {f(\boldsymbol{x})}}{\partial {x _{d}}}]$
  - 다변수함수의 테일러급수에 따라 $f(\boldsymbol{x}+\boldsymbol{\epsilon})=\displaystyle\sum_{|\alpha| \le k}^{}{\displaystyle\frac{\partial^{\alpha}f(\boldsymbol{x})}{\alpha!}}\boldsymbol{\epsilon} ^{\alpha}+\displaystyle\sum_{|\alpha|=K+1}^{}{R _{\alpha,k}(\boldsymbol{h})}$ 이다. 이를 일차항만 전개하자
  - $f(\boldsymbol{x}+\boldsymbol{\epsilon})=f(\boldsymbol{x})+ \boldsymbol{\epsilon} ^{T}\partial _{\boldsymbol{x}}f(\boldsymbol{x}) +\mathcal{O}( \| \epsilon ^{2} \|)=f(\boldsymbol{x})+\boldsymbol{\epsilon}^{T}\nabla_{}f(\boldsymbol{x})+\mathcal{O}(\| \boldsymbol{\epsilon} \| ^{2})$
  - 따라서 두번째 텀 $\boldsymbol{\epsilon}^{T}\nabla_{}f(\boldsymbol{x})$ 가 가장 가파른 방향의 경사로 함수를 줄이는 방향이 된다.
  - 따라서 경사 하강법 알고리즘의 원형은 다음과 같다 $\boldsymbol{x}\leftarrow \boldsymbol{x}-\eta \nabla_{}f(\boldsymbol{x})$
• 예제
  - 목적함수 $f(\boldsymbol{x})=x _{1} ^{2}+2 x _{2} ^{2}$ 라고 하자. $\nabla_{}{f(\boldsymbol{x})}=[2x _{1},4 x _{2}]^{T}$ 이다.
  - 이때 $\boldsymbol{x}$ 의 궤적trajectory에서 포기 위치는 $[-5,-2]$ 이다

def train_2d(trainer, steps=20, f_grad=None):  #@save
    """Optimize a 2D objective function with a customized trainer."""
    # `s1` and `s2` are internal state variables that will be used in Momentum, adagrad, RMSProp
    x1, x2, s1, s2 = -5, -2, 0, 0
    results = [(x1, x2)]
    for i in range(steps):
        if f_grad:
            x1, x2, s1, s2 = trainer(x1, x2, s1, s2, f_grad)
        else:
            x1, x2, s1, s2 = trainer(x1, x2, s1, s2)
        results.append((x1, x2))
    print(f'epoch {i + 1}, x1: {float(x1):f}, x2: {float(x2):f}')
    return results

def show_trace_2d(f, results):  #@save
    """Show the trace of 2D variables during optimization."""
    d2l.set_figsize()
    d2l.plt.plot(*zip(*results), '-o', color='#ff7f0e')
    x1, x2 = torch.meshgrid(torch.arange(-5.5, 1.0, 0.1),
                          torch.arange(-3.0, 1.0, 0.1))
    d2l.plt.contour(x1, x2, f(x1, x2), colors='#1f77b4')
    d2l.plt.xlabel('x1')
    d2l.plt.ylabel('x2')

def f_2d(x1,x2):
    return x1 **2 + 2 * x2 ** 2 

def f_2d_grad(x1,x2):
    return (2 * x1 , 4*x2)

def gradient_descent_2d(x1,x2,s1,s2,f_grad):
    g1,g2=f_grad(x1,x2)
    return (x1-eta* g1, x2-eta * g2 ,0,0)

eta= 0.1
show_trace_2d(f_2d,train_2d(gradient_descent_2d,f_grad=f_2d_grad))

Newton의 근사법

1변수 함수의 뉴턴 근사법

• 1변수함수에 대한 뉴턴의 근사법은 $x _{n+1}=x _{n}-\displaystyle\frac{f(x _{n})}{f'(x _{n})}$ 이다. 즉 $\epsilon=-\displaystyle\frac{f(x _{n})}{f'(x _{n})}$ 이다.
• 함수의 근 $x=a$ 이라 하고, $x _{n}$ 에서의 테일러 급수를 전개하자
  - $f(a)=\displaystyle\sum_{i=0}^{n}{\displaystyle\frac{f ^{(n)}(x _{n})}{n!}}(a-x _{n}) ^{n} \sim f(x _{n})+f'(x _{n})(a- x _{n})+\displaystyle\frac{1}{2}f''(x _{n})(a-x _{n}) ^{2})$
  - $f(a)=0$ 을 대입하고, $f'(x _{n})$ 으로 나누면
  - $0 \sim \displaystyle\frac{f(x _{n})}{f'(x _{n})}+(a-x _{n})+\displaystyle\frac{1}{2}\displaystyle\frac{f''(x _{n})}{f'(x _{n})}(a-x _{n}) ^{2}$
  - 여기서 뉴턴의 근사법 식을 더하자
  - $x _{n+1} \sim \displaystyle\frac{f(x _{n})}{f'(x _{n})}+a-\displaystyle\frac{f(x _{n})}{f'(x _{n})}+\displaystyle\frac{1}{2}\displaystyle\frac{f''(x _{n})}{f'(x _{n})}(a-x _{n}) ^{2}$
  - $a-x _{n+1} \sim \displaystyle\frac{-1}{2}\displaystyle\frac{f''(x _{n})}{f'(x _{n})}(a-x _{n}) ^{2}$
  - $\epsilon _{n}= a - x _{n}$ 라 하면 즉
  - $\epsilon _{n+1}=\displaystyle\frac{-1}{2}\displaystyle\frac{f''(x _{n})}{f'(x _{n})}\epsilon _{n} ^{2}$ 인 것이다
  -

다변수함수의 뉴턴 근사법

• 다변수함수의 테일러급수에 따라 $f(\boldsymbol{x}+\boldsymbol{\epsilon})=\displaystyle\sum_{|\alpha| \le k}^{}{\displaystyle\frac{\partial^{\alpha}f(\boldsymbol{x})}{\alpha!}}\boldsymbol{\epsilon} ^{\alpha}+\displaystyle\sum_{|\alpha|=K+1}^{}{R _{\alpha,k}(\boldsymbol{h})}$ 이다. 이를 2차항까지 전개하자
• $f(\boldsymbol{x}+\boldsymbol{\epsilon})=f(\boldsymbol{x})+\boldsymbol{\epsilon}^{T}\nabla_{}{f(\boldsymbol{x})}+\displaystyle\frac{1}{2}\boldsymbol{\epsilon}^{T} \nabla ^{2}{f(\boldsymbol{x})}\boldsymbol{\epsilon}+\mathcal{O}(\| \boldsymbol{\epsilon} \| ^{3})$
  - $\boldsymbol{H} ^{2}=\nabla ^{2} {f(\boldsymbol{x})}$ 로 표기하자
  - 그렇다면 헤시안 행렬 $\boldsymbol{H}$ 을 계산할 때마다 $\mathcal{O}(d ^{2})$ 의 연산이 사용되는데, 이는 backpropagation을 시행할때마다 너무 많은 연산이 요구되 잘 사용되지 않는 이유이기도 하다. 하지만 지금 잠시 이러한 알고리즘의 연산비용을 고려하지 말고 논리를 전개해가자
  - $f(\boldsymbol{x}+\boldsymbol{\epsilon})=f(\boldsymbol{x})+\boldsymbol{\epsilon}^{T} \nabla_{}{f(\boldsymbol{x})}+\displaystyle\frac{1}{2} \boldsymbol{\epsilon}^{T} \boldsymbol{H}\boldsymbol{\epsilon}+\mathcal{O}(\| \boldsymbol{\epsilon} \| ^{3})$
• $f$ 를 최소화 한다는 것은 $\nabla_{}{f}=0$ 을 만족시켜야 한다. 뉴턴의 근사법이 어떤 함수 $g$ 의 실근을 찾는 방법과 같으므로 $\nabla_{}{f}$ 에 대한 뉴턴 근사법을 시행하는 것과 같다.
  - 다변수함수인 이번 케이스에선 $\boldsymbol{\epsilon}$ 에 대하여 미분을 전개하면 $\nabla_{}{f(\boldsymbol{x})}+\boldsymbol{H}\boldsymbol{\epsilon}=0$ 그러므로 $\boldsymbol{\epsilon}=-\boldsymbol{H} ^{-1}\nabla_{}{f(\boldsymbol{x})}$ 이다
• 예제
  - $f(x)=cosh(cx)$ 라고 하자. 해석적으로, $x=0$ 에서 최솟값을 갖는다
  

from hashlib import new


c= torch.tensor(0.5)

def f(x):
    return torch.cosh(c * x)

def f_grad(x):
    return c * torch.sinh(c *x)

def f_hess(x):
    return c ** 2 * torch.cosh(c *x)

def newton(eta=1):
    x=10.0
    results= [x]
    for i in range(10):
        x -= eta * f_grad(x)/ f_hess(x)
        results.append(float(x))
    print('epoch 10,x',x)
    return results

show_trace(newton(),f)

• non-convex한 함수를 또 고려해보자
  - $f(x)=xcos(cx)$

c= torch.tensor(0.15 * np.pi)

def f(x):
    return  x * torch.cos(c *x)

def f_grad(x):
    return torch.cos(c*x) - c*x * torch.sin(c*x)

def f_hess(x):
    return -2 * c * torch.sin(c*x) -x * c **2 *torch.cos(c*x)

show_trace(newton(),f)

• 어떻게 하면 이 문제를 고칠 수 있을까? 그중 하나는 학습률을 바꾸는 것이다.

c= torch.tensor(0.15 * np.pi)

def f(x):
    return  x * torch.cos(c *x)

def f_grad(x):
    return torch.cos(c*x) - c*x * torch.sin(c*x)

def f_hess(x):
    return -2 * c * torch.sin(c*x) -x * c **2 *torch.cos(c*x)

show_trace(newton(0.5),f)

Preconditioning

• 전체 헤시안 행렬을 계산하는 것은 연산비용이 매우 높다. 이러한 이유로 다른 차선책이 개발되었는데, 그중 하나가 바로 preconditioning이다.
• 이는 Hessian 행렬 전체를 계산하는 대신 대각성분만을 계산하는 것이다
  - $\boldsymbol{x} \leftarrow \boldsymbol{x}-\eta \cdot diag(\boldsymbol{H}) ^{-1} \cdot \nabla_{}{f(\boldsymbol{x})}$
• 이는 당연히 전체 헤시안행렬을 계산하여 시행하는 뉴턴 근사법보다는 좋지 않지만, 그래도 꽤나 유용함을 보여준다.
• 게다가 각 변수들의 scale값이 마치 millimeter나 killometer로 표현하는 것과 같이 그 크기가 차이가 날수가 있는데, preconditioning이 이런 시케일 차로 발생하는 미스매치문제를 해결해준다

Stochastic Gradient Descent

• 딥러닝에서 손실함수는 전체 훈련 데이터셋에서 각 example에 대한 손실함수의 평균으로 정의되는 경우가 많다
• 훈련 데이터셋의 $n$ 개의 example에 대하여, $f _{i}(\boldsymbol{x})$ 가 이에 대응되는 손실함수라고 하였을때, 목적함수를 다음과 같이 계산하는 것이다
  - $f(\boldsymbol{x})=\displaystyle\frac{1}{n}\displaystyle\sum_{i=1}^{n}{f _{i}(\boldsymbol{x})}$
• 이때 목적함수의 gradient 또한 이렇게 계산된다
  - $\nabla_{}{f(\boldsymbol{x})}=\displaystyle\frac{1}{n}\displaystyle\sum_{i=1}^{n}{\nabla_{}{f _{i}(\boldsymbol{x})}}$
• 경사하강법이 사용된다면, 각 독립변수에 대하여 반복계산하므로 연산비용은 $\mathcal{O}(n)$ 이 될것이다.
  - 그러므로 훈련 데이터셋이 커지면 커질수록 경사하강법의 연산비용은 증가하는 것이다
• 확률적 경사하강법 SGD(Stochastic Gradient Descent)는 각 반복마다의 연산비용을 줄여준다. 각 gradient 계산마다 전체 데이터셋이 아닌 데이터셋에서 균등확률로 하나의 example만 뽑아 그것에 대한 gradient만을 계산한다. 그 결과 연산량을 $\mathcal{O}(1)$ 으로 줄인다
  - $\boldsymbol{x} \leftarrow \boldsymbol{x}-\eta \nabla_{}{f _{i}(\boldsymbol{x})}$
• 게다가 이 연산은 비편향 추정치unbiased estimate라는 특징을 가지고 있다
  - $\mathbb{E}(\nabla_{}{f _{i}(\boldsymbol{x})})=\displaystyle\frac{1}{n}\displaystyle\sum_{i=1}^{n}{\nabla_{}{f _{i}(\boldsymbol{x})}}=\nabla_{}{f(\boldsymbol{x})}$
• 파이썬 구현

import math 
import torch 
from d2l import torch as d2l 

def f(x1,x2):
    return x1 ** 2 + 2 * x2 ** 2 

def f_grad(x1,x2):
    return 2 * x1 , 4 * x2

def sgd(x1,x2,s1,s2,f_grad):
    g1,g2 = f_grad(x1,x2)
    #simulate noisy gradient
    g1 += torch.normal(0.0,1,(1,))
    g2 += torch.normal(0.0,1,(1,))
    eta_t= eta *lr()
    return (x1-eta_t *g1, x2-eta_t*g2,0,0)

def constant_lr():
    return 1 

eta=0.1
lr= constant_lr 
d2l.show_trace_2d(f,d2l.train_2d(sgd,steps=50,f_grad=f_grad))

• 그림에서 볼 수 있듯이, 확률경사하강법의 변수의 궤적은 기존 경사하강법보다 noisy하게 움직인다. 이는 우리가 최소값 인근에 있더라도, 불안정하게 계속 요동칠수 있다는 것이다
• 학습 횟수를 늘려도 그닥의 성능개선이 이루어지지 않기 때문에, 학습률 $\eta$ 를 낮출수도 있지만, 이 경우 초반에 유의미한 개선을 보이지 않게 된다. 만약 학습률이 지나치게 크다면 좋은 해를 얻기 어려워 질 것이다
• 이러한 연유로 최적화 과정에서 학습률을 지속적으로 변화시키는 방법, Dynamic Learning Rate가 도입되었다

Dynamic Learning Rate

• 학습을 상수가 아닌 시간의존의 함수 $\eta(t)$ 로 만듬으로써, 최적화 알고리즘이 수렴을 통제한다
• 우리는 학습률이 얼마나 빠르게 decay 되어야 하는지 알아야 한다. 너무 빠르게 decay되면 최적화의 과정이 설익게 되버리고, 또 지나치게 적게 decay되면 최적화에 많은 시간을 낭비하게 될것이다
• 다음과 같은 기초 전략들이 있다
  - piecewise constant : $\eta(t)=\eta _{i}$ $\text{if} \,\,t _{i} \le t \le t _{i+1}$
  - deep network를 학습시키는 기본적인 전략이다
  - exponential decay: $\eta(t)=\eta _{0} \cdot e^{-\lambda t}$
  - 좀 더 공격적으로 감소시키는 전략으로, 이 알고리즘은 때때로 알고리즘이 수렴하기 전에 멈춰버리는 문제가 발생한다
  - polynomial decay: $\eta(t)=\eta _{0}(\beta t+1) ^{-\alpha}$
  - 가장 널리 활용되는 방법으로 $\alpha=0.5$ 를 주로 쓴다. 이 경우 convex 알고리즘이 해당 비율에서 잘 작동well behaved한다는 여러 증명들이 있다
• 코드 구현

"""exponential decay"""
def exponential_lr():
    global t 
    t += 1
    return math.exp(-0.1 * t)

t= 1
lr= exponential_lr 
d2l.show_trace_2d(f,d2l.train_2d(sgd,steps=1000,f_grad=f_grad))

"""polynomial decay"""
def polynomial_lr(alpha=0.5) : 
    """Global variable that is defined outside this function
    and updated inside"""
    global t 
    t += 1 
    return (1+0.1 * t) ** (-alpha)

t=1 
lr= polynomial_lr 
d2l.show_trace_2d(f,d2l.train_2d(sgd,steps=50,f_grad=f_grad))

Convergence Analysis for Convex Objectives

• 목적함수 $f(\boldsymbol{\xi},\boldsymbol{x})$ 가 모든 $\boldsymbol{\xi}$ , 어떤 $\boldsymbol{x}$ 에서 볼록하다고 하자. 이때 확률경사하강 업데이트를 계산하자
  - $\boldsymbol{x}_{t+1}=\boldsymbol{x}-\eta _{t}\partial_{\boldsymbol{x}}f(\boldsymbol{\xi}_{t},\boldsymbol{x})$
  - 이때 $f(\boldsymbol{\xi}_{t},\boldsymbol{x})$ 는 각 훈련 example $\boldsymbol{\xi}_{t}$ 에 대한 목적함수이다.
  - $R(\boldsymbol{x})=E _{\boldsymbol{\xi}}[f(\boldsymbol{\xi},\boldsymbol{x})]$ 라고 표기하자. 이때 $\boldsymbol{x}^{*}$ minimizer 정의역 내에 존재한다고 가정하자.
  - $\| \boldsymbol{x}_{t+1}-\boldsymbol{x}^{*} \| ^{2}$
  - $=\| \boldsymbol{x}_{t}-\eta _{t}\partial_{\boldsymbol{x}}f(\boldsymbol{\xi}_{t},\boldsymbol{x})-\boldsymbol{x}^{*} \| ^{2}$
  1. $=\| \boldsymbol{x}_{t}-\boldsymbol{x}^{*} \| ^{2}+\eta _{t} ^{2}\| \partial_{\boldsymbol{x}}f(\boldsymbol{\xi},\boldsymbol{x}) ^{2} \|-2 \eta _{t}\langle {\boldsymbol{x}_{t}-\boldsymbol{x}^{*}},{\partial_{\boldsymbol{x}}f(\boldsymbol{\xi}_{t},\boldsymbol{x})} \rangle$
  - $\| \partial_{\boldsymbol{x}}f(\boldsymbol{\xi}_{t},\boldsymbol{x}) \| ^{2}$ 는 어떤 상수에 의해 유계되어있다고 가정하자
  2. $\eta _{t} ^{2}\| \partial_{\boldsymbol{x}}f(\boldsymbol{\xi}_{t},\boldsymbol{x}) \| ^{2} \le \eta _{t} ^{2}L ^{2}$
  - 우리의 관심사는 $\| \boldsymbol{x}_{t}-\boldsymbol{x}^{*} \| ^{2}$ 의 변화이다.
  - 다변수 convex함수는 다음의 성질을 갖고 있으므로 $f(\boldsymbol{y}) \ge f(\boldsymbol{x})+(\partial_{\boldsymbol{x}}f(\boldsymbol{x}))^{T}(\boldsymbol{y}-\boldsymbol{x})$
  3. $f(\boldsymbol{\xi}_{t},\boldsymbol{x}^{*})\ge f(\boldsymbol{\xi}_{t},\boldsymbol{x}_{t})+(\partial_{\boldsymbol{x}}{f(\boldsymbol{\xi}_{t},\boldsymbol{x}_{t})})^{T}(\boldsymbol{x}^{*}- \boldsymbol{x})$
  - 1,2,3번의 식을 종합하자,우선 1번과 2번식을 결합하면 다음과 같고,
  - $\| \boldsymbol{x}_{t+1}-\boldsymbol{x}^{*} \| ^{2} \le \| \boldsymbol{x}_{t}-\boldsymbol{x}^{*}\| ^{2}-2 \eta _{t}\langle {\boldsymbol{x}_{t}-\boldsymbol{x}^{*}},{\partial_{\boldsymbol{x}}}f(\boldsymbol{\xi}_{t},\boldsymbol{x}) \rangle+\eta _{t} ^{2}L ^{2}$
  - 2번과 3번을 결합한 식의 위치를 조정해주면 다음과 같다
  - $2 \eta _{t}\langle {\boldsymbol{x}_{t}-\boldsymbol{x}^{*}},{\partial_{\boldsymbol{x}}}f(\boldsymbol{\xi}_{t},\boldsymbol{x}) \rangle -\eta _{t} ^{2}L ^{2}\le \| \boldsymbol{x}_{t}-\boldsymbol{x}^{*}\| ^{2}-\| \boldsymbol{x}_{t+1}-\boldsymbol{x}^{*} \| ^{2}$
  - $2 \eta _{t}(f(\boldsymbol{\xi}_{t},\boldsymbol{x}_{t})-f(\boldsymbol{\xi}_{t},\boldsymbol{x}^{*}))-\eta _{t} ^{2} L ^{2}\le 2 \eta _{t}\langle {\boldsymbol{x}_{t}-\boldsymbol{x}^{*}},{\partial_{\boldsymbol{x}}}f(\boldsymbol{\xi}_{t},\boldsymbol{x}) \rangle -\eta _{t} ^{2}L ^{2}\le \| \boldsymbol{x}_{t}-\boldsymbol{x}^{*}\| ^{2}-\| \boldsymbol{x}_{t+1}-\boldsymbol{x}^{*} \| ^{2}$
  - $2 \eta _{t}(f(\boldsymbol{\xi}_{t},\boldsymbol{x}_{t})-f(\boldsymbol{\xi}_{t},\boldsymbol{x}^{*}))-\eta _{t} ^{2} L ^{2}\le \| \boldsymbol{x}_{t}-\boldsymbol{x}^{*}\| ^{2}-\| \boldsymbol{x}_{t+1}-\boldsymbol{x}^{*} \| ^{2}$
  - 이는 다음과 같고, 이는 현재 손실과 최적 손실사이에 $\eta _{t}L ^{2}/2$ 만큼의 차이가 있음을 의미한다
  - $E[\| \boldsymbol{x}_{t}-\boldsymbol{x}^{*} \| ^{2}]-E[\| \boldsymbol{x}_{t+1}-\boldsymbol{x}^{*} \|]\ge 2 \eta _{t}[E(R(\boldsymbol{x}_{t}))-R ^{*}]-\eta _{t} ^{2}L ^{2}$
  - $\eta _{t}$ 가 0으로 사라져야vanish 비로소 0으로 수렴할 수 있음을 보여준다
  - (후략 : 뒤에 내용이 더 있는데 복잡하여 나중에 다시한번 봐야 할듯)

Minibatch Stochastic Gradient Descent

• 정의
  - 미니배치 확률적 경사하강법이란 전체 데이터를 batch_size 개씩으로 나누어, batch_size 의 크기를 갖는 미니배치로 학습을 시행하는 방법이다
  - 예 : 전체 데이터셋이 1000개, batch_size=100 이라면 전체를 10묶음으로 하여, 1epoch당 10회의 경사하강법이 진행된다

배치와 CPU , GPU

• 배치란 GPU가 한번에 처리하는 데이터의 묶음을 의미한다

  CPU

  
• CPU의 구조
  - ALU: CPU의 연산을 담당한다
  - L1(Level1 cache memory) : CPU 코어 내 내장되어 CPU가 가장 빠르게 접근 가능한 메모리
  - L2(Level2 cache memory): L1캐시에서 원하는 데이터를 찾지 못하면 다음으로 찾는 메모리
  - L3(Level3 cache memory) : L2 메모리와 동일한 원리, 요즘 프로세서에선 대부분 L3 메모리를 달고 있지 않는다
  - Control: 명령을 해석하고 실행한다
  - Cache: 데이터를 담아둔다
• CPU 분류
  - 코어 :
• CPU는 명령어가 입력되는 순서대로 데이터를 처리하는 직렬처리 방식이다.
• "von Neumann Bottleneck" , 모든 계산의 결과는 반드시 ALU를 거쳐 메모리 어딘가의 저장되어야 한다는 구조이기 때문에 항상 한번의 하나의 연산만을 순차적으로 처리한다. 그러한 이유로 연산을 담당하는 ALU(Arithmetic Logic Unit) 개수가 적다
• 고정소수점 fixed point(부호 1비트, 정수부 15비트, 소수부 16비트로 소수부의 위치를 미리 지정해놓은 방식)을 잘 처리한다
• 예 : 1+2+3 연산
  - 다음과 같은 세개의 명령어 셋을 가지고 있는 마이크로프로세서가 있다고 하자
  - LDR: CPU 내부의 레지스터로 데이터 가져오기
  - STR: CPU 내부의 레지스터에서 메모리로 데이터 내보내기
  - ADD:두개의 레지스터의 데이터값을 더하여 다른 결과에 저장하기

LDR reg1, #1; // reg1 레지스터에 상수 1 로드 
LDR reg2, #2; // reg2 레지스터에 상수 2 로드
ADD reg1, reg2, reg3; // reg1 값과 reg2 값을 더해 reg3 에 저장
STR reg3, [0x00040222h]; // reg3 의 값을 0x00040222 메모리로 내보냄

GPU

• GPU는 병렬 연산을 위해 개발되었다. 캐시 메모리의 비중은 낮고, 연산을 수행하는 ALU의 갯수가 많다
  - 그래픽 처리를 할땐 빛과 관찰자 위치를 어떻게 가정하냐에 따라 발생하는 수많은 vector space conversion이 발생하고, 그에 따라 쉐이더,텍스쳐 연산과 픽셀 렌더링이 엄청나게 발생한다. 이 연산들은 엄청나게 많은 수의 부동소수점 곱셈 연산을 발생시키는데 이러한 연산을 처리하는데 특화되어졌다.
  - GPU는 서로 다른 명령어를 병렬적으로 처리하기 위해 설계되었기 때문에, 여러 명령을 동시 처리하는 병렬 처리방식에 특화되어 있다. 기존 CPU가 하나의 코어에 6~8개가 달리는 반면 GPU는 하나의 코어에 수백~수천개의 ALU가 장착되어 있다
  - AI추론과 학습에서 많이 활용되는 연산인 tensor contraction, matrix multiplication은 각 행과 열벡터의 내적 및 덧셈을 병렬로 처리할 수 있으므로, GPU에서 해당 연산이 CPU보다 훨씬 빠르다
  - 부동소수점floating point($\pm(1.\text{가수부})\times 2 ^{\text{지수부}-127}$ 로 부호 1비트, 지수 8비트, 가수 23비트를 활용한다)을 잘 처리한다.

CPU와 GPU 연산속도 비교

import time 
import numpy as np 
import torch 
from torch import nn 
from d2l import torch as d2l 

A= torch.zeros(256,256)
B= torch.randn(256,256)
C= torch.randn(256,256)

class Timer:
    """ Record multiple running times"""

    def __init__(self) -> None:
        self.times= [] 
        self.start() 
    
    def start(self):
        """start the timer"""
        self.tik= time.time() 

    def stop(self):
        """stop the timer and record the time in a list"""
        self.times.append(time.time()-self.tik)
        return self.times[-1]

    def avg(self):
        """ return the average time """
        return sum(self.times)/len(self.times)

    def sum(self):
        """return the sum of time"""
        return sum(self.times)

    def cumsum(self):
        """return the accumulated time"""
        return np.array(self.times).cumsum().tolist()
    

timer= Timer()

"""compute A=BC one element at a time """
timer.start() 
for i in range(256):
    for j in range(256):
        A[i,j]=torch.dot(B[i,:],C[:,j])

timer.stop()

"""result)
0.315291166305542
"""

# compute A=BC one column at a time 
timer.start()
for j in range(256):
    A[:,j] = torch.mv(B,C[:,j])

timer.stop()

""" result)
0.009061098098754883
"""

"""compute A=BC in one block """
timer.start() 
A= torch.mm(B,C)
timer.stop() 

gigaflops = [0.03/i for i in timer.times]
print(f'performance in Gigaflops: element{gigaflops[0]:.3f}',
      f'column {gigaflops[1]:.3f}, full{gigaflops[2]:.3f}')

"""result)
performance in Gigaflops: element0.095 column 3.311, full4.308
"""

미니배치

• 하나의 관측치로 학습시키는 방법은 많은 single matrix-vector multiplication을 야기한다. 이는 상당한 연산적 비용을 발생시킨다. 이는 네트워크가 훈련되는 도중에 평가할때, 파라미터를 업데이트하기 위하여 그레디언트를 계산할 때 모두 일어나는 일이다.
  - $\boldsymbol{g}_{t} \leftarrow \partial_{\displaystyle{\boldsymbol{w}}}f(\boldsymbol{x}_{t},\boldsymbol{w})$
• 미니배치를 활용하는것은 연산효율을 높이는 방법이다. 따라서 다음과 같이 식을 수정하자
  - $\boldsymbol{g}_{t} \leftarrow \displaystyle\frac{1}{|\mathcal{B}_{t}|}\partial_{\displaystyle{\boldsymbol{w}}}\displaystyle\sum_{\displaystyle{i \in \mathcal{B}_{t}}}^{}{f(\boldsymbol{x}_{i},\boldsymbol{w})}$
  - $\mathcal{B}_{t}$ 는 훈련 데이터셋에서 uniformly 추출된 원소들로 구성된 부분집합이다
  - 평균 gradient descent의 표준편차는 $(|\mathcal{B}_{t}|) ^{-1/2}$ 의 비율로 크기가 감소하게 됨으로써, 좀 더 안정화될 것이다.
  - 다만 $\mathcal{B}_{t}$ 의 크기를 키움으로서 줄어드는 표준편차에 비해, 연산량은 선형적으로 증가하기 때문에, GPU의 메모리를 고려한 적당한 미니배치사이즈를 결정하는 것이 중요하다

timer.start() 
for j in range(0,256,64):
    A[:,j:j+64] = torch.mm(B,C[:,j:j+64])
timer.stop()
print(f'performance in Gigaflops : block {0.03/timer.times[3]:.3f}')

"""result)
performance in Gigaflops : block 1.210
"""

Reading the Dataset

from operator import delitem
import numpy as np 
import time 

#@save
d2l.DATA_HUB['airfoil'] = (d2l.DATA_URL + 'airfoil_self_noise.dat',
                           '76e5be1548fd8222e5074cf0faae75edff8cf93f')

def get_data_ch11(batch_size=10, n=1500):
    data = np.genfromtxt(d2l.download('airfoil'),
                    dtype=np.float32,delimiter='\t')
    data = torch.from_numpy((data-data.mean(axis=0))/data.std(axis=0))
    data_iter= d2l.load_array((data[:n,:-1],data[:n,-1]),
                            batch_size,is_train=True)
    
    return data_iter, data.shape[1]-1


""" 
We add the status input `status` and place the 
hyperparameter in dictionary `hyperparams`
In addition we will average the loss of each minibatch example
in the training function, so the gradient in the optimization
algorithm does not need to be divided by the batch size
"""
def sgd(params, states, hyperparams):
    for p in params:
        p.data.sub_(hyperparams['lr']*p.grad)
        p.grad.data.zero_()

def train_ch11(trainer_fn, states, hyperparams, data_iter,
                feature_dim,num_epochs=2):
    
    """initialization"""
    w= torch.normal(mean=0.0, std= 0.01, size=(feature_dim,1),
                    requires_grad=True)
    b= torch.zeros((1),requires_grad=True)
    net, loss = lambda X: d2l.linreg(X,w,b), d2l.squared_loss 

    """train"""
    animator = d2l.Animator(xlabel='epoch',ylabel='loss',
                            xlim=[0,num_epochs],
                            ylim=[0.22,0.35])
    n,timer= 0, d2l.Timer() 
    
    for _ in range(num_epochs):
        for X, y in data_iter:
            l = loss(net(X),y).mean()
            l.backward()
            trainer_fn([w,b],states,hyperparams)
            n +=X.shape[0]
            if n % 200 == 0:
                timer.stop()
                animator.add(n/X.shape[0]/len(data_iter),
                            (d2l.evaluate_loss(net,data_iter,loss),))
                timer.start()
    
    print(f'loss: {animator.Y[0][-1]:.3f}, {timer.sum()/num_epochs:.3f} sec/epoch')
    return timer.cumsum(),animator.Y[0]

def train_sgd(lr,batch_size,num_epochs=2):
    data_iter, feature_dim= get_data_ch11(batch_size)
    return train_ch11 ( 
        sgd, None, {'lr':lr},data_iter,feature_dim,num_epochs)

gd_res=train_sgd(1,1500,10)

""" result) 
loss: 0.250, 0.005 sec/epoch
"""

sgd_res = train_sgd(0.005, 1)
""" result)
loss: 0.246, 0.151 sec/epoch
"""

-batch_size=1500으로 하였을 때
- 6번째 이후 유의미한 진전을 보이지 않는게 보여진다

• batch_size=1로 하였을때
  - 구현의 단순성을 위해 일정한 학습률을 사용하였다
  - 확률적 경사하강법은 example이 입력될때마다 갱신되는 모습을 보여준다
  - 한번의 epoch에 1500번의 업데이트가 시행된다
  - 위 아래 모두 한번의 epoch에 1500개의 example을 처리한것은 똑같으나, 확률경사하강법이 더 많은 시간이 소요되는 것을 볼 수 있다. 이는 확률경사하강법이 더 많은 파라미터 갱신횟수를 갖기 때문이다
  

• batch_size=100로 하였을 때

mini1_res = train_sgd(.4, 100)

"""result) 
loss: 0.243, 0.036 sec/epoch
"""

• batch_size=10로 하였을 때

mini2_res = train_sgd(.05, 10)

• 전체적 비교

d2l.set_figsize([6,3])
d2l.plot(*list(map(list,zip(gd_res,sgd_res,mini1_res,mini2_res))),
        'time(sec)',
        'loss',
        xlim=[1e-2,10],
        legend=['gd','sgd','batch_size=100','batch_size=10'])

d2l.plt.gca().set_xscale('log')