문제 설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 제한 사항 -첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) -둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) -첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 입출력 예 input output 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 6 10 4790 1 5..
역전파란? 역전파는 오차 역전파법, 오류 역전파 알고리즘 이라고도 하며, 동일 입력층에 대해 원하는 값이 출력되도록 각 계층의 가중치를 조정하는 방법으로 사용됩니다. 즉, 예측값과 실제값의 차이인 오차를 계산하고, 이것을 다시 역으로 전파하여 가중치를 조정합니다. 이때, 역전파 과정에서는 최적화 함수를 이용합니다. 역전파를 이해하기 위해서는 인공신경망이 어떻게 가중치를 조정하는지 원리부터 알아야합니다. 위와 같이 1개의 입력층, 1개의 은닉층, 1개의 출력층이 존재합니다.(각 계층에 뉴런은 2개씩) 이제 이 신경망을 학습시켜봅시다. (1) 순전파(forward propagation) 순전파는 입력받은 데이터를 각 가중치와 곱하여 출력을 뽑아내는 과정입니다. 먼저 입력층에서 입력을 받아 은닉층으로 ..
(7) RMSProp(Root Mean Square Propagation) AdaGrad는 학습 시간이 길어질수록 학습률이 0에 수렴하게 된다는 문제점이 존재했었죠. RMSProp는 이러한 문제점을 해결하고자 제시된 방법입니다. RMSProp는 과거의 모든 기울기를 더하는 것이 아니라, 먼 기울기는 서서히 잊고, 새로운 기울기 정보를 크게 반영합니다. 수식을 보면 새로운 하이퍼 파라미터인 p가 추가된 것을 볼 수 있습니다. p가 작을수록 가장 최신의 기울기를 더 크게 반영합니다. 이로 인해서 이제 기울기가 무한히 커지는 것을 막을 수 있습니다. (8) AdaDelta(Adaptive Delta) AdaDelta역시 AdaGrad의 문제점을 해결하기위해 제시된 방법입니다. AdaDelta는 기울기의..
최적화란? 신경망 학습의 목적은 손실 함수의 값을 가능한 낮추는 매개변수를 찾는 것입니다. 즉, 어떤 목적함수의 값을 최적화시키는 파라미터 조합을 찾는 것을 뜻합니다. 매개변수 공간은 굉장히 넓고, 복잡하기 때문에 최적화 솔루션을 찾는 것은 굉장히 어려운 문제입니다. 여기서! 목적 함수가 1차식 이하로 구성되어있다면, 선형 최적화 문제, 2차식 이상으로 되어있다면, 비선형 최적화 문제라고 합니다. 최적화의 원리? 현재의 손실 함수 값이 감소하는 방향으로 파라미터를 업데이트 시킵니다. 여기서 가장 중요한 이슈는 어느 방향으로 얼만큼 갈 것인지 결정하는 것 입니다. ▶ 경사 하강법(Gradient Descent) 경사 하강법은 최적화 시킬 목적함수 f(x)에 대해서, 시작점을 x0를 정하고, 현재 ..
활성화 함수란? 신경망에서입력 신호의 총 합을 출력 신호로 변환하는 함수입니다. 퍼셉트론은 인간의 뇌의 뉴런을 모방하여 만든 것입니다. 뉴런이 말단에서 다음 뉴런으로 전달될 때, 어떠한 임계 값을 기준으로 신호가 전달된다고 합니다. 쉽게 말해서, 퍼셉트론은 뉴런처럼 입력 받은 수치들을 계산하고, 출력하기 전에 활성화 함수를 거쳐 출력에 변화를 줍니다. 이제 활성화 함수에 종류에 대해서 알아봅시다. (1) 계단 함수 계단함수는 활성화 함수중에 가장 간단한 함수입니다. 특정한 값을 입력받았을때, 값이 0이하 즉, 음수이면 무조건 0을, 0초과이면 1을 출력해 주는 함수입니다. def step(x): return x > 0 코드도 아주아주 간단합니다. 계단 함수 계단 함수는 그래프에서 보이는 것 처럼,..
논문 https://arxiv.org/pdf/2005.14165.pdf Github https://github.com/openai/gpt-3 이 논문은 GPT-3에 대한 논문입니다. 등장 배경 GPT-3는 아래와 같은 기존 모델들의 한계점들을 해결하기 위해 제안되었습니다. 1. 자연어의 각 task에 대한 대용량의 라벨링된 데이터가 필요하다는 것은 언어 모델의 적용 가능성을 제한시킵니다. 2. 사전 학습된 모델을 다시 미세 조정 시키는 것은 매우 협소한 task에 대해 미세 조정되는 것입니다. 3. 사람의 학습법과 비슷하게, 적은 데이터를 이용하여 충분히 학습 가능합니다. 즉, 다양한 자연어 관련 task들과 skill들을 잘 섞어서 이용하는것이 더 효과적입니다. 해결 방법 1. GPT 시리즈..
논문 https://d4mucfpksywv.cloudfront.net/better-language-models/language-models.pdf Github https://github.com/openai/gpt-2 이 논문은 GPT-2에 대한 논문입니다. 기존의 GPT-1보다 어떤점이 더 나아졌는지 잘 살펴보겠습니다. 등장 배경 기존 GPT-1은 대규모의 자연어 데이터로 사전 학습을 먼저 거친 뒤, 사용할 task에 맞게 미세 조정을 했습니다. GPT-2는 이러한 과정조차 다 없애버리고, 미세 조정을 하지 않고도, 각 task에 맞는 수행을 할 수 있도록 제안된 모델입니다. 그렇기 때문에 GPT-2모델은 어마어마하게 큽니다. ※ 미세 조정을 왜 없앤건가요? 한번 사전 학습된 모델을 다시 미세..
논문 https://arxiv.org/pdf/1802.05365.pdf Github https://github.com/HIT-SCIR/ELMoForManyLangs 등장 배경 "너에게 사과를 한다.", "사과 먹을래?" 에서 "사과"라는 단어는 같지만, 다른 의미를 가집니다. 기존의 Word2Vec나, Glove등의 모델은 "사과"는 같은 임베딩 값을 가집니다. 단어가 어떻게 사용되느냐에 따라 다르게 의미를 임베딩 하는 방법이 바로 ELMo가 사용한 방법인 Contextualized Word Embedding입니다. 즉, ELMo는 동음이의어에 대해 서로 다른 벡터로 임베딩 할 수 있게 문맥을 고려하여 임베딩합니다. 모델 구조 ELMo는 다층 구조인 양방향 LSTM를 이용합니다. 여기서 기존의..
논문 https://arxiv.org/pdf/1810.04805.pdf Github https://github.com/google-research/bert 등장 배경 언어 모델의 사전 학습은 자연어 처리작업을 개선하는데 효과적인 것으로 나타났습니다. (GPT-1에서 이미 확인되었죠) 현재 나온 모델인 GPT-1은 왼쪽에서 오른쪽으로 이전 토큰만을 참고할 수 있는 단방향 구조를 사용합니다.(Transformer의 decoder를 사용하기 때문이죠.) 이 방법은 문장 수준의 작업에 적합하지 않고, 양방향 컨텍스트를 통합하는것이 중요한 질문,응답 문제에서 미세 조정을 할때, 좋지 않을 결과를 가지고 올 수 있습니다. 따라서 양방향 구조를 사용하는 BERT가 탄생합니다. ※ 양방향 단방향 구조가 뭔가..
논문 https://www.cs.ubc.ca/~amuham01/LING530/papers/radford2018improving.pdf Github https://github.com/openai/finetune-transformer-lm 자연어 처리 분야에서 BERT와 함께 뛰어난 성능으로 주목받고 있는 모델입니다. 현재는 GPT-3까지 출시가 되었는데, GPT-4가 출시될거라는 말이 나왔죠(기사링크). 오늘은 GPT-1을 알아보도록 하겠습니다. 등장 배경 현재 라벨링 되어있지 않은 텍스트 데이터는 굉장히 많은 반면, 라벨링된 데이터는 적습니다. 따라서 많은 데이터로 학습하기 위하여 비지도 학습(unsupervised learning)으로 학습 할 수 있는 모델이 필요해졌습니다. 따라서 GPT-1이..
