0
$\begingroup$

I came across some specific algorithm that divides high-dimensional vector space into non-overlapping cells of convex polyhedron.

It does this by using tree based binary partitions (which might not be precisely relevant to this site), but in order to divide vector space into cells of convex polyhedrons, random tests are utilized at each node of the tree, until it reaches a leaf node.

What's intersting, is what happens in the random tests itself.


Random tests are based on subspace projections of high dimensional vectors (variable $d$ is dimension of vector space, variable $r$ is the split ratio of the tree):

The test is based on subspace projections of high dimensional features. Suppose the node $l_i$ contains $n_i$ data points $x_0, x_1, ... ,x_{n_i}$ where $x_j=(x_{j0}, x_{j1}, ..., x_{jd-1})$. We randomly select an index set $I_i=\{d_{i0}, d_{i1}, ... , d_{ik-1}\}$ of size $K$ ($K \leq d$) where $d_{ij} \in (0, 1, ..., d-1)$ and random coefficients $\Im{}_i=\{\xi_{i0}, \xi_{i1},...,\xi_{ik-1}\}$ where $\xi_{ij} \in [0, 1]$, and compute for every feature vector $x_j$ a scale value $y_j=\sum^{K-1}_{k=0} x_{jd_{ik}} \xi_{ik}$ for $j=0,...,n_i-1$. We then sort out the $y_j{s}$ and denote the sorted sequence as $\{\tilde{y_j}\}$. Randomly select $\psi_i$ between the $100*r$ and $100*(1-r)$ percentile of points $\{\tilde{y_j}\}$, i.e., $\{\tilde{y_j}\} \in [\tilde{y}_{n_i * r}, \tilde{y}_{n_i * (1-r)}]$.

The random test (equation 1):

$$t_i(x)=\sum^{K-1}_{k=0} x_{d_{ik}} {\xi_{ik}}-\psi_i \geq 0$$

defines a hyper-plane which splits the polyhedron at node $l_i$ into two polyhedrons each containing no less than $r*n_i$ data points.

I do not have much knowledge of geometry, but I know from my linear algebra textbook that convex sets are sets such that every point of every line segment in the set belongs in the set.

Also, as explained in this brilliant answer, convex polyhedron equals the intersection of finitely many closed half-spaces and is not contained in a plane, and in three dimensions, can be represented by $ax+by+cz \geq 0$, which is very similar to the equation 1.

What would be the simple explanation of this process? let's say hyper-plane was a line (if it could be), how would it divide convex polyhedron? Furthermore, what do subspace projections have to do with this?

Thank you very much!

$\endgroup$
1
  • 2
    $\begingroup$ "..., can be represented by $ax + by + cz - d \ge 0$", you mean; $d / \sqrt{a^2 + b^2 + c^2}$ being the signed distance from origin to the plane. If you omit $d$, all the planes intersect at origin, and the polyhedron is a single point, origin. $\endgroup$ – Nominal Animal Dec 17 '18 at 19:40
2
$\begingroup$

Note that you can calculate $y_i$ as $$\bbox{ y_i = \sum_{k=0}^{d} x_{i k} \zeta_k }$$ and $t_i(x)$ as $$\bbox{ t_i(x) = -\psi_i + \sum_{k=0}^{d} x_{i k} \zeta_k = y_i - \psi_i }$$ where $\zeta$ is a $d$-dimensional vector with $d-K$ components zero, and all other components between $0$ and $1$.

This means that the underlying idea is to project the $n_i$ data points along a random, essentially $K$-dimensional vector; sort the $n_i$ data points according to their signed distance to origin along that vector, $y_i$; and pick $\psi_i$ so that there are at least $p n_i$ points with larger, and at least $p n_i$ points with smaller signed distance to origin.

(In practice, this can be done using quickselect or some other selection algorithm; if the selection algorithm modifies (partially sorts) the data, use tuples $(i, y_i)$, so that you do not need to recompute the $y_i$ to partition the data.)

The reason for the index set and coefficients is to reduce the computational complexity, by using a subspace of $K$ dimensions, instead of the full $d$-dimensional vectors. When $d$ is very large, using a smallish $K$ (say a dozen or so) makes a huge difference: instead of $d$ multiplications and $d-1$ additions per point to compute $y_i$, only $K$ multiplications and $K-1$ additions are needed.

This works as long as the points $n_i$ are not planar with respect to vector $\zeta$. (If they are, then all $y_i$ are the same.)

Consider the following four-level 2D tree:
2D subdivision
At the top level, the vector $\zeta$ is perpendicular to the red line marked 1. At least fraction $p$ of the points are on the right side, and $p$ on the left side. $\psi$ is where that vector and the red line intersect.

At the second level, the vectors $\zeta$ are perpendicular to the reddish-brown lines marked 2; at the third level, perpendicular to the brown lines marked 3; and at the fourth level, perpendicular to the green lines marked 4. In all cases, $\psi$ is where $\zeta$ and the shown line intersect.

This four-level, 15-node tree divides the space into 16 convex polygons. In general, an $N$-level tree has $2^N - 1$ nodes, and divides the space into $2^N$ convex polygons.

The cells are convex, because when subdividing, only the points inside a cell are subdivided into two subcells. In geometric terms, the dividing line (hyperplane) does not cross existing lines (hyperplanes), and each one only splits one cell into two (unless subdivided further).

If you have a 2D point, and you compute the four $t(x)$ tests for each level in the tree to descend into a leaf node, you arrive in the cell that contains your 2D point.

In the above diagram, $K = d = 2$, but as I already said, the splitting vector $\zeta$ is still random, just chosen in a way that reduces the computational complexity when $d \gg K$.

$\endgroup$
3
  • $\begingroup$ Thank you very much for the great answer! If I may ask final question, is there any specific purpose for $ψ_i$ to be a percentile of the sorted array? My apologies if there is any misunderstanding. $\endgroup$ – ShellRox Dec 17 '18 at 21:06
  • 1
    $\begingroup$ @ShellRox: Choosing $\psi$ as a percentile of the sorted array is important to ensure the tree is balanced. If you picked $\psi$ at random, then you might create a cell with no points in it. In general, that leads to a deep, inefficient tree. By choosing $p \approx 0.5$, you ensure the tree is as shallow as possible, with roughly the same number of points in each leaf node. This makes all lookups efficient, without "bad cases" that would take longer than others. $\endgroup$ – Nominal Animal Dec 18 '18 at 17:01
  • 1
    $\begingroup$ @ShellRox: That said, I do believe that there are methods that allows one to pick a $\psi$ and verify in nearly linear time that it corresponds to some $\beta \le p \le 1 - \beta$, by e.g. using a median-of-$N$, or perhaps mean, and adjusting $\psi$ (using e.g. short-circuited binary search) whenever necessary. I mean, it is not important that $\psi$ corresponds to an exact value of $p$; it is okay to pick $\psi$ in a random or semi-random fashion, as long as it ensures that it splits the point set reasonably evenly, say at least 33% of points in either side. $\endgroup$ – Nominal Animal Dec 18 '18 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.