Machine Learning From Scratch in Pure C: Module I — Supervised Learning & Foundations

Machine Learning From Scratch in Pure C

Module I: Supervised Learning & Model Validation

When studying machine learning, Python and libraries like Scikit-Learn or PyTorch often hide the low-level mechanics under high-level abstractions. Implementing these foundational algorithms in pure ANSI C exposes the core mathematics: mean deviations, 2x2 matrix determinants, Euclidean spatial metrics, Laplace conditional distributions, and gradient descent updates.

Every program in this lab guide is self-contained, written in standard C (<stdio.h> and <math.h>), and designed with clean, step-by-step logic suitable for lab exams, technical viva voce, and fast handwritten code reproduction.

---

Module I Syllabus & Lab Mapping

Lab #	Topic / Algorithm	Type	Core Mathematical Concept
Lab 01	Simple Linear Regression	Supervised (Regression)	Ordinary Least Squares (OLS) & Mean Deviations
Lab 02	Multiple Linear Regression	Supervised (Regression)	Deviation Product System & 2x2 Closed-Form Determinants
Lab 03	K-Nearest Neighbors (KNN)	Supervised (Classification)	Instance-based Euclidean Distance & Majority Voting
Lab 04	Naïve Bayes Classifier	Supervised (Classification)	Conditional Independence, Prior Probabilities & Laplace Smoothing
Lab 05	Logistic Regression	Supervised (Classification)	Sigmoid Hypothesis & Batch Gradient Descent Optimization
Lab 06	Leave-One-Out CV (LOOCV)	Model Evaluation	Exhaustive Resampling & Mean Squared Error (MSE)

---

Lab 01: Simple Linear Regression (Ordinary Least Squares)

1. Problem Statement

Implement Simple Linear Regression using Ordinary Least Squares (OLS). Given a training set of input features $x$ and continuous target outcomes $y$, compute:

1. Feature and target sample means ($\bar{x}, \bar{y}$)
2. Regression slope ($b_1$) and y-intercept ($b_0$)
3. The fitted linear model $\hat{y} = b_0 + b_1x$
4. Output predictions for unseen query values.

2. Core Mathematical Formulation

• Sample Means:
  $$\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i, \quad \bar{y} = \frac{1}{n}\sum_{i=1}^{n} y_i$$

• Slope Coefficient ($b_1$):
  $$b_1 = \frac{\sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=1}^{n} (x_i - \bar{x})^2}$$

• Y-Intercept ($b_0$):
  $$b_0 = \bar{y} - b_1\bar{x}$$

3. Pure C Implementation

#include <stdio.h>

int main() {
    int n = 4, i;
    // Training dataset: Study hours (x) vs Exam marks (y)
    float x[] = {1.0, 2.0, 3.0, 4.0};
    float y[] = {2.0, 3.0, 5.0, 6.0};

    float sum_x = 0.0, sum_y = 0.0;
    float mx, my;
    float num = 0.0, den = 0.0;
    float b0, b1;
    float test_x = 5.0, pred_y;

    // Step 1: Calculate arithmetic means
    for (i = 0; i < n; i++) {
        sum_x += x[i];
        sum_y += y[i];
    }
    mx = sum_x / n;
    my = sum_y / n;

    // Step 2: Compute deviation products (num) and squared deviations (den)
    for (i = 0; i < n; i++) {
        num += (x[i] - mx) * (y[i] - my);
        den += (x[i] - mx) * (x[i] - mx);
    }

    // Step 3: Compute slope (b1) and intercept (b0)
    b1 = num / den;
    b0 = my - (b1 * mx);

    // Step 4: Make prediction for new observation
    pred_y = b0 + (b1 * test_x);

    printf("=== Lab 01: Simple Linear Regression ===\n");
    printf("Mean X = %.2f, Mean Y = %.2f\n", mx, my);
    printf("Slope (b1) = %.2f\n", b1);
    printf("Intercept (b0) = %.2f\n", b0);
    printf("Fitted Equation: y = %.2f + %.2fx\n", b0, b1);
    printf("Prediction for x = %.1f -> y = %.2f\n", test_x, pred_y);

    return 0;
}

4. Implementation Walkthrough & Memory Triggers

• Two-Pass Loop Strategy: The first loop computes the means (mx and my). The second loop calculates the centered deviations (x[i] - mx) and accumulates the covariance numerator and variance denominator.
• Calculation Sequence: Always resolve b1 = num / den before computing b0 = my - b1 * mx, since $b_0$ explicitly depends on $b_1$.
• Time & Space Complexity: Time Complexity is $\mathcal{O}(n)$, Space Complexity is $\mathcal{O}(1)$ auxiliary space.

5. Sample Execution Output

=== Lab 01: Simple Linear Regression ===
Mean X = 2.50, Mean Y = 4.00
Slope (b1) = 1.40
Intercept (b0) = 0.50
Fitted Equation: y = 0.50 + 1.40x
Prediction for x = 5.0 -> y = 7.50

---

Lab 02: Multiple Linear Regression (Two Features)

1. Problem Statement

Implement Multiple Linear Regression with two independent continuous predictor variables ($X_1, X_2$) and one dependent target variable ($Y$). Solve the linear equation:
$$\hat{Y} = b_0 + b_1X_1 + b_2X_2$$
using closed-form deviation products and 2x2 determinants.

2. Core Mathematical Formulation

• Centering Variables (Mean Deviations):
  $$x_1 = X_1 - \bar{X}_1, \quad x_2 = X_2 - \bar{X}_2, \quad y = Y - \bar{Y}$$

• Coefficient Solution via System Determinants:
  $$b_1 = \frac{(\sum x_1 y)(\sum x_2^2) - (\sum x_2 y)(\sum x_1 x_2)}{(\sum x_1^2)(\sum x_2^2) - (\sum x_1 x_2)^2}$$
  $$b_2 = \frac{(\sum x_2 y)(\sum x_1^2) - (\sum x_1 y)(\sum x_1 x_2)}{(\sum x_1^2)(\sum x_2^2) - (\sum x_1 x_2)^2}$$

• Model Intercept ($b_0$):
  $$b_0 = \bar{Y} - b_1\bar{X}_1 - b_2\bar{X}_2$$

3. Pure C Implementation

#include <stdio.h>

int main() {
    int n = 3, i;
    // Input features X1, X2 and Target Y
    float X1[] = {1.0, 2.0, 3.0};
    float X2[] = {1.0, 2.1, 2.9};
    float Y[]  = {3.0, 5.8, 9.2};

    float m1 = 0.0, m2 = 0.0, my = 0.0;
    float s11 = 0.0, s22 = 0.0, s12 = 0.0, s1y = 0.0, s2y = 0.0;
    float den, b0, b1, b2;
    float test_x1 = 4.0, test_x2 = 3.8, pred_y;

    // Step 1: Calculate feature and target sample means
    for (i = 0; i < n; i++) {
        m1 += X1[i];
        m2 += X2[i];
        my += Y[i];
    }
    m1 /= n; m2 /= n; my /= n;

    // Step 2: Accumulate centered sum-of-squares and cross-products
    for (i = 0; i < n; i++) {
        float x1 = X1[i] - m1;
        float x2 = X2[i] - m2;
        float y  = Y[i] - my;
        s11 += x1 * x1;
        s22 += x2 * x2;
        s12 += x1 * x2;
        s1y += x1 * y;
        s2y += x2 * y;
    }

    // Step 3: Compute determinant denominator and weights
    den = (s11 * s22) - (s12 * s12);
    b1  = ((s1y * s22) - (s2y * s12)) / den;
    b2  = ((s2y * s11) - (s1y * s12)) / den;
    b0  = my - (b1 * m1) - (b2 * m2);

    // Step 4: Output model and evaluate new data point
    pred_y = b0 + (b1 * test_x1) + (b2 * test_x2);

    printf("=== Lab 02: Multiple Linear Regression ===\n");
    printf("b0 (Intercept) = %.2f\n", b0);
    printf("b1 (Weight X1) = %.2f\n", b1);
    printf("b2 (Weight X2) = %.2f\n", b2);
    printf("Model Equation: Y = %.2f + (%.2f * X1) + (%.2f * X2)\n", b0, b1, b2);
    printf("Prediction for (%.1f, %.1f) = %.2f\n", test_x1, test_x2, pred_y);

    return 0;
}

4. Implementation Walkthrough & Memory Triggers

• 5 Deviation Accumulators: Remember s11 ($\sum x_1^2$), s22 ($\sum x_2^2$), s12 ($\sum x_1 x_2$), s1y ($\sum x_1 y$), and s2y ($\sum x_2 y$).
• Cross Matching Rule: b1 pairs s1y with s22 minus s2y * s12. Conversely, b2 pairs s2y with s11 minus s1y * s12. Both share the exact same denominator den = s11*s22 - s12*s12.

5. Sample Execution Output

=== Lab 02: Multiple Linear Regression ===
b0 (Intercept) = 0.00
b1 (Weight X1) = 5.00
b2 (Weight X2) = -2.00
Model Equation: Y = 0.00 + (5.00 * X1) + (-2.00 * X2)
Prediction for (4.0, 3.8) = 12.40

---

Lab 03: K-Nearest Neighbors (KNN Classification)

1. Problem Statement

Implement the K-Nearest Neighbors (KNN) algorithm from scratch for binary classification. Given a query point $Q(q_1, q_2)$:

1. Calculate the Euclidean distance between $Q$ and all training vectors.
2. Sort the training instances in ascending order of proximity while maintaining label synchronicity.
3. Apply majority voting over the top $K$ nearest neighbors to classify $Q$.

2. Core Mathematical Formulation

• Euclidean Distance Metric:
  $$d(p, q) = \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2}$$

• Majority Voting Function:
  $$\hat{Y} = \begin{cases} 1 & \text{if } \sum_{i=1}^{K} y_{(i)} > \frac{K}{2} \ 0 & \text{otherwise} \end{cases}$$

3. Pure C Implementation

#include <stdio.h>
#include <math.h>

int main() {
    int n = 6, k = 3, i, j;
    // 2D training coordinates and binary classes (0 or 1)
    float x1[] = {1.0, 1.5, 2.0, 5.0, 5.5, 6.0};
    float x2[] = {1.0, 2.0, 1.5, 5.0, 6.0, 5.5};
    int label[] = {0, 0, 0, 1, 1, 1};

    float d[6];
    float q1 = 2.0, q2 = 2.5; // Test query point
    int votes = 0;

    // Step 1: Compute Euclidean distance to all training instances
    for (i = 0; i < n; i++) {
        d[i] = sqrt(((x1[i] - q1) * (x1[i] - q1)) + ((x2[i] - q2) * (x2[i] - q2)));
    }

    // Step 2: Sort distances in ascending order while keeping labels synchronized
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (d[j] > d[j + 1]) {
                float temp_d = d[j];
                d[j] = d[j + 1];
                d[j + 1] = temp_d;

                int temp_l = label[j];
                label[j] = label[j + 1];
                label[j + 1] = temp_l;
            }
        }
    }

    // Step 3: Tabulate votes across the top K neighbors
    for (i = 0; i < k; i++) {
        votes += label[i];
    }
    int pred_class = (votes > (k / 2)) ? 1 : 0;

    printf("=== Lab 03: K-Nearest Neighbors (KNN) ===\n");
    printf("Query Point: (%.1f, %.1f), K = %d\n", q1, q2, k);
    printf("Top %d Nearest Distances: %.2f, %.2f, %.2f\n", k, d[0], d[1], d[2]);
    printf("Top %d Neighbor Labels: %d, %d, %d\n", k, label[0], label[1], label[2]);
    printf("Predicted Class Label: %d\n", pred_class);

    return 0;
}

4. Implementation Walkthrough & Memory Triggers

• Parallel Swap in Bubble Sort: Never swap d[j] alone. Swapping distances without simultaneously swapping label[j] destroys class mapping.
• Odd $K$ Advantage: Choosing an odd value for $K$ ($K=3, 5$) avoids ties in two-class binary classification.

5. Sample Execution Output

=== Lab 03: K-Nearest Neighbors (KNN) ===
Query Point: (2.0, 2.5), K = 3
Top 3 Nearest Distances: 0.71, 0.71, 1.12
Top 3 Neighbor Labels: 0, 0, 0
Predicted Class Label: 0

---

Lab 04: Naïve Bayes Classifier (Laplace Smoothing)

1. Problem Statement

Implement a Naïve Bayes classifier with additive Laplace smoothing for discrete binary text features (e.g., spam email detection). Evaluate prior and likelihood probabilities to calculate class posterior scores for an incoming message.

2. Core Mathematical Formulation

• Bayes' Theorem with Independence Assumption:
  $$P(C \mid X) \propto P(C) \prod_{j=1}^{d} P(X_j \mid C)$$

• Laplace Smoothing Operator ($k = 2$ for binary attributes):
  $$P(X_j = v \mid C) = \frac{\text{count}(X_j = v \text{ and } C) + 1}{N_C + 2}$$
  where $N_C$ is total occurrences of class $C$.

3. Pure C Implementation

#include <stdio.h>

int main() {
    int n = 10, i;
    // Feature 1: Keyword "Free" present (1) or absent (0)
    int feat_free[]  = {0, 1, 1, 1, 1, 0, 0, 0, 0, 0};
    // Feature 2: Keyword "Offer" present (1) or absent (0)
    int feat_offer[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0};
    // Ground Truth Target: Spam = 1, Ham/Not-Spam = 0
    int target[]     = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0};

    // Test sample: Contains "Offer" (1), but no "Free" (0)
    int test_free = 0, test_offer = 1;

    int n_spam = 0, n_ham = 0;
    int c_free_spam = 0, c_offer_spam = 0;
    int c_free_ham = 0, c_offer_ham = 0;

    // Step 1: Accumulate class totals and matching feature frequencies
    for (i = 0; i < n; i++) {
        if (target[i] == 1) {
            n_spam++;
            if (feat_free[i] == test_free)   c_free_spam++;
            if (feat_offer[i] == test_offer) c_offer_spam++;
        } else {
            n_ham++;
            if (feat_free[i] == test_free)   c_free_ham++;
            if (feat_offer[i] == test_offer) c_offer_ham++;
        }
    }

    // Step 2: Calculate Class Prior Probabilities
    float p_spam = (float)n_spam / n;
    float p_ham  = (float)n_ham / n;

    // Step 3: Compute Laplace-smoothed conditional likelihoods: (count + 1) / (N + 2)
    float l_free_spam  = (float)(c_free_spam + 1) / (n_spam + 2);
    float l_offer_spam = (float)(c_offer_spam + 1) / (n_spam + 2);
    float l_free_ham   = (float)(c_free_ham + 1) / (n_ham + 2);
    float l_offer_ham  = (float)(c_offer_ham + 1) / (n_ham + 2);

    // Step 4: Multiply Prior * Likelihoods to obtain posterior scores
    float post_spam = p_spam * l_free_spam * l_offer_spam;
    float post_ham  = p_ham  * l_free_ham  * l_offer_ham;

    printf("=== Lab 04: Naive Bayes with Laplace Smoothing ===\n");
    printf("Priors: P(Spam) = %.2f, P(Ham) = %.2f\n", p_spam, p_ham);
    printf("Unnormalized Posterior Spam = %.4f\n", post_spam);
    printf("Unnormalized Posterior Ham  = %.4f\n", post_ham);
    printf("Classification Result       = %s\n", (post_spam > post_ham) ? "SPAM" : "HAM");

    return 0;
}

4. Implementation Walkthrough & Memory Triggers

• The Zero-Probability Solution: In standard probability, if $P(\text{Offer}=\text{Yes} \mid \text{Ham}) = 0$, the entire posterior collapses to zero. Laplace smoothing fixes this by adding $1$ to numerator and $k=2$ to denominator ((count + 1.0) / (N + 2)).
• Float Casting: Always write (float)(count + 1) / (N + 2) to avoid integer division returning zero.

5. Sample Execution Output

=== Lab 04: Naive Bayes with Laplace Smoothing ===
Priors: P(Spam) = 0.50, P(Ham) = 0.50
Unnormalized Posterior Spam = 0.1020
Unnormalized Posterior Ham  = 0.0612
Classification Result       = SPAM

---

Lab 05: Logistic Regression (Sigmoid & Gradient Descent)

1. Problem Statement

Implement binary Logistic Regression using gradient descent. Train a linear combination model $z = b_0 + b_1x$ passed through a continuous Sigmoid activation function $P = \frac{1}{1 + e^{-z}}$ to predict classification probabilities.

2. Core Mathematical Formulation

• Sigmoid Hypothesis:
  $$P(Y = 1 \mid x) = \sigma(z) = \frac{1}{1 + e^{-(b_0 + b_1x)}}$$

• Batch Gradient Descent Weight Update:
  $$b_0 \leftarrow b_0 - \alpha \frac{1}{m}\sum_{i=1}^{m}(P^{(i)} - y^{(i)})$$
  $$b_1 \leftarrow b_1 - \alpha \frac{1}{m}\sum_{i=1}^{m}(P^{(i)} - y^{(i)})x^{(i)}$$
  where $\alpha$ is the learning rate and $m$ is the sample count.

3. Pure C Implementation

#include <stdio.h>
#include <math.h>

int main() {
    int m = 6, epoch, i;
    // Data: Study Hours (x) vs Exam Result Pass=1 / Fail=0 (y)
    float x[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0};
    float y[] = {0.0, 0.0, 0.0, 1.0, 1.0, 1.0};

    float b0 = 0.0, b1 = 0.0;
    float alpha = 0.1; // Learning rate
    int epochs = 500;
    float test_x = 5.0, z_test, p_test;

    // Step 1: Batch Gradient Descent Optimization Loop
    for (epoch = 0; epoch < epochs; epoch++) {
        float grad_b0 = 0.0;
        float grad_b1 = 0.0;

        for (i = 0; i < m; i++) {
            float z = b0 + (b1 * x[i]);
            float p = 1.0 / (1.0 + exp(-z)); // Sigmoid activation
            float err = p - y[i];

            grad_b0 += err;
            grad_b1 += err * x[i];
        }

        // Apply parameter updates
        b0 -= alpha * (grad_b0 / m);
        b1 -= alpha * (grad_b1 / m);
    }

    // Step 2: Make prediction for new observation
    z_test = b0 + (b1 * test_x);
    p_test = 1.0 / (1.0 + exp(-z_test));
    int pred_class = (p_test >= 0.5) ? 1 : 0;

    printf("=== Lab 05: Logistic Regression ===\n");
    printf("Trained Weights: b0 = %.3f, b1 = %.3f\n", b0, b1);
    printf("Test Input x = %.1f -> Logit z = %.2f\n", test_x, z_test);
    printf("Predicted Probability P(Y=1) = %.4f\n", p_test);
    printf("Predicted Decision Class      = %d (%s)\n", pred_class, pred_class ? "PASS" : "FAIL");

    return 0;
}

4. Implementation Walkthrough & Memory Triggers

• Gradient Symmetry: Notice the gradient formula matches linear regression MSE gradient, but the prediction $P$ is squashed through 1.0 / (1.0 + exp(-z)).
• Standard Threshold: Probabilities $\ge 0.5$ map to Class 1, while $< 0.5$ map to Class 0.

5. Sample Execution Output

=== Lab 05: Logistic Regression ===
Trained Weights: b0 = -3.894, b1 = 1.113
Test Input x = 5.0 -> Logit z = 1.67
Predicted Probability P(Y=1) = 0.8416
Predicted Decision Class      = 1 (PASS)

---

Lab 06: Model Validation via Leave-One-Out Cross-Validation (LOOCV)

1. Problem Statement

Implement Leave-One-Out Cross-Validation (LOOCV) for a regression model in C. Partition a dataset of $n$ instances into $n$ separate folds. In each iteration, train on $n - 1$ samples, evaluate on the single held-out instance, and compute the final generalization Mean Squared Error ($\text{MSE}_{\text{LOO}}$).

2. Core Mathematical Formulation

• Exhaustive Partitioning:
  $$\text{Fold } k: \quad \mathcal{D}{\text{train}} = { (x_i, y_i) \mid i \neq k }, \quad \mathcal{D}{\text{test}} = { (x_k, y_k) }$$

• Cross-Validation Mean Squared Error:
  $$\text{MSE}{\text{LOO}} = \frac{1}{n} \sum{k=1}^{n} (y_k - \hat{y}_{(k)})^2$$

3. Pure C Implementation

#include <stdio.h>

int main() {
    int n = 4, test_idx, i;
    float x[] = {1.0, 2.0, 3.0, 4.0};
    float y[] = {2.0, 3.0, 5.0, 6.0};
    float total_sq_err = 0.0;

    printf("=== Lab 06: Leave-One-Out Cross-Validation (LOOCV) ===\n");

    // Outer Loop: Hold out each sample once
    for (test_idx = 0; test_idx < n; test_idx++) {
        float sum_x = 0.0, sum_y = 0.0;
        float mx, my, num = 0.0, den = 0.0;
        float b0, b1, pred_y, err;
        int train_size = n - 1;

        // Step 1: Compute means over the (n - 1) training instances
        for (i = 0; i < n; i++) {
            if (i == test_idx) continue; // Skip held-out test instance
            sum_x += x[i];
            sum_y += y[i];
        }
        mx = sum_x / train_size;
        my = sum_y / train_size;

        // Step 2: Fit model on the training fold
        for (i = 0; i < n; i++) {
            if (i == test_idx) continue;
            num += (x[i] - mx) * (y[i] - my);
            den += (x[i] - mx) * (x[i] - mx);
        }
        b1 = num / den;
        b0 = my - (b1 * mx);

        // Step 3: Evaluate on held-out sample
        pred_y = b0 + (b1 * x[test_idx]);
        err = y[test_idx] - pred_y;
        total_sq_err += err * err;

        printf("Fold %d: Left out (%.1f, %.1f) -> Pred: %.2f, Sq Error: %.4f\n", 
               test_idx + 1, x[test_idx], y[test_idx], pred_y, err * err);
    }

    // Step 4: Average squared loss across all folds
    float loo_mse = total_sq_err / n;
    printf("Final LOOCV Mean Squared Error (MSE) = %.4f\n", loo_mse);

    return 0;
}

4. Implementation Walkthrough & Memory Triggers

• The continue Statement: Using if (i == test_idx) continue; eliminates the need to allocate separate temporary arrays for every cross-validation fold.
• Division Factors: Train means divide by train_size = n - 1. The final overall cross-validation error divides by the total sample size n.

5. Sample Execution Output

=== Lab 06: Leave-One-Out Cross-Validation (LOOCV) ===
Fold 1: Left out (1.0, 2.0) -> Pred: 1.83, Sq Error: 0.0278
Fold 2: Left out (2.0, 3.0) -> Pred: 3.50, Sq Error: 0.2500
Fold 3: Left out (3.0, 5.0) -> Pred: 4.50, Sq Error: 0.2500
Fold 4: Left out (4.0, 6.0) -> Pred: 6.67, Sq Error: 0.4444
Final LOOCV Mean Squared Error (MSE) = 0.2431

---

Conclusion & Next Steps

This concludes Module I: Basic Supervised Learning & Validation written in pure C. You can compile any of these programs directly using GCC or Clang:

gcc -O2 lab_01.c -o lab_01
gcc -O2 lab_03.c -lm -o lab_03   # Note: link math library (-lm) for KNN / Logistic
./lab_01

Comments

[Alex Shev]

Building the foundations in C is valuable because it forces every hidden convenience into the open: layout, numerical stability, ownership, and the boundary between a correct formula and a robust implementation. A nice companion to the derivations would be property-style tests against a known reference implementation, especially around edge cases and gradient checks.

[Pavan Kumar Sadashiv]

Thanks, Alex! I completely agree. Writing it in C really forces you to understand the underlying mechanics that higher-level languages abstract away. Property-style tests against a reference implementation are a fantastic idea, especially for catching those tricky edge cases in the gradients. I'll definitely look into adding that as a next step!