I (Bob) am going to give a talk at the next NYC Machine Learning Meetup, on 19 January 2012 at 7 PM:
There’s an abstract on the meetup site. The short story is that Stan’s a directed graphical model compiler (like BUGS) that uses adaptive Hamiltonian Monte Carlo sampling to estimate posterior distributions for Bayesian models.
The official version 1 release is coming up soon, but until then, you can check out our work in progress at:
Last week I shut my LinkedIn account down.
My first attempt resulted in a warning web page saying I couldn’t shut it down because I had over 250 contacts. With that hint, I just deleted contacts until I had fewer than 250. Then I could close my account through their web form.
The first close attempt resulted in an e-mail from LinkedIn to their “customer support” group, cc-ed to me, asking them to close my account because I was unable to, citing the reason:
The member has a large network of connections to close. Please close during non-peak hours.
LinkedIn seems to be suggesting their site is so fragile it can’t be trusted to delete during peak hours.
A week later (as in today), I got the predicted response from “customer support”, namely a plea to stay. Today’s e-mail started with:
I’m sorry it’s taken so long to get back to you.
The apology seems rather disengenuous given the rest of the e-mail, which continued with:
I noticed that you have put a lot of effort into growing your LinkedIn network. Because of this, I wanted to confirm that you want to close an account with such a large number of connections.
Only after this did the e-mail start outlining further steps I’d have to take to close the account I’d already closed last week.
Why did I close my LinkedIn account? On the “con” side, it was a hassle to go through invitations to connect from people I didn’t know or had met once. I felt bad if I said “no” or “yes”. On the “pro” side, I couldn’t come up with anything. It’s not like I’m going to use LinkedIn to find a job.
Roberto Pieraccini, who was my boss at SpeechWorks (among other notable accomplishments), is going to be the new director of U. C. Berkeley’s International Computer Science Institute (ICSI).
Now this is a succession event I can (and did) wholeheartedly endorse. They asked me to write a recommendation letter as a former employee (his new colleagues all report to him; he’ll report to the trustees). I can paraphrase what I said: I’d be more than happy to work for Roberto again.
We will train and test on anything that’s easy to parse. Up today is a basic English part-of-speech tagging for Twitter developed by Kevin Gimpel et al. (and when I say “et al.”, there are ten co-authors!) in Noah Smith’s group at Carnegie Mellon.
The relevant resources are:
Their paper describes their tagging scheme as well as their CRF-based tagger. It uses Stanford’s CRF tagger with baseline features as a performance comparison. The code for their tagger’s also in the distribution. I’m not sure what the license is — it’s listed as “other open source” (I didn’t even know Google Code let you do that — I thought it was “free beer” or nothing with them).
Their corpus was very easy to parse (thanks, I really appreciate it). It only took me about an hour or so to download the data, parse it, and evaluate LingPipe’s baseline POS tagger on it. (It helps to be the author of code. The patterns feel awfully comfortable.)
Our performance was 85.4% accuracy on their train/test split using the default parameters for tagging in LingPipe. In contrast, the Stanford CRF tagger with default features was 85.9% accurate, whereas Gimpel et al.’s tagger achieved 89.4% accuracy. As usual, LingPipe’s HMM tagger is competitive with out-of-the-box CRFs and a few percentage points behind tuned, feature-rich CRFs.
Their paper (on page 5) says the annotator agreement is 92.2%. They also break accuracy out per tag, which LingPipe’s output also does; you can see this yourself if you run it.
The baseline POS tagger in LingPipe is a bigram HMM with emissions defined by a bounded character language model. Estimation is with simple additive smoothing (i.e., MAP estimates given symmetric Dirichlet priors) for the initial state and transition probabilities and Witten-Bell smoothing for the character LMs. Our main motivation for doing things this way is that (a) it’s online, letting us train an example at a time, and (b) it’s reasonably fast when it runs. We should be able to decode this tag set at well over 500K tokens/second by turning on caching of character LM results and pruning.
We could also implement their approach using LingPipe’s CRFs. It’s just that it’d take a bit longer than an hour all in.
You can get their code from their project home page, linked above.
All of my code’s checked into the LingPipe Sandbox in a project named “twitter-pos”. You can check it out anonymously using Subversion:
svn co https://aliasi.devguard.com/svn/sandbox/twitter-pos
The code’s in a single file, stored under the src subdirectory of the package:
package com.lingpipe.twpos;
import com.aliasi.classify.*;
import com.aliasi.corpus.*;
import com.aliasi.io.*;
import com.aliasi.hmm.*;
import com.aliasi.tag.*;
import java.io.*;
import java.util.*;
public class Eval {
public static void main(String[] args) throws IOException {
System.out.println("Reading Corpus");
TwitterPosCorpus corpus
= new TwitterPosCorpus(new File(args[0]));
System.out.println("Training Tagger");
HmmCharLmEstimator hmm = new HmmCharLmEstimator();
corpus.visitTrain(hmm);
HmmDecoder tagger = new HmmDecoder(hmm);
System.out.println("Evaluating");
boolean storeTokens = true;
TaggerEvaluator evaluator
= new TaggerEvaluator(tagger,storeTokens);
corpus.visitTest(evaluator);
System.out.println(evaluator.tokenEval());
}
static List<Tagging> parse(File f) throws IOException {
List<Tagging> taggings
= new ArrayList<Tagging>();
FileLineReader reader = new FileLineReader(f,"UTF-8");
List tokens = new ArrayList();
List tags = new ArrayList();
for (String line : reader) {
String[] tokTag = line.split("\\s+");
if (tokTag.length != 2) {
taggings.add(new Tagging(tokens,tags));
// System.out.println("tokens=" + tokens);
// System.out.println("tags=" + tags);
tokens = new ArrayList();
tags = new ArrayList();
} else {
tokens.add(tokTag[0]);
tags.add(tokTag[1]);
}
}
return taggings;
}
static class TwitterPosCorpus extends ListCorpus<Tagging> {
public TwitterPosCorpus(File path) throws IOException {
for (Tagging t : parse(new File(path,"train")))
addTrain(t);
for (Tagging t : parse(new File(path,"dev")))
addTrain(t);
for (Tagging t : parse(new File(path,"test")))
addTest(t);
}
}
}
LingPipe’s pretty fast for this sort of thing, with the entire program above, including I/O, corpus parsing, training, and testing taking a total of 5 seconds on my now ancient workstation.
Although it wouldn’t be a fair comparison, there’s usually a percent or so to be eked out of a little tuning in this setting (it would’ve been fair had I done tuning on the dev set and evaluated exactly once). This was just a straight out of the box, default settings eval. In general, one shouldn’t trust results that report post-hoc best settings values as they’re almost always going to overestimate real performance for all the usual reasons.
Finally, here’s the confusion matrix for tags in the first-best output:
,D,E,#,!,G,&,@,A,$,L,N,O,,,U,T,V,P,S,R,~,^,X,Z D,446,0,0,1,0,0,0,4,0,0,0,7,0,0,0,0,11,0,7,0,8,1,0 E,0,53,0,1,2,0,0,0,1,0,0,0,5,0,1,0,0,0,0,0,0,0,0 #,0,0,44,0,1,0,0,0,0,0,10,0,0,0,0,3,0,0,0,0,20,0,0 !,0,0,1,140,1,0,0,5,0,1,15,5,0,0,0,3,1,0,7,0,7,0,0 G,1,1,5,2,14,0,0,1,3,0,10,0,10,0,0,4,1,0,1,2,15,0,0 &,0,0,0,0,0,122,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0 @,0,0,0,0,0,0,328,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0 A,0,0,0,1,0,1,0,248,3,0,44,0,0,0,2,30,2,0,24,0,12,0,0 $,0,0,0,0,0,0,1,0,79,0,2,0,0,0,0,0,3,0,0,0,0,0,0 L,2,0,0,0,1,0,0,0,0,120,3,1,0,0,0,2,0,0,0,0,0,0,0 N,1,0,1,5,1,0,0,49,1,1,783,2,0,0,2,52,6,0,14,0,63,0,0 O,4,0,0,0,1,0,0,2,0,0,2,456,0,0,1,0,0,0,2,0,4,0,0 ,,0,4,0,0,2,0,0,0,0,0,0,0,861,0,0,2,0,0,0,11,0,0,0 U,0,0,0,1,0,0,0,0,0,0,0,0,1,114,0,0,0,0,0,0,1,0,0 T,0,0,0,0,0,0,0,0,0,0,0,1,0,0,24,0,9,0,1,0,1,0,0 V,0,1,0,0,0,0,0,21,0,1,69,1,0,0,0,921,9,0,7,2,21,0,0 P,2,0,0,1,0,0,0,4,1,0,1,0,0,0,11,6,571,0,12,0,4,0,0 S,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,2,0,0,1,0,0 R,4,0,0,1,0,0,0,13,0,0,20,1,0,0,1,6,15,0,269,0,8,1,0 ~,0,0,0,1,1,0,0,0,0,0,0,0,32,0,0,1,0,0,0,177,0,0,0 ^,1,0,4,1,2,0,0,29,2,0,101,0,2,0,0,16,4,0,1,0,331,0,1 X,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,0,3,0 Z,1,0,0,0,0,0,0,0,0,1,4,0,0,0,0,0,0,1,0,0,13,0,2
I should really figure out how to format that a bit more neatly.
[This post repeats a long comment I posted about licensing in response to Brendan O'Connor's blog entry, End-to-End NLP Packages. Brendan's post goes over some packages for NLP and singles out LingPipe as being only “quasi free.”]
Some of those other packages, like C&C Tools and Senna, are in the same “quasi free” category as LingPipe in the sense that they’re released under what their authors call “non-commercial” licenses. For instance, none of the Senna, C&C, or LingPipe licenses are compatible with GPL-ed code. Senna goes so far as to prohibit derived works altogether.
The intent for the
was a little different from the “academic use only” licenses in that we didn’t single out academia as a special class of users. We do allow free use for research purposes for industrialists and academics alike. We also provide a “developers” license that explicitly gives you this right, which makes some users’ organizations feel better.
The other tools, like NLTK, Mallet, OpenNLP, and GATE are released under more flexible licenses (LGPL, Apache or BSD), which I really do think of as being truly “free”. Mahout’s also in this category, though not mentioned by Brendan, whereas packages like TreeTagger are more like Senna or C&C in their restrictive “academic only” licensing.
Stanford NLP’s license sounds like it was written by someone who didn’t quite understand the GPL. Their page says (the link is also theirs):
The Stanford CoreNLP code is licensed under the full GPL, which allows its use for research purposes, free software projects, software services, etc., but not in distributed proprietary software.
Technically, what they say is true. It would’ve been clearer if they’d replaced “research” with “research and non-research” and “free” with “free and for-profit”. Instead, their choice of examples suggests “free” or “research” have some special status under the GPL, which they don’t. With my linguist hat on, I’d say their text leads the reader to a false implicature. The terms “research” and “academia” don’t even show up in the GPL, and although “free” does, GNU and others clarify this usage elswewhere as “free as in free speech”, not “free as in free beer”.
The key to understanding the GPL lies behind Stanford’s embedded link to
Here, proprietary doesn’t have to do with ownership, but rather with closed source. Basically, if you redistribute source code or an application based on GPL-ed code, you have to also release your code under the GPL, which is why it’s called a “copyleft” or “viral” license. In some cases, you can get away with using a less restrictive license like LGPL or BSD for your mods or interacting libraries, though you can’t change the underlying GPL-ed source’s license.
There’s no free ride for academics here — you can’t take GPL-ed code, use it to build a research project for your thesis, then give an executable away for free without also distributing your code with a compatible license. And you can’t restrict the license to something research only. Similarly, you couldn’t roll a GPL-ed library into Senna or C&C or LingPipe and redistribute them under their own licenses. Academics are often violating these terms because they somehow think “research use only” is special.
You can also set up a software service, for example on Amazon’s Elastic Compute Cloud (EC2) or on your own servers, that’s entirely driven by GPL-ed software, like say Stanford NLP or Weka, and then charge users for accessing it. Because you’re not redistributing the software itself, you can modify it any way you like and write code around it without releasing your own software. GNU introduced the Affero GPL (AGPL), a license even more restrictive than the GPL that tries to close this server loophole for the basic GPL.
You can charge for GPL-ed code if you can find someone to pay you. That’s what RedHat’s doing with Linux, what Revolution R’s doing with R, and what Enthought’s doing with Python.
Note that this is not what MySQL did with MySQL (before they sold it to Oracle) nor is it what we do with LingPipe. In both those cases, the company owns all the intellectual property and copyrights and thus is able to release the code under multiple licenses. This strategy’s explained on the
We license LingPipe under custom licenses as well as our royalty-free license. These licenses include all sorts of additional restrictions (like only using some of the modules on so many servers) and additional guarantees (like indemnification and maintenance); don’t ask me about the details — that’s Breck’s bailiwick. Suffice it to say most companies don’t like to get involved with copyleft, be it from GPL or LingPipe’s royalty-free license. So we let them pay us extra and get an unencumbered license so they can do what they want with LingPipe and not have to share their code. We’ve had more than one customer buy commercial license for LingPipe who wouldn’t even tell us what they were going to do with our software.
Also, keep in mind that as an academic, your university (or lab) probably has a claim to your intellectual property developed using their resources. Here’s some advice from GNU on that front:
The news that Oracle’s buying Endeca sounds awfully familiar. But this time it cuts a little closer to home, because we’re an Endeca technology partner. Endeca has been a great customer to work with — we’ve been really impressed with their engineers at every turn.
I believe this makes it almost a clean sweep of the medium-to-medium-large-sized independent search companies. Maybe Vivisimo will be next. Of course, there are still small companies delivering search via Apache Lucene and SOLR, such as Sematext and Lucid Imagination. I imagine they will be delighted that yet another small competitor was snapped up by a tech giant.
By combining the innovation and agility of FAST with the discipline and resources of Microsoft, our customers get the best of both worlds: market-leading products from a trusted technology partner. … Enterprise Search from Microsoft offers best-in-class technologies…
from: Microsoft fact sheet
Autonomy brings to HP higher value business solutions that will help customers manage the explosion of information. Together with Autonomy, we plan to reinvent how both unstructured and structured data is processed, analyzed, optimized, automated and protected. … this bold action will squarely position HP in software and information to create the next-generation Information Platform, and thereby, create significant value for our shareholders.
from: HP press release
Combination [of Oracle and Endeca] provides best-in-class technology and applications for unstructured data management, business intelligence, and web commerce. … The convergence of structured and unstructured information is driving the need for a common data management and analytics platform.
from: Oracle Press Release
Maybe the tough economic climate has made it hard for small-to-medium-sized tech companies to survive without the deep pockets of a successful large tech company. Maybe Oracle made them an offer that was too good to refuse. Far better to sell when you can get a good price than to suffer the fate of Yahoo! (or SpeechWorks, for that matter).
On that note, feel free to make us an offer for LingPipe.
The issue came up in the last blog post, Discontinuities in ROC calculations, about smoothing out Area-under-the-curve (AUC) calculations for ROC and PR curves given observed data points that are very close together.
If you have a bunch of point measurements that you assume were taken with some error, what you can do is model the error itself. Suppose we don’t want to think too hard and just make the error normal, so that a measurement of 
Then, rather than computing a function 
To get back to something on the same scale, it’s typical to use a Bayesian point estimate that minimizes expected square error, namely the expectation. Now, instead of a point
![\mathbb{E}[f(X)] = \int_X f(x) \ \mbox{\sf Norm}(x|a,\sigma^2) \ dx](http://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5Bf%28X%29%5D+%3D+%5Cint_X+f%28x%29+%5C+%5Cmbox%7B%5Csf+Norm%7D%28x%7Ca%2C%5Csigma%5E2%29+%5C+dx&bg=ffffff&fg=333333&s=0 "\mathbb{E}[f(X)] = \int_X f(x) \ \mbox{\sf Norm}(x|a,\sigma^2) \ dx")
We can also compute even probabilities, such as comparing two systems with noisy measurements 
![{} = \int \int \mathbb{I}[f(X) < f(Y)] \ \mbox{\sf Norm}(x|a,\sigma^2) \ \mbox{\sf Norm}(y|b,\sigma^2) \ dx \ dy](http://s0.wp.com/latex.php?latex=%7B%7D+%3D+%5Cint+%5Cint+%5Cmathbb%7BI%7D%5Bf%28X%29+%3C+f%28Y%29%5D+%5C+%5Cmbox%7B%5Csf+Norm%7D%28x%7Ca%2C%5Csigma%5E2%29+%5C+%5Cmbox%7B%5Csf+Norm%7D%28y%7Cb%2C%5Csigma%5E2%29+%5C+dx+%5C+dy&bg=ffffff&fg=333333&s=0 "{} = \int \int \mathbb{I}[f(X) < f(Y)] \ \mbox{\sf Norm}(x|a,\sigma^2) \ \mbox{\sf Norm}(y|b,\sigma^2) \ dx \ dy")
Of course, this leaves the problem of how to estimate 
![\mathbb{E}[f(X)] = \int_0^{\infty} \int_X f(x) \ \mbox{\sf Norm}(x|a,\sigma^2) \ p(\sigma|...) \ dx \ d\sigma](http://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5Bf%28X%29%5D+%3D+%5Cint_0%5E%7B%5Cinfty%7D+%5Cint_X+f%28x%29+%5C+%5Cmbox%7B%5Csf+Norm%7D%28x%7Ca%2C%5Csigma%5E2%29+%5C+p%28%5Csigma%7C...%29+%5C+dx+%5C+d%5Csigma&bg=ffffff&fg=333333&s=0 "\mathbb{E}[f(X)] = \int_0^{\infty} \int_X f(x) \ \mbox{\sf Norm}(x|a,\sigma^2) \ p(\sigma|...) \ dx \ d\sigma")
As Mike Ross pointed out, the result is going to be sensitive to
![\lim_{\sigma \rightarrow 0} \mathbb{E}[f(X)] = f(a)](http://s0.wp.com/latex.php?latex=%5Clim_%7B%5Csigma+%5Crightarrow+0%7D+%5Cmathbb%7BE%7D%5Bf%28X%29%5D+%3D+f%28a%29&bg=ffffff&fg=333333&s=0 "\lim_{\sigma \rightarrow 0} \mathbb{E}[f(X)] = f(a)")
Similarly, as 
The bottom line is that you'd like a sensible model of measurement error.
Real AUC calculations depend on more than one point. If you have a vector points ![\hat{x} \in [0,1]^N](http://s0.wp.com/latex.php?latex=%5Chat%7Bx%7D+%5Cin+%5B0%2C1%5D%5EN&bg=ffffff&fg=333333&s=0 "\hat{x} \in [0,1]^N")
With a normal noise model (or really any model you can sample from), it's easy to compute this integral using Monte Carlo methods. Just take a sequence of 
As the number of samples
![\lim_{M \rightarrow \infty} \frac{1}{M} \ \sum_{m=1}^M \mbox{AUC}(y^{(m)},x) = \mathbb{E}[\mbox{AUC}(\hat{x},x)]](http://s0.wp.com/latex.php?latex=%5Clim_%7BM+%5Crightarrow+%5Cinfty%7D+%5Cfrac%7B1%7D%7BM%7D+%5C+%5Csum_%7Bm%3D1%7D%5EM+%5Cmbox%7BAUC%7D%28y%5E%7B%28m%29%7D%2Cx%29+%3D+%5Cmathbb%7BE%7D%5B%5Cmbox%7BAUC%7D%28%5Chat%7Bx%7D%2Cx%29%5D&bg=ffffff&fg=333333&s=0 "\lim_{M \rightarrow \infty} \frac{1}{M} \ \sum_{m=1}^M \mbox{AUC}(y^{(m)},x) = \mathbb{E}[\mbox{AUC}(\hat{x},x)]")
Amaç Herdagdelen brought up some interesting examples on our mailing list that caused LingPipe’s ROC curve (and PR curve) implementation to provide some unexpected (and arguably wrong) results. (We then took the detailed discussion off line, and are now reporting back.)
The basic problem is that the computation of an ROC curve involves first sorting the responses by the system’s estimated probability a response should be positive, then incrementally computing sensitivity versus 1 – specificty operating points by working down the ranked list. You can see a worked example in the class documentation for
Mike Ross realized there was a problem when you had two examples with the same score, but different reference values. For instance, a system might be looking at two Tweets and estimate a 0.98 probability that both are positive sentiment. If one was classified as positive in the reference (i.e., the gold standard) and the other negative, then there’s a problem. With one order, you get one curve, and with the other order, you get a different curve. Mike figured out we might as well just leave off the intermediate point, because we get to the same operating point after handling both of them.
Then Amaç wrote back after noticing he had some cases that were very close, but not quite, the same. This comes up with arithmetic precision all the time. In his case, it was different one-versus-all results for a multi-category classifier. He suggested treating two results as the same if they were within some small absolute value of each other. This is the typical thing to do when checking results are the same in unit tests (or code) — it’s built into junit for Java and googletest for C++.
That led me (Bob) to realize that the real problem is that these measures are discontinuous in the underlying scores. Suppose I have three items, A, B and C, with true values POS, NEG, and POS. Now if I have assigned scores to them of 0.97, 0.96, and 0.98, I get a curve based on the sequence TP, TP, FP, or a perfect score. I get the same reslt as the score for B moves from 0.96 to any value less than 0.97. But at the point it crosses 0.97, I wind up with a sequence TP, FP, TP, which is a whole different story.
The upshot is that area under the ROC curve (or PR curve) is not continuous in the underlying scores.
Does anyone have any idea what we should do here?
I’m thinking moving to some kind of probabilistic version might be able to smooth things out in a well-defined way. For instance, if I add normally-distributed noise around each point and then integrate it out, things are smooth again.
Last post, I explained how to build hierarchical naive Bayes models for domain adaptation. That post covered the basic problem setup and motivation for hierarchical models.
Today, we’ll look at the so-called (in NLP) “discriminative” version of the domain adaptation problem. Specifically, using logistic regression. For simplicity, we’ll stick to the binary case, though this could all be generalized to K-way classifiers.
Logistic regression is more flexible than naive Bayes in allowing other features (aka predictors) to be brought in along with the words themselves. We’ll start with just the words, so the basic setup look more like naive Bayes.
We’ll use the same data representation as in the last post, with 
![N[d,i]](http://s0.wp.com/latex.php?latex=N%5Bd%2Ci%5D&bg=ffffff&fg=333333&s=0 "N[d,i]")
Raw document data provides a token ![x[d,i,n] \in 1{:}V](http://s0.wp.com/latex.php?latex=x%5Bd%2Ci%2Cn%5D+%5Cin+1%7B%3A%7DV&bg=ffffff&fg=333333&s=0 "x[d,i,n] \in 1{:}V")
![u[d,i]](http://s0.wp.com/latex.php?latex=u%5Bd%2Ci%5D&bg=ffffff&fg=333333&s=0 "u[d,i]")
![u[d,i,w] = \sum_{n = 1}^{N[d,i]} \mathbb{I}(x[d,i,n] = w)](http://s0.wp.com/latex.php?latex=u%5Bd%2Ci%2Cw%5D+%3D+%5Csum_%7Bn+%3D+1%7D%5E%7BN%5Bd%2Ci%5D%7D+%5Cmathbb%7BI%7D%28x%5Bd%2Ci%2Cn%5D+%3D+w%29&bg=ffffff&fg=333333&s=0 "u[d,i,w] = \sum_{n = 1}^{N[d,i]} \mathbb{I}(x[d,i,n] = w)")
where 
The labeled training data consists of a classification ![z[d,i] \in \{ 0, 1 \}](http://s0.wp.com/latex.php?latex=z%5Bd%2Ci%5D+%5Cin+%5C%7B+0%2C+1+%5C%7D&bg=ffffff&fg=333333&s=0 "z[d,i] \in \{ 0, 1 \}")
The main parameter to estimate is a coefficient vector ![\beta[d]](http://s0.wp.com/latex.php?latex=%5Cbeta%5Bd%5D&bg=ffffff&fg=333333&s=0 "\beta[d]")
The probabilty that a given document is of category 1 (rather than category 0) is given by
![\mbox{Pr}[z[d,i] = 1] = \mbox{logit}^{-1}(\beta[d]^T u[d,i])](http://s0.wp.com/latex.php?latex=%5Cmbox%7BPr%7D%5Bz%5Bd%2Ci%5D+%3D+1%5D+%3D+%5Cmbox%7Blogit%7D%5E%7B-1%7D%28%5Cbeta%5Bd%5D%5ET+u%5Bd%2Ci%5D%29&bg=ffffff&fg=333333&s=0 "\mbox{Pr}[z[d,i] = 1] = \mbox{logit}^{-1}(\beta[d]^T u[d,i])")
The inner (dot) product is just the sum of the dimensionwise products,
![\beta[d]^T u[d,i] = \sum_{v = 0}^V \beta[d,v] \times u[d,i,v]](http://s0.wp.com/latex.php?latex=%5Cbeta%5Bd%5D%5ET+u%5Bd%2Ci%5D+%3D+%5Csum_%7Bv+%3D+0%7D%5EV+%5Cbeta%5Bd%2Cv%5D+%5Ctimes+u%5Bd%2Ci%2Cv%5D&bg=ffffff&fg=333333&s=0 "\beta[d]^T u[d,i] = \sum_{v = 0}^V \beta[d,v] \times u[d,i,v]")
This value, called the linear prediction, can take values in 
maps the unbounded linear prediction to the range 
![z[d,i]](http://s0.wp.com/latex.php?latex=z%5Bd%2Ci%5D&bg=ffffff&fg=333333&s=0 "z[d,i]")
In sampling notation, we define the category as being drawn from a Bernoulli distribution with parameter given by the transformed predictor; in symbols,
![z[d,i] \sim \mbox{\sf Bern}(\mbox{logit}^{-1}(\beta[d]^T u[d,i])](http://s0.wp.com/latex.php?latex=z%5Bd%2Ci%5D+%5Csim+%5Cmbox%7B%5Csf+Bern%7D%28%5Cmbox%7Blogit%7D%5E%7B-1%7D%28%5Cbeta%5Bd%5D%5ET+u%5Bd%2Ci%5D%29&bg=ffffff&fg=333333&s=0 "z[d,i] \sim \mbox{\sf Bern}(\mbox{logit}^{-1}(\beta[d]^T u[d,i])")
Unlike naive Bayes, logistic regression model does not model the word data 
We are treating the coefficient vectors as estimated parameters, so we need a prior for them. We can choose just about any kind of prior we want here. We’ll only consider normal (Gaussian, L2) priors here, but the Laplace (L1) prior is also very popular. Recently, statisticians have argued for using a Cauchy distribution as a prior (very fat tails; see Gelman et al.’s paper) or combining L1 and L2 into a so-called elastic net prior. LingPipe implements all of these priors; see the documentation for regression priors.
Specifically, we are going to pool the prior across domains by sharing the priors for words 
![\beta[d,v] \sim \mbox{\sf Normal}(\mu[v],\sigma[v]^2)](http://s0.wp.com/latex.php?latex=%5Cbeta%5Bd%2Cv%5D+%5Csim+%5Cmbox%7B%5Csf+Normal%7D%28%5Cmu%5Bv%5D%2C%5Csigma%5Bv%5D%5E2%29&bg=ffffff&fg=333333&s=0 "\beta[d,v] \sim \mbox{\sf Normal}(\mu[v],\sigma[v]^2)")
Here ![\mu[v]](http://s0.wp.com/latex.php?latex=%5Cmu%5Bv%5D&bg=ffffff&fg=333333&s=0 "\mu[v]")
![\sigma[v]^2](http://s0.wp.com/latex.php?latex=%5Csigma%5Bv%5D%5E2&bg=ffffff&fg=333333&s=0 "\sigma[v]^2")
All that’s left is to provide a prior for these location and scale parameters. It’s typical to use a simple centered normal distribution for the locations, specifically
![\mu[v] \sim \mbox{\sf Normal}(0,\tau^2)](http://s0.wp.com/latex.php?latex=%5Cmu%5Bv%5D+%5Csim+%5Cmbox%7B%5Csf+Normal%7D%280%2C%5Ctau%5E2%29&bg=ffffff&fg=333333&s=0 "\mu[v] \sim \mbox{\sf Normal}(0,\tau^2)")
where 
Next, we need priors for the ![\sigma[v]](http://s0.wp.com/latex.php?latex=%5Csigma%5Bv%5D&bg=ffffff&fg=333333&s=0 "\sigma[v]")
![\sigma[v]^2 \sim \mbox{\sf InvGamma}(\alpha,\beta)](http://s0.wp.com/latex.php?latex=%5Csigma%5Bv%5D%5E2+%5Csim+%5Cmbox%7B%5Csf+InvGamma%7D%28%5Calpha%2C%5Cbeta%29&bg=ffffff&fg=333333&s=0 "\sigma[v]^2 \sim \mbox{\sf InvGamma}(\alpha,\beta)")
Gelman argues against inverse gamma priors on variance because they have pathological behavior when the hierarchical variance terms are near zero.
Gelman prefers the half-Cauchy prior, because it tends not to degenerate in hierarchical models like the inverse gamma can. The half Cauchy is just the Cauchy distribution restricted to positive values (thus doubling the usual density, but restricting support to non-negative values). In symbols, we generate the deviation
![\sigma[v] \sim \mbox{HalfCauchy}()](http://s0.wp.com/latex.php?latex=%5Csigma%5Bv%5D+%5Csim+%5Cmbox%7BHalfCauchy%7D%28%29&bg=ffffff&fg=333333&s=0 "\sigma[v] \sim \mbox{HalfCauchy}()")
And that’s about it. Of course, you’ll need some fancy-pants software to fit the whole thing, but it’s not that difficult to write.
Like in the naive Bayes case, going hierarchical means we get data pooling (or “adaptation” or “transfer”) across domains.
One very nice feature of the regression model follows from the fact that we are treating the word vectors as unmodeled predictors and thus don’t have to model their probabilities across domains. Instead, the coefficient vector ![\beta[d,v]](http://s0.wp.com/latex.php?latex=%5Cbeta%5Bd%2Cv%5D&bg=ffffff&fg=333333&s=0 "\beta[d,v]")
The intercept is just acting as a bias term toward one category or the other (depending on the value of its coefficient).
If one were to approximate the full Bayes solution with maximum a posteriori point estimates and use Laplace (L1) priors on the coefficients,
then we recreate the regression counterpart of Eisenstein et al.’s hybrid regression and naive-Bayes style sparse additive generative model of text (aka SAGE).
Eisenstein et al.’s motivation was to represent each domain as a difference from the average of all domains. If you recast the coefficient prior formula slightly and set
and sample
you’ll see that if the variance term ![\sigma[d]](http://s0.wp.com/latex.php?latex=%5Csigma%5Bd%5D&bg=ffffff&fg=333333&s=0 "\sigma[d]")
![\alpha[d,v]](http://s0.wp.com/latex.php?latex=%5Calpha%5Bd%2Cv%5D&bg=ffffff&fg=333333&s=0 "\alpha[d,v]")
Presumably, the values of coefficients have will have non-negligible covariance. That is, I expect words like “thrilling” and “scary” to covary. For thriller movies, they’re positive sentiment terms and for appliances, rather negative. The problem with modeling covariance among lexical items is that we usually have tens of thousands of them. Not much software can handle a 10K by 10K matrix.
Another way to add covariance instead of using a covariance model for “fixed effects” is instead convert to random effects. For instance, a model like latent Dirichlet allocation (LDA) models covariance of words by grouping them into topics. For instance, two words with high probabilities in the same topic will have positive covariance.
I’m a big fan of Gelman and Hill’s multilevel regression book. You definitely want to master that material before moving on to Gelman et al.’s Bayesian Data Analysis. Together, they’ll give you a much deeper understanding of the issues in hierarchical (or more generally, multilevel) modeling.
This will be the first of two posts exploring hierarchical and multilevel classifiers. In this post, I’ll describe a hierarchical generalization of naive Bayes (what the NLP world calls a “generative” model). The next post will explore hierarchical logistic regression (called a “discriminative” or “log linear” or “max ent” model in NLP land).
Within natural language processing, the term “domain adaptation” has come to mean something like “using data in one domain to improve results in another domain”. Examples that have received attention include positive/negative sentiment for reviews of different kinds of products, with, say, DVDs being one domain and kitchen appliances another (Blitzer et al. 2007). Other examples classifying sequences of tokens as names across different genres of text, such as newswire and transcribed speech (Daumé III 2007, Finkel and Manning 2009).
The work I’ve seen on adaptation has largely been in the supervised case, but what we’re going to do here can be unsupervised, in which case you get something like soft K-means clustering. It can also be semi-supervised, with some documents having category labels and some not having labels. I’ve talked about semi-supervised models before, too, as recently as the very last blog post, covering Tang and Lease’s semi-supervised annotation model and in our replication of Nigam et al.’s semi-supervised naive Bayes EM estimator in the LingPipe tutorial on semi-supervised naive Bayes classification.
The standard Bayesian approach to domain adaptation is to build a hierarchical model. The hierarchy in this case is the hieararchy of domains. We’ll just consider the flat case, where there’s a collection
I’ve blogged before about properly Bayesian approaches to naive Bayes classifiers, specifically about Bayesian naive Bayes inference and collapsed Gibbs sampling for computing it.
What we’re going to do is let information in one domain, such as which words are positive or which phrases are people names, inform estimates for other domains. This is sometimes referred to as “pooling” information across sub-populations in statistics. A simple example from political science that illustrates the general flavor of models we’re working on at Columbia is allowing estimates of the effect of income on voting in one state to inform estimates in other states, while still allowing the states to differ (an example is given in Gelman et al.’s What’s wrong with Connecticut?).
Theoretically, what we’re going to do amounts to assuming that the domains themselves are exchangeable. We use exchangeable models when we don’t have any information to distinguish the domains. We’ll discuss the case where we do have such information in the next post.
In Bayesian models, we treat exchangeable variables as being drawn from a population distribution (aka, a prior). In hierarchical models, we model the population directly. The reason it’s called hierarchical is that in a proper Bayesian model, there must be a prior distribution on the domain model. So we get a prior on the parameters of the domain model, which then acts as a prior on the estimates for each domain. The pooling is achieved by information flow through the dependencies in the joint distribution implied by the graphical model. In practice, this is simpler than it sounds.
Once we’ve got our heads around the Bayesian formulation of naive Bayes, extending it to hieararchical models is straightforward. We’re going to use the language of documents and tokens in describing naive Bayes, but it’s really a general multinomial model, so don’t assume this is only valid for text classifiers.
For simplicity, we’ll assume we have a binary classifier. I’ll say more about the multi-category case later and in the next post.
Let 
The raw document data we have provides a token 
The labeled training data we have is a classification
The hierarchical naive Bayes model is a directed graphical model and as such, easy to describe with sampling notation.
We have a parameter ![\pi[d]](http://s0.wp.com/latex.php?latex=%5Cpi%5Bd%5D&bg=ffffff&fg=333333&s=0 "\pi[d]")
![\pi[d] \sim \mbox{\sf Beta}(\alpha_{\pi}, \beta_{\pi})](http://s0.wp.com/latex.php?latex=%5Cpi%5Bd%5D+%5Csim+%5Cmbox%7B%5Csf+Beta%7D%28%5Calpha_%7B%5Cpi%7D%2C+%5Cbeta_%7B%5Cpi%7D%29&bg=ffffff&fg=333333&s=0 "\pi[d] \sim \mbox{\sf Beta}(\alpha_{\pi}, \beta_{\pi})")
The categories assigned to each document are sampled from a Bernoulli distribution parameterized by prevalence in the document’s domain,
![z[d,i] \sim \mbox{\sf Bern}(\pi[d])](http://s0.wp.com/latex.php?latex=z%5Bd%2Ci%5D+%5Csim+%5Cmbox%7B%5Csf+Bern%7D%28%5Cpi%5Bd%5D%29&bg=ffffff&fg=333333&s=0 "z[d,i] \sim \mbox{\sf Bern}(\pi[d])")
Each domain 
![\phi[d,c] \in [0,1]^V](http://s0.wp.com/latex.php?latex=%5Cphi%5Bd%2Cc%5D+%5Cin+%5B0%2C1%5D%5EV&bg=ffffff&fg=333333&s=0 "\phi[d,c] \in [0,1]^V")
![\sum_{v = 1}^V \phi[d,c,v] = 1](http://s0.wp.com/latex.php?latex=%5Csum_%7Bv+%3D+1%7D%5EV+%5Cphi%5Bd%2Cc%2Cv%5D+%3D+1&bg=ffffff&fg=333333&s=0 "\sum_{v = 1}^V \phi[d,c,v] = 1")
describing the distribution of vocabulary items 
These category word distributions for each domain are drawn from a Dirichlet prior ![\gamma[c]](http://s0.wp.com/latex.php?latex=%5Cgamma%5Bc%5D&bg=ffffff&fg=333333&s=0 "\gamma[c]")
![\phi[d,c] \sim \mbox{\sf Dir}(\gamma[c])](http://s0.wp.com/latex.php?latex=%5Cphi%5Bd%2Cc%5D+%5Csim+%5Cmbox%7B%5Csf+Dir%7D%28%5Cgamma%5Bc%5D%29&bg=ffffff&fg=333333&s=0 "\phi[d,c] \sim \mbox{\sf Dir}(\gamma[c])")
We then model the tokens in the standard way for naive Bayes, as being drawn independently (that’s the “naive” part) from the discrete distribution associated with their domain
![x[d,i,n] \sim \mbox{\sf Disc}(\phi[d, z[d,i]])](http://s0.wp.com/latex.php?latex=x%5Bd%2Ci%2Cn%5D+%5Csim+%5Cmbox%7B%5Csf+Disc%7D%28%5Cphi%5Bd%2C+z%5Bd%2Ci%5D%5D%29&bg=ffffff&fg=333333&s=0 "x[d,i,n] \sim \mbox{\sf Disc}(\phi[d, z[d,i]])")
So far, that’s only the lower level of the model. As I mentioned earlier, the priors characterize the populations of prevalences and vocabulary distributions for categories across domains. And we’re using hierarchical models on both sides of naive Bayes, for the categories themselves and for the topic distributions. There are many choices for how to model these populations. We’ll go with a very simple model that only characterizes prior means and variance, not prior covariance; as an example of a prior modeling covariance for multinomials, see the prior for topics in Lafferty and Blei’s correlated topic model.
It’s easier to start with the prevalences. The prior model here will model the mean prevalence of outcome 1 (say, the “positive” outcome for sentiment) across domains, as well as its variance. The mean of the density 
For convenience, we’ll reparameterize 
![\psi_{\pi} \in [0,1]](http://s0.wp.com/latex.php?latex=%5Cpsi_%7B%5Cpi%7D+%5Cin+%5B0%2C1%5D&bg=ffffff&fg=333333&s=0 "\psi_{\pi} \in [0,1]")
We’ll put a simple conjugate uniform prior on the prior mean 
(Note that 
![[0,1]](http://s0.wp.com/latex.php?latex=%5B0%2C1%5D&bg=ffffff&fg=333333&s=0 "[0,1]")
We’ll take a very weakly informative prior favoring high variance (low prior count) on the total prior counts,
where for 
The effect of this decision is that the estimate for prevalence 
We do the same thing for the Dirichlet prior, reparameterizating the prior count 
![\theta[b]](http://s0.wp.com/latex.php?latex=%5Ctheta%5Bb%5D&bg=ffffff&fg=333333&s=0 "\theta[b]")
![\rho[b]](http://s0.wp.com/latex.php?latex=%5Crho%5Bb%5D&bg=ffffff&fg=333333&s=0 "\rho[b]")
![\gamma[c] = \rho[b] \theta[b]](http://s0.wp.com/latex.php?latex=%5Cgamma%5Bc%5D+%3D+%5Crho%5Bb%5D+%5Ctheta%5Bb%5D&bg=ffffff&fg=333333&s=0 "\gamma[c] = \rho[b] \theta[b]")
We set a uniform prior on the prior vocabulary distribution
![\theta[b] \sim \mbox{Dir}(1)](http://s0.wp.com/latex.php?latex=%5Ctheta%5Bb%5D+%5Csim+%5Cmbox%7BDir%7D%281%29&bg=ffffff&fg=333333&s=0 "\theta[b] \sim \mbox{Dir}(1)")
and another weakly informative Pareto prior on the prior counts,
As the mathematicians are wont to say, Q.E.D..
What we do get is sharing of discriminative terms across domains. For instance, with polarity, positive term weights in each domain affect the prior, and the prior affects the average in each domain. The prior’s effect on estimates goes by the name “smoothing” in NLP. More specifically, the prior pulls the estimate for each domain and category toward the prior mean for that category by an amount inversely related to the prior variance (low prior variance exerting a stronger smoothing effect) and inversely related to the data count (with higher data counts, the prior’s effect is weaker).
We also get sharing of the non-discriminative terms among category 0 instances across domains and sharing among non-discriminative terms among category 1 instances.
… the fact that the model has to estimate the whole vocabulary of non-discriminative terms in both the negative and positive vocabulary priors ![\theta[0]](http://s0.wp.com/latex.php?latex=%5Ctheta%5B0%5D&bg=ffffff&fg=333333&s=0 "\theta[0]")
![\theta[1]](http://s0.wp.com/latex.php?latex=%5Ctheta%5B1%5D&bg=ffffff&fg=333333&s=0 "\theta[1]")
For instance, we’d expect “awesome” and “crap” to have a very different distribution in positive and negative sentiment product reviews, whereas “the” and “of” should be less discriminative.
The next level here would be to add a more informative prior for the prior per-category vocabulary distribution ![\theta[d]](http://s0.wp.com/latex.php?latex=%5Ctheta%5Bd%5D&bg=ffffff&fg=333333&s=0 "\theta[d]")
We could do the same thing for the prior mean for prevalence of categories if we have samples of other domains we could use.
One nice feature of hierarchical models is that it’s easy to extend the hierarchy (for an extreme example, see Li and McCallum’s paper on their aptly named technique, pachinko allocation).
It’s trivial to extend this hiearchical naive Bayes model to the multi-category setting. We kept things simple here because it’ll greatly simplify the next post on multilevel modeling with logistic regression. In the naive Bayes setting, just replace the Bernoulli distribution with a discrete distribution and the beta distribution with a Dirichlet.
It’s also trivial to extend the semi-supervised case. Any number of variables may be “missing” in a directed graphical model without hampering inference (theoretically it’s simple; computationally it requires more bookkeeping and perhaps more samplers). As we mentioned earlier, this is especially helpful in the setting where we’re estimating hyperpriors (here the top-level vocabulary prior over per-category vocabulary priors over per-category/per-domain vocabulary distributions).
This will work. The hieararchical modeling strategy pretty much always works. The reason is that with the right hyper-hyper priors, it’ll reduce to the original model. The real question is will it help?
We should see big gains in small count data.
I haven’t done any. If anyone else has evaluated hierarchical naive Bayes, please say so in the comments or e-mail me and I’ll write a link into the post itself.
A good data set would be Dredze et al.’s multi-domain sentiment data set. I’d at least like to see the results of this relatively simple and standard naive Bayes model and the one I’ll describe in the next post before delving into “deep” models a la (Glorot et al. 2011).
Wow, that was all only four lines of notes in my notebook. I wasn’t expecting this to run so long! The next post has six lines of notes, so watch out.
![\mbox{Pr}[f(X) < f(Y)]](http://s0.wp.com/latex.php?latex=%5Cmbox%7BPr%7D%5Bf%28X%29+%3C+f%28Y%29%5D&bg=ffffff&fg=333333&s=0 "\mbox{Pr}[f(X) < f(Y)]")
![\mathbb{E}[\mbox{AUC}(\hat{x},x)]](http://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5B%5Cmbox%7BAUC%7D%28%5Chat%7Bx%7D%2Cx%29%5D&bg=ffffff&fg=333333&s=0 "\mathbb{E}[\mbox{AUC}(\hat{x},x)]")
![\beta[d,v] \sim \mbox{\sf Laplace}(\mu[d],\sigma[d]^2)](http://s0.wp.com/latex.php?latex=%5Cbeta%5Bd%2Cv%5D+%5Csim+%5Cmbox%7B%5Csf+Laplace%7D%28%5Cmu%5Bd%5D%2C%5Csigma%5Bd%5D%5E2%29&bg=ffffff&fg=333333&s=0 "\beta[d,v] \sim \mbox{\sf Laplace}(\mu[d],\sigma[d]^2)")
![\beta[d,v] = \alpha[d,v] + \mu[d]](http://s0.wp.com/latex.php?latex=%5Cbeta%5Bd%2Cv%5D+%3D+%5Calpha%5Bd%2Cv%5D+%2B+%5Cmu%5Bd%5D&bg=ffffff&fg=333333&s=0 "\beta[d,v] = \alpha[d,v] + \mu[d]")
![\alpha[d,v] \sim \mbox{Laplace}(0,\sigma[d]^2)](http://s0.wp.com/latex.php?latex=%5Calpha%5Bd%2Cv%5D+%5Csim+%5Cmbox%7BLaplace%7D%280%2C%5Csigma%5Bd%5D%5E2%29&bg=ffffff&fg=333333&s=0 "\alpha[d,v] \sim \mbox{Laplace}(0,\sigma[d]^2)")
