ppad-eproc 0.5.1 → 0.5.2
raw patch · 8 files changed
+942/−1 lines, 8 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidAlpha :: {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidBaselineRate :: {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidBounds :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidComponentCount :: {-# UNPACK #-} !Int -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidGridSize :: {-# UNPACK #-} !Int -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidNullInterval :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: InvalidNullMean :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: config :: Double -> Either ConfigError Config
+ Numeric.Eproc.ConfSeq.Bernoulli: data Config
+ Numeric.Eproc.ConfSeq.Bernoulli: data ConfigError
+ Numeric.Eproc.ConfSeq.Bernoulli: data State
+ Numeric.Eproc.ConfSeq.Bernoulli: from_counts :: Int -> Int -> Maybe State
+ Numeric.Eproc.ConfSeq.Bernoulli: initial :: Config -> State
+ Numeric.Eproc.ConfSeq.Bernoulli: interval :: Config -> State -> (Double, Double)
+ Numeric.Eproc.ConfSeq.Bernoulli: samples :: State -> Int
+ Numeric.Eproc.ConfSeq.Bernoulli: successes :: State -> Int
+ Numeric.Eproc.ConfSeq.Bernoulli: update :: Config -> State -> Bool -> State
+ Numeric.Eproc.Merge: ebh :: Double -> [Double] -> [Int]
+ Numeric.Eproc.Merge: log_mean :: [Double] -> Double
+ Numeric.Eproc.Merge: log_product :: [Double] -> Double
+ Numeric.Eproc.TwoSample: Continue :: Verdict
+ Numeric.Eproc.TwoSample: InvalidAlpha :: {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.TwoSample: InvalidBaselineRate :: {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.TwoSample: InvalidBounds :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.TwoSample: InvalidComponentCount :: {-# UNPACK #-} !Int -> ConfigError
+ Numeric.Eproc.TwoSample: InvalidGridSize :: {-# UNPACK #-} !Int -> ConfigError
+ Numeric.Eproc.TwoSample: InvalidNullInterval :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.TwoSample: InvalidNullMean :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> ConfigError
+ Numeric.Eproc.TwoSample: Reject :: Verdict
+ Numeric.Eproc.TwoSample: clip_bound :: Double -> [Double] -> Double
+ Numeric.Eproc.TwoSample: config :: Double -> [Double] -> Double -> [Double] -> Either ConfigError Config
+ Numeric.Eproc.TwoSample: configInterval :: Double -> Double -> [Double] -> Double -> [Double] -> Either ConfigError Config
+ Numeric.Eproc.TwoSample: cut_points :: [Double] -> [Double]
+ Numeric.Eproc.TwoSample: data Config
+ Numeric.Eproc.TwoSample: data ConfigError
+ Numeric.Eproc.TwoSample: data State
+ Numeric.Eproc.TwoSample: data Verdict
+ Numeric.Eproc.TwoSample: decide :: Config -> State -> Verdict
+ Numeric.Eproc.TwoSample: initial :: Config -> State
+ Numeric.Eproc.TwoSample: log_evalue :: Config -> State -> Double
+ Numeric.Eproc.TwoSample: log_evalue_cdf :: State -> [Double]
+ Numeric.Eproc.TwoSample: log_evalue_magnitude :: State -> [Double]
+ Numeric.Eproc.TwoSample: log_evalue_sign :: State -> Double
+ Numeric.Eproc.TwoSample: log_evalue_sup :: State -> Double
+ Numeric.Eproc.TwoSample: samples :: State -> Int
+ Numeric.Eproc.TwoSample: update :: Config -> State -> Double -> [Double] -> State
+ Numeric.Eproc.TwoSample: update_pair :: Config -> State -> (Double, Double) -> State
Files
- CHANGELOG +13/−0
- bench/Main.hs +45/−0
- bench/Weight.hs +23/−0
- lib/Numeric/Eproc/ConfSeq/Bernoulli.hs +221/−0
- lib/Numeric/Eproc/Merge.hs +99/−0
- lib/Numeric/Eproc/TwoSample.hs +330/−0
- ppad-eproc.cabal +4/−1
- test/Main.hs +207/−0
CHANGELOG view
@@ -1,5 +1,18 @@ # Changelog +- 0.5.2 (2026-11-15)+ * Adds Numeric.Eproc.Merge: the mean of e-values (an e-value under+ any dependence), their product (under sequential validity), and+ the e-BH procedure (Wang & Ramdas 2022).+ * Adds Numeric.Eproc.ConfSeq.Bernoulli: an anytime-valid+ confidence sequence for a Bernoulli rate by Robbins' uniform+ mixture, exact at any rate and resumable from counts.+ * Adds Numeric.Eproc.TwoSample: a two-sample test of equality in law+ over an antisymmetric statistic, hedged over its sign, its+ magnitude clipped at several bounds, and indicators at cut points;+ an interval null on the clipped mean (configInterval); and the+ warmup calibration of its clip bounds and cut points.+ - 0.5.1 (2026-10-11) * Supports GHC 9.8 (base 4.19), where Prelude does not export foldl'.
bench/Main.hs view
@@ -9,8 +9,11 @@ import qualified Numeric.Eproc.Bernoulli.TwoSided as BernTS import qualified Numeric.Eproc.Bounded as Bounded import qualified Numeric.Eproc.ConfSeq as CS+import qualified Numeric.Eproc.ConfSeq.Bernoulli as CSB+import qualified Numeric.Eproc.Merge as Merge import qualified Numeric.Eproc.Mixture as Mix import qualified Numeric.Eproc.Paired as P+import qualified Numeric.Eproc.TwoSample as TS import Criterion.Main -- all relevant fields are strict (and UNPACK'd for the doubles), so@@ -22,6 +25,8 @@ instance NFData BernTS.State where rnf !_ = () instance NFData Mix.State where rnf !_ = () instance NFData Bounded.Verdict where rnf !_ = ()+-- TwoSample.State's lists are built whole by 'initial' and 'update'+instance NFData TS.State where rnf !_ = () -- partial helper for benches: configs here are hardcoded valid, so a -- 'Left' would be a bench-suite bug.@@ -43,6 +48,10 @@ , mix_stream , confseq_update , confseq_stream+ , hedge_update+ , hedge_stream+ , bernoulli_interval+ , merge ] update :: Benchmark@@ -188,4 +197,40 @@ run_c = L.foldl' (CS.update cfg) (CS.initial cfg) in bgroup "ConfSeq.update (1000-sample fold, g = 200)" [ bench "plug-in" $ nf run_c xs+ ]++hedge_update :: Benchmark+hedge_update =+ let !cfg = ok (TS.config 1.0e-3 [2, 8] 1 [1, 2, 3, 4, 5])+ !st = TS.initial cfg+ in bgroup "TwoSample.update_pair (one step, 5 cuts)" [+ bench "pair" $ nf (TS.update_pair cfg st) (3, 2)+ ]++hedge_stream :: Benchmark+hedge_stream =+ let !ps = force (take 1000 (cycle [(3, 2), (1, 4), (2, 2)]))+ !cfg = ok (TS.config 1.0e-3 [2, 8] 1 [1, 2, 3, 4, 5])+ run_h = L.foldl' (TS.update_pair cfg) (TS.initial cfg)+ in bgroup "TwoSample.update_pair (1000-pair fold, 5 cuts)" [+ bench "pairs" $ nf run_h ps+ ]++bernoulli_interval :: Benchmark+bernoulli_interval =+ let !cfg = ok (CSB.config 1.0e-3)+ st n = case CSB.from_counts (3 * n `div` 10) n of+ Just s -> s+ Nothing -> error "bench: invalid counts"+ in bgroup "ConfSeq.Bernoulli.interval" [+ bench "n = 100" $ nf (CSB.interval cfg) (st 100)+ , bench "n = 100000" $ nf (CSB.interval cfg) (st 100000)+ ]++merge :: Benchmark+merge =+ let !les = force (take 100 (cycle [0.1, -0.4, 2.0, 0.0, 7.5]))+ in bgroup "Merge (100 log e-values)" [+ bench "log_mean" $ nf Merge.log_mean les+ , bench "ebh" $ nf (Merge.ebh 0.05) les ]
bench/Weight.hs view
@@ -9,8 +9,10 @@ import qualified Numeric.Eproc.Bernoulli.TwoSided as BernTS import qualified Numeric.Eproc.Bounded as Bounded import qualified Numeric.Eproc.ConfSeq as CS+import qualified Numeric.Eproc.ConfSeq.Bernoulli as CSB import qualified Numeric.Eproc.Mixture as Mix import qualified Numeric.Eproc.Paired as P+import qualified Numeric.Eproc.TwoSample as TS import Weigh instance NFData Bounded.State where rnf !_ = ()@@ -19,6 +21,8 @@ instance NFData BernTS.State where rnf !_ = () instance NFData Mix.State where rnf !_ = () instance NFData Bounded.Verdict where rnf !_ = ()+-- TwoSample.State's lists are built whole by 'initial' and 'update'+instance NFData TS.State where rnf !_ = () -- partial helper for benches: configs here are hardcoded valid. ok :: Either e a -> a@@ -40,6 +44,8 @@ mix_stream confseq_update confseq_stream+ hedge_stream+ bernoulli_interval update :: Weigh () update =@@ -171,3 +177,20 @@ run_c = L.foldl' (CS.update cfg) (CS.initial cfg) in wgroup "ConfSeq.update (1000-sample fold, g = 200)" $ do func "plug-in" run_c xs++hedge_stream :: Weigh ()+hedge_stream =+ let !ps = force (take 1000 (cycle [(3, 2), (1, 4), (2, 2)]))+ !cfg = ok (TS.config 1.0e-3 [2, 8] 1 [1, 2, 3, 4, 5])+ run_h = L.foldl' (TS.update_pair cfg) (TS.initial cfg)+ in wgroup "TwoSample.update_pair (1000-pair fold, 5 cuts)" $ do+ func "pairs" run_h ps++bernoulli_interval :: Weigh ()+bernoulli_interval =+ let !cfg = ok (CSB.config 1.0e-3)+ st n = case CSB.from_counts (3 * n `div` 10) n of+ Just s -> s+ Nothing -> error "weigh: invalid counts"+ in wgroup "ConfSeq.Bernoulli.interval" $ do+ func "n = 100000" (CSB.interval cfg) (st 100000)
+ lib/Numeric/Eproc/ConfSeq/Bernoulli.hs view
@@ -0,0 +1,221 @@+{-# OPTIONS_HADDOCK prune #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE RecordWildCards #-}++-- |+-- Module: Numeric.Eproc.ConfSeq.Bernoulli+-- Copyright: (c) 2026 Jared Tobin+-- License: MIT+-- Maintainer: Jared Tobin <jared@ppad.tech>+--+-- Anytime-valid confidence sequence for a Bernoulli rate, by+-- Robbins' method of mixtures.+--+-- For trials @x_t@ in @{0, 1}@, i.i.d. with rate @r@, after @s@+-- successes in @n@ trials, the likelihood ratio of the uniform+-- mixture over rates against @r@,+--+-- @M_n(r) = B(s + 1, n - s + 1) \/ (r^s (1 - r)^(n - s))@+--+-- (@B@ the beta function), is a nonnegative martingale under @r@+-- with @M_0(r) = 1@. By Ville's inequality it ever reaches+-- @1 \/ alpha@ with probability at most @alpha@, so the rates it has+-- not reached that against,+--+-- @C_n = { r : M_n(r) < 1 \/ alpha }@,+--+-- cover the true rate at every @n@ at once with probability at least+-- @1 - alpha@: inspect after every trial and stop when you like. As+-- @B(s + 1, n - s + 1) = 1 \/ ((n + 1) C(n, s))@,+--+-- @log M_n(r) = - log(n + 1) - log P(s; n, r)@,+--+-- @P@ the binomial probability, computed by Loader's saddle-point+-- expansion (as R's @dbinom@): stable at any count, where a+-- difference of log-factorials of size @n log n@ is not.+-- @log M_n@ is convex in @r@ and at most zero at @s \/ n@, so @C_n@+-- is an interval about @s \/ n@, its ends found by bisection; its+-- half-width is about+--+-- @sqrt(2 r (1 - r) (log(1 \/ alpha) + log(tau n r (1 - r)) \/ 2) \/ n)@+--+-- (@tau = 2 pi@), the price of anytime validity a term in @log n@.+--+-- Unlike "Numeric.Eproc.ConfSeq", which bets over a finite grid of+-- candidate means of any bounded variable, this is exact for a rate,+-- however small, and depends on the trials only through their+-- counts: 'from_counts' resumes from a tally kept elsewhere.+--+-- == Example+--+-- >>> let Right cfg = config 0.05+-- >>> let Just st = from_counts 30 100+-- >>> let (lo, hi) = interval cfg st+-- >>> lo < 0.3 && 0.3 < hi+-- True++module Numeric.Eproc.ConfSeq.Bernoulli (+ -- * Configuration and state+ Config+ , State+ , ConfigError(..)++ -- * Construction+ , config+ , initial+ , from_counts++ -- * Streaming+ , update++ -- * Inspection+ , interval+ , samples+ , successes+ ) where++import qualified Data.List as L+import Numeric (log1p)++import Numeric.Eproc.Common (ConfigError(..), finite)++-- | Confidence-sequence configuration.+data Config = Config {+ cfg_alpha :: {-# UNPACK #-} !Double+ , cfg_log_thresh :: {-# UNPACK #-} !Double -- log (1 / alpha)+ }++-- | The trials so far, as their counts.+data State = State {+ st_n :: {-# UNPACK #-} !Int+ , st_s :: {-# UNPACK #-} !Int+ }++-- | Build a 'Config' at a level in @(0, 1)@.+--+-- >>> either (const False) (const True) (config 0.05)+-- True+config :: Double -> Either ConfigError Config+config !alpha+ | not (finite alpha && alpha > 0 && alpha < 1) =+ Left (InvalidAlpha alpha)+ | otherwise = Right (Config alpha (log (1 / alpha)))+{-# INLINE config #-}++-- | The state before any trial.+initial :: Config -> State+initial _ = State 0 0+{-# INLINE initial #-}++-- | The state after some successes of some trials, where there are+-- no more successes than trials and neither is negative.+--+-- >>> maybe False (const True) (from_counts 3 2)+-- False+from_counts :: Int -> Int -> Maybe State+from_counts !s !n+ | s < 0 || n < s = Nothing+ | otherwise = Just (State n s)+{-# INLINE from_counts #-}++-- | The state after one more trial, a success or not.+update :: Config -> State -> Bool -> State+update _ (State n s) x = State (n + 1) (if x then s + 1 else s)+{-# INLINE update #-}++-- | The number of trials so far.+samples :: State -> Int+samples = st_n+{-# INLINE samples #-}++-- | The number of successes so far.+successes :: State -> Int+successes = st_s+{-# INLINE successes #-}++-- | The confidence interval after the trials so far, @(0, 1)@ before+-- any. Each end is the outside one of the bracket a bisection+-- leaves it in, to the precision of a double, so that the interval+-- errs wide.+--+-- >>> let Right cfg = config 0.05+-- >>> interval cfg (initial cfg)+-- (0.0,1.0)+interval :: Config -> State -> (Double, Double)+interval Config{..} (State n s)+ | n <= 0 = (0, 1)+ | otherwise = (lower, upper)+ where+ !phat = fromIntegral s / fromIntegral n :: Double+ !ln1 = log (fromIntegral n + 1)+ inside r = negate ln1 - log_binom s n r < cfg_log_thresh+ lower+ | s == 0 = 0+ | otherwise = fst (bisect 0 phat)+ upper+ | s == n = 1+ | otherwise = snd (bisect phat 1)+ -- halving until the midpoint is one of the ends: the bracket as+ -- narrow as doubles allow, at any scale of rate+ bisect lo hi = go lo hi+ where+ !side = inside lo+ go x y =+ let !m = x + (y - x) / 2+ in if m <= x || m >= y then (x, y)+ else if inside m == side then go m y else go x m++-- log P(s; n, r), the binomial probability of s successes in n trials+-- at rate r, by Loader's saddle-point expansion: Stirling's error+-- terms, the deviances of s from n r and of n - s from n (1 - r), and+-- the normal constant+log_binom :: Int -> Int -> Double -> Double+log_binom s n r+ | s == 0 = nN * log1p (negate r)+ | s == n = nN * log r+ | otherwise =+ stirlerr n - stirlerr s - stirlerr (n - s)+ - bd0 sN (nN * r) - bd0 fN (nN * (1 - r))+ + 0.5 * log (nN / (tau * sN * fN))+ where+ !nN = fromIntegral n :: Double+ !sN = fromIntegral s :: Double+ !fN = fromIntegral (n - s) :: Double++-- the deviance x log(x / np) + np - x, by its series where x is near+-- np, where the direct form cancels+bd0 :: Double -> Double -> Double+bd0 !x !np+ | abs (x - np) < 0.1 * (x + np) =+ let !v = (x - np) / (x + np)+ go !acc !ej !j =+ let !ej' = ej * v * v+ !acc' = acc + ej' / (2 * j + 1)+ in if acc' == acc then acc' else go acc' ej' (j + 1)+ in go ((x - np) * v) (2 * x * v) (1 :: Double)+ | otherwise = x * log (x / np) + np - x++-- Stirling's error, log k! - (k log k - k + log(tau k) / 2), for k at+-- least one: directly below 16, by its series above+stirlerr :: Int -> Double+stirlerr k+ | k < 16 = log_factorial k - (x * log x - x + 0.5 * log (tau * x))+ | k > 500 = (s0 - s1 / xx) / x+ | k > 80 = (s0 - (s1 - s2 / xx) / xx) / x+ | k > 35 = (s0 - (s1 - (s2 - s3 / xx) / xx) / xx) / x+ | otherwise = (s0 - (s1 - (s2 - (s3 - s4 / xx) / xx) / xx) / xx) / x+ where+ !x = fromIntegral k :: Double+ !xx = x * x+ s0 = 1 / 12+ s1 = 1 / 360+ s2 = 1 / 1260+ s3 = 1 / 1680+ s4 = 1 / 1188++-- log k!, for small k+log_factorial :: Int -> Double+log_factorial k = L.foldl' (\acc j -> acc + log (fromIntegral j)) 0 [2 .. k]++tau :: Double+tau = 2 * pi
+ lib/Numeric/Eproc/Merge.hs view
@@ -0,0 +1,99 @@+{-# OPTIONS_HADDOCK prune #-}+{-# LANGUAGE BangPatterns #-}++-- |+-- Module: Numeric.Eproc.Merge+-- Copyright: (c) 2026 Jared Tobin+-- License: MIT+-- Maintainer: Jared Tobin <jared@ppad.tech>+--+-- Merging e-values, and choosing among the hypotheses they test.+--+-- An e-value for a null @H_0@ is a nonnegative statistic @E@ with+-- @E[E] <= 1@ under @H_0@. Two ways of merging them keep that+-- property:+--+-- * The mean of any e-values for one null is an e-value for it,+-- however they depend on one another ('log_mean'): the merge a+-- test over several observables makes, paying a factor of their+-- number.+--+-- * The product of e-values each valid given those before it (for+-- instance, computed on independent data) is an e-value+-- ('log_product'): the merge of a test continued on fresh data.+--+-- An e-process evaluated at a stopping time is an e-value, so both+-- apply to e-processes stopped when the caller likes.+--+-- Given e-values for several nulls, one each, 'ebh' chooses which to+-- reject: the e-BH procedure of Wang & Ramdas (2022), whose false+-- discovery rate is at most its level under any dependence between+-- the e-values.+--+-- Every function here takes and returns e-values as their natural+-- logarithms, as the test modules' @log_evalue@ accessors report+-- them.++module Numeric.Eproc.Merge (+ log_mean+ , log_product+ , ebh+ ) where++import qualified Data.List as L+import Data.Ord (Down(..), comparing)++-- | The log of the mean of e-values given as logs: an e-value for+-- the null they share, whatever their dependence. The mean of no+-- e-values is taken to be one.+--+-- >>> round (exp (log_mean [log 2, log 4]) * 1000)+-- 3000+-- >>> log_mean []+-- 0.0+-- >>> log_mean [1 / 0, 0]+-- Infinity+log_mean :: [Double] -> Double+log_mean les = case les of+ [] -> 0+ (l : ls) ->+ let !m = L.foldl' max l ls+ !s = L.foldl' (\ !acc v -> acc + exp (v - m)) 0 les+ !k = fromIntegral (length les) :: Double+ -- an infinite e-value, of either sign, is the mean's sign too: an+ -- e-value of zero among no greater, or one infinitely great+ in if isInfinite m+ then m+ else m + log s - log k+{-# INLINE log_mean #-}++-- | The log of the product of e-values given as logs: an e-value+-- where each is valid given those before it.+--+-- >>> log_product [log 2, log 3] == log 6+-- True+log_product :: [Double] -> Double+log_product = L.foldl' (+) 0+{-# INLINE log_product #-}++-- | The e-BH discoveries at a level among e-values, one per null,+-- given as logs: the indices of the @k@ largest, for the largest+-- @k@ whose @k@-th largest e-value is at least @n \/ (alpha k)@, for+-- @n@ of them, in decreasing order of e-value. The expected share+-- of discoveries whose null holds is at most @alpha@, under any+-- dependence between the e-values.+--+-- >>> ebh 0.1 [log 100, 0, log 14]+-- [0]+-- >>> ebh 0.1 [log 100, 0, log 15]+-- [0,2]+ebh :: Double -> [Double] -> [Int]+ebh !alpha les = take k ranked+ where+ !n = fromIntegral (length les) :: Double+ ranked = fmap fst (L.sortBy (comparing (Down . snd)) (zip [0 ..] les))+ sorted = L.sortBy (comparing Down) les+ !k = L.foldl' max 0+ [ j+ | (j, e) <- zip [ 1 .. ] sorted+ , e >= log (n / (alpha * fromIntegral j)) ]
+ lib/Numeric/Eproc/TwoSample.hs view
@@ -0,0 +1,330 @@+{-# OPTIONS_HADDOCK prune #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE RecordWildCards #-}++-- |+-- Module: Numeric.Eproc.TwoSample+-- Copyright: (c) 2026 Jared Tobin+-- License: MIT+-- Maintainer: Jared Tobin <jared@ppad.tech>+--+-- Anytime-valid two-sample test of equality in law, by a hedge of+-- e-processes on an antisymmetric statistic.+--+-- Draw pairs @(a_t, b_t)@, one from each of two laws, independently.+-- Under the null that the laws are equal the pair is exchangeable,+-- so any antisymmetric function of it, @f(a, b) = -f(b, a)@, is+-- symmetric about zero, whatever the law. The hedge bets on several+-- at once, each a component e-process for the null:+--+-- * the sign of the difference @d = a - b@ (ties skipped), against+-- one law running above the other ("Numeric.Eproc.Bernoulli.TwoSided");+--+-- * @d@ clipped at each of some bounds, against a shift in mean,+-- without letting rare large differences dominate+-- ("Numeric.Eproc.Bounded");+--+-- * at each of some cut points @q@, @1[a <= q] - 1[b <= q]@, against+-- the laws' distribution functions differing at @q@ (a change in+-- spread, say, that leaves the mean alone).+--+-- The hedge's e-value is the components' mean ("Numeric.Eproc.Merge"),+-- an e-process for the null; the test rejects when its supremum so+-- far reaches @1 \/ alpha@, with probability at most @alpha@ under the+-- null, at any stopping time. The hedge's price is the log of its+-- number of components, against power on each.+--+-- Nothing ties the statistic to a pair. 'update' takes any statistic+-- symmetric about zero under the null, and one per cut point bounded+-- by a given bound: the energy of a quartet (two draws from each of+-- two laws), say, which swapping two of its draws negates. 'update_pair'+-- makes the statistics of a pair.+--+-- Under an interval null ('configInterval'), that the clipped+-- difference's mean lies within a margin of zero, the clipped+-- components bet against the interval and alone make the hedge's+-- e-value; the sign and indicator components test the sharp null,+-- and are stepped beside it but not mixed.+--+-- The clip bounds and cut points must not depend on the data the+-- test sees: fix them from a warmup the test then discards+-- ('clip_bound', 'cut_points').+--+-- == Example+--+-- >>> let Right cfg = config 1.0e-3 [1.0, 4.0] 1 [0.5]+-- >>> let ps = take 2000 (cycle [(1, 0), (1, 0), (0, 0), (1, 1)])+-- >>> decide cfg (foldl' (update_pair cfg) (initial cfg) ps)+-- Reject++module Numeric.Eproc.TwoSample (+ -- * Configuration and state+ Config+ , State+ , Verdict(..)+ , ConfigError(..)++ -- * Construction+ , config+ , configInterval+ , initial++ -- * Calibration+ , clip_bound+ , cut_points++ -- * Streaming+ , update+ , update_pair+ , decide++ -- * Inspection+ , log_evalue+ , log_evalue_sup+ , log_evalue_sign+ , log_evalue_magnitude+ , log_evalue_cdf+ , samples+ ) where++import qualified Data.List as L++import qualified Numeric.Eproc.Bernoulli.TwoSided as Sign+import qualified Numeric.Eproc.Bounded as Magn+import Numeric.Eproc.Common (Bettor(..), ConfigError(..), Verdict(..),+ finite)+import Numeric.Eproc.Merge (log_mean)++-- | Hedge configuration.+data Config = Config {+ cfg_alpha :: {-# UNPACK #-} !Double+ , cfg_log_thresh :: {-# UNPACK #-} !Double -- log (1 / alpha)+ , cfg_sign :: !Sign.Config+ , cfg_magn :: ![(Double, Magn.Config)] -- each clip bound, its+ -- test+ , cfg_cdf_bound :: {-# UNPACK #-} !Double+ , cfg_cdf :: !Magn.Config -- shared by every cut+ , cfg_cuts :: ![Double]+ , cfg_interval :: !Bool -- an interval null+ }++-- | The hedge after some observations.+data State = State {+ st_n :: {-# UNPACK #-} !Int+ , st_sign :: !Sign.State+ , st_magn :: ![Magn.State]+ , st_cdf :: ![Magn.State]+ , st_sup :: {-# UNPACK #-} !Double -- the log e-value's supremum+ }++-- | Build a 'Config' for the sharp null, at a level in @(0, 1)@, from+-- positive clip bounds, the positive bound of the indicator+-- statistics (one for a pair's), and the cut points.+--+-- >>> either (const False) (const True) (config 1.0e-3 [1, 4] 1 [0])+-- True+config+ :: Double -- ^ significance level @alpha@+ -> [Double] -- ^ clip bounds+ -> Double -- ^ indicator statistics' bound+ -> [Double] -- ^ cut points+ -> Either ConfigError Config+config = mk Nothing+{-# INLINE config #-}++-- | Build a 'Config' for the interval null that the clipped+-- difference's mean lies within a positive margin of zero; each+-- clip bound must exceed the margin.+configInterval+ :: Double -- ^ margin+ -> Double -- ^ significance level @alpha@+ -> [Double] -- ^ clip bounds+ -> Double -- ^ indicator statistics' bound+ -> [Double] -- ^ cut points+ -> Either ConfigError Config+configInterval m = mk (Just m)+{-# INLINE configInterval #-}++mk+ :: Maybe Double -> Double -> [Double] -> Double -> [Double]+ -> Either ConfigError Config+mk margin !alpha bs !u qs+ | not (finite alpha && alpha > 0 && alpha < 1) =+ Left (InvalidAlpha alpha)+ | not (finite u && u > 0) = Left (InvalidBounds (negate u) u)+ | otherwise = do+ s <- Sign.config 0.5 alpha Newton+ ms <- traverse magn bs+ cd <- Magn.config 0 (negate u) u alpha Newton+ pure Config {+ cfg_alpha = alpha+ , cfg_log_thresh = log (1 / alpha)+ , cfg_sign = s+ , cfg_magn = ms+ , cfg_cdf_bound = u+ , cfg_cdf = cd+ , cfg_cuts = qs+ , cfg_interval = maybe False (const True) margin+ }+ where+ magn !b+ | not (finite b && b > 0) = Left (InvalidBounds (negate b) b)+ | otherwise = fmap ((,) b) $ case margin of+ Nothing -> Magn.config 0 (negate b) b alpha Newton+ Just m -> Magn.configInterval (negate m) m (negate b) b alpha+ Newton++-- | The hedge before any observation, its e-value one.+initial :: Config -> State+initial Config{..} = State {+ st_n = 0+ , st_sign = Sign.initial cfg_sign+ , st_magn = strict_map (Magn.initial . snd) cfg_magn+ , st_cdf = strict_map (const (Magn.initial cfg_cdf)) cfg_cuts+ , st_sup = 0+ }++-- a map whose list is whole, spine and elements, when evaluated at+-- all, as update's are+strict_map :: (a -> b) -> [a] -> [b]+strict_map f = go+ where+ go (x : xs) = let !y = f x+ !ys = go xs+ in y : ys+ go [] = []+{-# INLINE initial #-}++-- calibration ---------------------------------------------------------------++-- | A clip bound from a warmup's statistics: twice the nearest-rank+-- p99 of their magnitudes (the @ceiling (0.99 m)@-th smallest of+-- @m@), and at least a floor.+--+-- >>> clip_bound 1 [0.1, 0.2, -0.3]+-- 1.0+-- >>> clip_bound 0 (replicate 99 1 ++ [1.0e9])+-- 2.0+clip_bound :: Double -> [Double] -> Double+clip_bound !floor_ ds = max floor_ (2 * nearest 0.99 (L.sort (fmap abs ds)))+{-# INLINE clip_bound #-}++-- | Cut points from a warmup's pooled values: their nearest-rank+-- quantiles at 0.10, 0.25, 0.50, 0.75 and 0.90, ascending, alike+-- ones once. None from no values.+--+-- >>> cut_points [1, 2, 3, 4]+-- [1.0,2.0,3.0,4.0]+cut_points :: [Double] -> [Double]+cut_points xs = case L.sort xs of+ [] -> []+ sorted -> dedup [ nearest q sorted | q <- [0.10, 0.25, 0.50, 0.75, 0.90] ]+ where+ dedup (a : b : rest)+ | a == b = dedup (b : rest)+ | otherwise = a : dedup (b : rest)+ dedup ys = ys++-- the nearest-rank order statistic at a level of a sorted list: its+-- ceiling (q m)-th smallest of m, zero of an empty list+nearest :: Double -> [Double] -> Double+nearest !q xs = case drop i xs of+ x : _ -> x+ [] -> 0+ where+ !m = length xs+ !i = max 0 (min (m - 1) (ceiling (q * fromIntegral m) - 1))++-- streaming -----------------------------------------------------------------++-- | The hedge after one more observation: a statistic symmetric about+-- zero under the null, and one indicator statistic per cut point,+-- within the indicators' bound (clipped to it otherwise).+--+-- /Precondition/: one indicator statistic per cut point, in their+-- order; any beyond them are ignored.+update :: Config -> State -> Double -> [Double] -> State+update cfg@Config{..} State{..} !d cs =+ let !sg | d == 0 = st_sign+ | otherwise = Sign.update cfg_sign st_sign (d > 0)+ !mg = step_magn cfg_magn st_magn+ !cd = step_cdf cs st_cdf+ st' = State (st_n + 1) sg mg cd st_sup+ !le = log_evalue cfg st'+ in st' { st_sup = max st_sup le }+ where+ step_magn ((b, c) : bt) (s : ss) =+ let !s' = Magn.update c s (clip b d)+ !rest = step_magn bt ss+ in s' : rest+ step_magn _ _ = []+ step_cdf (x : xs) (s : ss) =+ let !s' = Magn.update cfg_cdf s (clip cfg_cdf_bound x)+ !rest = step_cdf xs ss+ in s' : rest+ step_cdf _ _ = []++-- | The hedge after one more pair: its difference, and at each cut+-- point whether its first value lies at or below it, less whether+-- its second does (the indicators' bound being one).+update_pair :: Config -> State -> (Double, Double) -> State+update_pair cfg st (!a, !b) =+ update cfg st (a - b) [ below a q - below b q | q <- cfg_cuts cfg ]+ where+ below x q = if x <= q then 1 else 0+{-# INLINE update_pair #-}++clip :: Double -> Double -> Double+clip !b !x+ | x > b = b+ | x < negate b = negate b+ | otherwise = x+{-# INLINE clip #-}++-- | 'Reject' iff the hedge's log e-value has reached @log(1 \/ alpha)@+-- at some observation so far.+decide :: Config -> State -> Verdict+decide Config{..} State{..}+ | st_sup >= cfg_log_thresh = Reject+ | otherwise = Continue+{-# INLINE decide #-}++-- inspection ----------------------------------------------------------------++-- | The hedge's current log e-value: the log of its components' mean,+-- of the clipped components' alone under an interval null.+log_evalue :: Config -> State -> Double+log_evalue Config{..} State{..}+ | cfg_interval = log_mean (fmap Magn.log_evalue st_magn)+ | otherwise = log_mean+ (Sign.log_evalue st_sign+ : fmap Magn.log_evalue st_magn <> fmap Magn.log_evalue st_cdf)+{-# INLINE log_evalue #-}++-- | The supremum so far of the hedge's log e-value; zero before any+-- observation.+log_evalue_sup :: State -> Double+log_evalue_sup = st_sup+{-# INLINE log_evalue_sup #-}++-- | The sign component's current log e-value.+log_evalue_sign :: State -> Double+log_evalue_sign = Sign.log_evalue . st_sign+{-# INLINE log_evalue_sign #-}++-- | Each clipped component's current log e-value, in the order of the+-- clip bounds.+log_evalue_magnitude :: State -> [Double]+log_evalue_magnitude = fmap Magn.log_evalue . st_magn+{-# INLINE log_evalue_magnitude #-}++-- | Each indicator component's current log e-value, in the order of+-- the cut points.+log_evalue_cdf :: State -> [Double]+log_evalue_cdf = fmap Magn.log_evalue . st_cdf+{-# INLINE log_evalue_cdf #-}++-- | How many observations the hedge has seen.+samples :: State -> Int+samples = st_n+{-# INLINE samples #-}
ppad-eproc.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: ppad-eproc-version: 0.5.1+version: 0.5.2 synopsis: Anytime-valid sequential testing via e-processes. license: MIT license-file: LICENSE@@ -41,8 +41,11 @@ Numeric.Eproc.Bounded Numeric.Eproc.Common Numeric.Eproc.ConfSeq+ Numeric.Eproc.ConfSeq.Bernoulli+ Numeric.Eproc.Merge Numeric.Eproc.Mixture Numeric.Eproc.Paired+ Numeric.Eproc.TwoSample build-depends: base >= 4.9 && < 5
test/Main.hs view
@@ -3,6 +3,7 @@ module Main where import Data.Bits+import Numeric (expm1) import qualified Data.List as L import Data.Word import qualified Numeric.Eproc.Bernoulli as Bern@@ -10,8 +11,11 @@ import qualified Numeric.Eproc.Bounded as Bounded import qualified Numeric.Eproc.Common as C import qualified Numeric.Eproc.ConfSeq as CS+import qualified Numeric.Eproc.ConfSeq.Bernoulli as CSB+import qualified Numeric.Eproc.Merge as Merge import qualified Numeric.Eproc.Mixture as Mix import qualified Numeric.Eproc.Paired as P+import qualified Numeric.Eproc.TwoSample as TS import Test.Tasty import Test.Tasty.HUnit import qualified Test.Tasty.QuickCheck as QC@@ -32,6 +36,9 @@ , evalue_accessor_tests , mixture_tests , confseq_tests+ , merge_tests+ , bernoulli_confseq_tests+ , hedge_tests ] -- partial helper: tests below hardcode valid configs.@@ -1073,3 +1080,203 @@ assertLeftCS e = case e of Left _ -> pure () Right _ -> assertFailure "expected Left"++-- merging e-values -----------------------------------------------------------++merge_tests :: TestTree+merge_tests = testGroup "merge" [+ testCase "the mean of no e-values is one" $+ Merge.log_mean [] @?= 0+ , testCase "the mean of e-values" $+ assertBool "mean of 2 and 4 is not 3" $+ abs (exp (Merge.log_mean [log 2, log 4]) - 3) < 1.0e-12+ , testCase "the mean of nil e-values is nil" $+ Merge.log_mean [log 0, log 0] @?= log 0+ , testCase "an infinite e-value's mean is infinite" $ do+ Merge.log_mean [1 / 0, 0] @?= 1 / 0+ Merge.ebh 0.05 [1 / 0, 0] @?= [0]+ , testCase "a product of e-values" $+ assertBool "product of 2 and 3 is not 6" $+ abs (Merge.log_product [log 2, log 3] - log 6) < 1.0e-12+ , testCase "e-BH: the largest alone at its threshold" $+ Merge.ebh 0.1 [log 100, 0, log 14] @?= [0]+ , testCase "e-BH: a second at its threshold" $+ Merge.ebh 0.1 [log 100, 0, log 15] @?= [0, 2]+ , testCase "e-BH: none" $+ Merge.ebh 0.1 [0, 1, 2] @?= []+ , QC.testProperty "the mean lies between the least and the greatest" $+ QC.forAll (QC.listOf1 (QC.choose (-20, 20))) $ \les ->+ let m = Merge.log_mean les+ in m >= minimum les - 1.0e-9 && m <= maximum les + 1.0e-9+ ]++-- bernoulli confidence sequence ---------------------------------------------++bernoulli_confseq_tests :: TestTree+bernoulli_confseq_tests = testGroup "bernoulli confidence sequence" [+ testCase "no trials, the whole interval" $ do+ let cfg = ok (CSB.config 0.05)+ CSB.interval cfg (CSB.initial cfg) @?= (0, 1)+ , testCase "counts that cannot be" $ do+ assertBool "more successes than trials" $+ maybe True (const False) (CSB.from_counts 3 2)+ assertBool "negative successes" $+ maybe True (const False) (CSB.from_counts (-1) 2)+ , testCase "streaming agrees with counts" $ do+ let cfg = ok (CSB.config 0.05)+ xs = take 100 (cycle [True, False, False])+ st = L.foldl' (CSB.update cfg) (CSB.initial cfg) xs+ Just (CSB.interval cfg st) @?=+ fmap (CSB.interval cfg) (CSB.from_counts 34 100)+ , testCase "an interval holds its estimate" $ do+ let cfg = ok (CSB.config 0.05)+ Just st = CSB.from_counts 30 100+ (lo, hi) = CSB.interval cfg st+ assertBool (show (lo, hi)) $ lo < 0.3 && 0.3 < hi+ , testCase "no successes: from zero" $ do+ let cfg = ok (CSB.config 0.05)+ Just st = CSB.from_counts 0 1000+ (lo, hi) = CSB.interval cfg st+ assertBool (show (lo, hi)) $ lo == 0 && hi > 0 && hi < 0.02+ , testCase "coverage of a small rate, every trial at once" $ do+ -- a rate of 0.01 over 2000 trials, checked after every trial+ let cfg = ok (CSB.config 0.05)+ misses = length (filter id+ (take 200 (fmap (csb_misses cfg 0.01 2000)+ (gen_seq (mk_gen 515151)))))+ assertBool ("missed " ++ show misses ++ " of 200") $ misses <= 16+ , testCase "no successes in very many trials: the exact end" $+ -- with s = 0 the end solves -log(n + 1) - n log(1 - r) =+ -- log(1 / alpha) in closed form+ mapM_ (\n -> do+ let cfg = ok (CSB.config 0.05)+ Just st = CSB.from_counts 0 n+ (_, hi) = CSB.interval cfg st+ nd = fromIntegral n :: Double+ exact = negate (expm1 (negate (log 20 + log (nd + 1)) / nd))+ assertBool (show (n, hi, exact)) $+ abs (hi - exact) / exact < 1.0e-9)+ [10, 1000, 10 ^ (6 :: Int), 10 ^ (12 :: Int), 10 ^ (16 :: Int)]+ , testCase "all successes in very many trials: the exact end" $ do+ let cfg = ok (CSB.config 0.05)+ n = 10 ^ (16 :: Int)+ Just st = CSB.from_counts n n+ (lo, _) = CSB.interval cfg st+ nd = fromIntegral n :: Double+ exact = exp (negate (log 20 + log (nd + 1)) / nd)+ assertBool (show (lo, exact)) $ abs (lo - exact) < 1.0e-12+ , testCase "a rate in very many trials: an interval about it" $ do+ -- 3 in 10 of 10^15 trials: an interval of half-width ~ 1e-7+ let cfg = ok (CSB.config 0.05)+ n = 10 ^ (15 :: Int)+ Just st = CSB.from_counts (3 * n `div` 10) n+ (lo, hi) = CSB.interval cfg st+ assertBool (show (lo, hi)) $+ lo < 0.3 && 0.3 < hi && hi - lo > 1.0e-8 && hi - lo < 1.0e-6+ , testCase "intervals shrink onto a rate" $ do+ -- half-width ~ sqrt(2 r (1 - r) (log 1000 + log(tau n r (1 - r)) / 2)+ -- / n) = 0.022 at r = 0.3, n = 10000+ let cfg = ok (CSB.config 1.0e-3)+ Just st = CSB.from_counts 3000 10000+ (lo, hi) = CSB.interval cfg st+ assertBool (show (lo, hi)) $ lo <= 0.3 && 0.3 <= hi && hi - lo < 0.05+ ]++-- whether a rate's interval misses it at any of some trials+csb_misses :: CSB.Config -> Double -> Int -> Gen -> Bool+csb_misses cfg p n g0 = go 0 g0 (CSB.initial cfg)+ where+ go !i !g !st+ | i >= n = False+ | otherwise =+ let (u, g') = next_double g+ st' = CSB.update cfg st (u < p)+ (lo, hi) = CSB.interval cfg st'+ in (p < lo || p > hi) || go (i + 1) g' st'++-- two-sample hedge -----------------------------------------------------------++hedge_tests :: TestTree+hedge_tests = testGroup "two-sample hedge" [+ testCase "calibration: clip bound and cut points" $ do+ TS.clip_bound 1 [0.1, -0.2, 0.3] @?= 1+ -- the 99th smallest of a hundred, not the greatest+ TS.clip_bound 0 (fmap fromIntegral [1 .. 100 :: Int]) @?= 198+ TS.clip_bound 0 (replicate 99 1 ++ [1.0e9]) @?= 2+ TS.cut_points [] @?= []+ TS.cut_points [5, 5, 5] @?= [5]+ , testCase "a fresh hedge's e-value is one" $ do+ let cfg = ok (TS.config 0.05 [1, 4] 1 [0.5])+ TS.log_evalue cfg (TS.initial cfg) @?= 0+ , testCase "one law in both: rejects at most at its level" $ do+ let cfg = ok (TS.config 0.05 [2, 8] 1 [0, 1, 2])+ rate = hedge_rate cfg (geometric 0.4) (geometric 0.4) 500 200+ 717171+ assertBool ("rate " ++ show rate) $ rate <= 0.08+ , testCase "a shifted law: rejects" $ do+ let cfg = ok (TS.config 1.0e-3 [2, 8] 1 [0, 1, 2])+ rate = hedge_rate cfg (geometric 0.5) (geometric 0.3) 2000 50+ 727272+ assertBool ("rate " ++ show rate) $ rate >= 0.95+ , testCase "a law changed in spread alone: rejects" $ do+ -- A always 5, B uniform on 3..7: one mean, two spreads+ let cfg = ok (TS.config 1.0e-3 [4, 16] 1 [3, 4, 5, 6])+ rate = hedge_rate cfg (const5) (spread5) 2000 50 737373+ assertBool ("rate " ++ show rate) $ rate >= 0.95+ , testCase "a margin above a shift: does not reject" $ do+ let cfg = ok (TS.configInterval 1.5 1.0e-3 [4, 16] 1 [0, 1, 2])+ rate = hedge_rate cfg (geometric 0.5) (geometric 0.35) 2000 50+ 747474+ assertBool ("rate " ++ show rate) $ rate <= 0.04+ , testCase "a margin below a shift: rejects" $ do+ let cfg = ok (TS.configInterval 0.3 1.0e-3 [4, 16] 1 [0, 1, 2])+ rate = hedge_rate cfg (geometric 0.5) (geometric 0.35) 4000 50+ 757575+ assertBool ("rate " ++ show rate) $ rate >= 0.9+ , testCase "a margin inside a clip bound" $+ assertBool "a margin at a clip bound was accepted" $+ either (const True) (const False)+ (TS.configInterval 1 1.0e-3 [1] 1 [0])+ , QC.testProperty "the supremum bounds the e-value" $+ QC.forAll (QC.listOf ((,) <$> QC.choose (0, 9) <*> QC.choose (0, 9)))+ $ \ps ->+ let cfg = ok (TS.config 0.05 [2, 8] 1 [3, 6])+ st = L.foldl' (TS.update_pair cfg) (TS.initial cfg)+ (fmap (\(a, b) -> (fromIntegral (a :: Int),+ fromIntegral (b :: Int))) ps)+ in TS.log_evalue cfg st <= TS.log_evalue_sup st + 1.0e-12+ ]++-- the trials until a first success, each succeeding with p+geometric :: Double -> Gen -> (Double, Gen)+geometric p = go 1+ where+ go !n g = let (u, g') = next_double g+ in if u < p then (n, g') else go (n + 1) g'++const5 :: Gen -> (Double, Gen)+const5 g = (5, g)++spread5 :: Gen -> (Double, Gen)+spread5 g = let (u, g') = next_double g+ in (fromIntegral (3 + floor (u * 5) :: Int), g')++-- the share of trials, each of at most some pairs, in which the hedge+-- rejects+hedge_rate+ :: TS.Config -> (Gen -> (Double, Gen)) -> (Gen -> (Double, Gen))+ -> Int -> Int -> Word64 -> Double+hedge_rate cfg fa fb budget trials seed =+ let gens = take trials (gen_seq (mk_gen seed))+ rejects = length (filter id (fmap trial gens))+ in fromIntegral rejects / fromIntegral trials+ where+ trial g0 = go 0 g0 (TS.initial cfg)+ where+ go !n !g !st+ | TS.decide cfg st == TS.Reject = True+ | n >= budget = False+ | otherwise =+ let (a, g1) = fa g+ (b, g2) = fb g1+ in go (n + 1) g2 (TS.update_pair cfg st (a, b))