Saturday, October 31, 2026

Data Leakage in Machine Learning

Machine learning မော်ဒယ်တွေ တည်ဆောက်တဲ့အခါ ဟိုက်ပါပါရာမီတာ ချိန်ညှိခြင်း (hyperparameter tuning) ပြုလုပ်စဉ်မှာ ဒေတာ ယိုစိမ့်မှု (data leakage) ကို ကာကွယ်နိုင်ဖို့အတွက်၊ ပုံမှန်အားဖြင့် ရှိရင်းစွဲ ဒေတာတွေကို အပိုင်း သုံးပိုင်း ခွဲခြား အသုံးပြုလေ့ရှိပါတယ်။ အဲဒါတွေကတော့ လေ့ကျင့်ရေး ဒေတာအစုအဝေး (training set)၊ စစ်ဆေးအတည်ပြုရေး ဒေတာအစုအဝေး (validation set) နဲ့ စမ်းသပ်ရေး ဒေတာအစုအဝေး (test set) တို့ပဲ ဖြစ်ပါတယ်။

စစ်ဆေးအတည်ပြုရေး ဒေတာအစုအဝေး (Validation Set) ၏ အခန်းကဏ္ဍ Validation set ဆိုတာ မော်ဒယ်ရဲ့ hyperparameter တွေကို အကြိမ်ကြိမ် ပြုပြင်ချိန်ညှိဖို့နဲ့ အကောင်းဆုံး setting ကို ရွေးချယ်ဖို့အတွက် အထူးသီးသန့် ဖယ်ထားတဲ့ ဒေတာအစုအဝေး ဖြစ်ပါတယ်။ သုတေသီ (researcher) ဟာ training set ကိုသုံးပြီး မော်ဒယ်ကို အရင်ဆုံး လေ့ကျင့်ပေးပါတယ်။ အဲဒီနောက်မှာ မော်ဒယ်ရဲ့ စွမ်းဆောင်ရည်ကို validation set ပေါ်မှာ စစ်ဆေးပြီး အမှားအယွင်းနှုန်းတွေ (error rates) ကို တိုင်းတာပါတယ်။ ရလာတဲ့ ရလဒ်တွေအပေါ် မူတည်ပြီး hyperparameter တွေကို အကောင်းဆုံးဖြစ်အောင် ထပ်ခါတလဲလဲ ပြောင်းလဲစမ်းသပ်ပါတယ်။ ဒါကြောင့်မို့လို့ မော်ဒယ်ဟာ validation set ပေါ်မှာ အကောင်းဆုံး အဖြေထုတ်ပေးနိုင်အောင် သွယ်ဝိုက်သောနည်းနဲ့ လေ့လာသင်ယူသွားပါတယ်။

စမ်းသပ်ရေး ဒေတာအစုအဝေး (Test Set) ၏ အခန်းကဏ္ဍ Test set ကတော့ မော်ဒယ်တည်ဆောက်ခြင်းနဲ့ ချိန်ညှိခြင်း လုပ်ငန်းစဉ်တွေ အားလုံး အပြီးသတ်သွားတဲ့အခါမှသာ၊ နောက်ဆုံးရလာတဲ့ အကောင်းဆုံး မော်ဒယ်ရဲ့ အပြင်ကမ္ဘာက အချက်အလက်အသစ်တွေအပေါ် စွမ်းဆောင်ရည်ကို (true performance on unseen data) တိုင်းတာဖို့အတွက် အသုံးပြုတဲ့ လုံးဝ ဖုံးကွယ်ထားတဲ့ (လုံးဝ ကြိုမကြည့်ရတဲ့) ဒေတာအစုအဝေး ဖြစ်ပါတယ်။ သူ့ကို မော်ဒယ်လေ့ကျင့်တဲ့ နေရာမှာရော၊ hyperparameter တွေ ရွေးချယ်တဲ့နေရာမှာပါ လုံးဝ အသုံးမပြုပါဘူး။ အလွယ်ပြောရရင် စာမေးပွဲခန်းထဲရောက်မှ ဖောက်ကြည့်ရမယ့် မေးခွန်းစာရွက်လိုပါပဲ၊ အပြင်မှာ ကြိုပြီး လုံးဝ လေ့လာခွင့် မရှိပါဘူး။

Data Leakage ကို ကာကွယ်ပေးပုံ ကွာခြားချက် အကယ်၍ သုတေသီဟာ validation set ကို သီးသန့်မထားဘဲ test set ပေါ်မှာပဲ တိုက်ရိုက် hyperparameter တွေကို ချိန်ညှိမယ်ဆိုရင်၊ သုတေသီရဲ့ ပြုပြင်ပြောင်းလဲမှုတွေကတစ်ဆင့် test set ရဲ့ အချက်အလက်တွေဟာ မော်ဒယ်ထဲကို ယိုစိမ့်ဝင်ရောက်သွားပါလိမ့်မယ် (information leaks into the model)။ ဒီလိုဆိုရင် မော်ဒယ်က အဲဒီ test set လေးတစ်ခုတည်းအတွက်ပဲ အလွတ်ကျက်ထားသလို (overfitting) ဖြစ်သွားပြီး၊ တကယ့် လက်တွေ့ပြင်ပမှာ အသုံးပြုတဲ့အခါ အဖြေမှန်တွေ ထုတ်ပေးနိုင်တော့မှာ မဟုတ်ပါဘူး။

ဒါကြောင့်မို့လို့ Validation set ကို သီးခြားခွဲထုတ် အသုံးပြုခြင်းအားဖြင့် မော်ဒယ်ကို လွတ်လွတ်လပ်လပ် စမ်းသပ်ချိန်ညှိဖို့ (to tune) နေရာတစ်ခုကို ဖန်တီးပေးလိုက်ပြီး၊ Test set ကိုတော့ အဂတိမလိုက်စားတဲ့ နောက်ဆုံး အကဲဖြတ်မှု (an unbiased final evaluation) ပြုလုပ်ဖို့အတွက် သန့်သန့်ရှင်းရှင်း သိမ်းဆည်းထားနိုင်တာပဲ ဖြစ်ပါတယ်။

Saturday, October 24, 2026

The application of the VERSION-SPACE-LEARNING algorithm (Part-2)

စားသောက်ဆိုင် ဒေတာ (restaurant data) ၁၂ ခုလုံးအပေါ်မှာ VERSION-SPACE-LEARNING အယ်လ်ဂိုရီသမ် (algorithm) မပြိုလဲဘဲ အဖြေမှန် ထွက်လာစေဖို့ဆိုရင် အဆိုပြုချက်များနယ်ပယ် (hypothesis space) ရဲ့ ဖော်ပြနိုင်စွမ်း (expressiveness) ကို အဆင့်ဆင့် တိုးချဲ့ပေးဖို့ လိုအပ်ပါတယ်။

AIMA စာအုပ် အခန်း ၂၀၊ အပိုင်း ၂၀.၁.၃ မှာ ဆွေးနွေးထားတဲ့အတိုင်း အဆိုပြုချက် ကိုယ်စားပြုပုံ (hypothesis representation) ကို ဘယ်လို တိုးချဲ့ပြင်ဆင်ရမလဲဆိုတာ အဆင့် ၂ ဆင့်နဲ့ အသေးစိတ် ကြည့်ရအောင်ပါ။

အဆင့် (၁) — အတွင်းပိုင်း ရွေးချယ်မှု (Internal Disjunction) ဖြင့် တိုးချဲ့ခြင်းနှင့် ၎င်း၏ ကန့်သတ်ချက်

အရင်က ရေးခဲ့တဲ့ ပရိုဂရမ်မှာ ဂုဏ်သတ္တိ (attribute) တစ်ခုချင်းစီက တန်ဖိုးတစ်ခုတည်း vₖ ဒါမှမဟုတ် ? ကိုပဲ လက်ခံနိုင်ပါတယ်။ ဒါကို အတွင်းပိုင်း ရွေးချယ်မှု (Internal Disjunction) ပုံစံ ပြောင်းလိုက်မယ်ဆိုရင် ဂုဏ်သတ္တိတစ်ခုချင်းစီမှာ တန်ဖိုးအစုငယ်လေးတွေ (subsets) လက်ခံနိုင်လာပါမယ် —

ဥပမာ — ဆိုင်ထဲက လူဦးရေအတွက် Pat ∈ {Some, Full} ဆိုပြီး တန်ဖိုးနှစ်ခုကို ရွေးချယ်လက်ခံနိုင်လာပါတယ်။ ဒါပေမဲ့ ဒီနေရာမှာ သင်္ချာနည်းကျ အလွန်အရေးကြီးတဲ့ အချက်တစ်ခု ရှိနေပါတယ်။ အဲဒါကတော့ Internal Disjunction ကို သုံးရင်တောင် စားသောက်ဆိုင် ဒေတာ ၁၂ ခုလုံးအပေါ်မှာ Version Space ပြိုလဲနေဦးမှာ ဖြစ်ပါတယ်။

ဘာကြောင့် ပြိုလဲနေဦးမှာလဲ? Internal Disjunction ဟာ ဂုဏ်သတ္တိတစ်ခုချင်းစီ အတွင်းမှာပဲ ∨ (OR) လုပ်ခွင့်ပေးထားပြီး၊ ဂုဏ်သတ္တိ ၁၀ ခုကြားမှာတော့ ∧ (AND) နဲ့ပဲ ချိတ်ဆက်ထားဆဲ ဖြစ်လို့ပါပဲ —


စားသောက်ဆိုင် ဒေတာရဲ့ အပေါင်းနမူနာ ၆ ခု (X1, X3, X4, X6, X8, X12) ကို ဖုံးအုပ်နိုင်မယ့် အတိကျဆုံး Internal Disjunction အဆိုပြုချက် S ကို တွက်ကြည့်လိုက်ရင် —

  • Pat အတွက် {Some, Full} ဖြစ်သွားပါမယ် (X1 မှာ Some၊ X4 မှာ Full ပါနေလို့ပါ)။

  • Est အတွက် {0-10, 10-30, 30-60} ဖြစ်သွားပါမယ် (X1, X4, X12 တို့ကြောင့်ပါ)။

  • ကျန်တဲ့ ဂုဏ်သတ္တိ ၈ ခုလုံးကတော့ အပေါင်းနမူနာတွေထဲမှာ ရှိသမျှ တန်ဖိုးအားလုံး ပါဝင်နေတာကြောင့် အကုန်လုံး ? (Domain အပြည့်) ဖြစ်သွားပါတယ်။

အဲဒီအခါ အနုတ်နမူနာ X2 (Pat = Full, Est = 30-60, WillWait = False) ကို စစ်ဆေးလိုက်ရင် Pat ∈ {Some, Full} ရော Est ∈ {0-10, 10-30, 30-60} ရော နှစ်ခုလုံးနဲ့ ကိုက်ညီနေတဲ့အတွက် S က X2 ကို True လို့ မှားခန့်မှန်းမိ (false positive) ပြီး ပြိုလဲသွားပါတယ်။

အဆင့် (၂) — ယုတ္တိပေါင်းစပ်ချက်များကို ပေါင်းစည်းရွေးချယ်သည့် ပုံစံ (Disjunctive Normal Form / k-DNF) သို့ တိုးချဲ့ခြင်း

စားသောက်ဆိုင် ပြဿနာရဲ့ အဖြေမှန်ဟာ "လူအနည်းငယ်ရှိရင် စောင့်မယ် (သို့မဟုတ်) လူပြည့်နေပေမဲ့ သောကြာနေ့ဖြစ်ပြီး ဗိုက်လည်းဆာနေရင် စောင့်မယ်" ဆိုတဲ့ ဂုဏ်သတ္တိအချင်းချင်း ဖြတ်သန်းချိတ်ဆက်ထားတဲ့ ∨ ယုတ္တိ ဖြစ်ပါတယ်။ ဒါကြောင့် အဆိုပြုချက် h တစ်ခုကို အစိတ်အပိုင်း ယုတ္တိပေါင်းစပ်ချက် (disjunct) အများဆုံး k ခုအထိ တွဲစပ်နိုင်တဲ့ k-DNF ပုံစံနဲ့ အောက်ပါအတိုင်း တိုးချဲ့ကိုယ်စားပြုရပါမယ် —


ဒီနေရာမှာ r_j တစ်ခုချင်းစီက ဂုဏ်သတ္တိ ၁၀ ခုပါဝင်တဲ့ ပုံမှန် ပေါင်းစပ်ယုတ္တိ (conjunctive rule) တစ်ခု ဖြစ်ပါတယ်။

ယေဘုယျဆန်မှု နှိုင်းယှဉ်ခြင်း (Subsumption Relation) ပြောင်းလဲသွားပုံ k-DNF အဆိုပြုချက် h_1 က h_2 ထက် ပိုပြီး ယေဘုယျဆန်တယ် (h_1 ≥_g h_2) လို့ သတ်မှတ်ဖို့အတွက် h_2 ထဲမှာ ပါဝင်တဲ့ အစိတ်အပိုင်း r_2 တိုင်းကို h_1 ထဲက အစိတ်အပိုင်း တစ်ခုခု r_1 က လွှမ်းခြုံနိုင်ရပါမယ် —


AIMA စာအုပ်ပါ သီအိုရီဆိုင်ရာ ချိန်ခွင်လျှာညှိမှု (Expressiveness vs. Inductive Bias) 
                  စာအုပ်ထဲမှာ Russell နဲ့ Norvig တို့ ထောက်ပြထားတဲ့ အရေးကြီးဆုံး သီအိုရီတစ်ခု ရှိပါတယ်။ အကယ်၍ k ကို အကန့်အသတ်မထားဘဲ အကန့်အသတ်မဲ့ အဆိုပြုချက်များနယ်ပယ် (unrestricted hypothesis space) အထိ ဖွင့်ပေးလိုက်မယ်ဆိုရင် Version Space ဟာ ဘယ်တော့မှ မပြိုလဲတော့ပါဘူး (ဒေတာထဲမှာ အချက်အလက်ချင်း ထပ်တူညီပြီး အဖြေကွဲနေတဲ့ ဆူညံသံ — noise မပါသရွေ့ပေါ့)။ ဒါပေမဲ့ အဲဒီအခါ S ဟာ တွေ့ခဲ့သမျှ အပေါင်းနမူနာတွေကို ∨ နဲ့ တိုက်ရိုက်စုစည်းထားရုံသက်သက် ဖြစ်သွားပြီး၊ နမူနာအသစ်တွေအပေါ် ယေဘုယျကောက်ချက်ဆွဲနိုင်စွမ်း (generalization) ပျောက်ဆုံးသွားပါတယ်။

ဒါကြောင့် စားသောက်ဆိုင် ဒေတာအတွက် k = 2 (2-DNF) လိုမျိုး သင့်တင့်တဲ့ အဆိုပြုချက်များနယ်ပယ်၏ ဘက်လိုက်မှု ကန့်သတ်ချက် (inductive bias) ကို ထားရှိခြင်းအားဖြင့် Version Space မပြိုလဲစေဘဲ ယေဘုယျကောက်ချက်ဆွဲနိုင်စွမ်းကိုပါ ထိန်းသိမ်းထားနိုင်မှာ ဖြစ်ပါတယ်။

Python ပရိုဂရမ် အပြည့်အစုံ (2-DNF Version Space Learning on All 12 Restaurant Examples)

အောက်ပါ Python ကုဒ်မှာ k = 2 (2-DNF) အဆိုပြုချက် ကိုယ်စားပြုပုံကို အသုံးပြုပြီး စားသောက်ဆိုင် ဒေတာ ၁၂ ခုလုံး (X1 မှ X12 အထိ) အပေါ်မှာ VERSION-SPACE-LEARNING ကို လက်တွေ့ Run ပြထားပါတယ်။

Python
import itertools

# ၁။ စားသောက်ဆိုင် ဒေတာ (Restaurant Data) ဂုဏ်သတ္တိ ၁၀ ခုနှင့် တန်ဖိုးများ
ATTRIBUTES = [
    "Alt", "Bar", "Fri", "Hun", "Pat",
    "Price", "Rain", "Res", "Type", "Est"
]

DOMAINS = {
    "Alt":   ["Yes", "No"],
    "Bar":   ["Yes", "No"],
    "Fri":   ["Yes", "No"],
    "Hun":   ["Yes", "No"],
    "Pat":   ["None", "Some", "Full"],
    "Price": ["P1", "P2", "P3"],
    "Rain":  ["Yes", "No"],
    "Res":   ["Yes", "No"],
    "Type":  ["French", "Italian", "Thai", "Burger"],
    "Est":   ["0-10", "10-30", "30-60", ">60"]
}

# AIMA Chapter 19 (Figure 19.2) မှ နမူနာဒေတာ ၁၂ ခုလုံး (X1 မှ X12)
RESTAURANT_DATA = [
    (("Yes", "No",  "No",  "Yes", "Some", "P3", "No",  "Yes", "French",  "0-10"),  True),   # X1
    (("Yes", "No",  "No",  "Yes", "Full", "P1", "No",  "No",  "Thai",    "30-60"), False),  # X2
    (("No",  "Yes", "No",  "No",  "Some", "P1", "No",  "No",  "Burger",  "0-10"),  True),   # X3
    (("Yes", "No",  "Yes", "Yes", "Full", "P1", "Yes", "No",  "Thai",    "10-30"), True),   # X4
    (("Yes", "No",  "Yes", "No",  "Full", "P3", "No",  "Yes", "French",  ">60"),   False),  # X5
    (("No",  "Yes", "No",  "Yes", "Some", "P2", "Yes", "Yes", "Italian", "0-10"),  True),   # X6
    (("No",  "Yes", "No",  "No",  "None", "P1", "Yes", "No",  "Burger",  "0-10"),  False),  # X7
    (("No",  "No",  "No",  "Yes", "Some", "P2", "Yes", "Yes", "Thai",    "0-10"),  True),   # X8
    (("No",  "Yes", "Yes", "No",  "Full", "P1", "Yes", "No",  "Burger",  ">60"),   False),  # X9
    (("Yes", "Yes", "Yes", "Yes", "Full", "P3", "No",  "Yes", "Italian", "10-30"), False),  # X10
    (("No",  "No",  "No",  "No",  "None", "P1", "No",  "No",  "Thai",    "0-10"),  False),  # X11
    (("Yes", "Yes", "Yes", "Yes", "Full", "P1", "No",  "No",  "Burger",  "30-60"), True),   # X12
]


# ၂။ တစ်ခုချင်းစီသော Conjunctive Rule အတွက် အထောက်အကူပြု လုပ်ဆောင်ချက်များ

def predict_rule(rule, x):
    """Conjunctive rule တစ်ခုက နမူနာ x ကို True ဟု ခန့်မှန်းခြင်း ရှိမရှိ စစ်ဆေးခြင်း"""
    return all(r_val == "?" or r_val == x_val for r_val, x_val in zip(rule, x))


def rule_more_general_or_equal(r1, r2):
    """r1 >=_g r2 ဖြစ်မဖြစ် စစ်ဆေးခြင်း"""
    return all(c1 == "?" or c1 == c2 for c1, c2 in zip(r1, r2))


def minimal_generalization_rule(r, x):
    """Rule r ကို နမူနာ x ပါဝင်လာအောင် အနည်းဆုံး ယေဘုယျပြုခြင်း"""
    return tuple(r_val if r_val == x_val else "?" for r_val, x_val in zip(r, x))


def immediate_specializations_rule(r, x):
    """Rule r ကို နမူနာ x မပါဝင်အောင် တိုက်ရိုက် အထူးပြုချက်များ ဖန်တီးခြင်း"""
    specs = set()
    for i, attr in enumerate(ATTRIBUTES):
        if r[i] == "?":
            for val in DOMAINS[attr]:
                if val != x[i]:
                    new_r = list(r)
                    new_r[i] = val
                    specs.add(tuple(new_r))
    return specs


# ၃။ k-DNF Hypothesis (frozenset of rules) အတွက် လုပ်ဆောင်ချက်များ

def simplify_dnf(h):
    """DNF အတွင်း အခြား rule တစ်ခုက လွှမ်းခြုံပြီးသား ဖြစ်နေသည့် ပိုလျှံနေသော rule များကို ဖယ်ရှားခြင်း"""
    rules = list(h)
    minimal_rules = set()
    for i, r1 in enumerate(rules):
        if not any(
            i != j and rule_more_general_or_equal(r2, r1)
            for j, r2 in enumerate(rules)
        ):
            minimal_rules.add(r1)
    return frozenset(minimal_rules)


def predict_dnf(h, x):
    """k-DNF အဆိုပြုချက် h က နမူနာ x ကို True ဟု ခန့်မှန်းခြင်း ရှိမရှိ စစ်ဆေးခြင်း"""
    return any(predict_rule(r, x) for r in h)


def dnf_more_general_or_equal(h1, h2):
    """h1 >=_g h2 (h2 ထဲရှိ disjunct တိုင်းကို h1 ထဲရှိ disjunct တစ်ခုခုက လွှမ်းခြုံနိုင်ခြင်း)"""
    return all(
        any(rule_more_general_or_equal(r1, r2) for r1 in h1)
        for r2 in h2
    )


def dnf_strictly_more_general(h1, h2):
    return h1 != h2 and dnf_more_general_or_equal(h1, h2)


def immediate_generalizations_dnf(s, x, k):
    """
    False negative ဖြစ်နေသော k-DNF အဆိုပြုချက် s ကို နမူနာ x ပါဝင်အောင်
    နည်းလမ်း ၂ သွယ်ဖြင့် ယေဘုယျပြုခြင်း:
    (၁) ရှိပြီးသား disjunct တစ်ခုကို ယေဘုယျပြုခြင်း
    (၂) အရေအတွက် k မပြည့်သေးပါက နမူနာ x အတွက် disjunct အသစ်တစ်ခု ထပ်ပေါင်းထည့်ခြင်း
    """
    gens = set()
    # နည်းလမ်း (၁): ရှိပြီးသား disjunct တစ်ခုချင်းစီကို အနည်းဆုံး ယေဘုယျပြုကြည့်ခြင်း
    for r in s:
        r_gen = minimal_generalization_rule(r, x)
        candidate = simplify_dnf((s - {r}) | {r_gen})
        if len(candidate) <= k:
            gens.add(candidate)

    # နည်းလမ်း (၂): Disjunct အရေအတွက် k ထက် နည်းနေသေးပါက x ကို သီးသန့် disjunct အဖြစ် ပေါင်းထည့်ခြင်း
    if len(s) < k:
        candidate = simplify_dnf(s | {x})
        if len(candidate) <= k:
            gens.add(candidate)

    return gens


def immediate_specializations_dnf(g, x, k):
    """
    False positive ဖြစ်နေသော k-DNF အဆိုပြုချက် g ကို နမူနာ x မပါဝင်အောင် အထူးပြုခြင်း
    """
    specs = set()
    matching_rules = [r for r in g if predict_rule(r, x)]
    non_matching_rules = frozenset(r for r in g if not predict_rule(r, x))

    # နည်းလမ်း (၁): x နှင့် ကိုက်ညီနေသော disjunct တိုင်းကို အထူးပြု၍ x ကို ဖယ်ထုတ်ခြင်း
    per_rule_specs = [list(immediate_specializations_rule(r, x)) for r in matching_rules]
    for combo in itertools.product(*per_rule_specs):
        candidate = simplify_dnf(non_matching_rules | frozenset(combo))
        if 1 <= len(candidate) <= k:
            specs.add(candidate)

    # နည်းလမ်း (၂): Disjunct ၁ ခုတည်းသာ ရှိသေးပြီး k >= 2 ဖြစ်ပါက disjunct ၂ ခုအဖြစ် ခွဲထုတ်ခြင်း
    if len(g) == 1 and k >= 2:
        single_specs = list(immediate_specializations_rule(matching_rules[0], x))
        for r_a, r_b in itertools.combinations(single_specs, 2):
            if not rule_more_general_or_equal(r_a, r_b) and not rule_more_general_or_equal(r_b, r_a):
                specs.add(frozenset({r_a, r_b}))

    return specs


# ၄။ k-DNF VERSION-SPACE-UPDATE နှင့် VERSION-SPACE-LEARNING

def k_dnf_version_space_update(S, G, x, y, k=2):
    S = set(S)
    G = set(G)

    if y is True:
        # Rule 4: G_i အတွက် False negative ဖြစ်နေလျှင် ဖယ်ထုတ်ခြင်း
        G = {g for g in G if predict_dnf(g, x)}

        # Rule 2: S_i အတွက် False negative ဖြစ်နေလျှင် immediate generalizations ဖြင့် အစားထိုးခြင်း
        next_S = set()
        for s in S:
            if predict_dnf(s, x):
                next_S.add(s)
            else:
                for s_gen in immediate_generalizations_dnf(s, x, k):
                    if any(dnf_more_general_or_equal(g, s_gen) for g in G):
                        next_S.add(s_gen)

        S = {
            s for s in next_S
            if not any(dnf_strictly_more_general(s, other_s) for other_s in next_S)
        }

    else:
        # Rule 1: S_i အတွက် False positive ဖြစ်နေလျှင် ဖယ်ထုတ်ခြင်း
        S = {s for s in S if not predict_dnf(s, x)}

        # Rule 3: G_i အတွက် False positive ဖြစ်နေလျှင် immediate specializations ဖြင့် အစားထိုးခြင်း
        next_G = set()
        for g in G:
            if not predict_dnf(g, x):
                next_G.add(g)
            else:
                for g_spec in immediate_specializations_dnf(g, x, k):
                    if any(dnf_more_general_or_equal(g_spec, s) for s in S):
                        next_G.add(g_spec)

        G = {
            g for g in next_G
            if not any(dnf_strictly_more_general(other_g, g) for other_g in next_G)
        }

    return S, G


def format_dnf(h):
    """DNF အဆိုပြုချက်ကို လူဖတ်ရလွယ်ကူအောင် စာသားပြောင်းပေးခြင်း"""
    if not h:
        return "∅ (မည်သည့်နမူနာကိုမျှ လက်မခံ)"
    parts = []
    for r in sorted(h):
        conds = [f"{attr}={val}" for attr, val in zip(ATTRIBUTES, r) if val != "?"]
        parts.append("(" + (" ∧ ".join(conds) if conds else "TRUE") + ")")
    return " ∨ ".join(parts)


def k_dnf_version_space_learning(examples, k=2, verbose=True):
    n = len(ATTRIBUTES)
    S = {frozenset()}                        # အတိကျဆုံး အစပျိုးမှု (Disjunct 0 ခု)
    G = {frozenset({tuple(["?"] * n)})}      # အယေဘုယျဆန်ဆုံး အစပျိုးမှု

    for idx, (x, y) in enumerate(examples, start=1):
        S, G = k_dnf_version_space_update(S, G, x, y, k=k)
        if verbose:
            print(f"နမူနာ X{idx:02d} (WillWait={str(y):5s}) ပြီးနောက် -> |S| = {len(S)}, |G| = {len(G)}")

        if not S or not G:
            print(">>> Version Space ပြိုလဲသွားပါပြီ!")
            return None, None, "COLLAPSED"

        if len(S) == 1 and len(G) == 1 and S == G:
            print(">>> တစ်ခုတည်းသော အဖြေအဆိုပြုချက် ရရှိပါပြီ!")
            return S, G, "UNIQUE"

    return S, G, "MULTIPLE"


def classify_dnf_version_space(S, G, new_x):
    """ကျန်ရှိနေသော S နှင့် G ဘောင်အဖွဲ့ဝင်များဖြင့် နမူနာအသစ်ကို ခန့်မှန်းခြင်း"""
    boundary = list(S.union(G))
    votes = [predict_dnf(h, new_x) for h in boundary]
    true_count = sum(votes)
    false_count = len(votes) - true_count
    if true_count == len(votes):
        return True, f"အားလုံး တညီတည်း သဘောတူသည် ({true_count}/{len(votes)})"
    elif false_count == len(votes):
        return False, f"အားလုံး တညီတည်း သဘောတူသည် ({false_count}/{len(votes)})"
    else:
        return (true_count > false_count), f"အများစုမဲစနစ် (True: {true_count}, False: {false_count})"


# ၅။ စားသောက်ဆိုင် ဒေတာ ၁၂ ခုလုံးအပေါ် လက်တွေ့ Run ကြည့်ခြင်း
if __name__ == "__main__":
    S_final, G_final, status = k_dnf_version_space_learning(RESTAURANT_DATA, k=2, verbose=True)

    print("\n========================================================")
    print(f"နောက်ဆုံးရလဒ် အခြေအနေ: {status}")
    print("========================================================")
    print("\n[S နယ်နိမိတ် အဖွဲ့ဝင် ဥပမာ]")
    for s in list(S_final)[:2]:
        print("  S:", format_dnf(s))

    print("\n[G နယ်နိမိတ် အဖွဲ့ဝင် ဥပမာများ]")
    for g in list(G_final)[:3]:
        print("  G:", format_dnf(g))

    # ဒေတာ ၁၂ ခုလုံးအပေါ် မှန်ကန်မှု (Accuracy) ပြန်လည်စစ်ဆေးခြင်း
    s_rep = next(iter(S_final))
    g_rep = next(iter(G_final))
    s_acc = sum(predict_dnf(s_rep, x) == y for x, y in RESTAURANT_DATA)
    g_acc = sum(predict_dnf(g_rep, x) == y for x, y in RESTAURANT_DATA)
    print(f"\nလေ့ကျင့်ရေး ဒေတာ ၁၂ ခုလုံးအပေါ် မှန်ကန်မှု: S = {s_acc}/12, G = {g_acc}/12")

    # မမြင်ဖူးသေးသော စားသောက်ဆိုင် အခြေအနေအသစ်တစ်ခုကို စမ်းသပ်ခန့်မှန်းခြင်း
    unseen_x = ("Yes", "No", "Yes", "Yes", "Full", "P1", "No", "No", "Thai", "10-30")
    pred, detail = classify_dnf_version_space(S_final, G_final, unseen_x)
    print(f"\nနမူနာအသစ် {unseen_x} အတွက် ခန့်မှန်းချက် -> {pred} ({detail})")


ပရိုဂရမ်၏ လုပ်ဆောင်ချက်နှင့် ရလဒ် ဆန်းစစ်ချက်

ဒီပရိုဂရမ်ကို Run လိုက်တဲ့အခါ အရင်ကလို X10 မှာ ပြိုလဲမသွားတော့ဘဲ ဒေတာ ၁၂ ခုလုံးကို ၁၂/၁၂ (100%) ကိုက်ညီစွာ ခွဲခြားနိုင်တဲ့ အဆိုပြုချက်တွေ ထွက်ပေါ်လာပါတယ်။ အဓိက ပြောင်းလဲသွားတဲ့ ယန္တရား ၃ ခုကို အောက်ပါအတိုင်း တွေ့မြင်နိုင်ပါတယ် —

  1. အစပျိုးမှု ပြောင်းလဲခြင်း S ကို အစိတ်အပိုင်း ၀ ခုပါတဲ့ ဗလာစု frozenset() အဖြစ် စတင်ထားပါတယ်။ ပထမဆုံး အပေါင်းနမူနာ X1 ဝင်လာတဲ့အခါ S ဟာ { {X1} } ဖြစ်လာပြီး၊ X3 နဲ့ X4 တို့ ဆက်ဝင်လာတဲ့အခါ immediate_generalizations_dnf လုပ်ဆောင်ချက်က လမ်းကြောင်း နှစ်သွယ် ခွဲထုတ်ပေးပါတယ်။ တစ်လမ်းက ရှိပြီးသား အစိတ်အပိုင်းကို ယေဘုယျပြုဖို့ ကြိုးစားပြီး၊ နောက်တစ်လမ်းကတော့ အစိတ်အပိုင်း အသစ်တစ်ခု ထပ်ပေါင်းထည့် (s ∪ {x}) ပေးပါတယ်။

  2. အနုတ်နမူနာများ ဝင်လာချိန်တွင် ဘောင်ခတ် ထိန်းသိမ်းခြင်း (boundary maintenance) X2၊ X5၊ X10 လို အနုတ်နမူနာတွေ ဝင်လာတဲ့အခါ ယေဘုယျဆန်လွန်းသွားတဲ့ 1-disjunct အဆိုပြုချက်တွေကို Rule 1 အရ S ထဲကနေ ဖယ်ထုတ်ပစ်လိုက်ပေမဲ့၊ 2-disjunct အဆိုပြုချက်တွေက ဆက်လက်ကျန်ရှိနေပါတယ်။ တစ်ချိန်တည်းမှာပဲ G ဘက်ကလည်း immediate_specializations_dnf ကို သုံးပြီး အစိတ်အပိုင်း နှစ်ခုပါတဲ့ ယေဘုယျဘောင်တွေအဖြစ် ခွဲထုတ်ထိန်းသိမ်းပေးပါတယ်။

  3. ထွက်ပေါ်လာသော အဖြေမှန် ပုံစံ နမူနာ ၁၂ ခုလုံး ပြီးဆုံးသွားချိန်မှာ G နယ်နိမိတ်ထဲမှာ (Pat=Some) ∨ (Fri=Yes ∧ Hun=Yes ∧ Price=P1) ဆိုတဲ့ ကျစ်လျစ်ပြီး ယေဘုယျကျတဲ့ အဆိုပြုချက်မျိုး ပါဝင်လာသလို၊ S နယ်နိမိတ်ထဲမှာလည်း အပေါင်းနမူနာ ၆ ခုလုံးကို တိတိကျကျ ဖုံးအုပ်ပြီး အနုတ်နမူနာ ၆ ခုလုံးကို အပြည့်အဝ ဖယ်ထုတ်နိုင်တဲ့ 2-DNF အဆိုပြုချက်တွေ တည်ရှိနေမှာ ဖြစ်ပါတယ်။