Hypothesis space of Naive Bayes and kNN I am confused about the hypothesis space of those two classifiers.
In the case of linear regression, it's pretty straightforward ; the possible hypothesis are equations of lines, that is, linear combinations of the features. Therefore, the hypothesis space is the space of all possible coefficient values.
But for kNN and NB, I don't clearly see what is the space of parameters you can act upon, and therefore I cannot define any hypothesis space. In the case of NB, I have seen it can correspond to a linear separator as well, therefore the hypothesis space would also be all the linear combinations of odds ratios? But in the case of kNN, it is totally unclear to me.
 A: In KNN, your hypothesis space depends on the density according to your $k$ neighbors (in a 2 dimensional feature vector picture a circle encircling all your $K$ neighbors). Then the density is $P(x) = \frac{k}{NV}$, where $k$ is the number of observations inside the volume $V$, and $N$ is the total number of observations.
A: You can think of hypothesis space of linear regression as the set of linear functions of your features. For simplicity assume the feature space is the entire $\mathbb R^d$. Then, the hypothesis space of linear regression is
$$
\mathcal F = \{f: \mathbb R^d \to \mathbb R :\; f(x) = \beta^T x, \quad \forall x \in \mathbb R^d,\; \text{and some $\beta \in \mathbb R^d$}\}.
$$
This class is a parametric family and can be equivalently described by the set of coefficients $\{ \beta:\; \beta \in \mathbb R^d\}$.
The k-NN regression is a nonparametric approach. The hypothesis space is  the class of all functions that are piecewise constant on the cells of the $k$th order Voronoi diagram of some set of $n$ points in $\mathbb R^d$.
To be more precise, for a collection of points $\{x_i\}_{i=1}^n \subset \mathbb R^d$, let $V_j^k(\{x_i\}_{i=1}^n)$ be the $j$th Voronoi cell in the $k$th order Voronoi partition of the space by points $\{x_i\}_{i=1}^n$ (let us say we order these cells in some way in order to index them). This means that all the points in each of these cells have the same $k$-nearest neighbors among $\{x_i\}_{i=1}^n$. Then, the class of functions underlying $k$-NN can be written as
\begin{align}
\mathcal F_{\text{$k$-NN}}^{(n)} = \Big\{f: \mathbb R^d \to \mathbb R:&\; \text{There exists $\{x_i\}_{i=1}^n \subset \mathbb R^d$ and $\{a_j\} \subset \mathbb R$ such that} \\ &f(x) = \sum_j a_j \cdot 1_{V_j^k(\{x_i\}_{i=1}^n)}(x), \quad \forall x \in \mathbb R^d. \Big\}.
\end{align}
Here, $1_{A}(x) = 1\{x \in A\}$ is the indicator function of set $A$. As you can see, this is a rather large class of functions. There are many ways to pick $n$ points in $\mathbb R^d$ and each one defines a potentially different Voronoi partition. If you consider all such partitions and all functions that are constant over cells of those partitions, you would get the $k$-NN class.
You can also take the union of $F_{\text{$k$-NN}}^{(n)}$ over all $n \in \{1,2,\dots\}$ to define all possible $k$-NN functions.
