IFT 3395 – Fundamentals of Machine Learning · Assignment 1

Coursework for IFT 3395 (Université de Montréal, 2021). The assignment has a practical part (Parzen-window classifiers on Iris, implemented from scratch in NumPy) and a theoretical part (probability, Naive-Bayes-style reasoning, maximum likelihood, k-NN, histograms).

The original handouts are in French; AI-translated English versions (instructions_en.pdf) are included next to each original.

---

What this assignment covers

Practical – non-parametric classification with Parzen windows

• Descriptive statistics: feature means and empirical covariance matrices, overall and per class.
• Parzen-window classification with two kernels, both written with vectorised NumPy:
  • Hard window: K(X_i, x) = \mathbb{1}\{d(X_i, x) < h\} — a majority vote among neighbours within radius h (random label if the window is empty).
  • Soft RBF (Gaussian) window: K(X_i, x) = \frac{1}{(2\pi)^{D/2}\sigma^D}\exp\!\big(-\tfrac12 d(X_i,x)^2/\sigma^2\big) — a kernel-weighted vote over all training points.
• Model selection: deterministic train/validation/test split (index mod 5), hyper-parameter search over h and \sigma on the validation set, final error on the test set.
• Under- / over-smoothing: how bandwidth controls the bias–variance trade-off.
• Computational complexity of both methods and how it depends on h / \sigma.
• (Bonus) Gaussian random projections (4D → 2D) and the effect of dimensionality reduction on accuracy, averaged over 500 random draws.

Theory

• Probability foundations: conditional probability, Bayes' theorem (with proof), applied word problems.
• Bag-of-words / single-topic model: conditional independence of words given the topic, posterior over topics, and estimating the parameters from labelled documents (the Naive Bayes setup).
• Maximum likelihood estimation: MLE of a Uniform$[0,\theta]$ distribution (\hat\theta = \max_i x_i).
• k-nearest neighbours vs nearest class mean: hand-drawn decision boundaries for 2 and 3 classes.
• Histogram density estimation: consistency via the law of large numbers, and the curse of dimensionality (number of bins grows as m^d, MNIST example).

---

Main results

Validation error vs. window parameter (Practical Q5)

We notice that for values of σ and h between 0 and 1, the error rate is fairly low. We potentially have too much bias with our Hard-Parzen and Soft-Parzen models, perhaps the low capacity of these models prevents us from lowering the error rate.

As for the considerable increase in the error rate, from 2 or 3, it is probably an overfitting problem given that the larger the parameters, the more points we consider (with more importance in the case of Soft-Parzen), until taking an “average” of all the training points.

The high error rate of Hard-Parzen for very small values of h could be explained by the random selection of the chosen label. Indeed, since h is small, almost no training point is considered a neighbor, thus the label decision no longer rests on the neighbors’ labels, but rather on the random label that is assigned by default.

Random projections (Practical Q9, bonus)

Projecting the data onto a reduced dimension decreases the capacity of our model. The error rates are, on average, better than those obtained in full dimension. However, we do not manage to go as low as before. In the graph of question 5, we were able to go very low when the parameters had a low value, this performance is perhaps spoiled by the noise which wins out over the data.

k-NN vs nearest-mean decision boundaries (Theory Q4)

To draw the boundaries of the following questions, I used the following strategy:

1. Draw the medians between a point and the other points (only those of other classes)
2. Take the intersection of the constraints to obtain the smallest polygon (possibly unbounded) that surrounds the point
3. Repeat for each point of the same class
4. Take the union of each polygon to obtain the decision region for the class of the points contained
5. Repeat for each class of point

Complexity (Practical Q7), in short

The 2 methods are in the same time-complexity class, the only change is the kernel function used by each. For Hard-Parzen the only real computation is the Euclidean distance between two vectors. This is fairly comparable to the computation in Soft-Parzen, which contains a power and an exponential.

As for the parameters σ and h, they have no effect on computation time. No matter whether they are small or large, the algorithm must still compare each test point to each point of the training set. One might think that the selection of the maximum is affected, since more points (per label) will be considered if the parameters σ and h are larger, but to find the maximum we must always compare each count obtained per label, no matter how many.

What does have an effect, however, is the number of parameters we test. It is quite obvious that for each additional parameter, model selection will last one more iteration.

We can therefore find the complexity class by examining the general behavior of the algorithm, whichever of Hard-Parzen or Soft-Parzen. For each phase (validation and test only), we begin by running the kernel with each point of the validation set (|D_validation| ≈ n/5) and each point of the training set (|D_train| ≈ 3n/5). For each of the validation points, we must also find the winning label, so m (number of classes) comparisons. This gives us

O(n^2 + nm)

If we consider the number of parameters (p) to try in the model selection, we have

O(pn (n + m))

We also repeat the entire process a constant number of times (for the different phases), but that does not change the complexity class.

---

Repository structure

.
├── README.md
├── practice/               # Practical part (Python / NumPy / Matplotlib)
│   ├── instructions.pdf    # original handout (French)
│   ├── instructions_en.pdf # AI-translated handout (English)
│   ├── solution.py         # graded code
│   └── report/             # written report (LaTeX): Q5 plot + discussion, Q7, Q9
│
└── theory/                 # Theoretical part
    ├── instructions.pdf    # original handout (French)
    ├── instructions_en.pdf # AI-translated handout (English)
    └── report/             # written solutions (LaTeX): Q1–Q5

Running the code

pip install numpy matplotlib
python practice/graph.py