Ujjwal's blog

Machine learning has proliferated our everyday lives leading to a number of data-driven decisions. Typically, applying machine learning requires good math skills in linear algebra, probability theory, and signal processing. This coupled with good programming skills go a long way to test new/existing algorithms on large amounts of data. I am a big fan of Matlab for testing machine learning algorithms as it provides very easy interface for matrix operations. Recently, I came to know that working with matrices in Python is also very easy. Therefore, I decided to write a series of blog posts about how to use Python for machine learning. The fundamental ideas will remain same weather we use R, Matlab, Python. 

As an example, I will mainly focus on supervised learning, as it is easier to make sense of. 

The main components are:

Reading raw data from a csv file (or some other file format)

Identifying the input features ($\mathbf{H} = [ \mathbf{h}_1, \mathbf{h}_2, ..., \mathbf{h}_p]$) and output $\mathbf{y} = [y_1, y_2, ..., y_n]^T$. This notation means that we have $p$ features and $n$ data points. Bold capital represents a matrix, otherwise bold represents a vector. $(\cdot)^T$ means the transpose operator. 

Divide the data into training and test set

Apply some supervised machine learning technique, such as linear regression or logistic regression to determine a mapping function from $H_i \rightarrow y_i,~~\forall~i \in [1,n]$ by using the training set. 

Then, apply the mapping function on test set to obtain predictions for $\hat{y_{test}}$

Plot this data together with known actual value to check the accuracy of the model

My goal is to write python code for each of these steps to successfully apply a supervised learning algorithm. Application of any other algorithm will then only require modifications of step 1, 4, 5. 

This post addresses the following question with the help of an example:  Question: Is  it possible to practically stabilize an unstable system without feedback?  Answer: Definitely, no!

Let us consider an unstable system with transfer function $P = \frac{1}{s-1}$. This plant has a pole on the right hand side plane in the s-domain, which means it is unstable. A naive (and incorrect way) to stabilize this system will be to employ a controller $K = \frac{s-1}{s+1}$ without any feedback. One might argue that the open loop transfer function $P\times K = \frac{1}{s+1}$ and the new pole now occurs at left hand plane of the s-domain, so this system must become stable. Unfortunately, it does not, due to at least two reasons:

The disturbances in the plant input and output can completely throw away the stability. This can only be corrected using feedback. 

Even in a disturbance free ideal world, all numbers are finite precision and have errors. So while computing $P \times K$, the $s-1$ terms in the numerator and denominator cannot completely cancel each other. 

Properly formatting references in a paper is important. I use Latex for typesetting all my papers and that is why BibTeX is a major part of adding references to the paper. Well, the challenge is that I want to have one master copy of a bib file that has all the references from all my papers. This is useful for writing a thesis as well as other papers that may reuse some of the references from an older paper. I tried several reference management software like Mendeley but never ended up using them for a long time. I wanted something simple and I thought of writing the code for parsing the bib entries myself. Then, I found Jabref software. It is a very simple software and has all the functionality that I need for reference management. Note, I am not advocating for any one software over the other, just writing about what I liked in Jabref.

It is easy to merge two bib files. It can find duplicates. You can merge the duplicates or choose to keep any one version.

I use the bib keys in the following format: [name][year][veryshorttitle] This is the same format how Google scholar produces keys.

The standard way to compute the variance of a data set is using the sqaure of the standard deviation. When we have scalar values $x_1, x_2, x_3, ..., x_N$, the mean $\mu_N$ standard deviation $\sigma_N$ for all the N values is computed as follows:

$$ \mu_N = \frac{\sum_{k=1}^N x_k}{N} ... (1) $$

$$ \sigma_N = \frac{\sqrt{\sum_{k=1}^N (x_k - \mu_N) }}{N} ... (1) $$

I already described in my previous blog post how to compute the mean in real time using the following algorithm at runtime: 

$$\begin{align}  & \mu_0 = 0;       \nonumber \\\ & \mathrm{for} \hspace{2mm} k = 1:1:N \nonumber \\\ & \hspace{4mm} \mu_k = \left( \frac{k-1}{k} \right) \mu_{k-1} + \frac{x_k}{k};   \nonumber \\\ & \mathrm{endfor} \nonumber \end{align}$$

This saves memory and is more elegent. 

Similarly, we can compute the variance of a data set using another recursive algorithm:

$$\begin{align} & \mu_0 = 0;       \nonumber \\\ & S_0 = 0;       \nonumber \\\ & \mathrm{for} \hspace{2mm} k = 1:1:N \nonumber \\\ & \hspace{4mm} \mu_k = \left( \frac{k-1}{k} \right) \mu_{k-1} + \frac{x_k}{k};   \nonumber \\\ & \hspace{4mm} S_k = S_{k-1} + \left( (x_k - \mu_k)(x_k - \mu_{k-1}) \right);   \nonumber \\\ & \hspace{4mm} \sigma_k = \sqrt\frac{S_k}{k} ;   \nonumber \\\ & \hspace{4mm} Var_k = \sigma _k^2 = \frac{S_k}{k};   \nonumber \\\ & \mathrm{endfor} \nonumber \end{align}$$ 

Note that, to compute the variance, we also require to compute the mean. 

I recently came across Pick’s theorem, which looks like a neat way to compute the area of a polygon drawn with its edges on a regular grid. The area of the polygon can be expressed using the number of points that lie on the boundaries of the polygon ($n_B$) and the number of points lying inside of the polygon ($n_I$) as follows:

$$Area = \frac{n_B}{2} + n_I - 1$$

This is just one of the ways of using Git. There are several other ways that can involve setting up your own server for repositories or using other services, such as Github. A good friend of mine, Ayush Rai helped me explore this procedure. Please note that I was using this procedure in 2015, so the steps below may have changed slightly. Let me know it this does not work.

Downloads

Bit-bucket: Setup an account in bitbucket.

Git: Install Git in your PC.

Smart-Git: Install Smart-Git client in your PC. The software is free for non-commercial use.

Setup

SSH key setup for your computer (You can use Git Bash for this step): link

Make sure that the .ssh folder is in your user folder. For example, Users/Ujjwal/

Add the key to your Bit-bucket account: link

Start Smart-Git and follow screen instructions to setup, you will be asked to provide your Bit-bucket username and password

That is it! You have the setup ready

How to learn Git?

The standard way to compute the mean (average) of a data set is to sum all the values and then divide by the total number of values. More explicitly, when we have scalar values $x_1, x_2, x_3, ..., x_N$, the mean $\mu_N$ for all the N values is computed as follows:

$$ \mu_N = \frac{\sum_{k=1}^N x_k}{N} ... (1) $$

Clearly, this is very simple. The simplicity comes at the cost of larger memory usage. This is because we have to store all the values from $x_1$ to $x_N$ in memory in order to compute the mean $\mu_N$. However, for real time systems performance and memory are critical. Therefore, a different method that computes the mean after every sample in a lightweight manner (without using too much memory) is required. One way is to use a recursive algorithm as follows: 

$$\begin{align}  & \mu_0 = 0;       \nonumber \\\ & \mathrm{for} \hspace{2mm} k = 1:1:N \nonumber \\\ & \hspace{4mm} \mu_k = \left( \frac{k-1}{k} \right) \mu_{k-1} + \frac{x_k}{k};   \nonumber \\\ & \mathrm{endfor} \nonumber \end{align}$$

Proof:  The proof is pretty easy. First use the formula for mean assuming $k-1$ values are known. Similarly, write formula of mean assuming $k$ values are known. Perform some simple algebra to obtain the solution of mean at $k$ in terms of mean at $k-1$ and new data $x_k$. Details are shown below:

$$\begin{eqnarray} & \mu_k = \frac{\sum_{i=1}^k x_i}{k} \\\ & \mu_{k-1} = \frac{\sum_{i=1}^{k-1} x_i}{k-1}  \end{eqnarray}$$ 

Now multiply the above equations by the denominator $k$ and ($k-1$),

$$\begin{align}  k\mu_k &= \sum_{i=1}^k x_i \\\ (k-1)\mu_{k-1} &= \sum_{i=1}^{k-1} x_i   \end{align}$$

Now subtract the first equation from the second equation and perform simple algebra,

$$ \begin{align}  k\mu_k - (k-1)\mu_{k-1} &= \sum_{i=1}^k x_i  - \sum_{i=1}^{k-1} x_i  \\\ \Rightarrow k\mu_k - (k-1)\mu_{k-1} &= x_k \\\ \Rightarrow k \mu_k &=  (k-1)\mu_{k-1} + x_k \\\ \Rightarrow \mu_k &= \left( \frac{k-1}{k} \right) \mu_{k-1} + \frac{x_k}{k} \end{align}$$  $\square$

I want to write some math equations in this blog. MathJax is a Javascript library that displays mathematical notation on web browsers. Apparently, we just have to copy paste the following code in Tumblr HTML, just before the <\head> tag:

<script type="text/x-mathjax-config">        MathJax.Hub.Config({        extensions: ["tex2jax.js"],        jax: ["input/TeX", "output/HTML-CSS"],        tex2jax: {        inlineMath: [[ '$','$']],        displayMath:  [['$$','$$']],        processEscapes: true        },        "HTML-CSS": { availableFonts: ["TeX"] }        }); </script> <script type="text/javascript" async       src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"> </script>

Example code: 

Maths between dollars is inline: $p = \alpha C_{dyn} V_{dd}^2f + I_{leak}V_{dd}$

Maths between two dollar signs is display as a separate equation: $$ p = \alpha C_{dyn} V_{dd}^2f + I_{leak}V_{dd} $$

Example output:

Maths between dollars is inline: $p = \alpha C_{dyn} V_{dd}^2f + I_{leak}V_{dd}$

Maths between two dollar signs is display as a separate equation: $$ p = \alpha C_{dyn} V_{dd}^2f + I_{leak}V_{dd} $$

Tips: 

Make sure that you write the math as normal text. If it is code type in tumblr then it will not be rendered. 

So the story goes like this…

I came back to ASU from Stone Ridge Technology with an incredible summer internship working on state-of-the-art FPGA RTL designs. Everyone working in this small start-up had a research mindset. This was intellectually very satisfying for me. Then, I met two more incredible folks: Prof. Martin Reisslein and Prof. Umit Ogras. They both helped me in unique ways to look at the research. I took Martin’s class in which he reinforced the need for surveying prior art. Umit joined ASU in Fall 2013 as an assistant professor. Frequent interactions with him made me very excited about exploring power management techniques in smartphones. Since the foundation of the power management techniques are power and performance models, we started exploring these models. In particular, we found a generalized form of Amdhal’s law. We got the idea for the performance model from a seminal paper from Hill and Marty on “Amdahl’s Law in the Multicore Era”. This gave the very first lesson about research. If we write a paper that is well thought out and easy to read, it will lead to more research ideas for everyone. We wrote the performance model and then my initial thought was to only publish the performance model that could be used for heterogeneous systems. However, Umit insisted that only the performance model was not sufficient for a good publication (rightly so!). This is because we need more mature ideas that not only show new models but also how they are useful.

“All models are wrong; some models are useful.” - George E. P. Box

Blogs look to be a convenient way to manage posts and content that is frequently posted. Tumblr looks to be a good blogging tool and I wanted to give it a try. So, the first thing I wanted to do is to embed the blog into my website to avoid having too many different online portals. I embedded Tumblr to my personal website using the following script:   <script type="text/javascript" src="http://ugupta.tumblr.com/js?start=0&num=5"></script>