확률 계단 하강법의 이론 입문(증명편)
이 보도는 확률 계단 하강법의 이론 입문의 정리 증명편이다.
정리를 증명하다
매개 변수 $w$의 데이터 $(x_i, y_i) $의 손실 함수는 $l_i(w)$.
손실 함수 데이터 분포의 기대치 $L(w) =\mathbb{E}_{x_i, y_i}(l_i(w))$를 범용 오차라고 합니다.
$l_i(w)$가 $a-$플랫 볼록 함수이고 비음손실 함수일 때,\mathbb{E}[L(\overline{w})]\leq \frac{1}{1-\eta a}(L(w^*) + \frac{{w^*}^2}{2\eta T}) \tag{1}
사용자 정의 모양새를 정의합니다.
이 정리는 SGD에서 얻은 매개 변수 $\overline {w}$의 범용 오차와 가장 좋은 매개 변수를 사용하는 범용 오차에 대한 평가입니다.
이 항목은 이 점을 증명하고자 한다.
준비
철함수와 평활함수의 정의를 다시 한 번 소개하고 그 성질을 소개한다.
볼록 함수
볼록 함수는 도표의 2점 선을 그릴 때 도표 아래에 나타나는 함수를 가리킨다.
볼록 함수 예
위의 예에서 도표의 2시에 녹색 선을 그리면 파란색 도표는 반드시 떨어진다.
볼록 함수 정의
関数fが凸関数であるとは，
f上の２点(x,f(x)), (y, f(y))と，\\
それらの間の点(tx + (1-t)y), f(tx + (1-t)y)) について，\\
f(tx + (1-t)y) \leq tf(x) + (1-t)f(y) が成立することです．
철 함수 성질 1
$f$가 미분철 함수일 때, 사다리 $f'(w)$, 모든 $w^*$에 대해f(w) - f(w^*) \leq f'(w)（w-w^*） \tag{2}
사용자 정의 모양새를 정의합니다.
(증명)
미분과 평균 변화율의 정의를 보면 알 수 있다.
볼록 함수의 경우 사다리가 단조롭게 증가하고\frac{f(w) - f(w^*)}{w-w^*} \leq f'(w) \ \ \ (w^* < w のとき)
이 색상은 색상이 바래집니다.
철 함수 성질 2
손실 함수 $l_i$가 볼록 함수일 경우 $w_i$와 $\overline{w}=\frac{\sum_{i=1}^Tw_i}{T}$,L(\overline{w}) \leq \frac{1}{T}\sum_i{L(w_i)} \tag{3}
사용자 정의 모양새를 정의합니다.
(증명)
$l_i$는 돌출 함수입니다.l_i(\overline{w}) \leq \frac{1}{T}\sum_i{l_i(w_i)}
양쪽을 $x_로 설정i,y_i$에 대한 기대치를 얻으면 필요한 표현식을 얻을 수 있습니다. (증명 끝)
이 공식에 따르면 SGD의 각 $w_i$를 사용하는 것보다 평균 $\overline {w}$를 사용하는 것이 기대치에 더 좋습니다.
매끄러운 함수
이번에 고려한 제곱 손실의 함수는 평활성과 양호한 성질을 가지고 있다.
부드러운 함수 정의
微分可能な関数f(w)がa-平滑関数であるとは， \\
|f'(w) - f'(u)|\leq a|w-u| \ が成立することです．
평활함수의 성질
미분 가능 함수 f(w)가 a-평활 함수일 때,f(v)\leq f(w) + (v-w)f'(w) + \frac{a}{2} (v-w)^2
사용자 정의 모양새를 정의합니다.
(증명)
매끄러운 함수의 성질을 사용하기 위해 $f'(w+t(v-w)-f'(w)$를 평가합니다. 단, $t\in[0,1]$.f'(w+t(v-w))-f'(w) \leq |f'(w+t(v-w))-f'(w)| \\
\leq a|w+t(v-w))-w| = at|v-w|
첫 번째 줄부터 두 번째 줄까지 부드러운 함수의 성질을 사용했다.
양쪽에서 $t$에 대해 [0,1] 포인트를 사용합니다.\int_{[0,1]}(f'(w+t(v-w))-f'(w))dt \leq \int_{[0,1]} at|v-w|dt
우선, 오른쪽은,\int_{[0,1]}at|v-w| dt = \frac{a}{2}|v-w|
다음 왼쪽은,\int_{[0,1]}(f'(w+t(v-w))-f'(w)) dt = \frac{f(v) - f(w)}{v-w}-f'(w)
만약 네가 그것들을 대입한다면,\frac{f(v) - f(w)}{v-w}-f'(w) \leq \frac{a}{2}|v-w|
$v>w$시와 $v비음평활 함수의 성질
$f$가 마이너스가 아니라고 가정합니다. 상기 공식에서 $v=w-\frac{1}{a}f'(w)$,f(v)\leq f(w) + (- \frac{1}{a}f'(w))f'(w) + \frac{a}{2} (- \frac{1}{a}f'(w))^2 \\
= f(w) - \frac{1}{2a} (f'(w))^2 \\
(f'(w))^2 \leq 2a(f(w) - f(v)) \leq 2af(w) \tag{4}
마지막 부등식에서 $f$는 마이너스가 아닙니다.
SGD
SGD의 알고리즘을 다시 나열합니다. $\eta$ 설정 $w_1=0달러로 초기화 단계 $i=1,2,\dots,T$다음 단계 반복 $(x_i, y_i)$견본 $w_{i+1} = w_i -\eta l_i'{(w_i)}$로 업데이트 $\overline{w}=\frac{\sum_iw_i}{T}$출력 SGD의 특성
(SGD에만 해당되지 않음) 매개변수는 다음과 같이 업데이트됩니다.w_1=0, w_{i+1} = w_{i} - \eta v_{i}
이 때, 모든 $w^*$,\sum_{i=1}^T (w_i-w^*)i_t \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |v_i|^2
특히 SGD의 경우 $v_i=l'(w_i)$,\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
사용자 정의 모양새를 정의합니다.
(증명)
현재의 절차와 앞의 절차의 제곱차 $(w_{i+1}-w^*)^2-(w_i-w^*)^2$를 비교하는 것이 증명의 요점이다.
표현식 업데이트 $w_{i+1} = w_i -\eta v_{i}$를 사용할 수 있습니다.(w_{i+1}-w^*)^2-(w_i-w^*)^2 = (w_i - \eta v_{i}-w^*)^2-(w_i-w^*)^2 \\
= -2\eta v_{i}(w_i-w^*) + (\eta v_{i})^2
양쪽 $i$의 합계에 관하여.(w_{T+1}-w^*)^2-(w_1-w^*)^2 = -2\eta \sum_{i=1}^T v_{i}(w_i-w^*) + \sum_{i=1}^T (\eta v_{i})^2
이항 평가,2\eta \sum_{i=1}^T v_{i}(w_i-w^*) \leq -(w_{T+1}-w^*)^2+(w_1-w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 \\
\leq (w_1-w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 \\
\leq (w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2
마지막으로, $w_1=0달러입니다. 양쪽을 $2\eta$로 나누면 필요한 공식을 얻을 수 있습니다. (증명 끝)
정리적 증명
지금까지 나타난 철함수의 성질, 평활함수의 성질, SGD의 성질을 모두 조합하면 목적식(1)을 증명할 수 있다.
(1)의 증명)
먼저 SGD의 성질을 $(5)$로 사용합니다.\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
왼쪽의 $(w_i-w^*)l'(w_i)$를 참고하십시오. 볼록 함수의 성질은 $(2)$입니다.\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2
오른쪽에 있는 $｜l'(w_i)｜^2$를 주의하십시오. 비음평활 함수의 성질은 $(4)$입니다.\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T (2a)l(w_i) \\
= \frac{|w^*|^2}{2\eta} + \eta a \sum_{i=1}^T l(w_i)
이항 정리.(1-\eta a)\sum_{i=1}^T l_i(w_i) \leq
\sum_{i=1}^T l_i(w^*) + \frac{|w^*|^2}{2\eta}
양쪽을 $T$로 나눈다.(1-\eta a)\frac{\sum_{i=1}^T l_i(w_i)}{T} \leq
\frac{\sum_{i=1}^T l_i(w^*)}{ T } + \frac{|w^*|^2}{2\eta T}
양쪽의 기대치를 가져옵니다. $\sum_{i=1}^T l_i(w^*)=TL(w^*)$.(1-\eta a)\frac{\sum_{i=1}^T L(w_i)}{T} \leq
\frac{TL(w^*)}{ T } + \frac{|w^*|^2}{2\eta T} = L(w^*) + \frac{|w^*|^2}{2\eta T}
마지막으로 볼록 함수의 성질 $(3)L (\overline{w})\leq\frac{1}{T}\sum_i{L(w_i)}$를 왼쪽에 적용합니다.(1-\eta a)L(\overline{w}) \leq L(w^*) + \frac{|w^*|^2}{2\eta T}
양쪽을 $1-\eta$로 계산하면 필요한 공식을 얻을 수 있습니다. 수고하셨습니다!
총결산
확률 계단법은 매우 깊은 이론을 가지고 그 유효성은 지금까지도 연구 중이다. (가장 간단한 예라도 상당히 어렵다.)
이번에는 간단하게 보기 위해 매개 변수 $w$를 1차원으로 설정하였으나, 다차원 매개 변수의 경우에도 완전히 성립되었다.
마지막으로 참고 문헌을 열거하다.
스즈키 대자《확률의 최적화》
화책이지만 다소 일반적이고 형식적인 글쓰기를 사용하기 때문에 초보자에게는 어려울 수 있다.
S. Shalev-Shwartz, S. Ben-David 『Understanding Machine Learning: From Theory to Algorithms』
서양책이지만 내용 자체는 초보자도 이해하기 쉽다.
U-TOKYO AP Advent Calendar 2018은 계속됩니다!
Reference
이 문제에 관하여(확률 계단 하강법의 이론 입문(증명편)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/snowhork/items/71cf59028728ec21458b
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
\mathbb{E}[L(\overline{w})]\leq \frac{1}{1-\eta a}(L(w^*) + \frac{{w^*}^2}{2\eta T}) \tag{1}
철함수와 평활함수의 정의를 다시 한 번 소개하고 그 성질을 소개한다.
볼록 함수
볼록 함수는 도표의 2점 선을 그릴 때 도표 아래에 나타나는 함수를 가리킨다.
볼록 함수 예
위의 예에서 도표의 2시에 녹색 선을 그리면 파란색 도표는 반드시 떨어진다.
볼록 함수 정의
関数fが凸関数であるとは，
f上の２点(x,f(x)), (y, f(y))と，\\
それらの間の点(tx + (1-t)y), f(tx + (1-t)y)) について，\\
f(tx + (1-t)y) \leq tf(x) + (1-t)f(y) が成立することです．
철 함수 성질 1
$f$가 미분철 함수일 때, 사다리 $f'(w)$, 모든 $w^*$에 대해
f(w) - f(w^*) \leq f'(w)（w-w^*） \tag{2}
(증명)
미분과 평균 변화율의 정의를 보면 알 수 있다.
볼록 함수의 경우 사다리가 단조롭게 증가하고
\frac{f(w) - f(w^*)}{w-w^*} \leq f'(w) \ \ \ (w^* < w のとき)
철 함수 성질 2
손실 함수 $l_i$가 볼록 함수일 경우 $w_i$와 $\overline{w}=\frac{\sum_{i=1}^Tw_i}{T}$,
L(\overline{w}) \leq \frac{1}{T}\sum_i{L(w_i)} \tag{3}
(증명)
$l_i$는 돌출 함수입니다.
l_i(\overline{w}) \leq \frac{1}{T}\sum_i{l_i(w_i)}
이 공식에 따르면 SGD의 각 $w_i$를 사용하는 것보다 평균 $\overline {w}$를 사용하는 것이 기대치에 더 좋습니다.
매끄러운 함수
이번에 고려한 제곱 손실의 함수는 평활성과 양호한 성질을 가지고 있다.
부드러운 함수 정의
微分可能な関数f(w)がa-平滑関数であるとは， \\
|f'(w) - f'(u)|\leq a|w-u| \ が成立することです．
평활함수의 성질
미분 가능 함수 f(w)가 a-평활 함수일 때,
f(v)\leq f(w) + (v-w)f'(w) + \frac{a}{2} (v-w)^2
(증명)
매끄러운 함수의 성질을 사용하기 위해 $f'(w+t(v-w)-f'(w)$를 평가합니다. 단, $t\in[0,1]$.
f'(w+t(v-w))-f'(w) \leq |f'(w+t(v-w))-f'(w)| \\
\leq a|w+t(v-w))-w| = at|v-w|
양쪽에서 $t$에 대해 [0,1] 포인트를 사용합니다.
\int_{[0,1]}(f'(w+t(v-w))-f'(w))dt \leq \int_{[0,1]} at|v-w|dt
\int_{[0,1]}at|v-w| dt = \frac{a}{2}|v-w|
\int_{[0,1]}(f'(w+t(v-w))-f'(w)) dt = \frac{f(v) - f(w)}{v-w}-f'(w)
\frac{f(v) - f(w)}{v-w}-f'(w) \leq \frac{a}{2}|v-w|
비음평활 함수의 성질
$f$가 마이너스가 아니라고 가정합니다. 상기 공식에서 $v=w-\frac{1}{a}f'(w)$,
f(v)\leq f(w) + (- \frac{1}{a}f'(w))f'(w) + \frac{a}{2} (- \frac{1}{a}f'(w))^2 \\
= f(w) - \frac{1}{2a} (f'(w))^2 \\
(f'(w))^2 \leq 2a(f(w) - f(v)) \leq 2af(w) \tag{4}
SGD
SGD의 알고리즘을 다시 나열합니다.
SGD의 특성
(SGD에만 해당되지 않음) 매개변수는 다음과 같이 업데이트됩니다.
w_1=0, w_{i+1} = w_{i} - \eta v_{i}
\sum_{i=1}^T (w_i-w^*)i_t \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |v_i|^2
\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
(증명)
현재의 절차와 앞의 절차의 제곱차 $(w_{i+1}-w^*)^2-(w_i-w^*)^2$를 비교하는 것이 증명의 요점이다.
표현식 업데이트 $w_{i+1} = w_i -\eta v_{i}$를 사용할 수 있습니다.
(w_{i+1}-w^*)^2-(w_i-w^*)^2 = (w_i - \eta v_{i}-w^*)^2-(w_i-w^*)^2 \\
= -2\eta v_{i}(w_i-w^*) + (\eta v_{i})^2
(w_{T+1}-w^*)^2-(w_1-w^*)^2 = -2\eta \sum_{i=1}^T v_{i}(w_i-w^*) + \sum_{i=1}^T (\eta v_{i})^2
2\eta \sum_{i=1}^T v_{i}(w_i-w^*) \leq -(w_{T+1}-w^*)^2+(w_1-w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 \\
\leq (w_1-w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 \\
\leq (w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2
정리적 증명
지금까지 나타난 철함수의 성질, 평활함수의 성질, SGD의 성질을 모두 조합하면 목적식(1)을 증명할 수 있다.
(1)의 증명)
먼저 SGD의 성질을 $(5)$로 사용합니다.\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
왼쪽의 $(w_i-w^*)l'(w_i)$를 참고하십시오. 볼록 함수의 성질은 $(2)$입니다.\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2
오른쪽에 있는 $｜l'(w_i)｜^2$를 주의하십시오. 비음평활 함수의 성질은 $(4)$입니다.\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T (2a)l(w_i) \\
= \frac{|w^*|^2}{2\eta} + \eta a \sum_{i=1}^T l(w_i)
이항 정리.(1-\eta a)\sum_{i=1}^T l_i(w_i) \leq
\sum_{i=1}^T l_i(w^*) + \frac{|w^*|^2}{2\eta}
양쪽을 $T$로 나눈다.(1-\eta a)\frac{\sum_{i=1}^T l_i(w_i)}{T} \leq
\frac{\sum_{i=1}^T l_i(w^*)}{ T } + \frac{|w^*|^2}{2\eta T}
양쪽의 기대치를 가져옵니다. $\sum_{i=1}^T l_i(w^*)=TL(w^*)$.(1-\eta a)\frac{\sum_{i=1}^T L(w_i)}{T} \leq
\frac{TL(w^*)}{ T } + \frac{|w^*|^2}{2\eta T} = L(w^*) + \frac{|w^*|^2}{2\eta T}
마지막으로 볼록 함수의 성질 $(3)L (\overline{w})\leq\frac{1}{T}\sum_i{L(w_i)}$를 왼쪽에 적용합니다.(1-\eta a)L(\overline{w}) \leq L(w^*) + \frac{|w^*|^2}{2\eta T}
양쪽을 $1-\eta$로 계산하면 필요한 공식을 얻을 수 있습니다. 수고하셨습니다!
총결산
확률 계단법은 매우 깊은 이론을 가지고 그 유효성은 지금까지도 연구 중이다. (가장 간단한 예라도 상당히 어렵다.)
이번에는 간단하게 보기 위해 매개 변수 $w$를 1차원으로 설정하였으나, 다차원 매개 변수의 경우에도 완전히 성립되었다.
마지막으로 참고 문헌을 열거하다.
스즈키 대자《확률의 최적화》
화책이지만 다소 일반적이고 형식적인 글쓰기를 사용하기 때문에 초보자에게는 어려울 수 있다.
S. Shalev-Shwartz, S. Ben-David 『Understanding Machine Learning: From Theory to Algorithms』
서양책이지만 내용 자체는 초보자도 이해하기 쉽다.
U-TOKYO AP Advent Calendar 2018은 계속됩니다!
\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2
\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T (2a)l(w_i) \\
= \frac{|w^*|^2}{2\eta} + \eta a \sum_{i=1}^T l(w_i)
(1-\eta a)\sum_{i=1}^T l_i(w_i) \leq
\sum_{i=1}^T l_i(w^*) + \frac{|w^*|^2}{2\eta}
(1-\eta a)\frac{\sum_{i=1}^T l_i(w_i)}{T} \leq
\frac{\sum_{i=1}^T l_i(w^*)}{ T } + \frac{|w^*|^2}{2\eta T}
(1-\eta a)\frac{\sum_{i=1}^T L(w_i)}{T} \leq
\frac{TL(w^*)}{ T } + \frac{|w^*|^2}{2\eta T} = L(w^*) + \frac{|w^*|^2}{2\eta T}
(1-\eta a)L(\overline{w}) \leq L(w^*) + \frac{|w^*|^2}{2\eta T}
확률 계단법은 매우 깊은 이론을 가지고 그 유효성은 지금까지도 연구 중이다. (가장 간단한 예라도 상당히 어렵다.)
이번에는 간단하게 보기 위해 매개 변수 $w$를 1차원으로 설정하였으나, 다차원 매개 변수의 경우에도 완전히 성립되었다.
마지막으로 참고 문헌을 열거하다.
스즈키 대자《확률의 최적화》
화책이지만 다소 일반적이고 형식적인 글쓰기를 사용하기 때문에 초보자에게는 어려울 수 있다.
S. Shalev-Shwartz, S. Ben-David 『Understanding Machine Learning: From Theory to Algorithms』
서양책이지만 내용 자체는 초보자도 이해하기 쉽다.
U-TOKYO AP Advent Calendar 2018은 계속됩니다!
Reference
이 문제에 관하여(확률 계단 하강법의 이론 입문(증명편)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/snowhork/items/71cf59028728ec21458b텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
