You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@mahout.apache.org by Drew Farris <dr...@gmail.com> on 2010/01/14 23:01:15 UTC
Collocation clarification
I have a question about precisely the numbers that are plugged into the
Log-likliehood ratio are calculated in the context of the collocation
discovery task, specifically whether the position of the term in the ngram
should be taken into account when generating these counts.
Starting with the basic table presented by Ted:
k11 = A and B occuring together
k12 = A occuring without B
k21 = B occuring without A
k22 = Neither A nor B occuring.
In the context of collocation discovery, A and B refer to parts of
ngrams. Given the simple string 'best times worst times', we have the 3
bigrams:
best times
times worst
worst times
In the case of the ngram 'best times', A = 'best' and B = 'times'. Clearly
best appears in only one case, but in the context of 'best times' is
'times' considered to appear 2 or 3 times? The same question could be asked
about the term worst, which either appears once or twice in either case.
In other words, should the numbers plugged into the LLR calculation for
collocations be based on the subgram position?
Drew
Re: Collocation clarification
Posted by Drew Farris <dr...@gmail.com>.
Thanks for the detailed explanation Ted.
On Jan 14, 2010 5:50 PM, "Ted Dunning" <te...@gmail.com> wrote:
As you say, there are three n-grams. the words best, times and worst each
appear once at the beginning of an n-gram (total = 3). The words times and
worst appear at the end of a bigram twice and once respectively (total =
3). The occurrences of times at the beginning and at the end of bigrams are
separate cases and should not be confused.
Also, for the record, it is common to augment the corpus with beginning and
ending symbols. Often these are virtually added between sentences. In your
example, this would give us two more bigrams: <start> best and times <end>.
These extra bigrams allow us, for instance, to note that the word "the"
commonly starts an English sentence, but rarely ends one.
For testing the "best times" bigram, the counts would be:
k11 = 1 (best times)
k12 = 0 (best NOT times)
k21 = 1 (NOT best times)
k22 = 1 (NOT best NOT times)
Note that k** = k11+k12+k21+k22 = 3 (total number of bigrams) and k1* = k11
+ k12 = 1 (number of times best occurred in bigram) and k*1 = k11 + k21 = 2
(number of times "times" occurred at end of bigram).
On Thu, Jan 14, 2010 at 2:01 PM, Drew Farris <dr...@gmail.com> wrote:
> I have a question ab...
--
Ted Dunning, CTO
DeepDyve
Re: Collocation clarification
Posted by Ted Dunning <te...@gmail.com>.
Yes. It can. And they tested that. Very nice paper.
On Sat, Jan 16, 2010 at 5:42 AM, Benson Margulies <bi...@gmail.com>wrote:
> I haven't read the paper, but I bet you a nickel that the unsupervised
> thing works can consume an initial set.
>
--
Ted Dunning, CTO
DeepDyve
Re: Collocation clarification
Posted by Benson Margulies <bi...@gmail.com>.
I haven't read the paper, but I bet you a nickel that the unsupervised
thing works can consume an initial set.
On Fri, Jan 15, 2010 at 10:26 PM, Ted Dunning <te...@gmail.com> wrote:
> One of their points was that the set of abbreviations is productive and
> using a static set is sub-optimal.
>
> Whether we need those last few percent is a matter of discussion, I would
> say.
>
> On Fri, Jan 15, 2010 at 6:41 PM, Benson Margulies <bi...@gmail.com>wrote:
>
>> It's not very hard to collect the abbreviations. It may be less work
>> than coding what's in the paper.
>>
>> On Fri, Jan 15, 2010 at 9:37 PM, Ted Dunning <te...@gmail.com>
>> wrote:
>> > The exceptions are a list of abbreviations that have a terminal full
>> stop,
>> > but which are customarily terminated by a capitalized word which is not
>> the
>> > start of a new sentence.
>> >
>> > It looks to me like machine learning has come a long way in this regard.
>> > This is the best paper on the subject that I have seen in a quick search.
>> >
>> > Unsupervised Multilingual Sentence Boundary Detection
>> > <http://www.linguistics.ruhr-uni-bochum.de/%7Estrunk/ks2005FINAL.pdf> by
>> > Kiss and Strunk.
>> >
>> > It doesn't require any lexical resources and can improve performance on
>> the
>> > fly by adapting to the language that it is working against.
>> >
>> > The fundamental insight is that abbreviations are situations where a stem
>> is
>> > very commonly followed by a full stop and a sentence start marker is
>> > something that is very commonly preceded by a full stop or other sentence
>> > marker. From these and a few other intuitions, they build a system that
>> is
>> > pretty darned accurate. One major component of its accuracy is due to
>> the
>> > ability to adapt on the fly to the corpus in use.
>> >
>> > A deficiency in our use case would be the requirement for training text,
>> but
>> > that could be solved with a few moderate sized resources that are the
>> result
>> > of training on reference texts for different languages.
>> >
>> > On Fri, Jan 15, 2010 at 2:49 PM, Drew Farris <dr...@gmail.com>
>> wrote:
>> >
>> >> I've found abbrevs, various identifiers etc are sort of a typical case
>> >> where these things fall flat. I'll see how it performs viz writing
>> >> something from scratch and see what I can come up with.
>> >>
>> >> > Right, although just slightly ironic that we are using a rule-based
>> >> system for a machine learning project.
>> >>
>> >> Heh, indeed, but it seems entirely appropriate in this case. Of
>> >> course, now I need to go read about statistical approaches to sentence
>> >> boundary detection.
>> >>
>> >
>> >
>> >
>> > --
>> > Ted Dunning, CTO
>> > DeepDyve
>> >
>>
>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
>
Re: Collocation clarification
Posted by Ted Dunning <te...@gmail.com>.
One of their points was that the set of abbreviations is productive and
using a static set is sub-optimal.
Whether we need those last few percent is a matter of discussion, I would
say.
On Fri, Jan 15, 2010 at 6:41 PM, Benson Margulies <bi...@gmail.com>wrote:
> It's not very hard to collect the abbreviations. It may be less work
> than coding what's in the paper.
>
> On Fri, Jan 15, 2010 at 9:37 PM, Ted Dunning <te...@gmail.com>
> wrote:
> > The exceptions are a list of abbreviations that have a terminal full
> stop,
> > but which are customarily terminated by a capitalized word which is not
> the
> > start of a new sentence.
> >
> > It looks to me like machine learning has come a long way in this regard.
> > This is the best paper on the subject that I have seen in a quick search.
> >
> > Unsupervised Multilingual Sentence Boundary Detection
> > <http://www.linguistics.ruhr-uni-bochum.de/%7Estrunk/ks2005FINAL.pdf> by
> > Kiss and Strunk.
> >
> > It doesn't require any lexical resources and can improve performance on
> the
> > fly by adapting to the language that it is working against.
> >
> > The fundamental insight is that abbreviations are situations where a stem
> is
> > very commonly followed by a full stop and a sentence start marker is
> > something that is very commonly preceded by a full stop or other sentence
> > marker. From these and a few other intuitions, they build a system that
> is
> > pretty darned accurate. One major component of its accuracy is due to
> the
> > ability to adapt on the fly to the corpus in use.
> >
> > A deficiency in our use case would be the requirement for training text,
> but
> > that could be solved with a few moderate sized resources that are the
> result
> > of training on reference texts for different languages.
> >
> > On Fri, Jan 15, 2010 at 2:49 PM, Drew Farris <dr...@gmail.com>
> wrote:
> >
> >> I've found abbrevs, various identifiers etc are sort of a typical case
> >> where these things fall flat. I'll see how it performs viz writing
> >> something from scratch and see what I can come up with.
> >>
> >> > Right, although just slightly ironic that we are using a rule-based
> >> system for a machine learning project.
> >>
> >> Heh, indeed, but it seems entirely appropriate in this case. Of
> >> course, now I need to go read about statistical approaches to sentence
> >> boundary detection.
> >>
> >
> >
> >
> > --
> > Ted Dunning, CTO
> > DeepDyve
> >
>
--
Ted Dunning, CTO
DeepDyve
Re: Collocation clarification
Posted by Benson Margulies <bi...@gmail.com>.
It's not very hard to collect the abbreviations. It may be less work
than coding what's in the paper.
On Fri, Jan 15, 2010 at 9:37 PM, Ted Dunning <te...@gmail.com> wrote:
> The exceptions are a list of abbreviations that have a terminal full stop,
> but which are customarily terminated by a capitalized word which is not the
> start of a new sentence.
>
> It looks to me like machine learning has come a long way in this regard.
> This is the best paper on the subject that I have seen in a quick search.
>
> Unsupervised Multilingual Sentence Boundary Detection
> <http://www.linguistics.ruhr-uni-bochum.de/%7Estrunk/ks2005FINAL.pdf> by
> Kiss and Strunk.
>
> It doesn't require any lexical resources and can improve performance on the
> fly by adapting to the language that it is working against.
>
> The fundamental insight is that abbreviations are situations where a stem is
> very commonly followed by a full stop and a sentence start marker is
> something that is very commonly preceded by a full stop or other sentence
> marker. From these and a few other intuitions, they build a system that is
> pretty darned accurate. One major component of its accuracy is due to the
> ability to adapt on the fly to the corpus in use.
>
> A deficiency in our use case would be the requirement for training text, but
> that could be solved with a few moderate sized resources that are the result
> of training on reference texts for different languages.
>
> On Fri, Jan 15, 2010 at 2:49 PM, Drew Farris <dr...@gmail.com> wrote:
>
>> I've found abbrevs, various identifiers etc are sort of a typical case
>> where these things fall flat. I'll see how it performs viz writing
>> something from scratch and see what I can come up with.
>>
>> > Right, although just slightly ironic that we are using a rule-based
>> system for a machine learning project.
>>
>> Heh, indeed, but it seems entirely appropriate in this case. Of
>> course, now I need to go read about statistical approaches to sentence
>> boundary detection.
>>
>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
>
Re: Collocation clarification
Posted by Ted Dunning <te...@gmail.com>.
The exceptions are a list of abbreviations that have a terminal full stop,
but which are customarily terminated by a capitalized word which is not the
start of a new sentence.
It looks to me like machine learning has come a long way in this regard.
This is the best paper on the subject that I have seen in a quick search.
Unsupervised Multilingual Sentence Boundary Detection
<http://www.linguistics.ruhr-uni-bochum.de/%7Estrunk/ks2005FINAL.pdf> by
Kiss and Strunk.
It doesn't require any lexical resources and can improve performance on the
fly by adapting to the language that it is working against.
The fundamental insight is that abbreviations are situations where a stem is
very commonly followed by a full stop and a sentence start marker is
something that is very commonly preceded by a full stop or other sentence
marker. From these and a few other intuitions, they build a system that is
pretty darned accurate. One major component of its accuracy is due to the
ability to adapt on the fly to the corpus in use.
A deficiency in our use case would be the requirement for training text, but
that could be solved with a few moderate sized resources that are the result
of training on reference texts for different languages.
On Fri, Jan 15, 2010 at 2:49 PM, Drew Farris <dr...@gmail.com> wrote:
> I've found abbrevs, various identifiers etc are sort of a typical case
> where these things fall flat. I'll see how it performs viz writing
> something from scratch and see what I can come up with.
>
> > Right, although just slightly ironic that we are using a rule-based
> system for a machine learning project.
>
> Heh, indeed, but it seems entirely appropriate in this case. Of
> course, now I need to go read about statistical approaches to sentence
> boundary detection.
>
--
Ted Dunning, CTO
DeepDyve
Re: Collocation clarification
Posted by Drew Farris <dr...@gmail.com>.
On Fri, Jan 15, 2010 at 10:00 AM, Grant Ingersoll <gs...@apache.org> wrote:
>
> Yeah, I think it makes sense to have a SentenceTokenFilter (as well as ParagraphTokenFilter). In fact, this would be a welcome contribution to Lucene as a new package under the Analyzers in a "o.a.l.analysis.boundary" package (to include other boundary detection techniques, such as paragraph, etc.) Define a common set of constants that indicate the boundary and then we can have different implementations. If you really wanted to go nuts, you could create a SpanBoundaryQuery classes that took in other clauses along w/ the boundary token and did a SpanNearQuery within boundaries. Of course, I don't want to distract you from contributing to Mahout, so...
Ok, thanks for the pointer and roughing out an approach. I'll look
into a SentenceTokenFilter and see where that takes me.
>>
>> Any idea what sort of edge cases I need to look for when using BreakIterator?
>
> Buy the book :-)... Just kidding, it doesn't handle abbreviations very well, is the first thing that jumps to mind. I seem to recall needing less than 10 or so rules to do a pretty decent job. Never did formal testing on it, though.
Ok, OK :-)
I've found abbrevs, various identifiers etc are sort of a typical case
where these things fall flat. I'll see how it performs viz writing
something from scratch and see what I can come up with.
> Right, although just slightly ironic that we are using a rule-based system for a machine learning project.
Heh, indeed, but it seems entirely appropriate in this case. Of
course, now I need to go read about statistical approaches to sentence
boundary detection.
Drew
Re: Collocation clarification
Posted by Grant Ingersoll <gs...@apache.org>.
On Jan 15, 2010, at 9:48 AM, Drew Farris wrote:
> On Fri, Jan 15, 2010 at 9:30 AM, Grant Ingersoll <gs...@apache.org> wrote:
>>
>> Yeah, I've even found using Java's BreakIterator (there's one for Sentences and it is supposedly Locale aware) plus some simple edge case modifications does quite well. I've got an implementation/demo in Taming Text, I think, but may also have one laying around somewhere else.
>>
>> Only trick thing is you have to buffer the tokens in Lucene, which is slightly annoying with the new incrementToken API, but not horrible. Then, once you find the break, just output a > > special token. Maybe also consider increasing the position increment.
>
> In this case it sounds like it might be useful to do sentence chinking
> prior to even getting the Analyzer involved. The BreakIterator returns
> offsets which can be used in a substring call to create a StringReader
> which then gets passed to the Analyzer. substring operates on the
> char[] of the original string, so the only overhead would be the
> allocation of the StringReaders.
>
> E.g, something like
>
> while (breakIterator.next()) {
> StringReader r = new
> StringReader(input.substring(breakIterator.start(),
> breakIterator.end());
> a.tokenStream(null, r);
> [..generate and collect ngrams here..]
> r.close()
> }
>
> On second thought however it would probably be more convenient if I
> packaged the sentence boundary detection into the analyzer itself so
> that the behavior can be easily changed by the end user. This would
> include the way in which I use the ShingleFilter to generate n-grams
> which is currently external to the Analyzer that gets plugged in.
Yeah, I think it makes sense to have a SentenceTokenFilter (as well as ParagraphTokenFilter). In fact, this would be a welcome contribution to Lucene as a new package under the Analyzers in a "o.a.l.analysis.boundary" package (to include other boundary detection techniques, such as paragraph, etc.) Define a common set of constants that indicate the boundary and then we can have different implementations. If you really wanted to go nuts, you could create a SpanBoundaryQuery classes that took in other clauses along w/ the boundary token and did a SpanNearQuery within boundaries. Of course, I don't want to distract you from contributing to Mahout, so...
>
> Any idea what sort of edge cases I need to look for when using BreakIterator?
Buy the book :-)... Just kidding, it doesn't handle abbreviations very well, is the first thing that jumps to mind. I seem to recall needing less than 10 or so rules to do a pretty decent job. Never did formal testing on it, though.
>
> At this point, I'm thinking it is probably worth trying to get
> something self-contained implemented for this relatively
> straightforward need as opposed to pulling in something like OpenNLP
> or Gate.
Right, although just slightly ironic that we are using a rule-based system for a machine learning project.
-Grant
Re: Collocation clarification
Posted by Drew Farris <dr...@gmail.com>.
On Fri, Jan 15, 2010 at 9:30 AM, Grant Ingersoll <gs...@apache.org> wrote:
>
> Yeah, I've even found using Java's BreakIterator (there's one for Sentences and it is supposedly Locale aware) plus some simple edge case modifications does quite well. I've got an implementation/demo in Taming Text, I think, but may also have one laying around somewhere else.
>
> Only trick thing is you have to buffer the tokens in Lucene, which is slightly annoying with the new incrementToken API, but not horrible. Then, once you find the break, just output a > > special token. Maybe also consider increasing the position increment.
In this case it sounds like it might be useful to do sentence chinking
prior to even getting the Analyzer involved. The BreakIterator returns
offsets which can be used in a substring call to create a StringReader
which then gets passed to the Analyzer. substring operates on the
char[] of the original string, so the only overhead would be the
allocation of the StringReaders.
E.g, something like
while (breakIterator.next()) {
StringReader r = new
StringReader(input.substring(breakIterator.start(),
breakIterator.end());
a.tokenStream(null, r);
[..generate and collect ngrams here..]
r.close()
}
On second thought however it would probably be more convenient if I
packaged the sentence boundary detection into the analyzer itself so
that the behavior can be easily changed by the end user. This would
include the way in which I use the ShingleFilter to generate n-grams
which is currently external to the Analyzer that gets plugged in.
Any idea what sort of edge cases I need to look for when using BreakIterator?
At this point, I'm thinking it is probably worth trying to get
something self-contained implemented for this relatively
straightforward need as opposed to pulling in something like OpenNLP
or Gate.
Drew
Re: Collocation clarification
Posted by Grant Ingersoll <gs...@apache.org>.
On Jan 14, 2010, at 9:45 PM, Ted Dunning wrote:
> Pretty OK sentence boundary detection in English can be done by finding full
> stops, ?, ! and excess new-lines and then qualifying the potential breaks.
Yeah, I've even found using Java's BreakIterator (there's one for Sentences and it is supposedly Locale aware) plus some simple edge case modifications does quite well. I've got an implementation/demo in Taming Text, I think, but may also have one laying around somewhere else.
Only trick thing is you have to buffer the tokens in Lucene, which is slightly annoying with the new incrementToken API, but not horrible. Then, once you find the break, just output a special token. Maybe also consider increasing the position increment.
Otherwise, OpenNLP has one too which is pretty easy to use, but requires a chunk of memory for the model.
>
> For the full stops, you then have check the preceding and following token.
> If you have mixed case text, the following token can eliminate some breaks
> by not being capitalized. The preceding token eliminates the break by being
> one of about two dozen special cases.
>
> There are a few other cases, but that is 90% of the game.
>
> Heavy weight framework not needed.
>
> On Thu, Jan 14, 2010 at 6:33 PM, Otis Gospodnetic <
> otis_gospodnetic@yahoo.com> wrote:
>
>> Good memory, Drew! No, nothing came out of it. OpenNLP and GATE have
>> sentence boundary detection.
>>
>> Otis
>> --
>> Sematext -- http://sematext.com/ -- Solr - Lucene - Nutch
>>
>>
>>
>> ----- Original Message ----
>>> From: Drew Farris <dr...@gmail.com>
>>> To: mahout-user@lucene.apache.org
>>> Sent: Thu, January 14, 2010 8:58:53 PM
>>> Subject: Re: Collocation clarification
>>>
>>> To follow up on the point about the and units. It would not be
>>> very difficult to add, especially if there is something out there that
>>> already detects them.
>>>
>>> Does anyone know of a component in the Lucene ecosystem that can detect
>>> sentence boundaries? It would make sense if there was something in the
>>> Analyzer family that emits tokens with an end of sentence type. I saw a
>> post
>>> from Otis on the java-dev list back in November regarding this issue --
>> does
>>> come out of it? (I really like the new Lucene Analyzer API)
>>>
>>> thanks for explaining this again Ted, I suspected it was the proper way
>> to
>>> do the calculation so the implementation in MAHOUT-242 currently works
>> this
>>> way. It is very nice to have confirmation that I grokked the idea
>> properly.
>>>
>>> Drew
>>>
>>> On Thu, Jan 14, 2010 at 5:49 PM, Ted Dunning wrote:
>>>
>>>> As you say, there are three n-grams. the words best, times and worst
>> each
>>>> appear once at the beginning of an n-gram (total = 3). The words times
>> and
>>>> worst appear at the end of a bigram twice and once respectively (total
>> =
>>>> 3). The occurrences of times at the beginning and at the end of
>> bigrams
>>>> are
>>>> separate cases and should not be confused.
>>>>
>>>> Also, for the record, it is common to augment the corpus with beginning
>> and
>>>> ending symbols. Often these are virtually added between sentences. In
>>>> your
>>>> example, this would give us two more bigrams: best and times .
>>>> These extra bigrams allow us, for instance, to note that the word "the"
>>>> commonly starts an English sentence, but rarely ends one.
>>>>
>>>> For testing the "best times" bigram, the counts would be:
>>>>
>>>> k11 = 1 (best times)
>>>> k12 = 0 (best NOT times)
>>>> k21 = 1 (NOT best times)
>>>> k22 = 1 (NOT best NOT times)
>>>>
>>>> Note that k** = k11+k12+k21+k22 = 3 (total number of bigrams) and k1* =
>> k11
>>>> + k12 = 1 (number of times best occurred in bigram) and k*1 = k11 + k21
>> = 2
>>>> (number of times "times" occurred at end of bigram).
>>>>
>>>> On Thu, Jan 14, 2010 at 2:01 PM, Drew Farris
>>>> wrote:
>>>>
>>>>> I have a question about precisely the numbers that are plugged into
>> the
>>>>> Log-likliehood ratio are calculated in the context of the collocation
>>>>> discovery task, specifically whether the position of the term in the
>>>> ngram
>>>>> should be taken into account when generating these counts.
>>>>>
>>>>> Starting with the basic table presented by Ted:
>>>>>
>>>>> k11 = A and B occuring together
>>>>> k12 = A occuring without B
>>>>> k21 = B occuring without A
>>>>> k22 = Neither A nor B occuring.
>>>>>
>>>>> In the context of collocation discovery, A and B refer to parts of
>>>>> ngrams. Given the simple string 'best times worst times', we have the
>> 3
>>>>> bigrams:
>>>>>
>>>>> best times
>>>>> times worst
>>>>> worst times
>>>>>
>>>>> In the case of the ngram 'best times', A = 'best' and B = 'times'.
>>>> Clearly
>>>>> best appears in only one case, but in the context of 'best times' is
>>>>> 'times' considered to appear 2 or 3 times? The same question could be
>>>> asked
>>>>> about the term worst, which either appears once or twice in either
>> case.
>>>>>
>>>>> In other words, should the numbers plugged into the LLR calculation
>> for
>>>>> collocations be based on the subgram position?
>>>>>
>>>>> Drew
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Ted Dunning, CTO
>>>> DeepDyve
>>>>
>>
>>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
--------------------------
Grant Ingersoll
http://www.lucidimagination.com/
Search the Lucene ecosystem using Solr/Lucene: http://www.lucidimagination.com/search
Re: Collocation clarification
Posted by Ted Dunning <te...@gmail.com>.
Pretty OK sentence boundary detection in English can be done by finding full
stops, ?, ! and excess new-lines and then qualifying the potential breaks.
For the full stops, you then have check the preceding and following token.
If you have mixed case text, the following token can eliminate some breaks
by not being capitalized. The preceding token eliminates the break by being
one of about two dozen special cases.
There are a few other cases, but that is 90% of the game.
Heavy weight framework not needed.
On Thu, Jan 14, 2010 at 6:33 PM, Otis Gospodnetic <
otis_gospodnetic@yahoo.com> wrote:
> Good memory, Drew! No, nothing came out of it. OpenNLP and GATE have
> sentence boundary detection.
>
> Otis
> --
> Sematext -- http://sematext.com/ -- Solr - Lucene - Nutch
>
>
>
> ----- Original Message ----
> > From: Drew Farris <dr...@gmail.com>
> > To: mahout-user@lucene.apache.org
> > Sent: Thu, January 14, 2010 8:58:53 PM
> > Subject: Re: Collocation clarification
> >
> > To follow up on the point about the and units. It would not be
> > very difficult to add, especially if there is something out there that
> > already detects them.
> >
> > Does anyone know of a component in the Lucene ecosystem that can detect
> > sentence boundaries? It would make sense if there was something in the
> > Analyzer family that emits tokens with an end of sentence type. I saw a
> post
> > from Otis on the java-dev list back in November regarding this issue --
> does
> > come out of it? (I really like the new Lucene Analyzer API)
> >
> > thanks for explaining this again Ted, I suspected it was the proper way
> to
> > do the calculation so the implementation in MAHOUT-242 currently works
> this
> > way. It is very nice to have confirmation that I grokked the idea
> properly.
> >
> > Drew
> >
> > On Thu, Jan 14, 2010 at 5:49 PM, Ted Dunning wrote:
> >
> > > As you say, there are three n-grams. the words best, times and worst
> each
> > > appear once at the beginning of an n-gram (total = 3). The words times
> and
> > > worst appear at the end of a bigram twice and once respectively (total
> =
> > > 3). The occurrences of times at the beginning and at the end of
> bigrams
> > > are
> > > separate cases and should not be confused.
> > >
> > > Also, for the record, it is common to augment the corpus with beginning
> and
> > > ending symbols. Often these are virtually added between sentences. In
> > > your
> > > example, this would give us two more bigrams: best and times .
> > > These extra bigrams allow us, for instance, to note that the word "the"
> > > commonly starts an English sentence, but rarely ends one.
> > >
> > > For testing the "best times" bigram, the counts would be:
> > >
> > > k11 = 1 (best times)
> > > k12 = 0 (best NOT times)
> > > k21 = 1 (NOT best times)
> > > k22 = 1 (NOT best NOT times)
> > >
> > > Note that k** = k11+k12+k21+k22 = 3 (total number of bigrams) and k1* =
> k11
> > > + k12 = 1 (number of times best occurred in bigram) and k*1 = k11 + k21
> = 2
> > > (number of times "times" occurred at end of bigram).
> > >
> > > On Thu, Jan 14, 2010 at 2:01 PM, Drew Farris
> > > wrote:
> > >
> > > > I have a question about precisely the numbers that are plugged into
> the
> > > > Log-likliehood ratio are calculated in the context of the collocation
> > > > discovery task, specifically whether the position of the term in the
> > > ngram
> > > > should be taken into account when generating these counts.
> > > >
> > > > Starting with the basic table presented by Ted:
> > > >
> > > > k11 = A and B occuring together
> > > > k12 = A occuring without B
> > > > k21 = B occuring without A
> > > > k22 = Neither A nor B occuring.
> > > >
> > > > In the context of collocation discovery, A and B refer to parts of
> > > > ngrams. Given the simple string 'best times worst times', we have the
> 3
> > > > bigrams:
> > > >
> > > > best times
> > > > times worst
> > > > worst times
> > > >
> > > > In the case of the ngram 'best times', A = 'best' and B = 'times'.
> > > Clearly
> > > > best appears in only one case, but in the context of 'best times' is
> > > > 'times' considered to appear 2 or 3 times? The same question could be
> > > asked
> > > > about the term worst, which either appears once or twice in either
> case.
> > > >
> > > > In other words, should the numbers plugged into the LLR calculation
> for
> > > > collocations be based on the subgram position?
> > > >
> > > > Drew
> > > >
> > >
> > >
> > >
> > > --
> > > Ted Dunning, CTO
> > > DeepDyve
> > >
>
>
--
Ted Dunning, CTO
DeepDyve
Re: Collocation clarification
Posted by Otis Gospodnetic <ot...@yahoo.com>.
Good memory, Drew! No, nothing came out of it. OpenNLP and GATE have sentence boundary detection.
Otis
--
Sematext -- http://sematext.com/ -- Solr - Lucene - Nutch
----- Original Message ----
> From: Drew Farris <dr...@gmail.com>
> To: mahout-user@lucene.apache.org
> Sent: Thu, January 14, 2010 8:58:53 PM
> Subject: Re: Collocation clarification
>
> To follow up on the point about the and units. It would not be
> very difficult to add, especially if there is something out there that
> already detects them.
>
> Does anyone know of a component in the Lucene ecosystem that can detect
> sentence boundaries? It would make sense if there was something in the
> Analyzer family that emits tokens with an end of sentence type. I saw a post
> from Otis on the java-dev list back in November regarding this issue -- does
> come out of it? (I really like the new Lucene Analyzer API)
>
> thanks for explaining this again Ted, I suspected it was the proper way to
> do the calculation so the implementation in MAHOUT-242 currently works this
> way. It is very nice to have confirmation that I grokked the idea properly.
>
> Drew
>
> On Thu, Jan 14, 2010 at 5:49 PM, Ted Dunning wrote:
>
> > As you say, there are three n-grams. the words best, times and worst each
> > appear once at the beginning of an n-gram (total = 3). The words times and
> > worst appear at the end of a bigram twice and once respectively (total =
> > 3). The occurrences of times at the beginning and at the end of bigrams
> > are
> > separate cases and should not be confused.
> >
> > Also, for the record, it is common to augment the corpus with beginning and
> > ending symbols. Often these are virtually added between sentences. In
> > your
> > example, this would give us two more bigrams: best and times .
> > These extra bigrams allow us, for instance, to note that the word "the"
> > commonly starts an English sentence, but rarely ends one.
> >
> > For testing the "best times" bigram, the counts would be:
> >
> > k11 = 1 (best times)
> > k12 = 0 (best NOT times)
> > k21 = 1 (NOT best times)
> > k22 = 1 (NOT best NOT times)
> >
> > Note that k** = k11+k12+k21+k22 = 3 (total number of bigrams) and k1* = k11
> > + k12 = 1 (number of times best occurred in bigram) and k*1 = k11 + k21 = 2
> > (number of times "times" occurred at end of bigram).
> >
> > On Thu, Jan 14, 2010 at 2:01 PM, Drew Farris
> > wrote:
> >
> > > I have a question about precisely the numbers that are plugged into the
> > > Log-likliehood ratio are calculated in the context of the collocation
> > > discovery task, specifically whether the position of the term in the
> > ngram
> > > should be taken into account when generating these counts.
> > >
> > > Starting with the basic table presented by Ted:
> > >
> > > k11 = A and B occuring together
> > > k12 = A occuring without B
> > > k21 = B occuring without A
> > > k22 = Neither A nor B occuring.
> > >
> > > In the context of collocation discovery, A and B refer to parts of
> > > ngrams. Given the simple string 'best times worst times', we have the 3
> > > bigrams:
> > >
> > > best times
> > > times worst
> > > worst times
> > >
> > > In the case of the ngram 'best times', A = 'best' and B = 'times'.
> > Clearly
> > > best appears in only one case, but in the context of 'best times' is
> > > 'times' considered to appear 2 or 3 times? The same question could be
> > asked
> > > about the term worst, which either appears once or twice in either case.
> > >
> > > In other words, should the numbers plugged into the LLR calculation for
> > > collocations be based on the subgram position?
> > >
> > > Drew
> > >
> >
> >
> >
> > --
> > Ted Dunning, CTO
> > DeepDyve
> >
Re: Collocation clarification
Posted by Drew Farris <dr...@gmail.com>.
To follow up on the point about the <start> and <end> units. It would not be
very difficult to add, especially if there is something out there that
already detects them.
Does anyone know of a component in the Lucene ecosystem that can detect
sentence boundaries? It would make sense if there was something in the
Analyzer family that emits tokens with an end of sentence type. I saw a post
from Otis on the java-dev list back in November regarding this issue -- does
come out of it? (I really like the new Lucene Analyzer API)
thanks for explaining this again Ted, I suspected it was the proper way to
do the calculation so the implementation in MAHOUT-242 currently works this
way. It is very nice to have confirmation that I grokked the idea properly.
Drew
On Thu, Jan 14, 2010 at 5:49 PM, Ted Dunning <te...@gmail.com> wrote:
> As you say, there are three n-grams. the words best, times and worst each
> appear once at the beginning of an n-gram (total = 3). The words times and
> worst appear at the end of a bigram twice and once respectively (total =
> 3). The occurrences of times at the beginning and at the end of bigrams
> are
> separate cases and should not be confused.
>
> Also, for the record, it is common to augment the corpus with beginning and
> ending symbols. Often these are virtually added between sentences. In
> your
> example, this would give us two more bigrams: <start> best and times <end>.
> These extra bigrams allow us, for instance, to note that the word "the"
> commonly starts an English sentence, but rarely ends one.
>
> For testing the "best times" bigram, the counts would be:
>
> k11 = 1 (best times)
> k12 = 0 (best NOT times)
> k21 = 1 (NOT best times)
> k22 = 1 (NOT best NOT times)
>
> Note that k** = k11+k12+k21+k22 = 3 (total number of bigrams) and k1* = k11
> + k12 = 1 (number of times best occurred in bigram) and k*1 = k11 + k21 = 2
> (number of times "times" occurred at end of bigram).
>
> On Thu, Jan 14, 2010 at 2:01 PM, Drew Farris <dr...@gmail.com>
> wrote:
>
> > I have a question about precisely the numbers that are plugged into the
> > Log-likliehood ratio are calculated in the context of the collocation
> > discovery task, specifically whether the position of the term in the
> ngram
> > should be taken into account when generating these counts.
> >
> > Starting with the basic table presented by Ted:
> >
> > k11 = A and B occuring together
> > k12 = A occuring without B
> > k21 = B occuring without A
> > k22 = Neither A nor B occuring.
> >
> > In the context of collocation discovery, A and B refer to parts of
> > ngrams. Given the simple string 'best times worst times', we have the 3
> > bigrams:
> >
> > best times
> > times worst
> > worst times
> >
> > In the case of the ngram 'best times', A = 'best' and B = 'times'.
> Clearly
> > best appears in only one case, but in the context of 'best times' is
> > 'times' considered to appear 2 or 3 times? The same question could be
> asked
> > about the term worst, which either appears once or twice in either case.
> >
> > In other words, should the numbers plugged into the LLR calculation for
> > collocations be based on the subgram position?
> >
> > Drew
> >
>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
>
Re: Collocation clarification
Posted by Ted Dunning <te...@gmail.com>.
As you say, there are three n-grams. the words best, times and worst each
appear once at the beginning of an n-gram (total = 3). The words times and
worst appear at the end of a bigram twice and once respectively (total =
3). The occurrences of times at the beginning and at the end of bigrams are
separate cases and should not be confused.
Also, for the record, it is common to augment the corpus with beginning and
ending symbols. Often these are virtually added between sentences. In your
example, this would give us two more bigrams: <start> best and times <end>.
These extra bigrams allow us, for instance, to note that the word "the"
commonly starts an English sentence, but rarely ends one.
For testing the "best times" bigram, the counts would be:
k11 = 1 (best times)
k12 = 0 (best NOT times)
k21 = 1 (NOT best times)
k22 = 1 (NOT best NOT times)
Note that k** = k11+k12+k21+k22 = 3 (total number of bigrams) and k1* = k11
+ k12 = 1 (number of times best occurred in bigram) and k*1 = k11 + k21 = 2
(number of times "times" occurred at end of bigram).
On Thu, Jan 14, 2010 at 2:01 PM, Drew Farris <dr...@gmail.com> wrote:
> I have a question about precisely the numbers that are plugged into the
> Log-likliehood ratio are calculated in the context of the collocation
> discovery task, specifically whether the position of the term in the ngram
> should be taken into account when generating these counts.
>
> Starting with the basic table presented by Ted:
>
> k11 = A and B occuring together
> k12 = A occuring without B
> k21 = B occuring without A
> k22 = Neither A nor B occuring.
>
> In the context of collocation discovery, A and B refer to parts of
> ngrams. Given the simple string 'best times worst times', we have the 3
> bigrams:
>
> best times
> times worst
> worst times
>
> In the case of the ngram 'best times', A = 'best' and B = 'times'. Clearly
> best appears in only one case, but in the context of 'best times' is
> 'times' considered to appear 2 or 3 times? The same question could be asked
> about the term worst, which either appears once or twice in either case.
>
> In other words, should the numbers plugged into the LLR calculation for
> collocations be based on the subgram position?
>
> Drew
>
--
Ted Dunning, CTO
DeepDyve