# Gradient-Free Neural Network Training via Synaptic-Level Reinforcement
Learning

Aman Bhargava
Division of Engineering Science
University of Toronto
Toronto, Ontario M5S 2E4, Canada
<EMAIL_ADDRESS>
&Mohammad R. Rezaei
Department of Biomedical Engineering
University of Toronto
Toronto, ON M5S 3G9, Canada
<EMAIL_ADDRESS>
&Milad Lankarany
Division of Clinical and Computational Neuroscience,
Krembil Brain Institute, University Health Network
60 Leonard Ave, Toronto, Ontario M5T 0SB, Canada
<EMAIL_ADDRESS>

###### Abstract

An ongoing challenge in neural information processing is: how do neurons
adjust their connectivity to improve task performance over time (i.e.,
actualize learning)? It is widely believed that there is a consistent,
synaptic-level learning mechanism in specific brain regions, such as the basal
ganglia, that actualizes learning. However, the exact nature of this mechanism
remains unclear. Here we investigate the use of universal synaptic-level
algorithms in training connectionist models. Specifically, we propose an
algorithm based on reinforcement learning (RL) to generate and apply a simple
biologically-inspired synaptic-level learning policy for multi-layer
perceptron (MLP) models. In this algorithm, the action space for each MLP
synapse consists of a small increase, decrease, or null action on the synapse
weight, and the state for each synapse consists of the last two actions and
global reward signals. A binary reward signal indicates either an increase or
decrease in the model loss between the previous two iterations. This algorithm
yields a static synaptic learning policy that enables simultaneous training of
over 20,000 parameters (i.e. synapses) and consistent MLP convergence when
applied to simulated decision boundary matching and optical character
recognition tasks. The static policy is robust as it produces faster and more
consistent training relative to the adaptive policy and is agnostic to
activation function, network shape, and task. The trained networks yield
character recognition performance comparable to identically shaped networks
trained with gradient descent. 0 hidden unit character recognition tests
yielded an average validation accuracy of 88.28%, 1.86$\pm$0.47% higher than
the same MLP trained with gradient descent. 32 hidden unit character
recognition tests yielded an average validation accuracy of 88.45%,
1.11$\pm$0.79% lower than the same MLP trained with gradient descent. The
approach has two significant advantages in comparison to traditional gradient
descent-based optimization methods. First, the robustness of our novel method
and lack of reliance on gradient computations opens the door to new techniques
for training difficult-to-differentiate artificial neural networks such as
spiking neural networks (SNNs) and recurrent neural networks (RNNs). Second,
the method’s simplicity provides a unique opportunity for further development
of local rule-driven multi-agent connectionist models for machine intelligence
analogous to cellular automata.

##  1 Introduction

Understanding the method by which biological neurons adjust their connectivity
to actualize learning has major consequences for neuroscience and machine
learning (ML) alike [1, 31]. For ML, it would enable highly parallelizable and
robust connectionist models that do not rely on traditional gradient descent
and backpropagation methods. In neuroscience, it would improve the
understanding of fundamental requirements for effective neural computation
[28]. However, this problem has proven challenging when investigated via
analysis and modelling of biological neuron behavior as well as via the
generation of computational models of more abstracted connectionist systems
[21, 30, 5, 20]. Here, we briefly introduce efforts to date from biologically-
and computationally-motivated lines of research in this problem.

Biologically-motivated neuroscientific studies in this research area
frequently focus on pathways between the cortex, basal ganglia, and thalamus
(known as CBGT pathways) [12, 22]. It is understood that this brain region is
deeply involved with action selection in decision making tasks, and that
connectivity adjusts over time to maximize a dopaminergic reward signal [7].
The major unanswered question on the mechanism behind this phenomena is: how
is “credit” assigned to any one neuron or synapse in order to inform
subsequent adjustments in connectivity [26]? Since the reward signal, action
selection, and pathway connectivity changes are spatially and temporally
distant from each other, researchers have struggled to find an effective,
cohesive solution to this credit assignment problem. Studies are further
complicated by the difficulty of simulating large networks of biologically
realistic neuron models [10]. Over time, research in this area has broadly
converged to the hypothesis that some consistent synaptic-level RL algorithm
is employed in these brain regions to actualize learning [26].

Computationally-motivated studies on abstracted connectionist models in this
area apply RL or related techniques to train neural network models [21, 5, 30,
20]. Within these studies, neurons are generally framed as RL agents in a
partially observable Markov decision process (POMDP) with a reward signal
based on network performance on a task. The works differ in terms of their
formulation of the agents’ state spaces, and some introduce competing reward
schemas [21] to incentivize biological realism. However, key issues were
observed in the art that either place the “weight” of the learning task’s
challenge on existing non-biologically-feasible techniques and/or mis-
formulate each neuron’s action space. For example, [21] models each neuron as
a deep Q-learning neural network optimized using gradient descent (policy
gradient) methods. The network is then evaluated on OpenAI’s Cartpole, a
standard task for deep Q-learning neural networks trained using policy
gradient methods [2, 29]. Both [21, 5] also frame the action space for each
neuron as “fire” or “not fire” rather than as a set of actions to alter
synaptic connectivity, an approach that is unsupported by the neuroscientific
and modern machine learning literature. [21, 5, 30, 20] all train separate
policies for each neuron/weight rather than training the same policy to be
applied by all synapses, as suggested by the neuroscientific literature
discussed above. In general, moderate success in network training was achieved
in these works.

We proposed the following high-level design changes:

  1. 1.

Frame the fundamental RL agent as the synapse rather than the neuron.

  2. 2.

Train and apply the same synaptic RL policy on all synapses.

  3. 3.

Set the action space for each synapse to consist of a small increment, a small
decrement, and null action on the synapse weight.

  4. 4.

Represent synapse state as the last $n$ synapse actions and rewards.

  5. 5.

Use a universal binary reward at each time step representing whether MLP
training loss increased or decreased between the most recent two iterations.

This formulation makes the problem computationally and statistically feasible,
particularly for large networks. Training and applying the same synaptic
policy for all synapses provides more data to inform the single policy which
leads to higher chance of convergence and lower chance of overfitting for a
given policy form [27, 29]. Choosing the synapse as the fundamental
reinforcement learning agent also simplifies the action space as biological
neurons can have thousands of synapses [14], and MLPs trained on standard
tasks such as optical character recognition can have an arbitrarily high
number of synapses per neuron depending on the hidden layer(s) size. A naïve
approach for updating neuron connectivity would yield an action space for each
neuron with dimensionality on the same order as the layer size.

While the neuroscientific literature suggests a larger and potentially more
complicated synapse state space and reward signal that includes additional
factors such as neuron/synapse activity [26, 4], we find that this simple
formulation enables surprisingly effective MLP training, particularly when a
static (learned) synaptic learning policy is applied. This static policy
enables the simultaneous training of over 20,000 parameters and consistently
converged for random decision boundary matching and optical character
recognition tasks on the notMNIST dataset [3]. The learned networks also
produce character recognition performance on par with identically shaped
networks trained with gradient descent. 0 and 32 hidden unit OCR MLPs were
trained 5 times using both the proposed synaptic RL method and gradient
descent. The 0 hidden unit synaptic RL MLPs yielded a mean final validation
accuracy of 88.28$\pm$0.41% while the 0 hidden unit gradient descent trained
MLPs yielded 86.42$\pm$0.22% final validation accuracy. The 32 hidden unit
synaptic RL tests had mean validation accuracy 88.45$\pm$0.6% while the 32
hidden unit gradient descent tests had 89.56$\pm$0.52% mean validation
accuracy.

##  2 Approach

We seek to understand the extent to which reinforcement learning methods can
be applied to the generation of a synaptic-level policy for training MLPs.
While MLPs pale in comparison to the complexity of biological neuronal
networks, they offer an easily simulated abstract connectionist model that
shares some high-level properties with biological neurons [25]. The form of
the proposed synaptic-level learning algorithm is informed by several
hypotheses about biological neurons. Since biological neurons are single cells
with limited computational capacity [19], we hypothesize that each synapse in
a biological neural network applies a relatively simple policy to adjust its
connectivity over time. This policy takes into account information including
global reward signals (e.g., dopaminergic signals) and the synapse’s own past
changes in connectivity to inform subsequent changes in connectivity. We
suspect that the policy applied by each synapse is roughly the same in a given
brain region, and that differences in behaviour and connectivity arise from
differences in local information, not from the application of an entirely
different policy. This policy results in the maximization of some reward
signal over time.

Given these hypotheses, we frame the problem as a POMDP with synapses as the
fundamental reinforcement learning (RL) agents. In this work, we apply the
temporal difference learning update equations to learn the $Q$-function for
training the synapses of MLP neural networks. We test the applicability and
generalizability of this method on simulated data and optical character
recognition tasks.

###  2.1 MLP notation

The following notation is used for MLPs [13, 27]:

  * •

$d$: Dimensionality of the original data vectors.

  * •

$N$: Number of data vectors $\vec{x}$ and labels $y$ in the training dataset.

  * •

$\vec{x}\in\mathbb{R}^{d+1}$: Data vectors, assumed to already be augmented
with $1$’s in the first index for the bias term.

  * •

$y$: Data vector label.

  * •

$\hat{y}$: Predicted data vector label using neural network model.

  * •

$\vec{w}^{(i,j)}$: The $i$th neuron’s weight vector in layer $j$.

  * •

$\theta(\cdot)$: Activation function (e.g.,
$\tanh(\cdot),\text{ReLU}(\cdot)$).

  * •

$\mathcal{L}(y,\hat{y})$: Loss function (generally Euclidean distance or Cross
Entropy loss).

Each scalar component of a neuron weight vector $\vec{w}^{(i,j)}$ represents a
synapse. At each non-terminal layer in the network, the activation function
$\theta(\cdot)$ is applied element-wise to previous layer output and a bias
term is prepended to the resulting vector. During network training, parameters
$\vec{w}^{(i,j)}$ are estimated in order to minimize $\mathcal{L}(\hat{y},y)$.

Datasets $(X,Y)$ are composed of a matrix of data vectors $X$ and a matrix of
data labels $Y$ as follows:

$X=\begin{bmatrix}\vrule&&\vrule\\\ \vec{x}^{(1)}&\dots&\vec{x}^{(N)}\\\
\vrule&&\vrule\\\ \end{bmatrix};\,\,\,\,Y=\begin{bmatrix}\vrule&&\vrule\\\
\vec{y}^{(1)}&\dots&\vec{y}^{(N)}\\\ \vrule&&\vrule\end{bmatrix}$ (1)

###  2.2 Synaptic reinforcement learning

Gradient-based approaches for inferring MLP parameters $\vec{w}^{(i,j)}$
require propagation of error signals backward throughout the network and are
not easily observed in biological neural networks [31]. We frame this problem
as a multi-agent RL problem in a POMDP as follows: Each synapse is treated as
an RL agent that executes the same policy. This policy maps synapse state to
actions (i.e., to alter the synapse weight). The temporal difference update
equation is applied to deduce the $Q$-function such that total reward is
maximized over time [27, 29].

At discrete time steps, we define the following for the proposed synaptic RL
model:

  1. 1.

Actions: Each synapse can either increment, decrement, or maintain its value
by some small synaptic learning rate $\alpha_{s}>0$.

$a_{t}\in\mathcal{A}=\\{-\alpha_{s},0,+\alpha_{s}\\}$ (2)

Weight update for a given synapse $k$ in neuron $i$ and layer $j$ is thus
given as:

$w_{k}^{(i,j)}\leftarrow w_{k}^{(i,j)}+w_{k}^{(i,j)}.a_{t}$ (3)

  2. 2.

Reward: Reward is defined in terms of the training loss at the previous two
time steps. Decreased loss is rewarded while increased or equivalent loss is
penalized.

$\begin{split}R_{t}&=\text{sign}(\mathcal{L}_{t-1}-\mathcal{L}_{t})\\\
&={\begin{cases}+1\text{ if }\mathcal{L}_{t-1}>\mathcal{L}_{t}\\\ -1\text{ if
}\mathcal{L}_{t-1}\leq\mathcal{L}_{t}\end{cases}}\end{split}$ (4)

  3. 3.

State: Each synapse $w_{k}^{(i,j)}$ “remembers” its previous two actions and
the previous two global network rewards.

$w_{k}^{(i,j)}.s_{t}=\\{a_{t-1},a_{t-2},R_{t-1},R_{t-2}\\}$ (5)

  4. 4.

Policy: The $Q$ function gives the expected total reward of a given state-
action pair $(s_{t},a)$ assuming that all future actions correspond to the
highest $Q$-value for the given future state [27]. The epsilon-greedy synaptic
policy $\pi(s_{t})$ returns the action $a\in\mathcal{A}$ with the highest
$Q$-value with probability $(1-\epsilon)$. Otherwise, a random action is
returned [29].

$\begin{split}Q(s_{t},a)&=R_{t+1}+\gamma\max_{a^{\prime}}Q(s_{t+1},a^{\prime})\\\
\pi(s_{t})&=\begin{cases}\arg\max_{a\in\mathcal{A}}Q(s_{t},a)&\text{
with}\Pr=1-\epsilon\\\ \text{random-uniform}(a\in\mathcal{A})&\text{
with}\Pr=\epsilon\end{cases}\end{split}$ (6)

Where $\gamma\in[0,1]$ is the discount for future reward and
$\epsilon\in[0,1]$ is the “exploration probability” of the policy. If the $Q$
function is accurate, then $\pi(s_{t})$ will return the optimal action
$a^{*}_{t}$ subject to discount factor $\gamma$. Since the state and action
spaces in this formulation have low dimensionality, the $Q$ function (and by
extension the policy $\pi$) can be implemented as lookup tables of finite
size.

###  2.3 Training

In this study, $Q$-value learning is generally a two-fold process where neural
network parameters $\vec{w}$ are trained at the same time as the $Q$ function
and, by extension, policy $\pi$. After a policy $\pi$ has been generated, it
can also be applied statically. During policy training, the $Q$-values are
updated using the following temporal difference learning update equation for
$Q$-learning [29]:

$Q(s_{t},a_{t})\leftarrow
Q(s_{t},a_{t})+\alpha_{q}[R_{t+1}+\gamma\max_{a^{\prime}}(Q(s_{t+1},a^{\prime})-Q(s_{t},a_{t}))]$
(7)

Where $\alpha_{q}>0$ is the Q-learning rate. The training pseudocode is as
follows:

Input : $Q$ function, dataset $(X,Y)$, iterations,
$\epsilon,\alpha_{s},\alpha_{q},\gamma$, MLP NET, boolean Train-Policy

Output : $Q$ function, updated NET

$\text{old-loss}\leftarrow\mathcal{L}(Y,\textit{NET}(X))$;

for  _$t=1\dots\text{iterations}$_ do

for  _each synapse $w$ in NET_ do

$w.a_{t}\leftarrow\pi(w.s_{t})$;

$w\leftarrow w+w.a_{t}$;

end for

$\text{new-loss}\leftarrow\mathcal{L}(Y,\textit{NET}(X))$;

$R_{t}\leftarrow\text{sign}(\text{old-loss}-\text{new-loss})$;

Update each $w.s$ with new global reward $R_{t}$;

if  _Train-Policy_ then

for  _each synapse $w$ in NET_ do

Apply temporal difference update equation $(7)$ to update $Q$ using $w.s_{t}$,
$w.a_{t}$, $w.s_{t-1}$, $w.a_{t-1}$, and $R_{t}$.

end for

end if

end for

return $Q,\textit{NET}$

Algorithm 1 Synaptic RL Training Algorithm.

##  3 Experiments & results

To determine the efficacy of the proposed synaptic RL technique for MLP
training, learning tasks of increasing complexity and dimensionality are
employed, starting with random 2D decision boundary matching. Once a static
synaptic learning policy is trained on this task, it is re-applied to a
different decision boundary task as well as optical character recognition
tasks with different network shapes and activation functions. Experiments are
run on an AMD Ryzen 9 5900x 4th generation processor.

#### MLP binary classification matching on $\mathbb{R}^{2}$:

Non-linear 2D decision boundaries are generated by randomly instantiating MLPs
with 2 input neurons, 100 hidden units, and 1 output neuron. If the output
neuron produces a value greater than zero, the point is classified in the
positive class, and vice versa. Synapse weights for the “target” MLP are
uniformly sampled in the range $[-1,1]$ and bias terms are set to $0$. Data
vector values are uniformly sampled in the range $[-10,10]$. 2000 data vectors
are used in training. The goal of this matching task is to train another MLP
of the same size to produce the same classifications as the “target” MLP on
the random data vectors (i.e., match the decision boundary). Two experiments
are highlighted in Figs. 1(a)-1(b). Fig. 1(a) shows results from simultaneous
policy and network training while Fig. 1(b) shows results from applying the
policy learned in Fig. 1(a) to a new decision boundary matching problem. All
hyperparameters are consistent between the two experiments.

(a) Adaptive policy applied to 2D decision boundary matching task. Exploration
probability $\epsilon$ is set to $25\%$, Q-learning rate $\alpha_{q}=0.01$,
synaptic learning rate $\alpha_{s}=0.001$, and future reward discount
$\gamma=0.9$. $\tanh$ activation functions were used in both the trained and
target networks. Final accuracy is $95.9\%$ while final mean Euclidean loss
across the dataset is $0.004023$.

(b) Static synaptic policy applied to 2D decision boundary matching task.
Exploration probability $\epsilon$ is set to $25\%$, synaptic learning rate
$\alpha_{s}=0.001$, and future reward discount $\gamma=0.9$. $\tanh$
activation functions were used in both the trained and target networks. Final
accuracy is $97.7\%$ while final mean Euclidean loss across the dataset is
$0.003411$.

Figure 1: Adaptive and static policy applied to decision boundary matching
task.

When the synaptic RL policy was trained simultaneously with the network,
convergence reliably occurred within 10,000 iterations (Fig. 1(a)). When a
static synaptic RL policy from an MLP matching task was re-applied,
convergence occurred slightly more quickly and smoothly (Fig. 1(b)).

#### Optical character recognition on the notMNIST dataset:

The notMNIST dataset is composed of 10 classes of 28x28 greyscale images of
typeset characters in a variety of fonts. There are 18,720 labeled images in
the dataset, and one-hot encoding is used for the training labels. Cross
entropy loss and ReLU activation functions are used for all trials, and a
75-25% randomized train-validation split is used for each experiment. Networks
with $0$ and $32$ hidden units are trained using both the proposed synaptic RL
method and with gradient descent. Hyperparameters for both training methods
are manually tuned. The static policy generated in Fig. 1(a) is applied in all
synaptic RL OCR trials. All experiments are run 5 times with validation
accuracy statistics shown in Table 1. Estimated runtime for each individual
experiment run, along with the number of trainable parameters, is reported in
Table 1 as well.

Table 1: notMNIST OCR validation accuracy comparison Experiment | Min | Max | Mean | Stdev | Est. Runtime | Params
---|---|---|---|---|---|---
Syn. RL 32 HU | 89.12% | 89.12% | 88.45% | 0.60% | 5.5 hours | 25,450
Grad. Desc. 32 HU | 88.57% | 90.00% | 89.56% | 0.52% | 20 minutes | 25,450
Syn. RL 0 HU | 87.65% | 88.84% | 88.28% | 0.41% | 1.5 hours | 7,850
Grad. Desc. 0 HU | 86.11% | 86.73% | 86.42% | 0.22% | 5 minutes | 7,850

To improve runtime for synaptic-level reinforcement learning experiments,
minibatching is used wherein a random subset of the data was re-selected to
train on at regular intervals. Batches composed of 5000 training data samples
are re-selected every 5000 iterations for all synaptic reinforcement learning
experiments. This approach is founded on the premise that prediction error on
a sufficiently large subset of the training dataset likely reflects prediction
error on the full set (as in stochastic gradient descent) [13]. Exploration
probability $\epsilon=0.1$ and synaptic learning rate $\alpha_{s}=0.0001$. For
the 32 hidden unit experiments, the learning rate $\alpha_{s}$ is reduced to
$0.00005$ (i.e., reduced by half) at iteration 60,000 to promote network
convergence. 32 hidden unit networks are trained for 500,000 iterations and 0
hidden unit networks are trained for 200,000 iterations.

For the gradient descent experiments, batch gradient descent is employed with
learning rate $\alpha=0.1$. No regularization, momentum, or mini-batching is
used. Duration of training and learning rate is tuned such that the models
train to completion (i.e., plateauing validation loss and accuracy). A
comparison of training and validation loss and accuracy plots from 32 hidden
unit experiments can be seen in Fig 2.

Figure 2:  Training curves from single trials from the 32 hidden unit synaptic
RL and gradient descent experiments.

Taking the difference between mean validation accuracy for each method
indicates that the 32 hidden unit synaptic RL method has 1.11$\pm$0.79% lower
validation accuracy than the 32 hidden unit MLPs trained using gradient
descent. The 0 hidden unit synaptic RL method has 1.86$\pm$0.47% higher
validation accuracy relative to the same size MLPs trained using gradient
descent.

##  4 Discussion

In this paper, we developed an algorithm to produce and apply a simple,
effective synaptic-level learning policy for MLP training. Reapplying the
static policy generated by training MLPs on a random decision boundary
matching task resulted in networks reliably converging for previously unseen
2-dimensional decision boundaries and optical character recognition tasks.
Optical character recognition validation accuracy was also comparable with, if
not slightly higher than, neural networks trained using conventional gradient
descent learning methods (Table 1). Overall, the static synaptic learning
policy was robust in the face of new activation functions, new tasks, and new
network structures. The simplicity, effectiveness, and robustness of this
approach for training MLPs supports the hypothesis that simple, universal
synaptic-level algorithms can enable learning in large connectionist models.
The results from this investigation are particularly salient when compared to
previous computational work in this area as the learned, static RL policy was
more effective in general than the adaptive one.

Of note is the fact that the 0 hidden unit experiments yielded superior
validation accuracy (1.86$\pm$0.47% higher) for the synaptic RL method as
compared to gradient descent. We suspect that this may be due to the
minibatching approach used for all synaptic RL experiments. This may have
helped the synaptic RL method escape local optima that the batch gradient
descent method was susceptible to, much like the stochastic gradient descent
algorithm upon which the minibatching approach is based [13]. Further work is
warranted to understand this performance difference, including direct
comparison of the synaptic RL algorithm with stochastic gradient descent
methods.

A key limitation of the algorithm is that the synaptic RL models required many
iterations and relatively small synaptic learning rates to converge reliably.
The overall time complexity for training MLPs on optical character recognition
tasks was higher for the proposed algorithm as compared to gradient descent
methods. Since MLPs are easily differentiable, it is logical to rely upon
techniques that take advantage of this valuable information to train
parameters efficiently. Therefore, we do not propose this algorithm as a
replacement for conventional training algorithms, but rather as a
demonstration of the effectiveness of simple synaptic-level learning rules in
connectionist models. As well, while this study took significant inspiration
from neuroscientific literature, MLPs are incredibly simplistic models of the
true behaviour of biological neurons [11], notably lacking significant time-
dependence. Further research is required to determine the extent to which the
results obtained are applicable to the credit assignment problem in biological
neurons.

Future directions may include investigations on the applicability of this
method to other connectionist models such as recurrent neural networks (RNNs),
convolutional neural networks (CNNs), and spiking neural networks (SNNs). It
is conceivable that the policy generated in this paper could apply directly to
RNNs since they are definitionally feedforward neural networks (MLPs) with
additional edges that forward propagate to subsequent time steps [18]. While
this complicates backpropagation, the proposed method would remain the same as
the only non-local information required in each synapse is the binary reward
signal. It is of interest to determine the applicability of the static policy
proposed in this work to CNNs as there is substantially more structure imposed
on the application of kernels and these kernel “synapses” generally coexist
with a set of fully connected terminal layers (MLP) [24, 16]. Since 2D
convolutions can be expressed as matrix multiplications with circulant
matrices [9], it may be that the proposed algorithm would generalize to the
CNN architecture. Applying these findings to SNNs may require significant
changes as the large number of iterations required for MLP training would be
difficult to achieve for compute-intensive SNNs [23]. The neuroscience
literature would suggest that time dependent local information features such
as pre- and post-synaptic activation timing (as in spike-timing-dependent
synaptic plasticity) would be a valuable addition to the state space of each
synapse [4]. Applications in unsupervised learning (e.g., autoencoders) are
also of strong interest.

Incorporation of additional information for use in the synaptic reinforcement
learning policy on MLPs may further enhance training speed and reliability.
Additional testing with different datasets and a more extensive hyperparameter
search would also aid in further understanding the broader applicability of
the algorithm. Techniques such as momentum [13] typically applied to gradient
descent optimization methods may also be applicable in the design of even more
effective synaptic reinforcement learning algorithms. In-depth comparison to
works that attempt to create biologically-feasible approximation methods for
gradient optimization would also help to shed light on the nature of the
proposed algorithm and its similarities to existing methods [15, 17].

The algorithm presented in this paper demonstrates the effectiveness of
framing the training of MLPs as a multi-agent, single-policy reinforcement
learning problem. While gradient based methods are well established for MLPs,
our approach removes the requirement for easy differentiation of the network
and the loss function. For the future development of machine learning and
machine intelligence systems, this is not an insignificant constraint. After
all, the primary example of “true intelligence” available to us is the brain –
a structure that does not appear to be driven directly by backpropagation-like
gradient optimization methods. It is therefore highly valuable to investigate
alternative optimization methods for connectionist models.

Furthermore, much of the prior computational work on framing neural network
training as a multi-agent reinforcement learning problem struggled with
computational efficiency [21, 30, 5, 20]. Neuron connectivity and policy
updates take a long time and are difficult to run at large scale on modern
hardware, especially in methods that train different policy for each neuron.
The proposed algorithm offers a low memory usage and low complexity single-
policy synaptic learning method that shows comparable end-performance to
gradient-based methods in training MLPs.

The synapse policy generated and implemented in this work bares resemblance to
the cellular automata studied extensively by Wolfram, Conway, Dennett, and
others [32, 6, 8]. One of the major results in Wolfram’s A New Kind of Science
is the fact that complex, irreducible behaviour can result from the
application of simple rules [32]. In addition to being complex, the behavior
exhibited by the static MLP synapse model in this study is effective in
actualizing a high-level goal (MLP training), agnostic of network topology,
activation function, and task. While the particular task of MLP training may
be “reducible” in the sense that gradient computations can enable estimation
of near-optimal MLP parameters quickly, Wolfram’s work suggests that other
potentially useful models for machine intelligence may not have such a “short
cut”.

##  5 Broader impact

We believe that the currently foreseeable consequences of this work will be
positive. Robust synaptic-level learning mechanisms for connectionist models
open many doors for engineering learning systems, and such mechanisms may also
shed light on adjacent neuroscientific problems. Since the main result from
this study was that the proposed algorithm yields comparable end-results to
standard methods for MLP training with less information, it is unlikely that
novel negative societal impacts would arise directly due to this research.

##  6 Acknowledgement

We thank Emre R. Alca for the use of his computing infrastructure to run the
final experiments in this work.

## References

  * [1] R. Adolphs.  The unsolved problems of neuroscience.  Trends in Cognitive Sciences, 19(4):173–175, 2015.
  * [2] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba.  Openai gym, 2016.
  * [3] Y. Bulatov.  notmnist dataset, September 2011.
  * [4] N. Caporale and Y. Dan.  Spike timing–dependent plasticity: a hebbian learning rule.  Annu. Rev. Neurosci., 31:25–46, 2008.
  * [5] M. Chalk, G. Tkacik, and O. Marre.  Training and inferring neural network function with multi-agent reinforcement learning.  bioRxiv, page 598086, 2020.
  * [6] J. Conway.  The game of life.  Scientific American, 223(4):4, 1970.
  * [7] N. D. Daw, J. P. O’Doherty, P. Dayan, B. Seymour, and R. J. Dolan.  Cortical substrates for exploratory decisions in humans.  Nature, 441(7095):876–879, 2006.
  * [8] D. C. Dennett.  Real patterns.  The Journal of Philosophy, 88(1):27–51, 1991.
  * [9] C. Ding, S. Liao, Y. Wang, Z. Li, N. Liu, Y. Zhuo, C. Wang, X. Qian, Y. Bai, G. Yuan, et al.  Circnn: accelerating and compressing deep neural networks using block-circulant weight matrices.  In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, pages 395–408, 2017.
  * [10] E. D’Angelo, S. Solinas, J. Garrido, C. Casellato, A. Pedrocchi, J. Mapelli, D. Gandolfi, and F. Prestori.  Realistic modeling of neurons and networks: towards brain simulation.  Functional neurology, 28(3):153, 2013.
  * [11] O. Eluyode and D. T. Akomolafe.  Comparative study of biological and artificial neural networks.  European Journal of Applied Engineering and Scientific Research, 2(1):36–46, 2013.
  * [12] J. I. Gold and M. N. Shadlen.  The neural basis of decision making.  Annual Review of Neuroscience, 30(1):535–574, 2007.
  * [13] I. Goodfellow, Y. Bengio, and A. Courville.  Deep Learning.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * [14] J. Hawkins and S. Ahmad.  Why neurons have thousands of synapses, a theory of sequence memory in neocortex.  Frontiers in Neural Circuits, 10:23–23, 2016.
  * [15] B. J. Lansdell, P. R. Prakash, and K. P. Kording.  Learning to solve the credit assignment problem.  arXiv preprint arXiv:1906.00889, 2019.
  * [16] Y. LeCun, Y. Bengio, and G. Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [17] T. P. Lillicrap, D. Cownden, D. B. Tweed, and C. J. Akerman.  Random synaptic feedback weights support error backpropagation for deep learning.  Nature Communications, 7(1):13276–13276, 2016.
  * [18] Z. C. Lipton, J. Berkowitz, and C. Elkan.  A critical review of recurrent neural networks for sequence learning.  arXiv preprint arXiv:1506.00019, 2015.
  * [19] T. M. McKenna, J. L. Davis, and S. F. Zornetzer.  Single neuron computation.  Academic Press, 2014.
  * [20] S. Ohsawa, K. Akuzawa, T. Matsushima, G. Bezerra, Y. Iwasawa, H. Kajino, S. Takenaka, and Y. Matsuo.  Neuron as an agent.  In ICLR 2018 : International Conference on Learning Representations 2018, 2018.
  * [21] J. Ott.  Giving up control: Neurons as reinforcement learning agents.  arXiv preprint arXiv:2003.11642, 2020.
  * [22] A. Parent and L.-N. Hazrati.  Functional anatomy of the basal ganglia. i. the cortico-basal ganglia-thalamo-cortical loop.  Brain Research Reviews, 20(1):91–127, 1995.
  * [23] M. Pfeiffer and T. Pfeil.  Deep learning with spiking neurons: opportunities and challenges.  Frontiers in neuroscience, 12:774, 2018.
  * [24] W. Rawat and Z. Wang.  Deep convolutional neural networks for image classification: A comprehensive review.  Neural computation, 29(9):2352–2449, 2017.
  * [25] F. Rosenblatt.  The perceptron: a probabilistic model for information storage and organization in the brain.  Psychological Review, 65(6):386–408, 1958.
  * [26] J. E. Rubin, C. Vich, M. Clapp, K. Noneman, and T. Verstynen.  The credit assignment problem in cortico-basal ganglia-thalamic networks: A review, a problem and a possible solution.  European Journal of Neuroscience, 53(7):2234–2253, 2021.
  * [27] S. Russell.  Artificial intelligence : a modern approach.  Prentice Hall, Upper Saddle River, New Jersey, 2010.
  * [28] L. Su, R. Gomez, and H. Bowman.  Analysing neurobiological models using communicating automata.  Formal Aspects of Computing, 26(6):1169–1204, 2014.
  * [29] R. S. Sutton and A. G. Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [30] Z. Wang and M. Cai.  Reinforcement learning applied to single neuron.  arXiv preprint arXiv:1505.04150, 2015.
  * [31] J. C. Whittington and R. Bogacz.  Theories of error back-propagation in the brain.  Trends in Cognitive Sciences, 23(3):235–250, 2019.
  * [32] S. Wolfram.  A New Kind of Science.  Wolfram Media, 2002.


# An Empirical Evaluation of End-to-end Polyphonic Optical Music Recognition

###### Abstract

Previous work has shown that neural architectures are able to perform optical
music recognition (OMR) on monophonic and homophonic music with high accuracy.
However, piano and orchestral scores frequently exhibit polyphonic passages,
which add a second dimension to the task. Monophonic and homophonic music can
be described as homorhythmic, or having a single musical rhythm. Polyphonic
music, on the other hand, can be seen as having multiple rhythmic sequences,
or voices, concurrently. We first introduce a workflow for creating large-
scale polyphonic datasets suitable for end-to-end recognition from sheet music
publicly available on the MuseScore forum. We then propose two novel
formulations for end-to-end polyphonic OMR—one treating the problem as a type
of multi-task binary classification, and the other treating it as multi-
sequence detection. Building upon the encoder-decoder architecture and an
image encoder proposed in past work on end-to-end OMR, we propose two novel
decoder models—FlagDecoder and RNNDecoder—that correspond to the two
formulations. Finally, we compare the empirical performance of these end-to-
end approaches to polyphonic OMR and observe a new state-of-the-art
performance with our multi-sequence detection decoder, RNNDecoder.

##  1 Introduction

Figure 1: Examples of the MuseScore Polyphonic Dataset (MSPD) and its hard
subset (MSPD-Hard)—(top) an easy excerpt in MSPD and (bottom) three excerpts
that can be found in both MSPD and MSPD-Hard.

As society continues to become more and more dependent on digitization as a
means of storing information such as photos, addresses, and music, now is a
perfect time to refine the technology required to digitize sheet music.
Organizing scanned music can be a tedious task to do manually. For example,
each image must be labeled with several attributes, the most basic being the
title, composer, arranger, and page number. Assuming that all of these are
input correctly, a user could then navigate through a large-scale collection
somewhat easily. However what if a user wanted to filter the scores by
attributes such as instrument, key signature, time signature, or tempo? What
if a user had a score, but wanted to transpose it to a different key? Manually
doing all of the annotation required for these demands when uploading sheet
music scans would be impractical, and this is where optical music recognition
(OMR) can shine.

Over the past few years, data driven approaches to optical music recognition
have become attractive ways to solve the problem. The improvement in the
accuracy of systems built using these tools is very exciting, however they are
far from perfect in challenging circumstances. One visual challenge relatively
unique to optical music recognition is detecting multi-voice music, also known
as polyphonic music. Previous work has mentioned that their approaches to OMR
cannot sufficiently solve this problem to the same extent as they have solved
monophonic OMR [1, 2].

In view of the lack of a large-scale polyphonic dataset for end-to-end
polyphonic OMR, we introduce a workflow for acquiring annotated samples from
sheet music publicly available on the MuseScore forum [3]. As an initial
attempt to the challenges of polyphonic OMR, we only consider single-staff
scores. Our objective with this dataset is to empirically evaluate the
performance of three different architectures on the task of end-to-end
polyphonic OMR, where the input is a staff line image and the output is a
symbolic sequence that can be encoded into common music notation formats such
as MusicXML. Voice information is not included in this process.

We propose two novel neural architectures for end-to-end OMR, namely
FlagDecoder and RNNDecoder, which are both encoder-decoder models based on the
architecture proposed by Calvo-Zaragoza et al. for monophonic scores [4],
hereafter referred to as the baseline. One feature common to all three models
is their mechanism for encoding each image: a CNN followed by a bidirectional
LSTM. The architectures differ, however, in their decoding mechanism. The
baseline architecture uses a fully connected layer as a symbol classifier on
the encoded image. Our proposed FlagDecoder treats polyphonic OMR as a multi-
task binary prediction problem, simultaneously detecting whether each pitch
and staff symbol is present or not, along with the rhythm if the symbol is a
note. Our other proposed architecture, RNNDecoder, uses a vertical RNN decoder
over the symbols appearing at each vertical image slice, giving the model the
capacity to output a predetermined number of symbol predictions at a single
horizontal position of an image.

In this paper, we first introduce the current state of polyphonic OMR
research. Then we introduce our procedure for building a large-scale dataset
of exclusively polyphonic music data. Finally we perform an empirical
evaluation of our proposed architectures introduced above, and find that they
both outperform past work in terms of symbol error rate, with the RNNDecoder
achieving a new state-of-the-art performance on end-to-end polyphonic OMR. All
source code is available at https://github.com/sachindae/polyphonic-omr.

##  2 Background

###  2.1 Optical music recognition (OMR)

Previous work on polyphonic OMR has been limited. One of the main approaches
to it has been a two-step process of first segmenting each musical symbol [5,
6, 7, 8, 9] and then identifying the relationships between them through a
post-processing step [10]. The challenge with building a system using this
method is that errors add up from both sub-systems. Particularly the latter
task, more formally known as forming a musical notation graph, can be quite
challenging, with the state-of-the-art being far from perfect [10]. Another
approach to OMR has been to treat it as an end-to-end task as proposed by [4,
11], where the complete symbolic sequence corresponding to an image is output
by the system. Among the end-to-end approaches, there have been a variety of
training objectives used for the task such as Connectionist Temporal
Classification (CTC) loss, cross-entropy loss, and Smooth-L1 loss [4, 11, 12].
While applied to monophonic and homophonic music [13] successfully, there have
not been any conclusions on the framework’s capability of being extended to
polyphonic notation.

###  2.2 Datasets for OMR

Several datasets have been proposed for musical symbol classification [14, 15,
16, 17, 18, 19]. Others have been proposed for training end-to-end OMR systems
on single-stave handwritten music scores [2] and typeset images for monophonic
scores [20, 21, 11]. However, these datasets are either small in size or
contain only monophonic scores.

| MSPD | MSPD-Hard
---|---|---
| Min | Mean | Max | Min | Mean | Max
Length (symbols) | 3 | 70.59 | 819 | 41 | 79.2 | 679
Length (measures) | 1 | 4.15 | 55 | 1 | 2.11 | 8
Density (symbols/measures) | 3 | 20.3 | 165 | 41 | 52.8 | 165
Polyphony (voices) | 2 | 2.05 | 4 | 2 | 2.42 | 4
Table 1: Statistics of the MuseScore Polyphonic Dataset (MSPD) and its hard
subset (MSPD-Hard).

##  3 MuseScore Polyphonic Dataset

Figure 2: Examples from the dataset where the staff line is not cropped
perfectly.
Figure 3: Example of the label encoding adopted in this paper.

Given the size of datasets such as PrIMuS [20] that have been used to show the
effectiveness of an end-to-end architecture on monophonic OMR, we decided to
come up with a dataset of similar size to do the same for polyphonic OMR.
Using 19,432 MuseScore files available to download online [22], we were able
to generate 124,671 varied-width single-staff images of exclusively polyphonic
music along with their ground truth labels. To determine whether a given
sample is polyphonic or not, we check if the music encoding defines multiple
voices within a single measure.

To generate the dataset, we first used the MuseScore software plugin API
(separate from the MuseScore forum mentioned above) to reduce the page height
of the rendering to easily generate single staff line images. Then we executed
a script to remove credit text which covered up some music symbols. After
that, we used the MuseScore plugin API to generate MusicXML and PNG files from
the MuseScore files. Lastly, we parsed the MusicXML to generate labels for
each of the images, and removed sparse (music with only rests) and non-
polyphonic data from the dataset.

The difficulty of the samples has quite a large range, from simple excerpts
with two-note chords to dense notation as shown in Figure 1. Also, many
samples are not perfectly cropped resulting in an additional implicit task of
extracting the staff line from noisy environments. We argue however that this
creates a more realistic environment as OMR systems should be able to handle
these kinds of interferences shown in Figure 2.

For our experiments with this dataset, we used a 70/15/15 split for training,
validation, and test respectively.

###  3.1 Data annotation

Due to our primary focus being polyphony, we chose to use a minimal symbol set
sufficient to represent pitch and rhythm accurately, apart from tuplets. More
specifically, we do not care about symbols such as dynamics, ties, tuplets,
staccatos, accents, and other staff text. Instead, the only musical symbols we
chose to label are clefs, key signatures, time signatures, barlines, and the
notes themselves (pitch and rhythm). Inspired by the labeling scheme used to
train models for end-to-end monophonic and homophonic OMR [4, 13], we
approached the task of polyphonic OMR in the same way, with the “Advance
position” encoding proposed by Alfaro et al. for representing homophonic music
as a one-dimensional sequence reading from left to right. This encoding adds a
‘+’ symbol between each sequential occurrence of notes and symbols, and orders
the individual notes of a chord from bottom to top, as seen in Figure 3.
Throughout the rest of this paper, we will refer to the non-note music symbols
described above (clefs, key signatures, time signatures, and barlines) as
staff symbols.

###  3.2 MSPD-Hard

While we are interested in the performance on the average polyphonic images,
we also want to have a means to push an OMR system to its limit so we can
better determine an upper bound on the capabilities. To do this, we created a
subset of the test set of all the samples with a density (defined by number of
symbols per measure) of at least 41, resulting in 900 samples, which we will
refer to as MSPD-Hard. The bottom three images in Figure 1 are samples from
the hard subset.

The statistic that sticks out the most when comparing the two (see Table 1) is
of course the density. While it may seem strange that the mean symbol length
of the hard test set is similar to the full test set, we observed that this is
because the more dense samples tend to contain measures that are filled with
symbols, thus fewer measures can fit per image on average. Lastly, the hard
subset samples tend to have a higher level of polyphony, measured by number of
voices defined by the MusicXML files, as expected.

Figure 4: Illustration of the image encoder used in this paper.

##  4 Architectural Comparison for Polyphonic Optical Music Recognition

As we mentioned in Section 2, several training objectives have been used for
end-to-end OMR. Due to many recent works showing the effectiveness of CTC [23]
for OMR [4, 2, 13], we chose to train all of the considered architectures
using the same objective. The equation below shows the objective that CTC aims
to maximize, where $y$ represents the target sequence, $z$ the alignment, $x$
the sequence of vertical image slices (i.e. fixed-width slices of a staff line
as shown in Figure 4), and $\theta$ the model parameters.

$\max_{\theta}P(y\,|\,x;\theta)=\max_{\theta}\sum_{z}P(y,z\,|\,x;\theta)\,.$
(1)

###  4.1 Architecture overview

At a high level, all of the architectures we compared share the same
structure. The two components are an encoder and a decoder. The function of
the encoder is firstly to extract features about the image while creating
vertical slices through pooling, and secondly to give global context of the
image encoding to each local image slice. The goal of the decoder is to use
the representations created by the encoder and predict the symbols that are
present in each of the vertical image slices. Finally, we use CTC to
marginalize over the alignment of these slices for training. Due to the
effectiveness of this end-to-end architecture on monophonic and homophonic
music [4, 13], we chose to keep the encoder fixed and instead look to
different decoding strategies that could be better suited for dense polyphonic
music.

###  4.2 Encoder details

The encoder we use is the one described by Calvo-Zaragoza et al, with 2x less
width pooling [21]. First, the image is fed through a deep convolutional
neural network (CNN) to extract relevant learned features. These two-
dimensional feature representations of each vertical image slice are then
flattened to a vector to create a sequential representation suitable for a
recurrent neural network (RNN). The purpose of the RNN in this context is to
give some awareness of the surrounding representations to each image slice’s
encoding, which is essential to help identify symbols that may span multiple
image slices. We chose to use a bidirectional Long Short-Term Memory (LSTM)
[24, 25] for its effectiveness in end-to-end OMR as empirically shown by Baro
et al. [2]. A visualization of the encoder components can be seen in Figure 4.

###  4.3 Baseline decoder

The baseline architecture we evaluated includes the encoder mentioned above,
followed by a simple decoder consisting of two parallel fully connected layers
to classify the pitch and rhythm of the symbol appearing in each vertical
image slice. By design, this decoder is only capable of outputting a single
symbol prediction at each image slice, a characteristic not ideal for
polyphonic music.

###  4.4 FlagDecoder

To incorporate the multi-dimensional nature of polyphonic music while being
trained on a one-dimensional sequence, we propose the BinaryVector. We
observed that there are a fixed number of positions on a staff line that a
note can appear on, indicating its pitch when combined with knowledge of the
clef, key signature, and any accidentals. Based on this, one possible decoding
for a vertical image slice could be an $n$-dimensional (where $n$ is the sum
of the number of note positions and the number of staff symbols) vector where
the value of each dimension indicates whether or not the corresponding pitch
or staff symbol appears in the image slice. This can be achieved using the
sigmoid activation function. For inference, we apply a threshold of 0.5 to
determine if a symbol is present or not.

Since we also need rhythm and accidental information for OMR, we modify this
BinaryVector approach so that each note position on the staff has a
corresponding rhythm and accidental classifier as opposed to a binary
classifier that is only applicable for staff symbols. Visualizing this in
Figure 5, there is a binary vector for the staff symbols, and a matrix for the
notes, together resembling a flag hence the name FlagDecoder. To handle the
case when two voices are playing the same note, we include two rows in the
note matrix for each note position on the staff.

The FlagDecoder first uses two parallel fully connected (FC) layers for the
note positions and staff symbols to reduce the dimensionality. Then the note
latent representation goes through two separate FC layers (for rhythms and
accidentals) to produce the note matrix, and the staff symbol latent
representation is connected to another FC layer to produce the BinaryVector.

Figure 5: Illustrations of the three decoder architectures examined in this
paper.

###  4.5 RNNDecoder

An alternative approach to those mentioned above, which maintain a single
dimensional sequence, is to embrace the fact that polyphonic music is
inherently multi-dimensional. Based on the near perfect results that have been
shown in previous published work on monophonic OMR with the baseline decoder,
we took a new approach to the challenge of polyphony that breaks up the task
into several simpler versions. Rather than representing polyphonic music as a
one-dimensional sequence, we propose RNNDecoder, a recurrent decoder that is
run across each image slice vertically, allowing for multiple outputs at a
single image slice. This can ideally handle polyphony better than the baseline
decoder, and can be trained trivially using the perspective that there are
multiple one-dimensional sequences occurring from bottom to top in each image.
To allow for alignment at inference time, we add a “noNote” symbol to the
labels, as shown in Figure 6.

As we mentioned above, the RNNDecoder can generate a fixed number $m$ of
outputs per image slice. Since the largest number of notes and staff symbols
we observed present in a single horizontal position of an image was 10, we
chose to have $m=10$ for our experiments. The key difference between the
RNNDecoder and the baseline is that a hidden state is included while
generating each output prediction, and is concatenated to the current image
slice encoding before going through the classifier. More specifically, at each
image slice as each output is generated, this hidden state is updated like the
hidden state of an RNN as in Figure 5, and fed through the same classifier
along with the image slice encoding 10 times. As shown in Figure 6, this new
decoder can be trained without using the “Advance position” label encoding.

###  4.6 Objective functions

As we mentioned in Section 4, CTC aims to maximize the likelihood of a target
symbolic sequence. For the baseline decoder, we use two target sequences – one
for rhythm and one for pitch – and jointly minimize those two CTC losses. On
the other hand for the FlagDecoder, we just use a single target sequence where
each "symbol" is a unique flag configuration (see Figure 6), meaning it
represents a combination of notes and staff symbols as opposed to just a
single word from a symbol vocabulary. Lastly for the RNNDecoder, we use the
same two target sequences used in the baseline, but we use 10 of them, thus
optimizing the arithmetic mean of the CTC losses over the $m$ sequences. The
loss functions are shown below in Equation 2:

$\displaystyle\mathcal{L}_{Baseline}$
$\displaystyle=\mathcal{L}_{Pitch}+\mathcal{L}_{Rhythm}\,,$ (2)
$\displaystyle\mathcal{L}_{FlagDecoder}$ $\displaystyle=\mathcal{L}_{Flag}\,,$
$\displaystyle\mathcal{L}_{RNNDecoder}$
$\displaystyle=\frac{1}{m}\sum_{i}^{m}{\left(\mathcal{L}_{Pitch}+\mathcal{L}_{Rhythm}\right)}\,,$

where $\mathcal{L}_{Pitch}$, $\mathcal{L}_{Rhythm}$ and $\mathcal{L}_{Flag}$
are the corresponding CTC losses.

##  5 Experiments

| MSPD | MSPD-Hard
---|---|---
Decoder model | Rhythm SER (%) | Pitch SER (%) | Rhythm SER (%) | Pitch SER (%)
Baseline | 7.39 | 10.28 | 14.11 | 18.83
FlagDecoder | 6.67 | 9.82 | 9.86 | 17.98
RNNDecoder | 3.92 | 5.64 | 5.82 | 8.57
Table 2: Performance of the three decoders on MuseScore Polyphonic Dataset
(MSPD) and its hard subset (MSPD-Hard).

###  5.1 Implementation details

All models were trained using stochastic gradient descent with the Adam
optimization algorithm [26]. We used a learning rate of $10^{-4}$ and a batch
size of 16. Additionally, each image goes through a short preprocessing stage
where they are inverted so that black pixels take on the highest value while
white pixels are 0, and subsequently resized to a fixed height of 128 pixels.

###  5.2 Experiment setup

For evaluation, we follow recent literature [2] and use Pitch and Rhythm
Symbol Error Rate (SER) as our evaluation metric of choice. This metric
measures the edit distance at a symbol level between a predicted sequence and
the ground truth sequence. More precisely, it can be written as the sum of
insertions ($I$), deletions ($D$), and substitutions ($S$) normalized by the
ground truth sequence length ($N$), i.e., $\text{SER}=(I+D+S)/N$.

In addition to staying consistent with previous literature, we also chose to
evaluate Pitch and Rhythm SER separately to be able to compare the
difficulties of the two tasks and gain insight on where improvements can be
made. The two sets of data we used for evaluation are the full test set
containing 18,700 images, and the hard test set containing 900 images, both of
which were discussed in depth in Section 3.

###  5.3 Experiment results

Figure 6: Examples of the different symbolic sequence representations used to
optimize the decoders—(top) BaselineDecoder using “Advance position” encoding,
(middle) FlagDecoder and (bottom) RNNDecoder, where number of outputs is 10.

We first compare the three different decoders using the full test set. An
interesting result is that the Pitch SER is higher than the Rhythm SER across
the board for all of the models. For the baseline and RNNDecoder, we believe
this is due to the fact that pitch is affected by clef, thus when a clef
prediction is off, or in particularly wide images, the correct clef may not be
represented in an image slice encoding, resulting in incorrect decoding.
Additionally when there are multiple neighboring notes together, identifying
the correct pitches naturally seems more challenging than identifying the
correct rhythms due to requiring more fine grained features to discern the
exact pitches. We believe using an agnostic representation of pitch as
described in [20] could potentially result in better pitch performance.

Figure 7: Comparison of the three decoders on an example with dense chords.
Red blocks indicate the errors.

While our FlagDecoder only slightly outperforms the baseline on the full test
set, the RNNDecoder appears to perform twice as well as the baseline on the
full test set, achieving a new state-of-the-art performance. Further
evaluating the performances of the new decoding methods on the hard test set
(MSPD-Hard) highlights our decoders’ strengths over the baseline decoder. With
the baseline, the error rate nearly doubles, whereas with the proposed
decoding strategies, the error rate increases by a smaller factor when dealing
with difficult data, with the Pitch SER of the FlagDecoder being the
exception.

###  5.4 Error analysis

We also examine some qualitative results on examples from MSPD-Hard to examine
the upper bound performance of the decoders. From Figure 7 we see that in the
first measure which contains several huge chords nearby, the baseline is
neither able to separate them by outputting a ‘+’ symbol nor output the
correct number of notes. The FlagDecoder handles the first two chords well,
but is likely thrown off by the sharps in the third chord. The RNNDecoder
performs the best in the first measure, just missing a single note and
accidental in the last chord, and deals with the polyphony in following
measure perfectly. Figure 8 is challenging due to its high level of polyphony,
which the baseline decoder clearly struggles with. In this example, both the
FlagDecoder and RNNDecoder perform similarly, however the FlagDecoder actually
handles the first chord with 4 voices correctly rhythmically whereas the
RNNDecoder makes a minor mistake.

Figure 8: Comparison of the decoders on an example with four levels of
polyphony. Red blocks indicate the errors.

##  6 Conclusion

In this work, we first introduced a workflow for generating datasets from
MuseScore files which will be beneficial for the research community given the
massive amount of sheet music publicly available on the MuseScore forum. We
then used this to create a large-scale dataset suitable for end-to-end
polyphonic optical music recognition (OMR), and proposed two novel decoding
strategies for the task, namely FlagDecoder and RNNDecoder. Further we
performed an empirical comparison of the performance of these methods on
polyphonic OMR, and observed a new state-of-the-art performance with the
RNNDecoder.

One of the main limitations of this work is generalizability, a problem that
many supervised machine learning systems struggle with. While our system can
perform extremely well on images generated from the MuseScore engraver, it is
not able to do well out of the box on music generated by other engravers. We
are also aware that there are many viable implementations of the new decoding
methods we proposed that could potentially give better performance, and hope
to evaluate them in the future when we have the required computing resources.
In addition, adapting these methods to multi-staff music will allow more
versatility in usage. Lastly, we hope to address the challenge of
generalizability in the future as it is currently one of the major barriers
preventing neural network-based OMR systems from being deployed widely.

## References

  * [1] J. Calvo-Zaragoza, J. Hajič jr., and A. Pacha, “Understanding optical music recognition,” _ACM Computing Surveys (CSUR)_ , vol. 53, no. 4, pp. 1–35, 2020.
  * [2] A. Baró, P. Riba, J. Calvo-Zaragoza, and A. Fornés, “From optical music recognition to handwritten music recognition: A baseline,” _Pattern Recognition Letters_ , vol. 123, pp. 1–8, 2019.
  * [3] “Musescore forum.” [Online]. Available: https://musescore.com
  * [4] J. Calvo-Zaragoza, J. J. Valero-Mas, and A. Pertusa, “End-to-end optical music recognition using neural networks,” in _Proceedings of the 18th International Society for Music Information Retrieval Conference (ISMIR)_ , 2017\.
  * [5] A. Pacha, K.-Y. Choi, B. Coüasnon, Y. Ricquebourg, R. Zanibbi, and H. Eidenberger, “Handwritten music object detection: Open issues and baseline results,” in _2018 13th IAPR International Workshop on Document Analysis Systems (DAS)_ , 2018.
  * [6] L. Tuggener, I. Elezi, J. Schmidhuber, and T. Stadelmann, “Deep watershed detector for music object recognition,” _arXiv preprint arXiv:1805.10548_ , 2018.
  * [7] J. Hajič jr., M. Dorfer, G. Widmer, and P. Pecina, “Towards full-pipeline handwritten omr with musical symbol detection by u-nets.” in _Proceedings of the 19th International Society for Music Information Retrieval Conference (ISMIR)_ , 2018.
  * [8] A. Pacha, J. Hajič jr., and J. Calvo-Zaragoza, “A baseline for general music object detection with deep learning,” _Applied Sciences_ , vol. 8, no. 9, p. 1488, 2018.
  * [9] Z. Huang, X. Jia, and Y. Guo, “State-of-the-art model for music object recognition with deep learning,” _Applied Sciences_ , vol. 9, no. 13, p. 2645, 2019.
  * [10] A. Pacha, J. Calvo-Zaragoza, and J. Hajič jr., “Learning notation graph construction for full-pipeline optical music recognition.” in _Proceedings of the 20th International Society for Music Information Retrieval Conference (ISMIR)_ , 2019.
  * [11] E. van der Wel and K. Ullrich, “Optical music recognition with convolutional sequence-to-sequence models,” in _Proceedings of the 18th International Society for Music Information Retrieval Conference (ISMIR)_ , 2017.
  * [12] A. Baró, C. Badal, and A. Fornés, “Handwritten historical music recognition by sequence-to-sequence with attention mechanism,” in _2020 17th International Conference on Frontiers in Handwriting Recognition (ICFHR)_ , 2020, pp. 205–210.
  * [13] M. Alfaro-Contreras, J. Calvo-Zaragoza, and J. M. Iñesta, “Approaching end-to-end optical music recognition for homophonic scores,” in _Iberian Conference on Pattern Recognition and Image Analysis_ , 2019, pp. 147–158.
  * [14] A. F. Desaedeleer, “Reading sheet music,” Master’s thesis, University of London, 2006.
  * [15] A. Fornés, J. Lladós, and G. Sánchez, “Old handwritten musical symbol classification by a dynamic time warping based method,” in _Graphics Recognition. Recent Advances and New Opportunities: 7th International Workshop (GREC)_ , 2008.
  * [16] A. Rebelo, G. Capela, and J. S. Cardoso, “Optical recognition of music symbols: A comparative study,” _International Journal on Document Analysis and Recognition (IJDAR)_ , vol. 13, no. 1, 2010.
  * [17] J. Calvo-Zaragoza and J. Oncina, “Recognition of pen-based music notation: The homus dataset,” in _Proceedings of the 22nd International Conference on Pattern Recognition (ICPR)_ , 2014.
  * [18] A. Pacha and H. Eidenberger, “Towards a universal music symbol classifier,” in _14th International Conference on Document Analysis and Recognition (ICDAR)_ , 2017, pp. 35–36.
  * [19] J. Hajič jr. and P. Pecina, “The MUSCIMA++ dataset for handwritten optical music recognition,” in _2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR)_ , 2017.
  * [20] J. Calvo-Zaragoza and D. Rizo, “End-to-end neural optical music recognition of monophonic scores,” _Applied Sciences_ , vol. 8, no. 4, 2018.
  * [21] ——, “Camera-PrIMuS: Neural end-to-end optical music recognition on realistic monophonic scores,” in _Proceedings of the 19th International Society for Music Information Retrieval Conference (ISMIR)_ , 2018.
  * [22] “Musescore dataset.” [Online]. Available: https://github.com/Xmader/musescore-dataset
  * [23] A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber, “Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks,” in _Proceedings of the 23rd International Conference on Machine Learning (ICML)_ , 2006, pp. 369–376.
  * [24] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [25] M. Schuster and K. Paliwal, “Bidirectional recurrent neural networks,” _IEEE Transactions on Signal Processing_ , vol. 45, no. 11, pp. 2673–2681, 1997.
  * [26] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.


## References

Lazzarotto  F  Cremonese  G  Lucchetti  A  Re  C  Simioni  E  Pajola  M
Cambianica  P  Munaretto  G

(February 7, 2020 -<EMAIL_ADDRESS>
  * 11affiliationtext: INAF-OAPD, Padova, Italy, http://www.oapd.inaf.it 22affiliationtext: University of Padova - DFA, Padova, Italy, https://www.dfa.unipd.it

##  High Quality Software for
Planetary Science from Space

Lazzarotto  F  Cremonese  G  Lucchetti  A  Re  C  Simioni  E  Pajola  M
Cambianica  P  Munaretto  G

(February 7, 2020 -<EMAIL_ADDRESS>
###### Abstract

Planetary science space missions need high quality software ed efficient
algorithms in order to extract innovative scientific results from flight data.
Reliable and efficient software technologies are increasingly vital to improve
and prolong the exploiting of the results of a mission, to allow the
application of established algorithms and technologies also to future space
missions and for the scientific analysis of archived data. Here after will be
given an in-depth analysis study accompanied by implementation examples on ESA
and ASI missions and some remarkable results fruit of decades of important
experience reached by space agencies and research institutes in the field.
Space applications software quality analysis is not different from other
application contexts, among the hi-tech and hi-reliability fields. We describe
here a Software Quality study in general, then we will focus on the quality of
space mission software (s/w) with details on some notable cases.

##  1 Software Quality

######  Definition 1.

_Quality: The degree to which a set of inherent characteristics of an entity
fulfills requirements [ISO 9000:2005]_.

Figure 1: S/W quality attributes

Quality means satisfying requirements which may be explicitly stated or
implicitly given by a shared notion, it is not an absolute degree of goodness.
In Software Quality, the entity which shall fulfill requirements is a software
system or component. Evaluating the quality of software is not simple because
usually s/w is not tangible and manifests only in effects and documentation,
especially the source code. We can face software quality studies with a
pragmatic practical view or with the more formal ISO standards view. The
pragmatic view

  * •

External Quality (as perceived);

  * •

Internal Quality (of s/w artifacts);

The ISO standards’ view [ISO/IEC 25010:2011]
based on measurement

  * •

Internal measures: internal quality;

  * •

External measures: external quality;

  * •

Usage measures: quality in use.

##  2 Software for Space Science

There are not drawbacks for using widely adopted free standards and free and
open source solutions for space missions data handling and computing software.
This has been the key of success for the most important advances in general
purpose computing and information technologies of last decades (advent of www,
cloud services, data science, smartphones, …).

Figure 2: Satellite data transfer

For (Astro)Physics and Planetary Science we can cite Astropy[2],
PlanetaryPy[3], CERN/Root framework[4], GDAL by OSGeo[10], QGis[17] and GNU
Scientific Library[8]. In our project we mostly used C/C++ and Bash computing
languages, with some Python and Java modules, from which was very easy and
efficient to call the described libraries, with no drawbacks, extra-costs and
unnecessary network connections due to proprietary licensed software.
Pipelines commands can be also run step by step interactively or operated
graphically through GUIs that has been simply and portably implemented (Win,
Mac, Linux) using kdialog by KDE or via more advanced compiled apps. All the
software included in our s/w distributions has been saved under a version
control system, such as Git, SVN or CVS to facilitate the team work, having
reliable distributed access and to individuate official releases.

##  3 BepiColombo mission

BepiColombo[1] (BC) mission to Mercury by ESA/JAXA will provide measurements
to allow studies of composition, origin and dynamics of Mercury’s exosphere
and polar deposits as well as of the structure and dynamics of Mercury’s
magnetosphere. Expected to arrive at Mercury in 2025 after Earth and Venus
flybys. On 2018-10-20 03.45 (CEST), BC was successfully launched from european
spaceport Kourou (French Guyana) with an Ariane 5 vehicle.

Figure 3: BC spacecrafts on Mercury orbits

##  4 Space Data Processing

We created SETM: a set of s/w libraries to process satellite data, supporting
different aspects of BC space mission Data Handling and Operations tasks and
we are applying it to the SERENA[15][14] and SIMBIO-SYS[9][5] BC instruments.
We focalised on widely adopted data structures and formats as well as we
imported and implemented commonly used algorithms, being neutral from the
specific formats and computing languages. The functions to be performed by the
s/w system has been collected in a S/W Requirement Specification document
(SRS), following ISO/IEC/IEEE 29148-2011 standard, using instrument team
requests and S/W engineering guidelines advised by ESA.
SETM functions include:

  * •

TM decoding/encoding;

  * •

Data Structures & Metadata definition;

  * •

Statistics, Plots & Reporting;

  * •

File I/O & DB archiving;

  * •

Networking & Automation.

##  5 Conclusion

The review of yet developed projects supported by ESA, EUMETSAT, NASA and NOAA
and the experience on science data processing systems software for space
missions participated by INAF led us to the synthesis of an efficient
collection of s/w libraries developed with a general approach, containing all
is needed to share and reuse it in international collaborative research
projects.

##  6 References

## References

  * [1] European Space Agency.  BepiColombo science mission homepage.  https://sci.esa.int/web/bepicolombo.
  * [2] Astropy Collaboration and Price-Whelan et al.  The Astropy Project: Building an Open-science Project and Status of the v2.0 Core Package.  Astrophysics Journal, 156(3):123, Sep 2018.
  * [3] The PlanetaryPy Team: Aye, M., Godber, A., et al.  PlanetaryPy. Python tools for Planetary Science.  https://github.com/planetarypy, 2020.  ”url accessed on 12/04/2020”.
  * [4] Rene Brun and Fons Rademakers.  Root - an object oriented data analysis framework, aihenp’96 workshop, lausanne.  volume 389, pages 81–86, Sep 1996.  http://root.cern.ch/.
  * [5] Gabriele Cremonese et al.  The Stereo Camera on the Bepicolombo Esa/jaxa Mission: a Novel Approach.  In Advances in Geosciences, Volume 15: Planetary Science (PS), volume 15, pages 305–322, Mar 2009.
  * [6] Sara De La Fuente, Angela Carasa, Iñaki Ortiz, Pedro Rodriguez, Mauro Casale, Johannes Benkhoff, and Joe Zender.  Planning Bepicolombo MPO Science Operations to study Mercury Interior.  In EGU Conference, page 15149, Apr 2017.
  * [7] Sara de la Fuente, Jonathan McAuliffe, and Mauro Casale.  Science operations planning concept for bepicolombo mercury planetary orbiter.  https://doi.org/10.2514/6.2016-2591, 2016.
  * [8] M. Galassi et al.  GNU Scientific Library Reference Manual (3rd Ed.).  Network Theory Ltd, 2009.  ”free numerical software library for C and C++ programmers callable from many other computer languages”.
  * [9] E. Flamini, F. Capaccioni, Cremonese, and SIMBIO-SYS Team.  SIMBIO-SYS for BepiColombo: status and issues.  Memorie della Societa Astronomica Italiana, 87:171, Jan 2016.
  * [10] GDAL/OGR contributors.  GDAL/OGR Geospatial Data Abstraction software Library.  Open Source Geospatial Foundation, 2019.
  * [11] Richard Soley Object Management Group.  Omg whitepaper: How to deliver resilient, secure, efficient, and easily changed it systems in line with cisq recommendations.  https://www.it-cisq.org/omg-cisq-wp, 2019.
  * [12] K. H. Jeeja, K. Keerthi, A. Lakshmi, H. ShantalaS., Jothy Soman, P. S. Sura, and N. Valarmathi.  An architecture of baseband data handling system for deep space mission and realization for mars orbiter mission.  ICACCI 2015 Conference, pages 694–699, 2015.
  * [13] Jose P. Miguel, David Mauricio, and Glen Rodriguez.  A review of software quality models for the evaluation of software products.  2014\.
  * [14] S. Orsini, S. Livi, K. Torkar, S. Barabash, and the SERENA Team.  ”SERENA: A suite of four instruments (elena, strofio, picam and mipa) on board bepicolombo-mpo for particle detection in the hermean environment”.  Planetary and Space Science, 58(1-2):166–181, Jan 2010.
  * [15] Stefano Orsini et al.  The BepiColombo/SERENA package: first signal from space.  In EPSC-DPS Joint Meeting 2019, volume 2019, pages EPSC–DPS2019–1737, Sep 2019.
  * [16] Fernando Perez-Lopez, Santa Martinez, Sara de la Fuente, Jayne Lefort, and Mauro Casale.  BepiColombo MPO Data Handling and Archiving Operations Strategy.  In DASIA 2013 - DAta Systems In Aerospace, volume 720 of ESA Special Publication, page 3, Aug 2013.
  * [17] QGIS Development Team.  Qgis documentation and manuals.  https://www.qgis.org/en/docs/index.html, 2020.  ”url accessed on 12/04/2020”.


Software for creating pictures in the LaTeX environment

R. V. Bezhencev<EMAIL_ADDRESS>
###### Abstract

To create a text with graphic instructions for output pictures into LaTeX
document, we offer software that allows us to build a picture in WIZIWIG mode
and for setting the text with these graphical instructions.

Keywords: LaTeX, TeX, GUI, drawing.

## Introduction

As we know, for drawing picture in LaTeX environment, user has to write
commands, which contain itself a set of primitives, which together completed
drawing. How creating LaTeX-integrated graphics and animations wrote Francesc
Sunol [1].

About drawing problems in LaTeX and motivation don’t integrated final image is
well described in the thesis Jie Xiao [2]. Since the process of creating
images in the LaTeX environment is not a WYSIWYG (“What You See Is what You
Get”), and reduced to manual writing graphics output commands in the TeX
language, the user has only to imagine how it will look finished drawing, and
approximately select control points.

This paper describes the software developed by the author of PaintTeX,
designed to solve this problem. It was developed in C and WinAPI, using the
methods of multi-threading, which guarantees the performance of the program.
To simplify the creation of drawings by other authors also develops software
Graphviz [2] for drawing graphs, Drawlets [2] for drawing arbitrary graphics
and FeynEdit [3] and JaxoDraw [4] for drawing Feynman diagrams.

##  1 Output line segment

To display the line segment or vector in the user text in addition to the
coordinates of reference point, it is necessary to specify a slope angle with
a width to height ratio. In the TeX language command output segment is as
follows:

    \put(60,50){\line(1,-2){20}}

where (60,50) - the coordinates of the start point of the segment, (1,-2) \-
angle as the ratio of length to height, 20 - the length of the projection on
the axis $OX$. Values in a proportion of given inclination should not exceed 6
in absolute value of segments, 4 of vectors, and don’t have common divisors
other than 1. Details can be found in the books of [5] and [6].

Created by the author software PaintTeX provides WYSIWYG interface for drawing
images using primitives, and then converts each primitive in the appropriate
command output graphics TeX language. For example, to draw the image shown in
picture 1, you need a long time to calculate the coordinates of control points
and other parameters of output commands for each graphic primitive, or fit
them around. This picture was painted in the program Paint TeX, the output
code is as follows:

    \begin{picture}(215,283)
    \qbezier(99,172)(105,172)(112,172)
    \qbezier(112,172)(108,174)(105,175)
    \qbezier(112,172)(108,171)(105,169)
    \qbezier(63,193)(82,170)(102,147)
    \qbezier(102,147)(100,151)(99,155)
    \qbezier(102,147)(98,149)(95,151)
    \qbezier(0,14)(111,14)(209,14)
    \qbezier(209,14)(205,16)(202,17)
    \qbezier(209,14)(205,13)(202,11)
    \qbezier(168,22)(89,129)(8,234)
    \qbezier(8,22)(93,22)(168,22)
    \qbezier(8,234)(8,128)(8,22)
    \qbezier(0,13)(0,145)(0,276)
    \qbezier(0,276)(-1,273)(-3,269)
    \qbezier(0,276)(1,273)(3,270)
    \put(64,192){\circle{38}}
    \put(101,160){V}
    \put(8,2){O}
    \put(10,283){Y}
    \put(215,0){X}
    \end{picture}

VOYX

Picture 1 - Example of a picture in LaTeX

Let us consider PaintTeX in action. The user selects the desired primitive and
draws it, pointing coordinates of the reference points on which the program
draws the primitive and stores them in memory. When user save a drawing
program inserts into the file text of outputting commands of the primitive
with stored coordinates of reference points. Complex primitives are displayed
in the form of a composition of simpler primitives, for example, vector - is
three straight lines, connections of the ends at the one point, which forms
the arrow, and rectangle - 4 straight. This method can display a myriad of
shapes, including three-dimensional.

##  2 How the program works

The principle of a program under development is as follows. When the program
starts, a window appears with menus, toolbar and drawing area. The user
selects the primitive on the toolbar, and then sets the coordinates of the
mouse control points. Control points are stored in an instance of the class
selected shape and it draws primitive. When you select “Save”, the program
saves output commands primitives in results file, inserting the necessary
parameters (coordinates, radius) from the coordinates of the control points.

For each primitive in the program is allocated class object of the primitive.
At the current stage of development, there are 7 classes: VETREX, LINE, LABEL,
BIZE, SQVR, CIRKLE, FISH. Each of these classes is a child of the base FIGURE
class. FIGURE class content that:

    class FIGURE
    {
    public:
        POINT *pt;
        FIGURE *nextFig;
    Ψvirtual void print() = 0;
    };

Due to the mechanism of inheritance, each child class inherits from a base
pointer types POINT, FIGURE and virtual function print (). When you create a
primitive, start initialization function, which converts a pointer *pt to the
array points, required for a given dimension of the primitive. That is, if you
create line segment, in the constructor LINE works command pt = new POINT[2],
and if the rectangle - pt = new POINT[4] in the constructor SQVR. Pointer
*nextFig serves to form a stack of primitives. Through the mechanism of
inheritance it can point to any class of the primitive.

Each description of classes of primitives in their own redefined output
function print(). This function writhen the primitive drawing commands into a
text file, from which a set of commands, and then you can copy in the article
and compile LaTeX tools. In each class, this function outputs in the file own
command and parameters, contained in the selected object. Below, for example,
is the content of a class of primitives “label”:

    class LABEL : public FIGURE
    {
    public:
    Ψchar *lab;
    Ψvoid ini (int x, int y, char *str, int len, HDC hdc)
    Ψ{
    ΨΨpt = new POINT;
    ΨΨpt[0].x = x;
    ΨΨpt[0].y = y;
    ΨΨlab = new char[len+1];
    ΨΨstrcpy(lab, str);
    ΨΨTextOutA(hdc, pt->x, pt->y, lab, strlen(lab));
    Ψ}
    ΨLABEL (){}
    Ψvoid print()
    Ψ{
    Ψofile << "\\put(" << pt[0].x - Canv_left << ","Ψ
        << Canv_top - pt[0].y << "){" << lab << "}" << endl;
    Ψ}
    }*label;

This class contains a pointer *lab, which is converted to a string for storing
text of the label, the initialization function, which stores the data in the
structure and draws the text, the function print(), a transformative figure in
the commands of graphics output with the crop, and a pointer *label,
responsible for work stack. Function to create a primitive “label” is as
follows:

    LABEL *new_label(int x, int y, char *str, int len, HDC hdc)
    {
    ΨLABEL *label_new = new LABEL;
    Ψlabel_new->ini(x, y, str, len, hdc);
    Ψif (!labelcount++) label_new->nextFig = 0;
    Ψelse label_new->nextFig = label;
    Ψreturn label_new;
    }

When the user draws a primitive, in this case, the label, the function of
creating passed the coordinates to reference point, text string, the length of
the string and device handle, which will be drawn text. Since for each new
primitive memory is allocated dynamically, it have to use for initialize the
initialization function, not the designer.

When you save commands, the program for each class of primitive creates a
separate thread. Each thread runs a function that using mutex synchronizes the
output of each command. Declaration of the function follows:

    void save(FIGURE *curfig, int counter)

As you can see, the argument * curfig - stack pointer primitives, and counter
- their total number. Through the mechanism of inheritance, each class
primitive is a class of FIGURE, which means for synchronous output primitives
of any class is sufficient to use a single function. So, thanks to the virtual
function print (), with curfig-¿ print (); You can access the output function
of each primitive, and the program will know what kind of entity it is
necessary to bring in a file.

Mathematical models have been taken from the book “ Mathematical Foundations
of Computer Graphics” cite momg. For example, a Bezier curve - parametric
curve given by the expression

$B(t)=\sum_{i=0}^{n}P_{i}b_{i,n}(t),0<t<1$

Where $P_{i}$ \- function of the components of the reference peaks, and
$b_{i,n}(t)$ \- basic functions of a Bezier curve, also called the Bernstein
polynomials.

$b_{i,n}(t)=\left(n\atop i\right)t^{i}(1-t)^{n-i}$

Where $\left(n\atop i\right)=\frac{n!}{I!(Ni)!}$ \- Number of combinations of
$n$ on $i$, where $n$ \- polynomial degree, $i$ \- number of reference peaks.
Since the syntax TeX can display curves only by three points, the formula for
the output has been simplified.

X = (1 - t)*(1 - t) * pt[0].x + 2*t*(1-t)*pt[1].x + t*t*pt[2].x;

Y = (1 - t)*(1 - t) * pt[0].y + 2*t*(1-t)*pt[1].y + t*t*pt[2].y;

Where pt[0].x, pt[1].x, pt[2].x - control points along the axis of $OX$, and
pt[0].y, pt[1].y, pt[2].y - coordinates of the reference points on the axis
$OY$. In the construction of the curve, the program increments t = t + 0.01
finds points on the curve, and then joins them small segments.

##  3 The problems in during the implementation the software

While working on the software adds the following problem. Since the values are
responsible for the slope in the primitive “segment” and “vector” must be
integers, and their number is very limited, and then the slope of the
primitive there is limited number of angles. A forthcoming software user draws
segments and vectors by specifying the coordinates of the starting and ending
point. Convert their coordinates in the output instruction in the TeX language
was not possible, so to print straight lines, it was decided to use Bezier
curves, defining the beginning of a line, a middle and an end. Since the
withdrawal of the Bezier curves does not specify a value for the slope and
length of the projection, the curves can be output through the straight
segments and vectors at any angle.

Just had a problem with the definition of the figure. In the LaTeX drawing
area is defined manually, and the user, as well as entities that also have to
pick up some, determining what sizes will be drawing. Thanks to the automatic
cutting PaintTeX defines the boundaries of the rectangle (canvas), which was
painted the image and crop a picture to fit your needs, inserting the
appropriate parameters in the command beginpicture().

Another problem - work with coordinates Windows and LaTeX. As the starting
point coordinates in Windows is the upper left edge of the window, and in the
LaTeX bottom left, when converting images to files saved coordinates Windows,
and then compile the image look in the mirror image vertically. Now PaintTeX
while saving the figure takes into account this nuance.

## References

  * [1] F. Sunol, Tools for creating LaTeX-integrated graphics and animations under GNU/Linux. - The PracTeX Journal, N 1 (2010), P. 1-12.
  * [2] X. Jie,Extending Two Drawing Frameworks to Create : Presented in partial Fulfillment of the requirements for the degree of master of computer science, Concordia University Monreal, Quebec, Canada, 2005. - 151 p.
  * [3] T. Hahn, P. Lang, “FeynEdit - a tool for drawing Feynman diagrams”, Munich, 2007. 9p. Preprint, arXiv:0711.1345v1 [hep-ph], Cornell Univ. http://arxiv.org/abs/0711.1345v1
  * [4] D. Binosi, J. Colins, C. Kaufhold, L. Theussl, “JaxoDraw: A graphical user interface for drawing Feynman diagrams. Version 2.0 release notes.”, Comput. Phys. Commun. 2008. 17p. Preprint, arXiv:0811.4113v1 [hep-ph], Cornell Univ. http://arxiv.org/abs/0811.4113v1
  * [5] S. M. Lvovsky, Typesetting set in the LaTeX system, St. Petersburg: Piter, 2003. - 448 p.
  * [6] D. E. Knuth, The TeXbook, part A series Computers and Typesetting. - Addison-Wesley, 1994, 640 p.
  * [7] J. A. Adams, D. F. Rogers, Computer-aided Heat Transfer Analysis, McGraw, N. Y., 1973. - 604 p.