Weighted Majority

See the Wikipedia page on the "Weighted Majority Algorithm."

The idea of "weighted majority" was presented in my Reasoning About Computation lecture today. The example he gave in class was this.

Consider you need to make a buy/sell decision based on the recommendations of your analysts. Some are better than others. It makes sense that you would lean toward the recommendations of your better analysts and ignore those which have performed poorly in the past.

A deterministic way of implementing this is to assign a "weight" to each of the analysts, which represents your trust in them. When they predict successfully, maintain the weight; when they are incorrect, divide their weight by some factor (say, 2). Then perform a weighted average of the predictions and round to the nearest answer (BUY or SELL).

Then Prof. Chazelle suggested that you could do better if you introduced a little bit of randomness! Well then! Instead of simply taking the weighted majority, use roulette wheel selection, where each portion of the wheel is one of the predictions and its size is proportional to the weight of the analyst.

Of course the math didn't all sink in, so I coded it in Ruby.

# Okay, so I didn't try very hard on this
# Refactor it yourself, jerk

class Agent
  def initialize(accuracy)
    @accuracy = accuracy
  end

  def guess(input)
    if rand(100) < @accuracy * 100
      input
    else
      input == 1 ? 0 : 1
    end
  end

  def to_s
    @accuracy.to_s
  end
end

class Runner
  def initialize(agents, type = :normal, punishment = 0.5)
    raise unless [:normal, :weighted, :weighted_random].include? type

    @agents = agents
    @type = type
    @weighted = [:weighted, :weighted_random].include? type
    @weighted_random = type == :weighted_random
    @punishment = punishment
  end

  def run(rounds)
    if @weighted
      @weights = Hash.new
      @agents.each { |agent| @weights[agent] = 1.0 }
    end

    return weighted_random_run(rounds) if @weighted_random
    wins = 0

    1.upto(rounds) do
      input = outcome = rand(2) # {0, 1}
      prediction = 0
      weight = 0 if @weighted

      debug "answer is #{outcome}"

      @agents.each do |agent|
        guess = agent.guess(input)

        if @weighted
          debug "agent #{agent} guesses #{guess} (weight #{@weights[agent]})"
          weight += @weights[agent]
          prediction += (guess == 1 ? 1 : 0) * @weights[agent]
          @weights[agent] *= @punishment if guess != outcome
        else
          debug "agent #{agent} guesses #{guess}"
          prediction += (guess == 1 ? 1 : 0)
        end
      end

      if @weighted
        debug "prediction sum: #{prediction}; total weight: #{weight}"
        prediction = prediction.to_f / weight.to_f
        debug "weighted prediction: #{prediction}"
      else
        prediction = prediction.to_f / @agents.length.to_f
      end

      correct = (prediction < 0.5 ? 0 : 1) == outcome
      debug correct ? "we win" : "we lose"

      wins += 1 if correct
      debug
    end

    wins
  end

  private

  def weighted_random_run(rounds)
    wins = 0

    1.upto(rounds) do
      input = outcome = rand(2) # {0, 1}
      prediction = 0
      guessed = false

      debug "answer is #{outcome}"
      total_weight = @weights.values.inject(0) { |sum, w| sum += w }
      debug "total weight is #{total_weight}"

      guess = 0
      @agents.each do |agent|
        guess = agent.guess(input)
        debug "agent #{agent} guesses #{guess} (weight #{@weights[agent]})"
        @weights[agent] *= @punishment if guess != outcome

        if !guessed && rand() < @weights[agent] / total_weight
          debug "agent #{agent} gets the final say"
          prediction = guess
          guessed = true
        end
      end

      if !guessed
        debug "agent #{@agents.last} gets the final say"
        prediction = guess
      end

      correct = (prediction < 0.5 ? 0 : 1) == outcome
      debug correct ? "we win" : "we lose"

      wins += 1 if correct
      guessed = false
      debug
    end

    wins
  end

  def debug(str="")
    #puts str
  end
end

agents = [Agent.new(0.8), Agent.new(0.5), Agent.new(0.5)]
normal          = Runner.new(agents, :normal)
weighted        = Runner.new(agents, :weighted, 0.5)
weighted_random = Runner.new(agents, :weighted_random, 0.5)

rounds = 3000
puts "#{rounds} rounds:"
puts "         normal: #{         normal.run(rounds)*100/rounds}%"
puts "       weighted: #{       weighted.run(rounds)*100/rounds}%"
puts "weighted random: #{weighted_random.run(rounds)*100/rounds}%"

A sample run looks like this:

3000 rounds:
         normal: 64%
       weighted: 80%
weighted random: 84%

I can't believe the random bit actually makes a difference.

Posted Oct 24, 2007, in the evening.

Comments

Click here to view the comments on this post.