6 ms·

It is almost comical. But it seems to be working, since it got a lot of attention. I should call my latest paper about finding integer solutions to LP relaxatio

• dkersten 8y ago
  Not only that, but “wavefunction collapse” makes it sound a lot more complex and makes it more daunting to understand. A simple description of the simple tiled model algorithm in the article is basically “pick a candidate at random and prune remaining lists to remove now-invalid candidates” or something similar. Building the rules is simply “list all of the pairs in the example and store how frequently they occur. The frequency count prioritises more common pairs and pairs not encountered in the example can’t occur in the output”. No “quantum” or “wavefunction” or anything here. A list of candidate items isn’t a wavefunciton. When I first saw this technique, I was interested in replicating it. So I started reading about wavefunction collapse on wikipedia. It had a bunch of complex quantum math and I gave up thiniking the technique was beyond me. But now I see it was also completely irrelevant. Thanks to the bad name, I gave up on it (until now, at least, when I see that its a lot simpler).
  • mujina 8y ago
    Yes, it should really just be called "Random Field Collapse" or even just "Random Field Generation". The simple case is a naive way to sample a Markov field in 2 dimensions, estimating transition probabilities from global overall adjacency frequencies.
  • Cybiote 8y ago
    The name is not so bad as you two think. The act of measurement of a quantum state can be thought of as a filtering procedure after which a normalization operation is applied. This is the same protocol that occurs when conditioning on an observation in regular probability. If you take away normalization and stop propagating weights, that same operation corresponds to applied constraints or guards, which trigger backtracking operations, in logic programs for example. This algorithm is actually an instance of constraint propagation: https://en.wikipedia.org/wiki/Local_consistency https://en.wikipedia.org/wiki/Local_consistency and constraint satisfaction algorithms generally, that find use in say, computing graph homomorphisms.
    • dkersten 8y ago
      If it had been called something around constant propagation then I would have had a starting point to learn more when I last attempted to (January or February of this year). Luckily thanks to this article and other recent articles/github projects, it seems that it’s more searchable now than it was then.
• whatshisface 8y ago
  >the crucial property of quantum systems is interference, specifically "negative probabilities". This suggests that it be called "PDF collapse," because it is collapsing a probability distribution function instead of a wavefunction.
  • atq2119 8y ago
    "PDF collapse" is usually known as "random sampling". Of course, random sampling can be quite non-trivial. The Lovasz local lemma comes to mind as something that's similar (but more general) to what the algorithm here achieves. I certainly understand how people can get annoyed by this kind of marketing. Randomized algorithms have a long tradition, including randomized rounding of fractional relaxations which somebody alluded to, and nobody who worked on those felt the need to mislead with quantum allusions.
    • whatshisface 8y ago
      >nobody who worked on those felt the need to mislead with quantum allusions. It may not be fair to the author to allege that they "felt a need to mislead." They might have just been a coder who thought it would be a cool name.
• andrepd 8y ago
  \begin{pedant} Not negative probabilities, but negative probability amplitudes. The former doesn't make sense :) \end{pedant}