| #!/usr/bin/env python3 |
| # Copyright 2022 The ChromiumOS Authors |
| # Use of this source code is governed by a BSD-style license that can be |
| # found in the LICENSE file. |
| |
| """ |
| |
| References |
| ---------- |
| .. [0] https://github.com/scipy/scipy/blob/main/scipy/stats/_resampling.py |
| .. [1] B. Efron and R. J. Tibshirani, An Introduction to the Bootstrap, |
| Chapman & Hall/CRC, Boca Raton, FL, USA (1993) |
| .. [2] Nathaniel E. Helwig, "Bootstrap Confidence Intervals", |
| http://users.stat.umn.edu/~helwig/notes/bootci-Notes.pdf |
| .. [3] Bootstrapping (statistics), Wikipedia, |
| https://en.wikipedia.org/wiki/Bootstrapping_%28statistics%29 |
| """ |
| |
| # This allows us to use the class name as type identifiers inside the |
| # class itself. |
| # https://github.com/google/styleguide/blob/gh-pages/pyguide.md#3193-forward-declarations |
| from __future__ import annotations |
| |
| import multiprocessing as mp |
| import time |
| from typing import Any, Callable, ClassVar, Iterable, Optional |
| |
| from experiment import Experiment |
| import fpsutils |
| import numpy as np |
| import numpy.typing as npt |
| |
| |
| # There are many issues and performance bottlenecks when using |
| # multiprocessing. Checkout some of the articles on |
| # https://thelaziestprogrammer.com/python/a-multiprocessing-pool-pickle . |
| |
| |
| class BootstrapResults: |
| def __init__(self, bootstrap_samples: list[int]) -> None: |
| self._samples = bootstrap_samples |
| |
| def samples(self) -> list[int]: |
| return self._samples |
| |
| def num_samples(self) -> int: |
| return len(self._samples) |
| |
| def confidence_interval( |
| self, confidence_percent: int = 95 |
| ) -> tuple[int, int]: |
| """Calculate confidence interval as documented in ISO 2006. |
| |
| This simply uses percentiles. |
| """ |
| # The output distributions seem to still be right-skewed. |
| # We should probably use BCa for FAR and FRR. |
| # |
| # https://en.wikipedia.org/wiki/Skewness |
| # https://en.wikipedia.org/wiki/Bootstrapping_(statistics) |
| # * Bias-corrected bootstrap – adjusts for bias in the bootstrap |
| # distribution. |
| # * Accelerated bootstrap – The bias-corrected and accelerated (BCa) |
| # bootstrap, by Efron (1987),[14] adjusts for both bias and skewness |
| # in the bootstrap distribution. This approach is accurate in a wide |
| # variety of settings, has reasonable computation requirements, and |
| # produces reasonably narrow intervals.[14] |
| |
| ci_percent_lower = (100 - confidence_percent) / 2 |
| ci_percent_upper = 100 - ci_percent_lower |
| |
| # 95% C.I. |
| boot_limits = np.percentile( |
| self._samples, [ci_percent_lower, ci_percent_upper] |
| ) |
| return boot_limits |
| |
| |
| class Bootstrap: |
| """The base class for implementing a bootstrap sample over an Experiment.""" |
| |
| USE_GLOBAL_SHARING = False |
| """Enables the use of sharing process data by global inheritance. |
| |
| Enable this when the serialization of the `self` data has become too much |
| of a parallelization bottleneck. You can see this IO overhead when running |
| the sample. Looking at the CPU monitor, if CPU loads are not being fully |
| utilized, this could mean that they are blocked on IO. Try enabling this |
| flag. |
| """ |
| |
| __data: ClassVar[Bootstrap] |
| __rng: ClassVar[np.random.Generator] |
| |
| def __init__(self, exp: Experiment, verbose: bool = False) -> None: |
| self._verbose = verbose |
| if self._verbose: |
| print("# Initializing Runtime and Caches.") |
| self._time_init_start = time.time() |
| self._init(exp) |
| self._time_init_end = time.time() |
| |
| self._time_rng_start = 0.0 |
| self._time_rng_end = 0.0 |
| self._time_pool_startup_start = 0.0 |
| self._time_pool_startup_end = 0.0 |
| self._time_samples_start = 0.0 |
| self._time_samples_end = 0.0 |
| |
| def _init(self, exp: Experiment) -> None: |
| """Initialize runtime caches. |
| |
| Implement this. |
| |
| This will be run once before any `_sample` invocations occur. |
| Save the absolute least amount of data in `self` as possible, since |
| this data must be copied to each worker process in certain runtime |
| configurations. |
| |
| Do not save a copy of `exp` itself, since tables may be modified upon |
| accessing them. This can cause unnecessary overhead for each worker |
| thread that could have simply be done once in this init function. |
| """ |
| return |
| |
| def _sample(self, rng: np.random.Generator) -> int: |
| """Complete a single bootstrap sample using. |
| |
| Implement this. |
| |
| Args: |
| rng: The initialized random number generator to use for the sample. |
| |
| Return: |
| Returns that count of values being observed in the sample. |
| """ |
| return 0 |
| |
| @classmethod |
| def _process_global_init(cls, data: Bootstrap): |
| cls.__rng = np.random.default_rng() |
| cls.__data = data |
| |
| @classmethod |
| def _process_global_sample(cls, sample_id: int) -> int: |
| return cls.__data._sample(cls.__rng) |
| |
| def __run_single_process( |
| self, |
| num_samples: int, |
| progress: Callable[[Iterable[Any], int], Iterable[Any]], |
| ) -> list[int]: |
| boot_counts = list() |
| |
| if self._verbose: |
| print("# Initializing RNG.") |
| self._time_rng_start = time.time() |
| rng = np.random.default_rng() |
| self._time_rng_end = time.time() |
| |
| if self._verbose: |
| print("# Starting Bootstrap Samples.") |
| self._time_samples_start = time.time() |
| for _ in progress(range(num_samples), num_samples): |
| boot_counts.append(self._sample(rng)) |
| self._time_samples_end = time.time() |
| |
| return boot_counts |
| |
| def __run_multi_process( |
| self, |
| num_samples: int, |
| num_proc: Optional[int], |
| progress: Callable[[Iterable[Any], int], Iterable[Any]], |
| ) -> list[int]: |
| # All processes must have their own unique seed for their pseudo random |
| # number generator, otherwise they will all generate the same random values. |
| # |
| # For reproducibility and testing, you can use np.random.SeedSequence.spawn |
| # or [np.random.default_rng(i) for i in range(BOOTSTRAP_SAMPLES)] |
| # See https://numpy.org/doc/stable/reference/random/parallel.html . |
| # |
| # We could possible generate fewer random number generators, since we only |
| # need one per process. This might be achievable by using the Pool |
| # constructor's initializer function to add a process local global |
| # rng variable. For now, it is just safer to generate BOOTSTRAP_SAMPLES |
| # random number generators. Do note that you can't really parallelize |
| # the rng initialization, since the CPU doesn't produce enough entropy |
| # to satisfy threads concurrently. They end up just being blocked |
| # on IO. |
| |
| if num_proc == 0: |
| num_proc = mp.cpu_count() |
| |
| if self._verbose: |
| print( |
| f"# Dispatching {num_samples} bootstrap samples over " |
| f"{num_proc} processes." |
| ) |
| |
| if self.USE_GLOBAL_SHARING: |
| # It is my understanding, from experimentation and documentation, |
| # that any normal object passed into the pool.map call will be |
| # serialized and sent to the worker processes. If the objects being |
| # sent are large, this serialization/deserialization can take some |
| # time and can be error prone if there are circular references. |
| # |
| # The worker processes will inherit [without serialization] global |
| # and local context for executing the `initializer` with `initargs`. |
| # We maintain the global context, but loose local references when |
| # executing subsequent pool executions operations. |
| # |
| # There are probably other performant mechanisms for sharing data |
| # efficiently on the same machine, but one of the fastest mechanisms |
| # I have experienced is exploiting the process initializer's lack of |
| # serialization to save the local object reference in each |
| # processes' global state. |
| # Although all permutations of this mechanism are subtle hack, |
| # using a classmethod to silo the global data to the class itself |
| # adds a small amount of scoping. Furthermore, this isn't |
| # necessarily a scope collision with other purposes, since the |
| # global scope is only clobbered within each pool process, not |
| # the parent process. the assumption is that you much reinitialize |
| # a new pool for each Bootsrap sampling. |
| self._time_pool_startup_start = time.time() |
| with mp.Pool( |
| initializer=self._process_global_init, |
| initargs=(self,), |
| processes=num_proc, |
| ) as pool: |
| self._time_pool_startup_end = time.time() |
| |
| if self._verbose: |
| print("# Blastoff.") |
| self._time_samples_start = time.time() |
| boot_counts = pool.map( |
| self._process_global_sample, |
| progress(range(num_samples), num_samples), |
| ) |
| self._time_samples_end = time.time() |
| |
| return boot_counts |
| else: |
| self._time_pool_startup_start = time.time() |
| with mp.Pool(processes=num_proc) as pool: |
| self._time_pool_startup_end = time.time() |
| |
| if self._verbose: |
| print("# Initializing RNGs.") |
| self._time_rng_start = time.time() |
| rngs = progress( |
| (np.random.default_rng(i) for i in range(num_samples)), |
| num_samples, |
| ) |
| self._time_rng_end = time.time() |
| |
| if self._verbose: |
| print("# Blastoff.") |
| self._time_samples_start = time.time() |
| boot_counts = pool.map(self._sample, rngs) |
| self._time_samples_end = time.time() |
| |
| return boot_counts |
| |
| def run( |
| self, |
| num_samples: int = 5000, |
| num_proc: Optional[int] = 0, |
| progress: Callable[ |
| [Iterable[Any], int], Iterable[Any] |
| ] = lambda it, total: iter(it), |
| ) -> BootstrapResults: |
| """Run all bootstrap samples. |
| |
| Args: |
| num_samples: Number of bootstrap samples should be acquired. |
| 1000 samples for 95% CI |
| 5000 samples for 99% CI |
| num_proc: Number of simultaneous processes to use. |
| (None = Sequential | 0 = Max Processors | # = Specific #) |
| progress: An interable function that can track the samples progress. |
| """ |
| |
| if num_proc is None: |
| boot_counts = self.__run_single_process(num_samples, progress) |
| else: |
| boot_counts = self.__run_multi_process( |
| num_samples, num_proc, progress |
| ) |
| |
| if self._verbose: |
| self.print_timing() |
| |
| return BootstrapResults(boot_counts) |
| |
| def print_timing(self): |
| """Print the saved timing values.""" |
| |
| delta_init = self._time_init_end - self._time_init_start |
| delta_rng = self._time_rng_end - self._time_rng_start |
| delta_pool_startup = ( |
| self._time_pool_startup_end - self._time_pool_startup_start |
| ) |
| delta_samples = self._time_samples_end - self._time_samples_start |
| |
| total = delta_init + delta_rng + delta_pool_startup + delta_samples |
| |
| print(f"Cache init took {delta_init:.6f}s.") |
| print(f"RNG init took {delta_rng:.6f}s.") |
| print( |
| f"Process pool setup took {delta_pool_startup:.6f}s" |
| f'{self.USE_GLOBAL_SHARING and " (includes RNG init)" or ""}.' |
| ) |
| print(f"Bootstrap sampling took {delta_samples:.6f}s.") |
| print("-----------------------------------------") |
| print(f"Total combined runtime was {total:.6f}s.") |
| |
| |
| class BootstrapFARFlat(Bootstrap): |
| # For the 100000 sample case, enabling this reduces overall time by |
| # 3 seconds. |
| USE_GLOBAL_SHARING = True |
| |
| def _init(self, exp: Experiment) -> None: |
| far = exp.far_decisions() |
| assert fpsutils.has_columns(far, [Experiment.TableCol.Decision]) |
| self.far_list: npt.NDArray[np.bool_] = np.array( |
| far[Experiment.TableCol.Decision.value] |
| == Experiment.Decision.Accept.value, |
| dtype=bool, |
| ) |
| |
| def _sample(self, rng: np.random.Generator) -> int: |
| """Complete a single flat bootstrap sample""" |
| |
| sample = fpsutils.boot_sample(self.far_list, rng=rng) |
| return np.sum(sample) |
| |
| |
| class BootstrapFullFARHierarchy(Bootstrap): |
| # For the 100000 sample case, enabling this reduces overall time by |
| # 3 seconds. |
| USE_GLOBAL_SHARING = True |
| |
| def _init(self, exp: Experiment) -> None: |
| fa_table = exp.fa_table() |
| # The accepted tuples for fa_set and fa_trie. |
| fa_set_tuple = [ |
| Experiment.TableCol.Verify_User.value, |
| Experiment.TableCol.Enroll_User.value, |
| Experiment.TableCol.Verify_Finger.value, |
| Experiment.TableCol.Enroll_Finger.value, |
| Experiment.TableCol.Verify_Sample.value, |
| ] |
| assert fpsutils.has_columns(fa_table, fa_set_tuple) |
| self.fa_set = fpsutils.DataFrameSetAccess(fa_table, fa_set_tuple) |
| self.fa_trie = fpsutils.DataFrameCountTrieAccess(fa_table, fa_set_tuple) |
| |
| self.users_list = exp.user_list() |
| self.fingers_list = exp.finger_list() |
| self.samples_list = exp.sample_list() |
| |
| # If you add exp, fa_table, and far_decisions to the self object, |
| # it becomes no longer runtime feasible to use USE_GLOBAL_SHARING=False. |
| # For some reason, the total runtime grows with respect to process |
| # count. |
| |
| def _sample(self, rng: np.random.Generator) -> int: |
| """Complete a single bootstrap sample using full hierarchy bootstrap method. |
| |
| The important parts of this approach are the following: |
| * Avoiding DataFrame queries during runtime. We use fa_set cache instead. |
| This is the difference between hundreds of _us_ vs. hundreds of _ns_ |
| per query |
| * Using rng.choice (now boot_sample) on either a scalar, np.array, or list |
| is important. Other methods are very slow. |
| * The big finale that gets the single bootstrap sample time down from |
| tens of _s_ to hundreds of _ms_ is checking for the loop abort path |
| using the fa_trie. |
| |
| Additional Performance: |
| * Use boot_sample_range instead os boot_sample. |
| * Flatten loops. |
| """ |
| |
| user_list = self.users_list |
| fingers_list = self.fingers_list |
| samples_list = self.samples_list |
| |
| fa_set = self.fa_set |
| fa_trie = self.fa_trie |
| |
| sample = [] |
| # 72 users |
| for v in fpsutils.boot_sample(user_list, rng=rng): |
| if not fa_trie.isin((v,)): |
| continue |
| # 72 other template users (same user with different finger is allowed) |
| for t in fpsutils.boot_sample(user_list, rng=rng): |
| if not fa_trie.isin((v, t)): |
| continue |
| # 6 fingers |
| for fv in fpsutils.boot_sample(fingers_list, rng=rng): |
| if not fa_trie.isin((v, t, fv)): |
| continue |
| |
| # FIXME: This is a hack to try to fix the possible |
| # sample pool issue described below. |
| # This is less bad, since there are only 6 fingers. |
| # mod_finger_list = np.array([0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5]) |
| # |
| # It should be known that having this fix here or not |
| # having this fix here does not change the output |
| # percentiles + mean. It also doesn't seem to change the |
| # histogram skew. |
| mod_finger_list = fingers_list |
| # if v == t: |
| # mod_finger_list = np.array(np.where(~(mod_finger_list == fv))) |
| |
| for ft in fpsutils.boot_sample(mod_finger_list, rng=rng): |
| # FIXME: See below conversation. |
| # FIXME: We could have this boot_sample keep running |
| # until it has seen len(fingers_list) or |
| # len(finger_list)-1 legitimate fingers. |
| if not fa_trie.isin((v, t, fv, ft)): |
| continue |
| # 60 verification samples |
| for a in fpsutils.boot_sample(samples_list, rng=rng): |
| # We don't avoid the invalid matching case, |
| # (v == t) and (fv == ft), since it is slower than |
| # simply querying for the results. |
| # We actually don't care about omitting these |
| # cases because it will always receive a 0 from the |
| # query. |
| # As long as we always use the sum operation to |
| # aggregate all subsample data, no problems should |
| # arise. |
| # |
| # TODO: Reverify that allowing the selection of |
| # an invalid match doesn't skew the probabilities, |
| # since you could end up with a sample of all |
| # invalid fingers (given replace=True). |
| # On second thought, this seems like it could be |
| # slightly wrong, but I don't recall why I thought |
| # this should work out to be the same as selecting |
| # always proper matches. |
| # |
| # I guess you only need to reduce the number of |
| # fingers in the selection pool when the users are |
| # the same. |
| # |
| # I think the original logic was that, if we aren't |
| # keeping track of the true accepts, then |
| # why should it matter if there are more |
| # (invalid true-accepts), but I think this is |
| # wrong because it reduces the chance |
| # of getting legitimate false accepts. |
| query = (v, t, fv, ft, a) |
| sample.append(fa_set.isin(query)) |
| # pass |
| return np.sum(sample) |
| |
| |
| class BootstrapFullFRRHierarchy(Bootstrap): |
| # For the 100000 sample case, enabling this reduces overall time by |
| # 3 seconds. |
| USE_GLOBAL_SHARING = True |
| |
| def _init(self, exp: Experiment) -> None: |
| fr_table = exp.fr_table() |
| # The accepted tuples for fa_set and fa_trie. |
| fr_set_tuple = [ |
| Experiment.TableCol.Enroll_User.value, |
| Experiment.TableCol.Enroll_Finger.value, |
| Experiment.TableCol.Verify_Sample.value, |
| ] |
| assert fpsutils.has_columns(fr_table, fr_set_tuple) |
| self.fa_set = fpsutils.DataFrameSetAccess(fr_table, fr_set_tuple) |
| self.fa_trie = fpsutils.DataFrameCountTrieAccess(fr_table, fr_set_tuple) |
| |
| self.users_list = exp.user_list() |
| self.fingers_list = exp.finger_list() |
| self.samples_list = exp.sample_list() |
| |
| # If you add exp, fa_table, and far_decisions to the self object, |
| # it becomes no longer runtime feasible to use USE_GLOBAL_SHARING=False. |
| # For some reason, the total runtime grows with respect to process |
| # count. |
| |
| def _sample(self, rng: np.random.Generator) -> int: |
| """Complete a single bootstrap sample using full hierarchy bootstrap method. |
| |
| The important parts of this approach are the following: |
| * Avoiding DataFrame queries during runtime. We use fa_set cache instead. |
| This is the difference between hundreds of _us_ vs. hundreds of _ns_ |
| per query |
| * Using rng.choice (now boot_sample) on either a scalar, np.array, or list |
| is important. Other methods are very slow. |
| * The big finale that gets the single bootstrap sample time down from |
| tens of _s_ to hundreds of _ms_ is checking for the loop abort path |
| using the fa_trie. |
| |
| Additional Performance: |
| * Use boot_sample_range instead os boot_sample. |
| * Flatten loops. |
| """ |
| |
| user_list = self.users_list |
| fingers_list = self.fingers_list |
| samples_list = self.samples_list |
| |
| fa_set = self.fa_set |
| fa_trie = self.fa_trie |
| |
| sample = [] |
| # 72 users |
| for u in fpsutils.boot_sample(user_list, rng=rng): |
| if not fa_trie.isin((u,)): |
| continue |
| # 6 fingers |
| for f in fpsutils.boot_sample(fingers_list, rng=rng): |
| if not fa_trie.isin((u, f)): |
| continue |
| # 60 verification samples |
| for s in fpsutils.boot_sample(samples_list, rng=rng): |
| query = (u, f, s) |
| sample.append(fa_set.isin(query)) |
| return np.sum(sample) |
