למידת מכונה מגלה קודים אלופים חדשים

המחקר מציע דרך מעשית להאיץ גילוי של קודי תיקון שגיאות טובים יותר — רכיב יסוד בתקשורת דיגיטלית, אחסון מידע, רשתות, לוויינים וחלל. במקום לבצע חישוב מדויק ויקר מאוד על כל מועמד, המערכת משתמשת ב-AI כדי לדרג במהירות אילו קודים שווים בדיקה מעמיקה, ואז מפעילה חיפוש אבולוציוני כדי להגיע לפתרונות חזקים יותר. עבור מנהלים ומהנדסים, המשמעות היא קיצור זמן מחקר ופיתוח בתחומים שבהם אמינות מידע קריטית, כמו תקשורת, חומרה, תשתיות נתונים ומערכות קצה. מעבר לתחום הקידוד עצמו, זהו גם הוכחת היתכנות לכך שאפשר להשתמש בלמידת מכונה כדי לנווט בעיות מתמטיות קשות מאוד, לצמצם משמעותית את מרחב החיפוש, ולגלות תוצרים חדשים שלא נמצאו בשיטות מיצוי קלאסיות.

מבוא

המאמר עוסק בבעיה יסודית בתורת הקודים: מציאת קודים ליניאריים מתקני שגיאות בעלי מרחק המינג מינימלי מקסימלי עבור אורך בלוק וממד נתונים. קודים כאלה נקראים champion codes, משום שהם משווים או משפרים את השיאים הידועים. הבעיה חישובית קשה מאוד, שכן חישוב המרחק המינימלי של קוד ליניארי הוא בעיה מסוג NP-hard. החישוב המדויק מתבצע בדרך כלל באמצעות אלגוריתם Brouwer-Zimmermann (BZ), שהוא יקר חישובית. לכן מטרת המחקר היא לא להחליף את החישוב המדויק, אלא לצמצם משמעותית את מספר הפעמים שצריך להפעיל אותו.

החוקרים מציעים מסגרת היברידית: תחילה מאמנים מודל Transformer לחזות את המרחק המינימלי של קוד, ולאחר מכן מחברים אותו לאלגוריתם גנטי שמנווט את החיפוש במרחב הקודים ומעדיף מועמדים שנחזים כמבטיחים. את השיטה מדגימים על משפחת generalised toric codes, אך טוענים שהיא רלוונטית גם למשפחות נוספות כמו Reed-Muller, BCH, קודים אלגבריים-גאומטריים ואולי גם קודים קוונטיים.

הקודים הטוריים המוכללים

המחקר מתמקד ב-generalised toric codes, המוגדרים מתוך קבוצות קודקודים על סריג דו-ממדי בתחום ([0,q-2]^2) מעל שדה סופי (\mathbb{F}_q). מכל קבוצה כזו נבנה קוד ליניארי באמצעות וקטורים הנוצרים מהערכת מונומים על נקודות השדה. לכל קוד מתקבלים אורך בלוק (n=(q-1)^2), ממד (k), ומרחק מינימלי (d).

החוקרים בחרו במשפחה זו מכמה סיבות: קל יותר לייצר עבורה דאטה, היא פשוטה לפרמטריזציה ולכן מתאימה לאופטימיזציה גנטית, והיא כבר הוכיחה את עצמה בעבר כמקור לגילוי קודים אלופים. בנוסף, היא משמשת כמקרה מבחן לא טריוויאלי לשיטה כללית יותר.

בניית מסגרת הלמידה

הקוד הליניארי מיוצג באמצעות מטריצת יוצר קנונית או מטריצת parity-check. החוקרים ממסגרים את המשימה כבעיית סיווג רצפים בסגנון NLP: כל שורת מטריצת היוצר היא "טוקן" ברצף, והתווית היא מחלקת המרחק המינימלי. טווח המחלקות הוא בקירוב מ-0 עד ((q-1)^2-1).

המודל מבוסס על גרסה מופשטת של GPT-2 שהותאמה ממשימת sequence-to-sequence למשימת sequence classification. האדריכלות כוללת ייצוגים לאיברי השדה, קידוד מיקום סינוסואידלי, שתי שכבות attention, שכבת סיכום ממוסכת, והקרנה לוגיטית עם softmax. עבור (\mathbb{F}_7) לא נעשה embedding מפורש לאיברי השדה, ואילו עבור (\mathbb{F}_8) השתמשו בוקטורים בני 4 ממדים.

מערכי הנתונים

עבור (\mathbb{F}_7) יצרו החוקרים מאגר של 2,700,000 קודים. התפלגות המרחקים הייתה מאוד לא מאוזנת: חלק מהמחלקות כללו 2 דוגמאות בלבד, ואחרות יותר מ-600,000. לכן הם ביצעו איזון מחלקות באמצעות oversampling למחלקות קטנות עד 500 דוגמאות ו-downsampling למחלקות גדולות עד 50,000, ולאחר ערבוב חוזר התקבל מערך של כ-550,000 דוגמאות. חלוקת train/test הייתה 9:1.

עבור (\mathbb{F}_8) נבנה מערך קטן יותר של 1,584,099 קודים, אך בגלל מורכבות גבוהה יותר ופיזור נתונים דל יותר, אומצה פרוצדורת אימון דו-שלבית. בשלב pre-training השתמשו בכ-300,000 דוגמאות ממחלקות עם יותר מ-10,000 מופעים. בשלב האימון הסופי השתמשו בכל המחלקות, עם oversampling/downsampling ל-600 דוגמאות לכל מחלקה, כך שהתקבל מערך של כ-20,000 דוגמאות. גם כאן בוצעה חלוקה 9:1.

ביצועי המודל

הביצועים נמדדו בעיקר לפי MAE ולפי שיעור התחזיות שנפלו בטווח של ±3 מהמרחק האמיתי.

על (\mathbb{F}_7):

• בסט האימון התקבל MAE של 1.04 ודיוק 91.9%.
• בסט הבדיקה, שכלל כ-61,000 דוגמאות, התקבל MAE של 1.05 ודיוק 91.6%.
• ברמת המחלקות, בכל המחלקות ה-MAE היה קטן מ-3, ורוב ערכי ה-MSE היו קרובים לריבוע ה-MAE, מה שמעיד שמספר הטעויות הגדולות היה קטן.

על (\mathbb{F}_8):

• לאחר post-training התקבל MAE של 1.09 ודיוק 93.4% בסט האימון.
• בסט הבדיקה התקבל MAE של 1.21 ודיוק 92.4%.
• חריגות גדולות יותר הופיעו בעיקר בכמה מחלקות מסוימות: (d=7,14,20,21,28), מה שמסמן כיוונים לשיפור עתידי.

שילוב עם אלגוריתם גנטי

לאחר האימון, המודל שימש כפונקציית התאמה בתוך אלגוריתם גנטי. הכרומוזום הוא קבוצת קודקודים בגודל (n), וכל קודקוד הוא "גן". בכל דור בוצעו:

• Selection: בחירה של 200 הורים מתוך אוכלוסייה של 300 באמצעות stochastic universal sampling.
• Crossover: החלפה בין מקטעי קודקודים לאחר flattening של הרשימות.
• Mutation: בהסתברות 10% מוחלף קודקוד בקודקוד חדש שאינו בשימוש.
• Elitism: 30 הפתרונות הטובים ביותר נשמרים לדור הבא.

האלגוריתם רץ במשך 200 דורות. פונקציית הכשירות שילבה את המרחק החזוי על ידי המודל, קנס על סטייה מהממד הרצוי, וקנס למניעת גילוי חוזר של קודים שכבר נמצאו.

תוצאות על (\mathbb{F}_7)

מטרת הניסוי על (\mathbb{F}_7) הייתה לשחזר קודים אלופים שכבר ידועים מהספרות. השיטה הצליחה לעשות זאת. לאורך 757 ריצות GA, ברוב הממדים נמצא קוד מיטבי כבר בניסיון הראשון. ממדים 12 ו-15 דרשו יותר איטרציות, וממד 19 נותר קשה במיוחד: גם לאחר 501 ריצות לא נמצא קוד ([36,19,12]) מסוג זה, כנראה בשל נדירותו ונוף חיפוש קשה יותר.

החוקרים מצאו מתאם רופף בין כמות הקודים האלופים שנמצאו בדאטה עבור ממד מסוים לבין מספר הריצות שנדרש כדי לגלותם מחדש. עם זאת, האפקט נחלש בממדים קטנים וגדולים, שבהם קל יחסית למצוא פתרונות טובים. ממצא מעניין במיוחד הוא שבממד 12 לא היו כלל קודים מיטביים בסט האימון והבדיקה, ובכל זאת השיטה הצליחה לגלות קוד מיטבי כזה.

תוצאות על (\mathbb{F}_8)

במקרה (\mathbb{F}_8), שבו מרחקי האלופים ברובם אינם ידועים, החוקרים השתמשו בסינון דו-שלבי: קודם בדיקה מול lower bounds ידועים באמצעות MAGMA, ורק לאחר מכן חישוב BZ מלא למועמדים מבטיחים. בשל מגבלות זמן וחישוב בוצעה ריצה מלאה אחת עבור הממדים 3 עד 46, למעט ממד 30 שנשמט עקב עלות BZ גבוהה.

למרות המגבלות, נמצאו יותר מ-700 מועמדים אפשריים לקודים אלופים, ומעל 500 קודים אלופים בפועל. החוקרים מאשרים לפחות 6 קודים חדשים שלא היו ידועים קודם. בנוסף, בריצה קודמת על טווח קודקודים 20–29 נמצא גם קוד אלוף בממד 22, אך בשל שגיאת קובץ הוא לא נכלל במערך השמור. הישג בולט במיוחד הוא גילוי קודים אלופים בממדים 18, 22 ו-38, אף שלא היו כלל קודים אלופים כאלה בנתוני האימון. בדיקה מפורשת הראתה שכל הקודים שהתגלו בממדים אלה הם אכן חדשים.

השוואה לחיפוש אקראי

החוקרים משווים את השיטה לחיפוש אקראי ומעריכים את גודל מרחב החיפוש כבקירוב (2^{(q-1)^2}/(q^2(q^2-1)(q^2-q))), לאחר קירוב על פי מחלקות שקילות אפיניות. עבור ממדים קטנים או גדולים, שבהם קודים אלופים נפוצים יחסית, לאלגוריתם הגנטי יש יתרון קטן. אך בממדים בינוניים, שבהם הבעיה קשה יותר, השיטה השיגה עד פי 2 הפחתה במספר בדיקות BZ לעומת חיפוש אקראי.

ב-(\mathbb{F}_7), ממד 14 הודגם כמקרה אידיאלי: היו מעט קודים אלופים בדאטה ולכן גילוי אקראי היה קשה, אך ה-GA מצא קוד אלוף בתוך שתי ריצות. ב-(\mathbb{F}_8), הטווח 18–39 דל במיוחד בדוגמאות, ולכן הגילוי בממדים 18, 22 ו-38 מרשים במיוחד ומצביע על יכולת הכללה של המודל מעבר למחלקות שראה היטב באימון.

דיון ומסקנות

המאמר מציג שיטה חדשה ומעשית לחיפוש קודים ליניאריים אלופים באמצעות שילוב של למידת מכונה ואופטימיזציה אבולוציונית. התרומה המרכזית אינה רק שיפור בחיזוי המרחק המינימלי, אלא יצירת pipeline שמפחית את העומס החישובי של חיפוש במרחב עצום. השיטה הצליחה גם לשחזר שיאים ידועים וגם לגלות קודים חדשים.

החוקרים מציינים מספר כיווני המשך: יצירת מערכי נתונים גדולים ומאוזנים יותר, שיפור אדריכלות המודל והלוס, טיוב האלגוריתם הגנטי, הרחבת החיפוש לשדות גדולים יותר כמו (\mathbb{F}9), (\mathbb{F}{11}), (\mathbb{F}_{13}), והחלה על משפחות קודים נוספות ואף קודים קוונטיים. בנוסף, הם מציעים לבחון גם ניסוחי למידה חלופיים, למשל סיווג תמונות על מטריצות מרופדות או שיטות representation learning.

בסיכום, זהו מחקר שמדגים כיצד AI יכול לסייע בפתרון בעיות מתמטיות קשות, לא דרך הוכחה פורמלית אלא דרך הכוונת החיפוש והאצת גילוי של אובייקטים מתמטיים חדשים.