Decision making, part N

(Warning: kooky stuff ahead)

Continuing on the "what's a good decision making system"-thread, here's a vague and incomplete idea that I've been turning over. A system of governance finds a problem to solve, generates a solution to it and implements it. To find a problem, it needs to know about it, which requires information about the state of the governed system and the ability to filter the information to recognize problems. To generate a solution, it needs to generate and evolve several different solutions and pick the best one. To implement the solution, it needs traction in the governed system.

In abstract: sensory information -> problem filter -> problem broadcast -> solution generation -> solution filter -> implementation plan -> implementation broadcast -> implementation.

Gathering sensory information is a [streaming] parallel map pass. The problem filter is a pattern recognizer, maybe a reduction tree of some sort. The problem broadcast make the problem known to solution generators. The solution generation is another parallel map pass, and the solution filter is a tournament. The implementation plan generation is similarly map-reduce, followed by the broadcast to implementers who then get to work.

It's not quite as simple though, as each step requires continuous feedback loops to optimize the implementation. Some parts of the problem are only found out at implementation time and the solution and plan need to evolve with the problem.

One anecdote from AI is that the quality of your algorithm is secondary to the amount of data you have. So you want the map passes gather as much data as possible and have a reduction network on top to do the filtering. The quality of a working reduction network is less important than the width of the gather pass. And I guess the reduction network functions the better the larger part of the population it involves.

In sports the best results are within an order of magnitude from average results. Maybe the same is true for intellectual pursuits: the world's best dictator may work as well or better than a parallelized council of ten average ministers, but a lot worse than a couple hundred average ministers, never mind a few dozen million.

Traction. For an implementation to actually get done, there needs to be buy-in among the implementers. For that the implementers need to be involved in figuring out the problem, solution and the implementation plan. To fix a problem, you need to know what problem you are fixing, otherwise you're just doing random pointless things and can't evolve the solution. Implementation is yet another of those things that benefits a lot from parallelization.

What do reduction networks and voting have to do with each other? Each filtering step needs a decision to be made, decisions need to be informed and informed decisions need a wide base of decision makers to provide the information. So, uh, grab a big part of the population, run the selection by them, go with the majority? Or is there a better way to get the information from the population, get the things that really matter and use that to do the selection?

The problem with small governments is that the smaller a government, the easier it is to bias. Bribery, threats, cronyism, nepotism, lobbying, you name it. Heck, just paying the decision makers an above-average salary is enough to bias the decisions. The problem with large governments is that you're sampling a much noisier pool. Uninformed people are easier to sway with negotiation skill? How does that differ from swaying a small amount of a bit differently uninformed people (i.e. MPs)? The republic battle-cry is "against mob rule!", but is it just a smaller mob that rules in a republic? Does a system that uses a small amount of elected lawyers do a better job at solving problems than a system that uses the whole population?

How do you filter out flagrantly anti-minority decisions? What's the threshold in the ratio between majority advantage and minority disadvantage. How do the current systems guard against that? Make the decision making body small enough to be outnumbered by the relevant minorities? But they also have guards and all this force boosting going on... demonstrations by thousands seem to have very little effect even on single parties, much less the whole government.

(Yes, there is a threshold in majority:minority-decisions: murder is outlawed, no? Much to the chagrin of the murder society. More controversial are decisions such as not providing street signs in every language of the world. It would be good to have that, and it is making the life more difficult for a significant part of the population, but currently the benefit is too low compared to the cost. So we compromise by having English signs at the airports, Swedish signs at most places in the south and west, Russian signs at shops in border towns, Japanese signs at Helsinki design shops and so on.)

The anti-democracy strawman usually goes like this: Suppose you have a vote that devolves into a nasty argument. In the next session, the winners of the previous vote propose hanging the losers of the previous vote. Continue until you have only two people left. Now, why don't we see that in parliaments? Surely the ruling party votes to have the opposition parties and their supporters shot. All the way until you have two MPs left, one stabs the other and declares himself emperor. .. Oh wait, that does actually happen. How do you avoid this kind of thing?

How do governments go wrong? By wrong here I mean something like "does not implement policies in the interest of the population". In other words, the governmental idea of good policy diverges from the population's idea of good policy. Or is it from the population's benefit? Does good policy do good or is it merely something seen to be good. How do you pass "bitter pill"-policies if everyone making the decision will take a short-term loss for a long-term gain. Same way as we do now?

The goal of a system of governance is to implement policies that are beneficial to the population. When a system benefits a sub-group disproportionally, the system is biased. When a system is generating policies worse than best known, it is uninformed. When a system can't implement the generated policies effectively, it lacks traction. A system of governance should strive to be unbiased, informed and popular.

To be unbiased, the system should be unbiased from the start and the cost of biasing the system should be high enough to be prohibitive. For the system to be unbiased, the individual actors in the system need to be close to an unmodified representative sample of the population. For the cost of biasing to be prohibitive, the number of individual actors in the system times the average cost of biasing an actor should be as high as possible.

To be informed, the system needs information. The more relevant information the system has, the better decisions it can make. Find fixable problems, find good solutions, find good implementation plans, refine through attempts at implementation. Each step requires a lot of sensory data and processing. To maximize the sensory input of the system, you need to maximize the number of sensors times the power of the sensor. Similarly, the processing power of the system is the number of processors times the power of each processor.

Brush stroke blending

Brush stroke blending is somewhat of a black art. Which is a shame, since Photoshop's been doing it for more than 15 years now.

Lemme try and explain.

Suppose you've got a pressure-sensitive drawing tablet where the pressure controls the opacity of the brush. If you do a low-pressure stroke, you'd like to have a flat surface of color with roughly the same alpha everywhere (say, alpha 0.5 for half pressure). If you use the usual source-over blend, each of the brush stroke segments would add to the alpha since it's src.a + (1-src.a) * dst.a. As the brush stroke intersects with itself, the alpha builds up all the way to 1. Which is not what you want if you're trying to paint an alpha 0.5 surface.

For a brush stroke with fixed alpha, this would be no problem, you could just vary the blend opacity of the stroke layer. But if you want to have varying alpha inside the stroke layer, you need a different blend. What I was using for hard-edged brushes (and what my Drawmore Touch prototype is using) is MAX blend for the alpha: max(src.a, dst.a). If an alpha 0.5 brush is stamped over a previous alpha 0.5 brush stroke pixel, the result is going to be alpha 0.5. This prevents the stroke layer from accumulating opacity above the brush opacity and makes it possible to do smooth surfaces using pressure-controlled opacity.

But it's broken for soft brushes. With soft brushes you'd like to paint a smooth surface with a soft edge. If you do alpha max, the brush intersections have cross-shaped blending artifacts and it's very difficult to do a smooth surface (you can try with the Drawmore thing: drag left on the brush 100% control to make it 0% hardness, then try to paint a smooth surface. No can do.) GIMP & Krita probably suffer from this too, Photoshop does something more magical.

What I've got in ShaderPaint is my latest attempt at solving this. It does brush stamping and alpha max mixed with source-over clamped to current stamp alpha.

void strokeBlend(vec4 src, float srcA, vec4 dst, out vec4 color)
{
    // Source-over blend for non-premultiplied alpha.
    color.a = src.a + (1.0-src.a)*dst.a;
    color.rgb = src.rgb*src.a + dst.rgb*dst.a*(1.0-src.a);
    color.rgb /= color.a;

    // Saturate color alpha to brush stamp max alpha.
    // For hard brushes this should be roughly the same as max(dst.a, src.a).
    // For soft brushes, the stroke accumulates alpha up to the brush stamp alpha,
    // which results in a flat stroke area with a smooth edge.
    if (color.a > srcA) {
        color.a = max(dst.a, srcA);
    }
}

The brush stamping shader is pretty simple. You pass it the last stamp position and the current mouse position (& use them to calculate the last stamp position for the next line segment). The shader then steps along the last stamp -> mouse position -vector with the brush spacing offset. For each of the brush stamp points, accumulate brush color with the in-stroke blending function.

strokeDirection = normalize(strokeDirection);
float stampSeparation = brushRadius * 0.5;
float stampCount = floor(strokeLength / stampSeparation + 0.5);

for (float i = 1.0; i < 200.0; i++) { // Max 200 stamps per segment.
    if (i > stampCount) { // Break once we're done with the stamps.
        break;
    }

    // Distance from circular brush.
    float d = length(fragCoord - (lastPoint + strokeDirection*i*stampSeparation)) / brushRadius;

    if (d < 1.0) { // The pixel is inside the brush stamp.
        vec4 src = currentColor;
        // Create a soft border for the brush.
        src.a *= smoothstep(1.0, hardness * max(0.1, 1.0 - (2.0 / (brushRadius))), d);
        strokeBlend(src, opacity, fragColor, fragColor); // Blend the brush stamp into the stroke layer.
    }
}

Dunno if there's a nicer solution, given the messiness of the blending function.

Easy 3D on the web

Problem: can't do 3D graphics on the web. Solution: WebGL. New problem: no, I mean, I want to put this 3D model onto a web page. Solution: Sketchfab / Three.js / Babylon.js / ShaderToy. New new problem: I need to download libraries and code stuff or host the files on a SaaS or develop a third brain to model using modulo groups of signed distance fields moving along Lissajous curves.

Could easy 3D be part of the web platform? And how? With images, the solution was simple. The usual image file is a 2D rectangle of static pixels and all you really needed to figure out was how to layout, size and composite it with regards to the rest of the web page. When you step outside of simple static 2D images, all hell breaks loose.

Animated GIFs have playback timing and that's not so easy to figure out, and so animated GIFs are pretty broken. Videos need playback controls with volume and scrubbing, potential subtitle tracks, and a bunch of codecs both on the video and audio sides, so they were pretty broken as well. (Then YouTube started using HTML5 videos because mobiles don't do Flash. And magically the video issues were fixed~)

SVGs also need to handle input events and have morphed from "umm, put this in an embed and it'll maybe work" to their current (pretty awesome!) state where an SVG can be used as a static image, an animated image, embedded document and an inline document. Something for everyone!

Displaying a 3D model on a web page is a bit like mixing SVG with video elements. You'd like to have controls to turn the model around - it is 3D after all. And you'd like to have the model animate - again, it's 3D and 3D's good for animations. It'd be also nice to have the model be interactive. I mean, we were promised a 3D data matrix by a bunch of fiction writers in the 80s, and that's going to require some serious animated 3D model clicking action (to be fair, they also promised us a thermonuclear war, but let's not go there right now.)

So. 3D model. Web page. <3d src="castle_in_the_sky.3d" onclick="event.target.querySelector('#gate').classList.add('open')"> Right?

What file format do you standardize on? How do you load in textures and geometry? How do you control the camera? How do you do shaders for the materials? How do you handle user interaction? What are the limits of this 3D model format? How do you make popular 3D packages output this file format (plus animations, plus semantic model for interactivity)? How do you compress the thing and progressively stream it?

ShaderPaint

I wrote a small painting program on ShaderToy, using the new multipass rendering feature. It's called ShaderPaint and it was a lot of fun to write.

The fun part about writing programs in ShaderToy is the programming model it imposes on you. Think of it as small pixel-size chunks of memory wired together in a directed graph. Each chunk of memory runs a small program that updates its contents. The chunks are wired together so that a chunk can read in the contents of chunks that it's interested in. The read gives you the contents on the last time step, so there's no concurrent crosstalk happening.

This is... rather different. Your usual programming model is all about a single big program, executing on a CPU, reading and writing to a massive pool of memory, modifying anything, anywhere, at any time. To go from that to ShaderToy's memory-centric approach is a big shift in perspective. Instead of thinking in terms of "The program is going to do this and then it's going to do that and then it's going to increment that counter over there.", you start to think like "If the program is running on this memory location, do this. If the program is running on that memory location, do that. If the program is running on the counter's memory location, increment the value." You go from having a single megaprogram to an army of small programs, each assigned to a memory location.

In the figure above, I've sketched the data flow of an output pixel. First, the UI inputs coming from the shader uniforms modify the UI state layer, which is read by the stroke layer to draw a brush stroke on it. The stroke layer is then composited with the draw layer when the brush stroke has ended. The final step is to composite the stroke layer and draw layer onto the output canvas, and draw the UI controls on it, based on the values on the UI state layer.

Flat cameras

Well, this is really cool. It's a flat camera. A camera sensor with a special mask in front of it that makes it possible to computationally deconvolve the sensor data into an image. Imagine credit-card-slim mobiles and mobile cameras with a very large image sensor for shooting in low light. Or front-facing cameras embedded into the display.

On a similar vein, this Light L16 thing looks pretty nifty: jam 16 small cameras into a smartphone and do computer vision magic to treat the ensemble as a single big sensor.

Display tech

I was playing with a Kindle the other day. It's got an e-ink display that's quite different from the usual mobile displays. For one, it works as a reflective display, much like the pages of a paper book. That means that you can read it without a backlight, unlike the LCD display you may have in your phone. The second big difference is that it's black & white only. Third, the screen can stay on and display an image without using any power. And finally, the refresh rate is very slow. So what's going on here? Why does it work that way?

E-ink displays have a tiny capsule for each pixel. This capsule is filled with black ink particles and white ink particles. The different colors have different charges. There's a charged plate underneath the capsule that can change the sign of its charge so as to attract one color and repel the other.

Let's say that you have black particles with a positive charge and white particles with a negative charge. When you set the charged plate to a positive charge, the white particles fly towards the charged plate at the bottom of the capsule and the black particles are pushed to the top of the capsule. As you're looking at the display from above, you see that the pixel turns black.

When you flip the charge, the black particles are drawn down to the bottom and the white particles are pushed to the top. The pixel now turns white.

Because the pixels use ink particles, the way they interact with light is much like you'd see with a regular sheet of paper. Light hits the ink at the top of the screen and bounces away towards your eyes. The black ink particles absorb more of the light than the white ones, and you see the resulting contrast. Nice and simple. But kinda slow, as the charging plate needs to flip its charge and the physical ink particles need to swap places for the pixel to change color.

By comparison, LCDs are quite a different beast. An LCD pixel is made out of three layers of material that polarize light. Polarized light is light where all the photons are vibrating in the same direction. In unpolarized light, the photons are vibrating in every which direction. To make polarized light, you either need a light source that produces polarized light or a filter that blocks photons that are vibrating in the wrong direction.

If you put two polarizing filters on top of each other, they do a bit of a trick. If the polarized filters are pointing to the same direction, they let light through. As you rotate them relative to each other, they let less and less light through, and once they're rotated to a 90 degree angle, they don't let any light through. What if you could change this rotation angle with electricity?

That's pretty much what an LCD pixel does. It's got a liquid crystal layer that rotates the polarization of light depending on how much electricity you put through it. To make the trick complete, it has two polarizing filters below and above the liquid crystal layer. The polarizing filters are at a 90 degree angle to each other, so when the liquid crystal layer is in the unrotating state, the pixel doesn't let any light through and appears dark. When the liquid crystal is set to rotate incoming light by 90 degrees, light passes through the pixel, making the pixel look bright.

Usually an LCD screen has a bright light behind it. The LCD in front blocks some of the light, creating the image that you see. Because the filters in the LCD are not perfect, some of the light hitting the dark pixels seeps through, making the darks brighter than ideal. Additionally, the black pixels are lit from behind at all times at the same intensity as the brightest white pixels, which makes LCDs relatively power-hungry. Because the liquid crystals can twist rapidly, LCDs have good refresh rates and work for displaying moving graphics.

OLEDs. OLEDs are tiny tiny lights, printed on the screen surface. The brightness of each of lamp is controllable by the amount of electricity fed to it. Because they're tiny individual lights, they are more power-efficient than LCDs as dark pixels don't use any energy at all. As each pixel is a tiny lamp, and black pixels are lamps that are turned off, the black levels of OLEDs are better than with LCDs. But because each pixel is a tiny lamp surrounded by circuitry, the total brightness achieved by an OLED display is worse than an LCD that can use a large powerful light behind the screen.

Ink, filters and lamps. That's what powers your mobile displays. Could you have something else? Maybe tiny waveguides that absorb a certain color of light - like the ones on butterfly wings - and have a controllable level of absorption? Something DLP-like where each display pixel is a mirror that either reflects incoming light back towards the viewing surface or away from it?

HTTPS and HTTP2 on Apache2 with Let's Encrypt

This morning I figured I'd set up HTTPS and HTTP2 on my web server. It was pretty easy, too. And man, HTTP2 is fast, especially on silly sites like mine that have a large amount of small images on the page. Good riddance to sprites.

Here's how I set up my Ubuntu Apache2 web server for HTTPS and HTTP2:

For starters, let's get a HTTPS cert. You can get one for free using Let's Encrypt, a non-profit certificate authority from the US. It has an automagical command line tool that creates certs for you and registers them with the CA. It can even automate installation for Apache. Sadly, my Apache config didn't work with the automatic tool, so I had to do it manually. Which wasn't too bad either.

First, I shut down the Apache web server with sudo service apache2 stop. Then, I used the Let's Encrypt client to fetch the cert (this needs to be run on the server pointed to by the domain name):

git clone https://github.com/letsencrypt/letsencrypt
cd letsencrypt
./letsencrypt-auto certonly --standalone -d MY.DOMAIN.NAME

If everything goes well, you should now have the certificate files in /etc/letsencrypt/live/MY.DOMAIN.NAME/. To get HTTPS running, I edited my Apache2 configuration to set up the SSL module and use it for my domain.

<VirtualHost *:443>
  ServerAlias MY.DOMAIN.NAME

  SSLEngine on
  SSLCertificateFile "/etc/letsencrypt/live/MY.DOMAIN.NAME/cert.pem"
  SSLCertificateKeyFile "/etc/letsencrypt/live/MY.DOMAIN.NAME/privkey.pem"
  SSLCertificateChainFile "/etc/letsencrypt/live/MY.DOMAIN.NAME/chain.pem"

...

Ok, HTTPS working. Let's do HTTP2 now. If you haven't yet, you need to upgrade your Apache to version 2.4.17 to get HTTP2 support. Older versions of Ubuntu don't have Apache 2.4.17, so you may need to add a custom PPA to your software sources with sudo add-apt-repository ppa:ondrej/apache2 or such.

After upgrading Apache, turn on the HTTP2 module with sudo a2enmod http2. Almost there! The last step is to turn on HTTP2 on our HTTPS virtual host by adding h2 to the Protocols directive. I also turned on the H2Direct directive, as the description said that it'll spare the server from upgrading a HTTP/1.1 connection if the client starts talking HTTP2.

<VirtualHost *:443>
  ServerAlias MY.DOMAIN.NAME

  SSLEngine on
  SSLCertificateFile "/etc/letsencrypt/live/MY.DOMAIN.NAME/cert.pem"
  SSLCertificateKeyFile "/etc/letsencrypt/live/MY.DOMAIN.NAME/privkey.pem"
  SSLCertificateChainFile "/etc/letsencrypt/live/MY.DOMAIN.NAME/chain.pem"

  Protocols h2 http/1.1
  H2Direct on

...

That's it! Now turn on Apache again with sudo service apache2 start and you should have HTTP2 running. You can check for it in Chrome DevTools by going to the Network pane, right-clicking on the columns header and turning on the Protocol column.

Thanks for reading! Hope this helps you getting your site up and running on HTTP2.