text:
# What is the reason we loop over epochs when training a neural network?

After reading through this thread and some other resources online, I still do not understand the role of epochs in training a neural network. I understand that one epoch is one iteration through the entire data set. But I don't understand what happens when we finish one epoch and start the second, i.e., what is happening such that the error is reduced after each epoch?

Assuming we have an outer loop over epochs, and an inner loop for the gradient descent iteration. What happens is the following, at least to my understanding:

For the first epoch, we take some random initial parameters and perform, say, 1000 gradient descent steps until we have found a local minima where the loss is minimised. So we have landed in a local minima, but it could be a bad one and we want to find a better one, preferably even the global minima. However, this is what I was thinking about:

The only way we can escape a bad local minima is to start a new gradient descent search with different initial parameters, but it seems like starting a new epoch is not just taking different parameters and repeating the process. According to the loss plotted over epochs, the loss is decreasing after each iteration, so it seems like the parameters are not chosen randomly, instead it looks like there is some knowledge used from the previous epoch. First, I assumed that a new epoch just means starting a new search over the loss landscape, this time with another set of random initial values, such that we end up in a different local minima. However, it is not guaranteed that this local minima is a better one, so we could also land in a worse local minima.

But if I look at graphs where the loss is plotted over epochs, it almost always decreases quite smoothly with each epoch, indicating that every epoch does indeed lead to a better minima. This is where I get confused. How is this possible? What is happening at the start of a new epoch? In order to decrease the error, we must have knowledge from the previous iteration, which means that we do not just simply start with a different random set of initial parameters. So, how does a new epoch iteration contribute to a better result? What is happening that the loss is decreasing without ever rising due to worse local minima?

------------ EDIT ------------

I want to add this simple example: consider a simple linear network, no activation function. We have 2 inputs, each multiplied by a weight to generate a scalar output, i.e. the first step would look like:

x1[0]*w1 + x2[1]*w2 = out

where x1[0] contains the initial value and x2 is a different, known value. We want to find the weights w1 and w2 which minimise the loss between the output and the ground truth. In this case, I will work with one batch only, which contains the 2 inputs. The goal is to approximate a function linearly, given a known initial value. Then, I would run the training loop as follows

...
net = Net(2,1)
criterion = nn.MSELoss()
optimizer = optim.SGD(net.parameters(),lr=0.01)

for m in range(1,11):
inputs = torch.Tensor(x[m-1], x[m]])
for iteration in range(5000):
out = net(inputs)
loss = criterion(out, truth)
loss.backward()
optimizer.step()

This is just as snapshot of the loop, but basically the idea here is to find the appropriate weights for each point m of the function I want to approximate, by repeating the gradient descent search until we have found the local minima, and then proceed to the next point m+1 and so on. Using this example, how and why would a third loop over epochs decrease the error?

I am not expert on optimization, but I can share with you my knowledge of the topic.

I think that the source of your confusion is that you assumed that, after the first epoch, we have reached a local minimum. This is not necessarily true, although we might be on our way to get there, so that's why we usually have more than one epoch, and this should also explain why the loss decreases over epochs.

Moreover, as you correctly realised, we don't start the next epoch with new random weights. We start it with the weights that we found in the previous epoch.

Lastly, we might train the neural network with mini-batch (stochastic) gradient descent, which means that we split the original training dataset into $$M = \lceil N / B \rceil$$ batches, where $$N$$ is the size of the original dataset and $$B$$ is the batch size (typical numbers are 32 or 64). So, if you have, say, $$N=10000$$ and $$B = 32$$, then we have $$M = 312$$ mini-batches; so, for each epoch, you will perform 312 gradient steps, one for each mini-batch.

Now, although we use the same training data in different epochs, there are at least 2-3 reasons why the result of GD at the end of these epochs is different

1. at the beginning of each epoch, we may randomly shuffle the original training dataset before splitting it into mini-batches
2. even if that's not the case, we may feed the mini-batches in different order to the neural network
3. we start the epochs with different weights (e.g. in the first epoch, we start with random weights, in the second, we start with the weights found in the first epoch, and so on); think of a loss landscape with multiple minima (figure 1 here): the result of the optimization process depends on the starting point on this loss landscape
• but why would I terminate the inner loop which is the optimisation loop when I have not found a stationary point? I do as many iterations as needed until the gradients vanish, so I know I am at a local min. And if the new epoch starts, with the parameters from the last epoch, well we are at the same point again, so how do we escape from there? Or, is the loop over epochs what I call here the optimisation loop? For simplicity, lets assume I do not have multiple batches, but one batch with all the data Apr 8 at 16:56
• I guess the answer to your question is in the 1st and 2nd point (regarding GD) in my answer, i.e. at the beginning of every epoch, you may randomly shuffle the training dataset before splitting it into mini-batches or, alternatively, you may feed the model with another (probably random) order of the mini-batches (wrt the previous epoch).
– nbro
Apr 8 at 17:00
• You could do what you say, i.e. not have epochs, but, if after you've gone through all your training data (with the mini-batches), you shuffle the training data again, conceptually, it makes sense to highlight that point in time (i.e. the beginning of another epoch). Right now, I don't remember whether libraries like Keras or PyTorch do exactly this (i.e. whether they shuffle the training dataset at the beginning of every epoch before splitting). You may want to look at that ;)
– nbro
Apr 8 at 17:00
• In any case, this is just a conceptual distinction, i.e. even if you shuffle the training data at some point, you could not have the epochs and just have "GD updates". One library (which I know of) that does something similar, but in the context of reinforcement learning, is stable-baselines. It doesn't have episodes (which would be the rough equivalent of epochs in supervised learning) but just "training steps".
– nbro
Apr 8 at 17:06
• thank you for your thoughtful explanations! after going through the documentation of PyTorch and some introductory videos I figured out where the confusion comes from: I approached the training of a neural network from an optimisation methods point of view. What you explained makes totally sense, however, I was picturing a very simple linear regression problem with 2 inputs and one output. For anyone having the same confusion, I will post an answer to my own question where I have more characters left:) Apr 9 at 13:19


text:
Aaron Lauterer

# Biblatex - Customizing citations

Recently I had a friend who needs to write essays on a frequent basis for their studies. After hearing how they were struggling with Microsoft Word in combination with the citation style mandated by their university department, I suggested the use of LaTEX.

So one evening we sat together and created a template for her to use which would fit these requirements. After a lot of searching in LaTEX forums and the Tex part of stackexchange.com, we managed to get the citation style the way needed.

This blog posts documents on what we needed to change. Mainly for myself to avoid going down the same rabid hole of stackexchange and forum threads again in the future.

Quite a few commands and fields of BibLaTEX are overwritten in this example. I can recommend the BibLaTEX documentation to read detailed descriptions what these commands and fields are.

Let´s get started with a minimal working example (MWE).

\documentclass{article}
\usepackage[
style=authoryear,
backend=biber,
useprefix=true
]{biblatex}

\begin{filecontents}{cites.bib}
@InBook{einstein,
author =       "Albert Einstein",
title =        "{Mein Weltbild}",
publisher =    "Wisdom Library",
pages =        "110 - 112",
year =         "1935",
}
\end{filecontents}

\begin{document}
Let's have some citation here \parencite[111]{einstein}.

\printbibliography
\end{document}

After running the following commands,

pdflatex -synctex=1 -interaction=nonstopmode sample.tex
biber sample
pdflatex -synctex=1 -interaction=nonstopmode sample.tex

the resulting PDF file looks like this:

There are a few things about the default authoryear style that needed to be changed. The first is how the page number in the citation within the text is presented. Currently this is (Einstein 1935, p. 111). The way it should look is (Einstein 1935: 111).

Adding the following lines will change this.

\renewcommand*{\postnotedelim}{\addcolon\space}
\DeclareFieldFormat{postnote}{#1}
\DeclareFieldFormat{multipostnote}{#1}

The first line changes the delimiter from the comma to a colon with a space. The second two lines change the template and make it place only what we put in the [] brackets of the citation.

Now only the bibliography needs to be adapted. Currently, it looks like this:

Einstein, Albert (1935). “Mein Weltbild”. In: Wisdom Library, pp. 110–112.

What we needed it to be was:

Einstein, Albert (1935): "Mein Weltbild", In: Wisdom Library, pp. 110-112.

Note the colon after the author year part and the comma instead of a dot as separator. This can be achieved by adding the following lines:

\renewcommand{\newunitpunct}{\addcomma\space}

The first line overwrites which delimiter is used while the second line overwrites the delimiter which is placed after the authors name and year.

The final result now look like this:

The final MWE:

\documentclass{article}
\usepackage[
style=authoryear,
backend=biber,
useprefix=true
]{biblatex}

\begin{filecontents}{cites.bib}
@InBook{einstein,
author =       "Albert Einstein",
title =        "{Mein Weltbild}",
publisher =    "Wisdom Library",
pages =        "110 - 112",
year =         "1935",
}
\end{filecontents}

format: plain


text:
# #MonthOfJulia Day 31: Regression

Today we’ll be looking at two packages for regression analyses in Julia: GLM and GLMNet. Let’s get both of those loaded so that we can begin.

julia> using GLM, GLMNet

Next we’ll create a synthetic data set which we’ll use for illustration purposes.

julia> using Distributions, DataFrames
julia> points = DataFrame();
julia> points[:x] = rand(Uniform(0.0, 10.0), 500);
julia> points[:y] = 2 + 3 * points[:x] + rand(Normal(1.0, 3.0) , 500);
julia> points[:z] = rand(Uniform(0.0, 10.0), 500);
julia> points[:valid] = 2 * points[:y] + points[:z] + rand(Normal(0.0, 3.0), 500) .> 35;
6x4 DataFrame
| Row | x        | y       | z       | valid |
|-----|----------|---------|---------|-------|
| 1   | 0.867859 | 3.08688 | 6.03142 | false |
| 2   | 9.92178  | 33.4759 | 2.14742 | true  |
| 3   | 8.54372  | 32.2662 | 8.86289 | true  |
| 4   | 9.69646  | 35.5689 | 8.83644 | true  |
| 5   | 4.02686  | 12.4154 | 2.75854 | false |
| 6   | 6.89605  | 27.1884 | 6.10983 | true  |

By design there is a linear relationship between the x and y fields. We can extract that relationship from the data using glm().

julia> model = glm(y ~ x, points, Normal(), IdentityLink())
DensePredChol{Float64,Cholesky{Float64}}},Float64}:

Coefficients:
Estimate Std.Error z value Pr(>|z|)
(Intercept)   2.69863  0.265687 10.1572   <1e-23
x             2.99845 0.0474285 63.2204   <1e-99

The third and forth arguments to glm() stipulate that we are applying simple linear regression where we expect the residuals to have a Normal distribution. The parameter estimates are close to what was expected, taking into account the additive noise introduced into the data. The call to glm() seems rather verbose for something as simple as linear regression and, consequently, there is a shortcut lm() which gets the same result with less fuss.

Using the result of glm() we can directly access the estimated coefficients along with their standard errors and the associated covariance matrix.

julia> coef(model)
2-element Array{Float64,1}:
2.69863
2.99845
julia> stderr(model)
2-element Array{Float64,1}:
0.265687
0.0474285
julia> vcov(model)
2x2 Array{Float64,2}:
0.0705897  -0.0107768
-0.0107768   0.00224947

The data along with the linear regression fit are shown below.

Moving on to the GLMNet package, which implements linear models with penalised maximum likelihood estimators. We’ll use the Boston housing data from R’s MASS package for illustration.

julia> using RDatasets
julia> boston = dataset("MASS", "Boston");
julia> X = array(boston[:,1:13]);
julia> y = array(boston[:,14]);			# Median value of houses in units of \$1000

Running glmnet() which will fit models for various values of the regularisation parameter, λ.

julia> path = glmnet(X, y);

The result is a set of 76 different models. We’ll have a look at the intercepts and coefficients for the first ten models (which correspond to the largest values of λ). The coefficients are held in the betas field, which is an array with a column for each model and a row for each coefficient. Since the first few models are strongly penalised, each has only a few non-zero coefficients.

julia> path.a0[1:10]
10-element Array{Float64,1}:
22.5328
23.6007
23.6726
21.4465
19.4206
17.5746
15.8927
14.3602
12.9638
12.5562
julia> path.betas[:,1:10]
13x10 Array{Float64,2}:
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.127841  0.569442  0.971462  1.33777   1.67153   1.97564   2.25274  2.47954
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0     -0.040168
0.0  0.0        0.0       0.0       0.0       0.0       0.0       0.0       0.0      0.0
0.0 -0.0843998 -0.153581 -0.196981 -0.236547 -0.272599 -0.305447 -0.335377 -0.36264 -0.384493

Now that we’ve got a bundle of models, how do we choose among them? Cross-validation, of course!

julia> path = glmnetcv(X, y)
Least Squares GLMNet Cross Validation
76 models for 13 predictors in 10 folds
Best λ 0.028 (mean loss 24.161, std 3.019)

We find that the best results (on the basis of loss) were achieved when λ had a value of 0.028, which is relatively weak regularisation. We’ll put the parameters of the corresponding model neatly in a data frame.

julia> DataFrame(variable = names(boston)[1:13],
beta = path.path.betas[:,indmin(path.meanloss)])
13x2 DataFrame
| Row | variable | beta       |
|-----|----------|------------|
| 1   | Crim     | -0.0983463 |
| 2   | Zn       | 0.0414416  |
| 3   | Indus    | 0.0        |
| 4   | Chas     | 2.68519    |
| 5   | NOx      | -16.3066   |
| 6   | Rm       | 3.86694    |
| 7   | Age      | 0.0        |
| 8   | Dis      | -1.39602   |
| 9   | Rad      | 0.252687   |
| 10  | Tax      | -0.0098268 |
| 11  | PTRatio  | -0.929989  |
| 12  | Black    | 0.00902588 |
| 13  | LStat    | -0.5225    |

From the fit coefficients we can conclude, for example, that average house value increases with the number of rooms in the house (Rm) but decreases with nitrogen oxides concentration (NOx), which is a proxy for traffic intensity.

Whew! That was exhilarating but exhausting. As a footnote, please have a look at the thesis “RegTools: A Julia Package for Assisting Regression Analysis” by Muzhou Liang. The RegTools package is available here. As always, the full code for today is available on github. Next time we’ll look at classification models. Below are a couple of pertinent videos to keep you busy in the meantime.

The post #MonthOfJulia Day 31: Regression appeared first on Exegetic Analytics.


text:
Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 118

Notice: A non well formed numeric value encountered in D:\InetPub\vhosts\orbifold.net\orbifold.net\default\wp-content\plugins\crayon-syntax-highlighter\crayon_formatter.class.php on line 119

Bare bones of neural networks

This is an intro to neural networks and does not assume prior knowledge. Theano is used here but almost identical code could be written for TensorFlow.

Neural networks are, like so many great ideas, in essence easy to understand but things get quickly out of hand if you increase the size or the complexity. That’s the reason why you have things like Keras, TFLearn and other meta-frameworks which hide the underlying plumbing of tensors and gradients.

The maths you need to grasp neural networks is fairly basic; some standard algebra and derivatives. If you look up the literature you encounter a bit more (at most path integrals) but it all boils down to very concrete and straighforward strategies. At some point things like quantum networks will become popular and engender a different kind of maths but for now things are easy.

First we’ll review the concepts and try to explain the basic ingredient; what is a tensor, what is a gradient and so on. Thereafter we tackle what a single neuron does or can do.

What is a tensor?

A tensor is simply a multi-dimensional matrix. From a strict mathematical perspective the word tensor is abused in the context of computer science. In reality a tensor is related to Riemannian manifolds and obeys precise transformation laws under coordinate transformations. So, it’s fine to use tensor as a synonym of multi-index matrix but don’t be too surprised if you look up in the literature what a tensor really is.

A tensor has an order or degree and a zero-tensor is also called scalar. It’s like a function or something returning a number. A 0-tensor on the real line is a simple real-valued function. Similarly, a 1-tensor is a vector and a 2-tensor is a 2d-matrix.

Tensors are used in neural networks because one transforms incoming vectors into different dimensions. Much like PCA in machine learning, things are sometimes crushed to lower dimensions. When dealing with images one linearized a 2d-object into a 1d-object. Or imagines that you have a digital marketing model with a latitude/longitude, browser caps and whatnot. If you bring it all together in one tensor you have many ways to observe visitors. It could also be the input for a neural network.

What is a neuron?

A neuron is a little box which receives some input and output some stuff. It can receive one number or many, it can output sound or images or anything you like. People usually describe a neuron as something which receives a vector $x$ and then transforms it like

$\sigma(w.x+b)$

with $w$ is a matrix called the weights, $b$ another vector called the bias and $\sigma$ a so-called activation function. Nothing prevents you to use something else. If you can find a way to use a neuron which predicts the arrival of a train on the basis of

$\theta(\sin(u.x)^7x)$

you will be rich and famous. That is, anything is valuable but certain things are easier to approach than others. The statement

$w.x+b$

is a linear transformation and linear things are easier than non-linear. Much of the successes of science are based on linearizations of complex phenomena. For example, elasticity is linear if you don’t stretch things too far. Describing an oscillator is based on a linear force. The thing is that coupling many linear things leads to complexity. If you couple many oscillators you get chaotic phenomena. Similarly, if you combine neurons which intrinsically have a linear mapping from a vector to another vector you can get complex output. Cellular automata are also a great example of how simple transformations lead to intensily complex output.

The activation function can be seen from different angles. It’s useful because it can switch on/off the output. It can also be seen as a way to increase the contrast in the linear transformation.

Let’s give an example. One of the often used activation functions is the sigmoid or smooth step-function. It’s like the step function but with a smooth transition. The smoothness matters also from a math perspective because this kinda function can be differentiated (technically; it’s continuous and differentiable).

If you plot it with various values for alpha you will see that the higher the alpha value the more the step is strict/steep.

Now, let’s take the linear transformation (with an arbitrary matrix w, here random) and see what the sigmoid does to the transform.

The sigmoid stretches the output and is like increasing the contrast in an image. It dissipates the irregularities and increase the true signal. So, in a neural network this helps to reduce the propagation of noise or less important information as data moves across the network.

Another popular activation function is based on the hyperbolic tangent:

As you can see, the tanh has a similar effect. At this point it’s useful to emphasize that there are no hard criteria to decide which activation function to use. Anything works and ultimately the accuracy of what you are trying to do justifies the choice of an activation function.

For example, if you take something like the sine function you emphasize the signal around the origin (with proper rescaling of the axis):

So, there you go. A single neuron takes in some numbers and outputs some numbers. In practive one uses a linear transformation with an activation function on top of it.

Side note: why is linearity so useful?

The linear transformation $w.x+b$ can be seen as a transformation or a separation. If you ask when the transformation is zero, that is

$w.x+b==0$

you effectively define a separation in space. You divide the vector space in two regions. From a machine learning point of view this is equivalent to defining a classification.
Of course, real-world problems are never mathematically clean so separating a whole space with one line never works well. Let’s say the separation works well for negative numbers but is a different separation for positive numbers. In that case you need to define two linear transformations and switch from one to the other halfway. This ‘switching’ is precisely where activation functions come in: you keep the linear separation but you switch things on/of with the sigmoid (or whatever works best).
At the same time, many quirky separations (i.e. w iggling line) can be approximated by means of linear segments. This is in fact a common trick in maths: you defined something for segments and then generalize the whole lot by approximating the complex by means of linear segments. That’s how integrals are defined, that’s how simplices and differentiable manifolds are defined. So, here as well. If you have a complex machine learning problem you can approximate the complex separation by means of linear separations which act only within a small (sub)domain.

Practice makes perfect: optimization and gradients

Imagine darts or hunting or whatever shooting activity you prefer. You aim and the visual feedback tells you whether to shift a little to the right/left/whetever. You feed the arrow with a vector (the direction) and the difference between your aim and the place where the dart landed is an indication of how to adjust. Big mistake means big shift. The closer you are to the hotspot the finer the shift.

Training a neuron (or network in general) is very much the same. You want some output and compare the reality with what you wish to adjust the weights of the neuron.

Now remember that the bias is not a weight? There is an easy trick to make it appear as a weight. You extend the input with one dimension, assign 1 to the extra dimension and you are done. It’s a bit like looking at Euclidean spaces from a projective point of view; you add an extra dimension to deal with infinity. So, the transformation becomes homogenous and the weights and bias can all be treated in the same way when training a network.

The crucial things about adjusting things is; how does one know how to adjust the weights in order to increase the precision? That’s where gradients and derivatives come in.

Imagine you are skiing and you want to get down to the valley as quickly as possible. The slope is crucial here, the steeper the faster. Similarly, if you have a function which tells you how far you are away from your aim you take the tangent and follow that route to get as fast as possible to the minimum of the function. In the context or neural networks (by the way, the same happens when dealing with genetic algorithms) this is called the error function. The error function tells you the difference between the output and the value you actually would like to have. Obviously, the lower the error the better your network performs.

So, here is the great principle of the so-called back-propagation algorithm: you start with random weights, see what comes out, look at the error and adjust the weights according to the gradients/tangents of the error function to get as quickly as possible to the minimum of the error function.

It’s called back-propagation because you go back to your network to tell it how well it performed. Of course, much like going down to the valley while skiing, the terrain changes as you go and you cannot assume that the direction you take will remain constanst; you need to adapt to the terrain in small chunks. Similarly, you achieve perfection with a neural network by improving things in chunks. This is called epochs and refers to the fact that you need to feed the network many times with the available data to adjust the weights.

The mathematical translation of a slope or tangent is the concept of derivative of a function. This is not the place to explain calculus and there are plenty of resources on the net to see the light. It should be clear in any case that matrices, functions and derivatives are variable objects in a neural network. So, you should understand that a framework which deals with neural nets has to be capable to take the derivative of functions and deal with arbitrary tensors. Obviously, not all functions are meaningful (anyone seen incomplete Besself functions for activation?) and, hence, typical frameworks like TensorFlow and Theano deal with a limited set of functions.

Basic Theano mechanics

Plain and lengthy explanations aside, let’s see how neural networks are made possible in Theano. It should be clear at this point that there are some main ingredients when dealing with neural networks:

• tensors or matrices
• functions
• derivatives
• optimization (how to get somewhere as fast as possible)

So, let’s review how these things are done in Theano.

Things in Theano (and TensorFlow) are abstract and not defined directly like ordinary variables. There are two reasons for this:

• things defined in these frameworks run both on CPU and GPU, so you need a meta-model which gets translated to the architecture where it will effectively run
• you need to take the derivative of a function sometimes and allowing things for arbitrary (Python) function is not possible, so one has a safe sandbox rather than using the generic function definitions.

With T as the namespace for Theano tensors you define a scalar as

and define abstract functions using the ordinary operations

or the proper Theano operators

If you want to effectively use such an abstract function you can do so by defining a map with the abstract variables:

You can define similarly abstract 1-tensors

and so on with T.dmatrix, T.dtensor3 etc. As mentioned above, the framework has some differential calculus integrated. So, let’s define a more complex function

and take the derivatives (the grad from gradient)

and the effective abstract form of the derivate can be obtained via the Theano pretty print (pp) function

Don’t worry about the whole expression, it’s an example demonstrating the fact that Theano can deal with some calculus. If you like this sort of stuff you should take a look at the Theano documentation which also highlights other calculus-related constructs like the Hessian and Jacobian. These things have to do with transformation of coordinates, integrals and more. In most cases you will not deal directly with these objects but if you implement your own neurons you will encounter them.

Now, how do we use all of this to optimize a neuron? Let’s take an even easier situation; finding the minimum of a function. The general problem is that of finding an extremum which includes both the minimu and the maximum. The mexican hat function is a good example because it exhibits both a maximum and multiple minima. This function is the prototypical example of how spontaneous symmetry breaking leads to mass (via the Higgs boson) in particle physics but that’s another story.

Let’s try to find the right minimum by means of the slope. This is the so-called gradient descent approach. You start somewhere, follow the slope and try to reach the valley. In this case we use the variable w as the to-be-found weight to minimize the mapping of values around 1. That is, our x-values are

and we try to find a value for w such that the sum

is minimized. Think of the mexican hat as a neuron, the x-values as input and the aim to reach zero as output.

If take the derivative of the hat and set this to zero (the usual way to find an extremum) you will see that the minima are at +/- the square-root of 2. Using the Theano mechanics we can see this by defining first some functions

note that w is here a shared variable and not a scalar. The optimization with gradient descent is obtained by shifting systematically in the direction of the gradient:

The optimized value of the weight is: 1.41592163386

The reason why the convergence does not go to zero (as you might expect) is because the precise minimum is the sum with the exact square root of two:

which corresponds with what you see in the line-plot above.
Of course all of this is rather tedious and is only to show you how the whole optimization of a neuron works. Theano has a much more direct way to reproduce this:

At this point it’s probably good to add a few remarks:

• the example above can be generalized in all directions; more neurons, different tensorial dimensions, different optimizations and more
• frameworks like Theano an TensorFlow enable the construction of arbitrarily complex topologies of coupled neurons and run on top of both cpu and gpu
• you don’t need to fully understand all the intricacies of Theano to use it. If a new research paper demonstrates a faster way to get to a minimum value it likely gets integrated in, say, TensorFlow but the higher level functions remain the same
• the backpropagation works with this simple type of neuron (aka perceptron) but one needs more mechanics to deal with so-called recurrent networks and other topologies. A neural network considered as a graph can have loops and create situations where data keeps flowing or does not converge
• convergence of weights is a topic on its own. There are theorems proving the convergence of weights and bias based on certain conditions but there is in general no guarantee that training a network leads to converging parameters
• our mexican hat has actually two minima and one can have in general many extrema and minima which are not global minimums. This is, as well, a whole research topic.
• neural networks are like flows of tensors (hence the appropriate name TensorFlow) but real-world data often needs to be preprocessed before one can feed a net. Sentences, images and sound can be converted to tensors in various ways and while there are standard approaches there is no mathematical or other constraint to approach things differently. The whole field of neural networks is a much an art and a craft as it is a science. To some extend, if something works for your situation, that’s OK. Even if there isn’t any literature proving it should work.
• training a network is a costly thing. The convergence above is obtained after 300 loops. In general, one has to use highly parallelized algorithms on GPU’s to obtain things in a timely fashion. Microsoft and other giants typically run experiments on hundreds of GPU’s sometimes in a span of weeks. So, if things seem slow on your end, don’t imagine the magic of neural networks comes cheap
• Theano does not come with high-tech optimization algorithms but TensorFlow does. Theano does not have for example the so-called adadelta optimizer (among other). Both frameworks have pro/con and all depends on what you want to do. Meta frameworks like Keras and TFLearn have even more hidden powers but you are less in control
• the training of a network does not necessarily have a unique solution. Some networks can have infinitely many solutions. Some have none. To prove or disprove things mathematically is quite difficult. Usually you need to simulate things and see what gives. Experience and intuition are your friends.

Some examples

Now that the general concepts and the Theano mechanics is explained, let’s see what one can do with neurons.

Boolean logic

Basic neurons can simulate boolean logic. Take the AND operator, it’s straightforward to implement it.

We’ll train the neuron in a moment but let’s first show that there is a solution:

Cool, it works with this solution. Can we discover it?

The result of this training shows that we get a completely different but equally functional estimate of the weights. This demonstrates the non-uniqueness of neural network weight distribution.

If you wonder where the odd error or loss function comes from, this is called the cross-entropy loss function and is fairly standard way to compare results and targets which supposedly are binary. It has its origins in information theory.

Side note: using R for an AND network

The package neuralnet in R allows you to create an AND gate with much less code:

The great thing about this R package is that is also allows you to plot the network.

Maybe something which is also not immediately clear from the whole discussion above is that you can create networks which simulates multiple functions at the same time. Say, you want to output both AND and OR with the same net:

Have fun, you can create in principle any real-value function in this fashion. Yes, literally, there are hard mathematical proofs of this fact and it’s known as the universal approximation theorem or the Hornik theorem.

You can easily play with this fact in R, here an example of approximating the sine function with a deep network:

What does it take to compute an AND and OR gate at the same time in Theano. You simply define two neurons and optimize them in the same loop:

At this point it should become clear that devloping more complex neural topologies leads to complex expressions and series of variable definitions. This is were Theano stops being useful and where meta-frameworks step on stage. Theano should be considered like simpy or some other low-level abstract computation framework. If you want to create some real-world neural networks you need to move beyond Theano.

In another article we’ll explain how Keras allows you to create more complex neural networks and how various topologies (e.g. recurrent neurons) can solve real-world problems.


text:
### This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

### This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

# ANSI - INCITS/ISO/IEC 8825-1

## Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)

active, Most Current
 Organization: ANSI Publication Date: 28 December 2004 Status: active Page Count: 34
##### scope:

This Recommendation | International Standard specifies a set of basic encoding rules that may be used to derive the specification of a transfer syntax for values of types defined using the notation specified in ITU-T Rec. X.680 | ISO/IEC 8824-1, ITU-T Rec. X.681 | ISO/IEC 8824-2, ITU-T Rec. X.682 | ISO/IEC 8824-3, and ITU-T Rec. X.683 | ISO/IEC 8824-4, collectively referred to as Abstract Syntax Notation One or ASN.1. These basic encoding rules are also to be applied for decoding such a transfer syntax in order to identify the data values being transferred. It also specifies a set of canonical and distinguished encoding rules that restrict the encoding of values to just one of the alternatives provided by the basic encoding rules.

### Document History

INCITS/ISO/IEC 8825-1
December 28, 2004
Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)
This Recommendation | International Standard specifies a set of basic encoding rules that may be used to derive the specification of a transfer syntax for values of types defined using the notation...
December 1, 2000
Information technology - ASN.l encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER) AMENDMENT 1 : Relative object identifiers
A description is not available for this item.
December 15, 1998
Information technology ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)
A description is not available for this item.


text:
# Rage against the (EV)Machine part 1: contract size

November 7, 2019

Originally published on Aragon One Official Blog

## Introduction

In this blog post series we are going to explore and share with you some issues that we experienced while building Aragon Network’s Court smart contracts.

Working with the Ethereum Virtual Machine has several limitations that can become frustrating. Sometimes it feels like using an old 20th century computer. Besides, it’s often counter-intuitive, e.g., it has a 256 bits architecture, which sounds quite futuristic compared to common 32 and 64 bits nowadays.

In this post, we are going to talk about the first of the issues we run into: contract size.

## The problem(s)

The maximum size a contract can have is limited in two ways.

The first one, quite obvious, is the gas cost of the deployment transaction: more code in your contract means more bytecode to be included in the original tx, and thus a higher gas cost. Right now Ethereum mainnet limit is about ~10M gas. Make sure you don’t go beyond that limit, or whatever it is when you deploy if you are running your tests with a big limit (something like ganache-cli -l 50000000). You can check the current gas limit value here.

The second way, less intuitive perhaps, is the infamous EIP-170. This prevents deploying any contract that has a bytecode size greater than 2^13 + 2^14 = 24576. You can easily check the deployment size of a contract with the following command (assuming you are using Truffle and therefore your compiled contracts are under build/contracts), just copy-paste it in your terminal:

    cat build/contracts/<YourContractName>.json | jq '.deployedBytecode' | wc -m | xargs -I {} echo "{} / 2 - 1" | bc

If you don’t have jq installed, you can try:

    cat build/contracts/<YourContractName>.json | grep deployedBytecode | cut -d':' -f2 | cut -d'"' -f2 | wc -m | xargs -I {} echo "{} / 2 - 1" | bc

# The solutions

We tried several approaches to mitigate the issue of contract size. Initially I disassembled the code and tried to manually inspect the resulting bytecode in order to try to detect patterns that could be unexpectedly and unnecessarily increasing the size. For instance trying to identify functions having a bytecode size too big compared to the amount of logic they contained, too often repeated patterns or any other thing which I could not think of previously and caught my eye. This was not only extremely laborious, but pointless, precisely because the contract we are dealing with is so big. However, it was a good exercise, and allowed me to learn and get some inspiration.

This blog post series by my team mate Ale was very helpful, and so was his pocketh tool.
After traversing this arduous path, and having learnt our lessons (the hard way), we arrived to a series of rules of thumb that we hereby present to you:

This one could seem pretty obvious, and it’s something we considered from the very beginning. For instance, here we discussed if we should use our Staking app externally or embed it into the Court contract instead. We first took the embedding approach, and started building a monolith with all the needed components (like the aforementioned Staking or the Voting app) to save gas and because we needed simplified versions of them. This didn’t play well with contract sizes. Soon enough, we weren’t being able to deploy our contracts.

Sometimes splitting things apart is not that easy to implement. To start with, you have to take care of shared state and try to make sure that the resulting smaller contracts are independent from each other, as having to maintain state in two different contracts is error prone. This can be especially tricky with inheritance, as you may have a hidden shared state in the base contract. So you will need a careful analysis before moving forward.

Another thing to consider when splitting contracts, is that there is some gas overhead when contracts call each other. Roughly about ~2000 gas for calling outer contracts, as you can see here. As a side note, although not directly related to our subject in this post, when splitting your contracts, make sure your functions are external instead of public whenever possible, as it will save you some gas too by avoiding to copy parameters into memory and reading from calldata instead. Something nice about Solidity 5, is that it forces you to use memory and calldata for public and external functions respectively, so you are more aware of this difference.

In our case we ended up splitting Commit Reveal Voting, the Sum Tree, and Staking from the big monolith the Court initially was. (Later some other splits, refactors, and renaming took place, but they were not related to contract size issues)

## Shorten error messages

It’s a good practice to add an error message whenever your code reverts. It’s especially helpful while testing, but here you don’t need a beautiful, detailed, and user friendly error message (we were using all uppercase with underscores to start with). You will use these errors either programmatically to check proper assertions in your tests, when the revert is expected, something like:

    await assertRevert(court.createAppeal(disputeId, roundId, appealMakerRuling, { from: appealMaker }), 'CT_DEPOSIT_FAILED')

or when manually trying to fix a bug, when the revert is unexpected and Truffle shows you something like:

    Error: Returned error: VM Exception while processing transaction: revert CT_ROUND_NOT_DRAFT_TERM -- Reason given: CT_ROUND_NOT_DRAFT_TERM.

In the first case, it doesn’t really matter what the message says, as it’s the computer that reads those messages. In the second case it’s going to be you, but you just need a little hint if any, as you will probably end up inspecting the code anyway and see where the error was being thrown.
Eventually web3 may support a way to produce more meaningful, front-end friendly error messages for the user. But again, it should be the front end code which translates those short messages to human readable ones. Meanwhile you can even document those errors with better explanations, like Compound does.

So, you don’t need long and user friendly error messages. Here you can see an example of these reductions.

Let’s dig a bit deeper into this so you can decide for yourself. Initially we were working under the assumption that everything under 32 chars long was ok, and this is true without compiler optimizations. Have a look at these two simple contracts:

    contract ErrorMessages1 {
function getDouble(uint256 _a) external pure returns (uint256) {
require(_a > 0, "A");
return 2 * _a;
}
}

contract ErrorMessages2 {
function getDouble(uint256 _a) external pure returns (uint256) {
require(_a > 0, "AAAA");
return 2 * _a;
}
}

If you compile these contracts (we are using solidity 0.5.8) you’ll see that both have a length of 282 bytes. If we disassemble the code we’ll see that the relevant lines are:

    134 {0x7f} [c208, r176] PUSH32             0x4100000000000000000000000000000000000000000000000000000000000000

and

    134 {0x7f} [c208, r176] PUSH32     0x4141414100000000000000000000000000000000000000000000000000000000

respectively. So indeed 32 bytes are always used, no matter how short strings are.

But if we turn on optimizations (so far we have runs = 1) then we get instead:

    118 {0x60} [c164, r133] PUSH1 0x41

and

    121 {0x63} [c166, r135] PUSH4 0x41414141

If you try to compare both outputs, you’ll notice that those different bytes produce of course some disaligments in the bytecode, as the jump destination points will be shifted due to the increase on that string, and also other side-effects in the optimized compiler which I was not able to understand. For instance in this example size goes up from 204 to 209, so it increases by 5 instead of by 3, but as a good rule of thumb you can count approximately that you save one byte per character.

## Make variables private to avoid auto-generated getters

Whenever you declare a variable public, Solidity automatically generates a getter for it (with the same name). Even if you can’t initially see it, it’s in the compiled bytecode and so it adds up to the contract size. The hint here is obvious; convert to internal any variable that you don’t want to access from the outside, or that you already have a function that does that (maybe combined with other variables, or because you want to access it in a different way).

## Be aware of modifiers

I personally dislike modifiers a lot, as they are easy to overlook. Having something that can modify state, that can run at the beginning, the end, or both, of your function (you don’t really know unless you check) in the function header instead of the body sounds like a terrible idea to me. But modifiers have a great advantage too: they are inline code, a feature that I miss a lot in Solidity. Regarding the matter of contract size, this advantage can be a problem too, as inlining means repeating code and therefore increasing bytecode size. Compare these two contracts:

    contract WithModifiers {
modifier check(uint256 _a, uint256 _b) {
require(_b > 0, "ERROR_B_ZERO");
require(_a >= _b, "ERROR_A_LESS_THAN_B");
_;
}

function add(uint256 _a, uint256 _b) external pure check(_a, _b) returns (uint256) {
return _a + _b;
}

function sub(uint256 _a, uint256 _b) external pure check(_a, _b) returns (uint256) {
return _a - _b;
}

function mul(uint256 _a, uint256 _b) external pure check(_a, _b) returns (uint256) {
return _a * _b;
}

function div(uint256 _a, uint256 _b) external pure check(_a, _b) returns (uint256) {
return _a / _b;
}
}

contract WithoutModifiers {
function add(uint256 _a, uint256 _b) external pure returns (uint256) {
check(_a, _b);
return _a + _b;
}

function sub(uint256 _a, uint256 _b) external pure returns (uint256) {
check(_a, _b);
return _a - _b;
}

function mul(uint256 _a, uint256 _b) external pure returns (uint256) {
check(_a, _b);
return _a * _b;
}

function div(uint256 _a, uint256 _b) external pure returns (uint256) {
check(_a, _b);
return _a / _b;
}

function check(uint256 _a, uint256 _b) internal pure {
require(_b > 0, "ERROR_B_ZERO");
require(_a >= _b, "ERROR_A_LESS_THAN_B");
}
}

Bytecode size for the first one is 1449 while for the second one is 769. These numbers can vary depending on how you configure the compiler (see below), but it’s definitely something worth checking.

## Group getters and other external function considerations

Adding external functions has a bit of overhead due to the function selector (this is quite small though) and the function wrapper. Sometimes you can group a few together and save space too.

There’s another subtlety we found in our Court contract. Look at this commit. Let’s focus on the important parts. We started with this code:

    constructor(...) public {
(...)
_setConfig(...);
}
(...)
function _setCourtConfig(...)
internal
ensureTerm
{
(...)
}

And then added this other function:

    function setCourtConfig(...)
external
only(governor)
{
_setCourtConfig(...);
}

This change accounts for an increase of ~2600 bytes. How is this possible? Yes, we have the function selector, and the function wrapper, and all those parameters, and the modifier. But the selector is about 10 bytes, the wrapper is about 100… So what’s going on here if we are just calling an internal function that already exists? The answer is easy: as that internal function is called only from the constructor, initially it was present only in the creation code, but not in the runtime code. Now that it can be called after the contract has been deployed through this new external wrapper, the inner logic needs to be duplicated within the runtime code as well.

For better understanding of this section I recommend again Ale’s article mentioned above, and in particular this nice diagram.
As a general recommendation, always try to identify what code is only needed during deployment, and isolate it.

## Check optimizations

Right now we have this configuration in our truffle-config.js file:

    compilers: {
solc: {
version: '0.5.8',
settings: {
optimizer: {
enabled: true,
runs: 1
},
},
},
}

The important thing here is that number 1. This means that it’s optimized as if the inner code were to be run only once (and then forgotten forever), and therefore prioritizes deployment over the inherent functions, which means that with this number it will produce the smallest bytecode size possible but it won’t care so much about functions gas costs; while if you set it, let’s say to 1000, it will optimize gas consumption as if the contract code was going to be used a thousand times. You can find another explanation here.

This is not good for us, because we expect our functions to be called a gazillion of times, and we would like to have them as optimized as possible, but if we try to increase the number of runs we surpass the EIP-170 max size. We are still working on it.

Thanks to Ale and John for reviewing this post.


text:
# A basic question on diameter of a metric space

A set S of real numbers is bounded if it has both upper and lower bounds. Therefore, a set of real numbers is bounded if it is contained in a finite interval.

While in a metric space a non-empty subset $S$ of metric space $X$ is said to be bounded set if its diameter is finite.

My question is: are both the definitions of boundedness are equivalent? Is it possible to determine diameter of every subset?

Is there any other criterion also to determine whether given subset of a metric space is bounded or not?

-

The diameter of a nonempty subset $S\subseteq X$ is defined to be $$\sup_{x,y\in S}d(x,y),$$ which is always defined (though it may be infinite). Thus you can always determine the diameter of a nonempty subset.
A nonempty subset $S\subseteq X$ having finite diameter is equivalent to $S$ being contained in some ball $B(x,r)$ for some $x\in X$ and some $r>0$. To see this, first suppose that $S$ has finite diameter $\Delta<\infty$. Pick any $x\in S$. Then $S\subseteq B(x,2\Delta)$, since $d(x,y)\leq \Delta$ for every $y\in S$. On the other hand, suppose that $S$ is contained in some ball $B(x,r)$, where $x\in X$ and $r>0$. Then for any two points $y,z\in S$, one has $d(y,z)\leq d(y,x) + d(x,z)\leq 2r$, so the diameter of $S$ is $\leq 2r$. I hope that answered your question!
If $\overline{S}$ is compact, then $S$ has finite diamter, since compact sets have finite diameter. That's probably the easiest condition. – froggie May 24 '12 at 1:03
For a general metric space, what do upper bound and lower bound mean? In $\mathbb{R}$, there is an ordering, which allows you to talk about upper and lower bounds. – froggie May 24 '12 at 2:03


text:
## Intermediate Algebra (12th Edition)

$\dfrac{q^{5/3}}{9p^{7/2}}$
$\bf{\text{Solution Outline:}}$ Use the laws of exponents to simplify the given expression, $\left( \dfrac{p^{-1/4}q^{-3/2}}{ 3^{-1}p^{-2}q^{-2/3}} \right)^{-2} .$ $\bf{\text{Solution Details:}}$ Using the extended Power Rule of the laws of exponents which states that $\left( \dfrac{x^my^n}{z^p} \right)^q=\dfrac{x^{mq}y^{nq}}{z^{pq}},$ the expression above is equivalent to \begin{array}{l}\require{cancel} \dfrac{p^{-\frac{1}{4}\cdot(-2)}q^{-\frac{3}{2}\cdot(-2)}}{3^{-1\cdot(-2)}p^{{-2}\cdot(-2)}q^{-\frac{2}{3}\cdot(-2)}} \\\\= \dfrac{p^{\frac{1}{2}}q^{3}}{3^{2}p^{4}q^{\frac{4}{3}}} \\\\= \dfrac{p^{\frac{1}{2}}q^{3}}{9p^{4}q^{\frac{4}{3}}} .\end{array} Using the Quotient Rule of the laws of exponents which states that $\dfrac{x^m}{x^n}=x^{m-n},$ the expression above simplifies to \begin{array}{l}\require{cancel} \dfrac{p^{\frac{1}{2}-4}q^{3-\frac{4}{3}}}{9} .\end{array} Changing the exponents to similar fractions, the expression above is equivalent to \begin{array}{l}\require{cancel} \dfrac{p^{\frac{1}{2}-\frac{8}{2}}q^{\frac{9}{3}-\frac{4}{3}}}{9} \\\\= \dfrac{p^{-\frac{7}{2}}q^{\frac{5}{3}}}{9} .\end{array} Using the Negative Exponent Rule of the laws of exponents which states that $x^{-m}=\dfrac{1}{x^m}$ or $\dfrac{1}{x^{-m}}=x^m,$ the expression above is equivalent to \begin{array}{l}\require{cancel} \dfrac{q^{\frac{5}{3}}}{9p^{\frac{7}{2}}} \\\\= \dfrac{q^{5/3}}{9p^{7/2}} .\end{array}


text: Speaker : Dr. Po-Han Lee (The Affiliated Senior High School of National Taiwan Normal University) 從玩遊戲到作研究- Complex root networks of Chinese characters 2017-06-28 (Wed) 15:00 - 16:00 Seminar Room 722, Institute of Mathematics (NTU Campus) There are several sets of Chinese characters that are still available today, including oracle bone inscriptions (OBI) in Shang Dynasty (about 1600-1046 BC), Chu characters (CC) used in Chu of Warring State Period (476–221 BC), Small Seal Script (SSS) in dictionary Shuowen Jiezi (SJ) edited by Xu Shen (ca. 58 – ca. 147 AD) in Eastern Han Dynasty (23-206 AD), and Kangxi Dictionary (KD) edited in 1710-1716 during Kangxi Emperor of Qing Dynasty (1644–1911). Such Chinese characters were all constructed via combinations of meaningful patterns, called roots. When two roots appear in the same character, they are connected by a link and a complex network of all roots (nodes) of a set of characters can be constructed. The clustering coefficient $C$, the average shortest distances between nodes $L$, the degree distribution, the average degrees of nodes $\bar{k}$, and the disassortative coefficient $r$ of a complex network can be calculated. Our studies indicate that roots of characters in OBI, CC, SJ and KD have characteristics of small world networks and scale-free networks. From OBI, Chu, SJ, to KD, $C$ and $\bar{k}$ have the evolution trend of becoming larger, $L$ has the trend of becoming smaller, and $r$ has the trend of becoming more negative.


text:
#### NumberTheory IMO

###### back to index

Let $a, b, c, d, e$ be distinct positive integers such that $a^4 + b^4 = c^4 + d^4 = e^5$. Show that $ac + bd$ is a composite number.

Solve in positive integers $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = \frac{4}{5}$

Prove there exist infinite number of positive integer $a$ such that for any positive integer $n$, $n^4 + a$ is not a prime number.

Prove for any positive integer $n$, the fraction $\frac{21n+4}{14n+3}$ cannot be further simplified.

If integer d is not equal to 2,5 or 13. Prove: there must exist two different elements $a$ and $b$ in set {2, 5, 3, d} such that $ab - Let$f(n)$denote the sum of the digits of$n$. Find$f(f(f(4444^{4444})))$. Prove that$\frac{5^{125}-1}{5^{25}-1}$is composite. Find all integers$a$,$b$,$c$with$1 < a < b < c$such that the number$(a-1)(b-1)(c-1)$is a divisor of$abc-1$. Prove that if positive integer$a$and$b$are such that$ab+1$divides$a^2 + b^2$. then $$\frac{a^2+b^2}{ab+1}$$ is a square number. Let sequence$g(n)$satisfy$g(1)=0, g(2)=1, g(n+2)=g(n+1)+g(n)+1$where$n\ge 1$. Show that if$n$is a prime greater than 5, then$n\mid g(n)[g(n)+1]$. Find all postive integers$(a,b,c)$such that $$ab-c,\quad bc-a,\quad ca-b$$are all powers of$2$. Proposed by Serbia Show that every integer$k > 1$has a multiple which is less than$k^4$and can be written in base 10 using at most 4 different digits. In a sports contest, there were$m$medals awarded on$n$successive days ($n > 1$). On the first day, one medal and$1/7$of the remaining$m − 1$medals were awarded. On the second day, two medals and$1/7$of the now remaining medals were awarded; and so on. On the$n^{th}$and last day, the remaining$n$medals were awarded. How many days did the contest last, and how many medals were awarded altogether? Determine all three-digit numbers$N$having the property that$N$is divisible by 11, and$\dfrac{N}{11}$is equal to the sum of the squares of the digits of$N$. Show that for any positive integer$n$, the value of$\displaystyle\sum_{k=0}^{n}2^{3k}\binom{2n+1}{2k+1}$is not a multiple of$5\$.


text:
Browse Questions

# Find the equivalent capacitance between A and B in the circuit shown below. If the ends ‘A’ and ‘B’ are connected across a 12 V cell, find the electrostatic potential energy of the system. (the capacitance of each capacitor is $100 \mu F$)

Can you answer this question?

$(A) 750 \mu l$


text:
# Bézier curve

## Primary tabs

\documentclass{article}
% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here

\providecommand{\PP}{\mathbf{P}}
\providecommand{\PB}{\mathbf{B}}
\providecommand{\PQ}{\mathbf{Q}}
\begin{document}
\section{Introduction}
B\'ezier curves are a particular family of curves in $\mathbb{R}^m$
that parameterize a smooth path \PMlinkescapetext{between} given points.
They are often used to model or approximate general curved shapes
because of their algebraic simplicity.

B\'ezier curves were originally developed by Paul de Casteljau in 1959. But it became a famous shape only when Pierre B\'ezier, a French engineer at Renault, used it to \PMlinkescapetext{design} automobiles in the 1970's.
They are now widely used in many \PMlinkescapetext{fields} such as industrial and computer-aided \PMlinkescapetext{design},
vector-based drawing, font design, and 3D modeling.

\section{Definition}
Given $n+1$ points $\mathbf{P}_i$ in $\mathbb{R}^m$,
the \emph{B\'ezier curve} for these \emph{control points} is the curve $\mathbf{B} \colon [0,1] \to \mathbb{R}^m$
defined by
$\mathbf{B}(t) = \sum_{i=0}^{n} \binom{n}{i} (1-t)^{n-i} \, t^i \: \mathbf{P}_i\,.$
The coefficients in this expression:
$b_{i,n}(t) = \binom{n}{i} (1-t)^{n-i} \, t^i \,, \quad i=0,\ldots, n\,.$
are the Bernstein basis polynomials.

\section{Special cases}
A B\'ezier curve between two control points is simply the line segment
between the two points:
$\mathbf{B}(t) = (1-t) \, \mathbf{P}_0 + t \, \mathbf{P}_1\,.$

For three control points, we have the quadratic B\'ezier curve:
$\mathbf{B}(t) = (1-t)^2 \, \mathbf{P}_0 + 2 t (1-t) \, \mathbf{P}_1 + t^2 \, \mathbf{P}_2\,.$

For four control points, we have the cubic B\'ezier curve:
$\mathbf{B}(t) = (1-t)^3 \, \mathbf{P}_0 + 3 t (1-t)^2 \, \mathbf{P}_1 + 3 t^2 (1-t) \, \mathbf{P}_2 + t^3\, \mathbf{P}_3\,.$

These are the most commonly employed versions of B\'ezier curves.

\section{Properties}

\begin{itemize}
\item Except for the first and the last points, where the curve starts and ends, the B\'ezier curve should not pass through any of the control points. i.e. all the controls points lie on the curve if and only if the curve is a straight line.

\item The curve is tangent to the segment of line $\overline{\mathbf{P}_0 \, \mathbf{P}_1}$ at the start and $\overline{\mathbf{P}_{n-1} \, \mathbf{P}_n}$ at the end.

\item It is easy to keep until the first order continuity when chaining curves. Moreover, every B\'ezier curve can be cut at any point into two new B\'ezier curves. In fact, the \PMlinkescapetext{design} industry uses series of B\'ezier curves with only 4 control points (a bicubic version of the equations) to draw complex shapes.

\item The curves never do fancy stuff and always remain within the convex hull of the control points.

\item For one and two points the definition is still valid and the result became a point and a segment of line, respectively.

\item But it is impossible to draw circles or arcs of circle.

\item It is also impossible to draw two parallel curves (except in trivial cases: straight line B\'eziers and coincident B\'eziers curves)

\item If the first and the last point are the same, the curve is closed. And if $\mathbf{P}_1$ and $\mathbf{P}_{n-1}$ are aligned with $\mathbf{P}_0$ then the curve is closed with a first order continuity.

\end{itemize}

\section{Curve Cut}

Let $\mathbf{B}_p(t)$ be a Bezier curve, defined by its control points $\mathbf{P}_0$ to $\mathbf{P}_{n}$ for $t \in [0,1]$.

Let $a, b$ be such as $[a,b] \subset [0,1]$
Let $u = {{t - a} \over {b - a}}$ be such as $\forall u \in [0,1], t \in [a,b]$

$\mathbf{B}_q(u)$ is a part of the initial bezier curve with new control points $\mathbf{Q}_{0}$
to $\mathbf{Q}_{n}$ whose \PMlinkescapetext{coordinates} will be determined.

For $n$ control points $\mathbf{B}(t)$ is a $n-1$-order polynom.

$\mathbf{B}_p(a) = \mathbf{B}_q(0)$

$\mathbf{B}_p(b) = \mathbf{B}_q(1)$

Let take $n-2$ more points, evenly spaced in [a,b]
$u_i = k / {n-1} \forall k \in [1 .. n-1]$

$\mathbf{B}_p(u (b - a) + a) = \mathbf{B}_q(u_i)$ for each $u_i$

For a 4 control points bezier curve
If we take $u$ in $(0, {1 \over 3}, {2 \over 3}, 1)$, hence $t_0$, $t_1$, $t_2$, $t_3$ respectively equal to  $a$, $\frac{b - 2 a}{3}$, $\frac{2b - a}{3}$, $b$

$\mathbf{Q}_0 = \mathbf{B}_p(t_0)$

$\mathbf{Q}_1 = {-15 \mathbf{B}_p(t_0) + 54 \mathbf{B}_p(t_1) -27 \mathbf{B}_p(t_2) + 6 \mathbf{B}_p(t_3)} / 18$

$\mathbf{Q}_2 = {6 \mathbf{B}_p(t_0) -27 \mathbf{B}_p(t_1) + 54 \mathbf{B}_p(t_2) -15 \mathbf{B}_p(t_3)} / 18$

$\mathbf{Q}_3 = \mathbf{B}_p(b)$


text:
# Range bit inversions and range set bit queries with a binary indexed tree

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows:

You are given a series of commands that operate on an array initially all zeroes.

1) Invert all bits from [a, b] (1 becomes a 0 and vice-versa)

2) Find the number of set bits from [a, b] (bits that have value 1).

I know that one way to solve this is using a segment tree with lazy propagation, but I want to see whether it can be solved using a binary indexed tree.

To start, I know that binary indexed trees can be used to do range increments and range sums as per my previous question.

Further, I know that the structure of a binary indexed tree is that the node $i$ stores a function of values form $i - 2^h + 1$ to $i$ where $h$ is $i \text{ and}-i$ which is sort of similar to a segment tree in which each node stores the merged value of its left and right children (2i and 2i + 1 in the array representation).

Binary indexed trees only operate on functions that are associative and have an inverse, (that is, function[a..b] = function[0..b] - function[0..a-1]). On the other hand, segment trees only need a function that is associative, as the range is built directly from smaller segments rather than being a difference of two other ranges.

Finding the number of set bits does seem to be a function where numSetBits[a...b] = numSetBits[0...b] - numSetBits[0...a-1]

except that inversion is not such a function. Could binary indexed trees somehow be cleverly modified (like was done to support range queries and updates) in order to solve this problem?

• Can you explain what is an associative function? I know the concept of associative operators, but not certain on associative function. – InformedA Dec 3 '14 at 5:09
• I don't think associative function is a formal term. Just one I made up. It is essentially a function that can operate across a range of values (like addition where you add each element in the list) and the following is true: f[a..b] + f[b..c] = f[a..c]. – 1110101001 Dec 3 '14 at 5:19
• In that case, you need to have a kind of ordering on the function's domain which is also not a thing I know of when defining a function. – InformedA Dec 3 '14 at 5:26


text:
Plummer Sphere, Density from Potential

1. Feb 26, 2013

SHISHKABOB

1. The problem statement, all variables and given/known data
It wants me to get the density function of a Plummer sphere from its gravitational potential.

2. Relevant equations
Plummer sphere potential:

$\Phi (r) = -\frac{GM}{\sqrt{r^{2}+a^{2}}}$

where phi is the potential as a function of radius from the mass, M. And a is a scale factor of the model. I think I'm just supposed to take M as a constant here.

I am supposed to end up with

$\rho = \frac{3a^{2}}{4\pi}\frac{M}{(r^{2} + a^{2})^{5/2}}$

3. The attempt at a solution

So according to Poisson's equation

$\nabla ^{2} \Phi = 4\pi G \rho (x)$

So to solve for ρ I just took the derivative of Phi twice with respect to r twice and then divided by 4πG

first derivative got me

$2rGM(r^{2} + a^{2})^{-1/2}$

and then the second derivative got me

$\frac{GM}{2}\left[2(r^{2} + a^{2})^{-3/2} - (r^{2} + a^{2})^{-1/2}\right]$

then after a bit of rearranging I have ended up with

$\frac{M}{8\pi}(r^{2} + a^{2})^{-1/2}(2 - \frac{1}{r^{2} + a^{2}})$

I'm not really sure if I'm on the right track...

2. Feb 26, 2013

voko

The Laplacian is not "taking the derivative with respect to r twice". Look up its expression in spherical coordinates (or derive it, if you are not supposed to know).

3. Feb 26, 2013

SHISHKABOB

ohhh yes you are right, thank you. That explains a lot


text:
# Exploring shortest paths – part 1

I am trying to find the length and location of the shortest path between objects. It seems like some application of bwdist should be able to do this. Any advice? Example:

1 0 1
0 1 0
0 0 0
0 1 0
1 0 1

Should yield

0 0 0
0 0 0
0 p 0
0 0 0
0 0 0

With p = path length = 1

I agree, some application of bwdist should do it. Actually, there are several other useful functions that can be applied to this task, including imregionalmin and bwdistgeodesic, a new function that just shipped in R2011b.

I've been tinkering with this problem off and on for a few days, and I think it might take a few posts to explore some of the interesting ideas and issues posed by this problem. Today I'll start with the basics of using bwdist and imregionalmin to identify a set of shortest paths from one object to another.

Let's use this simple test image to start our exploration.

bw = [ ...
0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0   ]
bw =

0     0     0     0     0     0     0     0     0     0     0     0
0     1     1     0     0     0     0     0     0     0     0     0
0     1     1     0     0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0     0     1     1     0
0     0     0     0     0     0     0     0     0     1     1     0
0     0     0     0     0     0     0     0     0     0     0     0

We want to find the shortest path (or paths!) from the upper left block of foreground pixels to the lower right block. The key algorithmic idea is this:

1. Compute the distance transform for just the upper left block of foreground pixels.
2. Compute the distance transform for just the lower right block of foreground pixels.
3. Add the two distance transforms together.
4. The pixels in the regional minimum of the result lie along one or more of the shortest paths from one block to the other.

(For reference, see P. Soille, Morphological Image Analysis: Principles and Applications, 2nd edition, Springer, 2003, section 7.3.4, "Application to minimal path detection," pp. 233-234.)

But we can't use the normal Euclidean distance transform because it doesn't correspond to a path traversal from one pixel center to another. Rather, we have to use one of the distance transform approximations supported by bwdist: 'chessboard', 'cityblock', and 'quasi-euclidean'.

Here's how to do it using 'quasi-euclidean'.

bw1 = [ ...
0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0   ];

bw2 = [ ...
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0   ];

D1 = bwdist(bw1, 'quasi-euclidean');
D2 = bwdist(bw2, 'quasi-euclidean');

D_sum = D1 + D2;
D_sum(3:5, 3:10)
ans =

7.8284    7.8284    7.8284    7.8284    7.8284    7.8284    8.4142    9.0000
8.4142    7.8284    7.8284    7.8284    7.8284    7.8284    7.8284    8.4142
9.0000    8.4142    7.8284    7.8284    7.8284    7.8284    7.8284    7.8284

You can see that the smallest value of D_sum is about 7.8284, and there's a set of pixels in-between the two objects that all have that value. The function imregionalmin identifies them all:

path_pixels = imregionalmin(D_sum)
path_pixels =

0     0     0     0     0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0     0     0     0     0
0     0     1     1     1     1     1     1     0     0     0     0
0     0     0     1     1     1     1     1     1     0     0     0
0     0     0     0     1     1     1     1     1     1     0     0
0     0     0     0     0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0     0     0     0     0

In the quasi-euclidean approximation to the distance transform, the distance from a pixel to one of its horizontal or vertical neighbors is 1, and the distance from a pixel to one of its diagonal neighbors is sqrt(2). The result above says that the shortest such path between the two objects is 7.8284. Furthermore, it says that there is more than one shortest path.

I plan to explore this topic more fully this month. When using the quasi-euclidean distance transform, for example, there are floating-point round-off issues that have to be dealt with when you try to apply the technique above to larger images. Another issue is the effect of using different path-based distance transform approximations, such as 'cityblock' or 'chessboard'. Yet another issue is how to identify specific paths from the family of paths identified by imregionalmin. Along the way I'll experiment with different ways to visualize the results.

Finally, I'll explore how to use a new function, bwdistgeodesic, to find shortest paths when there are constraints on where the paths can go.

#### All the posts in this series

• the basic idea of finding shortest paths by adding two distance transforms together (part 1)
• the nonuniqueness of the shortest paths (part 2)
• handling floating-point round-off effects (part 3)
• using thinning to pick out a single path (part 4)
• using bwdistgeodesic to find shortest paths subject to constraint (part 5)

Published with MATLAB® 7.13

|


text:
2010
DOI: 10.1007/978-3-642-11735-0_26
View full text |Buy / Rent full text
|
|

## Abstract:We investigate two control problems related to the aerodynamic optimization of flows around airfoils in high-lift configurations. The first issue is the steady state maximization of lift subject to restrictions on the drag. This leads to a boundary control problem for the 2D stationary Navier-Stokes equations with constrained controls functions belonging to L 2 (Γ ) under an integral state constraint. We derive optimality conditions and treat the problem numerically by direct solution of the associated nonsmoo… Show more

Help me understand this report

Search citation statements

Order By: Relevance

Paper Sections

Select...
1

Citation Types

0
1
0

Year Published

2011
2011
2011
2011

Publication Types

Select...
1

Relationship

0
1

Authors

Journals

##### Cited by 3 publications
(1 citation statement)
##### References 33 publications
(46 reference statements)
0
1
0
Order By: Relevance
“…In the sequel, we outline a simple identification technique which has been employed in a number of turbulence control studies with periodic forcing (Luchtenburg et al, 2009a(Luchtenburg et al, , 2010John et al, 2010). Let f i be the propagator of the natural dynamics and b be the amplitude of a local actuator.…”
Section: Identification Of a Forcing Termmentioning
confidence: 99%
“…In the sequel, we outline a simple identification technique which has been employed in a number of turbulence control studies with periodic forcing (Luchtenburg et al, 2009a(Luchtenburg et al, , 2010John et al, 2010). Let f i be the propagator of the natural dynamics and b be the amplitude of a local actuator.…”
Section: Identification Of a Forcing Termmentioning
confidence: 99%