study

A wrong way to solve

About two weeks ago I met the “number of islands” problem in LeetCode. The first idea that jumped out of my brain is ‘dynamic programming’: I can create a new matrix (let’s name it ‘number matrix’) with the same size as the problem matrix, and set every position a value. The value is the number of islands from (0, 0) to this position.

For example, as the below problem matrix:

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

problem matrix

We can create the ‘number matrix’:

1	1	1	1
1	1	1	1
2	2	3	3
2	2	3	3

number matrix

Why the (4, 0) position in ‘number matrix’ is 2? Because the (0, 0) to (4, 0) area in ‘problem matrix’ has two islands:

(0, 0) to (4, 0) area of ‘problem matrix’

Then, every time we want to calculate the value of a position in the ‘number matrix’ we can first calculate the values of its ‘left’, ‘top’ and ‘left-top’ position.

For example, since the (3, 3), (4, 3) and (3, 4) positions in the ‘number matrix’ are all ‘3’, and the (4, 4) position in ‘problem matrix’ is ‘0’, the (4, 4) position of ‘number matrix’ should be ‘3’ also.

But unfortunately, after two weeks of struggling on thinking, I finally found out that the value of a position in the ‘number matrix’ can’t be decided by its nearest three positions: left, top and left-top. The counterexample is below:

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

problem matrix A

Let’s just build the number matrix for the (6, 6) to (7, 7) area of problem matrix A:

2	2
2

Don’t rush. Let’s look at another problem matrix:

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

problem matrix B

This time, we also build the number matrix for the (4, 4) to (5, 5) area of problem matrix B:

2	2
2

See? They have the same values for left, top and left-top, but different final results (problem matrix A has just 1 island but problem matrix B has 2).

Two weeks of hard thinking just got the wrong idea. But this is the charming of algorithm 🙂

My summary for the paper “Unified Language Model Pre-training for Natural Language Understanding and Generation”

For NLU (Natural Language Understanding), we use the bidirectional language model (like BERT), but for NLG(Natural Language Generation), the left-to-right unidirectional language model (like GPT) is the only choice.

Could we accomplish these two tasks by using one unified language model?

In this paper, the authors use a mask matrix to run different tasks in the same model:

The pivotal equation for this method is:

“M is the mask matrix and determines whether a pair of tokens can be attended to each other.”

“Unidirectional LM is done by using a triangular matrix for the self-attention mask M (as in the above equation), where the upper triangular part of the self-attention mask is set to −∞, and the other elements to 0”

“Within one training batch, 1/3 of the time we use the bidirectional LM objective, 1/3 of the time we employ the sequence-to-sequence LM objective, and both left-to-right and right-to-left LM objectives are sampled with the rate of 1/6”

Keep a note that the training process use bidirectional/unidirectional/seq2seq objective, not samples)

The low-power mode for STM8L and ATTINY2313

I used to think STM8L would cost less energy than ATTINY. Today I got some time to view the datasheet for these two MCU.

First comes the STM8L datasheet:

If we just use low speed oscillator (LSI) in the STM8L, it would only cost 0.9uA when all other components has shutdown.

How about ATTINY? Then comes the datasheet:

Since we need to enable watch dog timer (WDT) to wakeup, the ATTINY cost typical 4uA in low power mode.

Seems my memory is still correct 🙂 STM8L is the winner.

Attach references on arXiv.org

About one month ago I and my old colleague Jian Mei had published a paper about ornithology images on arXiv.org. But two days ago, Jian Mei found out that I have written the number of images and categories wrong.

To update the paper, I just packed my .tex and .bib files into a zip and uploaded this zip to arXiv.org to replace my old pdf. But strange things happened: all the references are lost.

Then I caught sight of the document. Since the arXiv.org only supports .bbl file instead of .bib, I need to compile the .bib to a .bbl file manually.

Could overleaf do it? Fortunately it could. Just upload the zip file and click the “Logs and output files” icon as below:

Then click the “Other logs & files” and choose “bbl file”. The bbl file will be downloaded. Finally, change the bbl file name to be the same with the .tex file (except the .bbl suffix) and pack them again to be a zip file.

This time, all references came back to the paper.

A convenient environment to write LaTex

More than one year ago, I wrote a paper about how to accelerate Deep Learning training for sparse features and dense features (images). For writing this paper, I installed a bunch of tools and plugins in my Mac-book and fixed a lot of errors for them by searching Google. Seems preparing LaTex environment on a local computer is really a pain in the neck.
Fortunately I found a convenient way today.
First, download your favourite template. For me the best template is CVPR-2020, from which anyone could download template. The template is a zip file.
Second, go to overleaf.com, sign up a new account. Then, in the top-left of the page, click “New Project”, and click “Upload Project”, choose the zip file above.
Third, now you would see a beautiful IDE for writing LaTex.

Enjoy!

How to writing papers with Markdown

Last weekend I exported my Jupyter Notebook records into a PDF format file. Surprisingly, the PDF file looks so good that I begin to think about using Jupyter Notebook or Markdown instead of LaTex to write technical papers because LaTex is an extremely powerful but inconvenient tool for writing. Then I created a file named ‘hello.md’:

# Head1
## First
There is a fox on the bank.
## Second
Hello

Then using a command line to convert the Markdown file to PDF (if you meet problems like ‘Can’t find *.sty’, just use ‘sudo tlmgr install xxx’):

pandoc -s -f markdown -t latex -o hello.pdf hello.md

The PDF file looks like:

It does works, but the appearance looks too rigid. Then I found the ‘pandoc-latex-template‘. By downloading and installing the ‘eisvogel.tex’, I can generate PDF by:

pandoc --template Downloads/eisvogel.tex -s -f markdown -t latex -o hello.pdf hello.md

And the new style looks as below:

Actually, we can use this template more heavily. Change ‘hello.md’ to:

---
title: "How to write technical papers"
author: [Robin Dong]
date: "2019-04-19"
keywords: [Markdown, pandoc]
lang: "en"
...
# How to write technical papers
## Install pandoc
Visit pandoc website
## Download template
Visit [pandoc-latex-template](github https://raw.githubusercontent.com/Wandmalfarbe/pandoc-latex-template/master/examples/basic-example/basic-example.md)
## Equation
\begin{equation}
    E = m c^2
\end{equation}
## Source code
```python
    import torch
    a = torch.zeros([2, 3])
    print(a) # This is not java
```

Add a file ‘metadata.yaml’ for font:

---
fontsize: 13pt
---

Then the command line:

pandoc --template Downloads/eisvogel.tex -s -f markdown -t latex -o hello.pdf hello.md metadata.yaml --highlight-style tango

The final document looks much more formal:

A few other lessons from Kaggle’s competition ‘Human Protein Atlas Image Classification’

Practice makes progress. Therefore I continued to join Kaggle’s new competition ‘Human Protein Atlas Image Classification’ after the previous one.
I used think I could get a higher rating in image processing competition. But actually, I haven’t even entered the top half of rankings. After almost three month trials and errors, here are my rethinkings:
1. To solve the unbalanced data problem, we need to use ‘focal loss’ instead of normal cross entropy loss. I should be looking at other experts’ kernels earlier, then I could use new techniques as soon as possible.
2. To augment images, ‘lower resolution’ may be a better way than ‘mix up’
3. Try SGD and Cosine Decay, not only RMSProp
4. MobileNet may cause severe overfitting than Resnet
5. If dropout and weight-decay still can’t get better affection for regularization, what should we do? (An open question, feature engineering may be the answer)
6. Use more powerful DNN framework, such as Keras, so I can spend more time on the model itself

Some tips about LaTeX

1. After running ‘bibtex paper’, it reports

Too many commas in name 1 of "J.Chen, R.Monga, S.Bengio, R.Jozefowicz" for entry Revisit_SGD

This is because we need to use ‘and’ to replace commas. After changing them

# Change 'author = "J.Chen, R.Monga, S.Bengio, R.Jozefowicz"' to
author = "J.Chen and R.Monga and S.Bengio and R.Jozefowicz"

The errors disappeared.
2. How to extend space between two rows in a table?
Answer:

\begingroup
\setlength{\tabcolsep}{10pt} % Default value: 6pt
\renewcommand{\arraystretch}{1.5} % Default value: 1
\begin{tabular}{ c c c }
First Row & -6 & -5 \\
Second Row & 4 & 10\\
Third Row & 20 & 30\\
Fourth Row & 100 & -30\\
\end{tabular}
\endgroup

3. Problem: Can’t upload .bib file in arXiv.org
Answer: run ‘pdflatex paper’ to generate paper.aux from paper.tex, and then run ‘bibtex paper’ to convert paper.bib to paper.bbl. Now we could upload .bbl file to arXiv.
4. Problem: When select ‘Tools’–>’Check Spelling…’ in texStudio, it report “No dictionary Available”.
Answer: Download english dictionary from https://extensions.openoffice.org/en/download/1471, change suffix from ‘oxt’ to ‘zip’ and unzip it. In ‘preferences’ of texStudio, set dictionary path to the unzip directory. (ref)
After solved all these problems, I eventually submit my paper here: https://arxiv.org/abs/1806.03925

Some details about Arduino Uno

In previous article, I reviewed some open source hardwares for children programming, and considered the Micro:bit is the best choice. But recently, after searching many different types of micro-controllers, I noticed an advanced version of Arduino Uno R3 (less than $3) is desperately cheaper than Micro:bit (about $16) in Taobao.com (a famous e-marketing website in China). Despite the low price, Arduino also have a simple and intuitive IDE (Integrated Development Environment):

The programming language for Arduino is Processing, which looks just like C-language. A python developer could also learn Processing very quickly, for it is also a typeless language.
I also find an example code of blinking a LED bubble by Arduino:

// Blinking LED
const int LED = 13; // LED connected to
                    // digital pin 13
void setup() {
  pinMode(LED, OUTPUT); // sets the digital
                        // pin as output
}
void loop() {
  digitalWrite(LED, HIGH); // turns the LED on
  delay(1000);             // waits for a second
  digitalWrite(LED, LOW);  // turns the LED off
  delay(1000);             // waits for a second
}

Easy enough, right? But it still have more convenient graphic programming tools, such as ArduBlock and Mixly

The demo of ‘ArduBlock’

The demo of ‘Mixly’

With Easy-learning language, and graphic programming interface, I think Arduino is also a good choice for children programming.

My choice between Raspberry PI, Arduino, Pyboard and Micro:bit

I want to teach my child about programming. But Teaching child to sit steadily and keep watching computer screen is not easy, I think, for children usually can’t focus on the boring developing IDE for more than ten minutes. Therefore I try to find some micro-controller which could be used to do some interesting works for kids, such as getting temperature/humidity from the environment, or control micro motors on toy car.
There are many micro-controller or micro-computer chips on the market. Then I have to compare them and finally choose the most suitable one.

Raspberry PI is very powerful. It could do almost anything that a personal computer or laptop can do. But the problem about Raspberry PI is it is too difficult to learn for a child. And another reason I give up it is the price: $35 for only the bare chip without any peripherals.

Arduino

Arduino is cheap enough. But you could only use C-language to program it. Using C-language need strong knowledge about computer science, such as memory models and data structures. Imaging use C-language to implement a working-well dictionary, it looks like building a space ship in the backyard for a pupil.
Until now, I could narrow my choices to chips that could support python, or micro-python. Because Python is easy to understand, looks much straightforward, and also could be used in imperative mode. In one word, it’s much easier to learn than C.
So let’s take a look at chips which support micro-python.

Pyboard

Pyboard is simple and cheap enough, and also supports micro-python. The only imperfection of it is that its hardware interface is hard to use for someone who doesn’t know hardware very well.

Micro:bit

Launched in 2015 by BBC, Micro:bit is the most suitable chip for a child to learning program and even IOT(Internet Of Things), in my opinion. It is cheap: only $18. It supports programming by micro-python and Javascript (Graphic IDE), so the child could using a few lines of Python code to control it. It also supports a bunch of peripherals such as micro motor, thermometer, hygrometer, Bluetooth and WIFI. Children could use it as core-controller to run an intelligent toy car. The Micro:bit even have Android/IOS app for operation, which is perfect for a little child under 7 years.
So this is my choice: Micro:bit.