مقاله توزیع عادلانه سود و هزینه در مدیریت پایگاه داده

چکیده

Attribution scores can be applied in data management to quantify the contribution of individual items to conclusions from the data, as part of the explanation of what led to these conclusions. In Artificial Intelligence, Machine Learning, and Data Management, some of the common scores are deployments of the Shapley value, a formula for profit sharing in cooperative game theory. Since its invention in the 1950s, the Shapley value has been used for contribution measurement in many fields, from economics to law, with its latest researched applications in modern machine learning. Recent studies investigated the application of the Shapley value to database management. This article gives an overview of recent results on the computational complexity of the Shapley value for measuring the contribution of tuples to query answers and to the extent of inconsistency with respect to integrity constraints. More specifically, the article highlights lower and upper bounds on the complexity of calculating the Shapley value, either exactly or approximately, as well as solutions for realizing the calculation in practice.

چکیده به فارسی (ترجمه ماشینی)

نمرات انتساب می تواند در مدیریت داده ها برای تعیین کمیت سهم موارد فردی در نتیجه گیری از داده ها ، به عنوان بخشی از توضیح آنچه منجر به این نتیجه گیری ها شد ، اعمال شود.در هوش مصنوعی ، یادگیری ماشین و مدیریت داده ها ، برخی از نمرات مشترک استقرار ارزش Shapley ، فرمول اشتراک سود در تئوری بازی تعاونی است.از زمان اختراع آن در دهه 50 ، از ارزش Shapley برای اندازه گیری مشارکت در بسیاری از زمینه ها ، از اقتصاد گرفته تا قانون ، با آخرین برنامه های تحقیق شده خود در یادگیری ماشین مدرن استفاده شده است.مطالعات اخیر کاربرد ارزش شاپلی در مدیریت بانک اطلاعاتی را مورد بررسی قرار داده است.این مقاله مروری بر نتایج اخیر در مورد پیچیدگی محاسباتی مقدار Shapley برای اندازه گیری سهم Tuples در پاسخ به پرس و جو و میزان ناسازگاری با توجه به محدودیت های یکپارچگی ارائه می دهد.به طور خاص ، این مقاله مرزهای پایین و بالایی را در پیچیدگی محاسبه مقدار Shapley ، دقیقاً یا تقریباً ، و همچنین راه حل هایی برای تحقق محاسبه در عمل برجسته می کند.