<jupyter_start><jupyter_text>\begin{align*}P(Match(T1,T2)\space|\space Quality(T1), Quality(T2)) = prob\_dist(Quality(T1), Quality(T2))\end{align*}<jupyter_code>%matplotlib inline
import itertools
import random
from functools import reduce
import operator
from numpy.random import choice
import matplotlib.pyplot as plt
def prob_dist(team_1_quality, team_2_quality):
    assert team_1_quality in range(4), 'team_1 not in range'
    assert team_2_quality in range(4), 'team_2 not in range'
    dist = [1/3, 1/3, 1/3]
    diff = team_1_quality - team_2_quality
    if diff != 0:
        dist[0] += abs(diff)*0.10
        dist[1] -= abs(diff)*0.05
        dist[2] -= abs(diff)*0.05
    if diff < 0:
        dist.reverse()
    if sum(dist) < 0.999 or sum(dist) > 1.001:
        raise('invalid distribution', dist)
    return dist
print(prob_dist(0,0))
print(prob_dist(1,0))
print(prob_dist(1,2))<jupyter_output>[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]
[0.43333333333333335, 0.2833333333333333, 0.2833333333333333]
[0.2833333333333333, 0.2833333333333333, 0.43333333333333335]<jupyter_text>c. Suppose that in the first two matches A beats B and draws with C. Using an exact inference algorithm of your choice, compute the posterior distribution for the outcome of the third match.\begin{equation*}P(BC | AB=Win, AC=Tie) =\sum_{a=0}^3\sum_{b=0}^3 P(AB=Win|A=a,B=b)\times\sum_{c=0}^3 P(AC=Tie|A=a,C=c)\times P(BC|B=b,C=c)\end{equation*}<jupyter_code># P(BC | AB=Win, AC=Tie)
dist = [0,0,0]
for a in range(4):
    for b in range(4):
        #  P(AB=Win | A=a, B=b)
        f1 = prob_dist(a, b)
        f1 = f1[0]
        # print('P(AB=Win | A={}, B={})={}'.format(a, b, f1))
        s = [0,0,0]
        for c in range(4):
            # P(AC=Tie | A=a, C=c)
            f2 = prob_dist(a, c)
            f2 = f2[1]
            # print('P(AC=Tie | A={}, C={})={}'.format(a, c, f2))            
            # P(BC | B=b, C=c)
            f3 = prob_dist(b, c)
            # print('P(BC | B={}, C={})={}'.format(b, c, f3))            
            s[0]+= f2 * f3[0]
            s[1]+= f2 * f3[1]
            s[2]+= f2 * f3[2]

        dist[0] += f1 * s[0]
        dist[1] += f1 * s[1]
        dist[2] += f1 * s[2]

# normalize dist
dist = [p/sum(dist) for p in dist]
print(dist)
# 0.342, 0.271, 0.387<jupyter_output>[0.3422898703736289, 0.270760748430993, 0.38694938119537803]<jupyter_text>\begin{equation*}P(LastMatch | RestTheRestOfMatches) =\sum_{t1=0}^3\sum_{t2=0}^3...\sum_{tn=0}^3 P(M1|parents(M1)).P(M2|parents(M2))...P(Mn|parents(Mn))\end{equation*}<jupyter_code># probability distribution calculated using marginalization rule
def prob_dist_given_matches(teams, matches):
    print('Teams:', len(teams))
    print('History:', matches)
    last_match_1 = teams[-2]
    last_match_2 = teams[-1]    
    dist = [0, 0, 0]
    for c in itertools.product(range(4), repeat=len(teams)):
        factors = []
        for match, result in matches.items():
            team_1, team_2 = match
            f = prob_dist(c[team_1], c[team_2])
            factors.append(f[result])
        f = reduce(operator.mul, factors, 1)
        last_prob = prob_dist(c[last_match_1], c[last_match_2])
        dist[0]+= f * last_prob[0]
        dist[1]+= f * last_prob[1]
        dist[2]+= f * last_prob[2]

    dist = [p/sum(dist) for p in dist]
    return dist

def stats(team, matches):
    result = {'Win':0, 'Tie':0, 'Lose':0}
    for m, r in matches.items():
        if team in m:
            if r == 1:
                result['Tie'] += 1                
                continue
            if team == m[0]:
                if r == 0:
                    result['Win'] += 1
                else:
                    result['Lose'] += 1
            else:
                if r == 2:
                    result['Win'] += 1
                else:
                    result['Lose'] += 1
    return result
# Pseudo GIBBs for this problem
def gibbs_ask(teams, matches, K=1, history=False):
    N = [0,0,0]
    last_match = (teams[-2], teams[-1])
    x = matches.copy()
    hist = []
    
    for t in teams:
        # set random quality for team variables
        x[t] = random.randint(0,3)
    # set random result for last match
    x[last_match] = random.randint(0,2)
    all_matches = matches.copy()
    all_matches[last_match] = x[last_match]
    
    # save some useful data for stats
    counter = {}
    for t in teams:
        counter[t] = [0,0,0,0]
    for m in all_matches:
        counter[m] = [0,0,0]
    
    for k in range(K):
        # Z: none evidence variables (all teams plus last match)
        # We sample for all Zi in Z. First the teams, then the last match
        for t in teams:
            #print('Sample from P(Quality(T{}) | mb(T{}))'.format(t, t))
            dist = [1,1,1,1]
            for i in range(4):
                for m in all_matches:
                    team1, team2 = m
                    r = x[m]
                    if t in m:
                        if t == team1:
                            d = prob_dist(i, x[team2])
                        else:
                            # t is team2
                            d = prob_dist(x[team1], i)
                    else:
                        d = prob_dist(x[team1], x[team2])
                    dist[i] *= d[r]
            dist = [p/sum(dist) for p in dist]
            # sample from distribution dist = P(Q(t) | mb(t))
            selection = choice(range(4), 1, p=dist.copy())
            x[t] = selection[0]
            
        # Now we take the sample for last match from P(LM | mb(ML))
        dist = prob_dist(x[last_match[0]], x[last_match[1]])            
        selection = choice(range(3), 1, p=dist.copy())
        x[last_match] = selection[0]
        
        # save useful data
        for idx in x:
            counter[idx][x[idx]] += 1
            
        if history:
            hist.append(counter[last_match].copy())
            
                
    #for k in counter:
    #    n = counter[k]
    #    n = [p/sum(n) for p in n]
    #    print('Var {} Distribution: {}'.format(k, n))
    
    # counter[last_match] is N in the book
    N = counter[last_match]
    N = [p/sum(N) for p in N]
    return N, hist

def test(teams, matches, K=100):
    print('LAST MATCH {} vs {}'.format(teams[-2], teams[-1]))
    print('Stats Team {}: {}'.format(teams[-2], stats(teams[-2], matches)))
    print('Stats Team {}: {}'.format(teams[-1], stats(teams[-1], matches)))
    r1 = prob_dist_given_matches(teams, matches)
    print('Last Match Distribution (exact inferece)', r1)
    r2,_ = gibbs_ask(teams, matches, K)
    print('Last Match Distribution (GIBBS inferece)', r2)
    se = [(r1[i]-r2[i])**2 for i in range(len(r1))]
    print('Squares Errors:', se)
    print('Sum of Squares Errors:', sum(se))    
teams = range(3)
matches = {}
matches[(0,1)] = 0
matches[(0,2)] = 1
test(teams, matches, K=2000)
teams = range(3)
matches = {}
for p in itertools.combinations(teams, 2):
    matches[p] = random.randint(0, 2)
    
del matches[(teams[-2], teams[-1])]
test(teams, matches, K=1000)
teams = range(3)
matches = {}
matches[(0,1)] = 0
matches[(0,2)] = 1
test(teams, matches, K=10)
test(teams, matches, K=100)
test(teams, matches, K=1000)
test(teams, matches, K=5000)
teams = range(4)
matches = {}
matches[(0,1)] = 0
matches[(0,2)] = 2
matches[(0,3)] = 0
matches[(1,2)] = 2
matches[(1,3)] = 0
test(teams, matches)
gibbs_ask(teams, matches, K=1000)

teams = range(8)
matches = {}
for p in itertools.combinations(teams, 2):
    matches[p] = random.randint(0, 2)
    
del matches[(teams[-2], teams[-1])]
test(teams, matches, K=2000)
r1 = prob_dist_given_matches(teams, matches)
r2, hist = gibbs_ask(teams, matches, K=2000, history=True)
se = []
for r in hist:
    n = [p/sum(r) for p in r]
    se.append(sum([(r1[i]-n[i])**2 for i in range(len(r1))]))

plt.ylabel('Sum Square Error')
plt.plot([i for i in range(len(se))], se)
plt.ylabel('Sum Square Error')
plt.plot(se[0:50])
teams = range(10)
matches = {}
for p in itertools.combinations(teams, 2):
    matches[p] = random.randint(0, 2)
    
del matches[(teams[-2], teams[-1])]
r1 = prob_dist_given_matches(teams, matches)
r2, hist = gibbs_ask(teams, matches, K=200, history=True)
se = []
for r in hist:
    n = [p/sum(r) for p in r]
    se.append(sum([(r1[i]-n[i])**2 for i in range(len(r1))]))

plt.ylabel('Sum Square Error')
plt.plot([i for i in range(len(se))], se)<jupyter_output>Teams: 10
History: {(0, 1): 2, (0, 2): 0, (0, 3): 2, (0, 4): 2, (0, 5): 2, (0, 6): 2, (0, 7): 0, (0, 8): 2, (0, 9): 0, (1, 2): 0, (1, 3): 0, (1, 4): 0, (1, 5): 0, (1, 6): 2, (1, 7): 2, (1, 8): 0, (1, 9): 0, (2, 3): 1, (2, 4): 2, (2, 5): 2, (2, 6): 0, (2, 7): 0, (2, 8): 2, (2, 9): 2, (3, 4): 1, (3, 5): 1, (3, 6): 2, (3, 7): 2, (3, 8): 2, (3, 9): 2, (4, 5): 1, (4, 6): 2, (4, 7): 0, (4, 8): 1, (4, 9): 0, (5, 6): 0, (5, 7): 1, (5, 8): 2, (5, 9): 1, (6, 7): 1, (6, 8): 0, (6, 9): 2, (7, 8): 0, (7, 9): 1}
{'fraction_non_alphanumeric': 0.17888727191313109, 'fraction_numerical': 0.07265196462554573, 'mean_word_length': 2.402132520944402, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 9, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '394579', 'license': 'MIT', 'n_tokens_mistral': 3789, 'n_tokens_neox': 3426, 'n_words': 893, 'path': 'Exercises/chapter-14/AIMA 3 Exercises 14.21.ipynb', 'repo_name': 'kecol/aima3e', 'size': '8933'}