16
$\begingroup$

I'm trying to understand the context of the famous Minsky and Papert book "Perceptrons" from 1969, so critical to neural networks.

As far as I know, there were no other generic supervised learning algorithms yet except for perceptron: decision trees started to become actually useful only in late '70s, random forests and SVMs are '90s. It seems that the jackknife method was already known, but not k-cross validation (70s) or bootstrap (1979?).

Wikipedia says the classical statistics frameworks of Neyman-Pearson and Fisher were still in disagreement in '50s, despite that the first attempts at describing a hybrid theory were already in '40s.

Therefore my question: what were the state-of-the-art methods of solving general problems of predicting from data?

$\endgroup$
  • 6
    $\begingroup$ Logistic regression started to be used as it is today in the late 70' see Cramer, J. S. (2002). "The origins of logistic regression", p. 12, papers.tinbergen.nl/02119.pdf $\endgroup$ – Tim Feb 1 '16 at 15:47
  • $\begingroup$ Linear regression is probably a "generic supervised learning algorithm" and was originated in the early 1800s; probit regression, at least in some form, apparently originated in the 1930s. Do you mean something in particular by "generic" here? $\endgroup$ – Dougal Feb 1 '16 at 18:23
  • $\begingroup$ @Dougal: just "found to be applicable to a large number of problems in different fields", as opposed to "designed to solve a specific problem". I'm trying to understand what methods would be used by a statistician or an AI scientist in the '60s when facing a new unknown problem with no prior work when the simplest approach (like, I guess, linear regression?) doesn't work and therefore looking for more complex tools is justified. For example, random forest is now one of such algorithms: they work reasonably well on plenty of datasets from various fields. $\endgroup$ – liori Feb 1 '16 at 18:58
  • $\begingroup$ Yeah, sure. It's maybe worth noting that probit regression is actually probably a better general-purpose classification model than the original perceptrons. Whether it was used as such at the time, I don't know. Perceptrons were considered different at the time because they were bundled with an SGD-like optimization algorithm that probably made them more scalable for computers of the time than probit, though of course today we realize those choices are independent. $\endgroup$ – Dougal Feb 1 '16 at 19:14
  • 1
    $\begingroup$ For anyone here still interested in the topic: I found an interesting study from the sociology of science field on the topic of the perceptron controversies in '60s: Olazaran, "Official History of the Perceptrons Controversy". The text does not answer the question stated here, but provides the sociological context for the Minsky and Papert book—one which seems to me now more important than the actual state of science. $\endgroup$ – liori Apr 10 '16 at 18:12
12
$\begingroup$

I was curious about this, so I did some digging. I was surprised to find that recognizable versions of many common classification algorithms were already available in 1969 or thereabouts. Links and citations are given below.

It is worth noting that AI research was not always so focused on classification. There was a lot of interest in planning and symbolic reasoning, which are no longer in vogue, and labelled data was much harder to find. Not all of these articles may have been widely available then either: for example, the proto-SVM work was mostly published in Russian. Thus, this might over-estimate how much an average scientist knew about classification in 1969.


Discriminant Analysis

In a 1936 article in the Annals of Eugenics, Fisher described a procedure for finding a linear function which discriminates between three species of iris flowers, on the basis of their petal and sepal dimensions. That paper mentions that Fisher had already applied a similar technique to predict the sex of human mandibles (jaw bones) excavated in Egypt, in a collaboration with E. S Martin and Karl Pearson (jstor), as well as in a separate cranial measurement project with a Miss Mildred Barnard (which I couldn't track down).

Logistic Regression

The logistic function itself has been known since the 19th century, but mostly as a model for saturating processes, such as population growth or biochemical reactions. Tim links to JS Cramer's article above, which is a nice history of its early days. By 1969, however, Cox had published the first edition of Analysis of Binary Data. I could not find the original, but a later edition contains an entire chapter on using logistic regression to perform classification. For example:

In discriminant analysis, the primary notion is that there are two distinct populations, defined by $y=0,1$, usually two intrinsically different groups, like two species of bacteria or plants, two different kinds of product, two distinct but rather similar drugs, and so on....Esentially the focus in discriminant analysis is on the question: how do the two distributions differ most sharply? Often, this is put into a more specific form as follows. There is given a new vector $x'$ from an individual of unknown $y$. What can we say about that $y$....

$k$-Nearest Neighbors

Cover and Hart are often credited with inventing/discovering the $k$-nearest neighbor rule. Their 1967 paper contains a proof that $k$-NN's error rate is at most twice the Bayes error rate. However, they actually credit Fix and Hodge with inventing it in 1951, citing a technical report they prepared for the USAF School of Aviation Medicine (reprint via jstor).

Neural networks

Rosenblatt published a technical report describing the perceptron in 1957 and followed it up with a book, Principles of Neurodynamics in 1962. Continuous versions of backpropagation have been around since the early 1960s, including work by Kelley, Bryson, and Bryson & Ho (revised in 1975, but the original is from 1969. However, it wasn't applied to neural networks until a bit later, and methods for training very deep networks are much more recent. This scholarpedia article on deep learning has more information.

Statistical Methods

I suspect using Bayes' Rule for classification has been discovered and rediscovered many times--it is a pretty natural consequence of the rule itself. Signal detection theory developed a quantitative framework for deciding whether a given input was a "signal" or noise. Some of it came out of radar research after WWII, but it was rapidly adapted for perceptual experiments (e.g., by Green and Swets). I do not know who discovered that assuming independence between predictors works well, but work from the early 1970s seems to have exploited this idea, as summarized in this article. Incidentally, that article also points out that Naive Bayes was once called "idiot Bayes"!

Support Vector Machines

In 1962, Vapnik and Chervonenkis described the "Generalised Portrait Algorithm" (terrible scan, sorry), which looks like a special case of a support vector machine (or actually, a one-class SVM). Chervonenkis wrote an article entitled "Early History of Support Vector Machines" which describes this and their follow-up work in more detail. The kernel trick (kernels as inner products) was described by Aizerman, Braverman and Rozonoer in 1964. svms.org has a bit more about the history of support vector machines here.

$\endgroup$
  • 2
    $\begingroup$ time-series analysis was also solving some interesting problems. ARMA and Kalman filters made some good mileage in the 50's and 60's. $\endgroup$ – EngrStudent - Reinstate Monica Oct 21 '16 at 0:39
  • 1
    $\begingroup$ Interesting! I don't know nearly as much about it or its history, but I'd happily upvote an answer if you wrote one! $\endgroup$ – Matt Krause Oct 21 '16 at 17:58
3
$\begingroup$

DISCLAIMER: This answer is incomplete, but I don't have time to make it current right now. I hope to work on it later this week.


Question:
what were the state-of-the-art methods of solving genera problems of predicting from data circa 1969?

Note: this is not going to repeat the excellent answer by 'Matt Krause'.

"State of the Art" means "best and most modern" but not necessarily reduced to practice as an industry norm. In contrast, US Patent law looks for "non-obvious" as defined by "ordinary skill in the art". The "state of the art" for 1969 was likely put into patents over the next decade.

It is extremely likely that the "best and brightest" approaches of 1969 were used or evaluated for use in ECHELON (1) (2). It will also show in evaluation of the other, quite mathematically capable superpower of the era, the USSR. (3) I takes several years to fabricate a satellite, and so one would also expect that the technology or content for the next ~5 years of communication, telemetry, or reconnaissance satellites to show the state of the art of 1969. One example is the Meteor-2 weather satellite started in 1967 and with preliminary design completed in 1971. (4) The spectrometric and actinometric payloads engineering is informed by the data-processing capabilities of the day, and by the envisioned "near-future" data handling of the time. The processing of this sort of data is where to look for best practices of the period.

A perusal of the "Journal of Optimization Theory and Applications" had been operating for several years and has its contents accessible. (5) Consider this (6) evaluation of optimal estimators, and this one for recursive estimators. (7)

The SETI project, started in the 1970's, was likely using lower budget technology and techniques that were older to fit the technology of the time. Exploration of the early SETI techniques can also speak to what was considered leading around 1969. One likely candidate is the precurser to "suitcase SETI". The "suitcase SETI" used DSP to build autocorrelation receivers in ~130k narrow-band channels. The SETI folks were particularly looking to perform spectrum analysis. The approach was first used offline to process Aricebo data. It was later connected it to the Aricebo radio telescope in 1978 for live data and result were published the same year. The actual Suitecase-SETI was completed in 1982. Here (link) is a block diagram showing the process.

The approach was to use off-line long-Fourier transforms (~64k samples) to search bandwidth segments including handling chirp, and real-time compensation for Doppler shift. The approach is "not new" and references were provided including: See, for instance,

A. G. W. Cameron, Ed., 
In- terstellar Communication 
(Benjamin, New York,1963); 

I. S. Shklovskii and C. Sagan, 
In-telligent Life in the Universe 
(Holden-Day, San Francisco, 1966); 

C. Sagan, Ed., 
Communication with Extraterrestrial Intelligence 
(MIT Press, Cambridge, Mass., 1973); 
P. Morrison, J.

B. M. Oliver and J. Billingham, 
"Project Cyclops: A Design Study of a System for Detecting Extraterrestrial Intelligent Life," 
NASA Contract. Rep. CR114445 (1973). 

Tools used for prediction of the next state given the previous state that were popular at the time include:

  • Kalman (and derivative) filters (Weiner, Bucy, nonlinear...)
  • Time series (and derivative) methods
  • Frequency domain methods (Fourier) including filtering, and amplification

Common "keywords" (or buzz-words) include "adjoint, variational, gradient, optimal, second order, and conjugate".

The premise of a Kalman filter is optimal mixing of real world data with an analytic and predictive model. They were used for making things like missiles hit a moving target.

$\endgroup$
  • $\begingroup$ Thanks for writing that up--I like the application-driven approach you took! $\endgroup$ – Matt Krause Oct 28 '16 at 0:23
  • $\begingroup$ @MattKrause - I still have a bit to put into it. I figured that the application driven approach would serve the "archaeology of mathematics" in this case. We will see. The work makes me want to build a "suitcase-SETI" and use it to look around my human environment for life, just to get an idea of what the tools of 50 years were doing. $\endgroup$ – EngrStudent - Reinstate Monica Oct 28 '16 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.