GTN¶

Documentation for GTN, a library for automatic differentiation with weighted finite-state tranducers (WFSTs).

Building and Installing¶

Build Requirements¶

A C++ compiler with good C++14 support (e.g. g++ >= 5.0)
cmake – version 3.5.1 or later, and make

Building and Installing with CMake¶

Building¶

Currently, GTN must be built and installed from source.

First, clone gtn from its repository on Github:

git clone https://github.com/facebookresearch/gtn.git && cd gtn

Create a build directory and run CMake and make:

mkdir -p build && cd build
cmake ..
make -j $(nproc)

Run tests with:

make test

Install with:

make install

Build Options¶

Options	Configurations	Default Value
GTN_BUILD_TESTS	ON, OFF	ON
GTN_BUILD_BENCHMARKS	ON, OFF	ON
GTN_BUILD_EXAMPLES	ON, OFF	ON
GTN_BUILD_PYTHON_BINDINGS	ON, OFF	OFF
CMAKE_BUILD_TYPE	See CMake Docs	Debug

Linking your Project with CMake¶

Once flashlight is built and installed, including it in another project is simple with a CMake imported target. In your CMake list, add:

find_package(gtn REQUIRED)

# Create myCompiledTarget, etc.
# ...

target_link_libraries(myCompiledTarget PUBLIC gtn::gtn)

Your target’s files will be linked with the library and can include headers (e.g. #include <gtn/gtn.h>) directly.

Python Bindings¶

Installing Python Bindings

Basic Usage¶

Construction¶

Start by constructing a gtn::Graph and adding nodes and arcs.

Graph graph;

// Add a start node
graph.addNode(true);

// Add an accept node
graph.addNode(false, true);

// Add an internal node
graph.addNode();

// Add an arc from node 0 to 2 with label 0
graph.addArc(0, 2, 0);

// Add an arc from node 0 to 2 with input label 1 and output label 1
graph.addArc(0, 2, 1, 1);

// Add an arc from node 2 to 1 with input label 0, output label 0 and weight 2
graph.addArc(2, 1, 0, 0, 2);

We can visualize the graph with draw().

By default a gtn::Graph requires a gradient. To disable gradient computation use the constructer parameter (e.g. Graph(false)) or the method Graph::setCalcGrad().

Nodes and arcs have unique integer ids in the graph. When you add a node or an arc you can capture the id as the return value. This can make adding arcs from node ids simpler in some cases.

Graph g;
auto n1 = g.addNode();
auto n2 = g.addNode();
auto a1 = g.addArc(n1, n2, 0, 1);

Input and Output¶

The GTN framework provides some convenience functions to visualize graphs. We can print them to stdout or write them to Graphviz’s .dot format with draw().

// print graph to stdout
std::cout << graph << std::endl;

// Draw the graph in dot format to file
draw(graph, "simple_fsa.dot", {{0, "a"}, {1, "b"}, {2, "c"}});

Graph’s in .dot format can be compiled to different images formats. For example, to make a PDF image use

dot -Tpdf graph.dot -o graph.pdf

We can save graphs in binary with save() or as a text file with saveTxt(). Similarly we can load graphs in binary format with load() or from a text file with loadTxt().

// save in binary format
save("myGraph.bin", graph);

// save in text format
saveTxt("myGraph.txt", graph);

// load in binary format
graph = load("myGraph.bin");

// load in text format
graph = loadTxt("myGraph.txt");

We can save and load graphs from input streams as well as files. The text format of the graph is described below.

std::stringstream in(
    // First line is space separated  start states
    "0\n"
    // Second line is space separated accept states
    "1\n"
    // The remaining lines are a list of arcs:
    // <source node> <dest node> <ilabel> [olabel] [weight]
    // where the olabel defaults to the ilabel if it is not specified
    // and the weight defaults to 0.0 if it is not specified.
    "0 2 0\n" // olabel = 0, weight = 0.0
    "0 2 1 1\n" // olabel = 1, weight = 0.0
    "2 1 0 0 2\n"); // olabel = 0, weight = 2.0

Graph other_graph = load(in);

Comparisons¶

There are several ways to compare two graphs in GTN. Use equal() to check for an exact match between two graphs. In this case nodes with the same id should have the same arcs. The function isomorphic() checks that the graph structures are the same regardless of the actual node ids. This can be expensive for large graphs.

WFSAs and WFSTs of different structure can be equivalent in the sense that they accept or transduce the same paths with the same scores. To check this condition, use randEquivalent(). The function randEquivalent() uses a Monte Carlo sampling strategy to assess the equivalence between two graphs and may incorrectly assume the graphs are equivalent if not enough samples are used.

Example Graphs¶

Graphs in GTN can have multiple start and accept nodes. Start nodes have bold circles and accepting nodes are denoted by concentric circles in the figure below.

Graphs can also have cycles, though not every function supports cyclic graphs.

GTN also allows \(\epsilon\) transitions in graphs. Use epsilon to add \(\epsilon\) labels for arcs.

Common Functions¶

GTN supports a range of functions on WFSAs and WFSTs from the simple rational functions like concatenation to the powerful composition operation. Unless explicitly noted, every function in GTN is differentiable with respect to its inputs.

Union¶

Use union_() to compute the union of a std::vector of graphs.

The union of two graphs \(\mathcal{A}_1 + \mathcal{A}_2\) accepts any sequence accepted by either input graph.

_images/union_g1.svg — The `g1` recognizes \(aba^*\).¶

_images/union_g2.svg — The `g2` recognizes \(ba\).¶

_images/union_g3.svg — The graph `g3` recognizes \(ac\).¶

_images/union_graph.svg — The union graph, `union_({g1, g2, g3})`, recognizes any of \(aba^*\), \(ba\), or \(ac\).¶

Concatenation¶

Use concat() to compute the concatenation of two graphs or a std::vector of graphs.

The concatenation of two graphs, \(\mathcal{A}_1\mathcal{A}_2\) accepts any path \({\bf p}{\bf r}\) such that \({\bf p}\) is accepted by \(\mathcal{A}_1\) and \({\bf r}\) is accepted by \(\mathcal{A}_2\).

_images/concat_g1.svg — The graph `g1` recognizes \(ba\).¶

_images/concat_g2.svg — The graph `g2` recognizes \(ac\).¶

_images/concat_graph.svg — The concatenated graph, `concat(g1, g2)`, recognizes \(baac\).¶

Closure¶

Use closure() to compute the Kleene closure of a graph.

The Kleene closure, \(\mathcal{A}^*\), accepts any sequence accepted by the original graph repeated 0 or more times (0 repeats is the empty sequence, \(\epsilon\).).

_images/closure_input.svg — The graph `g` recognizes \(aba\).¶

_images/closure_graph.svg — The closed graph, `closure(g)`, recognizes \(\{aba\}^*\).¶

Intersection¶

Use intersect() to compute the intersection of two acceptors.

The intersection, \(\mathcal{A}_1 \circ \mathcal{A}_2\) accepts any path which is accepted by both input graphs. The score for a path in the intersected graph is the sum of the scores of the path from each input graph.

_images/simple_intersect_g1.svg — Graph `g1`.¶

_images/simple_intersect_g2.svg — Graph `g2`.¶

_images/simple_intersect.svg — The intersected graph, `intersect(g1, g2)`.¶

Compose¶

Use compose() to compute the composition of two transducers.

The composition, \(\mathcal{T}_1 \circ \mathcal{T}_2\) transduces \({\bf p} \rightarrow {\bf u}\) if the first input transduces \({\bf p} \rightarrow {\bf r}\) and the second graph transduces \({\bf r} \rightarrow {\bf u}\). As in intersection, the score of the transduction in the composed graph is the sum of the scores of the transduction from each input graph.

_images/transducer_compose_g1.svg — Graph `g1`.¶

_images/transducer_compose_g2.svg — Graph `g2`.¶

_images/transducer_compose.svg — The composed graph, `compose(g1, g2)`.¶

Forward Score¶

Use forwardScore() to compute the forward score of a graph.

The forward algorithm computes the log-sum-exp of the scores of all accepting paths in a graph. The graph must not have any cycles. Use Graph::item() on the output of forwardScore() to access the score.

_images/simple_forward.svg — The forward score is given by `forwardScore(g)`.¶

In the above example the graph has three paths:

\(0 \rightarrow 1 \rightarrow 2 \rightarrow 3\) with a score of 4.6
\(0 \rightarrow 2 \rightarrow 3\) with a score of 5.3
\(1 \rightarrow 2 \rightarrow 3\) with a score of 3.5

The resulting forward score is \(\log(e^{4.6} + e^{5.3} + e^{3.5}) = 5.81\).

Viterbi Score¶

Use viterbiScore() to compute the Viterbi score of a graph.

The Viterbi algorithm gives the max of the scores of all accepting paths in a graph. The graph must not have any cycles. Use Graph::item() on the output of viterbiScore() to access the score.

The Viterbi score of the figure in the section Forward Score is 5.3, the highest score over all paths.

Viterbi Path¶

Use viterbiPath() to compute the Viterbi path of a graph.

The Viterbi algorithm gives the highest scoring path of all accepting paths in a graph. The graph must not have any cycles. The output of viterbiPath() is a chain graph representing the highest scoring path.

_images/simple_viterbi_path.svg — The Viterbi path of the graph in section Forward Score, computed using `viterbiPath(g)`.¶

Autograd Basics¶

Whenever we apply a function on gtn::Graph (s), if at least one of its inputs requires a gradient, the output gtn::Graph records its inputs, and a method by which to compute its gradient. The gradients are computed with a GradFunc, a function that takes the gradient with respect to the gtn::Graph and computes the gradient with respect to its inputs.

To recursively compute the gradient of a gtn::Graph with respect to all of its inputs in the computation graph, call gtn::backward() on the gtn::Graph. This iteratively computes the gradients by repeatedly applying the chain rule in a reverse topological ordering of the computation graph.

Here is a simple example

auto g1 = Graph(true);
g1.addNode(true);
g1.addNode(false, true);
g1.addArc(0, 1, 0, 0, 1.0);

auto g2 = Graph(false);
g2.addNode(true);
g2.addNode(false, true);
g2.addArc(0, 1, 0, 0, 2.0);

auto g3 = Graph(true);
g3.addNode(true);
g3.addNode(false, true);
g3.addArc(0, 1, 0, 0, 3.0);

auto g4 = negate(subtract(add(g1, g2), g3));

g4.backward();

auto g1Grad = g1.grad(); // g1Grad.item() = -1

auto g3Grad = g3.grad(); // g3Grad.item() = 1

Warning

Calling g2.grad() will throw an exception since calcGrad is set to false for the graph

Retaining the Computation Graph

The gtn::backward() function takes an optional boolean parameter, retainGraph, which is false by default. When the argument is false, each gtn::Graph is cleared from the computation graph during the backward pass as soon as it is no longer needed. This reduces peak memory usage while computing gradients. Setting retainGraph to true is not recommended unless there is a need to call backward multiple times without redoing the forward computation.

Let’s consider the computation graph that is built with the above example

Assuming we need to call gtn::backward() only once on this graph, we can see that the intermediate Graph gSub can be deleted as soon as as the gradients of g3 and gSum are computed. This will happen when retainGraph is set to false.

Interfacing with PyTorch¶

Adding a GTN function or layer to PyTorch is just like adding any custom extension to PyTorch. For the details, take a look at an example which constructs a custom loss function in PyTorch with GTN. We’ll go over the example here at a high-level with attention to the bits specific to GTN.

First declare the class which should inherit from torch.autograd.Function.

class GTNLossFunction(torch.autograd.Function):
    """
    A minimal example of adding a custom loss function built with GTN graphs to
    PyTorch.

    The example is a sequence criterion which computes a loss between a
    frame-level input and a token-level target. The tokens in the target can
    align to one or more frames in the input.
    """

The GTNLossFunction requires static forward and a backward methods. The forward method, with some additional comments, is copied below:

@staticmethod
def forward(ctx, inputs, targets):
    B, T, C = inputs.shape
    losses = [None] * B
    emissions_graphs = [None] * B

    # Move data to the host as GTN operations run on the CPU:
    device = inputs.device
    inputs = inputs.cpu()
    targets = targets.cpu()

    # Compute the loss for the b-th example:
    def forward_single(b):
        emissions = gtn.linear_graph(T, C, inputs.requires_grad)
        # *NB* A reference to the `data` should be held explicitly when
        # using `data_ptr()` otherwise the memory may be claimed before the
        # weights are set. For example, the following is undefined and will
        # likely cause serious issues:
        #   `emissions.set_weights(inputs[b].contiguous().data_ptr())`
        data = inputs[b].contiguous()
        emissions.set_weights(data.data_ptr())

        target = GTNLossFunction.make_target_graph(targets[b])

        # Score the target:
        target_score = gtn.forward_score(gtn.intersect(target, emissions))

        # Normalization term:
        norm = gtn.forward_score(emissions)

        # Compute the loss:
        loss = gtn.subtract(norm, target_score)

        # We need the save the `loss` graph to call `gtn.backward` and we
        # need the `emissions` graph to access the gradients:
        losses[b] = loss
        emissions_graphs[b] = emissions

    # Compute the loss in parallel over the batch:
    gtn.parallel_for(forward_single, range(B))

    # Save some graphs and other data for backward:
    ctx.auxiliary_data = (losses, emissions_graphs, inputs.shape)

    # Put losses back in a torch tensor and move them  back to the device:
    return torch.tensor([l.item() for l in losses]).to(device)

To perform the backward computation, we save losses, a list which holds the individual graphs storing the loss for each example. We also save the emissions_graphs so that we can access the gradients in order to construct the full gradient with respect to the input tensor.

GTN provides parallel_for() to run computations in parallel. We us it here to parallelize the forward computation and backward computations over examples in the batch. Using parallel_for() requires some care. For example notice the lines:

losses = [None] * B
emissions_graphs = [None] * B

These lists must be preconstructed so that threads can insert into the list rather than constructively appending to it, which could cause a race condition during the execution of forward_single.

The backward method is very simple. It just calls backward() on each loss graph and accumulating the gradients into a torch.Tensor.

@staticmethod
def backward(ctx, grad_output):
    losses, emissions_graphs, in_shape = ctx.auxiliary_data
    B, T, C = in_shape
    input_grad = torch.empty((B, T, C))

    # Compute the gradients for each example:
    def backward_single(b):
        gtn.backward(losses[b])
        emissions = emissions_graphs[b]
        grad = emissions.grad().weights_to_numpy()
        input_grad[b] = torch.from_numpy(grad).view(1, T, C)

    # Compute gradients in parallel over the batch:
    gtn.parallel_for(backward_single, range(B))

    return grad_output.unsqueeze(1).unsqueeze(1) * input_grad.to(grad_output.device), None

Graph¶

class Graph¶

A Graph class to perform automatic differentiation with weighted finite-state acceptors (WFSAs) and transducers (WFSTs).

Example:

Graph graph;
graph.addNode(true); // Add a start node
graph.addNode(); // Add an internal node
graph.addNode(false, true); // Add an accept node

// Add an arc from node 0 to 1 with ilabel 0, olabel 1 and weight 2.0
graph.addArc(0, 1, 0, 1, 2.0);

// Add an arc from node 1 to 2 with ilabel 1, olabel 2 and weight 1.0
graph.addArc(1, 2, 1, 2, 1.0);

// Compute the Viterbi score of the graph
auto score = viterbiScore(graph);

print(score); // Print the score graph to std out

backward(score); // Compute the gradient
graph.grad(); // Access the gradient
graph.zeroGrad(); // Clear the gradient

All operations are in the log or tropical semirings. The default score for an arc is 0 (e.g. the multiplicative identity) and the additive identity is -infinity. Path scores are accumulated with log-sum-exp or max operations and the score for a path is accumulated with addition.

Graph-level Methods¶

Graph(bool calcGrad = true)¶

Construct a Graph.

Parameters: calcGrad – Whether or not to compute gradients with respect to this graph when calling gtn::backward.

int addNode(bool start = false, bool accept = false)¶

Adds a node to the graph.

Parameters

start – Indicates if the node is a starting node.
accept – Indicates if the node is an accepting node.

Returns

The id of the node (used for e.g. adding arcs).

size_t addArc(size_t srcNode, size_t dstNode, int label)¶

Add a arc between two nodes.

This assumes the graph is an acceptor, the input label on the arc is the same as the output label.

Parameters

srcNode – The id of the source node.
dstNode – The id of the destination node.
label – The arc label.

Returns

The id of the added arc.

size_t addArc(size_t srcNode, size_t dstNode, int ilabel, int olabel, float weight = 0.0)¶

Add a arc between two nodes.

Parameters

srcNode – The id of the source node.
dstNode – The id of the destination node.
ilabel – The arc input label.
olabel – The arc output label.
weight – The arc weight.

Returns

The id of the added arc.

inline size_t numArcs() const¶: The number of arcs in the graph.

inline size_t numNodes() const¶: The number of nodes in the graph.

inline size_t numStart() const¶: The number of starting nodes in the graph.

inline size_t numAccept() const¶: The number of accepting nodes in the graph.

float item() const¶: Get the weight on a single arc graph.

static Graph deepCopy(const Graph &src)¶

A deep copy of a graph src which is not recorded in the autograd tape.

For a version which is recorded in the autograd tape see gtn::clone.

void arcSort(bool olabel = false)¶

Sort the arcs entering and exiting a node in increasing order by arc in label or out label if olabel == true.

This function is intended to be used prior to calls to intersect and compose to improve the efficiency of the algorithm.

inline void markArcSorted(bool olabel = false)¶

Mark a graph’s arcs as sorted.

If olabel == false then the graph will be marked as sorted by arc input labels, otherwise it will be marked as sorted by the arc output labels.

inline bool ilabelSorted() const¶: Check if the arcs entering and exiting every node are sorted by input label.

inline bool olabelSorted() const¶: Check if the arcs entering and exiting every node are sorted by output label.

inline float *weights()¶

Returns an array of weights from a graph.

The array will contain Graph::numArcs() elements.

inline const float *weights() const¶: A const version of Graph::weights.

void setWeights(const float *weights)¶

Set the arc weights on a graph.

The weights array must have Graph::numArcs() elements.

void labelsToArray(int *out, bool ilabel = true)¶

Extract an array of labels from a graph.

The array should have space for Graph::numArcs() elements.

Parameters

out – [out] A pointer to the buffer to populate with labels.
ilabel – [in] Retreive ilabels if true, otherwise gets olabels.

std::vector<int> labelsToVector(bool ilabel = true)¶

Extract a std::vector of labels from the graph.

See Graph::labelsToArray.

Autograd Methods¶

void addGrad(std::vector<float> &&other)¶

Add a std::vector of gradients to the gradient graph weights without making a copy of other.

The Graph::addGrad methods are intended for use by the autograd. This overload is used with an rvalue or std::move to avoid an extra copy:

graph.addGrad(std::move(graphGrad));

void addGrad(const std::vector<float> &other)¶

Add a std::vector of gradients to the gradient graph weights.

The Graph::addGrad methods are intended for use by the autograd.

void addGrad(const Graph &other)¶

Add a Graph of gradients to the gradient graph.

The Graph::addGrad methods are intended for use by the autograd.

inline bool calcGrad() const¶: Check if a graph requires a gradient.

inline bool isGradAvailable() const¶: Check if a graph’s gradient is computed.

Graph &grad()¶: Get the gradient graph.

const Graph &grad() const¶: A const version of Graph::grad.

void setCalcGrad(bool calcGrad)¶: Specify if the gradient for this graph should be computed.

void zeroGrad()¶: Clear the graph’s gradients.

std::uintptr_t id()¶

A unique identifier for a graph.