Speaker
Description
PyTorch is a production-ready framework for machine learning in
Python, offering a robust ecosystem and a large community behind. It
takes advantage of GPUs, HPC, and cloud environments. While primarily
aimed for machine learning applications, it includes tools for a broad
area of numerical applications, including, e.g. linear algebra,
tensors, random numbers, statistics, optimization, etc. In spite of
that the coverage of methods and the structure of the package is
strongly aimed at ML applications, it has potential applications in
many other fields. The benefits of such an approach include the
possibility of exploiting extensive computer resources via codes that
are simply and quickly developed in Python.
In this talk I present in detail a PyTorch-based example of graph
coloring using the stochastic gradient descent (SGD) algorithm in
order to demonstrate such a use case. While the primary use of SGD and
its modified versions in AI is to optimize neural network parameters
during the “training” phase, the user can also use SGD to minimize a
custom objective function if it can be defined within the PyTorch
framework.
The objective function of our example is defined as follows. Let $A$ be
the $m\times m$ adjacency matrix of a finite, loopless planar graph. Let $C$ be
an $m\times n$ matrix, where each row represents a vertex and each row vector
is a one-hot encoded color vector candidate. Then the objective
function to be minimized w.r.t $C$ is
$$L(C)=\sum \sum \left[ C C^\top \circ A\right]$$
As for the algorithm, initially, fill $C$ with i.i.d. random
numbers. Then we apply row-wise softmax normalization after each
update on $C$ to ensure one-hot encoding for row vectors. The
presented algorithm is heuristic as it does not guarantee convergence
to an optimal coloring. Yet it demonstrates the simplicity of
implementing such an algorithm with PyTorch.
