Search code examples
pythongrid-searchhyperparameters

Grid search over a cube/sphere in R^n

I'm trying to implement a grid search (in Python, if it matters) over a sphere in R^n , where n is unknown.

The input includes the radius and the center of the sphere, as well as a hyperparameter theta , that controls the resolution of the grid. I would like to express each point in this sphere as function of these three parameters.

I'm also willing to consider cube search, iterating ONLY the faces of the cube. (Namely, iterating the L_inf sphere)

If I knew that n=2, what I would do is:

import numpy as np

def enumerate_2d_sphere(R,theta,center=(0,0)):
    for n in xrange(int(2*np.pi / theta)+1):
        degree = n*theta
        point =(center[0]+R*np.cos(degree),center[1]+R*np.sin(degree))
        yield point

for p in enumerate_2d_sphere(1,0.1):
    print p

Since n can be arbitrarily large, I'm looking for a way to iterate over the sphere\cube efficiently.

Any ideas?

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

I ended up using a modified version of what strubbly suggested:

import itertools
import numpy as np
import matplotlib.pyplot as plt

def f(d, center, scale=1):
    dim = len(center)
    print d/-2.0
    diff = scale * np.array([d/-2.0 for _ in xrange(dim)])
    bias = diff + center
    for i in range(dim):
        l = ([ xrange(1,d) for _ in xrange(i)] +
             [[0,d]] +
             [ xrange(d+1) for _ in xrange(dim-i-1)]
            )
        for r in itertools.product(*l):
            yield scale*np.array(r)+bias
#example for R^2:
center = (1,1.5)
data = np.array([x for x in f(20,center,scale = 0.1)])


plt.scatter(data[:,0], data[:,1],color='r',s=100,alpha=0.5)
plt.scatter(center[0], center[1],color='b',s=300,alpha=0.5)
plt.show()

The output figure:

enter image description here

One more option, is to generate uniformly distributed samples on the sphere. Note that the number of samples controls the "density" (or expected density) of points:

import numpy as np
def generate_random_points(R,center,quantity=1000):
    """
    :param R: float
    :param center: np.array
    :param quantity: int
    """
    dim = len(center)
    for n in xrange(quantity):
        s = np.random.normal(0, 1,dim)
        r = np.sqrt(np.dot(s,s))
        s = (R/r) * s
        yield s+center

The worst method (in terms of simplicity and efficiency) would be to generate points on the sphere using enumeration of n-1 angles. The lack of efficiency follows from the need to calculated products sin and cos often (although this can be hacked too)

Solution

  • You can use spherical coordinates in n dimensions (see e.g. wikipedia) or you can use the euclidean coordinates by just setting the last coordinate to be whatever is needed to get the correct radius (plus or minus). Both of these are fine parameterizations and will give you all the points on the sphere - with the right number of parameters to iterate through.

    But they don't lead naturally to a constant area (volume) element - as is easy to see by just thinking about the 3-sphere. There is no easy solution to that problem.

    I think a possible approach would be to use the n-1 dimensional grid parameterisation but to subdivide the nth component into a variable number of values depending on the volume.

    The faces of the n-cube are easier: just generate the n pairs of faces where the n-th coordinate is minimal or maximal. So, for example, considering the n-cube of size 1 starting at the origin:

    Set the first coordinate to zero and enumerate a grid over the remainder. Then set it to one and do it again. Then repeat for the second coordinate. And so on.

    Here's a simple way to do that using itertools.product. I have scaled the box into integer coordinates for simplicity and efficiency: you'll need to rescale and move the centre. So n is the number of dimensions and d the number of subdivisions along each axis.

    import itertools

def f(n,d):

    for i in range(n):
        l = ([ range(1,d-1) for _ in range(i)] +
             [[0,d-1]] +
             [ range(d) for _ in range(n-i-1)]
            )
        for r in itertools.product(*l):
            yield r

print(list(f(4,3)))