Maximum-margin classifiers and kernels, linear and nonlinear time series, and IF–THEN rule learning, with Lab 12.
This chapter continues Unit II with three further families of techniques: support vector machines and kernel methods for classification, time-series analysis (both linear systems and nonlinear dynamics) for data ordered in time, and rule induction for learning readable IF–THEN rules. Each topic includes a worked calculation.
5.1 Support vector and kernel methods
A support vector machine (SVM) is a classifier that separates two classes with the boundary that has the largest margin — the widest possible gap between the boundary and the nearest points of each class. In two dimensions the boundary is a line; in general it is a hyperplane w · x + b = 0, where w is a weight vector perpendicular to the boundary and b is an offset. The nearest points, which lie exactly on the edges of the margin where w · x + b = ±1, are called support vectors; only they determine the boundary, so the model is robust to points far away. The margin width is 2 / ‖w‖, so maximising the margin means minimising ‖w‖. Real data is rarely perfectly separable, so the soft-margin SVM allows some points inside the margin or on the wrong side, with a penalty controlled by the parameter C: a large C fits the training data tightly and risks overfitting, while a small C gives a wider, more tolerant margin.
Kernel methods. When the classes cannot be separated by a straight line — as in the XOR pattern — the data can be mapped by a function φ into a higher-dimensional space where a linear separator exists. Computing φ explicitly may be very expensive, but the SVM needs only dot products, so a kernel function K(x, y) = φ(x) · φ(y) computes them directly in the original space. This is the kernel trick.
| Kernel | Formula | When used |
|---|---|---|
| Linear | K(x, y) = x · y | Data already linearly separable; text with many features |
| Polynomial | K(x, y) = (x · y + c)^d | Curved boundaries of known degree |
| RBF (Gaussian) | K(x, y) = exp(−γ‖x − y‖²) | General default for non-linear data |
| Sigmoid | K(x, y) = tanh(α x · y + c) | Behaves like a neural network |
For the RBF kernel, γ controls how far each training point's influence reaches: a high γ gives a wiggly boundary that can overfit, a low γ a smooth one.
Worked example 1 – finding the maximum-margin line. Class −1 has support vector A = (1, 1) and class +1 has support vector B = (3, 3).
- The best boundary is perpendicular to AB, so w = (a, a) for some a.
- At the support vectors, w · x + b = ±1: for A, a(1 + 1) + b = −1, i.e. 2a + b = −1; for B, a(3 + 3) + b = +1, i.e. 6a + b = 1.
- Subtracting: 4a = 2, so a = 0.5 and b = −1 − 2(0.5) = −2. The boundary is 0.5x₁ + 0.5x₂ − 2 = 0, i.e. x₁ + x₂ = 4.
- Margin = 2 / ‖w‖ = 2 / √(0.25 + 0.25) = 2 / 0.7071 = 2.828, which equals the distance between A and B, √(2² + 2²) = √8.
- Classify a new point (4, 1): 0.5 × 4 + 0.5 × 1 − 2 = 0.5 > 0, so it is class +1. The point (0, 2) gives 0 + 1 − 2 = −1 < 0, so it is class −1.
Worked example 2 – the kernel trick. Let x = (1, 2) and y = (3, 4).
- Linear kernel: x · y = 1 × 3 + 2 × 4 = 11.
- Polynomial kernel with c = 0, d = 2: (x · y)² = 11² = 121.
- Check by explicit mapping φ(v) = (v₁², √2·v₁v₂, v₂²): φ(x) = (1, 2.828, 4) and φ(y) = (9, 16.97, 16). Their dot product is 9 + 48 + 64 = 121 — the same answer, obtained without ever building φ.
- RBF kernel with γ = 0.5: ‖x − y‖² = (1 − 3)² + (2 − 4)² = 8, so K = e^(−0.5 × 8) = e^(−4) = 0.0183; the two points are far apart, so their similarity is small.
Read more on the blog: Support Vector Machine.
5.2 Analysis of time series: linear systems analysis and nonlinear dynamics
A time series is a sequence of observations recorded at successive, usually equal, intervals of time, such as daily sales or monthly rainfall. Unlike ordinary data, the order matters, because each value is related to the values before it. A time series is usually seen as the combination of four components: the trend (long-term upward or downward movement), seasonality (a pattern that repeats every year, week or day), cyclic variation (longer, irregular business cycles) and irregular or random variation. Many models require the series to be stationary, meaning its mean and variance do not change over time; a trend can be removed by differencing (taking yₜ − yₜ₋₁). Simple forecasting methods include the moving average, which averages the last k values, and exponential smoothing, which weights recent values more heavily: Fₜ₊₁ = αyₜ + (1 − α)Fₜ, with 0 < α < 1.
Linear systems analysis. A linear system obeys the principle of superposition: if input u₁ produces output y₁ and input u₂ produces y₂, then the input u₁ + u₂ produces y₁ + y₂, and scaling the input scales the output by the same factor. For example, if a system doubles its input, then inputs 3 and 4 give 6 and 8, and the input 3 + 4 = 7 gives 14 = 6 + 8. Linear time-series models assume the next value is a linear combination of past values and past random shocks. The autoregressive model AR(p) is Xₜ = c + φ₁Xₜ₋₁ + … + φₚXₜ₋ₚ + εₜ; the moving-average model MA(q) uses past errors; ARMA(p, q) combines both; and ARIMA(p, d, q) first differences the series d times to make it stationary. The orders p and q are chosen by studying the autocorrelation (ACF) and partial autocorrelation (PACF) plots, and cycles can be found with frequency-domain (Fourier) analysis. Linear models are simple and interpretable but cannot capture sudden changes in behaviour.
Nonlinear dynamics. Many real systems — weather, heartbeats, financial markets — are nonlinear, so superposition does not hold and small changes in input can produce very large changes in output. Some nonlinear systems are chaotic: they are fully deterministic, yet two starting points that differ very slightly diverge rapidly, which makes long-term prediction impossible. The states that such a system settles into form an attractor (a strange attractor for chaotic systems). Because usually only one variable is observed, the system's state is reconstructed by time-delay embedding (Takens' theorem), and the rate of divergence is measured by the Lyapunov exponent, which is positive for chaos. Nonlinear models include threshold autoregressive (TAR) models, GARCH models for changing volatility, and neural-network forecasters.
Worked example 1 – moving average and exponential smoothing. Monthly sales are 10, 12, 14, 13, 15, 17 (thousand units).
- 3-month moving averages: (10 + 12 + 14) / 3 = 12.0; (12 + 14 + 13) / 3 = 13.0; (14 + 13 + 15) / 3 = 14.0; (13 + 15 + 17) / 3 = 15.0. The forecast for month 7 is the last average, 15.0.
- Exponential smoothing with α = 0.3 and starting forecast F₁ = 10:
| Month t | Actual yₜ | Forecast Fₜ | Calculation of Fₜ₊₁ = 0.3yₜ + 0.7Fₜ |
|---|---|---|---|
| 1 | 10 | 10.000 | 0.3(10) + 0.7(10) = 10.000 |
| 2 | 12 | 10.000 | 0.3(12) + 0.7(10) = 10.600 |
| 3 | 14 | 10.600 | 0.3(14) + 0.7(10.6) = 11.620 |
| 4 | 13 | 11.620 | 0.3(13) + 0.7(11.62) = 12.034 |
| 5 | 15 | 12.034 | 0.3(15) + 0.7(12.034) = 12.924 |
| 6 | 17 | 12.924 | 0.3(17) + 0.7(12.924) = 14.147 |
The forecast for month 7 is 14.15. It lags behind the rising trend, which is why trend-adjusted methods (Holt's) are used for trending data.
Worked example 2 – an AR(1) forecast. A fitted model is Xₜ = 5 + 0.6Xₜ₋₁. If this month's value is 17, next month's forecast is 5 + 0.6 × 17 = 15.2, and the month after is 5 + 0.6 × 15.2 = 14.12. The forecasts approach the long-run mean c / (1 − φ) = 5 / 0.4 = 12.5.
Worked example 3 – sensitivity in a nonlinear system. The logistic map xₙ₊₁ = 4xₙ(1 − xₙ) is started from 0.200 and from 0.201, a difference of only 0.001.
| n | Start 0.200 | Start 0.201 | Difference |
|---|---|---|---|
| 0 | 0.2000 | 0.2010 | 0.0010 |
| 1 | 0.6400 | 0.6424 | 0.0024 |
| 2 | 0.9216 | 0.9189 | 0.0027 |
| 3 | 0.2890 | 0.2981 | 0.0091 |
| 4 | 0.8219 | 0.8370 | 0.0151 |
| 5 | 0.5854 | 0.5457 | 0.0397 |
The gap grows about forty-fold in five steps, so after a few more steps the two series are unrelated. A linear model cannot represent this behaviour.
Read more on the blog: Analysis of Time Series.
Lab 12 (R) – Build a time-series model and evaluate its accuracy
Aim: forecast monthly airline passengers (built-in AirPassengers, 1949–1960) with ARIMA and exponential smoothing, and compare their accuracy on held-out data.
install.packages("forecast")
library(forecast)
ts_data <- AirPassengers
plot(ts_data, main = "Monthly airline passengers", ylab = "Passengers (000s)")
plot(decompose(ts_data, type = "multiplicative")) # trend + seasonality + random
# Hold out the last 2 years for testing
train <- window(ts_data, end = c(1958, 12))
test <- window(ts_data, start = c(1959, 1))
# Model 1: ARIMA (log transform stabilises growing seasonal swings)
fit_arima <- auto.arima(train, lambda = 0)
summary(fit_arima)
fc_arima <- forecast(fit_arima, h = length(test))
# Model 2: exponential smoothing (ETS / Holt-Winters)
fit_ets <- ets(train)
fc_ets <- forecast(fit_ets, h = length(test))
# Accuracy on the test set: RMSE, MAE, MAPE
accuracy(fc_arima, test)
accuracy(fc_ets, test)
autoplot(fc_arima) + autolayer(test, series = "Actual")
checkresiduals(fit_arima) # residuals should look like white noise
# Final forecast for the next 12 months using all data
forecast(auto.arima(ts_data, lambda = 0), h = 12)
The model with the lower test RMSE and MAPE is the better choice.
5.3 Rule induction
Rule induction learns a set of IF–THEN rules from data, such as "IF outlook = overcast THEN play = yes". Because each rule is readable, the resulting model can be checked and explained by domain experts, which is a major advantage over black-box methods. Each rule is judged by two measures. Coverage is the fraction of all records that satisfy the rule's IF part, and accuracy (confidence) is the fraction of covered records for which the THEN part is correct. Rules can be learned by converting each root-to-leaf path of a decision tree into a rule, or directly by sequential covering algorithms such as 1R, CN2 and RIPPER: learn one good rule, remove the records it covers, and repeat until few records remain. The simplest method, 1R (One Rule), builds one rule per value of a single attribute — predicting the majority class for each value — and keeps the attribute whose rules make the fewest errors.
Worked example – 1R on the weather data. The classic 14-day "play tennis" dataset has 9 yes and 5 no days.
| Attribute | Value | Yes | No | Rule (majority) | Errors |
|---|---|---|---|---|---|
| Outlook | Sunny | 2 | 3 | → No | 2 |
| Outlook | Overcast | 4 | 0 | → Yes | 0 |
| Outlook | Rain | 3 | 2 | → Yes | 2 |
| Humidity | High | 3 | 4 | → No | 3 |
| Humidity | Normal | 6 | 1 | → Yes | 1 |
- Outlook rules make 2 + 0 + 2 = 4 errors in 14 records; humidity rules make 3 + 1 = 4 errors. Both give accuracy (14 − 4) / 14 = 71.4%; 1R breaks the tie by choosing either, here outlook.
- Rule "IF outlook = overcast THEN play = yes": coverage = 4 / 14 = 28.6%, accuracy = 4 / 4 = 100%.
- Rule "IF outlook = sunny THEN play = no": coverage = 5 / 14 = 35.7%, accuracy = 3 / 5 = 60% — a weaker rule that a sequential-covering method would refine, for example by adding "AND humidity = high".
- For comparison, always predicting the majority class yes gives 9 / 14 = 64.3%, so the single-attribute rules already improve on the baseline.
Read more on the blog: Rule Induction.
Independent study notes written in my own words, for learning purposes. Not affiliated with any university or course provider. R, RStudio, Hadoop, Amazon S3, Tableau, Power BI and other product names are trademarks of their respective owners.