For me, it was "Erasure Coding in Windows Azure Storage" from Microsoft Research (2016) [0]
The idea that you can achieve the same practical effect of a 3x replication factor in a distributed system, but only increasing the cost of data storage by 1.6x, by leveraging some clever information theory tricks is mind bending to me.
If you're operating a large Ceph cluster, or you're Google/Amazon/Microsoft and you're running GCS/S3/ABS, if you needed 50PB HDDs before, you only need 27PB now (if implementing this).
The cost savings, and environmental impact reduction that this allows for are truly enormous, I'm surprised how little attention this paper has gotten in the wild.
The Google File System (GFS) paper from 2003 mentions erasure codes. Which isn't to say they did it then, but rather that the technique of using erasure coding was known back then.
(And surely before GFS too, I just picked it as an example of a large data storage system that used replication and a direct predecessor to the systems you mentioned.)
CDs (remember those? lol) also implemented Reed-Solomon erasure codes for the stored data, erasure codes in storage systems aren't new at all, and that's not what this paper is about.
I actually found out about this paper because it was referenced in a slide presentation from Google about Colossus (which is the successor to GFS). GFS indeed uses erasure coding with a 1.5x factor, but erasure coding alone does not guarantee durability, and thus needs to be combined with replication to satisfy that requirement, and erasure coding is not the same thing as replication.
The innovation here is explicitly the combination of a new erasure coding algorithm (LRC) AND replication, with a combined storage amplification that is much lower than the previous SOTA.
The paper explicitly compares the new algorithm (LRC) with GFS and other alternatives, and explains why it's better, so this is really not something that is comparable to the 2003 GFS paper in any way (or to any other prior art really), as this is not just a trivial application of erasure coding in a storage system.
There's also this paper [0] from 2001 which digs a bit deeper into the Erasure Codes vs Replication idea that I can recommend if you're interested
I think for the major players you mentioned the 2016 paper was retrospective. Everyone was already doing it. Even mid-tier players like Dropbox Magic Pocket were using erasure coding by 2016, and their scheme was mostly written by ex-Google engineers influenced by Colossus.
Oh I am absolutely aware that erasure codes are an old thing, Reed-Solomon codes exist since the 1960's, but this is not simply a trivial application of erasure coding to a storage system: erasure codes alone don't provide the same durability guarantees that replication does. [0]
This is a combination of erasure coding AND replication, whose combined storage amplification is dramatically lower than previous SOTA.
I gave a longer explanation in a sibing comment to yours [1]
Thanks for the clarification. I still think these techniques were somewhat widespread already ... see for example this figure from US Patent 9292389 describing nested, aka layered coding that to my thinking is isomorphic with the "LRC" or "pyramid code" described by the Microsoft researchers.
By the way, not at all trying to say this paper isn't interesting. I keep it in my filing cabinet to show my colleagues when I need to describe this technique, since Google hasn't ever bothered to describe Colossus in a way I can reference.
The primary reason why you should be using 3x or higher replication is the read throughput (which makes it only really relevant for magnetic storage). If the data is replicated 1.6x then there's only 1.6 magnetic disk heads per each file byte. If you replicate it 6x then there's 6 magnetic disk heads for each byte. At ~15x it becomes cheaper to store in SSD with ~1.5x reed-solomon/erasure code overhead since SSD has ~10x the per-byte cost of HDD.
(there are also effects on the tail latency of both read and write, because in a replicated encoding you are less likely to be affected by a single slow drive).
(also, for insane performance which is sometimes needed you can mlock() things into RAM; the per-byte cost of RAM is ~100x the cost of HDD and ~10x the cost of SSD).
Everything you just said is on point, but I think that's an orthogonal thing to what the paper is going for. Hot data should absolutely have a fully-materialized copy at the node where operations are made, and an arbitrary number of readable copies can be materialized for added performance in systems that don't rely on strong consistency as much.
However for cold-data, there really hasn't been (or at least I am unaware of) any system that can achieve the combined durability of 1.5x Reed-Solomon codes + 3x replication, with such a small penalty to storage costs.
Like you said though, it's definitely not the thing you'd be doing for things that prioritize performance as aggressively as the use-cases you've suggested.
~1.5x reed solomon is the default these days, again, unless you need read throughput performance. It is awesome :)
Also, these days the storage of the data doesn't have to be at the same machine that processes the data. A lot of datacenter setups have basically zero transfer cost (or, alternatively, all the within-DC transfer cost is in the CAPEX required to build the DC in the first place), ultra low latency, and essentially unlimited bandwidth for any within-datacenter communication. This doesn't hold for dc1->dc2 communication, in particular it is very very far from the truth in long distance lines.
One way to think about the above is that datacenters have become the new supercomputers of the IBM era - it's free and really fast to exchange data within a single DC.
Also2, this is completely independent of consistency guarantees. At best it relates to durability guarantees, but that I want from all storage solutions. And yes, properly done reed solomon has the same durability guarantees as plain old replicated setup.
Also to the above also2, single-DC solutions are never really durable as the DC can simply burn down or meet some other tragic end, you need geographic replication if your data cannot be accidentally lost without serious consequences (a lot of data actually can be lost, in particular if it is some kind of intermediate data that can be regenerated from the "source" with some engineering effort). This is not just a theoretical concern, I've seen "acts of God" destroy single-DC setups data, ay least partially. It is pretty rare, though.
I'm confused, as you don't seem to be replying to any point I've made...
> ~1.5x reed solomon is the default these days, again, unless you need read throughput performance
I'm not surprised that Reed-Solomon is the "default these days" given that it exists since the 1960's, and that the most widely available and deployed open-source distributed filesystem is HDFS (which uses Reed-Solomon). However I don't see how that is to be taken as a blind endorsement for it, especially given that the paper in reference explicitly compares itself to Reed-Solomon based systems, including concerns regarding reconstruction costs, performance, and reliability.
> Also, these days the storage of the data doesn't have to be at the same machine that processes the data
Even though what you said here is correct, I don't see how that's relevant to the referenced paper, nor do I think I implied that I hold a contrary belief in any way from what I said.
> Also2, this is completely independent of consistency guarantees
My comment about consistency referred only to the fact that you cannot "simply" spin up more replicas to increase read throughput, because consistent reads often have to aqcuire a lock on systems that enforce stronger consistency, so your comments regarding throughput are not universally true, given that there are many systems where reads cannot be made faster this way, as they are bottle-necked by design.
> Properly done Reed-Solomon has the same durability guarantees as plain old replicated setup
This is not true unless the fragments themselves are being replicated across failure domains, which you seem to address with your next comment with "you need geographic replication if your data cannot be accidentally lost without serious consequences". All of this, however, is directly addressed in the paper as well:
> The advantage of erasure coding over simple replication is that it can achieve much higher reliability with the same storage, or it requires much lower storage for the same reliability. The existing systems, however, do not explore alternative erasure coding designs other than Reed-Solomon codes. In this work, we show that, under the same reliability requirement, LRC allows a much more efficient cost and performance tradeoff than Reed-Solomon.
It's not even the reduction in storage costs in this paper that is groundbreaking. They talk about a way to not only reduce storage costs, but optimize for repairs. Repairs are costly at scale and reducing resources where possible: network, cpu, disk reads, etc is ideal.
and,
[2] HeART: improving storage efficiency by exploiting disk-reliability heterogeneity - https://www.usenix.org/conference/fast19/presentation/kadeko... . This paper talks about how just one erasure code is not enough and employing code conversions over the disk-reliability we can get up to 30% savings!
Even if not implemented in such a sophisticated manner, "meaningful availability" is a better metric than pure uptime/downtime for most websites.
At one startup we worked at we had availability problems for some time, with the service going down in a semi-predictable manner ~2 times a day (and the proper bugfix a few weeks away). Because once a day the service went down was in the middle of the night with no one on call, pure availability was 80-90%. Given that it was a single country app with no one trying to do any business during the night, meaningful availability was ~99%. Knowing that gave us peace of mind and made tackling the problem a much more relaxed ordeal than the crunch time for a few weeks I've seen at other companies in similar situations.
Goes to show the complete lack of agreement between researchers in the explainability space. Most popular packages (allen NLP, google LIT, Captum) use saliency based methods (Integrated gradients) or Attention. The community has fundamental disagreements on whether they capture anything equivalent to importance as humans would understand it.
An entire community of fairness, ethics and Computational social science is built on top of conclusions using these methods. It is a shame that so much money is poured into these fields, but there does not seem to be as strong a thrust to explore the most fundamental questions themselves.
(my 2 cents: I like SHAP and the stuff coming out of Bin Yu and Tommi Jakkola's labs better..but my opinion too is based in intuition without any real rigor)
recently, a lot of neural network models, especially those in NLP (like GPT-3, BERT, etc.) use "attention" which basically is a way for neural networks to focus on certain subset of the input (the neural network can focus its "attention" to a particular part of the input). Explanations just refers to ways for explaining the predictions of the neural networks.
These are deep neural net papers, specifically in NLP.
Explanation: why the model (the deep neural net, that is) is doing what it's doing.
Attention: a particular technique used in certain deep net models, invented a few years ago, that originally showed remarkable performance improvements in NLP (natural language processing) tasks, but has recently been applied in vision and elsewhere.
Some CogSci & Neuro papers I found interesting in 2020:
Constantinescu, Alexandra O., Jill X. O’Reilly, and Timothy EJ Behrens. "Organizing conceptual knowledge in humans with a gridlike code." Science 352.6292 (2016): 1464-1468.
Kriegeskorte, Nikolaus, and Katherine R. Storrs. "Grid cells for conceptual spaces?." Neuron 92.2 (2016): 280-284.
Klukas, Mirko, Marcus Lewis, and Ila Fiete. "Efficient and flexible representation of higher-dimensional cognitive variables with grid cells." PLOS Computational Biology 16.4 (2020): e1007796.
Moser, May-Britt, David C. Rowland, and Edvard I. Moser. "Place cells, grid cells, and memory." Cold Spring Harbor perspectives in biology 7.2 (2015): a021808.
Quiroga, Rodrigo Quian. "Concept cells: the building blocks of declarative memory functions." Nature Reviews Neuroscience 13.8 (2012): 587-597.
Stachenfeld, Kimberly L., Matthew M. Botvinick, and Samuel J. Gershman. "The hippocampus as a predictive map." Nature neuroscience 20.11 (2017): 1643.
Buzsáki, György, and David Tingley. "Space and time: The hippocampus as a sequence generator." Trends in cognitive sciences 22.10 (2018): 853-869.
Umbach, Gray, et al. "Time cells in the human hippocampus and entorhinal cortex support episodic memory." bioRxiv (2020).
Eichenbaum, Howard. "On the integration of space, time, and memory." Neuron 95.5 (2017): 1007-1018.
Schiller, Daniela, et al. "Memory and space: towards an understanding of the cognitive map." Journal of Neuroscience 35.41 (2015): 13904-13911.
Rolls, Edmund T., and Alessandro Treves. "The neuronal encoding of information in the brain." Progress in neurobiology 95.3 (2011): 448-490.
Fischer, Lukas F., et al. "Representation of visual landmarks in retrosplenial cortex." Elife 9 (2020): e51458.
Hebart, Martin, et al. "Revealing the multidimensional mental representations of natural objects underlying human similarity judgments." (2020).
Ezzyat, Youssef, and Lila Davachi. "Similarity breeds proximity: pattern similarity within and across contexts is related to later mnemonic judgments of temporal proximity." Neuron 81.5 (2014): 1179-1189.
Seger, Carol A., and Earl K. Miller. "Category learning in the brain." Annual review of neuroscience 33 (2010): 203-219.
Neurolinguistics:
Marcus, Gary F. "Evolution, memory, and the nature of syntactic representation." Birdsong, speech, and language: Exploring the evolution of mind and brain 27 (2013).
Dehaene, Stanislas, et al. "The neural representation of sequences: from transition probabilities to algebraic patterns and linguistic trees." Neuron 88.1 (2015): 2-19.
Fujita, Koji. "On the parallel evolution of syntax and lexicon: A Merge-only view." Journal of Neurolinguistics 43 (2017): 178-192.
Thanks for putting this list together! I took some cog sci courses in college and have been meaning to dive more into the research around it and these papers seem like a good place to start. I expect to run into lots of jargon and concepts I don't understand. Would it be possible for me to reach out to you for questions when I'm unable to make sense of the content after having researched the unknown concepts online?
Nice to see someone found Bird song book interesting.
Here's a cool paper on bird song during lockdown.
Derryberry, Elizabeth P., et al. Singing in a silent spring: Birds respond to a half-century soundscape reversion during the COVID-19 shutdown (2020) (DOI: 10.1126/science.abd5777)
Pulvermüller, Friedemann. "Words in the brain's language." Behavioral and brain sciences 22.2 (1999): 253-279.
Pulvermüller, Friedemann. "Brain embodiment of syntax and grammar: Discrete combinatorial mechanisms spelt out in neuronal circuits." Brain and language 112.3 (2010): 167-179.
Lau, Ellen F., Colin Phillips, and David Poeppel. "A cortical network for semantics:(de) constructing the N400." Nature Reviews Neuroscience 9.12 (2008): 920-933.
Bellmund, Jacob LS, et al. "Navigating cognition: Spatial codes for human thinking." Science 362.6415 (2018).
Peer, Michael, et al. "Processing of different spatial scales in the human brain." ELife 8 (2019): e47492.
Kriegeskorte, Nikolaus, and Rogier A. Kievit. "Representational geometry: integrating cognition, computation, and the brain." Trends in cognitive sciences 17.8 (2013): 401-412.
Mok, Robert M., and Bradley C. Love. "A non-spatial account of place and grid cells based on clustering models of concept learning." Nature communications 10.1 (2019): 1-9.
Chrastil, Elizabeth R., and William H. Warren. "From cognitive maps to cognitive graphs." PloS one 9.11 (2014): e112544.
-->On graph navigation and 'rich club' networks:
Watts, Duncan J., and Steven H. Strogatz. "Collective dynamics of ‘small-world’networks." nature 393.6684 (1998): 440-442.
Kleinberg, Jon M. "Navigation in a small world." Nature 406.6798 (2000): 845-845.
Ball, Gareth, et al. "Rich-club organization of the newborn human brain." Proceedings of the National Academy of Sciences 111.20 (2014): 7456-7461.
Malkov, Yury A., and Alexander Ponomarenko. "Growing homophilic networks are natural navigable small worlds." PloS one 11.6 (2016): e0158162.
Givoni, Inmar, Clement Chung, and Brendan J. Frey. "Hierarchical affinity propagation." arXiv preprint arXiv:1202.3722 (2012).
--> On concept formation, memory & generalization
Bowman, Caitlin R., and Dagmar Zeithamova. "Abstract memory representations in the ventromedial prefrontal cortex and hippocampus support concept generalization." Journal of Neuroscience 38.10 (2018): 2605-2614.
Garvert, Mona M., Raymond J. Dolan, and Timothy EJ Behrens. "A map of abstract relational knowledge in the human hippocampal–entorhinal cortex." Elife 6 (2017): e17086.
Collin, Silvy HP, Branka Milivojevic, and Christian F. Doeller. "Hippocampal hierarchical networks for space, time, and memory." Current opinion in behavioral sciences 17 (2017): 71-76.
Kumaran, Dharshan, et al. "Tracking the emergence of conceptual knowledge during human decision making." Neuron 63.6 (2009): 889-901.
DeVito, Loren M., et al. "Prefrontal cortex: role in acquisition of overlapping associations and transitive inference." Learning & Memory 17.3 (2010): 161-167.
Gallistel, Charles Randy, and Louis D. Matzel. "The neuroscience of learning: beyond the Hebbian synapse." Annual review of psychology 64 (2013): 169-200.
Martin, A., and W. K. Simmons. "Structural Basis of semantic memory." Learning and Memory: A Comprehensive Reference. Elsevier, 2007. 113-130.
Zeithamova, Dagmar, Margaret L. Schlichting, and Alison R. Preston. "The hippocampus and inferential reasoning: building memories to navigate future decisions." Frontiers in human neuroscience 6 (2012): 70.
Tenenbaum, Joshua B., and Thomas L. Griffiths. "Generalization, similarity, and Bayesian inference." Behavioral and brain sciences 24.4 (2001): 629.
You might think that it's possible to use machine learning to predict whether people will be successful using established socio-demographic, psychological, and educational metrics. It turns out that it's very hard and simple regression models outperform the fanciest machine learning ideas for this problem.
The way this study was done is also interesting and paves the way for new kinds of collaborative scientific projects that take on big questions. It draws on communities like Kaggle, but applies it to scientific questions not just pure prediction problems.
Genetics and net worth can be blown away by a good or bad group of friends. And unfortunately you start having friends before you are concious enough to realize the impact.
> simple regression models outperform the fanciest machine learning ideas for this problem
This reminds me of a classic paper: "Improper linear models are those in which the weights of the predictor variables are obtained by some nonoptimal method; for example, they
may be obtained on the basis of intuition, derived
from simulating a clinical judge's predictions, or set to
be equal. This article presents evidence that even
such improper linear models are superior to clinical intuition when predicting a numerical criterion from
numerical predictors."
Dawes, R. M. (1979). The robust beauty of improper linear models in decision making. American psychologist, 34(7), 571.
Tactical Periodization is a training program credited for the success of at least one star. This paper says, in short, there are no scientific studies proving it works. We'd give it the benefit of the doubt and wait for proof, but it's been 20 years and still nothing.
I'm not sure if this is precisely the direction things should go in order to improve the utilisation of specification within software development but it's a very important contribution. As yet my favourite development style has been with F-star but F-star also leaves me a bit in a lurch when the automatic system isn't able to find the answer. Too much hinting in the case of hard proofs.
Eventually there will be a system that lets you turn the crank up on specification late in the game, allows lots of the assertions to be discharged automatically, and then finally saddles you with the remaining proof obligations in a powerful proof assistant.
One of my favorites is definitely A Unified Framework for Dopamine Signals across Timescales (https://doi.org/10.1016/j.cell.2020.11.013), simply because of its experimental design. They 'teleported' rats in VR to see how their dopamine neurons responded, to determine whether TD learning explains dopamine signals on both short and long timescales. Short answer: it does.
It deals with the classic, and wonderful, question of "If I go and catch 100 birds, and they're from 20 different species, how many species are left uncaught?" There's more one can say about that than it might first appear and it has plenty of applications. But mostly I just love the name. Apparently PNAS had them change it for the final publication, sadly.
Yeah, exactly. If you wanted to know that your code was bug free, how could you do it? Set a team of experts to each independently scour for bugs. But when do you stop? The quick answer is that you should keep going until every bug you've found, has been found at least twice. I think of this as being that you "just barely" found a bug if only one person identified it, so there are probably still bugs you have "just barely" not found remaining.
Is that a direct application of the paper or something else? (sorry I didn't read it)
Just wondering because this rule of thumb sounds intuitively wrong to me. Depending on the difficulty of the bugs and the skill levels of the experts, it seems possible for them to find every "easy" bug at least twice while having none of them finding the hardest bug even once. (real world example would be some obscure zero-day security bug)
I should have said "at least until" rather than "until", sorry. It's from a result that predates the paper, due to Fisher (using butterflies, not code bugs).
The actual guarantee from the result is not that the number of unobserved "species" is small, but that the total population of all unobserved species is small. If you go back to the birds example, then you could say something like "at most 0.1% of all birds are from species that we haven't identified" but maybe those 0.1% of birds are from a million different species each with incredibly tiny populations. In the code bug example, the very rare species would be the bugs that are very unlikely to be found, i.e. it's more about estimating how many more bugs you will find if you continue to analyze it than how many are really there.
Set a team of experts to find bugs independently for some specified amount of time. Then look at how many of the same bugs were found by multiple experts.
If most of the bugs were found by multiple experts, then there are probably not that many more bugs than the total number that they found. If most of the bugs were found by only one expert, then there are probably a lot more than the total that they found.
With some math you can pin down the 'probablies' to numeric ranges.
Does that not assume equal probability of finding bugs? Seems to me that both teams would find the same easily identified bugs (say '=' instead of '==' or revealed by compiler warnings).
This sounds like a similar problem to an exercise in the famous probability textbook by William Feller about estimating the total number of fish in a lake by catching N of them and tagging them, and then throwing them back in the lake and coming back later to catch another N fish. You check how many of those fish are tagged and derive your estimate from that using the hypergeometric distribution. See the pages here:
Abstraction has made Programming a hybrid of Tradition/Authority/Science/Art.
It's nearly impossible to have a scientific paper on anything with abstraction. At best you can create some "after the fact" optimizations using time studies and statistics.
I don't mean programming literally (although there are plenty of papers on programming abstractions, especially in the functional world) but just computer subjects in general whether that is cryptography, complexity theory, hardware or something else.
196 comments
[ 1.7 ms ] story [ 256 ms ] threadThe idea that you can achieve the same practical effect of a 3x replication factor in a distributed system, but only increasing the cost of data storage by 1.6x, by leveraging some clever information theory tricks is mind bending to me.
If you're operating a large Ceph cluster, or you're Google/Amazon/Microsoft and you're running GCS/S3/ABS, if you needed 50PB HDDs before, you only need 27PB now (if implementing this).
The cost savings, and environmental impact reduction that this allows for are truly enormous, I'm surprised how little attention this paper has gotten in the wild.
[0] https://www.microsoft.com/en-us/research/wp-content/uploads/...
https://static.googleusercontent.com/media/research.google.c...
I actually found out about this paper because it was referenced in a slide presentation from Google about Colossus (which is the successor to GFS). GFS indeed uses erasure coding with a 1.5x factor, but erasure coding alone does not guarantee durability, and thus needs to be combined with replication to satisfy that requirement, and erasure coding is not the same thing as replication.
The innovation here is explicitly the combination of a new erasure coding algorithm (LRC) AND replication, with a combined storage amplification that is much lower than the previous SOTA.
The paper explicitly compares the new algorithm (LRC) with GFS and other alternatives, and explains why it's better, so this is really not something that is comparable to the 2003 GFS paper in any way (or to any other prior art really), as this is not just a trivial application of erasure coding in a storage system.
There's also this paper [0] from 2001 which digs a bit deeper into the Erasure Codes vs Replication idea that I can recommend if you're interested
[0] http://fireless.cs.cornell.edu/publications/erasure_iptps.pd...
This is a combination of erasure coding AND replication, whose combined storage amplification is dramatically lower than previous SOTA.
I gave a longer explanation in a sibing comment to yours [1]
[0] http://fireless.cs.cornell.edu/publications/erasure_iptps.pd...
[1] https://news.ycombinator.com/item?id=25351678
By the way, not at all trying to say this paper isn't interesting. I keep it in my filing cabinet to show my colleagues when I need to describe this technique, since Google hasn't ever bothered to describe Colossus in a way I can reference.
https://imgur.com/a/gi2Xdl0
(there are also effects on the tail latency of both read and write, because in a replicated encoding you are less likely to be affected by a single slow drive).
(also, for insane performance which is sometimes needed you can mlock() things into RAM; the per-byte cost of RAM is ~100x the cost of HDD and ~10x the cost of SSD).
However for cold-data, there really hasn't been (or at least I am unaware of) any system that can achieve the combined durability of 1.5x Reed-Solomon codes + 3x replication, with such a small penalty to storage costs.
Like you said though, it's definitely not the thing you'd be doing for things that prioritize performance as aggressively as the use-cases you've suggested.
Also, these days the storage of the data doesn't have to be at the same machine that processes the data. A lot of datacenter setups have basically zero transfer cost (or, alternatively, all the within-DC transfer cost is in the CAPEX required to build the DC in the first place), ultra low latency, and essentially unlimited bandwidth for any within-datacenter communication. This doesn't hold for dc1->dc2 communication, in particular it is very very far from the truth in long distance lines.
One way to think about the above is that datacenters have become the new supercomputers of the IBM era - it's free and really fast to exchange data within a single DC.
Also2, this is completely independent of consistency guarantees. At best it relates to durability guarantees, but that I want from all storage solutions. And yes, properly done reed solomon has the same durability guarantees as plain old replicated setup.
Also to the above also2, single-DC solutions are never really durable as the DC can simply burn down or meet some other tragic end, you need geographic replication if your data cannot be accidentally lost without serious consequences (a lot of data actually can be lost, in particular if it is some kind of intermediate data that can be regenerated from the "source" with some engineering effort). This is not just a theoretical concern, I've seen "acts of God" destroy single-DC setups data, ay least partially. It is pretty rare, though.
> ~1.5x reed solomon is the default these days, again, unless you need read throughput performance
I'm not surprised that Reed-Solomon is the "default these days" given that it exists since the 1960's, and that the most widely available and deployed open-source distributed filesystem is HDFS (which uses Reed-Solomon). However I don't see how that is to be taken as a blind endorsement for it, especially given that the paper in reference explicitly compares itself to Reed-Solomon based systems, including concerns regarding reconstruction costs, performance, and reliability.
> Also, these days the storage of the data doesn't have to be at the same machine that processes the data
Even though what you said here is correct, I don't see how that's relevant to the referenced paper, nor do I think I implied that I hold a contrary belief in any way from what I said.
> Also2, this is completely independent of consistency guarantees
My comment about consistency referred only to the fact that you cannot "simply" spin up more replicas to increase read throughput, because consistent reads often have to aqcuire a lock on systems that enforce stronger consistency, so your comments regarding throughput are not universally true, given that there are many systems where reads cannot be made faster this way, as they are bottle-necked by design.
> Properly done Reed-Solomon has the same durability guarantees as plain old replicated setup
This is not true unless the fragments themselves are being replicated across failure domains, which you seem to address with your next comment with "you need geographic replication if your data cannot be accidentally lost without serious consequences". All of this, however, is directly addressed in the paper as well:
> The advantage of erasure coding over simple replication is that it can achieve much higher reliability with the same storage, or it requires much lower storage for the same reliability. The existing systems, however, do not explore alternative erasure coding designs other than Reed-Solomon codes. In this work, we show that, under the same reliability requirement, LRC allows a much more efficient cost and performance tradeoff than Reed-Solomon.
> some clever information theory tricks is mind bending to me
It's a pretty trivial first-degree linear function, y = ax + b
[1] Clay Codes - https://www.usenix.org/conference/fast18/presentation/vajha . This paper was also implemented on Ceph and the results are shown in the paper.
and, [2] HeART: improving storage efficiency by exploiting disk-reliability heterogeneity - https://www.usenix.org/conference/fast19/presentation/kadeko... . This paper talks about how just one erasure code is not enough and employing code conversions over the disk-reliability we can get up to 30% savings!
https://www.nature.com/articles/s41587-020-0711-0
A good incremental improvement in service level indicator measurements for large-scale cloud services.
Obligatory The Morning Paper post: https://blog.acolyer.org/2020/02/26/meaningful-availability/
At one startup we worked at we had availability problems for some time, with the service going down in a semi-predictable manner ~2 times a day (and the proper bugfix a few weeks away). Because once a day the service went down was in the middle of the night with no one on call, pure availability was 80-90%. Given that it was a single country app with no one trying to do any business during the night, meaningful availability was ~99%. Knowing that gave us peace of mind and made tackling the problem a much more relaxed ordeal than the crunch time for a few weeks I've seen at other companies in similar situations.
https://arogozhnikov.github.io/2016/12/19/markov_chain_monte...
Thought the Naiad project is really cool!
https://cs.stanford.edu/~matei/courses/2015/6.S897/readings/...
https://research.google/pubs/pub48630/
1.Attention is not explanation (https://arxiv.org/abs/1902.10186)
2.Attention is not not Explanation (https://arxiv.org/abs/1908.04626)
Goes to show the complete lack of agreement between researchers in the explainability space. Most popular packages (allen NLP, google LIT, Captum) use saliency based methods (Integrated gradients) or Attention. The community has fundamental disagreements on whether they capture anything equivalent to importance as humans would understand it.
An entire community of fairness, ethics and Computational social science is built on top of conclusions using these methods. It is a shame that so much money is poured into these fields, but there does not seem to be as strong a thrust to explore the most fundamental questions themselves.
(my 2 cents: I like SHAP and the stuff coming out of Bin Yu and Tommi Jakkola's labs better..but my opinion too is based in intuition without any real rigor)
[1] [PDF] https://papers.nips.cc/paper/2018/file/b495ce63ede0f4efc9eec...
Explanation: why the model (the deep neural net, that is) is doing what it's doing.
Attention: a particular technique used in certain deep net models, invented a few years ago, that originally showed remarkable performance improvements in NLP (natural language processing) tasks, but has recently been applied in vision and elsewhere.
https://explainml-tutorial.github.io/papers
I saw the first paper mentioned in the tutorial chat.
What is your impression of anchor? https://github.com/marcotcr/anchor
Constantinescu, Alexandra O., Jill X. O’Reilly, and Timothy EJ Behrens. "Organizing conceptual knowledge in humans with a gridlike code." Science 352.6292 (2016): 1464-1468.
Kriegeskorte, Nikolaus, and Katherine R. Storrs. "Grid cells for conceptual spaces?." Neuron 92.2 (2016): 280-284.
Klukas, Mirko, Marcus Lewis, and Ila Fiete. "Efficient and flexible representation of higher-dimensional cognitive variables with grid cells." PLOS Computational Biology 16.4 (2020): e1007796.
Moser, May-Britt, David C. Rowland, and Edvard I. Moser. "Place cells, grid cells, and memory." Cold Spring Harbor perspectives in biology 7.2 (2015): a021808.
Quiroga, Rodrigo Quian. "Concept cells: the building blocks of declarative memory functions." Nature Reviews Neuroscience 13.8 (2012): 587-597.
Stachenfeld, Kimberly L., Matthew M. Botvinick, and Samuel J. Gershman. "The hippocampus as a predictive map." Nature neuroscience 20.11 (2017): 1643.
Buzsáki, György, and David Tingley. "Space and time: The hippocampus as a sequence generator." Trends in cognitive sciences 22.10 (2018): 853-869.
Umbach, Gray, et al. "Time cells in the human hippocampus and entorhinal cortex support episodic memory." bioRxiv (2020).
Eichenbaum, Howard. "On the integration of space, time, and memory." Neuron 95.5 (2017): 1007-1018.
Schiller, Daniela, et al. "Memory and space: towards an understanding of the cognitive map." Journal of Neuroscience 35.41 (2015): 13904-13911.
Rolls, Edmund T., and Alessandro Treves. "The neuronal encoding of information in the brain." Progress in neurobiology 95.3 (2011): 448-490.
Fischer, Lukas F., et al. "Representation of visual landmarks in retrosplenial cortex." Elife 9 (2020): e51458.
Hebart, Martin, et al. "Revealing the multidimensional mental representations of natural objects underlying human similarity judgments." (2020).
Ezzyat, Youssef, and Lila Davachi. "Similarity breeds proximity: pattern similarity within and across contexts is related to later mnemonic judgments of temporal proximity." Neuron 81.5 (2014): 1179-1189.
Seger, Carol A., and Earl K. Miller. "Category learning in the brain." Annual review of neuroscience 33 (2010): 203-219.
Neurolinguistics:
Marcus, Gary F. "Evolution, memory, and the nature of syntactic representation." Birdsong, speech, and language: Exploring the evolution of mind and brain 27 (2013).
Dehaene, Stanislas, et al. "The neural representation of sequences: from transition probabilities to algebraic patterns and linguistic trees." Neuron 88.1 (2015): 2-19.
Fujita, Koji. "On the parallel evolution of syntax and lexicon: A Merge-only view." Journal of Neurolinguistics 43 (2017): 178-192.
I'm not an expert though, just curious about "mind computations".
Here's a cool paper on bird song during lockdown.
Derryberry, Elizabeth P., et al. Singing in a silent spring: Birds respond to a half-century soundscape reversion during the COVID-19 shutdown (2020) (DOI: 10.1126/science.abd5777)
Pulvermüller, Friedemann. "Words in the brain's language." Behavioral and brain sciences 22.2 (1999): 253-279.
Pulvermüller, Friedemann. "Brain embodiment of syntax and grammar: Discrete combinatorial mechanisms spelt out in neuronal circuits." Brain and language 112.3 (2010): 167-179.
Buzsáki, György. "Neural syntax: cell assemblies, synapsembles, and readers." Neuron 68.3 (2010): 362-385.
Lau, Ellen F., Colin Phillips, and David Poeppel. "A cortical network for semantics:(de) constructing the N400." Nature Reviews Neuroscience 9.12 (2008): 920-933.
-->On cognitive maps, spacial & abstract navigation:
Bellmund, Jacob LS, et al. "Navigating cognition: Spatial codes for human thinking." Science 362.6415 (2018).
Peer, Michael, et al. "Processing of different spatial scales in the human brain." ELife 8 (2019): e47492.
Kriegeskorte, Nikolaus, and Rogier A. Kievit. "Representational geometry: integrating cognition, computation, and the brain." Trends in cognitive sciences 17.8 (2013): 401-412.
Mok, Robert M., and Bradley C. Love. "A non-spatial account of place and grid cells based on clustering models of concept learning." Nature communications 10.1 (2019): 1-9.
Chrastil, Elizabeth R., and William H. Warren. "From cognitive maps to cognitive graphs." PloS one 9.11 (2014): e112544.
-->On graph navigation and 'rich club' networks:
Watts, Duncan J., and Steven H. Strogatz. "Collective dynamics of ‘small-world’networks." nature 393.6684 (1998): 440-442.
Kleinberg, Jon M. "Navigation in a small world." Nature 406.6798 (2000): 845-845.
Ball, Gareth, et al. "Rich-club organization of the newborn human brain." Proceedings of the National Academy of Sciences 111.20 (2014): 7456-7461.
Malkov, Yury A., and Alexander Ponomarenko. "Growing homophilic networks are natural navigable small worlds." PloS one 11.6 (2016): e0158162.
Givoni, Inmar, Clement Chung, and Brendan J. Frey. "Hierarchical affinity propagation." arXiv preprint arXiv:1202.3722 (2012).
--> On concept formation, memory & generalization
Bowman, Caitlin R., and Dagmar Zeithamova. "Abstract memory representations in the ventromedial prefrontal cortex and hippocampus support concept generalization." Journal of Neuroscience 38.10 (2018): 2605-2614.
Garvert, Mona M., Raymond J. Dolan, and Timothy EJ Behrens. "A map of abstract relational knowledge in the human hippocampal–entorhinal cortex." Elife 6 (2017): e17086.
Collin, Silvy HP, Branka Milivojevic, and Christian F. Doeller. "Hippocampal hierarchical networks for space, time, and memory." Current opinion in behavioral sciences 17 (2017): 71-76.
Kumaran, Dharshan, et al. "Tracking the emergence of conceptual knowledge during human decision making." Neuron 63.6 (2009): 889-901.
DeVito, Loren M., et al. "Prefrontal cortex: role in acquisition of overlapping associations and transitive inference." Learning & Memory 17.3 (2010): 161-167.
Gallistel, Charles Randy, and Louis D. Matzel. "The neuroscience of learning: beyond the Hebbian synapse." Annual review of psychology 64 (2013): 169-200.
Martin, A., and W. K. Simmons. "Structural Basis of semantic memory." Learning and Memory: A Comprehensive Reference. Elsevier, 2007. 113-130.
Zeithamova, Dagmar, Margaret L. Schlichting, and Alison R. Preston. "The hippocampus and inferential reasoning: building memories to navigate future decisions." Frontiers in human neuroscience 6 (2012): 70.
Tenenbaum, Joshua B., and Thomas L. Griffiths. "Generalization, similarity, and Bayesian inference." Behavioral and brain sciences 24.4 (2001): 629.
[1] https://arxiv.org/abs/1912.04958
https://pdfs.semanticscholar.org/c26b/4d3156b0c526d16c891ce7...
>"three of the four most cited papers in the journals deal with hypoxia [...] yet its routine clinical use is very limited."
http://www.pnas.org/lookup/doi/10.1073/pnas.1915006117
You might think that it's possible to use machine learning to predict whether people will be successful using established socio-demographic, psychological, and educational metrics. It turns out that it's very hard and simple regression models outperform the fanciest machine learning ideas for this problem.
The way this study was done is also interesting and paves the way for new kinds of collaborative scientific projects that take on big questions. It draws on communities like Kaggle, but applies it to scientific questions not just pure prediction problems.
Genetics and net worth can be blown away by a good or bad group of friends. And unfortunately you start having friends before you are concious enough to realize the impact.
This reminds me of a classic paper: "Improper linear models are those in which the weights of the predictor variables are obtained by some nonoptimal method; for example, they may be obtained on the basis of intuition, derived from simulating a clinical judge's predictions, or set to be equal. This article presents evidence that even such improper linear models are superior to clinical intuition when predicting a numerical criterion from numerical predictors."
Dawes, R. M. (1979). The robust beauty of improper linear models in decision making. American psychologist, 34(7), 571.
https://core.ac.uk/download/pdf/190386677.pdf
https://www.researchgate.net/publication/342317256_A_systema...
Gradualizing the Calculus of Inductive Constructions (https://hal.archives-ouvertes.fr/hal-02896776/)
I'm not sure if this is precisely the direction things should go in order to improve the utilisation of specification within software development but it's a very important contribution. As yet my favourite development style has been with F-star but F-star also leaves me a bit in a lurch when the automatic system isn't able to find the answer. Too much hinting in the case of hard proofs.
Eventually there will be a system that lets you turn the crank up on specification late in the game, allows lots of the assertions to be discharged automatically, and then finally saddles you with the remaining proof obligations in a powerful proof assistant.
MMR vaccine could protect against COVID-19
https://mbio.asm.org/content/11/6/e02628-20?_ga=2.139230451....
"Temporal difference (TD) error is a powerful teaching signal in machine learning"
"Estimating the number of unseen species: A bird in the hand is worth log(n) in the bush" https://arxiv.org/abs/1511.07428 https://www.pnas.org/content/113/47/13283
It deals with the classic, and wonderful, question of "If I go and catch 100 birds, and they're from 20 different species, how many species are left uncaught?" There's more one can say about that than it might first appear and it has plenty of applications. But mostly I just love the name. Apparently PNAS had them change it for the final publication, sadly.
Just wondering because this rule of thumb sounds intuitively wrong to me. Depending on the difficulty of the bugs and the skill levels of the experts, it seems possible for them to find every "easy" bug at least twice while having none of them finding the hardest bug even once. (real world example would be some obscure zero-day security bug)
The actual guarantee from the result is not that the number of unobserved "species" is small, but that the total population of all unobserved species is small. If you go back to the birds example, then you could say something like "at most 0.1% of all birds are from species that we haven't identified" but maybe those 0.1% of birds are from a million different species each with incredibly tiny populations. In the code bug example, the very rare species would be the bugs that are very unlikely to be found, i.e. it's more about estimating how many more bugs you will find if you continue to analyze it than how many are really there.
Set a team of experts to find bugs independently for some specified amount of time. Then look at how many of the same bugs were found by multiple experts.
If most of the bugs were found by multiple experts, then there are probably not that many more bugs than the total number that they found. If most of the bugs were found by only one expert, then there are probably a lot more than the total that they found.
With some math you can pin down the 'probablies' to numeric ranges.
With python code.
Big game from an organization with that acronym.
https://imgur.com/oRF0OD3 https://imgur.com/UtCZL5A
No one knows what attention is (https://link.springer.com/article/10.3758/s13414-019-01846-w)
https://groups.csail.mit.edu/genesis/papers/radul%202009.pdf
An interesting (no pun intended) paper on what makes papers (or anything in general) interesting.
Which is actually great because it gives me something to read on subjects im not familar with.
It's nearly impossible to have a scientific paper on anything with abstraction. At best you can create some "after the fact" optimizations using time studies and statistics.
https://www.nationalgeographic.com/science/2020/04/first-spi...