Spatial models -- Polytopes vs Sampling
Two types of spatial models:
-
Traditional: Place individual voters randomly in an N-dimensional space,
compute the distance between each voter and each candidate to compute that
voter's ballot. -
Polytope: Kristofer's recent idea, implemented by me. Place candidates
in space, compute their Voronoi cells, intersect them to get all the
regions in space associated with each ballot, and compute their volumes.
The allure of (2) is the hope for higher precision at low cost because you
are computing areas and volumes. Looking at their source codes, QHull seems
to compute volumes exactly, but the Polytope library I'm using definitely
computes volumes by random sampling. That might still be better than method
(1) because the operations you do to compute a volume (linear inequalities)
are simpler and easier to offload to a NumPy backend or even LAPACK than
the sqrt() and if-branches that (1) requires. I want to benchmark this when
I have time.
The downside of (2) is that it forces you to assume that voters are spread
out uniformly across the space. Only method (1) allows you to distribute
voters according to some reasonable distribution like a Gaussian.
I would like to present an idea for a third method that combines features
of (1) and (2):
- Weighted Polytope: Compute Voronoi cells and their polytope
intersections exactly as in (2). But instead of assuming that voters are
uniformly distributed (i.e. Voters = Volumes), you also have a function
like (1) that tells you the voter density in space. Your goal now is to
integrate the voter density across the polytope associated with each ballot:
Voters = Mass = Integral{ Density x Volume }
We have to do the integral by random sampling, but that's what the Polytope
library is doing anyway. Here is how Polytope computes volume:
a) Draw random points from the smallest box that contains the polytope.
b) Count the points that are inside the polytope (i.e. satisfy all the
half-space inequalities).
c) Volume = (Volume of box) * (Points inside) / (All points)
To compute the "Mass" of the polytope with variable density, we just need
to add two steps:
d) For each point x inside the polytope, compute Density(x).
c) Voters = Mass = Volume x (Mean Density)
Step (d) can be done in NumPy, so I hope that this wouldn't be vastly
more expensive than what the Polytope library already does. And as I noted
earlier, I don't yet know whether computing volumes is actually faster than
method (1) for comparable accuracy. But if it is, then my method (3) could
be the best of both worlds:
- The superior speed vs accuracy trade-off geometry (2).
- The flexibility and realism of a dedicated voter-density function (1).
It might be several days before I have time to experiment with this, but I
wanted to put the ideas out there and see if any of you had any thoughts.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On 31.01.2022 21:39, Daniel Carrera wrote:
Two types of spatial models:
-
Traditional: Place individual voters randomly in an N-dimensional
space, compute the distance between each voter and each candidate to
compute that voter's ballot. -
Polytope: Kristofer's recent idea, implemented by me. Place
candidates in space, compute their Voronoi cells, intersect them to get
all the regions in space associated with each ballot, and compute their
volumes.
The allure of (2) is the hope for higher precision at low cost because
you are computing areas and volumes. Looking at their source codes,
QHull seems to compute volumes exactly, but the Polytope library I'm
using definitely computes volumes by random sampling. That might still
be better than method (1) because the operations you do to compute a
volume (linear inequalities) are simpler and easier to offload to a
NumPy backend or even LAPACK than the sqrt() and if-branches that (1)
requires. I want to benchmark this when I have time.
The downside of (2) is that it forces you to assume that voters are
spread out uniformly across the space. Only method (1) allows you to
distribute voters according to some reasonable distribution like a Gaussian.
I would like to present an idea for a third method that combines
features of (1) and (2):
- Weighted Polytope: Compute Voronoi cells and their polytope
intersections exactly as in (2). But instead of assuming that voters are
uniformly distributed (i.e. Voters = Volumes), you also have a function
like (1) that tells you the voter density in space. Your goal now is to
integrate the voter density across the polytope associated with each ballot:
Voters = Mass = Integral{ Density x Volume }
This idea (restricted to 2D space) came up in an earlier thread in the
context of Yee diagrams, since the pixel at (x,y) in a Yee diagram is
given by the outcome of an election where the voters are represented by
a Gaussian centered at that point, and the Voronoi regions (as usual)
give the area within which voters vote A>B>C, etc.
So by evaluating a Gaussian integral over these regions, we could get a
v->inf Yee diagram. This could be interesting in particular for IRV due
to its chaotic behavior and tie amplification.
For 2D, it might be possible to do an exact integral of an approximate
erf. At least in that case, it would be more accurate than method 1
(assuming the erf is well-behaved). That approach won't easily scale to
higher dimensions, though.
I don't yet know whether computing volumes is actually faster than
method (1) for comparable accuracy. But if it is, then my method (3)
could be the best of both worlds:
- The superior speed vs accuracy trade-off geometry (2).
- The flexibility and realism of a dedicated voter-density function (1).
I'd imagine it would depend on how easy it is to do high dimensional
Gaussian integration. There may be more efficient methods than ordinary
MC (e.g. quasi-MC,
https://web.maths.unsw.edu.au/~josefdick/preprints/DKS2013_Acta_Num_Version.pdf)
or there may be special-case Gaussian integrals over simplices, and then
the polytope can be decomposed to simplices (like the approach for
determining the exact area) and the Gaussian integral applied to them.
Forest would probably know more about tricks of calculus; it's not my
area of speciality.
-km
On Mon, Jan 31, 2022 at 3:32 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
I don't yet know whether computing volumes is actually faster than
method (1) for comparable accuracy. But if it is, then my method (3)
could be the best of both worlds:
- The superior speed vs accuracy trade-off geometry (2).
- The flexibility and realism of a dedicated voter-density function (1).
I'd imagine it would depend on how easy it is to do high dimensional
Gaussian integration. There may be more efficient methods than ordinary
MC (e.g. quasi-MC,
https://web.maths.unsw.edu.au/~josefdick/preprints/DKS2013_Acta_Num_Version.pdf
)
or there may be special-case Gaussian integrals over simplices, and then
the polytope can be decomposed to simplices (like the approach for
determining the exact area) and the Gaussian integral applied to them.
So I started reading up on quasi-MC. I haven't done this before so my
initial thoughts might be incorrect, but I think I've found two things:
-
It looks easy to do. There are libraries (e.g. scipy.stats.qmc) that
just give you a sequence of numbers that you can use as a drop-in
replacement for your random number generator in your MC integrator. -
But I see a lot of warnings saying that QMC constructions are designed
for special values of n, like powers of 2 or large primes, and if I
sub-sample or pick the wrong number of points I might ruin all their
properties. This is potentially a huge issue because integrating over the
polytope consists of throwing away all the points that aren't inside the
polytope.
Right now I'm just hoping that one of the QMC number generators is more
forgiving. Sobol seems to be the worst offender, while the Halton sequence
looks like it might be more forgiving:
The doc says:
Alternatively, you can skip some points like sampler.fast_forward(5) ...
Presumably that means that the Halton sequence isn't very finicky about
exactly which points get included in the integral. As luck would have it,
the Halton sequence is apparently superior for "low-dimensional" problems N
<= 6 (Morokoff & Caflisch 1995), which is the dimensionality I most care
about anyway. Honestly, the N=2 and N=3 problem is the most interesting for
real world elections.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On 01.02.2022 04:35, Daniel Carrera wrote:
So I started reading up on quasi-MC. I haven't done this before so my
initial thoughts might be incorrect, but I think I've found two things:
-
It looks easy to do. There are libraries (e.g. scipy.stats.qmc) that
just give you a sequence of numbers that you can use as a drop-in
replacement for your random number generator in your MC integrator. -
But I see a lot of warnings saying that QMC constructions are
designed for special values of n, like powers of 2 or large primes, and
if I sub-sample or pick the wrong number of points I might ruin all
their properties. This is potentially a huge issue because integrating
over the polytope consists of throwing away all the points that aren't
inside the polytope.
I'm hardly an expert on these matters, but I found a paper suggesting a
way to transform a simplex into a hypercube (by, I think, using extended
barycentric coordinates as a change of bases). If that's a workable
approach, then you could decompose the polytope into simplices,
transform these simplices into cubes, and do QMC on the cubes without
throwing any points out.
https://istam.iitkgp.ac.in/resources/2014/proceedings/59-istam-nm-fp-268.pdf
Presumably that means that the Halton sequence isn't very finicky about
exactly which points get included in the integral. As luck would have
it, the Halton sequence is apparently superior for "low-dimensional"
problems N <= 6 (Morokoff & Caflisch 1995), which is the dimensionality
I most care about anyway. Honestly, the N=2 and N=3 problem is the most
interesting for real world elections.
For 2D, you could compare your approach with
https://math.stackexchange.com/a/2283927 and the "exact approximate"
approach suggested by Thomas Ahle in a comment to
https://math.stackexchange.com/questions/627720; and see which is most
accurate/faster, if you have the time.
-km
On Tue, Feb 1, 2022 at 5:43 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
I'm hardly an expert on these matters, but I found a paper suggesting a
way to transform a simplex into a hypercube (by, I think, using extended
barycentric coordinates as a change of bases). If that's a workable
approach, then you could decompose the polytope into simplices,
transform these simplices into cubes, and do QMC on the cubes without
throwing any points out.
https://istam.iitkgp.ac.in/resources/2014/proceedings/59-istam-nm-fp-268.pdf
So I've been thinking about this, and I think I've come to the conclusion
that at least in this instance it is perfectly fine to throw out QMC
points. Here's why: Suppose I want to integrate a function f() over some
polytope P.
Voters = Integral_P { f( x ) }
Let C be some cube that contains the polytope P. I can always define a
function g() that is defined on C but has compact support in P:
g(x) = { f(x) if x in P; or 0 otherwise }
There's no reason why I shouldn't be allowed to integrate g(x) over the
cube C and technically I'm not throwing away any points. But that is
exactly equivalent to the original plan of generating QMC points inside the
C, selecting those in P, and evaluating f() on those.
Wikipedia says that one of the key advantages of quasi-MC over regular MC
is that a low-dispersion sequence gives you more even coverage of the space
without making a lattice. Random sampling will naturally create clusters of
points and voids with few points. It is the nature of randomness that
clustering happens. Low-dispersion sequences avoid clustering. Now... I
don't know why we're told to not throw away points. But if the reason is
that in general throwing away points will create gaps, then... well...
slicing the space would be an exception to the rule. If the points
uniformly cover C then they uniformly cover any subset of C. You just
need to be aware that you are effectively integrating over that subset of
C and not all of C, but in our case that is exactly what we want.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Great idea ... and if you bevel/taper/dither the function near the boundary
of its support, the numerical quadrature will converge faster.
El mar., 1 de feb. de 2022 5:44 p. m., Daniel Carrera dcarrera@gmail.com
escribió:
On Tue, Feb 1, 2022 at 5:43 AM Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:
I'm hardly an expert on these matters, but I found a paper suggesting a
way to transform a simplex into a hypercube (by, I think, using extended
barycentric coordinates as a change of bases). If that's a workable
approach, then you could decompose the polytope into simplices,
transform these simplices into cubes, and do QMC on the cubes without
throwing any points out.
https://istam.iitkgp.ac.in/resources/2014/proceedings/59-istam-nm-fp-268.pdf
So I've been thinking about this, and I think I've come to the conclusion
that at least in this instance it is perfectly fine to throw out QMC
points. Here's why: Suppose I want to integrate a function f() over some
polytope P.
Voters = Integral_P { f( x ) }
Let C be some cube that contains the polytope P. I can always define a
function g() that is defined on C but has compact support in P:
g(x) = { f(x) if x in P; or 0 otherwise }
There's no reason why I shouldn't be allowed to integrate g(x) over the
cube C and technically I'm not throwing away any points. But that is
exactly equivalent to the original plan of generating QMC points inside the
C, selecting those in P, and evaluating f() on those.
Wikipedia says that one of the key advantages of quasi-MC over regular MC
is that a low-dispersion sequence gives you more even coverage of the space
without making a lattice. Random sampling will naturally create clusters of
points and voids with few points. It is the nature of randomness that
clustering happens. Low-dispersion sequences avoid clustering. Now... I
don't know why we're told to not throw away points. But if the reason is
that in general throwing away points will create gaps, then... well...
slicing the space would be an exception to the rule. If the points
uniformly cover C then they uniformly cover any subset of C. You just
need to be aware that you are effectively integrating over that subset of
C and not all of C, but in our case that is exactly what we want.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Election-Methods mailing list - see https://electorama.com/em for list
info
So I implemented my proposed "voter mass function" based on integrating
"voter density" across a polytope. I have run some benchmarks on a sample
2D polytope (small dimension, but relevant to real elections). I
implemented regular Monte Carlo (MC) integration, as well as the Quasi
Monte Carlo (QMC) suggested by Kristofer. The QMC method was done with both
a Halton and a Sobol sequence. The voter density function is a
Gaussian distribution. Here are my results:
- The Halton sequence is apparently very expensive to generate. Most of
the cost of QMC is spent just generating the sequence apparently. Despite
this absurdity, it still manages to match MC in terms of cost for a given
level of accuracy. QMC/Halton can match the accuracy of MC for much lower N
(number of points) and that roughly compensates for the lack of speed.
Target Relative Error: < 1e-3
QMC/Sobol: N = 2^12 --- time = 0.000520s
QMC/Halton: N = 2^13 --- time = 0.000671s
Regular MC: N = 2^20 --- time = 0.081216s
- The Sobol sequence has about the same accuracy as Halton (slightly
better in this example), but it is just as fast as regular MC (slightly
faster). The overall result is impressive; especially at higher accuracy.
QMC/Sobol: N = 2^24 --- time = 1.96s --- error = 1e-6
QMC/Halton: N = 2^24 --- time = 31.1s --- error = 2e-6
Regular MC: N = 2^24 --- time = 1.89s --- error = 2e-4
I'll still try to find some sort of quadrature rule that can be faster and
more exact, but I'm finding the subject difficult to understand. My
baseline expectation is that I'll just stick to QMC/Sobol.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On 02.02.2022 12:41, Daniel Carrera wrote:
So I implemented my proposed "voter mass function" based on integrating
"voter density" across a polytope. I have run some benchmarks on a
sample 2D polytope (small dimension, but relevant to real elections). I
implemented regular Monte Carlo (MC) integration, as well as the Quasi
Monte Carlo (QMC) suggested by Kristofer. The QMC method was done with
both a Halton and a Sobol sequence. The voter density function is a
Gaussian distribution.
Great!
I was browsing the scipy.stats.qmc manual and noticed it has a third
method, Latin hypercube, explicitly designed for cubes. Would this
method be applicable to your problem, if you use the function g that's
zero outside of the simplex and Gaussian inside it? Does the proportion
of the cube occupied by the simplex vanish too quickly as d increases?
I would also imagine that you could reduce the dimension by one by using
a standard 1D Gaussian integral over the last dimension as long as you
can do line-simplex intersections to determine what line you should
integrate over. But perhaps the general covariance problem you mentioned
earlier would make this impractical - that it would be rather difficult
to line up the Gaussian integral with that line in the remaining dimension.
On a related note, I was reading James Green-Armytage's paper about
strategic voting: http://jamesgreenarmytage.com/strategy-utility.pdf. On
page 21, he states that an 8D spatial model is a good fit to the
political poll model, while 1D is not quite as good. He doesn't mention
intermediate dimensionality models, but it may provide a reason for
supporting high dimension spatial models (as long as the fit keeps
improving even when going from say, 7D to 8D). It does, I think, provide
pretty good evidence that there's little need for going beyond 8D, at least.
-km
On Thu, Feb 3, 2022 at 2:15 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Great!
I was browsing the scipy.stats.qmc manual and noticed it has a third
method, Latin hypercube, explicitly designed for cubes. Would this
method be applicable to your problem, if you use the function g that's
zero outside of the simplex and Gaussian inside it?
I tested it, and it didn't do as well as Sobol. The Latin Hypercube was a
little faster than the Halton sequence but a little less accurate. I think
Sobol has a huge advantage because (according to Wikipedia) there is a fast
implementation based on low-level bitwise operations and that's just hard
to beat with regular arithmetic.
Does the proportion
of the cube occupied by the simplex vanish too quickly as d increases?
I ran a test. It's certainly an issue, but not quite as bad as I had
expected. First, the library can easily detect the polytopes that are
completely empty. For the rest, I ran 10 sample elections with candidates
uniformly random in the unit cube. The proportion of the cube occupied by
the polytope seems to approach 10% as I get closer to 8 dims.
N_candidates = N_dim + 1
2 Dims: v = 0.535417 +/- 0.236171
3 Dims: v = 0.256944 +/- 0.134119
4 Dims: v = 0.156250 +/- 0.065763
5 Dims: v = 0.134810 +/- 0.035892
6 Dims: v = 0.125693 +/- 0.009282
That said, higher dimensions do get more expensive for other reasons ---
like the fact that you have (N_dim+1)! polytopes. I was planning to run the
simulation till N_dim=8 but I've been waiting for N_dim=7 to finish and it
just doesn't want to finish.
I would also imagine that you could reduce the dimension by one by using
a standard 1D Gaussian integral over the last dimension as long as you
can do line-simplex intersections to determine what line you should
integrate over. But perhaps the general covariance problem you mentioned
earlier would make this impractical - that it would be rather difficult
to line up the Gaussian integral with that line in the remaining dimension.
Yeah. If we assume that the Gaussian is fully symmetric (which feels a bit
restrictive) you could imagine drawing radial lines and figuring out where
they cross the polytope. The details could be a bit complicated. I have no
idea if that would be faster, but I could try something like that. I can't
work on this idea right now, but I didn't want to dismiss it.
On a related note, I was reading James Green-Armytage's paper about
strategic voting: http://jamesgreenarmytage.com/strategy-utility.pdf. On
page 21, he states that an 8D spatial model is a good fit to the
political poll model, while 1D is not quite as good. He doesn't mention
intermediate dimensionality models, but it may provide a reason for
supporting high dimension spatial models (as long as the fit keeps
improving even when going from say, 7D to 8D). It does, I think, provide
pretty good evidence that there's little need for going beyond 8D, at
least.
It's good to have a maximum. I hope we can get away with fewer than 8
dimensions. Regardless of the true political dimensions of the electorate,
if you only have N<8 parties, those parties will lie in an
(N-1)-dimensional subspace. That's why I suspect that we can get away with
modelling a lot less than 8D and just be aware that I'm only modelling the
subspace of political positions that is actually spanned by the candidates.
The US is a specially pathological example, where apparently your views on
LGBT rights somehow dictate your views on sex education, AR-15s, tax law,
climate change, vaccines, and the Israel-Palestine conflict.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
El jue., 3 de feb. de 2022 2:34 p. m., Daniel Carrera dcarrera@gmail.com
escribió:
On Thu, Feb 3, 2022 at 2:15 PM Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:
Great!
I was browsing the scipy.stats.qmc manual and noticed it has a third
method, Latin hypercube, explicitly designed for cubes. Would this
method be applicable to your problem, if you use the function g that's
zero outside of the simplex and Gaussian inside it?
I tested it, and it didn't do as well as Sobol. The Latin Hypercube was a
little faster than the Halton sequence but a little less accurate. I think
Sobol has a huge advantage because (according to Wikipedia) there is a fast
implementation based on low-level bitwise operations and that's just hard
to beat with regular arithmetic.
Does the proportion
of the cube occupied by the simplex vanish too quickly as d increases?
I ran a test. It's certainly an issue, but not quite as bad as I had
expected. First, the library can easily detect the polytopes that are
completely empty. For the rest, I ran 10 sample elections with candidates
uniformly random in the unit cube. The proportion of the cube occupied by
the polytope seems to approach 10% as I get closer to 8 dims.
N_candidates = N_dim + 1
2 Dims: v = 0.535417 +/- 0.236171
3 Dims: v = 0.256944 +/- 0.134119
4 Dims: v = 0.156250 +/- 0.065763
5 Dims: v = 0.134810 +/- 0.035892
6 Dims: v = 0.125693 +/- 0.009282
That said, higher dimensions do get more expensive for other reasons ---
like the fact that you have (N_dim+1)! polytopes. I was planning to run the
simulation till N_dim=8 but I've been waiting for N_dim=7 to finish and it
just doesn't want to finish.
I would also imagine that you could reduce the dimension by one by using
a standard 1D Gaussian integral over the last dimension as long as you
can do line-simplex intersections to determine what line you should
integrate over. But perhaps the general covariance problem you mentioned
earlier would make this impractical - that it would be rather difficult
to line up the Gaussian integral with that line in the remaining
dimension.
Yeah. If we assume that the Gaussian is fully symmetric (which feels a bit
restrictive) you could imagine drawing radial lines and figuring out where
they cross the polytope. The details could be a bit complicated. I have no
idea if that would be faster, but I could try something like that. I can't
work on this idea right now, but I didn't want to dismiss it.
On a related note, I was reading James Green-Armytage's paper about
strategic voting: http://jamesgreenarmytage.com/strategy-utility.pdf. On
page 21, he states that an 8D spatial model is a good fit to the
political poll model, while 1D is not quite as good. He doesn't mention
intermediate dimensionality models, but it may provide a reason for
supporting high dimension spatial models (as long as the fit keeps
improving even when going from say, 7D to 8D). It does, I think, provide
pretty good evidence that there's little need for going beyond 8D, at
least.
If a poll has potential voters fill out a questionnaire with where they
self locate on 40 issue, you end up with a forty by n matrix M, where n is
the number of voters that submitted their completed questionnaires.
If you then diagonalize the 40 by 40 matrix that is the matrix product of M
by its transpose ... the eigenvalues along the diagonal with reveal the
relative significance of the respective issues. When you get to an
eigenvalue that is a order of magnitude smaller than the largest one, you
can conclude that the remaining issues were not as relevant to the voters
or else weaker clones (correlates) of the more
interesting/important/controversial issues.
Evidently James Green-Armytage made a judgment on where the drop in
"singular value" magnitudes became significant.
It's good to have a maximum. I hope we can get away with fewer than 8
dimensions. Regardless of the true political dimensions of the electorate,
if you only have N<8 parties, those parties will lie in an
(N-1)-dimensional subspace. That's why I suspect that we can get away with
modelling a lot less than 8D and just be aware that I'm only modelling the
subspace of political positions that is actually spanned by the candidates.
The US is a specially pathological example, where apparently your views on
LGBT rights somehow dictate your views on sex education, AR-15s, tax law,
climate change, vaccines, and the Israel-Palestine conflict.
PR is supposed to help fix this, but ingrained traditions are hard to buck
... and (obviously) PR has no chance at all of helping if we never adopt it.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Election-Methods mailing list - see https://electorama.com/em for list
info