## 我的2017

2017就要过去了，必须赶在今年留下点东西。因为想说的话太多，反倒一直不敢动笔写。已经不知道怎么梳理头绪了，就选几个关键词写写吧。

2015年左脚韧带断裂做的手术，养伤100天，然后开始漫长的复出之旅。现在打球防守时还是很吃亏，脚用不上力容易被ankle break，特别丢人。进攻时也终于切换成中年人打法：“节奏流”。常想如果单挑大学时的自己，不知道哪个会赢。体重也是稳中有升，终于突破了75kg大关。脚踝有伤的另一问题是，走路不能走多。按照微信运动显示，当天走过1万步的话，脚就会酸痛，而且第二天上午都缓不过来。剧烈一点的运动——就是篮球啦——因为大多脚尖着地发力，反倒问题不大。嗯，那就好。

Wish you a happy new year.

## Find all duplicates in two different arrays in LabVIEW, 200 times faster

Recently I have been learning Python, machine learning and Natural Language Processing (NLP). That’s why I didn’t post these days. In future posts, I hope I can share some interesting things in these subjects.

Yesterday I came across an algorithm that finds out all the same elements in two arrays in the Coursera NLP course provided by Stanford University. This algorithm was adopted when merging the same words in the two lists.
Imagine we have two arrays of [1, 2, 3, 4, 5, 6] and [2, 4, 6, 8, 10]. We look to find out the same elements in the two arrays which are [2, 4, 6]. Since there is a ‘Search 1D array‘ function in LabVIEW that can tell if an element is in the array. The implementation of this function is hidden and thus I’m not sure how it was done. Presumebally it iterates through the array and quits either if it finds the equavalent element or reaches the end of the array. So the iteration can take up to N times where N is the length of the array. When we want to compare two arrays with the lengths N and M respectively, the iteration could take up to N*M times.

I prepared two arrays with the lengths of 100k and 90k and used LabVIEW ‘Search 1D Array’ function to find out the same elements. See the code below:

The code iteratively checks if the element of 90k array can be found in the 100k array, and remove the element in the 100k array if found. The running time for the above code is about 7.3 seconds on my desktop. Because the arrays size is large, it could take up to 100,000 * 90,000 = 9,000,000 iterations to calculate this.

An alternative way of doing this is explained in the course. This algorithm moves both arrays simultaneously and thus the running time is much shorter. An illustration screen capture is shown below:

The two arrays compare the first elements from the beginning, and both move forwards if the two elements are equivalent. If the values do not match, move the array with the smaller value and carry on comparing with the next value. This calculation takes up to N + M (the sum of the two lengths) iterations. When the array are large, it saves a lot of time.
Following is the seudo code of the ‘merge’ algorithm.

Here is the LabVIEW implementation.

And the test VI:

This code takes 0.03 second to compute, which is more than 200 times faster!:D Although we put the ‘Sort 1D array‘ function before hand, it still beats the first algorithm. This code also works well with text arrays (you need to change the input data type of course). Try it out yourself.:)

Tags :

## 小斌

————————————————————————-

## Hidden Markov Model in LabVIEW

Consider this scenario: a guy (let’s call him John) has three dices, Dice 1, 2 and 3. The shapes of the dices are different. Dice 1 has number [1, 2, 3, 4, 5, 6] on it, Dice 2 has number [1, 2, 3, 4] and Dice 3 has [1, 2, 3, 4, 5, 6, 7, 8], as seen in the following figure.

http://www.niubua.com/?p=1733

John throws one dice each time and the probability he picks the next dice is based on his previous selection. For example, he is more LIKELY to pickup Dice 1 if he just picked Dice 2 last time, and he UNLIKELY to pick Dice 1 if he just picked Dice 3 last time. We do not know which dice he selected but we can see the number shown on the dice. Now, after the observation of a sequence of throwing dices, what do you think the next number would be?

This may sound a very difficult question but actually in linguistics the researchers are dealing with this kind of problem all the time. It’s like you can HEAR the sound of each word every time and based on the HIDDEN connection rule of the words (i.e. syntax and meaning) we want to predict what the next word could be. Mathematical models were built to represent this type of question. In this example, the states are determined by its previous state(s) and we call it Markov Model, or Markov Chain. A simple case is the state is determined by its previous one state — a Markov chain of order 1. Also, which dice (state) was selected is not know and instead, the consequence of the state (number) can be observed. It is called Hidden Markov Model.

There are three problems in HMM that need be addressed. They are 1) Evaluation: Given the probability of the state transmission and the probability of the shown observations of each hidden state (I.e. for a given HMM), calculate the probability of an observed sequence.  2) Decoding: Given the HMM and the observed sequence, what is the most likely hidden states happened behind this. 3) Learning: Given the observed sequence, estimate the HMM. As we can see from this, the third problem is the most difficult one.

Hidden Markov Model (HMM) is a powerful tool for analyzing the time series signal. There is a good tutorial explaining the concept and the implementation of HMM. There are codes implementing HMM in different languages such as C, C++, C#, Python, MATLAB and Java etc. Unfortunately I failed to find one implemented in LabVIEW. This may be a reinvention of the wheel, but instead of calling the DLLs in LabVIEW, I built one purely in LabVIEW with no additional add-ons needed.

Multiple references were used to implement this LabVIEW HMM toolkit. [1], [2], [3], [4]. The test demo of forward algorithm, backward algorithm and Viterbi Algorithm in the code referenced [2].

The following demo analyzed the hidden states of a chapter of texts. You can find the detailed description in [1]. The following figure is the observed sequence of the HMM model. There are about 50,000 characters (including space) in this text. All punctuations were removed and only the space and letters were kept as the hidden states. Thus there are 27 states, State 0 to 26, of which State 0 = Space, State 1 = a/A, State 2 = b/B and so on.

With no prior knowledge of this text, or even English, we initialize a HHM model that has two hidden states. The probability of propagating from one state to another is unknown yet. The 26 letters are the observed phenomenons of the hidden states. The probability of each letter in State 1 is plotted in dots, and the probability of each letter is plotted in line in the 2nd state.

Running the forward-backward algorithm in HMM we obtained two states: Letters A, E, I, O, U more likely to appear in State 1 while the rest letters more likely to appear in State 2. So with no specified rules or prior knowledge we managed to divide the letters into vowels and consonants.  🙂

[1] https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf
[2] http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
[3] http://www.52nlp.cn/hmm-learn-best-practices-one-introduction (Chinese)
[4] http://www.kanungo.com/software/software.html#umdhmm

Tags :

## Get the old Pocket button back for Firefox

Firefox has integrated the Pocket button into the browser since version 38.0.5. You can take out the Pocket button by navigating to the customize button of Firefox.

After you download this file, you shall be able to install it by simply double clicking. If not, go to the Add-ons page in Firefox, click the gear (‘tools for all add-ons‘) icon on the top-right, select ‘Install Add-on From File…‘ and select the downloaded .xpi file.

Enjoy your retro Pocket button 🙂

Tags :

## THE personal blog site

Hi all, sorry that I haven’t been updating the posts for a long while (again!) and I just moved my blog from foolooo.wordpress.com (again!) to here. Now finally I have a blog site hosted on my own computer — well, not really my computer, I just rent this server. And what is cooler is I have my own domain name now 🙂 So people from both China (GFW issue) and all other countries around the world can visit this website with no problem.

Another reason I moved my blog is I kinda look for some place to merge both the techy blogs (previous Let’s LabVIEW) and the personal blogs (previous FoOl’s BlOg) so that it’s easier to maintain in the future. I also try to learn/write more things in Machine Learning, Computer Vision and Natural Language Processing which do not have to be in LabVIEW.

This website is just built and still under construction. More widgets need to added in and a better name may come up soon. Hope to keep in touch. Thanks all.

Cheers,
Bo

## Two tiny functional VIs

For the last a few months I am still learning Machine Learning with LabVIEW (which might not be the best language for ML) and doing more signal processing jobs. I tried to follow some MOOC courses on R and Python to master better tools for ML. Really got some to-do projects in my mind and want to implement them soon.

Since I am dealing with a lot of file loading recently, this vi was built to scan a folder to find the file starts with the specific string. This is nothing complicated and I am sure there is a simpler solution. But here is an example of the implementation:

It iterates the names of the files and quits if finds the name starts with the “Start with” string.

Another function is “Random selection from elements“. It allows the user to randomly select from their own dataset, which could be a number of integers, strings or any other data types. Again this is very simple but I found it quite useful in many “simulation” applications.

The input array can be replaced by any other types of arrays. It is worth mentioning there is a “Riffle.vi” in LabVIEW that can randomly disorganize the input elements (so the output is a disorganized array). The randomness can be repeated by setting the seed to the same number.

## Genetic Algorithm in LabVIEW to solve the shortest path routine problem

I came across Genetic Algorithm (GA) the other day when I was doing the project. It is typically adopted to solve the shortest path routine problem or design and optimize the structure of proteins. It is a very smart algorithm inspired by the biological system.

I will try to describe the idea behind the concept briefly: In some problems there are many possible solutions, and we look for the best one. To find this very best solution it is like creating the chromosome of the genes in the most optimized order. To find out the best (-ish) combination, one way is comparing ALL possible combinations, which is impractical in some cases.  So instead of listing all solutions and comparing them, a sub-group of solutions (population) are created, and then we pick two out of them as the parents. The better the solution was, the higher chance it can be selected. Then the two chromosomes crossover (exchange genes) to “breed” new populations. There is a chance of mutation for the new population as well. The new population are usually more “advanced” than their parent population (not necessarily better than their parents). Then new parents are picked out again to breed new populations and so on.

Typically the genes to order in the chromosome are binary, but we can also do that for integer numbers and other values. Please find this tutorial for more encoding methods.

To demonstrate the implementation of GA in LabVIEW I downloaded the coordinates of 31 cities of China and tried to find out the shortest path routine of them. So here is the .gif demo (the labels for X and Y axises should be “Latitude” and “Longitude”). Please note that this may not be the BEST solution. But in term of the number iterations we ran it, it is good enough.

You can download this code here:. Please rename it to .zip file and unzip it.

Let me know your score 😉

Tags :

## A quick update for the Flappy Bird project

It seems last post was found by @labview and brought much visiting here. So this project is still undergoing and I was kind of busy this month. But I will try finish this ASAP 🙂

Here are some updates since last post.

An Arduino controlled stylus now can be controlled by clicking the mouse.

There is a tip that the stylus needs to be earthed (via the red wire) to take affect.

And the Flappy Bird game is (poorly) simulated on LabVIEW. So I simulated FB (not facebook!) on LabVIEW to test the Q-learning algorithm in a purely software environment. Now it can pass 5 gaps 🙂 The algorithm needs to be altered a bit and then I will integrate the whole things.

Tags :