During Bridget's defense, Rich Maclin raised the issue of possibly using
ROC curves to evaluate problems where you get a ranked list of items. This
is what we have in collocation identification, where you have a list of
nrams that are scored, and you want to have the "best" bigrams (the ones
that are collocations) with the highest scores, and the not good ones
with lower scores.
I did a bit of reading and thinking, and I have concluded that I really
like ROC curves. Here's what I know so far. This is based on the
collocation identification problem, but could be applied to any problem
where you have a scored or ranked list of outcomes.
An ROC curve is an xy plot with a single line. The y axis shows you the
percentage of true positives (those are the bigrams that you identified
as collocations that are "truly" considered to be collocations in your
gold standard) and the x axis shows you the false positives (these would
be the bigrams that you thought were collocations, but aren't in the gold
standard). These are both represented as percentages, and the x and
y axes both go from 0 to 100%.
Now, what do you plot? You take your list of bigrams, identified by your
measure, and you keep a running total of the true and false positives.
You go all the way through your output, from top to bottom, and then
you go back and compute the percentages associated with each of those
true and false positive values.
Let's suppose we have the following list of bigrams from your program. We
would have true and false positive values for each of these (as a running
total from top to bottom) as follows:
Gold TP FP
New York Y 1 0
a dog N 1 1
cat hair Y 2 1
my friend N 2 2
long hair Y 3 2
Here "New York", "cat hair", and "long hair" are considered to be
collocations in the gold standard, and "a dog" and "my friend" are not.
That's indicated by the column Gold above.
The TP and FP values are the running totals of true and false positives.
Since New York is really a collocation (indicated by Gold Y) then the
count of TP is incremented, and FP is not. You see that the sum of TP and
FP is always equal to the number of bigrams you have seen thus far.
Now, let's look at the percentages you would end up plotting.
Gold TP FP y x
New York Y 1 0 1/3 0/2 .33 00
a dog N 1 1 1/3 1/2 .33 .50
cat hair Y 2 1 2/3 1/2 .66 .50
my friend N 2 2 2/3 2/2 .66 1.00
long hair Y 3 2 3/3 2/2 1.00 1.00
So what you can see here is interesting. There is a race to the top
really, between the true positives and the false positives, and you
can see how that race comes out by looking at the curve. If the curve is
like a hump on a camel (sort of) then it means that you had more true
positives early, and if it's like a valley (sort of) that means you had
more false positives.
Also, note that both values always reach 100%, so you just need to know
how many of the bigrams are in the gold standard and which are not.
Now, this is the best case:
Gold TP FP y x
New York Y 1 0 1/3 0/2 .33 00
cat hair Y 2 0 2/3 0/2 .66 .00
long hair Y 3 0 3/3 0/2 1.00 .00
a dog N 3 1 3/3 1/2 1.00 .50
my friend N 3 2 3/3 2/2 1.00 1.00
And here's the worst case:
Gold TP FP y x
a dog N 0 1 0/3 1/2 .00 .50
my friend N 0 2 0/3 2/2 .00 1.00
New York Y 1 2 1/3 2/2 .33 1.00
cat hair Y 2 2 2/3 2/2 .66 1.00
long hair Y 3 2 3/3 2/2 1.00 1.00
If you sketch these three plots out, you can see that they really
show (very nicely) the different nature of these results.
You can see in the best case, we race to the top of the y axis before we
go anywhere on the x, and in the case of the worst case, we shoot out
along the x axis before we rise on the y at all.
This is a very nice way to deal with evaluating a ranked or sorted
list of items. I'm glad Rich mentioned it. I have heard of ROC curves
for a while now, but never got around to checking them out.
Note, my understanding comes from the book Data Mining, by Witten and
Frank. This is a great book for understanding Machine Learning, and I
always recommend it very highly.
Now that I have potentially exposed my ignorance, do any of you out there
know about ROC curves? Can you correct me or elaborate?
Thanks,
Ted
--
Ted Pedersen
http://www.d.umn.edu/~tpederse
------------------------ Yahoo! Groups Sponsor --------------------~-->
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/x3XolB/TM
--------------------------------------------------------------------~->
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/nlpatumd/
<*> To unsubscribe from this group, send an email to:
[EMAIL PROTECTED]
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
