Learning Regular Languages
with Queries and Counterexamples

یادگیری فعّال اتوماتا – الگوریتم L* و فراتر از آن
محمد حسین صالحی‌نژاد ۴۰۲۳۱۰۳۳
دانشکده مهندسی کامپیوتر – دانشگاه صنعتی امیرکبیر پاییز ۱۴۰۴ نظریه زبان‌ها و اتوماتا

از پرسش‌های عضویت و هم‌ارزی تا مدلی دقیق – مروری بر یادگیری زبان‌های منظم

مسئله در یک نگاه

یادگیری رفتار یک سیستم ناشناخته فقط با تعامل

سیستم جعبه‌سیاه
چراغ A
چراغ B

ورودی: دکمه‌ها    خروجی: چراغ‌ها

❓ فقط می‌توانی دکمه بزنی و ببینی چه چراغی روشن می‌شود.

جعبه‌سیاه

  • دستگاه داری با چند دکمه (ورودی)
  • چند چراغ نشان‌دهنده (خروجی)
  • از داخلش هیچ نمی‌دانی
  • فقط می‌توانی دکمه بزنی و خروجی را ببینی
آیا می‌شود فقط با همین تعامل،
مدل دقیق رفتار دستگاه را کشف کرد؟

ریشه نظری دارد، اما انگیزه و کاربرد آن کاملاً عملی است.


این مقاله دربارهٔ این است که چطور می‌شود رفتار یک سیستم ناشناخته را فقط با سؤال پرسیدن و امتحان کردن یاد گرفت و برایش یک مدل دقیق (اتوماتا) ساخت.

چرا این موضوع حیاتی است؟

اهمیت و کاربردهای عملی

فقط یک مسئلهٔ نظری نیست – در قلب چندین حوزهٔ راهبردی قرار دارد

هوش مصنوعی

رباتی که وارد محیطی ناشناخته می‌شود، تنها با عمل و مشاهده باید مدلی از محیط بسازد.

امنیت شبکه

مهندس امنیت با فرستادن بسته‌های داده و دیدن پاسخ‌ها، ساختار پروتکل ناشناخته را حدس می‌زند.

یادگیری ماشین

یادگیری یک مفهوم رسمی (زبان، اتوماتا) تنها از طریق آزمایش و پرسش.

مهندسی سخت‌افزار

تست و مدل‌سازی مدارهای دیجیتال بدون آگاهی از طراحی داخلی.

هستهٔ مشترک همگی: «یادگیری رفتار از طریق پرسش و مشاهده»

از جعبه‌سیاه تا مدل – یادگیری فعال اتوماتا پاسخی به این نیاز مشترک است.

چرا اتوماتای قطعی (DFA)؟
مدل با حافظه محدود

خیلی از سیستم‌های واقعی ...

  • حافظه محدود دارند
  • رفتارشان به «حالت فعلی» وابسته است
  • با دریافت ورودی، تغییر حالت می‌دهند
  • خروجی (پذیرش/رد) قابل مشاهده است
  • تعداد حالت‌ها متناهی است

پس مسئله = یادگیری یک DFA

نمایش مفهومی
q₀
q₁
q₂
حالت شروع حالت پذیرش

هر پیشوند = حالتی در ماشین مینیمال

اگر رفتار سیستم با تعداد محدودی حالت توصیف شود → یادگیری DFA مسئلهٔ اصلی است.

قدیما می‌گفتند ...

«یک سری مثال مثبت و منفی بده، بعد از روی اونا یاد بگیر.»

به این می‌گفتند مدل یادگیری منفعل (Passive Learning).

  • یادگیرنده فقط دریافت‌کنندهٔ مثال‌هاست
  • هیچ سؤالی نمی‌تواند بپرسد
  • باید از بین بی‌نهایت DFA، یکی را انتخاب کند

نمونه ورودی

۰۰ قبول
۰۱ رد
۱۰ قبول
۱۱۱ رد

⚡ تعداد مثال‌ها محدود، اما فضای فرضیه‌ها نامتناهی.

📌
مارک گلد (۱۹۷۸)

پیدا کردن کوچک‌ترین DFA هماهنگ با مثال‌ها ← NP-hard

یعنی برای سیستم‌های واقعی، عملاً غیرقابل انجام.

اگر یادگیرنده فقط ساکت بنشیند و مثال بگیرد، حتی برای زبان‌های ساده هم یادگیری تضمین‌شده غیرممکن است.
۱۹۸۷ – نقطه عطف تاریخ یادگیری
دانا انگلین (Dana Angluin)
۱۹۸۷

«چرا یادگیرنده فقط ساکت بنشیند؟ بگذار سؤال بپرسد!»

مدل MAT

Minimally Adequate Teacher
معلم کمینهٔ کافی

  • معلم دو نوع سؤال پاسخ می‌دهد
  • الگوریتم L* روی همین مدل کار می‌کند

پرسش عضویت

«این رشته توی زبانه یا نه؟»

⏱️ پاسخ: بله/خیر – هزینهٔ O(1) در مدل نظری

مثال: MQ("۰۱۰") ← قبول

پرسش هم‌ارزی

«این DFA که حدس زدم درسته؟ اگر نه، مثال نقض بده.»

🎯 پاسخ: «بله» یا یک رشتهٔ مخالف

مثال نقض: رشته‌ای که توسط DFA حدس و زبان واقعی متفاوت جواب می‌دهد
الگوریتم L*

با استفاده از جدول مشاهده (Observation Table) و تکرار:
✔ بسته بودن (Closed) ✔ سازگار بودن (Consistent)
➡ هر بار DFA حدس زده می‌شود، با مثال نقض اصلاح می‌گردد.

پیچیدگی L*

  • n = تعداد حالت‌های DFA هدف
  • m = طول بلندترین مثال نقض
  • |Σ| = اندازه الفبا
📊 پرسش‌های عضویت: O(|Σ|·m·n² + n log m)
📊 پرسش‌های هم‌ارزی: O(n)
قضیه انگلین (۱۹۸۷)

هر زبان منظم را می‌توان در زمان چندجمله‌ای و با دقت ۱۰۰٪ یاد گرفت (با دسترسی به معلم در مدل MAT)

این نقطهٔ آغاز تمام حوزهٔ Active Automata Learning بود.

بنیاد نظری: رابطهٔ نرود (Nerode)

از هم‌ارزی نرود تا جدول مشاهده

«هر زبان منظم دقیقاً یک DFA مینیمال دارد و آن برابر است با کلاس‌های هم‌ارزی نرود.»

≡ₗ

u ≡ₗ v اگر و فقط اگر برای هر ادامهٔ w:

u·w ∈ L ⇔ v·w ∈ L

یعنی هیچ آزمایشی وجود ندارد که u و v را از هم جدا کند.

هر کلاس هم‌ارزی ← یک حالت در DFA مینیمال

کلاس‌های هم‌ارزی (مثال)

[ε] = {ε, 00, 11} [0] = {0, 010, 110} [1] = {1, 01, 101}

DFA مینیمال: هر کلاس = یک حالت.

جدول مشاهده (Observation Table)

پیشوند (S) ε ۰ ۱
ε ✅ ✅ ❌
۰ ✅ ❌ ✅
۱ ❌ ✅ ✅
۰۰ … در حال یادگیری

سطرها = پیشوندها (حالت‌های کاندید) | ستون‌ها = پسوندها (آزمایش‌ها)

بسته (Closed)

هر ترکیب s·a (پیشوند + حرف) با یکی از سطرهای موجود برابر باشد.

⚙️ اگر نباشد → آن را به S اضافه کن.

سازگار (Consistent)

اگر دو سطر یکسان باشند، پس از اضافه شدن یک حرف هم باید خروجی‌شان یکسان بماند.

⚙️ اگر نباشد → پسوند جدید اضافه کن.

الگوریتم L* – گام‌به‌گام

شروع

S = {ε}, E = {ε}, پرس‌وجوی عضویت

بسته/سازگار

اگر خیر: S یا E را توسعه بده

حدس DFA

ساخت M(S,E,T)

پرسش هم‌ارزی

به معلم بده

✅ تأیید

الگوریتم پایان – DFA نهایی

❌ مثال نقض (Counterexample)
«۰۱۰۱» رشته‌ای که توسط DFA حدس و زبان واقعی متفاوت جواب می‌دهد

➕ همهٔ پیشوندهای مثال نقض به S اضافه می‌شوند ← جدول گسترش می‌یابد.

L* خلاصه: یادگیری تدریجی DFA مینیمال با تضمین هم‌ارزی نهایی.
O(|Σ|·n²·m + n log m)
مشکل اول – فرض غیرواقعی
مشکل Reset
L* فرض می‌کند ...

فرض L*

«قبل از هر پرسش عضویت، می‌توان سیستم را به حالت آغازین بازگرداند.»

Reset ایدهآل – برگشت آنی به حالت اول

اما در دنیای واقعی ...

ربات در محیط

نمی‌تواند «تلپورت» کند تا به نقطهٔ شروع برگردد

پروتکل شبکهٔ زنده

نمی‌توان بدون قطع اتصال به حالت اولیه برگشت

سیستم تراکنش مالی

پس از هر تراکنش، وضعیت تغییر می‌کند

یادگیرنده همیشه در یک حالت ناشناخته q_current است

نمی‌داند پرسش عضویت بعدی را از کدام حالت شروع کند ← اجرای مستقیم L* غیرممکن است.

راه‌حل توالی هومینگ (Homing Sequence)

دنباله‌ای h ∈ Σ* که اگر از هر دو حالت q₁, q₂ اجرا شود و خروجی یکسان بدهد، آن دو حالت به یک حالت پایانی یکسان ختم شوند.

Preset

دنبالهٔ ثابت، مستقل از خروجی‌ها

Adaptive

درخت تصمیم – هر نماد بعدی بر اساس خروجی دیده شده انتخاب می‌شود (کارآمدتر)

الگوریتم Rivest & Schapire

بدون نیاز به Reset، با حفظ چند L* کپی موازی و گسترش تدریجی h، DFA درست را پیدا می‌کند.

⚙️ در بخش ۴ (اسلایدهای بعدی) به‌طور کامل به الگوریتم Homing و Adaptive می‌پردازیم.

یادگیری بدون Reset – راه‌حل عملی
توالی هومینگ (Homing Sequence) Rivest & Schapire, 1989

تعریف

دنبالهٔ h ∈ Σ* یک توالی هومینگ است اگر:

برای هر دو حالت q₁, q₂

اگر اجرای h از q₁ و q₂ خروجی یکسان دهد،

آن‌گاه به یک حالت پایانی یکسان ختم شوند.

Preset: ثابت Adaptive: درخت تصمیم

مثال: توالی هومینگ

q₀
q₁
q₂
h = a b a

🧪 با مشاهدهٔ خروجی، می‌توان تشخیص داد در کدام «دستهٔ هم‌ارزی» قرار گرفته‌ایم.

الگوریتم Rivest & Schapire

بدون نیاز به Reset، با حفظ چندین L* کپی موازی و گسترش تدریجی توالی هومینگ، DFA درست را پیدا می‌کنیم.

L*₁

فرض: حالت شروع q₁

L*₂

فرض: حالت شروع q₂

L*₃

فرض: حالت شروع q₃

۱

شروع با h = ε

۲

اجرای h و مشاهدهٔ خروجی

۳

اگر L*ها جواب نادرست دادند ← h را با دنبالهٔ کشف اختلاف گسترش بده

۴

تکرار تا h واقعی شود ← یکی از L*ها DFA درست را پیدا می‌کند

نکتهٔ طلایی: الگوریتم بدون نیاز به Reset، با پیدا کردن تدریجی یک توالی هومینگ مناسب، یادگیری DFA را ممکن می‌سازد.
پیچیدگی: چندجمله‌ای در تعداد حالت‌ها و طول توالی هومینگ
تضمین یادگیری دقیق در مدل غیرقابل بازنشانی
Probably Approximately Correct (PAC) Learning
یادگیری در دنیای واقعی: بدون معلم، فقط نمونه

مدل PAC – چارچوب استاندارد یادگیری ماشین نظری

مدل PAC

توسط Valiant (1984) معرفی شد – بنیان یادگیری محاسباتی.

یادگیرنده باید مدل h را به‌گونه‌ای بسازد که:

P[ error(h) ≤ ε ] ≥ 1 − δ
ε: خطای مجاز δ: اطمینان
  • هیچ معلمی نیست
  • نمی‌توان پرسش هم‌ارزی کرد
  • فقط نمونه‌های تصادفی از توزیع ناشناخته D

اوراکل نمونه (EX)

تنها راه ارتباط با دنیای خارج:

(x, L(x))

✦ x طبق توزیع D انتخاب می‌شود.
✦ L(x) برچسب واقعی (عضویت در زبان).

تفاوت اساسی با MAT: نمی‌توانی رشتهٔ دلخواه را بپرسی – فقط همانی که طبیعت به تو می‌دهد.

دو جهان موازی

مدل MAT (Angluin) مدل PAC (Valiant)
✅ معلم وجود دارد ❌ معلم وجود ندارد
✅ پرسش عضویت (هر رشته) ❌ فقط نمونهٔ تصادفی
✅ پرسش هم‌ارزی + مثال نقض ❌ هیچ پرسشی امکان ندارد
🎯 یادگیری دقیق (exact) 🎯 یادگیری تقریبی (approximate)
قضیهٔ انگلین (۱۹۸۷)

اگر یک کلاس زبان در مدل MAT قابل یادگیری دقیق باشد،
آنگاه در مدل PAC نیز قابل یادگیری است.

پیامد عملی

الگوریتم L* و سایر الگوریتم‌های MAT را می‌توان
به الگوریتم‌های PAC تبدیل کرد.

اهمیت نظری

قدرت یادگیری مدل پرسش و پاسخ
به مدل نمونه‌گیری تصادفی تعمیم می‌یابد.

L* تنها یک الگوریتم نظری نیست؛ بنیان روش‌های عملی یادگیری ماشین برای سیستم‌های منظم را می‌سازد.
ارائهٔ مشترک – دو نگاه، یک مسیر
محمدحسین صالحی‌نژاد
۴۰۲۳۱۰۳۳

بخش اول: بنیادها و الگوریتم کلاسیک

  • مدل MAT و پرسش‌های عضویت/هم‌ارزی
  • الگوریتم L* و جدول مشاهده
  • چالش Reset و توالی هومینگ
  • ارتباط MAT و PAC (قضیهٔ انگلین)
⏱️ تا اینجا – مبانی نظری و الگوریتم‌های پایه
آیناز میمنت
۴۰۲۳۱۴۲۲

بخش دوم: تعمیم‌ها، کاربردها و چشم‌انداز

  • نمایش مبتنی بر تنوع (Variety-based)
  • ماشین‌های ثبتی میلی (RMM) – یادگیری برنامه‌های با داده
  • الگوریتم L# – تلفیق L* با نمونه‌برداری PAC
  • کاربردهای عملی: تست نرم‌افزار، مهندسی معکوس، پروژه CONNECT
  • چالش‌های آینده و نتیجه‌گیری
🚀 ادامهٔ مسیر – از نظریه تا عمل
ادامه ارائه با آیناز میمنت

از آبیِ نظریه تا صورتیِ کاربرد – هم‌افزایی دو نگاه برای کشف رفتار سیستم‌های ناشناخته