IB COMPUTER SCIENCE | A4.2.3 Dimensionality Reduction (HL)

Lesson objective

Describe why reducing input dimensions can address sparsity, distance, overfitting, computation, memory and visualisation challenges while preserving relevant information.

Learn

A4.2.3 | DIMENSIONALITY REDUCTION (HL ONLY)

01 | MORE INFORMATION IS NOT ALWAYS MORE UNDERSTANDING

Imagine describing each delivery using planned distance and number of stops. Now add hundreds of route measurements, duplicated unit conversions, sensor readings and administrative codes. You have more numbers, but have you made the prediction easier?

Sometimes extra inputs reveal important patterns. Sometimes they repeat information or add noise, making examples harder to compare and patterns easier to mistake for coincidence. Dimensionality reduction represents data using fewer input dimensions while aiming to preserve information relevant to the task.

This HL lesson builds on feature selection. You will see why a large number of dimensions can create difficulties, how a reduced representation can help and why reducing too far can lose the very information a model needs. No PCA or LDA mathematics is required by this syllabus.

02 | WHAT IS A DIMENSION IN A DATASET?

A dimension is one coordinate used to represent an example. With inputs DistanceKm and PlannedStops, a delivery is described by two numbers: a point in a two-dimensional feature space. A third input, ParcelMassKg, adds a third coordinate.

The word “dimension” here does not mean the physical size of the van. It means an input quantity in the representation. We can store 100 input dimensions in a table even though we cannot draw 100 perpendicular axes on a classroom board.

One row is one example; the input columns provide its coordinates. The outcome to predict is the target and is not counted as an input dimension. An identifier kept for record management is also excluded unless it is actually used as a predictor.

03 | ROWS AND DIMENSIONS ARE DIFFERENT

Delivery DistanceKm input Stops input MassKg input DurationMinutes target
D201 5 2 12 24
D202 8 1 10 30
D203 4 3 15 26
D204 12 2 8 42

There are four examples and three input dimensions. DurationMinutes is the target. Delivery is a row identifier, not an input in this example.

Removing MassKg from the model representation gives four examples with two input dimensions. Removing D204 instead gives three examples with three input dimensions. Only the first operation reduces dimensionality.

A category can expand into several input columns when encoded. For example, one-hot encoding an area field into indicator columns can increase the number of representation dimensions. Count the actual model inputs, not just the original spreadsheet headings.

04 | FROM TWO COORDINATES TO A POINT

Suppose the horizontal coordinate is planned distance and the vertical coordinate is number of stops. Deliveries with similar values can lie near one another on a scatter plot. This gives a visible meaning to “nearby examples”.

An extra feature adds another direction in which points can differ. With enough useful examples and a suitable model, that can help. But with many varying inputs and limited data, it becomes harder to find examples that are close across all relevant coordinates.

The problem is not that computers cannot store a high-dimensional point. The problem is whether the available examples adequately support useful comparisons and reliable learning in that representation.

05 | THE CURSE OF DIMENSIONALITY

The curse of dimensionality describes difficulties that arise as the number of dimensions grows. For a fixed number of examples, data can become sparse across the larger space. Learning reliable local patterns can then require many more examples.

Consequences can include overfitting, less useful distance comparisons, greater computation, higher memory use and difficulty visualising the data. These effects are related, but they are not identical.

High-dimensional data is not automatically unusable. Relevant information may occupy a much simpler structure, and some models handle particular high-dimensional representations effectively. The difficulty depends on the data, task and algorithm, not a universal maximum number of columns.

06 | A SIMPLE WAY TO SEE SPACE GROW

Imagine dividing each input’s range into five bins. With one dimension there are 5 possible cells. With two dimensions there are 5 × 5 = 25 combinations. With three there are 5 × 5 × 5 = 125.

With d dimensions and b bins per dimension, the grid contains bᵈ cells. This is a simplified coverage illustration, not a requirement that a real model use bins or that the data occupy every cell.

Dimensions Bins per dimension Possible cells
1 5 5
2 5 25
3 5 125
6 5 15625
10 5 9765625

The number of possible coordinate combinations grows quickly even though each feature has only five intervals. Keeping 1000 examples does not keep the same coverage of this growing grid. Correlated features or constrained data may occupy only a small part of it.

07 | SPARSITY MEANS THIN COVERAGE HERE

With 1000 observations and 25 grid cells, the arithmetic average is 40 observations per cell. With the same 1000 observations and 15,625 cells, the average is only 0.064 per cell. Many cells must be empty in that second grid.

These averages do not tell us how examples are actually distributed. Observations can cluster unevenly, and several may fall into the same cell. The comparison demonstrates why limited examples may provide weak local coverage as dimensions increase.

Here, data sparsity means thin coverage of the feature space. It is distinct from a sparse matrix whose stored values are mostly zero. A dataset can have no zero values and still cover its feature space sparsely.

08 | EXPLORE COVERAGE AND STORAGE

Change the dimension count, bins and number of examples. The calculator shows the simplified grid size and the raw storage for a dense table of four-byte numeric inputs. It does not train a model or determine the sample size required by a real task.

Try changing only dimensions from 2 to 6. Notice that grid cells grow exponentially under this construction, while raw table storage grows linearly with the number of columns. These are different costs and should not be confused.

09 | WHY MORE EXAMPLES MAY BE NEEDED

A model needs evidence about relationships, including the combinations it will encounter after deployment. If examples are spread across many varying inputs, a small sample may contain few relevant neighbours for a new observation.

In the grid illustration, maintaining an average of two examples per cell needs 50 examples for 25 cells, but 31,250 for 15,625 cells. This describes a chosen uniform-coverage target for the illustration; it is not a general machine-learning sample-size formula.

Real requirements depend on noise, model complexity, how the inputs relate, the desired reliability and which regions matter. Collecting more data can help, but reducing irrelevant or redundant dimensions can also make existing evidence more useful.

10 | DISTANCE CAN BECOME A POOR GUIDE

Many methods compare examples using a distance metric, a rule for measuring how far apart points are. Euclidean distance combines coordinate differences: square each difference, add the squares and take the square root.

When many irrelevant, varying inputs are added, their contributions can overwhelm differences in genuinely useful inputs. In some high-dimensional distributions, nearest and farthest distances also become more similar in relative terms, weakening the contrast between “near” and “far”.

This is not a rule that every high-dimensional dataset has equal distances. Scaling, feature relevance, dependence between inputs and the chosen metric all matter. Dimensionality reduction aims to improve the representation, not merely shrink every numerical distance.

11 | WATCH AN IRRELEVANT INPUT CHANGE THE NEAREST EXAMPLE

Suppose useful feature U is on a comparable numeric scale to an unrelated noise measurement N. We want a nearby delivery in U. Query Q = (5, 0), candidate A = (6, 10), and candidate B = (9, 0).

Comparison Using useful U only Using U and noise N
Q to A |6 − 5| = 1 √(1² + 10²) = √101 ≈ 10.05
Q to B |9 − 5| = 4 √(4² + 0²) = 4
Nearest candidate A B

A is closer in the useful measurement. Adding this irrelevant noise coordinate makes B appear nearer under the two-input Euclidean metric. This constructed example shows a possible failure, not a measured rate at which real neighbours change.

Removing the irrelevant coordinate restores A as nearest under this rule. If N were actually useful, discarding it could instead be a mistake. Relevance and validation determine whether a reduction is appropriate.

12 | MORE INPUTS CAN CREATE MORE WAYS TO OVERFIT

With many candidate inputs and limited examples, a flexible model can find accidental relationships. A pattern that happens to describe the training sample may fail on future deliveries. This is overfitting.

Reducing irrelevant or redundant inputs can constrain these opportunities and make useful patterns easier to estimate. It may improve generalisation, meaning performance on genuinely new examples from the intended population.

Reduction alone is not a guarantee. A reduced representation can still overfit, and removing useful distinctions can cause underfitting. Compare complete pipelines with appropriate validation rather than judging only training performance or number of remaining columns.

13 | COMPUTATION AND MEMORY ARE PRACTICAL LIMITS

A dense table of n examples and d four-byte inputs uses n × d × 4 bytes for its raw numeric entries. For 10,000 examples and 100 inputs, that is 4,000,000 bytes. With 20 inputs, it is 800,000 bytes: an 80% reduction in this raw table.

These figures exclude column metadata, labels, identifiers, model parameters, temporary arrays and software overhead. A reduced representation may need a fitted transformation and extra processing too. Do not interpret the raw-table saving as an exact whole-application memory saving.

Comparing one query with every stored example using all coordinates performs work that grows with n and d in a straightforward distance scan. Reducing d can reduce this work, but total training time and inference speed depend on the algorithm, transformation overhead and implementation.

14 | TWO WAYS TO REDUCE THE REPRESENTATION

Approach What changes Example
Feature selection Retains a subset of original inputs Keep distance and stops; omit redundant distance-in-metres
Feature extraction or transformation Constructs fewer new coordinates from original inputs Combine closely related measurements into a suitable summary

Selection preserves the meaning of retained original columns. Extraction can combine information, but a new coordinate may be less immediately interpretable. Both can reduce dimensionality when the resulting number of inputs is smaller.

Normalization or standardization changes scale without necessarily changing the number of inputs. Deleting delivery rows changes the sample count. Neither operation alone is dimensionality reduction.

15 | A LOSSLESS REDUCTION IN A VERY SIMPLE CASE

Suppose an input table contains distance in kilometres and the same exact distance in metres. A delivery represented as (8, 8000) lies on the relationship metres = 1000 × kilometres.

Although there are two stored coordinates, one independent number is enough to express these exact measurements. Keeping kilometres alone preserves the original distance information because metres can be reconstructed by multiplying by 1000.

This is a simple example of lower intrinsic dimensionality: the underlying independent variation is smaller than the number of stored coordinates. Real measurements can include noise, so exact reconstructability must not be assumed for merely correlated features.

16 | A SIMPLE SUMMARY CAN ALSO LOSE INFORMATION

Two route sensors record travel-time estimates. For one delivery the estimates are 10 and 14 minutes; for another they are 11 and 13. Both have an average of 12 minutes.

Replacing the pair by its average reduces two inputs to one. It preserves their central value but loses the difference between them. If the disagreement is a useful warning about uncertain routes, the average alone discards relevant evidence.

A reduction is good only relative to what needs to be preserved. Keeping a broad statistical pattern is not automatically the same as keeping the information needed to predict the target or protect a rare class.

17 | VISUALISATION: SEE PATTERNS, BUT CHECK WHAT DISAPPEARS

Humans can inspect a two-dimensional scatter plot much more easily than a table with 100 inputs. A reduced view can help reveal groups, unusual examples and possible collection problems.

However, a projection can place distinct observations on top of one another. Two deliveries can have identical distance and stops yet different parcel mass. If the plot displays only distance and stops, that difference becomes invisible.

Two deliveries overlap when mass is omitted from a scatter plot Distance is the horizontal axis and stops the vertical axis. Delivery A and B share distance eight kilometres and two stops, so their plotted coordinates coincide. Their masses, four and twenty kilograms, differ and are omitted. Distance (km) Stops 2 8 A and B occupy the same plotted point
A: 8 km, 2 stops, 4 kg. B: 8 km, 2 stops, 20 kg. The two displayed inputs do not show the mass difference.

An attractive two-dimensional plot is evidence about that view, not proof that every relationship in the original data has been preserved. Some visualisation transformations also distort distances. Validate the representation for its actual purpose.

18 | WHAT SHOULD BE PRESERVED?

For a prediction task, preserve the distinctions and relationships that help predict valid future outcomes. For an exploratory plot, preserving useful neighbourhoods or group structure may matter. For storage, reconstruction quality may be relevant.

These goals can conflict. A feature with small overall variation could still separate an important rare condition. Removing it to create a compact view can harm that condition’s detection even if the broad pattern looks unchanged.

There is no universal percentage of dimensions that should be removed. Choose the number and method using task-appropriate validation, resource constraints and meaningful checks, including relevant subgroup or rare-case outcomes.

19 | FIT THE REDUCTION WITHOUT LEAKING THE TEST SET

A feature selector or learned transformation is part of the modelling pipeline. Learn its rules using training data; apply the fitted rule unchanged to validation, test and future prediction inputs.

When comparing reduction settings using cross-validation, refit the reduction within each training fold. Fitting a representation once on the entire dataset before evaluating held-out folds can use information those folds should not contribute.

Keep the final test data out of choices about the method or number of dimensions. Record the selected inputs or transformation, their order and any required scaling, so deployment uses the same meanings as training.

20 | COMPARE COMPLETE PIPELINES

Pipeline Inputs to predictor Illustrative validation MAE Interpretation
Original representation 100 6.4 min Baseline for this comparison
Moderate reduction 20 5.8 min Better validation error in this supplied example
Very strong reduction 2 8.1 min Important predictive detail may have been lost

These fictional results demonstrate how to reason about a comparison; no model was trained to generate this table. Lower mean absolute error is better for this duration metric. Twenty inputs performs better here, but it is not a universal optimum.

Also measure transformation cost, inference time, memory and stability across suitable validation runs. A tiny improvement on one split may be noise. A cheaper pipeline with slightly different error may be acceptable under a task’s defined constraints, but the choice needs justification.

21 | CHECK THE CONCEPT IN CONTEXT

Classify each situation by its main dimensionality concept. Some situations involve several issues; choose the one that directly explains the stated observation.

22 | BUILD A CLEAR EXAM DESCRIPTION

A strong description links the representation to a consequence: “With many varying inputs and few examples, data can be sparse in the feature space. This leaves fewer nearby examples for reliable local comparisons, so more data may be needed.”

Then describe the role of reduction: “A smaller representation can remove redundant or irrelevant information, reducing computation and memory while retaining useful patterns.” Include a limit: “If relevant distinctions are lost, predictive performance can fall.”

Cover the syllabus considerations: overfitting, computational complexity, data sparsity, effectiveness of distance metrics, visualisation, sample-size needs and memory usage. PCA and LDA statistical techniques are beyond this course’s scope; understanding the purpose and trade-offs is the priority.

Further reading: dimensionality, distance and nearest-neighbour computation and selection as a way to reduce input dimensions.

MATCH THE DIMENSIONALITY IDEA TO ITS ROLE

Terminology

Terminology

Dimension

One coordinate in an example’s model-input representation.

Dimensionality

The number of input dimensions used to represent an example.

Feature space

The space of possible input-coordinate combinations.

Example

One observation represented by its input coordinates.

Target

The outcome to predict, excluded from the input-dimension count.

Dimensionality reduction

Using fewer input dimensions while aiming to preserve relevant information.

Curse of dimensionality

Difficulties such as sparse coverage and costly learning as dimensionality increases.

Data sparsity

Here, thin coverage of the feature space by available examples.

Sparse matrix

A representation whose values are mostly zero; distinct from thin space coverage.

Bin

An interval or category used to partition a coordinate in a coverage illustration.

Grid cell

A combination of coordinate bins in the simplified coverage illustration.

Distance metric

A rule for measuring separation between examples.

Euclidean distance

The square root of the sum of squared coordinate differences.

Neighbour

An example considered close to another under a chosen representation and metric.

Distance concentration

A tendency in some high-dimensional settings for relative near/far distance contrast to weaken.

Irrelevant feature

An input adding no useful predictive information for the intended task.

Redundant feature

An input repeating information already represented elsewhere.

Overfitting

Learning training-specific patterns that do not reliably generalise.

Generalisation

Performance on genuinely new examples from the intended population.

Underfitting

Failure to capture useful patterns because the fitted representation or model is too restrictive.

Feature selection

Retaining a subset of original input attributes.

Feature extraction

Constructing transformed input attributes, potentially combining original inputs.

Intrinsic dimensionality

The number of independent degrees of variation underlying the data.

Projection

Mapping examples into another coordinate representation, often with fewer dimensions.

Information loss

Loss of distinctions or relationships during a transformation or selection.

Visualisation

A view of data intended to make patterns easier to inspect.

Dense input storage

Space used to store all entries of an input table, including zero values.

Pipeline

The sequence of preprocessing, reduction and model operations.

Data leakage

Use of information that should not legitimately influence fitting or evaluation.

Validation

Evaluation used to guide pipeline choices, kept separate from final test evaluation.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which correctly count the delivery example?
2. Which reduce input dimensionality?
3. Which describe the grid illustration?
4. Which distinguish sparsity meanings?
5. Which can affect distance comparisons?
6. Which are possible reduction benefits?
7. Which describe information preservation?
8. Which describe visualisation?
9. Which avoid leakage?
10. Which are correct resource statements?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe dimensionality using the four-delivery table.

2. Describe the curse of dimensionality.

3. Calculate the grid size for six dimensions with five bins each.

4. Describe why more examples may be required as dimensions increase.

5. Calculate which candidate is nearest in the noise example.

6. Describe how reduction can help overfitting and one limitation.

7. Calculate the raw input storage saving from 100 to 20 dimensions for 10,000 four-byte examples.

8. Describe feature selection and feature extraction as reduction approaches.

9. Describe why exact kilometre/metre duplication can be reduced without losing the measurement.

10. Describe a risk of visualising high-dimensional data in two dimensions.

11. Describe how to evaluate and deploy a learned reduction fairly.

12. Describe the balance between compactness and preserving relevant information.

DESCRIBE IT | REDUCE WITHOUT LOSING THE POINT

A delivery predictor has 100 inputs but limited examples. Describe how dimensionality reduction could help sparsity, distance comparisons, computation and memory. Include a possible information-loss risk, a validation procedure and a reason a clear two-dimensional plot does not prove the representation is suitable for prediction.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for A4.2.3 Dimensionality Reduction (HL) is coming soon. Complete the matching task and written questions in your exercise book.