The Lai–Robbins lower bound gives an asymptotic lower bound on the regret that any uniformly good algorithm must incur in the stochastic multi-armed bandit problem. The original result was proved by Tze Leung Lai and Herbert Robbins in 1985 for parametric exponential families. Later work extended the statement to more general classes of distributions. == Multi-armed bandit problem == The multi-armed bandit problem (MAB) is a sequential game in which the player must trade off exploration (to learn) and exploitation (to earn). The player chooses among K {\displaystyle K} actions (arms) with unknown distributions ν = ( ν 1 , … , ν K ) {\displaystyle \nu =(\nu _{1},\dots ,\nu _{K})} . The player is assumed to know a class of distributions D {\displaystyle {\mathcal {D}}} such that for every k {\displaystyle k} one has ν k ∈ D {\displaystyle \nu _{k}\in {\mathcal {D}}} (for example, D {\displaystyle {\mathcal {D}}} may be the family of Gaussian or Bernoulli distributions). At each round t = 1 , … , T {\displaystyle t=1,\dots ,T} the player selects (pulls) an arm a t {\displaystyle a_{t}} and observes a reward X t ∼ ν a t {\displaystyle X_{t}\sim \nu _{a_{t}}} . We denote N a ( t ) := ∑ s = 1 t 1 { a s = a } {\displaystyle N_{a}(t):=\sum _{s=1}^{t}\mathbf {1} _{\{a_{s}=a\}}} the number of times arm a {\displaystyle a} has been pulled in the first t {\displaystyle t} rounds, μ ( ν ) := ( μ 1 , … , μ K ) {\displaystyle \mu (\nu ):=(\mu _{1},\dots ,\mu _{K})} the vector of arm means, where μ k = E X ∼ ν k [ X ] {\displaystyle \mu _{k}=\mathbb {E} _{X\sim \nu _{k}}[X]} , μ ∗ := max a μ a {\displaystyle \mu ^{}:=\max _{a}\mu _{a}} the highest mean Δ a := μ ∗ − μ a ≥ 0 {\displaystyle \Delta _{a}:=\mu ^{}-\mu _{a}\geq 0} the gap of arm a {\displaystyle a} . An arm a {\displaystyle a} with μ a = μ ∗ {\displaystyle \mu _{a}=\mu ^{}} is called an optimal arm; otherwise it is a suboptimal arm. The goal is to minimize the regret at horizon T {\displaystyle T} , defined by R T := ∑ a = 1 K Δ a E [ N a ( T ) ] . {\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\,\mathbb {E} [N_{a}(T)].} Intuitively, the regret is the (expected) total loss compared to always playing an optimal arm: regret = ∑ a ( cost of playing a ) × ( times a is played ) . {\displaystyle {\text{regret}}=\sum _{a}\ ({\text{cost of playing }}a)\times ({\text{times }}a{\text{ is played}}).} An MAB algorithm is a (possibly randomized) policy that, at each round t {\displaystyle t} , choose an arm a_t by using the observations received from previous turns. === Intuitive example === Suppose a farmer must choose, each year, one of K {\displaystyle K} seed varieties to plant. Each variety k {\displaystyle k} has an unknown average yield μ k {\displaystyle \mu _{k}} . If the farmer knew the best variety (with mean μ ∗ {\displaystyle \mu ^{}} ) he would plant it every year; in reality he must try varieties to learn which is best. The cumulative regret after T {\displaystyle T} years measures the total expected loss in yield due to imperfect knowledge. Remarks The model above is the stochastic MAB; there also exist adversarial variants. One may consider a fixed-horizon setting (known T {\displaystyle T} ) or an anytime setting (unknown T {\displaystyle T} ). == Lai–Robbins lower bound == The theorem gives the right amount of time we should pull a suboptimal arm k {\displaystyle k} to distinguish whether we are in the instance with ν k {\displaystyle \nu _{k}} or with ν ~ k {\displaystyle {\tilde {\nu }}_{k}} where ν ~ k {\displaystyle {\tilde {\nu }}_{k}} is such that μ ~ k > μ ∗ {\displaystyle {\tilde {\mu }}_{k}>\mu ^{}} . Knowning a lower bound on the number of pull of every suboptimal arm gives a lower bound on the regret as only suboptimal arms contribute to the regret. Before stating the formal theorem we need to define what is a consistent algorithm. === Consistency (uniformly good algorithms) === Let D {\displaystyle {\mathcal {D}}} be a class of probability distributions and consider K {\displaystyle K} arms with reward distributions ν = ( ν 1 , … , ν K ) ∈ D K {\displaystyle \nu =(\nu _{1},\dots ,\nu _{K})\in {\mathcal {D}}^{K}} . An algorithm is said to be consistent (also called uniformly good) on D K {\displaystyle {\mathcal {D}}^{K}} if, for every instance ν ∈ D K {\displaystyle \nu \in {\mathcal {D}}^{K}} , the expected regret R T ( ν ) {\displaystyle R_{T}(\nu )} grows subpolynomially: ∀ α > 0 , R T ( ν ) = o ( T α ) as T → ∞ {\displaystyle \forall \alpha >0,\qquad R_{T}(\nu )=o(T^{\alpha })\quad {\text{as }}T\to \infty } This assumption excludes algorithms that perform well on some instances but incur linear regret on others. === Formal lower bound === For any suboptimal arm a {\displaystyle a} . For a distribution ν a ∈ D {\displaystyle \nu _{a}\in {\mathcal {D}}} and a threshold x {\displaystyle x} , define K inf ( ν a , x , D ) := inf { KL ( ν a , ν ′ ) : ν ′ ∈ D , μ ′ > x } {\displaystyle {\mathcal {K}}_{\inf }(\nu _{a},x,{\mathcal {D}}):=\inf {\Bigl \{}\operatorname {KL} (\nu _{a},\nu '):\nu '\in {\mathcal {D}},\ \mu '>x{\Bigr \}}} where KL ( ⋅ , ⋅ ) {\displaystyle \operatorname {KL} (\cdot ,\cdot )} denotes the Kullback-Leibler divergence. Then, for any algorithm consistent on D K {\displaystyle {\mathcal {D}}^{K}} and for every instance ν ∈ D K {\displaystyle \nu \in {\mathcal {D}}^{K}} , every suboptimal arm a {\displaystyle a} satisfies E ν [ N a ( T ) ] ≥ ln T K inf ( ν a , μ ∗ , D ) + o ( ln T ) {\displaystyle \mathbb {E} _{\nu }[N_{a}(T)]\geq {\frac {\ln T}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{},{\mathcal {D}})}}+o(\ln T)} Consequently, the regret satisfies R T ( ν ) ≥ ( ∑ a : μ a < μ ∗ Δ a K inf ( ν a , μ ∗ , D ) ) ln T + o ( ln T ) {\displaystyle R_{T}(\nu )\geq \left(\sum _{a:\,\mu _{a}<\mu ^{}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{},{\mathcal {D}})}}\right)\ln T+o(\ln T)} The original 1985 paper established this result for exponential families; later work showed that the bound holds under much weaker assumptions on D {\displaystyle {\mathcal {D}}} . === Intuition === Consistency imposes that, for every ν {\displaystyle \nu } , the number of pulls of an optimal arm must be large. This means that μ ∗ {\displaystyle \mu ^{}} is estimated very accurately. The goal is to determine, for a suboptimal arm k {\displaystyle k} , how many samples are needed to be confident, with the appropriate level of confidence, that μ k < μ ∗ {\displaystyle \mu _{k}<\mu ^{}} . To do so, we use what is called the most confusing instance: an instance close to ν {\displaystyle \nu } such that arm k {\displaystyle k} is optimal. We define it as ν ~ {\displaystyle {\tilde {\nu }}} such that, for all a ≠ k {\displaystyle a\neq k} , ν ~ a = ν a {\displaystyle {\tilde {\nu }}_{a}=\nu _{a}} , and ν ~ k {\displaystyle {\tilde {\nu }}_{k}} is chosen so that μ ~ k > μ ∗ {\displaystyle {\tilde {\mu }}_{k}>\mu ^{}} . The objective is to determine how many samples of arm k {\displaystyle k} are required to distinguish whether we are in the instance with ν k {\displaystyle \nu _{k}} or with ν ~ k {\displaystyle {\tilde {\nu }}_{k}} in terms of KL {\displaystyle \operatorname {KL} } distance. == Algorithms achieving the Lai–Robbins lower bound == Several algorithms are known to achieve the Lai–Robbins asymptotic lower bound under specific assumptions on the reward distribution class D {\displaystyle {\mathcal {D}}} . The following list summarizes a non-exhaustive list of algorithms matching the lower bound. == Extension to other problems == === Structured bandit === A more complexe is structured bandit where we know that the mean of each arm is in a set with some restriction. In this case we can prove a smaller lower bound that use the knowledge of this set. === Best arm identification (BAI) === A similar result has been proved for best arm identification, which is the same game except that, instead of minimizing the regret, the goal is to identify the best arm with probability 1 − δ {\displaystyle 1-\delta } using as few rounds as possible. === Reinforcement Learning (RL) === Similar results have been proved for regret minimization in average-reward reinforcement learning. The order is also ln T {\displaystyle \ln T} , with a constant that depends on the problem.
Bag-of-words model
The bag-of-words (BoW) model is a model of text which uses an unordered collection (a "bag") of words. It is used in natural language processing and information retrieval (IR). It disregards word order (and thus most of syntax or grammar) but captures multiplicity. The bag-of-words model is commonly used in methods of document classification where, for example, the (frequency of) occurrence of each word is used as a feature for training a classifier. It has also been used for computer vision. An early reference to "bag of words" in a linguistic context can be found in Zellig Harris's 1954 article on Distributional Structure. == Definition == The following models a text document using bag-of-words. Here are two simple text documents: Based on these two text documents, a list is constructed as follows for each document: Representing each bag-of-words as a JSON object, and attributing to the respective JavaScript variable: Each key is the word, and each value is the number of occurrences of that word in the given text document. The order of elements is free, so, for example {"too":1,"Mary":1,"movies":2,"John":1,"watch":1,"likes":2,"to":1} is also equivalent to BoW1. It is also what we expect from a strict JSON object representation. Note: if another document is like a union of these two, its JavaScript representation will be: So, as we see in the bag algebra, the "union" of two documents in the bags-of-words representation is, formally, the disjoint union, summing the multiplicities of each element. === Word order === The BoW representation of a text removes all word ordering. For example, the BoW representation of "man bites dog" and "dog bites man" are the same, so any algorithm that operates with a BoW representation of text must treat them in the same way. Despite this lack of syntax or grammar, BoW representation is fast and may be sufficient for simple tasks that do not require word order. For instance, for document classification, if the words "stocks" "trade" "investors" appears multiple times, then the text is likely a financial report, even though it would be insufficient to distinguish between Yesterday, investors were rallying, but today, they are retreating.andYesterday, investors were retreating, but today, they are rallying.and so the BoW representation would be insufficient to determine the detailed meaning of the document. == Implementations == Implementations of the bag-of-words model might involve using frequencies of words in a document to represent its contents. The frequencies can be "normalized" by the inverse of document frequency, or tf–idf. Additionally, for the specific purpose of classification, supervised alternatives have been developed to account for the class label of a document. Lastly, binary (presence/absence or 1/0) weighting is used in place of frequencies for some problems (e.g., this option is implemented in the WEKA machine learning software system). == Hashing trick == A common alternative to using dictionaries is the hashing trick, where words are mapped directly to indices with a hash function. When using a hash function, no memory is required to store a dictionary. In practice, hashing simplifies the implementation of bag-of-words models and improves scalability. Collisions can occur when two words are hashed to the same index, but this happens infrequently and may function as a form of regularization.
T Layout
The T-Layout is an architectural and design concept for web applications, specifically tailored to improve the user experience on mobile devices. It features a horizontally scrollable container divided into three distinct sections, each spanning the full width of the screen, and was developed to optimise space usage and streamline navigation. == Background == The T-Layout introduces horizontal scrolling as a complementary method to the conventional pop-up-based navigation system in mobile web applications. In this layout, the central section which is visible by default upon accessing the application, facilitates the main content of a URL address and is flanked by two "helper" sections. This approach minimises the need for extensive user movements, in order to reach navigation controls typically located at the top of the screen. It is aimed at enhancing the user experience on mobile devices by providing an easier way to access essential content such as the main navigation, e-commerce related screens, or user account related information, ensuring that those elements are readily accessible while requiring minimal user effort. The T-Layout was first implemented by E (e-streetwear.com) in their mobile web app layout, and it was inspired by the interfaces of well-tested native mobile apps like Instagram and Revolut. A study titled "Mobile Navigation and User Preferences Survey" indicated a preference among mobile app users for one-handed usage, primarily navigating with their thumb. These insights led to the T-Layout Experiment, which compared the efficiency of using swipe gestures to access navigational elements against reaching traditional navigation controls. == Development history == It was first released as the mobile layout of E in early 2023. It was originally developed based on six principles: user-centric functionality, lightweight filesize, HTML and CSS implementation with minimal or no use of JavaScript required, suitable both for browser and server-rendering architectures, intuitive design, and improved SEO. The development of the T-Layout was driven by the necessity for more ergonomic and user-friendly interfaces in mobile web applications. Its design, reminiscent of the letter 'T', emerged as a solution to several usability challenges mobile device users face, emphasising ease of access and efficient screen space utilisation. In July 2023, E formalised the concept and its technical specifications, introducing it to the web design and development community. In October 2023 the "Mobile Navigation and User Preferences Survey" was conducted, establishing that the vast majority of individuals prefer to use mobile applications by holding the phone in a one-handed grip, utilising only the thumb for gestures when possible. The subsequent "T-Layout Experiment", designed to measure the time in seconds and the distance (user effort) in pixels, required to access navigational elements by traditionally tapping on fixed-positioned controls compared to swiping anywhere on the screen. The results proved that swipe gestures require less time and much less effort. == Styling and features == The main characteristic of the T-Layout is its horizontal scrolling feature, which can improve navigation efficiency while preserving the functionality of traditionally structured user interfaces. Its Implementation can be achieved with a combination of HTML and styling with CSS as well as precompiled Scss and Sass, CSS-in-JS, and styled JSX. It can be either a purely HTML/CSS solution but JavaScript can be utilised as well to add more specific functionalities, while It can be implemented to both existing and new applications. Its application in server-side rendering architectures will ensure that all its underlying principles apply. Although principally each section in the layout has a distinct role and facilitates specific types of content, the T-Layout as a concept is versatile, and it is adaptable allowing modifications in the layout or how it's implemented to cater to the specific needs of different applications.
Apache Parquet
Apache Parquet is a free and open-source column-oriented data storage format in the Apache Hadoop ecosystem inspired by Google Dremel interactive ad-hoc query system for analysis of read-only nested data. It is similar to RCFile and ORC, the other columnar-storage file formats in Hadoop, and is compatible with most of the data processing frameworks around Hadoop. It provides data compression and encoding schemes with enhanced performance to handle complex data in bulk. == History == The open-source project to build Apache Parquet began as a joint effort between Twitter and Cloudera using the record shredding and assembly algorithm as described in Google's Dremel. Parquet was designed as an improvement on the Trevni columnar storage format created by Doug Cutting, the creator of Hadoop. The name 'parquet' (lit. 'small compartment') refers to a style of decorative flooring and was chosen to "evoke the bottom layer of a database with an interesting layout". The first version, Apache Parquet 1.0, was released in July 2013. Since April 27, 2015, Apache Parquet has been a top-level Apache Software Foundation (ASF)-sponsored project. == Features == Apache Parquet is implemented using the record-shredding and assembly algorithm, which accommodates the complex data structures that can be used to store data. The values in each column are stored in contiguous memory locations, providing the following benefits: Column-wise compression is efficient in storage space Encoding and compression techniques specific to the type of data in each column can be used Queries that fetch specific column values need not read the entire row, thus improving performance Apache Parquet is implemented using the Apache Thrift framework, which increases its flexibility; it can work with a number of programming languages like C++, Java, Python, PHP, etc. As of August 2015, Parquet supports the big-data-processing frameworks including Apache Hive, Apache Drill, Apache Impala, Apache Crunch, Apache Pig, Cascading, Presto and Apache Spark. It is one of the external data formats used by the pandas Python data manipulation and analysis library. == Compression and encoding == In Parquet, compression is performed column by column, which enables different encoding schemes to be used for text and integer data. This strategy also keeps the door open for newer and better encoding schemes to be implemented as they are invented. Parquet supports various compression formats: snappy, gzip, LZO, brotli, zstd, and LZ4. === Dictionary encoding === Parquet has an automatic dictionary encoding enabled dynamically for data with a small number of unique values (i.e. below 105) that enables significant compression and boosts processing speed. === Bit packing === Storage of integers is usually done with dedicated 32 or 64 bits per integer. For small integers, packing multiple integers into the same space makes storage more efficient. === Run-length encoding (RLE) === To optimize storage of multiple occurrences of the same value, run-length encoding is used, which is where a single value is stored once along with the number of occurrences. Parquet implements a hybrid of bit packing and RLE, in which the encoding switches based on which produces the best compression results. This strategy works well for certain types of integer data and combines well with dictionary encoding. == Cloud Storage and Data Lakes == Parquet is widely used as the underlying file format in modern cloud-based data lake architectures. Cloud storage systems such as Amazon S3, Azure Data Lake Storage, and Google Cloud Storage commonly store data in Parquet format due to its efficient columnar representation and retrieval capabilities. Data lakehouse frameworks—including Apache Iceberg, Delta Lake, and Apache Hudi —build an additional metadata layer on top of Parquet files to support features such as schema evolution, time-travel queries, and ACID-compliant transactions. In these architectures, Parquet files serve as the immutable storage layer while the table formats manage data versioning and transactional integrity. == Comparison == Apache Parquet is comparable to RCFile and Optimized Row Columnar (ORC) file formats — all three fall under the category of columnar data storage within the Hadoop ecosystem. They all have better compression and encoding with improved read performance at the cost of slower writes. In addition to these features, Apache Parquet supports limited schema evolution, i.e., the schema can be modified according to the changes in the data. It also provides the ability to add new columns and merge schemas that do not conflict. Apache Arrow is designed as an in-memory complement to on-disk columnar formats like Parquet and ORC. The Arrow and Parquet projects include libraries that allow for reading and writing between the two formats. == Implementations == Known implementations of Parquet include:
Test data management
Test data management (TDM) is a process in software testing concerned with the creation, preparation, and control of data used for testing software systems. It involves supplying datasets required to execute test cases and verifying system behaviour under defined conditions. Test data management is an integral part of the software development lifecycle (SDLC) and is utilized in both manual and automated testing processes. It is applied in environments that use continuous integration and DevOps practices, where test execution requires consistent and repeatable data conditions. == Overview == Test data management includes the generation, selection, and preparation of data for testing purposes, as well as its distribution across test environments. It also involves controlling data versions and ensuring that datasets correspond to specific test scenarios. In many cases, production data is adapted for testing through techniques such as masking or subsetting to reduce size and remove sensitive content. Test data management ensures that test cases are executed with relevant, consistent, and readily available data. This reduces variability in test results and supports reproducibility across test cycles. == Importance == The role of test data management has expanded with the growth of complex, data-driven systems and regulatory requirements governing data usage. Testing often depends on data that reflects real-world conditions, but direct use of production data may introduce security and privacy risks. As a result, organizations apply methods such as data masking and anonymization to meet compliance requirements, including those set by the California Privacy Rights Act (CPRA) and Europe’s General Data Protection Regulation (GDPR). Inadequate control of test data can lead to incomplete test coverage, unreliable test results, or delays in testing processes due to unavailable or inconsistent datasets. == Techniques and tools == Test data management leverages various techniques for preparing and controlling data used in testing. These include the generation of synthetic data, the extraction of subsets from production datasets, and the modification of data to remove or obscure sensitive information. A key technical requirement in these processes is maintaining referential integrity, or ensuring that relationships between data entities remain consistent across different tables and systems after masking or subsetting. Data virtualization is also used to provide access to datasets without full replication. These methods may be implemented using software tools that automate data preparation, masking, and distribution.
Apache Pig
Apache Pig is a high-level platform for creating programs that run on Apache Hadoop. The language for this platform is called Pig Latin. Pig can execute its Hadoop jobs in MapReduce, Apache Tez, or Apache Spark. Pig Latin abstracts the programming from the Java MapReduce idiom into a notation which makes MapReduce programming high level, similar to that of SQL for relational database management systems. Pig Latin can be extended using user-defined functions (UDFs) which the user can write in Java, Python, JavaScript, Ruby or Groovy and then call directly from the language. == History == Apache Pig was originally developed at Yahoo Research around 2006 for researchers to have an ad hoc way of creating and executing MapReduce jobs on very large data sets. In 2007, it was moved into the Apache Software Foundation. === Naming === Regarding the naming of the Pig programming language, the name was chosen arbitrarily and stuck because it was memorable, easy to spell, and for novelty. The story goes that the researchers working on the project initially referred to it simply as 'the language'. Eventually they needed to call it something. Off the top of his head, one researcher suggested Pig, and the name stuck. It is quirky yet memorable and easy to spell. While some have hinted that the name sounds coy or silly, it has provided us with an entertaining nomenclature, such as Pig Latin for the language, Grunt for the shell, and PiggyBank for the CPAN-like shared repository. == Example == Below is an example of a "Word Count" program in Pig Latin: The above program will generate parallel executable tasks which can be distributed across multiple machines in a Hadoop cluster to count the number of words in a dataset such as all the webpages on the internet. == Pig vs SQL == In comparison to SQL, Pig has a nested relational model, uses lazy evaluation, uses extract, transform, load (ETL), is able to store data at any point during a pipeline, declares execution plans, supports pipeline splits, thus allowing workflows to proceed along DAGs instead of strictly sequential pipelines. On the other hand, it has been argued DBMSs are substantially faster than the MapReduce system once the data is loaded, but that loading the data takes considerably longer in the database systems. It has also been argued RDBMSs offer out of the box support for column-storage, working with compressed data, indexes for efficient random data access, and transaction-level fault tolerance. Pig Latin is procedural and fits very naturally in the pipeline paradigm while SQL is instead declarative. In SQL users can specify that data from two tables must be joined, but not what join implementation to use (You can specify the implementation of JOIN in SQL, thus "... for many SQL applications the query writer may not have enough knowledge of the data or enough expertise to specify an appropriate join algorithm."). Pig Latin allows users to specify an implementation or aspects of an implementation to be used in executing a script in several ways. In effect, Pig Latin programming is similar to specifying a query execution plan, making it easier for programmers to explicitly control the flow of their data processing task. SQL is oriented around queries that produce a single result. SQL handles trees naturally, but has no built in mechanism for splitting a data processing stream and applying different operators to each sub-stream. Pig Latin script describes a directed acyclic graph (DAG) rather than a pipeline. Pig Latin's ability to include user code at any point in the pipeline is useful for pipeline development. If SQL is used, data must first be imported into the database, and then the cleansing and transformation process can begin.
Clara.io
Clara.io is web-based freemium 3D computer graphics software developed by Exocortex, a Canadian software company. The free or "Basic" component of their freemium offering, however, places severe restrictions, such as on saving models and importing texture maps, which are undisclosed in the company's own descriptions of their plans.vf TMN == History == Clara.io was announced in July 2013, and first presented as part of the official SIGGRAPH 2013 program later that month. By November 2013, when the open beta period started, Clara.io had 14,000 registered users. Clara.io claimed to have 26,000 registered users in January 2014, which grew to 85,000 by December 2014. Clara.io was permanently shut down on December 31, 2022, but the site is currently still partially functional to logged-in users. == Features == Polygonal modeling Constructive solid geometry Key frame animation Skeletal animation Hierarchical scene graph Texture mapping Photorealistic rendering (streaming cloud rendering using V-Ray Cloud) Scene publishing via HTML iframe embedding FBX, Collada, OBJ, STL and Three.js import/export Collaborative real-time editing Revision control (versioning & history) Scripting, Plugins & REST APIs 3D model library Unlisted and Private scenes (paid subscriptions only). == Technology == Clara.io is developed using HTML5, JavaScript, WebGL and Three.js. Clara.io does not rely on any browser plugins and thus runs on any platform that has a modern standards compliant browser. == Screenshots ==