Jon, hi and thank you, So, I am not going to be knowledgeable or sophisticated enough to have a conversation with you as an equal on computational complexity classes and algorithms. I can tell you what I was hoping to take from Valiant, on the assumption that it is compatible with the current best understanding of complexity classification of problems. If I say things that, through lack of technical understanding, stand for qualitatively wrong assertions, please correct if you are willing to.
I guess there are topics here that could be discussed partly disconnected, and then I have to recall why I brought them up together. I’ll start with the disconnected. > On Apr 27, 2021, at 1:46 PM, jon zingale <jonzing...@gmail.com> wrote: > > """ > I like what Leslie Valiant has to say in PAC, as a way of framing the issues, > even though I know he is a punching bag for the geneticists because of > various things they understand as important that he isn’t trying to > understand deeply or deal with. I don’t care that he had limitations; the > question for me is whether there is a good insight that could be developed > further. > What I intend to suggest above is that the lifecycle/hypergraph abstraction > is a more expressive class of formal models within which one can pose such > problems, and we should be able to generate more interesting answers by using > it. > """ > > There are many references above to investigate, and so far I have only begun > to engage with some. I am preparing to read your preprint > <https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fwww.biorxiv.org%2fcontent%2f10.1101%2f2021.02.09.430402v1.abstract&c=E,1,foihSOKMNjET5mL6M9KzZCqr7_tWNPHgzI_3sofGRZE3UxKmoRdLNguZdgA2o0YYjmnbpPuE0vsOrBhH0QlvNngq3GhSBTMe6p0YpXqBZUcW2P15CalIfw,,&typo=1>, > and I have managed to track down a copy of Valiant's PAC. Two notable ideas > Valiant raises are: > > > 0. Membership to a complexity class as real: A machine is identified with the > nature of its computation and not necessarily the fine details of its > instantiation. For instance, fine details in the case of biology could be > every aspect of its being in the world. I am reminded of the philosophical > problems associated with identity tracing, as well as a certain empiricist > perspective that days like today are in some sense more real than today. > Valiant mentions that the universality of Turing's machine is the stable > feature that ultimately matters, that a machine ought to be considered "the > same" under perturbation of its parts so long as what it does computationally > remains invariant. > The slipperiness of notions like "remaining computationally invariant" and > "perturbation of its parts" seem to be hotly debatable locales. In the spirit > of Ackley's robust algorithms, perturbations of a quick-sort rapidly lead to > nonviable algorithms, while bubble-sort can remain identifiable under > significant perturbation. Additionally, as with genetics, there is the > possibility of identifying perturbations (mutations) as an indispensable part > of the organism. This kind of analysis does leave some questions open. Should > we (by the thesis) consider a BPP-classed algorithm to be the same under > perturbation when it becomes both determined and its expected time complexity > remains invariant? > For definiteness, I will have in mind some problem class with constant structural description and a scaling variable, such as 3-sat, that is NP. I understand that classification to mean that, over all ordinary discrete-step solution algorithms with some bound on their parallelism in relation to the system size, no algorithm will certainly find a solution to an arbitrary instance with a time cost in a smaller class than exhaustive elaboration — meaning exponential in the problem size (even if the exponent is smaller than exhaustive elaboration). Compare that then to some other problem class that is simpler, P or some sufficiently low order polynomial, or whatever. What I hear Valiant trying to get at with his “learnable” functions is an assertion about how reinforcement learning can either produce a solution or contradiction itself to an arbitrary instance, or somehow be mapped to or select an algorithm that can do that. I understand his claim to be that, if the problem class is of sufficiently low complexity, reinforcement can obtain solutions almost-surely within some time bound, but if the problem is NP, reinforcement cannot (directly, or by way of selecting some implementation of an algorithm), produce solutions. I am not sure I know “precisely" what the claim is. Of course it could not produce a solution in less than exponential time cost, by the stipulation that the problem is NP. So to be saying that the problem is not “learnable”, I assume Valiant is asserting that reinforcement could not arrive at a solution almost-surely, at all. I’m not sure, even if the above is okay to say, it makes claims about how any given algorithm will hold up under perturbation of its steps or rules. I have assumed these complexity classes are frontiers that cannot be surpassed. But any given instantiation of any given solution, if disassembled and re-arranged, presumably yields another function that is simply of a different kind, which could be far behind the frontier. So in your comment I seem to see two topics: about the limiting performance over all solutions, and about robustness characteristics of any particular solution, relevant (?) in different contexts? > 1. Scaffolding in protein expression networks: Here, Valiant suggests a > protein level analogy to Nick's white smokers. Chaperone proteins > <https://en.wikipedia.org/wiki/Chaperone_(protein)>, at the very least, are > known to participate structurally in the process of error correction, namely > correcting errors in folding. I am reminded of recent dives into other > aspects of protein dynamics such as allosteric signaling > <https://en.wikipedia.org/wiki/Allosteric_regulation>. I can only imagine the > computational liberties present for scaffolding when considering variation in > PH (as narrow as it allows) or temperature. In these musings, I am reminded > of the inhibitory (epiphenomenal?) role of the dictionary in the functioning > of LZW data compression. > The concept of scaffolding seems to be extremely fertile, and is closer in a recognizable way to the _very small_ thing I was trying to do within that paper. I happen to be re-activated on scaffolding for various other reasons that I won’t digress on here. The connection would be that, to understand the questions about memory and selection that genetics wants to ask, you would need to judiciously include aspects of “what genes do” — together with each other — into your abstraction for what a system’s states and transition rules are. That was what the hypergraph formulation was meant to support. I will mention, however, that the anecdotes of response to COVID vaccines have me thinking that, in a different life, I could have greatly enjoyed researching sex differences in immune response. Immune response in people is such an exceeding tangle of components, accreted over deep time, with very complex interplays, and many of them set fo a quantitative trade-off between sensitivity and aggressiveness of protection, against noise-suppression and avoidance of self-harm. How the regulation of that system should somehow be co-tangled with the other complex regulations of sex difference — how much comes from components on the sex-determining chromosomes, versus how much is systemically modulated by long pathways that are only sex-linked very indirectly — would be a perfect challenge to “complexity” science. I have thought, anecdotally, of women’s immune responses as being, modestly but significantly, more sensitive and better regulated than men's, but the spectrum of responses turns out to be a quagmire. See https://apps.who.int/iris/bitstream/10665/44401/1/9789241500111_eng.pdf <https://apps.who.int/iris/bitstream/10665/44401/1/9789241500111_eng.pdf> (e.g. p.39). Yet this seems to trade off against increased incidence of some common autoimmune diseases such as lupus and MS, in women. How does one understand the vast complexity of selective forces and developmental commitments that result in these simple blunt statistics? But back to your question. I agree. The fact that we _have_ chromosomes, and _have_ ontogenetic and developmental regulatory sequences; that there even are categorical functions that identify “genes” within which variation creates “alleles”, is the ultimate scaffolding. Because I have to deal with RNA-World Origin of Lifers all the time, to whom everything is just a point-set of 1-off atoms of function carried on short RNA segments, I am sensitive to the enormous gulf between the model they put forth for the world, and what life became by the time it became “genomic” per se. To very material-literalist minds, there is no question here: molecules just get longer and the number of things linked by covalent bonds increases. There isn’t really even a word for the defined sequence of gene interactions in unicells — “development” as a technical term is meant to refer to the regulatory sequences governing multicellularity. But to me, the emergence of defined “roles” in a choreographed cell-building “program” is _the_ interesting thing to understand about the integration of fragmentary functional molecules. Multicellular development is then just an elaboration on that theme after various other architectural transitions (the stuff Chris Kempes does so well with Tori Hoelher and others). This, I think, is where I connect back to Valiant. My intuition is that the “bag of genes / bag of functions” paradigm of the RNA-Worlders becomes something that selection can no longer impose any sense on, already at fairly small bags. If Leslie is right, then compared to the set of all possible bags and all function composition combinations they could hold, the set of things selection can ever impose sense on becomes vanishingly small as the bags get large, as small as P < NP. Merely-linked gene fragments in a macromolecule might be the bags, or cells might be. If that intuition is valid, then the only things selection could ever rescue from chaos become those that get canalized into these ur-developmental “programs”, with defined roles for genes, and merely allelic variation within each role. I would like to find a formal way to frame that assertion as a question and then solve it. > That Glen found your paper "positively pornographic" is high praise. I hope > to find the time to take the dive myself. In the meantime, I would love to > hear more about your ideas concerning graphical models, as it is a place I > have thought a bit about. > I don’t think I said this in the early email to Nick and then Glen, but the place where I see my interest taking a coherent form is a bit to the side of the small and particular thing in this paper. There is a broad class of phenomena that can be abstracted in what I have taken to calling “3-level systems”, by which I mean the following: 1. Level 1 are “rules” in the way the rule-based systems people use the term. They could be reaction _mechanisms_ in graph-grammar chemistry, or site-rewrite rules in Walter Fontana’s site-graph abstractions for systems bio. The rules have an algebra of dependencies, and category theory seems to be a good language for talking about how these can be embedded in contexts in a structure-preserving way. Vincent Danos, Walter Fontana, and that whole crowd, and recently Nicolas Behr, as well as the MOD group are my go-to experts on this. 2. Level 2 are the “generators” of stochastic processes in a conventional sense. They consist of contexts for the rules, and of transformations. In a sense, they are “generated by” the rules (but they will “generate” a stochastic process in the level below them). So reaction mechanisms from level 1, represented as graph-fragment rewrites, can act on a few starting molecules to produce an expanding set of actual, whole molecules, and the reactions that interconvert them. Or for site graphs, rules, acting on any state of some protein type, can produce all the possible configurations. The natural representation for these systems (at least for chemistry) is the hypergraph. There is still an algebra of operation of reactions, but it is simpler than the algebra of rules, and mostly about counting. 3. Level 3 is then the state space, in which states are things like counts of all the possible species. So the state space is just a lattice. The “generator” from Level 2 is the generator of stochastic processes over this state space, and it is where probability distributions live. I like these systems because a finite collection at any level can generate an indefinitely or infinitely large collection in the level below it. So finitely many reaction mechanisms can generate an infinitely large hypergraph (the formose network or the HCN polymerization network). Likewise, even a finite hypergraph can govern probability flows for indefinitely many particles, which is where mass-action chemistry and the classical world come from. To return to your specific question: my interest is less in graphical models, as a class, than in the relation of these three levels of mathematical objects and how compactly encoded order at one level can govern cryptic but essential order in the level below it. (Related to what makes a problem solvable, so back to the beginning.) The hypergraph, at level 2, is interesting in its own right just because it is a generator of powerful and complex processes, and can be used to describe lots of stuff both expressively and yet analyzably. If I could be doing this for a living, I would be. Btw., Andres Ortiz-Munoz at SFI is a maven of the rule-based world. Artemy Kolchinsky is a maven of non-equilibrium stochastics. I keep hoping the two of them will notice something really original to do together. All best, Eric > Sent from the Friam mailing list archive <http://friam.471366.n2.nabble.com/> > at Nabble.com. > - .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. . > FRIAM Applied Complexity Group listserv > Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam > un/subscribe > https://linkprotect.cudasvc.com/url?a=http%3a%2f%2fredfish.com%2fmailman%2flistinfo%2ffriam_redfish.com&c=E,1,arNQ1xa21cEjpmLsaFg2pYtH8EW6maRKN7ak6QagEmQp3QRgdzvjrwoAO_p2dpuavz-uKWGGXUl4FtjL71BEXldfrZwUbsGwDdjASGN48fTBWT2w&typo=1 > FRIAM-COMIC > https://linkprotect.cudasvc.com/url?a=http%3a%2f%2ffriam-comic.blogspot.com%2f&c=E,1,xRhp_47731lCYlnSAtkmAB3CpINrmebV9BsiDOvIvB3QLx860XD6I2GngdHXQxiA3vLo8uVWkBd7MTFokuoFREkDyby4ss7X4Om8pcxHtvWtwTLgsasvncyklxQ,&typo=1 > archives: http://friam.471366.n2.nabble.com/
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. . FRIAM Applied Complexity Group listserv Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com FRIAM-COMIC http://friam-comic.blogspot.com/ archives: http://friam.471366.n2.nabble.com/
