For the last couple of days, I and @sudheer_624 have been busy working on this hack for a Yahoo! Hackday. Although still a prototype, the hack has turned out to be interesting so we thought of putting it out for others to play around with.

Dygest (pronounced as ‘digest’ - thanks to @bluesmoon) is aimed at changing the conventional way of displaying search context via a snippet to a more informative, machine generated document summary. There two kinds of relevance for evaluating search results:

• Vertical relevance: determined by the ranking algorithms.
• Horizontal relevance: the contextual information made available to the user about the result - Searchmonkey is a good initiative on this front.

The current way of displaying this context is via a snippet of text under every result. This snippet shows the neighborhood of the occurrence of the query terms. Usually this information is not rich enough for a searcher to make the right judgement about the result. This causes the searcher to switch back and forth between the documents and the search results if the the page is not relevant. This can be frustrating at times.

Dygest aims to solve this by either replacing or enhancing the current search snippet with a summary of the result page. At its core lies a summarization engine which figures out what the *real* content of the page is (distinguishing it from the other junk like surrounding text, navigational text, comments etc) and then performs text summarization on this content. The summary of the page is then displayed to the user via the appropriate interface. How cool is that?

The user no longer needs to click on irrelevant links. He/She can perceive the theme/important facts of the page from right within the results page. The other advantage of this is that it gives the user a good overview of the query topic - he no longer needs to spend time reading many long documents but rather read a few summaries from the top results to get a good overview of the subject. This is particularly well suited for mobile devices where its frustrating to switch back and forth between pages and the search results. This is also fit for news articles where we just need the important facts about the story.

Well, here is an example to convince you. A search for ‘Carol Bartz’ yields the following result which at the first glance is not at all informative.

Enhancing the existing view with an abstract of the page helps gauge the content and theme of the document. This would now look like:

Dygest outputs the following summaries for the query ‘Iran‘ restricted to Yahoo! News:

And following for ‘Obama stimulus plan‘:

Currently, Dygest has two interfaces - (1) a search interface powered by yahoo boss and (2) a searchmonkey plugin. Its just a prototype so be kind and don’t be too judgmental.

Start dygesting here.

Lets try to implement Hadoop’s ‘Hello World’ (Word Count) example. The MySQL table is as follows:

CREATE TABLE `wordcount` (
`word` varchar(255) DEFAULT NULL,
`count` int(11) DEFAULT NULL
)


We need a class that implements the map and reduce tasks. Lets call this class WordCount. This class needs to extend Configured and implement the Tool interface.

public class WordCount extends Configured implements Tool {

We need to implement the Tool interface to parse the generic options. This is needed as we will be passing the mysql-connector jar via command line argument (-libjar) to hadoop. This jar will become part of the custom configuration for the WordCount class. Thus, the WordCount class needs to be configurable as well. This is done by extending Configured.

Tuples/rows from the DB are converted to Java objects. Thus we need to define a class that would hold the tuples. All such classes need to implement the Writable and DBWritable interfaces. Typically every table that we want to read/write needs to be represented by a class implementing the above interfaces. We will be dealing with reading tables, hence only the read functions are overridden.

   static class WordRecord implements Writable, DBWritable {
        String word;
        int count;

        public void write(DataOutput arg0) throws IOException {
            throw new UnsupportedOperationException("Not supported yet.");
        }

       public void readFields(DataInput in) throws IOException {
            this.word = Text.readString(in);
            this.count = in.readInt();
        }

        public void write(PreparedStatement arg0) throws SQLException {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        public void readFields(ResultSet rs) throws SQLException {
            this.word = rs.getString(1);
            this.count = rs.getInt(2);
        }
    }

Once we’re done with this, its time to define the map and reduce operations. In the map function, we are just outputting the tuple, with the word as the key and its count as the value.

    static class WordCountMapper extends MapReduceBase
            implements Mapper {

        public void map(LongWritable key, WordRecord value,
                OutputCollector output, Reporter reporter)
                throws IOException {

            output.collect(new Text(value.word), new LongWritable(value.count));
        }
    }

In the reduce function, we are summing up the counts associated for a given word and outputting the [word , sum].

    static class WordCountReducer extends MapReduceBase
            implements Reducer {

        public void reduce(Text key, Iterator values,
                OutputCollector output, Reporter reporter)
                throws IOException {

            long sum = 0L;
            while (values.hasNext()) {
                sum += values.next().get();
            }
            output.collect(key, new LongWritable(sum));
        }
    }

Since we implemented the Tool interface, we need the WordCount class to implement the run function. In this function, we will specify the job configuration, configure the mapper and reducer classes, configure the DB, set the input and output to the job etc.

public int run(String[] arg0) throws Exception {
        // the getConf method is implemented by Configured - this way we can pass the generic options to the job
        JobConf job = new JobConf(getConf(), WordCount.class);

        job.setJobName("word count job");

        // set the mapper and reducer classes
        job.setMapperClass(WordCountMapper.class);
        job.setCombinerClass(WordCountReducer.class);
        job.setReducerClass(WordCountReducer.class);

        // configure the DB - provide the driver class, provide the mysql host and db name in the url
        DBConfiguration.configureDB(job, "com.mysql.jdbc.Driver", "jdbc:mysql://localhost/mysqlhadoop");

        // define the fields you want to access from the table
        String[] fields = {"word", "count"};

        // specify which class represents the tuple as well as the table to be accessed (in this case 'wordcount')
        // alternatively we can also specify a SQL query (which here is null)
        // we are sorting the results by the field 'word'
        DBInputFormat.setInput(job, WordRecord.class, "wordcount", null, "word", fields);

        job.setMapOutputKeyClass(Text.class);
        job.setMapOutputValueClass(LongWritable.class);

        job.setOutputKeyClass(Text.class);
        job.setOutputKeyClass(LongWritable.class);

        // write the final results to a folder in HDFS
        // alternatively we can also write the output back to mysql using DBOutputFormat
        FileOutputFormat.setOutputPath(job, new Path("output_wordcount);

        JobClient.runJob(job);

        return 0;
    }

And now finally we can define the main function as

    public static void main(String args[]) throws Exception {
        int ret = ToolRunner.run(new WordCount(), args);
        System.exit(ret);
    }

To see how the above pieces fit together take a look at WordCount.java.To run this job we need to provide the mysql-connector jar in the classpath. This can done by either placing this JAR in the $HADOOP_HOME/lib or by providing this JAR in the command line as follows:

$ ==> hadoop jar wordcount.jar WordCount -libjars mysql-connector-java-5.1.7-bin.jar

Its that easy to get hadoop talking to MySQL and you are ready to do some heavy number crunching. Get hold of WordCount.java here.

The *What* to *How* spectrum on page 100 is a must see.

Fun fact: Turing was conceived in Chhatrapur, Orissa, India. His father, Julius Mathison Turing, was a member of the Indian Civil Service. (via Wikipedia)

I have just started to scratch the surface of Natural Language Processing for my next project (involving NLP and Twitter - details to follow) and I already have a dozen questions bothering me. I shall attempt to put forth a few of the ideas and questions in this post. Lets talk briefly about the structure of language. Language has different levels of structure:

1. dicourse - group of sentences
2. sentences
3. phrases
4. words
5. and so on…

Between the ’sentences’ and ‘words’ lies the syntactic structure of language. This syntactic structure is built using the parts of speech of the words: nouns, verbs, etc. Words are grouped into phrases whose formation is governed by the grammar rules, for example:

Sentence -> ‘Noun Phrase’ . ‘Verb Phrase’
‘Noun Phrase’ -> Determiner . Adjective . Noun
‘Verb Phrase’ -> Verb . ‘Noun Phrase’

A sentence is grammatically correct if it adheres to the grammar of the language (like described above). With just the above knowledge about language (something you might have learnt in the 5th grade) we can see that for a candidate sentence to make sense in some language, it has to be composed of meaningful components and these components have to be in some specific order for it to logically make sense.

Grammar of Thought

This has led me to ponder if an analogous grammar exists for ‘thought’. Our thoughts can also be broken down into meaningful components and the components here also have to follow some implicit ordering for the ‘thought’ to make sense. If you think about the way you think, you will notice that as you run from one thought to another there is some logical connection between them just as between the sentences in a paragraph. If we could somehow get a formal representation of this grammar, wouldn’t it enable machines to think?

Language and Thought

There is enough literature out there which links the structure of language with the structure of thought. Benjamin Whorf states in his writings:

the structure of a human being’s language influences the manner in which he understands reality and behaves with respect to it

Thus, human cognition is based on the structure of language which in turn is the grammar defining the language. Hence a machine capable of generating sequence of grammatically correct sentences which also fit together logically (discourse), should have some ability of cognition. Even the Turing test uses natural language as a test for some level of cognition. Is this perspective of Natural Language Processing as a means of provisioning cognition to a machine, correct? Could this be another path for achieving artificial intelligence? I would love to get an answer to this from NLP experts out there.

Or is it just one of my other posts which don’t make sense because its 3am and I’m half asleep?

This is a follow-up post of The Monkey Just Got Delicious - I. The app is not yet public for the reasons mentioned in part I. As I had mentioned, my goal was to generate a tag cloud for the search results. Well, search monkey does not allow you to spit out arbitrary html, thus making it difficult to render a tag cloud. After much thought I settled for a color coded tag cloud (as in the screenshot below). You will notice the color of the tags gradually fading (darker shade means that the tag is more popular).

Got feedback, will listen.

[UPDATE] New tag cloud UI for deliciousify can be viewed here

[UPDATE] The search monkey app is currently disabled for public use as it was hitting the delicious rate limit. Hence it will remain as a prototype for now. BTW the delicious team is working on their own search monkey app and I bet its going to be much cooler.

I’m a big fan and an avid user of Yahoo! Search Monkey. So this weekend I decided to write myself a search monkey application that I have always wished for. Well, we all will agree that nothing beats human created metadata and what better metadata about search results can there be than the vast and rich knowledge stored in bookmarking services. My search monkey application deals with enriching the organic search results from Yahoo! with metadata from del.icio.us.

Sometimes the search summary does not provide a useful insight into the contents of the search result (as seen below). The only way users ascertain relevance is by clicking on the result and figuring it out themselves. Wouldn’t it be better if the contents of the result could be summarized by just a few words - keywords that highlight broadly what the document talks about. Deliciousify (as seen below) aims to solve this problem by listing the top tags about a search result from del.icio.us, along with its popularity (number of people who have bookmarked it). In the future, I plan to display a tag cloud for the results. Give it a try and send any comments/feedback my way.

• No day-0, day-1, or day-2 effects of terror are observed on traffic fatalities, but there is an increase of almost 35% in the rate of traffic fatalities 3 days after terror attacks.
• The findings suggest that the third-day effect of large terror attacks is even larger, with a 69% increase in traffic fatalities.
• Interestingly, the 3-day lag observed is similar to that found in studies on imitative suicides, in which well publicized suicides are followed 3 days after with a rise in traffic fatalities. [reference]
• A similar 3-day spike in homicides is also found after major boxing matches. [reference]
• Some fraction of the increase in traffic fatalities after terror attacks may be attributable to covert suicides and/or increased aggression on the road.
• There is a notable lack of longer-term effects beyond the 3-day spike in fatal accidents. Days four and beyond have normal levels of traffic volume and accidents and suggest that the effects of terror are transient.
• Why traffic fatalities increase on the third day after a terror attack remains a puzzle.

Possible explanations to the 3-day lag are:

• The day-three increase in fatalities coincides with the time when those exposed to terror may try to return to their normal routines but are not yet psychologically, and perhaps physiologically, sufficiently recovered.
• Yet another explanation for the 3-day lag is that it is a counterreaction to the collective bonding that occurs immediately after the terror event, similar to the “post-suppression rebound” found in experimental psychology.

The interesting point to look for in the graphs below is the 3rd day after the attack.

Other similar interesting reads are in the references of the paper. I am listing a few of them below:

• Motor vehicle fatalities increase just after publicized suicide stories
• Airplane Accident Fatalities Increase Just After Newspaper Stories About Murder and Suicide