What Is Machine Learning

Classical computer programs are built from an explicit algorithm: a finite, precise sequence of instructions that a programmer designs by reasoning directly about the problem. Given an input, the program applies these fixed instructions and produces an output. The correctness of the program depends entirely on whether the programmer's understanding of the problem was complete and correctly encoded. Machine learning inverts this relationship. Rather than supplying the instructions, we supply experience — a dataset of examples relevant to the problem — and a learning algorithm searches over a large space of candidate instructions (called models or hypotheses) to find one that performs well on that experience, in the hope that it will also perform well on new data drawn from the same underlying process. The canonical formal statement of this, due to Tom Mitchell, is: > A computer program is said to learn from experience $E$ with respect to some class of tasks $T$ and performance measure $P$, if its performance at tasks in $T$, as measured by $P$, improves with experience $E$. Each of the three components deserves precision. The task $T$ is what the system is ultimately asked to do — classify an email as spam, predict a house price, choose a move in a game. The experience $E$ is the data or interaction history available to the learner — a labeled dataset, a stream of unlabeled observations, or a sequence of trial-and-error interactions with an environment. The performance measure $P$ is a quantitative criterion — accuracy, mean squared error, cumulative reward — used to evaluate how well the task is being performed, and it is this measure that must improve as more experience is incorporated for the system to qualify as "learning" in this technical sense. Underlying every learning system are a few structural ingredients that recur throughout the field. A hypothesis space $\mathcal{H}$ is the set of candidate functions the learner is allowed to choose from — linear functions, decision trees, neural networks of a given architecture, and so on. A loss function quantifies the disagreement between a hypothesis's prediction and the truth on a single example. An objective (often the average loss over the training data, sometimes with a regularization term) is the quantity the learning algorithm actually optimizes. Finally, generalization is the property of interest: performing well not on the training data itself, but on new data drawn from the same distribution, which is measured through held-out validation or test data. This distinction between fitting the data at hand and generalizing beyond it is the deepest conceptual dividing line in the whole field, and it foreshadows concepts like Bias-Variance Tradeoff and Overfitting that recur in every learning paradigm.

Although specific algorithms differ enormously, essentially every machine learning system follows the same high-level procedure. It is useful to walk through this procedure once, abstractly, before specializing into supervised, unsupervised, or reinforcement settings.

Step 1 — Define the task and collect experience. Decide precisely what output is wanted (a label, a number, an action) and gather data that exemplifies the relationship between inputs and desired outputs, or simply exemplifies the structure of the input distribution if no explicit outputs are available.

Step 2 — Choose a representation and hypothesis space. Decide how inputs will be represented as vectors of features, and choose the family of functions (linear model, tree, neural network) the learner will search over. This choice encodes assumptions — an Inductive Bias — about what kinds of patterns are plausible.

Step 3 — Choose a performance measure and turn it into an objective. Translate "do well at the task" into a concrete numerical loss that can be computed on any candidate hypothesis and any example.

Step 4 — Fit the model by optimization. Use an algorithm — often a variant of Gradient Descent, or an exact combinatorial procedure for simpler models — to search the hypothesis space for a function that minimizes the objective on the training experience.

Step 5 — Evaluate generalization. Measure the performance measure on data the learner did not use for fitting, to estimate how it will behave on truly new inputs. If performance is poor, revisit the representation, hypothesis space, or amount of data, and repeat. ``` ALGORITHM GeneralLearningLoop Input: Task T, Experience E, Performance measure P, Hypothesis space H, Learning algorithm L Output: A fitted model h* that performs well on T according to P 1. (D_train, D_valid, D_test) := SPLIT(E) # partition experience 2. best_h := NULL 3. best_score := -INFINITY 4. for each candidate configuration c in H's configuration space: 5. h_c := L(D_train, c) # fit a hypothesis given config c 6. score := EVALUATE(h_c, D_valid, P) # generalization estimate 7. if score > best_score: 8. best_score := score 9. best_h := h_c 10. final_score := EVALUATE(best_h, D_test, P) # unbiased final estimate 11. return best_h, final_score ``` Two details make this pseudocode more than a toy sketch. First, the data is deliberately split into three disjoint pieces: `D_train` to fit parameters, `D_valid` to choose among hypotheses or hyperparameters, and `D_test`, touched exactly once, to report an honest final estimate of performance. Reusing `D_test` for model selection would leak information and bias the reported score upward — a mistake detailed in the pitfalls table below. Second, `L` itself (line 5) is a placeholder for an entire family of concrete algorithms — closed-form least squares, gradient descent on a neural network's weights, greedy tree splitting — each of which is the subject of its own dedicated treatment; this article's job is only to establish the shape of the loop they all live inside.

Machine learning is not a single algorithm, so "complexity" here means the shape of the resource tradeoffs that recur across the field, plus the sense in which the general loop above is a sound procedure.

Time and space complexity. Fitting a hypothesis (line 5 of the pseudocode, `L(D_train, c)`) dominates cost. For $n$ training examples with $d$ features:

• Closed-form linear regression via the normal equations costs $O(nd^2 + d^3)$ time (forming $X^\top X$ and inverting a $d \times d$ matrix) and $O(d^2)$ space, honest for small-to-moderate $d$; it becomes impractical once $d$ is large, motivating iterative alternatives.
• Gradient-descent-based fitting costs $O(nd)$ time per iteration (one pass over the data to compute a gradient) and $O(d)$ space for parameters, times the number of iterations needed to converge — which itself depends on the conditioning of the objective and is not fixed a priori.
• The outer hyperparameter search (the loop over configurations `c` in the pseudocode) multiplies whichever inner cost by the number of configurations tried, which is why model selection is often the dominant real-world cost, not any single fit.

Evaluating a fitted hypothesis on one new input, once fitting is done, is typically far cheaper than the training cost itself — often $O(d)$ for linear models — which is precisely why the expensive learning step is done once offline and the cheap "inference" step is run repeatedly at deployment.

Correctness: what does it even mean for learning to be "correct"? Unlike sorting or shortest-path algorithms, a learning algorithm cannot be judged against a single deterministic correct output, because the true input-output relationship is unknown and only observed through noisy, finite samples. The right correctness criterion is statistical: does the learned hypothesis's expected performance on the true underlying distribution, not just on the observed training sample, approach the best achievable performance as the amount of data grows? This is the question addressed rigorously by The Formal Learning Problem and by learning theory more broadly, but the essential argument can be sketched now. Suppose the training data $D_{\text{train}} = \{(x_i, y_i)\}_{i=1}^n$ is drawn i.i.d. from a fixed but unknown distribution $\mathcal{D}$, and the learner selects $h \in \mathcal{H}$ minimizing the empirical loss

By the law of large numbers, $\hat{L}(h)$ concentrates around the true expected loss $L(h) = \mathbb{E}_{(x,y)\sim \mathcal D}[\ell(h(x), y)]$ for any fixed $h$, with fluctuations shrinking at rate $O(1/\sqrt{n})$. The subtlety is that the learner does not evaluate a single fixed $h$ — it searches over all of $\mathcal{H}$ and picks whichever hypothesis looks best on this particular sample, so the fluctuation must be controlled uniformly over the whole space, not just pointwise. This uniform control is exactly what tools such as VC dimension and Rademacher complexity supply, and it is what justifies the separate validation split in the pseudocode: choosing among hypotheses using data disjoint from the data used to fit them prevents the "look best on this sample by luck" failure mode from contaminating the final estimate.

Honest tradeoffs. More expressive hypothesis spaces $\mathcal{H}$ can fit the training data better (lower $\hat{L}$) but require more data to guarantee that low training loss implies low true loss — the Bias-Variance Tradeoff. There is no free lunch: no single hypothesis space or algorithm generalizes best across all possible tasks, so choosing $\mathcal{H}$ is itself an inductive assumption about the problem, not a purely mechanical decision. This is why "collecting more data" and "restricting the hypothesis space" are both, in different regimes, valid remedies for poor generalization, and why neither is universally correct.

Consider a tiny, fully worked instance of the general loop: predicting a house's price from its size, using five historical sales as experience.

Step 1 (task & experience). $T$ = predict price given size. $E$ = the five $(x,y)$ pairs above. $P$ = mean squared error (MSE) on new sales.

Step 2 (hypothesis space). Choose linear functions $h(x) = w_1 x + w_0$ — a deliberately simple $\mathcal{H}$ for a five-point illustration.

Step 3 (objective). Minimize $\hat{L}(w_0, w_1) = \frac{1}{5}\sum_i (w_1 x_i + w_0 - y_i)^2$, i.e. ordinary least squares.

Step 4 (fit). Using the standard least-squares formulas $w_1 = \dfrac{\sum (x_i - \bar x)(y_i - \bar y)}{\sum (x_i-\bar x)^2}$ and $w_0 = \bar y - w_1 \bar x$, with $\bar x = 90$, $\bar y = 256$:

So the fitted hypothesis is $h(x) = 2.7x + 13$.

Step 5 (evaluate generalization). Suppose a sixth sale, held out as `D_test` and never used in fitting, is $x=100$, $y=280$. The model predicts $h(100) = 2.7(100) + 13 = 283$, giving a squared error of $(283-280)^2 = 9$ — a small error, suggesting the linear hypothesis generalizes reasonably beyond the five training points, though five points is far too little data to draw a strong statistical conclusion. This trace makes the contrast with explicit programming concrete: nobody told the system "price equals 2.7 times size plus 13." That rule was discovered by minimizing squared error over historical experience — the defining signature of machine learning, versus a programmer hand-deriving the same formula from domain reasoning (which, for house pricing, is exactly the kind of reasoning that becomes intractable once dozens of correlated features like location, age, and renovation history are added).

Machine learning's conceptual roots lie in the mid-twentieth-century convergence of statistics, cybernetics, and early artificial intelligence research, long before the computational power existed to make the ideas practical at scale.

Recommendation engines at streaming and e-commerce platforms learn user preference models from click and purchase history rather than from hand-tuned rules, updating continuously as new interactions arrive. Email providers learn spam filters from millions of labeled messages, adapting automatically as spammers change tactics — a task where writing an explicit, exhaustive rulebook is provably a losing game against an adversary who evolves. Medical imaging systems learn to flag tumors from datasets of annotated scans, often reaching or exceeding specialist-level accuracy on narrow, well-defined detection tasks. Financial institutions learn fraud-detection models from historical transaction patterns, since fraud tactics evolve faster than any static rule list could track by hand. Autonomous vehicles learn perception stacks — lane detection, object recognition, trajectory prediction — from enormous driving datasets, because the space of real-world driving scenes is far too vast and irregular for exhaustive manual rule design. In every one of these systems, the shift from explicit programming to learning from data is not a stylistic preference — it is the only tractable approach once the target relationship is too complex or too poorly understood to specify by hand, which is exactly the boundary this article was written to make precise.

Ask the tutor: How does the choice of hypothesis space concretely determine whether a model underfits or overfits a given dataset?