Appunti AI: Machine Learning and Pattern Recognition

K-means

K-means is an algorithm developed for clustering tasks. In simple words, upon a given set of observations, k-means searches for k groups of tightly similar observations. This is estimated by considering the minimum distance among k possible centroids, which are iteratively updated based on the newly assigned observations. The term "k-means" was first used in 1967, but the idea dates back to Hugo Steinhaus in 1956.

The General Problem Solver

Similar to the Logic Theorist, the General Problem Solver was conceived to perform general problem-solving, e.g., automated theorem proving or Tower of Hanoi games. In contrast, the algorithm exploits a new search method, called mean-ends analysis, which limits the search for the correct solution in order to keep the algorithm computationally efficient.

The Perception

Another important milestone was reached in 1957, when the psychologist Frank Rosenblatt designed a new type of artificial neuron, inspired by the design of the McCulloch and Pitts neuron. Rosenblatt's neuron, called Perceptron, had the ability to automatically update its synaptic weights, based on some input and some expected output. The update was performed following the principles of Hebbian Learning, through the Delta rule which activates the update every time the neuron misclassifies the input. Rosenblatt's neuron is at the basis of the modern research in deep learning. Eventually, multiple perceptrons can be combined in stacks, connected together to form a multilayer perceptron, to perform complex classification/regression tasks.

Support Vector Machine

SVM is an algorithm developed by two Russian scientists Vladimir Vapnik and Alexey Chervonenkis. The algorithm can be seen as an extension of the Perceptron, with the additional requirement that the learned separating boundary must be equally far from the point nearest to the boundary. In 1992, SVMs were further extended to deal with non-linearly separable data, by using the "kernel-trick".

Computational Complexity Theory

Theoretical computer scientists soon realized that not all the decidable problems were easily solvable in practice. In other words, with a linear increase of the input size some problems were insignificantly increasing their amount of computational time, while others were computationally infeasible. From these considerations, Harmanis and Sterns wrote "On the Computational Complexity of Algorithms", establishing the basic concepts of the computational complexity theory. Later, in 1971, Cook and Levin proved the existence of computationally intractable problems, called NP-Complete. This result effectively pushed the community into embracing a paradigm shift, searching for approximate solutions to NP-complete problems, instead of directly solving them.

Fukushima’s Neocognitron

Inspired by early studies on the cat visual cortex, the Japanese Kunihiko Fukushima introduced a new connectionist architecture, the Neocognitron. This model introduces two important layers that were successively used in the CNN, proposing various methods for the network weights training during the following years.

Hopfield Network

Hopfield networks named after its inventor, introduced a new kind of neural model in the field of connectionist AI, named RNN. This model repeatedly sends its output back as new input to re-process it, and updates its weight according to Hebbian learning rules, giving the ability to "remember" states by associate memory. A Hopfield network has been successfully used to solve problems such as the travelling salesman problem.

WordNet

With the improvement of computer hardware and the development of more efficient learning algorithms, the need for more learning data contextually increased and the dataset size started increasing. One notable example is provided by the WordNet project. Started by George Miller in 1985, WordNet aimed to provide a large lexical database of English words grouped into sets of cognitive synonyms and interlinked according to semantic and lexical relations. WordNet has been efficiently used in a number of NLP tasks.

Backpropagation

In 1986 Rumelhart, Hinton, and Williams addressed a well-known limitation regarding the difficulty to train MLPs. In their paper, the authors popularised a previously used method, named backpropagation that consists in the application of the derivative chain rule to apply the gradient descent algorithm for the weight update. Backpropagation helped connectionist AI in gaining popularity again, after the first AI winter.

CNN

Another interesting achievement in machine learning is convolutional neural networks. Inspired by Fukushima’s neocognitron, the researcher Yann LeCun proposed this new kind of connectionist architecture to recognize hand-written ZIP code numbers and used the backpropagation algorithm to train the network. CNN are nowadays still a method of choice for almost all computer vision tasks.

Vanishing Gradient

The 90’s attested another AI winter, mainly due to the discovery of the vanishing gradient problem. Sepp Hochreiter illustrated the problem in his diploma thesis. In particular, the researcher described the dampening effect generated by some activation functions to the backpropagation error, slowing down the convergence of neural networks such as MPLs.

Kernel Methods

Kernel Methods arose in the '90s. They do not learn weights but instead store a labeled subset of observations and classify a new instance based on its similarity with the subset's observations. The similarity is computed by means of a kernel function, which is suitable for fast computation.

IBM Deep Blue Beats Kasparov

On February 10-17, 1996, the American company IBM organized a match against the world chess champion Garry Kasparov and a computer-chess algorithm developed in the previous decade, Deep Blue. The match terminated with a 4-2 for the Russian champion. However, in May 1997, a second match was organized, where an updated version of the algorithm was successfully able to beat Kasparov. This event is perhaps one of the most known in artificial intelligence history and soon decorated the start of a new era where AI was considered "mature" enough to compete with human thinking.

ImageNet Challenge

In 2006, the researcher Fei-Fei Li started working on the creation of a large public image dataset with the aim of providing more accessible data for machine learning research. Her vision concretized in the creation of ImageNet, a dataset containing 14 million images with more than 20,000 categories. In addition, a subset of 1000 classes was selected to propose an image classification challenge, which soon became popular in the computer vision research field. With its huge size, ImageNet effectively helped the transition into the deep learning paradigm.

AlexNet

AlexNet, named after one of its designers, Alex Krizhevsky, is a deep neural model that is considered a milestone in the computer vision research field. This model was one of the first GPU-implemented neural models to achieve "superhuman" performance in the ImageNet challenge. AlexNet effectively started a new "AI spring" of connectionist models, with the main effect of pushing the AI community to gradually adopt deep architectures.

Word2Vec

In 2013, the Google team led by Tomas Molotov, proposed a group of related models, called Word2Vec, able to compute effective word embeddings for various NLP tasks. The model is simple yet effective, and it employs a one-layer.

AlphaGo Beats Human Go Players

From a computational point of view, the game of Go is more difficult to learn because of its huge number of possible moves, compared to chess. Thus, the standard computer-chess algorithms were able to beat amateur Go players only. In 2015, however, Google’s DeepMind team proposed a new model, AlphaGo, which was able to beat several professional players. To achieve this goal, the DeepMind team used a combination of reinforcement learning, deep learning, and tree search. AlphaGo proved the effectiveness of the reinforcement learning approach for addressing complex games such as Go, but also incomplete information games such as poker, or even video games.

The Bitter Lesson

On March 2019, the researcher Richard Sutton published a blog post entitled The Bitter Lesson, where he described his personal point of view on the actual situation in the machine learning community. In particular, Sutton notices that much of the improvements in the history of machine learning are due to an increment of computational power. The result is that the most effective methods are those that leverage a massive computational power to perform simple algorithms such as tree search. Sutton thus encourages the researchers to change their mindset and instead of focusing on the implementation of their knowledge model, they should focus on scalable models based on search and learning.

GPT-3

GPT-3 is the third version in a series of generative models based on the transformer architecture and it is used for addressing NLP tasks. Since its debut, GPT-3 impressed the public with its amazing performance and has been used in a wide variety of applications, including AI-paired programming.

What is Machine Learning?

ML is a complex, evolving field of research. As such, the organization of ML knowledge has not been fully established yet. Its interdisciplinary nature usually poses more than a difficulty to newcomers, and the subject can be addressed from different points of view.

The Various Modalities of Information

Human learning comes from the observation of real-world information. Accordingly, every ML algorithm learns from the wide variety of data that can be digitized.

One of the most common information elaborated by ML algorithms are images. Because of their immediacy, images are one of the primary sources of learning during childhood. Visual concepts spontaneously arise upon a quick look at an image, thanks to the capacity of our brain to process and correlate visual stimuli while filtering out unneeded information. Such sophisticated ability has been the subject of study and modelization since the very start of ML research.

Consider the following image: your computer displays it as a set of colored dots, called pixels. Each pixel is represented as a triplet of three values, and their combination encodes a color intensity (orange, brown, red, etc.). The first thing you note is that the image contains a cute pig. This task is often referred by the machine learning community as Image Classification or Object Recognition, and, roughly, consists in describing the image in its entirety.

You can move one step forward and describe the image in more detail, by telling where the pig is located in the image, as follows: This task is referred to as object detection and consists in localizing the object in the image by providing the pixel coordinates of an area where the object is located. This can be done by providing four values, representing the left and right corners of a rectangle, e.g., (10, 15) (20, 30).