word2vec : 'a word is known by the company it keeps'
Skip-gram word2vec은 확률 분포 P(OㅣC)를 학습
loss for a single pair of words c and o : cross entropy between the true distribution y and the predicted distribution y_hat
PART 2. Implementing Word2Vec
Sigmoid Function
def sigmoid(x):
"""
Compute the sigmoid function for the input here.
Arguments:
x -- A scalar or numpy array.
Return:
s -- sigmoid(x)
"""
### YOUR CODE HERE (~1 Line)
s = 1 / (1+np.exp(-x))
### END YOUR CODE
return s
Naive Softmax Loss and Gradient
center word vector(v_c) : (d, )
outside vector(U) : (v, d)
def naiveSoftmaxLossAndGradient(centerWordVec, outsideWordIdx, outsideVectors, dataset):
""" Naive Softmax loss & gradient function for word2vec models
Implement the naive softmax loss and gradients between a center word's
embedding and an outside word's embedding. This will be the building block
for our word2vec models. For those unfamiliar with numpy notation, note
that a numpy ndarray with a shape of (x, ) is a one-dimensional array, which
you can effectively treat as a vector with length x.
Arguments:
centerWordVec -- numpy ndarray, center word's embedding
in shape (word vector length, )
(v_c in the pdf handout)
outsideWordIdx -- integer, the index of the outside word
(o of u_o in the pdf handout)
outsideVectors -- outside vectors is
in shape (num words in vocab, word vector length)
for all words in vocab (tranpose of U in the pdf handout)
dataset -- needed for negative sampling, unused here.
Return:
loss -- naive softmax loss
gradCenterVec -- the gradient with respect to the center word vector
in shape (word vector length, )
(dJ / dv_c in the pdf handout)
gradOutsideVecs -- the gradient with respect to all the outside word vectors
in shape (num words in vocab, word vector length)
(dJ / dU)
"""
### YOUR CODE HERE (~6-8 Lines)
y_hat = softmax(np.dot(outsideVectors, centerWordVec)) # prob : (V,d)x(d,1) = (V,)
y = np.zeros(y_hat.shape) # (V,)
y[outsideWordIdx] = 1
loss = -np.log(y_hat[outsideWordIdx]) # negative log likelihood
gradCenterVec = np.matmul(outsideVectors.T, (y_hat-y)) # (d,V)x(V,) = (d,)
gradOutsideVecs = np.matmul((y_hat-y).reshape(-1,1), centerWordVec.reshape(1,-1)) # (V,1)x(1,d) = (V,d)
### Please use the provided softmax function (imported earlier in this file)
### This numerically stable implementation helps you avoid issues pertaining
### to integer overflow.
### END YOUR CODE
return loss, gradCenterVec, gradOutsideVecs
Negative Sampling
outside word가 아닌 k개의 단어 index sampling
def getNegativeSamples(outsideWordIdx, dataset, K):
""" Samples K indexes which are not the outsideWordIdx """
negSampleWordIndices = [None] * K
for k in range(K):
newidx = dataset.sampleTokenIdx()
while newidx == outsideWordIdx: # outside word와는 다른 단어가 뽑히도록 함
newidx = dataset.sampleTokenIdx()
negSampleWordIndices[k] = newidx
return negSampleWordIndices
Negative Sampling Loss and Gradient
효율적으로 계산하기 위해 자주 사용되는 U와 v_t를 내적해 sigmoid를 씌운 행렬을 h로 저장
outsidevector(w_s)에 대해 미분한 행렬은 s=o인 경우와 아닌 경우로 나눠 계산
def negSamplingLossAndGradient(centerWordVec, outsideWordIdx, outsideVectors, dataset, K=10):
""" Negative sampling loss function for word2vec models
Implement the negative sampling loss and gradients for a centerWordVec
and a outsideWordIdx word vector as a building block for word2vec
models. K is the number of negative samples to take.
Note: The same word may be negatively sampled multiple times. For
example if an outside word is sampled twice, you shall have to
double count the gradient with respect to this word. Thrice if
it was sampled three times, and so forth.
Arguments/Return Specifications: same as naiveSoftmaxLossAndGradient
"""
# Negative sampling of words is done for you. Do not modify this if you
# wish to match the autograder and receive points!
negSampleWordIndices = getNegativeSamples(outsideWordIdx, dataset, K)
indices = [outsideWordIdx] + negSampleWordIndices
### YOUR CODE HERE (~10 Lines)
# U = [u_o, -u_w1, ..., -u_wk]
U = -outsideVectors[indices] # (k+1,d)
U[0] = -U[0]
h = sigmoid(np.matmul(U, centerWordVec)) # (k+1,d)x(d,) = (k+1,)
loss = -np.log(h[0])-np.sum(np.log(h[1:]))
gradCenterVec = -np.matmul(1-h, U) # (k+1,)x(k+1,d) = (1,k+1)x(k+1xd) = (1,d) = (d,)
gradOutsideVecs = np.zeros(outsideVectors.shape) # (V,d)
gradOutsideVecs[outsideWordIdx] = -(1-h[0])*centerWordVec # target
for idx, num in enumerate(negSampleWordIndices): # 샘플링수를 고려하여 채우기
gradOutsideVecs[num] += ((1-h[idx+1])*centerWordVec) # h[0]은 제외해야함
### Please use your implementation of sigmoid in here.
### END YOUR CODE
return loss, gradCenterVec, gradOutsideVecs
Skip Gram
centerWordVectors : (V,d)
def skipgram(currentCenterWord, windowSize, outsideWords, word2Ind,
centerWordVectors, outsideVectors, dataset,
word2vecLossAndGradient=naiveSoftmaxLossAndGradient):
""" Skip-gram model in word2vec
Implement the skip-gram model in this function.
Arguments:
currentCenterWord -- a string of the current center word
windowSize -- integer, context window size
outsideWords -- list of no more than 2*windowSize strings, the outside words
word2Ind -- a dictionary that maps words to their indices in
the word vector list
centerWordVectors -- center word vectors (as rows) is in shape
(num words in vocab, word vector length)
for all words in vocab (V in pdf handout)
outsideVectors -- outside vectors is in shape
(num words in vocab, word vector length)
for all words in vocab (transpose of U in the pdf handout)
word2vecLossAndGradient -- the loss and gradient function for
a prediction vector given the outsideWordIdx
word vectors, could be one of the two
loss functions you implemented above.
Return:
loss -- the loss function value for the skip-gram model
(J in the pdf handout)
gradCenterVecs -- the gradient with respect to the center word vector
in shape (num words in vocab, word vector length)
(dJ / dv_c in the pdf handout)
gradOutsideVecs -- the gradient with respect to all the outside word vectors
in shape (num words in vocab, word vector length)
(dJ / dU)
"""
loss = 0.0
gradCenterVecs = np.zeros(centerWordVectors.shape)
gradOutsideVectors = np.zeros(outsideVectors.shape)
### YOUR CODE HERE (~8 Lines)
for o in outsideWords:
tmp_loss, grad_centerVec, grad_outsideVecs = word2vecLossAndGradient(centerWordVectors[word2Ind[currentCenterWord]], word2Ind[o], outsideVectors, dataset)
loss += tmp_loss
gradCenterVecs[word2Ind[currentCenterWord]] += grad_centerVec
gradOutsideVectors += grad_outsideVecs
### END YOUR CODE
return loss, gradCenterVecs, gradOutsideVectors
PART 2. SGD
def sgd(f, x0, step, iterations, postprocessing=None, useSaved=False,
PRINT_EVERY=10):
""" Stochastic Gradient Descent
Implement the stochastic gradient descent method in this function.
Arguments:
f -- the function to optimize, it should take a single
argument and yield two outputs, a loss and the gradient
with respect to the arguments
x0 -- the initial point to start SGD from
step -- the step size for SGD
iterations -- total iterations to run SGD for
postprocessing -- postprocessing function for the parameters
if necessary. In the case of word2vec we will need to
normalize the word vectors to have unit length.
PRINT_EVERY -- specifies how many iterations to output loss
Return:
x -- the parameter value after SGD finishes
"""
# Anneal learning rate every several iterations
ANNEAL_EVERY = 20000
if useSaved:
start_iter, oldx, state = load_saved_params()
if start_iter > 0:
x0 = oldx
step *= 0.5 ** (start_iter / ANNEAL_EVERY)
if state:
random.setstate(state)
else:
start_iter = 0
x = x0
if not postprocessing:
postprocessing = lambda x: x
exploss = None
for iter in range(start_iter + 1, iterations + 1):
# You might want to print the progress every few iterations.
loss = None
### YOUR CODE HERE (~2 lines)
loss, grad = f(x)
x -= step * grad
### END YOUR CODE
x = postprocessing(x)
if iter % PRINT_EVERY == 0:
if not exploss:
exploss = loss
else:
exploss = .95 * exploss + .05 * loss
print("iter %d: %f" % (iter, exploss))
if iter % SAVE_PARAMS_EVERY == 0 and useSaved:
save_params(iter, x)
if iter % ANNEAL_EVERY == 0:
step *= 0.5
return x
