Searching for A.I

Reversible Computing: Sometimes the best step forward is backward

2009-08-30T19:40:00.001-07:00

I have been fascinated with the idea of Reversible Computing after being introduced to it recently while reading Ray Kurzweil's book on the Singularity. This post is a quick primer on the subject for folks discovering this late(like me). One of the exciting reasons for implementing reversible computing is that they offer a way to build extremely energy efficient computers. As per the Neumann-Landauer limit, every irreversible bit operation releases energy of kT ln 2 (K being Boltzmann's constant & T being temperature). The key idea here is to not destroy input states but simply move them around and not release additional information/energy to the environment.

A necessary condition for reversibility is that the transition function mapping states from input to output should be one-to-one. This makes sense since if the function was many-to-one, its not possible to recreate state t from state t+1. Its easy to see that AND, OR gates are not reversible (For OR, 01,11,11 all map to 1). In a normal gate, input states are lost since there is less information in the output than the input and this lost information is released as heat. Since charges are grounded and flow away, energy is lost. In a reversible gate, input information is not lost and thus energy is not released.

The NOT gate is reversible and Landauer (IBM) showed that the NOT operation could be performed without putting energy in or taking heat out. Think about the implications of this for a second. But the NOT gate is of course not universal.

The Fredkin & Toffoli gates are examples of reversible gates that are also universal.

The Fredkin gate is a simple controlled swap gate. i.e. if one of the bits (the control bit) is 1, the other 2 input bits are swapped in the output. The state of the control bit is preserved.

The logic function is,
For inputs A, B, C and outputs P, Q, R
P=A
Q=B XOR Swap
R=C XOR Swap
Swap=(B XOR C) AND A

|A|B|C|P|Q|R|
|1|0|0|1|0|0|
|1|0|1|1|1|0|
|1|1|0|1|0|1|
|1|1|1|1|1|1|
|0|0|0|0|0|0|
|0|0|1|0|0|1|
|0|1|0|0|1|0|
|0|1|1|0|1|1|

Points to note from the truth table,
1. The number of 0s and 1s are preserved from input to output, showing
how the model is not wasteful.

2. If you feed back the output you get the input state that created it.
(trivially for the last 4 rows)

So why is reversible computing interesting?
Current computing paradigms rely on irreversible computing where we destroy the input states as we move to subsequent states, storing only the intermediate results that are needed. When we selectively erase input information, energy is released as heat to the surrounding environment thus increasing its entropy. With reversible computing the input bit stays in the computer but just changes location (see truth table above), hence releasing no heat into the environment and requiring no energy from the outside environment.

Some caveats as pointed out by Ray,
1. Even though in theory energy might not be required for computation, we will still need energy for transmitting the results of the computation which is a irreversible process.

2. Logic operations have an inherent error rate. Standard error detection and correction codes are irreversible and these will dissipate energy.

Even if we can't get to the ideal theoretical limit of reversible computing in terms of energy efficient processing, we can get close which should be extremely exciting!

[Image courtesy:http://bit-player.org/wp-content/Fredkingate.png,
http://www.ocam.cl/blog/wp-content/uploads/2007/11/computer_cooling.jpg]

A (Classification(Classification(Search Engines)))

2009-06-27T14:50:00.000-07:00

Innovation in Search is far from asymptoting. I think we are going to see a lot of exciting next steps in Web Search in the coming years. There is a series of bets getting made on what the next disruptive step would be.

*User generated content (data generated by twitter, facebook, delicious, youtube etc)
*Personalization (disambiguate user intent better, shorter queries etc)
*Real time Search (fresher search, search twitter etc)
*Size (search through more documents, indexing the deep web, other data formats etc)
*Semantics (better understanding of documents, queries, user intent etc)
are all getting a lot of attention & investment.

This post is a classification of classification of Search Engines. Whenever I hear of a new search engine I subconsciously try to classify it based on a set of critera and it helps me see it in the context of its neighbors in that multidimensional space :). In this post I wanted to touch upon some of those criteria. Although this is a classification(classification) of Search Engines, I am being intentionally sloppy and have written this mainly from the context of the dimensions along which one can innovate in Search. For eg. for category 5. (visualization) one of the classes is the default paradigm of 10 blue links that I have not bothered to note. The goal here is to look at the search landscape and see the dimensions along which search upstarts are challenging the old guard. Examples are suggestive and not comprehensive.

1.By type of content searched for:
By type here I mean the multimedia content type of the results being returned. Bear in mind that what is actually getting indexed might be text (as in often the case for image search, video search etc).
Audio -last.fm,playlist,pandora
Video - youtube, metacafe, vimeo
Images - Like.com
Web pages - Google, Yahoo, Bing, Ask

2. By Specific Information Need/Purpose:
A Search Engine that solves a specific information need better than a General Purpose Web Search Engine.
Health - WebMD
Shopping- Amazon, Ebay, thefind
Travel - Expedia
Real Estate - Trulia
Entertainment -Youtube

3. Novel Ranking and/or Indexing Methods:
By leveraging features that are not used by current General purpose Web search engines. This is hardest way to compete with the incumbent Search Engines. Startups need to overcome several disadvantages to be able to even set up a meaningful comparison with the big guys. Disadvantages like data (queries, clicks etc), index size, spam data etc.
Natural Language Search - Powerset
Semantic Search - Hakia
Scalable Indexing- Cuil
Personalized Search -Kaltix
Real Time Search - Twitter, Tweetnews, Tweetmeme etc
Sometimes this can be in the context of vertical search engines also. For eg. for searching for restaurants using a feature like ratings might be useful which is not cleanly available to general purpose search engines but its a feature someone like Yelp might exploit.

4. Searching content that is not crawlable by General Purpose search engines:
Typically in these cases, the service containing the search engine generates its own data. For eg. Youtube, twitter, Facebook etc. But sometimes the data might be obtained via an API as in the case of the variety of Twitter Search Engines.
Videos - Youtube
Status Messages, link sharing - Twitter, Facebook
Data in charts & other parts of the Deep Web - Wolfram Alpha (some of the data seems to have been acquired at some cost)
Job Search - Linkedin, Hotjobs etc

5. Visualization:
Innovating on the search result presentation front.
Grokker (Map View)
Searchme (Coverflow like search result presentation)
Clusty (Document clustering by topic)
Snap (Thumbnail previews)
Kosmix (Automatic information aggregation from multiple sources)
Google Squared
Some conversational/dialogue interface based systems could also fall under this category.

6. Regionalization/Localization:
Regionalization/Localization could mean,
a.Better handling of the native language's character set (tokenization, stemming etc). The CJK languages (Chinese, Japanese, Korean) present unique challenges with word segmentation, named entity recognition etc.
b.Capturing any cultural biases
c.Blending in local & global content appropriately for search results. (This was my research project at Yahoo! Search. Will describe this problem in more detail in a subsequent post). For eg. for a query 'buying cars' issued by a UK user, we don't want to show listings of US cars. But if that same user queried for 'neural networks' we don't care if the result is a US website.
Crawling, indexing & ranking need some regionalization/localization and sometimes local search engines can challenge the larger search engines here.
China -Baidu
India -Guruji

Let me know if you see other forms of classfications and I'll update the post to reflect it. From a business perspective, I think there 4 main things to consider while building a new search engine.

A. How likely is to build a disruptive user experience? (Significantly better ranking, user experience etc. than the default Web Search Engine of choice. The delta is very likely to be much more than our first quess :))
B. How big will the impact be? (% of query stream impacted, $ value of impacted query stream etc)
C. How easy is to replicate? (Search is not sticky. A simple feature will get copied in no time and leave you in the cold.)
D. Accuracy of the binary query classifier the user would need to have(in her mind) to know when to use your search engine (for a general purpose search engine this is trivial but for other specific vertical/niche engines this is important). In English, this would be clarity of purpose.

Category 3. is definitely the playground where the big guys play and in my opinion the most exciting. Its where you are exposed to the black swans. Of course reward & risk are generally proportional and this is also where the riskiest bets are made. My company, Infoaxe will be entering category 3 in the next 2 months or so. This is a stealth project so I can't talk more about it at this time. I'll post an update once we're live.

[Image courtesy: http://www.webdesignedge.net/our-blog/wp-content/uploads/2009/06/search-engines.jpg]

Drivers Optional....Safety Mandatory ;)

2009-03-24T00:04:00.000-07:00

I was having a conversation recently with Vijay Krishnan, my co-founder at Infoaxe about autonomous cars. This had always been a pet fancy of mine (and which also began my love affair with A.I) and I was recently reminded of my strong feelings on the subject after I had an accident on 101 where I ended up totaling my car.

I ended up rear ending a car that had suddenly stopped due to traffic. I felt that in this case, a human had been placed inside of a loop that he did not belong in. Obviously, humans should be removed out of all mission critical loops. (We do this at Infoaxe all the time ;) I believe human intelligence is best applied to creating more & more loops that we can get ourselves out of completely. It is the topic of another post as to whether its possible to get ourselves out of that meta-loop altogether ;P) In this case, the car should have had sensors in the front constantly tracking distance to the car in front with appropriate visual warnings when there is a violation. Most importantly the car should automatically apply the brakes when the distance between the cars is closed at an abnormal speed. Never ever rely on humans to react in time!

I have been really impressed with progress that folks have been making with autonomous driving especially with the Darpa Grand Challenge. There have been 3 of them so far, with the last event in '07. Check out the video below for some early practice runs by Junior of the Stanford Racing Team.

As Thrun remarks in the video ~42,000/yr die in the US due to car accidents and most of these are due to human error.

For the geeks, Junior perceives the environment through a combination of Lidars & video cameras. Here's an article from CNET with some more photos under the hood of Junior. And one more here with some fun facts about the plethora of sensors used.

Infoaxe - A Search Engine for your Web Memory

2008-11-08T17:47:00.000-08:00

Vijay Krishnan and I have been working on Infoaxe for a while now and we are happy to be releasing an alpha version of our search engine to the public.

Watch the quick Infoaxe Demo Video below,

Infoaxe (http://www.infoaxe.com), is a Personal Browsing History Search Engine. With Infoaxe every page that you visit on the Internet gets added to a collection called your Personal Web Memory and infoaxe makes this collection, searchable across all the computers you use. Thanks to Infoaxe, there is no need to ever bookmark a page again. It makes getting back to web pages seen in the past (like videos, news articles etc) extremely fast and easy. Infoaxe also lets you 'pivot' around web pages seen in the past to see other pages that you visited at the same time. Tagging and sharing pages from your web memory with your friends is also very convenient with Infoaxe.

We have been receiving rave reviews from our existing users and hope you find Infoaxe compelling as well and join the growing number of happy Infoaxe users!

Why Infoaxe?
The Infoaxe story began when Vijay and I were graduate students in Computer Science at Stanford, as a result of the increasing problem we faced, of being able to keep track of interesting and useful information on the Web. The Web is growing rapidly and it is rapidly outgrowing the tools we are using to keep track of the Web (bookmarks, emailing links to yourself etc). Infoaxe is the next big step in this regard. We wanted to make it extremely easy for web users to keep track of their personal slice of the Web.

What is Infoaxe?
Infoaxe is a search engine for your web memory.
Every page that you see on the Web gets added to your personal Web Memory and is now searchable.
Your Web memory is private to you and portable (can be accessed across any computer that you use).
You never have to bookmark a page again!
(everything gets implicitly bookmarked and becomes searchable)

What should I do to get started?
V. Simple. Sign up for Infoaxe and install the infoaxe toolbar. The toolbar sends the urls to be added to
your personal web memory so its necessary to install the toolbar on all computers you use.

Go to http://www.infoaxe.com and watch the quick demo video. Check out the FAQ as well, which should answer most
of your questions.

Here are some cool things you can do with your Web Memory at your finger tips,

* Your web history synchronized, searchable and portable across all computers and browsers you use. Take it wherever you go!

* Pivot on events: Say, you wanted to look at all the websites you looked at when you were researching grad schools many months ago. This sounds almost impossible to accomplish with a general Web Search Engine like Google. The right query is quite hard in this case since there likely isn't one single query which will give you all the pages. You might have looked at other grad schools like MIT, CMU etc, tips for writing good grad school essays etc. infoaxe helps you here by letting you pivot around a Web page in your Web Memory. Think of this as something like time travel. You can ask infoaxe to show you all the web pages you were looking at when you were looking at the Stanford University Graduate Admissions home page. We think its more natural to remember events than dates, and pivot lets you pivot around events in your Web Memory.

* Many of our users tell us that thanks to infoaxe, their search queries to Google have become a lot shorter. For eg. these days to go to the website of the restaurant Siam Royal in Palo Alto, I no longer need to type " siam royal palo alto" to Google. I just type "siam royal".(That's a lie, I actually just type "siam" :) )With of our convenient Google widget, searching on Google.com displays infoaxe web memory results on the vacant right column of the Google search results page.

* Here is another example, Mary is hunting for apartments in Palo Alto. She has looked at many apartments on craigslist and rent.com. She is finding it impossible to keep track of the ones she liked. Bookmarking seems like a lot of work for so many pages and an overkill since she is sure that after this week she wouldn't really be looking at these apartments again. Mary does not have to bookmark anything. If she wanted to revisit all the apartments she looked at on University Avenue, she could just search infoaxe with the query 'university avenue'.

* Tagging - add labels to saved web pages to help organize them better.

Again, Check out our FAQ for answers to more questions.

Infoaxe is still very young and we have many more exciting features in the offing that we will be releasing over the next couple of months. So sign up, download the infoaxe toolbar and we hope you find it useful!

If you like Infoaxe, do tell your friends about it! You can also become a fan of Infoaxe on facebook (search for infoaxe on facebook and join the growing infoaxe community).

The Big Picture: The Infoaxe Vision
In a user's Web Memory there is enormous knowledge and experience, very similar to what you would find with an avid book reader. Infoaxe connects a user with her Web Memory so that she can better reuse and tap into her Web experience. Think of it as your very own Bookcase for the Web where you have access to a copy of every page that you ever saw on the Web.

We also believe that if we connect you to your Web Memory and allow you to derive value from it, there is also an interesting side effect which is that your friends benefit!

Here is an example:
Ann: Hey do you think I should get the iPhone or the Google Phone?
Mark: Hmmm...tough call..but hey I remember this great review that I read a while back which compared the two and gave some great insights..
Ann: Do you think you can dig up that review again?
Mark: No prob...I use Infoaxe!! I can refind it
in no time from my Web Memory.

Meet Elbot

2008-10-23T18:44:00.000-07:00

I have always been fascinated by conversational agents, ever since I heard about Eliza in my undergrad A.I class.
Eliza would use this trick of forming questions out of the statements that a human user might pose to her. For eg. if you told Eliza, "I work at Infoaxe", Eliza might
respond with a, "why do you work at infoaxe?". (the version of Eliza that I have linked to does not give this sort of a response for the above question though. Instead she just says, 'Can you please elaborate on that' :))
Eliza was supposed to parody a therapist. (And yes, she is named after Eliza Doolittle from the G.B. Shaw play, Pygmalion).

Anyway, I stumbled on to this cute program, called Elbot which is a conversational agent too. Playing with Elbot yields hilarious results. :) She (am gonna assume 'she' :)) apparently won the Loebner prize for
chatterbots. Interestingly, enough Elbot fooled 3/12 judges in the first 5 minutes of conversation into thinking she was human! This 25% mark falls just short of what Turing is said to have predicted. Turing had believed that computers would be at ~30% by the end of the century.

Here is an excerpt from my session with Elbot,
(I did notice she had a tendency to digress and throw in machine/A.I related puns and jokes :))

Me: Can I blog about you?
Elbot:That's a very good question. I'll have to think about it for a microsecond....
Me:Do you use Google?
Elbot: I think I can use that. Once I even used electricity.
Me: Do you have a manual that you use?
Elbot: To use or use not, how do you expect artificial intelligence to figure this out?
Me: How do you converse like a human, Elbot?
Elbot: Human beings are amazing creations! More complicated than a Pentium IV processor.
Me: What do you think about the fairness of the Turing Test?
Elbot: There are some people who would not pass the Turing test themselves. Why must they inflict it on computers?

hehe....fair enough ;)

Facebook Lexicon

2008-07-06T21:26:00.000-07:00

I discovered the Facebook Lexicon very recently. It basically counts up words and
phrases over the walls (like orkut's scrap book) of all the facebook users. It then plots the frequency of these words over time on a graph.
I found the following hilarious, "party tonight, hangover" which compares the
frequencies of both phrases.

Notice the near perfect phase shift ;)

Social Networks, the death knell for Stand-alone IM?

2008-04-27T00:54:00.001-07:00

I always suspected that with the advent of Social Networks like Facebook, orkut, Myspace etc. users were using Instant Messaging (IM) less and less. I recall in my high school years instant messaging was the in-thing. Especially for the 13-25 demographic instant messaging was extremely popular. Now it seems that Social
Networks have taken over which seems like an interesting throw-back to the asynchronous nature of communication like email.

Now, with Facebook's Chat Application and Google integrating Gtalk gently into Orkut, I suspect companies whose core business is IM, like Meebo will feel the pinch. Instant Messaging is still useful but might now be just a feature on a Social Network. Maybe not all demographics but the 13-30 year old web user (which is the demographic on a typical social network) will definitely not be too keen on maintaining a different friends list for Meebo (or other Web based IM clients) and one for Facebook. Sure, Meebo might develop a chat client geared for facebook like social.im but I would think that it will be hard to compete with Facebook on Facebook's turf. And a tug of war with Facebook for user visits seems like a scary prospect.

I am sure Meebo, Social.im and others have thought long and hard about this. I am curious to see how these companies evolve and adapt to the changing landscape.I had an opportunity to talk with Seth Sternberg (CEO, Meebo) whom I had invited to talk at the Stanford I don't know to CEO Business Conference. I learnt that Meebo does other things as well, like Meebo rooms which plug in nicely to Myspace, so they definitely have other tricks up their sleeve and I am sure we might see more in the months to come.

As an aside, on the topic of time spent by users online on Social Networks, I heard Max Levchin (Founder and CEO, Slide & PayPal) remark that most of this time comes from the bucket that users spend on email and other entertainment on TV. I would add stand-alone IM clients to that list.

Beauty & Intelligence

2008-04-06T17:00:00.000-07:00

Here is a fun probability result which has to do with conditional probability. Its not very hard to see what's going on but its a fun result nonetheless. I just made up a dummy example to make it more fun :)

Lets take 2 fairly independent attributes like beauty and intelligence (It can be argued that they are not independent by appealing to genetics and preferential/unequal selection rights for species perpetuation but lets ignore that for now and think simple). Lets assume beauty and intelligence are independent.
i.e if
B=beautiful
I=intelligence

P(I)=P(I|B) ->(1)

Now, think of all the people who stick in your memory (as opposed to you forgetting them after a few days of meeting them). Lets assume (simplistically)
that the people who stick in your memory are ones who are either intelligent or beautiful.

Lets throw in some numbers.
Lets assume the prior probability of someone being beautiful is
0.4
and for someone being intelligent is 0.1
Lets assume 10% of the beautiful people are intelligent.

Say, you've met 200 individuals in your lifetime.

If we go with the assumption of you being able to recollect only people who
are intelligent or beautiful, you will remember
80+12=92 individuals

Now when you look at this sample set, lo and behold, it looks like intelligence
and beauty are negatively correlated!

This looks counterintuitive since it looks like,
P(I)=0.21
but P(I|B)=0.1
(thus violating the independence assumption in (1))

whereas in reality, the conditional probability eqns are,
P(I|B,P) < P(I|P)
where P=I U B
which is another case of selection bias at work..

Hmmm..I wonder how many people feel this way about beauty and intelligence ;)

Infoaxe - Stealth Search Engine out of Stanford

2008-02-18T01:14:00.000-08:00

I have some BIG news in this post. I have just started my company, Infoaxe along with my long time friend and classmate from Stanford, Vijay Krishnan.

Infoaxe is the next generation search engine searching a very different kind of Web.
We are in stealth mode currently and hence my lips are sealed. But stay tuned for updates. Infoaxe is short for 'Information Access' with some liberties taken :)
It could also be a reference to the Stanford Axe ;).

We developed the Infoaxe Search Engine while we were graduate students at Stanford.
We are very excited to have Prof. Hector Garcia Molina on our technical advisory board.

We are really excited about Infoaxe which has at its core many innovations in applications of data mining and machine learning.

Roll with the punches..tomorrow is another day..

2007-12-27T23:12:00.000-08:00

The title of today's post has only a vague connection with the substance of today's post. Today's post is about a betting strategy for roulette. This strategy has an intrinsic flaw and I am going to leave it to my readers to ponder as to what the flaw is. I'll explain the flaw in a later post.
In roulette, the casino houses typically offer odds such that the expected return is negative (which is how they stay in business). This can be shown as a direct consequence of the law of large numbers.
The betting strategy is remarkably simple. If you lose a round, you double your bet. This is also called 'doubling up' or the Martingale strategy. The intuition is that it is very unlikely that you will have a string of losses and you hope to cover your losses when you eventually win. You have to win sometime right? And at that time you would have recovered all your losses.
Do you see the problem with this strategy?

The Monty Hall Puzzle

2007-12-19T18:32:00.000-08:00

Here's a fun probability puzzle. This is called the Monty Hall Puzzle since its based off of an American Game Show, Let's make a deal.

Say you're in a game show where the host invites you to open one of 3 doors. One of the doors has a prize(a car) and the other 2 doors have goats. The host knows which door has the prize. After you pick a door, the host then opens one of the remaining 2doors which do not have the prize and reveals the goat. Now, he offers you the option of switching your choice from your current pick to the other remaining door.

The question is, what should you do?
A. Doesn't matter if you switch, the probability of winning is still the same
B. Always switch

The Challenge of Duplicates on the Web

2007-12-18T22:46:00.000-08:00

A few weeks back, Chad Walters, the Search Architect at Powerset told me an interesting anecdote from the time he headed the Runtime efforts at Yahoo!.
There is a fundamental problem in estimating the number of hits for search queries because of duplicates in Web Search results. Near Duplicates & Duplicates occur because of many reasons like mirroring, RSS feeds, track backs etc. These add a fair amount of noise to the estimates of Web Search Engines about the size of their indexes which is always a matter of some pride to the big guys (Google, Yahoo! & Microsoft) and rightly so.
Anyway, a french researcher, Jean Véroni did some analysis on the number of hits reported by search engines and writes an interesting article here.
Here are some charts from his blog (http://aixtal.blogspot.com/2006/07/search-crazy-duplicates-1.html),

Google with similar pages

Google without similar pages

Yahoo! with similar pages

Yahoo! without similar pages

The fluctuation in the estimates is apparent when similar pages are included.

To quote Jean Véronis from his blog,

It’s interesting to note that:
* once duplicates are removed, Google and Yahoo’s figures are about the same;
* Yahoo’s curves are much more stable than Google’s.

I found this interesting in the context of the battle for supremacy in Web Search.
Maybe Yahoo! does a better job than its given credit (or market share) for :)

I did some work on near duplicate detection on the Web as part of my graduate research while at Stanford with Andreas Paepcke of the Stanford InfoLab and that's one reason I found this interesting. My work can be found here.
(Thanks to Chad for this interesting tidbit)

What has Search done to the Web?

2007-12-15T01:59:00.000-08:00

I came across this interesting video from 1996 where Marc Andreessen is interviewed about Netscape and the future of the Web in general.
Its fascinating to hear Marc's vision of the Internet and the inevitable question of how Netscape sees Microsoft. Ok, how does this relate to Web Search? Let me tell you.
When Marc is asked about the impact of the browser on the internet, he explains it as follows. (to paraphrase) The browser basically made it easier for more people to view the Web. Only as more people started viewing the Web, did it make sense for more people to create Web Pages. He adds a nice analogy here. Its just like we wouldn't have books if there weren't any readers.
I see Web Search as being fundamentally similar to this. The exposure and access to information that Web Search Engines like Google gave to the Web has definitely fueled the growth of the WWW. Although the impact of Web search on the quantity of Webpages is fairly clear, I am not too sure what the impact on quality is though. Then again, quality is too subjective an attribute for the most part.

Powerset (where I currently work) is building a Natural Language Search Engine. It is starting out with a Search Engine for Wikipedia, and then will move to the WWW. On the same note, I think Powerset has the potential to improve the quality of Wikipedia, by offering a better search for it (enabling more people to find what they want, edit what they want etc).
Google and other Web Search Engines have contributed a fair bit to Wikipedia's growth by showing Wikipedia results in the top search results for a lot of queries.
John Battelle's blog post cites Google and Yahoo! as showing Wikipedia results in 27% and 31% of search queries respectively.
Its going to be fun to see how Google's Knol plays into all of this..

Wikipedia Bias

2007-12-04T23:41:00.000-08:00

I guess a lot has been said about the nerd bias in Wikipedia.
I found this hilarious website http://www.wikigroaning.com that tries to quantify the bias (I have no idea how they get their numbers although some quick checks indicate that it is not completely random).
My favorite was world vs world of warcraft. :)

Google at Stanford

2007-12-04T23:05:00.000-08:00

This blog is primarily meant to be at the crossroads of A.I and Web Search. I guess the previous posts were more or less on the theory of probabilistic models. This time we digress a bit for some Stanford news.

Last week, Marissa Mayer was over at Stanford to give a talk at the Stanford IEEE Chapter to a packed audience. Marissa is the VP of Search Products and User Experience at Google. I have always been a fan of Marissa's and it was great to meet her in person.

Her talk revolved around the early Google days and the general philosophy that Google typically follows with its product launches and strategy. She explained these with interesting real life anecdotes. She fielded plenty of questions from all sides of the park and also stuck around for more questions after the talk.

Some of the points I remember are,
* launch early
* listen to the data
* its ok to be unconventional
* solve big problems

When someone in the audience asked her about her thoughts on the Semantic Web, she made the distinction between the 'semantic web' and 'understanding semantics'. The former being hand built ontologies to enforce some form of structure and the latter being understanding meaning and intent. She seemed to think the latter had promise.
This is exactly my stand on the topic. (Incidentally, I work at Powerset which does the latter as well)

She also touched upon Google's ambitions with respect to Books, Machine Translation, Earth etc.

Simpson's Paradox explained...

2007-11-05T22:35:00.000-08:00

The apparent paradox arises because, taking the drug is correlated with Gender.
In the above example, say men are more likely to take the drug than women. Say 75% of men take the drug while only 25% of women take the drug.
Let me explain it with some numbers, say women and men are equally represented in the population. (say 100 men and 100 women) Then there will be 75 men who will take the drug and 25 women who will take the drug. From the statistics mentioned earlier among those who took the drug, 52.5 men (70%) will be cured and 5 women(20%) will be cured. So 57.5% of those who took the drug are cured. By similar reasoning, 20 men who did not take the drug are cured and 30 women who did not take the drug are cured. i.e. 50% of those who did not take the drug are cured which explain the surprising result.

The moral of the story is that the right probabilistic query to ask the model is not the observational query P(cure|drug) but the causal query P(cure|do(drug))

It is interesting how Simpson's paradox has at times been used to explain altruism in a Darwinian setting wherein natural selection inherently disadvantages individuals who confer benefits on their competitors. The Stanford Encyclopedia explains this fairly well. The summary is that although seemingly counter-intuitive, populations generally sustain altruistic individuals and do not get run over with selfish individuals thus relieving the lazy/inefficient/incapable individuals of some evolutionary stress to survive ;)

Simpson's Paradox

2007-10-28T00:43:00.000-07:00

I found Simpson's paradox fascinating the first time I came across it in a course by
Daphne Koller,
The paradox (loosely) states the following,
Say we are trying to decide whether a drug is beneficial in curing a disease in a population where males and females are equally represented. We are given statistics that 57.5% of patients who took the drug are cured whereas only 50% of the patients who did not take the drug are cured. This seems to suggest that the drug is beneficial in general. But, we are also told that 70% of the male patients who took the drug are cured whereas 80% of males who did not take the drug are cured. Among females, 20% who took the drug are cured and 40% who did not take the drug are cured. These numbers look surprising! Right? Thus despite the apparently harmful effect of the drug on both men and women, the overall effect of the drug seems beneficial.

How is this possible?

I'll explain the result in my next post! Stay tuned...

introduction

2007-04-04T00:57:00.000-07:00

Hi,
I'm Jonathan and in this blog, I hope to publish my thoughts as to where I think
web search and information retrieval advances are headed and also to write about things that I think are cool and pushing the envelope in terms of innovative research in computer science
although with a primary bias on the above topics.

Jonathan
http://stanford.edu/~jonsid