File size: 5,824 Bytes
ad474c9 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 | """Algebra-level tests for the binary hypervector core."""
import os
import random
import sys
import unittest
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from hdc.hypervec import ( # noqa: E402
DEFAULT_DIM,
bind,
bundle,
hamming,
hvc,
hv_to_int,
int_to_hv,
permute,
permute_inv,
popcount,
random_hv,
sim,
)
def brute_majority(vecs, d):
"""Per-bit reference majority; ties resolve to 0, as documented."""
out = 0
for pos in range(d):
ones = sum((v >> pos) & 1 for v in vecs)
if ones * 2 > len(vecs):
out |= 1 << pos
return out
class TestBind(unittest.TestCase):
def test_involutive(self):
rng = random.Random(11)
for _ in range(20):
a = random_hv(2000, rng)
b = random_hv(2000, rng)
self.assertEqual(bind(bind(a, b, 2000), b, 2000), a)
def test_bind_is_xor(self):
a, b = 0b1100, 0b1010
self.assertEqual(bind(a, b), a ^ b)
def test_bind_preserves_similarity(self):
rng = random.Random(12)
a = random_hv(4000, rng)
near = a ^ (1 << 5) # one bit away
x = random_hv(4000, rng)
self.assertAlmostEqual(
sim(bind(a, x), bind(near, x), 4000), sim(a, near, 4000), places=12
)
class TestBundle(unittest.TestCase):
def test_matches_brute_force_odd(self):
rng = random.Random(21)
d = 64
for n in (3, 5, 7):
vecs = [random_hv(d, rng) for _ in range(n)]
self.assertEqual(bundle(vecs, d), brute_majority(vecs, d))
def test_matches_brute_force_even_with_ties(self):
rng = random.Random(22)
d = 48
for n in (2, 4, 6):
vecs = [random_hv(d, rng) for _ in range(n)]
self.assertEqual(bundle(vecs, d), brute_majority(vecs, d))
def test_single_vector_and_empty(self):
rng = random.Random(23)
v = random_hv(128, rng)
self.assertEqual(bundle([v], 128), v)
self.assertEqual(bundle([], 128), 0)
def test_members_recover_above_noise(self):
rng = random.Random(24)
d = 4000
vecs = [random_hv(d, rng) for _ in range(5)]
b = bundle(vecs, d)
for v in vecs:
self.assertGreater(sim(b, v, d), 0.25)
class TestPermute(unittest.TestCase):
def test_roundtrip(self):
rng = random.Random(31)
d = 2000
v = random_hv(d, rng)
for k in (1, 7, 999, d - 1):
self.assertEqual(permute_inv(permute(v, k, d), k, d), v)
def test_preserves_similarity(self):
rng = random.Random(32)
d = 2000
a, b = random_hv(d, rng), random_hv(d, rng)
self.assertAlmostEqual(
sim(permute(a, 13, d), permute(b, 13, d), d), sim(a, b, d), places=12
)
def test_rotation_keeps_popcount(self):
rng = random.Random(33)
v = random_hv(1000, rng)
self.assertEqual(popcount(permute(v, 37, 1000)), popcount(v))
class TestSimilarity(unittest.TestCase):
def test_identical_is_one(self):
rng = random.Random(41)
v = random_hv(2000, rng)
self.assertEqual(sim(v, v, 2000), 1.0)
def test_complement_is_minus_one(self):
d = 256
v = random_hv(d, random.Random(42))
# the d-bit complement, not Python's unbounded ~v
self.assertEqual(sim(v, v ^ ((1 << d) - 1), d), -1.0)
def test_symmetry_and_bounds(self):
rng = random.Random(43)
d = 2000
for _ in range(20):
a, b = random_hv(d, rng), random_hv(d, rng)
self.assertEqual(sim(a, b, d), sim(b, a, d))
self.assertGreaterEqual(sim(a, b, d), -1.0)
self.assertLessEqual(sim(a, b, d), 1.0)
def test_random_pairs_near_orthogonal(self):
rng = random.Random(44)
d = 2000
vals = [sim(random_hv(d, rng), random_hv(d, rng), d) for _ in range(300)]
mean = sum(vals) / len(vals)
self.assertLess(abs(mean), 0.05)
def test_hamming_agrees_with_sim(self):
rng = random.Random(45)
d = 2000
a, b = random_hv(d, rng), random_hv(d, rng)
self.assertAlmostEqual(
sim(a, b, d), (d - 2 * hamming(a, b)) / d, places=12
)
class TestSymbols(unittest.TestCase):
def test_deterministic(self):
self.assertEqual(hvc("op/ADD", 2000), hvc("op/ADD", 2000))
def test_distinct_names_differ(self):
a, b = hvc("op/ADD", 2000), hvc("op/SUB", 2000)
self.assertNotEqual(a, b)
self.assertLess(abs(sim(a, b, 2000)), 0.1)
def test_dimension_matters(self):
self.assertNotEqual(hvc("op/ADD", 2000), hvc("op/ADD", 1000))
class TestIntegerCodec(unittest.TestCase):
VALUES = [0, 1, 7, 42, -5, 255, 65535, -12345]
def test_roundtrip_default_dim(self):
for n in self.VALUES:
self.assertEqual(hv_to_int(int_to_hv(n)), n, msg="value %d" % n)
def test_roundtrip_small_dim(self):
d = 2000
for n in self.VALUES:
self.assertEqual(hv_to_int(int_to_hv(n, d), d), n, msg="value %d" % n)
def test_encoded_values_are_hypervectors(self):
v = int_to_hv(42)
self.assertEqual(v.bit_length() <= DEFAULT_DIM, True)
# different integers must not collide
self.assertNotEqual(int_to_hv(42), int_to_hv(43))
self.assertNotEqual(int_to_hv(42), int_to_hv(-42))
# 42 and 7 share bit atom 1 by construction, so they are correlated
# but nowhere near identical
self.assertLess(sim(int_to_hv(42), int_to_hv(7), DEFAULT_DIM), 0.6)
def test_out_of_range_rejected(self):
with self.assertRaises(ValueError):
int_to_hv(1 << 40)
if __name__ == "__main__":
unittest.main()
|