Computer operating systems (OSes) provide a set of functions needed and used by most application programs on a computer, and the links needed to control and synchronize computer hardware. On the first computers, with no operating system, every program needed the full hardware specification to run correctly and perform standard tasks, and its own drivers for peripheral devices like printers and punched paper card readers. The growing complexity of hardware and application programs eventually made operating systems a necessity for everyday use. == Background == Early computers lacked any form of operating system. Instead, the user (rarely also the computer operator), had sole use of the machine for a scheduled period of time. The user would deliver his program to a computer operator who would be responsible for loading the computer with the program and data needed for its 'run'. Eventually, the end of a user's program could be detected and a control program automatically loaded which would load the next user's program, relieving the operator of having to load in each user's program individually and introducing the era of 'batched' programming. That is, a number of user programs could all be loaded together in a batch. Loading of program and data was accomplished in various ways including toggle switches (only used by a user on the earliest of computers, but later used by the computer operator to control the computer, e.g., to start it up, to shut it down, to 'pause', to 'dump' its RAM contents, and/or to control its input and/or its output), punched paper cards and magnetic or paper tape. Once loaded, the machine would be set to execute each program singly until that program completed, crashed, exceeded its time limit or went into a(n infinite) loop. In those early days, there were only 'Control Program' units for providing the software necessary to control the computers and ancillary hardware, e.g., for such semi hardware functions as I/O . None of the early 'Control Programs' were sufficiently sophisticated to recognize a looping user program or initiate a recovery action. Detection and recovery from a looping program was another critical operator function and was usually detected by the sound of the looping computer, whereupon the operator would simply initiate a complete dump of the executing program (for later debugging by the programmer) and then load in (or instruct the computer to go on to) the next user's program. Programs could sometimes be debugged via a control panel using dials, toggle switches and panel lights, making it a very manual and error-prone process. But, this was quite rare, since the high cost of even the simplest of the early computers prohibited such exclusive use of a computer by an individual programmer. Almost all program debugging was done away from any computer by the original programmer perusing the program and the dump of its execution obtained, e.g., by the computer operator or automatically by some computer hardware exception detection (such as a timeout, an attempt to divide by zero, or an over or underflow). Programmers then could only very rarely have more than one computer 'run' per day! Symbolic languages, e.g., assemblers and compilers were developed for programmers to translate symbolic program code into machine code that previously would have been hand-encoded. Later machines came with libraries of support code on punched cards or magnetic tape, which would be linked to the user's program to assist in operations such as input and output. This was the genesis of the modern-day operating system; however, machines still ran a single program or job at a time. At Cambridge University in England the job queue was at one time a string from which tapes attached to corresponding job tickets were hung with stationery pegs. == Mainframes == The first operating system used for real work was GM-NAA I/O, produced in 1956 by General Motors' Research division for its IBM 704. Most other early operating systems for IBM mainframes were also produced by customers. Early operating systems were very diverse, with each vendor or customer producing one or more operating systems specific to their particular mainframe computer. Every operating system, even from the same vendor, could have radically different models of commands, operating procedures, and such facilities as debugging aids. Typically, each time the manufacturer brought out a new machine, there would be a new operating system, and most applications would have to be manually adjusted, recompiled, and retested. === Systems on IBM hardware === Building on customer experience and requirements, IBM took on a more active role in developing operating systems for the 709, 1410, 7010, 7040, 7044, 7090 and 7094. IBM also collaborated with universities. The state of affairs continued until the mid 1960s when IBM, already a leading hardware vendor, stopped work on existing systems and put all its effort into developing the System/360 series of machines, all of which used the same instruction and input/output architecture. IBM intended to develop a single operating system for the new hardware, the OS/360. The problems encountered in the development of the OS/360 are legendary, and are described by Fred Brooks in The Mythical Man-Month—a book that has become a classic of software engineering. Because of performance differences across the hardware range and delays with software development, a whole family of operating systems was introduced instead of a single OS/360. IBM wound up releasing a series of stop-gaps followed by two longer-lived operating systems: OS/360 for mid-range and large systems. This was available in three system generation options: PCP for early users and for those without the resources for multiprogramming. MFT for mid-range systems, replaced by MFT-II in OS/360 Release 15/16. This had one successor, OS/VS1, which was discontinued in the 1980s. MVT for large systems. This was similar in most ways to PCP and MFT (most programs could be ported among the three without being re-compiled), but has more sophisticated memory management and a time-sharing facility, TSO. MVT had several successors including the current z/OS. DOS/360 for small System/360 models had several successors including the current z/VSE. It was significantly different from OS/360. IBM maintained full compatibility with the past, so that programs developed in the sixties can still run under z/VSE (if developed for DOS/360) or z/OS (if developed for MFT or MVT) with no change. IBM also developed TSS/360, a time-sharing system for the System/360 Model 67. Overcompensating for their perceived importance of developing a timeshare system, they set hundreds of developers to work on the project. Early releases of TSS were slow and unreliable; by the time TSS had acceptable performance and reliability, IBM wanted its TSS users to migrate to OS/360 and OS/VS2; while IBM offered a TSS/370 PRPQ, they dropped it after 3 releases. Several operating systems for the IBM S/360 and S/370 architectures were developed by third parties, including the Michigan Terminal System (MTS) and MUSIC/SP. === Other mainframe operating systems === Control Data Corporation developed the SCOPE operating systems in the 1960s, for batch processing and later developed the MACE operating system for time sharing, which was the basis for the later Kronos. In cooperation with the University of Minnesota, the Kronos and later the NOS operating systems were developed during the 1970s, which supported simultaneous batch and time sharing use. Like many commercial time sharing systems, its interface was an extension of the DTSS time sharing system, one of the pioneering efforts in timesharing and programming languages. In the late 1970s, Control Data and the University of Illinois developed the PLATO system, which used plasma panel displays and long-distance time sharing networks. PLATO was remarkably innovative for its time; the shared memory model of PLATO's TUTOR programming language allowed applications such as real-time chat and multi-user graphical games. For the UNIVAC 1107, UNIVAC, the first commercial computer manufacturer, produced the EXEC I operating system, and Computer Sciences Corporation developed the EXEC II operating system and delivered it to UNIVAC. EXEC II was ported to the UNIVAC 1108. Later, UNIVAC developed the EXEC 8 operating system for the 1108; it was the basis for operating systems for later members of the family. Like all early mainframe systems, EXEC I and EXEC II were a batch-oriented system that managed magnetic drums, disks, card readers and line printers; EXEC 8 supported both batch processing and on-line transaction processing. In the 1970s, UNIVAC produced the Real-Time Basic (RTB) system to support large-scale time sharing, also patterned after the Dartmouth BASIC system. Burroughs Corporation introduced the B5000 in 1961 with the MCP (Master Control Program) operating system. The B5000
Texture compression
Texture compression is a specialized form of image compression designed for storing texture maps in 3D computer graphics rendering systems. Unlike conventional image compression algorithms, texture compression algorithms are optimized for random access. Texture compression can be applied to reduce memory usage at runtime. Texture data is often the largest source of memory usage in a mobile application. == Tradeoffs == In their seminal paper on texture compression, Beers, Agrawala and Chaddha list four features that tend to differentiate texture compression from other image compression techniques. These features are: Decoding Speed It is highly desirable to be able to render directly from the compressed texture data and so, in order not to impact rendering performance, decompression must be fast. Random Access Since predicting the order that a renderer accesses texels would be difficult, any texture compression scheme must allow fast random access to decompressed texture data. This tends to rule out many better-known image compression schemes such as JPEG or run-length encoding. Compression Rate and Visual Quality In a rendering system, lossy compression can be more tolerable than for other use cases. Some texture compression libraries, such as crunch, allow the developer to flexibly trade off compression rate vs. visual quality, using methods such as rate–distortion optimization (RDO). Encoding Speed Texture compression is more tolerant of asymmetric encoding/decoding rates as the encoding process is often done only once during the application authoring process. Given the above, most texture compression algorithms involve some form of fixed-rate lossy vector quantization of small fixed-size blocks of pixels into small fixed-size blocks of coding bits, sometimes with additional extra pre-processing and post-processing steps. Block Truncation Coding is a very simple example of this family of algorithms. Because their data access patterns are well-defined, texture decompression may be executed on-the-fly during rendering as part of the overall graphics pipeline, reducing overall bandwidth and storage needs throughout the graphics system. As well as texture maps, texture compression may also be used to encode other kinds of rendering map, including bump maps and surface normal maps. Texture compression may also be used together with other forms of map processing such as mipmaps and anisotropic filtering. == Availability == Some examples of practical texture compression systems are S3 Texture Compression (S3TC), PVRTC, Ericsson Texture Compression (ETC) and Adaptive Scalable Texture Compression (ASTC); these may be supported by special function units in modern graphics processing units (GPUs). OpenGL and OpenGL ES, as implemented on many video accelerator cards and mobile GPUs, can support multiple common kinds of texture compression - generally through the use of vendor extensions. == Supercompression == A compressed-texture can be further compressed in what is called "supercompression". Fixed-rate texture compression formats are optimized for random access and are much less efficient compared to image formats such as PNG. By adding further compression, a programmer can reduce the efficiency gap. The extra layer can be decompressed by the CPU so that the GPU receives a normal compressed texture, or in newer methods, decompressed by the GPU itself. Supercompression saves the same amount of VRAM as regular texture compression, but saves more disk space and download size. == Neural Texture Compression == Random-Access Neural Compression of Material Textures (Neural Texture Compression) is a Nvidia's technology which enables two additional levels of detail (16× more texels, so four times higher resolution) while maintaining similar storage requirements as traditional texture compression methods. The key idea is compressing multiple material textures and their mipmap chains together, and using a small neural network, that is optimized for each material, to decompress them.
Artificial intelligence in industry
Industrial artificial intelligence, or industrial AI, refers to the application of artificial intelligence to industrial business processes. Unlike general artificial intelligence which is a frontier research discipline to build computerized systems that perform tasks requiring human intelligence, industrial AI is more concerned with the application of such technologies to address industrial pain-points for customer value creation, productivity improvement, cost reduction, site optimization, predictive analysis and insight discovery. Artificial intelligence and machine learning have become key enablers to leverage data in production in recent years due to a number of different factors: More affordable sensors and the automated process of data acquisition; More powerful computation capability of computers to perform more complex tasks at a faster speed with lower cost; Faster connectivity infrastructure and more accessible cloud services for data management and computing power outsourcing. == Categories == Possible applications of industrial AI and machine learning in the production domain can be divided into seven application areas: Market and trend analysis Machinery and equipment Intralogistics Production process Supply chain Building Product Each application area can be further divided into specific application scenarios that describe concrete AI/ML scenarios in production. While some application areas have a direct connection to production processes, others cover production adjacent fields like logistics or the factory building. An example from the application scenario Process Design & Innovation are collaborative robots. Collaborative robotic arms are able to learn the motion and path demonstrated by human operators and perform the same task. Predictive and preventive maintenance through data-driven machine learning are application scenarios from the Machinery & Equipment application area. == Challenges == In contrast to entirely virtual systems, in which ML applications are already widespread today, real-world production processes are characterized by the interaction between the virtual and the physical world. Data is recorded using sensors and processed on computational entities and, if desired, actions and decisions are translated back into the physical world via actuators or by human operators. This poses major challenges for the application of ML in production engineering systems. These challenges are attributable to the encounter of process, data and model characteristics: The production domain's high reliability requirements, high risk and loss potential, the multitude of heterogeneous data sources and the non-transparency of ML model functionality impede a faster adoption of ML in real-world production processes. In particular, production data comprises a variety of different modalities, semantics and quality. Furthermore, production systems are dynamic, uncertain and complex, and engineering and manufacturing problems are data-rich but information-sparse. Besides that, due to the variety of use cases and data characteristics, problem-specific data sets are required, which are difficult to acquire, hindering both practitioners and academic researchers in this domain. === Process and industry characteristics === The domain of production engineering can be considered as a rather conservative industry when it comes to the adoption of advanced technology and their integration into existing processes. This is due to high demands on reliability of the production systems resulting from the potentially high economic harm of reduced process effectiveness due to e.g., additional unplanned downtime or insufficient product qualities. In addition, the specifics of machining equipment and products prevent area-wide adoptions across a variety of processes. Besides the technical reasons, the reluctant adoption of ML is fueled by a lack of IT and data science expertise across the domain. === Data characteristics === The data collected in production processes mainly stem from frequently sampling sensors to estimate the state of a product, a process, or the environment in the real world. Sensor readings are susceptible to noise and represent only an estimate of the reality under uncertainty. Production data typically comprises multiple distributed data sources resulting in various data modalities (e.g., images from visual quality control systems, time-series sensor readings, or cross-sectional job and product information). The inconsistencies in data acquisition lead to low signal-to-noise ratios, low data quality and great effort in data integration, cleaning and management. In addition, as a result from mechanical and chemical wear of production equipment, process data is subject to various forms of data drifts. === Machine learning model characteristics === ML models are considered as black-box systems given their complexity and intransparency of input-output relation. This reduces the comprehensibility of the system behavior and thus also the acceptance by plant operators. Due to the lack of transparency and the stochasticity of these models, no deterministic proof of functional correctness can be achieved, complicating the certification of production equipment. Given their inherent unrestricted prediction behavior, ML models are vulnerable against erroneous or manipulated data, further risking the reliability of the production system because of lacking robustness and safety. In addition to high development and deployment costs, the data drifts cause high maintenance costs, which is disadvantageous compared to purely deterministic programs. == Standard processes for data science in production == The development of ML applications – starting with the identification and selection of the use case and ending with the deployment and maintenance of the application – follows dedicated phases that can be organized in standard process models. The process models assist in structuring the development process and defining requirements that must be met in each phase to enter the next phase. The standard processes can be classified into generic and domain-specific ones. Generic standard processes (e.g., CRISP-DM, ASUM-DM, or knowledge discovery in databases (KDD)) describe a generally valid methodology and are thus independent of individual domains. Domain-specific processes on the other hand consider specific peculiarities and challenges of special application areas. The Machine Learning Pipeline in Production is a domain-specific data science methodology that is inspired by the CRISP-DM model and was specifically designed to be applied in fields of engineering and production technology. To address the core challenges of ML in engineering – process, data, and model characteristics – the methodology especially focuses on use-case assessment, achieving a common data and process understanding data integration, data preprocessing of real-world production data and the deployment and certification of real-world ML applications. == Industrial data sources == The foundation of most artificial intelligence and machine learning applications in industrial settings are comprehensive datasets from the respective fields. Those datasets act as the basis for training the employed models. In other domains, like computer vision, speech recognition or language models, extensive reference datasets (e.g. ImageNet, Librispeech, The People's Speech) and data scraped from the open internet are frequently used for this purpose. Such datasets rarely exist in the industrial context because of high confidentiality requirements and high specificity of the data. Industrial applications of artificial intelligence are therefore often faced with the problem of data availability. For these reasons, existing open datasets applicable to industrial applications, often originate from public institutions like governmental agencies or universities and data analysis competitions hosted by companies. In addition to this, data sharing platforms exist. However, most of these platforms have no industrial focus and offer limited filtering abilities regarding industrial data sources.
Knuth–Eve algorithm
In computer science, the Knuth–Eve algorithm is an algorithm for polynomial evaluation. It preprocesses the coefficients of the polynomial to reduce the number of multiplications required at runtime. Ideas used in the algorithm were originally proposed by Donald Knuth in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated. In 1964, James Eve determined for which polynomials this structure exists, and gave a simple method of "preconditioning" polynomials (explained below) to endow them with that structure. == Algorithm == === Preliminaries === Consider an arbitrary polynomial p ∈ R [ x ] {\displaystyle p\in \mathbb {R} [x]} of degree n {\displaystyle n} . Assume that n ≥ 3 {\displaystyle n\geq 3} . Define m {\displaystyle m} such that: if n {\displaystyle n} is odd then n = 2 m + 1 {\displaystyle n=2m+1} , and if n {\displaystyle n} is even then n = 2 m + 2 {\displaystyle n=2m+2} . Unless otherwise stated, all variables in this article represent either real numbers or univariate polynomials with real coefficients. All operations in this article are done over R {\displaystyle \mathbb {R} } . Again, the goal is to create an algorithm that returns p ( x ) {\displaystyle p(x)} given any x {\displaystyle x} . The algorithm is allowed to depend on the polynomial p {\displaystyle p} itself, since its coefficients are known in advance. === Overview === ==== Key idea ==== Using polynomial long division, we can write p ( x ) = q ( x ) ⋅ ( x 2 − α ) + ( β x + γ ) , {\displaystyle p(x)=q(x)\cdot (x^{2}-\alpha )+(\beta x+\gamma ),} where x 2 − α {\displaystyle x^{2}-\alpha } is the divisor. Picking a value for α {\displaystyle \alpha } fixes both the quotient q {\displaystyle q} and the coefficients in the remainder β {\displaystyle \beta } and γ {\displaystyle \gamma } . The key idea is to cleverly choose α {\displaystyle \alpha } such that β = 0 {\displaystyle \beta =0} , so that p ( x ) = q ( x ) ⋅ ( x 2 − α ) + γ . {\displaystyle p(x)=q(x)\cdot (x^{2}-\alpha )+\gamma .} This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure recursively to q {\displaystyle q} , expressing p ( x ) = ( ( q ( x ) ⋅ ( x 2 − α m ) + γ m ) ⋯ ) ⋅ ( x 2 − α 1 ) + γ 1 . {\displaystyle p(x)=\left(\left(q(x)\cdot (x^{2}-\alpha _{m})+\gamma _{m}\right)\cdots \right)\cdot (x^{2}-\alpha _{1})+\gamma _{1}.} After m {\displaystyle m} recursive calls, the quotient q {\displaystyle q} is either a linear or a quadratic polynomial. In this base case, the polynomial can be evaluated with (say) Horner's method. ==== "Preconditioning" ==== For arbitrary p {\displaystyle p} , it may not be possible to force β = 0 {\displaystyle \beta =0} at every step of the recursion. Consider the polynomials p e {\displaystyle p^{e}} and p o {\displaystyle p^{o}} with coefficients taken from the even and odd terms of p {\displaystyle p} respectively, so that p ( x ) = p e ( x 2 ) + x ⋅ p o ( x 2 ) . {\displaystyle p(x)=p^{e}(x^{2})+x\cdot p^{o}(x^{2}).} If every root of p o {\displaystyle p^{o}} is real, then it is possible to write p {\displaystyle p} in the form given above. Each α i {\displaystyle \alpha _{i}} is a different root of p o {\displaystyle p^{o}} , counting multiple roots as distinct. Furthermore, if at least n − 1 {\displaystyle n-1} roots of p {\displaystyle p} lie in one half of the complex plane, then every root of p o {\displaystyle p^{o}} is real. Ultimately, it may be necessary to "precondition" p {\displaystyle p} by shifting it — by setting p ( x ) ← p ( x + t ) {\displaystyle p(x)\gets p(x+t)} for some t {\displaystyle t} — to endow it with the structure that most of its roots lie in one half of the complex plane. At runtime, this shift has to be "undone" by first setting x ← x − t {\displaystyle x\gets x-t} . === Preprocessing step === The following algorithm is run once for a given polynomial p {\displaystyle p} . At this point, the values of x {\displaystyle x} that p {\displaystyle p} will be evaluated on are not known. ==== Better choice of t ==== While any t ≥ Re ( r 2 ) {\displaystyle t\geq {\text{Re}}(r_{2})} can work, it is possible to remove one addition during evaluation if t {\displaystyle t} is also chosen such that two roots of p ( x + t ) {\displaystyle p(x+t)} are symmetric about the origin. In that case, α 1 {\displaystyle \alpha _{1}} can be chosen such that the shifted polynomial has a factor of x 2 − α 1 {\displaystyle x^{2}-\alpha _{1}} , so γ 1 = 0 {\displaystyle \gamma _{1}=0} . It is always possible to find such a t {\displaystyle t} . One possible algorithm for choosing t {\displaystyle t} is: === Evaluation step === The following algorithm evaluates p {\displaystyle p} at some, now known, point x {\displaystyle x} . Assuming t {\displaystyle t} is chosen optimally, γ 1 = 0 {\displaystyle \gamma _{1}=0} . So, the final iteration of the loop can instead run y ← y ⋅ ( s − α i ) , {\displaystyle y\gets y\cdot (s-\alpha _{i}),} saving an addition. == Analysis == In total, evaluation using the Knuth–Eve algorithm for a polynomial of degree n {\displaystyle n} requires n {\displaystyle n} additions and ⌊ n / 2 ⌋ + 2 {\displaystyle \lfloor n/2\rfloor +2} multiplications, assuming t {\displaystyle t} is chosen optimally. No algorithm to evaluate a given polynomial of degree n {\displaystyle n} can use fewer than n {\displaystyle n} additions or fewer than ⌈ n / 2 ⌉ {\displaystyle \lceil n/2\rceil } multiplications during evaluation. This result assumes only addition and multiplication are allowed during both preprocessing and evaluation. The Knuth–Eve algorithm is not well-conditioned.
Gutmann method
The Gutmann method is an algorithm for securely erasing the contents of computer hard disk drives, such as files. Devised by Peter Gutmann and Colin Plumb and presented in the paper Secure Deletion of Data from Magnetic and Solid-State Memory in July 1996, it involved writing a series of 35 patterns over the region to be erased. The selection of patterns assumes that the user does not know the encoding mechanism used by the drive, so it includes patterns designed specifically for three types of drives. A user who knows which type of encoding the drive uses can choose only those patterns intended for their drive. A drive with a different encoding mechanism would need different patterns. Most of the patterns in the Gutmann method were designed for older MFM/RLL-encoded disks. Gutmann himself has noted that more modern drives no longer use these older encoding techniques, making parts of the method irrelevant. He said "In the time since this paper was published, some people have treated the 35-pass overwrite technique described in it more as a kind of voodoo incantation to banish evil spirits than the result of a technical analysis of drive encoding techniques". Since about 2001, some ATA IDE and SATA hard drive manufacturer designs include support for the ATA Secure Erase standard, obviating the need to apply the Gutmann method when erasing an entire drive. The Gutmann method does not apply to USB sticks: a 2011 study reports that 71.7% of data remained available. On solid state drives it resulted in 0.8–4.3% recovery. == Background == The delete function in most operating systems simply marks the space occupied by the file as reusable (removes the pointer to the file) without immediately removing any of its contents. At this point the file can be fairly easily recovered by numerous recovery applications. However, once the space is overwritten with other data, there is no known way to use software to recover it. It cannot be done with software alone since the storage device only returns its current contents via its normal interface. Gutmann claims that intelligence agencies have sophisticated tools, including magnetic force microscopes, which together with image analysis, can detect the previous values of bits on the affected area of the media (for example hard disk). This claim however seems to be invalid based on the thesis "Data Reconstruction from a Hard Disk Drive using Magnetic Force Microscopy". == Method == An overwrite session consists of a lead-in of four random write patterns, followed by patterns 5 to 31 (see rows of table below), executed in a random order, and a lead-out of four more random patterns. Each of patterns 5 to 31 was designed with a specific magnetic media encoding scheme in mind, which each pattern targets. The drive is written to for all the passes even though the table below only shows the bit patterns for the passes that are specifically targeted at each encoding scheme. The result should obscure any data on the drive so that only the most advanced physical scanning (e.g., using a magnetic force microscope) of the drive is likely to be able to recover any data. The series of patterns is as follows: Encoded bits shown in bold are what should be present in the ideal pattern, although due to the encoding the complementary bit is actually present at the start of the track. == Criticism == Daniel Feenberg of the National Bureau of Economic Research, an American private nonprofit research organization, criticized Gutmann's claim that intelligence agencies are likely to be able to read overwritten data, citing a lack of evidence for such claims. He finds that Gutmann cites one non-existent source and sources that do not actually demonstrate recovery, only partially-successful observations. The definition of "random" is also quite different from the usual one used: Gutmann expects the use of pseudorandom data with sequences known to the recovering side, not an unpredictable one such as a cryptographically secure pseudorandom number generator. Nevertheless, some published government security procedures consider an overwritten disk to still be sensitive. Human factors and potential limitations in the overwriting software create a residual risk that is not considered acceptable at the highest security levels. Gutmann himself has responded to some of these criticisms and also criticized how his algorithm has been abused in an epilogue to his original paper, in which he states: In the time since this paper was published, some people have treated the 35-pass overwrite technique described in it more as a kind of voodoo incantation to banish evil spirits than the result of a technical analysis of drive encoding techniques. As a result, they advocate applying the voodoo to PRML and EPRML drives even though it will have no more effect than a simple scrubbing with random data. In fact performing the full 35-pass overwrite is pointless for any drive since it targets a blend of scenarios involving all types of (normally-used) encoding technology, which covers everything back to 30+-year-old MFM methods (if you don't understand that statement, re-read the paper). If you're using a drive which uses encoding technology X, you only need to perform the passes specific to X, and you never need to perform all 35 passes. For any modern PRML/EPRML drive, a few passes of random scrubbing is the best you can do. As the paper says, "A good scrubbing with random data will do about as well as can be expected". This was true in 1996, and is still true now. Gutmann's statement has been criticized for not recognizing that PRML/EPRML does not replace RLL, with critics claiming PRML/EPRML to be a signal detection method rather than a data encoding method. Polish data recovery service Kaleron has also claimed that Gutmann's publication contains further factual errors and assumptions that do not apply to actual disks.
Weak supervision
Weak supervision (also known as semi-supervised learning) is a paradigm in machine learning, the relevance and notability of which increased with the advent of large language models due to the large amount of data required to train them. It is characterized by using a combination of a small amount of human-labeled data (exclusively used in more expensive and time-consuming supervised learning paradigm), followed by a large amount of unlabeled data (used exclusively in unsupervised learning paradigm). In other words, the desired output values are provided only for a subset of the training data. The remaining data is unlabeled or imprecisely labeled. Intuitively, it can be seen as an exam and labeled data as sample problems that the teacher solves for the class as an aid in solving another set of problems. In the transductive setting, these unsolved problems act as exam questions. In the inductive setting, they become practice problems of the sort that will make up the exam. == Problem == The acquisition of labeled data for a learning problem often requires a skilled human agent (e.g. to transcribe an audio segment) or a physical experiment (e.g. determining the 3D structure of a protein or determining whether there is oil at a particular location). The cost associated with the labeling process thus may render large, fully labeled training sets infeasible, whereas acquisition of unlabeled data is relatively inexpensive. In such situations, semi-supervised learning can be of great practical value. Semi-supervised learning is also of theoretical interest in machine learning and as a model for human learning. == Technique == More formally, semi-supervised learning assumes a set of l {\displaystyle l} independently identically distributed examples x 1 , … , x l ∈ X {\displaystyle x_{1},\dots ,x_{l}\in X} with corresponding labels y 1 , … , y l ∈ Y {\displaystyle y_{1},\dots ,y_{l}\in Y} and u {\displaystyle u} unlabeled examples x l + 1 , … , x l + u ∈ X {\displaystyle x_{l+1},\dots ,x_{l+u}\in X} are processed. Semi-supervised learning combines this information to surpass the classification performance that can be obtained either by discarding the unlabeled data and doing supervised learning or by discarding the labels and doing unsupervised learning. Semi-supervised learning may refer to either transductive learning or inductive learning. The goal of transductive learning is to infer the correct labels for the given unlabeled data x l + 1 , … , x l + u {\displaystyle x_{l+1},\dots ,x_{l+u}} only. The goal of inductive learning is to infer the correct mapping from X {\displaystyle X} to Y {\displaystyle Y} . It is unnecessary (and, according to Vapnik's principle, imprudent) to perform transductive learning by way of inferring a classification rule over the entire input space; however, in practice, algorithms formally designed for transduction or induction are often used interchangeably. == Assumptions == In order to make any use of unlabeled data, some relationship to the underlying distribution of data must exist. Semi-supervised learning algorithms make use of at least one of the following assumptions: === Continuity / smoothness assumption === Points that are close to each other are more likely to share a label. This is also generally assumed in supervised learning and yields a preference for geometrically simple decision boundaries. In the case of semi-supervised learning, the smoothness assumption additionally yields a preference for decision boundaries in low-density regions, so few points are close to each other but in different classes. === Cluster assumption === The data tend to form discrete clusters, and points in the same cluster are more likely to share a label (although data that shares a label may spread across multiple clusters). This is a special case of the smoothness assumption and gives rise to feature learning with clustering algorithms. === Manifold assumption === The data lie approximately on a manifold of much lower dimension than the input space. In this case learning the manifold using both the labeled and unlabeled data can avoid the curse of dimensionality. Then learning can proceed using distances and densities defined on the manifold. The manifold assumption is practical when high-dimensional data are generated by some process that may be hard to model directly, but which has only a few degrees of freedom. For instance, human voice is controlled by a few vocal folds, and images of various facial expressions are controlled by a few muscles. In these cases, it is better to consider distances and smoothness in the natural space of the generating problem, rather than in the space of all possible acoustic waves or images, respectively. == History == The heuristic approach of self-training (also known as self-learning or self-labeling) is historically the oldest approach to semi-supervised learning, with examples of applications starting in the 1960s. The transductive learning framework was formally introduced by Vladimir Vapnik in the 1970s. Interest in inductive learning using generative models also began in the 1970s. A probably approximately correct learning bound for semi-supervised learning of a Gaussian mixture was demonstrated by Ratsaby and Venkatesh in 1995. == Methods == === Generative models === Generative approaches to statistical learning first seek to estimate p ( x | y ) {\displaystyle p(x|y)} , the distribution of data points belonging to each class. The probability p ( y | x ) {\displaystyle p(y|x)} that a given point x {\displaystyle x} has label y {\displaystyle y} is then proportional to p ( x | y ) p ( y ) {\displaystyle p(x|y)p(y)} by Bayes' rule. Semi-supervised learning with generative models can be viewed either as an extension of supervised learning (classification plus information about p ( x ) {\displaystyle p(x)} ) or as an extension of unsupervised learning (clustering plus some labels). Generative models assume that the distributions take some particular form p ( x | y , θ ) {\displaystyle p(x|y,\theta )} parameterized by the vector θ {\displaystyle \theta } . If these assumptions are incorrect, the unlabeled data may actually decrease the accuracy of the solution relative to what would have been obtained from labeled data alone. However, if the assumptions are correct, then the unlabeled data necessarily improves performance. The unlabeled data are distributed according to a mixture of individual-class distributions. In order to learn the mixture distribution from the unlabeled data, it must be identifiable, that is, different parameters must yield different summed distributions. Gaussian mixture distributions are identifiable and commonly used for generative models. The parameterized joint distribution can be written as p ( x , y | θ ) = p ( y | θ ) p ( x | y , θ ) {\displaystyle p(x,y|\theta )=p(y|\theta )p(x|y,\theta )} by using the chain rule. Each parameter vector θ {\displaystyle \theta } is associated with a decision function f θ ( x ) = argmax y p ( y | x , θ ) {\displaystyle f_{\theta }(x)={\underset {y}{\operatorname {argmax} }}\ p(y|x,\theta )} . The parameter is then chosen based on fit to both the labeled and unlabeled data, weighted by λ {\displaystyle \lambda } : argmax Θ ( log p ( { x i , y i } i = 1 l | θ ) + λ log p ( { x i } i = l + 1 l + u | θ ) ) {\displaystyle {\underset {\Theta }{\operatorname {argmax} }}\left(\log p(\{x_{i},y_{i}\}_{i=1}^{l}|\theta )+\lambda \log p(\{x_{i}\}_{i=l+1}^{l+u}|\theta )\right)} === Low-density separation === Another major class of methods attempts to place boundaries in regions with few data points (labeled or unlabeled). One of the most commonly used algorithms is the transductive support vector machine, or TSVM (which, despite its name, may be used for inductive learning as well). Whereas support vector machines for supervised learning seek a decision boundary with maximal margin over the labeled data, the goal of TSVM is a labeling of the unlabeled data such that the decision boundary has maximal margin over all of the data. In addition to the standard hinge loss ( 1 − y f ( x ) ) + {\displaystyle (1-yf(x))_{+}} for labeled data, a loss function ( 1 − | f ( x ) | ) + {\displaystyle (1-|f(x)|)_{+}} is introduced over the unlabeled data by letting y = sign f ( x ) {\displaystyle y=\operatorname {sign} {f(x)}} . TSVM then selects f ∗ ( x ) = h ∗ ( x ) + b {\displaystyle f^{}(x)=h^{}(x)+b} from a reproducing kernel Hilbert space H {\displaystyle {\mathcal {H}}} by minimizing the regularized empirical risk: f ∗ = argmin f ( ∑ i = 1 l ( 1 − y i f ( x i ) ) + + λ 1 ‖ h ‖ H 2 + λ 2 ∑ i = l + 1 l + u ( 1 − | f ( x i ) | ) + ) {\displaystyle f^{}={\underset {f}{\operatorname {argmin} }}\left(\displaystyle \sum _{i=1}^{l}(1-y_{i}f(x_{i}))_{+}+\lambda _{1}\|h\|_{\mathcal {H}}^{2}+\lambda _{2}\sum _{i=l+1}^{l+u}(1-|f(x_{i})|)_{+}\right)} An exact solution is intractable due to the non-convex term ( 1 − | f ( x ) | ) + {\displayst
Kullback–Leibler Upper Confidence Bound
In multi-armed bandit problems, KL-UCB (for Kullback–Leibler Upper Confidence Bound) is a UCB-type algorithm that is asymptotically optimal, in the sense that its regret matches the problem-dependent Lai-Robbins lower bound. == Multi-armed bandit problem == The Multi-armed bandit problem is a sequential game where one player has to choose at each turn between K {\displaystyle K} actions (arms). Behind every arm a {\displaystyle a} there is an unknown distribution ν a {\displaystyle \nu _{a}} that lies in a set D {\displaystyle {\mathcal {D}}} known by the player (for example, D {\displaystyle {\mathcal {D}}} can be the set of Gaussian distributions or Bernoulli distributions). At each turn t {\displaystyle t} the player chooses (pulls) an arm a t {\displaystyle a_{t}} , he then gets an observation X t {\displaystyle X_{t}} of the distribution ν a t {\displaystyle \nu _{a_{t}}} . === Regret minimization === The goal is to minimize the regret at time T {\displaystyle T} that is defined as R T := ∑ a = 1 K Δ a E [ N a ( T ) ] {\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\mathbb {E} [N_{a}(T)]} where μ a := E [ ν a ] {\displaystyle \mu _{a}:=\mathbb {E} [\nu _{a}]} is the mean of arm a {\displaystyle a} μ ∗ := max a μ a {\displaystyle \mu ^{}:=\max _{a}\mu _{a}} is the highest mean Δ a := μ ∗ − μ a {\displaystyle \Delta _{a}:=\mu ^{}-\mu _{a}} N a ( t ) {\displaystyle N_{a}(t)} is the number of pulls of arm a {\displaystyle a} up to turn t {\displaystyle t} The player has to find an algorithm that chooses at each turn t {\displaystyle t} which arm to pull based on the previous actions and observations ( a s , X s ) s < t {\displaystyle (a_{s},X_{s})_{s