Simplifying ML: Recommender Systems - Part 7

In this age of Amazon, Netflix and App stores where products, movies and apps are purchased online the method of up-selling and cross-selling online is through the use of recommender based systems.

When you go to site like Amazon/Flipkart or purchase apps on App store/Google Play we often see things like “People who bought this book/app also bought X, Y, Z”. These recommendations are the recommender system algorithms in action.

Recently, Netflix ran a competition in which users had to come with the best algorithm to recommend films that a user would also like. The prize money for this was of the order of $1 million. That’s how critical recommender systems are to organizations of today where most of the transactions happen on the web.

Typically users are asked to give a rating of 1 to 5 with 1 being the lowest and 5 being the highest.  So for example if we had classics like Moby Dick, Great Expectations and current best sellers like The Client, The da Vinci Code and a Science Fiction like 2001- A Space Odyssey we can expect that different people will rate the books differently. Obviously not everybody would have read every book in the list and some elements would be blank.

Recommender Systems are based on machine learning algorithms. The goal of these algorithms is to predict what score any user would give to books they did not rate. In other words what would be rating the buyers would give for books or apps they did not buy. So if the algorithm predicts a high rating then we could recommend that the user would also ‘like’ them. Or we could give recommendations of books/apps bought by users who bought the books/apps bought by this user.

The notation is

n_u = Number of users

n_b = Number of books

r^(i,j) = Boolean whether user j rated a book i

y^(i,j) = The rating user j gave book i

m_j  = The number of books that user j rated

Content based recommendation

In a typical content based recommendation algorithm we assume that we have data about some items we want to recommend rating for e.g. books/products/apps.  In the example for books bought in an online bookstore we assume some features in our case ‘classic’, “fiction” etc

So each book has its own feature vector where x¹ is the feature vector of the first book x²  feature vector of the 2nd book and so on

This can be done through linear regression by minimizing the cost function of the sum of squared errors from the predicted value

So for a parameter vector Ɵ^jand a feature vector xⁱ the recommender system will try to predict the rating that a user j will give a book i.

This can be written as

Number of stars (rating) = (θ^j) ^T xⁱ

This reduces to the minimization problem over all θ^j for r=1

min 1/2m Σ  ((θj)^T xⁱ  - y ^i,j)²

θ^j                  i:r=1

Adding the regularization term this becomes

min 1/2m Σ((θ^j)^T xⁱ  - y ^i,j)²  + λ/2m(Σ θ^j)²

θ^j                  i:r=1

The recommender algorithm in essence tries to learn parameters θ^j for a set of features of xⁱ the chosen system for e.g.  books in this case.

The recommender tries to learn the parameters for all the users

min 1/2m Σ Σ((θ^j)^T xⁱ  - y ^i,j)²  + λ/2m(Σ Σ θ^j)²

θ¹...θⁿ                i:r=1

The minimization is performed by gradient descent as

Θ^j _k:= Θ^j_k – α (Σ((θ^j)^T xⁱ  - y ^i,j)xⁱ + λ Θ^j _k

Recommender systems tries to learn the parameters for a set of chosen features over all users. Based on the learnt paramaters it then tries to predict the rating the user would give to books/apps that he is yet to purchase and push up those apps for which the user is likely to give a high rating based on the given set of ratings.

Recommender systems contribute substantially to the revenues of e-commerce sites like Amazon, Flipkart, Netflix etc

Note: This post, line previous posts on Machine Learning,  is based on the Coursera course on Machine Learning by Professor Andrew Ng
[polldaddy rating="7295683"]
Find me on Google+

Perils and pitfalls of Big Data

Big Data is hurtling towards us in a big way. It is already in the news and the blip seems to getting bigger. Big Data will soon become the key driver for almost any kind of decision that is to be made in manufacturing, retail, finance all the way to astronomy, oceanography etc. The common aspect of all industries and areas is that data is generated in the order of several petabytes to exabytes. Big Data is the technique to analyze such large volumes of data.

Big Data represents the technique to handle the huge deluge of data that is already becoming enmeshed in our lives. Multiple disparate, varied streams of data (text. tweets, click streams, html) flow through with tremendous volume & velocity. The key aspects of data in the world are the volume, variety and the velocity. It is never ending and never seems to stop. How do we handle this deluge? How do we make sense of this data is what Big Data is all about.

Big Data provides algorithms to find patterns, determine trends or classify data depending on the features provided. It is supposed to enable the decision makes to make key decisions based on the answers the algorithms spew forth.

Big Data is also complicated by the fact that data comes is multiple forms from click streams, tweets, html, texts, CSVs, structured and non –structured data.

The ability to detect patterns, determine trends, classify, identify outliers is no easy task

In this post I try to take a philosophical look at Big Data and ask whether it can really help us. Will it help or will take is on wild goose chase? Can we trust the results?

Big Data depends on algorithms to make sense of data. Big Data deals with data that is in the order of Petabytes to Exabytes. At this scale with multiple features our cognitive abilities are of no use. We must rely on machines and algorithms to make sense of these large amounts of data. Our mind can handle a few hundred data points and at most 3 dimensions. Beyond that the data  can hardly make any sense.

Data by itself, in the absence of features & algorithms, is indistinguishable from noise. It is data science that makes sense of data. Data science separates the signal from the noise.

It is the algorithms that try to determine the best fit for a given set of data. But how reliable are the results. For example let us take the following case

An unsupervised learning algorithm for the above data points could try to separate the data into 2 sets. Clearly this is one way but what is more appropriate is that we have 2 shapes, the circle & the rectangle. A machine algorithm would try to work based on the features that we choose. Are we in a position to decide whether the answer the algorithm gives us is correct? We have no way of knowing because the amount of data is beyond our cognitive capabilities,

In other words, Big Data is full of perils and pitfalls.

When we let the machine to analyze on our behalf the possibility of coming to a wrong conclusion is fairly high.  This coupled with the fact that we are sometimes led to erroneous judgments, as discussed below, the problem is further compounded.

In his book “Thinking fast, thinking slow” Daniel Kahneman discusses several situations where our mind falls into the traps of lazy thinking. We come to wrong conclusions. Also our minds tend to detect patterns in data where there are none. Sometimes according to Kahneman ‘randomness appears as regularity or a tendency to cluster’. Also he says ‘the tendency to see patterns in randomness is overwhelming’. We could argue that in Big Data it is the algorithm that is determining the pattern we could be tricked into coming to false conclusions. Sometimes the human mind sees causality where there is none. Occasionally we fail to see the obvious.

In the ‘famous gorilla experiment’ the researchers tried to assess selective attention. The participants are asked to count the number of passes those in white t-shirts make. Surprisingly a large number of the participants were complete oblivious a gorilla that appears midway in the video. When we, as human fail to see such large objects, can we expect the machine to accurately identify patterns and perform accurate classifications?

There are techniques that help in determining false positives for e.g. the Bonferroni correction. Simply put the Bonferroni correction tries to determine the possibility of getting at least 1 significant result when one is testing 20 hypothesis simultaneously. If we want to test 20 hypotheses with the significance of 0.05 then the probability of at least 1 significant result is

P(at least one significant result) = 1 - P(no significant results)

= 1 - (1 - 0:05)^20

= 0.64

So, with 20 tests being considered, we have a 64% chance of observing at least one significant result, even if all of the tests are actually not significant. This would be a false positive.

Given that our ability to come to significant conclusions depends largely on being able to choose appropriate features, we must also be able to maneuver between false negatives and false positives. In addition we must also take into account the fallibility of the human mind.

Clearly, Big Data is the future! However with Big Data we are really on treacherous, slippery ground!

Simplifying ML: Recommender Systems - Part 7

In this age of Amazon, Netflix and App stores where products, movies and apps are purchased online the method of up-selling and cross-selling online is through the use of recommender based systems.

When you go to site like Amazon/Flipkart or purchase apps on App store/Google Play we often see things like “People who bought this book/app also bought X, Y, Z”. These recommendations are the recommender system algorithms in action.

Recently, Netflix ran a competition in which users had to come with the best algorithm to recommend films that a user would also like. The prize money for this was of the order of $1 million. That’s how critical recommender systems are to organizations of today where most of the transactions happen on the web.

Typically users are asked to give a rating of 1 to 5 with 1 being the lowest and 5 being the highest.  So for example if we had classics like Moby Dick, Great Expectations and current best sellers like The Client, The da Vinci Code and a Science Fiction like 2001- A Space Odyssey we can expect that different people will rate the books differently. Obviously not everybody would have read every book in the list and some elements would be blank.



Recommender Systems are based on machine learning algorithms. The goal of these algorithms is to predict what score any user would give to books they did not rate. In other words what would be rating the buyers would give for books or apps they did not buy. So if the algorithm predicts a high rating then we could recommend that the user would also ‘like’ them. Or we could give recommendations of books/apps bought by users who bought the books/apps bought by this user.

The notation is

n_u = Number of users

n_b = Number of books

r^(i,j) = Boolean whether user j rated a book i

y^(i,j) = The rating user j gave book i

m_j = The number of books that user j rated

Content based recommendation

In a typical content based recommendation algorithm we assume that we have data about some items we want to recommend rating for e.g. books/products/apps.  In the example for books bought in an online bookstore we assume some features in our case ‘classic’, “fiction” etc



So each book has its own feature vector where x¹ is the feature vector of the first book x² feature vector of the 2nd book and so on

This can be done through linear regression by minimizing the cost function of the sum of squared errors from the predicted value

So for a parameter vector Ɵ^jand a feature vector xⁱ the recommender system will try to predict the rating that a user j will give a book i.

This can be written as

Number of stars (rating) = (θ^j) ^T xⁱ



This reduces to the minimization problem over all θ^j for r=1

min 1/2m Σ  ((θj)^T xⁱ  - y ^i,j)²

θ^j                 i:r=1

Adding the regularization term this becomes

min 1/2m Σ((θ^j)^T xⁱ  - y ^i,j)² + λ/2m(Σ θ^j)²

θ^j                 i:r=1

The recommender algorithm in essence tries to learn parameters θ^j for a set of features of xⁱ the chosen system for e.g.  books in this case.

The recommender tries to learn the parameters for all the users

min 1/2m Σ Σ((θ^j)^T xⁱ - y ^i,j)² + λ/2m(Σ Σ θ^j)²

θ¹...θⁿ               i:r=1

The minimization is performed by gradient descent as

Θ^j _k:= Θ^j_k – α (Σ((θ^j)^T xⁱ - y ^i,j)xⁱ + λ Θ^j _k



Recommender systems tries to learn the parameters for a set of chosen features over all users. Based on the learnt paramaters it then tries to predict the rating the user would give to books/apps that he is yet to purchase and push up those apps for which the user is likely to give a high rating based on the given set of ratings.

Recommender systems contribute substantially to the revenues of e-commerce sites like Amazon, Flipkart, Netflix etc

Note: This post, line previous posts on Machine Learning,  is based on the Coursera course on Machine Learning by Professor Andrew Ng

Perils and pitfalls of Big Data

Big Data is hurtling towards us in a big way. It is already in the news and the blip seems to getting bigger. Big Data will soon become the key driver for almost any kind of decision that is to be made in manufacturing, retail, finance all the way to astronomy, oceanography etc. The common aspect of all industries and areas is that data is generated in the order of several petabytes to exabytes. Big Data is the technique to analyze such large volumes of data.


Big Data represents the technique to handle the huge deluge of data that is already becoming enmeshed in our lives. Multiple disparate, varied streams of data (text. tweets, click streams, html) flow through with tremendous volume & velocity. The key aspects of data in the world are the volume, variety and the velocity. It is never ending and never seems to stop. How do we handle this deluge? How do we make sense of this data is what Big Data is all about.


Big Data provides algorithms to find patterns, determine trends or classify data depending on the features provided. It is supposed to enable the decision makes to make key decisions based on the answers the algorithms spew forth.



Big Data is also complicated by the fact that data comes is multiple forms from click streams, tweets, html, texts, CSVs, structured and non –structured data.



The ability to detect patterns, determine trends, classify, identify outliers is no easy task



In this post I try to take a philosophical look at Big Data and ask whether it can really help us. Will it help or will take is on wild goose chase? Can we trust the results?


Big Data depends on algorithms to make sense of data. Big Data deals with data that is in the order of Petabytes to Exabytes. At this scale with multiple features our cognitive abilities are of no use. We must rely on machines and algorithms to make sense of these large amounts of data. Our mind can handle a few hundred data points and at most 3 dimensions. Beyond that the data  can hardly make any sense.



Data by itself, in the absence of features & algorithms, is indistinguishable from noise. It is data science that makes sense of data. Data science separates the signal from the noise.



It is the algorithms that try to determine the best fit for a given set of data. But how reliable are the results. For example let us take the following case



An unsupervised learning algorithm for the above data points could try to separate the data into 2 sets. Clearly this is one way but what is more appropriate is that we have 2 shapes, the circle & the rectangle. A machine algorithm would try to work based on the features that we choose. Are we in a position to decide whether the answer the algorithm gives us is correct? We have no way of knowing because the amount of data is beyond our cognitive capabilities,


In other words, Big Data is full of perils and pitfalls.



When we let the machine to analyze on our behalf the possibility of coming to a wrong conclusion is fairly high.  This coupled with the fact that we are sometimes led to erroneous judgments, as discussed below, the problem is further compounded.



In his book “Thinking fast, thinking slow” Daniel Kahneman discusses several situations where our mind falls into the traps of lazy thinking. We come to wrong conclusions. Also our minds tend to detect patterns in data where there are none. Sometimes according to Kahneman ‘randomness appears as regularity or a tendency to cluster’. Also he says ‘the tendency to see patterns in randomness is overwhelming’. We could argue that in Big Data it is the algorithm that is determining the pattern we could be tricked into coming to false conclusions. Sometimes the human mind sees causality where there is none. Occasionally we fail to see the obvious.



In the ‘famous gorilla experiment’ the researchers tried to assess selective attention. The participants are asked to count the number of passes those in white t-shirts make. Surprisingly a large number of the participants were complete oblivious a gorilla that appears midway in the video. When we, as human fail to see such large objects, can we expect the machine to accurately identify patterns and perform accurate classifications?



There are techniques that help in determining false positives for e.g. the Bonferroni correction. Simply put the Bonferroni correction tries to determine the possibility of getting at least 1 significant result when one is testing 20 hypothesis simultaneously. If we want to test 20 hypotheses with the significance of 0.05 then the probability of at least 1 significant result is



P(at least one significant result) = 1 - P(no significant results)

= 1 - (1 - 0:05)^20

= 0.64


So, with 20 tests being considered, we have a 64% chance of observing at least one significant result, even if all of the tests are actually not significant. This would be a false positive.


Given that our ability to come to significant conclusions depends largely on being able to choose appropriate features, we must also be able to maneuver between false negatives and false positives. In addition we must also take into account the fallibility of the human mind.



Clearly, Big Data is the future! However with Big Data we are really on treacherous, slippery ground!

Reducing to the Map-Reduce paradigm- Thinking Web Scale – Part 1

In physics there are 4 types of forces – gravitational forces among celestial bodies, electro-magnetic forces and strong and weak forces at the sub-atomic level. The equations that seem to work among large bodies don’t seem to apply at the sub-atomic level though there have been several attempts at grand unification theories

Similarly in computing we have: – computing at personal level, enterprise level, data-center level and a web scale level. The problems and paradigms at each level are very different and unique. The sequential processing, relational database accesses or network speeds at the local area network level are very different to the parallel processing requirements, NoSQL based storage accesses  and WAN latencies.

Here is the first of my posts on paradigms at the Web Scale.

The internet now contains in excess of 1 billion hosts.  This is based on a report in the World Fact Book published in 2012.

In these 1 billion and odd hosts there are at least ~1.5 billion pages that have been indexed. There must be several hundred million that are not indexed by the major search engines.

Search engines like Google, Bing or Yahoo have to work on several hundred million pages.  Similarly social web sites like Facebook, Twitter or LinkedIn have to deal with several hundred million users who constantly perform status updates, upload images, tweet etc. To handle large quantities of data efficiently and quickly there is a need for web scale algorithms.

One such algorithm is the map-reduce, that had its origins in Google. The map reduce essentially consists of a set of mappers which take as input a key-value pair and outputs 0 or more key value pairs. The reducer takes all tuples with the same key and combines them based on some function and emits a key value pair



Map-reduce, and its open source avatar, Hadoop, are now used routinely to solve several large scale problems. To be honest, I was and still am, puzzled whether the 2 simple tasks types of mapping & reducing can be used for a large variety of problems. However, it appears so.

I would have assumed that there would have been other flavors, maybe an ‘identify-update’, ‘determine-solve’ or some such equivalent, unless a large set of problems can be expressed as some combination of the map reduce paradigm.

Anyway here a few examples for which the map reduce algorithm is useful.


Word Counting: The standard example for map-reduce is the word counting program. In this the map reduce algorithm generates a list of words with their corresponding word count from a set of input files. The Map task reads each document and breaks it into a sequence of words (w1, w2, w3 …). It then emits a key value pair as follows

(w1,1),(w2,1),(w3,1),(w1,1) and so on. If a word is repeated in the document it occurs multiple times in the output.  Now the entire key, value pairs are grouped by keys and sent to one of the reducer tasks. Each reducer will then sum all the values thus giving the total for each word.



Matrix multiplication: Big Data is a typical challenge in the web where there is a need to determine patterns and trends in mountains of data. Machine learning algorithms are utilized to determine structure in data that has 3 characteristics of volume, variety and velocity. Machine learning algorithms typically depend on matrix operations. Map-reduce is ideally suited for this and one of the original purposes of Google for map-reduce was with matrix multiplication.

Let us assume that we have a n x n matrix M whose element in row i and column j is m_ij

Also let us assume that there is a vector ‘v’ whose jth element is v_j . Then the matrix vector product can be is the vector x of the length n whose ith element is given as

x_i = ∑ m_ijv_j



Map function: The map function applies to each single element of the matrix M. For each element m_ij the map task outputs a key-value pair as follows (i, m_ijv_j).  Hence we will have a key-value pairs for all ‘i’ from 1 to n.

Reduce function:  The reduce function takes all pairs with the same key ‘i’ and sum it up.

Hence each reducer will generate

x_i = ∑ m_ijv_j

(Reference: Mining of Massive Datasets- Anand Rajaraman, Jure Leskovec, Jeffrey D Ullman)

This link gives a good write-up on a matrix x matrix multiplication,

Map-reduce for Relational Operations: Map-reduce can be used to perform a number of operations on large scale data that are used in database operations. Multiple database operations can be performed on large scale data like selection, projection, union, intersection, difference, natural join, grouping etc.

Here is a an example taken from ‘Web Intelligence & Big Data’ course from Coursera any Gautam Shroff.

Let us assume that there are 2 tables ‘Sales by address’ and “City by address’ and the need is to find the total ‘Sales by City’. The SQL query for this

SELECT SUM(Sale),City FROM Sales, City WHERE Sales.Addr_id = Cities.Addr_id GROUP BY City

This can be done by 2 map-reduce tasks.

The first map-reduce task GROUPs BY Sales as follows

Map1: The first map task will emit (Address, rest of record (SALE/City))

Reduce1: The first reduce task will SUM (Sales) by Address for every City. Clearly this will have multiple occurrences of City.


At this point we will have the sum of the sales for every city. However each city can occur multiple times. Now we have to GROUP BY City

Map2: Now the mapper emits the (City, rest of record (SALES)

Reduce2: The 2^nd reduce now SUMS all the sales for each city.


Clearly the map-reduce algorithm does solve some major areas. It is extremely useful when there is a need to perform the same operation on multiple documents. It would definitely be useful in building the inverted index or in Page rank. Also, map-reduce is very powerful in handling matrix operations. Large class of problems like machine learning, computer vision all use matrices extensively and map-reduce is extremely critical when it has done in large volumes of data.  Besides, the ability of map-reduce to perform a large set of database operations is something that can be used in many situations in the web.

However it is no silver bullet for all types of problems.
[polldaddy rating="7295683"]

Find me on Google+

Simplifying Machine Learning – K- Means clusters - Part 6

Our brain is an extraordinary apparatus. It is amazing how we humans can instantaneously perceive shapes, objects, forms. For e.g. when see a scene with many objects we are immediately able to identify the different objects in the scene.  View this against the backdrop of a recent Google’s artificial brain experiment of a neural network with 16000 processors and a billion connections. This artificial brain was fed with 10 million thumbnails of you tube videos before it was able to recognize cat videos.

That’s an awful lot of work to recognize cat videos!

We can see that a lot of work involved getting a computer to do something as simple thing as this.

Consider how a baby learns to recognize objects for e.g. cat, dog, toy etc. The human brain does not try to measure the number of eyes, spacing between the eyes, the mouth shape of face etc. The brain immediately is able to distinguish the different animals. How does it do it? Amazing right?

In any case here is a machine learning algorithm that is capable of identifying structure in data. This is also known as K-Means and is a form of unsupervised learning algorithm.

The K-Means algorithm takes as input an unlabeled data set and identifies groups in the set. It tries to determine structure in the data set.

Take a look at the picture below



It is readily obvious that there are 2 clusters in the above diagram. However to the computer this is just a random set of points.

How does the K-Means cluster identify the clusters in the above diagram?

The algorithm is fairly simply and intuitive.

1)    Let us start by choosing 2 random points which we call as ‘cluster centroids

2)    We then associate each centroid with the points in the dataset that are closest to it.

3)    We then compute the average of each group of associated points in the centroid and move the centroid to that average.

4)    We then repeat steps 2 – 4 until there is no significant change in the centroid

This is shown below



The above algorithm can be implemented iteratively as follows

For training set (x¹, x², x³ …)

Randomly initialize K cluster centroids μ₁, μ₂, μ₃ … μ_K



Repeat {

for 1 to m

c(i) = The cluster index from 1 to K that is closest to xⁱ => (A)

end

for k = 1 to K

u(k) = average of all points assigned to K   => (B)

end

}

In step (A) the points xⁱ closest to the centroid k is added to the centroid’s set. Hence if points 1,3,4,8 are in centroid 1 then

x¹ = 1, x³ = 1, x⁴ = 1, x⁸ =1

In step (B) the mean of the points 1, 3, 4, 8 is taken

So the centroid

c_1x = ¼ { x₁ + x₃ + x₄ + x₈} and c_1y = ¼ { y₁ + y₃ + y₄ + y₈}

This becomes the new c₁



However there can be occasions where the K-means cluster would get stuck in local optima. To choose optimum cluster centroid we have to determine the least cost. This can be done with the optimization objective.

The optimization objective of K-Means is as follows

K-Mean cluster determination is the problem of minimizing the distance of each point from its centroid. This is also known as the K-Means cost function or distortion function.

J(c¹,c²…c^m,, μ₁,… μ₂) = 1/m Σ|| xⁱ – μ_c(i) ||²

I like to visualize the algorithm as follows.

In step 1 we can visualize that there is a force of attraction between the datapoints and the cluster centroid based on proximity of the centroid.

In step 2 we can visualize that each datapoint attracts the centroid towards it. The centroid moves to the point where the attraction among all the datapoints balances out. This is average mean squared difference.

As can be seen the objective is to determine the average of the mean squared error of each data point to its closest centroid.

Given a set of data points how we choose the random centroids? One way is to initially pick some random data points themselves as the cluster centroid. The algorithm is then iterated to identify the real cluster centroids.

As mentioned before the algorithm can sometimes get stuck in local optima.  One option is to choose another random set of data points and continue to iterate. We need to run this several times to determine the best clustering

There is also the problem of determining the number of cluster centroids. How we to determine how many clusters are would be there in a random data set? Visually we can easily identify the number of clusters. But a machine cannot.

One technique that can be used to determine the number of clusters is as follows. Start with 2, 3… 10 clusters and plot the cost function. Then pick the one with the least cost.

Note: This post, line previous posts on Machine Learning,  is based on the Coursera course on Machine Learning by Professor Andrew Ng
[polldaddy rating="7295683"]
Find me on Google+

The thing about the Internet of Things

Introduction: It is now common knowledge that the world is becoming more connected, instrumented and data driven. In a world of 7 billion people we have almost 10 billion devices connected to the internet. A recent report from Cisco suggests that the number of connected devices will almost touch 50 billion by the year 2020.

This huge increase in the number connected devices will come largely from a couple of new technology trends namely Internet of Things (IoT), Smart grids etc.

What exactly is the Internet of Things?

The first formal definition of the Internet of Things happened when ITU-T the telecom wing of United Nations came with a report titled “The Internet of Things” in 2005. In this report ITU-T added a fourth dimension of ‘anything’ to the existing anyone, anywhere, anytime network. This report visualized a world where millions and millions of devices either passive, intelligent or sensors collected data from the environment and sent it through the network to a backend processing system.

In Mark Weiser’s classic words, “the most profound technologies are those that disappear and weave themselves into the fabric of everyday life until they are indistinguishable from it”. Embedded intelligence in the things themselves will further enhance the power of the network. IoT is just this vision of Mark Weiser.

This fourth dimension of ‘things’ or intelligent sensors give the ability to gather data from the environment which is then sent back through the wireless network to the internet for back end processing. Analysis of the gathered data helps in forecasting events ahead of the time.

The Internet of Things is also known as M2M or machine–to–machine computing, pervasive computing or ubiquitous computing.

The Maha Kumbh Mela experiment: Last year, 2013, coincided with the 12 year cycle of the Maha Kumbh mela festival. More than 100+ million people would have passed through the city of Allahabad for a holy dip in river Sangam at the confluence of Ganges & Yamuna. Almost 95% of this human mass would have carried mobile phones equipped with location sensors.  Harvard Business University with the help of mobile Telecom Operators ran an experiment to track the movement of people through the city of Allahabad to understand the behavior of people. It was  hoped that the study of this large amount of data, as people moved through the city, would help in identifying signatures of disaster and how they can be avoided.

This is possible because mobile phones have the ability to send their location data back to the net for processing. This is an example of the Internet of Things.

Some applications of the Internet of Things is outlined below

RFID or Radio Frequency Identification: RFID was one of the early enablers of this technology; The RFID is a passive device that responds with its identity when it is in the presence of a RFID receiver. The RFID receiver transmits a signal and a RFID tag responds with its unique tag id. The RFID technology has been used extensively by large retail stores like Walmart of US and Tesco of UK etc. These stores RFID tag all their products in the central warehouse. In the presence of an RFID receiver the RFID tags of all the products are read. So the warehouse has a complete list of its inventory. As the products move from the central warehouse to the regional warehouse and finally to the retail store the products are tracked. So the retail stores know exactly how many of each product is present in all its warehouses and stores. As customers buy products and check it out at the counter the count of the products in the store is also updated. So at any point in time each store will know the count of each of its products. So stores like Walmart can now forecast if there is a going o be a shortage of any of it products and can move some of them to the concerned store. In fact we can imagine a scenario where each shopping cart is equipped with a RFID receiver. As we keep putting products into our cart the cart can add each of the items we have taken so that we have the bill ready when we reach the counter. We need not scan the products at the check out counter.

Highway Tolls: An interesting application of IoT, is the payment of highway tools in which the vehicle do not need to stop to pay the toll. Toll is deducted from a device, with a driver, which is RFID tagged. There are also applications in which the tires of cars are embedded with sensors to detect the wear & tear of the tires. Insurance companies can use the driving data from these sensors to give discounts to safe drivers.

Car-to-car networks: Another certainty in the evolution of IoT is car-to-car networks. Vehicular Communication along with the Intelligent Transport Systems (ITS) achieves safety by enabling communication between vehicles, people and roads. Vehicle-to-vehicle communications are the fundamental building block of autonomous, self-driving cars. It enables the exchange of data between vehicles and allows automobiles to “see” and adapt to driving obstacles more completely, preventing accidents besides resulting in more efficient driving.

Intelligent homes:  Rapid advances in technology will be closer to the home both literally and figuratively. The future home will have the ability to detect the presence of people, pets, smoke and changes to humidity, moisture, lighting, temperature. Smart devices will monitor the environment and take appropriate steps to save energy, improve safety and enhance security of homes.  Devices will start learning your habits and enhance your comfort and convenience. Everything from thermostats, fire detectors, washing machines, refrigerators will be equipped electronics that will be capable of adapting to the environment. ‘Nest’ is a smart thermostat that made headlines recently. The thermostat learns your requirements and adjusts the temperature accordingly. All gadgets in the Smart Home will be accessible through laptops, tablets or smartphones from anywhere. Others gadgets in Intelligent Homes are smart locks, smart lighting etc. Hence, we will be able to monitor all aspects of our intelligent home from anywhere.

Intelligent offices: Smart devices will also make major inroads into offices leading to the birth of intelligent offices where the lighting, heating, cooling will be based on the presence of people in the offices. This will result in an enormous savings in energy. The advances in intelligent homes and intelligent offices will be in the greater context of the Smart Grid.

eHealth: IoT is being used by some hospitals for monitoring of heart patients Here a device is  implanted into the patient. The device regularly sends data to a doctor who can monitor the patient’s pulse rate, heart rate, blood pressure etc.  It can warn the physician when it detects an irregularity in the patient’s heart rhythm who can then call the patient and advice on appropriate medication to take avoiding a real cardiac arrest.

Smart Cities: How often we sit fretting and fuming in a traffic jam contributing to air pollution. Smart Cities are equipped with multiple devices that identify and measure traffic speed and volume on city roads. At the back end the systems analyze this continuous stream of real time and provide alternative routes based on predictive analytics based on real time and historical data. Studies have also shown that it is possible to control traffic by offering discounts to drivers on less crowded roads.

Smart Grid: The grid or the legacy electrical network has three components to it namely energy generation, energy transmission and energy distribution. The conventional electrical grid which is prevalent in most countries throughout the world has extremely high transmission losses besides having other issues. Typically an outage in one part of the network would cause a cascading effect throughout the network. Remember the infamous blackout in US in 2003 which was the largest black in US in history. More closer to home, in India, we had a blackout in Dec 2012 which was the largest black out ever. This is because of the domino effect where an issue causes a cascading effect. Closer to home we had the world’s biggest blackout in Jul 31 which left 600 million powerless for close to 2 days.

With the advent of Smart Grid the legacy electrical grid will have millions of electrical sensors which monitor the flow of energy. If there is a fault in any part of the network the sensors ensure that the failure is isolated so that outage does not spread to other parts.

Besides instead of the regular electrical meters Smart Grids include the concept of the Smart home equipped with smart meters. These smart meters have a two way communication. The price of energy which we get from the grid varies like the stock price. With the smart meters and smart appliances these appliances turn on when the price of drawing energy is low.

Wearable Technologies: he latest entrants to IoT are the wearable technology like Smart watches, Google Glass, Health bands. These technologies constantly monitor measure and send the data for processing to the backend.  For e.g. Google’s glass can immediately recognize prominent landmarks and display it. Similarly health bands like Fitbit, Nike FuelBand etc can now measure steps, heart rate and provide feedback.

Challenges: There are still many challenges on the way to a future filled with M2M. There is still no universally accepted protocol. There are many competing protocols like WiFi, Zigbee, MQPP, XMPP etc and there is yet to be a single common standard between devices and the networks for the Internet Of Things.

In any case, the Internet of Things or M2M is happening technology and will soon come into our neighborhood and we should all be pretty swamped by this tidal wave in our future

[polldaddy rating="7295683"]

Find me on Google+

Simplifying ML: Impact of degree of polynomial degree on bias, variance and other insights

This post takes off from my earlier post Simplifying Machine Learning: Bias, variance, regularization and odd facts- Part 4. As discussed earlier a poor hypothesis function could either underfit or overfit the data.  If the number of features selected were small of the order of 1 or 2 features, then we could plot the data and try to determine how the hypothesis function fits the data. We could also see whether the function is capable of predicting output target values for new data.

However if the number of features were large for e.g. of the order of 10’s of features then there needs to be method by which one can determine if the learned hypotheses is a ‘just right’ fit for all the data.

The following technique can be used to determine the ‘goodness’ of a hypothesis or how well the hypothesis can fit the data and can also generalize to new examples not in the training set.

Several insights on how to evaluate a hypothesis is  given below

Consider a hypothesis function

h_Ɵ (x) = Ɵ₀ + Ɵ₁x₁ + Ɵ₂x₂² + Ɵ₃x₃³  +  Ɵ₄x₄⁴

The above hypothesis does not generalize well enough for new examples in the data set.

Let us assume that there 100 training examples or data sets. Instead of using the entire set of 100 examples to learn the hypothesis function, the data set is divided into training set and test set in a 70%:30% ratio respectively

The hypothesis is learned from the training set. The learned hypothesis is then checked against the 30% test set data to determine whether the hypothesis is able to generalize on the test set also.

This is done by determining the error when the hypothesis is used against the test set.

For linear regression the error is computed by determining the average mean square error of the output value against the actual value as follows

The test set error is computed as follows

J_test(Ɵ) = 1/2m_test Σ(hƟ (x_testⁱ  - y_testⁱ)²

For logistic regression the test set error is similarly determined as

J_test(Ɵ) = = 1/m_test Σ -y_test * log(h_Ɵ (x_test))  - (1-y_test) * (log(1 - h_Ɵ (x_test))

The idea is that the test set error should as low as possible.

Model selection

A typical problem in determining the hypothesis is to choose the degree of the polynomial or to choose an appropriate model for the hypothesis

The method that can be followed is to choose 10 polynomial models

1. h_Ɵ (x) = Ɵ₀ + Ɵ₁x₁
2. h_Ɵ (x) = Ɵ₀ + Ɵ₁x₁ + Ɵ₂x₂²
3. h_Ɵ (x) = Ɵ₀ + Ɵ₁x₁² + Ɵ₂x₂² + Ɵ₃x₃³
4. …

Here‘d’ is the degree of the polynomial. One method is to train all the 10 models. Run each of the model’s hypotheses against the test set and then choose the model with the smallest error cost.

While this appears to a good technique to choose the best fit hypothesis, in reality it is not so. The reason is that the hypothesis chosen is based on the best fit and the least error for the test data. However this does not generalize well for examples not in the training or test set.

So the correct method is to divide the data into 3 sets  as 60:20:20 where 60% is the training set, 20% is used as a test set to determine the best fit and the remaining 20% is the cross-validation set.

The steps carried out against the data is

1. Train all 10 models against the training set (60%)
2. Compute the cost value J against the cross-validation set (20%)
3. Determine the lowest cost model
4. Use this model against the test set and determine the generalization error.

Degree of the polynomial versus bias and variance

How does the degree of the polynomial affect the bias and variance of a hypothesis?

Clearly for a given training set when the degree is low the hypothesis will underfit the data and there will be a high bias error. However when the degree of the polynomial is high then the fit will get better and better on the training set (Note: This does not imply a good generalization)

We run all the models with different polynomial degrees on the cross validation set. What we will observe is that when the degree of the polynomial is low then the error will be high. This error will decrease as the degree of the polynomial increases as we will tend to get a better fit. However the error will again increase as higher degree polynomials that overfit the training set will be a poor fit for the cross validation set.

This is shown below

Effect of regularization on bias & variance

Here is the technique to choose the optimum value for the regularization parameter λ

When λ is small then Ɵ_i values are large and we tend to overfit the data set. Hence the training error will be low but the cross validation error will be high. However when λ is large then the values of Ɵ_i become negligible almost leading to a polynomial degree of 1. These will underfit the data and result in a high training error and a cross validation error. Hence the chosen value of λ should be such that the cross validation error is the lowest

Plotting learning curves

This is another technique to identify if the learned hypothesis has a high bias or a high variance based on the number of training examples

A high bias indicates an underfit. When the number of samples in training set if low then the training error and cross validation error will be low as it will be easy to create a hypothesis if there are few training examples. As the number of samples increase the error will increase for the training set and will slightly decrease for the cross validation set. However for a high bias, or underfit, after a certain point increasing the number of samples will not change the error. This is the case of a high bias

In the case of high variance where a high degree polynomial is used for the hypothesis the training error will be low for smaller number of training examples. As the number of training examples increase the error will increase slowly. The cross validation error will be high for lesser number of training samples but will slowly decrease as the number of samples grow as the hypothesis will learn better. Hence for the case of high variance increasing the number of samples in the training set size will decrease the gap between the cross validation and the training error as shown below

Note: This post, line previous posts on Machine Learning,  is based on the Coursera course on Machine Learning by Professor Andrew Ng

Simplifying Machine Learning: Bias, Variance, regularization and odd facts – Part 4

In both linear and logistic regression the choice of the degree of the polynomial for the hypothesis function is extremely critical. A low degree for the polynomial can result in an underfit, while a very high degree can overfit the data as shown below

The figure on the left the data is underfit as we try to fit the data with a first order polynomial which is a straight line. This is a case of strong ‘bias’

The rightmost figure a much higher polynomial is used. All the data points are covered by the polynomial curve however it is not effective in predicting other values. This is a case of overfitting or a high variance.

The middle figure is just right as it intuitively fits the data points the best possible way.

A similar problem exists with logistic regression as shown below

There are 2 ways to handle overfitting

a)      Reducing the number of features selected

b)      Using regularization

In regularization the magnitude of the parameters Ɵ is decreased to reduce the effect of overfitting

Hence if we choose a hypothesis function

h_Ɵ (x) = Ɵ₀ + Ɵ₁x₁² + Ɵ₂x₂² + Ɵ₃x₃³ +  Ɵ₄x₄⁴

The cost function for this without regularization as mentioned in earlier posts

J(Ɵ) = 1/2m Σ(h_Ɵ (xⁱ  - yⁱ)²

Where the key is minimize the above function for the least error

The cost function with regularization becomes

J(Ɵ) = 1/2m Σ(h_Ɵ (xⁱ  - yⁱ)^{2 +} λ Σ Ɵ_j²

As can be seen the regularization now adds a factor Ɵ_j²  as a part of the cost function which needs to be minimized.

Hence with the regularization factor the problem of underfitting/overfitting can be solved

However the trick is determine the value of λ. If λ is too big then it would result in underfitting or resulting in a high bias.

Similarly the regularized equation for logistic regression is as shown below

J(Ɵ) = |1/m Σ  -y * log(h_Ɵ (x))  - (1-y) * (log(1 - h_Ɵ (x))  | + λ/2m Σ Ɵ_j²

Some tips suggested by Prof Andrew Ng while determining the parameters and features for regression

a)      Get as many training examples. It is worth spending more effort in getting as much examples

b)      Add additional features

c)      Observe changes to the learning algorithm with different values of λ

This post is continued in my next post - Simplifying ML: Impact of degree of polynomial on bias, variance and other insights

Note: This post, in line with my previous posts on Machine Learning,  is based on the Coursera course on Machine Learning by Professor Andrew Ng

A method to crowd source pothole marking on (Indian) roads

In, India, roads and potholes are 2 sides of the same coin! You cannot think of one in exclusion of another. This post of mine looks at a novel technique of rapidly identifying & marking potholes in (Indian) roads. This approach can be used for any city in the world but is very pertinent to Indian roads.

This idea of mine provides a technique of quickly marking pothole in roads through the method of crowd sourcing

Introduction: It is a well known fact that Indian roads are riddled with potholes. Some may even say that there are potholes with patches of road in between them. This disclosure looks at a novel technique of rapidly identifying & marking potholes in (Indian) roads. The approach can be used for any city in the world. However this disclosure will focus on Indian roads. This disclosure proposes a novel technique of crowd-sourcing the marking of potholes on roads rather than having any single government body (NHAI etc) travel on roads to make the markings.

Description: This post proposes a novel crowd-sourced method for pothole marking that will be easy to conduct and extremely rapid The crowd-sourced pothole marking application will be made of the following components namely Pot-hole marking app, Backend server, Map Matching utility, Pothole ranking utility.

Pothole marking App: A location based smartphone app will need to be created preferably both on Android and iOS. The app will display the map with buttons to mark the following

a)   Points in map of potholes

b)   Bad segments of roads with potholes

Backend Server: The backend server will collect all the data (marked potholes) and bad segments of roads and will update a database.  A map-matching utility will map the latitude, longitude of the marked point on to a map. When the geographical location of a pothole is received (latitude, longitude) the backend server will also store the time stamp.

Pothole ranker: This module will run on a periodical basis, say once every 3 minutes. This module will determine all the potholes that have been entered in the last 3 minutes and add to the accumulated count of marked potholes. Each marked pothole will hold the count of the marks and also the time stamp of the mark. It will also rank the criticality of the pothole based on the accumulated count of potholes over the period.

The pothole ranker will maintain the following metrics

1. Pothole criticality = Total accumulated count/ Total time
2. Pothole impact measure = Max rate of pothole marks (Pothole marks/hr)
3. Bad stretches of roads with many potholes =

Number of adjacent potholes/ Distance in meters

Description: This how the scheme will work in practice. The app will be uploaded into Google Play and Apple’s App store.  All users who would like to participate in the pothole marking exercise can download and install the app on their smart phones. These users when they are traveling on a road can mark potholes as they encounter them. It is assumed that the users are passengers in vehicles or pillion riders. The fact that users all over the city can simultaneously mark potholes as they encounter them will make the gathering of pothole data rapid and extremely accurate. A map of a city would need to be generated with the circles/points for locations of potholes, color-coded appropriately. We could use the color red for higher ranked potholes and yellow for lower ranked potholes with intermediate colors like purple, pink etc.  This data can then be used by Government bodies in addressing roads in fixing the roads.

There are three advantages of crowd sourcing the pothole marking

1)   The process of gathering data is rapid

2)   Roads where the traffic is heaviest will have potholes with a higher rank and can be addressed first

3)   The process will be very accurate

Crowd sourcing of pothole marking will have the following benefits

1. The marking of potholes will be extremely rapid
2. The potholes will be ranked based on accumulated count
3. Ranking of potholes can be done on

- Total accumulated count/Total time

- Rate of pothole mark

- Critical segments with major potholes

4. It will be easy to segregate

- Critical potholes
- Max impactful potholes
- Bad road segment

5. The process will be very accurate

Conclusion: The process of crowd sourcing pothole marking of Indian roads will be extremely efficient in marking potholes and bringing it to the attention of the Government.

A map of a city with the circles for locations of potholes, color-coded appropriately, to indicate higher marked potholes versus the lower ranked potholes could be generated. This map can be used to bring to the attention of the government the really bad roads and terrible road segments. Rather than having a couple of vehicles trying to ply roads and mark roads this will be very fast and extremely accurate.

Afterword: The concept of crowd sourcing for traffic is not new. Waze, which Google bought for close to $2bn does just that. It crowd sources traffic conditions and alerts users of the app. Also I did a Google search on using mobile apps for potholes marking and, not surprisingly, there were others who had also thought of a similar idea in Boston & Florida see the links below

1. http://www.cityofboston.gov/doit/apps/citizensconnect.asp
2. http://dailycrowdsource.com/20-resources/projects/421-crowdsourced-pothole-database-to-track-road-repair

However, I personally think that the situation in India is different, where there are ‘roads in between potholes’ ;-). While in the above 2 cases in US, only the location of the potholes is important, my idea ranks potholes based on the accumulated count and the rate of pothole marks. These metrics can be used by the government in addressing those sections of roads where the potholes have a higher rank i.e. where the traffic is highest.

Your thoughts are welcome.

Find me on Google+