We’re back!

09
Aug
2010
Hey Everyone,
So much has been happening here at Digital Trowel in the past months, and we’ve sort of let the blog fall to the side. But no more!
This blog is now a company-wide affair. You’ll be seeing regular postings from numerous members of our team, about everything from text mining and data analytics, to new product ideas and development updates.
First up – Steve Gasner, our Chief Data Officer, posting about risk modeling.
Please comment and reply. All are welcome. For any other questions, please feel free to email yoni (at) digitaltrowel.com with any questions or comments.
Enjoy!

The present state of development, future trends and expected market scenarios for Semantic Technologies are shown in the just published “Demand driven Mapping Report”. The report is part of the EU-funded project Value It, which is about bringing together the various stakeholders within the sector: Industry, Research and Government. VALUE-IT preliminary findings show that the STE potential market in Europe will size up to €1.44B for 2014. Scanning furthermore the executive summary of the report, some findings attract attention:
The survey results also show considerable variation by sector, both of policy and technology implementation. With respect to technologies, ICT companies are also the most willing to consider semantic approaches. The ICT sector has an unusually high interest in all ST components, with 20% or more being willing to consider all of them, and over half of IT respondents looking at Web 2.0 (social computing). [...]  The use of tagging technologies – which overall is the least mature approach in the survey – is most advanced in Life Sciences. The Life Sciences, Media & Entertainment, and ICT sectors all have a reasonably strong interest in Natural Language Processing (roughly 25% on average). Ontologies and RDF/OWL are the technologies least often considered, though the interest in these Semantic Technologies is not insignificant. Taxonomies are slightly more popular, perhaps indicating that companies are taking the first step to prepare for a more semantic approach to IT solutions. The ICT, Energy & Utilities, and Media & Entertainment sectors all have a reasonably strong interest in using taxonomies.
The 190 pages report gives an actual overview of the status quo on European Semantic Technology Market and is now available for download: Final demand driven mapping Report

Part 2 – Synergistic Sentiment Analysis:

The Space Between the Lines

Welcome back! Sit down and buckle up for a magical tour of the text mining technology focusing on Sentiment Analysis (SA).

Well, first things first. What is Sentiment Analysis anyway? Rephrasing the Wikipedia definitionSentiment analysis (sometimes called opinion mining) refers to an area of Natural Language Processing (NLP), which aims to determine the attitude of a writer with respect to some topic. This attitude may be their judgment or evaluation, their emotional state when writing or the intended emotional communication the author wishes to convey.

To keep our discussion as concrete as possible we’ll use real life examples to elucidate the different types of attitudes.  Consider the following example:

This year was a setup year for B&N, and 2010 will see its efforts start to pay off [...] In 2010, B&N will rack up significant sales of Nooks and e-books, as some consumers look for an Amazon alternative.

Obviously this excerpt contains an explicit positive evaluation for Barnes and Noble for 2010, but moreover the tone is upbeat, optimistic, and even excited. A good Sentiment Analysis would pick up on this tone and report a highly positive sentiment for B&N and their e-reader Nook, whereas a negative or at least an apprehensive sentiment should be reported for Amazon.

The next example is even more blatant:

Belated Happy New Year and already what a year it’s turning out to be for eReaders! [...] Time’s a fave around here these days, especially considering its December report naming nook one of the Best Travel Gadgets of 2009 as well as rating the device # 2 among the Top Ten Gadgets of the year. While emphasizing nook’s “classy book-lending feature”, the magazine also cited “the powerful, flexible Android operating system that the whole package runs on.”

The exclamation mark, the rhythm, the tone, the profuse use of superlatives and positive adjectives all indicate an extremely positive sentiment for the nook product. It is clear that the author has a favorable opinion of the product, and moreover that he is quite eager to share his enthusiasm with the readers.

Obviously these are not the only attitudes that can be found on the web. Other attitudes may include anticipation, sarcasm, doubt, apprehension, cynicism and even condemnation. It’s our nature to focus on the good, so we’ll spare you examples of the negative attitudes (well, I guess it’s also that we prefer to avoid any unnecessary lawsuits :) ) but the basic idea of what is meant by an underlying attitude should be clear by now.

It’s important to keep in mind that Sentiment Analysis is not severed from the basic meaning of the sentence. Rather, SA picks up on the basic meaning and further capitalizes on the cadence, the tone, the choice of words, and even the absence thereof, to build a complete picture of the message being conveyed. Note that we’ve implicitly drawn a line between some sort of “basic meaning” of a sentence, and the “ultimate intention” of the  message to be conveyed. Let’s try and be a bit more precise and explicit about this distinction.

Formal linguistic theory usually recognizes 3 levels of abstraction for natural language comprehension: Syntax, Semantics and Pragmatics (we are excluding phonology, phonetics and morphology which are irrelevant here). Simply stated, Syntax is the study of the grammatical structure of sentences, Semantics deals with how words are interpreted and how their interpretation is combined to yield the meaning of the sentence, and Pragmatics is the study of how extra-linguistic, real-world knowledge, so to speak, interacts with the basic meaning of sentences to yield the ultimate message conveyed.

So for example, syntactic theories may attempt to explain why the English sentence “I gave that to you” is fine whereas, “You gave that to I” is ungrammatical. Semantic theories may attempt to explain what the meaning of a word such as “tall” is, and how this meaning can be reconciled with seemingly problematic examples such as “I am tall” vs. “The midget is only 4 feet tall”. Pragmatics, goes one step further and attempts to explain how our knowledge of the world, circumstances, etc. play with and alter the meaning of the conveyed message. So for example, although strictly speaking the sentence: “I have 3 children”, does not formally preclude the possibility that I have more than 3, say 5 children, it would generally be considered wrong, or at least odd, for someone who indeed has 5 children to utter the original sentence: “I have 3 children”. To see how this judgment may change with circumstances, imagine Mr. Jones is being interviewed by the IRS, when he is notified by the interviewer that tax benefits are available to anyone with 3 or more children. Under these circumstance, we would probably no longer consider it odd for Mr. Jones to say “I have 3 children”, even if in fact he had 10 children.

So where does Sentiment Analysis fit in this 3-headed theoretical framework? If you’re guessing the answer lies somewhere between semantics and pragmatics, perhaps with a bit of a syntactic-twist, you’re following this introduction just fine. (If, on the other hand, you thought it was limited to the syntax, you may want to go brew yourself a fresh cup of coffee before you reread the last few paragraphs :) ).

Mirroring the theoretical image portrayed above, Natural Language Processing algorithms consist of syntactic algorithms (most notably Part Of Speech (POS) parsers and taggers), semantic algorithms (e.g. semantic rulebooks and relation extraction algorithms) and finally pragmatic algorithms (including for example, contextual disambiguating algorithms, and world knowledge look-up algorithms, used in automated translators for instance). At Digital Trowel we’ve honed our Sentiment Analysis algorithms to combine the strengths of these 3 disciplines to produce the most reliable and comprehensive understanding of the message being conveyed, reading not only the text itself, but also between the lines, so to speak.

The mathematical implementation of these algorithms is beyond the scope of this introduction, but this by no means should prevent us from taking advantage of the knowledge we’ve gained thus far to see how Sentiment Analysis techniques may harness the power of the different types of linguistic algorithms in an attempt to achieve their goal. In fact the lion’s share of the third part of this survey aims to do just that. For now, suffice it to say that one of the main reasons we at DT believe that our technology is superior has to do with our synergistic approach of integrating syntactic, semantic and pragmatic algorithms. This is why we call it Synergistic Sentiment Analysis (SSA). BTW, for those of you wondering, synergy is the term used to describe a situation where different entities cooperate advantageously for a final outcome (tx, Wikipedia!). There, you now understand yet another word in the titles above :-)

Before ending this part, let’s focus on the goals of SA, or in other words, what SA is good for. Well, in one sentence, as we already phrased it:

Extracting and discerning the underlying sentiment allows us to transform otherwise inert texts into vibrant business opportunities.

But how does this come about? I think the best way to explain is by using an example:

Every day, millions of business news articles are published on the web. Many of these articles contain both facts as well as judgments, predictions, and just plain old sentiment. Obviously, it is impossible for any one human (or even a team of a hundred people) to read all these articles, sieve and sort through them, extract the facts and discern the sentiment, let alone do this all in real time to facilitate decision-making. This is where our SA engine comes in.
In a few seconds, our Sentiment Analysis engine can run through thousands and thousands of articles, sorting them for industry, company, product, etc., extracting key facts and events, and discerning the underlying sentiment. Take the stock market for example. Within less than 10 seconds, our SA engine can scan every article mentioning any NYSE company for example, published within a specified time range. Not only are key facts and events compiled into our database, but a sentiment score is calculated and generated for each ticker, yielding a real time numeric indication of the stock’s vibe for each company on the market! Numeric scores can be translated into an array of decision making procedures, and help with consolidating trading strategies. Now if that isn’t a great business idea, I don’t know what would constitute one!

There are many other business opportunities for the SA technology, including some of which we’ve already implemented at DT such as evaluating pharmaceutical forums for client’s sentiment about drugs, as well as sports product satisfaction, but I think this is enough hype for now :)
The third and final part of this introduction to the field of SA, goes a bit deeper into the SA engine itself, and examines the innovative technology unique to Digital Trowel using real examples… Stay tuned, this is where things get really exciting :-)

Two Buddhist monks were traveling from monastery to monastery on their spiritual journey to enlightenment when they chanced upon a beautiful young woman standing by the bank of a stream.

Sorrowfully, the young woman could not cross the stream for the water had risen and it would ruin her silk robe. Without hesitating the older monk lifted the woman in his arms and carried her across, placing her gently on the opposite bank. The younger monk was taken by surprise – Buddhist monks were not supposed to touch women, let alone carry them – but decided to keep his silence, and the two proceeded on their journey for long hours without exchanging a word.

Finally at dusk the two monks arrived at their lodging and the younger monk could no longer hold his tongue. He turned to the older monk: “Tell me,” he asked, hardly concealing his reproachful tone, “Why did you carry that woman? We monks are not supposed to touch women at all!”

The older monk smiled amusedly and calmly replied: “I have let go of that woman many hours ago. Are you still carrying her in your mind?”

Now I bet you’re wondering what the heck this Zen story has to do with Natural Language Processing.

Well, it does – just read on :-)

It’s time to tell you a little more about the general extraction process we follow at DT.

You see, CARE doesn’t really work alone. Rather, it is assisted by both an HTML converter and a post processor.

The following diagram will help to illustrate the process:

Capture

As you can see CARE is “sandwiched” between the HTML Converter and the Post Processor. This blog entry will focus on the Post Processor, but first for the sake of completeness a few words about the HTML Converter:

The HTML Converter can be thought of as a “pre-processor”. It begins by downloading selected HTML code from the internet, and then performs the following tasks:

  • Cleans the HTML code leaving only the English text
  • Cleans the text of advertisements and other garbage sections
  • Classifies the text according to its content and determines what CARE rulebooks should run on each section of the text

So for example, sections describing a person’s biography will be marked and designated for the PPC (Person Position Company) and Education rulebooks, while sections of text containing addresses will be sent to the Contact Information rulebook.

Next, one or more of CARE’s rulebooks are run on the text. The text tagged by CARE is what’s fed to the Post Processor.

The Post Processor is essentially an extremely potent script that runs on CARE’s tagged output and turns it into sensible and readable information. Along the way it performs several intricate tasks, some of which are technical and some semantic in nature. In a less than perfect analogy, the Post Processor can be thought of the younger monk in our story, still holding on to all the events in their original context of which the older monk (aka CARE) has long since let go :-)

Following is a brief survey of the Post Processor’s most notable tasks:

  • Performing idiosyncratic regular expression substitutions and fixes
  • Resolving co-references and anaphoric phrases
    • For example the post processor will replace pronouns such as “he” or “she” by the relevant name of the person. Likewise if the phrase “the company” appears in an extracted relation, it will be replaced by the appropriate name of the company
  • Matching of entities and merging of relations – this is to ensure that information is not unnecessarily duplicated, and that all data is matched with the correct entities and only with them
  • Assertion and Filtering of outputted relations – this is a last validation of the information’s integrity

An example of part of the post processor’s capability is in place. Assume CARE is fed the following input sentence:

“Micha Breakstone earned his masters in math at Hebrew University (2007, cum laude), and then went on to study for his Ph.D. in cognitive sciences at Hebrew University. Subsequently he was invited to study for one year of his Ph.D at MIT”

CARE will parse the information correctly, but its output may at times look like gibberish to anyone who is not an expert engineer. Moreover, pronouns and conjunctions must be interpreted, as can be seen:

<S><PERSONDEGREE><_NAME><PERSON>Micha Breakstone</PERSON></_NAME> <_STATUS>earned</_STATUS> his <_DEGREE><TS type=”SUPER_GROUP” id=”1″/><TS type=”GROUP” id=”2″/>masters</_DEGREE> in <_SPECIALTY>math</_SPECIALTY><TE type=”GROUP” id=”2″/> at <_UNIVERSITY><TS type=”GROUP” id=”2″/>Hebrew University</_UNIVERSITY> (<_YEAR><TS type=”GROUP” id=”3″/>2007</_YEAR>, <_DISTINCTION>cum laude</_DISTINCTION><TE type=”GROUP” id=”3″/>)<TE type=”GROUP” id=”2″/><TE type=”SUPER_GROUP” id=”1″/></PERSONDEGREE>, <PERSONDEGREE><_NAME>and</_NAME> then went on to <_STATUS>study</_STATUS> for <TS type=”SUPER_GROUP” id=”1″/><TS type=”GROUP” id=”2″/>his <_DEGREE>Ph.D.</_DEGREE> in <_SPECIALTY>cognitive sciences</_SPECIALTY><TE type=”GROUP” id=”2″/> at <_UNIVERSITY>Hebrew University</_UNIVERSITY><TE type=”SUPER_GROUP” id=”1″/></PERSONDEGREE>. Subsequently <PERSONDEGREE><_NAME>he</_NAME> was invited to <_STATUS>study</_STATUS> for one year of <TS type=”SUPER_GROUP” id=”1″/><TS type=”GROUP” id=”2″/>his <_DEGREE>Ph.D</_DEGREE><TE type=”GROUP” id=”2″/> at <_UNIVERSITY>MIT</_UNIVERSITY><TE type=”SUPER_GROUP” id=”1″/></PERSONDEGREE> </S>


It is the Post Processor that comes and saves the day, tidying up, putting things in order, and all in all making sense of the myriad of unresolved anaphora and tags, to obtain a completely readable and simple extraction as follows:
<Education>
<DEGREE>masters</DEGREE>
<DISTINCTION>cum laude</DISTINCTION>
<NAME>Micha Breakstone</NAME>
<SPECIALTY>math</SPECIALTY>
<STATUS>earned</STATUS>
<UNIVERSITY>Hebrew University</UNIVERSITY>
</Education>
<Education>
<DEGREE>Ph.D.</DEGREE>
<NAME>Micha Breakstone</NAME>
<SPECIALTY>cognitive sciences</SPECIALTY>
<STATUS>study</STATUS>
<UNIVERSITY>Hebrew University</UNIVERSITY>
</Education>
<Education>
<DEGREE>Ph.D.</DEGREE>
<NAME>Micha Breakstone</NAME>
<STATUS>study</STATUS>
<UNIVERSITY>MIT</UNIVERSITY>
</Education>

<Education>

<DEGREE>masters</DEGREE>

<DISTINCTION>cum laude</DISTINCTION>

<NAME>Micha Breakstone</NAME>

<SPECIALTY>math</SPECIALTY>

<STATUS>earned</STATUS>

<UNIVERSITY>Hebrew University</UNIVERSITY>

<YEAR>2007</YEAR>

</Education>

<Education>

<DEGREE>Ph.D.</DEGREE>

<NAME>Micha Breakstone</NAME>

<SPECIALTY>cognitive sciences</SPECIALTY>

<STATUS>study</STATUS>

<UNIVERSITY>Hebrew University</UNIVERSITY>

</Education>

<Education>

<DEGREE>Ph.D.</DEGREE>

<NAME>Micha Breakstone</NAME>

<STATUS>study</STATUS>

<UNIVERSITY>MIT</UNIVERSITY>

</Education>

So, as you can see, next week I’m off to MIT :-)

In the next entries we’ll try and focus in more detail on each of the Post Processor’s tasks, discussing strategies for anaphora resolution, relation merging, etc. But meanwhile, wish me luck, continue to ask questions or comment, and in the spirit of Zen, remember to let go of any unproductive burdens you may be carrying in your mind.