In computational geometry, the farthest-first traversal of a compact metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, also known as the greedy permutation. Every prefix of a farthest-first traversal provides a set of points that is widely spaced and close to all remaining points. More precisely, no other set of equally many points can be spaced more than twice as widely, and no other set of equally many points can be less than half as far to its farthest remaining point. In part because of these properties, farthest-point traversals have many applications, including the approximation of the traveling salesman problem and the metric k-center problem. They may be constructed in polynomial time, or (for low-dimensional Euclidean spaces) approximated in near-linear time. == Definition and properties == A farthest-first traversal is a sequence of points in a compact metric space, with each point appearing at most once. If the space is finite, each point appears exactly once, and the traversal is a permutation of all of the points in the space. The first point of the sequence may be any point in the space. Each point p after the first must have the maximum possible distance to the set of points earlier than p in the sequence, where the distance from a point to a set is defined as the minimum of the pairwise distances to points in the set. A given space may have many different farthest-first traversals, depending both on the choice of the first point in the sequence (which may be any point in the space) and on ties for the maximum distance among later choices. Farthest-point traversals may be characterized by the following properties. Fix a number k, and consider the prefix formed by the first k points of the farthest-first traversal of any metric space. Let r be the distance between the final point of the prefix and the other points in the prefix. Then this subset has the following two properties: All pairs of the selected points are at distance at least r from each other, and All points of the metric space are at distance at most r from the subset. Conversely any sequence having these properties, for all choices of k, must be a farthest-first traversal. These are the two defining properties of a Delone set, so each prefix of the farthest-first traversal forms a Delone set. == Applications == Rosenkrantz, Stearns & Lewis (1977) used the farthest-first traversal to define the farthest-insertion heuristic for the travelling salesman problem. This heuristic finds approximate solutions to the travelling salesman problem by building up a tour on a subset of points, adding one point at a time to the tour in the ordering given by a farthest-first traversal. To add each point to the tour, one edge of the previous tour is broken and replaced by a pair of edges through the added point, in the cheapest possible way. Although Rosenkrantz et al. prove only a logarithmic approximation ratio for this method, they show that in practice it often works better than other insertion methods with better provable approximation ratios. Later, the same sequence of points was popularized by Gonzalez (1985), who used it as part of greedy approximation algorithms for two problems in clustering, in which the goal is to partition a set of points into k clusters. One of the two problems that Gonzalez solve in this way seeks to minimize the maximum diameter of a cluster, while the other, known as the metric k-center problem, seeks to minimize the maximum radius, the distance from a chosen central point of a cluster to the farthest point from it in the same cluster. For instance, the k-center problem can be used to model the placement of fire stations within a city, in order to ensure that every address within the city can be reached quickly by a fire truck. For both clustering problems, Gonzalez chooses a set of k cluster centers by selecting the first k points of a farthest-first traversal, and then creates clusters by assigning each input point to the nearest cluster center. If r is the distance from the set of k selected centers to the next point at position k + 1 in the traversal, then with this clustering every point is within distance r of its center and every cluster has diameter at most 2r. However, the subset of k centers together with the next point are all at distance at least r from each other, and any k-clustering would put some two of these points into a single cluster, with one of them at distance at least r/2 from its center and with diameter at least r. Thus, Gonzalez's heuristic gives an approximation ratio of 2 for both clustering problems. Gonzalez's heuristic was independently rediscovered for the metric k-center problem by Dyer & Frieze (1985), who applied it more generally to weighted k-center problems. Another paper on the k-center problem from the same time, Hochbaum & Shmoys (1985), achieves the same approximation ratio of 2, but its techniques are different. Nevertheless, Gonzalez's heuristic, and the name "farthest-first traversal", are often incorrectly attributed to Hochbaum and Shmoys. For both the min-max diameter clustering problem and the metric k-center problem, these approximations are optimal: the existence of a polynomial-time heuristic with any constant approximation ratio less than 2 would imply that P = NP. As well as for clustering, the farthest-first traversal can also be used in another type of facility location problem, the max-min facility dispersion problem, in which the goal is to choose the locations of k different facilities so that they are as far apart from each other as possible. More precisely, the goal in this problem is to choose k points from a given metric space or a given set of candidate points, in such a way as to maximize the minimum pairwise distance between the selected points. Again, this can be approximated by choosing the first k points of a farthest-first traversal. If r denotes the distance of the kth point from all previous points, then every point of the metric space or the candidate set is within distance r of the first k − 1 points. By the pigeonhole principle, some two points of the optimal solution (whatever it is) must both be within distance r of the same point among these first k − 1 chosen points, and (by the triangle inequality) within distance 2r of each other. Therefore, the heuristic solution given by the farthest-first traversal is within a factor of two of optimal. Other applications of the farthest-first traversal include color quantization (clustering the colors in an image to a smaller set of representative colors), progressive scanning of images (choosing an order to display the pixels of an image so that prefixes of the ordering produce good lower-resolution versions of the whole image rather than filling in the image from top to bottom), point selection in the probabilistic roadmap method for motion planning, simplification of point clouds, generating masks for halftone images, hierarchical clustering, finding the similarities between polygon meshes of similar surfaces, choosing diverse and high-value observation targets for underwater robot exploration, fault detection in sensor networks, modeling phylogenetic diversity, matching vehicles in a heterogenous fleet to customer delivery requests, uniform distribution of geodetic observatories on the Earth's surface or of other types of sensor network, generation of virtual point lights in the instant radiosity computer graphics rendering method, and geometric range searching data structures. == Algorithms == === Greedy exact algorithm === The farthest-first traversal of a finite point set may be computed by a greedy algorithm that maintains the distance of each point from the previously selected points, performing the following steps: Initialize the sequence of selected points to the empty sequence, and the distances of each point to the selected points to infinity. While not all points have been selected, repeat the following steps: Scan the list of not-yet-selected points to find a point p that has the maximum distance from the selected points. Remove p from the not-yet-selected points and add it to the end of the sequence of selected points. For each remaining not-yet-selected point q, replace the distance stored for q by the minimum of its old value and the distance from p to q. For a set of n points, this algorithm takes O(n2) steps and O(n2) distance computations. === Approximations === A faster approximation algorithm, given by Har-Peled & Mendel (2006), applie
Algorithmic inference
Algorithmic inference gathers new developments in the statistical inference methods made feasible by the powerful computing devices widely available to any data analyst. Cornerstones in this field are computational learning theory, granular computing, bioinformatics, and, long ago, structural probability (Fraser 1966). The main focus is on the algorithms which compute statistics rooting the study of a random phenomenon, along with the amount of data they must feed on to produce reliable results. This shifts the interest of mathematicians from the study of the distribution laws to the functional properties of the statistics, and the interest of computer scientists from the algorithms for processing data to the information they process. == The Fisher parametric inference problem == Concerning the identification of the parameters of a distribution law, the mature reader may recall lengthy disputes in the mid 20th century about the interpretation of their variability in terms of fiducial distribution (Fisher 1956), structural probabilities (Fraser 1966), priors/posteriors (Ramsey 1925), and so on. From an epistemology viewpoint, this entailed a companion dispute as to the nature of probability: is it a physical feature of phenomena to be described through random variables or a way of synthesizing data about a phenomenon? Opting for the latter, Fisher defines a fiducial distribution law of parameters of a given random variable that he deduces from a sample of its specifications. With this law he computes, for instance "the probability that μ (mean of a Gaussian variable – omeur note) is less than any assigned value, or the probability that it lies between any assigned values, or, in short, its probability distribution, in the light of the sample observed". == The classic solution == Fisher fought hard to defend the difference and superiority of his notion of parameter distribution in comparison to analogous notions, such as Bayes' posterior distribution, Fraser's constructive probability and Neyman's confidence intervals. For half a century, Neyman's confidence intervals won out for all practical purposes, crediting the phenomenological nature of probability. With this perspective, when you deal with a Gaussian variable, its mean μ is fixed by the physical features of the phenomenon you are observing, where the observations are random operators, hence the observed values are specifications of a random sample. Because of their randomness, you may compute from the sample specific intervals containing the fixed μ with a given probability that you denote confidence. === Example === Let X be a Gaussian variable with parameters μ {\displaystyle \mu } and σ 2 {\displaystyle \sigma ^{2}} and { X 1 , … , X m } {\displaystyle \{X_{1},\ldots ,X_{m}\}} a sample drawn from it. Working with statistics S μ = ∑ i = 1 m X i {\displaystyle S_{\mu }=\sum _{i=1}^{m}X_{i}} and S σ 2 = ∑ i = 1 m ( X i − X ¯ ) 2 , where X ¯ = S μ m {\displaystyle S_{\sigma ^{2}}=\sum _{i=1}^{m}(X_{i}-{\overline {X}})^{2},{\text{ where }}{\overline {X}}={\frac {S_{\mu }}{m}}} is the sample mean, we recognize that T = S μ − m μ S σ 2 m − 1 m = X ¯ − μ S σ 2 / ( m ( m − 1 ) ) {\displaystyle T={\frac {S_{\mu }-m\mu }{\sqrt {S_{\sigma ^{2}}}}}{\sqrt {\frac {m-1}{m}}}={\frac {{\overline {X}}-\mu }{\sqrt {S_{\sigma ^{2}}/(m(m-1))}}}} follows a Student's t distribution (Wilks 1962) with parameter (degrees of freedom) m − 1, so that f T ( t ) = Γ ( m / 2 ) Γ ( ( m − 1 ) / 2 ) 1 π ( m − 1 ) ( 1 + t 2 m − 1 ) m / 2 . {\displaystyle f_{T}(t)={\frac {\Gamma (m/2)}{\Gamma ((m-1)/2)}}{\frac {1}{\sqrt {\pi (m-1)}}}\left(1+{\frac {t^{2}}{m-1}}\right)^{m/2}.} Gauging T between two quantiles and inverting its expression as a function of μ {\displaystyle \mu } you obtain confidence intervals for μ {\displaystyle \mu } . With the sample specification: x = { 7.14 , 6.3 , 3.9 , 6.46 , 0.2 , 2.94 , 4.14 , 4.69 , 6.02 , 1.58 } {\displaystyle \mathbf {x} =\{7.14,6.3,3.9,6.46,0.2,2.94,4.14,4.69,6.02,1.58\}} having size m = 10, you compute the statistics s μ = 43.37 {\displaystyle s_{\mu }=43.37} and s σ 2 = 46.07 {\displaystyle s_{\sigma ^{2}}=46.07} , and obtain a 0.90 confidence interval for μ {\displaystyle \mu } with extremes (3.03, 5.65). == Inferring functions with the help of a computer == From a modeling perspective the entire dispute looks like a chicken-egg dilemma: either fixed data by first and probability distribution of their properties as a consequence, or fixed properties by first and probability distribution of the observed data as a corollary. The classic solution has one benefit and one drawback. The former was appreciated particularly back when people still did computations with sheet and pencil. Per se, the task of computing a Neyman confidence interval for the fixed parameter θ is hard: you do not know θ, but you look for disposing around it an interval with a possibly very low probability of failing. The analytical solution is allowed for a very limited number of theoretical cases. Vice versa a large variety of instances may be quickly solved in an approximate way via the central limit theorem in terms of confidence interval around a Gaussian distribution – that's the benefit. The drawback is that the central limit theorem is applicable when the sample size is sufficiently large. Therefore, it is less and less applicable with the sample involved in modern inference instances. The fault is not in the sample size on its own part. Rather, this size is not sufficiently large because of the complexity of the inference problem. With the availability of large computing facilities, scientists refocused from isolated parameters inference to complex functions inference, i.e. re sets of highly nested parameters identifying functions. In these cases we speak about learning of functions (in terms for instance of regression, neuro-fuzzy system or computational learning) on the basis of highly informative samples. A first effect of having a complex structure linking data is the reduction of the number of sample degrees of freedom, i.e. the burning of a part of sample points, so that the effective sample size to be considered in the central limit theorem is too small. Focusing on the sample size ensuring a limited learning error with a given confidence level, the consequence is that the lower bound on this size grows with complexity indices such as VC dimension or detail of a class to which the function we want to learn belongs. === Example === A sample of 1,000 independent bits is enough to ensure an absolute error of at most 0.081 on the estimation of the parameter p of the underlying Bernoulli variable with a confidence of at least 0.99. The same size cannot guarantee a threshold less than 0.088 with the same confidence 0.99 when the error is identified with the probability that a 20-year-old man living in New York does not fit the ranges of height, weight and waistline observed on 1,000 Big Apple inhabitants. The accuracy shortage occurs because both the VC dimension and the detail of the class of parallelepipeds, among which the one observed from the 1,000 inhabitants' ranges falls, are equal to 6. == The general inversion problem solving the Fisher question == With insufficiently large samples, the approach: fixed sample – random properties suggests inference procedures in three steps: === Definition === For a random variable and a sample drawn from it a compatible distribution is a distribution having the same sampling mechanism M X = ( Z , g θ ) {\displaystyle {\mathcal {M}}_{X}=(Z,g_{\boldsymbol {\theta }})} of X with a value θ {\displaystyle {\boldsymbol {\theta }}} of the random parameter Θ {\displaystyle \mathbf {\Theta } } derived from a master equation rooted on a well-behaved statistic s. === Example === You may find the distribution law of the Pareto parameters A and K as an implementation example of the population bootstrap method as in the figure on the left. Implementing the twisting argument method, you get the distribution law F M ( μ ) {\displaystyle F_{M}(\mu )} of the mean M of a Gaussian variable X on the basis of the statistic s M = ∑ i = 1 m x i {\textstyle s_{M}=\sum _{i=1}^{m}x_{i}} when Σ 2 {\displaystyle \Sigma ^{2}} is known to be equal to σ 2 {\displaystyle \sigma ^{2}} (Apolloni, Malchiodi & Gaito 2006). Its expression is: F M ( μ ) = Φ ( m μ − s M σ m ) , {\displaystyle F_{M}(\mu )=\Phi {\left({\frac {m\mu -s_{M}}{\sigma {\sqrt {m}}}}\right)},} shown in the figure on the right, where Φ {\displaystyle \Phi } is the cumulative distribution function of a standard normal distribution. Computing a confidence interval for M given its distribution function is straightforward: we need only find two quantiles (for instance δ / 2 {\displaystyle \delta /2} and 1 − δ / 2 {\displaystyle 1-\delta /2} quantiles in case we are interested in a confidence interval of level δ symmetric in the tail's probabilities) as indicated on the left in the diagram showing the behavior of
Is an AI Avatar Generator Worth It in 2026?
Looking for the best AI avatar generator? An AI avatar generator is software that uses machine learning to help you get more done — it can save you hours every week by automating repetitive work. Most options offer a generous free tier, with paid plans unlocking higher limits, faster processing, and team features. Whether you are a beginner or a pro, the right AI avatar generator slots into your workflow and pays for itself fast. Read on for hands-on impressions, pricing tiers, and the standout features that matter.
Ω-automaton
In automata theory, a branch of theoretical computer science, an ω-automaton (or stream automaton) is a variation of a finite automaton that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states. ω-automata are useful for specifying behavior of systems that are not expected to terminate, such as hardware, operating systems and control systems. For such systems, one may want to specify a property such as "for every request, an acknowledge eventually follows", or its negation "there is a request that is not followed by an acknowledge". The former is a property of infinite words: one cannot say of a finite sequence that it satisfies this property. Classes of ω-automata include the Büchi automata, Rabin automata, Streett automata, parity automata and Muller automata, each deterministic or non-deterministic. These classes of ω-automata differ only in terms of acceptance condition. They all recognize precisely the regular ω-languages except for the deterministic Büchi automata, which is strictly weaker than all the others. Although all these types of automata recognize the same set of ω-languages, they nonetheless differ in succinctness of representation for a given ω-language. == Deterministic ω-automata == Formally, a deterministic ω-automaton is a tuple A = ( Q , Σ , δ , q 0 , A a c c ) {\textstyle A=(Q,\Sigma ,\delta ,q_{0},A_{acc})} , that consists of the following components: Q {\textstyle Q} , is a finite set. The elements of Q {\textstyle Q} are called the states of A {\textstyle A} . Σ {\textstyle \Sigma } , is a finite set called the alphabet of A {\textstyle A} . δ : Q × Σ → Q {\textstyle \delta \colon Q\times \Sigma \rightarrow Q} is a function, called the transition function of A {\textstyle A} . Q 0 {\textstyle Q_{0}} is an element of Q {\textstyle Q} , called the initial state. A a c c {\textstyle A_{acc}} is a set of accepting states of A {\textstyle A} , formally a subset of Q ω {\textstyle Q^{\omega }} . An input for A {\textstyle A} is an infinite string over the alphabet Σ {\textstyle \Sigma } , i.e. it is an infinite sequence α = ( a 1 , a 2 , a 3 , … ) {\textstyle \alpha =(a_{1},a_{2},a_{3},\ldots )} . The run of A {\textstyle A} on such an input is an infinite sequence ρ = ( r 0 , r 1 , r 2 , … ) {\textstyle \rho =(r_{0},r_{1},r_{2},\ldots )} of states, defined as follows: r 0 = q 0 {\textstyle r_{0}=q_{0}} . r 1 = δ ( r 0 , a 1 ) {\textstyle r_{1}=\delta (r_{0},a_{1})} . r 2 = δ ( r 1 , a 2 ) {\textstyle r_{2}=\delta (r_{1},a_{2})} . ... that is, for every i {\textstyle i} : r i = δ ( r i − 1 , a i ) {\textstyle r_{i}=\delta (r_{i-1},a_{i})} . The main purpose of an ω-automaton is to define a subset of the set of all inputs: The set of accepted inputs. Whereas in the case of an ordinary finite automaton every run ends with a state r n {\textstyle r_{n}} and the input is accepted if and only if r n {\textstyle r_{n}} is an accepting state, the definition of the set of accepted inputs is more complicated for ω-automata. Here we must look at the entire run ρ {\textstyle \rho } . The input is accepted if the corresponding run is in Acc {\textstyle {\text{Acc}}} . The set of accepted input ω-words is called the recognized ω-language by the automaton, which is denoted as L ( A ) {\textstyle L(A)} . The definition of Acc {\textstyle {\text{Acc}}} as a subset of Q ω {\textstyle Q^{\omega }} is purely formal and not suitable for practice because normally such sets are infinite. The difference between various types of ω-automata (Büchi, Rabin etc.) consists in how they encode certain subsets Acc {\textstyle {\text{Acc}}} of Q ω {\textstyle Q^{\omega }} as finite sets, and therefore in which such subsets they can encode. == Nondeterministic ω-automata == Formally, a nondeterministic ω-automaton is a tuple A = ( Q , Σ , Δ , Q 0 , Acc ) {\textstyle A=(Q,\Sigma ,\Delta ,Q_{0},{\text{Acc}})} that consists of the following components: Q {\textstyle Q} is a finite set. The elements of Q {\textstyle Q} are called the states of A {\textstyle A} . Σ {\textstyle \Sigma } is a finite set called the alphabet of A {\textstyle A} . Δ {\textstyle \Delta } is a subset of Q × Σ × Q {\textstyle Q\times \Sigma \times Q} and is called the transition relation of A {\textstyle A} . Q 0 {\textstyle Q_{0}} is a subset of Q {\textstyle Q} , called the initial set of states. Acc {\textstyle {\text{Acc}}} is the acceptance condition, a subset of Q ω {\textstyle Q^{\omega }} . Unlike a deterministic ω-automaton, which has a transition function δ {\textstyle \delta } , the non-deterministic version has a transition relation Δ {\textstyle \Delta } . Note that Δ {\textstyle \Delta } can be regarded as a function Q × Σ → P ( Q ) {\textstyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)} from Q × Σ {\textstyle Q\times \Sigma } to the power set P ( Q ) {\textstyle {\mathcal {P}}(Q)} . Thus, given a state q n {\textstyle q_{n}} and a symbol a n {\textstyle a_{n}} , the next state q n + 1 {\textstyle q_{n+1}} is not necessarily determined uniquely, rather there is a set of possible next states. A run of A {\textstyle A} on the input α = ( a 1 , a 2 , a 3 , … ) {\textstyle \alpha =(a_{1},a_{2},a_{3},\ldots )} is any infinite sequence ρ = ( r 0 , r 1 , r 2 , … ) {\textstyle \rho =(r_{0},r_{1},r_{2},\ldots )} of states that satisfies the following conditions: r 0 {\textstyle r_{0}} is an element of Q 0 {\textstyle Q_{0}} . r 1 {\textstyle r_{1}} is an element of Δ ( r 0 , a 1 ) {\textstyle \Delta (r_{0},a_{1})} . r 2 {\textstyle r_{2}} is an element of Δ ( r 1 , a 2 ) {\textstyle \Delta (r_{1},a_{2})} . ... that is, for every i {\textstyle i} : r i {\textstyle r_{i}} is an element of Δ ( r i − 1 , a i ) {\textstyle \Delta (r_{i-1},a_{i})} . A nondeterministic ω-automaton may admit many different runs on any given input, or none at all. The input is accepted if at least one of the possible runs is accepting. Whether a run is accepting depends only on Acc {\textstyle {\text{Acc}}} , as for deterministic ω-automata. Every deterministic ω-automaton can be regarded as a nondeterministic ω-automaton by taking Δ {\textstyle \Delta } to be the graph of δ {\textstyle \delta } . The definitions of runs and acceptance for deterministic ω-automata are then special cases of the nondeterministic cases. == Acceptance conditions == Acceptance conditions may be infinite sets of ω-words. However, people mostly study acceptance conditions that are finitely representable. The following lists a variety of popular acceptance conditions. Before discussing the list, let's make the following observation. In the case of infinitely running systems, one is often interested in whether certain behavior is repeated infinitely often. For example, if a network card receives infinitely many ping requests, then it may fail to respond to some of the requests but should respond to an infinite subset of received ping requests. This motivates the following definition: For any run ρ {\textstyle \rho } , let Inf ( ρ ) {\textstyle {\text{Inf}}(\rho )} be the set of states that occur infinitely often in ρ {\textstyle \rho } . This notion of certain states being visited infinitely often will be helpful in defining the following acceptance conditions. A Büchi automaton is an ω-automaton A {\textstyle A} that uses the following acceptance condition, for some subset F {\textstyle F} of Q {\textstyle Q} : Büchi condition A {\textstyle A} accepts exactly those runs ρ {\textstyle \rho } for which Inf ( ρ ) ∩ F ≠ ∅ {\textstyle {\text{Inf}}(\rho )\cap F\neq \emptyset } , i.e. there is an accepting state that occurs infinitely often in ρ {\textstyle \rho } . A Rabin automaton is an ω-automaton A {\textstyle A} that uses the following acceptance condition, for some set Ω {\textstyle \Omega } of pairs ( B i , G i ) {\textstyle (B_{i},G_{i})} of sets of states: Rabin condition A {\textstyle A} accepts exactly those runs ρ {\textstyle \rho } for which there exists a pair ( B i , G i ) {\textstyle (B_{i},G_{i})} in Ω {\textstyle \Omega } such that B i ∩ Inf ( ρ ) = ∅ {\textstyle B_{i}\cap {\text{Inf}}(\rho )=\emptyset } and G i ∩ Inf ( ρ ) ≠ ∅ {\textstyle G_{i}\cap {\text{Inf}}(\rho )\neq \emptyset } . A Streett automaton is an ω-automaton A {\textstyle A} that uses the following acceptance condition, for some set Ω {\textstyle \Omega } of pairs ( B i , G i ) {\textstyle (B_{i},G_{i})} of sets of states: Streett condition A {\textstyle A} accepts exactly those runs ρ {\textstyle \rho } such that for all pairs ( B i , G i ) {\textstyle (B_{i},G_{i})} in Ω {\textstyle \Omega } , B i ∩ Inf ( ρ ) ≠ ∅ {\textstyle B_{i}\cap {\text{Inf}}(\rho )\neq \emptyset } or G i ∩ Inf ( ρ ) = ∅ {\textstyle G_{i}\cap {\text{Inf}}(\rho )=\emptyset } . A parity automaton is an automaton A {\textstyle A} whose set of states is Q = { 0 , 1 , 2 , … , k } {\textstyle Q=\{0,1,2,\ldots ,k\}} for some natural number k {\textst
Hanna Hajishirzi
Hannaneh Hajishirzi is an Iranian-American computer scientist specializing in natural language processing. She is Torode Family Professor in Computer Science & Engineering in the Paul G. Allen School of Computer Science and Engineering at the University of Washington, head of the H2Lab in the Allen School, and a senior director of natural language processing in the Allen Institute for AI. == Education and career == After a bachelor's degree from the Sharif University of Technology, Hajishirzi completed her Ph.D. in computer science in 2011, at the University of Illinois Urbana-Champaign. Her dissertation, Action-Centered Reasoning for Probabilistic Dynamic Systems, was supervised by Eyal Amir. After postdoctoral research at Disney Research in Pittsburgh, Hajishirzi joined the University of Washington in 2012, as a research scientist in electrical engineering. In 2015 she became a research assistant professor in electrical engineering. She obtained a regular-rank assistant professorship in 2018, at the same time becoming an AI Fellow in the Allen Institute for AI, where she became a senior director of research in 2021. She was promoted to associate professor in 2022 and to full professor in 2025. == Recognition == Hajishirzi was named as a Fellow of the Association for Computational Linguistics in 2025, "for significant contributions to question answering, scientific applications, multimodal artificial intelligence, and fully open language models". == Personal life == Hajishirzi is married to Ali Farhadi, the CEO of the Allen Institute for AI.
Retained mode
Retained mode in computer graphics is a major pattern of API design in graphics libraries, in which the graphics library, instead of the client, retains the scene (complete object model of the rendering primitives) to be rendered and the client calls into the graphics library do not directly cause actual rendering, but make use of extensive indirection to resources, managed – thus retained – by the graphics library. It does not preclude the use of double-buffering. Immediate mode is an alternative approach. Historically, retained mode has been the dominant style in GUI libraries; however, both can coexist in the same library and are not necessarily exclusionary in practice. == Overview == In retained mode the client calls do not directly cause actual rendering, but instead update an abstract internal model (typically a list of objects) which is maintained within the library's data space. This allows the library to optimize when actual rendering takes place along with the processing of related objects. Some techniques to optimize rendering include: managing double buffering treatment of hidden surfaces by backface culling/occlusion culling (Z-buffering) only transferring data that has changed from one frame to the next from the application to the library Example of coexistence with immediate mode in the same library is OpenGL. OpenGL has immediate mode functions that can use previously defined server side objects (textures, vertex buffers and index buffers, shaders, etc.) without resending unchanged data. Examples of retained mode rendering systems include Windows Presentation Foundation, SceneKit on macOS, and PHIGS.
Adobe Enhanced Speech
Adobe Enhanced Speech is an online artificial intelligence software tool by Adobe that aims to significantly improve the quality of recorded speech that may be badly muffled, reverberated, full of artifacts, tinny, etc. and convert it to a studio-grade, professional level, regardless of the initial input's clarity. Users may upload mp3 or wav files up to an hour long and a gigabyte in size to the site to convert them relatively quickly, then being free to listen to the converted version, toggle back-and-forth and alternate between it and the original as it plays, and download it. Currently in beta and free to the public, it has been used in the restoration of old movies and the creation of professional-quality podcasts, narrations, etc. by those without sufficient microphones. Although the model still has some current limitations, such as not being compatible with singing and occasional issues with excessively muffled source audio resulting in a light lisp in the improved version, it is otherwise noted as incredibly effective and efficient in its purpose. Utilizing advanced machine learning algorithms to distinguish between speech and background sounds, it enhances the quality of the speech by filtering out the noise and artifacts, adjusting the pitch and volume levels, and normalizing the audio. This is accomplished by the network having been trained on a large dataset of speech samples from a diverse range of sources and then being fine-tuned to optimize the output.