pvigier's blog

computer science, programming and other ideas

Fractal Image Compression

One year ago, I coded a very simple implementation of fractal image compression for a course and I made the code available on github there.

To my surprise, the repo is quite popular. So I decided to update the code and to write an article to explain the theory and the code.

Read more ...

Tags: math python

Non empty destructors in C++

Have you already faced problems with nontrivial destructors?

I face one recently which was really annoying. In this article, I want to share with you my knowledge of this problem and the solutions I use to address it.

The problem

The problem is not really that the destructor is nonempty but that the destructor is nontrivial: there is a release of memory or some states are changed in another part of the app.

Let us take a very simple example with a class that does dynamic allocation to explain the problem:

class A
    A() : mPointer(new int(0))


        delete mPointer;

    int* mPointer;

As we allocate an integer in the constructor, the natural solution for memory management is to free it in the destructor. However, this will have terrible consequences.

For instance, if we do this:

int main()
    A a;
    A anotherA(a);

    return 0;

A segmentation fault will occur.


Because when the main function ends, the destructor of A is called to delete a and anotherA. When a is destroyed the memory cell to which a’s mPointer points to is freed. Then, when anotherA is destroyed, we try to free the memory to which anotherA’s mPointer points to. But as anotherA is a copy of a, its mPointer points to the same memory cell as a’s mPointer. Thus, we try to free twice the same memory cell which causes the Segmentation fault.

So, the problem is that because of the copy the destructor is called twice on the same attributes.

Note that the copy or move constructors are often called when we use containers. For instance, there is a copy or a move when the std::vector’s push_back is called.

Read more ...

Tags: cpp

Circular dependencies in C++

Hi guys, it has been a while since the last post.

I write this short post to tell you about a small script I coded recently. You can find it here on my github account.

Its goal is to draw the “include” dependencies between classes in a C++ project. In particular, it allows to detect circular dependencies very easily or to check the architecture of a project.

You can see the output of the script on a project of mine:

Dependency graph

I really like this visual representation which allows to see how classes interact.

However, the true reason why I created this tool is not because I like to see beautiful graphs but because I hate circular dependencies (note that there is none in the graph above). I consider circular dependencies as design flaws. But sometimes in a large project, it could happen that accidentally I create circular dependencies …

Read more ...

Tags: cpp python

Pychain Part 2 - Application: MNIST

In part 1, we have created a fully functional library which is able to create and train neural networks using computational graphs. We used them on very simple examples. Today, we are going to try it on a more serious problem: character recognition.

We are going to use a well-known database in the machine learning and deep learning world named MNIST. The database is available on Yann LeCun’s website. If you have read a bit about neural networks before you should have already seen his name. He is a French scientist who is one of the pioneers of neural networks and inventors of convolutional neural networks and he is now the director of AI at Facebook.

Character recognition is an emblematic problem for two reasons. Firstly, it is one of the first successes and industrial applications of neural networks. It was used since the 90’s to read checks. Secondly, computer vision has always been a leading application domain for neural networks.

In this part, we are going to briefly discover the MNIST database. Then, we are going to train some networks on it and finally, we are going to explore a bit how a neural network works.

Read more ...

Tags: math python

Pychain Part 1 - Computational graphs

Welcome in this big tutorial on neural networks!

Our goal is to write our own deep learning framework like TensorFlow or Torch. We are going to learn in-depth how neural networks work, all the mechanics behind them.

We will get our hands dirty and code everything! In this tutorial, we will use Python3 and scipy but I hope that the code and the ideas are clear enough so that you can adapt the code to your favorite language.

First, I show you the plan. In this part, we are going to quickly introduce neural networks and then, we will introduce computational graphs in order to model them. In the end of this part, we are going to use our implementation to learn some non-linear functions.

In the second part, we will deal with a more serious problem. We are going to build an optical character recognition system upon the MNIST database. It is a classical problem in machine learning, we have to do it.

Then, we will tackle recurrent neural networks and show how to model them with our library. To apply our new knowledge, we will try to learn a formal grammar generated by an automaton.

In part 4, we will go further with recurrent neural networks and introduce the well-known LSTM cell. We will briefly compare it with fully-connected recurrent neural networks.

To approach part 6, some more efficient optimization algorithms are necessary. Consequently, we will discuss them in part 5.

Have you ever read this fabulous article by Andrej Karpathy? Yes? Cool, because, we are going to reproduce his results with our own library in part 6. Amazing, isn’t it?

Finally, parts 7 and 8 are going to be theoretical appendices for the most curious readers.

Is it all? Maybe not! Stay tuned!

If you are ready, let’s go!

Read more ...

Tags: math python