ترجمه فارسی مقاله اشکال‌زدایی داده‌ها برای طبقه‌بندی‌کننده‌های آموزش‌دیده با SGD، NP-hard است.

چکیده

Data debugging is to find a subset of the training data such that the model obtained by retraining on the subset has a better accuracy. A bunch of heuristic approaches are proposed, however, none of them are guaranteed to solve this problem effectively. This leaves an open issue whether there exists an efficient algorithm to find the subset such that the model obtained by retraining on it has a better accuracy. To answer this open question and provide theoretical basis for further study on developing better algorithms for data debugging, we investigate the computational complexity of the problem named Debuggable. Given a machine learning model $mathcal{M}$ obtained by training on dataset $D$ and a test instance $(mathbf{x}_text{test},y_text{test})$ where $mathcal{M}(mathbf{x}_text{test})neq y_text{test}$, Debuggable is to determine whether there exists a subset $D^prime$ of $D$ such that the model $mathcal{M}^prime$ obtained by retraining on $D^prime$ satisfies $mathcal{M}^prime(mathbf{x}_text{test})=y_text{test}$. To cover a wide range of commonly used models, we take SGD-trained linear classifier as the model and derive the following main results. (1) If the loss function and the dimension of the model are not fixed, Debuggable is NP-complete regardless of the training order in which all the training samples are processed during SGD. (2) For hinge-like loss functions, a comprehensive analysis on the computational complexity of Debuggable is provided; (3) If the loss function is a linear function, Debuggable can be solved in linear time, that is, data debugging can be solved easily in this case. These results not only highlight the limitations of current approaches but also offer new insights into data debugging.

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

اشکال زدایی داده ها برای یافتن زیر مجموعه ای از داده های آموزش به گونه ای است که مدل به دست آمده با بازآموزی در زیر مجموعه از دقت بهتری برخوردار است.دسته ای از رویکردهای اکتشافی ارائه شده است ، با این حال ، هیچ یک از آنها تضمین نشده اند تا این مشکل را به طور مؤثر حل کنند.این مسئله باز است که آیا یک الگوریتم کارآمد برای یافتن زیر مجموعه وجود دارد به گونه ای که مدل به دست آمده با بازآموزی روی آن دقت بهتری داشته باشد.برای پاسخ به این سؤال باز و ارائه مبنای نظری برای مطالعه بیشتر در مورد توسعه الگوریتم های بهتر برای اشکال زدایی داده ها ، ما پیچیدگی محاسباتی مسئله ای را به نام اشکال زدایی بررسی می کنیم.با توجه به یک مدل یادگیری ماشین $ mathcal {m} $ به دست آمده با آموزش در داده $ d $ و یک نمونه آزمون $ ( mathbf {x} _ text {test} ، y_ text {آزمون}) جایی که $ mathcal $ mathcal{m} ( mathbf {x} _ text {test}) neq y_ text {test} $ ، قابل اشکال این است که تعیین کنید که آیا یک زیر مجموعه $ d^ prime $ d $ وجود دارد به گونه ای که مدل $ $ $ mathcal {m}^ prime $ بدست آمده با بازآموزی در $ d^ prime $ $ mathcal {m}^ prime ( mathbf {x} _ text {test}) = y_ text {آزمون} $ را برآورده می کند.بشربرای پوشاندن طیف گسترده ای از مدلهای متداول ، طبقه بندی خطی آموزش دیده SGD را به عنوان مدل می گیریم و نتایج اصلی زیر را استخراج می کنیم.(1) اگر عملکرد از دست دادن و ابعاد مدل ثابت نباشد ، اشکال زدایی بدون توجه به ترتیب آموزشی که در آن همه نمونه های آموزش در طول SGD پردازش می شوند ، کاملاً مناسب نیست.(2) برای توابع از دست دادن مانند لولا ، تجزیه و تحلیل جامع در مورد پیچیدگی محاسباتی اشکال زدایی ارائه شده است.(3) اگر عملکرد از دست دادن یک تابع خطی باشد ، اشکال زدایی را می توان در زمان خطی حل کرد ، یعنی اشکال زدایی داده ها در این مورد به راحتی قابل حل است.این نتایج نه تنها محدودیت های رویکردهای فعلی را برجسته می کند بلکه بینش جدیدی در مورد اشکال زدایی داده ها نیز ارائه می دهد.