## Saturday, November 16, 2013

### Simplifying ML: Neural networks- Part 3

Neural networks try to overcome the shortcomings of logistic regression in which  we have to choose a non-linear hypothesis. Logistic regression requires that we choose an appropriate combination of polynomial terms and the order of the equation. The problem with this is sometimes we either tend to overfit or underfit. Neural networks allow the ability to learns new model parameters from the basis raw parameters.
The neural network is modeled on the neural networking ability of the human brain. The brain is made of trillions of neurons. Each neuron is a processing unit which has several inputs in the dendrites and an output the axon. The neurons communicate thro a combination of electro chemical signal at the synapses or the spaces between the neuron.
A neural network mimics the working of the neuron.
So in a neural network the features of the problem serve as input. For e.g in the case of being able to determine if a mail is spam or not the features could be the words in the subject line, the from address, the contents etc. Based on a combination of these features we need to classify whether the mail is spam or not.
The above diagram shows a simple neural network with features x1, x2, xand a bias unit x0

With a hypothesis function hƟ(x) = 1/(1 + e-x)
The edges from the features x are the model parameters Ɵ. In other words the edges represent weights.
A typical neural network is a network of many logistic units organized in layers. The output of each layer forms the input to the next subsequent layer. This is shown below
As can be seen in a multi-layer neural network at the left we have the features x1,x2, .. xn.
This at the layer becomes the activation unit. The key advantage of neural networks over regular logistic regression that learns the models parameters is that learned model parameters are input to the next subsequent layers which learn the model parameters more finely. Hence this gives a better fit for the combination of parameters.
The activation parameters at the next layer are
a12 = g(Ɵ101x0+ Ɵ111x1+ Ɵ121x2 + Ɵ131x3) where g is the logistic function or the sigmoid function discussed in my previous post Simplifying ML: Logistic regression - Part 2
Here a1is the activation parameter at layer 1
Ɵ10 is the model parameter at layer 1 and is the 0th parameter. Similarly Ɵ11 is the model parameter at layer 1 and is the 1st parameter and so on.
Similarly the other activation parameters can be written as
a22 = g(Ɵ201x0+ Ɵ211x1+ Ɵ221x2 + Ɵ231x3)
a32 = g(Ɵ301x0+ Ɵ311x1+ Ɵ321x2 + Ɵ331x3)
hƟ(x) = a13 = g(Ɵ102a0+ Ɵ112a1+ Ɵ122a2 + Ɵ132a - (A)

The crux of neural networks is that instead of creating a hypothesis based on the set of raw features, the neural network with multiple hidden layers can learn its own features. In the equation (A) we can see that the hypothesis is not a function of the input raw features x1,x2,… xn  but on a new set of features or the activation units a1,a2, … a. In other words the network has ‘learned’ its own features.
As mentioned above the output of each layer is the logistic function or the sigmoid function
The beauty of neural networks based on logistic functions is that we can easily realize the equivalent of logic gates like AND, OR, NOT, NOR etc.
The hypothesis for the above network would be
hƟ(x) = g(-30 + 20 * x1 + 20 * x2)
So for x1= 0 and x2 = 0 we would have
hƟ(x) = g(-30 + 0 + 0) = g(-30)
Since g(-30) < g(0) < 0.5 = 0
Similarly a NOT gate can be constructed with a neural network as follows
Neural networks can also be used for multi class classification.
Hence there are multiple advantages to neural networks. Neural networks are amenable to a) creating complex logic models of combinations of AND, NOT, OR gates
b) The model parameters are learned from the raw parameters and can be more flexible.
It appears that the interest in neural networks surged in the 1980s and then waned, The neural networks were similar to the above and were based on forward propagation. However it appears that in recent time’s backward propagation has been used successfully in areas of research known as ‘deep learning’
This is based on the Coursera course on Machine Learning by Professor Andrew Ng. A highy enjoyable and classic course!!!

### Simplifying ML: Logistic regression – Part 2

Logistic regression is another class of Machine Learning algorithms which comes under supervised learning. In this regression technique we need to classify data. Take a look at my earlier post Simplifying Machine Learning algorithms - Part 1 I had discussed linear regression. For e.g if we had data on tumor sizes versus the fact that the tumor was benign or malignant, the question is whether given a tumor size we can predict whether this tumor would be benign or cancerous. So we need to have the ability to classify this data.
This is shown below
It is obvious that a line with a certain slope could easily separate the two.
As another example we could have an algorithm that is able to automatically classify mail as either spam or not spam based on the subject line. So for e.g if the subject line had words like medicine, prize, lottery etc we could with a fair degree of probability classify this as spam.
However some classification problems could be far more complex.  We may need to classify another problem as shown below.
From the above it can be seen that hypothesis function is second order equation which is either a circle or an ellipse.
In the case of logistic regression the hypothesis function should be able to switch between 2 values 0 or 1 almost like a transistor either being in cutoff or in saturation state.
In the case of logistic regression 0 <= hƟ <= 1
The hypothesis function uses function of the following form
g(z) = 1/(1 + e‑z)
and hƟ (x) = g(ƟTX)
The function g(z) shown above has the characteristic required for logistic regression as it has the following shape
The function rapidly asymptotes at 1 when hƟ (x) >= 0.5 and  hƟ (x) asymptotes to 0 when hƟ (x) < 0.5
As in linear regression we can have hypothesis function be of an appropriate order. So for e.g. in the ellipse figure above one could choose a hypothesis function as follows
hƟ (x) = Ɵ0 + Ɵ1x12 + Ɵ2x22 + Ɵ3x1 +  Ɵ4x2

or

hƟ (x) = 1/(1 + e –(Ɵ0 + Ɵ1x12 + Ɵ2x22 + Ɵ3x1 +  Ɵ4x2))
We could choose the general form of a circle which is
f(x) = ax2 + by2 +2gx + 2hy + d
The cost function for logistic regression is given below
Cost(hƟ (x),y) = { -log(hƟ (x))             if y = 1
-log(1 - hƟ (x)))       if y = 0
In the case of regression there was a single cost function which could determine the error of the data against the predicted value.
The cost in the event of logistic regression is given as above as a set of 2 equations one for the case where the data is 1 and another for the case where the data is 0.
The reason for this is as follows. If we consider y =1 as a positive value, then when our hypothesis correctly predicts 1 then we have a ‘true positive’ however if we predict 0 when it should be 1 then we have a false negative. Similarly when the data is 0 and we predict a 1 then this is the case of a false positive and if we correctly predict 0 when it is 0 it is true negative.
Here is the reason as how the cost function
Cost(hƟ (x),y) = { -log(hƟ (x))             if y = 1
-log(1 - hƟ (x)))       if y = 0
Was arrived at. By definition the cost function gives the error between the predicted value and the data value.
The logic for determining the appropriate function is as follows
For y = 1
y=1 & hypothesis = 1 then cost = 0
y= 1 & hypothesis = 0 then cost = Infinity
Similarly for y = 0
y = 0 & hypotheses  = 0 then cost = 0
y = 0 & hypothesis = 1 then cost = Infinity
and the the functions above serve exactly this purpose as can be seen
Hence the cost can be written as
J(Ɵ) = Cost(hƟ (x),y) = -y * log(hƟ (x))  - (1-y) * (log(1 - hƟ (x))
This is the same as the equation above
The same gradient descent algorithm can now be used to minimize the cost function
So we can iterate througj
Ɵj =   Ɵj – α δ/δ Ɵj J(Ɵ0, Ɵ1,… Ɵn)
This works out to a function that is similar to linear regression
Ɵj = Ɵj – α 1/m { Σ hƟ (xi) – yi} xi
This will enable the machine to fairly accurately determine the parameters Ɵfor the features x and provide the hypothesis function.
This is based on the Coursera course on Machine Learning by Professor Andrew Ng. Highly recommended!!!

## Friday, November 15, 2013

### Simplifying Machine Learning algorithms – Part 1

Machine learning or the ability to use computers to predict values, classify data or identify patterns is truly a fascinating field. It is amazing how algorithms can come to conclusions on data. Detecting patterns is a inborn ability of the human mind. But our mind cannot handle large quantities of data with many features. It is here that machines have an edge over us.
This post is inspired by the Machine Learning course at Coursera conducted by Professor Andrew Ng of Stanford. The lectures are truly lucid and delivered with amazing clarity. In a series of post I will be trying to distil the meaning and motivation behind the algorithms that are part of machine learning.
There are 2 major types of learning
a)      Supervised learning b) Unsupervised learning
Supervised learning: In supervised learning we have to infer the relationship between input data and output values. The intention of supervised learning is determine the possible out for some random input once the relationship has been determined. Some examples of supervised learning are linear regression, logistic regression etc.
Unsupervised learning: In unsupervised learning the problem is to determine patterns and structure in unlabeled data. Some examples of unsupervised learning are K-Means clustering, hidden Markov models etc.
In this post I would like to take a look at Supervised Learning algorithms
Linear Regression
In regression problems we try to infer the relationship between a set of input parameters to an output value. Let us we have data for the number of rooms vs. price of the house as shown below
Depending on the data we could either fit a straight line or use a linear fit. Alternatively we could fit a higher order curve to data.
The function that determines the relationship is also known as hypothesis function. This can be represented as follows for e.g a hypothesis function with a single feature
hƟ(x) = Ɵ1x+ Ɵ0

The above equation is the hypothesis function where Ɵ is the parameter and x is the feature
We could have a higher order hypothesis function as follows
hƟ(x) = Ɵ2x2+ Ɵ1x+Ɵ0

To evaluate whether the hypothesis function is able to map the input and related output accurately is known as the ‘cost function’.
The cost function can be represented as
J(Ɵ) = 1/2m Σ(hƟ (xi)  - y i)2
The cost function really calculates the ‘mean squared error’ of the actual data points (y) with the points on the hypothesis function (hƟ). Clearly higher the value of J(Ɵ) the greater is the error in predicting the output based on a set of input parameters. If we just took the error instead of the squared error then if there were data points on either side of the predicted line then the positive & negative errors could cancel out. Hence the approach is usually to take the mean of the squared error.
The goal would be to minimize the error which will result in the best fit.
So the approach would be to choose values for the parameters Ɵi
The algorithm that is used for determining the values of the parameters that will result in the minimum error is gradient descent
The formula is
Ɵj := Ɵj – αd/d Ɵj J(Ɵ)
Where α is the learning rate
Gradient descent starts by picking a random value for Ɵi. Then the algorithm looks around to search for the next combination that will take us down fastest. By continuing this process the local minima is determined.
Gradient descent is based on the observation that if the multivariable function  is defined and differentiable in a neighborhood of a point , then  decreases fastest if one goes from  in the direction of the negative gradient. This is shown in the below diagram taken from Wikipedia.
For e.g for a curve as shown below
This how I think the gradient descent works. In the above diagram at point A the slope is +ve and taking the negative of the slope multiplied by the learning factor α and subtracting it from Ɵj will result in a value that is less than Ɵj. That is we move towards the minima or C. Similarly at point B the slope will be -ve. If we multiply by  - α then we will add to Ɵj. Hence we will move to the right or towards point C.
By applying the iterative process of gradient descent we can get the combination of parameter values for  Ɵ that will provide the best fit for the set of data points
The iterative process of gradient descent is applied to minimize the cost function which is function of the error in the current hypothesis
δ/δ J(Ɵ) = δ/ δ Ɵ * 1/2m Σ(hƟ (xi)  - y i)2

This process is applied iteratively to the below equation to arrive at the values of Ɵi
The formula is
Ɵj := Ɵj – αd/d Ɵj J(Ɵ)
to obtain the values for the best fit equation
hƟ(x) = Ɵ2xn+ Ɵ1xn-1+ …+  Ɵ0

## Tuesday, October 29, 2013

### Dissecting the Cloud – Part 2

This post further delves in a little more deeply into the cloud. In the last post Dissecting the Cloud –Part1, I described the analogy of a person partitioning a large house by creating self-contained units through the use of a hypervisor which abstracts the underlying hardware( CPU, storage and NICs) into virtual CPUs, virtual NICs and virtual disks.

Hence there are has several instances on the cloud each with its own CPU, NIC and storage. In fact several tenants can reside on the same cloud with their own individual CPU, NIC and storage. This is known as multi-tenancy.

However multi-tenancy creates a unique set of associated issues similar to that of a multi-tenanted house. For e.g. how does one isolate one tenant from another? How does one charge each tenant? Are the tenants secured from the prying eyes of their neighbors? How can the owner ensure that one  particular tenant does not consume an inordinate amount of water or electricity at the expense of other tenants?

These are typical problems in a multi-tenanted cloud. A common and a high profile issue in the cloud is that of the ‘noisy neighbor’. In this situation one of the instances of the cloud hogs the network bandwidth or the storage tier, resulting in a severe bandwidth crunch or storage access problems for other instances. Here is an interesting article on the noisy neighbor issue “The Problem with noisy neighbors in the cloud”.

It appears that IBM has patented a solution for the bandwidth crunch caused by noisy neighbors: IBM patents ‘noisy neighbor’ problem with SDN.

In order to ensure that multi-tenancy can be realized in the cloud it is essential to isolate the virtual CPUs, network and storage in the cloud

Network isolation: Network isolation is achieved through the use of VPNs (virtual private network), VLANs (Virtual LANS) and subnetting.

A VPN creates a secure tunnel between a user and the cloud instance while accessing the instance from the internet. The data in motion is encrypted using IPSec.  Also vNICs belonging to a client are logically grouped together in a VLAN. Groups of vNICs can be sub-netted together to allow broadcast between then.  VLANs can effectively isolate traffic between itself and other VLANs. A very good write-up of VLANs and sub-netting can be seen at “What is the difference between subnetting and VLAN”.

Storage isolation: Storage in cloud can be made of block storage, SAN or NAS storage. Storage isolation is typically achieved through the hypervisor and zoning. Zoning is the partitioning of a Fibre Channel fabric into smaller subsets to restrict interference, add security, and to simplify management.  While a SAN makes available several devices and/or ports to a single device, each system connected to the SAN should only be allowed access to a controlled subset of these devices/ports.

CPU isolation: The hypervisor does create individual instances all fairly isolated from one another. However this is the area that is receiving more attention than storage or networking isolation because of security concerns and is prone to attack. In fact I was greatly surprised to hear that there is a technique called ‘side channel’ attack by which an intruder by just observing the time that is taken for computations and the temperatures generated can reverse engineer the actual instructions. This is really a scary thought!

This is how multi-tenancy is achieved in clouds. I hope to revisit this topic again in the future.

### Dissecting the Cloud – Part 1

“The Cloud brings it with it the promise of utility-style computing and the ability to pay according to usage.
Cloud Computing provides elasticity or the ability to grow and shrink based on traffic patterns.
Cloud Computing does away with CAPEX and the need to buy infrastructure upfront and replaces it with OPEX model and so on”.
All this old news and has been repeated many times. But what exactly constitutes cloud computing? What brings about the above features? What are its building blocks of the cloud that enable one to realize the above?
This post tries to look deeper into the innards of the Cloud to determine what the cloud really is.
Before we get to this I would like to dwell on an analogy to understand the Cloud better.
Let us assume, Mr. A owns a large building of about 15,000 sq feet and about 100 feet tall. Let us assume that Mr. A wants to rent this building.
Now, assume that the door of this building opens to single, large room on the inside!
Mr. X comes to rent this building. If this was the case then poor Mr. X would have to pay through his nose, presumably, for the entire building even though his requirement would have been for a small room of about 600 x 600 feet. Imagine the waste of space. Moreover this would also have resulted in an enormous waste of electricity. Imagine the lighting needed. Also an inordinate amount of water would have to be utilized if this single, large room needed to be cleaned. The cost for all of this would have to be borne by Mr. X.
This is clearly not a pleasant state of affairs for either Mr. X or for the owner Mr. A of the building.
The solution to this is easy.  What Mr. A needs to do, is to partition the building into self-contained rooms (600 x 600 sq feet) with all the amenities. Each self-contained unit would need to have its own electricity and water meter.
Now Mr. A can rent rooms to different tenants on their need basis. This is a win-win situation both for Mr, A and Mr. X. The tenants only need to pay for the rooms they occupy and the electricity and water they consume.
This is exactly the principle behind cloud computing and is known as ‘virtualization’
There are 3 computing components that one must consider. CPU, Network and Storage. The below picture shows the virtualization of CPU,RAM, NIC (network card), Disk (storage)
The Cloud is essentially made up of  anywhere between 100 servers to 100,000 servers. The servers are akin to the large building. Running a single OS and application(s) on the entire server is a waste of computing, storage and network resources.
Virtualization abstracts the hardware, storage and network through the use of software known as the ‘hypervisor’. On top of the hypervisor several ‘guest OSes’ can run. Applications can then run on these guest OSes.
Hence over the CPU (single, dual or multi-core) of the server,  multiple guest OS’es  can run each with its own set of applications
This is similar to partitioning the large CPU resource of the server into smaller units.
There are 3 main Virtualization technologies namely VMware, Citrix and MS Hyper-V
Here is a diagram showing the 3 main the virtualization technologies
To be continued ...

## Friday, October 25, 2013

### Close encounters with the future

Published in Telecom Asia, Oct 22,2013 - Close encounters with the future

Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes and perhaps weigh 1.5 tons.—POPULAR MECHANICS, 1949

Introduction: Ray Kurzweil in his non-fiction book “The Singularity is near – When humans transcend biology” predicts that by the year 2045 the Singularity will allow humans to transcend our ‘frail biological bodies’ and our ‘petty, derivative and circumscribed brains’ . Specifically the book claims “that there will be a ‘technological singularity’ in the year 2045, a point where progress is so rapid it outstrips humans' ability to comprehend it. Irreversibly transformed, people will augment their minds and bodies with genetic alterations, nanotechnology, and artificial intelligence”.

He believes that advances in robotics, AI, nanotechnology and genetics will grow exponentially and will lead us into a future realm of intelligence that will far exceed biological intelligence. This explosion will be the result of ‘accelerating returns from significant advances in technology”

Futurescape

Here is a look at some of the more fascinating key trends in technology. You can decide whether we are heading to Singularity or not.

Autonomous Vehicles (AVs): Self driving cars have moved from the realm of science fiction to reality in recent times. Google’s autonomous cars has already driven around half a million miles. All the major car manufacturers of the world from BMW, Mercedes, Toyota, Nissan, Ford or GM are all coming with their own versions of autonomous cars. These cars are equipped with Adaptive Cruise Control and Collision Avoidance technologies and are already taking away control drivers. Moreover AVs alert drivers, if their attention strays from the road ahead, for too long. Autonomous Vehicles work with the help of Vehicular Communication Technology.

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.

Smart Assistants: From the defeat of Kasparov in chess by IBM’s Deep Blue in 1997, and then subsequently to  the resounding victory of IBM’s Watson in Jeopardy, capable of understanding natural human language, to the more prevalent Apple’s intelligent assistant Siri, Artificially Intelligent  (AI) systems have come a long way. The newest trend in this area is Smart Assistants.  Robots are currently analyzing documents, filling prescriptions, and handling other tasks that were once exclusively done by humans. Smart Assistants are already taking over the tasks of BPO operators, paralegals, store clerks, baby sitters. Robots, in many ways, are not only smarter than humans, but also do not get easily bored,

Intelligent homes and intelligent offices. 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. All gadgets at home will be accessible through laptops, tablets or smartphones from anywhere. We will be able to monitor all aspects of our intelligent home from anywhere.

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.

Swarms of drones: Contrary to the use of weaponized drones for unmanned aerial survey of enemy territory we will soon have commercial drones. Drone will start being used for civilian purposes.  The most compelling aspect of drones these days is the fact that they can be easily manufactured in large quantities, are cheap and can perform complex tasks either singly or collectively. Remotely controlled drones can perform hundreds of civilian jobs, including traffic monitoring, aerial surveying, and oil pipeline inspections and monitoring of crop conditions. Drones are also being employed for conservation of wildlife. In the wilderness of Africa, drones are already helping in providing aerial footage of the landscape, tracking poachers and in also herding elephants. However, before drones become a common sight, it is necessary to ensure that appropriate laws are made for maintaining the safety and security of civilians. This is likely to happen in US in 2015, when the Federal Aviation Administration (FAA) will come up with rules to safely integrate drones into the American skies.

MOOC (Massive Online Open Course): The concept of MOOC, or the ‘Massive Open Online Course’ from top colleges, though just a few years old, is already taking the world by storm. Coursera, edX and Udacity are the top 3 MOOCs besides many others and offer a variety of courses on technology, philosophy, sociology, computer science etc.  As more courses are available online, the requirements of having a uniform start and end date will diminish gradually. The availability of course lectures at all times and through all devices, namely the laptop, tablet or smartphone, will result in large scale adoption by students of all ages.

Contrary to regimented classes MOOCs now allow students to take classes at their own pace. It is likely that some students will breeze through an entire semester worth of classes in a few weeks. It is also likely that a few students will graduate in 4 years with more than a couple of degrees. MOOCs are a natural development considering that the world is going to be more knowledge driven where there will be the need for experts with a diverse set of in-depth skills. Here is an interesting article in WSJ “What College will be like in 2023

3D Printing: This is another technology that is bound to become ubiquitous in our future. 3D printers will revolutionize manufacturing in ways we could never imagine. A 3-D printer is similar to a hot-glue gun attached to a robotic arm. A 3-D printer creates an object by stacking one layer of material, typically plastic or metal, on top of another.  3D printers have been used for making everything from prosthetic limbs, phone cases, lamps all the way to a NASA funded 3D pizza. Here is a great article in New York Times “Dinner is Printed” It is likely that a 3D printer would be indispensable to our future homes much like the refrigerator and microwave.

Artificial sense organs: A recent news items in Science 2.0 “The Future touch sensitive prosthetic limbs”   discusses the invention of a prosthetic limb that can actually provide the sense of touch by stimulating the regions of the brain that deal with the sense of touch. The researchers identified the neural activity that occurs when grasping or feeling an object and successfully induced these patterns in the brain. Two parallel efforts are underway to understand how the human brain works. They are “The Human Brain Project” which has 130 members of the European Union and Obama’s BRAIN project. Both these projects attempt to ‘to give us a deeper and more meaningful understanding of how the human brain operates”. Possibilities as in the movies ‘Avatar’ or ‘Terminator’ may not be far away.

The Others: Besides the above, technologies like Big Data, Cloud Computing, Semantic Web, Internet of Things and Smart Grid will also be swamp us in the future and much has already been said about it.

Conclusion: The above sets of technologies represent seismic shifts and are bound to explode in our future in a million ways.

Given the advances in bionic limbs, Machine Intelligent AI systems, MOOCs, Autonomous Vehicles are we on target for the Singularity?

I wouldn’t be surprised at all!

### ‘The Search’ is not yet over!

Published in Telecom Asia, Oc9, 2013 - 'The search' is not yet over!
In this post I take a look at the technologies that power the now indispensable and ubiquitous ‘search’ that we do over the web. It would be  easy to rewind the world by at least 3 decades by simply removing ‘the search’ from our lives.
A classic article in the New York Times, ‘The Twitter trap’ discusses how technology is slowly replacing some of our more common faculties like the ability to memorize or perform simple calculations mentally.
For e.g. until the 15th century people had to remember a lot of information. Then came Gutenberg with his landmark invention, the printing press, which did away with the need to store information. Closer to the 2oth century the ‘Google Search’ now obviates the need to remember facts about anything. Detailed information is just a mouse click away.
Here’s a closer look at evolution of search technologies
The Inverted Index: The inverted index is a way to search the existence of key words or phrases in documents.  The inverted index is an index data structure storing a mapping from content, such as words or numbers, to its locations in a document or a set of documents. The ability to store words and the documents in which it is present, allows for an quick  retrieval of the related documents in which the word(s) are present. Search engines like Google, Bing or Yahoo typically crawl of the web continuously and keep updating this index of words versus the documents as new web pages and web sites are added. The inverted index is a simplistic method and is neither accurate nor efficient.

Google’s Page Rank: As mentioned before merely the presence of words in documents alone is not sufficient to return good search results. So Google came along with its PageRank algorithm. PageRank is an algorithm used by the Google’s  web search engine to rank websites in their search engine results.  According to Google PageRank works by “counting the number and quality of links to a page to determine a rough estimate of how important the website is.”  The underlying assumption is that more important websites are likely to receive more links from other websites.
In essence the PageRank algorithm tries to determine the likelihood that a surfer will land on a particular page by randomly clicking on links. Clearly the PageRank algorithm has been very effective for searches as now ‘googling’ is synonymous to searching (see below from Wikipedia)

Graph database: While the ‘Google Search’ is extremely powerful it would make more sense if the search could be precisely tailored to what the user is trying to search. A typical Google search throws up a few 100 million results.  This has led to even more powerful techniques, one of which is the ‘Graph database’. In a Graph database data is represented as a graph. Nodes in the graph can be entities and edges could be relationships. A search on the graph database will result in the traversal of the graph from a specific start node to specific terminating node. Here is a fun representation of a simple Graph database representation from InfoQ

Google has recently come out with its Knowledge Graph which is based on this technology. Facebook allows users to create complex queries of status updates using the graph database.
Finally, what next??
A Cognitive Search??: Even with the graph database the results cannot be very context specific. What I would hope to happen in the future is have a sort of a ‘Cognitive Search’ where the results would be bounded and would take into account the semantics and context of a user specified phrase or request.
So for e.g. if a user specified ‘Events leading to the Iraq war’ the search should throw all results which finally culminated in the Iraq war.
Alternatively if I was interested in knowing for e.g. ‘the impact of iPad on computing’ then the search should throw precise results from  the making of the iPad, the launch of iPad, the various positive and negative reviews and impact iPad has had on the tablet and computing industry as a whole.
Another interesting query would ‘The events that led to the downfall of a particular government in election of 1998’ the search should precisely output all those events that were significant during this specific period.
I would assume that the results themselves would come out as a graph with nodes and edges specifying which event(s) triggered which other event(s) with varying degrees of importance.
However this kind of ability where the search is cognitive is probably several years away!