از پرسشهای عضویت و همارزی تا مدلی دقیق – مروری بر یادگیری زبانهای منظم
ورودی: دکمهها خروجی: چراغها
❓ فقط میتوانی دکمه بزنی و ببینی چه چراغی روشن میشود.
ریشه نظری دارد، اما انگیزه و کاربرد آن کاملاً عملی است.
این مقاله دربارهٔ این است که چطور میشود رفتار یک سیستم ناشناخته را فقط با سؤال پرسیدن و امتحان کردن یاد گرفت و برایش یک مدل دقیق (اتوماتا) ساخت.
رباتی که وارد محیطی ناشناخته میشود، تنها با عمل و مشاهده باید مدلی از محیط بسازد.
مهندس امنیت با فرستادن بستههای داده و دیدن پاسخها، ساختار پروتکل ناشناخته را حدس میزند.
یادگیری یک مفهوم رسمی (زبان، اتوماتا) تنها از طریق آزمایش و پرسش.
تست و مدلسازی مدارهای دیجیتال بدون آگاهی از طراحی داخلی.
از جعبهسیاه تا مدل – یادگیری فعال اتوماتا پاسخی به این نیاز مشترک است.
پس مسئله = یادگیری یک DFA
هر پیشوند = حالتی در ماشین مینیمال
اگر رفتار سیستم با تعداد محدودی حالت توصیف شود → یادگیری DFA مسئلهٔ اصلی است.
«یک سری مثال مثبت و منفی بده، بعد از روی اونا یاد بگیر.»
به این میگفتند مدل یادگیری منفعل (Passive Learning).
⚡ تعداد مثالها محدود، اما فضای فرضیهها نامتناهی.
پیدا کردن کوچکترین DFA هماهنگ با مثالها ← NP-hard
یعنی برای سیستمهای واقعی، عملاً غیرقابل انجام.
«چرا یادگیرنده فقط ساکت بنشیند؟ بگذار سؤال بپرسد!»
Minimally Adequate Teacher
معلم
کمینهٔ کافی
⏱️ پاسخ: بله/خیر – هزینهٔ O(1) در مدل نظری
🎯 پاسخ: «بله» یا یک رشتهٔ مخالف
با استفاده از جدول مشاهده (Observation Table) و تکرار:
✔ بسته بودن (Closed) ✔ سازگار بودن (Consistent)
➡ هر بار DFA حدس زده میشود، با مثال نقض اصلاح میگردد.
هر زبان منظم را میتوان در زمان چندجملهای و با دقت ۱۰۰٪ یاد گرفت (با دسترسی به معلم در مدل MAT)
این نقطهٔ آغاز تمام حوزهٔ Active Automata Learning بود.
«هر زبان منظم دقیقاً یک DFA مینیمال دارد و آن برابر است با کلاسهای همارزی نرود.»
u ≡ₗ v اگر و فقط اگر برای هر ادامهٔ w:
u·w ∈ L ⇔ v·w ∈ L
یعنی هیچ آزمایشی وجود ندارد که u و v را از هم جدا کند.
DFA مینیمال: هر کلاس = یک حالت.
| پیشوند (S) | ε | ۰ | ۱ |
|---|---|---|---|
| ε | ✅ | ✅ | ❌ |
| ۰ | ✅ | ❌ | ✅ |
| ۱ | ❌ | ✅ | ✅ |
| ۰۰ | … در حال یادگیری | ||
سطرها = پیشوندها (حالتهای کاندید) | ستونها = پسوندها (آزمایشها)
هر ترکیب s·a (پیشوند + حرف) با یکی از سطرهای موجود برابر باشد.
⚙️ اگر نباشد → آن را به S اضافه کن.
اگر دو سطر یکسان باشند، پس از اضافه شدن یک حرف هم باید خروجیشان یکسان بماند.
⚙️ اگر نباشد → پسوند جدید اضافه کن.
S = {ε}, E = {ε}, پرسوجوی عضویت
اگر خیر: S یا E را توسعه بده
ساخت M(S,E,T)
به معلم بده
✅ تأیید
الگوریتم پایان – DFA نهایی
➕ همهٔ پیشوندهای مثال نقض به S اضافه میشوند ← جدول گسترش مییابد.
«قبل از هر پرسش عضویت، میتوان سیستم را به حالت آغازین بازگرداند.»
نمیتواند «تلپورت» کند تا به نقطهٔ شروع برگردد
نمیتوان بدون قطع اتصال به حالت اولیه برگشت
پس از هر تراکنش، وضعیت تغییر میکند
نمیداند پرسش عضویت بعدی را از کدام حالت شروع کند ← اجرای مستقیم L* غیرممکن است.
دنبالهای h ∈ Σ* که اگر از هر دو حالت q₁, q₂ اجرا شود و خروجی یکسان بدهد، آن دو حالت به یک حالت پایانی یکسان ختم شوند.
دنبالهٔ ثابت، مستقل از خروجیها
درخت تصمیم – هر نماد بعدی بر اساس خروجی دیده شده انتخاب میشود (کارآمدتر)
بدون نیاز به Reset، با حفظ چند L* کپی موازی و گسترش تدریجی h، DFA درست را پیدا میکند.
⚙️ در بخش ۴ (اسلایدهای بعدی) بهطور کامل به الگوریتم Homing و Adaptive میپردازیم.
دنبالهٔ h ∈ Σ* یک توالی هومینگ است اگر:
اگر اجرای h از q₁ و q₂ خروجی یکسان دهد،
آنگاه به یک حالت پایانی یکسان ختم شوند.
🧪 با مشاهدهٔ خروجی، میتوان تشخیص داد در کدام «دستهٔ همارزی» قرار گرفتهایم.
بدون نیاز به Reset، با حفظ چندین L* کپی موازی و گسترش تدریجی توالی هومینگ، DFA درست را پیدا میکنیم.
فرض: حالت شروع q₁
فرض: حالت شروع q₂
فرض: حالت شروع q₃
شروع با h = ε
اجرای h و مشاهدهٔ خروجی
اگر L*ها جواب نادرست دادند ← h را با دنبالهٔ کشف اختلاف گسترش بده
تکرار تا h واقعی شود ← یکی از L*ها DFA درست را پیدا میکند
مدل PAC – چارچوب استاندارد یادگیری ماشین نظری
توسط Valiant (1984) معرفی شد – بنیان یادگیری محاسباتی.
یادگیرنده باید مدل h را بهگونهای بسازد که:
تنها راه ارتباط با دنیای خارج:
✦ x طبق توزیع D انتخاب میشود.
✦ L(x) برچسب واقعی (عضویت در زبان).
| مدل MAT (Angluin) | مدل PAC (Valiant) |
|---|---|
| ✅ معلم وجود دارد | ❌ معلم وجود ندارد |
| ✅ پرسش عضویت (هر رشته) | ❌ فقط نمونهٔ تصادفی |
| ✅ پرسش همارزی + مثال نقض | ❌ هیچ پرسشی امکان ندارد |
| 🎯 یادگیری دقیق (exact) | 🎯 یادگیری تقریبی (approximate) |
اگر یک کلاس زبان در مدل MAT قابل یادگیری دقیق باشد،
آنگاه در مدل PAC نیز قابل یادگیری است.
الگوریتم L* و سایر الگوریتمهای MAT را میتوان
به الگوریتمهای PAC تبدیل کرد.
قدرت یادگیری مدل پرسش و پاسخ
به مدل نمونهگیری تصادفی تعمیم مییابد.
بخش اول: بنیادها و الگوریتم کلاسیک
بخش دوم: تعمیمها، کاربردها و چشمانداز
از آبیِ نظریه تا صورتیِ کاربرد – همافزایی دو نگاه برای کشف رفتار سیستمهای ناشناخته