Strength or Accuracy: Credit Assignment in Learning Classifier Systems

سیستم‌های طبقه‌بندی‌کننده، رویکردی جذاب برای طیف وسیعی از مشکلات یادگیری ماشین، بر اساس تولید خودکار و ارزیابی قوانین شرایط/عمل است. وظایف یادگیری تقویتی آنها به طور همزمان به دو مشکل عمده یادگیری یک خط مشی و تعمیم آن (و اشیاء مرتبط مانند توابع ارزش) می پردازند. با این حال، علیرغم بیش از 20 سال تحقیق، سیستم های طبقه بندی کننده به دلایلی که اغلب نامشخص بود، با موفقیت متفاوتی روبرو شده اند. سرانجام، در سال 1995، استوارت ویلسون ادعا کرد که مدت ها در انتظار پیشرفت بود با سیستم XCS ​​خود، که از چندین جنبه با سیستم های طبقه بندی کننده قبلی متفاوت است، که مهم ترین آنها روشی است که در آن ارزش قوانین را برای استفاده توسط سیستم محاسبه می کند. سیستم تولید قانون به طور خاص، XCS (مانند اکثر سیستم‌های طبقه‌بندی‌کننده) از یک الگوریتم ژنتیک برای تولید قوانین استفاده می‌کند، و روشی که در آن تناسب قوانین را محاسبه می‌کند با سیستم‌های قبلی متفاوت است. ویلسون XCS را به عنوان یک سیستم طبقه بندی مبتنی بر دقت و سیستم های قبلی را مبتنی بر قدرت توصیف کرد. این دو با هم تفاوت دارند که در سیستم‌های مبتنی بر قدرت، تناسب یک قانون با بازدهی (پاداش/بازده) که دریافت می‌کند، متناسب است، در حالی که در XCS تابعی از دقت پیش‌بینی بازده است. بنابراین تفاوت مربوط به تخصیص اعتبار است، یعنی اینکه چگونه سهم یک قانون در عملکرد سیستم تخمین زده می شود. XCS یک سیستم یادگیری Q است. در واقع، این یک تعمیم مناسب از یادگیری Q جدولی است که در آن قوانین حالت ها و اقدامات را جمع می کند. در XCS، مانند سایر یادگیرندگان Q، Q-values ​​برای انتخاب وزنه استفاده می شود.

Classifier systems are an intriguing approach to a broad range of machine learning problems, based on automated generation and evaluation of condi­ tion/action rules. Inreinforcement learning tasks they simultaneously address the two major problems of learning a policy and generalising over it (and re­ lated objects, such as value functions). Despite over 20 years of research, however, classifier systems have met with mixed success, for reasons which were often unclear. Finally, in 1995 Stewart Wilson claimed a long-awaited breakthrough with his XCS system, which differs from earlier classifier sys­ tems in a number of respects, the most significant of which is the way in which it calculates the value of rules for use by the rule generation system. Specifically, XCS (like most classifiersystems) employs a genetic algorithm for rule generation, and the way in whichit calculates rule fitness differsfrom earlier systems. Wilson described XCS as an accuracy-based classifiersystem and earlier systems as strength-based. The two differin that in strength-based systems the fitness of a rule is proportional to the return (reward/payoff) it receives, whereas in XCS it is a function of the accuracy with which return is predicted. The difference is thus one of credit assignment, that is, of how a rule's contribution to the system's performance is estimated. XCS is a Q­ learning system; in fact, it is a proper generalisation of tabular Q-learning, in which rules aggregate states and actions. In XCS, as in other Q-learners, Q-valuesare used to weightaction selection.