5 ms·

Universal function approximator == universal function approximator

• eru 3y ago
  Turing machines can also be used as universal function approximators. But I'm not sure it makes sense to put them in the same category as the other two.
  • bjornsing 3y ago
    I would love to put them in the same category as the other two. In fact I’ve spent quite a lot if time thinking about it / experimenting. Wouldn’t it be great if we could somehow train on data and get a small Turing machine instead of a huge neural network?
    • moffkalast 3y ago
      I would expect it to result in a large and slow Turing machine instead of a small neural network.
      • ethbr1 3y ago
        So far, betting on RISC over CISC in terms of ultimate hardware performance has been a good bet.
        • eru 3y ago
          Both RISC and CISC are usually used in the context of describing Turing complete instruction sets. I'm not sure, it's relevant here? If you want to make a comparison in this flavour: Turing machines are a bit like CPUs in that they can execute arbitrary things in sequence. All the flavours of machine learning are more like GPUs: they do well with oodles of big, parallelisable matrix multiplications interspersed with some simple non-linear transformations.
      • sgt101 3y ago
        These words, I do not think that they mean what you hope they will mean.
        • moffkalast 3y ago
          Well we're talking about a "native" implementation of both for comparison, right? Neural nets as they're being used are just being emulated by our turing-machine-like processors which makes them run like ass in practice. Something like an analog circuit that adds up voltages would be a native NN implementation and would surely vastly outperform any turing machine in wide highly parallel super highly memory driven tasks that are well suited for it, and either emulating the other is slow and bloated.
• westurner 3y ago
  Universal approximation theorem: https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore... NAND is a universal logic gate; from which all classical functions can be approximated. CCNOT and Hadamard are universal logic gates with which all (?) quantum functions/transforms can be approximated.
  • soVeryTired 3y ago
    Cubic splines are universal function approximators. As is piecewise linear interpolation. The universal function approximator thing is way overblown.
    • westurner 3y ago
      FFT describes everything with sinusoids by default. For QFT, it's wave functions. Wavelets are more like NN neurons that match (scale-invariant?) quantized sections of waveforms. Fluids are decomposed into things with curl. A classical universal function approximator is probably not sufficient to approximate quantum systems [...] https://news.ycombinator.com/item?id=37379123 https://news.ycombinator.com/item?id=37379123
  • vcxy 3y ago
    > CCNOT and Hadamard are universal logic gates with which all (?) quantum functions/transforms can be approximated. CNOT, H, S, and T are universal for approximating any quantum operation.
    • westurner 3y ago
      A classical universal function approximator is probably not sufficient to approximate quantum systems (unless there is IDK a geometric breakthrough in classical-quantum correspondence similar to the Amplituhedron). IIUC Church-Turing and Church-Turing-Deutsch say that Turing complete is enough for classical computing, and that a qubit computer can simulate the same quantum logic circuits as any qudit or qutrit computer; but is it ever shown that Quantum Logic is indeed the correct and sufficient logic for propositional calculus and also for all physical systems? From "Quantum logic gate > Universal quantum gates": https://en.wikipedia.org/wiki/Quantum_logic_gate#Universal_quantum_gates https://en.wikipedia.org/wiki/Quantum_logic_gate#Universal_q... : > Some universal quantum gate sets include: > - The rotation operators Rx(θ), Ry(θ), Rz(θ), the phase shift gate P(φ)[c] and CNOT are commonly used to form a universal quantum gate set. > - The Clifford set {CNOT, H, S} + T gate. The Clifford set alone is not a universal quantum gate set, as it can be efficiently simulated classically according to the Gottesman–Knill theorem. > - The Toffoli gate + Hadamard gate.[17] The Toffoli gate alone forms a set of universal gates for reversible boolean algebraic logic circuits which encompasses all classical computation. [...] > - The parametrized three-qubit Deutsch gate D(θ) > A universal logic gate for reversible classical computing, the Toffoli gate, is reducible to the Deutsch gate, D(π/2), thus showing that all reversible classical logic operations can be performed on a universal quantum computer. CCNOT: https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Quantum_logic_gate#Toffoli_(CCNOT)_gate https://en.wikipedia.org/wiki/Quantum_logic_gate#Toffoli_(CC... CNOT: https://en.wikipedia.org/wiki/Controlled_NOT_gate https://en.wikipedia.org/wiki/Controlled_NOT_gate H: https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_gate https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_ga... S: https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift_gates https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift... T: https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift_gates https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift... Implicit to a quantum approximator would be at least Quantum statistical mechanics and maybe also Quantum logic: Quantum statistical mechanics: https://en.wikipedia.org/wiki/Quantum_statistical_mechanics https://en.wikipedia.org/wiki/Quantum_statistical_mechanics Quantum logic: https://en.wikipedia.org/wiki/Quantum_logic https://en.wikipedia.org/wiki/Quantum_logic
• quickthrower2 3y ago
  Depends which valley it chooses to die on
  • sgt101 3y ago
    Yup - and that's the big question for ML... "which valley will this algorithm die on" so far I haven't seen an answer.
• deleted 3y ago
  [deleted]