You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Dmitriy Lyubimov <dl...@gmail.com> on 2014/08/07 01:21:50 UTC
co-occurrence paper and code
So, compared to original paper [1], similarity is now hardcoded and always
LLR? Do we have any plans to parameterize that further? Is there any reason
to parameterize it?
Also, reading the paper, i am a bit wondering -- similarity and distance
are functions that usually are moving into different directions (i.e.
cosine similarity and angular distance) but in the paper distance scores
are also considered similarities? How's that?
I suppose in that context LLR is considered a distance (higher scores mean
more `distant` items, co-occurring by chance only)?
[1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
-d
Re: co-occurrence paper and code
Posted by Pat Ferrel <pa...@gmail.com>.
+1 for better-than-absolute-threshold quality metric. Several users of hadoop item similarity have asked for this or expressed difficulty in using the existing absolute threshold. One method Ken Krugler asked for was to toss the lowest LLR items up to some fraction of the total. He wanted to use this to loose the least “quality" while sparsifying the matrix and it was on CF data. I understand that this conflates quality with sparsification but there it is anyway.
On Aug 7, 2014, at 5:41 PM, Ted Dunning <te...@gmail.com> wrote:
Speaking from experience, I think that expressing the threshold as a
confidence has some attraction, but can be a bit of a difficult interface.
For instance, the equivalent of a 5 standard deviation threshold of either
0.9999999 or 0.0000001 (or did I get those right? Can you tell?). In
either case, I think it is nicer to have something on a log scale somehow.
The options to make this easier all center about restating this threshold
around some naturally log-ish scale. Log-odds, log p-value and standard
deviations are all candidates for this. Log odds for 0.9999999 is 16.1 in
natural base or 7 in base 10. For 0.0000001, the log odds are -16.1 or -7.
For the SD scale, it is 5.7 or -5.7.
The problem is that these quantities are well outside the natural range for
percentiles. In normal frequentist analysis, the quantities being played
with are things like p-values of 0.05 or 0.01 or even 0.001. These are
practical for this notation. The much more extreme thresholds required for
recommendations are not so useful in this notation.
On Thu, Aug 7, 2014 at 2:00 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> if exploration and bootstrap are concerns, in my case its saturation is
> achieved by a different methodology. I want this threshold to be, (1) of
> course optional, and (2) be expressed in confidence level, %, just to
> understand the ballpark in each case.
>
> Ok i think i understand the code to convert confidence into LLR threshold
> (and vice versa). Thanks.
>
>
> On Thu, Aug 7, 2014 at 1:38 PM, Ted Dunning <te...@gmail.com> wrote:
>
>> Yes. This is a good thresholding to do.
>>
>> Typically I have done this by simply providing a threshold on the LLR
> score
>> itself. It is convenient to restate the score itself as the signed
> square
>> root of the score since that lets you add information about whether the
>> cooccurrence is more or less common than expected and it puts the scale
>> essentially on the same scale as standard deviations from a normal
>> distribution. On that scale, a cutoff in the range of 5 to 15 is
> commonly
>> used. The fact that 5 standard deviations represents a p-value of about
> 3
>> x 10^-7 is indicative of how stringent this criterion would be if it
> were a
>> frequentist hypothesis test.
>>
>> In practice, I haven't found that the cutoff is that useful. Part of the
>> reason for this is that I would just as soon have some wild-eyed behavior
>> happen with low data situations so that some kind of recommendations
> happen
>> and we can gather more data.
>>
>>
>> I don't see this threshold in our current RowSimilarityJob. There is a
>> threshold, but it is applied to counts on only some similarity classes.
>>
>>
>>
>> On Wed, Aug 6, 2014 at 5:07 PM, Dmitriy Lyubimov <dl...@gmail.com>
>> wrote:
>>
>>> On Wed, Aug 6, 2014 at 5:04 PM, Ted Dunning <te...@gmail.com>
>> wrote:
>>>
>>>> On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com>
>>>> wrote:
>>>>
>>>>>> LLR is a classic test.
>>>>>
>>>>>
>>>>> What i meant here it doesn't produce a p-value. or does it?
>>>>>
>>>>
>>>> It produces an asymptotically chi^2 distributed statistic with
> 1-degree
>>> of
>>>> freedom (for our case of 2x2 contingency tables) which can be reduced
>>>> trivially to a p-value in the standard way.
>>>>
>>>
>>> Great. so that means that we can do h_0 rejection based on a
> %-expressed
>>> level?
>>>
>>
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
Speaking from experience, I think that expressing the threshold as a
confidence has some attraction, but can be a bit of a difficult interface.
For instance, the equivalent of a 5 standard deviation threshold of either
0.9999999 or 0.0000001 (or did I get those right? Can you tell?). In
either case, I think it is nicer to have something on a log scale somehow.
The options to make this easier all center about restating this threshold
around some naturally log-ish scale. Log-odds, log p-value and standard
deviations are all candidates for this. Log odds for 0.9999999 is 16.1 in
natural base or 7 in base 10. For 0.0000001, the log odds are -16.1 or -7.
For the SD scale, it is 5.7 or -5.7.
The problem is that these quantities are well outside the natural range for
percentiles. In normal frequentist analysis, the quantities being played
with are things like p-values of 0.05 or 0.01 or even 0.001. These are
practical for this notation. The much more extreme thresholds required for
recommendations are not so useful in this notation.
On Thu, Aug 7, 2014 at 2:00 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> if exploration and bootstrap are concerns, in my case its saturation is
> achieved by a different methodology. I want this threshold to be, (1) of
> course optional, and (2) be expressed in confidence level, %, just to
> understand the ballpark in each case.
>
> Ok i think i understand the code to convert confidence into LLR threshold
> (and vice versa). Thanks.
>
>
> On Thu, Aug 7, 2014 at 1:38 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > Yes. This is a good thresholding to do.
> >
> > Typically I have done this by simply providing a threshold on the LLR
> score
> > itself. It is convenient to restate the score itself as the signed
> square
> > root of the score since that lets you add information about whether the
> > cooccurrence is more or less common than expected and it puts the scale
> > essentially on the same scale as standard deviations from a normal
> > distribution. On that scale, a cutoff in the range of 5 to 15 is
> commonly
> > used. The fact that 5 standard deviations represents a p-value of about
> 3
> > x 10^-7 is indicative of how stringent this criterion would be if it
> were a
> > frequentist hypothesis test.
> >
> > In practice, I haven't found that the cutoff is that useful. Part of the
> > reason for this is that I would just as soon have some wild-eyed behavior
> > happen with low data situations so that some kind of recommendations
> happen
> > and we can gather more data.
> >
> >
> > I don't see this threshold in our current RowSimilarityJob. There is a
> > threshold, but it is applied to counts on only some similarity classes.
> >
> >
> >
> > On Wed, Aug 6, 2014 at 5:07 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > On Wed, Aug 6, 2014 at 5:04 PM, Ted Dunning <te...@gmail.com>
> > wrote:
> > >
> > > > On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > > > wrote:
> > > >
> > > > > > LLR is a classic test.
> > > > >
> > > > >
> > > > > What i meant here it doesn't produce a p-value. or does it?
> > > > >
> > > >
> > > > It produces an asymptotically chi^2 distributed statistic with
> 1-degree
> > > of
> > > > freedom (for our case of 2x2 contingency tables) which can be reduced
> > > > trivially to a p-value in the standard way.
> > > >
> > >
> > > Great. so that means that we can do h_0 rejection based on a
> %-expressed
> > > level?
> > >
> >
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
if exploration and bootstrap are concerns, in my case its saturation is
achieved by a different methodology. I want this threshold to be, (1) of
course optional, and (2) be expressed in confidence level, %, just to
understand the ballpark in each case.
Ok i think i understand the code to convert confidence into LLR threshold
(and vice versa). Thanks.
On Thu, Aug 7, 2014 at 1:38 PM, Ted Dunning <te...@gmail.com> wrote:
> Yes. This is a good thresholding to do.
>
> Typically I have done this by simply providing a threshold on the LLR score
> itself. It is convenient to restate the score itself as the signed square
> root of the score since that lets you add information about whether the
> cooccurrence is more or less common than expected and it puts the scale
> essentially on the same scale as standard deviations from a normal
> distribution. On that scale, a cutoff in the range of 5 to 15 is commonly
> used. The fact that 5 standard deviations represents a p-value of about 3
> x 10^-7 is indicative of how stringent this criterion would be if it were a
> frequentist hypothesis test.
>
> In practice, I haven't found that the cutoff is that useful. Part of the
> reason for this is that I would just as soon have some wild-eyed behavior
> happen with low data situations so that some kind of recommendations happen
> and we can gather more data.
>
>
> I don't see this threshold in our current RowSimilarityJob. There is a
> threshold, but it is applied to counts on only some similarity classes.
>
>
>
> On Wed, Aug 6, 2014 at 5:07 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > On Wed, Aug 6, 2014 at 5:04 PM, Ted Dunning <te...@gmail.com>
> wrote:
> >
> > > On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > > wrote:
> > >
> > > > > LLR is a classic test.
> > > >
> > > >
> > > > What i meant here it doesn't produce a p-value. or does it?
> > > >
> > >
> > > It produces an asymptotically chi^2 distributed statistic with 1-degree
> > of
> > > freedom (for our case of 2x2 contingency tables) which can be reduced
> > > trivially to a p-value in the standard way.
> > >
> >
> > Great. so that means that we can do h_0 rejection based on a %-expressed
> > level?
> >
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
Yes. This is a good thresholding to do.
Typically I have done this by simply providing a threshold on the LLR score
itself. It is convenient to restate the score itself as the signed square
root of the score since that lets you add information about whether the
cooccurrence is more or less common than expected and it puts the scale
essentially on the same scale as standard deviations from a normal
distribution. On that scale, a cutoff in the range of 5 to 15 is commonly
used. The fact that 5 standard deviations represents a p-value of about 3
x 10^-7 is indicative of how stringent this criterion would be if it were a
frequentist hypothesis test.
In practice, I haven't found that the cutoff is that useful. Part of the
reason for this is that I would just as soon have some wild-eyed behavior
happen with low data situations so that some kind of recommendations happen
and we can gather more data.
I don't see this threshold in our current RowSimilarityJob. There is a
threshold, but it is applied to counts on only some similarity classes.
On Wed, Aug 6, 2014 at 5:07 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> On Wed, Aug 6, 2014 at 5:04 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > > LLR is a classic test.
> > >
> > >
> > > What i meant here it doesn't produce a p-value. or does it?
> > >
> >
> > It produces an asymptotically chi^2 distributed statistic with 1-degree
> of
> > freedom (for our case of 2x2 contingency tables) which can be reduced
> > trivially to a p-value in the standard way.
> >
>
> Great. so that means that we can do h_0 rejection based on a %-expressed
> level?
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
On Thu, Aug 7, 2014 at 11:34 AM, Ted Dunning <te...@gmail.com> wrote:
>
>
> Can you say a bit more about what you are trying to do?
>
Thank you.
I would like to customize co-oc code not to just yank top N scored
co-occurrences, but also make sure that all of them satisfy rejection of
coincidence with a given confidence level (anywhere between say 60% to
99%). I guess it is ok even if it is an asymptotical approximation, since
we in practice will be testing far right in the tail.
In other words, i don't want to bother heaping clear and pre-judged
coincidences.
In applications other than direct co-occurrence, similar decisioning would
be sensible.
> [1] https://dl.dropboxusercontent.com/u/36863361/llr-table.png
> [2] http://www.aclweb.org/anthology/J93-1003
>
>
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
On Wed, Aug 6, 2014 at 5:07 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> On Wed, Aug 6, 2014 at 5:04 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > > LLR is a classic test.
> > >
> > >
> > > What i meant here it doesn't produce a p-value. or does it?
> > >
> >
> > It produces an asymptotically chi^2 distributed statistic with 1-degree
> of
> > freedom (for our case of 2x2 contingency tables) which can be reduced
> > trivially to a p-value in the standard way.
> >
>
> Great. so that means that we can do h_0 rejection based on a %-expressed
> level?
>
Yes. You can use LLR (aka G^2) to do hypothesis testing. But in the
context we are using it, we are effectively doing millions or billions of
repeated comparisons. Frequentist testing is hopeless in such situations
and any p-values that you get will be meaningless (as p-values). Their
only virtue is that they will roughly sort the cases with interesting and
anomalous cases first. The raw score does that as well so that getting the
p-value is just wasted computation.
A classic hypothesis testing framework is also somewhat compromised by the
fact that the LLR is only asymptotically chi^2 distributed. For very small
counts, it is that close to chi^2 distributed, even though it is often
dozens to hundreds of orders of magnitudes more accurate than Pearson's
chi^2 test in such cases.
This table [1] from my original paper [2] on the LLR test shows what I mean:
[image: Inline image 1]
For the data that we typically see, np << 1e-3 so the p-values estimated by
conventional tests are really pretty horrible.
Can you say a bit more about what you are trying to do?
[1] https://dl.dropboxusercontent.com/u/36863361/llr-table.png
[2] http://www.aclweb.org/anthology/J93-1003
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
On Wed, Aug 6, 2014 at 5:04 PM, Ted Dunning <te...@gmail.com> wrote:
> On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > > LLR is a classic test.
> >
> >
> > What i meant here it doesn't produce a p-value. or does it?
> >
>
> It produces an asymptotically chi^2 distributed statistic with 1-degree of
> freedom (for our case of 2x2 contingency tables) which can be reduced
> trivially to a p-value in the standard way.
>
Great. so that means that we can do h_0 rejection based on a %-expressed
level?
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
On Wed, Aug 6, 2014 at 6:01 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> > LLR is a classic test.
>
>
> What i meant here it doesn't produce a p-value. or does it?
>
It produces an asymptotically chi^2 distributed statistic with 1-degree of
freedom (for our case of 2x2 contingency tables) which can be reduced
trivially to a p-value in the standard way.
It is as much a classic test as a t-test, a chi^2 test, an F test or any
other of the gazillion usual suspects.
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
On Wed, Aug 6, 2014 at 4:57 PM, Ted Dunning <te...@gmail.com> wrote:
> On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > I suppose in that context LLR is considered a distance (higher scores
> mean
> > > more `distant` items, co-occurring by chance only)?
> > >
> >
> > Self-correction on this one -- having given a quick look at llr paper
> > again, it looks like it is actually a similarity (higher scores meaning
> > more stable co-occurrences, i.e. it moves in the opposite direction of
> > p-value if it had been a classic test
> >
>
> LLR is a classic test.
What i meant here it doesn't produce a p-value. or does it?
> It is essentially Pearson's chi^2 test without the
> normal approximation. See my papers[1][2] introducing the test into
> computational linguistics (which ultimately brought it into all kinds of
> fields including recommendations) and also references for the G^2 test[3].
>
> [1] http://www.aclweb.org/anthology/J93-1003
> [2] http://arxiv.org/abs/1207.1847
> [3] http://en.wikipedia.org/wiki/G-test
>
Re: co-occurrence paper and code
Posted by Pat Ferrel <pa...@gmail.com>.
Thinking a bit more about the use of LLR only for similarity. Imagine the case where you are doing text analysis and have TF-IDF weights in the input matrix. LLR has one trait that makes me wonder about settling on it alone for general similarity and it’s more an observation since I have no data to address it. LLR ignores the input weights. Using document terminology now—LLR has some of the same characteristics as TF-IDF + cosine. It tends to mitigate the effect of large documents or extremely popular terms. But has there been any analysis that suggests LLR beats the traditional TF-IDF + cosine for document similarity?
BTW we once used the Mahout Item-based recommender with an ecom dataset of 2.5M users, 500K items over a year of fairly active interactions. We tried several of the similarity measures in Mahout and computed MAP for cross validation on each. LLR was the clear winner so I understand it’s singular use in recommenders.
On Aug 6, 2014, at 5:38 PM, Pat Ferrel <pa...@gmail.com> wrote:
BTW the cooccurrence code is going into RSJ too and there are uses of that where cosine is expected. I don’t know how to think about cross-cosine. Is there an argument for LLR only in RSJ?
> On Aug 6, 2014, at 5:20 PM, Sebastian Schelter <ss...@googlemail.com> wrote:
>
> I chose against porting all the similarity measures to the dsl version of
> the cooccurrence analysis for two reasons. First, adding the measures in a
> generalizable way makes the code superhard to read. Second, in practice, I
> have never seen something giving better results than llr. As Ted pointed
> out, a lot of the foundations of using similarity measures comes from
> wanting to predict ratings, which people never do in practice. I think we
> should restrict ourselves to approaches that work with implicit, count-like
> data.
>
> -s
Re: co-occurrence paper and code
Posted by Pat Ferrel <pa...@gmail.com>.
BTW the cooccurrence code is going into RSJ too and there are uses of that where cosine is expected. I don’t know how to think about cross-cosine. Is there an argument for LLR only in RSJ?
On Aug 6, 2014, at 5:20 PM, Sebastian Schelter <ss...@googlemail.com> wrote:
Sounds good to me.
-s
Am 06.08.2014 17:15 schrieb "Dmitriy Lyubimov" <dl...@gmail.com>:
> what i mean here i probably need to refactor it a little so that there's
> part of algorithm that accepts co-occurrence input directly and which is
> somewhat decoupled from the part that accepts u x item input and does
> downsampling and co-occurrence construction. So i could do some
> customization of my own to co-occurrence construction. Would that be
> reasonable if i do that?
>
>
> On Wed, Aug 6, 2014 at 5:12 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
>> Asking because i am considering pulling this implementation but for some
>> (mostly political) reasons people want to try different things here.
>>
>> I may also have to start with a different way of constructing
>> co-occurrences, and may do a few optimizations there (i.e. priority queue
>> queing/enqueing does twice the work it really needs to do etc.)
>>
>>
>>
>>
>> On Wed, Aug 6, 2014 at 5:05 PM, Sebastian Schelter <
>> ssc.open@googlemail.com> wrote:
>>
>>> I chose against porting all the similarity measures to the dsl version
> of
>>> the cooccurrence analysis for two reasons. First, adding the measures
> in a
>>> generalizable way makes the code superhard to read. Second, in
> practice, I
>>> have never seen something giving better results than llr. As Ted pointed
>>> out, a lot of the foundations of using similarity measures comes from
>>> wanting to predict ratings, which people never do in practice. I think
> we
>>> should restrict ourselves to approaches that work with implicit,
>>> count-like
>>> data.
>>>
>>> -s
>>> Am 06.08.2014 16:58 schrieb "Ted Dunning" <te...@gmail.com>:
>>>
>>>> On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
>>>> wrote:
>>>>
>>>>> On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dlieu.7@gmail.com
>>
>>>>> wrote:
>>>>>
>>>>> I suppose in that context LLR is considered a distance (higher
> scores
>>>> mean
>>>>>> more `distant` items, co-occurring by chance only)?
>>>>>>
>>>>>
>>>>> Self-correction on this one -- having given a quick look at llr
> paper
>>>>> again, it looks like it is actually a similarity (higher scores
>>> meaning
>>>>> more stable co-occurrences, i.e. it moves in the opposite direction
> of
>>>>> p-value if it had been a classic test
>>>>>
>>>>
>>>> LLR is a classic test. It is essentially Pearson's chi^2 test without
>>> the
>>>> normal approximation. See my papers[1][2] introducing the test into
>>>> computational linguistics (which ultimately brought it into all kinds
> of
>>>> fields including recommendations) and also references for the G^2
>>> test[3].
>>>>
>>>> [1] http://www.aclweb.org/anthology/J93-1003
>>>> [2] http://arxiv.org/abs/1207.1847
>>>> [3] http://en.wikipedia.org/wiki/G-test
>>>>
>>>
>>
>>
>
Re: co-occurrence paper and code
Posted by Sebastian Schelter <ss...@googlemail.com>.
Sounds good to me.
-s
Am 06.08.2014 17:15 schrieb "Dmitriy Lyubimov" <dl...@gmail.com>:
> what i mean here i probably need to refactor it a little so that there's
> part of algorithm that accepts co-occurrence input directly and which is
> somewhat decoupled from the part that accepts u x item input and does
> downsampling and co-occurrence construction. So i could do some
> customization of my own to co-occurrence construction. Would that be
> reasonable if i do that?
>
>
> On Wed, Aug 6, 2014 at 5:12 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > Asking because i am considering pulling this implementation but for some
> > (mostly political) reasons people want to try different things here.
> >
> > I may also have to start with a different way of constructing
> > co-occurrences, and may do a few optimizations there (i.e. priority queue
> > queing/enqueing does twice the work it really needs to do etc.)
> >
> >
> >
> >
> > On Wed, Aug 6, 2014 at 5:05 PM, Sebastian Schelter <
> > ssc.open@googlemail.com> wrote:
> >
> >> I chose against porting all the similarity measures to the dsl version
> of
> >> the cooccurrence analysis for two reasons. First, adding the measures
> in a
> >> generalizable way makes the code superhard to read. Second, in
> practice, I
> >> have never seen something giving better results than llr. As Ted pointed
> >> out, a lot of the foundations of using similarity measures comes from
> >> wanting to predict ratings, which people never do in practice. I think
> we
> >> should restrict ourselves to approaches that work with implicit,
> >> count-like
> >> data.
> >>
> >> -s
> >> Am 06.08.2014 16:58 schrieb "Ted Dunning" <te...@gmail.com>:
> >>
> >> > On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
> >> > wrote:
> >> >
> >> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dlieu.7@gmail.com
> >
> >> > > wrote:
> >> > >
> >> > > I suppose in that context LLR is considered a distance (higher
> scores
> >> > mean
> >> > > > more `distant` items, co-occurring by chance only)?
> >> > > >
> >> > >
> >> > > Self-correction on this one -- having given a quick look at llr
> paper
> >> > > again, it looks like it is actually a similarity (higher scores
> >> meaning
> >> > > more stable co-occurrences, i.e. it moves in the opposite direction
> of
> >> > > p-value if it had been a classic test
> >> > >
> >> >
> >> > LLR is a classic test. It is essentially Pearson's chi^2 test without
> >> the
> >> > normal approximation. See my papers[1][2] introducing the test into
> >> > computational linguistics (which ultimately brought it into all kinds
> of
> >> > fields including recommendations) and also references for the G^2
> >> test[3].
> >> >
> >> > [1] http://www.aclweb.org/anthology/J93-1003
> >> > [2] http://arxiv.org/abs/1207.1847
> >> > [3] http://en.wikipedia.org/wiki/G-test
> >> >
> >>
> >
> >
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
what i mean here i probably need to refactor it a little so that there's
part of algorithm that accepts co-occurrence input directly and which is
somewhat decoupled from the part that accepts u x item input and does
downsampling and co-occurrence construction. So i could do some
customization of my own to co-occurrence construction. Would that be
reasonable if i do that?
On Wed, Aug 6, 2014 at 5:12 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> Asking because i am considering pulling this implementation but for some
> (mostly political) reasons people want to try different things here.
>
> I may also have to start with a different way of constructing
> co-occurrences, and may do a few optimizations there (i.e. priority queue
> queing/enqueing does twice the work it really needs to do etc.)
>
>
>
>
> On Wed, Aug 6, 2014 at 5:05 PM, Sebastian Schelter <
> ssc.open@googlemail.com> wrote:
>
>> I chose against porting all the similarity measures to the dsl version of
>> the cooccurrence analysis for two reasons. First, adding the measures in a
>> generalizable way makes the code superhard to read. Second, in practice, I
>> have never seen something giving better results than llr. As Ted pointed
>> out, a lot of the foundations of using similarity measures comes from
>> wanting to predict ratings, which people never do in practice. I think we
>> should restrict ourselves to approaches that work with implicit,
>> count-like
>> data.
>>
>> -s
>> Am 06.08.2014 16:58 schrieb "Ted Dunning" <te...@gmail.com>:
>>
>> > On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
>> > wrote:
>> >
>> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
>> > > wrote:
>> > >
>> > > I suppose in that context LLR is considered a distance (higher scores
>> > mean
>> > > > more `distant` items, co-occurring by chance only)?
>> > > >
>> > >
>> > > Self-correction on this one -- having given a quick look at llr paper
>> > > again, it looks like it is actually a similarity (higher scores
>> meaning
>> > > more stable co-occurrences, i.e. it moves in the opposite direction of
>> > > p-value if it had been a classic test
>> > >
>> >
>> > LLR is a classic test. It is essentially Pearson's chi^2 test without
>> the
>> > normal approximation. See my papers[1][2] introducing the test into
>> > computational linguistics (which ultimately brought it into all kinds of
>> > fields including recommendations) and also references for the G^2
>> test[3].
>> >
>> > [1] http://www.aclweb.org/anthology/J93-1003
>> > [2] http://arxiv.org/abs/1207.1847
>> > [3] http://en.wikipedia.org/wiki/G-test
>> >
>>
>
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
Asking because i am considering pulling this implementation but for some
(mostly political) reasons people want to try different things here.
I may also have to start with a different way of constructing
co-occurrences, and may do a few optimizations there (i.e. priority queue
queing/enqueing does twice the work it really needs to do etc.)
On Wed, Aug 6, 2014 at 5:05 PM, Sebastian Schelter <ss...@googlemail.com>
wrote:
> I chose against porting all the similarity measures to the dsl version of
> the cooccurrence analysis for two reasons. First, adding the measures in a
> generalizable way makes the code superhard to read. Second, in practice, I
> have never seen something giving better results than llr. As Ted pointed
> out, a lot of the foundations of using similarity measures comes from
> wanting to predict ratings, which people never do in practice. I think we
> should restrict ourselves to approaches that work with implicit, count-like
> data.
>
> -s
> Am 06.08.2014 16:58 schrieb "Ted Dunning" <te...@gmail.com>:
>
> > On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > > wrote:
> > >
> > > I suppose in that context LLR is considered a distance (higher scores
> > mean
> > > > more `distant` items, co-occurring by chance only)?
> > > >
> > >
> > > Self-correction on this one -- having given a quick look at llr paper
> > > again, it looks like it is actually a similarity (higher scores meaning
> > > more stable co-occurrences, i.e. it moves in the opposite direction of
> > > p-value if it had been a classic test
> > >
> >
> > LLR is a classic test. It is essentially Pearson's chi^2 test without
> the
> > normal approximation. See my papers[1][2] introducing the test into
> > computational linguistics (which ultimately brought it into all kinds of
> > fields including recommendations) and also references for the G^2
> test[3].
> >
> > [1] http://www.aclweb.org/anthology/J93-1003
> > [2] http://arxiv.org/abs/1207.1847
> > [3] http://en.wikipedia.org/wiki/G-test
> >
>
Re: co-occurrence paper and code
Posted by Sebastian Schelter <ss...@googlemail.com>.
I chose against porting all the similarity measures to the dsl version of
the cooccurrence analysis for two reasons. First, adding the measures in a
generalizable way makes the code superhard to read. Second, in practice, I
have never seen something giving better results than llr. As Ted pointed
out, a lot of the foundations of using similarity measures comes from
wanting to predict ratings, which people never do in practice. I think we
should restrict ourselves to approaches that work with implicit, count-like
data.
-s
Am 06.08.2014 16:58 schrieb "Ted Dunning" <te...@gmail.com>:
> On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > I suppose in that context LLR is considered a distance (higher scores
> mean
> > > more `distant` items, co-occurring by chance only)?
> > >
> >
> > Self-correction on this one -- having given a quick look at llr paper
> > again, it looks like it is actually a similarity (higher scores meaning
> > more stable co-occurrences, i.e. it moves in the opposite direction of
> > p-value if it had been a classic test
> >
>
> LLR is a classic test. It is essentially Pearson's chi^2 test without the
> normal approximation. See my papers[1][2] introducing the test into
> computational linguistics (which ultimately brought it into all kinds of
> fields including recommendations) and also references for the G^2 test[3].
>
> [1] http://www.aclweb.org/anthology/J93-1003
> [2] http://arxiv.org/abs/1207.1847
> [3] http://en.wikipedia.org/wiki/G-test
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
On Wed, Aug 6, 2014 at 5:49 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> I suppose in that context LLR is considered a distance (higher scores mean
> > more `distant` items, co-occurring by chance only)?
> >
>
> Self-correction on this one -- having given a quick look at llr paper
> again, it looks like it is actually a similarity (higher scores meaning
> more stable co-occurrences, i.e. it moves in the opposite direction of
> p-value if it had been a classic test
>
LLR is a classic test. It is essentially Pearson's chi^2 test without the
normal approximation. See my papers[1][2] introducing the test into
computational linguistics (which ultimately brought it into all kinds of
fields including recommendations) and also references for the G^2 test[3].
[1] http://www.aclweb.org/anthology/J93-1003
[2] http://arxiv.org/abs/1207.1847
[3] http://en.wikipedia.org/wiki/G-test
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
We went around this may-pole a while ago. It is the same if the matrix is
binary. It isn't otherwise. Whether this code might someday be used in a
context with non-binary inputs is an open question. Likewise, whether it
is worth saving some time by omitting a thresholding operation to binarize
the matrix is similarly not clear.
My feeling is that assuming a binary matrix is fine.
On Wed, Aug 6, 2014 at 5:54 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> is this
>
> val bcastNumInteractions =
> drmBroadcast(drmI.numNonZeroElementsPerColumn)
>
> any different from just saying `drmI.colSums`?
>
>
> On Wed, Aug 6, 2014 at 4:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> >
> >
> >
> > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > I suppose in that context LLR is considered a distance (higher scores
> mean
> >> more `distant` items, co-occurring by chance only)?
> >>
> >
> > Self-correction on this one -- having given a quick look at llr paper
> > again, it looks like it is actually a similarity (higher scores meaning
> > more stable co-occurrences, i.e. it moves in the opposite direction of
> > p-value if it had been a classic test
> >
> >
> >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> >>
> >> -d
> >>
> >
> >
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
i thought `drmI` argument here meant indicator matrix (i.e. 1.0 or 0.0 ) ?
On Wed, Aug 6, 2014 at 5:03 PM, Pat Ferrel <pa...@gmail.com> wrote:
> Yes because the matrix A’A is not necessarily boolean. The actual value is
> ignored but it’s in the matrix so the colSums was not correct.
>
> On Aug 6, 2014, at 4:54 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
> is this
>
> val bcastNumInteractions =
> drmBroadcast(drmI.numNonZeroElementsPerColumn)
>
> any different from just saying `drmI.colSums`?
>
>
> On Wed, Aug 6, 2014 at 4:49 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> >
> >
> >
> > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > I suppose in that context LLR is considered a distance (higher scores
> mean
> >> more `distant` items, co-occurring by chance only)?
> >>
> >
> > Self-correction on this one -- having given a quick look at llr paper
> > again, it looks like it is actually a similarity (higher scores meaning
> > more stable co-occurrences, i.e. it moves in the opposite direction of
> > p-value if it had been a classic test
> >
> >
> >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> >>
> >> -d
> >>
> >
> >
>
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
On Wed, Aug 6, 2014 at 6:03 PM, Pat Ferrel <pa...@gmail.com> wrote:
> Yes because the matrix A’A is not necessarily boolean. The actual value is
> ignored but it’s in the matrix so the colSums was not correct.
>
> On Aug 6, 2014, at 4:54 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
> is this
>
> val bcastNumInteractions =
> drmBroadcast(drmI.numNonZeroElementsPerColumn)
>
> any different from just saying `drmI.colSums`?
>
Ignore what I said and listen to this guy.
I forgot that this was after the cooccurrence counting.
Re: co-occurrence paper and code
Posted by Pat Ferrel <pa...@gmail.com>.
Yes because the matrix A’A is not necessarily boolean. The actual value is ignored but it’s in the matrix so the colSums was not correct.
On Aug 6, 2014, at 4:54 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
is this
val bcastNumInteractions =
drmBroadcast(drmI.numNonZeroElementsPerColumn)
any different from just saying `drmI.colSums`?
On Wed, Aug 6, 2014 at 4:49 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
>
>
> On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> I suppose in that context LLR is considered a distance (higher scores mean
>> more `distant` items, co-occurring by chance only)?
>>
>
> Self-correction on this one -- having given a quick look at llr paper
> again, it looks like it is actually a similarity (higher scores meaning
> more stable co-occurrences, i.e. it moves in the opposite direction of
> p-value if it had been a classic test
>
>
>> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>>
>> -d
>>
>
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
is this
val bcastNumInteractions =
drmBroadcast(drmI.numNonZeroElementsPerColumn)
any different from just saying `drmI.colSums`?
On Wed, Aug 6, 2014 at 4:49 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
>
>
> On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> I suppose in that context LLR is considered a distance (higher scores mean
>> more `distant` items, co-occurring by chance only)?
>>
>
> Self-correction on this one -- having given a quick look at llr paper
> again, it looks like it is actually a similarity (higher scores meaning
> more stable co-occurrences, i.e. it moves in the opposite direction of
> p-value if it had been a classic test
>
>
>> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>>
>> -d
>>
>
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
I suppose in that context LLR is considered a distance (higher scores mean
> more `distant` items, co-occurring by chance only)?
>
Self-correction on this one -- having given a quick look at llr paper
again, it looks like it is actually a similarity (higher scores meaning
more stable co-occurrences, i.e. it moves in the opposite direction of
p-value if it had been a classic test
> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>
> -d
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
On Wed, Aug 6, 2014 at 4:53 PM, Ted Dunning <te...@gmail.com> wrote:
> strict anti-correlation between them. Yes, there is a sign change, but
> they still are representing basically the same thing. Elevation and depth
>
Sure. This is basic knowledge. The reason i asked is because the original
paper gives formulation without sign change in section 4.4 (e.g. cosine
similarity and manhattan distance formulas) and bills it as a functional
parameter to similarity calculation. Which would seem to result in an
technical error as described there since they make no mention about this
distinction at all.
Just was wondering if this was compensated for somewhere else that i don't
immediately see.
>
>
>
> On Wed, Aug 6, 2014 at 5:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > So, compared to original paper [1], similarity is now hardcoded and
> always
> > LLR? Do we have any plans to parameterize that further? Is there any
> reason
> > to parameterize it?
> >
> >
> > Also, reading the paper, i am a bit wondering -- similarity and distance
> > are functions that usually are moving into different directions (i.e.
> > cosine similarity and angular distance) but in the paper distance scores
> > are also considered similarities? How's that?
> >
> > I suppose in that context LLR is considered a distance (higher scores
> mean
> > more `distant` items, co-occurring by chance only)?
> >
> > [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> >
> > -d
> >
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
The entire reference to similarity harks back to the original formulation
of the MovieLens and Firefox recommenders which looked for similarity of
rating patterns. That made some sense then, but it is a bit of a tortured
turn of phrase when other formulations of recommendation are used.
There are currently two general approaches that seem to be generating
reasonable recommendation results in practice, LLR based sparsification of
cooccurrence and cross-occurrence matrices and matrix completion techniques
typically implemented as some form of factorization. The enormous number
of options that Mahout's map-reduce recommender implements have little
practical utility and are more of an artifact of a desire to implement most
of the research algorithms in a single framework.
The concept of distance can be useful in the matrix factorization since it
allows efficient algorithms to be derived. But with the sparsification
problem, the concepts of similarity and distance break down because with
cooccurrence we don't just have two answers. Instead, we have three:
anomalous cooccurrence, non-anomalous cooccurrence and insufficient data.
For the purposes of sparsification, we lump non-anomalous cooccurrence and
insufficient data together, but this lumping has the side effect that the
score that we get is not a useful measure of association, distance or
similarity. Instead, we just put down that anomalously cooccurrent pairs
are anomalous (a binary decision) and leave the weighting of them until
later.
If you are strict about thinking about cooccurrence measures as a distance,
you get into measures of the strength of association. These measures will
separate anomalous cooccurrence from non-anomalous cooccurrence, but they
will smear the insufficient data cases into both options. Since most pairs
have insufficient data, this will be a relatively disastrous thing to do,
causing massive numbers of false positives that swamp the valid pairs. The
virtue of LLR is that it does not do this, but there is a corollary vice in
that the resulting score is not useful as a distance.
Regarding the question about similarities and distances being used
essentially synonymously, this is relatively common because of the fairly
strict anti-correlation between them. Yes, there is a sign change, but
they still are representing basically the same thing. Elevation and depth
are similarly very closely related and somebody might refer to the
elevation of an underwater mountain range above its base or its depth below
the surface. These expressions are referring to the same z axis
measurement with different origins.
On Wed, Aug 6, 2014 at 5:21 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> So, compared to original paper [1], similarity is now hardcoded and always
> LLR? Do we have any plans to parameterize that further? Is there any reason
> to parameterize it?
>
>
> Also, reading the paper, i am a bit wondering -- similarity and distance
> are functions that usually are moving into different directions (i.e.
> cosine similarity and angular distance) but in the paper distance scores
> are also considered similarities? How's that?
>
> I suppose in that context LLR is considered a distance (higher scores mean
> more `distant` items, co-occurring by chance only)?
>
> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>
> -d
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
Ok. so here's the recap of what i have gathered (also illustrates source of
my initial confusion).
(1) The original test assumes that there are two Bernoulli random
variables, A and B, and their draws are conducted at the same time. Hence,
the logic goes, the LLR statistics will asymptotically approximate
chi-squared with df = 1. Another point here is that for discrete events
information measures baked in in the statistics work better _to compare_
things, than normality assumptions of the chi-squared distributions, for
the few datasets studied. The hope is that this study can extrapolate to
other data sets.
Note that i have found no accuracy study done that we can use chi-squared
distribution to derive p-values and makes confidence quanification
statements as in "we have 95% confidence that was not coincidence in
behavior of the subject". Which is in part, perhaps, due to approximation,
and in part perhaps because of assumptions of the problems i discuss below.
(2) With Surprise & concidence paper, the study goes over evaluating what i
call for now a "bigram problem", which is signficantly different setting
from the CF setting in co-occurrence paper.
With bigram problem, as far as i gathered from numbers, we collect N
bigrams. N could be thought of as number of edges in directed labeled graph
connecting token-representing nodes, with labels representing counts.
Obviously this graph is then can be represented as a sparse cooccurrence
matrix. Under this setting, "A&B" represents matrix element, "withA" and
"withB" represents correspondent element of colSums(), and the total trial
count (N) represents matrix elementwise sum (aka 1st p-norm). This problem
formulation for co-occurrence matrix, as we will see, is signficantly
different from the CF co-occurrence construction.
Another thing is that with bigram problem we encounter stretch of sampling
assumptions. In order to comply with assumptions made in (1), and keeping
in mind that 1bigram = 1draw, we have to assume we do a bernoulli draw for
every term with every bigram. But actual data tells us that only exactly
two variables (A and B) can draw as true at every draw; i.e. we just do
one hypergeometrical (or multinomial, if you are willing to consider
self-co-occurrences) with k=2, and set the rest of the term set as being
drawn as 0s. Then, again, we can demonstrate that it works better to
_compare_ things still (or do top-n), since assumption stretch equally
applies to all, but somehow it still feels like we cannot reliably
demostrate accuracy of confidence measurements of bigrams, and, again, it
would seem no accuracy study on a concrete dataset for confidence measure
was actually attempted.
(3) The Sebastien's paper describes another kind of problem, which i called
"CF co-occurrence" to oppose the "bigram" case. In here, we test each item
independently using individual user choice as a trial. Hence, number of
trials (N) = number of user per item, and withA and withB are taken as
elements of colsums of user/item matrix (not co-occurrence matrix). makes
sense.
Relaxation of assumption here is as follows. We obviously want to measure
unbiased trial behavor for items, since when we present them to user as
recommendation, we will solely rely on item true value given fairly
guaranteed portion of user attention. However, by the way of sampling and
construction of building our trials dataset, we experience, as they say
it, a _biased sampling_ for reasons mentioned above (UI does not guarantee
equal portions of user attention per item, so significant portion of
assumed negative trials simply did not occur).
In extreme case, when we just start the system, we have 0 exploration
happened, and thus our degenerate experiments represent an extremely biased
trials data. As we move towards more explored landscape, our bias
(hopefully) dissappear. However, it is not quite clear what time it would
take, and whether this time would be shorter than the stock time of the
item in many cases. So, in most realistic cases the trials sampling bias
will persist. Among other things, this also significantly relaxes accuracy
of any sort of confidence statement along the lines "we are 95% confident A
and B co-occurred, if any, due to chance".
(4) Now, about my problem.
My problem is more like "bigram" problem rather than "CF" problem. I am
constructing co-occurrence based on labeled graph and then evaluate the
chances of non-independence of co-occurrences. As such, i never have A'A
operation (and no use of users as equivalent of trials).
Comparing scores and inferring top N is of course still interesting for me.
However, perhaps more importantly, i was aiming to evaluate confidence in
more or less chi-squared p-value terms and make statements along the lines,
"given bias-compensated nature of trials, we can express 95% confidence of
non-coincidence of events A and B".
I do compare things as well, but also i expect a great amount of
non-confident results (due to the way data collected), and being able to
throw away a great deal of low-confidence co-occurrences. Maybe even 99%
co-occurrences (the way experiments are conducted, we can parametrise them
to manipulate true co-occurrence recall/precision, but we need to be able
to tell false co-occurrences more or less confidently in order to make a
good judgement about experiment parameters). Changing parameters of
experiment is obviously changing distributions of trials it produces, but
under this particular problem it is o.k. for various reasons as it also
translates into the distributions about which prediction is made.
On Mon, Aug 11, 2014 at 5:22 PM, Ted Dunning <te...@gmail.com> wrote:
> Opportunity in this case does not refer to "Saw something and decided to
> buy/click/view/listen". Instead, it refers to the entire process including
> the UI and whatever discovery mechanisms exist.
>
> You are correct that it is not just measuring the human component.
>
>
>
> On Mon, Aug 11, 2014 at 4:56 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > this logic does assume though that every user had an opportunity to
> eyeball
> > (A,B) pair and chose (vastly) not to buy them whereas it may have
> > overwhelmingly happened due to lack of exploration. thus, (not A & not B)
> > figures are probably grossly overestimated
> >
> >
> > On Mon, Aug 11, 2014 at 4:53 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > No, the question was why total number of trials sent to LLR is
> considered
> > > to be m where M is m x n is a user/item matrix.
> > >
> > > ok i got it. i made some incorrect assumption about previous code
> steps,
> > > hence my inference derailed.
> > >
> > >
> > >
> > >
> > > On Mon, Aug 11, 2014 at 4:07 PM, Ted Dunning <te...@gmail.com>
> > > wrote:
> > >
> > >> If you binarize the original occurrence matrix then it seems to me
> that
> > >> the
> > >> values in the cooccurrence matrix *are* user counts.
> > >>
> > >> Perhaps I misunderstand your original question.
> > >>
> > >>
> > >>
> > >> On Mon, Aug 11, 2014 at 3:44 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > >> wrote:
> > >>
> > >> > sorry rather total occurrences of a pair should be sum(a_i) +
> > sum(a_j) -
> > >> > a_ij (not 1norm of course)
> > >> >
> > >> >
> > >> > On Mon, Aug 11, 2014 at 3:11 PM, Dmitriy Lyubimov <
> dlieu.7@gmail.com>
> > >> > wrote:
> > >> >
> > >> > > Why coocurrence code takes number of users as total interactions?
> > >> > > shouldn't that be 1-norm of the co-occurrence matrix?
> > >> > >
> > >> > >
> > >> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <
> dlieu.7@gmail.com
> > >
> > >> > > wrote:
> > >> > >
> > >> > >> So, compared to original paper [1], similarity is now hardcoded
> and
> > >> > >> always LLR? Do we have any plans to parameterize that further? Is
> > >> there
> > >> > any
> > >> > >> reason to parameterize it?
> > >> > >>
> > >> > >>
> > >> > >> Also, reading the paper, i am a bit wondering -- similarity and
> > >> distance
> > >> > >> are functions that usually are moving into different directions
> > (i.e.
> > >> > >> cosine similarity and angular distance) but in the paper distance
> > >> scores
> > >> > >> are also considered similarities? How's that?
> > >> > >>
> > >> > >> I suppose in that context LLR is considered a distance (higher
> > scores
> > >> > >> mean more `distant` items, co-occurring by chance only)?
> > >> > >>
> > >> > >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> > >> > >>
> > >> > >> -d
> > >> > >>
> > >> > >
> > >> > >
> > >> >
> > >>
> > >
> > >
> >
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
Opportunity in this case does not refer to "Saw something and decided to
buy/click/view/listen". Instead, it refers to the entire process including
the UI and whatever discovery mechanisms exist.
You are correct that it is not just measuring the human component.
On Mon, Aug 11, 2014 at 4:56 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> this logic does assume though that every user had an opportunity to eyeball
> (A,B) pair and chose (vastly) not to buy them whereas it may have
> overwhelmingly happened due to lack of exploration. thus, (not A & not B)
> figures are probably grossly overestimated
>
>
> On Mon, Aug 11, 2014 at 4:53 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > No, the question was why total number of trials sent to LLR is considered
> > to be m where M is m x n is a user/item matrix.
> >
> > ok i got it. i made some incorrect assumption about previous code steps,
> > hence my inference derailed.
> >
> >
> >
> >
> > On Mon, Aug 11, 2014 at 4:07 PM, Ted Dunning <te...@gmail.com>
> > wrote:
> >
> >> If you binarize the original occurrence matrix then it seems to me that
> >> the
> >> values in the cooccurrence matrix *are* user counts.
> >>
> >> Perhaps I misunderstand your original question.
> >>
> >>
> >>
> >> On Mon, Aug 11, 2014 at 3:44 PM, Dmitriy Lyubimov <dl...@gmail.com>
> >> wrote:
> >>
> >> > sorry rather total occurrences of a pair should be sum(a_i) +
> sum(a_j) -
> >> > a_ij (not 1norm of course)
> >> >
> >> >
> >> > On Mon, Aug 11, 2014 at 3:11 PM, Dmitriy Lyubimov <dl...@gmail.com>
> >> > wrote:
> >> >
> >> > > Why coocurrence code takes number of users as total interactions?
> >> > > shouldn't that be 1-norm of the co-occurrence matrix?
> >> > >
> >> > >
> >> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dlieu.7@gmail.com
> >
> >> > > wrote:
> >> > >
> >> > >> So, compared to original paper [1], similarity is now hardcoded and
> >> > >> always LLR? Do we have any plans to parameterize that further? Is
> >> there
> >> > any
> >> > >> reason to parameterize it?
> >> > >>
> >> > >>
> >> > >> Also, reading the paper, i am a bit wondering -- similarity and
> >> distance
> >> > >> are functions that usually are moving into different directions
> (i.e.
> >> > >> cosine similarity and angular distance) but in the paper distance
> >> scores
> >> > >> are also considered similarities? How's that?
> >> > >>
> >> > >> I suppose in that context LLR is considered a distance (higher
> scores
> >> > >> mean more `distant` items, co-occurring by chance only)?
> >> > >>
> >> > >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> >> > >>
> >> > >> -d
> >> > >>
> >> > >
> >> > >
> >> >
> >>
> >
> >
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
this logic does assume though that every user had an opportunity to eyeball
(A,B) pair and chose (vastly) not to buy them whereas it may have
overwhelmingly happened due to lack of exploration. thus, (not A & not B)
figures are probably grossly overestimated
On Mon, Aug 11, 2014 at 4:53 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> No, the question was why total number of trials sent to LLR is considered
> to be m where M is m x n is a user/item matrix.
>
> ok i got it. i made some incorrect assumption about previous code steps,
> hence my inference derailed.
>
>
>
>
> On Mon, Aug 11, 2014 at 4:07 PM, Ted Dunning <te...@gmail.com>
> wrote:
>
>> If you binarize the original occurrence matrix then it seems to me that
>> the
>> values in the cooccurrence matrix *are* user counts.
>>
>> Perhaps I misunderstand your original question.
>>
>>
>>
>> On Mon, Aug 11, 2014 at 3:44 PM, Dmitriy Lyubimov <dl...@gmail.com>
>> wrote:
>>
>> > sorry rather total occurrences of a pair should be sum(a_i) + sum(a_j) -
>> > a_ij (not 1norm of course)
>> >
>> >
>> > On Mon, Aug 11, 2014 at 3:11 PM, Dmitriy Lyubimov <dl...@gmail.com>
>> > wrote:
>> >
>> > > Why coocurrence code takes number of users as total interactions?
>> > > shouldn't that be 1-norm of the co-occurrence matrix?
>> > >
>> > >
>> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
>> > > wrote:
>> > >
>> > >> So, compared to original paper [1], similarity is now hardcoded and
>> > >> always LLR? Do we have any plans to parameterize that further? Is
>> there
>> > any
>> > >> reason to parameterize it?
>> > >>
>> > >>
>> > >> Also, reading the paper, i am a bit wondering -- similarity and
>> distance
>> > >> are functions that usually are moving into different directions (i.e.
>> > >> cosine similarity and angular distance) but in the paper distance
>> scores
>> > >> are also considered similarities? How's that?
>> > >>
>> > >> I suppose in that context LLR is considered a distance (higher scores
>> > >> mean more `distant` items, co-occurring by chance only)?
>> > >>
>> > >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>> > >>
>> > >> -d
>> > >>
>> > >
>> > >
>> >
>>
>
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
No, the question was why total number of trials sent to LLR is considered
to be m where M is m x n is a user/item matrix.
ok i got it. i made some incorrect assumption about previous code steps,
hence my inference derailed.
On Mon, Aug 11, 2014 at 4:07 PM, Ted Dunning <te...@gmail.com> wrote:
> If you binarize the original occurrence matrix then it seems to me that the
> values in the cooccurrence matrix *are* user counts.
>
> Perhaps I misunderstand your original question.
>
>
>
> On Mon, Aug 11, 2014 at 3:44 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > sorry rather total occurrences of a pair should be sum(a_i) + sum(a_j) -
> > a_ij (not 1norm of course)
> >
> >
> > On Mon, Aug 11, 2014 at 3:11 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > Why coocurrence code takes number of users as total interactions?
> > > shouldn't that be 1-norm of the co-occurrence matrix?
> > >
> > >
> > > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > > wrote:
> > >
> > >> So, compared to original paper [1], similarity is now hardcoded and
> > >> always LLR? Do we have any plans to parameterize that further? Is
> there
> > any
> > >> reason to parameterize it?
> > >>
> > >>
> > >> Also, reading the paper, i am a bit wondering -- similarity and
> distance
> > >> are functions that usually are moving into different directions (i.e.
> > >> cosine similarity and angular distance) but in the paper distance
> scores
> > >> are also considered similarities? How's that?
> > >>
> > >> I suppose in that context LLR is considered a distance (higher scores
> > >> mean more `distant` items, co-occurring by chance only)?
> > >>
> > >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> > >>
> > >> -d
> > >>
> > >
> > >
> >
>
Re: co-occurrence paper and code
Posted by Ted Dunning <te...@gmail.com>.
If you binarize the original occurrence matrix then it seems to me that the
values in the cooccurrence matrix *are* user counts.
Perhaps I misunderstand your original question.
On Mon, Aug 11, 2014 at 3:44 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> sorry rather total occurrences of a pair should be sum(a_i) + sum(a_j) -
> a_ij (not 1norm of course)
>
>
> On Mon, Aug 11, 2014 at 3:11 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > Why coocurrence code takes number of users as total interactions?
> > shouldn't that be 1-norm of the co-occurrence matrix?
> >
> >
> > On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> >> So, compared to original paper [1], similarity is now hardcoded and
> >> always LLR? Do we have any plans to parameterize that further? Is there
> any
> >> reason to parameterize it?
> >>
> >>
> >> Also, reading the paper, i am a bit wondering -- similarity and distance
> >> are functions that usually are moving into different directions (i.e.
> >> cosine similarity and angular distance) but in the paper distance scores
> >> are also considered similarities? How's that?
> >>
> >> I suppose in that context LLR is considered a distance (higher scores
> >> mean more `distant` items, co-occurring by chance only)?
> >>
> >> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
> >>
> >> -d
> >>
> >
> >
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
sorry rather total occurrences of a pair should be sum(a_i) + sum(a_j) -
a_ij (not 1norm of course)
On Mon, Aug 11, 2014 at 3:11 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> Why coocurrence code takes number of users as total interactions?
> shouldn't that be 1-norm of the co-occurrence matrix?
>
>
> On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
>> So, compared to original paper [1], similarity is now hardcoded and
>> always LLR? Do we have any plans to parameterize that further? Is there any
>> reason to parameterize it?
>>
>>
>> Also, reading the paper, i am a bit wondering -- similarity and distance
>> are functions that usually are moving into different directions (i.e.
>> cosine similarity and angular distance) but in the paper distance scores
>> are also considered similarities? How's that?
>>
>> I suppose in that context LLR is considered a distance (higher scores
>> mean more `distant` items, co-occurring by chance only)?
>>
>> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>>
>> -d
>>
>
>
Re: co-occurrence paper and code
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
Why coocurrence code takes number of users as total interactions? shouldn't
that be 1-norm of the co-occurrence matrix?
On Wed, Aug 6, 2014 at 4:21 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> So, compared to original paper [1], similarity is now hardcoded and always
> LLR? Do we have any plans to parameterize that further? Is there any reason
> to parameterize it?
>
>
> Also, reading the paper, i am a bit wondering -- similarity and distance
> are functions that usually are moving into different directions (i.e.
> cosine similarity and angular distance) but in the paper distance scores
> are also considered similarities? How's that?
>
> I suppose in that context LLR is considered a distance (higher scores mean
> more `distant` items, co-occurring by chance only)?
>
> [1] http://ssc.io/wp-content/uploads/2012/06/rec11-schelter.pdf
>
> -d
>