Learning from Data on Its Own

Hinton and colleagues present a way to train a deep neural network “one layer at a time”. It is seen as an important step toward “deep learning”

Neural networks with many stacked layers could not be trained well by backpropagation alone. Hinton and colleagues showed a method in which, first, one layer at a time and without being given correct answers, the network learns the “features” of the data (pre-training), and then the whole network is adjusted by backpropagation. It reached an error rate of 1.25% on the handwritten digits of MNIST (the Neural Computation paper), and it was also better than earlier methods at representing images and documents with a small number of values (the Science paper).

Bayes’s essay: in 1763 his friend Price finds the manuscript among his papers and sends it to the Royal Society

Bayes’ theorem is the idea of recalculating how likely a cause or hypothesis is after seeing a result (evidence). It is the foundation of naive Bayes classification. On December 23, 1763, a paper was read at the Royal Society in the form of a letter from Price to the member John Canton. It was “An Essay towards solving a Problem in the Doctrine of Chances”, which Price had found among the papers of his late friend Bayes, and it was printed in the society’s journal Philosophical Transactions, volume 53 (from page 370). According to Price’s letter, Bayes’s aim was to find a method for judging the probability that an event will happen, when all we know is how many times it has happened and how many times it has failed, and nothing else.

Naive Bayes classifies documents — in 1961, Maron runs an experiment guessing the field of a paper from clue words by probability. He himself wrote that the assumption that words are independent is not correct

Naive Bayes classification is a method that, from the clue words contained in a document, uses Bayes' theorem to calculate the probability that the document belongs to each field, and puts it in the field with the highest probability. It assumes that once the field is fixed, the words appear independently of one another, so the calculation can be done by simply multiplying the probabilities of the individual words. In his 1961 paper “Automatic Indexing: An Experimental Inquiry”, M. E. Maron (The RAND Corporation) ran an experiment using 405 abstracts from 1959 issues of the computer journal IRE Transactions on Electronic Computers. The 260 abstracts from the March and June issues served as training data, used to count the relationship between words and fields. The 145 abstracts from the September issue were left completely unseen during preparation and were used later as test data. There were 32 fields and 90 clue words. Among the 85 test abstracts that contained two or more clue words, the top-ranked field was correct for 44 (51.8%), and the correct field was within the top three for 68 (80%).

What we still don’t know:This 1961 experiment separated training data from test data by leaving the 145 test abstracts completely unseen during preparation. The paper's numbers also show that the accuracy on new documents (51.8%) is much lower than the accuracy on the documents used for training (84.6% with the top-ranked field correct).

Least squares: Legendre announces it in the appendix of a book in 1805, and Gauss claims in 1809 that he had used it since 1795 (the most famous priority dispute in the history of statistics)

The method of least squares is a way of choosing the constants of a formula (for a straight line, the slope and intercept) so that, when you square each error between the measured values and the values calculated from the formula and add them all up, the total is as small as possible. In 1805 Legendre (A. M. Legendre) published a book in Paris on determining the orbits of comets, “Nouvelles méthodes pour la détermination des orbites des comètes”. In its appendix “Sur la Méthode des moindres quarrés” (on the method of least squares) he wrote that when there are more equations than unknowns the errors cannot all be made zero, and that making the sum of the squares of the errors as small as possible is the most general, most accurate and most practical choice. He also noted that this balances the errors against one another and guards against the effect of extreme errors. In Section 186 of his book on the motion of the heavenly bodies, “Theoria motus corporum coelestium”, published in Hamburg in 1809, Gauss (C. F. Gauss) wrote that the principle of minimizing the sum of the squares of the differences was one he and others had used since 1795, and that Legendre had recently published it too. Stigler, who re-examined the history in 1981, calls this the most famous priority dispute in the history of statistics.

What we still don’t know:Whether Gauss really used it in 1795 is not settled. In Gauss’s later testimony the year is sometimes given as 1794, so the date is uncertain. Stigler writes that it might be possible to check using data from the French meridian survey.

The logistic function (S-shaped curve): in 1838 Verhulst publishes it as an equation for how a population grows; it gets its name in 1845

The logistic function is an equation that grows at nearly a doubling pace at first but slows as it nears an upper limit, drawing an S shape. In later logistic regression, this S shape is used to express a probability (a number between 0 and 1). In 1838, in a short paper in volume 10 of the journal “Correspondance mathématique et physique”, edited by Quetelet, Verhulst (P.-F. Verhulst) expressed the speed at which a population p grows by the equation dp/dt = mp − np². It is the doubling term mp minus a brake np² that acts more strongly the larger the population is. From the solution of this equation, the population approaches an upper limit m/n as time passes. He compared it with population data for France, Belgium, Essex and Russia, and wrote that this work was completed in 1833 and that he published it on Quetelet’s advice. He also noted that when the form of the brake was changed to np³, np⁴ or n log p, the error against the observations was almost the same, but the value of the upper limit changed greatly.

What we still don’t know:Verhulst himself pointed out that even when the form of the brake was changed in various ways, the error against the observations stayed about the same, while the forecast of the upper limit changed greatly. He concluded that only the future can reveal the true form of the brake. The problem that a small amount of data cannot settle which equation is correct leads to the later discussion of model selection (AIC and so on).

Logistic regression — in 1958 D. R. Cox publishes a regression for 0-and-1 data; he himself said he did not know who did it first

Logistic regression is a method for data where the answer is 1 or 0, such as yes or no, and it predicts the probability of getting 1 from explanatory variables such as age. Ordinary linear regression can predict values below 0 or above 1, but with the S-shaped logistic curve the prediction always stays between 0 and 1, and the result can be read as an odds ratio (a ratio of how likely something is to happen). In his July 1958 paper “The Regression Analysis of Binary Sequences”, D. R. Cox (affiliation given in the paper: Birkbeck College, University of London) dealt with tests and estimation for the case where a sequence of 0s and 1s is observed and the probability of getting a 1 is thought to depend on one or more explanatory variables. The abstract says there is a fair amount of earlier work, which the paper also reviews. In a 1994 interview, Cox said his aim was to build a systematic framework, similar to least-squares regression, for analyzing 0-and-1 data, and that one thing that prompted it was the strong interest of experimental psychologists at Birkbeck College in analyzing 0-and-1 data.

What we still don’t know:Who first used logistic regression is not clear even from the people involved. Cox named Cornfield, but also said he does not remember whether he was influenced by him.

The prototype of principal component analysis: in 1901 Pearson shows that the line closest to a cloud of points runs along the longest axis of the spread of the points

Karl Pearson of University College, London dealt with the problem of finding the line or plane that best fits a cloud of points in a plane or in a space of three or more dimensions. In ordinary least squares (regression analysis, which assumes error only in y and makes the vertical gaps small), the line comes out different depending on whether x or y is taken as the base. Pearson said that when x and y both contain measurement error equally, one should minimize the sum of the squares of the lengths of the perpendiculars dropped from the points to the line. He then showed that this line passes through the center of gravity and runs along the longest axis of the ellipsoid that describes how the points are scattered. This corresponds to the direction of the first principal component in modern principal component analysis (a method of expressing many sets of numbers by a few numbers taken in order from the direction with the largest variation). The paper has a numerical example with 10 points: the slope of the closest line is −0.546, that of the regression line predicting y from x is −0.5396, and that predicting x from y is −0.5659, showing that the three lines differ.

Principal component analysis: in 1933 Hotelling names “the method of principal components”, a way to express many numbers, such as test scores, by a few components taken in order of how much they vary

Harold Hotelling of Columbia University considered that behind many variables that are related to one another, such as children’s scores on arithmetic-speed and reading tests, there are fewer basic quantities that are unrelated to each other, and he showed a method for extracting them. First take the one component that explains the most of the variation in all the variables, then take, in turn, from the components unrelated to it, the one that best explains the remaining variation. Components with small effects can be thrown away. He named this “the method of principal components”, and explained that it is the same as aligning the coordinate axes with the principal axes of the ellipsoid of the distribution of points. What psychology called “mental factors” can also be used in fields outside psychology (such as the properties of utility poles and exchange rates), and he writes that he chose to call them components so as not to clash with the mathematical word factor.

What we still don’t know:We have not checked on this site whether Hotelling knew Pearson’s 1901 paper (the copy we saved is machine-read text, and we have not read all the pages).

Quantification theory: in 1950 Chikio Hayashi writes up a method of giving numbers to qualitative data in order to predict parole

Chikio Hayashi of the Institute of Statistical Mathematics, as the 1948 survey of Japanese literacy was nearing its end, was consulted by a criminal law scholar at the Ministry of Justice training institute for corrections and parole. The request was to make the judgment of whether prisoners who had served a third of their sentence could be paroled statistically more reliable. The earlier method assigned scores such as −2, −1, 0, 1, 2 to the answers on each item by human judgment and added them up. Hayashi visited Yokohama Prison, where he heard that model prisoners who adapted well to prison life and worked hard would come back soon after release. He also read that very rebellious people were likely to reoffend, and that people in the middle were the least likely to. He saw that evaluation scores do not always line up in one simple direction. So he got the idea of deciding from the data the very numbers to assign to each answer (qualitative data), so that the group that did not reoffend and the group that did are separated most clearly. In his English paper of 1950 he set this up as a problem of maximizing the success rate of prediction. Hayashi then developed methods for field problems one by one, such as the literacy survey, a survey of human relations among track maintenance workers of Japanese National Railways, and a survey on the label design of canned goods for export, and these came to be called quantification theory together.

What we still don’t know:We have not confirmed on this site how much the numbers (weights) Hayashi made actually changed parole decisions (whether they were used in the field).

The beginning of k-nearest neighbors: in 1951 Fix and Hodges devise it in a US Air Force report (it was never made into a journal paper)

The k-nearest neighbors method (k-NN) finds the k labeled data points closest to a new point you want to classify, and assigns the point to the group that is the majority among them. Because it does not fix the distribution of the data in advance, it is called a nonparametric method. In February 1951, E. Fix and J. L. Hodges, Jr. devised this kind of rule in a report of the USAF School of Aviation Medicine (Randolph Field, Texas), “Discriminatory analysis, nonparametric discrimination”. They showed that if k is increased as the number of data points n increases, and k/n is made to approach 0, the rule is consistent (the more data there is, the closer it comes to the optimal classification). This is how the 1967 paper of Cover and Hart introduces it.

What we still don’t know:We have not yet opened and checked the original 1951 report on this site. The content is based on the introductions in the 1967 paper and in an explanatory article.

A theoretical guarantee for the nearest neighbor method — in 1967, Cover and Hart prove that even a classifier that just matches the single nearest point has an error rate no more than twice the theoretical minimum

The nearest neighbor method (the k-nearest-neighbor method with k=1) is a technique that puts a new data point into the same class (group) as the nearest already-classified point. In their January 1967 paper “Nearest Neighbor Pattern Classification”, T. M. Cover (Stanford University) and P. E. Hart (Stanford Research Institute) showed that when there are enough classified points, the error rate R of this method cannot be smaller than R*, the minimum error rate when the distribution is perfectly known (the Bayes error rate), but does not exceed twice R* (with M the number of classes, R* ≤ R ≤ R*(2 − MR*/(M − 1))). The paper writes that, in this sense, half of the classification information in infinite data is contained in the single nearest point.

What we still don’t know:This theoretical guarantee is about the case where there is plenty of data (in the paper's words, a large sample), and it says nothing about performance when data is scarce.

The seed of k-means — in 1957, Lloyd at Bell Laboratories writes down a procedure for finding the best way to represent a signal with a small set of representative values (it appeared in a journal only in 1982)

Lloyd of Bell Laboratories thought about PCM (pulse-code modulation: a way of sending a signal by replacing its voltage with one of a fixed number of representative values). The problem is to find the boundaries and representative values that make the mean of the squared error from the original signal (quantization noise) as small as possible. The procedure he called Method I alternates two steps: (1) fix the boundaries and take the centroid (average) of each interval as its representative value, (2) make the exact midpoint between neighboring representative values the new boundary. This has the same form as one-dimensional k-means (a procedure that repeats two steps: sort points into the group of the nearest representative, then move each representative to the average of its group). The manuscript was circulated inside Bell Laboratories in 1957, and part of it was presented at a meeting of a statistics society that September, but it appeared in a journal only about 25 years later, in 1982.

What we still don’t know:The 1957 manuscript itself (an internal Bell Laboratories record) has not been made public, and this site has only checked it through the note added to the 1982 paper. How much was presented at the 1957 meeting is not known.

k-means — in 1967, MacQueen names a procedure for splitting points into k groups k-means (k means)

J. MacQueen of the University of California, Los Angeles gave the name k-means to a procedure for dividing data (points) into k groups so that the scatter within the groups (the sum of squared distances from the mean) is small. In his procedure, the first k points each become a group of their own. After that, new points are added one at a time to the group whose mean is nearest, and that group's mean is updated right away. Because at every stage the k means are the means of the groups, he called it k-means. In the same paper MacQueen also describes the form that is often presented today as the k-means procedure (repeat two steps: reassign all points to the group of the nearest mean → recompute each group's mean). He says this is a method that Forgy and Jennrich each noticed separately and told him about around 1963.

What we still don’t know:It is known that several researchers independently arrived at the same procedure, but this site has not confirmed how much information passed between them (for example, who had read Lloyd's 1957 manuscript).

Hierarchical clustering — in 1958, Sokal and Michener group 97 species of bees into a tree diagram by similarity

Sokal and Michener of the Department of Entomology at the University of Kansas classified 97 species of solitary bees of the leafcutter bee family. They compared 122 characters per species (traits such as whether the abdomen is red or black) and expressed how alike species were with a correlation coefficient (a number showing how closely two lists of numbers rise and fall together). They then grouped similar species and joined the resulting groups step by step, summarizing everything in a tree diagram. This is the idea behind today's hierarchical clustering (a method that merges the closest items first and builds a tree of nested groups). Earlier classification gave weights to a few characters by human judgment, but the two men treated many characters with equal weight. For the calculations they used IBM punch-card machines and people operating desk calculators (the paper calls these human calculators “computer”), and the correlation coefficients alone took 160 person-hours. The two also wrote that a digital computer of the time could do it in under an hour.

What we still don’t know:The idea of merging similar items step by step to build a tree is said to have appeared in other fields around the same time, but this site has not opened those original papers and has not confirmed it. Which came first has not been decided.

Ward's method — in 1963, Ward presents hierarchical clustering that picks an objective function and merges two groups at a time

Joe H. Ward Jr. of the Aerospace Medical Division at Lackland Air Force Base presented a procedure for dividing people or objects into similar groups (clusters) in large surveys of more than 100. Starting with n groups (at first, one item each), it examines all n(n−1)/2 ways of joining two of them, and merges the two for which the objective function (a number showing how good the grouping is; the analyst chooses it to suit the purpose) comes out best, leaving n−1 groups. Repeating this until only one group remains shows the whole hierarchical structure and the amount of information lost at each stage. In the paper's example, if the scores of 10 people, 2, 6, 5, 6, 2, 2, 2, 0, 0, 0, are represented as one group by their mean, the error sum of squares (the total of the squared deviations from the mean) is 50.5, but if they are divided into the four groups {0,0,0} {2,2,2,2} {5} {6,6}, it is 0.

What we still don’t know:This site checked the first two pages of the paper (p.236-237). It has not read the details of the flow chart and numerical example (p.238 onward).

The hidden Markov model — in 1966, Baum and Petrie work out the mathematics of a model in which unseen states change and symbols come out of them

Leonard E. Baum and Petrie of the Institute for Defense Analyses in Princeton considered a certain probabilistic model. In it, states that cannot be seen from outside move as a Markov chain (a sequence of changes in which the next state is determined probabilistically by the current state alone), and each state emits symbols probabilistically. They called this a probabilistic function of a Markov chain. They then proved that from the observed symbol sequence Y1, …, YT alone, one can estimate the table A of state transition probabilities and the table B of symbol emission probabilities, and that as data increases, maximum likelihood estimation (choosing the values that make the data most likely) approaches the correct values. This is one of the mathematical beginnings of today's hidden Markov model (HMM). In 1970 the same group (Baum with Petrie, Soules and Weiss) presented an iterative calculation that raises the likelihood step by step. Dempster and colleagues wrote in 1977 that this was a special case of the EM algorithm.

What we still don’t know:This site has not confirmed who first used the name hidden Markov model, or in what year. The sources also do not say for what purpose this research was carried out at the Institute for Defense Analyses.

Speech recognition with hidden Markov models — Baker began using them in 1975 and Jelinek of IBM in 1976, and Rabiner's 1989 tutorial made them widely known

Even for the same word, speech varies with the person and the speaking speed. In 1975, J. Baker, in the speech understanding system DRAGON, expressed various kinds of linguistic knowledge in a single form, a probabilistic function of a Markov process (today's hidden Markov model: a model in which hidden states change with probabilities, and each state outputs features of sound with probabilities). In 1976, F. Jelinek of the IBM Thomas J. Watson Research Center published a paper on recognizing continuous speech by statistical methods. However, it was only in the last few years, as of 1988 when Rabiner wrote his manuscript, that this method came to be widely understood and used in speech research. In 1989, Lawrence R. Rabiner of AT&T Bell Laboratories pulled together the theory and its application to speech recognition in a single tutorial. In the experiments in that tutorial, for speaker-independent recognition of digits spoken one word at a time, the error rate of the hidden Markov model was about the same as that of conventional pattern matching (a method called DTW, which lines up differences in speaking speed with dynamic programming and then compares with learned sound patterns). This idea of pattern matching had also been published in Japan in 1971 by Hiroaki Sakoe and Seibi Chiba of NEC as DP matching (another event on this site).

What we still don’t know:Rabiner 1989 also points out that the assumption that sound observations are independent of each other and the Markov assumption do not fit real speech in some ways. Why it worked well in spite of that is not clearly explained in the tutorial.

The Akaike Information Criterion (AIC) — presented by Hirotugu Akaike in 1971 and put into a paper in 1973; it combines fit to the data and a penalty on the number of parameters in one

AIC is a criterion for deciding which to use among several candidate statistical models. It is calculated as AIC = (−2) × (maximum log-likelihood) + 2 × (number of parameters), and the model with the smaller value is judged better. The first term shows how well the model fits the data (the better the fit, the smaller the value), and the second term acts as a penalty for increasing the number of adjustable parameters too much. In 1968, Hirotugu Akaike of the Institute of Statistical Mathematics, working on a time-series model of the behavior of a cement rotary kiln, faced the problem of how many past values to use (the order), and came up with the expected prediction error (FPE). According to his 1981 recollection, on the morning of March 16, 1971, as he sat down on his commuter train, he suddenly noticed the link between maximum likelihood and the Kullback–Leibler information. In his 2006 Kyoto Prize commemorative lecture he said, “The first announcement about AIC was a report at the 1971 meeting of the Japan Statistical Society” (translated). He went on to recall that he presented it in detail the same year at the Second International Symposium on Information Theory held in Armenia, that it came out in the proceedings in 1973, and that in 1974 he published an explanation in a US IEEE journal on automatic control.

What we still don’t know:AIC was not accepted from the start. In his 2006 lecture, Akaike said that there was an eager response from applied fields, but “the response from the field of orthodox statistics was lukewarm” (translated). In his 1981 recollection he also writes that it was still not fully accepted by professional statisticians. Also, AIC assumes a regular model, in which parameters and distributions correspond one to one. So how it can be used for learning machines such as neural networks led to later research (such as Sumio Watanabe's WAIC).

Cross-validation — in 1974, Stone's paper on choosing and assessing prediction methods by splitting the data and checking. The idea itself dates from the 1930s

Cross-validation is a method in which you split the data you have into data for learning and data for checking, repeat the check while changing the split, and choose a prediction method from the average of the results. In the leave-one-out version, from n data points you remove one, build a model from the remaining n − 1, and test it on the removed one, repeating this in n ways. M. Stone (University College London) presented at the Royal Statistical Society on December 5, 1973, and in the paper “Cross-validatory Choice and Assessment of Statistical Predictions”, published in the Journal of the Royal Statistical Society, Series B in 1974, proposed using this criterion in a form that combines the choice of a prediction method with its assessment. He then showed it with examples of estimation from a single sample, multiple regression and analysis of variance.

What we still don’t know:In 1977, Stone showed that leave-one-out cross-validation and Akaike's AIC behave in the same way when there is a lot of data (they are asymptotically equivalent) (as introduced in Watanabe's 2010 paper). However, this is for regular models in which parameters and probability distributions correspond one to one. What happens with singular models such as neural networks was not known until Watanabe's 2010 paper.

WAIC — in 2010, Sumio Watanabe proves that an information criterion usable for neural networks and more, and leave-one-out cross-validation, approach the same value

WAIC (widely applicable information criterion) is a criterion devised by Sumio Watanabe (affiliation in the paper: Precision and Intelligence Laboratory, Tokyo Institute of Technology) for estimating the generalization loss (the prediction error on unseen data) of a Bayesian model. AIC assumes regular models, in which parameters and probability distributions correspond one to one. But many learning machines, such as neural networks, mixtures of normal distributions, hidden Markov models and Boltzmann machines, are singular models for which this assumption does not hold. In a December 2010 paper in the Journal of Machine Learning Research, Watanabe proved that even for such singular models, the loss of Bayesian leave-one-out cross-validation and WAIC approach the same value when the amount of data is large (they are asymptotically equivalent). For regular models, it was known, for example from Stone's 1977 paper, that leave-one-out cross-validation is asymptotically equivalent to AIC.

The EM algorithm: in 1977, Dempster, Laird, and Rubin gathered a method for learning from data with hidden parts into one general form and gave it a name

A. P. Dempster, N. M. Laird, and D. B. Rubin, of Harvard University and the Educational Testing Service, presented a general method for estimating the most likely parameters (the numbers inside a model) when part of the data cannot be seen (is missing). In the E step (expectation), the current parameters are used to calculate the expected values of the unseen parts. In the M step (maximization), the filled-in data are used to recalculate the parameters to their most likely values. Because the two steps are repeated in turn, they named it the EM algorithm. They proved that with every repetition the likelihood of the data (how likely it is that these parameters would produce this data) never goes down. They also showed that many examples fit this form: data with missing values, distributions made by mixing several peaks (mixture distributions), factor analysis, and more. Their first example was data on 197 animals that fall into 4 types through a mechanism of heredity (an example from Rao's 1965 book).

Otsu's binarization: in 1979, Nobuyuki Otsu presented a method that automatically sets the dividing line between white and black in a grayscale image at the point where the two groups are best separated

Nobuyuki Otsu (his affiliation in the 1979 English paper was the Electrotechnical Laboratory, Tokyo) showed a method for automatically deciding the brightness boundary (the threshold) used to separate characters or objects from the background in a black-and-white grayscale image. When the histogram of brightness is split into two groups at a brightness k, the method picks the k at which the spread between the groups (the between-class variance) is largest. This comes from the idea of discriminant analysis (a statistical method for finding a yardstick that separates two groups well), and it is equivalent to making the spread within the groups (the within-class variance) smallest. The calculation uses only the zeroth- and first-order cumulative moments of the histogram (the fraction of pixels up to that brightness, and the sum of their brightness), so it is very easy to compute. It is an unsupervised method: it decides without being given the correct answers. The abstract of the 1980 Japanese paper says the result is also optimal in the least-squares sense when the original grayscale image is approximated by a few values, and that it extends easily to splitting into three or more groups. The paper's examples were the letter A typed with a new ribbon and with an old ribbon, a cloth pattern, and a cell image (split into three: background, cytoplasm, and nucleus).

What we still don’t know:The English paper says that a rigorous proof that the evaluation function always has a single peak (is unimodal) has not yet been obtained (in experiments it was always smooth and unimodal).

Bayesian networks: in 1985, Pearl named a method that shows links between causes and effects as an arrow graph with conditional probabilities (the idea dates from 1982)

Judea Pearl of the University of California, Los Angeles (UCLA) called Bayesian networks the graphs in which many propositions or variables are points (nodes), direct dependencies are arrows, and strengths are given by conditional probabilities (the probability that B happens when A holds). When new evidence (for example, a test result) arrives, each node exchanges short messages only with its neighbors, and the probabilities of the whole network (how strongly we believe things) are updated correctly. This makes it possible to reason from many clues while keeping to the rules of probability. In a 1982 AAAI paper, Pearl wrote that many AI researchers had accepted the myth that computational models of reasoning under uncertainty must bend the rules of probability, at least in part, and were using ad hoc rules. He then showed that for a tree-shaped network, the whole network can be updated according to the rules of probability with a single round of message passing. The 1985 report presented this mechanism at a cognitive science conference as a model of human memory and reasoning.

What we still don’t know:In the abstract, Pearl himself writes that updating the whole network correctly by local message passing alone works only for networks in which there is just one path between any two nodes. For networks with multiple paths, this report only discussed the approach.

Decision trees: in 1986, Quinlan wrote up ID3 in a paper. Its sources are two streams, Hunt and colleagues' CLS (1966) and statistical trees dating from 1963

A decision tree is a classification method that arranges questions, such as what the weather is and whether the humidity is high, in a branching form. You follow the branches according to the answers, and when you reach a leaf, it outputs the result (the class). ID3 builds the tree by choosing which question to ask first as follows. It chooses the question that gives the greatest amount of information (information gain, measured in bits) when the data is split by it, and repeats the same process on each resulting branch. J. R. Quinlan (New South Wales Institute of Technology) worked through a concrete example in his 1986 paper “Induction of Decision Trees”. Using the weather conditions of 14 Saturday mornings (outlook, temperature, humidity and wind, and two classes, P and N), he showed that splitting by outlook gives 0.246 bits of information, the largest, so the root of the tree is outlook. According to the paper, the roots of this family of methods are Hunt and colleagues' CLS (a 1966 book). ID3 (1979) was developed while tackling a task posed by Donald Michie: identifying positions in a chess endgame (king and rook against king and knight) from features of their shape alone.

TD learning: in 1988, Sutton puts together as a theory a way to learn from the error against the next prediction without waiting for the final result

Richard Sutton of GTE Laboratories put together, as a theory, the TD method (temporal-difference learning), a way to learn predictions of the future from experience. Ordinary supervised learning corrects a prediction using the error between the prediction and the final outcome. The TD method, on the other hand, corrects today's prediction using the error between “today's prediction” and “tomorrow's prediction.” The paper gives a weather forecaster as an example. Suppose you predict every day whether it will rain on Saturday, and you predicted 50% on Monday and 75% on Tuesday. The TD method raises the prediction for a day like Monday without waiting for Saturday's result. Sutton argued that this way, the computation can be done a little at a time each day, less memory is needed, and in many cases the predictions are more accurate. He then proved convergence and optimality for special cases. As a test example, he had the method learn, in a random-walk problem that starts at the center D, moves one step at random left or right, and ends on reaching A at the left end or G at the right end, the probability of reaching G from each point.

What we still don’t know:Sutton argued that most of the problems on which supervised learning was being used at the time were in fact prediction problems where the TD method can be used to advantage (his outlook in 1988). This site has not checked how far this outlook turned out to be true.

Q-learning: in 1989, Watkins presents it in a doctoral thesis on how animals learn optimal behavior (the detailed proof came in 1992)

Christopher Watkins, in his King's College doctoral thesis Learning from Delayed Rewards (May 1989), posed the question of how an animal can learn optimal behavior from experience. In behavioral ecology, the optimal behavior of animals is derived by dynamic programming (a method that looks ahead through all later results to compute the best action), but it is hard to think that animals do such a calculation. So Watkins presented one-step Q-learning, which gradually updates the action value Q(x, a) of taking action a in state x, trial by trial, using the reward r obtained and the largest Q value in the next state. In an appendix he proved that, even without a model of the environment, if every action is tried many times in every state, the values approach those of the optimal behavior. In 1992, Watkins and Dayan published in a journal a short paper that wrote out this proof in detail.

What we still don’t know:According to the preface of the thesis, Sutton pointed out a difficult point of Q-learning. This site has not checked what that was.

A theory of profit sharing: in 1994, Kazuteru Miyazaki, Masayuki Yamamura and Shigenobu Kobayashi of the Tokyo Institute of Technology proved the condition under which reinforcement learning that hands out rewards in a lump does not learn useless actions, and won the Japanese Society for Artificial Intelligence's paper award

Reinforcement learning (a method of learning how to act by trial and error, guided by rewards) includes TD learning and Q-learning, which update the value of an action at every step, and the profit sharing method, which, when a reward is obtained, reinforces the whole series of earlier actions (the episode) together. Kazuteru Miyazaki, Masayuki Yamamura and Shigenobu Kobayashi mathematically analyzed, for the profit sharing method, how much of the reward to hand out to the action taken how many steps before it (the reinforcement function). As a result, they proved the necessary and sufficient condition for not learning ineffective rules (actions) that cause detours (the ineffective rule suppression theorem), and also showed that under the same condition it can learn an action policy that keeps earning rewards. The paper compares this with Q-learning, which needs a huge number of trials to understand the environment accurately, and says that profit sharing needs far fewer trials to learn. This paper won the Japanese Society for Artificial Intelligence's paper award for fiscal 1994.

What we still don’t know:This site has not confirmed how far this condition was later used in real robots and applications.

Boosting: in 1990, Schapire proves that weak learning can be turned into strong learning, and in 1995 Freund and Schapire announce AdaBoost

Boosting is a method that builds many weak classifiers that are only slightly better than guessing, trains each round with larger weights on the data that the previous round got wrong, and in the end combines them by a weighted majority vote into a strong classifier. Its origin was a question in computational theory. Kearns and Valiant left it as an open problem (the hypothesis boosting problem) whether weak learning, which is only slightly better than guessing, and strong learning, which can be made as accurate as you like, have the same power. R. E. Schapire (MIT Laboratory for Computer Science) proved in his 1990 paper “The Strength of Weak Learnability” that the two are the same, and showed a construction that turns a method of weak learning into a method of strong learning. Y. Freund and Schapire announced AdaBoost at a conference in Barcelona in March 1995 (the paper was published in an academic journal in 1997). They wrote in the paper that the name comes from the fact that, unlike earlier methods, it changes the weights adaptively according to the errors of the weak classifiers. The paper begins with an analogy of a person who keeps losing at horse racing and reallocates his bets according to the track records of his friends.

What we still don’t know:Why does the test error keep falling even after the training error reaches 0? Schapire's 2013 explanation writes that the explanation using margins is the only theory that can account for the cases where overfitting does not occur. He also writes, though, that the numerical guarantees are very loose.

Gradient boosting: in 1999, Friedman generalized boosting, which fills in residuals little by little with small decision trees, as gradient descent

Gradient boosting is a method that improves predictions little by little by repeating the following many times: have the next small decision tree predict the error (the residual) between the current model's prediction and the correct answer, and add that tree a little at a time. Friedman (Jerome H. Friedman, Stanford University) wrote the paper “Greedy Function Approximation: A Gradient Boosting Machine” dated February 24, 1999 (IMS 1999 Reitz Lecture, published in The Annals of Statistics in 2001). In it he regarded this piling up of additions as a computation that goes down a little at a time in the steepest direction, in function space, of the size of the error (the loss) (steepest descent). When the loss is squared error, the tree at each round simply learns the current residual. The same procedure can be applied to other losses, such as absolute error, the Huber loss, and the logistic likelihood for classification. He also writes that making the amount added at each round small with a learning rate ν (shrinkage) often gives better results.

The support vector machine with kernels: in 1992 Boser, Guyon and Vapnik presented margin maximization in a form that also works for curved boundaries

A support vector machine (SVM) is a method that draws the boundary between two classes so that the distance (the margin) from the boundary to the nearest points is as large as possible. Boser (B. E. Boser, University of California, Berkeley; part of the work was done at AT&T Bell Laboratories), Guyon (I. M. Guyon) and Vapnik (V. N. Vapnik; both at AT&T Bell Laboratories), in their paper “A Training Algorithm for Optimal Margin Classifiers” at the conference COLT '92 in July 1992, rewrote this problem so that it uses only a function that measures the similarity between points (the kernel) K(x, x') (the dual form). This lets the same computation maximize the margin even for curved boundaries such as polynomials or radial basis functions. The boundary is determined only by the few training examples closest to it (called supporting patterns in the paper). On handwritten digits taken from real mail (7,300 training and 2,000 test images), a 4th-degree polynomial kernel gave an error rate of 4.9%, slightly below the 5.1% reported for a 5-layer neural network on the same data.

Random forests: in 2001, Breiman combined the majority vote of many decision trees randomly varied a little. In 1995 Ho had already published random decision forests

A random forest is a method that grows many decision trees under slightly different conditions and decides the prediction by majority vote. Each tree is grown from examples chosen at random from the training data, and at each split the best way of dividing is chosen from a randomly chosen subset of the features. In his 2001 paper “Random Forests”, Breiman (Leo Breiman, Statistics Department, University of California, Berkeley) wrote that as more trees are added, the error rate converges to a fixed value by the strong law of large numbers, so overfitting is not a problem. He also showed that the error rate of a forest is determined by the strength of the individual trees and the correlation between them. Using the roughly one third of examples that were not chosen at random (out-of-bag), the error rate can be estimated without separate test data or cross-validation. In 1995, Ho (Tin Kam Ho, AT&T Bell Laboratories) had shown in “Random Decision Forests” that bundling trees that each use a randomly chosen subset of the features improves accuracy in handwritten-digit recognition, both on the training data and on data seen for the first time.

Singular value decomposition: Beltrami in 1873 and Jordan in 1874 show that any matrix can be split into three steps: rotate, stretch or shrink, rotate

Singular value decomposition (SVD) is the fact that any matrix (a table of numbers in rows and columns that expresses a transformation of vectors) can be split into three multiplications: change the direction (rotate) → stretch or shrink along each axis → rotate once more. The stretch or shrink factors are called singular values. If you keep only the large singular values, the original table can be approximated well with fewer numbers, so SVD is used for predicting tastes (recommendation features) and for computing principal component analysis. The first to publish this decomposition, in 1873, was Eugenio Beltrami, in a mathematics journal for Italian university students. At the start Beltrami wrote, in effect, that he hoped to give young readers a chance to become familiar with this kind of algebraic calculation. The next year, 1874, Camille Jordan separately presented the same decomposition in a more complete form.

What we still don’t know:According to Stewart 1992, the time when the term singular value settled into its present meaning was uncertain in the first half of the 20th century. We have not traced the original sources on this site.

Best approximation by a lower rank: in 1936 Eckart and Young solve it in connection with factor analysis (a rediscovery of Schmidt’s 1907 theorem)

Carl Eckart and Gale Young of the University of Chicago solved the problem of approximating a matrix by a matrix of lower rank (the number of mutually independent directions) so that the sum of squared errors is as small as possible. According to the abstract of the paper, the problem becomes easier to solve if the matrix is first brought to a canonical form (today’s singular value decomposition). A solution always exists and is usually unique. The solution is the singular value decomposition with the small singular values set to 0 (as explained by Stewart 1992). The abstract says the problem is deeply connected to a basic concept of factor analysis, which explains a table of test scores by a few factors. The paper appeared in volume 1 of Psychometrika, a journal of psychological measurement founded that year.

What we still don’t know:Whether Eckart and Young knew Schmidt’s 1907 work has not been checked on this site (we have not opened the full text).

The $1 million contest to predict movie tastes, the “Netflix Prize” (2006–2009): the winner was decided by a 20-minute margin

In October 2006, Netflix, which then rented out movies on DVD, opened a contest. It offered a $1 million prize to anyone who could predict movie ratings 10% more accurately than its own recommendation system (Cinematch). It distributed more than 100 million ratings (1 to 5 stars) of about 18,000 movies by about 480,000 people, with names replaced by numbers. About three years later, on September 21, 2009, the team BellKor's Pragmatic Chaos won. The second-place team had the same score (error 0.8567, a 10.06% improvement), but the side that submitted about 20 minutes earlier became the winner (under the rule that a tie goes to whoever submitted first).

Factorizing the table of tastes: in 2006 Simon Funk published on his blog the method he used in the Netflix Prize, which learns from only the known entries of a table full of blanks

Simon Funk, who was taking part in the Netflix Prize, a contest to predict movie tastes, published his whole method (at that time tied for third) on his blog on December 11, 2006. The data provided was 100 million ratings by about 500,000 people of about 17,000 movies; as a user-by-movie matrix, 8.4 billion of its roughly 8.5 billion entries were missing. Funk represented each user's taste and each movie's features as 40-dimensional vectors and predicted a rating from their inner product (about 20 million parameters, 1/400 of the original matrix). This has the same form as an approximation by singular value decomposition (SVD) that keeps the top 40 singular values, but real SVD cannot be computed when values are missing. So he found the prediction error only for the known ratings, and repeatedly adjusted the parameters a little in the direction that made the error smaller (gradient descent; the learning rate was 0.001). He himself calls this a modified SVD.

What we still don’t know:This site has not confirmed who, before Funk, had devised a method that likewise factorizes a matrix with missing values to predict tastes.

Amazon launches “Amazon Mechanical Turk”, which lets computers ask people to do small jobs (“Artificial Artificial Intelligence”)

Amazon announced “Amazon Mechanical Turk”, a system in which a program asks people to do small tasks and receives the results. The announcement calls a computer having many people do work and using the results “Artificial Artificial Intelligence”. Later, in 2009, it was used for ImageNet to check whether a photo really showed a given object. The ImageNet paper describes it as a place where workers are paid.

Fei-Fei Li and colleagues at Princeton University present ImageNet, millions of named photos; the people who checked them were workers hired over the internet

Li and colleagues presented ImageNet, built on WordNet, a dictionary that organizes concepts in a hierarchy, and collecting an average of 500–1,000 photos for each of about 80,000 groups of nouns (the paper's example is “Burmese cat”). At the time of publication it had reached 12 areas, 5,247 categories and 3.2 million images. The images were collected with search engines, and workers around the world, paid through Amazon Mechanical Turk, checked one by one whether the target object was really in each picture, deciding by the votes of several people.

What we still don’t know:The paper does not state the number of workers, the countries they lived in, or the amount they were paid (unconfirmed).

Three Google researchers present “The Unreasonable Effectiveness of Data”: stop aiming for a very neat theory, and make data your ally

Google's Alon Halevy, Peter Norvig and Fernando Pereira wrote that the most successful machine learning on language was statistical speech recognition and statistical machine translation. Translation (and transcribing speech is the same) is done routinely every day for real human needs, so, they said, there is naturally “the input-output behavior that we seek to automate” out in the world. They also mentioned that in 2006 Google released a data set of 1 trillion words of text (counts of word sequences up to 5 words long). And they stated that “invariably, simple models and a lot of data trump more elaborate models” based on less data, and in the closing paragraph they wrote “So, follow the data.”

NVIDIA announces CUDA, a system that lets the GPUs it makes for drawing images be used for other computing too

A GPU (a semiconductor chip for graphics) built to draw game images can do the same calculation at the same time on many small computing cores (up to 128 on the GeForce 8800 GTX). Along with the GeForce 8800, NVIDIA announced “CUDA”, a system that lets a GPU be used for computing other than graphics in an ordinary programming language (C). This later became a tool for training neural networks quickly (a 2009 Stanford paper, and the winning team of the 2012 image-recognition contest, also used GPUs).

Andrew Ng and colleagues at Stanford show that GPUs can speed up neural network training by up to 70 times

Rajat Raina, Anand Madhavan and Andrew Ng trained deep networks that learn without labels (unsupervised learning) on a gaming GPU (NVIDIA GeForce GTX 280). It was up to 70 times faster than an ordinary CPU (2 cores), and cut the training of a 4-layer network with 100 million numbers from “around a single day”. The paper pointed out the problem that, although learning from large amounts of data is important, slow computation kept experiments small.

At Google, “Google Brain”, a team for trying out large neural networks, gets started

According to the official page of X, a division of Google (the footer reads “X, a division of Google LLC” and the title is “Brain - A Google X Moonshot”), the Google Brain team began work in 2011 and moved from X to Google at the end of 2012. In December 2011, researchers at Google and Stanford University released the first version of a paper on learning from unlabeled YouTube images (later known as Google's cat paper). In a 2012 paper they presented DistBelief, a system for training one large neural network on thousands of computers; they reported training a network 30 times larger than previously reported, and also speeding up the training of a commercial speech recognizer. In April 2023, Google announced that it would merge this team with DeepMind into Google DeepMind.

Deep-learning AI had a success in “speech recognition” before images (2009–2012)

Deep learning (an AI method that learns with neural networks stacked in many layers) began, around 2009, to beat the statistical method that had long been used in speech recognition (GMM). In 2012, four research groups, at the University of Toronto, Microsoft Research, Google and IBM, wrote up a paper that “represents the shared views of four research groups”, and showed results such as cutting the share of wrong words on a speech-transcription test from 27.4% to 18.5% (by about one third). In a blog post on August 6, 2012, Google wrote that with the new version of Android, when you speak to your phone, “chances are, you are talking to a neural network trained to recognize your speech”.

What we still don’t know:Looking back, the four-group paper writes that most of the gains came from the ability to “exploit information in neighboring frames” (a frame is a short slice of sound) and from “modeling tied context-dependent states” (predicting sound states that are split according to the sounds before and after, with similar ones grouped together). At the same time, it also writes that there is “no reason to believe ... optimal types of hidden units or the optimal network architectures” have already been found (PDF page 13). Why deep neural networks work better was still an unfinished explanation at the time.

Japan's national research institute NICT releases “VoiceTra” worldwide, a smartphone app that translates what you say and answers in a voice

In the summer of 2010, NICT (National Institute of Information and Communications Technology), a national research institute of Japan, released the speech translation app VoiceTra and the text translation app TexTra free of charge worldwide on the App Store. With VoiceTra, you speak to your iPhone and it translates into another language and answers in a voice. The translation is computed on a server, not on the iPhone. The languages that worked by voice were Japanese, Mandarin, English, Indonesian and Vietnamese (Malay was in preparation). It was aimed at travel conversation, and NICT described the speech translation ability as “roughly equivalent to a person with a TOEIC score of 600 in language ability” (translated). The purpose of the release was to evaluate performance and to study ease of use. According to NICT's 2015 announcement, the technology was also used in real services such as Narita International Airport's app. It then became the central app of the Ministry of Internal Affairs and Communications' “Global Communication Plan” (April 2014; aiming for a society by 2020 in which foreign visitors to Japan do not have trouble with language).

Apple unveils the iPhone 4S with “Siri”, which helps with tasks when you talk to it (at first “in beta”)

On October 4, 2011, together with the iPhone 4S, Apple announced Siri, “an intelligent assistant” that helps with tasks when you ask by voice. In the example in the announcement, when you ask “Will I need an umbrella this weekend?”, it understands that you are looking for a weather forecast. At first it was “in beta” (a trial version), and the only languages supported were English (for the U.S., the U.K. and Australia), French and German. In Japan the iPhone 4S went on sale on October 14, but Siri with Japanese support came only on March 8, 2012. Siri's origin is CALO, research that SRI International carried out under PAL, a program of DARPA, the U.S. Department of Defense's research agency. It was spun off as a company in 2007, and in April 2010 Apple acquired that company (according to SRI's and DARPA's explanations).

NTT Docomo launches the voice dialogue service “Shabette Concier” (March 2012, one week before Japanese Siri)

On March 1, 2012, NTT Docomo launched Shabette Concier, a “voice agent function” (translated) that lets you look up information and operate email, alarms and more just by talking to a smartphone, as a free app for Docomo's Android smartphones. It reads the speaker's “intention” (translated) from the combination of words and chooses a suitable service or answer. Complex processing such as speech recognition was done not on the device but on Docomo's network side (the cloud). Docomo described it as following the “interpreter phone” (translated) cloud service, whose trial offering began in November 2011. The launch of Japanese Siri came one week later, on March 8.

IBM's question-answering AI “Watson” beats two all-time champions on the U.S. quiz show Jeopardy!

In February 2011, Watson, a question-answering system (a program that reads a question in natural language and returns an answer) developed by an IBM research team, played two games against two all-time champions on the U.S. TV quiz show Jeopardy!. The final scores were $77,147 for Watson, $24,000 for Ken Jennings and $21,600 for Brad Rutter (IBM's history page). Watson was not connected to the internet; it produced candidate answers with many methods, gathered evidence, and pressed the buzzer only when the “confidence” that machine learning (a way of learning from data) had put together was high enough. On the final question of the first game, a question about U.S. cities, it answered “What is Toronto?????” and was wrong.

How ReLU (0 if negative, unchanged if positive) became the standard in deep learning: named in 2010, widespread in 2011–2012. The same form appears in Kunihiko Fukushima's 1968 model

ReLU (rectified linear unit) is a unit (neuron) that outputs its input x as it is if x is greater than 0, and outputs 0 if x is 0 or less; as a formula, max(0, x). Sigmoid (S-shaped function) and tanh have a slope that becomes almost 0 (they saturate) when the input is large, but ReLU has a slope of always 1 for positive values, so the signal sent back through backpropagation is less likely to fade. In 2010, Nair and Hinton of the University of Toronto showed that if the 0-or-1 hidden units of a restricted Boltzmann machine are replaced by many copies of a unit with the same weights, shifted slightly one from another, their behavior can be approximated by noisy rectified linear units. They also reported better results in recognizing photos of objects and faces. In 2011, Glorot and colleagues at the Université de Montréal wrote that this unit is also a better model of real nerve cells and can form sparse representations, with many values exactly 0. They also wrote that, with plenty of labeled data, deep networks can learn well without prior unsupervised learning. The 2012 AlexNet paper, following Nair and Hinton, called it ReLU and wrote that it trained several times faster than the same network using tanh.

What we still don’t know:I have not checked whether the 2010 paper was the first to use the name “rectified linear” (the 2010 paper writes that Jarrett and colleagues in 2009 called it positive part). Fukushima's 1969 English paper (IEEE) is behind a paywall and I have not opened its text. I have not opened the 2009 paper by Jarrett and colleagues either.

How to set initial weights: matching the spread to the number of neurons in the layers (Glorot and Bengio 2010), and a version for ReLU (He et al. 2015)

Before a deep network is trained, what values are put into its weights (initialization) greatly changes whether it can be trained at all. If the signal grows or shrinks by a fixed factor each time it passes through a layer, then after many layers the backpropagated gradient vanishes or blows up. In 2010, Glorot and Bengio of the Université de Montréal showed that with the commonly used method, choosing from the range ±1/√n where n is the number of neurons in the previous layer, the spread (variance) of the backpropagated signal gets smaller from layer to layer. They proposed normalized initialization, which uses the numbers of neurons on the input side and the output side of a layer, nj and nj+1, and chooses uniformly from the range ±√6/√(nj+nj+1). The aim is to keep the spread of the forward-propagated values and of the backpropagated signal about the same in every layer. In 2015, Kaiming He and colleagues at Microsoft Research pointed out that this derivation rests on the assumption that neurons are linear (output proportional to input), which does not fit ReLU. For ReLU they proposed choosing from a normal distribution with mean 0 and standard deviation √(2/n). They write that a 30-layer network could be trained this way, while training stalled with Glorot and Bengio's method.

What we still don’t know:I have not confirmed when, or by whom, the name Xavier was given inside Caffe (I have not opened the Caffe paper or the program's records). I have not confirmed who started the ±1/√n method, which the 2010 paper calls a commonly used heuristic, or when.

Dropout: randomly resting half of the hidden-layer neurons at each training step to prevent overfitting (2012)

Dropout is a method in which, each time one piece of data is shown during training, hidden-layer neurons are temporarily removed at random with a fixed probability (often 0.5), that is, their outputs are set to 0, while the network learns. It prevents specific neurons from depending on one another (co-adaptation) and suppresses overfitting, in which a network fits only the training data too closely and makes mistakes on new data. At use time, all neurons are used and the outgoing weights are halved (in the 2014 paper, the weights are multiplied by the retention probability p). The result is close to averaging the predictions of many thin networks that share weights. The July 2012 arXiv paper (Hinton, Srivastava, Krizhevsky, Sutskever and Salakhutdinov of the University of Toronto) tried it on handwritten digits (MNIST) and others, and wrote that it set records in speech and object recognition. The AlexNet paper of the same year also used it in the two fully connected layers, and wrote that without it overfitting became serious.

What we still don’t know:I have not written down when dropout was conceived, or the several accounts Hinton himself later gave of how it came about, because I have not looked for the original talks.

Switzerland's IDSIA: a deep convolutional neural network trained on GPUs gets half the human error rate at recognizing traffic signs (8 months before the 2012 competition)

Dan Cireşan, Ueli Meier and Jürgen Schmidhuber of the Swiss institute IDSIA trained, on gaming GPUs, a method that lines up several deep convolutional neural networks and averages their outputs (a multi-column deep network). On recognition of German traffic signs (12,569 test images) it recorded an error rate of 0.54%, and according to the paper the human error rate was twice that. On the handwritten-digit set MNIST it also reached 0.23%, which they write is the first time a machine came close to the human figure of about 0.2%.

Google's cat experiment: a network that learned only from unlabeled YouTube images developed a neuron that responds strongly to cat faces

Quoc Le, Andrew Ng and colleagues at Google and Stanford University showed a 9-layer neural network with 1 billion connections still images (200×200 pixels), one taken from each of 10 million YouTube videos, with no labels, and let it learn. It took 3 days on 1,000 computers (16,000 cores). Without being taught, it developed neurons that respond to human faces, and also ones that respond to cat faces and human bodies. In its blog, Google described how “one of our artificial neurons learned to respond strongly to pictures of... cats”, and stressed that “this network had never been told what a cat was”.

What we still don’t know:The paper examines what the trained neurons respond to, by lining up the images that excite them most and by constructing images that make them respond more strongly. Methods for looking inside the network were already being devised at that time.

In the image-recognition competition ILSVRC 2012, the University of Toronto's deep convolutional neural network (SuperVision) wins by a wide margin. The runner-up is a University of Tokyo team

In a competition to identify 1,000 kinds of objects from photos, the team “SuperVision” of Krizhevsky, Sutskever and Hinton held its error rate, under a rule allowing 5 guesses, to 15.3% (16.4% if only the data supplied by the competition is used). The runner-up, a University of Tokyo team (ISI), scored 26.2%, a gap of about 11 points. They trained an 8-layer neural network with 60 million parameters on 2 gaming GPUs (graphics chips, made by NVIDIA). In a later paper, the competition's organizers wrote that “This was a turning point for large-scale object recognition” for research on recognizing a wide variety of objects.

In the image-recognition competition, the top team's “Error (5 guesses)” fell from 28% to 2% in 8 years. The “human: 5.1%” figure is one person's measurement

In a competition to identify 1,000 kinds of objects from images (with a rule allowing up to 5 guesses), the winning error rate fell: 28.2% in 2010, 25.8% in 2011, 15.3% in 2012 (16.4% with only the supplied data), 11.7% in 2013 (11.2% when outside data was also used), 6.7% in 2014, 3.6% in 2015, 3.0% in 2016 and 2.3% in 2017. The organizers also measured the human error rate. It was a test with two people (A1 and A2): A1, who had practiced on 500 images, scored 5.1% on 1,500 images, and A2, who had practiced on only 100 images, scored 12.0% on 258 images.

The shogi program Bonanza, which learns from professional game records, wins a world championship and the next year plays Ryuo Akira Watanabe in a public game

The shogi program Bonanza was developed by Kunihito Hoki, a chemistry researcher, and released free of charge in June 2005. Unlike many earlier shogi programs, it used “full-width search” (translated), which reads out every move allowed by the rules. It also adopted “machine learning” (translated), training the way positions are evaluated so as to play the same moves as professionals' game records. The author has said that he applied the idea from his research on controlling chemical reactions to learning position evaluation. In May 2006, at its first entry in the 16th World Computer Shogi Championship, it won the round robin of the 8 finalists with 6 wins and 1 loss. On March 21, 2007, it played a public game against Ryuo (Dragon King title holder) Akira Watanabe, with 2 hours of thinking time each. Bonanza was also said to have the upper hand in the middlegame, but the Ryuo won in 112 moves. Later its method (and in 2009 the inside of the program) was made public, and shogi programs based on Bonanza, such as Bonkras, were born.

The Information Processing Society of Japan's shogi software “Akara 2010” beats Women's Osho Ichiyo Shimizu

In April 2010 the Information Processing Society of Japan sent the Japan Shogi Association a challenge letter, “hoping for public games between computer shogi and top professional players” (translated). The association's president, Kunio Yonenaga, accepted and chose as the first opponent Ichiyo Shimizu, the Women's Osho (a title of women's shogi) and the leading woman professional. The game was played on October 11 at the University of Tokyo's Hongo campus; Shimizu resigned at move 86 and Akara 2010 won. Akara 2010 had Japan's four top shogi programs (Gekisashi, GPS Shogi, Bonanza and YSS) think about the same position and played the move chosen most often, a “majority vote” (translated) system, and used 208 computers (658 cores in total).

1st Shogi Den-O-sen: Kunio Yonenaga, Eternal Kisei, loses in 113 moves to the shogi software “Bonkras”

On January 14, 2012, at the Shogi Kaikan (Shogi Hall) in Tokyo, Kunio Yonenaga, president of the Japan Shogi Association and a retired professional holding the lifetime Kisei title (Eternal Kisei), played the shogi software “Bonkras”, developed by Hidenori Ito of Fujitsu Laboratories, and Bonkras won in 113 moves. Bonkras is a version of the publicly available shogi software Bonanza, improved to search in parallel on several computers; that day it read about 18 million moves per second on 6 servers. The name is a coined word combining Bonanza and “cluster”, which means a parallel computer (a system that calculates on several computers at the same time) (as explained in Fujitsu Laboratories' announcement).

Checkers “is now solved”: computers prove it is always a draw if neither side makes a mistake

Jonathan Schaeffer and his colleagues at the University of Alberta kept dozens of computers running almost nonstop from 1989 and proved that “Perfect play by both sides leads to a draw.” Checkers has about 5×10²⁰ (500 quintillion) board positions, making it the hardest well-known game solved so far. One of the main tools in the proof was the search method (df-pn) from Ayumu Nagai's 2002 doctoral thesis at the University of Tokyo. Akihiro Kishimoto, who by the time of the paper had moved to a university in Hakodate, Hokkaido, is also among the co-authors.

When did a professional first play a shogi program? The sources split between 2005, 2007 and 2013

For the “first” (translated) game between a professional shogi player and a shogi program, the sources name three different years. (1) For the September 2005 game between TACOS and 5-dan Takayoshi Hashimoto, the newspaper of the time reported, as the words of its developer, Professor Hiroyuki Iida, “This is the first time a professional has played a computer in an even game in a public setting” (translated). (2) For the March 2007 game between Bonanza and Ryuo (Dragon King title holder) Akira Watanabe, a researcher's commentary wrote “It was the first time a professional and a computer played in an official setting” (translated), and a 2020 interview article wrote “the first time in public as a professional player” (translated). (3) For the 2nd Shogi Den-O-sen in 2013, a column by the Japan Shogi Association (2017) put it as “For the first time, professional players officially fought computer shogi software” (translated). Because of the difference in the words “public setting”, “official setting” and “officially” (translated), every one of them can be called the “first” (translated).

The Japan Shogi Association decides that when professionals play software in public, they should “consult and confirm in advance with the organizer and the Association” (translated)

On September 18, 2005, in Komatsu, Ishikawa Prefecture, the shogi software “TACOS” (translated), developed by Professor Hiroyuki Iida and colleagues at the Japan Advanced Institute of Science and Technology, played a public even game (no handicap) against 5-dan Takayoshi Hashimoto. The professional won, but the software had the advantage until the endgame (The Sankei Shimbun). About a month later, on October 14, the Japan Shogi Association announced that, “to create an environment in which computer shogi software and humans can play in a proper setting” (translated), when players and women's professionals play shogi software in public, they should consult and confirm in advance with the organizer and the Association. The same announcement also says, “We want to go on cooperating with the development of shogi software as we have until now” (translated).

The National Institute of Informatics launches “Can a Robot Get into the University of Tokyo?” (Todai Robot, Torobo-kun). The goals: a high score on the Center Test by 2016, passing the University of Tokyo entrance exam in 2021

In 2011 the National Institute of Informatics began the “Artificial Brain Project”, which develops a computer program that solves university entrance exam questions. Its aims were to reintegrate AI research, which had split into specialized subfields since 1980, and to give young people a dream. As concrete targets it set “high scores on the university entrance Center Test by 2016” (translated) and “pass the University of Tokyo entrance exam in 2021” (translated).

What happened next:In the NII's announcement of November 14, 2016, the program scored 525 points (national average 454.8) on a mock Center Test (5 subject areas, 8 subjects), a standardized score (hensachi) of 57.1. That is a score with an 80% or higher chance of admission at 512 private universities (1,343 departments) and 23 national and public universities (30 departments). On the mock University of Tokyo entrance exam it reached a standardized score of 76.2 in mathematics (science track), fully solving 4 of the 6 problems without human help. For how the Center Test effort was treated at the briefing on the same day, see the 2016 Torobo-kun event (record → Torobo-kun (the Todai Robot): What Happ…). This site has not found an announcement that it passed the University of Tokyo entrance exam in 2021.

A prediction: in 2010 Japan's robot market will be about 3 trillion yen (a 2001 forecast by industry groups). The home and hospital robot market actually did not reach 10 billion yen

In 2001, a report by the Japan Machinery Federation and the Japan Robot Association forecast the robot market in five fields. For 2010 it gave 1.5 trillion yen for daily life, 850 billion yen for manufacturing, 290 billion yen for public use, 260 billion yen for medical care and welfare, and 90 billion yen for biotechnology (about 3 trillion yen in total), and for 2025 about 8 trillion yen in total. According to a 2009 analysis by Hirohiko Arai of the National Institute of Advanced Industrial Science and Technology, this forecast was used as the basis for explaining research and development budgets by the Ministry of Economy, Trade and Industry and others, and it spread through news reports too. A 2005 Aichi Expo announcement also stated that “a market size of 1.8 trillion yen is expected in 2010” (translated).

What happened next:According to Hirohiko Arai's 2009 analysis, the market for next-generation robots outside manufacturing stayed at 1.4 to 6.8 billion yen a year (under 10 billion yen) in surveys of actual conditions by the industry association and others, far from the 2010 forecast (about 2 trillion yen outside manufacturing). In 2006–2008, national agencies and the industry association itself revised the 2010 forecast downward to 50–75 billion yen. In 2015 the government's “New Robot Strategy” gave the size of the robot market as “600 billion yen at present” (translated) and set a new target of 2.4 trillion yen in 2020 (from the Ministry of Internal Affairs and Communications' 2015 white paper). This site has not checked the 2025 forecast.