7 ms·

Am I being a pedant if I think this algorithm has been misnamed for the purposes of PR? It just looks like constraint satisfaction. What's quantum about this?

Am I being a pedant if I think this algorithm has been misnamed for the purposes of PR? It just looks like constraint satisfaction. What's quantum about this? There's no constructive/destructive interference, which to my mind is the crucial distinction between quantum and classical systems.

petters 8y ago
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 relaxations something with quantum. I agree that the crucial property of quantum systems is interference, specifically "negative probabilities". Just having a dead/alive ambiguity does not make "wavefunction collapse" a reasonable name.
- 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}
zero_iq 8y ago
It's simply named only for the analogy with the Copenhagen Interpretation -- everything is in a 'superposition' (all options possible) until a single 'observation' is made, which causes a reduction in the available possibilities, which propagates across the space/structure. That's as far as the analogy goes. This sort of loose analogy is a perfectly reasonable way to name things IMHO. I don't hear anyone complaining that bubble sort doesn't consider buoyancy and surface tension, or that the flood fill algorithm doesn't involve any actual fuid dynamics. I have my own theory on why people like to complain about this particular analogy, but for the sake of not causing offence I will leave it there ;p
- pizza 8y ago
  I think people are saying that the algorithm isn't cool enough for its name. Bubbles aren't cool, so bubble sort must be rightly chided. /s Quantum physics? Now that's cool, regardless of how much one knows about it. I don't think the reason gets much deeper than that, barring any disagreements that it is just plain misleading. I guess you could argue to some degree that a name should be usefully informative to an outsider or newbie. But that doesn't really apply to things that have already established their cool factor, like 'deep learning', 'crypto', 'agile', 'serverless', etc..
  - Retra 8y ago
    I would object to the name on the basis of it influencing a misleading association. A person's brain will jump from one idea to the next based on familiar recall, and when people can't 'jump' to the correct association because their brain is filled with bad ideas that have nothing to do with the topic, then we all suffer for having to defend against it.
- dkersten 8y ago
  I’m complaining about it because when I first heard about it, I tried to look up information to understand the algorithm and.. it turns out that “wavefunction collapse” is not useful, at all, as search terms or a starting point to learn anything about this algorithm. The name is completely useless to understanding it or finding out any more about it. You could say the same about bubble sort or whatever, sure, and a case might have been made about the name when it was first introduced, but now they’re established names where “bubble sort” are good search terms that will help you find lots of information about the algorithm, but “Wavefunction collapse” isn’t a widely used algorithm and the name has a lot of existing publications that are not related (because they’re to do with actual quantum physics, not this algorithm). Even searching “wavefunctoin collapse algorithm”, when I last did it, only found quantum physics result (that seems to have changed though, as I just did a google search and the entire first page is about this algorithm, but I see most of the results are quite recent: within the last few months)
amitp 8y ago
I feel the same way. It is constraint satisfaction with a name that gets people's attention. https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf https://adamsmith.as/papers/wfc_is_constraint_solving_in_the...
- GuB-42 8y ago
  Cool names seem to work. Take the Mersenne twister algorithm for instance. It is a non secure pseudo random number generator that is found everywhere even though there are alternatives that are better IMHO. I'm sure it's success comes from the fact that it is good enough and that it has a cool name. I also think it is the rationale behind named vulnerabilities like heartbleed and spectre. Grabs attention.
erikpukinskis 8y ago
I haven’t looked at the algorithm so I can’t comment on your specific question, but I just want to warn you, if the bastardization of wave/particle theory annoys you, you are in for a world of hurt over the next few decades. I believe the notion of waves and their relationship to observations is the new “megameme” for western intellectualism. The progression as I see it: Everything (including us) is a clock/machine Everything (including us) is a computer/information processor Everything (including us) is a wave/field This metaphor will get dragged just as hard as the clock and information metaphors got dragged
KirinDave 8y ago
Hah, I just wrote a similar question. It seems like it's simply an application of a search technique where the constraints are an NxN matrix. It's a good trick, to be sure, but it doesn't seem "quantum". I suppose you could argue that there are often many valid solutions to the system, and you're just selecting a superposition.

petters 8y ago

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 relaxations something with quantum. I agree that the crucial property of quantum systems is interference, specifically "negative probabilities". Just having a dead/alive ambiguity does not make "wavefunction collapse" a reasonable name.

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}

zero_iq 8y ago

It's simply named only for the analogy with the Copenhagen Interpretation -- everything is in a 'superposition' (all options possible) until a single 'observation' is made, which causes a reduction in the available possibilities, which propagates across the space/structure. That's as far as the analogy goes. This sort of loose analogy is a perfectly reasonable way to name things IMHO. I don't hear anyone complaining that bubble sort doesn't consider buoyancy and surface tension, or that the flood fill algorithm doesn't involve any actual fuid dynamics. I have my own theory on why people like to complain about this particular analogy, but for the sake of not causing offence I will leave it there ;p

pizza 8y ago
I think people are saying that the algorithm isn't cool enough for its name. Bubbles aren't cool, so bubble sort must be rightly chided. /s Quantum physics? Now that's cool, regardless of how much one knows about it. I don't think the reason gets much deeper than that, barring any disagreements that it is just plain misleading. I guess you could argue to some degree that a name should be usefully informative to an outsider or newbie. But that doesn't really apply to things that have already established their cool factor, like 'deep learning', 'crypto', 'agile', 'serverless', etc..
- Retra 8y ago
  I would object to the name on the basis of it influencing a misleading association. A person's brain will jump from one idea to the next based on familiar recall, and when people can't 'jump' to the correct association because their brain is filled with bad ideas that have nothing to do with the topic, then we all suffer for having to defend against it.
dkersten 8y ago
I’m complaining about it because when I first heard about it, I tried to look up information to understand the algorithm and.. it turns out that “wavefunction collapse” is not useful, at all, as search terms or a starting point to learn anything about this algorithm. The name is completely useless to understanding it or finding out any more about it. You could say the same about bubble sort or whatever, sure, and a case might have been made about the name when it was first introduced, but now they’re established names where “bubble sort” are good search terms that will help you find lots of information about the algorithm, but “Wavefunction collapse” isn’t a widely used algorithm and the name has a lot of existing publications that are not related (because they’re to do with actual quantum physics, not this algorithm). Even searching “wavefunctoin collapse algorithm”, when I last did it, only found quantum physics result (that seems to have changed though, as I just did a google search and the entire first page is about this algorithm, but I see most of the results are quite recent: within the last few months)

amitp 8y ago

I feel the same way. It is constraint satisfaction with a name that gets people's attention. https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf https://adamsmith.as/papers/wfc_is_constraint_solving_in_the...

GuB-42 8y ago
Cool names seem to work. Take the Mersenne twister algorithm for instance. It is a non secure pseudo random number generator that is found everywhere even though there are alternatives that are better IMHO. I'm sure it's success comes from the fact that it is good enough and that it has a cool name. I also think it is the rationale behind named vulnerabilities like heartbleed and spectre. Grabs attention.

erikpukinskis 8y ago

I haven’t looked at the algorithm so I can’t comment on your specific question, but I just want to warn you, if the bastardization of wave/particle theory annoys you, you are in for a world of hurt over the next few decades. I believe the notion of waves and their relationship to observations is the new “megameme” for western intellectualism. The progression as I see it: Everything (including us) is a clock/machine Everything (including us) is a computer/information processor Everything (including us) is a wave/field This metaphor will get dragged just as hard as the clock and information metaphors got dragged

KirinDave 8y ago

Hah, I just wrote a similar question. It seems like it's simply an application of a search technique where the constraints are an NxN matrix. It's a good trick, to be sure, but it doesn't seem "quantum". I suppose you could argue that there are often many valid solutions to the system, and you're just selecting a superposition.