You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Benson Margulies <bi...@gmail.com> on 2010/02/13 18:38:05 UTC
Confidence estimation in a beam decoder
Folks,
Here's one of my occasional questions in which I am, in essence,
bartering my code wrangling efforts for expertise on hard stuff.
Consider a sequence problem addressed with a perceptron model with an
ordinary Viterbi decoder. There's a standard confidence estimation
technique borrowed from HMMs: calculate gamma = alpha + beta for each
state, take the difference of the gammas for the best and second best
hypothesis for each column of the trellis, and take argmin of them as
the overall confidence of the decode. (+, of course, because in a
perceptron we're summing feature weights, not multiplying
probabilities.)
This has been observed by better minds than mine to yield a confidence
estimation that is useful in doing active learning for training data
selection.
Now consider a beam decoder (*). Beta is not practically available. We
came up with the following idea for a next-best-idea. Whenever we
decide to keep something in the beam, estimate confidence as:
abs(feature sum of what we're keeping - feature sum of the next one
down the stack) / abs(feature sum of what we're keeping)
Then take argmin of that across the sentence, and call that a confidence.
To get some idea of whether this was valid, I put in the code to run
Pearson's product moment correlation coefficient on the accuracy on
each sentence versus the confidence. The results are awful.
So, if anyone has any ideas as to (a) if there's a better way to
evaluate this, or (b) if there's a better way to estimate confidence,
I'm all ears.
(*) for the curious, we're doing Asian-text segmentation with a beam
decoded perceptron model.
Re: Confidence estimation in a beam decoder
Posted by Benson Margulies <bi...@gmail.com>.
On Sun, Feb 14, 2010 at 4:47 PM, Ted Dunning <te...@gmail.com> wrote:
> Benson,
>
> One more thing. I forget the actual reference, but the best Chinese
> segmenter that I have seen in practice (whose name I forget) was able to get
> away with a simple unweighted lexicon and 2-3 word look-ahead + average word
> length for score.
That's more or less what our existing 'legacy' algorithmic code does.
It has very good accuracy overall, but there are important cases where
that approach runs into trouble.
The thing we're currently working with is
http://acl.ldc.upenn.edu/P/P07/p07-1106.pdf.
I follow the argument you are making here, though, and I'm thinking
about how to detect what I'd call 'word sausage boundaries.'
> This indicates to me that you can depth bound your beam
> search and turn it into an exhaustive search. The lesson of their success
> is that garden path sentences (with regard to segmentation) are rare in
> Chinese.
Re: Confidence estimation in a beam decoder
Posted by Benson Margulies <bi...@gmail.com>.
I should rephrase one thing. Our current product \started out/ a lot
like that. It wasn't good enough for the Google's of the world, so it
started to grow hair. We're looking at a statistical retread because
the hair gets harder and harder to comb.
On Sun, Feb 14, 2010 at 4:47 PM, Ted Dunning <te...@gmail.com> wrote:
> Benson,
>
> One more thing. I forget the actual reference, but the best Chinese
> segmenter that I have seen in practice (whose name I forget) was able to get
> away with a simple unweighted lexicon and 2-3 word look-ahead + average word
> length for score. This indicates to me that you can depth bound your beam
> search and turn it into an exhaustive search. The lesson of their success
> is that garden path sentences (with regard to segmentation) are rare in
> Chinese.
>
> On Sun, Feb 14, 2010 at 10:29 AM, Benson Margulies <bi...@gmail.com>wrote:
>
>> Ted, thanks very much.
>>
>> Thoughts in response to both of your messages:
>>
>> 1: alpha-beta is being used here in the sense of E+M. Or, to be
>> specific, alpha is the path sum from the beginning to the current
>> 'time', and beta is the path sum from the current 'time' to the end.
>>
>> 2: I had read about that 'at the margin' idea and completely forgotten
>> it. My starting point here is Miller and Guiness (one of whom used to
>> work with me and the other of whom still does). They didn't report,
>> and perhaps didn't measure, whether the examples selected via that
>> 'gamma' calculation had high error rates (far from the margin?) or low
>> error rates (close to the margin). They just observed that
>>
>> 3: A scatter-plot looks like what the doctor ordered.
>>
>> 4: That paper is new to me. My stack of papers in this neighborhood is
>> Collins, Miller + Guiness, Crammer (on Passive-Aggressive) and the
>> Oxford paper on segmentation. Thanks for the pointer.
>>
>> --benson
>>
>> On Sat, Feb 13, 2010 at 11:18 PM, Ted Dunning <te...@gmail.com>
>> wrote:
>> > Benson,
>> >
>> > Are you using techniques related to this:
>> > http://www.it.usyd.edu.au/~james/pubs/pdf/dlp07perc.pdf<http://www.it.usyd.edu.au/%7Ejames/pubs/pdf/dlp07perc.pdf>?
>> >
>> >
>> >
>> > On Sat, Feb 13, 2010 at 9:38 AM, Benson Margulies <bimargulies@gmail.com
>> >wrote:
>> >
>> >> Folks,
>> >>
>> >> Here's one of my occasional questions in which I am, in essence,
>> >> bartering my code wrangling efforts for expertise on hard stuff.
>> >>
>> >> Consider a sequence problem addressed with a perceptron model with an
>> >> ordinary Viterbi decoder. There's a standard confidence estimation
>> >> technique borrowed from HMMs: calculate gamma = alpha + beta for each
>> >> state, take the difference of the gammas for the best and second best
>> >> hypothesis for each column of the trellis, and take argmin of them as
>> >> the overall confidence of the decode. (+, of course, because in a
>> >> perceptron we're summing feature weights, not multiplying
>> >> probabilities.)
>> >>
>> >>
>> >
>>
>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
>
Re: Confidence estimation in a beam decoder
Posted by Ted Dunning <te...@gmail.com>.
Benson,
One more thing. I forget the actual reference, but the best Chinese
segmenter that I have seen in practice (whose name I forget) was able to get
away with a simple unweighted lexicon and 2-3 word look-ahead + average word
length for score. This indicates to me that you can depth bound your beam
search and turn it into an exhaustive search. The lesson of their success
is that garden path sentences (with regard to segmentation) are rare in
Chinese.
On Sun, Feb 14, 2010 at 10:29 AM, Benson Margulies <bi...@gmail.com>wrote:
> Ted, thanks very much.
>
> Thoughts in response to both of your messages:
>
> 1: alpha-beta is being used here in the sense of E+M. Or, to be
> specific, alpha is the path sum from the beginning to the current
> 'time', and beta is the path sum from the current 'time' to the end.
>
> 2: I had read about that 'at the margin' idea and completely forgotten
> it. My starting point here is Miller and Guiness (one of whom used to
> work with me and the other of whom still does). They didn't report,
> and perhaps didn't measure, whether the examples selected via that
> 'gamma' calculation had high error rates (far from the margin?) or low
> error rates (close to the margin). They just observed that
>
> 3: A scatter-plot looks like what the doctor ordered.
>
> 4: That paper is new to me. My stack of papers in this neighborhood is
> Collins, Miller + Guiness, Crammer (on Passive-Aggressive) and the
> Oxford paper on segmentation. Thanks for the pointer.
>
> --benson
>
> On Sat, Feb 13, 2010 at 11:18 PM, Ted Dunning <te...@gmail.com>
> wrote:
> > Benson,
> >
> > Are you using techniques related to this:
> > http://www.it.usyd.edu.au/~james/pubs/pdf/dlp07perc.pdf<http://www.it.usyd.edu.au/%7Ejames/pubs/pdf/dlp07perc.pdf>?
> >
> >
> >
> > On Sat, Feb 13, 2010 at 9:38 AM, Benson Margulies <bimargulies@gmail.com
> >wrote:
> >
> >> Folks,
> >>
> >> Here's one of my occasional questions in which I am, in essence,
> >> bartering my code wrangling efforts for expertise on hard stuff.
> >>
> >> Consider a sequence problem addressed with a perceptron model with an
> >> ordinary Viterbi decoder. There's a standard confidence estimation
> >> technique borrowed from HMMs: calculate gamma = alpha + beta for each
> >> state, take the difference of the gammas for the best and second best
> >> hypothesis for each column of the trellis, and take argmin of them as
> >> the overall confidence of the decode. (+, of course, because in a
> >> perceptron we're summing feature weights, not multiplying
> >> probabilities.)
> >>
> >>
> >
>
--
Ted Dunning, CTO
DeepDyve
Re: Confidence estimation in a beam decoder
Posted by Benson Margulies <bi...@gmail.com>.
Ted, thanks very much.
Thoughts in response to both of your messages:
1: alpha-beta is being used here in the sense of E+M. Or, to be
specific, alpha is the path sum from the beginning to the current
'time', and beta is the path sum from the current 'time' to the end.
2: I had read about that 'at the margin' idea and completely forgotten
it. My starting point here is Miller and Guiness (one of whom used to
work with me and the other of whom still does). They didn't report,
and perhaps didn't measure, whether the examples selected via that
'gamma' calculation had high error rates (far from the margin?) or low
error rates (close to the margin). They just observed that
3: A scatter-plot looks like what the doctor ordered.
4: That paper is new to me. My stack of papers in this neighborhood is
Collins, Miller + Guiness, Crammer (on Passive-Aggressive) and the
Oxford paper on segmentation. Thanks for the pointer.
--benson
On Sat, Feb 13, 2010 at 11:18 PM, Ted Dunning <te...@gmail.com> wrote:
> Benson,
>
> Are you using techniques related to this:
> http://www.it.usyd.edu.au/~james/pubs/pdf/dlp07perc.pdf ?
>
>
>
> On Sat, Feb 13, 2010 at 9:38 AM, Benson Margulies <bi...@gmail.com>wrote:
>
>> Folks,
>>
>> Here's one of my occasional questions in which I am, in essence,
>> bartering my code wrangling efforts for expertise on hard stuff.
>>
>> Consider a sequence problem addressed with a perceptron model with an
>> ordinary Viterbi decoder. There's a standard confidence estimation
>> technique borrowed from HMMs: calculate gamma = alpha + beta for each
>> state, take the difference of the gammas for the best and second best
>> hypothesis for each column of the trellis, and take argmin of them as
>> the overall confidence of the decode. (+, of course, because in a
>> perceptron we're summing feature weights, not multiplying
>> probabilities.)
>>
>>
>
Re: Confidence estimation in a beam decoder
Posted by Ted Dunning <te...@gmail.com>.
Benson,
Are you using techniques related to this:
http://www.it.usyd.edu.au/~james/pubs/pdf/dlp07perc.pdf ?
On Sat, Feb 13, 2010 at 9:38 AM, Benson Margulies <bi...@gmail.com>wrote:
> Folks,
>
> Here's one of my occasional questions in which I am, in essence,
> bartering my code wrangling efforts for expertise on hard stuff.
>
> Consider a sequence problem addressed with a perceptron model with an
> ordinary Viterbi decoder. There's a standard confidence estimation
> technique borrowed from HMMs: calculate gamma = alpha + beta for each
> state, take the difference of the gammas for the best and second best
> hypothesis for each column of the trellis, and take argmin of them as
> the overall confidence of the decode. (+, of course, because in a
> perceptron we're summing feature weights, not multiplying
> probabilities.)
>
>
Re: Confidence estimation in a beam decoder
Posted by Ted Dunning <te...@gmail.com>.
On Sat, Feb 13, 2010 at 9:38 AM, Benson Margulies <bi...@gmail.com>wrote:
> This has been observed by better minds than mine to yield a confidence
> estimation that is useful in doing active learning for training data
> selection.
>
I haven't used this technique and have only occasionally been able to use
active learning outside of the recommendations world. I am not quite sure,
by the way, exactly what you mean by alpha and beta. There is pretty
variable notation for the Viterbi algorithm, so this isn't all that
surprising.
Regardless of that and assuming that this is a good heuristic for active
learning, have you applied your scatterplot to these confidence levels
versus accuracy? Does that show you the relationship that you desire.
I should point out that the goal of active learning is to select training
examples that would have a large impact on the current model or space of
model hypotheses. As such, it is common, especially with perceptron like
algorithms like ANN's and SVM's to select examples that are near the
decision margin. This corresponds pretty well to the desired behavior.
There is nothing, however, that says that these examples will necessarily be
ones for which the model is more or less accurate. These are simply examples
whose actual target value have a large potential for influencing the model.
My own preference for a case like yours is to scan examples to find one
where knowing the true value of the target variable would have the largest
impact for an on-line learning algorithm. That may not be feasible, but I
would guess that their are on-line approximations for whatever learning
algorithm you are using given that you have perceptrons scattered about. To
compute sensitivity, I would simply assume that different candidates in the
beam are the correct result and see which example has the most action as a
result of these assumptions. Your current heuristic seems to be doing this
indirectly by including a probability of correctness measure and omitting
the gradient term but since you don't seem to have a viable probability of
correctness, maybe using the gradient will do. Since gradient of the model
parameters relative to a single target value is usually largest at the
margin, this may turn out to be nearly the same as your original desired
heuristic.
Wish I could help more, but I don't have any direct experience with the
stuff you are working on!