טיוטה:לימוד מערכת מסווגת
לימוד מערכות מסווגות, או LCS, הם פרדיגמה של שיטות לימוד מכונה המבוססות על כללים משלבים: מרכיב גילוי (בדרך כלל למשל אלגוריתם גנטי) עם מרכיב למידה (ביצוע או למידה בפיקוח, למידת חיזוק, או למידה ללא השגחה). לימוד מערכות מסווגות מתבקשות לזהות מערכת של כללים תלויים עם קשר קולקטיבי לאחסן וליישם את הידע באופן מקטעין כדי לבצע תחזיות (דוגמנות התנהגות למשל, סיווג, כריית נתונים, רגרסיה, קירוב פונקציה, או אסטרטגיית משחק). גישה זו מאפשרת רווחי פתרונות מורכבים על ידי פירוק החלקים לקטנים ופשוטים. המושגים המייסדים מאחורי מערכות מסווגות למידה באים מניסיונות מודל מורכבות של מערכות מסתגלות, באמצעות כללים אלו ניתן ליצור מערכת קוגניטיבית מלאכותית (למשל בינה מלאכותית).
מתודולוגיה[עריכת קוד מקור | עריכה]
הארכיטקטורה וצמתי מערכת למידה מסווגת יכולים להיות נתונים לשינוי. כדאי לחשוב על LCS כמכונה המורכבת ממספר רכיבי אינטראקציה. כל רכיב ניתן להוסיף או להסיר, או רכיבים הקיימים והשונים / החליפו כדי להתאימה לדרישות של תחום הבעיה הנתונה (כמו אובניים לבניין אלגוריתמי) או בכדי להפוך את האלגוריתם מספיק גמיש כדי לתפקד בתחומי בעיה שונים. כתוצאה מכך, הפרדיגמה LCS ניתן ליישם בגמישות תחומי בעיה רבים הנקראים למידת מכונה. על יחידת הזמן הגדולה בין הטמעות LCS הן כדלקמן: (1) אדריכלות מישיגן בסגנון לעומת האדריכלות בסגנון פיטסבורג, (2) חיזוק לימוד לעומת למידה בפיקוח, (3) למידה מצטברת לעומת למידה באצווה, (4) למידה מקוונת נגד לימוד מקוון, (5) כושר מבוסס כוח לעומת כושר מבוסס דיוק, (6) מיפוי פעולה מלאה לעומת מיפוי פעולה הטובה ביותר. חטיבות אלו אינן בהכרח סותרות זה את זה. לדוגמה, XCS,, הידוע ביותר כאלגוריתם LCS למידה הכי הטוב, הוא בסגנון מישיגן, נועד לחיזוק למידה וגם יכול לבצע למידה בפיקוח. למידה מצטברת שיכולה להיות באופן מקוון או לא מקוון, כושר מבוסס דיוק, ומבקש ליצור מיפוי פעולה מלא. אלמנטים של אלגוריתם LCS הגנרית צעד חכם סכמטי המדגים מחזור למידת מערכת מסווגתאת הלמידה הגנרית בסגנון מישיגן לביצוע למידה בפיקוח. יש לזכור כי LCS היא פרדיגמה עבור מכונה גנטית המבוססת למידה ולא מעשה מסוים, את הדברים הבאים מתארים היבטים מרכזיים של האלגוריתם LCS גנריות, מודרני (כלומר שלאחר XCS). לשם הפשטות הבה נתמקד באדריכלות בסגנון מישיגן עם למידה בפיקוח. ראה איורים מימין, את הצעדים שסדרו בסוג כזה של LCS גנריות.
סביבה[עריכת קוד מקור | עריכה]
הסביבה היא מקור הנתונים שעליו LCS לומד. זה יכול להיות מחובר במערך הדרכה סופי (מאפיין של בעיית כריית נתונים, מיון, או רגרסיה), או זרם רציף מקוון של מקרי אימון חיים. למשל, כל אימון יכול להוות הנחה ולכלול מספר תכונות (המכונה גם תכונות, או משתנה בלתי תלוי), ואת עמדת קצה של עניין (המכונה גם בכיתה, פעולה, פנוטיפ, חיזוי, או משתנה תלוי). חלק מלמידת LCS יכול להיות כרוך בבחירת תכונה, ולכן לא כל התכונות של נתוני אימון צריכים להיות אינפורמטיבי. הסט של ערכי תכונה של מופע המכונה כמדינה. לשם הפשטות נניח תחום הבעיה למשל עם תכונות בוליאני / בינארית בכיתה בוליאני / בינארי. עבור מערכות בסגנון מישיגן, למשל אחד מהסביבה מאומנת על כל מחזור למידה (למשל למידה מצטברת). מערכות בסגנון פיטסבורג מסוגלת לבצע למידה באצווה, שם-כלל קובע מוערכים כל איטרציה על הרבה או כל נתוני האימון.
כלל / מסווג / אוכלוסייה[עריכת קוד מקור | עריכה]
כלל הוא יחסי תלות בהקשר בין ערכי מדינה ורמת החיזוי. חוקים בדרך כלל לבושים בצורה של {IF: אז} ביטוי, (למשל {אם 'מצב' ועל 'פעולה'}, או כמו דוגמה ספציפית יותר, {IF 'אדום' AND 'מתומן' ועל 'להפסיק לחתום'} ). מושג קריטי LCS ומכונת שלטון המבוסס על למידה כאחד, הוא כי שום פרט אינו כשלעצמו מודל, מאחר שהכלל הוא ישים רק כאשר מצבו הוא מרוצה. תחשוב כלל בתור "מודל מקומי" של מרחב הפתרון. כללים יכולים להיות מיוצגים בכמה דרכים שונות, כדי להתמודד עם סוגים שונים של נתונים (למשל בינארי, דיסקרטי מוערך, סודר, רציף מוערך). נתונים בינאריים בהתחשב LCS מסורתית חלה ייצוג כלל משולש (כללים למשל יכולים לכלול או 0, 1, או '#' עבור כל תכונה בנתונים). ה 'לא אכפת לי' הסמל ( '#' למשל) משמש ככרטיס פראי בתוך הכללים המאפשרים במצבו של הכלל, ועל המערכת כולה להכליל יחסים בין תכונות ונקודת סיום היעד בכדי לחזות. קחו למשל את הכלל הבא (# 1 ### 0 ~ 1) (תנאי למשל ~ פעולה). כלל זה יכול להתפרש: אם התכונה השנייה = 1 והתכונה השישית = 0 אזי חיזוי class = 1. הייתי אומר כי התכונות השניות ושישיות פורטו בכלל זה, בעוד האחרים היו כלולים. כלל זה, והתחזית המקבילה חלה רק למופע כאשר התנאי של הכלל הוא מרוצה בערכאה. או נקרא בשמו הנפוץ - התאמה. ב LCS בסגנון מישיגן, לכל כלל יש כושר משלו, כמו גם מספר פרמטרי הקשורים אליו שיכול לתאר את מספר העותקים של אותה הממלכה קיימת (כלומר, כמות מרובה), גיל הכלל, הדיוק שלה, או הדיוק של תחזיות השכר, סטטיסטיקת תאוריה או תאוריה חווייתית אחרת. הכלל עם יחד הפרמטרים שלו מכונה לעיתים קרובות בתור 'מסווג'. במערכות בסגנון מישיגן, מסווגות, נמצאים בתוך אוכלוסייה של מספר מרובים המוגדרים על ידי משתמש של מסווגים. בניגוד לרוב אלגוריתם חיפוש סטוכסטיים (למשל אלגוריתמים אבולוציוניים), אוכלוסיות LCS יכולה לצאת לדרך ריקה (כלומר אין צורך לאתחל אוכלוסייה כלל באופן אקראי). מסווגים במקום יושקו בתחילה לאוכלוסייה עם מנגנון כיסוי. בכל LCS, המודל המאומן הוא סט של כללים / מסווגים, ולא לכל כלל / מסווג יחיד. ב LCS בסגנון מישיגן, כולו מאומן (ובאופן אופציונאלי, דחוסה) אוכלוסייה מסווגת מהווה את מודל החיזוי.
התאמה[עריכת קוד מקור | עריכה]
אחד המרכיבים הקריטיים ביותר המתרחש לעיתים קרובות הוא הזמן רב של LCS הוא בתהליך ההתאמה. הצעד הראשון במחזור למידת LCS לוקח מופע אימון יחיד מהסביבה ומעביר אותו [P] שם התאמה מתרחשת. בשלב שני, כל כלל [P] כעת בהשוואה למופע ההכשרה לראות אילו כללי משחק (למשל, האם רלוונטיים להיקשר למופע הנוכחי). בשלב שלישי, כל הכללים בהתאמה מועברים סט משחק [M]. כלל תואם את מופעה האימונים אם כל ערכי התכונה שצוינו במצב השלטון שקולה לערך התכונה המקבילה בערכאת האימון. לדוגמה, בהנחה למשל האימון הוא (001,001 ~ 0), כללים אלה יתאימו: (### 0 ## ~ 0), (00### 1 ~ 0), (# 01,001 ~ 1), ובלבד שכללים אלו לא יהיו (1 ##### ~ 0), (000 ## 1 ~ 0), (# 0 # 1 # 0 ~ 1). שים לב להתאמה, פעולת הסיום / שצוינה על ידי הכלל אינה נלקחת בחשבון. כתוצאה מכך, מערך המשחק עשוי להכיל מסווגים המציעים פעולות סותרות. בשלב הרביעי, מאז אנו מבצעים למידה בפיקוח, [ז] מחולק סט נכון [C] וסט שגוי [I]. כלל התאמה נכנס לסט הנכון אם היא מציעה את הפעולה הנכונה (מבוססת על הפעולה הידועה של המופע הכשר), אחר זה נכנס [I]. בלימוד LCS חיזוק, סט פעולה [A] היה להיווצר כאן במקום, מאז הפעולה הנכונה אינה ידועה.
הערות שוליים[עריכת קוד מקור | עריכה]
1. Stalph, Patrick O.; Butz, Martin V. (2010-02-01). "JavaXCSF: The XCSF Learning Classifier System in Java". SIGEVOlution. 4 (3): 16–19. doi:10.1145/1731888.1731890. ISSN 1931-8499. 2. Urbanowicz, Ryan J.; Moore, Jason H. (2009-09-22). "Learning Classifier Systems: A Complete Introduction, Review, and Roadmap". Journal of Artificial Evolution and Applications. 2009: 1–25. doi:10.1155/2009/736398. ISSN 1687-6229.
3. Dorigo, Marco. "Alecsys and the AutonoMouse: Learning to control a real robot by distributed classifier systems". Machine Learning. 19 (3): 209–240. doi:10.1007/BF00996270. ISSN 0885-6125.
4. Bernadó-Mansilla, Ester; Garrell-Guiu, Josep M. (2003-09-01). "Accuracy-Based Learning Classifier Systems: Models, Analysis and Applications to Classification Tasks". Evolutionary Computation. 11 (3): 209–238. doi:10.1162/106365603322365289. ISSN 1063-6560.
5. Urbanowicz, Ryan J.; Moore, Jason H. (2015-04-03). "ExSTraCS 2.0: description and evaluation of a scalable learning classifier system". Evolutionary Intelligence. 8 (2-3): 89–116. doi:10.1007/s12065-015-0128-8. ISSN 1864-5909. PMC 4583133. PMID 26417393.
6. Bernadó, Ester; Llorà, Xavier; Garrell, Josep M. (2001-07-07). Lanzi, Pier Luca; Stolzmann, Wolfgang; Wilson, Stewart W., eds. Advances in Learning Classifier Systems. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 115–132. doi:10.1007/3-540-48104-4_8. ISBN 9783540437932.
7. Bacardit, Jaume; Butz, Martin V. (2007-01-01). Kovacs, Tim; Llorà, Xavier; Takadama, Keiki; Lanzi, Pier Luca; Stolzmann, Wolfgang; Wilson, Stewart W., eds. Learning Classifier Systems. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 282–290. doi:10.1007/978-3-540-71231-2_19. ISBN 9783540712305.
8. Urbanowicz, Ryan; Ramanand, Niranjan; Moore, Jason (2015-01-01). "Continuous Endpoint Data Mining with ExSTraCS: A Supervised Learning Classifier System". Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. GECCO Companion '15. New York, NY, USA: ACM: 1029–1036. doi:10.1145/2739482.2768453. ISBN 9781450334884.
9. Butz, M. V.; Lanzi, P. L.; Wilson, S. W. (2008-06-01). "Function Approximation With XCS: Hyperellipsoidal Conditions, Recursive Least Squares, and Compaction". IEEE Transactions on Evolutionary Computation. 12 (3): 355–376. doi:10.1109/TEVC.2007.903551. ISSN 1089-778X.
10. Wilson, Stewart W. (1995-06-01). "Classifier Fitness Based on Accuracy". Evol. Comput. 3 (2): 149–175. doi:10.1162/evco.1995.3.2.149. ISSN 1063-6560.
11. Urbanowicz, R. J.; Granizo-Mackenzie, A.; Moore, J. H. (2012-11-01). "An analysis pipeline with statistical and visualization-guided knowledge discovery for Michigan-style learning classifier systems". IEEE Computational Intelligence Magazine. 7 (4): 35–45. doi:10.1109/MCI.2012.2215124. ISSN 1556-603X. PMC 4244006. PMID 25431544.
12. Bacardit, Jaume; Llorà, Xavier (2013). "Large‐scale data mining using genetics‐based machine learning". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 3 (1): 37–61. doi:10.1002/widm.1078.
13. Holland, John (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Michigan Press.
14. Holland JH (1976) Adaptation. In: Rosen R, Snell F (eds) Progress in theoretical biology, vol 4. Academic Press, New York, pp 263–293
15. Holland JH, Reitman JS (1978) Cognitive systems based on adaptive algorithms Reprinted in: Evolutionary computation. The fossil record. In: David BF (ed) IEEE Press, New York 1998. ISBN 0-7803-3481-7
16. Lanzi, Pier Luca (2008-02-08). "Learning classifier systems: then and now". Evolutionary Intelligence. 1 (1): 63–82. doi:10.1007/s12065-007-0003-3. ISSN 1864-5909.
17. Smith S (1980) A learning system based on genetic adaptive algorithms. Ph.D. thesis, Department of Computer Science, University of Pittsburgh
18. Smith S (1983) Flexible learning of problem solving heuristics through adaptive search. In: Eighth international joint conference on articial intelligence. Morgan Kaufmann, Los Altos, pp 421–425
19. De Jong KA (1988) Learning with genetic algorithms: an overview. Mach Learn 3:121–138
20. Holland, John H. "Escaping brittleness: the possibilities of general purpose learning algorithms applied to parallel rule-based system." Machine learning(1986): 593-623.
21. Holland, John H. (1985-01-01). "Properties of the Bucket Brigade". Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale, NJ, USA: L. Erlbaum Associates Inc.: 1–7. ISBN 0805804269.
22. Booker, L (1982-01-01). Intelligent Behavior as a Adaptation to the Task Environment (Thesis). University of Michigan.
23. Wilson, S. W. "Knowledge growth in an artificial animal. Proceedings of the First International Conference on Genetic Algorithms and their Applications." (1985).
24. Wilson, Stewart W. "Classifier systems and the animat problem". Machine Learning. 2 (3): 199–228. doi:10.1007/BF00058679. ISSN 0885-6125.
25. Bonelli, Pierre; Parodi, Alexandre; Sen, Sandip; Wilson, Stewart (1990-01-01). "NEWBOOLE: A Fast GBML System". Proceedings of the Seventh International Conference (1990) on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.: 153–159. ISBN 1558601414.
26. Frey, Peter W.; Slate, David J. "Letter recognition using Holland-style adaptive classifiers". Machine Learning. 6 (2): 161–182. doi:10.1007/BF00114162. ISSN 0885-6125.
27. Valenzuela-Rendón, Manuel. "The Fuzzy Classifier System: A Classifier System for Continuously Varying Variables." In ICGA, pp. 346-353. 1991.
28. Riolo, Rick L. (1988-01-01). Empirical Studies of Default Hierarchies and Sequences of Rules in Learning Classifier Systems (Thesis). Ann Arbor, MI, USA: University of Michigan.
29. R.L., Riolo, (1987-01-01). "Bucket brigade performance. I. Long sequences of classifiers". Genetic algorithms and their applications : proceedings of the second International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA.
30. R.L., Riolo, (1987-01-01). "Bucket brigade performance. II. Default hierarchies". Genetic algorithms and their applications : proceedings of the second International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA.
31. W. Stolzmann, "Anticipatory classifier systems," in Proceedings of the 3rd Annual Genetic Programming Conference, pp. 658–664, 1998.
32. Riolo, Rick L. (1990-01-01). "Lookahead Planning and Latent Learning in a Classifier System". Proceedings of the First International Conference on Simulation of Adaptive Behavior on From Animals to Animats. Cambridge, MA, USA: MIT Press: 316–326. ISBN 0262631385.
33. Watkins, Christopher John Cornish Hellaby. "Learning from delayed rewards." PhD diss., University of Cambridge, 1989.
34. Wilson, Stewart W. (1994-03-01). "ZCS: A Zeroth Level Classifier System". Evolutionary Computation. 2 (1): 1–18. doi:10.1162/evco.1994.2.1.1. ISSN 1063-6560.
35. Lanzi, P. L. "Learning classifier systems from a reinforcement learning perspective". Soft Computing. 6 (3-4): 162–170. doi:10.1007/s005000100113. ISSN 1432-7643.
36. Kovacs, Timothy Michael Douglas. A Comparison of Strength and Accuracy-based Fitness in Learning and Classifier Systems. 2002.
37. Kovacs, Tim. "Two views of classifier systems." In International Workshop on Learning Classifier Systems, pp. 74-87. Springer Berlin Heidelberg, 2001
38. ^ Jump up to:a b Congdon, Clare Bates. "A comparison of genetic algorithms and other machine learning systems on a complex classification task from common disease research." PhD diss., The University of Michigan, 1995.
39. Holmes, John H. (1996-01-01). "A Genetics-Based Machine Learning Approach to Knowledge Discovery in Clinical Data". Proceedings of the AMIA Annual Fall Symposium: 883. ISSN 1091-8280. PMC 2233061.
40. Holmes, John H. "Discovering Risk of Disease with a Learning Classifier System." In ICGA, pp. 426-433. 1997.
41. Holmes, John H., and Jennifer A. Sager. "Rule discovery in epidemiologic surveillance data using EpiXCS: an evolutionary computation approach." InConference on Artificial Intelligence in Medicine in Europe, pp. 444-452. Springer Berlin Heidelberg, 2005.
42. Butz, Martin V. "Biasing exploration in an anticipatory learning classifier system." In International Workshop on Learning Classifier Systems, pp. 3-22. Springer Berlin Heidelberg, 2001.
43. Wilson, Stewart W. "Classifiers that approximate functions". Natural Computing. 1 (2-3): 211–234. doi:10.1023/A:1016535925043. ISSN 1567-7818.
44. Bull, Larry. "A simple accuracy-based learning classifier system." Learning Classifier Systems Group Technical Report UWELCSG03-005, University of the West of England, Bristol, UK (2003).
45. Bull, Larry. "A simple payoff-based learning classifier system." InInternational Conference on Parallel Problem Solving from Nature, pp. 1032-1041. Springer Berlin Heidelberg, 2004.
46. Peñarroya, Jaume Bacardit. "Pittsburgh genetic-based machine learning in the data mining era: representations, generalization, and run-time." PhD diss., Universitat Ramon Llull, 2004.
47. Bacardit, Jaume; Burke, Edmund K.; Krasnogor, Natalio (2008-12-12). "Improving the scalability of rule-based evolutionary learning". Memetic Computing. 1 (1): 55–67. doi:10.1007/s12293-008-0005-4. ISSN 1865-9284.
48. Design and Analysis of Learning Classifier Systems - Springer. doi:10.1007/978-3-540-79866-8.
49. Urbanowicz, Ryan J., Gediminas Bertasius, and Jason H. Moore. "An extended michigan-style learning classifier system for flexible supervised learning, classification, and data mining." In International Conference on Parallel Problem Solving from Nature, pp. 211-221. Springer International Publishing, 2014.
50. Urbanowicz, Ryan J., Delaney Granizo-Mackenzie, and Jason H. Moore. "Using expert knowledge to guide covering and mutation in a michigan style learning classifier system to detect epistasis and heterogeneity." InInternational Conference on Parallel Problem Solving from Nature, pp. 266-275. Springer Berlin Heidelberg, 2012.
51. Urbanowicz, Ryan; Granizo-Mackenzie, Ambrose; Moore, Jason (2012-01-01). "Instance-linked Attribute Tracking and Feedback for Michigan-style Supervised Learning Classifier Systems". Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. GECCO '12. New York, NY, USA: ACM: 927–934. doi:10.1145/2330163.2330291. ISBN 9781450311779.
52. Bacardit, Jaume; Krasnogor, Natalio (2009-01-01). "A Mixed Discrete-continuous Attribute List Representation for Large Scale Classification Domains". Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation. GECCO '09. New York, NY, USA: ACM: 1155–1162. doi:10.1145/1569901.1570057. ISBN 9781605583259.
53. Iqbal, Muhammad; Browne, Will N.; Zhang, Mengjie (2014-08-01). "Reusing Building Blocks of Extracted Knowledge to Solve Complex, Large-Scale Boolean Problems". IEEE Transactions on Evolutionary Computation. IEEE. 18 (4): 465–480. doi:10.1109/tevc.2013.2281537.
54. Booker, L. B.; Goldberg, D. E.; Holland, J. H. (1989-09-01). "Classifier systems and genetic algorithms". Artificial Intelligence. 40 (1): 235–282. doi:10.1016/0004-3702(89)90050-7.
55. Wilson, Stewart W., and David E. Goldberg. "A critical review of classifier systems." In Proceedings of the third international conference on Genetic algorithms, pp. 244-255. Morgan Kaufmann Publishers Inc., 1989.