The application of the VERSION-SPACE-LEARNING algorithm

VERSION-SPACE-LEARNING အယ်လ်ဂိုရီသမ် (Candidate Elimination လို့လည်း ခေါ်တယ်။) 

            ကို Restaurant Data အပေါ် အသုံးချရာတွင်၊ ဖြစ်နိုင်ချေရှိသော ယူဆချက်များ (hypotheses) အားလုံးပါဝင်သည့် 'Version Space' တစ်ခုကို တည်ဆောက်ပြီး ဥပမာ (examples) တစ်ခုစီတိုင်းအတွက် ကိုက်ညီမှုရှိသော ယူဆချက်များကို စစ်ထုတ်သွားခြင်း ဖြစ်တယ်။

Restaurant Data တွင် "WillWait" ဟူသော Boolean target (Yes/No) ကို ခန့်မှန်းရန်အတွက် Alternate, Bar, Fri/Sat, Hungry, Patrons, Price, Raining, Reservation, Type, Est ဟူသော input attribute (၁၀) ခု ပါဝင်တယ်။

VERSION-SPACE-LEARNING အယ်လ်ဂိုရီသမ် အလုပ်လုပ်ပုံမှာ အောက်ပါအတိုင်း ဖြစ်ပါတယ်။

• Version Space ကို ဘောင်ခတ်ခြင်း: Version Space (V) အား ယေဘုယျအကျဆုံး ယူဆချက်များပါဝင်သည့် G-set နှင့်၊ အတိကျဆုံးဖြစ်အောင် ကန့်သတ်ထားသည့် ယူဆချက်များပါဝင်သည့် S-set တို့ကို အသုံးပြု၍ ဘောင်ခတ် ကိုယ်စားပြုဖော်ပြသည်။

• Positive Example များ (WillWait = Yes): အယ်လ်ဂိုရီသမ်သည် ဥပမာအသစ်နှင့် ကိုက်ညီစေရန် S-set ထဲရှိ ယူဆချက်များကို ပိုမိုယေဘုယျကျအောင် (Generalize) ပြောင်းလဲပေးပြီး၊ ၎င်းဥပမာနှင့် ကိုက်ညီမှုမရှိသော G-set ထဲမှ ယူဆချက်များကို ဖယ်ရှားသည်။

• Negative Example များ (WillWait = No): ဥပမာအသစ်အား ဖယ်ထုတ်နိုင်ရန် G-set ထဲရှိ ယူဆချက်များကို ပိုမိုတိကျအောင် (Specialize) ခွဲဖြာပြောင်းလဲပေးပြီး၊ ၎င်းဥပမာနှင့် ကိုက်ညီနေသော (မှားယွင်းနေသော) S-set ထဲမှ ယူဆချက်များကို ဖယ်ရှားသည်။

Restaurant Data ပေါ်တွင် အသုံးချခြင်း၏ ရလဒ်နှင့် တွေ့ရှိချက် (Limitation) 

            Conjuntive Hypothesis (AND logic သက်သက်) ကိုသာ အသုံးပြုထားသည့် မူလ Version Space Learning ဖြင့် ဤ Restaurant Data ကို တွက်ချက်ပါက၊ အယ်လ်ဂိုရီသမ်သည် အစပိုင်း ဥပမာအနည်းငယ်တွင် ပုံမှန်အလုပ်လုပ်သော်လည်း နောက်ပိုင်းတွင် Version Space ပြိုကွဲသွားခြင်း (Empty ဖြစ်သွားခြင်း) ကို ကြုံတွေ့ရမည် ဖြစ်သည်။ အကြောင်းရင်းမှာ Positive Example မျိုးစုံ (ဥပမာ x1, x3, x4) များ၌ တူညီသော attribute တန်ဖိုးများ မရှိသလောက် နည်းပါးသောကြောင့်၊ S-set သည် လျင်မြန်စွာပင် အရာအားလုံးနှင့် ကိုက်ညီသည့် < ?, ?, ?, ?, ?, ?, ?, ?, ?, ? > အခြေအနေသို့ ရောက်ရှိသွားမည် ဖြစ်သည်။ ထိုအခါ Negative Example တစ်ခုဝင်လာသည်နှင့် S-set မှ ကာကွယ်ပေးနိုင်ခြင်း မရှိတော့ဘဲ G-set နှင့် S-set တို့ ဖြတ်တောက်မှု (Intersection) သည် Empty ဖြစ်သွားမည် ဖြစ်သည်။ ဤသည်မှာ Version-space ချဉ်းကပ်မှု၏ အဓိက အားနည်းချက်တစ်ခုဖြစ်သည့် "Disjunction ပြဿနာ" (OR logic လိုအပ်ခြင်း) ကို လက်တွေ့သက်သေပြလိုက်ခြင်း ဖြစ်ပါသည်။

            အဆိုပါ သီအိုရီ အလုပ်လုပ်ပုံနှင့် Version Space ပြိုကွဲသွားသည့် အဆင့်အထိကို အသေးစိတ် ပုံဖော်တွက်ချက်ပြထားသည့် အပြည့်အစုံ အလုပ်လုပ်နိုင်သော Python ပရိုဂရမ်မှာ အောက်ပါအတိုင်း ဖြစ်ပါတယ်။

Python

import pandas as pd
import copy

# Figure 19.2 မှ Restaurant Data အချက်အလက်များ[cite: 1]
# Columns: Alt, Bar, Fri, Hun, Pat, Price, Rain, Res, Type, Est, WillWait
data = [
    ['Yes', 'No', 'No', 'Yes', 'Some', '$$$', 'No', 'Yes', 'French', '0-10', 'Yes'],
    ['Yes', 'No', 'No', 'Yes', 'Full', '$', 'No', 'No', 'Thai', '30-60', 'No'],
    ['No', 'Yes', 'No', 'No', 'Some', '$', 'No', 'No', 'Burger', '0-10', 'Yes'],
    ['Yes', 'No', 'Yes', 'Yes', 'Full', '$', 'Yes', 'No', 'Thai', '10-30', 'Yes'],
    ['Yes', 'No', 'Yes', 'No', 'Full', '$$$', 'No', 'Yes', 'French', '>60', 'No'],
    ['No', 'Yes', 'No', 'Yes', 'Some', '$$', 'Yes', 'Yes', 'Italian', '0-10', 'Yes'],
    ['No', 'Yes', 'No', 'No', 'None', '$', 'Yes', 'No', 'Burger', '0-10', 'No'],
    ['No', 'No', 'No', 'Yes', 'Some', '$$', 'Yes', 'Yes', 'Thai', '0-10', 'Yes'],
    ['No', 'Yes', 'Yes', 'No', 'Full', '$', 'Yes', 'No', 'Burger', '>60', 'No'],
    ['Yes', 'Yes', 'Yes', 'Yes', 'Full', '$$$', 'No', 'Yes', 'Italian', '10-30', 'No'],
    ['No', 'No', 'No', 'No', 'None', '$', 'No', 'No', 'Thai', '0-10', 'No'],
    ['Yes', 'Yes', 'Yes', 'Yes', 'Full', '$', 'No', 'No', 'Burger', '30-60', 'Yes']
]

attributes = ['Alternate', 'Bar', 'Fri/Sat', 'Hungry', 'Patrons', 'Price', 'Raining', 'Reservation', 'Type', 'WaitEstimate']

def is_consistent(hypothesis, example):
    """Hypothesis သည် ပေးထားသော ဥပမာနှင့် ကိုက်ညီမှု ရှိ/မရှိ စစ်ဆေးရန်"""
    for h_val, e_val in zip(hypothesis, example):
        if h_val != '?' and h_val != e_val:
            return False
    return True

def more_general(h1, h2):
    """h1 သည် h2 ထက် ပို၍ ယေဘုယျကျခြင်း (generalize ဖြစ်ခြင်း) ရှိ/မရှိ စစ်ဆေးရန်"""
    for v1, v2 in zip(h1, h2):
        if v1 != '?' and v1 != v2:
            return False
    return True

def version_space_learning(dataset):
    # S-set ကို အတိကျဆုံး အခြေအနေဖြင့် စတင်မည် ('0' သည် ကန့်သတ်ချက်အမြင့်ဆုံးကို ကိုယ်စားပြုသည်)
    S = ['0'] * len(attributes)
    # G-set ကို ယေဘုယျအကျဆုံး အခြေအနေဖြင့် စတင်မည် ('?' သည် မည်သည့်တန်ဖိုးမဆို ကိုယ်စားပြုသည်)
    G = [['?'] * len(attributes)]

    print(f"{'='*60}\nအစပြုချိန် S-set: {S}")
    print(f"အစပြုချိန် G-set: {G}\n{'='*60}")

    for i, row in enumerate(dataset):
        x = row[:-1]
        y = row[-1]
        print(f"\nExample {i+1} ကို စစ်ဆေးခြင်း: {x} => Target: {y}")

        if y == 'Yes':
            # Positive Example ဖြစ်လျှင်
            
            # ၁. G-set ထဲမှ ဥပမာ x နှင့် မကိုက်ညီသော ယူဆချက်များကို ဖယ်ရှားမည်
            G = [g for g in G if is_consistent(g, x)]
            
            # ၂. S-set ကို ဥပမာ x နှင့် ကိုက်ညီအောင် Generalize လုပ်မည်
            if S[0] == '0':
                S = list(x)
            else:
                for j in range(len(S)):
                    if S[j] != '?' and S[j] != x[j]:
                        S[j] = '?'
                        
            # S-set သည် G-set မှ ယူဆချက်တစ်ခုခုအောက်တွင် specific မဖြစ်တော့ပါက Version Space ပြိုကွဲပြီဖြစ်သည်
            if not any(more_general(g, S) for g in G):
                print("\n[!] သတိပေးချက်: Version Space ပြိုကွဲသွားပါပြီ (Empty ဖြစ်သွားပါသည်)။")
                print("အကြောင်းရင်း: S-set သည် လွန်ကဲစွာ ယေဘုယျကျသွားပြီး G-set နှင့် မကိုက်ညီတော့ပါ။")
                print("ကောက်ချက်: ဤ Restaurant Data ၏ Target Concept သည် AND logic သီးသန့်ဖြင့် ဖော်ပြ၍မရဘဲ၊ Disjunction (OR logic) များ လိုအပ်ပါသည်။")
                break

        else:
            # Negative Example ဖြစ်လျှင်
            
            # ၁. S-set သည် negative ဥပမာနှင့် ကိုက်ညီနေပါက Version space ပြိုကွဲသည်
            if S[0] != '0' and is_consistent(S, x):
                print("\n[!] သတိပေးချက်: Version Space ပြိုကွဲသွားပါပြီ။ S-set သည် Negative Example ကို လက်ခံနေပါသည်။")
                break
                
            # ၂. G-set ကို ဥပမာ x ကို ဖယ်ထုတ်နိုင်ရန် Specialize လုပ်မည်
            new_G = []
            for g in G:
                if is_consistent(g, x):
                    for j in range(len(g)):
                        if g[j] == '?':
                            # S-set ၏ တန်ဖိုးကို အသုံးပြု၍ Negative example ကို ရှောင်လွှဲနိုင်သော hypothesis အသစ် ဖန်တီးမည်
                            if S[j] != '0' and S[j] != '?':
                                if S[j] != x[j]:
                                    new_g = copy.deepcopy(g)
                                    new_g[j] = S[j]
                                    new_G.append(new_g)
                else:
                    new_G.append(g)

            # G-set ထဲမှ ပို၍ ယေဘုယျမကျသော (redundant ဖြစ်နေသော) ယူဆချက်များကို ဖယ်ရှားမည်
            G = []
            for g1 in new_G:
                if not any(more_general(g1, g2) for g2 in new_G if g1 != g2):
                    G.append(g1)

        print(f"Update ပြီးသော S-set: {S}")
        print(f"Update ပြီးသော G-set: {G}")

# ပရိုဂရမ်ကို run ရန်
version_space_learning(data)