ComputationalGraphPrimer (version 1.0.6, 2021-February-22)

ComputationalGraphPrimer.py

Version: 1.0.6

Author: Avinash Kak (kak@purdue.edu)

Date: 2021-February-22

 Download Version 1.0.6: gztar Total number of downloads (all versions): 274      This count is automatically updated at every rotation of      the weblogs (normally once every two to four days)      Last updated: Tue Nov 9 06:09:02 EST 2021

View the main module code file in your browser

CHANGES:

Version 1.0.6:

This version includes a demonstration of how to extend PyTorch's
Autograd class if you wish to customize how the learnable parameters
are updated during backprop on the basis of the data conditions
discovered during the forward propagation.  Previously this material
was in the DLStudio module.

Version 1.0.5:

I have been experimenting with different ideas for increasing the
tutorial appeal of this module.  (That is the reason for the jump in
the version number from 1.0.2 to the current 1.0.5.)  The previous
public version provided a simple demonstration of how one could forward
propagate data through a DAG (Directed Acyclic Graph) while at the same
compute the partial derivatives that would be needed subsequently
during the backpropagation step for updating the values of the
learnable parameters.  In 1.0.2, my goal was just to illustrate what
was meant by a DAG and how to use such a representation for forward
data flow and backward parameter update.  Since I had not incorporated
any nonlinearities in such networks, there was obviously no real
learning taking place.  That fact was made evident by a plot of
training loss versus iterations.

To remedy this shortcoming of the previous public-release version, the
current version introduces two special cases of networks --- a
one-neuron network and a multi-neuron network --- for experimenting
with forward propagation of data while calculating the partial
derivatives needed later, followed by backpropagation of the prediction
errors for updating the values of the learnable parameters. In both
cases, I have used the Sigmoid activation function at the nodes. The
partial derivatives that are calculated in the forward direction are
based on analytical formulas at both the pre-activation point for data
aggregation and the post-activation point.  The forward and backward
calculations incorporate smoothing of the prediction errors and the
derivatives over a batch as required by stochastic gradient descent.

Version 1.0.2:

This version reflects the change in the name of the module that was
initially released under the name CompGraphPrimer with version 1.0.1

INTRODUCTION:

This module was created with a modest goal in mind: its purpose being
merely to serve as a prelude to discussing automatic calculation of the
gradients of the loss with respect to the learnable parameters in
modern Python based platforms for deep learning.

Most students taking classes on deep learning focus on just using the
tools provided by platforms such as PyTorch without any understanding
of how the tools really work.  Consider, for example, Autograd --- a
module that is at the heart of PyTorch --- for automatic
differentiation of the loss at the output of a neural layer with
respect to all the learnable parameters that go into calculating that
output. With no effort on the part of the programmer, and through the
functionality built into the "torch.Tensor" class, the Autograd module
keeps track of a tensor through all calculations involving the tensor
and computes the partial derivatives of the output of the layer with
respect to the parameters stored in the tensor.  These derivatives are
subsequently used to update the values of the learnable parameters
during the backpropagation step.

Now imagine a beginning student trying to make sense of the following
excerpts from the official PyTorch documentation related to Autograd:

"Every operation performed on Tensors creates a new function object,
that performs the computation, and records that it happened. The
history is retained in the form of a DAG of functions, with edges
denoting data dependencies (input <- output). Then, when backward
is called, the graph is processed in the topological ordering, by
calling backward() methods of each Function object, and passing
returned gradients on to next Functions."

and

"Check gradients computed via small finite differences against
analytical gradients w.r.t. tensors in inputs that are of floating

There is a lot going on here: Why do we need to record the history of
the operations carried out on a tensor?  What is a DAG?  What are the
differences?  Analytical gradients of what? etc. etc.

This module has three goals:

1)    To introduce you to forward and backward dataflows in a Directed
Acyclic Graph (DAG).

2)    To extend the material developed for the first goal with simple
examples of neural networks for demonstrating the forward and
backward dataflows for the purpose of updating the learnable
parameters.  This part of the module also includes a comparison
of the performance of such networks with those constructed using
torch.nn components.

3)    To explain how the behavior of PyTorch's Autograd class can
be customized to your specific data needs by extending that
class.

GOAL 1:

The first goal of this Primer is to introduce you to forward and
backward dataflows in a general DAG. The acronym DAG stands for
Directed Acyclic Graph. Just for the educational value of playing with
dataflows in DAGs, this module allows you to create a DAG of variables
with a statement like

expressions = ['xx=xa^2',
'xy=ab*xx+ac*xa',
'xz=bc*xx+xy',
'xw=cd*xx+xz^3']

where we assume that a symbolic name that beings with the letter 'x' is
a variable, all other symbolic names being learnable parameters, and
where we use '^' for exponentiation. The four expressions shown above
contain five variables --- 'xx', 'xa', 'xy', 'xz', and 'xw' --- and
four learnable parameters: 'ab', 'ac', 'bc', and 'cd'.  The DAG that is
generated by these expressions looks like:

________________________________
/                                 \
/                                   \
/             xx=xa**2                v
xa --------------> xx -----------------> xy   xy = ab*xx + ac*xa
| \                   |
|  \                  |
|   \                 |
|    \                |
|     \_____________  |
|                   | |
|                   V V
\                   xz
\                 /    xz = bc*xx + xy
\               /
-----> xw <----

xw  = cd*xx + xz

By the way, you can call 'display_network2()' on an instance of
ComputationalGraphPrimer to make a much better looking plot of the
network graph for any DAG created by the sort of expressions shown
above.

In the DAG shown above, the variable 'xa' is an independent variable
since it has no incoming arcs, and 'xw' is an output variable since it
has no outgoing arcs. A DAG of the sort shown above is represented in
ComputationalGraphPrimer by two dictionaries: 'depends_on' and 'leads_to'.
Here is what the 'depends_on' dictionary would look like for the DAG
shown above:

depends_on['xx']  =  ['xa']
depends_on['xy']  =  ['xa', 'xx']
depends_on['xz']  =  ['xx', 'xy']
depends_on['xw']  =  ['xx', 'xz']

Something like "depends_on['xx'] = ['xa']" is best read as "the vertex
'xx' depends on the vertex 'xa'."  Similarly, the "depends_on['xz'] =
['xx', 'xy']" is best read aloud as "the vertex 'xz' depends on the
vertices 'xx' and 'xy'." And so on.

Whereas the 'depends_on' dictionary is a complete description of a DAG,
for programming convenience, ComputationalGraphPrimer also maintains
another representation for the same graph, as provide by the 'leads_to'
dictionary.  This dictionary for the same graph as shown above would
be:

The "leads_to[xa] = [xx]" is best read as "the outgoing edge at the
node 'xa' leads to the node 'xx'."  Along the same lines, the
edges at the vertex 'xx' lead to the vertices 'xy', 'xz', and 'xw'.

Given a computational graph like the one shown above, we are faced
with the following questions: (1) How to propagate the information
from the independent nodes --- that we can refer to as the input nodes
--- to the output nodes, these being the nodes with only incoming
edges?  (2) As the information flows in the forward direction, meaning
from the input nodes to the output nodes, is it possible to estimate
the partial derivatives that apply to each link in the graph?  And,
finally, (3) Given a scalar value at an output node (which could be
the loss estimated at that node), can the partial derivatives
estimated during the forward pass be used to backpropagate the loss?

Consider, for example, the directed link between the node 'xy' and
node 'xz'. As a variable, the value of 'xz' is calculated through the
formula "xz = bc*xx + xy". In the forward propagation of information,
we estimate the value of 'xz' from currently known values for the
learnable parameter 'bc' and the variables 'xx' and 'xy'.  In addition
to the value of the variable at the node 'xz', we are also interested
in the value of the partial derivative of 'xz' with respect to the
other variables that it depends on --- 'xx' and 'xy' --- and also with
respect to the parameter it depends on, 'bc'.  For the calculation of
the derivatives, we have a choice: We can either do a bit of computer
algebra and figure out that the partial of 'xz' with respect to 'xx'
is equal to the current value for 'bc'.  Or, we can use the small
finite difference method for doing the same, which means that (1) we
calculate the value of 'xz' for the current value of 'xx', on the one
hand, and, on the other, for 'xx' plus a delta; (2) take the
difference of the two; and (3) divide the difference by the delta.
ComputationalGraphPrimer module uses the finite differences method for
estimating the partial derivatives.

Since we have two different types of partial derivatives, partial of a
variable with respect to another variable, and the partial of a
variable with respect a learnable parameter, ComputationalGraphPrimer
uses two different dictionaries for storing this partials during each
forward pass.  Partials of variables with respect to other variables
as encountered during forward propagation are stored in the dictionary
"partial_var_to_var" and the partials of the variables with respect to
the learnable parameters are stored in the dictionary
partial_var_to_param.  At the end of each forward pass, the relevant
partials extracted from these dictionaries are used to estimate the
gradients of the loss with respect to the learnable parameters, as
illustrated in the implementation of the method train_on_all_data().

While the exercise mentioned above is good for appreciating data flows
in a general DAG, you've got to realize that, with today's algorithms,
it would be impossible to carry out any learning in a general DAG.  A
general DAG with millions of learnable parameters would not lend
itself to a fast calculation of the partial derivatives that are
needed during the backpropagation step.  Since the exercise described
above is just to get you thinking about data flows in networks in DAGs
and nothing else, I have not bothered to include any activation
functions in the DAG demonstration code in this Primer.

GOAL 2:

That brings us to the second major goal of this Primer module:

To provide examples of simple neural structures in which the
required partial derivatives are calculated during forward data
propagation and subsequently used for parameter update during the
backpropagation of loss.

In order to become familiar with how this is done in the module, your
best place to start would be the following two scripts in the Examples
directory of the distribution:

one_neuron_classifier.py

multi_neuron_classifier.py

The first script, "one_neuron_classifier.py", invokes the following
function from the module:

run_training_loop_one_neuron_model()

This function, in turn, calls the following functions, the first for
forward propagation of the data, and the second for the
backpropagation of loss and updating of the parameters values:

forward_prop_one_neuron_model()
backprop_and_update_params_one_neuron_model()

The data that is forward propagated to the output node is subject to
Sigmoid activation.  The derivatives that are calculated during
forward propagation of the data include the partial 'output vs. input'
derivatives for the Sigmoid nonlinearity. The backpropagation step
implemented in the second of the two functions listed above includes
averaging the partial derivatives and the prediction errors over a
batch of training samples, as required by SGD.

The second demo script in the Examples directory,
"multi_neuron_classifier.py" creates a neural network with a hidden
layer and an output layer.  Each node in the hidden layer and the node
in the output layer are all subject to Sigmoid activation.
This script invokes the following function of the module:

run_training_loop_multi_neuron_model()

And this function, in turn, calls upon the following two functions,
the first for forward propagating the data and the second for the
backpropagation of loss and updating of the parameters:

forward_prop_multi_neuron_model()
backprop_and_update_params_multi_neuron_model()

In contrast with the one-neuron demo, in this case, the batch-based
data that is output by the forward function is sent directly to the
backprop function.  It then becomes the job of the backprop function
to do the averaging needed for SGD.

In the Examples directory, you will also find the following script:

verify_with_torchnn.py

The idea for this script is to serve as a check on the performance of
the main demo scripts "one_neuron_classifier.py" and
"multi_neuron_classifier.py".  Note that you cannot expect the
performance of my one-neuron and multi-neuron scripts to match what
you would get from similar networks constructed with components drawn
from "torch.nn".  One primary reason for that is that "torch.nn" based
code uses the state-of-the-art optimization of the steps in the
parameter hyperplane, with is not the case with my demo scripts.
Nonetheless, a comparison with the "torch.nn" is important for general
trend of how the training loss varies with the iterations.  That is,
if the "torch.nn" based script showed decreasing loss (indicated that
learning was taking place) while that was not the case with my
one-neuron and multi-neuron scripts, that would indicate that perhaps
I had made an error in either the computation of the partial derivatives
during the forward propagation of the data, or I had used the
derivatives for updating the parameters.

GOAL 3:

The goal here is to show how to extend PyTorch's Autograd class if you
want to endow it with additional functionality. Let's say that you
wish for some data condition to be remembered during the forward
propagation of the data through a network and then use that condition
to alter in some manner how the parameters would be updated during
backpropagation of the prediction errors.  This can be accomplished by
subclassing from Autograd and incorporating the desired behavior in
the subclass.  As to how how you can extend Autograd is demonstrated
by the inner class AutogradCustomization in this module. Your starting
point for understanding what this class does would be the script

in the Examples directory of the distribution.

INSTALLATION:

The ComputationalGraphPrimer class was packaged using setuptools.  For
installation, execute the following command in the source directory
(this is the directory that contains the setup.py file after you have

sudo python3 setup.py install

On Linux distributions, this will install the module file at a location
that looks like

/usr/local/lib/python3.8/dist-packages/

If you do not have root access, you have the option of working directly
placing the following statements at the top of your scripts that use
the ComputationalGraphPrimer class:

import sys
sys.path.append( "pathname_to_ComputationalGraphPrimer_directory" )

To uninstall the module, simply delete the source directory, locate
where the ComputationalGraphPrimer module was installed with "locate
ComputationalGraphPrimer" and delete those files.  As mentioned above,
the full pathname to the installed version is likely to look like
"/usr/local/lib/python3.8/dist-packages/".

If you want to carry out a non-standard install of the
ComputationalGraphPrimer module, look up the on-line information on
Disutils by pointing your browser to

http://docs.python.org/dist/dist.html

USAGE:

Construct an instance of the ComputationalGraphPrimer class as follows:

from ComputationalGraphPrimer import *

cgp = ComputationalGraphPrimer(
expressions = ['xx=xa^2',
'xy=ab*xx+ac*xa',
'xz=bc*xx+xy',
'xw=cd*xx+xz^3'],
output_vars = ['xw'],
dataset_size = 10000,
learning_rate = 1e-6,
display_loss_how_often = 1000,
)

cgp.parse_expressions()
cgp.display_network2()
cgp.gen_gt_dataset(vals_for_learnable_params = {'ab':1.0, 'bc':2.0, 'cd':3.0, 'ac':4.0})
cgp.train_on_all_data()
cgp.plot_loss()

CONSTRUCTOR PARAMETERS:

batch_size: Introduced in Version 1.0.5 for demonstrating forward
propagation of the input data while calculating the
partial derivatives needed during backpropagation of
loss. For SGD, updating the parameters involves
smoothing the derivatives over the training samples in
a batch. Hence the need for batch_size as a constructor
parameter.

dataset_size: Although the networks created by an arbitrary set of
expressions are not likely to allow for any true
learning of the parameters, nonetheless the
ComputationalGraphPrimer allows for the computation of
the loss at the output nodes and backpropagation of the
loss to the other nodes.  To demonstrate this, we need
a ground-truth set of input/output values for given
value for the learnable parameters.  The constructor
parameter 'dataset_size' refers to how may of these
'input/output' pairs would be generated for such
experiments.

For the one-neuron and multi-neuron demos introduced in
Version 1.0.5, the constructor parameter dataset_size
refers to many tuples of randomly generated data should
be made available for learning. The size of each data
tuple is deduced from the the first expression in the
list made available to module through the parameter
'expressions' described below.

display_loss_how_often: This controls how often you will see the result
of the calculations being carried out in the
computational graph.  Let's say you are experimenting
with 10,000 input/output samples for propagation in the
network, if you set this constructor option to 1000,
you will see the partial derivatives and the values for
the learnable parameters every 1000 passes through the
graph.

expressions: These expressions define the computational graph.  The
expressions are based on the following assumptions: (1)
any variable name must start with the letter 'x'; (2) a
symbolic name that does not start with 'x' is a
learnable parameter; (3) exponentiation operator is
'^'; (4) the symbols '*', '+', and '-' carry their
usual arithmetic meanings.

grad_delta: This constructor option sets the value of the delta to be
used for estimating the partial derivatives with the
finite difference method.

layers_config: Introduced in Version 1.0.5 for the multi-neuron
demo. Its value is a list of nodes in each layer of the
network. Note that I consider the input to the neural
network as a layer unto itself.  Therefore, if the
value of the parameter num_layers is 3, the list you
supply for layers_config must have three numbers in it.

learning_rate: Carries the usual meaning for updating the values of the
learnable parameters based on the gradients of the loss
with respect to those parameters.

num_layers: Introduced in Version 1.0.5 for the multi-neuron demo. It
is merely a convenience parameter that indicated the
number of layers in your multi-neuron network. For the
purpose of counting layers, I consider the input as a
layer unto itself.

one_neuron_model: Introduced in Version 1.0.5.  This boolean parameter
is needed only when you are constructing a one-neuron
demo. I needed this constructor parameter for some
conditional evaluations in the "parse_expressions()"
method of the module.  I use that expression parser for
both the older demos and the new demo based on the
one-neuron model.

output_vars: Although the parser has the ability to figure out which
nodes in the computational graph represent the output
variables --- these being nodes with no outgoing arcs
--- you are allowed to designate the specific output
variables you are interested in through this
constructor parameter.

training_iterations: Carries the expected meaning.

PUBLIC METHODS:

(1)  backprop_and_update_params_one_neuron_model():

Introduced in Version 1.0.5.  This method is called by
run_training_loop_one_neuron_model() for backpropagating the loss
and updating the values of the learnable parameters.

(2)  backprop_and_update_params_multi_neuron_model():

Introduced in Version 1.0.5.  This method is called by
run_training_loop_multi_neuron_model() for backpropagating the
loss and updating the values of the learnable parameters.

(3)  display_network2():

This method calls on the networkx module to construct a visual
display of the computational graph.

(4)  forward_propagate_one_input_sample_with_partial_deriv_calc():

This method is used for pushing the input data forward through a
general DAG and at the same computing the partial derivatives that
would be needed during backpropagation for updating the values of
the learnable parameters.

(5)  forward_prop_one_neuron_model():

Introduced in Version 1.0.5.  This function propagates the input
data through a one-neuron network.  The data aggregated at the
neuron is subject to a Sigmoid activation.  The function also
calculates the partial derivatives needed during backprop.

(6)  forward_prop_multi_neuron_model():

Introduced in Version 1.0.5. This function does the same thing as
the previous function, except that it is intended for a multi-layer
neural network. The pre-activation values at each neuron are
subject to the Sigmoid nonlinearity. At the same time, the partial
derivatives are calculated and stored away for use during backprop.

(7)  gen_gt_dataset()

This method generates the training data for a general graph of
nodes in a DAG. For random values at the input nodes, it
calculates the values at the output nodes assuming certain given
values for the learnable parameters in the network. If it were
possible to carry out learning in such a network, the goal would
to see if the value of those parameters would be learned
automatically as in a neural network.

(8)  gen_training_data():

Introduced in Version 1.0.5. This function generates training data
for the scripts "one_neuron_classifier.py",
"multi_neuron_classifier.py" and "verify_with_torchnn.py" scripts
in the Examples directory of the distribution.  The data
corresponds to two classes defined by two different multi-variate
distributions. The dimensionality of the data is determined
entirely the how many nodes are found by the expression parser in
the list of expressions that define the network.

(9)  parse_expressions()

This method parses the expressions provided and constructs a DAG
from them for the variables and the parameters in the expressions.
It is based on the convention that the names of all variables
begin with the character 'x', with all other symbolic names being
treated as learnable parameters.

(10) parse_multi_layer_expressions():

Introduced in Version 1.0.5. Whereas the previous method,
parse_expressions(), works well for creating a general DAG and for
the one-neuron model, it is not meant to capture the layer based
structure of a neural network.  Hence this method.

(11) run_training_loop_one_neuron_model():

Introduced in Version 1.0.5.  This is the main function in the
module for the demo based on the one-neuron model. The demo
consists of propagating the input values forward, aggregating them
at the neuron, and subjecting the result to Sigmoid activation.
All the partial derivatives needed for updating the link weights
are calculating the forward propagation.  This includes the
derivatives of the output vis-a-vis the input at the Sigmoid
activation.  Subsequently, during backpropagation of the loss, the
parameter values are updated using the derivatives stored away
during forward propagation.

(12) run_training_loop_multi_neuron_model()

Introduced in Version 1.0.5.  This is the main function for the
demo based on a multi-layer neural network.  As each batch of
training data is pushed through the network, the partial derivatives
of the output at each layer is computed with respect to the
parameters. This calculating includes computing the partial
derivatives at the output of the activation function with respect
to its input.  Subsequently, during backpropagation, first
batch-based smoothing is applied to the derivatives and the
prediction errors stored away during forward propagation in order
to comply with the needs of SGD and the values of the learnable
parameters updated.

(13) run_training_with_torchnn():

Introduced in Version 1.0.5.  The purpose of this function is to
use comparable network components from the torch.nn module in
order to "authenticate" the performance of the handcrafted
one-neuron and the multi-neuron models in this module.  All that
is meant by "authentication" here is that if the torch.nn based
networks show the training loss decrease with iterations, you
would the one-neuron and the multi-neuron models to show similar
results.  This function contains the following inner classes:

class OneNeuronNet( torch.nn.Module )

class MultiNeuronNet( torch.nn.Module )

that define networks similar to the handcrafted one-neuron and
multi-neuron networks of this module.

(14) train_on_all_data()

The purpose of this function is to call forward propagation and
backpropagation functions of the module for the demo based on
arbitrary DAGs.

(15) plot_loss()

This is only used by the functions that DAG based demonstration code
in the module.  The training functions introduced in Version 1.0.5 have
embedded code for plotting the loss as a function of iterations.

THE Examples DIRECTORY:

The Examples directory of the distribution contains the following the
following scripts:

1.   graph_based_dataflow.py

This demonstrates forward propagation of input data and
backpropagation in a general DAG (Directed Acyclic Graph).
The forward propagation involves estimating the partial
derivatives that would subsequently be used for "updating" the
learnable parameters during backpropagation.  Since I have not
incorporated any activations in the DAG, you can really not
expect any real learning to take place in this demo.  The
purpose of this demo is just to illustrate what is meant by a
DAG and how information can flow forwards and backwards in
such a network.

2.   one_neuron_classifier.py

This script demonstrates the one-neuron model in the module.
The goal is to show forward propagation of data through the
neuron (which includes the Sigmoid activation), while
calculating the partial derivatives needed during the
backpropagation step for updating the parameters.

3.   multi_neuron_classifier.py

This script generalizes what is demonstrated by the one-neuron
model to a multi-layer neural network.  This script
demonstrates saving the partial-derivative information
calculated during the forward propagation through a
multi-layer neural network and using that information for
backpropagating the loss and for updating the values of the
learnable parameters.

4.   verify_with_torchnn.py

The purpose of this script is just to verify that the results
obtained with the scripts "one_neuron_classifier.py" and
"multi_neuron_classifier.py" are along the expected lines.
That is, if similar networks constructed with the torch.nn
module show the training loss decreasing with iterations, you
would expect the similar learning behavior from the scripts
"one_neuron_classifier.py" and "multi_neuron_classifier.py".

This provides a demo example of the recommended approach for
explanation in the doc section associated with the inner
class AutogradCustomization of this module for further info.

BUGS:

Please notify the author if you encounter any bugs.  When sending
email, please place the string 'ComputationalGraphPrimer' in the
subject line to get past the author's spam filter.

The author, Avinash Kak, is a professor of Electrical and Computer
Engineering at Purdue University.  For all issues related to this
module, contact the author at kak@purdue.edu If you send email, please
place the string "ComputationalGraphPrimer" in your subject line to get
past the author's spam filter.

@endofdocs

Modules

 copy math numpy networkx operator os matplotlib.pyplot random re sys torch

Classes

builtins.object
ComputationalGraphPrimer
Exp