Locklin on science

My favorite photo of this wacky election

Posted in stats jackass of the month, Uncategorized by Scott Locklin on November 9, 2016

This dope got lucky in 2012, essentially using “take the mean” and was hailed as a prophet. He was wrong about virtually everything, and if someone were to make a table of his predictions over time and calculate Brier scores, I’m pretty sure he’ll get a higher score than Magic-8 ball (Brier scores, lower is better). Prediction is difficult, as the sage said, especially regarding the future. Claiming you can do prediction when you can’t is irresponsible and can actually be dangerous.
silver.jpg

While he richly deserves to find his proper station in life as an opinionated taxi driver, this clown is unfortunately likely to be with us for years to come, bringing shame on the profession of quantitative analysis of data. We’ll be watching, Nate.

 

 

The Future ain’t what it used to be

Posted in fun, Progress by Scott Locklin on November 1, 2016

I came across this video recently. It is a think piece by the Ford motor company and a long dead electronics firm called Philco showing what the future will be like from the perspective of 1967. It’s a nice imaginative vista from a time of great technological optimism: 1967. They were close to accomplishing the moon shot, and the Mach-3 Boeing SST had only recently been announced. From the perspective of a technologist alive in those days, life could have ended up like this. The set of things people worried about technological solutions and conveniences they thought would be cool are also interesting. It is kind of sad comparing this bold imagined future (only 32 years away from when the video was made) to our actually existing shabby 1999 +17y future.  It’s 21 minutes, so if you don’t have 21 minutes to watch the whole thing, you can read my comments.

The husband of the house is an astrophysicist (working a remote day job on Mars Colonization no less) with a hobby doing … botany. He’s got a lab at home and is trying to breed a super peach with a protective tangerine skin. This is wildly unrealistic, even if they had thought of genetic engineering back then, and as far as I know, nobody is breeding crazy fruits today, let alone doing so as a hobby. Obviously nobody is colonizing Mars. Still, food and novelty was apparently considered important in 1967, so it is kind of endearing they gave the astrophysicist this kind of hobby. Most astrophysicists I know work 80 hour weeks and have hobbies like looking at youtube videos and grousing about funding levels.

home botany experiments

home botany experiments

The house of tomorrow has a central computer where all kinds of stuff is stored in its “memory banks.” There is really no reason why people distribute their data all over creation the way they do now; the future from 1967 looked a lot more sane and safe in this regard.  Memory banks and computers in this video look a lot like the computers, TVs and radios of 1967. They’re kind of cool looking, like a bit CAMAC crate or IBM mainframe.

memorybanks

memory banks of the future have lots of dip switches

The kid (single child to upper middle class parents; good prediction) seems to be homeschooled by  teaching machines. This is quite technically feasible these days, but not so many people work at home in our shabby future of 2016 that this is done regularly.

home schooling technology

home schooling technology

They chat with each other electronically. Their future used a sort of video intercom, which is a lot more interesting than our actual crummy future, where people furiously thumb-type text messages to each other from across the dinner table, rather than video calling from the other room. They also didn’t predict chatroulette.

1967 era instant messaging

1967 era instant messaging

Dinner is pre-processed and stored in some kind of central silo which microwaves dinner for everybody, based on their nutritional requirements and how fat they’re getting; all done in less than 2 minutes. The upside to our shabby future present is people don’t like icky but futuristic seeming TV dinners as much as they did in the 60s. Our shitty future equivalent, I guess, at least in the Bay Area, we have “services” which deliver food to your house unmade, and you have a bonding experience with your significant other following the directions and making the food. Or we just go to the grocery store like they did in 1967. There are probably apps which claim to track calories for people,  but in shitty future now pretty much everyone is disgustingly fat. Oh yeah, in the future of 1967, dishwashers are obsolete; everyone throws their (seemingly perfectly reusable) plates away. Little did they know in 1967, landfills would become a political problem.

making dinner using technology

making dinner using technology

Lots of clothes in the 1967 future will be as disposable as the plates and silverware. The ones that you want to keep are ultrasound dry cleaned using a frightening closet which seems quite exposed to the rest of the house, despite shooting visible clouds of noxious chemicals all over the place. People in the 1967 future weren’t as petrified of chemicals as we are now. Frankly their self cleaning closet gives even me the creeps. I don’t even like using moth balls. Hot link to scary cleaning closet here.

In the 1967 future, the Mrs. of the household can buy stuff “online,” which was a pretty good guess. Of course, their “online” is from some kind of live video feed. The idea of a website (or a mouse or keyboard) hadn’t occurred to them yet. And the bank is also accessible through some other kind of computerized console, as is a “home post office” which I guess was a form of email. Though their email system works in cursive in this example. I am guessing that typewriter style keyboards were seen as a specialized skill in those days, and “push button” was seen as more futuristic.

Amazon shopping in the future

Amazon shopping in the future

The house is powered by a hydrogen fuel cell for some reason, and “pure water” is a useful byproduct. Maybe in the 1967 future plumbing will be depreciated. In their 1967-vantage future, despite breeding crazy peaches and eating all their food from the microwave-refrigerator food dispensing machine, they’ll get strange undersea fruits from hydro-cultured underwater farms. 1960s futurology was filled with fantasies of growing things under water; science fiction from those days seemed to think we’d all be algae eaters in the future. I was never able to figure that out. I guess humanity obviated this with the green revolution, which was not something which was particularly predictable from those days.

The home gym is fun. It features a medical scanner which scans you while reclining on an Eames style couch and makes exercise suggestions; something that doesn’t exist anywhere, probably never will, despite all the DARPA requests for such a thing. Pretty much the same thing as in Star Trek’s “sick bay.” There’s lots of funny old timey exercise equipment in the gym, some of which has made a recent comeback; exercise clubs, gymnastic rings, chest expander. I don’t think they predicted the come back of such devices: those were probably cutting edge in 1967. Oh yeah, the medical scanner sends data back to the community medical center: HIPPA records apparently don’t apply in 1967 future, as opposed to our present shitty future, because people didn’t think of themselves as living in a sinister  oligopoly careening towards totalitarianism as we do now.

gym

gym

In 1967 future, you video call your far away buddy to make travel plans, just like now on skype. But in 1967 future you could pick between a golf course in Monterey and one in Mexico City for a casual afternoon of golf, depending on the weather forecast. Because in those days, it seemed inevitable that supersonic or even hypersonic air travel be cheap and convenient. They had no way of knowing the oil crisis would come, just as they had no way of knowing you’d need to arrive 3 hours early to the airport because of imbecile US foreign policy hubris. Remember you didn’t even need a photo ID to get on a plane until 1999 or so; you could go to the airport with a bundle of cash and fly anywhere you wanted to; just like in 1967. In a later scene in the video, pals from Philippines and Paris show up for a house party, because, again, supersonic (maybe hypersonic) flight is super cheap in the 1967 future.

skype in the future

skype in the future

Hobbies in the future: the lady of the house has a fine arts degree and makes pots at home. I actually know a few people like this, and suspect there were people like this in 1967, but it’s really more of an upper middle class thing than a future thing. It’s arguably more upper middle class now for the missus to work for a non-profit. Video games in 1967 future seemed to be restricted to chess. 1999 shabby future had stuff like Castle Wolfenstein and was legitimately less shitty than the imagined 1967 future. It’s probably better for kids to play computer chess though.

chess

Parties in the 1967 future looked better than modern parties; people dressed stylishly and listened to decent music while having enlightened conversation. This is pretty rare these days, though I suppose people do often have “parties” centered around the TV the way they did.

party!

party!

The 1999 future as envisioned in 1967 seemed like a nice place. Everything is convenient. People spent a lot of time bettering themselves with productive hobbies; making artistic pots and breeding interesting plants when they’re not doing a man’s work sending people to colonize Mars or playing duets with your child on a giant synthesizer. Friendships were cultivated all over the world, and travel was trivial and cheap. People in the 1967 envisioned future were apparently very worried about getting fat; I can only speculate that this was an actual concern of 1967, which is probably why everyone looks so slim in those old timey “people watching the moon shot” photos. I’m not sure what happened to that; perhaps cheap insulin has made people worry about it less. People in 1967 were also very concerned with overpopulation and foodstuffs to feed the teeming masses, which is why food came up so much in the video, and why the future family only had one offspring. While the 1967 envisioned future seemed preternaturally clean and environmentally sound, upper middle class neuroses now a days are more overtly concerned with pollution and environmental issues. I am guessing the household conveniences of disposable dishes, self-cleaning closets and pre-made meals were some technical reflection on the cultural changes between the sexes brewing in the 60s. In 1967 it probably seemed like you could solve these looming cultural upheavals using technology; just give the missus some self-cleaning closets and a machine which does the cooking. I couldn’t help but think that the Housewife of the future seemed a little bored. Honestly the whole family seemed  pretty spaced out and lost, but perhaps that’s because plot, characterization and motivation in industrial videos is not always a priority.

They did guess that computers would be important in the home, which was far from obvious at that point. They also guessed that some kind of networked computer system would be routine, which was a very good guess, as computer networks were entirely military up to that point. Oh yeah, and unlike lots of science fiction movies, the screens of the future were flat, rather than CRT based.

It would be interesting to find a modern “home of the future” video by a modern industrial concern; maybe there is one by Microsoft or Apple. I doubt as their future is as interesting and healthy seeming as this future. Perhaps some visionary should attempt this, if only for aspiration purposes.

Atlas data structure: columnar NoSQL for Kerf

Posted in Kerf, tools by Scott Locklin on August 26, 2016

Kerf introduces a new data structure called an “Atlas” that we think is a helpful thing to have inside of a programming language. We’ve found it very useful to have database Tables inside of a programming language, and the Atlas concept is a natural extension of that. Be careful about jumping to conclusions, though, since an Atlas does a few special things that make it unlike what you might expect. I’ll give a preview of the major points here:

Automatic indexing
Responds to SQL
First-class language type
Columnar implementation

We didn’t spend much time talking about Atlases originally, because interest in NoSQL-style computation seemed to be on the wane. Recently, however, we’ve had a lot of requests for those sorts of applications, and so a detailed description seems in order. (If you’ve come across any interesting problems like that in your work, tell us about them.)

If a Table is a way of including a SQL table inside of the language, then an Atlas is a way of including a NoSQL store: none of the rows have to have the same columns. In other words, an Atlas is a schemaless table. The Atlas is a generalization of the Table where the rows don’t have to be uniform. In one sense, an Atlas is a sparse Table. You could also think of a Table as a vectorized Atlas.

read the full post here.

 

Numeric linear algebra code: an appreciation

Posted in Design by Scott Locklin on May 26, 2016

Most computer science guys and “software engineers” never deal with the floating point end of their computer machines. This is too bad, as the computer was invented basically to do floating point calculations, whether to build nuclear weapons or to intercept Rooskie bombers. The present use cases of using computers to watch TV, sell underpants on the internet, mining bitcoins, and sending email to the guy across the cubicle from you are later developments: all integer oriented.

Because the subject is so old and obscure, you have to be a sort of historian of science to understand why things are the way they are on the floating point side of the computer machine. You also have to know Fortran, because that’s more or less what most of it is written in. In fact, you have to know old Fortran, because an awful lot of it was written a long time ago.

Much longer ago ago than this even

It is an exaggeration to say everything you can do to simulate or model the world happens using numeric linear algebra of some kind, but it isn’t much of an exaggeration. Numeric linear algebra can be dense, meaning all numbers are defined, and a matrix looks like a matrix in memory, or sparse meaning most of the numbers are 0 and it looks like a hash table in memory.  Most problems are inherently dense, but sparsification can make impossible things possible, and there are many data science applications (recommendation engines for example) where sparsity can be assumed if you think your matrix of data has any meaning to it.

You’d think this sort of thing is a trivial problem, but it isn’t. The reason it is two fold. One is the operations are hard. A naive  dense square matrix multiply with no trickery involved is O(n^3). If it’s dense, and you need to keep all three matrices around, it’s 3 * O(n^2) in memory. There is an additional problem here which “big O” doesn’t say much about. When you have big-O memory problems, you have IO problems. Your computer doesn’t operate directly on memory chips you install on your computer; it operates directly on registers. While matrix multiply is just vector multiply and sum, the conga dance of doing this in a way that maximizes the data moving in and out of the registers, caches and main memory is extremely intricate and usually machine dependent (because everyone’s computer has a slightly different memory profile).

Most of you have never thought about these matters, because you haven’t tried to simulate a quantum mechanical system, or solved differential equations using finite element analysis. If you build your linear algebra library right, you can get factors of 100 or 1000 speedup. That’s not a big-O speedup, but it sure as hell matters. Computer dorks worry a lot about big-O. Of course, big-O matters very much for both memory and processor cycles. But other things matter too, and computer dorks rarely explicitly worry about them, in part because they have no way of really understanding when they’re happening. I’d posit for any interestingly “large” problem, you’re dealing with something I call “big-IO.” Once you get past having a correct linear algebra algorithm, big-IO is screechingly important on practical problems. It’s the difference between being able to solve a problem and not solve a problem.

I think I’ve convinced any sane reader that matrix multiplies are hard. But this is usually the easiest thing you have to deal with, as it is an actual array operation; something that can be done without explicit loops and branches. QR decompositions, Givens rotations, Eigenvalues, Eigenvectors, Singular Value Decompositions, LU decomposition, inverses, partial inverses; these are more algorithmically challenging. Depending on the properties of the matrix you’re working with (and there’s no simple way to make matrices introspective to tell you this), there may be cheap solutions to these problems, and there may be very expensive ones. Lots of interesting problems are in the O(n^3) range. Regardless of what you use, you have “big-IO” bottlenecks everywhere.

Further complicating your problem, linear algebra on a computer also takes place on several types of floating point data: 32bit/float, 64bit/double and the short and long versions of complex numbers.  Some problems are inherently only 32 bit, some are 64 bit; some are inherently real numbers, and some complex numbers. So already, we’re talking about every kind of operation having 4 different types of implementation, all of which must be written and maintained and optimized for your IO and data locality requirements.

 

Most dense linear algebra work presently happens in something called LAPACK. If you want to calculate eigenvectors in Matlab, Incanter/Clojure, Python, R, Julia and what have you: it’s almost certainly getting piped through LAPACK. If you’re working in C, C++ or Fortran, you’re still probably doing in via LAPACK. If you’re doing linear algebra in Java, you are a lost soul, and you should seriously consider killing yourself, but the serious people I know who do this, they allocate blobs of memory and run LAPACK on the blobs. The same thing was true 25 years ago. In fact, people have basically been running their numerics code on LAPACK for over 40 years when it was called EISPACK and LINPACK.  Quite a lot of it conforms with… Fortran 66; a language invented 50 years ago which is specifically formatted for punched cards. That is an astounding fact.

mx5

Lapack: significantly older than this photo; still being used on your computer now

LAPACK is a sort of layercake on top of something called the BLAS (“Basic Linear Algebra Subroutines”). I think BLAS were originally designed as a useful abstraction so your Eigendecomposition functions have more elementary operations in common with your QR decomposition functions. This made LAPACK better than its ancestors from a code management and complexity point of view. It also made LAPACK faster, as it allowed one to use machine optimized BLAS when they are available, and BLAS are the type of thing a Fortran compiler could tune pretty well by itself, especially on old-timey architectures without complex cache latency. While most of these functions seem boring, they are in fact extremely interesting. Just to give a hint: there is a function in there for doing matrix-multiply via the Winograd version of the Strassen algorithm, which multiplies matrices in O(N^2.8) instead of O(N^3). It’s the GEMMS family of functions if you want to go look at it. Very few people end up using GEMMS, because you have to be a numerical linear algebraist to understand when it is useful enough to justify the O(N^0.2) speedup. For example, there are exactly no Lapack functions which call GEMMS. But GEMMS is there, implemented for you, just waiting for the moment when you might need to solve … I dunno, a generalized Sylvester equation where Strassen’s algorithm applies.

BLAS can be hyperoptimized for an individual machine by specialized packages like ATLAS or GotoBLAS (and descendants BLIS and OpenBLAS). Usually, it’s worth a factor of 5 or so, so I usually do it, even though it is a pain in the ass. Those packages with your Linux distribution that call themselves ATLAS BLAS; they are technically, but they’re never as fast as rolling your own. The original GotoBLAS were  mostly hand tuned assembler, meta-compiled into very fast BLAS for various permutations and combinations of supported architecture. They’re not called GotoBLAS because they use goto statements (though they do); they’re named after the author, Goto Kazushige, who appears to be some kind of superhuman mentat.

LAPACK is intensely important. Computer people who are not physicists or electrical engineers have probably never given it a second thought. The fact that they’re old Fortran code has implications. The most obvious one is Fortran arrays are column major, just like Linear Algebra itself is. I have no idea why C decided to be row-major; probably because they weren’t doing linear algebra. There are ways of handling this, but it ‘s one more thing you have to keep track of, and it can prevent you from doing things on the C side without expensive memory copies. There is also the matter that because old school Fortran looks like stack allocation of arrays (in code appearance only), you have to do weird things like instantiate your arrays and bizarro looking “workspaces” way up the calling pipeline when you’re calling in a C-like language. This is painful, and efforts have been made (LAPACKE) to make the API a little more friendly where this is done under the covers.

mx1

The problem with stuff like this: if you’ve already gone through the trouble of porting a version of C or Fortran LAPACK to your system, LAPACKE makes you do it all over again. The only thing you get out of this exercise is a nicer calling convention, except you have to write the code for your new and improved calling convention, and you don’t get anything extra from this work. So the old calling conventions persist, and probably will persist for another 20-30 years. People will probably be coding up errors that amount to “punched card rejected” in 2050 or 2060.

It’s weird that we still use LAPACK, but considering the difficulty of writing such a thing and moving it from place to place, not terribly surprising. There have been attempts at rewrites, some of which look pretty good to me. FLENS was one of them. I’ve never actually used this, though I have struggled with some vintage of its peculiar build system when examining a neural net package I was interested in. Considering the fact that I found it easier to write my own neural net than to get an old Python package based on FLENS working, I don’t see this project taking over any time soon. While calling FLENS from C++/Python might have been sweet, it didn’t seem useful enough to justify its existence. Another attempt was LibFLAME, which I have never attempted to use. LibFLAME was claiming some performance improvements, which is a reason to think about using it. It was clean and easy to read and came with Goto-san’s enhanced BLAS. Unfortunately, the last major release was in 2010, and the last point release in March of 2014, so I’m presuming the authors are doing other things now. As a historical point, LibFLAME actually employed Goto-san back when he was writing GotoBLAS. Unfortunately for the libFLAME team, he is now at Intel, presumably working on MKL.

mx3

For all this, you’d think there has been no progress in numeric dense linear algebra. This isn’t remotely true. It is one of the most interesting areas in computer science research at present. All kinds of crazy things have happened since LAPACK was written. They’re scattered to the winds, existing as scraps of C/Matlab/Fortran. In fact, I would even go so far as to say LAPACK doesn’t even contain the most interesting subset of available dense numeric linear algebra routines, though it inarguably contains the most useful subset. Just one obvious example of its deficiencies; the standard eigen-decomposition routine in LAPACK calculates the complete eigen-decompostion of a matrix. Very often, you only need the top eigenvectors, and that’s a lot cheaper; you can use a Lanczos algorithm. What does one do when this happens? Well, there’s this other ancient Fortran numeric linear algebra package called ARPACK out there. Usually, this gets used, very often for this one function.  What about sparse methods? Well, that’s another package. In Fortran days it was IMSL or SparseKit. Now a days, there are many choices.

If I had to bet on a future linear algebra package taking over, it would be libelemental.  I only heard about this last year (thanks Ryan), and I have yet to use it for anything important, but it appears to be a very good place to stick new numeric linear algebra algorithms. The problem with it is it depends on a lot of other stuff; LAPACK,  libFLAME (optionally for the good parts anyway), Scalapack (old Fortran code for distributed matrix math) and the kitchen sink. It would be nice if they eventually replace these old pieces, but in the meanwhile, it has a decent framework for fetching and building some version of them. A very big upside to libelemental is it gives you access to a lot of useful old code, via a nice modern C API and a modern C++ API. It also gives you access to some useful things built on top of these guys, such as non-negative matrix factorization and skeleton decomposition. It  includes convex optimization routines, logistic regression, and quite  few other things that are nice to have kicking around. With luck, Jack Poulson, the primary author, will dedicate enough of his time to keep this going and turn it into something that lots of other code depends on out of the box. Seems like there is enough interest at Stanford to keep this moving forward.