Being Accurate when having an Agenda

I was reading a report a few days back, and one of the sentences was:

"we observed that 50% of the women get salaries lower than the median salary of men"

Just think of alternative formulations of the same sentence. I will refrain from commenting further.

Evaluating Information Extraction using xROC Curves

Suppose that you have an information extraction system, which behaves like a blackbox. The box takes as input a document and gives in the output a set of relation tuples. For example, the information extraction system may process newspaper articles and identify mergers and acquisitions (Company1 bought Company2), or management succession events (Person1 succeeds Person2 in the the CEO position), and so on.

As expected, such systems are inherently noisy and generate imperfect output. Sometimes they miss tuples that appear in the documents and sometimes they generate spurious tuples. One of the important questions is how to evaluate such a system objectively and with the minimum amount of effort.

A common evaluation strategy is to use precision-recall curves to show how the system behaves under different settings. The precision of the output is defined as the number of correct tuples in the output over the total number of generated tuples; recall is defined as the as the number of correct tuples in the output over the total number of correct tuples that can be extracted from the documents.

Unfortunately, precision is problematic due to its dependence on the input class distribution, as the following example illustrates:

• Example: Consider an extraction system E that generates a table of companies and their headquarters locations, Headquarters(Company, Location) from news articles in The New York TimesBusiness'' and the "Sports'' section. The "Business'' documents contain many tuples for the target relation, while "Sports'' documents do not contain any. The information extraction system works well, but occasionally extracts spurious tuples from some documents, independently of their topic. If the test set contains a large number of "Sports'' documents then the extraction system will also generate a large number of incorrect tuples from these "bad'' documents, bringing down the precision of the output. Actually, the more "Sports'' documents in the test set, the worse the reported precision, even though the underlying extraction system remains the same. Notice, though, that the recall is not affected by the document distribution in the test set and remains constant, independently of the number of "Sports" documents in the test set.

The fact that precision depends on the distribution of good and bad documents in the test set is well-known in machine learning, from the task of classifier evaluation. To evaluate classifiers, it is preferable to use ROC curves, which are independent of the class distribution in the test set. The ROC curves summarize graphically the tradeoffs between the different types of errors. When characterizing a binary decision process with ROC curves, we plot the true positive rate (the fraction of true positives correctly classified as positives, i.e., recall) as the ordinate, and the false positive rate (the fraction of true negatives incorrectly classified as positives) as the abscissa.

The standard application of ROC curves for information extraction is unfortunately problematic, for two reasons.

First reason: We typically do not know what a "true negative" is. Unlike document classification, a "bad tuple" does not exist apriori in a document. It only exists because the extraction system can extract it.

• Solution 1: One way to overcome this problem is to measure the number of all bad tuples that can be extracted from a document using all possible settings and all available extraction systems. Then, we can use this number as the normalizing factor to define the false positive rate. This solution works when dealing with a static set of extraction systems. Alas, the definition of false positive rate becomes unstable if we introduce later another system (or another setting) that generates previously unseen noisy tuples; this changes the number of all bad tuples, which serves as the normalizing constant, and forces recomputation of all false positive rates.
• Solution 2: Another way to avoid this problem is by having an un-normalized x-axis (abscissa). Instead of having the false positive rate, we can have the average number of bad tuples generated. In this case, the new curve is called the "Free Response Operating Characteristic" (FROC) curve. Such techniques are widely used in radiology to evaluate the performance of systems that detect nodules in MRI and CAT scans. (A nodule refers to a small aggregation of cells, indicative of a disease.) A problem with this approach is the lack of a "probabilistic" interpretation of the x-axis; the probabilistic interpretation can be convenient when analyzing/integrating the extraction system as part of of a bigger system, and we are not simply trying to measure its performance in a vacuum.
  

Second reason: It is too expensive to know all the "true positives". You may have noticed that recall is the y-axis in the ROC/FROC curves. Unfortunately, computing recall is a rather expensive task. If we want to be correct, we need to have annotators read a document and infer which tuples can be extracted from each document; the number of all good tuples will be used as the normalizing constant to compute the recall of each extraction system. This is an expensive task, especially compared to the computation of precision or compared to the computation of the false positive rate. To compute the false positives we need only to evaluate the extracted tuples, a presumably much easier task than reading a lengthy document.

• Solution 1: We can play the same trick as above, to avoid the problem of reading/annotating the documents. We process each document multiple times, using all possible settings and all possible extraction systems. The union of the extracted tuples can be then validated to identify the set of all correct tuples. As in the case of true negatives, though, the definition becomes unstable if we have a dynamic set of extraction systems that can identify more good tuples at some point in the future, forcing a re-calculation of recall metrics for all systems.
• Solution 2: We can also have an un-normalized y-axis. For instance, we can have as the ordinate (y-axis) the average number of good tuples extracted for each document. (I have not seen anything like the FROC curves that will leave the true positive rate unnormalized, though.) The downside is that by leaving recall unnormalized, the values now depend on the distribution of good and bad documents in the input: the more bad documents with no good tuples in the test set, the lower the unnormalized value will be. Therefore, this definition seems to go against the spirit of ROC curves.
  

I am not aware of any alternative definitions of the ROC curves that do not have the problems of the solutions that I described above. If you have any ideas or pointers, post it in the comments.

Blending Mind Maps with Wikipedia

Following up on the topic, of how to use wikis to organize research literature about a given topic.

I have been thinking about the idea of keeping wikis to keep track of the state-of-the-art in any field. One way to organize the literature is to transform an existing survey article into a wiki and let people edit at-will (e.g., see this article on duplicate record detection). Another alternative is to keep a set of tables in a wiki, which summarize the results of a paper in a single line (e.g., see here and here for NLP-related tasks).

A problem with both approaches is the lack of a network that will allow people to mark and annotate the relations across different papers. The idea of using CMapTools (http://cmap.ihmc.us/) was interesting but I could not manage to install the software to see how it really works.

Today, I run into WikiMindMap, a web-based service that uses the wiki structure to convert Wikipedia articles into a mind map. The heuristics that it uses are rather basic but one could use this tool to organize the literature in a wiki (having the advantage of collaboration), and still have all the advantages of a visual tool that can show connections across entities. See for example the wikified article, mentioned above, transformed into a mind map.

Data Cleaning Service

Often, I get questions from colleagues and students on how to match "dirty" data, i.e., string database entries that are similar but not exactly identical. Although there is a very significant amount of research literature, there are not that many software packages available for free. For this reason, I decided to implement the technique that we described in our WWW2003 paper, and make it available on the web for anyone to use:

http://hyperion.stern.nyu.edu/SMWebSite/Default.aspx

So, now if you have two lists of names that need to be matched you can try this service. It works well for small datasets with a few thousands entries in each. I am pretty sure that it can scale to much bigger datasets, but it will take some time for the service to finish the job. One of the neat features of the service is that you can submit the job, keep the id of the submitted job, and come back to retrieve the results later.

If you have any ideas, or any bug reports, feel free to contact me.

Wikipedia-based Web Services

We have launched a beta version of some web services that use Wikipedia data for named entity extraction, for term identification, and for document expansion. You can take a look and try the services at:

http://wikinet.stern.nyu.edu/Wikinet/Wikinet.aspx

We are actively working on this, so if you see a bug or some unexpected behavior, feel free to drop me an email.