Marginalizing Latent Variables in EM

Posted by jeffy Posted on 6:36 PM with 2 comments
 
 

Sent to you by Jeffye via Google Reader:

 
 

via LingPipe Blog by lingpipe on 1/19/10


After getting carried away in my last post on this topic, Maximum Likelihood Estimates of Expression in RNA-Seq are Winner-Take-All Biased, 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).

Expression Mixture Model

Recall that we were looking at a mixture model, which is the bread and butter of maximum likelihood estimators like EM. We defined a joint likelihood function for a sequence of observed reads r, gene or splice variant sources g, and mRNA expression \theta, setting

p(r,g|\theta) = \prod_{n=1}^N p(r_n,g_n|\theta) = \prod_{n=1}^N p(r_n|g_n) \ p(g_n|\theta).

Maximum Likelihood

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.

What's a Parameter?

So that's what I did, calculating

g^*, \theta^* = \arg \max_{g,\theta} p(r|g,\theta).

The problem is that there's an implicit "except the latent parameters" inside the usual understanding the MLE.

What I should have done is marginalized out the latent gene sources g, taking

\theta^* = \arg \max_{\theta} p(r|\theta).

That requires marginalizing out the latent mapping of reads r_n to gene or splice variant sources g_n,

p(r|\theta) = \prod_{n=1}^N p(r_n|\theta_n) = \prod_{n=1}^N \sum_{k = 1}^K p(r_n|k) \ p(k|\theta).

On a log scale, that's

\log p(r|\theta) = \sum_{n=1}^N \log \sum_{k = 1}^K p(r_n|k) \ p(k|\theta).

The Example

I'll repeat the example here for convenience:

Isoform Expression Example

Suppose I have a gene with two isoforms, A and B, spliced from three exons, 1, 2, and 3. For simplicitly, we'll suppose all the exons are the same length. Suppose isoform A is made up of exon 1 and exon 2, and isoform B of exon 1 and 3. 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. In table form, we have the following mapping counts:

  Exon 1 Exon 2 Exon 3 Total
Iso 1 N 20 0 20+N
Iso 2 70-N 0 50 120-N
Total 70 20 50 140

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. That leaves the 70 reads falling in exon 1 to spread in some proportion between isoform 1 and isoform 2.

Turning the Crank In the Right Direction

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.

Now when we turn the crank, we see that

\log p(r|\theta) = \sum_{n=1}^N \log \sum_{k=1}^K p(r_n|k) p(k|\theta)

{} \ \ \ \ = 70 \log \sum_{k=1}^K p(1|k) p(k|\theta) + 20 \log \sum_{k=1}^K p(2|k) p(k|\theta) + 50 \log \sum_{k=1}^K p(3|k) p(k\theta)

= 20 \log \frac{\theta_1}{2} + 50 \log \frac{\theta_2}{2} + 70 \log (\frac{\theta_1}{2} + \frac{\theta_2}{2})

= 20 \log \theta_1 + 50 \log \theta_2 + (70 \log 1 -20\log 2 - 50 \log 2 - 70 \log 2).

The reduction on the third line is because the probability of a read in the second exon, p(2|k), is only non-zero for isoform k=1, and similarly for a read in the third exon, where p(3|k) is nly non-zero for the second gene or splice variant, k=2. The final reduction follows because \theta_1 + \theta_2 = 1.

Not so Biased After All

After marginalizing out the read mappings g, the MLE for expression is right where we'd expect it, at the solution of

\frac{d}{d\theta} \log p(r|\theta) = 0,

which is

\theta^*=20/70.

It turns out EM isn't so biased for these discrete mixtures, at least when you turn the crank the right way.


 
 

Things you can do from here:

 
 
Lable：
Read more »
Lable：

Chinese Information Retrieval with LingPipe and Lucene

Posted by jeffy Posted on 1:26 PM with No comments
from lingpipe-in-use « WordPress.com Tag Feed by lingpipe

The standard approach to information retrieval in English involves tokenizing text into a sequence of words, stemming the words to their morphological roots, then tossing out stop words that are too frequent or non-discriminative. This is how the standard settings work in Apache's Java-based Lucene search engine.

Taking this approach for Chinese would require being able to find the words. But the state of the art in Chinese word segmentation is only 97-98% or so on a relatively well-edited and homogeneous test set making up the third SIGHan segmentation bakeoff. And keep in mind that this is the usual average performance figure, with rarer words being harder to find. Out-of-training-vocabulary performance is at best 85%. Unfortunately, it's those rarer words in the long tail, likes names, that are often the key disrciminative component of a query.

It turns out that you can go a very long way indexing Chinese using character unigrams and bigrams. That is, instead of breaking text into tokens, pull out all the characters and index those as if they were words, then pull out all the two-character sequences and index those the same way. This is what we did for Technorati. The evaluation on real queries showed what you'd expect: very good recall, but often poor precision because of unintended cross-word and sub-word effects. Consider an English example of the word sequence "and add it to your", which would look like "andaddittoyour" without spaces. The problem is that without spaces, it matches the words "dad", "toy", "ditto", "you", and "our". (In swear word filtering, naive replacement in subwords leads to the "clbuttic" mistake).

By the way, subword problems come up in English at an alarming rate. How many of you know that "Spider-man" is two words while "Batman" is only one? In looking at customer query logs for TV data, we saw that users have no idea how many spaces to put in many examples. We just expect our search engines to have solved that one for us. They actually solve this problem roughly the same way as we suggest for Chinese. (This is also a problem in noun compounding languages like German and Danish, or generally highly compounding languages like Turkish.)

The cross-word effects would be completely mitigated if we could teach Chinese query writers to insert spaces between words. I'm told this is impossible given the conventions of the language, but my reply is "where there's a will, there's a way", and I think the adoption of Pinyin provides some direct support for my conjecture. But let's suppose we can't get the Chinese searchers to insert spaces; it won't take care of the subword problem anyway.

So how can we improve precision for unigram and bigram indexing? Add words when we can find them and let TF/IDF sort out the weights. This is the idea behind this paper, which evaluates a number of such combinations:

Jian-Yun Nie, Jiangfeng Gao, Jian Zhang, and Ming Zhou. 2001. On the Use of Words and N-grams for Chinese Information Retrieval.Proceedings of the 5th International Workshop Information Retrieval with Asian Languages.

The best indexing seems to arise from a mixture of character unigrams, character bigrams and words.

So how do we get the words? Two ways, for maximal precision and control. First, we use a dictionary. We can build an efficient tokenizer to find dictionary words using LingPipe's Aho-Corasick implementation dict.ExactDictionaryChunker, the use of which is described in the javadoc and in the named entity tutorial. Just make sure you use the right tokenizer, which for Chinese would be thetokenizer.CharacterTokenizerFactory. A dedicated implementation would be faster than going through tokenizers, given that we're treating each character as a token.

As to where to find a dictionary, that's up to you. Training data is still available on the old SIGHan site or from LDC.

The second approach to word spotting can be approximate, and for that, we recommend our noisy channel Chinese word segmenter, as described in our tutorial on Chinese word segmentation.

The only fiddly bits of coding are wrapping up our dictionary chunker and chinese word segmenter as Lucene analyzers (see lucene.analysis.Analyzer. You can see how to adapt LingPipe tokenizer factories for use as Lucene analyzers in our new sandbox project LingMed; look for the top-level read-me.html file and the adapter implementation for LingPipe tokenizers insrc/com/aliasi/lingmed/lucene/LuceneAnalyzer.java.

We've sidestepped the fact that Chinese has two distinct ways of rendering characters, traditional Chinese characters (used mainly in Taiwan and Hong Kong and among ex-pats) and simplifed Chinese characters (used primarily on the mainland). The unicode standard, of course, contains both.

It's a simple matter to load a single dictionary on both types of characters, and a single word segmenter operating over both types of characters. We've had good luck in training multilingual (English/Hindi) named entity extractors. It works because it relies on local context to predict words, and local context is almost always homogeneous in character set. That way, you can handle docs with mixed character sets and don't have to do a character set ID pass up front (which is tricky, because the code points overlap in unicode and queries are often short).

We should point out that this method can also work for Japanese. Though you might want to up the n-gram count for the syllabic characters in Hirigana and Katakana, while keeping 1-grams and 2-grams for the imported Chinese ideograms making upKanji.

Lable：
Read more »
Lable：

The Effect of Annotator Error on Classifier Evaluation

Posted by jeffy Posted on 3:30 PM with 27 comments

The Effect of Annotator Error on Classifier Evaluation

from LingPipe Blog by lingpipe

Anyone who’s looked at a corpus realizes that the “gold standards” are hardly 24 karat; they are full of impurities in the form of mislabeled items. Just how many, no one really knows. That’d require a true gold standard to evaluate! We’ve been wondering how we can conclude we have a 99.9% recall entity annotator when the gold standard data’s highly unlikely to be 100% accurate itself.

Check out this 2003 publication from the OpenMind Initiative’s list of publications:

Lam, Chuck P. and David G. Stork. 2003. Evaluating classifiers by means of test data with noisy labels. In Proceedings of IJCAI.

In particular, table 1, which plots the observed error rates for different true error rates and corpus mislabeling rates. Here’s a small slice:

Corpus Mislabeling Rate

True Classifier Error
1%
3%
5%

2%
3.0%
4.9%
6.8%

6%
6.9%
8.6%
10.4%

10%
10.8%
12.4%
14%

Observed Classifier Error vs. Mislabeled Corpus

For simplicity, Lam and Stork assumed the classifier being evaluated and the data annotators make independent errors. This is not particularly realistic, as problems that are hard for humans tend to be hard for classification algorithms, too. Even the authors point out that it’s common for the same errors to be in training data and test data, thus making it very likely errors will be correlated.

Lam and Stork’s paper is also the first I know to raise the problem addressed by Sheng et al.’s 2008 KDD paper, Get Another Label?, namely:

… it is no longer obvious how one should spend each additional labeling effort. Should one spend it labeling the unlabeled data, or should one spend it increasing the accuracy of already labeled data?   (Lam and Stork 2003)

Lam and Stork also discuss a problem related to that discussed in Snow et al.’s 2008 EMNLP paper, Cheap and Fast - But is it Good?, namely how many noisy annotators are required to estimate the true error rate (their figure 1). The answer, if they’re noisy, is “a lot”. Snow et al. considered how many really noisy annotators were required to recreate a gold standard approximated by presumably less noisy annotators, which is a rather different estimation.

Of course, this is all very Platonic in assuming that the truth is out there. Here at Alias-i, we are willing to accept that there is no truth, or at least that some cases are so borderline as to not be encompassed by a coding standard, and that any attempt to extend the standard will still leave a fuzzy boundary.

The question we have now is whether our models of annotation will distinguish the borderline cases from hard cases. With hard cases, enough good annotators should converge to a single truth. With borderline cases, there should be no convergence.

Lable：
Read more »
Lable：

Hierarchical Bayesian Models of Categorical Data Annotation

Posted by jeffy Posted on 8:20 PM with 2 comments
originally by lingpipe

Here’s a 2 page write-up of one of the models I’ve been looking at for evaluating data annotation in order to evaluate coding standards and annotator sensitivity and specificity:

* Carpenter, Bob. 2008. Hierarchical Bayesian Models of Categorical Data Analysis.

I’ve submitted it as a poster to the New York Academy of Sciences 3rd Annual Machine Learning Symposium, which will be October 10, 2008.

Please let me know what you think (carp@alias-i.com). I didn’t have room to squeeze in the more complex model that accounts for “easy” items. This model and the one for easy items derive from the epidemiology literature (cited in the paper), where they’re trying to estimate disease prevalence from a heterogeneous set of tests. I’ve added some more general Bayesian reasoning, and suggested applications for annotation (though Bruce and Wiebe were mostly there in their 1999 paper, which I cite), and for training using probabilistic supervision (don’t think anyone’s done this yet).

I’m happy to share the R scripts and BUGS models I used to generate the data, fit the models, and display the results. I’d also love to know how to get rid of those useless vertical axes in the posterior histogram plots.
Read more »
Lable： ,

Dissertation: Statistical Machine Translation: From Single-Word Models to Alignment Templates

Posted by jeffy Posted on 5:42 AM with No comments
Author: Och, Franz Josef

Title: Statistical Machine Translation: From Single-Word Models to

Alignment Templates

Year: 2002

University: Technical University Aachen

http://darwin.bth.rwth-aachen.de/opus3/frontdoor.php?source_opus=529&...

In this work, new approaches for machine translation using statistical

methods are described. In addition to the standard source-channel

approach to statistical machine translation, a more general approach

based on the maximum entropy principle is presented. Various methods

for computing single-word alignments using statistical or heuristic

models are described. Various smoothing techniques, methods to

integrate a conventional dictionary and training methods are analyzed.

A detailed evaluation of these models is performed by comparing the

automatically produced word alignment with a manually produced

reference alignment. Based on these fundamental single-word based

alignment models, a new phrase-based translation model - the alignment

template model - is suggested. For this model, a training and an

efficient search algorithm is developed. For two specific applications

(interactive translation and multi-source translation) specific search

algorithms are developed. The suggested machine translation approach

has been tested for the German-English Verbmobil task, the French-

English Hansards task and for Chinese-English news text translation.

Often, the obtained results have been significantly better than those

obtained with alternative approaches to machine translation.
Lable：
Read more »
Lable：

EM Clustering, Fat Gaussians and Number of Clusters

Posted by jeffy Posted on 5:35 AM with 1 comment

EM Clustering, Fat Gaussians and Number of Clusters

从 LingPipe Blog 作者：lingpipe

I just got back from a very nice talk at Columbia by Sanjoy Dasgupta, who’s on leave at Yahoo! from UCSD. The talk was basically about an old paper, Dasgupta and Schulman 2000, in which the authors introduce a “fat Gaussian” to overcome the curse of dimensionality in EM (soft) clustering.


Dasgupta started by making the point that a Gaussian with 1000
independent dimensions has almost all sample points roughly the same
distance from the mean, which is easy to prove given the central limit
theorem. In other words, the standard Gaussian defines a thin
high-likelihood shell around the expected distance. In reality (or at
least in experimental data sets), data’s more dispersed than
independent high-dimensional Gaussians can represent. Therefore, they
introduce fat Gaussians, which are just mixtures of Gaussians with
different variances, thus averaging over a bunch of thin shells at
their respective expected distances from the mean. He went on to show
various separability results for clustering based on these fat
Gaussians and mostly separable data.


What struck me most about the talk was Dasgupta’s answer to a
question from an audience member who asked if his method would help
determine the number of clusters. This is a perennial problem in
clustering. K-means and EM-clustering require the number of clusters to
be set ahead of time. Dasgupta’s answer was in two parts. The official
answer was “no”. But he qualified that by saying that what he really
believed was that the problem was ill-formed because different numbers
of clusters were useful for different applications.


Some natural language processing problems are like this, and some
are different. Categorizing documents by topic is like this, because
the world doesn’t come pre-segmented into a known number of topics. For
instance, we might categorize news into business, politics, sports and
entertainment, leading to four categories. Or we might go further, and
divide them into regional and international politics, baseball, soccer
and bowling, and movies versus music. It depends on the application.


But one reason we’re interested in clustering is for coreference
resolution, including database deduplication and grouping mentions of
the same entity (such as a consumer electronics product, gene name or
person) in text. For these tasks, there is a notion of “true” number of
clusters, though one might quibble that Bob-as-cook is different than
Bob-as-programmer.


EM clustering that estimates means and variances in a maximum
likelihood setting is ill-formed. The max likelihood solution in the
2-cluster setting places one cluster mean on a single data point with
zero variance, leading to an infinite value of the density for that
point, with the other points belonging to a single high-variance
covering distribution. One solution to this problem is to fix the
variances to positive values ahead of time and only estimate the means.


Another thing that strikes me about EM clustering is that it’s
almost always done with a uniform distribution over categories. That
is, the likelihood of a point x being in cluster c is p(c) * p(x|c).
I’ve never seen a presentation of Gaussian EM clustering where p(c) is
taken to be anything other than uniform. That is, we’re not modeling
the situation where clusters have different likelihoods — the
generative model is to draw a cluster according to a uniform
distribution and then draw a point from that cluster’s distribution.


The Bayesian (equivalently minimum description length) solution to
the number of clusters problem also addresses the uniform-cluster size
problem. Specifically, we put a prior on the model structure and then
choose the clustering that maximizes the likelihood times the prior:
p(data|model) * p(model). The standard Bayesian prior for this kind of
setting would comprise something like a Dirichlet process prior on the
distribution of categories p(c); we could also put Bayesian priors on
the means or more commonly variances of the Gaussians. With a Dirichlet
process, there is no bound on the number of categories, and draws from
a Dirichlet process prior lead to power-law (Zipf-like) distributions
of number and size of categories. You can see this working quite well
in coreference resolution as evidenced by the recent paper Haghighi and Klein 2007.


The only problem with the Bayesian “solution” is that the
concentration parameter of the Dirichlet process prior is just another
way of setting k. That is, you need to make a prior assumption about
how costly it is to introduce new categories. This is just replacing a
direct control (number of clusters) with an indirect one (cost to
introduce a new cluster). Haghighi and Klein, for instance, set the
concentration parameter of their Dirichlet process prior empirically.

Lable：
Read more »
Lable：

pinning Straw into Gold: How to do gold standard data right

Posted by jeffy Posted on 5:33 AM with 1 comment
How to do gold standard data right
LingPipe Blog author：lingpipe

We
have been struggling with how to evaluate whether we are finding ALL
the genes in MEDLINE/PubMed abstracts. And we want to do it right.
There has been a fair amount of work on how to evaluate natural
language problems–search via TREC, BIOCREATIVE, MEDTAG but nothing out
there really covered what we consider to be a key problem in text based
bioinformatics–coverage or recall in application to existing databases
of Entrez Gene.


What is the Rumpelstiltskin tie in?


From the Wikipedia:


“In order to make himself appear more important, a miller lied to
the king that his daughter could spin straw into gold. The king called
for the girl, shut her in a tower room with straw and a spinning wheel,
and demanded that she spin the straw into gold by morning, for three
nights, or be executed. ” Much drama ensues but in the end a fellow
named Rumpelstiltskin saves the day.


The cast breaks down as follows:


  • The king: The National Institutes of Health (NIH) who really prefer that you deliver on what you promise on grants.
  • The miller: Our NIH proposal in which we say “We are
    committed to making all the facts, or total recall, available to
    scientists…” Even worse is that this is from the one paragraph summary
    of how we were going to spend $750,000 of the NIH’s money. They will be
    asking about this.
  • The daughter: I (Breck), who sees lots of straw and no easy path to developing adequate gold standard data to evaluate ourselves against.
  • The straw: 15 million MEDLINE/PubMed abstracts and 500,000
    genes that need to be connected in order to produce the gold. Really
    just a subset of it.
  • The gold: A scientifically valid sample of mappings between
    genes and abstracts that we can test our claims of total recall. This
    is commonly called “Gold Standard Data.”
  • Rumpelstiltskin: Bob, and lucky for me I do know his name.

Creating Gold from Straw


Creating linguistic gold standard data is difficult, detail
oriented, frustrating and ultimately some of the most important work
that one can do to take on natural language problems seriously. I was
around when version 1 of the Penn Treebank was created and would chat
with Beatrice Santorini about the difficulties they encountered for
things as simple seeming as part-of-speech tagging. I annotated MUC-6
data for named entities and coreference, did the John Smith corpus of
cross-document coref with Amit Bagga and have done countless customer
projects. All of those efforts gave me insights that I would not have
had otherwise about how language is actually used rather than the
idealized version you get in standard linguistics classes.


The steps for creating a gold standard are:


  • Define what you are trying to annotate: We started with a
    very open ended “lets see what looks annotatable” attitude for linking
    Entrez Gene to MEDLINE/PubMed. By the time we felt we had a
    sufficiently robust linguistic phenomenon we had a standard that mapped
    abstracts as a whole to gene entries in Entrez Gene. The relevant
    question was: “Does this abstract mention anywhere a literal instance
    of the gene?” Gene families were not taken to mention the member genes,
    so “the EXT familly of genes” would not count, but “EXT1 and EXT2 are
    not implicated in autism” would.
  • Validate that you can get multiple people to do the same annotation:
    Bob and I sat down and annotated 20 of the same abstracts independently
    and compared our results. We found that we had 36 shared mappings from
    gene to abstract, with Bob finding 3 mappings that Bob did not and I
    found 4 that Bob did not. In terms of recall I found 92% (36/39) of
    what Bob did. Bob found 90% (36/40) of what I found. Pretty good eh?
    Not really, see below.
  • Annotate enough data to be statistically meaningful: Once we
    are convinced we have a reliable phenomenon, then we need to be sure we
    have enough examples to minimize chance occurrences.

The Tricky Bit


I (the daughter) need to stand in front of the king (the NIH) and
say how good our recall is. Better if the number is close to 100%
recall. But what is 100% recall?


Even a corpus annotation with an outrageously high 90% interannoatator

agreement leads to problems:


  • A marketing problem: Even if we hit 99.99% recall on the corpus, we don’t know what’s up with the 5% error.

    We can report 99.99% recall against the corpus, but not against the truth.

    after being total rock stars and modeling Bob at 99.99%, a slide that
    says we can only claim recall of 85-95% on the data. So I can throw out
    the 99.99% number and introduce a salad of footnotes and diagrams. I
    see congressional investigations in my future.
  • A scientific problem: It bugs me that I don’t have a handle
    on what truth looks like. We really do think recall is the key to text
    bioinformatics and that text bioinformatics is the key to curing lots
    of diseases.

Rumpelstiltskin Saves the Day


So, here we are in our hip Brooklyn office space, sun setting
beautifully over the Williamsburg bridge, Bob and I are sitting around
with a lot of straw. It is getting tense as I imagine the king’s
reaction to the “standard approach” of working from an interannotator
agreement validated data set. Phrases like “cannot be done in a
scientifically robust way”, “we should just do what everyone else does”
and “maybe we should focus on precision” were bandied about with
increasing panic. But the next morning Rumpelstiltskin walked in with
the gold. And it goes like this:


The problem is in estimating what truth is given somewhat unreliable
annotators. Assuming that Bob and I make independent errors and after
adjudication (we both looked at where we differed and decided what the
real errors were) we figured that each of us would miss 5% (1/20) of
the abstract to gene mappings. If we took the union of our annotations,
we end up with .025% missed mentions (1/400) by multiplying our recall
errors (1/20*1/20)–this assumes independence of errors, a big
assumption.


Now we have a much better upper limit that is in the 99% range, and
more importantly, a perspective on how to accumulate a recall gold
standard. Basically we should take annotations from all remotely
qualified annotators and not worry about it. We know that is going to
push down our precision (accuracy) but we are not in that business
anyway.


An apology


At ISMB in Detroit, I stood up and criticized the BioCreative/GENETAG folks for adopting a crazy-seeming annotation standard
that went something like this: “Annotate all the gene mentions in this
data. Don’t get too worried about the phrase boundaries, but make sure
the mention is specific.” I now see that approach as a sane way to
increase recall. I see the error of my ways and feel much better since
we have demonstrated 99.99% recall against gene mentions for that
task–note this is a different, but related task to linking Entrez Gene
ids to text abstracts. And thanks to the BioCreative folks for all the
hard work pulling together those annotations and running the bakeoffs.

Lable：
Read more »
Lable：

Logistic Regression by Any Other Name

Posted by jeffy Posted on 5:24 AM with 7 comments

Logistic Regression by Any Other Name

LingPipe Blog

I
(Bob) have been working on logistic regression. In particular,
multinomial logistic regression with a range of different priors and a
sparse regularized stochastic gradient descent optimizer. It’ll be out
in LingPipe 3.5 any day now.


I wrote up everything I learned in a white paper, Lazy Sparse Stochastic Gradient Descent for Regularized Multinomial Logistic Regression. The result was a slew of algebra reminiscent of Dan Klein and Chris Manning’s max-ent tutorial, but with more general regularization, a different (k-1)-vector parameterization, and a different optimization scheme.


I added a new white papers section
to the blog to hold it. I made a minor original contribution: a
stochastic gradient descent algorithm with regularization that fully
preserves both sparseness and the stocahsticity of regularization.


The amount of math I had to do to put the pieces back together took me straight back to grad school. My parents are visiting
and asked me last night why there was an enormous pile of math books on
the table (Strang on matrices [I couldn’t remember what positive
definite means], a calc textbook [I couldn’t even remember how to
differentiate logs and exponentials], Larsen and Marx (or was it
DeGroot and Schervish?) [need the basic density definitions and
properties], Gelman et al.’s Bayesian Data Analysis and Regression
books, rounded off with Bishop’s, MacKay’s, and Hastie et al.’s trio of
machine learning books and Manning and Schuetze for good measure). The
answer is that they all contained pieces of the puzzle.


I work out the full error function under maximum likelihood and
Gaussian, Laplace and Cauchy priors, derive the gradients and Hessians,
and show how to build it all into a stochastic gradient descent solver.
I show the links between logistic regression and max entropy, work out
the impact of feature functions, exponential bases, binary features,
input centering and variance normalization, and even kernel methods. I
have to admit I skipped full duality (but did talk about
kernelization), didn’t work out the Hessian positive definiteness proof
for error function is concavity, and don’t cover any of the convergence
proofs for SGD. But there are lots of references to books, papers,
tutorials and software packages.


I have to admit that during this process I felt like the great
Nicolai Ivanovich Lobachevsky as satirized in the Tom Lehrer song Lobachevsky.


The unit tests are now passing. I’d like to thank Dave Lewis
for help with test cases and understanding some of the math. Dave and I
were undergrad math majors at Michigan State together, and now find
ourselves doing logistic regression for NLP; he’s contributing to the BMR: Bayesian Multinomial Regression Software package (check out their cool use of priors for IDF-like term weighting).


One of the problems I had is the diverse literature around
regularized logistic regression and the sheer volume of terms used to
refer to it and its properties. Ditto for the stochastic gradient and
other optimization literature. Here’s the “also known as” section from
the forthcoming LingPipe 3.5 Javadoc (we’re our own search engine optimization providers):








Multinomial logistic regression is also known as polytomous,
polychotomous, or multi-class logistic regression, or just multilogit
regression.


Binary logistic regression is an instance of a generalized linear model (GLM) with the logit link function.


The logit function is the inverse of the logistic function, and the
logistic function is sometimes called the sigmoid function or the
s-curve.


Logistic regression estimation obeys the maximum entropy principle,
and thus logistic regression is sometimes called “maximum entropy
modeling”, and the resulting classifier the “maximum entropy
classifier”.


The generalization of binomial logistic regression to multinomial
logistic regression is sometimes called a softmax or exponential model.


Maximum a priori (MAP) estimation with Gaussian priors is often
referred to as “ridge regression”; with Laplace priors MAP estimation
is known as the “lasso”. MAP estimation with Gaussian, Laplace or
Cauchy priors is known as parameter shrinkage. Gaussian and Laplace are
forms of regularized regression, with the Gaussian version being
regularized with the L2 norm (Euclidean distance, called the
Frobenius norm for matrices of parameters) and the Laplace version
being regularized with the L1 norm (taxicab distance or Manhattan metric); other Minkowski metrics may be used for shrinkage.


Binary logistic regression is equivalent to a one-layer,
single-output neural network with a logistic (sigmoid) activation
function trained under log loss. This is sometimes called
classification with a single neuron.



Lable：
Read more »
Lable：

(Abstract) Base Classes vs. Interfaces

Posted by jeffy Posted on 7:17 PM with No comments
(Abstract) Base Classes vs. Interfaces
从 LingPipe Blog 作者：lingpipe


When definining a low-level abstraction as part of a framework, say vectors and matrices to make this concrete, there’s a choice of whether to code to interfaces or specify a (possibly abstract) base class.

There are two key differences between the base class and interface approach. First, in Java (and .NET from what I gather), classes must extend exactly one other class (Object is the default), but can implement zero or more interfaces. Second, interfaces can’t specify any implementations of methods (though they may define static constants).

But as Kirill Osenkov’s blog entry Choosing: Interface vs. Abstract Class points out, there are serious downstream consequences of this choice.

Most notably, once an interface is released, it has profound backward compatibility implications. Particularly, any attempt to add a method to the interface will break backward compatibility for anyone who has implemented the interface. As long as the base class implements the added method, there’s no such problem.

The conclusion I’ve come to after several years of coding to interfaces (following the Java collections framework for guidance), is that they almost all should’ve been (abstract) base classes. The exceptions are util.Compilable, util.Scored, and other lightweight marker-type interfaces, most notably corpus.Handler.

So what do you do if you forgot a critical method in an interface? I’m in that position right now with our matrix.Vector interface. I’ve just implemented multinomial logistic regression classification (aka max entropy, aka soft max, aka log linear classifiers) and found that I need two new vector operations to make the inner loop efficient. One, I need to be able to find the non-zero dimensions of a vector, and two, I need to add a scaled sparse vector to a vector.

I’ve added the methods to the interface and to the low-level abstract implementation matrix.AbstractVector.

I’m banking on no one having implemented Vector, because there’s really no reason to do it, so changing the interface won’t be so terrible.

I’d dearly love to add a method to the tokenizer.TokenizerFactory interface to create tokenizers from character sequences as well as slices. But alas, I fear too many users have coded to the existing interface, so I’m not going to do that.
Lable：
Read more »
Lable：

How Fat is Your (Prior’s) Tail?

Posted by jeffy Posted on 7:14 PM with No comments
How Fat is Your (Prior’s) Tail?
This paper is from LingPipe Blog






What kind of prior should you use for logistic regression (aka maximum entropy) coefficients? The common choices are the Laplace prior (aka L1 regularization, aka double exponential prior, aka the lasso), the Gaussian prior (aka L2 regularization, aka normal, aka ridge regression), and more recently, the Cauchy prior (aka Lorentz, aka Student-t with one degree of freedom).

These are all symmetric priors, and we typically use zero mean distributions as priors (or zero median in the Cauchy, which has no mean because the integral diverges). The effect is that there’s a penalty for larger coefficients, or looked at the other way, the priors shrink the parameters.

The main difference between the priors is how fat their tails are. For a given variance, the Laplace prior has very thin tails compared to the Gaussian, and the Cauchy has very thick tails compared to the Gaussian.

There’s an interesting paper by Goodman, Exponential Priors for Maximum Entropy Models, for which Microsoft received a blatantly ridiculous patent. Maybe we’ll get a nastygram from Redmond for using a textbook technique. Like the stats textbooks, Goodman notes that the Laplace prior likes to shrink coefficients to zero, effectively performing a kind of Bayesian feature selection.

There’s also a more recent offering by Genkin, Lewis and Madigan, Large-scale Bayesian logistic regression for text categorization, which covers both L1 and L2 regularization, which also comes with an open-source implementation for the multinomial case. This paper does a good job of comparing regularized logistic regression to SVM baselines. Dave Lewis has been a great help in understanding the math and algorithms behind logistic regression, particularly the one-parameter vector vs. two-parameter vector case, and the implications for priors and offsets in sparse computations.

There’s an interesting paper by Gelman, Jakulin, Su and Pittau, A Default Prior Distribution for Logistic and Other Regression Models, in which they argue that after centering and variance adjusting inputs, the Cauchy prior is a good general purpose prior. They evaluate on a range of binary classification problems.

I just had coffee with Andrew Gelman after guest-lecturing in his stat computation class, and we had a chat about regularization and about discriminitive versus generative models. He wasn’t happy with Laplace priors being applied willy-nilly, suggesting instead that feature selection be done separately from feature estimation. Andrew also surprised me in that he thinks of logistic regression as a generative model (”of course it’s generative, it’s Bayesian”, I believe he said); but for me, this is odd, because the data’s “generated” trivially. He was keen on my trying out some kind of posterior variance fiddling to move from a maximum a posteriori form of reasoning to a more Bayesian one. The only problem is that I just can’t invert the million by million matrix needed for the posterior variance estimates.

The issue here is a culture conflict between “machine learning” and “statistics”. If you read Hill and Gelman’s book on regression, it’s study after study of small dimensionality problems with dense data, not much data, and carefully engineered features and interaction features. Natural language problems, like most machine learning problems, involve millions of features and very sparse vectors. Maybe different techniques work better for quantitatively different problems.
Lable：
Read more »
Lable：

Symbols as Hash Codes for Super-fast Linear Classifiers

Posted by jeffy Posted on 7:12 PM with No comments
Symbols as Hash Codes for Super-fast Linear Classifiers
this paper is from LingPipe Blog

I was talking to John Langford, of Machine Learning(Theory) blog fame, after his talk in the Columbia machine learning reading group yesterday.

He mentioned a way to speed up linear classifiers at runtime that’s intriguing. A binary linear classifier is based on the dot product of a weight vector β (almost always dense) with a feature vector x (almost always sparse). Examples of linear classifiers include perceptrons, logistic regression, naive Bayes/multinomial, SVMs, and it’s even the innermost loop in discriminitive sequence models like CRFs.

The bottleneck at runtime for linear classifiers is converting the objects being classified into sparse vectors. If you use a symbol table, the bottleneck is the hash lookup in the symbol table. The feature weight vector β is almost always an array, so once you have the symbol ID, you pay the array lookup, multiplication of feature weight (typically 1 in NLP problems) by value found, and add to the sum for the dot product. Only the array lookup is time consuming here.

Actually constructing the sparse vector itself would also be expensive, but this can be done implicitly, because all we need is the dot product of the vector with the parameter

So what happens if we replace the symbol generated by a symbol table with a hash code? Instant speedup. We eliminate the expensive hash lookup, which requires an array lookup almost certainly out of L2 cache, and then iterating over the collision set doing a string-match until we get a match or exhaust the bucket.

The price we pay is possible collisions. In effect, any two features that have the same hash code get conflated. If we’re doing 20 newsgroups and trying to distinguish hockey posts from baseball posts, it’s going to hurt accuracy if the hashcode of “goalie” and “pitcher” are the same, as they’re highly discriminitive in this domain.

Now we’re going to use a hash code that produces numbers in a small range, say 0 to 2**18, or 18 bits, so that an array of floats or doubles of that size fits in L2 cache on our CPU. Now we’re really flying. The symbol we’re looking up will fit in a register, so computing its hash code will be pretty fast. It’s the lookup out of cache and subsequent matching that’s the time-sink.

In practice, John reports that experiments they’ve done have shown that this isn’t a problem. He found this somewhat surprising, but I didn’t. Language is highly redundant, so a few features being conflated is unlikely to hurt performance much. It’d be interesting to see a plot of size of hash table vs. number of features vs. accuracy.

This approach extends to the more complex, structured features common in discriminitive classifiers. We never need to build an explicit feature representation if we can generate a hash code for it.

If we ever have to make a simple classifier that really flies, this is what I’ll be thinking about. I might also be thinking about perfect hashing, because I’m a neat freak.
Lable： ,
Read more »
Lable： ,
loading..

Popular Posts