A2 · Word2Vec and Dependency Parsing

做什么

题面来自官方材料（本地原件在 _local/，官方链接见「材料」）。 编号是原件的编号（notebook 是 cell 序号、PDF 是页码），方便跟官方题面对号。 本项目不提供答案（D53）。

第 1 页

CS 224N Winter 2026 Assignment 2 Word2Vec and Dependency Parsing Due date: January 22nd, Thursday, 4:30 PM PST In this assignment, you will review the mathematics behind Word2Vec and build a neural dependency parser using PyTorch. For a review of the fundamentals of PyTorch, please check out the PyTorch review session on Canvas. In Part 1, you will explore the partial derivatives involved in training a Word2vec model using the naive softmax loss. In Part 2, you will learn about two general neural network techniques (Adam Optimization and Dropout). In Part 3, you will implement and train a dependency parser using the techniques from Part 2, before analyzing a few erroneous dependency parses. If you are using LaTeX, you can use \ifans{} to type your solutions. Please tag the questions correctly on Gradescope, otherwise the TAs will take points off if you don’t tag questions. 1. Understanding word2vec (20 points) Recall that the key insight behind word2vec is that ‘a word is known by the company it keeps’. Con- cretely, consider a ‘center’ word c surrounded before and after by a context of a certain length. We term words in this contextual window ‘outside words’ (O). For example, in Figure 1, the context window length is 2, the center word c is ‘banking’, and the outside words are ‘turning’, ‘into’, ‘crises’, and ‘as’: Figure 1: The word2vec skip-gram prediction model with window size 2 Skip-gram word2vec aims to learn the probability distribution P(O|C). Specifically, given a specific word o and a specific word c, we want to predict P(O = o|C = c): the probability that word o is an ‘outside’ word for c (i.e., that it falls within the contextual window of c). We model this probability by taking the softmax function over a series of vector dot-products: P(O = o | C = c) = exp(u⊤ o vc) P w∈Vocab exp(u⊤ wvc) (1) For each word, we learn vectors u and v, where uo is the ‘outside’ vector representing outside word o, and vc is the ‘center’ vector representing center word c. We store these parameters in two matrices, U and V. The columns of U are all the ‘outside’ vectors uw; the columns of V are all of the ‘center’ vectors vw. Both U and V contain a vector for every w ∈Vocabulary.1 1Assume that every word in our vocabulary is matched to an integer number k. Bolded lowercase letters represent vectors. uk is both the kth column of U and the ‘outside’ word vector for the word indexed by k. vk is both the kth column of V and the ‘center’ word vector for the word indexed by k. In order to simplify notation we shall interchangeably use k to refer to word k and the index of word k. 1

第 2 页

CS 224n Assignment 2 Page 2 of 8 Recall from lectures that, for a single pair of words c and o, the loss is given by: Jnaive-softmax(vc, o, U) = −log P(O = o|C = c). (2) We can view this loss as the cross-entropy2 between the true distribution y and the predicted distribu- tion ˆy, for a particular center word c and a particular outside word o. Here, both y and ˆy are vectors with length equal to the number of words in the vocabulary. Furthermore, the kth entry in these vectors indicates the conditional probability of the kth word being an ‘outside word’ for the given c. The true empirical distribution y is a one-hot vector with a 1 for the true outside word o, and 0 everywhere else, for this particular example of center word c and outside word o.3 The predicted distribution ˆy is the probability distribution P(O|C = c) given by our model in equation (1). Note: Throughout this homework, when computing derivatives, please use the method reviewed during the lecture (i.e. no Taylor Series Approximations). (a) (2 points) Prove that the naive-softmax loss (Equation 2) is the same as the cross-entropy loss between y and ˆy, i.e. (note that y (true distribution), ˆy (predicted distribution) are vectors and ˆyo is a scalar): − X w∈Vocab yw log(ˆyw) = −log(ˆyo). (3) Your answer should be one line. You may describe your answer in words. (b) (6 points) i. Compute the partial derivative of Jnaive-softmax(vc, o, U) with respect to vc. Please write your answer in terms of y, ˆy, U, and show your work to receive full credit. • Note: Your final answers for the partial derivative should follow the shape convention: the partial derivative of any function f(x) with respect to x should have the same shape as x.4 • Please provide your answers for the partial derivative in vectorized form. For example, when we ask you to write your answers in terms of y, ˆy, and U, you may not refer to specific elements of these terms in your final answer (such as y1, y2, . . . ). You may also not refer to specific vectors such as u0, u1, etc. ii. When is the gradient you computed equal to zero? Write a mathematical equation. Hint: You may wish to review and use some introductory linear algebra concepts. iii. The gradient you found is the difference between the two terms. Provide an interpretation of how each of these terms improves the word vector when this gradient is subtracted from the word vector vc. (c) (1 point) In many downstream applications using word embeddings, L2 normalized vectors (e.g. u/||u||2 where ||u||2 = pP i u2 i ) are used instead of their raw forms (e.g. u). Let’s consider a hypothetical downstream task of binary classification of phrases as being positive or negative, where you decide the sign based on the sum of individual embeddings of the words. When would L2 normalization take away useful information for the downstream task? When would it not? Hint: Consider the case where ux = αuy for some words x̸ = y and some scalar α. When α is positive, what will be the value of normalized ux and normalized uy? How might ux and uy be related for such a normalization to affect or not affect the resulting classification? 2The cross-entropy loss between the true (discrete) probability distribution p and another distribution q is −P i pi log(qi). 3Note that the true conditional probability distribution of context words for the entire training dataset would not be one-hot. 4This allows us to efficiently minimize a function using gradient descent without worrying about reshaping or dimension mismatching. While following the shape convention, we’re guaranteed that θ := θ −α ∂J(θ) ∂θ is a well-defined update rule.

第 3 页

CS 224n Assignment 2 Page 3 of 8 (d) (1 point) Write down the partial derivative of Jnaive-softmax(vc, o, U) with respect to U. Please break down your answer in terms of the column vectors ∂J(vc,o,U) ∂u1 , ∂J(vc,o,U) ∂u2 , · · · , ∂J(vc,o,U) ∂u|Vocab| (do not further expand these terms). No derivations are necessary, just an answer in the form of a matrix. (e) (5 points) Compute the partial derivatives of Jnaive-softmax(vc, o, U) with respect to each of the ‘outside’ word vectors, uw’s. There will be two cases: when w = o, the true ‘outside’ word vector, and w̸ = o, for all other words. Please write your answer in terms of y, ˆy, and vc. In this subpart, you may use specific elements within these terms as well (such as y1, y2, . . . ). Note that uw is a vector while y1, y2, . . . are scalars. Show your work to receive full credit. (f) (2 points) As an additional exercise for this problem, you will be taking the derivatives of some common loss functions, which may be used in variations of word2vec (such as the negative sampling variant). The Leaky ReLU (Leaky Rectified Linear Unit) activation function is given by Equation 4 and Figure 2: f(x) = max(αx, x) (4) Figure 2: Leaky ReLU Where x is a scalar and 0 < α < 1, please compute the derivative of f(x) with respect to x. You may ignore the case where the derivative is not defined at 0.5 (g) (3 points) The sigmoid function is given by Equation 5: σ(x) = 1 1 + e−x = ex ex + 1 (5) Please compute the derivative of σ(x) with respect to x, where x is a scalar. Please write your answer in terms of σ(x). Show your work to receive full credit. 5If you’re interested in how to handle the derivative at this point, you can read more about the notion of subderivatives.

第 4 页

CS 224n Assignment 2 Page 4 of 8 2. Neural Networks Optimization (8 points) (a) (4 points) Adam Optimizer Recall the standard Stochastic Gradient Descent update rule: θt+1 ←θt −α∇θtJminibatch(θt) where t + 1 is the current timestep, θ is a vector containing all of the model parameters, (θt is the model parameter at time step t, and θt+1 is the model parameter at time step t + 1), J is the loss function, ∇θJminibatch(θ) is the gradient of the loss function with respect to the parameters on a minibatch of data, and α is the learning rate. Adam Optimization6 uses a more sophisticated update rule with two additional steps.7 i. (2 points) First, Adam uses a trick called momentum by keeping track of m, a rolling average of the gradients: mt+1 ←β1mt + (1 −β1)∇θtJminibatch(θt) θt+1 ←θt −αmt+1 where β1 is a hyperparameter between 0 and 1 (often set to 0.9). Briefly explain in 2–4 sentences (you don’t need to prove mathematically, just give an intuition) how using m stops the updates from varying as much and why this low variance may be helpful to learning, overall. ii. (2 points) Adam extends the idea of momentum with the trick of adaptive learning rates by keeping track of v, a rolling average of the magnitudes of the gradients: mt+1 ←β1mt + (1 −β1)∇θtJminibatch(θt) vt+1 ←β2vt + (1 −β2)(∇θtJminibatch(θt) ⊙∇θtJminibatch(θt)) θt+1 ←θt −αmt+1/√vt+1 where ⊙and / denote elementwise multiplication and division (so z⊙z is elementwise squaring) and β2 is a hyperparameter between 0 and 1 (often set to 0.99). Since Adam divides the update by √v, which of the model parameters will get larger updates? Why might this help with learning? Briefly explain in 2–4 sentences. (b) (4 points) Dropout8 is a regularization technique. During training, dropout randomly sets units in the hidden layer h to zero with probability pdrop (dropping different units each minibatch), and then multiplies h by a constant γ. We can write this as: hdrop = γd ⊙h where d ∈{0, 1}Dh (Dh is the size of h) is a mask vector where each entry is 0 with probability pdrop and 1 with probability (1 −pdrop). γ is chosen such that the expected value of hdrop is h: Epdrop[hdrop]i = hi for all i ∈{1, . . . , Dh}. i. (2 points) What must γ equal in terms of pdrop? Briefly justify your answer or show your math derivation using the equations given above. ii. (2 points) Why should dropout be applied during training? Why should dropout NOT be applied during evaluation? Briefly explain in 2–4 sentences. Hint: it may help to look at the dropout paper linked. 6Kingma and Ba, 2015, https://arxiv.org/pdf/1412.6980.pdf 7The actual Adam update uses a few additional tricks that are less important, but we won’t worry about them here. If you want to learn more about it, you can take a look at: http://cs231n.github.io/neural-networks-3/#sgd 8Srivastava et al., 2014, https://www.cs.toronto.edu/˜hinton/absps/JMLRdropout.pdf

第 5 页

CS 224n Assignment 2 Page 5 of 8 3. Neural Transition-Based Dependency Parsing (40 points) In this section, you’ll be implementing a neural-network based dependency parser with the goal of max- imizing performance on the UAS (Unlabeled Attachment Score) metric. Before you begin, please follow the README to install all the needed dependencies for the assignment. We will be using PyTorch 2.1.2 from https://pytorch.org/get-started/locally/ with the CUDA option set to None, and the tqdm package – which produces progress bar visualizations through- out your training process. The official PyTorch website is a great resource that includes tutorials for understanding PyTorch’s Tensor library and neural networks. A dependency parser analyzes the grammatical structure of a sentence, establishing relationships between head words, and words which modify those heads. There are multiple types of dependency parsers, including transition-based parsers, graph-based parsers, and feature-based parsers. Your implementation will be a transition-based parser, which incrementally builds up a parse one step at a time. At every step it maintains a partial parse, which is represented as follows: • A stack of words that are currently being processed. • A buffer of words yet to be processed. • A list of dependencies predicted by the parser. Initially, the stack only contains ROOT, the dependencies list is empty, and the buffer contains all words of the sentence in order. At each step, the parser applies a transition to the partial parse until its buffer is empty and the stack size is 1. The following transitions can be applied: • SHIFT: removes the first word from the buffer and pushes it onto the stack. • LEFT-ARC: marks the second (second most recently added) item on the stack as a dependent of the first item and removes the second item from the stack, adding a first word →second word dependency to the dependency list. • RIGHT-ARC: marks the first (most recently added) item on the stack as a dependent of the second item and removes the first item from the stack, adding a second word →first word dependency to the dependency list. On each step, your parser will decide among the three transitions using a neural network classifier. (a) (4 points) Go through the sequence of transitions needed for parsing the sentence “I presented my findings at the NLP conference”. The dependency tree for the sentence is shown below. At each step, give the configuration of the stack and buffer, as well as what transition was applied this step and what new dependency was added (if any). The first three steps are provided below as an example. Stack Buffer New dependency Transition [ROOT] [I, presented, my, findings, at, the, NLP, conference] Initial Configuration [ROOT, I] [presented, my, findings, at, the, NLP, conference] SHIFT [ROOT, I, presented] [my, findings, at, the, NLP, conference] SHIFT [ROOT, presented] [my, findings, at, the, NLP, conference] presented→I LEFT-ARC

第 6 页

CS 224n Assignment 2 Page 6 of 8 (b) (2 points) A sentence containing n words will be parsed in how many steps (in terms of n)? Briefly explain in 1–2 sentences why. (c) (6 points) Implement the init and parse step functions in the PartialParse class in parser transitions.py. This implements the transition mechanics your parser will use. You can run basic (non-exhaustive) tests by running python parser transitions.py part c. (d) (8 points) Our network will predict which transition should be applied next to a partial parse. We could use it to parse a single sentence by applying predicted transitions until the parse is complete. However, neural networks run much more efficiently when making predictions about batches of data at a time (i.e., predicting the next transition for any different partial parses simultaneously). We can parse sentences in minibatches with the following algorithm. Algorithm 1 Minibatch Dependency Parsing Input: sentences, a list of sentences to be parsed and model, our model that makes parse decisions Initialize partial parses as a list of PartialParses, one for each sentence in sentences Initialize unfinished parses as a shallow copy of partial parses while unfinished parses is not empty do Take the first batch size parses in unfinished parses as a minibatch Use the model to predict the next transition for each partial parse in the minibatch Perform a parse step on each partial parse in the minibatch with its predicted transition Remove the completed (empty buffer and stack of size 1) parses from unfinished parses end while Return: The dependencies for each (now completed) parse in partial parses. Implement this algorithm in the minibatch parse function in parser transitions.py. You can run basic (non-exhaustive) tests by running python parser transitions.py part d. Note: You will need minibatch parse to be correctly implemented to evaluate the model you will build in part (e). However, you do not need it to train the model, so you should be able to complete most of part (e) even if minibatch parse is not implemented yet. (e) (20 points) We are now going to train a neural network to predict, given the state of the stack, buffer, and dependencies, which transition should be applied next. First, the model extracts a feature vector representing the current state. We will be using the feature set presented in the original neural dependency parsing paper: A Fast and Accurate Dependency Parser using Neural Networks.9 The function extracting these features has been implemented for you in utils/parser utils.py. This feature vector consists of a list of tokens (e.g., the last word in the stack, first word in the buffer, dependent of the second-to-last word in the stack if there is one, etc.). They can be represented as a list of integers w = [w1, w2, . . . , wm] where m is the number of features and each 0 ≤wi < |V | is the index of a token in the vocabulary (|V | is the vocabulary size). Then our network looks up an embedding for each word and concatenates them into a single input vector: x = [Ew1, ..., Ewm] ∈Rdm where E ∈R|V |×d is an embedding matrix with each row Ew as the vector for a particular word w 9Chen and Manning, 2014, https://nlp.stanford.edu/pubs/emnlp2014-depparser.pdf

第 7 页

CS 224n Assignment 2 Page 7 of 8 with dimension d. We then compute our prediction as: h = ReLU(xW + b1) l = hU + b2 ˆy = softmax(l) where h is referred to as the hidden layer, l is referred to as the logits, ˆy is referred to as the predictions, and ReLU(z) = max(z, 0)). We will train the model to minimize cross-entropy loss: J(θ) = CE(y, ˆy) = − 3 X j=1 yj log ˆyj where yj denotes the jth element of y. To compute the loss for the training set, we average this J(θ) across all training examples. i. Compute the derivative of h = ReLU(xW + b1) with respect to x. For simplicity, you only need to show the derivative ∂hi ∂xj for some index i and j. You may ignore the case where the derivative is not defined at 0. ii. Recall in part 1b, we computed the partial derivative of Jnaive-softmax(vc, o, U). Likewise, please compute the partial derivative of J(θ) with respect to the ith entry of l, which is denoted as li. Specifically, compute ∂CE(y,ˆy) ∂li , assuming that l ∈R3, ˆy ∈R3, y ∈R3, and the true label is c (i.e., yj = 1 if j = c). Hint: Use the chain rule: ∂J ∂l = ∂J ∂ˆy · ∂ˆy ∂l . iii. We will use UAS score as our evaluation metric. UAS refers to Unlabeled Attachment Score, which is computed as the ratio between number of correctly predicted dependencies and the number of total dependencies despite of the relations (our model doesn’t predict this). In parser model.py you will find skeleton code to implement this simple neural network using PyTorch. Complete the init , embedding lookup and forward functions to implement the model. Then complete the train for epoch and train functions within the run.py file. Finally execute python run.py to train your model and compute predictions on test data from Penn Treebank (annotated with Universal Dependencies). Note: • For this assignment, you are asked to implement Linear layer and Embedding layer. Please DO NOT use torch.nn.Linear or torch.nn.Embedding module in your code, otherwise you will receive deductions for this problem. • Please follow the naming requirements in our TODO if there are any, e.g. if there are explicit requirements about variable names you have to follow them in order to receive full credits. You are free to declare other variable names if not explicitly required. Hints: • Each of the variables you are asked to declare (self.embed to hidden weight, self.embed to hidden bias, self.hidden to logits weight, self.hidden to logits bias) corresponds to one of the variables above (W, b1, U, b2). • It may help to work backwards in the algorithm (start from ˆy) and keep track of the matrix/vector sizes. • Once you have implemented embedding lookup (e) or forward (f) you can call python parser model.py with flag -e or -f or both to run sanity checks with each

第 8 页

CS 224n Assignment 2 Page 8 of 8 function. These sanity checks are fairly basic and passing them doesn’t mean your code is bug free. • When debugging, you can add a debug flag: python run.py -d. This will cause the code to run over a small subset of the data, so that training the model won’t take as long. Make sure to remove the -d flag to run the full model once you are done debugging. • When running with debug mode, you should be able to get a loss smaller than 0.2 and a UAS larger than 65 on the dev set (although in rare cases your results may be lower, there is some randomness when training). • It should take up to 15 minutes to train the model on the entire training dataset, i.e., when debug mode is disabled. • When debug mode is disabled, you should be able to get a loss smaller than 0.08 on the train set and an Unlabeled Attachment Score larger than 87 on the dev set. For comparison, the model in the original neural dependency parsing paper gets 92.5 UAS. If you want, you can tweak the hyperparameters for your model (hidden layer size, hyperparameters for Adam, number of epochs, etc.) to improve the performance (but you are not required to do so). Deliverables: • Working implementation of the transition mechanics that the neural dependency parser uses in parser transitions.py. • Working implementation of minibatch dependency parsing in parser transitions.py. • Working implementation of the neural dependency parser in parser model.py. (We’ll look at and run this code for grading). • Working implementation of the functions for training in run.py. (We’ll look at and run this code for grading). • Please use efficient functions and avoid for loops when implementing embedding lookup. Otherwise, you may exceed the GradeScope test time limit. • Report the best UAS your model achieves on the dev set and the UAS it achieves on the test set in your written submission. You can report it in the PDF and tag the page. Submission Instructions You shall submit this assignment on GradeScope as two submissions – one for Assignment 2 [coding] and another for Assignment 2 [written]: 1. Run the collect submission.sh script to produce your assignment2.zip file. 2. Upload your assignment2.zip file to GradeScope to Assignment 2 [coding]. 3. Upload your written solutions to GradeScope to Assignment 2 [written].

材料

官方地址（W26 ✓ 全部验证过可下载 ✓）。本地副本放 _local/（只服务本地、不外传）。

怎么自查

• 官方仓库自带的测试（pytest / sanity check）—— ⚠️ Gradescope 只对注册学生开放， 自学者以仓库自带测试为准；
• 提交脚本：A3 / A4 提到 bash create_submission.sh。

这份作业和书的关系

见上表「配哪几讲」。等题面中英对照做完，这里会换成章节标题原文，并加定位校验 （指引指向一个不存在的标题会被 nav_check 报出来）。