[223002390010] |<title>Examples of “Futility of Commenting Code”</title>
[223002390020] |Continuing on from the previous blog entry, <a>The Futility of Commenting Code</a>, I’d like to address the <a>dissenting comment of Sandman</a>, who claims to have only seen the kind of caricature comments I made up in posts about commenting.
[223002390030] |Well, here goes reality. 
[223002390040] |<h3>A Real Example</h3>
[223002390050] |Consider the following real example, which I chose because I knew the source for Apache projects was available online, and suspecting Apache Commons would be less heavily checked than more popular projects.
[223002390060] |I dove into the e-mail package, because it’s the first one I actually use.
[223002390070] |I found this example right away:
[223002390080] |<li><a>source for <code>org.apache.commons.mail.ByteArrayDataSource</code></a> (revision 782475) 
[223002390090] |pieces of which I repeat here:
[223002390100] |I wasn’t talking about API comments, but these display the same problem.
[223002390110] |This public constructor is documented with “Create a datasource from a String”, but in fact, there are two string parameters, both documented as “a String”.
[223002390120] |That’s what the delcaration says, so this is exactly the kind of redundant comment I was talking about. 
[223002390130] |Next, consider the one code comment.
[223002390140] |It starts on the wrong foot, with “Assumption that the string contains only ASCII characters!”.
[223002390150] |If you look at the method call, <code>data.getBytes("iso-8859-1")</code>, you’ll see that it’s actually more general than documented, in that it’ll work for any ISO-8859-1 characters (aka Latin1).
[223002390160] |The second part of the comment, “Else just pass in a charset into this constructor and use it in getBytes()” makes no sense, because the bytes are hard coded, and there is no char encoding argument to the constructor. 
[223002390170] |Furthermore, the catch block (with its throw) should just be removed.
[223002390180] |It’s catching an <code>UnsupportedEncodingException</code>, which extends <code>IOException</code>, then throwing a fresh <code>IOException</code>.
[223002390190] |It should just be removed, at which point an unsupported encoding throws an unsupported encoding exception; you don’t even need to change the signature, because unsupported encoding exceptions are kinds of I/O exceptions.
[223002390200] |There are two problems with the code as is. First, the the IOException reports an unhelpful message; the unsupported encoding exception has the info on what went wrong in its message.
[223002390210] |Second, it’s returning a more general type, making it harder for catchers to do the right thing.
[223002390220] |You might also consider the fact that the original stack trace is lost a problem. 
[223002390230] |Another instance of (almost) commenting the language is later in the same file:
[223002390240] |I’d argue comments like “Write the InputData to OutputStream” are useless, because this is the idiom for buffered writes. 
[223002390250] |<b>Aside on Bad Code</b>
[223002390260] |Maybe you think you should always buffer streams.
[223002390270] |In this case, that’s wrong.
[223002390280] |Both bufferings simply cause twice as many assignments as necessary.
[223002390290] |Buffering the input stream is useless because you’re already reading into the byte array <code>buffer</code>. 
[223002390300] |Buffering the output stream is useless, because you’re writing to a byte array output stream <code>baos</code>.
[223002390310] |Furthermore, you don’t need to close or flush a byte array output stream, because both are no-ops (see the <a><code>ByteArrayOutputStream</code> javadoc</a>).
[223002390320] |Finally, the naming is wonky, because <code>osWriter</code> is not a writer, it’s an output stream. 
[223002390330] |This isn’t an isolated case.
[223002390340] |Other files in this package have similar problems with doc.
[223002390350] |<h3>Another Example</h3>
[223002390360] |While we’re picking on Apache Commons, I checked out another package I’ve used, fileUpload. 
[223002390370] |<li><a><code>org.apache.commons.fileupload/DiskFileUpload</a>: That's the kind of pre-formatted useless stuff I was talking about. We know what a member variable and constructor look like in Java. There weren't any other code comments in that file. In that same package, the <a><code>fileupload.ParameterParser</code></a> class has some, though, and I'm guessing they're of the kind that others mentioned as "good" comments, such as:
[223002390380] |I'd argue that perhaps a method called <code>trimLeadingWhiteSpace()</code> implemented the same way would be clearer.
[223002390390] |But if you're not going to define new methods, I'd say this kind of comment helps.
[223002390400] |But always verify that the code does what it says it does; don't take the comment's word (or method name's word) for it.
[223002390410] |I couldn't leave that file without commenting on their return-only-at-the-end-of-a-function style: 
[223002390420] |<h3>More Examples</h3>
[223002390430] |I thought only a couple wouldn't be convincing.
[223002390440] |So here's some links and examples:
[223002390450] |<li><a><code>collections.buffer.BoundedBuffer</a> Documenting what's clear from the code. (And nice section divider comments.) <li><a><code>digester.Digester</a> Yes, that's what <code>return</code>, <code>log</code>, and <code>throw</code> do.
[223002400010] |<title>Happy 95th Birthday, Martin Gardner</title>
[223002400020] |<a>Martin Gardner</a>, who turns 95 today, was a huge influence on me.
[223002400030] |I devoured his books and Scientific American “Mathematical Games” columns in junior high, high school, and even well into college.
[223002400040] |There’s a nice <a>profile of Martin Gardner by John Tierny</a> in today’s New York Times.
[223002400050] |(Already cited in four places by the Wikipedia article linked above.)
[223002400060] |Being now into my forties and trying to figure out what to do with my life, I’m fascinated by the fact that Gardner started at age 42 with no background in math other than a love of puzzles! 
[223002400070] |I’m not surprised a journalist would call “recreational mathematics” an <a>oxymoron</a>. 
[223002400080] |We already knew Gardner liked the A-HA style of puzzle —his books were full of them, requiring no real math knowledge to understand.
[223002400090] |I wonder what he’d have done if he grew up on <a>programming puzzles</a> rather than mathematical ones?
[223002400100] |We’d probably have more interesting, but equally ridiculous, programmer interview quizzes.
[223002410010] |<title>Learn Measure Theory for Under US$10</title>
[223002410020] |My friend and former colleague Christer Samuelsson sent me a present a while back (if you send me presents, you may be mentioned here too, though <a>I don’t have mugs for you</a>):
[223002410030] |<li>Kolmogorov, A. N. and S. V. Fomin; translated and adapted by Richard Silverman. 1970.
[223002410040] |<a>Introductory Real Analysis</a>.
[223002410050] |Dover. 
[223002410060] |Yes, it’s written by <a><b>the</b> Kolmogorov</a>, the man who invented (discovered, if you’re a Platonist) a consistent basis for probability using measure theory.
[223002410070] |Not content with laying the foundations for probability, Kolmogorov also kicked off the study of <a>algorithmic information theory</a> through what later became known as <a>Kolmogorov complexity</a>, and I can also highly recommend <a>Li and Vitanyi’s book</a> on that subject, though I’ve only read the introductory bits.
[223002410080] |You can check out the contents by following the Amazon link above.
[223002410090] |I’ll summarize by saying it covers the basics, from set theory to metric topology, including a long discussion of linear spaces and operators, a chapter on measure, and sections on Lebesgue integration in the first integration chapter and the Stieltjes generaliation later (really cool, in that it lets you merge integration and summation). 
[223002410100] |It presupposes the requisite “mathematical sophistication”, which really means you’ll be hard pressed to read more than a page every 10 or 15 minutes.
[223002410110] |Seriously, though, if you didn’t understand calc in high school (or college), this probably isn’t the book for you.
[223002410120] |In fact, if you haven’t studied higher math at all, this probably isn’t the place to start.
[223002410130] |Having said that, I hated calc in school, and only felt I understood it after doing analysis and topology, which cranked the level of abstraction beyond <img/>and Euclidean distances.
[223002410140] |It’d help to have some background in abstract algebra and set theory, too, though everything is explained clearly (though quickly) from first principles. 
[223002410150] |I don’t know whether to thank Kolmogorov, his co-author, or his translator, but this book is wonderfully clear.
[223002410160] |The examples are direct, the notation’s clear, and it’s fairly easy to use modularly (e.g. just to look up what a measure or σ-algebra is). 
[223002420010] |<title>Mihalcea (2007) Using Wikipedia for Automatic Word Sense Disambiguation</title>
[223002420020] |In response to a recent thread on the LingPipe mailing list about using Wikipedia for a word-sense disambiguation corpus, I’d like to point out Rada Mihalcea’s 2007 NAACL paper:
[223002420030] |<li>Mihalcea, Rada. 2007.
[223002420040] |<a>Using Wikipedia for Automatic Word Sense Disambiguation</a>.
[223002420050] |NAACL. 
[223002420060] |The idea’s very simple.
[223002420070] |A Wikipedia page represents a single sense of an ambiguous phrase.
[223002420080] |Both the senses and text for training can be extracted from Wikipedia’s link structure. 
[223002420090] |Rada maintains the <a>SenseEval</a> web pages and serves on the advising committee for the bakeoffs, which have pretty much defined the field recently. 
[223002420100] |<h3>Leaning on Wikitext</h3>
[223002420110] |The <a>wikitext</a> markup used for Wikipedia pages contains explicit disambiguation and mention-level information.
[223002420120] |Consider these examples from Rada’s paper:
[223002420130] |<li>In 1834, Sumner was admitted to the [[bar (law)|bar]] at the age of twenty three, and entered private practice in Boston.
[223002420140] |<li>It is danced in 3/4 time (like most waltzes), with the couple turning approx.
[223002420150] |180 degrees every [[bar (music)|bar]]. 
[223002420160] |The double brackets “[[ ]]” enclose links with the item on the left being the disambiguated reference, e.g. “bar (law)” or “bar (music)” and the item on the right the ambiguous word, e.g. “bar”.
[223002420170] |When viewing the page, the text to the right of the vertical bar shows up. 
[223002420180] |The scale’s impressive —there were 1108 examples of “bar” used as link text with 40 different categories, and this was a few years ago. 
[223002420190] |Rada extracted paragraphs around the mentions for training data.
[223002420200] |These are clearly marked in the Wikitext, so nothing fancy needs to be done for paragraph extraction (beyond the pain of Wikitext parsing itself).
[223002420210] |<h3>What About Disambiguation Pages?</h3>
[223002420220] |Wikipedia is full of <a>disambiguation pages</a>, which Wikipedia itself describes as:
[223002420230] |Disambiguation in Wikipedia is the process of resolving the conflicts that occur when articles about two or more different topics could have the same “natural” page title.
[223002420240] |This category contains disambiguation pages: non-article pages containing links to other Wikipedia articles and disambiguation pages. 
[223002420250] |For instance, the <a>Wikipedia page for “bar”</a>, lists an astounding number ambiguous meanings for the word.
[223002420260] |There are 11 popular usages (e.g. bar serving alcohol, bar of gold), 5 math and science usages (e.g. unit of pressure, bar chart), 4 uses in the law, and many other usages, some which appear under other categories. 
[223002420270] |I’d think the pages linked to would be useful for training.
[223002420280] |But Rada didn’t use them, listing reasons:
[223002420290] |<li>mismatch between disambiguation pages and usage, causing precision problems from links in a disambiguation page that are never referenced with the word and recall problems from some usages not showing up on the disambiguation page,
[223002420300] |<li>inconsistencies in the naming of disambiguation pages 
[223002420310] |The first issue is still problematic, though the recall side of it seems to be improving.
[223002420320] |The second issues is also still problematic.
[223002420330] |Although the category helps find such pages, Wikipedia’s formatting is still more like natural language than a database.
[223002420340] |<h3>Evaluation</h3>
[223002420350] |As you might expect, it worked pretty well.
[223002420360] |Rada evaluated a naive Bayes classifier with features including contextual words with part-of-speech tags. 
[223002420370] |<h3>Coding it in LingPipe</h3>
[223002420380] |This is something you could easily replicate in LingPipe.
[223002420390] |You could use one of the naive Bayes parsers.
[223002420400] |Or any of the other classifiers we consider in our <a>word-sense disambiguation tutorial</a>, including K-nearest neighbors and character or token-based language model classifiers. 
[223002420410] |If you need part-of-speech tags, check out our <a>part of speech tagging tutorial</a>.
[223002420420] |With naive Bayes and easily extracted unsupervised data, you could also use EM semi-supervised training, as described in our <a>EM tutorial</a>. 
[223002420430] |You could also use a discriminative linear classifier, as described in our <a>logistic regression tutorial</a>.
[223002420440] |The hard part’s all the data munging for Wikipedia.
[223002420450] |If you build a parser in Java and want to share, I’d be happy to link to it from here or host it in our <a>development sandbox</a>. 
[223002430010] |<title>LingPipe Classifiers and Chunkers for Endeca Extend Partner Program</title>
[223002430020] |A couple weeks ago, Endeca made the following press release:
[223002430030] |<li><a>Endeca Extend Partner Program Adds Leading Text Analytics Software Vendors</a> 
[223002430040] |The “leading text analytics software vendors” are us (props to Breck for naming us with an “A”), Basis Technology, Lexalytics, MetaCarta, NetOwl, Nstein, Semantia and Temis.
[223002430050] |But wait, that’s not all.
[223002430060] |A slew of text analytics companies had either joined earlier or announced joining now, including <a>ChoiceStream</a>, <a>BayNote</a>, <a>Lexalytics</a>, <a>Coremetrics</a>, <a>NStein</a>, and <a>Searchandise</a>.
[223002430070] |It’s no surprise that we’re all thinking Endeca has quite a bit of potential as a <a>channel partner</a>.
[223002430080] |After the usual marketing blather (e.g. “leveraging the extensibility of the McKinley platform”, “lower cost of ownership”, “value-added capabilities”, etc.) and vague promises (e.g. “unrestricted exploration of unstructured content”), the third paragraph of Endeca’s press release explains what it’s all about in allowing Endeca’s search customers to 
[223002430090] |…run their data through an Endeca Extend partner solution, extract additional meta-data elements from the text, and append that meta-data to the original content 
[223002430100] |<h3>Endeca Records</h3>
[223002430110] |Endeca stores documents in record data structures, which associate string keys with lists of string values.
[223002430120] |This is the same rought structure as is found in a <a>Lucene Document</a>. 
[223002430130] |One striking difference is that Endeca’s API is cleaner and better documented.
[223002430140] |Overall, I’m very impressed with Endeca’s API.
[223002430150] |Looking at their API reminds me of the APIs we built at SpeechWorks, where wiser heads prevailed on me to forego complex controls designed for control-freak grad students in favor of making easy things easy. 
[223002430160] |Another striking difference is that Lucene’s document structure is much richer, allowing for binary blobs to be stored by those trying to use <a>Lucene as a database</a>.
[223002430170] |Lucene also allows both documents as a whole and fields within a document to be boosted, adding a multiplier to their search scores for matching queries.
[223002430180] |<h3>Manipulator Extensions</h3>
[223002430190] |Endeca’s produced an API for extensions.
[223002430200] |An extension visits records, modifies them, and writes them back to the index.
[223002430210] |It can also write into its own scratch space on the file system and generate all new records.
[223002430220] |An extension consists of three components: configuration, factory, and runtime.
[223002430230] |<h3>Class 1.
[223002430240] |Configuration</h3>
[223002430250] |The bean-like configuration class provides setters and getters for strings, booleans, integers, and doubles.
[223002430260] |These are labeled with attributes and accessed through reflection.
[223002430270] |There’s then a method to validate a configuration that returns a list of errors as structured objects.
[223002430280] |I’m a big fan of immutable objects, so working with beans drives me crazy.
[223002430290] |They could use some more doc on concurrency and lifecycle order; as is, I was conservative and programmed defensively against changes in config.
[223002430300] |Configuration is handled through an administrator interface.
[223002430310] |As I said, it’s bean-like. 
[223002430320] |<h3>Class 2.
[223002430330] |Factory</h3>
[223002430340] |There is then a factory class with a method that returns the config class (so the admin interface can tell what kind of config to build for it).
[223002430350] |It also contains a method that takes an Endeca application context and configuration and produces a runtime application.
[223002430360] |The context provides services like logging, a path to local file space, and a hook into a pipe into which modified records may be sent.
[223002430370] |<h3>Class 3.
[223002430380] |Runtime</h3>
[223002430390] |The runtime simply provides a record visitor method.
[223002430400] |To write out changes, you grab the output channel from the context provided to the factory.
[223002430410] |There are also some lifecycle methods used as callbacks: interrupt processing, processing of records is complete, and final cleanup.
[223002430420] |You can still write out answers during the completion callback.
[223002430430] |<h3>Endeca’s Demo Manipulator Extension</h3>
[223002430440] |Endeca has great programmers and their Java API design was really clear.
[223002430450] |I love it when vendors follow standard patterns and idioms in their API designs.
[223002430460] |Especially when they use generics usefully.
[223002430470] |The PDF developer doc’s still in progress, but their Javadoc’s mostly in place.
[223002430480] |What was really sweet is that they gave us a working demo extension program with all of its configuration, tests, and even mock objects for use in JUnit testing the entire framework without a complete install of Endeca’s platform.
[223002430490] |I’m so happy when someone sends me a Java package that unpacks then compiles with Ant without griping.
[223002430500] |<h3>LingPipe Classifier CAS Manipulator Extension</h3>
[223002430510] |The first extension I wrote is configured with a path to a serialized text classifier on the classpath.
[223002430520] |I then configured a list of field names (only strings are available, so I went with comma-separated values) from which to collect text, and a field name into which to write the result of classification.
[223002430530] |[<b>Correction:</b> 5 Nov 2009, Endeca let me know that they had this covered; if I declare the variables in the bean-like configuration to be list-like values, the reflection-based config system will figure it out.
[223002430540] |This is awesome.
[223002430550] |I always hate rolling in ad-hoc little parsing "languages" like CSV in config.
[223002430560] |It's just sooo hard to doc and code correctly.]
[223002430570] |<h3>LingPipe Chunker CAS Manipulator Extension</h3>
[223002430580] |The second extension is a chunker.
[223002430590] |It requires a path to a chunker.
[223002430600] |Optionally, it allows a sentence detector to be configured for preprocessing (most of our chunkers work better at the sentence level).
[223002430610] |It also optionally allows a dictionary (and tokenizer factory) to be specified for overriding the chunks found by the chunker.
[223002430620] |Then, a list of field names from which to read text.
[223002430630] |The output gets written into chunk-specific fields.
[223002430640] |Because a given field name can contain multiple values, you can keep the resulting spans separate.
[223002430650] |<h3>Endeca’s Faceting</h3>
[223002430660] |Endeca’s big on <a>faceted search</a>.
[223002430670] |You may be familiar with it from two of the best online stores, <a>NewEgg</a> and <a>Amazon</a>. 
[223002430680] |It’s easy to treat our classifier plugin output as a facet.
[223002430690] |For instance, classify documents by sentiment and now sentiment’s a facet.
[223002430700] |Do a search, and you’ll get a summary of how many positive and how many negative documents, with an option to restrict search to either subset. 
[223002430710] |It’s also easy to treat our chunker output as a facet.
[223002430720] |For instance, if you include a company name chunker, you’ll be able to use companies as facets (e.g. as NewEgg does with manufacturers, though documents may contain references to more than one company).
[223002430730] |<h3>Buying Plugins</h3>
[223002430740] |Drop <a>Breck</a> a line.
[223002430750] |Now that I have my head around the bigger picture, it’s pretty easy to build these kinds of extensions.
[223002430760] |So if there’s something you’d like integrated into Endeca and you’re willing to pay for it, let us know.
[223002440010] |<title>Hierarchical Bayesian Batting Ability, with Multiple Comparisons</title>
[223002440020] |Just in time for the last game(s) of this year’s <a>World Series</a>, the final installment of my example of Bayesian stats using baseball batting ability.
[223002440030] |I took us off-topic (text analytics) with a general intro to Bayesian stats (<a>What is “Bayesian” Statistical Inference?</a>).
[223002440040] |As a first example, I compared Bayesian calculations of binomial posteriors with point estimates (<a>Batting Averages: Bayesian vs. MLE Estimates</a>).
[223002440050] |In exploring the question of “where do priors come from?”, I started with simple non-Bayesian point estimates (<a>Moment Matching for Empirical Bayes Beta Priors for Batting Averages</a>).
[223002440060] |Finally, I realized I’d meant “ability” where I’d said “average” (former is a latent parameter, latter is a statistic calculated from at bats), when I considered Bayesian point estimates (<a>Bayesian Estimators for the Beta-Binomial Model of Batting Ability</a>).
[223002440070] |<h3>Hierarchical Model Recap</h3>
[223002440080] |For batter <img/>, the number of hits <img/>in <img/>at bats is modeled as a binomial, 
[223002440090] |<img/>for <img/>,
[223002440100] |where the ability, or chance of getting a hit, for batter <img/>is <img/>.
[223002440110] |Ability is modeled as having a beta distribution
[223002440120] |<img/>for <img/>
[223002440130] |with prior number of hits <img/>and prior number of outs <img/>.
[223002440140] |These parameters, which act as priors for the for the binomial parameter, are themselves given priors.
[223002440150] |The mean of the beta, <img/>, is given a uniform prior,
[223002440160] |<img/>.
[223002440170] |The prior for the scale <img/>is modeled by a Pareto distribution, which has probability proportional to <img/>,
[223002440180] |<img/>.
[223002440190] |<h3>Fitting</h3>
[223002440200] |I used the 2006 AL position player data (given in this <a>previous blog post</a>).
[223002440210] |That fixes the number of players <img/>and the hits <img/>and at-bats <img/>for each player <img/>. 
[223002440220] |I then used BUGS encoding of the model above (as shown in <a>this previous post</a>).
[223002440230] |BUGS automaticaly implements Gibbs sampling, a form of Markov Chain Monte Carlo (MCMC) inference.
[223002440240] |I ran 3 chains of 1000 samples each, retaining the last 500 samples, for 1500 posterior samples total.
[223002440250] |All parameters had <img/>values very near 1, indicating convergence of the Markov chains.
[223002440260] |As usual, we read off statistics from the samples and used the sampled values for inference, where they allow the integrals involved in Bayesian inference (as descirbed in <a>this blog post</a>) to be computed. 
[223002440270] |<h3>Beta Posterior</h3>
[223002440280] |We can inspect the posterior for the beta mean <img/>and scale <img/>parameters.
[223002440290] |We plot them as a 2D scatterplot with their means picked out as lines. 
[223002440300] |As usual, the scale is much harder to estimate than the mean.
[223002440310] |<h3>Ability Posteriors</h3>
[223002440320] |We can also plot the ability for particular players.
[223002440330] |Here’s histograms of sampled posteriors for the players with the best average posterior ability estimates, with their hits and at-bats provided as labels above the plot:
[223002440340] |Notice how the variance of the posterior is determined by the number of at bats.
[223002440350] |The player with 60 at bats has a much wider posterior than the player with 695 at bats.
[223002440360] |<h3>Multiple Comparisons: Who’s the Best Batter?</h3>
[223002440370] |We’re going to do what <a>Andrew, Jennifer and Masanao suggest</a>, which is to use our hierarchical model to make a posterior comparison about player’s ability.
[223002440380] |In particular, we’ll estimate the posterior probabability that a particular player is the best player.
[223002440390] |We simply look at all 1500 posterior samples, which include ability samples as plotted above, and count how many times a player has the highest ability in a sample.
[223002440400] |Then divide by 1500, and we’re done.
[223002440410] |It’s a snap in R, and here’s the results, for the same batters as the plot above:
[223002440420] |The .347 batter with 521 at bats not only has the highest estimated chance in our model of having the highest ability, he also won the batting crown (Joe Mauer of Minnesota).
[223002440430] |The beta-binomial hierarchical model estimate is only 12% that this batter has the highest ability.
[223002440440] |The estimate is very close for the .343 batter with 623 at bats (Derek Jeter of the Yankees).
[223002440450] |[It turns out the race to the batting crown <a>came down to the wire</a>.]
[223002440460] |The larger number of at bats provides more evidence that the batter has a higher ability than average, thus pulling the posterior ability estimate further away from the prior mean.
[223002440470] |Finally, note that we’re assigning some chance that the .367 batter with only 60 at bats is best in the league.
[223002440480] |That’s because when the samples are on the high side of the distribution, this batter’s best.
[223002450010] |<title>Phrase Detectives Linguistic Annotation Game</title>
[223002450020] |<a>Massimo Poesio</a> just sent me a pointer to the following awesome web application:
[223002450030] |<li><a>Phrase Detectives</a> (the AnaWiki annotation game)</a> 
[223002450040] |<h3>Annotation Game</h3>
[223002450050] |Annotation games (aka “games with a purpose”) were popularized by van Ahn’s <a>ESP game</a>, though I first heard about them through David Stork’s <a>Open Mind</a> project. 
[223002450060] |Unlike the mechanical Turk, the games approach tries to make the task somewhat fun and competitive.
[223002450070] |It seems like making the users “detectives” is a thin veneer of “fun”, but they maintain the metaphor beautifully throughout the whole site, so it works. 
[223002450080] |As with many games, Phrase Detectives pays out in leader board bragging rights and cash prizes rather than directly for work completed as on Mechanical Turk. 
[223002450090] |<h3>Phrase Detective Tasks</h3>
[223002450100] |The really brilliant part is how they break the coref annotation task into four easy-to-answer questions about a single highlighted phrase. 
[223002450110] |<li>Not Mentioned Before: yes/no question as to whether the referent of highlighted phrase was previously mentioned in the text
[223002450120] |<li>Mentioned Before: highlight previous mention of a given phrase
[223002450130] |<li>Non-Referring: pick out non-referential nouns (like the “there” in “there is trouble brewing”)
[223002450140] |<li>Property of Another Phrase: pick out other phrases that describe someone already mentioned (e.g. attributives or apositives) 
[223002450150] |The site also has nice clean, easy-to-follow graphics, and appears to still have users after two years.
[223002450160] |<h3>Adjudication Phase</h3>
[223002450170] |OK, they call it “Detectives Conference”, but the idea is you get to vote yes/no as to whether someone else’s answer is right.
[223002450180] |This is a good idea widely used on Mechanical Turk because it’s easier to check someone’s work than to create it from scratch.
[223002450190] |<h3>Read All About It</h3>
[223002450200] |It was developed by academics, so there are at least as many papers as contributors:
[223002450210] |<li>Chamberlain, Jon, Massimo Poesio and Udo Kruschwitz. 2008.
[223002450220] |<a>Phrase Detectives: A Web-based Collaborative Annotation Game</a>.
[223002450230] |I-KNOW.
[223002450240] |<li>Chamberlain, Poesio and Kruschwitz. 2008.
[223002450250] |<a>Addressing the Resource Bottleneck to Create Large-Scale Annotated Texts</a>.
[223002450260] |ACL workshop.
[223002450270] |<li>Poesio, Kruschwitz and Chamberlain. 2008.
[223002450280] |<a>ANAWIKI Creating anaphorically annotated resources through web cooperation</a>.
[223002450290] |LREC.
[223002450300] |<li>Kruschwitz, Chamberlain and Poesio. 2009.
[223002450310] |<a>(Linguistic) Science Through Web Collaboration in the ANAWIKI project</a> 
[223002450320] |<h3>Coreference Annotation</h3>
[223002450330] |There are “expert” annotated within-doc coref corpora for the <a>MUC 7</a> and <a>ACE 2005</a> evaluations (available from <a>LDC</a>, who charge an arm and a leg for this stuff, especially for commercial rights).
[223002450340] |LingPipe does within-document coreference and we’ve worked on cross-document coreference.
[223002450350] |<h3>More Like This</h3>
[223002450360] |As soon as you find one of these things, you find more.
[223002450370] |Check out:
[223002450380] |<li><a>Sentiment Quiz</a> (Facebook app to do sentiment annotation) 
[223002450390] |I’d love to hear about more of these if anyone knows any.
[223002460010] |<title>Chang et al. (2009) Reading Tea Leaves: How Humans Interpret Topic Models</title>
[223002460020] |This forthcoming NIPS paper outlines a neat little idea for evaluating clustering output:
[223002460030] |<li>Chang, Jonathan, Jordan Boyd-Graber, Sean Gerrish, Chong Wang and David M. Blei. 2009.
[223002460040] |<a>Reading Tea Leaves: How Humans Interpret Topic Models</a>.
[223002460050] |NIPS. 
[223002460060] |The question they pose is how to evaluate clustering output, specifically topic-word and document-topic coherence, for human interpretability.
[223002460070] |<h3>Bag of Words</h3>
[223002460080] |Everything’s in the bag of words setting, so a topic is modeled as a discrete distribution over words. 
[223002460090] |<h3>Multiple Topics per Document</h3>
[223002460100] |They only consider models that allow multiple topics per document.
[223002460110] |Specifically, the clusterers all model a document as discrete distribution over topics.
[223002460120] |The clusterers considered share strong family resemblances: probabilistic latent semantic indexing (pLSI) and two forms of latent Dirichlet allocation (LDA), the usual one and one in which topics for documents are drawn from a logistic prior modeling topic correlations rather than a uniform Dirichlet.
[223002460130] |<h3>Intrusion Tasks</h3>
[223002460140] |To judge the coherence of a topic, they take the top six words from a topic, delete one of the words and insert a top word from a different topic.
[223002460150] |They then measure whether subjects can detect the “intruder”. 
[223002460160] |To judge the coherence of the topics assigned to a document, they do the same thing for document distributions: they take the top topics for a document, delete one and insert a topic not assigned with high probability to the document.
[223002460170] |<h3>Analysis</h3>
[223002460180] |They considered two small corpora of roughly 10K articles, 10K word types and 1M tokens, one from Wikipedia pages and one from NY Times articles.
[223002460190] |These can be relatively long documents compared to tweets, customer support requests, MEDLINE abstracts, etc, but are shorter than full-text research articles or corporate 10K or 10Q statements.
[223002460200] |They only consider 50, 100, and 150 topic models, and restrict parameterizations to add-1 smoothing (aka the Laplace form of the Dirichlet prior) for per-document topic distributions.
[223002460210] |I didn’t see any mention of what the prior was for the per-topic word distributions.
[223002460220] |I’ve found both of these parameters to have a huge effect on LDA output, with larger prior counts in both cases leading to more diffuse topic assignments to documents. 
[223002460230] |They only consider point estimates of the posteriors, which they compute using EM or variational inference.
[223002460240] |This is is not surprising given the non-identifiability of topics in the Gibbs sampler. 
[223002460250] |<h3>Mechanical Turker Voting</h3>
[223002460260] |They used 8 mechanical Turkers per task (aka HIT) of 10 judgments (wildly overpaying at US$0.07 to US$0.15 per HIT).
[223002460270] |<h3>(Pseudo Expected) Predictive Log Likelihood</h3>
[223002460280] |They do the usual sample cross-entropy rate evaluations (aka [pseudo expected] predictive log likelihoods).
[223002460290] |Reporting these to four decimal places is a mistake, because the different estimation methods for the various models have more variance than the differences shown here.
[223002460300] |Also, there’s a huge effect from the priors.
[223002460310] |For both points, check out <a>Asuncion et al.’s analysis of LDA estimation</a>, which the first author, Jonathan Chang, <a>blogged about</a>. 
[223002460320] |<h3>Model Precision</h3>
[223002460330] |Their evaluation for precision is the percentage of subjects who pick out the intruder.
[223002460340] |It’d be interesting to see the effect of adjusting for annotator bias and accuracy.
[223002460350] |This’d be easy to evaluate with any of <a>our annotation models</a>.
[223002460360] |For instance, it’d be interesting to see if it reduced the variance in their figure 3.
[223002460370] |There’s variation among the three models at different topics over the different corpora.
[223002460380] |I’m just not sure how far to trust their model precision estimates. 
[223002460390] |<h3>Their Take Home Message</h3>
[223002460400] |The authors drive home the point that traditional measures such as expected predictive log likelihood are negatively correlated with their notion of human evaluated precision.
[223002460410] |As I said, I’m skeptical about the robustness of this inference given the variation in estimation techniques and the strong effect of priors.
[223002460420] |The authors go so far as to suggest using humans in the model selection loop.
[223002460430] |Or developing an alternative estimation technique.
[223002460440] |If they’d been statisticians rather than computer scientists, my guess is that they’d be calling for better models, not a new model selection or estimation technique!
[223002460450] |<h3>The Real Take Home Message</h3>
[223002460460] |I think the real contribution here is the evaluation methodology.
[223002460470] |If you’re using clustering for exploratory data analysis, this might be a way to vet clusters for further consideration. 
[223002460480] |<h3>What They Could’ve Talked About</h3>
[223002460490] |Although they mention Griffiths and Steyvers’ work on using LDA for traditional psychometrics, I think a more interesting result is Griffith and Steyvers’ use of KL-divergence to measure the stability of topics across Gibbs samples (which I describe and recreate in the <a>LingPipe clustering tutorial</a>).
[223002460500] |Using KL divergence to compare different clusters may give you a Bayesian method to automatically assess Chang et al.’s notion of precision.
[223002470010] |<title>Probabilistic Edit Channel Models</title>
[223002470020] |This post is about probabilistic edit distances used as noisy channel models with applications to biological short-read sequencing and natural language spelling correction.
[223002470030] |(Spoiler: Normalization is over channel outputs and the forward (sum) algorithm is required instead of the usual Viterbi (max) algorithm.)
[223002470040] |<h3>Spelling Correction and Chinese Tokenization</h3>
[223002470050] |LingPipe models both spelling correction and Chinese tokenization (word splitting) using noisy channel models.
[223002470060] |We have two tutorials:
[223002470070] |<li><a>Spelling Correction Tutorial</a></li>
[223002470080] |<li><a>Chinese Tokenization Tutorial</a></li> 
[223002470090] |The two components of a <a>noisy channel model</a> are the source <img/>from which signals <img/>consisting of strings are generated probabilistically, and the channel <img/>which models the probability of observing the signal <img/>when the message is <img/>.
[223002470100] |For spell checking, the source model of what people are likely to say may be estimated using document data and/or query log, and the channel model of possible brainos and typos may be estimated using matched query/correction data (which itself may be inferred via EM from query logs and/or document data).
[223002470110] |For Chinese, the channel deterministically deletes spaces, which requires probabilistic reconstruction for the observer who doesn’t get word boundary information.
[223002470120] |LingPipe’s spelling package implements (confusion-matrix weighted) edit distance.
[223002470130] |And other models, such as n-gram comparison.
[223002470140] |This is all described in the spelling tutorial as it relates to spell checking, and also in:
[223002470150] |<li><a>String Comparison Tutorial</a></li> 
[223002470160] |LingPipe doesn’t enforce a probabilistic interpretation of edit distance.
[223002470170] |Furthermore, decoding of the intended signal given the observed message is implemented using the <a>Viterbi approximation</a>, which estimates the channel probability based on the single best alignment between the message <img/>and the observed signal <img/>.
[223002470180] |<h3>Mature mRNA Sequencing</h3>
[223002470190] |Mitzi’s lab’s working on sequencing the untranslated end regions of mature mRNA (aka the 3′ UTR) in <a>C. elegans</a> (aka the nematode worm), a widely studied <a>model organism</a>.
[223002470200] |The 3′ UTR is the sequence of bases after the <a>stop codon</a> and before the <a>poly-A tail</a> found on mature <a>mRNA</a>.
[223002470210] |<h3>Short Read Sequencers</h3>
[223002470220] |I’ve been talking with Mitzi lately about the next generation short-read DNA sequencers, like <a>Illumina</a> and <a>SOLiD</a>.
[223002470230] |Perhaps it’s not surprising, given that it’s locally coherent string data, that the same techniques are used in bioinformatics as in computational linguistics.
[223002470240] |<h3>Isoform Expression Models</h3>
[223002470250] |I’ve been formulating Bayesian models for <a>transcriptome</a> analysis.
[223002470260] |In particular, <a>isoform</a> (aka alternative splicing) expression.
[223002470270] |As usual, there’s an underlying generative model of the process.
[223002470280] |One of the components of this model is how the read <img/>that’s observed from the device (the observed data) is generated given the biological sequence <img/>from which it was generated (the estimand of interest).
[223002470290] |The noisy channel model is appropriate for this setting; I just need to make it probabilistic.
[223002470300] |<h3>Levenshtein Distance</h3>
[223002470310] |The simplest models of spelling correction or genetic sequencing involve simple <a>Levenshtein distance</a> calculations.
[223002470320] |The Levenshtein distance is the minimum number of insert, delete or substitution operations required to turn one sequence into the other.
[223002470330] |It’s symmetric.
[223002470340] |But it’s not probabilistic.
[223002470350] |<h3>Probabilistic Channels</h3>
[223002470360] |It’s actually quite simple to model <img/>.
[223002470370] |Just make sure all the moves from a given state sum to 1.0.
[223002470380] |A state corresponds to a prefix of the reference sequence <img/>.
[223002470390] |Legal moves are to skip (delete) the next symbol from the message <img/>, to add (insert) a spurious symbol into the observation <img/>, match the next symbol from <img/>and <img/>, or to substitute the next symbols.
[223002470400] |<h3>Viterbi versus Forward Algorithm</h3>
[223002470410] |The usual approach to calculation is to make the so-called Viterbi assumption, and look at the probability of the best sequence of moves, to consume the message sequence and observed sequence.
[223002470420] |Given a sequence of edit operations, we can generate an alignment between sequences.
[223002470430] |For instance, consider matching the message ACGTACG to the observed signal AGTTAGG.
[223002470440] |The following alignment consists of a match of A, a delete of C, two matches GT, an insertion of a T, a match on A, a substitution of a G for a C, and a final match on G:
[223002470450] |To make the probabilities add up to 1.0 for the moves from a particular state, we need to subdivide the inserts and substitutions.
[223002470460] |With the genetic alphabet of symbols {A, C, G, T}, the 9 possible moves are subdivided by output, I(A), I(C), I(G), I(T), D, S(A), S(C), S(G), S(T).
[223002470470] |We have probabilities for these outputs for each symbol.
[223002470480] |In the genetic case, that’s four multinomials of order 9.
[223002470490] |Note that we’ve included the match among the substitution operations for simplicity.
[223002470500] |If we know the next output symbol from a state, only one of the four substitutions will be legal —the one that outputs the next output symbol.
[223002470510] |But there are many more alignments for the same pair of strings.
[223002470520] |Some even have the same Levenshtein distance.
[223002470530] |For instance, we can align the two sequences using three substitutions:
[223002470540] |Edit distance assigns a probability to a path of operations, which corresponds to an alignment <img/>, say <img/>.
[223002470550] |Given the underlying message (or sequence) <img/>, the observed sequence <img/>is determined by the edit operations <img/>.
[223002470560] |What we need to do is integrate (or sum) out the alignments in the usual way in order to calculate the probability of the observed signal (query/read) <img/>given the message (meaning/reference sequence) <img/>:
[223002470570] |The Viterbi approximation is:
[223002470580] |The approximation is only reasonable from a probabilistic point of view if the best alignment accounts for most of the probability mass.
[223002470590] |Or, if we are doing calculations proportionally and the best alignment probability is a constant fraction of the total generation probability.
[223002470600] |Simply using the forward algorithm instead of the Viterbi algorithm computes this in <img/>time (and space) where <img/>is the length of <img/>and <img/>the length of <img/>.
[223002470610] |We can actually tighten up the space requirements to <img/>; this is how I did things for LingPipe’s implementation and what I contributed for Lucene’s fuzzy matcher.
[223002470620] |We can tighten even further if we have an upper bound on the maximum number of edits to consider, say <img/>.
[223002470630] |Then the time complexity reduces to <img/>.
[223002470640] |(As for all things string algorithm related, see <a>Gusfield’s string algorithms book</a> and <a>Durbin, Eddy, Krogh and Mithcison’s probabilistic string matching book</a>).
[223002470650] |Of course, we’ll compute it all on a log scale so the products become sums.
[223002470660] |This will require our old friend the <a>log sum of exponentials</a> operation.
[223002470670] |<h3>Filtering</h3>
[223002470680] |For the biological sequence matching problem, we’re facing on the order of 100M reads of 50 bases each, matching against a set of 30K isoforms of 1.5K bases each.
[223002470690] |This is prohibitive for the forward algorithm.
[223002470700] |There are various ways to share the prefix operations (again, see Gusfield’s book).
[223002470710] |Typically, though, practitioners use n-gram sequence indexes to spot potential matches, only considering sequences with good n-gram overlap, thus eliminating most of the work up front.
[223002470720] |This can be done either heuristically, as in <a>BLAST</a> (described in both books), or exactly, as in <a>SHRiMP</a> (the latter link is to a paper with a good description of the SOLiD color space reads and uses automaton composition to compose noisy channels, one for color read errors, one for sequencing errors, and one for mutations).
[223002470730] |This is like the notion of blocking in database <a>record linkage</a> (including database deduplication), which we also tend to carry out using character n-grams for natural language sequences.
[223002470740] |The transcendental math’s still going to dominate the calculations, so typically a Viterbi pass using Levenshtein distance is done after blocking with n-grams to further filter out unlikely alignments.
[223002470750] |Biological sequence analysis sure looks a lot like natural language sequence analysis!
[223002480010] |<title>Computing Marginal Channel Probabilities with Generalized Needleman-Wunsch</title>
[223002480020] |In my last post on <a>Probabilistic Edit Channel Models</a>, I tried to motivate a properly calculated marginal probability of an observation (e.g., a read) given a source (e.g., a reference sequence).
[223002480030] |In this post, I’ll show you how to build a properly normalized probabilistic generalization of the well-known <a>Needleman-Wunsch algorithm</a> for global alignment that computes full marginal probabilities rather than best path probabilities.
[223002480040] |Global alignment matches all of its two input sequences.
[223002480050] |This approach is easily generalized to the <a>Smith-Waterman algorithm</a> for local alignments or to fully matching a read sequence against a subsequence of a reference sequence.
[223002480060] |See the last section below.
[223002480070] |<h3>Edit Operations</h3>
[223002480080] |We’ll assume a simple alphabet of bases, {A,C,G,T}.
[223002480090] |We’ll also assume four possible actions given a reference sequence and a position in that reference sequence:
[223002480100] |<li>delete the next symbol from the reference (advance the ref position)</li>
[223002480110] |<li>insert a symbol into the read (don’t advance the ref position)</li>
[223002480120] |<li>generate a matched symbol for the read (advance ref)</li>
[223002480130] |<li>generate a mismatched symbol for the read (advance ref)</li> 
[223002480140] |There’s only one way to delete, which we’ll write D.
[223002480150] |There are four possiblities for insertion depending on the base inserted, which we’ll write IA, IC, IG, IT.
[223002480160] |There are a total of four possibilities for substitution and matching, depending on the base generated in the read, SA, SC, SG, ST; the one with the symbol corresponding to the next reference symbol is the match case.
[223002480170] |<h3>Probabilistic Edits</h3>
[223002480180] |Given a reference sequence, we generate a read sequence by iterating over the reference sequence base by base, and for each base, performing one of the above operations.
[223002480190] |If the operation is not a delete, the position in the reference sequence advances.
[223002480200] |For instance, consider the alignment we introduced in the previous post,
[223002480210] |which is generated by the sequence of operations:
[223002480220] |What we need to estimate is the conditional probability of one of the nine edit operations given the next base in the input.
[223002480230] |We’ll assume the edit probabilities are known.
[223002480240] |Typically, these edits are inferred using little or no training data through the EM algorithm.
[223002480250] |The sequence of edit operations is: σ = [SA, D, SG, SG, IT, SA, SA, SG].
[223002480260] |Given the reference sequence ACGTACG and the edit operations σ, the read AGTTAGG is uniquely determined.
[223002480270] |With this clean generative model, given an input reference sequence, the probability of all read sequences sums to 1.0.
[223002480280] |Of course, we will know the read in most of what we do and only need to compute its probability.
[223002480290] |The probability of that sequence of edit operations given the reference sequence ACGTACG is given by the product of all the probabilities in the rightmost column above:
[223002480300] |p(σ|ACGTACG) = p(SA|A) p(D|C) p(SG|G) p(ST|T) p(IT|T) p(SA|A) p(SG|C) p(SG|G)
[223002480310] |What we’re interested in calculating here is p(AGTTAGG | ACGTACG), namely the probability of the read given the reference sequence.
[223002480320] |This is done by summing over all possible alignments:
[223002480330] |Note that this probability will be zero if the edit sequence <img/>and reference <img/>don’t generate the read <img/>.
[223002480340] |The usual alignment programs compute the best alignment, namely:
[223002480350] |We could use a regular <img/>in place of <img/>to compute the probability of the best alignment instead of the alignment itself.
[223002480360] |Note that we take the maximum probability; usually the algorithm is formulated with edit costs and it takes the minimum cost.
[223002480370] |We could convert to the usual setup with minimization by reformulating in terms of negative log probabilities.
[223002480380] |<h3>Needleman-Wunsch Algorithm</h3>
[223002480390] |The Needlman-Wunsch algorithm is a classic instance of dynamic programming where the distances computed for shorter substrings are extended in the inner loop to distances for longer strings.
[223002480400] |The first two loops deal with the boundary conditions of all-insertions and all-deletions
[223002480410] |Given its simple loop, this algorithm clearly takes time proportional to read time reference length.
[223002480420] |<h3>Marginal Needleman-Wunsch</h3>
[223002480430] |I’ll call this the marginal Needleman-Wunsch, but if someone knows a better name, let me know.
[223002480440] |It bears the same relation to the standard N-W algorithm as the forward algorithm for HMMs compares to the Viterbi algorithm.
[223002480450] |The only change is that we’re calling the familiar <a>log sum of exponentials</a> function here rather than max.
[223002480460] |Recall the definition:
[223002480470] |We use this because in our case, x, y, and z are log probabilities, so that exp(x), exp(y), and exp(z) are linear probabilities, so that their sum is a linear probability, and hence the final result is the total probability of the paths converted back to the log scale.
[223002480480] |We don’t just maintain linear probabilities because we’re likely to hit underflow problems.
[223002480490] |(This may not actually be an issue for the limited number of errors allowed in these models; if not, then we just need a sum of the linear probabilities, which will be much faster to execute computationally.)
[223002480500] |That’s it.
[223002480510] |We’ve computed the (log of) the sum of all path probabilities.
[223002480520] |<h3>When the Reference is Exhausted</h3>
[223002480530] |One small detail: we need to be able to generate symbols in the read after the reference is exhausted, so we have to include that option in the algorithm.
[223002480540] |That is, we need five discrete distributions over edit operations, one for each next base {A,C,G,T} in the reference, and one to use when the reference is exhausted.
[223002480550] |Although not conceptually difficult or expensive to compute, it complicates the boundary conditions for the algorithm and the conceptualization of the algorithm, so the algorithm isn’t technically correct as stated.
[223002480560] |To correc it, the probability terms need to be fiddled to account for the boundary.
[223002480570] |<h3>Generalizing to Local Alignments</h3>
[223002480580] |The Smith-Waterman-like generalization to local alignments requires allowing zero-cost deletes on the first and last row of the edit matrix, and zero-cost inserts on the first and last column of the matrix.
[223002480590] |This isn’t quite properly normalized, but can be if we assume a uniform model of read start and end positions.
[223002480600] |We can also restrict local alignments in the usual way to the case where the read completely matches a substring of the reference sequence by only allowing zero-cost deletes on the first and last row of the distance matrix.
[223002480610] |<h3>Multiple Edits and Correlated Errors</h3>
[223002480620] |The model above is <a>Markovian</a>; only the current reference symbol determines the output symbol.
[223002480630] |This assumption may be relaxed to allow compound edit operations instead of the simple Markovian insertion, substitution, and deletion operations of the Needleman-Wunsch algorithm.
[223002480640] |For example, University of Toronto’s <a>SHRiMP alignment package</a> considers pairwise operations generated due to the <a>AB SOLiD platform’s colorspace</a> reads (there’s a shortage of capital “I”s for names, hence “Alias-i”).
[223002480650] |With this approach, SHRiMP can model the the correlated errors from the SOLiD colorspace reads relative to a reference sequence due to to singular nucleotide polymorphisms (SNPs) in the samples relative to the reads (which induce two sequential, correlated, color space read errors).
[223002480660] |SHRiMP’s generalization of Needleman-Wunsch is similar both algorithmically and conceptually to the phonetic extensions to he edit distance component of the noisy channel model for natural language spelling correction proposed by Kristina Toutanova and Bob Moore in their 2002 ACL paper, <a>Pronunciation Modeling for Improved Spelling Correction</a>.
[223002500010] |<title>Measure Theory in Two Definitions</title>
[223002500020] |<a><img"></a><a>Measure theory</a> generalizes the notion of length, area and volume to a very general topological setting.
[223002500030] |It also forms the basis of probability theory. 
[223002500040] |<h3>Definition 1</h3>
[223002500050] |A <b><img/>-algebra</b> is a set <img/>of sets which
[223002500060] |<li>is closed under difference, <img/>if <img/>,
[223002500070] |<li>is closed under countable unions, <img/>if <img/>, and
[223002500080] |<li>has a unit <img/>such that <img/>for all <img/>. 
[223002500090] |<h3>Definition 2</h3>
[223002500100] |A <b><img/>-additive measure</b> is a function <img/>over a <img/>-algebra <img/>taking non-negative values such that
[223002500110] |<img/>for pairwise disjoint sets <img/>.
[223002500120] |<h3>Immediate Consequences</h3>
[223002500130] |The closure of a <img/>-algebra under countable intersections follows from de Morgan’s law,
[223002500140] |<img/>.
[223002500150] |The empty set <img/>is the unique zero element such that <img/>for all <img/>.
[223002500160] |Further, <img/>and <img/>for all <img/>.
[223002500170] |A <img/>-algebra forms a <a>ring</a>, with <img/>as addition, <img/>as multiplication, <img/>as the multiplicative identity, <img/>as the additive identity, and <img/>as additive difference. 
[223002500180] |<h3>Constructing Lebesgue Measures</h3>
[223002500190] |It’s not entirely trivial to show that interesting measures exist, even working over the real numbers.
[223002500200] |The easiest useful measure to construct is the <a>Lebesgue measure</a> over the unit interval <img/>. 
[223002500210] |Start by defining the measure of a subinterval to be its length.
[223002500220] |Extend the definition to countable unions of subintervals by summation, following the definition of measure. 
[223002500230] |It remains to tidy up the some boundary cases producing zero-measure results, which isn’t entirely trivial (analysis is built on counterexamples and edge cases), but the basic idea pretty much works as is.
[223002510010] |<title>Probability Measures and Random Variables</title>
[223002510020] |I introduced measure theory in my last post, <a>Measure Theory in Two Definitions</a>.
[223002510030] |With that out of the way, we can move on to probability measures and random variables.
[223002510040] |<h3>Probability Measure</h3>
[223002510050] |A <b>probability measure</b> is a measure taking values in the closed interval <img/>and mapping the unit to 1, <img/>.
[223002510060] |It follows that <img/>. 
[223002510070] |In a probability measure, the sets <img/>are called <b>events</b> and we write <img/>for <img/>.
[223002510080] |The <b>sample space</b> for a probability measure is <img/>.
[223002510090] |<h3>Those Pesky Random Variables</h3>
[223002510100] |Given a probability measure <img/>, a <b>random variable</b> <img/>is a real-valued function over the measure’s sample space such that <img/>(so that it has a measure) for all <img/>. 
[223002510110] |The <b>cumulative density function</b> <img/>for <img/>is defined by 
[223002510120] |<img/>. 
[223002510130] |The <b>probability</b> that random variable <img/>is less than a fixed value <img/>is
[223002510140] |<img/>.
[223002510150] |The <b>probability</b> that the variable <img/>falls in the interval <img/>is defined by
[223002510160] |<img/>.
[223002510170] |When <img/>is differentiable, the <b>density function</b> <img/>is
[223002510180] |<img/>.
[223002510190] |When the density is defined, 
[223002510200] |and
[223002510210] |<img/>.
[223002510220] |<h3>End of Story</h3>
[223002510230] |This still seems like a lot of work just to get going with random variables.
[223002510240] |We haven’t even defined multivariate densities or conditional and joint probabilities.
[223002510250] |In applied work, we define integrable multivariate density functions explicitly and reason through integration.
[223002510260] |For instance, in the <a>hierarchical batting ability model</a> I discussed as an example of Bayesian inference, the model is fully described by the density
[223002510270] |Technically, we could construct the measure from the density function as follows.
[223002510280] |First, construct the sample space from which the parameters are drawn.
[223002510290] |Continuing the baseball example, we draw our parameter assignment <img/>from the sample space
[223002510300] |<img/>.
[223002510310] |We then take the Lebesgue measurable events <img/>with measure <img/>defined by (multivariate) Lebesgue-Stieltjes integration, 
[223002510320] |where, of course, <img/>.
[223002510330] |If <img/>is a simple hypercube in <img/>, this works out to the usual sum/integral:
[223002510340] |<img/>.
[223002520010] |<title>Coding Inference Talk at University of Chicago, Wed 16 Dec 2009</title>
[223002520020] |<b>Update:</b> It’s still Wednesday, but the right day is <b>16 December</b>.
[223002520030] |This Wednesday, I (Bob) will be giving a talk at the brand-spanking new <a>Knapp Center for Biomedical Discovery</a> at the University of Chicago. 
[223002520040] |<b>When:</b> 2 PM, Wed 16 Dec 2009
[223002520050] |<b>Where:</b> Knapp Center for Biomedical Discovery (KCBD) 10th Floor, South Conference Room 900 East 57th Street University of Chicago
[223002520060] |<h3>Multilevel Models of Coding and Diagnosis with Multiple Tests and No Gold Standards</h3>
[223002520070] |Bob Carpenter, Alias-i
[223002520080] |I’ll introduce multilevel generalizations of some well known models drawn from the epidemiology literature and evaluate their fit to diagnostic testing and linguistic annotation data.
[223002520090] |The analogy is that data annotation for machine learning (or, e.g., ICD-9 coding) is the same kind of process as diagnostic testing.
[223002520100] |The observed data consists of multiple testers supplying results for multiple tested units.
[223002520110] |True labels for some units may be known (perhaps with selection bias), and not all units need to undergo every test.
[223002520120] |In all models, there are parameters for outcome prevalence, the result for each unit, and some form of test accuracy.
[223002520130] |I’ll also consider models with parameters for individual test accuracy and bias (equivalently sensitivity and specificity in the binary case) and item difficulty/severity.
[223002520140] |I’ll focus on the priors for annotator accuracy/bias and item difficulty, showing how diffuse hyperpriors allow them to be effectively inferred along with the other parameters using Gibbs sampling.
[223002520150] |The posterior samples may be used for inferences for diagnostic precision, multiple comparisons of test accuracies, population prevalence, unit-level labels, etc.
[223002520160] |I’ll show that the resulting multilevel models can be fit using data simulated according to the model.
[223002520170] |I will then fit the model to a range of clinical and natural language data.
[223002520180] |I’ll discuss their advantages for inference with epidemiology data ranging from dentists diagnosing caries based on x-rays, oncologists diagnosing tumors based on slides, infection diagnosis based on exams and serum tests, and with natural language data including name spotting, word stemming, and classification.
[223002520190] |I’ll conclude by discussing extensions to further pooling through random effects for different testing facilities, different kinds of annotators (e.g. doctors vs. ICD-9 specialists), different kinds of subjects/units (e.g. genetic predisposition to diseases, or articles drawn from different journals), etc.
[223002520200] |All the software (Java, R, BUGS) and data discussed in this talk are freely available from the <a>LingPipe sandbox</a> in the <tt>hierAnno</tt> project.
[223002520210] |You may already be familiar with all this from the <a>data annotation thread</a> on this blog.
[223002530010] |<title>Multimodal Priors for Binomial Data</title>
[223002530020] |<a>Andrey Rzhetsky</a> gave me some great feedback on my talk at U. Chicago.
[223002530030] |I want to address one of the points he rasied in this blog post:
[223002530040] |<h3>What if the prior is multimodal?</h3>
[223002530050] |This is a reasonable question.
[223002530060] |When you look at the Mechanical Turk annotation data we have, sensitivities and specificities are suggestively multimodal, with the two modes representing the spammers, and what I’ve decided to call “hammers” (because the opposite of “spam” is “ham” in common parlance). 
[223002530070] |Here’s a replay from an earlier post, <a>Filtering Out Bad Annotators</a>:
[223002530080] |The center of each circle represents the sensitivity and specificity of an annotator relative to the gold standard from <a>Snow et al.’s paper on Mech Turk for NLP</a>.
[223002530090] |<h3>Beta Priors are Unimodal or Amodal</h3>
[223002530100] |But a <a>beta distribution</a> <img/>has a single mode at <img/>in the situation where <img/>, but has no modes if <img/>or <img/>.
[223002530110] |<h3>Mixture Priors</h3>
[223002530120] |One possibility would be to use a mixture of two beta distributions, where for <img/>and <img/>, we define:
[223002530130] |<img/>.
[223002530140] |<h3>Hierarchical Fit</h3>
[223002530150] |We can fit the mixture component <img/>along with the parameters of the beta mixture components in the usual way.
[223002530160] |It’s just one more variable to sample in the Gibbs sampler.
[223002530170] |<h3>Hierarchical Priors</h3>
[223002530180] |On the other hand, if you consider <a>baseball batting data</a>, there would be at least two modes in the prior for batting average corresponding to fielding position (i.e. shortstops and second-basemen typically don’t bat as well as outfielders and I imagine there’s more variance in batting ability for infielders).
[223002530190] |If we didn’t know the fielding position, it’d make sense to use a mixture prior.
[223002530200] |But if we knew the fielding position, we’d want to create a hierarchical model with a position prior nested inside of a league prior. 
[223002540010] |<title>NYC NLP/ML Group</title>
[223002540020] |<a>Joseph Turian</a>‘s back in town and has started a mailing list/newsgroup and Twitter feed for natural language processing (NLP) and machine learning (ML) in New York City (NYC):
[223002540030] |<li><a>NY NLP/ML Google Group</a>
[223002540040] |<li><a>NY NLP/ML Twitter Feed</a> 
[223002540050] |Joseph’s trying to organize something like the <a>Foo Camps</a> for NLP and ML programming in NY.
[223002540060] |If you’re interested, drop him a line, or wait for the announcement.
[223002540070] |P.S. Thanks to Joseph for not requiring registration for reading!
[223002540080] |P.P.S. Check out some of <a>Joseph’s latest work</a> surveying features for named entity recognition.
[223002550010] |<title>LREC 2010 Tutorial: Statistical Models of the Annotation Process</title>
[223002550020] |<h3>17 May 2010, Malta</h3>
[223002550030] |<a>Massimo Poesio</a> and I are going to be giving a half-day tutorial at <a>LREC 2010</a> in the afternoon of Monday 17 May 2010.
[223002550040] |The title is Statistical Models of the Annotation Process.
[223002550050] |We’ll be covering most of the material I’ve discussed in this blog’s <a>data annotation thread</a> and more.
[223002550060] |What’s really cool is that it’s in <a>Malta</a>! 
[223002550070] |I’ll be there for most of the <a>LREC 2010 programme</a>.
[223002550080] |I’m particularly excited about the 2nd Workshop on Building and Evaluating Resources for Biomedical Text Mining and the New Challenges for NLP Frameworks Workshop (where by “framework”, they mean tools like GATE and LingPipe).
[223002550090] |I’ve always liked workshops more than conferences.
[223002550100] |<h3>5–6 May 2010, Edinburgh</h3>
[223002550110] |Before Malta, I’ll be in Edinburgh 6–7 May 2010 for a reunion of the department in which I did my Ph.D., the <a>Centre for Cognitivie Science</a> (originally <a>School of Epistemics</a>).
[223002550120] |I’ll be giving a talk on data annotation there, too.
[223002560010] |<title>Blegging for Help: Web Scraping for Content?</title>
[223002560020] |I’m reduced to <a>blegging</a> (a lexical mashup of “blog” and “beg”).
[223002560030] |We run into this problem time and time again and have to tell customers we just don’t know the answer.
[223002560040] |If you do, please help by leaving a comment or <a>send me e-mail</a> and I’ll summarize on the blog.
[223002560050] |<h3>How Can I Scrape Web Content?</h3>
[223002560060] |I really don’t know a good general-purpose method of pulling the content out of arbitrary web pages and leaving the boilerplate, advertising, navigation, etc. behind.
[223002560070] |The research papers I’ve seen look at large corpora of documents and build background models for sites to pick out boilerplate from fresh content. 
[223002560080] |They also resort to techniques like 2D rendering just to put contiguous blocks of HTML together logically.
[223002560090] |Then there’s the problem of pulling out text that’s interrupted by advertisements, photos, figures, quotes, etc. 
[223002560100] |<h3>Yes, I Can Tidy HTML</h3>
[223002560110] |I love tools like <a>NekoHTML</a> that do a reasonable job of converting any old <a>crufty</a> HTML from the web into XHTML so I can parse it with SAX.
[223002560120] |It’s what we use in our <a>web demos</a> for HTML input.
[223002560130] |<h3>No, I Don’t Need Structured Parsing</h3>
[223002560140] |Yes, I know there are tons of things out there that let you build custom rule-based scrapers for particular sites.
[223002560150] |It’s a pain, but we’ve done this for fixed content. 
[223002560160] |But I’m talking about making a query on a search engine and downloading the HTML (or whatever) from the top 500 hits and trying to turn it into something you can feed to a natural language processing system to do something like indexing or information extraction.
[223002560170] |<h3>AJAX and Flash a Plus</h3>
[223002560180] |Just thinking about getting the HTML as rendered given all the AJAX makes my head spin.
[223002560190] |I also hear that Flash allows some kind of searchability now, so there might be relevant text in there. 
[223002560200] |<h3>We’ll Pay</h3>
[223002560210] |If there’s a service out there that does a decent job of this or software we can buy, we’ll gladly pony up.
[223002560220] |It’s not like we want to build this ourselves.
[223002570010] |<title>Kohlschütter, Fankhauser, Nejdl (2010) Boilerplate Detection Using Shallow Text Features</title>
[223002570020] |A lead from my <a>previous post on scraping text out of boilerplate</a> was the following paper, scheduled to be presented next month (specifically, Saturday 6 February 2010) right here in Brooklyn at ACM’s 3rd annual conference on web search and data mining, <a>WSDM 2010</a>:
[223002570030] |<li>Kohlschütter, Christian, Peter Fankhauser, and Wolfgang Nejdl (2010) <a>Boilerplate Detection Using Shallow Text Features</a>.
[223002570040] |In WSDM ’10. 
[223002570050] |<h3>Boilerpipe</h3>
[223002570060] |A java API-based implementation of the system described in the paper is available under a generous Apache 2.0 license</a> from: 
[223002570070] |<li>Google Code: <a>Boilerpipe</a> 
[223002570080] |It uses our favorite normalizer, <a>NekoHTML</a> as a front end.
[223002570090] |I’ll take it out for a spin in a separate review.
[223002570100] |The Java API nature and free licensing make it a very tempting option for the likes of us.
[223002570110] |<h3>The Approach(es)</h3>
[223002570120] |Kohlschütter et al. evaluate a range of features working directly over cleaned HTML for scraping content out of boilerplate like navigation and advertisements. 
[223002570130] |<h3>HTML Only</h3>
[223002570140] |They do not consider HTML rendering solutions, which simplifies but also limits the applicability of the final system.
[223002570150] |Of course, there’s no reason you couldn’t plug in something like <a>Crowbar</a> (thanks for that link, too) and use its HTML instead of the direct download. 
[223002570160] |<h3>Newswire vs. Cleaneval</h3>
[223002570170] |As he pointed out in a comment in the last post, Kohlschütter (and crew) concluded that the <a>Cleaneval bakeoff</a> used highly non-representative web text, and thus wasn’t a good baseline.
[223002570180] |As an alternative, they collected a corpus of 250K English news articles downloaded from <a>Google News</a> links from different countries (USA, Canada, UK, South Africa, India, Australia) in four topics (world. technology, sports, entertainment) from over 7500 different sources. 
[223002570190] |The paper advertises the data’s availability from the following site: 
[223002570200] |<li><a>Boilerpipe Data Site</a> 
[223002570210] |But it’s not there yet (11 January 2010).
[223002570220] |<h3>Four-Way and Two-Way Tasks</h3>
[223002570230] |The authors consider the two-way task of boilerplate versus content and the four-way classification task of boilerplate, full-text/comments, headline, and supplemental.
[223002570240] |<h3>Decision Tree Learner</h3>
[223002570250] |They evaluated decision tree learners, though claim linear SVMs (fit with sequential minimial optimization, aka SMO) had similar performance.
[223002570260] |<h3>Micro-F Evaluation</h3>
[223002570270] |They evaluated on a word-by-word basis.
[223002570280] |This is a kind of micro evaluation.
[223002570290] |A macro evaluation might rank by block.
[223002570300] |<h3>Features</h3>
[223002570310] |The authors didn’t consider structure other than H, P, DIV, and A.
[223002570320] |The features that seemed to work involved number of words and density of text relative to links. 
[223002570330] |The only global features they use of a collection are the global word frequencies (thus getting at something like stop list type features).
[223002570340] |They consider all sorts of local features, such as average word length, total number of words, average sentence length (using a simple heuristic sentence detector), ratio of periods to other characters, number of capitalized words and ratio of capitalized to non-capitalized words, etc. etc. 
[223002570350] |One of their most useful features is link density, which is number of words in anchor (A) spans compared to total number of words.
[223002570360] |They also consider position in the document, though this is tricky with only the raw HTML rather than the rendered output, as relative locations may change visually relative to the underlying HTML.
[223002570370] |<h3>Quotients Features and Context</h3>
[223002570380] |The authors extract these basic features from blocks, but then use the current (C), previous (P), and next (N) values in classification.
[223002570390] |Specifically, they find it useful to look at the quotient of the number of words in the previous block to the current block (their notation “P/C”). 
[223002570400] |The authors say “the text flow capturing variants of thse features (number of words quotient, text density quotient, …), which relate the value of the current block to the previous one, provide the highest information gain, indicating that intradocument context plays an important role”. 
[223002570410] |It’d be nice if these papers came with a table of features with simple definitions to make it easy for someone to browse them.
[223002570420] |<h3>Sequence Model Decoding?</h3>
[223002570430] |The classification in this paper is apparently done independently in a block-by-block fashion.
[223002570440] |I’d think using a sequence model like structured SVMs or CRFs would provide higher accuracy.
[223002570450] |Given the small number of categories (i.e. boilerplate/not), it’d be very speedy, too, even with second-order models.
[223002570460] |<h3>(Greedy) Information Gain</h3>
[223002570470] |The authors rank features by <a>information gain</a>.
[223002570480] |The big winners are number of words quotient, text density quotient, number of words, and the link and text densities.
[223002570490] |Clearly these are related measures, but it’s prohibitive to consider all the possible subsets of features.
[223002570500] |<h3>Conclusions</h3>
[223002570510] |They conclude word count is most important.
[223002570520] |Coupled with link density, you’re most of the way to the best results achieved using all local features plus global frequency.
[223002570530] |<h3>Or, Ask Ryan</h3>
[223002570540] |<a>Ryan Nitz</a>, enterprise programmer <a>par excellence</a>, just happened to be over for dinner last night.
[223002570550] |I asked him if he’d dealt with this problem and he said he just used the ratio of punctuation to letters.
[223002570560] |That seems similar to but simpler and more portable than the stopword approach Aria Haghighi suggested in a comment in the last post. 
[223002580010] |<title>Nobel (Memorial) Prize for Logistic Regression (aka Discrete Choice Analysis)</title>
[223002580020] |I’ve been meaning to blog on this topic ever since <a>Dave Lewis</a> was in town giving a talk to the Columbia stat student seminar.
[223002580030] |He was talking about one of his favorite topics, (Bayesian) logistic regression.
[223002580040] |It also fits in with (another) one of my favorite topics, the <a>scientific zeitgeist</a>.
[223002580050] |As Andrew Gelman once said (and I paraphrase), no matter what model you come up with, someone in psychometrics thought it up 50 years ago (or maybe it was econometrics).
[223002580060] |<h3>Multinomial Regression</h3>
[223002580070] |For simplicitly, we’ll stick to the simple multinomial regression case where we have <img/>possible output categories.
[223002580080] |Our training data then consists of <img/>input/output pairs <img/>, where the input <img/>is any old object and the output category <img/>. 
[223002580090] |<h3>“Max Ent” Feature Extraction</h3>
[223002580100] |In the maximum entropy style presentations, there is a feature function <img/>from pairs of inputs and output categories to <img/>-dimensional feature vectors, so <img/>for <img/>. 
[223002580110] |The model consists of (the feature extractors and) a single coefficient vector <img/>.
[223002580120] |The probability that an input <img/>is categorized as category <img/>is then
[223002580130] |<img/>,
[223002580140] |where, as usual, the normalizing constant is computed by summation:
[223002580150] |<img/>.
[223002580160] |The thing to notice here is that a feature in the same position can be produced by the same input in two different categories.
[223002580170] |<h3>Stats Textbook Feature Extraction</h3>
[223002580180] |If you pull out a statistics textbook, you’ll see feature extraction for multinomial logistic regression presented rather differently.
[223002580190] |In this setting, we have a feature extractor <img/>that works only on input categories, producing an <img/>-dimensional feature vector that does not depend on the output category, <img/>.
[223002580200] |The model then consists of a <img/>-dimensional coefficient vector <img/>for each output category <img/>.
[223002580210] |The category probability is then defined by
[223002580220] |<img/>, 
[223002580230] |with normalizer computed in the usual way:
[223002580240] |<img/>.
[223002580250] |Here, the vector for each output category is distinct, so there’s no (direct) way to produce the same feature (after multiplication with coefficient) from the same input for two different categories.
[223002580260] |<h3>LingPipe’s Approach</h3>
[223002580270] |LingPipe adopts the stats textbook approach for both logistic regression and CRFs.
[223002580280] |Mainly because it’s more efficient and I couldn’t find good enough reasons to go with the max ent approach.
[223002580290] |I tried to squeeze examples out of people at conferences, via e-mail, over meals, and when I <a>blogged about label-specific features for CRFs</a>!
[223002580300] |As is also the case in most stats textbook presentations, without loss of generality (for inference), one of the output category coefficient vectors can be set to zero.
[223002580310] |It’s actually required to identify a unique solution, because we can always add or subtract constants from all vectors without changing the predictions. 
[223002580320] |With priors on the coefficients, you can get a different result pegging one category to zero, so it makes most sense to do this transformation after fitting.
[223002580330] |LingPipe does it before fitting, which isn’t the way I’d do it if I had a do-over.
[223002580340] |On the other hand, it works well for binary classification problems when everyone uses one coefficient vector (though again, results vary with Gaussian priors because of their non-linearity).
[223002580350] |<h3>Stats Text to Max Ent Conversion</h3>
[223002580360] |The conversion from the stats textbook version to the max ent version is simple.
[223002580370] |We just define <img/>to be the concatenation of the <img/>, setting
[223002580380] |<img/>.
[223002580390] |For the feature function, we just define it to only set non-zero values in the appropriate range, with
[223002580400] |<img/>,
[223002580410] |where we take <img/>to be the <img/>-dimensional zero vector, and <img/>to be <img/>instances of the zero vector concatenated. 
[223002580420] |We get the same result after the translation, because
[223002580430] |<img/>.
[223002580440] |<h3>Max Ent to Stats Text Conversion</h3>
[223002580450] |Uh oh.
[223002580460] |This isn’t so easy.
[223002580470] |The problem is that in the max ent presentation, we can have the same feature generated for several different categories.
[223002580480] |In the stats textbook presentation, each feature is implicitly separated because the coefficients are separated.
[223002580490] |The solution is to allow tying of coefficients in the stats textbook model.
[223002580500] |That is, we need to be able to enforce <img/>for arbitrary pairs of coefficient positions.
[223002580510] |Then, we just put the tied features there.
[223002580520] |(It’s hard to write out as a formula, but hopefully the idea’s clear.)
[223002580530] |<h3>Worth a Nobel (Memorial) Prize in Econ?</h3>
[223002580540] |<a>Daniel McFadden</a> was awarded (half the) <a>2000 Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel</a> for work he’d done on <a>discrete choice analysis</a> (DCA). 
[223002580550] |As you may have guessed from the lead in, DCA’s just the term researchers in econometrics use for logistic regression.
[223002580560] |As Dave pointed out in his talk, they tend to use it in the same way as computational linguists working in the max ent tradition, with lots of feature tying. 
[223002580570] |McFadden lists his <a>1974 paper on logit</a> as his first econometrics publication on <a>his list of publications</a> (he’s still teaching intro stats at Berkeley!).
[223002580580] |The key definition is formula (12) on page 110, where he gives the probability function for multinomial logistic regression and uses max-ent style feature extraction. 
[223002580590] |It’s clear from McFadden’s extensive references that statisticians had been fitting binomial logistic regressions since 1950 and multinomials since 1960. 
[223002580600] |Perhaps not coincidentally, McFadden was working on DCA about the same time Nelder and Wedderburn introduced <a>generalized linear models</a> (GLM), which generalize logistic regression to other link functions.
[223002590010] |<title>Discrete Choice Analysis Example: Transportation Mode</title>
[223002590020] |I forgot to include the example in yesterday’s post.
[223002590030] |I’m reconstructing this from memory, so it doesn’t exactly match the one Dave Lewis used in his talk.
[223002590040] |Suppose you have a decision to make among different modes of transportation to get you from home to work: car, bus, train, bicycle, walking.
[223002590050] |Each will come with a cost in dollars and time (and risk, but I’ll leave that to <a>Professor Risk</a>).
[223002590060] |It makes sense to tie the parameters for cost and for time across the different modes of transportation.
[223002590070] |We’ll use dimension 1 of our feature vectors for time (in minutes) and dimension 2 for money (in US dollars).
[223002590080] |For instance, <img/>represents a mode of transportation for a person that takes 15 minutes and costs one dollar.
[223002590090] |It’s statistics, so in order to fit a model, we need exchangeable replicates.
[223002590100] |In this case, we use multiple commuters.
[223002590110] |For instance, suppose we consider commuter <img/>, for whom walking takes 30 minutes, and has no cost, taking the bus takes 20 minutes and costs $2, and driving takes 10 minutes and costs $5.
[223002590120] |With our simple model of transportation choice, we represent the three outcomes for commuter <img/>as
[223002590130] |<img/>for walking,
[223002590140] |<img/>for taking the bus, and 
[223002590150] |<img/>for driving.
[223002590160] |We might then have a second person <img/>who lives further from work, with features
[223002590170] |<img/>for walking, 
[223002590180] |<img/>for the bus, and 
[223002590190] |<img/>for driving. 
[223002590200] |The model parameters are the two coefficients for minutes and dollars, yielding a 2D vector <img/>.
[223002590210] |Suppose we have fit a model (presumably with a well-defined prior), and want to look at predictions.
[223002590220] |For person <img/>we get probabilities for choice of transportation mode
[223002590230] |<img/>for walking,
[223002590240] |<img/>for busing, and
[223002590250] |<img/>for driving.
[223002590260] |This all fits very neatly into the max-ent or DCA style of generating features for a multinomial logistic model.
[223002590270] |It even seems easier to conceptualize in this case than tied parameters. 
[223002590280] |Of course, if we really wanted to model commuter choices, we’d use a much more complex model including features like (disposable) income, neighborhood, etc., plus some non-linear combinations of existing features.
[223002590290] |All of these need not be shared across choices like time and money.
[223002600010] |<title>Maximum Likelihood Estimates of Expression in RNA-Seq are Winner-Take-All Biased</title>
[223002600020] |<em><strong>Update:</strong> I turned the crank a little too hard on this post.
[223002600030] |While it’s technically correct according to one way of interpreting maximum likelihood, the more standard approach does <strong>not</strong> suffer the same bias.
[223002600040] |I describe the “right” way to do EM in the followup post, </em>
[223002600050] |<li><em><a>Marginalizing Latent Variables in EM</a>.</em></li> 
[223002600060] |<em>While this is good news for EM (and RNA-Seq), it undercuts one of the motivations for the Bayesian estimator, which I’ll present soon.</em>
[223002600070] |I spent much of the winter break looking over Mitzi’s shoulder at papers on <a>RNA-Seq</a>.
[223002600080] |For those who don’t know what that it is, I added an appendix <a>Background on RNA-Seq</a> going over the problems.
[223002600090] |<h3>Statistical Problem Synopsis</h3>
[223002600100] |As usual, the problem is that the MLE falls on the parameter space boundary.
[223002600110] |Because of this, the MLE has what is known as <a>statistical bias</a>.
[223002600120] |In the case of MLEs for RNA-Seq expression, the bias is toward a winner-take-all solution in which one isoform is assigned all the uncertain mappings.
[223002600130] |<h3>You’ve Seen Biased MLEs Before</h3>
[223002600140] |You’ve seen it in the context of estimating the variance of a distribution from samples <img/>.
[223002600150] |The maximum likelihood estimate <img/>of the mean is the same as the unbiased estimate <img/>,
[223002600160] |<img/>.
[223002600170] |But the maximum likelihood estimate <img/>of variance is biased:
[223002600180] |<img/>.
[223002600190] |It’s biased on the low side (because it’s based on the estimate of the mean, not the actual mean).
[223002600200] |The unbiased estimate arises by subtracting one from the denominator,
[223002600210] |<img/>.
[223002600220] |But unlike the case for expression I’ll discuss next, as the sample size approaches infinity, the unbiased and MLE estimates of variance converge to the same value.
[223002600230] |<h3>Isoform Expression Example</h3>
[223002600240] |Suppose I have a gene with two isoforms, A and B, spliced from three exons, 1, 2, and 3.
[223002600250] |For simplicitly, we’ll suppose all the exons are the same length.
[223002600260] |Suppose isoform A is made up of exon 1 and exon 2, and isoform B of exon 1 and 3.
[223002600270] |Now suppose that you run your RNA-Seq experiment and find 70 reads mapping to exon 1, 20 reads mapping to exon 2, and 50 reads mapping to exon 3.
[223002600280] |In table form, we have the following mapping counts:
[223002600290] |The 20 reads mapping to exon 2 must be part of isoform 1, and similarly the 50 reads mapping to exon 3 must belong to isoform 2.
[223002600300] |That leaves the 70 reads falling in exon 1 to spread in some proportion between isoform 1 and isoform 2.
[223002600310] |So we’ve let N represent the total (out of 70) number of multi-mapped reads assigned to isoform 1.
[223002600320] |<h3>Calculating Expression and Likelihood</h3>
[223002600330] |For a given value of <img/>, we can directly calculate the maximum likelihood estimate for isoform expression for isoform 1 (<img/>) and isoform 2 (<img/>), by
[223002600340] |<img/>and <img/>.
[223002600350] |The (unnormalized) likelihood function for <img/>, which determines <img/>, is
[223002600360] |and the (unnormalized) log likelihood is
[223002600370] |<img/>.
[223002600380] |Here’s a plot of the (unnormalized) log likelihood versus N that illustrates the problem with the MLE estimator:
[223002600390] |The maximum likelihood (which is at the same point as the maximum of the unnormalized likelihood) is achieved at the boundary of the possible parameter values, so the MLE is <img/>.
[223002600400] |The MLE thus assigns all the multi-mapped reads to the second isoform, which is why I called it a “winner take all bias”.
[223002600410] |The unbiased estimator is the expected value of N,
[223002600420] |<img/>,
[223002600430] |which will obviously fall somewhere between 0 and 70, but closer to 0 than 70 given the skew of the likelihood function.
[223002600440] |Just to be clear, it’s not just the MLE that’s a problem.
[223002600450] |Maximum a posteriori (MAP) estimates, which use Bayesian priors but not Bayesian estimators, have the same problem.
[223002600460] |<h3>Who’s using MLE and MAP?</h3>
[223002600470] |It’s actually even more popular in biology than in computational linguistics.
[223002600480] |And while there’s not much that’s been published on RNA-Seq expression profiling, I know these three papers (and would be glad to hear about more):
[223002600490] |<li>de Hoon, Michiel J. L. et al. (2010) <a>Cross-mapping and the identification of editing sites in mature microRNAs in high-throughput sequencing libraries.</a>
[223002600500] |<em>Genome Research</em>.</li>
[223002600510] |<li>Marioni, John C. et al. (2009) <a>RNA-seq: an assessment of technical reproducibility and comparison with gene expression arrays</a>.
[223002600520] |<em>Genome Research</em>.</li>
[223002600530] |<li>Jiang, Hui et al. (2009) <a>Statistical inferences for isoform expression in RNA-Seq</a>.
[223002600540] |<em>Bioinformatics</em>.</li> 
[223002600550] |Ironically, MLE is being sold as an improvement to the one-step remapping approach outlined in the following two papers, the first of which overlaps significantly in authorship with the de Hoon et al. paper cited above:
[223002600560] |<li>Hashimoto, T. et al. (2009) <a>Probabilistic resolution of multi-mapping reads in massively parallel sequencing data using MuMRescueLite</a>.
[223002600570] |<em>Bioinformatics</em></li>
[223002600580] |<li>Mortazavi, A. et al. (2009) <a>Mapping and quantifying mammalian transcriptomes by RNA-Seq</a>.
[223002600590] |<em>Nature Methods</em>.</li> 
[223002600600] |While I like the fact that the former papers write down a full generative model, I say “ironically”, because the one-step remapping approach gets the “right” answer for the example above.
[223002600610] |The remapping of multi-maps by Mortazavi et al. is done proportionally to the expression computed over the uniquely mapped reads.
[223002600620] |In our example, that’s 20 to 50, so the 70 multi-mapped reads are split in the same proportion, with 20 going to isoform 1 and 50 to isoform 2, giving isoform 1 an expression of 40 and isoform 2 an expression of 100.
[223002600630] |<h3>Stay Tuned for the Next Installment</h3>
[223002600640] |In the next post in this series, I’ll show how to estimate the full Bayesian posterior using Gibbs sampling, incorporating probabilistic information from alignment.
[223002600650] |From the Bayesian posterior, unbiased point estimate is easily derived as is estimation variance (i.e. “confidence”).
[223002600660] |I’ll even show how to derive answers when there are no multi-mapped reads, and when exons and isoforms are of different sizes.
[223002600670] |<h3>Background on RNA-Seq</h3>
[223002600680] |For mammalian (and other complex) genomes, genes are made up of <a>exons</a> (of a few dozen to a few hundred bases) and <a>introns</a> (from very small to tens of thousands of bases in humans).
[223002600690] |<a>RNA</a> is <a>transcribed</a> from a gene’s <a>DNA</a>.
[223002600700] |After transcription, the <a>spliceosome</a> chops out the introns and splices the exons together, adds a cap on the 5′ end (start) and a sequence of A bases (the <a>poly(A) tail</a>) on the 3′ end (end).
[223002600710] |The result is so-called mature <a>mRNA</a> (messenger RNA), because it is ready to be <a>translated</a> into a <a>protein</a>.
[223002600720] |The spliceosome, for various not fully understood reasons (including regulation, cryptic [ambiguous] splice junctions, and perhaps chromatin structure), does not always splice all of the exons together to form mRNA.
[223002600730] |In different contexts, <a>alternative splicing variants</a>, the variant proteins produced from which are called <a>isoforms</a>, are generated at different levels of expression (concentration).
[223002600740] |The <a>ribosome</a> complex translates mature <a>mRNA</a> (which has four bases) into the 20 different <a>amino acids</a> making up <a>proteins</a> Three bases, together called a <a>codon</a>, are used per amino acid, with the so-called genetic code mapping codons to amino acids; there is also a start codon and stop codon so the ribosome knows where to start and end translation.
[223002600750] |The (short) portions of the mRNA before the start codon is called the <a>5′ UTR</a>, and the portion of mRNA between the stop codon and the poly(A) tail is called the <a>3′ UTR</a>.
[223002600760] |In RNA-Seq experiments, mature mRNA is isolated in the lab (typically by grabbing its poly(A) tail), then broken up into short sequences using specialized enzymes called <a>RNases</a>.
[223002600770] |The resulting short sequences are then copied to <a>complementary DNA</a> (cDNA), tens of millions short sequences which are then randomly attached to a slide (how this is done depends on the particular <a>sequencer</a>).
[223002600780] |Then the sequencer reads the bases, which is a very noisy process; if you’re lucky, you get confidence scores along with the reads that can be interpreted as probabilities of errors.
[223002600790] |The different machines have different error profiles.
[223002600800] |We now have tens of millions of noisily read sequences.
[223002600810] |These are next <a>mapped</a> to known genome positions using a combination of indexing and edit distance (there are some really groovy algorithms here; more on those later).
[223002600820] |Reads that map to one position with a higher score than all other positions are said to map uniquely (though they may map to other positions with lower likelihood).
[223002600830] |Reads that map to multiple positions are called multi-maps.
[223002600840] |The <a>genome</a> (drafts) have been marked up for exons (though this is also noisy) in what are called gene models (no Wikipedia ref I could find!).
[223002600850] |Multi-maps are very common if the target is an isoform, because isoforms share exons.
[223002600860] |But they also appear elsewhere because of the large number of <a>paralogs</a> (similar sequences) in copies and copy variants of genes in large genomes like those of mammals.
[223002600870] |The problem we’re looking at here is calculating isoform expression taking into account multi-maps.
[223002610010] |<title>DCA for Discriminative Coreference Resolution</title>
[223002610020] |<h3>DCA isn’t Just Tied Logistic Regression</h3>
[223002610030] |After <a>posting about discrete choice analysis</a> (DCA) a few days ago, then adding a <a>post about analyzing transportation choices</a>, it occurred to me that DCA isn’t really just a form of logistic regression with parameter tying in its most general form.
[223002610040] |In its most general form, any number of choices can be presented at run time, whereas in both the machine-learning max-ent style approaches and the stats textbook type approaches to logistic regression, there is always a fixed, finite set of outcome categories.
[223002610050] |<h3>DCA for Within-Document Coreference</h3>
[223002610060] |One of the projects on our plate right now involves within-document <a>coreference resolution</a>, which involves resolving which noun phrases in a document refer to the same entities.
[223002610070] |Thus it’s a bit more general than the classical <a>anaphora resolution</a> problem, which finds antecedents for pronouns.
[223002610080] |In our case, two mentions of “John Smith” in the same document need to be linked (if they refer to the same person; they won’t if you’re reading Amit Bagga and Breck’ss <a>John Smith resolution paper</a>, or for that matter, the recreation of their results in LingPipe’s <a>clustering tutorial</a>).
[223002610090] |<a>LingPipe’s heuristic coreference package</a> is based on Breck’s thesis work (called <a>CogNIAC</a>).
[223002610100] |If you troll through the code or read Breck’s paper, you’ll see that it’s essentially a greedy online algorithm that visits the entity mentions in a document in order, and for each mention either links it to a previous linked chain of mentions, or it starts a new chain consisting only of the current mention.
[223002610110] |Essentially, it’s a greedy online clustering algorithm.
[223002610120] |The resolution of a mention is guided by matchers and anti-matchers that score candidate antecedent mention chains based on properties such as the closest matching alias (using a complex comparison allowing for missing tokens), known alias associations, discourse proximity (how far away the last mention in a chain is and how many are intervening), entity type (person, location, and ogranization, and for persons, gender). 
[223002610130] |So far, there’s nothing for linking common nouns (as there is in ACE), and nothing for linking compound entities (e.g. “John and Mary …They …”).
[223002610140] |<h3>A DCA Model</h3>
[223002610150] |We could just throw all those features into a DCA type model!
[223002610160] |The discrete choices consist of each candidate antecedent mention chain along with the choice of creating a new mention chain.
[223002610170] |If we can extract a feature vector <img/>given a mention chain <img/>and mention <img/>, we’re in business.
[223002610180] |We could potentially even use the other mention chains in generating the features for mention <img/>, as in <img/>where <img/>is the set of previous mention chains, <img/>is the candidate mention chain, and <img/>is the mention being resolved.
[223002610190] |With all existing mention chains in play, we can also generate a reasonable feature vector <img/>for the choice of creating a new mention chain out of <img/>given the antecedent candidates <img/>.
[223002610200] |The model consists of a coefficient vector <img/>.
[223002610210] |Given a mention <img/>and set of potential antecedent chains <img/>, the probability of a given antecedent is defined in the usual way for log-linear logistic-type models.
[223002610220] |For linking to an antecedent chain <img/>, we have
[223002610230] |<img/>.
[223002610240] |For a new chain, which we’ll write <img/>, we have
[223002610250] |<img/>.
[223002610260] |Given annotated data and a feature extractor, the training cases easy to create.
[223002610270] |Each instance consists of the features for all previous mention chains and for creating a fresh along with the decision. 
[223002610280] |<h3>Does Any NLP Package Implement DCA?</h3>
[223002610290] |Alas, LingPipe can’t handle these models the way I wrote logistic regression.
[223002610300] |In fact, I’m not sure anyone’s NLP package can handle the full DCA type models. 
[223002610310] |I’m afraid I can never quite figure out from the <a>Mallet javadoc</a> what exactly it can and can’t do because everything’s so abstract and there are so many implementations of the interfaces and so little high-level doc.
[223002610320] |But classes like <a><code>cc.mallet.classify.MaxEnt</code></a> seem to assume a fixed set of output categories. 
[223002610330] |The <a>Open NLP javadoc</a> is much more straightforward; their <a><code>opennlp.maxent.GISModel</code></a> also requires a fixed set of categories.
[223002610340] |It also doesn’t look like Weka supports DCA-style models from the <a>Weka Javadoc</a>, but again, the interfaces are so general, and the implementations so plentiful, I’m not sure.
[223002610350] |I’d love to hear about which packages do support this kind of thing.
[223002610360] |Presumably something the econometricians are using would do it.
[223002610370] |<h3>Implementing DCA with SGD</h3>
[223002610380] |DCA won’t be at all hard to write.
[223002610390] |In fact, having just finished CRFs (stay tuned for the release, probably next week).
[223002610400] |Stochastic gradient descent (or a quasi-Newton method) is easy to adapt.
[223002610410] |The correct antecedent candidate or choice to create a new chain is treated as a positive (1) outcome, with all other candidate antecedent mention chains treated as negative (0) outcomes. 
[223002610420] |<h3>Coefficient Priors</h3>
[223002610430] |Of course, we can put priors on the coefficients.
[223002610440] |It sure would be nice to be able to create Bayesian estimators.
[223002610450] |Having just blogged about <a>MLE and MAP’s bias</a>, I’m worried about the MAP estimates for logistic regression all these systems (including LingPipe) use.
[223002610460] |<h3>OK, you could use SVMs, too</h3>
[223002610470] |Of course, SVM (hinge), perceptron (0/1), or other simple loss functions could be used instead of the logistic loss function.
[223002610480] |SGD will still work as is.
[223002610490] |And you could use non-linear kernels, which often squeeze a bit more accuracy out for very little work (contrasted with hand tuning non-linear features, such as interaction features, in a standard linear model).
[223002610500] |<h3>Coreference Training Data?</h3>
[223002610510] |Well, there was <a>MUC 7</a> which kicked things off, and then <a>ACE</a> more recently.
[223002610520] |MUC-6 and MUC-7 and several years of ACE datasets are available from the <a>LDC</a> for a fee.
[223002610530] |A couple months ago, I blogged about Massimo Poesio et al.’s effort to <a>collect a coreference corpus</a> using the <a>Phrase Detectives</a> annotation as game.
[223002610540] |This should be out soon, and be much larger than the MUC and ACE datasets.
[223002620010] |<title>Marginalizing Latent Variables in EM</title>
[223002620020] |<img/>After getting carried away in my last post on this topic, <a>Maximum Likelihood Estimates of Expression in RNA-Seq are Winner-Take-All Biased</a>, I want to explain what went wrong when I “turned the crank” (an idiom in mathematics for solving an equation by brute force without thinking too much about it).
[223002620030] |<h3>Expression Mixture Model</h3>
[223002620040] |Recall that we were looking at a mixture model, which is the bread and butter of maximum likelihood estimators like EM.
[223002620050] |We defined a joint likelihood function for a sequence of observed reads <img/>, gene or splice variant sources <img/>, and mRNA expression <img/>, setting
[223002620060] |<img/>.
[223002620070] |<h3>Maximum Likelihood</h3>
[223002620080] |Maximum likelihood is usually stated as finding the model parameters that maximize the likelihood function consisting of the probability of the observed data given the model parameters.
[223002620090] |<h3>What’s a Parameter?</h3>
[223002620100] |So that’s what I did, calculating
[223002620110] |<img/>.
[223002620120] |The problem is that there’s an implicit “except the latent parameters” inside the usual understanding the MLE.
[223002620130] |What I should have done is marginalized out the latent gene sources <img/>, taking
[223002620140] |<img/>.
[223002620150] |That requires marginalizing out the latent mapping of reads <img/>to gene or splice variant sources <img/>,
[223002620160] |<img/>.
[223002620170] |On a log scale, that’s
[223002620180] |<img/>.
[223002620190] |<h3>The Example</h3>
[223002620200] |I’ll repeat the example here for convenience:
[223002620210] |<h3>Isoform Expression Example</h3>
[223002620220] |Suppose I have a gene with two isoforms, A and B, spliced from three exons, 1, 2, and 3.
[223002620230] |For simplicitly, we’ll suppose all the exons are the same length.
[223002620240] |Suppose isoform A is made up of exon 1 and exon 2, and isoform B of exon 1 and 3.
[223002620250] |Now suppose that you run your RNA-Seq experiment and find 70 reads mapping to exon 1, 20 reads mapping to exon 2, and 50 reads mapping to exon 3.
[223002620260] |In table form, we have the following mapping counts:
[223002620270] |The 20 reads mapping to exon 2 must be part of isoform 1, and similarly the 50 reads mapping to exon 3 must belong to isoform 2.
[223002620280] |That leaves the 70 reads falling in exon 1 to spread in some proportion between isoform 1 and isoform 2.
[223002620290] |<h3>Turning the Crank In the Right Direction</h3>
[223002620300] |By assuming each splice variant consists of two exons of the same length, the probability of a read in an exon is 1/2 for each exon in the splice variant and 0 for the exon not in the variant.
[223002620310] |Now when we turn the crank, we see that
[223002620320] |<img/>.
[223002620330] |The reduction on the third line is because the probability of a read in the second exon, <img/>, is only non-zero for isoform <img/>, and similarly for a read in the third exon, where <img/>is nly non-zero for the second gene or splice variant, <img/>.
[223002620340] |The final reduction follows because <img/>.
[223002620350] |<h3>Not so Biased After All</h3>
[223002620360] |After marginalizing out the read mappings <img/>, the MLE for expression is right where we’d expect it, at the solution of
[223002620370] |<img/>,
[223002620380] |which is
[223002620390] |<img/>.
[223002620400] |It turns out EM isn’t so biased for these discrete mixtures, at least when you turn the crank the right way.
[223002630010] |<title>Dekel and Shamir (2009) Vox Populi: Collecting High-Quality Labels from a Crowd</title>
[223002630020] |Aleks just sent me a pointer to this paper from last year’s COLT:
[223002630030] |<li>Dekel, Ofer and Ohad Shamir. 2009.
[223002630040] |<a>Vox Populi: Collecting High-Quality Labels from a Crowd</a>.
[223002630050] |In COLT. 
[223002630060] |The paper presents, proves theorems about, and evaluates a very simple idea in the context of crowdsourcing binary classifier data coding.
[223002630070] |Unlike <a>other approaches I’ve blogged about</a>, Dekel and Shamir use <b>only one coder per item</b>, and often coders only label a handful of items. 
[223002630080] |They train an SVM on all the labels, then use the SVM to evaluate coders.
[223002630090] |They then prune out low-quality coders using the SVM as a reference. 
[223002630100] |This paper reminded me of <a>(Brodley and Friedl 1999)</a>, which was also about using multiple trained classifiers to remove bad labels.
[223002630110] |Brodley and Friedl remove items on an item by item basis rather than on an annotator by annotator basis.
[223002630120] |This paper is also somewhat reminiscent of <a>(Raykar et al. 2009)</a>, who train a classifier and use it as another annotator. 
[223002630130] |<h3>Lots of Theory</h3>
[223002630140] |There’s lots of theory saying why this’ll work.
[223002630150] |It is a COLT paper after all.
[223002630160] |<h3>Evaluation: Web Page Query Relevance</h3>
[223002630170] |They ran an eval on Amazon’s Mechanical Turk asking people to judge a pair consisting of a web query and web page as to whether the page is relevant to the query. 
[223002630180] |They used 15 coders per query/page pair in order to define a gold standard by voting.
[223002630190] |They then evaluated their approach using only one coder per item by subsampling their larger data set.
[223002630200] |One thing I noticed is that as they lowered the maximum number of items labeled by an annotator, their average annotator accuracy went up.
[223002630210] |This is consistent with our findings and those in Snow et al. that the spammy Mechanical Turkers complete a disproportionate number of tasks.
[223002630220] |With only one coder per item, Dekel and Shamir can’t evaluate the way everyone else is evaluating crowdsourcing, because they know their resulting data will remain noisy because it’s only singly annotated. 
[223002630230] |Estimates of coder sensitivity and specificity could be made based on their performance relative to the SVM’s best guesses.
[223002630240] |That’d provide some handle on final corpus quality in terms of false positives and negatives relative to ground truth.
[223002630250] |Rather than evaluating trained classifier performance, Dekel and Shamir measure the “noise level” of the resulting data set after pruning.
[223002630260] |What we really care about in practice is how much pruning bad annotators helps train a more reliable classifier (or help evaluate if that’s the goal).
[223002630270] |They discuss this kind of end-to-end evaluation under “future work”!
[223002630280] |It’s really striking how different the evaluation versus theory requirements are for different conferences.
[223002650010] |<title>Comparing Precision-Recall Curves the Bayesian Way?</title>
[223002650020] |<h3>Back Story</h3>
[223002650030] |There’s an interesting thread on the <a>BioNLP mailing list</a> (here’s a link to the <a>publicly readable thread</a>).
[223002650040] |The thread was kicked off when <a>Andrew Clegg</a> asked:
[223002650050] |Suppose I have two precision-recall curves for two different IR algorithms on the same test data and query.
[223002650060] |What would be the correct statistical test to determine if they are significantly different? 
[223002650070] |I’m particularly sympathetic to (part of) <a>Bill Hersh</a>‘s second response.
[223002650080] |…All statistical inference tells you is how likely your differences are due to chance.
[223002650090] |It says nothing about whether the difference is important. …
[223002650100] |to which Andrew replied 
[223002650110] |…in my case it’s the other way round, I think we’ve already displayed a clear benefit in terms of usability, I’m just thinking of including significance testing in case a very picky reviewer asks if it’s down to chance. 
[223002650120] |Can you say <a>CYA</a>?
[223002650130] |There were a host of classical tests proposed including the new-to-me <a>Page trend test</a>.
[223002650140] |Others suggesting taking an aggregate statistic like area-under-the-curve and doing a standard difference test. 
[223002650150] |<h3>ROC Curves vs. PR Curves</h3>
[223002650160] |There’s much more literature on <a>receiver operating characteristic curves</a> (aka ROC curves) than precision-recall (PR) curves.
[223002650170] |Just as a refresher, if we take a given number of true positives (TP), false positives (FP), true negatives (TN), and false negatives (FN), precision, recall, sensitivity and specificity are:
[223002650180] |Sensitivity = TP / (TP + FN)
[223002650190] |Specificity = TN / (TN + FP)
[223002650200] |Recall = Sensitivity = TP / (TP + FN)
[223002650210] |Precision = TP / (TP + FP)
[223002650220] |If we have a ranked list of outputs for which we know their gold-standard category (relevant or not in the case of IR), we can consider initial segments of the ranked list and compute the precision/recall at that point.
[223002650230] |The ROC curve plots 1-specificity (the false positive rate) versus sensitivity (the true positive rate) at various operating points for an algorithm.
[223002650240] |The PR curve plots precision versus recall. 
[223002650250] |In PR curves, it is often the case that only “interpolated” results are considered, which means taking the convex shell of the curve.
[223002650260] |This is easily accomplished by making sure the function is non-decreasing by propagating later higher results back.
[223002650270] |For instance, if precision at 1 recall is 1/2 and precision at 2 recall is 2/3 and at 3 recall is 1/2, then the precision at 1 recall is interpolated to 2/3 so the function is non-decreasing.
[223002650280] |(I’m not sure what this does to hypothesis testing.)
[223002650290] |There’s a lot more information and examples in the class documentation for
[223002650300] |<li>LingPipe’s <a><code>classify.ScoredPrecisionRecallEvaluation</code></a> 
[223002650310] |<h3>The Bayesian Way</h3>
[223002650320] |It’s in exactly these kinds of situations where a Bayesian approach seems natural.
[223002650330] |Just add a prior and compute a posterior over entire PR curves.
[223002650340] |Then compare the PR curves any way you want.
[223002650350] |Say by calculating how likely it is for one PR curve to be above the other at every operating point.
[223002650360] |Or how likely it is for one to be above the other at a given operating point (say 99% recall).
[223002650370] |Or how likely one is to be substantially better than another, or how much you expect one to be higher than another. 
[223002650380] |See my earlier post on <a>Bayesian counterpart to Fisher’s exact test on contingency table data</a>.
[223002650390] |The nifty part is that “adjustments” for multiple comparisons are built in.
[223002650400] |So we can ask what’s the posterior probability of one system having at least 1% higher precision than all others at 99% recall. 
[223002650410] |But once we’re doing multiple comparisons, it makes sense to build a hierarchical model.
[223002650420] |Often, a system will report results on multiple queries, so there’s a set of precision-recall curves for each system, leading to two levels of grouping.
[223002650430] |I provide an example of Bayesian multiple comparisons in a hierarchical model in my earlier blog post on <a>Bayesian batting ability with multiple comparisons</a>.
[223002650440] |<h3>Will it Work?</h3>
[223002650450] |How do I model the posterior PR (or ROC) curve?
[223002650460] |From that, a regular or interpolated PR (or ROC) curve can be generated if desired.
[223002650470] |I’m specifically worried about precision and recall sharing the TP term in their numerators and denominators; ROC curves seem simpler.
[223002650480] |I’m also worried about the low counts at the low recall end of the curves. 
[223002650490] |And about the correlations among the different operating points.
[223002650500] |It doesn’t seem that a naive independent binomial for each recall point would be justified, though it’d make the posteriors very clean, especially with uniform priors.
[223002650510] |For instance, suppose that after the first 5 true positives in the systems’ ranked lists, we have seen 7, 10, 4, 11, and 21 false positives for the five systems?
[223002650520] |The maximum likelihood point estimate of precision with a uniform prior is then 5/12, 5/15, 5/9, 5/16, and 5/26.
[223002650530] |Can we just use Beta(6,13), …, Beta(6,27) as the posteriors for comparison?
[223002650540] |Somehow it just seems wrong.
[223002650550] |<h3>Any Ideas?</h3>
[223002650560] |Does anyone know how to compute PR or ROC posteriors appropriately?
[223002650570] |<h3>Does Anyone Have Data?</h3>
[223002650580] |Andrew, or anyone: if you have the ranked data and gold standard answers, I’d love to code this up in R/BUGS and see what it looks like in the context of data someone cares about.