probabilities/model_probabilities2.py

import math
from statistics import median, stdev

def count_one_bits(n):
    return bin(n).count("1")

def compute_distance(a, b):
    distance = count_one_bits(a ^ b)
    # return 1 / (8 ** distance)
    if distance == 0:
        return 0
    # return 1 / (64 ** (distance - 1))
    return  distance

def xor_n(n):
    return count_one_bits(n) % 2

def compute_distances(N):
    return [[compute_distance(i, j) for j in range(N)] for i in range(N)]

def compute_nn_probabilities(i, knowns, distances):
    total = 0.0
    total_zero = 0.0
    total_one = 0.0
    for known in knowns:
        j = known[0]
        if i == j:
            continue
        distance = distances[i][j]
        total += distance
        if known[1] == 0:
            total_zero += distance
        else:
            total_one += distance
    p_zero = total_zero / total
    p_one = total_one / total
    return (p_zero, p_one)

def interpolate_probabilities(i, knowns, distances, probabilities, dim):
    total = 0.0
    total_dim = [0.0] * dim
    for known in knowns:
        j = known[0]
        if i == j:
            continue
        distance = distances[i][j]
        total += distance
        probability = probabilities[j]
        for index in range(dim):
            total_dim[index] += distance * probability[index]
    for index in range(dim):
        total_dim[index] /= total
    return total_dim

def compute_est_coherence(i, knowns, coherences, distances):
    total = 0.0
    coherence = 0.0
    for known in knowns:
        j = known[0]
        distance = distances[i][j]
        total += distance
        coherence += distance * coherences[j]
    return coherence / total

def compute_est_coherences(N, knowns, distances):
    nn_probabilities = [None for i in range(N)]
    nn_correct_probabilities = [None for i in range(N)]
    coherences = []

    for known in knowns:
        i = known[0]
        nn_probabilities[i] = compute_nn_probabilities(i, knowns, distances)
    
    # for i in range(len(nn_probabilities)):
    #     if not nn_probabilities[i] is None:
    #         continue
    #     nn_probabilities[i] = interpolate_probabilities(i, knowns, distances, nn_probabilities, 2)
    
    for known in knowns:
        i = known[0]
        nn_correct_probabilities[i] = [nn_probabilities[i][known[1]]]

    # for i in range(len(nn_correct_probabilities)):
    #     if not nn_correct_probabilities[i] is None:
    #         continue
    #     nn_correct_probabilities[i] = interpolate_probabilities(i, knowns, distances, nn_correct_probabilities, 1)

    coherences_0 = []
    coherences_1 = []
    for known_i in knowns:
        i = known_i[0]
        coherence = 0.0
        total = 0.0
        for known_j in knowns:
            j = known_j[0]
            if i == j:
                continue

            distance = distances[i][j]
            total += distance

            nn_p_i_0 = nn_probabilities[i][0]
            nn_p_i_1 = nn_probabilities[i][1]
            nn_c_p_i = nn_correct_probabilities[i][0]

            nn_p_j_0 = nn_probabilities[j][0]
            nn_p_j_1 = nn_probabilities[j][1]
            nn_c_p_j = nn_correct_probabilities[j][0]

            p_i_0 = nn_p_i_0 * nn_c_p_i + nn_p_i_1 * (1 - nn_c_p_i)
            p_i_1 = nn_p_i_1 * nn_c_p_i + nn_p_i_0 * (1 - nn_c_p_i)

            p_j_0 = nn_p_j_0 * nn_c_p_j + nn_p_j_1 * (1 - nn_c_p_j)
            p_j_1 = nn_p_j_1 * nn_c_p_j + nn_p_j_0 * (1 - nn_c_p_j)

            coherence += distance * (p_i_0 * p_j_0 + p_i_1 * p_j_1)
        coherences.append(coherence / total)
        if known_i[1] == 0:
            coherences_0.append(coherence / total)
        else:
            coherences_1.append(coherence / total)

    return coherences

def score(coherences, knowns, distances):
    # while len(coherences) > 1:
    #     coherences = [(coherences[i] + coherences[i + 1]) / 2 for i in range(0, len(coherences), 2)]
    # return coherences[0]

    # return median(coherences)
    # return sum(coherences) / len(coherences)
    if len(coherences) == 0:
        return 1.0
    numerator_0 = 0.0
    denominator_0 = 0.0
    numerator_1 = 0.0
    denominator_1 = 0.0
    count_0 = 0.0
    count_1 = 0.0
    for i in range(len(knowns)):
        weight = 0
        for j in range(len(knowns)):
            weight += distances[knowns[i][0]][knowns[j][0]]
        print(weight, end=' ')
        if knowns[i][1] == 0:
            denominator_0 += weight
            numerator_0 += weight * coherences[i]
            count_0 += 1
        else:
            denominator_1 += weight
            numerator_1 += weight * coherences[i]
            count_1 += 1
    # print()
    if count_0 == 0 or count_1 == 0:
        return 1.0

    # return ((sum(coherences[0]) / len(coherences[0])) + (sum(coherences[1]) / len(coherences[1]))) / 2.0
    # return (sum(coherences[0]) + sum(coherences[1])) / (len(coherences[0]) + len(coherences[1]))
    # div_0 = (numerator_0 / denominator_0 if denominator_0 > 0 else 1.0) * 0.5
    # div_1 = (numerator_1 / denominator_1 if denominator_1 > 0 else 1.0) * 0.5
    # return div_0 + div_1
    # aligned = 1.0 - abs(0.5 - max(count_0 / (count_0 + count_1), count_1 / (count_0 + count_1)))
    # return ((numerator_0 + numerator_1) / (denominator_0 + denominator_1)) * (aligned ** 0.1)
    # return (((numerator_0 + numerator_1) / (denominator_0 + denominator_1)) + 0.12 * aligned) * (1.0 / 1.12)
    return (numerator_0 + numerator_1) / (denominator_0 + denominator_1)

def xor_by_index(knowns, index):
    mask = 1 << index
    knowns = knowns[:]
    for i in range(len(knowns)):
        known = knowns[i]
        if known[0] & mask:
            knowns[i] = (known[0], known[1] ^ 1)
    return knowns

def main():
    n = 8
    N = 2 ** n
    distances = compute_distances(N)

    knowns = [(i, xor_n(i)) for i in [
        # 0, 3, 4, 5, 7
        # 3, 5, 6, 10, 12, 14
        # 1, 3, 7, 10, 14, 15
        # 0, 3, 5, 6, 10, 11, 12
        0, 3, 5, 6, 10, 11, 12, 24, 30
        # 0, 3, 5, 6, 10, 11, 12, 24, 30, 52, 63, 255, 243, 127
        # 128, 131, 248, 0, 7, 13, 17, 19
    ]]

    for known_i in knowns:
        i = known_i[0]
        for known_j in knowns:
            j = known_j[0]
            print(distances[i][j], end=' ')
        print()

    print(knowns)
    print()

    # knowns = [
    #     (1, 1),
    #     (3, 0),
    #     (7, 1),
    #     (10, 0),
    #     (14, 1),
    #     (15, 0)
    # ]

    # knowns = [
    #     (0, 0),
    #     (3, 0),
    #     (4, 1),
    #     (5, 0),
    #     (7, 1)
    # ]

    # knowns = [
    #     (0, 0),
    #     (1, 1),
    #     (2, 1),
    #     (3, 0),
    #     (4, 1),
    #     (5, 0),
    #     (6, 0),
    #     (7, 1)
    # ]

    coherences = compute_est_coherences(N, knowns, distances)
    best_coherence = score(coherences, knowns, distances)
    print(best_coherence)

    flipped = []
    while best_coherence < 1.0:
        print()
        # print(knowns)
        # print()
        best_index = -1
        # best_coherence = 0
        for i in range(0, n):
            if i in flipped:
                continue
            mutated_knowns = xor_by_index(knowns, i)
            coherences = compute_est_coherences(N, mutated_knowns, distances)
            coherence = score(coherences, mutated_knowns, distances)
            # print(coherence)
            print(coherence, end=' ')
            print(mutated_knowns)
            if coherence > best_coherence:
                best_coherence = coherence
                best_index = i
        if best_index < 0:
            break
        knowns = xor_by_index(knowns, best_index)
        # flipped.append(best_index)
        print(knowns)


if __name__ == "__main__":
    main()