Feeds:
Posts

## Maximum Number of Regions in Arrangement of Hyperplanes

A semi-useful fact for people working in Machine Learning.

Blurb: Recently, my supervisor was kind enough to institute a small reading group on Deep Neural Networks to help us understand them better. A side product of this would hopefully be that I get to explore this old interest of mine (I have an old interest in Neural Nets and have always wanted to study them in detail, especially work from the mid 90s when the area matured and connections to many others areas such as statistical physics became apparent. But before I got to do that, they seem to be back in vogue! I dub this resurgence as Connectionism 2.0 Although the hipster in me dislikes hype, it is always lends a good excuse to explore an interest). I also attended a Summer School on the topic at UCLA, find slides and talks over here.

Coming back: we have been making our way through this Foundations and Trends volume by Yoshua Bengio (which I quite highly recommend). Bengio spends a lot of time giving intuitions and arguments on why and when Deep Architectures are useful. One particular argument (which is actually quite general and not specific to trees as it might appear) went like this:

Ensembles of trees (like boosted trees, and forests) are more powerful than a single tree. They add a third level to the architecture which allows the model to discriminate among a number of regions exponential in the number of parameters. As illustrated in […], they implicitly form a distributed representation […]

This is followed by an illustration with the following figure:

[Image Source: Learning Deep Architectures for AI]

and accompanying text to the above figure:

Whereas a single decision tree (here just a two-way partition) can discriminate among a number of regions linear in the number of parameters (leaves), an ensemble of trees can discriminate among a number of regions exponential in the number of trees, i.e., exponential in the total number of parameters (at least as long as the number of trees does not exceed the number of inputs, which is not quite the case here). Each distinguishable region is associated with one of the leaves of each tree (here there are three 2-way trees, each defining two regions, for a total of seven regions). This is equivalent to a multi-clustering, here three clusterings each associated with two regions.

Now, the following question was considered: Referring to the text in boldface above, is the number of regions obtained exponential in the general case? It is easy to see that there would be cases where it is not exponential. For example: the number of regions obtained by the three trees would be the same  as those obtained by one tree if all three trees overlap, hence giving no benefit. The above claim refers to a paper (also by Yoshua Bengio) where he constructs examples to show the number of regions could be exponential in some cases.

But suppose for our satisfaction we are interested in actual numbers and the following general question, an answer to which should also answer the question raised above:

What is the maximum possible number of regions that can be obtained in ${\bf R}^n$ by the intersection of $m$ hyperplanes?

Let’s consider some examples in the ${\bf R}^2$ case.

Where there is one hyperplace i.e. $m = 1$, then the maximum number of possible regions is obviously two.

[1 Hyperplane: 2 Regions]

Clearly, for two hyerplanes, the maximum number of possible regions is 4.

[2 Hyperplanes: 4 Regions]

In case there are three hyperplanes, the maximum number of regions that might be possible would be 7 as illustrated in the first figure. For $m =4$ i.e. 4 hyerplanes, this number is 11 as shown below:

[4 Hyperplanes: 11 Regions]

On inspection we can see the number of regions with $m$ hyperplanes in ${\bf R}^2$ is given by:

Number of Regions = #lines + #intersections + 1

Now let’s consider the general case: What is the expression that would give us the maximum number of regions possibles with $m$ hyperplanes in ${\bf R}^n$? Turns out that there is a definite expression for the same:

Let $\mathcal{A}$ be an arrangement of $m$ hyperplanes in ${\bf R}^n$, then the maximum number of regions possible is given by

$\displaystyle r(\mathcal{A}) = 1 + m + \dbinom{m}{2} \ldots + \dbinom{m}{n}$

the number of bounded regions (closed from all sides) is given by:

$\displaystyle b(\mathcal{A}) = \dbinom{m - 1}{n}$

The above expressions actually derive from a more general expression when $\mathcal{A}$ is specifically a real arrangement.

I am not familiar with some of the techniques that are required to prove this in the general case ($\mathcal{A}$ is a set of affine hyperplanes in a vector space defined over some Field).  The above might be proven by induction. However, it turns out that in the ${\bf R}^2$ case the result is related to the crossing lemma (see discussion over here), I think it was one of the most favourite results of one of my previous advisors and he often talked about it. This connection makes me want to study the details [1],[2], which I haven’t had the time to look at and I will post the proof for the general version in a future post.

________________

References:

1. An Introduction to Hyperplane Arrangements: Richard P. Stanley (PDF)

Related:

2. Partially Ordered Sets: William Trotter (Handbook of Combinatorics) (PDF)

________________

Onionesque Reality Home >>

While searching for some methods for face representation in connection with my recent project, I lost the way clicking on some stray links and landed up on some beautiful art work involving Voronoi diagrams. I was aware of art work based on Voronoi diagrams (it kind of follows naturally that Voronoi diagrams can lead to very elegant designs, isn’t it?) but a couple of images on them were enough to re-ignite interest. It was also interesting to see an alternate solution to my problem based on Voronoi diagrams as well. However I intend to share some of the art work I came across.

———-

Before I get to the actual art-work I suppose it would be handy to give a very basic introduction to Voronoi Diagrams with a couple of handy applications.

Introduction: Voronoi diagrams are named after Georgy Voronoy (1868-1908), an eminent Russian/Ukrainian mathematician. A number of mathematicians before Voronoy such as Descartes and Dirichlet have been known to have used them, Voronoy extended the idea to $\mathcal{N}$ dimensions. The Voronoi diagram is a tessellation, or a tiling. A tiling of a plane is simply a collection of plane figures that fills the plane with no overlaps and no gaps in between. This idea can ofcourse be extended to $\mathcal{N}$ dimensions, but for simplicity let us stick with 2 dimensions.

[A pavement Tessellation/Tiling]

Definition: A Voronoi diagram is a special kind of a decomposition of a metric space which is determined by a discrete set of points.

Generally speaking for a 2-D case:

>> Let us designate a set of $n$ distinct points that we call sites as $\mathcal{P}$. i.e $\mathcal{P}=\{P_1, P_2\ldots, P_n\}$

>> We may then define the Voronoi Diagram of P as a collection $\mathcal{V}=\{V_1,V_2,\ldots, V_n\}$ of subsets of the plane. These subsets are called as Voronoi Regions. Each point in $V_i$ is such that it is closer to $\mathcal{P}_i$ than any other point in $\mathcal{P}$.

To be more precise:

A point $Q$ lies in the Voronoi Region corresponding to a site $P_i \in \mathcal{P}$ if and only if –

$Euclidean\_Distance(Q,P_i) < Euclidean\_Distance(Q,P_j)$ for each $P_i \neq P_j$

However it might be the case that there are some points in the plane that might have more than one site that is the closest to it. These points do not lie in either Voronoi Region, but simply lie on the boundary of two adjacent regions. All such points form a skeleton of lines that is called the Voronoi Skeleton of $\mathcal{P}$.

We can say that $\mathcal{V(P)}$ is the Voronoi Transform, that transforms a set of discrete points (sites) into a Voronoi Diagram.

———-

For more clarity on the above, consider a sample Voronoi Diagram below:

The dots are called the Sites. The Voronoi Regions are simply areas around a site but enclosed by the lines around them. The network of lines is simply the Voronoi Skeleton.

———-

Some Extensions to the above Definition: The above definition which is ofcourse extremely simple can be extended very easily[1] for getting some fun art forms.

Some of these extensions could be as follows [1]:

1. Since each region corresponds to a site, each site can be associated with a color. Hence the Voronoi diagram can be colored accordingly.

2. In the definition the sites were considered to be simply points, we can obtain a variety of figures by allowing the “sites” to be subsets of the plane than just points. We see, that if the sites are defined as simply points, the Voronoi skeleton would always be composed of straight lines. With this change there could be interesting skeletal figures emerging.

3. We could also modify the distance metric from the Euclidean distance to some other to get some very interesting figures.

This just shows the kind of variety of figures that can be generated by just a small change in one aspect of the basic definition.

———-

Constructing a Voronoi Diagram:

Let us forget the extensions that we spoke of for a moment and come back to the basic definition. Looking at the definition it  seems constructing Voronoi diagrams is a simple process. And it is not difficult at all. The steps are as follows:

1. Consider a random set of points.

2. Connect ALL of these points by straight lines.

3. Draw a perpendicular bisector to EACH of these connecting lines.

4. Now select pieces that are formed, such that each site (point) is encapsulated.

Voronoi Diagrams can be very easily made by direct commands in both MATLAB and MATHEMATICA.

———-

Voronoi Diagrams in Nature: It is interesting to see how often Voronoi diagrams occur in nature. Just consider two examples:

[Left: Reticulum Plasmatique (Image Source) Right: Polygons on Giraffes]

———-

Uses of Voronoi Diagrams: There are a wide variety of applications of Voronoi diagrams. They are more important then what one might come to believe. Some of the applications are as follows:

1. Nearest Neighbour Search: This is the most obvious application of Voronoi Diagrams.

2. Facility Location: The example that is often quoted in this case is the example of choosing where to place a new Antenna in case of cellular mobile systems and similarly deciding the location of a new McDonalds given a number of them already exist in the city.

3. Path Planning: Suppose one models the sites as obstacles, then they can be used to determine the best path (a path that stays at a maximum distance from all obstacles or sites).

There are a number of other applications, such as in Geophysics, Metrology, Computer Graphics, Epidemiology and even pattern recognition. A very good example that illustrates how they can be used was the analysis of the Cholera epidemic in London in 1854, in which physician John Snow determined a very strong correlation of deaths with proximity to a particular infected pump (specific example from Wolfram Mathworld).

Let’s consider the specific example of path planning [2]. Consider a robot placed in one corner of a room with stuff dispersed around.

Now the best path from the point where the robot is located to the goal would be the one in which the robot is farthest from the nearest obstacle at any point in time. To find such a path, the Voronoi diagram of the room would be required to be found out. Once it is done, the vertices or the skeleton of the Voronoi Diagram provides the best path. Which path ultimately is to be taken can be found out by comparing the various options (alternative paths) by using search algorithms.

Now finally after the background on Voronoi Diagrams let’s look at some cool artwork that i came across. ;-)

———-

Fractals from Voronoi Diagrams:

This I came across on the page of Kim Sherriff[3]. The idea is straightforward to say the least.

It is: To create a fractal, first create a Voronoi diagram from some points, next add more points and then create the Voronoi diagrams inside individual Voronoi Regions. Some sample progression could be like this:

Repeating the above process recursively on the above would give the following Voronoi fractal.

Interestingly, this fractal looks like the structure of a leaf.

The above was repeated in color by Frederik Vanhoutte[4] to get some spectacular results. Also I would highly recommend his blog!

[Voronoi Fractal – Image Source]

I am really going to try this myself, it seems a few hours of work at first sight. Ofcourse I won’t use the code that the author has provided. ;-)

———-

Mosaic Images Using Voronoi Diagrams[5] :

I have not had the time to read this paper. However, I am always attracted by mosaics, and these ones (the ones in the paper) as created using Voronoi Diagrams have an increased coolness quotient for me. Sample this image:

Golan Levin’s[6] experiments in using Voronoi diagrams to obtain aesthetic forms yielded probably even more pleasant results. The ones below give a very delicate look to their subjects.

The tilings that are produced by just mild tweaks to the basic definition of a Voronoi Diagram for a 2-D case that I had talked about earlier can give rise to a variety of tilings. Say like the one below:

Also, today I came across a nice Voronoi Diagram on The Reference Frame:

The diagram is a representation of 17,168 weather stations around the world. Dr Motl illustrates how handy MATHEMATICA is for such things.

Click to Enlarge

———-

References:

[1] Craig Kaplan, Voronoi Diagrams and Ornamental Design.

[2] Introduction to Voronoi Diagrams – Example.

[3] Kim Sherriff, “Fractals from Voronoi Diagrams“.

[4] Frederik Vanhoutte, “Voronoi Fractal“.

[6] Golan Levin, “Segmentation and Symptom

———-

Applets:

2. Bubble Harp.

———-