SECTION 02 / 10
Algorithms at scale
On this page 3 headings
Learning goal: Understand why algorithms use randomness to handle large datasets.
- The ideaYou already know how to classify, cluster and reduce data (PCA, nearest neighbour, SVM…).
- This course asks what happens when the data is huge: millions of points or millions of features.
- The surprising answer it builds towards is that tossing coins inside your algorithm can make it much cheaper, and probability lets you prove the result is still good.
Key statement
- Algorithms for Data Science → Scale, Graphs
- Assumed background: PCA / SVD, basic classification algorithms
- Foundations: Prob | LA | Opt (probability, linear algebra, optimisation)
- Randomization as a tool to deal with scale.
Worked example: what "scale" means
Consider this example: words, each a vector of numbers.
- Storing the data: numbers, about 40 GB in 4-byte floats.
- Number of pairs of points: .
One squared distance in d dimensions takes about d multiplications.
All pairwise distances: operations.
If we could work in k = 2,000 dimensions instead, every distance becomes 5× cheaper and storage drops 5×.
If d were , the saving would be 500×.
Check yourself
In this course, what is randomness used for?
- As a tool inside the algorithm to reduce computation on huge data.
- It is not just for modelling uncertainty in the data.
Name the two big themes of the course.
Scale (many points or features) and graphs.
Key points to remember
- Large numbers of points and features make computations expensive.
- Randomization can reduce work while probability bounds control the risk.