# Approximating a function of a cloud of (x,y) points

My objective is to approximate an (unknown) non-linear function whose:

• input is an unordered collection of an arbitrary number of (x,y) coordinates (imagine a cloud of, say, between 1 and 1000 points in two-dimensional space)
• output is one number

I have example inputs and corresponding outputs produced by a numerical model that is very expensive to run. (Hence the motivation to approximate the function, rather than calculating it exactly every time.)

Details of the model: a Computational Fluid Dynamics simulation, where the input points represent (identical) obstacles, of which there can be an arbitrary number, and output is the resulting time-averaged velocity deficit at the origin. The origin (output point) is upstream of the obstacles, so the function is fairly smooth.

My thought was to design a neural network that could be trained to approximate this function. But I can't figure out what kind of neural network, if any, would be suitable for the job.

• Feed-forward networks require a fixed number of inputs (whereas I have an arbitrary number of (x,y) points)
• Recurrent neural networks can handle arbitrary-length inputs, but inherently attach significance to the order of these inputs and will give different outputs for different orders (whereas the "order" of the points in my input collection isn't defined and therefore shouldn't influence the output)

What would be a suitable high-level neural network design?

Or are neural networks just not the right tool for the job?

• Have you first tried a much simpler approach, e.g., representing the input as a fixed number of features and applying (penalized) linear regression? – Kodiologist Jan 6 '18 at 20:32
• Tell us a lot more about the numerical model you're trying to approximate. This will help us find a suitable approximation. In particular, I'm curious to know how the input can have variable length. Are you trying to approximate the results of a CFD/FEM simulation with varying grid levels? – DeltaIV Jan 6 '18 at 21:52
• @DeltaIV Well guessed, I am indeed looking at CFD simulations. The input points represent (identical) obstacles, of which there can be an arbitrary number. The output is the resulting velocity deficit at the origin. I'll edit this into the question. – Jean-François Corbett Jan 7 '18 at 6:50
• Good to know, thanks. 1) Is there a practical upper limit to the number of obstacles $N$, say, 20, or is $N$ limited only by the number of grid points, and by how big an obstacle is with respect to a control volume? 2) (related) are the obstacles locations "arbitrary" (provided that they can't be closer than two grid control volumes), or can they be located only at some specific positions? If you answered "yes" to both questions, how many control volumes do you have, approximately? – DeltaIV Jan 7 '18 at 7:17
• Here's some order-of-magnitude answers: $N$ would probably never exceed a few to several hundred (say 1000). An obstacle width spans several cells, say ~10. The obstacle locations are arbitrary; though they have to be separated by at least a few to several obstacle widths. – Jean-François Corbett Jan 7 '18 at 7:27

## 1 Answer

I can't speak to the feasibility any strategy in the context of CFD, but have some general concerns about how complex the function might be (from the comments, I'm curious to hear DeltaIV's ideas). Instead, I'd just like to think about the regression/function approximation problem you raise: how can we learn a function whose input consists of a point cloud containing a variable number of points?

Distance metrics and kernel functions

One possible approach is to use a method based on distances or kernel functions, which measure the similarity between two point clouds. A suitably defined distance metric or kernel function can deal with a variable number of points in each cloud, and can be made invariant to their order. Defining this function is a crucial choice, and can be highly application specific. In this case, you may have to define a custom function. Intuitively, it should be defined such that, if two point clouds are considered similar, then their respective outputs should also be similar (the converse need not be true).

For example, some form of edit distance might be appropriate. Edit distances can be defined on many objects, such as strings, graphs, and sets of points. Here, you'd define a set of operations for transforming the point clouds, such as moving a point, deleting it, or inserting a new point. You'd also define the 'cost' of each operation. For example, the cost of moving a point would increase with the distance moved. Given two point clouds $x_1$ and $x_2$, the edit distance measures the minimum cost of transforming the point clouds such that each point in $x_1$ exactly matches a partner in $x_2$. Notice that $x_1$ and $x_2$ need not contain the same number of points, and the distance is invariant to the order of the points. A downside of edit distances is that they can be computationally expensive.

A kernel function on point clouds could also be defined. One way to do this is based on a distance metric (but this isn't necessary). For example, radial basis function (RBF) kernels are typically defined on vector spaces, using Euclidean distance. But, we could instead define one on variably-sized point clouds. Given a distance metric $D$ on point clouds and kernel bandwidth $\sigma$, the RBF kernel is:

$$K(x_1, x_2) = \exp \left ( -\frac{D(x_1, x_2)^2}{2 \sigma^2} \right )$$

Learning a function

The goal is to learn a function mapping variably-sized point clouds to real number outputs, based on a set of examples. Given a suitable distance metric or kernel function on point clouds (as above), this problem can be solved using standard regression methods.

As a particularly simple example, given a distance metric, one could use k-nearest neighbors regression. Given a kernel function, kernel regression or kernelized support vector regression could be used. Alternatively, one could use an RBF network, which is a type of neural net. There should be various tricks to reduce the computational load in each case, particularly if distance computations are expensive.

• Your approach relies on the definition of a distance metric between point clouds. This distance metric should respect many symmetries that the velocity decifit function surely has, such as for example the fact that all clouds made up of the same points in arbitrary order give rise to exactly the same velocity deficit (for example, , the two point clouds {(1,3),(3,4)} and {(3,4), (1,3)}). Can you give an example of such a metric? – DeltaIV Jan 8 '18 at 18:59
• Yes, the edit distance I mentioned should obey that particular symmetry (distance between order permutations of a point cloud is zero). I may need to edit to clarify why that's true. Another possibility might be smoothing the point clouds to obtain continuous functions, then integrating over the smoothed functions to compare them. – user20160 Jan 8 '18 at 23:41
• Of course, these are solutions for generic point clouds, and it would be really cool if someone w/ knowledge of CFD (not me) could come up with a distance metric that reflects the structure of this particular problem (e.g. similarity of point clouds implies similarity of fluid behavior in some sense) – user20160 Jan 8 '18 at 23:43
• Yes, after rereading your answer more carefully I noticed that you did mention that "the distance is invariant to the order of the points", but I couldn't edit my comment anymore (5 mins limit). Adding a practical example may help clarify things. Smoothing the point clouds to obtain continuous functions also sounds interesting: do you suggest adding a radial basis function at each point and finding a linear combination of them which interpolates the point cloud? – DeltaIV Jan 9 '18 at 0:02
• Interesting. Yeah, hope to hear more from OP. Regarding smoothing: yes, smoothing with a Gaussian kernel seems like a reasonable thing to do. It would essentially be a kernel density estimate that outputs the local density of points at any location. The deep sets approach you mentioned sounds fascinating. – user20160 Jan 10 '18 at 0:53