Anytime Algorithm For Machine Learning

Please check our other blogs related with Machine Learning.
Machine Learning Blog

References

[1] Zhu, Qiang & Batista, Gustavo & Rakthanmanon, Thanawin & Keogh, Eamonn. (2012). A Novel Approximation to Dynamic Time Warping allows Anytime Clustering of Massive Time Series Datasets. 10.1137/1.9781611972825.86.

[2] Malone, Brandon & Yuan, Changhe. (2013). Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks. Uncertainty in Artificial Intelligence – Proceedings of the 29th Conference, UAI 2013.

Radar Image Compressing by Huffman Algorithm

In AI Lab, one of our projects is “Weather Forecasting”, in which we process the data from weather radars, and perform prediction using nowcasting techniques, i.e.  forecasting in a short-time period like 60 minutes.

To develop forecasting model and do evaluation, we need to run many test-cases. Each test-case corresponds to one rainfall event, whose duration can be several hours. In the rainy season, one rainfall event cans last for several days.

Given one event and one interested area (80km2 of Tokyo city for example). In our actual work, a list of arrays of rainfall intensity needs to be stored in machine. Each array corresponds to one minute of observation by radar. If the event lasts for 5 days, then the number of arrays is

60 minutes x 24 hours x 5 days = 7200 arrays

Therefore, storing a such amount of data costs a lot of memory.

One of solution is to modify the way feeding data to the evaluation modul. However, for the scope of this blog, let assume that we would like to keep that amount of data in computer. How do we do to compress data, and how much of data can be compressed?

The aim of this post is to introduce the Huffman algorithm, one of the basic methods for data compressing. By learning about the Huffman algorithm, we can easily understand the mechanism behind some advanced compressing methods.

Let us start with a question: how does a computer store data?

Data in computer language

Computer uses bits of {0,1} to represent numbers. One character of 0 or 1 is called a bit. Any string of bits is called a code.

Each number is encoded by a unique string of bits, or code. The encoder should satisfy the “prefix” condition. This condition states that no code is the prefix of any other codes. This makes it is always possible to decode a bit-string back to a number.

Let us consider an example. Let assume that we have a data d as a list of numbers, d = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3].

To store this list d, the computer needs to encode the three numbers: 1, 2, 3. The two possible encoders are:

Code/Number 1 2 3
Code 1 ‘0’ ‘01’ ‘11’
Code 2 ‘0’ ‘10’ ‘11’

But the Code 1 violates the ‘prefix’ condition, as ‘0’ is prefix of ’01’, while the Code 2 does not. Therefore, the Code 2 can be used for encoding.

So, how many of bits needed to represent N different numbers? In theoretically, we need codes of k-bits length to encode 2^k numbers.