Measuring Associative Networks for Quality of Analytics

June 24th, 2008
By: peter.mancini

“I personally think we developed language because of our deep inner need to complain.” – Jane Wagner

 

When it comes to most text analytical tools the only measures given are recall and precision. Some may tie them up nicely and appropriately in the f-measure which is simply the harmonic mean of those two numbers. Usually the discussion of quality ends there and you are quickly whisked off into discussions of functionality, user interface and processing speed.

As I wrote before there are many issues with measuring NLP tools. One of those issues is a lack of accredited measures to apply to them. At DRS we have at the root of our analysis something called the associative network. You can read about how these work in theory and examine a few examples of them. Generally there are a lot of problems with them revolving around their explosive need for memory and the time it takes to process them. At DRS we’ve solved a lot of those problems and find that medium sized corpora work just fine on your standard 2GB laptop. Let me briefly explain what an associative network is, as we’ve defined it.

An Associative Network is a set of related elements from a distribution of elements based on shared features to one or more elements selected from that distribution. Essentially, it is supposed to give you ranked elements that are semantically “closer” to the element(s) provided for comparison. The effectiveness of Associative Networks generally turns on (a) the selection of features of the elements in the distribution to compare and (b) the features of the element provided for comparison that are relevant in ranking. For instance, if I were to provide “fly” as a linguistic element to a set of linguistic elements in a data set, I might want “flying”, “traveling”, and “moving” as my expected association. This, of course, assumes the “sense” of “fly” is as a predicate and not as an entity (such as an insect). If the latter were the case, I might expect the associations to be “insect,” “bug,” and “fruit fly.”

The key above is to recognize features about the elements as used in the data (”fly” as predicate and “fly” as entity would have very different features if properly measured) and which features are apt for comparison (the string “fly” may be insufficient to specify the appropriate set of features to prioritize because its sense may be ambiguous without the user selecting “entity” or “predicate” as a qualifier on “fly”). The ideal Associative Network solves the traditional Natural Language Processing problems of automatic thesauri creation, clustering of semantic nearest neighbors, and brings us very close to effective, unsupervised sense disambiguation technology. Those are some ways that Digital Reasoning applies its Associative Network technology.

This technology is exciting and is very new in commercial grade applications. It is important to understand the strength and weaknesses of this tool. If you were evaluating an analytical tool it would be important for you to evaluate the accuracy of such a system and its utility. I was asked months ago to come up with a measure for Associative Networks. Since I am lazy I went and looked high and low for someone else’s measure first! Sadly there wasn’t anything out there. So I started to analyze what was coming out of our tool. Every attempt failed to produce something I would want to show because the scientific side of me rejected the processes I was developing. The problem was subjectivity. Your hard sciences like physics have unambiguous predictions from theory. The Strange Quark charge is always going to be 87 MeV by the Standard Model and as predictions go this one has always been measured this way in experimentation. When we get to softer sciences things start to get a little more ambiguous and subjective. As I stated in a prior post you have to reject subjectivity as much as possible.

So there I was staring at input terms for the associative net and the resulting list of associated terms given as output. What, therefore, defines good associations for “tree” or “Teddy Roosevelt” or “quark”? When we look at the various ways in which the associative network can be tweeked (there are many variables that control the process) and the fact that different corpora will produce different associations I began to think there was no way to measure this. At least a non-subjective way. Subjectively I can look at a list and using my own knowledge say whether the list “looked right” or not. That is hardly a measure. It certainly isn’t scientific.

Throwing all subjectivity out the window I needed to find a scientific method… I had to make predictions and prove them out through experimentation. Then it hit me. It’s not just the associations. It’s the network. There should be a way of looking at two terms and predicting a third in relationship to both. So, taking an analysts approach I looked at a document from one of my corpora and found that the USS Nimitz has 5,900 sailors and the reactor has a peak-output of 190 MW. Ok, now we are talking. The intersection of associations between USS Nimitz and Sailors should contain 5,900 and the intersection of USS Nimitz and peak-output should contain 190 MW. It seems so simple and yet it eluded me for 2 months trying to solve this problem. I am currently working on a test of this concept and the write-up of the theory. I am sure I will come across some interesting issues and along the way discover more ways of testing associative nets and other semantically related data organization tools. By making these methods open it allows them to be used widely. By making them general in use (this method could be used on a wide variety of systems, including humans) they will have much more Universal applicability. I’ll use this place as my initial forum to announce the results of the experiment and methods one can use to replicate the experiment.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

Powering up Ajax apps with Dojo

June 15th, 2008
By: bill.day

Congrats to our friend and colleague Matthew Russell on the publication of his new O’Reilly book, “Dojo: The Definitive Guide“.

Click to read reviews or buy a copy from Amazon

Watch our blog for more information from Matthew on his new book.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

The Problem of Quality Assessment of NLP Tools

May 16th, 2008
By: peter.mancini

Hello, my name is Peter Mancini and I’ve been with Digital Reasoning for over 3 years. Lately my work has been focused on developing quality metrics for our NLP/UDA tools. Below I have a sort of random discussion about the philosophy of quality assessment. It is not a thorough discussion but more a starting point for discussion. I am always interested in hearing comments about my work and in this I am particularily interested since it is new ground for me. 

The difficulties with measuring the quality of any natural language system are great. The main source of difficulty comes from the subjective nature of language. Language is also living and a speaker or author can get creative with the use of words that breaks semantic rules but still conveys meaning. I believe that the vast majority (>90%) of language breaks the standard language at least once per written page if not more on average. Further, look at spoken language taken in transcripts; people reconstruct sentences half-way through. Speakers will often not even finish sentences but trade sentence fragments back and forth and both speakers will feel they got the meaning of the dialog correctly. A decent NLP system has to deal with this since  most of the input data will typically not be peer reviewed white papers but text collected from many sources. I propose the only useful measure of the quality of NLP tools is utility: how useful is the tool at helping the wielder performing their task. Note the difference between “utility” and “correctness.” Correctness is getting the standard language right, utility is leveraging the underlying meaning of the text for further purposes.

 Utility vs. Correctness

Utility is the ability to use the output to perform a task. Correctness is the ability of the tool to register its output with a set of rules. However, as we said, language is living and often the rules are broken. Many times they are broken by accident and other times they are specifically broken to convey a special meaning. Another aspect is looking at how an entity might be used and possibly changing its canon definition with a more useful one.

Take this as an example. Your NLP processor is parsing the following text:

 “The hospital is expected to be opened on 12/02/2008.” 

In the above utterance we see at the end a string of numbers and backslashes. Most systems would classify 12/02/2008 as one cardinal number. Other systems would classify it as 3 cardinal numbers with separators. Either way is correct. However when it is displayed as the following:

 “The hospital is expected to be opened on 12 February 2008.” 

…then it becomes Cardinal Number, Proper Noun Singular and Cardinal Number. OK, correct but is it useful to be correct here? How is this presentation substantially different than the prior one other than cosmetically? In this case it would be more interesting from a programming perspective if you treat February as a type of Cardinal Number. This can give the programmer more power to distinguish dates no matter what presentation. You run into problems with the months of April, May, June and August but only because they are also names of people. However there is always a trade off. The point is, you can get more utility out of the system by identifying dates easier with one approach than another. The quality of the system therefore shouldn’t be based upon how correct it is but how the output can be leveraged by software.

 Soft vs. Hard Assessment

All quality assessments have some measure of subjectivity to them. When you look at entity extraction, for example, even with well defined concepts such as “location” you end up with ambiguities that are resolved more by opinion than objective determination.

For example consider these examples:

  1. “We traveled to Boston.”
  2. “We were there in 1999.”
  3. “He was forced into exile.”
  4. “The accusation was all in his mind.”

In example 1 we have an unambiguous location. In example 2 we have a location in time. Time is the 4th dimension but we can’t place the location geographically. In example 3 we have an abstract location. It might be possible to determine the extents of a physical location but one could be in exile in a very abstract way that does not imply a change of location. In example 4 we have a further example of a highly abstract location. You can take this to further abstractions. “They ran in the Boston Marathon” might be a location to some as it implies a well established route. In various discussion of this last example some have told me they would prefer the system to designate the location as Boston Massachusetts. As a long time resident of the area I can assure you less than a mile of the race is actually within the city limits of Boston. Also, the word Boston here is actually a modifier for Marathon, so if you accept Boston Marathon then you also have to accept other places where Boston is a modifier such as in these examples Boston Creme Pie, Boston Whaler, Boston College (actually located in Chestnut Hill), Boston Legal (only exists on TV), Douglas A-20 Boston (a WWII bomber), Boston Market (a chain of resturants) and many others.

The key in situations like this is to set your rules and be consistent when scoring based upon them. However, one has to keep the amount of subjective perspective to the absolute minimum in any analysis. Otherwise you have “open ended criteria” without a pre-determined expected outcome which means that any analysis done with these parameters will always leave you victim to too many false positives being accepted as true. You do that by setting up reasonable constraints on the concept.

Our biggest challenge today is coming up with a model for qualitative analysis of Association Networks (AN). These are terms that are associated with a given term. They can include synonyms, narrower terms, broader terms, attributes and host of other things due to semantic interaction. Here we will first be looking to evaluate quality through utility. It would be hard to measure “correctness” for two reasons. The first is: what is the definition of correctness for an association network? The second is that it takes a lot of data to create a good association network and thus having a reference set that is perfectly understood such that one can predict all of the output from the input is a prohibitively expensive operation. This second issue is more a testament to my laziness than it is to the impossibility to measure correctness but there you have it. Looking at utility we still have an issue with subjectivity. The key will be to minimize that subjectivity so that creative and irreproducible results do not plague the analysis.

My next post will be about measuring the quality of Association Networks - what I’ve tried and what I think works.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

Somebody finally said it

April 30th, 2008
By: tim.estes

I recently gave a presentation at the Nashville Technology Council’s 4th Annual Innovation Conference.

I noted in my presentation that there isn’t any real early stage innovation investing in Middle Tennessee outside of the healthcare space.  In fact, the truth is that most TN venture firms don’t even keep their money in-state:

Tennessee investments by location

Now, I’ll predict the reactions to this from the community:

  1. Some will be offended and shoot the messenger
  2. Some will point to all of the new initiatives going on to spur entrepreneurship in the area
  3. Some will agree and try to figure out ways to change it (but not have the resources to do anything about it)
  4. One or two may get involved that can make a difference and invest in new things (maybe)

Click here to read my full presentation (PDF format).  Below I’ve summarized the key takeaways.

First, the presentation wasn’t meant to be critical of any particular group. The funds that are analyzed have an obligation to their investors, not to Tennessee or particular industries. If they make good returns, they are doing their job. Enough said.

While it would be great if their money stayed in Tennessee and was used by Tennessee innovators to create new things, investing in-state is not the job of these VCs. Their job is to make money. It is true that funds in major markets (San Francisco, Boston, Seattle, DC, etc.) have a track record of making money through innovation and riskier investing. Some markets (like Nashville) make money by investing in consistent performers – even though that gets a lot less press and generates less excitement. Whatever floats someone’s IRR

Second, the opportunities laid out in my presentation (peer to peer platforms, novel content distribution and recommendation services, and healthcare informatics) are VERY ACTIVE and TIMELY opportunities. It will be a crime if we don’t have at least one or two startups in Middle Tennessee that go after each of these opportunities.

Unfortunately, that means that somewhere between $20-100M has to go to work for them to really have a chance. It doesn’t all have to come from here, just the seed and Series A money ($5-15M of the above amount). Groups such as Sequoia Capital will place growth capital in other markets outside the Silicon Valley, just not early stage.

Therefore, we need emerging Middle Tennessee companies to be funded by angels and early stage groups with critical ties to mainstream companies.  These early investors also need ties to executives with strong track records recruited from ongoing concerns.  If we can get these kinds of early investments, then big funds will have better trust in the business development acumen of Nashville-based startups and follow-on funding will become available to help these emerging companies compete on the national and international stages

Third, we need strategic involvement and leadership from major companies in the area. We need strategic investment to go into firms such as Nissan, HCA, Ingram, MCA, and AT&T. We need executives willing to team with smart tech people and put their credibility to work to expand and grow the aforementioned emerging markets. Only by bridging experience, relationships, and innovation can we transform the Middle Tennessee economy into something that will be competitive for decades to come. That means that we need major firms to see the upside in spin-out innovation and equity/licensing strategies, not just bottom lines. This should be easier for private companies to experiment with than public ones.

Clearly every person has to do what works for them. If you are a VP at MCA or a deputy CIO at Nissan or Gaylord, you’ve got security and good personal upside. But there may be an opportunity to build something new and great with the right people and idea.

Young people in Nashville trying to do innovative things aren’t getting the backing and support they need. Many are being turned down repeatedly, often without being given a reason. Many of them get frustrated and leave. I heard this directly from numerous people after my speech. These aren’t people with sour grapes. They are bright, idealistic, passionate, and talented. And they are tired of being treated like unproven fodder by the people holding the money. If Middle Tennessee isn’t going to support them, they will go somewhere where there are a hundred options instead of five.  They’ll fall in love with one of those options, break out, and become successful.  And Tennessee will miss out on an economic opportunity in the process.

My request to executives and investors is this:  If an up-and-comer presents their idea to you, please take the time to explain your thinking whether you ultimately say yes or no. They need constructive guidance and they need to connect with people that can help them grow into leadership and teach them how to monetize their ideas.

I know that time is valuable and if you aren’t going to invest, it’s easy to just toss a group over the side and move to the next one, but after 3-5 tosses, many of these entrepreneurs will move and then they won’t be around four to five years later to give you the best deal you’ve ever seen.  Make the extra effort. It will come around to your advantage and the betterment of our whole economy in the long run.

Failing to support new ideas and entrepreneurs is not going to make the people that have money now poorer in the near term. But by not supporting innovation in Middle Tennessee now, we are sending people with talent elsewhere, to places where tremendous money is being made by backing these intelligent and ambitious people.

We can and should do better.

This is all meant as free advice for a place that I love from one of the sons of its founders (I can trace my family roots here back to the Gower family). Nashville can choose to be a hub of critical information and knowledge, entertainment, and culture in America, but it has some work to do.  Early stage innovation investing inside Tennessee would be a good start.  Suggestions on how to “get there from here” are very welcome.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

Sun highlights Digital Reasoning Systems

April 4th, 2008
By: bill.day

Sun Microsystems has written and published a “Customer Snapshot” highlighting how we used Java and various development tools and methodologies to build our Interceptor Suite.

Click here to read the article.

The article highlights some of our pre-existing intelligence and government work. I also hope to get another Sun snapshot covering our new commercial efforts published as soon as we are ready to dive into the details.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

GeoLocator 2.1 released

March 27th, 2008
By: bill.day

We released GeoLocator 2.1 and I wanted to blog a short bit about the release announcement here too, so that readers can link to the press release for details.

The announcement notes:

GeoLocator™ 2.1 can process over 14,000 text files every hour, with each text file averaging around seven kilobytes each. That is the equivalent of reading War and Peace, which is almost 1500 pages long, 33 times in an hour. In fact, if you were to print all of those text files on standard, letter-size paper and set them side-by-side you could cover almost 35 acres.

Reading “War and Peace“, including extracting all of the locations in it and aligning them to geocoordinates, in less than 2 minutes. That’s fast!

Learn more from the GeoLocator page here.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

Web 3.0 and its discontents

January 31st, 2008
By: tim.estes

For my first post to our new blog, I thought I would jump into an area that is of great and timely interest: The emerging “Semantic Web” and the technologies and solutions proposed to enable it.

There has been a lot of “Web 3.0″ buzz in the last year. See for example this MIT “Technology Review” article, Business 2.0’s piece on Radar Networks, the New York Times’ Metaweb article, and John Markoff’s original Web 3.0 article from the NY Times in late 2006. The reaction in the blogsphere has been equally interesting. There appears to be a combination of believers and advocates, both Web 2.0 players who are mad at the hype being stolen and those who are skeptics. If I were to put myself in a camp, I’d have to say I’m an “optimistic skeptic”.

I believe something like this vision of Web 3.0 will play out, but it might take the market six or seven “attempters” before we find a Google of Web 3.0.

Whoever eventually gets it right must overcome at least three critical issues to make the Web 3.0 vision reality.  I’ll lay them out here.

The W3C vision of the Semantic Web is a Dead End

Semantics = Metadata + Reasoning was and is a bad idea in the context of bridging human communication and machines.

Karen Sparck Jones sums it up nicely here. As she explains rather eloquently, we really have to look at which Semantic Web we are talking about. Most parties in the space sell the value of the “high end” Semantic Web (inferential reasoning from advanced world models using a uniform lexicon with known derivation rules) but really only have technology for the “low end” Semantic Web (human tagging/machine entity extraction + crude resolution procedures for mapping/structuring like elements into classes). The truth is that building the sub-domain ontology hooks is just a way to replace business logic with a derivative of XML. The marginal gains in flexibility by this approach are a costly tradeoff for the complexity, bloat, and performance implications of pushing around such an overly expressive and poor representation of knowledge.

Most vendors in the space seem to think they can execute on a simple ontology around some patterns of activity, such as a limited ontology around people, places, and particular electronic modes of communication. This is really just reengineering the integration of Outlook/Exchange with social networking or the development of mapping rules from certain descriptive strings in Wikipedia along a priori detectable paths (such as X is a Location and is tied to this person’s entry). While there is little doubt that this does enrich the content (a la MarkLogic’s enterprise offerings), it really isn’t the Semantic Web. This doesn’t mean that there is little value in that – there is – but, it isn’t the promise of the Semantic Web.

Scalability and Complexity

No one has demonstrated deep semantic web infrastructure of any scale. This doesn’t mean that such infrastructure is impossible, just that no one has shown it working at Web-scale.

There has been talk of powerful triple- and n-tuple stores and searches over billions of tuples in millisecond time. Given what GigaSpaces and other tuple space architectures have accomplished, this isn’t as big an issue as people think. Of course, most of these numbers are out of the funded companies, not necessarily indicative of real world environments.

The problem isn’t the scale, it’s the ambiguity of the state-space. Language and the agents that use it are utterly magical in how easily they deal with ambiguity that defies simple traversal of a limited graph. This is one reason many bright people have speculated that the brain must have some quantum properties in how it makes inferences across such a large number of potential states.

To see how hard the combinatorics of this are, compare it with work in n-gram models. People were still receiving PhDs for dissertations on 5-gram models as of a few years ago. While some may argue that the fixed semantics of a rule-base/ontology don’t lead to anything in this kind of state space, I’d challenge them to deal with a large, dynamic lexicon and more than trivial top-level ontological classes.

The bottom line is that a schematic representation is likely only going to be able to handle traversal along very rigid paths that are mapped to very specific use cases. In other words, if you try to make business logic that is remotely as dynamic as human semantics in language, you will have a problem representing them correctly. Worse yet, current representations are inherently unscalable.

There is promising work in this area looking at semantics as a superposition of states with runtime collapse into the appropriate sense (see Maya Design). Most systems that try to do this the “old fashioned way” take around a second to process a sentence on modest hardware. And they are still limited to modest global semantics.

Here’s the key point:  Without proof of scale, it’s just a cute demo.

Magic is a lot easier in a controlled environment under unrealistically small data constraints. It’s just a looser way of overfitting. The US Intelligence Community has already been through this and is on the other side of investing a whole lot more money than Sand Hill Road in getting this to work. Upon looking into this a while back, former NSA Chief Scientist Eric Haseltine was summarily unimpressed.

Thankfully, some people are doing a good job of setting expectations honestly for what could be done right now (see Nova’s comments in the Business 2.0 article mentioned at the beginning of this post). Those people have a far better prospect of creating value and loyalty in a future user base.

We don’t need a Web 3.0 version of Google: Just Say NO to Semantic Silos!

The Web 3.0 vision should not be realized through any one Web site. Instead we should work to realize it using diverse software that sits all over, the distributed hybrid of the current grid architecture of the Amazons, Suns, and Google and the BitTorrent model of distributed tracking and swarming of intelligence.

The alternative, implementing the current hosted model of data for semantics, would be very dangerous. And yet that is the espoused goal of the current market leader.

What could be more Orwellian than having to go to an outside server to determine what the accurate sense of the word “tax” or “war” is? That prospect should scare you. Semantic silos have much larger consequences than our current lock-in to a given social network or hosting for a video. Should such silos develop, it will be tantamount to auctioning off the truth.

The moral answer to this is to build the Semantic Web using a new type of software, not the same old centralized uber-service. And that is the answer we are pursuing and look forward to discussing with you.

Please contact us with your thoughts and subscribe to this blog to join the discussion.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

Welcome to our blog

January 24th, 2008
By: bill.day

Today we are launching our new Digital Reasoning Systems blog.
Thanks for coming and please let us know what you think of the blog (or anything else about Digital Reasoning Systems) via our feedback form (click here).

We plan to use this blog to:

  1. Explain our vision and company
  2. Enable more interactivity with partners, customers, and developers
  3. Syndicate our latest news, product releases, and technology updates

Subscribe to our feed for the latest from us, and please contact us with any questions or suggestions you may have for improving our site.  Thanks again, and welcome!


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

The eDiscovery market

October 22nd, 2007
By: bill.day

The Nashville Business Journal published a piece last week on our plans in the electronic discovery, aka eDiscovery, market. Read the article here.

As Tim Estes, Digital Reasoning Systems’ CEO, notes in a quote in the article:

Search solves the problem for the user who knows what they’re looking for and generally knows the answer is out there. This is all about how do you really read, learn and understand data without knowing everything you need to understand about it in advance.

This is yet another way in which we are unleashing the meaning inherent in human language. Watch this blog and DigitalReasoning.com for more.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank

Geolocation for the masses

September 11th, 2007
By: bill.day


It is no accident that we are announcing GeoLocator™ 2.0 today, on the sixth anniversary of the September 11th attacks.11 September 2001 crystalized Digital Reasoning Systems’ vision into a mission. Because we had already been working on discerning meaning inherent in unstructured data before the attacks, we were able to deliver a functional proof of concept of GeoLocator™ to the US Army National Ground Intelligence Center within a few months afterwards.Our solution delivered superior accuracy and a more flexible architecture at a fraction of the cost of our competitors.The same powerful technology used by intelligence professionals is now available to you.Today we deliver GeoLocator™ 2.0 for everyone, government and commercial customers alike. GeoLocator™ 2.0 unleashes accurate, flexible, cross-platform geolocation for commercial applications. We have enabled straightforward integration into existing software systems using Java or Web Services APIs. We have also made significant further improvements in performance, administration, and analysis flexibility. And we are still far, far cheaper than our competitors.

GeoLocator™ 2.0 provides:

  • Better performance (at least a 200% improvement over previous versions)
  • Easier installation of the application and gazetteer (location database) versus competitive products
  • Ability for customers to input their own locations as well as modify existing locations in the gazetteer
  • A GUI for interactive administration and analysis as well as a command line interface for batch processing and scriptable control
  • Built-in capability to export aligned locations into Google Earth, NASA World Wind, CSV, and other XML-based formats via standard XSLT transforms
  • A variety of text markup features (see datasheet for more details)
  • Web Services and Java API interfaces enabling the integration of GeoLocator™ functions into other applications
  • Support for customer-specified metadata field tags that can be used in the location disambiguation process
  • Enhanced application status and error reporting including configurable log file support

Access the datasheet for all the details including more information on capabilities, system requirements, and contacting Digital Reasoning Systems to evaluate GeoLocator™. Click here to read the GeoLocator™ datasheet.


Digg del.icio.us Reddit Technorati Ma.gnolia Netscape NewsVine StumbleUpon TailRank