It's here again; a few weeks early this year: the summer crush. We deliver our big update to systems at work in August. User Acceptance Testing (UAT) takes place in June and July. So, June tends to be pretty insane as we try to get things wrapped up.
This year, the pressure has come a bit early because the re-platform is such a big deal. So, schoolwork is going to take a back seat for a while and I probably will only post once or twice a week through June.
Friday, May 26, 2017
Wednesday, May 24, 2017
Randomized least squares
Here's a somewhat related take on sampling. The emphasis here is on how to actually perform the least squares computation efficiently. In stats class, this is done with QR factorization. That's an O(mnn) algorithm where m is the number of constraints and n is the number of data points. Squaring the number of rows when the number of rows goes into the trillions results in a really, really big number.
Reference: Iyer et al, A randomized least square solver for terabyte-sized dense overdetermined systems. Journal of Computational Science 2016.09.007.
Iyer looks at ways to sample the data and then perform the regression on the sample. This is actually part of a whole field of computational algebra which goes by RandNLA (Randomized Numerical Linear Algebrea). The basic idea is to transform the data into a smaller set which produces a solution that provably approximates the original problem with high probability.
Transforms that have been tried include Hadamard, Randomized Fourier, and Blendenpik. This paper focuses on the latter. The algorithm is implemented on a 5210-node super computer and it appears to work pretty well.
Most of the paper is straight computational considerations; primarily efficiency and preservation of accuracy. Both of these are extremely important when doing large matrix operations. Not so much in my problem domain. They do spend a little time on the randomized transform, but not enough to use it as a primary reference. I'll need to find better references on Blendenpik as well as others.
Reference: Iyer et al, A randomized least square solver for terabyte-sized dense overdetermined systems. Journal of Computational Science 2016.09.007.
Iyer looks at ways to sample the data and then perform the regression on the sample. This is actually part of a whole field of computational algebra which goes by RandNLA (Randomized Numerical Linear Algebrea). The basic idea is to transform the data into a smaller set which produces a solution that provably approximates the original problem with high probability.
Transforms that have been tried include Hadamard, Randomized Fourier, and Blendenpik. This paper focuses on the latter. The algorithm is implemented on a 5210-node super computer and it appears to work pretty well.
Most of the paper is straight computational considerations; primarily efficiency and preservation of accuracy. Both of these are extremely important when doing large matrix operations. Not so much in my problem domain. They do spend a little time on the randomized transform, but not enough to use it as a primary reference. I'll need to find better references on Blendenpik as well as others.
Monday, May 22, 2017
Bag of Bootstraps
I really hope at least some of my readers get the reference to Louis CK's "Bag of ..." routine.
For those that don't, oh well, you could always google it. Meanwhile, here's the math:
Reference: Kleiner, A, Talwalkar, A, Sarkar, P, Jordan, M: A scalable bootstrap for massive data. Journal or the Royal Statistical Society, 2014 Part 4, 795-816.
The bootstrap is a technique for estimator evaluation that's been around for a while. The name comes from the common phrase of "pulling oneself up by their bootstraps." It's a nod to the fact that the appraisal uses the same data that the estimator is derived from. That said, the technique is sound and widely used.
The problem is that with really big data sets, it becomes computationally infeasible in it's basic form. The authors of this paper show how, rather than using the entire data set at once, one can chop the data set into lots of chunks, apply the boostrap to each chunk and essentially average the results to get the same answer. They call this the "Bag of little Bootstraps".
What interests me is that they have stuck with uniform sampling of items to get their smaller samples. Why? Is there some reason you couldn't bias the tails? If that still produces good results, that would be a big deal for my problem space. So, I need to see if anybody has addressed that. If not, it's a great opportunity for a result that's much more theoretical than what I have been doing while still wholly relevant.
I'm talking with my adviser about it tomorrow.
For those that don't, oh well, you could always google it. Meanwhile, here's the math:
Reference: Kleiner, A, Talwalkar, A, Sarkar, P, Jordan, M: A scalable bootstrap for massive data. Journal or the Royal Statistical Society, 2014 Part 4, 795-816.
The bootstrap is a technique for estimator evaluation that's been around for a while. The name comes from the common phrase of "pulling oneself up by their bootstraps." It's a nod to the fact that the appraisal uses the same data that the estimator is derived from. That said, the technique is sound and widely used.
The problem is that with really big data sets, it becomes computationally infeasible in it's basic form. The authors of this paper show how, rather than using the entire data set at once, one can chop the data set into lots of chunks, apply the boostrap to each chunk and essentially average the results to get the same answer. They call this the "Bag of little Bootstraps".
What interests me is that they have stuck with uniform sampling of items to get their smaller samples. Why? Is there some reason you couldn't bias the tails? If that still produces good results, that would be a big deal for my problem space. So, I need to see if anybody has addressed that. If not, it's a great opportunity for a result that's much more theoretical than what I have been doing while still wholly relevant.
I'm talking with my adviser about it tomorrow.
Friday, May 19, 2017
On the Theory of Sampling from Finite Populations
Well, I was right about this one: it's one of those citation classics that you simply have to put into your bibliography. It's also a really good paper. Definitely required reading for any stratified sampling work.
On the Theory of Sampling from Finite Populations Morris H. Hansen and William N. Hurwitz The Annals of Mathematical Statistics Vol. 14, No. 4 (Dec., 1943), pp. 333-362
The key result is the estimator which weights a point by the inverse of its selection probability. In this paper, this is done with replacement, that is, once you've sampled a point, you return it to the population and may well sample it again. In CISS, we don't do that. Once a block is sampled, it's removed from further consideration. That does require some adjustments, but the basic principal is the same, the strata that get fully sampled (the tails) get a lot less weight in the estimate than the stata that have only a small percentage of blocks read.
This paper also has some good references on cluster sampling. I don't think I want to go back too much earlier than 1943 for my citations since most of the heavy lifting on cluster sampling was done in the 1980's and 1990's, but those references can be reversed. By looking for other papers that cite them, I can find newer stuff that is relevant.
On the Theory of Sampling from Finite Populations Morris H. Hansen and William N. Hurwitz The Annals of Mathematical Statistics Vol. 14, No. 4 (Dec., 1943), pp. 333-362
The key result is the estimator which weights a point by the inverse of its selection probability. In this paper, this is done with replacement, that is, once you've sampled a point, you return it to the population and may well sample it again. In CISS, we don't do that. Once a block is sampled, it's removed from further consideration. That does require some adjustments, but the basic principal is the same, the strata that get fully sampled (the tails) get a lot less weight in the estimate than the stata that have only a small percentage of blocks read.
This paper also has some good references on cluster sampling. I don't think I want to go back too much earlier than 1943 for my citations since most of the heavy lifting on cluster sampling was done in the 1980's and 1990's, but those references can be reversed. By looking for other papers that cite them, I can find newer stuff that is relevant.
Thursday, May 18, 2017
Leveraging and Weighted Least Squares
Reference: Ping Ma & Xiaoxiao Sun: Leveraging for big data regression. WIREs Comput Stat 2014. doi: 10-.1002/wics.1324
Don't let the Chinese names fool you. These guys are at University of Georgia and they write quite well in English. The "paper" (I have no idea if Wiley peer reviews this publication, but it seems legit) focuses on applying linear models to very large data sets. While I have no particular interest in that, if you can fit a linear model, you can obviously estimate a mean (or, at least a median), and that I do want to do. In fact, this paper is basically the theoretical validation of CISS that I was looking for.
Ordinary Least Squares is really unstable when using heavy-tailed distributions. By intentionally biasing the sample towards the tails (and, obviously, adjusting for that bias via a Weighted Least Squares), you get better convergence. Hooray, I already knew that. Some of their proofs are useful, though. In particular, they show the estimators are unbiased. Since showing the estimator of a mean is unbiased is pretty obvious, I had done that a little less formally in my paper. Rather than beef up those arguments, I can leave them as is and just cite this as backup.
More importantly, they reference two other lines of inquiry that will get put on the must read list, plus another that probably is only marginally relevant, but might be good to know about anyway:
Priority papers:
Drineas & Mahoney: Looking at computational efficiency of sub-sampled regression. Two papers cited: Sampling algorithms for l2 regression and applications. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami 2006 and Faster least squares approximation. Numer Math 2010.
Ma & Mahoney: Generalizing the above results. Again, two papers: A statistical perspective on algorithmic leveraging. ArXiv e-prints, 6/2013 and the same title (same paper?) in Proceedings of the 31st International Conference on Machine Learning, Beijing 2014
Background:
Hansen & Hurwitz: Defines an estimator based on a weighted sample where the weight is the inverse of the probability of the point being selected (this is sort of what CISS uses, though since CISS samples without replacement, there's a little more to it). The reference is old, which means it's probably one of those results that you simply have to cite in a complete literature review: On the theory of sampling from a finite population. Ann math Stat 1943, 14:333-362.
So, there's one paper reviewed. Everybody sing now:
99 bottles of beer on the wall...
Don't let the Chinese names fool you. These guys are at University of Georgia and they write quite well in English. The "paper" (I have no idea if Wiley peer reviews this publication, but it seems legit) focuses on applying linear models to very large data sets. While I have no particular interest in that, if you can fit a linear model, you can obviously estimate a mean (or, at least a median), and that I do want to do. In fact, this paper is basically the theoretical validation of CISS that I was looking for.
Ordinary Least Squares is really unstable when using heavy-tailed distributions. By intentionally biasing the sample towards the tails (and, obviously, adjusting for that bias via a Weighted Least Squares), you get better convergence. Hooray, I already knew that. Some of their proofs are useful, though. In particular, they show the estimators are unbiased. Since showing the estimator of a mean is unbiased is pretty obvious, I had done that a little less formally in my paper. Rather than beef up those arguments, I can leave them as is and just cite this as backup.
More importantly, they reference two other lines of inquiry that will get put on the must read list, plus another that probably is only marginally relevant, but might be good to know about anyway:
Priority papers:
Drineas & Mahoney: Looking at computational efficiency of sub-sampled regression. Two papers cited: Sampling algorithms for l2 regression and applications. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami 2006 and Faster least squares approximation. Numer Math 2010.
Ma & Mahoney: Generalizing the above results. Again, two papers: A statistical perspective on algorithmic leveraging. ArXiv e-prints, 6/2013 and the same title (same paper?) in Proceedings of the 31st International Conference on Machine Learning, Beijing 2014
Background:
Hansen & Hurwitz: Defines an estimator based on a weighted sample where the weight is the inverse of the probability of the point being selected (this is sort of what CISS uses, though since CISS samples without replacement, there's a little more to it). The reference is old, which means it's probably one of those results that you simply have to cite in a complete literature review: On the theory of sampling from a finite population. Ann math Stat 1943, 14:333-362.
So, there's one paper reviewed. Everybody sing now:
99 bottles of beer on the wall...
Wednesday, May 17, 2017
Coming Eclipse
No, I'm not talking about the total eclipse this summer (though that is also plenty cool and I plan on being in Columbia Missouri for optimal viewing when it happens). Rather I'm talking about Yaya.
As parents, it's natural to want your child to do great things. Even not great things are often puffed up to seem like great things. This is natural. I happily listen to folks telling me about how their kid scored a goal or won a Science Fair ribbon. It's not really bragging (well, usually not); it's just joy in your kid's success and you want to share it. I totally get that and I'm happy to share in it.
It's a little different when your kid gets better than you ever were.
That hasn't happened yet. I was a pretty decent musician by High School standards. My parents were fairly strict about practice time. My private teacher's day job was at Julliard (really!). That kind of support pays dividends. People who knew what they were talking about said with a straight face that I should consider it as a profession.
I indulged that thought for a while but came to realize that it wasn't going to happen. I just didn't have the passion for it that's required to make it your life's work. Music is very cruel to those who give some but not all.
Yaya may well come to the same conclusion. She's not better than I was quite yet (she's only in 7th grade) but, barring some major change of heart, she will be. Whether she has enough passion to make it her life, only she can judge. What's obvious to me is that she has more than I did. She practices more. I never have to enforce it; if anything, I'm telling her to put it down and tend to her other subjects. She asks more. She's constantly hitting me with questions about music. The questions are getting deep enough that I'm having to bust out my music theory texts for some of them and flat out defer to her teachers on others.
Most importantly, she dabbles. She picks up new instruments on a whim. Listens to weird stuff. Tries new things. All the really good musicians I know do these things. Almost all the people I know who do these things are really good musicians.
There was a brief time when I was a bit whimsical about all this. I saw what she was doing, saw the joy it was bringing her, and wondered why I didn't take the same path. I'm past that. As much as I value all the things I learned both about music and life from my years performing, I'm fine with the fact that I gave it up and soon my daughter will be way better than I ever was. It's not pride, it's joy.
Here she is playing her feature with her school jazz band. And, yes, she likes dressing like a dude. Deal with it.
As parents, it's natural to want your child to do great things. Even not great things are often puffed up to seem like great things. This is natural. I happily listen to folks telling me about how their kid scored a goal or won a Science Fair ribbon. It's not really bragging (well, usually not); it's just joy in your kid's success and you want to share it. I totally get that and I'm happy to share in it.
It's a little different when your kid gets better than you ever were.
That hasn't happened yet. I was a pretty decent musician by High School standards. My parents were fairly strict about practice time. My private teacher's day job was at Julliard (really!). That kind of support pays dividends. People who knew what they were talking about said with a straight face that I should consider it as a profession.
I indulged that thought for a while but came to realize that it wasn't going to happen. I just didn't have the passion for it that's required to make it your life's work. Music is very cruel to those who give some but not all.
Yaya may well come to the same conclusion. She's not better than I was quite yet (she's only in 7th grade) but, barring some major change of heart, she will be. Whether she has enough passion to make it her life, only she can judge. What's obvious to me is that she has more than I did. She practices more. I never have to enforce it; if anything, I'm telling her to put it down and tend to her other subjects. She asks more. She's constantly hitting me with questions about music. The questions are getting deep enough that I'm having to bust out my music theory texts for some of them and flat out defer to her teachers on others.
Most importantly, she dabbles. She picks up new instruments on a whim. Listens to weird stuff. Tries new things. All the really good musicians I know do these things. Almost all the people I know who do these things are really good musicians.
There was a brief time when I was a bit whimsical about all this. I saw what she was doing, saw the joy it was bringing her, and wondered why I didn't take the same path. I'm past that. As much as I value all the things I learned both about music and life from my years performing, I'm fine with the fact that I gave it up and soon my daughter will be way better than I ever was. It's not pride, it's joy.
Here she is playing her feature with her school jazz band. And, yes, she likes dressing like a dude. Deal with it.
Tuesday, May 16, 2017
Roadmap
So, when you want to get somewhere, it's helpful to have a map. In that spirit, here's the lay of the land for my summer literature review:
The two rectangles at the top are what I've got now: completed algorithms with demonstrated performance on reasonable test sets. That seems like a good start. So, how to tie them together and pull in enough bona-fide research to make it a dissertation?
My thought is this can evolve into the lower rectangle, which is basically a framework for performing multi-dimensional analysis on huge data sets in real time. The multi-dimensional part is what I've been missing up until now and it's the glue that holds all this together. I didn't really understand that until I put together my term presentation for D-BESt. Generalizing this to relational databases will kill a lot of the optimizations. Restricting the scope greatly increases the potential gains and also moves the research into a bit more of a niche (less likely to get scooped).
The fact that it's a niche, doesn't mean it doesn't have very real value. There are still lots of applications for multi-dimensional analysis. And, multi-dim datasets are growing much faster than existing tools can keep up with.
To get to the lower rectangle will require adding some important features, which are indicated by the diamonds. I thought about drawing arrows, but I don't know that I'll necessarily do them in the most logical order, which would be top to bottom. I'll probably implement them in the order I come up with decent ideas.
As for the ideas, the rounded boxes indicate related topics I can draw from. Again, I considered arrows, showing what related to what, but it got really busy. In general, the closer a rounded box is to a rectangle or diamond, the more relevant it is.
I'm figuring this creates a seed group of around 100 papers, which should be a good start. I'm sure I can't fully digest that many papers over the summer, but I should be able to at least locate them and get the major points into a survey. I'll revisit the details as I move through the actual research.
The two rectangles at the top are what I've got now: completed algorithms with demonstrated performance on reasonable test sets. That seems like a good start. So, how to tie them together and pull in enough bona-fide research to make it a dissertation?
My thought is this can evolve into the lower rectangle, which is basically a framework for performing multi-dimensional analysis on huge data sets in real time. The multi-dimensional part is what I've been missing up until now and it's the glue that holds all this together. I didn't really understand that until I put together my term presentation for D-BESt. Generalizing this to relational databases will kill a lot of the optimizations. Restricting the scope greatly increases the potential gains and also moves the research into a bit more of a niche (less likely to get scooped).
The fact that it's a niche, doesn't mean it doesn't have very real value. There are still lots of applications for multi-dimensional analysis. And, multi-dim datasets are growing much faster than existing tools can keep up with.
To get to the lower rectangle will require adding some important features, which are indicated by the diamonds. I thought about drawing arrows, but I don't know that I'll necessarily do them in the most logical order, which would be top to bottom. I'll probably implement them in the order I come up with decent ideas.
As for the ideas, the rounded boxes indicate related topics I can draw from. Again, I considered arrows, showing what related to what, but it got really busy. In general, the closer a rounded box is to a rectangle or diamond, the more relevant it is.
I'm figuring this creates a seed group of around 100 papers, which should be a good start. I'm sure I can't fully digest that many papers over the summer, but I should be able to at least locate them and get the major points into a survey. I'll revisit the details as I move through the actual research.
Subscribe to:
Posts (Atom)