FCRC Highlights
By popular request, here are some highlights from this week’s FCRC conference in Portland, Oregon:
- The edit distance between two strings means the minimum number of insertions, deletions, and replacements needed to convert one string to the other: for example, SHTETL and SHETLAND have an edit distance of 4. Edit distance has major, obvious applications to DNA sequence comparison, as well as plagiarism detection and many other things. There’s a clever dynamic programming algorithm to compute the edit distance between two n-bit strings, but it takes ~n2 time, which is already too slow for many applications. Can you do better? I remember wondering about that 15 years ago, as a beginning grad student taking Richard Karp’s computational biology course. Now Arturs Backurs and Piotr Indyk have shown that, if you can compute edit distance in O(n2-ε) time for any ε>0, then you can also solve CNF-SAT in 2cn time for some c<1, thereby refuting the Strong Exponential Time Hypothesis. For more about this important result, see this MIT News article.
- Olivier Temam gave a superb keynote talk about hardware neural networks. His main points were these: implementing neural nets with special-purpose hardware was a faddish idea a few decades ago, but was abandoned once people realized that (a) it didn’t work that great, and (b) more to the point, anything you could do with special-purpose hardware, you could do better and more easily with silicon chips, after waiting just a few years for Moore’s Law to catch up. Today, however, two things have spurred a revival of the idea: firstly, neural nets (renamed “deep learning,” and done with bigger networks and way more training data) are delivering spectacular, state-of-the-art results; and second, transistors have stopped shrinking, so it now makes more sense to think about the few orders-of-magnitude speed improvement that you can get from special-purpose hardware. This would mean organizing computers kind-of, sort-of like the brain is organized, with (for example) memory integrated into the connections between the “neurons” (processing elements), rather than on a separate chip that’s connected to the processor by a bus. On the other hand, Temam also stressed that computer architects shouldn’t slavishly copy the brain: instead, they should simply build the fastest hardware they can to implement the best available machine-learning algorithms, and they should rely on the machine-learning theorists to incorporate whatever broad lessons are to be gleaned from neuroscience (as they’ve done several times in the past).
- Three separate sets of authors (Koppula, Lewko, and Waters; Canetti, Holmgren, Jain, and Vaikuntanathan; and Bitansky, Garg, Lin, Pass, and Telang) independently wrote papers that showed how to achieve “indistinguishability obfuscation” (i.o.) for Turing machines rather than for circuits. For those not in the world of theoretical crypto, i.o. is a hot concept that basically means: obfuscating a program in such a way that no adversary can figure out anything about which program you started with, among all the possible programs that compute the same function in roughly the same amount of time. (On the other hand, the adversary might be able to learn more than she could if merely given a black box for the function. And that’s why this kind of obfuscation falls short of the “gold standard,” which was shown to be impossible in general in seminal work by Barak et al.) Recent papers have shown how to achieve the weaker notion of i.o., but they first require converting your program to a Boolean circuit—something that’s absurdly inefficient in practice, and also has the theoretical drawback of producing an obfuscated program whose size grows, not merely with the size of the original, unobfuscated program, but also with the amount of time the original program is supposed to run for. So, the new work gets around that drawback, by cleverly obfuscating a program whose purpose is to compute the “next step function” of the original program, on data that’s itself encrypted. The talk was delivered in “tag team” format, with one representative from each group of authors speaking for 6-7 minutes. Surprisingly, it worked extremely well.
- Laci Babai gave a truly epic hour-long Knuth Prize lecture, basically trying to summarize all of his work over the past 35 years (and related work by others), in 170 or so slides. The talk had not a single word of filler: it was just pure beef, result after result, some of them well-known and seminal (e.g., MIP=NEXP, AM[2]=AM[k], AlmostNP=MA, group membership in NP, group non-membership in AM…) and others obscure little gems. Boaz Barak commented that an entire semester-long course could be taught from the PowerPoint slides. Laci ended the talk by defining the Babai point, and then saying “having made my point, I’m done.”
- Ambainis (yes, the same Ambainis), Filmus and Le Gall had a paper about the limitations of the techniques used to achieve all matrix multiplication algorithms from Coppersmith-Winograd (O(n2.3755)) onward, including those of Stothers 2010 (O(n2.3730)), Vassilevska Williams 2012 (O(n2.3728642)), and Le Gall 2014 (O(n2.3728639)). Their basic conclusion—not surprising, but still nice to establish formally—is that applying more and more massive computer search to the current ideas can’t possibly get you below O(n2.308); new ideas will be needed to push further.
- At the STOC business meeting, there was a long discussion about the proposal to turn STOC into a weeklong “theory festival,” with more plenary talks (including from other fields), possibly more parallel sessions, etc. There were lots of interesting arguments, but alas, I was too tired and jetlagged to remember what they were. (Anyone who does remember is welcome to chime in.)
There are many great things that I haven’t written about—for example, I haven’t even said a word about any of the three best paper talks!—but I’m out of energy right now. Others are more than welcome to share other FCRC highlights in the comments section.
Follow
Comment #1 June 19th, 2015 at 6:15 pm
For a while I worked at a company that produced specialized hardware for Verilog emulation. They got crushed by Moore’s Law, and gigantic clusters of cheap hardware running Linux. The fascinating part is that I think a piece of hardware that could do that job well would also be able to simulate a neural network well.
It’s odd to think that ten years later, the product that was a failure might now be a big success. But times change.
Comment #2 June 19th, 2015 at 6:37 pm
Here’s an old talk by Ryan Williams regarding other results of the form “If you could improve on the best known algorithm for such-and-such a problem, it would disprove SETH.” Although it seems he is taking it more as evidence against SETH rather than in favor of the optimality of those algorithms!
Also, something seems to have gone missing at the beginning of the following sentence: “i.o., but they first require converting your program to a Boolean circuit…”
Comment #3 June 19th, 2015 at 8:31 pm
Sniffnoy #2,
That’s very interesting, and the fact that Ryan Williams apparently thinks that SETH is false is striking. It makes me very curious what his opinion is about ETH by itself.
The last slide he mentions the idea of trying to find some complexity class collapse that would be triggered by ~ SETH. This raises a question: is there any similar collapse for ~ETH other than classes where one has essentially constructed them to collapse under that hypothesis?
Comment #4 June 20th, 2015 at 3:31 am
@Jay L. Gischer
Do you literally mean the same product? Or a much beefier, scaled up hardware version of the product you had ten years ago?
The problem seems to be that cores are having difficulty getting any faster so people who figured out parallelization (hardware or software) now get the upper hand because the easy option is dying out: just letting the Chip Designer speed up your application by making faster cores.
Comment #5 June 20th, 2015 at 4:04 am
Edit distance is not unlike query complexity in its formulation – it focuses on write operations rather than read operations.
Thinking about it, we could define an analogous edit complexity as the minimum number of operations required to transform an input bit string x into f(x), for some function f.
Whereas query complexity receives a black-box for reading bits, edit complexity would receive a black-box for writing bits.
Then Quantum Computers would make use of interference to set several bits with just one call to the black box by giving it a superposition for the bit index and value.
And randomized algorithms would set bits at random. 🙂
I realize this is absurd, but now i’m curious, would a QC be able to write several bits with just one call to the black box? e.g. a sort of Grover-like algorithm for writing n bits in O(√n).
Comment #6 June 20th, 2015 at 8:48 am
Thx for the stuff!
About the edit distance: suppose two arbitrary DNA sequences differ by 1%, is the complexity about n^2 or about (0.01*n)^2? Suppose we can add some reasonable assumptions (such as: only one path from sequence A to sequence B, or one edit maximum per position). Do you think that would change the picture?
About hardware neural networks: beside the seminal McCulloch&Pitts model, what are the broad lessons from neuroscience that have already been incorporated? Also, isn’t it a bit weird to talk about special-purpose hardware implementing neural nets, without mentionning blue brain or HBP, or to talk about state-of-the-art machine learning, without mentionning random forests?
Comment #7 June 20th, 2015 at 9:26 am
Jay #6:
About the edit distance: suppose two arbitrary DNA sequences differ by 1%, is the complexity about n^2 or about (0.01*n)^2?
That’s an excellent question. But I believe the answer is neither: it’s about 0.01*n2 in the worst case, or n+(0.01*n)2 under some average-case distribution. See this website for more (particularly the discussion of Ukkonen’s algorithm).
About hardware neural networks: beside the seminal McCulloch&Pitts model, what are the broad lessons from neuroscience that have already been incorporated?
I think one of them is organizing a neural net into layers, where the bottom layers are designed to recognize lower-level features (e.g., the Fourier components of your image and boundaries at various angles) and the higher layers then use those to recognize higher-level features. Temam had some more specific examples in his talk, but unfortunately I don’t remember what they were.
isn’t it a bit weird to talk about special-purpose hardware implementing neural nets, without mentionning blue brain or HBP, or to talk about state-of-the-art machine learning, without mentionning random forests?
I believe Temam did discuss all those things in his talk (he certainly discussed the controversy about Markram’s Blue Brain project, with hundreds of neuroscientists considering it a waste of time). My 1-paragraph summary was not a complete account of everything he said!
Comment #8 June 20th, 2015 at 11:07 am
>Ukkonen’s algorithm
Thank you.
>organizing a neural net into layers
Ok yes, indeed, but do you understand the reasoning that we can be confident that all broad lessons have already been incorporated? Topology seems an obvious counterexample of a biological feature interesting to add (Kohonen’s map) and still not within deep learning framework.
>Markram’s Blue Brain project, with hundreds of neuroscientists considering it a waste of time
Of course your 1-paragraph summary could not capture Temam full reasoning, but this mention is enough to suggest he himself despise this project. Do you remember why?
I mean, it’s also my feeling that thousands of neuroscientists don’t give a damn, not only about the HBP, but about anything in computer science in general. What I don’t get is why a computer scientist would despise the HBP (or, more precisely, the computer part of the HBP). Or maybe Temam is a neuroscientist?
Comment #9 June 20th, 2015 at 12:17 pm
do you understand the reasoning that we can be confident that all broad lessons have already been incorporated?
I don’t think we can be confident that all the broad lessons from neuroscience have already been incorporated into machine learning; indeed I’d be astonished if they had been. But Temam wasn’t saying that. All he was saying, was that hardware designers should use machine learning as their intermediary into neuroscience, rather than trying to copy the brain directly.
but this mention is enough to suggest he himself despise this project. Do you remember why?
Actually, I don’t remember Temam taking a strong position either for or against the Blue Brain project. He mostly just discussed the controversy, as part of laying out the current landscape of the field.
Or maybe Temam is a neuroscientist?
No, he’s basically a computer architecture person, with cross-cutting interests in neuroscience and machine learning.
Comment #10 June 20th, 2015 at 12:28 pm
Job #5:
I realize this is absurd, but now i’m curious, would a QC be able to write several bits with just one call to the black box? e.g. a sort of Grover-like algorithm for writing n bits in O(√n).
No, I don’t know of any model of a serial (non-parallel) quantum computer with that kind of capability.
What you can do, is go into a superposition where in the first branch, you write the first bit in memory, in the second branch you write the second bit, and so forth. But then as soon as you measure the memory, you’ll find that only a single, random bit has been written!
Note that reading bits in superposition has the same behavior: if you just measured the QC’s state immediately, you’d find that only a single, random bit had been read. However, Grover’s algorithm lets you use interference to combine all the branches to learn something interesting about the n bits after only O(√n) read operations.
In the same way, there are quantum algorithms (e.g., Ambainis’s element distinctness algorithm) that involve writing to different locations in a quantum memory in superposition. However, the resulting superposition is never useful to measure directly; constructing it is always just one step of setting up a larger interference pattern that will reveal some particular piece of information you wanted.
Comment #11 June 20th, 2015 at 1:23 pm
As referenced in Sniffnoy’s comment #2, there’s a passage in Ryan Williams’ talk “On the Strong Exponential Time Hypothesis (SETH)” that (as it seems to me at least) admirably illuminates the FCRC conference as a whole, and illuminates also Scott’s recently expressed intention that Shtetl Optimized “transcend backgrounds and build a global shtetl”.
The illumination is associated to Williams’ point #3 (of slide 6)
(Point #3 emphasized by me)
Claim The catholicism of William’s Point #3 is broadly and beneficially applicable to many of the findings reported in this years FCRC, specifically by enlarging the STEAM community’s “Overton windows” (to borrow a phrase that Scott has been using here on Shtetl Optimized) for research postulates assessed as credible.
Example John Preskill’s tweet last week “Swingle’s optimism: Ground state properties of naturally arising Hamiltonians are efficiently computable, thanks to ‘s sourcery’” directs our attention to Brian Swingle’s “Area Law for Gapless States from Local Entanglement Thermodynamics” (arXiv:1505.07106), as reported at this month’s Kavli Institute for Theoretical Physics (KITP) Conference “Closing the Entanglement Gap” in Swingle’s talk “How are different ground states in the same phase of matter related? s sourcery“.
Swingle’s talk seeks to enlarge the Overton windows of his Kavli audience as follows
FCRC background Swingle’s Overton-enlarging assertion that “the exponential complexity of Hilbert space can be tamed” makes sense only in the light of computational discoveries, practices and capabilities that are prominently evident at this year’s FCRC: ever-larger clouds of ever-faster, ever-cheaper, ever-more-efficient processors, ever-more-efficient algorithms for foundational computational building-blocks, such as the linear matrix algorithms that “\(\sharp\)” vectors to covectors and “\(\flat\)” them back, and nonlinear extension like Babai point preconditioners.
When we seek to solve real-world \(n\)-DOF problems with \(n\sim 10^{6}\), and FCRC researchers show us how to gain one factor of \(n\) from parallelism and another factor of \(n\) from algorithms, then the resulting speedup \(\sim 10^{12}\) amounts to a transformation from “essentially impossible” to “essentially free”.
Conclusion In regard to last year’s Kalai/Harrow debate regarding the feasibility of scalable quantum computing, this year’s KITP/FCRC research enlarges our Overton window to reasonably accomodate both points of view:
Alternative A (Harrow) Quantum computing is feasible and state-spaces are Hilbert in universes in which all Hamiltonian functions are effectively realizable.
Alternative B (Kalai) Quantum computing is infeasible and state-spaces are effectively less-than-Hilbert in Swingle-type universes whose Hamiltonian functions are restricted to electromagnetic and gravitational interactions.
Unresolved questions Can the idealized Hamiltonian interactions of Nielsen and Chuang’s Quantum Computation and Quantum Information be effectively realized — either in reality or in principle — with technologies that are restricted to the electromagnetic and gravitational interactions that nature supplies? And if we should find that nature’s state-spaces are effectively less-than-Hilbert, can this insight help us to construct a quantum dynamics whose state-spaces are formally less-than-Hilbert?
Conclusion This summer’s KITP and FCRC conferences (and many more) enlarge our Overton windows sufficient to appreciate that the answers “yes” and “no” to the above unresolved questions are equally marvelous.
That’s why there’s never been a more exciting time to be a CT/QIT researcher.
For this ongoing (and oft-times discomfiting) enlargement of our Overton windows, we all of us are indebted to the collegial catholicism of a community of researchers that include the above-mentioned Ryan Williams, John Preskill, Brian Swingle, Aram Harrow, Gil Kalai, and Scott Aaronson … and uncountably many more. For which heart-felt appreciation and gratitude are hereby extended!
Comment #12 June 20th, 2015 at 1:25 pm
Thanks for these clarifications. As a last one, could you clarify what it means that no adversary can figure out one program among all the possible programs that compute the same function? If an adversary could figure out which function you’re computing, but not which particular program you’re using to compute this function, wouldn’t he be fully happy?
Comment #13 June 20th, 2015 at 3:14 pm
Jay #12: Keep in mind that the adversary sees the obfuscated code. So there’s a clear sense in which the adversary obviously, unavoidably “knows” which function you’re computing. Namely, you’re computing whichever function f is defined by that piece of code! 🙂 The adversary can even run the code, to learn the values of f(x) on whichever inputs x she wants.
So we need to be much more careful in defining what we mean by the adversary “not knowing” f. A first attempt at doing that was Barak et al.’s “black-box obfuscation,” which says that the adversary can’t learn anything by examining the code, that she couldn’t also have learned by simply querying a black box that computes f(x) for any given x. Unfortunately, it turns out that there are functions f that are flat-out impossible to obfuscate in that sense (that was Barak et al.’s main theorem).
So, a more relaxed definition is i.o. You can think of i.o. as saying the following: “hide whatever information about f it’s possible to hide, conditioned on my handing someone a piece of code that computes f. Furthermore, do this in an automatic, ‘uniform’ way, which doesn’t require any advance knowledge about which family of f’s I’m dealing with, but simply takes as input an unobfuscated program for f and spits out an obfuscated one in polynomial time.”
Why does i.o. have this interpretation? Well, informally, suppose there exists a program P that efficiently computes f, while hiding some particular piece of information I about f. Then by the very definition of i.o., the adversary can’t tell whether you started with P or with some other program! And therefore, by examining the obfuscated code, the adversary can’t learn I—since if she could, then she could also learn it from P by simulating the obfuscation process, contrary to our assumption.
Comment #14 June 20th, 2015 at 4:42 pm
What about a binary search for the edit distance, bounded by Levenshtein automata? These automata run in linear time in the length of a string but their complexity with respect to the maximum edit distance they accept is terrible. I just don’t know how terrible, because I don’t see a source that states it, because they’re all focused on small edit distances for text search applications. Then again, maybe they’re only focused on that because larger edit distances are so hard to compute.
I can imagine weighting the cut points of the search by the complexity with respect to maximum edit distance, so the cut points are less than half the last bound on each iteration. I can also imagine that weighting being strong enough to make the cut points consecutive integers, eliminating the binary search speedup…
Comment #15 June 20th, 2015 at 5:41 pm
A good example of what i.o. obfuscation is good at is *hiding debug code*. For example, suppose you have this code:
..debug_mode = false
..hash = 0xabf7aad6438836dbe526aa231abde2d0eef74d42
..def validatePassword(password) {
….if debug_mode {
……password=”correct horse battery staple”
….}
….return sha1(password) == hash
..}
If you apply i.o obfuscation to that and ship the result to an attacker, they should be unable to recover “correct horse battery staple” except by breaking the hash or by breaking the i.o. obfuscation scheme.
Comment #16 June 20th, 2015 at 6:03 pm
@Jay
You can’t use quantum to write extra bits per write.
For example, suppose you had a quantum circuit where log(n) bits were used to address which of n counters to increment. You repeat this addressed increment circuit m times, except you’re allowed to do whatever you want to the address qubits before, between, and after the increments (including introducing ancilla bits and measuring).
Before the first addressed increment, the system is in a superposition where the counters are all 0.
After the first addressed increment, the system is in a superposition of basis states, and the counters may differ between the involved basis states, but in all the involved basis states the sum of the counters is 1.
After the second addressed increment, the system is in a superposition where the counters sum up to 2. There may have been interference between the various possible states, but cancelling out some of the cases where the counters summed up to 2 in favor of other cases where the counters summed up to 2 will not change the fact that counters sum up to 2 in very case.
And so on.
So after the m’th addressed increment, the counters may be in some complicated superposition… but the basis states with non-zero amplitude will all have the counters summing up to m.
Therefore when it’s all over and you measure, you’ll find that exactly m increments happened.
I’m pretty sure that if you assumed it was possible to do more than m increments, you could send more than 1 classical bit per qubit without pre-existing entanglement. That would allow you to gain bandwidth by iteratively nesting superdense coding inside of quantum teleportation, allowing arbitrarily large amounts of qubits to be sent by sending only a constant number of qubits.
Comment #17 June 21st, 2015 at 7:10 am
Scott, is there a link to the conference papers? The results about edit distance and i.o seem pretty cool and I wanted to check out the source material.
Thanks!
Comment #18 June 21st, 2015 at 9:30 am
F. Marshall #17: I did put links in my post to the papers I talked about. But you can also get the complete STOC program, with links to the full-text papers, here.
Comment #19 June 21st, 2015 at 10:06 am
Scott, I am curious about obfuscated circuits in a less theoretical sense. The page you linked discussed obfuscating a circuit so that it was impossible to recover the source of the original program, but usually you aren’t interested in recovering the whole source code, but rather to perform some sort of analysis of the source code (for example, to detect malware). Is there any sort of research on what sort of analysis it is possible to “obfuscate away”? You mentioned that it’s not possible to obfuscate away /all/ analysis, but is there more information about what analysis is hard/easy to hide from? In particular I am interested in code-coverage metrics.
I suppose the answer might depend on what sort of overhead you are allowed. Are these theoretical results about practically feasible overheads? What about for practically stealthy-level overheads? (<1x)
Comment #20 June 21st, 2015 at 10:37 am
I should also comment that there seems to be a distinction between the sort of theoretical obfuscation you are discussing and another sort. I feel like the obfuscation you discuss is more like asking the question “is this thing I am measuring really a property of the function I am computing, or just the algorithm I am using to compute it?”
It seems like there might be some properties of the function itself that you want to obfuscate. For example, I could imagine asking about some property of the function that is easy to compute given the smallest/simplest program that computes the function, but could be obfuscated with minimal overhead into a form that it is hard to compute the property.
Comment #21 June 21st, 2015 at 6:56 pm
Jeremy #19, #20: I’m not sure if I understand the distinction you’re getting at. The point of obfuscation is to give someone code that lets them evaluate some function f, as a “black box,” but not give them additional information about f that they could normally get by examining the code.
Having said that, I completely agree with you that the impossibility result of Barak et al., seminal though it was, is extremely far from the last word in practice. In practice, first of all, it’s only particular functionalities that we’d normally want to obfuscate, not arbitrary ones. And even more to the point, we wouldn’t normally have the super-stringent requirement that the adversary learn absolutely nothing beyond what they could learn from black-box access. Rather, as you suggested, there’s probably some particular secret (which might vary depending on the application) that we want the adversary not to learn.
There has been a good deal of work about how to get around the Barak et al. impossibility result by relaxing the assumptions. As an example, see this paper by my former officemate Hoeteck Wee, which shows how to obfuscate point functions (that is, functions that simply recognize a secret password) given powerful enough one-way functions. Or see this quantum money paper by myself and Paul Christiano, where we needed a restricted form of obfuscation for testing membership in a “hidden subspace” (one that didn’t reveal a basis for the subspace), and came up with a candidate way to do it, using low-degree polynomials that happen to vanish on the subspace in question. Or, of course, check out the huge amount of recent work on i.o., which gives you an extremely interesting sort of security guarantee: that, sure, running a program through i.o. might fail to hide some secret about it, but if so, then it wasn’t your fault, because no other way of obfuscating that program would’ve hidden that secret about it either!
Maybe the experts can add some more references.
Comment #22 June 21st, 2015 at 8:49 pm
Thanks for the links, the introductions were well written and you’re right that I was confused about the definition of obfuscation. I think this paragraph from your original post confused me:
>obfuscating a program in such a way that no adversary can figure out anything about which program you started with, among all the possible programs that compute the same function in roughly the same amount of time.
I read this paragraph as saying that it was impossible to pinpoint which original program you started out with, out of the set of programs which compute the same function in roughly the same amount of time.
I think what you meant is that it was only possible to figure out things that were easy to figure out from every member of that set.
Comment #23 June 22nd, 2015 at 9:04 am
Very interesting. In the past, as a physicist I worked on machine learning algorithms implemented in custom chips for HEP applications. Indeed they got crushed by Moore. I have to look into this again if miniaturization is really stopping. GPUs are another rising resource in HEP applications. What about the coupling of GPUs and machine learning algorithms?
Comment #24 June 22nd, 2015 at 9:58 am
Intel’s $16B acquisition this month of the programmable-logic device (PLD) manufacturer Altera is a strong market-indicator that the custom-chip revolution isn’t “really stopping”, but rather has pivoted to PLDs.
Comment #25 June 22nd, 2015 at 11:34 am
@Rahul Verilog emulation, at the core, consists of
1. Bring some bits into memory
2. Perform a simple logical operation on them.
3. Store the result.
This sounds a lot like neural network simulation.
At scale, the hardest problem isn’t making the ALU go faster, it’s getting the bits in the right register at the right time. That is, bandwidth to memory and memory organization/retrieval is the hard part. Most ALU’s at this level kind of starve for data.
I expect neural networks to have the same issues.
Comment #26 June 22nd, 2015 at 12:38 pm
@anon 23
http://www.nvidia.com/object/machine-learning.html
http://arxiv.org/pdf/1404.5997v2.pdf
http://blog.diffbot.com/machine-learning-in-the-cloud/
Comment #27 June 23rd, 2015 at 12:30 am
Jay, John, thanks for the informations!
Comment #28 June 23rd, 2015 at 5:30 pm
Jay #8 says “What I don’t get is why a computer scientist would despise the HBP (or, more precisely, the computer part of the HBP).”
Many neuroscientists and computer scientists hate the HBP for a common reason – it’s a giant waste of a billion euros. The HBP uses huge and expensive hardware to run very large, brain scale simulations. But the circuits they wish to simulate are not known, so they must create them using statistical wiring rules. But the general feeling is that this does not encode enough of how biology does wiring, or learning, or anything else, for any interesting emergent behavior to emerge. So the HBP is unlikely to advance our understanding of how the brain really works.
Likewise the HBP is unlikely to advance computer science. It’s like lots of other large parallel computer setups. And like any other hardware it will be obsolete in a few years.
Basically, it’s like trying to reach the moon by scaling up an Estes rocket until it costs a billion dollars. It’s not going to work and you won’t even learn anything interesting by its failure. You would advance the field a lot more by figuring out first how things should work before scaling up. The opportunity cost that has been squandered by the Blue Brain project is enormous – a significant fraction of the budget of the field as a whole.
Comment #29 June 24th, 2015 at 3:43 pm
Lou Scheffer #28, your true forename is Louis right? Then, you’re exactly the kind of expert I’d love to understand on this topic. Unfortunatly, I can’t say what you gave allows much understanding.
>many scientists hate the HBP.
Many as in ten? hundreds? The fact is thousands of neuroscientists do participate in this project, which implicates more than a “I hate the HBP” public statement. Obviously, talking about the former only is not a mean to be fair, but a mean to say that *you* hate the HBP. Which is fine! That’s why I’d like to understand your opinion in the first place!
> general feeling is that this does not encode enough of how biology does wiring, or learning, or anything else
Really? I doubt this is the general feeling, and I doubt this is the reason for why you hate the project. Indeed, the HBP is not only about simulation, but also about bringing together informations ranging from hard to clinical neuroscience. If that was your true concern, you’d mention it’s only the simulation part that you despise, right?
> the HBP is unlikely to advance computer science.
I suspect you’re completly right on this (except for some engineering aspects, arguably minor ones). But did anyone ever pretend otherwise?
>The opportunity cost that has been squandered by the Blue Brain project is enormous
I guess this is the true reason, e.g. that you think you could have done better. Which is also why I’m so interested reading your opinion. What project would you start with 1 billion euros?
Also, the HBP is a european project, meaning you’d have at best seed money or partenership from it. What is your opinion about the BRAIN initiative?
Comment #30 June 24th, 2015 at 6:03 pm
Jay #29: Yes, I’m a computer- and neuro- scientist, so perhaps qualified to comment on this.
The objections to the HBP have been discussed in more detail and more clearly than my quick summary. See
http://news.sciencemag.org/brain-behavior/2014/07/updated-european-neuroscientists-revolt-against-e-u-s-human-brain-project
or
http://news.sciencemag.org/brain-behavior/2015/03/europe-s-human-brain-project-needs-urgent-reforms-panel-says
Here is the letter (http://www.neurofuture.eu/ ) submitted to the EU requesting changes in the HBP to address these problems. It has 811 signatures so far. This is only the tip of the iceberg since it’s risky, particularly for non-senior scientists, to criticize in writing both senior figures in the field and a funding organization. That so many are willing to make such a potentially career limiting step says a lot.
Comment #31 June 24th, 2015 at 6:59 pm
Jay #29: To answer your other questions, I’m a USA researcher and hence not directly affected whether the HBP comes or goes. But there are lots of European labs that could use the support that is now going to HBP, and do with the same money research that I think would be far more helpful in the long run. It’s this waste that bugs me.
The BRAIN initiative is organized much better, with a panel of senior folks asked what is needed to advance the field as a whole. They decided to start with circuit understanding and measurement technologies. This is stuff we desperately need *before* we spend a lot of money doing large scale simulation. The main topics they are funding to start with ( http://braininitiative.nih.gov/nih-brain-awards.htm ):
* Census of Cell Types
* Tools for Cells and Circuits
* Next Generation Human Imaging
* Large-Scale Recording-Modulation – New Technologies
* Large-Scale Recording-Modulation – Optimization
* Understanding Neural Circuits
Conversely, how can you justify large-scale simulation when these topics still need considerable basic research?
Comment #32 June 25th, 2015 at 6:49 am
Although the roadmaps of the european Human Brain Project (HBP) and the north american BRAIN initiative are very different, it is entirely reasonable to foresee that both roadmaps will be greatly strengthened by the other roadmap.
In other words, if the optimal brain-research strategy is a mixed strategy, then the question “Which strategy is right, HBP or BRAIN?” is fundamentally misguided.
Lessons from the human genome project Early criticism of the Human Genome Project (HGP) centered upon the transgressive reality that the HGP was not hypothesis-centric. This criticism proved unfounded: as the genomic data-rate accelerated, the net result was more hypotheses tested, not fewer. What the initial HGP roadmap overlooked was instead the sustained more-than-Moore improvement in technical sequencing capacity, which has driven a golden age of algorithmic advances in genomics.
BRAIN/HGP criticism The culture of wet-bench biology research has been irretrievably altered by these advances … not necessarily for the better, many now say. A forcible criticism is that the achieved radical advances in genomic instrumentation and genomic mathematics has not fostered a golden era of career opportunities for young genome-science researchers.
Implications for BRAIN/HGP It’s entirely reasonable to foresee that BRAIN/HGP is laying the foundations for similar success to the HGP. Namely, BRAIN’s great success in coming decades will be (hopefully) sustained more-than-Moore improvement in technical neuron-observing capacity, while HGP’s great success will be (hopefully) a golden age of algorithmic advances in neuro-simulation.
BRAIN/HBP apprehensions The culture of cognitive research will be irretrievably altered by these advances … not necessarily for the better, many foresee. A forcible criticism is that the foreseen radical advances in brain instrumentation and brain mathematics may not foster a golden era of career opportunities for young brain-science researchers.
Comment #33 June 25th, 2015 at 7:01 am
#30 The objections to the HBP have been discussed
Sorrry but no, it have not been discussed there. This petition was because last year Markram (and a majority of the board) decided to eliminate cognitive science from the HBP. We were pissed, and now we’re glad the petition reached it’s primary goal to get cognitive science back. But it’s sad this petition became a pretext for HBP haters.
#30 a potentially career limiting step
Cognitive scientists would put their carreer at risk denouncing their whole field was fired. Really?
Comment #34 June 25th, 2015 at 7:10 am
#31 This is stuff we desperately need *before* we spend a lot of money doing large scale simulation.
So you would be happy if only the HPB would include things such as:
– to generate data to complete existing data on the structure of the mouse brain
– to generate multi-level data for humans that parallels the data collected for mouse
– to identify the cognitive architecture of the human brain during selected tasks using functionnal neuroimagery
-to federate clinical data, including genetics and imaging, currently locked in hospital and research archives
-…
https://www.humanbrainproject.eu/discover/the-project/subprojects
Comment #35 June 25th, 2015 at 7:14 am
#31 how can you justify large-scale simulation when these topics still need considerable basic research?
More on that later, including critics of the BRAIN that would put my career at risk once the NSA will find my true name.
Comment #36 June 26th, 2015 at 9:08 am
So, how can I justify large-scale simulation when all information is not available? Simply, because we need it!
There are many properties that we don’t know if it comes from large-scale behavior of known properties, or if it comes from presently unknown basics features. As an example, two hot topics are gamma waves as NCC and large scale synchronisation. But where do these properties come from? Is it something we automatically gain from with large-scale neural nets? Or does it requiere some wiring principles? Or some specifics neurotransmitters? Of course we could gain some of this information from animal models, and we will, but the cost is huge, the pace very low, and it’ll be next to impossible for most of what is specific to humans. Or we can play with numeric models and systematically detect not only what features are necessary, but also what we should suspect from artificial modifications (for example, using TMS, tDCS or various pharmocological interventions), and then test the most interesting ones. So, to make a long story short, large-scale simulations are necessary because it’s a basic tool, and a very efficient one. That’s not to say experiments are not necessary. That’s to say all other experimental tools will becomes far more powerfull once we would be able to guide experiments with computational models.
But there’s more. Simulation is not only a tool, or a power-enhancing tool, it’s also a mean to bring data together. And this is the main difference between the BRAIN project and the HBP. The philosophy behind the HBP is to bring very different information altogether, from basic neurosciences to clinical information. This is in sharp constrat with the BRAIN project, which look like a list “à la Prévert” for which the aim seems “give at least a piece of something to any single big shot anywhere in the USA”. That’s not to say there’s no interesting projects. To the contrary, one can spend several hours reading many different and very exciting projects. But after a while, you stop and you still have no idea what the BRAIN project is about, because all these projects have actually not too much in common, and it’s not clear how we could see the big picture from them. Of course, it could be that it’s the best approach, but I’m glad we’ll be able to comparr which of these two strategy will be the most fruitfull, and if it’ll be possible to get synergies from these two approaches. Exciting times!
Comment #37 June 27th, 2015 at 7:01 am
I don’t think the complexity of edit distance is very well understood in general (and similarly it is quite plausible that the SETH is false). As examples a) as far as I know the quantum complexity of edit distance is very much open (is there any known speedup at all over the best classic algorithms?) b) I don’t think it is known if edit distance is in log space which seems like a very basic question to me and c) slightly tangentially but I think also intriguingly, it turns out that the cell probe complexity of *online* edit distance is O(log^2 n) http://arxiv.org/abs/1407.6559 ,
All this points to our general ignorance on this topic I feel.