Best arm identification

Best arm identification (BAI) is a sequential one-player game where the player has to find the best action (arm) among a list of actions (arms) by collecting information in the most efficient way. It is a multi-armed bandit game as a player only gets information about an arm by playing it. The most common objective in multi-armed bandit games is to minimize the regret (i.e., play the best action as much as possible), but in BAI, the goal is to find the best arm as efficiently as possible. This problem naturally arises in scenarios such as adaptive clinical trials where the number of patients is limited and the quantification of the confidence in a treatment is important. It also arises in hyperparameter optimization where the goal is to find the optimal choice of hyperparameters for an algorithm with the smallest possible number of experiments, as it can be costly in terms of time, energy, or money. == Stochastic multi-armed bandit == The stochastic multi-armed bandit (MAB) is a sequential game with one player and K {\displaystyle K} actions (arms). Each arm has an unknown probability distribution associated with it. At each turn, the player has to choose one action and receive an observation from the probability distribution associated with the arm. The more you play an arm, the more you get information on its probability distribution. === Best arm identification === In BAI the goal is to find the arm that has the probability distribution with the highest mean. BAI may be either fixed confidence or fixed horizon. In a fixed-confidence game, a confidence level δ {\displaystyle \delta } is fixed at the beginning of the game and the goal is to find the best arm with this confidence level in as few turns as possible. In a fixed horizon game, the number of turns T {\displaystyle T} is fixed, and the goal is to find the best arm with the highest possible confidence in T {\displaystyle T} turns. === Math formalisation === We have one player and K {\displaystyle K} actions (arms). Behind each arm k ∈ { 1 , … , K } {\displaystyle k\in \{1,\ldots ,K\}} lies an unknown distribution ν k {\displaystyle \nu _{k}} with mean μ k {\displaystyle \mu _{k}} . Each distribution ν k {\displaystyle \nu _{k}} belongs to a known family D {\displaystyle {\mathcal {D}}} (such as the set of Gaussian distributions or Bernoulli distributions). At each time step t {\displaystyle t} , the player selects an arm a t {\displaystyle a_{t}} and observes an independent sample X t ∼ ν a t {\displaystyle X_{t}\sim \nu _{a_{t}}} from the corresponding distribution. We will note μ ∗ := max μ a {\displaystyle \mu ^{}:=\max \mu _{a}} the highest mean. An arm a {\displaystyle a} that satisfies μ a = μ ∗ {\displaystyle \mu _{a}=\mu ^{}} is called an optimal arm; otherwise it is called suboptimal arm. In best arm identification (BAI) the objective is to identify an optimal arm. Two main settings for BAI appear in the literature: Fixed confidence: In this setting, one typically assumes that there exists a unique optimal arm. A confidence level δ ∈ ( 0 , 1 ) {\displaystyle \delta \in (0,1)} is specified at the beginning. The algorithm must stop at some finite stopping time τ δ < + ∞ {\displaystyle \tau _{\delta }<+\infty } and return an arm a ^ τ δ {\displaystyle {\hat {a}}_{\tau _{\delta }}} such that the probability of error is bounded: P ( a ^ τ δ ≠ a ∗ ) ≤ δ {\displaystyle \mathbb {P} ({\hat {a}}_{\tau _{\delta }}\neq a^{})\leq \delta } . The objective is to minimize the expected sample complexity E [ τ δ ] {\displaystyle \mathbb {E} [\tau _{\delta }]} . Such a setting appears, for example, when a constraint on the confidence is required (for example, if we require a confidence level of 95%, so δ = 1 − 0.95 = 0.05 {\displaystyle \delta =1-0.95=0.05} ). Fixed horizon: In this setting, the number of samples T {\displaystyle T} is fixed in advance. The goal is to design an algorithm that minimizes the probability of misidentifying the optimal arm: P ( a ^ T ≠ a ∗ ) {\displaystyle \mathbb {P} ({\hat {a}}_{T}\neq a^{})} . This setting appears when the number of experiments is limited (for drug tests, the number of patients can be fixed in advance). === Example of simple modelling === In the case where we have K {\displaystyle K} treatments and we want to be sure with a confidence level of 95% which treatment is the best to heal a specific disease. Each treatment heals or does not heal the disease with a probability μ k {\displaystyle \mu _{k}} , which means that each distribution is a Bernoulli distribution, so D {\displaystyle {\mathcal {D}}} is the set of Bernoulli distributions. We can use a BAI algorithm to minimize E [ τ 0.05 ] {\displaystyle \mathbb {E} [\tau _{0.05}]} , the number of patients required to find the best treatment with probability 95%. == Applications == Best arm identification naturally arises in several practical domains: Adaptive clinical trials: The objective is to identify the most effective treatment based on sequentially collected patient data. Each treatment can be modeled as having an underlying distribution of outcomes. The goal is to identify the treatment with the highest expected outcome with high confidence (fixed confidence setting δ {\displaystyle \delta } ) while minimizing the number of drug test patients (minimise E [ τ δ ] {\displaystyle \mathbb {E} [\tau _{\delta }]} ), as it costs to pay patients for this and we would like to use as little as possible less effective drugs. Hyperparameter tuning: Selecting the best configuration for machine learning models efficiently by treating each hyperparameter setting as an arm. The goal is to find the best hyperparameter with as few experiments possible as experiments are costly in time and in energy == Fixed confidence level == In the fixed-confidence setting, the goal is to design an algorithm that identifies the best arm with a prescribed confidence level δ {\displaystyle \delta } while minimizing the expected number of samples. Any such algorithm requires two key components: Stopping rule: A decision criterion that determines when to stop sampling. Formally, this defines a stopping time τ δ {\displaystyle \tau _{\delta }} and returns an arm a ^ τ δ {\displaystyle {\hat {a}}_{\tau _{\delta }}} such that P ( a ^ τ δ ≠ a ⋆ ) ≤ δ {\displaystyle \mathbb {P} ({\hat {a}}_{\tau _{\delta }}\neq a^{\star })\leq \delta } and P ( τ δ < + ∞ ) = 1 {\displaystyle \mathbb {P} (\tau _{\delta }<+\infty )=1} . Sampling rule: A policy π {\displaystyle \pi } that, at each round t {\displaystyle t} , selects the next arm to sample a t {\displaystyle a_{t}} based on all previous observations ( a s , X s ) s < t {\displaystyle (a_{s},X_{s})_{s

Esdat

ESdat is a data management, analysis and reporting software for environmental and groundwater data, developed by EarthScience Information Systems (EScIS). It is used to manage many types of environmental data including laboratory chemistry (analytical results, QA data, lab sample planning, and electronic Chain of Custody), field chemistry (water, gas, and soil), hydrogeological data (groundwater, borehole and well construction, lithological, geotechnical and stratigraphic, and LNAPL), meteorological data (rain, wind, and temperature), emission data (dust deposition, HiVol, air quality, and noise) and logger data. Data can be compared against environmental standards or site-specific trigger levels to generate exceedence tables, time series graphs, maps, statistics, and other outputs. ESdat integrates with Power BI and ArcGIS and data can also be exported in a range of other database formats, including USEPA Regions 2,4 & 5, and NYS DEC. ESdat is used by environmental consultants, government, mining and industry for validation, interrogation, and reporting of data derived from complex environmental programs, such as contaminated sites, groundwater investigations, and regulatory compliance for landfills or mining operations.

Anti-Grain Geometry

Anti-Grain Geometry (AGG) is a 2D rendering graphics library written in C++. It features anti-aliasing and sub-pixel resolution. It is not a graphics library, per se, but rather a framework to build a graphics library upon. The library is operating system independent and renders to an abstract memory object. It comes with examples interfaced to the X Window System, Microsoft Windows, Mac OS X, AmigaOS, BeOS, SDL. The examples also include an SVG viewer. The design of AGG uses C++ templates only at a very high level, rather than extensively, to achieve the flexibility to plug custom classes into the rendering pipeline, without requiring a rigid class hierarchy, and allows the compiler to inline many of the method calls for high performance. For a library of its complexity, it is remarkably lightweight: it has no dependencies above the standard C++ libraries and it avoids the C++ STL in the implementation of the basic algorithms. The implicit interfaces are not well documented, however, and this can make the learning process quite cumbersome. While AGG version 2.5 is licensed under the GNU General Public License, version 2 or greater, AGG version 2.4 is still available under the 3-clause BSD license and is virtually the same as version 2.5. == History == Active development of the AGG codebase stalled in 2006, around the time of the v2.5 release, due to shifting priorities of its main developer and maintainer Maxim Shemanarev. M. Shemanarev remained active in the community until his sudden death in 2013. Development has continued on a fork of the more liberally licensed v2.4 on SourceForge.net. == Usage == The Haiku operating system uses AGG in its windowing system. It is one of the renderers available for use in GNU's Gnash Flash player. Graphical version of Rebol language interpreter is using AGG for scalable vector graphics DRAW dialect. Hilti uses it in some of their rebar detection tools, like the PS 1000. Matplotlib uses AGG as its canonical renderer for interactive user interfaces. fpGUI Toolkit has an optional AggPas back-end rendering engine. Work is being done to make AggPas the default or sole rendering engine for fpGUI. Mapnik, the toolkit that renders the maps on the OpenStreetMap website, uses AGG for all its bitmap map rendering by default. HTTPhotos uses AGG to scale photos. Pdfium, the PDF rendering engine used by Google Chrome makes use of AGG, although work is progressing to replace this with Skia Graphics Engine. Graphics Mill, the .NET imaging SDK uses AGG as its drawing engine. Image-Line FL Studio, a digital audio workstation, since version 10.8 released on September 30, 2012, uses AGG for drawing. Native Instruments's Supercharger and Supercharger GT compressors use AGG for its user interface. == Author == The main author of the library was Maxim Shemanarev (Russian: Максим Шеманарёв). On November 26, 2013 Shemanarev (born June 15, 1966, Nizhny Novgorod, Russia) was reported dead at the age of 47 at his home in Columbia, Maryland (US). He died suddenly, allegedly from an epileptic seizure that he had suffered for a while. He was a graduate from Nizhny Novgorod State Technical University. Little is known about his personal life. It's known though that he was divorced and his mother was alive at the time of his death. He used to love skiing, snowboarding (in Colorado), and inline skating. He was praised by his friends for his intelligent programming skills.

TIMIT

TIMIT is a corpus of phonemically and lexically transcribed speech of American English speakers of different sexes and dialects. Each transcribed element has been delineated in time. TIMIT was designed to further acoustic-phonetic knowledge and automatic speech recognition systems. It was commissioned by DARPA and corpus design was a joint effort between the Massachusetts Institute of Technology, SRI International, and Texas Instruments (TI). The speech was recorded at TI, transcribed at MIT, and verified and prepared for publishing by the National Institute of Standards and Technology (NIST). There is also a telephone bandwidth version called NTIMIT (Network TIMIT). TIMIT and NTIMIT are not freely available — either membership of the Linguistic Data Consortium, or a monetary payment, is required for access to the dataset. == Data == TIMIT contains ~5 hours of speech, of 10 sentences spoken by each of 630 speakers. The sentences were randomly sampled from a corpus of 2342 sentences. The speakers were native speakers of American English, classified under 8 major dialect regions: New England, Northern, North Midland, South Midland, Southern, New York City, Western, Army Brat (moved around). The speakers were 70% male and 30% female. Recordings were made in a noise-isolated recording booth at Texas Instrument, using a semi-automatic computer system (STEROIDS) to control the presentation of prompts to the speaker and the recording. Two-channel recordings were made using a Sennheiser HMD 414 headset-mounted microphone and a Brüel & Kjær 1/2" far-field pressure microphone (#4165). The speech was digitized at a sample rate of 20 kHz then and downsampled to 16 kHz. == History == The TIMIT telephone corpus was an early attempt to create a database with speech samples. It was published in the year 1988 on CD-ROM and consists of only 10 sentences per speaker. Two 'dialect' sentences were read by each speaker, as well as another 8 sentences selected from a larger set Each sentence averages 3 seconds long and is spoken by 630 different speakers. It was the first notable attempt in creating and distributing a speech corpus and the overall project has produced costs of 1.5 million US$. An update was released in October 1990. It included full 630-speaker corpus; checked and corrected transcriptions; word-alignment transcriptions; NIST SPHERE-headered waveform files and header manipulation software; phonemic dictionary; new test and training subsets balanced for dialectal and phonetic coverage; more extensive documentation. The full name of the project is DARPA-TIMIT Acoustic-Phonetic Continuous Speech Corpus and the acronym TIMIT stands for Texas Instruments/Massachusetts Institute of Technology. The main reason why a corpus of telephone speech was created was to train speech recognition software. In the Blizzard challenge, different software has the obligation to convert audio recordings into textual data and the TIMIT corpus was used as a standardized baseline.

Manual override

A manual override (MO) or manual analog override (MAO) is a mechanism where control is taken from an automated system and given to the user. For example, a manual override in photography refers to the ability for the human photographer to turn off the automatic aperture sizing, automatic focusing, or any other automated system on the camera. Some manual overrides can be used to veto an automated system's judgment when the system is in error. An example of this is a printer's ink level detection: in one case, a researcher found that when he overrode the system, up to 38% more pages could be printed at good quality by the printer than the automated system would have allowed. Automated systems are becoming increasingly common and integrated into everyday objects such as automobiles and domestic appliances. This development of ubiquitous computing raises general issues of policy and law about the need for manual overrides for matters of great importance such as life-threatening situations and major economic decisions. The loyalty of such autonomous devices then becomes an issue. If they follow rules installed by the manufacturer or required by law and refuse to cede control in some situations then the owners of the devices may feel disempowered, alienated and lacking true ownership. == Major incidents == China Airlines Flight 140 crashed, causing many deaths, due to a misunderstanding about the manual overrides for the autopilot. The Take-Off/Go Around system had been activated to abort a landing. It was programmed to ignore manual controls in this situation but the human pilots tried to continue the landing. The conflicting control signals from the pilots and autopilot then resulted in the aircraft stalling and crashing. The autopilot for this aircraft type was then reprogrammed so that it would never ignore a manual override.

Color gradient

In color science, a color gradient (also known as a color ramp or a color progression) specifies a range of position-dependent colors, usually used to fill a region. In assigning colors to a set of values, a gradient is a continuous colormap, a type of color scheme. In computer graphics, the term swatch has come to mean a palette of active colors. == Definitions == Color gradient is a set of colors arranged in a linear order (ordered) A continuous colormap is a curve through a colorspace === Strict definition === A colormap is a function which associate a real value r with point c in color space C {\displaystyle C} f : [ r m i n , r m a x ] ⊂ R → C {\displaystyle f:[r_{min},r_{max}]\subset \mathbf {R} \to C} which is defined by: a colorspace C an increasing sequence of sampling points r 0 < . . . < r m ∈ [ r m i n , r m a x ] {\displaystyle r_{0}<...

Level set (data structures)

In computer science, a level set is a data structure designed to represent discretely sampled dynamic level sets of functions. A common use of this form of data structure is in efficient image rendering. The underlying method constructs a signed distance field that extends from the boundary, and can be used to solve the motion of the boundary in this field. == Chronological developments == The powerful level-set method is due to Osher and Sethian 1988. However, the straightforward implementation via a dense d-dimensional array of values, results in both time and storage complexity of O ( n d ) {\displaystyle O(n^{d})} , where n {\displaystyle n} is the cross sectional resolution of the spatial extents of the domain and d {\displaystyle d} is the number of spatial dimensions of the domain. === Narrow band === The narrow band level set method, introduced in 1995 by Adalsteinsson and Sethian, restricted most computations to a thin band of active voxels immediately surrounding the interface, thus reducing the time complexity in three dimensions to O ( n 2 ) {\displaystyle O(n^{2})} for most operations. Periodic updates of the narrowband structure, to rebuild the list of active voxels, were required which entailed an O ( n 3 ) {\displaystyle O(n^{3})} operation in which voxels over the entire volume were accessed. The storage complexity for this narrowband scheme was still O ( n 3 ) . {\displaystyle O(n^{3}).} Differential constructions over the narrow band domain edge require careful interpolation and domain alteration schemes to stabilise the solution. === Sparse field === This O ( n 3 ) {\displaystyle O(n^{3})} time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998. The sparse field level set method employs a set of linked lists to track the active voxels around the interface. This allows incremental extension of the active region as needed without incurring any significant overhead. While consistently O ( n 2 ) {\displaystyle O(n^{2})} efficient in time, O ( n 3 ) {\displaystyle O(n^{3})} storage space is still required by the sparse field level set method. See for implementation details. === Sparse block grid === The sparse block grid method, introduced by Bridson in 2003, divides the entire bounding volume of size n 3 {\displaystyle n^{3}} into small cubic blocks of m 3 {\displaystyle m^{3}} voxels each. A coarse grid of size ( n / m ) 3 {\displaystyle (n/m)^{3}} then stores pointers only to those blocks that intersect the narrow band of the level set. Block allocation and deallocation occur as the surface propagates to accommodate to the deformations. This method has a suboptimal storage complexity of O ( ( n m ) 3 + m 3 n 2 ) {\displaystyle O\left((nm)3+m^{3}n^{2}\right)} , but retains the constant time access inherent to dense grids. === Octree === The octree level set method, introduced by Strain in 1999 and refined by Losasso, Gibou and Fedkiw, and more recently by Min and Gibou uses a tree of nested cubes of which the leaf nodes contain signed distance values. Octree level sets currently require uniform refinement along the interface (i.e. the narrow band) in order to obtain sufficient precision. This representation is efficient in terms of storage, O ( n 2 ) , {\displaystyle O(n^{2}),} and relatively efficient in terms of access queries, O ( log n ) . {\displaystyle O(\log \,n).} An advantage of the level method on octree data structures is that one can solve the partial differential equations associated with typical free boundary problems that use the level set method. The CASL research group has developed this line of work in computational materials, computational fluid dynamics, electrokinetics, image-guided surgery and controls. === Run-length encoded === The run-length encoding (RLE) level set method, introduced in 2004, applies the RLE scheme to compress regions away from the narrow band to just their sign representation while storing with full precision the narrow band. The sequential traversal of the narrow band is optimal and storage efficiency is further improved over the octree level set. The addition of an acceleration lookup table allows for fast O ( log ⁡ r ) {\displaystyle O(\log r)} random access, where r is the number of runs per cross section. Additional efficiency is gained by applying the RLE scheme in a dimensional recursive fashion, a technique introduced by Nielsen & Museth's similar DT-Grid. === Hash Table Local Level Set === The Hash Table Local Level Set method was introduced in 2011 by Eyiyurekli and Breen and extended in 2012 by Brun, Guittet, and Gibou, only computes the level set data in a band around the interface, as in the Narrow Band Level-Set Method, but also only stores the data in that same band. A hash table data structure is used, which provides an O ( 1 ) {\displaystyle O(1)} access to the data. However, Brun et al. conclude that their method, while being easier to implement, performs worse than a quadtree implementation. They find that as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms. Three main reasons for worse efficiency are listed: to obtain accurate results, a rather large band is required close to the interface, which counterbalances the absence of grid nodes far from the interface; the performances are deteriorated by extrapolation procedures on the outer edges of the local grid and the width of the band restricts the time step and slows down the method. === Point-based === Corbett in 2005 introduced the point-based level set method. Instead of using a uniform sampling of the level set, the continuous level set function is reconstructed from a set of unorganized point samples via moving least squares.