The Nearest Neighbor Descent method as usually described is technically a way to optimize an existing estimate of the nearest neighbor graph. You must think of a way to initialize the graph. The obvious approach and the one used in the description of NND in (Dong, Moses, and Li 2011) is to start with a random selection of neighbors. One of the clever things about the PyNNDescent implementation is that it uses a random partition forest (Dasgupta and Freund 2008) to come up with the initial guess. Random partition forests are part of a large group of tree-based methods. These are often very fast and conceptually simple, but can be inaccurate. Much of the literature is devoted to proposals of tweaks to these methods to improve their performance, often at the expense of their simplicity and speed. PyNNDescent (and rnndescent follows its lead) avoids this because we only need to get to a decent guess of the nearest neighbor graph which we can then improve by nearest neighbor descent. As long as we don’t take substantially longer than the random initialization to come up with the guess and it’s sufficiently good, we should come out ahead.
Here’s a basic introduction to how random partition forests work.
First, we will consider the recipe for building a space-partitioning tree:
Variations of steps 1 and 2 determines the vast majority of the differences between the various tree-based methods.
For a random partition tree we:
This is enough to define a hyperplane in the data. This is not exactly the algorithm as described in (Dasgupta and Freund 2008), but it is how it’s done in the very similar method Annoy.
Step 3 then involves calculating which side of the hyperplane each point is on and assigning data to the child nodes on that basis.
A random partition forest is just a collection of random partition trees. Because of the random nature of the trees, they will all be different.
To build a forest with rnndescent, use the
rpf_build function. We’ll use the iris dataset
as an example, with the goal of finding the 15-nearest neighbors of each
item in the dataset.
Some options at your disposal:
metric: the type of distance calculation to use. The
default is euclidean, but there are a lot to choose from.
See the help text for the metric parameter in rpf_build()`
for details.n_trees: the number of trees to build. The default is
to choose based on the size of the data provided, with a maximum of 32:
eventually you will get diminishing returns from the number of trees in
a forest.leaf_size: the number of items in a leaf. The splitting
procedure stops when there are fewer than this number of items in a
node. The default is 10 but you will want the leaf size to
scale with the number of neighbors you will look for, so I have
increased it to 15 for this example. The bigger this value
the more accurate the search will be, but at the cost of a lot more
distance calculations to carry out. Conversely, if you make it too small
compared to the number of neighbors, then you may end up with not all
items finding k neighbors.max_tree_depth: the maximum depth of the tree. If a
tree reaches this depth then even if the current node size exceeds the
value of leaf_size, it will stop splitting. The point of
splitting a tree is that the size of each leaf should rapidly
decrease as you go down the tree, and in an ideal case it would decrease
by a factor of two at each level, so ideally we can process datasets
that vary by many orders of magnitude while the depth of the tree only
increases by a few levels. The default max_tree_depth is
200, so if you trigger this limit, the answer may not be to
increase the depth. It’s more likely that there is something about the
distribution of your data that prevents it from splitting well. In this
case, if there’s a different metric to try that still has
relevance for your data, that’s worth a try, but possibly the best
solution is to abandon the tree-based approach (for example initialize
nearest neighbor descent with random neighbors). If you set
verbose = TRUE you will get a warning about the maximum
leaf size being larger than leaf_size.margin: this makes a slight modification to how the
assignment of data to the sides of the hyperplane is calculated. We’ll
discuss this below.The forest that is returned is just an R list, so you can save it and
load it with saveRDS and readRDS without
issue. But it’s not something you will want to inspect and definitely
don’t modify it. It’s mainly useful for passing to other functions, like
the one we will talk about next.
To use this to find nearest neighbors, a query point will traverse the tree from the root to a leaf, calculating the side of each hyperplane it encounters. All the items in the leaf in which it ends up are then candidates for nearest neighbors.
To query the forest we just build, we use the
rpf_knn_query function. Apart from the forest itself, we
also need the data we want to query (query) and the data
used to build the forest (reference), because the forest
doesn’t store that information. In thus case, because we are looking at
the k-nearest neighbors or iris, the query and
the reference are the same, but they don’t have to be. At
this point, we must also specify the number of neighbors we want.
The iris_query that is returned is a list with two
matrices: idx contains for each row the indices of the
k-nearest neighbors, and dist contains the distances.
You could use the querying approach mentioned above for finding the k-nearest neighbors of the data that was used in building the tree. However, the data has already been partitioned so if you want k-nearest neighbor data, there’s a more efficient way to do that: for each leaf, the k-nearest neighbors of each point in the leaf are the other members of that leaf. While usually the distance calculations take up most of the time when looking for neighbors, you do avoid having to make any tree traversals and the associated hyperplane distance calculations.
This should give the same result as running rpf_build
followed by rpf_knn_query (apart from the vagaries of the
random number generator), but is a lot more convenient and a bit faster.
You have access to the same parameters for forest building as
rpf_build, e.g. leaf_size,
n_trees, max_tree_depth etc.
Additionally, if you want the k-nearest neighbors and you
also want the forest for future querying, if you set
ret_forest = TRUE, the return value will now also contain
the forest as the forest item in the list. In this example
we build the forest (and get the 15-nearest neighbors) for the first 50
iris items and then query the remaining 100:
The margin parameter determines how to calculate the
side of the hyperplane each item in a split belongs to. The usual method
(margin = "explicit") does the same thing as in
PyNNDescent: the way the hyperplane is defined is to use the vector
defined by the two points a
and b as the normal vector to
a plane, and then the point midway between them as the point on the
plane. We then calculate the margin of a point x (effectively the signed distance
from the plane to x) as:
$$ \text{margin}(\mathbf{x}) = ((\mathbf{b} - \mathbf{a}) \cdot (\mathbf{x} - \frac{\mathbf{a} + \mathbf{b}}{2})) $$
Taking dot products of vectors and finding mid points is all totally unexceptional if you are using a Euclidean metric. And because there is a monotonic relationship between the cosine distances and the Euclidean distance after normalization of vectors, we can define an “angular” version of this calculation that works on the normalized vectors.
But for some datasets this will be a bit weird and un-natural. Imagine a dataset of binary vectors in which you are applying e.g. the Hamming metric. The mid-point of two binary vectors is not a binary vector, and nor does it make sense to think about the geometric relationship implied by a dot product.
As an alternative to calculating the margin via an explicit creation of a hyperplane, you could instead think about how the distance between x and a, dxa compares to the distance between x and b, dxb and what the significance for the margin is. Remember that the vector defined by a and b is the normal vector to the hyperplane, so you can think of a line connecting a and b, with the hyperplane splitting that line in two equal halves. Now imagine x is somewhere on that line. If x is closer to a than b it must be on the same side of the hyperplane as a, and vice versa. Therefore we can calculate the margin by comparing dxa and dxb and seeing which value is smaller.
Because we don’t explicitly create the hyperplane, I call this the
“implicit” margin method and you can choose to generate splits this way
by setting margin = "implicit". We’ll use some random
binary data for this example.
Note the as.logical call: if rnndescent
detects binary data in this format and you specify a metric
which is appropriate for binary data (e.g. Hamming), and you
use margin = "implicit" then a specialized function is
called which should be much faster than the functions written only with
generic floating point data in mind.
The following will give the same results but for large datasets is likely to be noticeably slower:
So if the implicit margin method is faster (and makes sense for more
metrics) why would you ever want to use the explicit method? Well, the
implicit method is only faster for binary data with specialized metrics.
The downside of the implicit method is that determining the side of the
hyperplane requires two distance calculations per point,
whereas the explicit method only requires the dot product calculation,
which is likely to be only as costly as a single distance calculation.
So for floating point data, the explicit method is likely to be about
twice as fast. That’s a lot to think about so the default setting for
margin is "auto", which tries to do the right
thing: if you are using binary data with a suitable metric, it will use
the implicit method, otherwise it will use the explicit method and
normalize the vectors to give a more “angular” approach for some metrics
that put more emphasis on angle versus magnitude.
As mentioned at the beginning of this vignette, in
rnndescent it’s expected that you would only use random
partition forests as an initialization to nearest neighbor descent. In
that case, keeping the entire forest for querying new data is probably
unnecessary: we can keep only the “best” trees. PyNNDescent only keeps
one tree for this purpose. For determining what tree is “best”, we mean
the tree that reproduces the k-nearest neighbor graph most effectively.
You can do this by comparing an existing k-nearest neighbor graph with
that produced by a single tree. The rpf_filter function
does this for you:
n_trees is the number of trees to keep. Feel free to
keep more if you like, although there is no extra diversification step
to ensure that the trees being retained are both good at reproducing the
k-nearest neighbor graph and are diverse from each other
(perhaps they reproduce different parts of the neighbor graph well?).
The higher quality the k-nearest-neighbor graph is, the better the
filtering will work so although the example above uses the graph from
the forest, you might get better results using the graph from having run
nearest neighbor descent with the forest result as input.