<jupyter_start><jupyter_text>作業目標: 了解斷詞演算法的背後計算  根據課程講述的內容, 請計算出下列剩餘所有情況的若有一個人連續觀察到三天水草都是乾燥的(Dry), 則這三天的天氣機率為何？(可參考講義第13頁)(Hint: 共有8種可能機率)```pythonstates = ('sunny', 'rainy')observations = ('dry', 'damp', 'soggy')start_probability = {'sunny': 0.4, 'rainy': 0.6}transition_probability = {'sunny':{'sunny':0.6, 'rainy':0.4},                          'rainy': {'sunny':0.3, 'rainy':0.7}}emission_probatility = {'sunny': {'dry':0.6, 'damp':0.3, 'soggy':0.1},                        'rainy': {'dry':0.1, 'damp':0.4, 'soggy':0.5}}``` ```觀察狀態 = 'dry', 'dry', 'dry'Sunny, Sunny, Sunny: 0.4*(0.6)*0.6*(0.6)*0.6*(0.6) = 0.031104Rainy, Sunny, Sunny: 0.6*(0.1)*0.3*(0.6)*0.6*(0.6) = 0.003888最大機率為: Sunny, Sunny, Sunny```  My answers<jupyter_code>GoundTruths = {
"Sunny-->Sunny-->Sunny" : 0.4 * (0.6) * 0.6 * (0.6) * 0.6 * (0.6),
"Sunny-->Sunny-->Rainy" : 0.4 * (0.6) * 0.6 * (0.6) * 0.4 * (0.1),
"Sunny-->Rainy-->Sunny" : 0.4 * (0.6) * 0.4 * (0.1) * 0.3 * (0.6),
"Sunny-->Rainy-->Rainy" : 0.4 * (0.6) * 0.4 * (0.1) * 0.7 * (0.1),
"Rainy-->Sunny-->Sunny" : 0.6 * (0.1) * 0.3 * (0.6) * 0.6 * (0.6),
"Rainy-->Sunny-->Rainy" : 0.6 * (0.1) * 0.3 * (0.6) * 0.4 * (0.1),
"Rainy-->Rainy-->Sunny" : 0.6 * (0.1) * 0.7 * (0.1) * 0.3 * (0.6),
"Rainy-->Rainy-->Rainy" : 0.6 * (0.1) * 0.7 * (0.1) * 0.7 * (0.1),
}

for path, prob in GoundTruths.items():
    print(path, ":", prob)<jupyter_output>Sunny-->Sunny-->Sunny : 0.031103999999999993
Sunny-->Sunny-->Rainy : 0.0034560000000000003
Sunny-->Rainy-->Sunny : 0.0017280000000000002
Sunny-->Rainy-->Rainy : 0.0006720000000000001
Rainy-->Sunny-->Sunny : 0.003887999999999999
Rainy-->Sunny-->Rainy : 0.00043200000000000004
Rainy-->Rainy-->Sunny : 0.0007559999999999998
Rainy-->Rainy-->Rainy : 0.000294<jupyter_text>根據上述條件, 寫出Viterbi應用程式<jupyter_code>observations           = ('dry', 'dry', 'dry') #實際上觀察到的狀態為dry, dry, dry
states                 = ('sunny', 
                          'rainy')
start_probability      = {'sunny': 0.4, 
                          'rainy': 0.6}
transition_probability = {'sunny': {'sunny':0.6, 'rainy':0.4},
                          'rainy': {'sunny':0.3, 'rainy':0.7}}
emission_probatility   = {'sunny': {'dry':0.6, 'damp':0.3, 'soggy':0.1},
                          'rainy': {'dry':0.1, 'damp':0.4, 'soggy':0.5}}
def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    path = {}

    # Initialize base cases (t == 0)
    t = 0
    for cur_state in states:
        # get current prob
        pre_prob = start_p[cur_state]
        cur_prob = pre_prob * emit_p[cur_state][obs[t]]
        # assign prob & path
        V[t][cur_state] = cur_prob
        path[cur_state] = [cur_state,]
        
    # Run Viterbi for t > 0
    for t in range(1, len(obs)):
        V.append({})
        temp_path = {}
        for cur_state in states:        
            # get current prob & path
            prob_path_paris = []
            for pre_state in states:            
                pre_prob = V[t-1][pre_state]
                cur_prob = pre_prob * trans_p[pre_state][cur_state] * emit_p[cur_state][obs[t]]
                prob_path_paris.append([cur_prob, [pre_state, cur_state]])        
            best_prob, best_path = max(prob_path_paris)        
            # assign prob & path
            V[t][cur_state] = best_prob
            temp_path[cur_state] = path[best_path[0]][:-1] + best_path        
        # update path
        path = temp_path 
    
    #(prob, state) = max([(V[len(obs) - 1][final_state], final_state) for final_state in states])
    #return (prob, path[state])
    cur_t = len(obs) - 1
    max_state = max(V[cur_t])
    max_prob = V[cur_t][max_state]
    return max_prob, path[max_state]
    
result = viterbi(observations,
                 states,
                 start_probability,
                 transition_probability,
                 emission_probatility)
result<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.19969119917653114, 'fraction_numerical': 0.08749356664951106, 'mean_word_length': 2.394759825327511, 'pattern_counts': {'":': 1, '<': 8, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 7, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '656333', 'license': 'MIT', 'n_tokens_mistral': 1899, 'n_tokens_neox': 1696, 'n_words': 266, 'path': 'practices/Day-005/day_005_practice.ipynb', 'repo_name': 'magikerwin1993/1st-NLP-Marathon', 'size': '3886'}