One of the first things we invented at Aiaioo Labs was a cheap vest that could keep people cool in the hot Bangalore summers.
We had applied for a patent for the vest, but later abandoned the application (it had appeared in the Indian patent office gazette as 2058/CHE/2008, with a filing date of 25.08.2008).
Since we do not intend to pursue the technology to production ourselves, I thought I’d describe it in our blog in the hope that someone interested in the idea might find a way to solve the remaining problems on the road to productising it.
This figure illustrates the components of the vest:
Tubing filled with water
A connector that connects the tubing to a reservoir (a bottle) of cold water
A reservoir full of ice-cold water
A hand-pump for circulating the water
The tubing is laid out in the pattern shown in the figure above so that cold water, entering at the top, can flow through the tube freely all the way to the bottom, mixing with the fluid already in the tubing.
This prevents the formation of cold spots and permits the water to maintain an evenly cool temperature throughout the vest.
The tubes that run up from the reservoir to the top of the vest carry very cold water and the wearer needs to be insulated from them as shown in the above figure.
The coolant is circulated using a hand pump – a kind of bellows – as shown above. There are two reservoirs in the figure, but one reservoir will suffice.
The second reservoir comes in handy if the mixing of warm and cool fluids in the tubing does not warm of the coolant to a comfortable temperature. The second reservoir can then be kept at a higher temperature than the first.
The above figure is of a simple pump that I built from commonly available parts – a rubber bulb, two valves and two nozzles.
Field Trials
We built a working prototype of the vest, and on a fine day in 2008, I wore it under my clothes while travelling by bus from Banashankari to Vidyaranyapura.
I thought it felt cooler with the vest on, but not significantly.
Work Remaining
To productise this, among other things, one needs to improve the tubing.
The only tubing whose walls could maintain their shape tended to have thick rubber/plastic insulating walls which impeded the cooling effect of the vest.
Thinner tubes tended to collapse and fold sharply, stopping the circulation of the fluid.
Another issue was the pumping pressure. The hand pump (the bladder) was sufficient but needed frequent tight short squeezes to pump the fluid through the tube, which became exhausting and monotonous.
If a non-insulating, non-collapsing tubing system could be constructed, and the pump operated by a light battery-powered peristaltic pump, and the cost of the latter kept to within a few hundred rupees, then the vest could become a commercially feasible proposition.
A few of us were wondering the other day if it might be possible to carry road vehicles on metro rails.
A car is a machine with wheels that operates on certain flat surfaces, namely roads.
A metro train is also a machine on wheels, but it operates on railway tracks.
Roads tend to be very crowded, but not so the rails. Long stretches of railway tracks go unoccupied most of the time.
So, initially, we felt that if we could put cars on rails using a suitable adaptor, we could move some 4-wheeler traffic off the roads.
Such an adaptor, it turns out, is easy to build.
A cage with a roof with eyelets that allow the cage to be lifted, and wheel chocks that immobilize the car will do the trick.
Such a cage makes the car easily transportable and allows it to be lifted onto railway carriages or inaccessible parking spaces (say on the roofs of buildings).
Advantages
We calculated that a typical metro coach could hold up to 8 cars (a coach is 22 metres in length while cars are usually less than 5 metres in length, and you can stack two car cages one on top of the other).
So, 20 coaches could hold 160 cars.
Assuming a metro train frequency of one every 5 minutes and 20 car coaches, you would have an hourly capacity of 1920 cars.
Typical peak road capacities are around 1700 cars per hour per lane.
Since many central Bangalore roads are single lane roads, this could effectively double the traffic capacity at the city center.
Disadvantages
However, the plan would be hard to justify for the following reasons.
Each metro coach can carry a maximum of 300 passengers (if they are packed 6 to a square metre). So the ticket for a car would be that of 40 passengers during peak hours. I doubt anyone would pay so much to travel by car on a metro train.
The second problem is that metro coaches are prohibitively expensive. Metro coaches cost upwards of Rs. 8 crores each.
Finally, a metro transport system is designed to serve a high density of passengers. Those 20 coaches would have been of far greater service to commuters if employed to carry 6000 people instead of 160 cars.
So, it would make sense to add car-carrying trailers only after all commuter demand has been met, and only if the cost of car-carrying trailers turns out to be far less than that of passenger coaches.
Using such cages for parking also seemed like an interesting idea, but I feel that the cost of such a system might again be prohibitive (it’s cheaper in India to use a valet).
Anyways, it was an interesting thought experiment.
The OpenNLP project of the Apache Foundation is a machine learning toolkit for text analytics.
For many years, OpenNLP did not carry a Naive Bayes classifier implementation.
OpenNLP has finally included a Naive Bayes classifier implementation in the trunk (it is not yet available in a stable release).
Naive Bayes classifiers are very useful when there is little to no labelled data available.
Labelled data is usually needed in large quantities to train classifiers.
However, the Naive Bayes classifier can sometimes make do with a very small amount of labelled data and bootstrap itself over unlabelled data. Unlabelled data is usually easier to get your hands on or cheaper to collect than labelled data – by far. The process of bootstrapping Naive Bayes classifiers over unlabelled data is explained in the paper “Text Classification from Labelled and Unlabelled Documents using EM” by Kamal Nigam et al.
So, whenever I get clients who are using OpenNLP, but have only very scanty labelled data available to train a classifier with, I end up having to teach them to build a Naive Bayes classifier and bootstrap it by using an EM procedure over unlabelled data.
Now that won’t be necessary any longer, because OpenNLP provides a Naive Bayes classifier that can be used for that purpose.
Tutorial
Training a Naive Bayes classifier is a lot like training a maximum entropy classifier. In fact, you still have to use the DocumentCategorizerME class to do it.
But you pass in a special parameter to tell the DocumentCategorizerME class that you want a Naive Bayes classifier instead.
Here is some code for training a classifier (from the OpenNLP manual) in this case, the Maximum Entropy classifier.
DoccatModel model = null;
InputStream dataIn = null;
try {
dataIn = new FileInputStream("en-sentiment.train");
ObjectStream<String> lineStream =
new PlainTextByLineStream(dataIn, "UTF-8");
ObjectStream<DocumentSample> sampleStream = new DocumentSampleStream(lineStream);
// Training a maxent model by default!!!
model = DocumentCategorizerME.train("en", sampleStream);
}
catch (IOException e) {
// Failed to read or parse training data, training failed
e.printStackTrace();
}
Now, if you want to invoke the new Naive Bayes classifier instead, you just have to pass in a few training parameters, as follows.
DoccatModel model = null;
InputStream dataIn = null;
try {
dataIn = new FileInputStream("en-sentiment.train");
ObjectStream<String> lineStream =
new PlainTextByLineStream(dataIn, "UTF-8");
ObjectStream<DocumentSample> sampleStream = new DocumentSampleStream(lineStream);
TrainingParameters params = new TrainingParameters(); params.put(TrainingParameters.CUTOFF_PARAM, Integer.toString(0)); params.put(TrainingParameters.ALGORITHM_PARAM, NaiveBayesTrainer.NAIVE_BAYES_VALUE);
// Now the parameter TrainingParameters.ALGORITHM_PARAM ensures
// that we train a Naive Bayes model instead
model = DocumentCategorizerME.train("en", sampleStream, params);
}
catch (IOException e) {
// Failed to read or parse training data, training failed
e.printStackTrace();
}
Evaluation
I ran some tests on the Naive Bayes document categorizer in OpenNLP built from the trunk (you can also get the latest build using Maven).
Here are the numbers.
1. Subjectivity Classification
I ran the experiment on the 5000 movie reviews dataset (used in the paper “A Sentimental Education” by Bo Pang and Lillian Lee) with a 50:50 split into training and test:
We recently came up with three proofs that taken together suggest that the naive independence assumptions made in the Naive Bayes classifier are quite unnecessary for achieving the accuracy it is capable of.
A new classifier based on this math (called the Perplexed Bayes Classifier) is described in our recent research paper.
The perplexed bayes classifier is a classifier that resembles the naive bayes classifier but does not suffer from one of the shortcomings of the naive bayes classifier (a tendency to be unjustifiably overconfident about its predictions).
The following diagram shows how the reliability curves of the perplexed bayes classifier look alongside the naive bayes classifier’s.
We are proud to announce our latest research paper.
This paper describes an improved version of the grand old Naive Bayesian classification algorithm with rather interesting mathematical implications.
We have shown in this paper that it is possible to create a classifier that can classify data in exactly the same way as a Naive Bayes classifier, but without using the same “naive” independence assumptions from which the old classifier got its name.
Now smoke that for a second. What we’re saying is that it was completely unnecessary to make those independence assumptions to get that accuracy after all.
So you take them out.
And what results is vastly better posterior probabilities. In other words, the classifier’s confidence in a prediction becomes vastly more believable.
But since it makes the same decisions as a Naive Bayes algorithm, its accuracy is provably the same!
We call the new classifier the Perplexed Bayes classifier because it uses the reciprocal of perplexity (the geometric mean) as the combination operator for individual feature probabilities.
It turns out moreover, that the mathematical implications of using this operator are that the naive independence assumptions disappear.
However, we had not been able to explain how people could die on flat ground.
In this article, we present a model for how forces on people in a crowd of flat ground can increase to such a magnitude that people would be crushed to death.
We also present a number of mechanisms for preventing deaths due to excess pressure in crowds.
On flat ground, as long as everyone in the crowd remains standing and stationary, there would be no horizontal crushing force.
However, a person can generate a force by trying to move in any direction.
Let’s say one person can generate 10 Kilograms of lateral force.
Now, if ten people stood one behind the other, in contact with each other, and pushed in the same direction, they could be expected to generate approximately ten times the 10 Kg of lateral force.
In other words, they’d be exerting 100 Kg of force on anything ahead of them, as shown in the figure below.
When people in a crowd experience such accumulated forces, they are either injured physically or asphyxiated.
If the area of the torso coming in contact with another person in a crush is 2 square feet, about 1 ton of force (about 1000 Kg) would be needed to exert a force of 6.4 psi.
A tightly packed column of 100 people could generate that kind of cumulative lateral crushing force.
So, if a tightly packed column of people say a 100 men/women deep were to suddenly be obstructed, say by a barrier or by another group of people crossing their path, the forces experienced by those in front (or at the intersection) could be as high as 1 ton.
This seems to have been what happened in Mecca a few days ago.
How people were injured
According to eye witness accounts of the stampede during the Hajj, the deaths occurred on a flat road, and there had been pushing and jostling at the start of the stampede:
“As our group started to head back, taking Road 204, another group, coming from Road 206, crossed our way,” said another worshipper, Ahmed Mohammed Amer.
“Heavy pushing ensued. I’m at a loss of words to describe what happened. This massive pushing is what caused the high number of casualties among the pilgrims.”
On January 12, as we were returning to Mina for the last ritual of Haj, we saw the big stampede from a distance as waves of people collided.
Mathematical / Physical Models
I will now attempt to show that in a constrained space, even higher forces can be generated by a wedging effect.
The Wedge Effect
A wedge is a mechanical device that can amplify forces.
If a wedge that is four times as long as it is tall is used, and a force of 10 Kg applied along its longer edge, it can generate a force of 40 Kg in the direction of the shorter edge, as shown in the following diagram.
Restraints of any kind (railings, barriers, fences, chains) can act as wedges and increase the pressure within a crowd perpendicular to the direction of movement of the crowd.
So, a column of 20 people can generate a force of one ton if they were wedged in between fences of an aspect ratio of 1:5 (the fence closed in by 1 meter for every 5 meters of road), as shown in the following diagram (for space, we have demonstrated that a column of 5 people can generate a lateral force of 250 Kg on account of the wedging).
Wedging could also occur if the path had no constrictions, if people in the crowd moved in opposite directions, as shown in the following figure.
One of the complainants was none other than Flipkart which is, I believe, one of the largest e-commerce companies in India.
Flipkart seems to have complained that ‘it found search results to have a direct correlation with the amount of money it spent on advertising with Google through Google’s Adwords program’ (the quote is from the news article; I haven’t seen the actual complaint).
Iff Flipkart’s observations are indeed true, and if Flipkart can establish beyond a shadow of doubt the existence of a correlation between advertising expenditure and search ranking (for a random allocation of advertising spend – and we see later why this is important) then it could have serious implications for digital marketers.
If the search rankings really correlate with advertising spend, it would mean that customers would be better off not spending any money at all on advertising with Google, rather than spending a small amount of money on the same. In other words, it impacts the choice of SEO vs SEM for digital marketing.
SEO vs SEM
SEO and SEM are two strategies available to firms to bring their offerings to the notice of customers seeking information using search engines.
SEO (Search Engine Optimization) involves optimizing the text and links of web pages so that they rank higher in search results.
SEM (Search Engine Marketing) is the term used to describe the strategy of paying search engines (like Google) to display ads about a firm’s offerings alongside search results.
If there is a causal relation between advertising spend and ranking, then a common strategy used by many Indian firms – that of spending a little on SEM in addition to SEO – might hurt rather than help them.
Is Flipkart’s complaint valid?
I don’t have a detailed study and can’t provide incontrovertible evidence for the validity or invalidity of Flipkart’s complaint.
However, I have some anecdotal evidence that suggests that Flipkart’s complaint might hold some water.
And I am going to present the evidence to you in the form of a search experiment that you can all perform yourselves.
Search Experiment
Here’s an exercise that you can all try yourselves.
There is a book called “Taming Text” that is a practical introduction to a text search platform called ‘Solr’.
When I search for the string “taming text” (the location is India and I use a browser into which I am neither logged in nor signed into Google from), I get the following results:
Results for ‘taming text’ page 1 (above the fold)
As you can see, Flipkart is nowhere to be seen (though it is the largest online book retailer in India).
If you scroll down to the bottom and look ‘below the fold’, you see the following:
Results for ‘taming text’ page 1 (below the fold)
The Flipkart product page does not show up here either. But you see an Amazon India advertisement right at the bottom.
Let’s look at the second page.
Results for ‘taming text’ page 2 (above the fold)
Again, no luck. You get a link to Google books, but no Flipkart.
(We looked through 10 pages of results but found no link to Flipkart. Did you?)
So, we try a different search.
We enter “taming text flipkart” into the search engine.
And here are the results!
Results for ‘taming text flipkart’ page 1 (above the fold)
This time, the Flipkart page shows up right at the top!
In addition, a Flipkart advertisement shows up right above it.
So it appears that Flipkart had bid on the ‘flipkart’ keyword or on ‘taming text’ or on some combination of ‘flipkart’ and ‘taming text’.
When we scroll to the bottom of this page of results, we see:
Results for ‘taming text flipkart’ page 1 (below the fold)
Amazon, it appears, had also bid for either ‘flipkart’ or ‘taming text’.
Moreover, we see that Google has obviously indexed the Flipkart product page for ‘Taming Text’.
Then why was the Flipkart page ranking so low as compared to the Amazon India page?
Evil or Innocent
Could the difference in rankings be caused by the differences in advertisement expenditure on different keywords by different vendors?
If so, it would be evil.
Flipkart seems to think so, as evidenced by their complaint.
But, as it turns out, that does not have to be the case.
It is possible for the search rankings to be correlated with advertising spend without the latter causing the former (correlation without causation) in the following manner.
If Flipkart’s own SEM algorithms had bid higher on keywords that described their products better, that could in and of itself have resulted in a correlation between search ranking and ad-spend.
You probably saw a case of that in the example above.
The term ‘taming text flipkart’ would certainly have matched the link to the Flipkart product better than the link to the Amazon product. This is because of the appearance of the word ‘flipkart’ in the Flipkart URL (the word ‘flipkart’ would not have appeared in the Amazon URL).
So, the fact that more words in the search string were matched would have caused the Flipkart URL to be ranked higher. If Flipkart had bid on the keyword ‘flipkart’ but not on ‘taming text’, it would appear as if the rankings were correlated with the advertising spend. But one (the expenditure) would not have caused the other (the rankings).
Similarly, for the string ‘taming text’, the Flipkart product URL could have ranked lower than the Amazon URL merely because there are fewer buyers for the book in India than in the USA. This could have resulted in Google’s machine learning algorithms associating the name of this book with the keyword ‘Amazon’.
Thus, there could have been a correlation of ad spend and ranking without causation.
In other words, the perceived correlation could be on account of external factors that affected both variables. The only way to eliminate those external factors would be to randomly allocate advertising spend and then see if there still was a correlation. If a correlation could still be established, there would then be a strong case for saying that the relation was one of causation and not correlation.
But even if there were no evil intention (no causation), the fact remains that this ranking pattern is unfair to Flipkart, though unintendedly.
In other words, Amazon’s search rankings (if my theory as to why it ranked higher is right), might have received a boost from buyer behaviour in a geography where its competitor Flipkart does not operate.
So, Flipkart’s complaint of unfairness might indeed be warranted.
Venkatasubramanian’s research revealed that you can use a test to determine if the algorithm in question is possibly biased. If the test—which ironically uses another machine-learning algorithm—can accurately predict a person’s race or gender based on the data being analyzed, even though race or gender is hidden from the data, then there is a potential problem for bias based on the definition of disparate impact.
Search bias was also described as a cause for concern by Brin and Page in their paper on Google written during their days at Stanford:
The paper says, and I quote none other than Sergey Brin and Lawrence Page:
The goals of the advertising business model do not always correspond to providing quality search to users. … we expect that advertising funded search engines will be inherently biased towards the advertisers and away from the needs of the consumers.
Since it is very difficult even for experts to evaluate search engines, search engine bias is particularly insidious. A good example was OpenText, which was reported to be selling companies the right to be listed at the top of the search results for particular queries. This type of bias is much more insidious than advertising, because it is not clear who “deserves” to be there, and who is willing to pay money to be listed. This business model resulted in an uproar, and OpenText has ceased to be a viable search engine. But less blatant bias are likely to be tolerated by the market. For example, a search engine could add a small factor to search results from “friendly” companies, and subtract a factor from results from competitors. This type of bias is very difficult to detect but could still have a significant effect on the market.
Other interesting articles on the subject of search result bias:
I’ve always wondered if there was a way to teach people to cobble together quick and dirty solutions to problems involving natural language, from duct tape, as it were.
Having worked in the field now for a donkey’s years as of 2015, and having taught a number of text analytics courses along the way, I’ve seen students of text analysis stumble mostly on one of two hurdles:
1. Inability to Reduce Text Analytics Problems to Machine Learning Problems
I’ve seen students, after hours of training, still revert to rule-based thinking when asked to solve new problems involving text.
You can spend hours teaching people about classification and feature sets, but when you ask them to apply their learning to a new task, say segmenting a resume, you’ll hear them very quickly falling back to thinking in terms of programming steps.
Umm, you could write a script to look for a horizontal line, followed by capitalized text in bold, big font, with the words “Education” or “Experience” in it !!!
2. Inability to Solve the Machine Learning (ML) Problems
Another task that I have seen teams getting hung up on has been solving ML problems and comparing different solutions.
My manager wants me to identify the ‘introduction’ sections. So, I labelled 5 sentences as introductions. Then, I trained a maximum entropy classifier with them. Why isn’t it working?
One Machine Learning Algorithm to Rule Them All
One day, when I was about to give a lecture at Barcamp Bangalore, I had an idea.
Wouldn’t it be fun to try to use just one machine learning algorithm, show people how to code up that algorithm themselves, and then show them how a really large number of text analytics problem (almost every single problem related to the semantic web) could be solved using it.
So, I quickly wrote up a set of problems in order of increasing complexity, and went about trying to reduce them all to one ML problem, and surprised myself! It could be done!
Just about every text analytics problem related to the semantic web (which is, by far, the most important commercial category) could be reduced to a classification problem.
Moreover, you could tackle just about any problem using just two steps:
a) Modeling the problem as a machine learning problem
Spot the appropriate machine learning problem underlying the text analytics problem, and if it is a classification problem, the relevant categories, and you’ve reduced the text analytics problem to a machine learning problem.
b) Solving the problem using feature engineering
To solve the machine learning problem, you need to coming up with a set of features that allows the machine learning algorithm to separate the desired categories.
That’s it!
Check it out for yourself!
Here’s a set of slides.
It’s called “Fun with Text – Hacking Text Analytics”.
Aiaioo Labs Blog 