III. Metric Spaces #

Problem 1 #

As it was suggested in class, our course will focus on metrics and metric spaces. However, there are useful ways of measuring distances that do not satisfy all the properties of a metric. This exercise will introduce you to one used frequently in machine learning. We begin with a short reading about a basic problem in machine learning.

Classification problems. Classification is a central problem in machine learning. Its goal is to assign a class to an object. For example, if the object is the image of a handwritten digit, we would like to know which of the digits 0 through 9 it represents. An email classifier seeks to determine whether a given email is spam or not. And text sentiment analysis seeks to identify the sentiment of a text sample. Even large language models are classification algorithms under-the-hood.

If we focus on the example of hand-written digits, there are ten classes, one for each digit. A common way for an algorithm to assign a class is to compute a vector \((p_1, p_2, \ldots, p_{10})\) where \(p_i\) represents the probability that our machine-learning model assigns for each of the ten classes. The predicted class is just the class corresponding to the largest value of \(p_i\). For instance, given the input image of a handwritten digit, the output of a pretty good algorithm might be a vector with values

p = (0.001, 0.001, 0.002, 0.230, 0.001, 0.001, 0.001, 0.760, 0.001, 0.002)

indicating the writer was most likely trying to write the digit \(7\), perhaps the digit \(3\), and that other digits are really unlikely. Of course, the writer knew what they were trying to do, so in addition to the prediction vector above, we have the ground truth vector

q = (0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 1.00, 0.000, 0.000)

which indicates the above image was their attempt at writing the digit 7.

Let us make this a little more formal.

Definition. A vector \((p_1, p_2, \dots, p_n)\) of non-negative real numbers is a probability vector if and only if \(\sum_{i=1}^n p_i = 1\). It is a positive probability vector when all \(p_i > 0\).

Probability vectors arise in classification problems. Each coordinate of a probability vector corresponds to one of \(n\) classes. The goal of a classification algorithm is, when given an input, to compute a probability vector where \(p_i\) is the probability that the input belongs to the \(i^{th}\) class. So suppose that we have a machine learning algorithm. How do we know that it is any good? One way is to compare its prediction and ground-truth vectors

$$\vec{p}=(p_1, p_2, \ldots, p_n) \qquad \text{ and } \qquad \vec{q}=(q_1, q_2, \ldots, q_n).$$

If the prediction vector is close to the ground-truth vector for a variety of inputs, then our model is doing ok. But when are two vectors close? In classification problems, the two vectors are compared in an interesting way. Suppose that \(\vec{p}\) and \(\vec{q}\) are positive probability vectors.

Definition. The Kullback–Leibler distance between two positive probability vectors is defined by the following formula:

$$\rho(\vec{p}, \vec{q}) = \sum_{i=1}^n p_i \log\left(\tfrac{p_i}{q_i}\right).$$

Complete the following exercises:

Solutions: Hint · Solution · Long solution

Problem 2 #

Consider vectors \(\vec{v}\) and \(\vec{w}\) in \(\mathbb{R}^n\). We can define a function \(\rho_1: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}\) by letting

$$\rho_1(\vec{v},\vec{w}) = \sum_{i=1}^n |v_i - w_i|.$$

In \(\mathbb{R}^2\) this is called the “taxicab metric.” Prove that when endowed with this metric, \(\mathbb{R}^2\) becomes a metric space.

Solutions: Hint · Solution · Long solution

Problem 3 #

Recall the definitions of the metrics \(\rho_2, \rho_1,\) and \(\rho_\infty\) on the set \(\mathbb{R}^n\) from class. They are a part of a larger family of metrics called the \(p\)-metrics.

Definition. Let \(\vec{v} = (v_1, \ldots, v_n)\) and \(\vec{w} = (w_1, \ldots, w_n) \in \mathbb{R}^n\). For \(p \in \mathbb{N}\), we define a function

$$\rho_p (\vec{v},\vec{w}) = \sqrt[p]{|v_1-w_1|^p + \ldots + |v_n-w_n|^p}.$$

It turns out that this is always a metric. I urge you to stay away from the proof of the triangle inequality. Armed with this knowledge, try to visualize how these metrics are interrelated by the following exercise. Let \(\vec{0}\) be the origin in \(\mathbb{R}^n\). Draw the unit sphere \(S_1(\vec{0})\) in the metric spaces

$$(\mathbb{R}^2, \rho_2), \quad (\mathbb{R}^2, \rho_1), \quad (\mathbb{R}^2, \rho_\infty), \quad (\mathbb{R}^3, \rho_1), \quad \text{and} \quad (\mathbb{R}^2, \rho_3).$$

Solutions: Hint · Solution · Long solution

Problem 4 #

Show that it is possible to find a metric space \((S, \rho)\), points \(x,y \in S\), and positive numbers \(r_1\) and \(r_2\) so that

$$B_{r_1}(x) \subseteq B_{r_2}(y),$$

and \(r_1 > r_2\); that is, a ball with a smaller radius contains a ball with a larger radius (!).

Solutions: Hint · Solution · Long solution

Problem 5 #

Consider a metric space \(S\) with metric \(\rho\). If \(A\) and \(B\) are subsets of \(S\), we can define the distance between them to be

$$\rho(A,B) = \inf_{a \in A,\, b \in B} \rho(a,b);$$

that is, the infimum of the set of all possible distances between a point in \(A\) and a point in \(B\). Show that \(\rho(A,B)=0\) if \(A \cap B \neq \varnothing\) and, by providing a counterexample, show that the converse need not hold.

Solutions: Hint · Solution · Long solution

Problem 6 #

Prove the following proposition. We will use it a number of times in the course to show that two points of a metric space are equal.

Proposition. Consider points \(p\) and \(p'\) in a metric space \((S, \rho)\). If \(\rho(p,p') < \epsilon\) for every \(\epsilon > 0\), then \(p = p'\).

Solutions: Hint · Solution · Long solution