Machine Learning

Imperial College London

Nuri Cingillioglu

Part 1: Atomic Unit of Thought

Opening Act: Mini-MNIST

Can machines think?

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." Alan Turing (1912-1954)

COMPUTING MACHINERY AND INTELLIGENCE

Turing, A.M. (1950). Computing machinery and intelligence. Mind, 59, 433-460.

Many ways to think about intelligence

  • Optimisation Theory
  • Statistics
  • Probabilistic Modelling
  • Information Theory
  • Cognitive Science
  • Neuroscience
  • Operations Research
  • Biology

This module asks the question: How to build an artificial brain? We will touch on these different fields of study.

  • We will have good moments.
  • We will have bad times.
  • And there will Agly (deliberate typo).

My take on this course

ML is a mess. I will try my best to guide you through it.

  • All slides are hand-written (probably last time ever)
  • All diagrams and demos are AI generated.

My background

  • MEng, PhD at Imperial. Been around for a while...
  • Neuro-symbolic AI, natural intelligence, and AGI.
  • Previous layovers at Google DeepMind, Google.
  • Passionate about teaching and innovation.

https://www.doc.ic.ac.uk/~nuric/
https://www.linkedin.com/in/nuric17/

Broadly speaking

  • Supervised Learning: Given input and output , we want to learn a function such that
    • e.g. regression, classification
  • Unsupervised Learning: Given input , we want to learn a function such that reveals some structure in
    • e.g. clustering, dimensionality reduction
  • Reinforcement Learning: Given an environment, maximise some reward signal.

What about self-supervised learning such as next token prediction?

Cool AI examples

Normally we show many cool examples of AI but you already know them. Ask an LLM to generate cool demos for you!

  • Image generation, classification
  • Text generation, reasoning, coding assistants
  • AlphaGo, AlphaFold, AlphaStar, AlphaZero, AlphaNuri...

Atomic Unit of Thought

The biological neuron is a complex system of dendrites, soma, axon, and synapses.

Biological vs. Artificial Neuron

Biological Component Computational Equivalent Role in Information Processing
Dendrites Inputs Receive incoming signals from input features or upstream neurons
Synapses Weights Modulate input strength (excitatory / inhibitory , simplified)
Soma (Cell Body) Pre-activation Spatially and temporally integrates weighted inputs
Axon Hillock Activation function Evaluates all-or-none firing threshold (action potential)
Axon & Terminals Output prediction Transmits output signal to downstream units

The Perceptron (1958)

Rosenblatt, F. (1958). "The perceptron: A probabilistic model for information storage and organisation in the brain". Psychological Review. 65 (6): 386–408. https://doi.org/10.1037%2Fh0042519

Perceptron

We'll start our journey in 1958 with the following equation:

where is the activation function, is the weight vector, is the input vector, and is the bias. We can also absorb into the weight vector by adding an extra 1 to .

In 1958, the activation function was the Heaviside step function:

Let there be DATA

We organise data into a matrix and a vector

For example, consider logical AND:

then a single data point is and . Usually, capital bold is matrix, lower case bold is vector and lower case is scalar.

It is difficult to find a single convention to write these equations and they vary between textbooks. My advice just go with it.

Let there be learning

where is the learning rate, is the true label, and is the predicted label.

Error Prediction State Weight Update Action
False Negative () (pulls towards )
False Positive () (pushes away from )
Correct classification No change to

Very underwhelming to say machine learning is just an equation we update. If this upsets you, be prepared for disappointment.

Learning in action

What about XOR?

Minsky & Papert, 1969

What could they have possibly done to start the AI winter?

Perceptrons: An Introduction to Computational Geometry By: Marvin Minsky, Seymour A. Papert

XOR Contradiction: 1. Setup
0 0 0
0 1 1
1 0 1
1 1 0

Perceptron Classifier

A single-layer perceptron classifies via an affine hyperplane threshold:

XOR Contradiction: 2. Four Inequalities

Assume there exist real parameters such that the perceptron correctly classifies all 4 XOR inputs:

Input Target Condition Inequality Label
0
1
1
0

3. Deriving the Contradiction

Summing Class 1 ()

Add inequalities (2) and (3):

Summing Class 0 ()

Add inequalities (4) and (1):


Hint: Notice that the left-hand sides of (A) and (B) are identical!

4. Contradiction

Comparing (A) and (B)

Define . The simultaneous system requires:

Conclusion

A real scalar cannot be strictly positive and non-positive simultaneously:

A single-layer perceptron cannot compute the XOR function!

Show me the code: Perceptron

sklearn is a popular library for machine learning in Python. All the classic non-deep learning algorithms you might ever use or don't use are in there.

from sklearn.linear_model import Perceptron

# Logical AND truth table
X = [[0, 0], [0, 1], [1, 0], [1, 1]]
y = [0, 0, 0, 1]

clf = Perceptron()
clf.fit(X, y)

print("Predictions:", clf.predict(X))  # [0, 0, 0, 1]
print("Accuracy:   ", clf.score(X, y))    # 1.0

k-Nearest Neighbours

Would you believe that the simplest non-trivial algorithm can solve XOR? Easy.

1. Neighbourhood Identification

Given training set and query point , find the closest instances :

For (closest example):

2. Decision Rule

Majority Voting (Classification):

Class Probability Estimate:

Mean Value (Regression):

k-Nearest Neighbours: Geometric Intuition

  • 1-NN Voronoi Tessellation: Partitions the space into convex polyhedra. Each cell shares the label of its generating point.
  • Solves XOR naturally: Non-linear decision boundaries emerge from local piecewise linear facets!

What does "near" mean?

The notion of similarity or distance is key to many machine learning algorithms.

Let me repeat that: It is very very important to be able to measure similarity of things.

You have probably seen different distance metrics before:

  • Manhattan distance:
  • Euclidean distance:
  • Chebyshev distance:

It is very very important to be able to measure similarity of things.

Minkowski Distance: -norms

Minkowski Distance ( norm): General family parameterised by :

Show me the code: -Nearest Neighbours

Unlike the Perceptron, 1-NN solves non-linearly separable XOR easy peasy:

from sklearn.neighbors import KNeighborsClassifier

# Non-linearly separable XOR
X = [[0, 0], [0, 1], [1, 0], [1, 1]]
y = [0, 1, 1, 0]

knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X, y)

print("Predictions:", knn.predict(X))  # [0, 1, 1, 0]
print("Accuracy:   ", knn.score(X, y))    # 1.0

Instance-Based vs. Model-Based Learning

Compare where is number of data points and is input / model dimensionality:

Model-Based

Example: Perceptron, Neural Networks

  • Training (): Learns a compact model from data.
  • Inference (): Fast; evaluates . Training data can be discarded.
  • Memory (): Fixed, independent of dataset size .
  • Inductive Bias: Strong model assumptions (e.g. linear boundary).

Instance-Based

Example: -Nearest Neighbours

  • Training (): Stores training instances in memory.
  • Inference (): Scans examples at query time.
  • Memory (): Grows linearly with dataset size .
  • Inductive Bias: Weak, local assumptions (nearby points).

Why Model-Based?

Everything we will look at will almost exclusively be model-based. WHY?

Because it generalises patterns from data into a compact mathematical function, allowing for much faster predictions and lower memory usage at scale.

  • After all, we don't carry a copy of the world to live, i.e. to identify a chair I don't need to recall every chair I've seen in my life.

What we mean by model is some fittable set of parameters or that map from a representation of data to a prediction.

But how does your brain learn? There seems to be some memorisation, e.g. for the exam?

Pillars of Machine Learning

  • Model: where are the learnable parameters like weights and biases.
  • Data: or for unlabelled data.
  • Task: Objective, Loss, Cost: something like

The idea is to improve model parameters using such that we improve on the task. In other words, machine learning.

If your task is to estimate human lifespan using data that contains smokers who live longer than non-smokers, machine will learn ...

If the brain is the model, and the world is the data, what was the task you were improving on all this time???

Importance of Data

Data is everything.

  • Numerical Data: tables, vectors, tensors, audio waveforms, pixel values, sensor readings
  • Text Data: natural language documents, sentences, words, tokens
  • Image Data: photographs, medical scans, satellite imagery
  • Graph Data: social networks, molecule structures, citation networks
  • Time Series Data: stock prices, sensor readings, weather measurements
  • Video Data: sequences of images with temporal dependencies
  • Tabular Data: rows and columns, spreadsheets, CSV files
  • Data Data: data and more data, internet scale data

Everything becomes a number

All data at the end becomes a number a machine can process:

  • Images are turned into pixels with values between 0 and 255 (or other values)
  • Text are turned into tokens which are turned into embeddings (vectors of numbers)
  • Audio are turned into spectrograms or other numerical representations
  • Graphs are turned into adjacency matrices or other numerical representations
  • etc.

Two Types of Data

We mainly worry about two types of data:

  • Continuous Data: real numbers, real-valued data that can take any value within a given range. These are things we usually measure.
    • e.g. height, weight, temperature, price, stock value, sensor stuff
  • Discrete Data: integer values, data that can only take specific values. These are things we usually count.
    • e.g. tokens, word counts, user IDs, ratings (1-5), on/off states

By applying thresholds one can turn continuous data into discrete data, e.g. age groups.

MNIST

Modified National Institute of Standards and Technology database (CC BY-SA 4.0, Josef Steppan)

Data Addiction

Academic Benchmarks

  • MNIST (1998, Vision): greyscale digits ()
  • CIFAR-10 (2009, Vision): colour images ()
  • ImageNet (2012, Vision): images across classes
  • LibriSpeech (2015, Audio): English speech

Web-Scale & Foundation Era

  • English Wikipedia (Text): High-quality text dump ( words)
  • The Pile (2020, Text/Code): Curated diverse corpus
  • LAION-5B (2022, Multimodal): image-text pairs
  • Common Crawl (Web): Petabyte-scale monthly crawls ( tokens)

From a floppy disk () to the entire open web (), data hunger has grown by over !

This is it

We will explore this landscape in the following weeks. So stay tuned to this radio channel!