AlgoVerse

وزن‌های ضربی (اکثریت وزن‌دار)

از چند «کارشناس» پیش‌بینی می‌گیرد و طبق رأی وزن‌دار آن‌ها پیش‌بینی می‌کند؛ هر کارشناسی که اشتباه کرد وزنش ضربدر (1 − ε) می‌شود. تعداد اشتباه‌ها حداکثر حدود ۲ برابر بهترین کارشناس به اضافه‌ی O(log n/ε) است.

هر روز باید چیزی را پیش‌بینی کنیم (مثلاً «فردا باران می‌آید؟»). n کارشناس هر کدام پیش‌بینی خودشان را می‌دهند و نمی‌دانیم کدام بهتر است. می‌خواهیم در طول زمان تقریباً به خوبی بهترین کارشناس عمل کنیم، بی آنکه از قبل بدانیم کیست.

ادامه‌ی توضیح ↓
ورودی:
R 10×4 · eps=50خروجی PDF

سه کارشناس در ده دور؛ کارشناس ۳ همیشه درست می‌گوید. ε = ۰٫۵: بعد از چند اشتباه اول، رأی او غالب می‌شود.

  1. def weighted_majority(R, eps):
  2. # Each row of R is one round: the experts' predictions (0 or 1), then what really happened in the last column.
  3. # eps is in hundredths: a wrong expert's weight is multiplied by 1 - eps/100.
  4. beta = 1 - eps / 100
  5. n = len(R[0]) - 1
  6. weight = [1.0] * n
  7. mistakes = 0
  8. expert_mistakes = [0] * n
  9. rows = [] # for the picture: round, our prediction, the truth, the weights after the round
  10. for t in range(len(R)):
  11. votes = R[t][:n]
  12. truth = R[t][n]
  13. one = sum(weight[i] for i in range(n) if votes[i] == 1)
  14. zero = sum(weight[i] for i in range(n) if votes[i] == 0)
  15. guess = 1 if one >= zero else 0
  16. if guess != truth:
  17. mistakes = mistakes + 1
  18. for i in range(n):
  19. if votes[i] != truth:
  20. expert_mistakes[i] = expert_mistakes[i] + 1
  21. weight[i] = round(weight[i] * beta, 4)
  22. rows.append([t + 1, guess, truth, list(weight)])
  23. best = min(expert_mistakes)
  24. return [mistakes, best]

ناوردا: وزن هر کارشناس (1 − ε)^(تعداد اشتباه‌هایش) است؛ هر بار که ما اشتباه می‌کنیم، وزن کل حداقل به اندازه‌ی ضریب (1 − ε/2) کم می‌شود.

شروع اجرا

weight—
mistakes—
expert_mistakes—

جدول هنوز خالی است.

متغیرهای محلی

eps50

نارنجی = در همین گام عوض شد

R list

[1, 1, 0, 0][1, 0, 1, 1][0, 0, 1, 1][1, 1, 0, 0][0, 1, 1, 1][1, 1, 0, 0][1, 0, 1, 1][0, 1, 0, 0][1, 1, 1, 1][1, 0, 0, 0]

Call stack

  1. weighted_majority()خط 1
گام ۱ از ۱۸۷
خط سیاه = reweigh · خط نارنجی = گام کلیدیpredict: 0/10 · wrong: 0/1 · reweigh: 0/10 · done: 0/1
    توضیح

    مسئله

    هر روز باید چیزی را پیش‌بینی کنیم (مثلاً «فردا باران می‌آید؟»). n کارشناس هر کدام پیش‌بینی خودشان را می‌دهند و نمی‌دانیم کدام بهتر است. می‌خواهیم در طول زمان تقریباً به خوبی بهترین کارشناس عمل کنیم، بی آنکه از قبل بدانیم کیست.

    الگوریتم اکثریت وزن‌دار

    همه‌ی کارشناس‌ها با وزن ۱ شروع می‌کنند. هر دور:

    1. طبق رأی وزن‌دار پیش‌بینی کن.
    2. وقتی جواب معلوم شد، وزن هر کارشناسی که اشتباه کرد را در 1 − ε ضرب کن.

    ضمانت

    اگر بهترین کارشناس m* اشتباه کند، تعداد اشتباه‌های ما حداکثر

    2(1 + ε) m* + (2 ln n) / ε

    است. هر بار که ما اشتباه می‌کنیم، حداقل نیمی از وزن کل اشتباه کرده، پس وزن کل کم می‌شود؛ ولی وزن بهترین کارشناس حداقل (1 − ε)^(m*) می‌ماند.

    همین ایده‌ی «وزن‌دهی ضربی» در بازی‌ها، برنامه‌ریزی خطی تقریبی و تقویت (boosting) هم به کار می‌رود.

    ورودی

    هر سطر R یک دور است: پیش‌بینی کارشناس‌ها (۰ یا ۱) و در ستون آخر جواب واقعی. eps به صدم است (۵۰ یعنی ۰٫۵).