| """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 ( |
| 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) |
| 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)) |
| |
| 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) |
| |
| self.assertNotEqual(int_to_hv(42), int_to_hv(43)) |
| self.assertNotEqual(int_to_hv(42), int_to_hv(-42)) |
| |
| |
| 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() |
|
|
