Syllabus Outline

This subchapter introduces pattern classification through the classic fish sorting example, detailing the processing pipeline, features, and error-cost decision boundaries. - Why we need this: To understand the fundamental goal of pattern classification: converting raw sensory measurements into discrete decision categories. It defines the vocabulary (features, patterns, classifiers) we will use throughout the course. - Where we need this: In any machine learning pipeline (like sorting fish on a conveyor belt, face detection on a camera, or speech recognition). In the exam, it helps you identify what features to extract and why raw data classification is not directly feasible. - Goal: Classify incoming objects (patterns) into distinct categories using sensory measurements. - Running Example: Sorting fish on a conveyor belt as either Sea Bass ($\omega_1$) or Salmon ($\omega_2$). - Standard Workflow: - Data Collection: Gather a representative set of training samples. - Labeling: Experts assign true class labels to the samples. - Sensing: Capture raw data (e.g., images) from the samples. - Feature Extraction: Compute numerical representations (features) from raw data. - Classifier Training: Build a decision function (classifier) mapping features to labels. - Evaluation: Experimentally evaluate reliability on unseen cases. A pattern classification system operates in three sequential phases: - Preprocessing: Segment and isolate individual objects from the background (e.g., image segmentation). - Feature Extraction: Reduce and abstract raw high-dimensional data (pixels) into a compact set of informative characteristics (features). - Classification: Pass the extracted features to a classifier which evaluates the decision function and outputs the predicted category. Comparing different feature attempts to discriminate between Sea Bass and Salmon: - Attempt 1: Length: Look at class histograms of fish lengths. - Result: Strong overlap between the two classes. - Conclusion: Length is a poor discriminator. No single threshold $l^*$ can achieve low error. [Image] - Attempt 2: Lightness: Look at class histograms of average scale lightness. - Result: Significantly less overlap compared to length. - Conclusion: Lightness is a much better discriminator, though still not perfectly error-free. [Image] - Symmetric Costs: If all errors are equally bad, we place the decision boundary at the intersection point of the distributions to minimize the total error rate. - Asymmetric Costs: In real life, different errors have different costs. - Example: If misclassifying Sea Bass as Salmon is more costly than Salmon as Sea Bass, we must adjust the decision threshold. - Action: Shift the boundary to the left (toward Salmon) to reduce the risk of Sea Bass misclassification. - Decision Theory: The study of choosing optimal decision boundaries given feature distributions and relative costs of errors. \subsection{Subchapter 1.2: Feature Spaces, Decision Boundaries, Generalization, and the Design Cycle}

This subchapter establishes the mathematical notations used throughout the course and reviews continuous probability, probability density functions (PDFs), and cumulative distribution functions (CDFs). - Why we need this: To mathematically model the uncertainty and noise inherent in real-world measurements. Probability mass functions (PMFs) for discrete data and density functions (PDFs) for continuous features allow us to represent uncertainty quantitatively. - Where we need this: As the foundational language of probabilistic machine learning. You need this to calculate priors, likelihoods, and posteriors in all Bayesian models. In the exam, you will calculate cumulative probabilities (CDFs) over specific feature ranges. Strict mathematical notation is adhered to across the lecture and exam: Object Type & LaTeX Notation & Example

Variables / features & Upper-case italics & $X, \text{Length}$

Scalar values & Lower-case italics & $x, y, \omega_i$

Vectors (points in $\mathbb{R}^d$) & Lower-case bold italics & $\mathbf{x}, \boldsymbol{\mu}$

Matrices & Upper-case bold & $\mathbf{M}, \boldsymbol{\Sigma}$

Sets & Upper-case calligraphic & $\mathcal{D}, \mathcal{X}$

Discrete probabilities & Upper-case letter & $P(X = x)$ or $P(x)$

Continuous densities (PDF) & Lower-case letter & $p(x)$

Note: Bold face for vectors and matrices is represented as bold italics in text, e.g., $\mathbf{x}, \boldsymbol{\mu}$ for vectors and $\mathbf{\Sigma}$ for matrices. - Discrete (PMF): A probability mass function $P(x)$ assigns a probability to each value $x_i \in \text{Val}(X)$, where $0 \le P(x_i) \le 1.0$ and $\sum_i P(x_i) = 1.0$. - Continuous (PDF): In real-world tasks, features are continuous (real-valued). The probability of obtaining any exact value $x \in \mathbb{R}$ is exactly zero: $P(X = x) = 0$ In English: The probability that a continuous random variable $X$ takes on any single exact real value $x$ is exactly zero. (This is basically because there are infinitely many possible real numbers, so the probability of hitting any single exact point is zero; we can only measure probability over intervals using area under the density curve). Instead, we define a Probability Density Function (PDF) $p(x)$. A function $p : \mathcal{X} \rightarrow \mathbb{R}^+$ is a PDF if: - $p(x) \ge 0$ for all $x \in \text{Val}(X)$. - $p(x) = 0$ for all $x \notin \text{Val}(X)$. - $\int_{-\infty}^{+\infty} p(x) \,dx = 1.0$ (In English: The total area under the probability density function curve from negative infinity to positive infinity must equal exactly one. This represents the absolute certainty that the random variable must take some value within the domain of all possible outcomes). A PDF value $p(x)$ itself is not a probability and can be greater than $1.0$ (as long as the total area under the curve is $1.0$). Probabilities over continuous intervals are computed using the CDF, $P(X \le a)$: $P(X \le a) = \int_{-\infty}^{a} p(x) \,dx$ In English: The probability that the random variable $X$ is less than or equal to $a$ is the integral (area under the curve) of the density function from negative infinity up to $a$. (This accumulates all probabilities from the left up to point $a$ to give the cumulative probability). Consequently, the probability of $X$ lying in the range $[a, b]$ is: $P(a \le X \le b) = P(X \le b) - P(X \le a) = \int_{a}^{b} p(x) \,dx$ In English: The probability of $X$ falling between $a$ and $b$ is the probability of being less than $b$ minus the probability of being less than $a$, which equals the area under the density curve from $a$ to $b$. (This is basically subtracting the left tail probability up to $a$ from the total tail probability up to $b$ to isolate the region $[a, b]$). - Uniform Distribution ($X \sim \text{Unif}[a, b]$): $p(x) =$\begin{cases} \frac{1}{b-a} & \text{if } a \le x \le b 0 & \text{otherwise} \end{cases}$$ *In English: The density at any point $x$ between $a$ and $b$ is constant and equal to one divided by the interval width, and is zero elsewhere. (Here, \frac{1*{b-a} is the height of the rectangle, ensuring that the total area of the rectangle---height times the width $(b-a)$---equals exactly one).} If $(b-a) < 1$, the density $p(x) > 1.0$. - Univariate Normal Distribution ($X \sim \mathcal{N}(\mu, \sigma^2)$): $p(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$ In English: The density of a normal distribution is a symmetric bell curve centered at the mean $\mu$, where: \begin{itemize - $\frac{1}{\sqrt{2\pi}\sigma}$ is the normalization constant that scales the curve height so that the total area underneath integrates to exactly one. - $-\frac{(x-\mu)^2}{2\sigma^2}$ is the exponent that measures the squared distance of point $x$ from the mean $\mu$, normalized by the variance $\sigma^2$ (as you move further from the mean, this term becomes more negative, causing the exponential value to drop towards zero). } where $\mu$ is the mean and $\sigma^2$ is the variance. \subsection{Subchapter 2.2: Multivariate Gaussian Distribution}

This subchapter introduces the motivation behind probability density estimation from training data, compares parametric and non-parametric approaches, and defines the Likelihood and Log-Likelihood functions. - Why we need this: To estimate probability densities from a finite set of training data. The Likelihood function measures how well a parameterized model explains the observed training samples. - Where we need this: Underpins almost all model-fitting in machine learning (Maximum Likelihood Estimation). It is the standard method to fit probability distributions to features in your dataset before classification. A Bayesian classifier requires: - Prior class probabilities $P(\omega_i)$. - Class-conditional probability densities $p(\mathbf{x} \mid \omega_i)$. Since the true underlying distributions are unknown, we must estimate them from a training dataset: $D = \{(\mathbf{x}_1, \omega_{x1}), \dots, (\mathbf{x}_n, \omega_{xn})\}$ There are two main families of density estimation: - Parametric Estimation: - We assume the data was generated by a specific family of distributions (e.g., Gaussian, Uniform, Bernoulli) governed by a finite set of parameters $\boldsymbol{\theta}$. - The task is to estimate these parameters $\boldsymbol{\theta}$ from the training set $D$. - Non-parametric Estimation: - We place no constraints on the shape of the underlying density $p(\mathbf{x} \mid \omega_i)$. - Instead of fitting a global function, we estimate the density locally (e.g., using histograms, nearest neighbors, or Parzen windows). Suppose we have a set of independent and identically distributed (i.i.d.) samples $D = \{\mathbf{x}_1, \dots, \mathbf{x}_n\}$. The Likelihood of the parameters $\boldsymbol{\theta}$ given the data $D$ is: $L(\boldsymbol{\theta} : D) = p(D \mid \boldsymbol{\theta}) = \prod_{i=1}^n p(\mathbf{x}_i \mid \boldsymbol{\theta})$ *In English: The likelihood of the parameters \boldsymbol{\theta* given the independent data $D$ is the joint probability density of the data, which is the product of the individual sample densities. (This assumes the training samples are independent and identically distributed, meaning the overall probability of observing the entire dataset is simply the product of their individual probabilities).} The likelihood measures the degree to which a distribution parametrized by $\boldsymbol{\theta}$ explains the observed training data $D$. For numerical and mathematical reasons, we work with the natural logarithm of the likelihood, called the Log-Likelihood $\ell(\boldsymbol{\theta} : D)$: $\ell(\boldsymbol{\theta} : D) = \ln L(\boldsymbol{\theta} : D) = \ln \left( \prod_{i=1}^n p(\mathbf{x}_i \mid \boldsymbol{\theta}) \right) = \sum_{i=1}^n \ln p(\mathbf{x}_i \mid \boldsymbol{\theta})$ *In English: The log-likelihood of parameters \boldsymbol{\theta* is the natural logarithm of the likelihood, which converts the product of individual sample densities into a sum of log-densities. (This converts products into sums, which prevents numerical underflow---multiplying many small probabilities to get zero---and simplifies finding the maximum using derivatives).} In Maximum Likelihood Estimation, we choose the parameters $\hat{\boldsymbol{\theta}}$ that maximize this function: $\hat{\boldsymbol{\theta}} = \arg\max_{\boldsymbol{\theta}} L(\boldsymbol{\theta} : D) = \arg\max_{\boldsymbol{\theta}} \ell(\boldsymbol{\theta} : D)$ *In English: The maximum likelihood estimate \hat{\boldsymbol{\theta*} is the set of parameter values that maximizes the likelihood (or log-likelihood) function. (This is basically selecting the distribution parameters that make our observed training dataset as probable as possible).} [Image] Let's break down the key concepts with a simple coin toss example: - i.i.d. (Independent and Identically Distributed): Imagine flipping a coin 10 times. Each flip is independent of the others (the coin has no memory), and each flip uses the same coin (identically distributed). Because they are independent, the probability of getting a specific sequence of flips is the product of their individual probabilities. - Probability vs. Likelihood: - Probability: "If I have a fair coin ($\theta = 0.5$), what is the probability of getting 10 heads?" (We vary the data for fixed parameters). - Likelihood: "I flipped a coin and got 8 heads. What is the likelihood that this is a fair coin ($\theta = 0.5$) vs. a biased coin ($\theta = 0.8$)?" (We vary the parameters for a fixed dataset). Note: Likelihood is not a probability distribution over parameters (it does not integrate to $1.0$). - Why use Logs?: If we have 1000 independent samples, the likelihood is the product of 1000 numbers less than $1.0$ (e.g., $0.1^{1000} \approx 0$). Computers suffer from numerical underflow and round this to exactly zero. Taking the logarithm converts the product into a sum of logs (e.g., $\ln(0.1) \approx -2.3$, so the sum is $-2300$). This remains within a normal numerical range. Additionally, taking derivatives of sums is much easier than taking derivatives of products. \subsection{Subchapter 3.2: MLE for Gaussians and Discrete Distributions}

This subchapter introduces the general scenario for classification learning, defines true and empirical error, and details the primary methods for estimating a classifier's performance: the Resubstitution Estimate, Holdout Testing, $k$-fold Cross-Validation, and Comparison to a Baseline. - Why we need this: We cannot see the future and we do not know the true underlying data distribution. Therefore, we must use empirical estimation techniques on held-out datasets to reliably estimate how well our classifier will perform on new, unseen cases in the real world. - Where we need this: Used in every single machine learning project to validate models before deployment. In JKU exams, you will commonly be asked to define true vs. empirical error, identify the flaws of resubstitution, distinguish between stratified and leave-one-out cross-validation, and calculate baseline accuracies. - The General Scenario: The world is modeled as a $d$-dimensional feature space $\mathcal{X} \subseteq \mathbb{R}^d$ governed by an unknown stationary joint probability distribution $p(\mathbf{x}, \omega_i)$ over features and classes. Training samples $D$ are drawn independently and identically distributed (i.i.d.) from $p$. - Categorical Classifiers: Classifiers that directly predict a discrete class label from the input features $\mathbf{x} \mapsto \omega_i$. - Examples: Linear Discriminant, $k$-NN, Decision Trees, Random Forests, Support Vector Machines (SVMs). - Probabilistic Classifiers: Classifiers that estimate class posterior probabilities $P(\omega_j \mid \mathbf{x})$ first and then apply a decision criterion (e.g., argmax) to make a prediction. - Examples: Naïve Bayes, Logistic Regression, Neural Networks. - True Error $E_p(c)$: The true probability that a classifier $c$ will misclassify a sample randomly drawn from the underlying distribution $p$: $E_p(c) = P(\mathbf{x} \in \mathcal{X} : c(\mathbf{x}) \neq \text{class}(\mathbf{x}))$ *In English: The true error of a classifier $c$ is the probability of drawing a feature vector \mathbf{x* from the feature space $\mathcal{X}$ for which the predicted label $c(\mathbf{x})$ is not equal to the true expert class label. (This represents the actual out-of-sample error rate of the classifier over the entire data universe governed by distribution $p$).} - **Empirical Error \hat{E**_D(c)}: The fraction of misclassifications measured on a specific finite dataset $D$: $\hat{E}_D(c) = \frac{|\{\mathbf{x}_i \in D : c(\mathbf{x}_i) \neq \text{class}(\mathbf{x}_i)\}|}{|D|}$ In English: The empirical error is the count of samples in dataset $D$ where the classifier makes a wrong prediction, divided by the total number of samples in $D$. (This is the average error rate we compute directly from our training or test samples, since we cannot compute the true error $E_p(c)$ analytically). - Classification Accuracy: $\text{Acc}(c) = 1 - E(c)$ In English: Accuracy is one minus the error rate, representing the proportion of correct predictions. To estimate a model's true accuracy, we use one of the following empirical procedures: - The Resubstitution Estimate (Train-on-Test): - Procedure: Train the classifier $c$ on dataset $D$, then evaluate its performance on that same dataset $D$. - Problem: Extremely too optimistic as an estimate of true accuracy because the classifier was optimized to fit this exact data. It only shows how well the model family can fit the training set. - Golden Rule: The data used for testing must be completely independent of the data used for training. - Holdout Testing: - Procedure: Randomly split dataset $D$ into two disjoint sets: $D_{\text{train}}$ and $D_{\text{test}}$. Train only on $D_{\text{train}}$ and test on $D_{\text{test}}$. - Repeated Holdout: Shuffle and split the data $N$ times to compute the mean, range, and standard deviation of accuracy, accounting for split variance. - $k$-fold Cross-Validation: - Procedure: Partition the dataset $D$ randomly into $k$ equal-sized folds $F_1, \dots, F_k$. For each fold $i$, train on all other folds combined ($D \setminus F_i$) and test on $F_i$. This yields $k$ independent performance estimates. - Stratified Cross-Validation: Folds are partitioned such that each fold has approximately the same class distribution (proportion of each class) as the overall dataset, reducing variance in evaluation. - Leave-One-Out Cross-Validation (LOOCV): A special case where $k = |D|$ (each individual sample is its own fold). Highly useful when training data is very scarce, but computationally expensive. To know if "N% accuracy" is actually good, we must compare our model to a baseline: - Baseline (Default) Accuracy: The accuracy achieved by "informed guessing", which corresponds to always predicting the majority class (the most frequent class in the training set $D$): $\text{Baseline} = \frac{\max_j N_j}{|D|}$ In English: The baseline accuracy is the number of samples in the most frequent class divided by the total number of samples in the dataset. (This is the score you get by simply guessing the most common class for every test case without looking at any features. A classifier is only useful if it performs significantly better than this baseline). Let's make these evaluation methods intuitive: - Resubstitution is like a Cheat Sheet: Imagine a teacher gives you a math test with 10 practice questions that you have already studied with the solutions. If you score 100%, it doesn't mean you are a math genius---it just means you memorized the practice questions (high resubstitution accuracy, poor generalization). - Holdout is a Real Exam: The teacher teaches you from the textbook ($D_{\text{train}}$) but tests you using new, unseen exam questions ($D_{\text{test}}$). This gives a true reflection of your understanding. - Cross-Validation is Rotation Training: If you only have a few questions, you split them into 5 groups. You study 4 groups and test on the remaining group. You repeat this 5 times, rotating the test group each time. This ensures every question is used for testing exactly once, maximizing the utility of a small dataset. - Baseline is the Lazy Guess: If you go to a medical clinic in a country where 95% of patients have a common cold, you can achieve 95% accuracy by always diagnosing everyone with a cold. If a sophisticated machine learning doctor machine gets 94% accuracy, it is worse than useless---it is worse than just guessing the default! \subsection{Subchapter 4.2: Overfitting, Bias-Variance, and Model Selection}

This subchapter recaps the operational properties, advantages, and shortcomings of three simple baseline classifiers introduced in previous units: the Default (Majority Class) Classifier, the Naïve Bayes Classifier, and the $k$-Nearest Neighbor ($k$-NN) Classifier. - Why we need this: Before training a complex machine learning model (like a Random Forest or Support Vector Machine), we must establish a simple baseline to understand the difficulty of our task and justify the added complexity of more advanced models. - Where we need this: Used at the beginning of any machine learning project to set the baseline performance metrics. In JKU exam questions, you will frequently be asked to list the specific advantages and disadvantages of Naïve Bayes and $k$-NN, or explain why Naïve Bayes is considered a high-bias model while $k$-NN is a low-bias model. The simplest baseline is to completely ignore features and always guess the most frequent class: - Baseline (Default) Accuracy: $\text{Baseline} = \frac{\max_j N_j}{|D|}$ In English: The baseline accuracy is the count of samples in the most frequent class $N_j$ divided by the total number of samples in the training set $D$. (This represents the score of a classifier that simply outputs the majority class for every sample; a learned model is only useful if it performs substantially better than this baseline). - Core Algorithm: Estimates class posteriors using the conditional independence assumption of features given the class: $P(\omega_j \mid \mathbf{x}) \propto P(\omega_j) \prod_{i=1}^d P(x_i \mid \omega_j)$ *In English: The posterior probability of class $\omega_j$ given feature vector \mathbf{x* is proportional to the product of the class prior probability $P(\omega_j)$ and the product of the individual feature likelihoods $P(x_i \mid \omega_j)$ across all $d$ dimensions. (This represents the Naïve Bayes decision rule, which assumes features do not influence each other within the same class).} - Advantages: - Simple and efficient. - Fast learning and classification. - Can learn incrementally online (by updating frequency counts). - Directly applicable to multi-class problems. - Outputs probabilities along with its predictions. - Can be used in discrete domains and in very high-dimensional feature spaces. - Disadvantages / Shortcomings: - The feature independence assumption is rarely satisfied in practice. - May give poor class probability estimates in domains with highly correlated features. - High Bias (Restricted Model Class): Cannot take feature interactions into account, restricting its decision boundaries. - Core Algorithm: Classifies query point $\mathbf{x}$ by taking a majority vote of its $k$ nearest neighbors: $\omega^* = \arg\max_{\omega_j} \sum_{i=1}^k 1(\text{Class}(\mathbf{z}_i) = \omega_j)$ *In English: The predicted class $\omega^*$ is the class index that maximizes the count of the nearest neighbors \mathbf{z*_i belonging to that class. (This is the instance-based majority vote classification rule).} - Advantages: - Extremely simple. - Extremely short training time (none, we just store the data). - Can learn incrementally online. - Low Bias (Highly Expressive): Can represent arbitrarily complex, non-linear decision boundaries given enough data. - Disadvantages / Shortcomings: - Slow at classification time (computation grows linearly with the size of the training set $|D|$). - Does not produce an interpretable model. - Sensitive to irrelevant features due to distance dilution (Curse of Dimensionality), making it problematic in high-dimensional feature spaces. \subsection{Subchapter 5.2: Decision Trees & The ID3 Algorithm}

This subchapter focuses on optimizing the classifier's input representation. We analyze how irrelevant or redundant features degrade performance and study greedy search algorithms (Forward Selection and Backward Elimination) to find optimal feature subsets. Additionally, we explore feature construction, deriving new features from raw measurements to expose hidden relationships. - Why we need this: Real-world datasets often contain irrelevant or redundant features. For example, $k$-NN is highly sensitive to irrelevant features because they distort distance calculations, while Naïve Bayes suffers from redundant features due to double-counting evidence. Feature selection reduces dimensionality to prevent overfitting and speed up training. Feature construction allows classifiers to learn relationships they would otherwise be blind to (e.g., ratio or difference features). - Where we need this: In the initial data preprocessing and engineering phase of any machine learning project. In JKU exams, you will be asked to compare Forward Selection and Backward Elimination, explain why $k$-NN or Naïve Bayes are sensitive to feature issues, and solve feature construction problems (such as the square-vs-rectangle classification example). A classifier's performance is heavily bounded by the quality of its input features. We distinguish two main types of feature issues: - Irrelevant Features: Features that carry no useful information about the class label. - Effect on $k$-NN: Highly detrimental. Since $k$-NN uses Euclidean distance, an irrelevant feature adds random noise to the distance metric. As the number of irrelevant dimensions increases, the true nearest neighbors are lost in noise, and classification accuracy drops. - Overfitting: Irrelevant features increase the search space, giving low-bias learners (like decision trees) more opportunities to fit random noise (overfit). - Redundant Features: Features that are highly correlated with other features, adding no new information. - Effect on Naïve Bayes: Detrimental. Naïve Bayes assumes features are conditionally independent. If feature $A$ and feature $B$ are identical copies, Naïve Bayes multiplies their probabilities, effectively double-counting the evidence of that feature and distorting the posterior distribution. Finding the absolute optimal feature subset from a set of $N$ features requires evaluating all possible subsets: $\text{Number of Subsets} = 2^N$ In English: The number of possible subsets of features grows exponentially as $2^N$ where $N$ is the total number of features. (Since this search is $O(2^N)$, it quickly becomes computationally impossible for large $N$, requiring greedy heuristic search algorithms). Common greedy approaches evaluated via cross-validation include: - Forward Selection: - Start with an empty feature set: $S = \emptyset$. - For each feature $f_j \notin S$, temporarily add it to $S$ and evaluate the cross-validation accuracy of the classifier. - Permanently add the feature that yields the largest accuracy increase. - Repeat until adding any remaining feature no longer improves cross-validation accuracy. - Backward Elimination: - Start with the full set of features: $S = X$. - For each feature $f_j \in S$, temporarily remove it from $S$ and evaluate the cross-validation accuracy. - Permanently remove the feature whose deletion yields the highest accuracy (or causes the smallest drop). - Repeat until removing any further feature decreases cross-validation accuracy. - Other Search Strategies: Bidirectional search, best-first search, beam search, and stochastic search (genetic algorithms). [Image] A comparison of Forward Selection and Backward Elimination search strategies. Both are greedy heuristics that run cross-validation at each step to navigate the $O(2^N)$ search space. Feature construction derives new features from existing ones to expose relationships that the learning algorithm cannot discover automatically: - Motivation: Many classifiers evaluate features in isolation and are blind to feature interactions. - The Square vs. Rectangle Example: - Setup: A decision tree learner (like ID3) is trained to classify "Square" vs. "General Rectangle" based on features $X = \{\text{Length}, \text{Width}, \text{Colour}\}$. - Problem: A square is defined by the relation $\text{Length} = \text{Width}$. Since squares can be of any scale, evaluating Length or Width individually yields almost $0.0$ Information Gain ($IG_D(\text{Length}) \approx 0$ and $IG_D(\text{Width}) \approx 0$). ID3 evaluates features individually and will decide that both features are useless, potentially selecting the noisy feature "Colour" instead. - Solution: We construct a new ratio feature $R = \text{Length}/\text{Width}$ or a boolean feature $Q \equiv (\text{Length} = \text{Width})$. The newly constructed feature $Q$ will have an Information Gain of $1.0$ bit, allowing ID3 to learn a perfect, 1-node decision tree instantly. - Common Feature Construction Operations: - Rescaling: $\log X, \sqrt{X}, X^k, e^X$. - Arithmetic combinations: $X - Y$, $X \cdot Y$, $X/Y$. - Relational operators: $X = Y$, $X > Y$. Let's make these concepts intuitive: - Forward Selection is packing a light backpack: You start with nothing. You try packing items one-by-one (first a bottle of water, then a map) and check how prepared you are. You only add items that significantly improve your survival rating. You stop when carrying more weight isn't worth the effort. - Backward Elimination is cleaning a heavy closet: You start with everything in the closet. You try taking items out one-by-one (removing old receipts, then mismatched socks). If taking an item out makes no difference (or makes it easier to find things), you throw it away. You stop when removing anything else would actually be a loss. - Feature Construction is giving the builder a calculator: Imagine a builder trying to see if a box fits in a doorway. The builder can only measure the height of the box, then walk over and measure the door. Because they can't remember both numbers at once, they fail. Feature construction is like writing the difference (Box Height - Door Height) on a piece of paper. The builder can now read this single number and immediately know if the box fits. \subsection{Subchapter 6.2: Model Selection and Parameter Optimisation}

This subchapter introduces Artificial Neural Networks (ANNs) by formalizing the basic biological analogies of connectionist models and explaining how classification can be formulated as a regression task (probabilistic concept learning). We present the basic computation unit (neuron) and trace parameter optimization using Sum Squared Error (SSE) and Iterative Gradient Descent. - Why we need this: Many real-world problems require predicting continuous numerical variables (e.g., fuel efficiency, real estate prices) rather than discrete classes. Furthermore, by framing classification as a regression task, our models predict class membership probabilities (e.g., probability of a transaction being fraudulent) rather than binary decisions, allowing for risk-based decision making. - Where we need this: Predicting stock prices, temperature trends, medical health indicators, and estimation of posterior probabilities $P(\omega_j \mid x)$ in speech recognition and anomaly detection. In the exam, you will be expected to trace the operations of a single neuron, calculate Sum Squared Error (SSE) for a dataset, and execute parameter updates using gradient descent. A regression model predicts one or more continuous numeric values from a set of features. We can model JKU's probabilistic concept learning by learning class membership probabilities: - Single-class prediction: Learn a function $f_c: X \to [0, 1] \subset \mathbb{R}$ that maps input features to the posterior probability of class $c$: $f_c(x) = \hat{P}(c \mid x)$ *In English: The function $f_c(x)$ outputs a continuous estimate of the probability \hat{P* that the input $x$ belongs to class $c$.} - Multi-class prediction: Learn a vector-valued function $f: X \to [0, 1]^k$ mapping inputs to probabilities over all classes $\Omega = \{\omega_1, \dots, \omega_k\}$: $f(x) = \hat{P}(\Omega \mid x)$ *In English: The model output $f(x)$ is a $k$-dimensional vector containing the estimated probability distribution \hat{P* over the set of classes $\Omega$ given the input $x$.} An artificial neuron (or unit) $i$ is a distributed computation unit characterized by its incoming connections and weights. - Inputs and Weights: Unit $i$ receives inputs $x_j$ from other units. Each connection has a weight $w_{ij}$ modeling synaptic strength. - Net Input calculation: $\text{net}_i = \sum_j w_{ij} x_j$ *In English: The net input \text{net*_i is the weighted sum of all incoming inputs $x_j$, where each input is multiplied by its connection weight $w_{ij}$.} - Activation Function application: $y_i = f(\text{net}_i)$ *In English: The final output $y_i$ of unit $i$ is obtained by applying the activation function $f$ to the net input \text{net*_i. This output $y_i$ is then passed as an input connection to other units.} To train a model, we need an objective measure $E$ of its error. Consider JKU's linear regression scenario predicting fuel consumption (miles per gallon $y$) from weight (pounds $x$): $y = w_1 x + w_0$ In English: The predicted output $y$ is a linear function of the input feature $x$, with slope $w_1$ and vertical intercept $w_0$. For a training set $D$, the standard measure of goodness-of-fit is the Sum Squared Error (SSE): $E = \frac{1}{2} \sum_{x_i \in D} (y_i - \hat{y}(x_i))^2$ *In English: The total error $E$ is half of the sum of squared differences between the true targets $y_i$ and the predictions \hat{y*(x_i) across all instances in dataset $D$. The factor of $\frac{1}{2}$ is a mathematical convenience that cancels out when we take the derivative of the quadratic error term.} While linear models can be solved analytically using Least Squares, non-linear neural networks must be optimized iteratively. - Gradient: The gradient vector $G$ points in the direction of the greatest rate of increase of the error function $E$. The component for weight $w$ is the partial derivative: $G_w = \frac{\partial E}{\partial w}$ In English: The gradient component $G_w$ represents the slope of the error surface $E$ with respect to weight $w$ at its current value. - Weight Update Rule: To minimize error, we move "downhill" in the opposite direction of the gradient, scaled by a learning rate $\eta > 0$: $\theta_i \leftarrow \theta_i - \eta \cdot G_{\theta_i}$ *In English: We update parameter $\theta_i$ by subtracting the product of the learning rate $\eta$ and the gradient component G_{\theta_i*. This is repeated iteratively until the gradient becomes close to zero, signaling that we have reached a local minimum.} \subsection{Subchapter 7.2: Feed-forward Networks (MLPs) and Activation Functions}

This subchapter provides an overview of the wide variety of regression, classification, and generative tasks that deep learning models can perform. It covers classical and modern applications of neural networks, demonstrating how deep models scale to complex high-dimensional outputs. - Why we need this: To understand how real-world problems (from predicting material strength to generating text or audio) are mapped onto machine learning objectives (regression, classification, colorization, sequence-to-sequence, or generative modeling). - Where we need this: In system design, when deciding whether to treat a problem as a classification, regression, or generation task. In the exam, you should be able to identify and distinguish the different capabilities and task formulations of deep learning. Deep learning models can be broadly categorized by their output structure and training objectives: - Discriminative Tasks: Map high-dimensional inputs to simple structures (scalars or low-dimensional vectors): - Nonlinear Regression: Mapping continuous input properties to a continuous scalar output. For example, predicting the compressive strength (in MPa) of a concrete cylinder depending on component quantities (cement, slag, fly ash, water, superplasticizer, aggregates) and age. - Binary Classification: Mapping inputs to a single output value predicting a binary label. For example, distinguishing photographs of chihuahuas from blueberry muffins. - Categorical Classification: Mapping inputs to a probability distribution over $k$ categories. For example, handwritten digit recognition (MNIST) or object recognition with a fixed set of answers. - Acoustic Event Detection: Finding boundary transitions in sequential signals. For example, detecting structural boundaries in a music piece (e.g., transition from verse to chorus). - Translational / Mapping Tasks: Map structured inputs to structured outputs of similar dimensions. For example, image colorization (predicting RGB colors from a grayscale input image). - Generative Tasks: Creating structured outputs (images, audio, or text sequences) from scratch or from text prompts. - Image Generation: Creating colored images from text prompts (e.g., "horse sitting on an astronaut"). - Music Generation: Creating coherent audio waveforms or MIDI representations from text descriptions. - Text Generation: Generating text sequences recursively by predicting the next character or word given the preceding context (used in chatbot models and code generation). [Image] Overview of Deep Learning task formulations, categorized into discriminative, translational/mapping, and generative tasks. \subsection{Subchapter 8.2: How Deep Learning Works & Task Formalization}

This subchapter covers the fundamentals of audio representation, focusing on how continuous acoustic waveforms are converted into compact, biologically-motivated log-Mel spectrograms suitable for deep neural network inputs. - Why we need this: Raw audio signals (waveforms) are represented as high-frequency time-series (e.g., 44.1 kHz), containing immense redundancy. Standard neural networks cannot directly parse these signals to detect sound events. Log-Mel spectrograms compress this data into a 2D time-frequency grid, highlighting harmonic and temporal patterns like a visual image. - Where we need this: In the audio preprocessing pipeline. Continuous sound waveforms are segmented, transformed via STFT, mapped to Mel bands, and log-compressed to form the 2D feature map inputs for a CRNN model. In the exam, you will be expected to write down the Mel scale formula, describe the discrete Short-Time Fourier Transform (STFT) steps, and explain why log-compression and Mel filterbanks are biologically inspired. Audio signals are originally recorded in the time domain: - Waveform: A time-series $x(t)$ representing air pressure changes over time. Waveforms lack explicit frequency information, which is critical for distinguishing sound sources (e.g., the high pitch of a microwave beep vs. the broadband noise of running water). - Spectral Analysis: We partition the continuous signal into short overlapping segments (frames) and compute the frequency spectrum of each frame using the Fourier transform. To capture how frequency content changes over time, we use the Short-Time Fourier Transform (STFT): - Procedure: We slide a window function $w(n)$ of length $N$ (e.g., Hann window) across the signal $x(n)$ with a step size of $H$ samples (hop size). For each windowed frame, we compute the Discrete Fourier Transform (DFT). - Mathematical Formula: $X(m, k) = \sum_{n=0}^{N-1} x(n + m \cdot H) w(n) e^{-j \frac{2\pi}{N} k n}$ In English: The STFT coefficient $X(m, k)$ at frame index $m$ and frequency bin $k$ is the Discrete Fourier Transform of a windowed segment of the signal, where $w(n)$ is the window function, $N$ is the window size, and $H$ is the hop size separating successive frames. - Spectrogram: The magnitude spectrogram $|X(m, k)|$ or power spectrogram $|X(m, k)|^2$ represents the spectral energy at each time-frequency bin. The human auditory system does not perceive frequency changes linearly: - Mel Scale: A perceptual scale of pitches judged by listeners to be equal in distance from one another. Humans are much more sensitive to small frequency changes in lower ranges than in higher ranges. - Mel Conversion Formula: $m = 2595 \cdot \log_{10}\left(1 + \frac{f}{700}\right)$ In English: The pitch $m$ in Mels is calculated from the physical frequency $f$ in Hertz using a logarithmic scale, compression-scaling the higher frequencies to align with human hearing limits. - Mel Filterbank: We apply a set of overlapping triangular bandpass filters spaced linearly on the Mel scale to the power spectrogram. This warps the frequency axis and reduces the frequency bins (e.g., from 1025 DFT bins to 80 Mel bands), making the representation highly compact. Human perception of sound volume (loudness) is also logarithmic rather than linear: - Concept: A doubling of physical sound pressure level does not sound twice as loud. To mimic this, we apply a logarithmic compression to the Mel-spectrogram amplitudes. - Log-Mel Energy Formula: $S_{\text{log}}(m, b) = 10 \cdot \log_{10}\left( S_{\text{mel}}(m, b) \right)$ *In English: The compressed log-Mel value S_{\text{log*}(m, b) at frame $m$ and Mel band $b$ is obtained by taking the base-10 logarithm of the linear Mel energy $S_{\text{mel}}(m, b)$ and scaling by $10$, converting the values into the decibel (dB) scale.} [Image] Audio feature extraction pipeline: Raw audio amplitude waveform in the time domain (top) transformed into a 2D Log-Mel spectrogram representation in the time-frequency domain (bottom). \subsection{Subchapter 9.2: Sound Event Detection (SED) Task Formulation & Evaluation}

This subchapter details the fundamental differences between supervised and unsupervised learning, outlines the key goals of unsupervised algorithms, and provides mathematical formulations of unsupervised objectives (such as the Mean Quantisation Error). - Why we need this: In many real-world applications, labeled data is scarce or nonexistent. Unsupervised learning allows us to find natural groups in data, compress feature representations, discover outliers, and build generative models without needing manual human labels. - Where we need this: Customer segmentation, image/data compression, anomaly detection, audio-source separation, and data exploration. In the exam, you must be able to contrast predictive vs. descriptive modeling, list the three primary goals of unsupervised learning, and write the Mean Quantisation Error (MQE) equation. - Supervised Learning (Predictive/Discriminative Modeling): - Input: Training set $D = \{(x_i, y_i)\}$ of examples $x_i$ labeled with class $y_i \in \Omega$. - Goal: Learn a classification model that predicts class $y$ from features $x$. - Unsupervised Learning (Descriptive/Generative Modeling): - Input: Unlabeled dataset $D = \{x_i\}$. - Goal: Learn the underlying structure and distribution of the dataset. Unsupervised learning algorithms are designed to achieve one or more of the following goals: - Goal 1: Find Structure in the Data: Reveal natural, distinct groups of data points in the feature space (clustering). - Goal 2: Find Compact Description of Data: Find prototype representatives (centroids) and shape profiles for clusters to summarize the dataset (useful for data compression/quantisation). - Goal 3: Find a Generative Model: Model the dataset as if it were produced by a stochastic process (e.g., a mixture of Gaussians) governed by prior probabilities and density parameters. Clustering partitions a dataset into $k$ disjoint groups (clusters) using a distance measure in feature space: - Clustering Input: A set of objects $D = \{x_i\} \subset \mathcal{X}$ and a distance measure $D(\cdot, \cdot)$ (e.g., Euclidean distance). - Mean Quantisation Error (MQE): MQE is the quality criterion optimized (minimized) by clustering algorithms: $MQE = \frac{1}{|D|} \sum_{x_i \in D} D(x_i, c(x_i))$ In English: The Mean Quantisation Error (MQE) is computed as the average distance between each data point $x_i$ in the dataset $D$ and the centroid $c(x_i)$ of the cluster to which it has been assigned. - Centroid Notation: $c(x_i)$ represents the centroid of the cluster $C_j$ to which the instance $x_i$ belongs. MQE represents the average error or information loss incurred if we replace (approximate) each data point with its cluster center. [Image] Three core goals of unsupervised learning illustrated on a synthetic 2D dataset with three clusters. Left: Finding natural structures (disjoint groups). Middle: Finding compact descriptions (centroids and quantization error). Right: Finding a generative model (Gaussian Mixture Model density contours). \subsection{Subchapter 10.2: Clustering & The K-means Algorithm}