فهرست مقاله
ممکن است بالاترین نتایج جست‌وجو به پرسش مربوط باشند، اما تقریباً یک مطلب را تکرار کنند. برای انتخاب نتیجهٔ بعدی، گاهی لازم است هم ارتباط با پرسش و هم شباهت به نتایجِ از قبل انتخاب‌شده را ببینیم. این درس الگوریتم حریصانهٔ MMR را روی چهار شناسه و امتیازهای دست‌نویس اجرا می‌کند؛ سند واقعی، مدل برداری و سنجش کیفیت کاربران در مثال حضور ندارند.
۱. ارتباط با پرسش را از تکرار نتایج جدا کنیم
دو ورودی عددی متفاوت داریم: امتیاز ارتباط هر نامزد با پرسش، و جدول شباهت هر دو نامزد به یکدیگر. خوب‌بودن امتیاز اول، مقدار دوم را تعیین نمی‌کند. دو سند می‌توانند هر دو امتیاز ارتباط بالا داشته باشند و در عین حال بسیار به هم شبیه باشند؛ حذف یکی از آن‌ها هم بدون شناخت نیاز کاربر، الزاماً تصمیم بهتری نیست.
گلدشتاین و کربونل در مقالهٔ TIPSTER سال ۱۹۹۸، این ترکیب ارتباط و تازگی نسبت به انتخاب‌های قبلی را صورت‌بندی کرده‌اند. ما فرمول بخش دوم مقاله را برای یک مثال مستقل استفاده می‌کنیم؛ نتایج تجربی آن پژوهش را به دادهٔ ساختگی خودمان یا موتور جست‌وجوی شرکت نسبت نمی‌دهیم. این منبع تاریخی، خبر تازه نیست.
اگر ارتباط از روشی مانند وزن‌دهی BM25 بیاید، مرحلهٔ حاضر همچنان به تعریف مستقلِ شباهت میان نامزدها نیاز دارد. خروجی ما خودِ بازیابی نیست؛ فقط ترتیبِ یک پنجرهٔ از پیش داده‌شده را عوض می‌کند. سندی که در پنجره نیست، با تغییر ضریب تعادل از هیچ ظاهر نمی‌شود.
۲. امتیاز حاشیه‌ای را پس از هر انتخاب تازه کنیم
در هر گام، امتیاز ارتباط را در لامبدا ضرب می‌کنیم و جریمهٔ تکرار را کم می‌کنیم: یک منهای لامبدا، ضرب در بیشترین شباهتِ نامزد به مجموعهٔ انتخاب‌شده. شکل کوتاه آن lambda*q - (1-lambda)*max_similarity است. جریمه بر اساس بیشینه است، نه میانگین شباهت‌ها؛ وجود یک نتیجهٔ بسیار شبیه می‌تواند مؤثر باشد.
پس از اضافه‌شدن هر نتیجه، مجموعهٔ انتخاب‌شده تغییر می‌کند و امتیاز نامزدهای باقی‌مانده باید دوباره حساب شود. مرتب‌کردن یک‌باره بر اساس جریمه نسبت به فقط نتیجهٔ اول، همان الگوریتم نیست. تصمیم هر مرحله به مسیر انتخاب‌های قبلی وابسته است؛ این تفاوتِ اصلی با یک امتیاز ثابت برای هر سند است.
برای اولین نتیجه هنوز مجموعهٔ قبلی نداریم و بیشینه روی آن را خودکار عددی فرض نمی‌کنیم. سیاست صریحِ نمونه این است که ابتدا بیشترین امتیاز ارتباط انتخاب شود، حتی وقتی لامبدا صفر است. از گام دوم فرمول اجرا می‌شود. در تساوی، شناسهٔ واژگانی کوچک‌تر برنده است؛ ترتیب تصادفیِ ورود نامزدها تصمیم را عوض نمی‌کند.
۳. ضریب تعادل و تساوی امتیاز را صریح تعیین کنیم
لامبدا از صفر تا یک است. یک، جریمه را حذف و ترتیب ارتباط را بازسازی می‌کند؛ صفر، پس از همان انتخاب اولیهٔ قراردادی، فقط شباهت به انتخاب‌های قبلی را جریمه می‌کند. این حالت می‌تواند سند کم‌ارتباط‌تر را زودتر بیاورد. «متفاوت‌تر» را نباید بی‌دلیل «درست‌تر»، «مرتبط‌تر» یا «پاسخ بهتر» ترجمه کرد.
برای نمونه، همهٔ امتیازها بین صفر و یک، بی‌واحد و دقیقاً کسری‌اند. جدول شباهتِ خودمان متقارن و قطر آن یک است؛ این محدودیتِ پروفایل آموزشی است. نه برداری ساخته‌ایم و نه ثابت کرده‌ایم جدول، ماتریس کسینوسیِ یک فضای برداری معتبر است. محاسبهٔ کسینوس سندها مرحله‌ای جداست و نباید خروجی ساختگی اینجا را اندازه‌گیری آن نامید.
حداکثر هشت شناسهٔ یکتا می‌پذیریم و تعداد خروجی از صفر تا تعداد نامزدهاست. اگر امتیاز حاشیه‌ای منفی شود، باز هم تا تعداد خواسته‌شده انتخاب می‌کنیم؛ شرط توقفِ کیفیت تعریف نشده است. پس منفی بودن به معنی احتمال منفی یا خرابی محاسبه نیست، بلکه نتیجهٔ تفاضل دو مؤلفه در همین قرارداد است.
۴. کد و جدول دستی را با مرجع مستقل بسنجیم
فایل mmr_diversity.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. Fraction حساب کسری را نگه می‌دارد تا تساوی به گردکردنِ شناور وابسته نباشد. عدد صحیح یا کسرِ واقعی پذیرفته می‌شود؛ مقدار شناور و bool رد می‌شوند. مخرج کسر هم حداکثر ده‌هزار است؛ این قید برای مثال محدود ماست.
"""Original exact-score greedy MMR teaching example; no embeddings or model."""
from fractions import Fraction
from itertools import combinations, permutations
import copy
import json
import platform
import re
def unit_fraction(value):
if type(value) not in {int, Fraction}:
raise ValueError('actual int/Fraction required, not float/bool')
value = Fraction(value)
if not 0 <= value <= 1 or value.denominator > 10000:
raise ValueError('score outside bounded unit interval')
return value
def rerank(candidates, query_scores, similarity, *, weight=Fraction(1, 2), k=3):
if type(candidates) is not list or len(candidates) > 8:
raise ValueError('at most eight explicit candidate IDs')
if any(type(i) is not str or not re.fullmatch(r'[A-Za-z][A-Za-z0-9_]{0,15}', i) for i in candidates):
raise ValueError('invalid candidate ID')
if len(set(candidates)) != len(candidates):
raise ValueError('duplicate candidate ID')
if type(k) is not int or not 0 <= k <= len(candidates):
raise ValueError('k must lie within candidate count')
weight = unit_fraction(weight)
ids = set(candidates)
if type(query_scores) is not dict or set(query_scores) != ids:
raise ValueError('exact query-score coverage required')
q = {i: unit_fraction(query_scores[i]) for i in candidates}
if type(similarity) is not dict or set(similarity) != ids:
raise ValueError('exact similarity rows required')
matrix = {}
for i in candidates:
if type(similarity[i]) is not dict or set(similarity[i]) != ids:
raise ValueError('exact matrix coverage required')
matrix[i] = {j: unit_fraction(similarity[i][j]) for j in candidates}
if any(matrix[i][i] != 1 or matrix[i][j] != matrix[j][i] for i in candidates for j in candidates):
raise ValueError('own matrix profile requires unit diagonal and symmetry')
selected = []
trace = []
if k:
# Own explicit seed policy, including weight=0; max over empty S undefined.
first = min(candidates, key=lambda i: (-q[i], i))
selected.append(first)
trace.append({'picked': first, 'criterion': 'seed_query_score', 'score': str(q[first]),
'max_similarity_to_selected': None, 'selected_before': []})
while len(selected) < k:
values = {}
for i in candidates:
if i not in selected:
penalty = max(matrix[i][j] for j in selected)
values[i] = (weight * q[i] - (1 - weight) * penalty, penalty)
picked = min(values, key=lambda i: (-values[i][0], i))
score, penalty = values[picked]
trace.append({'picked': picked, 'criterion': 'mmr', 'score': str(score),
'max_similarity_to_selected': str(penalty), 'selected_before': selected.copy()})
selected.append(picked)
return {'selected': selected, 'trace': trace}
QUERY20 = {'A': 18, 'B': 17, 'C': 14, 'D': 8}
SIM20 = {'A': {'A': 20, 'B': 19, 'C': 2, 'D': 4},
'B': {'A': 19, 'B': 20, 'C': 3, 'D': 5},
'C': {'A': 2, 'B': 3, 'C': 20, 'D': 12},
'D': {'A': 4, 'B': 5, 'C': 12, 'D': 20}}
def fixture(ids):
return ({i: Fraction(QUERY20[i], 20) for i in ids},
{i: {j: Fraction(SIM20[i][j], 20) for j in ids} for i in ids})
def integer_permutation_oracle(ids, weight, k):
if not ids or not k:
return []
a, b = weight.numerator, weight.denominator
acceptable = []
for order in permutations(ids):
valid = all(QUERY20[order[0]] > QUERY20[j] or
(QUERY20[order[0]] == QUERY20[j] and order[0] <= j) for j in ids)
for step in range(1, len(order)):
before = order[:step]
gains = {i: a * QUERY20[i] - (b - a) * max(SIM20[i][j] for j in before) for i in order[step:]}
winner = order[step]
valid = valid and all(gains[winner] > gains[j] or
(gains[winner] == gains[j] and winner <= j) for j in gains)
if valid:
acceptable.append(list(order[:k]))
assert len(acceptable) == 1
return acceptable[0]
def rejects(fn):
try:
fn()
except ValueError:
return True
return False
def run_example():
ids = ['A', 'B', 'C', 'D'];q, matrix = fixture(ids)
before = copy.deepcopy((ids, q, matrix))
answer = rerank(ids, q, matrix, k=4)
bad_symmetric = copy.deepcopy(matrix);bad_symmetric['A']['B'] = Fraction(1, 2)
bad_diagonal = copy.deepcopy(matrix);bad_diagonal['A']['A'] = Fraction(1, 2)
bad_coverage = copy.deepcopy(matrix);del bad_coverage['A']['B']
tie_ids = ['B', 'A'];tie_q = {'A': Fraction(1, 2), 'B': Fraction(1, 2)}
tie_matrix = {'A': {'A': 1, 'B': 0}, 'B': {'A': 0, 'B': 1}}
oracle = []
for length in range(5):
for subset in combinations(ids, length):
window = list(subset);qs, ms = fixture(window)
for weight in [Fraction(0), Fraction(1, 4), Fraction(1, 2), Fraction(3, 4), Fraction(1)]:
for k in range(length + 1):
oracle.append(rerank(window, qs, ms, weight=weight, k=k)['selected'] == integer_permutation_oracle(window, weight, k))
checks = {
'literal_half_weight_hand_order': answer['selected'] == ['A', 'C', 'B', 'D'],
'literal_half_weight_step_scores': [x['score'] for x in answer['trace']] == ['9/10', '3/10', '-1/20', '-1/10'],
'penalty_recomputed_after_each_selection': answer['trace'][3]['max_similarity_to_selected'] == '3/5' and answer['trace'][3]['selected_before'] == ['A', 'C', 'B'],
'weight_one_is_query_order': rerank(ids, q, matrix, weight=1, k=4)['selected'] == ['A', 'B', 'C', 'D'],
'weight_zero_has_explicit_query_seed_then_diversity': rerank(ids, q, matrix, weight=0, k=4)['selected'] == ['A', 'C', 'D', 'B'],
'exact_ties_use_id_not_input_order': rerank(tie_ids, tie_q, tie_matrix, k=2)['selected'] == ['A', 'B'],
'input_permutation_does_not_change_result': all(rerank(list(order), q, matrix, k=4) == answer for order in permutations(ids)),
'candidate_window_cannot_recover_absent_document': rerank(['A', 'B'], *fixture(['A', 'B']), k=2)['selected'] == ['A', 'B'],
'empty_zero_and_singleton_boundaries': rerank([], {}, {}, k=0) == {'selected': [], 'trace': []} and rerank(ids, q, matrix, k=0)['selected'] == [] and rerank(['A'], *fixture(['A']), k=1)['selected'] == ['A'],
'duplicate_identifier_and_candidate_type_contract': all(rejects(fn) for fn in [lambda: rerank(['A', 'A'], q, matrix, k=1), lambda: rerank(('A',), {}, {}, k=0), lambda: rerank(['A B'], {}, {}, k=0)]),
'k_and_weight_strict_bounds': all(rejects(fn) for fn in [lambda: rerank(ids, q, matrix, k=True), lambda: rerank(ids, q, matrix, k=5), lambda: rerank(ids, q, matrix, k=-1), lambda: rerank(ids, q, matrix, weight=True), lambda: rerank(ids, q, matrix, weight=0.5), lambda: rerank(ids, q, matrix, weight=Fraction(2))]),
'matrix_symmetry_diagonal_and_coverage': all(rejects(lambda m=m: rerank(ids, q, m)) for m in [bad_symmetric, bad_diagonal, bad_coverage]),
'query_score_types_unit_interval_and_fraction_bound': all(rejects(lambda x=x: rerank(ids, {**q, 'A': x}, matrix)) for x in [True, 0.9, Fraction(-1, 2), Fraction(3, 2), Fraction(1, 10001)]),
'negative_marginal_score_is_not_clamped_or_stopped': len(answer['selected']) == 4 and answer['trace'][2]['score'] == '-1/20',
'independent_integer_permutation_reference': all(oracle),
'all_inputs_preserved_and_selected_unique': (ids, q, matrix) == before and len(set(answer['selected'])) == 4,
}
assert all(type(x) is bool and x for x in checks.values()), checks
return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
'example_kind': 'Original synthetic bounded unit-score MMR profile; no embedding, model or relevance benchmark',
'half_weight_result': answer,
'query_scores': {i: str(q[i]) for i in ids},
'pairwise_similarity': {i: {j: str(matrix[i][j]) for j in ids} for i in ids},
'independent_window_weight_k_cases_inside_one_group': len(oracle), 'checks': checks}
if __name__ == '__main__':
print(json.dumps(run_example(), ensure_ascii=False, indent=2))
امتیاز پرسش برای A,B,C,D به‌ترتیب 18/20,17/20,14/20,8/20 است. شباهت A-B نوزده‌بیستم و A-C یک‌دهم است. با لامبدای یک‌دوم، پس از انتخاب اولیهٔ A، امتیازهای حاشیه‌ای سه نامزد به‌ترتیب -1/20,3/10,1/10 می‌شوند؛ بنابراین C دوم است.
پس از این انتخاب، بیشترین شباهت D به مجموعه، سه‌پنجم می‌شود و امتیازش منفی یک‌دهم است؛ B با منفی یک‌بیستم جلوتر می‌ماند. ترتیب کامل A,C,B,D است. ردیف اول trace با برچسب انتخاب اولیه و امتیاز پرسش ثبت شده، نه با ادعای ارزیابی فرمول برای مجموعهٔ تهی.
شانزده گروه بررسی داریم. مرجع مستقل همهٔ جایگشت‌های ممکن را می‌سازد و با نامساوی‌های صحیحِ مقیاس بیست، ترتیب‌های سازگار با انتخاب حریصانه را پیدا می‌کند؛ تابع کسری اصلی را صدا نمی‌زند. شانزده پنجرهٔ نامزد، پنج ضریب و تعدادهای خروجیِ معتبر، ۲۴۰ مقایسه در یک گروه می‌سازند؛ جواب دستیِ نمونه نیز جداست.
۵. تنوع الگوریتمی را به کیفیت واقعی تعمیم ندهیم
حریصانه بودن یعنی در هر مرحله با انتخاب‌های فعلی تصمیم می‌گیریم؛ ادعای بهترین زیرمجموعهٔ سراسری نداریم. همسانیِ دامنهٔ عددیِ دو نوع امتیاز نیز کالیبراسیون آن‌ها را ثابت نمی‌کند. انتخاب لامبدا برای کاربرد واقعی به دادهٔ ارتباط، تعریف تکرار و نیاز کاربر وابسته است؛ این مثال بهترین مقدار را کشف نکرده است.
{
"python": "3.14.5",
"dependencies": "Python standard library only",
"example_kind": "Original synthetic bounded unit-score MMR profile; no embedding, model or relevance benchmark",
"half_weight_result": {
"selected": [
"A",
"C",
"B",
"D"
],
"trace": [
{
"picked": "A",
"criterion": "seed_query_score",
"score": "9/10",
"max_similarity_to_selected": null,
"selected_before": []
},
{
"picked": "C",
"criterion": "mmr",
"score": "3/10",
"max_similarity_to_selected": "1/10",
"selected_before": [
"A"
]
},
{
"picked": "B",
"criterion": "mmr",
"score": "-1/20",
"max_similarity_to_selected": "19/20",
"selected_before": [
"A",
"C"
]
},
{
"picked": "D",
"criterion": "mmr",
"score": "-1/10",
"max_similarity_to_selected": "3/5",
"selected_before": [
"A",
"C",
"B"
]
}
]
},
"query_scores": {
"A": "9/10",
"B": "17/20",
"C": "7/10",
"D": "2/5"
},
"pairwise_similarity": {
"A": {
"A": "1",
"B": "19/20",
"C": "1/10",
"D": "1/5"
},
"B": {
"A": "19/20",
"B": "1",
"C": "3/20",
"D": "1/4"
},
"C": {
"A": "1/10",
"B": "3/20",
"C": "1",
"D": "3/5"
},
"D": {
"A": "1/5",
"B": "1/4",
"C": "3/5",
"D": "1"
}
},
"independent_window_weight_k_cases_inside_one_group": 240,
"checks": {
"literal_half_weight_hand_order": true,
"literal_half_weight_step_scores": true,
"penalty_recomputed_after_each_selection": true,
"weight_one_is_query_order": true,
"weight_zero_has_explicit_query_seed_then_diversity": true,
"exact_ties_use_id_not_input_order": true,
"input_permutation_does_not_change_result": true,
"candidate_window_cannot_recover_absent_document": true,
"empty_zero_and_singleton_boundaries": true,
"duplicate_identifier_and_candidate_type_contract": true,
"k_and_weight_strict_bounds": true,
"matrix_symmetry_diagonal_and_coverage": true,
"query_score_types_unit_interval_and_fraction_bound": true,
"negative_marginal_score_is_not_clamped_or_stopped": true,
"independent_integer_permutation_reference": true,
"all_inputs_preserved_and_selected_unique": true
}
}کلیدهای نمره و ماتریس باید دقیقاً پنجره را پوشش دهند؛ قطر، تقارن، نوع و حدود بررسی می‌شوند. این بررسی‌ها کیفیت متن یا امنیت منبع را تأیید نمی‌کنند. منابع در ۲۵ مهر ۱۴۰۵ خوانده شدند؛ مقالهٔ مورد استناد مربوط به اکتبر ۱۹۹۸، مستندات 3.14.8 و اجرای محلی 3.14.5 جدا ثبت شده‌اند. هیچ مدل، شبکه یا رابط پولی فراخوانی نشده است.
پرسش اول: چرا نتیجهٔ دوم با ارتباط کمتر جلو آمد؟ پاسخ: جریمهٔ شباهت آن به انتخاب اول کوچک‌تر بود؛ این حاصلِ امتیازهای فرضی است، نه اثبات برتری محتوای سند.
پرسش دوم: لامبدای یک چه می‌دهد؟ پاسخ: ترتیب ارتباط A,B,C,D؛ مؤلفهٔ جریمه صفر می‌شود.
پرسش سوم: لامبدای صفر، اولین سند را چگونه می‌گیرد؟ پاسخ: طبق سیاست مستقلِ همین مثال از ارتباط، سپس ترتیب C,D,B بر اساس جریمه ادامه پیدا می‌کند.
پرسش چهارم: پنجرهٔ فقط A,B می‌تواند C بسازد؟ پاسخ: خیر؛ بازرتبه‌بندی بازیابیِ نامزد غایب نیست. بزرگ‌کردن تعداد خروجی هم این محدودیت را حل نمی‌کند.
منابع و مطالعهٔ بیشتر
بررسی منابع: ۲۵ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
