Winds of Change

The Demise of the Language Barrier

As autumn briskly descends on New England I find myself admiring nature’s capacity to silently transmute subtle changes into full-fledged displays of majestic beauty. A leaf here, a leaf there… They practically go unnoticed for several weeks – and then suddenly one morning you wake up and look through the window, amazed to see that nearly all the trees on the street are ablaze.

Reflecting back on this past year, I can’t help but draw the analogy to Digital Trowel’s own progress. It seems unbelievable that only one year ago we were a small team of 7 engineers crowded together in 2 small rooms, with not much more than an untested NLP platform and a vision. As the weeks passed by, we added an engineer here, a linguist and a mathematician there, and suddenly we are a mature, full-fledged commercial company, with over 40 developers, selling products and data, ablaze with a proven breakthrough NLP technology in hand.

But we’re still hungry! And our team of scientists is cooking up a storm

We’ve just recently hired another mathematician and a computer scientist, so we now have 5 PhD level scientists on our R&D team. We strongly emphasize the research aspect of the business, because we know that being at the top is a very fragile state. So while we’re very proud to be the first company to produce consistent commercial results with over 90% accuracy and recall across multiple semantic fields, we realize there are still many challenges to be met, and we’re determined to be the first to meet them.

While I’m not yet at liberty to divulge the full extent of our newest developments, I am able to give you a taste of some of the advances we’ve made.

One of the most exciting projects we’re looking into is a multi-lingual text-mining platform codenamed SNUG for Semantically Negotiated Universal Grammar. Admittedly, I don’t think this is exactly what Noam Chomsky had in mind when he first proposed his theory of Universal Grammar, but it may not be too far off. Let me explain:

Linguists use the term Universal Grammar (UG) to denote a theory according to which all humans possess an inherent “hard-wired” capability to acquire a language. It is this linguistic “hardware” we’re all born with that allows children to learn the grammar of a language even when the linguistic data available to them is insufficient.

A quick example is in order. A child born in the U.S.A must learn to form questions out of assertions in English. He may, for example, hear the assertion:

“My sister is pregnant.”

 

And over time infer that the proper interrogative form of this statement is:

“Is my sister pregnant?”

He may then (subconsciously) form a rule of grammar in his mind, whereby questions in English are formed by moving the first auxiliary verb to the beginning of the sentence. We would then expect that children faced with an assertion such as:

“My sister who is pregnant will be blessed with happiness.”

 

Would form the incorrect question:

* “Is my sister who pregnant will be blessed with happiness?”

Interestingly enough – they don’t! Only the correct form is acquired by children:

“Will my sister who is pregnant be blessed with happiness?”   (Of course she will!)

The claim (asserted by UG supporters) is that children simply don’t encounter enough sentences as complicated as the one above to make a learned choice. So how do they do it? Well, simply put – they are born knowing. More accurately, they’re born with a set of rules that are triggered and activated in a certain way once they are exposed to sentences in their language.

Of course, things are far more complicated than these simplistic examples, and many questions immediately arise. How, for example, is it that other languages, German and French for instance, form questions by placing the main verb at the beginning of the sentence? For example:

 

French: Parlez-vous anglais?

German: Sprechen Sie Englisch?

Both mean: Do you speak English?

But a literal translation would be the ungrammatical: * Speak you English?

So, obviously, the theory must be significantly more complex. But don’t worry, that concludes today’s lesson in linguistics 101 . We now return to what got us here in the first place – our new multi-lingual text-mining platform SNUG (We thought it’s kind of cute to build SNUG using CARE ).

So, first things first: No – we’re not out there to decipher the way our mind processes languages, but – Yes we are out there to create a platform that will enable us to process and mine texts in any language.

For us humans, it’s quite hard to fathom learning a new language in say, a week. But for our system that’s actually an achievable feat. In order for us to effectively extract data from free text in a new language, we need to accomplish two things. First, we need to teach our system this new language. Well not exactly the language itself, but more like the statistical distribution of words in this new language. We do this using an automatic training process, by which our system runs through huge text corpora, producing a statistical model of the language, which is further refined every time we train the system.

The second task is translating our semantic rulebooks. Here is where our linguists come into play. Since our rulebooks are basically comprised of highly sophisticated weighted Context-Free Grammars, their translation amounts to a structure-preserving function of semantic rules (a semantic homomorphism). This function can be thought of as taking an English semantic-driven grammar as input and transmuting it into a semantic-driven grammar for a different language. Though languages vary considerably in their actual spoken grammar, they tend to convey events and factual information in a surprisingly similar manner (or rather, the structure of the required semantic rules is quite similar).

Most Central European languages share so many common qualities with English, that many of the rules can be translated verbatim. Some of the challenges arise when translating rulebooks to languages with a word order that significantly differs from the English word order (e.g. German, not to mention Subject-Object-Verb languages such as Japanese, Hindi and Turkish). Languages with a high level of agreement inflection such as French, Italian and Spanish are usually easier to parse as well, though high inflection agreement often incurs the omitting of overt pronouns. So for example “I eat” in Italian will simply be “mangio”. This turns out to be quite problematic for issues of anaphora resolution.

Every new language poses a new and exciting challenge, but crucially, it does not require us to rewrite the code. All we need is a few large text corpora, an expert linguist, a savvy rulebook writer, and a week or two of intensive work, and our system will learn to “speak” a new language. If only it were so simple for people to learn…

Well I guess that’s enough for this post. I hope you’ve enjoyed this quick “intro to linguistics”, and are as excited as I am by the prospect of text-mining – free of language barriers. Stay tuned for more new and interesting features in my next entry.

Meanwhile, wherever you are, I hope you have an autumn as beautiful as the one I am having in Boston. Even more importantly, I hope you take the time to appreciate the beauty of change all around – spoken without any words.

New Year’s Blessings

On the occasion of the new Hebrew year, I thought I’d make this entry a bit lighter than usual and present blessings for the new year in the spirit of NLP, spiced up with some advice, so here goes:

When setting the goals for extraction results, try to find the optimal balance between recall and precision. Remember: Aiming high is good, just make sure there’s an easy way down!

Do not attempt to debug a rulebook for more than 24 hours straight. We’ve been there. We’ve done that. If you think you’re stuck now, you still haven’t seen nada!

Remember the chain of  language processing from last entry? First comes The HTML converter – it hands down the info to CARE, which does all the hard work and in turn passes the parsed relations to the Post Processor so that it can rest on its laurels

Perfect “Anaphora Resolution” is a myth. You can try. For a while, you may even believe you’ve done it. Our prediction: In the end the bubble will burst. Or you’ll go crazy trying to solve all the problems. Or both.

Make sure that all the crucial information that comes in as input, goes out as output

Remember the engineer that didn’t take our advice and corrected extraction rules through the night?

Just like life itself, retrieving the ultimate extractions for a given relation may be an extremely tedious and laborious task. Lighten up, add some spice. Make fun of yourself!

Do everything you do with love and CARE!

But remember that if you’re not enjoying it, you’re probably not doing it right!

Here from Cambridge, MA, wishing you all a wonderful year full of wonderful experiences, CARE-ing, happiness and love!

Zen and the Art of Post Processing

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:

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.

It’s About Time!

First of all I want to thank you all for your emails and comments. Part of the idea behind this blog is to establish an active community. Your questions are already challenging us to create even better rulebooks for information extraction… so keep the ideas and challenges coming!

Speaking of challenges, today I’ll present a few amusing (yet formidable) examples we encountered while writing our Financial Events rulebook.

Unlike the Person Position Company (PPC) and Education rulebooks which aim to extract biographical information, the Financial Events rulebook aims to capture any and all events pertaining to different companies and organizations. As such, it is action-oriented, and must therefore  be sensitive to complex verb constructions such as negation, modalities (e.g. could, would, may) and speculative tones (e.g. “it is rumored that…”), as well as idiom usage and subjective interpretations of the events.

Consider the following examples we’ve recently encountered:

AOL to buy Time Warner in historic merger – CNET News

Yahoo stalling tactics buy time with Microsoft

Now Is the Time to Buy Yahoo!

Although the word “time” is used quite differently in each of the above examples, our rulebook is able to ascertain that only the first sentence denotes an acquisition event, yielding the following welcome result:

<Acquisition>

<ACQUIRER>AOL</ACQUIRER>

<ACQUIRED>Time Warner</ACQUIRED>

<ACTION_ACQUISITION>to buy</ACTION_ACQUISITION>

<SOURCE>CNET News</SOURCE>

</Acquisition>

How are we able to achieve this? The secret lies in the synergetic interplay of our NER (Named Entity Recognition) component with the semantic rules handcrafted by our linguistic engineers, and the inherent competition between possible parses.

In the first sentence, Time Warner is identified as an organization by the NER, and thus any interpretation tagging it as such will receive a relatively greater weight. On the other hand, in the second and third sentences, “time” is identified as a regular word by the NER, so that interpretations consistent with this (vacuous) tagging are preferred.

Still, you may wonder, why isn’t Microsoft identified as an organization in the second sentence, leading to the (wrong) conclusion that Yahoo is buying Microsoft? The answer is that Microsoft is, in fact, identified as an organization, but the idiom “to buy time” competes with inflections of the verb “to buy”, receiving a greater weight which renders the “acquisition-less” parsing the most rewarding one.

In fact, this is only the tip of the iceberg. Deciphering the subtleties, connotations, and “between the lines” interpretations of newsfeeds is one of the greatest challenges we’ve taken upon ourselves. We’ve recently developed a whole new set of rulebooks to extract – or if you will – divine, the sentiment attributed to sentences, paragraphs and articles.

Running our Sentiment Analysis (SA) engine on financial sites, we are able to automatically generate a sentiment score for each company mentioned. Likewise, applying the SA engine to health forums, we are able to ascertain how satisfied patients are with a certain drug or treatment. The possibilities are nearly endless, but the SA topic deserves an entry (or several) of its own, so enough for now

I’ll wrap up this entry with an amusing example:

A few weeks ago while testing our Financial Events rulebook, one of our engineers encountered the following suspicious extraction:

<Acquisition>

<ACQUIRER>Goldman Sachs</ACQUIRER>

<ACQUIRED>Treasury Department</ACQUIRED>

<ACTION_ACQUISITION>to Acquire</ACTION_ACQUISITION>

<ACTION_STATUS>in Talks</ACTION_STATUS>

</Acquisition>

Preparing himself for a new bout of debugging, our engineer turned to the source text from which the event was extracted.

You may want to have a look at the source yourself.

Quoting the article, it indeed turns out that “Goldman Sachs [is] in Talks to Acquire Treasury Department”.

It seems even Google Finance accepts satire from time to time (I especially enjoyed the description of the festivities: “Goldman recently celebrated record earnings by roasting a suckling pig over a bonfire of hundred-dollar bills”). Naturally, we took immediate action and hired two comedians to join our algorithms team in hope of improving CARE’s sense of humor

____________

On a more personal note, I just landed in the USA, and am very excited about beginning my studies at MIT in a few weeks… Meanwhile, please continue with your comments and questions. Till soon…

Yes We CARE!

It’s been nearly a month since the last post – so there’s much to catch up on! In this entry I’ll explain a little more about what makes CARE so special, and provide examples to prove it.

The beauty of CARE is that it combines several cutting-edge technologies to achieve its ultimate goal:

Extracting complex relations from free text with a precision and recall rate of over 90%.

In the professional lingo, CARE is what is known as a hybrid system. On the one hand, it employs supervised machine learning for Named Entity Recognition, and on the other, it involves Knowledge Engineering-based rules. 

If you’re not an expert you’re probably a bit lost, so let me explain .

CARE is comprised of 2 basic components. The first component uses automated algorithms to learn the semantics of specific words and phrases according to their statistical distributions in text corpora. This is referred to as the Named Entity Recognition (NER) module. The primary NER module is currently trained to identify salient entity categories such as: People, Organizations, Locations, Products, etc. However, the NER can essentially be trained to identify any category of entities.

On top of the NER comes the second component, which comprises a set of relation-specific linguistic rules. These rules are written by a team of engineers and linguists. Together, this collection of rules form what is known as a grammar. Formally, CARE uses what is called a Context-Free Grammar (CFG), which is a term used to indicate that rules are independent of the context in which they occur. More precisely, we use a Weighted CFG, which means that each rule is assigned a weight, so that rules may compete with each other, with the highest weighted rule prevailing. It is this Weighted CFG component that allows CARE to decipher and extract higher-level relations from within the text.

The real beauty of this, though, is that the interface between the two components described above is flexible. Now, what could I possibly mean by a flexible interface? Well, put simply, it means that the two components interact. Instead of two severed immutable components, we have the two components running in parallel and modifying each other’s output, until an optimal result for both modules is obtained.  As it turns out, it is exactly this synergetic cooperation between the automated machine learning module and the semantically engineered grammar that gives CARE its winning edge.

Well, enough theory (at least for this entry ) let’s talk facts!

Recently, we ran an experiment to test our “Person-Position-Company” relation rulebook (PPC), on biography pages we selected randomly from the Internet. Before sharing the results with you, I’ll explain the task at hand and give a few examples so that you can get a feel of how complex it is.

Say CARE receives the following paragraph as input: 

Mr. Alan H. Fishman is the Chief Executive Officer and Director at Washington Mutual Inc. Previously, he was President and Chief Executive Officer at Independence Community Bank Corp. Prior to that, he served as the President and Chief Executive Officer at ContiFinancial Corp. from July 1999 to December 2000. Mr. Fishman is also the Founder and was the Managing Partner at Columbia Financial Partners LP, from 1992 to March 2001. 

How many different relations should be extracted from this paragraph? As a quick exercise (or rather task in occupational therapy) try “extracting” all the relevant information. During this time, I will leisurely run CARE (honestly, this is precisely what I am doing at the time I write these lines) to obtain the following results within milliseconds: 

<document>
−
<PPC>
<EDATE>CURRENT</EDATE>
<EMPLOYER>Washington Mutual Inc.</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>Chief Executive Officer</POSITION>
</PPC>
−
<PPC>
<EDATE>CURRENT</EDATE>
<EMPLOYER>Washington Mutual Inc.</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>Director</POSITION>
</PPC>
−
<PPC>
<EDATE>PAST</EDATE>
<EMPLOYER>Independence Community Bank Corp.</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>President</POSITION>
</PPC>
−
<PPC>
<EDATE>PAST</EDATE>
<EMPLOYER>Independence Community Bank Corp.</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>Chief Executive Officer</POSITION>
</PPC>
−
<PPC>
<EDATE>December 2000</EDATE>
<EMPLOYER>ContiFinancial Corp.</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>President</POSITION>
<SDATE>July 1999</SDATE>
</PPC>
−
<PPC>
<EDATE>December 2000</EDATE>
<EMPLOYER>ContiFinancial Corp.</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>Chief Executive Officer</POSITION>
<SDATE>July 1999</SDATE>
</PPC>
−
<PPC>
<EDATE>CURRENT</EDATE>
<EMPLOYER>Columbia Financial Partners LP</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>Founder</POSITION>
</PPC>
−
<PPC>
<EDATE>March 2001</EDATE>
<EMPLOYER>Columbia Financial Partners LP</EMPLOYER>
<NAME>Mr. Alan H. Fishman; Mr. Fishman</NAME>
<POSITION>Managing Partner</POSITION>
<SDATE>1992</SDATE>
</PPC>
</document>

The above results are given in our post-processor’s XML-format with the outermost tag indicating the relation caught (here PPC) and the inner tags indicating the different slots and entities (all are quite self explanatory, except perhaps for EDATE which stands for “End Date” and SDATE, which stands, well, for “Start Date” :-) ).

You can check for yourselves to see that we got all the relations (100% Recall) and that we got all of them right (100% Precision).

Pretty impressive, don’t you think? Well that’s nothing! Imagine the results when we run this same automatic extraction over hundreds-of-thousands of biographies within minutes. Just think of the endless applications for such refined and structured data in numbers that really have no limit…

Before we get to the punch-line (the actual recall and precision results we obtained) I’ll add a few technical details, for those so inclined (non-experts can skip the next paragraphJ).

In our experiment we used a CRF-based NER model which was trained on the CoNLL 2003 shared task data. The test set was comprised of 10 web pages, containing 113 instances of the PPC relation. We ran CARE (with the PPC rulebook) over these pages and then manually checked the results. We used the following definitions to present the statistics for the results:

Recall is the number of True Positive catches divided by the total number of True Instances (=113).

Precision is the number of True Positive catches divided by the sum of the True Positive catches and the False Positive catches.

And finally (drums, please…) for the final results:

In the experiment described above, we obtained Recall of 94.8% and Precision of 96.0%

So, now I have only 3 words left for you:

Yes we CARE!

__________________________________________________

In the next few weeks I’ll be presenting further examples of relation extraction on an ever-increasing level of complexity. If you have questions, comments or challenging ideas please drop me a note.

Also, if you’d like to see me extract a specific type of relation – don’t hesitate to write me. I’ll be back shortly with more exciting challenges and results – so be sure to stay posted!