In formal language theory, the Kleene star (or Kleene operator or Kleene closure) refers to two related unary operations, that can be applied either to an alphabet of symbols or to a formal language, a set of strings (finite sequences of symbols). The Kleene star operator on an alphabet V generates the set V of all finite-length strings over V, that is, finite sequences whose elements belong to V; in mathematics, it is more commonly known as the free monoid construction. The Kleene star operator on a language L generates another language L, the set of all strings that can be obtained as a concatenation of zero or more members of L. In both cases, repetitions are allowed. The Kleene star operators are named after American mathematician Stephen Cole Kleene, who first introduced and widely used it to characterize automata for regular expressions. == Of an alphabet == Given an alphabet V {\displaystyle V} , define V 0 = { ε } {\displaystyle V^{0}=\{\varepsilon \}} (the set consists only of the empty string), V 1 = V , {\displaystyle V^{1}=V,} and define recursively the set V i + 1 = { w v : w ∈ V i and v ∈ V } {\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}} for each i > 0 , {\displaystyle i>0,} where w v {\displaystyle wv} denotes the string obtained by appending the single character v {\displaystyle v} to the end of w {\displaystyle w} . Here, V i {\displaystyle V^{i}} can be understood to be the set of all strings of length exactly i {\displaystyle i} , with characters from V {\displaystyle V} . The definition of Kleene star on V {\displaystyle V} is V ∗ = ⋃ i ≥ 0 V i = V 0 ∪ V 1 ∪ V 2 ∪ V 3 ∪ V 4 ∪ ⋯ . {\displaystyle V^{}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .} == Of a language == Given a language L {\displaystyle L} (any finite or infinite set of strings), define L 0 = { ε } {\displaystyle L^{0}=\{\varepsilon \}} (the language consisting only of the empty string), L 1 = L , {\displaystyle L^{1}=L,} and define recursively the set L i + 1 = { w v : w ∈ L i and v ∈ L } {\displaystyle L^{i+1}=\{wv:w\in L^{i}{\text{ and }}v\in L\}} for each i > 0 , {\displaystyle i>0,} where w v {\displaystyle wv} denotes the string obtained by concatenating w {\displaystyle w} and v {\displaystyle v} . Here, L i {\displaystyle L^{i}} can be understood to be the set of all strings that can be obtained by concatenating exactly i {\displaystyle i} strings from L {\displaystyle L} , allowing repetitions. The definition of Kleene star on L {\displaystyle L} is L ∗ = ⋃ i ≥ 0 L i = L 0 ∪ L 1 ∪ L 2 ∪ L 3 ∪ L 4 ∪ ⋯ . {\displaystyle L^{}=\bigcup _{i\geq 0}L^{i}=L^{0}\cup L^{1}\cup L^{2}\cup L^{3}\cup L^{4}\cup \cdots .} == Kleene plus == In some formal language studies, (e.g. AFL theory) a variation on the Kleene star operation called the Kleene plus is used. The Kleene plus omits the V 0 {\displaystyle V^{0}} or L 0 {\displaystyle L^{0}} term in the above unions. In other words, the Kleene plus on V {\displaystyle V} is V + = ⋃ i ≥ 1 V i = V 1 ∪ V 2 ∪ V 3 ∪ ⋯ , {\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots ,} or V + = V ∗ V . {\displaystyle V^{+}=V^{}V.} == Examples == Example of Kleene star applied to a set of strings: {"ab","c"} = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}. Example of Kleene star applied to a set of strings without the prefix property: {"a","ab","b"} = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...};In this example, the string "aab" can be obtained in two different ways. The Sardinas-Patterson algorithm can be used to check for a given V whether any member of V can be obtained in more than one way. Example of Kleene and Kleene plus applied to a set of characters (following the C programming language convention where a character is denoted by single quotes and a string is denoted by double quotes): {'a', 'b', 'c'} = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}. {'a', 'b', 'c'}+ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}. == Properties == If V {\displaystyle V} is any finite or countably infinite set of characters, then V ∗ {\displaystyle V^{}} is a countably infinite set. As a result, each formal language over a finite or countably infinite alphabet Σ {\displaystyle \Sigma } is countable, since it is a subset of the countably infinite set Σ ∗ {\displaystyle \Sigma ^{}} . ( L ∗ ) ∗ = L ∗ {\displaystyle (L^{})^{}=L^{}} , which means that the Kleene star operator is an idempotent unary operator, as ( L ∗ ) i = L ∗ {\displaystyle (L^{})^{i}=L^{}} for every i ≥ 1 {\displaystyle i\geq 1} . V ∗ = { ε } {\displaystyle V^{}=\{\varepsilon \}} , if V {\displaystyle V} is the empty set ∅. For the version of the Kleene star operator on languages, L ∗ = { ε } {\displaystyle L^{}=\{\varepsilon \}} when L {\displaystyle L} is either the empty set ∅ or the singleton set { ε } {\displaystyle \{\varepsilon \}} . == Generalization == Strings form a monoid with concatenation as the binary operation and ε the identity element. In addition to strings, the Kleene star is defined for any monoid. More precisely, let (M, ⋅) be a monoid, and S ⊆ M. Then S is the smallest submonoid of M containing S; that is, S contains the neutral element of M, the set S, and is such that if x,y ∈ S, then x⋅y ∈ S. Furthermore, the Kleene star is generalized by including the -operation (and the union) in the algebraic structure itself by the notion of complete star semiring.
Inductive probability
Inductive probability attempts to give the probability of future events based on past events. It is the basis for inductive reasoning, and gives the mathematical basis for learning and the perception of patterns. It is a source of knowledge about the world. There are three sources of knowledge: inference, communication, and deduction. Communication relays information found using other methods. Deduction establishes new facts based on existing facts. Inference establishes new facts from data. Its basis is Bayes' theorem. Information describing the world is written in a language. For example, a simple mathematical language of propositions may be chosen. Sentences may be written down in this language as strings of characters. But in the computer it is possible to encode these sentences as strings of bits (1s and 0s). Then the language may be encoded so that the most commonly used sentences are the shortest. This internal language implicitly represents probabilities of statements. Occam's razor says the "simplest theory, consistent with the data is most likely to be correct". The "simplest theory" is interpreted as the representation of the theory written in this internal language. The theory with the shortest encoding in this internal language is most likely to be correct. == History == Probability and statistics was focused on probability distributions and tests of significance. Probability was formal, well defined, but limited in scope. In particular its application was limited to situations that could be defined as an experiment or trial, with a well defined population. Bayes's theorem is named after Rev. Thomas Bayes 1701–1761. Bayesian inference broadened the application of probability to many situations where a population was not well defined. But Bayes' theorem always depended on prior probabilities, to generate new probabilities. It was unclear where these prior probabilities should come from. Ray Solomonoff developed algorithmic probability which gave an explanation for what randomness is and how patterns in the data may be represented by computer programs, that give shorter representations of the data circa 1964. Chris Wallace and D. M. Boulton developed minimum message length circa 1968. Later Jorma Rissanen developed the minimum description length circa 1978. These methods allow information theory to be related to probability, in a way that can be compared to the application of Bayes' theorem, but which give a source and explanation for the role of prior probabilities. Marcus Hutter combined decision theory with the work of Ray Solomonoff and Andrey Kolmogorov to give a theory for the Pareto optimal behavior for an Intelligent agent, circa 1998. === Minimum description/message length === The program with the shortest length that matches the data is the most likely to predict future data. This is the thesis behind the minimum message length and minimum description length methods. At first sight Bayes' theorem appears different from the minimimum message/description length principle. At closer inspection it turns out to be the same. Bayes' theorem is about conditional probabilities, and states the probability that event B happens if firstly event A happens: P ( A ∧ B ) = P ( B ) ⋅ P ( A | B ) = P ( A ) ⋅ P ( B | A ) {\displaystyle P(A\land B)=P(B)\cdot P(A|B)=P(A)\cdot P(B|A)} becomes in terms of message length L, L ( A ∧ B ) = L ( B ) + L ( A | B ) = L ( A ) + L ( B | A ) . {\displaystyle L(A\land B)=L(B)+L(A|B)=L(A)+L(B|A).} This means that if all the information is given describing an event then the length of the information may be used to give the raw probability of the event. So if the information describing the occurrence of A is given, along with the information describing B given A, then all the information describing A and B has been given. ==== Overfitting ==== Overfitting occurs when the model matches the random noise and not the pattern in the data. For example, take the situation where a curve is fitted to a set of points. If a polynomial with many terms is fitted then it can more closely represent the data. Then the fit will be better, and the information needed to describe the deviations from the fitted curve will be smaller. Smaller information length means higher probability. However, the information needed to describe the curve must also be considered. The total information for a curve with many terms may be greater than for a curve with fewer terms, that has not as good a fit, but needs less information to describe the polynomial. === Inference based on program complexity === Solomonoff's theory of inductive inference is also inductive inference. A bit string x is observed. Then consider all programs that generate strings starting with x. Cast in the form of inductive inference, the programs are theories that imply the observation of the bit string x. The method used here to give probabilities for inductive inference is based on Solomonoff's theory of inductive inference. ==== Detecting patterns in the data ==== If all the bits are 1, then people infer that there is a bias in the coin and that it is more likely also that the next bit is 1 also. This is described as learning from, or detecting a pattern in the data. Such a pattern may be represented by a computer program. A short computer program may be written that produces a series of bits which are all 1. If the length of the program K is L ( K ) {\displaystyle L(K)} bits then its prior probability is, P ( K ) = 2 − L ( K ) {\displaystyle P(K)=2^{-L(K)}} The length of the shortest program that represents the string of bits is called the Kolmogorov complexity. Kolmogorov complexity is not computable. This is related to the halting problem. When searching for the shortest program some programs may go into an infinite loop. ==== Considering all theories ==== The Greek philosopher Epicurus is quoted as saying "If more than one theory is consistent with the observations, keep all theories". As in a crime novel all theories must be considered in determining the likely murderer, so with inductive probability all programs must be considered in determining the likely future bits arising from the stream of bits. Programs that are already longer than n have no predictive power. The raw (or prior) probability that the pattern of bits is random (has no pattern) is 2 − n {\displaystyle 2^{-n}} . Each program that produces the sequence of bits, but is shorter than the n is a theory/pattern about the bits with a probability of 2 − k {\displaystyle 2^{-k}} where k is the length of the program. The probability of receiving a sequence of bits y after receiving a series of bits x is then the conditional probability of receiving y given x, which is the probability of x with y appended, divided by the probability of x. ==== Universal priors ==== The programming language affects the predictions of the next bit in the string. The language acts as a prior probability. This is particularly a problem where the programming language codes for numbers and other data types. Intuitively we think that 0 and 1 are simple numbers, and that prime numbers are somehow more complex than numbers that may be composite. Using the Kolmogorov complexity gives an unbiased estimate (a universal prior) of the prior probability of a number. As a thought experiment an intelligent agent may be fitted with a data input device giving a series of numbers, after applying some transformation function to the raw numbers. Another agent might have the same input device with a different transformation function. The agents do not see or know about these transformation functions. Then there appears no rational basis for preferring one function over another. A universal prior insures that although two agents may have different initial probability distributions for the data input, the difference will be bounded by a constant. So universal priors do not eliminate an initial bias, but they reduce and limit it. Whenever we describe an event in a language, either using a natural language or other, the language has encoded in it our prior expectations. So some reliance on prior probabilities are inevitable. A problem arises where an intelligent agent's prior expectations interact with the environment to form a self reinforcing feed back loop. This is the problem of bias or prejudice. Universal priors reduce but do not eliminate this problem. === Universal artificial intelligence === The theory of universal artificial intelligence applies decision theory to inductive probabilities. The theory shows how the best actions to optimize a reward function may be chosen. The result is a theoretical model of intelligence. It is a fundamental theory of intelligence, which optimizes the agents behavior in, Exploring the environment; performing actions to get responses that broaden the agents knowledge. Competing or co-operating with another agent; games. Balancing short and long term rewards. In general no agent will always provi
Type–token distinction
The type–token distinction is the difference between a type of objects (analogous to a class) and the individual tokens of that type (analogous to instances). Since each type may be instantiated by multiple tokens, there are generally more tokens than types of an object. For example, the sentence "A rose is a rose is a rose" contains three word types: three word tokens of the type a, two word tokens of the type is, and three word tokens of the type rose. The distinction is important in disciplines such as logic, linguistics, metalogic, typography, and computer programming. == Overview == The type–token distinction separates types (abstract descriptive concepts) from tokens (objects that instantiate concepts). For example, in the sentence "the bicycle is becoming more popular" the word bicycle represents the abstract concept of bicycles and this abstract concept is a type, whereas in the sentence "the bicycle is in the garage", it represents a particular object and this particular object is a token. Similarly, the word type 'letter' uses only four letter types: L, E, T and R. Nevertheless, it uses both E and T twice. One can say that the word type 'letter' has six letter tokens, with two tokens each of the letter types E and T. Whenever a word type is inscribed, the number of letter tokens created equals the number of letter occurrences in the word type. Some logicians consider a word type to be the class of its tokens. Other logicians counter that the word type has a permanence and constancy not found in the class of its tokens. The type remains the same while the class of its tokens is continually gaining new members and losing old members. == Typography == In typography, the type–token distinction is used to determine the presence of a text printed by movable type: The defining criteria which a typographic print has to fulfill is that of the type identity of the various letter forms which make up the printed text. In other words: each letter form which appears in the text has to be shown as a particular instance ("token") of one and the same type which contains a reverse image of the printed letter. == Charles Sanders Peirce == The distinctions between using words as types or tokens were first made by American logician and philosopher Charles Sanders Peirce in 1906 using terminology that he established. Peirce's type–token distinction applies to words, sentences, paragraphs and so on: to anything in a universe of discourse of character-string theory, or concatenation theory. Peirce's original words are the following: A common mode of estimating the amount of matter in a ... printed book is to count the number of words. There will ordinarily be about twenty 'thes' on a page, and, of course, they count as twenty words. In another sense of the word 'word,' however, there is but one word 'the' in the English language; and it is impossible that this word should lie visibly on a page, or be heard in any voice .... Such a ... Form, I propose to term a Type. A Single ... Object ... such as this or that word on a single line of a single page of a single copy of a book, I will venture to call a Token. .... In order that a Type may be used, it has to be embodied in a Token which shall be a sign of the Type, and thereby of the object the Type signifies.
MacSpeech Scribe
MacSpeech Scribe is speech recognition software for Mac OS X designed specifically for transcription of recorded voice dictation. It runs on Mac OS X 10.6 Snow Leopard. The software transcribes dictation recorded by an individual speaker. Typically, the speaker will record their dictation using a digital recording device such as a handheld digital recorder, mobile smartphone (e.g. iPhone), or desktop or laptop computer with a suitable microphone. MacSpeech Scribe supports specific audio file formats for recorded dictation: .aif, .aiff, .wav, .mp4, .m4a, and .m4v. MacSpeech Scribe was originally developed by MacSpeech, Inc. and released February 11, 2010, at Macworld Expo in San Francisco. The product is now owned by Nuance Communications which acquired MacSpeech on February 16, 2010. Nuance is the developer of other speech recognition products including Dragon NaturallySpeaking for Windows, Dragon Dictate for Mac (formerly "MacSpeech Dictate"), and Dragon Dictation apps for iOS. Jeffery Battersby of Macworld noted in his September 2010 review of MacSpeech Scribe, v1.1: Small foibles aside, MacSpeech Scribe is a powerful and intelligent tool for transcribing your recorded speech. A simple training process and access to a wide variety of standard audio formats mean that you’ll be moving your spoken text to the printed page in a matter of minutes and with a minimum of hassle. Scribe is the best, simplest way for you to get your spoken word to the printed page. == Release history ==
Intelligent Robotics Group
The Intelligent Robotics Group (IRG) is a research organization within the Intelligent Systems Division at the NASA Ames Research Center in California's Silicon Valley. IRG conducts applied research in the area of robotics and autonomy and is one of the principal organizations at NASA responsible for robotics expertise, along with groups at the Jet Propulsion Laboratory and Johnson Space Center. The group's portfolio includes robotics in support of human exploration, perception and navigation, user interfaces, software architectures, and simulation. IRG developed the Astrobee free-flying robots on the International Space Station and was a primary contributor to the VIPER lunar rover in the areas of flight software, navigation, simulation, and mission operations. IRG has also conducted many robotic field test campaigns in support of spaceflight mission concept developments. These experiences led to the commercialization of the GigaPan system in collaboration with Carnegie Mellon University.
Contrast-to-noise ratio
Contrast-to-noise ratio (CNR) is a measure used to determine image quality. CNR is similar to the metric signal-to-noise ratio (SNR), but subtracts a term before taking the ratio. This is important when there is a significant bias in an image, such as from haze. As can be seen in the picture at right, the intensity is rather high even though the features of the image are washed out by the haze. Thus this image may have a high SNR metric, but will have a low CNR metric. One way to define contrast-to-noise ratio is: C = | S A − S B | σ o {\displaystyle C={\frac {|S_{A}-S_{B}|}{\sigma _{o}}}} where SA and SB are signal intensities for signal producing structures A and B in the region of interest and σo is the standard deviation of the pure image noise.
Mustafa Suleyman
Mustafa Suleyman (born in August 1984) is a British artificial intelligence (AI) entrepreneur. He is the CEO of Microsoft AI, and the co-founder and former head of applied AI at DeepMind, an AI company which was acquired by Google. After leaving DeepMind, he co-founded Inflection AI, a machine learning and generative AI company, in 2022. == Early life and education == Suleyman's Syrian father worked as a taxi driver and his English mother was a nurse. He grew up off Caledonian Road, London, where he lived with his parents and his two younger brothers. Suleyman went to Thornhill Primary School, a state school in Islington, followed by Queen Elizabeth's School, Barnet, a boys' grammar school. Around that time, he met his DeepMind co-founder, Demis Hassabis, through his best friend, who was Demis's younger brother. Suleyman shared that he and Hassabis often discussed how they could make a positive impact on the world. Suleyman enrolled to study philosophy and theology at the University of Oxford where he was an undergraduate student at Mansfield College, Oxford, before dropping out at 19. == Career == In August 2001, while still a teenager and a "strong atheist", Suleyman helped Mohammed Mamdani establish a telephone counselling service called the Muslim Youth Helpline. The organization would later become one of the largest mental health support services. Suleyman subsequently worked as a policy officer on human rights for Ken Livingstone, the Mayor of London, before going on to start Reos Partners, a "systemic change" consultancy that uses methods from conflict resolution to navigate social problems. As a negotiator and facilitator, Mustafa worked for a wide range of clients such as the United Nations, the Dutch government, and the World Wide Fund for Nature. === DeepMind and Google === In 2010 Suleyman co-founded DeepMind Technologies, an artificial intelligence (AI) and machine learning company, and became its chief product officer. The company quickly established itself as one of the leaders in the AI sector. In 2014 DeepMind was acquired by Google for a reported £400 million, the company's largest acquisition in Europe at that time. Following the acquisition, Suleyman became head of applied AI at DeepMind, taking on responsibility for integrating the company's technology across a wide range of Google products. In February 2016 Suleyman launched DeepMind Health at the Royal Society of Medicine. DeepMind Health builds clinician-led technology for the National Health Service (NHS) and other partners to improve frontline healthcare services. Under Suleyman, DeepMind also developed research collaborations with healthcare organizations in the United Kingdom, including Moorfields Eye Hospital NHS foundation trust. In 2016, Suleyman led an effort to apply DeepMind's machine learning algorithms to help reduce the energy required to cool Google's data centres. The system evaluated the billions of possible combinations of actions that the data centre operators could take, and came up with recommendations based on the predicted power usage. The system discovered novel methods of cooling, leading to a reduction of up to 40% of the amount of energy used for cooling, and a 15% improvement in the buildings' overall energy efficiency. Since June 2019, Suleyman has served on the board of The Economist Group, which publishes The Economist newspaper. In August 2019, Suleyman was placed on administrative leave following allegations of bullying employees. The company hired an external lawyer to investigate, and shortly thereafter Suleyman left to take a VP role at parent company Google. An email circulated by DeepMind's leadership to staff after the story broke, as well as additional details published by Business Insider, said Suleyman's "management style fell short" of expected standards. In December 2019, Suleyman announced he would be leaving DeepMind to join Google, working in a policy role. === Inflection AI === Suleyman left Google in January 2022 and joined Greylock Partners as a venture partner and in March 2022, Suleyman co-founded Inflection AI, a new AI lab venture with Greylock's Reid Hoffman. The company was founded with the goal of leveraging "AI to help humans 'talk' to computers," recruited former staff from companies such as Google and Meta and raised $225 million in its first funding round. In 2023, Inflection AI launched a chatbot named “Pi” for Personal Intelligence. The bot “remembers” past conversations and seems to get to know its users over time. According to Suleyman, the long-term goal for Pi is to be a digital “Chief of Staff”, with the initial design focused on maintaining conversational dialogue with users, asking questions, and offering emotional support. === Microsoft AI === In March 2024, Microsoft appointed Suleyman as Executive Vice President (EVP) and CEO of its newly created consumer AI unit, Microsoft AI. Several members of Inflection AI's team were also appointed to the division, including co-founder Karen Simonyan. === Awards and honours === Suleyman was appointed a Commander of the British Empire (CBE) in the 2019 New Year Honours. Suleyman was named by Time as one of the 100 most influential people in artificial intelligence in 2023 and in 2024. === Views on AI ethics === Suleyman is prominent in the debate over the ethics of AI and has spoken widely about the need for companies, governments and civil society to join in holding technologists accountable for the impacts of their work. He has advocated redesigning incentives in the technology industry to steer business leaders toward prioritising social responsibility alongside their fiduciary duties. Within DeepMind he set up a research unit called DeepMind Ethics & Society to study the real-world impacts of AI and help technologists put ethics into practice. Suleyman is also a founding co-chair of the Partnership on AI – an organisation that includes representatives from companies such as Amazon, Apple, DeepMind, Meta, Google, IBM, and Microsoft. The organisation studies and formulates best practices for AI technologies, advances the public's understanding of AI, and serves as an open platform for discussion and engagement about AI and how it affects people and society. Its board of directors has equal representation from non-profit and for profit entities. In September 2023, Suleyman, in collaboration with researcher Michael Bhaskar, published The Coming Wave, Technology, Power and the 21st Century's Greatest Dilemma, a book that examines the transformative and potentially perilous impact of advanced technologies, particularly AI and synthetic biology. According to Suleyman, AI notably has the potential to bring "radical abundance", address climate change and empower people with its cheap problem-solving capabilities. But it may also improve its own design and manufacturing processes, leading to a period of dangerously rapid AI progress. And it could enable catastrophic misuse, from bioengineered pathogens to autonomous weapons, making global oversight and containment essential to avoid unintended consequences. It was shortlisted for the 2023 Financial Times Business Book of the Year Award. In June 2024, in an interview with Andrew Ross Sorkin at the Aspen Ideas Festival, Suleyman expressed the view that unless a website explicitly specifies otherwise, for "content that is already on the open web, the social contract of that content since the 90s has been that it is fair use. Anyone can copy it, recreate with it, reproduce with it. That has been freeware, if you like. That's been the understanding." The statement sparked controversy over the use of Internet data for training AI models. == Personal life == A Business Insider profile in 2017 described Suleyman as being liberal.