#!if top1 != null && 문서명1 == null
[DEPRECATED] top1 파라미터는 더 이상 사용되지 않습니다! 대신 문서명1 파라미터를 사용해 주세요.#!if top1 == null && 문서명1 != null
[[기계학습]]{{{#!if 문서명2 != null
, [[]]}}}{{{#!if 문서명3 != null
, [[]]}}}{{{#!if 문서명4 != null
, [[]]}}}{{{#!if 문서명5 != null
, [[]]}}}{{{#!if 문서명6 != null
, [[]]}}}| [[이론 컴퓨터 과학|'''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"]] | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36,#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 람다 대수 · 유형 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set) · 트리^레드-블랙 트리, B-트리, 힙, 피보나치 힙^ · 큐 · 스택 | ||||
| 수학적 최적화 | <keepall> 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| <keepall> 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| <keepall> 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성 | ||||
| <keepall> 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| <keepall> 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colkeepall><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · 바이오스 · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 함수형 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구 및 기타 논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영체제(멀티태스킹 · 프로세스 스케줄링 · 데드락 · 식사하는 철학자 문제 · 뮤텍스 · 세마포어 · 인터럽트) · 데이터베이스 · 컴퓨터 언어 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 어휘 분석 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 마크업 언어 · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크(네트워크 포트) · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템) · 난수생성
Gradient Descent
1. 개요
경사하강법은 영어로 Gradient Descent method 혹은 Gradient Descent Algorithm이며, 함수의 최솟값을 찾는 최적화 이론 기법이다.2. 상세
함수의 변화량[1]을 이용하여 계수를 조정하는 방식으로, 함수가 줄어드는 방향으로 계수를 계속 갱신해 나간다. 개발자는 함수가 한 번에 얼마나 줄어들게 하는지를 결정하는 패러미터를 정해야한다. 이 패러미터가 너무 작으면 최적화가 너무 오래 걸리고 너무 크면 최솟값을 지나칠 수 있다.비용함수의 최솟값을 찾아야 하는 '인공지능' 관련 학과 입학 질문 단골 메뉴이다.
경사하강법은 분명 '인공지능'의 기초를 이루는 방법이기는 하지만, 오늘날의 인공지능 분야는 경사하강법 만으로는 해결할 수 없는 문제를 다룬다. 최소한 관련 방법을 여러번 써야 해결 되는 문제를 다루는 편.
3. 역사
경사 하강법의 역사는 19세기까지 거슬러 올라가는데 초기 개념은 19세기 프랑스의 수학자 오귀스탱 루이 코시(Augustin-Louis Cauchy)가 제안되었다. 코시는 1847년에 발표한 「Méthodes générales pour la résolution des systèmes d’équations simultanées」에서 ‘최급강하법(Method of Steepest Descent)’이라는 개념을 소개하였다. 그 핵심은 함수의 값이 가장 빠르게 감소하는 방향, 즉 음의 기울기 방향으로 이동함으로써 함수의 최솟값을 찾을 수 있다는 내용으로 오늘날 경사 하강법의 가장 오래된 형태로 볼 수 있다.이론적으로는 유효했지만, 최급강하법은 실제 문제에 적용했을 때 수렴 속도가 느리거나 경로가 지그재그로 움직이는 등의 비효율성이 존재했다. 이를 보완하기 위해 20세기 초중반에는 다양한 방식의 경사 하강법이 개발되었다. 그중에서도 공액 경사법(Conjugate Gradient Method) 같은 알고리즘이 더 나은 수렴 특성을 보였지만 경사 하강법의 기본적인 골자는 바뀌지 않았다.
20세기 후반에 이르러 인공 신경망과 딥러닝이 주목받기 시작하면서, 경사 하강법은 다시금 핵심적인 최적화 기법으로 조명되었다. 신경망은 수많은 파라미터를 포함하고 있기 때문에 이 복잡한 모델을 학습시키는데 따르는 최적화 문제가 발생했고 이때 등장한 것이 역전파(Backpropagation) 알고리즘이다. 역전파는 신경망의 각 가중치에 대한 손실 함수의 기울기를 효율적으로 계산하는 방법을 보장했고, 이렇게 계산된 기울기를 이용해 경사 하강법으로 가중치를 조정하는 방식이 널리 퍼졌다.
이 과정에서 전체 데이터를 한꺼번에 사용하는 배치 경사 하강법(Batch Gradient Descent)의 한계가 드러났다. 대규모 데이터셋의 경우 모든 데이터를 매번 처리하는 데에 막대한 계산 자원이 필요했기 때문이다. 이를 극복하기 위해 개발된 것이 확률적 경사 하강법(Stochastic Gradient Descent, SGD)이다. SGD는 전체 데이터가 아닌 일부, 즉 미니배치(mini-batch)만을 사용하여 각 단계에서 기울기를 추정하고 가중치를 업데이트한다. 확률적 경사 하강법은 계산 효율성을 크게 높였으며 경우에 따라 더 빠르게 수렴하는 효과도 가져왔다.
최근에는 SGD의 한계를 보완하고자 다양한 변형 알고리즘들이 등장했다. 가령, 모멘텀(Momentum)은 이전 업데이트 방향을 고려하여 수렴 속도를 높이고 지역 최적점에서 벗어나는 데 도움을 준다. AdaGrad, RMSProp, Adam 등은 각 가중치마다 학습률을 적응적으로 조절하여 학습 효율성을 높이는 기법들이다. 특히 Adam은 현재 딥러닝 모델 학습에 있어 가장 널리 사용되는 최적화 알고리즘 중 하나로 자리매김하였다.
이처럼 경사 하강법은 19세기 코시가 처음 제안한 이래 여러가지 이론적 및 실용적 발전을 거쳐왔다. 초창기에는 단순한 이론적 개념에 불과했지만 컴퓨터 과학과 머신러닝의 발전, 특히 딥러닝 기술의 확산과 함께 실용적으로 적용가능한 범위가 날로 커져가고 있다.
4. 변형 알고리즘
4.1. 확률적 경사하강법(Stochastic Gradient Descent, SGD)
Mini Batch Gradient Descent라고도 한다.기존의 경사하강법은 가중치를 한 번 업데이트할 때 전체 학습 데이터를 전부 사용한다. 모든 데이터를 한꺼번에 집어넣고 각 데이터에 대한 gradient를 계산한 뒤, 그것들을 평균내 한 번에 모델을 갱신하는 방식이다. 하지만 이렇게 하면 데이터 양이 많아질수록 한 번에 처리하기가 어렵다.
그래서 등장한 것이 stochastic gradient descent, 줄여서 SGD인데 용어가 어려워 보이지만 까보면 데이터를 작은 단위인 batch로 나누어 경사하강법으로 학습하자는 단순한 아이디어다.
SGD는 전체 데이터를 사용하는 대신, 무작위로 골라낸 일부 데이터만 가지고 gradient를 계산하고 모델을 업데이트한다.
batch size만큼의 데이터만 사용해서 한 번씩 업데이트를 해 나가는 방식이다.
이렇게 하면 계산량이 줄고, 더 빠르게 학습을 진행할 수 있기 때문에 실제 머신러닝에서는 SGD를 널리 사용한다.
4.2. 모멘텀(Momentum)
Momentum 기법은 경사 하강법의 단점을 보완하기 위해 제안된 최적화 알고리즘으로 마치 언덕에서 공을 굴릴 때, 이전의 운동량을 이용하여 작은 턱이나 local minima를 넘어갈 수 있도록 하는 아이디어에서 착안했다. 단순히 현재 gradient 방향으로만 이동하는 것이 아니라 이전 업데이트 벡터의 일부를 현재 업데이트에 반영한다.심층 학습에서 SGD와 함께 다른 고급 최적화 알고리즘의 구성 요소로 널리 활용된다. Momentum을 적용하면 학습 과정이 더 안정적이고 부드러운 곡선을 나타내는 경향이 있다.
4.3. AdaGrad(Adaptive Gradient Algorithm)
AdaGrad는 각 패러미터(가중치)마다 개별적인, 적응적인 학습률을 적용하는 방법이다. 핵심 아이디어는 '지금까지 많이 변화한 패러미터는 학습률을 작게, 적게 변화한 패러미터는 학습률을 크게 조절하자'는 것인데 이를 위해 각 패러미터에 대해 이전까지의 모든 기울기(gradient) 제곱 값의 합을 누적하여 기록한다.학습률을 업데이트할 때는 이 누적된 값의 제곱근에 반비례하여 실제 학습률을 조정한다. 즉, 특정 패러미터의 기울기가 과거에 컸다면 해당 패러미터의 학습률은 점점 작아진다. 이는 데이터의 특성(feature)이 희소(sparse)할 때, 드물게 등장하는 특성에 대해서는 상대적으로 높은 학습률을 적용하여 더 효과적으로 학습할 수 있게 돕는다. 예를 들어, 자연어 처리에서 자주 등장하지 않는 단어 임베딩 벡터를 더 빠르게 학습시킬 수 있다.
하지만 결정적인 단점이 있는데 학습이 진행됨에 따라 기울기 제곱의 합이 계속 커지기 때문에 학습률이 단조적으로 감소하여 결국 [math(0)]에 수렴하게 되고 학습이 너무 일찍 멈출 수 있다는 점이다. 분모에 작은 값 [math(\epsilon)]을 더해 [math(0)]으로 나누는 것을 방지한다.
[math(g_t = \nabla_\theta J(\theta_t))]
[math(G_t = G_{t-1} + g_t \odot g_t)]
[math(\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot g_t)]
(여기서 [math(G_t)]는 시간 [math(t)]까지의 기울기 제곱의 누적 합, [math(\eta)]는 기본 학습률, [math(\odot)]는 요소별 곱셈이다.)
4.4. RMSProp(Root Mean Square Propagation)
RMSProp은 AdaGrad의 학습률이 너무 빠르게 감소하여 학습이 조기에 중단되는 문제를 해결하기 위해 제안되었다. 제프리 힌튼(Geoffrey Hinton)이 2012년 Coursera 강의에서 처음 제시한 방법으로 AdaGrad처럼 기울기 제곱 값을 사용하지만 무한정 누적하는 대신 지수 이동 평균(Exponential Moving Average, EMA)을 사용한다. 과거의 모든 기울기 제곱 값을 동일하게 반영하되 대신 최근의 기울기 정보에 더 높은 가중치를 부여하고 오래된 정보는 점차 잊어버리는 것이다. 이를 위해 감쇠율(decay rate) [math(\gamma)] (또는 [math(\beta)]) 하이퍼패러미터를 도입하여, 현재 스텝의 기울기 제곱과 이전 스텝까지의 이동 평균값을 가중 평균한다.이렇게 계산된 지수 이동 평균의 제곱근으로 학습률을 나누어 적용한다. 이 방식 덕분에 분모가 되는 기울기 제곱의 평균값이 무한정 커지지 않아 학습률이 [math(0)]으로 급격히 수렴하는 것을 방지하고, 학습 과정을 더 오랫동안 안정적으로 유지할 수 있다. RMSProp은 특히 불안정한 목적 함수(objective function)나 순환 신경망(RNN)과 같이 시간에 따라 동적으로 변하는 환경에서 좋은 성능을 보이는 것으로 알려져 있다.
[math(g_t = \nabla_\theta J(\theta_t))]
[math(E[g^2]t = \gamma E[g^2]{t-1} + (1-\gamma) g_t^2)]
[math(\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}} g_t)]
(여기서 [math(E[g^2]_t)]는 시간 [math(t)]까지의 기울기 제곱의 지수 이동 평균, [math(\gamma)]는 감쇠율이다.)
4.5. Adam(Adaptive Moment Estimation)
Adam은 현재 가장 널리 사용되는 최적화 알고리즘 중 하나로 RMSProp과 모멘텀(Momentum) 최적화 기법의 장점을 결합한 방식이다.Adam은 각 패러미터마다 적응적인 학습률을 계산한다는 점에서 RMSProp과 유사하지만 두 가지 중요한 차이점이 있다. 첫째는 기울기의 제곱 값에 대한 지수 이동 평균([math(v_t)], 2차 모멘트 추정치)뿐만 아니라, 기울기 자체에 대한 지수 이동 평균([math(m_t)], 1차 모멘트 추정치)도 함께 유지한다는 것이다. [math(m_t)]는 모멘텀처럼 기울기의 방향과 크기를 고려하여 파라미터 업데이트 방향을 부드럽게 하고 수렴 속도를 높이는 역할을 한다.
둘째는 학습 초기에 [math(m_t)]와 [math(v_t)]가 [math(0)]으로 초기화되어 편향(bias)되는 문제를 해결하기 위해 편향 보정(bias correction) 단계를 포함한다. 처음 몇 스텝 동안 계산된 이동 평균값들을 보정하여 초반에도 안정적인 학습이 가능하도록 한다. Adam은 일반적으로 하이퍼파라미터 [math(\beta_1)] (1차 모멘트 감쇠율), [math(\beta_2)] (2차 모멘트 감쇠율), [math(\epsilon)] (0으로 나누기 방지)에 덜 민감하며, 다양한 종류의 딥러닝 모델에서 빠르고 안정적인 수렴 성능을 보여주어 기본 옵티마이저로 많이 채택된다.
[math(g_t = \nabla_\theta J(\theta_t))]
[math(m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t \quad \text{(1st moment estimate)})]
[math(v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2 \quad \text{(2nd moment estimate)})]
[math(\hat{m}_t = \frac{m_t}{1-\beta_1^t} \quad \text{(Bias-corrected 1st moment)})]
[math(\hat{v}t = \frac{v_t}{1-\beta_2^t} \quad \text{(Bias-corrected 2nd moment)})]
[math(\theta{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t)]
(여기서 [math(\beta_1)], [math(\beta_2)]는 각 모멘트 추정치의 감쇠율이다.)