In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound. Like the ancient sieve of Eratosthenes, it has a simple conceptual basis in number theory. It is especially suited to quick hand computation for small bounds. Whereas the sieve of Eratosthenes marks off each non-prime for each of its prime factors, the sieve of Pritchard avoids considering almost all non-prime numbers by building progressively larger wheels, which represent the pattern of numbers not divisible by any of the primes processed thus far. It thereby achieves a better asymptotic complexity, and was the first sieve with a running time sublinear in the specified bound. Its asymptotic running-time has not been improved on, and it deletes fewer composites than any other known sieve. It was created in 1979 by Paul Pritchard. Since Pritchard has created a number of other sieve algorithms for finding prime numbers, the sieve of Pritchard is sometimes singled out by being called the wheel sieve (by Pritchard himself) or the dynamic wheel sieve. == Overview == A prime number is a natural number that has no natural number divisors other than the number 1 and itself. To find all the prime numbers less than or equal to a given integer N, a sieve algorithm examines a set of candidates in the range 2, 3, …, N, and eliminates those that are not prime, leaving the primes at the end. The sieve of Eratosthenes examines all of the range, first removing all multiples of the first prime 2, then of the next prime 3, and so on. The sieve of Pritchard instead examines a subset of the range consisting of numbers that occur on successive wheels, which represent the pattern of numbers left after each successive prime is processed by the sieve of Eratosthenes. For i > 0, the ith wheel Wi represents this pattern. It is the set of numbers between 1 and the product Pi = p1 · p2 ⋯ pi of the first i prime numbers that are not divisible by any of these prime numbers (and is said to have an associated length Pi). This is because adding Pi to a number does not change whether it is divisible by one of the first i prime numbers, since the remainder on division by any one of these primes is unchanged. So W1 = {1} with length P1 = 2 represents the pattern of odd numbers; W2 = {1,5} with length P2 = 6 represents the pattern of numbers not divisible by 2 or 3; etc. Wheels are so-called because Wi can be usefully visualized as a circle of circumference Pi with its members marked at their corresponding distances from an origin. Then rolling the wheel along the number line marks points corresponding to successive numbers not divisible by one of the first i prime numbers. The animation shows W2 being rolled up to 30. It is useful to define Wi → n for n > 0 to be the result of rolling Wi up to n. Then the animation generates W2 → 30 = {1,5,7,11,13,17,19,23,25,29}. Note that up to 52 − 1 = 24, this consists only of 1 and the primes between 5 and 25. The sieve of Pritchard is derived from the observation that this holds generally: for all i > 0, the values in Wi → (p2i+1 − 1) are 1 and the primes between pi+1 and p2i+1. It even holds for i = 0, where the wheel has length 1 and contains just 1 (representing all the natural numbers). So the sieve of Pritchard starts with the trivial wheel W0 and builds successive wheels until the square of the wheel's first member after 1 is at least N. Wheels grow very quickly, but only their values up to N are needed and generated. It remains to find a method for generating the next wheel. Note in the animation that W3 = {1,5,7,11,13,17,19,23,25,29} − {5 · 1 , 5 · 5} can be obtained by rolling W2 up to 30 and then removing 5 times each member of W2.This also holds generally: for all i ≥ 0, Wi+1 = (Wi → Pi+1) − {pi+1 · w | w ∈ Wi}. Rolling Wi past Pi just adds values to Wi, so the current wheel is first extended by getting each successive member starting with w = 1, adding Pi to it, and inserting the result in the set. Then the multiples of pi+1 are deleted. Care must be taken to avoid a number being deleted that itself needs to be multiplied by pi+1. The sieve of Pritchard as originally presented does so by first skipping past successive members until finding the maximum one needed, and then doing the deletions in reverse order by working back through the set. This is the method used in the first animation above. A simpler approach is just to gather the multiples of pi+1 in a list, and then delete them. Another approach is given by Gries and Misra. If the main loop terminates with a wheel whose length is less than N, it is extended up to N to generate the remaining primes. The algorithm, for finding all primes up to N, is therefore as follows: Start with a set W = {1} and length = 1 representing wheel 0, and prime p = 2. As long as p2 ≤ N, do the following: if length < N, then extend W by repeatedly getting successive members w of W starting with 1 and inserting length + w into W as long as it does not exceed p · length or N; increase length to the minimum of p · length and N. repeatedly delete p times each member of W by first finding the largest ≤ length and then working backwards. note the prime p, then set p to the next member of W after 1 (or 3 if p was 2). if length < N, then extend W to N by repeatedly getting successive members w of W starting with 1 and inserting length + w into W as long as it does not exceed N; On termination, the rest of the primes up to N are the members of W after 1. === Example === To find all the prime numbers less than or equal to 150, proceed as follows. Start with wheel 0 with length 1, representing all natural numbers 1, 2, 3...: 1 The first number after 1 for wheel 0 (when rolled) is 2; note it as a prime. Now form wheel 1 with length 2 × 1 = 2 by first extending wheel 0 up to 2 and then deleting 2 times each number in wheel 0, to get: 1 2 The first number after 1 for wheel 1 (when rolled) is 3; note it as a prime. Now form wheel 2 with length 3 × 2 = 6 by first extending wheel 1 up to 6 and then deleting 3 times each number in wheel 1, to get 1 2 3 5 The first number after 1 for wheel 2 is 5; note it as a prime. Now form wheel 3 with length 5 × 6 = 30 by first extending wheel 2 up to 30 and then deleting 5 times each number in wheel 2 (in reverse order), to get 1 2 3 5 7 11 13 17 19 23 25 29 The first number after 1 for wheel 3 is 7; note it as a prime. Now wheel 4 has length 7 × 30 = 210, so we only extend wheel 3 up to our limit 150. (No further extending will be done now that the limit has been reached.) We then delete 7 times each number in wheel 3 until we exceed our limit 150, to get the elements in wheel 4 up to 150: 1 2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 The first number after 1 for this partial wheel 4 is 11; note it as a prime. Since we have finished with rolling, we delete 11 times each number in the partial wheel 4 until we exceed our limit 150, to get the elements in wheel 5 up to 150: 1 2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 The first number after 1 for this partial wheel 5 is 13. Since 13 squared is at least our limit 150, we stop. The remaining numbers (other than 1) are the rest of the primes up to our limit 150. Just 8 composite numbers are removed, once each. The rest of the numbers considered (other than 1) are prime. In comparison, the natural version of Eratosthenes sieve (stopping at the same point) removes composite numbers 184 times. == Pseudocode == The sieve of Pritchard can be expressed in pseudocode, as follows: algorithm Sieve of Pritchard is input: an integer N >= 2. output: the set of prime numbers in {1,2,...,N}. let W and Pr be sets of integer values, and all other variables integer values. k, W, length, p, Pr := 1, {1}, 2, 3, {2}; {invariant: p = pk+1 and W = Wk ∩ {\displaystyle \cap } {1,2,...,N} and length = minimum of Pk,N and Pr = the primes up to pk} while p2 <= N do if (length < N) then Extend W,length to minimum of plength,N; Delete multiples of p from W; Insert p into Pr; k, p := k+1, next(W, 1) if (length < N) then Extend W,length to N; return Pr ∪ {\displaystyle \cup } W - {1}; where next(W, w) is the next value in the ordered set W after w. procedure Extend W,length to n is {in: W = Wk and length = Pk and n > length} {out: W = Wk → {\displaystyle \rightarrow } n and length = n} integer w, x; w, x := 1, length+1; while x <= n do Insert x into W; w := next(W,w); x := length + w; length := n; procedure Delete multiples of p from W,length is integer w; w := p; while pw <= length do w := next(W,w); while w > 1 do w := prev(W,w); Remove pw from W; where prev(W, w) is the previous value in the ordered set W before w. The algorithm can be initialized with W0 instead of W1 at the minor complication of making next(W, 1) a special case when k = 0. This a
AI-complete
In the field of artificial intelligence (AI), tasks that are hypothesized to require artificial general intelligence to solve are informally known as AI-complete or AI-hard. Calling a problem AI-complete reflects the belief that it cannot be solved by a simple specific algorithm. Prior to 2013, problems supposed to be AI-complete included computer vision, natural language understanding, and dealing with unexpected circumstances while solving any real-world problem. AI-complete tasks were notably considered useful for distinguishing humans from automated agents, as CAPTCHAs aim to do. == History == The term was coined by Fanya Montalvo by analogy with NP-complete and NP-hard in complexity theory, which formally describes the most famous class of difficult problems. Early uses of the term are in Erik Mueller's 1987 PhD dissertation and in Eric Raymond's 1991 Jargon File. Expert systems, that were popular in the 1980s, were able to solve very simple and/or restricted versions of AI-complete problems, but never in their full generality. When AI researchers attempted to "scale up" their systems to handle more complicated, real-world situations, the programs tended to become excessively brittle without commonsense knowledge or a rudimentary understanding of the situation: they would fail as unexpected circumstances outside of its original problem context would begin to appear. When human beings are dealing with new situations in the world, they are helped by their awareness of the general context: they know what the things around them are, why they are there, what they are likely to do and so on. They can recognize unusual situations and adjust accordingly. Expert systems lacked this adaptability and were brittle when facing new situations. DeepMind published a work in May 2022 in which they trained a single model to do several things at the same time. The model, named Gato, can "play Atari, caption images, chat, stack blocks with a real robot arm and much more, deciding based on its context whether to output text, joint torques, button presses, or other tokens." Similarly, some tasks once considered to be AI-complete, like machine translation, are among the capabilities of large language models. == AI-complete problems == AI-complete problems have been hypothesized to include: AI peer review (composite natural language understanding, automated reasoning, automated theorem proving, formalized logic expert system) Bongard problems Computer vision (and subproblems such as object recognition) Natural language understanding (and subproblems such as text mining, machine translation, and word-sense disambiguation) Autonomous driving Dealing with unexpected circumstances while solving any real world problem, whether navigation, planning, or even the kind of reasoning done by expert systems. == Formalization == Computational complexity theory deals with the relative computational difficulty of computable functions. By definition, it does not cover problems whose solution is unknown or has not been characterized formally. Since many AI problems have no formalization yet, conventional complexity theory does not enable a formal definition of AI-completeness. == Research == Roman Yampolskiy suggests that a problem C {\displaystyle C} is AI-Complete if it has two properties: It is in the set of AI problems (Human Oracle-solvable). Any AI problem can be converted into C {\displaystyle C} by some polynomial time algorithm. On the other hand, a problem H {\displaystyle H} is AI-Hard if and only if there is an AI-Complete problem C {\displaystyle C} that is polynomial time Turing-reducible to H {\displaystyle H} . This also gives as a consequence the existence of AI-Easy problems, that are solvable in polynomial time by a deterministic Turing machine with an oracle for some problem. Yampolskiy has also hypothesized that the Turing Test is a defining feature of AI-completeness. Groppe and Jain classify problems which require artificial general intelligence to reach human-level machine performance as AI-complete, while only restricted versions of AI-complete problems can be solved by the current AI systems. For Šekrst, getting a polynomial solution to AI-complete problems would not necessarily be equal to solving the issue of artificial general intelligence, while emphasizing the lack of computational complexity research being the limiting factor towards achieving artificial general intelligence. For Kwee-Bintoro and Velez, solving AI-complete problems would have strong repercussions on society.
Developmental robotics
Developmental robotics (DevRob), sometimes called epigenetic robotics, is a scientific field which aims at studying the developmental mechanisms, architectures and constraints that allow lifelong and open-ended learning of new skills and new knowledge in embodied machines. As in human children, learning is expected to be cumulative and of progressively increasing complexity, and to result from self-exploration of the world in combination with social interaction. The typical methodological approach consists in starting from theories of human and animal development elaborated in fields such as developmental psychology, neuroscience, developmental and evolutionary biology, and linguistics, then to formalize and implement them in robots, sometimes exploring extensions or variants of them. The experimentation of those models in robots allows researchers to confront them with reality, and as a consequence, developmental robotics also provides feedback and novel hypotheses on theories of human and animal development. Developmental robotics is related to but differs from evolutionary robotics (ER). ER uses populations of robots that evolve over time, whereas DevRob is interested in how the organization of a single robot's control system develops through experience, over time. DevRob is also related to work done in the domains of robotics and artificial life. == Background == Can a robot learn like a child? Can it learn a variety of new skills and new knowledge unspecified at design time and in a partially unknown and changing environment? How can it discover its body and its relationships with the physical and social environment? How can its cognitive capacities continuously develop without the intervention of an engineer once it is "out of the factory"? What can it learn through natural social interactions with humans? These are the questions at the center of developmental robotics. Alan Turing, as well as a number of other pioneers of cybernetics, already formulated those questions and the general approach in 1950, but it is only since the end of the 20th century that they began to be investigated systematically. Because the concept of adaptive intelligent machines is central to developmental robotics, it has relationships with fields such as artificial intelligence, machine learning, cognitive robotics or computational neuroscience. Yet, while it may reuse some of the techniques elaborated in these fields, it differs from them from many perspectives. It differs from classical artificial intelligence because it does not assume the capability of advanced symbolic reasoning and focuses on embodied and situated sensorimotor and social skills rather than on abstract symbolic problems. It differs from cognitive robotics because it focuses on the processes that allow the formation of cognitive capabilities rather than these capabilities themselves. It differs from computational neuroscience because it focuses on functional modeling of integrated architectures of development and learning. More generally, developmental robotics is uniquely characterized by the following three features: It targets task-independent architectures and learning mechanisms, i.e. the machine/robot has to be able to learn new tasks that are unknown by the engineer; It emphasizes open-ended development and lifelong learning, i.e. the capacity of an organism to acquire continuously novel skills. This should not be understood as a capacity for learning "anything" or even “everything”, but just that the set of skills that is acquired can be infinitely extended at least in some (not all) directions; The complexity of acquired knowledge and skills shall increase (and the increase be controlled) progressively. Developmental robotics emerged at the crossroads of several research communities including embodied artificial intelligence, enactive and dynamical systems cognitive science, connectionism. Starting from the essential idea that learning and development happen as the self-organized result of the dynamical interactions among brains, bodies and their physical and social environment, and trying to understand how this self-organization can be harnessed to provide task-independent lifelong learning of skills of increasing complexity, developmental robotics strongly interacts with fields such as developmental psychology, developmental and cognitive neuroscience, developmental biology (embryology), evolutionary biology, and cognitive linguistics. As many of the theories coming from these sciences are verbal and/or descriptive, this implies a crucial formalization and computational modeling activity in developmental robotics. These computational models are then not only used as ways to explore how to build more versatile and adaptive machines but also as a way to evaluate their coherence and possibly explore alternative explanations for understanding biological development. == Research directions == === Skill domains === Due to the general approach and methodology, developmental robotics projects typically focus on having robots develop the same types of skills as human infants. A first category that is important being investigated is the acquisition of sensorimotor skills. These include the discovery of one's own body, including its structure and dynamics such as hand-eye coordination, locomotion, and interaction with objects as well as tool use, with a particular focus on the discovery and learning of affordances. A second category of skills targeted by developmental robots are social and linguistic skills: the acquisition of simple social behavioural games such as turn-taking, coordinated interaction, lexicons, syntax and grammar, and the grounding of these linguistic skills into sensorimotor skills (sometimes referred as symbol grounding). In parallel, the acquisition of associated cognitive skills are being investigated such as the emergence of the self/non-self distinction, the development of attentional capabilities, of categorization systems and higher-level representations of affordances or social constructs, of the emergence of values, empathy, or theories of mind. === Mechanisms and constraints === The sensorimotor and social spaces in which humans and robot live are so large and complex that only a small part of potentially learnable skills can actually be explored and learnt within a life-time. Thus, mechanisms and constraints are necessary to guide developmental organisms in their development and control of the growth of complexity. There are several important families of these guiding mechanisms and constraints which are studied in developmental robotics, all inspired by human development: Motivational systems, generating internal reward signals that drive exploration and learning, which can be of two main types: extrinsic motivations push robots/organisms to maintain basic specific internal properties such as food and water level, physical integrity, or light (e.g. in phototropic systems); intrinsic motivations push robot to search for novelty, challenge, compression or learning progress per se, thus generating what is sometimes called curiosity-driven learning and exploration, or alternatively active learning and exploration; Social guidance: as humans learn a lot by interacting with their peers, developmental robotics investigates mechanisms that can allow robots to participate to human-like social interaction. By perceiving and interpreting social cues, this may allow robots both to learn from humans (through diverse means such as imitation, emulation, stimulus enhancement, demonstration, etc. ...) and to trigger natural human pedagogy. Thus, social acceptance of developmental robots is also investigated; Statistical inference biases and cumulative knowledge/skill reuse: biases characterizing both representations/encodings and inference mechanisms can typically allow considerable improvement of the efficiency of learning and are thus studied. Related to this, mechanisms allowing to infer new knowledge and acquire new skills by reusing previously learnt structures is also an essential field of study; The properties of embodiment, including geometry, materials, or innate motor primitives/synergies often encoded as dynamical systems, can considerably simplify the acquisition of sensorimotor or social skills, and is sometimes referred as morphological computation. The interaction of these constraints with other constraints is an important axis of investigation; Maturational constraints: In human infants, both the body and the neural system grow progressively, rather than being full-fledged already at birth. This implies, for example, that new degrees of freedom, as well as increases of the volume and resolution of available sensorimotor signals, may appear as learning and development unfold. Transposing these mechanisms in developmental robots, and understanding how it may hinder or on the contrary ease the acquisition of novel complex skills is a central questi
Mountain car problem
Mountain Car, a standard testing domain in Reinforcement learning, is a problem in which an under-powered car must drive up a steep hill. Since gravity is stronger than the car's engine, even at full throttle, the car cannot simply accelerate up the steep slope. The car is situated in a valley and must learn to leverage potential energy by driving up the opposite hill before the car is able to make it to the goal at the top of the rightmost hill. The domain has been used as a test bed in various reinforcement learning papers. == Introduction == The mountain car problem, although fairly simple, is commonly applied because it requires a reinforcement learning agent to learn on two continuous variables: position and velocity. For any given state (position and velocity) of the car, the agent is given the possibility of driving left, driving right, or not using the engine at all. In the standard version of the problem, the agent receives a negative reward at every time step when the goal is not reached; the agent has no information about the goal until an initial success. == History == The mountain car problem appeared first in Andrew Moore's PhD thesis (1990). It was later more strictly defined in Singh and Sutton's reinforcement learning paper with eligibility traces. The problem became more widely studied when Sutton and Barto added it to their book Reinforcement Learning: An Introduction (1998). Throughout the years many versions of the problem have been used, such as those which modify the reward function, termination condition, and the start state. == Techniques used to solve mountain car == Q-learning and similar techniques for mapping discrete states to discrete actions need to be extended to be able to deal with the continuous state space of the problem. Approaches often fall into one of two categories, state space discretization or function approximation. === Discretization === In this approach, two continuous state variables are pushed into discrete states by bucketing each continuous variable into multiple discrete states. This approach works with properly tuned parameters but a disadvantage is information gathered from one state is not used to evaluate another state. Tile coding can be used to improve discretization and involves continuous variables mapping into sets of buckets offset from one another. Each step of training has a wider impact on the value function approximation because when the offset grids are summed, the information is diffused. === Function approximation === Function approximation is another way to solve the mountain car. By choosing a set of basis functions beforehand, or by generating them as the car drives, the agent can approximate the value function at each state. Unlike the step-wise version of the value function created with discretization, function approximation can more cleanly estimate the true smooth function of the mountain car domain. === Eligibility traces === One aspect of the problem involves the delay of actual reward. The agent is not able to learn about the goal until a successful completion. Given a naive approach for each trial the car can only backup the reward of the goal slightly. This is a problem for naive discretization because each discrete state will only be backed up once, taking a larger number of episodes to learn the problem. This problem can be alleviated via the mechanism of eligibility traces, which will automatically backup the reward given to states before, dramatically increasing the speed of learning. Eligibility traces can be viewed as a bridge from temporal difference learning methods to Monte Carlo methods. == Technical details == The mountain car problem has undergone many iterations. This section focuses on the standard well-defined version from Sutton (2008). === State variables === Two-dimensional continuous state space. V e l o c i t y = ( − 0.07 , 0.07 ) {\displaystyle Velocity=(-0.07,0.07)} P o s i t i o n = ( − 1.2 , 0.6 ) {\displaystyle Position=(-1.2,0.6)} === Actions === One-dimensional discrete action space. m o t o r = ( l e f t , n e u t r a l , r i g h t ) {\displaystyle motor=(left,neutral,right)} === Reward === For every time step: r e w a r d = − 1 {\displaystyle reward=-1} === Update function === For every time step: A c t i o n = [ − 1 , 0 , 1 ] {\displaystyle Action=[-1,0,1]} V e l o c i t y = V e l o c i t y + ( A c t i o n ) ∗ 0.001 + cos ( 3 ∗ P o s i t i o n ) ∗ ( − 0.0025 ) {\displaystyle Velocity=Velocity+(Action)0.001+\cos(3Position)(-0.0025)} P o s i t i o n = P o s i t i o n + V e l o c i t y {\displaystyle Position=Position+Velocity} === Starting condition === Optionally, many implementations include randomness in both parameters to show better generalized learning. P o s i t i o n = − 0.5 {\displaystyle Position=-0.5} V e l o c i t y = 0.0 {\displaystyle Velocity=0.0} === Termination condition === End the simulation when: P o s i t i o n ≥ 0.6 {\displaystyle Position\geq 0.6} == Variations == There are many versions of the mountain car which deviate in different ways from the standard model. Variables that vary include but are not limited to changing the constants (gravity and steepness) of the problem so specific tuning for specific policies become irrelevant and altering the reward function to affect the agent's ability to learn in a different manner. An example is changing the reward to be equal to the distance from the goal, or changing the reward to zero everywhere and one at the goal. Additionally, a 3D mountain car can be used, with a 4D continuous state space.
Automated medical scribe
Automated medical scribes (also called artificial intelligence scribes, AI scribes, digital scribes, virtual scribes, ambient AI scribes, AI documentation assistants, and digital/virtual/smart clinical assistants) are tools for transcribing medical speech, such as patient consultations and dictated medical notes. Many also produce summaries of consultations. Automated medical scribes based on large language models (LLMs, commonly called "AI", short for "artificial intelligence") increased drastically in popularity in 2024. There are privacy and antitrust concerns. Accuracy concerns also exist, and intensify in situations in which tools try to go beyond transcribing and summarizing, and are asked to format information by its meaning, since LLMs do not deal well with meaning (see weak artificial intelligence). Medics using these scribes are generally expected to understand the ethical and legal considerations, and supervise the outputs. The privacy protections of automated medical scribes vary widely. While it is possible to do all the transcription and summarizing locally, with no connection to the internet, most closed-source providers require that data be sent to their own servers over the internet, processed there, and the results sent back (as with digital voice assistants). Some retailers say their tools use zero-knowledge encryption (meaning that the service provider can't access the data). Others explicitly say that they use patient data to train their AIs, or rent or resell it to third parties; the nature of privacy protections used in such situations is unclear, and they are likely not to be fully effective. Most providers have not published any safety or utility data in academic journals, and are not responsive to requests from medical researchers studying their products. == Privacy == Some providers unclear about what happens to user data. Some may sell data to third parties. Some explicitly send user data to for-profit tech companies for secondary purposes, which may not be specified. Some require users to sign consents to such reuse of their data. Some ingest user data to train the software, promising to anonymize it; however, deanonymization may be possible (that is, it may become obvious who the patient is). It is intrinsically impossible to prevent an LLM from correlating its inputs; they work by finding similar patterns across very large data sets. Some information on the patient will be known from other sources (for instance, information that they were injured in an incident on a certain day might be available from the news media; information that they attended specific appointment locations at specific times is probably available to their cellphone provider/apps/data brokers; information about when they had a baby is probably implied by their online shopping records; and they might mention lifestyle changes to their doctor and on a forum or blog). The software may correlate such information with the "anonymized" clinical consultation record, and, asked about the named patient, provide information which they only told their doctor privately. Because a patient's record is all about the same patient, it is all unavoidably linked; in very many cases, medical histories are intrinsically identifiable. Depending on how common a condition and what other data is available, K-anonymity may be useless. Differential privacy could theoretically preserve privacy. Data broker companies like Google, Amazon, Apple and Microsoft have produced or bought up medical scribes, some of which use user data for secondary purposes, which has led to antitrust concerns. Transfer of patient records for AI training has, in the past, prompted legal action. Open-source programs typically do all the transcription locally, on the doctor's own computer. Open-source software is widely used in healthcare, with some national public healthcare bodies holding hack days. === Data resale and commercialization === Several AI medical scribe providers include terms in their service agreements that allow the reuse, sale, or commercialization of de-identified or user-submitted data. Although such data are generally described as anonymized or aggregated, these practices have raised ethical concerns among clinicians and privacy advocates regarding secondary uses of medical information beyond clinical documentation. Freed, an AI transcription and scribe platform, states in its Terms of Use that it may "collect, use, publish, disseminate, sell, transfer, and otherwise exploit" de-identified and aggregated data derived from user inputs. OpenEvidence similarly states that it may "collect, use, transfer, sell, and disclose non-personal information and customer usage data for any purpose including commercial uses." Doximity, which offers an AI-enabled medical scribe as part of its physician platform, grants itself a "nonexclusive, irrevocable, worldwide, perpetual, unlimited, assignable, sublicensable, royalty-free" license to "copy, prepare derivative works from, improve, distribute, publish, ... analyze, index, tag, [and] commercialize" content submitted by users, subject to its privacy policy. Because these terms allow broad secondary use—including sale, licensing, model-training, derivative works, and commercial exploitation of de-identified or user-submitted data—some commentators have recommended that clinicians review data-handling provisions carefully when adopting AI-scribe tools, particularly in clinical environments where patient privacy and regulatory compliance are critical. === Encryption === Multifactor authentication for access to the data is expected practice. Typically, Diffie–Hellman key exchange is used for encryption; this is the standard method commonly used for things like online banking. This encryption is expensive but not impossible to break; it is not generally considered safe against eavesdroppers with the resources of a nation-state. If content is encrypted between the client and the service provider's remote server (transport cryptography), then the server has an unencrypted copy. This is necessary if the data is used by the service provider (for instance, to train the software). Zero-knowledge encryption implies that the only unencrypted copy is at the client, and the server cannot decrypt the data any more easily than a monster-in-the-middle attacker. == Platforms == Scribes may operate on desktops, laptop, or mobile computers, under a variety of operating systems. These vary in their risks; for instance, mobiles can be lost. The underlying mobile or desktop operating systems are also part of the trusted computing base, and if they are not secure, the software relying on them cannot be secure either. Some AI medical scribe platforms are designed to operate as cloud-based applications that generate structured clinical documentation from clinician–patient conversations. These systems may offer features such as real-time transcription, document generation, and integration with electronic health record (EHR) systems. == Confabulation, omissions, and other errors == Like other LLMs, medical-scribe LLMs are prone to hallucinations, where they make up content based on statistically associations between their training data and the transcription audio. LLMs do not distinguish between trying to transcribe the audio and guessing what words will come next, but perform both processes mixed together. They are especially likely to take short silences or non-speech noises and invent some sort of speech to transcribe them as. LLM medical scribes have been known to confabulate racist and otherwise prejudiced content; this is partly because the training datasets of many LLMs contain pseudoscientific texts about medical racism. They may misgender patients. A survey found that most doctors preferred, in principle, that scribes be trained on data reviewed by medical subject experts. Relevant, accurate training data increases the probability of an accurate transcription, but does not guarantee accuracy. Software trained on thousands of real clinical conversations generated transcripts with lower word error rates. Software trained on manually-transcribed training data did better than software trained with automatically transcribed training data such as YouTube captions. Autoscribes omit parts of the conversation classes as irrelevant. The may wrongly classify pertinent information as irrelevant and omit it. They may also confuse historic and current symptoms, or otherwise misclassify information. They may also simply wrongly transcribe the speech, writing something incorrect instead. If clinicians do not carefully check the recording, such mistakes could make their way into their medical records and cause patient harms. == Patient consent == Professional organizations generally require that scribes be used only with patient consent; some bodies may require written consent. Medics must also abide by local surveillance laws, which may criminalize recording pri
Pyramid (image processing)
Pyramid, or pyramid representation, is a type of multi-scale signal representation developed by the computer vision, image processing and signal processing communities, in which a signal or an image is subject to repeated smoothing and subsampling. Pyramid representation is a predecessor to scale-space representation and multiresolution analysis. == Pyramid generation == There are two main types of pyramids: lowpass and bandpass. A lowpass pyramid is made by smoothing the image with an appropriate smoothing filter and then subsampling the smoothed image, usually by a factor of 2 along each coordinate direction. The resulting image is then subjected to the same procedure, and the cycle is repeated multiple times. Each cycle of this process results in a smaller image with increased smoothing, but with decreased spatial sampling density (that is, decreased image resolution). If illustrated graphically, the entire multi-scale representation will look like a pyramid, with the original image on the bottom and each cycle's resulting smaller image stacked one atop the other. A bandpass pyramid is made by forming the difference between images at adjacent levels in the pyramid and performing image interpolation between adjacent levels of resolution, to enable computation of pixelwise differences. == Pyramid generation kernels == A variety of different smoothing kernels have been proposed for generating pyramids. Among the suggestions that have been given, the binomial kernels arising from the binomial coefficients stand out as a particularly useful and theoretically well-founded class. Thus, given a two-dimensional image, we may apply the (normalized) binomial filter (1/4, 1/2, 1/4) typically twice or more along each spatial dimension and then subsample the image by a factor of two. This operation may then proceed as many times as desired, leading to a compact and efficient multi-scale representation. If motivated by specific requirements, intermediate scale levels may also be generated where the subsampling stage is sometimes left out, leading to an oversampled or hybrid pyramid. With the increasing computational efficiency of CPUs available today, it is in some situations also feasible to use wider supported Gaussian filters as smoothing kernels in the pyramid generation steps. === Gaussian pyramid === In a Gaussian pyramid, subsequent images are weighted down using a Gaussian average (Gaussian blur) and scaled down. Each pixel containing a local average corresponds to a neighborhood pixel on a lower level of the pyramid. This technique is used especially in texture synthesis. === Laplacian pyramid === A Laplacian pyramid is very similar to a Gaussian pyramid but saves the difference image of the blurred versions between each levels. Only the smallest level is not a difference image to enable reconstruction of the high resolution image using the difference images on higher levels. This technique can be used in image compression. === Steerable pyramid === A steerable pyramid, developed by Simoncelli and others, is an implementation of a multi-scale, multi-orientation band-pass filter bank used for applications including image compression, texture synthesis, and object recognition. It can be thought of as an orientation selective version of a Laplacian pyramid, in which a bank of steerable filters are used at each level of the pyramid instead of a single Laplacian or Gaussian filter. == Applications of pyramids == === Alternative representation === In the early days of computer vision, pyramids were used as the main type of multi-scale representation for computing multi-scale image features from real-world image data. More recent techniques include scale-space representation, which has been popular among some researchers due to its theoretical foundation, the ability to decouple the subsampling stage from the multi-scale representation, the more powerful tools for theoretical analysis as well as the ability to compute a representation at any desired scale, thus avoiding the algorithmic problems of relating image representations at different resolution. Nevertheless, pyramids are still frequently used for expressing computationally efficient approximations to scale-space representation. === Detail manipulation === Levels of a Laplacian pyramid can be added to or removed from the original image to amplify or reduce detail at different scales. However, detail manipulation of this form is known to produce halo artifacts in many cases, leading to the development of alternatives such as the bilateral filter. Some image compression file formats use the Adam7 algorithm or some other interlacing technique. These can be seen as a kind of image pyramid. Because those file format store the "large-scale" features first, and fine-grain details later in the file, a particular viewer displaying a small "thumbnail" or on a small screen can quickly download just enough of the image to display it in the available pixels—so one file can support many viewer resolutions, rather than having to store or generate a different file for each resolution.
Gödel machine
A Gödel machine is a hypothetical self-improving computer program that solves problems in an optimal way. It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove the new code provides a better strategy. The machine was invented by Jürgen Schmidhuber (first proposed in 2003), but is named after Kurt Gödel who inspired the mathematical theories. The Gödel machine is often discussed when dealing with issues of meta-learning, also known as "learning to learn." Applications include automating human design decisions and transfer of knowledge between multiple related tasks, and may lead to design of more robust and general learning architectures. Though theoretically possible, no full implementation has been created. The Gödel machine is often compared with Marcus Hutter's AIXI, another formal specification for an artificial general intelligence. Schmidhuber points out that the Gödel machine could start out by implementing AIXItl as its initial sub-program, and self-modify after it finds proof that another algorithm for its search code will be better. == Limitations == Traditional problems solved by a computer only require one input and provide some output. Computers of this sort had their initial algorithm hardwired. This does not take into account the dynamic natural environment, and thus was a goal for the Gödel machine to overcome. The Gödel machine has limitations of its own, however. According to Gödel's First Incompleteness Theorem, any formal system that encompasses arithmetic is either flawed or allows for statements that cannot be proved in the system. Hence even a Gödel machine with unlimited computational resources must ignore those self-improvements whose effectiveness it cannot prove. == Variables of interest == There are three variables that are particularly useful in the run time of the Gödel machine. At some time t {\displaystyle t} , the variable time {\displaystyle {\text{time}}} will have the binary equivalent of t {\displaystyle t} . This is incremented steadily throughout the run time of the machine. Any input meant for the Gödel machine from the natural environment is stored in variable x {\displaystyle x} . It is likely the case that x {\displaystyle x} will hold different values for different values of variable time {\displaystyle {\text{time}}} . The outputs of the Gödel machine are stored in variable y {\displaystyle y} , where y ( t ) {\displaystyle y(t)} would be the output bit-string at some time t {\displaystyle t} . At any given time t {\displaystyle t} , where ( 1 ≤ t ≤ T ) {\displaystyle (1\leq t\leq T)} , the goal is to maximize future success or utility. A typical utility function follows the pattern u ( s , E n v ) : S × E → R {\displaystyle u(s,\mathrm {Env} ):S\times E\rightarrow \mathbb {R} } : u ( s , E n v ) = E μ [ ∑ τ = time T r ( τ ) ∣ s , E n v ] {\displaystyle u(s,\mathrm {Env} )=E_{\mu }{\Bigg [}\sum _{\tau ={\text{time}}}^{T}r(\tau )\mid s,\mathrm {Env} {\Bigg ]}} where r ( t ) {\displaystyle r(t)} is a real-valued reward input (encoded within s ( t ) {\displaystyle s(t)} ) at time t {\displaystyle t} , E μ [ ⋅ ∣ ⋅ ] {\displaystyle E_{\mu }[\cdot \mid \cdot ]} denotes the conditional expectation operator with respect to some possibly unknown distribution μ {\displaystyle \mu } from a set M {\displaystyle M} of possible distributions ( M {\displaystyle M} reflects whatever is known about the possibly probabilistic reactions of the environment), and the above-mentioned time = time ( s ) {\displaystyle {\text{time}}=\operatorname {time} (s)} is a function of state s {\displaystyle s} which uniquely identifies the current cycle. Note that we take into account the possibility of extending the expected lifespan through appropriate actions. == Instructions used by proof techniques == The nature of the six proof-modifying instructions below makes it impossible to insert an incorrect theorem into proof, thus trivializing proof verification. === get-axiom(n) === Appends the n-th axiom as a theorem to the current theorem sequence. Below is the initial axiom scheme: Hardware Axioms formally specify how components of the machine could change from one cycle to the next. Reward Axioms define the computational cost of hardware instruction and the physical cost of output actions. Related Axioms also define the lifetime of the Gödel machine as scalar quantities representing all rewards/costs. Environment Axioms restrict the way new inputs x are produced from the environment, based on previous sequences of inputs y. Uncertainty Axioms/String Manipulation Axioms are standard axioms for arithmetic, calculus, probability theory, and string manipulation that allow for the construction of proofs related to future variable values within the Gödel machine. Initial State Axioms contain information about how to reconstruct parts or all of the initial state. Utility Axioms describe the overall goal in the form of utility function u. === apply-rule(k, m, n) === Takes in the index k of an inference rule (such as Modus tollens, Modus ponens), and attempts to apply it to the two previously proved theorems m and n. The resulting theorem is then added to the proof. === delete-theorem(m) === Deletes the theorem stored at index m in the current proof. This helps to mitigate storage constraints caused by redundant and unnecessary theorems. Deleted theorems can no longer be referenced by the above apply-rule function. === set-switchprog(m, n) === Replaces switchprog S pm:n, provided it is a non-empty substring of S p. === check() === Verifies whether the goal of the proof search has been reached. A target theorem states that given the current axiomatized utility function u (Item 1f), the utility of a switch from p to the current switchprog would be higher than the utility of continuing the execution of p (which would keep searching for alternative switchprogs). === state2theorem(m, n) === Takes in two arguments, m and n, and attempts to convert the contents of Sm:n into a theorem. == Example applications == === Time-limited NP-hard optimization === The initial input to the Gödel machine is the representation of a connected graph with a large number of nodes linked by edges of various lengths. Within given time T it should find a cyclic path connecting all nodes. The only real-valued reward will occur at time T. It equals 1 divided by the length of the best path found so far (0 if none was found). There are no other inputs. The by-product of maximizing expected reward is to find the shortest path findable within the limited time, given the initial bias. === Fast theorem proving === Prove or disprove as quickly as possible that all even integers > 2 are the sum of two primes (Goldbach’s conjecture). The reward is 1/t, where t is the time required to produce and verify the first such proof. === Maximizing expected reward with bounded resources === A cognitive robot that needs at least 1 liter of gasoline per hour interacts with a partially unknown environment, trying to find hidden, limited gasoline depots to occasionally refuel its tank. It is rewarded in proportion to its lifetime, and dies after at most 100 years or as soon as its tank is empty or it falls off a cliff, and so on. The probabilistic environmental reactions are initially unknown but assumed to be sampled from the axiomatized Speed Prior, according to which hard-to-compute environmental reactions are unlikely. This permits a computable strategy for making near-optimal predictions. One by-product of maximizing expected reward is to maximize expected lifetime.