{ "cells": [ { "metadata": {}, "cell_type": "markdown", "source": [ "# 1 Classifiers \n", "> *Or: What is a chair?*\n", "\n", "![title](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/title.png)" ], "id": "98ba3ec79e9b1307" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Motivation\n", "\n", "### Aristotelian Essentialism\n", "\n", "Let's say we want to classify things in chairs and non-chairs. Wouldn't it be helpful to first answer the question: What is a chair? Aristotelian essentialism is the philosophical view that entities possess an intrinsic essence that defines what they are. According to Aristotle, every object or being has a set of necessary properties that make it what it is and distinguish it from what it is not.\n", "\n", "![essentialism](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/essentialism.png)\n", "\n", "So, let's define a chair this way:\n", "\n", "A chair is ***has four legs*** and ***one can sit on it***.\n", "\n", "Is this definition helpful? " ], "id": "d4a8bc618cd50108" }, { "metadata": {}, "cell_type": "markdown", "source": [ "\n", "\n", "
\n", " \"Image\n", " \"Image\n", " \"Image\n", " \"Image\n", " \"Image\n", "
" ], "id": "6e9e92253cf813d" }, { "metadata": {}, "cell_type": "markdown", "source": [ "A horse ***has four legs*** and ***one can sit on it*** but a horse is not a chair!\n", "\n", "Can we revise our definition?\n", "\n", "A chair is ***nonliving***, ***has four legs***, and ***one can sit on it***." ], "id": "7aba6b7b83a33cc2" }, { "metadata": {}, "cell_type": "markdown", "source": [ "
\n", " \"Image\n", " \"Image\n", " \"Image\n", " \"Image\n", "
" ], "id": "b894e8dc47bf29e4" }, { "metadata": {}, "cell_type": "markdown", "source": [ "Some chairs have four legs, some have five. Some have three and there are even chairs without legs. The number of legs doesn't seem to be *essential* to the definition of a chair.\n", "\n", "![weird-chairs](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/weird-chairs.png)" ], "id": "f7075c066af12149" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Classification is Effortless!\n", "\n", "There appears to be a puzzle here. Have you ever mistaken a horse for a chair? If you encountered someone who made such an error, even just once, what advice would you give them?\n", "\n", "![mistake-meme](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/trivial-classification.png)\n", "\n", "A neurologist would probably diagnose such a person with [visual object agnosia](https://www.sciencedirect.com/topics/psychology/object-agnosia). People seem to classify objects effortless. Remarkably, this ability develops naturally—after all, when was the last time you attended chair-class?\n", "\n", "\n", "![chair-class](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/chair-class.png)" ], "id": "e32456e0b71750a7" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Machine Learning in a nutshell\n", "\n", "Directly writing a classifier function seems helpless:\n", "\n", "```python\n", "def is_chair(object):\n", " \"\"\"\n", " Returns True if something is a chair.\n", " \"\"\"\n", " if has_legs(object):\n", " if nr_legs(object) == 4:\n", " if has_flat_surface(object):\n", " if is_stable(object):\n", " if has_backrest(object):\n", " if is_comforable_height(object):\n", " if material(object) == 'wood':\n", " ...\n", "def has_legs(object):\n", " \"\"\"\n", " Returns true if something has legs.\n", " \"\"\"\n", " for element in object.elements:\n", " if is_leg(element):\n", " return true\n", "\n", "def is_leg(object):\n", " \"\"\"\n", " Returns true if something is a leg.\n", " \"\"\"\n", " if is_attached_to(object, objects_that_have_legs):\n", " ...\n", "```\n", "\n", "\n", "Instead of directly writing a function that recognizes a chair, we write an algorithm that *learns* from data to create a function that recognizes a chair." ], "id": "d760382b43cbdd46" }, { "metadata": {}, "cell_type": "markdown", "source": [ "\n", "## Classifying Classifiers\n", "\n", "To not get lost in the broader landscape of machine learning, we can think about different approaches in terms of key aspects. These include the type of *data* they process, the *solution space* that is considered, the *learning algorithm* employed, and the methods used to *evaluate* the resulting function.\n", "\n", "It is important to note that all of these aspects are, to some extent, *design choices*. While \"machine learning\" is often perceived as a general-purpose tool that can be applied to almost *any* problem, its effectiveness depends on careful design decisions. \n", "\n", "The **art of machine learning** involves: \n", "- Choosing an appropriate **feature representation** (i.e., organizing data effectively), \n", "- Defining a suitable **solution space** (i.e., constraining the problem appropriately), \n", "- Designing a meaningful **loss function** (i.e., determining how to evaluate solutions), and \n", "- Selecting an appropriate **learning algorithm** (e.g., formulating the problem as an optimization task to leverage general-purpose optimization methods). " ], "id": "b9415fa7f0d8da58" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Data\n", "\n", "The data used for classifiers is **labeled**, meaning we have examples of objects along with their corresponding category labels. For instance, a dataset might contain images of chairs and non-chairs, each labeled accordingly (e.g., *chair*, *horse*, *table*, *plant*).\n", "\n", "Mathematically, we can represent a dataset as a set of tuples:\n", "\n", "\n", "$$\n", "D = \\left\\{ (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \\dots, (x^{(n)}, y^{(n)}) \\right\\}\n", "$$\n", "\n", "where:\n", "- $D$ is the dataset containing $n$ labeled examples,\n", "- $x^{(i)}$ represents the **$i$-th input** (e.g., an image or feature vector),\n", "- $y^{(i)}$ represents the **$i$-th label** (e.g., \"chair\" or \"horse\").\n", "\n", "\n", "![chair-class](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/data-word-label.png)\n", "\n", "\n", "\n", "\n" ], "id": "7b4cfb3827f72bd4" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Binary Classification\n", "\n", "Here, we will specifically introduce *binary* classifiers. That means we do not want to classify objects into *chairs*, *horses*, *tables*, and *plants*. Instead, we are only interested in whether something *is a chair* or *is not a chair*.\n", "\n", "We can express this by defining the label as either $-1$ or $1$:\n", "\n", "$$\n", "D = \\left\\{ (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \\dots, (x^{(n)}, y^{(n)}) \\right\\}\n", "$$\n", "\n", "where\n", "\n", "$$\n", "y^{(i)} \\in \\{-1, 1\\}, \\quad \\forall i \\in \\{1, \\dots, n\\}\n", "$$\n", "\n", "![chair-class](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/data-label-binary.png)" ], "id": "73843c85b68387b8" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Caveat: Feature Representation\n", "\n", "In the above example, we do not actually classify *chairs* themselves. Instead, we classify *pictures of chairs*. In this case, we can use black-and-white images as their **feature representation**. For instance, $x^{(i)}$ could be a 2D vector of brightness values. \n", "\n", "More generally, we need a function $\\varphi$ that transforms the \"real thing\" $x$ into a feature representation $x^{(i)}$:\n", " \n", "$$\n", "\\varphi : x \\rightarrow x^{(i)}\n", "$$\n", "\n", "The feature representation typically consists of list of numbers (vectors or tensors). To keep things short and concise, in this guide, we will primarily work with the feature representation instead of the \"real thing\" and will sometimes use $x$ when we actually mean $x^{(i)}$. However, it is important to note that using a *poorly chosen* $\\varphi$ can undermine even the most sophisticated learning algorithm." ], "id": "3bdade4424dd1122" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Solution Space - Hypothesis Class\n", "\n", "Before finding a specific solution to a given problem, machine learning first requires defining a space of possible solutions. This space is often referred to as the *solution space*, *hypothesis class*, or *hypothesis space*. A single element of this space is called a *hypothesis*, and a *hypothesis* that (best) solves the problem is called a *solution*. \n", "\n", "If you come from a different field, you can think of this as *architectural constraints* or *inductive biases*. More formally, the *hypothesis space* is defined as a parameterized function:\n", "\n", "$$\n", "h \\in \\mathcal{H}\n", "$$\n", "\n", "where a specific function $y$ is given by:\n", "\n", "$$\n", "y = h(x, \\theta)\n", "$$\n", "\n", "where $\\theta$ represents the parameters of the function.\n", "\n", "If you're having a hard time wrapping your head around this concept, consider the following analogy:\n", "\n", "Imagine you need to tighten a nut. A very broad hypothesis class would be **all tools in my shed.** However, this is too general, and searching through every possible tool would be inefficient. Instead, you can constrain the hypothesis class to **all wrenches.** Now, finding the right tool becomes much easier because you’ve eliminated irrelevant options.\n", "\n", "Additionally, narrowing down the hypothesis class makes it easier to parameterize your choice. Instead of searching through every tool type, you now only need to adjust *one parameter*—the size of the wrench.\n", "\n", "***Note:*** In this example, you could even use a form of gradient descent (we will formally introduce this later) to find the correct wrench size:\n", "\n", "- If the wrench is too big, try a smaller one.\n", "- If the wrench is too small, try a bigger one.\n", "\n", "By iteratively refining your choice, you are guaranteed to find the correct solution—provided that the right wrench is available in your shed.\n", "\n", "![wrong-hypothesis](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/hypothesis.png)" ], "id": "aed8496a02693b4f" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Evaluating a Hypothesis: The Loss Function\n", "\n", "To evaluate a specific guess $h$ from the hypothesis space $\\mathcal{H}$, we introduce the concept of **loss**. Essentially, loss quantifies *how bad* a given hypothesis $h$ is at making predictions—it answers the question: *How unhappy are we with the answer that $h$ provides?* \n", "\n", "Given: \n", "- $a$ as the **actual label** at $x$, \n", "- $g$ as the **prediction** made under the hypothesis $h$, \n", "\n", "our loss for a specific $x$ is represented as a function $L(g, a)$ (or $L(h(x), a). Often, the total loss over all data points is expressed as a **average of individual losses**. \n", "\n", "A key principle in designing loss functions is that we are typically *happy* when \\( g = a \\), meaning our prediction is correct. The loss function should reflect this by assigning lower values when predictions are accurate and higher values when they are incorrect. \n", "\n", "\n", "However, in this guide, we will not delve into regularization functions in detail.\n" ], "id": "4b307eaa40f1fcf9" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Caveat: Don't Overfit \n", "\n", "Loss functions make it clear that our goal is to minimize loss—we certainly don’t want a high loss. However, there are some important subtleties to consider: \n", "\n", "Do we want to minimize the loss function **only on the training data**? \n", "After all, the function we are searching for shouldn't just perform well on the data it has already seen and that we have already labeled. If that were the goal, we could simply store all known labels in a dictionary and be done with it. \n", "\n", "But how can we evaluate loss on data that the model hasn’t seen and that we haven't labeled? That seems impossible, right? \n", "\n", "To address this, we use **proxies**: \n", "\n", "1. **Training Loss (Training Error):** \n", " The first proxy is the loss computed on the training data:\n", "\n", " $$\n", " \\epsilon_n = \\sum_{i=1}^{n} L(h(x^{(i)}), y^{(i)})\n", " $$\n", "\n", " This helps guide the learning process by *nudging* the hypothesis in the right direction. \n", "\n", "2. **Test Loss (Test Error):** \n", " The second proxy is the loss on a **holdout set**, which consists of labeled data that we intentionally **do not** show the model during training:\n", "\n", " $$\n", " \\epsilon_{\\text{test}} = \\sum_{i=n+1}^{n'} L(h(x^{(i)}), y^{(i)})\n", " $$\n", "\n", "This serves as a better approximation of the model's performance on unseen data, **especially if our dataset is representative and not biased**. \n", "\n", "For example, a **bias** could be introduced if our dataset consists exclusively of furniture from IKEA. In that case, even when evaluating on a test set, we would still be testing only on IKEA furniture. As a result, the model might perform well on this specific subset but fail to generalize to chairs from other brands, leading to **misclassifications**. This would cause our classifier to perform significantly worse on truly unseen data compared to what the test loss suggests.\n", "\n", "***Note:*** *Overfitting* refers to a model that performs well on training data but significantly worse on test data. This occurs when the model learns patterns that are **too specific** to the training data, rather than generalizing to unseen examples.\n", "\n", "![loss](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/loss.png)" ], "id": "91767409a4bee7e5" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Linear Classifiers\n", "\n", "### Dataset $D$\n", "\n", "Let's consider a dataset where $x^{(i)}$ are vectors in d-dimensional space and labels are either $-1$ or $1$:\n", "\n", "$$\n", "D = \\left\\{ (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \\dots, (x^{(n)}, y^{(n)}) \\right\\}\n", "$$\n", "\n", "where\n", "\n", "$$\n", "y^{(i)} \\in \\{-1, 1\\}, \\quad \\forall i \\in \\{1, \\dots, n\\}\n", "$$\n", "\n", "and\n", "\n", "$$\n", "x^{(i)} \\in \\mathbb{R}^{d}\n", "$$\n", "\n" ], "id": "a22b6920a6cb9ef2" }, { "metadata": {}, "cell_type": "markdown", "source": [ "\n", "### Hypothesis Space $\\mathcal{H}$\n", "\n", "We can then define our hypothesis space $\\mathcal{H}$ as following:\n", "\n", "$$\n", "h(x, \\theta, \\theta_{0}) = sign(\\theta \\cdot x + \\theta_{0})\n", "$$\n", "\n", "where \n", "\n", "$$\n", "\\theta \\in \\mathbb{R}^{d} \n", "$$\n", "\n", "and \n", "\n", "$$\n", "\\theta \\in \\mathbb{R}\n", "$$\n", "\n", "---\n", "\n", "*Why does this work?*\n", "\n", "To build an intuition, let's consider $\\theta_0 = 0$. Then, we need to determine the sign of the dot product:\n", "\n", "$$\n", "sign(\\theta \\cdot x)\n", "$$\n", "\n", "In other words, when is the dot product between two vectors **positive** or **negative**? The dot product measures **how much one vector aligns with another**. Specifically:\n", "\n", "- The dot product is **positive** when the angle between the two vectors is **less than $90^\\circ$**.\n", "- The dot product is **zero** when the two vectors are **perpendicular** (in other words **equal to $0^\\circ$**).\n", "- The dot product is **negative** when the angle is **greater than $90^\\circ$**.\n", "\n", "**Generalizing This to Decision Boundaries**\n", "\n", "This same intuition applies to any **linear classifier**:\n", "\n", "- The decision boundary is defined by the equation:\n", "\n", " $$\n", " \\theta \\cdot x = 0\n", " $$\n", "\n", " This represents a **hyperplane** (a line in 2D, a plane in 3D, etc.) that is **orthogonal** to $\\theta$.\n", " \n", "- Any point $x$ **on the same side** as $\\theta$ satisfies:\n", "\n", " $$\n", " \\theta \\cdot x > 0\n", " $$\n", "\n", " Meaning it is classified **positively**.\n", "\n", "- Any point on the **opposite side** satisfies:\n", "\n", " $$\n", " \\theta \\cdot x < 0\n", " $$\n", "\n", " Meaning it is classified **negatively**.\n", "\n", "- Any point **exactly on the boundary** satisfies:\n", "\n", " $$\n", " \\theta \\cdot x = 0\n", " $$\n", "\n", " Meaning it is **perpendicular** to $\\theta$ and is **neither positively nor negatively classified**.\n", "\n", "Try different theta vectors in the following graph to build an intuition (you can grab and drag $\\theta$):\n", "\n", "" ], "id": "8bae4f5b342fdd96" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Loss L\n", "\n", "We define a simple loss:\n", "\n", "$$\n", "L(g, a) =\n", "\\begin{cases} \n", "0, & \\text{ if } g = a \\\\ \n", "1, & \\text{ if } g \\neq a \\\\ \n", "\\end{cases}\n", "$$\n", "\n", "In other words, we are sad if we guessed wrong ($g \\neq a$) and not sad otherwise." ], "id": "a740241539a248d" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Learning Algorithm 1: Dumb learning\n", "\n", "For a given dataset $D$, a learning algorithm that searches over the hypothesis space $\\mathcal{H}$ and tries to find a solution $s \\in \\mathcal{H}$ that minimizes the Loss $L$.\n", "\n", "As a first try, let's do `dumb_learning`: We randomly pick a number of $\\theta$ and $\\theta_0$ and pick the best:\n", "\n", "\n", "\n", "
\n", "\n", "dump_learning(D, k):
\n", "    for j = 0 to k:
\n", "        $\\theta^{(j)}$ = $\\text{random}(\\mathbb{R}^d)$
\n", "        $\\theta_0^{(j)}$ = $\\text{random}(\\mathbb{R})$
\n", "    $j^{*}$ = $\\text{argmin}_{\\{0, ..., k\\}}(\\epsilon_n(\\theta^{(j)}, \\theta_0^{(j)}))$
\n", "    return $(\\theta^{(j^{*})}, \\theta_0^{(j^{*})})$\n", "\n", "
\n", "\n", "***Note:*** The $k$ in the above algorithm is what is typically referred to as a *hyperparameter*. It is not part of the parametrization of the hypothesis space but influences the learning. Here, the higher $k$, the lower the loss, and one can even prove that:\n", "\n", "$$\n", "\\lim_{k \\to \\infty} \\epsilon(\\theta^k, \\theta_0^k) = 0\n", "$$\n", "\n", "meaning that if $k$ grows larger and larger, eventually the loss will be zero for all points (if a solution exists, meaning there is some line that separates the points).\n", "\n", "\n", "**See `dumb_learning` in action:**\n", "\n", "" ], "id": "5c3cdcbd8f036637" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Learning Algorithm 2: Clever Algorithm by a Clever Person\n", "\n", "![perceptron](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/perceptron.png)\n", "\n", "\n", "1957 – Frank Rosenblatt, a very clever person whom some refer to as the father of deep learning, developed `clever_learning`, which he dubbed the *Perceptron*. It was later proven to solve all linearly separable problems—classification problems that can be perfectly separated by a hyperplane.\n", "\n", "
\n", "\n", "clever_learning(D, T):
\n", "    $\\theta$ = $0$; $\\theta_0$ = 0
\n", "    for j = 0 to T:
\n", "        for i = 0 to n:
\n", "            if $y^{(i)}(\\theta \\cdot x^{(i)} + \\theta_0) \\leq 0$:
\n", "                $\\theta = \\theta + y^{(i)} * x^{(i)}$
\n", "                $\\theta_0 = \\theta_0 + y^{(i)}$
\n", "    return $(\\theta, \\theta_0)$\n", "\n", "
\n", "\n", "Watch `clever_learning` in action! (You may want to restart the simulation a few times—this algorithm is so clever that it often finds the correct solution on the first try!)\n", "\n", "\n", "\n", "\n", "\n" ], "id": "ce9786070638ceef" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Machine Learning as Optimization\n", "> Clever Learning Algorithms for not so clever people\n", "\n", "![optimus](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/optimus.jpg)\n", "\n", "Here, we don't want to rely on being as clever as the \"father of deep learning\" each time we have a new problem. Instead of using our intuition to come up with cool learning algorithms, we turn our problem into an optimization problem and use general purpose methods to find an optimum.\n", "\n", "An optimization function is characterized by an objective function: $J(\\theta)$. The optimization then finds $\\theta^* = \\text{argmin}_{\\theta}(J(\\theta))$.\n", "\n", "A typical machine learning objective function is\n", "\n", "$$\n", "J(\\theta) = (\\frac{1}{n}\\sum_{i=1}^{n}\\mathcal{L}(h(x^{(i)}, y^{(i)})) + \\lambda R(\\theta)\n", "$$\n", "\n", "with the training error\n", "\n", "$$\n", "\\frac{1}{n}\\sum_{i=1}^{n}\\mathcal{L}(h(x^{(i)}, y^{(i)})\n", "$$\n", "\n", "and a regularize term (for example to penalize large entries for $\\theta$)\n", "\n", "$$\n", "\\lambda R(\\theta)\n", "$$\n", "\n", "The upside of framing a problem as an optimization problem, is that we can then use general purpose algorithms to optimize. For example, gradient descend:" ], "id": "6b5d290a363fee80" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Gradient Descend\n", "\n", "Imagine you are lost in the mountains and thirsty. How would you go about finding a water source? One strategy is to always take the steepest downward path at each step. This way you will find a lower point (the lowest local point) where the chances are high that there is water. This is exactly how **gradient descent** works in optimization problems. In nature, a river naturally follows gradient descent.\n", "\n", "**Intuition**\n", "\n", "Gradient descent is an iterative optimization algorithm used to find the minimum of a function. It follows these steps:\n", "\n", "1. **Start at a random point**: Choose an initial guess for the solution.\n", "2. **Compute the gradient**: The gradient (vector of partial derivatives) points in the direction of the steepest ascent.\n", "3. **Take a step in the opposite direction**: Move against the gradient by a small step size (learning rate).\n", "4. **Repeat until convergence**: Continue iterating until the function value stops changing significantly.\n", "\n", "\n", "**Types of Gradient Descent**\n", "\n", "1. **Batch Gradient Descent**: Uses the entire dataset to compute the gradient.\n", "2. **Stochastic Gradient Descent (SGD)**: Uses a single random data point per update.\n", "3. **Mini-Batch Gradient Descent**: Uses small subsets of the data for each update.\n", "\n" ], "id": "e9f527cd802c6b79" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### 1 Dimensional Gradient Descent\n", "\n", "Let's first assume both $\\theta$ and $f(\\theta)$ are 1-dimensional (scalars). The update rule for gradient descent then is defined by\n", "\n", "$$\n", "\\theta^{t+1} = \\theta^t - \\eta f'(\\theta^t)\n", "$$\n", "\n", "with $f'(\\theta_t)$ the derivative of $f$ at point $\\theta_t$ and the learning rate $\\eta$. \n", "\n", "We can also write this as an algorithm:\n", "\n", "
\n", "\n", "GD1D($\\theta_{init}$, $f$, $f'$, $\\eta$, $\\varepsilon$):
\n", "    $\\theta^{(0)} = \\theta_{init}$
\n", "    $t = 0$
\n", "    loop
\n", "        $t = t + 1$
\n", "        $\\theta^{t+1} = \\theta^t - \\eta f'(\\theta^t)$
\n", "    until $|f(\\theta^{(t)}) - f(\\theta^{(t-1)})| < \\varepsilon$
\n", "    return $\\theta^{(t)}$
\n", "\n", "
\n", "\n", "To get a better intuition, here a few examples:\n", "\n", "\n", "\n", "\n", "\n", "***Note:*** For a convex function, it can be shown that for each error $\\varepsilon$ no matter how little, one can find a learning rate $\\eta$ so that the above algorithm *converges*. In mathematical terms:\n", "\n", "$$\n", "\\forall \\varepsilon > 0, \\quad \\exists \\eta > 0 \\text{ such that } |f(\\theta^{(t)}) - f(\\theta^*)| < \\varepsilon \\text{ as } t \\to \\infty.\n", "$$\n", "\n", "where $f(\\theta^*)$ is the minimum value of $f$.\n" ], "id": "ecca11571988f75f" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### n Dimensional Gradient Descent\n", "\n", "The above algorithm works just as well when $\\theta$ has more than one dimension. Instead of the derivative $f'$, we then use\n", "\n", "$$\n", "\\nabla f =\n", "\\begin{bmatrix}\n", "\\frac{\\partial f}{\\partial \\theta_0} \\\\\n", "\\frac{\\partial f}{\\partial \\theta_1} \\\\\n", "\\vdots \\\\\n", "\\frac{\\partial f}{\\partial \\theta_n}\n", "\\end{bmatrix}\n", "$$\n", "\n", "***Note:*** Here, the *output* of $f$ is still one-dimensional. You can imagine this, for example, as a height map when $\\theta$ is two-dimensional. Then, the gradient will be the steepest direction—the opposite direction of the fall line. \n", "If you like to ski, this is the line where you are \"drawn to,\" or, similarly, the path where water will naturally flow downhill. " ], "id": "5a9e3d372e287f47" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Logistic Regression - Why?\n", "\n", "![optimus](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/log.png)" ], "id": "c1e108010a3b84a8" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Why Linear Classifiers are not Optimal (nor Optimizable$^*$)\n", "\n", "In the above section about linear classifier, we defined an error function. Why can we not just plug that into our gradient descent function?\n", "\n", "Again, imagine you are lost and thirsty in the mountains. But since you have learned about gradient descent, you have a solution, right? Just follow the opposite of the gradient. What do you do if you reach a plateau though (in other words the gradient is 0)? If you are a very committed to the gradient descent algorithm you will die from thirst in this scenario.\n", "\n", "The same is true for our linear classifier. There are \"plateaus\" everywhere. You can convince yourself by \"wiggling\" the $\\theta$ vector in the interactive plot earlier. Small changes will not change the amount of blue or red dots which means small changes wouldn't change our error function (the amount of dots classified incorrectly). In other words, our gradient is zero and the gradient descent algorithm doesn't *know* in which direction to go.\n", "\n", "\n", "\n", "**$^*$ At least not with the standard gradient descent algorithm described earlier.**\n", "\n", "To build up an intuition, you can think about this as: **Certain properties of the loss function make it easier to optimize it. Steps are problematic, continuity is good.**\n", "\n", "![lost-gradient](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/lost-gradient.png)" ], "id": "39ba700888cc7cae" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Why don't we really on the Perceptron then?\n", "\n", "The perceptron only guarantees that a solution is found if (and only if) the minimum loss of the function is zero. Then it will find the solution. However, we would also like to find the **best** solution (the one that optimizes the loss) in other scenarios like this:\n", "\n", "![non-zero-loss](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/non-zero-loss.png)\n", "\n", " " ], "id": "27bef656476b20f4" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Linear Logistic Classifier\n", "\n", "```{note}\n", "\n", "Until now, we used the labels (-1, 1), but to make things easier, we will change the labels to (0, 1).\n", "\n", "```" ], "id": "83d472e69e4d2411" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Hypothesis Class $\\mathcal{H}$\n", "\n", "The only difference between a **linear classifier** and a **linear logistic classifier** is that instead of the $sign$ function, we now use $\\sigma$:\n", "\n", "Our hypothesis will look like this (here to make things explicit we name the hypothesis LLC instead of $h$):\n", "\n", "$$\n", "LLC(x; \\theta, \\theta_0) = \\sigma(\\theta \\cdot x + \\theta_0) \n", "$$\n", "\n", "with \n", "\n", "$$\n", "\\sigma(z) = \\frac{1}{1-e^{-z}}\n", "$$\n", "\n", "The following image might help with your intuition why this is a reasonable function to choose:\n", "\n", "---\n", "\n", "Remember the *linear classifier* hypothesis: \n", "\n", "$$\n", "LC(x; \\theta; \\theta_0) = sign(\\theta \\cdot x + \\theta_0)\n", "$$\n", "\n", "This can be understood as a \"step function\":\n", "\n", "![non-zero-loss](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/linear-step-function.png)\n", "\n", "---\n", "\n", "Remember the linear *logistic* classifier hypothesis: \n", "\n", "$$\n", "LLC(x; \\theta; \\theta_0) = \\sigma(\\theta \\cdot x + \\theta_0)\n", "$$\n", "\n", "This can be understood as a smoother version of the same \"step function\":\n", "\n", "![non-zero-loss](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/logistic-function.png)\n", "\n", "---\n", "\n", "***Note:*** By now, if you have built some intuition about gradient descent you should also have an intuition why a smoother version of the step function might be easier to optimize: Instead of a error function with plateaus, we will build an error function that is \"smooth\"." ], "id": "874f99cfd639cb20" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Loss function $L$\n", "\n", "With our hypothesis space $LLC$, we can now define a Loss function $L$:\n", "\n", "Let's look at our prediction $g$:\n", "\n", "$$\n", "g^{(i)} = \\sigma(\\theta \\cdot x^{(i)} + \\theta_0)\n", "$$\n", "\n", "this can be interpreted as the probability of guessing that the label at $x^{(i)}$ is $1$. But then, we can write the accuracy of the hypothesis $A$ on the training set as:\n", "\n", "$$\n", "A = \\prod_{i=0}^n \\begin{cases} \n", "g^{(i)}, & \\text{ if } y^{(i)} = 1 \\\\ \n", "1 - g^{(i)} , & \\text{ if } y^{(i)} = 0 \\\\ \n", "\\end{cases}\n", "$$\n", "\n", "this is the probability of guessing the full training set (every label) correctly.\n", "\n", "A more compact way of writing this is:\n", "\n", "$$\n", "A = \\prod_{i=0}^n {g^{(i)}}^{y^{(i)}} * (1 - {g^{(i)})}^{1 - y^{(i)}}\n", "$$\n", "\n", "***Tip 1:*** This trick of using exponentiation to replace conditional branching is a powerful and elegant technique. It’s particularly useful in optimization and gradient-based learning because it allows for smooth, differentiable computations without explicit if statements. It works since $a^0 = 1$ and $y^{(i)}$ is either 0 or 1. Convince yourself, that the formulas are equivalent by trying out both cases of the if statement ($^{(i)} = 0$ and $^{(i)} = 1$).\n", "\n", "***Tip 2:*** $A$ is also called the **Bernoulli likelihood function**.\n", "\n", "With all the math involved in defining a loss function, it's easy to lose sight of the main goal: providing an objective function that can be optimized using gradient descent (or similar methods).\n", "\n", "*What Really Matters?*\n", "\n", "Most of the time, we don’t necessarily care about the interpretability of the loss function. Instead, we only need to ensure that:\n", "\n", "1. The loss function provides meaningful gradients that guide the optimizer toward better model parameters. \n", "2. Optimizing the loss improves the model’s performance.\n", "\n", "\n", "For example, if we take an objective function $O$ and multiply it by a positive scalar, the function itself becomes \"stretched.\" However, this does not change the location of the minima and maxima—it only scales the gradients. Since gradient-based optimizers adjust step sizes accordingly, optimization results remain unchanged.\n", "\n", "Thus, while a scaled loss function might lose its original interpretability, it still leads to the same optimal solution when used in training.\n", "\n", "This is not only true for **stretching** but for all monotonic transformations: If we preserve the **order** of the values, that means we use a transformation $w$ for witch $x_i < x_j \\implies w(x_i) < w(x_j) \\ \\forall x_i, x_j$, then our gradient descent optimization still gives the same results.\n", "\n", "This is important, since we will use now log-transform $A$ to get our final loss function $A'$\n", "\n", "This is not only true for **stretching** but for all **monotonic transformations**: \n", "\n", "If we preserve the **order** of the values, that means we use a transformation \\( w \\) for which:\n", "\n", "$$\n", "\\begin{align}\n", "A' &= \\log(A) \\\\\n", "&= \\log (\\prod_{i=0}^{n} g^{(i)y^{(i)}} (1 - g^{(i)})^{1 - y^{(i)}}) \\\\ \n", "&= \\sum_{i=0}^{n} \\log \\left( g^{(i)y^{(i)}} \\right) + \\log \\left( (1 - g^{(i)})^{1 - y^{(i)}} \\right) \\ (1) \\\\\n", "&= \\sum_{i=0}^{n} y^{(i)} \\log (g^{(i)}) + (1 - y^{(i)}) \\log (1 - g^{(i)}) \\ (2)\n", "\\end{align}\n", "$$\n", "\n", "We used:\n", "\n", "1. $\\log(a*b) = \\log(a) + \\log(b)$\n", "2. $\\log(a^b) = b * \\log(a)$\n", "\n", "Since we want to maximize $A$, we can minimize -$A'$ which is also called *Negative log likelihood* or *cross entropy*:\n", "\n", "$$\n", "\\mathcal{L} = - \\sum_{i=0}^{n} y^{(i)} \\log (g^{(i)}) + (1 - y^{(i)}) \\log (1 - g^{(i)})\n", "$$\n", "\n", "We won’t go through the full derivation of the gradient of $\\mathcal{L}$ with respect to $\\theta$ here, but it’s a great exercise for those interested. Tip: Use the chain-rule.\n", "\n", "The final result for the gradient is:\n", "\n", "$$\n", "\\nabla_{\\theta} \\mathcal{L} = \\sum_{i=0}^{n} (g^{(i)} - y^{(i)}) x^{(i)}\n", "$$\n", "\n" ], "id": "c53d0f922767e64c" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Caveat: Linear Separability\n", "\n", "The linear logistic classifier only gives good answers when the data is **linear separable**. To get around this we can sometimes transform our data, for example by using an additional dimension and a polynomial basis:\n", "\n", "![linear-separable](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/linear-separable.png)\n", "\n", "\n", "However, a neural networks provide a more general solution for this problem:" ], "id": "6cb138550e7d8b12" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Neural Networks\n", "\n", "### Neuron\n", "\n", "![linear-separable](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/neuron.png)\n", "\n", "A single **neuron** in a neural network computes its activation using a weighted sum of inputs $\\vec{x}$), followed by a activation function $f$. Mathematically, this can be written as:\n", "\n", "$$\n", "a = f ( \\sum_{i=0}^n w_i * x_i + w_0 )\n", "$$\n", "\n", "or in vector notation\n", "\n", "$$\n", "a = f \\left( \\vec{w} \\cdot \\vec{x} + w_0 \\right)\n", "$$\n", "\n", "***Note:*** \n", "\n", "- If $f = sign$ this is just a **linear classifier**. \n", "- If $f = \\sigma$ it is a **linear logistic classifier**." ], "id": "6f575bd99d86e986" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Layer\n", "\n", "![linear-separable](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/layer.png)\n", "\n", "We call $m$ parallel neurons a **layer** of size m.\n", "\n", "we can write this as\n", "\n", "$$\n", "a_j = f( \\vec{w}^{(j)} \\cdot \\vec{x} + w_0^{(j)})\n", "$$ \n", "\n", "or more concise in matrix form:\n", "\n", "$$\n", "\\vec{a} = f ( W \\vec{x} + \\vec{w}_0)\n", "$$\n", "\n", "with \n", "\n", "$$\n", "\\vec{x} \\in \\mathbb{R}^n; \\ \\vec{a}, \\vec{w}_0 \\in \\mathbb{R}^m; \\ W \\in \\mathbb{R}^{n \\ \\text{x} \\ m}\n", "$$" ], "id": "4be13d7a7b303069" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Network\n", "\n", "![linear-separable](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/neural-network.png)\n", "\n", "A neural network is when we (serially) connect multiple layers\n", "\n", "***Note:***\n", "If $f^L = \\sigma$ and $W^L \\in \\mathbb{R}^{\\cdot \\ \\text{x} \\ 1}$, the neural network is a (logistic) classifier." ], "id": "609e81bae75c78d4" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### Activation Functions\n", "\n", "Think about what could be \"good\" activation functions $f^i$?\n", "\n", "To keep things simple, let's consider linear activation functions $f(z) = \\lambda * z$.\n", "\n", "If all our activation functions are linear, we can write:\n", "\n", "$$\n", "A \\vec{x} = W^total \\vec{x} : W^total = \\prod \\lambda^{i} W^i\n", "$$\n", "\n", "in other words, we can write our neural network as one layer and the matrix $W^total$! This is defeats the purpose of using multiple layers. Instead, activation functions are only helpful if they are non-linear. In addition, for reasons we explored in the section about optimization, they should be differentiable (that means step functions or signs are not ideal). But, we can use $\\sigma$ or ReLU:\n", "\n", "![linear-separable](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/activation-functions.png)" ], "id": "1056408f8abead1" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Backpropagation \n", "\n", "If you’ve been following along, understanding backpropagation seems almost trivial. In essence, backpropagation is just a more fancy word for the *chain rule* you are familiar with from calculus.\n", "\n", "![linear-separable](https://younesstrittmatter.github.io/teaching/_static/machine-learning/classifiers/backprop.png)\n", "\n", "$$\n", "\\frac{\\delta loss}{\\delta W^L} = \\frac{\\delta loss}{\\delta A^L} * \\frac{\\delta A^L}{\\delta Z^L} * \\frac{\\delta Z^L}{\\delta W^L}\n", "$$\n", "\n", "with:\n", "\n", "$\\frac{\\delta loss}{\\delta A^L}$ defined by the chosen loss function\n", "\n", "$\\frac{\\delta A^L}{\\delta Z^L} = (f^{L})'$\n", "\n", "$\\frac{\\delta Z^L}{\\delta W^L} = A^{L-1}$\n", "\n", "And, we can then successively calculate the Losses for each weight by:\n", "\n", "$$\n", "\\frac{\\delta loss}{\\delta W^1} = \\frac{\\delta loss}{\\delta A^L} * \\frac{\\delta A^L}{\\delta Z^L} * \\frac{\\delta Z^L}{\\delta A^{L-1}} * \\frac{\\delta A^{L-1}}{\\delta Z^{L-1}} * ... * \\frac{\\delta A^2}{\\delta Z^2} * \\frac{\\delta Z^2}{\\delta A^1} * \\frac{\\delta A^1}{\\delta Z^1}\n", "$$\n", "\n", "with\n", " \n", "$\\frac{\\delta Z^i}{\\delta A^{i-1}} = W^i$ since $W$ are linear functions\n", "\n", "$\\frac{\\delta A^i}{\\delta Z^i} = (f^i)'$\n", "\n", "which we can both easily calculate.\n", "\n" ], "id": "3b8041623c98bcb5" }, { "metadata": {}, "cell_type": "markdown", "source": "THANK YOU AND HAPPY CODING!", "id": "37b29954d8aa061a" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": "", "id": "a6a62397031cd4bb" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" } }, "nbformat": 4, "nbformat_minor": 5 }