An overview of gradient descent optimization algorithms


제목: An overview of gradient descent optimization algorithms

저자: Sebastian Ruder
출처: Insight Centre for Data Analytics, Aylien Ltd.
원문: https://arxiv.org/abs/1609.04747 (pdf: https://arxiv.org/pdf/1609.04747.pdf)
일시: 2017.06.15

요약
  기계학습에서 온라인 최적화 방식에 대한 간략 리뷰 및 비교

Paper Abstract
 Gradient descent optimization algorithms, while increasingly popular, are often used as black-box optimizers, as practical explanations of their strengths and weaknesses are hard to come by. This article aims to provide the reader with intuitions with regard to the behaviour of different algorithms that will allow her to put them to use. In the course of this overview, we look at different variants of gradient descent, summarize challenges, introduce the most common optimization algorithms, review architectures in a parallel and distributed setting, and investigate additional strategies for optimizing gradient descent.


생각
   인공지능 AI의 부상으로 기계학습 machine learning, 특히 딥러닝 deep learning에 대한 관심도 높아졌고 공부하려는 사람들이 많아졌습니다. 단순 관심의 수준을 넘어서 딥러닝 알고리즘을 공부하고 구현해서 실제 문제에 적용하려는 분들도 많습니다. 딥러닝을 마스터하기 위해서 넘어야하는 허들이 많이 있지만, 궁극적으로 가장 난관은 학습모델을 어떻게 최적화할 것이냐입니다. 딥러닝을 다루는 많은 연성의 자료들이 이런 저런 수박 겉핥기 식의 내용만 다뤄지는 현실이 이 분야에서 그래도 공부 좀 했던 사람으로서 미안함을 많이 느낍니다. howerver, 짧지만 개괄적으로 최적화 알고리즘을 다룬 논문이 있어서 소개합니다.

 Genetic algorithm이나 Simulated annealing 등과 evolutionary 최적화 방식도 존재하지만, 머신러닝 커뮤니티에서 가장 많이 적용하는 수학적 최적화 방식은 gradient에 기반한 것입니다. 최적식 또는 loss 함수의 기울기 (미분) 반대방향으로 모델 파라메터를 조정해가는 방식이라 보면 됩니다. 가장 기초적으로 batch gradient descent가 있는데 이는 많은 양의 학습 데이터를 한꺼번에 사용해서 최적화합니다. 많은/모든 데이터를 함께 사용하기 때문에 글로벌 옵티마를 찾을 가능성이 있지만 많은 학습데이터로 학습속도가 느립니다. 글로벌 옵티마의 가능성은 있지만 역설적이게도 배치 방식은 로멀 옵티마에 빠질 가능성이 매우 높습니다. 그래서 새로운 학습 데이터가 생길 때마다 온라인으로 모델 파라메터를 조정하는 stochastic gradient descent (SGD) 방식을 실제 학습에서 많이 사용합니다. 온라인 방식이어서 최신 데이터를 모델에 바로 반영할 수 있고, stochastic의 속성상 로컬 옵티마에서 빠져나올 가능성이 배치보다 높습니다. 하지만, 신규 학습 데이터에 따라서 모델 파라메터가 계속 바뀌므로 불안정하고 전체 데이터 스페이스를 조망하지 못하는 단점이 있습니다. 그래서 이 둘의 장점을 합쳐서 일정수의 작은 합습데이터 세트로 쪼개서 (또는 모아서) 학습하는 mini-batch gradient descent가 일반적입니다.

 Gradient 방식을 현실 문제에 적용할 때 학습비율 learning rate, 학습 스케쥴 등을 정하는 문제를 해결하기 위해서 Momentum, Nesterov accelerated graident, AdaGrad, AdaDelta, RMSprp, Adam, AdaMax, Nadam 등의 방식이 최근 많이 소개돼고 있습니다. 요는 모델 학습에서 하이퍼 파라메터 hyper parameter (모델 파라메터 외에 모델을 학습하는데 필요한 파라메터)를 어떻게 더 쉽게 또는 자동으로 정해줄 것인가 그래서 빠르고 안정적인 최적화를 이룰 것인가 등을 해결한 방식입니다. 개별 알고리즘에 대한 자세한 설명은 논문 참조... 처음에는 잘 읽히지 않을 수도 있지만, 몇 번 읽고 관련 참고 자료를 함께 보다보면 수식이나 방식이 눈에 들어올 겁니다.


'Paper' 카테고리의 다른 글

Feature Hashing for Large Scale Multitask Learning  (0) 2017.09.10

Feature Hashing for Large Scale Multitask Learning


제목: Feature Hashing for Large Scale Multitask Learning

저자: Weinberger et al.
출처: Yahoo! Research
원문: https://arxiv.org/pdf/0902.2206.pdf
일시: 2010.02.27

요약
Hashing trick을 소개하고, multi-task learning에 적용함

Paper Abstract. 
Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case — multitask learning with hundreds of thousands of tasks.

생각
 원래는 지금 하고 있는 업무 때문에 Hashing Trick이 세부 내용을 확인하기 위해서 다시 읽었지만, 해싱트릭의 기본은 매우 간단하고 중간에 나열한 여러 속성이나 증명은 굳이 더 자세히 알 필요가 없지만 (수식과 이론을 바탕으로 새로운 이론을 도출해서 논문을 쓸 계획이 없기 때문에), 후반부 (Application)에 소개된 Multitask learning에 적용한 부분에서 현재 팀내에서 진행하는 다른 업무에 도움이 될 인사이트를 얻었기 때문에 이 논문을 소개합니다.

 해싱트릭 Hashing Trick은 이름에서 유추할 수 있듯이 해싱과 트릭으로 나눠서 생각할 수 있다. 먼저 해싱은 보통 y = f(x), 즉 인풋 x를 넣으면 아웃풋 y가 나오는 함수로 생각하면 된다. 우리의 관념에서 1:1 매핑의 아름다운 함수를 기대하지만, 보통 해싱함수는 N:1의 형태를 띈다. 그래서 abstract에 언급됐듯이 dimension reduction이 가능하다. 해싱을 사용하면 N차원의 데이터를 d차원 (d << N)의 데이터로 축소한다고 보면 된다. 이런 N:1 함수의 문제점은 다수의 원 데이터가 하나의 (또는 작은 수의) bin으로 매핑돼서 충돌이 발생할 가능성이 있다. 그럼에도 불구하고 차원을 축소함으로써 얻는 이득이 많기 때문에 해싱이 (computationally) 효과적이다. 해싱충돌 (collision)을 최소화하는 차원 d나 해싱함수를 선택하는 것이 중요하고, 때로는 다수의 해싱을 사용해서 충돌을 최대한 방어할 수도 있다. 보통 수십만에서 수천만 이상의 데이터를 수백, 수천 차원으로 줄이기 때문에 2~3개 이상의 해싱을 사용하면 충돌을 거의 막으면서 원래 데이터의 속성을 유지할 수있다.

 두번째로 trick은 흔히 SVM (Support Vector Machine)으로 알려진 Kernel machines에서 말하는 (Kernel) trick의 그것과 동일하다. 즉, 원래 데이터 또는 변형된 데이터가 무엇이냐를 명시적으로 보지 않고, 두 개의 벡터 (또는 변형된 벡터)의 관계 (보통은 유사도)만을 계산하면 된다. 즉, 커널머신에서 커널이란 보통 유사도의 다른 의미로 사용되는데, x1과 x2의 유사도를 계산하기 위해서 <phi(x1), phi(x2)>처럼 phi함수로 차원을 확장하고 그 둘 사이의 연산으로 구하는 것이 (쉽게 말해서) 커널 트릭이다. 그런데 해싱트릭은 앞서 해싱이 차원을 축소하는 기술이라 설명했듯이, 커널트릭과 반대로 차원을 축소해서 원래 유사도를 구하는 방식이라고 보면 된다. 수백만 차원의 데이터 x1과 x2 간의 유사도를 구하는 것이 아니라, 축소된 수십/수백 차원의 데이터 x1'와 x2' 간의 유사도를 구하는 것이다.

 앞서 해싱충돌도 언급했지만, 문제는 원래 데이터 간의 유사도 (OS = Sim(x1, x2))와 축소된 데이터 간의 유사도 (RS = Sim(x1', x2'))가 완전히 같지는 않다는 점이다. 하지만, OS와 RS 간의 차이가 별로 크지 않다는 것 (|OS - RS| < e)을 설명해주는  Johnson–Lindenstrauss lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)라는 이론이 있다. 하지만, 통상적으로 e의 범위가 매우 적을 것으로 기대하겠지만, 실은 0에서 1사이라는 점이 함정이다. 하지만, 앞서 말했듯이 여러 개의 해싱을 사용하는 등으로 충분히 회피 가능하다. 데이터의 차원을 축소하는 방식으로 아주 간단한 Random Projection이라는 것이 있는데, 해싱트릭은 랜덤프로젝션의 아주 특수한 케이스지만 랜덤프로젝션보다 더 나은 속성을 갖고 있다. 연산이 예측가능 (일관적)이고, sparse 데이터의 sparsity를 어느 정도 유지시켜주고, 또 함수로 연산이 되므로 프로젝션 매트릭스를 저장해둘 필요가 없다는 점 등이다.

Multitask learning은 좀 일반적인 개념이다. 간단히 말해서 하나의 식으로 여러 개의 태스트를 동시에 처리하도록 학습시키는 것이라 보면 된다. 개인화 추천에서 개개인별로 특화된 추천식을 학습시켜주는 것이 맞지만, 이렇게 되면 수백만, 수천만개의 식을 학습시켜줘야 한다. 이는 비효율적이기 때문에 하나의 추천식이 모든 개인 및 아이템별로 다른 값을 예측하도록 학습시킨다. 보통 유저 피쳐와 아이템 피쳐 간의 Cartesian Production (Conjunction)을 취해서 피쳐 수를 늘려서 하나의 예측식을 만드는 것이 보통이다. 그런데 만약 유저피쳐가 1,000개이고, 아이템 피쳐가 1,000개라면 카테시안 피쳐는 1,000,000차원이 된다. 그래서 야후나 크리테오에서 광고추천 로직에 앞서 설명한 해싱트릭으로 차원을 축소해서 사용하고 있다.

이런 (개인화된) 멀티태스크 런닝의 기본 철학은 공유할 수 있는 데이터를 공유하고, 개별 속성은 별도로 반영한다는 것이다. ... 좀더 깊게 들어가면 Transfer learning까지 들어가야 하는데, 트랜스퍼러닝은 다음 기회에...


'Paper' 카테고리의 다른 글

An overview of gradient descent optimization algorithms  (1) 2017.10.17

실리콘 밸리의 무자비한 군주들, by Rob Cox


제목: The Ruthless Overlords of Silicon Valley
저자: Rob Cox
일시: March 12, 2012

요약
 실리콘 밸리의 주요 IT기업들은 스스로 기존의 대기업들과 다르다고 믿고 있다. 여기서 말하는 기존 대기업이란 19세기나 20세기 초에 카네기, 록펠러, 모건 스탠리 등에 의해서 설립된 석유, 재철, 철도, 또는 금융/은행기업들을 뜻한다. 보통 이런 대기업들은 수익을 최고의 가치로 여기고 무한정확장을 해나가면서 탐욕자로 낙인이 찍혀있다. 특히 최근의 금융위기에서도 잘 나타났듯이 월스트리트의 금융기업들은 탐욕의 아이콘으로 낙인이 찍혀있다. 이에 반해서 최근 실리콘 밸리를 중심으로 창업되는 많은 IT기업들은 처음부터 돈보다는 사용자들의 만족을 앞세우고 있다. 그렇기에 이런 IT기업들은 스스로 선하다고 여기고 있다. 대표적으로 구글의 Don't Evil 만트라나 애플의 스티브 잡스가 밝힌 '더 많은 돈보다는 더 위대한 제품을 만들기 위해서 고민한다' 등과 같은 말들은 스스로의 선함을 내세우는 의로 작용하고 있다. 그러나 최근의 모습에서는 이들 IT기업들도 그들이 대놓고 악하다고 말하고 있는 기존의 악덕대기업들과 전혀 다를 것이 없다. 애플이 아웃소싱을 하는 Foxconn의 노동문제는 나이키가 10여년 전에 겪었던 노동착취의 그것과 비슷하고, 구글 등의 인터넷 기업들은 SOPA로 대변되었던 저작권 보호 움직임에 반기를 들고 있고, 세계 최대 소셜네트워크 기업인 페이스북은 그들 사용자들의 프라이버시 문제에 대해서 엄격하지 못하다. 이런 몇 가지 사례에서 보듯이 스스로 선하겠다고 시작했던 IT기업들도 사업규모가 커지면서 그들의 이익에만 혈안이 되어있기 때문에 기존의 악덕기업들과 차별성을 찾기가 어려워졌다.
 
생각
 다른 것은 모르겠지만, 저작권 보호 SOPA에 관련된 생각은 별도로 밝힐 예정이다. 기본적으로 강제적인 법규에 의한 조정보다는 사용자들의 자발적 규제 (외부 압력에 눈치보는 자체검열이 아님)에 대해서는 찬성하지만, 최근의 금융 위기가 직간적접으로 글라스-스티걸법이라는 은행과 보험과 증권 업무의 분리라는 규제법의 폐지에서 시작되었다는 점에서 각 사기업에 무제한의 권한을 부여하는 것에서 발생하는 위험은 어느 정도 규제 또는 관리감독이 필요하다는 생각도 있다.