[sldev] Research on flagging/rating systems? (Re: Your Feedback Wanted on Search Flagging !)

[Celierra Darling]

On Fri, May 2, 2008 at 6:15 PM, Rob Lanphier <robla at lindenlab.com> wrote:
> Hi all,
>
>  Let me ask this another way.  Is anyone aware of published research or
> other helpful information in this area that may not have been considered in
> the original design?   Big bonus points if you can actually provide helpful
> quotes from that research that are relevant to the proposed design.
>
>  Rob
>

Hmm... I think a version of the Weighted Majority Algorithm applies
here (see http://www.cs.cornell.edu/courses/cs482/2008sp/handouts/prediction.pdf
, section 2 and figure 1), but it'll need a few modifications.

If you'll forgive me for running away with this (I need practice for
my algorithms final anyway), I'd suggest:

- Each normal resident is an "expert" in the terminology the
algorithm.  Their credibilities ("weights") start at 1.
- A resident flags (predicts 1) if they saw the content for at least y
seconds, and did set a flag
- A resident sets an anti-flag (predicts 0) if they seem to "approve"
of the search result, which can be defined as
-- saw the content for at least x seconds, but didn't set a flag, and/or
-- teleported to the location, and/or stayed there for a while, and/or...
-- something else
- Add a "null" prediction, i.e. neither a 0 nor 1.  Null votes
contribute to neither the weight of 0s nor the weight of 1s.  Weights
are neither increased nor decreased for null predictions.
- The "correct answers" are derived from actions by employees or
trusted volunteers

The original algorithm only decreases weights for every wrong answer:
when a "wrong" prediction is made, the algorithm says to knock down
the weight by the constant factor r = (1-epsilon).   This would
constantly decrease the weights of the most active residents (due to
human error and attrition).  So, add a concept of forgiveness and an
ability to gain credibility through correct flaggings:
- When a correct prediction is made, increase the resident's weight to
max(n*old_weight, maximum_weight) where 1 < n < 1/r.  (Let forgiveness
cost f be the number of correct flaggings necessary in order to
recover from the loss of credibility due to one wrong flagging, which
I think is -log base r of n.)

Then:
Consider all 0 and 1 votes over the past however-long period.
Suspiciousness metric: sum of weights of residents predicting 1 - sum
of weights of residents predicting 0
List results based on their suspiciousness metric
Lindens/volunteers look at the most suspicious entries, and act on
those (note that the algorithm needs "correct answers", so preferably
everything should be human-checked)

This has some nice properties:
- Suppose that the weight of 0 votes stays relatively constant over
time.  x residents repeatedly flagging the same entries together can
abusively/mistakenly flag at most O(log x) times in a row before their
weight becomes so low that they cannot overcome the weight of 0 votes.
 In the worst case, the x accounts perfectly split up their votes in
order to get O(x) abuses, but that requires a lot of luck (see below).
- Beyond that point, those x residents would need to help the system f
times (f is the forgiveness cost from before) for every time they
abuse it / make a mistake.
- No action needs to be taken on abusers, since their weights will
silently and rapidly fall towards zero, and the abuser will just
wonder why the system is not listening to their flags anymore (as long
as they're ignorant of this algorithm).
- Since nobody ever looks at the non-suspicious results, you can't
build up forgiveness by anti-flagging "easy" results - you have to
make decisions on the difficult cases.

Three not-so-good properties:
- If someone with perfect knowledge and x alts is trying to abuse the
algorithm, that person could theoretically be able to get O(x) abuses,
by doing the following:
-- Group the alts into teams so that their weights sum to something
just large enough to put the targets into the top-n suspiciousness
list.  Call this weight c.
-- Flag the targets, and wait until the flagging is rejected
-- Repeat step 1 with new weights (this results in 1-epsilon times
fewer groupings)
-- Flag the targets again
-- Repeat
This requires a lot of knowledge - in particular, I don't think anyone
will be able to see how many flags they need to put in to get
something into the suspiciousness metric.  Epsilon is also pretty hard
to get knowledge of.

Might want to check the math on the O(x) bound... It comes from:
Let r = (1-epsilon).  The number of abuses is something like:
x/c + (x/c)r + (x/c)r^2 + ... + (x/c)r^(-log_r (x/c))
= (x/c)*(1-r*r^log_r(c/x))/(1-r), using the formula for geometric series
= (x/c)*(1-rc/x)/(1-r)
= (x/c - r)/(1-r)
= (1/c)(1/epsilon)x - (1-epsilon)/epsilon, substituted for r
= O(x)
That's a pretty small constant factor in front of the x, though. :)

- If a large army of new alts flags lots of entries at once, all the
metrics will be calculated with the old weights = 1, and they could
pollute the entire top-n suspiciousness list.  When the next few
'correct answers' come in, you'd want to knock down all the alts'
weights and recalculate the applicable metrics so that the garbage
entries slide off the list.  I imagine that this would be quite
costly.  Actually getting to the point of exploiting this is
*probably* too difficult, but I'm not certain...

- Most flaggings (preferably all of them) need to be human-checked for
the algorithm to work...

There are a lot of details and pieces that can be changed while
keeping most of the good stuff, so hope that helps? :)

-- 
~Alex and Cel