coursera

Duplicate keys 일반적으로 대량의 데이터에 대해 정렬을 수행하는 것은 중복되는 key를 기준으로 정렬을 적용하는 경우가 많습니다. 위처럼 '도시 - 시간' 형태의 데이터라면 도시를 기준으로 정렬하게 되는 것이죠. 원래는 중복된 key를 포함하는 데이터에 대해 퀵정렬을 수행하는 경우 quadratic(2차) 시간이 걸린다는 문제점이 있었으나, 병합 정렬을 이용하여 그 시간을 획기적으로 줄일 수 있게 되었죠. Duplicate keys: the problem 하지만 일반적인 병합 정렬 방식을 적용하게 되면, key가 모두 동일한 경우에 대해서는 quadratic 시간이 소요될 것입니다. 이를 방지하기 위해 paritioning item(기준 아이템)과 동일한 것이 확인되는 순간 작업을 멈춰서 Nl..

GloVe (global vectors for word representatoin) 굉장히 직관적이고 간단한 방식으로 유명한 GloVe 모델입니다. context i, target j의 관계에서, context가 주어졌을 때 target이 몇 번 등장했는지를 Xij 변수에 담습니다. 설정한 조건들에 따라서 Xij, Xji의 값이 같을 수 있습니다. Model 모델의 학습 방향은 당연히 손실 함수를 최소화하는 것입니다. i, j가 각각 target, context를 의미한다는 점을 고려해 본다면, 예측한 확률에서 각 target의 등장 횟수를 log를 취해 빼는 방식입니다. 가중치 인자에 해당하는 f는 this, is, of, a와 같이 자주 등장하지만 그 의미는 약한 stopwords에게는 적은 가중치를..

Defining a new learning problem skip-gram 모델은 위처럼 context 하나에 대해 target을 random sampling 하는 방식입니다. 위 예시에서는 k 변수를 4로 설정하여 실제 target을 제외한 후보를 네 개 추출한 것을 볼 수 있습니다. 만약 데이터셋이 작은 경우라면 이 k의 값을 키워 여러 개의 단어를 추출해보는 것이 좋습니다. 반대로 데이터셋이 크다면 k의 값을 줄이는 것이 효율적입니다. 결국 context - word 쌍을 input X로 주고, target y를 output으로 두어서 모델이 학습하게 됩니다. Model 위 소프트맥스 함수는, context와 target 쌍이 주어졌을 때, 예측 결과가 실제 target이었을 확률을 구하는 것입니다..

Skip-grams 이번에는 Word2Vec 모델 중 하나인 skip-gram에 대해 다룹니다. 지금까지는 target 단어를 기준으로 context를 어떻게 설정하는지에 대해 주로 이야기했습니다. 하지만 여기서는 orange라는 하나의 context를 기준으로 랜덤하게(5개의 단어 +- 범위 내에서) target을 설정한 것을 볼 수 있습니다. Model context에 따른 target을 설정하는 방법이 조금 다르다는 점을 제외한 나머지 과정은 동일합니다. context의 one-hot vector를 통해 embedding matrix에서 해당 column을 추출합니다. 여기에 softmax를 적용해 어떤 단어가 될지(vocab에 포함된 단어 중)를 예측하여 y hat을 구합니다. 이때 context..

Neural language model 지난 시간까지 배웠던 word embedding이 어떤 식으로 모델 학습에 이용되는지를 나타내고 있습니다. 1. 각 단어(토큰)를 대상으로 vocab에서 숫자를 꺼내어 one-hot vector를 생성합니다. 2. 이를 이용하여 embedding matrix에서 매칭되는 column을 추출합니다. 3. 추출된 column을 중첩하여 input으로 이용합니다. 4. 모델 학습은 이렇게 만든 input에 대한 weight & bias, 그리고 softmax를 통해 추출한 확률을 구할 때의 weight & bias로 진행됩니다. Other context/target pairs target, 즉 예측하고자 하는 단어의 주변 문맥을 어디까지 설정하는가도 중요한 문제입니다. ..

Selection 이번에는 '선택'과 관련한 문제입니다. 만약 어떤 배열에서 '최소/최대'의 값을 구해야 한다면 배열을 한 번만 쭉 훑으면서 최소/최대의 값을 저장하면 되기 때문에 선형 시간이 필요할 것입니다. 즉, N만큼의 시간이 소요되죠. 하지만 배열에서 k번째의 값을 구하려면 이는 단순히 한 번 훑어보는 것으로 판단할 수 있는 문제가 아니게 됩니다. 정렬 후 k번째 값을 가져오면 되지만 이는 linearithmic, 즉 NlogN만큼의 시간이 필요한 작업입니다. 뭔가 비슷한듯 비슷하지 않은 두 방식에 대해서, 후자도 선형 시간으로 처리할 수 있지 않을까? 라는게 과거 학자들의 궁금증이었습니다. Quick-select import random def partition(a, lo, hi): i, j =..