Algorithm engineering focuses on the design, analysis, implementation, optimization, profiling and experimental evaluation of computer algorithms, bridging the gap between algorithmics theory and practical applications of algorithms in software engineering. It is a general methodology for algorithmic research. == Origins == In 1995, a report from an NSF-sponsored workshop "with the purpose of assessing the current goals and directions of the Theory of Computing (TOC) community" identified the slow speed of adoption of theoretical insights by practitioners as an important issue and suggested measures to reduce the uncertainty by practitioners whether a certain theoretical breakthrough will translate into practical gains in their field of work, and tackle the lack of ready-to-use algorithm libraries, which provide stable, bug-free and well-tested implementations for algorithmic problems and expose an easy-to-use interface for library consumers. But also, promising algorithmic approaches have been neglected due to difficulties in mathematical analysis. The term "algorithm engineering" was first used with specificity in 1997, with the first Workshop on Algorithm Engineering (WAE97), organized by Giuseppe F. Italiano. == Difference from algorithm theory == Algorithm engineering does not intend to replace or compete with algorithm theory, but tries to enrich, refine and reinforce its formal approaches with experimental algorithmics (also called empirical algorithmics). This way it can provide new insights into the efficiency and performance of algorithms in cases where the algorithm at hand is less amenable to algorithm theoretic analysis, formal analysis pessimistically suggests bounds which are unlikely to appear on inputs of practical interest, the algorithm relies on the intricacies of modern hardware architectures like data locality, branch prediction, instruction stalls, instruction latencies which the machine model used in Algorithm Theory is unable to capture in the required detail, the crossover between competing algorithms with different constant costs and asymptotic behaviors needs to be determined. == Methodology == Some researchers describe algorithm engineering's methodology as a cycle consisting of algorithm design, analysis, implementation and experimental evaluation, joined by further aspects like machine models or realistic inputs. They argue that equating algorithm engineering with experimental algorithmics is too limited, because viewing design and analysis, implementation and experimentation as separate activities ignores the crucial feedback loop between those elements of algorithm engineering. === Realistic models and real inputs === While specific applications are outside the methodology of algorithm engineering, they play an important role in shaping realistic models of the problem and the underlying machine, and supply real inputs and other design parameters for experiments. === Design === Compared to algorithm theory, which usually focuses on the asymptotic behavior of algorithms, algorithm engineers need to keep further requirements in mind: Simplicity of the algorithm, implementability in programming languages on real hardware, and allowing code reuse. Additionally, constant factors of algorithms have such a considerable impact on real-world inputs that sometimes an algorithm with worse asymptotic behavior performs better in practice due to lower constant factors. === Analysis === Some problems can be solved with heuristics and randomized algorithms in a simpler and more efficient fashion than with deterministic algorithms. Unfortunately, this makes even simple randomized algorithms difficult to analyze because there are subtle dependencies to be taken into account. === Implementation === Huge semantic gaps between theoretical insights, formulated algorithms, programming languages and hardware pose a challenge to efficient implementations of even simple algorithms, because small implementation details can have rippling effects on execution behavior. The only reliable way to compare several implementations of an algorithm is to spend an considerable amount of time on tuning and profiling, running those algorithms on multiple architectures, and looking at the generated machine code. === Experiments === See: Experimental algorithmics === Application engineering === Implementations of algorithms used for experiments differ in significant ways from code usable in applications. While the former prioritizes fast prototyping, performance and instrumentation for measurements during experiments, the latter requires thorough testing, maintainability, simplicity, and tuning for particular classes of inputs. === Algorithm libraries === Stable, well-tested algorithm libraries like LEDA play an important role in technology transfer by speeding up the adoption of new algorithms in applications. Such libraries reduce the required investment and risk for practitioners, because it removes the burden of understanding and implementing the results of academic research. == Conferences == Two main conferences on Algorithm Engineering are organized annually, namely: Symposium on Experimental Algorithms (SEA), established in 1997 (formerly known as WEA). SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), established in 1999. The 1997 Workshop on Algorithm Engineering (WAE'97) was held in Venice (Italy) on September 11–13, 1997. The Third International Workshop on Algorithm Engineering (WAE'99) was held in London, UK in July 1999. The first Workshop on Algorithm Engineering and Experimentation (ALENEX99) was held in Baltimore, Maryland on January 15–16, 1999. It was sponsored by DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science (at Rutgers University), with additional support from SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory, and SIAM, the Society for Industrial and Applied Mathematics.
Layers (digital image editing)
Layers are used in digital image editing to separate different elements of an image. A layer can be compared to a transparency on which imaging effects or images are applied and placed over or under an image. Today they are an integral feature of image editors. In the early days of computing, memory was at a premium and the idea of using multi-layered images was considered infeasible in personal computer applications as the tradeoffs were image size and color depth. As the price of memory fell it became feasible to apply the concept of layering to raster images. The first software known to apply the concept of layers was LALF, which was released in 1989 for the NEC PC-9801. LALF's terminology for layers is "cells", after the concept of drawing animation frames over-top of a stencil. Layers were introduced in Western markets by Fauve Matisse (later Macromedia xRes), and then available in Adobe Photoshop 3.0, in 1994, which lead to widespread adoption. In vector image editors that support animation, layers are used to further enable manipulation along a common timeline for the animation; in SVG images, the equivalent to layers are "groups". == Layer types == There are different kinds of layers, and not all of them exist in all programs. They represent a part of a picture, either as pixels or as modification instructions. They are stacked on top of each other, and depending on the order, determine the appearance of the final picture. In graphics software, layers are the different levels at which one can place an object or image file. In the program, layers can be stacked, merged, or defined when creating a digital image. Layers can be partially obscured allowing portions of images within a layer to be hidden or shown in a translucent manner within another image. Layers can also be used to combine two or more images into a single digital image. For the purpose of editing, working with layers allows for applying changes to just one specific layer. == Layer (basic) == The standard layer available to most programs consists of a rectangular, semitransparent picture which may be superimposed over other layers. Some programs require that layers cover the same area as the final canvas, but others offer layers of multiple sizes. Each layer may bear individual settings, such as opacity, blending modes, dynamic filters, and potentially hundreds of other properties. == Layer mask == A layer mask is linked to a layer and hides part of the layer from the picture. What is painted black on the layer mask will not be visible in the final picture. What is grey will be more or less transparent depending on the shade of grey. As the layer mask can be both edited and moved around independently of both the background layer and the layer it applies to, it gives the user the ability to test a lot of different combinations of overlay. == Adjustment layer == An adjustment layer typically applies a common effect like brightness or saturation to other layers. However, as the effect is stored in a separate layer, it is easy to try it out and switch between different alternatives, without changing the original layer. In addition, an adjustment layer can easily be edited, just like a layer mask, so an effect can be applied to just part of the image.
Irwin King
Irwin King is a Hong Kong computer scientist known for his contributions to machine learning, social computing, and recommender systems. == Career == King is a professor in the Department of Computer Science and Engineering at the Chinese University of Hong Kong. His research focuses on machine learning and social computing, including work on social recommendation, trust-aware recommender systems, and graph-based learning. King has served as editor-in-chief of the journal ACM Transactions on Intelligent Systems and Technology (TIST). == Awards == ACM Fellow (2024) IEEE Fellow (2019) INNS Fellow (2021) AAIA Fellow (2022) HKIE Fellow ACM WSDM Test of Time Award (2022) ACM SIGIR Test of Time Award (2020) ACM CIKM Test of Time Award (2019) 2021 INNS Dennis Gabor Award for work in Neural Engineering for Social Computing 2020 APNNS Outstanding Achievement Award
Cortana (virtual assistant)
Cortana is a discontinued virtual assistant developed by Microsoft that used the Bing search engine to perform tasks such as setting reminders and answering questions for users. Cortana was available in English, Portuguese, French, German, Italian, Spanish, Chinese, and Japanese language editions, depending on the software platform and region in which it was used. In 2019, Microsoft began reducing the prevalence of Cortana and converting it from an assistant into different software integrations. It was split from the Windows 10 search bar in April 2019. In January 2020, the Cortana mobile app was removed from certain markets, and on March 31, 2021, the Cortana mobile app was shut down globally. On June 2, 2023, Microsoft announced that support for the Cortana standalone app on Microsoft Windows would end in late 2023 and would be replaced by Microsoft Copilot, an AI chatbot. Support for Cortana in the Microsoft Outlook and Microsoft 365 mobile apps was discontinued in fall of 2023. == History == === Beginnings (2009–2014) === The development of Cortana started in 2009 in the Microsoft Speech products team with general manager Zig Serafin and Chief Scientist Larry Heck. Heck and Serafin established the vision, mission, and long-range plan for Microsoft's digital personal assistant and they built a team with the expertise to create the initial prototypes for Cortana. Some of the key researchers in these early efforts included Microsoft Research researchers Dilek Hakkani-Tür, Gokhan Tur, Andreas Stolcke, and Malcolm Slaney, research software developer Madhu Chinthakunta, and user experience designer Lisa Stifelman. To develop the Cortana digital assistant, the team interviewed human personal assistants. The interviews inspired a number of unique features in Cortana, including the assistant's "notebook" feature. Originally, Cortana was meant to be only a codename, but a petition on Windows Phone's UserVoice site proved to be popular and made the codename official. Cortana was demonstrated for the first time at the Microsoft Build developer conference in San Francisco in April 2014. It was launched as a key ingredient of Microsoft's planned "makeover" of future operating systems for Windows Phone and Windows. It was named after Cortana, a synthetic intelligence character in Microsoft's Halo video game franchise originating in Bungie folklore, with Jen Taylor, the character's voice actress, returning to voice the personal assistant's US-specific version. === Expansion (2015–2018) === In January 2015, Microsoft announced the availability of Cortana for Windows 10 desktops and mobile devices as part of merging Windows Phone into the operating system at large. On May 26, 2015, Microsoft announced that Cortana would also be available on other mobile platforms. An Android release was set for July 2015, but the Android APK file containing Cortana was leaked ahead of its release. It was officially released, along with an iOS version, in December 2015. During E3 2015, Microsoft announced that Cortana would come to the Xbox One as part of a universally designed Windows 10 update for the console. Microsoft integrated Cortana into numerous products such as Microsoft Edge. Microsoft's Cortana assistant was deeply integrated into the browser. Cortana was able to find opening hours when on restaurant sites, show retail coupons for websites, or show weather information in the address bar. At the Worldwide Partners Conference 2015 Microsoft demonstrated Cortana integration with products such as GigJam. Conversely, Microsoft announced in late April 2016 that it would block anything other than Bing and Edge from being used to complete Cortana searches, again raising questions of anti-competitive practices by the company. Microsoft's "Windows in the car" concept included Cortana. The concept makes it possible for drivers to make restaurant reservations and see places before they go there. At Microsoft Build 2016, Microsoft announced plans to integrate Cortana into Skype (Microsoft's video-conferencing and instant messaging service) as a bot to allow users to order food, book trips, transcribe video messages and make calendar appointments through Cortana in addition to other bots. As of 2016, Cortana was able to underline certain words and phrases in Skype conversations that relate to contacts and corporations. A writer from Engadget has criticised the Cortana integration in Skype for responding only to very specific keywords, feeling as if she was "chatting with a search engine" due to the impersonal way the bots replied to certain words such as "Hello" causing the Bing Music bot to bring up Adele's song of that name. Microsoft also announced at Microsoft Build 2016 that Cortana would be able to cloud-synchronise notifications between Windows 10 Mobile's and Windows 10's Action Center, as well as notifications from Android devices. In December 2016, Microsoft announced the preview of Calendar.help, a service that enabled people to delegate the scheduling of meetings to Cortana. Users interact with Cortana by including her in email conversations. Cortana would then check people's availability in Outlook Calendar or Google Calendar, and work with others Cc'd on the email to schedule the meeting. The service relied on automation and human-based computation. In May 2017, Microsoft announced INVOKE, a voice-activated speaker featuring Cortana, in collaboration with Harman Kardon. The premium speaker has a cylindrical design and offers 360-degree sound, the ability to make and receive calls with Skype, and all of the other features currently available with Cortana. In 2017, Microsoft partnered with Amazon to integrate Echo and Cortana with each other, allowing users of each smart assistant to summon the other via a command. This feature preview was released in August 2018. Windows 10 users were able to just say "Hey Cortana, open Alexa" and Echo users were able to say "Alexa, open Cortana" to summon the other assistant. === Decreasing focus and discontinuation (2019–2024) === In January 2019, Microsoft CEO Satya Nadella stated that he no longer saw Cortana as a direct competitor against Alexa and Siri. Shortly thereafter, Microsoft began reducing the prevalence of Cortana and converting it from an assistant into different software integrations. It was split from the Windows 10 search bar in April 2019. In January 2020, the Cortana mobile app was removed from certain markets, and then, on July 24, 2020, Cortana was removed from the Xbox dashboard as part of a redesign. On January 31, 2021, Microsoft removed the Cortana mobile application in many markets, including the UK, Australia, Germany, Mexico, China, Spain, Canada, and India. On March 31, 2021, Microsoft shut down the Cortana apps globally for iOS and Android and removed the apps entirely from their corresponding app stores. To access previously recorded content, users had to use Cortana on Windows 10 or other specialized Microsoft applications. Microsoft also reduced emphasis on Cortana in Windows with the 2021 release of Windows 11. Cortana was not used during the device setup process or pinned to the taskbar by default. On June 2, 2023, Microsoft announced the Cortana standalone app on Windows 10 and Windows 11 which would shut down later in the year. In its support article, Microsoft listed several alternatives, most of which have since been rebranded as Microsoft Copilot. They also added that the change would not impact Cortana in Office 365 and Teams environments. On August 11, 2023, Microsoft updated the Cortana standalone app in Windows, informing that it was deprecated and can no longer be used. Microsoft's support article announcing the deprecation of Cortana was updated to reflect this change. Along with the deprecation of the standalone app, it was announced that Cortana support in Teams mobile, Microsoft Teams displays, and Teams rooms would end in late 2023. The support article states that Cortana in the “Play my emails” feature of the Microsoft Outlook mobile app would continue to be available. Later in June 2024, the support article was updated, stating that Cortana in the voice search and the "Play my emails" feature is now removed from the Microsoft Outlook mobile app, officially marking the discontinuation of Cortana across all Microsoft products. On May 22, 2024, Microsoft announced the Windows 11 24H2 update, which removed Cortana, Tips, and WordPad from systems. == Functionality == Cortana was able to set reminders, recognize natural voice without the requirement for keyboard input, and answer questions using information from the Bing search engine. Searches using Windows 10 are made only with the Microsoft Bing search engine, and all links will open with Microsoft Edge, except when a screen reader such as Narrator was being used, where the links will open in Internet Explorer. Windows Phone 8.1's universal Bing SmartSearch features were incorporated into Cortana, which replaced the
Moore machine
In the theory of computation, a Moore machine is a finite-state machine whose current output values are determined only by its current state. This is in contrast to a Mealy machine, whose output values are determined both by its current state and by the values of its inputs. Like other finite state machines, in Moore machines, the input typically influences the next state. Thus the input may indirectly influence subsequent outputs, but not the current or immediate output. The Moore machine is named after Edward F. Moore, who presented the concept in a 1956 paper, “Gedanken-experiments on Sequential Machines.” == Formal definition == A Moore machine can be defined as a 6-tuple ( S , s 0 , Σ , Λ , δ , G ) {\displaystyle (S,s_{0},\Sigma ,\Lambda ,\delta ,G)} consisting of the following: A finite set of states S {\displaystyle S} A start state (also called initial state) s 0 {\displaystyle s_{0}} which is an element of S {\displaystyle S} A finite set called the input alphabet Σ {\displaystyle \Sigma } A finite set called the output alphabet Λ {\displaystyle \Lambda } A transition function δ : S × Σ → S {\displaystyle \delta :S\times \Sigma \rightarrow S} mapping a state and the input alphabet to the next state An output function G : S → Λ {\displaystyle G:S\rightarrow \Lambda } mapping each state to the output alphabet "Evolution across time" is realized in this abstraction by having the state machine consult the time-changing input symbol at discrete "timer ticks" t 0 , t 1 , t 2 , . . . {\displaystyle t_{0},t_{1},t_{2},...} and react according to its internal configuration at those idealized instants, or else having the state machine wait for a next input symbol (as on a FIFO) and react whenever it arrives. A Moore machine can be regarded as a restricted type of finite-state transducer. == Visual representation == === Table === A state transition table is a table listing all the triples in the transition relation δ : S × Σ → S {\displaystyle \delta :S\times \Sigma \rightarrow S} . === Diagram === The state diagram for a Moore machine, or Moore diagram, is a state diagram that associates an output value with each state. == Relationship with Mealy machines == As Moore and Mealy machines are both types of finite-state machines, they are equally expressive: either type can be used to parse a regular language. The difference between Moore machines and Mealy machines is that in the latter, the output of a transition is determined by the combination of current state and current input ( S × Σ {\displaystyle S\times \Sigma } as the domain of G {\displaystyle G} ), as opposed to just the current state ( S {\displaystyle S} as the domain of G {\displaystyle G} ). When represented as a state diagram, for a Moore machine, each node (state) is labeled with an output value; for a Mealy machine, each arc (transition) is labeled with an output value. Every Moore machine M {\displaystyle M} is equivalent to the Mealy machine with the same states and transitions and the output function G ( s , σ ) = G M ( δ M ( s , σ ) ) {\displaystyle G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))} , which takes each state-input pair ( s , σ ) {\displaystyle (s,\sigma )} and yields G M ( δ M ( s , σ ) ) {\displaystyle G_{M}(\delta _{M}(s,\sigma ))} , where G M {\displaystyle G_{M}} is M {\displaystyle M} 's output function and δ M {\displaystyle \delta _{M}} is M {\displaystyle M} 's transition function. However, not every Mealy machine can be converted to an equivalent Moore machine. Some can be converted only to an almost equivalent Moore machine, with outputs shifted in time. This is due to the way that state labels are paired with transition labels to form the input/output pairs. Consider a transition s i → s j {\displaystyle s_{i}\rightarrow s_{j}} from state s i {\displaystyle s_{i}} to state s j {\displaystyle s_{j}} . The input causing the transition s i → s j {\displaystyle s_{i}\rightarrow s_{j}} labels the edge ( s i , s j ) {\displaystyle (s_{i},s_{j})} . The output corresponding to that input, is the label of state s i {\displaystyle s_{i}} . Notice that this is the source state of the transition. So for each input, the output is already fixed before the input is received, and depends solely on the present state. This is the original definition by E. Moore. It is a common mistake to use the label of state s j {\displaystyle s_{j}} as output for the transition s i → s j {\displaystyle s_{i}\rightarrow s_{j}} . == Examples == Types according to number of inputs/outputs. === Simple === Simple Moore machines have one input and one output: edge detector using XOR binary adding machine clocked sequential systems (a restricted form of Moore machine where the state changes only when the global clock signal changes) Most digital electronic systems are designed as clocked sequential systems. Clocked sequential systems are a restricted form of Moore machine where the state changes only when the global clock signal changes. Typically the current state is stored in flip-flops, and a global clock signal is connected to the "clock" input of the flip-flops. Clocked sequential systems are one way to solve metastability problems. A typical electronic Moore machine includes a combinational logic chain to decode the current state into the outputs (lambda). The instant the current state changes, those changes ripple through that chain, and almost instantaneously the output gets updated. There are design techniques to ensure that no glitches occur on the outputs during that brief period while those changes are rippling through the chain, but most systems are designed so that glitches during that brief transition time are ignored or are irrelevant. The outputs then stay the same indefinitely (LEDs stay bright, power stays connected to the motors, solenoids stay energized, etc.), until the Moore machine changes state again. ==== Worked example ==== A sequential network has one input and one output. The output becomes 1 and remains 1 thereafter when at least two 0's and two 1's have occurred as inputs. A Moore machine with nine states for the above description is shown on the right. The initial state is state A, and the final state is state I. The state table for this example is as follows: === Complex === More complex Moore machines can have multiple inputs as well as multiple outputs. == Gedanken-experiments == In Moore's 1956 paper "Gedanken-experiments on Sequential Machines", the ( n ; m ; p ) {\displaystyle (n;m;p)} automata (or machines) S {\displaystyle S} are defined as having n {\displaystyle n} states, m {\displaystyle m} input symbols and p {\displaystyle p} output symbols. Nine theorems are proved about the structure of S {\displaystyle S} , and experiments with S {\displaystyle S} . Later, " S {\displaystyle S} machines" became known as "Moore machines". At the end of the paper, in Section "Further problems", the following task is stated: Another directly following problem is the improvement of the bounds given at the theorems 8 and 9. Moore's Theorem 8 is formulated as: Given an arbitrary ( n ; m ; p ) {\displaystyle (n;m;p)} machine S {\displaystyle S} , such that every two of its states are distinguishable from one another, then there exists an experiment of length n ( n − 1 ) 2 {\displaystyle {\tfrac {n(n-1)}{2}}} which determines the state of S {\displaystyle S} at the end of the experiment. In 1957, A. A. Karatsuba proved the following two theorems, which completely solved Moore's problem on the improvement of the bounds of the experiment length of his "Theorem 8". Theorem A. If S {\displaystyle S} is an ( n ; m ; p ) {\displaystyle (n;m;p)} machine, such that every two of its states are distinguishable from one another, then there exists a branched experiment of length at most ( n − 1 ) ( n − 2 ) 2 + 1 {\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1} through which one may determine the state of S {\displaystyle S} at the end of the experiment. Theorem B. There exists an ( n ; m ; p ) {\displaystyle (n;m;p)} machine, every two states of which are distinguishable from one another, such that the length of the shortest experiments establishing the state of the machine at the end of the experiment is equal to ( n − 1 ) ( n − 2 ) 2 + 1 {\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1} . Theorems A and B were used for the basis of the course work of a student of the fourth year, A. A. Karatsuba, "On a problem from the automata theory", which was distinguished by testimonial reference at the competition of student works of the faculty of mechanics and mathematics of Moscow State University in 1958. The paper by Karatsuba was given to the journal Uspekhi Mat. Nauk on 17 December 1958 and was published there in June 1960. Until the present day (2011), Karatsuba's result on the length of experiments is the only exact nonlinear result, both in automata theory, and in similar problems of computational complexity theory.
Granular computing
Granular computing is an emerging computing paradigm of information processing that concerns the processing of complex information entities called "information granules", which arise in the process of data abstraction and derivation of knowledge from information or data. Generally speaking, information granules are collections of entities that usually originate at the numeric level and are arranged together due to their similarity, functional or physical adjacency, indistinguishability, coherency, or the like. At present, granular computing is more a theoretical perspective than a coherent set of methods or principles. As a theoretical perspective, it encourages an approach to data that recognizes and exploits the knowledge present in data at various levels of resolution or scales. In this sense, it encompasses all methods which provide flexibility and adaptability in the resolution at which knowledge or information is extracted and represented. == Types of granulation == As mentioned above, granular computing is not an algorithm or process; there is no particular method that is called "granular computing". It is rather an approach to looking at data that recognizes how different and interesting regularities in the data can appear at different levels of granularity, much as different features become salient in satellite images of greater or lesser resolution. On a low-resolution satellite image, for example, one might notice interesting cloud patterns representing cyclones or other large-scale weather phenomena, while in a higher-resolution image, one misses these large-scale atmospheric phenomena but instead notices smaller-scale phenomena, such as the interesting pattern that is the streets of Manhattan. The same is generally true of all data: At different resolutions or granularities, different features and relationships emerge. The aim of granular computing is to try to take advantage of this fact in designing more effective machine-learning and reasoning systems. There are several types of granularity that are often encountered in data mining and machine learning, and we review them below: === Value granulation (discretization/quantization) === One type of granulation is the quantization of variables. It is very common that in data mining or machine-learning applications the resolution of variables needs to be decreased in order to extract meaningful regularities. An example of this would be a variable such as "outside temperature" (temp), which in a given application might be recorded to several decimal places of precision (depending on the sensing apparatus). However, for purposes of extracting relationships between "outside temperature" and, say, "number of health-club applications" (club), it will generally be advantageous to quantize "outside temperature" into a smaller number of intervals. ==== Motivations ==== There are several interrelated reasons for granulating variables in this fashion: Based on prior domain knowledge, there is no expectation that minute variations in temperature (e.g., the difference between 80–80.7 °F (26.7–27.1 °C)) could have an influence on behaviors driving the number of health-club applications. For this reason, any "regularity" which our learning algorithms might detect at this level of resolution would have to be spurious, as an artifact of overfitting. By coarsening the temperature variable into intervals the difference between which we do anticipate (based on prior domain knowledge) might influence number of health-club applications, we eliminate the possibility of detecting these spurious patterns. Thus, in this case, reducing resolution is a method of controlling overfitting. By reducing the number of intervals in the temperature variable (i.e., increasing its grain size), we increase the amount of sample data indexed by each interval designation. Thus, by coarsening the variable, we increase sample sizes and achieve better statistical estimation. In this sense, increasing granularity provides an antidote to the so-called curse of dimensionality, which relates to the exponential decrease in statistical power with increase in number of dimensions or variable cardinality. Independent of prior domain knowledge, it is often the case that meaningful regularities (i.e., which can be detected by a given learning methodology, representational language, etc.) may exist at one level of resolution and not at another. For example, a simple learner or pattern recognition system may seek to extract regularities satisfying a conditional probability threshold such as p ( Y = y j | X = x i ) ≥ α . {\displaystyle p(Y=y_{j}|X=x_{i})\geq \alpha .} In the special case where α = 1 , {\displaystyle \alpha =1,} this recognition system is essentially detecting logical implication of the form X = x i → Y = y j {\displaystyle X=x_{i}\rightarrow Y=y_{j}} or, in words, "if X = x i , {\displaystyle X=x_{i},} then Y = y j {\displaystyle Y=y_{j}} ". The system's ability to recognize such implications (or, in general, conditional probabilities exceeding threshold) is partially contingent on the resolution with which the system analyzes the variables. As an example of this last point, consider the feature space shown to the right. The variables may each be regarded at two different resolutions. Variable X {\displaystyle X} may be regarded at a high (quaternary) resolution wherein it takes on the four values { x 1 , x 2 , x 3 , x 4 } {\displaystyle \{x_{1},x_{2},x_{3},x_{4}\}} or at a lower (binary) resolution wherein it takes on the two values { X 1 , X 2 } . {\displaystyle \{X_{1},X_{2}\}.} Similarly, variable Y {\displaystyle Y} may be regarded at a high (quaternary) resolution or at a lower (binary) resolution, where it takes on the values { y 1 , y 2 , y 3 , y 4 } {\displaystyle \{y_{1},y_{2},y_{3},y_{4}\}} or { Y 1 , Y 2 } , {\displaystyle \{Y_{1},Y_{2}\},} respectively. At the high resolution, there are no detectable implications of the form X = x i → Y = y j , {\displaystyle X=x_{i}\rightarrow Y=y_{j},} since every x i {\displaystyle x_{i}} is associated with more than one y j , {\displaystyle y_{j},} and thus, for all x i , {\displaystyle x_{i},} p ( Y = y j | X = x i ) < 1. {\displaystyle p(Y=y_{j}|X=x_{i})<1.} However, at the low (binary) variable resolution, two bilateral implications become detectable: X = X 1 ↔ Y = Y 1 {\displaystyle X=X_{1}\leftrightarrow Y=Y_{1}} and X = X 2 ↔ Y = Y 2 {\displaystyle X=X_{2}\leftrightarrow Y=Y_{2}} , since every X 1 {\displaystyle X_{1}} occurs iff Y 1 {\displaystyle Y_{1}} and X 2 {\displaystyle X_{2}} occurs iff Y 2 . {\displaystyle Y_{2}.} Thus, a pattern recognition system scanning for implications of this kind would find them at the binary variable resolution, but would fail to find them at the higher quaternary variable resolution. ==== Issues and methods ==== It is not feasible to exhaustively test all possible discretization resolutions on all variables in order to see which combination of resolutions yields interesting or significant results. Instead, the feature space must be preprocessed (often by an entropy analysis of some kind) so that some guidance can be given as to how the discretization process should proceed. Moreover, one cannot generally achieve good results by naively analyzing and discretizing each variable independently, since this may obliterate the very interactions that we had hoped to discover. A sample of papers that address the problem of variable discretization in general, and multiple-variable discretization in particular, is as follows: Chiu, Wong & Cheung (1991), Bay (2001), Liu et al. (2002), Wang & Liu (1998), Zighed, Rabaséda & Rakotomalala (1998), Catlett (1991), Dougherty, Kohavi & Sahami (1995), Monti & Cooper (1999), Fayyad & Irani (1993), Chiu, Cheung & Wong (1990), Nguyen & Nguyen (1998), Grzymala-Busse & Stefanowski (2001), Ting (1994), Ludl & Widmer (2000), Pfahringer (1995), An & Cercone (1999), Chiu & Cheung (1989), Chmielewski & Grzymala-Busse (1996), Lee & Shin (1994), Liu & Wellman (2002), Liu & Wellman (2004). === Variable granulation (clustering/aggregation/transformation) === Variable granulation is a term that could describe a variety of techniques, most of which are aimed at reducing dimensionality, redundancy, and storage requirements. We briefly describe some of the ideas here, and present pointers to the literature. ==== Variable transformation ==== A number of classical methods, such as principal component analysis, multidimensional scaling, factor analysis, and structural equation modeling, and their relatives, fall under the genus of "variable transformation." Also in this category are more modern areas of study such as dimensionality reduction, projection pursuit, and independent component analysis. The common goal of these methods in general is to find a representation of the data in terms of new variables, which are a linear or nonlinear transformation of the original variables, and in which important stati
Adam Tauman Kalai
Adam Tauman Kalai is an American computer scientist who specializes in artificial intelligence and works at OpenAI. == Education and career == Kalai graduated from Harvard University in 1996 with a BA in computer science and received a MA and PhD, both in computer science, from Carnegie Mellon University in 1999 and 2001, respectively. His doctoral advisor was Avrim Blum. After graduation, Kalai did his postdoctoral research at Massachusetts Institute of Technology under Santosh Vempala until 2003. Kalai became a faculty member at the Toyota Technological Institute at Chicago from 2003 to 2006, followed by a stint as an assistant professor at Georgia Institute of Technology from 2007 to 2008. He joined Microsoft Research in 2008 and subsequently moved to OpenAI in 2023. == Contributions == Kalai is known for his algorithm for generating random factored numbers (see Bach's algorithm), for co-inventing the cooperative-competitive value (coco value), for efficiently learning learning mixtures of Gaussians, for the Blum-Kalai-Wasserman algorithm for learning parity with noise, and for the intractability of the folk theorem in game theory. More recently, Kalai is known for identifying and reducing gender bias in word embeddings, which are a representation of words commonly used in AI systems. In 2026, he coauthored a Nature paper on hallucinations in large language models. == Personal life == Kalai is the son of game theorist Ehud Kalai and is married to cryptographer Yael Tauman Kalai.