2025-11-19T16:52:14.243866

Learning Weighted Automata over Number Rings, Concretely and Categorically

Aristote, van Gool, Petrişan et al.
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories. As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.
academic

تعلم الأتمتة الموزونة على حلقات الأعداد، بشكل ملموس وفئوي

المعلومات الأساسية

  • معرّف الورقة: 2504.16596
  • العنوان: تعلم الأتمتة الموزونة على حلقات الأعداد، بشكل ملموس وفئوي
  • المؤلفون: Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi
  • التصنيف: cs.FL (نظرية اللغات الرسمية والأتمتة)
  • تاريخ النشر: 23 أبريل 2025 (نسخة أولية على arXiv)
  • رابط الورقة: https://arxiv.org/abs/2504.16596

الملخص

تطور هذه الورقة إجراء اختزال موحد لمشاكل التعلم النشط. يستلهم هذا النهج من العمل الحديث لـ Buna-Marginean وآخرين (2024) الذي اقترح اختزالاً متعدد الحدود لمشكلة تعلم الأتمتة الموزونة على الأعداد الصحيحة إلى تعلم الأتمتة الموزونة على الأعداد النسبية. يحسّن الإجراء كفاءة خوارزميات التعلم الفئوية للأتمتة، ويطرح أسئلة جديدة حول تعقيد التنفيذ عند التجسيد في حالات فئوية ملموسة. كمساهمة ثانية رئيسية، يعالج المؤلفون هذه أسئلة التعقيد في الإعداد الملموس لتعلم الأتمتة الموزونة على حلقات الأعداد (حلقات الأعداد الصحيحة في حقول الأعداد الجبرية). بافتراض تمثيل كامل لحلقة الأعداد OK، تم الحصول على خوارزمية تعلم دقيقة للأتمتة الموزونة على OK بتعقيد زمني متعدد الحدود فيما يتعلق بحجم الأتمتة المستهدفة، واللوغاريتم لطول أطول مثال معاكس، ودرجة حقل الأعداد، واللوغاريتم للمميز. تنتج الخوارزمية أتمتة بحد أقصى حالة واحدة أكثر من الأتمتة الدنيا، ويثبت أن تحقيق نتيجة أفضل يتطلب حل مشكلة المثالية الرئيسية، حيث أفضل خوارزمية معروفة حالياً هي زمن متعدد الحدود الكمي.

الخلفية البحثية والدافع

خلفية المشكلة

  1. تعلم الأتمتة الكلاسيكي: خوارزمية L* لـ Angluin تتعلم بكفاءة الأتمتة الحتمية المحدودة تحت إطار المعلم الكافي الأدنى (MAT)، وهي نتيجة كلاسيكية في نظرية التعلم الحسابي.
  2. تحديات تعلم الأتمتة الموزونة: يواجه توسيع خوارزميات التعلم إلى نماذج أكثر تعبيراً (مثل الأتمتة الموزونة) تحديات، خاصة عندما تكون الأوزان في حلقة بدلاً من حقل.
  3. قيود الطرق الموجودة:
    • بالنسبة للأتمتة الموزونة على الحقول، توجد خوارزميات تعلم متعددة الحدود
    • بالنسبة للأتمتة الموزونة على الحلقات العامة، الطرق الموجودة إما أن يكون لها تعقيد مرتفع جداً أو نطاق تطبيق محدود
    • الطرق الفئوية، على الرغم من عموميتها، قد تؤدي إلى تعقيد أسي عند التنفيذ الملموس

الدافع البحثي

  1. الحاجة النظرية: الحاجة إلى إطار عمل يحافظ على عموميّة الطريقة الفئوية ويحقق تعقيداً متعدد الحدود في الحالات الملموسة
  2. التطبيقات العملية: حلقات الأعداد لها تطبيقات مهمة في التشفير وغيره، وللتعلم الفعال للأتمتة الموزونة عليها قيمة عملية
  3. الحدود النظرية: استكشاف الحدود النظرية لتقليل الأتمتة الموزونة، خاصة تعميم خاصية Fatou

المساهمات الأساسية

  1. خوارزمية الاختزال الموحدة: تقديم Algorithm 3، وهو إجراء اختزال موحد في الإطار الفئوي يختزل فئة من مشاكل التعلم إلى فئة أخرى أسهل في المعالجة
  2. خوارزمية ملموسة على حلقات الأعداد: تطوير Algorithm 4، خوارزمية تعلم متعددة الحدود متخصصة للأتمتة الموزونة على حلقات الأعداد OK
  3. نتائج شبه الأمثلية: إثبات أن الأتمتة التي تنتجها الخوارزمية تحتوي على حالة واحدة على الأكثر أكثر من الأتمتة الدنيا (شبه الحد الأدنى)
  4. حدود التعقيد النظري: إثبات أن الحصول على أتمتة دنيا تماماً يعادل حل مشكلة المثالية الرئيسية (PIP-hard)، مما يؤسس الحد الأدنى النظري للمشكلة
  5. تعميم خاصية Fatou: إثبات أن حلقات Dedekind هي "حلقات Fatou قوية تقريباً"، مما يعمم الخاصية الكلاسيكية

شرح الطريقة

تعريف المهمة

المدخل: لغة موزونة مجهولة على OK: L: Σ* → OK (يتم الوصول إليها عبر oracle) المخرج: أتمتة موزونة على OK تحسب L القيود: تعقيد الخوارزمية متعدد الحدود في حجم الأتمتة المستهدفة، واللوغاريتم لطول أطول مثال معاكس، ودرجة حقل الأعداد، واللوغاريتم للمميز

الإطار التقني الأساسي

1. الأساس الفئوي

تعتمد الورقة على منظور الدوال، حيث تُعتبر الأتمتة كدالة A: I → C، حيث:

  • I هي الفئة الحرة المولدة بواسطة الأبجدية Σ
  • C هي فئة المخرجات (مثل فئة الوحدات ModR)

2. خوارزمية الاختزال الموحدة (Algorithm 3)

فكرة الخوارزمية:
1. تعلم الأتمتة في فئة "سهلة المعالجة" D
2. إنشاء ارتباط عبر دالة F: C → D
3. استخدام الملحق الأيمن G: D → C لسحب النتيجة إلى الفئة المستهدفة C

الافتراض الرئيسي (Assumption 12):

  • F يحافظ على فئات معينة من التشكلات
  • F له ملحق أيمن G
  • تشكلات الوحدة والملحق المشترك لها خصائص محددة

3. التنفيذ الملموس على حلقات الأعداد (Algorithm 4)

الخطوة 1: الاقتران الخلفي

حساب أساس الفضاء الخلفي للأتمتة A وهو B
اقتران A بالمصفوفة B للحصول على A'

الخطوة 2: توليد الوحدة الأمامية

استدعاء Algorithm 5 لحساب مجموعة توليد الوحدة OK الأمامية لـ A'
استخدام استراتيجية ثنائية المراحل:
- المرحلة الأولى: البحث عن كلمات تزيد الرتبة في K
- المرحلة الثانية: إكمال توليد الوحدة في OK

الخطوة 3: حساب الأساس الزائف

استخدام الشكل الزائف لـ Hermite (pseudo-HNF) لحساب الأساس الزائف من مجموعة التوليد
شكل الأساس الزائف: {(ai, vi) | 1 ≤ i ≤ ℓ}، حيث ai هي مثاليات كسرية

الخطوة 4: مجموعة التوليد شبه الدنيا

تحويل الأساس الزائف إلى مجموعة توليد بحجم على الأكثر ℓ+1 عبر Algorithm 6
استخدام تحسين عامل المثالية والنظرية الصينية للبواقي

نقاط الابتكار التقني

  1. استراتيجية التوليد ثنائية المراحل: تحديد الرتبة أولاً في الحقل K، ثم إكمال بنية الوحدة في الحلقة OK، مما يتجنب التعقيد الأسي
  2. تقنية الأساس الزائف: الاستفادة من نظرية بنية حلقات Dedekind، معالجة حالة الحقول غير ذات المثاليات الرئيسية عبر الأساس الزائف
  3. دمج النظرية الفئوية مع الخوارزميات الملموسة: تجسيد الإطار الفئوي المجرد في خوارزمية ملموسة متعددة الحدود

الإعداد التجريبي

التحقق النظري

الورقة هي في الأساس عمل نظري، يتم التحقق منه بالطرق التالية:

  1. تحليل التعقيد: تحليل مفصل لتعقيد الزمن لـ Algorithm 4 و Algorithm 5
  2. إثبات الصحة: إثبات صحة الخوارزمية الموحدة عبر Theorem 18
  3. التحقق بالأمثلة: توفير أمثلة ملموسة (مثل Example 1) توضح الحالة على Zi√5

حدود التعقيد

النظرية 2: بافتراض تمثيل كامل لـ OK، يمكن حل تعلم الأتمتة الموزونة على OK في زمن متعدد الحدود في المعاملات التالية:

  • حجم الأتمتة المستهدفة
  • اللوغاريتم لطول أطول مثال معاكس
  • درجة حقل الأعداد d
  • اللوغاريتم للمميز ΔK

نتائج التجارب

النتائج النظرية الرئيسية

  1. شبه الأمثلية (Proposition 10): بالنسبة لحلقة Dedekind R، إذا كانت L لغة موزونة على R برتبة n، فإنه يوجد أتمتة موزونة على R بحد أقصى n+1 حالة تحسب L
  2. الحد الأدنى للتعقيد (Proposition 26): تحديد ما إذا كانت أتمتة موزونة على OK ذات حد أدنى من الحالات هو PIP-困难
  3. تعميم خاصية Fatou (Corollary 16): حلقات Dedekind هي حلقات Fatou قوية تقريباً

تحليل الأمثلة الملموسة

المثال 1: في حلقة الأعداد R = Zi√5:

  • بناء أتمتة موزونة على R بـ 3 حالات
  • وجود أتمتة موزونة على K معادلة بـ 2 حالة (K = Q(i√5))
  • يوضح أن خاصية Fatou القوية لا تكون دائماً صحيحة، لكن خاصية Fatou القوية تقريباً تكون صحيحة

الأعمال ذات الصلة

تعلم الأتمتة الكلاسيكي

  • خوارزمية L* لـ Angluin: تعلم متعدد الحدود للأتمتة الحتمية المحدودة
  • Beimel وآخرون: خوارزميات تعلم الأتمتة الموزونة على الحقول

الأتمتة الموزونة على الحلقات

  • van Heerdt وآخرون: التعلم على حلقات المثاليات الرئيسية، لكن بدون حدود التعقيد
  • Buna-Marginean وآخرون: الاختزال من Z إلى Q، الإلهام المباشر لهذه الورقة

الطرق الفئوية

  • Colcombet-Petrişan: طريقة الدوال لتقليل الأتمتة
  • Urbat-Schröder وآخرون: الطرق الجبرية للتعلم

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. تطوير أول خوارزمية تعلم متعددة الحدود للأتمتة الموزونة على حلقات الأعداد
  2. إثبات صعوبة الحصول على أتمتة دنيا تماماً (PIP-困难)
  3. بناء جسر بين النظرية الفئوية والخوارزميات الملموسة

القيود

  1. متطلبات التمثيل: الحاجة إلى "تمثيل كامل" لحلقة الأعداد OK، وهذا قد يكون صعباً في الممارسة العملية
  2. شبه الأمثلية: قد تنتج الخوارزمية أتمتة بحالة واحدة أكثر من الأتمتة الدنيا
  3. البنية المحددة: الطريقة متخصصة لحلقات Dedekind، والتعميم على الحلقات العامة غير واضح

الاتجاهات المستقبلية

  1. فئات حلقات أخرى: البحث عن التعميم على حقول غير Dedekind
  2. التنفيذ العملي: تطوير تنفيذ برمجي ملموس والتحقق التجريبي
  3. استكشاف التطبيقات: التطبيقات الملموسة في التشفير وغيره

التقييم المتعمق

المميزات

  1. العمق النظري: دمج ماهر للنظرية الفئوية، نظرية الأعداد الجبرية، ونظرية التعقيد الحسابي
  2. الابتكار التقني: استخدام استراتيجية التعلم ثنائية المراحل وتقنية الأساس الزائف مبتكر جداً
  3. الاكتمال: تقديم خوارزمية وإثبات الحد الأدنى، مما يوفر صورة كاملة للمشكلة
  4. الدقة: الإثباتات الرياضية دقيقة وتحليل التعقيد مفصل

أوجه القصور

  1. الجدوى العملية: افتقار إلى التنفيذ الفعلي والتحقق التجريبي
  2. سهولة القراءة: قد تكون أجزاء النظرية الفئوية صعبة الفهم للمتخصصين غير المتخصصين
  3. نطاق التطبيق: محدودية نطاق تطبيق الطريقة بسبب البنى الجبرية المحددة

التأثير

  1. المساهمة النظرية: مساهمة مهمة في نظرية تعلم الأتمتة الموزونة
  2. المنهجية: توضيح كيفية تجسيد الطرق الفئوية المجردة
  3. التعاون بين المجالات: ربط نظرية الأتمتة، نظرية الأعداد الجبرية، والتعقيد الحسابي

السيناريوهات المناسبة

  1. التشفير: تطبيقات حلقات الأعداد في تشفير الشبكات
  2. الحساب الرمزي: مشاكل الحساب على حقول الأعداد الجبرية
  3. البحث النظري: توفير أساس لأبحاث إضافية في تعلم الأتمتة

تفاصيل تقنية إضافية

تمثيل حلقات الأعداد

تتطلب الورقة "تمثيلاً كاملاً" لـ OK يتضمن:

  • الأساس المتكامل Ω = {ω1,...,ωd}
  • العنصر البدائي θ وكثيرة حدوده الدنيا
  • مقياس التعقيد CK = d⁴(log d + log ΔK)

تعقيد الخوارزمية

حدود التعقيد الرئيسية تأتي من:

  • حساب pseudo-HNF: زمن متعدد الحدود (Biasse-Fieker-Hofmann)
  • طول السلسلة المتزايدة بشكل صارم: محدود بواسطة Lemma 24 بـ log(N(d))
  • عمليات المثاليات: زمن متعدد الحدود في CK

تقدم هذه الورقة مساهمة مهمة في مجال علوم الحاسوب النظرية، خاصة في مجال التقاطع بين تعلم الأتمتة والحساب الجبري. على الرغم من أن الجدوى العملية تحتاج إلى التحقق، فإن قيمتها النظرية ومعنى منهجيتها كبيران جداً.