Hacker News Reader

Comment by Footnote7341 | Hacker News Reader

When did we start calling markov chains 'wave function collapse'?

Several years before it became fashionable to dismiss everything as a Makov chain.

Given a simple history can be mapped into a higher dimensional state, Markov chains are much more common than they first seem, so it's basically* always possible to dismiss any physically implementable system as "a Markov chain" if you're so inclined.

* While I wouldn't be surprised if someone has come up with laws of physics that can't be described by a Markov chain, mere quantum mechanics can.

Why would analyzing something as Markov chain be dismissing it? Perhaps its Markov chains that are being dismissed?

The comment I am replying to looks like a dismissal, and does not look like an analysis.

Quantum mechanics can be described as a Markov chain? That seems plausible but I haven't worked with MCs enough to see exactly how. Could you please elaborate? It seems interesting.

If you want to study a quantum mechanical system in equilibrium at inverse temperature β, the interesting quantity is the partition function Z = tr exp[-β H]. This can be converted into a path integral Z = ∫ dφ exp[-S[φ]] which can be importance-sampled via the Metropolis-Hastings algorithm [mh] via Markov-chain Monte Carlo.

This approach is commonly used in lattice field theory [lft], where the Hamiltonian H is that of a discretized spacetime (or the problem is formulated in terms of the action S to begin with).

Real-time problems in quantum mechanics involve exp[i t H] which brings a horrible complication called the sign problem [sign]. The one-sentence summary is that exp[-β H] is positive-definite but exp[i t H] is not and it's not clear how to incorporate a complex Boltzmann weight as a probability for MCMC.

mh: https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_al...

lft: https://en.wikipedia.org/wiki/Lattice_field_theory

sign: https://en.wikipedia.org/wiki/Numerical_sign_problem

A Markov process is a random process where the new state only depends on the old state, not anything else. This can be stretched to include almost anything, since you can expand the definition of the state to record history or whatever you want, although you may make the process much more difficult to work with mathematically. In other words, the fact that something may be a Markov process is generally not interesting, because it is a very broad definition, and doesn't guarantee any interesting properties without further assumptions.

The wavefunction in QM doesn't evolve randomly, so I would say it is not technically a Markov process. On the other hand you can create a theory of observables derived from QM that is "random" (depending on your interpretation of quantum mechanics).

You will have a hard time constructing Markov Chain that correctly models the real-time evolution of physical quantum-mechanical observables. The problem is that the transition matrix that governs quantum-mechanical evolution is exp[i t H], which is not a well-formed probability distribution.

I would have said something very close to zeofig's answer, with the one significant change being to say that a deterministic system is itself a very boring kind of Markov chain where all states' transition probabilities are exactly 0 or 1.

The "wave function collapse" part comes from the original algorithm which inferred the constraints from a sample image : https://github.com/mxgmn/WaveFunctionCollapse

Still a misnomer in my opinion, but I noticed that this part of the algorithm was missing from all the articles that followed (mine included). People are basically implementing sudoku solvers :)

Since people started using marketing tactics to promote themselves. WFC is a $100 name for a $1 concept. Other entries in the tech hall of shame are mersenne twister and dependency injection

Like calling random vector functional link networks and single-layer feed-forward networks with random hidden weight an "Extreme Learning Machine".

https://en.wikipedia.org/wiki/Extreme_learning_machine#Contr...

>Controversy

>There are two main complaints from academic community concerning this work, the first one is about "reinventing and ignoring previous ideas", the second one is about "improper naming and popularizing", as shown in some debates in 2008 and 2015.[33] In particular, it was pointed out in a letter[34] to the editor of IEEE Transactions on Neural Networks that the idea of using a hidden layer connected to the inputs by random untrained weights was already suggested in the original papers on RBF networks in the late 1980s; Guang-Bin Huang replied by pointing out subtle differences.[35] In a 2015 paper,[1] Huang responded to complaints about his invention of the name ELM for already-existing methods, complaining of "very negative and unhelpful comments on ELM in neither academic nor professional manner due to various reasons and intentions" and an "irresponsible anonymous attack which intends to destroy harmony research environment", arguing that his work "provides a unifying learning platform" for various types of neural nets,[1] including hierarchical structured ELM.[28] In 2015, Huang also gave a formal rebuttal to what he considered as "malign and attack."[36] Recent research replaces the random weights with constrained random weights.[6][37]

But at least it's easier to say, rolls off the tongue smoothly, and makes better click bait for awesome blog postings!

I also love how the cool buzzwords "Reservoir Computing" and "Liquid State Machines" sounds like such deep stuff.

https://news.ycombinator.com/item?id=40903302

>"I'll tell you why it's not a scam, in my opinion: Tide goes in, tide goes out, never a miscommunication." -Bill O'Reilly

How about rebranding WFC as "Extreme Liquid Quantum Sudoko Machines"? ;)

Then there's "Crab Computing"!

https://news.ycombinator.com/item?id=42701560

[...] If billiard balls aren't creepy enough for you, live soldier crabs of the species Mictyris guinotae can be used in place of the billiard balls.

https://www.newscientist.com/blogs/onepercent/2012/04/resear...

https://www.wired.com/2012/04/soldier-crabs/

http://www.complex-systems.com/abstracts/v20_i02_a02.html

Robust Soldier Crab Ball Gate

Yukio-Pegio Gunji, Yuta Nishiyama. Department of Earth and Planetary Sciences, Kobe University, Kobe 657-8501, Japan.

Andrew Adamatzky. Unconventional Computing Centre. University of the West of England, Bristol, United Kingdom.

Abstract

Soldier crabs Mictyris guinotae exhibit pronounced swarming behavior. Swarms of the crabs are tolerant of perturbations. In computer models and laboratory experiments we demonstrate that swarms of soldier crabs can implement logical gates when placed in a geometrically constrained environment.

https://www.futilitycloset.com/2017/02/26/crab-computing/

What would be a better name?

Constraint-based tiling maybe?

Permutation City with a nod to Egan?

WFC in particular wasn't even new. The exact same thing was published by someone else before. I don't know if he gave it a name though

The difference between Deepak Chopra's abuse of Quantum Physics terminology and WFC's is that WFC actually works and is useful for something, and its coiner publishes his results for free as open source software and papers, so he deserves more poetic license than a pretentious new-age shill hawking books and promises of immortality for cash like Deepak.

Here are some notes I wrote and links I found when researching WFC (which is admittedly a catchier name than "Variable State Independent Decaying Sum (VSIDS) branching heuristics in conflict-driven clause-learning (CDCL) Boolean satisfiability (SAT) solvers"):

https://donhopkins.com/home/wfc-notes.txt

    Here are some notes I wrote and links I found when researching Wave
    Function Collapse (WFC). -Don Hopkins

    Wave Function Collapse

    Maxim Gumin

    Paul Merrell

    https://paulmerrell.org/research/

    https://paulmerrell.org/model-synthesis/

    Liang et al

    Jia Hui Liang, Vijay Ganesh, Ed Zulkoski, Atulan Zaman, and
    Krzysztof Czarnecki. 2015. Understanding VSIDS branching heuristics
    in conflict-driven clauselearning SAT solvers. In Haifa Verification
    Conference. Springer, 225–241.

    WaveFunctionCollapse is constraint solving in the wild

    https://escholarship.org/content/qt1f29235t/qt1f29235t.pdf?t=qwp94i

    Constraint Satisfaction Problem (CSP)
    Machine Learning (ML)

[...lots more stuff...]

AFAIU WFC is not a Markov chain. See here:

https://escholarship.org/uc/item/1fb9k44q

It splits an image to cells by using convolutions, derives a set of constraints of how cells can be combined and then generates combinations that satisfy the constraints. It's a form of machine learning based on combinatorial optimisation, really.

Far as I can tell it doesn't apply any Markov assumptions anywhere, but I might just not have noticed it so please prove me wrong on that one.

Reply on news.ycombinator.com