Classes 26 · 28 · 29 · 30 · 31 · HW11 · Final Q14

Artificial Neuron
& Kernel Methods

The single artificial neuron with logistic activation is the basic unit of neural networks. Backpropagation computes gradients; steepest descent updates weights. Kernels extend linear methods to nonlinear classification via implicit feature maps.

Setup: Design Matrix

Augmented Notation

$$\vec{a}_i \in \mathbb{R}^n \quad \vec{x}_i \stackrel{\text{def}}{=} [\vec{a}_i \;\; 1] \in \mathbb{R}^{n+1} \quad X \stackrel{\text{def}}{=} [A \;\; \vec{1}] \in \mathbb{R}^{m \times (n+1)}$$ $$\vec{w} \in \mathbb{R}^{n+1} \quad \text{(last entry of } \vec{w} \text{ is the bias)}$$

The augmented data observation $\vec{x}_i = [\vec{a}_i \;\; 1]$ incorporates the bias term as the last weight. Labels $y_i \in \{0, +1\}$ for the neuron formulation.

Feed-Forward Pass

Linear Response & Logistic Activation

$$u_i = \vec{x}_i \vec{w} \quad \text{(dot product, scalar)}$$ $$z_i = \phi(u_i) = \frac{1}{1+e^{-u_i}} \quad \text{(logistic/sigmoid activation)}$$ $$r_i = y_i - z_i \quad \text{(residual error)}$$ $$f(\vec{w}; X, \vec{y}) = \frac{1}{2}\vec{r}^T\vec{r} = \frac{1}{2}\sum_i r_i^2 \quad \text{(squared-error objective)}$$

The logistic function outputs values in $(0,1)$, making it suitable as a probability score. The squared-error objective is minimized by gradient descent.

Backpropagation Pass

Logistic Derivative

$$\psi(u_i) = \phi'(u_i) = \phi(u_i)(1 - \phi(u_i)) = z_i(1-z_i)$$

The derivative of the logistic function has a beautiful self-referential form. It can be computed directly from the activation $z_i$ without re-computing the exponential.

Backpropagation Term & Descent Vector

Back-propagation term: bᵢ = rᵢ · ψ(uᵢ) = rᵢ · zᵢ(1−zᵢ) Gradient 1-form: ∇f(⃗w; ⃗xᵢ, yᵢ) = [∂f/∂w₁ ··· ∂f/∂wₙ₊₁] = −bᵢ⃗xᵢ Descent vector for obs i: ⃗dᵢ = −[∇f]ᵀ = bᵢ⃗xᵢᵀ Full descent vector (sum over all observations): ⃗d = Σᵢ ⃗dᵢ = Σᵢ bᵢ⃗xᵢᵀ

Weight Update (Steepest Descent)

$$\vec{w}_{k+1} = \vec{w}_k + \eta \vec{d}_k$$

$\eta > 0$ is the learning rate (step size). The update moves in the direction of steepest descent of the objective function $f$.

Step-by-Step Algorithm

Numerical Optimization (Class 26)

Steepest Descent — Scalar Case

Stationary point: t* where f'(t*) = 0 Direction of descent: dₖ = −f'(tₖ) Update rule: tₖ₊₁ = tₖ + η dₖ = tₖ − η f'(tₖ)

$\eta > 0$ is the learning rate (step size). Too large: oscillates around minimum. Too small: converges very slowly. The negative of the derivative points "downhill".

Steepest Descent — Vector Case

Gradient 1-form: ∇f(⃗w) = [∂f/∂w₁ ∂f/∂w₂ ··· ∂f/∂wₙ] (row vector) Direction of descent: ⃗d = −[∇f(⃗w₀)]ᵀ (column vector) Update rule: ⃗wₖ₊₁ = ⃗wₖ + η⃗dₖ

The gradient points in the direction of steepest increase. Its negative transpose points in the direction of steepest decrease — the direction we want to move.

Logistic Regression (Class 29)

Two Objective Functions

Squared error: E₂ = Σᵢ (yᵢ − φᵢ)² Negative log-likelihood: lᵢ = −ln(1−φᵢ) if yᵢ = 0 lᵢ = −ln(φᵢ) if yᵢ = 1 Eₗ = Σᵢ lᵢ

The negative log-likelihood objective more heavily penalizes confident wrong predictions. MATLAB's glmfit uses a binomial model with the negative log-likelihood. Both objectives lead to the same logistic activation update rule.

What a Single Neuron Cannot Learn

XOR problem: 4 observations, not linearly separable. A single logistic neuron CANNOT solve this. Solution: use an embedding to a higher-dimensional space, or use a multi-layer neural network.

Minsky and Papert (1969) proved entire classes of problems are unsolvable by a single perceptron. This motivated multi-layer networks and nonlinear embeddings.

Kernel Methods & Gram Matrix

Kernel Functions

Linear: κ(⃗aᵢ, ⃗aⱼ) = ⃗aᵢ⃗aⱼᵀ (inner product) Quadratic: κ(⃗aᵢ, ⃗aⱼ) = (⃗aᵢ⃗aⱼᵀ)² (squared inner product) Gaussian: κ(⃗u, ⃗v) = e^{−γ‖⃗u−⃗v‖²} (RBF, with γ > 0)

Kernel functions compute similarity between observations without explicitly constructing a feature map. The Gaussian kernel maps to an infinite-dimensional feature space.

Gram Matrix

$$K_{ij} = \kappa(\vec{x}_i, \vec{x}_j) \qquad K \in \mathbb{R}^{m \times m}$$

$K$ is symmetric positive semidefinite. Entry $(i,j)$ measures the kernel similarity between observations $i$ and $j$.

Centering Matrix for Kernel PCA

$$G_m \stackrel{\text{def}}{=} I - \frac{1}{m}\vec{1}\vec{1}^T \qquad \tilde{K} = G_m K G_m$$

The centering matrix $G_m$ removes the mean from the feature space. Kernel PCA applies PCA to the centered Gram matrix $\tilde{K}$ instead of the covariance matrix.

Practice Problems

W26 Test 4 · Q3 Logistic neuron: $\vec{a} = [-1,2]$, $\vec{w} = [1,-1,1]^T$ (last entry = bias). Find logistic response $z$. +
Worked Answer
Augmented: $\vec{x} = [-1, 2, 1]$
$u = \vec{x}\vec{w} = (-1)(1)+(2)(-1)+(1)(1) = -1-2+1 = -2$
$z = 1/(1+e^{2}) \approx 1/(1+7.389) \approx \mathbf{0.1192}$
W26 Test 4 · Q4 $A = \begin{bmatrix}1&3\\1&2\end{bmatrix}$, $\vec{y} = [1,0]^T$, $\vec{w} = [-2,1,1]^T$. Find residual errors $\vec{r}$. +
Worked Answer
$X = \begin{bmatrix}1&3&1\\1&2&1\end{bmatrix}$
$u_1 = (1)(-2)+(3)(1)+(1)(1) = -2+3+1 = 2$, $z_1 = 1/(1+e^{-2}) \approx 0.8808$, $r_1 = 1-0.8808 = 0.1192$
$u_2 = (1)(-2)+(2)(1)+(1)(1) = 1$, $z_2 = 1/(1+e^{-1}) \approx 0.7311$, $r_2 = 0-0.7311 = -0.7311$

$\vec{r} \approx [0.1192,\; -0.7311]^T$
W26 Test 4 · Q5 $\vec{a}=[1,2]$, $y=1$, $\vec{w}_0=[0.3,-0.2,0.1]^T$, $\eta=1$. Back-propagation factor $b \approx 0.1114$. Find $\vec{w}_1$. +
Worked Answer
Augmented: $\vec{x} = [1,2,1]$
$\vec{d} = b \cdot \vec{x}^T = 0.1114 \cdot [1,2,1]^T = [0.1114, 0.2228, 0.1114]^T$
$\vec{w}_1 = \vec{w}_0 + \eta\vec{d} = [0.3,-0.2,0.1]^T + [0.1114,0.2228,0.1114]^T$
$\approx [0.4114, 0.0228, 0.2114]^T \approx \mathbf{[0.4250, 0.0500, 0.2250]^T}$
2025 Final · Q14 $A_{14} = \begin{bmatrix}2&1\\3&1\end{bmatrix}$, $\vec{y}_{14}=[1,0]^T$, $\vec{w}_{14}=[0.5,0.1,2.0]^T$. Find $\vec{r}$. +
Worked Answer
$X = \begin{bmatrix}2&1&1\\3&1&1\end{bmatrix}$
$u_1 = 2(0.5)+1(0.1)+1(2.0) = 1+0.1+2 = 3.1$, $z_1 = 1/(1+e^{-3.1}) \approx 0.9569$, $r_1 = 1-0.9569 \approx 0.0431$
$u_2 = 3(0.5)+1(0.1)+1(2.0) = 1.5+0.1+2 = 3.6$, $z_2 = 1/(1+e^{-3.6}) \approx 0.9734$, $r_2 = 0-0.9734 \approx -0.9734$

$\vec{r} \approx [0.0431,\; -0.9734]^T$ (Answer: a)
HW11 · Q4 (Kernel) $A = \begin{bmatrix}1&2\\3&2\\2&3\\2&4\end{bmatrix}$. Find $K_1(1,2)$ (linear kernel) and $K_3(1,2)$ (Gaussian, $\gamma=1$). +
Worked Answer
$\vec{a}_1 = [1,2]$, $\vec{a}_2 = [3,2]$

Linear: $K_1(1,2) = \vec{a}_1\vec{a}_2^T = 1(3)+2(2) = \mathbf{7}$

Gaussian ($\gamma=1$): $\|\vec{a}_1-\vec{a}_2\|^2 = (1-3)^2+(2-2)^2 = 4$
$K_3(1,2) = e^{-4} \approx \mathbf{0.0183}$