The K-Nearest Neighbors (KNN) algorithm is an *instance-based learner* — it does not build an explicit model during training. Instead, it stores all training examples and does all the work at prediction time. This is why KNN is called a *lazy learner*. The goal of KNN is to classify a new data point into one of a finite set of categories. This is called *approximating a discrete-valued target function*: the output is one specific value — yes or no, or Class A / Class B / Class C — rather than a continuous number. The set of possible classes is denoted $V=\{v_1,v_2,\dots ,v_m\}$. **Notation:** - An input instance has $n$ attributes: $⟨a_1(x),a_2(x),\dots ,a_n(x)⟩$ - $v\in V$ is one of the finite set of classes - $f(x_i)$ is the class predicted by training example $x_i$

**Phase 1 — Training (memorization only):** For every training example $⟨x,f(x)⟩$, add it to the list of training examples. Nothing else happens. The model does not learn a formula or a rule. It only stores all the data it has seen. This is what makes it a lazy learner. **Phase 2 — Classification (where the work happens):** When a new query instance $x_q$ arrives: 1. Find the $k$ instances from the stored training examples that are *physically closest* to $x_q$. Closeness is measured by a distance metric, most commonly Euclidean distance. 2. Let $x_1,x_2,\dots ,x_k$ denote the $k$ nearest training instances. 3. Look at the class of each neighbor and count the votes. 4. Return the class that has the most votes. The voting is formalized by: $$\hat{f}(x_q)\leftarrow {\mathrm{argmax}}_{v\in V}\sum _{i=1}^k\delta (v,f(x_i))$$ where $\delta (v,f(x_i))$ is the *Kronecker delta function*. This function equals $1$ if the neighbor's class $f(x_i)$ matches the class $v$ being checked; otherwise it equals $0$. > Think of it this way: for each possible class $v$, count how many of the $k$ neighbors belong to that class. Pick the class with the highest count.

The $\mathrm{argmax}$ function appears throughout machine learning. It returns the *argument* (the input value) that produces the *maximum* output, not the maximum output itself. For KNN, ${\mathrm{argmax}}_{v\in V}$ means: iterate over every possible class $v$ in the set $V$. For each class, compute the sum of Kronecker delta votes. Return the class $v$ that had the largest sum.

Standard KNN treats all $k$ neighbors equally, regardless of how far they are from the query point. This causes a problem: One neighbor may be extremely close to the query point (almost overlapping), strongly indicating that the query point belongs to that neighbor's class. But other neighbors, though farther away, happen to be among the $k$ closest and outvote the truly close neighbor. The prediction is wrong even though the most similar training example points to the correct answer. **Solution:** Give more voting power to closer neighbors. Neighbors that are closer to the query point should have a larger influence on the prediction. Neighbors farther away should have a smaller influence.

Weight functions in KNN are also called *kernel functions*. A kernel function defines the similarity between pairs of data points in a high-dimensional feature space. In KNN, the kernel converts the distance between the query point and a neighbor into a similarity score (the weight). **Why "kernel"?** The term is most commonly used for SVM, ridge regression, and Gaussian processes. Any function that defines similarity between pairs of data points and is used as a weight is called a kernel. In KNN, the kernel serves as a similarity measure between a training point and the query point. **Common weight functions (kernels):** **1. Inverse distance (simplest):** $$w_i=\frac{1}{d(x_q,x_i)}$$ A neighbor at distance 2 gets weight $1/2$. A neighbor at distance 0.5 gets weight $1/0.5=2$. Simple but breaks when distance equals zero (division by zero → weight → infinity). **2. Inverse square distance:** $$w_i=\frac{1}{d(x_q,x_i{)}^2}$$ The influence of points drops off much faster. A neighbor at distance 2 gets weight $1/4$ instead of $1/2$. This faster drop-off is called a higher *decay*. **3. Modified inverse square distance (with $d_0$):** $$w_i=\frac{1}{(d_0+d(x_q,x_i){)}^2}$$ $d_0$ is a very small positive constant (e.g., $0.0001$ or $10^{-5}$). This prevents division by zero when the query point exactly overlaps a training point. The maximum possible weight any point can get is now capped at $1/d_0^2$. Even if the distance is zero, the denominator is still at least $d_0$. > **Q:** What happens when distance $d=0$? > **A:** The query point is identical to (overlapping with) a training point. Without $d_0$, the weight would be $1/0$ — infinity. That makes sense conceptually (we want maximum weight for an identical point), but infinity causes numerical problems. So $d_0$ caps the weight. The weight will still be huge relative to other neighbors, and that neighbor will dominate the vote — which is exactly what we want. **How to choose $d_0$:** No standard method exists. Common approaches: - Set $d_0$ to a very small value like $0.0001$ or $10^{-5}$ - Try a range of values ($0.01,0.1,0.5,1.0$) and use cross validation to pick the best one **4. Gaussian kernel (Gaussian decay):** $$w_i=e^{-{\left(\frac{d(x_q,x_i)}{\sigma }\right)}^2}$$ or equivalently: $$w_i=\exp \left(-\frac{d(x_q,x_i{)}^2}{2b}\right)$$ where $\sigma$ (or $b$) controls the *width* (bandwidth) of the kernel: - **Small $\sigma$ (small $b$):** Only very close neighbors get significant weight. Far points get weight near zero. - **Large $\sigma$ (large $b$):** Even distant points get non-zero weight. The kernel is wider. The Gaussian kernel drops to near-zero very quickly because of the squared term. Only extremely close neighbors matter significantly. If the data roughly follows a Gaussian (bell-curve) distribution, the Gaussian kernel is a natural choice. The denominator ($\sigma$ or $\sqrt{2b}$) determines the width — analogous to standard deviation.

The linear approximation model for a query point $x_q$: $$\hat{f}(x)\approx w_0+w_1{a}_1(x)+w_2{a}_2(x)+\cdots +w_n{a}_n(x)$$ where: - $\hat{f}(x)$ is the predicted value - $w_0$ is the *bias* or *intercept* — the baseline prediction when all input attributes are zero - $w_1,w_2,\dots ,w_n$ are the *slopes* — each measures the importance or influence of a specific attribute. A larger weight means that attribute has a stronger influence on the output - $a_i(x)$ is the value of the $i$-th attribute of instance $x$ **Global error function (standard linear regression):** $$E=\frac{1}{2}\sum _{x\in D}{\left(f(x)-\hat{f}(x)\right)}^2$$ The $\frac{1}{2}$ is a mathematical convenience — when we take the derivative to find the minimum, the exponent 2 cancels out the $\frac{1}{2}$. **Gradient descent update rule (standard):** $$w_j\leftarrow w_j+\eta \sum _{x\in D}\left(f(x)-\hat{f}(x)\right)a_j(x)$$ where $\eta$ (eta) is the *learning rate* — a small number controlling the step size. Too large: overshoot the best solution. Too small: training takes forever.

*Radial basis functions* (RBFs) are closely related to distance-weighted regression and KNN. They also heavily rely on distance: the closer an input is to a center point, the more influence that center has on the prediction. RBFs are extensively used in *artificial neural networks* (ANNs). An RBF network has exactly three layers: 1. **Input layer** — receives the data 2. **Hidden layer** — applies the radial basis function for non-linear transformation 3. **Output layer** — performs a linear weighted sum **The RBF hypothesis (prediction function):** $$\hat{f}(x)=w_0+\sum _{u=1}^K{w}_u\cdot K(d(x,x_u))$$ where: - $\hat{f}(x)$ is the predicted output - $w_0$ is the bias term - $K$ (uppercase) is the number of components — analogous to the number of nearest neighbors. This $K$ is a user-defined parameter (distinct from the kernel function). - $w_u$ is the weight learned during training for component $u$ - $K(d(x,x_u))$ (lowercase $k$ for kernel function) is the kernel / basis function — converts distance to a similarity score

All models studied so far (KNN, linear regression, logistic regression) treat model parameters (like the weights $w$) as *fixed unknown constants* to be discovered. For example, we say "the slope is 2.5" — a single definitive number. *Bayesian learning* takes a different approach. It treats everything probabilistically. Instead of saying "the slope is 2.5," Bayesian reasoning says "based on the data, the slope is likely around 2.5, but there is some uncertainty." In Bayesian learning: - Information is not treated as hard fact but as a *degree of belief* measured by probability - We start with a *prior belief* — what we think is true before seeing any data - We update that belief as we gather new evidence - The result is an *updated belief* — a new probability that incorporates both the prior and the evidence This is fundamentally different from starting from scratch every time. Bayesian methods build on existing knowledge.

A *random variable* is a mathematical concept used to represent a quantity that can take different values depending on the outcome of a random event. It is a function that maps outcomes of a random event to numerical values. **Two types:** **Discrete random variable:** Takes on a *countable* number of distinct values. - Example 1: Number of heads in three coin tosses. Possible values: $X\in \{0,1,2,3\}$. - Example 2: Result of rolling a die. Possible values: $X\in \{1,2,3,4,5,6\}$. **Continuous random variable:** Takes on an *uncountable* number of values within a range or interval. - Example 1: Height of a person - Example 2: Time to run a race - The variable can be 170.1, 170.13, 170.137, etc. — infinitely many values in any interval.

A *probability distribution* describes how probabilities are spread across different possible outcomes. **For discrete random variables — Probability Mass Function (PMF):** The PMF gives the probability that a discrete random variable takes on a specific value. For example, for a fair die: $P(X=3)=\frac{1}{6}$. **For continuous random variables — Probability Density Function (PDF):** The PDF gives the *probability density*, not the probability itself. For a continuous variable, the probability of taking any single exact value is 0 (there are infinitely many possible values). Instead, the PDF helps compute the probability over an *interval*. For example, the probability that a person's weight is between 160 and 170 pounds is the *area under the PDF curve* between 160 and 170 — computed by integration.

*Parameter estimation* is the process of estimating the parameters of a statistical model or probability distribution based on observed data. **Forward problem (probability):** You are *given* the parameters of a distribution. Example: "The data follows a Gaussian distribution with $\mu =10$ and $\sigma =2$. What is the probability that a randomly drawn value is 16?" This is what is taught in probability courses. **Reverse problem (parameter estimation):** You are *given* the data but *do not know* the parameters. Example: "Here are the heights of 1,000 people. What values of $\mu$ and $\sigma$ for a Gaussian distribution would have most likely generated this data?"

**Point Estimation:** Gives a *single specific number* as the best guess for the parameter. Finds the value that maximizes (or minimizes) some function related to the data, such as a likelihood function. Example: Survey 100 people. The average height is exactly 175 cm. This single number (175) is the point estimate for $\mu$. **Interval Estimation:** Gives a *range of possible values* for the parameter. This range is called a *confidence interval*. Example: "I am 95% confident that the true mean height of the population is between 173 cm and 177 cm."