packages feed

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 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))