gtn

Autograd

backward(g, grad, retain_graph=False)

Compute the gradients of any inputs with respect to graph.

Parameters

  • graph (Graph) – The graph to compute gradients with respect to.

  • grad (Graph) – A seed gradient, typically set to be a gradient of another function with respect to graph.

  • retain_graph (bool) – Whether or not to save the autograd graph. Setting this to False is more memory efficient as temporary graphs created during the forward computation may be destroyed.

backward(g, retain_graph=False)

Same as backward() but with the initial grad set to be ones.

Functions

add(g1, g2)

Add two scalar graphs.

closure(g)

Compute the (Kleene) closure of the graph. This operation is recorded in the autograd tape.

compose(g1, g2)

Compose two transducers. This operation is recorded in the autograd tape. If x:y is transduced by g1 and y:z is transduced by g2 then the composed graph will transduce x:z. The arc scores are added in the composed graph.

Both compose() and intersect() can be much faster when operating on graphs with sorted arcs. See Graph.arc_sort().

concat(graphs)

Concatenate a list of graphs. This operation is recorded in the autograd tape.

If x_i is a sequence accepted (or x_i:y_i is transduced) by graphs[i] then the concatenated graph accepts the sequence x_1x_2...x_n if graphs contains n graphs. The score of the path x_1...x_n is the sum of the scores of the individual x_i in graphs[i]. The concatenated graph is constructed by connecting every accepting state of graphs[i-1] to every starting state of graphs[i] with an \(\epsilon\) transition. The starting state of the concatenated graphs are starting states of graphs[0] and the accepting states are accepting states of graphs[-1].

Note the concatenation of 0 graphs gtn::concat([]) is the graph which accepts the empty string (\(\epsilon\)). The concatenation of a single graph is equivalent to a clone.

concat(g1, g2)

Equivalent to concat([g1, g2]), see concat().

forward_score(g)

Compute the forward score of a graph. Returns the score in a scalar graph which can be accessed with Graph.item(). This operation is recorded in the autograd tape.

The forward score is equivalent to the shortest distance from the start nodes to the accept nodes in the log semiring.

NB: graph must be acyclic.

intersect(g1, g2)

Intersect two acceptors. This operation is recorded in the autograd tape. This function only works on acceptors, calling it on a graph where graph.ilabel(a) != graph.olabel(a) for some a is undefined and may yield incorrect results. The intersected graph accepts any path x which is accepted by both g1 and g2. The arc scores are added in the intersected graph.

The result of compose() will yield an equivalent result, however; this function should be preferred since the implementation may be faster.

Both compose() and intersect() can be much faster when operating on graphs with sorted arcs. See Graph.arc_sort().

negate(g)

Negate a scalar graph.

project_input(other)

Removes the output labels from the graph and records the operation in the autograd tape. This function makes a copy of the input graph.

project_output(other)

Removes the input labels from the graph and records the operation in the autograd tape. This function makes a copy of the input graph.

remove(other, label=gtn.epsilon)

Construct the equivalent graph without \(\epsilon\) transitions. The \(\epsilon\) closure of each node in the graph is computed and the required transitions are added to yield the \(\epsilon\)-free equivalent graph. If label is specified then instead of removing epsilon transitions, arcs with the matching label are removed. The removed arc labels are treated as if they were \(\epsilon\) transitions.

subtract(g1, g2)

Subtract one scalar graph from another.

union(graphs)

Construct the union of a list of graphs.

viterbi_score(g)

Compute the Viterbi score of a graph. Returns the score in a scalar graph which can be accessed with Graph.item(). This operation is recorded in the autograd tape.

This is equivalent to the shortest distance from the start nodes to the accepting nodes in the tropical semiring.

NB: graph must be acyclic.

viterbi_path(g)

Compue the Viterbi shortest path of a graph and return it in a single chain graph with the labels and weights of the shortest path. This operation is recorded in the autograd tape.

The Viterbi shorted path is equivalent to the shortest path from the start nodes to the accepting nodes in the tropical semiring.

NB: graph must be acyclic.

Creations

scalar_graph(weight, calc_grad=True)

Creates a scalar graph - a graph with a single arc between two nodes with a given weight value and an \(\epsilon\) label (epsilon).

linear_graph(M, N, calc_grad=True)

Create a linear chain graph with M + 1 nodes and N edges between each node. The labels of the edges between each node are the integers [0, ..., N - 1].

Comparisons

equal(g1, g2)

Checks if two graphs are exactly equal (not isomorphic).

isomorphic(g1, g2)

Checks if two graphs are isomorphic. This function will be extremely slow for large graphs.

Parallel

parallel_for(function, int_list)

Computes the result of a given function that takes an int argument in parallel given some list of ints over which to process.

Returns nothing, even if the passed function has a return value.

Input and Output

draw(g1, file_name, isymbols={}, osymbols={})

Draw a graph to an image. This function requires a working installation of Graphviz. Arc labels are of the format ilabel/olabel:weight. If the output symbols are not specified then the olabel is omitted and arc labels are of the format ilabel:weight. If the input symbols are not specified then integer ids are used as the label.

The format of the image is determined by the file_name extension and can be any dot supported extension (check with dot -T?).

Parameters

  • graph (Graph) – The graph to draw

  • file_name (str) – The name of the file to write to

  • isymbols (dict) – A map of integer ids to strings used for arc input labels

  • osymbols (dict) – A map of integer ids to strings used for arc output labels

load(file_name)

Load a graph from a file. The first two lines contain the list of space separated start and accept nodes respectively. The following lines contain the arcs in the format:

srcNode dstNode ilabel [olabel=ilabel] [weight=0.0]

where [x=y] indicate optional values for x with a default value of y.

For example:

0
1
0 1 1

is a two node graph with an arc from start node 0 to accept node 1 with input and output label of 1,

0
1
0 1 1 2

is a two node graph with an arc from node 0 to node 1 with input label 1 and output label 2, and

0
1
0 1 1 2 3.0

is a two node graph with an arc from node 0 to node 1 with input label 1, output label 2, and a weight of 3.0.

write_dot(g, file_name, isymbols={}, osymbols={})

Write the graph in Graphviz DOT format. See draw().

epsilon: int

Use the epsilon constant to refer to \(\epsilon\) transitions.