#!/usr/bin/env python3
# Student name: NAME
# Student number: NUMBER
# UTORid: ID
Copyright By PowCoder代写 加微信 powcoder
import typing as T
from math import inf
import torch
import torch.nn.functional as F
from torch import Tensor
def is_projective(heads: T.Iterable[int]) -> bool:
Determines whether the dependency tree for a sentence is projective.
heads: The indices of the heads of the words in sentence. Since ROOT
has no head, it is not expected to be part of the input, but the
index values in heads are such that ROOT is assumed in the
starting (zeroth) position. See the examples below.
True if and only if the tree represented by the input is
projective.
The projective tree from the assignment handout:
>>> is_projective([2, 5, 4, 2, 0, 7, 5, 7])
The non-projective tree from the assignment handout:
>>> is_projective([2, 0, 2, 2, 6, 3, 6])
projective = True
# *#* BEGIN YOUR CODE *#* #
# *** END YOUR CODE *** #
return projective
def is_single_root_tree(heads: Tensor, lengths: Tensor) -> Tensor:
Determines whether the selected arcs for a sentence constitute a tree with
a single root word.
Remember that index 0 indicates the ROOT node. A tree with “a single root
word” has exactly one outgoing edge from ROOT.
If you like, you may add helper functions to this file for this function.
heads (Tensor): a Tensor of dimensions (batch_sz, sent_len) and dtype
int where the entry at index (b, i) indicates the index of the
predicted head for vertex i for input b in the batch
lengths (Tensor): a Tensor of dimensions (batch_sz,) and dtype int
where each element indicates the number of words (this doesn’t
include ROOT) in the corresponding sentence.
A Tensor of dtype bool and dimensions (batch_sz,) where the value
for each element is True if and only if the corresponding arcs
constitute a single-root-word tree as defined above
Valid trees from the assignment handout:
>>> is_single_root_tree(torch.tensor([[2, 5, 4, 2, 0, 7, 5, 7],\
[2, 0, 2, 2, 6, 3, 6, 0]]),\
torch.tensor([8, 7]))
tensor([True, True])
Invalid trees (the first has a cycle; the second has multiple roots):
>>> is_single_root_tree(torch.tensor([[2, 5, 4, 2, 0, 8, 6, 7],\
[2, 0, 2, 2, 6, 3, 6, 0]]),\
torch.tensor([8, 8]))
tensor([False, False])
# *#* BEGIN YOUR CODE *#* #
tree_single_root = torch.ones_like(heads[:, 0], dtype=torch.bool)
# *** END YOUR CODE *** #
return tree_single_root
def single_root_mst(arc_scores: Tensor, lengths: Tensor) -> Tensor:
Finds the maximum spanning tree (more technically, arborescence) for the
given sentences such that each tree has a single root word.
Remember that index 0 indicates the ROOT node. A tree with “a single root
word” has exactly one outgoing edge from ROOT.
If you like, you may add helper functions to this file for this function.
arc_scores (Tensor): a Tensor of dimensions (batch_sz, x, y) and dtype
float where x=y and the entry at index (b, i, j) indicates the
score for a candidate arc from vertex j to vertex i.
lengths (Tensor): a Tensor of dimensions (batch_sz,) and dtype int
where each element indicates the number of words (this doesn’t
include ROOT) in the corresponding sentence.
A Tensor of dtype int and dimensions (batch_sz, x) where the value at
index (b, i) indicates the head for vertex i according to the
maximum spanning tree for the input graph.
>>> single_root_mst(torch.tensor(\
[[[0, 0, 0, 0],\
[12, 0, 6, 5],\
[4, 5, 0, 7],\
[4, 7, 8, 0]],\
[[0, 0, 0, 0],\
[1.5, 0, 4, 0],\
[2, 0.1, 0, 0],\
[0, 0, 0, 0]],\
[[0, 0, 0, 0],\
[4, 0, 3, 1],\
[6, 2, 0, 1],\
[1, 1, 8, 0]]]),\
torch.tensor([3, 2, 3]))
tensor([[0, 0, 3, 1],
[0, 2, 0, 0],
[0, 2, 0, 2]])
# *#* BEGIN YOUR CODE *#* #
best_arcs = arc_scores.argmax(-1)
# *** END YOUR CODE *** #
return best_arcs
if __name__ == ‘__main__’:
import doctest
doctest.testmod()
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com