The Master Algorithm

Definition of correlation

Recently, I was reading the book The Master Algorithm by Pedro Domingos — a Professor at the University of Washington in machine learning.

According to the description of his book,

The Master Algorithm in Machine Learning

A spell-binding quest for the one algorithm capable of deriving all knowledge from data, including a cure for cancer.

Society is changing, one learning algorithm at a time, from search engines to online dating, personalized medicine to predicting the stock market. But learning algorithms are not just about Big Data – these algorithms take raw data and make it useful by creating more algorithms. This is something new under the sun: a technology that builds itself. In The Master Algorithm, Pedro Domingos reveals how machine learning is remaking business, politics, science and war. And he takes us on an awe-inspiring quest to find ‘The Master Algorithm’ – a universal learner capable of deriving all knowledge from data.

So I thought about a master algorithm that exists for digital communication systems. I could not find one in general but for linear modulations under AWGN channels, Correlation is certainly the master algorithm. Correlation solves the detection problem by choosing the most probable hypothesis, correlation solves the receiver design problem by leading to numerous timing, frequency and phase synchronization algorithms (which are largely variations of a single concept derived through correlation), correlation leads to channel estimation and equalization techniques to combat channel distortions.

Due to these reasons, I called it the heart of digital communication systems in a previous article on correlation.

As an example, during our discussion on demodulation, we derived the expression for a matched filter with the process of correlation in the following manner.

Since the maximum overlap is the only sample within a symbol time T_M that is required out of L = T_M/T_S samples, let us write

(1)   \begin{align*}         z(T_M) &= z(nT_S) \bigg| _{n = L = T_M/T_S} \nonumber \\                 &= \sum \limits _i r(iT_S) p(iT_S-nT_S) \bigg| _{n = L = T_M/T_S} \nonumber \\                 &= \sum \limits _i r(iT_S) p\Big(-(nT_S - iT_S)\Big) \bigg| _{n = L = T_M/T_S} \nonumber \\                 &= r(nT_S) * p(-nT_S) \bigg| _{n = L = T_M/T_S}        \end{align*}

We concluded that the process of correlation can be implemented as convolution with a filter whose impulse response h(nT_S) is a flipped version of the actual pulse shape. That filter is called the matched filter. For details, see the article on demodulation.

Similarly, during the discussion on timing, phase and frequency synchronization for Volume 2 of the book, we will derive the relevant estimators through this process as well demonstrating that correlation is indeed the master algorithm in this domain.

Leave a Comment

Your email address will not be published. Required fields are marked *