#! /usr/bin/env python # unittests.py -- MEU framework unit tests # Copyright (C) 2007 Martin Jansche # # Permission is hereby granted, free of charge, to any person obtaining # a copy of this software and associated documentation files (the # "Software"), to deal in the Software without restriction, including # without limitation the rights to use, copy, modify, merge, publish, # distribute, distribute with modifications, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be # included in all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. # IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, # DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR # OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR # THE USE OR OTHER DEALINGS IN THE SOFTWARE. # # Except as contained in this notice, the name(s) of the above copyright # holders shall not be used in advertising or otherwise to promote the # sale, use or other dealings in this Software without prior written # authorization. from math import exp, log import random import unittest import double import meu_framework import select def hypotheses(probs): """Enumerate all binary sequences of length len(probs) together with their probability. The elements of the sequence are assumed to cooccur independently, with probability Pr(x[i]=1) == probs[i].""" def hypotheses_aux(n, probs): if n <= 0: yield [], 0.0 else: for x,p in hypotheses_aux(n-1, probs): yield x+[1], p + log(probs[n-1]) yield x+[0], p + log(1.0 - probs[n-1]) return for x,p in hypotheses_aux(len(probs), probs): yield x, exp(p) return FUNCTIONS = ( lambda z: meu_framework.ZeroOne_Loss(z), lambda z: meu_framework.Hamming_Loss(z, 2), lambda z: meu_framework.Hamming_Loss(z, 5), lambda z: meu_framework.Hamming_Loss(z), lambda z: meu_framework.F_Score(z, 1.0), lambda z: meu_framework.F_Score(z, 3.0), lambda z: meu_framework.F_Score(z, 0.25), lambda z: meu_framework.Pk_Loss(z, 0), lambda z: meu_framework.Pk_Loss(z, 1), lambda z: meu_framework.Pk_Loss(z, 2), lambda z: meu_framework.Pk_Loss(z, 3), lambda z: meu_framework.Pk_Loss(z, 4), ) ZP_DATA = ( ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0.1, 0.2, 0.8, 0.1, 0.6, 0.5, 0.2, 0.9, 0.5, 0.3)), ((0, 0, 0, 0, 0, 0, 0, 1, 0, 0), (0.1, 0.2, 0.8, 0.1, 0.6, 0.5, 0.2, 0.9, 0.5, 0.3)), ((0, 0, 1, 0, 0, 0, 0, 1, 0, 0), (0.1, 0.2, 0.8, 0.1, 0.6, 0.5, 0.2, 0.9, 0.5, 0.3)), ((0, 0, 1, 0, 1, 0, 0, 1, 0, 0), (0.1, 0.2, 0.8, 0.1, 0.6, 0.5, 0.2, 0.9, 0.5, 0.3)), ((0, 0, 1, 0, 1, 1, 0, 1, 1, 0), (0.1, 0.2, 0.8, 0.1, 0.6, 0.5, 0.2, 0.9, 0.5, 0.3)), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1), (0.1, 0.2, 0.8, 0.1, 0.6, 0.5, 0.2, 0.9, 0.5, 0.3)), ) EXPECTATION_ALGORITHM = ( lambda z, p: meu_framework.exact_expectF(z, p, 1.0), lambda z, p: meu_framework.exact_expectF(z, p, 3.0), lambda z, p: meu_framework.exact_expectF(z, p, 0.25), lambda z, p: meu_framework.inexact_expectF(z, p, 1.0), lambda z, p: meu_framework.inexact_expectF(z, p, 3.0), lambda z, p: meu_framework.inexact_expectF(z, p, 0.25), lambda z, p: meu_framework.inexact_expectF(z, p, 1.0, lambda n: log(n+1)), lambda z, p: meu_framework.inexact_expectF(z, p, 3.0, lambda n: log(n+1)), lambda z, p: meu_framework.inexact_expectF(z, p, 0.25, lambda n: log(n+1)), lambda z, p: meu_framework.inexact_expectF(z, p, 1.0, lambda n: 4), lambda z, p: meu_framework.inexact_expectF(z, p, 3.0, lambda n: 4), lambda z, p: meu_framework.inexact_expectF(z, p, 0.25, lambda n: 4), lambda z, p: meu_framework.inexact_expectF(z, p, 1.0, lambda n: 1), lambda z, p: meu_framework.inexact_expectF(z, p, 3.0, lambda n: 1), lambda z, p: meu_framework.inexact_expectF(z, p, 0.25, lambda n: 1), ) P_DATA = ( (), (0.501,), (0.2, 0.8), (0.7, 0.501, 0.3), (0.9, 0.4, 0.1, 0.6), (0.3, 0.9, 0.501, 0.1, 0.7), (0.10, 0.11, 0.12, 0.90, 0.91, 0.92), ) class TestMEUFramework(unittest.TestCase): def test_evaluate_Eg(self): """Test whether the efficient computation of an expected value yields the same result as the brute-force computation.""" for G in FUNCTIONS: for z, p in ZP_DATA: g = G(z) # Brute-force computation by naive summation: E = 0.0 t = 0.0 for y, p_y in hypotheses(p): E += meu_framework.evaluate_g(g, y) * p_y t += p_y # Probabilities must sum to unity: self.assertAlmostEqual(t, 1.0, 10) # Exact efficient computation: E2 = meu_framework.evaluate_Eg(g, p) self.assertAlmostEqual(E, E2, 10) # Inexact efficient computation with no effective limit: res = meu_framework.evaluate_inexact_Eg(g, p, 2147483647) E3 = res[0] self.assertAlmostEqual(E, E3, 10) return def test_evaluate_inexact_Eg(self): """Check the bounds returned by the inexact calculation method.""" for z, p in ZP_DATA: g = meu_framework.F_Score(z) E = meu_framework.evaluate_Eg(g, p) res = meu_framework.evaluate_inexact_Eg(g, p, 1) # For the F-Score, an upper bound is available: self.assert_(res[1] is not None) # Check that the exact value falls within the bounds: self.assert_(res[0] <= E) # lower bound self.assert_(E <= res[1]) # upper bound return def test_ZeroOne_Loss(self): """Test whether the expected zero-one loss of a hypothesis z is equal to 1-Pr(z).""" for p in P_DATA: for z, p_z in hypotheses(p): g = meu_framework.ZeroOne_Loss(z) E = meu_framework.evaluate_Eg(g, p) self.assertAlmostEqual(E, 1.0 - p_z, 10) return def test_max_EF_decode(self): """Test whether the decoder returns a hypothesis whose expected F-score matches that of an optimal hypothesis found by a brute-force search.""" for EF in EXPECTATION_ALGORITHM: for p in P_DATA: # Brute-force search for an optimal hypothesis: argmax = None valmax = double.NEGATIVE_INFINITY for z, _ in hypotheses(p): val = EF(z, p) if val > valmax: argmax = z valmax = val self.assert_(argmax is not None) # Efficient search: (argmax2, valmax2) = meu_framework.max_EF_decode(p, EF) self.assertAlmostEqual(valmax, valmax2, 10) return COMPARATORS = ( lambda a, b: cmp(a, b), lambda a, b: cmp(b, a), ) class TestSelect(unittest.TestCase): def test_quicksort(self): # Test whether short arguments are handled correctly: for x in ([], [1], [2,2]): y = x[:] select.quicksort(y) self.assertEqual(y, x) # Repeatedly permute and sort a list: x = [0, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10] for _ in xrange(100): for comp in COMPARATORS: y = x[:] z = x[:] select.quicksort(y, comp) z.sort(comp) self.assertEqual(y, z) random.shuffle(x) return def test_select(self): x = [0, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10] for _ in xrange(100): y = x[:] random.shuffle(y) for comp in COMPARATORS: x.sort(comp) for k in xrange(len(x)): z = y[:] q = select.select(k, z, comp) self.assertEqual(q, x[k]) for p in z[:k]: self.assert_(comp(p, q) <= 0) for r in z[k+1:]: self.assert_(comp(q, r) <= 0) return if __name__ == '__main__': unittest.main() # eof